API reorganization around nodes / operations

[caleridas]

While working on generalizing the structural nodes (esp. lambda and gamma nodes), I noticed that the division of responsibilities between what is a "node" and what is an "operation" is not very clear. In my mind the difference should be:

• the "node" designates the behavior the object has wrt the graph itself
• the "operation" carries the semantic content of what is supposed to happen when this is executed
  This is mostly the case for everything that is of kind "simple_node" (which TBH I should have named "operation node" or similar), but is rather fuzzy for everything else.
  The division among node types should roughly be:
• "simple_node" is everything that does not contain a subregion
• "structural_node" are the only ones that contain subregions, and there are a finite number of structural node kinds
  This is today mostly enforced, except for delta::node which is structural but does not contain a region. It should be possible to turn it into simple_node, as delta::operation contains "almost everything", except for a few small bits.
  I would like to proceed towards the following organization:
• for everything that does not contain a region, it should be "simple_node" with everything describing the node carried in the attached operation; "simple_node" is not subclassed at all, only the operations attached
• have generic lambda, gamma, theta and phi nodes that are also not subclassed anymore -- but they as well can carry operation descriptors containing domain-specific information required for interpretation; so everything presently in llvm::lambda would move towards its operation
• Ideally, only the operations corresponding to "simple_node" should be derived from "operation". The information attached to lambda, gamma etc is of a different nature: the "evaluation semantic" is already defined by the structural node itself, but what backends need is backend-specific meta-information for the translation. I don't want to rename these from "operation" yet, but it should be made more clear in the end.
  To this end I would like to start restructuring towards the above goals while implementig the generic lambda. The transformation will not be completed in a single PR, but I would like to see whether the direction makes sense before committig something that goes into a direction not agreed upon.

@phate @haved @sjalander

[caleridas]

One additional thought regarding the information attached to llvm::lambda: I think that it would be better to distinguish between "lambda" (the callable object) and "function def" (the thing that binds a callable object to a symbol/name + linkage). Otherwise, anonymous lambdas are a bit odd as they should be ephemeral objects without any specified linkage etc. It is only after deciding to turn them into "real" functions (instead of e.g. inlining them at all use sites) that they even need a name, linkage etc.

[caleridas]

The additional reason why this might be the most sensible approach is to correctly handle visibility specifications. Consider this example:

void foo() __attribute__((visibility("default")));  // redundant, default visibility is always implied unless otherwise specified
void foo()  { std::terminate(); }
void bar() { foo(); }

If compiled using -fPIC, then bar is not allowed to resolve to calling std::terminate() directly, but most go through the symbol foo (it could be overridden by another symbol at runtime).

OTOH:

void foo() __attribute__((visibility("protected")));
void foo()  { std::terminate(); }
void bar() { foo(); }

allows that the call in bar to foo to resolve to the contents of foo.

[haved]

I can see the desire to only specialize operations, as we currently specialize a subset of the nodes, which makes copying nodes require a virtual function that the implementer needs to remember to override.

An alternative would be to make simple_node abstract, and force all operations to have corresponding subclasses of simple_node. This is the plan for argument and result, and I think it makes sense there. For nodes it might add a lot of work for not too much gain.

If I understand them correctly, classes like LoadNode and StoreNode do not add any extra state to the graph, but instead provide accessor functions and validation of nodes holding load and store operations. Without these subclasses, it becomes quite fiddly to access the different inputs and outputs of the nodes (accessing them by index).

If it was somehow possible to use accessor functions defined on the operations, to easily work with the nodes holding those operations, it might no longer be that useful to use custom subclasses of simple_node. Alternatively, LoadNode could be a thin wrapper holding a reference to a simple_node whose operation is a load. This wrapper would be constructed ad hoc, but without casting.

I am still not entirely sure about the role of operations in the pipeline. As far as I can tell they also exist outside of RVSDG, in something called TAC, and in some sort of intermediate control flow graph. This makes it a bit unclear if operations are primarily a way of specializing RVSDG nodes, or if operations are more general than that, with the RVSDG nodes being designed around holding them temporarily.

[caleridas]

Accessor functions within the operations are in my opinion the most sensible thing, validation should also go there -- that is, the "operation" should specify the signature that the node needs to follow, and then validation also ought to work generically. The amount of code duplication due to "copy" being on all of nodes, operations, inputs and outputs definitely is not helpful, particularly when attempting to reorganize things as everything is very interconnected and non-orthogonal.

API-wise I don't think that it is hugely problematic, consider presently this:

rvsdg::node* n = ...;
if  (auto load = dynamic_cast<const llvm::StoreVolatileNode>(n)) {
  auto io = load->GetIoStateInput();
  ...
}

when transferring this to the operation:

rvsdg::node* n = ...;
if (auto load =dynamic_cast<const llvm::StoreVolatileOp>(n->Op())) {
  auto io = load->GetIoStateInput(n);
}

which is really only marginally more verbose, but allows making all graph structures generic. While I am not fond of syntactic sugar, it would be entirely feasible to create wrapper to this extent:

rvsdg::node* n = ...;
if (auto load = n->operation_cast<const llvm::StoreVolatileOp>()) {
  auto io = load->GetIoStateInput(); // n implicitly bound by previous cast
}

In any case I think that it is better to make the data model clean and orthogonal than saving a few characters in typing.

[caleridas]

On the origin & relation of "nodes" and "ops": At the very beginning, nodes were simply subclassed, so every kind of distinct operation had its own node class. That turned out problematic because a) sometimes the code needs to "reason" about operations and their semantics decoupled from a specific graph node (i.e. compare if two nodes "represent the same operation", like add32, but independent of whether they both have the same inputs), b) sometimes it is necessary to create nodes conforming to a specific (known) operation to begin with (e.g. transform ((a+b)+c) to (a+(b+c)) - requires creating "different" add operations, but it is awkward to generically have nodes spawn new nodes). So, attaching the "semantic" to node is actually problematic, and keeping the nodes to just have the "graph connectivity" information generally simplifies everything.

[phate]

if (auto load =dynamic_cast<const llvm::StoreVolatileOp>(n->Op())) {
  auto io = load->GetIoStateInput(n);
}

I still fail to fully understand how this should work in terms of implementation? Does that not also mean that you would ultimately intermix the operations again with graph structures (exactly what you do not want)? I am fine to type a few characters more as long as I get something like the GetIoStateInput() functions instead of load->operand(2).

If I understand them correctly, classes like LoadNode and StoreNode do not add any extra state to the graph, but instead provide accessor functions and validation of nodes holding load and store operations. Without these subclasses, it becomes quite fiddly to access the different inputs and outputs of the nodes (accessing them by index).

Yes, that is exactly the reason.

If it was somehow possible to use accessor functions defined on the operations, to easily work with the nodes holding those operations, it might no longer be that useful to use custom subclasses of simple_node. Alternatively, LoadNode could be a thin wrapper holding a reference to a simple_node whose operation is a load. This wrapper would be constructed ad hoc, but without casting.

I fully agree with this.

I am still not entirely sure about the role of operations in the pipeline. As far as I can tell they also exist outside of RVSDG, in something called TAC, and in some sort of intermediate control flow graph. This makes it a bit unclear if operations are primarily a way of specializing RVSDG nodes, or if operations are more general than that, with the RVSDG nodes being designed around holding them temporarily.

This is a mix of history and lack of engineering time (and potentially some more reasons). Originally, operations held the semantics of concrete operations (add, load, etc.). These operations were then put in the RVSDG structure through nodes, giving the individual nodes meaning (there were no subclasses of nodes back then). This turned out not so great for implementing optimizations as no specific accessors were available. Thus, the implementations turned into casts all over the place and accessing operands via indices. As this became an unreadable mess, I started to subclass the nodes for concrete operations to get easy accessors, creating a parallel world (i.e. subclassing operations and nodes).

Aside from the RVSDG, we have the control flow/call graph structure, which is used as a stepping stone in order to get into an RVSDG. There we have ThreeAddressCodes (TAC) that also hold the (simple) operations. From these TACs, the operations are then taken when creating the RVSDG simple nodes. Thus, operations serve as carrier of the semantics, while the other entities only decide in which graph structure these operations are utilized. TLDR: RVSDG (and TAC) nodes were designed to hold them in order to give these entities semantic meaning, but the practical necessity of working with the RVSDG nodes combined with lack of engineering time lead to this parallel world of also subclassing simple nodes.

[caleridas]

Thanks, that sounds that we are overwhelmingly in agreement.

Regarding API, how about this then:

rvsdg::node* n = ...;
if (auto load = n->operation_cast<const llvm::StoreVolatileOp>()) {
  auto io = n->output(n->IoStateOutput());
}

This way, operations-level API is entirely decoupled from graph structure -- ops are responsible for characterizing inputs/outputs.

The return of n->IoStateOutput() might be just an index, but could also be overloaded to be a "descriptor" instead -- e.g. one could make it something like:

template<typename T> struct OutputDescriptor { size_t index; }

and use the parameter T to coerce the returned value into something specific (via checked_cast).

It's "marginally" more than deriving nodes, but IMHO it should be acceptable. WDYT?

[phate]

I think that I am convinced on the simple node part of your proposal, i.e., getting rid off all simple_node subclasses and expressing the accessors as discussed above. This would remove quite a bit of duplicated code and should not require too much of refactoring as a lot of this is already there.

I am not so convinced about the structural node part of your proposal yet. Personally, I think that it could work, but I do not fully see all the consequences of it yet. I would need to mull a bot more about this.

[phate]

This is mostly the case for everything that is of kind "simple_node" (which TBH I should have named "operation node" or similar), but is rather fuzzy for everything else.

I believe that I am at fault with the naming here.

"simple_node" is everything that does not contain a subregion

Yes.

"structural_node" are the only ones that contain subregions, and there are a finite number of structural node kinds
This is today mostly enforced, except for delta::node which is structural but does not contain a region. It should be possible to turn it into simple_node, as delta::operation contains "almost everything", except for a few small bits.
I would like to proceed towards the following organization:

This is not true. The delta node is a structural node and contains a single region. Please see its constructor and how it invokes the structural_node constructor with argument 1 as last parameter. The delta node needs to stay a structural node as its subregion can contain other simple nodes.

for everything that does not contain a region, it should be "simple_node" with everything describing the node carried in the attached operation; "simple_node" is not subclassed at all, only the operations attached

I am fine with this as long as you do give me a way to access the individual inputs/outputs of a simple node. I do not want to write:

simple_node * loadNode = ...
auto addressOperand = load->operand(0);

but rather (as it is right now):

LoadNode * loadNode = ...
auto addressOperand = load->GetAdressOperand();

In other words, please do not make me remember which operand is at which index, but give me concrete accessors to individual (groups) of inputs/outputs. Everything else simply becomes a mess of indices that is unreadable and requires intricate knowledge of the individual operations and their type signatures.

have generic lambda, gamma, theta and phi nodes that are also not subclassed anymore -- but they as well can carry operation descriptors containing domain-specific information required for interpretation; so everything presently in llvm::lambda would move towards its operation

What about the hls::loop_nodes from the HLS dialect? I am okay with this, as long as you provide me a convenient (and intuitive way) to access the individual inputs/outputs/etc. of these specific nodes. I do not want to iterate through all the lambda subregion arguments and filter out myself which of those are the function arguments (and not the input arguments). Rather, I want accessors to them such that I only get these.

Ideally, only the operations corresponding to "simple_node" should be derived from "operation". The information attached to lambda, gamma etc is of a different nature: the "evaluation semantic" is already defined by the structural node itself, but what backends need is backend-specific meta-information for the translation. I don't want to rename these from "operation" yet, but it should be made more clear in the end.

I agree with you. The plan in my head (so far) was to remove the operations for structural nodes altogether, as they do not really serve a purpose (as compared to operations for simple nodes). The semantics is already in the structural node.

but I would like to see whether the direction makes sense before committig something that goes into a direction not agreed upon.

I really appreciate that. Thanks a lot!

One additional thought regarding the information attached to llvm::lambda: I think that it would be better to distinguish between "lambda" (the callable object) and "function def" (the thing that binds a callable object to a symbol/name + linkage). Otherwise, anonymous lambdas are a bit odd as they should be ephemeral objects without any specified linkage etc. It is only after deciding to turn them into "real" functions (instead of e.g. inlining them at all use sites) that they even need a name, linkage etc.

Makes sense, I can get behind this.

[caleridas]

After trying this out on gamma, theta and lambda, I have a clearer picture and more specific proposal on API structure.

Inputs & outputs: There really exist only two classes, namely "inputs / outputs to nodes" and "results / arguments" of regions. So, when code needs to handle an input or output of unknown kind, they should canonically proceed like this:

if (auto node = output->GetOwningNode()) {
  // now try to cast node into what you want to handle, and proceed further
} else if (auto region = output->GetOwningRegion()) {
  // now can inspect the type of region, try casting node owning the region into something interesiting
  // -- e.g. it may the subregion of a gamma
} else {
  std::terminate(); // that's an impossibility
}

presently, there is a bit of a mixture of casting variously the output type or the node type, and I think this would benefit from being made regular and uniform throughout the code base. In principle one could also write convenience helpers to "flatten" the above into a single if-cascade again:

if (auto node = IsOutputOfNode<GammaNode>(output)) {
  // we now know that it is output of gamma node, and have also obtained the
  // node; can proceed further
} else if (auto node = IsArgumentOfSubregion<GammaNode>(output)) {
  // we now know that we are in a subregion of a gamma node, and have
  // obtained the parent node of this region
} else if (auto node = IsOutputOfNode<CallNode>(output) {
  // handle call etc.
}

Routing things into and out of structural nodes as well as tracing paths through structural nodes: When routing a variable e.g. into a theta node, one needs to have 1. the input into the theta, 2. inside the theta region the pre-loop value, 3. inside a theta a way to assign a new post-loop value to it, and 4. get the loop exit value for later code. Currently, this is accomplished by add_loopvar returning an input through which caller then steps to get what it needs. An IMHO cleaner API would grant access to everything caller would like:

/**
 * \brief Description of a loop-carried variable
 *
 * A loop-carried variable from the POV of a theta node has
 * multiple representations (entry, pre-iteration,
 * post-iteration, exit). This structure bundles
 * all representations of a single loop-carried variable.
 */
struct ThetaNode::LoopVar
{
  /**
   * \brief Variable at loop entry (input to theta).
   */
  rvsdg::input * entry;
  /**
   * \brief Variable before iteration (input argument to subregion).
   */
  RegionArgument * pre;
  /**
   * \brief Variable after iteration (output result from subregion).
   */
  RegionResult * post;
  /**
   * \brief Variable at loop exit (output of theta).
   */
  rvsdg::output * exit;
};

so providing this as a "uniform representation" to handle aspects of a specific loop var. Using this in the places where required also makes it clear that the code is presently handling a loop variable as a whole, and retains its context.

Then, to add a loopvar:

ThetaNode::LoopVar
ThetaNode::AddLoopVar(rvsdg::output * origin);

returns the full thing. This actually satisfies >95% of the use cases where one presently needs to resolve "the other pieces of the loop variable, given just an input".

For code stepping and tracing through loops, it should also handle similarly:

// Given an input into the theta region, get the full description of the entire loop variable.
ThetaNode::LoopVar
ThetaNode::MapEntryToLoopVar(rvsdg::input * input);

So there is a uniform way of handling this.

@phate @haved WDYT?

[haved]

I think the API for getting the node/region for inputs and outputs is nice. The naming is perhaps a bit misleading in

auto gammaNode = IsOutputOfNode<GammaNode>(output);

since the name Is... does not convey returning a node.
One alternative could be

// When you are not sure of the type. T can be defaulted to `rvsdg::node`
if (auto gammaOutput = output->TryGetOwningNode<GammaNode>()) {
  // Do something
}

// When you are sure, asserts internally when asserts are enabled. Returns a reference
auto & gammaOutput = output->GetOwningNode<GammaNode>();

For reference, the current API is this:

// Either cast the output to node_output and use the node() method
if (auto nodeOutput = dynamic_cast<node_output>(output)) {
  auto gammaNode = dynamic_cast<GammaNode>(nodeOutput->node());
  // Do something
}

// Or we also have the slightly nicer alternative using the static node() method
auto node = rvsdg::output_node::node(output);
auto gammaNode = dynamic_cast<GammaNode>(node);
// Do something

Regarding the loop variables of theta nodes, I think returning a struct is quite nice. The return value is a bit larger than returning exactly what you want, but it makes the API very easy to use, and aids discoverability. If all the functions returning the struct are defined in the header, the compiler should be able to inline it and ignore unused fields.

Lastly, regarding operations and nodes, I think the nicest API might be what Nico wrote

if (auto loadOp = dynamic_cast<LoadOperation>(&node.operation()) {
  auto & address = loadOp->GetAddressOperand(node);
}

We could make the first line a bit nicer by adding a helper if we want to

if (auto loadOp = node.TryGetOperation<LoadOperation>()) { ... }

The last part can be implemented by adding methods to LoadOperation like:

rvsdg::input &
LoadOperation::GetAddressOperand(rvsdg::simple_node & node) {
    JLM_ASSERT(node.operation() == this);
    return node->input(0);
}

One could argue that introducing methods like this adds some node-related implementation to the operation class, which sort of breaks the "hierarchy" where operations are independent of the concept of nodes, and can exist in other contexts, such as is the TAC. We could do some funky template magic to abstract away nodes into "list of operands and outputs we can index into", but I'm not sure it is worth the complexity.

@phate @caleridas WDYT?

[phate]

I agree with Håvard here: auto gammaNode = IsOutputOfNode<GammaNode>(output); is a little bit misleading. I prefer the TryGetOwningNode<>() and GetOwningNode<>() version from him.

I am for the LoopVar struct as I think this will be nice. However, I do not like the naming entry, pre, post, and exit. I rather want input, argument, result, output.

One could argue that introducing methods like this adds some node-related implementation to the operation class, which sort of breaks the "hierarchy" where operations are independent of the concept of nodes, and can exist in other contexts, such as is the TAC.

This is a fair point, but we somehow need a mapping from operation specific knowledge to concrete graph structures. The operation itself might not be the right place for it though.

Otherwise, I have not much to say except that it all looks fine to me.

[caleridas]

Thanks for the input -- on the naming regarding Try... yes I agree that this is better, generally more attached to the concept rather than the names, will also draft a PR to introduce this as API.

On LoopVar: I am not sure it is helpful to have an "input" of type "input" an "argument" of type "argument" etc. as this is redundant -- what I tried with the names entry/pre/post/exit is to clarify the roles they play from the POV of the loop rather than their types (maybe preIter/postIter would be more precise). For anyone familiar with the details of the implementation, "loop result" may make sense, but for anyone else they would most certainly be more likely to interpret this as the "final" value computed in the loop (i.e. the "exit value"). Again, I am not attached to specific names but would think that it is preferable to have "intent" rather than "type" in the names.

Regarding mapping in ops/nodes -- I think for structural nodes I would put them into the nodes for now as I am not yet certain whether/what will go into ops there (I could see lambda op providing compilation-specific attributes, e.g. calling convention). This is in contrast to simple_node where semantic is only encoded in ops -- admittedly, adding graph-specific things into ops is somewhat in violation of the "layering", but not so bad as that it would stretch the design beyond its breaking point.