Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Christopher F Clark Newsgroups: comp.compilers Subject: RE: Assembling span-dependent instructions Date: Thu, 28 Jul 2022 16:02:16 +0300 Organization: Compilers Central Lines: 39 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-07-056@comp.compilers> References: <22-07-049@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="56136"; mail-complaints-to="abuse@iecc.com" Keywords: code, optimize Posted-Date: 29 Jul 2022 16:39:52 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:3143 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 ------------------------------------------------------------------------------