RE: Assembling span-dependent instructions

Christopher F Clark <christopher.f.clark@compiler-resources.com> 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


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


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
start-small-and-grow).


>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
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[Szymanski was working on a PDP-11 where all instructions are
an integral number or words so there's no alignment to do. -John]

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