Introduction: Code scheduling is a form of program optimization that applies to the machinecode that is produced by the code generator. Code scheduling is subject tothree kinds of constraints:
1. Control-dependence constraints. All the operations executed in the original program must be executed in the optimized one.
2. Data-dependence constraints. The operations in the optimized program must produce the same results as the corresponding ones in the original program.
3. Resource constraints.The schedule must not oversubscribe the resources on the machine.
These scheduling constraints guarantee that the optimized program produces the same results as the original. However, because code scheduling changes the order in which the operations execute, the state of the memory at any one point may not match any of the memory states in a sequential execution. This situation is a problem if a program's execution is interrupted by, for example, a thrown exception or a user-inserted breakpoint. Optimized programs are therefore harder to debug. Note that this problem is not specific to code scheduling but applies to all other optimizations, including partial redundancy Elimination and register allocation.
Data Dependence: It is easy to see that if we change the execution order of two operations that donot touch any of the same variables; we cannot possibly affect their results. Infact, even if these two operations read the same variable, we can still permutetheir execution. Only if an operation writes to a variable read or written byanother can changing their execution order alter their results. Such pairs ofoperations are said to share data dependence, and their relative executionorder must be preserved. There are three flavors of data dependence:
1. True dependence: read after write. If a write is followed by a read of the same location, the read depends on the value written; such dependence is known as a true dependence.
2. Anti dependence: write after read. If a read is followed by a write to the same location, we say that there is an anti-dependence from the read to the write. The write does not depend on the read per se, but if the write happens before the read, then the read operation will pick up the wrong value. Anti dependence is a byproduct of imperative programming, where the same memory locations are used to store different values. It is not a "true" dependence and potentially can be eliminated by storing the values in different locations.
Output dependence: write after write. Two writes to the same location share an output dependence. If the dependence is violated, the value of the memory location written will have the wrong value after both operations are performed. Anti-dependence and output dependences are referred to as storage-related dependences. These are not "true" dependences and can be eliminated by using different locations to store different values. Note that data dependences apply to both memory accesses and register accesses.