[PATCH PR41488]Recognize more induction variables by simplifying PEELED chrec in scalar evolution

[Jeff Law]

On 12/06/13 03:29, bin.cheng wrote:
> Hi,
> Entry pr41488 shows a case in which induction variable can't be recognized
> or coalesced.  As noted in the bug entry, one possible fix is to teach PRE
> not to do some specific transformation.  However, it's in nature a scalar
> evolution issue.  Considering below snippet:
>
>     # i_17 = PHI <i_13(5), 0(3)>
>     # _20 = PHI <_5(5), start_4(D)(3)>
>     ...
>     i_13 = i_17 + 1;
>     _5 = start_4(D) + i_13;
>
> Variable _20 appears in the form of PEELED chrec like (start_4, _5)_LOOP,
> meaning it has value "start_4" in the 1st iteration, then changes to _5 in
> following iterations.  PEELED chrec is not implemented by GCC right now, it
> can be simplified into either POLYNOMIAL or PERIOD one.
Right.  PEELED_CHREC was removed from the LNO branch back in 2004, 
presumably before the LNO branch was merged into the mainline.  No 
reason was given.

But what you're really discovering here is that _20 is just another 
standard looking IV that appears in the form of a peeled chrec, right?


  The POLYNOMIAL
> chrec is processed by GCC after being recognized, as in the examle, _20 is
> actually {start_4, 1}_LOOP.
Right.  Based on reading the archives, it looks like this stuff is/was 
generated by PRE.  I also suspect jump threading can create them.  There 
was talk of throttling PRE to leave things in a form that the IV 
analysis could more easily digest, but I'm not sure if that was ever 
completed.

[ snip ]

>
> One point needs to be clarified that I use tree_to_aff_combination_expand in
> the patch.  Rational is the number of the specific PEELED_CHRECs should be
> moderate, I also check the equality literally firstly and resort to affine
> facility if that fails.  By measuring bootstrap of gcc and spec2kint, I
> collected the number of opportunities caught by this patch like below:
>                              literal comparison/affine comparison
> GCC                          ~1200/~250
> Spec2Kint              93/34
>
> I could back trace the ssa chain instead of using affine functions, but that
> would miss some cases.
I assume tree_to_aff_combination_expand is relatively expensive, thus 
the two approaches, one which avoids tree_to_aff_combination_expand.


In add_old_iv_candidates, is it the case that the only time 
SSA_NAME_DEF_STMT (def) is another PHI node is when it's one of these 
affine ivs appearing in the form of a PEELED_CHREC?  And in that case, 
we do not want to record the possibility of leaving the original IV 
untouched?  -- Just trying to make sure I understand the code before 
giving a final approval.

jeff