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 {
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,
63 BitVector &VisitedPreds);
64
65public:
66 static char ID; // Pass identification, replacement for typeid
67
68 MachineLateInstrsCleanup() : MachineFunctionPass(ID) {
70 }
71
72 void getAnalysisUsage(AnalysisUsage &AU) const override {
73 AU.setPreservesCFG();
75 }
76
77 bool runOnMachineFunction(MachineFunction &MF) override;
78
81 MachineFunctionProperties::Property::NoVRegs);
82 }
83};
84
85} // end anonymous namespace
86
87char MachineLateInstrsCleanup::ID = 0;
88
89char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID;
90
91INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE,
92 "Machine Late Instructions Cleanup Pass", false, false)
93
94bool 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;
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.
119void MachineLateInstrsCleanup::
120clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
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
145void 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.
158static 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
182bool 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() &&
190 MachineBasicBlock *FirstPred = *MBB->pred_begin();
191 for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
192 if (llvm::all_of(
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.
206 Register FrameReg = TRI->getFrameRegister(*MF);
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}
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
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
Definition: InlineInfo.cpp:109
#define I(x, y, z)
Definition: MD5.cpp:58
static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)
#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 isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
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
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:320
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
constexpr bool isValid() const
Definition: Register.h:116
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.