Interprocedural Dependence Analysis of Higher-Order Programs via Stack Reachability
Matthew Might, Tarun Prabhu · 2009
We present a small-step abstract interpretation for the A-Normal Form λ-calculus (ANF). This abstraction has been instrumented to find data-dependence conflicts for expressions and procedures. Our goal is parallelization: when two expressions have no de-pendence conflicts, it is safe to evaluate them in parallel. The under-lying principle for discovering dependences is Harrison’s principle: whenever a resources is accessed or modified, procedures that have frames live on the stack have a dependence upon that resource. The abstract interpretation models the stack of a modified CESK ma-chine by mimicking heap-allocation of continuations. Abstractions of continuation marks are employed so that the abstract semantics retain proper tail-call optimization without sacrificing dependence information.