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 IRBuilder<>::InsertPointGuard Guard(Builder); 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 DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock); 301 return true; 302 } 303 304 /// Compare blocks from two if-regions, where \param Head1 is the entry of the 305 /// 1st if-region. \param Head2 is the entry of the 2nd if-region. \param 306 /// Block1 is a block in the 1st if-region to compare. \param Block2 is a block 307 // in the 2nd if-region to compare. \returns true if \param Block1 and \param 308 /// Block2 have identical instructions and do not have memory reference alias 309 /// with \param Head2. 310 /// 311 bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2, 312 BasicBlock *Block1, 313 BasicBlock *Block2) { 314 TerminatorInst *PTI2 = Head2->getTerminator(); 315 Instruction *PBI2 = Head2->begin(); 316 317 bool eq1 = (Block1 == Head1); 318 bool eq2 = (Block2 == Head2); 319 if (eq1 || eq2) { 320 // An empty then-path or else-path. 321 return (eq1 == eq2); 322 } 323 324 // Check whether instructions in Block1 and Block2 are identical 325 // and do not alias with instructions in Head2. 326 BasicBlock::iterator iter1 = Block1->begin(); 327 BasicBlock::iterator end1 = Block1->getTerminator(); 328 BasicBlock::iterator iter2 = Block2->begin(); 329 BasicBlock::iterator end2 = Block2->getTerminator(); 330 331 while (1) { 332 if (iter1 == end1) { 333 if (iter2 != end2) 334 return false; 335 break; 336 } 337 338 if (!iter1->isIdenticalTo(iter2)) 339 return false; 340 341 // Illegal to remove instructions with side effects except 342 // non-volatile stores. 343 if (iter1->mayHaveSideEffects()) { 344 Instruction *CurI = &*iter1; 345 StoreInst *SI = dyn_cast<StoreInst>(CurI); 346 if (!SI || SI->isVolatile()) 347 return false; 348 } 349 350 // For simplicity and speed, data dependency check can be 351 // avoided if read from memory doesn't exist. 352 if (iter1->mayReadFromMemory()) 353 return false; 354 355 if (iter1->mayWriteToMemory()) { 356 for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) { 357 if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) { 358 // Check alias with Head2. 359 if (!AA || AA->alias(iter1, BI)) 360 return false; 361 } 362 } 363 } 364 ++iter1; 365 ++iter2; 366 } 367 368 return true; 369 } 370 371 /// Check whether \param BB is the merge block of a if-region. If yes, check 372 /// whether there exists an adjacent if-region upstream, the two if-regions 373 /// contain identical instructions and can be legally merged. \returns true if 374 /// the two if-regions are merged. 375 /// 376 /// From: 377 /// if (a) 378 /// statement; 379 /// if (b) 380 /// statement; 381 /// 382 /// To: 383 /// if (a || b) 384 /// statement; 385 /// 386 bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder, 387 Pass *P) { 388 BasicBlock *IfTrue2, *IfFalse2; 389 Value *IfCond2 = GetIfCondition(BB, IfTrue2, IfFalse2); 390 Instruction *CInst2 = dyn_cast_or_null<Instruction>(IfCond2); 391 if (!CInst2) 392 return false; 393 394 BasicBlock *SecondEntryBlock = CInst2->getParent(); 395 if (SecondEntryBlock->hasAddressTaken()) 396 return false; 397 398 BasicBlock *IfTrue1, *IfFalse1; 399 Value *IfCond1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1); 400 Instruction *CInst1 = dyn_cast_or_null<Instruction>(IfCond1); 401 if (!CInst1) 402 return false; 403 404 BasicBlock *FirstEntryBlock = CInst1->getParent(); 405 406 // Either then-path or else-path should be empty. 407 if ((IfTrue1 != FirstEntryBlock) && (IfFalse1 != FirstEntryBlock)) 408 return false; 409 if ((IfTrue2 != SecondEntryBlock) && (IfFalse2 != SecondEntryBlock)) 410 return false; 411 412 TerminatorInst *PTI2 = SecondEntryBlock->getTerminator(); 413 Instruction *PBI2 = SecondEntryBlock->begin(); 414 415 if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfTrue1, 416 IfTrue2)) 417 return false; 418 419 if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfFalse1, 420 IfFalse2)) 421 return false; 422 423 // Check whether \param SecondEntryBlock has side-effect and is safe to 424 // speculate. 425 for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) { 426 Instruction *CI = BI; 427 if (isa<PHINode>(CI) || CI->mayHaveSideEffects() || 428 !isSafeToSpeculativelyExecute(CI)) 429 return false; 430 } 431 432 // Merge \param SecondEntryBlock into \param FirstEntryBlock. 433 FirstEntryBlock->getInstList().pop_back(); 434 FirstEntryBlock->getInstList() 435 .splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList()); 436 BranchInst *PBI = dyn_cast<BranchInst>(FirstEntryBlock->getTerminator()); 437 Value *CC = PBI->getCondition(); 438 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 439 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 440 Builder.SetInsertPoint(PBI); 441 Value *NC = Builder.CreateOr(CInst1, CC); 442 PBI->replaceUsesOfWith(CC, NC); 443 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 444 445 // Remove IfTrue1 446 if (IfTrue1 != FirstEntryBlock) { 447 IfTrue1->dropAllReferences(); 448 IfTrue1->eraseFromParent(); 449 } 450 451 // Remove IfFalse1 452 if (IfFalse1 != FirstEntryBlock) { 453 IfFalse1->dropAllReferences(); 454 IfFalse1->eraseFromParent(); 455 } 456 457 // Remove \param SecondEntryBlock 458 SecondEntryBlock->dropAllReferences(); 459 SecondEntryBlock->eraseFromParent(); 460 DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock); 461 return true; 462 } 463 464 bool FlattenCFGOpt::run(BasicBlock *BB) { 465 bool Changed = false; 466 assert(BB && BB->getParent() && "Block not embedded in function!"); 467 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 468 469 IRBuilder<> Builder(BB); 470 471 if (FlattenParallelAndOr(BB, Builder)) 472 return true; 473 474 if (MergeIfRegion(BB, Builder)) 475 return true; 476 477 return Changed; 478 } 479 480 /// FlattenCFG - This function is used to flatten a CFG. For 481 /// example, it uses parallel-and and parallel-or mode to collapse 482 // if-conditions and merge if-regions with identical statements. 483 /// 484 bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) { 485 return FlattenCFGOpt(AA).run(BB); 486 } 487