3 ms·

> 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

• 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.).
  • chrisseaton 5y ago
    The compiler I work with most, Graal, does the opposite and keeps structured loops as a first-class concept in the graph almost all the way through compilation, and turns jumps into a structured loop if it can. We find it makes reasoning about the loops easier. It does make irreducible control-flow harder to deal with (and in some cases impossible.)
    • WalterBright 5y ago
      C doesn't constrain what e1, e2, and e3 are or what they do in `for(e1;e2;e3)`, and goto's can be willy-nilly turning it into a hash anyway. Hence, trying to use the higher level construct is going to result in lots of special case code, and special case code is much more likely to lead to problems. But hey, if Graal works for you, great!
• ncmncm 5y ago
  Structured control flow is a thing to help people understand code. The compiler's job is to emit instructions that do precisely the things the code says to do, as efficiently as possible. There is no need for chips to understand the purpose of the code; they just need to do what it says. They don't get confused.
  • mhh__ 5y ago
    Chips don't need to know but knowing information about loops is really important, so some structure or metadata can go a very long way.
  • chrisseaton 5y ago
    > as efficiently as possible Which requires a high-level understanding of the program and its control flow.
    • WalterBright 5y ago
      > Which requires a high-level understanding of the program and its control flow. The `for` loop construct does not offer the compiler any more understanding of the code than one made from `goto`s. They contain the same information, and are interchangeable. The latter, however, is more amenable to applying mathematical algorithms to. The former is more amenable to human understanding.
      • chrisseaton 5y ago
        Why is unstructured control-flow better for applying algorithms than structured control flow? That seems counter-intuitive to me. With structured control-flow I can do things like reason about the level of nesting of the loop that I'm in. I can peel a loop iteration by literally saying 'take this loop here - copy the body of it out'. For context here's the kind of structure we use https://chrisseaton.com/truffleruby/basic-graal-graphs/#loops https://chrisseaton.com/truffleruby/basic-graal-graphs/#loop....