contrib/llvm/lib/CodeGen/GlobalISel/CSEInfo.cpp

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