Path profile guided partial dead code elimination using predication

Abstract

Presents a path-profile-guided partial dead code elimination algorithm that uses predication to enable sinking for the removal of deadness along frequently executed paths at the expense of adding additional instructions along infrequently executed paths. Our approach to optimization is particularly suitable for VLIW architectures since it directs the efforts of the optimizer towards aggressively enabling generation of fast schedules along frequently executed paths by reducing their critical path lengths. The paper presents a cost-benefit data flow analysis that uses path profiling information to determine the profitability of using predication-enabled sinking. The cost of predication-enabled sinking of a statement past a merge point is determined by identifying paths along which an additional statement is introduced. The benefit of predication-enabled sinking is determined by identifying paths along which additional dead code elimination is achieved due to predication. The results of this analysis are incorporated in a code sinking framework in which predication-enabled sinking is allowed past merge points only if its benefit is determined to be greater than the cost. It is also demonstrated that trade-off can be performed between the compile-time cost and the precision of cost-benefit analysis.