RE: Assembling span-dependent instructions

Christopher F Clark <>
Thu, 28 Jul 2022 16:02:16 +0300

          From comp.compilers

Related articles
Assembling span-dependent instructions (2022-07-27)
RE: Assembling span-dependent instructions (Christopher F Clark) (2022-07-28)
RE: Assembling span-dependent instructions (2022-07-30)
RE: Assembling span-dependent instructions (Christopher F Clark) (2022-07-31)
| List of all articles for this month |

From: Christopher F Clark <>
Newsgroups: comp.compilers
Date: Thu, 28 Jul 2022 16:02:16 +0300
Organization: Compilers Central
References: 22-07-049
Injection-Info:; posting-host=""; logging-data="56136"; mail-complaints-to=""
Keywords: code, optimize
Posted-Date: 29 Jul 2022 16:39:52 EDT


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 Clark email:
Compiler Resources, Inc. Web Site:
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris

Post a followup to this message

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