Profiling all paths: A new profiling technique for both cyclic and acyclic paths
As an important technique in dynamic program analysis, path profiling collects the execution frequency of different paths, and has been widely used in a variety of areas. However, existing intra-procedural profiling techniques cannot effectively deal with loops, i.e., they are limited in either working with acyclic paths, or with a small number of loop iteration. This paper presents a new profiling technique called PAP (Profiling All Paths), which can profile all finite-length paths within a procedure. PAP consists of two basic phases, the probe instrumentation phase which assigns a unique pathid to each path, and the backwalk phase which uses the pathids to determine the corresponding executed paths. Furthermore, breakpoints are introduced to store the probe value which may overflow during long executions, and the number of probes is reduced based on the integration of PAP with an existing profiling technique. From our case study and experiments, PAP is found to be effective and efficient in profiling both cyclic and acyclic paths.