A very old gcc "bug"

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11203

by vinutheraj • 17 years ago

14 19 17 years ago

gcc.gnu.org

zandorg• 17 years ago

I find it hard to believe that you wouldn't know how many registers code should use. However - it's not C code, it's assembly code, so it seems unfair to blame gcc - a C compiler.

matttah• 17 years ago

register allocation is a notoriously hard problem. To make matters worse, registers on different architectures have vastly different properties.

rbanffy• 17 years ago

Wouldn't it be simple in SPARC-like architectures with register windows?

yuvi4• 17 years ago

There are a couple reasons you wouldn't know that (for an entire inline asm function):

1. x86_64 vs. x86_32. It's possible that you'd want to use more registers than 32-bit has. In this case, it's usually optimal to use memory operands on x86_32 but registers on x86_64.

2. gcc _will not_ allow you to use ebx in inline asm with PIC code. Likewise with ebp with frame pointer. There's no technical reason gcc couldn't just save+restore those registers around the block, but it doesn't.

3. The case in the bugreport: you have various locations in memory you want to address, and you want gcc to figure out their addresses for you. Without analysis that eliminates identical registers, the naive implementation of using 1-2 new registers per operand will quickly fail.

viraptor• 17 years ago

> There's no technical reason gcc couldn't just save+restore those registers around the block, but it doesn't.

While it's not impossible to do, it makes debugging a lot harder. gdb would have a much harder job of figuring out what's going on if the code messed with ebp, since the fp location would depend on the code. Some more debug information to describe that location could solve the problem... but why create that problem in the first place.

jacquesm3• 17 years ago

read comment #24:

Martin, you should realize that this problem cannot be solved. Yes, there will perhaps be a time when this particular test case compiles, though I think that is unlikely. But anyway, then there will be other cases that fail.

The reason is dead simple: register allocation is NP-complete, so it is even theoretically not possible to write register allocators that always find a coloring. That means any register allocator will always fail on some very constrained asm input. And you cannot allow it to run indefinitely until a coloring is found, because then you've turned the graph coloring problem into the halting problem because you can't prove that a coloring exists and that the register allocator algorithm will terminate.

So really it doesn't matter at all whether or not your specific inline asm compiles or not. When yours does, someone else's will fail.

yuvi4• 17 years ago

You skipped over 26, 27, and 34...

jacquesm3• 17 years ago

You're right, I stopped reading at that point. My bad!

ars3• 17 years ago

You are not the only one who does not understand the halting problem.

The halting problem only says you can not prove every program will (or won't) halt - the general case.

It says nothing at all about any specific case, and there are plenty of programs where you can prove they halt.

And NP just means the solution does not scale well, not that it can't be done.

And NP-complete is something else entirely. It has to do with being able to interconvert all NP-complete problems (i.e. if you solve one you solve all).

There are many NP problems that are not NP-complete. Proving any particular problem is NP-complete, and not just NP is usually a big deal, so don't just throw that term around.

jacquesm3• 17 years ago

It was a quote from the original thread.

As for your explanation, yes, that's correct. The thing that I didn't get about the way they were sparring on the list was that if there is a solution the problem might not be solved in an elegant way, but with the number of variations involved you could simply brute force it.

Then if a solution exists you'll find it, if it doesn't exist then you can report that. After all, if you say you want to put 12 variables in to 7 registers and there is no possible way then there is no possible way. If there is such a possibility the number of permutations is small enough that it could be found anyway.

GCC contributes to the problem by having some overhead that reserves registers that could be saved on the stack for the duration of this part of the computation.

Dilpil• 17 years ago

My favorite gcc trick is to compile and run the following two line, and then try to reconcile the results.

x = 7;

printf("%d %d %d",x++,++x,x++);

x = 7;

printf("%d %d %d",x++,x=2,x++);

Go ahead, try it, run it, and explain the output.

vinutheraj• 17 years ago

http://stackoverflow.com/questions/376278/parameter-evaluati...

https://www.securecoding.cert.org/confluence/display/seccode...

Basically, do not depend on the order of evaluation of arguments to a function call, because it is unspecified and left to the implementation to decide according to the C99 standard.

EDIT: Another explanation, pertinent to your example can be found here - http://c-faq.com/expr/evalorder2.html

ecaron• 17 years ago

For those curious, the output is: 9 10 7 2 3 7

The output should be (at least from my understanding and what PHP renders): 7 9 9 7 2 2

As far as reconciliation, I guess the first line makes sense when you think about it as machine code and how the pointers probably behave. The second line though, seems quite evil and I am going to go hide under my "Rails will save me" blanket until someone can explain this voodoo.

yuvi4• 17 years ago

clang gives 7 9 9 7 2 2 as well. gcc gives 7 10 9 7 3 2 when targeting arm.

2,3,7 are all valid possibilities for the 4th and 6th numbers, but apparently gcc interprets the 5th as 2 + 1 somehow, which I can't see as being valid whatsoever.

burke• 17 years ago

Very neat.

        movl    $7, -4(%rbp)
        movl    -4(%rbp), %ecx
        addl    $1, -4(%rbp)
        movl    $2, -4(%rbp)
        movl    -4(%rbp), %esi
        addl    $1, -4(%rbp)
        movl    -4(%rbp), %edx
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf

A very old gcc "bug"

Related Stories