LLVM API Documentation

IfConversion.cpp

Go to the documentation of this file.
00001 //===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the machine instruction level if-conversion pass.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "ifcvt"
00015 #include "llvm/Function.h"
00016 #include "llvm/CodeGen/Passes.h"
00017 #include "llvm/CodeGen/MachineModuleInfo.h"
00018 #include "llvm/CodeGen/MachineFunctionPass.h"
00019 #include "llvm/Target/TargetInstrInfo.h"
00020 #include "llvm/Target/TargetLowering.h"
00021 #include "llvm/Target/TargetMachine.h"
00022 #include "llvm/Support/CommandLine.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/Support/ErrorHandling.h"
00025 #include "llvm/Support/raw_ostream.h"
00026 #include "llvm/ADT/DepthFirstIterator.h"
00027 #include "llvm/ADT/Statistic.h"
00028 #include "llvm/ADT/STLExtras.h"
00029 using namespace llvm;
00030 
00031 // Hidden options for help debugging.
00032 static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
00033 static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
00034 static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
00035 static cl::opt<bool> DisableSimple("disable-ifcvt-simple", 
00036                                    cl::init(false), cl::Hidden);
00037 static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", 
00038                                     cl::init(false), cl::Hidden);
00039 static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", 
00040                                      cl::init(false), cl::Hidden);
00041 static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev", 
00042                                       cl::init(false), cl::Hidden);
00043 static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", 
00044                                       cl::init(false), cl::Hidden);
00045 static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", 
00046                                        cl::init(false), cl::Hidden);
00047 static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", 
00048                                     cl::init(false), cl::Hidden);
00049 
00050 STATISTIC(NumSimple,       "Number of simple if-conversions performed");
00051 STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
00052 STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
00053 STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
00054 STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
00055 STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
00056 STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
00057 STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
00058 STATISTIC(NumDupBBs,       "Number of duplicated blocks");
00059 
00060 namespace {
00061   class VISIBILITY_HIDDEN IfConverter : public MachineFunctionPass {
00062     enum IfcvtKind {
00063       ICNotClassfied,  // BB data valid, but not classified.
00064       ICSimpleFalse,   // Same as ICSimple, but on the false path.
00065       ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
00066       ICTriangleFRev,  // Same as ICTriangleFalse, but false path rev condition.
00067       ICTriangleRev,   // Same as ICTriangle, but true path rev condition.
00068       ICTriangleFalse, // Same as ICTriangle, but on the false path.
00069       ICTriangle,      // BB is entry of a triangle sub-CFG.
00070       ICDiamond        // BB is entry of a diamond sub-CFG.
00071     };
00072 
00073     /// BBInfo - One per MachineBasicBlock, this is used to cache the result
00074     /// if-conversion feasibility analysis. This includes results from
00075     /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
00076     /// classification, and common tail block of its successors (if it's a
00077     /// diamond shape), its size, whether it's predicable, and whether any
00078     /// instruction can clobber the 'would-be' predicate.
00079     ///
00080     /// IsDone          - True if BB is not to be considered for ifcvt.
00081     /// IsBeingAnalyzed - True if BB is currently being analyzed.
00082     /// IsAnalyzed      - True if BB has been analyzed (info is still valid).
00083     /// IsEnqueued      - True if BB has been enqueued to be ifcvt'ed.
00084     /// IsBrAnalyzable  - True if AnalyzeBranch() returns false.
00085     /// HasFallThrough  - True if BB may fallthrough to the following BB.
00086     /// IsUnpredicable  - True if BB is known to be unpredicable.
00087     /// ClobbersPred    - True if BB could modify predicates (e.g. has
00088     ///                   cmp, call, etc.)
00089     /// NonPredSize     - Number of non-predicated instructions.
00090     /// BB              - Corresponding MachineBasicBlock.
00091     /// TrueBB / FalseBB- See AnalyzeBranch().
00092     /// BrCond          - Conditions for end of block conditional branches.
00093     /// Predicate       - Predicate used in the BB.
00094     struct BBInfo {
00095       bool IsDone          : 1;
00096       bool IsBeingAnalyzed : 1;
00097       bool IsAnalyzed      : 1;
00098       bool IsEnqueued      : 1;
00099       bool IsBrAnalyzable  : 1;
00100       bool HasFallThrough  : 1;
00101       bool IsUnpredicable  : 1;
00102       bool CannotBeCopied  : 1;
00103       bool ClobbersPred    : 1;
00104       unsigned NonPredSize;
00105       MachineBasicBlock *BB;
00106       MachineBasicBlock *TrueBB;
00107       MachineBasicBlock *FalseBB;
00108       SmallVector<MachineOperand, 4> BrCond;
00109       SmallVector<MachineOperand, 4> Predicate;
00110       BBInfo() : IsDone(false), IsBeingAnalyzed(false),
00111                  IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
00112                  HasFallThrough(false), IsUnpredicable(false),
00113                  CannotBeCopied(false), ClobbersPred(false), NonPredSize(0),
00114                  BB(0), TrueBB(0), FalseBB(0) {}
00115     };
00116 
00117     /// IfcvtToken - Record information about pending if-conversions to attemp:
00118     /// BBI             - Corresponding BBInfo.
00119     /// Kind            - Type of block. See IfcvtKind.
00120     /// NeedSubsumption - True if the to-be-predicated BB has already been
00121     ///                   predicated.
00122     /// NumDups      - Number of instructions that would be duplicated due
00123     ///                   to this if-conversion. (For diamonds, the number of
00124     ///                   identical instructions at the beginnings of both
00125     ///                   paths).
00126     /// NumDups2     - For diamonds, the number of identical instructions
00127     ///                   at the ends of both paths.
00128     struct IfcvtToken {
00129       BBInfo &BBI;
00130       IfcvtKind Kind;
00131       bool NeedSubsumption;
00132       unsigned NumDups;
00133       unsigned NumDups2;
00134       IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0)
00135         : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {}
00136     };
00137 
00138     /// Roots - Basic blocks that do not have successors. These are the starting
00139     /// points of Graph traversal.
00140     std::vector<MachineBasicBlock*> Roots;
00141 
00142     /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
00143     /// basic block number.
00144     std::vector<BBInfo> BBAnalysis;
00145 
00146     const TargetLowering *TLI;
00147     const TargetInstrInfo *TII;
00148     bool MadeChange;
00149     int FnNum;
00150   public:
00151     static char ID;
00152     IfConverter() : MachineFunctionPass(&ID), FnNum(-1) {}
00153 
00154     virtual bool runOnMachineFunction(MachineFunction &MF);
00155     virtual const char *getPassName() const { return "If Converter"; }
00156 
00157   private:
00158     bool ReverseBranchCondition(BBInfo &BBI);
00159     bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const;
00160     bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
00161                        bool FalseBranch, unsigned &Dups) const;
00162     bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
00163                       unsigned &Dups1, unsigned &Dups2) const;
00164     void ScanInstructions(BBInfo &BBI);
00165     BBInfo &AnalyzeBlock(MachineBasicBlock *BB,
00166                          std::vector<IfcvtToken*> &Tokens);
00167     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
00168                              bool isTriangle = false, bool RevBranch = false);
00169     bool AnalyzeBlocks(MachineFunction &MF,
00170                        std::vector<IfcvtToken*> &Tokens);
00171     void InvalidatePreds(MachineBasicBlock *BB);
00172     void RemoveExtraEdges(BBInfo &BBI);
00173     bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
00174     bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
00175     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
00176                           unsigned NumDups1, unsigned NumDups2);
00177     void PredicateBlock(BBInfo &BBI,
00178                         MachineBasicBlock::iterator E,
00179                         SmallVectorImpl<MachineOperand> &Cond);
00180     void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
00181                                SmallVectorImpl<MachineOperand> &Cond,
00182                                bool IgnoreBr = false);
00183     void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI);
00184 
00185     bool MeetIfcvtSizeLimit(unsigned Size) const {
00186       return Size > 0 && Size <= TLI->getIfCvtBlockSizeLimit();
00187     }
00188 
00189     // blockAlwaysFallThrough - Block ends without a terminator.
00190     bool blockAlwaysFallThrough(BBInfo &BBI) const {
00191       return BBI.IsBrAnalyzable && BBI.TrueBB == NULL;
00192     }
00193 
00194     // IfcvtTokenCmp - Used to sort if-conversion candidates.
00195     static bool IfcvtTokenCmp(IfcvtToken *C1, IfcvtToken *C2) {
00196       int Incr1 = (C1->Kind == ICDiamond)
00197         ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;
00198       int Incr2 = (C2->Kind == ICDiamond)
00199         ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;
00200       if (Incr1 > Incr2)
00201         return true;
00202       else if (Incr1 == Incr2) {
00203         // Favors subsumption.
00204         if (C1->NeedSubsumption == false && C2->NeedSubsumption == true)
00205           return true;
00206         else if (C1->NeedSubsumption == C2->NeedSubsumption) {
00207           // Favors diamond over triangle, etc.
00208           if ((unsigned)C1->Kind < (unsigned)C2->Kind)
00209             return true;
00210           else if (C1->Kind == C2->Kind)
00211             return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
00212         }
00213       }
00214       return false;
00215     }
00216   };
00217 
00218   char IfConverter::ID = 0;
00219 }
00220 
00221 static RegisterPass<IfConverter>
00222 X("if-converter", "If Converter");
00223 
00224 FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
00225 
00226 bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
00227   TLI = MF.getTarget().getTargetLowering();
00228   TII = MF.getTarget().getInstrInfo();
00229   if (!TII) return false;
00230 
00231   DEBUG(errs() << "\nIfcvt: function (" << ++FnNum <<  ") \'"
00232         << MF.getFunction()->getName() << "\'");
00233 
00234   if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
00235     DOUT << " skipped\n";
00236     return false;
00237   }
00238   DOUT << "\n";
00239 
00240   MF.RenumberBlocks();
00241   BBAnalysis.resize(MF.getNumBlockIDs());
00242 
00243   // Look for root nodes, i.e. blocks without successors.
00244   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
00245     if (I->succ_empty())
00246       Roots.push_back(I);
00247 
00248   std::vector<IfcvtToken*> Tokens;
00249   MadeChange = false;
00250   unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
00251     NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
00252   while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
00253     // Do an initial analysis for each basic block and find all the potential
00254     // candidates to perform if-conversion.
00255     bool Change = AnalyzeBlocks(MF, Tokens);
00256     while (!Tokens.empty()) {
00257       IfcvtToken *Token = Tokens.back();
00258       Tokens.pop_back();
00259       BBInfo &BBI = Token->BBI;
00260       IfcvtKind Kind = Token->Kind;
00261       unsigned NumDups = Token->NumDups;
00262       unsigned NumDups2 = Token->NumDups2;
00263 
00264       delete Token;
00265 
00266       // If the block has been evicted out of the queue or it has already been
00267       // marked dead (due to it being predicated), then skip it.
00268       if (BBI.IsDone)
00269         BBI.IsEnqueued = false;
00270       if (!BBI.IsEnqueued)
00271         continue;
00272 
00273       BBI.IsEnqueued = false;
00274 
00275       bool RetVal = false;
00276       switch (Kind) {
00277       default: assert(false && "Unexpected!");
00278         break;
00279       case ICSimple:
00280       case ICSimpleFalse: {
00281         bool isFalse = Kind == ICSimpleFalse;
00282         if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
00283         DOUT << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"")
00284              << "): BB#" << BBI.BB->getNumber() << " ("
00285              << ((Kind == ICSimpleFalse)
00286                  ? BBI.FalseBB->getNumber()
00287                  : BBI.TrueBB->getNumber()) << ") ";
00288         RetVal = IfConvertSimple(BBI, Kind);
00289         DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
00290         if (RetVal) {
00291           if (isFalse) NumSimpleFalse++;
00292           else         NumSimple++;
00293         }
00294        break;
00295       }
00296       case ICTriangle:
00297       case ICTriangleRev:
00298       case ICTriangleFalse:
00299       case ICTriangleFRev: {
00300         bool isFalse = Kind == ICTriangleFalse;
00301         bool isRev   = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
00302         if (DisableTriangle && !isFalse && !isRev) break;
00303         if (DisableTriangleR && !isFalse && isRev) break;
00304         if (DisableTriangleF && isFalse && !isRev) break;
00305         if (DisableTriangleFR && isFalse && isRev) break;
00306         DOUT << "Ifcvt (Triangle";
00307         if (isFalse)
00308           DOUT << " false";
00309         if (isRev)
00310           DOUT << " rev";
00311         DOUT << "): BB#" << BBI.BB->getNumber() << " (T:"
00312              << BBI.TrueBB->getNumber() << ",F:"
00313              << BBI.FalseBB->getNumber() << ") ";
00314         RetVal = IfConvertTriangle(BBI, Kind);
00315         DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
00316         if (RetVal) {
00317           if (isFalse) {
00318             if (isRev) NumTriangleFRev++;
00319             else       NumTriangleFalse++;
00320           } else {
00321             if (isRev) NumTriangleRev++;
00322             else       NumTriangle++;
00323           }
00324         }
00325         break;
00326       }
00327       case ICDiamond: {
00328         if (DisableDiamond) break;
00329         DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
00330              << BBI.TrueBB->getNumber() << ",F:"
00331              << BBI.FalseBB->getNumber() << ") ";
00332         RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
00333         DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
00334         if (RetVal) NumDiamonds++;
00335         break;
00336       }
00337       }
00338 
00339       Change |= RetVal;
00340 
00341       NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
00342         NumTriangleFalse + NumTriangleFRev + NumDiamonds;
00343       if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)
00344         break;
00345     }
00346 
00347     if (!Change)
00348       break;
00349     MadeChange |= Change;
00350   }
00351 
00352   // Delete tokens in case of early exit.
00353   while (!Tokens.empty()) {
00354     IfcvtToken *Token = Tokens.back();
00355     Tokens.pop_back();
00356     delete Token;
00357   }
00358 
00359   Tokens.clear();
00360   Roots.clear();
00361   BBAnalysis.clear();
00362 
00363   return MadeChange;
00364 }
00365 
00366 /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
00367 /// its 'true' successor.
00368 static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
00369                                          MachineBasicBlock *TrueBB) {
00370   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
00371          E = BB->succ_end(); SI != E; ++SI) {
00372     MachineBasicBlock *SuccBB = *SI;
00373     if (SuccBB != TrueBB)
00374       return SuccBB;
00375   }
00376   return NULL;
00377 }
00378 
00379 /// ReverseBranchCondition - Reverse the condition of the end of the block
00380 /// branch. Swap block's 'true' and 'false' successors.
00381 bool IfConverter::ReverseBranchCondition(BBInfo &BBI) {
00382   if (!TII->ReverseBranchCondition(BBI.BrCond)) {
00383     TII->RemoveBranch(*BBI.BB);
00384     TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond);
00385     std::swap(BBI.TrueBB, BBI.FalseBB);
00386     return true;
00387   }
00388   return false;
00389 }
00390 
00391 /// getNextBlock - Returns the next block in the function blocks ordering. If
00392 /// it is the end, returns NULL.
00393 static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) {
00394   MachineFunction::iterator I = BB;
00395   MachineFunction::iterator E = BB->getParent()->end();
00396   if (++I == E)
00397     return NULL;
00398   return I;
00399 }
00400 
00401 /// ValidSimple - Returns true if the 'true' block (along with its
00402 /// predecessor) forms a valid simple shape for ifcvt. It also returns the
00403 /// number of instructions that the ifcvt would need to duplicate if performed
00404 /// in Dups.
00405 bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const {
00406   Dups = 0;
00407   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
00408     return false;
00409 
00410   if (TrueBBI.IsBrAnalyzable)
00411     return false;
00412 
00413   if (TrueBBI.BB->pred_size() > 1) {
00414     if (TrueBBI.CannotBeCopied ||
00415         TrueBBI.NonPredSize > TLI->getIfCvtDupBlockSizeLimit())
00416       return false;
00417     Dups = TrueBBI.NonPredSize;
00418   }
00419 
00420   return true;
00421 }
00422 
00423 /// ValidTriangle - Returns true if the 'true' and 'false' blocks (along
00424 /// with their common predecessor) forms a valid triangle shape for ifcvt.
00425 /// If 'FalseBranch' is true, it checks if 'true' block's false branch
00426 /// branches to the false branch rather than the other way around. It also
00427 /// returns the number of instructions that the ifcvt would need to duplicate
00428 /// if performed in 'Dups'.
00429 bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
00430                                 bool FalseBranch, unsigned &Dups) const {
00431   Dups = 0;
00432   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
00433     return false;
00434 
00435   if (TrueBBI.BB->pred_size() > 1) {
00436     if (TrueBBI.CannotBeCopied)
00437       return false;
00438 
00439     unsigned Size = TrueBBI.NonPredSize;
00440     if (TrueBBI.IsBrAnalyzable) {
00441       if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
00442         // Ends with an unconditional branch. It will be removed.
00443         --Size;
00444       else {
00445         MachineBasicBlock *FExit = FalseBranch
00446           ? TrueBBI.TrueBB : TrueBBI.FalseBB;
00447         if (FExit)
00448           // Require a conditional branch
00449           ++Size;
00450       }
00451     }
00452     if (Size > TLI->getIfCvtDupBlockSizeLimit())
00453       return false;
00454     Dups = Size;
00455   }
00456 
00457   MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
00458   if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
00459     MachineFunction::iterator I = TrueBBI.BB;
00460     if (++I == TrueBBI.BB->getParent()->end())
00461       return false;
00462     TExit = I;
00463   }
00464   return TExit && TExit == FalseBBI.BB;
00465 }
00466 
00467 static
00468 MachineBasicBlock::iterator firstNonBranchInst(MachineBasicBlock *BB,
00469                                                const TargetInstrInfo *TII) {
00470   MachineBasicBlock::iterator I = BB->end();
00471   while (I != BB->begin()) {
00472     --I;
00473     if (!I->getDesc().isBranch())
00474       break;
00475   }
00476   return I;
00477 }
00478 
00479 /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
00480 /// with their common predecessor) forms a valid diamond shape for ifcvt.
00481 bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
00482                                unsigned &Dups1, unsigned &Dups2) const {
00483   Dups1 = Dups2 = 0;
00484   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
00485       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
00486     return false;
00487 
00488   MachineBasicBlock *TT = TrueBBI.TrueBB;
00489   MachineBasicBlock *FT = FalseBBI.TrueBB;
00490 
00491   if (!TT && blockAlwaysFallThrough(TrueBBI))
00492     TT = getNextBlock(TrueBBI.BB);
00493   if (!FT && blockAlwaysFallThrough(FalseBBI))
00494     FT = getNextBlock(FalseBBI.BB);
00495   if (TT != FT)
00496     return false;
00497   if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
00498     return false;
00499   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
00500     return false;
00501 
00502   // FIXME: Allow true block to have an early exit?
00503   if (TrueBBI.FalseBB || FalseBBI.FalseBB ||
00504       (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred))
00505     return false;
00506 
00507   MachineBasicBlock::iterator TI = TrueBBI.BB->begin();
00508   MachineBasicBlock::iterator FI = FalseBBI.BB->begin();
00509   while (TI != TrueBBI.BB->end() && FI != FalseBBI.BB->end()) {
00510     if (!TI->isIdenticalTo(FI))
00511       break;
00512     ++Dups1;
00513     ++TI;
00514     ++FI;
00515   }
00516 
00517   TI = firstNonBranchInst(TrueBBI.BB, TII);
00518   FI = firstNonBranchInst(FalseBBI.BB, TII);
00519   while (TI != TrueBBI.BB->begin() && FI != FalseBBI.BB->begin()) {
00520     if (!TI->isIdenticalTo(FI))
00521       break;
00522     ++Dups2;
00523     --TI;
00524     --FI;
00525   }
00526 
00527   return true;
00528 }
00529 
00530 /// ScanInstructions - Scan all the instructions in the block to determine if
00531 /// the block is predicable. In most cases, that means all the instructions
00532 /// in the block are isPredicable(). Also checks if the block contains any
00533 /// instruction which can clobber a predicate (e.g. condition code register).
00534 /// If so, the block is not predicable unless it's the last instruction.
00535 void IfConverter::ScanInstructions(BBInfo &BBI) {
00536   if (BBI.IsDone)
00537     return;
00538 
00539   bool AlreadyPredicated = BBI.Predicate.size() > 0;
00540   // First analyze the end of BB branches.
00541   BBI.TrueBB = BBI.FalseBB = NULL;
00542   BBI.BrCond.clear();
00543   BBI.IsBrAnalyzable =
00544     !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
00545   BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL;
00546 
00547   if (BBI.BrCond.size()) {
00548     // No false branch. This BB must end with a conditional branch and a
00549     // fallthrough.
00550     if (!BBI.FalseBB)
00551       BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);  
00552     if (!BBI.FalseBB) {
00553       // Malformed bcc? True and false blocks are the same?
00554       BBI.IsUnpredicable = true;
00555       return;
00556     }
00557   }
00558 
00559   // Then scan all the instructions.
00560   BBI.NonPredSize = 0;
00561   BBI.ClobbersPred = false;
00562   for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
00563        I != E; ++I) {
00564     const TargetInstrDesc &TID = I->getDesc();
00565     if (TID.isNotDuplicable())
00566       BBI.CannotBeCopied = true;
00567 
00568     bool isPredicated = TII->isPredicated(I);
00569     bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch();
00570 
00571     if (!isCondBr) {
00572       if (!isPredicated)
00573         BBI.NonPredSize++;
00574       else if (!AlreadyPredicated) {
00575         // FIXME: This instruction is already predicated before the
00576         // if-conversion pass. It's probably something like a conditional move.
00577         // Mark this block unpredicable for now.
00578         BBI.IsUnpredicable = true;
00579         return;
00580       }
00581     }
00582 
00583     if (BBI.ClobbersPred && !isPredicated) {
00584       // Predicate modification instruction should end the block (except for
00585       // already predicated instructions and end of block branches).
00586       if (isCondBr) {
00587         // A conditional branch is not predicable, but it may be eliminated.
00588         continue;
00589       }
00590 
00591       // Predicate may have been modified, the subsequent (currently)
00592       // unpredicated instructions cannot be correctly predicated.
00593       BBI.IsUnpredicable = true;
00594       return;
00595     }
00596 
00597     // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
00598     // still potentially predicable.
00599     std::vector<MachineOperand> PredDefs;
00600     if (TII->DefinesPredicate(I, PredDefs))
00601       BBI.ClobbersPred = true;
00602 
00603     if (!TID.isPredicable()) {
00604       BBI.IsUnpredicable = true;
00605       return;
00606     }
00607   }
00608 }
00609 
00610 /// FeasibilityAnalysis - Determine if the block is a suitable candidate to be
00611 /// predicated by the specified predicate.
00612 bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
00613                                       SmallVectorImpl<MachineOperand> &Pred,
00614                                       bool isTriangle, bool RevBranch) {
00615   // If the block is dead or unpredicable, then it cannot be predicated.
00616   if (BBI.IsDone || BBI.IsUnpredicable)
00617     return false;
00618 
00619   // If it is already predicated, check if its predicate subsumes the new
00620   // predicate.
00621   if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred))
00622     return false;
00623 
00624   if (BBI.BrCond.size()) {
00625     if (!isTriangle)
00626       return false;
00627 
00628     // Test predicate subsumption.
00629     SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
00630     SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
00631     if (RevBranch) {
00632       if (TII->ReverseBranchCondition(Cond))
00633         return false;
00634     }
00635     if (TII->ReverseBranchCondition(RevPred) ||
00636         !TII->SubsumesPredicate(Cond, RevPred))
00637       return false;
00638   }
00639 
00640   return true;
00641 }
00642 
00643 /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
00644 /// the specified block. Record its successors and whether it looks like an
00645 /// if-conversion candidate.
00646 IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB,
00647                                              std::vector<IfcvtToken*> &Tokens) {
00648   BBInfo &BBI = BBAnalysis[BB->getNumber()];
00649 
00650   if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed)
00651     return BBI;
00652 
00653   BBI.BB = BB;
00654   BBI.IsBeingAnalyzed = true;
00655 
00656   ScanInstructions(BBI);
00657 
00658   // Unanalyzable or ends with fallthrough or unconditional branch.
00659   if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) {
00660     BBI.IsBeingAnalyzed = false;
00661     BBI.IsAnalyzed = true;
00662     return BBI;
00663   }
00664 
00665   // Do not ifcvt if either path is a back edge to the entry block.
00666   if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
00667     BBI.IsBeingAnalyzed = false;
00668     BBI.IsAnalyzed = true;
00669     return BBI;
00670   }
00671 
00672   // Do not ifcvt if true and false fallthrough blocks are the same.
00673   if (!BBI.FalseBB) {
00674     BBI.IsBeingAnalyzed = false;
00675     BBI.IsAnalyzed = true;
00676     return BBI;
00677   }
00678 
00679   BBInfo &TrueBBI  = AnalyzeBlock(BBI.TrueBB, Tokens);
00680   BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
00681 
00682   if (TrueBBI.IsDone && FalseBBI.IsDone) {
00683     BBI.IsBeingAnalyzed = false;
00684     BBI.IsAnalyzed = true;
00685     return BBI;
00686   }
00687 
00688   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
00689   bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
00690 
00691   unsigned Dups = 0;
00692   unsigned Dups2 = 0;
00693   bool TNeedSub = TrueBBI.Predicate.size() > 0;
00694   bool FNeedSub = FalseBBI.Predicate.size() > 0;
00695   bool Enqueued = false;
00696   if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
00697       MeetIfcvtSizeLimit(TrueBBI.NonPredSize - (Dups + Dups2)) &&
00698       MeetIfcvtSizeLimit(FalseBBI.NonPredSize - (Dups + Dups2)) &&
00699       FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
00700       FeasibilityAnalysis(FalseBBI, RevCond)) {
00701     // Diamond:
00702     //   EBB
00703     //   / \_
00704     //  |   |
00705     // TBB FBB
00706     //   \ /
00707     //  TailBB
00708     // Note TailBB can be empty.
00709     Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
00710                                     Dups2));
00711     Enqueued = true;
00712   }
00713 
00714   if (ValidTriangle(TrueBBI, FalseBBI, false, Dups) &&
00715       MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
00716       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
00717     // Triangle:
00718     //   EBB
00719     //   | \_
00720     //   |  |
00721     //   | TBB
00722     //   |  /
00723     //   FBB
00724     Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
00725     Enqueued = true;
00726   }
00727   
00728   if (ValidTriangle(TrueBBI, FalseBBI, true, Dups) &&
00729       MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
00730       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
00731     Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
00732     Enqueued = true;
00733   }
00734 
00735   if (ValidSimple(TrueBBI, Dups) &&
00736       MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
00737       FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
00738     // Simple (split, no rejoin):
00739     //   EBB
00740     //   | \_
00741     //   |  |
00742     //   | TBB---> exit
00743     //   |    
00744     //   FBB
00745     Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
00746     Enqueued = true;
00747   }
00748 
00749   if (CanRevCond) {
00750     // Try the other path...
00751     if (ValidTriangle(FalseBBI, TrueBBI, false, Dups) &&
00752         MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
00753         FeasibilityAnalysis(FalseBBI, RevCond, true)) {
00754       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
00755       Enqueued = true;
00756     }
00757 
00758     if (ValidTriangle(FalseBBI, TrueBBI, true, Dups) &&
00759         MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
00760         FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
00761       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
00762       Enqueued = true;
00763     }
00764 
00765     if (ValidSimple(FalseBBI, Dups) &&
00766         MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
00767         FeasibilityAnalysis(FalseBBI, RevCond)) {
00768       Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
00769       Enqueued = true;
00770     }
00771   }
00772 
00773   BBI.IsEnqueued = Enqueued;
00774   BBI.IsBeingAnalyzed = false;
00775   BBI.IsAnalyzed = true;
00776   return BBI;
00777 }
00778 
00779 /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
00780 /// candidates. It returns true if any CFG restructuring is done to expose more
00781 /// if-conversion opportunities.
00782 bool IfConverter::AnalyzeBlocks(MachineFunction &MF,
00783                                 std::vector<IfcvtToken*> &Tokens) {
00784   bool Change = false;
00785   std::set<MachineBasicBlock*> Visited;
00786   for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
00787     for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited),
00788            E = idf_ext_end(Roots[i], Visited); I != E; ++I) {
00789       MachineBasicBlock *BB = *I;
00790       AnalyzeBlock(BB, Tokens);
00791     }
00792   }
00793 
00794   // Sort to favor more complex ifcvt scheme.
00795   std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
00796 
00797   return Change;
00798 }
00799 
00800 /// canFallThroughTo - Returns true either if ToBB is the next block after BB or
00801 /// that all the intervening blocks are empty (given BB can fall through to its
00802 /// next block).
00803 static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
00804   MachineFunction::iterator I = BB;
00805   MachineFunction::iterator TI = ToBB;
00806   MachineFunction::iterator E = BB->getParent()->end();
00807   while (++I != TI)
00808     if (I == E || !I->empty())
00809       return false;
00810   return true;
00811 }
00812 
00813 /// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed
00814 /// to determine if it can be if-converted. If predecessor is already enqueued,
00815 /// dequeue it!
00816 void IfConverter::InvalidatePreds(MachineBasicBlock *BB) {
00817   for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
00818          E = BB->pred_end(); PI != E; ++PI) {
00819     BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
00820     if (PBBI.IsDone || PBBI.BB == BB)
00821       continue;
00822     PBBI.IsAnalyzed = false;
00823     PBBI.IsEnqueued = false;
00824   }
00825 }
00826 
00827 /// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
00828 ///
00829 static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
00830                                const TargetInstrInfo *TII) {
00831   SmallVector<MachineOperand, 0> NoCond;
00832   TII->InsertBranch(*BB, ToBB, NULL, NoCond);
00833 }
00834 
00835 /// RemoveExtraEdges - Remove true / false edges if either / both are no longer
00836 /// successors.
00837 void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
00838   MachineBasicBlock *TBB = NULL, *FBB = NULL;
00839   SmallVector<MachineOperand, 4> Cond;
00840   if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
00841     BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
00842 }
00843 
00844 /// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
00845 ///
00846 bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
00847   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
00848   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
00849   BBInfo *CvtBBI = &TrueBBI;
00850   BBInfo *NextBBI = &FalseBBI;
00851 
00852   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
00853   if (Kind == ICSimpleFalse)
00854     std::swap(CvtBBI, NextBBI);
00855 
00856   if (CvtBBI->IsDone ||
00857       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
00858     // Something has changed. It's no longer safe to predicate this block.
00859     BBI.IsAnalyzed = false;
00860     CvtBBI->IsAnalyzed = false;
00861     return false;
00862   }
00863 
00864   if (Kind == ICSimpleFalse)
00865     if (TII->ReverseBranchCondition(Cond))
00866       assert(false && "Unable to reverse branch condition!");
00867 
00868   if (CvtBBI->BB->pred_size() > 1) {
00869     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
00870     // Copy instructions in the true block, predicate them, and add them to
00871     // the entry block.
00872     CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
00873   } else {
00874     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
00875 
00876     // Merge converted block into entry block.
00877     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
00878     MergeBlocks(BBI, *CvtBBI);
00879   }
00880 
00881   bool IterIfcvt = true;
00882   if (!canFallThroughTo(BBI.BB, NextBBI->BB)) {
00883     InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
00884     BBI.HasFallThrough = false;
00885     // Now ifcvt'd block will look like this:
00886     // BB:
00887     // ...
00888     // t, f = cmp
00889     // if t op
00890     // b BBf
00891     //
00892     // We cannot further ifcvt this block because the unconditional branch
00893     // will have to be predicated on the new condition, that will not be
00894     // available if cmp executes.
00895     IterIfcvt = false;
00896   }
00897 
00898   RemoveExtraEdges(BBI);
00899 
00900   // Update block info. BB can be iteratively if-converted.
00901   if (!IterIfcvt)
00902     BBI.IsDone = true;
00903   InvalidatePreds(BBI.BB);
00904   CvtBBI->IsDone = true;
00905 
00906   // FIXME: Must maintain LiveIns.
00907   return true;
00908 }
00909 
00910 /// IfConvertTriangle - If convert a triangle sub-CFG.
00911 ///
00912 bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
00913   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
00914   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
00915   BBInfo *CvtBBI = &TrueBBI;
00916   BBInfo *NextBBI = &FalseBBI;
00917 
00918   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
00919   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
00920     std::swap(CvtBBI, NextBBI);
00921 
00922   if (CvtBBI->IsDone ||
00923       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
00924     // Something has changed. It's no longer safe to predicate this block.
00925     BBI.IsAnalyzed = false;
00926     CvtBBI->IsAnalyzed = false;
00927     return false;
00928   }
00929 
00930   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
00931     if (TII->ReverseBranchCondition(Cond))
00932       assert(false && "Unable to reverse branch condition!");
00933 
00934   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
00935     if (ReverseBranchCondition(*CvtBBI)) {
00936       // BB has been changed, modify its predecessors (except for this
00937       // one) so they don't get ifcvt'ed based on bad intel.
00938       for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
00939              E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
00940         MachineBasicBlock *PBB = *PI;
00941         if (PBB == BBI.BB)
00942           continue;
00943         BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
00944         if (PBBI.IsEnqueued) {
00945           PBBI.IsAnalyzed = false;
00946           PBBI.IsEnqueued = false;
00947         }
00948       }
00949     }
00950   }
00951 
00952   bool HasEarlyExit = CvtBBI->FalseBB != NULL;
00953   bool DupBB = CvtBBI->BB->pred_size() > 1;
00954   if (DupBB) {
00955     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
00956     // Copy instructions in the true block, predicate them, and add them to
00957     // the entry block.
00958     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
00959   } else {
00960     // Predicate the 'true' block after removing its branch.
00961     CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
00962     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
00963 
00964     // Now merge the entry of the triangle with the true block.
00965     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
00966     MergeBlocks(BBI, *CvtBBI);
00967   }
00968 
00969   // If 'true' block has a 'false' successor, add an exit branch to it.
00970   if (HasEarlyExit) {
00971     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
00972                                            CvtBBI->BrCond.end());
00973     if (TII->ReverseBranchCondition(RevCond))
00974       assert(false && "Unable to reverse branch condition!");
00975     TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond);
00976     BBI.BB->addSuccessor(CvtBBI->FalseBB);
00977   }
00978 
00979   // Merge in the 'false' block if the 'false' block has no other
00980   // predecessors. Otherwise, add an unconditional branch to 'false'.
00981   bool FalseBBDead = false;
00982   bool IterIfcvt = true;
00983   bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
00984   if (!isFallThrough) {
00985     // Only merge them if the true block does not fallthrough to the false
00986     // block. By not merging them, we make it possible to iteratively
00987     // ifcvt the blocks.
00988     if (!HasEarlyExit &&
00989         NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough) {
00990       MergeBlocks(BBI, *NextBBI);
00991       FalseBBDead = true;
00992     } else {
00993       InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
00994       BBI.HasFallThrough = false;
00995     }
00996     // Mixed predicated and unpredicated code. This cannot be iteratively
00997     // predicated.
00998     IterIfcvt = false;
00999   }
01000 
01001   RemoveExtraEdges(BBI);
01002 
01003   // Update block info. BB can be iteratively if-converted.
01004   if (!IterIfcvt) 
01005     BBI.IsDone = true;
01006   InvalidatePreds(BBI.BB);
01007   CvtBBI->IsDone = true;
01008   if (FalseBBDead)
01009     NextBBI->IsDone = true;
01010 
01011   // FIXME: Must maintain LiveIns.
01012   return true;
01013 }
01014 
01015 /// IfConvertDiamond - If convert a diamond sub-CFG.
01016 ///
01017 bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
01018                                    unsigned NumDups1, unsigned NumDups2) {
01019   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
01020   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
01021   MachineBasicBlock *TailBB = TrueBBI.TrueBB;
01022   // True block must fall through or end with an unanalyzable terminator.
01023   if (!TailBB) {
01024     if (blockAlwaysFallThrough(TrueBBI))
01025       TailBB = FalseBBI.TrueBB;
01026     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
01027   }
01028 
01029   if (TrueBBI.IsDone || FalseBBI.IsDone ||
01030       TrueBBI.BB->pred_size() > 1 ||
01031       FalseBBI.BB->pred_size() > 1) {
01032     // Something has changed. It's no longer safe to predicate these blocks.
01033     BBI.IsAnalyzed = false;
01034     TrueBBI.IsAnalyzed = false;
01035     FalseBBI.IsAnalyzed = false;
01036     return false;
01037   }
01038 
01039   // Merge the 'true' and 'false' blocks by copying the instructions
01040   // from the 'false' block to the 'true' block. That is, unless the true
01041   // block would clobber the predicate, in that case, do the opposite.
01042   BBInfo *BBI1 = &TrueBBI;
01043   BBInfo *BBI2 = &FalseBBI;
01044   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
01045   if (TII->ReverseBranchCondition(RevCond))
01046     assert(false && "Unable to reverse branch condition!");
01047   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
01048   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
01049 
01050   // Figure out the more profitable ordering.
01051   bool DoSwap = false;
01052   if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
01053     DoSwap = true;
01054   else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
01055     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
01056       DoSwap = true;
01057   }
01058   if (DoSwap) {
01059     std::swap(BBI1, BBI2);
01060     std::swap(Cond1, Cond2);
01061   }
01062 
01063   // Remove the conditional branch from entry to the blocks.
01064   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
01065 
01066   // Remove the duplicated instructions at the beginnings of both paths.
01067   MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
01068   MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
01069   BBI1->NonPredSize -= NumDups1;
01070   BBI2->NonPredSize -= NumDups1;
01071   while (NumDups1 != 0) {
01072     ++DI1;
01073     ++DI2;
01074     --NumDups1;
01075   }
01076   BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
01077   BBI2->BB->erase(BBI2->BB->begin(), DI2);
01078 
01079   // Predicate the 'true' block after removing its branch.
01080   BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
01081   DI1 = BBI1->BB->end();
01082   for (unsigned i = 0; i != NumDups2; ++i)
01083     --DI1;
01084   BBI1->BB->erase(DI1, BBI1->BB->end());
01085   PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1);
01086 
01087   // Predicate the 'false' block.
01088   BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
01089   DI2 = BBI2->BB->end();
01090   while (NumDups2 != 0) {
01091     --DI2;
01092     --NumDups2;
01093   }
01094   PredicateBlock(*BBI2, DI2, *Cond2);
01095 
01096   // Merge the true block into the entry of the diamond.
01097   MergeBlocks(BBI, *BBI1);
01098   MergeBlocks(BBI, *BBI2);
01099 
01100   // If the if-converted block falls through or unconditionally branches into
01101   // the tail block, and the tail block does not have other predecessors, then
01102   // fold the tail block in as well. Otherwise, unless it falls through to the
01103   // tail, add a unconditional branch to it.
01104   if (TailBB) {
01105     BBInfo TailBBI = BBAnalysis[TailBB->getNumber()];
01106     if (TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) {
01107       BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
01108       MergeBlocks(BBI, TailBBI);
01109       TailBBI.IsDone = true;
01110     } else {
01111       InsertUncondBranch(BBI.BB, TailBB, TII);
01112       BBI.HasFallThrough = false;
01113     }
01114   }
01115 
01116   RemoveExtraEdges(BBI);
01117 
01118   // Update block info.
01119   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
01120   InvalidatePreds(BBI.BB);
01121 
01122   // FIXME: Must maintain LiveIns.
01123   return true;
01124 }
01125 
01126 /// PredicateBlock - Predicate instructions from the start of the block to the
01127 /// specified end with the specified condition.
01128 void IfConverter::PredicateBlock(BBInfo &BBI,
01129                                  MachineBasicBlock::iterator E,
01130                                  SmallVectorImpl<MachineOperand> &Cond) {
01131   for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
01132     if (TII->isPredicated(I))
01133       continue;
01134     if (!TII->PredicateInstruction(I, Cond)) {
01135 #ifndef NDEBUG
01136       cerr << "Unable to predicate " << *I << "!\n";
01137 #endif
01138       llvm_unreachable(0);
01139     }
01140   }
01141 
01142   std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
01143 
01144   BBI.IsAnalyzed = false;
01145   BBI.NonPredSize = 0;
01146 
01147   NumIfConvBBs++;
01148 }
01149 
01150 /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
01151 /// the destination block. Skip end of block branches if IgnoreBr is true.
01152 void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
01153                                         SmallVectorImpl<MachineOperand> &Cond,
01154                                         bool IgnoreBr) {
01155   MachineFunction &MF = *ToBBI.BB->getParent();
01156 
01157   for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
01158          E = FromBBI.BB->end(); I != E; ++I) {
01159     const TargetInstrDesc &TID = I->getDesc();
01160     bool isPredicated = TII->isPredicated(I);
01161     // Do not copy the end of the block branches.
01162     if (IgnoreBr && !isPredicated && TID.isBranch())
01163       break;
01164 
01165     MachineInstr *MI = MF.CloneMachineInstr(I);
01166     ToBBI.BB->insert(ToBBI.BB->end(), MI);
01167     ToBBI.NonPredSize++;
01168 
01169     if (!isPredicated)
01170       if (!TII->PredicateInstruction(MI, Cond)) {
01171 #ifndef NDEBUG
01172         cerr << "Unable to predicate " << *I << "!\n";
01173 #endif
01174         llvm_unreachable(0);
01175       }
01176   }
01177 
01178   std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
01179                                          FromBBI.BB->succ_end());
01180   MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
01181   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
01182 
01183   for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
01184     MachineBasicBlock *Succ = Succs[i];
01185     // Fallthrough edge can't be transferred.
01186     if (Succ == FallThrough)
01187       continue;
01188     ToBBI.BB->addSuccessor(Succ);
01189   }
01190 
01191   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
01192             std::back_inserter(ToBBI.Predicate));
01193   std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
01194 
01195   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
01196   ToBBI.IsAnalyzed = false;
01197 
01198   NumDupBBs++;
01199 }
01200 
01201 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
01202 ///
01203 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
01204   ToBBI.BB->splice(ToBBI.BB->end(),
01205                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
01206 
01207   // Redirect all branches to FromBB to ToBB.
01208   std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(),
01209                                          FromBBI.BB->pred_end());
01210   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
01211     MachineBasicBlock *Pred = Preds[i];
01212     if (Pred == ToBBI.BB)
01213       continue;
01214     Pred->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB);
01215   }
01216  
01217   std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
01218                                          FromBBI.BB->succ_end());
01219   MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
01220   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
01221 
01222   for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
01223     MachineBasicBlock *Succ = Succs[i];
01224     // Fallthrough edge can't be transferred.
01225     if (Succ == FallThrough)
01226       continue;
01227     FromBBI.BB->removeSuccessor(Succ);
01228     ToBBI.BB->addSuccessor(Succ);
01229   }
01230 
01231   // Now FromBBI always falls through to the next block!
01232   if (NBB && !FromBBI.BB->isSuccessor(NBB))
01233     FromBBI.BB->addSuccessor(NBB);
01234 
01235   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
01236             std::back_inserter(ToBBI.Predicate));
01237   FromBBI.Predicate.clear();
01238 
01239   ToBBI.NonPredSize += FromBBI.NonPredSize;
01240   FromBBI.NonPredSize = 0;
01241 
01242   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
01243   ToBBI.HasFallThrough = FromBBI.HasFallThrough;
01244   ToBBI.IsAnalyzed = false;
01245   FromBBI.IsAnalyzed = false;
01246 }