Open Kixiron opened 2 years ago
Representing and manipulating expressions is the easy part in any compiler. The paper you sent is about very low level representations, suitable for compiler back-ends. We need a representation in the front-end. How do you represent type declarations, generics, functions, literals? Are the nodes typed? What are the types of nodes supported? How is the IR traversal done? Is there a generic infrastructure for that?
This isn't for the frontend, it's for the backend optimization of programs
@Kixiron , are you thinking of using an existing RVSDG crate?
I don't think that this is a good representation for use as the main IR. The main IR should be a tree-like representation that is more abstract. A dataflow graph representation should be built from the IR when needed, used to analyze and optimize the code by generating a new IR, and then discarded.
Are you thinking of using an existing RVSDG crate?
At present there aren't any, I'm currently making one
I don't think that this is a good representation for use as the main IR.
This is an optimization IR, it's not strictly tied to the dataflow semantics of our target. It brings along many benefits to "normal" optimization as well as our domain specific needs
Is the plan to use equality-saturation-based optimization?
That's a definite possibility, but one I need to investigate further
Having said that, I think we need a more detailed design before implementing anything. In particular, what would the rewrite rules and a rule engine for an optimizer based on such a hybrid graph look like?
And also what are the exact node types in the graph? E.g., our surface syntax consists of operators like filter
, map
, join
, etc. Internally, we want additional nodes like arrange
, distinct
, and consolidate
. In addition, we may want to split the program into multiple dataflow graphs. Do these correspond to nested regions?
And also what are the exact node types in the graph?
I'd probably use the lower leveled representation of things so that we can share as much work as possible, ex. only arranging any given stream once instead of re-arranging it multiple times
Do these correspond to nested regions?
Yep, each self-contained subgraph would be contained within its own region, ditto with recursive/iterative dataflow scopes
Background:
As an intermediate representation we should use the RVSDG to represent both the timely-level dataflow graph and the inter-operator expressions (map functions, for instance). Using this unified representation to encompass both aspects of ddlog programs brings a number of benefits:
relation.filter(|_| false) => empty_relation()
and.map(|_| 10).filter(|x| x == 10) => .map(|_| 10)
For those unfamiliar, the RVSDG is a way to represent programs as an abstract graph with only four distinct components:
1
,add 1, 2
ormap
if ... { ... } else { ... }
and the theta node represents aloop { ... }
add
node having two incoming value edges from a1
and a2
nodeprint()
calls being sequential relative to each other (this is an important note as the RVSDG is inherently unstructured). Effect edges won't be used very much within the ddlog compiler, but they do have an important, albeit sparse, role to play in itWith these four primitives we can express programs in a very abstract and inherently normalizing way. That is to say, many different source language programs can (and will) look identical once translated into an RVSDG due to it's inherent lack of ordering. Instead of
add 1, 2; add 2, 3
andadd 2, 3, add 1, 2
being seen as two separate programs, the RVSDG simply seesThis (as mentioned before) also comes into effect when analyzing the dataflow graph as a whole since both the nodes of the dataflow graph and the expressions they contain can be unified, cutting the total program's potential runtime in half:
Ignoring the questionable nature of this program, the raw translation of this program into a graph would render this
From which we can see that the map operation is trivially reducible, that's duplicated effort we've done and we can remove it
That's a rather trivial example that could definitely be optimized further (say, by turning multiple filters on one relation that are then concatenated into a single filter), but it expresses the intent quite nicely.
Another optimization I mentioned was dead code elimination, with two simple rules we can do all the DCE on dataflow graphs that we need to
Both of these graphs would be considered dead code
So to wrap things up, I believe that the RVSDG is an optimal representation for compiling and optimizing our dataflow graphs and the expressions within them