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