Re: Generating optimal code from a DAG

16 Apr 2005 11:11:04 -0400

          From comp.compilers

Related articles
Generating optimal code from a DAG (Michael Weitzel) (2005-04-11)
Re: Generating optimal code from a DAG (TOUATI Sid) (2005-04-16)
Re: Generating optimal code from a DAG (2005-04-16)
| List of all articles for this month |

From: TOUATI Sid <>
Newsgroups: comp.compilers
Date: 16 Apr 2005 11:11:04 -0400
Organization: Universite de Versailles Saint-Quentin-en-Yvelines
References: 05-04-028
Keywords: optimize
Posted-Date: 16 Apr 2005 11:11:04 EDT

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

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.


Post a followup to this message

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