Index: lib/Transforms/Vectorize/VPlanHCFGTransforms.h =================================================================== --- lib/Transforms/Vectorize/VPlanHCFGTransforms.h +++ lib/Transforms/Vectorize/VPlanHCFGTransforms.h @@ -17,20 +17,25 @@ #include "LoopVectorizationPlanner.h" #include "VPlan.h" #include "llvm/IR/Instruction.h" - +#include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h" namespace llvm { class VPlanHCFGTransforms { - using VPlanPtr = std::unique_ptr; public: /// Sinks instructions in \p Plan, depending on their underlying values in /// \p SinkAfter. - // FIXME: Migrate to using a VPlan based mapping, once - // LoopVectorizationLegality::getSinkAfter is moved to VPlan. static void sinkInstructions(VPlanPtr &Plan, DenseMap &SinkAfter); + + /// Creates a new VPlan using VPRecipes from a VPInstruction VPlan + /// \p OriginalPlan + static void VPInstructionsToVPRecipes( + VPlanPtr &OriginalPlan, + LoopVectorizationLegality::InductionList *Inductions, + SmallPtrSetImpl &DeadInstructions); }; } // namespace llvm Index: lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp =================================================================== --- lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp +++ lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp @@ -55,3 +55,58 @@ } } } + +void VPlanHCFGTransforms::VPInstructionsToVPRecipes( + VPlanPtr &OriginalPlan, + LoopVectorizationLegality::InductionList *Inductions, + SmallPtrSetImpl &DeadInstructions) { + + VPRegionBlock *TopRegion = dyn_cast(OriginalPlan->getEntry()); + ReversePostOrderTraversal RPOT(TopRegion->getEntry()); + for (VPBlockBase *Base : RPOT) { + // Do not widen instructions in pre-header and exit blocks. + if (Base->getNumPredecessors() == 0 || Base->getNumSuccessors() == 0) + continue; + + VPBasicBlock *VPBB = Base->getEntryBasicBlock(); + VPRecipeBase *LastRecipe = nullptr; + // Introduce each ingredient into VPlan. + for (auto I = VPBB->begin(), E = VPBB->end(); I != E;) { + VPRecipeBase *Ingredient = &*I++; + // Can only handle VPInstructions. + VPInstruction *VPInst = cast(Ingredient); + Instruction *Inst = cast(VPInst->getUnderlyingValue()); + if (DeadInstructions.count(Inst)) { + Ingredient->eraseFromParent(); + continue; + } + + VPRecipeBase *NewRecipe = nullptr; + // Create VPWidenMemoryInstructionRecipe for loads and stores. + if (isa(Inst) || isa(Inst)) + NewRecipe = new VPWidenMemoryInstructionRecipe(*Inst, nullptr /*Mask*/); + else if (PHINode *Phi = dyn_cast(Inst)) { + InductionDescriptor II = Inductions->lookup(Phi); + if (II.getKind() == InductionDescriptor::IK_IntInduction || + II.getKind() == InductionDescriptor::IK_FpInduction) { + NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi); + } else + NewRecipe = new VPWidenPHIRecipe(Phi); + } else { + // If the last recipe is a VPWidenRecipe, add Inst to it instead of + // creating a new recipe. + if (VPWidenRecipe *WidenRecipe = + dyn_cast_or_null(LastRecipe)) { + WidenRecipe->appendInstruction(Inst); + Ingredient->eraseFromParent(); + continue; + } + NewRecipe = new VPWidenRecipe(Inst); + } + + NewRecipe->insertBefore(Ingredient); + LastRecipe = NewRecipe; + Ingredient->eraseFromParent(); + } + } +} Index: unittests/Transforms/Vectorize/CMakeLists.txt =================================================================== --- unittests/Transforms/Vectorize/CMakeLists.txt +++ unittests/Transforms/Vectorize/CMakeLists.txt @@ -1,7 +1,9 @@ set(LLVM_LINK_COMPONENTS Vectorize + AsmParser ) add_llvm_unittest(VectorizeTests VPlanTest.cpp + VPlanHCFGTest.cpp ) Index: unittests/Transforms/Vectorize/VPlanHCFGTest.cpp =================================================================== --- /dev/null +++ unittests/Transforms/Vectorize/VPlanHCFGTest.cpp @@ -0,0 +1,178 @@ +//===- llvm/unittest/Transforms/Vectorize/VPlanHCFGTest.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/VPlan.h" +#include "../lib/Transforms/Vectorize/VPlanHCFGBuilder.h" +#include "../lib/Transforms/Vectorize/VPlanHCFGTransforms.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Dominators.h" +#include "gtest/gtest.h" + +namespace llvm { +namespace { + +class VPlanHCFGTest : public testing::Test { +protected: + std::unique_ptr DT; + std::unique_ptr LI; + + VPlanHCFGTest() {} + + VPlanPtr doBuildPlan(BasicBlock *LoopHeader) { + DT.reset(new DominatorTree(*LoopHeader->getParent())); + LI.reset(new LoopInfo(*DT)); + + auto Plan = llvm::make_unique(); + VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get()); + HCFGBuilder.buildHierarchicalCFG(*Plan.get()); + return Plan; + } +}; + +TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) { + LLVMContext Ctx; + const char *ModuleString = + "define void @f(i32* %A, i64 %N) {\n" + "entry:\n" + " br label %for.body\n" + "for.body:\n" + " %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n" + " %arr.idx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n" + " %l1 = load i32, i32* %arr.idx, align 4\n" + " %res = add i32 %l1, 10\n" + " store i32 %res, i32* %arr.idx, align 4\n" + " %indvars.iv.next = add i64 %indvars.iv, 1\n" + " %exitcond = icmp ne i64 %indvars.iv.next, %N\n" + " br i1 %exitcond, label %for.body, label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + SMDiagnostic Err; + std::unique_ptr M = parseAssemblyString(ModuleString, Err, Ctx); + + Function *F = M->getFunction("f"); + BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor(); + auto Plan = doBuildPlan(LoopHeader); + + VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock(); + EXPECT_NE(nullptr, Entry->getSingleSuccessor()); + EXPECT_EQ(0u, Entry->getNumPredecessors()); + EXPECT_EQ(1u, Entry->getNumSuccessors()); + + VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock(); + EXPECT_EQ(7u, VecBB->size()); + EXPECT_EQ(2u, VecBB->getNumPredecessors()); + EXPECT_EQ(2u, VecBB->getNumSuccessors()); + + auto Iter = VecBB->begin(); + VPInstruction *Phi = dyn_cast(&*Iter++); + EXPECT_EQ(Instruction::PHI, Phi->getOpcode()); + + VPInstruction *Idx = dyn_cast(&*Iter++); + EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode()); + EXPECT_EQ(2u, Idx->getNumOperands()); + EXPECT_EQ(Phi, Idx->getOperand(1)); + + VPInstruction *Load = dyn_cast(&*Iter++); + EXPECT_EQ(Instruction::Load, Load->getOpcode()); + EXPECT_EQ(1u, Load->getNumOperands()); + EXPECT_EQ(Idx, Load->getOperand(0)); + + VPInstruction *Add = dyn_cast(&*Iter++); + EXPECT_EQ(Instruction::Add, Add->getOpcode()); + EXPECT_EQ(2u, Add->getNumOperands()); + EXPECT_EQ(Load, Add->getOperand(0)); + + VPInstruction *Store = dyn_cast(&*Iter++); + EXPECT_EQ(Instruction::Store, Store->getOpcode()); + EXPECT_EQ(2u, Store->getNumOperands()); + EXPECT_EQ(Add, Store->getOperand(0)); + EXPECT_EQ(Idx, Store->getOperand(1)); + + VPInstruction *IndvarAdd = dyn_cast(&*Iter++); + EXPECT_EQ(Instruction::Add, IndvarAdd->getOpcode()); + EXPECT_EQ(2u, IndvarAdd->getNumOperands()); + EXPECT_EQ(Phi, IndvarAdd->getOperand(0)); + + VPInstruction *ICmp = dyn_cast(&*Iter++); + EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode()); + EXPECT_EQ(2u, ICmp->getNumOperands()); + EXPECT_EQ(IndvarAdd, ICmp->getOperand(0)); + + LoopVectorizationLegality::InductionList Inductions; + SmallPtrSet DeadInstructions; + VPlanHCFGTransforms::VPInstructionsToVPRecipes(Plan, &Inductions, + DeadInstructions); +} + +TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) { + LLVMContext Ctx; + const char *ModuleString = + "define void @f(i32* %A, i64 %N) {\n" + "entry:\n" + " br label %for.body\n" + "for.body:\n" + " %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n" + " %arr.idx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n" + " %l1 = load i32, i32* %arr.idx, align 4\n" + " %res = add i32 %l1, 10\n" + " store i32 %res, i32* %arr.idx, align 4\n" + " %indvars.iv.next = add i64 %indvars.iv, 1\n" + " %exitcond = icmp ne i64 %indvars.iv.next, %N\n" + " br i1 %exitcond, label %for.body, label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + SMDiagnostic Err; + std::unique_ptr M = parseAssemblyString(ModuleString, Err, Ctx); + + Function *F = M->getFunction("f"); + BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor(); + auto Plan = doBuildPlan(LoopHeader); + + LoopVectorizationLegality::InductionList Inductions; + SmallPtrSet DeadInstructions; + VPlanHCFGTransforms::VPInstructionsToVPRecipes(Plan, &Inductions, + DeadInstructions); + + VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock(); + EXPECT_NE(nullptr, Entry->getSingleSuccessor()); + EXPECT_EQ(0u, Entry->getNumPredecessors()); + EXPECT_EQ(1u, Entry->getNumSuccessors()); + + VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock(); + EXPECT_EQ(6u, VecBB->size()); + EXPECT_EQ(2u, VecBB->getNumPredecessors()); + EXPECT_EQ(2u, VecBB->getNumSuccessors()); + + auto Iter = VecBB->begin(); + auto *Phi = dyn_cast(&*Iter++); + EXPECT_NE(nullptr, Phi); + + auto *Idx = dyn_cast(&*Iter++); + EXPECT_NE(nullptr, Idx); + + auto *Load = dyn_cast(&*Iter++); + EXPECT_NE(nullptr, Load); + + auto *Add = dyn_cast(&*Iter++); + EXPECT_NE(nullptr, Add); + + auto *Store = dyn_cast(&*Iter++); + EXPECT_NE(nullptr, Store); + + auto *LastWiden = dyn_cast(&*Iter++); + EXPECT_NE(nullptr, LastWiden); + EXPECT_EQ(VecBB->end(), Iter); +} + +} // namespace +} // namespace llvm