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

Groups > comp.arch.embedded > #30774

Re: Stack analysis tool that really work?

Show all headers | View raw

On 8/7/2021 4:09 AM, Niklas Holsti wrote:
> 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.

I don't run Linux.  I already support Solaris/SPARC, Windows and NetBSD hosts.
Adding yet another just makes things harder.

I build all of the "programs" ("packages") on my NetBSD boxes.  In the past,
the userland was built by folks of dubious abilities.  They'd just try to
"get it to compile" (not even "compile without warnings").  So, there would
often be bugs and failures in the ported code.

[I recall a prebuilt gnuplot that didn't even successfully pass the
COMPREHENSIVE test suite -- because the person porting it didn't know
what certain functions should look like, graphically!]

Building myself lets me see the warnings/errors thrown.  And, also lets
me inspect the sources as, often, the configuration options are not
completely documented (but apparent *if* you look at the sources).

As building package Q may rely on package B and L, which, in turn rely on
F, G and Z, this is often a bit involved.  But, if those dependencies
can be used by other packages, that's less work, later.

[I keep track of what I build, the order I build them, any patches I
make to the sources, etc.]

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

OK, that's what I was addressing; namely, that the two outcomes of a
(conditional) branch can have different costs -- yet those appeared to be
"outside" the blocks that you were describing.

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

Oh!  I would have opted for a (possibly big) table.  But, that's just personal
preference (I like table driven algorithms)

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

Doesn't this require a fairly complete model of the processor?

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

Historically, it's been hard for me to have access to real hardware.
So, my development style pushes all the I/Os out to the fringes of
the algorithms; so there is little more than a "copy" that occurs
between the algorithm and the I/O.

So, I can debug most of my code (95+%) just by simulating input
values and capturing output values.  It's no worse than testing
a math library.

Then, to move to real hardware, just ensure that the transfers in and
out are atomic/intact/correct.

E.g., for my speech synthesizers, I just had them generate D/AC values
that I captured using some test scaffolding.  Then, massaged the captured
data into a form that a media player could process and "played" them
on a PC.

For my gesture recognizer, I captured/simulated input from the various
types of input devices in a form that the algorithms expected.  Then,
just passed the data to the algorithms and noted their "conclusions".

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

Yes, of course.  I'm speaking of the types of applications that I have dealt
with, not "universally".

My "cost constrained" days were back in the days of the "small/cheap CPU"
where you had to predict performance accurately -- but, doing so was
relatively easy (because processors had very predictable instruction
execution times).

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