RE: Assembling span-dependent instructions

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

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