Consider: void bar0 (void); void bar1 (void); void bar2 (void); void bar3 (void); void foo (int a) { if (a < 100) return; if (200 < a) return; switch (a) { case 99: bar0 (); return; case 100: bar1 (); return; case 101: bar2 (); return; case 102: bar3 (); return; } } case 99 won't trigger, but I still get: foo (a) { <bb 0>: if (a <= 99) goto <L0>; else goto <L1>; <L0>:; return; <L1>:; if (a > 200) goto <L2>; else goto <L3>; <L2>:; return; <L3>:; switch (a) { case 99: goto <L4>; case 100: goto <L5>; case 101: goto <L6>; case 102: goto <L7>; default : goto <L8>; } <L4>:; bar0 () [tail call]; return; <L5>:; bar1 () [tail call]; return; <L6>:; bar2 () [tail call]; return; <L7>:; bar3 () [tail call]; return; <L8>:; return; }
Confirmed.
VRP does not remove this for some reason even though we have now enough information to do so: a_2: [100, 200] switch (a_2)
I think the issue is that we don't simulate anything besides COND_EXPR.
The issue is that the propagator engine does not implement the concept of multiway branches taking some edges. It supports ONE, NONE or ALL. Frankly, I'm not at all convinced that this is worth handling. But if we were to handle it, the place to fix is the propagator engine.
I think something similar happens for the following code. int f(int a) { switch (a & 7) { case 0: return 2; case 1: return 3; case 2: return 5; case 3: return 7; case 4: return 11; case 5: return 13; case 6: return 17; case 7: return 19; } } Part of the generated code looks like this: movl 8(%ebp), %eax andl $7, %eax cmpl $7, %eax jbe .L15 popl %ebp ret .p2align 4,,15 .L15: jmp *.L11(,%eax,4) The test for values bigger than 7 is clearly not needed here. I don't know much about compiler technologie, but maybe this specific case is easier to solve with some peephole optimization? I have seen real code (Z80 emulator or HQ2x scaler algorithm) that does a switch on a unsigned char and handles all 256 cases. Code like that would benefit from this optimization. Thanks.
I have a patch to handle the ONE edge case.
Subject: Bug number PR14495 A patch for this bug has been added to the patch tracker. The mailing list url for the patch is http://gcc.gnu.org/ml/gcc-patches/2007-04/msg01072.html
Subject: Bug 14495 Author: rguenth Date: Wed Apr 2 12:51:37 2008 New Revision: 133834 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=133834 Log: 2008-04-02 Richard Guenther <rguenther@suse.de> PR tree-optimization/14495 * tree-vrp.c (vrp_visit_cond_stmt): Do not handle SWITCH_EXPR here ... (vrp_visit_switch_stmt): ... but here (new function). (find_case_label_index): New helper function. (vrp_visit_stmt): Dispatch to vrp_visit_switch_stmt. * gcc.dg/tree-ssa/vrp40.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp40.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-vrp.c
Subject: Bug 14495 Author: rguenth Date: Wed Apr 2 12:54:08 2008 New Revision: 133835 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=133835 Log: 2008-04-02 Richard Guenther <rguenther@suse.de> PR tree-optimization/14495 PR tree-optimization/34793 * tree-vrp.c (struct switch_update): New structure. (to_remove_edges, to_update_switch_stmts): New VECs. (simplify_switch_using_ranges): New function. Remove not taken case labels and edges. (simplify_stmt_using_ranges): Call it. (identify_jump_threads): Mark edges we have queued for removal so we don't thread them. (execute_vrp): Remove edges queued for removal, update SWITCH_STMT case label vector. * tree-cfg.c (group_case_labels): Deal with missing default label. (tree_verify_flow_info): Allow missing default label. * stmt.c (emit_case_bit_tests): Deal with NULL default_label. (emit_case_nodes): Likewise. (expand_case): Do not rely on the default label to be present. * expr.c (try_casesi): Deal with NULL default_label. (do_tablejump): Likewise. * gcc.dg/tree-ssa/vrp41.c: New testcase. * gcc.dg/tree-ssa/vrp42.c: Likewise. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp41.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp42.c Modified: trunk/gcc/ChangeLog trunk/gcc/expr.c trunk/gcc/stmt.c trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-cfg.c trunk/gcc/tree-vrp.c
Fixed.