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
12#include "llvm/CodeGen/GlobalISel/Localizer.h"
13#include "llvm/ADT/DenseMap.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/Analysis/TargetTransformInfo.h"
17#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
18#include "llvm/CodeGen/GlobalISel/Utils.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
21#include "llvm/CodeGen/MachinePassManager.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/CodeGen/TargetLowering.h"
24#include "llvm/IR/Analysis.h"
25#include "llvm/IR/DebugInfoMetadata.h"
26#include "llvm/InitializePasses.h"
27#include "llvm/Support/Debug.h"
28
29#define DEBUG_TYPE "localizer"
30
31using namespace llvm;
32
33namespace {
34
35class LocalizerImpl {
36 /// MRI contains all the register class/bank information that this
37 /// pass uses and updates.
38 MachineRegisterInfo *MRI = nullptr;
39 /// TTI used for getting remat costs for instructions.
40 TargetTransformInfo *TTI = nullptr;
41
42 /// Check if \p MOUse is used in the same basic block as \p Def.
43 /// If the use is in the same block, we say it is local.
44 /// When the use is not local, \p InsertMBB will contain the basic
45 /// block when to insert \p Def to have a local use.
46 static bool isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
47 MachineBasicBlock *&InsertMBB);
48
49 /// Initialize the field members using \p MF.
50 void init(MachineFunction &MF, function_ref<TargetTransformInfo *()> GetTTI);
51
52 typedef SmallSetVector<MachineInstr *, 32> LocalizedSetVecT;
53
54 /// If \p Op is a reg operand of a PHI, return the number of total
55 /// operands in the PHI that are the same as \p Op, including itself.
56 unsigned getNumPhiUses(MachineOperand &Op) const;
57
58 /// Do inter-block localization from the entry block.
59 bool localizeInterBlock(MachineFunction &MF,
60 LocalizedSetVecT &LocalizedInstrs);
61
62 /// Do intra-block localization of already localized instructions.
63 bool localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs);
64
65public:
66 bool runOnMachineFunction(MachineFunction &MF,
67 function_ref<TargetTransformInfo *()> GetTTI);
68};
69
70} // namespace
71
72char LocalizerLegacy::ID = 0;
73INITIALIZE_PASS_BEGIN(LocalizerLegacy, DEBUG_TYPE,
74 "Move/duplicate certain instructions close to their use",
75 false, false)
76INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
77INITIALIZE_PASS_END(LocalizerLegacy, DEBUG_TYPE,
78 "Move/duplicate certain instructions close to their use",
79 false, false)
80
81LocalizerLegacy::LocalizerLegacy() : MachineFunctionPass(ID) {}
82
83void LocalizerImpl::init(MachineFunction &MF,
84 function_ref<TargetTransformInfo *()> GetTTI) {
85 MRI = &MF.getRegInfo();
86 TTI = GetTTI();
87}
88
89void LocalizerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
90 AU.addRequired<TargetTransformInfoWrapperPass>();
91 AU.setPreservesCFG();
92 getSelectionDAGFallbackAnalysisUsage(AU);
93 MachineFunctionPass::getAnalysisUsage(AU);
94}
95
96bool LocalizerImpl::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
97 MachineBasicBlock *&InsertMBB) {
98 MachineInstr &MIUse = *MOUse.getParent();
99 InsertMBB = MIUse.getParent();
100 if (MIUse.isPHI())
101 InsertMBB = MIUse.getOperand(i: MOUse.getOperandNo() + 1).getMBB();
102 return InsertMBB == Def.getParent();
103}
104
105unsigned LocalizerImpl::getNumPhiUses(MachineOperand &Op) const {
106 auto *MI = dyn_cast<GPhi>(Val: &*Op.getParent());
107 if (!MI)
108 return 0;
109
110 Register SrcReg = Op.getReg();
111 unsigned NumUses = 0;
112 for (unsigned I = 0, NumVals = MI->getNumIncomingValues(); I < NumVals; ++I) {
113 if (MI->getIncomingValue(I) == SrcReg)
114 ++NumUses;
115 }
116 return NumUses;
117}
118
119bool LocalizerImpl::localizeInterBlock(MachineFunction &MF,
120 LocalizedSetVecT &LocalizedInstrs) {
121 bool Changed = false;
122 DenseMap<std::pair<MachineBasicBlock *, Register>, Register> MBBWithLocalDef;
123
124 // Since the IRTranslator only emits constants into the entry block, and the
125 // rest of the GISel pipeline generally emits constants close to their users,
126 // we only localize instructions in the entry block here. This might change if
127 // we start doing CSE across blocks.
128 auto &MBB = MF.front();
129 auto &TL = *MF.getSubtarget().getTargetLowering();
130 for (MachineInstr &MI : llvm::reverse(C&: MBB)) {
131 if (!TL.shouldLocalize(MI, TTI))
132 continue;
133 LLVM_DEBUG(dbgs() << "Should localize: " << MI);
134 assert(MI.getDesc().getNumDefs() == 1 &&
135 "More than one definition not supported yet");
136 Register Reg = MI.getOperand(i: 0).getReg();
137 // Check if all the users of MI are local. We are going to invalidate the
138 // list of use operands, so we can't use a range iterator. Debug users stay
139 // with the original definition.
140 for (MachineOperand &MOUse :
141 llvm::make_early_inc_range(Range: MRI->use_nodbg_operands(Reg))) {
142 // Check if the use is already local.
143 MachineBasicBlock *InsertMBB;
144 LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
145 dbgs() << "Checking use: " << MIUse
146 << " #Opd: " << MOUse.getOperandNo() << '\n');
147 if (isLocalUse(MOUse, Def: MI, InsertMBB)) {
148 // Even if we're in the same block, if the block is very large we could
149 // still have many long live ranges. Try to do intra-block localization
150 // too.
151 LocalizedInstrs.insert(X: &MI);
152 continue;
153 }
154
155 // PHIs look like a single user but can use the same register in multiple
156 // edges, causing remat into each predecessor. Allow this to a certain
157 // extent.
158 unsigned NumPhiUses = getNumPhiUses(Op&: MOUse);
159 const unsigned PhiThreshold = 2; // FIXME: Tune this more.
160 if (NumPhiUses > PhiThreshold)
161 continue;
162
163 LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
164 Changed = true;
165 auto MBBAndReg = std::make_pair(x&: InsertMBB, y&: Reg);
166 auto NewVRegIt = MBBWithLocalDef.find(Val: MBBAndReg);
167 if (NewVRegIt == MBBWithLocalDef.end()) {
168 // Create the localized instruction.
169 MachineInstr *LocalizedMI = MF.CloneMachineInstr(Orig: &MI);
170 LocalizedInstrs.insert(X: LocalizedMI);
171 MachineInstr &UseMI = *MOUse.getParent();
172 if (MRI->hasOneNonDBGUse(RegNo: Reg) && !UseMI.isPHI())
173 InsertMBB->insert(I: UseMI, MI: LocalizedMI);
174 else
175 InsertMBB->insert(I: InsertMBB->SkipPHIsAndLabels(I: InsertMBB->begin()),
176 MI: LocalizedMI);
177
178 // Set a new register for the definition.
179 Register NewReg = MRI->cloneVirtualRegister(VReg: Reg);
180 LocalizedMI->getOperand(i: 0).setReg(NewReg);
181 NewVRegIt =
182 MBBWithLocalDef.try_emplace(Key: MBBAndReg, Args&: NewReg).first;
183 LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
184 }
185 LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
186 << '\n');
187 // Update the user reg.
188 MOUse.setReg(NewVRegIt->second);
189 }
190 }
191 return Changed;
192}
193
194bool LocalizerImpl::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
195 bool Changed = false;
196
197 // For each already-localized instruction which has multiple users, then we
198 // scan the block top down from the current position until we hit one of them.
199
200 // FIXME: Consider doing inst duplication if live ranges are very long due to
201 // many users, but this case may be better served by regalloc improvements.
202
203 for (MachineInstr *MI : LocalizedInstrs) {
204 Register Reg = MI->getOperand(i: 0).getReg();
205 MachineBasicBlock &MBB = *MI->getParent();
206 // All of the user MIs of this reg.
207 SmallPtrSet<MachineInstr *, 32> Users;
208 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
209 if (!UseMI.isPHI())
210 Users.insert(Ptr: &UseMI);
211 }
212 MachineBasicBlock::iterator II(MI);
213 // If all the users were PHIs then they're not going to be in our block, we
214 // may still benefit from sinking, especially since the value might be live
215 // across a call.
216 if (Users.empty()) {
217 // Make sure we don't sink in between two terminator sequences by scanning
218 // forward, not backward.
219 II = MBB.getFirstTerminatorForward();
220 LLVM_DEBUG(dbgs() << "Only phi users: moving inst to end: " << *MI);
221 } else {
222 ++II;
223 while (II != MBB.end() && !Users.count(Ptr: &*II))
224 ++II;
225 assert(II != MBB.end() && "Didn't find the user in the MBB");
226 LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *II);
227 }
228
229 // Leave each DBG_VALUE above MI that uses one of its results behind as
230 // undef, so that it still ends any earlier location of the variable, and
231 // put a copy right after MI, like MachineSink does. No copy is needed if a
232 // later DBG_VALUE of the same variable replaces it before that.
233 SmallVector<MachineInstr *, 4> DbgUsers;
234 SmallVector<MachineInstr *, 4> DbgUsersToCopy;
235 for (MachineInstr &DbgMI :
236 make_range(x: std::next(x: MachineBasicBlock::iterator(MI)), y: II)) {
237 if (!DbgMI.isDebugValue())
238 continue;
239 erase_if(C&: DbgUsersToCopy, P: [&](const MachineInstr *Earlier) {
240 return Earlier->getDebugVariable() == DbgMI.getDebugVariable() &&
241 Earlier->getDebugLoc().getInlinedAt() ==
242 DbgMI.getDebugLoc().getInlinedAt() &&
243 Earlier->getDebugExpression()->fragmentsOverlap(
244 Other: DbgMI.getDebugExpression());
245 });
246 if (DbgMI.hasDebugOperandForReg(Reg)) {
247 DbgUsers.push_back(Elt: &DbgMI);
248 DbgUsersToCopy.push_back(Elt: &DbgMI);
249 }
250 }
251
252 MI->removeFromParent();
253 MBB.insert(I: II, MI);
254 Changed = true;
255
256 for (MachineInstr *DbgMI : DbgUsersToCopy)
257 MBB.insert(I: II, MI: MBB.getParent()->CloneMachineInstr(Orig: DbgMI));
258 for (MachineInstr *DbgMI : DbgUsers)
259 DbgMI->setDebugValueUndef();
260
261 // If the instruction (constant) being localized has single user, we can
262 // propagate debug location from user.
263 if (Users.size() == 1) {
264 const auto &DefDL = MI->getDebugLoc();
265 const auto &UserDL = (*Users.begin())->getDebugLoc();
266
267 if ((!DefDL || DefDL.getLine() == 0) && UserDL && UserDL.getLine() != 0) {
268 MI->setDebugLoc(UserDL);
269 }
270 }
271 }
272 return Changed;
273}
274
275bool LocalizerImpl::runOnMachineFunction(
276 MachineFunction &MF, function_ref<TargetTransformInfo *()> GetTTI) {
277 // If the ISel pipeline failed, do not bother running that pass.
278 if (MF.getProperties().hasFailedISel())
279 return false;
280
281 LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
282
283 init(MF, GetTTI);
284
285 // Keep track of the instructions we localized. We'll do a second pass of
286 // intra-block localization to further reduce live ranges.
287 LocalizedSetVecT LocalizedInstrs;
288
289 bool Changed = localizeInterBlock(MF, LocalizedInstrs);
290 Changed |= localizeIntraBlock(LocalizedInstrs);
291 return Changed;
292}
293
294bool LocalizerLegacy::runOnMachineFunction(MachineFunction &MF) {
295 LocalizerImpl Impl;
296 return Impl.runOnMachineFunction(MF, GetTTI: [&]() {
297 return &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
298 F: MF.getFunction());
299 });
300}
301
302PreservedAnalyses LocalizerPass::run(MachineFunction &MF,
303 MachineFunctionAnalysisManager &MFAM) {
304 MFPropsModifier<LocalizerPass> _(*this, MF);
305 LocalizerImpl Impl;
306 bool Changed = Impl.runOnMachineFunction(MF, GetTTI: [&]() {
307 Function &F = MF.getFunction();
308 FunctionAnalysisManager &FAM =
309 MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
310 .getManager();
311 return &FAM.getResult<TargetIRAnalysis>(IR&: F);
312 });
313 return Changed ? getMachineFunctionPassPreservedAnalyses()
314 .preserveSet<CFGAnalyses>()
315 : PreservedAnalyses::all();
316}
317