/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/CodeGen/Utils.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===--- Utils.cpp - Utility functions for the code generation --*- C++ -*-===// |
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 contains utility functions for the code generation. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "polly/CodeGen/Utils.h" |
14 | | #include "polly/CodeGen/IRBuilder.h" |
15 | | #include "polly/ScopInfo.h" |
16 | | #include "llvm/Analysis/LoopInfo.h" |
17 | | #include "llvm/Analysis/RegionInfo.h" |
18 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
19 | | |
20 | | using namespace llvm; |
21 | | |
22 | | // Alternative to llvm::SplitCriticalEdge. |
23 | | // |
24 | | // Creates a new block which branches to Succ. The edge to split is redirected |
25 | | // to the new block. |
26 | | // |
27 | | // The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is |
28 | | // not critical. |
29 | | // The issue with llvm::SplitEdge is that it does not always create the middle |
30 | | // block, but reuses Prev/Succ if it can. We always want a new middle block. |
31 | | static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ, |
32 | | const char *Suffix, DominatorTree *DT, |
33 | 915 | LoopInfo *LI, RegionInfo *RI) { |
34 | 915 | assert(Prev && Succ); |
35 | 915 | |
36 | 915 | // Before: |
37 | 915 | // \ / / // |
38 | 915 | // Prev / // |
39 | 915 | // | \___/ // |
40 | 915 | // | ___ // |
41 | 915 | // | / \ // |
42 | 915 | // Succ \ // |
43 | 915 | // / \ \ // |
44 | 915 | |
45 | 915 | // The algorithm to update DominatorTree and LoopInfo of |
46 | 915 | // llvm::SplitCriticalEdge is more efficient than |
47 | 915 | // llvm::SplitBlockPredecessors, which is more general. In the future we might |
48 | 915 | // either modify llvm::SplitCriticalEdge to allow skipping the critical edge |
49 | 915 | // check; or Copy&Pase it here. |
50 | 915 | BasicBlock *MiddleBlock = SplitBlockPredecessors( |
51 | 915 | Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI); |
52 | 915 | |
53 | 915 | if (RI) { |
54 | 915 | Region *PrevRegion = RI->getRegionFor(Prev); |
55 | 915 | Region *SuccRegion = RI->getRegionFor(Succ); |
56 | 915 | if (PrevRegion->contains(MiddleBlock)) { |
57 | 915 | RI->setRegionFor(MiddleBlock, PrevRegion); |
58 | 915 | } else { |
59 | 0 | RI->setRegionFor(MiddleBlock, SuccRegion); |
60 | 0 | } |
61 | 915 | } |
62 | 915 | |
63 | 915 | // After: |
64 | 915 | // \ / / // |
65 | 915 | // Prev / // |
66 | 915 | // | \___/ // |
67 | 915 | // | // |
68 | 915 | // MiddleBlock // |
69 | 915 | // | ___ // |
70 | 915 | // | / \ // |
71 | 915 | // Succ \ // |
72 | 915 | // / \ \ // |
73 | 915 | |
74 | 915 | return MiddleBlock; |
75 | 915 | } |
76 | | |
77 | | std::pair<polly::BBPair, BranchInst *> |
78 | | polly::executeScopConditionally(Scop &S, Value *RTC, DominatorTree &DT, |
79 | 305 | RegionInfo &RI, LoopInfo &LI) { |
80 | 305 | Region &R = S.getRegion(); |
81 | 305 | PollyIRBuilder Builder(S.getEntry()); |
82 | 305 | |
83 | 305 | // Before: |
84 | 305 | // |
85 | 305 | // \ / // |
86 | 305 | // EnteringBB // |
87 | 305 | // _____|_____ // |
88 | 305 | // / EntryBB \ // |
89 | 305 | // | (region) | // |
90 | 305 | // \_ExitingBB_/ // |
91 | 305 | // | // |
92 | 305 | // ExitBB // |
93 | 305 | // / \ // |
94 | 305 | |
95 | 305 | // Create a fork block. |
96 | 305 | BasicBlock *EnteringBB = S.getEnteringBlock(); |
97 | 305 | BasicBlock *EntryBB = S.getEntry(); |
98 | 305 | assert(EnteringBB && "Must be a simple region"); |
99 | 305 | BasicBlock *SplitBlock = |
100 | 305 | splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI); |
101 | 305 | SplitBlock->setName("polly.split_new_and_old"); |
102 | 305 | |
103 | 305 | // If EntryBB is the exit block of the region that includes Prev, exclude |
104 | 305 | // SplitBlock from that region by making it itself the exit block. This is |
105 | 305 | // trivially possible because there is just one edge to EnteringBB. |
106 | 305 | // This is necessary because we will add an outgoing edge from SplitBlock, |
107 | 305 | // which would violate the single exit block requirement of PrevRegion. |
108 | 305 | Region *PrevRegion = RI.getRegionFor(EnteringBB); |
109 | 308 | while (PrevRegion->getExit() == EntryBB) { |
110 | 3 | PrevRegion->replaceExit(SplitBlock); |
111 | 3 | PrevRegion = PrevRegion->getParent(); |
112 | 3 | } |
113 | 305 | RI.setRegionFor(SplitBlock, PrevRegion); |
114 | 305 | |
115 | 305 | // Create a join block |
116 | 305 | BasicBlock *ExitingBB = S.getExitingBlock(); |
117 | 305 | BasicBlock *ExitBB = S.getExit(); |
118 | 305 | assert(ExitingBB && "Must be a simple region"); |
119 | 305 | BasicBlock *MergeBlock = |
120 | 305 | splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI); |
121 | 305 | MergeBlock->setName("polly.merge_new_and_old"); |
122 | 305 | |
123 | 305 | // Exclude the join block from the region. |
124 | 305 | R.replaceExitRecursive(MergeBlock); |
125 | 305 | RI.setRegionFor(MergeBlock, R.getParent()); |
126 | 305 | |
127 | 305 | // \ / // |
128 | 305 | // EnteringBB // |
129 | 305 | // | // |
130 | 305 | // SplitBlock // |
131 | 305 | // _____|_____ // |
132 | 305 | // / EntryBB \ // |
133 | 305 | // | (region) | // |
134 | 305 | // \_ExitingBB_/ // |
135 | 305 | // | // |
136 | 305 | // MergeBlock // |
137 | 305 | // | // |
138 | 305 | // ExitBB // |
139 | 305 | // / \ // |
140 | 305 | |
141 | 305 | // Create the start and exiting block. |
142 | 305 | Function *F = SplitBlock->getParent(); |
143 | 305 | BasicBlock *StartBlock = |
144 | 305 | BasicBlock::Create(F->getContext(), "polly.start", F); |
145 | 305 | BasicBlock *ExitingBlock = |
146 | 305 | BasicBlock::Create(F->getContext(), "polly.exiting", F); |
147 | 305 | SplitBlock->getTerminator()->eraseFromParent(); |
148 | 305 | Builder.SetInsertPoint(SplitBlock); |
149 | 305 | BranchInst *CondBr = Builder.CreateCondBr(RTC, StartBlock, S.getEntry()); |
150 | 305 | |
151 | 305 | if (Loop *L = LI.getLoopFor(SplitBlock)) { |
152 | 26 | L->addBasicBlockToLoop(StartBlock, LI); |
153 | 26 | L->addBasicBlockToLoop(ExitingBlock, LI); |
154 | 26 | } |
155 | 305 | DT.addNewBlock(StartBlock, SplitBlock); |
156 | 305 | DT.addNewBlock(ExitingBlock, StartBlock); |
157 | 305 | RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock)); |
158 | 305 | RI.setRegionFor(ExitingBlock, RI.getRegionFor(SplitBlock)); |
159 | 305 | |
160 | 305 | // \ / // |
161 | 305 | // EnteringBB // |
162 | 305 | // | // |
163 | 305 | // SplitBlock---------\ // |
164 | 305 | // _____|_____ | // |
165 | 305 | // / EntryBB \ StartBlock // |
166 | 305 | // | (region) | | // |
167 | 305 | // \_ExitingBB_/ ExitingBlock // |
168 | 305 | // | // |
169 | 305 | // MergeBlock // |
170 | 305 | // | // |
171 | 305 | // ExitBB // |
172 | 305 | // / \ // |
173 | 305 | |
174 | 305 | // Connect start block to exiting block. |
175 | 305 | Builder.SetInsertPoint(StartBlock); |
176 | 305 | Builder.CreateBr(ExitingBlock); |
177 | 305 | DT.changeImmediateDominator(ExitingBlock, StartBlock); |
178 | 305 | |
179 | 305 | // Connect exiting block to join block. |
180 | 305 | Builder.SetInsertPoint(ExitingBlock); |
181 | 305 | Builder.CreateBr(MergeBlock); |
182 | 305 | DT.changeImmediateDominator(MergeBlock, SplitBlock); |
183 | 305 | |
184 | 305 | // \ / // |
185 | 305 | // EnteringBB // |
186 | 305 | // | // |
187 | 305 | // SplitBlock---------\ // |
188 | 305 | // _____|_____ | // |
189 | 305 | // / EntryBB \ StartBlock // |
190 | 305 | // | (region) | | // |
191 | 305 | // \_ExitingBB_/ ExitingBlock // |
192 | 305 | // | | // |
193 | 305 | // MergeBlock---------/ // |
194 | 305 | // | // |
195 | 305 | // ExitBB // |
196 | 305 | // / \ // |
197 | 305 | // |
198 | 305 | |
199 | 305 | // Split the edge between SplitBlock and EntryBB, to avoid a critical edge. |
200 | 305 | splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI); |
201 | 305 | |
202 | 305 | // \ / // |
203 | 305 | // EnteringBB // |
204 | 305 | // | // |
205 | 305 | // SplitBlock---------\ // |
206 | 305 | // | | // |
207 | 305 | // PreEntryBB | // |
208 | 305 | // _____|_____ | // |
209 | 305 | // / EntryBB \ StartBlock // |
210 | 305 | // | (region) | | // |
211 | 305 | // \_ExitingBB_/ ExitingBlock // |
212 | 305 | // | | // |
213 | 305 | // MergeBlock---------/ // |
214 | 305 | // | // |
215 | 305 | // ExitBB // |
216 | 305 | // / \ // |
217 | 305 | |
218 | 305 | return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr); |
219 | 305 | } |