RE: Assembling span-dependent instructions

From	Christopher F Clark <christopher.f.clark@compiler-resources.com>
Newsgroups	comp.compilers
Subject	RE: Assembling span-dependent instructions
Date	2022-07-28 16:02 +0300
Organization	Compilers Central
Message-ID	<22-07-056@comp.compilers> (permalink)
References	<22-07-049@comp.compilers>

Show all headers | View raw

Anton,

Curiously, I recently used that example (limited to jumps) to explain
something on Quora, how two different approaches can yield different
answers to the same question.

You can make both, the large-and-shrink, and small-and-grow approaches
converge (just ban doing the opposite, once shrunk an instruction cannot
regrow or once grown an instruction cannot reshrink).  And under certain
assumptions, you can show that the small-and-grow result will always be
"more optimal" (smaller) than the large-and-shrink result.  However, one of
those assumptions is that shrinking some instruction will not require a
different instruction to grow--the results must be monotonic.  That is not
always true in real-life instruction sets.

More relevant is that the order or growing or shrinking instructions can
change which other instructions grow or shrink and that means picking which
one to grow or shrink is important and that contributes to the
NP-completeness of the problem.  You potentially have to try all possible
orders of growing/shrinking to find the optimal set.

There are even other aspects that impact real-life implementations, such as
aligned instructions possibly executing faster, such that one isn't just
looking for the smallest size, but the smallest size that runs fastest.

Nice to see someone else remembering the same issues.

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