Lucas Silva
2011-Apr-08 18:03 UTC
[LLVMdev] doubts about Instruction Selection and Scheduling
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 ? 2. Where is described how the variations of List Scheduling work, in -pre-RA-sched phase ? -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 ? -- Lucas da Costa Silva @landir
Jim Grosbach
2011-Apr-08 19:00 UTC
[LLVMdev] doubts about Instruction Selection and Scheduling
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
Apparently Analagous Threads
- [LLVMdev] Instruction Scheduling
- [LLVMdev] LLVM x86 Code Generator discards Instruction-level Parallelism
- [Newbie Question] Compute a schedule region's scheduled cycles.
- [LLVMdev] Integrated instruction scheduling/register allocation
- [Newbie Question] Compute a schedule region's scheduled cycles.