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