LLVM  14.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"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Support/Debug.h"
27 
28 using namespace llvm;
29 
30 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
33 
34 char MachineLoopInfo::ID = 0;
37 }
38 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
39  "Machine Natural Loop Construction", true, true)
43 
45 
46 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
47  calculate(getAnalysis<MachineDominatorTree>());
48  return false;
49 }
50 
52  releaseMemory();
53  LI.analyze(MDT.getBase());
54 }
55 
57  AU.setPreservesAll();
60 }
61 
63  MachineBasicBlock *TopMBB = getHeader();
64  MachineFunction::iterator Begin = TopMBB->getParent()->begin();
65  if (TopMBB->getIterator() != Begin) {
66  MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
67  while (contains(PriorMBB)) {
68  TopMBB = PriorMBB;
69  if (TopMBB->getIterator() == Begin)
70  break;
71  PriorMBB = &*std::prev(TopMBB->getIterator());
72  }
73  }
74  return TopMBB;
75 }
76 
78  MachineBasicBlock *BotMBB = getHeader();
79  MachineFunction::iterator End = BotMBB->getParent()->end();
80  if (BotMBB->getIterator() != std::prev(End)) {
81  MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
82  while (contains(NextMBB)) {
83  BotMBB = NextMBB;
84  if (BotMBB == &*std::next(BotMBB->getIterator()))
85  break;
86  NextMBB = &*std::next(BotMBB->getIterator());
87  }
88  }
89  return BotMBB;
90 }
91 
93  if (MachineBasicBlock *Latch = getLoopLatch()) {
94  if (isLoopExiting(Latch))
95  return Latch;
96  else
97  return getExitingBlock();
98  }
99  return nullptr;
100 }
101 
103  // Try the pre-header first.
104  if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
105  if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
106  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
107  return DL;
108 
109  // If we have no pre-header or there are no instructions with debug
110  // info in it, try the header.
111  if (MachineBasicBlock *HeadMBB = getHeader())
112  if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
113  return HeadBB->getTerminator()->getDebugLoc();
114 
115  return DebugLoc();
116 }
117 
119 MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,
120  bool FindMultiLoopPreheader) const {
122  return PB;
123 
124  if (!SpeculativePreheader)
125  return nullptr;
126 
127  MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
128  if (HB->pred_size() != 2 || HB->hasAddressTaken())
129  return nullptr;
130  // Find the predecessor of the header that is not the latch block.
131  MachineBasicBlock *Preheader = nullptr;
132  for (MachineBasicBlock *P : HB->predecessors()) {
133  if (P == LB)
134  continue;
135  // Sanity.
136  if (Preheader)
137  return nullptr;
138  Preheader = P;
139  }
140 
141  // Check if the preheader candidate is a successor of any other loop
142  // headers. We want to avoid having two loop setups in the same block.
143  if (!FindMultiLoopPreheader) {
144  for (MachineBasicBlock *S : Preheader->successors()) {
145  if (S == HB)
146  continue;
148  if (T && T->getHeader() == S)
149  return nullptr;
150  }
151  }
152  return Preheader;
153 }
154 
156  MachineFunction *MF = I.getParent()->getParent();
158  const TargetSubtargetInfo &ST = MF->getSubtarget();
159  const TargetRegisterInfo *TRI = ST.getRegisterInfo();
160  const TargetInstrInfo *TII = ST.getInstrInfo();
161 
162  // The instruction is loop invariant if all of its operands are.
163  for (const MachineOperand &MO : I.operands()) {
164  if (!MO.isReg())
165  continue;
166 
167  Register Reg = MO.getReg();
168  if (Reg == 0) continue;
169 
170  // An instruction that uses or defines a physical register can't e.g. be
171  // hoisted, so mark this as not invariant.
173  if (MO.isUse()) {
174  // If the physreg has no defs anywhere, it's just an ambient register
175  // and we can freely move its uses. Alternatively, if it's allocatable,
176  // it could get allocated to something with a def during allocation.
177  // However, if the physreg is known to always be caller saved/restored
178  // then this use is safe to hoist.
179  if (!MRI->isConstantPhysReg(Reg) &&
180  !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
181  !TII->isIgnorableUse(MO))
182  return false;
183  // Otherwise it's safe to move.
184  continue;
185  } else if (!MO.isDead()) {
186  // A def that isn't dead can't be moved.
187  return false;
188  } else if (getHeader()->isLiveIn(Reg)) {
189  // If the reg is live into the loop, we can't hoist an instruction
190  // which would clobber it.
191  return false;
192  }
193  }
194 
195  if (!MO.isUse())
196  continue;
197 
198  assert(MRI->getVRegDef(Reg) &&
199  "Machine instr not mapped for this vreg?!");
200 
201  // If the loop contains the definition of an operand, then the instruction
202  // isn't loop invariant.
203  if (contains(MRI->getVRegDef(Reg)))
204  return false;
205  }
206 
207  // If we got this far, the instruction is loop invariant!
208  return true;
209 }
210 
211 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
213  print(dbgs());
214 }
215 #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:507
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::MachineLoopInfo::calculate
void calculate(MachineDominatorTree &MDT)
Definition: MachineLoopInfo.cpp:51
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:127
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
T
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, bool FindMultiLoopPreheader=false) const
Find the block that either is the loop preheader, or could speculatively be used as the preheader.
Definition: MachineLoopInfo.cpp:119
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:825
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:233
TargetInstrInfo.h
llvm::MachineLoop::getBottomBlock
MachineBasicBlock * getBottomBlock()
Return the "bottom" block in the loop, which is the last block in the linear layout,...
Definition: MachineLoopInfo.cpp:77
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1564
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:163
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:332
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:651
llvm::MachineLoop::dump
void dump() const
Definition: MachineLoopInfo.cpp:212
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
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:150
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:41
llvm::MachineLoop::findLoopControlBlock
MachineBasicBlock * findLoopControlBlock()
Find the block that contains the loop control variable and the loop test.
Definition: MachineLoopInfo.cpp:92
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
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:35
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:823
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:398
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:560
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
PB
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
Passes.h
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:641
llvm::MachineLoopInfoID
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
Definition: MachineLoopInfo.cpp:44
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
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:215
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:167
true
machine Machine Natural Loop true
Definition: MachineLoopInfo.cpp:42
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:229
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:353
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:359
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
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
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:511
llvm::MachineLoopInfo::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineLoopInfo.cpp:56
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:102
llvm::LoopBase< MachineBasicBlock, MachineLoop >::getHeader
MachineBasicBlock * getHeader() const
Definition: LoopInfo.h:104
Construction
machine Machine Natural Loop Construction
Definition: MachineLoopInfo.cpp:42
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:366
llvm::MachineDominatorTree::getBase
MachineDomTree & getBase()
Definition: MachineDominators.h:86
llvm::MachineLoop::getTopBlock
MachineBasicBlock * getTopBlock()
Return the "top" block in the loop, which is the first block in the linear layout,...
Definition: MachineLoopInfo.cpp:62
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:46
llvm::MachineLoop::isLoopInvariant
bool isLoopInvariant(MachineInstr &I) const
Returns true if the instruction is loop invariant.
Definition: MachineLoopInfo.cpp:155
InitializePasses.h
Debug.h
machine
coro Split coroutine into a set of functions driving its state machine
Definition: CoroSplit.cpp:2353
MachineDominators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38