Bug Summary

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