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
29using namespace llvm;
30
31#define DEBUG_TYPE "flattencfg"
32
33namespace {
34
35class 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, where \p Head2 is the entry block of the 2nd
49  /// if-region.  \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 *Block1, BasicBlock *Block2,
53                            BasicBlock *Head2);
54
55public:
56  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 %cmp10, 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: 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 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: 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 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, BB is the common successor of conditional branches.
133///  In Case 1, BB (BB4) has an unconditional branch (BB3) as
134///  its predecessor.  In Case 2, BB (BB3) only has conditional branches
135///  as its predecessors.
136bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder) {
137  PHINode *PHI = dyn_cast<PHINode>(BB->begin());
138  if (PHI)
139    return false; // For simplicity, avoid cases containing PHI nodes.
140
141  BasicBlock *LastCondBlock = nullptr;
142  BasicBlock *FirstCondBlock = nullptr;
143  BasicBlock *UnCondBlock = nullptr;
144  int Idx = -1;
145
146  // Check predecessors of \param BB.
147  SmallPtrSet<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
148  for (BasicBlock *Pred : Preds) {
149    BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator());
150
151    // All predecessors should terminate with a branch.
152    if (!PBI)
153      return false;
154
155    BasicBlock *PP = Pred->getSinglePredecessor();
156
157    if (PBI->isUnconditional()) {
158      // Case 1: Pred (BB3) is an unconditional block, it should
159      // have a single predecessor (BB2) that is also a predecessor
160      // of \param BB (BB4) and should not have address-taken.
161      // There should exist only one such unconditional
162      // branch among the predecessors.
163      if (UnCondBlock || !PP || !Preds.contains(PP) ||
164          Pred->hasAddressTaken())
165        return false;
166
167      UnCondBlock = Pred;
168      continue;
169    }
170
171    // Only conditional branches are allowed beyond this point.
172    assert(PBI->isConditional());
173
174    // Condition's unique use should be the branch instruction.
175    Value *PC = PBI->getCondition();
176    if (!PC || !PC->hasOneUse())
177      return false;
178
179    if (PP && Preds.count(PP)) {
180      // These are internal condition blocks to be merged from, e.g.,
181      // BB2 in both cases.
182      // Should not be address-taken.
183      if (Pred->hasAddressTaken())
184        return false;
185
186      // Instructions in the internal condition blocks should be safe
187      // to hoist up.
188      for (BasicBlock::iterator BI = Pred->begin(), BE = PBI->getIterator();
189           BI != BE;) {
190        Instruction *CI = &*BI++;
191        if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI))
192          return false;
193      }
194    } else {
195      // This is the condition block to be merged into, e.g. BB1 in
196      // both cases.
197      if (FirstCondBlock)
198        return false;
199      FirstCondBlock = Pred;
200    }
201
202    // Find whether BB is uniformly on the true (or false) path
203    // for all of its predecessors.
204    BasicBlock *PS1 = PBI->getSuccessor(0);
205    BasicBlock *PS2 = PBI->getSuccessor(1);
206    BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
207    int CIdx = (PS1 == BB) ? 0 : 1;
208
209    if (Idx == -1)
210      Idx = CIdx;
211    else if (CIdx != Idx)
212      return false;
213
214    // PS is the successor which is not BB. Check successors to identify
215    // the last conditional branch.
216    if (!Preds.contains(PS)) {
217      // Case 2.
218      LastCondBlock = Pred;
219    } else {
220      // Case 1
221      BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
222      if (BPS && BPS->isUnconditional()) {
223        // Case 1: PS(BB3) should be an unconditional branch.
224        LastCondBlock = Pred;
225      }
226    }
227  }
228
229  if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
230    return false;
231
232  Instruction *TBB = LastCondBlock->getTerminator();
233  BasicBlock *PS1 = TBB->getSuccessor(0);
234  BasicBlock *PS2 = TBB->getSuccessor(1);
235  BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
236  BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
237
238  // If PS1 does not jump into PS2, but PS2 jumps into PS1,
239  // attempt branch inversion.
240  if (!PBI1 || !PBI1->isUnconditional() ||
241      (PS1->getTerminator()->getSuccessor(0) != PS2)) {
242    // Check whether PS2 jumps into PS1.
243    if (!PBI2 || !PBI2->isUnconditional() ||
244        (PS2->getTerminator()->getSuccessor(0) != PS1))
245      return false;
246
247    // Do branch inversion.
248    BasicBlock *CurrBlock = LastCondBlock;
249    bool EverChanged = false;
250    for (; CurrBlock != FirstCondBlock;
251         CurrBlock = CurrBlock->getSinglePredecessor()) {
252      auto *BI = cast<BranchInst>(CurrBlock->getTerminator());
253      auto *CI = dyn_cast<CmpInst>(BI->getCondition());
254      if (!CI)
255        continue;
256
257      CmpInst::Predicate Predicate = CI->getPredicate();
258      // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
259      if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
260        CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
261        BI->swapSuccessors();
262        EverChanged = true;
263      }
264    }
265    return EverChanged;
266  }
267
268  // PS1 must have a conditional branch.
269  if (!PBI1 || !PBI1->isUnconditional())
270    return false;
271
272  // PS2 should not contain PHI node.
273  PHI = dyn_cast<PHINode>(PS2->begin());
274  if (PHI)
275    return false;
276
277  // Do the transformation.
278  BasicBlock *CB;
279  BranchInst *PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
280  bool Iteration = true;
281  IRBuilder<>::InsertPointGuard Guard(Builder);
282  Value *PC = PBI->getCondition();
283
284  do {
285    CB = PBI->getSuccessor(1 - Idx);
286    // Delete the conditional branch.
287    FirstCondBlock->back().eraseFromParent();
288    FirstCondBlock->splice(FirstCondBlock->end(), CB);
289    PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
290    Value *CC = PBI->getCondition();
291    // Merge conditions.
292    Builder.SetInsertPoint(PBI);
293    Value *NC;
294    if (Idx == 0)
295      // Case 2, use parallel or.
296      NC = Builder.CreateOr(PC, CC);
297    else
298      // Case 1, use parallel and.
299      NC = Builder.CreateAnd(PC, CC);
300
301    PBI->replaceUsesOfWith(CC, NC);
302    PC = NC;
303    if (CB == LastCondBlock)
304      Iteration = false;
305    // Remove internal conditional branches.
306    CB->dropAllReferences();
307    // make CB unreachable and let downstream to delete the block.
308    new UnreachableInst(CB->getContext(), CB);
309  } while (Iteration);
310
311  LLVM_DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
312  return true;
313}
314
315/// Compare blocks from two if-regions, where \param Head2 is the entry of the
316/// 2nd if-region. \param Block1 is a block in the 1st if-region to compare.
317/// \param Block2 is a block in the 2nd if-region to compare.  \returns true if
318/// Block1 and Block2 have identical instructions and do not have
319/// memory reference alias with Head2.
320bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2,
321                                         BasicBlock *Head2) {
322  Instruction *PTI2 = Head2->getTerminator();
323  Instruction *PBI2 = &Head2->front();
324
325  // Check whether instructions in Block1 and Block2 are identical
326  // and do not alias with instructions in Head2.
327  BasicBlock::iterator iter1 = Block1->begin();
328  BasicBlock::iterator end1 = Block1->getTerminator()->getIterator();
329  BasicBlock::iterator iter2 = Block2->begin();
330  BasicBlock::iterator end2 = Block2->getTerminator()->getIterator();
331
332  while (true) {
333    if (iter1 == end1) {
334      if (iter2 != end2)
335        return false;
336      break;
337    }
338
339    if (!iter1->isIdenticalTo(&*iter2))
340      return false;
341
342    // Illegal to remove instructions with side effects except
343    // non-volatile stores.
344    if (iter1->mayHaveSideEffects()) {
345      Instruction *CurI = &*iter1;
346      StoreInst *SI = dyn_cast<StoreInst>(CurI);
347      if (!SI || SI->isVolatile())
348        return false;
349    }
350
351    // For simplicity and speed, data dependency check can be
352    // avoided if read from memory doesn't exist.
353    if (iter1->mayReadFromMemory())
354      return false;
355
356    if (iter1->mayWriteToMemory()) {
357      for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
358        if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
359          // Check alias with Head2.
360          if (!AA || !AA->isNoAlias(&*iter1, &*BI))
361            return false;
362        }
363      }
364    }
365    ++iter1;
366    ++iter2;
367  }
368
369  return true;
370}
371
372/// Check whether \param BB is the merge block of a if-region.  If yes, check
373/// whether there exists an adjacent if-region upstream, the two if-regions
374/// contain identical instructions and can be legally merged.  \returns true if
375/// the two if-regions are merged.
376///
377/// From:
378/// if (a)
379///   statement;
380/// if (b)
381///   statement;
382///
383/// To:
384/// if (a || b)
385///   statement;
386///
387///
388/// And from:
389/// if (a)
390///   ;
391/// else
392///   statement;
393/// if (b)
394///   ;
395/// else
396///   statement;
397///
398/// To:
399/// if (a && b)
400///   ;
401/// else
402///   statement;
403///
404/// We always take the form of the first if-region. This means that if the
405/// statement in the first if-region, is in the "then-path", while in the second
406/// if-region it is in the "else-path", then we convert the second to the first
407/// form, by inverting the condition and the branch successors. The same
408/// approach goes for the opposite case.
409bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {
410  BasicBlock *IfTrue2, *IfFalse2;
411  BranchInst *DomBI2 = GetIfCondition(BB, IfTrue2, IfFalse2);
412  if (!DomBI2)
413    return false;
414  Instruction *CInst2 = dyn_cast<Instruction>(DomBI2->getCondition());
415  if (!CInst2)
416    return false;
417
418  BasicBlock *SecondEntryBlock = CInst2->getParent();
419  if (SecondEntryBlock->hasAddressTaken())
420    return false;
421
422  BasicBlock *IfTrue1, *IfFalse1;
423  BranchInst *DomBI1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
424  if (!DomBI1)
425    return false;
426  Instruction *CInst1 = dyn_cast<Instruction>(DomBI1->getCondition());
427  if (!CInst1)
428    return false;
429
430  BasicBlock *FirstEntryBlock = CInst1->getParent();
431  // Don't die trying to process degenerate/unreachable code.
432  if (FirstEntryBlock == SecondEntryBlock)
433    return false;
434
435  // Either then-path or else-path should be empty.
436  bool InvertCond2 = false;
437  BinaryOperator::BinaryOps CombineOp;
438  if (IfFalse1 == FirstEntryBlock) {
439    // The else-path is empty, so we must use "or" operation to combine the
440    // conditions.
441    CombineOp = BinaryOperator::Or;
442    if (IfFalse2 != SecondEntryBlock) {
443      if (IfTrue2 != SecondEntryBlock)
444        return false;
445
446      InvertCond2 = true;
447      std::swap(IfTrue2, IfFalse2);
448    }
449
450    if (!CompareIfRegionBlock(IfTrue1, IfTrue2, SecondEntryBlock))
451      return false;
452  } else if (IfTrue1 == FirstEntryBlock) {
453    // The then-path is empty, so we must use "and" operation to combine the
454    // conditions.
455    CombineOp = BinaryOperator::And;
456    if (IfTrue2 != SecondEntryBlock) {
457      if (IfFalse2 != SecondEntryBlock)
458        return false;
459
460      InvertCond2 = true;
461      std::swap(IfTrue2, IfFalse2);
462    }
463
464    if (!CompareIfRegionBlock(IfFalse1, IfFalse2, SecondEntryBlock))
465      return false;
466  } else
467    return false;
468
469  Instruction *PTI2 = SecondEntryBlock->getTerminator();
470  Instruction *PBI2 = &SecondEntryBlock->front();
471
472  // Check whether \param SecondEntryBlock has side-effect and is safe to
473  // speculate.
474  for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
475    Instruction *CI = &*BI;
476    if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||
477        !isSafeToSpeculativelyExecute(CI))
478      return false;
479  }
480
481  // Merge \param SecondEntryBlock into \param FirstEntryBlock.
482  FirstEntryBlock->back().eraseFromParent();
483  FirstEntryBlock->splice(FirstEntryBlock->end(), SecondEntryBlock);
484  BranchInst *PBI = cast<BranchInst>(FirstEntryBlock->getTerminator());
485  assert(PBI->getCondition() == CInst2);
486  BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
487  BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
488  Builder.SetInsertPoint(PBI);
489  if (InvertCond2) {
490    // If this is a "cmp" instruction, only used for branching (and nowhere
491    // else), then we can simply invert the predicate.
492    auto Cmp2 = dyn_cast<CmpInst>(CInst2);
493    if (Cmp2 && Cmp2->hasOneUse())
494      Cmp2->setPredicate(Cmp2->getInversePredicate());
495    else
496      CInst2 = cast<Instruction>(Builder.CreateNot(CInst2));
497    PBI->swapSuccessors();
498  }
499  Value *NC = Builder.CreateBinOp(CombineOp, CInst1, CInst2);
500  PBI->replaceUsesOfWith(CInst2, NC);
501  Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
502
503  // Handle PHI node to replace its predecessors to FirstEntryBlock.
504  for (BasicBlock *Succ : successors(PBI)) {
505    for (PHINode &Phi : Succ->phis()) {
506      for (unsigned i = 0, e = Phi.getNumIncomingValues(); i != e; ++i) {
507        if (Phi.getIncomingBlock(i) == SecondEntryBlock)
508          Phi.setIncomingBlock(i, FirstEntryBlock);
509      }
510    }
511  }
512
513  // Remove IfTrue1
514  if (IfTrue1 != FirstEntryBlock) {
515    IfTrue1->dropAllReferences();
516    IfTrue1->eraseFromParent();
517  }
518
519  // Remove IfFalse1
520  if (IfFalse1 != FirstEntryBlock) {
521    IfFalse1->dropAllReferences();
522    IfFalse1->eraseFromParent();
523  }
524
525  // Remove \param SecondEntryBlock
526  SecondEntryBlock->dropAllReferences();
527  SecondEntryBlock->eraseFromParent();
528  LLVM_DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
529  return true;
530}
531
532bool FlattenCFGOpt::run(BasicBlock *BB) {
533  assert(BB && BB->getParent() && "Block not embedded in function!");
534  assert(BB->getTerminator() && "Degenerate basic block encountered!");
535
536  IRBuilder<> Builder(BB);
537
538  if (FlattenParallelAndOr(BB, Builder) || MergeIfRegion(BB, Builder))
539    return true;
540  return false;
541}
542
543/// FlattenCFG - This function is used to flatten a CFG.  For
544/// example, it uses parallel-and and parallel-or mode to collapse
545/// if-conditions and merge if-regions with identical statements.
546bool llvm::FlattenCFG(BasicBlock *BB, AAResults *AA) {
547  return FlattenCFGOpt(AA).run(BB);
548}
549