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