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

Groups > comp.arch.embedded > #30771

Re: Stack analysis tool that really work?

Show all headers | View raw

On 2021-08-07 5:55, George Neuner wrote:
> On Thu, 5 Aug 2021 18:39:51 +0300, Niklas Holsti
> <niklas.holsti@tidorum.invalid> wrote:
> 
>>   :
>> 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.
    ...

> How do you handle branch/jump mispredicts?


See above re the assumptions of the tool.

The WCET analysis function of the Bound-T tool is (at present) suited 
only for simple, deterministic processors. The tool development started 
in the late 1990s when the company I then worked for developed 
applications mainly for such processors.

If the processor uses a static branch prediction scheme (for example, 
predict forward branches as not taken and backward branches as taken), 
the mispredict penalty can be included in the WCET assigned to the 
non-predicted edge in the control-flow graph at instruction decode-time.

For dynamic (history-dependent) branch predictors, various models for 
static analysis have been proposed and published, but they have the same 
problems as cache-analysis models: the HW microarchitectures are 
becoming more and more complex and varied, making the modelling effort 
more expensive, both in implementation effort and in analysis time, and 
reducing the customer base for each specific model.

The WCET-analysis tools from AbsInt include detailed signal-by-signal 
simulations of the microarchitectures. Unfortunately such details are 
seldom documented well, and I believe AbsInt has had to enter special 
agreements with processor suppliers for access to such information. And 
the details can change with each processor revision...

Speculative executions such as branch prediction can create so-called 
"timing anomalies" which make the WCET analysis much harder. A timing 
anomaly is any property of a processor that makes it invalid to estimate 
the WCET of a sequence of instructions by assuming that the first 
instruction encounters its worst case (for example, a cache miss instead 
of a cache hit) and then continuing the analysis of the rest of the 
sequence while propagating that assumption forward as an assumption on 
the state of the processor.

The canonical example of timing anomalies are processors where a cache 
hit at one instruction changes the processor state in such a way that a 
later instruction takes much longer than it would have taken, had the 
first instruction encountered a cache miss instead of a hit. Propagating 
the "first instruction missed" assumption to the context of the later 
instruction may make the analysis under-estimate the execution time of 
that later instruction. To handle timing anomalies, the analysis must 
consider all possible combinations: first instruction hits or misses, 
second instruction hits or misses, etc. Exponential complexity.

It amuses me that such processor properties, which are/were the bane of 
static WCET analysis, are now in the limelight as the origin of the side 
channels for various malware, such as Spectre exploits.


> More importantly, how do you handle chains of conditional branches
> and/or switch/case constructs which can mispredict at every decision
> point?  The branch targets may not be in cache - neither mispredicted
> targets nor the actual one.  Worst case for a horribly mispredicted
> switch/case can be absolutely dreadful.


I don't know if those questions are addressed to me (re the Bound-T 
tool) or to WCET analysis in general. The advanced WCET tools, like the 
ones from AbsInt, do try to cover such cases by their cache analysis to 
provide a safe upper bound on the WCET, but the degree of pessimism 
(over-estimation) increases with the complexity of the code.

That said, in many programs most of the processing time is taken by 
relatively simple loops, for which the present I-cache analyses work 
quite well, and for which even D-cache analysis can (I believe) work 
satisfactorily if the memory addressing patterns are regular.

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