Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!us.feeder.erje.net!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED!nerds-end From: Ivan Godard Newsgroups: comp.compilers Subject: Re: Best tools for writing an assembler? Date: Mon, 24 Feb 2014 15:13:44 -0800 Organization: A noiseless patient Spider Lines: 25 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-02-036@comp.compilers> References: <14-02-018@comp.compilers> <14-02-025@comp.compilers> <14-02-027@comp.compilers> <14-02-033@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: miucha.iecc.com 1393298171 42110 64.57.183.58 (25 Feb 2014 03:16:11 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Tue, 25 Feb 2014 03:16:11 +0000 (UTC) Keywords: assembler, comment Posted-Date: 24 Feb 2014 22:16:10 EST 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:1115 On 2/24/2014 12:42 PM, glen herrmannsfeldt wrote: > -- glen [Variable length instructions aren't that hard. You start by > assuming everything will be the long form, then iterate over the code > a few times shrinking what you can. That isn't always perfectly > optimal (which is known to be NP complete), but it's pretty close. > -John] > Shrink is not NP, it is exact using a relaxation algorithm: track pairs of addresses, one the smallest address assuming all unresolved are resolved short, and one largest assuming all unresolved address are long. Resolve long all those spreads whose shortest is longer than the longest short; resolve short all those spreads whose longest is shorter than than the longest short. Iterate resolution until you do a pass in which no more were resolved. Set any remaining unresolved to short. In practice, three iterations are always sufficient, including the final one that resolves nothing. [With some assumptions about chaining variable length jumps, it really is NP-complete. See this 1978 CACM article http://dx.doi.org/10.1145/359460.359474 -John]