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/Analysis/TargetTransformInfo.h"
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
17 #include "llvm/CodeGen/TargetLowering.h"
18 #include "llvm/InitializePasses.h"
19 #include "llvm/Support/Debug.h"
20
21 #define DEBUG_TYPE "localizer"
22
23 using namespace llvm;
24
25 char Localizer::ID = 0;
26 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
27 "Move/duplicate certain instructions close to their use",
28 false, false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)29 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
30 INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,
31 "Move/duplicate certain instructions close to their use",
32 false, false)
33
34 Localizer::Localizer(std::function<bool(const MachineFunction &)> F)
35 : MachineFunctionPass(ID), DoNotRunPass(F) {}
36
Localizer()37 Localizer::Localizer()
38 : Localizer([](const MachineFunction &) { return false; }) {}
39
init(MachineFunction & MF)40 void Localizer::init(MachineFunction &MF) {
41 MRI = &MF.getRegInfo();
42 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
43 }
44
getAnalysisUsage(AnalysisUsage & AU) const45 void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {
46 AU.addRequired<TargetTransformInfoWrapperPass>();
47 getSelectionDAGFallbackAnalysisUsage(AU);
48 MachineFunctionPass::getAnalysisUsage(AU);
49 }
50
isLocalUse(MachineOperand & MOUse,const MachineInstr & Def,MachineBasicBlock * & InsertMBB)51 bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
52 MachineBasicBlock *&InsertMBB) {
53 MachineInstr &MIUse = *MOUse.getParent();
54 InsertMBB = MIUse.getParent();
55 if (MIUse.isPHI())
56 InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB();
57 return InsertMBB == Def.getParent();
58 }
59
isNonUniquePhiValue(MachineOperand & Op) const60 bool Localizer::isNonUniquePhiValue(MachineOperand &Op) const {
61 MachineInstr *MI = Op.getParent();
62 if (!MI->isPHI())
63 return false;
64
65 Register SrcReg = Op.getReg();
66 for (unsigned Idx = 1; Idx < MI->getNumOperands(); Idx += 2) {
67 auto &MO = MI->getOperand(Idx);
68 if (&MO != &Op && MO.isReg() && MO.getReg() == SrcReg)
69 return true;
70 }
71 return false;
72 }
73
localizeInterBlock(MachineFunction & MF,LocalizedSetVecT & LocalizedInstrs)74 bool Localizer::localizeInterBlock(MachineFunction &MF,
75 LocalizedSetVecT &LocalizedInstrs) {
76 bool Changed = false;
77 DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
78
79 // Since the IRTranslator only emits constants into the entry block, and the
80 // rest of the GISel pipeline generally emits constants close to their users,
81 // we only localize instructions in the entry block here. This might change if
82 // we start doing CSE across blocks.
83 auto &MBB = MF.front();
84 auto &TL = *MF.getSubtarget().getTargetLowering();
85 for (auto RI = MBB.rbegin(), RE = MBB.rend(); RI != RE; ++RI) {
86 MachineInstr &MI = *RI;
87 if (!TL.shouldLocalize(MI, TTI))
88 continue;
89 LLVM_DEBUG(dbgs() << "Should localize: " << MI);
90 assert(MI.getDesc().getNumDefs() == 1 &&
91 "More than one definition not supported yet");
92 Register Reg = MI.getOperand(0).getReg();
93 // Check if all the users of MI are local.
94 // We are going to invalidation the list of use operands, so we
95 // can't use range iterator.
96 for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end();
97 MOIt != MOItEnd;) {
98 MachineOperand &MOUse = *MOIt++;
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: " << MIUse.getOperandNo(&MOUse) << '\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 // If the use is a phi operand that's not unique, don't try to localize.
113 // If we do, we can cause unnecessary instruction bloat by duplicating
114 // into each predecessor block, when the existing one is sufficient and
115 // allows for easier optimization later.
116 if (isNonUniquePhiValue(MOUse))
117 continue;
118
119 LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
120 Changed = true;
121 auto MBBAndReg = std::make_pair(InsertMBB, Reg);
122 auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
123 if (NewVRegIt == MBBWithLocalDef.end()) {
124 // Create the localized instruction.
125 MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
126 LocalizedInstrs.insert(LocalizedMI);
127 MachineInstr &UseMI = *MOUse.getParent();
128 if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
129 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(UseMI), LocalizedMI);
130 else
131 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
132 LocalizedMI);
133
134 // Set a new register for the definition.
135 Register NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg));
136 MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(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
localizeIntraBlock(LocalizedSetVecT & LocalizedInstrs)151 bool 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.
164 SmallPtrSet<MachineInstr *, 32> Users;
165 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
166 if (!UseMI.isPHI())
167 Users.insert(&UseMI);
168 }
169 // If all the users were PHIs then they're not going to be in our block,
170 // don't try to move this instruction.
171 if (Users.empty())
172 continue;
173
174 MachineBasicBlock::iterator II(MI);
175 ++II;
176 while (II != MBB.end() && !Users.count(&*II))
177 ++II;
178
179 LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
180 << "\n");
181 assert(II != MBB.end() && "Didn't find the user in the MBB");
182 MI->removeFromParent();
183 MBB.insert(II, MI);
184 Changed = true;
185 }
186 return Changed;
187 }
188
runOnMachineFunction(MachineFunction & MF)189 bool Localizer::runOnMachineFunction(MachineFunction &MF) {
190 // If the ISel pipeline failed, do not bother running that pass.
191 if (MF.getProperties().hasProperty(
192 MachineFunctionProperties::Property::FailedISel))
193 return false;
194
195 // Don't run the pass if the target asked so.
196 if (DoNotRunPass(MF))
197 return false;
198
199 LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
200
201 init(MF);
202
203 // Keep track of the instructions we localized. We'll do a second pass of
204 // intra-block localization to further reduce live ranges.
205 LocalizedSetVecT LocalizedInstrs;
206
207 bool Changed = localizeInterBlock(MF, LocalizedInstrs);
208 Changed |= localizeIntraBlock(LocalizedInstrs);
209 return Changed;
210 }
211