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