When the compiler detects that an LOD must be inserted into the code to satisfy a dependence, it is often the case that the dependencies imply a region over which the LOD can be placed rather than an exact position. Consider the example illustrated below:
280 do 100 mrs = 1, nrs
284 10 xrsiq(mi, mq) = zero
302 val = xrsiq(mi, mq)
icons (i.e. 284, 291
and 292) represent DU definitions of the xrsiq
array. Similarly, the code marked with
at line 302, represents a CU use of xrsiq. Together
these define three dependencies which must each be broken by a CU/DU synchronization
(i.e. an LOD). There are, however, several choices as to the position in the code
where the synchronization should be placed. It could be placed immediately prior to the
CU use of xrsiq, but then the LOD would be executed 2,821,875 times. Clearly, the
optimimum position of the LOD is at a point in the code which dominates the CU use
and which post-dominates all DU definitions, but which executes least frequently.
In the experimental compiler, the decoupler uses a graph algorithm to hoist LODs to a basic block in the intermediate code which satisfies the above criteria. In this example, it places the LOD at line 298, resulting in an LOD frequency of just 2,625.
It is also possible that the target of the dependence is executed less frequently than the sources, and perhaps even less frequently than the ``obvious'' position that the hoisting algorithm might suggest. This could occur, for example, if the sources of the dependencies execute conditionally and their conditions are rarely true. In such cases it pays to migrate the LOD towards the sources, possibly replicating the LOD where sources are guarded by different conditions.