/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Analysis/LoopInfoImpl.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===// |
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 is the generic implementation of LoopInfo used for both Loops and |
11 | | // MachineLoops. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H |
16 | | #define LLVM_ANALYSIS_LOOPINFOIMPL_H |
17 | | |
18 | | #include "llvm/ADT/DepthFirstIterator.h" |
19 | | #include "llvm/ADT/PostOrderIterator.h" |
20 | | #include "llvm/ADT/STLExtras.h" |
21 | | #include "llvm/ADT/SetVector.h" |
22 | | #include "llvm/Analysis/LoopInfo.h" |
23 | | #include "llvm/IR/Dominators.h" |
24 | | |
25 | | namespace llvm { |
26 | | |
27 | | //===----------------------------------------------------------------------===// |
28 | | // APIs for simple analysis of the loop. See header notes. |
29 | | |
30 | | /// getExitingBlocks - Return all blocks inside the loop that have successors |
31 | | /// outside of the loop. These are the blocks _inside of the current loop_ |
32 | | /// which branch out. The returned list is always unique. |
33 | | /// |
34 | | template <class BlockT, class LoopT> |
35 | | void LoopBase<BlockT, LoopT>::getExitingBlocks( |
36 | 11.6M | SmallVectorImpl<BlockT *> &ExitingBlocks) const { |
37 | 11.6M | assert(!isInvalid() && "Loop not in a valid state!"); |
38 | 11.6M | for (const auto BB : blocks()) |
39 | 44.2M | for (const auto &Succ : children<BlockT *>(BB)) |
40 | 67.1M | if (67.1M !contains(Succ)67.1M ) { |
41 | 14.4M | // Not in current loop? It must be an exit block. |
42 | 14.4M | ExitingBlocks.push_back(BB); |
43 | 14.4M | break; |
44 | 14.4M | } |
45 | 11.6M | } llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const Line | Count | Source | 36 | 86.6k | SmallVectorImpl<BlockT *> &ExitingBlocks) const { | 37 | 86.6k | assert(!isInvalid() && "Loop not in a valid state!"); | 38 | 86.6k | for (const auto BB : blocks()) | 39 | 3.79M | for (const auto &Succ : children<BlockT *>(BB)) | 40 | 6.15M | if (6.15M !contains(Succ)6.15M ) { | 41 | 213k | // Not in current loop? It must be an exit block. | 42 | 213k | ExitingBlocks.push_back(BB); | 43 | 213k | break; | 44 | 213k | } | 45 | 86.6k | } |
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const Line | Count | Source | 36 | 11.5M | SmallVectorImpl<BlockT *> &ExitingBlocks) const { | 37 | 11.5M | assert(!isInvalid() && "Loop not in a valid state!"); | 38 | 11.5M | for (const auto BB : blocks()) | 39 | 40.4M | for (const auto &Succ : children<BlockT *>(BB)) | 40 | 61.0M | if (61.0M !contains(Succ)61.0M ) { | 41 | 14.1M | // Not in current loop? It must be an exit block. | 42 | 14.1M | ExitingBlocks.push_back(BB); | 43 | 14.1M | break; | 44 | 14.1M | } | 45 | 11.5M | } |
|
46 | | |
47 | | /// getExitingBlock - If getExitingBlocks would return exactly one block, |
48 | | /// return that block. Otherwise return null. |
49 | | template <class BlockT, class LoopT> |
50 | 6.08M | BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { |
51 | 6.08M | assert(!isInvalid() && "Loop not in a valid state!"); |
52 | 6.08M | SmallVector<BlockT *, 8> ExitingBlocks; |
53 | 6.08M | getExitingBlocks(ExitingBlocks); |
54 | 6.08M | if (ExitingBlocks.size() == 1) |
55 | 5.21M | return ExitingBlocks[0]; |
56 | 861k | return nullptr; |
57 | 6.08M | } llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlock() const Line | Count | Source | 50 | 26 | BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { | 51 | 26 | assert(!isInvalid() && "Loop not in a valid state!"); | 52 | 26 | SmallVector<BlockT *, 8> ExitingBlocks; | 53 | 26 | getExitingBlocks(ExitingBlocks); | 54 | 26 | if (ExitingBlocks.size() == 1) | 55 | 14 | return ExitingBlocks[0]; | 56 | 12 | return nullptr; | 57 | 26 | } |
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlock() const Line | Count | Source | 50 | 6.08M | BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { | 51 | 6.08M | assert(!isInvalid() && "Loop not in a valid state!"); | 52 | 6.08M | SmallVector<BlockT *, 8> ExitingBlocks; | 53 | 6.08M | getExitingBlocks(ExitingBlocks); | 54 | 6.08M | if (ExitingBlocks.size() == 1) | 55 | 5.21M | return ExitingBlocks[0]; | 56 | 861k | return nullptr; | 57 | 6.08M | } |
|
58 | | |
59 | | /// getExitBlocks - Return all of the successor blocks of this loop. These |
60 | | /// are the blocks _outside of the current loop_ which are branched to. |
61 | | /// |
62 | | template <class BlockT, class LoopT> |
63 | | void LoopBase<BlockT, LoopT>::getExitBlocks( |
64 | 14.3M | SmallVectorImpl<BlockT *> &ExitBlocks) const { |
65 | 14.3M | assert(!isInvalid() && "Loop not in a valid state!"); |
66 | 14.3M | for (const auto BB : blocks()) |
67 | 77.7M | for (const auto &Succ : children<BlockT *>(BB)) |
68 | 130M | if (130M !contains(Succ)130M ) |
69 | 130M | // Not in current loop? It must be an exit block. |
70 | 19.4M | ExitBlocks.push_back(Succ); |
71 | 14.3M | } llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const Line | Count | Source | 64 | 13.8M | SmallVectorImpl<BlockT *> &ExitBlocks) const { | 65 | 13.8M | assert(!isInvalid() && "Loop not in a valid state!"); | 66 | 13.8M | for (const auto BB : blocks()) | 67 | 75.4M | for (const auto &Succ : children<BlockT *>(BB)) | 68 | 126M | if (126M !contains(Succ)126M ) | 69 | 126M | // Not in current loop? It must be an exit block. | 70 | 18.7M | ExitBlocks.push_back(Succ); | 71 | 13.8M | } |
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const Line | Count | Source | 64 | 512k | SmallVectorImpl<BlockT *> &ExitBlocks) const { | 65 | 512k | assert(!isInvalid() && "Loop not in a valid state!"); | 66 | 512k | for (const auto BB : blocks()) | 67 | 2.29M | for (const auto &Succ : children<BlockT *>(BB)) | 68 | 3.89M | if (3.89M !contains(Succ)3.89M ) | 69 | 3.89M | // Not in current loop? It must be an exit block. | 70 | 666k | ExitBlocks.push_back(Succ); | 71 | 512k | } |
|
72 | | |
73 | | /// getExitBlock - If getExitBlocks would return exactly one block, |
74 | | /// return that block. Otherwise return null. |
75 | | template <class BlockT, class LoopT> |
76 | 413k | BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { |
77 | 413k | assert(!isInvalid() && "Loop not in a valid state!"); |
78 | 413k | SmallVector<BlockT *, 8> ExitBlocks; |
79 | 413k | getExitBlocks(ExitBlocks); |
80 | 413k | if (ExitBlocks.size() == 1) |
81 | 324k | return ExitBlocks[0]; |
82 | 89.6k | return nullptr; |
83 | 413k | } Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlock() const llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlock() const Line | Count | Source | 76 | 413k | BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { | 77 | 413k | assert(!isInvalid() && "Loop not in a valid state!"); | 78 | 413k | SmallVector<BlockT *, 8> ExitBlocks; | 79 | 413k | getExitBlocks(ExitBlocks); | 80 | 413k | if (ExitBlocks.size() == 1) | 81 | 324k | return ExitBlocks[0]; | 82 | 89.6k | return nullptr; | 83 | 413k | } |
|
84 | | |
85 | | /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). |
86 | | template <class BlockT, class LoopT> |
87 | | void LoopBase<BlockT, LoopT>::getExitEdges( |
88 | 0 | SmallVectorImpl<Edge> &ExitEdges) const { |
89 | 0 | assert(!isInvalid() && "Loop not in a valid state!"); |
90 | 0 | for (const auto BB : blocks()) |
91 | 0 | for (const auto &Succ : children<BlockT *>(BB)) |
92 | 0 | if (0 !contains(Succ)0 ) |
93 | 0 | // Not in current loop? It must be an exit block. |
94 | 0 | ExitEdges.emplace_back(BB, Succ); |
95 | 0 | } Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitEdges(llvm::SmallVectorImpl<std::__1::pair<llvm::BasicBlock const*, llvm::BasicBlock const*> >&) const Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitEdges(llvm::SmallVectorImpl<std::__1::pair<llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*> >&) const |
96 | | |
97 | | /// getLoopPreheader - If there is a preheader for this loop, return it. A |
98 | | /// loop has a preheader if there is only one edge to the header of the loop |
99 | | /// from outside of the loop and it is legal to hoist instructions into the |
100 | | /// predecessor. If this is the case, the block branching to the header of the |
101 | | /// loop is the preheader node. |
102 | | /// |
103 | | /// This method returns null if there is no preheader for the loop. |
104 | | /// |
105 | | template <class BlockT, class LoopT> |
106 | 18.5M | BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { |
107 | 18.5M | assert(!isInvalid() && "Loop not in a valid state!"); |
108 | 18.5M | // Keep track of nodes outside the loop branching to the header... |
109 | 18.5M | BlockT *Out = getLoopPredecessor(); |
110 | 18.5M | if (!Out) |
111 | 14.5k | return nullptr; |
112 | 18.5M | |
113 | 18.5M | // Make sure we are allowed to hoist instructions into the predecessor. |
114 | 18.5M | if (18.5M !Out->isLegalToHoistInto()18.5M ) |
115 | 33 | return nullptr; |
116 | 18.5M | |
117 | 18.5M | // Make sure there is only one exit out of the preheader. |
118 | 18.5M | typedef GraphTraits<BlockT *> BlockTraits; |
119 | 18.5M | typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); |
120 | 18.5M | ++SI; |
121 | 18.5M | if (SI != BlockTraits::child_end(Out)) |
122 | 170k | return nullptr; // Multiple exits from the block, must not be a preheader. |
123 | 18.5M | |
124 | 18.5M | // The predecessor has exactly one successor, so it is a preheader. |
125 | 18.3M | return Out; |
126 | 18.5M | } llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPreheader() const Line | Count | Source | 106 | 544k | BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { | 107 | 544k | assert(!isInvalid() && "Loop not in a valid state!"); | 108 | 544k | // Keep track of nodes outside the loop branching to the header... | 109 | 544k | BlockT *Out = getLoopPredecessor(); | 110 | 544k | if (!Out) | 111 | 2.82k | return nullptr; | 112 | 544k | | 113 | 544k | // Make sure we are allowed to hoist instructions into the predecessor. | 114 | 541k | if (541k !Out->isLegalToHoistInto()541k ) | 115 | 0 | return nullptr; | 116 | 541k | | 117 | 541k | // Make sure there is only one exit out of the preheader. | 118 | 541k | typedef GraphTraits<BlockT *> BlockTraits; | 119 | 541k | typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); | 120 | 541k | ++SI; | 121 | 541k | if (SI != BlockTraits::child_end(Out)) | 122 | 23.6k | return nullptr; // Multiple exits from the block, must not be a preheader. | 123 | 541k | | 124 | 541k | // The predecessor has exactly one successor, so it is a preheader. | 125 | 518k | return Out; | 126 | 544k | } |
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPreheader() const Line | Count | Source | 106 | 18.0M | BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { | 107 | 18.0M | assert(!isInvalid() && "Loop not in a valid state!"); | 108 | 18.0M | // Keep track of nodes outside the loop branching to the header... | 109 | 18.0M | BlockT *Out = getLoopPredecessor(); | 110 | 18.0M | if (!Out) | 111 | 11.6k | return nullptr; | 112 | 18.0M | | 113 | 18.0M | // Make sure we are allowed to hoist instructions into the predecessor. | 114 | 18.0M | if (18.0M !Out->isLegalToHoistInto()18.0M ) | 115 | 33 | return nullptr; | 116 | 18.0M | | 117 | 18.0M | // Make sure there is only one exit out of the preheader. | 118 | 18.0M | typedef GraphTraits<BlockT *> BlockTraits; | 119 | 18.0M | typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); | 120 | 18.0M | ++SI; | 121 | 18.0M | if (SI != BlockTraits::child_end(Out)) | 122 | 147k | return nullptr; // Multiple exits from the block, must not be a preheader. | 123 | 18.0M | | 124 | 18.0M | // The predecessor has exactly one successor, so it is a preheader. | 125 | 17.8M | return Out; | 126 | 18.0M | } |
|
127 | | |
128 | | /// getLoopPredecessor - If the given loop's header has exactly one unique |
129 | | /// predecessor outside the loop, return it. Otherwise return null. |
130 | | /// This is less strict that the loop "preheader" concept, which requires |
131 | | /// the predecessor to have exactly one successor. |
132 | | /// |
133 | | template <class BlockT, class LoopT> |
134 | 20.9M | BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { |
135 | 20.9M | assert(!isInvalid() && "Loop not in a valid state!"); |
136 | 20.9M | // Keep track of nodes outside the loop branching to the header... |
137 | 20.9M | BlockT *Out = nullptr; |
138 | 20.9M | |
139 | 20.9M | // Loop over the predecessors of the header node... |
140 | 20.9M | BlockT *Header = getHeader(); |
141 | 41.7M | for (const auto Pred : children<Inverse<BlockT *>>(Header)) { |
142 | 41.7M | if (!contains(Pred)41.7M ) { // If the block is not in the loop... |
143 | 20.9M | if (Out && 20.9M Out != Pred23.0k ) |
144 | 22.9k | return nullptr; // Multiple predecessors outside the loop |
145 | 20.9M | Out = Pred; |
146 | 20.9M | } |
147 | 41.7M | } |
148 | 20.9M | |
149 | 20.9M | // Make sure there is only one exit out of the preheader. |
150 | 20.9M | assert(Out && "Header of loop has no predecessors from outside loop?"); |
151 | 20.9M | return Out; |
152 | 20.9M | } llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPredecessor() const Line | Count | Source | 134 | 20.1M | BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { | 135 | 20.1M | assert(!isInvalid() && "Loop not in a valid state!"); | 136 | 20.1M | // Keep track of nodes outside the loop branching to the header... | 137 | 20.1M | BlockT *Out = nullptr; | 138 | 20.1M | | 139 | 20.1M | // Loop over the predecessors of the header node... | 140 | 20.1M | BlockT *Header = getHeader(); | 141 | 40.0M | for (const auto Pred : children<Inverse<BlockT *>>(Header)) { | 142 | 40.0M | if (!contains(Pred)40.0M ) { // If the block is not in the loop... | 143 | 20.1M | if (Out && 20.1M Out != Pred11.8k ) | 144 | 11.6k | return nullptr; // Multiple predecessors outside the loop | 145 | 20.1M | Out = Pred; | 146 | 20.1M | } | 147 | 40.0M | } | 148 | 20.1M | | 149 | 20.1M | // Make sure there is only one exit out of the preheader. | 150 | 20.0M | assert(Out && "Header of loop has no predecessors from outside loop?"); | 151 | 20.0M | return Out; | 152 | 20.1M | } |
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPredecessor() const Line | Count | Source | 134 | 832k | BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { | 135 | 832k | assert(!isInvalid() && "Loop not in a valid state!"); | 136 | 832k | // Keep track of nodes outside the loop branching to the header... | 137 | 832k | BlockT *Out = nullptr; | 138 | 832k | | 139 | 832k | // Loop over the predecessors of the header node... | 140 | 832k | BlockT *Header = getHeader(); | 141 | 1.71M | for (const auto Pred : children<Inverse<BlockT *>>(Header)) { | 142 | 1.71M | if (!contains(Pred)1.71M ) { // If the block is not in the loop... | 143 | 844k | if (Out && 844k Out != Pred11.2k ) | 144 | 11.2k | return nullptr; // Multiple predecessors outside the loop | 145 | 832k | Out = Pred; | 146 | 832k | } | 147 | 1.71M | } | 148 | 832k | | 149 | 832k | // Make sure there is only one exit out of the preheader. | 150 | 821k | assert(Out && "Header of loop has no predecessors from outside loop?"); | 151 | 821k | return Out; | 152 | 832k | } |
|
153 | | |
154 | | /// getLoopLatch - If there is a single latch block for this loop, return it. |
155 | | /// A latch block is a block that contains a branch back to the header. |
156 | | template <class BlockT, class LoopT> |
157 | 25.1M | BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { |
158 | 25.1M | assert(!isInvalid() && "Loop not in a valid state!"); |
159 | 25.1M | BlockT *Header = getHeader(); |
160 | 25.1M | BlockT *Latch = nullptr; |
161 | 50.2M | for (const auto Pred : children<Inverse<BlockT *>>(Header)) { |
162 | 50.2M | if (contains(Pred)50.2M ) { |
163 | 25.1M | if (Latch) |
164 | 4.71k | return nullptr; |
165 | 25.1M | Latch = Pred; |
166 | 25.1M | } |
167 | 50.2M | } |
168 | 25.1M | |
169 | 25.1M | return Latch; |
170 | 25.1M | } llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatch() const Line | Count | Source | 157 | 25.1M | BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { | 158 | 25.1M | assert(!isInvalid() && "Loop not in a valid state!"); | 159 | 25.1M | BlockT *Header = getHeader(); | 160 | 25.1M | BlockT *Latch = nullptr; | 161 | 50.2M | for (const auto Pred : children<Inverse<BlockT *>>(Header)) { | 162 | 50.2M | if (contains(Pred)50.2M ) { | 163 | 25.1M | if (Latch) | 164 | 4.71k | return nullptr; | 165 | 25.1M | Latch = Pred; | 166 | 25.1M | } | 167 | 50.2M | } | 168 | 25.1M | | 169 | 25.1M | return Latch; | 170 | 25.1M | } |
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopLatch() const Line | Count | Source | 157 | 1.57k | BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { | 158 | 1.57k | assert(!isInvalid() && "Loop not in a valid state!"); | 159 | 1.57k | BlockT *Header = getHeader(); | 160 | 1.57k | BlockT *Latch = nullptr; | 161 | 3.14k | for (const auto Pred : children<Inverse<BlockT *>>(Header)) { | 162 | 3.14k | if (contains(Pred)3.14k ) { | 163 | 1.57k | if (Latch) | 164 | 3 | return nullptr; | 165 | 1.57k | Latch = Pred; | 166 | 1.57k | } | 167 | 3.14k | } | 168 | 1.57k | | 169 | 1.57k | return Latch; | 170 | 1.57k | } |
|
171 | | |
172 | | //===----------------------------------------------------------------------===// |
173 | | // APIs for updating loop information after changing the CFG |
174 | | // |
175 | | |
176 | | /// addBasicBlockToLoop - This method is used by other analyses to update loop |
177 | | /// information. NewBB is set to be a new member of the current loop. |
178 | | /// Because of this, it is added as a member of all parent loops, and is added |
179 | | /// to the specified LoopInfo object as being in the current basic block. It |
180 | | /// is not valid to replace the loop header with this method. |
181 | | /// |
182 | | template <class BlockT, class LoopT> |
183 | | void LoopBase<BlockT, LoopT>::addBasicBlockToLoop( |
184 | 1.16M | BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { |
185 | 1.16M | assert(!isInvalid() && "Loop not in a valid state!"); |
186 | | #ifndef NDEBUG |
187 | | if (!Blocks.empty()) { |
188 | | auto SameHeader = LIB[getHeader()]; |
189 | | assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() && |
190 | | "Incorrect LI specified for this loop!"); |
191 | | } |
192 | | #endif |
193 | | assert(NewBB && "Cannot add a null basic block to the loop!"); |
194 | 1.16M | assert(!LIB[NewBB] && "BasicBlock already in the loop!"); |
195 | 1.16M | |
196 | 1.16M | LoopT *L = static_cast<LoopT *>(this); |
197 | 1.16M | |
198 | 1.16M | // Add the loop mapping to the LoopInfo object... |
199 | 1.16M | LIB.BBMap[NewBB] = L; |
200 | 1.16M | |
201 | 1.16M | // Add the basic block to this loop and all parent loops... |
202 | 2.99M | while (L2.99M ) { |
203 | 1.82M | L->addBlockEntry(NewBB); |
204 | 1.82M | L = L->getParentLoop(); |
205 | 1.82M | } |
206 | 1.16M | } llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBasicBlockToLoop(llvm::MachineBasicBlock*, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&) Line | Count | Source | 184 | 96.5k | BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { | 185 | 96.5k | assert(!isInvalid() && "Loop not in a valid state!"); | 186 | | #ifndef NDEBUG | 187 | | if (!Blocks.empty()) { | 188 | | auto SameHeader = LIB[getHeader()]; | 189 | | assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() && | 190 | | "Incorrect LI specified for this loop!"); | 191 | | } | 192 | | #endif | 193 | | assert(NewBB && "Cannot add a null basic block to the loop!"); | 194 | 96.5k | assert(!LIB[NewBB] && "BasicBlock already in the loop!"); | 195 | 96.5k | | 196 | 96.5k | LoopT *L = static_cast<LoopT *>(this); | 197 | 96.5k | | 198 | 96.5k | // Add the loop mapping to the LoopInfo object... | 199 | 96.5k | LIB.BBMap[NewBB] = L; | 200 | 96.5k | | 201 | 96.5k | // Add the basic block to this loop and all parent loops... | 202 | 256k | while (L256k ) { | 203 | 159k | L->addBlockEntry(NewBB); | 204 | 159k | L = L->getParentLoop(); | 205 | 159k | } | 206 | 96.5k | } |
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBasicBlockToLoop(llvm::BasicBlock*, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&) Line | Count | Source | 184 | 1.07M | BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { | 185 | 1.07M | assert(!isInvalid() && "Loop not in a valid state!"); | 186 | | #ifndef NDEBUG | 187 | | if (!Blocks.empty()) { | 188 | | auto SameHeader = LIB[getHeader()]; | 189 | | assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() && | 190 | | "Incorrect LI specified for this loop!"); | 191 | | } | 192 | | #endif | 193 | | assert(NewBB && "Cannot add a null basic block to the loop!"); | 194 | 1.07M | assert(!LIB[NewBB] && "BasicBlock already in the loop!"); | 195 | 1.07M | | 196 | 1.07M | LoopT *L = static_cast<LoopT *>(this); | 197 | 1.07M | | 198 | 1.07M | // Add the loop mapping to the LoopInfo object... | 199 | 1.07M | LIB.BBMap[NewBB] = L; | 200 | 1.07M | | 201 | 1.07M | // Add the basic block to this loop and all parent loops... | 202 | 2.73M | while (L2.73M ) { | 203 | 1.66M | L->addBlockEntry(NewBB); | 204 | 1.66M | L = L->getParentLoop(); | 205 | 1.66M | } | 206 | 1.07M | } |
|
207 | | |
208 | | /// replaceChildLoopWith - This is used when splitting loops up. It replaces |
209 | | /// the OldChild entry in our children list with NewChild, and updates the |
210 | | /// parent pointer of OldChild to be null and the NewChild to be this loop. |
211 | | /// This updates the loop depth of the new child. |
212 | | template <class BlockT, class LoopT> |
213 | | void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild, |
214 | 122 | LoopT *NewChild) { |
215 | 122 | assert(!isInvalid() && "Loop not in a valid state!"); |
216 | 122 | assert(OldChild->ParentLoop == this && "This loop is already broken!"); |
217 | 122 | assert(!NewChild->ParentLoop && "NewChild already has a parent!"); |
218 | 122 | typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild); |
219 | 122 | assert(I != SubLoops.end() && "OldChild not in loop!"); |
220 | 122 | *I = NewChild; |
221 | 122 | OldChild->ParentLoop = nullptr; |
222 | 122 | NewChild->ParentLoop = static_cast<LoopT *>(this); |
223 | 122 | } Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::replaceChildLoopWith(llvm::MachineLoop*, llvm::MachineLoop*) llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::replaceChildLoopWith(llvm::Loop*, llvm::Loop*) Line | Count | Source | 214 | 122 | LoopT *NewChild) { | 215 | 122 | assert(!isInvalid() && "Loop not in a valid state!"); | 216 | 122 | assert(OldChild->ParentLoop == this && "This loop is already broken!"); | 217 | 122 | assert(!NewChild->ParentLoop && "NewChild already has a parent!"); | 218 | 122 | typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild); | 219 | 122 | assert(I != SubLoops.end() && "OldChild not in loop!"); | 220 | 122 | *I = NewChild; | 221 | 122 | OldChild->ParentLoop = nullptr; | 222 | 122 | NewChild->ParentLoop = static_cast<LoopT *>(this); | 223 | 122 | } |
|
224 | | |
225 | | /// verifyLoop - Verify loop structure |
226 | | template <class BlockT, class LoopT> |
227 | 4.85M | void LoopBase<BlockT, LoopT>::verifyLoop() const { |
228 | 4.85M | assert(!isInvalid() && "Loop not in a valid state!"); |
229 | | #ifndef NDEBUG |
230 | | assert(!Blocks.empty() && "Loop header is missing"); |
231 | | |
232 | | // Setup for using a depth-first iterator to visit every block in the loop. |
233 | | SmallVector<BlockT *, 8> ExitBBs; |
234 | | getExitBlocks(ExitBBs); |
235 | | df_iterator_default_set<BlockT *> VisitSet; |
236 | | VisitSet.insert(ExitBBs.begin(), ExitBBs.end()); |
237 | | df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>> |
238 | | BI = df_ext_begin(getHeader(), VisitSet), |
239 | | BE = df_ext_end(getHeader(), VisitSet); |
240 | | |
241 | | // Keep track of the BBs visited. |
242 | | SmallPtrSet<BlockT *, 8> VisitedBBs; |
243 | | |
244 | | // Check the individual blocks. |
245 | | for (; BI != BE; ++BI) { |
246 | | BlockT *BB = *BI; |
247 | | |
248 | | assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB), |
249 | | GraphTraits<BlockT *>::child_end(BB), |
250 | | [&](BlockT *B) { return contains(B); }) && |
251 | | "Loop block has no in-loop successors!"); |
252 | | |
253 | | assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB), |
254 | | GraphTraits<Inverse<BlockT *>>::child_end(BB), |
255 | | [&](BlockT *B) { return contains(B); }) && |
256 | | "Loop block has no in-loop predecessors!"); |
257 | | |
258 | | SmallVector<BlockT *, 2> OutsideLoopPreds; |
259 | | std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB), |
260 | | GraphTraits<Inverse<BlockT *>>::child_end(BB), |
261 | | [&](BlockT *B) { |
262 | | if (!contains(B)) |
263 | | OutsideLoopPreds.push_back(B); |
264 | | }); |
265 | | |
266 | | if (BB == getHeader()) { |
267 | | assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); |
268 | | } else if (!OutsideLoopPreds.empty()) { |
269 | | // A non-header loop shouldn't be reachable from outside the loop, |
270 | | // though it is permitted if the predecessor is not itself actually |
271 | | // reachable. |
272 | | BlockT *EntryBB = &BB->getParent()->front(); |
273 | | for (BlockT *CB : depth_first(EntryBB)) |
274 | | for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) |
275 | | assert(CB != OutsideLoopPreds[i] && |
276 | | "Loop has multiple entry points!"); |
277 | | } |
278 | | assert(BB != &getHeader()->getParent()->front() && |
279 | | "Loop contains function entry block!"); |
280 | | |
281 | | VisitedBBs.insert(BB); |
282 | | } |
283 | | |
284 | | if (VisitedBBs.size() != getNumBlocks()) { |
285 | | dbgs() << "The following blocks are unreachable in the loop: "; |
286 | | for (auto BB : Blocks) { |
287 | | if (!VisitedBBs.count(BB)) { |
288 | | dbgs() << *BB << "\n"; |
289 | | } |
290 | | } |
291 | | assert(false && "Unreachable block in loop"); |
292 | | } |
293 | | |
294 | | // Check the subloops. |
295 | | for (iterator I = begin(), E = end(); I != E; ++I) |
296 | | // Each block in each subloop should be contained within this loop. |
297 | | for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); |
298 | | BI != BE; ++BI) { |
299 | | assert(contains(*BI) && |
300 | | "Loop does not contain all the blocks of a subloop!"); |
301 | | } |
302 | | |
303 | | // Check the parent loop pointer. |
304 | | if (ParentLoop) { |
305 | | assert(is_contained(*ParentLoop, this) && |
306 | | "Loop is not a subloop of its parent!"); |
307 | | } |
308 | | #endif |
309 | | } Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verifyLoop() const llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoop() const Line | Count | Source | 227 | 4.85M | void LoopBase<BlockT, LoopT>::verifyLoop() const { | 228 | 4.85M | assert(!isInvalid() && "Loop not in a valid state!"); | 229 | | #ifndef NDEBUG | 230 | | assert(!Blocks.empty() && "Loop header is missing"); | 231 | | | 232 | | // Setup for using a depth-first iterator to visit every block in the loop. | 233 | | SmallVector<BlockT *, 8> ExitBBs; | 234 | | getExitBlocks(ExitBBs); | 235 | | df_iterator_default_set<BlockT *> VisitSet; | 236 | | VisitSet.insert(ExitBBs.begin(), ExitBBs.end()); | 237 | | df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>> | 238 | | BI = df_ext_begin(getHeader(), VisitSet), | 239 | | BE = df_ext_end(getHeader(), VisitSet); | 240 | | | 241 | | // Keep track of the BBs visited. | 242 | | SmallPtrSet<BlockT *, 8> VisitedBBs; | 243 | | | 244 | | // Check the individual blocks. | 245 | | for (; BI != BE; ++BI) { | 246 | | BlockT *BB = *BI; | 247 | | | 248 | | assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB), | 249 | | GraphTraits<BlockT *>::child_end(BB), | 250 | | [&](BlockT *B) { return contains(B); }) && | 251 | | "Loop block has no in-loop successors!"); | 252 | | | 253 | | assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB), | 254 | | GraphTraits<Inverse<BlockT *>>::child_end(BB), | 255 | | [&](BlockT *B) { return contains(B); }) && | 256 | | "Loop block has no in-loop predecessors!"); | 257 | | | 258 | | SmallVector<BlockT *, 2> OutsideLoopPreds; | 259 | | std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB), | 260 | | GraphTraits<Inverse<BlockT *>>::child_end(BB), | 261 | | [&](BlockT *B) { | 262 | | if (!contains(B)) | 263 | | OutsideLoopPreds.push_back(B); | 264 | | }); | 265 | | | 266 | | if (BB == getHeader()) { | 267 | | assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); | 268 | | } else if (!OutsideLoopPreds.empty()) { | 269 | | // A non-header loop shouldn't be reachable from outside the loop, | 270 | | // though it is permitted if the predecessor is not itself actually | 271 | | // reachable. | 272 | | BlockT *EntryBB = &BB->getParent()->front(); | 273 | | for (BlockT *CB : depth_first(EntryBB)) | 274 | | for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) | 275 | | assert(CB != OutsideLoopPreds[i] && | 276 | | "Loop has multiple entry points!"); | 277 | | } | 278 | | assert(BB != &getHeader()->getParent()->front() && | 279 | | "Loop contains function entry block!"); | 280 | | | 281 | | VisitedBBs.insert(BB); | 282 | | } | 283 | | | 284 | | if (VisitedBBs.size() != getNumBlocks()) { | 285 | | dbgs() << "The following blocks are unreachable in the loop: "; | 286 | | for (auto BB : Blocks) { | 287 | | if (!VisitedBBs.count(BB)) { | 288 | | dbgs() << *BB << "\n"; | 289 | | } | 290 | | } | 291 | | assert(false && "Unreachable block in loop"); | 292 | | } | 293 | | | 294 | | // Check the subloops. | 295 | | for (iterator I = begin(), E = end(); I != E; ++I) | 296 | | // Each block in each subloop should be contained within this loop. | 297 | | for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); | 298 | | BI != BE; ++BI) { | 299 | | assert(contains(*BI) && | 300 | | "Loop does not contain all the blocks of a subloop!"); | 301 | | } | 302 | | | 303 | | // Check the parent loop pointer. | 304 | | if (ParentLoop) { | 305 | | assert(is_contained(*ParentLoop, this) && | 306 | | "Loop is not a subloop of its parent!"); | 307 | | } | 308 | | #endif | 309 | | } |
|
310 | | |
311 | | /// verifyLoop - Verify loop structure of this loop and all nested loops. |
312 | | template <class BlockT, class LoopT> |
313 | | void LoopBase<BlockT, LoopT>::verifyLoopNest( |
314 | 54 | DenseSet<const LoopT *> *Loops) const { |
315 | 54 | assert(!isInvalid() && "Loop not in a valid state!"); |
316 | 54 | Loops->insert(static_cast<const LoopT *>(this)); |
317 | 54 | // Verify this loop. |
318 | 54 | verifyLoop(); |
319 | 54 | // Verify the subloops. |
320 | 77 | for (iterator I = begin(), E = end(); I != E77 ; ++I23 ) |
321 | 23 | (*I)->verifyLoopNest(Loops); |
322 | 54 | } llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoopNest(llvm::DenseSet<llvm::Loop const*, llvm::DenseMapInfo<llvm::Loop const*> >*) const Line | Count | Source | 314 | 54 | DenseSet<const LoopT *> *Loops) const { | 315 | 54 | assert(!isInvalid() && "Loop not in a valid state!"); | 316 | 54 | Loops->insert(static_cast<const LoopT *>(this)); | 317 | 54 | // Verify this loop. | 318 | 54 | verifyLoop(); | 319 | 54 | // Verify the subloops. | 320 | 77 | for (iterator I = begin(), E = end(); I != E77 ; ++I23 ) | 321 | 23 | (*I)->verifyLoopNest(Loops); | 322 | 54 | } |
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verifyLoopNest(llvm::DenseSet<llvm::MachineLoop const*, llvm::DenseMapInfo<llvm::MachineLoop const*> >*) const |
323 | | |
324 | | template <class BlockT, class LoopT> |
325 | | void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth, |
326 | 531 | bool Verbose) const { |
327 | 531 | OS.indent(Depth * 2) << "Loop at depth " << getLoopDepth() << " containing: "; |
328 | 531 | |
329 | 531 | BlockT *H = getHeader(); |
330 | 1.55k | for (unsigned i = 0; i < getBlocks().size()1.55k ; ++i1.02k ) { |
331 | 1.02k | BlockT *BB = getBlocks()[i]; |
332 | 1.02k | if (!Verbose1.02k ) { |
333 | 1.02k | if (i) |
334 | 492 | OS << ","; |
335 | 1.02k | BB->printAsOperand(OS, false); |
336 | 1.02k | } else |
337 | 0 | OS << "\n"; |
338 | 1.02k | |
339 | 1.02k | if (BB == H) |
340 | 531 | OS << "<header>"; |
341 | 1.02k | if (isLoopLatch(BB)) |
342 | 531 | OS << "<latch>"; |
343 | 1.02k | if (isLoopExiting(BB)) |
344 | 570 | OS << "<exiting>"; |
345 | 1.02k | if (Verbose) |
346 | 0 | BB->print(OS); |
347 | 1.02k | } |
348 | 531 | OS << "\n"; |
349 | 531 | |
350 | 659 | for (iterator I = begin(), E = end(); I != E659 ; ++I128 ) |
351 | 128 | (*I)->print(OS, Depth + 2); |
352 | 531 | } Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::print(llvm::raw_ostream&, unsigned int, bool) const llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&, unsigned int, bool) const Line | Count | Source | 326 | 531 | bool Verbose) const { | 327 | 531 | OS.indent(Depth * 2) << "Loop at depth " << getLoopDepth() << " containing: "; | 328 | 531 | | 329 | 531 | BlockT *H = getHeader(); | 330 | 1.55k | for (unsigned i = 0; i < getBlocks().size()1.55k ; ++i1.02k ) { | 331 | 1.02k | BlockT *BB = getBlocks()[i]; | 332 | 1.02k | if (!Verbose1.02k ) { | 333 | 1.02k | if (i) | 334 | 492 | OS << ","; | 335 | 1.02k | BB->printAsOperand(OS, false); | 336 | 1.02k | } else | 337 | 0 | OS << "\n"; | 338 | 1.02k | | 339 | 1.02k | if (BB == H) | 340 | 531 | OS << "<header>"; | 341 | 1.02k | if (isLoopLatch(BB)) | 342 | 531 | OS << "<latch>"; | 343 | 1.02k | if (isLoopExiting(BB)) | 344 | 570 | OS << "<exiting>"; | 345 | 1.02k | if (Verbose) | 346 | 0 | BB->print(OS); | 347 | 1.02k | } | 348 | 531 | OS << "\n"; | 349 | 531 | | 350 | 659 | for (iterator I = begin(), E = end(); I != E659 ; ++I128 ) | 351 | 128 | (*I)->print(OS, Depth + 2); | 352 | 531 | } |
|
353 | | |
354 | | //===----------------------------------------------------------------------===// |
355 | | /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the |
356 | | /// result does / not depend on use list (block predecessor) order. |
357 | | /// |
358 | | |
359 | | /// Discover a subloop with the specified backedges such that: All blocks within |
360 | | /// this loop are mapped to this loop or a subloop. And all subloops within this |
361 | | /// loop have their parent loop set to this loop or a subloop. |
362 | | template <class BlockT, class LoopT> |
363 | | static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges, |
364 | | LoopInfoBase<BlockT, LoopT> *LI, |
365 | 7.59M | const DomTreeBase<BlockT> &DomTree) { |
366 | 7.59M | typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits; |
367 | 7.59M | |
368 | 7.59M | unsigned NumBlocks = 0; |
369 | 7.59M | unsigned NumSubloops = 0; |
370 | 7.59M | |
371 | 7.59M | // Perform a backward CFG traversal using a worklist. |
372 | 7.59M | std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); |
373 | 41.4M | while (!ReverseCFGWorklist.empty()41.4M ) { |
374 | 33.8M | BlockT *PredBB = ReverseCFGWorklist.back(); |
375 | 33.8M | ReverseCFGWorklist.pop_back(); |
376 | 33.8M | |
377 | 33.8M | LoopT *Subloop = LI->getLoopFor(PredBB); |
378 | 33.8M | if (!Subloop33.8M ) { |
379 | 23.8M | if (!DomTree.isReachableFromEntry(PredBB)) |
380 | 24 | continue; |
381 | 23.8M | |
382 | 23.8M | // This is an undiscovered block. Map it to the current loop. |
383 | 23.8M | LI->changeLoopFor(PredBB, L); |
384 | 23.8M | ++NumBlocks; |
385 | 23.8M | if (PredBB == L->getHeader()) |
386 | 7.59M | continue; |
387 | 23.8M | // Push all block predecessors on the worklist. |
388 | 16.2M | ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), |
389 | 16.2M | InvBlockTraits::child_begin(PredBB), |
390 | 16.2M | InvBlockTraits::child_end(PredBB)); |
391 | 33.8M | } else { |
392 | 10.0M | // This is a discovered block. Find its outermost discovered loop. |
393 | 10.4M | while (LoopT *Parent = Subloop->getParentLoop()) |
394 | 428k | Subloop = Parent; |
395 | 10.0M | |
396 | 10.0M | // If it is already discovered to be a subloop of this loop, continue. |
397 | 10.0M | if (Subloop == L) |
398 | 7.86M | continue; |
399 | 10.0M | |
400 | 10.0M | // Discover a subloop of this loop. |
401 | 2.15M | Subloop->setParentLoop(L); |
402 | 2.15M | ++NumSubloops; |
403 | 2.15M | NumBlocks += Subloop->getBlocks().capacity(); |
404 | 2.15M | PredBB = Subloop->getHeader(); |
405 | 2.15M | // Continue traversal along predecessors that are not loop-back edges from |
406 | 2.15M | // within this subloop tree itself. Note that a predecessor may directly |
407 | 2.15M | // reach another subloop that is not yet discovered to be a subloop of |
408 | 2.15M | // this loop, which we must traverse. |
409 | 4.33M | for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) { |
410 | 4.33M | if (LI->getLoopFor(Pred) != Subloop) |
411 | 2.16M | ReverseCFGWorklist.push_back(Pred); |
412 | 4.33M | } |
413 | 10.0M | } |
414 | 33.8M | } |
415 | 7.59M | L->getSubLoopsVector().reserve(NumSubloops); |
416 | 7.59M | L->reserveBlocks(NumBlocks); |
417 | 7.59M | } MachineLoopInfo.cpp:void llvm::discoverAndMapSubloop<llvm::MachineBasicBlock, llvm::MachineLoop>(llvm::MachineLoop*, llvm::ArrayRef<llvm::MachineBasicBlock*>, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>*, llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&) Line | Count | Source | 365 | 2.15M | const DomTreeBase<BlockT> &DomTree) { | 366 | 2.15M | typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits; | 367 | 2.15M | | 368 | 2.15M | unsigned NumBlocks = 0; | 369 | 2.15M | unsigned NumSubloops = 0; | 370 | 2.15M | | 371 | 2.15M | // Perform a backward CFG traversal using a worklist. | 372 | 2.15M | std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); | 373 | 11.7M | while (!ReverseCFGWorklist.empty()11.7M ) { | 374 | 9.55M | BlockT *PredBB = ReverseCFGWorklist.back(); | 375 | 9.55M | ReverseCFGWorklist.pop_back(); | 376 | 9.55M | | 377 | 9.55M | LoopT *Subloop = LI->getLoopFor(PredBB); | 378 | 9.55M | if (!Subloop9.55M ) { | 379 | 6.72M | if (!DomTree.isReachableFromEntry(PredBB)) | 380 | 0 | continue; | 381 | 6.72M | | 382 | 6.72M | // This is an undiscovered block. Map it to the current loop. | 383 | 6.72M | LI->changeLoopFor(PredBB, L); | 384 | 6.72M | ++NumBlocks; | 385 | 6.72M | if (PredBB == L->getHeader()) | 386 | 2.15M | continue; | 387 | 6.72M | // Push all block predecessors on the worklist. | 388 | 4.56M | ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), | 389 | 4.56M | InvBlockTraits::child_begin(PredBB), | 390 | 4.56M | InvBlockTraits::child_end(PredBB)); | 391 | 9.55M | } else { | 392 | 2.83M | // This is a discovered block. Find its outermost discovered loop. | 393 | 3.00M | while (LoopT *Parent = Subloop->getParentLoop()) | 394 | 168k | Subloop = Parent; | 395 | 2.83M | | 396 | 2.83M | // If it is already discovered to be a subloop of this loop, continue. | 397 | 2.83M | if (Subloop == L) | 398 | 2.21M | continue; | 399 | 2.83M | | 400 | 2.83M | // Discover a subloop of this loop. | 401 | 618k | Subloop->setParentLoop(L); | 402 | 618k | ++NumSubloops; | 403 | 618k | NumBlocks += Subloop->getBlocks().capacity(); | 404 | 618k | PredBB = Subloop->getHeader(); | 405 | 618k | // Continue traversal along predecessors that are not loop-back edges from | 406 | 618k | // within this subloop tree itself. Note that a predecessor may directly | 407 | 618k | // reach another subloop that is not yet discovered to be a subloop of | 408 | 618k | // this loop, which we must traverse. | 409 | 1.25M | for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) { | 410 | 1.25M | if (LI->getLoopFor(Pred) != Subloop) | 411 | 625k | ReverseCFGWorklist.push_back(Pred); | 412 | 1.25M | } | 413 | 2.83M | } | 414 | 9.55M | } | 415 | 2.15M | L->getSubLoopsVector().reserve(NumSubloops); | 416 | 2.15M | L->reserveBlocks(NumBlocks); | 417 | 2.15M | } |
LoopInfo.cpp:void llvm::discoverAndMapSubloop<llvm::BasicBlock, llvm::Loop>(llvm::Loop*, llvm::ArrayRef<llvm::BasicBlock*>, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>*, llvm::DominatorTreeBase<llvm::BasicBlock, false> const&) Line | Count | Source | 365 | 5.43M | const DomTreeBase<BlockT> &DomTree) { | 366 | 5.43M | typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits; | 367 | 5.43M | | 368 | 5.43M | unsigned NumBlocks = 0; | 369 | 5.43M | unsigned NumSubloops = 0; | 370 | 5.43M | | 371 | 5.43M | // Perform a backward CFG traversal using a worklist. | 372 | 5.43M | std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); | 373 | 29.7M | while (!ReverseCFGWorklist.empty()29.7M ) { | 374 | 24.3M | BlockT *PredBB = ReverseCFGWorklist.back(); | 375 | 24.3M | ReverseCFGWorklist.pop_back(); | 376 | 24.3M | | 377 | 24.3M | LoopT *Subloop = LI->getLoopFor(PredBB); | 378 | 24.3M | if (!Subloop24.3M ) { | 379 | 17.1M | if (!DomTree.isReachableFromEntry(PredBB)) | 380 | 24 | continue; | 381 | 17.1M | | 382 | 17.1M | // This is an undiscovered block. Map it to the current loop. | 383 | 17.1M | LI->changeLoopFor(PredBB, L); | 384 | 17.1M | ++NumBlocks; | 385 | 17.1M | if (PredBB == L->getHeader()) | 386 | 5.43M | continue; | 387 | 17.1M | // Push all block predecessors on the worklist. | 388 | 11.7M | ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), | 389 | 11.7M | InvBlockTraits::child_begin(PredBB), | 390 | 11.7M | InvBlockTraits::child_end(PredBB)); | 391 | 24.3M | } else { | 392 | 7.18M | // This is a discovered block. Find its outermost discovered loop. | 393 | 7.45M | while (LoopT *Parent = Subloop->getParentLoop()) | 394 | 260k | Subloop = Parent; | 395 | 7.18M | | 396 | 7.18M | // If it is already discovered to be a subloop of this loop, continue. | 397 | 7.18M | if (Subloop == L) | 398 | 5.65M | continue; | 399 | 7.18M | | 400 | 7.18M | // Discover a subloop of this loop. | 401 | 1.53M | Subloop->setParentLoop(L); | 402 | 1.53M | ++NumSubloops; | 403 | 1.53M | NumBlocks += Subloop->getBlocks().capacity(); | 404 | 1.53M | PredBB = Subloop->getHeader(); | 405 | 1.53M | // Continue traversal along predecessors that are not loop-back edges from | 406 | 1.53M | // within this subloop tree itself. Note that a predecessor may directly | 407 | 1.53M | // reach another subloop that is not yet discovered to be a subloop of | 408 | 1.53M | // this loop, which we must traverse. | 409 | 3.08M | for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) { | 410 | 3.08M | if (LI->getLoopFor(Pred) != Subloop) | 411 | 1.54M | ReverseCFGWorklist.push_back(Pred); | 412 | 3.08M | } | 413 | 7.18M | } | 414 | 24.3M | } | 415 | 5.43M | L->getSubLoopsVector().reserve(NumSubloops); | 416 | 5.43M | L->reserveBlocks(NumBlocks); | 417 | 5.43M | } |
|
418 | | |
419 | | /// Populate all loop data in a stable order during a single forward DFS. |
420 | | template <class BlockT, class LoopT> class PopulateLoopsDFS { |
421 | | typedef GraphTraits<BlockT *> BlockTraits; |
422 | | typedef typename BlockTraits::ChildIteratorType SuccIterTy; |
423 | | |
424 | | LoopInfoBase<BlockT, LoopT> *LI; |
425 | | |
426 | | public: |
427 | 12.0M | PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {} llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>*) Line | Count | Source | 427 | 8.47M | PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {} |
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>*) Line | Count | Source | 427 | 3.58M | PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {} |
|
428 | | |
429 | | void traverse(BlockT *EntryBlock); |
430 | | |
431 | | protected: |
432 | | void insertIntoLoop(BlockT *Block); |
433 | | }; |
434 | | |
435 | | /// Top-level driver for the forward DFS within the loop. |
436 | | template <class BlockT, class LoopT> |
437 | 12.0M | void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { |
438 | 12.0M | for (BlockT *BB : post_order(EntryBlock)) |
439 | 82.6M | insertIntoLoop(BB); |
440 | 12.0M | } llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::traverse(llvm::MachineBasicBlock*) Line | Count | Source | 437 | 3.58M | void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { | 438 | 3.58M | for (BlockT *BB : post_order(EntryBlock)) | 439 | 23.7M | insertIntoLoop(BB); | 440 | 3.58M | } |
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::traverse(llvm::BasicBlock*) Line | Count | Source | 437 | 8.47M | void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { | 438 | 8.47M | for (BlockT *BB : post_order(EntryBlock)) | 439 | 58.9M | insertIntoLoop(BB); | 440 | 8.47M | } |
|
441 | | |
442 | | /// Add a single Block to its ancestor loops in PostOrder. If the block is a |
443 | | /// subloop header, add the subloop to its parent in PostOrder, then reverse the |
444 | | /// Block and Subloop vectors of the now complete subloop to achieve RPO. |
445 | | template <class BlockT, class LoopT> |
446 | 82.6M | void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { |
447 | 82.6M | LoopT *Subloop = LI->getLoopFor(Block); |
448 | 82.6M | if (Subloop && 82.6M Block == Subloop->getHeader()23.8M ) { |
449 | 7.59M | // We reach this point once per subloop after processing all the blocks in |
450 | 7.59M | // the subloop. |
451 | 7.59M | if (Subloop->getParentLoop()) |
452 | 2.15M | Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); |
453 | 7.59M | else |
454 | 5.43M | LI->addTopLevelLoop(Subloop); |
455 | 7.59M | |
456 | 7.59M | // For convenience, Blocks and Subloops are inserted in postorder. Reverse |
457 | 7.59M | // the lists, except for the loop header, which is always at the beginning. |
458 | 7.59M | Subloop->reverseBlock(1); |
459 | 7.59M | std::reverse(Subloop->getSubLoopsVector().begin(), |
460 | 7.59M | Subloop->getSubLoopsVector().end()); |
461 | 7.59M | |
462 | 7.59M | Subloop = Subloop->getParentLoop(); |
463 | 7.59M | } |
464 | 107M | for (; Subloop107M ; Subloop = Subloop->getParentLoop()24.6M ) |
465 | 24.6M | Subloop->addBlockEntry(Block); |
466 | 82.6M | } llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop(llvm::BasicBlock*) Line | Count | Source | 446 | 58.9M | void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { | 447 | 58.9M | LoopT *Subloop = LI->getLoopFor(Block); | 448 | 58.9M | if (Subloop && 58.9M Block == Subloop->getHeader()17.1M ) { | 449 | 5.43M | // We reach this point once per subloop after processing all the blocks in | 450 | 5.43M | // the subloop. | 451 | 5.43M | if (Subloop->getParentLoop()) | 452 | 1.53M | Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); | 453 | 5.43M | else | 454 | 3.89M | LI->addTopLevelLoop(Subloop); | 455 | 5.43M | | 456 | 5.43M | // For convenience, Blocks and Subloops are inserted in postorder. Reverse | 457 | 5.43M | // the lists, except for the loop header, which is always at the beginning. | 458 | 5.43M | Subloop->reverseBlock(1); | 459 | 5.43M | std::reverse(Subloop->getSubLoopsVector().begin(), | 460 | 5.43M | Subloop->getSubLoopsVector().end()); | 461 | 5.43M | | 462 | 5.43M | Subloop = Subloop->getParentLoop(); | 463 | 5.43M | } | 464 | 76.6M | for (; Subloop76.6M ; Subloop = Subloop->getParentLoop()17.6M ) | 465 | 17.6M | Subloop->addBlockEntry(Block); | 466 | 58.9M | } |
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::insertIntoLoop(llvm::MachineBasicBlock*) Line | Count | Source | 446 | 23.7M | void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { | 447 | 23.7M | LoopT *Subloop = LI->getLoopFor(Block); | 448 | 23.7M | if (Subloop && 23.7M Block == Subloop->getHeader()6.72M ) { | 449 | 2.15M | // We reach this point once per subloop after processing all the blocks in | 450 | 2.15M | // the subloop. | 451 | 2.15M | if (Subloop->getParentLoop()) | 452 | 618k | Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); | 453 | 2.15M | else | 454 | 1.53M | LI->addTopLevelLoop(Subloop); | 455 | 2.15M | | 456 | 2.15M | // For convenience, Blocks and Subloops are inserted in postorder. Reverse | 457 | 2.15M | // the lists, except for the loop header, which is always at the beginning. | 458 | 2.15M | Subloop->reverseBlock(1); | 459 | 2.15M | std::reverse(Subloop->getSubLoopsVector().begin(), | 460 | 2.15M | Subloop->getSubLoopsVector().end()); | 461 | 2.15M | | 462 | 2.15M | Subloop = Subloop->getParentLoop(); | 463 | 2.15M | } | 464 | 30.6M | for (; Subloop30.6M ; Subloop = Subloop->getParentLoop()6.97M ) | 465 | 6.97M | Subloop->addBlockEntry(Block); | 466 | 23.7M | } |
|
467 | | |
468 | | /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal |
469 | | /// interleaved with backward CFG traversals within each subloop |
470 | | /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so |
471 | | /// this part of the algorithm is linear in the number of CFG edges. Subloop and |
472 | | /// Block vectors are then populated during a single forward CFG traversal |
473 | | /// (PopulateLoopDFS). |
474 | | /// |
475 | | /// During the two CFG traversals each block is seen three times: |
476 | | /// 1) Discovered and mapped by a reverse CFG traversal. |
477 | | /// 2) Visited during a forward DFS CFG traversal. |
478 | | /// 3) Reverse-inserted in the loop in postorder following forward DFS. |
479 | | /// |
480 | | /// The Block vectors are inclusive, so step 3 requires loop-depth number of |
481 | | /// insertions per block. |
482 | | template <class BlockT, class LoopT> |
483 | 12.0M | void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) { |
484 | 12.0M | // Postorder traversal of the dominator tree. |
485 | 12.0M | const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode(); |
486 | 82.6M | for (auto DomNode : post_order(DomRoot)) { |
487 | 82.6M | |
488 | 82.6M | BlockT *Header = DomNode->getBlock(); |
489 | 82.6M | SmallVector<BlockT *, 4> Backedges; |
490 | 82.6M | |
491 | 82.6M | // Check each predecessor of the potential loop header. |
492 | 109M | for (const auto Backedge : children<Inverse<BlockT *>>(Header)) { |
493 | 109M | // If Header dominates predBB, this is a new loop. Collect the backedges. |
494 | 109M | if (DomTree.dominates(Header, Backedge) && |
495 | 109M | DomTree.isReachableFromEntry(Backedge)7.75M ) { |
496 | 7.75M | Backedges.push_back(Backedge); |
497 | 7.75M | } |
498 | 109M | } |
499 | 82.6M | // Perform a backward CFG traversal to discover and map blocks in this loop. |
500 | 82.6M | if (!Backedges.empty()82.6M ) { |
501 | 7.59M | LoopT *L = AllocateLoop(Header); |
502 | 7.59M | discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree); |
503 | 7.59M | } |
504 | 82.6M | } |
505 | 12.0M | // Perform a single forward CFG traversal to populate block and subloop |
506 | 12.0M | // vectors for all loops. |
507 | 12.0M | PopulateLoopsDFS<BlockT, LoopT> DFS(this); |
508 | 12.0M | DFS.traverse(DomRoot->getBlock()); |
509 | 12.0M | } llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&) Line | Count | Source | 483 | 3.58M | void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) { | 484 | 3.58M | // Postorder traversal of the dominator tree. | 485 | 3.58M | const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode(); | 486 | 23.7M | for (auto DomNode : post_order(DomRoot)) { | 487 | 23.7M | | 488 | 23.7M | BlockT *Header = DomNode->getBlock(); | 489 | 23.7M | SmallVector<BlockT *, 4> Backedges; | 490 | 23.7M | | 491 | 23.7M | // Check each predecessor of the potential loop header. | 492 | 30.4M | for (const auto Backedge : children<Inverse<BlockT *>>(Header)) { | 493 | 30.4M | // If Header dominates predBB, this is a new loop. Collect the backedges. | 494 | 30.4M | if (DomTree.dominates(Header, Backedge) && | 495 | 30.4M | DomTree.isReachableFromEntry(Backedge)2.28M ) { | 496 | 2.28M | Backedges.push_back(Backedge); | 497 | 2.28M | } | 498 | 30.4M | } | 499 | 23.7M | // Perform a backward CFG traversal to discover and map blocks in this loop. | 500 | 23.7M | if (!Backedges.empty()23.7M ) { | 501 | 2.15M | LoopT *L = AllocateLoop(Header); | 502 | 2.15M | discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree); | 503 | 2.15M | } | 504 | 23.7M | } | 505 | 3.58M | // Perform a single forward CFG traversal to populate block and subloop | 506 | 3.58M | // vectors for all loops. | 507 | 3.58M | PopulateLoopsDFS<BlockT, LoopT> DFS(this); | 508 | 3.58M | DFS.traverse(DomRoot->getBlock()); | 509 | 3.58M | } |
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&) Line | Count | Source | 483 | 8.47M | void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) { | 484 | 8.47M | // Postorder traversal of the dominator tree. | 485 | 8.47M | const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode(); | 486 | 58.9M | for (auto DomNode : post_order(DomRoot)) { | 487 | 58.9M | | 488 | 58.9M | BlockT *Header = DomNode->getBlock(); | 489 | 58.9M | SmallVector<BlockT *, 4> Backedges; | 490 | 58.9M | | 491 | 58.9M | // Check each predecessor of the potential loop header. | 492 | 79.3M | for (const auto Backedge : children<Inverse<BlockT *>>(Header)) { | 493 | 79.3M | // If Header dominates predBB, this is a new loop. Collect the backedges. | 494 | 79.3M | if (DomTree.dominates(Header, Backedge) && | 495 | 79.3M | DomTree.isReachableFromEntry(Backedge)5.46M ) { | 496 | 5.46M | Backedges.push_back(Backedge); | 497 | 5.46M | } | 498 | 79.3M | } | 499 | 58.9M | // Perform a backward CFG traversal to discover and map blocks in this loop. | 500 | 58.9M | if (!Backedges.empty()58.9M ) { | 501 | 5.43M | LoopT *L = AllocateLoop(Header); | 502 | 5.43M | discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree); | 503 | 5.43M | } | 504 | 58.9M | } | 505 | 8.47M | // Perform a single forward CFG traversal to populate block and subloop | 506 | 8.47M | // vectors for all loops. | 507 | 8.47M | PopulateLoopsDFS<BlockT, LoopT> DFS(this); | 508 | 8.47M | DFS.traverse(DomRoot->getBlock()); | 509 | 8.47M | } |
|
510 | | |
511 | | template <class BlockT, class LoopT> |
512 | 46 | SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() { |
513 | 46 | SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; |
514 | 46 | // The outer-most loop actually goes into the result in the same relative |
515 | 46 | // order as we walk it. But LoopInfo stores the top level loops in reverse |
516 | 46 | // program order so for here we reverse it to get forward program order. |
517 | 46 | // FIXME: If we change the order of LoopInfo we will want to remove the |
518 | 46 | // reverse here. |
519 | 46 | for (LoopT *RootL : reverse(*this)) { |
520 | 46 | assert(PreOrderWorklist.empty() && |
521 | 46 | "Must start with an empty preorder walk worklist."); |
522 | 46 | PreOrderWorklist.push_back(RootL); |
523 | 59 | do { |
524 | 59 | LoopT *L = PreOrderWorklist.pop_back_val(); |
525 | 59 | // Sub-loops are stored in forward program order, but will process the |
526 | 59 | // worklist backwards so append them in reverse order. |
527 | 59 | PreOrderWorklist.append(L->rbegin(), L->rend()); |
528 | 59 | PreOrderLoops.push_back(L); |
529 | 59 | } while (!PreOrderWorklist.empty()); |
530 | 46 | } |
531 | 46 | |
532 | 46 | return PreOrderLoops; |
533 | 46 | } Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInPreorder() llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInPreorder() Line | Count | Source | 512 | 46 | SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() { | 513 | 46 | SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; | 514 | 46 | // The outer-most loop actually goes into the result in the same relative | 515 | 46 | // order as we walk it. But LoopInfo stores the top level loops in reverse | 516 | 46 | // program order so for here we reverse it to get forward program order. | 517 | 46 | // FIXME: If we change the order of LoopInfo we will want to remove the | 518 | 46 | // reverse here. | 519 | 46 | for (LoopT *RootL : reverse(*this)) { | 520 | 46 | assert(PreOrderWorklist.empty() && | 521 | 46 | "Must start with an empty preorder walk worklist."); | 522 | 46 | PreOrderWorklist.push_back(RootL); | 523 | 59 | do { | 524 | 59 | LoopT *L = PreOrderWorklist.pop_back_val(); | 525 | 59 | // Sub-loops are stored in forward program order, but will process the | 526 | 59 | // worklist backwards so append them in reverse order. | 527 | 59 | PreOrderWorklist.append(L->rbegin(), L->rend()); | 528 | 59 | PreOrderLoops.push_back(L); | 529 | 59 | } while (!PreOrderWorklist.empty()); | 530 | 46 | } | 531 | 46 | | 532 | 46 | return PreOrderLoops; | 533 | 46 | } |
|
534 | | |
535 | | template <class BlockT, class LoopT> |
536 | | SmallVector<LoopT *, 4> |
537 | 245 | LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() { |
538 | 245 | SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; |
539 | 245 | // The outer-most loop actually goes into the result in the same relative |
540 | 245 | // order as we walk it. LoopInfo stores the top level loops in reverse |
541 | 245 | // program order so we walk in order here. |
542 | 245 | // FIXME: If we change the order of LoopInfo we will want to add a reverse |
543 | 245 | // here. |
544 | 230 | for (LoopT *RootL : *this) { |
545 | 230 | assert(PreOrderWorklist.empty() && |
546 | 230 | "Must start with an empty preorder walk worklist."); |
547 | 230 | PreOrderWorklist.push_back(RootL); |
548 | 302 | do { |
549 | 302 | LoopT *L = PreOrderWorklist.pop_back_val(); |
550 | 302 | // Sub-loops are stored in forward program order, but will process the |
551 | 302 | // worklist backwards so we can just append them in order. |
552 | 302 | PreOrderWorklist.append(L->begin(), L->end()); |
553 | 302 | PreOrderLoops.push_back(L); |
554 | 302 | } while (!PreOrderWorklist.empty()); |
555 | 230 | } |
556 | 245 | |
557 | 245 | return PreOrderLoops; |
558 | 245 | } llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInReverseSiblingPreorder() Line | Count | Source | 537 | 245 | LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() { | 538 | 245 | SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; | 539 | 245 | // The outer-most loop actually goes into the result in the same relative | 540 | 245 | // order as we walk it. LoopInfo stores the top level loops in reverse | 541 | 245 | // program order so we walk in order here. | 542 | 245 | // FIXME: If we change the order of LoopInfo we will want to add a reverse | 543 | 245 | // here. | 544 | 230 | for (LoopT *RootL : *this) { | 545 | 230 | assert(PreOrderWorklist.empty() && | 546 | 230 | "Must start with an empty preorder walk worklist."); | 547 | 230 | PreOrderWorklist.push_back(RootL); | 548 | 302 | do { | 549 | 302 | LoopT *L = PreOrderWorklist.pop_back_val(); | 550 | 302 | // Sub-loops are stored in forward program order, but will process the | 551 | 302 | // worklist backwards so we can just append them in order. | 552 | 302 | PreOrderWorklist.append(L->begin(), L->end()); | 553 | 302 | PreOrderLoops.push_back(L); | 554 | 302 | } while (!PreOrderWorklist.empty()); | 555 | 230 | } | 556 | 245 | | 557 | 245 | return PreOrderLoops; | 558 | 245 | } |
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInReverseSiblingPreorder() |
559 | | |
560 | | // Debugging |
561 | | template <class BlockT, class LoopT> |
562 | 7 | void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { |
563 | 16 | for (unsigned i = 0; i < TopLevelLoops.size()16 ; ++i9 ) |
564 | 9 | TopLevelLoops[i]->print(OS); |
565 | | #if 0 |
566 | | for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), |
567 | | E = BBMap.end(); I != E; ++I) |
568 | | OS << "BB '" << I->first->getName() << "' level = " |
569 | | << I->second->getLoopDepth() << "\n"; |
570 | | #endif |
571 | | } llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&) const Line | Count | Source | 562 | 7 | void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { | 563 | 16 | for (unsigned i = 0; i < TopLevelLoops.size()16 ; ++i9 ) | 564 | 9 | TopLevelLoops[i]->print(OS); | 565 | | #if 0 | 566 | | for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), | 567 | | E = BBMap.end(); I != E; ++I) | 568 | | OS << "BB '" << I->first->getName() << "' level = " | 569 | | << I->second->getLoopDepth() << "\n"; | 570 | | #endif | 571 | | } |
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::print(llvm::raw_ostream&) const |
572 | | |
573 | | template <typename T> |
574 | | bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) { |
575 | | std::sort(BB1.begin(), BB1.end()); |
576 | | std::sort(BB2.begin(), BB2.end()); |
577 | | return BB1 == BB2; |
578 | | } |
579 | | |
580 | | template <class BlockT, class LoopT> |
581 | | void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders, |
582 | | const LoopInfoBase<BlockT, LoopT> &LI, |
583 | | const LoopT &L) { |
584 | | LoopHeaders[L.getHeader()] = &L; |
585 | | for (LoopT *SL : L) |
586 | | addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL); |
587 | | } |
588 | | |
589 | | #ifndef NDEBUG |
590 | | template <class BlockT, class LoopT> |
591 | | static void compareLoops(const LoopT *L, const LoopT *OtherL, |
592 | | DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) { |
593 | | BlockT *H = L->getHeader(); |
594 | | BlockT *OtherH = OtherL->getHeader(); |
595 | | assert(H == OtherH && |
596 | | "Mismatched headers even though found in the same map entry!"); |
597 | | |
598 | | assert(L->getLoopDepth() == OtherL->getLoopDepth() && |
599 | | "Mismatched loop depth!"); |
600 | | const LoopT *ParentL = L, *OtherParentL = OtherL; |
601 | | do { |
602 | | assert(ParentL->getHeader() == OtherParentL->getHeader() && |
603 | | "Mismatched parent loop headers!"); |
604 | | ParentL = ParentL->getParentLoop(); |
605 | | OtherParentL = OtherParentL->getParentLoop(); |
606 | | } while (ParentL); |
607 | | |
608 | | for (const LoopT *SubL : *L) { |
609 | | BlockT *SubH = SubL->getHeader(); |
610 | | const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH); |
611 | | assert(OtherSubL && "Inner loop is missing in computed loop info!"); |
612 | | OtherLoopHeaders.erase(SubH); |
613 | | compareLoops(SubL, OtherSubL, OtherLoopHeaders); |
614 | | } |
615 | | |
616 | | std::vector<BlockT *> BBs = L->getBlocks(); |
617 | | std::vector<BlockT *> OtherBBs = OtherL->getBlocks(); |
618 | | assert(compareVectors(BBs, OtherBBs) && |
619 | | "Mismatched basic blocks in the loops!"); |
620 | | } |
621 | | #endif |
622 | | |
623 | | template <class BlockT, class LoopT> |
624 | | void LoopInfoBase<BlockT, LoopT>::verify( |
625 | 28 | const DomTreeBase<BlockT> &DomTree) const { |
626 | 28 | DenseSet<const LoopT *> Loops; |
627 | 59 | for (iterator I = begin(), E = end(); I != E59 ; ++I31 ) { |
628 | 31 | assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); |
629 | 31 | (*I)->verifyLoopNest(&Loops); |
630 | 31 | } |
631 | 28 | |
632 | 28 | // Verify that blocks are mapped to valid loops. |
633 | | #ifndef NDEBUG |
634 | | for (auto &Entry : BBMap) { |
635 | | const BlockT *BB = Entry.first; |
636 | | LoopT *L = Entry.second; |
637 | | assert(Loops.count(L) && "orphaned loop"); |
638 | | assert(L->contains(BB) && "orphaned block"); |
639 | | } |
640 | | |
641 | | // Recompute LoopInfo to verify loops structure. |
642 | | LoopInfoBase<BlockT, LoopT> OtherLI; |
643 | | OtherLI.analyze(DomTree); |
644 | | |
645 | | // Build a map we can use to move from our LI to the computed one. This |
646 | | // allows us to ignore the particular order in any layer of the loop forest |
647 | | // while still comparing the structure. |
648 | | DenseMap<BlockT *, const LoopT *> OtherLoopHeaders; |
649 | | for (LoopT *L : OtherLI) |
650 | | addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L); |
651 | | |
652 | | // Walk the top level loops and ensure there is a corresponding top-level |
653 | | // loop in the computed version and then recursively compare those loop |
654 | | // nests. |
655 | | for (LoopT *L : *this) { |
656 | | BlockT *Header = L->getHeader(); |
657 | | const LoopT *OtherL = OtherLoopHeaders.lookup(Header); |
658 | | assert(OtherL && "Top level loop is missing in computed loop info!"); |
659 | | // Now that we've matched this loop, erase its header from the map. |
660 | | OtherLoopHeaders.erase(Header); |
661 | | // And recursively compare these loops. |
662 | | compareLoops(L, OtherL, OtherLoopHeaders); |
663 | | } |
664 | | |
665 | | // Any remaining entries in the map are loops which were found when computing |
666 | | // a fresh LoopInfo but not present in the current one. |
667 | | if (!OtherLoopHeaders.empty()) { |
668 | | for (const auto &HeaderAndLoop : OtherLoopHeaders) |
669 | | dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n"; |
670 | | llvm_unreachable("Found new loops when recomputing LoopInfo!"); |
671 | | } |
672 | | #endif |
673 | | } llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::verify(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&) const Line | Count | Source | 625 | 28 | const DomTreeBase<BlockT> &DomTree) const { | 626 | 28 | DenseSet<const LoopT *> Loops; | 627 | 59 | for (iterator I = begin(), E = end(); I != E59 ; ++I31 ) { | 628 | 31 | assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); | 629 | 31 | (*I)->verifyLoopNest(&Loops); | 630 | 31 | } | 631 | 28 | | 632 | 28 | // Verify that blocks are mapped to valid loops. | 633 | | #ifndef NDEBUG | 634 | | for (auto &Entry : BBMap) { | 635 | | const BlockT *BB = Entry.first; | 636 | | LoopT *L = Entry.second; | 637 | | assert(Loops.count(L) && "orphaned loop"); | 638 | | assert(L->contains(BB) && "orphaned block"); | 639 | | } | 640 | | | 641 | | // Recompute LoopInfo to verify loops structure. | 642 | | LoopInfoBase<BlockT, LoopT> OtherLI; | 643 | | OtherLI.analyze(DomTree); | 644 | | | 645 | | // Build a map we can use to move from our LI to the computed one. This | 646 | | // allows us to ignore the particular order in any layer of the loop forest | 647 | | // while still comparing the structure. | 648 | | DenseMap<BlockT *, const LoopT *> OtherLoopHeaders; | 649 | | for (LoopT *L : OtherLI) | 650 | | addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L); | 651 | | | 652 | | // Walk the top level loops and ensure there is a corresponding top-level | 653 | | // loop in the computed version and then recursively compare those loop | 654 | | // nests. | 655 | | for (LoopT *L : *this) { | 656 | | BlockT *Header = L->getHeader(); | 657 | | const LoopT *OtherL = OtherLoopHeaders.lookup(Header); | 658 | | assert(OtherL && "Top level loop is missing in computed loop info!"); | 659 | | // Now that we've matched this loop, erase its header from the map. | 660 | | OtherLoopHeaders.erase(Header); | 661 | | // And recursively compare these loops. | 662 | | compareLoops(L, OtherL, OtherLoopHeaders); | 663 | | } | 664 | | | 665 | | // Any remaining entries in the map are loops which were found when computing | 666 | | // a fresh LoopInfo but not present in the current one. | 667 | | if (!OtherLoopHeaders.empty()) { | 668 | | for (const auto &HeaderAndLoop : OtherLoopHeaders) | 669 | | dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n"; | 670 | | llvm_unreachable("Found new loops when recomputing LoopInfo!"); | 671 | | } | 672 | | #endif | 673 | | } |
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verify(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&) const |
674 | | |
675 | | } // End llvm namespace |
676 | | |
677 | | #endif |