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 #include "llvm/Support/Error.h" 15 16 #define DEBUG_TYPE "cseinfo" 17 18 using namespace llvm; 19 char llvm::GISelCSEAnalysisWrapperPass::ID = 0; 20 GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass() 21 : MachineFunctionPass(ID) { 22 initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry()); 23 } 24 INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE, 25 "Analysis containing CSE Info", false, true) 26 INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE, 27 "Analysis containing CSE Info", false, true) 28 29 /// -------- UniqueMachineInstr -------------// 30 31 void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) { 32 GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI); 33 } 34 /// ----------------------------------------- 35 36 /// --------- CSEConfigFull ---------- /// 37 bool CSEConfigFull::shouldCSEOpc(unsigned Opc) { 38 switch (Opc) { 39 default: 40 break; 41 case TargetOpcode::G_ADD: 42 case TargetOpcode::G_AND: 43 case TargetOpcode::G_ASHR: 44 case TargetOpcode::G_LSHR: 45 case TargetOpcode::G_MUL: 46 case TargetOpcode::G_OR: 47 case TargetOpcode::G_SHL: 48 case TargetOpcode::G_SUB: 49 case TargetOpcode::G_XOR: 50 case TargetOpcode::G_UDIV: 51 case TargetOpcode::G_SDIV: 52 case TargetOpcode::G_UREM: 53 case TargetOpcode::G_SREM: 54 case TargetOpcode::G_CONSTANT: 55 case TargetOpcode::G_FCONSTANT: 56 case TargetOpcode::G_IMPLICIT_DEF: 57 case TargetOpcode::G_ZEXT: 58 case TargetOpcode::G_SEXT: 59 case TargetOpcode::G_ANYEXT: 60 case TargetOpcode::G_UNMERGE_VALUES: 61 case TargetOpcode::G_TRUNC: 62 case TargetOpcode::G_PTR_ADD: 63 case TargetOpcode::G_EXTRACT: 64 return true; 65 } 66 return false; 67 } 68 69 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) { 70 return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_IMPLICIT_DEF; 71 } 72 73 std::unique_ptr<CSEConfigBase> 74 llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) { 75 std::unique_ptr<CSEConfigBase> Config; 76 if (Level == CodeGenOpt::None) 77 Config = std::make_unique<CSEConfigConstantOnly>(); 78 else 79 Config = std::make_unique<CSEConfigFull>(); 80 return Config; 81 } 82 83 /// ----------------------------------------- 84 85 /// -------- GISelCSEInfo -------------// 86 void GISelCSEInfo::setMF(MachineFunction &MF) { 87 this->MF = &MF; 88 this->MRI = &MF.getRegInfo(); 89 } 90 91 GISelCSEInfo::~GISelCSEInfo() {} 92 93 bool GISelCSEInfo::isUniqueMachineInstValid( 94 const UniqueMachineInstr &UMI) const { 95 // Should we check here and assert that the instruction has been fully 96 // constructed? 97 // FIXME: Any other checks required to be done here? Remove this method if 98 // none. 99 return true; 100 } 101 102 void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) { 103 bool Removed = CSEMap.RemoveNode(UMI); 104 (void)Removed; 105 assert(Removed && "Invalidation called on invalid UMI"); 106 // FIXME: Should UMI be deallocated/destroyed? 107 } 108 109 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID, 110 MachineBasicBlock *MBB, 111 void *&InsertPos) { 112 auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos); 113 if (Node) { 114 if (!isUniqueMachineInstValid(*Node)) { 115 invalidateUniqueMachineInstr(Node); 116 return nullptr; 117 } 118 119 if (Node->MI->getParent() != MBB) 120 return nullptr; 121 } 122 return Node; 123 } 124 125 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) { 126 handleRecordedInsts(); 127 assert(UMI); 128 UniqueMachineInstr *MaybeNewNode = UMI; 129 if (InsertPos) 130 CSEMap.InsertNode(UMI, InsertPos); 131 else 132 MaybeNewNode = CSEMap.GetOrInsertNode(UMI); 133 if (MaybeNewNode != UMI) { 134 // A similar node exists in the folding set. Let's ignore this one. 135 return; 136 } 137 assert(InstrMapping.count(UMI->MI) == 0 && 138 "This instruction should not be in the map"); 139 InstrMapping[UMI->MI] = MaybeNewNode; 140 } 141 142 UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) { 143 assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node"); 144 auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI); 145 return Node; 146 } 147 148 void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) { 149 assert(MI); 150 // If it exists in temporary insts, remove it. 151 TemporaryInsts.remove(MI); 152 auto *Node = getUniqueInstrForMI(MI); 153 insertNode(Node, InsertPos); 154 } 155 156 MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID, 157 MachineBasicBlock *MBB, 158 void *&InsertPos) { 159 handleRecordedInsts(); 160 if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) { 161 LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;); 162 return const_cast<MachineInstr *>(Inst->MI); 163 } 164 return nullptr; 165 } 166 167 void GISelCSEInfo::countOpcodeHit(unsigned Opc) { 168 #ifndef NDEBUG 169 if (OpcodeHitTable.count(Opc)) 170 OpcodeHitTable[Opc] += 1; 171 else 172 OpcodeHitTable[Opc] = 1; 173 #endif 174 // Else do nothing. 175 } 176 177 void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) { 178 if (shouldCSE(MI->getOpcode())) { 179 TemporaryInsts.insert(MI); 180 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI); 181 } 182 } 183 184 void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) { 185 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE"); 186 auto *UMI = InstrMapping.lookup(MI); 187 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI); 188 if (UMI) { 189 // Invalidate this MI. 190 invalidateUniqueMachineInstr(UMI); 191 InstrMapping.erase(MI); 192 } 193 /// Now insert the new instruction. 194 if (UMI) { 195 /// We'll reuse the same UniqueMachineInstr to avoid the new 196 /// allocation. 197 *UMI = UniqueMachineInstr(MI); 198 insertNode(UMI, nullptr); 199 } else { 200 /// This is a new instruction. Allocate a new UniqueMachineInstr and 201 /// Insert. 202 insertInstr(MI); 203 } 204 } 205 206 void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) { 207 if (auto *UMI = InstrMapping.lookup(MI)) { 208 invalidateUniqueMachineInstr(UMI); 209 InstrMapping.erase(MI); 210 } 211 TemporaryInsts.remove(MI); 212 } 213 214 void GISelCSEInfo::handleRecordedInsts() { 215 while (!TemporaryInsts.empty()) { 216 auto *MI = TemporaryInsts.pop_back_val(); 217 handleRecordedInst(MI); 218 } 219 } 220 221 bool GISelCSEInfo::shouldCSE(unsigned Opc) const { 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 #ifndef NDEBUG 264 static const char *stringify(const MachineInstr *MI, std::string &S) { 265 raw_string_ostream OS(S); 266 OS << *MI; 267 return OS.str().c_str(); 268 } 269 #endif 270 271 Error GISelCSEInfo::verify() { 272 #ifndef NDEBUG 273 std::string S1, S2; 274 handleRecordedInsts(); 275 // For each instruction in map from MI -> UMI, 276 // Profile(MI) and make sure UMI is found for that profile. 277 for (auto &It : InstrMapping) { 278 FoldingSetNodeID TmpID; 279 GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first); 280 void *InsertPos; 281 UniqueMachineInstr *FoundNode = 282 CSEMap.FindNodeOrInsertPos(TmpID, InsertPos); 283 if (FoundNode != It.second) 284 return createStringError(std::errc::not_supported, 285 "CSEMap mismatch, InstrMapping has MIs without " 286 "corresponding Nodes in CSEMap:\n%s", 287 stringify(It.second->MI, S1)); 288 } 289 290 // For every node in the CSEMap, make sure that the InstrMapping 291 // points to it. 292 for (const UniqueMachineInstr &UMI : CSEMap) { 293 if (!InstrMapping.count(UMI.MI)) 294 return createStringError(std::errc::not_supported, 295 "Node in CSE without InstrMapping:\n%s", 296 stringify(UMI.MI, S1)); 297 298 if (InstrMapping[UMI.MI] != &UMI) 299 return createStringError(std::make_error_code(std::errc::not_supported), 300 "Mismatch in CSE mapping:\n%s\n%s", 301 stringify(InstrMapping[UMI.MI]->MI, S1), 302 stringify(UMI.MI, S2)); 303 } 304 #endif 305 return Error::success(); 306 } 307 308 void GISelCSEInfo::print() { 309 LLVM_DEBUG(for (auto &It 310 : OpcodeHitTable) { 311 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second 312 << "\n"; 313 };); 314 } 315 /// ----------------------------------------- 316 // ---- Profiling methods for FoldingSetNode --- // 317 const GISelInstProfileBuilder & 318 GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const { 319 addNodeIDMBB(MI->getParent()); 320 addNodeIDOpcode(MI->getOpcode()); 321 for (auto &Op : MI->operands()) 322 addNodeIDMachineOperand(Op); 323 addNodeIDFlag(MI->getFlags()); 324 return *this; 325 } 326 327 const GISelInstProfileBuilder & 328 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const { 329 ID.AddInteger(Opc); 330 return *this; 331 } 332 333 const GISelInstProfileBuilder & 334 GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const { 335 uint64_t Val = Ty.getUniqueRAWLLTData(); 336 ID.AddInteger(Val); 337 return *this; 338 } 339 340 const GISelInstProfileBuilder & 341 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const { 342 ID.AddPointer(RC); 343 return *this; 344 } 345 346 const GISelInstProfileBuilder & 347 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const { 348 ID.AddPointer(RB); 349 return *this; 350 } 351 352 const GISelInstProfileBuilder & 353 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const { 354 ID.AddInteger(Imm); 355 return *this; 356 } 357 358 const GISelInstProfileBuilder & 359 GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const { 360 ID.AddInteger(Reg); 361 return *this; 362 } 363 364 const GISelInstProfileBuilder & 365 GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const { 366 addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false)); 367 return *this; 368 } 369 370 const GISelInstProfileBuilder & 371 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const { 372 ID.AddPointer(MBB); 373 return *this; 374 } 375 376 const GISelInstProfileBuilder & 377 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const { 378 if (Flag) 379 ID.AddInteger(Flag); 380 return *this; 381 } 382 383 const GISelInstProfileBuilder & 384 GISelInstProfileBuilder::addNodeIDReg(Register Reg) const { 385 LLT Ty = MRI.getType(Reg); 386 if (Ty.isValid()) 387 addNodeIDRegType(Ty); 388 389 if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) { 390 if (const auto *RB = RCOrRB.dyn_cast<const RegisterBank *>()) 391 addNodeIDRegType(RB); 392 else if (const auto *RC = RCOrRB.dyn_cast<const TargetRegisterClass *>()) 393 addNodeIDRegType(RC); 394 } 395 return *this; 396 } 397 398 const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand( 399 const MachineOperand &MO) const { 400 if (MO.isReg()) { 401 Register Reg = MO.getReg(); 402 if (!MO.isDef()) 403 addNodeIDRegNum(Reg); 404 405 // Profile the register properties. 406 addNodeIDReg(Reg); 407 assert(!MO.isImplicit() && "Unhandled case"); 408 } else if (MO.isImm()) 409 ID.AddInteger(MO.getImm()); 410 else if (MO.isCImm()) 411 ID.AddPointer(MO.getCImm()); 412 else if (MO.isFPImm()) 413 ID.AddPointer(MO.getFPImm()); 414 else if (MO.isPredicate()) 415 ID.AddInteger(MO.getPredicate()); 416 else 417 llvm_unreachable("Unhandled operand type"); 418 // Handle other types 419 return *this; 420 } 421 422 GISelCSEInfo & 423 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt, 424 bool Recompute) { 425 if (!AlreadyComputed || Recompute) { 426 Info.releaseMemory(); 427 Info.setCSEConfig(std::move(CSEOpt)); 428 Info.analyze(*MF); 429 AlreadyComputed = true; 430 } 431 return Info; 432 } 433 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 434 AU.setPreservesAll(); 435 MachineFunctionPass::getAnalysisUsage(AU); 436 } 437 438 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) { 439 releaseMemory(); 440 Wrapper.setMF(MF); 441 return false; 442 } 443