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

Groups > comp.arch.embedded > #30767

Re: Stack analysis tool that really work?

Show all headers | View raw

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.

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