Index: lib/Transforms/Vectorize/VPlan.h =================================================================== --- lib/Transforms/Vectorize/VPlan.h +++ lib/Transforms/Vectorize/VPlan.h @@ -53,9 +53,13 @@ class InnerLoopVectorizer; class InterleaveGroup; class LoopInfo; +template class LoopInfoBase; class raw_ostream; class Value; class VPBasicBlock; +class VPBlockBase; +class VPLoop; +typedef LoopInfoBase VPLoopInfo; class VPRegionBlock; class VPlan; @@ -527,6 +531,13 @@ // support for VPInstructions/Recipes. printAsOperand(OS, false); } + + /// Return true if it is legal to hoist instructions into this block. + bool isLegalToHoistInto() { + // There are currently no constraints that prevent an instruction to be + // hoisted into a VPBlockBase. + return true; + } }; /// VPRecipeBase is a base class modeling a sequence of one or more output IR @@ -1108,17 +1119,12 @@ /// VPlan. Value2VPValueTy Value2VPValue; + /// Holds the VPLoopInfo analysis for this VPlan. + VPLoopInfo *VPLInfo = nullptr; + public: VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {} - - ~VPlan() { - if (Entry) - VPBlockBase::deleteCFG(Entry); - for (auto &MapEntry : Value2VPValue) - delete MapEntry.second; - for (VPValue *Def : VPExternalDefs) - delete Def; - } + ~VPlan(); /// Generate the IR code for this VPlan. void execute(struct VPTransformState *State); @@ -1154,6 +1160,13 @@ return Value2VPValue[V]; } + /// Return the VPLoopInfo analysis for this VPlan. + VPLoopInfo *getVPLoopInfo() { return VPLInfo; } + const VPLoopInfo *getVPLoopInfo() const { return VPLInfo; } + + /// Set the VPLoopInfo analysis for this VPlan. + void setVPLoopInfo(VPLoopInfo *VPLI) { VPLInfo = VPLI; } + private: /// Add to the given dominator tree the header block and every new basic block /// that was created between it and the latch block, inclusive. Index: lib/Transforms/Vectorize/VPlan.cpp =================================================================== --- lib/Transforms/Vectorize/VPlan.cpp +++ lib/Transforms/Vectorize/VPlan.cpp @@ -19,6 +19,7 @@ #include "VPlan.h" #include "VPlanDominatorTree.h" +#include "VPlanLoopInfo.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallVector.h" @@ -294,6 +295,17 @@ } } +VPlan::~VPlan() { + if (Entry) + VPBlockBase::deleteCFG(Entry); + for (auto &MapEntry : Value2VPValue) + delete MapEntry.second; + if (VPLInfo) + delete (VPLInfo); + for (VPValue *Def : VPExternalDefs) + delete Def; +} + /// Generate the code inside the body of the vectorized loop. Assumes a single /// LoopVectorBody basic-block was created for this. Introduce additional /// basic-blocks as needed, and fill them all. Index: lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp =================================================================== --- lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp +++ lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp @@ -24,6 +24,7 @@ #include "VPlanHCFGBuilder.h" #include "LoopVectorizationPlanner.h" +#include "VPlanLoopInfo.h" #include "llvm/Analysis/LoopIterator.h" #define DEBUG_TYPE "loop-vectorize" @@ -342,4 +343,11 @@ VPDomTree.recalculate(*TopRegion); LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n"; VPDomTree.print(dbgs())); + + // Compute VPLInfo and keep it in Plan. + VPLoopInfo *VPLInfo = new VPLoopInfo(); + VPLInfo->analyze(VPDomTree); + Plan.setVPLoopInfo(VPLInfo); + LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n"; + VPLInfo->print(dbgs())); } Index: lib/Transforms/Vectorize/VPlanLoopInfo.h =================================================================== --- /dev/null +++ lib/Transforms/Vectorize/VPlanLoopInfo.h @@ -0,0 +1,45 @@ +//===-- VPLoopInfo.h --------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file defines VPLoopInfo analysis and VPLoop class. VPLoopInfo is a +/// specialization of LoopInfoBase for VPBlockBase. VPLoops is a specialization +/// of LoopBase that is used to hold loop metadata from VPLoopInfo. Further +/// information can be found in VectorizationPlanner.rst. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H +#define LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H + +#include "llvm/Analysis/LoopInfoImpl.h" + +namespace llvm { +class VPBlockBase; + +/// Hold analysis information for every loop detected by VPLoopInfo. It is an +/// instantiation of LoopBase. +class VPLoop : public LoopBase { +private: + friend class LoopInfoBase; + explicit VPLoop(VPBlockBase *VPB) : LoopBase(VPB) {} +}; + +/// VPLoopInfo provides analysis of natural loop for VPBlockBase-based +/// Hierarchical CFG. It is a specialization of LoopInfoBase class. +// TODO: VPLoopInfo is initially computed on top of the VPlan plain CFG, which +// is the same as the incoming IR CFG. If it's more efficient than running the +// whole loop detection algorithm, we may want to create a mechanism to +// translate LoopInfo into VPLoopInfo. However, that would require significant +// changes in LoopInfoBase class. +typedef LoopInfoBase VPLoopInfo; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H Index: unittests/Transforms/Vectorize/CMakeLists.txt =================================================================== --- unittests/Transforms/Vectorize/CMakeLists.txt +++ unittests/Transforms/Vectorize/CMakeLists.txt @@ -7,6 +7,7 @@ add_llvm_unittest(VectorizeTests VPlanDominatorTreeTest.cpp + VPlanLoopInfoTest.cpp VPlanTest.cpp VPlanHCFGTest.cpp ) Index: unittests/Transforms/Vectorize/VPlanLoopInfoTest.cpp =================================================================== --- /dev/null +++ unittests/Transforms/Vectorize/VPlanLoopInfoTest.cpp @@ -0,0 +1,114 @@ +//===- llvm/unittests/Transforms/Vectorize/VPlanLoopInfoTest.cpp -----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "../lib/Transforms/Vectorize/VPlanLoopInfo.h" +#include "../lib/Transforms/Vectorize/VPlanHCFGBuilder.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/SourceMgr.h" +#include "gtest/gtest.h" + +using namespace llvm; + +/// Build the VPlan plain CFG for the loop nest in function \p FuncName. +static std::unique_ptr buildVPlanPlainCFG(Module &M, + StringRef FuncName) { + auto *F = M.getFunction(FuncName); + assert(F && "Could not find function!"); + BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor(); + + DominatorTree DT(*LoopHeader->getParent()); + LoopInfo LI(DT); + + auto Plan = llvm::make_unique(); + VPlanHCFGBuilder HCFGBuilder(LI.getLoopFor(LoopHeader), &LI, *Plan.get()); + VPRegionBlock *TopRegion = HCFGBuilder.buildPlainCFG(); + Plan->setEntry(TopRegion); + return Plan; +} + +static std::unique_ptr makeLLVMModule(LLVMContext &Context, + StringRef ModuleStr) { + SMDiagnostic Err; + std::unique_ptr M = parseAssemblyString(ModuleStr, Err, Context); + assert(M && "Bad assembly?"); + return M; +} + +TEST(VPlanLoopInfoTree, BasicLoopInfoTest) { + StringRef ModuleString = + "define void @f(i32* %a, i32* %b, i32* %c, i32 %N, i32 %M, i32 %K) {\n" + "entry:\n" + " br label %for.body\n" + "\n" + "for.body:\n" + " %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.inc ]\n" + " br i1 true, label %if.then, label %if.else\n" + "\n" + "if.then:\n" + " br label %for.inc\n" + "\n" + "if.else:\n" + " br label %for.inc\n" + "for.inc:\n" + " %iv.next = add nuw nsw i64 %iv, 1\n" + " %exitcond = icmp eq i64 %iv.next, 300\n" + " br i1 %exitcond, label %for.end, label %for.body\n" + "\n" + "for.end:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + // Build VPlan plain CFG, VPDominatorTree and VPLoopInfo analyses. + std::unique_ptr Plan = buildVPlanPlainCFG(*M, "f"); + VPRegionBlock *TopRegion = cast(Plan->getEntry()); + VPDominatorTree VPDT; + VPDT.recalculate(*TopRegion); + VPLoopInfo VPLI; + VPLI.analyze(VPDT); + + VPBlockBase *PH = TopRegion->getEntry(); + VPBlockBase *H = PH->getSingleSuccessor(); + VPBlockBase *IfThen = H->getSuccessors()[0]; + VPBlockBase *IfElse = H->getSuccessors()[1]; + VPBlockBase *Latch = IfThen->getSingleSuccessor(); + VPBlockBase *Exit = Latch->getSuccessors()[0] != H + ? Latch->getSuccessors()[0] + : Latch->getSuccessors()[1]; + + // Number of loops. + EXPECT_EQ(1, std::distance(VPLI.begin(), VPLI.end())); + VPLoop *VPLp = *VPLI.begin(); + + // VPBBs contained in VPLoop. + EXPECT_FALSE(VPLp->contains(PH)); + EXPECT_EQ(nullptr, VPLI.getLoopFor(PH)); + EXPECT_TRUE(VPLp->contains(H)); + EXPECT_EQ(VPLp, VPLI.getLoopFor(H)); + EXPECT_TRUE(VPLp->contains(IfThen)); + EXPECT_EQ(VPLp, VPLI.getLoopFor(IfThen)); + EXPECT_TRUE(VPLp->contains(IfElse)); + EXPECT_EQ(VPLp, VPLI.getLoopFor(IfElse)); + EXPECT_TRUE(VPLp->contains(Latch)); + EXPECT_EQ(VPLp, VPLI.getLoopFor(Latch)); + EXPECT_FALSE(VPLp->contains(Exit)); + EXPECT_EQ(nullptr, VPLI.getLoopFor(Exit)); + + // VPLoop's parts. + EXPECT_EQ(PH, VPLp->getLoopPreheader()); + EXPECT_EQ(H, VPLp->getHeader()); + EXPECT_EQ(Latch, VPLp->getLoopLatch()); + EXPECT_EQ(Latch, VPLp->getExitingBlock()); + EXPECT_EQ(Exit, VPLp->getExitBlock()); +}