LLVM 17.0.0git
MachineLateInstrsCleanup.cpp
Go to the documentation of this file.
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"
19#include "llvm/ADT/Statistic.h"
30#include "llvm/Pass.h"
31#include "llvm/Support/Debug.h"
32
33using namespace llvm;
34
35#define DEBUG_TYPE "machine-latecleanup"
36
37STATISTIC(NumRemoved, "Number of redundant instructions removed.");
38
39namespace {
40
41class MachineLateInstrsCleanup : public MachineFunctionPass {
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
53public:
54 static char ID; // Pass identification, replacement for typeid
55
56 MachineLateInstrsCleanup() : MachineFunctionPass(ID) {
58 }
59
60 void getAnalysisUsage(AnalysisUsage &AU) const override {
61 AU.setPreservesCFG();
63 }
64
65 bool runOnMachineFunction(MachineFunction &MF) override;
66
69 MachineFunctionProperties::Property::NoVRegs);
70 }
71};
72
73} // end anonymous namespace
74
75char MachineLateInstrsCleanup::ID = 0;
76
77char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID;
78
79INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE,
80 "Machine Late Instructions Cleanup Pass", false, false)
81
82bool 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;
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.
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
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.
149static 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
173bool 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 MachineBasicBlock *FirstPred = *MBB->pred_begin();
180 for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
181 if (llvm::all_of(
183 [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {
184 auto PredDefI = RegDefs[Pred->getNumber()].find(Reg);
185 return PredDefI != RegDefs[Pred->getNumber()].end() &&
186 DefMI->isIdenticalTo(*PredDefI->second);
187 })) {
188 MBBDefs[Reg] = DefMI;
189 LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in "
190 << printMBBReference(*MBB) << ": " << *DefMI;);
191 }
192 }
193
194 // Process MBB.
197 Register FrameReg = TRI->getFrameRegister(*MF);
199 // If FrameReg is modified, no previous load-address instructions (using
200 // it) are valid.
201 if (MI.modifiesRegister(FrameReg, TRI)) {
202 MBBDefs.clear();
203 continue;
204 }
205
206 Register DefedReg;
207 bool IsCandidate = isCandidate(&MI, DefedReg, FrameReg);
208
209 // Check for an earlier identical and reusable instruction.
210 if (IsCandidate) {
211 auto DefI = MBBDefs.find(DefedReg);
212 if (DefI != MBBDefs.end() && MI.isIdenticalTo(*DefI->second)) {
213 LLVM_DEBUG(dbgs() << "Removing redundant instruction in "
214 << printMBBReference(*MBB) << ": " << MI;);
216 Changed = true;
217 continue;
218 }
219 }
220
221 // Clear any entries in map that MI clobbers.
222 for (auto DefI = MBBDefs.begin(); DefI != MBBDefs.end();) {
223 Register Reg = DefI->first;
224 if (MI.modifiesRegister(Reg, TRI))
225 DefI = MBBDefs.erase(DefI);
226 else
227 ++DefI;
228 }
229
230 // Record this MI for potential later reuse.
231 if (IsCandidate) {
232 LLVM_DEBUG(dbgs() << "Found interesting instruction in "
233 << printMBBReference(*MBB) << ": " << MI;);
234 MBBDefs[DefedReg] = &MI;
235 }
236 }
237
238 return Changed;
239}
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock & MBB
This file implements the BitVector class.
#define LLVM_DEBUG(X)
Definition: Debug.h:101
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)
static void clearKillsForDef(Register Reg, MachineBasicBlock *MBB, MachineBasicBlock::iterator I, BitVector &VisitedPreds, const TargetRegisterInfo *TRI)
static void removeRedundantDef(MachineInstr *MI, const TargetRegisterInfo *TRI)
#define DEBUG_TYPE
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & set()
Definition: BitVector.h:351
static constexpr unsigned NoRegister
Definition: MCRegister.h:43
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< pred_iterator > predecessors()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineOperand class - Representation of each machine instruction operand.
bool isCImm() const
isCImm - Test if this is a MO_CImmediate operand.
bool isImplicit() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isCPI() const
isCPI - Tests if this is a MO_ConstantPoolIndex operand.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
bool isSymbol() const
isSymbol - Tests if this is a MO_ExternalSymbol operand.
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
Register getReg() const
getReg - Returns the register number.
bool isFPImm() const
isFPImm - Tests if this is a MO_FPImmediate operand.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isValid() const
Definition: Register.h:126
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:413
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:748
char & MachineLateInstrsCleanupID
MachineLateInstrsCleanup - This pass removes redundant identical instructions after register allocati...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void initializeMachineLateInstrsCleanupPass(PassRegistry &)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.