Automatic Schedule Generation/Explication

[od0x0]

The version of caiman with the old scheduling language had a fairly rudimentary and predictable schedule generator that operated by tracking which values were present on which device, and creating a copy somehow as late as possible if it was not present when a computation needed it. I had to disable this when I created the new scheduling language because it was added surface area that needed to change. It's essential for the caiman story that we have a component that can take us from no schedule to some functional (even if not performant) schedule. Partial schedule to full schedule (like the old explicator) would be nice, but is not essential for a 1.0. Optimal schedule generation is a non-goal at this time. Predictability is much more important.

This can be implemented in the caiman backend as a pass before codegen the way the old explicator was, but it could also be implemented external and operate as an IR to IR transform before it gets loaded into caimanc.

For a v1, I would start by having pipeline definitions with the minimal necessary type information at the boundary but no concrete funclets, then generating the implementation via a backwards traversal through the associated value funclets. The algorithm should be very similar to linear scan register allocation (values are traditional SSA registers and slots are basically physical registers/spill slots with extra type checking).

The new scheduling language has timeline and spatial funclets that capture different aspects of the schedule, in addition to the ScheduleExplicit funclets. For a predictable schedule generation from partial schedules in a v2, these would probably need to be combined as a ScheduleImplicit funclet that allows partial specification and explication of all three simultaneously. Alternatively, the explicator could clone/instantiate and explicate the trio of funclets simultaneously.