arm gcc and Cortex-Mx MCUs embedded systems. Is there a compilation-time (static) tool for stack analysis that really works? The best I could find is -fstack-usage and avstack.pl Perl script, but I guess there's another and better way.
Stack analysis tool that really work?
Started by ●July 29, 2021
Reply by ●July 29, 20212021-07-29
On 2021-07-29 19:22, pozz wrote:> arm gcc and Cortex-Mx MCUs embedded systems. > > Is there a compilation-time (static) tool for stack analysis that really > works? > > The best I could find is -fstack-usage and avstack.pl Perl script, but I > guess there's another and better way.If you can pay, there is https://www.absint.com/stackanalyzer/index.htm. I haven't used it, but I have used other tools from AbsInt (WCET-analysis tools) which worked well, and (I believe) perform stack analysis internally, so I guess the simpler stack-analysis tool also works. There is also https://www.adacore.com/gnatpro/toolsuite/gnatstack, which I have used successfully. I used it for an Ada application, but it should also work for C and C++. Unfortunately I don't know of any free tools for your target.
Reply by ●August 2, 20212021-08-02
On 7/29/2021 9:22 AM, pozz wrote:> arm gcc and Cortex-Mx MCUs embedded systems. > > Is there a compilation-time (static) tool for stack analysis that really works?What do you mean by "really works"? It's a (potentially) unbounded problem as the compiler can't know what the inputs will drive the code to do, in practice. Your best practical option is to tease a callgraph (tree) out and use your own knowledge of what the code WANTS to do to identify the worst-case stack penetration path. This is also a great way to get a feel for if your code might benefit from a good refactoring!> The best I could find is -fstack-usage and avstack.pl Perl script, but I guess > there's another and better way.There are general tools that you can probably instrument to coax a number out of the source (if you don't have access to the source, you're typically SoL) but they will be expensive in time or money.
Reply by ●August 3, 20212021-08-03
On 2021-08-03 3:56, Don Y wrote:> On 7/29/2021 9:22 AM, pozz wrote: >> arm gcc and Cortex-Mx MCUs embedded systems. >> >> Is there a compilation-time (static) tool for stack analysis that >> really works? > > What do you mean by "really works"?� It's a (potentially) unbounded problem > as the compiler can't know what the inputs will drive the code to do, in > practice.There are practical static-analysis methods to compute an upper bound on the stack usage that work well for many embedded programs. An upper bound is usually all one needs. The exact worst case is less interesting. Some problems arise for programs that branch to dynamically computed addresses, for example by calling functions via function pointers. Static analyses may not be able to find the set of possible target addresses. When that happens you have to guide the analysis by specifying where such control transfers can end up. For typical embedded code that is not hard to do, but a program that relies extensively on virtual function calls may be hard to analyze.> There are general tools that you can probably instrument to coax a > number out of the source (if you don't have access to the source, you're > typically SoL) but they will be expensive in time or money.The exact stack usage of a subprogram can't be derived from source code without knowing what machine code the compiler and linker will produce. The static stack-analysis tools typically work on the final executable code (which also means that they can be independent of the programming language). But (as I said in an earlier post) the tools I am aware of, for the OP's target, are not free.
Reply by ●August 3, 20212021-08-03
On 8/3/2021 1:43 AM, Niklas Holsti wrote:> On 2021-08-03 3:56, Don Y wrote: >> On 7/29/2021 9:22 AM, pozz wrote: >>> arm gcc and Cortex-Mx MCUs embedded systems. >>> >>> Is there a compilation-time (static) tool for stack analysis that really works? >> >> What do you mean by "really works"? It's a (potentially) unbounded problem >> as the compiler can't know what the inputs will drive the code to do, in >> practice. > > There are practical static-analysis methods to compute an upper bound on the > stack usage that work well for many embedded programs. An upper bound is > usually all one needs. The exact worst case is less interesting.That depends on the actual algorithm being implemented, the style of the developer and, often, the inputs provided. For example, I often use recursive algorithms for pattern matching (because they are easier to "get right"). Looking at the algorithm, you can't know how deep the recursion will be -- without seeing the input it will be fed. I, OTOH, have intimate knowledge of that input (or, at least *one* half of the comparison) and can ensure the recursion 1) stops and 2) stops at a predictable depth (based on that one half of the comparison). The same for "layered" UI's -- the structure of the user interface is encoded elsewhere; the code that implements it is driven by those structures (which can change -- or be changed -- at runtime). Any analysis (even by human beings) won't provide those figures -- without having a peek at the inputs.> Some problems arise for programs that branch to dynamically computed addresses, > for example by calling functions via function pointers. Static analyses may not > be able to find the set of possible target addresses. When that happens you > have to guide the analysis by specifying where such control transfers can end > up. For typical embedded code that is not hard to do, but a program that relies > extensively on virtual function calls may be hard to analyze.The same is true of a program that is driven by external events. The code doesn't (typically) "know" the constraints placed on those events. (one can argue as to whether or not this is "good practice") So, it can't "find the end".>> There are general tools that you can probably instrument to coax a >> number out of the source (if you don't have access to the source, you're >> typically SoL) but they will be expensive in time or money. > > The exact stack usage of a subprogram can't be derived from source code without > knowing what machine code the compiler and linker will produce. The static > stack-analysis tools typically work on the final executable code (which also > means that they can be independent of the programming language).If you don't have the sources, you can't *do* anything with the results of the analysis -- other than define a minimum stack size (which may be a surprise to you *and* your hardware!) If you don't have the sources, you likely haven't a clue as to how the code behaves, under the complete set of I/O conditions.> But (as I said in an earlier post) the tools I am aware of, for the OP's > target, are not free.You can possibly instrument some DSE-like tools. But, I would imagine the execution time of the tool would be prohibitively long -- for all but trivial codebases. [I should try that when I have some time!] How efficient are those you've used? Do they operate in "near compile time"? Or, something considerably longer (slower)? I.e., are they practical to use iteratively? On an entire application?
Reply by ●August 3, 20212021-08-03
Il 03/08/2021 02:56, Don Y ha scritto:> On 7/29/2021 9:22 AM, pozz wrote: >> arm gcc and Cortex-Mx MCUs embedded systems. >> >> Is there a compilation-time (static) tool for stack analysis that >> really works? > > What do you mean by "really works"?� It's a (potentially) unbounded problem > as the compiler can't know what the inputs will drive the code to do, in > practice.I mean a simple tool that can be instructed, even manually, to produce a good result. -fstack-usage is not usable "by hands". You need at least a call-graph (generated by a tool), fill each branch (function) with a stack usage (generated by the compiler), fill every branch that is not known at compilation time by the tools (call functions by pointers, recursive, and so on). It's surprisingly to me there isn't a single non-expensive tool that helps in this, considering there are a multitude of good free tools for developers.> Your best practical option is to tease a callgraph (tree) out and use your > own knowledge of what the code WANTS to do to identify the worst-case > stack penetration path.� This is also a great way to get a feel for if your > code might benefit from a good refactoring! > >> The best I could find is -fstack-usage and avstack.pl Perl script, but >> I guess there's another and better way. > > There are general tools that you can probably instrument to coax a > number out of the source (if you don't have access to the source, you're > typically SoL) but they will be expensive in time or money.
Reply by ●August 4, 20212021-08-04
On 8/3/2021 2:49 AM, pozz wrote:> Il 03/08/2021 02:56, Don Y ha scritto: >> On 7/29/2021 9:22 AM, pozz wrote: >>> arm gcc and Cortex-Mx MCUs embedded systems. >>> >>> Is there a compilation-time (static) tool for stack analysis that really works? >> >> What do you mean by "really works"? It's a (potentially) unbounded problem >> as the compiler can't know what the inputs will drive the code to do, in >> practice. > > I mean a simple tool that can be instructed, even manually, to produce a good > result.What's "good"? Does it have to solve *most* peoples' needs? Or, just yours? As I said, the first step is understanding what the dynamics of execution in your task happen to be. You may be surprised to see functions being dragged in that you'd not have thought were part of the mix! ("why is printf() being called, here?? and, couldn't I use something like itoa() instead?") The compiler won't know anything about your run-time environment. It won't know if you have a separate stack for ISRs, if the function you are analyzing runs as the "root" of a particular process tree, etc. Do you know how much work is done BEFORE the first line of your function executed? It also won't know which execution paths *will* be exercised in practice. You may have paths that can't be executed (given a particular set of inputs). How will you know to recognize their impact on any figures reported?> -fstack-usage is not usable "by hands".No, but you can use that data *with* the call tree to get an idea of where your maximum lies -- assuming no recursion and worst-case path coverage. You can also fill the stack space with 0x2B00B1E5, run your COMPREHENSIVE test case suite that exercises ALL paths through the code and check to see what the high-water mark was. (you *are* testing the code, right?) Hint: you *really* want tasks to be of the lowest practical complexity that can meet your requirements -- even if that means splitting tasks into more subunits.> You need at least a call-graph (generated by a tool), fill each branch > (function) with a stack usage (generated by the compiler),These can be done with a script (as I suggested below)> fill every branch > that is not known at compilation time by the tools (call functions by pointers, > recursive, and so on).Ah, well... there's the rub! How smart should this "free" tool be? And, how should it handle cases that can't be known at compile time ("Sorry, your codebase appears to need AT LEAST X bytes of stack; but, I can't tell you how much more!" -- what use, that?)> It's surprisingly to me there isn't a single non-expensive tool that helps in > this, considering there are a multitude of good free tools for developers.It costs money to engage in any business (non-hobbyist) endeavor. Expecting all of your tools to be "free" is a bit naive. There are some absolutely *amazing* tools available that can save man-years of development effort and greatly improve the quality/correctness of code. You can buy them -- or, spend man-hours trying to do what they do. Hopefully, without error. And, having *done* that, do it all over again on your NEXT project! <frown>>> Your best practical option is to tease a callgraph (tree) out and use your >> own knowledge of what the code WANTS to do to identify the worst-case >> stack penetration path. This is also a great way to get a feel for if your >> code might benefit from a good refactoring! >> >>> The best I could find is -fstack-usage and avstack.pl Perl script, but I >>> guess there's another and better way. >> >> There are general tools that you can probably instrument to coax a >> number out of the source (if you don't have access to the source, you're >> typically SoL) but they will be expensive in time or money.*Try* building the call tree (there are some graphic tools) and have a look at it. Is it what you expected? Do you understand *why* each function is being invoked in each edge? Then, try to *guess* where the "stack pigs" are located. Finally, see what the compiler tells you for each of them and how well that fits with your "understanding" of the code. [The reason you want to do this is so you have a better feel for the costs of particular approaches -- instead of just reacting to the "final assessment". For example, most newbies are stunned to discover how expensive an off-the-shelf printf() can be!]
Reply by ●August 4, 20212021-08-04
Il 04/08/2021 05:17, Don Y ha scritto:> On 8/3/2021 2:49 AM, pozz wrote: >> Il 03/08/2021 02:56, Don Y ha scritto: >>> On 7/29/2021 9:22 AM, pozz wrote: >>>> arm gcc and Cortex-Mx MCUs embedded systems. >>>> >>>> Is there a compilation-time (static) tool for stack analysis that >>>> really works? >>> >>> What do you mean by "really works"?� It's a (potentially) unbounded >>> problem >>> as the compiler can't know what the inputs will drive the code to do, in >>> practice. >> >> I mean a simple tool that can be instructed, even manually, to produce >> a good result. > > What's "good"?� Does it have to solve *most* peoples' needs?� Or, just > yours?Most peoples' needs that are similar: have a good estimate of stack usage worst case.> As I said, the first step is understanding what the dynamics of execution > in your task happen to be.� You may be surprised to see functions being > dragged in that you'd not have thought were part of the mix!� ("why is > printf() being called, here??� and, couldn't I use something like itoa() > instead?")Oh yes, but a simple tool that generates automatically a call graph could be very useful for this.> The compiler won't know anything about your run-time environment.� It won't > know if you have a separate stack for ISRs, if the function you are > analyzing > runs as the "root" of a particular process tree, etc.� Do you know how much > work is done BEFORE the first line of your function executed? > > It also won't know which execution paths *will* be exercised in practice. > You may have paths that can't be executed (given a particular set of > inputs).� How will you know to recognize their impact on any figures > reported?I know that compiler can't know everything, but *I* can instruct the tool with that kind of info.>> -fstack-usage is not usable "by hands". > > No, but you can use that data *with* the call tree to get an idea of > where your maximum lies -- assuming no recursion and worst-case path > coverage.I think this job could be done by a single tool that creates a call graph and fill in the values from stack usage.> You can also fill the stack space with 0x2B00B1E5, run your COMPREHENSIVE > test case suite that exercises ALL paths through the code and check to see > what the high-water mark was.� (you *are* testing the code, right?)This is the dynamic approach, I was exploring the static approach.> Hint:� you *really* want tasks to be of the lowest practical complexity > that can meet your requirements -- even if that means splitting tasks > into more subunits. > >> You need at least a call-graph (generated by a tool), fill each branch >> (function) with a stack usage (generated by the compiler), > > These can be done with a script (as I suggested below) > >> fill every branch that is not known at compilation time by the tools >> (call functions by pointers, recursive, and so on). > > Ah, well... there's the rub!� How smart should this "free" tool be? > And, how should it handle cases that can't be known at compile time > ("Sorry, your codebase appears to need AT LEAST X bytes of stack; but, > I can't tell you how much more!" -- what use, that?) > >> It's surprisingly to me there isn't a single non-expensive tool that >> helps in this, considering there are a multitude of good free tools >> for developers. > > It costs money to engage in any business (non-hobbyist) endeavor. > Expecting all of your tools to be "free" is a bit naive.Anyway there are plenty of complex and good free and open-source software (gcc is one of them). So it's strange there isn't a similar tool for stack analysis. That's all, it's strange for me, but I don't pretend all my preferred tools must be free.> There are some absolutely *amazing* tools available that can save > man-years of development effort and greatly improve the quality/correctness > of code.� You can buy them -- or, spend man-hours trying to do what they > do.� Hopefully, without error. > > And, having *done* that, do it all over again on your NEXT project! > > <frown>Yes, I know these are the only solutions. I was asking if a free tool really existed but I didn't knew it.>>> Your best practical option is to tease a callgraph (tree) out and use >>> your >>> own knowledge of what the code WANTS to do to identify the worst-case >>> stack penetration path.� This is also a great way to get a feel for >>> if your >>> code might benefit from a good refactoring! >>> >>>> The best I could find is -fstack-usage and avstack.pl Perl script, >>>> but I guess there's another and better way. >>> >>> There are general tools that you can probably instrument to coax a >>> number out of the source (if you don't have access to the source, you're >>> typically SoL) but they will be expensive in time or money. > > *Try* building the call tree (there are some graphic tools) and > have a look at it.� Is it what you expected?� Do you understand > *why* each function is being invoked in each edge? > > Then, try to *guess* where the "stack pigs" are located. > > Finally, see what the compiler tells you for each of them and > how well that fits with your "understanding" of the code. > > [The reason you want to do this is so you have a better feel > for the costs of particular approaches -- instead of just > reacting to the "final assessment".� For example, most newbies > are stunned to discover how expensive an off-the-shelf > printf() can be!]
Reply by ●August 4, 20212021-08-04
On 2021-08-03 12:49, pozz wrote:> Il 03/08/2021 02:56, Don Y ha scritto: >> On 7/29/2021 9:22 AM, pozz wrote: >>> arm gcc and Cortex-Mx MCUs embedded systems. >>> >>> Is there a compilation-time (static) tool for stack analysis that >>> really works? >> >> What do you mean by "really works"? It's a (potentially) unbounded >> problem as the compiler can't know what the inputs will drive the >> code to do, in practice. > > I mean a simple tool that can be instructed, even manually, to > produce a good result. > > -fstack-usage is not usable "by hands". > > You need at least a call-graph (generated by a tool), fill each > branch (function) with a stack usage (generated by the compiler), > fill every branch that is not known at compilation time by the tools > (call functions by pointers, recursive, and so on). > > It's surprisingly to me there isn't a single non-expensive tool that > helps in this, considering there are a multitude of good free tools > for developers.One reason is that for good results, such a tool has to analyze the executable code, and therefore must be target-specific, or at least have ports to the various targets, increasing the effort to implement and maintain the tool. The gnatstack tool gets around that, to some extent, by relying on stack-usage and call information from the compiler (gcc). Note that a source-level call graph will not show calls to the various support routines (run-time routines) inserted by the compiler, but those calls do use stack. I am the main author of a WCET-analysis tool, Bound-T, that also does stack analysis and is now free. However, there is (as yet) no port for ARM Cortex-M. See http://www.bound-t.com/.
Reply by ●August 4, 20212021-08-04
On 8/4/2021 10:00 AM, Niklas Holsti wrote:> On 2021-08-03 12:49, pozz wrote: >> Il 03/08/2021 02:56, Don Y ha scritto: >>> On 7/29/2021 9:22 AM, pozz wrote: >>>> arm gcc and Cortex-Mx MCUs embedded systems. >>>> >>>> Is there a compilation-time (static) tool for stack analysis that >>>> really works? >>> >>> What do you mean by "really works"? It's a (potentially) unbounded >>> problem as the compiler can't know what the inputs will drive the >>> code to do, in practice. >> >> I mean a simple tool that can be instructed, even manually, to >> produce a good result. >> >> -fstack-usage is not usable "by hands". >> >> You need at least a call-graph (generated by a tool), fill each >> branch (function) with a stack usage (generated by the compiler), >> fill every branch that is not known at compilation time by the tools >> (call functions by pointers, recursive, and so on). >> >> It's surprisingly to me there isn't a single non-expensive tool that >> helps in this, considering there are a multitude of good free tools >> for developers. > > > One reason is that for good results, such a tool has to analyze the executable > code, and therefore must be target-specific, or at least have ports to the > various targets, increasing the effort to implement and maintain the tool. The > gnatstack tool gets around that, to some extent, by relying on stack-usage and > call information from the compiler (gcc).I am seeing an increasing number of tools relying on intermediate encodings (e.g., via LLVM) to give more portability to their application. But, then you're stuck *needing* access to the sources.> Note that a source-level call graph > will not show calls to the various support routines (run-time routines) > inserted by the compiler, but those calls do use stack. > > I am the main author of a WCET-analysis tool, Bound-T, that also does stack > analysis and is now free. However, there is (as yet) no port for ARM Cortex-M. > See http://www.bound-t.com/.But not free as in open (?)