/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- StructurizeCFG.cpp -------------------------------------------------===// |
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 | | #include "llvm/ADT/DenseMap.h" |
10 | | #include "llvm/ADT/MapVector.h" |
11 | | #include "llvm/ADT/PostOrderIterator.h" |
12 | | #include "llvm/ADT/STLExtras.h" |
13 | | #include "llvm/ADT/SmallPtrSet.h" |
14 | | #include "llvm/ADT/SmallVector.h" |
15 | | #include "llvm/Analysis/InstructionSimplify.h" |
16 | | #include "llvm/Analysis/LegacyDivergenceAnalysis.h" |
17 | | #include "llvm/Analysis/LoopInfo.h" |
18 | | #include "llvm/Analysis/RegionInfo.h" |
19 | | #include "llvm/Analysis/RegionIterator.h" |
20 | | #include "llvm/Analysis/RegionPass.h" |
21 | | #include "llvm/IR/Argument.h" |
22 | | #include "llvm/IR/BasicBlock.h" |
23 | | #include "llvm/IR/CFG.h" |
24 | | #include "llvm/IR/Constant.h" |
25 | | #include "llvm/IR/Constants.h" |
26 | | #include "llvm/IR/Dominators.h" |
27 | | #include "llvm/IR/Function.h" |
28 | | #include "llvm/IR/InstrTypes.h" |
29 | | #include "llvm/IR/Instruction.h" |
30 | | #include "llvm/IR/Instructions.h" |
31 | | #include "llvm/IR/Metadata.h" |
32 | | #include "llvm/IR/PatternMatch.h" |
33 | | #include "llvm/IR/Type.h" |
34 | | #include "llvm/IR/Use.h" |
35 | | #include "llvm/IR/User.h" |
36 | | #include "llvm/IR/Value.h" |
37 | | #include "llvm/Pass.h" |
38 | | #include "llvm/Support/Casting.h" |
39 | | #include "llvm/Support/Debug.h" |
40 | | #include "llvm/Support/ErrorHandling.h" |
41 | | #include "llvm/Support/raw_ostream.h" |
42 | | #include "llvm/Transforms/Scalar.h" |
43 | | #include "llvm/Transforms/Utils.h" |
44 | | #include "llvm/Transforms/Utils/SSAUpdater.h" |
45 | | #include <algorithm> |
46 | | #include <cassert> |
47 | | #include <utility> |
48 | | |
49 | | using namespace llvm; |
50 | | using namespace llvm::PatternMatch; |
51 | | |
52 | | #define DEBUG_TYPE "structurizecfg" |
53 | | |
54 | | // The name for newly created blocks. |
55 | | static const char *const FlowBlockName = "Flow"; |
56 | | |
57 | | namespace { |
58 | | |
59 | | static cl::opt<bool> ForceSkipUniformRegions( |
60 | | "structurizecfg-skip-uniform-regions", |
61 | | cl::Hidden, |
62 | | cl::desc("Force whether the StructurizeCFG pass skips uniform regions"), |
63 | | cl::init(false)); |
64 | | |
65 | | static cl::opt<bool> |
66 | | RelaxedUniformRegions("structurizecfg-relaxed-uniform-regions", cl::Hidden, |
67 | | cl::desc("Allow relaxed uniform region checks"), |
68 | | cl::init(false)); |
69 | | |
70 | | // Definition of the complex types used in this pass. |
71 | | |
72 | | using BBValuePair = std::pair<BasicBlock *, Value *>; |
73 | | |
74 | | using RNVector = SmallVector<RegionNode *, 8>; |
75 | | using BBVector = SmallVector<BasicBlock *, 8>; |
76 | | using BranchVector = SmallVector<BranchInst *, 8>; |
77 | | using BBValueVector = SmallVector<BBValuePair, 2>; |
78 | | |
79 | | using BBSet = SmallPtrSet<BasicBlock *, 8>; |
80 | | |
81 | | using PhiMap = MapVector<PHINode *, BBValueVector>; |
82 | | using BB2BBVecMap = MapVector<BasicBlock *, BBVector>; |
83 | | |
84 | | using BBPhiMap = DenseMap<BasicBlock *, PhiMap>; |
85 | | using BBPredicates = DenseMap<BasicBlock *, Value *>; |
86 | | using PredMap = DenseMap<BasicBlock *, BBPredicates>; |
87 | | using BB2BBMap = DenseMap<BasicBlock *, BasicBlock *>; |
88 | | |
89 | | /// Finds the nearest common dominator of a set of BasicBlocks. |
90 | | /// |
91 | | /// For every BB you add to the set, you can specify whether we "remember" the |
92 | | /// block. When you get the common dominator, you can also ask whether it's one |
93 | | /// of the blocks we remembered. |
94 | | class NearestCommonDominator { |
95 | | DominatorTree *DT; |
96 | | BasicBlock *Result = nullptr; |
97 | | bool ResultIsRemembered = false; |
98 | | |
99 | | /// Add BB to the resulting dominator. |
100 | 6.01k | void addBlock(BasicBlock *BB, bool Remember) { |
101 | 6.01k | if (!Result) { |
102 | 3.01k | Result = BB; |
103 | 3.01k | ResultIsRemembered = Remember; |
104 | 3.01k | return; |
105 | 3.01k | } |
106 | 2.99k | |
107 | 2.99k | BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB); |
108 | 2.99k | if (NewResult != Result) |
109 | 939 | ResultIsRemembered = false; |
110 | 2.99k | if (NewResult == BB) |
111 | 782 | ResultIsRemembered |= Remember; |
112 | 2.99k | Result = NewResult; |
113 | 2.99k | } |
114 | | |
115 | | public: |
116 | 3.01k | explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {} |
117 | | |
118 | 3.01k | void addBlock(BasicBlock *BB) { |
119 | 3.01k | addBlock(BB, /* Remember = */ false); |
120 | 3.01k | } |
121 | | |
122 | 2.99k | void addAndRememberBlock(BasicBlock *BB) { |
123 | 2.99k | addBlock(BB, /* Remember = */ true); |
124 | 2.99k | } |
125 | | |
126 | | /// Get the nearest common dominator of all the BBs added via addBlock() and |
127 | | /// addAndRememberBlock(). |
128 | 1.40k | BasicBlock *result() { return Result; } |
129 | | |
130 | | /// Is the BB returned by getResult() one of the blocks we added to the set |
131 | | /// with addAndRememberBlock()? |
132 | 2.18k | bool resultIsRememberedBlock() { return ResultIsRemembered; } |
133 | | }; |
134 | | |
135 | | /// Transforms the control flow graph on one single entry/exit region |
136 | | /// at a time. |
137 | | /// |
138 | | /// After the transform all "If"/"Then"/"Else" style control flow looks like |
139 | | /// this: |
140 | | /// |
141 | | /// \verbatim |
142 | | /// 1 |
143 | | /// || |
144 | | /// | | |
145 | | /// 2 | |
146 | | /// | / |
147 | | /// |/ |
148 | | /// 3 |
149 | | /// || Where: |
150 | | /// | | 1 = "If" block, calculates the condition |
151 | | /// 4 | 2 = "Then" subregion, runs if the condition is true |
152 | | /// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow |
153 | | /// |/ 4 = "Else" optional subregion, runs if the condition is false |
154 | | /// 5 5 = "End" block, also rejoins the control flow |
155 | | /// \endverbatim |
156 | | /// |
157 | | /// Control flow is expressed as a branch where the true exit goes into the |
158 | | /// "Then"/"Else" region, while the false exit skips the region |
159 | | /// The condition for the optional "Else" region is expressed as a PHI node. |
160 | | /// The incoming values of the PHI node are true for the "If" edge and false |
161 | | /// for the "Then" edge. |
162 | | /// |
163 | | /// Additionally to that even complicated loops look like this: |
164 | | /// |
165 | | /// \verbatim |
166 | | /// 1 |
167 | | /// || |
168 | | /// | | |
169 | | /// 2 ^ Where: |
170 | | /// | / 1 = "Entry" block |
171 | | /// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block |
172 | | /// 3 3 = "Flow" block, with back edge to entry block |
173 | | /// | |
174 | | /// \endverbatim |
175 | | /// |
176 | | /// The back edge of the "Flow" block is always on the false side of the branch |
177 | | /// while the true side continues the general flow. So the loop condition |
178 | | /// consist of a network of PHI nodes where the true incoming values expresses |
179 | | /// breaks and the false values expresses continue states. |
180 | | class StructurizeCFG : public RegionPass { |
181 | | bool SkipUniformRegions; |
182 | | |
183 | | Type *Boolean; |
184 | | ConstantInt *BoolTrue; |
185 | | ConstantInt *BoolFalse; |
186 | | UndefValue *BoolUndef; |
187 | | |
188 | | Function *Func; |
189 | | Region *ParentRegion; |
190 | | |
191 | | LegacyDivergenceAnalysis *DA; |
192 | | DominatorTree *DT; |
193 | | LoopInfo *LI; |
194 | | |
195 | | SmallVector<RegionNode *, 8> Order; |
196 | | BBSet Visited; |
197 | | |
198 | | BBPhiMap DeletedPhis; |
199 | | BB2BBVecMap AddedPhis; |
200 | | |
201 | | PredMap Predicates; |
202 | | BranchVector Conditions; |
203 | | |
204 | | BB2BBMap Loops; |
205 | | PredMap LoopPreds; |
206 | | BranchVector LoopConds; |
207 | | |
208 | | RegionNode *PrevNode; |
209 | | |
210 | | void orderNodes(); |
211 | | |
212 | | Loop *getAdjustedLoop(RegionNode *RN); |
213 | | unsigned getAdjustedLoopDepth(RegionNode *RN); |
214 | | |
215 | | void analyzeLoops(RegionNode *N); |
216 | | |
217 | | Value *invert(Value *Condition); |
218 | | |
219 | | Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert); |
220 | | |
221 | | void gatherPredicates(RegionNode *N); |
222 | | |
223 | | void collectInfos(); |
224 | | |
225 | | void insertConditions(bool Loops); |
226 | | |
227 | | void delPhiValues(BasicBlock *From, BasicBlock *To); |
228 | | |
229 | | void addPhiValues(BasicBlock *From, BasicBlock *To); |
230 | | |
231 | | void setPhiValues(); |
232 | | |
233 | | void killTerminator(BasicBlock *BB); |
234 | | |
235 | | void changeExit(RegionNode *Node, BasicBlock *NewExit, |
236 | | bool IncludeDominator); |
237 | | |
238 | | BasicBlock *getNextFlow(BasicBlock *Dominator); |
239 | | |
240 | | BasicBlock *needPrefix(bool NeedEmpty); |
241 | | |
242 | | BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed); |
243 | | |
244 | | void setPrevNode(BasicBlock *BB); |
245 | | |
246 | | bool dominatesPredicates(BasicBlock *BB, RegionNode *Node); |
247 | | |
248 | | bool isPredictableTrue(RegionNode *Node); |
249 | | |
250 | | void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd); |
251 | | |
252 | | void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd); |
253 | | |
254 | | void createFlow(); |
255 | | |
256 | | void rebuildSSA(); |
257 | | |
258 | | public: |
259 | | static char ID; |
260 | | |
261 | | explicit StructurizeCFG(bool SkipUniformRegions_ = false) |
262 | | : RegionPass(ID), |
263 | 2.74k | SkipUniformRegions(SkipUniformRegions_) { |
264 | 2.74k | if (ForceSkipUniformRegions.getNumOccurrences()) |
265 | 1 | SkipUniformRegions = ForceSkipUniformRegions.getValue(); |
266 | 2.74k | initializeStructurizeCFGPass(*PassRegistry::getPassRegistry()); |
267 | 2.74k | } |
268 | | |
269 | | bool doInitialization(Region *R, RGPassManager &RGM) override; |
270 | | |
271 | | bool runOnRegion(Region *R, RGPassManager &RGM) override; |
272 | | |
273 | 0 | StringRef getPassName() const override { return "Structurize control flow"; } |
274 | | |
275 | 2.72k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
276 | 2.72k | if (SkipUniformRegions) |
277 | 2.42k | AU.addRequired<LegacyDivergenceAnalysis>(); |
278 | 2.72k | AU.addRequiredID(LowerSwitchID); |
279 | 2.72k | AU.addRequired<DominatorTreeWrapperPass>(); |
280 | 2.72k | AU.addRequired<LoopInfoWrapperPass>(); |
281 | 2.72k | |
282 | 2.72k | AU.addPreserved<DominatorTreeWrapperPass>(); |
283 | 2.72k | RegionPass::getAnalysisUsage(AU); |
284 | 2.72k | } |
285 | | }; |
286 | | |
287 | | } // end anonymous namespace |
288 | | |
289 | | char StructurizeCFG::ID = 0; |
290 | | |
291 | 36.0k | INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", |
292 | 36.0k | false, false) |
293 | 36.0k | INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis) |
294 | 36.0k | INITIALIZE_PASS_DEPENDENCY(LowerSwitch) |
295 | 36.0k | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
296 | 36.0k | INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) |
297 | 36.0k | INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG", |
298 | | false, false) |
299 | | |
300 | | /// Initialize the types and constants used in the pass |
301 | 28.9k | bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) { |
302 | 28.9k | LLVMContext &Context = R->getEntry()->getContext(); |
303 | 28.9k | |
304 | 28.9k | Boolean = Type::getInt1Ty(Context); |
305 | 28.9k | BoolTrue = ConstantInt::getTrue(Context); |
306 | 28.9k | BoolFalse = ConstantInt::getFalse(Context); |
307 | 28.9k | BoolUndef = UndefValue::get(Boolean); |
308 | 28.9k | |
309 | 28.9k | return false; |
310 | 28.9k | } |
311 | | |
312 | | /// Use the exit block to determine the loop if RN is a SubRegion. |
313 | 3.62k | Loop *StructurizeCFG::getAdjustedLoop(RegionNode *RN) { |
314 | 3.62k | if (RN->isSubRegion()) { |
315 | 244 | Region *SubRegion = RN->getNodeAs<Region>(); |
316 | 244 | return LI->getLoopFor(SubRegion->getExit()); |
317 | 244 | } |
318 | 3.37k | |
319 | 3.37k | return LI->getLoopFor(RN->getEntry()); |
320 | 3.37k | } |
321 | | |
322 | | /// Use the exit block to determine the loop depth if RN is a SubRegion. |
323 | 1.81k | unsigned StructurizeCFG::getAdjustedLoopDepth(RegionNode *RN) { |
324 | 1.81k | if (RN->isSubRegion()) { |
325 | 122 | Region *SubR = RN->getNodeAs<Region>(); |
326 | 122 | return LI->getLoopDepth(SubR->getExit()); |
327 | 122 | } |
328 | 1.68k | |
329 | 1.68k | return LI->getLoopDepth(RN->getEntry()); |
330 | 1.68k | } |
331 | | |
332 | | /// Build up the general order of nodes |
333 | 806 | void StructurizeCFG::orderNodes() { |
334 | 806 | ReversePostOrderTraversal<Region*> RPOT(ParentRegion); |
335 | 806 | SmallDenseMap<Loop*, unsigned, 8> LoopBlocks; |
336 | 806 | |
337 | 806 | // The reverse post-order traversal of the list gives us an ordering close |
338 | 806 | // to what we want. The only problem with it is that sometimes backedges |
339 | 806 | // for outer loops will be visited before backedges for inner loops. |
340 | 1.81k | for (RegionNode *RN : RPOT) { |
341 | 1.81k | Loop *Loop = getAdjustedLoop(RN); |
342 | 1.81k | ++LoopBlocks[Loop]; |
343 | 1.81k | } |
344 | 806 | |
345 | 806 | unsigned CurrentLoopDepth = 0; |
346 | 806 | Loop *CurrentLoop = nullptr; |
347 | 2.61k | for (auto I = RPOT.begin(), E = RPOT.end(); I != E; ++I1.81k ) { |
348 | 1.81k | RegionNode *RN = cast<RegionNode>(*I); |
349 | 1.81k | unsigned LoopDepth = getAdjustedLoopDepth(RN); |
350 | 1.81k | |
351 | 1.81k | if (is_contained(Order, *I)) |
352 | 15 | continue; |
353 | 1.79k | |
354 | 1.79k | if (LoopDepth < CurrentLoopDepth) { |
355 | 15 | // Make sure we have visited all blocks in this loop before moving back to |
356 | 15 | // the outer loop. |
357 | 15 | |
358 | 15 | auto LoopI = I; |
359 | 30 | while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) { |
360 | 15 | LoopI++; |
361 | 15 | if (getAdjustedLoop(cast<RegionNode>(*LoopI)) == CurrentLoop) { |
362 | 15 | --BlockCount; |
363 | 15 | Order.push_back(*LoopI); |
364 | 15 | } |
365 | 15 | } |
366 | 15 | } |
367 | 1.79k | |
368 | 1.79k | CurrentLoop = getAdjustedLoop(RN); |
369 | 1.79k | if (CurrentLoop) |
370 | 411 | LoopBlocks[CurrentLoop]--; |
371 | 1.79k | |
372 | 1.79k | CurrentLoopDepth = LoopDepth; |
373 | 1.79k | Order.push_back(*I); |
374 | 1.79k | } |
375 | 806 | |
376 | 806 | // This pass originally used a post-order traversal and then operated on |
377 | 806 | // the list in reverse. Now that we are using a reverse post-order traversal |
378 | 806 | // rather than re-working the whole pass to operate on the list in order, |
379 | 806 | // we just reverse the list and continue to operate on it in reverse. |
380 | 806 | std::reverse(Order.begin(), Order.end()); |
381 | 806 | } |
382 | | |
383 | | /// Determine the end of the loops |
384 | 1.81k | void StructurizeCFG::analyzeLoops(RegionNode *N) { |
385 | 1.81k | if (N->isSubRegion()) { |
386 | 122 | // Test for exit as back edge |
387 | 122 | BasicBlock *Exit = N->getNodeAs<Region>()->getExit(); |
388 | 122 | if (Visited.count(Exit)) |
389 | 5 | Loops[Exit] = N->getEntry(); |
390 | 122 | |
391 | 1.68k | } else { |
392 | 1.68k | // Test for successors as back edge |
393 | 1.68k | BasicBlock *BB = N->getNodeAs<BasicBlock>(); |
394 | 1.68k | BranchInst *Term = cast<BranchInst>(BB->getTerminator()); |
395 | 1.68k | |
396 | 1.68k | for (BasicBlock *Succ : Term->successors()) |
397 | 2.61k | if (Visited.count(Succ)) |
398 | 195 | Loops[Succ] = BB; |
399 | 1.68k | } |
400 | 1.81k | } |
401 | | |
402 | | /// Invert the given condition |
403 | 450 | Value *StructurizeCFG::invert(Value *Condition) { |
404 | 450 | // First: Check if it's a constant |
405 | 450 | if (Constant *C = dyn_cast<Constant>(Condition)) |
406 | 5 | return ConstantExpr::getNot(C); |
407 | 445 | |
408 | 445 | // Second: If the condition is already inverted, return the original value |
409 | 445 | Value *NotCondition; |
410 | 445 | if (match(Condition, m_Not(m_Value(NotCondition)))) |
411 | 1 | return NotCondition; |
412 | 444 | |
413 | 444 | if (Instruction *Inst = dyn_cast<Instruction>(Condition)) { |
414 | 433 | // Third: Check all the users for an invert |
415 | 433 | BasicBlock *Parent = Inst->getParent(); |
416 | 433 | for (User *U : Condition->users()) |
417 | 437 | if (Instruction *I = dyn_cast<Instruction>(U)) |
418 | 437 | if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))420 ) |
419 | 9 | return I; |
420 | 433 | |
421 | 433 | // Last option: Create a new instruction |
422 | 433 | return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator())424 ; |
423 | 11 | } |
424 | 11 | |
425 | 11 | if (Argument *Arg = dyn_cast<Argument>(Condition)) { |
426 | 11 | BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock(); |
427 | 11 | return BinaryOperator::CreateNot(Condition, |
428 | 11 | Arg->getName() + ".inv", |
429 | 11 | EntryBlock.getTerminator()); |
430 | 11 | } |
431 | 0 | |
432 | 0 | llvm_unreachable("Unhandled condition to invert"); |
433 | 0 | } |
434 | | |
435 | | /// Build the condition for one edge |
436 | | Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx, |
437 | 1.06k | bool Invert) { |
438 | 1.06k | Value *Cond = Invert ? BoolFalse195 : BoolTrue865 ; |
439 | 1.06k | if (Term->isConditional()) { |
440 | 963 | Cond = Term->getCondition(); |
441 | 963 | |
442 | 963 | if (Idx != (unsigned)Invert) |
443 | 450 | Cond = invert(Cond); |
444 | 963 | } |
445 | 1.06k | return Cond; |
446 | 1.06k | } |
447 | | |
448 | | /// Analyze the predecessors of each block and build up predicates |
449 | 1.81k | void StructurizeCFG::gatherPredicates(RegionNode *N) { |
450 | 1.81k | RegionInfo *RI = ParentRegion->getRegionInfo(); |
451 | 1.81k | BasicBlock *BB = N->getEntry(); |
452 | 1.81k | BBPredicates &Pred = Predicates[BB]; |
453 | 1.81k | BBPredicates &LPred = LoopPreds[BB]; |
454 | 1.81k | |
455 | 1.81k | for (BasicBlock *P : predecessors(BB)) { |
456 | 1.73k | // Ignore it if it's a branch from outside into our region entry |
457 | 1.73k | if (!ParentRegion->contains(P)) |
458 | 365 | continue; |
459 | 1.36k | |
460 | 1.36k | Region *R = RI->getRegionFor(P); |
461 | 1.36k | if (R == ParentRegion) { |
462 | 1.20k | // It's a top level block in our region |
463 | 1.20k | BranchInst *Term = cast<BranchInst>(P->getTerminator()); |
464 | 3.52k | for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i2.31k ) { |
465 | 2.31k | BasicBlock *Succ = Term->getSuccessor(i); |
466 | 2.31k | if (Succ != BB) |
467 | 1.11k | continue; |
468 | 1.20k | |
469 | 1.20k | if (Visited.count(P)) { |
470 | 1.01k | // Normal forward edge |
471 | 1.01k | if (Term->isConditional()) { |
472 | 949 | // Try to treat it like an ELSE block |
473 | 949 | BasicBlock *Other = Term->getSuccessor(!i); |
474 | 949 | if (Visited.count(Other) && !Loops.count(Other)186 && |
475 | 949 | !Pred.count(Other)180 && !Pred.count(P)147 ) { |
476 | 147 | |
477 | 147 | Pred[Other] = BoolFalse; |
478 | 147 | Pred[P] = BoolTrue; |
479 | 147 | continue; |
480 | 147 | } |
481 | 865 | } |
482 | 865 | Pred[P] = buildCondition(Term, i, false); |
483 | 865 | } else { |
484 | 195 | // Back edge |
485 | 195 | LPred[P] = buildCondition(Term, i, true); |
486 | 195 | } |
487 | 1.20k | } |
488 | 1.20k | } else { |
489 | 160 | // It's an exit from a sub region |
490 | 190 | while (R->getParent() != ParentRegion) |
491 | 30 | R = R->getParent(); |
492 | 160 | |
493 | 160 | // Edge from inside a subregion to its entry, ignore it |
494 | 160 | if (*R == *N) |
495 | 35 | continue; |
496 | 125 | |
497 | 125 | BasicBlock *Entry = R->getEntry(); |
498 | 125 | if (Visited.count(Entry)) |
499 | 110 | Pred[Entry] = BoolTrue; |
500 | 15 | else |
501 | 15 | LPred[Entry] = BoolFalse; |
502 | 125 | } |
503 | 1.36k | } |
504 | 1.81k | } |
505 | | |
506 | | /// Collect various loop and predicate infos |
507 | 806 | void StructurizeCFG::collectInfos() { |
508 | 806 | // Reset predicate |
509 | 806 | Predicates.clear(); |
510 | 806 | |
511 | 806 | // and loop infos |
512 | 806 | Loops.clear(); |
513 | 806 | LoopPreds.clear(); |
514 | 806 | |
515 | 806 | // Reset the visited nodes |
516 | 806 | Visited.clear(); |
517 | 806 | |
518 | 1.81k | for (RegionNode *RN : reverse(Order)) { |
519 | 1.81k | LLVM_DEBUG(dbgs() << "Visiting: " |
520 | 1.81k | << (RN->isSubRegion() ? "SubRegion with entry: " : "") |
521 | 1.81k | << RN->getEntry()->getName() << " Loop Depth: " |
522 | 1.81k | << LI->getLoopDepth(RN->getEntry()) << "\n"); |
523 | 1.81k | |
524 | 1.81k | // Analyze all the conditions leading to a node |
525 | 1.81k | gatherPredicates(RN); |
526 | 1.81k | |
527 | 1.81k | // Remember that we've seen this node |
528 | 1.81k | Visited.insert(RN->getEntry()); |
529 | 1.81k | |
530 | 1.81k | // Find the last back edges |
531 | 1.81k | analyzeLoops(RN); |
532 | 1.81k | } |
533 | 806 | } |
534 | | |
535 | | /// Insert the missing branch conditions |
536 | 1.61k | void StructurizeCFG::insertConditions(bool Loops) { |
537 | 1.61k | BranchVector &Conds = Loops ? LoopConds806 : Conditions806 ; |
538 | 1.61k | Value *Default = Loops ? BoolTrue806 : BoolFalse806 ; |
539 | 1.61k | SSAUpdater PhiInserter; |
540 | 1.61k | |
541 | 1.61k | for (BranchInst *Term : Conds) { |
542 | 1.09k | assert(Term->isConditional()); |
543 | 1.09k | |
544 | 1.09k | BasicBlock *Parent = Term->getParent(); |
545 | 1.09k | BasicBlock *SuccTrue = Term->getSuccessor(0); |
546 | 1.09k | BasicBlock *SuccFalse = Term->getSuccessor(1); |
547 | 1.09k | |
548 | 1.09k | PhiInserter.Initialize(Boolean, ""); |
549 | 1.09k | PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default); |
550 | 1.09k | PhiInserter.AddAvailableValue(Loops ? SuccFalse198 : Parent893 , Default); |
551 | 1.09k | |
552 | 1.09k | BBPredicates &Preds = Loops ? LoopPreds[SuccFalse]198 : Predicates[SuccTrue]893 ; |
553 | 1.09k | |
554 | 1.09k | NearestCommonDominator Dominator(DT); |
555 | 1.09k | Dominator.addBlock(Parent); |
556 | 1.09k | |
557 | 1.09k | Value *ParentValue = nullptr; |
558 | 1.30k | for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) { |
559 | 1.30k | BasicBlock *BB = BBAndPred.first; |
560 | 1.30k | Value *Pred = BBAndPred.second; |
561 | 1.30k | |
562 | 1.30k | if (BB == Parent) { |
563 | 831 | ParentValue = Pred; |
564 | 831 | break; |
565 | 831 | } |
566 | 478 | PhiInserter.AddAvailableValue(BB, Pred); |
567 | 478 | Dominator.addAndRememberBlock(BB); |
568 | 478 | } |
569 | 1.09k | |
570 | 1.09k | if (ParentValue) { |
571 | 831 | Term->setCondition(ParentValue); |
572 | 831 | } else { |
573 | 260 | if (!Dominator.resultIsRememberedBlock()) |
574 | 143 | PhiInserter.AddAvailableValue(Dominator.result(), Default); |
575 | 260 | |
576 | 260 | Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent)); |
577 | 260 | } |
578 | 1.09k | } |
579 | 1.61k | } |
580 | | |
581 | | /// Remove all PHI values coming from "From" into "To" and remember |
582 | | /// them in DeletedPhis |
583 | 2.80k | void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) { |
584 | 2.80k | PhiMap &Map = DeletedPhis[To]; |
585 | 2.80k | for (PHINode &Phi : To->phis()) { |
586 | 5.02k | while (Phi.getBasicBlockIndex(From) != -1) { |
587 | 2.51k | Value *Deleted = Phi.removeIncomingValue(From, false); |
588 | 2.51k | Map[&Phi].push_back(std::make_pair(From, Deleted)); |
589 | 2.51k | } |
590 | 2.51k | } |
591 | 2.80k | } |
592 | | |
593 | | /// Add a dummy PHI value as soon as we knew the new predecessor |
594 | 2.97k | void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) { |
595 | 2.97k | for (PHINode &Phi : To->phis()) { |
596 | 2.44k | Value *Undef = UndefValue::get(Phi.getType()); |
597 | 2.44k | Phi.addIncoming(Undef, From); |
598 | 2.44k | } |
599 | 2.97k | AddedPhis[To].push_back(From); |
600 | 2.97k | } |
601 | | |
602 | | /// Add the real PHI value as soon as everything is set up |
603 | 806 | void StructurizeCFG::setPhiValues() { |
604 | 806 | SmallVector<PHINode *, 8> InsertedPhis; |
605 | 806 | SSAUpdater Updater(&InsertedPhis); |
606 | 2.32k | for (const auto &AddedPhi : AddedPhis) { |
607 | 2.32k | BasicBlock *To = AddedPhi.first; |
608 | 2.32k | const BBVector &From = AddedPhi.second; |
609 | 2.32k | |
610 | 2.32k | if (!DeletedPhis.count(To)) |
611 | 330 | continue; |
612 | 1.99k | |
613 | 1.99k | PhiMap &Map = DeletedPhis[To]; |
614 | 1.99k | for (const auto &PI : Map) { |
615 | 1.92k | PHINode *Phi = PI.first; |
616 | 1.92k | Value *Undef = UndefValue::get(Phi->getType()); |
617 | 1.92k | Updater.Initialize(Phi->getType(), ""); |
618 | 1.92k | Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); |
619 | 1.92k | Updater.AddAvailableValue(To, Undef); |
620 | 1.92k | |
621 | 1.92k | NearestCommonDominator Dominator(DT); |
622 | 1.92k | Dominator.addBlock(To); |
623 | 2.51k | for (const auto &VI : PI.second) { |
624 | 2.51k | Updater.AddAvailableValue(VI.first, VI.second); |
625 | 2.51k | Dominator.addAndRememberBlock(VI.first); |
626 | 2.51k | } |
627 | 1.92k | |
628 | 1.92k | if (!Dominator.resultIsRememberedBlock()) |
629 | 1.26k | Updater.AddAvailableValue(Dominator.result(), Undef); |
630 | 1.92k | |
631 | 1.92k | for (BasicBlock *FI : From) |
632 | 2.44k | Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI)); |
633 | 1.92k | } |
634 | 1.99k | |
635 | 1.99k | DeletedPhis.erase(To); |
636 | 1.99k | } |
637 | 806 | assert(DeletedPhis.empty()); |
638 | 806 | |
639 | 806 | // Simplify any phis inserted by the SSAUpdater if possible |
640 | 806 | bool Changed; |
641 | 837 | do { |
642 | 837 | Changed = false; |
643 | 837 | |
644 | 837 | SimplifyQuery Q(Func->getParent()->getDataLayout()); |
645 | 837 | Q.DT = DT; |
646 | 2.14k | for (size_t i = 0; i < InsertedPhis.size(); ++i1.30k ) { |
647 | 1.30k | PHINode *Phi = InsertedPhis[i]; |
648 | 1.30k | if (Value *V = SimplifyInstruction(Phi, Q)) { |
649 | 45 | Phi->replaceAllUsesWith(V); |
650 | 45 | Phi->eraseFromParent(); |
651 | 45 | InsertedPhis[i] = InsertedPhis.back(); |
652 | 45 | InsertedPhis.pop_back(); |
653 | 45 | i--; |
654 | 45 | Changed = true; |
655 | 45 | } |
656 | 1.30k | } |
657 | 837 | } while (Changed); |
658 | 806 | } |
659 | | |
660 | | /// Remove phi values from all successors and then remove the terminator. |
661 | 2.05k | void StructurizeCFG::killTerminator(BasicBlock *BB) { |
662 | 2.05k | Instruction *Term = BB->getTerminator(); |
663 | 2.05k | if (!Term) |
664 | 363 | return; |
665 | 1.68k | |
666 | 1.68k | for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); |
667 | 4.30k | SI != SE; ++SI2.61k ) |
668 | 2.61k | delPhiValues(BB, *SI); |
669 | 1.68k | |
670 | 1.68k | if (DA) |
671 | 1.38k | DA->removeValue(Term); |
672 | 1.68k | Term->eraseFromParent(); |
673 | 1.68k | } |
674 | | |
675 | | /// Let node exit(s) point to NewExit |
676 | | void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit, |
677 | 1.08k | bool IncludeDominator) { |
678 | 1.08k | if (Node->isSubRegion()) { |
679 | 122 | Region *SubRegion = Node->getNodeAs<Region>(); |
680 | 122 | BasicBlock *OldExit = SubRegion->getExit(); |
681 | 122 | BasicBlock *Dominator = nullptr; |
682 | 122 | |
683 | 122 | // Find all the edges from the sub region to the exit |
684 | 357 | for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) { |
685 | 235 | // Incrememt BBI before mucking with BB's terminator. |
686 | 235 | BasicBlock *BB = *BBI++; |
687 | 235 | |
688 | 235 | if (!SubRegion->contains(BB)) |
689 | 39 | continue; |
690 | 196 | |
691 | 196 | // Modify the edges to point to the new exit |
692 | 196 | delPhiValues(BB, OldExit); |
693 | 196 | BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit); |
694 | 196 | addPhiValues(BB, NewExit); |
695 | 196 | |
696 | 196 | // Find the new dominator (if requested) |
697 | 196 | if (IncludeDominator) { |
698 | 110 | if (!Dominator) |
699 | 62 | Dominator = BB; |
700 | 48 | else |
701 | 48 | Dominator = DT->findNearestCommonDominator(Dominator, BB); |
702 | 110 | } |
703 | 196 | } |
704 | 122 | |
705 | 122 | // Change the dominator (if requested) |
706 | 122 | if (Dominator) |
707 | 62 | DT->changeImmediateDominator(NewExit, Dominator); |
708 | 122 | |
709 | 122 | // Update the region info |
710 | 122 | SubRegion->replaceExit(NewExit); |
711 | 961 | } else { |
712 | 961 | BasicBlock *BB = Node->getNodeAs<BasicBlock>(); |
713 | 961 | killTerminator(BB); |
714 | 961 | BranchInst::Create(NewExit, BB); |
715 | 961 | addPhiValues(BB, NewExit); |
716 | 961 | if (IncludeDominator) |
717 | 85 | DT->changeImmediateDominator(NewExit, BB); |
718 | 961 | } |
719 | 1.08k | } |
720 | | |
721 | | /// Create a new flow node and update dominator tree and region info |
722 | 363 | BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) { |
723 | 363 | LLVMContext &Context = Func->getContext(); |
724 | 363 | BasicBlock *Insert = Order.empty() ? ParentRegion->getExit()94 : |
725 | 363 | Order.back()->getEntry()269 ; |
726 | 363 | BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName, |
727 | 363 | Func, Insert); |
728 | 363 | DT->addNewBlock(Flow, Dominator); |
729 | 363 | ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion); |
730 | 363 | return Flow; |
731 | 363 | } |
732 | | |
733 | | /// Create a new or reuse the previous node as flow node |
734 | 1.09k | BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) { |
735 | 1.09k | BasicBlock *Entry = PrevNode->getEntry(); |
736 | 1.09k | |
737 | 1.09k | if (!PrevNode->isSubRegion()) { |
738 | 1.09k | killTerminator(Entry); |
739 | 1.09k | if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end()0 ) |
740 | 1.09k | return Entry; |
741 | 0 | } |
742 | 0 | |
743 | 0 | // create a new flow node |
744 | 0 | BasicBlock *Flow = getNextFlow(Entry); |
745 | 0 |
|
746 | 0 | // and wire it up |
747 | 0 | changeExit(PrevNode, Flow, true); |
748 | 0 | PrevNode = ParentRegion->getBBNode(Flow); |
749 | 0 | return Flow; |
750 | 0 | } |
751 | | |
752 | | /// Returns the region exit if possible, otherwise just a new flow node |
753 | | BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow, |
754 | 1.09k | bool ExitUseAllowed) { |
755 | 1.09k | if (!Order.empty() || !ExitUseAllowed822 ) |
756 | 363 | return getNextFlow(Flow); |
757 | 728 | |
758 | 728 | BasicBlock *Exit = ParentRegion->getExit(); |
759 | 728 | DT->changeImmediateDominator(Exit, Flow); |
760 | 728 | addPhiValues(Flow, Exit); |
761 | 728 | return Exit; |
762 | 728 | } |
763 | | |
764 | | /// Set the previous node |
765 | 1.09k | void StructurizeCFG::setPrevNode(BasicBlock *BB) { |
766 | 1.09k | PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)363 |
767 | 1.09k | : nullptr728 ; |
768 | 1.09k | } |
769 | | |
770 | | /// Does BB dominate all the predicates of Node? |
771 | 280 | bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { |
772 | 280 | BBPredicates &Preds = Predicates[Node->getEntry()]; |
773 | 367 | return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) { |
774 | 367 | return DT->dominates(BB, Pred.first); |
775 | 367 | }); |
776 | 280 | } |
777 | | |
778 | | /// Can we predict that this node will always be called? |
779 | 2.00k | bool StructurizeCFG::isPredictableTrue(RegionNode *Node) { |
780 | 2.00k | BBPredicates &Preds = Predicates[Node->getEntry()]; |
781 | 2.00k | bool Dominated = false; |
782 | 2.00k | |
783 | 2.00k | // Regionentry is always true |
784 | 2.00k | if (!PrevNode) |
785 | 993 | return true; |
786 | 1.01k | |
787 | 1.09k | for (std::pair<BasicBlock*, Value*> Pred : Preds)1.01k { |
788 | 1.09k | BasicBlock *BB = Pred.first; |
789 | 1.09k | Value *V = Pred.second; |
790 | 1.09k | |
791 | 1.09k | if (V != BoolTrue) |
792 | 888 | return false; |
793 | 203 | |
794 | 203 | if (!Dominated && DT->dominates(BB, PrevNode->getEntry())) |
795 | 172 | Dominated = true; |
796 | 203 | } |
797 | 1.01k | |
798 | 1.01k | // TODO: The dominator check is too strict |
799 | 1.01k | return Dominated128 ; |
800 | 1.01k | } |
801 | | |
802 | | /// Take one node from the order vector and wire it up |
803 | | void StructurizeCFG::wireFlow(bool ExitUseAllowed, |
804 | 1.81k | BasicBlock *LoopEnd) { |
805 | 1.81k | RegionNode *Node = Order.pop_back_val(); |
806 | 1.81k | Visited.insert(Node->getEntry()); |
807 | 1.81k | |
808 | 1.81k | if (isPredictableTrue(Node)) { |
809 | 918 | // Just a linear flow |
810 | 918 | if (PrevNode) { |
811 | 112 | changeExit(PrevNode, Node->getEntry(), true); |
812 | 112 | } |
813 | 918 | PrevNode = Node; |
814 | 918 | } else { |
815 | 893 | // Insert extra prefix node (or reuse last one) |
816 | 893 | BasicBlock *Flow = needPrefix(false); |
817 | 893 | |
818 | 893 | // Insert extra postfix node (or use exit instead) |
819 | 893 | BasicBlock *Entry = Node->getEntry(); |
820 | 893 | BasicBlock *Next = needPostfix(Flow, ExitUseAllowed); |
821 | 893 | |
822 | 893 | // let it point to entry and next block |
823 | 893 | Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow)); |
824 | 893 | addPhiValues(Flow, Entry); |
825 | 893 | DT->changeImmediateDominator(Entry, Flow); |
826 | 893 | |
827 | 893 | PrevNode = Node; |
828 | 987 | while (!Order.empty() && !Visited.count(LoopEnd)300 && |
829 | 987 | dominatesPredicates(Entry, Order.back())280 ) { |
830 | 94 | handleLoops(false, LoopEnd); |
831 | 94 | } |
832 | 893 | |
833 | 893 | changeExit(PrevNode, Next, false); |
834 | 893 | setPrevNode(Next); |
835 | 893 | } |
836 | 1.81k | } |
837 | | |
838 | | void StructurizeCFG::handleLoops(bool ExitUseAllowed, |
839 | 1.81k | BasicBlock *LoopEnd) { |
840 | 1.81k | RegionNode *Node = Order.back(); |
841 | 1.81k | BasicBlock *LoopStart = Node->getEntry(); |
842 | 1.81k | |
843 | 1.81k | if (!Loops.count(LoopStart)) { |
844 | 1.61k | wireFlow(ExitUseAllowed, LoopEnd); |
845 | 1.61k | return; |
846 | 1.61k | } |
847 | 198 | |
848 | 198 | if (!isPredictableTrue(Node)) |
849 | 0 | LoopStart = needPrefix(true); |
850 | 198 | |
851 | 198 | LoopEnd = Loops[Node->getEntry()]; |
852 | 198 | wireFlow(false, LoopEnd); |
853 | 328 | while (!Visited.count(LoopEnd)) { |
854 | 130 | handleLoops(false, LoopEnd); |
855 | 130 | } |
856 | 198 | |
857 | 198 | // If the start of the loop is the entry block, we can't branch to it so |
858 | 198 | // insert a new dummy entry block. |
859 | 198 | Function *LoopFunc = LoopStart->getParent(); |
860 | 198 | if (LoopStart == &LoopFunc->getEntryBlock()) { |
861 | 0 | LoopStart->setName("entry.orig"); |
862 | 0 |
|
863 | 0 | BasicBlock *NewEntry = |
864 | 0 | BasicBlock::Create(LoopStart->getContext(), |
865 | 0 | "entry", |
866 | 0 | LoopFunc, |
867 | 0 | LoopStart); |
868 | 0 | BranchInst::Create(LoopStart, NewEntry); |
869 | 0 | DT->setNewRoot(NewEntry); |
870 | 0 | } |
871 | 198 | |
872 | 198 | // Create an extra loop end node |
873 | 198 | LoopEnd = needPrefix(false); |
874 | 198 | BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed); |
875 | 198 | LoopConds.push_back(BranchInst::Create(Next, LoopStart, |
876 | 198 | BoolUndef, LoopEnd)); |
877 | 198 | addPhiValues(LoopEnd, LoopStart); |
878 | 198 | setPrevNode(Next); |
879 | 198 | } |
880 | | |
881 | | /// After this function control flow looks like it should be, but |
882 | | /// branches and PHI nodes only have undefined conditions. |
883 | 806 | void StructurizeCFG::createFlow() { |
884 | 806 | BasicBlock *Exit = ParentRegion->getExit(); |
885 | 806 | bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit); |
886 | 806 | |
887 | 806 | DeletedPhis.clear(); |
888 | 806 | AddedPhis.clear(); |
889 | 806 | Conditions.clear(); |
890 | 806 | LoopConds.clear(); |
891 | 806 | |
892 | 806 | PrevNode = nullptr; |
893 | 806 | Visited.clear(); |
894 | 806 | |
895 | 2.39k | while (!Order.empty()) { |
896 | 1.58k | handleLoops(EntryDominatesExit, nullptr); |
897 | 1.58k | } |
898 | 806 | |
899 | 806 | if (PrevNode) |
900 | 78 | changeExit(PrevNode, Exit, EntryDominatesExit); |
901 | 806 | else |
902 | 806 | assert(EntryDominatesExit); |
903 | 806 | } |
904 | | |
905 | | /// Handle a rare case where the disintegrated nodes instructions |
906 | | /// no longer dominate all their uses. Not sure if this is really necessary |
907 | 806 | void StructurizeCFG::rebuildSSA() { |
908 | 806 | SSAUpdater Updater; |
909 | 806 | for (BasicBlock *BB : ParentRegion->blocks()) |
910 | 19.8k | for (Instruction &I : *BB)2.44k { |
911 | 19.8k | bool Initialized = false; |
912 | 19.8k | // We may modify the use list as we iterate over it, so be careful to |
913 | 19.8k | // compute the next element in the use list at the top of the loop. |
914 | 42.1k | for (auto UI = I.use_begin(), E = I.use_end(); UI != E;) { |
915 | 22.3k | Use &U = *UI++; |
916 | 22.3k | Instruction *User = cast<Instruction>(U.getUser()); |
917 | 22.3k | if (User->getParent() == BB) { |
918 | 14.7k | continue; |
919 | 14.7k | } else if (PHINode *7.50k UserPN7.50k = dyn_cast<PHINode>(User)) { |
920 | 3.53k | if (UserPN->getIncomingBlock(U) == BB) |
921 | 3.37k | continue; |
922 | 4.13k | } |
923 | 4.13k | |
924 | 4.13k | if (DT->dominates(&I, User)) |
925 | 4.07k | continue; |
926 | 57 | |
927 | 57 | if (!Initialized) { |
928 | 54 | Value *Undef = UndefValue::get(I.getType()); |
929 | 54 | Updater.Initialize(I.getType(), ""); |
930 | 54 | Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); |
931 | 54 | Updater.AddAvailableValue(BB, &I); |
932 | 54 | Initialized = true; |
933 | 54 | } |
934 | 57 | Updater.RewriteUseAfterInsertions(U); |
935 | 57 | } |
936 | 19.8k | } |
937 | 806 | } |
938 | | |
939 | | static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, |
940 | 1.26k | const LegacyDivergenceAnalysis &DA) { |
941 | 1.26k | // Bool for if all sub-regions are uniform. |
942 | 1.26k | bool SubRegionsAreUniform = true; |
943 | 1.26k | // Count of how many direct children are conditional. |
944 | 1.26k | unsigned ConditionalDirectChildren = 0; |
945 | 1.26k | |
946 | 1.95k | for (auto E : R->elements()) { |
947 | 1.95k | if (!E->isSubRegion()) { |
948 | 1.85k | auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator()); |
949 | 1.85k | if (!Br || !Br->isConditional()) |
950 | 559 | continue; |
951 | 1.29k | |
952 | 1.29k | if (!DA.isUniform(Br)) |
953 | 669 | return false; |
954 | 627 | |
955 | 627 | // One of our direct children is conditional. |
956 | 627 | ConditionalDirectChildren++; |
957 | 627 | |
958 | 627 | LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName() |
959 | 627 | << " has uniform terminator\n"); |
960 | 627 | } else { |
961 | 96 | // Explicitly refuse to treat regions as uniform if they have non-uniform |
962 | 96 | // subregions. We cannot rely on DivergenceAnalysis for branches in |
963 | 96 | // subregions because those branches may have been removed and re-created, |
964 | 96 | // so we look for our metadata instead. |
965 | 96 | // |
966 | 96 | // Warning: It would be nice to treat regions as uniform based only on |
967 | 96 | // their direct child basic blocks' terminators, regardless of whether |
968 | 96 | // subregions are uniform or not. However, this requires a very careful |
969 | 96 | // look at SIAnnotateControlFlow to make sure nothing breaks there. |
970 | 191 | for (auto BB : E->getNodeAs<Region>()->blocks()) { |
971 | 191 | auto Br = dyn_cast<BranchInst>(BB->getTerminator()); |
972 | 191 | if (!Br || !Br->isConditional()) |
973 | 61 | continue; |
974 | 130 | |
975 | 130 | if (!Br->getMetadata(UniformMDKindID)) { |
976 | 20 | // Early exit if we cannot have relaxed uniform regions. |
977 | 20 | if (!RelaxedUniformRegions) |
978 | 16 | return false; |
979 | 4 | |
980 | 4 | SubRegionsAreUniform = false; |
981 | 4 | break; |
982 | 4 | } |
983 | 130 | } |
984 | 96 | } |
985 | 1.95k | } |
986 | 1.26k | |
987 | 1.26k | // Our region is uniform if: |
988 | 1.26k | // 1. All conditional branches that are direct children are uniform (checked |
989 | 1.26k | // above). |
990 | 1.26k | // 2. And either: |
991 | 1.26k | // a. All sub-regions are uniform. |
992 | 1.26k | // b. There is one or less conditional branches among the direct children. |
993 | 1.26k | return 584 SubRegionsAreUniform584 || (ConditionalDirectChildren <= 1)1 ; |
994 | 1.26k | } |
995 | | |
996 | | /// Run the transformation for each region found |
997 | 28.9k | bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { |
998 | 28.9k | if (R->isTopLevelRegion()) |
999 | 27.5k | return false; |
1000 | 1.39k | |
1001 | 1.39k | DA = nullptr; |
1002 | 1.39k | |
1003 | 1.39k | if (SkipUniformRegions) { |
1004 | 1.26k | // TODO: We could probably be smarter here with how we handle sub-regions. |
1005 | 1.26k | // We currently rely on the fact that metadata is set by earlier invocations |
1006 | 1.26k | // of the pass on sub-regions, and that this metadata doesn't get lost -- |
1007 | 1.26k | // but we shouldn't rely on metadata for correctness! |
1008 | 1.26k | unsigned UniformMDKindID = |
1009 | 1.26k | R->getEntry()->getContext().getMDKindID("structurizecfg.uniform"); |
1010 | 1.26k | DA = &getAnalysis<LegacyDivergenceAnalysis>(); |
1011 | 1.26k | |
1012 | 1.26k | if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) { |
1013 | 584 | LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R |
1014 | 584 | << '\n'); |
1015 | 584 | |
1016 | 584 | // Mark all direct child block terminators as having been treated as |
1017 | 584 | // uniform. To account for a possible future in which non-uniform |
1018 | 584 | // sub-regions are treated more cleverly, indirect children are not |
1019 | 584 | // marked as uniform. |
1020 | 584 | MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {}); |
1021 | 1.21k | for (RegionNode *E : R->elements()) { |
1022 | 1.21k | if (E->isSubRegion()) |
1023 | 70 | continue; |
1024 | 1.14k | |
1025 | 1.14k | if (Instruction *Term = E->getEntry()->getTerminator()) |
1026 | 1.14k | Term->setMetadata(UniformMDKindID, MD); |
1027 | 1.14k | } |
1028 | 584 | |
1029 | 584 | return false; |
1030 | 584 | } |
1031 | 806 | } |
1032 | 806 | |
1033 | 806 | Func = R->getEntry()->getParent(); |
1034 | 806 | ParentRegion = R; |
1035 | 806 | |
1036 | 806 | DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
1037 | 806 | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
1038 | 806 | |
1039 | 806 | orderNodes(); |
1040 | 806 | collectInfos(); |
1041 | 806 | createFlow(); |
1042 | 806 | insertConditions(false); |
1043 | 806 | insertConditions(true); |
1044 | 806 | setPhiValues(); |
1045 | 806 | rebuildSSA(); |
1046 | 806 | |
1047 | 806 | // Cleanup |
1048 | 806 | Order.clear(); |
1049 | 806 | Visited.clear(); |
1050 | 806 | DeletedPhis.clear(); |
1051 | 806 | AddedPhis.clear(); |
1052 | 806 | Predicates.clear(); |
1053 | 806 | Conditions.clear(); |
1054 | 806 | Loops.clear(); |
1055 | 806 | LoopPreds.clear(); |
1056 | 806 | LoopConds.clear(); |
1057 | 806 | |
1058 | 806 | return true; |
1059 | 806 | } |
1060 | | |
1061 | 2.72k | Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) { |
1062 | 2.72k | return new StructurizeCFG(SkipUniformRegions); |
1063 | 2.72k | } |