Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

When I left you, I was but the pupil. Now, I am the master. -- Darth Vader


devel / comp.arch.embedded / Re: Stack analysis tool that really work?

SubjectAuthor
* Stack analysis tool that really work?pozz
+- Re: Stack analysis tool that really work?Niklas Holsti
`* Re: Stack analysis tool that really work?Don Y
 +* Re: Stack analysis tool that really work?Niklas Holsti
 |`* Re: Stack analysis tool that really work?Don Y
 | `* Re: Stack analysis tool that really work?Niklas Holsti
 |  `- Re: Stack analysis tool that really work?Don Y
 `* Re: Stack analysis tool that really work?pozz
  +* Re: Stack analysis tool that really work?Don Y
  |`* Re: Stack analysis tool that really work?pozz
  | `* Re: Stack analysis tool that really work?Don Y
  |  `* Re: Stack analysis tool that really work?Niklas Holsti
  |   `- Re: Stack analysis tool that really work?Don Y
  `* Re: Stack analysis tool that really work?Niklas Holsti
   `* Re: Stack analysis tool that really work?Don Y
    +* Re: Stack analysis tool that really work?Niklas Holsti
    |`* Re: Stack analysis tool that really work?Don Y
    | `* Re: Stack analysis tool that really work?Niklas Holsti
    |  `* Re: Stack analysis tool that really work?Don Y
    |   `* Re: Stack analysis tool that really work?Niklas Holsti
    |    +* Re: Stack analysis tool that really work?Don Y
    |    |`* Re: Stack analysis tool that really work?Niklas Holsti
    |    | `* Re: Stack analysis tool that really work?Don Y
    |    |  +* Re: Stack analysis tool that really work?Don Y
    |    |  |`* Re: Stack analysis tool that really work?Niklas Holsti
    |    |  | `* Re: Stack analysis tool that really work?Don Y
    |    |  |  `* Re: Stack analysis tool that really work?Niklas Holsti
    |    |  |   `- Re: Stack analysis tool that really work?Don Y
    |    |  `* Re: Stack analysis tool that really work?Niklas Holsti
    |    |   `* Re: Stack analysis tool that really work?Don Y
    |    |    `* Re: Stack analysis tool that really work?Niklas Holsti
    |    |     +- Re: Stack analysis tool that really work?Niklas Holsti
    |    |     `* Re: Stack analysis tool that really work?Don Y
    |    |      `- Re: Stack analysis tool that really work?Niklas Holsti
    |    `* Re: Stack analysis tool that really work?George Neuner
    |     `* Re: Stack analysis tool that really work?Niklas Holsti
    |      `* Re: Stack analysis tool that really work?George Neuner
    |       `* Re: Stack analysis tool that really work?Niklas Holsti
    |        +* Re: Stack analysis tool that really work?Paul Rubin
    |        |`- Re: Stack analysis tool that really work?Niklas Holsti
    |        `- Re: Stack analysis tool that really work?Don Y
    `* Re: Stack analysis tool that really work?Niklas Holsti
     `- Re: Stack analysis tool that really work?Don Y

Pages:12
Stack analysis tool that really work?

<sdukj9$8tu$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=566&group=comp.arch.embedded#566

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: pozzu...@gmail.com (pozz)
Newsgroups: comp.arch.embedded
Subject: Stack analysis tool that really work?
Date: Thu, 29 Jul 2021 18:22:00 +0200
Organization: A noiseless patient Spider
Lines: 7
Message-ID: <sdukj9$8tu$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 29 Jul 2021 16:22:01 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="bb0ee098d8759f02a84644b401f9af2c";
logging-data="9150"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18PGy6kjy875p6ZTW1PveiApACEBR8LlAU="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.12.0
Cancel-Lock: sha1:PUrOc/jiuMkvsGmUh1e5ers3igc=
Content-Language: it
X-Mozilla-News-Host: news://news.eternal-september.org:119
 by: pozz - Thu, 29 Jul 2021 16:22 UTC

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.

Re: Stack analysis tool that really work?

<img3p7Flnb9U1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=567&group=comp.arch.embedded#567

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 29 Jul 2021 19:36:55 +0300
Organization: Tidorum Ltd
Lines: 20
Message-ID: <img3p7Flnb9U1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net F/Hpmdjh9OShi6fURi7Jrg/tDzfO9bGvJNNgr/N2pT2uVodK8B
Cancel-Lock: sha1:MMeuCm1xO3WjRngUhU7UvASzccM=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <sdukj9$8tu$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Thu, 29 Jul 2021 16:36 UTC

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.

Re: Stack analysis tool that really work?

<sea47k$j3s$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=568&group=comp.arch.embedded#568

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Mon, 2 Aug 2021 17:56:17 -0700
Organization: A noiseless patient Spider
Lines: 20
Message-ID: <sea47k$j3s$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 3 Aug 2021 00:56:21 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="91833d90e6a47781cdaf0b0cd1e62d69";
logging-data="19580"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19MI/YhCBBR/Q9mY1Gtupsp"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:GWS7YfEiyo2Q3srlZWWP+Rfu1v4=
In-Reply-To: <sdukj9$8tu$1@dont-email.me>
Content-Language: en-US
 by: Don Y - Tue, 3 Aug 2021 00:56 UTC

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.

Re: Stack analysis tool that really work?

<imsdtvF7jafU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=569&group=comp.arch.embedded#569

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Tue, 3 Aug 2021 11:43:42 +0300
Organization: Tidorum Ltd
Lines: 38
Message-ID: <imsdtvF7jafU1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: individual.net FAbyOXPQkQUy/4sbs8v1sw9/zAkYCjPMqZwVNbYNrvLsPNXM/D
Cancel-Lock: sha1:wghUg7NI1yC+UENn2v0SJfNiD+Y=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <sea47k$j3s$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Tue, 3 Aug 2021 08:43 UTC

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.

Re: Stack analysis tool that really work?

<seb289$ol0$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=570&group=comp.arch.embedded#570

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Tue, 3 Aug 2021 02:28:26 -0700
Organization: A noiseless patient Spider
Lines: 73
Message-ID: <seb289$ol0$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<imsdtvF7jafU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 3 Aug 2021 09:28:41 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="91833d90e6a47781cdaf0b0cd1e62d69";
logging-data="25248"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19qxaLAaNm911mwkTJfoTpd"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:+S7IF0bAvOhM/ytywEPxPDKGBg4=
In-Reply-To: <imsdtvF7jafU1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Tue, 3 Aug 2021 09:28 UTC

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?

Re: Stack analysis tool that really work?

<seb3fa$82q$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=571&group=comp.arch.embedded#571

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: pozzu...@gmail.com (pozz)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Tue, 3 Aug 2021 11:49:29 +0200
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <seb3fa$82q$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 3 Aug 2021 09:49:30 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="36d9649db003e5fe25acfa4f0f1e3b56";
logging-data="8282"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18uzqVskhi15zpbS+GOc9yt0Xu9tmzKgGs="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.12.0
Cancel-Lock: sha1:VsEV4+CVkYAz1SzEM0UdPEE9FfA=
In-Reply-To: <sea47k$j3s$1@dont-email.me>
Content-Language: it
 by: pozz - Tue, 3 Aug 2021 09:49 UTC

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.

Re: Stack analysis tool that really work?

<sed0s0$ehl$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=572&group=comp.arch.embedded#572

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Tue, 3 Aug 2021 20:17:14 -0700
Organization: A noiseless patient Spider
Lines: 101
Message-ID: <sed0s0$ehl$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 4 Aug 2021 03:17:20 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5b50f543c5dad870dca29226e10bcba6";
logging-data="14901"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/RDMzmLv9PpqV2GJezDUDK"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:IUPlR5ifwoRyiVHM1ZCFi8zO/6g=
In-Reply-To: <seb3fa$82q$1@dont-email.me>
Content-Language: en-US
 by: Don Y - Wed, 4 Aug 2021 03:17 UTC

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!]

Re: Stack analysis tool that really work?

<see91v$uiq$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=573&group=comp.arch.embedded#573

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: pozzu...@gmail.com (pozz)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 16:43:10 +0200
Organization: A noiseless patient Spider
Lines: 139
Message-ID: <see91v$uiq$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <sed0s0$ehl$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 4 Aug 2021 14:43:11 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="c1f60829ccc2ee746db6e47b456e1dcd";
logging-data="31322"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18Hdgfd17N+MuKSEojqRtWhc9dJf0kdd7o="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.12.0
Cancel-Lock: sha1:qXZDci6OyvHg5j69QWGfCTNTMRQ=
In-Reply-To: <sed0s0$ehl$1@dont-email.me>
Content-Language: it
 by: pozz - Wed, 4 Aug 2021 14:43 UTC

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!]

Re: Stack analysis tool that really work?

<imvvdmFu7i4U1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=574&group=comp.arch.embedded#574

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 20:00:37 +0300
Organization: Tidorum Ltd
Lines: 39
Message-ID: <imvvdmFu7i4U1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net Eve39rqWNyBhB+MaXbW14wB6na1GqQfa5dwXfh+tjwCE4pssHW
Cancel-Lock: sha1:7R0InBiAEQNhIcmAfQnGN4+4u/s=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <seb3fa$82q$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Wed, 4 Aug 2021 17:00 UTC

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/.

Re: Stack analysis tool that really work?

<seek0l$e3r$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=575&group=comp.arch.embedded#575

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 10:50:06 -0700
Organization: A noiseless patient Spider
Lines: 48
Message-ID: <seek0l$e3r$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 4 Aug 2021 17:50:13 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5b50f543c5dad870dca29226e10bcba6";
logging-data="14459"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18HD/JtWj6MHtX/QIVbCSCs"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:mED2z7Wb0/EkwyYX8YLj40TquFA=
In-Reply-To: <imvvdmFu7i4U1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Wed, 4 Aug 2021 17:50 UTC

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 (?)

Re: Stack analysis tool that really work?

<seekur$l16$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=576&group=comp.arch.embedded#576

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 11:06:08 -0700
Organization: A noiseless patient Spider
Lines: 78
Message-ID: <seekur$l16$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <sed0s0$ehl$1@dont-email.me>
<see91v$uiq$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 4 Aug 2021 18:06:19 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5b50f543c5dad870dca29226e10bcba6";
logging-data="21542"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+cFye/kVCdln/px0nBTcbj"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:W9vkr9EH9rzaEOOgcgQxEyY5ZIM=
In-Reply-To: <see91v$uiq$1@dont-email.me>
Content-Language: en-US
 by: Don Y - Wed, 4 Aug 2021 18:06 UTC

On 8/4/2021 7:43 AM, pozz wrote:
>> 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.

How "simple" does it have to be? There are already tools that will
do this for you. Even GUI out. How "pretty" is a matter of debate
given that it's hard to make an algorithm that can find the "prettiest"
way of drawing such a graph.

>> 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.

When does your effort fall to the level of being "by hand"?
Note that you really would like a tool to do everything
(at least, everything IMPORTANT) for you so you don't
screw up or misapply it.

>>> -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.

Have you looked at egypt? There are other similar tools (that may
require more than one command to build the output)

>> 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.

My point is that you still have to perform tests that exercise every path
through your code. So, the test suite can be instrumented to harvest
this data KNOWING that every option has been examined.

>> 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.

What's available is what SOMEONE decided they wanted to develop *and*
offer up to others. You typically have fewer choices for "free" than
"for pay". Developing any tool (and maintaining it -- or, providing enough
information that OTHERS can maintain it without you) isn't a trivial job.

And, *a* free tool will likely soak up much of the effort that others
may have spent on some OTHER approach to that free tool. So, the first
drives/hinders future development; it's hard to completely redesign an
existing tool -- esp if others have bought into it on the maintenance side!

I build lots of tools to address *my* needs. But, rarely publish them
(beyond close colleagues) because I don't want to "pay the tax" of
supporting others -- even if they just have simple questions and aren't
looking for some change to the tool. I have my own interests; maintaining
a tool FOR OTHERS isn't one of them! <frown>

Re: Stack analysis tool that really work?

<in05quF11e0U1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=577&group=comp.arch.embedded#577

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 21:50:06 +0300
Organization: Tidorum Ltd
Lines: 18
Message-ID: <in05quF11e0U1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net 80Hu/oxNCmR8ckgN8GYnOQNu7hIAc3+cQwK7yhl+owhTL/9728
Cancel-Lock: sha1:2+RaNOzZR2hJjAFYzHnO5QJsg24=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <seek0l$e3r$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Wed, 4 Aug 2021 18:50 UTC

On 2021-08-04 20:50, Don Y wrote:
> On 8/4/2021 10:00 AM, Niklas Holsti wrote:

...

>> 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 (?)

The source code is downloadable; see http://bound-t.com/download/src.
The copyright text is of my own writing, but I'm open to switching to
some better-known copyright such as GPL or even some non-viral version.

However, you may want to read about the state of the tool at
http://bound-t.com/status.html.

Re: Stack analysis tool that really work?

<in078sF1a5uU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=578&group=comp.arch.embedded#578

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 22:14:35 +0300
Organization: Tidorum Ltd
Lines: 125
Message-ID: <in078sF1a5uU1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<imsdtvF7jafU1@mid.individual.net> <seb289$ol0$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: individual.net KENcARDSfEiBjcykVzl7LgU17wAiHIKsdPUePsuMzib7k0BjkX
Cancel-Lock: sha1:KqgqXXMknaIPK/yYLwIK99vO1qU=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <seb289$ol0$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Wed, 4 Aug 2021 19:14 UTC

On 2021-08-03 12:28, Don Y wrote:
> 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.

Well, most embedded programmers avoid recursion. And if you implement
recursion in a memory-constrained system, your design and code should
set a hard limit on the recursion depth and reject input that would
require deeper recursion.

Some (admittedly complex) static analyses can discover such limits from
the machine code, in the same way as they discover loop iteration limits
for WCET analysis. (In fact, I believe that the AbsInt tools translate
loops into recursions before the analysis.)

>> 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".

Again, if some sequences of external events might use an unbounded
amount of stack, the design and code should set a hard limit. I have not
encountered such programs.

The typical design is to allow some fixed maximum nesting of event
processing (eg. a finite set of interrupt priority levels) and otherwise
enqueue the events for sequential processing, which does not require an
unbounded stack.

>>> 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 the program is single-threaded, the allocated stack size is usually
set in the linker command file. Sure, you need the source for that file
if you want to change the stack size. Of course you are screwed if your
machine does not have enough memory for the size of stack you want.

> 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.

I've analyzed the stack usage (upper bounds) of many libraries without
access to source code. Typically embedded libraries have call-graphs
that can be extracted from the machine code without assumptions about
the I/O or other run-time values. But that may no longer be the case for
libraries written in C++ or other languages with run-time binding of calls.

I agree that for complete programs one sometimes needs more insight, in
particular if there are calls through function pointers or local
variables with dynamic (data-dependent) size.

>> 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.

Sorry, what is a "DSE-like" tool? DSE = ?

> How efficient are those you've used?  Do they operate in "near compile
> time"?

For stack-usage analysis the tools are quite fast, typically, because
embedded programs tend not to allocate dynamically-sized local
variables. The main time is spent in reading the executable and decoding
the instructions.

For programs that allocate local variables of dynamic size the analysis
becomes much more complex, can need lots of time and memory, and can
often fail.

> I.e., are they practical to use iteratively? On an entire
> application?

Yes, for many applications. And if you are implementing a
safety-critical system, you design your application to be analysable.

Re: Stack analysis tool that really work?

<sef565$4u7$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=579&group=comp.arch.embedded#579

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 15:43:10 -0700
Organization: A noiseless patient Spider
Lines: 140
Message-ID: <sef565$4u7$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<imsdtvF7jafU1@mid.individual.net> <seb289$ol0$1@dont-email.me>
<in078sF1a5uU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 4 Aug 2021 22:43:17 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="525b32a73b6b0d390504b38f200f730a";
logging-data="5063"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX185s+a20lXV/hURAjcaAKMf"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:LUPUfKy8bTcHSK3CWSasxRbZyJ4=
In-Reply-To: <in078sF1a5uU1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Wed, 4 Aug 2021 22:43 UTC

On 8/4/2021 12:14 PM, Niklas Holsti wrote:
> On 2021-08-03 12:28, Don Y wrote:
>> 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.
>
> Well, most embedded programmers avoid recursion. And if you implement recursion
> in a memory-constrained system, your design and code should set a hard limit on
> the recursion depth and reject input that would require deeper recursion.

Yes, but you don't need that limit to be enforced by a "depth counter".
Instead, it can be encoded in the data that *drives* the recursion.
A *human* understands that there is a limit (and exactly what that limit
is, for any dataset). But, an algorithm may be taxed with trying to
determine this.

I shouldn't have to adopt a coding style just for the sake of a tool.

> Some (admittedly complex) static analyses can discover such limits from the
> machine code, in the same way as they discover loop iteration limits for WCET
> analysis. (In fact, I believe that the AbsInt tools translate loops into
> recursions before the analysis.)
>
>>> 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".
>
> Again, if some sequences of external events might use an unbounded amount of
> stack, the design and code should set a hard limit. I have not encountered such
> programs.
>
> The typical design is to allow some fixed maximum nesting of event processing
> (eg. a finite set of interrupt priority levels) and otherwise enqueue the
> events for sequential processing, which does not require an unbounded stack.

Events need not be interrupts. They may be user actions/keystrokes.
But, the "grammar" (odd choice of words) that defines the range of
permissible actions can limit how deeply the "generic" algorithm
recurses. Again, something that a human can see and verify but that
could evade anything sort of a sophisticated analysis of code+data.

>>>> 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 the program is single-threaded, the allocated stack size is usually set in
> the linker command file. Sure, you need the source for that file if you want to
> change the stack size. Of course you are screwed if your machine does not have
> enough memory for the size of stack you want.

But you can't *change* your algorithm, having discovered that it uses
more stack than you had anticipated (or, that other consumers have
left available for its use). Without the sources, your only option
is to change the hardware to make more stack available.

[And, even that may not be possible; e.g., multithreaded in a single
address space]

>> 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.
>
> I've analyzed the stack usage (upper bounds) of many libraries without access
> to source code. Typically embedded libraries have call-graphs that can be
> extracted from the machine code without assumptions about the I/O or other
> run-time values. But that may no longer be the case for libraries written in
> C++ or other languages with run-time binding of calls.
>
> I agree that for complete programs one sometimes needs more insight, in
> particular if there are calls through function pointers or local variables with
> dynamic (data-dependent) size.
>
>>> 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.
>
> Sorry, what is a "DSE-like" tool? DSE = ?

Dynamic Symbolic Execution.

>> How efficient are those you've used? Do they operate in "near compile time"?
>
> For stack-usage analysis the tools are quite fast, typically, because embedded
> programs tend not to allocate dynamically-sized local variables. The main time
> is spent in reading the executable and decoding the instructions.
>
> For programs that allocate local variables of dynamic size the analysis becomes
> much more complex, can need lots of time and memory, and can often fail.

Ah. The symbolic tools (alluded to above) are *really* resource intensive.
You can spend HOURS analyzing a piece of code -- with a fast workstation.
(my point being this is a tool that you'd use to VERIFY your assumptions;
relying on it to tell you what you don't yet know -- esp if your code is
evolving -- is way too costly!)

>> I.e., are they practical to use iteratively? On an entire
>> application?
>
> Yes, for many applications. And if you are implementing a safety-critical
> system, you design your application to be analysable.

But, wouldn't you inherently *know* where your design is headed?
And, just need the tool to confirm that? (and put real numbers on it)

Re: Stack analysis tool that really work?

<sef5c3$5so$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=580&group=comp.arch.embedded#580

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Wed, 4 Aug 2021 15:46:20 -0700
Organization: A noiseless patient Spider
Lines: 25
Message-ID: <sef5c3$5so$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in05quF11e0U1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 4 Aug 2021 22:46:28 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="525b32a73b6b0d390504b38f200f730a";
logging-data="6040"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19qxUT2OoAUNjTbkWFKJmff"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:fCaMTmgk2+X0so3sxrfhy/mr+rs=
In-Reply-To: <in05quF11e0U1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Wed, 4 Aug 2021 22:46 UTC

On 8/4/2021 11:50 AM, Niklas Holsti wrote:
> On 2021-08-04 20:50, Don Y wrote:
>> On 8/4/2021 10:00 AM, Niklas Holsti wrote:
>
> ...
>
>>> 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 (?)
>
> The source code is downloadable; see http://bound-t.com/download/src. The
> copyright text is of my own writing, but I'm open to switching to some
> better-known copyright such as GPL or even some non-viral version.

Ah, OK. I may have a look at it to see how well it works and
how much work to port to ARM objects. Given that you've not
done so, already (despite your familiarity with the codebase),
I suspect that's not a trivial task?

> However, you may want to read about the state of the tool at
> http://bound-t.com/status.html.

Hmmm... that sounds ominous! :> (or, am I just too much of a Cynic?)

Re: Stack analysis tool that really work?

<in1nknFamrvU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=581&group=comp.arch.embedded#581

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 5 Aug 2021 12:00:06 +0300
Organization: Tidorum Ltd
Lines: 61
Message-ID: <in1nknFamrvU1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <sed0s0$ehl$1@dont-email.me>
<see91v$uiq$1@dont-email.me> <seekur$l16$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: individual.net a5vR/Aars8IB1k7aEgry2Qqog6/e+ZDQySQNnD+dkbx6cK2uS/
Cancel-Lock: sha1:E5pwuZWhgF2GFVB6sAJSx8Nelkc=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <seekur$l16$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Thu, 5 Aug 2021 09:00 UTC

On 2021-08-04 21:06, Don Y wrote:
> On 8/4/2021 7:43 AM, pozz wrote:
>>> 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.
>
> How "simple" does it have to be?  There are already tools that will
> do this for you.  Even GUI out.  How "pretty" is a matter of debate
> given that it's hard to make an algorithm that can find the "prettiest"
> way of drawing such a graph.

The "dot" tool in the GraphViz package does a good job of graph lay-out.
See https://en.wikipedia.org/wiki/Graphviz. Bound-T generates its graphs
in "dot" format. The AbsInt tools have their own graph-layout package;
it may even be sold separately.

However, as a said earlier, a source-level call-graph is often not
complete with respect to the calls that happen at run time.

>> This is the dynamic approach, I was exploring the static approach.
>
> My point is that you still have to perform tests that exercise every path
> through your code.

That (full path coverage) is almost never done, because it is
exponential in the number of branches.

In case the sizes of local variables depend on input data, it may be
very hard to find the input values that lead to the actual worst-case
stack-usage path. Safe upper bounds are easier to find by analysis.

> What's available is what SOMEONE decided they wanted to develop *and*
> offer up to others.  You typically have fewer choices for "free" than
> "for pay".  Developing any tool (and maintaining it -- or, providing enough
> information that OTHERS can maintain it without you) isn't a trivial job.

My experience is that rather few developers favour the static-analysis
approach to resource analysis -- most just instrument and test. There
are a few application domains that require better guarantees --
aerospace, automotive, nuclear -- and they are also prepared to pay (a
bit) for the tools. However, tools for such domains usually need some
kind of formal qualification or certification, which can be expensive.

Also, while static analysis is still possible for stack usage, it is
becoming impossible for WCET, because of the complex, dynamic
architecture of current high-end embedded processors (out-of-order
execution, complex caches, multi-core with shared-resource conflicts,
and so on and on). The field seems to be moving towards hybrid analysis
methods that combine measured execution times with static flow analys,
for example the tools from Rapita (https://www.rapitasystems.com/).

Re: Stack analysis tool that really work?

<in1s7sFbkaoU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=582&group=comp.arch.embedded#582

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 5 Aug 2021 13:18:36 +0300
Organization: Tidorum Ltd
Lines: 52
Message-ID: <in1s7sFbkaoU1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: individual.net fGIHphnj0umqz32J3EflOA2vC5MS6r6N/H69GI6QmPL7lAswhy
Cancel-Lock: sha1:hXDsQh2b9KmuOMgFlYkxuGmLO+s=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <seek0l$e3r$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Thu, 5 Aug 2021 10:18 UTC

On 2021-08-04 20:50, Don Y wrote:
> 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.

LLVM IR and other similar program representations are a good "level" for
some semantic analyses, such as value analysis (finding possible ranges
of variable values) and control-flow analysis. But it is typically too
high a level for analysing machine resources such as stack usage and WCET.

If one can set up a reliable mapping between the IR entities (variables
and control flow) and the machine-level entities (registers, memory
locations, branch instructions) the two levels of analysis can support
each other. Unfortunately that mapping is defined by the compiler and
linker and is usually described only incompletely in the debugging
information emitted from the compiler and linker.

Re: Stack analysis tool that really work?

<in1tnaFbu8rU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=583&group=comp.arch.embedded#583

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 5 Aug 2021 13:43:54 +0300
Organization: Tidorum Ltd
Lines: 49
Message-ID: <in1tnaFbu8rU1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in05quF11e0U1@mid.individual.net>
<sef5c3$5so$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: individual.net A6hF7juvJo0SXT3JDvOBuQHlUYwahLG91EnvnmSMxvr4LClaa7
Cancel-Lock: sha1:4NCQa7fVzPAgz5DpshG9GCpkq3k=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <sef5c3$5so$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Thu, 5 Aug 2021 10:43 UTC

On 2021-08-05 1:46, Don Y wrote:
> On 8/4/2021 11:50 AM, Niklas Holsti wrote:
>> On 2021-08-04 20:50, Don Y wrote:
>>> On 8/4/2021 10:00 AM, Niklas Holsti wrote:
>>
>>     ...
>>
>>>> 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 (?)
>>
>> The source code is downloadable; see http://bound-t.com/download/src.
>> The copyright text is of my own writing, but I'm open to switching to
>> some better-known copyright such as GPL or even some non-viral version.
>
> Ah, OK.  I may have a look at it to see how well it works and
> how much work to port to ARM objects.  Given that you've not
> done so, already (despite your familiarity with the codebase),
> I suspect that's not a trivial task?

There is an ARM TDMI port (32-bit ARM code and THUMB, pre Cortex), but
of course that architecture is out of date. I started a port to ARM
Cortex-M, but did not (yet) finish it for the reasons described on the
status page.

Note that the tool is implemented in Ada.

Porting to a new target processor means writing procedures to decode the
machine instructions and translate them to the internal representation
used by the analysis. Sometimes it is also necessary to modify or extend
the tool parts that read the executable files and especially the
debugging information -- some of that may be compiler-specific,
unfortunately. It is a fair amount of work and requires a good
understanding both of the target processor and of the Bound-T internal
representation. And Ada, of course, but every programmer should know
Ada, IMO :-)

>> However, you may want to read about the state of the tool at
>> http://bound-t.com/status.html.
>
> Hmmm... that sounds ominous!  :>  (or, am I just too much of a Cynic?)

The problems described on the status page are more relevant to WCET
analysis than to stack analysis, but can affect stack analysis too, in
some cases.

Re: Stack analysis tool that really work?

<segjih$e76$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=584&group=comp.arch.embedded#584

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 5 Aug 2021 04:54:43 -0700
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <segjih$e76$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <sed0s0$ehl$1@dont-email.me>
<see91v$uiq$1@dont-email.me> <seekur$l16$1@dont-email.me>
<in1nknFamrvU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 5 Aug 2021 11:54:57 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="525b32a73b6b0d390504b38f200f730a";
logging-data="14566"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+1jOmNpsidbcThFlEgbgTn"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:mO778VG0a68vYY0CX2yrGi/eRQU=
In-Reply-To: <in1nknFamrvU1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Thu, 5 Aug 2021 11:54 UTC

On 8/5/2021 2:00 AM, Niklas Holsti wrote:
> On 2021-08-04 21:06, Don Y wrote:
>>> This is the dynamic approach, I was exploring the static approach.
>>
>> My point is that you still have to perform tests that exercise every path
>> through your code.
>
> That (full path coverage) is almost never done, because it is exponential in
> the number of branches.

It's impractical for a "whole program" but is relatively easy to accomplish
for tasks designed to be small and single-focus. A solution that is
implemented in this sort of "decomposed" manner is easier to analyze
whereas something "monolithic" is hard to (later) "chop up" to yield testable
SMALLER/simpler pieces.

> In case the sizes of local variables depend on input data, it may be very hard
> to find the input values that lead to the actual worst-case stack-usage path.
> Safe upper bounds are easier to find by analysis.
>
>> What's available is what SOMEONE decided they wanted to develop *and*
>> offer up to others. You typically have fewer choices for "free" than
>> "for pay". Developing any tool (and maintaining it -- or, providing enough
>> information that OTHERS can maintain it without you) isn't a trivial job.
>
> My experience is that rather few developers favour the static-analysis approach
> to resource analysis -- most just instrument and test. There are a few
> application domains that require better guarantees -- aerospace, automotive,
> nuclear -- and they are also prepared to pay (a bit) for the tools. However,
> tools for such domains usually need some kind of formal qualification or
> certification, which can be expensive.

Ditto medical/pharma/gamiing. In addition to tool qualification, there
are also *process* qualification issues. This tends to reduce the number
of variants/releases of a "product" as each release requires running
through the validation effort, again.

[And, a release begs the question: "Do you mean there were things that
DID NOT WORK in the prior release? If so, then how comprehensive was
the previous validation effort??? Assure me that your process isn't
inherently flawed..."]

The fact that this effort exists (is required) means you will spend
money to lessen it's cost AND increase the apparent integrity of
your process to customers/agencies. Esp as you will be doing this
repeatedly (for this product or others). Imagine having to *manually*
repeat the entire effort from the previous release PLUS the changes
brought about by the new release... for EVERY successive release!

[No, you can't just *claim* that all of the stuff you validated before
STILL WORKS!]

> Also, while static analysis is still possible for stack usage, it is becoming
> impossible for WCET, because of the complex, dynamic architecture of current
> high-end embedded processors (out-of-order execution, complex caches,
> multi-core with shared-resource conflicts, and so on and on). The field seems
> to be moving towards hybrid analysis methods that combine measured execution
> times with static flow analys, for example the tools from Rapita
> (https://www.rapitasystems.com/).

I've taken a different approach on my current (real-time) project: assume
any task can fail to meet it's deadlines and provide mechanisms to handle
those overruns. (a "hard" real-time task has a very simple deadline
handler: kill the task! :> )

But, that's because the resource load (and resource complement) is not known
a priori so you can't make *any* guarantees.

Re: Stack analysis tool that really work?

<segjri$hre$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=585&group=comp.arch.embedded#585

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 5 Aug 2021 04:59:38 -0700
Organization: A noiseless patient Spider
Lines: 65
Message-ID: <segjri$hre$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in1s7sFbkaoU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 5 Aug 2021 11:59:46 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="525b32a73b6b0d390504b38f200f730a";
logging-data="18286"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/KH/TnY8SyJM7gDSEZmoX6"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:hc9GXnsMscbHf05tfBSt0TU4xOk=
In-Reply-To: <in1s7sFbkaoU1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Thu, 5 Aug 2021 11:59 UTC

On 8/5/2021 3:18 AM, Niklas Holsti wrote:
> On 2021-08-04 20:50, Don Y wrote:
>> 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.
>
> LLVM IR and other similar program representations are a good "level" for some
> semantic analyses, such as value analysis (finding possible ranges of variable
> values) and control-flow analysis.

Yes. I use such tools for automatically determining test coverage conditions.
"Look at my code and figure out the inputs necessary to 'go everywhere'".

> But it is typically too high a level for
> analysing machine resources such as stack usage and WCET.

Timing, agreed. But, I suspect there might be a way to add hooks to
the analysis that "expose" the current SP to each function -- and
then extract that. (I've not thought about it beyond conceptually;
the tool WILL visit each variant of function invocation so if it
can be coerced to take note of SP then it would simply be a matter
of looking for max() -- and, it would be able to tell you *how*
it got to that point!)

> If one can set up a reliable mapping between the IR entities (variables and
> control flow) and the machine-level entities (registers, memory locations,
> branch instructions) the two levels of analysis can support each other.
> Unfortunately that mapping is defined by the compiler and linker and is usually
> described only incompletely in the debugging information emitted from the
> compiler and linker.

Re: Stack analysis tool that really work?

<segoc2$6dj$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=586&group=comp.arch.embedded#586

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 5 Aug 2021 06:16:36 -0700
Organization: A noiseless patient Spider
Lines: 61
Message-ID: <segoc2$6dj$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in05quF11e0U1@mid.individual.net>
<sef5c3$5so$1@dont-email.me> <in1tnaFbu8rU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 5 Aug 2021 13:16:50 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="525b32a73b6b0d390504b38f200f730a";
logging-data="6579"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+o3CtuLeM/hlBbNTcqajJ8"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:Angxh0tRAA61Qq8daobFVo/89Fg=
In-Reply-To: <in1tnaFbu8rU1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Thu, 5 Aug 2021 13:16 UTC

On 8/5/2021 3:43 AM, Niklas Holsti wrote:
> On 2021-08-05 1:46, Don Y wrote:

>>> The source code is downloadable; see http://bound-t.com/download/src. The
>>> copyright text is of my own writing, but I'm open to switching to some
>>> better-known copyright such as GPL or even some non-viral version.
>>
>> Ah, OK. I may have a look at it to see how well it works and
>> how much work to port to ARM objects. Given that you've not
>> done so, already (despite your familiarity with the codebase),
>> I suspect that's not a trivial task?
>
> There is an ARM TDMI port (32-bit ARM code and THUMB, pre Cortex), but of
> course that architecture is out of date. I started a port to ARM Cortex-M, but
> did not (yet) finish it for the reasons described on the status page.
>
> Note that the tool is implemented in Ada.

OK. It's been ~20 years since I wrote a line of Ada code but I doubt it
will take much to "refresh" those memory cells. Esp as this likely doesn't
have synchronization issues, RT constraints, etc.

> Porting to a new target processor means writing procedures to decode the
> machine instructions and translate them to the internal representation used by
> the analysis.

That shouldn't be hard -- except for the "timing uncertainties" in the
processor. (Did you rely on some blanket generalization -- like all
caches cold -- as you are looking for WORST case timing? OTOH, a
loop known to fit in a cache line *should* expect that speedup... :< )

> Sometimes it is also necessary to modify or extend the tool parts
> that read the executable files and especially the debugging information -- some
> of that may be compiler-specific, unfortunately. It is a fair amount of work
> and requires a good understanding both of the target processor and of the
> Bound-T internal representation.

The latter will likely be the bigger effort. It requires trying to infer
your mindset when you began the design.

[I now include "rationales" in my documentation for exactly this purpose;
to let those "following" understand why particular choices were made
instead of choices that may (in hindsight) appear better]

> And Ada, of course, but every programmer
> should know Ada, IMO :-)
>
>>> However, you may want to read about the state of the tool at
>>> http://bound-t.com/status.html.
>>
>> Hmmm... that sounds ominous! :> (or, am I just too much of a Cynic?)
>
> The problems described on the status page are more relevant to WCET analysis
> than to stack analysis, but can affect stack analysis too, in some cases.

OK. I'll try to make some time to look through it. Sadly, a neighbor was
admitted to hospital with congestive heart failure, last night. So, I've
some added responsibilities cutting into my time (meal prep, chores around
his house, etc.) until he's got a firmer prognosis...

[I don't *need* to sleep, do I? :< ]

Re: Stack analysis tool that really work?

<in2f27FfeehU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=587&group=comp.arch.embedded#587

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Thu, 5 Aug 2021 18:39:51 +0300
Organization: Tidorum Ltd
Lines: 84
Message-ID: <in2f27FfeehU1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in05quF11e0U1@mid.individual.net>
<sef5c3$5so$1@dont-email.me> <in1tnaFbu8rU1@mid.individual.net>
<segoc2$6dj$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: individual.net gGwZZTvRMR+mlpxMDbgcxA7m4ZZ5tjxkvNsJ+JDjiyDPjKvrPu
Cancel-Lock: sha1:HMVG6l1syKXKKlPPpSesSL67VMs=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <segoc2$6dj$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Thu, 5 Aug 2021 15:39 UTC

On 2021-08-05 16:16, Don Y wrote:
> On 8/5/2021 3:43 AM, Niklas Holsti wrote:
>> On 2021-08-05 1:46, Don Y wrote:
>
>>>> The source code is downloadable; see
>>>> http://bound-t.com/download/src. The copyright text is of my own
>>>> writing, but I'm open to switching to some better-known copyright
>>>> such as GPL or even some non-viral version.
>>>
>>> Ah, OK.  I may have a look at it to see how well it works and
>>> how much work to port to ARM objects.  Given that you've not
>>> done so, already (despite your familiarity with the codebase),
>>> I suspect that's not a trivial task?
>>
>> There is an ARM TDMI port (32-bit ARM code and THUMB, pre Cortex), but
>> of course that architecture is out of date. I started a port to ARM
>> Cortex-M, but did not (yet) finish it for the reasons described on the
>> status page.
>>
>> Note that the tool is implemented in Ada.
>
> OK.  It's been ~20 years since I wrote a line of Ada code but I doubt it
> will take much to "refresh" those memory cells.  Esp as this likely doesn't
> have synchronization issues, RT constraints, etc.

Right. The only use of tasking features is to set an upper limit on the
execution time of the analysis, and that feature is easy to remove if
needed.

The code mostly relies on the 1995 Ada standard, with some use of Ada
2005 additions.

>> Porting to a new target processor means writing procedures to decode
>> the machine instructions and translate them to the internal
>> representation used by the analysis.
>
> That shouldn't be hard -- except for the "timing uncertainties" in the
> processor.  (Did you rely on some blanket generalization -- like all
> caches cold -- as you are looking for WORST case timing?   OTOH, a
> loop known to fit in a cache line *should* expect that speedup...  :< )

At present the tool assumes that every instruction and control transfer
can be assigned its own WCET, in machine cycles, independent of other
context or data values. The only dynamic aspects of instruction
execution time that are modelled are the possible pipeline stalls due to
read-after-write interlocks. As a special case, in the version for
SPARC, the concurrent execution of the Integer Unit and the Floating
Point Unit is modelled to estimate where and for how long the IU has to
wait for the FPU to complete an operation.

Good algorithms for computing WCET bounds for most kinds of instruction
caches are known, but I did not get around to implementing any of those,
so only cache-less processors are supported now. If you need WCET
analysis of caches, the AbsInt tool is best.

Data caches are still a hard problem, where the WCET analyses tend to be
quite pessimistic. Moreover, the increasing use of eviction algorithms
other than LRU (for example, pseudo-random eviction) lessens the
precision of the cache analyses, even for instruction caches.

>> Sometimes it is also necessary to modify or extend the tool parts that
>> read the executable files and especially the debugging information --
>> some of that may be compiler-specific, unfortunately. It is a fair
>> amount of work and requires a good understanding both of the target
>> processor and of the Bound-T internal representation.
>
> The latter will likely be the bigger effort.  It requires trying to infer
> your mindset when you began the design.

You could start by reading http://bound-t.com/whats-inside.html.

> [I now include "rationales" in my documentation for exactly this purpose;
> to let those "following" understand why particular choices were made
> instead of choices that may (in hindsight) appear better]

Me too. Ceterum censeo that calling the in-code documentation "comments"
was a very poor choice of term and very misleading for what such
documentation should contain and its importance.

Re: Stack analysis tool that really work?

<seiqoj$8mk$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=588&group=comp.arch.embedded#588

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Fri, 6 Aug 2021 01:09:46 -0700
Organization: A noiseless patient Spider
Lines: 105
Message-ID: <seiqoj$8mk$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in05quF11e0U1@mid.individual.net>
<sef5c3$5so$1@dont-email.me> <in1tnaFbu8rU1@mid.individual.net>
<segoc2$6dj$1@dont-email.me> <in2f27FfeehU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 6 Aug 2021 08:09:55 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="3e1f5a766a82721144bb89497815d79d";
logging-data="8916"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19hErx7Zejr/rCROIiREZIM"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:hlR2802FPettXM5IDajK5CXOdLY=
In-Reply-To: <in2f27FfeehU1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Fri, 6 Aug 2021 08:09 UTC

On 8/5/2021 8:39 AM, Niklas Holsti wrote:
> On 2021-08-05 16:16, Don Y wrote:
>> On 8/5/2021 3:43 AM, Niklas Holsti wrote:
>>> On 2021-08-05 1:46, Don Y wrote:
>>
>>>>> The source code is downloadable; see http://bound-t.com/download/src. The
>>>>> copyright text is of my own writing, but I'm open to switching to some
>>>>> better-known copyright such as GPL or even some non-viral version.
>>>>
>>>> Ah, OK. I may have a look at it to see how well it works and
>>>> how much work to port to ARM objects. Given that you've not
>>>> done so, already (despite your familiarity with the codebase),
>>>> I suspect that's not a trivial task?
>>>
>>> There is an ARM TDMI port (32-bit ARM code and THUMB, pre Cortex), but of
>>> course that architecture is out of date. I started a port to ARM Cortex-M,
>>> but did not (yet) finish it for the reasons described on the status page.
>>>
>>> Note that the tool is implemented in Ada.
>>
>> OK. It's been ~20 years since I wrote a line of Ada code but I doubt it
>> will take much to "refresh" those memory cells. Esp as this likely doesn't
>> have synchronization issues, RT constraints, etc.
>
> Right. The only use of tasking features is to set an upper limit on the
> execution time of the analysis, and that feature is easy to remove if needed.
>
> The code mostly relies on the 1995 Ada standard, with some use of Ada 2005
> additions.

OK. I'll have to build a more current version of GNAT.

>>> Porting to a new target processor means writing procedures to decode the
>>> machine instructions and translate them to the internal representation used
>>> by the analysis.
>>
>> That shouldn't be hard -- except for the "timing uncertainties" in the
>> processor. (Did you rely on some blanket generalization -- like all
>> caches cold -- as you are looking for WORST case timing? OTOH, a
>> loop known to fit in a cache line *should* expect that speedup... :< )
>
> At present the tool assumes that every instruction and control transfer can be
> assigned its own WCET, in machine cycles, independent of other context or data

So, you just sum worst case times? You don't, for example, alter
times based on conditionals?

I assume this is semi table-driven (?) -- as a preface to inquiring as to
how you develop (and verify!) a test suite?

> values. The only dynamic aspects of instruction execution time that are
> modelled are the possible pipeline stalls due to read-after-write interlocks.
> As a special case, in the version for SPARC, the concurrent execution of the
> Integer Unit and the Floating Point Unit is modelled to estimate where and for
> how long the IU has to wait for the FPU to complete an operation.
>
> Good algorithms for computing WCET bounds for most kinds of instruction caches
> are known, but I did not get around to implementing any of those, so only
> cache-less processors are supported now. If you need WCET analysis of caches,
> the AbsInt tool is best.

It's arguable whether (and to what extent) you should model I-cache effects.
E.g., in a multithreaded environment, the cache can be purged at some
frequency that a tool (or the developer, for that matter -- at least not
wrt the instruction stream) can't know. Aim high and be pleasantly
surprised...

> Data caches are still a hard problem, where the WCET analyses tend to be quite
> pessimistic. Moreover, the increasing use of eviction algorithms other than LRU
> (for example, pseudo-random eviction) lessens the precision of the cache
> analyses, even for instruction caches.

As would handling page faults or other NUMA issues.

[How do you handle accesses to memories with different *basic* access times?]

>>> Sometimes it is also necessary to modify or extend the tool parts that read
>>> the executable files and especially the debugging information -- some of
>>> that may be compiler-specific, unfortunately. It is a fair amount of work
>>> and requires a good understanding both of the target processor and of the
>>> Bound-T internal representation.
>>
>> The latter will likely be the bigger effort. It requires trying to infer
>> your mindset when you began the design.
>
> You could start by reading http://bound-t.com/whats-inside.html.
>
>> [I now include "rationales" in my documentation for exactly this purpose;
>> to let those "following" understand why particular choices were made
>> instead of choices that may (in hindsight) appear better]
>
> Me too. Ceterum censeo that calling the in-code documentation "comments" was a
> very poor choice of term and very misleading for what such documentation should
> contain and its importance.

A "rationale" lets you talk to the next developer(s) informally. You can
point out areas for likely optimization, areas fraught with dragons, etc.
Otherwise, relying on leafing through hundreds of pages of code in the
hope of stumbling on some "XXX ..." annotation is wasteful.

And, *not* being tied to a "text only" presentation means you can explain
things in ways that would be difficult to do (unambiguously) with prose.

[How do I audibly explain the difference between front vowels and back
vowels to a non-native speaker/listener?]

Re: Stack analysis tool that really work?

<in5iifF4i5gU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=589&group=comp.arch.embedded#589

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Fri, 6 Aug 2021 22:58:06 +0300
Organization: Tidorum Ltd
Lines: 166
Message-ID: <in5iifF4i5gU1@mid.individual.net>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in05quF11e0U1@mid.individual.net>
<sef5c3$5so$1@dont-email.me> <in1tnaFbu8rU1@mid.individual.net>
<segoc2$6dj$1@dont-email.me> <in2f27FfeehU1@mid.individual.net>
<seiqoj$8mk$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: individual.net Dl2+D+WMETmK8RK+lARp8wKcRLiy8IQWFU4geUg80xuC2F3COV
Cancel-Lock: sha1:78gS4ikQf6k7NFmAnSX2f0nu048=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.12.0
In-Reply-To: <seiqoj$8mk$1@dont-email.me>
Content-Language: en-US
 by: Niklas Holsti - Fri, 6 Aug 2021 19:58 UTC

On 2021-08-06 11:09, Don Y wrote:
> On 8/5/2021 8:39 AM, Niklas Holsti wrote:
>> On 2021-08-05 16:16, Don Y wrote:
>>> On 8/5/2021 3:43 AM, Niklas Holsti wrote:
>>>> On 2021-08-05 1:46, Don Y wrote:
>>>
>>>>>> The source code is downloadable; see
>>>>>> http://bound-t.com/download/src. The copyright text is of my own
>>>>>> writing, but I'm open to switching to some better-known copyright
>>>>>> such as GPL or even some non-viral version.
>>>>>
>>>>> Ah, OK.  I may have a look at it to see how well it works and
>>>>> how much work to port to ARM objects.  Given that you've not
>>>>> done so, already (despite your familiarity with the codebase),
>>>>> I suspect that's not a trivial task?
>>>>
>>>> There is an ARM TDMI port (32-bit ARM code and THUMB, pre Cortex),
>>>> but of course that architecture is out of date. I started a port to
>>>> ARM Cortex-M, but did not (yet) finish it for the reasons described
>>>> on the status page.
>>>>
>>>> Note that the tool is implemented in Ada.
>>>
>>> OK.  It's been ~20 years since I wrote a line of Ada code but I doubt it
>>> will take much to "refresh" those memory cells.  Esp as this likely
>>> doesn't
>>> have synchronization issues, RT constraints, etc.
>>
>> Right. The only use of tasking features is to set an upper limit on
>> the execution time of the analysis, and that feature is easy to remove
>> if needed.
>>
>> The code mostly relies on the 1995 Ada standard, with some use of Ada
>> 2005 additions.
>
> OK.  I'll have to build a more current version of GNAT.

For playing around, I would just use the GNAT Community Edition. Or the
FSF GNAT that comes with MinGW32.

>>>> Porting to a new target processor means writing procedures to decode
>>>> the machine instructions and translate them to the internal
>>>> representation used by the analysis.
>>>
>>> That shouldn't be hard -- except for the "timing uncertainties" in the
>>> processor.  (Did you rely on some blanket generalization -- like all
>>> caches cold -- as you are looking for WORST case timing?   OTOH, a
>>> loop known to fit in a cache line *should* expect that speedup...  :< )
>>
>> At present the tool assumes that every instruction and control
>> transfer can be assigned its own WCET, in machine cycles, independent
>> of other context or data
>
> So, you just sum worst case times?  You don't, for example, alter
> times based on conditionals?

(Note: I say "WCET" below, but really I should always say "upper bound
on the WCET".)

The analysis works on the control-flow graph (per subprogram). The WCET
for each basic block is the sum of the WCETs of the instructions in that
block. The WCET for an execution path through the graph (from entry to
return) is the sum of the WCETs of the basic blocks in the bath, plus
the WCETs assigned to each edge (control transfer) between basic blocks
in the path. The WCET for the whole graph is computed by a pessimisation
over all syntactically possible paths through the graph, using an
Integer Linear Programming solver (lp_solve, for Bound-T). This method
is common in WCET analysis and is called IPET, for Implicit Path
Exploration Technique.

By "syntactically possible" I mean that the tool generally does not
attempt to find semantically or logically infeasible paths. For example,
if a subprogram has this form:

if boo then
perform computation A;
else
perform computation B;
end if;
perform computation C;

then the WCET for the subprogram is estimated as max(WCET(A),WCET(B)) +
WCET(C). But if the subprogram has this form:

if boo then
perform computation A;
end if;
perform computation C;
if not boo then
perform computation B;
end if;

then the WCET for the subprogram is estimated as WCET(A) + WCET(C) +
WCET(B). In other words, the analysis (usually) does not discover that
the conditions "boo" and "not boo" are mutually exclusive.

> I assume this is semi table-driven (?)

I don't understand that question. Please clarify.

> -- as a preface to inquiring as to
> how you develop (and verify!) a test suite?

In the same way as for any complex program. Final validation by running
and measuring test code on a real processor or a cycle-accurate simulation.

>> Good algorithms for computing WCET bounds for most kinds of
>> instruction caches are known, but I did not get around to implementing
>> any of those, so only cache-less processors are supported now. If you
>> need WCET analysis of caches, the AbsInt tool is best.
>
> It's arguable whether (and to what extent) you should model I-cache
> effects.
> E.g., in a multithreaded environment, the cache can be purged at some
> frequency that a tool (or the developer, for that matter -- at least not
> wrt the instruction stream) can't know.  Aim high and be pleasantly
> surprised...

Such Cache-Related Preemption Delays (CRPDs) are a much-studied problem
in WCET analysis. The most common solution is to first find out how the
various tasks and interrupts can access memory blocks which potentially
may collide in the caches, and then to take the worst possible
interference into account in the schedulability analysis, which does
know (or assumes) the worst case frequency of preemptions.

For processors where cache misses are much slower than cache hits (which
is fast coming to mean almost all processors) IMO an I-cache analysis is
necessary for static WCET analysis to be useful.

> [How do you handle accesses to memories with different *basic* access
> times?]

For code fetch the address is always statically known, so the correct
access time can be selected and included in the WCET for the instruction
when the instruction is decoded.

For data accesses, if different instructions are used for different
memories (as in the 8051 architecture, for example), the proper access
time can be included in the WCET for the instruction when the
instruction is decoded.

If the same instructions are used to access memories with different
access times, depending on the address, and the memory addresses are
dynamically determined at run time, the practical but pessimistic way is
to use the largest of the access times, that is, assume that the slowest
memory is accessed. In principle the tool can try to analyze the address
computations and might find sufficient bounds on the address to ensure
that a faster memory is accessed, but the analysis methods currently
available in Bound-T seldom manage that, and can be quite slow.

That said, for some processors it is easy to recognize at decode-time
most of the instructions that access the stack, and some versions of
Bound-T let one specify different access times for stack accesses and
for general (unclassified) accesses. That can be useful if the stack is
located in fast memory, but other data are in slower memory.

Re: Stack analysis tool that really work?

<sekf60$uvl$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=590&group=comp.arch.embedded#590

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: blockedo...@foo.invalid (Don Y)
Newsgroups: comp.arch.embedded
Subject: Re: Stack analysis tool that really work?
Date: Fri, 6 Aug 2021 16:04:21 -0700
Organization: A noiseless patient Spider
Lines: 203
Message-ID: <sekf60$uvl$1@dont-email.me>
References: <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me>
<seb3fa$82q$1@dont-email.me> <imvvdmFu7i4U1@mid.individual.net>
<seek0l$e3r$1@dont-email.me> <in05quF11e0U1@mid.individual.net>
<sef5c3$5so$1@dont-email.me> <in1tnaFbu8rU1@mid.individual.net>
<segoc2$6dj$1@dont-email.me> <in2f27FfeehU1@mid.individual.net>
<seiqoj$8mk$1@dont-email.me> <in5iifF4i5gU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 6 Aug 2021 23:04:32 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="6cf6db0820c4e91bdcad9bf6ed3258ca";
logging-data="31733"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+4yPS2fQeW+Y3fQiLzU1zj"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.1.1
Cancel-Lock: sha1:lB1r4slH9GgMGdLOLm6y0w5d4sc=
In-Reply-To: <in5iifF4i5gU1@mid.individual.net>
Content-Language: en-US
 by: Don Y - Fri, 6 Aug 2021 23:04 UTC

On 8/6/2021 12:58 PM, Niklas Holsti wrote:

>>>>>>> The source code is downloadable; see http://bound-t.com/download/src.
>>>>>>> The copyright text is of my own writing, but I'm open to switching to
>>>>>>> some better-known copyright such as GPL or even some non-viral version.
>>>>>>
>>>>>> Ah, OK. I may have a look at it to see how well it works and
>>>>>> how much work to port to ARM objects. Given that you've not
>>>>>> done so, already (despite your familiarity with the codebase),
>>>>>> I suspect that's not a trivial task?
>>>>>
>>>>> There is an ARM TDMI port (32-bit ARM code and THUMB, pre Cortex), but of
>>>>> course that architecture is out of date. I started a port to ARM Cortex-M,
>>>>> but did not (yet) finish it for the reasons described on the status page.
>>>>>
>>>>> Note that the tool is implemented in Ada.
>>>>
>>>> OK. It's been ~20 years since I wrote a line of Ada code but I doubt it
>>>> will take much to "refresh" those memory cells. Esp as this likely doesn't
>>>> have synchronization issues, RT constraints, etc.
>>>
>>> Right. The only use of tasking features is to set an upper limit on the
>>> execution time of the analysis, and that feature is easy to remove if needed.
>>>
>>> The code mostly relies on the 1995 Ada standard, with some use of Ada 2005
>>> additions.
>>
>> OK. I'll have to build a more current version of GNAT.
>
> For playing around, I would just use the GNAT Community Edition. Or the FSF
> GNAT that comes with MinGW32.

Ugh! No, I'll just build a fresh copy. I do all my development
under NetBSD so have everything I want/need ('cept the Ada tools)
there, already.

>>>>> Porting to a new target processor means writing procedures to decode the
>>>>> machine instructions and translate them to the internal representation
>>>>> used by the analysis.
>>>>
>>>> That shouldn't be hard -- except for the "timing uncertainties" in the
>>>> processor. (Did you rely on some blanket generalization -- like all
>>>> caches cold -- as you are looking for WORST case timing? OTOH, a
>>>> loop known to fit in a cache line *should* expect that speedup... :< )
>>>
>>> At present the tool assumes that every instruction and control transfer can
>>> be assigned its own WCET, in machine cycles, independent of other context or
>>> data
>>
>> So, you just sum worst case times? You don't, for example, alter
>> times based on conditionals?
>
> (Note: I say "WCET" below, but really I should always say "upper bound on the
> WCET".)

Understood.

> The analysis works on the control-flow graph (per subprogram). The WCET for
> each basic block is the sum of the WCETs of the instructions in that block. The
> WCET for an execution path through the graph (from entry to return) is the sum
> of the WCETs of the basic blocks in the bath, plus the WCETs assigned to each
> edge (control transfer) between basic blocks in the path.

So, the costs of conditional control transfers are handled separately (?)

> The WCET for the
> whole graph is computed by a pessimisation over all syntactically possible
> paths through the graph, using an Integer Linear Programming solver (lp_solve,
> for Bound-T). This method is common in WCET analysis and is called IPET, for
> Implicit Path Exploration Technique.
>
> By "syntactically possible" I mean that the tool generally does not attempt to
> find semantically or logically infeasible paths. For example, if a subprogram
> has this form:
>
> if boo then
> perform computation A;
> else
> perform computation B;
> end if;
> perform computation C;
>
> then the WCET for the subprogram is estimated as max(WCET(A),WCET(B)) +
> WCET(C). But if the subprogram has this form:
>
> if boo then
> perform computation A;
> end if;
> perform computation C;
> if not boo then
> perform computation B;
> end if;
>
> then the WCET for the subprogram is estimated as WCET(A) + WCET(C) + WCET(B).
> In other words, the analysis (usually) does not discover that the conditions
> "boo" and "not boo" are mutually exclusive.

OK. This is different from how a DSE-based tool would approach the problem.
It would walk through the code and "solve" for each variable that affects
control flow or execution cost. So, on one "probe", it would set boo
to "TRUE" and evaluate ALL of the consequences of that choice.

Then, would repeat the exercise with boo as FALSE.

(hence, it is more costly -- though could be made less so if it
wasn't actively probing for new cases along the way)

>> I assume this is semi table-driven (?)
>
> I don't understand that question. Please clarify.

A large number of opcodes, each with particular costs.
Do you build a jungle of conditionals to subdivide the
"opcode space" into groups of similar-cost operations?
Or, do you just have a table of:

{opcode, mask, type[1], cost}

[1] used to apply some further heuristics to your
refinement of "cost"

>> -- as a preface to inquiring as to
>> how you develop (and verify!) a test suite?
>
> In the same way as for any complex program. Final validation by running and
> measuring test code on a real processor or a cycle-accurate simulation.

Ah, OK. So, you could "can" that particular exemplar and use it
to test a modification to the code (without having to run the app
on "real hardware", again)

I don't rely on "live" tests for my code. Rather, I use tools to generate
good test coverage and then verify the results are what I expect. I find this
easier and more easily extensible (I can test ARM code by running an x86
port of that code)

>>> Good algorithms for computing WCET bounds for most kinds of instruction
>>> caches are known, but I did not get around to implementing any of those, so
>>> only cache-less processors are supported now. If you need WCET analysis of
>>> caches, the AbsInt tool is best.
>>
>> It's arguable whether (and to what extent) you should model I-cache effects.
>> E.g., in a multithreaded environment, the cache can be purged at some
>> frequency that a tool (or the developer, for that matter -- at least not
>> wrt the instruction stream) can't know. Aim high and be pleasantly
>> surprised...
>
> Such Cache-Related Preemption Delays (CRPDs) are a much-studied problem in WCET
> analysis. The most common solution is to first find out how the various tasks
> and interrupts can access memory blocks which potentially may collide in the
> caches, and then to take the worst possible interference into account in the
> schedulability analysis, which does know (or assumes) the worst case frequency
> of preemptions.
>
> For processors where cache misses are much slower than cache hits (which is
> fast coming to mean almost all processors) IMO an I-cache analysis is necessary
> for static WCET analysis to be useful.

I look at it the other way around. Assume there is NO cache. You know that
your code WILL run in less time than this case. Regardless of the frequency
or presence of competing events.

Processors are fast enough, now, that you can usually afford to "step up"
in capability for comparably little cost.

And, if you've minimized the number of things that *must* meet specific
timing/performance goals -- and left everything else as a lower
priority/importance secondary goal -- then cache just increases the
performance of those "less important" goals, pleasantly.

>> [How do you handle accesses to memories with different *basic* access times?]
>
> For code fetch the address is always statically known, so the correct access
> time can be selected and included in the WCET for the instruction when the
> instruction is decoded.

So, you know the access characteristics of each block of memory in which code
may reside.

> For data accesses, if different instructions are used for different memories
> (as in the 8051 architecture, for example), the proper access time can be
> included in the WCET for the instruction when the instruction is decoded.
>
> If the same instructions are used to access memories with different access
> times, depending on the address, and the memory addresses are dynamically
> determined at run time, the practical but pessimistic way is to use the largest
> of the access times, that is, assume that the slowest memory is accessed. In
> principle the tool can try to analyze the address computations and might find
> sufficient bounds on the address to ensure that a faster memory is accessed,
> but the analysis methods currently available in Bound-T seldom manage that, and
> can be quite slow.


Click here to read the complete article
Pages:12
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor