IMPROVING DATA-FLOW ANALYSIS WITH PATH PROFILES

Data-flow analysis computes its solutions over the paths in a control- flow graph. These paths-whether feasible of infeasible, heavily or rar ely executed-contribute equally to a solution. However, programs execu te only a small fraction of their potential paths and, moreover, progr ams' execution time and cost is concentrated in a far smaller subset o f hot paths. This paper describes a new approach to analyzing and opti mizing programs, which improves the precision of data flow analysis al ong hot paths. Our technique identifies and duplicates hot paths, crea ting a hot path graph in which these paths are isolated. After flow an alysis, the graph is reduced to eliminate unnecessary duplicates of un profitable paths. In experiments on SPEC95 benchmarks, path qualificat ion identified 2-112 times more non-local constants (weighted dynamica lly) than the Wegman-Zadek conditional constant algorithm, which trans lated into 1-7% more dynamic instructions with constant results.