Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -303,12 +303,9 @@ BranchProbability DefaultProb; }; - /// Minimum jump table density, in percent. - enum { MinJumpTableDensity = 40 }; - /// Check whether a range of clusters is dense enough for a jump table. bool isDense(const CaseClusterVector &Clusters, unsigned *TotalCases, - unsigned First, unsigned Last); + unsigned First, unsigned Last, unsigned Density); /// Build a jump table cluster from Clusters[First..Last]. Returns false if it /// decides it's not a good idea. Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -86,6 +86,19 @@ EnableFMFInDAG("enable-fmf-dag", cl::init(true), cl::Hidden, cl::desc("Enable fast-math-flags for DAG nodes")); +/// Minimum jump table density for normal +static cl::opt +SparseJumpTableDensity("sparse-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 +DenseJumpTableDensity("dense-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 @@ -7888,7 +7901,8 @@ bool SelectionDAGBuilder::isDense(const CaseClusterVector &Clusters, unsigned *TotalCases, unsigned First, - unsigned Last) { + unsigned Last, + unsigned Density) { assert(Last >= First); assert(TotalCases[Last] >= TotalCases[First]); @@ -7909,7 +7923,7 @@ assert(NumCases < UINT64_MAX / 100); assert(Range >= NumCases); - return NumCases * 100 >= Range * MinJumpTableDensity; + return NumCases * 100 >= Range * Density; } static inline bool areJTsAllowed(const TargetLowering &TLI) { @@ -8023,7 +8037,11 @@ TotalCases[i] += TotalCases[i - 1]; } - if (N >= MinJumpTableSize && isDense(Clusters, &TotalCases[0], 0, N - 1)) { + unsigned Density = SparseJumpTableDensity; + if (DefaultMBB->getParent()->getFunction()->optForSize()) + Density = DenseJumpTableDensity; + if (N >= MinJumpTableSize + && isDense(Clusters, &TotalCases[0], 0, N - 1, Density)) { // Cheap case: the whole range might be suitable for jump table. CaseCluster JTCluster; if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) { @@ -8068,7 +8086,7 @@ // 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]. - if (isDense(Clusters, &TotalCases[0], i, j)) { + if (isDense(Clusters, &TotalCases[0], i, j, Density)) { unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]); bool IsTable = j - i + 1 >= MinJumpTableSize; unsigned Tables = IsTable + (j == N - 1 ? 0 : NumTables[j + 1]); Index: test/CodeGen/ARM/2011-08-25-ldmia_ret.ll =================================================================== --- test/CodeGen/ARM/2011-08-25-ldmia_ret.ll +++ test/CodeGen/ARM/2011-08-25-ldmia_ret.ll @@ -1,4 +1,4 @@ -; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=cortex-a9 | FileCheck %s +; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=cortex-a9 -sparse-jump-table-density=40 | FileCheck %s ; Test that ldmia_ret preserves implicit operands for return values. ; ; This CFG is reduced from a benchmark miscompile. With current Index: test/CodeGen/Generic/MachineBranchProb.ll =================================================================== --- test/CodeGen/Generic/MachineBranchProb.ll +++ test/CodeGen/Generic/MachineBranchProb.ll @@ -41,11 +41,11 @@ entry: switch i32 %x, label %return [ i32 0, label %bb0 - i32 10, label %bb1 - i32 20, label %bb2 - i32 30, label %bb3 - i32 40, label %bb4 - i32 50, label %bb5 + i32 100, label %bb1 + i32 200, label %bb2 + i32 300, label %bb3 + i32 400, label %bb4 + i32 500, label %bb5 ], !prof !1 bb0: tail call void @g(i32 0) br label %return bb1: tail call void @g(i32 1) br label %return @@ -68,7 +68,7 @@ !1 = !{!"branch_weights", ; Default: i32 1, - ; Case 0, 10, 20: + ; Case 0, 100, 200: i32 10, i32 1, i32 1, - ; Case 30, 40, 50: + ; Case 300, 400, 500: i32 1, i32 10, i32 10} Index: test/CodeGen/PowerPC/pr26690.ll =================================================================== --- test/CodeGen/PowerPC/pr26690.ll +++ test/CodeGen/PowerPC/pr26690.ll @@ -35,9 +35,9 @@ while.body: ; preds = %while.body.backedge, %while.body.lr.ph switch i32 %.pre, label %while.body.backedge [ i32 0, label %sw.bb1 - i32 8, label %sw.bb1 - i32 6, label %sw.bb1 - i32 24, label %while.cond.backedge + i32 80, label %sw.bb1 + i32 60, label %sw.bb1 + i32 240, label %while.cond.backedge ] while.body.backedge: ; preds = %while.body, %while.cond.backedge Index: test/CodeGen/Thumb2/ldr-str-imm12.ll =================================================================== --- test/CodeGen/Thumb2/ldr-str-imm12.ll +++ test/CodeGen/Thumb2/ldr-str-imm12.ll @@ -29,16 +29,16 @@ bb20: ; preds = %entry switch i32 undef, label %bb1287 [ - i32 11, label %bb119 - i32 12, label %bb119 - i32 21, label %bb420 - i32 23, label %bb420 - i32 45, label %bb438 - i32 46, label %bb438 - i32 55, label %bb533 - i32 56, label %bb569 - i32 64, label %bb745 - i32 78, label %bb1098 + i32 110, label %bb119 + i32 120, label %bb119 + i32 210, label %bb420 + i32 230, label %bb420 + i32 450, label %bb438 + i32 460, label %bb438 + i32 550, label %bb533 + i32 560, label %bb569 + i32 640, label %bb745 + i32 780, label %bb1098 ] bb119: ; preds = %bb20, %bb20 Index: test/CodeGen/X86/switch-bt.ll =================================================================== --- test/CodeGen/X86/switch-bt.ll +++ test/CodeGen/X86/switch-bt.ll @@ -1,4 +1,4 @@ -; RUN: llc -march=x86-64 -asm-verbose=false < %s | FileCheck %s +; RUN: llc -march=x86-64 -asm-verbose=false < %s -sparse-jump-table-density=40 | FileCheck %s ; This switch should use bit tests, and the third bit test case is just ; testing for one possible value, so it doesn't need a bt. Index: test/CodeGen/X86/switch-edge-weight.ll =================================================================== --- test/CodeGen/X86/switch-edge-weight.ll +++ test/CodeGen/X86/switch-edge-weight.ll @@ -233,11 +233,11 @@ ; block. switch i32 %x, label %sw.default [ - i32 1, label %sw.bb - i32 5, label %sw.bb2 - i32 7, label %sw.bb3 - i32 9, label %sw.bb4 - i32 31, label %sw.bb5 + i32 4, label %sw.bb + i32 20, label %sw.bb2 + i32 28, label %sw.bb3 + i32 36, label %sw.bb4 + i32 124, label %sw.bb5 ], !prof !2 sw.bb: @@ -272,7 +272,7 @@ ; ; CHECK: BB#0: ; BB#0 to BB#6: [10, UINT32_MAX] (15) -; BB#0 to BB#8: [1, 5, 7, 9] (jump table) (45) +; BB#0 to BB#8: [4, 20, 28, 36] (jump table) (45) ; CHECK: Successors according to CFG: BB#8({{[0-9a-fx/= ]+}}25.00%) BB#9({{[0-9a-fx/= ]+}}75.00%) } Index: test/CodeGen/X86/switch.ll =================================================================== --- test/CodeGen/X86/switch.ll +++ test/CodeGen/X86/switch.ll @@ -1,5 +1,5 @@ -; RUN: llc -mtriple=x86_64-linux-gnu %s -o - | FileCheck %s -; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 | FileCheck --check-prefix=NOOPT %s +; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -sparse-jump-table-density=40 | FileCheck %s +; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 -sparse-jump-table-density=40 | FileCheck --check-prefix=NOOPT %s declare void @g(i32)