diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -61,6 +61,10 @@ bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA); +Value *getLCSSAPhisForUser(SmallVectorImpl &Worklist, + Instruction *User, DominatorTree &DT, LoopInfo &LI, + ScalarEvolution *SE); + /// Ensures LCSSA form for every instruction from the Worklist in the scope of /// innermost containing loop. /// diff --git a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h --- a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h +++ b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h @@ -1,4 +1,4 @@ -//=== Transforms/Utils/ScalarEvolutionExpander.h - SCEV Expander *- C++ -*-===// +//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -49,6 +49,8 @@ // New instructions receive a name to identify them with the current pass. const char* IVName; + bool PreserveLCSSA; + // InsertedExpressions caches Values for reuse, so must track RAUW. DenseMap, TrackingVH> InsertedExpressions; @@ -143,9 +145,10 @@ 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)) { #ifndef NDEBUG DebugType = ""; @@ -204,14 +207,14 @@ /// 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); + Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I, + bool Root = true); /// Insert code to directly compute the specified SCEV expression into the /// program. The inserted 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, bool Root = false); /// Generates a code sequence that evaluates this predicate. The inserted /// instructions will be at position \p Loc. The result will be of type i1 @@ -409,6 +412,8 @@ Instruction *Pos, PHINode *LoopPhi); void fixupInsertPoints(Instruction *I); + + Value *fixupLCSSAFormFor(Value *V); }; } diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp --- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -5460,8 +5460,8 @@ // we can remove them after we are done working. SmallVector 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 @@ -5720,7 +5720,7 @@ if (EnablePhiElim && L->isLoopSimplifyForm()) { SmallVector 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 diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp --- a/llvm/lib/Transforms/Utils/LCSSA.cpp +++ b/llvm/lib/Transforms/Utils/LCSSA.cpp @@ -59,7 +59,8 @@ #ifdef EXPENSIVE_CHECKS static bool VerifyLoopLCSSA = true; #else -static bool VerifyLoopLCSSA = false; +// static bool VerifyLoopLCSSA = false; +static bool VerifyLoopLCSSA = true; #endif static cl::opt VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), @@ -72,6 +73,220 @@ return is_contained(ExitBlocks, BB); } +Value *llvm::getLCSSAPhisForUser(SmallVectorImpl &Worklist, + Instruction *User, DominatorTree &DT, + LoopInfo &LI, ScalarEvolution *SE) { + SmallVector UsesToRewrite; + SmallSetVector PHIsToRemove; + PredIteratorCache PredCache; + bool Changed = false; + + // Cache the Loop ExitBlocks across this loop. We expect to get a lot of + // instructions within the same loops, computing the exit blocks is + // expensive, and we're not mutating the loop structure. + SmallDenseMap> LoopExitBlocks; + Value *Result = nullptr; + while (!Worklist.empty()) { + UsesToRewrite.clear(); + + Instruction *I = Worklist.pop_back_val(); + assert(!I->getType()->isTokenTy() && "Tokens shouldn't be in the worklist"); + BasicBlock *InstBB = I->getParent(); + Loop *L = LI.getLoopFor(InstBB); + assert(L && "Instruction belongs to a BB that's not part of a loop"); + if (!LoopExitBlocks.count(L)) + L->getExitBlocks(LoopExitBlocks[L]); + assert(LoopExitBlocks.count(L)); + const SmallVectorImpl &ExitBlocks = LoopExitBlocks[L]; + + if (ExitBlocks.empty()) + continue; + + for (Use &U : I->uses()) { + Instruction *User = cast(U.getUser()); + BasicBlock *UserBB = User->getParent(); + if (auto *PN = dyn_cast(User)) + UserBB = PN->getIncomingBlock(U); + + if (InstBB != UserBB && !L->contains(UserBB)) + UsesToRewrite.push_back(&U); + } + if ((User->getParent() == InstBB || L->contains(User->getParent())) && + UsesToRewrite.empty()) + continue; + + ++NumLCSSA; // We are applying the transformation + + // Invoke instructions are special in that their result value is not + // available along their unwind edge. The code below tests to see whether + // DomBB dominates the value, so adjust DomBB to the normal destination + // block, which is effectively where the value is first usable. + BasicBlock *DomBB = InstBB; + if (auto *Inv = dyn_cast(I)) + DomBB = Inv->getNormalDest(); + + DomTreeNode *DomNode = DT.getNode(DomBB); + + SmallVector AddedPHIs; + SmallVector PostProcessPHIs; + + SmallVector InsertedPHIs; + SSAUpdater SSAUpdate(&InsertedPHIs); + SSAUpdate.Initialize(I->getType(), I->getName()); + + // Force re-computation of I, as some users now need to use the new PHI + // node. + if (SE) + SE->forgetValue(I); + + // Insert the LCSSA phi's into all of the exit blocks dominated by the + // value, and add them to the Phi's map. + for (BasicBlock *ExitBB : ExitBlocks) { + if (!DT.dominates(DomNode, DT.getNode(ExitBB))) + continue; + + // If we already inserted something for this BB, don't reprocess it. + if (SSAUpdate.HasValueForBlock(ExitBB)) + continue; + + PHINode *PN = nullptr; + for (PHINode &P : ExitBB->phis()) { + if (P.getNumIncomingValues() != 1) + continue; + if (P.getIncomingValue(0) == I) { + PN = &P; + break; + } + } + if (!PN) { + PN = PHINode::Create(I->getType(), PredCache.size(ExitBB), + I->getName() + ".lcssa", &ExitBB->front()); + // Get the debug location from the original instruction. + PN->setDebugLoc(I->getDebugLoc()); + // Add inputs from inside the loop for this PHI. + for (BasicBlock *Pred : PredCache.get(ExitBB)) { + PN->addIncoming(I, Pred); + + // If the exit block has a predecessor not within the loop, arrange + // for the incoming value use corresponding to that predecessor to be + // rewritten in terms of a different LCSSA PHI. + if (!L->contains(Pred)) + UsesToRewrite.push_back( + &PN->getOperandUse(PN->getOperandNumForIncomingValue( + PN->getNumIncomingValues() - 1))); + } + } + + AddedPHIs.push_back(PN); + + // Remember that this phi makes the value alive in this block. + SSAUpdate.AddAvailableValue(ExitBB, PN); + + // LoopSimplify might fail to simplify some loops (e.g. when indirect + // branches are involved). In such situations, it might happen that an + // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we + // create PHIs in such an exit block, we are also inserting PHIs into L2's + // header. This could break LCSSA form for L2 because these inserted PHIs + // can also have uses outside of L2. Remember all PHIs in such situation + // as to revisit than later on. FIXME: Remove this if indirectbr support + // into LoopSimplify gets improved. + if (auto *OtherLoop = LI.getLoopFor(ExitBB)) + if (!L->contains(OtherLoop)) + PostProcessPHIs.push_back(PN); + } + + // assert(!isa(User)); + BasicBlock *UserBB = User->getParent(); + + if (AddedPHIs.size() == 1) + Result = AddedPHIs[0]; + else + Result = SSAUpdate.GetValueInMiddleOfBlock(UserBB); + + // Rewrite all uses outside the loop in terms of the new PHIs we just + // inserted. + for (Use *UseToRewrite : UsesToRewrite) { + // If this use is in an exit block, rewrite to use the newly inserted PHI. + // This is required for correctness because SSAUpdate doesn't handle uses + // in the same block. It assumes the PHI we inserted is at the end of the + // block. + Instruction *User = cast(UseToRewrite->getUser()); + BasicBlock *UserBB = User->getParent(); + if (auto *PN = dyn_cast(User)) + UserBB = PN->getIncomingBlock(*UseToRewrite); + + if (isa(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { + UseToRewrite->set(&UserBB->front()); + continue; + } + + // If we added a single PHI, it must dominate all uses and we can directly + // rename it. + if (AddedPHIs.size() == 1) { + UseToRewrite->set(AddedPHIs[0]); + continue; + } + + // Otherwise, do full PHI insertion. + SSAUpdate.RewriteUse(*UseToRewrite); + } + SmallVector DbgValues; + llvm::findDbgValues(DbgValues, I); + + // Update pre-existing debug value uses that reside outside the loop. + auto &Ctx = I->getContext(); + for (auto DVI : DbgValues) { + BasicBlock *UserBB = DVI->getParent(); + if (InstBB == UserBB || L->contains(UserBB)) + continue; + // We currently only handle debug values residing in blocks that were + // traversed while rewriting the uses. If we inserted just a single PHI, + // we will handle all relevant debug values. + Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0] + : SSAUpdate.FindValueForBlock(UserBB); + if (V) + DVI->setOperand(0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(V))); + } + + // SSAUpdater might have inserted phi-nodes inside other loops. We'll need + // to post-process them to keep LCSSA form. + for (PHINode *InsertedPN : InsertedPHIs) { + if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent())) + if (!L->contains(OtherLoop)) + PostProcessPHIs.push_back(InsertedPN); + } + + // Post process PHI instructions that were inserted into another disjoint + // loop and update their exits properly. + for (auto *PostProcessPN : PostProcessPHIs) + if (!PostProcessPN->use_empty()) + Worklist.push_back(PostProcessPN); + + // Keep track of PHI nodes that we want to remove because they did not have + // any uses rewritten. If the new PHI is used, store it so that we can + // try to propagate dbg.value intrinsics to it. + SmallVector NeedDbgValues; + for (PHINode *PN : AddedPHIs) + if (PN->use_empty() && Result != PN) + PHIsToRemove.insert(PN); + else + NeedDbgValues.push_back(PN); + insertDebugValuesForPHIs(InstBB, NeedDbgValues); + Changed = true; + } + // Remove PHI nodes that did not have any uses rewritten. We need to redo the + // use_empty() check here, because even if the PHI node wasn't used when added + // to PHIsToRemove, later added PHI nodes can be using it. This cleanup is + // not guaranteed to handle trees/cycles of PHI nodes that only are used by + // each other. Such situations has only been noticed when the input IR + // contains unreachable code, and leaving some extra redundant PHI nodes in + // such situations is considered a minor problem. + for (PHINode *PN : PHIsToRemove) + if (PN->use_empty()) + PN->eraseFromParent(); + return Result; +} + /// For every instruction from the worklist, check to see if it has any uses /// that are outside the current loop. If so, insert LCSSA PHI nodes and /// rewrite the uses. @@ -110,8 +325,9 @@ if (auto *PN = dyn_cast(User)) UserBB = PN->getIncomingBlock(U); - if (InstBB != UserBB && !L->contains(UserBB)) + if (InstBB != UserBB && !L->contains(UserBB)) { UsesToRewrite.push_back(&U); + } } // If there are no uses outside the loop, exit with no change. @@ -152,21 +368,32 @@ if (SSAUpdate.HasValueForBlock(ExitBB)) continue; - PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB), - I->getName() + ".lcssa", &ExitBB->front()); - // Get the debug location from the original instruction. - PN->setDebugLoc(I->getDebugLoc()); - // Add inputs from inside the loop for this PHI. - for (BasicBlock *Pred : PredCache.get(ExitBB)) { - PN->addIncoming(I, Pred); - - // If the exit block has a predecessor not within the loop, arrange for - // the incoming value use corresponding to that predecessor to be - // rewritten in terms of a different LCSSA PHI. - if (!L->contains(Pred)) - UsesToRewrite.push_back( - &PN->getOperandUse(PN->getOperandNumForIncomingValue( - PN->getNumIncomingValues() - 1))); + PHINode *PN = nullptr; + for (PHINode &P : ExitBB->phis()) { + if (P.getNumIncomingValues() != 1) + continue; + if (P.getIncomingValue(0) == I) { + PN = &P; + break; + } + } + if (!PN) { + PN = PHINode::Create(I->getType(), PredCache.size(ExitBB), + I->getName() + ".lcssa", &ExitBB->front()); + // Get the debug location from the original instruction. + PN->setDebugLoc(I->getDebugLoc()); + // Add inputs from inside the loop for this PHI. + for (BasicBlock *Pred : PredCache.get(ExitBB)) { + PN->addIncoming(I, Pred); + + // If the exit block has a predecessor not within the loop, arrange + // for the incoming value use corresponding to that predecessor to be + // rewritten in terms of a different LCSSA PHI. + if (!L->contains(Pred)) + UsesToRewrite.push_back( + &PN->getOperandUse(PN->getOperandNumForIncomingValue( + PN->getNumIncomingValues() - 1))); + } } AddedPHIs.push_back(PN); @@ -199,9 +426,20 @@ if (auto *PN = dyn_cast(User)) UserBB = PN->getIncomingBlock(*UseToRewrite); - if (isa(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { - UseToRewrite->set(&UserBB->front()); - continue; + if (isExitBlock(UserBB, ExitBlocks)) { + Instruction *PN = &UserBB->front(); + for (PHINode &P : UserBB->phis()) { + if (P.getNumIncomingValues() != 1) + continue; + if (P.getIncomingValue(0) == I) { + PN = &P; + break; + } + } + if (PN) { + UseToRewrite->set(PN); + continue; + } } // If we added a single PHI, it must dominate all uses and we can directly diff --git a/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp b/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp --- a/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp +++ b/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp @@ -26,6 +26,7 @@ #include "llvm/IR/PatternMatch.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/LoopUtils.h" using namespace llvm; using namespace PatternMatch; @@ -1263,7 +1264,7 @@ assert(L->getLoopPreheader() && "Can't expand add recurrences without a loop preheader!"); Value *StartV = expandCodeFor(Normalized->getStart(), ExpandTy, - L->getLoopPreheader()->getTerminator()); + L->getLoopPreheader()->getTerminator(), false); // StartV must have been be inserted into L's preheader to dominate the new // phi. @@ -1281,7 +1282,7 @@ if (useSubtract) Step = SE.getNegativeSCEV(Step); // Expand the step somewhere that dominates the loop header. - Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front()); + Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front(), 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 @@ -1427,7 +1428,7 @@ { // Expand the step somewhere that dominates the loop header. SCEVInsertPointGuard Guard(Builder, this); - StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front()); + StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front(), false); } Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); } @@ -1518,7 +1519,7 @@ BasicBlock::iterator NewInsertPt = findInsertPointAfter(cast(V), Builder.GetInsertBlock()); V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr, - &*NewInsertPt); + &*NewInsertPt, false); return V; } @@ -1758,15 +1759,30 @@ return LHS; } -Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty, - Instruction *IP) { +Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty, Instruction *IP, + bool Root) { setInsertPoint(IP); - return expandCodeFor(SH, Ty); + Value *V = expandCodeFor(SH, Ty, Root); + return V; } -Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) { +Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty, bool Root) { // Expand the code for this SCEV. - Value *V = expand(SH); + Value *V = fixupLCSSAFormFor(expand(SH)); + if (Root) { + if (auto *Inst = dyn_cast(V)) { + SmallVector ToUpdate; + if (PreserveLCSSA && SE.LI.getLoopFor(Inst->getParent())) { + ToUpdate.push_back(Inst); + auto *LCSSA = getLCSSAPhisForUser(ToUpdate, &*Builder.GetInsertPoint(), + SE.DT, SE.LI, &SE); + if (LCSSA) + V = LCSSA; + } + } + } + + 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!"); @@ -1915,6 +1931,8 @@ InsertedPostIncValues.insert(I); else InsertedValues.insert(I); + + fixupLCSSAFormFor(I); } /// getOrInsertCanonicalInductionVariable - This method returns the @@ -1934,7 +1952,7 @@ // Emit code for it. SCEVInsertPointGuard Guard(Builder, this); PHINode *V = - cast(expandCodeFor(H, nullptr, &L->getHeader()->front())); + cast(expandCodeFor(H, nullptr, &L->getHeader()->front(), false)); return V; } @@ -2227,8 +2245,10 @@ 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 = + expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP, false); + Value *Expr1 = + expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP, false); Builder.SetInsertPoint(IP); auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check"); @@ -2260,15 +2280,15 @@ IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits); Builder.SetInsertPoint(Loc); - Value *TripCountVal = expandCodeFor(ExitCount, CountTy, Loc); + Value *TripCountVal = expandCodeFor(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 = expandCodeFor(Step, Ty, Loc, false); + Value *NegStepValue = expandCodeFor(SE.getNegativeSCEV(Step), Ty, Loc, false); + Value *StartValue = expandCodeFor(Start, ARExpandTy, Loc, false); ConstantInt *Zero = ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits)); @@ -2372,6 +2392,24 @@ return Check; } +Value *SCEVExpander::fixupLCSSAFormFor(Value *V) { + if (!PreserveLCSSA) + return V; + + if (auto *Inst = dyn_cast(V)) { + SmallVector ToUpdate; + for (Value *Op : Inst->operands()) { + auto *OpI = dyn_cast(Op); + if (!OpI || !SE.LI.getLoopFor(OpI->getParent())) + continue; + ToUpdate.push_back(OpI); + formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE); + ToUpdate.clear(); + } + } + return V; +} + namespace { // Search for a SCEV subexpression that is not safe to expand. Any expression // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely diff --git a/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-2.ll b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-2.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-2.ll @@ -0,0 +1,85 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -indvars -S -indvars -verify-loop-lcssa %s | FileCheck %s + +; Make sure SCEVExpander does not crash and introduce unnecessary LCSSA PHI nodes. + +define void @ReadCharMetrics() { +; CHECK-LABEL: @ReadCharMetrics( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LAND_LHS_TRUE:%.*]] +; CHECK: land.lhs.true: +; CHECK-NEXT: br label [[WHILE_COND22:%.*]] +; CHECK: while.cond22: +; CHECK-NEXT: br i1 false, label [[WHILE_COND22]], label [[WHILE_COND29_PREHEADER:%.*]] +; CHECK: while.cond29.preheader: +; CHECK-NEXT: br label [[WHILE_BODY35:%.*]] +; CHECK: while.body35: +; CHECK-NEXT: [[I_1107:%.*]] = phi i32 [ [[I_9:%.*]], [[IF_END224:%.*]] ], [ undef, [[WHILE_COND29_PREHEADER]] ] +; CHECK-NEXT: br label [[WHILE_COND192:%.*]] +; CHECK: while.cond192: +; CHECK-NEXT: switch i8 undef, label [[WHILE_BODY205:%.*]] [ +; CHECK-NEXT: i8 59, label [[WHILE_COND215_PREHEADER:%.*]] +; CHECK-NEXT: i8 10, label [[IF_END224_LOOPEXIT1:%.*]] +; CHECK-NEXT: ] +; CHECK: while.cond215.preheader: +; CHECK-NEXT: br label [[WHILE_COND215:%.*]] +; CHECK: while.body205: +; CHECK-NEXT: br label [[WHILE_COND192]] +; CHECK: while.cond215: +; CHECK-NEXT: [[I_8_IN:%.*]] = phi i32 [ [[I_8:%.*]], [[WHILE_COND215]] ], [ [[I_1107]], [[WHILE_COND215_PREHEADER]] ] +; CHECK-NEXT: [[I_8]] = add nsw i32 [[I_8_IN]], 1 +; CHECK-NEXT: [[IDXPROM216:%.*]] = sext i32 [[I_8]] to i64 +; CHECK-NEXT: [[ARRAYIDX217:%.*]] = getelementptr inbounds [512 x i8], [512 x i8]* undef, i64 0, i64 [[IDXPROM216]] +; CHECK-NEXT: br i1 false, label [[WHILE_COND215]], label [[IF_END224_LOOPEXIT:%.*]] +; CHECK: if.end224.loopexit: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[I_1107]], 1 +; CHECK-NEXT: br label [[IF_END224]] +; CHECK: if.end224.loopexit1: +; CHECK-NEXT: br label [[IF_END224]] +; CHECK: if.end224: +; CHECK-NEXT: [[I_9]] = phi i32 [ [[TMP0]], [[IF_END224_LOOPEXIT]] ], [ [[I_1107]], [[IF_END224_LOOPEXIT1]] ] +; CHECK-NEXT: br i1 true, label [[WHILE_END225:%.*]], label [[WHILE_BODY35]] +; CHECK: while.end225: +; CHECK-NEXT: br label [[LAND_LHS_TRUE]] +; +entry: + br label %land.lhs.true + +land.lhs.true: ; preds = %while.end225, %entry + br label %while.cond22 + +while.cond22: ; preds = %while.cond22, %land.lhs.true + br i1 undef, label %while.cond22, label %while.cond29.preheader + +while.cond29.preheader: ; preds = %while.cond22 + br label %while.body35 + +while.body35: ; preds = %if.end224, %while.cond29.preheader + %i.1107 = phi i32 [ %i.9, %if.end224 ], [ undef, %while.cond29.preheader ] + br label %while.cond192 + +while.cond192: ; preds = %while.body205, %while.body35 + %i.7 = phi i32 [ %i.1107, %while.body35 ], [ %inc206, %while.body205 ] + switch i8 undef, label %while.body205 [ + i8 59, label %while.cond215 + i8 10, label %if.end224 + ] + +while.body205: ; preds = %while.cond192 + %inc206 = add nsw i32 %i.7, 1 + br label %while.cond192 + +while.cond215: ; preds = %while.cond215, %while.cond192 + %i.8.in = phi i32 [ %i.8, %while.cond215 ], [ %i.7, %while.cond192 ] + %i.8 = add nsw i32 %i.8.in, 1 + %idxprom216 = sext i32 %i.8 to i64 + %arrayidx217 = getelementptr inbounds [512 x i8], [512 x i8]* undef, i64 0, i64 %idxprom216 + br i1 undef, label %while.cond215, label %if.end224 + +if.end224: ; preds = %while.cond215, %while.cond192 + %i.9 = phi i32 [ %i.8, %while.cond215 ], [ %i.7, %while.cond192 ] + br i1 undef, label %while.end225, label %while.body35 + +while.end225: ; preds = %if.end224 + br label %land.lhs.true +} diff --git a/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-3.ll b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-3.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-3.ll @@ -0,0 +1,58 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -indvars -S %s | FileCheck %s + +; Make sure SCEVExpander does not crash and introduce unnecessary LCSSA PHI nodes. + +define void @readcells() local_unnamed_addr #0 { +; CHECK-LABEL: @readcells( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[WHILE_BODY:%.*]] +; CHECK: while.body: +; CHECK-NEXT: br label [[FOR_BODY1208:%.*]] +; CHECK: for.body1208: +; CHECK-NEXT: [[M_0804:%.*]] = phi i32 [ 1, [[WHILE_BODY]] ], [ [[INC1499:%.*]], [[FOR_INC1498:%.*]] ] +; CHECK-NEXT: [[CMP1358:%.*]] = icmp eq i32 undef, 0 +; CHECK-NEXT: br i1 [[CMP1358]], label [[IF_THEN1360:%.*]], label [[FOR_INC1498]] +; CHECK: if.then1360: +; CHECK-NEXT: [[M_0804_LCSSA:%.*]] = phi i32 [ [[M_0804]], [[FOR_BODY1208]] ] +; CHECK-NEXT: br label [[FOR_COND1390:%.*]] +; CHECK: for.cond1390: +; CHECK-NEXT: br i1 false, label [[FOR_BODY1394:%.*]], label [[FOR_END1469:%.*]] +; CHECK: for.body1394: +; CHECK-NEXT: br label [[FOR_COND1390]] +; CHECK: for.end1469: +; CHECK-NEXT: store i32 [[M_0804_LCSSA]], i32* undef, align 4 +; CHECK-NEXT: br label [[WHILE_BODY]] +; CHECK: for.inc1498: +; CHECK-NEXT: [[INC1499]] = add nuw nsw i32 [[M_0804]], 1 +; CHECK-NEXT: br label [[FOR_BODY1208]] +; +entry: + br label %while.body + +while.body: ; preds = %for.end1469, %entry + br label %for.body1208 + +for.body1208: ; preds = %for.inc1498, %while.body + %m.0804 = phi i32 [ 1, %while.body ], [ %inc1499, %for.inc1498 ] + %cmp1358 = icmp eq i32 undef, 0 + br i1 %cmp1358, label %if.then1360, label %for.inc1498 + +if.then1360: ; preds = %for.body1208 + br label %for.cond1390 + +for.cond1390: ; preds = %for.body1394, %if.then1360 + %m.2.in = phi i32 [ %m.0804, %if.then1360 ], [ 0, %for.body1394 ] + br i1 undef, label %for.body1394, label %for.end1469 + +for.body1394: ; preds = %for.cond1390 + br label %for.cond1390 + +for.end1469: ; preds = %for.cond1390 + store i32 %m.2.in, i32* undef, align 4 + br label %while.body + +for.inc1498: ; preds = %for.body1208 + %inc1499 = add nuw nsw i32 %m.0804, 1 + br label %for.body1208 +} diff --git a/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-4.ll b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-4.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa-4.ll @@ -0,0 +1,115 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -indvars -S %s | FileCheck %s + +; Make sure SCEVExpander does not crash and introduce unnecessary LCSSA PHI nodes. + +%struct.locbox.6.21.126.201.276.411.576.711.876.981.1086.1221.1266.1341.1416.1686.1716.1746.1776.1821.1881.1896.1911.1926.1941.1956.2001.2076.2091.2136.2286.2526.2541.2586.2661.2736.2901.3066.3756.3771.3786.3846.4020 = type { i32, i32, i32, i32 } + +define void @readcells() { +; CHECK-LABEL: @readcells( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[WHILE_BODY:%.*]] +; CHECK: while.body: +; CHECK-NEXT: br label [[FOR_COND1204_PREHEADER:%.*]] +; CHECK: for.cond1204.preheader: +; CHECK-NEXT: br i1 true, label [[IF_THEN1504:%.*]], label [[FOR_BODY1208_LR_PH:%.*]] +; CHECK: for.body1208.lr.ph: +; CHECK-NEXT: br label [[FOR_BODY1208:%.*]] +; CHECK: for.body1208: +; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ undef, [[FOR_BODY1208_LR_PH]] ], [ [[TMP1:%.*]], [[FOR_INC1498:%.*]] ] +; CHECK-NEXT: [[M_0804:%.*]] = phi i32 [ 1, [[FOR_BODY1208_LR_PH]] ], [ [[INC1499:%.*]], [[FOR_INC1498]] ] +; CHECK-NEXT: [[IDXPROM1212:%.*]] = zext i32 [[M_0804]] to i64 +; CHECK-NEXT: [[CMP1215:%.*]] = icmp eq i32 0, undef +; CHECK-NEXT: [[YPOS1223:%.*]] = getelementptr inbounds [[STRUCT_LOCBOX_6_21_126_201_276_411_576_711_876_981_1086_1221_1266_1341_1416_1686_1716_1746_1776_1821_1881_1896_1911_1926_1941_1956_2001_2076_2091_2136_2286_2526_2541_2586_2661_2736_2901_3066_3756_3771_3786_3846_4020:%.*]], %struct.locbox.6.21.126.201.276.411.576.711.876.981.1086.1221.1266.1341.1416.1686.1716.1746.1776.1821.1881.1896.1911.1926.1941.1956.2001.2076.2091.2136.2286.2526.2541.2586.2661.2736.2901.3066.3756.3771.3786.3846.4020* undef, i64 [[IDXPROM1212]], i32 1 +; CHECK-NEXT: br i1 [[CMP1215]], label [[IF_THEN1217:%.*]], label [[IF_ELSE1351:%.*]] +; CHECK: if.then1217: +; CHECK-NEXT: [[M_0804_LCSSA:%.*]] = phi i32 [ [[M_0804]], [[FOR_BODY1208]] ] +; CHECK-NEXT: br label [[FOR_COND1247:%.*]] +; CHECK: for.cond1247: +; CHECK-NEXT: [[M_1_IN:%.*]] = phi i32 [ [[M_0804_LCSSA]], [[IF_THEN1217]] ], [ [[M_1:%.*]], [[IF_THEN1260:%.*]] ] +; CHECK-NEXT: [[M_1]] = add nuw nsw i32 [[M_1_IN]], 1 +; CHECK-NEXT: br label [[FOR_BODY1251:%.*]] +; CHECK: for.body1251: +; CHECK-NEXT: [[IDXPROM1255:%.*]] = zext i32 [[M_1]] to i64 +; CHECK-NEXT: [[XPOS1257:%.*]] = getelementptr inbounds [[STRUCT_LOCBOX_6_21_126_201_276_411_576_711_876_981_1086_1221_1266_1341_1416_1686_1716_1746_1776_1821_1881_1896_1911_1926_1941_1956_2001_2076_2091_2136_2286_2526_2541_2586_2661_2736_2901_3066_3756_3771_3786_3846_4020]], %struct.locbox.6.21.126.201.276.411.576.711.876.981.1086.1221.1266.1341.1416.1686.1716.1746.1776.1821.1881.1896.1911.1926.1941.1956.2001.2076.2091.2136.2286.2526.2541.2586.2661.2736.2901.3066.3756.3771.3786.3846.4020* undef, i64 [[IDXPROM1255]], i32 0 +; CHECK-NEXT: br i1 false, label [[IF_THEN1260]], label [[FOR_END1326:%.*]] +; CHECK: if.then1260: +; CHECK-NEXT: br label [[FOR_COND1247]] +; CHECK: for.end1326: +; CHECK-NEXT: br label [[IF_END1824:%.*]] +; CHECK: if.else1351: +; CHECK-NEXT: [[CMP1358:%.*]] = icmp eq i32 undef, 0 +; CHECK-NEXT: br i1 [[CMP1358]], label [[IF_THEN1360:%.*]], label [[FOR_INC1498]] +; CHECK: if.then1360: +; CHECK-NEXT: [[DOTLCSSA2:%.*]] = phi i32 [ [[TMP0]], [[IF_ELSE1351]] ] +; CHECK-NEXT: [[M_0804_LCSSA1:%.*]] = phi i32 [ [[M_0804]], [[IF_ELSE1351]] ] +; CHECK-NEXT: [[CMP1392:%.*]] = icmp slt i32 [[M_0804_LCSSA1]], [[DOTLCSSA2]] +; CHECK-NEXT: unreachable +; CHECK: for.inc1498: +; CHECK-NEXT: [[INC1499]] = add nuw nsw i32 [[M_0804]], 1 +; CHECK-NEXT: [[TMP1]] = load i32, i32* undef, align 8 +; CHECK-NEXT: br label [[FOR_BODY1208]] +; CHECK: if.then1504: +; CHECK-NEXT: unreachable +; CHECK: if.end1824: +; CHECK-NEXT: br label [[WHILE_BODY]] +; +entry: + br label %while.body + +while.body: ; preds = %if.end1824, %entry + br label %for.cond1204.preheader + +for.cond1204.preheader: ; preds = %while.body + br i1 undef, label %if.then1504, label %for.body1208.lr.ph + +for.body1208.lr.ph: ; preds = %for.cond1204.preheader + br label %for.body1208 + +for.body1208: ; preds = %for.inc1498, %for.body1208.lr.ph + %0 = phi i32 [ undef, %for.body1208.lr.ph ], [ %1, %for.inc1498 ] + %m.0804 = phi i32 [ 1, %for.body1208.lr.ph ], [ %inc1499, %for.inc1498 ] + %idxprom1212 = zext i32 %m.0804 to i64 + %cmp1215 = icmp eq i32 0, undef + %ypos1223 = getelementptr inbounds %struct.locbox.6.21.126.201.276.411.576.711.876.981.1086.1221.1266.1341.1416.1686.1716.1746.1776.1821.1881.1896.1911.1926.1941.1956.2001.2076.2091.2136.2286.2526.2541.2586.2661.2736.2901.3066.3756.3771.3786.3846.4020, %struct.locbox.6.21.126.201.276.411.576.711.876.981.1086.1221.1266.1341.1416.1686.1716.1746.1776.1821.1881.1896.1911.1926.1941.1956.2001.2076.2091.2136.2286.2526.2541.2586.2661.2736.2901.3066.3756.3771.3786.3846.4020* undef, i64 %idxprom1212, i32 1 + br i1 %cmp1215, label %if.then1217, label %if.else1351 + +if.then1217: ; preds = %for.body1208 + br label %for.cond1247 + +for.cond1247: ; preds = %if.then1260, %if.then1217 + %m.1.in = phi i32 [ %m.0804, %if.then1217 ], [ %m.1, %if.then1260 ] + %m.1 = add nuw nsw i32 %m.1.in, 1 + %cmp1249 = icmp slt i32 %m.1.in, %0 + br label %for.body1251 + +for.body1251: ; preds = %for.cond1247 + %idxprom1255 = zext i32 %m.1 to i64 + %xpos1257 = getelementptr inbounds %struct.locbox.6.21.126.201.276.411.576.711.876.981.1086.1221.1266.1341.1416.1686.1716.1746.1776.1821.1881.1896.1911.1926.1941.1956.2001.2076.2091.2136.2286.2526.2541.2586.2661.2736.2901.3066.3756.3771.3786.3846.4020, %struct.locbox.6.21.126.201.276.411.576.711.876.981.1086.1221.1266.1341.1416.1686.1716.1746.1776.1821.1881.1896.1911.1926.1941.1956.2001.2076.2091.2136.2286.2526.2541.2586.2661.2736.2901.3066.3756.3771.3786.3846.4020* undef, i64 %idxprom1255, i32 0 + br i1 undef, label %if.then1260, label %for.end1326 + +if.then1260: ; preds = %for.body1251 + br label %for.cond1247 + +for.end1326: ; preds = %for.body1251 + br label %if.end1824 + +if.else1351: ; preds = %for.body1208 + %cmp1358 = icmp eq i32 undef, 0 + br i1 %cmp1358, label %if.then1360, label %for.inc1498 + +if.then1360: ; preds = %if.else1351 + %cmp1392 = icmp slt i32 %m.0804, %0 + unreachable + +for.inc1498: ; preds = %if.else1351 + %inc1499 = add nuw nsw i32 %m.0804, 1 + %1 = load i32, i32* undef, align 8 + br label %for.body1208 + +if.then1504: ; preds = %for.cond1204.preheader + unreachable + +if.end1824: ; preds = %for.end1326 + br label %while.body +} diff --git a/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa.ll b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/IndVarSimplify/scev-expander-lcssa.ll @@ -0,0 +1,67 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -indvars -S %s | FileCheck %s + +define void @asm_noperands() { +; CHECK-LABEL: @asm_noperands( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 undef, label [[FOR_COND_PREHEADER:%.*]], label [[RETURN:%.*]] +; CHECK: for.cond.preheader: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: switch i16 undef, label [[RETURN_LOOPEXIT1:%.*]] [ +; CHECK-NEXT: i16 41, label [[FOR_END:%.*]] +; CHECK-NEXT: i16 43, label [[FOR_COND]] +; CHECK-NEXT: ] +; CHECK: for.end: +; CHECK-NEXT: [[I_0_LCSSA2:%.*]] = phi i32 [ undef, [[FOR_COND]] ] +; CHECK-NEXT: [[CMP8243:%.*]] = icmp sgt i32 [[I_0_LCSSA2]], 0 +; CHECK-NEXT: br i1 [[CMP8243]], label [[FOR_BODY84_PREHEADER:%.*]], label [[RETURN]] +; CHECK: for.body84.preheader: +; CHECK-NEXT: br label [[FOR_BODY84:%.*]] +; CHECK: for.body84: +; CHECK-NEXT: [[I_144:%.*]] = phi i32 [ [[INC:%.*]], [[IF_END106:%.*]] ], [ 0, [[FOR_BODY84_PREHEADER]] ] +; CHECK-NEXT: br i1 false, label [[IF_END106]], label [[RETURN_LOOPEXIT:%.*]] +; CHECK: if.end106: +; CHECK-NEXT: [[INC]] = add nuw nsw i32 [[I_144]], 1 +; CHECK-NEXT: [[CMP82:%.*]] = icmp slt i32 [[INC]], [[I_0_LCSSA2]] +; CHECK-NEXT: br i1 [[CMP82]], label [[FOR_BODY84]], label [[RETURN_LOOPEXIT]] +; CHECK: return.loopexit: +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return.loopexit1: +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: ret void +; +entry: + br i1 undef, label %for.cond, label %return + +for.cond: ; preds = %for.cond, %entry + %i.0 = phi i32 [ %sub, %for.cond ], [ undef, %entry ] + %sub = add nsw i32 %i.0, -1 + switch i16 undef, label %return [ + i16 41, label %for.end + i16 43, label %for.cond + ] + +for.end: ; preds = %for.cond + %cmp8243 = icmp sgt i32 %i.0, 0 + br i1 %cmp8243, label %for.body84, label %return + +for.body84: ; preds = %if.end106, %for.end + %i.144 = phi i32 [ %inc, %if.end106 ], [ 0, %for.end ] + br i1 undef, label %if.end106, label %return + +if.end106: ; preds = %for.body84 + %inc = add nuw nsw i32 %i.144, 1 + %cmp82 = icmp slt i32 %inc, %i.0 + br i1 %cmp82, label %for.body84, label %return + +return: ; preds = %if.end106, %for.body84, %for.end, %for.cond, %entry + ret void +} + +attributes #0 = { "use-soft-float"="false" } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 10.0.0 (git@github.com:llvm/llvm-project.git 2ac702aaf09174432905a9f05b31418a89019437)"} diff --git a/llvm/test/Transforms/LoopStrengthReduce/scev-expander-lcssa.ll b/llvm/test/Transforms/LoopStrengthReduce/scev-expander-lcssa.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopStrengthReduce/scev-expander-lcssa.ll @@ -0,0 +1,144 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -loop-reduce -S %s | FileCheck %s + +; Make sure SCEVExpander does not crash and introduce unnecessary LCSSA PHI nodes. + +define void @schedule_block() { +; CHECK-LABEL: @schedule_block( +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i16 undef, label [[IF_END156_I:%.*]] [ +; CHECK-NEXT: i16 27, label [[IF_THEN_I:%.*]] +; CHECK-NEXT: i16 28, label [[IF_THEN_I]] +; CHECK-NEXT: i16 29, label [[IF_THEN13_I:%.*]] +; CHECK-NEXT: i16 32, label [[LAND_LHS_TRUE136_I:%.*]] +; CHECK-NEXT: ] +; CHECK: if.then.i: +; CHECK-NEXT: unreachable +; CHECK: if.then13.i: +; CHECK-NEXT: unreachable +; CHECK: land.lhs.true136.i: +; CHECK-NEXT: unreachable +; CHECK: if.end156.i: +; CHECK-NEXT: switch i16 undef, label [[WHILE_END256:%.*]] [ +; CHECK-NEXT: i16 29, label [[IF_THEN210:%.*]] +; CHECK-NEXT: i16 28, label [[IF_THEN210]] +; CHECK-NEXT: i16 27, label [[LAND_LHS_TRUE191:%.*]] +; CHECK-NEXT: i16 32, label [[IF_END248:%.*]] +; CHECK-NEXT: ] +; CHECK: land.lhs.true191: +; CHECK-NEXT: unreachable +; CHECK: if.then210: +; CHECK-NEXT: unreachable +; CHECK: if.end248: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: while.end256: +; CHECK-NEXT: unreachable +; CHECK: for.end: +; CHECK-NEXT: br label [[WHILE_BODY1013:%.*]] +; CHECK: while.body1013: +; CHECK-NEXT: br label [[FOR_COND_I2472:%.*]] +; CHECK: for.cond.i2472: +; CHECK-NEXT: [[I_0_I:%.*]] = phi i32 [ 0, [[WHILE_BODY1013]] ], [ [[TMP2:%.*]], [[FOR_END34_I:%.*]] ] +; CHECK-NEXT: br i1 false, label [[FOR_COND3_PREHEADER_I:%.*]], label [[IF_END107_I_LOOPEXIT:%.*]] +; CHECK: for.cond3.preheader.i: +; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[I_0_I]] to i64 +; CHECK-NEXT: [[TMP1:%.*]] = add nsw i64 [[TMP0]], 1 +; CHECK-NEXT: br label [[FOR_COND3_I:%.*]] +; CHECK: for.cond3.i: +; CHECK-NEXT: [[INDVARS_IV301_I2691:%.*]] = phi i64 [ [[INDVARS_IV_NEXT302_I:%.*]], [[FOR_BODY5_I:%.*]] ], [ [[TMP1]], [[FOR_COND3_PREHEADER_I]] ] +; CHECK-NEXT: [[INDVARS_IV_NEXT302_I]] = add nsw i64 [[INDVARS_IV301_I2691]], 1 +; CHECK-NEXT: br label [[FOR_BODY5_I]] +; CHECK: for.body5.i: +; CHECK-NEXT: br i1 false, label [[FOR_COND3_I]], label [[FOR_BODY5_I_FOR_END_I2475_LOOPEXIT_CRIT_EDGE:%.*]] +; CHECK: for.body5.i.for.end.i2475.loopexit_crit_edge: +; CHECK-NEXT: [[TMP2]] = trunc i64 [[INDVARS_IV_NEXT302_I]] to i32 +; CHECK-NEXT: br label [[FOR_END34_I]] +; CHECK: for.end34.i: +; CHECK-NEXT: br i1 false, label [[FOR_COND_I2472]], label [[IF_ELSE_I2488:%.*]] +; CHECK: if.else.i2488: +; CHECK-NEXT: br i1 undef, label [[IF_END107_I:%.*]], label [[FOR_BODY45_PREHEADER_I:%.*]] +; CHECK: for.body45.preheader.i: +; CHECK-NEXT: [[TMP3:%.*]] = sext i32 [[I_0_I]] to i64 +; CHECK-NEXT: unreachable +; CHECK: if.end107.i.loopexit: +; CHECK-NEXT: br label [[IF_END107_I]] +; CHECK: if.end107.i: +; CHECK-NEXT: unreachable +; +entry: + switch i16 undef, label %if.end156.i [ + i16 27, label %if.then.i + i16 28, label %if.then.i + i16 29, label %if.then13.i + i16 32, label %land.lhs.true136.i + ] + +if.then.i: ; preds = %entry, %entry + unreachable + +if.then13.i: ; preds = %entry + unreachable + +land.lhs.true136.i: ; preds = %entry + unreachable + +if.end156.i: ; preds = %entry + switch i16 undef, label %while.end256 [ + i16 29, label %if.then210 + i16 28, label %if.then210 + i16 27, label %land.lhs.true191 + i16 32, label %if.end248 + ] + +land.lhs.true191: ; preds = %if.end156.i + unreachable + +if.then210: ; preds = %if.end156.i, %if.end156.i + unreachable + +if.end248: ; preds = %if.end156.i + br label %for.end + +while.end256: ; preds = %if.end156.i + unreachable + +for.end: ; preds = %if.end248 + br label %while.body1013 + +while.body1013: ; preds = %for.end + br label %for.cond.i2472 + +for.cond.i2472: ; preds = %for.end34.i, %while.body1013 + %i.0.i = phi i32 [ 0, %while.body1013 ], [ %2, %for.end34.i ] + br i1 undef, label %for.cond3.preheader.i, label %if.end107.i + +for.cond3.preheader.i: ; preds = %for.cond.i2472 + %0 = sext i32 %i.0.i to i64 + %1 = add nsw i64 %0, 1 + br label %for.cond3.i + +for.cond3.i: ; preds = %for.body5.i, %for.cond3.preheader.i + %indvars.iv301.i2691 = phi i64 [ %indvars.iv.next302.i, %for.body5.i ], [ %1, %for.cond3.preheader.i ] + %indvars.iv.next302.i = add nsw i64 %indvars.iv301.i2691, 1 + br label %for.body5.i + +for.body5.i: ; preds = %for.cond3.i + br i1 undef, label %for.cond3.i, label %for.body5.i.for.end.i2475.loopexit_crit_edge + +for.body5.i.for.end.i2475.loopexit_crit_edge: ; preds = %for.body5.i + %2 = trunc i64 %indvars.iv.next302.i to i32 + br label %for.end34.i + +for.end34.i: ; preds = %for.body5.i.for.end.i2475.loopexit_crit_edge + br i1 undef, label %for.cond.i2472, label %if.else.i2488 + +if.else.i2488: ; preds = %for.end34.i + br i1 undef, label %if.end107.i, label %for.body45.preheader.i + +for.body45.preheader.i: ; preds = %if.else.i2488 + %3 = sext i32 %i.0.i to i64 + unreachable + +if.end107.i: ; preds = %if.else.i2488, %for.cond.i2472 + unreachable +} diff --git a/llvm/unittests/Transforms/Utils/ScalarEvolutionExpanderTest.cpp b/llvm/unittests/Transforms/Utils/ScalarEvolutionExpanderTest.cpp --- a/llvm/unittests/Transforms/Utils/ScalarEvolutionExpanderTest.cpp +++ b/llvm/unittests/Transforms/Utils/ScalarEvolutionExpanderTest.cpp @@ -280,7 +280,7 @@ Phi->addIncoming(Add, L); Builder.SetInsertPoint(Post); - Builder.CreateRetVoid(); + Instruction *Ret = Builder.CreateRetVoid(); ScalarEvolution SE = buildSE(*F); const SCEV *S = SE.getSCEV(Phi); @@ -291,6 +291,11 @@ 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