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