Bug Summary

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