Bug 88936 - [8 Regression] -fipa-pta breaks bash (incorrect optimisation of recursive static function)
Summary: [8 Regression] -fipa-pta breaks bash (incorrect optimisation of recursive sta...
Alias: None
Product: gcc
Classification: Unclassified
Component: ipa (show other bugs)
Version: 8.2.0
: P2 normal
Target Milestone: 9.0
Assignee: Richard Biener
Keywords: wrong-code
Depends on:
Blocks: 68331
  Show dependency treegraph
Reported: 2019-01-21 08:25 UTC by Sergei Trofimovich
Modified: 2023-04-01 00:45 UTC (History)
5 users (show)

See Also:
Known to work: 6.4.0, 9.0
Known to fail: 7.3.0, 8.2.0
Last reconfirmed: 2019-01-21 00:00:00

main,c (293 bytes, text/x-csrc)
2019-01-21 08:26 UTC, Sergei Trofimovich
prototype conservative fix (1.77 KB, patch)
2019-02-05 10:50 UTC, Richard Biener
Details | Diff
final fix (2.06 KB, patch)
2019-04-12 09:54 UTC, Richard Biener
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Sergei Trofimovich 2019-01-21 08:25:44 UTC
Initially bug is observed by muffindrake on #gentoo-portage as a series of mysterious bash failures.

Here is the minimal reproducer:

  #include <stdio.h>

   How to reproduce:

  $ gcc -O2 -Wall -fno-stack-protector           main.c -o c-bug         && ./c-bug
  ff(1) = 1
  $ gcc -O2 -Wall -fno-stack-protector -fipa-pta main.c -o c-bug-ipa-pta && ./c-bug-ipa-pta
  ff(1) = 3

  static long bug (long depth, long * v)
    if (depth == 0)
      *v = 0;
      return 1;

    long r = 1;
    long val = bug(depth - 1, &r);
    return 2 * r + val;

  static long ff (long depth)
    return bug(depth, (long*)NULL);

  int main() {
    fprintf(stderr, "ff(1) = %ld\n", ff(1));

Reproducible on 9.0.0 20190120, 8.2.0, 7.4.0, 6.5.0. Not reproducible on 5.5.0.
Reproducible on multiple platforms.

$ ./xgcc -B. -v
Reading specs from ./specs
Target: x86_64-pc-linux-gnu
Configured with: ../gcc/configure --enable-languages=c,c++ --disable-bootstrap --with-multilib-list=m64 --prefix=/home/slyfox/dev/git/gcc-native/../gcc-native-quick-installed --disable-nls CFLAGS='-O0 -g ' CXXFLAGS='-O0 -g ' --with-sysroot=/usr/x86_64-HEAD-linux-gnu
Thread model: posix
gcc version 9.0.0 20190120 (experimental) (GCC)
Comment 1 Sergei Trofimovich 2019-01-21 08:26:51 UTC
Created attachment 45476 [details]
Comment 2 Sergei Trofimovich 2019-01-21 08:29:02 UTC
The sample output different result with -fipa-pta and without.

$ gcc -O2 -Wall -fno-stack-protector           main.c -o c-bug         && ./c-bug
ff(1) = 1
$ gcc -O2 -Wall -fno-stack-protector -fipa-pta main.c -o c-bug-ipa-pta && ./c-bug-ipa-pta
ff(1) = 3
Comment 3 Martin Liška 2019-01-21 08:33:51 UTC
Confirmed, started with r231498.
Comment 4 Richard Biener 2019-01-21 09:42:13 UTC
Comment 5 Richard Biener 2019-01-21 10:35:25 UTC
OK, so the issue is that the clobber of rD.1909 makes *v_8(D) = 0 dead
because IPA points-to uses the callers r UID in the points-to set on
the receiving side as well.

bug (long intD.8 depthD.1905, long intD.8 * vD.1906)
  # RANGE [-9223372036854775808, 9223372036854775806]
  long intD.8 depth_6(D) = depthD.1905;
  # PT = null { D.1909 }
  # ALIGN = 8, MISALIGN = 0
  long intD.8 * v_8(D) = vD.1906;
  long intD.8 valD.1910;
  <bb 2> [local count: 1073741824]:
  if (depth_6(D) == 0)
    goto <bb 3>; [51.12%]
    goto <bb 4>; [48.88%]

  <bb 3> [local count: 548896821]:
  *v_8(D) = 0;
  goto <bb 5>; [100.00%]
  <bb 5> [local count: 1073741824]:
  # _4 = PHI <1(3), _13(4)>
  rD.1909 ={v} {CLOBBER};
  return _4;


I don't see an easy way to mitigate this (this can also happen in arbitrary cycles).  We have to support the case where exactly this UID needs to be
present (if a pointer to r is returned again) as well as the case of
supporting alternate instantiations of r.  One way would be to always
pass down another dummy var (but we'd need a UID for that).  There's
also the missed optimization that bug() doesn't know v does not point
to its local r in IPA-PTA (I think).

Cycles are difficult.

A simple approach might be to drop to non-IPA mode for members of a
cgraph cycle.  Do we have an utility to compute SCCs of the callgraph?
Comment 6 Richard Biener 2019-01-21 11:19:04 UTC
Honza, is there a way to get at "is this cgraph edge inside a cycle"?  I can
of course compute SCCs myself (pushing the cgraph to graphds for example),
but IIRC some IPA code already computes cgraph cycles.
Comment 7 Jan Hubicka 2019-01-21 16:26:55 UTC
there is ipa_reduced_postorder that will compute SCCs and store scc
Comment 8 Sergei Trofimovich 2019-01-21 21:35:18 UTC
(In reply to Martin Liška from comment #3)
> Confirmed, started with r231498.

That was really fast!

Minor comment: 'git tag' says that revision was added before gcc-6.1.0.  Running test locally says 6.4.0 (and 6.5.0) is also broken. Last working version was gcc-5.5.0.

Or I'm interpreting the field 'Known to work: 6.4.0' incorrectly and it's the token past support horizon?
Comment 9 Richard Biener 2019-01-22 12:52:24 UTC
(In reply to Jan Hubicka from comment #7)
> Hi,
> there is ipa_reduced_postorder that will compute SCCs and store scc
> index.

OK, from looking at examples it seems that I can access node->aux
as ipa_dfs_info * after ipa_reduced_postorder and before I call
ipa_free_postorder_info.  To check whether a call is possibly
recursing to the caller I'd then check whether the callers and the
callees DFS number match.  That works as far as direct calls are
considered - but what about indirect calls?

Not that I'm sure what to do when hitting a possibly recursive call - dropping
all the way to pt_anything for arguments would be a bit harsh.  But whether
ensuring that we do not end up with a singleton composed of caller automatic
vars is enough I'm not sure...
Comment 10 Richard Biener 2019-01-22 14:11:35 UTC
So the idea for the fix is to make locals that escape through recursive edges
behave as if they were really *ptr with ptr pointing to &local, &localp
where localp would be "the other locals".  This could be done on the
constraint level.

Semantically equivalent is doing the above by post-processing the points-to
sets after propagation and replacing 'local' with 'local + localp'.  We'd need
to gather a bitmap of candidate UIDs for this which we could eventually
prune by the set of vars that do not escape through such an edge (implementation
is not entirely clear).

What is missing right now is a conservative predicate telling us whether
defined function X is reachable recursively.  Honza?
Comment 11 Richard Biener 2019-02-05 10:50:41 UTC
Created attachment 45605 [details]
prototype conservative fix

So this is a very conservative fix computing what automatic variables "escape"
and duplicating those with (a single) shadow variable.  It FAILs at least
the following test (though IPA PTA has low testsuite coverage)

FAIL: gcc.dg/ipa/ipa-pta-3.c scan-tree-dump fre3 "Replaced \\*p_2\\(D\\) with 1"

The testcase tests optimization on

static int __attribute__((noinline,noclone))
foo (int *p, int *q)
  *p = 1;
  *q = 0;
  return *p;

extern void abort (void);

int main()
  int a, b;
  if (foo (&a, &b) != 1)
    abort ();
  return 0;

where you see we now compute a and b as escaping and thus add SHADOW to
the points-to sets of both p and q making them appear aliasing.  Missed
optimizations of the patch are
 a) main isn't reached recursively so we never need shadow vars for a or b
 b) we could have used separate shadow vars for a and b

The patch has the opportunity to provide the missing local escaped solution.

In practice the opportunity to cut non-recursively reached functions is
probably low - I've yet have to identify a conservative way to compute this.
Comment 12 Richard Biener 2019-04-12 09:54:41 UTC
Created attachment 46146 [details]
final fix

I am testing the following now which should do less work (but waste more UIDs to be less conservative).  The ipa-pta-3.c testcase is no longer affected, we're more optimistically identifying candidates by just looking at a variables
function parameter solutions and globals for locals recursively reaching a
Comment 13 Richard Biener 2019-04-12 09:56:49 UTC
Testcase using globals instead of parameters:

static int *p;
void bar(int cnt)
  int i = 0;
  if (cnt == 0)
      p = &i;
      bar (1);
      if (i != 1)
        __builtin_abort ();
  else if (cnt == 1)
    *p = 1;
int main()
  bar (0);
  return 0;
Comment 14 Richard Biener 2019-04-15 10:09:39 UTC
Author: rguenth
Date: Mon Apr 15 10:09:08 2019
New Revision: 270366

URL: https://gcc.gnu.org/viewcvs?rev=270366&root=gcc&view=rev
2019-04-15  Richard Biener  <rguenther@suse.de>

	PR ipa/88936
	* tree.h (auto_var_p): Declare.
	* tree.c (auto_var_p): New function, split out from ...
	(auto_var_in_fn_p): ... here.
	* tree-ssa-structalias.c (struct variable_info): Add shadow_var_uid
	(new_var_info): Initialize it.
	(set_uids_in_ptset): Also set the shadow variable uid if required.
	(ipa_pta_execute): Postprocess points-to solutions assigning
	shadow variable uids for locals that may reach their containing
	function recursively.
	* tree-ssa-ccp.c (fold_builtin_alloca_with_align): Do not
	assert but instead check whether the points-to solution is
	a singleton.

	* gcc.dg/torture/pr88936-1.c: New testcase.
	* gcc.dg/torture/pr88936-2.c: Likewise.
	* gcc.dg/torture/pr88936-3.c: Likewise.

Comment 15 Richard Biener 2019-04-15 10:10:18 UTC
Fixed on trunk sofar.
Comment 16 Richard Biener 2019-11-14 07:50:13 UTC
The GCC 7 branch is being closed, re-targeting to GCC 8.4.
Comment 17 Jakub Jelinek 2020-03-04 09:42:11 UTC
GCC 8.4.0 has been released, adjusting target milestone.
Comment 18 Jakub Jelinek 2021-05-14 11:29:33 UTC
The GCC 8 branch is being closed, fixed in GCC 9.1.