Questions about TurboFan IR

[Seungwan Kwon]

Hi all,

I'm doing some research on the turbofan of the V8, and I have a few questions:

1. Is the order of execution of the turbofan IR (Sea of node) unique?

2. If not unique, what is the reason?

3. Is there any property that holds in terms of uniqueness? (e.g. it is preserved in block units.)

4. Are there cases where there is no side-effect edge between two operations where side-effect actually exists?

Thanks.

[Jakob Kummerow]

Also asked here: https://stackoverflow.com/questions/70003663/questions-about-the-uniqueness-of-turbofan-ir-execution/

--

[Andreas Haas]

Hi,

On Wed, Nov 17, 2021 at 4:42 PM Jakob Kummerow <jkum...@chromium.org> wrote:

Also asked here: https://stackoverflow.com/questions/70003663/questions-about-the-uniqueness-of-turbofan-ir-execution/

On Mon, Nov 15, 2021 at 3:20 PM Seungwan Kwon <seungw...@prosys.kr> wrote:

Hi all,

I'm doing some research on the turbofan of the V8, and I have a few questions:

1. Is the order of execution of the turbofan IR (Sea of node) unique?

It's not clear what "unique" means here. The order of execution (actually called the schedule) may be deterministic, because testing is easier if you can reproduce schedules. However the schedule may not be stable. It could be that you add one completely independent node, and the whole schedule changes.

All nodes you want to be ordered have to be connected by some kind of edge. All nodes that are not connected directly nor indirectly can get ordered either way.

 

2. If not unique, what is the reason?

I think the better question is, why should it be unique? As I mentioned above, the schedule may be deterministic to allow better testing. The idea of a sea of node compiler is to find an optimal schedule that respects all edges in the graph. If there are multiple optimal schedules, the compiler can pick any of them.

 

3. Is there any property that holds in terms of uniqueness? (e.g. it is preserved in block units.)

I'm not sure what you mean. You can expect that all edges in your graph will be preserved, but all nodes that are not connected, neither directly nor indirectly, may get scheduled either way.

 

4. Are there cases where there is no side-effect edge between two operations where side-effect actually exists?

Are you asking if there are implicit edges in the graph that get respected in the graph schedule? I'm not directly involved in the implementation of the graph scheduler, but I would expect that that is not the case. It would be much cleaner to just add an edge to the graph and not add this kind of special handling to the scheduling algorithm. 

I have not been involved directly in the development of TurboFan, so features may have been added that affect "uniqueness". But in my understanding, a deterministic schedule for a given graph is the best you can get.

Reminds me, if you have a fully-connected graph, the schedule will be unique, as there exists only one correct schedule.

--

Andreas Haas

Software Engineer

ah...@google.com

Google Germany GmbH

Erika-Mann-Straße 33

80636 München

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Diese E-Mail ist vertraulich. Falls sie diese fälschlicherweise erhalten haben sollten, leiten Sie diese bitte nicht an jemand anderes weiter, löschen Sie alle Kopien und Anhänge davon und lassen Sie mich bitte wissen, dass die E-Mail an die falsche Person gesendet wurde.

    

This e-mail is confidential. If you received this communication by mistake, please don't forward it to anyone else, please erase all copies and attachments, and please let me know that it has gone to the wrong person.