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 COLLECT_GCC=./xgcc COLLECT_LTO_WRAPPER=./lto-wrapper 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)
Created attachment 45476 [details] main,c
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
Confirmed, started with r231498.
Mine.
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%] else 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?
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.
Hi, there is ipa_reduced_postorder that will compute SCCs and store scc index.
(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?
(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...
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?
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.
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 function.
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; }
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 Log: 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 member. (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. Added: trunk/gcc/testsuite/gcc.dg/torture/pr88936-1.c trunk/gcc/testsuite/gcc.dg/torture/pr88936-2.c trunk/gcc/testsuite/gcc.dg/torture/pr88936-3.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-ccp.c trunk/gcc/tree-ssa-structalias.c trunk/gcc/tree.c trunk/gcc/tree.h
Fixed on trunk sofar.
The GCC 7 branch is being closed, re-targeting to GCC 8.4.
GCC 8.4.0 has been released, adjusting target milestone.
The GCC 8 branch is being closed, fixed in GCC 9.1.