>> Note some safety critical systems do not permit optimisations.
>
> I'd be interested to see how they [the enforcers of this rule] cope
> with the behaviour of the average compiler, since one of the things
> it's likely to do is convert the HLL into an intermediate
> representation and then start transformations on that intermediate
> rep., some of which will never be visible outside the compiler but
> most of which are certainly optimi[sz]ations and may not even be
> disablable, before it even thinks about emitting code. Would they
> disallow the use of such a compiler? Or is "do not permit
> optimisations" not intended to be taken literally, or to this depth?
>
> mlp
In a DO-178B level A project the practice is generally to have source to
object code traceability. That is to say, inspect/verify the output of the
compiler for a given construct, then check that the output is the same each
time the same construct is used. This is then used in combination with MCDC
test coverage to demonstrate that the compiler output does what you intend,
and nothing that you did not intend.
--
Regards,
Richard.
+ http://www.FreeRTOS.org
A free real time kernel for 8, 16 and 32bit systems.
+ http://www.SafeRTOS.com
An IEC 61508 certified real time kernel for safety related systems.
Reply by Chris Hills●June 13, 20072007-06-13
In article <m3d5006qus.fsf@Claudio.Messina>, Mark L Pappin <mlp@acm.org>
writes
>Chris Hills <chris@phaedsys.org> writes:
>
>> Note some safety critical systems do not permit optimisations.
>
>I'd be interested to see how they [the enforcers of this rule]
1 mandate no optimisation
2 look at the binary. At high SIL they do compare binary to source,
>cope
>with the behaviour of the average compiler, since one of the things
>it's likely to do is convert the HLL into an intermediate
>representation and then start transformations on that intermediate
>rep., some of which will never be visible outside the compiler but
>most of which are certainly optimi[sz]ations and may not even be
>disablable, before it even thinks about emitting code. Would they
>disallow the use of such a compiler?
Yes. The compiler usually validated before user.
>Or is "do not permit
>optimisations" not intended to be taken literally, or to this depth?
No it is taken to mean disable all compiler optimisations.
--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills Staffs England /\/\/\/\/
/\/\/ chris@phaedsys.org www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
Reply by ●June 13, 20072007-06-13
Chris Hills <chris@phaedsys.org> writes:
> Note some safety critical systems do not permit optimisations.
I'd be interested to see how they [the enforcers of this rule] cope
with the behaviour of the average compiler, since one of the things
it's likely to do is convert the HLL into an intermediate
representation and then start transformations on that intermediate
rep., some of which will never be visible outside the compiler but
most of which are certainly optimi[sz]ations and may not even be
disablable, before it even thinks about emitting code. Would they
disallow the use of such a compiler? Or is "do not permit
optimisations" not intended to be taken literally, or to this depth?
mlp
Reply by David Brown●June 11, 20072007-06-11
Paul Keinanen wrote:
> On Mon, 11 Jun 2007 09:35:11 +0200, David Brown
> <david@westcontrol.removethisbit.com> wrote:
>
>> No, it is not that easy to make a full trace buffer this way.
>> Continuous single-stepping (whether by using the trace facility of many
>> larger processors, or with external help such as a debugger or your
>> suggested interrupt trick) will let you trace program flow, but not data
>> flow. Thus you can see when the statement "*p++ = *q++;" was executed,
>> but you don't have a record of what p, q, *p or *q are before and after
>> the operation. To do that needs something much more - a hardware trace
>> of data transactions, trapping on memory writes, examination of the
>> statements before they are executed, or tricks like regular snapshots
>> and then replaying the code up to the point of interest.
>
> For truly memory-to-memory architectures, you would indeed need some
> emulation code to interpret the instruction, to see what "side
> effects" the instruction had on the memory contents.
>
> For many common architectures, at least the pointers would normally be
> in registers, so taking a register snapshot after each instruction
> would help a lot.
>
> On RISCy architectures, most data transfer would also go through a
> register, so again, the transferred value would be visible in a
> register trace.
>
Register snapshots would clearly help, but if an instruction causes a
write to memory, then knowing the address is only part of the solution.
Before executing the instruction, you'd have to figure out that the
instruction is a write, figure out which register holds the address,
then read and log the original data. Then you carry out the
instruction, and log the data written. You have to have the original
data so that you can restore it when stepping backwards past the write
instruction. That's why I suggested trapping on memory writes (even if
your processor does not have an MMU, it could be possible to temporarily
make the ram read-only) - that way you don't have to figure everything
out yourself, but can get it from the bus error exception stack frame
(or equivalent for your processor).
> Of course tracing in deeply pipelined architectures can cause strange
> results, unless the pipeline can be disabled during tracing/single
> stepping.
>
Indeed, it would get so messy, and give such an unrealistic picture due
to timing differences, that it's unlikely to be of any real help at all.
As far as I can see, the use of things like trace traps, snapshots,
replays, hardware trace buffers, etc., can give you varying benefits for
varying costs, but the only way to get true backstepping of relevance to
embedded development (where you can seldom rely on having the same input
data on two runs, cutting out the Lizard technique I mentioned earlier),
is by simulation of the processor. In the days of full hardware
emulators for microcontrollers (before jtag-type debugging became common
even on small devices), you could get expensive emulators that included
full tracing while running at cycle-correct speeds. With modern
devices, it's a lot less practical.
> Paul
>
Reply by Paul Keinanen●June 11, 20072007-06-11
On Mon, 11 Jun 2007 09:35:11 +0200, David Brown
<david@westcontrol.removethisbit.com> wrote:
>
>No, it is not that easy to make a full trace buffer this way.
>Continuous single-stepping (whether by using the trace facility of many
>larger processors, or with external help such as a debugger or your
>suggested interrupt trick) will let you trace program flow, but not data
>flow. Thus you can see when the statement "*p++ = *q++;" was executed,
>but you don't have a record of what p, q, *p or *q are before and after
>the operation. To do that needs something much more - a hardware trace
>of data transactions, trapping on memory writes, examination of the
>statements before they are executed, or tricks like regular snapshots
>and then replaying the code up to the point of interest.
For truly memory-to-memory architectures, you would indeed need some
emulation code to interpret the instruction, to see what "side
effects" the instruction had on the memory contents.
For many common architectures, at least the pointers would normally be
in registers, so taking a register snapshot after each instruction
would help a lot.
On RISCy architectures, most data transfer would also go through a
register, so again, the transferred value would be visible in a
register trace.
Of course tracing in deeply pipelined architectures can cause strange
results, unless the pipeline can be disabled during tracing/single
stepping.
Paul
Reply by David Brown●June 11, 20072007-06-11
Paul Keinanen wrote:
> On Fri, 08 Jun 2007 09:35:02 +0200, David Brown
> <david@westcontrol.removethisbit.com> wrote:
>
>> Back-stepping cannot be done without hardware support or simulation of
>> some sort. Either your product uses hardware support in some way, or it
>> simply doesn't do full backwards debugging. I'm quite happy to believe
>> that you can get somewhat beyond the simple call-stack view of gdb
>> without more sophisticated hardware, but I am sceptical to your claims
>> of back-stepping since you offer no explanation as to how it might work
>> (at least, none that I can find).
>
> Any processors with a decent trace bit/single step support should be
> able to handle this quite easily, although not in real time :-).
>
> In such systems, the trace interrupt service routine is executed after
> each instruction, so it is easy to create a trace buffer. For instance
> on the PDP-11, the trace mode used the same ISR as the breakpoint trap
> ISR, so you had to check from the processor status word, if the T
> (trace) bit was set or not, to determine, what was the cause of the
> interrupt.
>
<snip for brevity>
No, it is not that easy to make a full trace buffer this way.
Continuous single-stepping (whether by using the trace facility of many
larger processors, or with external help such as a debugger or your
suggested interrupt trick) will let you trace program flow, but not data
flow. Thus you can see when the statement "*p++ = *q++;" was executed,
but you don't have a record of what p, q, *p or *q are before and after
the operation. To do that needs something much more - a hardware trace
of data transactions, trapping on memory writes, examination of the
statements before they are executed, or tricks like regular snapshots
and then replaying the code up to the point of interest.
mvh.,
David
Reply by Paul Keinanen●June 8, 20072007-06-08
On Fri, 08 Jun 2007 09:35:02 +0200, David Brown
<david@westcontrol.removethisbit.com> wrote:
>Back-stepping cannot be done without hardware support or simulation of
>some sort. Either your product uses hardware support in some way, or it
>simply doesn't do full backwards debugging. I'm quite happy to believe
>that you can get somewhat beyond the simple call-stack view of gdb
>without more sophisticated hardware, but I am sceptical to your claims
>of back-stepping since you offer no explanation as to how it might work
>(at least, none that I can find).
Any processors with a decent trace bit/single step support should be
able to handle this quite easily, although not in real time :-).
In such systems, the trace interrupt service routine is executed after
each instruction, so it is easy to create a trace buffer. For instance
on the PDP-11, the trace mode used the same ISR as the breakpoint trap
ISR, so you had to check from the processor status word, if the T
(trace) bit was set or not, to determine, what was the cause of the
interrupt.
On processors that does not support the trace/single step feature, it
would be a good idea to check what happens if an interrupt line is
constantly active, does it execute the same ISR again without
executing even a single instruction or does it execute the next
instruction and then executes the ISR again. In the latter case, this
feature could be used to build the trace buffer.
Even with edge sensitive interrupts, the trace feature could be
implemented with a minimum hardware (a simple monostable). The trace
ISR triggers the monostable and the monostable output is connected to
the interrupt request pin. The falling edge of the monostable
activates the interrupt again. Instead of a monostable, a few
inverters in series could produce enough delay so that the ISR exits
and the decoding of the next instruction will advance to a point that
the next instruction is executed, even if the interrupt request line
is active.
Paul
Reply by ●June 8, 20072007-06-08
Wilco Dijkstra wrote:
> I meant the worst case complexity. People too often only look at
> the theoretical worst case rather than at the amortized average
> case which is what matters in practise.
Only if said practise by some stroke of luck happens not include
real-time constraints. This would be the wrong newsgroup to refer to
such circumstances as "in practise" without qualification. Actually,
worst-case time is probably *more* important in our line of work than
average time would be.
> My standard implementation chooses the pivot from the middle,
> which works perfectly for partially sorted, sorted, reverse sorted
> inputs, and even the degenerate case of all elements identical.
Brushing the worst case under a different corner of the same carpet
doesn't really solve anything --- even if it's *very* big carpet.
> Mergesort works quite well on linked lists but is very inefficient
> on arrays as it isn't an in-place algorithm. Quicksort needs far
> fewer data swaps, and that is the main reason it wins over
> mergesort or heapsort.
Not really. Actual data swaps can be avoided the same way for all
internal sorting algorithms, to the point where all algorithms use the
same, perfect sequence of data moves (--> disjoint cycle decomposition
of the permutation). Which is why standard theoretical analysis doesn't
even bother looking at data moves, and instead qualifies algorithms by
the number of comparisons only.
Reply by CBFalconer●June 8, 20072007-06-08
Wilco Dijkstra wrote:
> "CBFalconer" <cbfalconer@yahoo.com> wrote:
>> Wilco Dijkstra wrote:
>>> "CBFalconer" <cbfalconer@yahoo.com> wrote:
>>>> David Brown wrote:
>>>>
>> ... snip ...
>>>
>>>>> This is why sorting is so interesting in algorithm design -
>>>>> depending on the requirements, and the kind and size of data
>>>>> you will be sorting, there are many different algorithms.
>>>>
>>>> This is one of the points about mergesort. It is ALWAYS O(nlogn).
>>>> In addition, it is always (properly coded) a stable sort. Neither
>>>> applies to quicksort. Mergesort code can be very compact.
>>>
>>> Mergesort works quite well on linked lists but is very inefficient
>>> on arrays as it isn't an in-place algorithm. Quicksort needs far
>>> fewer data swaps, and that is the main reason it wins over
>>> mergesort or heapsort.
>>
>> Take a look at my implementation, as referenced before. No data is
>> moved, only pointers.
>
> I did, and it's a small and easy to understand implementation indeed
> (unlike some of the copying variants). Other sorts can avoid data swaps
> in a similar way. However when sorting pointers, you still need pointer
> swaps, and merge sort needs far more swaps than a good quicksort.
"CBFalconer" <cbfalconer@yahoo.com> wrote in message news:4668B4F9.E4FC387F@yahoo.com...
> Wilco Dijkstra wrote:
>> "CBFalconer" <cbfalconer@yahoo.com> wrote:
>>> David Brown wrote:
>>>
> ... snip ...
>>
>>>> This is why sorting is so interesting in algorithm design -
>>>> depending on the requirements, and the kind and size of data you
>>>> will be sorting, there are many different algorithms.
>>>
>>> This is one of the points about mergesort. It is ALWAYS O(nlogn).
>>> In addition, it is always (properly coded) a stable sort. Neither
>>> applies to quicksort. Mergesort code can be very compact.
>>
>> Mergesort works quite well on linked lists but is very inefficient
>> on arrays as it isn't an in-place algorithm. Quicksort needs far
>> fewer data swaps, and that is the main reason it wins over
>> mergesort or heapsort.
>
> Take a look at my implementation, as referenced before. No data is
> moved, only pointers.
I did, and it's a small and easy to understand implementation indeed
(unlike some of the copying variants). Other sorts can avoid data swaps
in a similar way. However when sorting pointers, you still need pointer
swaps, and merge sort needs far more swaps than a good quicksort.
Wilco