about the keyword "register"

Discussion in 'C Programming' started by Dave win, Dec 28, 2004.

  1. Dave win

    Dave win Guest

    howdy....
    plz take a look at the following codes, and tell me the reason.

    1 #define swap(a,b) a=a^b;b=b^a;a=a^b
    2
    3 int main(void){
    4 register int a=4;
    5 register int b=5;
    6 swap(a,b);
    7
    8 return 0;
    9 }
    The assemble code of the above code.

    (gdb) disassemble main
    Dump of assembler code for function main:
    0x08048334 <main+0>: push %ebp
    0x08048335 <main+1>: mov %esp,%ebp
    0x08048337 <main+3>: sub $0x8,%esp
    0x0804833a <main+6>: and $0xfffffff0,%esp
    0x0804833d <main+9>: mov $0x0,%eax
    0x08048342 <main+14>: add $0xf,%eax
    0x08048345 <main+17>: add $0xf,%eax
    0x08048348 <main+20>: shr $0x4,%eax
    0x0804834b <main+23>: shl $0x4,%eax
    0x0804834e <main+26>: sub %eax,%esp
    0x08048350 <main+28>: mov $0x0,%eax
    0x08048355 <main+33>: leave
    0x08048356 <main+34>: ret
    End of assembler dump.

    where is the XOR instruction?

    if I remove the keyword "register" in my C program.
    1 #define swap(a,b) a=a^b;b=b^a;a=a^b
    2
    3 int main(void){
    4 int a=4;
    5 int b=5;
    6 swap(a,b);
    7 return 0;
    8 }

    I'll got the following "monster" asm code...
    (gdb) disassemble main
    Dump of assembler code for function main:
    0x08048334 <main+0>: push %ebp
    0x08048335 <main+1>: mov %esp,%ebp
    0x08048337 <main+3>: sub $0x8,%esp
    0x0804833a <main+6>: and $0xfffffff0,%esp
    0x0804833d <main+9>: mov $0x0,%eax
    0x08048342 <main+14>: add $0xf,%eax
    0x08048345 <main+17>: add $0xf,%eax
    0x08048348 <main+20>: shr $0x4,%eax
    0x0804834b <main+23>: shl $0x4,%eax
    0x0804834e <main+26>: sub %eax,%esp
    0x08048350 <main+28>: movl $0x4,0xfffffffc(%ebp)
    0x08048357 <main+35>: movl $0x5,0xfffffff8(%ebp)
    0x0804835e <main+42>: mov 0xfffffff8(%ebp),%edx
    0x08048361 <main+45>: lea 0xfffffffc(%ebp),%eax
    0x08048364 <main+48>: xor %edx,(%eax)
    0x08048366 <main+50>: mov 0xfffffffc(%ebp),%edx
    0x08048369 <main+53>: lea 0xfffffff8(%ebp),%eax
    0x0804836c <main+56>: xor %edx,(%eax)
    0x0804836e <main+58>: mov 0xfffffff8(%ebp),%edx
    0x08048371 <main+61>: lea 0xfffffffc(%ebp),%eax
    0x08048374 <main+64>: xor %edx,(%eax)
    0x08048376 <main+66>: mov $0x0,%eax
    0x0804837b <main+71>: leave
    0x0804837c <main+72>: ret
    End of assembler dump.

    Another strange thing is the xor instruction.
    Plz see the code:
    0x0804835e <main+42>: mov 0xfffffff8(%ebp),%edx
    0x08048361 <main+45>: lea 0xfffffffc(%ebp),%eax
    0x08048364 <main+48>: xor %edx,(%eax)
    0x08048366 <main+50>: mov 0xfffffffc(%ebp),%edx
    0x08048369 <main+53>: lea 0xfffffff8(%ebp),%eax
    0x0804836c <main+56>: xor %edx,(%eax)

    why dont use
    xor %edx,(%eax)
    xor %eax,(%edx)
    to replace the redundent
    0x08048366 <main+50>: mov 0xfffffffc(%ebp),%edx
    0x08048369 <main+53>: lea 0xfffffff8(%ebp),%eax

    Thanx!!!!
     
    Dave win, Dec 28, 2004
    #1
    1. Advertisements

  2. Dave win

    Michael Mair Guest

    This macro will break when used in a loop.
    Use
    #define swap(a,b) do { \
    a=a^b;b=b^a;a=a^b;\
    } while(0)
    to circumvent this problem.
    Note that this XOR trick is not necessarily faster
    than whatever your compiler does when you let it
    optimise the code.
    This is not topical in comp.lang.c; please ask in a newsgroup
    dedicated to your compiler and/or platform. I suggest
    gnu.gcc.help for a start.


    Cheers
    Michael
     
    Michael Mair, Dec 28, 2004
    #2
    1. Advertisements

  3. Dave win

    Jack Klein Guest

    [snip off-topic assembly language]
    [snip]

    The compiler can verify that the values of 'a' and 'b' are never used.
    By the as-if rule, it can eliminate all of your main() function other
    than the return statement.
     
    Jack Klein, Dec 28, 2004
    #3
  4. Dave win

    Malcolm Guest

    Your problem is that you have given a trivial function to the compiler to
    optimise. Since you have put a and b in registers, it has decided to
    optimise very aggressively, which in this case means just calling main and
    returning. The assembly instructions left probably just set up the stack
    frame.

    If you are trying to write little functions to see what the compiler does,
    which is a totally legitimate and sensible thing to do though not strictly
    on-topic, the best thing to do is to make a real function, for instance by
    reading two integers from stdin and swapping them, then outputting the
    result.
     
    Malcolm, Dec 28, 2004
    #4
  5. Dave win

    Novitas Guest

    A couple of things:

    1. Either enclose the macro definition in parenthesis [i.e. -- ()'s]
    with comma seperation instead of semicolon seperation, or enclose the
    macro definition in the do{}while(0) construct suggested by another
    poster. Personally, I use parenthesis when I can so that the macro can
    lexically be used just like a function, but either approach will avoid
    non-obvious problems.

    2. If it is your objective to force the compiler to do things your way
    (i.e. swap using exclusive or) without incurring all of the bulk due to
    automatic variables, then try using the keyword 'volatile' instead of
    'register' and compiling the program with maximum optimization. In
    general there is no guarantee that a compiler will produce the results
    you desire however and no guarantee that it won't do a better job than
    what you desire either.
     
    Novitas, Dec 28, 2004
    #5
  6. What 'XOR instruction'? Are you implying that there supposed to be some
    kind of definitive correspondence between C language operators and
    machine commands, like '^' is supposed to translate into a 'xor'
    instruction? That would be nonsense. There is absolutely no definitive
    matching between the two. There's absolutely no reason to expect to see
    a 'xor' instruction in machine code that evaluates a C expression with
    '^' operator. In this case the compiler decided to evaluate your
    expressions without using 'xor' instruction. There's nothing wrong
    and/or unusual with this as long as the final result is correct.
     
    Andrey Tarasevich, Dec 28, 2004
    #6
  7. Dave win

    Malcolm Guest

    That's way too strong. The reason C has a xor operator, but not an
    exponentiation operator for example, is that xor is typically implemented as
    a machine instruction whilst pow() is not. So if I compiled source using the
    xor operator, and found that the resulting assembly does not contain a xor
    instruction, I would indeed be surprised. In this case the reason is that
    the function can be aggressively optimised to nothing, because there is no
    output. That is arguably not desirable behaviour from a compiler, though the
    standard does allow it. And of course xor might be implemented with a
    combination of ands and ors if some quirk of the platform made that more
    efficient, but one would not expect that situation to arise normally.
     
    Malcolm, Dec 28, 2004
    #7
  8. This not too strong in general case. Not at all. An optimizing compiler
    could be smart enough to realize that certain code does not really need
    an actual 'xor' and can be implemented more efficiently without it.

    For example, the same reasoning that you use above can be used to
    conclude that both multiplication and shift operators were also added to
    C language because they are typically matched by corresponding machine
    instructions. However, on many platforms the most efficient way to
    implement multiplication to a constant power-of-2 coefficient could be
    neither machine 'mul' operation nor machine shift operation. It could be
    some seemingly unrelated load-effective-address operation ('lea' of x86,
    for example) or something completely different. I won't be surprised to
    see that both expression 'foo *= 4' and expression 'bar <<= 2' got
    translated into identical something like

    lea eax, [eax*4]

    instead of "expected" applications of 'mul's and/or shifts.

    Something like this can easily happen to '^' as well. The compiler might
    decide that is some particular context a '^' operation can be safely and
    efficiently replaced with a non-equality check, for example.

    Assumption that there's some kind of 1:1 correspondence between C
    operations and machine instructions is not a good thing. It often
    results in unreadable code (because of heavy use of useless
    optimizations, like replacing multiplications with shifts). It often
    encourages users to make further ungrounded assumptions about the order
    of evaluation of C expressions, resulting in broken code.
     
    Andrey Tarasevich, Dec 29, 2004
    #8
  9. First, any operation can be eliminated if its result isn't used, which
    I think is what was happening with the OP's code.

    Leaving that aside, there are a lot of cases where a multiplication by
    a constant can be replaced by some cheaper operation such as a shift
    or an addition (assuming the compiler knows, or can guess, how
    expensive the operations are). But a multiplication of two variables
    (assuming the compiler can't derive their actual values) will probably
    show up as a multiplication operator in the generated code.
    That can happen if the compiler knows that both operands have the
    value 0 or 1 (but only if a non-equality check is cheaper than an xor
    instruction, which I expect it normally wouldn't be). Similarly, an
    xor operation might be eliminated if one of the operands is a
    constant, or can be evaluated at compilation time (but even then an
    xor instruction might still be the cheapest way to do the
    calculation), or if the result isn't used. But if the operands are
    variables whose values can't be computed at compilation time and the
    result is used, a "^" operation will probably appear as an xor
    instruction in the generated code. If an xor instruction isn't the
    cheapest way to perform an exclusive-or, there's no point in having it
    in the instruction set.

    Here's a simple example:

    #include <stdio.h>
    #include <stdlib.h>

    int main(int argc, char **argv)
    {
    int x, y;
    if (argc != 3) {
    exit(EXIT_FAILURE);
    }
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    printf("%d & %d = %d\n", x, y, x * y);
    printf("%d ^ %d = %d\n", x, y, x ^ y);
    return 0;
    }

    One interesting question is how many "*" and "^" operators in real
    code are best implemented by actual multiply and xor instructions, and
    how many can be reduced to something cheaper. My guess is that
    multiplication can be reduced more often that xor, but beyond that I
    don't know what the proportions are.
     
    Keith Thompson, Dec 29, 2004
    #9
  10. On Wed, 29 Dec 2004 09:28:02 +0000, Keith Thompson wrote:

    ....
    Consider this:

    #include <stdio.h>

    #define swap(a,b) ((a)=(a)^(b),(b)=(b)^(a),(a)=(a)^(b))

    void foo(int x, int y)
    {
    printf("%d %d\n", x, y);
    swap(x, y);
    printf("%d %d\n", x, y);
    }

    Which gcc was able to compile into:

    foo:
    subl $28, %esp
    movl %ebx, 20(%esp)
    movl 36(%esp), %ebx
    movl %esi, 24(%esp)
    movl 32(%esp), %esi
    movl %ebx, 8(%esp)
    movl $.LC0, (%esp)
    movl %esi, 4(%esp)
    xchgl %ebx, %esi
    call printf
    movl %ebx, 8(%esp)
    movl %esi, 4(%esp)
    movl $.LC0, (%esp)
    call printf
    movl 20(%esp), %ebx
    movl 24(%esp), %esi
    addl $28, %esp
    ret

    Note here that gcc was clever enough to recognise that IN THIS CASE the
    sequence of ^ operations amount to a swap operation so didn't have to
    generate any xor instructions. If it had been a little bit cleverer it
    could have eliminated the xchgl instruction too. Writing it as:

    #include <stdio.h>

    #define swap(a,b) do { int tmp_ = (a); (a) = (b); (b) = tmp_; } while (0)

    void bar(int x, int y)
    {
    printf("%d %d\n", x, y);
    swap(x, y);
    printf("%d %d\n", x, y);
    }

    produced:

    bar:
    subl $28, %esp
    movl %ebx, 20(%esp)
    movl 32(%esp), %ebx
    movl %esi, 24(%esp)
    movl 36(%esp), %esi
    movl %ebx, 4(%esp)
    movl $.LC0, (%esp)
    movl %esi, 8(%esp)
    call printf
    movl %ebx, 8(%esp)
    movl %esi, 4(%esp)
    movl $.LC0, (%esp)
    call printf
    movl 20(%esp), %ebx
    movl 24(%esp), %esi
    addl $28, %esp
    ret

    I.e. writing the simple, obvious swap code rather than something "clever"
    results here in more efficient code (it managed to eliminate the xchgl
    instruction). Note that there is no code here that corresponds to the
    assignments in the swap, it just picks the values from the right places.

    Lawrence
     
    Lawrence Kirby, Dec 29, 2004
    #10
  11. This is all great, but my point is, once again, that in general case one
    should not expect the compiler to unconditionally translate C operators
    into their "intuitive" counterparts in machine language (which is what
    the OP seems to do). There are several reasons why this might not be the
    case, regardless of whether the result of the expression is used in the
    program or not. One thing worth mentioning is that often the seemingly
    natural mapping between C operators and machine instructions is not
    really that straightforward when one starts to look closer and notices
    some little but important detail of C operator specification (like, for
    example, the requirement of integral division to operate in accordance
    "round towards zero" approach).
     
    Andrey Tarasevich, Dec 29, 2004
    #11
  12. I agree with your point. I just think you picked a poor example to
    demonstrate it.
     
    Keith Thompson, Dec 29, 2004
    #12
  13. Dave win

    Randy Howard Guest

    It's still broken in that it does not work properly in all cases.
    See the FAQ.
     
    Randy Howard, Dec 29, 2004
    #13
  14. Dave win

    Malcolm Guest

    I sort of agree as well. One of the strengths of C is that the programmer
    has a pretty good idea of what assembly will be generated, and thus an
    inutitive feel for how processor-intensive his function will be. However to
    extend this to assuming that "I have used a XOR therefore the instruction
    XOR must appear in the machine code" is dangerous. Most of the time you will
    be correct, but it might be that the instruction can be optimised away, as
    happened to the OP, or it might be that an alternative is chosen by the
    compiler for some obscure reason. So if the actual machine instructions are
    vital, you should program in actual assembler.
     
    Malcolm, Dec 30, 2004
    #14
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.