RE: Assembling span-dependent instructions (Anton Ertl)
Sat, 30 Jul 2022 09:28:06 GMT

          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: (Anton Ertl)
Newsgroups: comp.compilers
Date: Sat, 30 Jul 2022 09:28:06 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 22-07-049 22-07-056
Injection-Info:; posting-host=""; logging-data="40817"; mail-complaints-to=""
Keywords: code, optimize, comment
Posted-Date: 30 Jul 2022 14:09:36 EDT

Christopher F Clark <> writes:
>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).

My example

          movl foo+133-bar(%rdi),%eax

is one where start-large-and-shrink fails, unless you can regrow: Once
you have shrunk the instruction, the resulting offset 130 does not fit
into the -128..127 range allowed for a byte offset, so the result
would be a failure. Szymanski's approach is to never shrink
instructions that might have this problem (and he has a way to
distinguish those from others that are guaranteed not to have this
problem, and that he allows to shrink).

By contrast, start-small-and-grow never fails and always converges,
without needing to identify problematic instructions.

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

It's not about order, it's about sets. If one wants to do better than
start-small-and-grow, one could take the set of n problematic
instructions and try out all 2^n assignments of small/large to this
set (the sizes of unproblematic instructions are then determined by

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

Alignment was not considered in Szymanski's paper (and probably not in
the assembler he worked on), so the problem can occur without .align
directives. Of course, with .align there are additional reasons for
the non-monotonic behaviour.

Concerning assemblers that select longer instructions for alignment
considerations, I have never heard of that, and I doubt that an
assembler does that, except for the filler instructions produced by
the .align directive when it occurs in code.

- anton
M. Anton Ertl
[Szymanski was working on a PDP-11 where all instructions are
an integral number or words so there's no alignment to do. -John]

Post a followup to this message

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