Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3149

RE: Assembling span-dependent instructions

Show all headers | View raw

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
------------------------------------------------------------------------------

Back to comp.compilers | Previous | Next — Previous in thread | Find similar

Thread

Assembling span-dependent instructions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-07-27 16:32 +0000
  Re: Assembling span-dependent instructions Kaz Kylheku <480-992-1380@kylheku.com> - 2022-07-27 22:52 +0000
    Re: Assembling span-dependent instructions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-07-28 05:56 +0000
    Re: Assembling span-dependent instructions antispam@math.uni.wroc.pl - 2022-07-28 12:15 +0000
      Re: Assembling span-dependent instructions gah4 <gah4@u.washington.edu> - 2022-07-29 14:22 -0700
      Re: Assembling span-dependent instructions Kaz Kylheku <480-992-1380@kylheku.com> - 2022-07-29 22:36 +0000
  RE: Assembling span-dependent instructions Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-07-28 16:02 +0300
    RE: Assembling span-dependent instructions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-07-30 09:28 +0000
      RE: Assembling span-dependent instructions Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-07-31 02:28 +0300

csiph-web