7 ms·

That's not what a bit field is. A bit field (in C/C++) is a weird object type that can only exist in a structure or union type, which kind of acts like an unde

That's not what a bit field is. A bit field (in C/C++) is a weird object type that can only exist in a structure or union type, which kind of acts like an underlying regular integral type except for those situations where it does not. For an example of why compilers might have issues compiling bit fields properly (although this requires C++, since C's ternary operator works on rvalues, not lvalues): struct A { int x: 3; int y: 5 } a; (choice ? a.x : a.y) = val; Enjoy making that codegen work properly.

mwint 5y ago
Can someone explain further why this is so hard? I’m not familiar enough with any of this to understand without some help.
- ncmncm 5y ago
  It is just very finicky, with myriad edge cases easy to get wrong, and even easier to neglect to have complete tests for. Each target CPU design and version has quirks. Many involve sign extension.
  - jstimpfle 5y ago
    Extracting a subrange of bits and shifting them to the beginning is not exactly rocket science.
    - ncmncm 5y ago
      Experience indicates otherwise. If you must use bit fields, make them unsigned. Bugs love to hide under signed bit fields.
      - jstimpfle 5y ago
        That makes sense, looking at how signed arithmetic works on different architectures it would feel strange to use signed bitfields. Unsigned bitfields are a nice way to get modular arithmetic with n bits without syntactic clutter.
        ncmncm 5y ago
        "Unsigned bitfields are a nice ..." Appear to be. Are, when all the stars align. Are not in fact, often enough that you are issued a red warning you may ignore if you are insulated from all consequences.
- jcranmer 5y ago
  There's a few layers of complexity here. The first is lvalues. In compiler jargon, an lvalue is a kind of object that can have a value stored to it. And you can usually represent it as the address of some memory location [1]. Of course, bitfields break this representation: you need to know what the bit offset and bit size of the field you're storing is (as well as the signedness). The next level of complexity is the conditional operator. This means that, when conditional operators yield lvalues [2], you now end up in a situation where the lvalue now has a conditional bit offset and bit size within the address. Or maybe one leg of the expression returns a bit-field and the other leg returns a regular int lvalue. Imagine how complex your datastructure needs to be to represent an lvalue during this code generation phase. [1] Not all lvalues need to have memory locations. But if you're writing a C compiler, it's an easy first approximation to give every variable, even those marked register, some memory location and rely on an optimization pass to convert stack memory locations into register locations, rather than keeping track of this information when the frontend does code generation. [2] As mentioned elsewhere, conditional operators in C do not yield lvalues. But conditional operators in C++ do.
chrisseaton 5y ago
Is that valid C code? Is a ternary on an L-value an L-value? I'm not sure it is - regardless of bitfields or not? https://godbolt.org/z/aP8v5xKaz https://godbolt.org/z/aP8v5xKaz
- jcranmer 5y ago
  I mentioned in the note that it's not legal C, since ternaries must yield rvalues in C. It is legal C++, however, since there ternaries may be lvalues.
  - chrisseaton 5y ago
    I feel like you added that after I replied.
iainmerrick 5y ago
But, you’d have an even harder time making that work with mask-and-shift macros! It also doesn’t seem like something that would come up very often. I can’t think of the last time I conditionally stored to one of two struct fields, if I ever have. The much more normal case would be: val = choice ? a.x : a.y; That one seems pretty straightforward from a codegen perspective.
- ncmncm 5y ago
  "Seems" is not the domain under discussion.
- jcranmer 5y ago
  The example I gave is an example of something legal with bitfields (in C++) that is legitimately challenging to implement [1] that leads to bugs in compilers. It's not meant to be something that anyone is intended to use--indeed, I'd firmly suggest that the standard ought to prohibit this kind of usage. The broader point is that bitfields are actually weird little objects that look a lot like regular objects in many, but not all, contexts. And it's very easy from a language design or implementation perspective to forget to account for the possibility that you're dealing with a weird little object. This leads to underspecified language specifications and compilers that crash if you do something weird (but legal) such as virtually inherit from a struct containing a bitfield as its last member. [1] So challenging, in fact, that Clang gives an error message "cannot compile this conditional operator yet". It does work in g++, icx, and MSVC though.
  - iainmerrick 5y ago
    That all makes it sound like a C++ problem, not a C problem.
    - jcranmer 5y ago
      You can make a lot of the "fun" of bitfields go away with lvalue-to-rvalue conversion, and C tends to do this conversion very rapidly so that it's hard to find good cases for truly bizarre stuff, whereas C++ makes lvalues last a lot longer. Of course, if you go reach for C's standard "fun with lvalue" operations, you can get some crazy nonsense. What machine code should you generate here [1]: struct A { int x : 5; volatile _Atomic int y: 3; } a; a.y++; I will note that the intersection of volatile and bitfields has been another fruitful area of compiler bugs [2] historically speaking. While C++ does provide better what-the-ever-living-fuck moments for bitfields, C has had its fair share of issues with bitfields. [1] Whether or not you can make a bitfield _Atomic in C is implementation-defined, so it's possible that someone writes a C implementation where this is legal. I will note that, in a rare display of sanity, all C compilers I can test do in fact sensibly reject _Atomic bitfields, but for the purposes of argument, assume that someone has one where it's permitted, since it is allowable by the standard. [2] Or programmer bugs blamed on the compiler. This is the intersection of two areas that are notorious for underspecification to begin with, and combined with the general tendency of programmers to expect C compilers to be a thin veneer over assembly, makes it awfully difficult to figure out which behavior is language-intended.
WalterBright 5y ago
The compiler can rewrite it as: choice ? ((a.x = val),a.x) : ((a.y = val),a.y); The trick with a compiler is to rewrite complex constructions into simpler equivalent ones, then the code gen is much simpler and more reliable. For example, in the D compiler the `while` loop doesn't survive the semantic pass, as it gets rewritten into a `for` loop. The `for` loop then gets rewritten into `if` and `goto` statements. The code generator only needs to learn about `if` and `goto`.
- chrisseaton 5y ago
  > in the D compiler the `while` loop doesn't survive the semantic pass, as it gets rewritten into a `for` loop. The `for` loop then gets rewritten into `if` and `goto` statements You throw away structured control flow in favour of unstructured control flow? I would have thought it'd be the other way around and you'd be trying to recover nice clean structured control flow from raw concepts like goto.
  - jcranmer 5y ago
    Most middle-end compiler IRs are built on conditional/unconditional branches rather than high-level control flow structures. The key concepts at that level can usually be expressed in terms of dominators, postdominators, and/or control-dependence [1]. For example, a (natural) loop exists when a block dominates one of its predecessors. Induction variables in such loop can be very easily discovered, especially if you're already in SSA form (already usually the case at this level of IR). So, in short, structured control flow--or at least a sufficient subset of such structured control flow--can be easily recovered from low-level information, and you're generally not going to lose much information going down to that level. LLVM even has a way to attach metadata to loops despite not having any dedicated loop construct. [1] You only need two of these concepts: the third falls out from the definition of the other two.
  - WalterBright 5y ago
    > You throw away structured control flow in favour of unstructured control flow? That's right. It sounds counter-intuitive, but it works great. You wind up with a collection of blocks of code connected by edges. Then, you can use graph theory to work magic on them in a general, correct way. Data flow analysis is based on this. One thing the graph math does is enable the reconstruction of loops out of the blocks and edges - so you can write loops any way you please, and the compiler will figure it all out and apply general algorithms to it (like loop rotation, loop unrolling, etc.).

mwint 5y ago

Can someone explain further why this is so hard? I’m not familiar enough with any of this to understand without some help.

ncmncm 5y ago
It is just very finicky, with myriad edge cases easy to get wrong, and even easier to neglect to have complete tests for. Each target CPU design and version has quirks. Many involve sign extension.
- jstimpfle 5y ago
  Extracting a subrange of bits and shifting them to the beginning is not exactly rocket science.
  - ncmncm 5y ago
    Experience indicates otherwise. If you must use bit fields, make them unsigned. Bugs love to hide under signed bit fields.
    - jstimpfle 5y ago
      That makes sense, looking at how signed arithmetic works on different architectures it would feel strange to use signed bitfields. Unsigned bitfields are a nice way to get modular arithmetic with n bits without syntactic clutter.
      - ncmncm 5y ago
        "Unsigned bitfields are a nice ..." Appear to be. Are, when all the stars align. Are not in fact, often enough that you are issued a red warning you may ignore if you are insulated from all consequences.
jcranmer 5y ago
There's a few layers of complexity here. The first is lvalues. In compiler jargon, an lvalue is a kind of object that can have a value stored to it. And you can usually represent it as the address of some memory location [1]. Of course, bitfields break this representation: you need to know what the bit offset and bit size of the field you're storing is (as well as the signedness). The next level of complexity is the conditional operator. This means that, when conditional operators yield lvalues [2], you now end up in a situation where the lvalue now has a conditional bit offset and bit size within the address. Or maybe one leg of the expression returns a bit-field and the other leg returns a regular int lvalue. Imagine how complex your datastructure needs to be to represent an lvalue during this code generation phase. [1] Not all lvalues need to have memory locations. But if you're writing a C compiler, it's an easy first approximation to give every variable, even those marked register, some memory location and rely on an optimization pass to convert stack memory locations into register locations, rather than keeping track of this information when the frontend does code generation. [2] As mentioned elsewhere, conditional operators in C do not yield lvalues. But conditional operators in C++ do.

chrisseaton 5y ago

Is that valid C code? Is a ternary on an L-value an L-value? I'm not sure it is - regardless of bitfields or not? https://godbolt.org/z/aP8v5xKaz https://godbolt.org/z/aP8v5xKaz

jcranmer 5y ago
I mentioned in the note that it's not legal C, since ternaries must yield rvalues in C. It is legal C++, however, since there ternaries may be lvalues.
- chrisseaton 5y ago
  I feel like you added that after I replied.

iainmerrick 5y ago

But, you’d have an even harder time making that work with mask-and-shift macros! It also doesn’t seem like something that would come up very often. I can’t think of the last time I conditionally stored to one of two struct fields, if I ever have. The much more normal case would be: val = choice ? a.x : a.y; That one seems pretty straightforward from a codegen perspective.

ncmncm 5y ago
"Seems" is not the domain under discussion.
jcranmer 5y ago
The example I gave is an example of something legal with bitfields (in C++) that is legitimately challenging to implement [1] that leads to bugs in compilers. It's not meant to be something that anyone is intended to use--indeed, I'd firmly suggest that the standard ought to prohibit this kind of usage. The broader point is that bitfields are actually weird little objects that look a lot like regular objects in many, but not all, contexts. And it's very easy from a language design or implementation perspective to forget to account for the possibility that you're dealing with a weird little object. This leads to underspecified language specifications and compilers that crash if you do something weird (but legal) such as virtually inherit from a struct containing a bitfield as its last member. [1] So challenging, in fact, that Clang gives an error message "cannot compile this conditional operator yet". It does work in g++, icx, and MSVC though.
- iainmerrick 5y ago
  That all makes it sound like a C++ problem, not a C problem.
  - jcranmer 5y ago
    You can make a lot of the "fun" of bitfields go away with lvalue-to-rvalue conversion, and C tends to do this conversion very rapidly so that it's hard to find good cases for truly bizarre stuff, whereas C++ makes lvalues last a lot longer. Of course, if you go reach for C's standard "fun with lvalue" operations, you can get some crazy nonsense. What machine code should you generate here [1]: struct A { int x : 5; volatile _Atomic int y: 3; } a; a.y++; I will note that the intersection of volatile and bitfields has been another fruitful area of compiler bugs [2] historically speaking. While C++ does provide better what-the-ever-living-fuck moments for bitfields, C has had its fair share of issues with bitfields. [1] Whether or not you can make a bitfield _Atomic in C is implementation-defined, so it's possible that someone writes a C implementation where this is legal. I will note that, in a rare display of sanity, all C compilers I can test do in fact sensibly reject _Atomic bitfields, but for the purposes of argument, assume that someone has one where it's permitted, since it is allowable by the standard. [2] Or programmer bugs blamed on the compiler. This is the intersection of two areas that are notorious for underspecification to begin with, and combined with the general tendency of programmers to expect C compilers to be a thin veneer over assembly, makes it awfully difficult to figure out which behavior is language-intended.

WalterBright 5y ago

The compiler can rewrite it as: choice ? ((a.x = val),a.x) : ((a.y = val),a.y); The trick with a compiler is to rewrite complex constructions into simpler equivalent ones, then the code gen is much simpler and more reliable. For example, in the D compiler the `while` loop doesn't survive the semantic pass, as it gets rewritten into a `for` loop. The `for` loop then gets rewritten into `if` and `goto` statements. The code generator only needs to learn about `if` and `goto`.

chrisseaton 5y ago
> in the D compiler the `while` loop doesn't survive the semantic pass, as it gets rewritten into a `for` loop. The `for` loop then gets rewritten into `if` and `goto` statements You throw away structured control flow in favour of unstructured control flow? I would have thought it'd be the other way around and you'd be trying to recover nice clean structured control flow from raw concepts like goto.
- jcranmer 5y ago
  Most middle-end compiler IRs are built on conditional/unconditional branches rather than high-level control flow structures. The key concepts at that level can usually be expressed in terms of dominators, postdominators, and/or control-dependence [1]. For example, a (natural) loop exists when a block dominates one of its predecessors. Induction variables in such loop can be very easily discovered, especially if you're already in SSA form (already usually the case at this level of IR). So, in short, structured control flow--or at least a sufficient subset of such structured control flow--can be easily recovered from low-level information, and you're generally not going to lose much information going down to that level. LLVM even has a way to attach metadata to loops despite not having any dedicated loop construct. [1] You only need two of these concepts: the third falls out from the definition of the other two.
- WalterBright 5y ago
  > You throw away structured control flow in favour of unstructured control flow? That's right. It sounds counter-intuitive, but it works great. You wind up with a collection of blocks of code connected by edges. Then, you can use graph theory to work magic on them in a general, correct way. Data flow analysis is based on this. One thing the graph math does is enable the reconstruction of loops out of the blocks and edges - so you can write loops any way you please, and the compiler will figure it all out and apply general algorithms to it (like loop rotation, loop unrolling, etc.).