[Reassociate] swap binop operands to increase factoring potential

[spatel]

Summary

If we have a pair of binops feeding another pair of binops, rearrange the operands so the matching pair are together because that allows easy factorization folds to happen in instcombine:
((X << S) & Y) & (Z << S) --> ((X << S) & (Z << S)) & Y (reassociation)

--> ((X & Z) << S) & Y (factorize shift from 'and' ops optimization)

This is part of solving PR37098:
https://bugs.llvm.org/show_bug.cgi?id=37098

Note that there's an instcombine version of this patch attached there. This reassociate patch took about 10x more effort, so I hope this is the preferred direction. :)

For reasons I still don't completely understand, reassociate does this kind of transform sometimes, but misses everything in my motivating cases.

This patch on its own is gluing an independent cleanup chunk to the end of the existing RewriteExprTree() loop. But if it's approved, I think we can build on it and do something stronger to better order the full expression tree like D40049. That might be an alternative to the proposal to add a separate reassociation pass like D41574.

[spatel]

Ping.

[lebedev.ri]

lib/Transforms/Scalar/Reassociate.cpp

2121 ↗

(On Diff #143169)

I'd think this could be

if (!B.isAssociative() || !B.isCommutative() ||
    !match(&B, m_BinOp(m_BinOp(B0), m_BinOp(B1))))
  return;

[spatel]

lib/Transforms/Scalar/Reassociate.cpp

2121 ↗

(On Diff #143169)

Sure - I can change that if the general functionality of the patch is approved.

[opaparo]

What are your plans for deeper associate-operand trees, such as in the tests I've suggested at D41574? Will you support such cases?

[bjope]

As far as I can see this is another case of reusing existing Instructions/Values, while changing the actual value that the Instruction produce, right?

Take a look at the debug-info fixes I made here for a similar problem in RewriteExprTree: https://reviews.llvm.org/D45975
I suspect that you may need to discard debug-info in a similar way as in D45975, somewhere inside your new function swapOperandsToMatchBinops.

[spatel]

In D45842#1081028, @opaparo wrote:

What are your plans for deeper associate-operand trees, such as in the tests I've suggested at D41574? Will you support such cases?

This patch is independent of D41574 from what I see. Ie, that patch makes no difference on any of these tests. Could it be enhanced to catch these?

If we want to do something like D41574 (provide stronger sorting of the expression tree based on opcode/operand) here in the existing -reassociate, then an addition to ReassociateExpression() like this could be used:

for (unsigned i = 0; i < Ops.size() - 1; ++i) {
  for (unsigned j = i + 1; j < Ops.size(); ++j) {
    BinaryOperator *B0, *B1;
    if (!match(Ops[i].Op, m_BinOp(B0)))
      continue;
    if (match(Ops[j].Op, m_BinOp(B1)) && B0->getOpcode() < B1->getOpcode())
      continue;
    if (B0->getOpcode() == B1->getOpcode()) {
      const APInt *B0C, *B1C;
      if (match(B0->getOperand(1), m_APInt(B0C)) && match(B1->getOperand(1), m_APInt(B1C)))
        if (B0C->ule(*B1C))
          continue;
    }
    std::swap(Ops[i], Ops[j]);
  }
}

That creates some of the factoring folds that we want, but it won't reduce as far as shown in the other patch. I'm not sure if that's a limitation of this pass or if I just botched the code (and this is untested, so may not be correct).

[spatel]

In D45842#1081077, @bjope wrote:

As far as I can see this is another case of reusing existing Instructions/Values, while changing the actual value that the Instruction produce, right?

Take a look at the debug-info fixes I made here for a similar problem in RewriteExprTree: https://reviews.llvm.org/D45975
I suspect that you may need to discard debug-info in a similar way as in D45975, somewhere inside your new function swapOperandsToMatchBinops.

Thanks! You're correct that we're recycling instructions here (not sure why we don't just create new instructions with a Builder?). The funny thing about all the examples here is that after we swap operands in swapOperandsToMatchBinops(), we end up going through the main reassociation loop again and make more changes which triggers your code D45975, so I already see 'undef' in the right places.

Nevertheless, it's a small change to extract and call that code, so let me do that to be safe.

[spatel]

Patch updated:

1. Extract discardDebugInfo() as a helper function and use it.
2. Added a test case with debug info (baseline added at rL331083).
3. Use another m_BinOp to shrink the code.

[bjope]

In D45842#1081703, @spatel wrote:

In D45842#1081077, @bjope wrote:

As far as I can see this is another case of reusing existing Instructions/Values, while changing the actual value that the Instruction produce, right?

Take a look at the debug-info fixes I made here for a similar problem in RewriteExprTree: https://reviews.llvm.org/D45975
I suspect that you may need to discard debug-info in a similar way as in D45975, somewhere inside your new function swapOperandsToMatchBinops.

Thanks! You're correct that we're recycling instructions here (not sure why we don't just create new instructions with a Builder?). The funny thing about all the examples here is that after we swap operands in swapOperandsToMatchBinops(), we end up going through the main reassociation loop again and make more changes which triggers your code D45975, so I already see 'undef' in the right places.

Nevertheless, it's a small change to extract and call that code, so let me do that to be safe.

Great! Your last update seems to fix my concern about debug-info. I'll let someone else review the actual code transformation done here.

[spatel]

Ping * 2.

Note that D46336 is proposing to solve the reassociation problems shown here within instcombine (but in a bigger way than my draft patch would have done it).

[lebedev.ri]

Overall, this seems to make sense to me, but the comments seem misdirecting.

lib/Transforms/Scalar/Reassociate.cpp

2138 ↗

(On Diff #144408)

And by "matching" you really mean "with the same type as the parent binop"

2141 ↗

(On Diff #144408)

Why can't we swap if B1 has more than one use?
And why is it not a problem for B0? (and positive test for this multi-use would be awesome)

2147 ↗

(On Diff #144408)

// If B0 is still not matching, or both operands already have the same opcode, nothing to do.

2152–2153 ↗

(On Diff #144408)

I find this comment not strictly true.
We only check that B00->getOpcode() != OtherOpc, we don't check B01.
Also s/V01/B01/

2157 ↗

(On Diff #144408)

And here we don't care about one-use?

2161 ↗

(On Diff #144408)

B01 ?

2163–2165 ↗

(On Diff #144408)

I see, so V01 and B01 are actually the same thing, but with different type.
Would it be better to condense it into one if, like:

BinaryOperator *B01;
if (( match(B0->getOperand(0), m_BinOp(B00)) && B00->getOpcode() == OtherOpc) && 
    (!match(B0->getOperand(1), m_BinOp(B01)) || B01->getOpcode() != OtherOpc)) {
  Value *V01 = B0->getOperand(1);

?

test/Transforms/Reassociate/matching-binops.ll

186 ↗

(On Diff #144408)

The logic behind one-use restrictions in this case is not clear to me,
so i'd personally prefer to have more one-use tests, where one-use is
the only thing that is preventing the reassociation.

[lebedev.ri]

Hmm, is only test/Transforms/Reassociate/matching-binops.ll regenerated here?
I'm wondering why D46336 changes so many more tests.

[spatel]

In D45842#1088136, @lebedev.ri wrote:

Hmm, is only test/Transforms/Reassociate/matching-binops.ll regenerated here?
I'm wondering why D46336 changes so many more tests.

Yes, and this is intentional. I don't think we usually want to have IR regression tests that depend on multiple passes. Although in this case - because I've left the actual factoring/distributive optimization out of this patch (at least for now) - it may be worth adding tests under PhaseOrdering to make sure that nothing is interfering with this transform before instcombine has a chance to reduce it.

[lebedev.ri]

In D45842#1088226, @spatel wrote:

In D45842#1088136, @lebedev.ri wrote:

Hmm, is only test/Transforms/Reassociate/matching-binops.ll regenerated here?
I'm wondering why D46336 changes so many more tests.

Yes, and this is intentional.

Oh right, this is a reassociate pass, not instcombine :)

I don't think we usually want to have IR regression tests that depend on multiple passes. Although in this case - because I've left the actual factoring/distributive optimization out of this patch (at least for now) - it may be worth adding tests under PhaseOrdering to make sure that nothing is interfering with this transform before instcombine has a chance to reduce it.

[spatel]

Patch updated:
I think what made this patch confusing and overly complex is trying to recycle existing instructions (swapping operands rather than just creating new instructions).

As I mentioned in an earlier comment, I don't see a good reason to do that, so let's do the easy thing: use IRBuilder to create new instructions. This has 3 benefits and shrinks the patch:

1. It simplifies the code needed for commutative canonicalization (looks more like the original instcombine patch now).
2. It means we don't need to manually update debug info (IRBuilder does the right thing automatically).
3. It makes the IR flag clearing/propagation cleaner.

[spatel]

FWIW, I added a debug statistic for this transform and tested with test-suite, and it fires 1301 times.

[lebedev.ri]

In D45842#1090363, @spatel wrote:

Patch updated:
I think what made this patch confusing and overly complex is trying to recycle existing instructions (swapping operands rather than just creating new instructions).

As I mentioned in an earlier comment, I don't see a good reason to do that, so let's do the easy thing: use IRBuilder to create new instructions. This has 3 benefits and shrinks the patch:

1. It simplifies the code needed for commutative canonicalization (looks more like the original instcombine patch now).
2. It means we don't need to manually update debug info (IRBuilder does the right thing automatically).
3. It makes the IR flag clearing/propagation cleaner.

Nice!
Looks much better, much easier to follow the logic / read the code.

I think this is ok, but maybe wait for a second opinion, i don't trust myself too much..

[bjope]

test/Transforms/Reassociate/matching-binops.ll

297 ↗

(On Diff #145523)

nit: Verify that we "discard" the dbg.value for variable "a" (metadata !19 in the input, metadata !18 in the output), since we do nto calculate the value %and after the transformation.

@aprantl once told me that is was better to use metadata i32 undef instead of metadata !{} when a dbg.value is "discarded". I think it is out-of-scope for this patch, but maybe the code that picks metadata !2 in this solution should insert an undef value instead (or maybe later passes should handle metadata !{} the same way as if we have an explicit undef value, in case there really is a difference today).

[lebedev.ri]

One important take-away from https://reviews.llvm.org/D46336#1090588:
The InstCombine and Reassociate need to be run after each another in a loop (what't the correct term, internal pipeline?) until neither of them produces any more changes.

bool madeChanges = false;
do {
  madeChanges |= instcombine();
  madeChanges |= reassociate();
} while(madeChanges);

[aprantl]

test/Transforms/Reassociate/matching-binops.ll

297 ↗

(On Diff #145523)

Do you think it would help to have a common facility along the lines of DbgInstrinsicInstr::replaceWithUndef() to make it easier to do the right thing?

[spatel]

test/Transforms/Reassociate/matching-binops.ll

297 ↗

(On Diff #145523)

Definitely. I don't know anything about debuginfo, so I don't know why one option is better than the other or what is best.

As you can see, I'm just using a default IRBuilder, so can we get it to do the optimal thing automatically?

[spatel]

In D45842#1091129, @lebedev.ri wrote:

One important take-away from https://reviews.llvm.org/D46336#1090588:
The InstCombine and Reassociate need to be run after each another in a loop (what't the correct term, internal pipeline?) until neither of them produces any more changes.

bool madeChanges = false;
do {
  madeChanges |= instcombine();
  madeChanges |= reassociate();
} while(madeChanges);

There are parallel conversations going on about the general direction, so let's move this to llvm-dev and reach consensus before we get into the details:
http://lists.llvm.org/pipermail/llvm-dev/2018-May/123117.html

[spatel]

If there are no objections, I'll commit this soon. The larger D41574 looks stalled. In the meantime, this is a small patch/improvement that will help limit hyper-extension proposals to instcombine. The patch still applies to trunk cleanly.

[spatel]

Reopening - reverted with rL342083 because this patch can cause indeterminate output.
At first glance, it's not incorrect output, but there is a difference in the order of operands.

[lebedev.ri]

I don't think this just relanded, phab gone mad due to the disk space issues?

[sammccall]

In D45842#1697098, @lebedev.ri wrote:

I don't think this just relanded, phab gone mad due to the disk space issues?

Yes. It's decided to reimport all the reviews, so anything that was committed and reopened will probably be autoclosed :-(
Sorry, not really sure how to stop it without leaving everything in an unimported state.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

[fhahn]

Is this still needed? Marking as changes requested to clear from review queue.

[spatel]

I think we've managed to get this for most cases in InstCombine now, so abandoning.

llvm/include/llvm/Transforms/Scalar/Reassociate.h

private:
   Value *OptimizeMul(BinaryOperator *I,
                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
   void EraseInst(Instruction *I);
   void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts);
   void OptimizeInst(Instruction *I);
   Instruction *canonicalizeNegConstExpr(Instruction *I);
   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
+  void swapOperandsToMatchBinops(BinaryOperator &B);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H

llvm/lib/Transforms/Scalar/Reassociate.cpp

 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include <algorithm>
 #include <cassert>
 #include <utility>
 
 using namespace llvm;
 using namespace reassociate;
+using namespace PatternMatch;
 
 #define DEBUG_TYPE "reassociate"
 
 STATISTIC(NumChanged, "Number of insts reassociated");
 STATISTIC(NumAnnihil, "Number of expr tree annihilated");
 STATISTIC(NumFactor , "Number of multiplies factored");
 
 #ifndef NDEBUG
if (BO->hasOneUse() && BO->getOpcode() == Instruction::Add &&
     return;
   if (BO->hasOneUse() && BO->getOpcode() == Instruction::FAdd &&
       cast<Instruction>(BO->user_back())->getOpcode() == Instruction::FSub)
     return;
 
   ReassociateExpression(BO);
 }
 
+/// If we have an associative pair of binops with the same opcode and 2 of the 3
+/// operands to that pair of binops are some other matching binop, rearrange the
+/// operands of the associative binops so the matching ops are paired together.
+/// This transform creates factoring opportunities by pairing opcodes.
+/// TODO: Should those factoring optimizations be handled here or InstCombine?
+/// Example:
+///   ((X << S) & Y) & (Z << S) --> ((X << S) & (Z << S)) & Y (reassociation)
+///     --> ((X & Z) << S) & Y (factorize shift from 'and' ops optimization)
+void ReassociatePass::swapOperandsToMatchBinops(BinaryOperator &B) {
+  BinaryOperator *B0, *B1;
+  if (!B.isAssociative() || !B.isCommutative() ||
+      !match(&B, m_BinOp(m_BinOp(B0), m_BinOp(B1))))
+    return;
+
+  // We have (B0 op B1) where both operands are also binops.
+  // Canonicalize a binop with the same opcode as the parent binop (B) to B0 and
+  // a binop with a different opcode to B1.
+  Instruction::BinaryOps TopOpc = B.getOpcode();
+  if (B0->getOpcode() != TopOpc)
+    std::swap(B0, B1);
+
+  // If (1) we don't have a pair of binops with the same opcode or (2) B0 and B1
+  // already have the same opcode, there is nothing to do. If the binop with the
+  // same opcode (B0) has more than one use, reassociation would result in more
+  // instructions, so bail out.
+  Instruction::BinaryOps OtherOpc = B1->getOpcode();
+  if (B0->getOpcode() != TopOpc || !B0->hasOneUse() || OtherOpc == TopOpc)
+    return;
+
+  // Canonicalize a binop that matches B1 to V00 (operand 0 of B0) and a value
+  // that does not match B1 to V01.
+  Value *V00 = B0->getOperand(0), *V01 = B0->getOperand(1);
+  if (!match(V00, m_BinOp()) ||
+      cast<BinaryOperator>(V00)->getOpcode() != OtherOpc)
+    std::swap(V00, V01);
+
+  // We need a binop with the same opcode in V00, and a value with a different
+  // opcode in V01.
+  BinaryOperator *B00, *B01;
+  if (!match(V00, m_BinOp(B00)) || B00->getOpcode() != OtherOpc ||
+      (match(V01, m_BinOp(B01)) && B01->getOpcode() == OtherOpc))
+    return;
+
+  // B00 and B1 are displaced matching binops, so pull them together:
+  // (B00 & V01) & B1  --> (B00 & B1) & V01
+  IRBuilder<> Builder(&B);
+  Builder.SetInstDebugLocation(&B);
+  Value *NewBO1 = Builder.CreateBinOp(TopOpc, B00, B1);
+  Value *NewBO2 = Builder.CreateBinOp(TopOpc, NewBO1, V01);
+
+  // Fast-math-flags propagate from B; wrapping flags are cleared.
+  if (auto *I1 = dyn_cast<Instruction>(NewBO1))
+    I1->copyIRFlags(&B, false);
+  if (auto *I2 = dyn_cast<Instruction>(NewBO2))
+    I2->copyIRFlags(&B, false);
+
+  B.replaceAllUsesWith(NewBO2);
+  return;
+}
+
 void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
   // First, walk the expression tree, linearizing the tree, collecting the
   // operand information.
   SmallVector<RepeatedValue, 8> Tree;
   MadeChange |= LinearizeExprTree(I, Tree);
   SmallVector<ValueEntry, 8> Ops;
   Ops.reserve(Tree.size());
   for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
if (Max > 1) {
       Ops.erase(&Ops[BestPair.first]);
       Ops.push_back(Op0);
       Ops.push_back(Op1);
     }
   }
   // Now that we ordered and optimized the expressions, splat them back into
   // the expression tree, removing any unneeded nodes.
   RewriteExprTree(I, Ops);
+
+  // Try a final reassociation of the root of the tree.
+  swapOperandsToMatchBinops(*I);
 }
 
 void
 ReassociatePass::BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT) {
   // Make a "pairmap" of how often each operand pair occurs.
   for (BasicBlock *BI : RPOT) {
     for (Instruction &I : *BI) {
       if (!I.isAssociative())

llvm/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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[Z:%.*]]
 ; 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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[Z:%.*]]
 ; 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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[Z:%.*]]
 ; 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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[Z:%.*]]
 ; 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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[Z:%.*]]
 ; 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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[Z:%.*]]
 ; 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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[Z:%.*]]
 ; 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 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[Z:%.*]]
 ; 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> [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], [[Z:%.*]]
 ; 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
 }
;
   %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.
+; We only care about extra uses of the first associative value - in this
+; case, it's %a. Everything else can have extra uses.
+
+declare void @use(i8)
 
 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:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[A]], [[SY]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[SX]], [[SY]]
+; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], [[Z:%.*]]
+; CHECK-NEXT:    call void @use(i8 [[SX]])
+; CHECK-NEXT:    call void @use(i8 [[SY]])
+; CHECK-NEXT:    call void @use(i8 [[TMP2]])
+; CHECK-NEXT:    ret i8 [[TMP2]]
 ;
   %sx = lshr i8 %x, %shamt
   %a = add i8 %sx, %z
   %sy = lshr i8 %y, %shamt
   %r = add i8 %a, %sy
+  call void @use(i8 %sx)
+  call void @use(i8 %sy)
+  call void @use(i8 %r)
   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 i8 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = mul i8 [[A]], [[Z:%.*]]
 ; 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:    [[R:%.*]] = add nsw i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = add i8 [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[A]], [[Z:%.*]]
 ; 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:    [[SY:%.*]] = fmul float [[Y:%.*]], [[M]]
-; CHECK-NEXT:    [[R:%.*]] = fadd fast float [[A]], [[SY]]
+; CHECK-NEXT:    [[A:%.*]] = fadd fast float [[SX]], [[SY]]
+; CHECK-NEXT:    [[R:%.*]] = fadd fast float [[A]], [[Z:%.*]]
 ; 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 [[SY]], [[SX]]
+; CHECK-NEXT:    [[R:%.*]] = fmul fast float [[A]], [[Z:%.*]]
 ; 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).
+; Verify that debug info for modified instructions is not invalid.
 
 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:    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:    call void @llvm.dbg.value(metadata i32 [[AND2]], metadata !19, metadata !DIExpression()), !dbg !31
-; CHECK-NEXT:    ret i32 [[AND2]], !dbg !32
+; CHECK-NEXT:    call void @llvm.dbg.value(metadata !2, metadata !18, metadata !DIExpression()), !dbg !28
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[SHL]], [[SHL1]], !dbg !29
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Z]], !dbg !29
+; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP2]], metadata !19, metadata !DIExpression()), !dbg !30
+; CHECK-NEXT:    ret i32 [[TMP2]], !dbg !31
 ;
   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
   call void @llvm.dbg.value(metadata i32 %shl, metadata !17, metadata !DIExpression()), !dbg !26
   %shl1 = shl i32 %y, %shamt, !dbg !27