Re: Generating optimal code from a DAG

The notion of optimality is very relative. The universal definition is
that the generated code is the fastest possible. In the old days, people
spoke about optimal code generation for DAGs because the von-neuman
execution model was the unique reference. So, an optimal code is the
smallest one (minimal spill insertion for instance) since von-neuman
model assume that execution time depends on the number of executed
instructions.




Nowadays, you cannot really guarantee the universal optimality of a
generated DAG, since many micro-architectural features makes very hard
static execution time prediction.




>
> In the texts I read, these problems (and probably others I forgot) are
> usually summarized (or "slayed"?) in a sentence like "Code generation
> from DAG is NP-complete.". ;-)




Usually, it is the problem of generating a code from a DAG that either
contains the smallest number of spill code (proved NP-complete in the
70's) or that uses the available processor functional units in the
smallest time.


>
> I haven't seen any proof or exact description of the problem yet. What
> makes code generation from DAG NP-complete? I have some ideas -- but how
> does an optimal algorithm work?


For instance, just read NP-completeness results of :
- optimal scheduling of a DAG under ressource constraints
- minimal spill insertion of a DAG


These two small problems allow you to generalize the NP-completeness to
your more complex problem.


S

Return to the comp.compilers page.
Search the comp.compilers archives again.