LLVM  8.0.0svn
MachineLoopInfo.cpp
Go to the documentation of this file.
1 //===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the MachineLoopInfo class that is used to identify natural
11 // loops and determine the loop depth of various nodes of the CFG. Note that
12 // the loops identified may actually be several natural loops that share the
13 // same header node... not just a single natural loop.
14 //
15 //===----------------------------------------------------------------------===//
16 
20 #include "llvm/CodeGen/Passes.h"
21 #include "llvm/Config/llvm-config.h"
22 #include "llvm/Support/Debug.h"
24 using namespace llvm;
25 
26 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
29 
30 char MachineLoopInfo::ID = 0;
31 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
32  "Machine Natural Loop Construction", true, true)
35  "Machine Natural Loop Construction", true, true)
36 
37 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
38 
39 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
40  releaseMemory();
41  LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
42  return false;
43 }
44 
46  AU.setPreservesAll();
49 }
50 
52  MachineBasicBlock *TopMBB = getHeader();
53  MachineFunction::iterator Begin = TopMBB->getParent()->begin();
54  if (TopMBB->getIterator() != Begin) {
55  MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
56  while (contains(PriorMBB)) {
57  TopMBB = PriorMBB;
58  if (TopMBB->getIterator() == Begin)
59  break;
60  PriorMBB = &*std::prev(TopMBB->getIterator());
61  }
62  }
63  return TopMBB;
64 }
65 
67  MachineBasicBlock *BotMBB = getHeader();
68  MachineFunction::iterator End = BotMBB->getParent()->end();
69  if (BotMBB->getIterator() != std::prev(End)) {
70  MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
71  while (contains(NextMBB)) {
72  BotMBB = NextMBB;
73  if (BotMBB == &*std::next(BotMBB->getIterator()))
74  break;
75  NextMBB = &*std::next(BotMBB->getIterator());
76  }
77  }
78  return BotMBB;
79 }
80 
82  if (MachineBasicBlock *Latch = getLoopLatch()) {
83  if (isLoopExiting(Latch))
84  return Latch;
85  else
86  return getExitingBlock();
87  }
88  return nullptr;
89 }
90 
92  // Try the pre-header first.
93  if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
94  if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
95  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
96  return DL;
97 
98  // If we have no pre-header or there are no instructions with debug
99  // info in it, try the header.
100  if (MachineBasicBlock *HeadMBB = getHeader())
101  if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
102  return HeadBB->getTerminator()->getDebugLoc();
103 
104  return DebugLoc();
105 }
106 
109  bool SpeculativePreheader) const {
110  if (MachineBasicBlock *PB = L->getLoopPreheader())
111  return PB;
112 
113  if (!SpeculativePreheader)
114  return nullptr;
115 
116  MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
117  if (HB->pred_size() != 2 || HB->hasAddressTaken())
118  return nullptr;
119  // Find the predecessor of the header that is not the latch block.
120  MachineBasicBlock *Preheader = nullptr;
121  for (MachineBasicBlock *P : HB->predecessors()) {
122  if (P == LB)
123  continue;
124  // Sanity.
125  if (Preheader)
126  return nullptr;
127  Preheader = P;
128  }
129 
130  // Check if the preheader candidate is a successor of any other loop
131  // headers. We want to avoid having two loop setups in the same block.
132  for (MachineBasicBlock *S : Preheader->successors()) {
133  if (S == HB)
134  continue;
135  MachineLoop *T = getLoopFor(S);
136  if (T && T->getHeader() == S)
137  return nullptr;
138  }
139  return Preheader;
140 }
141 
142 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
144  print(dbgs());
145 }
146 #endif
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:174
A debug info location.
Definition: DebugLoc.h:34
machine Machine Natural Loop true
return AArch64::GPR64RegClass contains(Reg)
iterator_range< succ_iterator > successors()
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
MachineBasicBlock * getTopBlock()
Return the "top" block in the loop, which is the first block in the linear layout, ignoring any parts of the loop not contiguous with the part that contains the header.
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
MachineBasicBlock * getBottomBlock()
Return the "bottom" block in the loop, which is the last block in the linear layout, ignoring any parts of the loop not contiguous with the part that contains the header.
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
BlockT * getHeader() const
Definition: LoopInfo.h:100
MachineBasicBlock * findLoopControlBlock()
Find the block that contains the loop control variable and the loop test.
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:363
#define P(N)
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Represent the analysis usage information of a pass.
self_iterator getIterator()
Definition: ilist_node.h:82
iterator_range< pred_iterator > predecessors()
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Iterator for intrusive lists based on ilist_node.
machine loops
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void setPreservesAll()
Set by analyses that do not transform their input at all.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops", "Machine Natural Loop Construction", true, true) INITIALIZE_PASS_END(MachineLoopInfo
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:124
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...
machine Machine Natural Loop Construction
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
This class builds and contains all of the top-level loop structures in the specified function...
Definition: LoopInfo.h:62