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