[P1] Create a canonicalization pass

[ShangkunLi]

Create a canonicalization pass to transform all kinds of CFG edges into cond_br/br edges with values.

Then we can use transform ctrl2data to transform it into dataflow representation.

[tancheng]

struct PromoteLiveInsPass : mlir::PassWrapper<PromoteLiveInsPass, OperationPass<YourFuncOp>> {
  void runOnOperation() override {
    auto func = getOperation();
    for (auto &block : func.getBody()) {
      mlir::promoteValuesToBlockArguments(block);
    }
  }
};

is suggested by GPT (i am trying to ask whether there existing pass/util can help us).

[ShangkunLi]

Hi~ @tancheng I have implemented this canonicalization pass. The problem now is that the pass will bring many unnecessary operations. The result is an incraesed II.

For example, for branch_for.mlir, we can get RecMII=4, ResMII=2, but the CompiledII=6 because this pass will bring extra 8 operations for this case (e.g., grant_predicate, phi).

Even using the exhaustive strategy, the compiled II is still 6. And the mapping time is ~10 mins.

So I am thinking if it deserves to introduce such a pass...

[tancheng]

Hi~ @tancheng I have implemented this canonicalization pass. The problem now is that the pass will bring many unnecessary operations. The result is an incraesed II.

For example, for branch_for.mlir, we can get RecMII=4, ResMII=2, but the CompiledII=6 because this pass will bring extra 8 operations for this case (e.g., grant_predicate, phi).

Even using the exhaustive strategy, the compiled II is still 6. And the mapping time is ~10 mins.

So I am thinking if it deserves to introduce such a pass...

Can you show the before and after IRs? II=6 is the mapping's issue, these two issues are orthogonal, the canonicalization pass should always be there (one can optionally skip the ctrl-flow canonicalization but just keep function argument canonicalization if you want to achieve better II).

[ShangkunLi]

Can you show the before and after IRs? II=6 is the mapping's issue, these two issues are orthogonal, the canonicalization pass should always be there (one can optionally skip the ctrl-flow canonicalization but just keep function argument canonicalization if you want to achieve better II).

The before and after bb-based IR:

module {
  func.func @loop_test() -> f32 attributes {accelerator = "neura"} {
    %0 = "neura.constant"() <{predicate = true, value = 10 : i64}> : () -> i64
    %1 = "neura.constant"() <{predicate = true, value = 0 : i64}> : () -> i64
    %2 = "neura.constant"() <{predicate = true, value = 1 : i64}> : () -> i64
    %3 = "neura.constant"() <{predicate = true, value = 3.000000e+00 : f32}> : () -> f32
    %4 = "neura.constant"() <{predicate = true, value = 0.000000e+00 : f32}> : () -> f32
    neura.br %1, %4 : i64, f32 to ^bb1
  ^bb1(%5: i64, %6: f32):  // 2 preds: ^bb0, ^bb1
    %7 = "neura.fadd"(%6, %3) : (f32, f32) -> f32
    %8 = "neura.add"(%5, %2) : (i64, i64) -> i64
    %9 = "neura.icmp"(%8, %0) <{cmpType = "slt"}> : (i64, i64) -> i1
    neura.cond_br %9 : i1 then %8, %7 : i64, f32 to ^bb1 else %7 : f32 to ^bb2
  ^bb2(%10: f32):  // pred: ^bb1
    "neura.return"(%10) : (f32) -> ()
  }
}

module {
  func.func @loop_test() -> f32 attributes {accelerator = "neura"} {
    %0 = "neura.constant"() <{predicate = true, value = 10 : i64}> : () -> i64
    %1 = "neura.constant"() <{predicate = true, value = 0 : i64}> : () -> i64
    %2 = "neura.constant"() <{predicate = true, value = 1 : i64}> : () -> i64
    %3 = "neura.constant"() <{predicate = true, value = 3.000000e+00 : f32}> : () -> f32
    %4 = "neura.constant"() <{predicate = true, value = 0.000000e+00 : f32}> : () -> f32
    neura.br %1, %4, %3, %2, %0 : i64, f32, f32, i64, i64 to ^bb1
  ^bb1(%5: i64, %6: f32, %7: f32, %8: i64, %9: i64):  // 2 preds: ^bb0, ^bb1
    %10 = "neura.fadd"(%6, %7) : (f32, f32) -> f32
    %11 = "neura.add"(%5, %8) : (i64, i64) -> i64
    %12 = "neura.icmp"(%11, %9) <{cmpType = "slt"}> : (i64, i64) -> i1
    neura.cond_br %12 : i1 then %11, %10, %3, %2, %0 : i64, f32, f32, i64, i64 to ^bb1 else %10 : f32 to ^bb2
  ^bb2(%13: f32):  // pred: ^bb1
    "neura.return"(%13) : (f32) -> ()
  }
}

The before and after dataflow IR:

module {
  func.func @loop_test() -> f32 attributes {accelerator = "neura"} {
    %0 = "neura.constant"() <{predicate = true, value = 10 : i64}> : () -> !neura.data<i64, i1>
    %1 = "neura.grant_always"(%0) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %2 = "neura.constant"() <{predicate = true, value = 0 : i64}> : () -> !neura.data<i64, i1>
    %3 = "neura.grant_once"(%2) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %4 = "neura.constant"() <{predicate = true, value = 1 : i64}> : () -> !neura.data<i64, i1>
    %5 = "neura.grant_always"(%4) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %6 = "neura.constant"() <{predicate = true, value = 3.000000e+00 : f32}> : () -> !neura.data<f32, i1>
    %7 = "neura.grant_always"(%6) : (!neura.data<f32, i1>) -> !neura.data<f32, i1>
    %8 = "neura.constant"() <{predicate = true, value = 0.000000e+00 : f32}> : () -> !neura.data<f32, i1>
    %9 = "neura.grant_once"(%8) : (!neura.data<f32, i1>) -> !neura.data<f32, i1>
    %10 = neura.reserve : !neura.data<f32, i1>
    %11 = "neura.phi"(%10, %9) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
    %12 = neura.reserve : !neura.data<i64, i1>
    %13 = "neura.phi"(%12, %3) : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i64, i1>
    %14 = "neura.fadd"(%11, %7) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
    %15 = "neura.add"(%13, %5) : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i64, i1>
    %16 = "neura.icmp"(%15, %1) <{cmpType = "slt"}> : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i1, i1>
    %17 = neura.grant_predicate %15, %16 : !neura.data<i64, i1>, !neura.data<i1, i1> -> !neura.data<i64, i1>
    neura.ctrl_mov %17 -> %12 : !neura.data<i64, i1> !neura.data<i64, i1>
    %18 = neura.grant_predicate %14, %16 : !neura.data<f32, i1>, !neura.data<i1, i1> -> !neura.data<f32, i1>
    neura.ctrl_mov %18 -> %10 : !neura.data<f32, i1> !neura.data<f32, i1>
    %19 = "neura.not"(%16) : (!neura.data<i1, i1>) -> !neura.data<i1, i1>
    %20 = neura.grant_predicate %14, %19 : !neura.data<f32, i1>, !neura.data<i1, i1> -> !neura.data<f32, i1>
    "neura.return"(%20) : (!neura.data<f32, i1>) -> ()
  }
}

module {
  func.func @loop_test() -> f32 attributes {accelerator = "neura"} {
    %0 = "neura.constant"() <{predicate = true, value = 10 : i64}> : () -> !neura.data<i64, i1>
    %1 = "neura.grant_always"(%0) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %2 = "neura.grant_once"(%0) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %3 = "neura.constant"() <{predicate = true, value = 0 : i64}> : () -> !neura.data<i64, i1>
    %4 = "neura.grant_once"(%3) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %5 = "neura.constant"() <{predicate = true, value = 1 : i64}> : () -> !neura.data<i64, i1>
    %6 = "neura.grant_always"(%5) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %7 = "neura.grant_once"(%5) : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
    %8 = "neura.constant"() <{predicate = true, value = 3.000000e+00 : f32}> : () -> !neura.data<f32, i1>
    %9 = "neura.grant_always"(%8) : (!neura.data<f32, i1>) -> !neura.data<f32, i1>
    %10 = "neura.grant_once"(%8) : (!neura.data<f32, i1>) -> !neura.data<f32, i1>
    %11 = "neura.constant"() <{predicate = true, value = 0.000000e+00 : f32}> : () -> !neura.data<f32, i1>
    %12 = "neura.grant_once"(%11) : (!neura.data<f32, i1>) -> !neura.data<f32, i1>
    %13 = neura.reserve : !neura.data<i64, i1>
    %14 = "neura.phi"(%13, %2) : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i64, i1>
    %15 = neura.reserve : !neura.data<i64, i1>
    %16 = "neura.phi"(%15, %7) : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i64, i1>
    %17 = neura.reserve : !neura.data<f32, i1>
    %18 = "neura.phi"(%17, %10) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
    %19 = neura.reserve : !neura.data<f32, i1>
    %20 = "neura.phi"(%19, %12) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
    %21 = neura.reserve : !neura.data<i64, i1>
    %22 = "neura.phi"(%21, %4) : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i64, i1>
    %23 = "neura.fadd"(%20, %18) : (!neura.data<f32, i1>, !neura.data<f32, i1>) -> !neura.data<f32, i1>
    %24 = "neura.add"(%22, %16) : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i64, i1>
    %25 = "neura.icmp"(%24, %14) <{cmpType = "slt"}> : (!neura.data<i64, i1>, !neura.data<i64, i1>) -> !neura.data<i1, i1>
    %26 = neura.grant_predicate %24, %25 : !neura.data<i64, i1>, !neura.data<i1, i1> -> !neura.data<i64, i1>
    neura.ctrl_mov %26 -> %21 : !neura.data<i64, i1> !neura.data<i64, i1>
    %27 = neura.grant_predicate %23, %25 : !neura.data<f32, i1>, !neura.data<i1, i1> -> !neura.data<f32, i1>
    neura.ctrl_mov %27 -> %19 : !neura.data<f32, i1> !neura.data<f32, i1>
    %28 = neura.grant_predicate %10, %25 : !neura.data<f32, i1>, !neura.data<i1, i1> -> !neura.data<f32, i1>
    neura.ctrl_mov %28 -> %17 : !neura.data<f32, i1> !neura.data<f32, i1>
    %29 = neura.grant_predicate %7, %25 : !neura.data<i64, i1>, !neura.data<i1, i1> -> !neura.data<i64, i1>
    neura.ctrl_mov %29 -> %15 : !neura.data<i64, i1> !neura.data<i64, i1>
    %30 = neura.grant_predicate %2, %25 : !neura.data<i64, i1>, !neura.data<i1, i1> -> !neura.data<i64, i1>
    neura.ctrl_mov %30 -> %13 : !neura.data<i64, i1> !neura.data<i64, i1>
    %31 = "neura.not"(%25) : (!neura.data<i1, i1>) -> !neura.data<i1, i1>
    %32 = neura.grant_predicate %23, %31 : !neura.data<f32, i1>, !neura.data<i1, i1> -> !neura.data<f32, i1>
    "neura.return"(%32) : (!neura.data<f32, i1>) -> ()
  }
}

But to keep the correctness in case of meeting some CFGs that the current ctrl2data pass is unable to handle, we may need the ctrl-flow canonicalization to always take effect.

We do can eliminate some grant_always/grant_once if we use this pass.

[tancheng]

Right, I think we can have this pass, it LGTM. We can improve the mapping by prioritizing the operations on the critical path, and modeling the registers inside tile to relax this part:

dataflow/lib/NeuraDialect/Mapping/mapping_util.cpp

Lines 325 to 347 in a0cd122

	// The last link can be held from arrival_time to dst_time - 1.
	// TODO: We actually don't need to occupy the last link if the registers
	// within the tile can be explicitly represented.
	// https://github.com/coredac/dataflow/issues/52.
	bool all_free = true;
	assert(!current_path.empty() &&
	"Path should not be empty when checking last link");
	MappingLoc last_link = current_path.back();
	std::vector<MappingLoc> last_link_occupying;
	for (int t = current_time; t < deadline_step; ++t) {
	MappingLoc repeated{last_link.resource, t};
	last_link_occupying.push_back(repeated);
	if (!state.isAvailableAcrossTime(repeated)) {
	all_free = false;
	break;
	}
	}
	if (all_free) {
	path_out = current_path;
	path_out.insert(path_out.end(), last_link_occupying.begin(),
	last_link_occupying.end());
	return true;
	}

[ShangkunLi]

Completed in #86.