A Lightweight Algorithm for Dynamic If-Conversion during Dynamic Optimization

Dynamic Optimization is an umbrella term that refers to any optimization of software that is performed after the initial compiles time. It is a complementary optimization opportunity that may greatly improve performance on any computer system, but plays an especially important role in statically scheduled code. Several groups are working on developing dynamic optimization systems, yet the area of dynamic optimization algorithms can still benefit from further research. We introduce a lightweight algorithm that can be used in any modern dynamic optimizer to balance control flow and predication based on actual runtime behavior. In addition, we study the effectiveness of predicting overall runtime behavior based on a small sample size. Preliminary results show that if we skip the warm-up period of programs, profiles based on a small sample size of a particular run can be quite representative of overall runtime behavior (up to 98% correlation). This profile information can be used effectively in a number of dynamic optimizations. We found that our dynamic if-conversion algorithm can use this collated profile data to incorporate actual branch misprediction rates into the if-conversion decision process. This method acts as an effective means for balancing the results of static if-conversion, achieving speedup values of up to 14.7%, and can be easily incorporated into modern dynamic optimizers.