Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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