Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/FlattenCFG.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- FlatternCFG.cpp - Code to perform CFG flattening -------------------===//
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
// Reduce conditional branches in CFG.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/ADT/SmallPtrSet.h"
14
#include "llvm/Analysis/AliasAnalysis.h"
15
#include "llvm/Transforms/Utils/Local.h"
16
#include "llvm/Analysis/ValueTracking.h"
17
#include "llvm/IR/BasicBlock.h"
18
#include "llvm/IR/IRBuilder.h"
19
#include "llvm/IR/InstrTypes.h"
20
#include "llvm/IR/Instruction.h"
21
#include "llvm/IR/Instructions.h"
22
#include "llvm/IR/Value.h"
23
#include "llvm/Support/Casting.h"
24
#include "llvm/Support/Debug.h"
25
#include "llvm/Support/raw_ostream.h"
26
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
27
#include <cassert>
28
29
using namespace llvm;
30
31
#define DEBUG_TYPE "flattencfg"
32
33
namespace {
34
35
class FlattenCFGOpt {
36
  AliasAnalysis *AA;
37
38
  /// Use parallel-and or parallel-or to generate conditions for
39
  /// conditional branches.
40
  bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder);
41
42
  /// If \param BB is the merge block of an if-region, attempt to merge
43
  /// the if-region with an adjacent if-region upstream if two if-regions
44
  /// contain identical instructions.
45
  bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder);
46
47
  /// Compare a pair of blocks: \p Block1 and \p Block2, which
48
  /// are from two if-regions whose entry blocks are \p Head1 and \p
49
  /// Head2.  \returns true if \p Block1 and \p Block2 contain identical
50
  /// instructions, and have no memory reference alias with \p Head2.
51
  /// This is used as a legality check for merging if-regions.
52
  bool CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
53
                            BasicBlock *Block1, BasicBlock *Block2);
54
55
public:
56
30.4k
  FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {}
57
58
  bool run(BasicBlock *BB);
59
};
60
61
} // end anonymous namespace
62
63
/// If \param [in] BB has more than one predecessor that is a conditional
64
/// branch, attempt to use parallel and/or for the branch condition. \returns
65
/// true on success.
66
///
67
/// Before:
68
///   ......
69
///   %cmp10 = fcmp une float %tmp1, %tmp2
70
///   br i1 %cmp1, label %if.then, label %lor.rhs
71
///
72
/// lor.rhs:
73
///   ......
74
///   %cmp11 = fcmp une float %tmp3, %tmp4
75
///   br i1 %cmp11, label %if.then, label %ifend
76
///
77
/// if.end:  // the merge block
78
///   ......
79
///
80
/// if.then: // has two predecessors, both of them contains conditional branch.
81
///   ......
82
///   br label %if.end;
83
///
84
/// After:
85
///  ......
86
///  %cmp10 = fcmp une float %tmp1, %tmp2
87
///  ......
88
///  %cmp11 = fcmp une float %tmp3, %tmp4
89
///  %cmp12 = or i1 %cmp10, %cmp11    // parallel-or mode.
90
///  br i1 %cmp12, label %if.then, label %ifend
91
///
92
///  if.end:
93
///    ......
94
///
95
///  if.then:
96
///    ......
97
///    br label %if.end;
98
///
99
///  Current implementation handles two cases.
100
///  Case 1: \param BB is on the else-path.
101
///
102
///          BB1
103
///        /     |
104
///       BB2    |
105
///      /   \   |
106
///     BB3   \  |     where, BB1, BB2 contain conditional branches.
107
///      \    |  /     BB3 contains unconditional branch.
108
///       \   | /      BB4 corresponds to \param BB which is also the merge.
109
///  BB => BB4
110
///
111
///
112
///  Corresponding source code:
113
///
114
///  if (a == b && c == d)
115
///    statement; // BB3
116
///
117
///  Case 2: \param BB BB is on the then-path.
118
///
119
///             BB1
120
///          /      |
121
///         |      BB2
122
///         \    /    |  where BB1, BB2 contain conditional branches.
123
///  BB =>   BB3      |  BB3 contains unconditiona branch and corresponds
124
///           \     /    to \param BB.  BB4 is the merge.
125
///             BB4
126
///
127
///  Corresponding source code:
128
///
129
///  if (a == b || c == d)
130
///    statement;  // BB3
131
///
132
///  In both cases,  \param BB is the common successor of conditional branches.
133
///  In Case 1, \param BB (BB4) has an unconditional branch (BB3) as
134
///  its predecessor.  In Case 2, \param BB (BB3) only has conditional branches
135
///  as its predecessors.
136
30.4k
bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder) {
137
30.4k
  PHINode *PHI = dyn_cast<PHINode>(BB->begin());
138
30.4k
  if (PHI)
139
669
    return false; // For simplicity, avoid cases containing PHI nodes.
140
29.7k
141
29.7k
  BasicBlock *LastCondBlock = nullptr;
142
29.7k
  BasicBlock *FirstCondBlock = nullptr;
143
29.7k
  BasicBlock *UnCondBlock = nullptr;
144
29.7k
  int Idx = -1;
145
29.7k
146
29.7k
  // Check predecessors of \param BB.
147
29.7k
  SmallPtrSet<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
148
29.7k
  for (SmallPtrSetIterator<BasicBlock *> PI = Preds.begin(), PE = Preds.end();
149
31.9k
       PI != PE; 
++PI2.18k
) {
150
2.62k
    BasicBlock *Pred = *PI;
151
2.62k
    BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator());
152
2.62k
153
2.62k
    // All predecessors should terminate with a branch.
154
2.62k
    if (!PBI)
155
0
      return false;
156
2.62k
157
2.62k
    BasicBlock *PP = Pred->getSinglePredecessor();
158
2.62k
159
2.62k
    if (PBI->isUnconditional()) {
160
546
      // Case 1: Pred (BB3) is an unconditional block, it should
161
546
      // have a single predecessor (BB2) that is also a predecessor
162
546
      // of \param BB (BB4) and should not have address-taken.
163
546
      // There should exist only one such unconditional
164
546
      // branch among the predecessors.
165
546
      if (UnCondBlock || 
!PP542
||
(Preds.count(PP) == 0)393
||
166
546
          
Pred->hasAddressTaken()326
)
167
220
        return false;
168
326
169
326
      UnCondBlock = Pred;
170
326
      continue;
171
326
    }
172
2.07k
173
2.07k
    // Only conditional branches are allowed beyond this point.
174
2.07k
    assert(PBI->isConditional());
175
2.07k
176
2.07k
    // Condition's unique use should be the branch instruction.
177
2.07k
    Value *PC = PBI->getCondition();
178
2.07k
    if (!PC || !PC->hasOneUse())
179
145
      return false;
180
1.93k
181
1.93k
    if (PP && 
Preds.count(PP)299
) {
182
56
      // These are internal condition blocks to be merged from, e.g.,
183
56
      // BB2 in both cases.
184
56
      // Should not be address-taken.
185
56
      if (Pred->hasAddressTaken())
186
0
        return false;
187
56
188
56
      // Instructions in the internal condition blocks should be safe
189
56
      // to hoist up.
190
56
      for (BasicBlock::iterator BI = Pred->begin(), BE = PBI->getIterator();
191
126
           BI != BE;) {
192
101
        Instruction *CI = &*BI++;
193
101
        if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI))
194
31
          return false;
195
101
      }
196
1.87k
    } else {
197
1.87k
      // This is the condition block to be merged into, e.g. BB1 in
198
1.87k
      // both cases.
199
1.87k
      if (FirstCondBlock)
200
39
        return false;
201
1.83k
      FirstCondBlock = Pred;
202
1.83k
    }
203
1.93k
204
1.93k
    // Find whether BB is uniformly on the true (or false) path
205
1.93k
    // for all of its predecessors.
206
1.93k
    BasicBlock *PS1 = PBI->getSuccessor(0);
207
1.86k
    BasicBlock *PS2 = PBI->getSuccessor(1);
208
1.86k
    BasicBlock *PS = (PS1 == BB) ? 
PS2969
:
PS1893
;
209
1.86k
    int CIdx = (PS1 == BB) ? 
0969
:
1893
;
210
1.86k
211
1.86k
    if (Idx == -1)
212
1.83k
      Idx = CIdx;
213
23
    else if (CIdx != Idx)
214
1
      return false;
215
1.86k
216
1.86k
    // PS is the successor which is not BB. Check successors to identify
217
1.86k
    // the last conditional branch.
218
1.86k
    if (Preds.count(PS) == 0) {
219
1.40k
      // Case 2.
220
1.40k
      LastCondBlock = Pred;
221
1.40k
    } else {
222
461
      // Case 1
223
461
      BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
224
461
      if (BPS && BPS->isUnconditional()) {
225
299
        // Case 1: PS(BB3) should be an unconditional branch.
226
299
        LastCondBlock = Pred;
227
299
      }
228
461
    }
229
1.86k
  }
230
29.7k
231
29.7k
  
if (29.2k
!FirstCondBlock29.2k
||
!LastCondBlock1.77k
||
(FirstCondBlock == LastCondBlock)1.64k
)
232
29.2k
    return false;
233
14
234
14
  Instruction *TBB = LastCondBlock->getTerminator();
235
14
  BasicBlock *PS1 = TBB->getSuccessor(0);
236
14
  BasicBlock *PS2 = TBB->getSuccessor(1);
237
14
  BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
238
14
  BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
239
14
240
14
  // If PS1 does not jump into PS2, but PS2 jumps into PS1,
241
14
  // attempt branch inversion.
242
14
  if (!PBI1 || 
!PBI1->isUnconditional()7
||
243
14
      
(PS1->getTerminator()->getSuccessor(0) != PS2)7
) {
244
7
    // Check whether PS2 jumps into PS1.
245
7
    if (!PBI2 || 
!PBI2->isUnconditional()2
||
246
7
        
(PS2->getTerminator()->getSuccessor(0) != PS1)2
)
247
6
      return false;
248
1
249
1
    // Do branch inversion.
250
1
    BasicBlock *CurrBlock = LastCondBlock;
251
1
    bool EverChanged = false;
252
2
    for (; CurrBlock != FirstCondBlock;
253
1
         CurrBlock = CurrBlock->getSinglePredecessor()) {
254
1
      BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator());
255
1
      CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
256
1
      if (!CI)
257
1
        continue;
258
0
259
0
      CmpInst::Predicate Predicate = CI->getPredicate();
260
0
      // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
261
0
      if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
262
0
        CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
263
0
        BI->swapSuccessors();
264
0
        EverChanged = true;
265
0
      }
266
0
    }
267
1
    return EverChanged;
268
1
  }
269
7
270
7
  // PS1 must have a conditional branch.
271
7
  if (!PBI1 || !PBI1->isUnconditional())
272
0
    return false;
273
7
274
7
  // PS2 should not contain PHI node.
275
7
  PHI = dyn_cast<PHINode>(PS2->begin());
276
7
  if (PHI)
277
0
    return false;
278
7
279
7
  // Do the transformation.
280
7
  BasicBlock *CB;
281
7
  BranchInst *PBI = dyn_cast<BranchInst>(FirstCondBlock->getTerminator());
282
7
  bool Iteration = true;
283
7
  IRBuilder<>::InsertPointGuard Guard(Builder);
284
7
  Value *PC = PBI->getCondition();
285
7
286
15
  do {
287
15
    CB = PBI->getSuccessor(1 - Idx);
288
15
    // Delete the conditional branch.
289
15
    FirstCondBlock->getInstList().pop_back();
290
15
    FirstCondBlock->getInstList()
291
15
        .splice(FirstCondBlock->end(), CB->getInstList());
292
15
    PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
293
15
    Value *CC = PBI->getCondition();
294
15
    // Merge conditions.
295
15
    Builder.SetInsertPoint(PBI);
296
15
    Value *NC;
297
15
    if (Idx == 0)
298
0
      // Case 2, use parallel or.
299
0
      NC = Builder.CreateOr(PC, CC);
300
15
    else
301
15
      // Case 1, use parallel and.
302
15
      NC = Builder.CreateAnd(PC, CC);
303
15
304
15
    PBI->replaceUsesOfWith(CC, NC);
305
15
    PC = NC;
306
15
    if (CB == LastCondBlock)
307
7
      Iteration = false;
308
15
    // Remove internal conditional branches.
309
15
    CB->dropAllReferences();
310
15
    // make CB unreachable and let downstream to delete the block.
311
15
    new UnreachableInst(CB->getContext(), CB);
312
15
  } while (Iteration);
313
7
314
7
  LLVM_DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
315
7
  return true;
316
7
}
317
318
/// Compare blocks from two if-regions, where \param Head1 is the entry of the
319
/// 1st if-region. \param Head2 is the entry of the 2nd if-region. \param
320
/// Block1 is a block in the 1st if-region to compare. \param Block2 is a block
321
//  in the 2nd if-region to compare.  \returns true if \param Block1 and \param
322
/// Block2 have identical instructions and do not have memory reference alias
323
/// with \param Head2.
324
bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
325
                                         BasicBlock *Block1,
326
21
                                         BasicBlock *Block2) {
327
21
  Instruction *PTI2 = Head2->getTerminator();
328
21
  Instruction *PBI2 = &Head2->front();
329
21
330
21
  bool eq1 = (Block1 == Head1);
331
21
  bool eq2 = (Block2 == Head2);
332
21
  if (eq1 || 
eq217
) {
333
4
    // An empty then-path or else-path.
334
4
    return (eq1 == eq2);
335
4
  }
336
17
337
17
  // Check whether instructions in Block1 and Block2 are identical
338
17
  // and do not alias with instructions in Head2.
339
17
  BasicBlock::iterator iter1 = Block1->begin();
340
17
  BasicBlock::iterator end1 = Block1->getTerminator()->getIterator();
341
17
  BasicBlock::iterator iter2 = Block2->begin();
342
17
  BasicBlock::iterator end2 = Block2->getTerminator()->getIterator();
343
17
344
21
  while (true) {
345
21
    if (iter1 == end1) {
346
6
      if (iter2 != end2)
347
2
        return false;
348
4
      break;
349
4
    }
350
15
351
15
    if (!iter1->isIdenticalTo(&*iter2))
352
11
      return false;
353
4
354
4
    // Illegal to remove instructions with side effects except
355
4
    // non-volatile stores.
356
4
    if (iter1->mayHaveSideEffects()) {
357
1
      Instruction *CurI = &*iter1;
358
1
      StoreInst *SI = dyn_cast<StoreInst>(CurI);
359
1
      if (!SI || SI->isVolatile())
360
0
        return false;
361
4
    }
362
4
363
4
    // For simplicity and speed, data dependency check can be
364
4
    // avoided if read from memory doesn't exist.
365
4
    if (iter1->mayReadFromMemory())
366
0
      return false;
367
4
368
4
    if (iter1->mayWriteToMemory()) {
369
8
      for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; 
++BI7
) {
370
7
        if (BI->mayReadFromMemory() || 
BI->mayWriteToMemory()3
) {
371
4
          // Check alias with Head2.
372
4
          if (!AA || AA->alias(&*iter1, &*BI))
373
0
            return false;
374
4
        }
375
7
      }
376
1
    }
377
4
    ++iter1;
378
4
    ++iter2;
379
4
  }
380
17
381
17
  
return true4
;
382
17
}
383
384
/// Check whether \param BB is the merge block of a if-region.  If yes, check
385
/// whether there exists an adjacent if-region upstream, the two if-regions
386
/// contain identical instructions and can be legally merged.  \returns true if
387
/// the two if-regions are merged.
388
///
389
/// From:
390
/// if (a)
391
///   statement;
392
/// if (b)
393
///   statement;
394
///
395
/// To:
396
/// if (a || b)
397
///   statement;
398
30.3k
bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {
399
30.3k
  BasicBlock *IfTrue2, *IfFalse2;
400
30.3k
  Value *IfCond2 = GetIfCondition(BB, IfTrue2, IfFalse2);
401
30.3k
  Instruction *CInst2 = dyn_cast_or_null<Instruction>(IfCond2);
402
30.3k
  if (!CInst2)
403
29.7k
    return false;
404
657
405
657
  BasicBlock *SecondEntryBlock = CInst2->getParent();
406
657
  if (SecondEntryBlock->hasAddressTaken())
407
0
    return false;
408
657
409
657
  BasicBlock *IfTrue1, *IfFalse1;
410
657
  Value *IfCond1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
411
657
  Instruction *CInst1 = dyn_cast_or_null<Instruction>(IfCond1);
412
657
  if (!CInst1)
413
640
    return false;
414
17
415
17
  BasicBlock *FirstEntryBlock = CInst1->getParent();
416
17
417
17
  // Either then-path or else-path should be empty.
418
17
  if ((IfTrue1 != FirstEntryBlock) && (IfFalse1 != FirstEntryBlock))
419
0
    return false;
420
17
  if ((IfTrue2 != SecondEntryBlock) && (IfFalse2 != SecondEntryBlock))
421
0
    return false;
422
17
423
17
  Instruction *PTI2 = SecondEntryBlock->getTerminator();
424
17
  Instruction *PBI2 = &SecondEntryBlock->front();
425
17
426
17
  if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfTrue1,
427
17
                            IfTrue2))
428
13
    return false;
429
4
430
4
  if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfFalse1,
431
4
                            IfFalse2))
432
0
    return false;
433
4
434
4
  // Check whether \param SecondEntryBlock has side-effect and is safe to
435
4
  // speculate.
436
11
  
for (BasicBlock::iterator BI(PBI2), BE(PTI2); 4
BI != BE;
++BI7
) {
437
10
    Instruction *CI = &*BI;
438
10
    if (isa<PHINode>(CI) || 
CI->mayHaveSideEffects()7
||
439
10
        
!isSafeToSpeculativelyExecute(CI)7
)
440
3
      return false;
441
10
  }
442
4
443
4
  // Merge \param SecondEntryBlock into \param FirstEntryBlock.
444
4
  FirstEntryBlock->getInstList().pop_back();
445
1
  FirstEntryBlock->getInstList()
446
1
      .splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList());
447
1
  BranchInst *PBI = dyn_cast<BranchInst>(FirstEntryBlock->getTerminator());
448
1
  Value *CC = PBI->getCondition();
449
1
  BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
450
1
  BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
451
1
  Builder.SetInsertPoint(PBI);
452
1
  Value *NC = Builder.CreateOr(CInst1, CC);
453
1
  PBI->replaceUsesOfWith(CC, NC);
454
1
  Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
455
1
456
1
  // Remove IfTrue1
457
1
  if (IfTrue1 != FirstEntryBlock) {
458
1
    IfTrue1->dropAllReferences();
459
1
    IfTrue1->eraseFromParent();
460
1
  }
461
1
462
1
  // Remove IfFalse1
463
1
  if (IfFalse1 != FirstEntryBlock) {
464
0
    IfFalse1->dropAllReferences();
465
0
    IfFalse1->eraseFromParent();
466
0
  }
467
1
468
1
  // Remove \param SecondEntryBlock
469
1
  SecondEntryBlock->dropAllReferences();
470
1
  SecondEntryBlock->eraseFromParent();
471
1
  LLVM_DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
472
1
  return true;
473
4
}
474
475
30.4k
bool FlattenCFGOpt::run(BasicBlock *BB) {
476
30.4k
  assert(BB && BB->getParent() && "Block not embedded in function!");
477
30.4k
  assert(BB->getTerminator() && "Degenerate basic block encountered!");
478
30.4k
479
30.4k
  IRBuilder<> Builder(BB);
480
30.4k
481
30.4k
  if (FlattenParallelAndOr(BB, Builder) || 
MergeIfRegion(BB, Builder)30.3k
)
482
8
    return true;
483
30.3k
  return false;
484
30.3k
}
485
486
/// FlattenCFG - This function is used to flatten a CFG.  For
487
/// example, it uses parallel-and and parallel-or mode to collapse
488
/// if-conditions and merge if-regions with identical statements.
489
30.4k
bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) {
490
30.4k
  return FlattenCFGOpt(AA).run(BB);
491
30.4k
}