Re: Stack analysis tool that really work?

From	Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups	comp.arch.embedded
Subject	Re: Stack analysis tool that really work?
Date	2021-08-05 18:39 +0300
Organization	Tidorum Ltd
Message-ID	<in2f27FfeehU1@mid.individual.net> (permalink)
References	(4 earlier) <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>

Show all headers | View raw

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.

Thread

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

csiph-web