Bug 34648 - [4.3 Regression] ICE in find_or_generate_expression
Summary: [4.3 Regression] ICE in find_or_generate_expression
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.3.0
: P1 normal
Target Milestone: 4.3.0
Assignee: Not yet assigned to anyone
URL:
Keywords: ice-on-valid-code
Depends on:
Blocks:
 
Reported: 2008-01-03 09:41 UTC by Jakub Jelinek
Modified: 2008-01-17 21:54 UTC (History)
7 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2008-01-03 11:02:13


Attachments
proposed patch for sccvn (284 bytes, patch)
2008-01-16 20:53 UTC, Andrew Macleod
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jakub Jelinek 2008-01-03 09:41:53 UTC
The following testcase distilled from tinyfugue-5.0 ICEs with
internal compiler error: in find_or_generate_expression, at tree-ssa-pre.c:2255

/* { dg-do compile } */
/* { dg-options "-O2 -fexceptions" } */

extern const unsigned short int **bar (void) __attribute__ ((const));
const char *a;
int b;
char c;

char
foo (int *x)
{
  char r;

  c = '\0';
  if (!b)
    {
      while (((*bar ())[a[*x]] & 0x2000) != 0)
        (*x)++;
      if (a[++(*x)] == '-')
        {
          (*x)++;
          if (a[*x] && !((*bar ())[a[*x]] & 0x2000))
            return '?';
        }
      if (!a[*x] || ((*bar ())[a[*x]] & 0x2000))
        {
          while (((*bar ())[a[*x]] & 0x2000))
            ++(*x);
          return '\0';
        }
    }

  r = a[*x];
  b = a[*x] && !((*bar ())[a[*x]] & 0x2000);
  return r;
}
Comment 1 Richard Biener 2008-01-03 11:02:13 UTC
Confirmed.  We only have SSA_NAMEs in the expression set, which we do not PRE.
Danny, is this supposed not to happen somehow?
Comment 2 Richard Biener 2008-01-03 11:05:35 UTC
We are creating *VH.97 by pieces but fail to create the 'piece' for VH.97 because
we don't consider a SSA_NAME ok for it.
Comment 3 Daniel Berlin 2008-01-03 18:16:45 UTC
It is never okay to base an existing expression on an SSA_NAME alone, which is why we avoid it.

If the SSA_NAME was available, it would have been in the AVAIL set and been found by the "find" part of find_or_generate_expression.
:)

(In reply to comment #2)
> We are creating *VH.97 by pieces but fail to create the 'piece' for VH.97
> because
> we don't consider a SSA_NAME ok for it.
> 

Comment 4 Richard Biener 2008-01-12 18:02:30 UTC
Also ICEs cc1plus with plain -O2 the same way.
Comment 5 Richard Biener 2008-01-12 19:13:55 UTC
Danny, maybe you mis-understood.  We try to generate *VH.98, but VH.98 is indeed
not in avail_out[19], but created for example as

exp_gen[4] := { x_7(D) (VH.72) , D.1661_4 (VH.98) , *VH.74 (VH.75) , a.1_6 (VH.76) , *VH.72 (VH.77) , (unsigned int) VH.77 (VH.78) , VH.76 + VH.78 (VH.79) , *VH.79 (VH.80) , (unsigned int) VH.80 (VH.81) , VH.81 * 2 (VH.82) , VH.75 + VH.82 (VH.83) , *VH.83 (VH.84) , (int) VH.84 (VH.85) , VH.85 & 8192 (VH.86)  }
tmp_gen[4] := { D.1661_4 (VH.98) , D.1662_5 (VH.75) , a.1_6 (VH.76) , D.1664_8 (VH.77) , D.1665_9 (VH.78) , D.1666_10 (VH.79) , D.1667_11 (VH.80) , D.1668_12 (VH.81) , D.1669_13 (VH.82) , D.1670_14 (VH.83) , D.1671_15 (VH.84) , D.1672_16 (VH.85) , D.1673_17 (VH.86)  }

exp_gen[7] := { D.1661_4 (VH.98) , D.1667_34 (VH.97) , *VH.98 (VH.99) , (unsigned int) VH.97 (VH.100) , VH.100 * 2 (VH.101) , VH.99 + VH.101 (VH.102) , *VH.102 (VH.103) , (int) VH.103 (VH.104) , VH.104 & 8192 (VH.105)  }
tmp_gen[7] := { D.1661_35 (VH.98) , D.1662_36 (VH.99) , D.1668_42 (VH.100) , D.1669_43 (VH.101) , D.1670_44 (VH.102) , D.1671_45 (VH.103) , D.1672_46 (VH.104) , D.1673_47 (VH.105)  }

exp_gen[9] := { D.1661_4 (VH.98) , D.1667_53 (VH.109) , *VH.98 (VH.110) , (unsigned int) VH.109 (VH.111) , VH.111 * 2 (VH.112) , VH.110 + VH.112 (VH.113) , *VH.113 (VH.114) , (int) VH.114 (VH.115) , VH.115 & 8192 (VH.116)  }
tmp_gen[9] := { D.1661_54 (VH.98) , D.1662_55 (VH.110) , D.1668_61 (VH.111) , D.1669_62 (VH.112) , D.1670_63 (VH.113) , D.1671_64 (VH.114) , D.1672_65 (VH.115) , D.1673_66 (VH.116)  }

exp_gen[10] := { D.1661_4 (VH.98) , D.1667_53 (VH.109) , *VH.98 (VH.110) , (unsigned int) VH.109 (VH.111) , VH.111 * 2 (VH.112) , VH.110 + VH.112 (VH.113) , *VH.113 (VH.114) , (int) VH.114 (VH.115) , VH.115 & 8192 (VH.116)  }

But all these expressions for VH.98 are plain SSA_NAMEs.

So we can in fact not do insertion of *VH.98 in two of the preds of BB.  It
looks like we do not do verification for that anywhere?
Comment 6 Daniel Berlin 2008-01-12 19:33:57 UTC
Subject: Re:  [4.3 Regression] ICE in find_or_generate_expression

On 12 Jan 2008 19:13:56 -0000, rguenth at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #5 from rguenth at gcc dot gnu dot org  2008-01-12 19:13 -------
> Danny, maybe you mis-understood.  We try to generate *VH.98, but VH.98 is
> indeed
> not in avail_out[19], but created for example as
>
> So we can in fact not do insertion of *VH.98 in two of the preds of BB.  It
> looks like we do not do verification for that anywhere?
Sure we do. It should never be ANTIC if it is not possible to
regenerate the expression.  Anything else is a bug in ANTIC
calculation or initial exp_gen/tmp_gen/etc set construction.

valid_in_sets ensures that SSA_NAME's are either AVAIL_OUT[1], or
available in our current ANTIC set.
ANTIC propagation subtracts TMP_GEN from ANTIC, which should ensure
that values do not get hoisted above the point that creates them.


[1] I honestly don't remember why valid_in_sets ensures that
SSA_NAME's are AVAIL_OUT when bare. That seems wrong to me. The
correct condition is whether they are in our current ANTIC set, just
like it does for more complex expressions. I do not remember when or
why this got changed, but it seems like a bug.
Comment 7 Richard Biener 2008-01-12 19:48:38 UTC
Maybe sth for steven, as he was asking for bugs to look at... ;)
Comment 8 Andrew Macleod 2008-01-16 20:53:41 UTC
Created attachment 14951 [details]
proposed patch for sccvn

I did some analysis, and then verified with dberlin that I was on the right track.

The root of the problem is a disconnect between SCCVN and PRE.

The function bar() is a function call which is a constant. SCCVN therefore puts it in the tables as a value which can be regenerated by calling bar().

PRE in turn looks at the call and notes that it can throw an exception, and says that it is therefore *not* an expression which can be regenerated.

Things then fail in find_or_generate_expression() because the expression is in the table, but PRE is unable to regenerate it.

In order to fix the problem, we need to make SCCVN and PRE agree whether a constant function which can throw is an expression which can be regenerated.

My initial take on that it is not, because the throw could result in some side effects.

The decl for bar() is

   extern const unsigned short int **bar (void) __attribute__ ((const));

The other question is 'is that really a throwable function?'

tree_could_throw_p() currently returns TRUE for bar().  This problem could also be fixed by bar() not being a throwable expression. I'm assuming this is well defined, and currently correct. 

The final option would be to allow PRE to regenerate expressions which can throw.

Thoughts?

I've attached a patch to modify SCCVN to say expressions which throw can not be regenerated.  Its currently going through testing.
Comment 9 rguenther@suse.de 2008-01-16 21:18:15 UTC
Subject: Re:  [4.3 Regression] ICE in
 find_or_generate_expression

On Wed, 16 Jan 2008, amacleod at redhat dot com wrote:

> ------- Comment #8 from amacleod at redhat dot com  2008-01-16 20:53 -------
> Created an attachment (id=14951)
>  --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14951&action=view)
> proposed patch for sccvn
> 
> I did some analysis, and then verified with dberlin that I was on the right
> track.

Thanks!

> The root of the problem is a disconnect between SCCVN and PRE.
> 
> The function bar() is a function call which is a constant. SCCVN therefore puts
> it in the tables as a value which can be regenerated by calling bar().
> 
> PRE in turn looks at the call and notes that it can throw an exception, and
> says that it is therefore *not* an expression which can be regenerated.
> 
> Things then fail in find_or_generate_expression() because the expression is in
> the table, but PRE is unable to regenerate it.
> 
> In order to fix the problem, we need to make SCCVN and PRE agree whether a
> constant function which can throw is an expression which can be regenerated.
> 
> My initial take on that it is not, because the throw could result in some side
> effects.
> 
> The decl for bar() is
> 
>    extern const unsigned short int **bar (void) __attribute__ ((const));
> 
> The other question is 'is that really a throwable function?'

A const function does not throw.  From the docs:

"..., and have no effects except the return value."

likewise pure functions do not throw.

> tree_could_throw_p() currently returns TRUE for bar().  This problem could also
> be fixed by bar() not being a throwable expression. I'm assuming this is well
> defined, and currently correct. 

Yes it is.  I think adjusting tree_could_throw_p() is the correct
thing to do.

Richard.
Comment 10 Andrew Macleod 2008-01-16 21:27:44 UTC
Sure, if that the case, then the bug is in tree_could_throw_p() and we can fix it there  :-)
Comment 11 Andrew Macleod 2008-01-16 22:44:46 UTC
One could also argue that this exposes two bugs.

First, the const function should not be returning true for tree_could_throw_p()
second, SCCVN and PRE don't agree on whether an expression that can throw can be regenerated.

We probably still need to make SCCVN and PRE agree, or something else may trigger this down the road.
Comment 12 Andrew Macleod 2008-01-17 21:54:42 UTC
Bah. I missed getting the PR in the checkin message.  

Committed the proposed patch and the testcase as revision 131610. Bootstrapped and regression tested on x86_64-linux-gnu

Follow on conversations about const functions throwing were had at http://gcc.gnu.org/ml/gcc-patches/2008-01/msg00764.html