How to Model "maybe" Side Effects

MLIR
1

Side effects of an op are described by the MemoryEffectsOpInterface.

We currently have the following memory side effects: MemoryEffect::Allocate, MemoryEffect::Free, MemoryEffect::Read, MemoryEffect::Write.

Side effects are also used in Transform dialect to described handle access/consumption.

I’d like to get your opinion about ops that may have a side effect. An example is bufferization.dealloc:

// Deallocate %m if %c.
bufferization.dealloc (%m : memref<?xf32>) if (%c : i1)

This op does currently not implement the MemoryEffectsOpInterface. I think the op should implement that interface and declare a MemoryEffect::Free side effect. However, that change breaks existing (old) code in the bufferization dialect, which assumes that if an op has the MemoryEffect::Free side effect, it will definitely free the memory.

As another example, consider a probabilistic allocation:

// With a probability of 40%: %0 = %m
// With a probability of 60%: %0 is a new allocation
%0 = test.probabilistic_alloc {p = 0.4 : f32} %m : memref<?xf32>

I think this op should declare a MemoryEffect::Allocate side effect.

The general questions are:

  • If an op declares a side effect, is that a “definite” or a “maybe” property?
  • Should it depend on the kind of side effect?
  • Should we extend the MemoryEffectsOpInterface such that effects can be declared with a degree of “certainty”? E.g., “MUST BE” or “MAY BE”.
2

I think we are just missing the may/must distinction in side effects, and should add it. The exact design remains to be discussed. Two straightforward options are (1) introduce a may/must bit in EffectInstance; (2) introduce MayWrite/MustWrite and similar kind distinctions. A bit less straightforward option is to use the attribute associated with each instance to specify may/must and, potentially, the condition of “may”. In absence of such a modeling, we should interpret the effects in the most conservative way, typically “may” for dataflow-like scenarios.

There is a very simple example from classical dependency analyses that we currently cannot differentiate:

// This is a "must" store, the value in %ptr is definitely
// overwritten on this control flow path.
llvm.store %value, %ptr
%v = llvm.load %ptr

// This has recursive side effects, so it has a store effect
// on %ptr. But it must be a "may" store because we may or
// may not enter the branch.
scf.if %cond {
  // This is a "must" store.
  llvm.store %another_value, %ptr
}
%v2 = llvm.load %ptr

in this scenario, we have to interpret the effect as “may” store, at which point the load-to-store forwarding for %v cannot be proven correct from memory effects alone. And we cannot interpret it as “must” store because that would allow for the incorrect load-to-store forwarding for %v2.