blob: 8c96308ac91a7602c6a553702c9821b0503bab9a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
//===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the MachineLoopInfo class that is used to identify natural
// loops and determine the loop depth of various nodes of the CFG. Note that
// natural loops may actually be several loops that share the same header node.
//
// This analysis calculates the nesting structure of loops in a function. For
// each natural loop identified, this analysis identifies natural loops
// contained entirely within the loop and the basic blocks the make up the loop.
//
// It can calculate on the fly various bits of information, for example:
//
// * whether there is a preheader for the loop
// * the number of back edges to the header
// * whether or not a particular block branches out of the loop
// * the successor blocks of the loop
// * the loop depth
// * the trip count
// * etc...
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_MACHINE_LOOP_INFO_H
#define LLVM_CODEGEN_MACHINE_LOOP_INFO_H
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/Analysis/LoopInfo.h"
namespace llvm {
// Provide overrides for Loop methods that don't make sense for machine loops.
template<> inline
PHINode *LoopBase<MachineBasicBlock>::getCanonicalInductionVariable() const {
assert(0 && "getCanonicalInductionVariable not supported for machine loops!");
return 0;
}
template<> inline Instruction*
LoopBase<MachineBasicBlock>::getCanonicalInductionVariableIncrement() const {
assert(0 &&
"getCanonicalInductionVariableIncrement not supported for machine loops!");
return 0;
}
template<>
inline bool LoopBase<MachineBasicBlock>::isLoopInvariant(Value *V) const {
assert(0 && "isLoopInvariant not supported for machine loops!");
return false;
}
template<>
inline Value *LoopBase<MachineBasicBlock>::getTripCount() const {
assert(0 && "getTripCount not supported for machine loops!");
return 0;
}
template<>
inline bool LoopBase<MachineBasicBlock>::isLCSSAForm() const {
assert(0 && "isLCSSAForm not supported for machine loops");
return false;
}
typedef LoopBase<MachineBasicBlock> MachineLoop;
class MachineLoopInfo : public MachineFunctionPass {
LoopInfoBase<MachineBasicBlock>* LI;
friend class LoopBase<MachineBasicBlock>;
LoopInfoBase<MachineBasicBlock>& getBase() { return *LI; }
public:
static char ID; // Pass identification, replacement for typeid
MachineLoopInfo() : MachineFunctionPass(&ID) {
LI = new LoopInfoBase<MachineBasicBlock>();
}
~MachineLoopInfo() { delete LI; }
/// iterator/begin/end - The interface to the top-level loops in the current
/// function.
///
typedef std::vector<MachineLoop*>::const_iterator iterator;
inline iterator begin() const { return LI->begin(); }
inline iterator end() const { return LI->end(); }
bool empty() const { return LI->empty(); }
/// getLoopFor - Return the inner most loop that BB lives in. If a basic
/// block is in no loop (for example the entry node), null is returned.
///
inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const {
return LI->getLoopFor(BB);
}
/// operator[] - same as getLoopFor...
///
inline const MachineLoop *operator[](const MachineBasicBlock *BB) const {
return LI->getLoopFor(BB);
}
/// getLoopDepth - Return the loop nesting level of the specified block...
///
inline unsigned getLoopDepth(const MachineBasicBlock *BB) const {
return LI->getLoopDepth(BB);
}
// isLoopHeader - True if the block is a loop header node
inline bool isLoopHeader(MachineBasicBlock *BB) const {
return LI->isLoopHeader(BB);
}
/// runOnFunction - Calculate the natural loop information.
///
virtual bool runOnMachineFunction(MachineFunction &F);
virtual void releaseMemory() { LI->releaseMemory(); }
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
/// removeLoop - This removes the specified top-level loop from this loop info
/// object. The loop is not deleted, as it will presumably be inserted into
/// another loop.
inline MachineLoop *removeLoop(iterator I) { return LI->removeLoop(I); }
/// changeLoopFor - Change the top-level loop that contains BB to the
/// specified loop. This should be used by transformations that restructure
/// the loop hierarchy tree.
inline void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L) {
LI->changeLoopFor(BB, L);
}
/// changeTopLevelLoop - Replace the specified loop in the top-level loops
/// list with the indicated loop.
inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) {
LI->changeTopLevelLoop(OldLoop, NewLoop);
}
/// addTopLevelLoop - This adds the specified loop to the collection of
/// top-level loops.
inline void addTopLevelLoop(MachineLoop *New) {
LI->addTopLevelLoop(New);
}
/// removeBlock - This method completely removes BB from all data structures,
/// including all of the Loop objects it is nested in and our mapping from
/// MachineBasicBlocks to loops.
void removeBlock(MachineBasicBlock *BB) {
LI->removeBlock(BB);
}
};
// Allow clients to walk the list of nested loops...
template <> struct GraphTraits<const MachineLoop*> {
typedef const MachineLoop NodeType;
typedef std::vector<MachineLoop*>::const_iterator ChildIteratorType;
static NodeType *getEntryNode(const MachineLoop *L) { return L; }
static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
static inline ChildIteratorType child_end(NodeType *N) {
return N->end();
}
};
template <> struct GraphTraits<MachineLoop*> {
typedef MachineLoop NodeType;
typedef std::vector<MachineLoop*>::const_iterator ChildIteratorType;
static NodeType *getEntryNode(MachineLoop *L) { return L; }
static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
static inline ChildIteratorType child_end(NodeType *N) {
return N->end();
}
};
} // End llvm namespace
#endif
|
