# REP13 - Nested Cyclical Region Identification ###### tags: `revng-hour`, `region-identification`, `cycles`, `REP` --- ### MLIR Pipeline Overview ```graphviz digraph { node[shape=box] Input -> Dispatchers [label=LLVMIR] Dispatchers -> SESEify [label=LLVMIR] SESEify -> BB_Specialization [label=LLVMIR] BB_Specialization -> Tiling [label=LLVMIR] Tiling -> Backend [label=Clift] {rank = same; Input; Dispatchers; SESEify; BB_Specialization; Tiling; Backend} Region_Identification [style=dashed] # Cycle_Set_ID [style=dashed] Region_Identification -> Dispatchers [style=dashed] # Cycle_Set_ID -> SESEify [style=dashed] Region_Identification_2 [style=dashed, label="Region_Identification"] Region_Identification_2 -> Tiling [style=dashed] {rank = same; Region_Identification;} } ``` ---- - The goal of the __region-identification__ analysis is to detect a well-nested tree of __cyclical regions__ - Each cyclical region represents a set of strongly connected nodes of the CFG. ---- - Cyclical regions should be __well nested__ (either strictly nested or disjoint, never partially overlapping). - Informally, each of the detected cyclical regions is an area of the CFG that we plan to emit as a __loop__ in C ---- ```graphviz digraph { node[shape=box] edge[dir=forward] {rankdir = LR} A -> B B -> C C -> D C -> B D -> A } ``` ---- ```graphviz digraph { node[shape=box] edge[dir=forward] rankdir="TB" A -> B B -> C C -> D D -> B [constraint=false] C -> A [constraint=false] } ``` --- ### `GenericCycle` - Our analysis relies on LLVM `GenericCycle`, which constructs a well nested tree of regions in the following way: ---- #### Definitions 1) In a directed graph F, a _cycle_ is a maximal strongly connected region with at least one internal edge. 2) A bb in a cycle that can be reached from the entry of F, and which does not visit any other bb, is an entry (multiple). 3) For a given DFS, the first node of a cycle is the `header`. ---- 4) In any DFS starting from entry, the set of cycles is the same. These are the _top-level cycles_. 5) The _child cycles_ nested inside a cycle C with header H, are the cycles in the subgraph induced on the set of nodes (C - H). 6) We have an implementation-defined forest of cycles. ---- ```graphviz digraph { node[shape=box] edge[dir=forward] rankdir="TB" {rank = same; A; B} Entry -> A Entry -> B A -> A B -> B A -> C B -> C C -> A C -> B } ``` - cycle: {A, B, C} entries: {A, B} header: A - cycle: {B, C} entries: {B, C} header: C - cycle: {B} entries: {B} header: B ---- #### LLVM loops vs cycles - A _loop_, has the additional requirement to have a defined _header_, which dominates all the bbs in the loop (only _entry_) - A cycle is irreducible if it has multiple entries. - If the whole CFG is reducible, the cycles map one-to-one over the natural loops and each cycle has a single _entry_ block ---- - Irreducible control flow: ```graphviz digraph { node[shape=box] edge[dir=forward] rankdir="TB" {rank = same; A; B} Entry -> A Entry -> B A -> B B -> A B -> C } ``` ---- - Nested Cyclical Regions are a concept that is looser than LLVM loops, and also than C loops. This means that given a CFG there can be a higher number of nested cyclical regions than loops. - Therefore, the results of this analysis are used to identify candidates for being promoted to C loops by some transformations on the CFG (dispatchers/first iteration outlining) and tiling (adding some `goto`s). ---- ```graphviz digraph { node[shape=box] edge[dir=forward] rankdir="TB" #{rank = same; A; B} B2 [label="B'"] Entry -> A Entry -> B2 A -> B B -> A B -> C B2 -> A B2 -> C } ``` --- ### Design and Implementation - We don't want a LLVMIR specific pass. In our current pipeline, we already need this analysis to work on both LLVMIR and MLIR LLVM Dialect. - Therefore, we implemented this as an analysis working merely on the `llvm::GraphTraits` exposed by the underlying graph. - We then instantiate it in the two situations. ---- #### - Each region is represented by (info given by `GenericCycle`): - The blocks composing it - The blocks that are considered _entries_ (and `header`) - The exit blocks (branched to) - The parent cycle (unique) - The children cycles ---- - In addition, we compute: - The entry block (may be different from `header`) - The retreating edges (given by the DFS visit) - Loop successor inlining (blocks directly dominated) ---- #### Loop inlining ```graphviz digraph { node[shape=box] edge[dir=forward] rankdir="TB" D [label="ret 1"] E [label="ret 2"] A -> B B -> C C -> A [constraint=false] C -> D B -> E } ``` ---- #### DFS ordering ```graphviz digraph { node[shape=box] edge[dir=forward] A -> B A -> D B -> C C -> D D -> C [style=dashed, color=red] D -> B [style=dashed, color=red] } ``` ---- #### DFS ordering ```graphviz digraph { node[shape=box] edge[dir=forward] A -> D A -> B B -> C C -> D [style=dashed, color=red] D -> C D -> B } ``` --- ### Questions? --- #### `GraphTraits` desiderata - A __read-only__ analysis like the showed one is easy to decouple, but what about a tranformation? - My idea is that in every IR (LLVM or MLIR), a CFG transformation basically consists of rewriting the __terminator__ of a bb changing the dest-operands. ---- #### `GraphTraits` desiderata - If we can abstract everything like this (taking into account of the corner cases where a `brcond` may become a `br` or a `switch`), we could have a `rewriteTerminatorOperands` trait that should be implemented by all the IR that we want to support. - Anyone has already experimented with this?
{}