spaghetti code

Apologies if I'm missing something -- I don't know all that much about
compilers -- but as far as I can see the problem of optimising spaghetti
code as opposed to structured code is one of turning each procedure into a
form where no pair of jumps (forward or backward) is linked. (A pair of
jumps is linked when each jump encloses exactly one end of the other.)


If I'm right so far, there are surely two ways to go about the process of
unlinking. One involves duplicating sections of code, and has been
described in previous news -- node splitting, as I now know it is called.
The other involves introduction of extra variables, used as flags to
maintain a particular flow of control, and has only a very small overhead
in terms of either code size or number of instructions executed. For
example, the following (pseudo-)code segment:


statement1; <-------
label1; |
statement2; <---- |
label2; | |
statement3; | |
if condition1 then goto label1; >------
statement4; |
if condition2 then goto label2; >---
statement5;


which I guess was what was meant by "intertwined loops" in previous news,
becomes:


statement1;
label1; <--------------------------
statement2; |
label2; <----------------------- |
statement3; | |
flag1 := condition1; | |
if flag1 then goto label3; >--- | |
statement4; | | |
label3; <--- | |
if (condition2 AND NOT flag1) then goto label2; >-- |
if flag1 then goto label1; >-------------------------
statement5;


Hey presto, unlinked and optimisable. I developed this for use with a
verification system, not a compiler, so I may be totally wide of the mark
here and I won't waste news space with the details, but I had no trouble
generalising this sort of idea to arbitrary spaghetti code, and proving
that it terminates in quadratic time relative to the number of jumps that
are linked to some other jump. If anyone wants to know more, I'll be
happy to post a complete description (only c. 5 times the size of this
message).


Cheers, Aubrey de Grey
[I believe that in soem cases you can have the same sort of explosion with
extra flags and labels that you do with code duplication. -John]
--

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