IfConversion.cpp revision edf4896a1461fe43081aab3ab7dda16f9dac8590 
1//===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the Evan Cheng and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the machine instruction level if-conversion pass.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "ifcvt"
15#include "llvm/Function.h"
16#include "llvm/CodeGen/Passes.h"
17#include "llvm/CodeGen/MachineModuleInfo.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/Target/TargetInstrInfo.h"
20#include "llvm/Target/TargetLowering.h"
21#include "llvm/Target/TargetMachine.h"
22#include "llvm/Support/CommandLine.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/ADT/DepthFirstIterator.h"
25#include "llvm/ADT/Statistic.h"
26using namespace llvm;
27
28namespace {
29  // Hidden options for help debugging.
30  cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
31  cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
32  cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
33  cl::opt<bool> DisableSimple("disable-ifcvt-simple",
34                              cl::init(false), cl::Hidden);
35  cl::opt<bool> DisableSimpleFalse("disable-ifcvt-simple-false",
36                                   cl::init(false), cl::Hidden);
37  cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
38                                cl::init(false), cl::Hidden);
39  cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
40                               cl::init(false), cl::Hidden);
41}
42
43STATISTIC(NumSimple,    "Number of simple if-conversions performed");
44STATISTIC(NumSimpleRev, "Number of simple (reversed) if-conversions performed");
45STATISTIC(NumTriangle,  "Number of triangle if-conversions performed");
46STATISTIC(NumDiamonds,  "Number of diamond if-conversions performed");
47STATISTIC(NumIfConvBBs, "Number of if-converted blocks");
48
49namespace {
50  class IfConverter : public MachineFunctionPass {
51    enum BBICKind {
52      ICNotAnalyzed,   // BB has not been analyzed.
53      ICReAnalyze,     // BB must be re-analyzed.
54      ICNotClassfied,  // BB data valid, but not classified.
55      ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
56      ICSimpleFalse,   // Same as ICSimple, but on the false path.
57      ICTriangle,      // BB is entry of a triangle sub-CFG.
58      ICDiamond,       // BB is entry of a diamond sub-CFG.
59      ICChild,         // BB is part of the sub-CFG that'll be predicated.
60      ICDead           // BB cannot be if-converted again.
61    };
62
63    /// BBInfo - One per MachineBasicBlock, this is used to cache the result
64    /// if-conversion feasibility analysis. This includes results from
65    /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
66    /// classification, and common tail block of its successors (if it's a
67    /// diamond shape), its size, whether it's predicable, and whether any
68    /// instruction can clobber the 'would-be' predicate.
69    ///
70    /// Kind            - Type of block. See BBICKind.
71    /// NonPredSize     - Number of non-predicated instructions.
72    /// IsAnalyzable    - True if AnalyzeBranch() returns false.
73    /// ModifyPredicate - True if BB would modify the predicate (e.g. has
74    ///                   cmp, call, etc.)
75    /// BB              - Corresponding MachineBasicBlock.
76    /// TrueBB / FalseBB- See AnalyzeBranch().
77    /// BrCond          - Conditions for end of block conditional branches.
78    /// Predicate       - Predicate used in the BB.
79    struct BBInfo {
80      BBICKind Kind;
81      unsigned NonPredSize;
82      bool IsAnalyzable;
83      bool hasFallThrough;
84      bool ModifyPredicate;
85      MachineBasicBlock *BB;
86      MachineBasicBlock *TrueBB;
87      MachineBasicBlock *FalseBB;
88      MachineBasicBlock *TailBB;
89      std::vector<MachineOperand> BrCond;
90      std::vector<MachineOperand> Predicate;
91      BBInfo() : Kind(ICNotAnalyzed), NonPredSize(0),
92                 IsAnalyzable(false), hasFallThrough(false),
93                 ModifyPredicate(false),
94                 BB(0), TrueBB(0), FalseBB(0), TailBB(0) {}
95    };
96
97    /// Roots - Basic blocks that do not have successors. These are the starting
98    /// points of Graph traversal.
99    std::vector<MachineBasicBlock*> Roots;
100
101    /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
102    /// basic block number.
103    std::vector<BBInfo> BBAnalysis;
104
105    const TargetLowering *TLI;
106    const TargetInstrInfo *TII;
107    bool MadeChange;
108  public:
109    static char ID;
110    IfConverter() : MachineFunctionPass((intptr_t)&ID) {}
111
112    virtual bool runOnMachineFunction(MachineFunction &MF);
113    virtual const char *getPassName() const { return "If converter"; }
114
115  private:
116    bool ReverseBranchCondition(BBInfo &BBI);
117    bool ValidSimple(BBInfo &TrueBBI) const;
118    bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
119                       bool FalseBranch = false) const;
120    bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI) const;
121    void ScanInstructions(BBInfo &BBI);
122    void AnalyzeBlock(MachineBasicBlock *BB);
123    bool FeasibilityAnalysis(BBInfo &BBI, std::vector<MachineOperand> &Cond,
124                             bool isTriangle = false, bool RevBranch = false);
125    bool AttemptRestructuring(BBInfo &BBI);
126    bool AnalyzeBlocks(MachineFunction &MF,
127                       std::vector<BBInfo*> &Candidates);
128    void ReTryPreds(MachineBasicBlock *BB);
129    bool IfConvertSimple(BBInfo &BBI);
130    bool IfConvertTriangle(BBInfo &BBI);
131    bool IfConvertDiamond(BBInfo &BBI);
132    void PredicateBlock(BBInfo &BBI,
133                        std::vector<MachineOperand> &Cond,
134                        bool IgnoreTerm = false);
135    void MergeBlocks(BBInfo &TrueBBI, BBInfo &FalseBBI);
136
137    // blockAlwaysFallThrough - Block ends without a terminator.
138    bool blockAlwaysFallThrough(BBInfo &BBI) const {
139      return BBI.IsAnalyzable && BBI.TrueBB == NULL;
140    }
141
142    // IfcvtCandidateCmp - Used to sort if-conversion candidates.
143    static bool IfcvtCandidateCmp(BBInfo* C1, BBInfo* C2){
144      // Favor diamond over triangle, etc.
145      return (unsigned)C1->Kind < (unsigned)C2->Kind;
146    }
147  };
148  char IfConverter::ID = 0;
149}
150
151FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
152
153bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
154  TLI = MF.getTarget().getTargetLowering();
155  TII = MF.getTarget().getInstrInfo();
156  if (!TII) return false;
157
158  static int FnNum = -1;
159  DOUT << "\nIfcvt: function (" << ++FnNum <<  ") \'"
160       << MF.getFunction()->getName() << "\'";
161
162  if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
163    DOUT << " skipped\n";
164    return false;
165  }
166  DOUT << "\n";
167
168  MF.RenumberBlocks();
169  BBAnalysis.resize(MF.getNumBlockIDs());
170
171  // Look for root nodes, i.e. blocks without successors.
172  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
173    if (I->succ_size() == 0)
174      Roots.push_back(I);
175
176  std::vector<BBInfo*> Candidates;
177  MadeChange = false;
178  while (IfCvtLimit == -1 || (int)NumIfConvBBs < IfCvtLimit) {
179    // Do an intial analysis for each basic block and finding all the potential
180    // candidates to perform if-convesion.
181    bool Change = AnalyzeBlocks(MF, Candidates);
182    while (!Candidates.empty()) {
183      BBInfo &BBI = *Candidates.back();
184      Candidates.pop_back();
185
186      bool RetVal = false;
187      switch (BBI.Kind) {
188      default: assert(false && "Unexpected!");
189        break;
190      case ICReAnalyze:
191        // One or more of 'children' have been modified, abort!
192      case ICDead:
193        // Block has been already been if-converted, abort!
194        break;
195      case ICSimple:
196      case ICSimpleFalse: {
197        bool isRev = BBI.Kind == ICSimpleFalse;
198        if ((isRev && DisableSimpleFalse) || (!isRev && DisableSimple)) break;
199        DOUT << "Ifcvt (Simple" << (BBI.Kind == ICSimpleFalse ? " false" : "")
200             << "): BB#" << BBI.BB->getNumber() << " ("
201             << ((BBI.Kind == ICSimpleFalse)
202                 ? BBI.FalseBB->getNumber() : BBI.TrueBB->getNumber()) << ") ";
203        RetVal = IfConvertSimple(BBI);
204        DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
205        if (RetVal)
206          if (isRev) NumSimpleRev++;
207          else       NumSimple++;
208       break;
209      }
210      case ICTriangle:
211        if (DisableTriangle) break;
212        DOUT << "Ifcvt (Triangle): BB#" << BBI.BB->getNumber() << " (T:"
213             << BBI.TrueBB->getNumber() << ",F:" << BBI.FalseBB->getNumber()
214             << ") ";
215        RetVal = IfConvertTriangle(BBI);
216        DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
217        if (RetVal) NumTriangle++;
218        break;
219      case ICDiamond:
220        if (DisableDiamond) break;
221        DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
222             << BBI.TrueBB->getNumber() << ",F:" << BBI.FalseBB->getNumber();
223        if (BBI.TailBB)
224          DOUT << "," << BBI.TailBB->getNumber() ;
225        DOUT << ") ";
226        RetVal = IfConvertDiamond(BBI);
227        DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
228        if (RetVal) NumDiamonds++;
229        break;
230      }
231      Change |= RetVal;
232
233      if (IfCvtLimit != -1 && (int)NumIfConvBBs > IfCvtLimit)
234        break;
235    }
236
237    if (!Change)
238      break;
239    MadeChange |= Change;
240  }
241
242  Roots.clear();
243  BBAnalysis.clear();
244
245  return MadeChange;
246}
247
248static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
249                                         MachineBasicBlock *TrueBB) {
250  for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
251         E = BB->succ_end(); SI != E; ++SI) {
252    MachineBasicBlock *SuccBB = *SI;
253    if (SuccBB != TrueBB)
254      return SuccBB;
255  }
256  return NULL;
257}
258
259bool IfConverter::ReverseBranchCondition(BBInfo &BBI) {
260  if (!TII->ReverseBranchCondition(BBI.BrCond)) {
261    TII->RemoveBranch(*BBI.BB);
262    TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond);
263    std::swap(BBI.TrueBB, BBI.FalseBB);
264    return true;
265  }
266  return false;
267}
268
269/// ValidSimple - Returns true if the 'true' block (along with its
270/// predecessor) forms a valid simple shape for ifcvt.
271bool IfConverter::ValidSimple(BBInfo &TrueBBI) const {
272  return !blockAlwaysFallThrough(TrueBBI) &&
273    TrueBBI.BrCond.size() == 0 && TrueBBI.BB->pred_size() == 1;
274}
275
276/// ValidTriangle - Returns true if the 'true' and 'false' blocks (along
277/// with their common predecessor) forms a valid triangle shape for ifcvt.
278bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
279                                bool FalseBranch) const {
280  if (TrueBBI.BB->pred_size() != 1)
281    return false;
282
283  MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
284  if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
285    MachineFunction::iterator I = TrueBBI.BB;
286    if (++I == TrueBBI.BB->getParent()->end())
287      return false;
288    TExit = I;
289  }
290  return TExit && TExit == FalseBBI.BB;
291}
292
293/// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
294/// with their common predecessor) forms a valid diamond shape for ifcvt.
295bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI) const {
296  // FIXME: Also look for fallthrough
297  return (TrueBBI.TrueBB == FalseBBI.TrueBB &&
298          TrueBBI.BB->pred_size() == 1 &&
299          FalseBBI.BB->pred_size() == 1 &&
300          !TrueBBI.FalseBB && !FalseBBI.FalseBB);
301}
302
303/// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
304/// the specified block. Record its successors and whether it looks like an
305/// if-conversion candidate.
306void IfConverter::AnalyzeBlock(MachineBasicBlock *BB) {
307  BBInfo &BBI = BBAnalysis[BB->getNumber()];
308
309  if (BBI.Kind == ICReAnalyze) {
310    BBI.BrCond.clear();
311    BBI.TrueBB = BBI.FalseBB = NULL;
312  } else {
313    if (BBI.Kind != ICNotAnalyzed)
314      return;  // Already analyzed.
315    BBI.BB = BB;
316    BBI.NonPredSize = std::distance(BB->begin(), BB->end());
317  }
318
319  // Look for 'root' of a simple (non-nested) triangle or diamond.
320  BBI.Kind = ICNotClassfied;
321  BBI.IsAnalyzable =
322    !TII->AnalyzeBranch(*BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
323  BBI.hasFallThrough = BBI.IsAnalyzable && BBI.FalseBB == NULL;
324  // Unanalyable or ends with fallthrough or unconditional branch.
325  if (!BBI.IsAnalyzable || BBI.BrCond.size() == 0)
326    return;
327  // Do not ifcvt if either path is a back edge to the entry block.
328  if (BBI.TrueBB == BB || BBI.FalseBB == BB)
329    return;
330
331  AnalyzeBlock(BBI.TrueBB);
332  BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
333
334  // No false branch. This BB must end with a conditional branch and a
335  // fallthrough.
336  if (!BBI.FalseBB)
337    BBI.FalseBB = findFalseBlock(BB, BBI.TrueBB);
338  assert(BBI.FalseBB && "Expected to find the fallthrough block!");
339
340  AnalyzeBlock(BBI.FalseBB);
341  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
342
343  // If both paths are dead, then forget about it.
344  if (TrueBBI.Kind == ICDead && FalseBBI.Kind == ICDead) {
345    BBI.Kind = ICDead;
346    return;
347  }
348
349  // Look for more opportunities to if-convert a triangle. Try to restructure
350  // the CFG to form a triangle with the 'false' path.
351  std::vector<MachineOperand> RevCond(BBI.BrCond);
352  bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
353
354  if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI) &&
355      !(TrueBBI.ModifyPredicate && FalseBBI.ModifyPredicate) &&
356      FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
357      FeasibilityAnalysis(FalseBBI, RevCond)) {
358    // Diamond:
359    //   EBB
360    //   / \_
361    //  |   |
362    // TBB FBB
363    //   \ /
364    //  TailBB
365    // Note TailBB can be empty.
366    BBI.Kind = ICDiamond;
367    TrueBBI.Kind = FalseBBI.Kind = ICChild;
368    BBI.TailBB = TrueBBI.TrueBB;
369  } else {
370    // FIXME: Consider duplicating if BB is small.
371    if (ValidTriangle(TrueBBI, FalseBBI) &&
372        FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
373      // Triangle:
374      //   EBB
375      //   | \_
376      //   |  |
377      //   | TBB
378      //   |  /
379      //   FBB
380      BBI.Kind = ICTriangle;
381      TrueBBI.Kind = ICChild;
382    } else if (ValidSimple(TrueBBI) &&
383               FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
384      // Simple (split, no rejoin):
385      //   EBB
386      //   | \_
387      //   |  |
388      //   | TBB---> exit
389      //   |
390      //   FBB
391      BBI.Kind = ICSimple;
392      TrueBBI.Kind = ICChild;
393    } else if (CanRevCond) {
394      // Try the other path...
395      if (ValidTriangle(FalseBBI, TrueBBI) &&
396          FeasibilityAnalysis(FalseBBI, RevCond, true)) {
397        // Reverse 'true' and 'false' paths.
398        ReverseBranchCondition(BBI);
399        BBI.Kind = ICTriangle;
400        FalseBBI.Kind = ICChild;
401      } else if (ValidTriangle(FalseBBI, TrueBBI, true) &&
402                 FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
403        ReverseBranchCondition(FalseBBI);
404        ReverseBranchCondition(BBI);
405        BBI.Kind = ICTriangle;
406        FalseBBI.Kind = ICChild;
407      } else if (ValidSimple(FalseBBI) &&
408                 FeasibilityAnalysis(FalseBBI, RevCond)) {
409        BBI.Kind = ICSimpleFalse;
410        FalseBBI.Kind = ICChild;
411      }
412    }
413  }
414  return;
415}
416
417/// FeasibilityAnalysis - Determine if the block is predicable. In most
418/// cases, that means all the instructions in the block has M_PREDICABLE flag.
419/// Also checks if the block contains any instruction which can clobber a
420/// predicate (e.g. condition code register). If so, the block is not
421/// predicable unless it's the last instruction.
422bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
423                                      std::vector<MachineOperand> &Pred,
424                                      bool isTriangle, bool RevBranch) {
425  // If the block is dead, or it is going to be the entry block of a sub-CFG
426  // that will be if-converted, then it cannot be predicated.
427  if (BBI.Kind != ICNotAnalyzed &&
428      BBI.Kind != ICNotClassfied &&
429      BBI.Kind != ICChild)
430    return false;
431
432  // Check predication threshold.
433  if (BBI.NonPredSize == 0 || BBI.NonPredSize > TLI->getIfCvtBlockSizeLimit())
434    return false;
435
436  // If it is already predicated, check if its predicate subsumes the new
437  // predicate.
438  if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred))
439    return false;
440
441  bool SeenPredMod = false;
442  bool SeenCondBr = false;
443  for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
444       I != E; ++I) {
445    const TargetInstrDescriptor *TID = I->getInstrDescriptor();
446    if (SeenPredMod) {
447      // Predicate modification instruction should end the block (except for
448      // already predicated instructions and end of block branches).
449      if (!TII->isPredicated(I)) {
450        // This is the 'true' block of a triangle, i.e. its 'true' block is
451        // the same as the 'false' block of the entry. So false positive
452        // is ok.
453        if (isTriangle && !SeenCondBr && BBI.IsAnalyzable &&
454            (TID->Flags & M_BRANCH_FLAG) != 0 &&
455            (TID->Flags & M_BARRIER_FLAG) == 0) {
456          // This is the first conditional branch, test predicate subsumsion.
457          std::vector<MachineOperand> RevPred(Pred);
458          std::vector<MachineOperand> Cond(BBI.BrCond);
459          if (RevBranch) {
460            if (TII->ReverseBranchCondition(Cond))
461              return false;
462          }
463          if (TII->ReverseBranchCondition(RevPred) ||
464              !TII->SubsumesPredicate(Cond, RevPred))
465            return false;
466          SeenCondBr = true;
467          continue;  // Conditional branches is not predicable.
468        }
469        return false;
470      }
471    }
472
473    if (TID->Flags & M_CLOBBERS_PRED) {
474      BBI.ModifyPredicate = true;
475      SeenPredMod = true;
476    }
477
478    if (!I->isPredicable())
479      return false;
480  }
481
482  return true;
483}
484
485/// AttemptRestructuring - Restructure the sub-CFG rooted in the given block to
486/// expose more if-conversion opportunities. e.g.
487///
488///                cmp
489///                b le BB1
490///                /  \____
491///               /        |
492///             cmp        |
493///             b eq BB1   |
494///              /  \____  |
495///             /        \ |
496///                      BB1
497///  ==>
498///
499///                cmp
500///                b eq BB1
501///                /  \____
502///               /        |
503///             cmp        |
504///             b le BB1   |
505///              /  \____  |
506///             /        \ |
507///                      BB1
508bool IfConverter::AttemptRestructuring(BBInfo &BBI) {
509  return false;
510}
511
512/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
513/// candidates. It returns true if any CFG restructuring is done to expose more
514/// if-conversion opportunities.
515bool IfConverter::AnalyzeBlocks(MachineFunction &MF,
516                                std::vector<BBInfo*> &Candidates) {
517  bool Change = false;
518  std::set<MachineBasicBlock*> Visited;
519  for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
520    for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited),
521           E = idf_ext_end(Roots[i], Visited); I != E; ++I) {
522      MachineBasicBlock *BB = *I;
523      AnalyzeBlock(BB);
524      BBInfo &BBI = BBAnalysis[BB->getNumber()];
525      switch (BBI.Kind) {
526        case ICSimple:
527        case ICSimpleFalse:
528        case ICTriangle:
529        case ICDiamond:
530          Candidates.push_back(&BBI);
531          break;
532        default:
533          Change |= AttemptRestructuring(BBI);
534          break;
535      }
536    }
537  }
538
539  // Sort to favor more complex ifcvt scheme.
540  std::stable_sort(Candidates.begin(), Candidates.end(), IfcvtCandidateCmp);
541
542  return Change;
543}
544
545/// isNextBlock - Returns true either if ToBB the next block after BB or
546/// that all the intervening blocks are empty.
547static bool isNextBlock(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
548  MachineFunction::iterator I = BB;
549  MachineFunction::iterator TI = ToBB;
550  MachineFunction::iterator E = BB->getParent()->end();
551  while (++I != TI)
552    if (I == E || !I->empty())
553      return false;
554  return true;
555}
556
557/// ReTryPreds - Invalidate predecessor BB info so it would be re-analyzed
558/// to determine if it can be if-converted.
559void IfConverter::ReTryPreds(MachineBasicBlock *BB) {
560  for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
561         E = BB->pred_end(); PI != E; ++PI) {
562    BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
563    PBBI.Kind = ICReAnalyze;
564  }
565}
566
567/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
568///
569static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
570                               const TargetInstrInfo *TII) {
571  std::vector<MachineOperand> NoCond;
572  TII->InsertBranch(*BB, ToBB, NULL, NoCond);
573}
574
575/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
576///
577bool IfConverter::IfConvertSimple(BBInfo &BBI) {
578  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
579  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
580  BBInfo *CvtBBI = &TrueBBI;
581  BBInfo *NextBBI = &FalseBBI;
582
583  std::vector<MachineOperand> Cond(BBI.BrCond);
584  if (BBI.Kind == ICSimpleFalse) {
585    std::swap(CvtBBI, NextBBI);
586    TII->ReverseBranchCondition(Cond);
587  }
588
589  PredicateBlock(*CvtBBI, Cond);
590
591  // Merge converted block into entry block. Also add an unconditional branch
592  // to the 'false' branch.
593  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
594  MergeBlocks(BBI, *CvtBBI);
595  BBI.BB->removeSuccessor(CvtBBI->BB);
596
597  bool IterIfcvt = true;
598  if (!isNextBlock(BBI.BB, NextBBI->BB)) {
599    InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
600    BBI.hasFallThrough = false;
601    // Now ifcvt'd block will look like this:
602    // BB:
603    // ...
604    // t, f = cmp
605    // if t op
606    // b BBf
607    //
608    // We cannot further ifcvt this block because the unconditional branch
609    // will have to be predicated on the new condition, that will not be
610    // available if cmp executes.
611    IterIfcvt = false;
612  }
613  std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
614
615  // Update block info. BB can be iteratively if-converted.
616  if (IterIfcvt)
617    BBI.Kind = ICReAnalyze;
618  else
619    BBI.Kind = ICDead;
620  ReTryPreds(BBI.BB);
621  CvtBBI->Kind = ICDead;
622
623  // FIXME: Must maintain LiveIns.
624  return true;
625}
626
627/// IfConvertTriangle - If convert a triangle sub-CFG.
628///
629bool IfConverter::IfConvertTriangle(BBInfo &BBI) {
630  BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
631
632  // Predicate the 'true' block after removing its branch.
633  TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB);
634  PredicateBlock(TrueBBI, BBI.BrCond);
635
636  // If 'true' block has a 'false' successor, add an exit branch to it.
637  bool HasEarlyExit = TrueBBI.FalseBB != NULL;
638  if (HasEarlyExit) {
639    std::vector<MachineOperand> RevCond(TrueBBI.BrCond);
640    if (TII->ReverseBranchCondition(RevCond))
641      assert(false && "Unable to reverse branch condition!");
642    TII->InsertBranch(*BBI.TrueBB, TrueBBI.FalseBB, NULL, RevCond);
643  }
644
645  // Now merge the entry of the triangle with the true block.
646  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
647  MergeBlocks(BBI, TrueBBI);
648
649  // Merge in the 'false' block if the 'false' block has no other
650  // predecessors. Otherwise, add a unconditional branch from to 'false'.
651  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
652  bool FalseBBDead = false;
653  bool IterIfcvt = true;
654  bool isFallThrough = isNextBlock(BBI.BB, FalseBBI.BB);
655  if (!isFallThrough) {
656    // Only merge them if the true block does not fallthrough to the false
657    // block. By not merging them, we make it possible to iteratively
658    // ifcvt the blocks.
659    if (!HasEarlyExit && FalseBBI.BB->pred_size() == 1) {
660      MergeBlocks(BBI, FalseBBI);
661      FalseBBDead = true;
662    } else {
663      InsertUncondBranch(BBI.BB, FalseBBI.BB, TII);
664      TrueBBI.hasFallThrough = false;
665    }
666    // Mixed predicated and unpredicated code. This cannot be iteratively
667    // predicated.
668    IterIfcvt = false;
669  }
670
671  // Remove entry to false edge if false block is merged in as well.
672  if (FalseBBDead)
673    BBI.BB->removeSuccessor(FalseBBI.BB);
674  std::copy(BBI.BrCond.begin(), BBI.BrCond.end(),
675            std::back_inserter(BBI.Predicate));
676
677  // Update block info. BB can be iteratively if-converted.
678  if (IterIfcvt)
679    BBI.Kind = ICReAnalyze;
680  else
681    BBI.Kind = ICDead;
682  ReTryPreds(BBI.BB);
683  TrueBBI.Kind = ICDead;
684  if (FalseBBDead)
685    FalseBBI.Kind = ICDead;
686
687  // FIXME: Must maintain LiveIns.
688  return true;
689}
690
691/// IfConvertDiamond - If convert a diamond sub-CFG.
692///
693bool IfConverter::IfConvertDiamond(BBInfo &BBI) {
694  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
695  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
696
697  SmallVector<MachineInstr*, 2> Dups;
698  if (!BBI.TailBB) {
699    // No common merge block. Check if the terminators (e.g. return) are
700    // the same or predicable.
701    MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator();
702    MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator();
703    while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) {
704      if (TT->isIdenticalTo(FT))
705        Dups.push_back(TT);  // Will erase these later.
706      else if (!TT->isPredicable() && !FT->isPredicable())
707        return false; // Can't if-convert. Abort!
708      ++TT;
709      ++FT;
710    }
711
712    // One of the two pathes have more terminators, make sure they are
713    // all predicable.
714    while (TT != BBI.TrueBB->end()) {
715      if (!TT->isPredicable()) {
716        return false; // Can't if-convert. Abort!
717      }
718      ++TT;
719    }
720    while (FT != BBI.FalseBB->end()) {
721      if (!FT->isPredicable()) {
722        return false; // Can't if-convert. Abort!
723      }
724      ++FT;
725    }
726  }
727
728  // Remove the duplicated instructions from the 'true' block.
729  for (unsigned i = 0, e = Dups.size(); i != e; ++i) {
730    Dups[i]->eraseFromParent();
731    --TrueBBI.NonPredSize;
732  }
733
734  // Merge the 'true' and 'false' blocks by copying the instructions
735  // from the 'false' block to the 'true' block. That is, unless the true
736  // block would clobber the predicate, in that case, do the opposite.
737  BBInfo *BBI1 = &TrueBBI;
738  BBInfo *BBI2 = &FalseBBI;
739  std::vector<MachineOperand> RevCond(BBI.BrCond);
740  TII->ReverseBranchCondition(RevCond);
741  std::vector<MachineOperand> *Cond1 = &BBI.BrCond;
742  std::vector<MachineOperand> *Cond2 = &RevCond;
743  // Check the 'true' and 'false' blocks if either isn't ended with a branch.
744  // Either the block fallthrough to another block or it ends with a
745  // return. If it's the former, add a branch to its successor.
746  bool NeedBr1 = !BBI1->TrueBB && BBI1->BB->succ_size();
747  bool NeedBr2 = !BBI2->TrueBB && BBI2->BB->succ_size();
748
749  if ((TrueBBI.ModifyPredicate && !FalseBBI.ModifyPredicate) ||
750      (!TrueBBI.ModifyPredicate && !FalseBBI.ModifyPredicate &&
751       NeedBr1 && !NeedBr2)) {
752    std::swap(BBI1, BBI2);
753    std::swap(Cond1, Cond2);
754    std::swap(NeedBr1, NeedBr2);
755  }
756
757  // Predicate the 'true' block after removing its branch.
758  BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
759  PredicateBlock(*BBI1, *Cond1);
760
761  // Add an early exit branch if needed.
762  if (NeedBr1)
763    TII->InsertBranch(*BBI1->BB, *BBI1->BB->succ_begin(), NULL, *Cond1);
764
765  // Predicate the 'false' block.
766  PredicateBlock(*BBI2, *Cond2, true);
767
768  // Add an unconditional branch from 'false' to to 'false' successor if it
769  // will not be the fallthrough block.
770  if (NeedBr2 && !NeedBr1) {
771    // If BBI2 isn't going to be merged in, then the existing fallthrough
772    // or branch is fine.
773    if (!isNextBlock(BBI.BB, *BBI2->BB->succ_begin())) {
774      InsertUncondBranch(BBI2->BB, *BBI2->BB->succ_begin(), TII);
775      BBI2->hasFallThrough = false;
776    }
777  }
778
779  // Keep them as two separate blocks if there is an early exit.
780  if (!NeedBr1)
781    MergeBlocks(*BBI1, *BBI2);
782
783  // Remove the conditional branch from entry to the blocks.
784  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
785
786  // Merge the combined block into the entry of the diamond.
787  MergeBlocks(BBI, *BBI1);
788  std::copy(Cond1->begin(), Cond1->end(),
789            std::back_inserter(BBI.Predicate));
790  if (!NeedBr1)
791    std::copy(Cond2->begin(), Cond2->end(),
792              std::back_inserter(BBI.Predicate));
793
794  // 'True' and 'false' aren't combined, see if we need to add a unconditional
795  // branch to the 'false' block.
796  if (NeedBr1 && !isNextBlock(BBI.BB, BBI2->BB)) {
797    InsertUncondBranch(BBI.BB, BBI2->BB, TII);
798    BBI1->hasFallThrough = false;
799  }
800
801  // If the if-converted block fallthrough or unconditionally branch into the
802  // tail block, and the tail block does not have other predecessors, then
803  // fold the tail block in as well.
804  BBInfo *CvtBBI = NeedBr1 ? BBI2 : &BBI;
805  if (BBI.TailBB &&
806      BBI.TailBB->pred_size() == 1 && CvtBBI->BB->succ_size() == 1) {
807    CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
808    BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()];
809    MergeBlocks(*CvtBBI, TailBBI);
810    TailBBI.Kind = ICDead;
811  }
812
813  // Update block info.
814  BBI.Kind = ICDead;
815  TrueBBI.Kind = ICDead;
816  FalseBBI.Kind = ICDead;
817
818  // FIXME: Must maintain LiveIns.
819  return true;
820}
821
822/// PredicateBlock - Predicate every instruction in the block with the specified
823/// condition. If IgnoreTerm is true, skip over all terminator instructions.
824void IfConverter::PredicateBlock(BBInfo &BBI,
825                                 std::vector<MachineOperand> &Cond,
826                                 bool IgnoreTerm) {
827  for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
828       I != E; ++I) {
829    if (IgnoreTerm && TII->isTerminatorInstr(I->getOpcode()))
830      continue;
831    if (TII->isPredicated(I))
832      continue;
833    if (!TII->PredicateInstruction(I, Cond)) {
834      cerr << "Unable to predicate " << *I << "!\n";
835      abort();
836    }
837  }
838
839  BBI.NonPredSize = 0;
840  NumIfConvBBs++;
841}
842
843static MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) {
844  MachineFunction::iterator I = BB;
845  MachineFunction::iterator E = BB->getParent()->end();
846  if (++I == E)
847    return NULL;
848  return I;
849}
850
851/// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
852///
853void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
854  ToBBI.BB->splice(ToBBI.BB->end(),
855                   FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
856
857  // Redirect all branches to FromBB to ToBB.
858  std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(),
859                                         FromBBI.BB->pred_end());
860  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
861    MachineBasicBlock *Pred = Preds[i];
862    if (Pred == ToBBI.BB)
863      continue;
864    Pred->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB);
865  }
866
867  std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
868                                         FromBBI.BB->succ_end());
869  MachineBasicBlock *FallThrough = FromBBI.hasFallThrough
870    ? getNextBlock(FromBBI.BB) : NULL;
871
872  for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
873    MachineBasicBlock *Succ = Succs[i];
874    if (Succ == FallThrough)
875      continue;
876    FromBBI.BB->removeSuccessor(Succ);
877    if (!ToBBI.BB->isSuccessor(Succ))
878      ToBBI.BB->addSuccessor(Succ);
879  }
880
881  ToBBI.NonPredSize += FromBBI.NonPredSize;
882  FromBBI.NonPredSize = 0;
883
884  ToBBI.ModifyPredicate |= FromBBI.ModifyPredicate;
885  ToBBI.hasFallThrough = FromBBI.hasFallThrough;
886}
887