CSCD70-Assignment1 Introduction to LLVM

学习笔记 / 静态分析
字数统计: 1.8k   |   阅读时长≈ 9 分钟

函数信息

没啥好说的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class FunctionInfoPass final : public PassInfoMixin<FunctionInfoPass> {
public:
  PreservedAnalyses run([[maybe_unused]] Module &M, ModuleAnalysisManager &) {
    outs() << "CSCD70 Function Information Pass"
           << "\n";

    /// @todo(CSCD70) Please complete this method.

    for(auto& F : M.functions())
    {
      outs() << "Function Name: " << F.getName() << "\n";
      outs() << "Number of Arguments: " << F.arg_size() << "\n";
      outs() << "Number of Calls: " << F.getNumUses() << "\n";
      outs() << "Number OF BBs: " << F.size() << "\n";
      outs() << "Number of Instructions: " << F.getInstructionCount() << "\n";
    }
    return PreservedAnalyses::all();
  }
}; // class FunctionInfoPass

局部优化

代数恒等式

识别

加减运算中,其中一个操作数为常量0;乘除运算中,其中一个操作数为常量1.

在判别常量的值的时候,需要这样的转化:

1
2
Value* oper1 =In.getOperand(0)
ConstVal1 = dyn_cast<ConstantInt>(oper1)->getSExtValue()

但是在二元运算中,操作数不一定是ConstantInt,所以需要先判别一下:

1
if(isa<ConstantInt>(oper1))

优化

用代数恒等式的最终值代替所有引用该指令结果的地方,然后删除该指令.

1
In.replaceAllUsesWith(AlgebraicIdentity);

删除指令应该在遍历完所有指令之后,否则可能会导致迭代器失效.
一个相关的demo如下:

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec({1,2,3});
    for(std::vector<int>::iterator iter = vec.begin();iter!=vec.end();++iter)
    {
        std::cout << *iter <<" ";
        vec.erase(iter);
    }
}
1
2
3
4
g++ test.cpp && ./a.out
22145664082593 0872 180082552 2 6101240994215 82538  19428801684252 4048 9411899120 87594 220361632 217 91908160516051605 88948 81625610688 288 288 288 211024042 80848 8242 242 242 242 0 80094 85240422961 961 961 961 87619 85558 23824 894 894 894 89286254005 213 959527952795279527221 52042352892352045204520452049 87673 54062283040 040 040 040 84094 84344 840972344 844 844 844 844 844 844 844 844 840972344 840972344 891303733 94279427942794279427942794279427942748211 876164408 540161074 540161016101610161074 540161074 540161074 
......
段错误

将所有要删除的指令加入一个vector,最后统一删除.

1
2
3
4
5
6
7
8
9
10
void delIns(std::vector<Instruction*> InsList)
{
  for(auto& ins : InsList)
  {
    if(ins->isSafeToRemove())
    {
      ins->eraseFromParent();
    }
  }
}

注意这里使用的是eraseFromParent,使用removeFromParent会导致如下错误:

1
2
Instruction referencing instruction not embedded in a basic block!
  %5 = sdiv i32 %3, 10
1
2
3
4
5
6
7
8
/// This method unlinks 'this' from the containing basic block, but does not
/// delete it.
void removeFromParent();

/// This method unlinks 'this' from the containing basic block and deletes it.
///
/// \returns an iterator pointing to the element after the erased one
SymbolTableList<Instruction>::iterator eraseFromParent();

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
PreservedAnalyses AlgebraicIdentityPass::run([[maybe_unused]] Function &F,
                                             FunctionAnalysisManager &) {

  /// @todo(CSCD70) Please complete this method.
  int cnt = 0;
  std::vector<Instruction*> del_InsList;
  for(auto& BB : F)
  {
    for(auto& In : BB)
    {
      if(In.isBinaryOp())
      {
        Value* AlgebraicIdentity = 0;
        bool flag = false;
        auto oper1 =In.getOperand(0);
        auto oper2 =In.getOperand(1);
        int64_t ConstVal1,ConstVal2;
        if(isa<ConstantInt>(oper1))
          ConstVal1 = dyn_cast<ConstantInt>(oper1)->getSExtValue();
        if(isa<ConstantInt>(oper2))
          ConstVal2 = dyn_cast<ConstantInt>(oper2)->getSExtValue();

        switch (In.getOpcode())
        {
          //x+0 x-0 --> x
        case Instruction::Add:
        case Instruction::Sub:
          if((isa<ConstantInt>(oper1)&&!ConstVal1)||(isa<ConstantInt>(oper2)&&!ConstVal2))
          {
            AlgebraicIdentity = oper1 ? oper1 : oper2;
            flag = true;
          }
          break;
        
        case Instruction::Mul:
        case Instruction::SDiv:
          if((isa<ConstantInt>(oper1)&&ConstVal1==1)||(isa<ConstantInt>(oper2)&&ConstVal2==1))
          {
            AlgebraicIdentity = ConstVal1==1? oper2 : oper1;
            flag = true; 
          }
        break;
        default:
          break;
        }
        if(flag)
        {
          In.replaceAllUsesWith(AlgebraicIdentity);
          del_InsList.push_back(&In);
          ++cnt;
        }
      }
    }
  }
  delIns(del_InsList);
  outs() << "define dso_local void @AlgebraicIdentity(i32 noundef %0) {" << "\n";
  outs() << "Algebraic Identity: " << cnt << "\n";
  return PreservedAnalyses::none();
}

测试

1
make && opt -load-pass-plugin=./libLocalOpts.so -passes=algebraic-identity ./test/TestCase1.ll -o ./TestCase.bc && llvm-dis TestCase.bc -o TestCase.ll

优化前:

1
2
3
4
5
6
7
8
9
10
11
define dso_local void @AlgebraicIdentity(i32 noundef %0) {
  %2 = add nsw i32 %0, 0
  %3 = add nsw i32 0, %0
  %4 = mul nsw i32 %0, 1
  %5 = mul nsw i32 1, %0
  %6 = sub nsw i32 %0, 0
  %7 = sdiv i32 %0, 1
  %8 = call i32 (ptr, ...) @printf(ptr noundef @.str, i32 noundef %2, i32 noundef %3, i32 noundef %4, i32 noundef %5, i32 noundef %6, i32 noundef %7)
  ret void
}

优化后:

1
2
3
4
define dso_local void @AlgebraicIdentity(i32 noundef %0) {
  %2 = call i32 (ptr, ...) @printf(ptr noundef @.str, i32 noundef %0, i32 noundef 0, i32 noundef %0, i32 noundef %0, i32 noundef %0, i32 noundef 1)
  ret void
}

强度削弱

识别

乘除运算,其中一个操作数为2的幂.

优化

在原指令下方增加一条移位指令,移除并删除原指令.这里要用到IRBuilder.
用当前指令来初始化builder,为其设置指令的插入点.

1
2
3
IRBuilder<> builder(&In);
Value* NewIns = builder.CreateShl(oper,shift);
In.replaceAllUsesWith(NewIns);

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
int getshift(int x)
{
  if(!((x > 0) && !(x & (x - 1))))
    return -1;
  int i = -1;
  while(x)
  {
    x = x>>1;
    ++i;
  }
  return i;

}

PreservedAnalyses StrengthReductionPass::run([[maybe_unused]] Function &F,
                                             FunctionAnalysisManager &) {

  /// @todo(CSCD70) Please complete this method.
  int cnt = 0;
  std::vector<Instruction*> del_InsList;
  for(auto& BB : F)
  {
    for(auto& In : BB)
    {
      if(In.isBinaryOp())
      {
        int shift = 0;
        Value* oper;
        auto oper1 =In.getOperand(0);
        auto oper2 =In.getOperand(1);
        int shift1 = -1,shift2 = -1;
        if(isa<ConstantInt>(oper1))
          shift1 = getshift(dyn_cast<ConstantInt>(oper1)->getSExtValue());
        if(isa<ConstantInt>(oper2))
          shift2 = getshift(dyn_cast<ConstantInt>(oper2)->getSExtValue());



        switch (In.getOpcode())
        {
        case Instruction::Mul:
        case Instruction::SDiv:
        case Instruction::UDiv:
          if((isa<ConstantInt>(oper1)&&shift1!=-1)||(isa<ConstantInt>(oper2)&&shift2!=-1))
          {
            shift = shift1==-1 ? shift2 : shift1;
            oper = shift1==-1? oper1 : oper2;
            
            IRBuilder<> builder(&In);
            
            Value* NewIns;
            switch (In.getOpcode())
            {
            case Instruction::Mul:
              NewIns = builder.CreateShl(oper,shift);
              break;
            case Instruction::SDiv:
            case Instruction::UDiv:
              NewIns =builder.CreateAShr(oper,shift);
              break;            
            }

            In.replaceAllUsesWith(NewIns);
            del_InsList.push_back(&In);
            cnt++;
          }
          break;
        default:
          break;
        }
      }
    }
  }
  delIns(del_InsList);
  outs() << "define dso_local void @StrengthReduction(i32 noundef %0) {" << "\n";
  outs() << "strength-reduction: " << cnt << "\n";
  return PreservedAnalyses::none();
}

测试

1
make && opt -load-pass-plugin=./libLocalOpts.so -passes=algebraic-identity,strength-reduction ./test/TestCase2.ll -o ./TestCase.bc && llvm-dis TestCase.bc -o TestCase.ll

优化前:

1
2
3
4
5
6
7
8
9
define dso_local void @StrengthReduction(i32 noundef %0) {
  %2 = mul nsw i32 %0, 2
  %3 = mul nsw i32 64, %0
  %4 = sdiv i32 %0, 4
  %5 = sdiv i32 %0, 128
  %6 = call i32 (ptr, ...) @printf(ptr noundef @.str.1, i32 noundef %2, i32 noundef %3, i32 noundef %4, i32 noundef %5)
  ret void
}

优化后:

1
2
3
4
5
6
7
8
define dso_local void @StrengthReduction(i32 noundef %0) {
  %2 = shl i32 %0, 1
  %3 = shl i32 %0, 6
  %4 = ashr i32 %0, 2
  %5 = ashr i32 %0, 7
  %6 = call i32 (ptr, ...) @printf(ptr noundef @.str.1, i32 noundef %2, i32 noundef %3, i32 noundef %4, i32 noundef %5)
  ret void
}

Multi-Instruction Optimization

识别

以先加后减运算为例: 

1
c = a+b;d = c-a;  -->  c = a+b;d = b;

对于指令In,遍历其UserIn,如果UserIn的操作符含义与In的操作符相反(如加与减,乘与除),且UserIn的第二个操作数(减数)与In的任一操作数(加数)均为对同一个Value的引用.

其实就是UserIn正好抵消In的运算,具体是否可消除模式的识别与操作符本身有关,这里仅以上述先加后减的模式进行优化.

优化

以之前的值替换即可.

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
PreservedAnalyses MultiInstOptPass::run([[maybe_unused]] Function &F,
                                        FunctionAnalysisManager &) {

  /// @todo(CSCD70) Please complete this method.
  int cnt = 0;
  std::vector<Instruction*> del_InsList;
  for(auto& BB : F)
  {
    for(auto& In : BB)
    {
      if(In.isBinaryOp())
      {
        int op = -1 ; //1 -> + ; 0 -> -;
        int Incnt = 0;
        auto oper1 = In.getOperand(0);
        auto oper2 = In.getOperand(1);
        switch (In.getOpcode())
        {
        case Instruction::Add:
          for(User* user:In.users())
          {
            if(Instruction* UserIn = dyn_cast<Instruction>(user))
            {
              Value* Val = NULL;
              if(In.isBinaryOp())
              {
                if(UserIn->getOpcode() == Instruction::Sub)
                {
                  if(UserIn->getOperand(1) == oper1)
                    Val = oper2;
                  else if(UserIn->getOperand(1) == oper2)
                    Val = oper1;

                  if(Val)
                  {
                    UserIn->replaceAllUsesWith(Val);  
                    del_InsList.push_back(UserIn);
                    ++cnt;
                  }
                }
              }
            }
          }
          break;
        
        default:
          break;
        }
      }
    }
  }
  delIns(del_InsList);
  outs() << "define dso_local void @MultiInstOpt(i32 noundef %0, i32 noundef %1) {" << "\n";
  outs() << "multi-inst-opt: " << cnt << "\n";
  return PreservedAnalyses::none();
}

测试

1
make && opt -load-pass-plugin=./libLocalOpts.so -passes=algebraic-identity,strength-reduction,multi-inst-opt ./test/TestCaseBasic.ll -o ./TestCase.bc && llvm-dis TestCase.bc -o TestCase.ll
1
2
3
4
5
6
7
8
define dso_local void @MultiInstOpt(i32 noundef %0, i32 noundef %1) {
  %3 = add nsw i32 %0, 3
  %4 = sub nsw i32 %3, 3
  %5 = add nsw i32 %0, %1
  %6 = sub nsw i32 %5, %1
  %7 = call i32 (ptr, ...) @printf(ptr noundef @.str.1, i32 noundef %3, i32 noundef %4, i32 noundef %5, i32 noundef %6)
  ret void
}
1
2
3
4
5
6
define dso_local void @MultiInstOpt(i32 noundef %0, i32 noundef %1) {
  %3 = add nsw i32 %0, 3
  %4 = add nsw i32 %0, %1
  %5 = call i32 (ptr, ...) @printf(ptr noundef @.str.1, i32 noundef %3, i32 noundef %0, i32 noundef %4, i32 noundef %0)
  ret void
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2024 翰青HanQi

请我喝杯咖啡吧~

支付宝
微信