Identifying common instructions

In figure 4.4 some instructions are printed in blue. Those are the instructions that directly or indirectly influence the loop variable. Clearly, any instruction that influences the loop variable, must be propagated to all loops we create, otherwise the behavior of the new loops will be different from the original loop.

These instructions that influence the loop variable are called the common instructions. In the example it is simply the two operations that decrease the loop variable, but the case could have been less simple.

In the following, we consider our loop code (the code inside the loop) to be the only code visible to us (which is actually the case for the loop parallelizer in the current implementation).

We work with several sets here: The set C of common instructions. The set of variables $\mathcal{S}$ that influence the loop variable. The touches set $\mathcal{T}$ of the current instruction. And finally the uses set $\mathcal{U}$ of the current instruction.

Initially $\mathcal{S}$ is set to contain only the loop variable itself. We set the current instruction to be the last instruction in the loop code. We want to traverse the loop from the bottom and up (since the last instruction in the loop code is the one that has most recently had the chance to alter the loop variable, in the second and all following iterations).

We calculate the intersection $m = \mathcal{T} \cap \mathcal{S}$. This is the set of variables that currently influence the loop, and that the current instruction touches.

If $m$ is non-empty, we add the current instruction to the set of common instructions. And, we assign $\mathcal{S} \gets (\mathcal{S} \setminus m) \cup \mathcal{U}$. Or, in other words, we remove the variables the current instruction touches from the set of variables that influence the loop variable. Secondly, we add the variables it uses, to this same set.

The current instruction is then set to be the instruction preceding the current ``current instruction''. Remember, we are traversing the loop code from the bottom and up. We go back to recalculating $m$.

This iteration is continued until we have been thru all instructions in the loop code.

The end result, is a set of common instructions that reflects exactly which instructions are needed to update the loop variable properly. Any remaining instructions are the ones that do the ``real'' work.