Re: 8086 register allocation

Path	csiph.com!xmission!usenet.csail.mit.edu!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	Fernando <pronesto@gmail.com>
Newsgroups	comp.compilers
Subject	Re: 8086 register allocation
Date	Mon, 10 May 2021 04:46:31 -0700 (PDT)
Organization	Compilers Central
Lines	21
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<21-05-006@comp.compilers> (permalink)
References	<21-05-005@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset="UTF-8"
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="14625"; mail-complaints-to="abuse@iecc.com"
Keywords	architecture, optimize
Posted-Date	10 May 2021 11:05:30 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
In-Reply-To	<21-05-005@comp.compilers>
Xref	csiph.com comp.compilers:2658

Show key headers only | View raw

Hi Alex,

I read part of your code. Very nice! The core algorithm (disregarding the x86 specific part) seems like 'local register allocation' using Belady's heuristic for spilling. I have a class about it here:

https://youtu.be/XmNXeNCGSIA

There has been some academic work about models for register allocation for x86. Two papers follow below:

* Register Allocation by Puzzle Solving, https://llvm.org/pubs/2008-06-PLDI-PuzzleSolving.pdf

* A generalized algorithm for graph-coloring register allocation, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.10.3076&rep=rep1&type=pdf

Regards,

Fernando

> For the fun of it I've implemented a greedy bottom-up local register
> allocator for the intel 8086 CPU, which is known for its non-uniform
> use of registers in ALU instructions and memory operands
> (https://github.com/alexfru/regal86).

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

8086 register allocation "Alexei A. Frounze" <alexfrunews@gmail.com> - 2021-05-09 14:28 -0700
  Re: 8086 register allocation Fernando <pronesto@gmail.com> - 2021-05-10 04:46 -0700
  Re: 8086 register allocation gah4 <gah4@u.washington.edu> - 2021-05-10 14:49 -0700
    Re: 8086 register allocation Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2021-05-11 03:35 +0200
      Re: 8086 register allocation gah4 <gah4@u.washington.edu> - 2021-05-10 21:19 -0700
      Re: 8086 register allocation Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2021-05-11 09:35 +0200
    Re: 8086 register allocation Thomas Koenig <tkoenig@netcologne.de> - 2021-05-11 06:44 +0000

csiph-web