LLVM  13.0.0git
MachineLoopInfo.cpp
Go to the documentation of this file.
1 //===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
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 //
9 // This file defines the MachineLoopInfo class that is used to identify natural
10 // loops and determine the loop depth of various nodes of the CFG. Note that
11 // the loops identified may actually be several natural loops that share the
12 // same header node... not just a single natural loop.
13 //
14 //===----------------------------------------------------------------------===//
15 
20 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Support/Debug.h"
26 
27 using namespace llvm;
28 
29 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
32 
33 char MachineLoopInfo::ID = 0;
36 }
37 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
38  "Machine Natural Loop Construction", true, true)
42 
44 
45 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
46  calculate(getAnalysis<MachineDominatorTree>());
47  return false;
48 }
49 
51  releaseMemory();
52  LI.analyze(MDT.getBase());
53 }
54 
56  AU.setPreservesAll();
59 }
60 
62  MachineBasicBlock *TopMBB = getHeader();
63  MachineFunction::iterator Begin = TopMBB->getParent()->begin();
64  if (TopMBB->getIterator() != Begin) {
65  MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
66  while (contains(PriorMBB)) {
67  TopMBB = PriorMBB;
68  if (TopMBB->getIterator() == Begin)
69  break;
70  PriorMBB = &*std::prev(TopMBB->getIterator());
71  }
72  }
73  return TopMBB;
74 }
75 
77  MachineBasicBlock *BotMBB = getHeader();
78  MachineFunction::iterator End = BotMBB->getParent()->end();
79  if (BotMBB->getIterator() != std::prev(End)) {
80  MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
81  while (contains(NextMBB)) {
82  BotMBB = NextMBB;
83  if (BotMBB == &*std::next(BotMBB->getIterator()))
84  break;
85  NextMBB = &*std::next(BotMBB->getIterator());
86  }
87  }
88  return BotMBB;
89 }
90 
92  if (MachineBasicBlock *Latch = getLoopLatch()) {
93  if (isLoopExiting(Latch))
94  return Latch;
95  else
96  return getExitingBlock();
97  }
98  return nullptr;
99 }
100 
102  // Try the pre-header first.
103  if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
104  if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
105  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
106  return DL;
107 
108  // If we have no pre-header or there are no instructions with debug
109  // info in it, try the header.
110  if (MachineBasicBlock *HeadMBB = getHeader())
111  if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
112  return HeadBB->getTerminator()->getDebugLoc();
113 
114  return DebugLoc();
115 }
116 
119  bool SpeculativePreheader) const {
120  if (MachineBasicBlock *PB = L->getLoopPreheader())
121  return PB;
122 
123  if (!SpeculativePreheader)
124  return nullptr;
125 
126  MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
127  if (HB->pred_size() != 2 || HB->hasAddressTaken())
128  return nullptr;
129  // Find the predecessor of the header that is not the latch block.
130  MachineBasicBlock *Preheader = nullptr;
131  for (MachineBasicBlock *P : HB->predecessors()) {
132  if (P == LB)
133  continue;
134  // Sanity.
135  if (Preheader)
136  return nullptr;
137  Preheader = P;
138  }
139 
140  // Check if the preheader candidate is a successor of any other loop
141  // headers. We want to avoid having two loop setups in the same block.
142  for (MachineBasicBlock *S : Preheader->successors()) {
143  if (S == HB)
144  continue;
146  if (T && T->getHeader() == S)
147  return nullptr;
148  }
149  return Preheader;
150 }
151 
153  MachineFunction *MF = I.getParent()->getParent();
156 
157  // The instruction is loop invariant if all of its operands are.
158  for (const MachineOperand &MO : I.operands()) {
159  if (!MO.isReg())
160  continue;
161 
162  Register Reg = MO.getReg();
163  if (Reg == 0) continue;
164 
165  // An instruction that uses or defines a physical register can't e.g. be
166  // hoisted, so mark this as not invariant.
168  if (MO.isUse()) {
169  // If the physreg has no defs anywhere, it's just an ambient register
170  // and we can freely move its uses. Alternatively, if it's allocatable,
171  // it could get allocated to something with a def during allocation.
172  // However, if the physreg is known to always be caller saved/restored
173  // then this use is safe to hoist.
174  if (!MRI->isConstantPhysReg(Reg) &&
175  !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())))
176  return false;
177  // Otherwise it's safe to move.
178  continue;
179  } else if (!MO.isDead()) {
180  // A def that isn't dead can't be moved.
181  return false;
182  } else if (getHeader()->isLiveIn(Reg)) {
183  // If the reg is live into the loop, we can't hoist an instruction
184  // which would clobber it.
185  return false;
186  }
187  }
188 
189  if (!MO.isUse())
190  continue;
191 
192  assert(MRI->getVRegDef(Reg) &&
193  "Machine instr not mapped for this vreg?!");
194 
195  // If the loop contains the definition of an operand, then the instruction
196  // isn't loop invariant.
197  if (contains(MRI->getVRegDef(Reg)))
198  return false;
199  }
200 
201  // If we got this far, the instruction is loop invariant!
202  return true;
203 }
204 
205 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
207  print(dbgs());
208 }
209 #endif
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:499
llvm
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::MachineLoopInfo::calculate
void calculate(MachineDominatorTree &MDT)
Definition: MachineLoopInfo.cpp:50
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:124
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops", "Machine Natural Loop Construction", true, true) INITIALIZE_PASS_END(MachineLoopInfo
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LoopBase< MachineBasicBlock, MachineLoop >::contains
bool contains(const MachineLoop *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::MachineLoopInfo::findLoopPreheader
MachineBasicBlock * findLoopPreheader(MachineLoop *L, bool SpeculativePreheader=false) const
Find the block that either is the loop preheader, or could speculatively be used as the preheader.
Definition: MachineLoopInfo.cpp:118
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:739
LoopInfoImpl.h
llvm::LoopBase< MachineBasicBlock, MachineLoop >
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:124
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::MachineLoop::getBottomBlock
MachineBasicBlock * getBottomBlock()
Return the "bottom" block in the loop, which is the last block in the linear layout,...
Definition: MachineLoopInfo.cpp:76
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
MachineRegisterInfo.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:328
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:565
llvm::MachineLoop::dump
void dump() const
Definition: MachineLoopInfo.cpp:206
llvm::MachineLoopInfo::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: MachineLoopInfo.h:147
MachineLoopInfo.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
loops
machine loops
Definition: MachineLoopInfo.cpp:40
llvm::MachineLoop::findLoopControlBlock
MachineBasicBlock * findLoopControlBlock()
Find the block that contains the loop control variable and the loop test.
Definition: MachineLoopInfo.cpp:91
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineLoopInfo::ID
static char ID
Definition: MachineLoopInfo.h:96
llvm::MachineLoopInfo::MachineLoopInfo
MachineLoopInfo()
Definition: MachineLoopInfo.cpp:34
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:737
llvm::LoopBase< MachineBasicBlock, MachineLoop >::getExitingBlock
MachineBasicBlock * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:400
llvm::TargetRegisterInfo::isCallerPreservedPhysReg
virtual bool isCallerPreservedPhysReg(MCRegister PhysReg, const MachineFunction &MF) const
Physical registers that may be modified within a function but are guaranteed to be restored before an...
Definition: TargetRegisterInfo.h:544
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
Passes.h
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:555
llvm::MachineLoopInfoID
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
Definition: MachineLoopInfo.cpp:43
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
llvm::MachineDominatorTree::getBase
DomTreeT & getBase()
Definition: MachineDominators.h:87
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::initializeMachineLoopInfoPass
void initializeMachineLoopInfoPass(PassRegistry &)
llvm::MachineBasicBlock::hasAddressTaken
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
Definition: MachineBasicBlock.h:211
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LoopBase< MachineBasicBlock, MachineLoop >::getLoopPreheader
MachineBasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
true
machine Machine Natural Loop true
Definition: MachineLoopInfo.cpp:41
llvm::LoopBase< MachineBasicBlock, MachineLoop >::getLoopLatch
MachineBasicBlock * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:349
llvm::MachineFunction
Definition: MachineFunction.h:227
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:513
llvm::MachineLoopInfo::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineLoopInfo.cpp:55
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::LoopInfoBase
This class builds and contains all of the top-level loop structures in the specified function.
Definition: LoopInfo.h:66
llvm::MachineLoop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: MachineLoopInfo.cpp:101
llvm::LoopBase< MachineBasicBlock, MachineLoop >::getHeader
MachineBasicBlock * getHeader() const
Definition: LoopInfo.h:104
Construction
machine Machine Natural Loop Construction
Definition: MachineLoopInfo.cpp:41
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:365
llvm::MachineLoop::getTopBlock
MachineBasicBlock * getTopBlock()
Return the "top" block in the loop, which is the first block in the linear layout,...
Definition: MachineLoopInfo.cpp:61
llvm::LoopBase< MachineBasicBlock, MachineLoop >::isLoopExiting
bool isLoopExiting(const MachineBasicBlock *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Definition: LoopInfo.h:225
llvm::LoopBase< MachineBasicBlock, MachineLoop >::print
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:384
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::MachineLoop::isLoopInvariant
bool isLoopInvariant(MachineInstr &I) const
Returns true if the instruction is loop invariant.
Definition: MachineLoopInfo.cpp:152
InitializePasses.h
Debug.h
machine
coro Split coroutine into a set of functions driving its state machine
Definition: CoroSplit.cpp:2246
MachineDominators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38