[LLVMdev] LLVM's Pre-allocation Scheduler Tested against a Branch-and-Bound Scheduler

[Andrew Trick]

On Sep 29, 2012, at 11:37 AM, Evan Cheng <evan.cheng at apple.com> wrote:

>> 
>> 2. The BURR scheduler on x86-32 appears to set all latencies to one (which makes it a pure RR scheduler with no ILP), while the ILP scheduler on x86-64 appears to set all latencies to 10 expect for a few long-latency instructions. For the sake of documenting this in the paper, does anyone know (or can point me to) a precise description of how the scheduler sets latency values? In the revised paper, I will add experimental results based on precise latency values (see the attached spreadsheet) and would like to clearly document how LLVM's rough latencies for x86 are determined.
> 
> I don't think your information is correct. The ILP scheduler is not setting the latencies to 10. LLVM does not have machine models for x86 (except for atom) so it's using a uniform latency model (one cycle).

Evan's description is precise. Everything is one cycle, unless it is 10 cycles ;) But it's easy to reconfigure to use itineraries, as I guess you've done.

>> 
>> 3. Was the choice to use rough latency values in the ILP scheduler based on the fact that using precise latencies makes it much harder for a heuristic non-backtracking scheduler to balance ILP and RP or the choice was made simply because nobody bothered to write an x86 itinerary?  

> No one has bothered to write the itinerary.

I recently committed infrastructure that allows machine models to be developed incrementally, at the level of detail appropriate for the processor. I have a feeling we will start to see models begin to evolve for x86 processors very soon. The framework is documented in TargetSchedule.td and you're welcome to contribute.

The only feature that I still plan to implement is the ability of a machine model to specify that it is derived from another. It will be trivial to add though when the time comes.

>> 4. Does the ILP scheduler ever consider scheduling a stall (leaving a cycle empty) when there are ready instructions? Here is a small hypothetical example that explains what I mean:
>> 
>> Suppose that at Cycle C the register pressure (RP) is equal to the physical limit and all ready instructions in that cycle start new live ranges, thus increasing the RP above the physical register limit. However, in a later cycle C+Delta some instruction X that closes a currently open live range will become ready. If the objective is minimizing RP, the right choice to make in this case is leaving Cycles C through C+Delta-1 empty and scheduling Instruction X in Cycle C+Delta. Otherwise, we will be increasing the RP. Does the ILP scheduler ever make such a choice or it will always schedule an instruction when the ready list is not empty?

The standard ILP scheduler does not have a "ReadyFilter" so instructions are inserted in the ready queue the moment their predecessors are scheduled. So, yes, it will effectively "impose stalls" to reduce register pressure. Note that things work differently with an itinerary though. And the answer will depend on how you've written the itinerary.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121004/9fff170c/attachment.html>