llvm/lib/CodeGen/GlobalISel/CSEInfo.cpp

   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(CodeGenOptLevel Level) {
  80   std::unique_ptr<CSEConfigBase> Config;
  81   if (Level == CodeGenOptLevel::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   if (HandlingRecordedInstrs)
 221     return;
 222   HandlingRecordedInstrs = true;
 223   while (!TemporaryInsts.empty()) {
 224     auto *MI = TemporaryInsts.pop_back_val();
 225     handleRecordedInst(MI);
 226   }
 227   HandlingRecordedInstrs = false;
 228 }
 229
 230 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
 231   assert(CSEOpt.get() && "CSEConfig not set");
 232   return CSEOpt->shouldCSEOpc(Opc);
 233 }
 234
 235 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
 236 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
 237 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
 238   // For now, perform erase, followed by insert.
 239   erasingInstr(MI);
 240   createdInstr(MI);
 241 }
 242 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
 243
 244 void GISelCSEInfo::analyze(MachineFunction &MF) {
 245   setMF(MF);
 246   for (auto &MBB : MF) {
 247     for (MachineInstr &MI : MBB) {
 248       if (!shouldCSE(MI.getOpcode()))
 249         continue;
 250       LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
 251       insertInstr(&MI);
 252     }
 253   }
 254 }
 255
 256 void GISelCSEInfo::releaseMemory() {
 257   print();
 258   CSEMap.clear();
 259   InstrMapping.clear();
 260   UniqueInstrAllocator.Reset();
 261   TemporaryInsts.clear();
 262   CSEOpt.reset();
 263   MRI = nullptr;
 264   MF = nullptr;
 265 #ifndef NDEBUG
 266   OpcodeHitTable.clear();
 267 #endif
 268 }
 269
 270 #ifndef NDEBUG
 271 static const char *stringify(const MachineInstr *MI, std::string &S) {
 272   raw_string_ostream OS(S);
 273   OS << *MI;
 274   return OS.str().c_str();
 275 }
 276 #endif
 277
 278 Error GISelCSEInfo::verify() {
 279 #ifndef NDEBUG
 280   std::string S1, S2;
 281   handleRecordedInsts();
 282   // For each instruction in map from MI -> UMI,
 283   // Profile(MI) and make sure UMI is found for that profile.
 284   for (auto &It : InstrMapping) {
 285     FoldingSetNodeID TmpID;
 286     GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first);
 287     void *InsertPos;
 288     UniqueMachineInstr *FoundNode =
 289         CSEMap.FindNodeOrInsertPos(TmpID, InsertPos);
 290     if (FoundNode != It.second)
 291       return createStringError(std::errc::not_supported,
 292                                "CSEMap mismatch, InstrMapping has MIs without "
 293                                "corresponding Nodes in CSEMap:\n%s",
 294                                stringify(It.second->MI, S1));
 295   }
 296
 297   // For every node in the CSEMap, make sure that the InstrMapping
 298   // points to it.
 299   for (const UniqueMachineInstr &UMI : CSEMap) {
 300     if (!InstrMapping.count(UMI.MI))
 301       return createStringError(std::errc::not_supported,
 302                                "Node in CSE without InstrMapping:\n%s",
 303                                stringify(UMI.MI, S1));
 304
 305     if (InstrMapping[UMI.MI] != &UMI)
 306       return createStringError(std::make_error_code(std::errc::not_supported),
 307                                "Mismatch in CSE mapping:\n%s\n%s",
 308                                stringify(InstrMapping[UMI.MI]->MI, S1),
 309                                stringify(UMI.MI, S2));
 310   }
 311 #endif
 312   return Error::success();
 313 }
 314
 315 void GISelCSEInfo::print() {
 316   LLVM_DEBUG(for (auto &It
 317                   : OpcodeHitTable) {
 318     dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
 319            << "\n";
 320   };);
 321 }
 322 /// -----------------------------------------
 323 // ---- Profiling methods for FoldingSetNode --- //
 324 const GISelInstProfileBuilder &
 325 GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
 326   addNodeIDMBB(MI->getParent());
 327   addNodeIDOpcode(MI->getOpcode());
 328   for (const auto &Op : MI->operands())
 329     addNodeIDMachineOperand(Op);
 330   addNodeIDFlag(MI->getFlags());
 331   return *this;
 332 }
 333
 334 const GISelInstProfileBuilder &
 335 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
 336   ID.AddInteger(Opc);
 337   return *this;
 338 }
 339
 340 const GISelInstProfileBuilder &
 341 GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
 342   uint64_t Val = Ty.getUniqueRAWLLTData();
 343   ID.AddInteger(Val);
 344   return *this;
 345 }
 346
 347 const GISelInstProfileBuilder &
 348 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
 349   ID.AddPointer(RC);
 350   return *this;
 351 }
 352
 353 const GISelInstProfileBuilder &
 354 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
 355   ID.AddPointer(RB);
 356   return *this;
 357 }
 358
 359 const GISelInstProfileBuilder &
 360 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
 361   ID.AddInteger(Imm);
 362   return *this;
 363 }
 364
 365 const GISelInstProfileBuilder &
 366 GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
 367   ID.AddInteger(Reg);
 368   return *this;
 369 }
 370
 371 const GISelInstProfileBuilder &
 372 GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
 373   addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
 374   return *this;
 375 }
 376
 377 const GISelInstProfileBuilder &
 378 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
 379   ID.AddPointer(MBB);
 380   return *this;
 381 }
 382
 383 const GISelInstProfileBuilder &
 384 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
 385   if (Flag)
 386     ID.AddInteger(Flag);
 387   return *this;
 388 }
 389
 390 const GISelInstProfileBuilder &
 391 GISelInstProfileBuilder::addNodeIDReg(Register Reg) const {
 392   LLT Ty = MRI.getType(Reg);
 393   if (Ty.isValid())
 394     addNodeIDRegType(Ty);
 395
 396   if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) {
 397     if (const auto *RB = dyn_cast_if_present<const RegisterBank *>(RCOrRB))
 398       addNodeIDRegType(RB);
 399     else if (const auto *RC =
 400                  dyn_cast_if_present<const TargetRegisterClass *>(RCOrRB))
 401       addNodeIDRegType(RC);
 402   }
 403   return *this;
 404 }
 405
 406 const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
 407     const MachineOperand &MO) const {
 408   if (MO.isReg()) {
 409     Register Reg = MO.getReg();
 410     if (!MO.isDef())
 411       addNodeIDRegNum(Reg);
 412
 413     // Profile the register properties.
 414     addNodeIDReg(Reg);
 415     assert(!MO.isImplicit() && "Unhandled case");
 416   } else if (MO.isImm())
 417     ID.AddInteger(MO.getImm());
 418   else if (MO.isCImm())
 419     ID.AddPointer(MO.getCImm());
 420   else if (MO.isFPImm())
 421     ID.AddPointer(MO.getFPImm());
 422   else if (MO.isPredicate())
 423     ID.AddInteger(MO.getPredicate());
 424   else
 425     llvm_unreachable("Unhandled operand type");
 426   // Handle other types
 427   return *this;
 428 }
 429
 430 GISelCSEInfo &
 431 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
 432                              bool Recompute) {
 433   if (!AlreadyComputed || Recompute) {
 434     Info.releaseMemory();
 435     Info.setCSEConfig(std::move(CSEOpt));
 436     Info.analyze(*MF);
 437     AlreadyComputed = true;
 438   }
 439   return Info;
 440 }
 441 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 442   AU.setPreservesAll();
 443   MachineFunctionPass::getAnalysisUsage(AU);
 444 }
 445
 446 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
 447   releaseMemory();
 448   Wrapper.setMF(MF);
 449   return false;
 450 }