Re: code transformations

Henry Dan Lambright <hdlambri@cs.arizona.edu>
25 Oct 1996 22:16:05 -0400

          From comp.compilers
Related articles
code transformations? lord@emf.net (1996-09-22)
Re: code transformations? hdlambri@cs.arizona.edu (Henry Dan Lambright) (1996-10-20)
Re: code transformations? hogan@rintintin.Colorado.EDU (1996-10-24)
Re: code transformations hdlambri@cs.arizona.edu (Henry Dan Lambright) (1996-10-25)
| List of all articles for this month |
From: Henry Dan Lambright <hdlambri@cs.arizona.edu>
Newsgroups: comp.compilers
Date: 25 Oct 1996 22:16:05 -0400
Organization: Compilers Central
References: 96-10-107 96-09-094 96-10-101
Keywords: translator

On 24 Oct 1996, Apollo wrote:
> According to Garey & Johnson, "Maximum Subgraph Matching" is NP-complete.
> But your algorithm would solve MSM, hence your problem is NP-hard.
> It also appears that it is in NP, so it seems that a 'diff' of DAGs is
> an NP-complete problem. If the DAGs turn out to be _trees_, though, it
> seems likely that there is a polynomial algorithm for the problem.


A reasonable restriction on the flowgraph in mind is that it was not
derived from a language that has arbitrary jumps (gotos.) The
language would allow one to break out of loops in Java's manner
(ie. labeled break and continue,) however. This restriction would
simplify the DAGs. I do not know if they would be simplified enough.


On 24 Oct 1996, Bill Leonard wrote:
> Consider, for instance, transformations such as loop interchange or
> loop fusion, which have drastic effects on the flow graph.


Yes. I should have clarified in my original message that in the
problem in mind, one has control over compilation. ie, I am given
source code, not the binaries. The compiler would be told to perform
no optimizations.
--

Post a followup to this message

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