[InlineCost] Improve the cost heuristic for Switch
Summary:
The motivation example is like below which has 13 cases but only 2 distinct targets
```
lor.lhs.false2: ; preds = %if.then
switch i32 %Status, label %if.then27 [
i32 -7012, label %if.end35
i32 -10008, label %if.end35
i32 -10016, label %if.end35
i32 15000, label %if.end35
i32 14013, label %if.end35
i32 10114, label %if.end35
i32 10107, label %if.end35
i32 10105, label %if.end35
i32 10013, label %if.end35
i32 10011, label %if.end35
i32 7008, label %if.end35
i32 7007, label %if.end35
i32 5002, label %if.end35
]
```
which is compiled into a balanced binary tree like this on AArch64 (similar on X86)
```
.LBB853_9: // %lor.lhs.false2
mov w8, #10012
cmp w19, w8
b.gt .LBB853_14
// BB#10: // %lor.lhs.false2
mov w8, #5001
cmp w19, w8
b.gt .LBB853_18
// BB#11: // %lor.lhs.false2
mov w8, #-10016
cmp w19, w8
b.eq .LBB853_23
// BB#12: // %lor.lhs.false2
mov w8, #-10008
cmp w19, w8
b.eq .LBB853_23
// BB#13: // %lor.lhs.false2
mov w8, #-7012
cmp w19, w8
b.eq .LBB853_23
b .LBB853_3
.LBB853_14: // %lor.lhs.false2
mov w8, #14012
cmp w19, w8
b.gt .LBB853_21
// BB#15: // %lor.lhs.false2
mov w8, #-10105
add w8, w19, w8
cmp w8, #9 // =9
b.hi .LBB853_17
// BB#16: // %lor.lhs.false2
orr w9, wzr, #0x1
lsl w8, w9, w8
mov w9, #517
and w8, w8, w9
cbnz w8, .LBB853_23
.LBB853_17: // %lor.lhs.false2
mov w8, #10013
cmp w19, w8
b.eq .LBB853_23
b .LBB853_3
.LBB853_18: // %lor.lhs.false2
mov w8, #-7007
add w8, w19, w8
cmp w8, #2 // =2
b.lo .LBB853_23
// BB#19: // %lor.lhs.false2
mov w8, #5002
cmp w19, w8
b.eq .LBB853_23
// BB#20: // %lor.lhs.false2
mov w8, #10011
cmp w19, w8
b.eq .LBB853_23
b .LBB853_3
.LBB853_21: // %lor.lhs.false2
mov w8, #14013
cmp w19, w8
b.eq .LBB853_23
// BB#22: // %lor.lhs.false2
mov w8, #15000
cmp w19, w8
b.ne .LBB853_3
```
However, the inline cost model estimates the cost to be linear with the number
of distinct targets and the cost of the above switch is just 2 InstrCosts.
The function containing this switch is then inlined about 900 times.
This change use the general way of switch lowering for the inline heuristic. It
etimate the number of case clusters with the suitability check for a jump table
or bit test. Considering the binary search tree built for the clusters, this
change modifies the model to be linear with the size of the balanced binary
tree. The model is off by default for now :
-inline-generic-switch-cost=false
This change was originally proposed by Haicheng in D29870.
Reviewers: hans, bmakam, chandlerc, eraman, haicheng, mcrosier
Reviewed By: hans
Subscribers: joerg, aemerson, llvm-commits, rengolin
Differential Revision: https://reviews.llvm.org/D31085
llvm-svn: 301649
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 07d5580..a9156d6 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -83,20 +83,6 @@
"for some float libcalls"),
cl::location(LimitFloatPrecision),
cl::init(0));
-
-/// Minimum jump table density for normal functions.
-static cl::opt<unsigned>
-JumpTableDensity("jump-table-density", cl::init(10), cl::Hidden,
- cl::desc("Minimum density for building a jump table in "
- "a normal function"));
-
-/// Minimum jump table density for -Os or -Oz functions.
-static cl::opt<unsigned>
-OptsizeJumpTableDensity("optsize-jump-table-density", cl::init(40), cl::Hidden,
- cl::desc("Minimum density for building a jump table in "
- "an optsize function"));
-
-
// Limit the width of DAG chains. This is important in general to prevent
// DAG-based analysis from blowing up. For example, alias analysis and
// load clustering may not complete in reasonable time. It is difficult to
@@ -8589,13 +8575,10 @@
HasTailCall = true;
}
-bool SelectionDAGBuilder::isDense(const CaseClusterVector &Clusters,
- const SmallVectorImpl<unsigned> &TotalCases,
- unsigned First, unsigned Last,
- unsigned Density) const {
+uint64_t
+SelectionDAGBuilder::getJumpTableRange(const CaseClusterVector &Clusters,
+ unsigned First, unsigned Last) const {
assert(Last >= First);
- assert(TotalCases[Last] >= TotalCases[First]);
-
const APInt &LowCase = Clusters[First].Low->getValue();
const APInt &HighCase = Clusters[Last].High->getValue();
assert(LowCase.getBitWidth() == HighCase.getBitWidth());
@@ -8604,26 +8587,17 @@
// comparison to lower. We should discriminate against such consecutive ranges
// in jump tables.
- uint64_t Diff = (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100);
- uint64_t Range = Diff + 1;
-
- uint64_t NumCases =
- TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]);
-
- assert(NumCases < UINT64_MAX / 100);
- assert(Range >= NumCases);
-
- return NumCases * 100 >= Range * Density;
+ return (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100) + 1;
}
-static inline bool areJTsAllowed(const TargetLowering &TLI,
- const SwitchInst *SI) {
- const Function *Fn = SI->getParent()->getParent();
- if (Fn->getFnAttribute("no-jump-tables").getValueAsString() == "true")
- return false;
-
- return TLI.isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
- TLI.isOperationLegalOrCustom(ISD::BRIND, MVT::Other);
+uint64_t SelectionDAGBuilder::getJumpTableNumCases(
+ const SmallVectorImpl<unsigned> &TotalCases, unsigned First,
+ unsigned Last) const {
+ assert(Last >= First);
+ assert(TotalCases[Last] >= TotalCases[First]);
+ uint64_t NumCases =
+ TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]);
+ return NumCases;
}
bool SelectionDAGBuilder::buildJumpTable(const CaseClusterVector &Clusters,
@@ -8662,10 +8636,11 @@
JTProbs[Clusters[I].MBB] += Clusters[I].Prob;
}
+ const TargetLowering &TLI = DAG.getTargetLoweringInfo();
unsigned NumDests = JTProbs.size();
- if (isSuitableForBitTests(NumDests, NumCmps,
- Clusters[First].Low->getValue(),
- Clusters[Last].High->getValue())) {
+ if (TLI.isSuitableForBitTests(
+ NumDests, NumCmps, Clusters[First].Low->getValue(),
+ Clusters[Last].High->getValue(), DAG.getDataLayout())) {
// Clusters[First..Last] should be lowered as bit tests instead.
return false;
}
@@ -8686,7 +8661,6 @@
}
JumpTableMBB->normalizeSuccProbs();
- const TargetLowering &TLI = DAG.getTargetLoweringInfo();
unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI.getJumpTableEncoding())
->createJumpTableIndex(Table);
@@ -8715,17 +8689,12 @@
#endif
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- if (!areJTsAllowed(TLI, SI))
+ if (!TLI.areJTsAllowed(SI->getParent()->getParent()))
return;
- const bool OptForSize = DefaultMBB->getParent()->getFunction()->optForSize();
-
const int64_t N = Clusters.size();
const unsigned MinJumpTableEntries = TLI.getMinimumJumpTableEntries();
const unsigned SmallNumberOfEntries = MinJumpTableEntries / 2;
- const unsigned MaxJumpTableSize =
- OptForSize || TLI.getMaximumJumpTableSize() == 0
- ? UINT_MAX : TLI.getMaximumJumpTableSize();
if (N < 2 || N < MinJumpTableEntries)
return;
@@ -8740,15 +8709,12 @@
TotalCases[i] += TotalCases[i - 1];
}
- const unsigned MinDensity =
- OptForSize ? OptsizeJumpTableDensity : JumpTableDensity;
-
// Cheap case: the whole range may be suitable for jump table.
- unsigned JumpTableSize = (Clusters[N - 1].High->getValue() -
- Clusters[0].Low->getValue())
- .getLimitedValue(UINT_MAX - 1) + 1;
- if (JumpTableSize <= MaxJumpTableSize &&
- isDense(Clusters, TotalCases, 0, N - 1, MinDensity)) {
+ uint64_t Range = getJumpTableRange(Clusters,0, N - 1);
+ uint64_t NumCases = getJumpTableNumCases(TotalCases, 0, N - 1);
+ assert(NumCases < UINT64_MAX / 100);
+ assert(Range >= NumCases);
+ if (TLI.isSuitableForJumpTable(SI, NumCases, Range)) {
CaseCluster JTCluster;
if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) {
Clusters[0] = JTCluster;
@@ -8801,11 +8767,11 @@
// Search for a solution that results in fewer partitions.
for (int64_t j = N - 1; j > i; j--) {
// Try building a partition from Clusters[i..j].
- JumpTableSize = (Clusters[j].High->getValue() -
- Clusters[i].Low->getValue())
- .getLimitedValue(UINT_MAX - 1) + 1;
- if (JumpTableSize <= MaxJumpTableSize &&
- isDense(Clusters, TotalCases, i, j, MinDensity)) {
+ uint64_t Range = getJumpTableRange(Clusters, i, j);
+ uint64_t NumCases = getJumpTableNumCases(TotalCases, i, j);
+ assert(NumCases < UINT64_MAX / 100);
+ assert(Range >= NumCases);
+ if (TLI.isSuitableForJumpTable(SI, NumCases, Range)) {
unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
unsigned Score = j == N - 1 ? 0 : PartitionsScore[j + 1];
int64_t NumEntries = j - i + 1;
@@ -8849,36 +8815,6 @@
Clusters.resize(DstIndex);
}
-bool SelectionDAGBuilder::rangeFitsInWord(const APInt &Low, const APInt &High) {
- // FIXME: Using the pointer type doesn't seem ideal.
- uint64_t BW = DAG.getDataLayout().getPointerSizeInBits();
- uint64_t Range = (High - Low).getLimitedValue(UINT64_MAX - 1) + 1;
- return Range <= BW;
-}
-
-bool SelectionDAGBuilder::isSuitableForBitTests(unsigned NumDests,
- unsigned NumCmps,
- const APInt &Low,
- const APInt &High) {
- // FIXME: I don't think NumCmps is the correct metric: a single case and a
- // range of cases both require only one branch to lower. Just looking at the
- // number of clusters and destinations should be enough to decide whether to
- // build bit tests.
-
- // To lower a range with bit tests, the range must fit the bitwidth of a
- // machine word.
- if (!rangeFitsInWord(Low, High))
- return false;
-
- // Decide whether it's profitable to lower this range with bit tests. Each
- // destination requires a bit test and branch, and there is an overall range
- // check branch. For a small number of clusters, separate comparisons might be
- // cheaper, and for many destinations, splitting the range might be better.
- return (NumDests == 1 && NumCmps >= 3) ||
- (NumDests == 2 && NumCmps >= 5) ||
- (NumDests == 3 && NumCmps >= 6);
-}
-
bool SelectionDAGBuilder::buildBitTests(CaseClusterVector &Clusters,
unsigned First, unsigned Last,
const SwitchInst *SI,
@@ -8900,16 +8836,17 @@
APInt High = Clusters[Last].High->getValue();
assert(Low.slt(High));
- if (!isSuitableForBitTests(NumDests, NumCmps, Low, High))
+ const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+ const DataLayout &DL = DAG.getDataLayout();
+ if (!TLI.isSuitableForBitTests(NumDests, NumCmps, Low, High, DL))
return false;
APInt LowBound;
APInt CmpRange;
- const int BitWidth = DAG.getTargetLoweringInfo()
- .getPointerTy(DAG.getDataLayout())
- .getSizeInBits();
- assert(rangeFitsInWord(Low, High) && "Case range must fit in bit mask!");
+ const int BitWidth = TLI.getPointerTy(DL).getSizeInBits();
+ assert(TLI.rangeFitsInWord(Low, High, DL) &&
+ "Case range must fit in bit mask!");
// Check if the clusters cover a contiguous range such that no value in the
// range will jump to the default statement.
@@ -8999,7 +8936,9 @@
// If target does not have legal shift left, do not emit bit tests at all.
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- EVT PTy = TLI.getPointerTy(DAG.getDataLayout());
+ const DataLayout &DL = DAG.getDataLayout();
+
+ EVT PTy = TLI.getPointerTy(DL);
if (!TLI.isOperationLegal(ISD::SHL, PTy))
return;
@@ -9030,8 +8969,8 @@
// Try building a partition from Clusters[i..j].
// Check the range.
- if (!rangeFitsInWord(Clusters[i].Low->getValue(),
- Clusters[j].High->getValue()))
+ if (!TLI.rangeFitsInWord(Clusters[i].Low->getValue(),
+ Clusters[j].High->getValue(), DL))
continue;
// Check nbr of destinations and cluster types.
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
index 128057d..9e99890 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
@@ -304,10 +304,13 @@
BranchProbability DefaultProb;
};
- /// Check whether a range of clusters is dense enough for a jump table.
- bool isDense(const CaseClusterVector &Clusters,
- const SmallVectorImpl<unsigned> &TotalCases,
- unsigned First, unsigned Last, unsigned MinDensity) const;
+ /// Return the range of value in [First..Last].
+ uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First,
+ unsigned Last) const;
+
+ /// Return the number of cases in [First..Last].
+ uint64_t getJumpTableNumCases(const SmallVectorImpl<unsigned> &TotalCases,
+ unsigned First, unsigned Last) const;
/// Build a jump table cluster from Clusters[First..Last]. Returns false if it
/// decides it's not a good idea.
@@ -319,14 +322,6 @@
void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
MachineBasicBlock *DefaultMBB);
- /// Check whether the range [Low,High] fits in a machine word.
- bool rangeFitsInWord(const APInt &Low, const APInt &High);
-
- /// Check whether these clusters are suitable for lowering with bit tests based
- /// on the number of destinations, comparison metric, and range.
- bool isSuitableForBitTests(unsigned NumDests, unsigned NumCmps,
- const APInt &Low, const APInt &High);
-
/// Build a bit test cluster from Clusters[First..Last]. Returns false if it
/// decides it's not a good idea.
bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
diff --git a/llvm/lib/CodeGen/TargetLoweringBase.cpp b/llvm/lib/CodeGen/TargetLoweringBase.cpp
index e579922..9b9f45f 100644
--- a/llvm/lib/CodeGen/TargetLoweringBase.cpp
+++ b/llvm/lib/CodeGen/TargetLoweringBase.cpp
@@ -53,6 +53,18 @@
("max-jump-table-size", cl::init(0), cl::Hidden,
cl::desc("Set maximum size of jump tables; zero for no limit."));
+/// Minimum jump table density for normal functions.
+static cl::opt<unsigned>
+ JumpTableDensity("jump-table-density", cl::init(10), cl::Hidden,
+ cl::desc("Minimum density for building a jump table in "
+ "a normal function"));
+
+/// Minimum jump table density for -Os or -Oz functions.
+static cl::opt<unsigned> OptsizeJumpTableDensity(
+ "optsize-jump-table-density", cl::init(40), cl::Hidden,
+ cl::desc("Minimum density for building a jump table in "
+ "an optsize function"));
+
// Although this default value is arbitrary, it is not random. It is assumed
// that a condition that evaluates the same way by a higher percentage than this
// is best represented as control flow. Therefore, the default value N should be
@@ -1901,6 +1913,10 @@
MinimumJumpTableEntries = Val;
}
+unsigned TargetLoweringBase::getMinimumJumpTableDensity(bool OptForSize) const {
+ return OptForSize ? OptsizeJumpTableDensity : JumpTableDensity;
+}
+
unsigned TargetLoweringBase::getMaximumJumpTableSize() const {
return MaximumJumpTableSize;
}