LLVM 19.0.0git
Localizer.cpp
Go to the documentation of this file.
1//===- Localizer.cpp ---------------------- Localize some instrs -*- C++ -*-==//
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/// \file
9/// This file implements the Localizer class.
10//===----------------------------------------------------------------------===//
11
13#include "llvm/ADT/DenseMap.h"
14#include "llvm/ADT/STLExtras.h"
21#include "llvm/Support/Debug.h"
22
23#define DEBUG_TYPE "localizer"
24
25using namespace llvm;
26
27char Localizer::ID = 0;
29 "Move/duplicate certain instructions close to their use",
30 false, false)
33 "Move/duplicate certain instructions close to their use",
35
37 : MachineFunctionPass(ID), DoNotRunPass(F) {}
38
40 : Localizer([](const MachineFunction &) { return false; }) {}
41
42void Localizer::init(MachineFunction &MF) {
43 MRI = &MF.getRegInfo();
44 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
45}
46
51}
52
53bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
54 MachineBasicBlock *&InsertMBB) {
55 MachineInstr &MIUse = *MOUse.getParent();
56 InsertMBB = MIUse.getParent();
57 if (MIUse.isPHI())
58 InsertMBB = MIUse.getOperand(MOUse.getOperandNo() + 1).getMBB();
59 return InsertMBB == Def.getParent();
60}
61
62unsigned Localizer::getNumPhiUses(MachineOperand &Op) const {
63 auto *MI = dyn_cast<GPhi>(&*Op.getParent());
64 if (!MI)
65 return 0;
66
67 Register SrcReg = Op.getReg();
68 unsigned NumUses = 0;
69 for (unsigned I = 0, NumVals = MI->getNumIncomingValues(); I < NumVals; ++I) {
70 if (MI->getIncomingValue(I) == SrcReg)
71 ++NumUses;
72 }
73 return NumUses;
74}
75
76bool Localizer::localizeInterBlock(MachineFunction &MF,
77 LocalizedSetVecT &LocalizedInstrs) {
78 bool Changed = false;
80
81 // Since the IRTranslator only emits constants into the entry block, and the
82 // rest of the GISel pipeline generally emits constants close to their users,
83 // we only localize instructions in the entry block here. This might change if
84 // we start doing CSE across blocks.
85 auto &MBB = MF.front();
86 auto &TL = *MF.getSubtarget().getTargetLowering();
88 if (!TL.shouldLocalize(MI, TTI))
89 continue;
90 LLVM_DEBUG(dbgs() << "Should localize: " << MI);
91 assert(MI.getDesc().getNumDefs() == 1 &&
92 "More than one definition not supported yet");
93 Register Reg = MI.getOperand(0).getReg();
94 // Check if all the users of MI are local.
95 // We are going to invalidation the list of use operands, so we
96 // can't use range iterator.
97 for (MachineOperand &MOUse :
99 // Check if the use is already local.
100 MachineBasicBlock *InsertMBB;
101 LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
102 dbgs() << "Checking use: " << MIUse
103 << " #Opd: " << MOUse.getOperandNo() << '\n');
104 if (isLocalUse(MOUse, MI, InsertMBB)) {
105 // Even if we're in the same block, if the block is very large we could
106 // still have many long live ranges. Try to do intra-block localization
107 // too.
108 LocalizedInstrs.insert(&MI);
109 continue;
110 }
111
112 // PHIs look like a single user but can use the same register in multiple
113 // edges, causing remat into each predecessor. Allow this to a certain
114 // extent.
115 unsigned NumPhiUses = getNumPhiUses(MOUse);
116 const unsigned PhiThreshold = 2; // FIXME: Tune this more.
117 if (NumPhiUses > PhiThreshold)
118 continue;
119
120 LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
121 Changed = true;
122 auto MBBAndReg = std::make_pair(InsertMBB, Reg);
123 auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
124 if (NewVRegIt == MBBWithLocalDef.end()) {
125 // Create the localized instruction.
126 MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
127 LocalizedInstrs.insert(LocalizedMI);
128 MachineInstr &UseMI = *MOUse.getParent();
129 if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
130 InsertMBB->insert(UseMI, LocalizedMI);
131 else
132 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
133 LocalizedMI);
134
135 // Set a new register for the definition.
136 Register NewReg = MRI->cloneVirtualRegister(Reg);
137 LocalizedMI->getOperand(0).setReg(NewReg);
138 NewVRegIt =
139 MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
140 LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
141 }
142 LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
143 << '\n');
144 // Update the user reg.
145 MOUse.setReg(NewVRegIt->second);
146 }
147 }
148 return Changed;
149}
150
151bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
152 bool Changed = false;
153
154 // For each already-localized instruction which has multiple users, then we
155 // scan the block top down from the current position until we hit one of them.
156
157 // FIXME: Consider doing inst duplication if live ranges are very long due to
158 // many users, but this case may be better served by regalloc improvements.
159
160 for (MachineInstr *MI : LocalizedInstrs) {
161 Register Reg = MI->getOperand(0).getReg();
162 MachineBasicBlock &MBB = *MI->getParent();
163 // All of the user MIs of this reg.
165 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
166 if (!UseMI.isPHI())
167 Users.insert(&UseMI);
168 }
170 // If all the users were PHIs then they're not going to be in our block, we
171 // may still benefit from sinking, especially since the value might be live
172 // across a call.
173 if (Users.empty()) {
174 // Make sure we don't sink in between two terminator sequences by scanning
175 // forward, not backward.
177 LLVM_DEBUG(dbgs() << "Only phi users: moving inst to end: " << *MI);
178 } else {
179 ++II;
180 while (II != MBB.end() && !Users.count(&*II))
181 ++II;
182 assert(II != MBB.end() && "Didn't find the user in the MBB");
183 LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *II);
184 }
185
186 MI->removeFromParent();
187 MBB.insert(II, MI);
188 Changed = true;
189
190 // If the instruction (constant) being localized has single user, we can
191 // propagate debug location from user.
192 if (Users.size() == 1) {
193 const auto &DefDL = MI->getDebugLoc();
194 const auto &UserDL = (*Users.begin())->getDebugLoc();
195
196 if ((!DefDL || DefDL.getLine() == 0) && UserDL && UserDL.getLine() != 0) {
197 MI->setDebugLoc(UserDL);
198 }
199 }
200 }
201 return Changed;
202}
203
205 // If the ISel pipeline failed, do not bother running that pass.
206 if (MF.getProperties().hasProperty(
208 return false;
209
210 // Don't run the pass if the target asked so.
211 if (DoNotRunPass(MF))
212 return false;
213
214 LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
215
216 init(MF);
217
218 // Keep track of the instructions we localized. We'll do a second pass of
219 // intra-block localization to further reduce live ranges.
220 LocalizedSetVecT LocalizedInstrs;
221
222 bool Changed = localizeInterBlock(MF, LocalizedInstrs);
223 Changed |= localizeIntraBlock(LocalizedInstrs);
224 return Changed;
225}
MachineInstrBuilder & UseMI
aarch64 promote const
MachineBasicBlock & MBB
Performs the initial survey of the specified function
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
Declares convenience wrapper classes for interpreting MachineInstr instances as specific generic oper...
IRTranslator LLVM IR MI
iv Induction Variable Users
Definition: IVUsers.cpp:48
Select target instructions out of generic instructions
Move duplicate certain instructions close to their use
Definition: Localizer.cpp:33
#define DEBUG_TYPE
Definition: Localizer.cpp:23
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
Return the first found DebugLoc that has a DILocation, given a range of instructions.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file describes how to lower LLVM code to machine code.
This pass exposes codegen information to IR-level passes.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
This pass implements the localization mechanism described at the top of this file.
Definition: Localizer.h:43
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Localizer.cpp:47
static char ID
Definition: Localizer.h:45
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: Localizer.cpp:204
iterator getFirstTerminatorForward()
Finds the first terminator in a block by scanning forward.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
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.
bool hasProperty(Property P) const
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineFunctionProperties & getProperties() const
Get the function properties.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
const MachineBasicBlock & front() const
Representation of each machine instruction.
Definition: MachineInstr.h:68
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:326
void insert(mop_iterator InsertBefore, ArrayRef< MachineOperand > Ops)
Inserts Ops BEFORE It. Can untie/retie tied operands.
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:553
MachineOperand class - Representation of each machine instruction operand.
unsigned getOperandNo() const
Returns the index of this operand in the instruction that it belongs to.
MachineBasicBlock * getMBB() const
void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool hasOneUse(Register RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Register cloneVirtualRegister(Register VReg, StringRef Name="")
Create and return a new virtual register in the function with the same attributes as the given regist...
iterator_range< use_iterator > use_operands(Register Reg) const
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
virtual const TargetLowering * getTargetLowering() const
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
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
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
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:1072
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858