[MLIR][Concept] "SSA CFG Region" vs "Graph Region"

MLIR
1

Hello

I was reading the MLIR documentation on regions and became curious about the difference between SSA CFG region and Graph region.

To my understanding, the main difference is that

SSA CFG region

  • reads lines sequentially
  • can have blocks within entry block

while

Graph region

  • can only have an entry block
  • operations does not have regions (so it is like a function signature without implementation)

It seems like region type is the characteristic specific to an operation.

I am curious if this was language design effort to create Abstraction and Polymorphism.

Is it okay to think graph region as something like interface in Java? and SSA CFG region is just a regular class?

or

Is there any other reason for having a graph region? (e.g, performance gain)

Thanks

2

I don’t quite get what you mean with this?

Graph region are limited to a single block, where there is no implicit “control flow” defined by the textual order of the operations. The execution order is defined by the enclosing operation.

There is no restriction on operations having regions or not inside a graph region.

I can’t really understand the analogy right now unfortunately.

3

Hello Mehdi

Thank you for the reply.

Do you mind asking what was the purpose of making graph region syntax when you were initially creating MLIR?

I think everything can be expressed using SSA CFG region syntax.

Thanks

4

One easy example is representing arbitrary graphs with cycles: https://llvm.org/devmtg/2021-11/slides/2021-RepresentingConcurrencywithGraphRegionsinMLIR.pdf

NOTSSA(%b) {
%a2 = op(%a1, %b)
%a3 = op(%a2, %b)
%a1 = op(%a3, %b)
}

That’s relatively recent as it refers to https://circt.llvm.org/ dialects.

For the historical background, see:

5

Thank you so much! Matt

I read all your links and finally able to understand what they are.

I will summarize my understanding so that future people benefit from it.

Summary

Region kind is the characteristic of specific operation. If region exists in an operation, operation can have one of SSA CFG region or graph region.

SSA CFG Region

  • can have multiple blocks within the region (because, we assume that SSA CFG region won’t have a loop).
  • reads operation sequentially from top to bottom.
  • In the control flow graph, we assume the directed graph is acyclic, meaning it doesn’t have infinite loop.

SSA CFG region should be DAG (Directed Acyclic Graph)

  • In the control flow graph, operation is denoted as node and value is denoted as arrow.

SSA CFG region Example

Code
func.func @f(%1: i32) -> () {
    %2 = func.call @g(%1) : (i32) -> i32
    %3 = func.call @h(%1, %2) : (i32, i32) -> i32
    func.return
}

func.func @g(%1: i32) -> i32 {
    func.return %1 : i32
}

func.func @h(%1: i32, %2: i32) -> i32 {
    %3 = arith.addi %1, %2 : i32
    func.return %3 : i32
}

Control flow graph of the code

SSA CFG
SSA CFG320Ă—272 7.38 KB

  • The control flow graph does not have cycle.

Graph Region

  • cannot have blocks within the entry block. There is no specific reason for this as stated in the documentation.
  • allows cycle in the control flow graph.
  • is designed to express structure. For example, in GPU programming, we send script to GPU for parallel programming. Another example, is expressing circuit design, which can have a cycle.
    • Thus, order of operations within the region does not matter.
  • is like a flag to an operation, that this operation may have a cycle.

Graph Region can contain cycles

Graph region example

func.func @f(%1: i32) -> () {
    %2 = func.call @g(%1) : (i32) -> i32
    %1 = func.call @h(%2) : (i32) -> i32
    func.return
}

func.func @g(%1: i32) -> i32 {
    func.return %1 : i32
}

func.func @h(%1: i32) -> i32 {
    %3 = arith.addi %1, %2 : i32
    func.return %1 : i32
}

Control flow graph of code

Graph region
Graph region236Ă—246 6.21 KB

6

This isn’t exact. Operations can have as many regions as they want. But all of those regions should be of the same kind.

This isn’t exact either. SSA CFG regions may and do have cycles, otherwise one would be unable to express a basic loop construct. What they can’t have are cycles between operations, i.e., an operation A cannot use as operand the result of an operation B if B also uses the result of A as an operand (going through basic block arguments break this cycle). This is not limited to a single block.

Function calls are a different kind of control flow, this example is irrelevant.

This makes no sense. Blocks cannot have blocks (directly) in them. Graph regions must have at most one block though.

There isn’t really a control flow graph in graph regions, as opposed to CFG regions where CFG stands for Control Flow Graph. Control flow graph exists between blocks.

This isn’t true. We don’t send a script to GPU, but a compiled program. There are multiple kinds of concurrent on GPUs (between threads, warps, and blocks + asynchronous copies and tensor operations). None of them are expressed using graph regions in upstream MLIR dialects as far as I know.

I can only encourage you to read the documentation: https://mlir.llvm.org/docs/LangRef/#high-level-structure and follow the tutorial Understanding the IR Structure - MLIR . Perhaps some reading on what is an IR, what is the SSA form, and some graph concepts like dominance will be needed as a precondition.

7

Thank you, Alex, for the clarification.
I was going to edit summary above, but it seems like editing is disabled, so I will put fixed part here.

SSA Dominance Rule

  • SSA value is reachable in the nested block.

Code

func.func @f() -> () {
  // entry block
  %1 = arith.constant 2026 : i32 // SSA Value
  %zero = arith.constant 0 : i32
  %condition = arith.cmpi sgt, %1, %zero : i32
  cf.cond_br %condition, ^block1, ^block2

^block1:
  %0 = arith.addi %1, %1 : i32 // entry block is on the path to block1, so the block can use %1
  func.return

^block2:
  %2 = arith.addi %1, %1 : i32 // entry block is on the path to block2, so the block can use %1
  func.return
}

SSA Control Flow Graph

ssa dominance
ssa dominance568Ă—338 13.7 KB

Graph Region

  • It allows cycle between operations.

Code

func.func @f() -> (){
    %1 = op1 %1, %3 : (i32, i32) -> (i32)
    %3 = op2 %1, %4 : (i32, i32) -> (i32)
    %4 = op3 %1 : (i32) -> (i32)
    func.return
}

Visualization of the graph region code

  • It is not a directed graph.
  • (I guess Mehdi (@mehdi_amini) didn’t allow blocks within the region because it is undirected graph and there is no domination relation)

graph region visualization
graph region visualization546Ă—268 13.3 KB

8

Indeed, only moderators or highly trusted users may edit posts.

https://en.wikipedia.org/wiki/Dominator\_(graph_theory) . Dominance means an operation is encountered on every control flow path leading to the current operation. There are related concepts of reaching definitions and available values/expressions. You can find these and more in any decent compiler textbook.

It is directed. The arrows may point from uses to definitions or vice versa, depending on the interpretation. It just allows for cycles.

There is simply no need for multiple blocks in graph regions. Blocks serve to break use-def cycles via block arguments (also known as phi nodes). Cycles are allowed in graph regions.

9

Thanks a lot for the help! Alex
:smiley: