In this recipe, you will learn about reassociating expressions and how it helps in optimization.
- Write the test case for a simple reassociate transformation:
$ cat testreassociate.ll define i32 @test(i32 %b, i32 %a) { %tmp.1 = add i32 %a, 1234 %tmp.2 = add i32 %b, %tmp.1 %tmp.4 = xor i32 %a, -1 ; (b+(a+1234))+~a -> b+1233 %tmp.5 = add i32 %tmp.2, %tmp.4 ret i32 %tmp.5 }
- Run the reassociate pass on this test case to see how the code is modified:
$ opt testreassociate.ll –reassociate –die –S define i32 @test(i32 %b, i32 %a) { %tmp.5 = add i32 %b, 1233 ret i32 %tmp.5 }
By reassociation, we mean applying algebraic properties such as associativity, commutativity, and distributivity to rearrange an expression to enable other optimizations, such as constant folding, LICM, and so on.
In the preceding example, we used the inverse property to eliminate patterns such as "X + ~X" -> "-1" using reassociation.
The first three lines of the test case give us the expression of the form (b+(a+1234))+~a. In this expression, using the reassociate pass, we transform a+~a to -1. Hence, in the result, we get the final return value as b+1234-1 = b+1233.
The code that handles this transformation is in the Reassociate.cpp file, located under lib/Transforms/Scalar.
If you look into this file, specifically the code segment, you can see that it checks whether there are a and ~a in the operand list:
if (!BinaryOperator::isNeg(TheOp) && !BinaryOperator::isNot(TheOp))
continue;
Value *X = nullptr;
…
…
else if (BinaryOperator::isNot(TheOp))
X = BinaryOperator::getNotArgument(TheOp);
unsigned FoundX = FindInOperandList(Ops, i, X);The following code is responsible for handling and inserting the -1 value when it gets such values in the expression:
if (BinaryOperator::isNot(TheOp)) {
Value *V = Constant::getAllOnesValue(X->getType());
Ops.insert(Ops.end(), ValueEntry(getRank(V), V));
e += 1;
}