Discussion on Paper Efficient Path Profiling

The path Efficient Path Profiling proposes a very clever way of
doing path profiling with low overhead.  The method of assigning
values to edges to differentiate paths is both accurate and efficient
in terms of coding space.  The overhead for this profiling method is
low because most of the operations are used to increment path
registers.  There are also tricks to distribute path register
initialization and counter update to minimize cost.  It can capture
much more dynamic characteristics of programs' control flow than edge
profiling.  Therefore, it's ideal for profiling programs with
relatively simple control flows.  For programs with very complicated
control flows, however, hashing must be done to reduce memory
consumption, at the cost of complexity and speed.  The overhead
incurred is still not high, but roughly at the same order of magnitude
as edge profiling.  In terms of accuracy in determining paths'
frequency, this method is superior to edge profiling.

The method introduced in this paper has shortcomings. Namely,
 
 

When being used to profile programs with potentially huge
number of paths, it has to break paths to reduce memory usage and
avoid register overflow.  Effectively, it degrades to super edge
1. profiling, while edge profiling is less affected by this situation.

If can't differentiate among paths that undergo different number
of iterations within a loop(or loops) while the other part are the
same.  These different paths are sometimes important for test
generation.  It also can't handle programs with badly written control
flows well, such as programs contains goto's.

l1: ...
    if (...) goto l2
    ...
    goto l1
l2: ...

Discussion on Paper Edge Profiling versus Path Profiling: The Showdown

The paper Edge Profiling versus Path Profiling: The Showdown
introduces an effective way of finding hot paths base on edge
profiling.  It uses dynamic programming technique to find definitely
hot paths and potentially hot paths.  For programs with highly biased
branches such as those in SPEC benchmark suite, this method can often
yield very good hot path coverage.  However, for programs with many
unbiased(or not highly biased) branches, the method can't find many
definitely hot paths.  Potentially hot paths don't really reveal too
much information about programs' control flow, though they are
somewhat useful.  In these cases, it's better to refer to path
profiling for better result.