Re: [RFC] Massive recursion in tree_ssa_phiprop_1?
On Sat, Apr 18, 2009 at 7:01 PM, Dave Korn
wrote:
>
> Hi,
>
> I'm getting a stack overflow caused by *very* deep recursion while trying to
> build gnu/javax/swing/text/html/parser/HTML_401F.o in libjava, bootstrapping
> HEAD on i686-pc-cygwin.
>
> With the default per-thread stack size of 2MB, it crashes in
> tree_ssa_phiprop_1(), which by the time of the crash has recursed to a depth
> that I can actually honestly describe as "OVER 9000"! If I boost the stack to
> 4MB, I find that the recursion does actually bottom out at some point, since
> the compile completes, but I tested at 3MB and it crashed at a recursion depth
> of 13924.
>
> I know that boostrapping libjava is a tough job and pretty intensive on
> memory demands, but is this level of nesting actually to be expected, or has
> something gone astray?
Well, this is one of the usual ways of iterating over the CFG, so this
is certainly
not unexpected. Maybe for some reason gsi is not scalarized and stack usage
of that function is unusually high?
Richard.
> cheers,
> DaveK
> --
> Breakpoint 1, tree_ssa_phiprop_1 (bb=0x7efd0580, phivn=0x3d3c9a8, n=150236)
> at /gnu/gcc/gcc/gcc/tree-ssa-phiprop.c:333
> 333 {
> (gdb) bt -13
> #9198 0x007e069c in tree_ssa_phiprop_1 (bb=,
> phivn=, n=150236)
> at /gnu/gcc/gcc/gcc/tree-ssa-phiprop.c:344
> #9199 0x007e069c in tree_ssa_phiprop_1 (bb=,
> phivn=, n=150236)
> at /gnu/gcc/gcc/gcc/tree-ssa-phiprop.c:344
> #9200 0x007e069c in tree_ssa_phiprop_1 (bb=,
> phivn=, n=150236)
> at /gnu/gcc/gcc/gcc/tree-ssa-phiprop.c:344
> #9201 0x007e1063 in tree_ssa_phiprop ()
> at /gnu/gcc/gcc/gcc/tree-ssa-phiprop.c:360
> #9202 0x0053d646 in execute_one_pass (pass=)
> at /gnu/gcc/gcc/gcc/passes.c:1290
> #9203 0x0053d8ac in execute_pass_list (pass=0xbb4b80)
> at /gnu/gcc/gcc/gcc/passes.c:1339
> #9204 0x0053d8bf in execute_pass_list (pass=0xbb3e60)
> at /gnu/gcc/gcc/gcc/passes.c:1340
> #9205 0x0079f5e0 in tree_rest_of_compilation (fndecl=0x7ff72c80)
> at /gnu/gcc/gcc/gcc/tree-optimize.c:437
> #9206 0x005b8bc5 in cgraph_expand_function (node=0x7ff74c00)
> at /gnu/gcc/gcc/gcc/cgraphunit.c:1048
> #9207 0x005ba950 in cgraph_optimize () at /gnu/gcc/gcc/gcc/cgraphunit.c:1107
> #9208 0x00443e4a in java_parse_file (set_yydebug=0)
> at /gnu/gcc/gcc/gcc/java/jcf-parse.c:1987
> #9209 0x00475b64 in toplev_main (argc=32, argv=0x2f19be8)
> at /gnu/gcc/gcc/gcc/toplev.c:976
> #9210 0x0044e2f0 in main (argc=32, argv=0x2f19be8)
> at /gnu/gcc/gcc/gcc/main.c:35
> (gdb) print *bb
> $1 = {preds = 0x7d1e2920, succs = 0x7d1e2980, aux = 0x0, loop_father = 0x0,
> dom = {0x3b3c798, 0x0}, prev_bb = 0x7efd0540, next_bb = 0x7efd05c0, il = {
> gimple = 0x7f10ba80, rtl = 0x7f10ba80}, count = 0, index = 18400,
> loop_depth = 0, frequency = 252, flags = 3}
> (gdb) print *bb->dom[0]
> $2 = {data = 0x7efd0580, dfs_num_in = 9200, dfs_num_out = 34433,
> father = 0x3b3c738, son = 0x3b3c7f8, left = 0x3b3c768, right = 0x3b3c768,
> rightmost_occ = 0x3b3fcd0, parent_occ = 0x3768630}
> (gdb) print *bb->dom[0]->son
> $3 = {data = 0x7efd0600, dfs_num_in = 9201, dfs_num_out = 34430,
> father = 0x3b3c798, son = 0x3b3c858, left = 0x3b3c7c8, right = 0x3b3c7c8,
> rightmost_occ = 0x3b3fd20, parent_occ = 0x3768680}
> (gdb) print *bb->dom[0]->son->son
> $4 = {data = 0x7efd0700, dfs_num_in = 9202, dfs_num_out = 34427,
> father = 0x3b3c7f8, son = 0x3b3c8b8, left = 0x3b3c828, right = 0x3b3c828,
> rightmost_occ = 0x3b3fd70, parent_occ = 0x37686d0}
> (gdb) print *bb->dom[0]->son->son->son
> $5 = {data = 0x7efd07c0, dfs_num_in = 9203, dfs_num_out = 34424,
> father = 0x3b3c858, son = 0x3b3c918, left = 0x3b3c888, right = 0x3b3c888,
> rightmost_occ = 0x3b3fdc0, parent_occ = 0x3768720}
> (gdb) print *bb->dom[0]->son->son->son->son
> $6 = {data = 0x7efd0840, dfs_num_in = 9204, dfs_num_out = 34421,
> father = 0x3b3c8b8, son = 0x3b3c978, left = 0x3b3c8e8, right = 0x3b3c8e8,
> rightmost_occ = 0x3b3fe10, parent_occ = 0x3768770}
> (gdb) print *bb->dom[0]->son->son->son->son->son->son->son->son->son->son->son
> ->son
> $7 = {data = 0x7efd0e80, dfs_num_in = 9212, dfs_num_out = 34397,
> father = 0x3b3cbb8, son = 0x3b3cc78, left = 0x3b3cbe8, right = 0x3b3cbe8,
> rightmost_occ = 0x3b40090, parent_occ = 0x37689f0}
> (gdb) print *bb->dom[0]->son->son->son->son->son->son->son->son->son->son->son
> ->son->son->son->son->son->son->son->son->son->son->son->son->son
> $8 = {data = 0x7efd1780, dfs_num_in = 9224, dfs_num_out = 34361,
> father = 0x3b3d038, son = 0x3b3d0f8, left = 0x3b3d068, right = 0x3b3d068,
> rightmost_occ = 0x3b40450, parent_occ = 0x3768db0}
> (gdb) print *bb->dom[0]->son->son->son->son->son->son->son->son->son->son->son
> ->son->son->son->son->son->son->son->son->son->son->son->son->son->son->son->s
> on->son->son->son->son->son->son->son->son->son->son->son->son->son->son->son-
>>son->son->son->son->son->son->son->son->son->son->son->son->son->son
> $9 = {data = 0x7efd2f80, dfs_num_in = 9256, dfs_num_out = 3426
Re: [RFC] Massive recursion in tree_ssa_phiprop_1?
Richard Guenther wrote:
> On Sat, Apr 18, 2009 at 7:01 PM, Dave Korn
> wrote:
>> With the default per-thread stack size of 2MB, it crashes in
>> tree_ssa_phiprop_1(), which by the time of the crash has recursed to a depth
>> that I can actually honestly describe as "OVER 9000"! If I boost the stack
>> to
>> 4MB, I find that the recursion does actually bottom out at some point, since
>> the compile completes, but I tested at 3MB and it crashed at a recursion
>> depth
>> of 13924.
>>
>> I know that boostrapping libjava is a tough job and pretty intensive on
>> memory demands, but is this level of nesting actually to be expected, or has
>> something gone astray?
>
> Well, this is one of the usual ways of iterating over the CFG, so this
> is certainly not unexpected.
It appears to be the only pass that gets anywhere near this level of stack
usage, if I gate it off the compilation completes successfully.
> Maybe for some reason gsi is not scalarized and stack usage
> of that function is unusually high?
Yes, I suspect it's as simple as that. The function itself is
defineElements() in
libjava/classpath/gnu/javax/swing/text/html/parser/HTML_401F.java, and it's
got a huge long sequence of function calls to a function called defElement(),
each of which contain numerous constructors creating array arguments for the
call, e.g.
defElement(SUB, 0, false, false, null,
NONE
,
new String[] {
PCDATA, A, ABBR, ACRONYM,
APPLET, B, BASEFONT, BDO, BIG,
BR, BUTTON, CITE, CODE, DFN,
EM, FONT, I, IFRAME, IMG,
INPUT, KBD, LABEL, MAP, OBJECT,
Q, S, SAMP, SCRIPT, SELECT,
SMALL, SPAN, STRIKE, STRONG, SUB,
SUP, TEXTAREA, TT, U, VAR
}
,
new AttributeList[] {
attr(sID, null, null, ID, IMPLIED),
attr(CLASS, null, null, 0, IMPLIED),
attr(STYLE, null, null, 0, IMPLIED),
attr(TITLE, null, null, 0, IMPLIED),
attr(LANG, null, null, 0, IMPLIED),
attr(DIR, null, new String[] { LTR, RTL }, 0, IMPLIED),
attr(ONCLICK, null, null, 0, IMPLIED),
attr(ONDBLCLICK, null, null, 0, IMPLIED),
attr(ONMOUSEDOWN, null, null, 0, IMPLIED),
attr(ONMOUSEUP, null, null, 0, IMPLIED),
attr(ONMOUSEOVER, null, null, 0, IMPLIED),
attr(ONMOUSEMOVE, null, null, 0, IMPLIED),
attr(ONMOUSEOUT, null, null, 0, IMPLIED),
attr(ONKEYPRESS, null, null, 0, IMPLIED),
attr(ONKEYDOWN, null, null, 0, IMPLIED),
attr(ONKEYUP, null, null, 0, IMPLIED)
}
);
and that's one of the shorter examples, and this goes on for thousands of
lines, so I think I can believe that there really are that many BBs and that
level of dominator nesting. Thanks for commenting; I'll just turn up my
per-thread stack allocation and not worry about it.
cheers,
DaveK
Re: [RFC] Massive recursion in tree_ssa_phiprop_1?
> On Sat, Apr 18, 2009 at 7:01 PM, Dave Korn > wrote: > > > > Hi, > > > > I'm getting a stack overflow caused by *very* deep recursion while trying > > to > > build gnu/javax/swing/text/html/parser/HTML_401F.o in libjava, bootstrapping > > HEAD on i686-pc-cygwin. > > > > With the default per-thread stack size of 2MB, it crashes in > > tree_ssa_phiprop_1(), which by the time of the crash has recursed to a depth > > that I can actually honestly describe as "OVER 9000"! If I boost the stack > > to > > 4MB, I find that the recursion does actually bottom out at some point, since > > the compile completes, but I tested at 3MB and it crashed at a recursion > > depth > > of 13924. > > > > I know that boostrapping libjava is a tough job and pretty intensive on > > memory demands, but is this level of nesting actually to be expected, or has > > something gone astray? > > Well, this is one of the usual ways of iterating over the CFG, so this > is certainly > not unexpected. Maybe for some reason gsi is not scalarized and stack usage > of that function is unusually high? There used to be rule that we should not expect CFG walk to fit in stack. I.e. all CFG walking needs to be written with explicit worklist/stack instead of using recursion. Perhaps it should enforce it here too? :) Honza
Re: [RFC] Massive recursion in tree_ssa_phiprop_1?
2009/4/19 Jan Hubicka : >> On Sat, Apr 18, 2009 at 7:01 PM, Dave Korn >> wrote: >> > >> > Hi, >> > >> > I'm getting a stack overflow caused by *very* deep recursion while trying >> > to >> > build gnu/javax/swing/text/html/parser/HTML_401F.o in libjava, >> > bootstrapping >> > HEAD on i686-pc-cygwin. >> > >> > With the default per-thread stack size of 2MB, it crashes in >> > tree_ssa_phiprop_1(), which by the time of the crash has recursed to a >> > depth >> > that I can actually honestly describe as "OVER 9000"! If I boost the >> > stack to >> > 4MB, I find that the recursion does actually bottom out at some point, >> > since >> > the compile completes, but I tested at 3MB and it crashed at a recursion >> > depth >> > of 13924. >> > >> > I know that boostrapping libjava is a tough job and pretty intensive on >> > memory demands, but is this level of nesting actually to be expected, or >> > has >> > something gone astray? >> >> Well, this is one of the usual ways of iterating over the CFG, so this >> is certainly >> not unexpected. Maybe for some reason gsi is not scalarized and stack usage >> of that function is unusually high? > > There used to be rule that we should not expect CFG walk to fit in > stack. I.e. all CFG walking needs to be written with explicit > worklist/stack instead of using recursion. Perhaps it should enforce it > here too? :) Well ... in this case it's likely the problem that propagate_with_phi is inlined (single-use static function) and maybe other helpers of it too. Maybe we should instead throttle inlining into functions that recurse? ;) Richard. > > Honza >
Re: [RFC] Massive recursion in tree_ssa_phiprop_1?
> 2009/4/19 Jan Hubicka : > >> On Sat, Apr 18, 2009 at 7:01 PM, Dave Korn > >> wrote: > >> > > >> > Hi, > >> > > >> > I'm getting a stack overflow caused by *very* deep recursion while > >> > trying to > >> > build gnu/javax/swing/text/html/parser/HTML_401F.o in libjava, > >> > bootstrapping > >> > HEAD on i686-pc-cygwin. > >> > > >> > With the default per-thread stack size of 2MB, it crashes in > >> > tree_ssa_phiprop_1(), which by the time of the crash has recursed to a > >> > depth > >> > that I can actually honestly describe as "OVER 9000"! If I boost the > >> > stack to > >> > 4MB, I find that the recursion does actually bottom out at some point, > >> > since > >> > the compile completes, but I tested at 3MB and it crashed at a recursion > >> > depth > >> > of 13924. > >> > > >> > I know that boostrapping libjava is a tough job and pretty intensive on > >> > memory demands, but is this level of nesting actually to be expected, or > >> > has > >> > something gone astray? > >> > >> Well, this is one of the usual ways of iterating over the CFG, so this > >> is certainly > >> not unexpected. Maybe for some reason gsi is not scalarized and stack > >> usage > >> of that function is unusually high? > > > > There used to be rule that we should not expect CFG walk to fit in > > stack. I.e. all CFG walking needs to be written with explicit > > worklist/stack instead of using recursion. Perhaps it should enforce it > > here too? :) > > Well ... in this case it's likely the problem that propagate_with_phi is > inlined (single-use static function) and maybe other helpers of it too. > Maybe we should instead throttle inlining into functions that recurse? ;) There is stack frame growth limit parameter for inliner, we can experiment with setting these lower. It seemed that it does not reduce performance, but since stack usage params was made primarily for kernel I didn't didn't care much to see if they can be trottled down for normal code. Trottling even lower for functions lying in SCC of cgraph seems good idea too. Honza > > Richard. > > > > > Honza > >
Re: [gnat] reuse of ASTs already constructed
Anybody out there? How about not doing the name expansion in-place but rather storing the expanded name in an extra node field? --Oliver On 2009-04-18 at 21:35 +0200, Oliver Kellogg wrote: > I've run up against a problem with reusing the GNAT trees: > Apparently during semantic analysis entity names are expanded > to their fully qualified names in the tree. > > For example, when compiling the following file with the node > for System already installed by a previous compilation, > > -- file: ext.ads > with System; > procedure Ext (Addr : System.Address); > > I get the following error from sem_ch8.adb Find_Expanded_Name > during semantic analysis of the above System.Address, > > ext.ads:3:29: "Address" is not a visible entity of "System" > > This is because in sem_ch8.adb:4482, > > if No (Id) or else Chars (Id) /= Chars (Selector) then ... > > the second part of the condition becomes true as Chars(Id) is > "system__address" [and Chars(Selector) is "address"]. > When compiling the same file afresh without preinstalled nodes, > Chars(Id) is just "address" and all is fine. > > Oliver > > > On 2009-04-12 at 19:29 +0200, Oliver Kellogg wrote: > > Picking up an old thread, > > http://gcc.gnu.org/ml/gcc/2003-03/msg00281.html > > > > > > On Tue, 4 Mar 2003, Geert Bosch wrote: > > > [...] > > > Best would be to first post a design overview, > > > before doing a lot of work in order to prevent spending time > > > on implementing something that may turn out to have fundamental > > > problems. > > > > I've done a little experimenting to get a feel for this. > > > > I've looked at the work done toward the GCC compile server but > > decided that I want to concentrate on GNAT trees (whereas the > > compile server targets the GNU trees.) > > > > Also I am aiming somewhat lower - not making a separate compile > > server process but rather extending gnat1 to handle multiple > > files in a single invocation. > > > > The current GNAT code makes a strong assumption that there be > > only one main unit, and this Main_Unit be located at index 0 of > > Lib.Units.Table (see procedure Lib.Load.Load_Main_Source). > > > > I am currently looking at having each main unit supplied on > > the gnat1 command line overwrite the Main_Unit in the Units table. > > > > What do you think of this approach? > > > > The attached patch sets the stage for passing multiple source > > files to a single gnat1 invocation. (Beware, this is a rough cut. > > Best use "svn diff --diff-cmd diff -x -uw" after applying as > > there are many changes that only affect indentation.) > > > > Thanks, > > > > Oliver > > > >
gcc-4.3-20090419 is now available
Snapshot gcc-4.3-20090419 is now available on ftp://gcc.gnu.org/pub/gcc/snapshots/4.3-20090419/ and on various mirrors, see http://gcc.gnu.org/mirrors.html for details. This snapshot has been generated from the GCC 4.3 SVN branch with the following options: svn://gcc.gnu.org/svn/gcc/branches/gcc-4_3-branch revision 146360 You'll find: gcc-4.3-20090419.tar.bz2 Complete GCC (includes all of below) gcc-core-4.3-20090419.tar.bz2 C front end and core compiler gcc-ada-4.3-20090419.tar.bz2 Ada front end and runtime gcc-fortran-4.3-20090419.tar.bz2 Fortran front end and runtime gcc-g++-4.3-20090419.tar.bz2 C++ front end and runtime gcc-java-4.3-20090419.tar.bz2 Java front end and runtime gcc-objc-4.3-20090419.tar.bz2 Objective-C front end and runtime gcc-testsuite-4.3-20090419.tar.bz2The GCC testsuite Diffs from 4.3-20090412 are available in the diffs/ subdirectory. When a particular snapshot is ready for public consumption the LATEST-4.3 link is updated and a message is sent to the gcc list. Please do not use a snapshot before it has been announced that way.
vector<> issue in g++?
I don't think this is a bug but certainly it is a problem.
Would you please consider it and let me know? I hope so. Thanks.
The following simple volcalc.cpp code compiles with no errors (and
works) in Windows Visual C++.
It simply sizes the "alldata" array later in the code.
With g++ v.4.3.2 instead I get the error reported hereby.
For some reason it does not like the fact that struct is declared
local. If you declare struct as global it will be working but I cannot
change the code so drastically.
I would thankfully appreciate any help (including tough critics to the code).
volcalc.cpp:26: error: template argument for ‘template
class std::allocator’ uses local type ‘main(int, char**)::series’
volcalc.cpp:26: error: trying to instantiate ‘template
class std::allocator’
volcalc.cpp:26: error: template argument 2 is invalid
volcalc.cpp:66: error: request for member ‘resize’ in ‘alldata’, which
is of non-class type ‘int’
int main(int argc, char *argv[])
{
struct series {
};
int nr;
vector alldata; // line 26
// calculate nr as int.
alldata.resize(nr); // line 66
}
Re: vector<> issue in g++?
On Sun, Apr 19, 2009 at 4:15 PM, Paolo Piacentini wrote: > I don't think this is a bug but certainly it is a problem. > > Would you please consider it and let me know? I hope so. Thanks. > > The following simple volcalc.cpp code compiles with no errors (and > works) in Windows Visual C++. > It simply sizes the "alldata" array later in the code. If Visual C++ does not diagnose the error in the code in its best standards-conforming mode, that is a bug in Visual C++. Allowing it as an extension is an entirely reasonable thing to do though. > With g++ v.4.3.2 instead I get the error reported hereby. > For some reason it does not like the fact that struct is declared > local. That is what C++ requires; template parameters must have external linkage, and in C++98 local types do not have external linkage. > If you declare struct as global it will be working but I cannot > change the code so drastically. > > I would thankfully appreciate any help (including tough critics to the code). The "drastic" change would be needed to make your code valid C++, and if you do that then g++ will compile it. There has been discussion of changing this rule for the next C++ standard, see e.g., http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2402.pdf though I don't see signs of it having been merged into the current committee draft. N2402 does mention the change in MSVC++ as being a relatively recent extension. A quick search hasn't turned up the current status of N2402, though there was some discussion of weakening it by removing support for using unnamed types as template parameters, and it seemed to have reasonably strong support in that form. -- James
Re: [RFC] Massive recursion in tree_ssa_phiprop_1?
Richard Guenther wrote: > > Well ... in this case it's likely the problem that propagate_with_phi is > inlined (single-use static function) and maybe other helpers of it too. It is inlined. I rebuilt jc1 after adding __attribute__ ((noinline)), and the stack frame size for tree_ssa_phiprop_1 went down from 0xcc to 0x3c, so that buys us some breathing room, but the problem is still lurking there; compilation of a larger function could still trip it. (It saved enough headroom for my trial build of the libjava html parser to complete successfully.) Should we be concerned that end-users might run into this in real-world situations when they're compiling large files of bulk auto-generated code? cheers, DaveK
Re: GCC 4.3.2 bug (was: Illegal subtraction in tmp-dive_1.s)
> Vincent Lefevre writes: >while ((*(q++))-- == 0) ; Is that defined and legal?? Is q incremented before or after *q is decremented? They are both post operators! Jason Mancini _ Rediscover Hotmail®: Get e-mail storage that grows with you. http://windowslive.com/RediscoverHotmail?ocid=TXT_TAGLM_WL_HM_Rediscover_Storage2_042009
Re: [RFC] Massive recursion in tree_ssa_phiprop_1?
Dave Korn wrote:
> Richard Guenther wrote:
>
>> Well ... in this case it's likely the problem that propagate_with_phi is
>> inlined (single-use static function) and maybe other helpers of it too.
>
> It is inlined. I rebuilt jc1 after adding __attribute__ ((noinline)), and
> the stack frame size for tree_ssa_phiprop_1 went down from 0xcc to 0x3c, so
> that buys us some breathing room, but the problem is still lurking there;
> compilation of a larger function could still trip it. (It saved enough
> headroom for my trial build of the libjava html parser to complete
> successfully.)
>
> Should we be concerned that end-users might run into this in real-world
> situations when they're compiling large files of bulk auto-generated code?
Indeed we should use dom-walk.c, or better copy the worklist approach
from it.
worklist[sp++] = ENTRY_BLOCK_PTR;
while (sp)
{
bb = worklist[--sp];
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
did_something |= propagate_with_phi (bb, gsi_stmt (gsi), phivn, n);
for (dest = first_dom_son (walk_data->dom_direction, bb);
dest; dest = next_dom_son (walk_data->dom_direction, dest))
worklist[sp++] = dest;
}
return did_something;
Paolo
