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

Groups > comp.arch.embedded > #30780

Re: Stack analysis tool that really work?

Show all headers | View raw

On 2021-08-07 20:34, Don Y wrote:
> On 8/7/2021 9:50 AM, Niklas Holsti wrote:
>> On 2021-08-07 18:09, Don Y wrote:
>>> On 8/7/2021 4:09 AM, Niklas Holsti wrote:
>>
>>
>> (On how the Bound-T tool models instructions for stack and WCET 
>> analysis:)
>>
>>>> The internal model includes not only the cost of the instruction, 
>>>> but also its effect on the computation. For example, an instruction 
>>>> like "increment the accumulator", INC A, would be decoded into a 
>>>> model that says
>>>>
>>>>      WCET: 1 cycle.
>>>>      Control flow: to next instruction, unconditional.
>>>>      Effect: A := A + 1.
>>>>
>>>> and also the effect, if any, on condition flags.
>>>
>>> Why do you care about the "effect"?  Are you trying to determine
>>> which branches will be taken?  How many iterations through loops?
>>> etc.
>>
>> The effect is necessary for any analysis that depends on run-time 
>> values. Loop bounds are the prime example for WCET analysis, but 
>> stack-usage analysis also needs it. For example, the effect of a push 
>> instruction is to increment the "local stack height" model variable by 
>> some number that reflects the size of the pushed data (which size can, 
>> in principle, be non-static and computed at run time).
> 
> OK.  But, you're not trying to emulate/simulate the complete algorithm;
> just handle the side effects of value changes.
> 
> But wouldn't you *have* to do a more thorough emulation?
> 
> foo(count) {
>     for (i = 0; i < 5 * count; i++) {
>         diddle()
>     }
> }


The point and aim of _static_ analysis is to abstract the computation to 
model only the aspects that are relevant for the goals of the analysis, 
and especially to avoid any step-by-step emulation or interpretation -- 
that would become "dynamic analysis".

For that example, analysing the subprogram foo stand-alone, the WCET 
analysis in Bound-T would conclude that, in the loop:

- The variable "i" is an induction variable that increases by one on 
each iteration. This looks promising, and means that Bound-T can model 
the value of "i" as the initial value (zero) plus the loop iteration 
number (starting the count at iteration number zero).

- But the analysis will not find a numeric upper bound on the iteration 
number, because the value of "count" is unknown.

If this analysis of foo occurs while analysing some higher-level 
subprogram that calls foo, Bound-T would next try to compute bounds for 
the actual value of "count" in each such call. Say that the call is simply

    foo (33);

This would make Bound-T reanalyze foo in the context count=33, which 
would show that the loop can be repeated only under the condition

    5 * (iteration number) < 33

equivalent to (iteration number) < 33/5 = 6, which bounds the number of 
loop iterations and lets Bound-T produce a WCET bound for this specific 
call of foo (assuming that Bound-T can produce a WCET bound for the 
"diddle" subprogram too).

Such repeated analyses down a call-path with increasing amount of 
context will of course increase the analysis time.

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