> -----Original Message-----
> From: Jiangning Liu
> Sent: Wednesday, December 28, 2011 5:38 PM
> To: Jiangning Liu; 'Richard Guenther'
> Cc: Michael Matz; gcc@gcc.gnu.org
> Subject: RE: A case exposing code sink issue
>
>
>
> > -----Original Message-----
> > From: gcc-ow...@gcc.gnu.org [mailto:gcc-ow...@gcc.gnu.org] On Behalf
> Of
> > Jiangning Liu
> > Sent: Tuesday, December 27, 2011 5:10 PM
> > To: 'Richard Guenther'
> > Cc: Michael Matz; gcc@gcc.gnu.org
> > Subject: RE: A case exposing code sink issue
> >
> > >
> > > The job to do this is final value replacement, not sinking (we do
> not
> > > sink non-invariant expressions - you'd have to translate them
> through
> > > the loop-closed SSA exit PHI node, certainly doable, patches
> > > welcome ;)).
> > >
> >
> > Richard,
> >
> > In final value replacement, expression "&a + D.xxxx" can be figured
> out,
> > while "&a[i_xxx]" failed to be CHRECed, so I'm wondering if we should
> > lower
> > &a[i_xxx] to "&a + unitsize(a) * i_xxx" first? It seems GCC intends
> to
> > keep
> > &a[i_xxx] until cfgexpand pass. Or we have to directly modify CHREC
> > algorithm to get it calculated?
> >
> > Appreciate your kindly help in advance!
> >
>
> Richard,
>
> Now I have a patch working for the case of step "i++", by directly
> modifying
> scalar evolution algorithm. the following code would be generated after
> SCCP,
> l
> # i_13 = PHI <i_6(7), k_2(D)(4)>
> a_p.0_4 = &a[i_13];
> MEM[(int *)&a][i_13] = 100;
> i_6 = i_13 + 1;
> if (i_6 <= 999)
> goto <bb 7>;
> else
> goto <bb 6>;
>
> <bb 6>:
> a_p_lsm.5_11 = &MEM[(void *)&a + 3996B];
> a_p = a_p_lsm.5_11;
> goto <bb 3>;
>
> It looks good, but I still have problem when the case has step "i+=k".
>
> For this case the value of variable i exiting loop isn't invariant, the
> algorithm below in scalar evolution doesn't work on it,
>
> compute_overall_effect_of_inner_loop()
> {
> ...
> tree nb_iter = number_of_latch_executions (inner_loop);
>
> if (nb_iter == chrec_dont_know)
> return chrec_dont_know;
> else
> {
> tree res;
>
> /* evolution_fn is the evolution function in LOOP. Get
> its value in the nb_iter-th iteration. */
> res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
>
> if (chrec_contains_symbols_defined_in_loop (res, loop->num))
> res = instantiate_parameters (loop, res);
>
> /* Continue the computation until ending on a parent of LOOP.
> */
> return compute_overall_effect_of_inner_loop (loop, res);
> }
> }
>
> In theory, we can still have the transformation like below even if the
> step
> is "i+=k",
>
> # i_13 = PHI <i_6(7), k_2(D)(4)>
> i_14 = i_13,
> a_p.0_4 = &a[i_13];
> MEM[(int *)&a][i_13] = 100;
> i_6 = i_13 + k_2(D); // i+=k
> if (i_6 <= 999)
> goto <bb 7>;
> else
> goto <bb 6>;
>
> <bb 6>:
> a_p_lsm.5_11 = &a[i_14];
> a_p = a_p_lsm.5_11;
> goto <bb 3>;
>
> But I realize this is not a loop closed SSA form at all, because i_14
> is
> being used out of the loop. Where could we extend the liverange of
> variable
> i in GCC infrastructure and finally solve this problem?
>
It seems many people are still in the happy of the upcoming 2012 New Year.
:-)
Following my story, I find the following code in tree-ssa-copy.c
/* Avoid copy propagation from an inner into an outer loop.
Otherwise, this may move loop variant variables outside of
their loops and prevent coalescing opportunities. If the
value was loop invariant, it will be hoisted by LICM and
exposed for copy propagation.
??? The value will be always loop invariant.
In loop-closed SSA form do not copy-propagate through
PHI nodes in blocks with a loop exit edge predecessor. */
if (current_loops
&& TREE_CODE (arg_value) == SSA_NAME
&& (loop_depth_of_name (arg_value) > loop_depth_of_name (lhs)
|| (loops_state_satisfies_p (LOOP_CLOSED_SSA)
&& loop_exit_edge_p (e->src->loop_father, e))))
{
phi_val.value = lhs;
break;
}
Here http://gcc.gnu.org/ml/gcc-patches/2006-12/msg00066.html, Dan said
"The original check was not because of coalescing, but because we would
copy prop in-loop variables outside the loop, causing *more*
invariantness in nested loops."
Can anybody give me a concrete example to explain this statement?
Anyway, for my simple case, I don't see bad thing would happen when
propagate &a[i] out of the loop. Also, after this propagation, "a_p.0_4 =
&a[i_13];" within the loop would be dead code and removed in the passes
afterwards. In my opinion, that way the computation would be reduced in the
loop. Did I make any mistake?
> > Thanks,
> > -Jiangning
> >
> >
> >
>
>
