[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[wouter dot vermaelen at pi dot be]

------- Comment #5 from wouter dot vermaelen at pi dot be  2006-04-20 10:58 -------
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.


-- 

wouter dot vermaelen at pi dot be changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |wouter dot vermaelen at pi
                   |                            |dot be


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2007-04-13 10:31 -------
I have a patch to handle the ONE edge case.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2006-03-05 17:19:18         |2007-04-13 10:31:07
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[patchapp at dberlin dot org]

------- Comment #7 from patchapp at dberlin dot org  2007-04-17 14:05 -------
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


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2008-04-02 12:52 -------
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


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2008-04-02 12:54 -------
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


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2008-04-02 12:55 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.4.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[pinskia at gcc dot gnu dot org]

-- 
Bug 14495 depends on bug 18373, which changed state.

Bug 18373 Summary: [meta-bug] VRP Value Range Propagation
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18373

           What    |Old Value                   |New Value
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-06-03 13:55 -------

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.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-08 18:10 -------
I think the issue is that we don't simulate anything besides COND_EXPR.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dnovillo at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-24 11:52 -------
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)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495

[Bug tree-optimization/14495] [tree-ssa] Propagate range info into a switch statement

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.5.0                       |---


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14495