[Bug tree-optimization/51840] New: asm goto incorrect code generation at -O2 and -O3

[Bug tree-optimization/51840] New: asm goto incorrect code generation at -O2 and -O3

[adam at consulting dot net.nz]

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

             Bug #: 51840
           Summary: asm goto incorrect code generation at -O2 and -O3
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: adam@consulting.net.nz


Created attachment 26310
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26310
asm goto incorrect code generation at -O2 and -O3

Attached is the simplest test case causing incorrect code generation I've been
able to craft. I've added comments, expanded out macros by hand, eliminated
many dispatch destinations and built a define switch so you can compare the
code to computed goto by commenting out the #define ASM_GOTO statement.

I original tested asm goto as a replacement for computed goto since GCC doesn't
generate complex jmp instructions [jmp [m] is superior to mov [m]->r; jmp r.
The complex jmp is an overall shorter instruction sequence and if correctly
predicted may have an overall latency of zero].

asm goto requires a list of destination labels. By only listing possible
destinations of each dispatch GCC has an opportunity to generate better code. I
think I have uncovered a bug exercising this increased optimization potential.

Here's the problem (with gcc 4.5, 4.6 or snapshot; the printed destination
addresses may differ):

$ gcc -Wall -O0 -std=gnu99 exec_code.c && ./a.out 
atop__a_dec:         0x400648
atop__a_non_zero_p:  0x40068c
atop__exit:          0x400735
atop_f__jmp_if_true: 0x4006cc
atop_t__jmp_if_true: 0x4006f2
fixme:               0x400742
atop = 10
atop = 9
atop = 8
atop = 7
atop = 6
atop = 5
atop = 4
atop = 3
atop = 2
atop = 1

$ gcc -Wall -O1 -std=gnu99 exec_code.c && ./a.out 
atop__a_dec:         0x400634
atop__a_non_zero_p:  0x40066b
atop__exit:          0x4006ad
atop_f__jmp_if_true: 0x400688
atop_t__jmp_if_true: 0x400698
fixme:               0x4006ca
atop = 10
atop = 9
atop = 8
atop = 7
atop = 6
atop = 5
atop = 4
atop = 3
atop = 2
atop = 1

$ gcc -Wall -O2 -std=gnu99 exec_code.c && ./a.out 
atop__a_dec:         0x400657
atop__a_non_zero_p:  0x4006ea
atop__exit:          0x400678
atop_f__jmp_if_true: 0x400710
atop_t__jmp_if_true: 0x4006f8
fixme:               0x400660
Dispatch logic ERROR

$ gcc -Wall -O3 -std=gnu99 exec_code.c && ./a.out 
atop__a_dec:         0x400657
atop__a_non_zero_p:  0x4006ea
atop__exit:          0x400678
atop_f__jmp_if_true: 0x4006bc
atop_t__jmp_if_true: 0x400700
fixme:               0x400660
Dispatch logic ERROR


I am surprised that -Os correctly counts down:

$ gcc -Wall -Os -std=gnu99 exec_code.c && ./a.out 
atop__a_dec:         0x400636
atop__a_non_zero_p:  0x40065f
atop__exit:          0x40069b
atop_f__jmp_if_true: 0x40067b
atop_t__jmp_if_true: 0x400686
fixme:               0x4006a7
atop = 10
atop = 9
atop = 8
atop = 7
atop = 6
atop = 5
atop = 4
atop = 3
atop = 2
atop = 1


This may narrow the bug down to one of the optimisations performed at -O2,-O3
that is not performed at -Os.


Any level of optimization is OK when #define ASM_GOTO is commented out:

$ gcc -Wall -O3 -std=gnu99 exec_code.c && ./a.out 
atop__a_dec:         0x400660
atop__a_non_zero_p:  0x400690
atop__exit:          0x4006e0
atop_f__jmp_if_true: 0x4006b0
atop_t__jmp_if_true: 0x4006c8
fixme:               0x400700
atop = 10
atop = 9
atop = 8
atop = 7
atop = 6
atop = 5
atop = 4
atop = 3
atop = 2
atop = 1

[Bug tree-optimization/51840] asm goto incorrect code generation at -O2 and -O3

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-01-13 00:53:17 UTC ---
I think the problem here is the label references are being moved which is
correct as GCC thinks the labels where the address was taken is not going to
happen.  I don't think you can use asm goto like this.  If you want a smaller
indirect goto, then file a bug against GCC instead of working around it.

[Bug tree-optimization/51840] asm goto incorrect code generation at -O2 and -O3

[adam at consulting dot net.nz]

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

--- Comment #2 from Adam Warner <adam at consulting dot net.nz> 2012-01-13 02:08:34 UTC ---
(In reply to comment #1)
> I think the problem here is the label references are being moved which is
> correct as GCC thinks the labels where the address was taken is not going to
> happen.  I don't think you can use asm goto like this.  If you want a smaller
> indirect goto, then file a bug against GCC instead of working around it.

Bug 46219. "Generate indirect jump instruction on x86-64". Reported 2010-10-28.

If I replace the initial dispatch with a computed goto statement (leaving all
the other asm gotos alone) the code does compile correctly. It's slightly
faster but that's probably due to the asm indirect goto instructions.

There are further potential optimisation benefits in being able to specify only
the destinations of a dispatch. asm goto provides this information to the
compiler. With computed goto every dispatch is assumed to jump to every
&&label.

I've just realised this is the kind of asm goto I'm looking for:

asm goto ("jmp *%0" : : "m" (vm_dispatch[S_atop][next_inst])
 : : &&atop__a_dec, &&atop__a_non_zero_p, &&atop__exit, &&fixme);
__builtin_unreachable();

Could this bug report become a feature request for being able to specify label
addresses using labels as values "&&" syntax in asm goto statements?

[Bug c/51840] asm goto enhancement request

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |c
            Summary|asm goto incorrect code     |asm goto enhancement
                   |generation at -O2 and -O3   |request
           Severity|normal                      |enhancement

[Bug c/51840] asm goto enhancement request

[timo.kreuzer at reactos dot org]

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

Timo Kreuzer <timo.kreuzer at reactos dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |timo.kreuzer at reactos dot
                   |                            |org

--- Comment #3 from Timo Kreuzer <timo.kreuzer at reactos dot org> 2012-09-05 21:39:56 UTC ---
I support this enhancement request with additional explanation.

The documentation for asm goto in the online docs for gcc 4.7.1 contain an
example using a jump table. This is done by creating the jump table inside the
asm statement, using ".pushsection" and ".popsection" directives to move the
actual jump table data into a dedicated section.

This does not work on x86 PE targets.

2 possible workarounds come to mind:
a) Using explicit sections, like ".section bla; ... ;.section .text;"
But this has limitations, since you cannot use it in a function that will go to
a different section than the .text section, something pretty common for driver
code, where initialization code is put in ".INIT" and pageable code is put in
".PAGE". For my usage scenario (exception handling for reactos) this approach
will not work.

b) Use C-style jump tables. "static void *jmp_table[] = {&&label1, &&label2};"
This has also the advantage that it integrates better with the rest of the C
code and allows to reuse the jump tables in C code.

Sadly solution b) is broken.

Here's an example:

int
example1(int param)
{
    int value = 0;

    if (param > 2)
        asm goto ("movl %0, %%ecx\n\tjmp %l[label1]\n" : : "i"(&&label1) :
"ecx" : label1);

    value = 1;

    if (param > 1)
        asm goto ("movl %0, %%ecx\n\tjmp %l[label1]\n" : : "i"(&&label1) :
"ecx" : label1);

    value = 2;

label1:
    return value;
}


The compiler output looks like this (cleaned up):

_example1:
    movl    4(%esp), %edx
    cmpl    $2, %edx
    jle    L2
    movl $L3, %ecx
    jmp L4
L2:
    movl    $2, %eax
    cmpl    $1, %edx
    jle    L3
    movl $L3, %ecx
    jmp L6
    ret
L4:
    movl    $0, %eax
    ret
L6:
    movl    $1, %eax
L3:
    rep
    ret


The 2 jmp instructions jump to L4 and L6, while both mov instructions point
to L3. A jump from the asm goto to L3 would result in broken behaviour.

Using asm goto with C style jump tables causes the compiler to generate code
pathes that are incompatible with a jump to the static address of the label, as
stored in the jump table.

When a simple goto can correctly jump to addresses in static tables, then asm
goto should be able to do that as well.
There should also not be a big performance penalty for that, since the compiler
can simple move whatever is now put in the individual pathes to the place
before the asm goto is emitted.

[Bug c/51840] asm goto enhancement request

[timo.kreuzer at reactos dot org]

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

--- Comment #4 from Timo Kreuzer <timo.kreuzer at reactos dot org> 2012-09-15 12:16:38 UTC ---
Update: I fought a bit with GCC and made clear that my Kung Fu is better than
GCC's ;-)

I solved this issue with a workaround. I forced a number of constraints upon
GCC, that made it cry and stop shuffling the code around. These constraints
will make certain optimizations by moving code around useless, so assuming that
gcc will do the right thing, it won't move code onto pathes between the asm
goto and the actual label address.

So here's my code:

int
example1(int param)
{
    int value = 0;

    if (param > 2)
    {
label1:
        asm goto ("movl %0, %%ecx\n\tjmp %l[label3]\n" : : "i"(&&label3) :
"ecx" : label3, labelx);
    }

    value = 1;

    if (param > 1)
    {
label2:
        asm goto ("movl %0, %%ecx\n\tjmp %l[label3]\n" : : "i"(&&label3) :
"ecx" : label3, labelx);
    }

    value = 2;

label3:
    return value;

labelx:(void)0;
    void *plabel;
    asm volatile ("#" : "=a"(plabel) : "p"(&&label1), "p"(&&label2),
"p"(&&label3), "p"(&&labelx) : "memory");
    goto *plabel;
}

Almost the same as before, with exception to the additional labelx construct.
First the asm instruction makes GCC think the addresses of all the labels might
be used here and after it we have plabel being eax containing something that
GCC doesn't know anything about.
The goto basically tells GCC that there are pathes between these labels.
GCC won't insert any "lazy" evaluation of constants into a codepath between
label1 and the static label3 address, because due to the additional asm goto
reference to labelx, it would need to add this code in the path between label1
and labelx as well. But since there is a virtual goto from labelx back to
label1, it would put the code into the inner of a loop, which it will try to
avoid.

Anyway this is a huge hack and works rather on the principle of good faith,
than on hard specifications.

Maybe someone finds an approach that is proovable to result in the right thing.
Or some gcc dev does the right thing and fixes asm goto.

[Bug c/51840] asm goto enhancement request

[ktietz at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51840

Kai Tietz <ktietz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-06-18
                 CC|                            |ktietz at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #5 from Kai Tietz <ktietz at gcc dot gnu.org> ---
So original issue is caused by two issues.

For initial expand we produce the following rtl for the first code-switch:

(jump_insn 32 31 34 2 (parallel [
            (asm_operands/v ("jmp *%0") ("") 0 [
                    (mem/v/f/j:DI (plus:DI (mult:DI (reg:DI 136)
                                (const_int 8 [0x8]))
                            (reg/f:DI 135)) [0 vm_dispatch S8 A64])
                ]
                 [
                    (asm_input:DI ("m") t_asmgoto.c:65)
                ]
                 [
                    (label_ref:DI 36)
                    (label_ref:DI 56)
                    (label_ref:DI 114)
                    (label_ref:DI 120)
                ] t_asmgoto.c:65)
            (clobber (reg:QI 18 fpsr))
            (clobber (reg:QI 17 flags))
            (clobber (mem:BLK (scratch) [0  A8]))
        ]) t_asmgoto.c:65 -1
     (insn_list:REG_LABEL_TARGET 36 (insn_list:REG_LABEL_TARGET 56
(insn_list:REG_LABEL_TARGET 114 (nil))))
 -> 120)
(note 34 32 33 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(note/s 33 34 35 4 ("atop__a_dec") NOTE_INSN_DELETED_LABEL 2)
(barrier 35 33 36)
(code_label 36 35 37 5 8 "" [3 uses])
...

Of interest is here the '(note/s 33 34 35 4 ("atop__a_dec")
NOTE_INSN_DELETED_LABEL 2)'.  As long as code_label 36 (which is implementation
of "atop__a_dec" code) follows directly that note, we are fine.
That's true for -Os, -O0, and -O1.  For -O2 we exectute additional the
basic-block-reorder pass, and that moves label 36 away.  Nevertheless the
semi-deleted label-note remains and cause the wrong code-path.

[Bug c/51840] asm goto enhancement request

[ktietz at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51840

--- Comment #6 from Kai Tietz <ktietz at gcc dot gnu.org> ---
So this is a source of endless bugs ... and all are related to merging of
basic-blocks.

By the following patch the sample can be built successful on x64 targets. 
There seems to be another issue for x86 targets triggered in some cases.  For
32-bit the factoring out of partial addresses to register leads to new
basic-blocks placed before blocks actually jumped by table. Major issue happens
in mergephi pass.

For all of those problems is common that we happily operate on forced
user-labels.

Index: tree-cfgcleanup.c
===================================================================
--- tree-cfgcleanup.c   (Revision 212070)
+++ tree-cfgcleanup.c   (Arbeitskopie)
@@ -285,12 +285,19 @@ tree_forwarder_block_p (basic_block bb, bool phi_w
   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
     {
       gimple stmt = gsi_stmt (gsi);
+      tree lbl;

       switch (gimple_code (stmt))
        {
        case GIMPLE_LABEL:
-         if (DECL_NONLOCAL (gimple_label_label (stmt)))
+         lbl = gimple_label_label (stmt);
+         if (DECL_NONLOCAL (lbl))
            return false;
+         /* If PHI_WANTED is true, we can't operate on user-labels.
+            See PR 51840.  */
+         if (phi_wanted
+             && !DECL_ARTIFICIAL (lbl) && FORCED_LABEL (lbl))
+           return false;
          if (optimize == 0 && gimple_location (stmt) != locus)
            return false;
          break;

[Bug c/51840] asm goto enhancement request

[rth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51840

Richard Henderson <rth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rth at gcc dot gnu.org

--- Comment #7 from Richard Henderson <rth at gcc dot gnu.org> ---
(In reply to Kai Tietz from comment #6)
> +         lbl = gimple_label_label (stmt);
> +         if (DECL_NONLOCAL (lbl))
>             return false;
> +         /* If PHI_WANTED is true, we can't operate on user-labels.
> +            See PR 51840.  */
> +         if (phi_wanted
> +             && !DECL_ARTIFICIAL (lbl) && FORCED_LABEL (lbl))
> +           return false;

Why the check for PHI_WANTED?  I must say the comment is less than
enlightening.  Is there any drawback to just

  if (DECL_NONLOCAL (lbl) || FORCED_LABEL (lbl))

?

[Bug c/51840] asm goto enhancement request

[ktietz at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51840

--- Comment #8 from Kai Tietz <ktietz at gcc dot gnu.org> ---
(In reply to Richard Henderson from comment #7)
> Why the check for PHI_WANTED?  I must say the comment is less than
> enlightening.  Is there any drawback to just
> 
>   if (DECL_NONLOCAL (lbl) || FORCED_LABEL (lbl))
> 
> ?

I tested at beginning condition '!DECL_ARTIFICIAL (lbl) && FORCED_LABEL (lbl)',
and it bootstrapped fine.  To use here just FORCED_LABEL would cause additional
regressions due all labels in gimple have set this flsg if they their address
is used (see gimpilify.c comments about setting this flag).  The issue happens
here only for the none-artificial labels marked as forced.
  If we don't check here for PHI_WANTED, then we get a regression in
tree-ssa/pr18134.c.  Well, if we are conservative, we have to avoid
modification of user-labels, nevertheless we would cause weak user-code by
allowing PHI_WANTED code-path too in mergephi pass.

[Bug c/51840] asm goto enhancement request

[rth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51840

--- Comment #9 from Richard Henderson <rth at gcc dot gnu.org> ---
Created attachment 33105
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=33105&action=edit
corrected test case

I believe that the original test case is in fact invalid.

Every asm goto has N labels attached, and the optimizers are properly 
adjusting them when we make changes to the CFG.  The fact that the
test doesn't make use of the changed labels is what makes it invalid.

If we fix the test case like so, it does work properly.

[Bug c/51840] asm goto enhancement request

[rth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51840

Richard Henderson <rth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |INVALID

--- Comment #10 from Richard Henderson <rth at gcc dot gnu.org> ---
See comment #9.

[Bug c/51840] asm goto enhancement request

[adam at consulting dot net.nz]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51840

--- Comment #11 from Adam Warner <adam at consulting dot net.nz> ---
Thank you for the fixed example! Just for the record only toy VM examples can
be implemented using this technique.

GCC documentation used to say that that the extended asm 30 operand limit might
be lifted in a future version of GCC. This sentence seems to have been deleted.
The full statement now reads: "The total number of input + output + goto
operands has a limit of 30."

The Java Virtual Machine, for example, contains almost 200 bytecode
instructions. To use this technique to jump to each instruction the list of asm
goto labels would number around 200. But the GCC limit is less than 30 (since
one must also subtract input operands from the limit). It's a blemish on GCC's
compiler architecture and a gross violation of the zero-one-infinity rule.

BTW if the example is modified by adding 25+ additional dummy goto labels there
is an Internal Compiler Error in extract_insn, at recog.c:2175 [gcc (Debian
4.9.0-7) 4.9.0]