X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FIfConversion.cpp;h=c61fd17e7911e26a92f27559d1a5af08cb2e6dee;hb=165e96bd25200ccabe4539aaf29a249b61074d11;hp=b05f6630ea75a51219fc1c604a02312e811ac5c6;hpb=d2c5eb864fc80665ca57038793f2f4a296a87eb3;p=oota-llvm.git diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index b05f6630ea7..c61fd17e791 100644 --- a/lib/CodeGen/IfConversion.cpp +++ b/lib/CodeGen/IfConversion.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the Evan Cheng and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "ifcvt" +#include "BranchFolding.h" #include "llvm/Function.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineModuleInfo.h" @@ -21,31 +22,31 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" using namespace llvm; -namespace { - // Hidden options for help debugging. - cl::opt IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden); - cl::opt IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden); - cl::opt IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden); - cl::opt DisableSimple("disable-ifcvt-simple", - cl::init(false), cl::Hidden); - cl::opt DisableSimpleF("disable-ifcvt-simple-false", - cl::init(false), cl::Hidden); - cl::opt DisableTriangle("disable-ifcvt-triangle", - cl::init(false), cl::Hidden); - cl::opt DisableTriangleR("disable-ifcvt-triangle-rev", - cl::init(false), cl::Hidden); - cl::opt DisableTriangleF("disable-ifcvt-triangle-false", - cl::init(false), cl::Hidden); - cl::opt DisableTriangleFR("disable-ifcvt-triangle-false-rev", - cl::init(false), cl::Hidden); - cl::opt DisableDiamond("disable-ifcvt-diamond", - cl::init(false), cl::Hidden); -} +// Hidden options for help debugging. +static cl::opt IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden); +static cl::opt IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden); +static cl::opt IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden); +static cl::opt DisableSimple("disable-ifcvt-simple", + cl::init(false), cl::Hidden); +static cl::opt DisableSimpleF("disable-ifcvt-simple-false", + cl::init(false), cl::Hidden); +static cl::opt DisableTriangle("disable-ifcvt-triangle", + cl::init(false), cl::Hidden); +static cl::opt DisableTriangleR("disable-ifcvt-triangle-rev", + cl::init(false), cl::Hidden); +static cl::opt DisableTriangleF("disable-ifcvt-triangle-false", + cl::init(false), cl::Hidden); +static cl::opt DisableTriangleFR("disable-ifcvt-triangle-false-rev", + cl::init(false), cl::Hidden); +static cl::opt DisableDiamond("disable-ifcvt-diamond", + cl::init(false), cl::Hidden); STATISTIC(NumSimple, "Number of simple if-conversions performed"); STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed"); @@ -84,7 +85,7 @@ namespace { /// IsBrAnalyzable - True if AnalyzeBranch() returns false. /// HasFallThrough - True if BB may fallthrough to the following BB. /// IsUnpredicable - True if BB is known to be unpredicable. - /// ClobbersPredicate- True if BB would modify the predicate (e.g. has + /// ClobbersPred - True if BB could modify predicates (e.g. has /// cmp, call, etc.) /// NonPredSize - Number of non-predicated instructions. /// BB - Corresponding MachineBasicBlock. @@ -105,8 +106,8 @@ namespace { MachineBasicBlock *BB; MachineBasicBlock *TrueBB; MachineBasicBlock *FalseBB; - std::vector BrCond; - std::vector Predicate; + SmallVector BrCond; + SmallVector Predicate; BBInfo() : IsDone(false), IsBeingAnalyzed(false), IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false), HasFallThrough(false), IsUnpredicable(false), @@ -117,7 +118,7 @@ namespace { /// IfcvtToken - Record information about pending if-conversions to attemp: /// BBI - Corresponding BBInfo. /// Kind - Type of block. See IfcvtKind. - /// NeedSubsumsion - True if the to be predicated BB has already been + /// NeedSubsumption - True if the to-be-predicated BB has already been /// predicated. /// NumDups - Number of instructions that would be duplicated due /// to this if-conversion. (For diamonds, the number of @@ -128,11 +129,11 @@ namespace { struct IfcvtToken { BBInfo &BBI; IfcvtKind Kind; - bool NeedSubsumsion; + bool NeedSubsumption; unsigned NumDups; unsigned NumDups2; IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0) - : BBI(b), Kind(k), NeedSubsumsion(s), NumDups(d), NumDups2(d2) {} + : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {} }; /// Roots - Basic blocks that do not have successors. These are the starting @@ -146,12 +147,13 @@ namespace { const TargetLowering *TLI; const TargetInstrInfo *TII; bool MadeChange; + int FnNum; public: static char ID; - IfConverter() : MachineFunctionPass((intptr_t)&ID) {} + IfConverter() : MachineFunctionPass(&ID), FnNum(-1) {} virtual bool runOnMachineFunction(MachineFunction &MF); - virtual const char *getPassName() const { return "If converter"; } + virtual const char *getPassName() const { return "If Converter"; } private: bool ReverseBranchCondition(BBInfo &BBI); @@ -163,7 +165,7 @@ namespace { void ScanInstructions(BBInfo &BBI); BBInfo &AnalyzeBlock(MachineBasicBlock *BB, std::vector &Tokens); - bool FeasibilityAnalysis(BBInfo &BBI, std::vector &Cond, + bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl &Cond, bool isTriangle = false, bool RevBranch = false); bool AnalyzeBlocks(MachineFunction &MF, std::vector &Tokens); @@ -175,9 +177,9 @@ namespace { unsigned NumDups1, unsigned NumDups2); void PredicateBlock(BBInfo &BBI, MachineBasicBlock::iterator E, - std::vector &Cond); + SmallVectorImpl &Cond); void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, - std::vector &Cond, + SmallVectorImpl &Cond, bool IgnoreBr = false); void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI); @@ -199,10 +201,10 @@ namespace { if (Incr1 > Incr2) return true; else if (Incr1 == Incr2) { - // Favors subsumsion. - if (C1->NeedSubsumsion == false && C2->NeedSubsumsion == true) + // Favors subsumption. + if (C1->NeedSubsumption == false && C2->NeedSubsumption == true) return true; - else if (C1->NeedSubsumsion == C2->NeedSubsumsion) { + else if (C1->NeedSubsumption == C2->NeedSubsumption) { // Favors diamond over triangle, etc. if ((unsigned)C1->Kind < (unsigned)C2->Kind) return true; @@ -217,6 +219,9 @@ namespace { char IfConverter::ID = 0; } +static RegisterPass +X("if-converter", "If Converter"); + FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } bool IfConverter::runOnMachineFunction(MachineFunction &MF) { @@ -224,22 +229,21 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { TII = MF.getTarget().getInstrInfo(); if (!TII) return false; - static int FnNum = -1; - DOUT << "\nIfcvt: function (" << ++FnNum << ") \'" - << MF.getFunction()->getName() << "\'"; + DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'" + << MF.getFunction()->getName() << "\'"); if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) { - DOUT << " skipped\n"; + DEBUG(dbgs() << " skipped\n"); return false; } - DOUT << "\n"; + DEBUG(dbgs() << "\n"); MF.RenumberBlocks(); BBAnalysis.resize(MF.getNumBlockIDs()); // Look for root nodes, i.e. blocks without successors. for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) - if (I->succ_size() == 0) + if (I->succ_empty()) Roots.push_back(I); std::vector Tokens; @@ -247,14 +251,18 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds; while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) { - // Do an intial analysis for each basic block and finding all the potential - // candidates to perform if-convesion. + // Do an initial analysis for each basic block and find all the potential + // candidates to perform if-conversion. bool Change = AnalyzeBlocks(MF, Tokens); while (!Tokens.empty()) { IfcvtToken *Token = Tokens.back(); Tokens.pop_back(); BBInfo &BBI = Token->BBI; IfcvtKind Kind = Token->Kind; + unsigned NumDups = Token->NumDups; + unsigned NumDups2 = Token->NumDups2; + + delete Token; // If the block has been evicted out of the queue or it has already been // marked dead (due to it being predicated), then skip it. @@ -273,16 +281,17 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { case ICSimpleFalse: { bool isFalse = Kind == ICSimpleFalse; if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break; - DOUT << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"") - << "): BB#" << BBI.BB->getNumber() << " (" - << ((Kind == ICSimpleFalse) - ? BBI.FalseBB->getNumber() - : BBI.TrueBB->getNumber()) << ") "; + DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"") + << "): BB#" << BBI.BB->getNumber() << " (" + << ((Kind == ICSimpleFalse) + ? BBI.FalseBB->getNumber() + : BBI.TrueBB->getNumber()) << ") "); RetVal = IfConvertSimple(BBI, Kind); - DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; - if (RetVal) + DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); + if (RetVal) { if (isFalse) NumSimpleFalse++; else NumSimple++; + } break; } case ICTriangle: @@ -295,16 +304,16 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { if (DisableTriangleR && !isFalse && isRev) break; if (DisableTriangleF && isFalse && !isRev) break; if (DisableTriangleFR && isFalse && isRev) break; - DOUT << "Ifcvt (Triangle"; + DEBUG(dbgs() << "Ifcvt (Triangle"); if (isFalse) - DOUT << " false"; + DEBUG(dbgs() << " false"); if (isRev) - DOUT << " rev"; - DOUT << "): BB#" << BBI.BB->getNumber() << " (T:" - << BBI.TrueBB->getNumber() << ",F:" - << BBI.FalseBB->getNumber() << ") "; + DEBUG(dbgs() << " rev"); + DEBUG(dbgs() << "): BB#" << BBI.BB->getNumber() << " (T:" + << BBI.TrueBB->getNumber() << ",F:" + << BBI.FalseBB->getNumber() << ") "); RetVal = IfConvertTriangle(BBI, Kind); - DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; + DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); if (RetVal) { if (isFalse) { if (isRev) NumTriangleFRev++; @@ -318,11 +327,11 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { } case ICDiamond: { if (DisableDiamond) break; - DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:" - << BBI.TrueBB->getNumber() << ",F:" - << BBI.FalseBB->getNumber() << ") "; - RetVal = IfConvertDiamond(BBI, Kind, Token->NumDups, Token->NumDups2); - DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; + DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:" + << BBI.TrueBB->getNumber() << ",F:" + << BBI.FalseBB->getNumber() << ") "); + RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2); + DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); if (RetVal) NumDiamonds++; break; } @@ -352,6 +361,13 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { Roots.clear(); BBAnalysis.clear(); + if (MadeChange) { + BranchFolder BF(false); + BF.OptimizeFunction(MF, TII, + MF.getTarget().getRegisterInfo(), + getAnalysisIfAvailable()); + } + return MadeChange; } @@ -369,7 +385,7 @@ static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, } /// ReverseBranchCondition - Reverse the condition of the end of the block -/// branchs. Swap block's 'true' and 'false' successors. +/// branch. Swap block's 'true' and 'false' successors. bool IfConverter::ReverseBranchCondition(BBInfo &BBI) { if (!TII->ReverseBranchCondition(BBI.BrCond)) { TII->RemoveBranch(*BBI.BB); @@ -430,8 +446,8 @@ bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, unsigned Size = TrueBBI.NonPredSize; if (TrueBBI.IsBrAnalyzable) { - if (TrueBBI.TrueBB && TrueBBI.BrCond.size() == 0) - // End with an unconditional branch. It will be removed. + if (TrueBBI.TrueBB && TrueBBI.BrCond.empty()) + // Ends with an unconditional branch. It will be removed. --Size; else { MachineBasicBlock *FExit = FalseBranch @@ -462,8 +478,7 @@ MachineBasicBlock::iterator firstNonBranchInst(MachineBasicBlock *BB, MachineBasicBlock::iterator I = BB->end(); while (I != BB->begin()) { --I; - const TargetInstrDescriptor *TID = I->getInstrDescriptor(); - if ((TID->Flags & M_BRANCH_FLAG) == 0) + if (!I->getDesc().isBranch()) break; } return I; @@ -522,7 +537,7 @@ bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, /// ScanInstructions - Scan all the instructions in the block to determine if /// the block is predicable. In most cases, that means all the instructions -/// in the block has M_PREDICABLE flag. Also checks if the block contains any +/// in the block are isPredicable(). Also checks if the block contains any /// instruction which can clobber a predicate (e.g. condition code register). /// If so, the block is not predicable unless it's the last instruction. void IfConverter::ScanInstructions(BBInfo &BBI) { @@ -542,22 +557,24 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { // fallthrough. if (!BBI.FalseBB) BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB); - assert(BBI.FalseBB && "Expected to find the fallthrough block!"); + if (!BBI.FalseBB) { + // Malformed bcc? True and false blocks are the same? + BBI.IsUnpredicable = true; + return; + } } // Then scan all the instructions. BBI.NonPredSize = 0; BBI.ClobbersPred = false; - bool SeenCondBr = false; for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); I != E; ++I) { - const TargetInstrDescriptor *TID = I->getInstrDescriptor(); - if ((TID->Flags & M_NOT_DUPLICABLE) != 0) + const TargetInstrDesc &TID = I->getDesc(); + if (TID.isNotDuplicable()) BBI.CannotBeCopied = true; bool isPredicated = TII->isPredicated(I); - bool isCondBr = BBI.IsBrAnalyzable && - (TID->Flags & M_BRANCH_FLAG) != 0 && (TID->Flags & M_BARRIER_FLAG) == 0; + bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch(); if (!isCondBr) { if (!isPredicated) @@ -569,16 +586,13 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { BBI.IsUnpredicable = true; return; } - } if (BBI.ClobbersPred && !isPredicated) { // Predicate modification instruction should end the block (except for // already predicated instructions and end of block branches). if (isCondBr) { - SeenCondBr = true; - - // Conditional branches is not predicable. But it may be eliminated. + // A conditional branch is not predicable, but it may be eliminated. continue; } @@ -588,10 +602,13 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { return; } - if (TID->Flags & M_CLOBBERS_PRED) + // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are + // still potentially predicable. + std::vector PredDefs; + if (TII->DefinesPredicate(I, PredDefs)) BBI.ClobbersPred = true; - if ((TID->Flags & M_PREDICABLE) == 0) { + if (!TII->isPredicable(I)) { BBI.IsUnpredicable = true; return; } @@ -601,7 +618,7 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { /// FeasibilityAnalysis - Determine if the block is a suitable candidate to be /// predicated by the specified predicate. bool IfConverter::FeasibilityAnalysis(BBInfo &BBI, - std::vector &Pred, + SmallVectorImpl &Pred, bool isTriangle, bool RevBranch) { // If the block is dead or unpredicable, then it cannot be predicated. if (BBI.IsDone || BBI.IsUnpredicable) @@ -616,9 +633,9 @@ bool IfConverter::FeasibilityAnalysis(BBInfo &BBI, if (!isTriangle) return false; - // Test predicate subsumsion. - std::vector RevPred(Pred); - std::vector Cond(BBI.BrCond); + // Test predicate subsumption. + SmallVector RevPred(Pred.begin(), Pred.end()); + SmallVector Cond(BBI.BrCond.begin(), BBI.BrCond.end()); if (RevBranch) { if (TII->ReverseBranchCondition(Cond)) return false; @@ -646,8 +663,8 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, ScanInstructions(BBI); - // Unanalyable or ends with fallthrough or unconditional branch. - if (!BBI.IsBrAnalyzable || BBI.BrCond.size() == 0) { + // Unanalyzable or ends with fallthrough or unconditional branch. + if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) { BBI.IsBeingAnalyzed = false; BBI.IsAnalyzed = true; return BBI; @@ -660,6 +677,13 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, return BBI; } + // Do not ifcvt if true and false fallthrough blocks are the same. + if (!BBI.FalseBB) { + BBI.IsBeingAnalyzed = false; + BBI.IsAnalyzed = true; + return BBI; + } + BBInfo &TrueBBI = AnalyzeBlock(BBI.TrueBB, Tokens); BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens); @@ -669,7 +693,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, return BBI; } - std::vector RevCond(BBI.BrCond); + SmallVector RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); bool CanRevCond = !TII->ReverseBranchCondition(RevCond); unsigned Dups = 0; @@ -812,7 +836,7 @@ void IfConverter::InvalidatePreds(MachineBasicBlock *BB) { /// static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, const TargetInstrInfo *TII) { - std::vector NoCond; + SmallVector NoCond; TII->InsertBranch(*BB, ToBB, NULL, NoCond); } @@ -820,7 +844,7 @@ static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, /// successors. void IfConverter::RemoveExtraEdges(BBInfo &BBI) { MachineBasicBlock *TBB = NULL, *FBB = NULL; - std::vector Cond; + SmallVector Cond; if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond)) BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); } @@ -833,7 +857,7 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { BBInfo *CvtBBI = &TrueBBI; BBInfo *NextBBI = &FalseBBI; - std::vector Cond(BBI.BrCond); + SmallVector Cond(BBI.BrCond.begin(), BBI.BrCond.end()); if (Kind == ICSimpleFalse) std::swap(CvtBBI, NextBBI); @@ -846,11 +870,12 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { } if (Kind == ICSimpleFalse) - TII->ReverseBranchCondition(Cond); + if (TII->ReverseBranchCondition(Cond)) + assert(false && "Unable to reverse branch condition!"); if (CvtBBI->BB->pred_size() > 1) { BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); - // Copy instructions in the true block, predicate them add them to + // Copy instructions in the true block, predicate them, and add them to // the entry block. CopyAndPredicateBlock(BBI, *CvtBBI, Cond); } else { @@ -898,7 +923,7 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { BBInfo *CvtBBI = &TrueBBI; BBInfo *NextBBI = &FalseBBI; - std::vector Cond(BBI.BrCond); + SmallVector Cond(BBI.BrCond.begin(), BBI.BrCond.end()); if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) std::swap(CvtBBI, NextBBI); @@ -911,21 +936,23 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { } if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) - TII->ReverseBranchCondition(Cond); + if (TII->ReverseBranchCondition(Cond)) + assert(false && "Unable to reverse branch condition!"); if (Kind == ICTriangleRev || Kind == ICTriangleFRev) { - ReverseBranchCondition(*CvtBBI); - // BB has been changed, modify its predecessors (except for this - // one) so they don't get ifcvt'ed based on bad intel. - for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(), - E = CvtBBI->BB->pred_end(); PI != E; ++PI) { - MachineBasicBlock *PBB = *PI; - if (PBB == BBI.BB) - continue; - BBInfo &PBBI = BBAnalysis[PBB->getNumber()]; - if (PBBI.IsEnqueued) { - PBBI.IsAnalyzed = false; - PBBI.IsEnqueued = false; + if (ReverseBranchCondition(*CvtBBI)) { + // BB has been changed, modify its predecessors (except for this + // one) so they don't get ifcvt'ed based on bad intel. + for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(), + E = CvtBBI->BB->pred_end(); PI != E; ++PI) { + MachineBasicBlock *PBB = *PI; + if (PBB == BBI.BB) + continue; + BBInfo &PBBI = BBAnalysis[PBB->getNumber()]; + if (PBBI.IsEnqueued) { + PBBI.IsAnalyzed = false; + PBBI.IsEnqueued = false; + } } } } @@ -934,16 +961,14 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { bool DupBB = CvtBBI->BB->pred_size() > 1; if (DupBB) { BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); - // Copy instructions in the true block, predicate them add them to + // Copy instructions in the true block, predicate them, and add them to // the entry block. CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true); } else { // Predicate the 'true' block after removing its branch. CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond); - } - if (!DupBB) { // Now merge the entry of the triangle with the true block. BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); MergeBlocks(BBI, *CvtBBI); @@ -951,7 +976,8 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { // If 'true' block has a 'false' successor, add an exit branch to it. if (HasEarlyExit) { - std::vector RevCond(CvtBBI->BrCond); + SmallVector RevCond(CvtBBI->BrCond.begin(), + CvtBBI->BrCond.end()); if (TII->ReverseBranchCondition(RevCond)) assert(false && "Unable to reverse branch condition!"); TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond); @@ -959,7 +985,7 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { } // Merge in the 'false' block if the 'false' block has no other - // predecessors. Otherwise, add a unconditional branch from to 'false'. + // predecessors. Otherwise, add an unconditional branch to 'false'. bool FalseBBDead = false; bool IterIfcvt = true; bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB); @@ -1001,7 +1027,7 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; MachineBasicBlock *TailBB = TrueBBI.TrueBB; - // True block must fall through or ended with unanalyzable terminator. + // True block must fall through or end with an unanalyzable terminator. if (!TailBB) { if (blockAlwaysFallThrough(TrueBBI)) TailBB = FalseBBI.TrueBB; @@ -1023,10 +1049,11 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, // block would clobber the predicate, in that case, do the opposite. BBInfo *BBI1 = &TrueBBI; BBInfo *BBI2 = &FalseBBI; - std::vector RevCond(BBI.BrCond); - TII->ReverseBranchCondition(RevCond); - std::vector *Cond1 = &BBI.BrCond; - std::vector *Cond2 = &RevCond; + SmallVector RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); + if (TII->ReverseBranchCondition(RevCond)) + assert(false && "Unable to reverse branch condition!"); + SmallVector *Cond1 = &BBI.BrCond; + SmallVector *Cond2 = &RevCond; // Figure out the more profitable ordering. bool DoSwap = false; @@ -1078,8 +1105,8 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, MergeBlocks(BBI, *BBI1); MergeBlocks(BBI, *BBI2); - // If the if-converted block fallthrough or unconditionally branch into the - // tail block, and the tail block does not have other predecessors, then + // If the if-converted block falls through or unconditionally branches into + // the tail block, and the tail block does not have other predecessors, then // fold the tail block in as well. Otherwise, unless it falls through to the // tail, add a unconditional branch to it. if (TailBB) { @@ -1108,13 +1135,15 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, /// specified end with the specified condition. void IfConverter::PredicateBlock(BBInfo &BBI, MachineBasicBlock::iterator E, - std::vector &Cond) { + SmallVectorImpl &Cond) { for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) { if (TII->isPredicated(I)) continue; if (!TII->PredicateInstruction(I, Cond)) { - cerr << "Unable to predicate " << *I << "!\n"; - abort(); +#ifndef NDEBUG + dbgs() << "Unable to predicate " << *I << "!\n"; +#endif + llvm_unreachable(0); } } @@ -1129,24 +1158,28 @@ void IfConverter::PredicateBlock(BBInfo &BBI, /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to /// the destination block. Skip end of block branches if IgnoreBr is true. void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, - std::vector &Cond, + SmallVectorImpl &Cond, bool IgnoreBr) { + MachineFunction &MF = *ToBBI.BB->getParent(); + for (MachineBasicBlock::iterator I = FromBBI.BB->begin(), E = FromBBI.BB->end(); I != E; ++I) { - const TargetInstrDescriptor *TID = I->getInstrDescriptor(); + const TargetInstrDesc &TID = I->getDesc(); bool isPredicated = TII->isPredicated(I); // Do not copy the end of the block branches. - if (IgnoreBr && !isPredicated && (TID->Flags & M_BRANCH_FLAG) != 0) + if (IgnoreBr && !isPredicated && TID.isBranch()) break; - MachineInstr *MI = I->clone(); + MachineInstr *MI = MF.CloneMachineInstr(I); ToBBI.BB->insert(ToBBI.BB->end(), MI); ToBBI.NonPredSize++; if (!isPredicated) if (!TII->PredicateInstruction(MI, Cond)) { - cerr << "Unable to predicate " << *MI << "!\n"; - abort(); +#ifndef NDEBUG + dbgs() << "Unable to predicate " << *I << "!\n"; +#endif + llvm_unreachable(0); } } @@ -1160,8 +1193,7 @@ void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, // Fallthrough edge can't be transferred. if (Succ == FallThrough) continue; - if (!ToBBI.BB->isSuccessor(Succ)) - ToBBI.BB->addSuccessor(Succ); + ToBBI.BB->addSuccessor(Succ); } std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), @@ -1201,11 +1233,10 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) { if (Succ == FallThrough) continue; FromBBI.BB->removeSuccessor(Succ); - if (!ToBBI.BB->isSuccessor(Succ)) - ToBBI.BB->addSuccessor(Succ); + ToBBI.BB->addSuccessor(Succ); } - // Now FromBBI always fall through to the next block! + // Now FromBBI always falls through to the next block! if (NBB && !FromBBI.BB->isSuccessor(NBB)) FromBBI.BB->addSuccessor(NBB);