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
  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 }