X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FIfConversion.cpp;h=db53b0473a9a9dfbb1b52a0f2c1b2d1ba3d699ad;hb=806562cc59ad35e6c742abe9109e9b8090b3f820;hp=ce3eda789131998d5b8dc84955741491a5665c77;hpb=2ad40d34947ced36d96f351f6c2a4d57a044e2a4;p=oota-llvm.git diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index ce3eda78913..db53b0473a9 100644 --- a/lib/CodeGen/IfConversion.cpp +++ b/lib/CodeGen/IfConversion.cpp @@ -28,6 +28,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" using namespace llvm; @@ -93,7 +94,8 @@ namespace { /// ClobbersPred - True if BB could modify predicates (e.g. has /// cmp, call, etc.) /// NonPredSize - Number of non-predicated instructions. - /// ExtraCost - Extra cost for microcoded instructions. + /// ExtraCost - Extra cost for multi-cycle instructions. + /// ExtraCost2 - Some instructions are slower when predicated /// BB - Corresponding MachineBasicBlock. /// TrueBB / FalseBB- See AnalyzeBranch(). /// BrCond - Conditions for end of block conditional branches. @@ -110,6 +112,7 @@ namespace { bool ClobbersPred : 1; unsigned NonPredSize; unsigned ExtraCost; + unsigned ExtraCost2; MachineBasicBlock *BB; MachineBasicBlock *TrueBB; MachineBasicBlock *FalseBB; @@ -119,7 +122,7 @@ namespace { IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false), HasFallThrough(false), IsUnpredicable(false), CannotBeCopied(false), ClobbersPred(false), NonPredSize(0), - ExtraCost(0), BB(0), TrueBB(0), FalseBB(0) {} + ExtraCost(0), ExtraCost2(0), BB(0), TrueBB(0), FalseBB(0) {} }; /// IfcvtToken - Record information about pending if-conversions to attempt: @@ -203,17 +206,20 @@ namespace { bool IgnoreBr = false); void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true); - bool MeetIfcvtSizeLimit(MachineBasicBlock &BB, unsigned Size, + bool MeetIfcvtSizeLimit(MachineBasicBlock &BB, + unsigned Cycle, unsigned Extra, float Prediction, float Confidence) const { - return Size > 0 && TII->isProfitableToIfCvt(BB, Size, - Prediction, Confidence); + return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra, + Prediction, Confidence); } - bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB, unsigned TSize, - MachineBasicBlock &FBB, unsigned FSize, + bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB, + unsigned TCycle, unsigned TExtra, + MachineBasicBlock &FBB, + unsigned FCycle, unsigned FExtra, float Prediction, float Confidence) const { - return TSize > 0 && FSize > 0 && - TII->isProfitableToIfCvt(TBB, TSize, FBB, FSize, + return TCycle > 0 && FCycle > 0 && + TII->isProfitableToIfCvt(TBB, TCycle, TExtra, FBB, FCycle, FExtra, Prediction, Confidence); } @@ -520,18 +526,6 @@ bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, return TExit && TExit == FalseBBI.BB; } -static -MachineBasicBlock::iterator firstNonBranchInst(MachineBasicBlock *BB, - const TargetInstrInfo *TII) { - MachineBasicBlock::iterator I = BB->end(); - while (I != BB->begin()) { - --I; - if (!I->getDesc().isBranch()) - break; - } - return I; -} - /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along /// with their common predecessor) forms a valid diamond shape for ifcvt. bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, @@ -560,64 +554,70 @@ bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)) return false; - MachineBasicBlock::iterator TI = TrueBBI.BB->begin(); - MachineBasicBlock::iterator FI = FalseBBI.BB->begin(); + // Count duplicate instructions at the beginning of the true and false blocks. + MachineBasicBlock::iterator TIB = TrueBBI.BB->begin(); + MachineBasicBlock::iterator FIB = FalseBBI.BB->begin(); MachineBasicBlock::iterator TIE = TrueBBI.BB->end(); MachineBasicBlock::iterator FIE = FalseBBI.BB->end(); - // Skip dbg_value instructions - while (TI != TIE && TI->isDebugValue()) - ++TI; - while (FI != FIE && FI->isDebugValue()) - ++FI; - while (TI != TIE && FI != FIE) { + while (TIB != TIE && FIB != FIE) { // Skip dbg_value instructions. These do not count. - if (TI->isDebugValue()) { - while (TI != TIE && TI->isDebugValue()) - ++TI; - if (TI == TIE) + if (TIB->isDebugValue()) { + while (TIB != TIE && TIB->isDebugValue()) + ++TIB; + if (TIB == TIE) break; } - if (FI->isDebugValue()) { - while (FI != FIE && FI->isDebugValue()) - ++FI; - if (FI == FIE) + if (FIB->isDebugValue()) { + while (FIB != FIE && FIB->isDebugValue()) + ++FIB; + if (FIB == FIE) break; } - if (!TI->isIdenticalTo(FI)) + if (!TIB->isIdenticalTo(FIB)) break; ++Dups1; - ++TI; - ++FI; + ++TIB; + ++FIB; } - TI = firstNonBranchInst(TrueBBI.BB, TII); - FI = firstNonBranchInst(FalseBBI.BB, TII); - MachineBasicBlock::iterator TIB = TrueBBI.BB->begin(); - MachineBasicBlock::iterator FIB = FalseBBI.BB->begin(); - // Skip dbg_value instructions at end of the bb's. - while (TI != TIB && TI->isDebugValue()) - --TI; - while (FI != FIB && FI->isDebugValue()) - --FI; - while (TI != TIB && FI != FIB) { + // Now, in preparation for counting duplicate instructions at the ends of the + // blocks, move the end iterators up past any branch instructions. + while (TIE != TIB) { + --TIE; + if (!TIE->getDesc().isBranch()) + break; + } + while (FIE != FIB) { + --FIE; + if (!FIE->getDesc().isBranch()) + break; + } + + // If Dups1 includes all of a block, then don't count duplicate + // instructions at the end of the blocks. + if (TIB == TIE || FIB == FIE) + return true; + + // Count duplicate instructions at the ends of the blocks. + while (TIE != TIB && FIE != FIB) { // Skip dbg_value instructions. These do not count. - if (TI->isDebugValue()) { - while (TI != TIB && TI->isDebugValue()) - --TI; - if (TI == TIB) + if (TIE->isDebugValue()) { + while (TIE != TIB && TIE->isDebugValue()) + --TIE; + if (TIE == TIB) break; } - if (FI->isDebugValue()) { - while (FI != FIB && FI->isDebugValue()) - --FI; - if (FI == FIB) + if (FIE->isDebugValue()) { + while (FIE != FIB && FIE->isDebugValue()) + --FIE; + if (FIE == FIB) break; } - if (!TI->isIdenticalTo(FI)) + if (!TIE->isIdenticalTo(FIE)) break; ++Dups2; - --TI; - --FI; + --TIE; + --FIE; } return true; @@ -655,6 +655,7 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { // Then scan all the instructions. BBI.NonPredSize = 0; BBI.ExtraCost = 0; + BBI.ExtraCost2 = 0; BBI.ClobbersPred = false; for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); I != E; ++I) { @@ -671,9 +672,12 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { if (!isCondBr) { if (!isPredicated) { BBI.NonPredSize++; - unsigned NumOps = TII->getNumMicroOps(&*I, InstrItins); - if (NumOps > 1) - BBI.ExtraCost += NumOps-1; + unsigned ExtraPredCost = 0; + unsigned NumCycles = TII->getInstrLatency(InstrItins, &*I, + &ExtraPredCost); + if (NumCycles > 1) + BBI.ExtraCost += NumCycles-1; + BBI.ExtraCost2 += ExtraPredCost; } else if (!AlreadyPredicated) { // FIXME: This instruction is already predicated before the // if-conversion pass. It's probably something like a conditional move. @@ -821,9 +825,9 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) && MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBI.NonPredSize - (Dups + Dups2) + - TrueBBI.ExtraCost), + TrueBBI.ExtraCost), TrueBBI.ExtraCost2, *FalseBBI.BB, (FalseBBI.NonPredSize - (Dups + Dups2) + - FalseBBI.ExtraCost), + FalseBBI.ExtraCost),FalseBBI.ExtraCost2, Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond) && FeasibilityAnalysis(FalseBBI, RevCond)) { @@ -842,7 +846,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction, Confidence) && MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost, - Prediction, Confidence) && + TrueBBI.ExtraCost2, Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) { // Triangle: // EBB @@ -857,7 +861,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction, Confidence) && MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost, - Prediction, Confidence) && + TrueBBI.ExtraCost2, Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) { Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups)); Enqueued = true; @@ -865,7 +869,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, if (ValidSimple(TrueBBI, Dups, Prediction, Confidence) && MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost, - Prediction, Confidence) && + TrueBBI.ExtraCost2, Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond)) { // Simple (split, no rejoin): // EBB @@ -884,7 +888,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, 1.0-Prediction, Confidence) && MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize + FalseBBI.ExtraCost, - 1.0-Prediction, Confidence) && + FalseBBI.ExtraCost2, 1.0-Prediction, Confidence) && FeasibilityAnalysis(FalseBBI, RevCond, true)) { Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups)); Enqueued = true; @@ -894,7 +898,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, 1.0-Prediction, Confidence) && MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize + FalseBBI.ExtraCost, - 1.0-Prediction, Confidence) && + FalseBBI.ExtraCost2, 1.0-Prediction, Confidence) && FeasibilityAnalysis(FalseBBI, RevCond, true, true)) { Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups)); Enqueued = true; @@ -903,7 +907,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, if (ValidSimple(FalseBBI, Dups, 1.0-Prediction, Confidence) && MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize + FalseBBI.ExtraCost, - 1.0-Prediction, Confidence) && + FalseBBI.ExtraCost2, 1.0-Prediction, Confidence) && FeasibilityAnalysis(FalseBBI, RevCond)) { Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups)); Enqueued = true; @@ -1433,9 +1437,11 @@ void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, MachineInstr *MI = MF.CloneMachineInstr(I); ToBBI.BB->insert(ToBBI.BB->end(), MI); ToBBI.NonPredSize++; - unsigned NumOps = TII->getNumMicroOps(MI, InstrItins); - if (NumOps > 1) - ToBBI.ExtraCost += NumOps-1; + unsigned ExtraPredCost = 0; + unsigned NumCycles = TII->getInstrLatency(InstrItins, &*I, &ExtraPredCost); + if (NumCycles > 1) + ToBBI.ExtraCost += NumCycles-1; + ToBBI.ExtraCost2 += ExtraPredCost; if (!TII->isPredicated(I) && !MI->isDebugValue()) { if (!TII->PredicateInstruction(MI, Cond)) { @@ -1510,8 +1516,10 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { ToBBI.NonPredSize += FromBBI.NonPredSize; ToBBI.ExtraCost += FromBBI.ExtraCost; + ToBBI.ExtraCost2 += FromBBI.ExtraCost2; FromBBI.NonPredSize = 0; FromBBI.ExtraCost = 0; + FromBBI.ExtraCost2 = 0; ToBBI.ClobbersPred |= FromBBI.ClobbersPred; ToBBI.HasFallThrough = FromBBI.HasFallThrough;