Re: [PING][PATCH][PR65443] Add transform_to_exit_first_loop_alt

[Richard Biener <rguenther@suse.de>]

On Wed, 15 Apr 2015, Tom de Vries wrote:

> On 03-04-15 14:39, Tom de Vries wrote:
> > On 27-03-15 15:10, Tom de Vries wrote:
> > > Hi,
> > > 
> > > this patch fixes PR65443, a todo in the parloops pass for function
> > > transform_to_exit_first_loop:
> > > ...
> > >     TODO: the common case is that latch of the loop is empty and
> > > immediately
> > >     follows the loop exit.  In this case, it would be better not to copy
> > > the
> > >     body of the loop, but only move the entry of the loop directly before
> > > the
> > >     exit check and increase the number of iterations of the loop by one.
> > >     This may need some additional preconditioning in case NIT = ~0.
> > > ...
> > > 
> > > The current implementation of transform_to_exit_first_loop transforms the
> > > loop
> > > by moving and duplicating the loop body. This patch transforms the loop
> > > into the
> > > same normal form, but without the duplication, if that's possible
> > > (determined by
> > > try_transform_to_exit_first_loop_alt).
> > > 
> > > The actual transformation, done by transform_to_exit_first_loop_alt
> > > transforms
> > > this loop:
> > > ...
> > >       bb preheader:
> > >       ...
> > >       goto <bb header>
> > > 
> > >       <bb header>:
> > >       ...
> > >       if (ivtmp < n)
> > >         goto <bb latch>;
> > >       else
> > >         goto <bb exit>;
> > > 
> > >       <bb latch>:
> > >       ivtmp = ivtmp + inc;
> > >       goto <bb header>
> > > ...
> > > 
> > > into this one:
> > > ...
> > >       bb preheader:
> > >       ...
> > >       goto <bb newheader>
> > > 
> > >       <bb header>:
> > >       ...
> > >       goto <bb latch>;
> > > 
> > >       <bb newheader>:
> > >       if (ivtmp < n + 1)
> > >         goto <bb header>;
> > >       else
> > >         goto <bb exit>;
> > > 
> > >       <bb latch>:
> > >       ivtmp = ivtmp + inc;
> > >       goto <bb newheader>
> > > ...
> > > 
> > 
> > Updated patch, now using redirect_edge_var_map and flush_pending_stmts.
> > 
> > Bootstrapped and reg-tested on x86_64.
> > 
> > OK for stage1 trunk?
> > 
> 
> Ping.

+static void
+replace_imm_uses (tree val, imm_use_iterator *imm_iter)
+{
+  use_operand_p use_p;
+
+  FOR_EACH_IMM_USE_ON_STMT (use_p, *imm_iter)
+    SET_USE (use_p, val);

Use propagate_value.  Why this odd interface passing a imm_iter?!

In fact most of the "repair SSA" in transform_to_exit_first_loop_alt
looks too ad-hoc to me ... it also looks somewhat familiar to other
code ...

Unfortunately the comment before the function isn't in SSA form
so it's hard to follow the transform.

I consider the parloops code bitrotten, no repair possible, so
I might be convinced to not care about new spaghetti in there...

+  /* Fix up loop structure.  TODO: Check whether this is sufficient.  */
+  loop->header = new_header;
+

no, surely not.  Number of iterations (and estimates) are off
after the transform and loop->latch might also need updating.

"Safest" is to simply schedule a fixup (but you'll lose any
loop annotation in that process).

+  /* Figure out whether nit + 1 overflows.  */
+  if (TREE_CODE (nit) == INTEGER_CST)
+    {
+      if (!tree_int_cst_equal (nit, TYPE_MAXVAL (nit_type)))

in case nit_type is a pointer type TYPE_MAXVAL will be NULL I think.

Is the whole exercise for performance?  In that case using an
entirely new, unsigned IV, that runs from 0 to niter should
be easiest and just run-time guard that niter == +INF case?

For the graphite case, can't you make graphite generate the
loops exit-first in the first place?

The testcases are just correctness ones?  That is, there isn't
any testcase that checks whether the new code is exercised?
(no extra debugging dumping?)

Thanks,
Richard.