Bug Summary

File:lib/Transforms/Scalar/StructurizeCFG.cpp
Warning:line 734, column 23
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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