Show description

For the sake of brevity, we only show the effects on the updated elements of state d per rule. We assume a non-standard execution model: predicated execution. Regardless of the flow of control, every operation in the program is executed in topological order. However, the state is only updated if the value @(x) of the program point x is true, otherwise the operation has no effect: @(x) is the predicate of x. The value of @ is true for the entry program point, and initially false for all other program points.

The following problem occurs if such an operation has an operand that is a nested data structure: If this data structure is not uniform, we have to generate code that extracts the sequential values from that data structure and creates values of the corresponding scalar data structure for each of the sequential operations. If the operation is allowed to modify the value, we have to introduce additional write-back operations afterwards. 3 shows an example for this. 3 Structures of data passed to unknown functions yield significant overhead due to creation of temporary scalar structures.

Vectorization of arbitrary control flow requires to generate mask code that tracks which instances are active at any point of the function. Furthermore, we do not want to discard results of inactive instances after each operation, since that would introduce far too much overhead. Placing only as many blend operations as required, however, is a non-trivial task in the presence of complex loop structures. To our knowledge, WFV is the only vectorization approach that can vectorize arbitrary control flow.