[Transforms][LICM] Add the ability to undo unprofitable reassociation

[pawosm01]

Summary

Consider the following piece of code:

void innermost_loop(int i, double d1, double d2, double delta, int n, double cells[n])
{
  int j;
  const double d1d = d1 * delta;
  const double d2d = d2 * delta;

  for (j = 0; j <= i; j++)
    cells[j] = d1d * cells[j + 1] + d2d * cells[j];
}

When compiling at -Ofast level, after the "Reassociate expressions"
pass, this code is transformed into an equivalent of:

int j;

for (j = 0; j <= i; j++)
  cells[j] = (d1 * cells[j + 1] + d2 * cells[j]) * delta;

Effectively, the computation of those loop invariants isn't done
before the loop anymore, we have one extra multiplication on each
loop iteration instead. Sadly, this results in a significant
performance hit.

Similarly, specifically crafted user code will also experience
inability to hoist those invariants.

This patch is solving this issue by adding the ability to undo such
reassociation into the LICM pass. Note that for doing such
transformation this pass requires the same conditions as the
"Reassociate expressions" pass, namely, the involved binary operators
must have the reassociations allowed (e.g. by specifying the fast
attribute) and they must have single use only.

Some parts of this patch were suggested by Nikita Popov.

[pawosm01]

Making it slightly less readable, per clang-format request.

[pawosm01]

Back to the drawing board: my patch can’t cope with IR emitted by flang-new: Instruction does not dominate all uses

[pawosm01]

Fixing the problem I've found while using this patch with a larger codebase.

[pawosm01]

I had to simplify this logic. After some time even I couldn't understand it.

[huntergr]

llvm/lib/Transforms/Scalar/LICM.cpp

2754–2755

This seems a little odd, like you might be processing more candidates than you originally identified and want to prevent wrapping?

I think it might be better to see if you can add candidate operations to a SmallVector worklist and process them directly from that instead of walking back through the IR a second time.

[qcolombet]

llvm/lib/Transforms/Scalar/LICM.cpp

2677

Could you add a comment on what this function is doing and what it means to return true or false?

It'll make the review easier.

[pawosm01]

Reaction to the review comments.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2677

I'll try.

2754–2755

Yeah, that simplifies the code indeed.

[huntergr]

llvm/lib/Transforms/Scalar/LICM.cpp

2707–2708

Can just 'return false;' here instead of taking the extra step before returning.

Same with the other checks in this loop.

2732

I don't think we need a count here; just a boolean 'CandidateFound' would suffice.

2744–2754

Using a loop over the ops with a break after the substitution is performed feels a bit unwieldy. Could you try recording the Ops in a known order in Changes (probably using std::swap as you did before), so you know that e.g. the first one is always loop invariant? I don't think we need to maintain the order of operations for an fmul so you could overwrite both, but if there is a good reason to maintain the order then you could just make the nested pair in changes a tuple instead and record the index of the invariant operand.

[pawosm01]

post-review changes

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2707–2708

Yes, same in the other places.

2732

It isn't as easy as it seems. As it turns, this transformation shouldn't be applied for every situation where at least one candidate is found.

There are two problems here:

1. a simple expression like inv1 * var1 * inv2 will be found as a candidate and transformed into var1 * (inv1 * inv2) where (inv1 * inv2) part will be hoisted. But this expression itself can be a part of a longer expression, e.g. inv1 * var1 * inv2 + inv1 * var2 * inv2 + inv1 * var3 * inv2 which before the introduction of my change could easily be transformed into (var1 + var2 + var3) * (inv1 * inv2) with (inv1 * inv2) hoisted. The transformation I'm proposing should rather focus on the expressions described in the comment block placed before this function which usually require undoing the actions of some previous pass (namely, the Reasociate pass), and leave simpler cases alone and make the existing test cases supporting them just pass without any awfully messy change. Hence, I've added AnyAdds variable to make sure the intended expression patterns are being found. The previous oversimlified condition eliminated such cases by a sheer coincidence.

2. with the expression long enough and small enough trip count there is a possibility that the transformation leading to the hoisting can cause performance degradation. If most of the operations in a particularly long expression involves non-invariants, there will be more multiplications introduced than operations hoisted. By changing the type of the Candidates counter to a signed integer and decrementing it whenever there is no invariant in the operation (hence no candidate for hoisting), the applicability of this transformation can be limited to the situations where the numbers of non-invariant operations and hoisting candidates are at least equal. A crude estimate and naïve one, I can admit that, but anything better would overcomplicate the logic here, e.g. by introducing instruction cost estimation and trip count estimation, the cost of doing it can easily outgrow any benefits.

2744–2754

yeah, I've simplified this.

[huntergr]

llvm/lib/Transforms/Scalar/LICM.cpp

2704–2706

It may be worthwhile considering an upper limit on the number of multiplies you support -- depending on the trip count of the loop, you may actually be introducing extra work for no gain (especially for a target with wide vectors that may complete everything in one vector iteration).

2732

Yes, I see that if you have multiplies with no loop-invariant operands in the chain of adds then you need to add more multiplies inside the loop, which seems to defeat the purpose of the optimization. So perhaps we should avoid performing this transformation if there is such a multiply in the chain.

It might be possible to perform it with only 1 such multiply since you'll be reordering the operations and may reduce the latency, but that would require benchmarking to confirm and is dependent on the workload and target, but I think the safe side is to bail out.

[pawosm01]

Following the reviewer's suggestions.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2704–2706

I've imposed a reasonable upper limit below.

[huntergr]

LGTM

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2679

deassociate -> reassociate

2691–2692

Here and elsewhere: Remove all unnecessary parentheses, apply de Morgan as needed.

2702

I think you just reinvented Use? That's how you reference a specific operand of an instruction.

[pawosm01]

Post-review changes again.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2702

Ok, I've changed it to make use of Use, I hope you'll like it.

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2725

This should be &Op->getOperandUse(Ops[L.isLoopInvariant(Ops[0]) ? 0 : 1]) or so. But I think it would be less awkward to do something like this, so you don't go back and forth between operand indices, Values and Uses:

if (Op->getOpcode() != Instruction::FMul) {
  if (OpNext->getOpcode() != Instruction::FMul)
    return false;
  std::swap(Op, OpNext);
}
if (!Op->hasOneUse() || !Op->hasAllowReassoc() || L.isLoopInvariant(Op))
  return false;
Use &U0 = Op->getOperandUse(0);
Use &U1 = Op->getOperandUse(1);
if (L.isLoopInvariant(U0))
  Changes.push_back(&U0);
else if (L.isLoopInvariant(U1))
  Changes.push_back(&U1);
else
  return false;

[pawosm01]

more post-review changes.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2725

ok, thanks for your valuable input.

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2708

Do we need to require that the fadd is reassoc as well?

2742

This copies the FMF flags from the top-level fmul, but is that correct? We have multiple fadds and fmuls involved in the transform, why is it safe to use the flags from that one in particular?

(The test coverage for this is not great, because you just use "fast" everywhere.)

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2708

Yes, this match specifically requires that the expression is of the form that is described in the comment written above this function: ((A1 * B1) + (A2 * B2) + ...). I wrote this function to solve the problem at hand, to which I know that my solution provides noticeable performance benefit. Trying to make it more general would require a whole lot more research and performance impact analysis that would go far beyond what I wanted to fix. I'm offering this solution which I based on the other hoist... functions in this file, I believe if one finds a reason for extending this (to handle their own performance issue at hand), they could do that basing on what I did propose.

2742

Yes I assume it's correct. What is happening here is that the fmul instruction from which the flag is taken is effectively being copied to every subexpression in the parenthesis, it is reasonable to copy the fast flag too. As checking for associations being allowed is implicitly checking the fast flag, nothing harmful is happening here.

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2708

Let me rephrase this: Isn't this missing a reassoc check on the fadd? We check the root fmul above, and we check the inner fmuls below, but we don't seem to check anything about the fadd.

2732

I didn't quite get your argument in 1. for why it's a bad idea to transform inv1 * var1 * inv2 into var1 * (inv1 * inv2). Why is there a problem if it's part of a longer expression? Wouldn't we still get (var1 + var2 + var3) * (inv1 * inv2) as the end result if inv1 * inv2 is hoisted out of each part and then CSEd?

As far as I can tell, the transform should be profitable regardless of whether there is an fadd or not.

2742

The transform only requires the reassoc flag on each instruction, while this is also copying all other FMF flags. It's not obvious to me that this is correct.

One could probably make an argument along the lines of "if the final fmul is nnan, then that implies that the fadd chain result is not nan. As the result would be nan if any operand were nan, we can propagate the nnan flag up the chain". This sounds plausible. But I'm not sure the same logic holds up for ninf and other FMF flags.

[pawosm01]

more changes

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2708

I assumed it would be checked anyhow, when OpNext is processed, but yeah, it is more clear to check it early, yet also it should be checked whether it is FAdd in the first place

2732

Followed your observation, I've added such ability, plus a simple test case covering it.

2742

Ok, so let's copy it from the affected instruction itself...

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2701

As a final note, I would rewrite this loop into a worklist iteration, something along these lines:

SmallVector<BinaryOperator *> Worklist;
Worklist.push_back(VariantOp);
while (!Worklist.empty()) {
  BinaryOperator *BO = Worklist.pop_back_val();
  if (!BO->hasOneUse())
    return false;
  BinaryOperator *Op0, *Op1;
  if (match(BO, m_FAdd(m_BinOp(Op0), m_BinOp(Op1))) &&
      I->hasAllocReassoc()) {
    Worklist.push_back(Op0);
    Worklist.push_back(Op1);
    continue;
  }
  if (BO->getOpcode() != Instruction::FMul || !BO->hasAllocReassoc() ||
      L.isLoopInvariant(BO))
    return false;
  Use &U0 = BO->getOperandUse(0);
  Use &U1 = BO->getOperandUse(1);
   if (L.isLoopInvariant(U0))
     Changes.push_back(&U0);
   else if (L.isLoopInvariant(U1))
     Changes.push_back(&U1);
   else
     return false;
   if (Changes.size() > 5U) // A reasonable upper limit
     return false;
}

This has the benefit of not relying on specific structure for the fadds (is there something that guarantees that these form a linear chain?) and I think is also less confusing because the fadd and fmul handling is pretty cleanly separated.

I also wanted to ask where the number 5 for the cutoff comes from. Is that just chosen arbitrarily?

2741

dyn_cast + assert == cast

[pawosm01]

Following reviewer's advice.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2701

Well, I deliberately wanted to avoid recursion, even if explicitly using stack (here named a Worklist). But this looks so neat that let's have it this way.

2741

ah, I didn't notice that, I'll get back to it soon.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2701

I also wanted to ask where the number 5 for the cutoff comes from. Is that just chosen arbitrarily?

This was chosen arbitrarily indeed, the choice was based on an observation of the problem at hand.

[pawosm01]

a missing change instantiated

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2741

Done.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/LICM.cpp

2737

nit: Can move this IRBuilder outside the loop.

[paulwalker-arm]

llvm/lib/Transforms/Scalar/LICM.cpp

2701

Perhaps it's worth replacing the hardwired value with a command line option that defaults to 5?

[pawosm01]

Added new option, as suggested by the reviewer.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2701

Agreed. I've added one.

[pawosm01]

One more change.

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

2737

Ah, yeah, good catch; corrected.

[paulwalker-arm]

Thanks for adding the command line option @pawosm01.

llvm/lib/Transforms/Scalar/LICM.cpp

133

Up to you but I think "licm-max-num-fp-reassociations" or "licm-fp-reassociation-cap" would be more in keeping with the existing naming of licm options.

[pawosm01]

following reviewer's advice

[pawosm01]

llvm/lib/Transforms/Scalar/LICM.cpp

133

yes, "licm-max-num-fp-reassociations" seems a better name for an option.

[bgraur]

Heads-up: this is likely causing a miscompile. We're working on a reproducer.

[bgraur]

In D152281#4570151, @bgraur wrote:

Heads-up: this is likely causing a miscompile. We're working on a reproducer.

This was a false alarm. Please disregard.

llvm/lib/Transforms/Scalar/LICM.cpp

 STATISTIC(NumLoadPromoted, "Number of load-only promotions");
 STATISTIC(NumLoadStorePromoted, "Number of load and store promotions");
 STATISTIC(NumMinMaxHoisted,
           "Number of min/max expressions hoisted out of the loop");
 STATISTIC(NumGEPsHoisted,
           "Number of geps reassociated and hoisted out of the loop");
 STATISTIC(NumAddSubHoisted, "Number of add/subtract expressions reassociated "
                             "and hoisted out of the loop");
+STATISTIC(NumFPAssociationsHoisted, "Number of invariant FP expressions "
+                                    "reassociated and hoisted out of the loop");
 
 /// Memory promotion is enabled by default.
 static cl::opt<bool>
     DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
                      cl::desc("Disable memory promotion in LICM pass"));
 
 static cl::opt<bool> ControlFlowHoisting(
     "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
     cl::desc("Enable control flow (and PHI) hoisting in LICM"));
 
 static cl::opt<bool>
     SingleThread("licm-force-thread-model-single", cl::Hidden, cl::init(false),
                  cl::desc("Force thread model single in LICM pass"));
 
 static cl::opt<uint32_t> MaxNumUsesTraversed(
     "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
     cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
 // Experimental option to allow imprecision in LICM in pathological cases, in
 // exchange for faster compile. This is to be removed if MemorySSA starts to
 // address the same issue. LICM calls MemorySSAWalker's
 // getClobberingMemoryAccess, up to the value of the Cap, getting perfect
 // accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
 // which may not be precise, since optimizeUses is capped. The result is
 // correct, but we may not get as "far up" as possible to get which access is
 // clobbering the one queried.
 cl::opt<unsigned> llvm::SetLicmMssaOptCap(
     "licm-mssa-optimization-cap", cl::init(100), cl::Hidden,

   // users instead of I itself.
   if (hoistAdd(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT))
     return true;
 
   if (hoistSub(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT))
     return true;
 
   return false;
 }
 
+/// Try to reassociate expressions like ((A1 * B1) + (A2 * B2) + ...) * C where
+/// A1, A2, ... and C are loop invariants into expressions like
+/// ((A1 * C * B1) + (A2 * C * B2) + ... and hoist the (A1 * C), (A2 * C), ...
+/// invariant expressions. This functions returns true only if any hoisting has
+/// actually occured.
+static bool hoistFPAssociation(Instruction &I, Loop &L,
+                               ICFLoopSafetyInfo &SafetyInfo,
+                               MemorySSAUpdater &MSSAU, AssumptionCache *AC,
+                               DominatorTree *DT) {
+  using namespace PatternMatch;
+  Value *VariantOp = nullptr, *InvariantOp = nullptr;
+
+  if (!match(&I, m_FMul(m_Value(VariantOp), m_Value(InvariantOp))) ||
+      !I.hasAllowReassoc())
+    return false;
+  if (L.isLoopInvariant(VariantOp))
+    std::swap(VariantOp, InvariantOp);
+  if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
+    return false;
+  Value *Factor = InvariantOp;
+
+  // First, we need to make sure we should do the transformation.
+  bool AnyAdds = false;
+  SmallVector<Use *> Changes;
+  for (BinaryOperator *Op = nullptr, *OpNext = nullptr,
+                      *VOp = dyn_cast<BinaryOperator>(VariantOp);
+       VOp; VOp = OpNext) {
+    if (!VOp->hasOneUse() || !VOp->hasAllowReassoc())
+      return false;
+    if (!match(VOp, m_FAdd(m_BinOp(Op), m_BinOp(OpNext)))) {
+      Op = VOp;
+      OpNext = nullptr;
+    } else
+      AnyAdds = true;
+    if (Op->getOpcode() != Instruction::FMul) {
+      if (!OpNext)
+        return false;
+      if (OpNext->getOpcode() != Instruction::FMul)
+        return false;
+      std::swap(Op, OpNext);
+    }
+    if (!Op->hasOneUse() || !Op->hasAllowReassoc() || L.isLoopInvariant(Op))
+      return false;
+    Use &U0 = Op->getOperandUse(0);
+    Use &U1 = Op->getOperandUse(1);
+    if (L.isLoopInvariant(U0))
+      Changes.push_back(&U0);
+    else if (L.isLoopInvariant(U1))
+      Changes.push_back(&U1);
+    else
+      return false;
+    if (Changes.size() > 5U) // A reasonable upper limit
+      return false;
+  }
+  if (Changes.empty() || !AnyAdds)
+    return false;
+
+  // We know we should do it so let's do the transformation.
+  auto *Preheader = L.getLoopPreheader();
+  assert(Preheader && "Loop is not in simplify form?");
+  for (auto *U : Changes) {
+    assert(L.isLoopInvariant(U->get()));
+    IRBuilder<> Builder(Preheader->getTerminator());
+    U->set(Builder.CreateFMulFMF(U->get(), Factor, &I, "factor.op.fmul"));
+  }
+  I.replaceAllUsesWith(VariantOp);
+  eraseInstruction(I, SafetyInfo, MSSAU);
+  return true;
+}
+
 static bool hoistArithmetics(Instruction &I, Loop &L,
                              ICFLoopSafetyInfo &SafetyInfo,
                              MemorySSAUpdater &MSSAU, AssumptionCache *AC,
                              DominatorTree *DT) {
   // Optimize complex patterns, such as (x < INV1 && x < INV2), turning them
   // into (x < min(INV1, INV2)), and hoisting the invariant part of this
   // expression out of the loop.
   if (hoistMinMax(I, L, SafetyInfo, MSSAU)) {
     ++NumHoisted;
     ++NumMinMaxHoisted;
     return true;
   }
 
   // Try to hoist GEPs by reassociation.
   if (hoistGEP(I, L, SafetyInfo, MSSAU, AC, DT)) {
     ++NumHoisted;
     ++NumGEPsHoisted;
     return true;
   }
 
   // Try to hoist add/sub's by reassociation.
   if (hoistAddSub(I, L, SafetyInfo, MSSAU, AC, DT)) {
     ++NumHoisted;
     ++NumAddSubHoisted;
     return true;
   }
 
+  if (hoistFPAssociation(I, L, SafetyInfo, MSSAU, AC, DT)) {
+    ++NumHoisted;
+    ++NumFPAssociationsHoisted;
+    return true;
+  }
+
   return false;
 }
 
 /// Little predicate that returns true if the specified basic block is in
 /// a subloop of the current one, not the current one itself.
 ///
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
   return LI->getLoopFor(BB) != CurLoop;
 }

llvm/test/Transforms/LICM/expr-reassociate.ll

 ; LICM_ONLY-NEXT:    store double [[FADD_1]], ptr [[ARRAYIDX_J]], align 8
 ; LICM_ONLY-NEXT:    br label [[FOR_COND]]
 ; LICM_ONLY:       for.end:
 ; LICM_ONLY-NEXT:    ret void
 ;
 ; LICM_AFTER_REASSOCIATE-LABEL: define void @innermost_loop_2d_fast
 ; LICM_AFTER_REASSOCIATE-SAME: (i32 [[I:%.*]], double [[D1:%.*]], double [[D2:%.*]], double [[DELTA:%.*]], ptr [[CELLS:%.*]]) {
 ; LICM_AFTER_REASSOCIATE-NEXT:  entry:
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FACTOR_OP_FMUL:%.*]] = fmul fast double [[D2]], [[DELTA]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FACTOR_OP_FMUL1:%.*]] = fmul fast double [[D1]], [[DELTA]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    br label [[FOR_COND:%.*]]
 ; LICM_AFTER_REASSOCIATE:       for.cond:
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD_J_1:%.*]], [[FOR_BODY:%.*]] ]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[J]], [[I]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    br i1 [[CMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; LICM_AFTER_REASSOCIATE:       for.body:
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ADD_J_1]] = add nuw nsw i32 [[J]], 1
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[IDXPROM_J_1:%.*]] = zext i32 [[ADD_J_1]] to i64
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ARRAYIDX_J_1:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J_1]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CELL_1:%.*]] = load double, ptr [[ARRAYIDX_J_1]], align 8
-; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[D1]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[FACTOR_OP_FMUL1]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[IDXPROM_J:%.*]] = zext i32 [[J]] to i64
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ARRAYIDX_J:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CELL_2:%.*]] = load double, ptr [[ARRAYIDX_J]], align 8
-; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[D2]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[FACTOR_OP_FMUL]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[REASS_ADD:%.*]] = fadd fast double [[FMUL_2]], [[FMUL_1]]
-; LICM_AFTER_REASSOCIATE-NEXT:    [[REASS_MUL:%.*]] = fmul fast double [[REASS_ADD]], [[DELTA]]
-; LICM_AFTER_REASSOCIATE-NEXT:    store double [[REASS_MUL]], ptr [[ARRAYIDX_J]], align 8
+; LICM_AFTER_REASSOCIATE-NEXT:    store double [[REASS_ADD]], ptr [[ARRAYIDX_J]], align 8
 ; LICM_AFTER_REASSOCIATE-NEXT:    br label [[FOR_COND]]
 ; LICM_AFTER_REASSOCIATE:       for.end:
 ; LICM_AFTER_REASSOCIATE-NEXT:    ret void
 ;
 entry:
   %fmul.d1 = fmul fast double %d1, %delta
   %fmul.d2 = fmul fast double %d2, %delta
   br label %for.cond

 ; LICM_ONLY-NEXT:    store double [[FADD_2]], ptr [[ARRAYIDX_J_2]], align 8
 ; LICM_ONLY-NEXT:    br label [[FOR_COND]]
 ; LICM_ONLY:       for.end:
 ; LICM_ONLY-NEXT:    ret void
 ;
 ; LICM_AFTER_REASSOCIATE-LABEL: define void @innermost_loop_3d_fast
 ; LICM_AFTER_REASSOCIATE-SAME: (i32 [[I:%.*]], double [[D1:%.*]], double [[D2:%.*]], double [[D3:%.*]], double [[DELTA:%.*]], ptr [[CELLS:%.*]]) {
 ; LICM_AFTER_REASSOCIATE-NEXT:  entry:
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FACTOR_OP_FMUL:%.*]] = fmul fast double [[D3]], [[DELTA]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FACTOR_OP_FMUL2:%.*]] = fmul fast double [[D2]], [[DELTA]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FACTOR_OP_FMUL3:%.*]] = fmul fast double [[D1]], [[DELTA]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    br label [[FOR_COND:%.*]]
 ; LICM_AFTER_REASSOCIATE:       for.cond:
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD_J_1:%.*]], [[FOR_BODY:%.*]] ]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[J]], [[I]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    br i1 [[CMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; LICM_AFTER_REASSOCIATE:       for.body:
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ADD_J_1]] = add nuw nsw i32 [[J]], 1
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[IDXPROM_J_1:%.*]] = zext i32 [[ADD_J_1]] to i64
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ARRAYIDX_J_1:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J_1]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CELL_1:%.*]] = load double, ptr [[ARRAYIDX_J_1]], align 8
-; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[D1]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[FACTOR_OP_FMUL3]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[IDXPROM_J:%.*]] = zext i32 [[J]] to i64
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ARRAYIDX_J:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CELL_2:%.*]] = load double, ptr [[ARRAYIDX_J]], align 8
-; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[D2]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[FACTOR_OP_FMUL2]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ADD_J_2:%.*]] = add nuw nsw i32 [[J]], 2
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[IDXPROM_J_2:%.*]] = zext i32 [[ADD_J_2]] to i64
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ARRAYIDX_J_2:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J_2]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CELL_3:%.*]] = load double, ptr [[ARRAYIDX_J_2]], align 8
-; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_3:%.*]] = fmul fast double [[CELL_3]], [[D3]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_3:%.*]] = fmul fast double [[CELL_3]], [[FACTOR_OP_FMUL]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[REASS_ADD:%.*]] = fadd fast double [[FMUL_2]], [[FMUL_1]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[REASS_ADD1:%.*]] = fadd fast double [[REASS_ADD]], [[FMUL_3]]
-; LICM_AFTER_REASSOCIATE-NEXT:    [[REASS_MUL:%.*]] = fmul fast double [[REASS_ADD1]], [[DELTA]]
-; LICM_AFTER_REASSOCIATE-NEXT:    store double [[REASS_MUL]], ptr [[ARRAYIDX_J_2]], align 8
+; LICM_AFTER_REASSOCIATE-NEXT:    store double [[REASS_ADD1]], ptr [[ARRAYIDX_J_2]], align 8
 ; LICM_AFTER_REASSOCIATE-NEXT:    br label [[FOR_COND]]
 ; LICM_AFTER_REASSOCIATE:       for.end:
 ; LICM_AFTER_REASSOCIATE-NEXT:    ret void
 ;
 entry:
   %fmul.d1 = fmul fast double %d1, %delta
   %fmul.d2 = fmul fast double %d2, %delta
   %fmul.d3 = fmul fast double %d3, %delta

 ; REASSOCIATE_ONLY-NEXT:    store double [[REASS_MUL]], ptr [[ARRAYIDX_J]], align 8
 ; REASSOCIATE_ONLY-NEXT:    br label [[FOR_COND]]
 ; REASSOCIATE_ONLY:       for.end:
 ; REASSOCIATE_ONLY-NEXT:    ret void
 ;
 ; LICM_ONLY-LABEL: define void @innermost_loop_2d_fast_reassociated
 ; LICM_ONLY-SAME: (i32 [[I:%.*]], double [[D1:%.*]], double [[D2:%.*]], double [[DELTA:%.*]], ptr [[CELLS:%.*]]) {
 ; LICM_ONLY-NEXT:  entry:
+; LICM_ONLY-NEXT:    [[FACTOR_OP_FMUL:%.*]] = fmul fast double [[D2]], [[DELTA]]
+; LICM_ONLY-NEXT:    [[FACTOR_OP_FMUL1:%.*]] = fmul fast double [[D1]], [[DELTA]]
 ; LICM_ONLY-NEXT:    br label [[FOR_COND:%.*]]
 ; LICM_ONLY:       for.cond:
 ; LICM_ONLY-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD_J_1:%.*]], [[FOR_BODY:%.*]] ]
 ; LICM_ONLY-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[J]], [[I]]
 ; LICM_ONLY-NEXT:    br i1 [[CMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; LICM_ONLY:       for.body:
 ; LICM_ONLY-NEXT:    [[ADD_J_1]] = add nuw nsw i32 [[J]], 1
 ; LICM_ONLY-NEXT:    [[IDXPROM_J_1:%.*]] = zext i32 [[ADD_J_1]] to i64
 ; LICM_ONLY-NEXT:    [[ARRAYIDX_J_1:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J_1]]
 ; LICM_ONLY-NEXT:    [[CELL_1:%.*]] = load double, ptr [[ARRAYIDX_J_1]], align 8
-; LICM_ONLY-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[D1]]
+; LICM_ONLY-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[FACTOR_OP_FMUL1]]
 ; LICM_ONLY-NEXT:    [[IDXPROM_J:%.*]] = zext i32 [[J]] to i64
 ; LICM_ONLY-NEXT:    [[ARRAYIDX_J:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J]]
 ; LICM_ONLY-NEXT:    [[CELL_2:%.*]] = load double, ptr [[ARRAYIDX_J]], align 8
-; LICM_ONLY-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[D2]]
+; LICM_ONLY-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[FACTOR_OP_FMUL]]
 ; LICM_ONLY-NEXT:    [[REASS_ADD:%.*]] = fadd fast double [[FMUL_2]], [[FMUL_1]]
-; LICM_ONLY-NEXT:    [[REASS_MUL:%.*]] = fmul fast double [[REASS_ADD]], [[DELTA]]
-; LICM_ONLY-NEXT:    store double [[REASS_MUL]], ptr [[ARRAYIDX_J]], align 8
+; LICM_ONLY-NEXT:    store double [[REASS_ADD]], ptr [[ARRAYIDX_J]], align 8
 ; LICM_ONLY-NEXT:    br label [[FOR_COND]]
 ; LICM_ONLY:       for.end:
 ; LICM_ONLY-NEXT:    ret void
 ;
 ; LICM_AFTER_REASSOCIATE-LABEL: define void @innermost_loop_2d_fast_reassociated
 ; LICM_AFTER_REASSOCIATE-SAME: (i32 [[I:%.*]], double [[D1:%.*]], double [[D2:%.*]], double [[DELTA:%.*]], ptr [[CELLS:%.*]]) {
 ; LICM_AFTER_REASSOCIATE-NEXT:  entry:
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FACTOR_OP_FMUL:%.*]] = fmul fast double [[D2]], [[DELTA]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FACTOR_OP_FMUL1:%.*]] = fmul fast double [[D1]], [[DELTA]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    br label [[FOR_COND:%.*]]
 ; LICM_AFTER_REASSOCIATE:       for.cond:
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD_J_1:%.*]], [[FOR_BODY:%.*]] ]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[J]], [[I]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    br i1 [[CMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; LICM_AFTER_REASSOCIATE:       for.body:
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ADD_J_1]] = add nuw nsw i32 [[J]], 1
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[IDXPROM_J_1:%.*]] = zext i32 [[ADD_J_1]] to i64
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ARRAYIDX_J_1:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J_1]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CELL_1:%.*]] = load double, ptr [[ARRAYIDX_J_1]], align 8
-; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[D1]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_1:%.*]] = fmul fast double [[CELL_1]], [[FACTOR_OP_FMUL1]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[IDXPROM_J:%.*]] = zext i32 [[J]] to i64
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[ARRAYIDX_J:%.*]] = getelementptr inbounds double, ptr [[CELLS]], i64 [[IDXPROM_J]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[CELL_2:%.*]] = load double, ptr [[ARRAYIDX_J]], align 8
-; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[D2]]
+; LICM_AFTER_REASSOCIATE-NEXT:    [[FMUL_2:%.*]] = fmul fast double [[CELL_2]], [[FACTOR_OP_FMUL]]
 ; LICM_AFTER_REASSOCIATE-NEXT:    [[REASS_ADD:%.*]] = fadd fast double [[FMUL_2]], [[FMUL_1]]
-; LICM_AFTER_REASSOCIATE-NEXT:    [[REASS_MUL:%.*]] = fmul fast double [[REASS_ADD]], [[DELTA]]
-; LICM_AFTER_REASSOCIATE-NEXT:    store double [[REASS_MUL]], ptr [[ARRAYIDX_J]], align 8
+; LICM_AFTER_REASSOCIATE-NEXT:    store double [[REASS_ADD]], ptr [[ARRAYIDX_J]], align 8
 ; LICM_AFTER_REASSOCIATE-NEXT:    br label [[FOR_COND]]
 ; LICM_AFTER_REASSOCIATE:       for.end:
 ; LICM_AFTER_REASSOCIATE-NEXT:    ret void
 ;
 entry:
   br label %for.cond
 
 for.cond: