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