FlattenCFG.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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" 23using namespace llvm; 24 25namespace { 26class 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 43public: 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/// 123bool 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 // Canonicalize 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/// 311bool 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/// 386bool 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 464bool 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/// 484bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) { 485 return FlattenCFGOpt(AA).run(BB); 486} 487