X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FIfConversion.cpp;h=fb53377b98ba0959468d0a9fca07bb1f77f003c0;hb=a9407f593778c3eff02dbb1fa11129865a59c6d3;hp=4b2eb621e32740797aff0de333dbb723662529d3;hpb=a1a878791b305880c976038b8fcd2697b7799ec1;p=oota-llvm.git diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index 4b2eb621e32..fb53377b98b 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. // //===----------------------------------------------------------------------===// // @@ -26,26 +26,24 @@ #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 +82,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. @@ -239,7 +237,7 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { // 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; @@ -399,6 +397,9 @@ bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const { if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) return false; + if (TrueBBI.IsBrAnalyzable) + return false; + if (TrueBBI.BB->pred_size() > 1) { if (TrueBBI.CannotBeCopied || TrueBBI.NonPredSize > TLI->getIfCvtDupBlockSizeLimit()) @@ -406,7 +407,7 @@ bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const { Dups = TrueBBI.NonPredSize; } - return !blockAlwaysFallThrough(TrueBBI) && TrueBBI.BrCond.size() == 0; + return true; } /// ValidTriangle - Returns true if the 'true' and 'false' blocks (along @@ -427,7 +428,7 @@ bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, unsigned Size = TrueBBI.NonPredSize; if (TrueBBI.IsBrAnalyzable) { - if (TrueBBI.TrueBB && TrueBBI.BrCond.size() == 0) + if (TrueBBI.TrueBB && TrueBBI.BrCond.empty()) // End with an unconditional branch. It will be removed. --Size; else { @@ -459,8 +460,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; @@ -486,11 +486,12 @@ bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, return false; if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable)) return false; - // FIXME: Allow false block to have an early exit? - if (TrueBBI.BB->pred_size() > 1 || - FalseBBI.BB->pred_size() > 1 || - TrueBBI.FalseBB || FalseBBI.FalseBB || - (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)) + if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) + return false; + + // FIXME: Allow true block to have an early exit? + if (TrueBBI.FalseBB || FalseBBI.FalseBB || + (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)) return false; MachineBasicBlock::iterator TI = TrueBBI.BB->begin(); @@ -518,13 +519,14 @@ 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) { if (BBI.IsDone) return; + bool AlreadyPredicated = BBI.Predicate.size() > 0; // First analyze the end of BB branches. BBI.TrueBB = BBI.FalseBB = NULL; BBI.BrCond.clear(); @@ -546,16 +548,25 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { bool SeenCondBr = false; for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); I != E; ++I) { - if (!BBI.CannotBeCopied && !TII->CanBeDuplicated(I)) + const TargetInstrDesc &TID = I->getDesc(); + if (TID.isNotDuplicable()) BBI.CannotBeCopied = true; - const TargetInstrDescriptor *TID = I->getInstrDescriptor(); bool isPredicated = TII->isPredicated(I); - bool isCondBr = BBI.IsBrAnalyzable && - (TID->Flags & M_BRANCH_FLAG) != 0 && (TID->Flags & M_BARRIER_FLAG) == 0; - - if (!isPredicated && !isCondBr) - BBI.NonPredSize++; + bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch(); + + if (!isCondBr) { + if (!isPredicated) + BBI.NonPredSize++; + else if (!AlreadyPredicated) { + // FIXME: This instruction is already predicated before the + // if-conversion pass. It's probably something like a conditional move. + // Mark this block unpredicable for now. + BBI.IsUnpredicable = true; + return; + } + + } if (BBI.ClobbersPred && !isPredicated) { // Predicate modification instruction should end the block (except for @@ -568,15 +579,18 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { } // Predicate may have been modified, the subsequent (currently) - // unpredocated instructions cannot be correctly predicated. + // unpredicated instructions cannot be correctly predicated. BBI.IsUnpredicable = true; 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 (!TID.isPredicable()) { BBI.IsUnpredicable = true; return; } @@ -632,7 +646,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, ScanInstructions(BBI); // Unanalyable or ends with fallthrough or unconditional branch. - if (!BBI.IsBrAnalyzable || BBI.BrCond.size() == 0) { + if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) { BBI.IsBeingAnalyzed = false; BBI.IsAnalyzed = true; return BBI; @@ -806,16 +820,8 @@ static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, void IfConverter::RemoveExtraEdges(BBInfo &BBI) { MachineBasicBlock *TBB = NULL, *FBB = NULL; std::vector Cond; - bool isAnalyzable = !TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond); - bool CanFallthrough = isAnalyzable && (TBB == NULL || FBB == NULL); - if (BBI.TrueBB && BBI.BB->isSuccessor(BBI.TrueBB)) - if (!(BBI.TrueBB == TBB || BBI.TrueBB == FBB || - (CanFallthrough && getNextBlock(BBI.BB) == BBI.TrueBB))) - BBI.BB->removeSuccessor(BBI.TrueBB); - if (BBI.FalseBB && BBI.BB->isSuccessor(BBI.FalseBB)) - if (!(BBI.FalseBB == TBB || BBI.FalseBB == FBB || - (CanFallthrough && getNextBlock(BBI.BB) == BBI.FalseBB))) - BBI.BB->removeSuccessor(BBI.FalseBB); + if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond)) + BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); } /// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG. @@ -936,23 +942,19 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { 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); + } + // If 'true' block has a 'false' successor, add an exit branch to it. if (HasEarlyExit) { std::vector RevCond(CvtBBI->BrCond); if (TII->ReverseBranchCondition(RevCond)) assert(false && "Unable to reverse branch condition!"); - if (DupBB) { - TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond); - BBI.BB->addSuccessor(CvtBBI->FalseBB); - } else { - TII->InsertBranch(*CvtBBI->BB, CvtBBI->FalseBB, NULL, RevCond); - } - } - - if (!DupBB) { - // Now merge the entry of the triangle with the true block. - BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); - MergeBlocks(BBI, *CvtBBI); + TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond); + BBI.BB->addSuccessor(CvtBBI->FalseBB); } // Merge in the 'false' block if the 'false' block has no other @@ -1024,25 +1026,18 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, TII->ReverseBranchCondition(RevCond); std::vector *Cond1 = &BBI.BrCond; std::vector *Cond2 = &RevCond; - bool NeedBr1 = BBI1->FalseBB != NULL; - bool NeedBr2 = BBI2->FalseBB != NULL; // Figure out the more profitable ordering. bool DoSwap = false; if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred) DoSwap = true; else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) { - if (!NeedBr1 && NeedBr2) + if (TrueBBI.NonPredSize > FalseBBI.NonPredSize) DoSwap = true; - else if (NeedBr1 == NeedBr2) { - if (TrueBBI.NonPredSize > FalseBBI.NonPredSize) - DoSwap = true; - } } if (DoSwap) { std::swap(BBI1, BBI2); std::swap(Cond1, Cond2); - std::swap(NeedBr1, NeedBr2); } // Remove the conditional branch from entry to the blocks. @@ -1069,10 +1064,6 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, BBI1->BB->erase(DI1, BBI1->BB->end()); PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1); - // Add an early exit branch if needed. - if (NeedBr1) - TII->InsertBranch(*BBI1->BB, BBI1->FalseBB, NULL, *Cond1); - // Predicate the 'false' block. BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB); DI2 = BBI2->BB->end(); @@ -1082,30 +1073,9 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, } PredicateBlock(*BBI2, DI2, *Cond2); - // Add an unconditional branch from 'false' to to 'false' successor if it - // will not be the fallthrough block. - if (NeedBr2 && !NeedBr1) { - // If BBI2 isn't going to be merged in, then the existing fallthrough - // or branch is fine. - if (!canFallThroughTo(BBI.BB, BBI2->FalseBB)) { - InsertUncondBranch(BBI2->BB, BBI2->FalseBB, TII); - BBI2->HasFallThrough = false; - } - } - - // Keep them as two separate blocks if there is an early exit. - if (!NeedBr1) - MergeBlocks(*BBI1, *BBI2); - - // Merge the combined block into the entry of the diamond. + // Merge the true block into the entry of the diamond. MergeBlocks(BBI, *BBI1); - - // 'True' and 'false' aren't combined, see if we need to add a unconditional - // branch to the 'false' block. - if (NeedBr1 && !canFallThroughTo(BBI.BB, BBI2->BB)) { - InsertUncondBranch(BBI.BB, BBI2->BB, TII); - BBI1->HasFallThrough = false; - } + 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 @@ -1113,19 +1083,13 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, // tail, add a unconditional branch to it. if (TailBB) { BBInfo TailBBI = BBAnalysis[TailBB->getNumber()]; - BBInfo *LastBBI = NeedBr1 ? BBI2 : &BBI; - bool HasEarlyExit = NeedBr1 ? NeedBr2 : false; - if (!HasEarlyExit && - TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) { - LastBBI->NonPredSize -= TII->RemoveBranch(*LastBBI->BB); - MergeBlocks(*LastBBI, TailBBI); + if (TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) { + BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); + MergeBlocks(BBI, TailBBI); TailBBI.IsDone = true; } else { - bool isFallThrough = canFallThroughTo(LastBBI->BB, TailBB); - if (!isFallThrough) { - InsertUncondBranch(LastBBI->BB, TailBB, TII); - LastBBI->HasFallThrough = false; - } + InsertUncondBranch(BBI.BB, TailBB, TII); + BBI.HasFallThrough = false; } } @@ -1168,10 +1132,10 @@ void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, bool IgnoreBr) { 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(); @@ -1185,6 +1149,20 @@ void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, } } + std::vector Succs(FromBBI.BB->succ_begin(), + FromBBI.BB->succ_end()); + MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); + MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL; + + for (unsigned i = 0, e = Succs.size(); i != e; ++i) { + MachineBasicBlock *Succ = Succs[i]; + // Fallthrough edge can't be transferred. + if (Succ == FallThrough) + continue; + if (!ToBBI.BB->isSuccessor(Succ)) + ToBBI.BB->addSuccessor(Succ); + } + std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), std::back_inserter(ToBBI.Predicate)); std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate)); @@ -1227,7 +1205,7 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) { } // Now FromBBI always fall through to the next block! - if (NBB) + if (NBB && !FromBBI.BB->isSuccessor(NBB)) FromBBI.BB->addSuccessor(NBB); std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),