[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

["law at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From law at redhat dot com  2004-12-10 20:52 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 19:08 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 19:08 -------
> Subject: Re:  [4.0 regression] loop
>  miscompilation at -O1 (-ftree-ch)
> 
> Hi Jeff,
> 
> > Note that recording tmp_1 = next_2 isn't particularly good either since 
> > tmp_1 really isn't equivalent to next_2.  It's equivalent to the
> > previous valueof n next_2, which was next_3.  ugh.  Anyway, I'll verify
> > that Kazu's patch handles this correctly.
> 
> I think so. :-)


So as I mentioned in a message a short while ago, there are some very
simple solutions to this problem.

  1. The simplest would be to disable jump threading on for backedges in
  loops.  Based on some simple instrumentation, that would be bad as
  it would inhibit a large number of threading opportunities (at least
  two hundred within GCC's cc1 .i files).

  2. Disable threading only if we find a PHI argument which was set
  by a PHI the same block.  This still disables a lot of threading
  opportunities. However, we can do much better with a trivial 
  improvement....

  3. Given a PHI node like x_2 = (..., x_2, ...); if we want the x_2
  alternative, then there's no need to inhibit jump threading since
  x_2 is always trivially equivalent to itself.

Option #3 only prevents two valid jump threading opportunities in the
tests I ran.  And it's implementation is pretty trivial:  


  /* Each PHI creates a temporary equivalence, record them.  */
  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
    {
      tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
      tree dst = PHI_RESULT (phi);

      /* If the desired argument is not the same as this PHI's result
         and it is set by a PHI in this block, then we can not thread
         through this block.  */
      if (src != dst
          && TREE_CODE (src) == SSA_NAME
          && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
          && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
        return;

      record_const_or_copy (dst, src);
      register_new_def (dst, &block_defs_stack);
    }


A final approach would be to turn that code into something like this:

  /* Each PHI creates a temporary equivalence, record them.  */
  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
    {
      tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
      tree dst = PHI_RESULT (phi);

      /* If the desired argument is not the same as this PHI's result
         and it is set by a PHI in this block, then we can not thread
         through this block.  */
      if (src != dst
          && TREE_CODE (src) == SSA_NAME
          && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
          && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
        {
          src = make_ssa_name (SSA_NAME_VAR (dst), build_empty_stmt());
        }

      record_const_or_copy (dst, src);
      register_new_def (dst, &block_defs_stack);
    }

Which would allow us to do full jump threading.  What I don't like about
this approach is we have to add some code to track the SSA_NAMEs we
generate in that loop so that we can release them.  Ugh.  It doesn't 
seem worth the headache.

Jeff



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18694