FlattenCFG.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
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/Transforms/Utils/Local.h" 15#include "llvm/ADT/SmallPtrSet.h" 16#include "llvm/Analysis/AliasAnalysis.h" 17#include "llvm/Analysis/ValueTracking.h" 18#include "llvm/IR/IRBuilder.h" 19#include "llvm/Support/Debug.h" 20#include "llvm/Support/raw_ostream.h" 21#include "llvm/Transforms/Utils/BasicBlockUtils.h" 22using namespace llvm; 23 24#define DEBUG_TYPE "flattencfg" 25 26namespace { 27class FlattenCFGOpt { 28 AliasAnalysis *AA; 29 /// \brief Use parallel-and or parallel-or to generate conditions for 30 /// conditional branches. 31 bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder, 32 Pass *P = nullptr); 33 /// \brief If \param BB is the merge block of an if-region, attempt to merge 34 /// the if-region with an adjacent if-region upstream if two if-regions 35 /// contain identical instructions. 36 bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder, Pass *P = nullptr); 37 /// \brief Compare a pair of blocks: \p Block1 and \p Block2, which 38 /// are from two if-regions whose entry blocks are \p Head1 and \p 39 /// Head2. \returns true if \p Block1 and \p Block2 contain identical 40 /// instructions, and have no memory reference alias with \p Head2. 41 /// This is used as a legality check for merging if-regions. 42 bool CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2, 43 BasicBlock *Block1, BasicBlock *Block2); 44 45public: 46 FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {} 47 bool run(BasicBlock *BB); 48}; 49} 50 51/// If \param [in] BB has more than one predecessor that is a conditional 52/// branch, attempt to use parallel and/or for the branch condition. \returns 53/// true on success. 54/// 55/// Before: 56/// ...... 57/// %cmp10 = fcmp une float %tmp1, %tmp2 58/// br i1 %cmp1, label %if.then, label %lor.rhs 59/// 60/// lor.rhs: 61/// ...... 62/// %cmp11 = fcmp une float %tmp3, %tmp4 63/// br i1 %cmp11, label %if.then, label %ifend 64/// 65/// if.end: // the merge block 66/// ...... 67/// 68/// if.then: // has two predecessors, both of them contains conditional branch. 69/// ...... 70/// br label %if.end; 71/// 72/// After: 73/// ...... 74/// %cmp10 = fcmp une float %tmp1, %tmp2 75/// ...... 76/// %cmp11 = fcmp une float %tmp3, %tmp4 77/// %cmp12 = or i1 %cmp10, %cmp11 // parallel-or mode. 78/// br i1 %cmp12, label %if.then, label %ifend 79/// 80/// if.end: 81/// ...... 82/// 83/// if.then: 84/// ...... 85/// br label %if.end; 86/// 87/// Current implementation handles two cases. 88/// Case 1: \param BB is on the else-path. 89/// 90/// BB1 91/// / | 92/// BB2 | 93/// / \ | 94/// BB3 \ | where, BB1, BB2 contain conditional branches. 95/// \ | / BB3 contains unconditional branch. 96/// \ | / BB4 corresponds to \param BB which is also the merge. 97/// BB => BB4 98/// 99/// 100/// Corresponding source code: 101/// 102/// if (a == b && c == d) 103/// statement; // BB3 104/// 105/// Case 2: \param BB BB is on the then-path. 106/// 107/// BB1 108/// / | 109/// | BB2 110/// \ / | where BB1, BB2 contain conditional branches. 111/// BB => BB3 | BB3 contains unconditiona branch and corresponds 112/// \ / to \param BB. BB4 is the merge. 113/// BB4 114/// 115/// Corresponding source code: 116/// 117/// if (a == b || c == d) 118/// statement; // BB3 119/// 120/// In both cases, \param BB is the common successor of conditional branches. 121/// In Case 1, \param BB (BB4) has an unconditional branch (BB3) as 122/// its predecessor. In Case 2, \param BB (BB3) only has conditional branches 123/// as its predecessors. 124/// 125bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder, 126 Pass *P) { 127 PHINode *PHI = dyn_cast<PHINode>(BB->begin()); 128 if (PHI) 129 return false; // For simplicity, avoid cases containing PHI nodes. 130 131 BasicBlock *LastCondBlock = nullptr; 132 BasicBlock *FirstCondBlock = nullptr; 133 BasicBlock *UnCondBlock = nullptr; 134 int Idx = -1; 135 136 // Check predecessors of \param BB. 137 SmallPtrSet<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB)); 138 for (SmallPtrSetIterator<BasicBlock *> PI = Preds.begin(), PE = Preds.end(); 139 PI != PE; ++PI) { 140 BasicBlock *Pred = *PI; 141 BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator()); 142 143 // All predecessors should terminate with a branch. 144 if (!PBI) 145 return false; 146 147 BasicBlock *PP = Pred->getSinglePredecessor(); 148 149 if (PBI->isUnconditional()) { 150 // Case 1: Pred (BB3) is an unconditional block, it should 151 // have a single predecessor (BB2) that is also a predecessor 152 // of \param BB (BB4) and should not have address-taken. 153 // There should exist only one such unconditional 154 // branch among the predecessors. 155 if (UnCondBlock || !PP || (Preds.count(PP) == 0) || 156 Pred->hasAddressTaken()) 157 return false; 158 159 UnCondBlock = Pred; 160 continue; 161 } 162 163 // Only conditional branches are allowed beyond this point. 164 assert(PBI->isConditional()); 165 166 // Condition's unique use should be the branch instruction. 167 Value *PC = PBI->getCondition(); 168 if (!PC || !PC->hasOneUse()) 169 return false; 170 171 if (PP && Preds.count(PP)) { 172 // These are internal condition blocks to be merged from, e.g., 173 // BB2 in both cases. 174 // Should not be address-taken. 175 if (Pred->hasAddressTaken()) 176 return false; 177 178 // Instructions in the internal condition blocks should be safe 179 // to hoist up. 180 for (BasicBlock::iterator BI = Pred->begin(), BE = PBI; BI != BE;) { 181 Instruction *CI = BI++; 182 if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI)) 183 return false; 184 } 185 } else { 186 // This is the condition block to be merged into, e.g. BB1 in 187 // both cases. 188 if (FirstCondBlock) 189 return false; 190 FirstCondBlock = Pred; 191 } 192 193 // Find whether BB is uniformly on the true (or false) path 194 // for all of its predecessors. 195 BasicBlock *PS1 = PBI->getSuccessor(0); 196 BasicBlock *PS2 = PBI->getSuccessor(1); 197 BasicBlock *PS = (PS1 == BB) ? PS2 : PS1; 198 int CIdx = (PS1 == BB) ? 0 : 1; 199 200 if (Idx == -1) 201 Idx = CIdx; 202 else if (CIdx != Idx) 203 return false; 204 205 // PS is the successor which is not BB. Check successors to identify 206 // the last conditional branch. 207 if (Preds.count(PS) == 0) { 208 // Case 2. 209 LastCondBlock = Pred; 210 } else { 211 // Case 1 212 BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator()); 213 if (BPS && BPS->isUnconditional()) { 214 // Case 1: PS(BB3) should be an unconditional branch. 215 LastCondBlock = Pred; 216 } 217 } 218 } 219 220 if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock)) 221 return false; 222 223 TerminatorInst *TBB = LastCondBlock->getTerminator(); 224 BasicBlock *PS1 = TBB->getSuccessor(0); 225 BasicBlock *PS2 = TBB->getSuccessor(1); 226 BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator()); 227 BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator()); 228 229 // If PS1 does not jump into PS2, but PS2 jumps into PS1, 230 // attempt branch inversion. 231 if (!PBI1 || !PBI1->isUnconditional() || 232 (PS1->getTerminator()->getSuccessor(0) != PS2)) { 233 // Check whether PS2 jumps into PS1. 234 if (!PBI2 || !PBI2->isUnconditional() || 235 (PS2->getTerminator()->getSuccessor(0) != PS1)) 236 return false; 237 238 // Do branch inversion. 239 BasicBlock *CurrBlock = LastCondBlock; 240 bool EverChanged = false; 241 while (1) { 242 BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator()); 243 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 244 CmpInst::Predicate Predicate = CI->getPredicate(); 245 // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq 246 if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) { 247 CI->setPredicate(ICmpInst::getInversePredicate(Predicate)); 248 BI->swapSuccessors(); 249 EverChanged = true; 250 } 251 if (CurrBlock == FirstCondBlock) 252 break; 253 CurrBlock = CurrBlock->getSinglePredecessor(); 254 } 255 return EverChanged; 256 } 257 258 // PS1 must have a conditional branch. 259 if (!PBI1 || !PBI1->isUnconditional()) 260 return false; 261 262 // PS2 should not contain PHI node. 263 PHI = dyn_cast<PHINode>(PS2->begin()); 264 if (PHI) 265 return false; 266 267 // Do the transformation. 268 BasicBlock *CB; 269 BranchInst *PBI = dyn_cast<BranchInst>(FirstCondBlock->getTerminator()); 270 bool Iteration = true; 271 IRBuilder<>::InsertPointGuard Guard(Builder); 272 Value *PC = PBI->getCondition(); 273 274 do { 275 CB = PBI->getSuccessor(1 - Idx); 276 // Delete the conditional branch. 277 FirstCondBlock->getInstList().pop_back(); 278 FirstCondBlock->getInstList() 279 .splice(FirstCondBlock->end(), CB->getInstList()); 280 PBI = cast<BranchInst>(FirstCondBlock->getTerminator()); 281 Value *CC = PBI->getCondition(); 282 // Merge conditions. 283 Builder.SetInsertPoint(PBI); 284 Value *NC; 285 if (Idx == 0) 286 // Case 2, use parallel or. 287 NC = Builder.CreateOr(PC, CC); 288 else 289 // Case 1, use parallel and. 290 NC = Builder.CreateAnd(PC, CC); 291 292 PBI->replaceUsesOfWith(CC, NC); 293 PC = NC; 294 if (CB == LastCondBlock) 295 Iteration = false; 296 // Remove internal conditional branches. 297 CB->dropAllReferences(); 298 // make CB unreachable and let downstream to delete the block. 299 new UnreachableInst(CB->getContext(), CB); 300 } while (Iteration); 301 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/// 313bool 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 instructions 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/// 388bool 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 466bool 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/// 486bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) { 487 return FlattenCFGOpt(AA).run(BB); 488} 489