Path: csiph.com!xmission!news.alt.net!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Elijah Stone Newsgroups: comp.compilers Subject: Nitty-gritty aspects of register allocation Date: Thu, 10 Sep 2020 16:41:26 -0700 Organization: A noiseless patient Spider Lines: 43 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <20-09-028@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="64671"; mail-complaints-to="abuse@iecc.com" Keywords: code, optimize, question Posted-Date: 10 Sep 2020 20:14:09 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:2599 There is a lot of research and a lot of resources on the high-level aspects of register allocation--colouring interference graphs, lifetimes, CFGs, etc. But there are a lot of low-level architecture-specific things that these models don't account for on their own. Most notably, not all registers can be used for the same things. Just on amd64: - Multiplication and division use the rdx:rax register pair. - Bit shifts always use cl. - When calling functions, their arguments have to go in specific registers. In all of these cases, you can spill whatever happens to already be in those registers, but it would be nicer if you could arrange for the appropriate values to already be in the right places. But how? A naive solution to the first two problems just makes rax/rcx/rdx the lowest-priority registers except when doing a multiply/divide/shift; and spills only if necessary (rare). But that's not a general solution (imagine if every register has a few pieces of unique functionality), and function calls reserve too many registers for that strategy to be practical in that case. Bonus microconsiderations (these seem much easier to model, but still not trivial): - Some registers need a special prefix to be used (REX prefix). These registers are generally different from the special-purpose registers (for e.g. multiplication). Is it better to put a non-multiplied value in a REX-prefixed register, or keep it in an unprefixed register and spill it later when you need to multiply? - The second-lowest 8 bits of some registers can be addressed separately. When does it make sense to use them? (All of these are x86-specific, and most architectures admittedly have fewer esotericisms.) -- time flies like an arrow; fruit flies like a banana