RE: Assembling span-dependent instructions

In the large-and-shrink model, you are not allowed to shrink an instruction
which causes the program to become incorrect, it's a test you make before
shrinking it, so you never shrink your example instruction and have to
regrow it. I suppose you could do it by shrink-test-abort
(regrow)/commit. However, that doesn't fix the problem where shrinking one
instruction depends upon shrinking another to result in a valid program
(and the instructions are mutually dependent that way).


And, that's one of the reasons why the two results converge to different
programs. There can be cliques of instructions that need to be all shrunk
before the program is legal. (Or in the more realistic case, graphs where
you have to color (small, large) just right to get the smallest legal
program, which is why it becomes NP-complete and reduces to a
satisfiability problem.)


If you disallow shrinking instructions which don't produce legal programs
(without any other changes, i.e. you cannot shrink your example
instruction), the large-and-shrink model converges. However, there are
combinations of shrunk instructions it never tries, because they are
mutually dependent.


And as far as I know, the first presentations of this idea only dealt with
shrinking jump instructions, where all distances were positive, so that you
could guarantee that the process was monotonic, i.e. all shrinking of
instructions made more shrinking possible. And that's where the proofs
that both algorithms could be shown to converge (but to different code
sequences) applies.


And the large-and-shrink algorithm was shown first, because if the
algorithm was halted mid-way through, it still resulted in a legal
program. The small-and-grow algorithm starts with an invalid program and
needs to proceed to reach a state where the program is legal. If you don't
let it converge, you have a broken instruction sequence.


Kind regards,
Chris


--
******************************************************************************


Chris Clark email:
christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

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