4 ms·

Interesting... now I'm thinking maybe I was confusing it with interprocedural analysis? I've definitely seen the distinction made between them before, though I'

Interesting... now I'm thinking maybe I was confusing it with interprocedural analysis? I've definitely seen the distinction made between them before, though I'm not sure if I've seen them mentioned alongside local analysis in the same text. I guess if you want to have fun this week, go ask your colleagues what the difference between local, interprocedural, and global analysis is. See if they say the last two are synonymous. :-) Regarding the difference for interprocedural analysis: I'm not entirely sure I follow it unfortunately. Let's say you can do everything within a function. Can't you just inline all of its callees (at whatever depth you want) and do your analysis/optimizations based off the result of that? Inlining itself is a rather trivial mechanical transformation, and after that everything is inside one function again, which you can already handle. The only real obstacle here seems to be recursion, but if you just treat that as any other opaque function call that you can't optimize across, you should otherwise get the rest of the way there, right? What am I missing?

UncleMeat 6y ago
As a preface, it is difficult to speak about true fundamental limitations of things like abstract interpretation because "print Top" is a valid algorithm that will work for all programs. It is just completely useless. So you can model function calls in trivial ways (just treat calls and returns as giant phi nodes and widen whenever you hit mutual recursion). But this tends to produce pretty poor results for real programs and your fixed point computation tends to take longer due to the shape of real program call graphs. Add in dynamic dispatch and you've got all sorts of fun (watch all your pointers in a java program get merged through the receiver to Object.equals(), for example). In practice, these structural differences require new approaches. The field has done a really good job at intraprocedural analysis, solving a lot of really important problems many decades ago. How to do fixed point computation over SSAed CFGs is well understood, even when you've got heap relationships to think about. Interprocedural analysis still largely sucks. Even modern approaches like CFL-reachability for dataflow analysis produce a ton of garbage. This is one reason why I say it is just harder. As you mention, recursion prevents you from inlining everything into one giant function. You do get "the rest of the way there" by inlining to some depth limit in the sense that inlining is a way of achieving context sensitive analysis (though it is generally not preferred). But you've still got big problems at the points of mutual recursion (either you need to widen badly or you need to actually do interprocedural analysis) and your program is also exponentially larger in pathological cases.
- dataflow 6y ago
  Ahh I see! Thanks for the explanation.

UncleMeat 6y ago

As a preface, it is difficult to speak about true fundamental limitations of things like abstract interpretation because "print Top" is a valid algorithm that will work for all programs. It is just completely useless. So you can model function calls in trivial ways (just treat calls and returns as giant phi nodes and widen whenever you hit mutual recursion). But this tends to produce pretty poor results for real programs and your fixed point computation tends to take longer due to the shape of real program call graphs. Add in dynamic dispatch and you've got all sorts of fun (watch all your pointers in a java program get merged through the receiver to Object.equals(), for example). In practice, these structural differences require new approaches. The field has done a really good job at intraprocedural analysis, solving a lot of really important problems many decades ago. How to do fixed point computation over SSAed CFGs is well understood, even when you've got heap relationships to think about. Interprocedural analysis still largely sucks. Even modern approaches like CFL-reachability for dataflow analysis produce a ton of garbage. This is one reason why I say it is just harder. As you mention, recursion prevents you from inlining everything into one giant function. You do get "the rest of the way there" by inlining to some depth limit in the sense that inlining is a way of achieving context sensitive analysis (though it is generally not preferred). But you've still got big problems at the points of mutual recursion (either you need to widen badly or you need to actually do interprocedural analysis) and your program is also exponentially larger in pathological cases.

dataflow 6y ago
Ahh I see! Thanks for the explanation.