This patch adds FoldPHIUserOpIntoPred, which finds a phi node that is
- used by only one add/sub instruction and
- all its incoming values are ConstantInt or add/sub instruction used only by this phi node.
For such Phi nodes, we can eliminate add/sub instruction after the phi node by changing immediates of previous add/sub instructions.
Example of redundant add instruction to be optimized:
BB1: %add = add i64 %a, 5 # -> immediate will be changed to 6 br label %BB3 BB2: %sub = sub i64 %b, 3 # -> immediate will be changed to 2 br label %BB3 BB3: %phi = phi i64 [ %add, %BB1 ], [ %sub, %BB2 ] %rc = add i64 %phi, 1 # -> will be removed
Additionally, if only one incoming value to the phi node does not meet above conditions, we can move the add/sub instruction to avoid partially redundant computation.
This optimization happens about 19k times (4k for full redundant cases and others for partially redundant cases) while building LLVM/Clang.
I am going to add similar optimization for logical operations as well as add/sub as a separate patch later.