16 Apr 2005 11:11:04 -0400

Related articles |
---|

Generating optimal code from a DAG weitzel@simtec.mb.uni-siegen.de (Michael Weitzel) (2005-04-11) |

Re: Generating optimal code from a DAG touati@prism.uvsq.fr (TOUATI Sid) (2005-04-16) |

Re: Generating optimal code from a DAG tmk@netvision.net.il (2005-04-16) |

From: | TOUATI Sid <touati@prism.uvsq.fr> |

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 |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.