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

Groups > comp.arch.embedded > #30772

Re: Stack analysis tool that really work?

Show all headers | View raw

On 2021-08-07 2:04, Don Y wrote:
> On 8/6/2021 12:58 PM, Niklas Holsti wrote: 

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


You are braver than I am. Note that the front-end of GNAT is implemented 
in Ada, so it has to be bootstrapped with an Ada compiler. And the 
current version of GNAT requires quite an up-to-date Ada compiler for 
the bootstrap. In practice, I think people have found that only GNAT can 
build GNAT.

Many Linux distributions come with GNAT pre-built. Debian-derived 
distributions have good support, I hear.


>> 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 (?)


I'm not sure I understand your question. Each edge in the control-flow 
graph, that is, each transition from one instruction or one basic block 
to a possible next instruction or block, is assigned a WCET value when 
the instructions are decoded and entered in the control-flow graph. 
Usually this WCET is zero for a fall-through edge from a non-branch 
instruction to the next, and is non-zero only for edges from branch 
instructions, whether conditional or unconditional. For a conditional 
branch, the "not taken" edge usually has a zero WCET and the "taken" 
edge has some non-zero WCET, as specified in the processor documentation 
(remember we are assuming a simple processor).


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


I would say that the approach to translating instructions into their 
analysis models (elements in the control-flow graph) is usually not 
table-driven, but emulates the field-by-field decoding and case analysis 
that would be done by a disassembler or emulator (and Bound-T can 
produce a disassembly of the code). 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.


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


Yep.


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


At my former job, implementing SW for ESA satellite applications, we 
almost always tested the code first on normal PCs, in a simulated I/O 
environment, and then on the embedded target. Easier for Ada than for C.


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


Sometimes, but not always. The ESA applications we made were usually 
running (worst case) at about 70% processor load, and faster processors 
for space applications were very expensive, not only in euros but also 
in power, volume and mass, which are scarce resources in space.

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