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