Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #30766

Re: Stack analysis tool that really work?

Show all headers | View raw

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

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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