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

Groups > comp.arch.embedded > #30768

Re: Stack analysis tool that really work?

Show all headers | View raw

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.

It would also require the user to be more specific about his execution
environment.

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

I'm thinking, specifically, about I/Os -- which are increasingly memory
mapped (including register spaces).

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