Slicing for MLIR

Hi @mehdi_amini, As discussed in discord:

I am looking for a feature to go

FROM:

fn @main() {
  %0 = "create_core"() {id = "a"} : () -> !core
  %1 = "create_core"() {id = "b"}: () -> !core
  %2 = "create_core"() {id = "c"}: () -> !core

  %4 = some_other_value
  %5 = some_other_value

  %6 = some_other_value
  %7 = some_other_value

  bar(%0, %4, %5) : (!core)
  bar(%1, %4, %5) : (!core)
  bar(%2, %6, %7) : (!core)
}

TO:

fn @a () {
  %0 = "create_core"() {id = "a"} : () -> !core
  %4 = some_other_value                                                    <- copied (dup)
  %5 = some_other_value                                                   <- copied (dup)
  bar(%0, %4, %5) : (!core)
}

fn @b () {
  %0 = "create_core"() {id = "b"} : () -> !core
  %4 = some_other_value                                                   <- copied (dup)
  %5 = some_other_value                                                   <- copied (dup)
  bar(%0, %4, %5) : (!core)
}

fn @c () {
  %0 = "create_core"() {id = "c"} : () -> !core
  %6 = some_other_value                                                   <- moved
  %7 = some_other_value                                                   <- moved
  bar(%0, %6, %7) : (!core)
}

fn @main() {                                                     <- order of ops here doesnt matter
    call @a() : () -> ()
    call @b() : () -> ()
    call @c() : () -> ()
}

The spec can be something like this:

  • Slicing can be done based on an operation
  • Slicing creates a funcOp(?) with a name configurable by a user
    • Name can be operation dependent - i.e. slice (op, /*name*/op->getAttr("foo"))
  • All relative operation dependencies can be moved or copied
    • Moved only if the dependency is a singleton.
    • Copied if there are more operations using it.

Now that we are discussing this, could it also be possible to implement something like a merge as well?

  • i.e. merge (funcOp_a, funcOp_b, "merged")
    • results - assuming that we are working on the already-sliced code above.
fn @merged () {
  %0 = "create_core"() {id = "a"} : () -> !core
  %4 = some_other_value                                                    <- moved
  %5 = some_other_value                                                   <- moved
  bar(%0, %4, %5) : (!core)
  %1 = "create_core"() {id = "b"} : () -> !core
  %6 = some_other_value                                                   <- moved
  %7 = some_other_value                                                   <- moved
  bar(%1, %6, %7) : (!core)
}

fn @c () {
  %0 = "create_core"() {id = "c"} : () -> !core
  %6 = some_other_value                                                   <- moved
  %7 = some_other_value                                                   <- moved
  bar(%0, %6, %7) : (!core)
}

fn @main(){                                                     <- order of ops here doesnt matter
    call @merged() : () -> ()
    call @c() : () -> ()
}

It would seem like what you’re trying to do is take an operation and isolate a DAG of all its users and outline this DAG into a function call.

I’m not sure what you would call this utility. “SplitAndOutline”? The opposite operation, “merge”, already exists. It’s called inline + CSE.

I would start with a utility

LogicalResult splitAndOutline(Operation *root, function_ref<bool(Operation *)> canDuplicate);

Another question would be how to handle terminators. Possibly, terminator operands would be set to the results of the outlined function. Also, how would you handle nested regions?

FYI, I guess SVExtractTestCode pass in CIRCT is doing a similar thing (create modules from backward slices regarding specific operations like sv.assert, sv.assume, sv.cover) so it may help. For example,

hw.module @Foo(%clock:i1) -> () {
    sv.initial  {
       sv.assert %clock, immediate
       sv.assume %clock, immediate
       sv.cover %clock, immediate
    }
    hw.output
  }

will be transformed into something like this:

module {
  hw.module @Foo_assert(%clock: i1) {
    sv.initial {
      sv.assert %clock, immediate
    }
    hw.output
  }
  hw.module @Foo_assume(%clock: i1) {
    sv.initial {
      sv.assume %clock, immediate
    }
    hw.output
  }
  hw.module @Foo_cover(%clock: i1) {
    sv.initial {
      sv.cover %clock, immediate
    }
    hw.output
  }
 hw.module @Foo(%clock: i1) {
    hw.instance "InvisibleBind_assert"@Foo_assert(clock: %clock: i1) -> () 
    hw.instance "InvisibleBind_assume" @Foo_assume(clock: %clock: i1) -> ()
    hw.instance "InvisibleBind_cover"  @Foo_cover(clock: %clock: i1) -> () 
    hw.output
  }
}

code: https://github.com/llvm/circt/blob/main/lib/Dialect/SV/Transforms/SVExtractTestCode.cpp
test: https://github.com/llvm/circt/blob/main/test/Dialect/SV/hw-extract-test-code.mlir