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)
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 
37 Localizer::Localizer()
38     : Localizer([](const MachineFunction &) { return false; }) {}
39 
40 void Localizer::init(MachineFunction &MF) {
41   MRI = &MF.getRegInfo();
42   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
43 }
44 
45 void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {
46   AU.addRequired<TargetTransformInfoWrapperPass>();
47   getSelectionDAGFallbackAnalysisUsage(AU);
48   MachineFunctionPass::getAnalysisUsage(AU);
49 }
50 
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 
60 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 
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 (MachineInstr &MI : llvm::reverse(MBB)) {
86     if (!TL.shouldLocalize(MI, TTI))
87       continue;
88     LLVM_DEBUG(dbgs() << "Should localize: " << MI);
89     assert(MI.getDesc().getNumDefs() == 1 &&
90            "More than one definition not supported yet");
91     Register Reg = MI.getOperand(0).getReg();
92     // Check if all the users of MI are local.
93     // We are going to invalidation the list of use operands, so we
94     // can't use range iterator.
95     for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end();
96          MOIt != MOItEnd;) {
97       MachineOperand &MOUse = *MOIt++;
98       // Check if the use is already local.
99       MachineBasicBlock *InsertMBB;
100       LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
101                  dbgs() << "Checking use: " << MIUse
102                         << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n');
103       if (isLocalUse(MOUse, MI, InsertMBB)) {
104         // Even if we're in the same block, if the block is very large we could
105         // still have many long live ranges. Try to do intra-block localization
106         // too.
107         LocalizedInstrs.insert(&MI);
108         continue;
109       }
110 
111       // If the use is a phi operand that's not unique, don't try to localize.
112       // If we do, we can cause unnecessary instruction bloat by duplicating
113       // into each predecessor block, when the existing one is sufficient and
114       // allows for easier optimization later.
115       if (isNonUniquePhiValue(MOUse))
116         continue;
117 
118       LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
119       Changed = true;
120       auto MBBAndReg = std::make_pair(InsertMBB, Reg);
121       auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
122       if (NewVRegIt == MBBWithLocalDef.end()) {
123         // Create the localized instruction.
124         MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
125         LocalizedInstrs.insert(LocalizedMI);
126         MachineInstr &UseMI = *MOUse.getParent();
127         if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
128           InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(UseMI), LocalizedMI);
129         else
130           InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
131                             LocalizedMI);
132 
133         // Set a new register for the definition.
134         Register NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg));
135         MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg));
136         LocalizedMI->getOperand(0).setReg(NewReg);
137         NewVRegIt =
138             MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
139         LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
140       }
141       LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
142                         << '\n');
143       // Update the user reg.
144       MOUse.setReg(NewVRegIt->second);
145     }
146   }
147   return Changed;
148 }
149 
150 bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
151   bool Changed = false;
152 
153   // For each already-localized instruction which has multiple users, then we
154   // scan the block top down from the current position until we hit one of them.
155 
156   // FIXME: Consider doing inst duplication if live ranges are very long due to
157   // many users, but this case may be better served by regalloc improvements.
158 
159   for (MachineInstr *MI : LocalizedInstrs) {
160     Register Reg = MI->getOperand(0).getReg();
161     MachineBasicBlock &MBB = *MI->getParent();
162     // All of the user MIs of this reg.
163     SmallPtrSet<MachineInstr *, 32> Users;
164     for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
165       if (!UseMI.isPHI())
166         Users.insert(&UseMI);
167     }
168     // If all the users were PHIs then they're not going to be in our block,
169     // don't try to move this instruction.
170     if (Users.empty())
171       continue;
172 
173     MachineBasicBlock::iterator II(MI);
174     ++II;
175     while (II != MBB.end() && !Users.count(&*II))
176       ++II;
177 
178     LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
179                       << "\n");
180     assert(II != MBB.end() && "Didn't find the user in the MBB");
181     MI->removeFromParent();
182     MBB.insert(II, MI);
183     Changed = true;
184   }
185   return Changed;
186 }
187 
188 bool Localizer::runOnMachineFunction(MachineFunction &MF) {
189   // If the ISel pipeline failed, do not bother running that pass.
190   if (MF.getProperties().hasProperty(
191           MachineFunctionProperties::Property::FailedISel))
192     return false;
193 
194   // Don't run the pass if the target asked so.
195   if (DoNotRunPass(MF))
196     return false;
197 
198   LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
199 
200   init(MF);
201 
202   // Keep track of the instructions we localized. We'll do a second pass of
203   // intra-block localization to further reduce live ranges.
204   LocalizedSetVecT LocalizedInstrs;
205 
206   bool Changed = localizeInterBlock(MF, LocalizedInstrs);
207   Changed |= localizeIntraBlock(LocalizedInstrs);
208   return Changed;
209 }
210