diff options
author | Owen Anderson <resistor@mac.com> | 2010-10-01 22:45:50 +0000 |
---|---|---|
committer | Owen Anderson <resistor@mac.com> | 2010-10-01 22:45:50 +0000 |
commit | e3cc84a43d6a4bb6c50f58f3dd8e60e28787509e (patch) | |
tree | 236f7bad5fd51f72f50409f3d67bf9dcda8c5388 | |
parent | 6314ef9e8100c889956bd26ba71cc04e06564568 (diff) | |
download | external_llvm-e3cc84a43d6a4bb6c50f58f3dd8e60e28787509e.zip external_llvm-e3cc84a43d6a4bb6c50f58f3dd8e60e28787509e.tar.gz external_llvm-e3cc84a43d6a4bb6c50f58f3dd8e60e28787509e.tar.bz2 |
Thread the determination of branch prediction hit rates back through the if-conversion heuristic APIs. For now,
stick with a constant estimate of 90% (branch predictors are good!), but we might find that we want to provide
more nuanced estimates in the future.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115364 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/Target/TargetInstrInfo.h | 15 | ||||
-rw-r--r-- | lib/CodeGen/IfConversion.cpp | 62 | ||||
-rw-r--r-- | lib/Target/ARM/ARMBaseInstrInfo.cpp | 9 | ||||
-rw-r--r-- | lib/Target/ARM/ARMBaseInstrInfo.h | 8 | ||||
-rw-r--r-- | lib/Target/ARM/Thumb2InstrInfo.cpp | 11 | ||||
-rw-r--r-- | lib/Target/ARM/Thumb2InstrInfo.h | 4 |
6 files changed, 67 insertions, 42 deletions
diff --git a/include/llvm/Target/TargetInstrInfo.h b/include/llvm/Target/TargetInstrInfo.h index 08e6a0e..0063dfc 100644 --- a/include/llvm/Target/TargetInstrInfo.h +++ b/include/llvm/Target/TargetInstrInfo.h @@ -305,10 +305,11 @@ public: /// isProfitableToIfCvt - Return true if it's profitable to first "NumInstrs" /// of the specified basic block, where the probability of the instructions - /// being executed is given by Probability. + /// being executed is given by Probability, and Confidence is a measure + /// of our confidence that it will be properly predicted. virtual bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumInstrs, - float Probability) const { + float Probability, float Confidence) const { return false; } @@ -316,21 +317,23 @@ public: /// checks for the case where two basic blocks from true and false path /// of a if-then-else (diamond) are predicated on mutally exclusive /// predicates, where the probability of the true path being taken is given - /// by Probability. + /// by Probability, and Confidence is a measure of our confidence that it + /// will be properly predicted. virtual bool isProfitableToIfCvt(MachineBasicBlock &TMBB, unsigned NumTInstrs, MachineBasicBlock &FMBB, unsigned NumFInstrs, - float Probability) const { + float Probability, float Confidence) const { return false; } /// isProfitableToDupForIfCvt - Return true if it's profitable for /// if-converter to duplicate a specific number of instructions in the /// specified MBB to enable if-conversion, where the probability of the - /// instructions being executed is given by Probability. + /// instructions being executed is given by Probability, and Confidence is + /// a measure of our confidence that it will be properly predicted. virtual bool isProfitableToDupForIfCvt(MachineBasicBlock &MBB, unsigned NumInstrs, - float Probability) const { + float Probability, float Confidence) const { return false; } diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index bd65a44..bf4175c 100644 --- a/lib/CodeGen/IfConversion.cpp +++ b/lib/CodeGen/IfConversion.cpp @@ -170,9 +170,11 @@ namespace { private: bool ReverseBranchCondition(BBInfo &BBI); - bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups, float Prediction) const; + bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups, + float Prediction, float Confidence) const; bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, - bool FalseBranch, unsigned &Dups) const; + bool FalseBranch, unsigned &Dups, + float Prediction, float Confidence) const; bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, unsigned &Dups1, unsigned &Dups2) const; void ScanInstructions(BBInfo &BBI); @@ -198,15 +200,17 @@ namespace { void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true); bool MeetIfcvtSizeLimit(MachineBasicBlock &BB, unsigned Size, - float Prediction) const { - return Size > 0 && TII->isProfitableToIfCvt(BB, Size, Prediction); + float Prediction, float Confidence) const { + return Size > 0 && TII->isProfitableToIfCvt(BB, Size, + Prediction, Confidence); } bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB, unsigned TSize, MachineBasicBlock &FBB, unsigned FSize, - float Prediction) const { + float Prediction, float Confidence) const { return TSize > 0 && FSize > 0 && - TII->isProfitableToIfCvt(TBB, TSize, FBB, FSize, Prediction); + TII->isProfitableToIfCvt(TBB, TSize, FBB, FSize, + Prediction, Confidence); } // blockAlwaysFallThrough - Block ends without a terminator. @@ -445,7 +449,7 @@ static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) { /// number of instructions that the ifcvt would need to duplicate if performed /// in Dups. bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups, - float Prediction) const { + float Prediction, float Confidence) const { Dups = 0; if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) return false; @@ -456,7 +460,7 @@ bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups, if (TrueBBI.BB->pred_size() > 1) { if (TrueBBI.CannotBeCopied || !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize, - Prediction)) + Prediction, Confidence)) return false; Dups = TrueBBI.NonPredSize; } @@ -471,7 +475,8 @@ bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups, /// returns the number of instructions that the ifcvt would need to duplicate /// if performed in 'Dups'. bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, - bool FalseBranch, unsigned &Dups) const { + bool FalseBranch, unsigned &Dups, + float Prediction, float Confidence) const { Dups = 0; if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) return false; @@ -493,7 +498,8 @@ bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, ++Size; } } - if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size, 0.5)) + if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size, + Prediction, Confidence)) return false; Dups = Size; } @@ -786,7 +792,9 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, // General heuristics are: // - backedge -> 90% taken // - early exit -> 20% taken + // - branch predictor confidence -> 90% float Prediction = 0.5f; + float Confidence = 0.9f; MachineLoop *Loop = MLI->getLoopFor(BB); if (Loop) { if (TrueBBI.BB == Loop->getHeader()) @@ -805,7 +813,7 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) && MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize - (Dups + Dups2), *FalseBBI.BB, FalseBBI.NonPredSize - (Dups + Dups2), - Prediction) && + Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond) && FeasibilityAnalysis(FalseBBI, RevCond)) { // Diamond: @@ -821,8 +829,9 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, Enqueued = true; } - if (ValidTriangle(TrueBBI, FalseBBI, false, Dups) && - MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize, Prediction) && + if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction, Confidence) && + MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize, + Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) { // Triangle: // EBB @@ -835,15 +844,17 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, Enqueued = true; } - if (ValidTriangle(TrueBBI, FalseBBI, true, Dups) && - MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize, Prediction) && + if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction, Confidence) && + MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize, + Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) { Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups)); Enqueued = true; } - if (ValidSimple(TrueBBI, Dups, Prediction) && - MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize, Prediction) && + if (ValidSimple(TrueBBI, Dups, Prediction, Confidence) && + MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize, + Prediction, Confidence) && FeasibilityAnalysis(TrueBBI, BBI.BrCond)) { // Simple (split, no rejoin): // EBB @@ -858,22 +869,27 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, if (CanRevCond) { // Try the other path... - if (ValidTriangle(FalseBBI, TrueBBI, false, Dups) && - MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize,1.0-Prediction) && + if (ValidTriangle(FalseBBI, TrueBBI, false, Dups, + 1.0-Prediction, Confidence) && + MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize, + 1.0-Prediction, Confidence) && FeasibilityAnalysis(FalseBBI, RevCond, true)) { Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups)); Enqueued = true; } - if (ValidTriangle(FalseBBI, TrueBBI, true, Dups) && - MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize,1.0-Prediction) && + if (ValidTriangle(FalseBBI, TrueBBI, true, Dups, + 1.0-Prediction, Confidence) && + MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize, + 1.0-Prediction, Confidence) && FeasibilityAnalysis(FalseBBI, RevCond, true, true)) { Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups)); Enqueued = true; } - if (ValidSimple(FalseBBI, Dups, 1.0-Prediction) && - MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize,1.0-Prediction) && + if (ValidSimple(FalseBBI, Dups, 1.0-Prediction, Confidence) && + MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize, + 1.0-Prediction, Confidence) && FeasibilityAnalysis(FalseBBI, RevCond)) { Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups)); Enqueued = true; diff --git a/lib/Target/ARM/ARMBaseInstrInfo.cpp b/lib/Target/ARM/ARMBaseInstrInfo.cpp index 9a904cd..6034b4a 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.cpp +++ b/lib/Target/ARM/ARMBaseInstrInfo.cpp @@ -1201,7 +1201,8 @@ bool ARMBaseInstrInfo::isSchedulingBoundary(const MachineInstr *MI, bool ARMBaseInstrInfo::isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumInstrs, - float Probability) const { + float Probability, + float Confidence) const { if (!NumInstrs) return false; @@ -1218,7 +1219,7 @@ bool ARMBaseInstrInfo::isProfitableToIfCvt(MachineBasicBlock &MBB, // Attempt to estimate the relative costs of predication versus branching. float UnpredCost = Probability * NumInstrs; UnpredCost += 1.0; // The branch itself - UnpredCost += 0.1 * Subtarget.getMispredictionPenalty(); + UnpredCost += (1.0 - Confidence) * Subtarget.getMispredictionPenalty(); float PredCost = NumInstrs; @@ -1229,7 +1230,7 @@ bool ARMBaseInstrInfo::isProfitableToIfCvt(MachineBasicBlock &MBB, bool ARMBaseInstrInfo:: isProfitableToIfCvt(MachineBasicBlock &TMBB, unsigned NumT, MachineBasicBlock &FMBB, unsigned NumF, - float Probability) const { + float Probability, float Confidence) const { // Use old-style if-conversion heuristics if (OldARMIfCvt) { return NumT && NumF && NumT <= 2 && NumF <= 2; @@ -1241,7 +1242,7 @@ isProfitableToIfCvt(MachineBasicBlock &TMBB, unsigned NumT, // Attempt to estimate the relative costs of predication versus branching. float UnpredCost = Probability * NumT + (1.0 - Probability) * NumF; UnpredCost += 1.0; // The branch itself - UnpredCost += 0.1 * Subtarget.getMispredictionPenalty(); + UnpredCost += (1.0 - Confidence) * Subtarget.getMispredictionPenalty(); float PredCost = NumT + NumF; diff --git a/lib/Target/ARM/ARMBaseInstrInfo.h b/lib/Target/ARM/ARMBaseInstrInfo.h index f6800bb..fbe5fe8 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.h +++ b/lib/Target/ARM/ARMBaseInstrInfo.h @@ -312,15 +312,17 @@ public: const MachineFunction &MF) const; virtual bool isProfitableToIfCvt(MachineBasicBlock &MBB, - unsigned NumInstrs, float Prob) const; + unsigned NumInstrs, + float Prob, float Confidence) const; virtual bool isProfitableToIfCvt(MachineBasicBlock &TMBB,unsigned NumT, MachineBasicBlock &FMBB,unsigned NumF, - float Probability) const; + float Probability, float Confidence) const; virtual bool isProfitableToDupForIfCvt(MachineBasicBlock &MBB, unsigned NumInstrs, - float Probability) const { + float Probability, + float Confidence) const { return NumInstrs && NumInstrs == 1; } diff --git a/lib/Target/ARM/Thumb2InstrInfo.cpp b/lib/Target/ARM/Thumb2InstrInfo.cpp index a79b4ae..0a0f314 100644 --- a/lib/Target/ARM/Thumb2InstrInfo.cpp +++ b/lib/Target/ARM/Thumb2InstrInfo.cpp @@ -44,19 +44,22 @@ unsigned Thumb2InstrInfo::getUnindexedOpcode(unsigned Opc) const { bool Thumb2InstrInfo::isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumInstrs, - float Prediction) const { + float Prediction, + float Confidence) const { if (!OldT2IfCvt) - return ARMBaseInstrInfo::isProfitableToIfCvt(MBB, NumInstrs, Prediction); + return ARMBaseInstrInfo::isProfitableToIfCvt(MBB, NumInstrs, + Prediction, Confidence); return NumInstrs && NumInstrs <= 3; } bool Thumb2InstrInfo:: isProfitableToIfCvt(MachineBasicBlock &TMBB, unsigned NumT, MachineBasicBlock &FMBB, unsigned NumF, - float Prediction) const { + float Prediction, float Confidence) const { if (!OldT2IfCvt) return ARMBaseInstrInfo::isProfitableToIfCvt(TMBB, NumT, - FMBB, NumF, Prediction); + FMBB, NumF, + Prediction, Confidence); // FIXME: Catch optimization such as: // r0 = movne diff --git a/lib/Target/ARM/Thumb2InstrInfo.h b/lib/Target/ARM/Thumb2InstrInfo.h index f9b1f32..b348ad0 100644 --- a/lib/Target/ARM/Thumb2InstrInfo.h +++ b/lib/Target/ARM/Thumb2InstrInfo.h @@ -39,10 +39,10 @@ public: MachineBasicBlock::iterator MBBI) const; bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumInstrs, - float Prediction) const; + float Prediction, float Confidence) const; bool isProfitableToIfCvt(MachineBasicBlock &TMBB, unsigned NumTInstrs, MachineBasicBlock &FMBB, unsigned NumFInstrs, - float Prediction) const; + float Prediction, float Confidence) const; void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, DebugLoc DL, |