0
$\begingroup$

I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG).

Is there an algorithm for taking code (or Abstract syntax trees) from a language, say Python, and generating a DAG for it? I've been searching for a paper related to this for a long time and haven't found anything on google scholar.

Intuitively, I'd say that it's not possible, since some languages (such as Python) can change just about everything at run-time, and thus to determine the behavior and dependencies of a given program you would have to run it first for every possible set of inputs.

EDIT: I'm using DAG in this sense as the Directed Acyclic Graph for the dependencies (i.e. which parts depend on which other parts)

$\endgroup$
  • 2
    $\begingroup$ What exactly is the DAG supposed to express? You are probably correct, but the answer depends on the definition. $\endgroup$ – reinierpost Sep 2 '15 at 8:15
  • $\begingroup$ I think OP means the call graph (en.wikipedia.org/wiki/Call_graph), not (e.g.) the CFG. Of recursion renders the call graph cyclic... $\endgroup$ – S Huntsman Sep 9 '15 at 3:32
  • $\begingroup$ Are you asking how one can obtain a task graph of a program, given only its code? $\endgroup$ – András Salamon Sep 10 '15 at 13:54
3
$\begingroup$

I assume you're looking for ways to compute the Control Flow Graph of a given program.

This graph depends (obviously) on the actual operational semantics of the language you are interested in, and so cannot be computed from the AST alone, in the sense that some knowledge of the language semantics themselves are needed.

For a given language it is possible to build the CFG given the AST of the parsed program, and indeed this is usually a very important step in compilers to perform flow analysis. This can be found in chapter 17 of Appel or in chapter 7 of Muchnick.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.