Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
Line
Count
Source (jump to first uncovered line)
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
49
using namespace llvm;
50
using namespace llvm::PatternMatch;
51
52
#define DEBUG_TYPE "structurizecfg"
53
54
// The name for newly created blocks.
55
static const char *const FlowBlockName = "Flow";
56
57
namespace {
58
59
static 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
static 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
72
using BBValuePair = std::pair<BasicBlock *, Value *>;
73
74
using RNVector = SmallVector<RegionNode *, 8>;
75
using BBVector = SmallVector<BasicBlock *, 8>;
76
using BranchVector = SmallVector<BranchInst *, 8>;
77
using BBValueVector = SmallVector<BBValuePair, 2>;
78
79
using BBSet = SmallPtrSet<BasicBlock *, 8>;
80
81
using PhiMap = MapVector<PHINode *, BBValueVector>;
82
using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
83
84
using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
85
using BBPredicates = DenseMap<BasicBlock *, Value *>;
86
using PredMap = DenseMap<BasicBlock *, BBPredicates>;
87
using 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.
94
class NearestCommonDominator {
95
  DominatorTree *DT;
96
  BasicBlock *Result = nullptr;
97
  bool ResultIsRemembered = false;
98
99
  /// Add BB to the resulting dominator.
100
6.01k
  void addBlock(BasicBlock *BB, bool Remember) {
101
6.01k
    if (!Result) {
102
3.01k
      Result = BB;
103
3.01k
      ResultIsRemembered = Remember;
104
3.01k
      return;
105
3.01k
    }
106
2.99k
107
2.99k
    BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
108
2.99k
    if (NewResult != Result)
109
939
      ResultIsRemembered = false;
110
2.99k
    if (NewResult == BB)
111
782
      ResultIsRemembered |= Remember;
112
2.99k
    Result = NewResult;
113
2.99k
  }
114
115
public:
116
3.01k
  explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
117
118
3.01k
  void addBlock(BasicBlock *BB) {
119
3.01k
    addBlock(BB, /* Remember = */ false);
120
3.01k
  }
121
122
2.99k
  void addAndRememberBlock(BasicBlock *BB) {
123
2.99k
    addBlock(BB, /* Remember = */ true);
124
2.99k
  }
125
126
  /// Get the nearest common dominator of all the BBs added via addBlock() and
127
  /// addAndRememberBlock().
128
1.40k
  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
2.18k
  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.
180
class 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
258
public:
259
  static char ID;
260
261
  explicit StructurizeCFG(bool SkipUniformRegions_ = false)
262
      : RegionPass(ID),
263
2.74k
        SkipUniformRegions(SkipUniformRegions_) {
264
2.74k
    if (ForceSkipUniformRegions.getNumOccurrences())
265
1
      SkipUniformRegions = ForceSkipUniformRegions.getValue();
266
2.74k
    initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
267
2.74k
  }
268
269
  bool doInitialization(Region *R, RGPassManager &RGM) override;
270
271
  bool runOnRegion(Region *R, RGPassManager &RGM) override;
272
273
0
  StringRef getPassName() const override { return "Structurize control flow"; }
274
275
2.72k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
276
2.72k
    if (SkipUniformRegions)
277
2.42k
      AU.addRequired<LegacyDivergenceAnalysis>();
278
2.72k
    AU.addRequiredID(LowerSwitchID);
279
2.72k
    AU.addRequired<DominatorTreeWrapperPass>();
280
2.72k
    AU.addRequired<LoopInfoWrapperPass>();
281
2.72k
282
2.72k
    AU.addPreserved<DominatorTreeWrapperPass>();
283
2.72k
    RegionPass::getAnalysisUsage(AU);
284
2.72k
  }
285
};
286
287
} // end anonymous namespace
288
289
char StructurizeCFG::ID = 0;
290
291
36.0k
INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
292
36.0k
                      false, false)
293
36.0k
INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
294
36.0k
INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
295
36.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
296
36.0k
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)
297
36.0k
INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
298
                    false, false)
299
300
/// Initialize the types and constants used in the pass
301
28.9k
bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
302
28.9k
  LLVMContext &Context = R->getEntry()->getContext();
303
28.9k
304
28.9k
  Boolean = Type::getInt1Ty(Context);
305
28.9k
  BoolTrue = ConstantInt::getTrue(Context);
306
28.9k
  BoolFalse = ConstantInt::getFalse(Context);
307
28.9k
  BoolUndef = UndefValue::get(Boolean);
308
28.9k
309
28.9k
  return false;
310
28.9k
}
311
312
/// Use the exit block to determine the loop if RN is a SubRegion.
313
3.62k
Loop *StructurizeCFG::getAdjustedLoop(RegionNode *RN) {
314
3.62k
  if (RN->isSubRegion()) {
315
244
    Region *SubRegion = RN->getNodeAs<Region>();
316
244
    return LI->getLoopFor(SubRegion->getExit());
317
244
  }
318
3.37k
319
3.37k
  return LI->getLoopFor(RN->getEntry());
320
3.37k
}
321
322
/// Use the exit block to determine the loop depth if RN is a SubRegion.
323
1.81k
unsigned StructurizeCFG::getAdjustedLoopDepth(RegionNode *RN) {
324
1.81k
  if (RN->isSubRegion()) {
325
122
    Region *SubR = RN->getNodeAs<Region>();
326
122
    return LI->getLoopDepth(SubR->getExit());
327
122
  }
328
1.68k
329
1.68k
  return LI->getLoopDepth(RN->getEntry());
330
1.68k
}
331
332
/// Build up the general order of nodes
333
806
void StructurizeCFG::orderNodes() {
334
806
  ReversePostOrderTraversal<Region*> RPOT(ParentRegion);
335
806
  SmallDenseMap<Loop*, unsigned, 8> LoopBlocks;
336
806
337
806
  // The reverse post-order traversal of the list gives us an ordering close
338
806
  // to what we want.  The only problem with it is that sometimes backedges
339
806
  // for outer loops will be visited before backedges for inner loops.
340
1.81k
  for (RegionNode *RN : RPOT) {
341
1.81k
    Loop *Loop = getAdjustedLoop(RN);
342
1.81k
    ++LoopBlocks[Loop];
343
1.81k
  }
344
806
345
806
  unsigned CurrentLoopDepth = 0;
346
806
  Loop *CurrentLoop = nullptr;
347
2.61k
  for (auto I = RPOT.begin(), E = RPOT.end(); I != E; 
++I1.81k
) {
348
1.81k
    RegionNode *RN = cast<RegionNode>(*I);
349
1.81k
    unsigned LoopDepth = getAdjustedLoopDepth(RN);
350
1.81k
351
1.81k
    if (is_contained(Order, *I))
352
15
      continue;
353
1.79k
354
1.79k
    if (LoopDepth < CurrentLoopDepth) {
355
15
      // Make sure we have visited all blocks in this loop before moving back to
356
15
      // the outer loop.
357
15
358
15
      auto LoopI = I;
359
30
      while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) {
360
15
        LoopI++;
361
15
        if (getAdjustedLoop(cast<RegionNode>(*LoopI)) == CurrentLoop) {
362
15
          --BlockCount;
363
15
          Order.push_back(*LoopI);
364
15
        }
365
15
      }
366
15
    }
367
1.79k
368
1.79k
    CurrentLoop = getAdjustedLoop(RN);
369
1.79k
    if (CurrentLoop)
370
411
      LoopBlocks[CurrentLoop]--;
371
1.79k
372
1.79k
    CurrentLoopDepth = LoopDepth;
373
1.79k
    Order.push_back(*I);
374
1.79k
  }
375
806
376
806
  // This pass originally used a post-order traversal and then operated on
377
806
  // the list in reverse. Now that we are using a reverse post-order traversal
378
806
  // rather than re-working the whole pass to operate on the list in order,
379
806
  // we just reverse the list and continue to operate on it in reverse.
380
806
  std::reverse(Order.begin(), Order.end());
381
806
}
382
383
/// Determine the end of the loops
384
1.81k
void StructurizeCFG::analyzeLoops(RegionNode *N) {
385
1.81k
  if (N->isSubRegion()) {
386
122
    // Test for exit as back edge
387
122
    BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
388
122
    if (Visited.count(Exit))
389
5
      Loops[Exit] = N->getEntry();
390
122
391
1.68k
  } else {
392
1.68k
    // Test for successors as back edge
393
1.68k
    BasicBlock *BB = N->getNodeAs<BasicBlock>();
394
1.68k
    BranchInst *Term = cast<BranchInst>(BB->getTerminator());
395
1.68k
396
1.68k
    for (BasicBlock *Succ : Term->successors())
397
2.61k
      if (Visited.count(Succ))
398
195
        Loops[Succ] = BB;
399
1.68k
  }
400
1.81k
}
401
402
/// Invert the given condition
403
450
Value *StructurizeCFG::invert(Value *Condition) {
404
450
  // First: Check if it's a constant
405
450
  if (Constant *C = dyn_cast<Constant>(Condition))
406
5
    return ConstantExpr::getNot(C);
407
445
408
445
  // Second: If the condition is already inverted, return the original value
409
445
  Value *NotCondition;
410
445
  if (match(Condition, m_Not(m_Value(NotCondition))))
411
1
    return NotCondition;
412
444
413
444
  if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
414
433
    // Third: Check all the users for an invert
415
433
    BasicBlock *Parent = Inst->getParent();
416
433
    for (User *U : Condition->users())
417
437
      if (Instruction *I = dyn_cast<Instruction>(U))
418
437
        if (I->getParent() == Parent && 
match(I, m_Not(m_Specific(Condition)))420
)
419
9
          return I;
420
433
421
433
    // Last option: Create a new instruction
422
433
    
return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator())424
;
423
11
  }
424
11
425
11
  if (Argument *Arg = dyn_cast<Argument>(Condition)) {
426
11
    BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
427
11
    return BinaryOperator::CreateNot(Condition,
428
11
                                     Arg->getName() + ".inv",
429
11
                                     EntryBlock.getTerminator());
430
11
  }
431
0
432
0
  llvm_unreachable("Unhandled condition to invert");
433
0
}
434
435
/// Build the condition for one edge
436
Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
437
1.06k
                                      bool Invert) {
438
1.06k
  Value *Cond = Invert ? 
BoolFalse195
:
BoolTrue865
;
439
1.06k
  if (Term->isConditional()) {
440
963
    Cond = Term->getCondition();
441
963
442
963
    if (Idx != (unsigned)Invert)
443
450
      Cond = invert(Cond);
444
963
  }
445
1.06k
  return Cond;
446
1.06k
}
447
448
/// Analyze the predecessors of each block and build up predicates
449
1.81k
void StructurizeCFG::gatherPredicates(RegionNode *N) {
450
1.81k
  RegionInfo *RI = ParentRegion->getRegionInfo();
451
1.81k
  BasicBlock *BB = N->getEntry();
452
1.81k
  BBPredicates &Pred = Predicates[BB];
453
1.81k
  BBPredicates &LPred = LoopPreds[BB];
454
1.81k
455
1.81k
  for (BasicBlock *P : predecessors(BB)) {
456
1.73k
    // Ignore it if it's a branch from outside into our region entry
457
1.73k
    if (!ParentRegion->contains(P))
458
365
      continue;
459
1.36k
460
1.36k
    Region *R = RI->getRegionFor(P);
461
1.36k
    if (R == ParentRegion) {
462
1.20k
      // It's a top level block in our region
463
1.20k
      BranchInst *Term = cast<BranchInst>(P->getTerminator());
464
3.52k
      for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; 
++i2.31k
) {
465
2.31k
        BasicBlock *Succ = Term->getSuccessor(i);
466
2.31k
        if (Succ != BB)
467
1.11k
          continue;
468
1.20k
469
1.20k
        if (Visited.count(P)) {
470
1.01k
          // Normal forward edge
471
1.01k
          if (Term->isConditional()) {
472
949
            // Try to treat it like an ELSE block
473
949
            BasicBlock *Other = Term->getSuccessor(!i);
474
949
            if (Visited.count(Other) && 
!Loops.count(Other)186
&&
475
949
                
!Pred.count(Other)180
&&
!Pred.count(P)147
) {
476
147
477
147
              Pred[Other] = BoolFalse;
478
147
              Pred[P] = BoolTrue;
479
147
              continue;
480
147
            }
481
865
          }
482
865
          Pred[P] = buildCondition(Term, i, false);
483
865
        } else {
484
195
          // Back edge
485
195
          LPred[P] = buildCondition(Term, i, true);
486
195
        }
487
1.20k
      }
488
1.20k
    } else {
489
160
      // It's an exit from a sub region
490
190
      while (R->getParent() != ParentRegion)
491
30
        R = R->getParent();
492
160
493
160
      // Edge from inside a subregion to its entry, ignore it
494
160
      if (*R == *N)
495
35
        continue;
496
125
497
125
      BasicBlock *Entry = R->getEntry();
498
125
      if (Visited.count(Entry))
499
110
        Pred[Entry] = BoolTrue;
500
15
      else
501
15
        LPred[Entry] = BoolFalse;
502
125
    }
503
1.36k
  }
504
1.81k
}
505
506
/// Collect various loop and predicate infos
507
806
void StructurizeCFG::collectInfos() {
508
806
  // Reset predicate
509
806
  Predicates.clear();
510
806
511
806
  // and loop infos
512
806
  Loops.clear();
513
806
  LoopPreds.clear();
514
806
515
806
  // Reset the visited nodes
516
806
  Visited.clear();
517
806
518
1.81k
  for (RegionNode *RN : reverse(Order)) {
519
1.81k
    LLVM_DEBUG(dbgs() << "Visiting: "
520
1.81k
                      << (RN->isSubRegion() ? "SubRegion with entry: " : "")
521
1.81k
                      << RN->getEntry()->getName() << " Loop Depth: "
522
1.81k
                      << LI->getLoopDepth(RN->getEntry()) << "\n");
523
1.81k
524
1.81k
    // Analyze all the conditions leading to a node
525
1.81k
    gatherPredicates(RN);
526
1.81k
527
1.81k
    // Remember that we've seen this node
528
1.81k
    Visited.insert(RN->getEntry());
529
1.81k
530
1.81k
    // Find the last back edges
531
1.81k
    analyzeLoops(RN);
532
1.81k
  }
533
806
}
534
535
/// Insert the missing branch conditions
536
1.61k
void StructurizeCFG::insertConditions(bool Loops) {
537
1.61k
  BranchVector &Conds = Loops ? 
LoopConds806
:
Conditions806
;
538
1.61k
  Value *Default = Loops ? 
BoolTrue806
:
BoolFalse806
;
539
1.61k
  SSAUpdater PhiInserter;
540
1.61k
541
1.61k
  for (BranchInst *Term : Conds) {
542
1.09k
    assert(Term->isConditional());
543
1.09k
544
1.09k
    BasicBlock *Parent = Term->getParent();
545
1.09k
    BasicBlock *SuccTrue = Term->getSuccessor(0);
546
1.09k
    BasicBlock *SuccFalse = Term->getSuccessor(1);
547
1.09k
548
1.09k
    PhiInserter.Initialize(Boolean, "");
549
1.09k
    PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
550
1.09k
    PhiInserter.AddAvailableValue(Loops ? 
SuccFalse198
:
Parent893
, Default);
551
1.09k
552
1.09k
    BBPredicates &Preds = Loops ? 
LoopPreds[SuccFalse]198
:
Predicates[SuccTrue]893
;
553
1.09k
554
1.09k
    NearestCommonDominator Dominator(DT);
555
1.09k
    Dominator.addBlock(Parent);
556
1.09k
557
1.09k
    Value *ParentValue = nullptr;
558
1.30k
    for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
559
1.30k
      BasicBlock *BB = BBAndPred.first;
560
1.30k
      Value *Pred = BBAndPred.second;
561
1.30k
562
1.30k
      if (BB == Parent) {
563
831
        ParentValue = Pred;
564
831
        break;
565
831
      }
566
478
      PhiInserter.AddAvailableValue(BB, Pred);
567
478
      Dominator.addAndRememberBlock(BB);
568
478
    }
569
1.09k
570
1.09k
    if (ParentValue) {
571
831
      Term->setCondition(ParentValue);
572
831
    } else {
573
260
      if (!Dominator.resultIsRememberedBlock())
574
143
        PhiInserter.AddAvailableValue(Dominator.result(), Default);
575
260
576
260
      Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
577
260
    }
578
1.09k
  }
579
1.61k
}
580
581
/// Remove all PHI values coming from "From" into "To" and remember
582
/// them in DeletedPhis
583
2.80k
void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
584
2.80k
  PhiMap &Map = DeletedPhis[To];
585
2.80k
  for (PHINode &Phi : To->phis()) {
586
5.02k
    while (Phi.getBasicBlockIndex(From) != -1) {
587
2.51k
      Value *Deleted = Phi.removeIncomingValue(From, false);
588
2.51k
      Map[&Phi].push_back(std::make_pair(From, Deleted));
589
2.51k
    }
590
2.51k
  }
591
2.80k
}
592
593
/// Add a dummy PHI value as soon as we knew the new predecessor
594
2.97k
void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
595
2.97k
  for (PHINode &Phi : To->phis()) {
596
2.44k
    Value *Undef = UndefValue::get(Phi.getType());
597
2.44k
    Phi.addIncoming(Undef, From);
598
2.44k
  }
599
2.97k
  AddedPhis[To].push_back(From);
600
2.97k
}
601
602
/// Add the real PHI value as soon as everything is set up
603
806
void StructurizeCFG::setPhiValues() {
604
806
  SmallVector<PHINode *, 8> InsertedPhis;
605
806
  SSAUpdater Updater(&InsertedPhis);
606
2.32k
  for (const auto &AddedPhi : AddedPhis) {
607
2.32k
    BasicBlock *To = AddedPhi.first;
608
2.32k
    const BBVector &From = AddedPhi.second;
609
2.32k
610
2.32k
    if (!DeletedPhis.count(To))
611
330
      continue;
612
1.99k
613
1.99k
    PhiMap &Map = DeletedPhis[To];
614
1.99k
    for (const auto &PI : Map) {
615
1.92k
      PHINode *Phi = PI.first;
616
1.92k
      Value *Undef = UndefValue::get(Phi->getType());
617
1.92k
      Updater.Initialize(Phi->getType(), "");
618
1.92k
      Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
619
1.92k
      Updater.AddAvailableValue(To, Undef);
620
1.92k
621
1.92k
      NearestCommonDominator Dominator(DT);
622
1.92k
      Dominator.addBlock(To);
623
2.51k
      for (const auto &VI : PI.second) {
624
2.51k
        Updater.AddAvailableValue(VI.first, VI.second);
625
2.51k
        Dominator.addAndRememberBlock(VI.first);
626
2.51k
      }
627
1.92k
628
1.92k
      if (!Dominator.resultIsRememberedBlock())
629
1.26k
        Updater.AddAvailableValue(Dominator.result(), Undef);
630
1.92k
631
1.92k
      for (BasicBlock *FI : From)
632
2.44k
        Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI));
633
1.92k
    }
634
1.99k
635
1.99k
    DeletedPhis.erase(To);
636
1.99k
  }
637
806
  assert(DeletedPhis.empty());
638
806
639
806
  // Simplify any phis inserted by the SSAUpdater if possible
640
806
  bool Changed;
641
837
  do {
642
837
    Changed = false;
643
837
644
837
    SimplifyQuery Q(Func->getParent()->getDataLayout());
645
837
    Q.DT = DT;
646
2.14k
    for (size_t i = 0; i < InsertedPhis.size(); 
++i1.30k
) {
647
1.30k
      PHINode *Phi = InsertedPhis[i];
648
1.30k
      if (Value *V = SimplifyInstruction(Phi, Q)) {
649
45
        Phi->replaceAllUsesWith(V);
650
45
        Phi->eraseFromParent();
651
45
        InsertedPhis[i] = InsertedPhis.back();
652
45
        InsertedPhis.pop_back();
653
45
        i--;
654
45
        Changed = true;
655
45
      }
656
1.30k
    }
657
837
  } while (Changed);
658
806
}
659
660
/// Remove phi values from all successors and then remove the terminator.
661
2.05k
void StructurizeCFG::killTerminator(BasicBlock *BB) {
662
2.05k
  Instruction *Term = BB->getTerminator();
663
2.05k
  if (!Term)
664
363
    return;
665
1.68k
666
1.68k
  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
667
4.30k
       SI != SE; 
++SI2.61k
)
668
2.61k
    delPhiValues(BB, *SI);
669
1.68k
670
1.68k
  if (DA)
671
1.38k
    DA->removeValue(Term);
672
1.68k
  Term->eraseFromParent();
673
1.68k
}
674
675
/// Let node exit(s) point to NewExit
676
void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
677
1.08k
                                bool IncludeDominator) {
678
1.08k
  if (Node->isSubRegion()) {
679
122
    Region *SubRegion = Node->getNodeAs<Region>();
680
122
    BasicBlock *OldExit = SubRegion->getExit();
681
122
    BasicBlock *Dominator = nullptr;
682
122
683
122
    // Find all the edges from the sub region to the exit
684
357
    for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) {
685
235
      // Incrememt BBI before mucking with BB's terminator.
686
235
      BasicBlock *BB = *BBI++;
687
235
688
235
      if (!SubRegion->contains(BB))
689
39
        continue;
690
196
691
196
      // Modify the edges to point to the new exit
692
196
      delPhiValues(BB, OldExit);
693
196
      BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
694
196
      addPhiValues(BB, NewExit);
695
196
696
196
      // Find the new dominator (if requested)
697
196
      if (IncludeDominator) {
698
110
        if (!Dominator)
699
62
          Dominator = BB;
700
48
        else
701
48
          Dominator = DT->findNearestCommonDominator(Dominator, BB);
702
110
      }
703
196
    }
704
122
705
122
    // Change the dominator (if requested)
706
122
    if (Dominator)
707
62
      DT->changeImmediateDominator(NewExit, Dominator);
708
122
709
122
    // Update the region info
710
122
    SubRegion->replaceExit(NewExit);
711
961
  } else {
712
961
    BasicBlock *BB = Node->getNodeAs<BasicBlock>();
713
961
    killTerminator(BB);
714
961
    BranchInst::Create(NewExit, BB);
715
961
    addPhiValues(BB, NewExit);
716
961
    if (IncludeDominator)
717
85
      DT->changeImmediateDominator(NewExit, BB);
718
961
  }
719
1.08k
}
720
721
/// Create a new flow node and update dominator tree and region info
722
363
BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
723
363
  LLVMContext &Context = Func->getContext();
724
363
  BasicBlock *Insert = Order.empty() ? 
ParentRegion->getExit()94
:
725
363
                       
Order.back()->getEntry()269
;
726
363
  BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
727
363
                                        Func, Insert);
728
363
  DT->addNewBlock(Flow, Dominator);
729
363
  ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
730
363
  return Flow;
731
363
}
732
733
/// Create a new or reuse the previous node as flow node
734
1.09k
BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
735
1.09k
  BasicBlock *Entry = PrevNode->getEntry();
736
1.09k
737
1.09k
  if (!PrevNode->isSubRegion()) {
738
1.09k
    killTerminator(Entry);
739
1.09k
    if (!NeedEmpty || 
Entry->getFirstInsertionPt() == Entry->end()0
)
740
1.09k
      return Entry;
741
0
  }
742
0
743
0
  // create a new flow node
744
0
  BasicBlock *Flow = getNextFlow(Entry);
745
0
746
0
  // and wire it up
747
0
  changeExit(PrevNode, Flow, true);
748
0
  PrevNode = ParentRegion->getBBNode(Flow);
749
0
  return Flow;
750
0
}
751
752
/// Returns the region exit if possible, otherwise just a new flow node
753
BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
754
1.09k
                                        bool ExitUseAllowed) {
755
1.09k
  if (!Order.empty() || 
!ExitUseAllowed822
)
756
363
    return getNextFlow(Flow);
757
728
758
728
  BasicBlock *Exit = ParentRegion->getExit();
759
728
  DT->changeImmediateDominator(Exit, Flow);
760
728
  addPhiValues(Flow, Exit);
761
728
  return Exit;
762
728
}
763
764
/// Set the previous node
765
1.09k
void StructurizeCFG::setPrevNode(BasicBlock *BB) {
766
1.09k
  PrevNode = ParentRegion->contains(BB) ? 
ParentRegion->getBBNode(BB)363
767
1.09k
                                        : 
nullptr728
;
768
1.09k
}
769
770
/// Does BB dominate all the predicates of Node?
771
280
bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
772
280
  BBPredicates &Preds = Predicates[Node->getEntry()];
773
367
  return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
774
367
    return DT->dominates(BB, Pred.first);
775
367
  });
776
280
}
777
778
/// Can we predict that this node will always be called?
779
2.00k
bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
780
2.00k
  BBPredicates &Preds = Predicates[Node->getEntry()];
781
2.00k
  bool Dominated = false;
782
2.00k
783
2.00k
  // Regionentry is always true
784
2.00k
  if (!PrevNode)
785
993
    return true;
786
1.01k
787
1.09k
  
for (std::pair<BasicBlock*, Value*> Pred : Preds)1.01k
{
788
1.09k
    BasicBlock *BB = Pred.first;
789
1.09k
    Value *V = Pred.second;
790
1.09k
791
1.09k
    if (V != BoolTrue)
792
888
      return false;
793
203
794
203
    if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
795
172
      Dominated = true;
796
203
  }
797
1.01k
798
1.01k
  // TODO: The dominator check is too strict
799
1.01k
  
return Dominated128
;
800
1.01k
}
801
802
/// Take one node from the order vector and wire it up
803
void StructurizeCFG::wireFlow(bool ExitUseAllowed,
804
1.81k
                              BasicBlock *LoopEnd) {
805
1.81k
  RegionNode *Node = Order.pop_back_val();
806
1.81k
  Visited.insert(Node->getEntry());
807
1.81k
808
1.81k
  if (isPredictableTrue(Node)) {
809
918
    // Just a linear flow
810
918
    if (PrevNode) {
811
112
      changeExit(PrevNode, Node->getEntry(), true);
812
112
    }
813
918
    PrevNode = Node;
814
918
  } else {
815
893
    // Insert extra prefix node (or reuse last one)
816
893
    BasicBlock *Flow = needPrefix(false);
817
893
818
893
    // Insert extra postfix node (or use exit instead)
819
893
    BasicBlock *Entry = Node->getEntry();
820
893
    BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
821
893
822
893
    // let it point to entry and next block
823
893
    Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
824
893
    addPhiValues(Flow, Entry);
825
893
    DT->changeImmediateDominator(Entry, Flow);
826
893
827
893
    PrevNode = Node;
828
987
    while (!Order.empty() && 
!Visited.count(LoopEnd)300
&&
829
987
           
dominatesPredicates(Entry, Order.back())280
) {
830
94
      handleLoops(false, LoopEnd);
831
94
    }
832
893
833
893
    changeExit(PrevNode, Next, false);
834
893
    setPrevNode(Next);
835
893
  }
836
1.81k
}
837
838
void StructurizeCFG::handleLoops(bool ExitUseAllowed,
839
1.81k
                                 BasicBlock *LoopEnd) {
840
1.81k
  RegionNode *Node = Order.back();
841
1.81k
  BasicBlock *LoopStart = Node->getEntry();
842
1.81k
843
1.81k
  if (!Loops.count(LoopStart)) {
844
1.61k
    wireFlow(ExitUseAllowed, LoopEnd);
845
1.61k
    return;
846
1.61k
  }
847
198
848
198
  if (!isPredictableTrue(Node))
849
0
    LoopStart = needPrefix(true);
850
198
851
198
  LoopEnd = Loops[Node->getEntry()];
852
198
  wireFlow(false, LoopEnd);
853
328
  while (!Visited.count(LoopEnd)) {
854
130
    handleLoops(false, LoopEnd);
855
130
  }
856
198
857
198
  // If the start of the loop is the entry block, we can't branch to it so
858
198
  // insert a new dummy entry block.
859
198
  Function *LoopFunc = LoopStart->getParent();
860
198
  if (LoopStart == &LoopFunc->getEntryBlock()) {
861
0
    LoopStart->setName("entry.orig");
862
0
863
0
    BasicBlock *NewEntry =
864
0
      BasicBlock::Create(LoopStart->getContext(),
865
0
                         "entry",
866
0
                         LoopFunc,
867
0
                         LoopStart);
868
0
    BranchInst::Create(LoopStart, NewEntry);
869
0
    DT->setNewRoot(NewEntry);
870
0
  }
871
198
872
198
  // Create an extra loop end node
873
198
  LoopEnd = needPrefix(false);
874
198
  BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
875
198
  LoopConds.push_back(BranchInst::Create(Next, LoopStart,
876
198
                                         BoolUndef, LoopEnd));
877
198
  addPhiValues(LoopEnd, LoopStart);
878
198
  setPrevNode(Next);
879
198
}
880
881
/// After this function control flow looks like it should be, but
882
/// branches and PHI nodes only have undefined conditions.
883
806
void StructurizeCFG::createFlow() {
884
806
  BasicBlock *Exit = ParentRegion->getExit();
885
806
  bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
886
806
887
806
  DeletedPhis.clear();
888
806
  AddedPhis.clear();
889
806
  Conditions.clear();
890
806
  LoopConds.clear();
891
806
892
806
  PrevNode = nullptr;
893
806
  Visited.clear();
894
806
895
2.39k
  while (!Order.empty()) {
896
1.58k
    handleLoops(EntryDominatesExit, nullptr);
897
1.58k
  }
898
806
899
806
  if (PrevNode)
900
78
    changeExit(PrevNode, Exit, EntryDominatesExit);
901
806
  else
902
806
    assert(EntryDominatesExit);
903
806
}
904
905
/// Handle a rare case where the disintegrated nodes instructions
906
/// no longer dominate all their uses. Not sure if this is really necessary
907
806
void StructurizeCFG::rebuildSSA() {
908
806
  SSAUpdater Updater;
909
806
  for (BasicBlock *BB : ParentRegion->blocks())
910
19.8k
    
for (Instruction &I : *BB)2.44k
{
911
19.8k
      bool Initialized = false;
912
19.8k
      // We may modify the use list as we iterate over it, so be careful to
913
19.8k
      // compute the next element in the use list at the top of the loop.
914
42.1k
      for (auto UI = I.use_begin(), E = I.use_end(); UI != E;) {
915
22.3k
        Use &U = *UI++;
916
22.3k
        Instruction *User = cast<Instruction>(U.getUser());
917
22.3k
        if (User->getParent() == BB) {
918
14.7k
          continue;
919
14.7k
        } else 
if (PHINode *7.50k
UserPN7.50k
= dyn_cast<PHINode>(User)) {
920
3.53k
          if (UserPN->getIncomingBlock(U) == BB)
921
3.37k
            continue;
922
4.13k
        }
923
4.13k
924
4.13k
        if (DT->dominates(&I, User))
925
4.07k
          continue;
926
57
927
57
        if (!Initialized) {
928
54
          Value *Undef = UndefValue::get(I.getType());
929
54
          Updater.Initialize(I.getType(), "");
930
54
          Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
931
54
          Updater.AddAvailableValue(BB, &I);
932
54
          Initialized = true;
933
54
        }
934
57
        Updater.RewriteUseAfterInsertions(U);
935
57
      }
936
19.8k
    }
937
806
}
938
939
static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID,
940
1.26k
                                   const LegacyDivergenceAnalysis &DA) {
941
1.26k
  // Bool for if all sub-regions are uniform.
942
1.26k
  bool SubRegionsAreUniform = true;
943
1.26k
  // Count of how many direct children are conditional.
944
1.26k
  unsigned ConditionalDirectChildren = 0;
945
1.26k
946
1.95k
  for (auto E : R->elements()) {
947
1.95k
    if (!E->isSubRegion()) {
948
1.85k
      auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator());
949
1.85k
      if (!Br || !Br->isConditional())
950
559
        continue;
951
1.29k
952
1.29k
      if (!DA.isUniform(Br))
953
669
        return false;
954
627
955
627
      // One of our direct children is conditional.
956
627
      ConditionalDirectChildren++;
957
627
958
627
      LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName()
959
627
                        << " has uniform terminator\n");
960
627
    } else {
961
96
      // Explicitly refuse to treat regions as uniform if they have non-uniform
962
96
      // subregions. We cannot rely on DivergenceAnalysis for branches in
963
96
      // subregions because those branches may have been removed and re-created,
964
96
      // so we look for our metadata instead.
965
96
      //
966
96
      // Warning: It would be nice to treat regions as uniform based only on
967
96
      // their direct child basic blocks' terminators, regardless of whether
968
96
      // subregions are uniform or not. However, this requires a very careful
969
96
      // look at SIAnnotateControlFlow to make sure nothing breaks there.
970
191
      for (auto BB : E->getNodeAs<Region>()->blocks()) {
971
191
        auto Br = dyn_cast<BranchInst>(BB->getTerminator());
972
191
        if (!Br || !Br->isConditional())
973
61
          continue;
974
130
975
130
        if (!Br->getMetadata(UniformMDKindID)) {
976
20
          // Early exit if we cannot have relaxed uniform regions.
977
20
          if (!RelaxedUniformRegions)
978
16
            return false;
979
4
980
4
          SubRegionsAreUniform = false;
981
4
          break;
982
4
        }
983
130
      }
984
96
    }
985
1.95k
  }
986
1.26k
987
1.26k
  // Our region is uniform if:
988
1.26k
  // 1. All conditional branches that are direct children are uniform (checked
989
1.26k
  // above).
990
1.26k
  // 2. And either:
991
1.26k
  //   a. All sub-regions are uniform.
992
1.26k
  //   b. There is one or less conditional branches among the direct children.
993
1.26k
  
return 584
SubRegionsAreUniform584
||
(ConditionalDirectChildren <= 1)1
;
994
1.26k
}
995
996
/// Run the transformation for each region found
997
28.9k
bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
998
28.9k
  if (R->isTopLevelRegion())
999
27.5k
    return false;
1000
1.39k
1001
1.39k
  DA = nullptr;
1002
1.39k
1003
1.39k
  if (SkipUniformRegions) {
1004
1.26k
    // TODO: We could probably be smarter here with how we handle sub-regions.
1005
1.26k
    // We currently rely on the fact that metadata is set by earlier invocations
1006
1.26k
    // of the pass on sub-regions, and that this metadata doesn't get lost --
1007
1.26k
    // but we shouldn't rely on metadata for correctness!
1008
1.26k
    unsigned UniformMDKindID =
1009
1.26k
        R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");
1010
1.26k
    DA = &getAnalysis<LegacyDivergenceAnalysis>();
1011
1.26k
1012
1.26k
    if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) {
1013
584
      LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R
1014
584
                        << '\n');
1015
584
1016
584
      // Mark all direct child block terminators as having been treated as
1017
584
      // uniform. To account for a possible future in which non-uniform
1018
584
      // sub-regions are treated more cleverly, indirect children are not
1019
584
      // marked as uniform.
1020
584
      MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
1021
1.21k
      for (RegionNode *E : R->elements()) {
1022
1.21k
        if (E->isSubRegion())
1023
70
          continue;
1024
1.14k
1025
1.14k
        if (Instruction *Term = E->getEntry()->getTerminator())
1026
1.14k
          Term->setMetadata(UniformMDKindID, MD);
1027
1.14k
      }
1028
584
1029
584
      return false;
1030
584
    }
1031
806
  }
1032
806
1033
806
  Func = R->getEntry()->getParent();
1034
806
  ParentRegion = R;
1035
806
1036
806
  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1037
806
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1038
806
1039
806
  orderNodes();
1040
806
  collectInfos();
1041
806
  createFlow();
1042
806
  insertConditions(false);
1043
806
  insertConditions(true);
1044
806
  setPhiValues();
1045
806
  rebuildSSA();
1046
806
1047
806
  // Cleanup
1048
806
  Order.clear();
1049
806
  Visited.clear();
1050
806
  DeletedPhis.clear();
1051
806
  AddedPhis.clear();
1052
806
  Predicates.clear();
1053
806
  Conditions.clear();
1054
806
  Loops.clear();
1055
806
  LoopPreds.clear();
1056
806
  LoopConds.clear();
1057
806
1058
806
  return true;
1059
806
}
1060
1061
2.72k
Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
1062
2.72k
  return new StructurizeCFG(SkipUniformRegions);
1063
2.72k
}