modify the same spot in array a. When a possible dependence is found, loop dependence analysis usually makes every attempt to characterize the relationship between dependent instances, as some optimizations may still be possible. It may also be possible to transform the loop to remove or modify the dependence. In the course of proving or disproving such dependencies, a statement S may be decomposed according to which iteration it comes from. For instance, S[1,3,5] refers to the iteration where i1 = 1, i2 = 3 and i3 = 5. Of course, references to abstract iterations, such as S[d1+1,d2,d3], are both permitted and common. Data dependence Data dependencies show the relationships between the variables in the code. There are three different types of data dependencies: True Dependence (sometimes referred to as Flow Dependence) Anti Dependence Output Dependence True dependence A true dependence occurs when a location in memory is written to before it is read. It introduces read-after-write (RAW) hazards because the instruction that reads from the location in memory has to wait until it is written to by the previous instruction or else the reading instruction will read the wrong value. An example of a true dependence is: S1: a = 5; S2: b = a; In this example, there is a true dependence between S1 and S2 because variable a is first written in statement S1 and then variable a is read by statement S2. This true dependence can be represented by S1 →T S2. A true dependence can also be seen when reading and writing between different iterations in a loop. The following example shows a true dependence between different iterations. for (j = 1; j < n; j++) S1: a[j] = a[j-1]; In this example, a true dependence exists between statement S1 in the jth iteration and S1 in the j+1th iteration. There is a true dependence because a value will be written to a[j] in one iteration and then a read occurs by a[j-1] in the next iteration. This true dependence can be represented by S1[j] →T S1[j+1]. Anti dependence An anti dependence occurs when a location in memory is read before that same location is written to. This introduces write-after-read (WAR) hazards because the instruction that writes the data into a memory location has to wait until that memory location has been read by the previous instruction or else the reading instruction would read the