extending path profiling across loop backedges and procedure boundaries
Since their introduction, path profiles have been used toguide the application of aggressive code optimizations andperforming instruction scheduling. However, for optimizationand scheduling, it is often desirable to obtain frequencycounts of paths that extend across loop iterations and crossprocedure boundaries. These longer paths, referred to asinteresting paths in this paper, account for over 75\% of theflow in a subset of SPEC benchmarks. Although the frequencycounts of interesting paths can be estimated frompath profiles, the degree of imprecision of these estimates isvery high. We extend Ball Larus (BL) paths to create slightlylonger overlapping paths and develop an instrumentationalgorithm to collect their frequencies. While these pathsare slightly longer than BL paths, they enable very preciseestimation of frequencies of potentially much longer interestingpaths. Our experiments show that the average cost ofcollecting frequencies of overlapping paths is 86.8\% whichis 4.2 times that of BL paths. However, while the averageimprecision in estimated total flow of interesting paths derivedfrom BL path frequencies ranges from -38 \% to +138\%, the average imprecision in flow estimates derived fromoverlapping path frequencies ranges only from -4\% to +8\%.
path profiles profiles applications code optimality instruction scheduling scheduling iter paper account flow benchmark collect experience cost profileguided optimization and instruction scheduling overlapping path profiles