Index: include/llvm/Analysis/LoopInfo.h =================================================================== --- include/llvm/Analysis/LoopInfo.h +++ include/llvm/Analysis/LoopInfo.h @@ -366,6 +366,16 @@ /// invariant. bool hasLoopInvariantOperands(const Instruction *I) const; + // Return true if the specified value is either loop invariant or defined in + // the given subloop. + bool isLoopInvariantOutsideSubLoop(const Value *V, + const Loop *Sub) const; + + // Return true if all the operands of the specified instruction are loop + // invariant or defined in the given subloop. + bool hasLoopInvariantOperandsOutsideSubLoop(const Instruction *I, + const Loop *Sub) const; + /// If the given value is an instruction inside of the loop and it can be /// hoisted, do so to make it trivially loop-invariant. /// Return true if the value after any hoisting is loop invariant. This Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -17,6 +17,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/EHPersonalities.h" +#include "llvm/Analysis/LoopPass.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" @@ -343,7 +344,7 @@ /// It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LICMSafetyInfo *, LoopPass *); /// \brief Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -354,7 +355,7 @@ /// loop and loop safety information as arguments. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LICMSafetyInfo *, LoopPass *); /// \brief Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over Index: lib/Analysis/LoopInfo.cpp =================================================================== --- lib/Analysis/LoopInfo.cpp +++ lib/Analysis/LoopInfo.cpp @@ -64,6 +64,23 @@ return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); }); } +bool Loop::isLoopInvariantOutsideSubLoop(const Value *V, + const Loop *Sub) const { + if (const Instruction *I = dyn_cast(V)) { + // It's defined in the subloop or outside the outer loop. + return Sub->contains(I) || !contains(I); + } + return true; +} + +bool Loop::hasLoopInvariantOperandsOutsideSubLoop(const Instruction *I, + const Loop *Sub) const { + return all_of(I->operands(), + [this, Sub](Value *V) { + return isLoopInvariantOutsideSubLoop(V, Sub); + }); +} + bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt) const { if (Instruction *I = dyn_cast(V)) Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -103,6 +103,7 @@ DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo); +static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I); namespace { struct LICM : public LoopPass { @@ -117,7 +118,6 @@ /// loop preheaders be inserted into the CFG... /// void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesCFG(); AU.addRequired(); AU.addRequired(); AU.addRequiredID(LoopSimplifyID); @@ -239,10 +239,10 @@ // if (L->hasDedicatedExits()) Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop, - CurAST, &SafetyInfo); + CurAST, &SafetyInfo, this); if (Preheader) Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, - CurLoop, CurAST, &SafetyInfo); + CurLoop, CurAST, &SafetyInfo, this); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can. @@ -289,6 +289,294 @@ return Changed; } +static bool canSinkSubLoop(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI, + DominatorTree *DT, TargetLibraryInfo *TLI, + Loop *CurLoop, AliasSetTracker *CurAST, + LICMSafetyInfo *SafetyInfo) { + // Only loops at level n+1. + if (SubLoop->getParentLoop() != CurLoop) + return false; + + auto ExitBlock = SubLoop->getExitBlock(); + // Don't sink if it has multiple exit or entry blocks, or if there's no + // single exit block we can sink to. + if (!ExitBlock || !SubLoop->getLoopPreheader() || !CurLoop->getExitBlock()) { + return false; + } + + // Don't sink the subloop unless it's guaranteed to execute, i.e. all paths + // to the outer loop's exit block go through the subloop. + if (!DT->dominates(SubLoop->getHeader(), CurLoop->getExitBlock())) { + DEBUG(dbgs() << "Not sinking subloop: " << SubLoop->getHeader()->getName() + << " does not dominate outer loop exit: " + << CurLoop->getExitBlock()->getName() << "\n"); + return false; + } + + // Find any LCSSA phi nodes and check they're not used inside the loop. + PHINode *PN; + for (auto II = ExitBlock->begin(); (PN = dyn_cast(II)); ++II) { + if (PN->getNumOperands() == 1 && + SubLoop->contains(PN->getIncomingBlock(0))) { + if (!isNotUsedInLoop(*PN, CurLoop, SafetyInfo)) { + DEBUG(dbgs() << "Not sinking subloop: " + << SubLoop->getHeader()->getName() + << ": Inner loop value used in outer loop.\n"); + return false; + } + } + } + + // Check we can sink each instruction inside the loop. + for (BasicBlock *BB : SubLoop->blocks()) { + for (Instruction &I : *BB) { + if (!isa(&I) && !isa(&I) && + !canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) { + DEBUG(dbgs() << "Not sinking subloop: " + << SubLoop->getHeader()->getName() << ": Can't sink " << I + << "\n"); + return false; + } + } + } + + return true; +} + +static bool canHoistSubLoop(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI, + DominatorTree *DT, TargetLibraryInfo *TLI, + Loop *CurLoop, AliasSetTracker *CurAST, + LICMSafetyInfo *SafetyInfo) { + // Only loops at level n+1. + if (SubLoop->getParentLoop() != CurLoop) + return false; + + // Don't hoist if it has multiple exit or entry blocks. + if (!SubLoop->getExitBlock() || !SubLoop->getLoopPreheader()) { + DEBUG(dbgs() << "Not hoisting subloop: " << SubLoop->getHeader()->getName() + << ": Missing exit block or preheader."); + return false; + } + + if (!DT->dominates(SubLoop->getHeader(), CurLoop->getExitBlock())) { + DEBUG(dbgs() << "Not hoisting subloop: " << SubLoop->getHeader()->getName() + << " does not dominate outer loop exit: " + << CurLoop->getExitBlock()->getName() << "\n"); + return false; + } + + // Go through all instructions in the subloop, and return if one of them + // means the loop can't be hoisted. + // FIXME: Only do this loop once, share result between sinking and hoisting. + for (BasicBlock *BB : SubLoop->blocks()) { + for (Instruction &I : *BB) { + if (!CurLoop->hasLoopInvariantOperandsOutsideSubLoop(&I, SubLoop)) { + DEBUG(dbgs() << "Not hoisting subloop: " + << SubLoop->getHeader()->getName() + << ": Instruction has loop-variant operands: " << I + << "\n"); + return false; + } else if (isa(&I) || isa(&I)) { + continue; + } else if (!canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, + CurAST, SafetyInfo)) { + return false; + } else if (!isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo, + CurLoop->getLoopPreheader()->getTerminator())) { + return false; + } + } + } + + return true; +} + +/// \brief Update all phi nodes for which the incoming block is no longer a +// predecessor of BB to refer to New. +static void replaceInvalidPHIOperandsWith(BasicBlock *BB, BasicBlock *New) { + PHINode *PN; + for (auto II = BB->begin(); (PN = dyn_cast(II)); ++II) { + for (unsigned Idx = 0; Idx < PN->getNumOperands(); ++Idx) { + BasicBlock *Incoming = PN->getIncomingBlock(Idx); + if (std::find(pred_begin(BB), pred_end(BB), Incoming) == pred_end(BB)) + PN->setIncomingBlock(Idx, New); + } + } +} + +static void removeSubLoop(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI, + DominatorTree *DT, TargetLibraryInfo *TLI, + Loop *CurLoop, AliasSetTracker *CurAST, + LICMSafetyInfo *SafetyInfo) { + auto &SubLoops = CurLoop->getSubLoops(); + BasicBlock *SubLoopHeader = SubLoop->getHeader(); + Loop::iterator it = std::find(SubLoops.begin(), SubLoops.end(), SubLoop); + assert(it != SubLoops.end() && *it == SubLoop); + SubLoop = CurLoop->removeChildLoop(it); + + auto OldExitBlock = SubLoop->getExitBlock(); + assert(OldExitBlock); + + // Create a new exit block, which will be hoisted along with the loop to + // preserve LCSSA. + BasicBlock *NewExitBlock = + BasicBlock::Create(SubLoopHeader->getContext(), + SubLoopHeader->getName() + ".licm_exit", + SubLoopHeader->getParent()); + + TerminatorInst *DummyTerm = + new UnreachableInst(NewExitBlock->getContext(), NewExitBlock); + + // Find any LCSSA phi nodes and add them to the new exit block. + std::vector PhisToMove; + PHINode *PN; + for (auto II = OldExitBlock->begin(); (PN = dyn_cast(II)); ++II) { + if (PN->getNumOperands() == 1 && + SubLoop->contains(PN->getIncomingBlock(0))) { + auto Inst = dyn_cast(PN->getIncomingValue(0)); + if (Inst && SubLoop->contains(Inst)) + PhisToMove.push_back(PN); + } + } + for (auto PN : PhisToMove) + PN->moveBefore(DummyTerm); + + // Point the subloop's predecessor at its exit block. + BasicBlock *SubLoopPredecessor = SubLoop->getLoopPredecessor(); + SubLoopPredecessor->getTerminator()->replaceUsesOfWith(SubLoopHeader, + OldExitBlock); + + auto ExitingBlock = SubLoop->getExitingBlock(); + for (auto II = OldExitBlock->begin(); isa(II); ++II) + II->replaceUsesOfWith(ExitingBlock, SubLoopPredecessor); + + // Branch from the subloop's exiting block to the new exit block. + for (auto BBI = succ_begin(ExitingBlock); BBI != succ_end(ExitingBlock); + ++BBI) { + if (!SubLoop->contains(*BBI)) { + ExitingBlock->getTerminator()->replaceUsesOfWith(*BBI, NewExitBlock); + } + } + + for (auto *BB : SubLoop->blocks()) + CurLoop->removeBlockFromLoop(BB); +} + +// Insert the subloop between the outer loop's preheader and header. +static void insertLoopAfterPreheader(Loop *SubLoop, AliasAnalysis *AA, + LoopInfo *LI, DominatorTree *DT, + TargetLibraryInfo *TLI, Loop *CurLoop, + AliasSetTracker *CurAST, + LICMSafetyInfo *SafetyInfo) { + BasicBlock *SubLoopHeader = SubLoop->getHeader(); + BasicBlock *Preheader = CurLoop->getLoopPreheader(); + BasicBlock *NewExitBlock = SubLoop->getExitBlock(); + + DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": "); + DEBUG(SubLoop->dump()); + + // The preheader's successors are having (one of) their predecessors replaced + // with NewExitBlock, so update their phis. + Preheader->replaceSuccessorsPhiUsesWith(NewExitBlock); + + // Replace the hoisted subloop's exit block's dummy terminator with the + // preheader's terminator. + Preheader->getTerminator()->moveBefore(NewExitBlock->getTerminator()); + NewExitBlock->getTerminator()->eraseFromParent(); + + // Branch from the preheader to the hoisted subloop. + BranchInst::Create(SubLoopHeader, Preheader); + + // Fix up invalid phis in the subloop header. If a block in a phi is _not_ a + // predecessor, it's invalid and used to point to somewhere in the outer + // loop. Point it at the preheader instead. + replaceInvalidPHIOperandsWith(SubLoopHeader, Preheader); + + Loop *ParentLoop = CurLoop->getParentLoop(); + if (ParentLoop) { + ParentLoop->addChildLoop(SubLoop); + ParentLoop->addBasicBlockToLoop(NewExitBlock, *LI); + } +} + +// Insert the subloop between after the phis in the outer loop's exit block. +static void sinkSubLoopToExit(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI, + DominatorTree *DT, TargetLibraryInfo *TLI, + Loop *CurLoop, AliasSetTracker *CurAST, + LICMSafetyInfo *SafetyInfo) { + BasicBlock *SubLoopHeader = SubLoop->getHeader(); + BasicBlock *ExitBlock = CurLoop->getExitBlock(); + BasicBlock *SubLoopExitBlock = SubLoop->getExitBlock(); + assert(SubLoopHeader && ExitBlock && SubLoopExitBlock); + + DEBUG(dbgs() << "LICM sinking to " << ExitBlock->getName() << ": "); + DEBUG(SubLoop->dump()); + + // Split the outer loop's exit block into phi and non-phi parts. + BasicBlock *AfterSubLoop = ExitBlock->splitBasicBlock( + ExitBlock->getFirstNonPHI(), ExitBlock->getName() + ".licm_post_subloop"); + + // Like in hoisting, fix up invalid phis in the subloop header which used to + // refer to the loop's predecessors inside the outer loop. + replaceInvalidPHIOperandsWith(SubLoopHeader, ExitBlock); + + // The outer loop's exit block may contain LCSSA phi nodes referring to + // values defined in the inner loop. But because we've moved the inner loop + // to *after* these nodes, they are invalid. RAUW with the *inner* loop's + // LCSSA node. + std::vector InstructionsToErase; + PHINode *PN; + for (auto II = ExitBlock->begin(); (PN = dyn_cast(II)); ++II) { + auto Incoming = dyn_cast(PN->getIncomingValue(0)); + if (Incoming && PN->getNumOperands() > 0 && + isTriviallyReplacablePHI(*PN, *Incoming)) { + if (Incoming->getParent() == SubLoopExitBlock) { + PN->replaceAllUsesWith(Incoming); + InstructionsToErase.push_back(PN); + } + } + } + for (auto I : InstructionsToErase) + I->eraseFromParent(); + + // Branch from the sunk subloop's exit block to the non-phi part of the + // original exit block. + ExitBlock->getTerminator()->moveBefore(SubLoopExitBlock->getTerminator()); + SubLoopExitBlock->getTerminator()->eraseFromParent(); + + // Branch from the outer loop's exit block to the sunk subloop. + BranchInst::Create(SubLoopHeader, ExitBlock); + + // The sunk subloop may use values which were defined in the outer loop. To + // preserve LCSSA, find these and add phis in the outer loop's exit block. + SmallVector ExitingBlocks; + CurLoop->getExitingBlocks(ExitingBlocks); + for (BasicBlock *BB : SubLoop->blocks()) { + for (Instruction &I : *BB) { + for (unsigned Idx = 0; Idx < I.getNumOperands(); ++Idx) { + auto Op = dyn_cast(I.getOperand(Idx)); + if (Op && CurLoop->contains(Op->getParent())) { + auto PN = + PHINode::Create(Op->getType(), 0, Op->getName() + ".licm_lcssa", + &*ExitBlock->begin()); + for (BasicBlock *ExitingBlock : ExitingBlocks) { + PN->addIncoming(Op, ExitingBlock); + } + I.setOperand(Idx, PN); + DEBUG(dbgs() << "Creating PHI node: " << *PN << "\n"); + } + } + } + } + + Loop *ParentLoop = CurLoop->getParentLoop(); + if (ParentLoop) { + ParentLoop->addChildLoop(SubLoop); + ParentLoop->addBasicBlockToLoop(SubLoopExitBlock, *LI); + ParentLoop->addBasicBlockToLoop(AfterSubLoop, *LI); + } +} + /// Walk the specified region of the CFG (defined by all blocks dominated by /// the specified block, and that are in the current loop) in reverse depth /// first order w.r.t the DominatorTree. This allows us to visit uses before @@ -296,7 +584,8 @@ /// bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, - AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) { + AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo, + LoopPass *LP) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && @@ -311,11 +600,33 @@ bool Changed = false; const std::vector &Children = N->getChildren(); for (DomTreeNode *Child : Children) - Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); + Changed |= + sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, LP); // Only need to process the contents of this block if it is not part of a // subloop (which would already have been processed). - if (inSubLoop(BB,CurLoop,LI)) return Changed; + if (inSubLoop(BB, CurLoop, LI)) { + BasicBlock *BB = N->getBlock(); + Loop *SubLoop = LI->getLoopFor(BB); + + // Make sure this is the dominating block. + if (SubLoop->getHeader() == BB) { + if (canSinkSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, + SafetyInfo)) { + removeSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); + sinkSubLoopToExit(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, + SafetyInfo); + SubLoop->verifyLoop(); + CurLoop->verifyLoop(); + Changed = true; + // runOnLoop uses the subloop list to find out what to free. Because + // SubLoop is no longer in that list, free it here instead. + if (LP && !CurLoop->getParentLoop()) + LP->deleteAnalysisLoop(SubLoop); + } + } + return Changed; + } for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { Instruction &I = *--II; @@ -352,7 +663,8 @@ /// bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, - AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) { + AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo, + LoopPass *LP) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && CurAST != nullptr && @@ -366,7 +678,7 @@ // Only need to process the contents of this block if it is not part of a // subloop (which would already have been processed). bool Changed = false; - if (!inSubLoop(BB, CurLoop, LI)) + if (!inSubLoop(BB, CurLoop, LI)) { for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { Instruction &I = *II++; // Try constant folding this instruction. If all the operands are @@ -392,10 +704,32 @@ CurLoop->getLoopPreheader()->getTerminator())) Changed |= hoist(I, DT, CurLoop, SafetyInfo); } + } else { // See if we can hoist the entire subloop. + BasicBlock *BB = N->getBlock(); + Loop *SubLoop = LI->getLoopFor(BB); + + // Make sure this is the dominating block. + if (SubLoop->getHeader() == BB) { + if (canHoistSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, + SafetyInfo)) { + removeSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); + insertLoopAfterPreheader(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, + SafetyInfo); + SubLoop->verifyLoop(); + Changed = true; + // runOnLoop uses the subloop list to find out what to free. Because + // SubLoop is no longer in that list, free it here instead. + if (LP && !CurLoop->getParentLoop()) + LP->deleteAnalysisLoop(SubLoop); + } + } + } const std::vector &Children = N->getChildren(); - for (DomTreeNode *Child : Children) - Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); + for (DomTreeNode *Child : Children) { + Changed |= + hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, LP); + } return Changed; } @@ -1063,20 +1397,26 @@ AliasSetTracker *LICM::collectAliasInfoFromSubLoops(Loop *L) { AliasSetTracker *CurAST = nullptr; for (Loop *InnerL : L->getSubLoops()) { - AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL]; - assert(InnerAST && "Where is my AST?"); - - if (CurAST != nullptr) { - // What if InnerLoop was modified by other passes ? - CurAST->add(*InnerAST); - - // Once we've incorporated the inner loop's AST into ours, we don't need - // the subloop's anymore. - delete InnerAST; - } else { - CurAST = InnerAST; + auto ASTI = LoopToAliasSetMap.find(InnerL); + + // Subloop alias info may have already been merged into another subloop's + // AST if it was hoisted from an inner loop. + if (ASTI != LoopToAliasSetMap.end()) { + AliasSetTracker *InnerAST = ASTI->second; + assert(InnerAST); + + if (CurAST != nullptr) { + // What if InnerLoop was modified by other passes ? + CurAST->add(*InnerAST); + + // Once we've incorporated the inner loop's AST into ours, we don't need + // the subloop's anymore. + delete InnerAST; + } else { + CurAST = InnerAST; + } + LoopToAliasSetMap.erase(InnerL); } - LoopToAliasSetMap.erase(InnerL); } if (CurAST == nullptr) CurAST = new AliasSetTracker(*AA); @@ -1086,32 +1426,39 @@ /// Simple analysis hook. Clone alias set info. /// void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { - AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); - if (!AST) - return; + auto ASTI = LoopToAliasSetMap.find(L); + if (ASTI != LoopToAliasSetMap.end()) { + AliasSetTracker *AST = ASTI->second; + assert(AST); - AST->copyValue(From, To); + AST->copyValue(From, To); + } } /// Simple Analysis hook. Delete value V from alias set /// void LICM::deleteAnalysisValue(Value *V, Loop *L) { - AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); - if (!AST) - return; + auto ASTI = LoopToAliasSetMap.find(L); + + if (ASTI != LoopToAliasSetMap.end()) { + AliasSetTracker *AST = ASTI->second; + assert(AST); - AST->deleteValue(V); + AST->deleteValue(V); + } } /// Simple Analysis hook. Delete value L from alias set map. /// void LICM::deleteAnalysisLoop(Loop *L) { - AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); - if (!AST) - return; + auto ASTI = LoopToAliasSetMap.find(L); + if (ASTI != LoopToAliasSetMap.end()) { + AliasSetTracker *AST = ASTI->second; + assert(AST); - delete AST; - LoopToAliasSetMap.erase(L); + delete AST; + LoopToAliasSetMap.erase(L); + } } Index: test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll =================================================================== --- test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll +++ test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll @@ -2,7 +2,7 @@ ; PR11882: ComputeLoadConstantCompareExitLimit crash. ; ; for.body is deleted leaving a loop-invariant load. -; CHECK-NOT: for.body +; CHECK-NOT: for.body: target datalayout = "e-p:64:64:64-n32:64" @func_21_l_773 = external global i32, align 4 Index: test/Transforms/LICM/inner-loop-dont-sink.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/inner-loop-dont-sink.ll @@ -0,0 +1,34 @@ +; RUN: opt < %s -S -licm | FileCheck %s + +define void @main() #0 { +; CHECK-LABEL: @main( +entry: +; CHECK: entry: +; CHECK-NEXT: br label %outer.header + br label %outer.header + +outer.header: +; CHECK: outer.header: +; CHECK: br i1 undef, label %if.then, label %outer.latch + br i1 undef, label %if.then, label %outer.latch + +if.then: +; CHECK: if.then: + %call = tail call i32 @generate() +; CHECK: br label %inner.body + br label %inner.body + +inner.body: +; CHECK: inner.body: + %arrayctor.done = icmp eq i32 undef, %call +; CHECK: br i1 %arrayctor.done, label %outer.latch.loopexit, label %inner.body + br i1 %arrayctor.done, label %outer.latch, label %inner.body + +outer.latch: + br i1 undef, label %outer.exit, label %outer.header + +outer.exit: + ret void +} + +declare i32 @generate() #1 Index: test/Transforms/LICM/inner-loop-hoist.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/inner-loop-hoist.ll @@ -0,0 +1,52 @@ +; RUN: opt < %s -S -licm -loop-unswitch | FileCheck %s + +; Function Attrs: nounwind uwtable +define i32 @main() #1 { +; CHECK-LABEL: @main( +entry: +; CHECK: entry: +; CHECK-NEXT: br label %third.body + br label %first.header + +first.header: +; CHECK: first.header: +; CHECK-NEXT: br label %third.body.licm_exit + br label %second.header + +second.header: +; CHECK: second.header: +; CHECK-NEXT: br label %second.exiting + br label %third.body + +third.body: +; CHECK: third.body: + %xor1.i = phi i32 [ 0, %second.header ], [ %xor1, %third.body ] + %xor1 = xor i32 %xor1.i, 1234567 +; CHECK: br i1 false, label %third.body, label %third.body.licm_exit + br i1 undef, label %third.body, label %second.exiting + +second.exiting: +; CHECK: second.exiting: + %xor1.lcssa = phi i32 [ %xor1, %third.body ] + %call1 = tail call i32 (i32) @putchar(i32 %xor1.lcssa) +; CHECK: br i1 false, label %second.header, label %first.exiting + br i1 undef, label %second.header, label %first.exiting + +first.exiting: + %xor1.lcssa2 = phi i32 [ %xor1.lcssa, %second.exiting ] + %call2 = tail call i32 (i32) @putchar(i32 %xor1.lcssa2) + br i1 false, label %first.header, label %first.exit + +first.exit: + ret i32 0 + +; CHECK: third.body.licm_exit: +; CHECK-NEXT: br label %second.header + +; CHECK: third.body.licm_exit1: +; CHECK-NEXT: phi i32 [ %xor1, %third.body ] +; CHECK-NEXT br label %first.header +} + +; Function Attrs: nounwind +declare i32 @putchar(i32) #2 Index: test/Transforms/LICM/inner-loop-sink-multiple-phi.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/inner-loop-sink-multiple-phi.ll @@ -0,0 +1,44 @@ +; RUN: opt < %s -S -licm -loop-unswitch | FileCheck %s + +define void @main() #0 { +; CHECK-LABEL: @main( +entry: +; CHECK: entry: +; CHECK: br label %outer.header + br label %outer.header + +outer.header: + br label %inner.body + +inner.body: +; CHECK: inner.body: +; CHECK-NEXT: %y = phi i32 [ 0, %outer.exit ], [ %add1, %inner.body ] +; CHECK-NEXT: %z = phi i32 [ 0, %outer.exit ], [ %add2, %inner.body ] + %y = phi i32 [ 0, %outer.header ], [ %add1, %inner.body ] + %z = phi i32 [ 0, %outer.header ], [ %add2, %inner.body ] + %add1 = add i32 %y, 7 + %add2 = add i32 %z, 11 +; CHECK: br i1 false, label %inner.body, label %inner.body.licm_exit + br i1 undef, label %inner.body, label %outer.inc + +outer.inc: +; CHECK: outer.inc: +; CHECK-NEXT: br i1 false, label %outer.header, label %outer.exit + %y.lcssa = phi i32 [ %add1, %inner.body ] + %z.lcssa = phi i32 [ %add2, %inner.body ] + br i1 undef, label %outer.header, label %outer.exit + +outer.exit: +; CHECK: outer.exit: +; CHECK-NEXT: br label %inner.body + %y.0.lcssa = phi i32 [ %y.lcssa, %outer.inc ] + %z.0.lcssa = phi i32 [ %z.lcssa, %outer.inc ] +; CHECK: outer.exit.licm_post_subloop: +; CHECK-NEXT: ret void + ret void + +; CHECK: inner.body.licm_exit: +; CHECK-NEXT: %y.lcssa = phi i32 [ %add1, %inner.body ] +; CHECK-NEXT: %z.lcssa = phi i32 [ %add2, %inner.body ] +; CHECK-NEXT: br label %outer.exit.licm_post_subloop +} Index: test/Transforms/LICM/sinking.ll =================================================================== --- test/Transforms/LICM/sinking.ll +++ test/Transforms/LICM/sinking.ll @@ -348,7 +348,7 @@ lab21: ; CHECK: lab21: ; CHECK-NOT: store -; CHECK: br i1 false, label %lab21, label %lab22 +; CHECK: br i1 false, label %lab21, label %lab21.licm_exit store i32 36127957, i32* undef, align 4 br i1 undef, label %lab21, label %lab22