|dc.description.abstract||Most dynamic program analysis techniques such as proﬁle-driven compiler optimizations, software testing and runtime property checking infer program properties by proﬁling one or more executions of a program. Unfortunately, program proﬁling does not come for free. For example, even the most eﬃcient techniques for proﬁling acyclic, intra-procedural paths can slow down program execution by a factor of 2. In this thesis, we propose techniques that signiﬁcantly lower the overheads of proﬁling paths, enabling the use of path-based dynamic analyzes in cost-sensitive environments.
Preferential path proﬁling (PPP) is a novel software-only path proﬁling scheme that eﬃciently proﬁles given subsets of paths, which we refer to as interesting paths. The algorithm is based on the observation that most consumers of path proﬁles are only interested in proﬁling a small set of paths known a priori. Our algorithm can be viewed as a generalization of the Ball-Larus path proﬁling algorithm. Whereas the Ball-Larus algorithm assigns weights to the edges of a given CFG such that the sum of the weights of the edges along each path through the CFG is unique, our algorithm assigns weights to the edges such that the sum of the weights along the edges of interesting paths is unique. Furthermore, our algorithm attempts to achieve a minimal and compact encoding of the interesting paths; such an encoding signiﬁcantly reduces the overheads of path proﬁling by eliminating expensive hash operations during proﬁling. Interestingly, we ﬁnd that both the Ball-Larus algorithm and PPP are essentially a form of arithmetic coding. We use this connection to prove that the numbering produced by PPP is optimal.
We also propose a programmable, non-intrusive hardware path proﬁler (HPP). The hardware proﬁler consists of a path detector that detects paths by monitoring the stream of retiring branch instructions emanating from the processor pipeline. The path detector can be programmed to detect various types of paths and track architectural events that occur along paths. The second component of the hardware proﬁling infrastructure is a Hot Path Table (HPT), that collects accurate hot path proﬁles.
Our experimental evaluation shows that PPP reduces the overheads of proﬁling paths to 15% on average (with a maximum of 26%). The algorithm can be easily extended to proﬁle inter-procedural paths at minimal additional overheads (average of 26%). We modeled HPP using a cycle-accurate superscalar processor simulator and ﬁnd that HPP generates accurate path proﬁles at extremely low overheads (0.6% on average) with a moderate hardware budget. We also evaluated the use of PPP and HPP in a realistic proﬁling scenarios. We ﬁnd that the proﬁles generated by HPP can eﬀectively replace expensive proﬁles used in proﬁle-driven optimizations. We also ﬁnd that even well-tested programs tend to exercise a large number of untested paths in the ﬁeld, emphasizing the need for eﬃcient proﬁling schemes that can be deployed in production environments.||en