the "computed goto" problem

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

the "computed goto" problem

Renato Golin via cfe-dev
Hello cfe,

This year at CppCon (https://www.youtube.com/watch?v=9cPU1NdsgDQ), there was a funny talk about the use of what they called a "computed goto".
I was playing around with the idea, and there might be something incorrect about the code generated by clang when constexpr is involved (starting with 9.0).

The idea is this: the address of a bunch of labels are taken and stored into a table:

  enum bytecode : int8_t { add1, add2, halt };

  constexpr void* labels[] = {
    [bytecode::add1] = &&add1_label,
    [bytecode::add2] = &&add2_label,
    [bytecode::halt] = &&halt_label,
  };

  //labels defined here...

However, this is the IR generated with -O0 -emit-llvm:

  @labels = private unnamed_addr constant [3 x i8*] [i8* blockaddress(@"label1", <badref>), i8* blockaddress(@"label2", <badref>), i8* blockaddress(@"label3", <badref>)], align 16

Note the badrefs! Also, we generate a basic block with no predecessors:

  12: ; No predecessors!
  indirectbr i8* undef, [label <badref>, label <badref>, label <badref>]

As such, as soon as we start optimizing, the whole function is optimized away.
If we remove constexpr, however, everything seems sane. Godbolt link: https://godbolt.org/z/Anc9EI

Any insights on what might be happening here? I suspect a lot of people will play around with this construction just "for fun" and will encounter this.

--
Felipe

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: the "computed goto" problem

Renato Golin via cfe-dev
Definitely a bug.

Looks like a bug in the combination of block addresses, constexpr, and lambda functions. Note that the "labels" global value gets duplicated -- one for the function it's defined in, and then a copy for the inner lambda function. The copy for the lambda got the block references broken, by attempting to change the function the block is defined in, to the lambda. Obviously, those blocks don't actually exist within the lambda function, so that's busted!

@__const._Z22run_with_computed_gotoPK8bytecode.labels = private unnamed_addr constant [3 x i8*] [i8* blockaddress(@_Z22run_with_computed_gotoPK8bytecode, %9), i8* blockaddress(@_Z22run_with_computed_gotoPK8bytecode, %13), i8* blockaddress(@_Z22run_with_computed_gotoPK8bytecode, %17)], align 16
@__const._Z22run_with_computed_gotoPK8bytecode.labels.1 = private unnamed_addr constant [3 x i8*] [i8* blockaddress(@"_ZZ22run_with_computed_gotoPK8bytecodeENK3$_0clEv", <badref>), i8* blockaddress(@"_ZZ22run_with_computed_gotoPK8bytecodeENK3$_0clEv", <badref>), i8* blockaddress(@"_ZZ22run_with_computed_gotoPK8bytecodeENK3$_0clEv", <badref>)], align 16

If you want a workaround, I suggest not using the lambda. Changing it to e.g.
  #define next() labels[*instructions++]
should be fine.

On Thu, Oct 3, 2019 at 8:48 AM De Azevedo Piovezan, Felipe via cfe-dev <[hidden email]> wrote:
Hello cfe,

This year at CppCon (https://www.youtube.com/watch?v=9cPU1NdsgDQ), there was a funny talk about the use of what they called a "computed goto".
I was playing around with the idea, and there might be something incorrect about the code generated by clang when constexpr is involved (starting with 9.0).

The idea is this: the address of a bunch of labels are taken and stored into a table:

  enum bytecode : int8_t { add1, add2, halt };

  constexpr void* labels[] = {
    [bytecode::add1] = &&add1_label,
    [bytecode::add2] = &&add2_label,
    [bytecode::halt] = &&halt_label,
  };

  //labels defined here...

However, this is the IR generated with -O0 -emit-llvm:

  @labels = private unnamed_addr constant [3 x i8*] [i8* blockaddress(@"label1", <badref>), i8* blockaddress(@"label2", <badref>), i8* blockaddress(@"label3", <badref>)], align 16

Note the badrefs! Also, we generate a basic block with no predecessors:

  12: ; No predecessors!
  indirectbr i8* undef, [label <badref>, label <badref>, label <badref>]

As such, as soon as we start optimizing, the whole function is optimized away.
If we remove constexpr, however, everything seems sane. Godbolt link: https://godbolt.org/z/Anc9EI

Any insights on what might be happening here? I suspect a lot of people will play around with this construction just "for fun" and will encounter this.

--
Felipe

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: the "computed goto" problem

Renato Golin via cfe-dev

Thanks for the input!

 

I’ve filed https://bugs.llvm.org/show_bug.cgi?id=43546

There are other computed goto reported bugs, but they don’t seem related to this.

 

From: James Y Knight <[hidden email]>
Sent: Thursday, October 3, 2019 10:01 AM
To: De Azevedo Piovezan, Felipe <[hidden email]>
Cc: [hidden email]
Subject: Re: [cfe-dev] the "computed goto" problem

 

Definitely a bug.

 

Looks like a bug in the combination of block addresses, constexpr, and lambda functions. Note that the "labels" global value gets duplicated -- one for the function it's defined in, and then a copy for the inner lambda function. The copy for the lambda got the block references broken, by attempting to change the function the block is defined in, to the lambda. Obviously, those blocks don't actually exist within the lambda function, so that's busted!

 

@__const._Z22run_with_computed_gotoPK8bytecode.labels = private unnamed_addr constant [3 x i8*] [i8* blockaddress(@_Z22run_with_computed_gotoPK8bytecode, %9), i8* blockaddress(@_Z22run_with_computed_gotoPK8bytecode, %13), i8* blockaddress(@_Z22run_with_computed_gotoPK8bytecode, %17)], align 16

@__const._Z22run_with_computed_gotoPK8bytecode.labels.1 = private unnamed_addr constant [3 x i8*] [i8* blockaddress(@"_ZZ22run_with_computed_gotoPK8bytecodeENK3$_0clEv", <badref>), i8* blockaddress(@"_ZZ22run_with_computed_gotoPK8bytecodeENK3$_0clEv", <badref>), i8* blockaddress(@"_ZZ22run_with_computed_gotoPK8bytecodeENK3$_0clEv", <badref>)], align 16

 

If you want a workaround, I suggest not using the lambda. Changing it to e.g.

  #define next() labels[*instructions++]

should be fine.

 

On Thu, Oct 3, 2019 at 8:48 AM De Azevedo Piovezan, Felipe via cfe-dev <[hidden email]> wrote:

Hello cfe,

This year at CppCon (https://www.youtube.com/watch?v=9cPU1NdsgDQ), there was a funny talk about the use of what they called a "computed goto".
I was playing around with the idea, and there might be something incorrect about the code generated by clang when constexpr is involved (starting with 9.0).

The idea is this: the address of a bunch of labels are taken and stored into a table:

  enum bytecode : int8_t { add1, add2, halt };

  constexpr void* labels[] = {
    [bytecode::add1] = &&add1_label,
    [bytecode::add2] = &&add2_label,
    [bytecode::halt] = &&halt_label,
  };

  //labels defined here...

However, this is the IR generated with -O0 -emit-llvm:

  @labels = private unnamed_addr constant [3 x i8*] [i8* blockaddress(@"label1", <badref>), i8* blockaddress(@"label2", <badref>), i8* blockaddress(@"label3", <badref>)], align 16

Note the badrefs! Also, we generate a basic block with no predecessors:

  12: ; No predecessors!
  indirectbr i8* undef, [label <badref>, label <badref>, label <badref>]

As such, as soon as we start optimizing, the whole function is optimized away.
If we remove constexpr, however, everything seems sane. Godbolt link: https://godbolt.org/z/Anc9EI

Any insights on what might be happening here? I suspect a lot of people will play around with this construction just "for fun" and will encounter this.

--
Felipe

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev