LLVM  10.0.0svn
Localizer.cpp
Go to the documentation of this file.
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 
14 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/Support/Debug.h"
17 
18 #define DEBUG_TYPE "localizer"
19 
20 using namespace llvm;
21 
22 char Localizer::ID = 0;
24  "Move/duplicate certain instructions close to their use",
25  false, false)
28  "Move/duplicate certain instructions close to their use",
29  false, false)
30 
31 Localizer::Localizer() : MachineFunctionPass(ID) { }
32 
33 void Localizer::init(MachineFunction &MF) {
34  MRI = &MF.getRegInfo();
35  TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
36 }
37 
38 bool Localizer::shouldLocalize(const MachineInstr &MI) {
39  // Assuming a spill and reload of a value has a cost of 1 instruction each,
40  // this helper function computes the maximum number of uses we should consider
41  // for remat. E.g. on arm64 global addresses take 2 insts to materialize. We
42  // break even in terms of code size when the original MI has 2 users vs
43  // choosing to potentially spill. Any more than 2 users we we have a net code
44  // size increase. This doesn't take into account register pressure though.
45  auto maxUses = [](unsigned RematCost) {
46  // A cost of 1 means remats are basically free.
47  if (RematCost == 1)
48  return UINT_MAX;
49  if (RematCost == 2)
50  return 2U;
51 
52  // Remat is too expensive, only sink if there's one user.
53  if (RematCost > 2)
54  return 1U;
55  llvm_unreachable("Unexpected remat cost");
56  };
57 
58  // Helper to walk through uses and terminate if we've reached a limit. Saves
59  // us spending time traversing uses if all we want to know is if it's >= min.
60  auto isUsesAtMost = [&](unsigned Reg, unsigned MaxUses) {
61  unsigned NumUses = 0;
62  auto UI = MRI->use_instr_nodbg_begin(Reg), UE = MRI->use_instr_nodbg_end();
63  for (; UI != UE && NumUses < MaxUses; ++UI) {
64  NumUses++;
65  }
66  // If we haven't reached the end yet then there are more than MaxUses users.
67  return UI == UE;
68  };
69 
70  switch (MI.getOpcode()) {
71  default:
72  return false;
73  // Constants-like instructions should be close to their users.
74  // We don't want long live-ranges for them.
75  case TargetOpcode::G_CONSTANT:
76  case TargetOpcode::G_FCONSTANT:
77  case TargetOpcode::G_FRAME_INDEX:
78  case TargetOpcode::G_INTTOPTR:
79  return true;
80  case TargetOpcode::G_GLOBAL_VALUE: {
81  unsigned RematCost = TTI->getGISelRematGlobalCost();
82  Register Reg = MI.getOperand(0).getReg();
83  unsigned MaxUses = maxUses(RematCost);
84  if (MaxUses == UINT_MAX)
85  return true; // Remats are "free" so always localize.
86  bool B = isUsesAtMost(Reg, MaxUses);
87  return B;
88  }
89  }
90 }
91 
96 }
97 
98 bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
99  MachineBasicBlock *&InsertMBB) {
100  MachineInstr &MIUse = *MOUse.getParent();
101  InsertMBB = MIUse.getParent();
102  if (MIUse.isPHI())
103  InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB();
104  return InsertMBB == Def.getParent();
105 }
106 
107 bool Localizer::localizeInterBlock(MachineFunction &MF,
108  LocalizedSetVecT &LocalizedInstrs) {
109  bool Changed = false;
110  DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
111 
112  // Since the IRTranslator only emits constants into the entry block, and the
113  // rest of the GISel pipeline generally emits constants close to their users,
114  // we only localize instructions in the entry block here. This might change if
115  // we start doing CSE across blocks.
116  auto &MBB = MF.front();
117  for (auto RI = MBB.rbegin(), RE = MBB.rend(); RI != RE; ++RI) {
118  MachineInstr &MI = *RI;
119  if (!shouldLocalize(MI))
120  continue;
121  LLVM_DEBUG(dbgs() << "Should localize: " << MI);
122  assert(MI.getDesc().getNumDefs() == 1 &&
123  "More than one definition not supported yet");
124  Register Reg = MI.getOperand(0).getReg();
125  // Check if all the users of MI are local.
126  // We are going to invalidation the list of use operands, so we
127  // can't use range iterator.
128  for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end();
129  MOIt != MOItEnd;) {
130  MachineOperand &MOUse = *MOIt++;
131  // Check if the use is already local.
132  MachineBasicBlock *InsertMBB;
133  LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
134  dbgs() << "Checking use: " << MIUse
135  << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n');
136  if (isLocalUse(MOUse, MI, InsertMBB))
137  continue;
138  LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
139  Changed = true;
140  auto MBBAndReg = std::make_pair(InsertMBB, Reg);
141  auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
142  if (NewVRegIt == MBBWithLocalDef.end()) {
143  // Create the localized instruction.
144  MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
145  LocalizedInstrs.insert(LocalizedMI);
146  MachineInstr &UseMI = *MOUse.getParent();
147  if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
148  InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(UseMI), LocalizedMI);
149  else
150  InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
151  LocalizedMI);
152 
153  // Set a new register for the definition.
154  Register NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg));
155  MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg));
156  LocalizedMI->getOperand(0).setReg(NewReg);
157  NewVRegIt =
158  MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
159  LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
160  }
161  LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
162  << '\n');
163  // Update the user reg.
164  MOUse.setReg(NewVRegIt->second);
165  }
166  }
167  return Changed;
168 }
169 
170 bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
171  bool Changed = false;
172 
173  // For each already-localized instruction which has multiple users, then we
174  // scan the block top down from the current position until we hit one of them.
175 
176  // FIXME: Consider doing inst duplication if live ranges are very long due to
177  // many users, but this case may be better served by regalloc improvements.
178 
179  for (MachineInstr *MI : LocalizedInstrs) {
180  Register Reg = MI->getOperand(0).getReg();
181  MachineBasicBlock &MBB = *MI->getParent();
182  // All of the user MIs of this reg.
184  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
185  if (!UseMI.isPHI())
186  Users.insert(&UseMI);
187  }
188  // If all the users were PHIs then they're not going to be in our block,
189  // don't try to move this instruction.
190  if (Users.empty())
191  continue;
192 
194  ++II;
195  while (II != MBB.end() && !Users.count(&*II))
196  ++II;
197 
198  LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
199  << "\n");
200  assert(II != MBB.end() && "Didn't find the user in the MBB");
201  MI->removeFromParent();
202  MBB.insert(II, MI);
203  Changed = true;
204  }
205  return Changed;
206 }
207 
209  // If the ISel pipeline failed, do not bother running that pass.
210  if (MF.getProperties().hasProperty(
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  return Changed |= localizeIntraBlock(LocalizedInstrs);
224 }
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static char ID
Definition: Localizer.h:42
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:412
const MachineFunctionProperties & getProperties() const
Get the function properties.
This pass implements the localization mechanism described at the top of this file.
Definition: Localizer.h:40
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
Definition: MachineInstr.h:527
unsigned Reg
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
iv Induction Variable Users
Definition: IVUsers.cpp:51
bool isPHI() const
INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE, "Move/duplicate certain instructions close to their use", false, false) INITIALIZE_PASS_END(Localizer
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
static use_iterator use_end()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: Localizer.cpp:208
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:408
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
const RegClassOrRegBank & getRegClassOrRegBank(unsigned Reg) const
Return the register bank or register class of Reg.
void setReg(Register Reg)
Change the register this operand corresponds to.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Wrapper pass for TargetTransformInfo.
Move duplicate certain instructions close to their use
Definition: Localizer.cpp:27
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineInstrBuilder & UseMI
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Localizer.cpp:92
Represent the analysis usage information of a pass.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
const MachineBasicBlock & front() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
#define DEBUG_TYPE
Definition: Localizer.cpp:18
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
MachineOperand class - Representation of each machine instruction operand.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:240
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
Representation of each machine instruction.
Definition: MachineInstr.h:64
unsigned getGISelRematGlobalCost() const
bool hasOneUse(unsigned RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
use_iterator use_begin(unsigned RegNo) const
MachineInstr * removeFromParent()
Unlink &#39;this&#39; from the containing basic block, and return it without deleting it. ...
static use_instr_nodbg_iterator use_instr_nodbg_end()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasProperty(Property P) const
use_instr_nodbg_iterator use_instr_nodbg_begin(unsigned RegNo) const
IRTranslator LLVM IR MI
inst_range instructions(Function *F)
Definition: InstIterator.h:133
This pass exposes codegen information to IR-level passes.
Register createGenericVirtualRegister(LLT Ty, StringRef Name="")
Create and return a new generic virtual register with low-level type Ty.
Register getReg() const
getReg - Returns the register number.
void setRegClassOrRegBank(unsigned Reg, const RegClassOrRegBank &RCOrRB)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const
Wrapper class representing virtual and physical registers.
Definition: Register.h:19