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

Groups > comp.compilers > #1228 > unrolled thread

Mysterious triple test failures

Back to article view | Back to comp.compilers

Contents

  Mysterious triple test failures "Nils M Holm" <nmh@t3x.org> - 2014-05-03 21:38 +0200
    Re: Mysterious triple test failures Kaz Kylheku <kaz@kylheku.com> - 2014-05-03 22:19 +0000
      Tripe test failure update "Nils M Holm" <nmh@t3x.org> - 2014-05-04 10:53 +0200
        Re: Triple test failure update Chris Dodd <cdodd@acm.org> - 2014-05-23 01:50 +0000
          Re: Triple test failure update "Nils M Holm" <nmh@t3x.org> - 2014-05-23 09:09 +0200
          Re: Triple test failure update alexfrunews@gmail.com - 2014-05-23 02:17 -0700
    Re: Mysterious triple test failures mrs@Kithrup.COM (Mike Stump) - 2014-05-04 04:47 +0000
    Re: Mysterious triple test failures alexfrunews@gmail.com - 2014-05-04 03:57 -0700
      Re: Tripe test failure update "Nils M Holm" <nmh@t3x.org> - 2014-05-05 10:30 +0200

#1228 — Mysterious triple test failures

In the recent months, several people who ported and/or used my
SubC compiler[1] reported that the triple test failed, but the
compiler still worked fine.

I am running the triple test as follows:

Subc sources ---[ third-party C compiler  ]---> stage-0 SubC
Subc sources ---[      stage-0 SubC       ]---> stage-1 SubC
Subc sources ---[      stage-1 SubC       ]---> stage-2 SubC

(where x---[y]--->z means "compile x with y to z"). Finally the
stage-1 and stage-2 compilers are compared. When they are equal,
the triple test is passed.

Now it has happened that this test failed, resulting in stage-1
and stage-2 compiler of identical size, but with tens of thousands
of differences. However, both compilers seem to work fine. The
differences are not in the symbol table, stripping the binaries
did not make any difference.

Further tests have shown that the assembly language output of
the differing compilers is identical.

This happened on 386-based OpenBSD and x86-64-based Linux systems.

So, what is going on here? Does anybody have an explanation?

And: to work around the problem, I thought about comparing the
assembly output of the compilers instead of the binaries. This
should yield the same results, shouldn't it?

Please let me know what you think!

[1] http://t3x.org/subc/

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org
[Are the stage-0 and stage-1 assembly sources the same?  The
first thing that occurs to me is that the code is laid out
differently so the variable-length branch logic has long
and short instructions in different places. -John]

[toc] | [next] | [standalone]

#1229

On 2014-05-03, Nils M Holm <nmh@t3x.org> wrote:
> In the recent months, several people who ported and/or used my
> SubC compiler[1] reported that the triple test failed, but the
> compiler still worked fine.

If you don't understand it, who can? Haha.

This isn't real-time-event-processing software with nonrepeatable
inputs and scheduling patterns. :)


>
> I am running the triple test as follows:
>
> Subc sources ---[ third-party C compiler  ]---> stage-0 SubC
> Subc sources ---[      stage-0 SubC       ]---> stage-1 SubC
> Subc sources ---[      stage-1 SubC       ]---> stage-2 SubC
>
> (where x---[y]--->z means "compile x with y to z"). Finally the
> stage-1 and stage-2 compilers are compared. When they are equal,
> the triple test is passed.
>
> Now it has happened that this test failed, resulting in stage-1
> and stage-2 compiler of identical size, but with tens of thousands
> of differences.

It means you have some uninitialized variable or something which leads
the third-party-C-compiled SubC to write different code from the
SubC-compiled SubC.

> However, both compilers seem to work fine.

Do these tests execute with zero errors under Valgrind on a Linux box?

> Further tests have shown that the assembly language output of
> the differing compilers is identical.

But that of stage-0 and stage-1 isn't identical: they produce
different output when compiling SubC. Necessarily so: the stages use
completely different compilers.  But those outputs, in turn, have a different
behavior: they produce different code!

If you were to iterate and make a stage-3 with stage-2, it would probably come
out identical to stage-2. I.e. there is a "fixed point" when you feed
the compiler into itself.

> This happened on 386-based OpenBSD and x86-64-based Linux systems.
>
> So, what is going on here? Does anybody have an explanation?
>
> And: to work around the problem, I thought about comparing the
> assembly output of the compilers instead of the binaries. This
> should yield the same results, shouldn't it?

Only if the assembly stage is responsible for the differences.

> Please let me know what you think!

Disable all special code-generation options like optimizations.
If that makes the problem go away, re-introduce them one by one until
a difference shows up.

A bug could be causing some optimization or other code transformation decision
to be done differently.  If such a decision is semantics-preserving
(which such decisions often are) then the differing variants of the
translated code behave the same way.

It still points to a bug, which is why it's smart to do that comparison between
the stages.

You have a simple case here of a program compiled by two different C compilers
producing different output. How does that happen? I mean, let me count
the ways, right? Dependencies on orders of evaluation, uninitialized
storage, or numerous other "undefined behaviors". This is why a sweep with
a debugging tool like Valgrind wouldn't hurt.

[toc] | [prev] | [next] | [standalone]

#1233 — Tripe test failure update

I am currently running the following procedure to find out at which
point the triple test of my SubC compiler fails. This is what happens:

The stage-0 (third-party-compiled) scc0 is used to generate a stage-1
scc1. Then scc1 is used to generate the stage-2 compiler scc2.

Then scc1 compiles itself to 1) assembly 2) a binary. The same is done
with scc2.

The assembly output of scc1 and scc2 is identical, the binaries are not.
*Both* compilers seem to work perfectly fine.

The assembler and linker of the Linux system are used to generate
binaries from the assembly output.

Adding a stage-3 compiler (compiled with scc2) and comparing against
scc2 does not change anything: same assembly, different executables.

The test as described above works (identical binaries) on FreeBSD/386,
FreeBSD/x86-64, FreeBSD/ARM, NetBSD-x86-64, DOS-8086, and others.

It sometimes fails (maybe depending on version?) on Linux-x86-64.
(OpenBSD/386 was a false negative.)

Differences in the file are literally all over the place. A diff on
the hexdumps reports multiple thousand differences).

All differences I have found so far are related to addresses, like in
the following disassembly snippet:

SCC
00000353 74 02                          jz      0x00000357
00000355 EB 16                          ljmp    0x0000036D
00000357 E8 AD F6 00 00                 lcall   0x0000FA09   *****
0000035C 48                             dec     %eax
0000035D 89 04 25 38 96 61 00           movl    %eax, 0x619638(,1)
------------------------------------------------------------------
SCC1
00000353 74 02                          jz      0x00000357
00000355 EB 16                          ljmp    0x0000036D
00000357 E8 47 F6 00 00                 lcall   0x0000F9A3   *****
0000035C 48                             dec     %eax
0000035D 89 04 25 38 96 61 00           movl    %eax, 0x619638(,1)

I would say that the cause for the difference is in the assembler
or linker, but I would like to understand what is going on here.

John wrote:
[Are the stage-0 and stage-1 assembly sources the same?  The
first thing that occurs to me is that the code is laid out
differently so the variable-length branch logic has long
and short instructions in different places. -John]

Yes, the stages 0 and 1 generate identical assembly output,
so any change in the layout would have to happen in later
phases (i.e. assembly and linking). How can that happen?

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org
[When you compared the individual object files that the assembler
genereated, what did you find? -John]

[toc] | [prev] | [next] | [standalone]

#1252 — Re: Triple test failure update

"Nils M Holm" <nmh@t3x.org> wrote in news:14-05-008@comp.compilers:
> The assembly output of scc1 and scc2 is identical, the binaries are not.
> *Both* compilers seem to work perfectly fine.

So the difference is in the assembler or the linker.

Have you tried turning off ASLR (address space randomization)?  You
can do this on linux with

  # echo 0 > /proc/sys/kernel/randomize_va_space

If there is anything in the assembler or linker that depends on
addresses allocated in memory (such as hash tables?) then ASLR will
move things around, which may result in things being processed in a
different order and laid out differently.

Chris Dodd
cdodd@acm.org

[toc] | [prev] | [next] | [standalone]

#1253 — Re: Triple test failure update

Chris Dodd <cdodd@acm.org> wrote:
> So the difference is in the assembler or the linker.
>
> Have you tried turning off ASLR (address space randomization)?  You
> can do this on linux with
>
> # echo 0 > /proc/sys/kernel/randomize_va_space
>
> If there is anything in the assembler or linker that depends on
> addresses allocated in memory (such as hash tables?) then ASLR will
> move things around, which may result in things being processed in a
> different order and laid out differently.

Ah, this is interesting!  I had previously thought about ASLR, but
then thought that it cannot affect executables as long as they merely
sit on the hard disk.  Your comment sheds new light on this aspect.

Unfortunately, I have never been able to reproduce this behavior
myself (only heard about it from testers) and currently it does not
seem to be reproducible anywhere. This happened after I changed the
Makefile from

scc *.c

to

scc $(SRC)

so it looks like John and a few others here in c.c. where right. It
was most probably the order of objects passed to the linker. However,
should the problem re-appear, I will definitely try what you suggested!

Thanks!

Nils

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

[toc] | [prev] | [next] | [standalone]

#1254 — Re: Triple test failure update

On Thursday, May 22, 2014 6:50:19 PM UTC-7, Chris Dodd wrote:
> "Nils M Holm" <nmh@t3x.org> wrote in news:14-05-008@comp.compilers:
> > The assembly output of scc1 and scc2 is identical, the binaries are not.
> > *Both* compilers seem to work perfectly fine.
>
> So the difference is in the assembler or the linker.

I remember seeing *.c expand to a string containing all .c files. I'm not sure
how common this behavior of the OS shell is, but the list of files from such
an expansion may not be guaranteed to be sorted/ordered at all or always be in
one particular order. Interwebs tell me that the order may depend on the
setting of the environment variable LC_COLLATE (or an equivalent). And so,
yes, it may be an issue with the link order of the object (.o) files that
depends on the shell behavior if one uses wildcards in it.

AFAIR, in Spanish, the digraphs CH, LL (and RR?) used to collate differently
than they do now and than in English. They were considered single letters
(following C, L and R, respectively). So, for example, you could get these 2
different orders:

chico
cubo
llama
lobo

vs

cubo
chico
lobo
llama

Alex
[On any POSIX system, expanded shell wildcards are alphabetized.  I suppose
it's possible that local langauge settings could change the result, but that's
getting a bit far afield from compilers. -John]

[toc] | [prev] | [next] | [standalone]

#1230

In article <14-05-003@comp.compilers>, Nils M Holm <nmh@t3x.org> wrote:
>Now it has happened that this test failed, resulting in stage-1
>and stage-2 compiler of identical size, but with tens of thousands
>of differences. However, both compilers seem to work fine. The
>differences are not in the symbol table, stripping the binaries
>did not make any difference.

objdump -s, onjdump -d, objdump -h are your friends...  You can do
dumps and compare those outputs...  Also, for production comparisons,
come over to gcc (gcc.gnu.org) land, we have comparisons methods that
work across lots of machines and can deal with things like embedded
file time stamps and the like.

[toc] | [prev] | [next] | [standalone]

#1235

On Saturday, May 3, 2014 12:38:13 PM UTC-7, Nils M Holm wrote:
> In the recent months, several people who ported and/or used my
> SubC compiler[1] reported that the triple test failed, but the
> compiler still worked fine. ...

If the size is the same and the assembly code is the same and all
binaries appear to function and yet are different, I'd suggest to look
at the order in which the object files are linked together.

Alex

[toc] | [prev] | [next] | [standalone]

#1239 — Re: Tripe test failure update

John wrote:
> [When you compared the individual object files that the assembler
> genereated, what did you find? -John]

I do not have a 64-bit Linux machine for testing, but someone who
tried the compiler wrote me in an e-mail that the object files are
identical on his system and still the executables differ.

Yes, I know about time stamps, but have only once actually seen
them in the wild, in the COFF linker of Coherent. And anyway, a
timestamp would cause one single difference of a few bytes and
not in the text segment, wouldn't it?

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org
[Yes, that's right.  From what you've said, it sounds like modules
were linked in a different order. -John]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web