Method for convergence analysis based on thread variance analysis

摘要

Basic blocks within a thread program are characterized for convergence based on variance analysis or corresponding instructions. Each basic block is marked as divergent based on transitive control dependence on a block that is either divergent or comprising a variant branch condition. Convergent basic blocks that are defined by invariant instructions are advantageously identified as candidates for scalarization by a thread program compiler.

主权项

1. A computer-implemented method for characterizing a thread program, the method comprising:
marking each basic block associated with the thread program as being convergent, wherein each basic block includes a plurality of instructions and starts with a label instruction and is terminated by a control transfer instruction; marking a set of instructions associated with each basic block as being invariant; initializing a work list that includes instructions that are known to be variant relative to the set of instructions; selecting a first instruction from the work list; marking the first instruction as variant; adding successor instructions to the work list based on the first instruction; and propagating a divergence attribute to identify associated basic blocks as divergent, and to identify instructions within the associated basic blocks as variant.