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, where \p Head2 is the entry block of the 2nd 49 /// if-region. \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 *Block1, BasicBlock *Block2, 53 BasicBlock *Head2); 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 %cmp10, 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: 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 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: 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 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, BB is the common successor of conditional branches. 133 /// In Case 1, BB (BB4) has an unconditional branch (BB3) as 134 /// its predecessor. In Case 2, 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 (BasicBlock *Pred : Preds) { 149 BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator()); 150 151 // All predecessors should terminate with a branch. 152 if (!PBI) 153 return false; 154 155 BasicBlock *PP = Pred->getSinglePredecessor(); 156 157 if (PBI->isUnconditional()) { 158 // Case 1: Pred (BB3) is an unconditional block, it should 159 // have a single predecessor (BB2) that is also a predecessor 160 // of \param BB (BB4) and should not have address-taken. 161 // There should exist only one such unconditional 162 // branch among the predecessors. 163 if (UnCondBlock || !PP || !Preds.contains(PP) || 164 Pred->hasAddressTaken()) 165 return false; 166 167 UnCondBlock = Pred; 168 continue; 169 } 170 171 // Only conditional branches are allowed beyond this point. 172 assert(PBI->isConditional()); 173 174 // Condition's unique use should be the branch instruction. 175 Value *PC = PBI->getCondition(); 176 if (!PC || !PC->hasOneUse()) 177 return false; 178 179 if (PP && Preds.count(PP)) { 180 // These are internal condition blocks to be merged from, e.g., 181 // BB2 in both cases. 182 // Should not be address-taken. 183 if (Pred->hasAddressTaken()) 184 return false; 185 186 // Instructions in the internal condition blocks should be safe 187 // to hoist up. 188 for (BasicBlock::iterator BI = Pred->begin(), BE = PBI->getIterator(); 189 BI != BE;) { 190 Instruction *CI = &*BI++; 191 if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI)) 192 return false; 193 } 194 } else { 195 // This is the condition block to be merged into, e.g. BB1 in 196 // both cases. 197 if (FirstCondBlock) 198 return false; 199 FirstCondBlock = Pred; 200 } 201 202 // Find whether BB is uniformly on the true (or false) path 203 // for all of its predecessors. 204 BasicBlock *PS1 = PBI->getSuccessor(0); 205 BasicBlock *PS2 = PBI->getSuccessor(1); 206 BasicBlock *PS = (PS1 == BB) ? PS2 : PS1; 207 int CIdx = (PS1 == BB) ? 0 : 1; 208 209 if (Idx == -1) 210 Idx = CIdx; 211 else if (CIdx != Idx) 212 return false; 213 214 // PS is the successor which is not BB. Check successors to identify 215 // the last conditional branch. 216 if (!Preds.contains(PS)) { 217 // Case 2. 218 LastCondBlock = Pred; 219 } else { 220 // Case 1 221 BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator()); 222 if (BPS && BPS->isUnconditional()) { 223 // Case 1: PS(BB3) should be an unconditional branch. 224 LastCondBlock = Pred; 225 } 226 } 227 } 228 229 if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock)) 230 return false; 231 232 Instruction *TBB = LastCondBlock->getTerminator(); 233 BasicBlock *PS1 = TBB->getSuccessor(0); 234 BasicBlock *PS2 = TBB->getSuccessor(1); 235 BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator()); 236 BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator()); 237 238 // If PS1 does not jump into PS2, but PS2 jumps into PS1, 239 // attempt branch inversion. 240 if (!PBI1 || !PBI1->isUnconditional() || 241 (PS1->getTerminator()->getSuccessor(0) != PS2)) { 242 // Check whether PS2 jumps into PS1. 243 if (!PBI2 || !PBI2->isUnconditional() || 244 (PS2->getTerminator()->getSuccessor(0) != PS1)) 245 return false; 246 247 // Do branch inversion. 248 BasicBlock *CurrBlock = LastCondBlock; 249 bool EverChanged = false; 250 for (; CurrBlock != FirstCondBlock; 251 CurrBlock = CurrBlock->getSinglePredecessor()) { 252 auto *BI = cast<BranchInst>(CurrBlock->getTerminator()); 253 auto *CI = dyn_cast<CmpInst>(BI->getCondition()); 254 if (!CI) 255 continue; 256 257 CmpInst::Predicate Predicate = CI->getPredicate(); 258 // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq 259 if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) { 260 CI->setPredicate(ICmpInst::getInversePredicate(Predicate)); 261 BI->swapSuccessors(); 262 EverChanged = true; 263 } 264 } 265 return EverChanged; 266 } 267 268 // PS1 must have a conditional branch. 269 if (!PBI1 || !PBI1->isUnconditional()) 270 return false; 271 272 // PS2 should not contain PHI node. 273 PHI = dyn_cast<PHINode>(PS2->begin()); 274 if (PHI) 275 return false; 276 277 // Do the transformation. 278 BasicBlock *CB; 279 BranchInst *PBI = cast<BranchInst>(FirstCondBlock->getTerminator()); 280 bool Iteration = true; 281 IRBuilder<>::InsertPointGuard Guard(Builder); 282 Value *PC = PBI->getCondition(); 283 284 do { 285 CB = PBI->getSuccessor(1 - Idx); 286 // Delete the conditional branch. 287 FirstCondBlock->back().eraseFromParent(); 288 FirstCondBlock->splice(FirstCondBlock->end(), CB); 289 PBI = cast<BranchInst>(FirstCondBlock->getTerminator()); 290 Value *CC = PBI->getCondition(); 291 // Merge conditions. 292 Builder.SetInsertPoint(PBI); 293 Value *NC; 294 if (Idx == 0) 295 // Case 2, use parallel or. 296 NC = Builder.CreateOr(PC, CC); 297 else 298 // Case 1, use parallel and. 299 NC = Builder.CreateAnd(PC, CC); 300 301 PBI->replaceUsesOfWith(CC, NC); 302 PC = NC; 303 if (CB == LastCondBlock) 304 Iteration = false; 305 // Remove internal conditional branches. 306 CB->dropAllReferences(); 307 // make CB unreachable and let downstream to delete the block. 308 new UnreachableInst(CB->getContext(), CB); 309 } while (Iteration); 310 311 LLVM_DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock); 312 return true; 313 } 314 315 /// Compare blocks from two if-regions, where \param Head2 is the entry of the 316 /// 2nd if-region. \param Block1 is a block in the 1st if-region to compare. 317 /// \param Block2 is a block in the 2nd if-region to compare. \returns true if 318 /// Block1 and Block2 have identical instructions and do not have 319 /// memory reference alias with Head2. 320 bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2, 321 BasicBlock *Head2) { 322 Instruction *PTI2 = Head2->getTerminator(); 323 Instruction *PBI2 = &Head2->front(); 324 325 // Check whether instructions in Block1 and Block2 are identical 326 // and do not alias with instructions in Head2. 327 BasicBlock::iterator iter1 = Block1->begin(); 328 BasicBlock::iterator end1 = Block1->getTerminator()->getIterator(); 329 BasicBlock::iterator iter2 = Block2->begin(); 330 BasicBlock::iterator end2 = Block2->getTerminator()->getIterator(); 331 332 while (true) { 333 if (iter1 == end1) { 334 if (iter2 != end2) 335 return false; 336 break; 337 } 338 339 if (!iter1->isIdenticalTo(&*iter2)) 340 return false; 341 342 // Illegal to remove instructions with side effects except 343 // non-volatile stores. 344 if (iter1->mayHaveSideEffects()) { 345 Instruction *CurI = &*iter1; 346 StoreInst *SI = dyn_cast<StoreInst>(CurI); 347 if (!SI || SI->isVolatile()) 348 return false; 349 } 350 351 // For simplicity and speed, data dependency check can be 352 // avoided if read from memory doesn't exist. 353 if (iter1->mayReadFromMemory()) 354 return false; 355 356 if (iter1->mayWriteToMemory()) { 357 for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) { 358 if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) { 359 // Check alias with Head2. 360 if (!AA || !AA->isNoAlias(&*iter1, &*BI)) 361 return false; 362 } 363 } 364 } 365 ++iter1; 366 ++iter2; 367 } 368 369 return true; 370 } 371 372 /// Check whether \param BB is the merge block of a if-region. If yes, check 373 /// whether there exists an adjacent if-region upstream, the two if-regions 374 /// contain identical instructions and can be legally merged. \returns true if 375 /// the two if-regions are merged. 376 /// 377 /// From: 378 /// if (a) 379 /// statement; 380 /// if (b) 381 /// statement; 382 /// 383 /// To: 384 /// if (a || b) 385 /// statement; 386 /// 387 /// 388 /// And from: 389 /// if (a) 390 /// ; 391 /// else 392 /// statement; 393 /// if (b) 394 /// ; 395 /// else 396 /// statement; 397 /// 398 /// To: 399 /// if (a && b) 400 /// ; 401 /// else 402 /// statement; 403 /// 404 /// We always take the form of the first if-region. This means that if the 405 /// statement in the first if-region, is in the "then-path", while in the second 406 /// if-region it is in the "else-path", then we convert the second to the first 407 /// form, by inverting the condition and the branch successors. The same 408 /// approach goes for the opposite case. 409 bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) { 410 BasicBlock *IfTrue2, *IfFalse2; 411 BranchInst *DomBI2 = GetIfCondition(BB, IfTrue2, IfFalse2); 412 if (!DomBI2) 413 return false; 414 Instruction *CInst2 = dyn_cast<Instruction>(DomBI2->getCondition()); 415 if (!CInst2) 416 return false; 417 418 BasicBlock *SecondEntryBlock = CInst2->getParent(); 419 if (SecondEntryBlock->hasAddressTaken()) 420 return false; 421 422 BasicBlock *IfTrue1, *IfFalse1; 423 BranchInst *DomBI1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1); 424 if (!DomBI1) 425 return false; 426 Instruction *CInst1 = dyn_cast<Instruction>(DomBI1->getCondition()); 427 if (!CInst1) 428 return false; 429 430 BasicBlock *FirstEntryBlock = CInst1->getParent(); 431 // Don't die trying to process degenerate/unreachable code. 432 if (FirstEntryBlock == SecondEntryBlock) 433 return false; 434 435 // Either then-path or else-path should be empty. 436 bool InvertCond2 = false; 437 BinaryOperator::BinaryOps CombineOp; 438 if (IfFalse1 == FirstEntryBlock) { 439 // The else-path is empty, so we must use "or" operation to combine the 440 // conditions. 441 CombineOp = BinaryOperator::Or; 442 if (IfFalse2 != SecondEntryBlock) { 443 if (IfTrue2 != SecondEntryBlock) 444 return false; 445 446 InvertCond2 = true; 447 std::swap(IfTrue2, IfFalse2); 448 } 449 450 if (!CompareIfRegionBlock(IfTrue1, IfTrue2, SecondEntryBlock)) 451 return false; 452 } else if (IfTrue1 == FirstEntryBlock) { 453 // The then-path is empty, so we must use "and" operation to combine the 454 // conditions. 455 CombineOp = BinaryOperator::And; 456 if (IfTrue2 != SecondEntryBlock) { 457 if (IfFalse2 != SecondEntryBlock) 458 return false; 459 460 InvertCond2 = true; 461 std::swap(IfTrue2, IfFalse2); 462 } 463 464 if (!CompareIfRegionBlock(IfFalse1, IfFalse2, SecondEntryBlock)) 465 return false; 466 } else 467 return false; 468 469 Instruction *PTI2 = SecondEntryBlock->getTerminator(); 470 Instruction *PBI2 = &SecondEntryBlock->front(); 471 472 // Check whether \param SecondEntryBlock has side-effect and is safe to 473 // speculate. 474 for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) { 475 Instruction *CI = &*BI; 476 if (isa<PHINode>(CI) || CI->mayHaveSideEffects() || 477 !isSafeToSpeculativelyExecute(CI)) 478 return false; 479 } 480 481 // Merge \param SecondEntryBlock into \param FirstEntryBlock. 482 FirstEntryBlock->back().eraseFromParent(); 483 FirstEntryBlock->splice(FirstEntryBlock->end(), SecondEntryBlock); 484 BranchInst *PBI = cast<BranchInst>(FirstEntryBlock->getTerminator()); 485 assert(PBI->getCondition() == CInst2); 486 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 487 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 488 Builder.SetInsertPoint(PBI); 489 if (InvertCond2) { 490 // If this is a "cmp" instruction, only used for branching (and nowhere 491 // else), then we can simply invert the predicate. 492 auto Cmp2 = dyn_cast<CmpInst>(CInst2); 493 if (Cmp2 && Cmp2->hasOneUse()) 494 Cmp2->setPredicate(Cmp2->getInversePredicate()); 495 else 496 CInst2 = cast<Instruction>(Builder.CreateNot(CInst2)); 497 PBI->swapSuccessors(); 498 } 499 Value *NC = Builder.CreateBinOp(CombineOp, CInst1, CInst2); 500 PBI->replaceUsesOfWith(CInst2, NC); 501 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 502 503 // Handle PHI node to replace its predecessors to FirstEntryBlock. 504 for (BasicBlock *Succ : successors(PBI)) { 505 for (PHINode &Phi : Succ->phis()) { 506 for (unsigned i = 0, e = Phi.getNumIncomingValues(); i != e; ++i) { 507 if (Phi.getIncomingBlock(i) == SecondEntryBlock) 508 Phi.setIncomingBlock(i, FirstEntryBlock); 509 } 510 } 511 } 512 513 // Remove IfTrue1 514 if (IfTrue1 != FirstEntryBlock) { 515 IfTrue1->dropAllReferences(); 516 IfTrue1->eraseFromParent(); 517 } 518 519 // Remove IfFalse1 520 if (IfFalse1 != FirstEntryBlock) { 521 IfFalse1->dropAllReferences(); 522 IfFalse1->eraseFromParent(); 523 } 524 525 // Remove \param SecondEntryBlock 526 SecondEntryBlock->dropAllReferences(); 527 SecondEntryBlock->eraseFromParent(); 528 LLVM_DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock); 529 return true; 530 } 531 532 bool FlattenCFGOpt::run(BasicBlock *BB) { 533 assert(BB && BB->getParent() && "Block not embedded in function!"); 534 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 535 536 IRBuilder<> Builder(BB); 537 538 if (FlattenParallelAndOr(BB, Builder) || MergeIfRegion(BB, Builder)) 539 return true; 540 return false; 541 } 542 543 /// FlattenCFG - This function is used to flatten a CFG. For 544 /// example, it uses parallel-and and parallel-or mode to collapse 545 /// if-conditions and merge if-regions with identical statements. 546 bool llvm::FlattenCFG(BasicBlock *BB, AAResults *AA) { 547 return FlattenCFGOpt(AA).run(BB); 548 } 549