Re: [sdcc-devel] A really deep stack

[Erik P. <epe...@iv...>]

On Sun, 25 Dec 2011, Philipp Klaus Krause wrote:

> Am 25.12.2011 07:15, schrieb Erik Petrich:
>>
>> For the past few days the snapshot for Windows 64 bit has been failing the
>> regression tests with a stack overflow when attempting to compile
>> gcc-torture-execute-divcmp-1 for the z80 target. The stack size was 2 MB;
>> I have increased it to 4 MB, which seems to be enough to at least complete
>> the regression tests successfully.
>>
>> To use this much stack, it seems like there would need to be a lot of
>> recursion in conjunction with large local variables. The regression test
>> that was failing to compile has a function that has approximately 100
>> conditions that are sequentially tested, so the flow control graph is
>> quite large. Philipp, I am wondering what you think of this. Is this the
>> sort of memory usage that you would expect using the new register
>> allocator in this situation, or is this a symptom of some unintended
>> allocations that we should look into?
>>
>
> The new register allocator is recursive, and the number of recursive
> calls is O(number of nodes in the control-flow graph). However there
> should be only few, small local variables. Do you have a backtrace of
> the last few calls during the stack overflow?
>
> Philipp

Well, the stack overflow case was happening for the 64-bit Windows 
executable, which I don't know how to debug. However, I can run the x86 
64-bit Linux executable under gdb. It doesn't actually stack overflow, but 
the stack usage is also quite heavy and I can interrupt it while it's deep 
into the recursion. The backtrace looks something like:

(first several levels are in the run-time libraries)

#8  operator= (alist=std::list = {...}, i=225, v=191, G=..., I=...)
     at ./../SDCCralloc.hpp:148
#9  assignments_introduce_variable<boost::adjacency_list<boost::vecS,
boost::vecS, boost::bidirectionalS, cfg_node, boost::no_property,
boost::no_property, boost::listS>, 
boost::adjacency_matrix<boost::undirectedS,
con_node, boost::no_property, boost::no_property, std::allocator<bool> > >
(alist=std::list = {...},
     i=225, v=191, G=..., I=...) at ./../SDCCralloc.hpp:536
#10 0x00000000004bf1f7 in
tree_dec_ralloc_introduce<boost::adjacency_list<boost::vecS,
boost::vecS, boost::bidirectionalS, tree_dec_node, boost::no_property,
boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS,
boost::vecS, boost::bidirectionalS, cfg_node, boost::no_property,
boost::no_property, boost::listS>, 
boost::adjacency_matrix<boost::undirectedS,
con_node, boost::no_property, boost::no_property, std::allocator<bool> > >
(T=<value optimized out>,
     t=<value optimized out>, G=..., I=..., ac=...) at 
./../SDCCralloc.hpp:685
#11 0x00000000004bf526 in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=1564, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:905
#12 0x00000000004bf4ef in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=1999, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:904
#13 0x00000000004bf4ef in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=1563, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:904

(several thousand levels of recursion omitted)

#3132 0x00000000004bf4ef in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=3, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:904
#3133 0x00000000004bf4ef in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=3465, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:904
#3134 0x00000000004bf4ef in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=2, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:904
#3135 0x00000000004bf4ef in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=1, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:904
#3136 0x00000000004bf4ef in
tree_dec_ralloc_nodes<boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, tree_dec_node, boost::no_property, 
boost::no_property,
boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, cfg_node, boost::no_property, boost::no_property,
boost::listS>, con2_t> (T=..., t=0, G=..., I=..., ac=...) at
./../SDCCralloc.hpp:904
#3137 0x00000000004bf8de in tree_dec_ralloc<tree_dec_t, cfg_t, con_t> 
(T=...,
     G=..., I=...) at ralloc2.cc:1232
#3138 0x00000000004b1ec9 in z80_ralloc2_cc (ebbi=<value optimized out>)
     at ralloc2.cc:1331
#3139 0x00000000004ade60 in z80_ralloc (ebbi=0x2baf320) at ralloc.c:3148
#3140 0x0000000000422151 in eBBlockFromiCode (ic=<value optimized out>)
     at SDCCopt.c:2077
#3141 0x000000000043620d in createFunction (name=0x8d03e0, body=0xab1170)
     at SDCCast.c:6628
#3142 0x00000000004050bc in yyparse () at SDCC.y:191
#3143 0x000000000040ddda in main (argc=6, argv=<value optimized out>,
     envp=0x7fffffffe500) at SDCCmain.c:2494

Since I just manually interrupted the program, this is probably not the 
deepest point of the recursion. This still seems like a awefully large 
number of levels of recursion for a program that should have a 
control-flow graph of a bit over 200 nodes (although of course O(n) says 
nothing about what the constant scaling factor is).

Checking the value of the stack pointer register from one frame to the 
next shows that 256 bytes are allocated on the stack for each level of 
recursion at SDCCralloc.hpp:904.

I will be away visiting my parents until next week, so I won't be able to 
do any further testing I return (and depending on the quality of their 
internet connection, may not be able to reply to email either).

   Erik