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
Confirmed, there is a load PRE missing also which looks like is causing the jump threader not to be able to do this jump.
Oh, we still not load PRE this one because we don't handle (*a).b yet.
the load PRE issue has been fixed but DOM does not thread the jump for some reason.
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.
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.
Created attachment 10812 [details] PATCH
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
Fixed with today's change to tree-ssa-threadedge.c