SSA dominance

MLIR
1

Hi all,

We recently encountered some surprising (at least to me) behavior in the dominance analysis, that led to implementing a custom dominance analysis in our code base.

Consider the following:

func @test() -> i32 {
  %c1_i32 = constant 1 : i32
  %c2_i32 = constant 2 : i32
  %0 = addi %c1_i32, %c2_i32 : i32
  return %0 : i32
}

Then c1 dominates addi and c2 dominates addi.

But what is the reason that c1 dominate c2? I’m probably missing something, but they seem unrelated to me? According to mlir::DominanceInfo because c1 precedes c2 in the same block. Does anyone know what was the reason for this choice?

2

Dominance has to do with control flow paths – it has nothing to do with other relations between ops like def/use or dependences. All paths to c2 flow through c1 (since this block isn’t in a graph region) – hence c1 dominates c2.

1 Like
3

Thanks. I see, so putting operations together in a block implies strictly sequential flow? I was indeed assuming that dominance would be similar to def/use for MLIR.

4

Yes, unless this is a graph region.

We just reuse the dominance definition that LLVM is using and that is coming from the SSA compiler literature I believe: Dominator (graph theory) - Wikipedia (note that the graph you see on this page isn’t the def-use chains, but the CFG: the nodes are blocks and the edges are branches).

5

Thanks, I understand. Ok, so my use case may be a bit of an extreme. The question arose from a dialect for a neuromorphic architecture where the data flow graph and control flow graph are for all intents and purposes the same thing. In this case all operations are in their own block in the SSA compiler literature sense, and therefore def-use chains and CFG are more or less the same in this context.

I think what I was really after is a block with semantics somewhere between RegionKind::SSACFG and RegionKind::Graph; RegionKind::SSADFG maybe? I suppose that doesn’t make sense for most uses of MLIR.

6

Could you expand about why in between? What about the Graph kind wouldn’t work?

7

Sure, I don’t want to allow cycles between the operations in the region.

Conceptually there is a certain control flow, it just happens to be the same as the flow of data. If in SSACFG dominance means A dominates B in the same block if A precedes B; and in Graph A and B dominate each other when in the same block, then I was looking for a region kind where A dominates B if B uses A. This seems to sit between the existing two region kinds.
More practically, it is just convenient to be able to depend on the ordering of operations in the block.

8

Ah, so a graph region type + verifier on op for cycles would be the in between?

9

That’s not really a control-flow to me: I understand it as “there is a flow that provides you with which instructions to execute next”: basically it is the frontend of the CPU (instruction pointer, etc.). In your model you have a dataflow graph: two operations not related with each other in the dataflow graph aren’t ordered, this has not translation in terms of control-flow.

The Graph Region was created to support this. There is the question of cycles indeed, Jacques mentioned that you can have a verifier on your graph region to forbid cycles, I’d have to think if it is consistent with any potential generic transformation on graph region but you’d be fine with any of your own pipeline on such a region.