Module cranelift_codegen::machinst::blockorder

Computation of basic block order in emitted code.

This module handles the translation from CLIF BBs to VCode BBs.

The basic idea is that we compute a sequence of “lowered blocks” that correspond to one or more blocks in the graph: (CLIF CFG) union (implicit block on every edge). Conceptually, the lowering pipeline wants to insert moves for phi-nodes on every block-to-block transfer; these blocks always conceptually exist, but may be merged with an “original” CLIF block (and hence not actually exist; this is equivalent to inserting the blocks only on critical edges).

In other words, starting from a CFG like this (where each “CLIF block” and “(edge N->M)” is a separate basic block):

             CLIF block 0
              /           \
      (edge 0->1)         (edge 0->2)
             |                |
      CLIF block 1         CLIF block 2
             \                /
          (edge 1->3)   (edge 2->3)
                  \      /
                CLIF block 3

We can produce a CFG of lowered blocks like so:

           +--------------+
           | CLIF block 0 |
           +--------------+
              /           \
    +--------------+     +--------------+
    | (edge 0->1)  |     |(edge 0->2)   |
    | CLIF block 1 |     | CLIF block 2 |
    +--------------+     +--------------+
             \                /
         +-----------+ +-----------+
         |(edge 1->3)| |(edge 2->3)|
         +-----------+ +-----------+
                  \      /
               +------------+
               |CLIF block 3|
               +------------+

(note that the edges into CLIF blocks 1 and 2 could be merged with those blocks’ original bodies, but the out-edges could not because for simplicity in the successor-function definition, we only ever merge an edge onto one side of an original CLIF block.)

Each LoweredBlock names just an original CLIF block, an original CLIF block prepended or appended with an edge block (never both, though), or just an edge block.

To compute this lowering, we do a DFS over the CLIF-plus-edge-block graph (never actually materialized, just defined by a “successors” function), and compute the reverse postorder.

This algorithm isn’t perfect w.r.t. generated code quality: we don’t, for example, consider any information about whether edge blocks will actually have content, because this computation happens as part of lowering before regalloc, and regalloc may or may not insert moves/spills/reloads on any particular edge. But it works relatively well and is conceptually simple. Furthermore, the MachBuffer machine-code sink performs final peephole-like branch editing that in practice elides empty blocks and simplifies some of the other redundancies that this scheme produces.

Structs

BlockLoweringOrder

Mapping from CLIF BBs to VCode BBs.

Enums

LoweredBlock

The origin of a block in the lowered block-order: either an original CLIF block, or an inserted edge-block, or a combination of the two if an edge is non-critical.