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