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 @@ -14,7 +14,10 @@ declare void @foo(i32) declare i32 @bar(i32) -define i32 @test(i32 %in1, i32 %in2) nounwind { +; optsize is necessary to reproduce the behavior, because at the time the bug +; was found, the minimum jump table density was 40 for all functions, but now +; it is lower for non optsize functions. +define i32 @test(i32 %in1, i32 %in2) nounwind optsize { entry: %call = tail call zeroext i1 @getbool() nounwind br i1 %call, label %sw.bb18, label %sw.bb2 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 @@ -12,7 +12,9 @@ ; CHECK: testq %rax, %r ; CHECK-NEXT: j -define void @test(i8* %l) nounwind { +; optsize is necessary here, to prevent the switch from turning into a jump +; table. +define void @test(i8* %l) nounwind optsize { entry: %l.addr = alloca i8*, align 8 ; [#uses=2] store i8* %l, i8** %l.addr @@ -102,7 +104,8 @@ ; Ensure that optimizing for jump tables doesn't needlessly deteriorate the ; created binary tree search. See PR22262. -define void @test4(i32 %x, i32* %y) { +; optsize necessary to force the backend to not create a jump table. +define void @test4(i32 %x, i32* %y) optsize { ; CHECK-LABEL: test4: entry: Index: test/CodeGen/X86/switch-edge-weight.ll =================================================================== --- test/CodeGen/X86/switch-edge-weight.ll +++ test/CodeGen/X86/switch-edge-weight.ll @@ -54,6 +54,7 @@ ; CHECK-LABEL: test2 +; optsize necessary to prevent there from being 1 larger jump table define void @test2(i32 %x) nounwind { entry: @@ -226,7 +227,8 @@ ; CHECK-LABEL: test5 -define void @test5(i32 %x) nounwind { +; optsize forces more dense jump tables +define void @test5(i32 %x) nounwind optsize { entry: ; In this switch statement, there is an edge from jump table to default basic Index: test/CodeGen/X86/switch.ll =================================================================== --- test/CodeGen/X86/switch.ll +++ test/CodeGen/X86/switch.ll @@ -246,7 +246,9 @@ } -define void @optimal_jump_table1(i32 %x) { +; optsize necessary to prevent lower density threshold from making a single +; jump table. +define void @optimal_jump_table1(i32 %x) optsize { entry: switch i32 %x, label %return [ i32 0, label %bb0 @@ -288,7 +290,8 @@ } -define void @optimal_jump_table2(i32 %x) { +; optsize prevents lower thresholds from creating a single jump table. +define void @optimal_jump_table2(i32 %x) optsize { entry: switch i32 %x, label %return [ i32 0, label %bb0 @@ -315,7 +318,8 @@ } -define void @optimal_jump_table3(i32 %x) { +; optsize prevents lower thresholds from creating a single jump table. +define void @optimal_jump_table3(i32 %x) optsize { entry: switch i32 %x, label %return [ i32 1, label %bb0 @@ -540,11 +544,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 !3 bb0: tail call void @g(i32 0) br label %return bb1: tail call void @g(i32 1) br label %return @@ -557,7 +561,7 @@ ; Make sure to pick a pivot in the middle also with zero-weight cases. ; CHECK-LABEL: zero_weight_tree ; CHECK-NOT: cmpl -; CHECK: cmpl $29 +; CHECK: cmpl $299 } !3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10} @@ -567,13 +571,13 @@ 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 60, label %bb6 - i32 70, label %bb6 + i32 100, label %bb1 + i32 200, label %bb2 + i32 300, label %bb3 + i32 400, label %bb4 + i32 500, label %bb5 + i32 600, label %bb6 + i32 700, label %bb6 ], !prof !4 bb0: tail call void @g(i32 0) br label %return bb1: tail call void @g(i32 1) br label %return @@ -592,7 +596,7 @@ ; CHECK-LABEL: left_leaning_weight_balanced_tree ; CHECK-NOT: cmpl -; CHECK: cmpl $49 +; CHECK: cmpl $499 } !4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1000} @@ -602,13 +606,13 @@ 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 60, label %bb6 - i32 70, label %bb6 + i32 100, label %bb1 + i32 200, label %bb2 + i32 300, label %bb3 + i32 400, label %bb4 + i32 500, label %bb5 + i32 600, label %bb6 + i32 700, label %bb6 ], !prof !5 bb0: tail call void @g(i32 0) br label %return bb1: tail call void @g(i32 1) br label %return @@ -620,13 +624,13 @@ bb7: tail call void @g(i32 7) br label %return return: ret void -; Same as the previous test, except case 50 has higher rank to the left than it -; would have on the right. Case 60 would have the same rank on both sides, so is +; Same as the previous test, except case 500 has higher rank to the left than it +; would have on the right. Case 600 would have the same rank on both sides, so is ; moved into the leaf. ; CHECK-LABEL: left_leaning_weight_balanced_tree2 ; CHECK-NOT: cmpl -; CHECK: cmpl $59 +; CHECK: cmpl $599 } !5 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 90, i32 70, i32 1000} @@ -636,13 +640,13 @@ 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 60, label %bb6 - i32 70, label %bb6 + i32 100, label %bb1 + i32 200, label %bb2 + i32 300, label %bb3 + i32 400, label %bb4 + i32 500, label %bb5 + i32 600, label %bb6 + i32 700, label %bb6 ], !prof !6 bb0: tail call void @g(i32 0) br label %return bb1: tail call void @g(i32 1) br label %return @@ -658,7 +662,7 @@ ; CHECK-LABEL: right_leaning_weight_balanced_tree ; CHECK-NOT: cmpl -; CHECK: cmpl $19 +; CHECK: cmpl $199 } !6 = !{!"branch_weights", i32 1, i32 1000, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 10}