Bug Summary

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