Program execution optimization using uniform variable identification

摘要

A method, apparatus and computer program, each for optimizing execution of a computer program is disclosed in which a topology-based control flow analysis of basic blocks of the computer program is performed and a data flow analysis of the instructions within the basic blocks is performed to determine if each instruction of said computer program is uniform or non-uniform (variant or invariant). Subsequently, when the computer program is executed, storage of a copy of a variable dependent on a uniform instruction is suppressed.

主权项

1. A processor-executed method of optimizing execution of a computer program, the method comprising the steps of:
identifying basic blocks of instructions within the computer program, wherein each basic block has only one entry point and only one exit point; performing a topology-based control flow analysis of the basic blocks to associate at least one tag ID with each basic block, wherein a tag ID identifies at least one run-time thread having a given run-time instruction sequence; performing a data flow analysis of instructions within the basic blocks and their associated tag IDs to determine whether each instruction of said computer program is uniform or non-uniform, wherein a uniform instruction has a same value for all tag IDs associated with the basic block containing the uniform instruction, wherein, in the data flow analysis, for each immediate successor basic block of an analysed basic block, when the analysed basic block ends with a non-uniform conditional branch instruction, a dummy block is generated on each edge from the analysed basic block to the immediate successor basic block and a new tag ID is generated for association with each dummy block, wherein, in the topology-based control flow analysis, when the analysed basic block immediately post-dominates a second basic block and the second basic block ends with a non-uniform conditional branch instruction, any tag IDs associated with the second basic block are associated with the analysed basic block, wherein, in the topology-based control flow analysis, when the analysed basic block immediately post-dominates a third basic block, and the third basic block ends with a non-uniform conditional branch instruction, tag IDs of successors of the third basic block are dissociated from the analysed basic block, and wherein a phi instruction is determined to be non-uniform, wherein the phi instruction merges two or more variable definitions into a single variable definition from plural predecessor basic blocks of the analysed basic block, when operands of the phi instruction originate in basic blocks which are associated with more than one tag ID; and suppressing storage, when the computer program is executed, of a copy of a variable dependent on a uniform instruction.