1 //===- Region.h -------------------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_SANDBOXIR_REGION_H 10 #define LLVM_SANDBOXIR_REGION_H 11 12 #include "llvm/Support/Compiler.h" 13 #include <memory> 14 15 #include "llvm/ADT/SetVector.h" 16 #include "llvm/ADT/iterator_range.h" 17 #include "llvm/Analysis/TargetTransformInfo.h" 18 #include "llvm/SandboxIR/Instruction.h" 19 #include "llvm/Support/raw_ostream.h" 20 21 namespace llvm::sandboxir { 22 23 class Region; 24 25 class ScoreBoard { 26 const Region &Rgn; 27 TargetTransformInfo &TTI; 28 constexpr static TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput; 29 /// The cost of all instructions added to the region. 30 InstructionCost AfterCost = 0; 31 /// The cost of all instructions that got removed and replaced by new ones. 32 InstructionCost BeforeCost = 0; 33 /// Helper for both add() and remove(). \Returns the TTI cost of \p I. 34 LLVM_ABI InstructionCost getCost(Instruction *I) const; 35 /// No need to allow copies. 36 ScoreBoard(const ScoreBoard &) = delete; 37 const ScoreBoard &operator=(const ScoreBoard &) = delete; 38 39 public: ScoreBoard(Region & Rgn,TargetTransformInfo & TTI)40 ScoreBoard(Region &Rgn, TargetTransformInfo &TTI) : Rgn(Rgn), TTI(TTI) {} 41 /// Mark \p I as a newly added instruction to the region. add(Instruction * I)42 void add(Instruction *I) { AfterCost += getCost(I); } 43 /// Mark \p I as a deleted instruction from the region. 44 LLVM_ABI void remove(Instruction *I); 45 /// \Returns the cost of the newly added instructions. getAfterCost()46 InstructionCost getAfterCost() const { return AfterCost; } 47 /// \Returns the cost of the Removed instructions. getBeforeCost()48 InstructionCost getBeforeCost() const { return BeforeCost; } 49 50 #ifndef NDEBUG dump(raw_ostream & OS)51 void dump(raw_ostream &OS) const { 52 OS << "BeforeCost: " << BeforeCost << "\n"; 53 OS << "AfterCost: " << AfterCost << "\n"; 54 } 55 LLVM_DUMP_METHOD void dump() const; 56 #endif // NDEBUG 57 }; 58 59 /// The main job of the Region is to point to new instructions generated by 60 /// vectorization passes. It is the unit that RegionPasses operate on with their 61 /// runOnRegion() function. 62 /// 63 /// The region allows us to stack transformations horizontally, meaning that 64 /// each transformation operates on a single region and the resulting region is 65 /// the input to the next transformation, as opposed to vertically, which is the 66 /// common way of applying a transformation across the whole function. This 67 /// enables us to check for profitability and decide whether we accept or 68 /// rollback at a region granularity, which is much better than doing this at 69 /// the function level. 70 /// 71 // Traditional approach: transformations applied vertically for the whole 72 // function 73 // F 74 // +----+ 75 // | | 76 // | | 77 // | | -> Transform1 -> ... -> TransformN -> Check Cost 78 // | | 79 // | | 80 // +----+ 81 // 82 // Region-based approach: transformations applied horizontally, for each Region 83 // F 84 // +----+ 85 // |Rgn1| -> Transform1 -> ... -> TransformN -> Check Cost 86 // | | 87 // |Rgn2| -> Transform1 -> ... -> TransformN -> Check Cost 88 // | | 89 // |Rgn3| -> Transform1 -> ... -> TransformN -> Check Cost 90 // +----+ 91 // 92 // The region can also hold an ordered sequence of "auxiliary" instructions. 93 // This can be used to pass auxiliary information across region passes, like for 94 // example the initial seed slice used by the bottom-up vectorizer. 95 96 class Region { 97 /// All the instructions in the Region. Only new instructions generated during 98 /// vectorization are part of the Region. 99 SetVector<Instruction *> Insts; 100 /// An auxiliary sequence of Instruction-Index pairs. 101 SmallVector<Instruction *> Aux; 102 103 /// MDNode that we'll use to mark instructions as being part of the region. 104 MDNode *RegionMDN; 105 static constexpr const char *MDKind = "sandboxvec"; 106 static constexpr const char *RegionStr = "sandboxregion"; 107 static constexpr const char *AuxMDKind = "sandboxaux"; 108 109 Context &Ctx; 110 /// Keeps track of cost of instructions added and removed. 111 ScoreBoard Scoreboard; 112 113 /// ID (for later deregistration) of the "create instruction" callback. 114 Context::CallbackID CreateInstCB; 115 /// ID (for later deregistration) of the "erase instruction" callback. 116 Context::CallbackID EraseInstCB; 117 118 /// Adds \p I to the set but also don't track the instruction's score if \p 119 /// IgnoreCost is true. Only to be used when adding an instruction to the 120 /// auxiliary vector. 121 /// NOTE: When an instruction is added to the region we track it cost in the 122 /// scoreboard, which currently resides in the region class. However, when we 123 /// add an instruction to the auxiliary vector it does get tagged as being a 124 /// member of the region (for ownership reasons), but its cost does not get 125 /// counted because the instruction hasn't been added in the "normal" way. 126 LLVM_ABI void addImpl(Instruction *I, bool IgnoreCost); 127 /// Adds I to the set. This is the main API for adding an instruction to the 128 /// region. add(Instruction * I)129 void add(Instruction *I) { addImpl(I, /*IgnoreCost=*/false); } 130 /// Removes I from the set. 131 LLVM_ABI void remove(Instruction *I); 132 friend class Context; // The callbacks need to call add() and remove(). 133 friend class RegionInternalsAttorney; // For unit tests. 134 friend class RegionsFromBBs; // For add(). 135 136 /// Set \p I as the \p Idx'th element in the auxiliary vector. 137 /// NOTE: This is for internal use, it does not set the metadata. 138 void setAux(unsigned Idx, Instruction *I); 139 /// Helper for dropping Aux metadata for \p I. 140 void dropAuxMetadata(Instruction *I); 141 /// Remove instruction \p I from Aux and drop metadata. 142 void removeFromAux(Instruction *I); 143 144 public: 145 LLVM_ABI Region(Context &Ctx, TargetTransformInfo &TTI); 146 LLVM_ABI ~Region(); 147 getContext()148 Context &getContext() const { return Ctx; } 149 /// Returns true if I is in the Region. contains(Instruction * I)150 bool contains(Instruction *I) const { return Insts.contains(I); } 151 /// Returns true if the Region has no instructions. empty()152 bool empty() const { return Insts.empty(); } 153 /// Set the auxiliary vector. 154 LLVM_ABI void setAux(ArrayRef<Instruction *> Aux); 155 /// \Returns the auxiliary vector. getAux()156 const SmallVector<Instruction *> &getAux() const { return Aux; } 157 /// Clears all auxiliary data. 158 LLVM_ABI void clearAux(); 159 160 using iterator = decltype(Insts.begin()); begin()161 iterator begin() { return Insts.begin(); } end()162 iterator end() { return Insts.end(); } insts()163 iterator_range<iterator> insts() { return make_range(begin(), end()); } 164 165 LLVM_ABI static SmallVector<std::unique_ptr<Region>> 166 createRegionsFromMD(Function &F, TargetTransformInfo &TTI); 167 /// \Returns the ScoreBoard data structure that keeps track of instr costs. getScoreboard()168 const ScoreBoard &getScoreboard() const { return Scoreboard; } 169 170 #ifndef NDEBUG 171 /// This is an expensive check, meant for testing. 172 bool operator==(const Region &Other) const; 173 bool operator!=(const Region &other) const { return !(*this == other); } 174 175 void dump(raw_ostream &OS) const; 176 void dump() const; 177 friend raw_ostream &operator<<(raw_ostream &OS, const Region &Rgn) { 178 Rgn.dump(OS); 179 return OS; 180 } 181 #endif 182 }; 183 184 /// A helper client-attorney class for unit tests. 185 class RegionInternalsAttorney { 186 public: add(Region & Rgn,Instruction * I)187 static void add(Region &Rgn, Instruction *I) { Rgn.add(I); } remove(Region & Rgn,Instruction * I)188 static void remove(Region &Rgn, Instruction *I) { Rgn.remove(I); } 189 }; 190 191 } // namespace llvm::sandboxir 192 193 #endif // LLVM_SANDBOXIR_REGION_H 194