aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorOwen Anderson <resistor@mac.com>2010-10-01 22:45:50 +0000
committerOwen Anderson <resistor@mac.com>2010-10-01 22:45:50 +0000
commite3cc84a43d6a4bb6c50f58f3dd8e60e28787509e (patch)
tree236f7bad5fd51f72f50409f3d67bf9dcda8c5388
parent6314ef9e8100c889956bd26ba71cc04e06564568 (diff)
downloadexternal_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.h15
-rw-r--r--lib/CodeGen/IfConversion.cpp62
-rw-r--r--lib/Target/ARM/ARMBaseInstrInfo.cpp9
-rw-r--r--lib/Target/ARM/ARMBaseInstrInfo.h8
-rw-r--r--lib/Target/ARM/Thumb2InstrInfo.cpp11
-rw-r--r--lib/Target/ARM/Thumb2InstrInfo.h4
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,