Skip to content

[P0] --transform-ctrl-to-data-flow PASS violates SSA dominance when flattening blocks #177

@YanzhouTang

Description

@YanzhouTang

Problem

The --transform-ctrl-to-data-flow pass fails with "operand does not dominate this use" errors when processing functions with non-trivial control flow (diamond patterns, loops, nested conditionals).

Root Cause

The pass flattens multiple blocks into the entry block by iterating them in their physical order within the Region:

// lib/NeuraDialect/Transforms/TransformCtrlToDataFlowPass.cpp (line 487-494)
for (Block &block : region) {  // ❌ Arbitrary physical order
  if (&block != entry_block) {
    blocks_to_flatten.push_back(&block);
  }
}

This order is arbitrary and doesn't respect control flow structure. When blocks are moved in wrong order, uses can appear before definitions, violating SSA.

Visual Example

Consider this diamond CFG:

         entry
          / \
        bb1  bb2
    (def x)  (def y)
          \  /
          bb3
        (use x,y)
entry:
  %c1 = "neura.constant"() <{value = 1.0 : f32}> : () -> !neura.data<f32, i1>
  %c2 = "neura.constant"() <{value = 2.0 : f32}> : () -> !neura.data<f32, i1>
  %cond = "neura.icmp"(%c1, %c2) <{cmpType = "slt"}> : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<i1, i1>
  
  // === From bb3 (moved FIRST - but needs %x and %y!) ===
  %result = "neura.phi"(%x, %y) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
  // ❌ ERROR: %x and %y are not defined yet!
  
  // === From bb1 (moved SECOND - defines %x) ===
  %x = "neura.fadd"(%c1, %c2) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
  // %x is defined HERE (too late!)
  
  // === From bb2 (moved THIRD - defines %y) ===
  %y = "neura.fmul"(%c1, %c2) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
  // %y is defined HERE (too late!)
  
  "neura.return"(%result) : (!neura.data<f32, i1>) -> ()

Error: operand #0 does not dominate this use - phi uses %x and %y before they're defined!

Solution

Use Reverse Post-Order (RPO) traversal to ensure topological ordering:

Metadata

Metadata

Assignees

Labels

bugSomething isn't working

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions