LLVM  16.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 
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Pass.h"
25 #include "llvm/PassRegistry.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 
118 MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,
119  bool FindMultiLoopPreheader) const {
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  if (!FindMultiLoopPreheader) {
143  for (MachineBasicBlock *S : Preheader->successors()) {
144  if (S == HB)
145  continue;
147  if (T && T->getHeader() == S)
148  return nullptr;
149  }
150  }
151  return Preheader;
152 }
153 
155  MachineFunction *MF = I.getParent()->getParent();
157  const TargetSubtargetInfo &ST = MF->getSubtarget();
158  const TargetRegisterInfo *TRI = ST.getRegisterInfo();
159  const TargetInstrInfo *TII = ST.getInstrInfo();
160 
161  // The instruction is loop invariant if all of its operands are.
162  for (const MachineOperand &MO : I.operands()) {
163  if (!MO.isReg())
164  continue;
165 
166  Register Reg = MO.getReg();
167  if (Reg == 0) continue;
168 
169  // An instruction that uses or defines a physical register can't e.g. be
170  // hoisted, so mark this as not invariant.
172  if (MO.isUse()) {
173  // If the physreg has no defs anywhere, it's just an ambient register
174  // and we can freely move its uses. Alternatively, if it's allocatable,
175  // it could get allocated to something with a def during allocation.
176  // However, if the physreg is known to always be caller saved/restored
177  // then this use is safe to hoist.
178  if (!MRI->isConstantPhysReg(Reg) &&
179  !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
180  !TII->isIgnorableUse(MO))
181  return false;
182  // Otherwise it's safe to move.
183  continue;
184  } else if (!MO.isDead()) {
185  // A def that isn't dead can't be moved.
186  return false;
187  } else if (getHeader()->isLiveIn(Reg)) {
188  // If the reg is live into the loop, we can't hoist an instruction
189  // which would clobber it.
190  return false;
191  }
192  }
193 
194  if (!MO.isUse())
195  continue;
196 
197  assert(MRI->getVRegDef(Reg) &&
198  "Machine instr not mapped for this vreg?!");
199 
200  // If the loop contains the definition of an operand, then the instruction
201  // isn't loop invariant.
202  if (contains(MRI->getVRegDef(Reg)))
203  return false;
204  }
205 
206  // If we got this far, the instruction is loop invariant!
207  return true;
208 }
209 
210 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
212  print(dbgs());
213 }
214 #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:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:126
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:50
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
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
Pass.h
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:139
llvm::MachineLoopInfo::findLoopPreheader
MachineBasicBlock * findLoopPreheader(MachineLoop *L, bool SpeculativePreheader=false, bool FindMultiLoopPreheader=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:856
LoopInfoImpl.h
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::LoopBase< MachineBasicBlock, MachineLoop >
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
TargetInstrInfo.h
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
PassRegistry.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
MachineRegisterInfo.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:365
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::MachineLoop::dump
void dump() const
Definition: MachineLoopInfo.cpp:211
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
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:149
MachineLoopInfo.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineLoopInfo::ID
static char ID
Definition: MachineLoopInfo.h:95
llvm::MachineLoopInfo::MachineLoopInfo
MachineLoopInfo()
Definition: MachineLoopInfo.cpp:34
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:854
llvm::LoopBase< MachineBasicBlock, MachineLoop >::getExitingBlock
MachineBasicBlock * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
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:396
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:566
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
PB
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::MachineLoopInfoID
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
Definition: MachineLoopInfo.cpp:43
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::initializeMachineLoopInfoPass
void initializeMachineLoopInfoPass(PassRegistry &)
llvm::MachineBasicBlock::hasAddressTaken
bool hasAddressTaken() const
Test whether this block is used as as something other than the target of a terminator,...
Definition: MachineBasicBlock.h:227
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LoopBase< MachineBasicBlock, MachineLoop >::getLoopPreheader
MachineBasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
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:232
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:261
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:386
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
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
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
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:515
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:67
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:105
Construction
machine Machine Natural Loop Construction
Definition: MachineLoopInfo.cpp:41
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:370
llvm::MachineDominatorTree::getBase
MachineDomTree & getBase()
Definition: MachineDominators.h:91
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:242
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:394
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
llvm::MachineLoop::isLoopInvariant
bool isLoopInvariant(MachineInstr &I) const
Returns true if the instruction is loop invariant.
Definition: MachineLoopInfo.cpp:154
InitializePasses.h
MachineDominators.h