1 //===- llvm/CodeGen/GlobalISel/CSEInfo.h ------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 /// Provides analysis for continuously CSEing during GISel passes. 11 // 12 //===----------------------------------------------------------------------===// 13 #ifndef LLVM_CODEGEN_GLOBALISEL_CSEINFO_H 14 #define LLVM_CODEGEN_GLOBALISEL_CSEINFO_H 15 16 #include "llvm/ADT/FoldingSet.h" 17 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" 18 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h" 19 #include "llvm/CodeGen/GlobalISel/Utils.h" 20 #include "llvm/CodeGen/MachineBasicBlock.h" 21 #include "llvm/CodeGen/MachineFunctionPass.h" 22 #include "llvm/IR/PassManager.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Support/Allocator.h" 25 26 namespace llvm { 27 28 /// A class that wraps MachineInstrs and derives from FoldingSetNode in order to 29 /// be uniqued in a CSEMap. The tradeoff here is extra memory allocations for 30 /// UniqueMachineInstr vs making MachineInstr bigger. 31 class UniqueMachineInstr : public FoldingSetNode { 32 friend class GISelCSEInfo; 33 const MachineInstr *MI; UniqueMachineInstr(const MachineInstr * MI)34 explicit UniqueMachineInstr(const MachineInstr *MI) : MI(MI) {} 35 36 public: 37 void Profile(FoldingSetNodeID &ID); 38 }; 39 40 // Class representing some configuration that can be done during CSE analysis. 41 // Currently it only supports shouldCSE method that each pass can set. 42 class CSEConfig { 43 public: 44 virtual ~CSEConfig() = default; 45 // Hook for defining which Generic instructions should be CSEd. 46 // GISelCSEInfo currently only calls this hook when dealing with generic 47 // opcodes. 48 virtual bool shouldCSEOpc(unsigned Opc); 49 }; 50 51 // TODO: Find a better place for this. 52 // Commonly used for O0 config. 53 class CSEConfigConstantOnly : public CSEConfig { 54 public: 55 virtual ~CSEConfigConstantOnly() = default; 56 virtual bool shouldCSEOpc(unsigned Opc) override; 57 }; 58 59 /// The CSE Analysis object. 60 /// This installs itself as a delegate to the MachineFunction to track 61 /// new instructions as well as deletions. It however will not be able to 62 /// track instruction mutations. In such cases, recordNewInstruction should be 63 /// called (for eg inside MachineIRBuilder::recordInsertion). 64 /// Also because of how just the instruction can be inserted without adding any 65 /// operands to the instruction, instructions are uniqued and inserted lazily. 66 /// CSEInfo should assert when trying to enter an incomplete instruction into 67 /// the CSEMap. There is Opcode level granularity on which instructions can be 68 /// CSE'd and for now, only Generic instructions are CSEable. 69 class GISelCSEInfo : public GISelChangeObserver { 70 // Make it accessible only to CSEMIRBuilder. 71 friend class CSEMIRBuilder; 72 73 BumpPtrAllocator UniqueInstrAllocator; 74 FoldingSet<UniqueMachineInstr> CSEMap; 75 MachineRegisterInfo *MRI = nullptr; 76 MachineFunction *MF = nullptr; 77 std::unique_ptr<CSEConfig> CSEOpt; 78 /// Keep a cache of UniqueInstrs for each MachineInstr. In GISel, 79 /// often instructions are mutated (while their ID has completely changed). 80 /// Whenever mutation happens, invalidate the UniqueMachineInstr for the 81 /// MachineInstr 82 DenseMap<const MachineInstr *, UniqueMachineInstr *> InstrMapping; 83 84 /// Store instructions that are not fully formed in TemporaryInsts. 85 /// Also because CSE insertion happens lazily, we can remove insts from this 86 /// list and avoid inserting and then removing from the CSEMap. 87 GISelWorkList<8> TemporaryInsts; 88 89 // Only used in asserts. 90 DenseMap<unsigned, unsigned> OpcodeHitTable; 91 92 bool isUniqueMachineInstValid(const UniqueMachineInstr &UMI) const; 93 94 void invalidateUniqueMachineInstr(UniqueMachineInstr *UMI); 95 96 UniqueMachineInstr *getNodeIfExists(FoldingSetNodeID &ID, 97 MachineBasicBlock *MBB, void *&InsertPos); 98 99 /// Allocate and construct a new UniqueMachineInstr for MI and return. 100 UniqueMachineInstr *getUniqueInstrForMI(const MachineInstr *MI); 101 102 void insertNode(UniqueMachineInstr *UMI, void *InsertPos = nullptr); 103 104 /// Get the MachineInstr(Unique) if it exists already in the CSEMap and the 105 /// same MachineBasicBlock. 106 MachineInstr *getMachineInstrIfExists(FoldingSetNodeID &ID, 107 MachineBasicBlock *MBB, 108 void *&InsertPos); 109 110 /// Use this method to allocate a new UniqueMachineInstr for MI and insert it 111 /// into the CSEMap. MI should return true for shouldCSE(MI->getOpcode()) 112 void insertInstr(MachineInstr *MI, void *InsertPos = nullptr); 113 114 public: 115 GISelCSEInfo() = default; 116 117 virtual ~GISelCSEInfo(); 118 119 void setMF(MachineFunction &MF); 120 121 /// Records a newly created inst in a list and lazily insert it to the CSEMap. 122 /// Sometimes, this method might be called with a partially constructed 123 /// MachineInstr, 124 // (right after BuildMI without adding any operands) - and in such cases, 125 // defer the hashing of the instruction to a later stage. 126 void recordNewInstruction(MachineInstr *MI); 127 128 /// Use this callback to inform CSE about a newly fully created instruction. 129 void handleRecordedInst(MachineInstr *MI); 130 131 /// Use this callback to insert all the recorded instructions. At this point, 132 /// all of these insts need to be fully constructed and should not be missing 133 /// any operands. 134 void handleRecordedInsts(); 135 136 /// Remove this inst from the CSE map. If this inst has not been inserted yet, 137 /// it will be removed from the Tempinsts list if it exists. 138 void handleRemoveInst(MachineInstr *MI); 139 140 void releaseMemory(); 141 setCSEConfig(std::unique_ptr<CSEConfig> Opt)142 void setCSEConfig(std::unique_ptr<CSEConfig> Opt) { CSEOpt = std::move(Opt); } 143 144 bool shouldCSE(unsigned Opc) const; 145 146 void analyze(MachineFunction &MF); 147 148 void countOpcodeHit(unsigned Opc); 149 150 void print(); 151 152 // Observer API 153 void erasingInstr(MachineInstr &MI) override; 154 void createdInstr(MachineInstr &MI) override; 155 void changingInstr(MachineInstr &MI) override; 156 void changedInstr(MachineInstr &MI) override; 157 }; 158 159 class TargetRegisterClass; 160 class RegisterBank; 161 162 // Simple builder class to easily profile properties about MIs. 163 class GISelInstProfileBuilder { 164 FoldingSetNodeID &ID; 165 const MachineRegisterInfo &MRI; 166 167 public: GISelInstProfileBuilder(FoldingSetNodeID & ID,const MachineRegisterInfo & MRI)168 GISelInstProfileBuilder(FoldingSetNodeID &ID, const MachineRegisterInfo &MRI) 169 : ID(ID), MRI(MRI) {} 170 // Profiling methods. 171 const GISelInstProfileBuilder &addNodeIDOpcode(unsigned Opc) const; 172 const GISelInstProfileBuilder &addNodeIDRegType(const LLT &Ty) const; 173 const GISelInstProfileBuilder &addNodeIDRegType(const unsigned) const; 174 175 const GISelInstProfileBuilder & 176 addNodeIDRegType(const TargetRegisterClass *RC) const; 177 const GISelInstProfileBuilder &addNodeIDRegType(const RegisterBank *RB) const; 178 179 const GISelInstProfileBuilder &addNodeIDRegNum(unsigned Reg) const; 180 181 const GISelInstProfileBuilder &addNodeIDImmediate(int64_t Imm) const; 182 const GISelInstProfileBuilder & 183 addNodeIDMBB(const MachineBasicBlock *MBB) const; 184 185 const GISelInstProfileBuilder & 186 addNodeIDMachineOperand(const MachineOperand &MO) const; 187 188 const GISelInstProfileBuilder &addNodeIDFlag(unsigned Flag) const; 189 const GISelInstProfileBuilder &addNodeID(const MachineInstr *MI) const; 190 }; 191 192 /// Simple wrapper that does the following. 193 /// 1) Lazily evaluate the MachineFunction to compute CSEable instructions. 194 /// 2) Allows configuration of which instructions are CSEd through CSEConfig 195 /// object. Provides a method called get which takes a CSEConfig object. 196 class GISelCSEAnalysisWrapper { 197 GISelCSEInfo Info; 198 MachineFunction *MF = nullptr; 199 bool AlreadyComputed = false; 200 201 public: 202 /// Takes a CSEConfig object that defines what opcodes get CSEd. 203 /// If CSEConfig is already set, and the CSE Analysis has been preserved, 204 /// it will not use the new CSEOpt(use Recompute to force using the new 205 /// CSEOpt). 206 GISelCSEInfo &get(std::unique_ptr<CSEConfig> CSEOpt, bool ReCompute = false); setMF(MachineFunction & MFunc)207 void setMF(MachineFunction &MFunc) { MF = &MFunc; } setComputed(bool Computed)208 void setComputed(bool Computed) { AlreadyComputed = Computed; } releaseMemory()209 void releaseMemory() { Info.releaseMemory(); } 210 }; 211 212 /// The actual analysis pass wrapper. 213 class GISelCSEAnalysisWrapperPass : public MachineFunctionPass { 214 GISelCSEAnalysisWrapper Wrapper; 215 216 public: 217 static char ID; GISelCSEAnalysisWrapperPass()218 GISelCSEAnalysisWrapperPass() : MachineFunctionPass(ID) { 219 initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry()); 220 } 221 222 void getAnalysisUsage(AnalysisUsage &AU) const override; 223 getCSEWrapper()224 const GISelCSEAnalysisWrapper &getCSEWrapper() const { return Wrapper; } getCSEWrapper()225 GISelCSEAnalysisWrapper &getCSEWrapper() { return Wrapper; } 226 227 bool runOnMachineFunction(MachineFunction &MF) override; 228 releaseMemory()229 void releaseMemory() override { 230 Wrapper.releaseMemory(); 231 Wrapper.setComputed(false); 232 } 233 }; 234 235 } // namespace llvm 236 237 #endif 238