| Yes, the time complexity of m-cfa is polynomial. See https://arxiv.org/pdf/1311.4231 I'll borrow a few choice pieces from the paper to try to explain why. The main difference is that: k-cfa is sensitive to the last k calls. m-cfa is sensitive to the top m stack frames. This turns out not equivalent: with k=1 vs m=1: a program where main calls a calls b. in k-cfa, the context will be the call to b. in m-cfa, the context will be the call to a. How m-cfa came about and why it works: k-CFA is EXPTIME-complete (so no polynomial algorithm can exist). However, it was observed that there are plenty of provably k-cfa equivalent points-to for OO languages that ran in provably polynomial time (and none for functional languages). Diving into this caused folks to discover the difference between objects and closures matters a lot to the time-bounds, and led to the formulation of m-cfa. Space complexity was never as much an issue as time complexity was, due to BDD's and other things. |