DATA-FLOW FREQUENCY-ANALYSIS

Conventional dataflow analysis computes information about what facts m ay or will not hold during the execution of a program. Sometimes it is useful, for program optimization, to know how often or with what prob ability a fact holds true during program execution. In this paper, we provide a precise formulation of this problem for a large class of dat aflow problems - the class of finite bi-distributive subset problems. We show how it can be reduced to a generalization of the standard data flow analysis problem, one that requires a sum-over-all-paths quantity instead of the usual meet-overall-paths quantity. We show that Kildal l's result expressing the meet-over-all-paths value as a maximal-fixed -point carries over to the generalized setting, We then outline ways t o adapt the standard dataflow analysis algorithms to solve this genera lized problem, both in the intraprocedural and the interprocedural cas e.