Home | History | Annotate | Download | only in Utils 
      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 #define DEBUG_TYPE "flattencfg"
     15 #include "llvm/Transforms/Utils/Local.h"
     16 #include "llvm/ADT/SmallPtrSet.h"
     17 #include "llvm/Analysis/AliasAnalysis.h"
     18 #include "llvm/Analysis/ValueTracking.h"
     19 #include "llvm/IR/IRBuilder.h"
     20 #include "llvm/Support/Debug.h"
     21 #include "llvm/Support/raw_ostream.h"
     22 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
     23 using namespace llvm;
     24 
     25 namespace {
     26 class FlattenCFGOpt {
     27   AliasAnalysis *AA;
     28   /// \brief Use parallel-and or parallel-or to generate conditions for
     29   /// conditional branches.
     30   bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder, Pass *P = 0);
     31   /// \brief If \param BB is the merge block of an if-region, attempt to merge
     32   /// the if-region with an adjacent if-region upstream if two if-regions
     33   /// contain identical instructions.
     34   bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder, Pass *P = 0);
     35   /// \brief Compare a pair of blocks: \p Block1 and \p Block2, which
     36   /// are from two if-regions whose entry blocks are \p Head1 and \p
     37   /// Head2.  \returns true if \p Block1 and \p Block2 contain identical
     38   /// instructions, and have no memory reference alias with \p Head2.
     39   /// This is used as a legality check for merging if-regions.
     40   bool CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
     41                             BasicBlock *Block1, BasicBlock *Block2);
     42 
     43 public:
     44   FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {}
     45   bool run(BasicBlock *BB);
     46 };
     47 }
     48 
     49 /// If \param [in] BB has more than one predecessor that is a conditional
     50 /// branch, attempt to use parallel and/or for the branch condition. \returns
     51 /// true on success.
     52 ///
     53 /// Before:
     54 ///   ......
     55 ///   %cmp10 = fcmp une float %tmp1, %tmp2
     56 ///   br i1 %cmp1, label %if.then, label %lor.rhs
     57 ///
     58 /// lor.rhs:
     59 ///   ......
     60 ///   %cmp11 = fcmp une float %tmp3, %tmp4
     61 ///   br i1 %cmp11, label %if.then, label %ifend
     62 ///
     63 /// if.end:  // the merge block
     64 ///   ......
     65 ///
     66 /// if.then: // has two predecessors, both of them contains conditional branch.
     67 ///   ......
     68 ///   br label %if.end;
     69 ///
     70 /// After:
     71 ///  ......
     72 ///  %cmp10 = fcmp une float %tmp1, %tmp2
     73 ///  ......
     74 ///  %cmp11 = fcmp une float %tmp3, %tmp4
     75 ///  %cmp12 = or i1 %cmp10, %cmp11    // parallel-or mode.
     76 ///  br i1 %cmp12, label %if.then, label %ifend
     77 ///
     78 ///  if.end:
     79 ///    ......
     80 ///
     81 ///  if.then:
     82 ///    ......
     83 ///    br label %if.end;
     84 ///
     85 ///  Current implementation handles two cases.
     86 ///  Case 1: \param BB is on the else-path.
     87 ///
     88 ///          BB1
     89 ///        /     |
     90 ///       BB2    |
     91 ///      /   \   |
     92 ///     BB3   \  |     where, BB1, BB2 contain conditional branches.
     93 ///      \    |  /     BB3 contains unconditional branch.
     94 ///       \   | /      BB4 corresponds to \param BB which is also the merge.
     95 ///  BB => BB4
     96 ///
     97 ///
     98 ///  Corresponding source code:
     99 ///
    100 ///  if (a == b && c == d)
    101 ///    statement; // BB3
    102 ///
    103 ///  Case 2: \param BB BB is on the then-path.
    104 ///
    105 ///             BB1
    106 ///          /      |
    107 ///         |      BB2
    108 ///         \    /    |  where BB1, BB2 contain conditional branches.
    109 ///  BB =>   BB3      |  BB3 contains unconditiona branch and corresponds
    110 ///           \     /    to \param BB.  BB4 is the merge.
    111 ///             BB4
    112 ///
    113 ///  Corresponding source code:
    114 ///
    115 ///  if (a == b || c == d)
    116 ///    statement;  // BB3
    117 ///
    118 ///  In both cases,  \param BB is the common successor of conditional branches.
    119 ///  In Case 1, \param BB (BB4) has an unconditional branch (BB3) as
    120 ///  its predecessor.  In Case 2, \param BB (BB3) only has conditional branches
    121 ///  as its predecessors.
    122 ///
    123 bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder,
    124                                          Pass *P) {
    125   PHINode *PHI = dyn_cast<PHINode>(BB->begin());
    126   if (PHI)
    127     return false; // For simplicity, avoid cases containing PHI nodes.
    128 
    129   BasicBlock *LastCondBlock = NULL;
    130   BasicBlock *FirstCondBlock = NULL;
    131   BasicBlock *UnCondBlock = NULL;
    132   int Idx = -1;
    133 
    134   // Check predecessors of \param BB.
    135   SmallPtrSet<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
    136   for (SmallPtrSetIterator<BasicBlock *> PI = Preds.begin(), PE = Preds.end();
    137        PI != PE; ++PI) {
    138     BasicBlock *Pred = *PI;
    139     BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator());
    140 
    141     // All predecessors should terminate with a branch.
    142     if (!PBI)
    143       return false;
    144 
    145     BasicBlock *PP = Pred->getSinglePredecessor();
    146 
    147     if (PBI->isUnconditional()) {
    148       // Case 1: Pred (BB3) is an unconditional block, it should
    149       // have a single predecessor (BB2) that is also a predecessor
    150       // of \param BB (BB4) and should not have address-taken.
    151       // There should exist only one such unconditional
    152       // branch among the predecessors.
    153       if (UnCondBlock || !PP || (Preds.count(PP) == 0) ||
    154           Pred->hasAddressTaken())
    155         return false;
    156 
    157       UnCondBlock = Pred;
    158       continue;
    159     }
    160 
    161     // Only conditional branches are allowed beyond this point.
    162     assert(PBI->isConditional());
    163 
    164     // Condition's unique use should be the branch instruction.
    165     Value *PC = PBI->getCondition();
    166     if (!PC || !PC->hasOneUse())
    167       return false;
    168 
    169     if (PP && Preds.count(PP)) {
    170       // These are internal condition blocks to be merged from, e.g.,
    171       // BB2 in both cases.
    172       // Should not be address-taken.
    173       if (Pred->hasAddressTaken())
    174         return false;
    175 
    176       // Instructions in the internal condition blocks should be safe
    177       // to hoist up.
    178       for (BasicBlock::iterator BI = Pred->begin(), BE = PBI; BI != BE;) {
    179         Instruction *CI = BI++;
    180         if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI))
    181           return false;
    182       }
    183     } else {
    184       // This is the condition block to be merged into, e.g. BB1 in
    185       // both cases.
    186       if (FirstCondBlock)
    187         return false;
    188       FirstCondBlock = Pred;
    189     }
    190 
    191     // Find whether BB is uniformly on the true (or false) path
    192     // for all of its predecessors.
    193     BasicBlock *PS1 = PBI->getSuccessor(0);
    194     BasicBlock *PS2 = PBI->getSuccessor(1);
    195     BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
    196     int CIdx = (PS1 == BB) ? 0 : 1;
    197 
    198     if (Idx == -1)
    199       Idx = CIdx;
    200     else if (CIdx != Idx)
    201       return false;
    202 
    203     // PS is the successor which is not BB. Check successors to identify
    204     // the last conditional branch.
    205     if (Preds.count(PS) == 0) {
    206       // Case 2.
    207       LastCondBlock = Pred;
    208     } else {
    209       // Case 1
    210       BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
    211       if (BPS && BPS->isUnconditional()) {
    212         // Case 1: PS(BB3) should be an unconditional branch.
    213         LastCondBlock = Pred;
    214       }
    215     }
    216   }
    217 
    218   if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
    219     return false;
    220 
    221   TerminatorInst *TBB = LastCondBlock->getTerminator();
    222   BasicBlock *PS1 = TBB->getSuccessor(0);
    223   BasicBlock *PS2 = TBB->getSuccessor(1);
    224   BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
    225   BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
    226 
    227   // If PS1 does not jump into PS2, but PS2 jumps into PS1,
    228   // attempt branch inversion.
    229   if (!PBI1 || !PBI1->isUnconditional() ||
    230       (PS1->getTerminator()->getSuccessor(0) != PS2)) {
    231     // Check whether PS2 jumps into PS1.
    232     if (!PBI2 || !PBI2->isUnconditional() ||
    233         (PS2->getTerminator()->getSuccessor(0) != PS1))
    234       return false;
    235 
    236     // Do branch inversion.
    237     BasicBlock *CurrBlock = LastCondBlock;
    238     bool EverChanged = false;
    239     while (1) {
    240       BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator());
    241       CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
    242       CmpInst::Predicate Predicate = CI->getPredicate();
    243       // Cannonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
    244       if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
    245         CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
    246         BI->swapSuccessors();
    247         EverChanged = true;
    248       }
    249       if (CurrBlock == FirstCondBlock)
    250         break;
    251       CurrBlock = CurrBlock->getSinglePredecessor();
    252     }
    253     return EverChanged;
    254   }
    255 
    256   // PS1 must have a conditional branch.
    257   if (!PBI1 || !PBI1->isUnconditional())
    258     return false;
    259 
    260   // PS2 should not contain PHI node.
    261   PHI = dyn_cast<PHINode>(PS2->begin());
    262   if (PHI)
    263     return false;
    264 
    265   // Do the transformation.
    266   BasicBlock *CB;
    267   BranchInst *PBI = dyn_cast<BranchInst>(FirstCondBlock->getTerminator());
    268   bool Iteration = true;
    269   BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
    270   BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
    271   Value *PC = PBI->getCondition();
    272 
    273   do {
    274     CB = PBI->getSuccessor(1 - Idx);
    275     // Delete the conditional branch.
    276     FirstCondBlock->getInstList().pop_back();
    277     FirstCondBlock->getInstList()
    278         .splice(FirstCondBlock->end(), CB->getInstList());
    279     PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
    280     Value *CC = PBI->getCondition();
    281     // Merge conditions.
    282     Builder.SetInsertPoint(PBI);
    283     Value *NC;
    284     if (Idx == 0)
    285       // Case 2, use parallel or.
    286       NC = Builder.CreateOr(PC, CC);
    287     else
    288       // Case 1, use parallel and.
    289       NC = Builder.CreateAnd(PC, CC);
    290 
    291     PBI->replaceUsesOfWith(CC, NC);
    292     PC = NC;
    293     if (CB == LastCondBlock)
    294       Iteration = false;
    295     // Remove internal conditional branches.
    296     CB->dropAllReferences();
    297     // make CB unreachable and let downstream to delete the block.
    298     new UnreachableInst(CB->getContext(), CB);
    299   } while (Iteration);
    300 
    301   Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
    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 ///
    313 bool 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 instuctions 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 ///
    388 bool 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 
    466 bool 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 ///
    486 bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) {
    487   return FlattenCFGOpt(AA).run(BB);
    488 }
    489