Re: code transformations?

Henry Dan Lambright <hdlambri@cs.arizona.edu> writes:
> Suppose you modify a program's source, but do not modify it in a way so
> that it performs differently (ie the modified version never yields
> different output for any given input.) I would like to know if the
> underlying control and data flow graphs would be similar enough (between
> the former and later versions of the program) for you to be able to "diff"
> the two graphs.


If your only criterion is that the two programs give the same output
for identical inputs, then I'd say the control flow graphs may have no
resemblance to either other. Determining equivalence of two flow
graphs is equivalent to the Halting Problem.


Consider, for instance, transformations such as loop interchange or
loop fusion, which have drastic effects on the flow graph.
Transformations as strength reduction change the actual computations
performed, so that two basic blocks may look completely different but
actually compute the same result. Transformations such as folding
constant branch tests and zero-trip-test elimination either eliminate
branches or introduce new ones, which will have a substantial effect
on the flow graph.


Now put all this together, and throw in subroutine inlining and code
motion, and you can easily get a flow graph that looks absolutely
nothing like the original. (In fact, in my experience in debugging
optimizers, the most difficult part was actually trying to figure out
how the modified flow graph related to the original one.) And there
are many more transformations I haven't mentioned.


> Does anyone out there know if an algorithm exists which counts the
> minimum number of steps to change one DAG into another ?


No, I don't. You'd have to define what you mean by "step" first.


--
Bill Leonard
Concurrent Computer Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.ccur.com
--

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