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/Analysis/TargetTransformInfo.h"
15 #include "llvm/CodeGen/MachineRegisterInfo.h"
16 #include "llvm/CodeGen/TargetLowering.h"
17 #include "llvm/InitializePasses.h"
18 #include "llvm/Support/Debug.h"
19
20 #define DEBUG_TYPE "localizer"
21
22 using namespace llvm;
23
24 char Localizer::ID = 0;
25 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
26 "Move/duplicate certain instructions close to their use",
27 false, false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)28 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
29 INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,
30 "Move/duplicate certain instructions close to their use",
31 false, false)
32
33 Localizer::Localizer(std::function<bool(const MachineFunction &)> F)
34 : MachineFunctionPass(ID), DoNotRunPass(F) {}
35
Localizer()36 Localizer::Localizer()
37 : Localizer([](const MachineFunction &) { return false; }) {}
38
init(MachineFunction & MF)39 void Localizer::init(MachineFunction &MF) {
40 MRI = &MF.getRegInfo();
41 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
42 }
43
getAnalysisUsage(AnalysisUsage & AU) const44 void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {
45 AU.addRequired<TargetTransformInfoWrapperPass>();
46 getSelectionDAGFallbackAnalysisUsage(AU);
47 MachineFunctionPass::getAnalysisUsage(AU);
48 }
49
isLocalUse(MachineOperand & MOUse,const MachineInstr & Def,MachineBasicBlock * & InsertMBB)50 bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
51 MachineBasicBlock *&InsertMBB) {
52 MachineInstr &MIUse = *MOUse.getParent();
53 InsertMBB = MIUse.getParent();
54 if (MIUse.isPHI())
55 InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB();
56 return InsertMBB == Def.getParent();
57 }
58
localizeInterBlock(MachineFunction & MF,LocalizedSetVecT & LocalizedInstrs)59 bool Localizer::localizeInterBlock(MachineFunction &MF,
60 LocalizedSetVecT &LocalizedInstrs) {
61 bool Changed = false;
62 DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
63
64 // Since the IRTranslator only emits constants into the entry block, and the
65 // rest of the GISel pipeline generally emits constants close to their users,
66 // we only localize instructions in the entry block here. This might change if
67 // we start doing CSE across blocks.
68 auto &MBB = MF.front();
69 auto &TL = *MF.getSubtarget().getTargetLowering();
70 for (auto RI = MBB.rbegin(), RE = MBB.rend(); RI != RE; ++RI) {
71 MachineInstr &MI = *RI;
72 if (!TL.shouldLocalize(MI, TTI))
73 continue;
74 LLVM_DEBUG(dbgs() << "Should localize: " << MI);
75 assert(MI.getDesc().getNumDefs() == 1 &&
76 "More than one definition not supported yet");
77 Register Reg = MI.getOperand(0).getReg();
78 // Check if all the users of MI are local.
79 // We are going to invalidation the list of use operands, so we
80 // can't use range iterator.
81 for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end();
82 MOIt != MOItEnd;) {
83 MachineOperand &MOUse = *MOIt++;
84 // Check if the use is already local.
85 MachineBasicBlock *InsertMBB;
86 LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
87 dbgs() << "Checking use: " << MIUse
88 << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n');
89 if (isLocalUse(MOUse, MI, InsertMBB)) {
90 // Even if we're in the same block, if the block is very large we could
91 // still have many long live ranges. Try to do intra-block localization
92 // too.
93 LocalizedInstrs.insert(&MI);
94 continue;
95 }
96 LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
97 Changed = true;
98 auto MBBAndReg = std::make_pair(InsertMBB, Reg);
99 auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
100 if (NewVRegIt == MBBWithLocalDef.end()) {
101 // Create the localized instruction.
102 MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
103 LocalizedInstrs.insert(LocalizedMI);
104 MachineInstr &UseMI = *MOUse.getParent();
105 if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
106 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(UseMI), LocalizedMI);
107 else
108 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
109 LocalizedMI);
110
111 // Set a new register for the definition.
112 Register NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg));
113 MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg));
114 LocalizedMI->getOperand(0).setReg(NewReg);
115 NewVRegIt =
116 MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
117 LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
118 }
119 LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
120 << '\n');
121 // Update the user reg.
122 MOUse.setReg(NewVRegIt->second);
123 }
124 }
125 return Changed;
126 }
127
localizeIntraBlock(LocalizedSetVecT & LocalizedInstrs)128 bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
129 bool Changed = false;
130
131 // For each already-localized instruction which has multiple users, then we
132 // scan the block top down from the current position until we hit one of them.
133
134 // FIXME: Consider doing inst duplication if live ranges are very long due to
135 // many users, but this case may be better served by regalloc improvements.
136
137 for (MachineInstr *MI : LocalizedInstrs) {
138 Register Reg = MI->getOperand(0).getReg();
139 MachineBasicBlock &MBB = *MI->getParent();
140 // All of the user MIs of this reg.
141 SmallPtrSet<MachineInstr *, 32> Users;
142 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
143 if (!UseMI.isPHI())
144 Users.insert(&UseMI);
145 }
146 // If all the users were PHIs then they're not going to be in our block,
147 // don't try to move this instruction.
148 if (Users.empty())
149 continue;
150
151 MachineBasicBlock::iterator II(MI);
152 ++II;
153 while (II != MBB.end() && !Users.count(&*II))
154 ++II;
155
156 LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
157 << "\n");
158 assert(II != MBB.end() && "Didn't find the user in the MBB");
159 MI->removeFromParent();
160 MBB.insert(II, MI);
161 Changed = true;
162 }
163 return Changed;
164 }
165
runOnMachineFunction(MachineFunction & MF)166 bool Localizer::runOnMachineFunction(MachineFunction &MF) {
167 // If the ISel pipeline failed, do not bother running that pass.
168 if (MF.getProperties().hasProperty(
169 MachineFunctionProperties::Property::FailedISel))
170 return false;
171
172 // Don't run the pass if the target asked so.
173 if (DoNotRunPass(MF))
174 return false;
175
176 LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
177
178 init(MF);
179
180 // Keep track of the instructions we localized. We'll do a second pass of
181 // intra-block localization to further reduce live ranges.
182 LocalizedSetVecT LocalizedInstrs;
183
184 bool Changed = localizeInterBlock(MF, LocalizedInstrs);
185 Changed |= localizeIntraBlock(LocalizedInstrs);
186 return Changed;
187 }
188