IfConversion.cpp revision f15d44cc108a1ce8139b3c80fff7b99cbd651333 
1//===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the Evan Cheng and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the machine instruction level if-conversion pass.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "ifconversion"
15#include "llvm/CodeGen/Passes.h"
16#include "llvm/CodeGen/MachineModuleInfo.h"
17#include "llvm/CodeGen/MachineFunctionPass.h"
18#include "llvm/Target/TargetInstrInfo.h"
19#include "llvm/Target/TargetLowering.h"
20#include "llvm/Target/TargetMachine.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/ADT/DepthFirstIterator.h"
23#include "llvm/ADT/Statistic.h"
24using namespace llvm;
25
26STATISTIC(NumIfConvBBs, "Number of if-converted blocks");
27
28namespace {
29  class IfConverter : public MachineFunctionPass {
30    enum BBICKind {
31      ICNotAnalyzed,   // BB has not been analyzed.
32      ICReAnalyze,     // BB must be re-analyzed.
33      ICNotClassfied,  // BB data valid, but not classified.
34      ICEarlyExit,     // BB is entry of an early-exit sub-CFG.
35      ICTriangle,      // BB is entry of a triangle sub-CFG.
36      ICDiamond,       // BB is entry of a diamond sub-CFG.
37      ICChild,         // BB is part of the sub-CFG that'll be predicated.
38      ICDead           // BB has been converted and merged, it's now dead.
39    };
40
41    /// BBInfo - One per MachineBasicBlock, this is used to cache the result
42    /// if-conversion feasibility analysis. This includes results from
43    /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
44    /// classification, and common tail block of its successors (if it's a
45    /// diamond shape), its size, whether it's predicable, and whether any
46    /// instruction can clobber the 'would-be' predicate.
47    ///
48    /// Kind            - Type of block. See BBICKind.
49    /// NonPredSize     - Number of non-predicated instructions.
50    /// isPredicable    - Is it predicable. (FIXME: Remove.)
51    /// hasEarlyExit    - Ends with a return, indirect jump or br to jumptable.
52    /// ModifyPredicate - FIXME: Not used right now. True if BB would modify
53    ///                   the predicate (e.g. has cmp, call, etc.)
54    /// BB              - Corresponding MachineBasicBlock.
55    /// TrueBB / FalseBB- See AnalyzeBranch().
56    /// BrCond          - Conditions for end of block conditional branches.
57    /// Predicate       - Predicate used in the BB.
58    struct BBInfo {
59      BBICKind Kind;
60      unsigned NonPredSize;
61      bool isPredicable;
62      bool hasEarlyExit;
63      bool ModifyPredicate;
64      MachineBasicBlock *BB;
65      MachineBasicBlock *TrueBB;
66      MachineBasicBlock *FalseBB;
67      MachineBasicBlock *TailBB;
68      std::vector<MachineOperand> BrCond;
69      std::vector<MachineOperand> Predicate;
70      BBInfo() : Kind(ICNotAnalyzed), NonPredSize(0), isPredicable(false),
71                 hasEarlyExit(false), ModifyPredicate(false),
72                 BB(0), TrueBB(0), FalseBB(0), TailBB(0) {}
73    };
74
75    /// Roots - Basic blocks that do not have successors. These are the starting
76    /// points of Graph traversal.
77    std::vector<MachineBasicBlock*> Roots;
78
79    /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
80    /// basic block number.
81    std::vector<BBInfo> BBAnalysis;
82
83    const TargetLowering *TLI;
84    const TargetInstrInfo *TII;
85    bool MadeChange;
86  public:
87    static char ID;
88    IfConverter() : MachineFunctionPass((intptr_t)&ID) {}
89
90    virtual bool runOnMachineFunction(MachineFunction &MF);
91    virtual const char *getPassName() const { return "If converter"; }
92
93  private:
94    void StructuralAnalysis(MachineBasicBlock *BB);
95    void FeasibilityAnalysis(BBInfo &BBI,
96                             std::vector<MachineOperand> &Cond);
97    bool AttemptRestructuring(BBInfo &BBI);
98    bool AnalyzeBlocks(MachineFunction &MF,
99                       std::vector<BBInfo*> &Candidates);
100    void ReTryPreds(MachineBasicBlock *BB);
101    bool IfConvertEarlyExit(BBInfo &BBI);
102    bool IfConvertTriangle(BBInfo &BBI);
103    bool IfConvertDiamond(BBInfo &BBI);
104    void PredicateBlock(BBInfo &BBI,
105                        std::vector<MachineOperand> &Cond,
106                        bool IgnoreTerm = false);
107    void MergeBlocks(BBInfo &TrueBBI, BBInfo &FalseBBI);
108  };
109  char IfConverter::ID = 0;
110}
111
112FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
113
114bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
115  TLI = MF.getTarget().getTargetLowering();
116  TII = MF.getTarget().getInstrInfo();
117  if (!TII) return false;
118
119  MF.RenumberBlocks();
120  unsigned NumBBs = MF.getNumBlockIDs();
121  BBAnalysis.resize(NumBBs);
122
123  // Look for root nodes, i.e. blocks without successors.
124  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
125    if (I->succ_size() == 0)
126      Roots.push_back(I);
127
128  std::vector<BBInfo*> Candidates;
129  MadeChange = false;
130  while (true) {
131    bool Change = false;
132
133    // Do an intial analysis for each basic block and finding all the potential
134    // candidates to perform if-convesion.
135    Change |= AnalyzeBlocks(MF, Candidates);
136    while (!Candidates.empty()) {
137      BBInfo &BBI = *Candidates.back();
138      Candidates.pop_back();
139      switch (BBI.Kind) {
140      default: assert(false && "Unexpected!");
141        break;
142      case ICEarlyExit:
143        Change |= IfConvertEarlyExit(BBI);
144        break;
145      case ICTriangle:
146        Change |= IfConvertTriangle(BBI);
147        break;
148      case ICDiamond:
149        Change |= IfConvertDiamond(BBI);
150        break;
151      }
152    }
153
154    MadeChange |= Change;
155    if (!Change)
156      break;
157  }
158
159  Roots.clear();
160  BBAnalysis.clear();
161
162  return MadeChange;
163}
164
165static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
166                                         MachineBasicBlock *TrueBB) {
167  for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
168         E = BB->succ_end(); SI != E; ++SI) {
169    MachineBasicBlock *SuccBB = *SI;
170    if (SuccBB != TrueBB)
171      return SuccBB;
172  }
173  return NULL;
174}
175
176/// StructuralAnalysis - Analyze the structure of the sub-CFG starting from
177/// the specified block. Record its successors and whether it looks like an
178/// if-conversion candidate.
179void IfConverter::StructuralAnalysis(MachineBasicBlock *BB) {
180  BBInfo &BBI = BBAnalysis[BB->getNumber()];
181
182  if (BBI.Kind != ICReAnalyze) {
183    if (BBI.Kind != ICNotAnalyzed)
184      return;  // Already analyzed.
185    BBI.BB = BB;
186    BBI.NonPredSize = std::distance(BB->begin(), BB->end());
187  }
188
189  // Look for 'root' of a simple (non-nested) triangle or diamond.
190  BBI.Kind = ICNotClassfied;
191  bool CanAnalyze = !TII->AnalyzeBranch(*BB, BBI.TrueBB, BBI.FalseBB,
192                                        BBI.BrCond);
193  // Does it end with a return, indirect jump, or jumptable branch?
194  BBI.hasEarlyExit = TII->BlockHasNoFallThrough(*BB) && !BBI.TrueBB;
195  if (!CanAnalyze || !BBI.TrueBB || BBI.BrCond.size() == 0)
196    return;
197
198  // Not a candidate if 'true' block is going to be if-converted.
199  StructuralAnalysis(BBI.TrueBB);
200  BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
201  if (TrueBBI.Kind != ICNotClassfied)
202    return;
203
204  // TODO: Only handle very simple cases for now.
205  if (TrueBBI.FalseBB || TrueBBI.BrCond.size())
206    return;
207
208  // No false branch. This BB must end with a conditional branch and a
209  // fallthrough.
210  if (!BBI.FalseBB)
211    BBI.FalseBB = findFalseBlock(BB, BBI.TrueBB);
212  assert(BBI.FalseBB && "Expected to find the fallthrough block!");
213
214  // Not a candidate if 'false' block is going to be if-converted.
215  StructuralAnalysis(BBI.FalseBB);
216  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
217  if (FalseBBI.Kind != ICNotClassfied)
218    return;
219
220  // TODO: Only handle very simple cases for now.
221  if (FalseBBI.FalseBB || FalseBBI.BrCond.size())
222    return;
223
224  unsigned TrueNumPreds  = BBI.TrueBB->pred_size();
225  unsigned FalseNumPreds = BBI.FalseBB->pred_size();
226  if ((TrueBBI.hasEarlyExit && TrueNumPreds <= 1) &&
227      !(FalseBBI.hasEarlyExit && FalseNumPreds <=1)) {
228    BBI.Kind = ICEarlyExit;
229    TrueBBI.Kind = ICChild;
230  } else if (!(TrueBBI.hasEarlyExit && TrueNumPreds <= 1) &&
231             (FalseBBI.hasEarlyExit && FalseNumPreds <=1)) {
232    BBI.Kind = ICEarlyExit;
233    FalseBBI.Kind = ICChild;
234  } else if (TrueBBI.TrueBB && TrueBBI.TrueBB == BBI.FalseBB) {
235    // Triangle:
236    //   EBB
237    //   | \_
238    //   |  |
239    //   | TBB
240    //   |  /
241    //   FBB
242    BBI.Kind = ICTriangle;
243    TrueBBI.Kind = FalseBBI.Kind = ICChild;
244  } else if (TrueBBI.TrueBB == FalseBBI.TrueBB &&
245             TrueNumPreds <= 1 && FalseNumPreds <= 1) {
246    // Diamond:
247    //   EBB
248    //   / \_
249    //  |   |
250    // TBB FBB
251    //   \ /
252    //  TailBB
253    // Note MBB can be empty in case both TBB and FBB are return blocks.
254    BBI.Kind = ICDiamond;
255    TrueBBI.Kind = FalseBBI.Kind = ICChild;
256    BBI.TailBB = TrueBBI.TrueBB;
257  }
258  return;
259}
260
261/// FeasibilityAnalysis - Determine if the block is predicable. In most
262/// cases, that means all the instructions in the block has M_PREDICABLE flag.
263/// Also checks if the block contains any instruction which can clobber a
264/// predicate (e.g. condition code register). If so, the block is not
265/// predicable unless it's the last instruction. Note, this function assumes
266/// all the terminator instructions can be converted or deleted so it ignore
267/// them.
268void IfConverter::FeasibilityAnalysis(BBInfo &BBI,
269                                      std::vector<MachineOperand> &Cond) {
270  if (BBI.NonPredSize == 0 || BBI.NonPredSize > TLI->getIfCvtBlockSizeLimit())
271    return;
272
273  for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
274       I != E; ++I) {
275    // TODO: check if instruction clobbers predicate.
276    if (TII->isTerminatorInstr(I->getOpcode()))
277      break;
278    if (!I->isPredicable())
279      return;
280  }
281
282  if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Cond))
283    return;
284
285  BBI.isPredicable = true;
286}
287
288/// AttemptRestructuring - Restructure the sub-CFG rooted in the given block to
289/// expose more if-conversion opportunities. e.g.
290///
291///                cmp
292///                b le BB1
293///                /  \____
294///               /        |
295///             cmp        |
296///             b eq BB1   |
297///              /  \____  |
298///             /        \ |
299///                      BB1
300///  ==>
301///
302///                cmp
303///                b eq BB1
304///                /  \____
305///               /        |
306///             cmp        |
307///             b le BB1   |
308///              /  \____  |
309///             /        \ |
310///                      BB1
311bool IfConverter::AttemptRestructuring(BBInfo &BBI) {
312  return false;
313}
314
315/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
316/// candidates. It returns true if any CFG restructuring is done to expose more
317/// if-conversion opportunities.
318bool IfConverter::AnalyzeBlocks(MachineFunction &MF,
319                                std::vector<BBInfo*> &Candidates) {
320  bool Change = false;
321  std::set<MachineBasicBlock*> Visited;
322  for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
323    for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited),
324           E = idf_ext_end(Roots[i], Visited); I != E; ++I) {
325      MachineBasicBlock *BB = *I;
326      StructuralAnalysis(BB);
327      BBInfo &BBI = BBAnalysis[BB->getNumber()];
328      switch (BBI.Kind) {
329        case ICEarlyExit:
330        case ICTriangle:
331        case ICDiamond:
332          Candidates.push_back(&BBI);
333          break;
334        default:
335          Change |= AttemptRestructuring(BBI);
336          break;
337      }
338    }
339  }
340
341  return Change;
342}
343
344/// TransferPreds - Transfer all the predecessors of FromBB to ToBB.
345///
346static void TransferPreds(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) {
347   std::vector<MachineBasicBlock*> Preds(FromBB->pred_begin(),
348                                         FromBB->pred_end());
349    for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
350      MachineBasicBlock *Pred = Preds[i];
351      Pred->removeSuccessor(FromBB);
352      if (!Pred->isSuccessor(ToBB))
353        Pred->addSuccessor(ToBB);
354    }
355}
356
357/// TransferSuccs - Transfer all the successors of FromBB to ToBB.
358///
359static void TransferSuccs(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) {
360   std::vector<MachineBasicBlock*> Succs(FromBB->succ_begin(),
361                                         FromBB->succ_end());
362    for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
363      MachineBasicBlock *Succ = Succs[i];
364      FromBB->removeSuccessor(Succ);
365      if (!ToBB->isSuccessor(Succ))
366        ToBB->addSuccessor(Succ);
367    }
368}
369
370/// isNextBlock - Returns true if ToBB the next basic block after BB.
371///
372static bool isNextBlock(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
373  MachineFunction::iterator Fallthrough = BB;
374  return MachineFunction::iterator(ToBB) == ++Fallthrough;
375}
376
377/// ReTryPreds - Invalidate predecessor BB info so it would be re-analyzed
378/// to determine if it can be if-converted.
379void IfConverter::ReTryPreds(MachineBasicBlock *BB) {
380  for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
381         E = BB->pred_end(); PI != E; ++PI) {
382    BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
383    PBBI.Kind = ICReAnalyze;
384  }
385}
386
387/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
388///
389static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
390                               const TargetInstrInfo *TII) {
391  std::vector<MachineOperand> NoCond;
392  TII->InsertBranch(*BB, ToBB, NULL, NoCond);
393}
394
395/// IfConvertEarlyExit - If convert a early exit sub-CFG.
396///
397bool IfConverter::IfConvertEarlyExit(BBInfo &BBI) {
398  BBI.Kind = ICNotClassfied;
399
400  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
401  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
402  BBInfo *CvtBBI = &TrueBBI;
403  BBInfo *NextBBI = &FalseBBI;
404
405  bool ReserveCond = false;
406  if (TrueBBI.Kind != ICChild) {
407    std::swap(CvtBBI, NextBBI);
408    ReserveCond = true;
409  }
410
411  std::vector<MachineOperand> NewCond(BBI.BrCond);
412  if (ReserveCond)
413    TII->ReverseBranchCondition(NewCond);
414  FeasibilityAnalysis(*CvtBBI, NewCond);
415  if (!CvtBBI->isPredicable)
416    return false;
417
418  PredicateBlock(*CvtBBI, NewCond);
419
420  // Merge converted block into entry block. Also convert the end of the
421  // block conditional branch (to the non-converted block) into an
422  // unconditional one.
423  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
424  MergeBlocks(BBI, *CvtBBI);
425  if (!isNextBlock(BBI.BB, NextBBI->BB))
426    InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
427  std::copy(NewCond.begin(), NewCond.end(), std::back_inserter(BBI.Predicate));
428
429  // Update block info. BB can be iteratively if-converted.
430  BBI.Kind = ICNotAnalyzed;
431  BBI.TrueBB = BBI.FalseBB = NULL;
432  BBI.BrCond.clear();
433  TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
434  ReTryPreds(BBI.BB);
435  CvtBBI->Kind = ICDead;
436
437  // FIXME: Must maintain LiveIns.
438  NumIfConvBBs++;
439  return true;
440}
441
442/// IfConvertTriangle - If convert a triangle sub-CFG.
443///
444bool IfConverter::IfConvertTriangle(BBInfo &BBI) {
445  BBI.Kind = ICNotClassfied;
446
447  BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
448  FeasibilityAnalysis(TrueBBI, BBI.BrCond);
449  if (!TrueBBI.isPredicable)
450    return false;
451
452  // Predicate the 'true' block after removing its branch.
453  TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB);
454  PredicateBlock(TrueBBI, BBI.BrCond);
455
456  // Join the 'true' and 'false' blocks by copying the instructions
457  // from the 'false' block to the 'true' block.
458  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
459  MergeBlocks(TrueBBI, FalseBBI);
460
461  // Now merge the entry of the triangle with the true block.
462  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
463  MergeBlocks(BBI, TrueBBI);
464  std::copy(BBI.BrCond.begin(), BBI.BrCond.end(),
465            std::back_inserter(BBI.Predicate));
466
467  // Update block info. BB can be iteratively if-converted.
468  BBI.Kind = ICNotClassfied;
469  BBI.TrueBB = BBI.FalseBB = NULL;
470  BBI.BrCond.clear();
471  TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
472  ReTryPreds(BBI.BB);
473  TrueBBI.Kind = ICDead;
474
475  // FIXME: Must maintain LiveIns.
476  NumIfConvBBs++;
477  return true;
478}
479
480/// IfConvertDiamond - If convert a diamond sub-CFG.
481///
482bool IfConverter::IfConvertDiamond(BBInfo &BBI) {
483  BBI.Kind = ICNotClassfied;
484
485  bool TrueNeedBr;
486  bool FalseNeedBr;
487  BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
488  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
489  FeasibilityAnalysis(TrueBBI, BBI.BrCond);
490  std::vector<MachineOperand> RevCond(BBI.BrCond);
491  TII->ReverseBranchCondition(RevCond);
492  FeasibilityAnalysis(FalseBBI, RevCond);
493
494  SmallVector<MachineInstr*, 2> Dups;
495  bool Proceed = TrueBBI.isPredicable && FalseBBI.isPredicable;
496  if (Proceed) {
497    // Check the 'true' and 'false' blocks if either isn't ended with a branch.
498    // Either the block fallthrough to another block or it ends with a
499    // return. If it's the former, add a branch to its successor.
500    TrueNeedBr  = !TrueBBI.TrueBB && BBI.TrueBB->succ_size();
501    FalseNeedBr = !FalseBBI.TrueBB && BBI.FalseBB->succ_size();
502    if (TrueNeedBr && TrueBBI.ModifyPredicate) {
503      TrueBBI.isPredicable = false;
504      Proceed = false;
505    }
506    if (FalseNeedBr && FalseBBI.ModifyPredicate) {
507      FalseBBI.isPredicable = false;
508      Proceed = false;
509    }
510
511    if (Proceed) {
512      if (!BBI.TailBB) {
513        // No common merge block. Check if the terminators (e.g. return) are
514        // the same or predicable.
515        MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator();
516        MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator();
517        while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) {
518          if (TT->isIdenticalTo(FT))
519            Dups.push_back(TT);  // Will erase these later.
520          else if (!TT->isPredicable() && !FT->isPredicable()) {
521            Proceed = false;
522            break; // Can't if-convert. Abort!
523          }
524          ++TT;
525          ++FT;
526        }
527
528        // One of the two pathes have more terminators, make sure they are
529        // all predicable.
530        while (Proceed && TT != BBI.TrueBB->end())
531          if (!TT->isPredicable()) {
532            Proceed = false;
533            break; // Can't if-convert. Abort!
534          }
535        while (Proceed && FT != BBI.FalseBB->end())
536          if (!FT->isPredicable()) {
537            Proceed = false;
538            break; // Can't if-convert. Abort!
539          }
540      }
541    }
542  }
543
544  if (!Proceed)
545    return false;
546
547  // Remove the duplicated instructions from the 'true' block.
548  for (unsigned i = 0, e = Dups.size(); i != e; ++i) {
549    Dups[i]->eraseFromParent();
550    --TrueBBI.NonPredSize;
551  }
552
553  // Predicate the 'true' block after removing its branch.
554  TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB);
555  PredicateBlock(TrueBBI, BBI.BrCond);
556
557  // Predicate the 'false' block.
558  PredicateBlock(FalseBBI, RevCond, true);
559
560  // Merge the 'true' and 'false' blocks by copying the instructions
561  // from the 'false' block to the 'true' block. That is, unless the true
562  // block would clobber the predicate, in that case, do the opposite.
563  BBInfo *CvtBBI;
564  if (!TrueBBI.ModifyPredicate) {
565    // Add a conditional branch from 'true' to 'true' successor if needed.
566    if (TrueNeedBr)
567      TII->InsertBranch(*BBI.TrueBB, *BBI.TrueBB->succ_begin(), NULL,
568                        BBI.BrCond);
569    // Add an unconditional branch from 'false' to to 'false' successor if it
570    // will not be the fallthrough block.
571    if (FalseNeedBr &&
572        !isNextBlock(BBI.BB, *BBI.FalseBB->succ_begin()))
573      InsertUncondBranch(BBI.FalseBB, *BBI.FalseBB->succ_begin(), TII);
574    MergeBlocks(TrueBBI, FalseBBI);
575    CvtBBI = &TrueBBI;
576  } else {
577    // Add a conditional branch from 'false' to 'false' successor if needed.
578    if (FalseNeedBr)
579      TII->InsertBranch(*BBI.FalseBB, *BBI.FalseBB->succ_begin(), NULL,
580                        RevCond);
581    // Add an unconditional branch from 'true' to to 'true' successor if it
582    // will not be the fallthrough block.
583    if (TrueNeedBr &&
584        !isNextBlock(BBI.BB, *BBI.TrueBB->succ_begin()))
585      InsertUncondBranch(BBI.TrueBB, *BBI.TrueBB->succ_begin(), TII);
586    MergeBlocks(FalseBBI, TrueBBI);
587    CvtBBI = &FalseBBI;
588  }
589
590  // Remove the conditional branch from entry to the blocks.
591  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
592
593  bool OkToIfcvt = true;
594  // Merge the combined block into the entry of the diamond if the entry
595  // block is its only predecessor. Otherwise, insert an unconditional
596  // branch from entry to the if-converted block.
597  if (CvtBBI->BB->pred_size() == 1) {
598    MergeBlocks(BBI, *CvtBBI);
599    CvtBBI = &BBI;
600    OkToIfcvt = false;
601  } else
602    InsertUncondBranch(BBI.BB, CvtBBI->BB, TII);
603
604  // If the if-converted block fallthrough or unconditionally branch into the
605  // tail block, and the tail block does not have other predecessors, then
606  // fold the tail block in as well.
607  if (BBI.TailBB &&
608      BBI.TailBB->pred_size() == 1 && CvtBBI->BB->succ_size() == 1) {
609    CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
610    BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()];
611    MergeBlocks(*CvtBBI, TailBBI);
612    TailBBI.Kind = ICDead;
613  }
614
615  // Update block info. BB may be iteratively if-converted.
616  if (OkToIfcvt) {
617    BBI.Kind = ICNotClassfied;
618    BBI.TrueBB = BBI.FalseBB = NULL;
619    BBI.BrCond.clear();
620    TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
621    ReTryPreds(BBI.BB);
622  }
623  TrueBBI.Kind = ICDead;
624  FalseBBI.Kind = ICDead;
625
626  // FIXME: Must maintain LiveIns.
627  NumIfConvBBs += 2;
628  return true;
629}
630
631/// PredicateBlock - Predicate every instruction in the block with the specified
632/// condition. If IgnoreTerm is true, skip over all terminator instructions.
633void IfConverter::PredicateBlock(BBInfo &BBI,
634                                 std::vector<MachineOperand> &Cond,
635                                 bool IgnoreTerm) {
636  for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
637       I != E; ++I) {
638    MachineInstr *MI = I;
639    if (IgnoreTerm && TII->isTerminatorInstr(MI->getOpcode()))
640      continue;
641    if (TII->isPredicated(MI))
642      continue;
643    if (!TII->PredicateInstruction(MI, Cond)) {
644      cerr << "Unable to predication " << *I << "!\n";
645      abort();
646    }
647  }
648
649  BBI.NonPredSize = 0;
650}
651
652/// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
653///
654void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
655  ToBBI.BB->splice(ToBBI.BB->end(),
656                   FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
657
658  // If FromBBI is previously a successor, remove it from ToBBI's successor
659  // list and update its TrueBB / FalseBB field if needed.
660  if (ToBBI.BB->isSuccessor(FromBBI.BB))
661    ToBBI.BB->removeSuccessor(FromBBI.BB);
662
663  // Transfer preds / succs and update size.
664  TransferPreds(ToBBI.BB, FromBBI.BB);
665  TransferSuccs(ToBBI.BB, FromBBI.BB);
666  ToBBI.NonPredSize += FromBBI.NonPredSize;
667  FromBBI.NonPredSize = 0;
668}
669