Instruction scheduling: Difference between revisions

Revision as of 14:49, 6 January 2018

Revision as of 18:02, 29 April 2018

Line 1:

{{UnreferencedRefimprove|date=JanuaryApril 20092018}}

In [[computer science]], '''instruction scheduling''' is a [[compiler optimization]] used to improve [[instruction-level parallelism]], which improves performance on machines with [[instruction pipeline]]s. Put more simply, without changing the meaning of the code, it tries to

* Avoid [[pipeline stall]]s by rearranging the order of instructions.<ref name="ColdScheduling_1994"/>

* Avoid illegal or semantically ambiguous operations (typically involving subtle instruction pipeline timing issues or non-interlocked resources).

<!-- * order the instructions to avoid duplicated memory access

Line 30:

* If choosing a candidate will create many new sources, its priority will rise. This heuristic tends to generate more freedom for the scheduler.

== The phase order of Instructioninstruction Schedulingscheduling ==

Instruction scheduling may be done either before or after [[register allocation]] or both before and after it. The advantage of doing it before register allocation is that this results in maximum parallelism. The disadvantage of doing it before register allocation is that this can result in the register allocator needing to use a number of registers exceeding those available. This will cause spill/fill code to be introduced which will reduce the performance of the section of code in question.

Line 37:

If scheduling is only done after register allocation then there will be false dependencies introduced by the register allocation that will limit the amount of instruction motion possible by the scheduler.

== Types of Instructioninstruction Schedulingscheduling ==

There are several types of instruction scheduling:

#Local (Basic Block) Scheduling: instructions can't move across basic block boundaries.

Line 50:

* [[Instruction unit]]

* [[Branch predication]]

==References==

{{reflist|refs=

<ref name="ColdScheduling_1994">{{cite report |author-first1=Ching-Long |author-last1=Su |author-first2=Chi-Ying |author-last2=Tsui |author-first3=Alvin M. |author-last3=Despain |url=http://www.scarpaz.com/2100-papers/Power%20Estimation/su94-low%20power%20architecture%20and%20compilation.pdf |title=Low Power Architecture Design and Compilation Techniques for High-Performance Processors |date=1994 |publisher=Advanced Computer Architecture Laboratory |id=ACAL-TR-94-01}}</ref>

}}

{{Compiler optimizations}}