Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.compilers Subject: RE: Assembling span-dependent instructions Date: Sat, 30 Jul 2022 09:28:06 GMT Organization: Institut fuer Computersprachen, Technische Universitaet Wien Lines: 55 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-07-061@comp.compilers> References: <22-07-049@comp.compilers> <22-07-056@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="40817"; mail-complaints-to="abuse@iecc.com" Keywords: code, optimize, comment Posted-Date: 30 Jul 2022 14:09:36 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:3148 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 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]