[Bug middle-end/21417] New: Missed jump threading opportunity on trees

[Bug middle-end/21417] New: Missed jump threading opportunity on trees

[steven at gcc dot gnu dot org]

Consider the following test case (t.c): 
-------------------------------- 
struct tree_common 
{ 
  int code; 
}; 
union tree_node 
{ 
  struct tree_common common; 
}; 
typedef union tree_node *tree; 
 
extern tree test (tree, int, int); 
extern tree foo (void); 
extern void abort (void) __attribute__ ((__noreturn__)); 
 
tree 
test (tree expr, int t, int D17630) 
{ 
  int __i; 
 
L0: 
  if (expr->common.code != 142) goto L23; else goto L2; 
 
L2: 
  __i = 0; 
  goto L10; 
 
L10: 
  __i = __i + 1; 
  if (D17630 != __i) goto L8; else goto L19; 
 
L8: 
  if (t) goto L15; else goto L10; 
 
L15: 
  expr = foo (); 
  if (expr->common.code != 142) goto L23; else goto L0; 
 
L19: 
  abort (); 
 
L23: 
  return expr; 
} 
-------------------------------- 
 
$ ./cc1 -quiet -O3 -dG --param max-cse-path-length=1 -fdump-tree-vars t.c 
$ grep "Bypass edge" t.c.07.bypass 
Bypass edge from 5->1 to 2 
# ./cc1 --version 
GNU C version 4.1.0 20050506 (experimental) (x86_64-unknown-linux-gnu) 
        compiled by GNU C version 4.1.0 20050506 (experimental). 
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072

-- 
           Summary: Missed jump threading opportunity on trees
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Keywords: missed-optimization, TREE
          Severity: normal
          Priority: P2
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: steven at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org,law at redhat dot com


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

[Bug middle-end/21417] Missed jump threading opportunity on trees

[kazu at cs dot umass dot edu]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kazu at cs dot umass dot edu


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |tree-optimization


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-06 14:12 -------
Confirmed, there is a load PRE missing also which looks like is causing the jump threader not to be able 
to do this jump.



-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-05-06 14:12:07
               date|                            |


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2006-01-21 03:03 -------
Oh, we still not load PRE this one because we don't handle (*a).b yet.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
   Last reconfirmed|2005-10-24 00:23:37         |2006-01-21 03:03:17
               date|                            |


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2006-02-06 16:17 -------
the load PRE issue has been fixed but DOM does not thread the jump for some
reason.


-- 


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[law at redhat dot com]

------- Comment #4 from law at redhat dot com  2006-02-07 21:24 -------
The jump threading code is *very* conservative when threading across a backedge
in the CFG.   The fundamental issue is that you'll have the result of the
conditional in your hash tables from the normal DOM walk and you may
(incorrectly) use that result.  ie, think about the case where you've got
something like this at the head of a loop

x = y->z
if (x == 42) ...

If you traverse a backedge to that block and try to thread through the block,
you can get incorrect results since you'll have recorded knowledge about x in
your hash tables already, but x's value may change from one iteration to the
next.

Threading the backedge *is* safe when statements in the target block do not
affect the result of the conditional at the end of the target block.  I found
that handling the trivial case (there are *no* statements other than the 
conditional) caught most of the cases of threadable backedges I had
encountered.

It shouldn't be terribly hard to look at the operands of the conditional and
allow threading a backedge if the operands of the conditional are not set in
statements in the same block as the conditional.


-- 


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[law at gcc dot gnu dot org]

------- Comment #7 from law at gcc dot gnu dot org  2006-02-09 02:36 -------
Subject: Bug 21417

Author: law
Date: Thu Feb  9 02:36:33 2006
New Revision: 110785

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=110785
Log:

        PR tree-optimization/21417
        * tree-ssa-threadedge.c (thread_across_edge): Reject threading
        across a backedge if the control statement at the end of the
        block is data dependent on other statements in the same block.
        (record_temporary_equivalences_from_stmts): Remove over-conservative
        test for threading across backedges.

        * gcc.dg/tree-ssa/pr21417.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr21417.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-threadedge.c


-- 


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[law at redhat dot com]

------- Comment #5 from law at redhat dot com  2006-02-09 02:36 -------
Subject: Re:  Missed jump threading
        opportunity on trees

On Mon, 2006-02-06 at 16:17 +0000, pinskia at gcc dot gnu dot org wrote:
> 
> ------- Comment #3 from pinskia at gcc dot gnu dot org  2006-02-06 16:17 -------
> the load PRE issue has been fixed but DOM does not thread the jump for some
> reason.
This patch allows DOM to thread the jump in question (which in
effect pulls the conditional out of the loop, definitely a good
thing to do when we can).

As I mentioned in a previous comment, we were being very conservative
when threading across backedges in the CFG.  We can be a little more
aggressive, specifically we can allow statements in the target block
which do not affect the control statement at the end of the target
block.

This triggered a few more times in my testbucket, so I'm confident
it's allowing us to avoid conditionals in at least a few real world
hunks of code.

Bootstrapped and regression tested on i686-pc-linux-gnu.


------- Comment #6 from law at redhat dot com  2006-02-09 02:36 -------
Created an attachment (id=10812)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=10812&action=view)


-- 


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

[Bug tree-optimization/21417] Missed jump threading opportunity on trees

[law at redhat dot com]

------- Comment #8 from law at redhat dot com  2006-02-09 02:36 -------
Fixed with today's change to tree-ssa-threadedge.c


-- 

law at redhat dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


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