IfConversion.cpp revision 3ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1 
1//===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
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// This file implements the machine instruction level if-conversion pass.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "ifcvt"
15#include "BranchFolding.h"
16#include "llvm/Function.h"
17#include "llvm/CodeGen/Passes.h"
18#include "llvm/CodeGen/MachineModuleInfo.h"
19#include "llvm/CodeGen/MachineFunctionPass.h"
20#include "llvm/Target/TargetInstrInfo.h"
21#include "llvm/Target/TargetInstrItineraries.h"
22#include "llvm/Target/TargetLowering.h"
23#include "llvm/Target/TargetMachine.h"
24#include "llvm/Target/TargetRegisterInfo.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/ErrorHandling.h"
28#include "llvm/Support/raw_ostream.h"
29#include "llvm/ADT/DepthFirstIterator.h"
30#include "llvm/ADT/Statistic.h"
31#include "llvm/ADT/STLExtras.h"
32using namespace llvm;
33
34// Hidden options for help debugging.
35static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
36static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
37static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
38static cl::opt<bool> DisableSimple("disable-ifcvt-simple",
39                                   cl::init(false), cl::Hidden);
40static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
41                                    cl::init(false), cl::Hidden);
42static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
43                                     cl::init(false), cl::Hidden);
44static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
45                                      cl::init(false), cl::Hidden);
46static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
47                                      cl::init(false), cl::Hidden);
48static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev",
49                                       cl::init(false), cl::Hidden);
50static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
51                                    cl::init(false), cl::Hidden);
52static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",
53                                     cl::init(true), cl::Hidden);
54
55STATISTIC(NumSimple,       "Number of simple if-conversions performed");
56STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
57STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
58STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
59STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
60STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
61STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
62STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
63STATISTIC(NumDupBBs,       "Number of duplicated blocks");
64
65namespace {
66  class IfConverter : public MachineFunctionPass {
67    enum IfcvtKind {
68      ICNotClassfied,  // BB data valid, but not classified.
69      ICSimpleFalse,   // Same as ICSimple, but on the false path.
70      ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
71      ICTriangleFRev,  // Same as ICTriangleFalse, but false path rev condition.
72      ICTriangleRev,   // Same as ICTriangle, but true path rev condition.
73      ICTriangleFalse, // Same as ICTriangle, but on the false path.
74      ICTriangle,      // BB is entry of a triangle sub-CFG.
75      ICDiamond        // BB is entry of a diamond sub-CFG.
76    };
77
78    /// BBInfo - One per MachineBasicBlock, this is used to cache the result
79    /// if-conversion feasibility analysis. This includes results from
80    /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
81    /// classification, and common tail block of its successors (if it's a
82    /// diamond shape), its size, whether it's predicable, and whether any
83    /// instruction can clobber the 'would-be' predicate.
84    ///
85    /// IsDone          - True if BB is not to be considered for ifcvt.
86    /// IsBeingAnalyzed - True if BB is currently being analyzed.
87    /// IsAnalyzed      - True if BB has been analyzed (info is still valid).
88    /// IsEnqueued      - True if BB has been enqueued to be ifcvt'ed.
89    /// IsBrAnalyzable  - True if AnalyzeBranch() returns false.
90    /// HasFallThrough  - True if BB may fallthrough to the following BB.
91    /// IsUnpredicable  - True if BB is known to be unpredicable.
92    /// ClobbersPred    - True if BB could modify predicates (e.g. has
93    ///                   cmp, call, etc.)
94    /// NonPredSize     - Number of non-predicated instructions.
95    /// BB              - Corresponding MachineBasicBlock.
96    /// TrueBB / FalseBB- See AnalyzeBranch().
97    /// BrCond          - Conditions for end of block conditional branches.
98    /// Predicate       - Predicate used in the BB.
99    struct BBInfo {
100      bool IsDone          : 1;
101      bool IsBeingAnalyzed : 1;
102      bool IsAnalyzed      : 1;
103      bool IsEnqueued      : 1;
104      bool IsBrAnalyzable  : 1;
105      bool HasFallThrough  : 1;
106      bool IsUnpredicable  : 1;
107      bool CannotBeCopied  : 1;
108      bool ClobbersPred    : 1;
109      unsigned NonPredSize;
110      MachineBasicBlock *BB;
111      MachineBasicBlock *TrueBB;
112      MachineBasicBlock *FalseBB;
113      SmallVector<MachineOperand, 4> BrCond;
114      SmallVector<MachineOperand, 4> Predicate;
115      BBInfo() : IsDone(false), IsBeingAnalyzed(false),
116                 IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
117                 HasFallThrough(false), IsUnpredicable(false),
118                 CannotBeCopied(false), ClobbersPred(false), NonPredSize(0),
119                 BB(0), TrueBB(0), FalseBB(0) {}
120    };
121
122    /// IfcvtToken - Record information about pending if-conversions to attempt:
123    /// BBI             - Corresponding BBInfo.
124    /// Kind            - Type of block. See IfcvtKind.
125    /// NeedSubsumption - True if the to-be-predicated BB has already been
126    ///                   predicated.
127    /// NumDups      - Number of instructions that would be duplicated due
128    ///                   to this if-conversion. (For diamonds, the number of
129    ///                   identical instructions at the beginnings of both
130    ///                   paths).
131    /// NumDups2     - For diamonds, the number of identical instructions
132    ///                   at the ends of both paths.
133    struct IfcvtToken {
134      BBInfo &BBI;
135      IfcvtKind Kind;
136      bool NeedSubsumption;
137      unsigned NumDups;
138      unsigned NumDups2;
139      IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0)
140        : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {}
141    };
142
143    /// Roots - Basic blocks that do not have successors. These are the starting
144    /// points of Graph traversal.
145    std::vector<MachineBasicBlock*> Roots;
146
147    /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
148    /// basic block number.
149    std::vector<BBInfo> BBAnalysis;
150
151    const TargetLowering *TLI;
152    const TargetInstrInfo *TII;
153    const TargetRegisterInfo *TRI;
154    const InstrItineraryData *InstrItins;
155    bool MadeChange;
156    int FnNum;
157  public:
158    static char ID;
159    IfConverter() : MachineFunctionPass(ID), FnNum(-1) {}
160
161    virtual bool runOnMachineFunction(MachineFunction &MF);
162    virtual const char *getPassName() const { return "If Converter"; }
163
164  private:
165    bool ReverseBranchCondition(BBInfo &BBI);
166    bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const;
167    bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
168                       bool FalseBranch, unsigned &Dups) const;
169    bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
170                      unsigned &Dups1, unsigned &Dups2) const;
171    void ScanInstructions(BBInfo &BBI);
172    BBInfo &AnalyzeBlock(MachineBasicBlock *BB,
173                         std::vector<IfcvtToken*> &Tokens);
174    bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
175                             bool isTriangle = false, bool RevBranch = false);
176    void AnalyzeBlocks(MachineFunction &MF, std::vector<IfcvtToken*> &Tokens);
177    void InvalidatePreds(MachineBasicBlock *BB);
178    void RemoveExtraEdges(BBInfo &BBI);
179    bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
180    bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
181    bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
182                          unsigned NumDups1, unsigned NumDups2);
183    void PredicateBlock(BBInfo &BBI,
184                        MachineBasicBlock::iterator E,
185                        SmallVectorImpl<MachineOperand> &Cond,
186                        SmallSet<unsigned, 4> &Redefs);
187    void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
188                               SmallVectorImpl<MachineOperand> &Cond,
189                               SmallSet<unsigned, 4> &Redefs,
190                               bool IgnoreBr = false);
191    void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);
192
193    bool MeetIfcvtSizeLimit(MachineBasicBlock &BB, unsigned Size) const {
194      return Size > 0 && TII->isProfitableToIfCvt(BB, Size);
195    }
196
197    bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB, unsigned TSize,
198                            MachineBasicBlock &FBB, unsigned FSize) const {
199      return TSize > 0 && FSize > 0 &&
200        TII->isProfitableToIfCvt(TBB, TSize, FBB, FSize);
201    }
202
203    // blockAlwaysFallThrough - Block ends without a terminator.
204    bool blockAlwaysFallThrough(BBInfo &BBI) const {
205      return BBI.IsBrAnalyzable && BBI.TrueBB == NULL;
206    }
207
208    // IfcvtTokenCmp - Used to sort if-conversion candidates.
209    static bool IfcvtTokenCmp(IfcvtToken *C1, IfcvtToken *C2) {
210      int Incr1 = (C1->Kind == ICDiamond)
211        ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;
212      int Incr2 = (C2->Kind == ICDiamond)
213        ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;
214      if (Incr1 > Incr2)
215        return true;
216      else if (Incr1 == Incr2) {
217        // Favors subsumption.
218        if (C1->NeedSubsumption == false && C2->NeedSubsumption == true)
219          return true;
220        else if (C1->NeedSubsumption == C2->NeedSubsumption) {
221          // Favors diamond over triangle, etc.
222          if ((unsigned)C1->Kind < (unsigned)C2->Kind)
223            return true;
224          else if (C1->Kind == C2->Kind)
225            return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
226        }
227      }
228      return false;
229    }
230  };
231
232  char IfConverter::ID = 0;
233}
234
235INITIALIZE_PASS(IfConverter, "if-converter", "If Converter", false, false);
236
237FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
238
239bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
240  TLI = MF.getTarget().getTargetLowering();
241  TII = MF.getTarget().getInstrInfo();
242  TRI = MF.getTarget().getRegisterInfo();
243  InstrItins = MF.getTarget().getInstrItineraryData();
244  if (!TII) return false;
245
246  // Tail merge tend to expose more if-conversion opportunities.
247  BranchFolder BF(true);
248  bool BFChange = BF.OptimizeFunction(MF, TII,
249                                   MF.getTarget().getRegisterInfo(),
250                                   getAnalysisIfAvailable<MachineModuleInfo>());
251
252  DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum <<  ") \'"
253               << MF.getFunction()->getName() << "\'");
254
255  if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
256    DEBUG(dbgs() << " skipped\n");
257    return false;
258  }
259  DEBUG(dbgs() << "\n");
260
261  MF.RenumberBlocks();
262  BBAnalysis.resize(MF.getNumBlockIDs());
263
264  // Look for root nodes, i.e. blocks without successors.
265  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
266    if (I->succ_empty())
267      Roots.push_back(I);
268
269  std::vector<IfcvtToken*> Tokens;
270  MadeChange = false;
271  unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
272    NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
273  while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
274    // Do an initial analysis for each basic block and find all the potential
275    // candidates to perform if-conversion.
276    bool Change = false;
277    AnalyzeBlocks(MF, Tokens);
278    while (!Tokens.empty()) {
279      IfcvtToken *Token = Tokens.back();
280      Tokens.pop_back();
281      BBInfo &BBI = Token->BBI;
282      IfcvtKind Kind = Token->Kind;
283      unsigned NumDups = Token->NumDups;
284      unsigned NumDups2 = Token->NumDups2;
285
286      delete Token;
287
288      // If the block has been evicted out of the queue or it has already been
289      // marked dead (due to it being predicated), then skip it.
290      if (BBI.IsDone)
291        BBI.IsEnqueued = false;
292      if (!BBI.IsEnqueued)
293        continue;
294
295      BBI.IsEnqueued = false;
296
297      bool RetVal = false;
298      switch (Kind) {
299      default: assert(false && "Unexpected!");
300        break;
301      case ICSimple:
302      case ICSimpleFalse: {
303        bool isFalse = Kind == ICSimpleFalse;
304        if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
305        DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ?
306                                            " false" : "")
307                     << "): BB#" << BBI.BB->getNumber() << " ("
308                     << ((Kind == ICSimpleFalse)
309                         ? BBI.FalseBB->getNumber()
310                         : BBI.TrueBB->getNumber()) << ") ");
311        RetVal = IfConvertSimple(BBI, Kind);
312        DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
313        if (RetVal) {
314          if (isFalse) ++NumSimpleFalse;
315          else         ++NumSimple;
316        }
317       break;
318      }
319      case ICTriangle:
320      case ICTriangleRev:
321      case ICTriangleFalse:
322      case ICTriangleFRev: {
323        bool isFalse = Kind == ICTriangleFalse;
324        bool isRev   = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
325        if (DisableTriangle && !isFalse && !isRev) break;
326        if (DisableTriangleR && !isFalse && isRev) break;
327        if (DisableTriangleF && isFalse && !isRev) break;
328        if (DisableTriangleFR && isFalse && isRev) break;
329        DEBUG(dbgs() << "Ifcvt (Triangle");
330        if (isFalse)
331          DEBUG(dbgs() << " false");
332        if (isRev)
333          DEBUG(dbgs() << " rev");
334        DEBUG(dbgs() << "): BB#" << BBI.BB->getNumber() << " (T:"
335                     << BBI.TrueBB->getNumber() << ",F:"
336                     << BBI.FalseBB->getNumber() << ") ");
337        RetVal = IfConvertTriangle(BBI, Kind);
338        DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
339        if (RetVal) {
340          if (isFalse) {
341            if (isRev) ++NumTriangleFRev;
342            else       ++NumTriangleFalse;
343          } else {
344            if (isRev) ++NumTriangleRev;
345            else       ++NumTriangle;
346          }
347        }
348        break;
349      }
350      case ICDiamond: {
351        if (DisableDiamond) break;
352        DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
353                     << BBI.TrueBB->getNumber() << ",F:"
354                     << BBI.FalseBB->getNumber() << ") ");
355        RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
356        DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
357        if (RetVal) ++NumDiamonds;
358        break;
359      }
360      }
361
362      Change |= RetVal;
363
364      NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
365        NumTriangleFalse + NumTriangleFRev + NumDiamonds;
366      if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)
367        break;
368    }
369
370    if (!Change)
371      break;
372    MadeChange |= Change;
373  }
374
375  // Delete tokens in case of early exit.
376  while (!Tokens.empty()) {
377    IfcvtToken *Token = Tokens.back();
378    Tokens.pop_back();
379    delete Token;
380  }
381
382  Tokens.clear();
383  Roots.clear();
384  BBAnalysis.clear();
385
386  if (MadeChange && IfCvtBranchFold) {
387    BranchFolder BF(false);
388    BF.OptimizeFunction(MF, TII,
389                        MF.getTarget().getRegisterInfo(),
390                        getAnalysisIfAvailable<MachineModuleInfo>());
391  }
392
393  MadeChange |= BFChange;
394  return MadeChange;
395}
396
397/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
398/// its 'true' successor.
399static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
400                                         MachineBasicBlock *TrueBB) {
401  for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
402         E = BB->succ_end(); SI != E; ++SI) {
403    MachineBasicBlock *SuccBB = *SI;
404    if (SuccBB != TrueBB)
405      return SuccBB;
406  }
407  return NULL;
408}
409
410/// ReverseBranchCondition - Reverse the condition of the end of the block
411/// branch. Swap block's 'true' and 'false' successors.
412bool IfConverter::ReverseBranchCondition(BBInfo &BBI) {
413  DebugLoc dl;  // FIXME: this is nowhere
414  if (!TII->ReverseBranchCondition(BBI.BrCond)) {
415    TII->RemoveBranch(*BBI.BB);
416    TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);
417    std::swap(BBI.TrueBB, BBI.FalseBB);
418    return true;
419  }
420  return false;
421}
422
423/// getNextBlock - Returns the next block in the function blocks ordering. If
424/// it is the end, returns NULL.
425static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) {
426  MachineFunction::iterator I = BB;
427  MachineFunction::iterator E = BB->getParent()->end();
428  if (++I == E)
429    return NULL;
430  return I;
431}
432
433/// ValidSimple - Returns true if the 'true' block (along with its
434/// predecessor) forms a valid simple shape for ifcvt. It also returns the
435/// number of instructions that the ifcvt would need to duplicate if performed
436/// in Dups.
437bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const {
438  Dups = 0;
439  if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
440    return false;
441
442  if (TrueBBI.IsBrAnalyzable)
443    return false;
444
445  if (TrueBBI.BB->pred_size() > 1) {
446    if (TrueBBI.CannotBeCopied ||
447        !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize))
448      return false;
449    Dups = TrueBBI.NonPredSize;
450  }
451
452  return true;
453}
454
455/// ValidTriangle - Returns true if the 'true' and 'false' blocks (along
456/// with their common predecessor) forms a valid triangle shape for ifcvt.
457/// If 'FalseBranch' is true, it checks if 'true' block's false branch
458/// branches to the 'false' block rather than the other way around. It also
459/// returns the number of instructions that the ifcvt would need to duplicate
460/// if performed in 'Dups'.
461bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
462                                bool FalseBranch, unsigned &Dups) const {
463  Dups = 0;
464  if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
465    return false;
466
467  if (TrueBBI.BB->pred_size() > 1) {
468    if (TrueBBI.CannotBeCopied)
469      return false;
470
471    unsigned Size = TrueBBI.NonPredSize;
472    if (TrueBBI.IsBrAnalyzable) {
473      if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
474        // Ends with an unconditional branch. It will be removed.
475        --Size;
476      else {
477        MachineBasicBlock *FExit = FalseBranch
478          ? TrueBBI.TrueBB : TrueBBI.FalseBB;
479        if (FExit)
480          // Require a conditional branch
481          ++Size;
482      }
483    }
484    if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size))
485      return false;
486    Dups = Size;
487  }
488
489  MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
490  if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
491    MachineFunction::iterator I = TrueBBI.BB;
492    if (++I == TrueBBI.BB->getParent()->end())
493      return false;
494    TExit = I;
495  }
496  return TExit && TExit == FalseBBI.BB;
497}
498
499static
500MachineBasicBlock::iterator firstNonBranchInst(MachineBasicBlock *BB,
501                                               const TargetInstrInfo *TII) {
502  MachineBasicBlock::iterator I = BB->end();
503  while (I != BB->begin()) {
504    --I;
505    if (!I->getDesc().isBranch())
506      break;
507  }
508  return I;
509}
510
511/// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
512/// with their common predecessor) forms a valid diamond shape for ifcvt.
513bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
514                               unsigned &Dups1, unsigned &Dups2) const {
515  Dups1 = Dups2 = 0;
516  if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
517      FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
518    return false;
519
520  MachineBasicBlock *TT = TrueBBI.TrueBB;
521  MachineBasicBlock *FT = FalseBBI.TrueBB;
522
523  if (!TT && blockAlwaysFallThrough(TrueBBI))
524    TT = getNextBlock(TrueBBI.BB);
525  if (!FT && blockAlwaysFallThrough(FalseBBI))
526    FT = getNextBlock(FalseBBI.BB);
527  if (TT != FT)
528    return false;
529  if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
530    return false;
531  if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
532    return false;
533
534  // FIXME: Allow true block to have an early exit?
535  if (TrueBBI.FalseBB || FalseBBI.FalseBB ||
536      (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred))
537    return false;
538
539  MachineBasicBlock::iterator TI = TrueBBI.BB->begin();
540  MachineBasicBlock::iterator FI = FalseBBI.BB->begin();
541  MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
542  MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
543  // Skip dbg_value instructions
544  while (TI != TIE && TI->isDebugValue())
545    ++TI;
546  while (FI != FIE && FI->isDebugValue())
547    ++FI;
548  while (TI != TIE && FI != FIE) {
549    // Skip dbg_value instructions. These do not count.
550    if (TI->isDebugValue()) {
551      while (TI != TIE && TI->isDebugValue())
552        ++TI;
553      if (TI == TIE)
554        break;
555    }
556    if (FI->isDebugValue()) {
557      while (FI != FIE && FI->isDebugValue())
558        ++FI;
559      if (FI == FIE)
560        break;
561    }
562    if (!TI->isIdenticalTo(FI))
563      break;
564    ++Dups1;
565    ++TI;
566    ++FI;
567  }
568
569  TI = firstNonBranchInst(TrueBBI.BB, TII);
570  FI = firstNonBranchInst(FalseBBI.BB, TII);
571  MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
572  MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
573  // Skip dbg_value instructions at end of the bb's.
574  while (TI != TIB && TI->isDebugValue())
575    --TI;
576  while (FI != FIB && FI->isDebugValue())
577    --FI;
578  while (TI != TIB && FI != FIB) {
579    // Skip dbg_value instructions. These do not count.
580    if (TI->isDebugValue()) {
581      while (TI != TIB && TI->isDebugValue())
582        --TI;
583      if (TI == TIB)
584        break;
585    }
586    if (FI->isDebugValue()) {
587      while (FI != FIB && FI->isDebugValue())
588        --FI;
589      if (FI == FIB)
590        break;
591    }
592    if (!TI->isIdenticalTo(FI))
593      break;
594    ++Dups2;
595    --TI;
596    --FI;
597  }
598
599  return true;
600}
601
602/// ScanInstructions - Scan all the instructions in the block to determine if
603/// the block is predicable. In most cases, that means all the instructions
604/// in the block are isPredicable(). Also checks if the block contains any
605/// instruction which can clobber a predicate (e.g. condition code register).
606/// If so, the block is not predicable unless it's the last instruction.
607void IfConverter::ScanInstructions(BBInfo &BBI) {
608  if (BBI.IsDone)
609    return;
610
611  bool AlreadyPredicated = BBI.Predicate.size() > 0;
612  // First analyze the end of BB branches.
613  BBI.TrueBB = BBI.FalseBB = NULL;
614  BBI.BrCond.clear();
615  BBI.IsBrAnalyzable =
616    !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
617  BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL;
618
619  if (BBI.BrCond.size()) {
620    // No false branch. This BB must end with a conditional branch and a
621    // fallthrough.
622    if (!BBI.FalseBB)
623      BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);
624    if (!BBI.FalseBB) {
625      // Malformed bcc? True and false blocks are the same?
626      BBI.IsUnpredicable = true;
627      return;
628    }
629  }
630
631  // Then scan all the instructions.
632  BBI.NonPredSize = 0;
633  BBI.ClobbersPred = false;
634  for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
635       I != E; ++I) {
636    if (I->isDebugValue())
637      continue;
638
639    const TargetInstrDesc &TID = I->getDesc();
640    if (TID.isNotDuplicable())
641      BBI.CannotBeCopied = true;
642
643    bool isPredicated = TII->isPredicated(I);
644    bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch();
645
646    if (!isCondBr) {
647      if (!isPredicated) {
648        unsigned NumOps = TII->getNumMicroOps(&*I, InstrItins);
649        BBI.NonPredSize += NumOps;
650      } else if (!AlreadyPredicated) {
651        // FIXME: This instruction is already predicated before the
652        // if-conversion pass. It's probably something like a conditional move.
653        // Mark this block unpredicable for now.
654        BBI.IsUnpredicable = true;
655        return;
656      }
657    }
658
659    if (BBI.ClobbersPred && !isPredicated) {
660      // Predicate modification instruction should end the block (except for
661      // already predicated instructions and end of block branches).
662      if (isCondBr) {
663        // A conditional branch is not predicable, but it may be eliminated.
664        continue;
665      }
666
667      // Predicate may have been modified, the subsequent (currently)
668      // unpredicated instructions cannot be correctly predicated.
669      BBI.IsUnpredicable = true;
670      return;
671    }
672
673    // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
674    // still potentially predicable.
675    std::vector<MachineOperand> PredDefs;
676    if (TII->DefinesPredicate(I, PredDefs))
677      BBI.ClobbersPred = true;
678
679    if (!TII->isPredicable(I)) {
680      BBI.IsUnpredicable = true;
681      return;
682    }
683  }
684}
685
686/// FeasibilityAnalysis - Determine if the block is a suitable candidate to be
687/// predicated by the specified predicate.
688bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
689                                      SmallVectorImpl<MachineOperand> &Pred,
690                                      bool isTriangle, bool RevBranch) {
691  // If the block is dead or unpredicable, then it cannot be predicated.
692  if (BBI.IsDone || BBI.IsUnpredicable)
693    return false;
694
695  // If it is already predicated, check if its predicate subsumes the new
696  // predicate.
697  if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred))
698    return false;
699
700  if (BBI.BrCond.size()) {
701    if (!isTriangle)
702      return false;
703
704    // Test predicate subsumption.
705    SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
706    SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
707    if (RevBranch) {
708      if (TII->ReverseBranchCondition(Cond))
709        return false;
710    }
711    if (TII->ReverseBranchCondition(RevPred) ||
712        !TII->SubsumesPredicate(Cond, RevPred))
713      return false;
714  }
715
716  return true;
717}
718
719/// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
720/// the specified block. Record its successors and whether it looks like an
721/// if-conversion candidate.
722IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB,
723                                             std::vector<IfcvtToken*> &Tokens) {
724  BBInfo &BBI = BBAnalysis[BB->getNumber()];
725
726  if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed)
727    return BBI;
728
729  BBI.BB = BB;
730  BBI.IsBeingAnalyzed = true;
731
732  ScanInstructions(BBI);
733
734  // Unanalyzable or ends with fallthrough or unconditional branch.
735  if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) {
736    BBI.IsBeingAnalyzed = false;
737    BBI.IsAnalyzed = true;
738    return BBI;
739  }
740
741  // Do not ifcvt if either path is a back edge to the entry block.
742  if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
743    BBI.IsBeingAnalyzed = false;
744    BBI.IsAnalyzed = true;
745    return BBI;
746  }
747
748  // Do not ifcvt if true and false fallthrough blocks are the same.
749  if (!BBI.FalseBB) {
750    BBI.IsBeingAnalyzed = false;
751    BBI.IsAnalyzed = true;
752    return BBI;
753  }
754
755  BBInfo &TrueBBI  = AnalyzeBlock(BBI.TrueBB, Tokens);
756  BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
757
758  if (TrueBBI.IsDone && FalseBBI.IsDone) {
759    BBI.IsBeingAnalyzed = false;
760    BBI.IsAnalyzed = true;
761    return BBI;
762  }
763
764  SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
765  bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
766
767  unsigned Dups = 0;
768  unsigned Dups2 = 0;
769  bool TNeedSub = TrueBBI.Predicate.size() > 0;
770  bool FNeedSub = FalseBBI.Predicate.size() > 0;
771  bool Enqueued = false;
772  if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
773      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize - (Dups + Dups2),
774                         *FalseBBI.BB, FalseBBI.NonPredSize - (Dups + Dups2)) &&
775      FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
776      FeasibilityAnalysis(FalseBBI, RevCond)) {
777    // Diamond:
778    //   EBB
779    //   / \_
780    //  |   |
781    // TBB FBB
782    //   \ /
783    //  TailBB
784    // Note TailBB can be empty.
785    Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
786                                    Dups2));
787    Enqueued = true;
788  }
789
790  if (ValidTriangle(TrueBBI, FalseBBI, false, Dups) &&
791      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) &&
792      FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
793    // Triangle:
794    //   EBB
795    //   | \_
796    //   |  |
797    //   | TBB
798    //   |  /
799    //   FBB
800    Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
801    Enqueued = true;
802  }
803
804  if (ValidTriangle(TrueBBI, FalseBBI, true, Dups) &&
805      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) &&
806      FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
807    Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
808    Enqueued = true;
809  }
810
811  if (ValidSimple(TrueBBI, Dups) &&
812      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) &&
813      FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
814    // Simple (split, no rejoin):
815    //   EBB
816    //   | \_
817    //   |  |
818    //   | TBB---> exit
819    //   |
820    //   FBB
821    Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
822    Enqueued = true;
823  }
824
825  if (CanRevCond) {
826    // Try the other path...
827    if (ValidTriangle(FalseBBI, TrueBBI, false, Dups) &&
828        MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) &&
829        FeasibilityAnalysis(FalseBBI, RevCond, true)) {
830      Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
831      Enqueued = true;
832    }
833
834    if (ValidTriangle(FalseBBI, TrueBBI, true, Dups) &&
835        MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) &&
836        FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
837      Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
838      Enqueued = true;
839    }
840
841    if (ValidSimple(FalseBBI, Dups) &&
842        MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) &&
843        FeasibilityAnalysis(FalseBBI, RevCond)) {
844      Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
845      Enqueued = true;
846    }
847  }
848
849  BBI.IsEnqueued = Enqueued;
850  BBI.IsBeingAnalyzed = false;
851  BBI.IsAnalyzed = true;
852  return BBI;
853}
854
855/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
856/// candidates.
857void IfConverter::AnalyzeBlocks(MachineFunction &MF,
858                                std::vector<IfcvtToken*> &Tokens) {
859  std::set<MachineBasicBlock*> Visited;
860  for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
861    for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited),
862           E = idf_ext_end(Roots[i], Visited); I != E; ++I) {
863      MachineBasicBlock *BB = *I;
864      AnalyzeBlock(BB, Tokens);
865    }
866  }
867
868  // Sort to favor more complex ifcvt scheme.
869  std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
870}
871
872/// canFallThroughTo - Returns true either if ToBB is the next block after BB or
873/// that all the intervening blocks are empty (given BB can fall through to its
874/// next block).
875static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
876  MachineFunction::iterator PI = BB;
877  MachineFunction::iterator I = llvm::next(PI);
878  MachineFunction::iterator TI = ToBB;
879  MachineFunction::iterator E = BB->getParent()->end();
880  while (I != TI) {
881    // Check isSuccessor to avoid case where the next block is empty, but
882    // it's not a successor.
883    if (I == E || !I->empty() || !PI->isSuccessor(I))
884      return false;
885    PI = I++;
886  }
887  return true;
888}
889
890/// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed
891/// to determine if it can be if-converted. If predecessor is already enqueued,
892/// dequeue it!
893void IfConverter::InvalidatePreds(MachineBasicBlock *BB) {
894  for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
895         E = BB->pred_end(); PI != E; ++PI) {
896    BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
897    if (PBBI.IsDone || PBBI.BB == BB)
898      continue;
899    PBBI.IsAnalyzed = false;
900    PBBI.IsEnqueued = false;
901  }
902}
903
904/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
905///
906static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
907                               const TargetInstrInfo *TII) {
908  DebugLoc dl;  // FIXME: this is nowhere
909  SmallVector<MachineOperand, 0> NoCond;
910  TII->InsertBranch(*BB, ToBB, NULL, NoCond, dl);
911}
912
913/// RemoveExtraEdges - Remove true / false edges if either / both are no longer
914/// successors.
915void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
916  MachineBasicBlock *TBB = NULL, *FBB = NULL;
917  SmallVector<MachineOperand, 4> Cond;
918  if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
919    BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
920}
921
922/// InitPredRedefs / UpdatePredRedefs - Defs by predicated instructions are
923/// modeled as read + write (sort like two-address instructions). These
924/// routines track register liveness and add implicit uses to if-converted
925/// instructions to conform to the model.
926static void InitPredRedefs(MachineBasicBlock *BB, SmallSet<unsigned,4> &Redefs,
927                           const TargetRegisterInfo *TRI) {
928  for (MachineBasicBlock::livein_iterator I = BB->livein_begin(),
929         E = BB->livein_end(); I != E; ++I) {
930    unsigned Reg = *I;
931    Redefs.insert(Reg);
932    for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
933         *Subreg; ++Subreg)
934      Redefs.insert(*Subreg);
935  }
936}
937
938static void UpdatePredRedefs(MachineInstr *MI, SmallSet<unsigned,4> &Redefs,
939                             const TargetRegisterInfo *TRI,
940                             bool AddImpUse = false) {
941  SmallVector<unsigned, 4> Defs;
942  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
943    const MachineOperand &MO = MI->getOperand(i);
944    if (!MO.isReg())
945      continue;
946    unsigned Reg = MO.getReg();
947    if (!Reg)
948      continue;
949    if (MO.isDef())
950      Defs.push_back(Reg);
951    else if (MO.isKill()) {
952      Redefs.erase(Reg);
953      for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR)
954        Redefs.erase(*SR);
955    }
956  }
957  for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
958    unsigned Reg = Defs[i];
959    if (Redefs.count(Reg)) {
960      if (AddImpUse)
961        // Treat predicated update as read + write.
962        MI->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
963                                                true/*IsImp*/,false/*IsKill*/));
964    } else {
965      Redefs.insert(Reg);
966      for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR)
967        Redefs.insert(*SR);
968    }
969  }
970}
971
972static void UpdatePredRedefs(MachineBasicBlock::iterator I,
973                             MachineBasicBlock::iterator E,
974                             SmallSet<unsigned,4> &Redefs,
975                             const TargetRegisterInfo *TRI) {
976  while (I != E) {
977    UpdatePredRedefs(I, Redefs, TRI);
978    ++I;
979  }
980}
981
982/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
983///
984bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
985  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
986  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
987  BBInfo *CvtBBI = &TrueBBI;
988  BBInfo *NextBBI = &FalseBBI;
989
990  SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
991  if (Kind == ICSimpleFalse)
992    std::swap(CvtBBI, NextBBI);
993
994  if (CvtBBI->IsDone ||
995      (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
996    // Something has changed. It's no longer safe to predicate this block.
997    BBI.IsAnalyzed = false;
998    CvtBBI->IsAnalyzed = false;
999    return false;
1000  }
1001
1002  if (Kind == ICSimpleFalse)
1003    if (TII->ReverseBranchCondition(Cond))
1004      assert(false && "Unable to reverse branch condition!");
1005
1006  // Initialize liveins to the first BB. These are potentiall redefined by
1007  // predicated instructions.
1008  SmallSet<unsigned, 4> Redefs;
1009  InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1010  InitPredRedefs(NextBBI->BB, Redefs, TRI);
1011
1012  if (CvtBBI->BB->pred_size() > 1) {
1013    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1014    // Copy instructions in the true block, predicate them, and add them to
1015    // the entry block.
1016    CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs);
1017  } else {
1018    PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1019
1020    // Merge converted block into entry block.
1021    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1022    MergeBlocks(BBI, *CvtBBI);
1023  }
1024
1025  bool IterIfcvt = true;
1026  if (!canFallThroughTo(BBI.BB, NextBBI->BB)) {
1027    InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1028    BBI.HasFallThrough = false;
1029    // Now ifcvt'd block will look like this:
1030    // BB:
1031    // ...
1032    // t, f = cmp
1033    // if t op
1034    // b BBf
1035    //
1036    // We cannot further ifcvt this block because the unconditional branch
1037    // will have to be predicated on the new condition, that will not be
1038    // available if cmp executes.
1039    IterIfcvt = false;
1040  }
1041
1042  RemoveExtraEdges(BBI);
1043
1044  // Update block info. BB can be iteratively if-converted.
1045  if (!IterIfcvt)
1046    BBI.IsDone = true;
1047  InvalidatePreds(BBI.BB);
1048  CvtBBI->IsDone = true;
1049
1050  // FIXME: Must maintain LiveIns.
1051  return true;
1052}
1053
1054/// IfConvertTriangle - If convert a triangle sub-CFG.
1055///
1056bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
1057  BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1058  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1059  BBInfo *CvtBBI = &TrueBBI;
1060  BBInfo *NextBBI = &FalseBBI;
1061  DebugLoc dl;  // FIXME: this is nowhere
1062
1063  SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1064  if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1065    std::swap(CvtBBI, NextBBI);
1066
1067  if (CvtBBI->IsDone ||
1068      (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
1069    // Something has changed. It's no longer safe to predicate this block.
1070    BBI.IsAnalyzed = false;
1071    CvtBBI->IsAnalyzed = false;
1072    return false;
1073  }
1074
1075  if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1076    if (TII->ReverseBranchCondition(Cond))
1077      assert(false && "Unable to reverse branch condition!");
1078
1079  if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
1080    if (ReverseBranchCondition(*CvtBBI)) {
1081      // BB has been changed, modify its predecessors (except for this
1082      // one) so they don't get ifcvt'ed based on bad intel.
1083      for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
1084             E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
1085        MachineBasicBlock *PBB = *PI;
1086        if (PBB == BBI.BB)
1087          continue;
1088        BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
1089        if (PBBI.IsEnqueued) {
1090          PBBI.IsAnalyzed = false;
1091          PBBI.IsEnqueued = false;
1092        }
1093      }
1094    }
1095  }
1096
1097  // Initialize liveins to the first BB. These are potentially redefined by
1098  // predicated instructions.
1099  SmallSet<unsigned, 4> Redefs;
1100  InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1101  InitPredRedefs(NextBBI->BB, Redefs, TRI);
1102
1103  bool HasEarlyExit = CvtBBI->FalseBB != NULL;
1104  if (CvtBBI->BB->pred_size() > 1) {
1105    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1106    // Copy instructions in the true block, predicate them, and add them to
1107    // the entry block.
1108    CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true);
1109  } else {
1110    // Predicate the 'true' block after removing its branch.
1111    CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
1112    PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1113
1114    // Now merge the entry of the triangle with the true block.
1115    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1116    MergeBlocks(BBI, *CvtBBI, false);
1117  }
1118
1119  // If 'true' block has a 'false' successor, add an exit branch to it.
1120  if (HasEarlyExit) {
1121    SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
1122                                           CvtBBI->BrCond.end());
1123    if (TII->ReverseBranchCondition(RevCond))
1124      assert(false && "Unable to reverse branch condition!");
1125    TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl);
1126    BBI.BB->addSuccessor(CvtBBI->FalseBB);
1127  }
1128
1129  // Merge in the 'false' block if the 'false' block has no other
1130  // predecessors. Otherwise, add an unconditional branch to 'false'.
1131  bool FalseBBDead = false;
1132  bool IterIfcvt = true;
1133  bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
1134  if (!isFallThrough) {
1135    // Only merge them if the true block does not fallthrough to the false
1136    // block. By not merging them, we make it possible to iteratively
1137    // ifcvt the blocks.
1138    if (!HasEarlyExit &&
1139        NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough) {
1140      MergeBlocks(BBI, *NextBBI);
1141      FalseBBDead = true;
1142    } else {
1143      InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1144      BBI.HasFallThrough = false;
1145    }
1146    // Mixed predicated and unpredicated code. This cannot be iteratively
1147    // predicated.
1148    IterIfcvt = false;
1149  }
1150
1151  RemoveExtraEdges(BBI);
1152
1153  // Update block info. BB can be iteratively if-converted.
1154  if (!IterIfcvt)
1155    BBI.IsDone = true;
1156  InvalidatePreds(BBI.BB);
1157  CvtBBI->IsDone = true;
1158  if (FalseBBDead)
1159    NextBBI->IsDone = true;
1160
1161  // FIXME: Must maintain LiveIns.
1162  return true;
1163}
1164
1165/// IfConvertDiamond - If convert a diamond sub-CFG.
1166///
1167bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
1168                                   unsigned NumDups1, unsigned NumDups2) {
1169  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1170  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1171  MachineBasicBlock *TailBB = TrueBBI.TrueBB;
1172  // True block must fall through or end with an unanalyzable terminator.
1173  if (!TailBB) {
1174    if (blockAlwaysFallThrough(TrueBBI))
1175      TailBB = FalseBBI.TrueBB;
1176    assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
1177  }
1178
1179  if (TrueBBI.IsDone || FalseBBI.IsDone ||
1180      TrueBBI.BB->pred_size() > 1 ||
1181      FalseBBI.BB->pred_size() > 1) {
1182    // Something has changed. It's no longer safe to predicate these blocks.
1183    BBI.IsAnalyzed = false;
1184    TrueBBI.IsAnalyzed = false;
1185    FalseBBI.IsAnalyzed = false;
1186    return false;
1187  }
1188
1189  // Put the predicated instructions from the 'true' block before the
1190  // instructions from the 'false' block, unless the true block would clobber
1191  // the predicate, in which case, do the opposite.
1192  BBInfo *BBI1 = &TrueBBI;
1193  BBInfo *BBI2 = &FalseBBI;
1194  SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1195  if (TII->ReverseBranchCondition(RevCond))
1196    assert(false && "Unable to reverse branch condition!");
1197  SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
1198  SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
1199
1200  // Figure out the more profitable ordering.
1201  bool DoSwap = false;
1202  if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
1203    DoSwap = true;
1204  else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
1205    if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1206      DoSwap = true;
1207  }
1208  if (DoSwap) {
1209    std::swap(BBI1, BBI2);
1210    std::swap(Cond1, Cond2);
1211  }
1212
1213  // Remove the conditional branch from entry to the blocks.
1214  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1215
1216  // Initialize liveins to the first BB. These are potentially redefined by
1217  // predicated instructions.
1218  SmallSet<unsigned, 4> Redefs;
1219  InitPredRedefs(BBI1->BB, Redefs, TRI);
1220
1221  // Remove the duplicated instructions at the beginnings of both paths.
1222  MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
1223  MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
1224  MachineBasicBlock::iterator DIE1 = BBI1->BB->end();
1225  MachineBasicBlock::iterator DIE2 = BBI2->BB->end();
1226  // Skip dbg_value instructions
1227  while (DI1 != DIE1 && DI1->isDebugValue())
1228    ++DI1;
1229  while (DI2 != DIE2 && DI2->isDebugValue())
1230    ++DI2;
1231  BBI1->NonPredSize -= NumDups1;
1232  BBI2->NonPredSize -= NumDups1;
1233
1234  // Skip past the dups on each side separately since there may be
1235  // differing dbg_value entries.
1236  for (unsigned i = 0; i < NumDups1; ++DI1) {
1237    if (!DI1->isDebugValue())
1238      ++i;
1239  }
1240  while (NumDups1 != 0) {
1241    ++DI2;
1242    if (!DI2->isDebugValue())
1243      --NumDups1;
1244  }
1245
1246  UpdatePredRedefs(BBI1->BB->begin(), DI1, Redefs, TRI);
1247  BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
1248  BBI2->BB->erase(BBI2->BB->begin(), DI2);
1249
1250  // Predicate the 'true' block after removing its branch.
1251  BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
1252  DI1 = BBI1->BB->end();
1253  for (unsigned i = 0; i != NumDups2; ) {
1254    // NumDups2 only counted non-dbg_value instructions, so this won't
1255    // run off the head of the list.
1256    assert (DI1 != BBI1->BB->begin());
1257    --DI1;
1258    // skip dbg_value instructions
1259    if (!DI1->isDebugValue())
1260      ++i;
1261  }
1262  BBI1->BB->erase(DI1, BBI1->BB->end());
1263  PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, Redefs);
1264
1265  // Predicate the 'false' block.
1266  BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
1267  DI2 = BBI2->BB->end();
1268  while (NumDups2 != 0) {
1269    // NumDups2 only counted non-dbg_value instructions, so this won't
1270    // run off the head of the list.
1271    assert (DI2 != BBI2->BB->begin());
1272    --DI2;
1273    // skip dbg_value instructions
1274    if (!DI2->isDebugValue())
1275      --NumDups2;
1276  }
1277  PredicateBlock(*BBI2, DI2, *Cond2, Redefs);
1278
1279  // Merge the true block into the entry of the diamond.
1280  MergeBlocks(BBI, *BBI1, TailBB == 0);
1281  MergeBlocks(BBI, *BBI2, TailBB == 0);
1282
1283  // If the if-converted block falls through or unconditionally branches into
1284  // the tail block, and the tail block does not have other predecessors, then
1285  // fold the tail block in as well. Otherwise, unless it falls through to the
1286  // tail, add a unconditional branch to it.
1287  if (TailBB) {
1288    BBInfo TailBBI = BBAnalysis[TailBB->getNumber()];
1289    bool CanMergeTail = !TailBBI.HasFallThrough;
1290    // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
1291    // check if there are any other predecessors besides those.
1292    unsigned NumPreds = TailBB->pred_size();
1293    if (NumPreds > 1)
1294      CanMergeTail = false;
1295    else if (NumPreds == 1 && CanMergeTail) {
1296      MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
1297      if (*PI != BBI1->BB && *PI != BBI2->BB)
1298        CanMergeTail = false;
1299    }
1300    if (CanMergeTail) {
1301      MergeBlocks(BBI, TailBBI);
1302      TailBBI.IsDone = true;
1303    } else {
1304      BBI.BB->addSuccessor(TailBB);
1305      InsertUncondBranch(BBI.BB, TailBB, TII);
1306      BBI.HasFallThrough = false;
1307    }
1308  }
1309
1310  // RemoveExtraEdges won't work if the block has an unanalyzable branch,
1311  // which can happen here if TailBB is unanalyzable and is merged, so
1312  // explicitly remove BBI1 and BBI2 as successors.
1313  BBI.BB->removeSuccessor(BBI1->BB);
1314  BBI.BB->removeSuccessor(BBI2->BB);
1315  RemoveExtraEdges(BBI);
1316
1317  // Update block info.
1318  BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
1319  InvalidatePreds(BBI.BB);
1320
1321  // FIXME: Must maintain LiveIns.
1322  return true;
1323}
1324
1325/// PredicateBlock - Predicate instructions from the start of the block to the
1326/// specified end with the specified condition.
1327void IfConverter::PredicateBlock(BBInfo &BBI,
1328                                 MachineBasicBlock::iterator E,
1329                                 SmallVectorImpl<MachineOperand> &Cond,
1330                                 SmallSet<unsigned, 4> &Redefs) {
1331  for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
1332    if (I->isDebugValue() || TII->isPredicated(I))
1333      continue;
1334    if (!TII->PredicateInstruction(I, Cond)) {
1335#ifndef NDEBUG
1336      dbgs() << "Unable to predicate " << *I << "!\n";
1337#endif
1338      llvm_unreachable(0);
1339    }
1340
1341    // If the predicated instruction now redefines a register as the result of
1342    // if-conversion, add an implicit kill.
1343    UpdatePredRedefs(I, Redefs, TRI, true);
1344  }
1345
1346  std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
1347
1348  BBI.IsAnalyzed = false;
1349  BBI.NonPredSize = 0;
1350
1351  ++NumIfConvBBs;
1352}
1353
1354/// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
1355/// the destination block. Skip end of block branches if IgnoreBr is true.
1356void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
1357                                        SmallVectorImpl<MachineOperand> &Cond,
1358                                        SmallSet<unsigned, 4> &Redefs,
1359                                        bool IgnoreBr) {
1360  MachineFunction &MF = *ToBBI.BB->getParent();
1361
1362  for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
1363         E = FromBBI.BB->end(); I != E; ++I) {
1364    const TargetInstrDesc &TID = I->getDesc();
1365    // Do not copy the end of the block branches.
1366    if (IgnoreBr && TID.isBranch())
1367      break;
1368
1369    MachineInstr *MI = MF.CloneMachineInstr(I);
1370    ToBBI.BB->insert(ToBBI.BB->end(), MI);
1371    unsigned NumOps = TII->getNumMicroOps(MI, InstrItins);
1372    ToBBI.NonPredSize += NumOps;
1373
1374    if (!TII->isPredicated(I) && !MI->isDebugValue()) {
1375      if (!TII->PredicateInstruction(MI, Cond)) {
1376#ifndef NDEBUG
1377        dbgs() << "Unable to predicate " << *I << "!\n";
1378#endif
1379        llvm_unreachable(0);
1380      }
1381    }
1382
1383    // If the predicated instruction now redefines a register as the result of
1384    // if-conversion, add an implicit kill.
1385    UpdatePredRedefs(MI, Redefs, TRI, true);
1386  }
1387
1388  if (!IgnoreBr) {
1389    std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1390                                           FromBBI.BB->succ_end());
1391    MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1392    MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1393
1394    for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1395      MachineBasicBlock *Succ = Succs[i];
1396      // Fallthrough edge can't be transferred.
1397      if (Succ == FallThrough)
1398        continue;
1399      ToBBI.BB->addSuccessor(Succ);
1400    }
1401  }
1402
1403  std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1404            std::back_inserter(ToBBI.Predicate));
1405  std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
1406
1407  ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1408  ToBBI.IsAnalyzed = false;
1409
1410  ++NumDupBBs;
1411}
1412
1413/// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
1414/// This will leave FromBB as an empty block, so remove all of its
1415/// successor edges except for the fall-through edge.  If AddEdges is true,
1416/// i.e., when FromBBI's branch is being moved, add those successor edges to
1417/// ToBBI.
1418void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
1419  ToBBI.BB->splice(ToBBI.BB->end(),
1420                   FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
1421
1422  std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1423                                         FromBBI.BB->succ_end());
1424  MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1425  MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1426
1427  for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1428    MachineBasicBlock *Succ = Succs[i];
1429    // Fallthrough edge can't be transferred.
1430    if (Succ == FallThrough)
1431      continue;
1432    FromBBI.BB->removeSuccessor(Succ);
1433    if (AddEdges)
1434      ToBBI.BB->addSuccessor(Succ);
1435  }
1436
1437  // Now FromBBI always falls through to the next block!
1438  if (NBB && !FromBBI.BB->isSuccessor(NBB))
1439    FromBBI.BB->addSuccessor(NBB);
1440
1441  std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1442            std::back_inserter(ToBBI.Predicate));
1443  FromBBI.Predicate.clear();
1444
1445  ToBBI.NonPredSize += FromBBI.NonPredSize;
1446  FromBBI.NonPredSize = 0;
1447
1448  ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1449  ToBBI.HasFallThrough = FromBBI.HasFallThrough;
1450  ToBBI.IsAnalyzed = false;
1451  FromBBI.IsAnalyzed = false;
1452}
1453