Struct midenc_hir_transform::Treeify

pub struct Treeify;

This pass rewrites the CFG of a function so that it forms a tree.

While we technically call this treeification, the CFG cannot be fully converted into a tree in general, as loops must be preserved (they can be copied along multiple control flow paths, but we want to preserve the loop structure in the CFG).

The treeify transformation concerns itself with any block B which has multiple predecessors in the control flow graph, where for at least two of those predecessors, the predecessor is always visited before B, if control flows through both. This is a slightly less restrictive conditon than the dominance property, but is very much related - the primary difference being that unlike dominance, what we are capturing is that the predecessor block is not along a loopback edge. It is quite common for a predecessor block to always be visited first in the CFG, while not dominating its successor: consider an if/else expression, where control splits at the if/else, and rejoins afterwards, the code in the final block where control is joined can only be reached after either the if or else block has executed, but neither the if nor the else blocks can be considered to “dominate” the final block in the graph theoretical sense.

The actual treeification process works like so:

1. For each block B, in the postorder sort of the CFG, determine if B has more than one predecessor P, where P appears before B in the reverse postorder sort of the CFG. a. If found, treeify the block as described in subsequent steps b. Otherwise, ignore this block and proceed
2. For each P, clone B to a new block B’, and rewrite P such that it branches to B’ rather than B.
3. For each successor S of B: a. If S is a loop header, and S appears before B in the reverse postorder sort of the CFG, then it is a loopback edge, so the corresponding edge from B’ to S is left intact. b. If S is a loop header, but S appears after B in the reverse postorder sort of the CFG, then it is treated like other blocks (see c.) c. Otherwise, clone S to S’, and rewrite B’ to branch to S’ instead of S.
4. Repeat step 2 for the successors of S, recursively, until the subgraph reachable from B

Since we are treeifying blocks from the leaves of the CFG to the root, and because we do not follow loopback edges which escape/continue an outer loop - whenever we clone a subgraph of the CFG, we know that it has already been treeified, as we only start to treeify a block once all of the blocks reachable via that block have been treeified.

In short, we’re trying to split blocks with multiple predecessors such that all blocks have either zero or one predecessors, i.e. the CFG forms a tree. As mentioned previously, we must make an exception for loop headers, which by definition must have at least one predecessor which is a loopback edge, but this suits us just fine, as Miden Assembly provides control flow instructions compatible with lowering from such a CFG.

Examples

Basic DAG

This example demonstrates how the DAG of a function with multiple returns gets transformed:

blk0
 |
 v
blk1 -> blk3 -> ret
 |     /
 |    /
 |   /
 v  v
blk2
 |
 v
ret

Becomes:

blk0
 |
 v
blk1 -> blk3 -> ret
 |       |
 |       |
 |       |
 v       v
blk2    blk2
 |       |
 v       v
ret     ret

Basic Loop

This is an example of a function with multiple returns and a simple loop:

blk0
 |                -------
 v               v       |
blk1 -> blk3 -> blk4 -> blk5 -> ret
 |     /
 |    /
 |   /
 v  v
blk2
 |
 v
ret

Becomes:

blk0
 |                -------
 v               v       |
blk1 -> blk3 -> blk4 -> blk5 -> ret
 |       |
 |       |
 |       |
 v       v
blk2    blk2
 |       |
 v       v
ret     ret

Complex Loop

This is an example of a function with a complex loop (i.e. multiple exit points):

blk0
 |
 v
blk1
 |  \
 |   blk2 <-----
 |    |         |
 |   blk3       |
 |   /   \      |
 |  /     blk4--
 | /       |
 vv        |
blk5      blk6

Becomes:

blk0
 |
 v
blk1
 |  \
 |   \
 |    blk2 <---
 |     |       |
 |     v       |
 |    blk3     |
 |    |  \     |
 |    |   blk4--
 |    |    |
 v    v    v
blk5 blk5  blk6

NOTE: Here, when generating code for blk5 and blk6, the loop depth is 0, so we will emit a single push.0 at the end of both blocks which will terminate the containing loop, and then return from the function as we’ve reached the bottom of the tree.

Nested Loops

This is an extension of the example above, but with nested loops:

blk0
 |
 v
blk1
 |  \
 |   blk2 <-------
 |    |         | |
 |   blk3       | |
 |   /   \      | |
 |  /     blk4--  |
 | /       |      |
 vv        v      |
blk5<-    blk6-->blk7-->blk8
      |    ^             |
      |    |_____________|
      |                  |
      |__________________|

We have two loops, the outer one starting at blk2:

• blk2->blk3->blk4->blk2
• blk2->blk3->blk4->blk6->blk7->blk2

And the inner one starting at blk6:

• blk6->blk7->blk8->blk6

Additionally, there are multiple exits through the loops, depending on the path taken:

• blk2->blk3->blk5
• blk2->blk3->blk4->blk6->blk7->blk8->blk5
• blk6->blk7->blk8->blk5

After transformation, this becomes:

blk0
 |
 v
blk1
 |  \
 |   blk2 <-------
 |    |         | |
 |   blk3       | |
 |    |  \      | |
 |    |   blk4--  |
 |    |    |      |
 v    v    v      |
blk5 blk5 blk6-->blk7-->blk8
           ^             | |
           |_____________|_|
                         |
                         v
                        blk5

During codegen though, we end up with the following tree of stack machine code.

At each point where control flow either continues a loop or leaves it, we must

• Duplicate loop headers on control flow edges leading to those headers
• Emit N push.0 instructions on control flow edges exiting the function from a loop depth of N
• Emit a combination of the above on control flow edges exiting an inner loop for an outer loop, depending on what depths the predecessor and successor blocks are at

blk0
blk1
if.true
  blk2
  while.true
    blk3
    if.true
      blk4
      if.true
        blk2         # duplicated outer loop header
      else
        blk6
        while.true
          blk7
          if.true
            blk2     # duplicated outer loop header
            push.0   # break out of inner loop
          else
            blk8
            if.true
              blk6   # duplicated inner loop header
            else
              blk5
              push.0 # break out of outer loop
              push.0 # break out of inner loop
            end
          end
        end
      end
    else
      blk5
      push.0         # break out of outer loop
    end
  end
else
  blk5
end

Trait Implementations

impl Default for Treeify

fn default() -> Treeify

Returns the “default value” for a type.

impl PassInfo for Treeify

const FLAG: &'static str = Treeify

The string which should be used as the name of this pass on the command line.

const SUMMARY: &'static str = /// This pass rewrites the CFG of a function so that it forms a tree. /// /// While we technically call this treeification, the CFG cannot be fully converted into a /// tree in general, as loops must be preserved (they can be copied along multiple control /// flow paths, but we want to preserve the loop structure in the CFG). /// /// The treeify transformation concerns itself with any block B which has multiple predecessors /// in the control flow graph, where for at least two of those predecessors, the predecessor is /// always visited before B, if control flows through both. This is a slightly less restrictive /// conditon than the dominance property, but is very much related - the primary difference being /// that unlike dominance, what we are capturing is that the predecessor block is not along a /// loopback edge. It is quite common for a predecessor block to always be visited first in the /// CFG, while not dominating its successor: consider an if/else expression, where control splits /// at the `if/else`, and rejoins afterwards, the code in the final block where control is joined /// can only be reached after either the `if` or `else` block has executed, but neither the `if` /// nor the `else` blocks can be considered to "dominate" the final block in the graph theoretical /// sense. /// /// The actual treeification process works like so: /// /// 1. For each block B, in the postorder sort of the CFG, determine if B has more than one /// predecessor P, where P appears before B in the reverse postorder sort of the CFG. a. If /// found, treeify the block as described in subsequent steps b. Otherwise, ignore this block and /// proceed /// 2. For each P, clone B to a new block B', and rewrite P such that it branches to B' rather than /// B. /// 3. For each successor S of B: /// a. If S is a loop header, and S appears before B in the reverse postorder sort of the CFG, /// then it is a loopback edge, so the corresponding edge from B' to S is left intact. /// b. If S is a loop header, but S appears after B in the reverse postorder sort of the CFG, /// then it is treated like other blocks (see c.) /// c. Otherwise, clone S to S', and rewrite B' to branch to S' instead of S. /// 4. Repeat step 2 for the successors of S, recursively, until the subgraph reachable from B /// /// Since we are treeifying blocks from the leaves of the CFG to the root, and because we do not /// follow loopback edges which escape/continue an outer loop - whenever we clone a subgraph of /// the CFG, we know that it has already been treeified, as we only start to treeify a block once /// all of the blocks reachable via that block have been treeified. /// /// In short, we're trying to split blocks with multiple predecessors such that all blocks have /// either zero or one predecessors, i.e. the CFG forms a tree. As mentioned previously, we must /// make an exception for loop headers, which by definition must have at least one predecessor /// which is a loopback edge, but this suits us just fine, as Miden Assembly provides control flow /// instructions compatible with lowering from such a CFG. /// /// # Examples /// /// ## Basic DAG /// /// This example demonstrates how the DAG of a function with multiple returns gets transformed: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 -> blk3 -> ret /// | / /// | / /// | / /// v v /// blk2 /// | /// v /// ret /// ``` /// /// Becomes: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 -> blk3 -> ret /// | | /// | | /// | | /// v v /// blk2 blk2 /// | | /// v v /// ret ret /// ``` /// /// ## Basic Loop /// /// This is an example of a function with multiple returns and a simple loop: /// /// ```text,ignore /// blk0 /// | ------- /// v v | /// blk1 -> blk3 -> blk4 -> blk5 -> ret /// | / /// | / /// | / /// v v /// blk2 /// | /// v /// ret /// ``` /// /// Becomes: /// /// ```text,ignore /// blk0 /// | ------- /// v v | /// blk1 -> blk3 -> blk4 -> blk5 -> ret /// | | /// | | /// | | /// v v /// blk2 blk2 /// | | /// v v /// ret ret /// ``` /// /// ## Complex Loop /// /// This is an example of a function with a complex loop (i.e. multiple exit points): /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | blk2 <----- /// | | | /// | blk3 | /// | / \ | /// | / blk4-- /// | / | /// vv | /// blk5 blk6 /// ``` /// /// Becomes: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | \ /// | blk2 <--- /// | | | /// | v | /// | blk3 | /// | | \ | /// | | blk4-- /// | | | /// v v v /// blk5 blk5 blk6 /// ``` /// /// NOTE: Here, when generating code for `blk5` and `blk6`, the loop depth is 0, so /// we will emit a single `push.0` at the end of both blocks which will terminate the /// containing loop, and then return from the function as we've reached the bottom /// of the tree. /// /// ## Nested Loops /// /// This is an extension of the example above, but with nested loops: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | blk2 <------- /// | | | | /// | blk3 | | /// | / \ | | /// | / blk4-- | /// | / | | /// vv v | /// blk5<- blk6-->blk7-->blk8 /// | ^ | /// | |_____________| /// | | /// |__________________| /// ``` /// /// We have two loops, the outer one starting at `blk2`: /// /// * `blk2->blk3->blk4->blk2` /// * `blk2->blk3->blk4->blk6->blk7->blk2` /// /// And the inner one starting at `blk6`: /// /// * `blk6->blk7->blk8->blk6` /// /// Additionally, there are multiple exits through the loops, depending on the path taken: /// /// * `blk2->blk3->blk5` /// * `blk2->blk3->blk4->blk6->blk7->blk8->blk5` /// * `blk6->blk7->blk8->blk5` /// /// After transformation, this becomes: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | blk2 <------- /// | | | | /// | blk3 | | /// | | \ | | /// | | blk4-- | /// | | | | /// v v v | /// blk5 blk5 blk6-->blk7-->blk8 /// ^ | | /// |_____________|_| /// | /// v /// blk5 /// ``` /// /// During codegen though, we end up with the following tree of stack machine code. /// /// At each point where control flow either continues a loop or leaves it, we must /// /// * Duplicate loop headers on control flow edges leading to those headers /// * Emit N `push.0` instructions on control flow edges exiting the function from a loop depth of N /// * Emit a combination of the above on control flow edges exiting an inner loop for an outer loop, /// depending on what depths the predecessor and successor blocks are at /// /// ```text,ignore /// blk0 /// blk1 /// if.true /// blk2 /// while.true /// blk3 /// if.true /// blk4 /// if.true /// blk2 # duplicated outer loop header /// else /// blk6 /// while.true /// blk7 /// if.true /// blk2 # duplicated outer loop header /// push.0 # break out of inner loop /// else /// blk8 /// if.true /// blk6 # duplicated inner loop header /// else /// blk5 /// push.0 # break out of outer loop /// push.0 # break out of inner loop /// end /// end /// end /// end /// else /// blk5 /// push.0 # break out of outer loop /// end /// end /// else /// blk5 /// end /// ``` #[derive(Default, PassInfo, ModuleRewritePassAdapter)] pub struct Treeify;

A short, single-line description of what this pass does.

const DESCRIPTION: &'static str = /// This pass rewrites the CFG of a function so that it forms a tree. /// /// While we technically call this treeification, the CFG cannot be fully converted into a /// tree in general, as loops must be preserved (they can be copied along multiple control /// flow paths, but we want to preserve the loop structure in the CFG). /// /// The treeify transformation concerns itself with any block B which has multiple predecessors /// in the control flow graph, where for at least two of those predecessors, the predecessor is /// always visited before B, if control flows through both. This is a slightly less restrictive /// conditon than the dominance property, but is very much related - the primary difference being /// that unlike dominance, what we are capturing is that the predecessor block is not along a /// loopback edge. It is quite common for a predecessor block to always be visited first in the /// CFG, while not dominating its successor: consider an if/else expression, where control splits /// at the `if/else`, and rejoins afterwards, the code in the final block where control is joined /// can only be reached after either the `if` or `else` block has executed, but neither the `if` /// nor the `else` blocks can be considered to "dominate" the final block in the graph theoretical /// sense. /// /// The actual treeification process works like so: /// /// 1. For each block B, in the postorder sort of the CFG, determine if B has more than one /// predecessor P, where P appears before B in the reverse postorder sort of the CFG. a. If /// found, treeify the block as described in subsequent steps b. Otherwise, ignore this block and /// proceed /// 2. For each P, clone B to a new block B', and rewrite P such that it branches to B' rather than /// B. /// 3. For each successor S of B: /// a. If S is a loop header, and S appears before B in the reverse postorder sort of the CFG, /// then it is a loopback edge, so the corresponding edge from B' to S is left intact. /// b. If S is a loop header, but S appears after B in the reverse postorder sort of the CFG, /// then it is treated like other blocks (see c.) /// c. Otherwise, clone S to S', and rewrite B' to branch to S' instead of S. /// 4. Repeat step 2 for the successors of S, recursively, until the subgraph reachable from B /// /// Since we are treeifying blocks from the leaves of the CFG to the root, and because we do not /// follow loopback edges which escape/continue an outer loop - whenever we clone a subgraph of /// the CFG, we know that it has already been treeified, as we only start to treeify a block once /// all of the blocks reachable via that block have been treeified. /// /// In short, we're trying to split blocks with multiple predecessors such that all blocks have /// either zero or one predecessors, i.e. the CFG forms a tree. As mentioned previously, we must /// make an exception for loop headers, which by definition must have at least one predecessor /// which is a loopback edge, but this suits us just fine, as Miden Assembly provides control flow /// instructions compatible with lowering from such a CFG. /// /// # Examples /// /// ## Basic DAG /// /// This example demonstrates how the DAG of a function with multiple returns gets transformed: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 -> blk3 -> ret /// | / /// | / /// | / /// v v /// blk2 /// | /// v /// ret /// ``` /// /// Becomes: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 -> blk3 -> ret /// | | /// | | /// | | /// v v /// blk2 blk2 /// | | /// v v /// ret ret /// ``` /// /// ## Basic Loop /// /// This is an example of a function with multiple returns and a simple loop: /// /// ```text,ignore /// blk0 /// | ------- /// v v | /// blk1 -> blk3 -> blk4 -> blk5 -> ret /// | / /// | / /// | / /// v v /// blk2 /// | /// v /// ret /// ``` /// /// Becomes: /// /// ```text,ignore /// blk0 /// | ------- /// v v | /// blk1 -> blk3 -> blk4 -> blk5 -> ret /// | | /// | | /// | | /// v v /// blk2 blk2 /// | | /// v v /// ret ret /// ``` /// /// ## Complex Loop /// /// This is an example of a function with a complex loop (i.e. multiple exit points): /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | blk2 <----- /// | | | /// | blk3 | /// | / \ | /// | / blk4-- /// | / | /// vv | /// blk5 blk6 /// ``` /// /// Becomes: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | \ /// | blk2 <--- /// | | | /// | v | /// | blk3 | /// | | \ | /// | | blk4-- /// | | | /// v v v /// blk5 blk5 blk6 /// ``` /// /// NOTE: Here, when generating code for `blk5` and `blk6`, the loop depth is 0, so /// we will emit a single `push.0` at the end of both blocks which will terminate the /// containing loop, and then return from the function as we've reached the bottom /// of the tree. /// /// ## Nested Loops /// /// This is an extension of the example above, but with nested loops: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | blk2 <------- /// | | | | /// | blk3 | | /// | / \ | | /// | / blk4-- | /// | / | | /// vv v | /// blk5<- blk6-->blk7-->blk8 /// | ^ | /// | |_____________| /// | | /// |__________________| /// ``` /// /// We have two loops, the outer one starting at `blk2`: /// /// * `blk2->blk3->blk4->blk2` /// * `blk2->blk3->blk4->blk6->blk7->blk2` /// /// And the inner one starting at `blk6`: /// /// * `blk6->blk7->blk8->blk6` /// /// Additionally, there are multiple exits through the loops, depending on the path taken: /// /// * `blk2->blk3->blk5` /// * `blk2->blk3->blk4->blk6->blk7->blk8->blk5` /// * `blk6->blk7->blk8->blk5` /// /// After transformation, this becomes: /// /// ```text,ignore /// blk0 /// | /// v /// blk1 /// | \ /// | blk2 <------- /// | | | | /// | blk3 | | /// | | \ | | /// | | blk4-- | /// | | | | /// v v v | /// blk5 blk5 blk6-->blk7-->blk8 /// ^ | | /// |_____________|_| /// | /// v /// blk5 /// ``` /// /// During codegen though, we end up with the following tree of stack machine code. /// /// At each point where control flow either continues a loop or leaves it, we must /// /// * Duplicate loop headers on control flow edges leading to those headers /// * Emit N `push.0` instructions on control flow edges exiting the function from a loop depth of N /// * Emit a combination of the above on control flow edges exiting an inner loop for an outer loop, /// depending on what depths the predecessor and successor blocks are at /// /// ```text,ignore /// blk0 /// blk1 /// if.true /// blk2 /// while.true /// blk3 /// if.true /// blk4 /// if.true /// blk2 # duplicated outer loop header /// else /// blk6 /// while.true /// blk7 /// if.true /// blk2 # duplicated outer loop header /// push.0 # break out of inner loop /// else /// blk8 /// if.true /// blk6 # duplicated inner loop header /// else /// blk5 /// push.0 # break out of outer loop /// push.0 # break out of inner loop /// end /// end /// end /// end /// else /// blk5 /// push.0 # break out of outer loop /// end /// end /// else /// blk5 /// end /// ``` #[derive(Default, PassInfo, ModuleRewritePassAdapter)] pub struct Treeify;

A rich, potentially multi-line description of this pass and its configuration.

impl RewritePass for Treeify

type Entity = Function

The entity type to which this rewrite applies

fn apply( &mut self, function: &mut Self::Entity, analyses: &mut AnalysisManager, session: &Session, ) -> RewriteResult

Apply this rewrite to entity

fn should_apply(&self, _entity: &Self::Entity, _session: &Session) -> bool

Returns true if this rewrite should be applied to entity

fn chain<R>(self, next: R) -> RewriteSet<Self::Entity>

where Self: Sized + 'static, R: RewritePass<Entity = Self::Entity> + 'static,

Apply this rewrite, then next as a pipeline of rewrites