spirv-fuzz: Transformation to permute instructions in the basic block

[Vasniktel]

Overview

This transformation will randomly decide for each instruction whether we want to move it up or down in the basic block or between different basic blocks. It turns out that the domination rules enable us to determine the set of basic blocks that can be used to put the desired instruction in. A more thorough description will be given in the Implementation details section.

Implementation

Instructions in the SPIR-V language follow a set of rules to ensure that the program remains valid at all times. One of these rules says that the definition of some id should always dominate all usages of that id. This guarantees that when the program encounters some instruction that uses some id A, the instruction that resulted in that id A has already been executed. Thus, we must make sure that these rules are followed to correctly implement this transformation.
In particular, consider some instruction a (let us call it ‘target instruction’) declared in some basic block A (let us call it ‘target block’). This instruction has a set of instructions it depends on. Every instruction from that set is declared in some block that must dominate block A. The target instruction also has a set of instructions that use it. In this case, the target block must dominate all blocks that declare those instructions. Thus, to move target instruction into some basic block we simply have to make sure that that block dominates all blocks that use the target instruction, and that it is being dominated by all the blocks the target instruction depends on.
The implementation will simply have to select a random position in one of those blocks, where the instruction will be put. We should be careful, though, with position-dependent instructions (e.g. OpPhi, OpLoopMerge, OpLabel, OpBranch, OpFunctionParameter etc).