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