[Reassociate] Stop linearizing all associative expression trees w/o profitability

[reames]

Summary

The Reassociate pass currently does two things. First, it factors out common sub-expressions and otherwise *optimizes* the expression tree. Second, it blindly linearizes the result, regardless of whether any *optimizations* were performed.

This second part is problematic, as we don't have a robust scheduler anywhere else in the pipeline, and a linear execution order is distinctly non-optimal on modern CPUs. Consider the following (toy) example:
for (int i = 0; i < N; i++) {

int tmp = a[i];
tmp += b;
acquire_fence();
sum += tmp;

}

In this case, we end up with a nicely unrolled loop, but due to the linearization of the add expressions, we emit a long chain of additions with a single target register. This form bottlenecks in the scheduler on modern X86 chips for a 25% performance slow down over the original form.

Note that to do this, I had remove a stale piece of code which tried to aggressively re-try expression formation after removing uses. Given that code has been disabled since 2012, I'm not too worried about that.

An alternate approach to this problem would be to invest in building a scheduler for associative expressions which can properly balance ILP and register pressure. I'm hoping not to have to solve that problem. :)

[lebedev.ri]

I'm seeing many regressions in diffs.

Honestly i'd say this is the wrong fix/direction,
i don't recall any such thing as register pressure
for middle-end IR, there are no registers here, only value.

[reames]

Rebase remainder of test changes after autogening them in a separate commit..

[reames]

In D65614#1611255, @lebedev.ri wrote:

I'm seeing many regressions in diffs.

Can you point to a specific example of what you mean? I haven't studied every single one closely, but on a skim, I am not seeing regressions, so I'm curious what you mean?

Honestly i'd say this is the wrong fix/direction,
i don't recall any such thing as register pressure
for middle-end IR, there are no registers here, only value.

Right, but for the same reason, why should we be perturbing the input without reason? We don't have any information about profitability to justify the transform.

[lebedev.ri]

In D65614#1611421, @reames wrote:

In D65614#1611255, @lebedev.ri wrote:

I'm seeing many regressions in diffs.

Can you point to a specific example of what you mean? I haven't studied every single one closely, but on a skim, I am not seeing regressions, so I'm curious what you mean?

Hm? There's clearly a lot of cases where instruction count increases.

Honestly i'd say this is the wrong fix/direction,
i don't recall any such thing as register pressure
for middle-end IR, there are no registers here, only value.

Right, but for the same reason, why should we be perturbing the input without reason? We don't have any information about profitability to justify the transform.

This is a canonicalization pass. The same reasoning could be applied to InstCombine.

test/Transforms/Reassociate/basictest.ll

39–40

66–67

93–94

115–123

!

301

test/Transforms/Reassociate/fast-basictest.ll

89–90

116–117

143–144

test/Transforms/Reassociate/no-op.ll

31–35

Hm, interesting.
I guess this is the first improvement i'm seeing.

[spatel]

I like the idea of limiting this pass. It annoys me that -reassociate can pseudo-randomly change the order of associative+commutative operands, and those transforms don't play by instcombine's operand complexity canonicalization rules (see getComplexity() in InstCombine). In other words, this pass can (hopefully only benignly) fight with instcombine.

But I agree with Roman's analysis of the test diffs - we need to preserve the cases where reassociation/factorization eliminates instructions. InstCombine doesn't handle that generally, and we don't want to shift that burden to InstCombine because that pass is already expensive.

[lebedev.ri]

In D65614#1612409, @spatel wrote:

I like the idea of limiting this pass. It annoys me that -reassociate can pseudo-randomly change the order of associative+commutative operands, and those transforms don't play by instcombine's operand complexity canonicalization rules (see getComplexity() in InstCombine). In other words, this pass can (hopefully only benignly) fight with instcombine.

I'm indeed not opposed to preventing this pass from doing NOP work, but still,
i don't think the reasoning/patch description should say anything about linearization/register pressure.
If that is a problem, then you will have the exact same problem if you start with such bad IR before this transform.

In other words, while you can put a band-aid on it by "arbitrarily crippling" passes,
it may only stop degradation of IR, but nothing will be improving the already-bad IR.
So i'd guess this really should be solved more head-on.

But I agree with Roman's analysis of the test diffs - we need to preserve the cases where reassociation/factorization eliminates instructions. InstCombine doesn't handle that generally, and we don't want to shift that burden to InstCombine because that pass is already expensive.

[reames]

In D65614#1611681, @lebedev.ri wrote:

In D65614#1611421, @reames wrote:

In D65614#1611255, @lebedev.ri wrote:

I'm seeing many regressions in diffs.

Can you point to a specific example of what you mean? I haven't studied every single one closely, but on a skim, I am not seeing regressions, so I'm curious what you mean?

Hm? There's clearly a lot of cases where instruction count increases.

Gah, you're right, my sample was bogus. What I get for skimming from the bottom of a large diff, not the top.

The issue appears to be that GVN is relying on a canonical order of operands to be able to do CSE. I'll think about that one a bit, see if I can come up with a good robust solution.

[reames]

POC fix for the CSE pointed out in review. This isn't a "real" patch yet, more of a hint as to a possible direction. I'm fairly sure we *could* make this sufficiently fast if we want to move in this direction by memoizing expression trees.

I'm more interested in feedback on the approach. I have to admit I hadn't realized the CSE impact when first proposing this. Even with a GVN fix, this will still harm local CSE (in various passes) and EarlyCSE. Is that too high an impact?

[reames]

Missed a condition in the POC

[reames]

Marking as "Plan Changes" to cleanup phab views.

[mgrang]

lib/Transforms/Scalar/GVN.cpp

293 ↗

(On Diff #213087)

Please use range based llvm::sort instead of std::sort. See https://llvm.org/docs/CodingStandards.html#beware-of-non-deterministic-sorting-order-of-equal-elements

[reames]

Abandoning an old review I'm not going to return to any time soon.

lib/Transforms/Scalar/Reassociate.cpp

 ///   (Ops[1].first op Ops[1].first op ... Ops[1].first)  <- Ops[1].second times
 /// op
 ///   ...
 /// op
 ///   (Ops[N].first op Ops[N].first op ... Ops[N].first)  <- Ops[N].second times
 ///
 /// Note that the values Ops[0].first, ..., Ops[N].first are all distinct.
 ///
-/// This routine may modify the function, in which case it returns 'true'.  The
-/// changes it makes may well be destructive, changing the value computed by 'I'
-/// to something completely different.  Thus if the routine returns 'true' then
-/// you MUST either replace I with a new expression computed from the Ops array,
-/// or use RewriteExprTree to put the values back in.
+/// This routine may modify the function, in which case it returns 'true'.  It
+/// does this to increase oppurtunities for reassociation.
 ///
 /// A leaf node is either not a binary operation of the same kind as the root
 /// node 'I' (i.e. is not a binary operator at all, or is, but with a different
 /// opcode), or is the same kind of binary operator but has a use which either
 /// does not belong to the expression, or does belong to the expression but is
 /// a leaf node.  Every leaf node has at least one use that is a non-leaf node
 /// of the expression, while for non-leaf nodes (except for the root 'I') every
 /// use is a non-leaf node of the expression.

 /// The leaf nodes are C, E, F and G.  The Ops array will contain (maybe not in
 /// that order) (C, 1), (E, 1), (F, 2), (G, 2).
 ///
 /// The expression is maximal: if some instruction is a binary operator of the
 /// same kind as 'I', and all of its uses are non-leaf nodes of the expression,
 /// then the instruction also belongs to the expression, is not a leaf node of
 /// it, and its operands also belong to the expression (but may be leaf nodes).
 ///
-/// NOTE: This routine will set operands of non-leaf non-root nodes to undef in
-/// order to ensure that every non-root node in the expression has *exactly one*
-/// use by a non-leaf node of the expression.  This destruction means that the
-/// caller MUST either replace 'I' with a new expression or use something like
-/// RewriteExprTree to put the values back in if the routine indicates that it
-/// made a change by returning 'true'.
-///
-/// In the above example either the right operand of A or the left operand of B
-/// will be replaced by undef.  If it is B's operand then this gives:
-///
-///                     +        |        I
-///                    / \       |
-///                   +   +      |      A,  B - operand of B replaced with undef
-///                  / \   \     |
-///                 *   +   *    |    C,  D,  E
-///                / \ / \ / \   |
-///                   +   *      |      F,  G
-///
-/// Note that such undef operands can only be reached by passing through 'I'.
-/// For example, if you visit operands recursively starting from a leaf node
-/// then you will never see such an undef operand unless you get back to 'I',
-/// which requires passing through a phi node.
-///
 /// Note that this routine may also mutate binary operators of the wrong type
 /// that have all uses inside the expression (i.e. only used by non-leaf nodes
 /// of the expression) if it can turn them into binary operators of the right
 /// type and thus make the expression bigger.
 static bool LinearizeExprTree(Instruction *I,
                               SmallVectorImpl<RepeatedValue> &Ops) {
   assert((isa<UnaryOperator>(I) || isa<BinaryOperator>(I)) &&
          "Expected a UnaryOperator or BinaryOperator!");
for (unsigned OpIdx = 0; OpIdx < I->getNumOperands(); ++OpIdx) { // Visit operands.
       } else {
         // Already in the leaf map.
         assert(It != Leaves.end() && Visited.count(Op) &&
                "In leaf map but not visited!");
 
         // Update the number of paths to the leaf.
         IncorporateWeight(It->second, Weight, Opcode);
 
-#if 0   // TODO: Re-enable once PR13021 is fixed.
-        // The leaf already has one use from inside the expression.  As we want
-        // exactly one such use, drop this new use of the leaf.
-        assert(!Op->hasOneUse() && "Only one use, but we got here twice!");
-        I->setOperand(OpIdx, UndefValue::get(I->getType()));
-        Changed = true;
-
-        // If the leaf is a binary operation of the right kind and we now see
-        // that its multiple original uses were in fact all by nodes belonging
-        // to the expression, then no longer consider it to be a leaf and add
-        // its operands to the expression.
-        if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
-          LLVM_DEBUG(dbgs() << "UNLEAF: " << *Op << " (" << It->second << ")\n");
-          Worklist.push_back(std::make_pair(BO, It->second));
-          Leaves.erase(It);
-          continue;
-        }
-#endif
-
         // If we still have uses that are not accounted for by the expression
         // then it is not safe to modify the value.
         if (!Op->hasOneUse())
           continue;
 
         // No uses outside the expression, try morphing it.
         Weight = It->second;
         Leaves.erase(It); // Since the value may be morphed below.

 }
 
 /// Now that the operands for this expression tree are
 /// linearized and optimized, emit them in-order.
 void ReassociatePass::RewriteExprTree(BinaryOperator *I,
                                       SmallVectorImpl<ValueEntry> &Ops) {
   assert(Ops.size() > 1 && "Single values should be used directly!");
 
+  // Check to see if we've actually made a meaningful change to the
+  // computation.  We don't want to perturb the *schedule* of the computation
+  // by linearizing it if we haven't actually been able to improve the
+  // computation itself.  TODO: At some point, finding a way to do an ILP vs
+  // RegPressure aware scheduler for when we *have* changed the expression
+  // would really help.
+  auto HaveUnchangedOperands = [&]() {
+    SmallPtrSet<Value*, 16> Leafs;
+    for (auto &Op : Ops)
+      // TODO: handle duplicates
+      if (!Leafs.insert(Op.Op).second)
+        return false;
+    
+    unsigned Opcode = I->getOpcode();
+    SmallVector<BinaryOperator*, 8> Worklist;
+    Worklist.push_back(I);
+    while(!Worklist.empty()) {
+      BinaryOperator *Op = Worklist.pop_back_val();
+      Value *LHS = Op->getOperand(0);
+      Value *RHS = Op->getOperand(1);
+      if (Leafs.count(LHS))
+        Leafs.erase(LHS);
+      else if (auto *LHSBO = isReassociableOp(LHS, Opcode))
+        Worklist.push_back(LHSBO);
+      else
+        // Unrecognized leaf
+        return false;
+
+      if (Leafs.count(RHS))
+        Leafs.erase(RHS);
+      else if (auto *RHSBO = isReassociableOp(RHS, Opcode))
+        Worklist.push_back(RHSBO);
+      else
+        // unrecognized leaf
+        return false;
+    }
+    // If we didn't find any of our leaves, we've modified the original.
+    return Leafs.empty();
+  };
+  if (HaveUnchangedOperands())
+    return;
+
   // Since our optimizations should never increase the number of operations, the
   // new expression can usually be written reusing the existing binary operators
   // from the original expression tree, without creating any new instructions,
   // though the rewritten expression may have a completely different topology.
   // We take care to not change anything if the new expression will be the same
   // as the original.  If more than trivial changes (like commuting operands)
   // were made then we are obliged to clear out any optional subclass data like
   // nsw flags.

test/Transforms/Reassociate/2002-05-15-MissedTree.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -instcombine -S | FileCheck %s
 
 define i32 @test1(i32 %A, i32 %B) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %W = add i32 %B, -5
   %Y = add i32 %A, 5
   %Z = add i32 %W, %Y
   ret i32 %Z
 }

test/Transforms/Reassociate/2002-05-15-SubReassociate.ll

;
   %Y = sub i32 %X, %W
   %Z = add i32 %Y, 12
   ret i32 %Z
 }
 
 ; With sub reassociation, constant folding can eliminate the two 12 constants.
 define i32 @test2(i32 %A, i32 %B, i32 %C, i32 %D) {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[TMP1]], [[C:%.*]]
 ; CHECK-NEXT:    [[Q:%.*]] = sub i32 [[D:%.*]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[Q]]
 ;
   %M = add i32 %A, 12
   %N = add i32 %M, %B
   %O = add i32 %N, %C
   %P = sub i32 %D, %O
   %Q = add i32 %P, 12
   ret i32 %Q
 }
 

test/Transforms/Reassociate/basictest.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -gvn -instcombine -S | FileCheck %s
 ; RUN: opt < %s -passes='reassociate,gvn,instcombine' -S | FileCheck %s
 
 define i32 @test1(i32 %arg) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[ARG_NEG:%.*]] = sub i32 0, [[ARG:%.*]]
 ; CHECK-NEXT:    ret i32 [[ARG_NEG]]
 ;
   %tmp1 = sub i32 -12, %arg
   %tmp2 = add i32 %tmp1, 12
   ret i32 %tmp2
 }
 
 define i32 @test2(i32 %reg109, i32 %reg1111) {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[REG117:%.*]] = add i32 [[REG1111:%.*]], [[REG109:%.*]]
+; CHECK-NEXT:    [[REG117:%.*]] = add i32 [[REG109:%.*]], [[REG1111:%.*]]
 ; CHECK-NEXT:    ret i32 [[REG117]]
 ;
   %reg115 = add i32 %reg109, -30
   %reg116 = add i32 %reg115, %reg1111
   %reg117 = add i32 %reg116, 30
   ret i32 %reg117
 }
 
 @e = external global i32
 @a = external global i32
 @b = external global i32
 @c = external global i32
 @f = external global i32
 
 define void @test3() {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[A:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[B:%.*]] = load i32, i32* @b, align 4
 ; CHECK-NEXT:    [[C:%.*]] = load i32, i32* @c, align 4
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[B]], [[A]]
+; CHECK-NEXT:    [[T1:%.*]] = add i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], [[C]]
+; CHECK-NEXT:    [[T3:%.*]] = add i32 [[A]], [[C]]
+; CHECK-NEXT:    [[T4:%.*]] = add i32 [[B]], [[T3]]
 ; CHECK-NEXT:    store i32 [[T2]], i32* @e, align 4
-; CHECK-NEXT:    store i32 [[T2]], i32* @f, align 4
+; CHECK-NEXT:    store i32 [[T4]], i32* @f, align 4
 ; CHECK-NEXT:    ret void
 ;
   %A = load i32, i32* @a
   %B = load i32, i32* @b
   %C = load i32, i32* @c
   %t1 = add i32 %A, %B
   %t2 = add i32 %t1, %C
   %t3 = add i32 %C, %A
   %t4 = add i32 %t3, %B
   ; e = (a+b)+c;
   store i32 %t2, i32* @e
   ; f = (a+c)+b
   store i32 %t4, i32* @f
   ret void
 }
 
 define void @test4() {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    [[A:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[B:%.*]] = load i32, i32* @b, align 4
 ; CHECK-NEXT:    [[C:%.*]] = load i32, i32* @c, align 4
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[B]], [[A]]
+; CHECK-NEXT:    [[T1:%.*]] = add i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], [[C]]
+; CHECK-NEXT:    [[T3:%.*]] = add i32 [[A]], [[C]]
+; CHECK-NEXT:    [[T4:%.*]] = add i32 [[B]], [[T3]]
 ; CHECK-NEXT:    store i32 [[T2]], i32* @e, align 4
-; CHECK-NEXT:    store i32 [[T2]], i32* @f, align 4
+; CHECK-NEXT:    store i32 [[T4]], i32* @f, align 4
 ; CHECK-NEXT:    ret void
 ;
   %A = load i32, i32* @a
   %B = load i32, i32* @b
   %C = load i32, i32* @c
   %t1 = add i32 %A, %B
   %t2 = add i32 %t1, %C
   %t3 = add i32 %C, %A
   %t4 = add i32 %t3, %B
   ; e = c+(a+b)
   store i32 %t2, i32* @e
   ; f = (c+a)+b
   store i32 %t4, i32* @f
   ret void
 }
 
 define void @test5() {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[A:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[B:%.*]] = load i32, i32* @b, align 4
 ; CHECK-NEXT:    [[C:%.*]] = load i32, i32* @c, align 4
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[B]], [[A]]
+; CHECK-NEXT:    [[T1:%.*]] = add i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], [[C]]
+; CHECK-NEXT:    [[T3:%.*]] = add i32 [[A]], [[C]]
+; CHECK-NEXT:    [[T4:%.*]] = add i32 [[B]], [[T3]]
 ; CHECK-NEXT:    store i32 [[T2]], i32* @e, align 4
-; CHECK-NEXT:    store i32 [[T2]], i32* @f, align 4
+; CHECK-NEXT:    store i32 [[T4]], i32* @f, align 4
 ; CHECK-NEXT:    ret void
 ;
   %A = load i32, i32* @a
   %B = load i32, i32* @b
   %C = load i32, i32* @c
   %t1 = add i32 %B, %A
   %t2 = add i32 %t1, %C
   %t3 = add i32 %C, %A
   %t4 = add i32 %t3, %B
   ; e = c+(b+a)
   store i32 %t2, i32* @e
   ; f = (c+a)+b
   store i32 %t4, i32* @f
   ret void
 }
 
 define i32 @test6() {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    ret i32 0
+; CHECK-NEXT:    [[TMP_0:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP_1:%.*]] = load i32, i32* @b, align 4
+; CHECK-NEXT:    [[TMP_2:%.*]] = add i32 [[TMP_0]], [[TMP_1]]
+; CHECK-NEXT:    [[TMP_4:%.*]] = load i32, i32* @c, align 4
+; CHECK-NEXT:    [[TMP_5:%.*]] = add i32 [[TMP_2]], [[TMP_4]]
+; CHECK-NEXT:    [[TMP_8:%.*]] = add i32 [[TMP_0]], [[TMP_4]]
+; CHECK-NEXT:    [[TMP_11:%.*]] = add i32 [[TMP_1]], [[TMP_8]]
+; CHECK-NEXT:    [[RV:%.*]] = xor i32 [[TMP_5]], [[TMP_11]]
+; CHECK-NEXT:    ret i32 [[RV]]
 ;
   %tmp.0 = load i32, i32* @a
   %tmp.1 = load i32, i32* @b
   ; (a+b)
   %tmp.2 = add i32 %tmp.0, %tmp.1
   %tmp.4 = load i32, i32* @c
   ; (a+b)+c
   %tmp.5 = add i32 %tmp.2, %tmp.4
   ; (a+c)
   %tmp.8 = add i32 %tmp.0, %tmp.4
   ; (a+c)+b
   %tmp.11 = add i32 %tmp.8, %tmp.1
   ; X ^ X = 0
   %RV = xor i32 %tmp.5, %tmp.11
   ret i32 %RV
 }
 
 ; This should be one add and two multiplies.
 ; A*A*B + A*C*A
 
 define i32 @test7(i32 %A, i32 %B, i32 %C) {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i32 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL2:%.*]] = mul i32 [[A:%.*]], [[A]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = mul i32 [[REASS_MUL2]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret i32 [[REASS_MUL]]
 ;
   %aa = mul i32 %A, %A
   %aab = mul i32 %aa, %B
   %ac = mul i32 %A, %C
   %aac = mul i32 %ac, %A
   %r = add i32 %aab, %aac
   ret i32 %r
 }
 
 define i32 @test8(i32 %X, i32 %Y, i32 %Z) {
 ; CHECK-LABEL: @test8(
-; CHECK-NEXT:    [[A:%.*]] = mul i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = sub i32 [[Z:%.*]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = sub i32 [[Z:%.*]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = sub i32 0, %X
   %B = mul i32 %A, %Y
   ; (-X)*Y + Z -> Z-X*Y
   %C = add i32 %B, %Z
   ret i32 %C
 }
if.then:
   ret i64 %add2
 
 if.end:
   ret i64 0
 }
 
 define i32 @test17(i32 %X1, i32 %X2, i32 %X3, i32 %X4) {
 ; CHECK-LABEL: @test17(
-; CHECK-NEXT:    [[A:%.*]] = mul i32 [[X4:%.*]], [[X3:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = mul i32 [[A]], [[X1:%.*]]
-; CHECK-NEXT:    [[D:%.*]] = mul i32 [[A]], [[X2:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = mul i32 [[X1:%.*]], [[X3:%.*]]
+; CHECK-NEXT:    [[B:%.*]] = mul i32 [[X2:%.*]], [[X3]]
+; CHECK-NEXT:    [[C:%.*]] = mul i32 [[A]], [[X4:%.*]]
+; CHECK-NEXT:    [[D:%.*]] = mul i32 [[B]], [[X4]]
 ; CHECK-NEXT:    [[E:%.*]] = xor i32 [[C]], [[D]]
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %A = mul i32 %X3, %X1
   %B = mul i32 %X3, %X2
   %C = mul i32 %A, %X4
   %D = mul i32 %B, %X4
   %E = xor i32 %C, %D
   ret i32 %E
 }
 

test/Transforms/Reassociate/canonicalize-neg-const.ll

 ;   (%pow2*-5.0 + %sub) -> (%sub - %pow2*5.0)
 ; as we would later break up this subtract causing a cycle.
 
 define double @pr34078(double %A) {
 ; CHECK-LABEL: @pr34078(
 ; CHECK-NEXT:    [[SUB:%.*]] = fsub fast double 1.000000e+00, [[A:%.*]]
 ; CHECK-NEXT:    [[POW2:%.*]] = fmul double [[A]], [[A]]
 ; CHECK-NEXT:    [[MUL5_NEG:%.*]] = fmul fast double [[POW2]], -5.000000e-01
-; CHECK-NEXT:    [[SUB1:%.*]] = fadd fast double [[MUL5_NEG]], [[SUB]]
+; CHECK-NEXT:    [[SUB1:%.*]] = fadd fast double [[SUB]], [[MUL5_NEG]]
 ; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast double [[SUB1]], 2.000000e+00
 ; CHECK-NEXT:    ret double [[FACTOR]]
 ;
   %sub = fsub fast double 1.000000e+00, %A
   %pow2 = fmul double %A, %A
   %mul5 = fmul fast double %pow2, 5.000000e-01
   %sub1 = fsub fast double %sub, %mul5
   %add = fadd fast double %sub1, %sub1
   ret double %add
 }

test/Transforms/Reassociate/commute.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -reassociate -S < %s | FileCheck %s
 
 declare void @use(i32)
 
 define void @test1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    call void @use(i32 [[TMP1]])
 ; CHECK-NEXT:    call void @use(i32 [[TMP3]])
 ; CHECK-NEXT:    ret void
 ;
 
   %1 = mul i32 %x, %y
   %2 = mul i32 %y, %x
   %3 = sub i32 %1, %2
   call void @use(i32 %1)
   call void @use(i32 %3)
   ret void
 }

test/Transforms/Reassociate/factorize-again.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -reassociate < %s | FileCheck %s
 
 define void @main(float, float) {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  wrapper_entry:
 ; CHECK-NEXT:    [[TMP2:%.*]] = fsub float undef, [[TMP0:%.*]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = fsub float undef, [[TMP1:%.*]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = call float @llvm.rsqrt.f32(float undef)
-; CHECK-NEXT:    [[REASS_ADD2:%.*]] = fadd fast float [[TMP3]], [[TMP2]]
-; CHECK-NEXT:    [[REASS_MUL3:%.*]] = fmul fast float [[TMP4]], [[REASS_ADD2]]
+; CHECK-NEXT:    [[REASS_ADD2:%.*]] = fadd fast float [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[REASS_MUL3:%.*]] = fmul fast float [[REASS_ADD2]], [[TMP4]]
 ; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast float [[REASS_MUL3]], [[TMP4]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[REASS_ADD1]], undef
 ; CHECK-NEXT:    [[TMP5:%.*]] = call float @foo2(float [[REASS_MUL]], float 0.000000e+00)
 ; CHECK-NEXT:    [[MUL36:%.*]] = fmul fast float [[TMP5]], 1.500000e+00
 ; CHECK-NEXT:    call void @foo1(i32 4, float [[MUL36]])
 ; CHECK-NEXT:    ret void
 ;
 wrapper_entry:

test/Transforms/Reassociate/fast-ReassociateVector.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 
 ; Check that a*c+b*c is turned into (a+b)*c
 
 define <4 x float> @test1(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[REASS_ADD:%.*]] = fadd fast <4 x float> [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = fadd fast <4 x float> [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast <4 x float> [[REASS_ADD]], [[C:%.*]]
 ; CHECK-NEXT:    ret <4 x float> [[REASS_MUL]]
 ;
   %mul = fmul fast <4 x float> %a, %c
   %mul1 = fmul fast <4 x float> %b, %c
   %add = fadd fast <4 x float> %mul, %mul1
   ret <4 x float> %add
 }
;
   %add = fadd reassoc <4 x float> %mul, %mul1
   ret <4 x float> %add
 }
 
 ; Check that a*a*b+a*a*c is turned into a*(a*(b+c)).
 
 define <2 x float> @test2(<2 x float> %a, <2 x float> %b, <2 x float> %c) {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast <2 x float> [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast <2 x float> [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL2:%.*]] = fmul fast <2 x float> [[A:%.*]], [[A]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast <2 x float> [[REASS_MUL2]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret <2 x float> [[REASS_MUL]]
 ;
   %t0 = fmul fast <2 x float> %a, %b
   %t1 = fmul fast <2 x float> %a, %t0
   %t2 = fmul fast <2 x float> %a, %c
   %t3 = fmul fast <2 x float> %a, %t2
;
   %t4 = fadd reassoc <2 x float> %t1, %t3
   ret <2 x float> %t4
 }
 
 ; Check that a*b+a*c+d is turned into a*(b+c)+d.
 
 define <2 x double> @test3(<2 x double> %a, <2 x double> %b, <2 x double> %c, <2 x double> %d) {
 ; CHECK-LABEL: @test3(
-; CHECK-NEXT:    [[REASS_ADD:%.*]] = fadd fast <2 x double> [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast <2 x double> [[REASS_ADD]], [[A:%.*]]
-; CHECK-NEXT:    [[T3:%.*]] = fadd fast <2 x double> [[REASS_MUL]], [[D:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = fadd fast <2 x double> [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast <2 x double> [[A:%.*]], [[REASS_ADD]]
+; CHECK-NEXT:    [[T3:%.*]] = fadd fast <2 x double> [[D:%.*]], [[REASS_MUL]]
 ; CHECK-NEXT:    ret <2 x double> [[T3]]
 ;
   %t0 = fmul fast <2 x double> %a, %b
   %t1 = fmul fast <2 x double> %a, %c
   %t2 = fadd fast <2 x double> %t1, %d
   %t3 = fadd fast <2 x double> %t0, %t2
   ret <2 x double> %t3
 }
;
   %f = fneg reassoc <2 x float> %e
   ret <2 x float> %f
 }
 
 ; Check x*y+y*x -> x*y*2.
 
 define <2 x double> @test11(<2 x double> %x, <2 x double> %y) {
 ; CHECK-LABEL: @test11(
-; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast <2 x double> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast <2 x double> [[FACTOR]], <double 2.000000e+00, double 2.000000e+00>
+; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast <2 x double> [[X:%.*]], <double 2.000000e+00, double 2.000000e+00>
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast <2 x double> [[FACTOR]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x double> [[REASS_MUL]]
 ;
   %1 = fmul fast <2 x double> %x, %y
   %2 = fmul fast <2 x double> %y, %x
   %3 = fadd fast <2 x double> %1, %2
   ret <2 x double> %3
 }
 
;
   %3 = fadd reassoc <2 x double> %1, %2
   ret <2 x double> %3
 }
 
 ; FIXME: shifts should be converted to mul to assist further reassociation.
 
 define <2 x i64> @test12(<2 x i64> %b, <2 x i64> %c) {
 ; CHECK-LABEL: @test12(
-; CHECK-NEXT:    [[MUL:%.*]] = mul <2 x i64> [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul <2 x i64> [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i64> [[MUL]], <i64 5, i64 5>
 ; CHECK-NEXT:    ret <2 x i64> [[SHL]]
 ;
   %mul = mul <2 x i64> %c, %b
   %shl = shl <2 x i64> %mul, <i64 5, i64 5>
   ret <2 x i64> %shl
 }
 
 ; FIXME: expressions with a negative const should be canonicalized to assist
 ; further reassociation.
 ; We would expect (-5*b)+a -> a-(5*b) but only the constant operand is commuted.
 
 define <4 x float> @test13(<4 x float> %a, <4 x float> %b) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul fast <4 x float> [[B:%.*]], <float -5.000000e+00, float -5.000000e+00, float -5.000000e+00, float -5.000000e+00>
-; CHECK-NEXT:    [[ADD:%.*]] = fadd fast <4 x float> [[MUL]], [[A:%.*]]
+; CHECK-NEXT:    [[ADD:%.*]] = fadd fast <4 x float> [[A:%.*]], [[MUL]]
 ; CHECK-NEXT:    ret <4 x float> [[ADD]]
 ;
   %mul = fmul fast <4 x float> <float -5.000000e+00, float -5.000000e+00, float -5.000000e+00, float -5.000000e+00>, %b
   %add = fadd fast <4 x float> %mul, %a
   ret <4 x float> %add
 }
 
 ; Break up subtract to assist further reassociation.
 ; Check a+b-c -> a+b+-c.
 
 define <2 x i64> @test14(<2 x i64> %a, <2 x i64> %b, <2 x i64> %c) {
 ; CHECK-LABEL: @test14(
-; CHECK-NEXT:    [[ADD:%.*]] = add <2 x i64> [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[ADD:%.*]] = add <2 x i64> [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[C_NEG:%.*]] = sub <2 x i64> zeroinitializer, [[C:%.*]]
 ; CHECK-NEXT:    [[SUB:%.*]] = add <2 x i64> [[ADD]], [[C_NEG]]
 ; CHECK-NEXT:    ret <2 x i64> [[SUB]]
 ;
   %add = add <2 x i64> %b, %a
   %sub = sub <2 x i64> %add, %c
   ret <2 x i64> %sub
 }
 
 define <2 x i32> @test15(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @test15(
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %tmp1 = and <2 x i32> %x, %y
   %tmp2 = and <2 x i32> %y, %x
   %tmp3 = and <2 x i32> %tmp1, %tmp2
   ret <2 x i32> %tmp3
 }
 
 define <2 x i32> @test16(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @test16(
-; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %tmp1 = or <2 x i32> %x, %y
   %tmp2 = or <2 x i32> %y, %x
   %tmp3 = or <2 x i32> %tmp1, %tmp2
   ret <2 x i32> %tmp3
 }
 
 define <2 x i32> @test17(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @test17(
 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %tmp1 = xor <2 x i32> %x, %y
   %tmp2 = xor <2 x i32> %y, %x
   %tmp3 = xor <2 x i32> %tmp1, %tmp2
   ret <2 x i32> %tmp3
 }
 
 define <2 x i32> @test18(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @test18(
-; CHECK-NEXT:    [[TMP5:%.*]] = xor <2 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = xor <2 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP5]]
 ;
   %tmp1 = xor <2 x i32> %x, %y
   %tmp2 = xor <2 x i32> %y, %x
   %tmp3 = xor <2 x i32> %x, %y
   %tmp4 = xor <2 x i32> %tmp1, %tmp2
   %tmp5 = xor <2 x i32> %tmp4, %tmp3
   ret <2 x i32> %tmp5
 }

test/Transforms/Reassociate/fast-SubReassociate.ll

 
 define float @test4(float %A, float %B, float %C, float %D) {
 ; FIXME: InstCombine should be able to get us to the following:
 ; %sum = fadd fast float %B, %A
 ; %sum1 = fadd fast float %sum, %C
 ; %Q = fsub fast float %D, %sum1
 ; ret i32 %Q
 ; CHECK-LABEL: @test4(
-; CHECK-NEXT:    [[B_NEG:%.*]] = fsub fast float -0.000000e+00, [[B:%.*]]
-; CHECK-NEXT:    [[O_NEG:%.*]] = fsub fast float [[B_NEG]], [[A:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = fsub fast float -0.000000e+00, [[A:%.*]]
+; CHECK-NEXT:    [[O_NEG:%.*]] = fsub fast float [[A_NEG]], [[B:%.*]]
 ; CHECK-NEXT:    [[P:%.*]] = fsub fast float [[O_NEG]], [[C:%.*]]
 ; CHECK-NEXT:    [[Q:%.*]] = fadd fast float [[P]], [[D:%.*]]
 ; CHECK-NEXT:    ret float [[Q]]
 ;
   %M = fadd fast float 1.200000e+01, %A
   %N = fadd fast float %M, %B
   %O = fadd fast float %N, %C
   %P = fsub fast float %D, %O

test/Transforms/Reassociate/fast-basictest.ll

 @fc = external global float
 @ff = external global float
 
 define void @test4() {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    [[A:%.*]] = load float, float* @fa, align 4
 ; CHECK-NEXT:    [[B:%.*]] = load float, float* @fb, align 4
 ; CHECK-NEXT:    [[C:%.*]] = load float, float* @fc, align 4
-; CHECK-NEXT:    [[T1:%.*]] = fadd fast float [[B]], [[A]]
+; CHECK-NEXT:    [[T1:%.*]] = fadd fast float [[A]], [[B]]
 ; CHECK-NEXT:    [[T2:%.*]] = fadd fast float [[T1]], [[C]]
+; CHECK-NEXT:    [[T3:%.*]] = fadd fast float [[A]], [[C]]
+; CHECK-NEXT:    [[T4:%.*]] = fadd fast float [[B]], [[T3]]
 ; CHECK-NEXT:    store float [[T2]], float* @fe, align 4
-; CHECK-NEXT:    store float [[T2]], float* @ff, align 4
+; CHECK-NEXT:    store float [[T4]], float* @ff, align 4
 ; CHECK-NEXT:    ret void
 ;
   %A = load float, float* @fa
   %B = load float, float* @fb
   %C = load float, float* @fc
   %t1 = fadd fast float %A, %B
   %t2 = fadd fast float %t1, %C
   %t3 = fadd fast float %C, %A
   %t4 = fadd fast float %t3, %B
   ; e = (a+b)+c;
   store float %t2, float* @fe
   ; f = (a+c)+b
   store float %t4, float* @ff
   ret void
 }
 
 define void @test5() {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[A:%.*]] = load float, float* @fa, align 4
 ; CHECK-NEXT:    [[B:%.*]] = load float, float* @fb, align 4
 ; CHECK-NEXT:    [[C:%.*]] = load float, float* @fc, align 4
-; CHECK-NEXT:    [[T1:%.*]] = fadd fast float [[B]], [[A]]
+; CHECK-NEXT:    [[T1:%.*]] = fadd fast float [[A]], [[B]]
 ; CHECK-NEXT:    [[T2:%.*]] = fadd fast float [[T1]], [[C]]
+; CHECK-NEXT:    [[T3:%.*]] = fadd fast float [[A]], [[C]]
+; CHECK-NEXT:    [[T4:%.*]] = fadd fast float [[B]], [[T3]]
 ; CHECK-NEXT:    store float [[T2]], float* @fe, align 4
-; CHECK-NEXT:    store float [[T2]], float* @ff, align 4
+; CHECK-NEXT:    store float [[T4]], float* @ff, align 4
 ; CHECK-NEXT:    ret void
 ;
   %A = load float, float* @fa
   %B = load float, float* @fb
   %C = load float, float* @fc
   %t1 = fadd fast float %A, %B
   %t2 = fadd fast float %t1, %C
   %t3 = fadd fast float %C, %A
   %t4 = fadd fast float %t3, %B
   ; e = c+(a+b)
   store float %t2, float* @fe
   ; f = (c+a)+b
   store float %t4, float* @ff
   ret void
 }
 
 define void @test6() {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[A:%.*]] = load float, float* @fa, align 4
 ; CHECK-NEXT:    [[B:%.*]] = load float, float* @fb, align 4
 ; CHECK-NEXT:    [[C:%.*]] = load float, float* @fc, align 4
-; CHECK-NEXT:    [[T1:%.*]] = fadd fast float [[B]], [[A]]
+; CHECK-NEXT:    [[T1:%.*]] = fadd fast float [[A]], [[B]]
 ; CHECK-NEXT:    [[T2:%.*]] = fadd fast float [[T1]], [[C]]
+; CHECK-NEXT:    [[T3:%.*]] = fadd fast float [[A]], [[C]]
+; CHECK-NEXT:    [[T4:%.*]] = fadd fast float [[B]], [[T3]]
 ; CHECK-NEXT:    store float [[T2]], float* @fe, align 4
-; CHECK-NEXT:    store float [[T2]], float* @ff, align 4
+; CHECK-NEXT:    store float [[T4]], float* @ff, align 4
 ; CHECK-NEXT:    ret void
 ;
   %A = load float, float* @fa
   %B = load float, float* @fb
   %C = load float, float* @fc
   %t1 = fadd fast float %B, %A
   %t2 = fadd fast float %t1, %C
   %t3 = fadd fast float %C, %A
   %t4 = fadd fast float %t3, %B
   ; e = c+(b+a)
   store float %t2, float* @fe
   ; f = (c+a)+b
   store float %t4, float* @ff
   ret void
 }
 
 define float @test7(float %A, float %B, float %C) {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast float [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast float [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL2:%.*]] = fmul fast float [[A:%.*]], [[A]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[REASS_MUL2]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret float [[REASS_MUL]]
 ;
   %aa = fmul fast float %A, %A
   %aab = fmul fast float %aa, %B
   %ac = fmul fast float %A, %C
   %aac = fmul fast float %ac, %A
;
   %r = fadd reassoc float %aab, %aac
   ret float %r
 }
 
 ; (-X)*Y + Z -> Z-X*Y
 
 define float @test8(float %X, float %Y, float %Z) {
 ; CHECK-LABEL: @test8(
-; CHECK-NEXT:    [[A:%.*]] = fmul fast float [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = fsub fast float [[Z:%.*]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = fsub fast float [[Z:%.*]], [[TMP1]]
 ; CHECK-NEXT:    ret float [[C]]
 ;
   %A = fsub fast float 0.0, %X
   %B = fmul fast float %A, %Y
   %C = fadd fast float %B, %Z
   ret float %C
 }
 
;
   %B = fmul fast float %A, %X2   ; -X1*X2
   %C = fmul fast float %X1, %X3  ; X1*X3
   %D = fadd fast float %B, %C    ; -X1*X2 + X1*X3 -> X1*(X3-X2)
   ret float %D
 }
 
 define float @test13_unary_fneg(float %X1, float %X2, float %X3) {
 ; CHECK-LABEL: @test13_unary_fneg(
-; CHECK-NEXT:    [[TMP1:%.*]] = fsub fast float [[X3:%.*]], [[X2:%.*]]
-; CHECK-NEXT:    [[D:%.*]] = fmul fast float [[TMP1]], [[X1:%.*]]
-; CHECK-NEXT:    ret float [[D]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = fsub fast float [[X3:%.*]], [[X2:%.*]]
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[REASS_ADD]], [[X1:%.*]]
+; CHECK-NEXT:    ret float [[REASS_MUL]]
 ;
   %A = fneg fast float %X1
   %B = fmul fast float %A, %X2   ; -X1*X2
   %C = fmul fast float %X1, %X3  ; X1*X3
   %D = fadd fast float %B, %C    ; -X1*X2 + X1*X3 -> X1*(X3-X2)
   ret float %D
 }
 
;
   %e = fmul fast float %c, %d
   %f = fmul fast float %e, 1.234500e+04
   %g = fsub fast float 0.000000e+00, %f
   ret float %g
 }
 
 define float @test17_unary_fneg(float %a, float %b, float %z) {
 ; CHECK-LABEL: @test17_unary_fneg(
-; CHECK-NEXT:    [[D:%.*]] = fmul fast float [[A:%.*]], 1.234500e+04
-; CHECK-NEXT:    [[E:%.*]] = fmul fast float [[D]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast float [[E]], [[Z:%.*]]
-; CHECK-NEXT:    ret float [[TMP1]]
+; CHECK-NEXT:    [[E:%.*]] = fmul fast float [[A:%.*]], 1.234500e+04
+; CHECK-NEXT:    [[F:%.*]] = fmul fast float [[E]], [[B:%.*]]
+; CHECK-NEXT:    [[G:%.*]] = fmul fast float [[F]], [[Z:%.*]]
+; CHECK-NEXT:    ret float [[G]]
 ;
   %c = fneg fast float %z
   %d = fmul fast float %a, %b
   %e = fmul fast float %c, %d
   %f = fmul fast float %e, 1.234500e+04
   %g = fneg fast float %f
   ret float %g
 }

test/Transforms/Reassociate/fast-fp-commute.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -reassociate -S < %s | FileCheck %s
 
 declare void @use(float)
 
 define void @test1(float %x, float %y) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast float [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = fmul fast float [[Y]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = fmul fast float [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = fsub fast float [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    call void @use(float [[TMP1]])
 ; CHECK-NEXT:    call void @use(float [[TMP3]])
 ; CHECK-NEXT:    ret void
 ;
   %1 = fmul fast float %x, %y
   %2 = fmul fast float %y, %x
   %3 = fsub fast float %1, %2
   call void @use(float %1)
   call void @use(float %3)
   ret void
 }
 
 define float @test2(float %x, float %y) {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast float [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = fmul fast float [[Y]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = fmul fast float [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = fsub fast float [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret float [[TMP3]]
 ;
   %1 = fmul fast float %x, %y
   %2 = fmul fast float %y, %x
   %3 = fsub fast float %1, %2
   ret float %3
 }
 
 define float @test3(float %x, float %y) {
 ; CHECK-LABEL: @test3(
-; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast float [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[FACTOR]], 2.000000e+00
+; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast float [[X:%.*]], 2.000000e+00
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[FACTOR]], [[Y:%.*]]
 ; CHECK-NEXT:    ret float [[REASS_MUL]]
 ;
   %1 = fmul fast float %x, %y
   %2 = fmul fast float %y, %x
   %3 = fadd fast float %1, %2
   ret float %3
 }
 

test/Transforms/Reassociate/fast-multistep.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 
 ; Check that a*a*b+a*a*c is turned into a*(a*(b+c)).
 
 define float @fmultistep1(float %a, float %b, float %c) {
 ; CHECK-LABEL: @fmultistep1(
-; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast float [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast float [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL2:%.*]] = fmul fast float [[A:%.*]], [[A]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[REASS_MUL2]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret float [[REASS_MUL]]
 ;
   %t0 = fmul fast float %a, %b
   %t1 = fmul fast float %a, %t0 ; a*(a*b)
   %t2 = fmul fast float %a, %c
   %t3 = fmul fast float %a, %t2 ; a*(a*c)
   %t4 = fadd fast float %t1, %t3
   ret float %t4
 }
 
 ; Check that a*b+a*c+d is turned into a*(b+c)+d.
 
 define float @fmultistep2(float %a, float %b, float %c, float %d) {
 ; CHECK-LABEL: @fmultistep2(
-; CHECK-NEXT:    [[REASS_ADD:%.*]] = fadd fast float [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[REASS_ADD]], [[A:%.*]]
-; CHECK-NEXT:    [[T3:%.*]] = fadd fast float [[REASS_MUL]], [[D:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = fadd fast float [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[A:%.*]], [[REASS_ADD]]
+; CHECK-NEXT:    [[T3:%.*]] = fadd fast float [[D:%.*]], [[REASS_MUL]]
 ; CHECK-NEXT:    ret float [[T3]]
 ;
   %t0 = fmul fast float %a, %b
   %t1 = fmul fast float %a, %c
   %t2 = fadd fast float %t1, %d ; a*c+d
   %t3 = fadd fast float %t0, %t2 ; a*b+(a*c+d)
   ret float %t3
 }
 

test/Transforms/Reassociate/looptest.ll

 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[REG115:%.*]] = phi i32 [ [[REG120:%.*]], [[BB6:%.*]] ], [ 0, [[BB0:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND221]], label [[BB6]], label [[BB3:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[REG116:%.*]] = phi i32 [ [[REG119:%.*]], [[BB5:%.*]] ], [ 0, [[BB2]] ]
 ; CHECK-NEXT:    br i1 [[COND221]], label [[BB5]], label [[BB4:%.*]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[REG117:%.*]] = phi i32 [ [[REG118:%.*]], [[BB4]] ], [ 0, [[BB3]] ]
-; CHECK-NEXT:    [[REG113:%.*]] = add i32 [[REG116]], [[REG115]]
-; CHECK-NEXT:    [[REG114:%.*]] = add i32 [[REG113]], [[REG117]]
+; CHECK-NEXT:    [[REG113:%.*]] = add i32 [[REG115]], [[REG117]]
+; CHECK-NEXT:    [[REG114:%.*]] = add i32 [[REG116]], [[REG113]]
 ; CHECK-NEXT:    [[CAST227:%.*]] = getelementptr [4 x i8], [4 x i8]* @.LC0, i64 0, i64 0
 ; CHECK-NEXT:    [[TMP0:%.*]] = call i32 (i8*, ...) @printf(i8* [[CAST227]], i32 [[REG114]])
 ; CHECK-NEXT:    [[REG118]] = add i32 [[REG117]], 1
 ; CHECK-NEXT:    [[COND224:%.*]] = icmp ne i32 [[REG118]], [[NUM]]
 ; CHECK-NEXT:    br i1 [[COND224]], label [[BB4]], label [[BB5]]
 ; CHECK:       bb5:
 ; CHECK-NEXT:    [[REG119]] = add i32 [[REG116]], 1
 ; CHECK-NEXT:    [[COND225:%.*]] = icmp ne i32 [[REG119]], [[NUM]]

test/Transforms/Reassociate/matching-binops.ll

 ;           260 potential variations of this fold
 ; for integer binops. There are another 40 for FP.
 ; Mix the commutation options to provide coverage using less tests.
 
 define i8 @and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @and_shl(
 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = shl i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = and i8 %sx, %z
   %r = and i8 %sy, %a
   ret i8 %r
 }
 
 define i8 @or_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @or_shl(
 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = shl i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = or i8 %sx, %z
   %r = or i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @xor_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @xor_shl(
 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = xor i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = shl i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = xor i8 %z, %sx
   %r = xor i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @and_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @and_lshr(
 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = lshr i8 %x, %shamt
   %sy = lshr i8 %y, %shamt
   %a = and i8 %z, %sx
   %r = and i8 %sy, %a
   ret i8 %r
 }
 
 define i8 @or_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @or_lshr(
 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = lshr i8 %x, %shamt
   %sy = lshr i8 %y, %shamt
   %a = or i8 %sx, %z
   %r = or i8 %sy, %a
   ret i8 %r
 }
 
 define i8 @xor_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @xor_lshr(
 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = xor i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = lshr i8 %x, %shamt
   %sy = lshr i8 %y, %shamt
   %a = xor i8 %sx, %z
   %r = xor i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @and_ashr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @and_ashr(
 ; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = ashr i8 %x, %shamt
   %sy = ashr i8 %y, %shamt
   %a = and i8 %z, %sx
   %r = and i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @or_ashr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @or_ashr(
 ; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = ashr i8 %x, %shamt
   %sy = ashr i8 %y, %shamt
   %a = or i8 %z, %sx
   %r = or i8 %sy, %a
   ret i8 %r
 }
 
 ; Vectors work too.
 
 define <2 x i8> @xor_ashr(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z, <2 x i8> %shamt) {
 ; CHECK-LABEL: @xor_ashr(
 ; CHECK-NEXT:    [[SX:%.*]] = ashr <2 x i8> [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = ashr <2 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = xor <2 x i8> [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = xor <2 x i8> [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[SY]], [[A]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %sx = ashr <2 x i8> %x, %shamt
   %sy = ashr <2 x i8> %y, %shamt
   %a = xor <2 x i8> %sx, %z
   %r = xor <2 x i8> %a, %sy
   ret <2 x i8> %r
 }
 
 ; Negative test - different logic ops
 
 define i8 @or_and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @or_and_shl(
 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = shl i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = or i8 %sx, %z
   %r = and i8 %sy, %a
   ret i8 %r
 }
 
 ; Negative test - different shift ops
 
 define i8 @or_lshr_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @or_lshr_shl(
 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = lshr i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = or i8 %sx, %z
   %r = or i8 %a, %sy
   ret i8 %r
 }
 
 ; Negative test - multi-use
 
 define i8 @xor_lshr_multiuse(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @xor_lshr_multiuse(
 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = xor i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SY]], [[A]]
 ; CHECK-NEXT:    [[R2:%.*]] = sdiv i8 [[A]], [[R]]
 ; CHECK-NEXT:    ret i8 [[R2]]
 ;
   %sx = lshr i8 %x, %shamt
   %sy = lshr i8 %y, %shamt
   %a = xor i8 %sx, %z
   %r = xor i8 %a, %sy
   %r2 = sdiv i8 %a, %r
   ret i8 %r2
 }
 
 ; Math ops work too. Change instruction positions too to verify placement.
 
 define i8 @add_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @add_lshr(
 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[SX]], [[Z:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = add i8 [[Z:%.*]], [[SX]]
 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = lshr i8 %x, %shamt
   %a = add i8 %sx, %z
   %sy = lshr i8 %y, %shamt
   %r = add i8 %a, %sy
   ret i8 %r
 }
 
 ; Make sure wrapping flags are cleared.
 
 define i8 @mul_sub(i8 %x, i8 %y, i8 %z, i8 %m) {
 ; CHECK-LABEL: @mul_sub(
 ; CHECK-NEXT:    [[SX:%.*]] = sub i8 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = sub i8 [[Y:%.*]], [[M]]
-; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = mul nuw i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw i8 [[SY]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = sub i8 %x, %m
   %sy = sub i8 %y, %m
   %a = mul nsw i8 %sx, %z
   %r = mul nuw i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @add_mul(i8 %x, i8 %y, i8 %z, i8 %m) {
 ; CHECK-LABEL: @add_mul(
 ; CHECK-NEXT:    [[SX:%.*]] = mul nuw i8 [[X:%.*]], 42
-; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[Z:%.*]], [[SX]]
-; CHECK-NEXT:    [[SY:%.*]] = mul nsw i8 [[M:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[SX]], [[Z:%.*]]
+; CHECK-NEXT:    [[SY:%.*]] = mul nsw i8 [[Y:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = add nsw i8 [[A]], [[SY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = mul nuw i8 %x, 42
   %a = add nuw i8 %sx, %z
   %sy = mul nsw i8 %y, %m
   %r = add nsw i8 %sy, %a
   ret i8 %r
 }
 
 ; Floating-point works too if it's not strict.
 ; TODO: These should not require the full 'fast' FMF.
 
 define float @fadd_fmul(float %x, float %y, float %z, float %m) {
 ; CHECK-LABEL: @fadd_fmul(
 ; CHECK-NEXT:    [[SX:%.*]] = fmul float [[X:%.*]], [[M:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = fadd fast float [[SX]], [[Z:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = fadd fast float [[Z:%.*]], [[SX]]
 ; CHECK-NEXT:    [[SY:%.*]] = fmul float [[Y:%.*]], [[M]]
-; CHECK-NEXT:    [[R:%.*]] = fadd fast float [[A]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = fadd fast float [[SY]], [[A]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %sx = fmul float %x, %m
   %a = fadd fast float %sx, %z
   %sy = fmul float %y, %m
   %r = fadd fast float %sy, %a
   ret float %r
 }
 
 define float @fmul_fdiv(float %x, float %y, float %z, float %m) {
 ; CHECK-LABEL: @fmul_fdiv(
 ; CHECK-NEXT:    [[SX:%.*]] = fdiv float [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[SY:%.*]] = fdiv float [[Y:%.*]], 4.200000e+01
-; CHECK-NEXT:    [[A:%.*]] = fmul fast float [[SY]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = fmul fast float [[A]], [[SX]]
+; CHECK-NEXT:    [[A:%.*]] = fmul fast float [[Z:%.*]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = fmul fast float [[SY]], [[A]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %sx = fdiv float %x, %m
   %sy = fdiv float %y, 42.0
   %a = fmul fast float %z, %sx
   %r = fmul fast float %sy, %a
   ret float %r
 }
 
 ; Verify that debug info for modified instructions gets discarded (references become undef).
 
 define i32 @and_shl_dbg(i32 %x, i32 %y, i32 %z, i32 %shamt) {
 ; CHECK-LABEL: @and_shl_dbg(
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[X:%.*]], metadata !7, metadata !DIExpression()), !dbg !20
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[Y:%.*]], metadata !13, metadata !DIExpression()), !dbg !21
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[Z:%.*]], metadata !14, metadata !DIExpression()), !dbg !22
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[SHAMT:%.*]], metadata !15, metadata !DIExpression()), !dbg !23
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X]], [[SHAMT]], !dbg !24
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[SHL]], metadata !16, metadata !DIExpression()), !dbg !25
 ; CHECK-NEXT:    [[SHL1:%.*]] = shl i32 [[Y]], [[SHAMT]], !dbg !26
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[SHL1]], metadata !17, metadata !DIExpression()), !dbg !27
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], [[Z]], !dbg !28
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[Z]], [[SHL]], !dbg !28
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[AND]], metadata !18, metadata !DIExpression()), !dbg !29
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND]], [[SHL1]], !dbg !30
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[SHL1]], [[AND]], !dbg !30
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[AND2]], metadata !19, metadata !DIExpression()), !dbg !31
 ; CHECK-NEXT:    ret i32 [[AND2]], !dbg !32
 ;
   call void @llvm.dbg.value(metadata i32 %x, metadata !13, metadata !DIExpression()), !dbg !21
   call void @llvm.dbg.value(metadata i32 %y, metadata !14, metadata !DIExpression()), !dbg !22
   call void @llvm.dbg.value(metadata i32 %z, metadata !15, metadata !DIExpression()), !dbg !23
   call void @llvm.dbg.value(metadata i32 %shamt, metadata !16, metadata !DIExpression()), !dbg !24
   %shl = shl i32 %x, %shamt, !dbg !25

test/Transforms/Reassociate/mixed-fast-nonfast-fp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -reassociate %s -S | FileCheck %s
 
 define float @foo(float %a,float %b, float %c) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:    [[MUL3:%.*]] = fmul float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast float [[C:%.*]], 2.000000e+00
 ; CHECK-NEXT:    [[REASS_ADD1:%.*]] = fadd fast float [[FACTOR]], [[B]]
-; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[REASS_ADD1]], [[A]]
-; CHECK-NEXT:    [[ADD3:%.*]] = fadd fast float [[REASS_MUL]], [[MUL3]]
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast float [[A]], [[REASS_ADD1]]
+; CHECK-NEXT:    [[ADD3:%.*]] = fadd fast float [[MUL3]], [[REASS_MUL]]
 ; CHECK-NEXT:    ret float [[ADD3]]
 ;
   %mul1 = fmul fast float %a, %c
   %mul2 = fmul fast float %a, %b
   %mul3 = fmul float %a, %b   ; STRICT
   %mul4 = fmul fast float %a, %c
   %add1 = fadd fast  float %mul1, %mul3
   %add2 = fadd fast float %mul4, %mul2
   %add3 = fadd fast float %add1, %add2
   ret float %add3
 }
 
 define float @foo_reassoc(float %a,float %b, float %c) {
 ; CHECK-LABEL: @foo_reassoc(
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul reassoc float [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[MUL2:%.*]] = fmul fast float [[B:%.*]], [[A]]
+; CHECK-NEXT:    [[MUL2:%.*]] = fmul fast float [[A]], [[B:%.*]]
 ; CHECK-NEXT:    [[MUL3:%.*]] = fmul float [[A]], [[B]]
 ; CHECK-NEXT:    [[MUL4:%.*]] = fmul reassoc float [[A]], [[C]]
-; CHECK-NEXT:    [[ADD1:%.*]] = fadd fast float [[MUL1]], [[MUL3]]
+; CHECK-NEXT:    [[ADD1:%.*]] = fadd fast float [[MUL3]], [[MUL1]]
 ; CHECK-NEXT:    [[ADD2:%.*]] = fadd reassoc float [[MUL2]], [[MUL4]]
 ; CHECK-NEXT:    [[ADD3:%.*]] = fadd fast float [[ADD1]], [[ADD2]]
 ; CHECK-NEXT:    ret float [[ADD3]]
 ;
   %mul1 = fmul reassoc float %a, %c
   %mul2 = fmul fast float %a, %b
   %mul3 = fmul float %a, %b   ; STRICT
   %mul4 = fmul reassoc float %a, %c
   %add1 = fadd fast  float %mul1, %mul3
   %add2 = fadd reassoc float %mul4, %mul2
   %add3 = fadd fast float %add1, %add2
   ret float %add3
 }
 

test/Transforms/Reassociate/mulfactor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 
 define i32 @test1(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[T2:%.*]] = mul i32 [[A:%.*]], [[A]]
 ; CHECK-NEXT:    [[T6:%.*]] = mul i32 [[A]], 2
-; CHECK-NEXT:    [[REASS_ADD:%.*]] = add i32 [[T6]], [[B:%.*]]
-; CHECK-NEXT:    [[REASS_MUL:%.*]] = mul i32 [[REASS_ADD]], [[B]]
-; CHECK-NEXT:    [[T11:%.*]] = add i32 [[REASS_MUL]], [[T2]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = add i32 [[B:%.*]], [[T6]]
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = mul i32 [[B]], [[REASS_ADD]]
+; CHECK-NEXT:    [[T11:%.*]] = add i32 [[T2]], [[REASS_MUL]]
 ; CHECK-NEXT:    ret i32 [[T11]]
 ;
   %t2 = mul i32 %a, %a
   %t5 = shl i32 %a, 1
   %t6 = mul i32 %t5, %b
   %t8 = mul i32 %b, %b
   %t7 = add i32 %t6, %t2
   %t11 = add i32 %t7, %t8

test/Transforms/Reassociate/multistep.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 
 ; Check that a*a*b+a*a*c is turned into a*(a*(b+c)).
 
 define i64 @multistep1(i64 %a, i64 %b, i64 %c) {
 ; CHECK-LABEL: @multistep1(
-; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i64 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i64 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL2:%.*]] = mul i64 [[A:%.*]], [[A]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = mul i64 [[REASS_MUL2]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret i64 [[REASS_MUL]]
 ;
   %t0 = mul i64 %a, %b
   %t1 = mul i64 %a, %t0 ; a*(a*b)
   %t2 = mul i64 %a, %c
   %t3 = mul i64 %a, %t2 ; a*(a*c)
   %t4 = add i64 %t1, %t3
   ret i64 %t4
 }
 
 ; Check that a*b+a*c+d is turned into a*(b+c)+d.
 
 define i64 @multistep2(i64 %a, i64 %b, i64 %c, i64 %d) {
 ; CHECK-LABEL: @multistep2(
-; CHECK-NEXT:    [[REASS_ADD:%.*]] = add i64 [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[REASS_MUL:%.*]] = mul i64 [[REASS_ADD]], [[A:%.*]]
-; CHECK-NEXT:    [[T3:%.*]] = add i64 [[REASS_MUL]], [[D:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = add i64 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[REASS_MUL:%.*]] = mul i64 [[A:%.*]], [[REASS_ADD]]
+; CHECK-NEXT:    [[T3:%.*]] = add i64 [[D:%.*]], [[REASS_MUL]]
 ; CHECK-NEXT:    ret i64 [[T3]]
 ;
   %t0 = mul i64 %a, %b
   %t1 = mul i64 %a, %c
   %t2 = add i64 %t1, %d ; a*c+d
   %t3 = add i64 %t0, %t2 ; a*b+(a*c+d)
   ret i64 %t3
 }
 

test/Transforms/Reassociate/no-op.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 
 ; When there is nothing to do, or not much to do, check that reassociate leaves
 ; things alone.
 
 declare void @use(i32)
 
 define void @test1(i32 %a, i32 %b) {
 ; Shouldn't change or move any of the add instructions.  Should commute but
 ; otherwise not change or move any of the mul instructions.
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[A0:%.*]] = add nsw i32 [[A:%.*]], 1
 ; CHECK-NEXT:    [[M0:%.*]] = mul nsw i32 [[A]], 3
 ; CHECK-NEXT:    [[A1:%.*]] = add nsw i32 [[A0]], [[B:%.*]]
-; CHECK-NEXT:    [[M1:%.*]] = mul nsw i32 [[M0]], [[B]]
+; CHECK-NEXT:    [[M1:%.*]] = mul nsw i32 [[B]], [[M0]]
 ; CHECK-NEXT:    call void @use(i32 [[A1]])
 ; CHECK-NEXT:    call void @use(i32 [[M1]])
 ; CHECK-NEXT:    ret void
 ;
   %a0 = add nsw i32 %a, 1
   %m0 = mul nsw i32 3, %a
   %a1 = add nsw i32 %a0, %b
   %m1 = mul nsw i32 %b, %m0
   call void @use(i32 %a1)
   call void @use(i32 %m1)
   ret void
 }
 
 define void @test2(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; The initial add doesn't change so should not lose the nsw flag.
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[A0:%.*]] = add nsw i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[A1:%.*]] = add i32 [[A0]], [[C:%.*]]
-; CHECK-NEXT:    [[A2:%.*]] = add i32 [[A1]], [[D:%.*]]
+; CHECK-NEXT:    [[A0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[A1:%.*]] = add nsw i32 [[A0]], [[D:%.*]]
+; CHECK-NEXT:    [[A2:%.*]] = add nsw i32 [[C:%.*]], [[A1]]
 ; CHECK-NEXT:    call void @use(i32 [[A2]])
 ; CHECK-NEXT:    ret void
 ;
   %a0 = add nsw i32 %b, %a
   %a1 = add nsw i32 %a0, %d
   %a2 = add nsw i32 %a1, %c
   call void @use(i32 %a2)
   ret void
 }

test/Transforms/Reassociate/optional-flags.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -reassociate < %s | FileCheck %s
 ; rdar://8944681
 
 ; Reassociate should clear optional flags like nsw when reassociating.
 
 define i64 @test0(i64 %a, i64 %b, i64 %c) {
 ;
 ; CHECK-LABEL: @test0(
-; CHECK-NEXT:    [[Y:%.*]] = add i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = add i64 [[Y]], [[C:%.*]]
+; CHECK-NEXT:    [[Y:%.*]] = add nsw i64 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = add i64 [[A:%.*]], [[Y]]
 ; CHECK-NEXT:    ret i64 [[Z]]
 ;
   %y = add nsw i64 %c, %b
   %z = add i64 %y, %a
   ret i64 %z
 }
 
 define i64 @test1(i64 %a, i64 %b, i64 %c) {
 ;
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[Y:%.*]] = add i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = add i64 [[Y]], [[C:%.*]]
+; CHECK-NEXT:    [[Y:%.*]] = add i64 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = add nsw i64 [[A:%.*]], [[Y]]
 ; CHECK-NEXT:    ret i64 [[Z]]
 ;
   %y = add i64 %c, %b
   %z = add nsw i64 %y, %a
   ret i64 %z
 }
 
 ; PR9215
 define i32 @test2(i32 %x, i32 %y) {
 ;
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[S:%.*]] = add nsw i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[S:%.*]] = add nsw i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[S]]
 ;
   %s = add nsw i32 %x, %y
   ret i32 %s
 }

test/Transforms/Reassociate/pointer-collision-non-determinism.ll

 
 define float @test(float %arg) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP:%.*]] = fmul fast float [[ARG:%.*]], 0x3FE99999A0000000
 ; CHECK-NEXT:    [[TMP110:%.*]] = fsub fast float 1.000000e+00, [[TMP]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = fmul fast float [[ARG]], 0x3FE99999A0000000
 ; CHECK-NEXT:    [[TMP311:%.*]] = fsub fast float 1.000000e+00, [[TMP2]]
-; CHECK-NEXT:    [[REASS_MUL160:%.*]] = fmul fast float [[TMP110]], [[ARG]]
-; CHECK-NEXT:    [[TMP4:%.*]] = fmul fast float [[REASS_MUL160]], [[TMP311]]
-; CHECK-NEXT:    [[TMP5:%.*]] = fadd fast float [[TMP4]], [[ARG]]
-; CHECK-NEXT:    [[TMP6:%.*]] = fmul fast float [[TMP5]], [[ARG]]
-; CHECK-NEXT:    [[TMP7:%.*]] = fadd fast float [[TMP6]], [[ARG]]
-; CHECK-NEXT:    [[TMP8:%.*]] = fmul fast float [[TMP7]], [[ARG]]
-; CHECK-NEXT:    [[TMP9:%.*]] = fadd fast float [[TMP8]], [[ARG]]
-; CHECK-NEXT:    [[TMP10:%.*]] = fmul fast float [[TMP9]], [[ARG]]
-; CHECK-NEXT:    [[TMP11:%.*]] = fadd fast float [[TMP10]], [[ARG]]
-; CHECK-NEXT:    [[TMP12:%.*]] = fmul fast float [[TMP11]], [[ARG]]
-; CHECK-NEXT:    [[TMP13:%.*]] = fadd fast float [[TMP12]], [[ARG]]
-; CHECK-NEXT:    [[TMP14:%.*]] = fmul fast float [[TMP13]], [[ARG]]
-; CHECK-NEXT:    [[TMP15:%.*]] = fadd fast float [[TMP14]], [[ARG]]
-; CHECK-NEXT:    [[TMP16:%.*]] = fmul fast float [[TMP15]], [[ARG]]
-; CHECK-NEXT:    [[TMP17:%.*]] = fadd fast float [[TMP16]], [[ARG]]
-; CHECK-NEXT:    [[TMP18:%.*]] = fmul fast float [[TMP17]], [[ARG]]
-; CHECK-NEXT:    [[TMP19:%.*]] = fadd fast float [[TMP18]], [[ARG]]
-; CHECK-NEXT:    [[TMP20:%.*]] = fmul fast float [[TMP19]], [[ARG]]
-; CHECK-NEXT:    [[TMP21:%.*]] = fadd fast float [[TMP20]], [[ARG]]
-; CHECK-NEXT:    [[TMP22:%.*]] = fmul fast float [[TMP21]], [[ARG]]
-; CHECK-NEXT:    [[TMP23:%.*]] = fadd fast float [[TMP22]], [[ARG]]
+; CHECK-NEXT:    [[REASS_MUL160:%.*]] = fmul fast float [[ARG]], [[TMP110]]
+; CHECK-NEXT:    [[TMP4:%.*]] = fmul fast float [[TMP311]], [[REASS_MUL160]]
+; CHECK-NEXT:    [[TMP5:%.*]] = fadd fast float [[ARG]], [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = fmul fast float [[ARG]], [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = fadd fast float [[ARG]], [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = fmul fast float [[ARG]], [[TMP7]]
+; CHECK-NEXT:    [[TMP9:%.*]] = fadd fast float [[ARG]], [[TMP8]]
+; CHECK-NEXT:    [[TMP10:%.*]] = fmul fast float [[ARG]], [[TMP9]]
+; CHECK-NEXT:    [[TMP11:%.*]] = fadd fast float [[ARG]], [[TMP10]]
+; CHECK-NEXT:    [[TMP12:%.*]] = fmul fast float [[ARG]], [[TMP11]]
+; CHECK-NEXT:    [[TMP13:%.*]] = fadd fast float [[ARG]], [[TMP12]]
+; CHECK-NEXT:    [[TMP14:%.*]] = fmul fast float [[ARG]], [[TMP13]]
+; CHECK-NEXT:    [[TMP15:%.*]] = fadd fast float [[ARG]], [[TMP14]]
+; CHECK-NEXT:    [[TMP16:%.*]] = fmul fast float [[ARG]], [[TMP15]]
+; CHECK-NEXT:    [[TMP17:%.*]] = fadd fast float [[ARG]], [[TMP16]]
+; CHECK-NEXT:    [[TMP18:%.*]] = fmul fast float [[ARG]], [[TMP17]]
+; CHECK-NEXT:    [[TMP19:%.*]] = fadd fast float [[ARG]], [[TMP18]]
+; CHECK-NEXT:    [[TMP20:%.*]] = fmul fast float [[ARG]], [[TMP19]]
+; CHECK-NEXT:    [[TMP21:%.*]] = fadd fast float [[ARG]], [[TMP20]]
+; CHECK-NEXT:    [[TMP22:%.*]] = fmul fast float [[ARG]], [[TMP21]]
+; CHECK-NEXT:    [[TMP23:%.*]] = fadd fast float [[ARG]], [[TMP22]]
 ; CHECK-NEXT:    [[REASS_MUL166:%.*]] = fmul fast float [[ARG]], [[ARG]]
 ; CHECK-NEXT:    [[TMP24:%.*]] = fmul fast float [[REASS_MUL166]], [[TMP23]]
-; CHECK-NEXT:    [[TMP25:%.*]] = fadd fast float [[TMP24]], [[ARG]]
-; CHECK-NEXT:    [[TMP26:%.*]] = fmul fast float [[TMP25]], [[ARG]]
-; CHECK-NEXT:    [[TMP27:%.*]] = fadd fast float [[TMP26]], [[ARG]]
+; CHECK-NEXT:    [[TMP25:%.*]] = fadd fast float [[ARG]], [[TMP24]]
+; CHECK-NEXT:    [[TMP26:%.*]] = fmul fast float [[ARG]], [[TMP25]]
+; CHECK-NEXT:    [[TMP27:%.*]] = fadd fast float [[ARG]], [[TMP26]]
 ; CHECK-NEXT:    [[TMP29:%.*]] = fmul fast float [[ARG]], [[ARG]]
 ; CHECK-NEXT:    [[TMP31:%.*]] = fmul fast float [[TMP29]], 0x3FEA2E8B80000000
 ; CHECK-NEXT:    [[TMP33:%.*]] = fmul fast float [[TMP31]], [[TMP27]]
-; CHECK-NEXT:    [[TMP34:%.*]] = fadd fast float [[TMP33]], [[ARG]]
+; CHECK-NEXT:    [[TMP34:%.*]] = fadd fast float [[ARG]], [[TMP33]]
 ; CHECK-NEXT:    ret float [[TMP34]]
 ;
 entry:
   %tmp = fmul fast float %arg, 0xBFE99999A0000000
   %tmp1 = fadd fast float %tmp, 1.000000e+00
   %tmp2 = fmul fast float %arg, 0xBFE99999A0000000
   %tmp3 = fadd fast float %tmp2, 1.000000e+00
   %reass.mul156 = fmul fast float %arg, %tmp1

test/Transforms/Reassociate/propagate-flags.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 
 define double @func(double %a, double %b) {
 ; CHECK-LABEL: @func(
-; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast double [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fmul fast double [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = fmul fast double [[TMP1]], [[TMP1]]
 ; CHECK-NEXT:    ret double [[TMP2]]
 ;
   %mul1 = fmul fast double %a, %a
   %mul2 = fmul fast double %b, %b
   %mul3 = fmul fast double %mul1, %mul2
   ret double %mul3
 }

test/Transforms/Reassociate/reassociate_dbgvalue_discard.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S -o - | FileCheck %s
 
 ; After reassociation m1 and m2 aren't calculated as m1=c*a and m2=c*b any longer.
 ; So let's verify that the dbg.value nodes for m1 and m3 are invalidated.
 
 source_filename = "reassociate_dbgvalue_discard.c"
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define dso_local i32 @test1(i32 %a, i32 %b, i32 %c, i32 %d) local_unnamed_addr #0 !dbg !7 {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 undef, metadata !16, metadata !DIExpression()), !dbg !20
-; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 undef, metadata !17, metadata !DIExpression()), !dbg !21
-; CHECK-NEXT:    [[M1:%.*]] = mul i32 [[D:%.*]], [[C:%.*]], !dbg !22
-; CHECK-NEXT:    [[M3:%.*]] = mul i32 [[M1]], [[A:%.*]], !dbg !23
-; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[M3]], metadata !18, metadata !DIExpression()), !dbg !24
-; CHECK-NEXT:    [[M2:%.*]] = mul i32 [[D]], [[C]], !dbg !25
-; CHECK-NEXT:    [[M4:%.*]] = mul i32 [[M2]], [[B:%.*]], !dbg !26
+; CHECK-NEXT:    [[M1:%.*]] = mul i32 [[A:%.*]], [[C:%.*]], !dbg !20
+; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[M1]], metadata !16, metadata !DIExpression()), !dbg !21
+; CHECK-NEXT:    [[M2:%.*]] = mul i32 [[B:%.*]], [[C]], !dbg !22
+; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[M2]], metadata !17, metadata !DIExpression()), !dbg !23
+; CHECK-NEXT:    [[M3:%.*]] = mul i32 [[M1]], [[D:%.*]], !dbg !24
+; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[M3]], metadata !18, metadata !DIExpression()), !dbg !25
+; CHECK-NEXT:    [[M4:%.*]] = mul i32 [[M2]], [[D]], !dbg !26
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[M4]], metadata !19, metadata !DIExpression()), !dbg !27
 ; CHECK-NEXT:    [[RES:%.*]] = xor i32 [[M3]], [[M4]]
 ; CHECK-NEXT:    ret i32 [[RES]], !dbg !28
 ;
 entry:
   %m1 = mul i32 %c, %a, !dbg !24
   call void @llvm.dbg.value(metadata i32 %m1, metadata !16, metadata !DIExpression()), !dbg !25
   %m2 = mul i32 %c, %b, !dbg !26

test/Transforms/Reassociate/shift-factor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -instcombine -S | FileCheck %s
 
 ; There should be exactly one shift and one add left.
 
 define i32 @test1(i32 %X, i32 %Y) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[REASS_ADD:%.*]] = add i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = shl i32 [[REASS_ADD]], 1
 ; CHECK-NEXT:    ret i32 [[REASS_MUL]]
 ;
   %t2 = shl i32 %X, 1
   %t6 = shl i32 %Y, 1
   %t4 = add i32 %t6, %t2
   ret i32 %t4
 }
 

test/Transforms/Reassociate/vaarg_movable.ll

 ;
 ; CHECK-LABEL: @func(
 ; CHECK-NEXT:    [[VARARGS:%.*]] = alloca i8*, align 8
 ; CHECK-NEXT:    [[VARARGS1:%.*]] = bitcast i8** [[VARARGS]] to i8*
 ; CHECK-NEXT:    call void @llvm.va_start(i8* [[VARARGS1]])
 ; CHECK-NEXT:    [[V0:%.*]] = va_arg i8** [[VARARGS]], i32
 ; CHECK-NEXT:    [[V1:%.*]] = va_arg i8** [[VARARGS]], i32
 ; CHECK-NEXT:    [[V0_NEG:%.*]] = sub i32 0, [[V0]]
-; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[V0_NEG]], 1
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SUB]], [[V1]]
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[V1]], [[V0_NEG]]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[SUB]], 1
 ; CHECK-NEXT:    call void @llvm.va_end(i8* [[VARARGS1]])
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %varargs = alloca i8*, align 8
   %varargs1 = bitcast i8** %varargs to i8*
   call void @llvm.va_start(i8* %varargs1)
   %v0 = va_arg i8** %varargs, i32
   %v1 = va_arg i8** %varargs, i32
   %sub = sub nsw i32 %v1, %v0
   %add = add nsw i32 %sub, 1
   call void @llvm.va_end(i8* %varargs1)
   ret i32 %add
 }
 
 declare void @llvm.va_start(i8*)
 declare void @llvm.va_end(i8*)

test/Transforms/Reassociate/wrap-flags.ll

entry:
   ret i32 %mul2
 }
 
 define i2 @pr23926(i2 %X1, i2 %X2) {
 ;
 ; CHECK-LABEL: @pr23926(
 ; CHECK-NEXT:    [[X1_NEG:%.*]] = sub i2 0, [[X1:%.*]]
 ; CHECK-NEXT:    [[ADD_NEG:%.*]] = add i2 [[X1_NEG]], -1
-; CHECK-NEXT:    [[SUB:%.*]] = add i2 [[ADD_NEG]], [[X2:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = add i2 [[X2:%.*]], [[ADD_NEG]]
 ; CHECK-NEXT:    ret i2 [[SUB]]
 ;
   %add = add nuw i2 %X1, 1
   %sub = sub nuw nsw i2 %X2, %add
   ret i2 %sub
 }

test/Transforms/Reassociate/xor_reassoc.ll

 }
 
 ; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
 ;  c3 = ~c1 ^ c2
 define i32 @xor3(i32 %x, i32 %y) {
 ; CHECK-LABEL: @xor3(
 ; CHECK-NEXT:    [[AND_RA:%.*]] = and i32 [[X:%.*]], -436
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 123
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[XOR]], [[AND_RA]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[AND_RA]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[XOR1]]
 ;
   %or = or i32 %x, 123
   %xor = xor i32 %or, %y
   %and = and i32 %x, 456
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 }
 
 ; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
 ;  c3 = ~c1 ^ c2
 define <2 x i32> @xor3_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @xor3_vec(
 ; CHECK-NEXT:    [[AND_RA:%.*]] = and <2 x i32> [[X:%.*]], <i32 -436, i32 -436>
 ; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i32> [[Y:%.*]], <i32 123, i32 123>
-; CHECK-NEXT:    [[XOR1:%.*]] = xor <2 x i32> [[XOR]], [[AND_RA]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor <2 x i32> [[AND_RA]], [[XOR]]
 ; CHECK-NEXT:    ret <2 x i32> [[XOR1]]
 ;
   %or = or <2 x i32> %x, <i32 123, i32 123>
   %xor = xor <2 x i32> %or, %y
   %and = and <2 x i32> %x, <i32 456, i32 456>
   %xor1 = xor <2 x i32> %xor, %and
   ret <2 x i32> %xor1
 }
 
 ; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
 define i32 @xor4(i32 %x, i32 %y) {
 ; CHECK-LABEL: @xor4(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], -124
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 435
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[XOR]], [[AND]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[AND]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[XOR1]]
 ;
   %and = and i32 %x, -124
   %xor = xor i32 %y, 435
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 }
 
 ; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
 define <2 x i32> @xor4_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @xor4_vec(
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X:%.*]], <i32 -124, i32 -124>
 ; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i32> [[Y:%.*]], <i32 435, i32 435>
-; CHECK-NEXT:    [[XOR1:%.*]] = xor <2 x i32> [[XOR]], [[AND]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor <2 x i32> [[AND]], [[XOR]]
 ; CHECK-NEXT:    ret <2 x i32> [[XOR1]]
 ;
   %and = and <2 x i32> %x, <i32 -124, i32 -124>
   %xor = xor <2 x i32> %y, <i32 435, i32 435>
   %xor1 = xor <2 x i32> %xor, %and
   ret <2 x i32> %xor1
 }
 
;
   %xor1 = xor <2 x i32> %xor, %and
   ret <2 x i32> %xor1
 }
 
 ; Special case1:
 ;  (x | c1) ^ (x & c1) = x ^ c1
 define i32 @xor_special2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @xor_special2(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X:%.*]], 123
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[XOR]], [[Y:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 123
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[X:%.*]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[XOR1]]
 ;
   %or = or i32 %x, 123
   %xor = xor i32 %or, %y
   %and = and i32 %x, 123
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 }
 
 ; Special case1:
 ;  (x | c1) ^ (x & c1) = x ^ c1
 define <2 x i32> @xor_special2_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @xor_special2_vec(
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i32> [[X:%.*]], <i32 123, i32 123>
-; CHECK-NEXT:    [[XOR1:%.*]] = xor <2 x i32> [[XOR]], [[Y:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i32> [[Y:%.*]], <i32 123, i32 123>
+; CHECK-NEXT:    [[XOR1:%.*]] = xor <2 x i32> [[X:%.*]], [[XOR]]
 ; CHECK-NEXT:    ret <2 x i32> [[XOR1]]
 ;
   %or = or <2 x i32> %x, <i32 123, i32 123>
   %xor = xor <2 x i32> %or, %y
   %and = and <2 x i32> %x, <i32 123, i32 123>
   %xor1 = xor <2 x i32> %xor, %and
   ret <2 x i32> %xor1
 }

 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3
 ; is enabled if one of operands has multiple uses
 ;
 define i32 @xor_ra_size1(i32 %x) {
 ; CHECK-LABEL: @xor_ra_size1(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], 123
 ; CHECK-NEXT:    [[AND_RA:%.*]] = and i32 [[X]], 435
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND_RA]], 435
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[OR]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %or = or i32 %x, 123
   %or1 = or i32 %x, 456
   %xor = xor i32 %or, %or1
 
   %add = add i32 %xor, %or
   ret i32 %add
 }
 
 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3
 ; is disenabled if bothf operands has multiple uses.
 ;
 define i32 @xor_ra_size2(i32 %x) {
 ; CHECK-LABEL: @xor_ra_size2(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], 123
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[X]], 456
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[OR]], [[OR1]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[OR1]], [[OR]]
-; CHECK-NEXT:    [[ADD2:%.*]] = add i32 [[ADD]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[OR]], [[XOR]]
+; CHECK-NEXT:    [[ADD2:%.*]] = add i32 [[OR1]], [[ADD]]
 ; CHECK-NEXT:    ret i32 [[ADD2]]
 ;
   %or = or i32 %x, 123
   %or1 = or i32 %x, 456
   %xor = xor i32 %or, %or1
 
   %add = add i32 %xor, %or
   %add2 = add i32 %add, %or1

 define i32 @xor_bug2(i32, i32, i32, i32) {
 ; CHECK-LABEL: @xor_bug2(
 ; CHECK-NEXT:    [[TMP5:%.*]] = mul i32 [[TMP0:%.*]], 123
 ; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP1:%.*]], 3456789
 ; CHECK-NEXT:    [[TMP7:%.*]] = or i32 [[TMP6]], 4567890
 ; CHECK-NEXT:    [[TMP8:%.*]] = and i32 [[TMP2:%.*]], 255
 ; CHECK-NEXT:    [[AND_RA:%.*]] = and i32 [[TMP1]], -360490541
 ; CHECK-NEXT:    [[TMP9:%.*]] = xor i32 [[TMP5]], 891034567
-; CHECK-NEXT:    [[TMP10:%.*]] = xor i32 [[TMP9]], [[AND_RA]]
-; CHECK-NEXT:    [[TMP11:%.*]] = xor i32 [[TMP10]], [[TMP7]]
+; CHECK-NEXT:    [[TMP10:%.*]] = xor i32 [[AND_RA]], [[TMP9]]
+; CHECK-NEXT:    [[TMP11:%.*]] = xor i32 [[TMP7]], [[TMP10]]
 ; CHECK-NEXT:    [[TMP12:%.*]] = and i32 [[TMP3:%.*]], 255
 ; CHECK-NEXT:    [[TMP13:%.*]] = add i32 [[TMP1]], 32
 ; CHECK-NEXT:    [[TMP14:%.*]] = add i32 [[TMP13]], [[TMP2]]
-; CHECK-NEXT:    [[TMP15:%.*]] = add i32 [[TMP14]], [[TMP8]]
+; CHECK-NEXT:    [[TMP15:%.*]] = add i32 [[TMP8]], [[TMP14]]
 ; CHECK-NEXT:    [[TMP16:%.*]] = add i32 [[TMP15]], [[TMP11]]
 ; CHECK-NEXT:    ret i32 [[TMP16]]
 ;
   %5 = mul i32 %0, 123
   %6 = add i32 %2, 24
   %7 = add i32 %1, 8
   %8 = and i32 %1, 3456789
   %9 = or i32 %8,  4567890