[LLVMdev] doubts about Instruction Selection and Scheduling

[Jim Grosbach]

On Apr 8, 2011, at 11:03 AM, Lucas Silva wrote:

> Hello,
> 
> I'm working on the text of my Master's Thesis and I have some doubts:
> 
> 1. What algorithm is used in Selection Instruction ? What is the input ?

It's a custom algorithm unique to LLVM, as far as I know. The input is a DAG, and generally speaking it's a greedy algorithm based on pattern matching. See llvm/lib/CodeGen/SelectionDAG for details on the data structure and the associated machinery for how it's used for instruction selection.

> 2. Where is described how the variations of List Scheduling work, in
> -pre-RA-sched phase ?

llvm/lib/CodeGen/ScheduleDAG.cpp and associated (and similarly named) files.

> -pre-RA-sched                           - Instruction schedulers
> available (before register allocation):
>    =source                               -   Similar to list-burr but
> schedules in source order when possible
>    =list-tdrr                            -   Top-down register
> reduction list scheduling
>    =list-burr                            -   Bottom-up register
> reduction list scheduling
>    =list-td                              -   Top-down list scheduler
>    =fast                                 -   Fast suboptimal list scheduling
>    =default                              -   Best scheduler for the target
> 
> 
> 3. What is algorithm executed in -post-RA-scheduler - Enable
> scheduling after register allocation ?
> 

llvm/lib/CodeGen/PostRASchedulerList.cpp

In addition to the source files, I would also suggest searches of the mailing list archives of llvmdev. There's some history of how things developed there.

Regards,
-Jim