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/GlobalISel/GenericMachineInstrs.h"
17 #include "llvm/CodeGen/GlobalISel/Utils.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/CodeGen/TargetLowering.h"
20 #include "llvm/InitializePasses.h"
21 #include "llvm/Support/Debug.h"
22 
23 #define DEBUG_TYPE "localizer"
24 
25 using namespace llvm;
26 
27 char Localizer::ID = 0;
28 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
29                       "Move/duplicate certain instructions close to their use",
30                       false, false)
31 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
32 INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,
33                     "Move/duplicate certain instructions close to their use",
34                     false, false)
35 
36 Localizer::Localizer(std::function<bool(const MachineFunction &)> F)
37     : MachineFunctionPass(ID), DoNotRunPass(F) {}
38 
39 Localizer::Localizer()
40     : Localizer([](const MachineFunction &) { return false; }) {}
41 
42 void Localizer::init(MachineFunction &MF) {
43   MRI = &MF.getRegInfo();
44   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
45 }
46 
47 void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {
48   AU.addRequired<TargetTransformInfoWrapperPass>();
49   getSelectionDAGFallbackAnalysisUsage(AU);
50   MachineFunctionPass::getAnalysisUsage(AU);
51 }
52 
53 bool 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 
62 unsigned 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 
76 bool Localizer::localizeInterBlock(MachineFunction &MF,
77                                    LocalizedSetVecT &LocalizedInstrs) {
78   bool Changed = false;
79   DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
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();
87   for (MachineInstr &MI : llvm::reverse(MBB)) {
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 :
98          llvm::make_early_inc_range(MRI->use_operands(Reg))) {
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 
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     MachineBasicBlock::iterator II(MI);
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.
176       II = MBB.getFirstTerminatorForward();
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 
204 bool Localizer::runOnMachineFunction(MachineFunction &MF) {
205   // If the ISel pipeline failed, do not bother running that pass.
206   if (MF.getProperties().hasProperty(
207           MachineFunctionProperties::Property::FailedISel))
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 }
226