[SCEVExpander] Preserve LCSSA directly.

[fhahn]

Summary

This patch teaches SCEVExpander to directly preserve LCSSA.

As it is currently, SCEV does not look through PHI nodes in loops,
as it might break LCSSA form. Once SCEVExpander can preserve
LCSSA form, it should be safe for SCEV to look through PHIs.

To preserve LCSSA form, this patch uses formLCSSAForInstructions
on operands of newly created instructions, if the definition is inside
a different loop than the new instruction.

The final value we return from expandCodeFor may also need LCSSA
phis, depending on the insert point. As no user for it exists there yet,
create a temporary instruction at the insert point, which can be passed
to formLCSSAForInstructions. This temporary instruction is removed
after LCSSA construction.

[merge_guards_bot]

clang-format: pass.

Build artifacts: diff.json, console-log.txt

[fhahn]

Rebased, simplified code, all tests passing now.

[mkazantsev]

Could you please add some .ll tests showing how this change impacts the code being generated (if it is possible)?

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

182–183

Please add a comment on what is Root.

182–183

My concern here is that now, as it seems, it is only valid to call expandCodeFor with Root = false when expanding sub-expression for another expression. But because by default Root is true, people who are not aware of this might easily make mistakes in the future (it is intuitive to just call expand and not pass root param unless I have to).

I'd suggest the following:

• Have private version of expandCodeFor without default value for this param, so that we must always specify it explicitly;
• Have public version of expandCodeFor that calls expandCodeFor( .., Root = true).

In that way, it will be harder to make this kind of mistakes. WDYT?

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1765

I don't quite get this logic. If all you need it for is an insertion point, why not just take next/prev iterator if Inst in its block?

[fhahn]

Introduce expandCodeForImpl, make Root non-optional, document Root.

In D71538#2155291, @mkazantsev wrote:

Could you please add some .ll tests showing how this change impacts the code being generated (if it is possible)?

Thank you very much for taking a look!

This change should be NFC (I'll adjust the commit message) with current SCEV, where we do not look through LCSSA phis. This means there should be no cases where we would need to insert/get LCSSA phis (there are no code changes on SPEC2000,SPEC2006,MultiSource with -O3 -flto on X86).

I also put up a follow-up patch (D71539), which changes SCEV to look through PHIs and then we may need to get/insert LCSSA phis while expanding.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

182–183

In that way, it will be harder to make this kind of mistakes. WDYT?

yes that makes a lot of sense, thanks! I dropped the Root argument from expandCodeFor and added a expandCodeForImpl that takes Root without default. expandCodeForImpl is supposed to be used internally by SCEVExpander, while expandCodeFor is for external clients and passes Root = true.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1765

This code here is a preparation step so we can use formLCSSAForInstructions to fix the LCSSA form. formLCSSAForInstructions will insert LCSSA phi nodes as required for all uses of a given instruction.

The problem here is that we do not have a use at the insertion point yet, as the caller will insert the use. So to conveniently use the existing formLCSSAForInstructions, it is easiest to just create a temporary user at the insertion point, so LCSSA phis are inserted for uses at insertion point, if required. Does that make sense?

[fhahn]

ping

[mkazantsev]

Let's give it a try. :) LGTM with some nits inline.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

393

The inserted code is inserted -> The code is inserted; too many insertions for one sentence :)

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1765

I get it, thanks. Looks fishy, I'm certain there should be a cleaner way to do it, but I cannot come up with one on the top of my head. Please add a TODO to consider a better way to do it.

[fhahn]

In D71538#2178409, @mkazantsev wrote:

Let's give it a try. :) LGTM with some nits inline.

Thank you very much for taking a look! I'll definitely keep an eye out for any upcoming issues.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1765

Agreed, I added a comment. I will look into this as follow-up, unless some other fundamental issues are exposed by the patches.

[uabelho]

Hi!

We ran into a problem with this patch. I wrote https://bugs.llvm.org/show_bug.cgi?id=47343 about it.

[fhahn]

In D71538#2244228, @uabelho wrote:

Hi!

We ran into a problem with this patch. I wrote https://bugs.llvm.org/show_bug.cgi?id=47343 about it.

Thanks for the report. I'll take a look in the next few days. If it is blocking you, please feel free to revert.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

 /// memory.
 class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
   ScalarEvolution &SE;
   const DataLayout &DL;
 
   // New instructions receive a name to identify them with the current pass.
   const char *IVName;
 
+  /// Indicates whether LCSSA phis should be created for inserted values.
+  bool PreserveLCSSA;
+
   // InsertedExpressions caches Values for reuse, so must track RAUW.
   DenseMap<std::pair<const SCEV *, Instruction *>, TrackingVH<Value>>
       InsertedExpressions;
 
   // InsertedValues only flags inserted instructions so needs no RAUW.
   DenseSet<AssertingVH<Value>> InsertedValues;
   DenseSet<AssertingVH<Value>> InsertedPostIncValues;
 
#ifndef NDEBUG
   const char *DebugType;
 #endif
 
   friend struct SCEVVisitor<SCEVExpander, Value *>;
 
 public:
   /// Construct a SCEVExpander in "canonical" mode.
   explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
-                        const char *name)
-      : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr),
-        IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false),
+                        const char *name, bool PreserveLCSSA = true)
+      : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
+        IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
+        LSRMode(false),
         Builder(se.getContext(), TargetFolder(DL),
                 IRBuilderCallbackInserter(
                     [this](Instruction *I) { rememberInstruction(I); })) {
 #ifndef NDEBUG
     DebugType = "";
 #endif
   }
 
#endif
   /// to expand the same expression into multiple BasicBlocks or different
   /// places within the same BasicBlock can do so.
   void clear() {
     InsertedExpressions.clear();
     InsertedValues.clear();
     InsertedPostIncValues.clear();
     ChainedPhis.clear();
   }
 
   /// Return true for expressions that can't be evaluated at runtime
   /// within given \b Budget.
   ///
   /// At is a parameter which specifies point in code where user is going to
   /// expand this expression. Sometimes this knowledge can lead to
   /// a less pessimistic cost estimation.
   bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
                            const TargetTransformInfo *TTI,
                            const Instruction *At) {
#endif
 
   /// replace congruent phis with their most canonical representative. Return
   /// the number of phis eliminated.
   unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
                                SmallVectorImpl<WeakTrackingVH> &DeadInsts,
                                const TargetTransformInfo *TTI = nullptr);
 
   /// Insert code to directly compute the specified SCEV expression into the
-  /// program.  The inserted code is inserted into the specified block.
-  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);
+  /// program.  The code is inserted into the specified block.
+  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) {
+    return expandCodeForImpl(SH, Ty, I, true);
+  }
 
   /// Insert code to directly compute the specified SCEV expression into the
-  /// program.  The inserted code is inserted into the SCEVExpander's current
+  /// program.  The code is inserted into the SCEVExpander's current
   /// insertion point. If a type is specified, the result will be expanded to
   /// have that type, with a cast if necessary.
-  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
+  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) {
+    return expandCodeForImpl(SH, Ty, true);
+  }
 
   /// Generates a code sequence that evaluates this predicate.  The inserted
   /// instructions will be at position \p Loc.  The result will be of type i1
   /// and will have a value of 0 when the predicate is false and 1 otherwise.
   Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc);
 
   /// A specialized variant of expandCodeForPredicate, handling the case when
   /// we are expanding code for a SCEVEqualPredicate.
#endif
   /// didn't find any value it does not mean that there is no such value.
   ///
   Optional<ScalarEvolution::ValueOffsetPair>
   getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
 
 private:
   LLVMContext &getContext() const { return SE.getContext(); }
 
+  /// Insert code to directly compute the specified SCEV expression into the
+  /// program. The code is inserted into the SCEVExpander's current
+  /// insertion point. If a type is specified, the result will be expanded to
+  /// have that type, with a cast if necessary. If \p Root is true, this
+  /// indicates that \p SH is the top-level expression to expand passed from
+  /// an external client call.
+  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root);
+
+  /// Insert code to directly compute the specified SCEV expression into the
+  /// program. The code is inserted into the specified block. If \p
+  /// Root is true, this indicates that \p SH is the top-level expression to
+  /// expand passed from an external client call.
+  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I, bool Root);
+
   /// Recursive helper function for isHighCostExpansion.
   bool isHighCostExpansionHelper(const SCEV *S, Loop *L, const Instruction &At,
                                  int &BudgetRemaining,
                                  const TargetTransformInfo &TTI,
                                  SmallPtrSetImpl<const SCEV *> &Processed,
                                  SmallVectorImpl<const SCEV *> &Worklist);
 
   /// Insert the specified binary operator, doing a small amount of work to
private:
 
   /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
   /// ptrtoint+arithmetic+inttoptr.
   Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end,
                         PointerType *PTy, Type *Ty, Value *V);
   Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
 
   /// Find a previous Value in ExprValueMap for expand.
   ScalarEvolution::ValueOffsetPair
   FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
 
   Value *expand(const SCEV *S);
 
   /// Determine the most "relevant" loop for the given SCEV.
   const Loop *getRelevantLoop(const SCEV *);
 
   Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
                                      Type *&TruncTy, bool &InvertStep);
   Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy,
                      Type *IntTy, bool useSubtract);
 
   void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
                       Instruction *Pos, PHINode *LoopPhi);
 
   void fixupInsertPoints(Instruction *I);
+
+  /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new
+  /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User.
+  /// If no PHIs have been created, return the unchanged operand \p OpIdx.
+  Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx);
 };
 } // namespace llvm
 
 #endif

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 /// Rewrite all the fixup locations with new values, following the chosen
 /// solution.
 void LSRInstance::ImplementSolution(
     const SmallVectorImpl<const Formula *> &Solution) {
   // Keep track of instructions we may have made dead, so that
   // we can remove them after we are done working.
   SmallVector<WeakTrackingVH, 16> DeadInsts;
 
-  SCEVExpander Rewriter(SE, L->getHeader()->getModule()->getDataLayout(),
-                        "lsr");
+  SCEVExpander Rewriter(SE, L->getHeader()->getModule()->getDataLayout(), "lsr",
+                        false);
 #ifndef NDEBUG
   Rewriter.setDebugType(DEBUG_TYPE);
 #endif
   Rewriter.disableCanonicalMode();
   Rewriter.enableLSRMode();
   Rewriter.setIVIncInsertPos(L, IVIncInsertPos);
 
   // Mark phi nodes that terminate chains so the expander tries to reuse them.
static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,
   Changed |=
       LSRInstance(L, IU, SE, DT, LI, TTI, AC, TLI, MSSAU.get()).getChanged();
 
   // Remove any extra phis created by processing inner loops.
   Changed |= DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());
   if (EnablePhiElim && L->isLoopSimplifyForm()) {
     SmallVector<WeakTrackingVH, 16> DeadInsts;
     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
-    SCEVExpander Rewriter(SE, DL, "lsr");
+    SCEVExpander Rewriter(SE, DL, "lsr", false);
 #ifndef NDEBUG
     Rewriter.setDebugType(DEBUG_TYPE);
 #endif
     unsigned numFolded = Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, &TTI);
     if (numFolded) {
       Changed = true;
       RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts, &TLI,
                                                            MSSAU.get());

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
 
 using namespace llvm;
 
 cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(
     "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
     cl::desc("When performing SCEV expansion only if it is cheap to do, this "
              "controls the budget that is considered cheap (default = 4)"));
 
if (ElTy->isSized()) {
         }
       }
     }
 
     // Record the scaled array index for this level of the type. If
     // we didn't find any operands that could be factored, tentatively
     // assume that element zero was selected (since the zero offset
     // would obviously be folded away).
-    Value *Scaled = ScaledOps.empty() ?
-                    Constant::getNullValue(Ty) :
-                    expandCodeFor(SE.getAddExpr(ScaledOps), Ty);
+    Value *Scaled =
+        ScaledOps.empty()
+            ? Constant::getNullValue(Ty)
+            : expandCodeForImpl(SE.getAddExpr(ScaledOps), Ty, false);
     GepIndices.push_back(Scaled);
 
     // Collect struct field index operands.
     while (StructType *STy = dyn_cast<StructType>(ElTy)) {
       bool FoundFieldNo = false;
       // An empty struct has no fields.
       if (STy->getNumElements() == 0) break;
       // Field offsets are known. See if a constant offset falls within any of
if (!AnyNonZeroIndices) {
     // Cast the base to i8*.
     V = InsertNoopCastOfTo(V,
        Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
 
     assert(!isa<Instruction>(V) ||
            SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
 
     // Expand the operands for a plain byte offset.
-    Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty);
+    Value *Idx = expandCodeForImpl(SE.getAddExpr(Ops), Ty, false);
 
     // Fold a GEP with constant operands.
     if (Constant *CLHS = dyn_cast<Constant>(V))
       if (Constant *CRHS = dyn_cast<Constant>(Idx))
         return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()),
                                               CLHS, CRHS);
 
     // Do a quick scan to see if we have this GEP nearby.  If so, reuse it.
if (!Sum) {
       SmallVector<const SCEV *, 4> NewOps;
       NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) :
                                                SE.getSCEV(Sum));
       for (++I; I != E && I->first == CurLoop; ++I)
         NewOps.push_back(I->second);
       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
     } else if (Op->isNonConstantNegative()) {
       // Instead of doing a negate and add, just do a subtract.
-      Value *W = expandCodeFor(SE.getNegativeSCEV(Op), Ty);
+      Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty, false);
       Sum = InsertNoopCastOfTo(Sum, Ty);
       Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,
                         /*IsSafeToHoist*/ true);
       ++I;
     } else {
       // A simple add.
-      Value *W = expandCodeFor(Op, Ty);
+      Value *W = expandCodeForImpl(Op, Ty, false);
       Sum = InsertNoopCastOfTo(Sum, Ty);
       // Canonicalize a constant to the RHS.
       if (isa<Constant>(Sum)) std::swap(Sum, W);
       Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
                         /*IsSafeToHoist*/ true);
       ++I;
     }
   }
const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
     while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
       ++Exponent;
       ++E;
     }
     assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
 
     // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
     // that are needed into the result.
-    Value *P = expandCodeFor(I->second, Ty);
+    Value *P = expandCodeForImpl(I->second, Ty, false);
     Value *Result = nullptr;
     if (Exponent & 1)
       Result = P;
     for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
       P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,
                       /*IsSafeToHoist*/ true);
       if (Exponent & BinExp)
         Result = Result ? InsertBinop(Instruction::Mul, Result, P,
Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
   }
 
   return Prod;
 }
 
 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
 
-  Value *LHS = expandCodeFor(S->getLHS(), Ty);
+  Value *LHS = expandCodeForImpl(S->getLHS(), Ty, false);
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
     const APInt &RHS = SC->getAPInt();
     if (RHS.isPowerOf2())
       return InsertBinop(Instruction::LShr, LHS,
                          ConstantInt::get(Ty, RHS.logBase2()),
                          SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
   }
 
-  Value *RHS = expandCodeFor(S->getRHS(), Ty);
+  Value *RHS = expandCodeForImpl(S->getRHS(), Ty, false);
   return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
                      /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
 }
 
 /// Move parts of Base into Rest to leave Base with the minimal
 /// expression that provides a pointer operand suitable for a
 /// GEP expansion.
 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
   // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
   // so it's not worth implementing SmallPtrSet::swap.
   PostIncLoopSet SavedPostIncLoops = PostIncLoops;
   PostIncLoops.clear();
 
   // Expand code for the start value into the loop preheader.
   assert(L->getLoopPreheader() &&
          "Can't expand add recurrences without a loop preheader!");
-  Value *StartV = expandCodeFor(Normalized->getStart(), ExpandTy,
-                                L->getLoopPreheader()->getTerminator());
+  Value *StartV =
+      expandCodeForImpl(Normalized->getStart(), ExpandTy,
+                        L->getLoopPreheader()->getTerminator(), false);
 
   // StartV must have been be inserted into L's preheader to dominate the new
   // phi.
   assert(!isa<Instruction>(StartV) ||
          SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
                                  L->getHeader()));
 
   // Expand code for the step value. Do this before creating the PHI so that PHI
   // reuse code doesn't see an incomplete PHI.
   const SCEV *Step = Normalized->getStepRecurrence(SE);
   // If the stride is negative, insert a sub instead of an add for the increment
   // (unless it's a constant, because subtracts of constants are canonicalized
   // to adds).
   bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
   if (useSubtract)
     Step = SE.getNegativeSCEV(Step);
   // Expand the step somewhere that dominates the loop header.
-  Value *StepV = expandCodeFor(Step, IntTy,
-                               &*L->getHeader()->getFirstInsertionPt());
+  Value *StepV = expandCodeForImpl(
+      Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
 
   // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
   // we actually do emit an addition.  It does not apply if we emit a
   // subtraction.
   bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
   bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
 
   // Create the PHI.
if (isa<Instruction>(Result) &&
       bool useSubtract =
         !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
       if (useSubtract)
         Step = SE.getNegativeSCEV(Step);
       Value *StepV;
       {
         // Expand the step somewhere that dominates the loop header.
         SCEVInsertPointGuard Guard(Builder, this);
-        StepV = expandCodeFor(Step, IntTy,
-                              &*L->getHeader()->getFirstInsertionPt());
+        StepV = expandCodeForImpl(
+            Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
       }
       Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
     }
   }
 
   // We have decided to reuse an induction variable of a dominating loop. Apply
   // truncation and/or inversion of the step.
   if (TruncTy) {
     Type *ResTy = Result->getType();
     // Normalize the result type.
     if (ResTy != SE.getEffectiveSCEVType(ResTy))
       Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
     // Truncate the result.
     if (TruncTy != Result->getType())
       Result = Builder.CreateTrunc(Result, TruncTy);
 
     // Invert the result.
     if (InvertStep)
-      Result = Builder.CreateSub(expandCodeFor(Normalized->getStart(), TruncTy),
-                                 Result);
+      Result = Builder.CreateSub(
+          expandCodeForImpl(Normalized->getStart(), TruncTy, false), Result);
   }
 
   // Re-apply any non-loop-dominating scale.
   if (PostLoopScale) {
     assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
     Result = InsertNoopCastOfTo(Result, IntTy);
     Result = Builder.CreateMul(Result,
-                               expandCodeFor(PostLoopScale, IntTy));
+                               expandCodeForImpl(PostLoopScale, IntTy, false));
   }
 
   // Re-apply any non-loop-dominating offset.
   if (PostLoopOffset) {
     if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
       if (Result->getType()->isIntegerTy()) {
-        Value *Base = expandCodeFor(PostLoopOffset, ExpandTy);
+        Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy, false);
         Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
       } else {
         Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
       }
     } else {
       Result = InsertNoopCastOfTo(Result, IntTy);
-      Result = Builder.CreateAdd(Result,
-                                 expandCodeFor(PostLoopOffset, IntTy));
+      Result = Builder.CreateAdd(
+          Result, expandCodeForImpl(PostLoopOffset, IntTy, false));
     }
   }
 
   return Result;
 }
 
 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
   // In canonical mode we compute the addrec as an expression of a canonical IV
if (CanonicalIV &&
       SE.getTypeSizeInBits(Ty)) {
     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
                                        S->getNoWrapFlags(SCEV::FlagNW)));
     BasicBlock::iterator NewInsertPt =
         findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
-    V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
-                      &*NewInsertPt);
+    V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
+                          &*NewInsertPt, false);
     return V;
   }
 
   // {X,+,F} --> X + {0,+,F}
   if (!S->getStart()->isZero()) {
     SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());
     NewOps[0] = SE.getConstant(Ty, 0);
     const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
 
   // Truncate the result down to the original type, if needed.
   const SCEV *T = SE.getTruncateOrNoop(V, Ty);
   return expand(T);
 }
 
 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
-  Value *V = expandCodeFor(S->getOperand(),
-                           SE.getEffectiveSCEVType(S->getOperand()->getType()));
+  Value *V = expandCodeForImpl(
+      S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
+      false);
   return Builder.CreateTrunc(V, Ty);
 }
 
 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
-  Value *V = expandCodeFor(S->getOperand(),
-                           SE.getEffectiveSCEVType(S->getOperand()->getType()));
+  Value *V = expandCodeForImpl(
+      S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
+      false);
   return Builder.CreateZExt(V, Ty);
 }
 
 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
-  Value *V = expandCodeFor(S->getOperand(),
-                           SE.getEffectiveSCEVType(S->getOperand()->getType()));
+  Value *V = expandCodeForImpl(
+      S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
+      false);
   return Builder.CreateSExt(V, Ty);
 }
 
 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands()-2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
       LHS = InsertNoopCastOfTo(LHS, Ty);
     }
-    Value *RHS = expandCodeFor(S->getOperand(i), Ty);
+    Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
     Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
     LHS = Sel;
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands()-2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
       LHS = InsertNoopCastOfTo(LHS, Ty);
     }
-    Value *RHS = expandCodeFor(S->getOperand(i), Ty);
+    Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
     Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
     LHS = Sel;
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
 Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands() - 2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
       LHS = InsertNoopCastOfTo(LHS, Ty);
     }
-    Value *RHS = expandCodeFor(S->getOperand(i), Ty);
+    Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
     Value *ICmp = Builder.CreateICmpSLT(LHS, RHS);
     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin");
     LHS = Sel;
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands() - 2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
       LHS = InsertNoopCastOfTo(LHS, Ty);
     }
-    Value *RHS = expandCodeFor(S->getOperand(i), Ty);
+    Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
     Value *ICmp = Builder.CreateICmpULT(LHS, RHS);
     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin");
     LHS = Sel;
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
-Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,
-                                   Instruction *IP) {
+Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
+                                       Instruction *IP, bool Root) {
   setInsertPoint(IP);
-  return expandCodeFor(SH, Ty);
+  Value *V = expandCodeForImpl(SH, Ty, Root);
+  return V;
 }
 
-Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
+Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
   // Expand the code for this SCEV.
   Value *V = expand(SH);
+
+  if (PreserveLCSSA) {
+    if (auto *Inst = dyn_cast<Instruction>(V)) {
+      // Create a temporary instruction to at the current insertion point, so we
+      // can hand it off to the helper to create LCSSA PHIs if required for the
+      // new use.
+      // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor)
+      // would accept a insertion point and return an LCSSA phi for that
+      // insertion point, so there is no need to insert & remove the temporary
+      // instruction.
+      Instruction *Tmp;
+      if (Inst->getType()->isIntegerTy())
+        Tmp = cast<Instruction>(Builder.CreateAdd(Inst, Inst));
+      else {
+        assert(Inst->getType()->isPointerTy());
+        Tmp = cast<Instruction>(Builder.CreateGEP(Inst, Builder.getInt32(1)));
+      }
+      V = fixupLCSSAFormFor(Tmp, 0);
+
+      // Clean up temporary instruction.
+      InsertedValues.erase(Tmp);
+      InsertedPostIncValues.erase(Tmp);
+      Tmp->eraseFromParent();
+    }
+  }
+
+  InsertedExpressions[std::make_pair(SH, &*Builder.GetInsertPoint())] = V;
   if (Ty) {
     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
            "non-trivial casts should be done with the SCEVs directly!");
     V = InsertNoopCastOfTo(V, Ty);
   }
   return V;
 }
 
Value *SCEVExpander::expand(const SCEV *S) {
   // the expression at this insertion point. If the mapped value happened to be
   // a postinc expansion, it could be reused by a non-postinc user, but only if
   // its insertion point was already at the head of the loop.
   InsertedExpressions[std::make_pair(S, InsertPt)] = V;
   return V;
 }
 
 void SCEVExpander::rememberInstruction(Value *I) {
+  auto DoInsert = [this](Value *V) {
     if (!PostIncLoops.empty())
-    InsertedPostIncValues.insert(I);
+      InsertedPostIncValues.insert(V);
     else
-    InsertedValues.insert(I);
+      InsertedValues.insert(V);
+  };
+  DoInsert(I);
+
+  if (!PreserveLCSSA)
+    return;
+
+  if (auto *Inst = dyn_cast<Instruction>(I)) {
+    // A new instruction has been added, which might introduce new uses outside
+    // a defining loop. Fix LCSSA from for each operand of the new instruction,
+    // if required.
+    for (unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd;
+         OpIdx++) {
+      auto *V = fixupLCSSAFormFor(Inst, OpIdx);
+      if (V != I)
+        DoInsert(V);
+    }
+  }
 }
 
 /// getOrInsertCanonicalInductionVariable - This method returns the
 /// canonical induction variable of the specified type for the specified
 /// loop (inserting one if there is none).  A canonical induction variable
 /// starts at zero and steps by one on each iteration.
 PHINode *
 SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
                                                     Type *Ty) {
   assert(Ty->isIntegerTy() && "Can only insert integer induction variables!");
 
   // Build a SCEV for {0,+,1}<L>.
   // Conservatively use FlagAnyWrap for now.
   const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0),
                                    SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap);
 
   // Emit code for it.
   SCEVInsertPointGuard Guard(Builder, this);
-  PHINode *V =
-      cast<PHINode>(expandCodeFor(H, nullptr,
-                                  &*L->getHeader()->getFirstInsertionPt()));
+  PHINode *V = cast<PHINode>(expandCodeForImpl(
+      H, nullptr, &*L->getHeader()->getFirstInsertionPt(), false));
 
   return V;
 }
 
 /// replaceCongruentIVs - Check for congruent phis in this loop header and
 /// replace them with their most canonical representative. Return the number of
 /// phis eliminated.
 ///
case SCEVPredicate::P_Wrap: {
     return expandWrapPredicate(AddRecPred, IP);
   }
   }
   llvm_unreachable("Unknown SCEV predicate type");
 }
 
 Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
                                           Instruction *IP) {
-  Value *Expr0 = expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP);
-  Value *Expr1 = expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP);
+  Value *Expr0 =
+      expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false);
+  Value *Expr1 =
+      expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false);
 
   Builder.SetInsertPoint(IP);
   auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
   return I;
 }
 
 Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
                                            Instruction *Loc, bool Signed) {
Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
 
   // The expression {Start,+,Step} has nusw/nssw if
   //   Step < 0, Start - |Step| * Backedge <= Start
   //   Step >= 0, Start + |Step| * Backedge > Start
   // and |Step| * Backedge doesn't unsigned overflow.
 
   IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
   Builder.SetInsertPoint(Loc);
-  Value *TripCountVal = expandCodeFor(ExitCount, CountTy, Loc);
+  Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc, false);
 
   IntegerType *Ty =
       IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
   Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty;
 
-  Value *StepValue = expandCodeFor(Step, Ty, Loc);
-  Value *NegStepValue = expandCodeFor(SE.getNegativeSCEV(Step), Ty, Loc);
-  Value *StartValue = expandCodeFor(Start, ARExpandTy, Loc);
+  Value *StepValue = expandCodeForImpl(Step, Ty, Loc, false);
+  Value *NegStepValue =
+      expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc, false);
+  Value *StartValue = expandCodeForImpl(Start, ARExpandTy, Loc, false);
 
   ConstantInt *Zero =
       ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits));
 
   Builder.SetInsertPoint(Loc);
   // Compute |Step|
   Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
   Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
for (auto Pred : Union->getPredicates()) {
     auto *NextCheck = expandCodeForPredicate(Pred, IP);
     Builder.SetInsertPoint(IP);
     Check = Builder.CreateOr(Check, NextCheck);
   }
 
   return Check;
 }
 
+Value *SCEVExpander::fixupLCSSAFormFor(Instruction *User, unsigned OpIdx) {
+  assert(PreserveLCSSA);
+  SmallVector<Instruction *, 1> ToUpdate;
+
+  auto *OpV = User->getOperand(OpIdx);
+  auto *OpI = dyn_cast<Instruction>(OpV);
+  if (!OpI)
+    return OpV;
+
+  Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent());
+  Loop *UseLoop = SE.LI.getLoopFor(User->getParent());
+  if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop))
+    return OpV;
+
+  ToUpdate.push_back(OpI);
+  formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE);
+  return User->getOperand(OpIdx);
+}
+
 namespace {
 // Search for a SCEV subexpression that is not safe to expand.  Any expression
 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
 // instruction, but the important thing is that we prove the denominator is
 // nonzero before expansion.
 //
 // IVUsers already checks that IV-derived expressions are safe. So this check is

llvm/unittests/Transforms/Utils/ScalarEvolutionExpanderTest.cpp

TEST_F(ScalarEvolutionExpanderTest, SCEVExpanderIsSafeToExpandAt) {
   auto *Limit = ConstantInt::get(T_int64, 1000);
   auto *Cond = cast<Instruction>(
       Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));
   Builder.CreateCondBr(Cond, L, Post);
   Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
   Phi->addIncoming(Add, L);
 
   Builder.SetInsertPoint(Post);
-  Builder.CreateRetVoid();
+  Instruction *Ret = Builder.CreateRetVoid();
 
   ScalarEvolution SE = buildSE(*F);
   const SCEV *S = SE.getSCEV(Phi);
   EXPECT_TRUE(isa<SCEVAddRecExpr>(S));
   const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
   EXPECT_TRUE(AR->isAffine());
   EXPECT_FALSE(isSafeToExpandAt(AR, Top->getTerminator(), SE));
   EXPECT_FALSE(isSafeToExpandAt(AR, LPh->getTerminator(), SE));
   EXPECT_TRUE(isSafeToExpandAt(AR, L->getTerminator(), SE));
   EXPECT_TRUE(isSafeToExpandAt(AR, Post->getTerminator(), SE));
+
+  EXPECT_TRUE(LI->getLoopFor(L)->isLCSSAForm(*DT));
+  SCEVExpander Exp(SE, M.getDataLayout(), "expander");
+  Exp.expandCodeFor(SE.getSCEV(Add), nullptr, Ret);
+  EXPECT_TRUE(LI->getLoopFor(L)->isLCSSAForm(*DT));
 }
 
 // Check that SCEV expander does not use the nuw instruction
 // for expansion.
 TEST_F(ScalarEvolutionExpanderTest, SCEVExpanderNUW) {
   /*
    * Create the following code:
    * func(i64 %a)