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