LLVM  14.0.0git
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 
13 #include "llvm/ADT/DenseMap.h"
14 #include "llvm/ADT/STLExtras.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;
27  "Move/duplicate certain instructions close to their use",
28  false, false)
31  "Move/duplicate certain instructions close to their use",
33 
35  : MachineFunctionPass(ID), DoNotRunPass(F) {}
36 
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 
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 (MachineOperand &MOUse :
97  // Check if the use is already local.
98  MachineBasicBlock *InsertMBB;
99  LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
100  dbgs() << "Checking use: " << MIUse
101  << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n');
102  if (isLocalUse(MOUse, MI, InsertMBB)) {
103  // Even if we're in the same block, if the block is very large we could
104  // still have many long live ranges. Try to do intra-block localization
105  // too.
106  LocalizedInstrs.insert(&MI);
107  continue;
108  }
109 
110  // If the use is a phi operand that's not unique, don't try to localize.
111  // If we do, we can cause unnecessary instruction bloat by duplicating
112  // into each predecessor block, when the existing one is sufficient and
113  // allows for easier optimization later.
114  if (isNonUniquePhiValue(MOUse))
115  continue;
116 
117  LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
118  Changed = true;
119  auto MBBAndReg = std::make_pair(InsertMBB, Reg);
120  auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
121  if (NewVRegIt == MBBWithLocalDef.end()) {
122  // Create the localized instruction.
123  MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
124  LocalizedInstrs.insert(LocalizedMI);
125  MachineInstr &UseMI = *MOUse.getParent();
126  if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
127  InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(UseMI), LocalizedMI);
128  else
129  InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
130  LocalizedMI);
131 
132  // Set a new register for the definition.
133  Register NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg));
134  MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg));
135  LocalizedMI->getOperand(0).setReg(NewReg);
136  NewVRegIt =
137  MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
138  LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
139  }
140  LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
141  << '\n');
142  // Update the user reg.
143  MOUse.setReg(NewVRegIt->second);
144  }
145  }
146  return Changed;
147 }
148 
149 bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
150  bool Changed = false;
151 
152  // For each already-localized instruction which has multiple users, then we
153  // scan the block top down from the current position until we hit one of them.
154 
155  // FIXME: Consider doing inst duplication if live ranges are very long due to
156  // many users, but this case may be better served by regalloc improvements.
157 
158  for (MachineInstr *MI : LocalizedInstrs) {
159  Register Reg = MI->getOperand(0).getReg();
160  MachineBasicBlock &MBB = *MI->getParent();
161  // All of the user MIs of this reg.
164  if (!UseMI.isPHI())
165  Users.insert(&UseMI);
166  }
167  // If all the users were PHIs then they're not going to be in our block,
168  // don't try to move this instruction.
169  if (Users.empty())
170  continue;
171 
173  ++II;
174  while (II != MBB.end() && !Users.count(&*II))
175  ++II;
176 
177  LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
178  << "\n");
179  assert(II != MBB.end() && "Didn't find the user in the MBB");
180  MI->removeFromParent();
181  MBB.insert(II, MI);
182  Changed = true;
183  }
184  return Changed;
185 }
186 
188  // If the ISel pipeline failed, do not bother running that pass.
189  if (MF.getProperties().hasProperty(
191  return false;
192 
193  // Don't run the pass if the target asked so.
194  if (DoNotRunPass(MF))
195  return false;
196 
197  LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
198 
199  init(MF);
200 
201  // Keep track of the instructions we localized. We'll do a second pass of
202  // intra-block localization to further reduce live ranges.
203  LocalizedSetVecT LocalizedInstrs;
204 
205  bool Changed = localizeInterBlock(MF, LocalizedInstrs);
206  Changed |= localizeIntraBlock(LocalizedInstrs);
207  return Changed;
208 }
use
Move duplicate certain instructions close to their use
Definition: Localizer.cpp:31
llvm::MachineFunctionProperties::hasProperty
bool hasProperty(Property P) const
Definition: MachineFunction.h:165
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm::MachineInstr::getOperandNo
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
Definition: MachineInstr.h:683
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:102
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:543
to
Should compile to
Definition: README.txt:449
llvm::Localizer::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Localizer.cpp:45
DenseMap.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:469
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::getSelectionDAGFallbackAnalysisUsage
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:802
STLExtras.h
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
TargetLowering.h
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:820
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:636
llvm::MachineRegisterInfo::setRegClassOrRegBank
void setRegClassOrRegBank(Register Reg, const RegClassOrRegBank &RCOrRB)
Definition: MachineRegisterInfo.h:678
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineFunction::getProperties
const MachineFunctionProperties & getProperties() const
Get the function properties.
Definition: MachineFunction.h:717
false
Definition: StackSlotColoring.cpp:142
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:238
llvm::Localizer::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: Localizer.cpp:187
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::Localizer::Localizer
Localizer()
Definition: Localizer.cpp:37
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:626
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2387
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:358
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::MachineBasicBlock::SkipPHIsAndLabels
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
Definition: MachineBasicBlock.cpp:210
llvm::DenseMap
Definition: DenseMap.h:714
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
Localizer.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:541
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
DEBUG_TYPE
#define DEBUG_TYPE
Definition: Localizer.cpp:21
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1255
llvm::MachineRegisterInfo::createGenericVirtualRegister
Register createGenericVirtualRegister(LLT Ty, StringRef Name="")
Create and return a new generic virtual register with low-level type Ty.
Definition: MachineRegisterInfo.cpp:188
llvm::MachineRegisterInfo::getRegClassOrRegBank
const RegClassOrRegBank & getRegClassOrRegBank(Register Reg) const
Return the register bank or register class of Reg.
Definition: MachineRegisterInfo.h:668
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:552
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunctionProperties::Property::FailedISel
@ FailedISel
std
Definition: BitVector.h:838
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:592
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1312
llvm::Localizer::ID
static char ID
Definition: Localizer.h:42
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE, "Move/duplicate certain instructions close to their use", false, false) INITIALIZE_PASS_END(Localizer
llvm::TargetSubtargetInfo::getTargetLowering
virtual const TargetLowering * getTargetLowering() const
Definition: TargetSubtargetInfo.h:96
llvm::MachineRegisterInfo::hasOneUse
bool hasOneUse(Register RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
Definition: MachineRegisterInfo.h:510
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::MachineRegisterInfo::getType
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
Definition: MachineRegisterInfo.h:732
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:55
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
TargetTransformInfo.h
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:110
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::Localizer
This pass implements the localization mechanism described at the top of this file.
Definition: Localizer.h:40
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37