diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -7349,15 +7349,21 @@ } void VPInterleaveRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPInterleaveRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"INTERLEAVE-GROUP with factor " << IG->getFactor() << " at "; IG->getInsertPos()->printAsOperand(O, false); O << ", "; - getAddr()->printAsOperand(O); + getAddr()->printAsOperand(O, SlotTracker); VPValue *Mask = getMask(); if (Mask) { O << ", "; - Mask->printAsOperand(O); + Mask->printAsOperand(O, SlotTracker); } O << "\\l\""; for (unsigned i = 0; i < IG->getFactor(); ++i) diff --git a/llvm/lib/Transforms/Vectorize/VPlan.h b/llvm/lib/Transforms/Vectorize/VPlan.h --- a/llvm/lib/Transforms/Vectorize/VPlan.h +++ b/llvm/lib/Transforms/Vectorize/VPlan.h @@ -634,6 +634,8 @@ /// Each recipe prints itself. virtual void print(raw_ostream &O, const Twine &Indent) const = 0; + virtual void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const = 0; /// Insert an unlinked recipe into a basic block immediately before /// the specified recipe. @@ -720,9 +722,12 @@ /// Print the Recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; /// Print the VPInstruction. void print(raw_ostream &O) const; + void print(raw_ostream &O, VPSlotTracker &SlotTracker) const; /// Return true if this instruction may modify memory. bool mayWriteToMemory() const { @@ -769,6 +774,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// A recipe for handling GEP instructions. @@ -799,6 +806,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// A recipe for handling phi nodes of integer and floating-point inductions, @@ -824,6 +833,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// A recipe for handling all phi nodes except for integer and FP inductions. @@ -845,6 +856,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// A recipe for vectorizing a phi-node as a sequence of mask-based select @@ -876,6 +889,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// VPInterleaveRecipe is a recipe for transforming an interleave group of load @@ -916,6 +931,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; const InterleaveGroup *getInterleaveGroup() { return IG; } }; @@ -966,6 +983,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// A recipe for generating conditional branches on the bits of a mask. @@ -989,10 +1008,13 @@ void execute(VPTransformState &State) override; /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override { + void print(raw_ostream &O, const Twine &Indent) const override; + + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override { O << " +\n" << Indent << "\"BRANCH-ON-MASK "; if (User) - O << *User->getOperand(0); + User->getOperand(0)->print(O, SlotTracker); else O << " All-One"; O << "\\l\""; @@ -1025,6 +1047,9 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// A Recipe for widening load/store operations. @@ -1065,6 +1090,8 @@ /// Print the recipe. void print(raw_ostream &O, const Twine &Indent) const override; + void print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const override; }; /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It @@ -1352,6 +1379,7 @@ } }; +class VPSlotTracker; /// VPlan models a candidate for vectorization, encoding various decisions take /// to produce efficient output IR, including which branches, basic-blocks and /// output IR instructions to generate, and their cost. VPlan holds a @@ -1359,6 +1387,7 @@ /// VPBlock. class VPlan { friend class VPlanPrinter; + friend class VPSlotTracker; private: /// Hold the single entry to the Hierarchical CFG of the VPlan. @@ -1392,7 +1421,10 @@ SmallVector VPCBVs; public: - VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {} + VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) { + if (Entry) + Entry->setPlan(this); + } ~VPlan() { if (Entry) @@ -1496,7 +1528,10 @@ unsigned BID = 0; SmallDenseMap BlockID; - VPlanPrinter(raw_ostream &O, const VPlan &P) : OS(O), Plan(P) {} + VPSlotTracker SlotTracker; + + VPlanPrinter(raw_ostream &O, const VPlan &P) + : OS(O), Plan(P), SlotTracker(&P) {} /// Handle indentation. void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); } diff --git a/llvm/lib/Transforms/Vectorize/VPlan.cpp b/llvm/lib/Transforms/Vectorize/VPlan.cpp --- a/llvm/lib/Transforms/Vectorize/VPlan.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlan.cpp @@ -48,12 +48,11 @@ #define DEBUG_TYPE "vplan" -raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) { - if (const VPInstruction *Instr = dyn_cast(&V)) - Instr->print(OS); +void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const { + if (const VPInstruction *Instr = dyn_cast(this)) + Instr->print(OS, SlotTracker); else - V.printAsOperand(OS); - return OS; + printAsOperand(OS, SlotTracker); } // Get the top-most entry block of \p Start. This is the entry block of the @@ -377,13 +376,24 @@ } void VPInstruction::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPInstruction::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"EMIT "; - print(O); + print(O, SlotTracker); O << "\\l\""; } void VPInstruction::print(raw_ostream &O) const { - printAsOperand(O); + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, SlotTracker); +} + +void VPInstruction::print(raw_ostream &O, VPSlotTracker &SlotTracker) const { + printAsOperand(O, SlotTracker); O << " = "; switch (getOpcode()) { @@ -405,7 +415,7 @@ for (const VPValue *Operand : operands()) { O << " "; - Operand->printAsOperand(O); + Operand->printAsOperand(O, SlotTracker); } } @@ -559,10 +569,14 @@ OS << "\\n" << DOT::EscapeString(Plan.getName()); if (!Plan.Value2VPValue.empty() || Plan.BackedgeTakenCount) { OS << ", where:"; - if (Plan.BackedgeTakenCount) - OS << "\\n" << *Plan.BackedgeTakenCount << " := BackedgeTakenCount"; + if (Plan.BackedgeTakenCount) { + OS << "\\n"; + Plan.BackedgeTakenCount->print(OS, SlotTracker); + OS << " := BackedgeTakenCount"; + } for (auto Entry : Plan.Value2VPValue) { - OS << "\\n" << *Entry.second; + OS << "\\n"; + Entry.second->print(OS, SlotTracker); OS << DOT::EscapeString(" := "); Entry.first->printAsOperand(OS, false); } @@ -629,25 +643,25 @@ if (Pred) { OS << " +\n" << Indent << " \"BlockPredicate: "; if (const VPInstruction *PredI = dyn_cast(Pred)) { - PredI->printAsOperand(OS); + PredI->printAsOperand(OS, SlotTracker); OS << " (" << DOT::EscapeString(PredI->getParent()->getName()) << ")\\l\""; } else - Pred->printAsOperand(OS); + Pred->printAsOperand(OS, SlotTracker); } for (const VPRecipeBase &Recipe : *BasicBlock) - Recipe.print(OS, Indent); + Recipe.print(OS, Indent, SlotTracker); // Dump the condition bit. const VPValue *CBV = BasicBlock->getCondBit(); if (CBV) { OS << " +\n" << Indent << " \"CondBit: "; if (const VPInstruction *CBI = dyn_cast(CBV)) { - CBI->printAsOperand(OS); + CBI->printAsOperand(OS, SlotTracker); OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\""; } else { - CBV->printAsOperand(OS); + CBV->printAsOperand(OS, SlotTracker); OS << "\""; } } @@ -695,6 +709,12 @@ } void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"WIDEN\\l\""; for (auto &Instr : make_range(Begin, End)) O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\""; @@ -702,6 +722,12 @@ void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"WIDEN-INDUCTION"; if (Trunc) { O << "\\l\""; @@ -712,6 +738,12 @@ } void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"WIDEN-GEP "; O << (IsPtrLoopInvariant ? "Inv" : "Var"); size_t IndicesNumber = IsIndexLoopInvariant.size(); @@ -722,10 +754,22 @@ } void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\""; } void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"BLEND "; Phi->printAsOperand(O, false); O << " ="; @@ -739,13 +783,19 @@ O << " "; Phi->getIncomingValue(I)->printAsOperand(O, false); O << "/"; - User->getOperand(I)->printAsOperand(O); + User->getOperand(I)->printAsOperand(O, SlotTracker); } } O << "\\l\""; } void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ") << VPlanIngredient(Ingredient); @@ -754,7 +804,18 @@ O << "\\l\""; } +void VPBranchOnMaskRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst) << "\\l\""; @@ -762,13 +823,19 @@ void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent) const { + VPSlotTracker SlotTracker(getParent()->getPlan()); + print(O, Indent, SlotTracker); +} + +void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent, + VPSlotTracker &SlotTracker) const { O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr); O << ", "; - getAddr()->printAsOperand(O); + getAddr()->printAsOperand(O, SlotTracker); VPValue *Mask = getMask(); if (Mask) { O << ", "; - Mask->printAsOperand(O); + Mask->printAsOperand(O, SlotTracker); } O << "\\l\""; } @@ -782,6 +849,14 @@ User->setOperand(I, New); } +void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const { + unsigned Slot = Tracker.getSlot(this); + if (Slot == unsigned(-1)) + OS << ""; + else + OS << "%vp" << Tracker.getSlot(this); +} + void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New, InterleavedAccessInfo &IAI) { @@ -827,3 +902,48 @@ Old2NewTy Old2New; visitRegion(cast(Plan.getEntry()), Old2New, IAI); } + +void VPSlotTracker::assignSlot(const VPValue *V) { + assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!"); + Slots[V] = NextSlot++; +} + +void VPSlotTracker::assignSlots(const VPBlockBase *VPBB) { + if (auto *Region = dyn_cast(VPBB)) + assignSlots(Region); + else + assignSlots(cast(VPBB)); +} + +void VPSlotTracker::assignSlots(const VPRegionBlock *Region) { + ReversePostOrderTraversal RPOT(Region->getEntry()); + for (const VPBlockBase *Block : RPOT) + assignSlots(Block); +} + +void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) { + for (const VPRecipeBase &Recipe : *VPBB) { + if (const auto *VPI = dyn_cast(&Recipe)) + assignSlot(VPI); + } +} + +void VPSlotTracker::assignSlots(const VPlan &Plan) { + + for (const VPValue *V : Plan.VPExternalDefs) + assignSlot(V); + + for (auto &E : Plan.Value2VPValue) + if (!isa(E.second)) + assignSlot(E.second); + + for (const VPValue *V : Plan.VPCBVs) + assignSlot(V); + + if (Plan.BackedgeTakenCount) + assignSlot(Plan.BackedgeTakenCount); + + ReversePostOrderTraversal RPOT(Plan.getEntry()); + for (const VPBlockBase *Block : RPOT) + assignSlots(Block); +} diff --git a/llvm/lib/Transforms/Vectorize/VPlanValue.h b/llvm/lib/Transforms/Vectorize/VPlanValue.h --- a/llvm/lib/Transforms/Vectorize/VPlanValue.h +++ b/llvm/lib/Transforms/Vectorize/VPlanValue.h @@ -31,6 +31,8 @@ // Forward declarations. class VPUser; +class VPSlotTracker; + // This is the base class of the VPlan Def/Use graph, used for modeling the data // flow into, within and out of the VPlan. VPValues can stand for live-ins // coming from the input IR, instructions which VPlan will generate if executed @@ -85,9 +87,8 @@ /// for any other purpose, as the values may change as LLVM evolves. unsigned getVPValueID() const { return SubclassID; } - void printAsOperand(raw_ostream &OS) const { - OS << "%vp" << (unsigned short)(unsigned long long)this; - } + void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const; + void print(raw_ostream &OS, VPSlotTracker &Tracker) const; unsigned getNumUsers() const { return Users.size(); } void addUser(VPUser &User) { Users.push_back(&User); } @@ -124,7 +125,7 @@ typedef DenseMap Value2VPValueTy; typedef DenseMap VPValue2ValueTy; -raw_ostream &operator<<(raw_ostream &OS, const VPValue &V); +// raw_ostream &operator<<(raw_ostream &OS, const VPValue &V); /// This class augments VPValue with operands which provide the inverse def-use /// edges from VPValue's users to their defs. @@ -180,6 +181,38 @@ return const_operand_range(op_begin(), op_end()); } }; +class VPlan; +class VPBasicBlock; +class VPRegionBlock; + +/// This class can be used to assign consecutive numbers to all VPValues in a +/// VPlan and allows querying the numbering for printing, similar to the +/// ModuleSlotTracker for IR values. +class VPSlotTracker { +private: + DenseMap Slots; + unsigned NextSlot = 0; + + void assignSlots(const VPBlockBase *VPBB); + void assignSlots(const VPRegionBlock *Region); + void assignSlots(const VPBasicBlock *VPBB); + void assignSlot(const VPValue *V); + + void assignSlots(const VPlan &Plan); + +public: + VPSlotTracker(const VPlan *Plan) { + if (Plan) + assignSlots(*Plan); + } + + unsigned getSlot(const VPValue *V) const { + auto I = Slots.find(V); + if (I == Slots.end()) + return -1; + return I->second; + } +}; } // namespace llvm diff --git a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp --- a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp +++ b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp @@ -11,6 +11,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "gtest/gtest.h" +#include namespace llvm { namespace { @@ -86,5 +87,67 @@ EXPECT_EQ(I3->getParent(), I4->getParent()); } +TEST(VPInstructionTest, print) { + VPInstruction *I1 = new VPInstruction(10, {}); + VPInstruction *I2 = new VPInstruction(1, {I1}); + VPInstruction *I3 = new VPInstruction(2, {I1, I2}); + + VPBasicBlock *VPBB1 = new VPBasicBlock(); + VPBB1->appendRecipe(I1); + VPBB1->appendRecipe(I2); + VPBB1->appendRecipe(I3); + + VPInstruction *I4 = new VPInstruction(4, {I3, I2}); + VPInstruction *I5 = new VPInstruction(5, {I1}); + VPBasicBlock *VPBB2 = new VPBasicBlock(); + VPBB2->appendRecipe(I4); + VPBB2->appendRecipe(I5); + + VPBlockUtils::connectBlocks(VPBB1, VPBB2); + + // Check printing an instruction without associated VPlan. + { + std::string I3Dump; + raw_string_ostream OS(I3Dump); + I3->print(OS); + OS.flush(); + EXPECT_EQ(" = br ", I3Dump); + } + + VPlan Plan; + Plan.setEntry(VPBB1); + std::string FullDump; + raw_string_ostream(FullDump) << Plan; + + EXPECT_EQ(R"(digraph VPlan { +graph [labelloc=t, fontsize=30; label="Vectorization Plan"] +node [shape=rect, fontname=Courier, fontsize=30] +edge [fontname=Courier, fontsize=30] +compound=true + N0 [label = + ":\n" + + "EMIT %vp0 = catchswitch\l" + + "EMIT %vp1 = ret %vp0\l" + + "EMIT %vp2 = br %vp0 %vp1\l" + ] + N0 -> N1 [ label=""] + N1 [label = + ":\n" + + "EMIT %vp3 = indirectbr %vp2 %vp1\l" + + "EMIT %vp4 = invoke %vp0\l" + ] +} +)", + FullDump); + + { + std::string I3Dump; + raw_string_ostream OS(I3Dump); + I3->print(OS); + OS.flush(); + EXPECT_EQ("%vp2 = br %vp0 %vp1", I3Dump); + } +} + } // namespace } // namespace llvm