1 //===- CSEInfo.cpp ------------------------------===// 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 // 10 //===----------------------------------------------------------------------===// 11 #include "llvm/CodeGen/GlobalISel/CSEInfo.h" 12 #include "llvm/CodeGen/MachineRegisterInfo.h" 13 #include "llvm/InitializePasses.h" 14 15 #define DEBUG_TYPE "cseinfo" 16 17 using namespace llvm; 18 char llvm::GISelCSEAnalysisWrapperPass::ID = 0; 19 GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass() 20 : MachineFunctionPass(ID) { 21 initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry()); 22 } 23 INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE, 24 "Analysis containing CSE Info", false, true) 25 INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE, 26 "Analysis containing CSE Info", false, true) 27 28 /// -------- UniqueMachineInstr -------------// 29 30 void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) { 31 GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI); 32 } 33 /// ----------------------------------------- 34 35 /// --------- CSEConfigFull ---------- /// 36 bool CSEConfigFull::shouldCSEOpc(unsigned Opc) { 37 switch (Opc) { 38 default: 39 break; 40 case TargetOpcode::G_ADD: 41 case TargetOpcode::G_AND: 42 case TargetOpcode::G_ASHR: 43 case TargetOpcode::G_LSHR: 44 case TargetOpcode::G_MUL: 45 case TargetOpcode::G_OR: 46 case TargetOpcode::G_SHL: 47 case TargetOpcode::G_SUB: 48 case TargetOpcode::G_XOR: 49 case TargetOpcode::G_UDIV: 50 case TargetOpcode::G_SDIV: 51 case TargetOpcode::G_UREM: 52 case TargetOpcode::G_SREM: 53 case TargetOpcode::G_CONSTANT: 54 case TargetOpcode::G_FCONSTANT: 55 case TargetOpcode::G_ZEXT: 56 case TargetOpcode::G_SEXT: 57 case TargetOpcode::G_ANYEXT: 58 case TargetOpcode::G_UNMERGE_VALUES: 59 case TargetOpcode::G_TRUNC: 60 case TargetOpcode::G_PTR_ADD: 61 return true; 62 } 63 return false; 64 } 65 66 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) { 67 return Opc == TargetOpcode::G_CONSTANT; 68 } 69 70 std::unique_ptr<CSEConfigBase> 71 llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) { 72 std::unique_ptr<CSEConfigBase> Config; 73 if (Level == CodeGenOpt::None) 74 Config = std::make_unique<CSEConfigConstantOnly>(); 75 else 76 Config = std::make_unique<CSEConfigFull>(); 77 return Config; 78 } 79 80 /// ----------------------------------------- 81 82 /// -------- GISelCSEInfo -------------// 83 void GISelCSEInfo::setMF(MachineFunction &MF) { 84 this->MF = &MF; 85 this->MRI = &MF.getRegInfo(); 86 } 87 88 GISelCSEInfo::~GISelCSEInfo() {} 89 90 bool GISelCSEInfo::isUniqueMachineInstValid( 91 const UniqueMachineInstr &UMI) const { 92 // Should we check here and assert that the instruction has been fully 93 // constructed? 94 // FIXME: Any other checks required to be done here? Remove this method if 95 // none. 96 return true; 97 } 98 99 void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) { 100 bool Removed = CSEMap.RemoveNode(UMI); 101 (void)Removed; 102 assert(Removed && "Invalidation called on invalid UMI"); 103 // FIXME: Should UMI be deallocated/destroyed? 104 } 105 106 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID, 107 MachineBasicBlock *MBB, 108 void *&InsertPos) { 109 auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos); 110 if (Node) { 111 if (!isUniqueMachineInstValid(*Node)) { 112 invalidateUniqueMachineInstr(Node); 113 return nullptr; 114 } 115 116 if (Node->MI->getParent() != MBB) 117 return nullptr; 118 } 119 return Node; 120 } 121 122 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) { 123 handleRecordedInsts(); 124 assert(UMI); 125 UniqueMachineInstr *MaybeNewNode = UMI; 126 if (InsertPos) 127 CSEMap.InsertNode(UMI, InsertPos); 128 else 129 MaybeNewNode = CSEMap.GetOrInsertNode(UMI); 130 if (MaybeNewNode != UMI) { 131 // A similar node exists in the folding set. Let's ignore this one. 132 return; 133 } 134 assert(InstrMapping.count(UMI->MI) == 0 && 135 "This instruction should not be in the map"); 136 InstrMapping[UMI->MI] = MaybeNewNode; 137 } 138 139 UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) { 140 assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node"); 141 auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI); 142 return Node; 143 } 144 145 void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) { 146 assert(MI); 147 // If it exists in temporary insts, remove it. 148 TemporaryInsts.remove(MI); 149 auto *Node = getUniqueInstrForMI(MI); 150 insertNode(Node, InsertPos); 151 } 152 153 MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID, 154 MachineBasicBlock *MBB, 155 void *&InsertPos) { 156 handleRecordedInsts(); 157 if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) { 158 LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;); 159 return const_cast<MachineInstr *>(Inst->MI); 160 } 161 return nullptr; 162 } 163 164 void GISelCSEInfo::countOpcodeHit(unsigned Opc) { 165 #ifndef NDEBUG 166 if (OpcodeHitTable.count(Opc)) 167 OpcodeHitTable[Opc] += 1; 168 else 169 OpcodeHitTable[Opc] = 1; 170 #endif 171 // Else do nothing. 172 } 173 174 void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) { 175 if (shouldCSE(MI->getOpcode())) { 176 TemporaryInsts.insert(MI); 177 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI); 178 } 179 } 180 181 void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) { 182 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE"); 183 auto *UMI = InstrMapping.lookup(MI); 184 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI); 185 if (UMI) { 186 // Invalidate this MI. 187 invalidateUniqueMachineInstr(UMI); 188 InstrMapping.erase(MI); 189 } 190 /// Now insert the new instruction. 191 if (UMI) { 192 /// We'll reuse the same UniqueMachineInstr to avoid the new 193 /// allocation. 194 *UMI = UniqueMachineInstr(MI); 195 insertNode(UMI, nullptr); 196 } else { 197 /// This is a new instruction. Allocate a new UniqueMachineInstr and 198 /// Insert. 199 insertInstr(MI); 200 } 201 } 202 203 void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) { 204 if (auto *UMI = InstrMapping.lookup(MI)) { 205 invalidateUniqueMachineInstr(UMI); 206 InstrMapping.erase(MI); 207 } 208 TemporaryInsts.remove(MI); 209 } 210 211 void GISelCSEInfo::handleRecordedInsts() { 212 while (!TemporaryInsts.empty()) { 213 auto *MI = TemporaryInsts.pop_back_val(); 214 handleRecordedInst(MI); 215 } 216 } 217 218 bool GISelCSEInfo::shouldCSE(unsigned Opc) const { 219 // Only GISel opcodes are CSEable 220 if (!isPreISelGenericOpcode(Opc)) 221 return false; 222 assert(CSEOpt.get() && "CSEConfig not set"); 223 return CSEOpt->shouldCSEOpc(Opc); 224 } 225 226 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); } 227 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); } 228 void GISelCSEInfo::changingInstr(MachineInstr &MI) { 229 // For now, perform erase, followed by insert. 230 erasingInstr(MI); 231 createdInstr(MI); 232 } 233 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); } 234 235 void GISelCSEInfo::analyze(MachineFunction &MF) { 236 setMF(MF); 237 for (auto &MBB : MF) { 238 if (MBB.empty()) 239 continue; 240 for (MachineInstr &MI : MBB) { 241 if (!shouldCSE(MI.getOpcode())) 242 continue; 243 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI); 244 insertInstr(&MI); 245 } 246 } 247 } 248 249 void GISelCSEInfo::releaseMemory() { 250 print(); 251 CSEMap.clear(); 252 InstrMapping.clear(); 253 UniqueInstrAllocator.Reset(); 254 TemporaryInsts.clear(); 255 CSEOpt.reset(); 256 MRI = nullptr; 257 MF = nullptr; 258 #ifndef NDEBUG 259 OpcodeHitTable.clear(); 260 #endif 261 } 262 263 void GISelCSEInfo::print() { 264 LLVM_DEBUG(for (auto &It 265 : OpcodeHitTable) { 266 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second 267 << "\n"; 268 };); 269 } 270 /// ----------------------------------------- 271 // ---- Profiling methods for FoldingSetNode --- // 272 const GISelInstProfileBuilder & 273 GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const { 274 addNodeIDMBB(MI->getParent()); 275 addNodeIDOpcode(MI->getOpcode()); 276 for (auto &Op : MI->operands()) 277 addNodeIDMachineOperand(Op); 278 addNodeIDFlag(MI->getFlags()); 279 return *this; 280 } 281 282 const GISelInstProfileBuilder & 283 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const { 284 ID.AddInteger(Opc); 285 return *this; 286 } 287 288 const GISelInstProfileBuilder & 289 GISelInstProfileBuilder::addNodeIDRegType(const LLT &Ty) const { 290 uint64_t Val = Ty.getUniqueRAWLLTData(); 291 ID.AddInteger(Val); 292 return *this; 293 } 294 295 const GISelInstProfileBuilder & 296 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const { 297 ID.AddPointer(RC); 298 return *this; 299 } 300 301 const GISelInstProfileBuilder & 302 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const { 303 ID.AddPointer(RB); 304 return *this; 305 } 306 307 const GISelInstProfileBuilder & 308 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const { 309 ID.AddInteger(Imm); 310 return *this; 311 } 312 313 const GISelInstProfileBuilder & 314 GISelInstProfileBuilder::addNodeIDRegNum(unsigned Reg) const { 315 ID.AddInteger(Reg); 316 return *this; 317 } 318 319 const GISelInstProfileBuilder & 320 GISelInstProfileBuilder::addNodeIDRegType(const unsigned Reg) const { 321 addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false)); 322 return *this; 323 } 324 325 const GISelInstProfileBuilder & 326 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const { 327 ID.AddPointer(MBB); 328 return *this; 329 } 330 331 const GISelInstProfileBuilder & 332 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const { 333 if (Flag) 334 ID.AddInteger(Flag); 335 return *this; 336 } 337 338 const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand( 339 const MachineOperand &MO) const { 340 if (MO.isReg()) { 341 Register Reg = MO.getReg(); 342 if (!MO.isDef()) 343 addNodeIDRegNum(Reg); 344 LLT Ty = MRI.getType(Reg); 345 if (Ty.isValid()) 346 addNodeIDRegType(Ty); 347 auto *RB = MRI.getRegBankOrNull(Reg); 348 if (RB) 349 addNodeIDRegType(RB); 350 auto *RC = MRI.getRegClassOrNull(Reg); 351 if (RC) 352 addNodeIDRegType(RC); 353 assert(!MO.isImplicit() && "Unhandled case"); 354 } else if (MO.isImm()) 355 ID.AddInteger(MO.getImm()); 356 else if (MO.isCImm()) 357 ID.AddPointer(MO.getCImm()); 358 else if (MO.isFPImm()) 359 ID.AddPointer(MO.getFPImm()); 360 else if (MO.isPredicate()) 361 ID.AddInteger(MO.getPredicate()); 362 else 363 llvm_unreachable("Unhandled operand type"); 364 // Handle other types 365 return *this; 366 } 367 368 GISelCSEInfo & 369 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt, 370 bool Recompute) { 371 if (!AlreadyComputed || Recompute) { 372 Info.setCSEConfig(std::move(CSEOpt)); 373 Info.analyze(*MF); 374 AlreadyComputed = true; 375 } 376 return Info; 377 } 378 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 379 AU.setPreservesAll(); 380 MachineFunctionPass::getAnalysisUsage(AU); 381 } 382 383 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) { 384 releaseMemory(); 385 Wrapper.setMF(MF); 386 return false; 387 } 388