Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -423,8 +423,9 @@ /// instructions of the loop and loop safety information as /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, - TargetLibraryInfo *, Loop *, AliasSetTracker *, - LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); + TargetLibraryInfo *, TargetTransformInfo *, Loop *, + AliasSetTracker *, LoopSafetyInfo *, + OptimizationRemarkEmitter *ORE); /// \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 Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -89,14 +89,17 @@ static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI); static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo); + const LoopSafetyInfo *SafetyInfo, + TargetTransformInfo *TTI, + bool &ContainFoldableUsersInLoop); static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE); static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, const Loop *CurLoop, AliasSetTracker *CurAST, const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE); + OptimizationRemarkEmitter *ORE, + bool ContainFoldableUsersInLoop); static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, @@ -114,8 +117,9 @@ namespace { struct LoopInvariantCodeMotion { bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, - TargetLibraryInfo *TLI, ScalarEvolution *SE, - OptimizationRemarkEmitter *ORE, bool DeleteAST); + TargetLibraryInfo *TLI, TargetTransformInfo *TTI, + ScalarEvolution *SE, OptimizationRemarkEmitter *ORE, + bool DeleteAST); DenseMap &getLoopToAliasSetMap() { return LoopToAliasSetMap; @@ -155,6 +159,8 @@ &getAnalysis().getLoopInfo(), &getAnalysis().getDomTree(), &getAnalysis().getTLI(), + &getAnalysis().getTTI( + *L->getHeader()->getParent()), SE ? &SE->getSE() : nullptr, &ORE, false); } @@ -164,6 +170,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); + AU.addRequired(); getLoopAnalysisUsage(AU); } @@ -204,7 +211,8 @@ "cached at a higher level"); LoopInvariantCodeMotion LICM; - if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.SE, ORE, true)) + if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.TTI, &AR.SE, ORE, + true)) return PreservedAnalyses::all(); auto PA = getLoopPassPreservedAnalyses(); @@ -217,6 +225,7 @@ false, false) INITIALIZE_PASS_DEPENDENCY(LoopPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, false) @@ -228,12 +237,10 @@ /// We should delete AST for inner loops in the new pass manager to avoid /// memory leak. /// -bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA, - LoopInfo *LI, DominatorTree *DT, - TargetLibraryInfo *TLI, - ScalarEvolution *SE, - OptimizationRemarkEmitter *ORE, - bool DeleteAST) { +bool LoopInvariantCodeMotion::runOnLoop( + Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, + TargetLibraryInfo *TLI, TargetTransformInfo *TTI, ScalarEvolution *SE, + OptimizationRemarkEmitter *ORE, bool DeleteAST) { bool Changed = false; assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."); @@ -258,7 +265,7 @@ // instructions, we perform another pass to hoist them out of the loop. // if (L->hasDedicatedExits()) - Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L, + Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L, CurAST, &SafetyInfo, ORE); if (Preheader) Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L, @@ -358,7 +365,8 @@ /// definitions, allowing us to sink a loop body in one pass without iteration. /// bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, - DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, + DominatorTree *DT, TargetLibraryInfo *TLI, + TargetTransformInfo *TTI, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { @@ -399,10 +407,14 @@ // outside of the loop. In this case, it doesn't even matter if the // operands of the instruction are loop invariant. // - if (isNotUsedInLoop(I, CurLoop, SafetyInfo) && + bool ContainFoldableUsersInLoop = false; + if (isNotUsedInLoop(I, CurLoop, SafetyInfo, TTI, + ContainFoldableUsersInLoop) && canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE)) { - ++II; - Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo, ORE); + if (!ContainFoldableUsersInLoop) + ++II; + Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo, ORE, + ContainFoldableUsersInLoop); } } } @@ -694,12 +706,34 @@ return true; } +static bool isFreeInLoop(const Instruction *I, const Instruction *UserI, + const TargetTransformInfo *TTI) { + /// FIXME: for now we simply check if the addressing mode defined by a GEP is + /// directly foldable into a load/store. The GEP could also be a part of + /// addressing mode in a load/store instruction through other instructions + /// (e.g., sext or other GEPs). + /// We might not even have to restrict this to GEPs, but rather, we could + /// allow all zero-cost instructions. However, we need to take wide tests + /// before opening up this for all other instructions. + const GetElementPtrInst *GEP = dyn_cast(I); + // Specificially check if the GEP is used by a load/store in the same block. + if (GEP && (isa(UserI) || isa(UserI)) && + (I->getParent() == UserI->getParent())) { + return TTI->getUserCost(GEP) == TargetTransformInfo::TCC_Free; + } + return false; +} + /// Return true if the only users of this instruction are outside of /// the loop. If this is true, we can sink the instruction to the exit /// blocks of the loop. /// +/// We also return true if the instruction is foldable in the loop at isel time +/// (e.g., a GEP can be folded into a load as an addressing mode in the loop). static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo) { + const LoopSafetyInfo *SafetyInfo, + TargetTransformInfo *TTI, + bool &ContainFoldableUsersInLoop) { const auto &BlockColors = SafetyInfo->BlockColors; for (const User *U : I.users()) { const Instruction *UI = cast(U); @@ -737,8 +771,14 @@ continue; } - if (CurLoop->contains(UI)) + if (CurLoop->contains(UI)) { + // Check if the instruction is foldable with its user in the loop. + if (isFreeInLoop(&I, UI, TTI)) { + ContainFoldableUsersInLoop = true; + continue; + } return false; + } } return true; } @@ -812,7 +852,8 @@ static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, const Loop *CurLoop, AliasSetTracker *CurAST, const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE) { + OptimizationRemarkEmitter *ORE, + bool ContainFoldableUsersInLoop) { DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); ORE->emit(OptimizationRemark(DEBUG_TYPE, "InstSunk", &I) << "sinking " << ore::NV("Inst", &I)); @@ -833,13 +874,19 @@ // Clones of this instruction. Don't create more than one per exit block! SmallDenseMap SunkCopies; + SmallPtrSet UsersToBeRemoved; // If this instruction is only used outside of the loop, then all users are // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of // the instruction. - while (!I.use_empty()) { - Value::user_iterator UI = I.user_begin(); + for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) { auto *User = cast(*UI); + Use &U = UI.getUse(); + ++UI; + + if (CurLoop->contains(User) || UsersToBeRemoved.count(User)) + continue; + if (!DT->isReachableFromEntry(User->getParent())) { User->replaceUsesOfWith(&I, UndefValue::get(I.getType())); continue; @@ -850,7 +897,6 @@ // Surprisingly, instructions can be used outside of loops without any // exits. This can only happen in PHI nodes if the incoming block is // unreachable. - Use &U = UI.getUse(); BasicBlock *BB = PN->getIncomingBlock(U); if (!DT->isReachableFromEntry(BB)) { U = UndefValue::get(I.getType()); @@ -869,12 +915,18 @@ New = SunkCopies[ExitBlock] = CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo); + UsersToBeRemoved.insert(PN); PN->replaceAllUsesWith(New); - PN->eraseFromParent(); } - CurAST->deleteValue(&I); - I.eraseFromParent(); + for (auto *User : UsersToBeRemoved) + User->eraseFromParent(); + + if (!ContainFoldableUsersInLoop) { + CurAST->deleteValue(&I); + I.eraseFromParent(); + } + return Changed; } Index: test/Transforms/LICM/sink-foldable.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/sink-foldable.ll @@ -0,0 +1,98 @@ +; RUN: opt < %s -licm -S | FileCheck %s +target triple = "aarch64--linux-gnueabi" + +; CHECK-LABEL:@test1 +; CHECK-LABEL:loopexit1: +; CHECK: %[[PHI:.+]] = phi i8** [ %arrayidx0, %if.end ] +; CHECK: getelementptr inbounds i8*, i8** %[[PHI]], i64 1 + +define i8** @test1(i32 %j, i8** readonly %P, i8* readnone %Q) { +entry: + %cmp0 = icmp slt i32 0, %j + br i1 %cmp0, label %for.body.lr.ph, label %return + +for.body.lr.ph: + br label %for.body + +for.body: + %P.addr = phi i8** [ %P, %for.body.lr.ph ], [ %arrayidx0, %if.end ] + %i0 = phi i32 [ 0, %for.body.lr.ph ], [ %i.add, %if.end] + + %i0.ext = sext i32 %i0 to i64 + %arrayidx0 = getelementptr inbounds i8*, i8** %P.addr, i64 %i0.ext + %l0 = load i8*, i8** %arrayidx0, align 8 + %cmp1 = icmp ugt i8* %l0, %Q + br i1 %cmp1, label %loopexit0, label %if.end + +if.end: ; preds = %for.body + %arrayidx1 = getelementptr inbounds i8*, i8** %arrayidx0, i64 1 + %l1 = load i8*, i8** %arrayidx1, align 8 + %cmp4 = icmp ugt i8* %l1, %Q + %i.add = add nsw i32 %i0, 2 + br i1 %cmp4, label %loopexit1, label %for.body + +loopexit0: + %p1 = phi i8** [%arrayidx0, %for.body] + br label %return + +loopexit1: + %p2 = phi i8** [%arrayidx1, %if.end] + br label %return + +return: + %retval.0 = phi i8** [ %p1, %loopexit0 ], [%p2, %loopexit1], [ null, %entry ] + ret i8** %retval.0 +} + +; CHECK-LABEL: @test2 +; CHECK-LABEL: loopexit2: +; CHECK: %[[PHI:.*]] = phi i8** [ %add.ptr, %if.end ] +; CHECK: getelementptr inbounds i8*, i8** %[[PHI]] + +define i8** @test2(i32 %j, i8** readonly %P, i8* readnone %Q) { + +entry: + br label %for.body + +for.cond: + %i.addr.0 = phi i32 [ %add, %if.end ] + %P.addr.0 = phi i8** [ %add.ptr, %if.end ] + %cmp = icmp slt i32 %i.addr.0, %j + br i1 %cmp, label %for.body, label %loopexit0 + +for.body: + %P.addr = phi i8** [ %P, %entry ], [ %P.addr.0, %for.cond ] + %i.addr = phi i32 [ 0, %entry ], [ %i.addr.0, %for.cond ] + + %idx.ext = sext i32 %i.addr to i64 + %add.ptr = getelementptr inbounds i8*, i8** %P.addr, i64 %idx.ext + %l0 = load i8*, i8** %add.ptr, align 8 + + %cmp1 = icmp ugt i8* %l0, %Q + br i1 %cmp1, label %loopexit1, label %if.end + +if.end: + %add.i = add i32 %i.addr, 1 + %idx2.ext = sext i32 %add.i to i64 + %arrayidx2 = getelementptr inbounds i8*, i8** %add.ptr, i64 %idx2.ext + %l1 = load i8*, i8** %arrayidx2, align 8 + %cmp2 = icmp ugt i8* %l1, %Q + %add = add nsw i32 %add.i, 1 + br i1 %cmp2, label %loopexit2, label %for.cond + +loopexit0: + %p0 = phi i8** [ null, %for.cond ] + br label %return + +loopexit1: + %p1 = phi i8** [ %add.ptr, %for.body ] + br label %return + +loopexit2: + %p2 = phi i8** [ %arrayidx2, %if.end ] + br label %return + +return: + %retval.0 = phi i8** [ %p1, %loopexit1 ], [ %p2, %loopexit2 ], [ %p0, %loopexit0 ] + ret i8** %retval.0 +}