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