LLVM 中端优化之 InstCombine

 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

/// Populate the IC worklist from a function, by walking it in depth-first
/// order and adding all reachable code to the worklist.
///
/// This has a couple of tricks to make the code faster and more powerful.  In
/// particular, we constant fold and DCE instructions as we go, to avoid adding
/// them to the worklist (this significantly speeds up instcombine on code where
/// many instructions are dead or constant).  Additionally, if we find a branch
/// whose condition is a known constant, we only visit the reachable successors.
static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL,
                                          const TargetLibraryInfo *TLI,
                                          InstructionWorklist &ICWorklist) {
  bool MadeIRChange = false;
  SmallPtrSet<BasicBlock *, 32> Visited;
  SmallVector<BasicBlock*, 256> Worklist;
  Worklist.push_back(&F.front());

  SmallVector<Instruction *, 128> InstrsForInstructionWorklist;
  DenseMap<Constant *, Constant *> FoldedConstants;
  AliasScopeTracker SeenAliasScopes;

  do {
    BasicBlock *BB = Worklist.pop_back_val();

    // We have now visited this block!  If we've already been here, ignore it.
    if (!Visited.insert(BB).second)
      continue;

    for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
      // 常量折叠指令，如果可能。
    }
    // 如果 terminator 是分支指令，看看有没有明显不可达的分支，若有则跳过。
  } while (!Worklist.empty());

  // 删掉所有不可达的基本块。

  // Once we've found all of the instructions to add to instcombine's worklist,
  // add them in reverse order.  This way instcombine will visit from the top
  // of the function down.  This jives well with the way that it adds all uses
  // of instructions to the worklist after doing a transformation, thus avoiding
  // some N^2 behavior in pathological cases.
  ICWorklist.reserve(InstrsForInstructionWorklist.size());
  for (Instruction *Inst : reverse(InstrsForInstructionWorklist)) {
    // 删掉死代码。
    ICWorklist.push(Inst);
  }

  return MadeIRChange;
}

 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

bool InstCombinerImpl::run() {
  while (!Worklist.isEmpty()) {
    if (Instruction *Result = visit(*I)) {
      ++NumCombined;
      // Should we replace the old instruction with a new one?
      if (Result != I) {
        // Everything uses the new instruction now.
        I->replaceAllUsesWith(Result);

        // Move the name to the new instruction first.
        Result->takeName(I);

        // Insert the new instruction into the basic block...
        BasicBlock *InstParent = I->getParent();
        BasicBlock::iterator InsertPos = I->getIterator();
        Result->insertInto(InstParent, InsertPos);

        // Push the new instruction and any users onto the worklist.
        Worklist.pushUsersToWorkList(*Result);
        Worklist.push(Result);

        eraseInstFromFunction(*I);
      } else {
        // If the instruction was modified, it's possible that it is now dead.
        // if so, remove it.
        if (isInstructionTriviallyDead(I, &TLI)) {
          eraseInstFromFunction(*I);
        } else {
          Worklist.pushUsersToWorkList(*I);
          Worklist.push(I);
        }
      }
      MadeIRChange = true;
    }
  }
  return MadeIRChange;
}

1
2
3

  // A + -B  -->  A - B
  if (match(RHS, m_Neg(m_Value(B))))
    return BinaryOperator::CreateSub(LHS, B);

1

%add = add nsw i32 %a, %b

1
2
3
4
5

Value *X, *Y;
if (match(m_Add(m_Value(X), m_Value(Y)))) {
    X->dump(); // %a
    Y->dump(); // %b
}

1
2

Value *A, *B;
match(m_Mul(m_Add(m_Valule(A), m_Value(B)), m_Add(m_Specific(A), m_Specific(B))))

1
2

Value* A;
match(m_Add(m_Value(A), m_Deferred(A)));

1
2
3

  // LHS + (A + LHS) --> A + (LHS << 1)
  if (match(RHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(LHS)))))
    return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));

1
2
3
4
5

x = a + 1;
y = x + 1;

==>
y = a + 2; // 没有新增指令。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

$ # 在 llvm/test/Transforms/InstCombine 中新增测试。
$ # 更新 check line。
$ python3 llvm/utils/update_test_checks.py --tool-binary=/path-to-your-build-dir/bin/opt 修改的测试文件
$ git commit # 这个就是 precommit test。
$ arc diff # 提交到 Phabricator
$ # 编写新规则
$ ninja # 重新编译
$ # 重新生成 check line，可以在 diff 中清楚看到我们的规则给 IR 带来的改变。
$ python3 llvm/utils/update_test_checks.py --tool-binary=/path-to-your-build-dir/bin/opt 修改的测试文件
$ git commit # 我们的主 patch。