samskivert: Points-to Analysis in Almost Linear Time – Steensgaard

06 March 2010

Describes a cool technique for turning a points-to analysis into a type inference problem—one that can be done in almost linear time, hence the title. As type checking is flow-insensitive, so is the analysis, and since it infers monomorphic types, the analysis is also context-sensitive, but there’s nothing stopping you from doing a polymorphic inference and getting a context sensitive analysis (which I think Steensgaard later did).

Source: PDF ACM

©1999–2022 Michael Bayne