User account creation filtered due to spam.

Bug 14495 - [tree-ssa] Propagate range info into a switch statement
Summary: [tree-ssa] Propagate range info into a switch statement
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: tree-ssa
: P2 enhancement
Target Milestone: 4.4.0
Assignee: Richard Biener
URL:
Keywords: missed-optimization
Depends on: 18373
Blocks: 34793
  Show dependency treegraph
 
Reported: 2004-03-09 00:35 UTC by Kazu Hirata
Modified: 2008-04-02 12:55 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2007-04-13 10:31:07


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Kazu Hirata 2004-03-09 00:35:13 UTC
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;

}
Comment 1 Andrew Pinski 2004-03-09 00:45:32 UTC
Confirmed.
Comment 2 Andrew Pinski 2005-04-24 11:52:04 UTC
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)
Comment 3 Andrew Pinski 2005-05-08 18:10:35 UTC
I think the issue is that we don't simulate anything besides COND_EXPR.
Comment 4 Diego Novillo 2005-06-03 13:55:44 UTC
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.
Comment 5 Wouter Vermaelen 2006-04-20 10:58:52 UTC
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.
Comment 6 Richard Biener 2007-04-13 10:31:07 UTC
I have a patch to handle the ONE edge case.
Comment 7 patchapp@dberlin.org 2007-04-17 14:05:24 UTC
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
Comment 8 Richard Biener 2008-04-02 12:52:21 UTC
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

Comment 9 Richard Biener 2008-04-02 12:54:53 UTC
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

Comment 10 Richard Biener 2008-04-02 12:55:37 UTC
Fixed.