llvm/lib/CodeGen/MachineLateInstrsCleanup.cpp

   1 //==--- MachineLateInstrsCleanup.cpp - Late Instructions Cleanup Pass -----===//
   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 // This simple pass removes any identical and redundant immediate or address
  10 // loads to the same register. The immediate loads removed can originally be
  11 // the result of rematerialization, while the addresses are redundant frame
  12 // addressing anchor points created during Frame Indices elimination.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/ADT/BitVector.h"
  17 #include "llvm/ADT/PostOrderIterator.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/CodeGen/MachineBasicBlock.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineInstr.h"
  23 #include "llvm/CodeGen/MachineOperand.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/TargetInstrInfo.h"
  26 #include "llvm/CodeGen/TargetRegisterInfo.h"
  27 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  28 #include "llvm/InitializePasses.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/Support/Debug.h"
  31
  32 using namespace llvm;
  33
  34 #define DEBUG_TYPE "machine-latecleanup"
  35
  36 STATISTIC(NumRemoved, "Number of redundant instructions removed.");
  37
  38 namespace {
  39
  40 class MachineLateInstrsCleanup : public MachineFunctionPass {
  41   const TargetRegisterInfo *TRI = nullptr;
  42   const TargetInstrInfo *TII = nullptr;
  43
  44   // Data structures to map regs to their definitions and kills per MBB.
  45   struct Reg2MIMap : public SmallDenseMap<Register, MachineInstr *> {
  46     bool hasIdentical(Register Reg, MachineInstr *ArgMI) {
  47       MachineInstr *MI = lookup(Reg);
  48       return MI && MI->isIdenticalTo(*ArgMI);
  49     }
  50   };
  51
  52   std::vector<Reg2MIMap> RegDefs;
  53   std::vector<Reg2MIMap> RegKills;
  54
  55   // Walk through the instructions in MBB and remove any redundant
  56   // instructions.
  57   bool processBlock(MachineBasicBlock *MBB);
  58
  59   void removeRedundantDef(MachineInstr *MI);
  60   void clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
  61                         MachineBasicBlock::iterator I,
  62                         BitVector &VisitedPreds);
  63
  64 public:
  65   static char ID; // Pass identification, replacement for typeid
  66
  67   MachineLateInstrsCleanup() : MachineFunctionPass(ID) {
  68     initializeMachineLateInstrsCleanupPass(*PassRegistry::getPassRegistry());
  69   }
  70
  71   void getAnalysisUsage(AnalysisUsage &AU) const override {
  72     AU.setPreservesCFG();
  73     MachineFunctionPass::getAnalysisUsage(AU);
  74   }
  75
  76   bool runOnMachineFunction(MachineFunction &MF) override;
  77
  78   MachineFunctionProperties getRequiredProperties() const override {
  79     return MachineFunctionProperties().set(
  80         MachineFunctionProperties::Property::NoVRegs);
  81   }
  82 };
  83
  84 } // end anonymous namespace
  85
  86 char MachineLateInstrsCleanup::ID = 0;
  87
  88 char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID;
  89
  90 INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE,
  91                 "Machine Late Instructions Cleanup Pass", false, false)
  92
  93 bool MachineLateInstrsCleanup::runOnMachineFunction(MachineFunction &MF) {
  94   if (skipFunction(MF.getFunction()))
  95     return false;
  96
  97   TRI = MF.getSubtarget().getRegisterInfo();
  98   TII = MF.getSubtarget().getInstrInfo();
  99
 100   RegDefs.clear();
 101   RegDefs.resize(MF.getNumBlockIDs());
 102   RegKills.clear();
 103   RegKills.resize(MF.getNumBlockIDs());
 104
 105   // Visit all MBBs in an order that maximises the reuse from predecessors.
 106   bool Changed = false;
 107   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
 108   for (MachineBasicBlock *MBB : RPOT)
 109     Changed |= processBlock(MBB);
 110
 111   return Changed;
 112 }
 113
 114 // Clear any previous kill flag on Reg found before I in MBB. Walk backwards
 115 // in MBB and if needed continue in predecessors until a use/def of Reg is
 116 // encountered. This seems to be faster in practice than tracking kill flags
 117 // in a map.
 118 void MachineLateInstrsCleanup::
 119 clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
 120                  MachineBasicBlock::iterator I,
 121                  BitVector &VisitedPreds) {
 122   VisitedPreds.set(MBB->getNumber());
 123
 124   // Kill flag in MBB
 125   if (MachineInstr *KillMI = RegKills[MBB->getNumber()].lookup(Reg)) {
 126     KillMI->clearRegisterKills(Reg, TRI);
 127     return;
 128   }
 129
 130   // Def in MBB (missing kill flag)
 131   if (MachineInstr *DefMI = RegDefs[MBB->getNumber()].lookup(Reg))
 132     if (DefMI->getParent() == MBB)
 133       return;
 134
 135   // If an earlier def is not in MBB, continue in predecessors.
 136   if (!MBB->isLiveIn(Reg))
 137     MBB->addLiveIn(Reg);
 138   assert(!MBB->pred_empty() && "Predecessor def not found!");
 139   for (MachineBasicBlock *Pred : MBB->predecessors())
 140     if (!VisitedPreds.test(Pred->getNumber()))
 141       clearKillsForDef(Reg, Pred, Pred->end(), VisitedPreds);
 142 }
 143
 144 void MachineLateInstrsCleanup::removeRedundantDef(MachineInstr *MI) {
 145   Register Reg = MI->getOperand(0).getReg();
 146   BitVector VisitedPreds(MI->getMF()->getNumBlockIDs());
 147   clearKillsForDef(Reg, MI->getParent(), MI->getIterator(), VisitedPreds);
 148   MI->eraseFromParent();
 149   ++NumRemoved;
 150 }
 151
 152 // Return true if MI is a potential candidate for reuse/removal and if so
 153 // also the register it defines in DefedReg.  A candidate is a simple
 154 // instruction that does not touch memory, has only one register definition
 155 // and the only reg it may use is FrameReg. Typically this is an immediate
 156 // load or a load-address instruction.
 157 static bool isCandidate(const MachineInstr *MI, Register &DefedReg,
 158                         Register FrameReg) {
 159   DefedReg = MCRegister::NoRegister;
 160   bool SawStore = true;
 161   if (!MI->isSafeToMove(nullptr, SawStore) || MI->isImplicitDef() ||
 162       MI->isInlineAsm())
 163     return false;
 164   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 165     const MachineOperand &MO = MI->getOperand(i);
 166     if (MO.isReg()) {
 167       if (MO.isDef()) {
 168         if (i == 0 && !MO.isImplicit() && !MO.isDead())
 169           DefedReg = MO.getReg();
 170         else
 171           return false;
 172       } else if (MO.getReg() && MO.getReg() != FrameReg)
 173         return false;
 174     } else if (!(MO.isImm() || MO.isCImm() || MO.isFPImm() || MO.isCPI() ||
 175                  MO.isGlobal() || MO.isSymbol()))
 176       return false;
 177   }
 178   return DefedReg.isValid();
 179 }
 180
 181 bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) {
 182   bool Changed = false;
 183   Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];
 184   Reg2MIMap &MBBKills = RegKills[MBB->getNumber()];
 185
 186   // Find reusable definitions in the predecessor(s).
 187   if (!MBB->pred_empty() && !MBB->isEHPad() &&
 188       !MBB->isInlineAsmBrIndirectTarget()) {
 189     MachineBasicBlock *FirstPred = *MBB->pred_begin();
 190     for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
 191       if (llvm::all_of(
 192               drop_begin(MBB->predecessors()),
 193               [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {
 194                 return RegDefs[Pred->getNumber()].hasIdentical(Reg, DefMI);
 195               })) {
 196         MBBDefs[Reg] = DefMI;
 197         LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in "
 198                           << printMBBReference(*MBB) << ":  " << *DefMI;);
 199       }
 200   }
 201
 202   // Process MBB.
 203   MachineFunction *MF = MBB->getParent();
 204   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
 205   Register FrameReg = TRI->getFrameRegister(*MF);
 206   for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) {
 207     // If FrameReg is modified, no previous load-address instructions (using
 208     // it) are valid.
 209     if (MI.modifiesRegister(FrameReg, TRI)) {
 210       MBBDefs.clear();
 211       MBBKills.clear();
 212       continue;
 213     }
 214
 215     Register DefedReg;
 216     bool IsCandidate = isCandidate(&MI, DefedReg, FrameReg);
 217
 218     // Check for an earlier identical and reusable instruction.
 219     if (IsCandidate && MBBDefs.hasIdentical(DefedReg, &MI)) {
 220       LLVM_DEBUG(dbgs() << "Removing redundant instruction in "
 221                         << printMBBReference(*MBB) << ":  " << MI;);
 222       removeRedundantDef(&MI);
 223       Changed = true;
 224       continue;
 225     }
 226
 227     // Clear any entries in map that MI clobbers.
 228     for (auto DefI : llvm::make_early_inc_range(MBBDefs)) {
 229       Register Reg = DefI.first;
 230       if (MI.modifiesRegister(Reg, TRI)) {
 231         MBBDefs.erase(Reg);
 232         MBBKills.erase(Reg);
 233       } else if (MI.findRegisterUseOperandIdx(Reg, true /*isKill*/, TRI) != -1)
 234         // Keep track of register kills.
 235         MBBKills[Reg] = &MI;
 236     }
 237
 238     // Record this MI for potential later reuse.
 239     if (IsCandidate) {
 240       LLVM_DEBUG(dbgs() << "Found interesting instruction in "
 241                         << printMBBReference(*MBB) << ":  " << MI;);
 242       MBBDefs[DefedReg] = &MI;
 243       assert(!MBBKills.count(DefedReg) && "Should already have been removed.");
 244     }
 245   }
 246
 247   return Changed;
 248 }