SIMD (Single Instruction stream, Multiple Data stream) computers can only execute the exact same instruction across all processing elements. This paper presents a new com;piler optimization that transforms multiple distinct code threads so that they have as many instructions in common as possible, hence, SIMD execution time is minimized. For example, SIMD "parallel if" statements typically take the then clause time plus the else clause time to execute, but this new tmnsformation usually can induce identical code sequences for most of the code in the then and else clauses, often yielding a 40% improvement in execution speed. The same principle also could be used to transform code which operates on multiple short vectors into operations on long vectors containing the catenation of the shorter vectors; for example, operations on two 8,192-element arrays might be combined into a single operation apparently acting on a 16,384-element array.


Common subexpression induction (CSI), common subexpression elimination (CSE), Single Insuuction stream Multiple Data stream (SIMD), compiler optimization

Date of this Version

January 1992