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