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