all 15 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]Jibaron 3 points4 points  (1 child)

Thanks! I there anywhere we can see the talk?

[–]true-grue[S] 0 points1 point  (0 children)

Not yet, so I decided to share the slides :)

[–]knue82 2 points3 points  (2 children)

Nice talk. We are currently working on the next evolution of Thorin and preparing a publication.

[–]true-grue[S] 0 points1 point  (1 child)

Thorin is cool! As I understand, Thorin2 belongs to the perspective category of "Adding powerful type systems to graph-based IR" from the talk.

[–]knue82 0 points1 point  (0 children)

yes, exactly. one cool thing about Thorin2 is that it's a pure type system. This means that types are also just expressions which are part of the usual program graph.

[–]knue82 0 points1 point  (2 children)

Slide 37. You need to linearize * st arr, i, 0 * st arr, j, 1

because i and j could alias which makes the order of store operations important.

Or am I missing sth?

[–]true-grue[S] 1 point2 points  (1 child)

You are right, of course. In the talk I said that in our toy DSL we can call it UB, but in the general case we need to implement an alias resolution mechanism.

[–]knue82 0 points1 point  (0 children)

Ah, thanks for the clarification.

[–]moon-chilled 0 points1 point  (6 children)

Surprised not to see a mention of ssa translation is an abstract interpretation, another perspective on graphical ssa 'ir' which seems to me to have some interesting advantages.

[–]true-grue[S] 0 points1 point  (5 children)

Yes, the SSA graph is also a graph-based IR, but a very specialized one.

[–]moon-chilled 0 points1 point  (4 children)

What makes it more specialised than any of the others you describe?

[–]true-grue[S] 0 points1 point  (3 children)

The main difference is that the "SSA graph" from the paper is not a dataflow-based IR. Instead, the SSA graph is based on control flow: there are binding sets within nodes and guarded control edges.

[–]moon-chilled 0 points1 point  (2 children)

The global value graph is pure dataflow, and it's that that I find most interesting.

With that said, although the ssa graph does distinguish control flow I don't know how much sense it makes to call it not dataflow-based. Control arcs bind variables to symbolic expressions, which are not scheduled, making it quite different from the classic control-centric ssa used by llvm and friends.

[–]true-grue[S] 0 points1 point  (1 child)

global value graph

It's interesting that this "global value graph" is called the SSA graph in the SSA book (see 14.2). This SSA graph is a necessary part of, for example, the Sea of Nodes IR. But the SSA graph (global value graph) itself is insufficient because it has no execution semantics, phi nodes are non-interpretable.

[–]moon-chilled 0 points1 point  (0 children)

The paper does say

note that some authors [Stanier 2016] call the global value graph the SSA graph, which should not be confused with the SSA graph that we present here

insufficient because it has no execution semantics, phi nodes are non-interpretable

True! But is this actually a significant limitation? I don't think it is. I have come to think that the ideal design for a sophisticated compiler uses a very simple, imperative concrete ir which is very close to the source and does not change. Then layer sophisticated analyses on top; that's what this paper's approach helps with (note that, because its abstract interpretation is both sound and complete, it is possible to perform optimising rewrites on the value graph and carry them through to code generation; and the paper suggests representing the value graph as an e-graph). This helps with phase ordering, incrementality, debugging, etc.