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