[LLVMdev] Scheduler Roadmap

[dag at cray.com]

Sergei Larin <slarin at codeaurora.org> writes:

> Ideally scheduler itself should be able to produce bundled code (since
> it has the best picture of machine resources and instruction stream)

Ok, that's what I was imagining.

>> How so?  Isn't the bundle representation supposed to be fairly
>> transparent to passes that don't care about it?

> We also lack API to move MIs between BBs in presence of bundles. 

Why would you want to do that?  Wouldn't you just move bundles across
BBs?  A rebundling pass could split out the individual MIs you want to
move if there are dependence issues.

> Live Intervals obviously do not work with bundles...

I don't see that as obvious.  I'd been imagining LiveIntervals to use a
generic bundle interface to get at the defs and uses of trhe MIs inside
it.  Is it just a matter of not having those interfaces yet?

> Two, semantics (dependencies) within a bundle are parallel (think { r0
> = r1; r1 = r0 } in serial vs. parallel semantics) and if a pass needs to
> "understand" it, it will need to be "taught" how to do it. 

But if a pass need to know about that it is a special bundle-aware pass
and I wouldn't expect the bundle to be transparent.

> This is where incremental rebundling might come in handy. Fortunately
> we currently do bundling fairly late, so it is not an issue yet.

Right, but I'm glad you're thinking ahead.  :)

> [Larin, Sergei] The core of bundler is the DFA state machine, which also
> _must_ be a part of any VLIW scheduler, so in my Hexagon VLIW "custom"
> scheduler (I actually have two - SDNode and MI based) I virtually __create__
> bundles, but discard them at the end of pass, only to recreate them again
> later in the standalone bundler. Second attempt is riddled with additional
> false dependencies (anti, output etc.) introduced by the register
> allocation, so bundling quality is affected.

They're only "false" in the sense of the register names being fixed at
that point.  It's essentially the same problem as trying to schedule for
latency after register allocation.  You're constrained by hazards
imposed by a reduced namespace.  If the scheduler-created bundles were
maintained, then the register allocator would have less freedom to
assign registers.  It's a classic scheduler/regalloc tradeoff.  Bunding
is "just" another fun detail, I think.  :)

>> We could also use a global scheduler in the medium-term though it's not
>> absolutely critical.  A nice clean infrastructure to support global
>> scheduling with multiple heuristics, etc. would be very valuable.  It
>> would also be a lot of work.  :)
>
> [Larin, Sergei] I will need to start doing this very soon to meet my
> performance goals, but extensive discussion and generic support might take
> some time to crystallize... but indeed critically needed.

Yes, I fully expect it will take a while to mature.  I'm really excited
that you're starting to look at this!

                               -Dave