lib/Transforms/Utils/FlattenCFG.cpp

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