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.

► A new intra-procedural profiling technique called PAP is presented.
► The correctness of PAP's path encoding is proved.
► EPP is introduced to integrate with PAP to improve PAP's performance.
► PAP's profiling ability and efficiency are tested on JGF and JDK programs.