536 lines · cpp
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-exception6//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 29using namespace llvm;30 31#define DEBUG_TYPE "flatten-cfg"32 33namespace {34 35class FlattenCFGOpt {36 AliasAnalysis *AA;37 38 /// Use parallel-and or parallel-or to generate conditions for39 /// conditional branches.40 bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder);41 42 /// If \param BB is the merge block of an if-region, attempt to merge43 /// the if-region with an adjacent if-region upstream if two if-regions44 /// contain identical instructions.45 bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder);46 47 /// Compare a pair of blocks: \p Block1 and \p Block2, which48 /// are from two if-regions, where \p Head2 is the entry block of the 2nd49 /// if-region. \returns true if \p Block1 and \p Block2 contain identical50 /// 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 55public:56 FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {}57 58 bool run(BasicBlock *BB);59};60 61} // end anonymous namespace62 63/// If \param [in] BB has more than one predecessor that is a conditional64/// branch, attempt to use parallel and/or for the branch condition. \returns65/// true on success.66///67/// Before:68/// ......69/// %cmp10 = fcmp une float %tmp1, %tmp270/// br i1 %cmp10, label %if.then, label %lor.rhs71///72/// lor.rhs:73/// ......74/// %cmp11 = fcmp une float %tmp3, %tmp475/// br i1 %cmp11, label %if.then, label %ifend76///77/// if.end: // the merge block78/// ......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, %tmp287/// ......88/// %cmp11 = fcmp une float %tmp3, %tmp489/// %cmp12 = or i1 %cmp10, %cmp11 // parallel-or mode.90/// br i1 %cmp12, label %if.then, label %ifend91///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/// BB1103/// / |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 => BB4110///111///112/// Corresponding source code:113///114/// if (a == b && c == d)115/// statement; // BB3116///117/// Case 2: BB is on the then-path.118///119/// BB1120/// / |121/// | BB2122/// \ / | where BB1, BB2 contain conditional branches.123/// BB => BB3 | BB3 contains unconditiona branch and corresponds124/// \ / to BB. BB4 is the merge.125/// BB4126///127/// Corresponding source code:128///129/// if (a == b || c == d)130/// statement; // BB3131///132/// In both cases, BB is the common successor of conditional branches.133/// In Case 1, BB (BB4) has an unconditional branch (BB3) as134/// its predecessor. In Case 2, BB (BB3) only has conditional branches135/// as its predecessors.136bool 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(llvm::from_range, predecessors(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 should159 // have a single predecessor (BB2) that is also a predecessor160 // of \param BB (BB4) and should not have address-taken.161 // There should exist only one such unconditional162 // 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 safe187 // 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 in196 // both cases.197 if (FirstCondBlock)198 return false;199 FirstCondBlock = Pred;200 }201 202 // Find whether BB is uniformly on the true (or false) path203 // 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 identify215 // the last conditional branch.216 if (!Preds.contains(PS)) {217 // Case 2.218 LastCondBlock = Pred;219 } else {220 // Case 1221 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_oeq259 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 else298 // 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 the316/// 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 if318/// Block1 and Block2 have identical instructions and do not have319/// memory reference alias with Head2.320bool 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 identical326 // 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 except343 // 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 be352 // 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 whether iter1 and BI may access the same memory location.360 if (!AA || AA->getModRefInfo(&*iter1, &*BI) != ModRefInfo::NoModRef)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, check373/// whether there exists an adjacent if-region upstream, the two if-regions374/// contain identical instructions and can be legally merged. \returns true if375/// 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/// else392/// statement;393/// if (b)394/// ;395/// else396/// statement;397///398/// To:399/// if (a && b)400/// ;401/// else402/// statement;403///404/// We always take the form of the first if-region. This means that if the405/// statement in the first if-region, is in the "then-path", while in the second406/// if-region it is in the "else-path", then we convert the second to the first407/// form, by inverting the condition and the branch successors. The same408/// approach goes for the opposite case.409bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {410 // We cannot merge the if-region if the merge point has phi nodes.411 if (isa<PHINode>(BB->front()))412 return false;413 414 BasicBlock *IfTrue2, *IfFalse2;415 BranchInst *DomBI2 = GetIfCondition(BB, IfTrue2, IfFalse2);416 if (!DomBI2)417 return false;418 Instruction *CInst2 = dyn_cast<Instruction>(DomBI2->getCondition());419 if (!CInst2)420 return false;421 422 BasicBlock *SecondEntryBlock = CInst2->getParent();423 if (SecondEntryBlock->hasAddressTaken())424 return false;425 426 BasicBlock *IfTrue1, *IfFalse1;427 BranchInst *DomBI1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);428 if (!DomBI1)429 return false;430 Instruction *CInst1 = dyn_cast<Instruction>(DomBI1->getCondition());431 if (!CInst1)432 return false;433 434 BasicBlock *FirstEntryBlock = CInst1->getParent();435 // Don't die trying to process degenerate/unreachable code.436 if (FirstEntryBlock == SecondEntryBlock)437 return false;438 439 // Either then-path or else-path should be empty.440 bool InvertCond2 = false;441 BinaryOperator::BinaryOps CombineOp;442 if (IfFalse1 == FirstEntryBlock) {443 // The else-path is empty, so we must use "or" operation to combine the444 // conditions.445 CombineOp = BinaryOperator::Or;446 if (IfFalse2 != SecondEntryBlock) {447 if (IfTrue2 != SecondEntryBlock)448 return false;449 450 InvertCond2 = true;451 std::swap(IfTrue2, IfFalse2);452 }453 454 if (!CompareIfRegionBlock(IfTrue1, IfTrue2, SecondEntryBlock))455 return false;456 } else if (IfTrue1 == FirstEntryBlock) {457 // The then-path is empty, so we must use "and" operation to combine the458 // conditions.459 CombineOp = BinaryOperator::And;460 if (IfTrue2 != SecondEntryBlock) {461 if (IfFalse2 != SecondEntryBlock)462 return false;463 464 InvertCond2 = true;465 std::swap(IfTrue2, IfFalse2);466 }467 468 if (!CompareIfRegionBlock(IfFalse1, IfFalse2, SecondEntryBlock))469 return false;470 } else471 return false;472 473 Instruction *PTI2 = SecondEntryBlock->getTerminator();474 Instruction *PBI2 = &SecondEntryBlock->front();475 476 // Check whether \param SecondEntryBlock has side-effect and is safe to477 // speculate.478 for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {479 Instruction *CI = &*BI;480 if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||481 !isSafeToSpeculativelyExecute(CI))482 return false;483 }484 485 // Merge \param SecondEntryBlock into \param FirstEntryBlock.486 FirstEntryBlock->back().eraseFromParent();487 FirstEntryBlock->splice(FirstEntryBlock->end(), SecondEntryBlock);488 BranchInst *PBI = cast<BranchInst>(FirstEntryBlock->getTerminator());489 assert(PBI->getCondition() == CInst2);490 BasicBlock *SaveInsertBB = Builder.GetInsertBlock();491 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();492 Builder.SetInsertPoint(PBI);493 if (InvertCond2) {494 InvertBranch(PBI, Builder);495 }496 Value *NC = Builder.CreateBinOp(CombineOp, CInst1, PBI->getCondition());497 PBI->replaceUsesOfWith(PBI->getCondition(), NC);498 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);499 500 // Remove IfTrue1501 if (IfTrue1 != FirstEntryBlock) {502 IfTrue1->dropAllReferences();503 IfTrue1->eraseFromParent();504 }505 506 // Remove IfFalse1507 if (IfFalse1 != FirstEntryBlock) {508 IfFalse1->dropAllReferences();509 IfFalse1->eraseFromParent();510 }511 512 // Remove \param SecondEntryBlock513 SecondEntryBlock->dropAllReferences();514 SecondEntryBlock->eraseFromParent();515 LLVM_DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);516 return true;517}518 519bool FlattenCFGOpt::run(BasicBlock *BB) {520 assert(BB && BB->getParent() && "Block not embedded in function!");521 assert(BB->getTerminator() && "Degenerate basic block encountered!");522 523 IRBuilder<> Builder(BB);524 525 if (FlattenParallelAndOr(BB, Builder) || MergeIfRegion(BB, Builder))526 return true;527 return false;528}529 530/// FlattenCFG - This function is used to flatten a CFG. For531/// example, it uses parallel-and and parallel-or mode to collapse532/// if-conditions and merge if-regions with identical statements.533bool llvm::FlattenCFG(BasicBlock *BB, AAResults *AA) {534 return FlattenCFGOpt(AA).run(BB);535}536