Skip to content

Depdencency DAG linearization as a transformation

As @mattwala pointed out today, linear schedules are much easier to do analysis on that DAG-y ones. On the other hand, many other things are easier on DAG-y ones (such as saying: XYZ needs to happen before ABC --- but I don't care when exactly).

Since a DAG can be used to represent a linear order, the scheduler could be made to be a transformation that spits out a valid linearization. Since barriers are now also representable in the IR, barrier insertion similarly should just be a transformation.

The schedule in the conventional format can trivially be extracted from a linearization, likely at the beginning of codegen.

A transformation that does the opposite of scheduling is also conceivable, i.e. "relaxing" the dependencies from a strict linear order to the minimum/a smaller set needed for correctness.