contrib/llvm-project/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
  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 }