Propstacklen: A program to calculate SPIN stack sizes
For some time now I've been working on a program that will calculate the stack size required for a SPIN program. It's now at the stage of generating output, and I'd like to gauge how much interest there'd be if I published it in the Obex.
At the moment, I believe the usual way to check stack size is to fill the stack area with longs of some value, and then run the program and see how many get overwritten. The snag with that technique is that it gives only a lower bound for the size - a program run with different inputs may send the stack deeper.
So I wrote propstacklen to carry out a static analysis of the SPIN program, from which the deepest possible stack can be traced. When run, propstacklen reads the .list and .eeprom files that the compiler generated, and generates a report showing the trace of method calls that will produce the maximum stack. In this way, the figures generated in the report are the upper bound on the stack size.
Here's the output from PlayWav_8bit.spin in the WavPlayers Obex object. This is about a simple as it gets, because that program has only two methods: a main method, and one that's called by main(). The maximum stack depth is 80 bytes
The other thing to note is that if you scroll to the bottom of the report, you'll find that BoeBotBasic has two methods (servoProcess and pingProcess) that are opened in seperate cogs. Propstacklen detects this, and reports on the stack sizes those cogs will need.
Not shown here, but some SPIN programs are intended as libraries - not complete programs, but objects to be used within other programs. In such cases, propstacklen can be told to produce a separate report for each PUB method in the top object, giving an indication of the stack impact of using the library.
Propstacklen is a command line program written in C++, so it should run on any platform that has a C++ compiler. It writes its output to the standard output stream. It's developed and has been (minimally) tested under Linux; if it fails to build and run under other operating systems I'll consider that a bug.
Techie note: propstacklen doesn't work on the .spin file. Instead, it uses the .list and .eeprom files as generated by Brad's bstc compiler. That means that it should reflect any compiler optimisations that are applied. It also means that *any* compiler, for any language, that generates SPIN byte code should be covered by it - with the possible need to accommodate that compiler's particular syntax of the list file.
Source code. I don't believe the source code is polished enough for public display, but if I wait until it is you'll never see it :-)
So I've put it on my website here: http://www.jsjf.demon.uk/propstacklen.zip. I would have attached it to this post, but the forum software and Firefox don't seem to play well together in that regard. See the file README.txt for more details of how to use propstacklen.
Update: the latest version is http://www.jsjf.demon.co.uk/propstacklen_0.3.zip.
At the moment, I believe the usual way to check stack size is to fill the stack area with longs of some value, and then run the program and see how many get overwritten. The snag with that technique is that it gives only a lower bound for the size - a program run with different inputs may send the stack deeper.
So I wrote propstacklen to carry out a static analysis of the SPIN program, from which the deepest possible stack can be traced. When run, propstacklen reads the .list and .eeprom files that the compiler generated, and generates a report showing the trace of method calls that will produce the maximum stack. In this way, the figures generated in the report are the upper bound on the stack size.
Here's the output from PlayWav_8bit.spin in the WavPlayers Obex object. This is about a simple as it gets, because that program has only two methods: a main method, and one that's called by main(). The maximum stack depth is 80 bytes
Stack depth report for PlayWav_8bit
Generated by propstacklen version 0.1
========================================================
STACK DEPTH REPORT for Method PlayWav_8bit.Main
All reported values are in decimal notation unless prefixed with 0x
Stack sizes are given in bytes
Main stack starts at 0x7340 and so extends to 0x738f
80 Max stack depth within PlayWav_8bit.Main()
occurs in line 12 at statement:
Player(@Wav,10,11)
24 is the local stack frame depth before the call
to PlayWav_8bit.Player
56 Max stack depth within PlayWav_8bit.Player()
occurs in line 24 at statement:
CTRA:= 110 << 26 + 0<<9 + PinR
========================================================
By way of contrast, here's the much more extensive report for Mike Green's BoeBotBasic:Stack depth report for BoeBotBasic
Generated by propstacklen version 0.1
========================================================
STACK DEPTH REPORT for Method BoeBotBasic.main
All reported values are in decimal notation unless prefixed with 0x
Stack sizes are given in bytes
RECURSION WARNING: Recursion has been detected and will add to the stack size
Main stack starts at 0x4900 and so extends to 0x4b3b
572 Max stack depth within BoeBotBasic.main()
occurs in line 220 at statement:
err := \doline(s)
20 is the local stack frame depth before the call
to BoeBotBasic.doline
552 Max stack depth within BoeBotBasic.doline()
occurs in line 1300 at statement:
texec
20 is the local stack frame depth before the call
to BoeBotBasic.texec
532 Max stack depth within BoeBotBasic.texec()
occurs in line 1284 at statement:
mass.writeExpander(a,specialExpr)
96 is the local stack frame depth before the call
to BoeBotBasic.specialExpr
436 Max stack depth within BoeBotBasic.specialExpr()
occurs in line 666 at statement:
return expr
12 is the local stack frame depth before the call
to BoeBotBasic.expr
424 Max stack depth within BoeBotBasic.expr()
occurs in line 653 at statement:
t := logicAnd
20 is the local stack frame depth before the call
to BoeBotBasic.logicAnd
404 Max stack depth within BoeBotBasic.logicAnd()
occurs in line 643 at statement:
t := logicNot
20 is the local stack frame depth before the call
to BoeBotBasic.logicNot
384 Max stack depth within BoeBotBasic.logicNot()
occurs in line 639 at statement:
return not compare
12 is the local stack frame depth before the call
to BoeBotBasic.compare
372 Max stack depth within BoeBotBasic.compare()
occurs in line 612 at statement:
a := arithExpr
28 is the local stack frame depth before the call
to BoeBotBasic.arithExpr
344 Max stack depth within BoeBotBasic.arithExpr()
occurs in line 599 at statement:
t := term
20 is the local stack frame depth before the call
to BoeBotBasic.term
324 Max stack depth within BoeBotBasic.term()
occurs in line 583 at statement:
t := bitTerm
20 is the local stack frame depth before the call
to BoeBotBasic.bitTerm
304 Max stack depth within BoeBotBasic.bitTerm()
occurs in line 570 at statement:
t := bitFactor
20 is the local stack frame depth before the call
to BoeBotBasic.bitFactor
284 Max stack depth within BoeBotBasic.bitFactor()
occurs in line 560 at statement:
t := shifts
20 is the local stack frame depth before the call
to BoeBotBasic.shifts
264 Max stack depth within BoeBotBasic.shifts()
occurs in line 536 at statement:
t := factor
20 is the local stack frame depth before the call
to BoeBotBasic.factor
244 Max stack depth within BoeBotBasic.factor()
occurs in line 465 at statement:
return mass.getByte
20 is the local stack frame depth before the call
to BB_massStorage.getByte
224 Max stack depth within BB_massStorage.getByte()
occurs in line 170 at statement:
return pgetc
12 is the local stack frame depth before the call
to BB_massStorage.pgetc
212 Max stack depth within BB_massStorage.pgetc()
occurs in line 667 at statement:
t := pfillbuf
16 is the local stack frame depth before the call
to BB_massStorage.pfillbuf
196 Max stack depth within BB_massStorage.pfillbuf()
occurs in line 483 at statement:
fclust := nextcluster
16 is the local stack frame depth before the call
to BB_massStorage.nextcluster
180 Max stack depth within BB_massStorage.nextcluster()
occurs in line 378 at statement:
clust := followchain
16 is the local stack frame depth before the call
to BB_massStorage.followchain
164 Max stack depth within BB_massStorage.followchain()
occurs in line 368 at statement:
clust := brword(readfat(fclust))
20 is the local stack frame depth before the call
to BB_massStorage.readfat
144 Max stack depth within BB_massStorage.readfat()
occurs in line 362 at statement:
return readbytec(fatptr)
16 is the local stack frame depth before the call
to BB_massStorage.readbytec
128 Max stack depth within BB_massStorage.readbytec()
occurs in line 353 at statement:
readblockc(byteloc >> SectorShift)
16 is the local stack frame depth before the call
to BB_massStorage.readblockc
112 Max stack depth within BB_massStorage.readblockc()
occurs in line 268 at statement:
flushifdirty
16 is the local stack frame depth before the call
to BB_massStorage.flushifdirty
96 Max stack depth within BB_massStorage.flushifdirty()
occurs in line 259 at statement:
writeblock2(lastread, @buf2)
12 is the local stack frame depth before the call
to BB_massStorage.writeblock2
84 Max stack depth within BB_massStorage.writeblock2()
occurs in line 250 at statement:
ldr.writeSDCard(n, b, SectorSize)
20 is the local stack frame depth before the call
to BB_i2cSpiLdr.writeSDCard
64 Max stack depth within BB_i2cSpiLdr.writeSDCard()
occurs in line 107 at statement:
return doOperation(def#ioSpiWrite,addr,buffer,count)
24 is the local stack frame depth before the call
to BB_i2cSpiLdr.doOperation
40 Max stack depth within BB_i2cSpiLdr.doOperation()
occurs in line 123 at statement:
long[def#ioControl+4] := (count << 16) | (buffer & $FFFF)
========================================================
STACK DEPTH REPORT for Method BoeBotBasic.servoProcess
All reported values are in decimal notation unless prefixed with 0x
Stack sizes are given in bytes
36 Max stack depth within BoeBotBasic.servoProcess()
occurs in line 1463 at statement:
uS := clkfreq / 1_000_000
========================================================
STACK DEPTH REPORT for Method BoeBotBasic.pingProcess
All reported values are in decimal notation unless prefixed with 0x
Stack sizes are given in bytes
32 Max stack depth within BoeBotBasic.pingProcess()
occurs in line 1490 at statement:
waitpne(0, |< pingData, 0)
========================================================
The first thing to notice is that BoeBotBasic uses recursion. Nothing wrong with that in itself, but it does mean that the stack size is unpredictable as far as a program like propstacklen (or, I believe, any other conceivable program) is concerned. So it reports the stack size for the main program as 572 bytes, but every recursive call will add to that amount. So far, propstacklen merely notes that recursion was detected. It would be possible to improve on that level of reporting, though never to the extent of predicting a maximum stack size when recursion is present.The other thing to note is that if you scroll to the bottom of the report, you'll find that BoeBotBasic has two methods (servoProcess and pingProcess) that are opened in seperate cogs. Propstacklen detects this, and reports on the stack sizes those cogs will need.
Not shown here, but some SPIN programs are intended as libraries - not complete programs, but objects to be used within other programs. In such cases, propstacklen can be told to produce a separate report for each PUB method in the top object, giving an indication of the stack impact of using the library.
Propstacklen is a command line program written in C++, so it should run on any platform that has a C++ compiler. It writes its output to the standard output stream. It's developed and has been (minimally) tested under Linux; if it fails to build and run under other operating systems I'll consider that a bug.
Techie note: propstacklen doesn't work on the .spin file. Instead, it uses the .list and .eeprom files as generated by Brad's bstc compiler. That means that it should reflect any compiler optimisations that are applied. It also means that *any* compiler, for any language, that generates SPIN byte code should be covered by it - with the possible need to accommodate that compiler's particular syntax of the list file.
Source code. I don't believe the source code is polished enough for public display, but if I wait until it is you'll never see it :-)
So I've put it on my website here: http://www.jsjf.demon.uk/propstacklen.zip. I would have attached it to this post, but the forum software and Firefox don't seem to play well together in that regard. See the file README.txt for more details of how to use propstacklen.
Update: the latest version is http://www.jsjf.demon.co.uk/propstacklen_0.3.zip.

Comments
Any ideas? I should add that the program compiles and runs.
The error message it's referring to was the line:
You've found an error in the program.
Could you either post or send by PM your .list and .eeprom files?
I'll look into it. The message you saw was generated by defensive code and should not have happened :-(
Happy bug hunting!
Well, that was exciting. I'm not done yet, but I can present the report for your program:
[john@henry thermo-master]$ propstacklen -q Thermo-Master Stack depth report for Thermo-Master Generated by propstacklen version 0.2 ======================================================== STACK DEPTH REPORT for Method thermo-master.main All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes Main stack starts at 0x44c0 and so extends to 0x455f 160 Max stack depth within thermo-master.main() occurs in line 169 at statement: updateLCDLocal 16 is the local stack frame depth before the call to thermo-master.updateLCDLocal 144 Max stack depth within thermo-master.updateLCDLocal() occurs in line 384 at statement: Comms.str(LCD, FltStr.FloatToFormat(LocTemp, 5, 1)) 20 is the local stack frame depth before the call to FloatString.FloatToFormat 124 Max stack depth within FloatString.FloatToFormat() occurs in line 201 at statement: n := F.FRound(F.FMul(single & $7FFF_FFFF , F.FFloat(teni[dp]))) 36 is the local stack frame depth before the call to FloatMath.FMul 88 Max stack depth within FloatMath.FMul() occurs in line 110 at statement: Unpack(@sa, singleA) 44 is the local stack frame depth before the call to FloatMath.Unpack 44 Max stack depth within FloatMath.Unpack() occurs in line 174 at statement: longmove(pointer, @s, 3) ======================================================== STACK DEPTH REPORT for Method thermo-master.cog_LocalTemp All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes 120 Max stack depth within thermo-master.cog_LocalTemp() occurs in line 190 at statement: Sht.config(33, Sht#off, Sht#yes, Sht#hires) 28 is the local stack frame depth before the call to Sensirion_full.config 92 Max stack depth within Sensirion_full.config() occurs in line 100 at statement: writeStatus((heater << 2) + (OTPreload << 1) + measRes) 28 is the local stack frame depth before the call to Sensirion_full.writeStatus 64 Max stack depth within Sensirion_full.writeStatus() occurs in line 174 at statement: ack := sendCommand(cmd_WriteStatus) 20 is the local stack frame depth before the call to Sensirion_full.sendCommand 44 Max stack depth within Sensirion_full.sendCommand() occurs in line 199 at statement: return writeByte(cmd) 16 is the local stack frame depth before the call to Sensirion_full.writeByte 28 Max stack depth within Sensirion_full.writeByte() occurs in line 232 at statement: dira[dpin] := value >> 7 ======================================================== STACK DEPTH REPORT for Method thermo-master.cog_Remote All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes 160 Max stack depth within thermo-master.cog_Remote() occurs in line 240 at statement: Comms.str(XB, FltStr.FloatToFormat(LocTemp, 5, 1)) 36 is the local stack frame depth before the call to FloatString.FloatToFormat 124 Max stack depth within FloatString.FloatToFormat() occurs in line 201 at statement: n := F.FRound(F.FMul(single & $7FFF_FFFF , F.FFloat(teni[dp]))) 36 is the local stack frame depth before the call to FloatMath.FMul 88 Max stack depth within FloatMath.FMul() occurs in line 110 at statement: Unpack(@sa, singleA) 44 is the local stack frame depth before the call to FloatMath.Unpack 44 Max stack depth within FloatMath.Unpack() occurs in line 174 at statement: longmove(pointer, @s, 3) ======================================================== STACK DEPTH REPORT for Method thermo-master.cog_Log All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes 224 Max stack depth within thermo-master.cog_Log() occurs in line 293 at statement: Drv.popen(@FilName, "a") 20 is the local stack frame depth before the call to fsrw.popen 204 Max stack depth within fsrw.popen() occurs in line 377 at statement: pclose 36 is the local stack frame depth before the call to fsrw.pclose 168 Max stack depth within fsrw.pclose() occurs in line 349 at statement: r := pflush 16 is the local stack frame depth before the call to fsrw.pflush 152 Max stack depth within fsrw.pflush() occurs in line 319 at statement: return pflushbuf(bufat, 1) 12 is the local stack frame depth before the call to fsrw.pflushbuf 140 Max stack depth within fsrw.pflushbuf() occurs in line 276 at statement: readfat(cluststart) 36 is the local stack frame depth before the call to fsrw.readfat 104 Max stack depth within fsrw.readfat() occurs in line 217 at statement: return readbytec(fatptr) 16 is the local stack frame depth before the call to fsrw.readbytec 88 Max stack depth within fsrw.readbytec() occurs in line 209 at statement: readblockc(byteloc >> SECTORSHIFT) 16 is the local stack frame depth before the call to fsrw.readblockc 72 Max stack depth within fsrw.readblockc() occurs in line 131 at statement: flushifdirty 16 is the local stack frame depth before the call to fsrw.flushifdirty 56 Max stack depth within fsrw.flushifdirty() occurs in line 123 at statement: writeblock2(lastread, @buf2) 12 is the local stack frame depth before the call to fsrw.writeblock2 44 Max stack depth within fsrw.writeblock2() occurs in line 115 at statement: sdspi.writeblock(n, b) 20 is the local stack frame depth before the call to sdspiqasm.writeblock 24 Max stack depth within sdspiqasm.writeblock() occurs in line 92 at statement: param := b ======================================================== STACK DEPTH REPORT for Method thermo-master.cog_Button All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes 20 Max stack depth within thermo-master.cog_Button() occurs in line 345 at statement: waitcnt((clkfreq / 5) + cnt) ========================================================You might want to examine the section on cog_Log - if propstacklen is right (big if), you'll be wanting to increase that stack allowance.
I haven't yet published the updated source, because one of the things I had to fix was an error in handling the bytecode generated for the LOOKUPZ spin statement. A similar fix will be needed for LOOKDOWN/LOOKDOWNZ so I'd like to do that before unleashing the next version.
Meanwhile, I hope the report helps.
This is great. I'll be sure to try it out.
Thank you,
Please do - and please be patient if, like JLocke, it doesn't work for you out of the box. I've been testing it on objects pulled more or less at random from the Obex, and clearly I haven't necessarily covered all the possible cases yet.
Suggestions of large and/or complicated Obex programs that might be good exercises are also welcome.
http://www.jsjf.demon.co.uk/propstacklen_0.2.zip
See README.txt for detailed information about the program.
I have (I hope) fixed the problem that DLocke had, and made a few other mainly cosmetic changes. For example, error messages are now clearly marked as such instead of just being buried in the rest of the output.
My test cases still don't include full coverage of the SPIN bytecodes, and I'd be very grateful if someone could suggest an Obex program that makes extensive use of locks in particular.
I'm also contemplating the fact that this tool should work with compilers other than bstc. If anyone's interested in that, I'd need a listing file and eeprom file generated by the compiler. The source language doesn't have to be spin: any compiler that generates spin byte code should be fair game.
Enjoy!
I've made some rather significant changes to my project source, so thought I'd try version 0.2. I built the executable and ran it against my project files, and again came up with an error. Below is the output from the program:
I've attached my .list and .eeprom files for your inspection. Thanks!
The issue is that propstacklen is being confused by a perfectly legitimate trick you're using: breaking a long line of code by terminating it with '{' and starting the next line with '}'. The continuation line then appears in the list file out of the normal sequence.
I need to fix propstacklen, but as a temporary work-round you could try removing those line breaks (there are only four). Propstacklen v0.2 will then process your files.
My problem is that bstc appears to be inconsistent in its own handling of this: sometimes it lists the continuation line, sometimes not. I need to look further into it.
It fixes the problem where using a curly bracketted comment to split long source lines was causing confusion in the parse of the list file. No other changes.
For the second, it's complaining that you ran bstc without specifying the -s flag (which tells bstc to include the source lines in the list file). Since you've been using propstacklen successfully I assume you did use the flag, in which case this is a propstacklen error.
If you'd care to post the list and eeprom files for the failure case, I'll look into it.
And thanks for your patience and all the useful feedback.