General system for marking operations as unique per node

[haved]

I think it makes sense to define a clear way for operations to mark themselves as "unique per invocation".

This comes up after considering the following:

• In Improve check in NodeHoisting transformation #1422, @phate requests more precise information about which operations it is safe to hoist
• Add IOState to MallocOperation #1492 added an IOState to the MallocOperation to prevent hoisting. The same issue technically also applies to AllocaOperation, but I would really like to avoid sequentializing allocas with IO.
• The AllocaOperation and MallocOperation has hacky implementations of operator ==() to prevent Common Node Elimination from collapsing distinct alloca nodes into a single node.

What I mean by "unique per invocation" is that two instances of the operation produce unique results, even if they take identical inputs. This is what effectively happens with alloca and malloc. Marking an operation as unique would disable Common Node Elimination, and prevent hoisting out of loops (as each iteration has its own invocation of the operation). Hoisting out of gamma nodes is still fine, assuming all regions contain the operation, as the total number of invocations does not change.

The only other way I see to represent this in current RVSDG is to route states through the operations, but this has the downside of also forcing the operations to be sequentialized. The state also needs to come from somewhere, and it should not be the IO state. Routing states also entail special handling when doing Dead Node Elimination, as the state should not be able to keep the operation alive.

What do you think about having such a "trait" on operations, @caleridas? In practice it would be a virtual method on the Operation class.

Is there a name for operations that only have the side-effect of producing a unique result each time, but otherwise being "stateless"?

[caleridas]

I think that this path forward is going to be very problematic and cause numerous downstream problems. I would strongly urge to rather add "attributes" to the nodes that you want to distinguish.

Operations do not necessarily need to be sequentialized, this is a question of modelling. IMHO the "correct" way to deal with alloca (for "program-stati local variables", i.e. those things that are defined as variables as opposed to true "dynamic" alloca) to have:

• a stackframe state
• split this stackframe state into all the variables you want to have + residual
• join them back together at stackframe cleanup

the "interim" step is to

• have stackframe state
• one alloca "splits off" the variable you want to have + residual state
• and then the next alloca becomes formally sequentialized

from this it is then a question of recognizing that the underlying op is associative i.e. split-of-split can be rearranged

the solution to avoiding sequentialization IMHO is not to mess with DNE and create "hidden" state (which is what you effectively doing with this "unique" notion -- it is trying to tell the compiler: "there is state that you cannot see"), but make the state explicit. anything else is eventually I think going to destroy the very property that makes rvsdg useful to begin with.