1 //===- FlatternCFG.cpp - Code to perform CFG flattening -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Reduce conditional branches in CFG.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/Analysis/AliasAnalysis.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 "llvm/Transforms/Utils/Local.h"
32 #define DEBUG_TYPE "flattencfg"
39 /// \brief Use parallel-and or parallel-or to generate conditions for
40 /// conditional branches.
41 bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder);
43 /// \brief If \param BB is the merge block of an if-region, attempt to merge
44 /// the if-region with an adjacent if-region upstream if two if-regions
45 /// contain identical instructions.
46 bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder);
48 /// \brief Compare a pair of blocks: \p Block1 and \p Block2, which
49 /// are from two if-regions whose entry blocks are \p Head1 and \p
50 /// Head2. \returns true if \p Block1 and \p Block2 contain identical
51 /// instructions, and have no memory reference alias with \p Head2.
52 /// This is used as a legality check for merging if-regions.
53 bool CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
54 BasicBlock *Block1, BasicBlock *Block2);
57 FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {}
59 bool run(BasicBlock *BB);
62 } // end anonymous namespace
64 /// If \param [in] BB has more than one predecessor that is a conditional
65 /// branch, attempt to use parallel and/or for the branch condition. \returns
70 /// %cmp10 = fcmp une float %tmp1, %tmp2
71 /// br i1 %cmp1, label %if.then, label %lor.rhs
75 /// %cmp11 = fcmp une float %tmp3, %tmp4
76 /// br i1 %cmp11, label %if.then, label %ifend
78 /// if.end: // the merge block
81 /// if.then: // has two predecessors, both of them contains conditional branch.
87 /// %cmp10 = fcmp une float %tmp1, %tmp2
89 /// %cmp11 = fcmp une float %tmp3, %tmp4
90 /// %cmp12 = or i1 %cmp10, %cmp11 // parallel-or mode.
91 /// br i1 %cmp12, label %if.then, label %ifend
100 /// Current implementation handles two cases.
101 /// Case 1: \param BB is on the else-path.
107 /// BB3 \ | where, BB1, BB2 contain conditional branches.
108 /// \ | / BB3 contains unconditional branch.
109 /// \ | / BB4 corresponds to \param BB which is also the merge.
113 /// Corresponding source code:
115 /// if (a == b && c == d)
116 /// statement; // BB3
118 /// Case 2: \param BB BB is on the then-path.
123 /// \ / | where BB1, BB2 contain conditional branches.
124 /// BB => BB3 | BB3 contains unconditiona branch and corresponds
125 /// \ / to \param BB. BB4 is the merge.
128 /// Corresponding source code:
130 /// if (a == b || c == d)
131 /// statement; // BB3
133 /// In both cases, \param BB is the common successor of conditional branches.
134 /// In Case 1, \param BB (BB4) has an unconditional branch (BB3) as
135 /// its predecessor. In Case 2, \param BB (BB3) only has conditional branches
136 /// as its predecessors.
137 bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder) {
138 PHINode *PHI = dyn_cast<PHINode>(BB->begin());
140 return false; // For simplicity, avoid cases containing PHI nodes.
142 BasicBlock *LastCondBlock = nullptr;
143 BasicBlock *FirstCondBlock = nullptr;
144 BasicBlock *UnCondBlock = nullptr;
147 // Check predecessors of \param BB.
148 SmallPtrSet<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
149 for (SmallPtrSetIterator<BasicBlock *> PI = Preds.begin(), PE = Preds.end();
151 BasicBlock *Pred = *PI;
152 BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator());
154 // All predecessors should terminate with a branch.
158 BasicBlock *PP = Pred->getSinglePredecessor();
160 if (PBI->isUnconditional()) {
161 // Case 1: Pred (BB3) is an unconditional block, it should
162 // have a single predecessor (BB2) that is also a predecessor
163 // of \param BB (BB4) and should not have address-taken.
164 // There should exist only one such unconditional
165 // branch among the predecessors.
166 if (UnCondBlock || !PP || (Preds.count(PP) == 0) ||
167 Pred->hasAddressTaken())
174 // Only conditional branches are allowed beyond this point.
175 assert(PBI->isConditional());
177 // Condition's unique use should be the branch instruction.
178 Value *PC = PBI->getCondition();
179 if (!PC || !PC->hasOneUse())
182 if (PP && Preds.count(PP)) {
183 // These are internal condition blocks to be merged from, e.g.,
184 // BB2 in both cases.
185 // Should not be address-taken.
186 if (Pred->hasAddressTaken())
189 // Instructions in the internal condition blocks should be safe
191 for (BasicBlock::iterator BI = Pred->begin(), BE = PBI->getIterator();
193 Instruction *CI = &*BI++;
194 if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI))
198 // This is the condition block to be merged into, e.g. BB1 in
202 FirstCondBlock = Pred;
205 // Find whether BB is uniformly on the true (or false) path
206 // for all of its predecessors.
207 BasicBlock *PS1 = PBI->getSuccessor(0);
208 BasicBlock *PS2 = PBI->getSuccessor(1);
209 BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
210 int CIdx = (PS1 == BB) ? 0 : 1;
214 else if (CIdx != Idx)
217 // PS is the successor which is not BB. Check successors to identify
218 // the last conditional branch.
219 if (Preds.count(PS) == 0) {
221 LastCondBlock = Pred;
224 BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
225 if (BPS && BPS->isUnconditional()) {
226 // Case 1: PS(BB3) should be an unconditional branch.
227 LastCondBlock = Pred;
232 if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
235 TerminatorInst *TBB = LastCondBlock->getTerminator();
236 BasicBlock *PS1 = TBB->getSuccessor(0);
237 BasicBlock *PS2 = TBB->getSuccessor(1);
238 BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
239 BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
241 // If PS1 does not jump into PS2, but PS2 jumps into PS1,
242 // attempt branch inversion.
243 if (!PBI1 || !PBI1->isUnconditional() ||
244 (PS1->getTerminator()->getSuccessor(0) != PS2)) {
245 // Check whether PS2 jumps into PS1.
246 if (!PBI2 || !PBI2->isUnconditional() ||
247 (PS2->getTerminator()->getSuccessor(0) != PS1))
250 // Do branch inversion.
251 BasicBlock *CurrBlock = LastCondBlock;
252 bool EverChanged = false;
253 for (; CurrBlock != FirstCondBlock;
254 CurrBlock = CurrBlock->getSinglePredecessor()) {
255 BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator());
256 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
260 CmpInst::Predicate Predicate = CI->getPredicate();
261 // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
262 if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
263 CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
264 BI->swapSuccessors();
271 // PS1 must have a conditional branch.
272 if (!PBI1 || !PBI1->isUnconditional())
275 // PS2 should not contain PHI node.
276 PHI = dyn_cast<PHINode>(PS2->begin());
280 // Do the transformation.
282 BranchInst *PBI = dyn_cast<BranchInst>(FirstCondBlock->getTerminator());
283 bool Iteration = true;
284 IRBuilder<>::InsertPointGuard Guard(Builder);
285 Value *PC = PBI->getCondition();
288 CB = PBI->getSuccessor(1 - Idx);
289 // Delete the conditional branch.
290 FirstCondBlock->getInstList().pop_back();
291 FirstCondBlock->getInstList()
292 .splice(FirstCondBlock->end(), CB->getInstList());
293 PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
294 Value *CC = PBI->getCondition();
296 Builder.SetInsertPoint(PBI);
299 // Case 2, use parallel or.
300 NC = Builder.CreateOr(PC, CC);
302 // Case 1, use parallel and.
303 NC = Builder.CreateAnd(PC, CC);
305 PBI->replaceUsesOfWith(CC, NC);
307 if (CB == LastCondBlock)
309 // Remove internal conditional branches.
310 CB->dropAllReferences();
311 // make CB unreachable and let downstream to delete the block.
312 new UnreachableInst(CB->getContext(), CB);
315 DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
319 /// Compare blocks from two if-regions, where \param Head1 is the entry of the
320 /// 1st if-region. \param Head2 is the entry of the 2nd if-region. \param
321 /// Block1 is a block in the 1st if-region to compare. \param Block2 is a block
322 // in the 2nd if-region to compare. \returns true if \param Block1 and \param
323 /// Block2 have identical instructions and do not have memory reference alias
324 /// with \param Head2.
325 bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
327 BasicBlock *Block2) {
328 TerminatorInst *PTI2 = Head2->getTerminator();
329 Instruction *PBI2 = &Head2->front();
331 bool eq1 = (Block1 == Head1);
332 bool eq2 = (Block2 == Head2);
334 // An empty then-path or else-path.
338 // Check whether instructions in Block1 and Block2 are identical
339 // and do not alias with instructions in Head2.
340 BasicBlock::iterator iter1 = Block1->begin();
341 BasicBlock::iterator end1 = Block1->getTerminator()->getIterator();
342 BasicBlock::iterator iter2 = Block2->begin();
343 BasicBlock::iterator end2 = Block2->getTerminator()->getIterator();
352 if (!iter1->isIdenticalTo(&*iter2))
355 // Illegal to remove instructions with side effects except
356 // non-volatile stores.
357 if (iter1->mayHaveSideEffects()) {
358 Instruction *CurI = &*iter1;
359 StoreInst *SI = dyn_cast<StoreInst>(CurI);
360 if (!SI || SI->isVolatile())
364 // For simplicity and speed, data dependency check can be
365 // avoided if read from memory doesn't exist.
366 if (iter1->mayReadFromMemory())
369 if (iter1->mayWriteToMemory()) {
370 for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
371 if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
372 // Check alias with Head2.
373 if (!AA || AA->alias(&*iter1, &*BI))
385 /// Check whether \param BB is the merge block of a if-region. If yes, check
386 /// whether there exists an adjacent if-region upstream, the two if-regions
387 /// contain identical instructions and can be legally merged. \returns true if
388 /// the two if-regions are merged.
399 bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {
400 BasicBlock *IfTrue2, *IfFalse2;
401 Value *IfCond2 = GetIfCondition(BB, IfTrue2, IfFalse2);
402 Instruction *CInst2 = dyn_cast_or_null<Instruction>(IfCond2);
406 BasicBlock *SecondEntryBlock = CInst2->getParent();
407 if (SecondEntryBlock->hasAddressTaken())
410 BasicBlock *IfTrue1, *IfFalse1;
411 Value *IfCond1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
412 Instruction *CInst1 = dyn_cast_or_null<Instruction>(IfCond1);
416 BasicBlock *FirstEntryBlock = CInst1->getParent();
418 // Either then-path or else-path should be empty.
419 if ((IfTrue1 != FirstEntryBlock) && (IfFalse1 != FirstEntryBlock))
421 if ((IfTrue2 != SecondEntryBlock) && (IfFalse2 != SecondEntryBlock))
424 TerminatorInst *PTI2 = SecondEntryBlock->getTerminator();
425 Instruction *PBI2 = &SecondEntryBlock->front();
427 if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfTrue1,
431 if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfFalse1,
435 // Check whether \param SecondEntryBlock has side-effect and is safe to
437 for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
438 Instruction *CI = &*BI;
439 if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||
440 !isSafeToSpeculativelyExecute(CI))
444 // Merge \param SecondEntryBlock into \param FirstEntryBlock.
445 FirstEntryBlock->getInstList().pop_back();
446 FirstEntryBlock->getInstList()
447 .splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList());
448 BranchInst *PBI = dyn_cast<BranchInst>(FirstEntryBlock->getTerminator());
449 Value *CC = PBI->getCondition();
450 BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
451 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
452 Builder.SetInsertPoint(PBI);
453 Value *NC = Builder.CreateOr(CInst1, CC);
454 PBI->replaceUsesOfWith(CC, NC);
455 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
458 if (IfTrue1 != FirstEntryBlock) {
459 IfTrue1->dropAllReferences();
460 IfTrue1->eraseFromParent();
464 if (IfFalse1 != FirstEntryBlock) {
465 IfFalse1->dropAllReferences();
466 IfFalse1->eraseFromParent();
469 // Remove \param SecondEntryBlock
470 SecondEntryBlock->dropAllReferences();
471 SecondEntryBlock->eraseFromParent();
472 DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
476 bool FlattenCFGOpt::run(BasicBlock *BB) {
477 assert(BB && BB->getParent() && "Block not embedded in function!");
478 assert(BB->getTerminator() && "Degenerate basic block encountered!");
480 IRBuilder<> Builder(BB);
482 if (FlattenParallelAndOr(BB, Builder) || MergeIfRegion(BB, Builder))
487 /// FlattenCFG - This function is used to flatten a CFG. For
488 /// example, it uses parallel-and and parallel-or mode to collapse
489 /// if-conditions and merge if-regions with identical statements.
490 bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) {
491 return FlattenCFGOpt(AA).run(BB);