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