loop unswitching is sensitive to edge order

loop unswitching is sensitive to edge order

[Ben Elliston]

Hi Zdenek,

The following patch of yours seems to add some code that is sensitive
to the order of edges in the bb edge list.  Am I right?

I could try and fix it myself, but I figure you know the code best.
Is it possible that you can correct it?

Thanks, Ben

2004-09-23  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>

	* cfgloop.h (update_single_exits_after_duplication): Declare.
	(loopify, split_loop_bb): Declaration changed.
	* cfgloopmanip.c (split_loop_bb): Take void * as an argument instead
	of rtx.
	(loopify): Added redirect_all_edges argument.
	(update_single_exits_after_duplication): Export.
	* loop-unswitch.c (unswitch_loop): Changed due to loopify change.
	* tree-flow.h (tree_duplicate_loop_to_header_edge,
	tree_ssa_loop_version): Declare.
	* tree-ssa-loop-manip.c (copy_phi_node_args, rename_variables,
	set_phi_def_stmts, tree_duplicate_loop_to_header_edge,
	lv_adjust_loop_header_phi, lv_adjust_loop_entry_edge,
	lv_update_pending_stmts, tree_ssa_loop_version): New functions.

	* tree-ssa-loop-unswitch.c: New file.
	* Makefile.in (tree-ssa-loop-unswitch.o): Add.
	* timevar.def (TV_TREE_LOOP_UNSWITCH): New timevar.
	* tree-flow.h (tree_ssa_unswitch_loops): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add pass_unswitch.
	* tree-pass.h (pass_unswitch): Declare.
	* tree-ssa-loop.c (tree_ssa_loop_unswitch,
	gate_tree_ssa_loop_unswitch, pass_unswitch): New pass.
	* doc/passes.texi: Documen tree level loop unswitching.

Re: loop unswitching is sensitive to edge order

[Zdenek Dvorak]

Hello,

> The following patch of yours seems to add some code that is sensitive
> to the order of edges in the bb edge list.  Am I right?

I do not know, since I do not understand what you mean.  What problem
do you see with the code?

Zdenek

Re: loop unswitching is sensitive to edge order

[Ben Elliston]

Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> writes:

> > The following patch of yours seems to add some code that is sensitive
> > to the order of edges in the bb edge list.  Am I right?
> 
> I do not know, since I do not understand what you mean.  What problem
> do you see with the code?

My edges-in-vectors patch breaks when integrated with your patch.  I
was able to fix that breakage by modifying my code so that new
elements are inserted at the head of the vector and that vector order
is maintained when elements are removed (ie. it emulates the behaviour
of the existing pred and succ linked lists).

My understanding is that none of the code in GCC should depend on the
order of edges in their containers.  This is the first time I've
encountered such behaviour.

Ben

Re: loop unswitching is sensitive to edge order

[Zdenek Dvorak]

Hello,

> > > The following patch of yours seems to add some code that is sensitive
> > > to the order of edges in the bb edge list.  Am I right?
> > 
> > I do not know, since I do not understand what you mean.  What problem
> > do you see with the code?
> 
> My edges-in-vectors patch breaks when integrated with your patch.  I
> was able to fix that breakage by modifying my code so that new
> elements are inserted at the head of the vector and that vector order
> is maintained when elements are removed (ie. it emulates the behaviour
> of the existing pred and succ linked lists).
> 
> My understanding is that none of the code in GCC should depend on the
> order of edges in their containers.  This is the first time I've
> encountered such behaviour.

as far as I am aware, there is no such dependence in unswitching.  What
exactly breaks with your patch?

Zdenek

Re: loop unswitching is sensitive to edge order

[Ben Elliston]

[-- Attachment #1: Type: text/plain, Size: 903 bytes --]

Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> writes:

> as far as I am aware, there is no such dependence in unswitching.
> What exactly breaks with your patch?

Numerous GCC test cases at -O3.  For example:

Executing on host: /home/bje/build/head/gcc/xgcc -B/home/bje/build/head/gcc/   -O3 -fomit-frame-pointer  -w -c  -o 20020109-1.o /home/bje/source/gcc-head/gcc/testsuite/gcc.c-torture/compile/20020109-1.c    (timeout = 300)
/home/bje/source/gcc-head/gcc/testsuite/gcc.c-torture/compile/20020109-1.c: In function 'foo':
/home/bje/source/gcc-head/gcc/testsuite/gcc.c-torture/compile/20020109-1.c:15: internal compiler error: in tree_split_edge, at tree-cfg.c:3032
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.
compiler exited with status 1

I've attached a patch, as Steven asked, so others can take a look.


[-- Attachment #2: PATCH.bz2 --]
[-- Type: application/octet-stream, Size: 55761 bytes --]

[-- Attachment #3: Type: text/plain, Size: 5 bytes --]


Ben

Re: loop unswitching is sensitive to edge order

[Steven Bosscher]

On Saturday 25 September 2004 13:40, Ben Elliston wrote:
> Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> writes:
> > > The following patch of yours seems to add some code that is sensitive
> > > to the order of edges in the bb edge list.  Am I right?
> >
> > I do not know, since I do not understand what you mean.  What problem
> > do you see with the code?
>
> My edges-in-vectors patch breaks when integrated with your patch.  I
> was able to fix that breakage by modifying my code so that new
> elements are inserted at the head of the vector and that vector order
> is maintained when elements are removed (ie. it emulates the behaviour
> of the existing pred and succ linked lists).
>
> My understanding is that none of the code in GCC should depend on the
> order of edges in their containers.  This is the first time I've
> encountered such behaviour.

Can you post your merge patch so everyone can see what is going on?

Gr.
Steven