World's most popular travel blog for travel bloggers.

What additional expressivity does polyvariance give in pushdown CFA?

, , No Comments
Problem Detail: 

I'm reading through Pushdown Control-Flow Analysis of Higher-Order Programs, which presents a synthesis of the Abstracting Abstract Machines technique and pushdown automata to get static analysis which perfectly matches call and return sites. The paper presents a monovariant and two polyvariant forms of the system.

I can't seem to get my head around what additional expressive power polyvariance (e.g. 1CFA) grants when return-flow merging is already eliminated in the monovariant case by the pushdown methods.

Could someone provide an example program in which polyvariance helps?

Asked By : Alex R
Answered By : Alex R

After playing with an implementation (found here), I believe I've figured it out.

Although 0PDCFA technically entirely eliminates return-flow merging, this isn't a very strong result in the absence of any polyvariance: if the same function is called in two different contexts, the analysis must end up merging flows within the body of the function, since multiple values are bound to the same variable and the variable's abstract address is identified with its name. 1PDCFA provides a different set of addresses to each syntactically distinct call of each function (I might be either under- or over-selling here), eliminating much of the merging.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback