  The control flow graph (CFG) representation of a procedure used by virtually
all flow-sensitive program analyses, admits a large number of infeasible
control flow paths i.e., these paths do not occur in any execution of the
program. Hence the information reaching along infeasible paths in an analysis
is spurious. This affects the precision of the conventional maximum fixed point
(MFP) solution of the data flow analysis, because it includes the information
reaching along all control flow paths. The existing approaches for removing
this imprecision are either specific to a data flow problem with no
straightforward generalization or involve control flow graph restructuring
which may exponentially blow up the size of the CFG.
  We lift the notion of MFP solution to define the notion of feasible path MFP
(FPMFP) solutions that exclude the data flowing along known infeasible paths.
The notion of FPMFP is generic and does not involve CFG restructuring. Instead,
it takes externally supplied information about infeasible paths and lifts any
data flow analysis to an analysis that maintains the distinctions between
different paths where these distinctions are beneficial, and ignores them where
they are not. Thus it gets the benefit of a path-sensitive analysis where it is
useful without performing a conventional path-sensitive analysis.
  We evaluated the proposed feasible path MFP solutions for reaching
definitions analysis and potentially uninitialized variable analysis on 30
benchmarks. The evaluation results indicate that precision improvement in these
two analyses respectively reduce the number def-use pairs by up to 13.6%
(average 2.87%, geometric mean 1.75%), and reduce the potentially uninitialized
variable alarms by up to 100% (average 18.5%, geo. mean 3%). We found that the
FPMFP computation time was 2.9X of MFP computation time on average.
