Instruction scheduling

[P. Pavan Kumar]

Dear sir,
       I want to know details of instruction scheduling pass of GCC,
 How sched_deps.c file computes dependencies between instructions.
 Is there any reference papers to understand instruction scheduling.
I want to know how depencendencies , priorities, cost and reservations are
computing. How stalls are computing?

Please help me

when I use "-fsched-verbose=10" option the dump file contails the following
output.

;;   ======================================================
;;   -- basic block 0 from 34 to 39 -- after reload
;;   ======================================================

;;   --------------- forward dependences: ------------

;;   --- Region Dependences --- b 0 bb 0
;;      insn  code    bb   dep  prio  cost   reservation
;;      ----  ----    --   ---  ----  ----   -----------
;;       34    29     0     0     6     1   pentium-firstuv     : 39 38 35
;;       35    35     0     1     5     1   pentium-firstuv     : 39 38 41
43 7
;;        7    35     0     1     3     1   pentium-firstuv     : 39 38 44
;;       43    35     0     1     3     1   pentium-firstuv     : 39 38 44
;;       44   140     0     2     2     1   pentium-firstuv     : 39 42
;;       41    35     0     1     2     1   pentium-firstuv     : 39 38 42
;;       42   140     0     2     1     1   pentium-firstuv     : 39 28
;;       28    -1     0     1     0     0   nothing     : 39
;;       38    32     0     5     0     1   pentium-firstuv     : 39
;;       39   364     0     9     0     0   nothing     :

;;              Ready list after queue_to_ready:    34
;;              Ready list after ready_sort:    34
;;      Ready list (t =  0):    34
;;        0--> 34   [--sp]=bp                          :pentium-firstuv
;;              dependences resolved: insn 35 into queue with cost=1
;;              Ready-->Q: insn 35: queued for 1 cycles.
;;      Ready list (t =  0):
;;              Second chance
;;              Q-->Ready: insn 35: moving to ready without stalls
;;              Ready list after queue_to_ready:    35
;;              Ready list after ready_sort:    35
;;      Ready list (t =  1):    35
;;        1--> 35   bp=sp                              :pentium-firstuv
;;              dependences resolved: insn 41 into queue with cost=2
;;              Ready-->Q: insn 41: queued for 2 cycles.
;;              dependences resolved: insn 43 into queue with cost=2
;;              Ready-->Q: insn 43: queued for 2 cycles.
;;              dependences resolved: insn 7 into queue with cost=2
;;              Ready-->Q: insn 7: queued for 2 cycles.
;;      Ready list (t =  1):
;;              Second chance
;;              Q-->Ready: insn 7: moving to ready with 1 stalls
;;              Q-->Ready: insn 43: moving to ready with 1 stalls
;;              Q-->Ready: insn 41: moving to ready with 1 stalls
;;              Ready list after queue_to_ready:    41  43  7
;;              Ready list after ready_sort:    41  43  7
;;      Ready list (t =  3):    41  43  7
;;        3--> 7    ax=[bp+0xc]                        :pentium-firstuv
;;      Ready list (t =  3):    41  43
;;        3--> 43   cx=[bp+0x8]                        :pentium-firstuv
;;              dependences resolved: insn 44 into queue with cost=1
;;              Ready-->Q: insn 44: queued for 1 cycles.
;;      Ready list (t =  3):    41
;;              Q-->Ready: insn 44: moving to ready without stalls
;;              Ready list after queue_to_ready:    44  41
;;              Ready list after ready_sort:    44  41
;;      Ready list (t =  4):    44  41
;;        4--> 41   dx=[bp+0x10]                       :pentium-firstuv
;;              dependences resolved: insn 38 into ready
;;      Ready list (t =  4):    38  44
;;        4--> 44   {ax=ax+cx;clobber flags;}          :pentium-firstuv
;;              dependences resolved: insn 42 into queue with cost=1
;;              Ready-->Q: insn 42: queued for 1 cycles.
;;      Ready list (t =  4):    38
;;              Q-->Ready: insn 42: moving to ready without stalls
;;              Ready list after queue_to_ready:    42  38
;;              Ready list after ready_sort:    38  42
;;      Ready list (t =  5):    38  42
;;        5--> 42   {ax=ax+dx;clobber flags;}          :pentium-firstuv
;;              dependences resolved: insn 28 into ready
;;      Ready list (t =  5):    28  38
;;        5--> 38   {bp=[sp];sp=sp+0x4;}               :pentium-firstuv
;;      Ready list (t =  5):    28
;;              Ready list after queue_to_ready:    28
;;              Ready list after ready_sort:    28
;;      Ready list (t =  6):    28
;;        6--> 28   use ax                             :nothing
;;              dependences resolved: insn 39 into ready
;;      Ready list (t =  6):    39
;;        6--> 39   return                             :nothing
;;      Ready list (t =  6):
;;              Second chance
;;      Ready list (final):
;;   total time = 6
;;   new head = 36
;;   new tail = 39

Thanks in advance

Pavan,
Home: http://www.cse.iitb.ac.in/~pavankumar