Why does not GCC generate correct assembly code for int division?

Question

I have written the following C code. But in runtime it gave me incorrect values for the variable sb, so i tried to debug it with GDB and i found out that the assembly code for the int division E(vdes->addr, bs) (#define E(X,Y) X/Y) was completely incomprehensible and seems to be not doing the right thing.

File: main.c

typedef struct virtual_file_descriptor
{
    int     dfb;
    int     addr;

} vfd;

vfd vdes;

if(!strcmp(argv[1], "write")){
        vdes.dfb = atoi(argv[2]);
        vdes.addr = atoi(argv[3]);
        vwrite(&vdes, inbuffer, atoi(argv[4]));
    }

File: vwrite.c

#define E(X,Y)  X/Y
#define bs      sizeof(D_Record)*MAX_BLOCK_ENTRIES

int vwrite(vfd *vdes, char *buffer, int size){
    if(!vdes)
        return -1;

    int sb, nb, offset;

    sb      = E(vdes->addr, bs) + 1;     // i did 140/280 => wrong result
    offset  = vdes->addr - (sb - 1) * bs;

    printf("size=%d bs=%d   addr=%d sb=%d   offset=%d\n\n", size, bs, vdes->addr, sb, offset);

}

The assembly language generated for the int devision was (Which is wrong and doesn't contain any sings of doing an arithmetic division) :

(gdb) n
58      sb      = E(vdes->addr, bs) + 1;
(gdb) x/10i $pc
=> 0x80001c3d <vwrite+39>:  mov    0x8(%ebp),%eax
   0x80001c40 <vwrite+42>:  mov    0x4(%eax),%eax
   0x80001c43 <vwrite+45>:  shr    $0x2,%eax
   0x80001c46 <vwrite+48>:  mov    $0x24924925,%edx
   0x80001c4b <vwrite+53>:  mul    %edx
   0x80001c4d <vwrite+55>:  mov    %edx,%eax
   0x80001c4f <vwrite+57>:  shl    $0x2,%eax
   0x80001c52 <vwrite+60>:  add    %edx,%eax
   0x80001c54 <vwrite+62>:  add    %eax,%eax
   0x80001c56 <vwrite+64>:  add    $0x1,%eax
   0x80001c59 <vwrite+67>:  mov    %eax,-0x2c(%ebp)
   0x80001c5c <vwrite+70>:  mov    0x8(%ebp),%eax
   0x80001c5f <vwrite+73>:  mov    0x4(%eax),%eax
   0x80001c62 <vwrite+76>:  mov    %eax,%edx

I copied the same code sequence to a new standalone file and everything works fine (Correct results and correct assembly code). So i came to wonder why doesn't the first code work ?

File: test.c

#define E(X,Y) X/Y

int main(int argc, char **argv){

    int sb = E(atoi(argv[1]), atoi(argv[2]));

    return 0;
}

Assembly code generated for previous code (which is a nicely understandable and correct code for doing int devision):

   .
   .
   call atoi
   .
   call atoi
   .
   .
   0x800005db <main+75>:    mov    %eax,%ecx
   0x800005dd <main+77>:    mov    %edi,%eax
   0x800005df <main+79>:    cltd   
   0x800005e0 <main+80>:    idiv   %ecx
   0x800005e2 <main+82>:    mov    %eax,-0x1c(%ebp)

It doesn't look that unusual to me, but of course hard to check without trying it. Do you have some test cases? — harold, Jun 29 '17 at 23:11
I strongly suspect that the GDB disassembled code you've shown was not created by the exact same source code you've shown in the first example. You're probably debugging some old version of your program by mistake. This is why you need to provide an [mcve]. Make sure to include all the options you're using the compile the MCVE that reproduces the problem along with the version of GCC you're using. — Ross Ridge, Jun 29 '17 at 23:32
If you had written `#define bs 28 * 10`, this is the code I would expect. — harold, Jun 29 '17 at 23:36
@RossRidge Well i've found where was the problem. In the matter of fact i didn't define bs as 280 but as `#define bs sizeof(D_Record)*MAX_BLOCK_ENTRIES` . The reason i did that because i thought that was always a constant value but it seems like things happen when making such a definition. So what was the problem with that ? — Karim Manaouil, Jun 29 '17 at 23:53
Always use extensive parentheses in macros, i.e. `#define E(X,Y) X/Y` => `#define E(X,Y) ((X)/(Y))` ... as you can be never sure, what text the programmer will later use in the macro parameters for expansions. Overall if this would be C++11 source, I would suggest to avoid macros completely and use `constexpr`, but as this is C, it's your fight (still consider using functions instead of macros). And use longer macro names, to avoid accidental ambiguities ... also for arguments. (We did once search 3 hours for a bug which was due to macro defined with a,b, but using x,y (available in code :/)) — Ped7g, Jun 30 '17 at 00:30
every C book should already mention [the need for parentheses in macros](https://stackoverflow.com/q/10820340/995714), and [every modern compilers will optimize out divisions by constants anyway](https://stackoverflow.com/q/41183935/995714) — phuclv, Jun 30 '17 at 02:15
@CodyGray That was a marginal sub-topic answer for this question. The main answer is totally different and was about expression definition. — Karim Manaouil, Jun 30 '17 at 10:38
So you're saying I should have voted to close it as a typo instead? I guess that makes sense, but I thought the duplicate would be more helpful. — Cody Gray - on strike, Jun 30 '17 at 10:43
@LưuVĩnhPhúc: Nice, thanks for finding a good link for the macro-parens issue. I'm loving that SO allows editing the list of duplicate questions now, so I can close this as a duplicate of both those questions (since that's exactly what it is: macro problem creating wrong answers, leading to "mysterious" asm when trying to sort it out while debugging). — Peter Cordes, Jul 02 '17 at 09:16

zneak · Answer 1 · 2017-06-30T00:37:30.437

10

Just because you don't see an idiv instruction or that you can't understand the code at first glance doesn't mean that it's incorrect. Compilers optimize divisions by constants by multiplying by a large factor and then dividing by a power of two.

With additional info in the comments, we know that bs used to be defined as sizeof(D_Record)*MAX_BLOCK_ENTRIES. The bug is that the E(vdes->addr, bs) macro expands to vfs->address / sizeof(D_Record) * MAX_BLOCK_ENTRIES, which is equivalent to (vfs->address / sizeof(D_Record)) * MAX_BLOCK_ENTRIES. The solution is to add parentheses in E's definition to group correctly:

#define E(X, Y) ((X)/(Y))

This also adds parentheses around the whole expression to be safe, since you could otherwise run into a similar problem doing foo * E(bar, baz).

In addition, before jumping to disassembly, I'd recommend looking at the preprocessed source, which can be done using cpp or gcc -E (or clang -E).

edited Jun 30 '17 at 00:37

answered Jun 29 '17 at 23:24

zneak

134,922
42
253
328

I'm ok with that. I'm not willing to understand that code. But it is giving me incorrect values, now that's a problem ! – Karim Manaouil Jun 29 '17 at 23:26
2

At least show inputs and outputs, expected and actual. – Jester Jun 29 '17 at 23:28
@afr0ck, [here's your code](http://ideone.com/BiYGNR) with `addr=140` giving exactly the results that I'd expect (sb=1). Do you expect something else? – zneak Jun 29 '17 at 23:30
@zneak i defined bs as `#define bs sizeof(D_Record)*MAX_BLOCK_ENTRIES` in the original program. I thought that was a constant and will have no effect if i changed it to a numerical value. Once i did, everything works fine. – Karim Manaouil Jun 29 '17 at 23:56
@afr0ck, in that case the problem is that your macro expands to `vfs->address/sizeof(D_Record)*MAX_BLOCK_ENTRIES`. Division and multiplication being left-associative, that's the equivalent of `(vfs->address / sizeof(D_Record)) * MAX_BLOCK_ENTRIES`. Add parentheses to `E`: `#define E(X, Y) (X)/(Y)` – zneak Jun 29 '17 at 23:57
I didn't expect such a behavior from the preprocessor. But why does it have to do that ? why not `vfs->address/(sizeof(D_Record)*MAX_BLOCK_ENTRIES)` ? – Karim Manaouil Jun 30 '17 at 00:02
2

@afr0ck, it's not the preprocessor's fault. The preprocessor is not aware of any syntactical meaning. It's perfectly legal to write a macro like `#define E(X) X /` that you'd use like `E(4) 2`. – zneak Jun 30 '17 at 00:05
The answer has perfectly solved the problem. @zneak – Karim Manaouil Jun 30 '17 at 00:10
2

@zneak - the define for bs should also be enclosed by parenthesis, in case it's ever used in another expression: `#define bs (sizeof(D_Record)*MAX_BLOCK_ENTRIES)` . – rcgldr Jun 30 '17 at 00:18
1

I would suggest to enclose the whole result of E in parentheses also, i.e. `#define E(X, Y) ((X)/(Y))` ... I know there's brutal shortage of parentheses since LISP, but common, you can add two more for any macro... – Ped7g Jun 30 '17 at 00:36

rcgldr · Accepted Answer · 2017-06-30T01:39:10.880

The original question had

#define bs      280

It was later changed to:

#define bs      sizeof(D_Record)*MAX_BLOCK_ENTRIES

To avoid issues using bs in other expressions, this should be

#define bs      (sizeof(D_Record)*MAX_BLOCK_ENTRIES)

The define for E should be:

#define E(X,Y) ((X)/(Y))

The generated assembly code appears to be based on

#define bs      sizeof(D_Record)*MAX_BLOCK_ENTRIES
#define E(X,Y) X/Y
    ... E(vdes->addr, bs) ...

So divide by 28 using shift and multiply, then multiply by 10.

        mov    0x4(%eax),%eax       ;eax = dividend
        shr    $0x2,%eax            ;eax = dividend/4 (pre shift)
        mov    $0x24924925,%edx     ;edx = multiply constant
        mul    %edx                 ;edx = dividend/28 (no post shift)
        mov    %edx,%eax            ;eax = (dividend/28)*10
        shl    $0x2,%eax
        add    %edx,%eax
        add    %eax,%eax

For the eax = edx*10 sequence, I'm not sure why lea wasn't used:

        lea    (%edx,%edx,2),eax    ;eax = edx*5
        add    %eax,%eax            ;eax = edx*10

Link to prior thread with an explanation how divide by constant is converted into multiply and shifts.

Why does GCC use multiplication by a strange number in implementing integer division?

Actually, does that even divide by 280? Looks like 28 to me. Followed by a mysterious multiplication by 10.. — harold, Jun 29 '17 at 23:21
@harold - It is a divide by 28 followed by a multiply by 10. The original question changed the definition of `bs` from `280` to `sizeof(D_Record)*MAX_BLOCK_ENTRIES` . — rcgldr, Jun 30 '17 at 00:23

Why does not GCC generate correct assembly code for int division?

2 Answers2