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