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