How to traverse a computational graph in an compiler pass?

[Ruizhe Zhao]

Hello,

I am trying to build a computational graph of the design I write within a compiler pass, and I might need some hints about how to do that.

The current plan that I have is to extend Traverse and build the computational graph while visiting blocks.

I'm just wondering whether this is a viable solution. Also, is there any existing utility for such purposes in the codebase?

Any comment will be highly appreciated!

(P.S. just want to confirm that Traverse doesn't visit blocks in topological order in terms of data-flow dependency, right?)

Best regards

Ruizhe

[David Koeplinger]

I'm a bit confused what you're trying to achieve. You say you want to build a computation graph while visiting blocks. Are you trying to insert your computational graph into an existing program?

If so, the canonical way for doing this is to write a Transformer (a type of Traversal that can modify a graph), and inline your graph wherever you want. If this is what you're trying to do, we can help you do this - there's a couple existing transformers that do exactly this.

The traversal order of a graph is based on program declaration order, which is one possible linearization of dataflow order. 

By default, traversals are done depth-first for hierarchical dataflow graphs, since this requires the least amount of state and is usually what you want to do in practice.

Standard traversals can be thought of as (roughly) tail-recursive (they typically visit the inner blocks after the outer block).

Transformers are (roughly) head-recursive (they visit the children before the outer node, since you need to know what your transformed children are before you can transform yourself).

[Ruizhe Zhao]

Hi David,

So sorry for the confusion. What I was trying to say is whether or not there is a computational graph we can access in a compiler pass.

There are three purposes:

1) I need to traverse Op in topological order. I have discovered that blocks can be visited, as you said, based on program declaration order. But I was not sure whether that is a data-flow order or not. Thank you for clarifying that.

2) I also intend to find a data path between two Op to analyze the data dependency, in which case I assume I might need to build a graph by myself? I've checked several Transformer and Traverse classes but haven't got one that has a similar objective.

3) At last, I might need to traverse Op in a reversed topological order. It seems that there is no such a Traverse trait/class that I can extend, and in this case, constructing a graph and traversing it backwards looks like an only option to me.

Please let me know if I've got anything wrong. Thanks!

Best regards

Ruizhe

[David Koeplinger]

Ok, I see what you mean now. Let me clarify a few things then:

1. Op - includes its data dependencies via `inputs` which can be inspected. 

2. Block - a single level of hierarchy with a sequence of statements (symbol + op pairs) in program declaration order

I should clarify that you can create a custom traversal direction without building a new graph if you absolutely need to. For instance, when visiting a block, you can visit its statements in reverse order.

In my experience there is never a need to build an entirely new graph. The existing program graph should have all of the information you need. 

Depending on what you're trying to do, there's several ways of inspecting data dependencies. See Spatial's AccessPatternAnalyzer, for example, which looks for localized patterns like (a * b) + (c * d) by pattern matching on inputs.

In other cases, reverse traversal actually isn't required at all, since you can flag nodes as you reach them, propagate those flags, and check to see if a node's inputs are flagged.

Even in the worst case, it's fairly simple to set up a traversal that would approximate reversed topological sort simply by traversing blocks in the reverse order like I mentioned. Building a new graph should absolutely be avoided.

It would help here to know more details about what analysis you're trying to achieve. I don't know how much compiler experience you have, but it sounds like there's a good chance that the solution you're thinking of is much more complicated than it needs to be.

[Ruizhe Zhao]

Hi David,

Thank you so much for your detailed explanation.

On Friday, 26 April 2019 22:09:37 UTC+1, David Koeplinger wrote:

Ok, I see what you mean now. Let me clarify a few things then:

1. Op - includes its data dependencies via `inputs` which can be inspected. 

2. Block - a single level of hierarchy with a sequence of statements (symbol + op pairs) in program declaration order

I did misunderstand these concepts. I kind of mixed Op with Block.

 

I should clarify that you can create a custom traversal direction without building a new graph if you absolutely need to. For instance, when visiting a block, you can visit its statements in reverse order.

In my experience there is never a need to build an entirely new graph. The existing program graph should have all of the information you need. 

I think this part is what I'm not sure about. To my understanding, we can only define what to do with a single Block, or a (Sym, Op) pair, in Traverse/Transformer by visit or transform. What if I want to perform some operations across multiple Ops or Blocks? Should I first dissect the algorithm into what to perform on each Op or Block? I will go with this approach and see whether it is possible or not.

 

Depending on what you're trying to do, there's several ways of inspecting data dependencies. See Spatial's AccessPatternAnalyzer, for example, which looks for localized patterns like (a * b) + (c * d) by pattern matching on inputs.

In other cases, reverse traversal actually isn't required at all, since you can flag nodes as you reach them, propagate those flags, and check to see if a node's inputs are flagged.

Even in the worst case, it's fairly simple to set up a traversal that would approximate reversed topological sort simply by traversing blocks in the reverse order like I mentioned. Building a new graph should absolutely be avoided.

Thank you for these tips. Those Analyzers in the codebase are quite informative to understand the mechanism.

It would help here to know more details about what analysis you're trying to achieve. I don't know how much compiler experience you have, but it sounds like there's a good chance that the solution you're thinking of is much more complicated than it needs to be.

Writing a compiler pass is not a familiar task to me. After reading your suggestions I have a rough idea about the design pattern of doing so. I will try to implement my stuff based on the current idiom. If I have any further specific question, I will let you know :)

Best regards

Ruizhe