[tree-ssa] Tail recursion improvement

[Zdenek Dvorak]

Hello,

> > After fixing this, I have run into a problem with dce; it removes the
> > *x assignment.  It does not do this without loop header copying, since
> > without it x has a name tag with DECL_NEEDS_TO_LIVE_IN_MEMORY_INTERNAL
> > set; but for the type tag it is not, and thus the statement is not
> > considered necessary.  I am not sure whether this is a bug at all
> > (if the program was not buggy, the writes to *x could indeed be safely
> > eliminated); but in any case it causes the libmudflap test to fail.
> > In case it indeed is a bug, where should it be fixed? Adding some more
> > conditions to mark_stmt_if_obviously_necessary? Or setting
> > DECL_NEEDS_TO_LIVE_IN_MEMORY_INTERNAL also for the type tag, somewhere?
> > 
> Well, I bootstrapped your patch together with the fix for this problem. 
> It seems to work, but we get a few new regressions in libstdc++.
> 
> Undoing your patch fixes the regressions, but I cannot really say
> whether your patch is still missing something or if there are more
> aliasing problems that need to be addressed.
> 
> New regressions in 00testsuite-linux-gnu/20040304/libstdc++.sum.gz:
>          FAIL: 20_util/binders.cc execution test

the problem here is this:

We have

  goto <bb 2> (<L2>);

<L0>:;
  printf ("xxx\n");
  #   VUSE <__first_22>;
  T.200_17 = __first._M_current;
  T.201_18 = T.200_17 + 4B;
  #   __first_25 = VDEF <__first_22>;
  __first._M_current = T.201_18;
  # SUCC: 2 (fallthru,dfs_back)

  # BLOCK 2
  # PRED: 1 (fallthru,dfs_back) 0 (fallthru)
  # __first_22 = PHI <__first_23(0), __first_25(1)>;
<L2>:;
  <D10845>_4 = (int * const *)&__first;
  #   VUSE <__first_22>;
  T.197_7 = *<D10845>_4;
  <D10849>_9 = (int * const *)&__last;
  #   VUSE <__last_24>;
  T.199_12 = *<D10849>_9;
  <D10837>_13 = T.197_7 != T.199_12;
  T.174_14 = (bool)<D10837>_13;
  if (T.174_14) goto <L0>; else goto <L6>;

After copying the loop header, this becomes

  # __first_25 = PHI <__first_23(0), __first_32(1)>;
<L0>:;
  printf ("xxx\n");
  #   VUSE <__first_25>;
  T.200_17 = __first._M_current;
  T.201_18 = T.200_17 + 4B;
  #   __first_32 = VDEF <__first_25>;
  __first._M_current = T.201_18;
  <D10845>_33 = (int * const *)&__first;
  #   VUSE <TMT.217_26>;
  T.197_34 = *<D10845>_33;
  <D10849>_35 = (int * const *)&__last;
  #   VUSE <TMT.217_26>;
  T.199_36 = *<D10849>_35;
  <D10837>_37 = T.197_34 != T.199_36;
  T.174_38 = (bool)<D10837>_37;
  if (T.174_38) goto <L0>; else goto <L6>;

Which is wrong, since the loads in the copied header now do not know
that they are modified in the loop body.  It seems to me that we either
need to preserve name tags in copied parts (which would be a good idea
anyway, so that we do not lose information unnecessarily, but does not
seem easy to do), or cancel the name tags that are rewritten out of ssa
completely, right?

Zdenek