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"
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "flattencfg"
25 
26 namespace {
27 class 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 
45 public:
FlattenCFGOpt(AliasAnalysis * AA)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 ///
FlattenParallelAndOr(BasicBlock * BB,IRBuilder<> & Builder,Pass * P)125 bool 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     for (;CurrBlock != FirstCondBlock;
242           CurrBlock = CurrBlock->getSinglePredecessor()) {
243       BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator());
244       CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
245       if (!CI)
246         continue;
247 
248       CmpInst::Predicate Predicate = CI->getPredicate();
249       // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
250       if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
251         CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
252         BI->swapSuccessors();
253         EverChanged = true;
254       }
255     }
256     return EverChanged;
257   }
258 
259   // PS1 must have a conditional branch.
260   if (!PBI1 || !PBI1->isUnconditional())
261     return false;
262 
263   // PS2 should not contain PHI node.
264   PHI = dyn_cast<PHINode>(PS2->begin());
265   if (PHI)
266     return false;
267 
268   // Do the transformation.
269   BasicBlock *CB;
270   BranchInst *PBI = dyn_cast<BranchInst>(FirstCondBlock->getTerminator());
271   bool Iteration = true;
272   IRBuilder<>::InsertPointGuard Guard(Builder);
273   Value *PC = PBI->getCondition();
274 
275   do {
276     CB = PBI->getSuccessor(1 - Idx);
277     // Delete the conditional branch.
278     FirstCondBlock->getInstList().pop_back();
279     FirstCondBlock->getInstList()
280         .splice(FirstCondBlock->end(), CB->getInstList());
281     PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
282     Value *CC = PBI->getCondition();
283     // Merge conditions.
284     Builder.SetInsertPoint(PBI);
285     Value *NC;
286     if (Idx == 0)
287       // Case 2, use parallel or.
288       NC = Builder.CreateOr(PC, CC);
289     else
290       // Case 1, use parallel and.
291       NC = Builder.CreateAnd(PC, CC);
292 
293     PBI->replaceUsesOfWith(CC, NC);
294     PC = NC;
295     if (CB == LastCondBlock)
296       Iteration = false;
297     // Remove internal conditional branches.
298     CB->dropAllReferences();
299     // make CB unreachable and let downstream to delete the block.
300     new UnreachableInst(CB->getContext(), CB);
301   } while (Iteration);
302 
303   DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
304   return true;
305 }
306 
307 /// Compare blocks from two if-regions, where \param Head1 is the entry of the
308 /// 1st if-region. \param Head2 is the entry of the 2nd if-region. \param
309 /// Block1 is a block in the 1st if-region to compare. \param Block2 is a block
310 //  in the 2nd if-region to compare.  \returns true if \param Block1 and \param
311 /// Block2 have identical instructions and do not have memory reference alias
312 /// with \param Head2.
313 ///
CompareIfRegionBlock(BasicBlock * Head1,BasicBlock * Head2,BasicBlock * Block1,BasicBlock * Block2)314 bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
315                                          BasicBlock *Block1,
316                                          BasicBlock *Block2) {
317   TerminatorInst *PTI2 = Head2->getTerminator();
318   Instruction *PBI2 = Head2->begin();
319 
320   bool eq1 = (Block1 == Head1);
321   bool eq2 = (Block2 == Head2);
322   if (eq1 || eq2) {
323     // An empty then-path or else-path.
324     return (eq1 == eq2);
325   }
326 
327   // Check whether instructions in Block1 and Block2 are identical
328   // and do not alias with instructions in Head2.
329   BasicBlock::iterator iter1 = Block1->begin();
330   BasicBlock::iterator end1 = Block1->getTerminator();
331   BasicBlock::iterator iter2 = Block2->begin();
332   BasicBlock::iterator end2 = Block2->getTerminator();
333 
334   while (1) {
335     if (iter1 == end1) {
336       if (iter2 != end2)
337         return false;
338       break;
339     }
340 
341     if (!iter1->isIdenticalTo(iter2))
342       return false;
343 
344     // Illegal to remove instructions with side effects except
345     // non-volatile stores.
346     if (iter1->mayHaveSideEffects()) {
347       Instruction *CurI = &*iter1;
348       StoreInst *SI = dyn_cast<StoreInst>(CurI);
349       if (!SI || SI->isVolatile())
350         return false;
351     }
352 
353     // For simplicity and speed, data dependency check can be
354     // avoided if read from memory doesn't exist.
355     if (iter1->mayReadFromMemory())
356       return false;
357 
358     if (iter1->mayWriteToMemory()) {
359       for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) {
360         if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
361           // Check alias with Head2.
362           if (!AA || AA->alias(iter1, BI))
363             return false;
364         }
365       }
366     }
367     ++iter1;
368     ++iter2;
369   }
370 
371   return true;
372 }
373 
374 /// Check whether \param BB is the merge block of a if-region.  If yes, check
375 /// whether there exists an adjacent if-region upstream, the two if-regions
376 /// contain identical instructions and can be legally merged.  \returns true if
377 /// the two if-regions are merged.
378 ///
379 /// From:
380 /// if (a)
381 ///   statement;
382 /// if (b)
383 ///   statement;
384 ///
385 /// To:
386 /// if (a || b)
387 ///   statement;
388 ///
MergeIfRegion(BasicBlock * BB,IRBuilder<> & Builder,Pass * P)389 bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder,
390                                   Pass *P) {
391   BasicBlock *IfTrue2, *IfFalse2;
392   Value *IfCond2 = GetIfCondition(BB, IfTrue2, IfFalse2);
393   Instruction *CInst2 = dyn_cast_or_null<Instruction>(IfCond2);
394   if (!CInst2)
395     return false;
396 
397   BasicBlock *SecondEntryBlock = CInst2->getParent();
398   if (SecondEntryBlock->hasAddressTaken())
399     return false;
400 
401   BasicBlock *IfTrue1, *IfFalse1;
402   Value *IfCond1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
403   Instruction *CInst1 = dyn_cast_or_null<Instruction>(IfCond1);
404   if (!CInst1)
405     return false;
406 
407   BasicBlock *FirstEntryBlock = CInst1->getParent();
408 
409   // Either then-path or else-path should be empty.
410   if ((IfTrue1 != FirstEntryBlock) && (IfFalse1 != FirstEntryBlock))
411     return false;
412   if ((IfTrue2 != SecondEntryBlock) && (IfFalse2 != SecondEntryBlock))
413     return false;
414 
415   TerminatorInst *PTI2 = SecondEntryBlock->getTerminator();
416   Instruction *PBI2 = SecondEntryBlock->begin();
417 
418   if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfTrue1,
419                             IfTrue2))
420     return false;
421 
422   if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfFalse1,
423                             IfFalse2))
424     return false;
425 
426   // Check whether \param SecondEntryBlock has side-effect and is safe to
427   // speculate.
428   for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) {
429     Instruction *CI = BI;
430     if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||
431         !isSafeToSpeculativelyExecute(CI))
432       return false;
433   }
434 
435   // Merge \param SecondEntryBlock into \param FirstEntryBlock.
436   FirstEntryBlock->getInstList().pop_back();
437   FirstEntryBlock->getInstList()
438       .splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList());
439   BranchInst *PBI = dyn_cast<BranchInst>(FirstEntryBlock->getTerminator());
440   Value *CC = PBI->getCondition();
441   BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
442   BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
443   Builder.SetInsertPoint(PBI);
444   Value *NC = Builder.CreateOr(CInst1, CC);
445   PBI->replaceUsesOfWith(CC, NC);
446   Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
447 
448   // Remove IfTrue1
449   if (IfTrue1 != FirstEntryBlock) {
450     IfTrue1->dropAllReferences();
451     IfTrue1->eraseFromParent();
452   }
453 
454   // Remove IfFalse1
455   if (IfFalse1 != FirstEntryBlock) {
456     IfFalse1->dropAllReferences();
457     IfFalse1->eraseFromParent();
458   }
459 
460   // Remove \param SecondEntryBlock
461   SecondEntryBlock->dropAllReferences();
462   SecondEntryBlock->eraseFromParent();
463   DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
464   return true;
465 }
466 
run(BasicBlock * BB)467 bool FlattenCFGOpt::run(BasicBlock *BB) {
468   bool Changed = false;
469   assert(BB && BB->getParent() && "Block not embedded in function!");
470   assert(BB->getTerminator() && "Degenerate basic block encountered!");
471 
472   IRBuilder<> Builder(BB);
473 
474   if (FlattenParallelAndOr(BB, Builder))
475     return true;
476 
477   if (MergeIfRegion(BB, Builder))
478     return true;
479 
480   return Changed;
481 }
482 
483 /// FlattenCFG - This function is used to flatten a CFG.  For
484 /// example, it uses parallel-and and parallel-or mode to collapse
485 //  if-conditions and merge if-regions with identical statements.
486 ///
FlattenCFG(BasicBlock * BB,AliasAnalysis * AA)487 bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) {
488   return FlattenCFGOpt(AA).run(BB);
489 }
490