Index: llvm/trunk/lib/Transforms/Vectorize/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Transforms/Vectorize/CMakeLists.txt +++ llvm/trunk/lib/Transforms/Vectorize/CMakeLists.txt @@ -6,6 +6,7 @@ Vectorize.cpp VPlan.cpp VPlanHCFGBuilder.cpp + VPlanHCFGTransforms.cpp VPlanVerifier.cpp ADDITIONAL_HEADER_DIRS Index: llvm/trunk/lib/Transforms/Vectorize/VPlan.h =================================================================== --- llvm/trunk/lib/Transforms/Vectorize/VPlan.h +++ llvm/trunk/lib/Transforms/Vectorize/VPlan.h @@ -568,6 +568,8 @@ /// executed, these instructions would always form a single-def expression as /// the VPInstruction is also a single def-use vertex. class VPInstruction : public VPUser, public VPRecipeBase { + friend class VPlanHCFGTransforms; + public: /// VPlan opcodes, extending LLVM IR with idiomatics instructions. enum { Not = Instruction::OtherOpsEnd + 1 }; Index: llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGTransforms.h =================================================================== --- llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGTransforms.h +++ llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGTransforms.h @@ -0,0 +1,36 @@ +//===- VPlanHCFGTransforms.h - Utility VPlan to VPlan transforms ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file provides utility VPlan to VPlan transformations. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANHCFGTRANSFORMS_H +#define LLVM_TRANSFORMS_VECTORIZE_VPLANHCFGTRANSFORMS_H + +#include "VPlan.h" +#include "llvm/IR/Instruction.h" +#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h" + +namespace llvm { + +class VPlanHCFGTransforms { + +public: + /// Replaces the VPInstructions in \p Plan with corresponding + /// widen recipes. + static void VPInstructionsToVPRecipes( + VPlanPtr &Plan, + LoopVectorizationLegality::InductionList *Inductions, + SmallPtrSetImpl &DeadInstructions); +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANHCFGTRANSFORMS_H Index: llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp =================================================================== --- llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp +++ llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp @@ -0,0 +1,73 @@ +//===-- VPlanHCFGTransforms.cpp - Utility VPlan to VPlan transforms -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file implements a set of utility VPlan to VPlan transformations. +/// +//===----------------------------------------------------------------------===// + +#include "VPlanHCFGTransforms.h" +#include "llvm/ADT/PostOrderIterator.h" + +using namespace llvm; + +void VPlanHCFGTransforms::VPInstructionsToVPRecipes( + VPlanPtr &Plan, + LoopVectorizationLegality::InductionList *Inductions, + SmallPtrSetImpl &DeadInstructions) { + + VPRegionBlock *TopRegion = dyn_cast(Plan->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: llvm/trunk/unittests/Transforms/Vectorize/CMakeLists.txt =================================================================== --- llvm/trunk/unittests/Transforms/Vectorize/CMakeLists.txt +++ llvm/trunk/unittests/Transforms/Vectorize/CMakeLists.txt @@ -1,7 +1,9 @@ set(LLVM_LINK_COMPONENTS Vectorize + AsmParser ) add_llvm_unittest(VectorizeTests VPlanTest.cpp + VPlanHCFGTest.cpp ) Index: llvm/trunk/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp =================================================================== --- llvm/trunk/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp +++ llvm/trunk/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