LLVM 19.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"
18#include "llvm/ADT/Statistic.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/Debug.h"
31
32using namespace llvm;
33
34#define DEBUG_TYPE "machine-latecleanup"
35
36STATISTIC(NumRemoved, "Number of redundant instructions removed.");
37
38namespace {
39
40class 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,
62 BitVector &VisitedPreds);
63
64public:
65 static char ID; // Pass identification, replacement for typeid
66
67 MachineLateInstrsCleanup() : MachineFunctionPass(ID) {
69 }
70
71 void getAnalysisUsage(AnalysisUsage &AU) const override {
72 AU.setPreservesCFG();
74 }
75
76 bool runOnMachineFunction(MachineFunction &MF) override;
77
80 MachineFunctionProperties::Property::NoVRegs);
81 }
82};
83
84} // end anonymous namespace
85
86char MachineLateInstrsCleanup::ID = 0;
87
88char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID;
89
90INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE,
91 "Machine Late Instructions Cleanup Pass", false, false)
92
93bool 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;
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.
118void MachineLateInstrsCleanup::
119clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
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
144void 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.
157static 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
181bool 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() &&
189 MachineBasicBlock *FirstPred = *MBB->pred_begin();
190 for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
191 if (llvm::all_of(
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.
205 Register FrameReg = TRI->getFrameRegister(*MF);
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}
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 '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:269
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & set()
Definition: BitVector.h:351
static constexpr unsigned NoRegister
Definition: MCRegister.h:52
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:326
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:329
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:1731
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:665
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.