LLVM  6.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/Support/Debug.h"
23 using namespace llvm;
24 
25 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
28 
29 char MachineLoopInfo::ID = 0;
30 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
31  "Machine Natural Loop Construction", true, true)
34  "Machine Natural Loop Construction", true, true)
35 
36 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
37 
38 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
39  releaseMemory();
40  LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
41  return false;
42 }
43 
45  AU.setPreservesAll();
48 }
49 
51  MachineBasicBlock *TopMBB = getHeader();
52  MachineFunction::iterator Begin = TopMBB->getParent()->begin();
53  if (TopMBB->getIterator() != Begin) {
54  MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
55  while (contains(PriorMBB)) {
56  TopMBB = PriorMBB;
57  if (TopMBB->getIterator() == Begin)
58  break;
59  PriorMBB = &*std::prev(TopMBB->getIterator());
60  }
61  }
62  return TopMBB;
63 }
64 
66  MachineBasicBlock *BotMBB = getHeader();
68  if (BotMBB->getIterator() != std::prev(End)) {
69  MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
70  while (contains(NextMBB)) {
71  BotMBB = NextMBB;
72  if (BotMBB == &*std::next(BotMBB->getIterator()))
73  break;
74  NextMBB = &*std::next(BotMBB->getIterator());
75  }
76  }
77  return BotMBB;
78 }
79 
81  if (MachineBasicBlock *Latch = getLoopLatch()) {
82  if (isLoopExiting(Latch))
83  return Latch;
84  else
85  return getExitingBlock();
86  }
87  return nullptr;
88 }
89 
91  // Try the pre-header first.
92  if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
93  if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
94  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
95  return DL;
96 
97  // If we have no pre-header or there are no instructions with debug
98  // info in it, try the header.
99  if (MachineBasicBlock *HeadMBB = getHeader())
100  if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
101  return HeadBB->getTerminator()->getDebugLoc();
102 
103  return DebugLoc();
104 }
105 
108  bool SpeculativePreheader) const {
109  if (MachineBasicBlock *PB = L->getLoopPreheader())
110  return PB;
111 
112  if (!SpeculativePreheader)
113  return nullptr;
114 
115  MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
116  if (HB->pred_size() != 2 || HB->hasAddressTaken())
117  return nullptr;
118  // Find the predecessor of the header that is not the latch block.
119  MachineBasicBlock *Preheader = nullptr;
120  for (MachineBasicBlock *P : HB->predecessors()) {
121  if (P == LB)
122  continue;
123  // Sanity.
124  if (Preheader)
125  return nullptr;
126  Preheader = P;
127  }
128 
129  // Check if the preheader candidate is a successor of any other loop
130  // headers. We want to avoid having two loop setups in the same block.
131  for (MachineBasicBlock *S : Preheader->successors()) {
132  if (S == HB)
133  continue;
134  MachineLoop *T = getLoopFor(S);
135  if (T && T->getHeader() == S)
136  return nullptr;
137  }
138  return Preheader;
139 }
140 
141 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
143  print(dbgs());
144 }
145 #endif
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:157
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
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:106
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.
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:59
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Represent the analysis usage information of a pass.
static const unsigned End
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:132
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:420
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:123
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