|code transformations? email@example.com (1996-09-22)|
|Re: code transformations? firstname.lastname@example.org (Henry Dan Lambright) (1996-10-20)|
|Re: code transformations? hogan@rintintin.Colorado.EDU (1996-10-24)|
|Re: code transformations email@example.com (Henry Dan Lambright) (1996-10-25)|
|From:||Henry Dan Lambright <firstname.lastname@example.org>|
|Date:||25 Oct 1996 22:16:05 -0400|
|References:||96-10-107 96-09-094 96-10-101|
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
Return to the
Search the comp.compilers archives again.