diff --git a/llvm/include/llvm/Analysis/LoopNestAnalysis.h b/llvm/include/llvm/Analysis/LoopNestAnalysis.h --- a/llvm/include/llvm/Analysis/LoopNestAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopNestAnalysis.h @@ -21,11 +21,14 @@ namespace llvm { using LoopVectorTy = SmallVector; + class LPMUpdater; /// This class represents a loop nest and can be used to query its properties. class LoopNest { public: + using InstrVectorTy = SmallVector; + /// Construct a loop nest rooted by loop \p Root. LoopNest(Loop &Root, ScalarEvolution &SE); @@ -48,6 +51,12 @@ static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE); + /// Return a vector of instructions that prevent the LoopNest given + /// by loops \p OuterLoop and \p InnerLoop from being perfect. + static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop, + const Loop &InnerLoop, + ScalarEvolution &SE); + /// Return the maximum nesting depth of the loop nest rooted by loop \p Root. /// For example given the loop nest: /// \code @@ -150,6 +159,17 @@ protected: const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. LoopVectorTy Loops; // the loops in the nest (in breadth first order). + +private: + enum LoopNestEnum { + PerfectLoopNest, + ImperfectLoopNest, + InvalidLoopStructure, + OuterLoopLowerBoundUnknown + }; + static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop, + const Loop &InnerLoop, + ScalarEvolution &SE); }; raw_ostream &operator<<(raw_ostream &, const LoopNest &); diff --git a/llvm/lib/Analysis/LoopNestAnalysis.cpp b/llvm/lib/Analysis/LoopNestAnalysis.cpp --- a/llvm/lib/Analysis/LoopNestAnalysis.cpp +++ b/llvm/lib/Analysis/LoopNestAnalysis.cpp @@ -50,8 +50,66 @@ return std::make_unique(Root, SE); } +static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) { + + const BasicBlock *Latch = OuterLoop.getLoopLatch(); + assert(Latch && "Expecting a valid loop latch"); + + const BranchInst *BI = dyn_cast(Latch->getTerminator()); + assert(BI && BI->isConditional() && + "Expecting loop latch terminator to be a branch instruction"); + + CmpInst *OuterLoopLatchCmp = dyn_cast(BI->getCondition()); + DEBUG_WITH_TYPE( + VerboseDebug, if (OuterLoopLatchCmp) { + dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp + << "\n"; + }); + return OuterLoopLatchCmp; +} + +static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) { + + BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch(); + CmpInst *InnerLoopGuardCmp = + (InnerGuard) ? dyn_cast(InnerGuard->getCondition()) : nullptr; + + DEBUG_WITH_TYPE( + VerboseDebug, if (InnerLoopGuardCmp) { + dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp + << "\n"; + }); + return InnerLoopGuardCmp; +} + +static bool checkSafeInstruction(const Instruction &I, + const CmpInst *InnerLoopGuardCmp, + const CmpInst *OuterLoopLatchCmp, + Optional OuterLoopLB) { + + bool IsAllowed = + isSafeToSpeculativelyExecute(&I) || isa(I) || isa(I); + if (!IsAllowed) + return false; + // The only binary instruction allowed is the outer loop step instruction, + // the only comparison instructions allowed are the inner loop guard + // compare instruction and the outer loop latch compare instruction. + if ((isa(I) && &I != &OuterLoopLB->getStepInst()) || + (isa(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) { + return false; + } + return true; +} + bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { + return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) == + PerfectLoopNest); +} + +LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest( + const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { + assert(!OuterLoop.isInnermost() && "Outer loop should have subloops"); assert(!InnerLoop.isOutermost() && "Inner loop should have a parent"); LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName() @@ -66,7 +124,7 @@ // the outer loop latch. if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) { LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n"); - return false; + return InvalidLoopStructure; } // Bail out if we cannot retrieve the outer loop bounds. @@ -74,33 +132,11 @@ if (OuterLoopLB == None) { LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: " << OuterLoop << "\n";); - return false; + return OuterLoopLowerBoundUnknown; } - // Identify the outer loop latch comparison instruction. - const BasicBlock *Latch = OuterLoop.getLoopLatch(); - assert(Latch && "Expecting a valid loop latch"); - const BranchInst *BI = dyn_cast(Latch->getTerminator()); - assert(BI && BI->isConditional() && - "Expecting loop latch terminator to be a branch instruction"); - - const CmpInst *OuterLoopLatchCmp = dyn_cast(BI->getCondition()); - DEBUG_WITH_TYPE( - VerboseDebug, if (OuterLoopLatchCmp) { - dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp - << "\n"; - }); - - // Identify the inner loop guard instruction. - BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch(); - const CmpInst *InnerLoopGuardCmp = - (InnerGuard) ? dyn_cast(InnerGuard->getCondition()) : nullptr; - - DEBUG_WITH_TYPE( - VerboseDebug, if (InnerLoopGuardCmp) { - dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp - << "\n"; - }); + CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop); + CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop); // Determine whether instructions in a basic block are one of: // - the inner loop guard comparison @@ -109,29 +145,15 @@ // - a phi node, a cast or a branch auto containsOnlySafeInstructions = [&](const BasicBlock &BB) { return llvm::all_of(BB, [&](const Instruction &I) { - bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa(I) || - isa(I); - if (!isAllowed) { - DEBUG_WITH_TYPE(VerboseDebug, { - dbgs() << "Instruction: " << I << "\nin basic block: " << BB - << " is considered unsafe.\n"; - }); - return false; - } - - // The only binary instruction allowed is the outer loop step instruction, - // the only comparison instructions allowed are the inner loop guard - // compare instruction and the outer loop latch compare instruction. - if ((isa(I) && &I != &OuterLoopLB->getStepInst()) || - (isa(I) && &I != OuterLoopLatchCmp && - &I != InnerLoopGuardCmp)) { + bool IsSafeInstr = checkSafeInstruction(I, InnerLoopGuardCmp, + OuterLoopLatchCmp, OuterLoopLB); + if (IsSafeInstr) { DEBUG_WITH_TYPE(VerboseDebug, { dbgs() << "Instruction: " << I << "\nin basic block:" << BB << "is unsafe.\n"; }); - return false; } - return true; + return IsSafeInstr; }); }; @@ -148,13 +170,72 @@ !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) { LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is " "unsafe\n";); - return false; + return ImperfectLoopNest; } LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '" << InnerLoop.getName() << "' are perfectly nested.\n"); - return true; + return PerfectLoopNest; +} + +LoopNest::InstrVectorTy LoopNest::getInterveningInstructions( + const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { + InstrVectorTy Instr; + switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) { + case PerfectLoopNest: + LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty " + "instruction vector. \n";); + return Instr; + + case InvalidLoopStructure: + LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. " + "Instruction vector is empty.\n";); + return Instr; + + case OuterLoopLowerBoundUnknown: + LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: " + << OuterLoop << "\nInstruction vector is empty.\n";); + return Instr; + + case ImperfectLoopNest: + break; + } + + // Identify the outer loop latch comparison instruction. + auto OuterLoopLB = OuterLoop.getBounds(SE); + + CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop); + CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop); + + auto GetUnsafeInstructions = [&](const BasicBlock &BB) { + for (const Instruction &I : BB) { + if (!checkSafeInstruction(I, InnerLoopGuardCmp, OuterLoopLatchCmp, + OuterLoopLB)) { + Instr.push_back(&I); + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs() << "Instruction: " << I << "\nin basic block:" << BB + << "is unsafe.\n"; + }); + } + } + }; + + // Check the code surrounding the inner loop for instructions that are deemed + // unsafe. + const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); + const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); + const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); + const BasicBlock *InnerLoopExitBlock = InnerLoop.getExitBlock(); + + GetUnsafeInstructions(*OuterLoopHeader); + GetUnsafeInstructions(*OuterLoopLatch); + GetUnsafeInstructions(*InnerLoopExitBlock); + + if (InnerLoopPreHeader != OuterLoopHeader) { + GetUnsafeInstructions(*InnerLoopPreHeader); + } + return Instr; } SmallVector diff --git a/llvm/unittests/Analysis/LoopNestTest.cpp b/llvm/unittests/Analysis/LoopNestTest.cpp --- a/llvm/unittests/Analysis/LoopNestTest.cpp +++ b/llvm/unittests/Analysis/LoopNestTest.cpp @@ -40,6 +40,14 @@ return parseAssemblyString(ModuleStr, Err, Context); } +static Instruction *getInstructionByName(Function &F, StringRef Name) { + for (BasicBlock &BB : F) + for (Instruction &I : BB) + if (I.getName() == Name) + return &I; + llvm_unreachable("Expected to find instruction!"); +} + TEST(LoopNestTest, PerfectLoopNest) { const char *ModuleStr = "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" @@ -106,6 +114,8 @@ // Ensure the nest depth and perfect nest depth are computed correctly. EXPECT_EQ(LN.getNestDepth(), 2u); EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); + + EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty()); }); } @@ -190,6 +200,107 @@ // Ensure the nest depth and perfect nest depth are computed correctly. EXPECT_EQ(LN.getNestDepth(), 3u); EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); + + EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty()); }); } +TEST(LoopNestTest, InterveningInstrLoopNest) { + const char *ModuleStr = + "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" + "define void @foo(i64 signext %nx, i64 signext %ny, i32* noalias %A, i32 " + "%op0, i32 %op1){\n" + "entry:\n" + " br label %for.outer\n" + "for.outer:\n" + " %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n" + " %cmp21 = icmp slt i64 0, %ny\n" + " call void @outerheader()\n" + " br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n" + "for.inner.preheader:\n" + " %varr = getelementptr inbounds i32, i32* %A, i64 5\n" + " store i32 5, i32* %varr, align 4\n" + " call void @innerpreheader()\n" + " br label %for.inner\n" + "for.inner:\n" + " %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n" + " br label %for.inner.latch\n" + "for.inner.latch:\n" + " %inc = add nsw i64 %j, 1\n" + " %cmp2 = icmp slt i64 %inc, %ny\n" + " br i1 %cmp2, label %for.inner, label %for.inner.exit\n" + "for.inner.exit:\n" + " %varr1 = getelementptr inbounds i32, i32* %A, i64 5\n" + " call void @innerexit()\n" + " br label %for.outer.latch\n" + "for.outer.latch:\n" + " %inc13 = add nsw i64 %i, 1\n" + " call void @outerlatch()\n" + " %cmp = icmp slt i64 %inc13, %nx\n" + " br i1 %cmp, label %for.outer, label %for.outer.exit\n" + "for.outer.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n" + "declare void @innerpreheader()\n" + "declare void @outerheader()\n" + "declare void @outerlatch()\n" + "declare void @innerexit()\n"; + + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + Function::iterator FI = F.begin(); + // Skip the first basic block (entry), get to the outer loop header. + BasicBlock *Header = &*(++FI); + assert(Header->getName() == "for.outer"); + Loop *L = LI.getLoopFor(Header); + EXPECT_NE(L, nullptr); + + LoopNest LN(*L, SE); + EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); + + // Ensure that we can identify the outermost loop in the nest. + const Loop &OL = LN.getOutermostLoop(); + EXPECT_EQ(OL.getName(), "for.outer"); + + // Ensure that we can identify the innermost loop in the nest. + const Loop *IL = LN.getInnermostLoop(); + EXPECT_NE(IL, nullptr); + EXPECT_EQ(IL->getName(), "for.inner"); + + // Ensure the loop nest is recognized as having 2 loops. + const ArrayRef Loops = LN.getLoops(); + EXPECT_EQ(Loops.size(), 2ull); + + // Ensure the loop nest is not recognized as perfect in its entirety. + const SmallVector &PLV = LN.getPerfectLoops(SE); + EXPECT_EQ(PLV.size(), 2ull); + EXPECT_EQ(PLV.front().size(), 1ull); + EXPECT_EQ(PLV.back().size(), 1ull); + + // Ensure the nest depth and perfect nest depth are computed correctly. + EXPECT_EQ(LN.getNestDepth(), 2u); + EXPECT_EQ(LN.getMaxPerfectDepth(), 1u); + + // Ensure enclosed instructions are recognized + const LoopNest::InstrVectorTy InstrV = + LN.getInterveningInstructions(OL, *IL, SE); + EXPECT_EQ(InstrV.size(), 5u); + + Instruction *SI = getInstructionByName(F, "varr")->getNextNode(); + Instruction *CI = SI->getNextNode(); + Instruction *OLH = + getInstructionByName(F, "i")->getNextNode()->getNextNode(); + Instruction *OLL = getInstructionByName(F, "inc13")->getNextNode(); + Instruction *IE = getInstructionByName(F, "varr1")->getNextNode(); + + EXPECT_EQ(InstrV.front(), OLH); + EXPECT_EQ(InstrV[1], OLL); + EXPECT_EQ(InstrV[2], IE); + EXPECT_EQ(InstrV[3], SI); + EXPECT_EQ(InstrV.back(), CI); + }); +}