Re: Stack analysis tool that really work?

From	Don Y <blockedofcourse@foo.invalid>
Newsgroups	comp.arch.embedded
Subject	Re: Stack analysis tool that really work?
Date	2021-08-03 02:28 -0700
Organization	A noiseless patient Spider
Message-ID	<seb289$ol0$1@dont-email.me> (permalink)
References	<sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me> <imsdtvF7jafU1@mid.individual.net>

Show all headers | View raw

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?

Thread

Stack analysis tool that really work? pozz <pozzugno@gmail.com> - 2021-07-29 18:22 +0200
  Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-07-29 19:36 +0300
  Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-02 17:56 -0700
    Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-03 11:43 +0300
      Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-03 02:28 -0700
        Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-04 22:14 +0300
          Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 15:43 -0700
    Re: Stack analysis tool that really work? pozz <pozzugno@gmail.com> - 2021-08-03 11:49 +0200
      Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-03 20:17 -0700
        Re: Stack analysis tool that really work? pozz <pozzugno@gmail.com> - 2021-08-04 16:43 +0200
          Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 11:06 -0700
            Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 12:00 +0300
              Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-05 04:54 -0700
      Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-04 20:00 +0300
        Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 10:50 -0700
          Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-04 21:50 +0300
            Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 15:46 -0700
              Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 13:43 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-05 06:16 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 18:39 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-06 01:09 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-06 22:58 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-06 16:04 -0700
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-06 16:06 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 14:20 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 10:26 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 20:46 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 15:14 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 14:09 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 08:09 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 19:50 +0300
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 20:02 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 10:34 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 21:10 +0300
                Re: Stack analysis tool that really work? George Neuner <gneuner2@comcast.net> - 2021-08-06 22:55 -0400
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 13:40 +0300
                Re: Stack analysis tool that really work? George Neuner <gneuner2@comcast.net> - 2021-08-08 18:34 -0400
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-09 10:50 +0300
                Re: Stack analysis tool that really work? Paul Rubin <no.email@nospam.invalid> - 2021-08-09 11:26 -0700
                Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-09 22:59 +0300
                Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-09 12:04 -0700
          Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 13:18 +0300
            Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-05 04:59 -0700

csiph-web