# 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?