From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 69078 invoked by alias); 20 Dec 2017 17:25:44 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 69067 invoked by uid 89); 20 Dec 2017 17:25:44 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=3.1 required=5.0 tests=BAYES_00,HTML_MESSAGE,KAM_SHORT,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.2 spammy=conference, optimum, Conference, H*F:D*dk X-HELO: homiemail-a114.g.dreamhost.com Received: from sub5.mail.dreamhost.com (HELO homiemail-a114.g.dreamhost.com) (208.113.200.129) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 20 Dec 2017 17:25:42 +0000 Received: from homiemail-a114.g.dreamhost.com (localhost [127.0.0.1]) by homiemail-a114.g.dreamhost.com (Postfix) with ESMTP id 9D36148000A2F; Wed, 20 Dec 2017 09:25:37 -0800 (PST) Received: from jolesen-macbook.pk5001z (184-100-150-189.ptld.qwest.net [184.100.150.189]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) (Authenticated sender: stoklund@2pi.dk) by homiemail-a114.g.dreamhost.com (Postfix) with ESMTPSA id 13BB348000A2E; Wed, 20 Dec 2017 09:25:37 -0800 (PST) From: Jakob Stoklund Olesen Message-Id: Mime-Version: 1.0 (Mac OS X Mail 11.2 \(3445.5.20\)) Subject: Re: Register Allocation Graph Coloring algorithm and Others Date: Wed, 20 Dec 2017 17:25:00 -0000 In-Reply-To: <80f8f21c-7e07-903c-7557-09ef186ad3ef@llvm.org.cn> Cc: Matthias Braun , dag@cray.com, vmakarov@redhat.com, LewisR9@cf.ac.uk, LLVM Developers Mailing List , GCC Development To: Leslie Zhai References: <9CBFCADA170A6854@apple.com> <6708A731-203E-4096-8137-85D4104DA035@apple.com> <80f8f21c-7e07-903c-7557-09ef186ad3ef@llvm.org.cn> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-SW-Source: 2017-12/txt/msg00134.txt.bz2 > On Dec 18, 2017, at 19:03, Leslie Zhai wrote: Hi Leslie, As others have pointed out, the notion that register allocation is isomorph= ic to graph coloring is poppycock. There are other important aspects, in pa= rticular the placement of spill/fill/copy instructions. The importance of g= raph coloring relative to spill code placement depends on how many register= s you have available. If you are generating code for 32-bit x86 which has o= nly 6-7 general purpose registers, you will have so much spill code and sho= rt live ranges that graph coloring doesn=E2=80=99t matter much at all. On t= he other hand, if you have 32 registers like Chaitin did, you have much les= s spilling in typical code, and the graph coloring aspect becomes important. Early compilers would keep each local variable in a stack slot, and the reg= ister allocation optimization would literally allocate a whole local variab= le to a register. The C =E2=80=9Cregister=E2=80=9D keyword makes sense in t= hat context. Later improvements like copy coalescing and live range splitti= ng meant that multiple local variables could use the same register and a va= riable could live in different places at different times. It is sometimes u= seful to take this development to its logical extreme and look at register = allocation as a caching problem: The register allocator=E2=80=99s job is to= make sure that values are available to the instructions the need them, usi= ng the registers as a cache to get the values there in the most efficient w= ay possible. Guo, J., Garzar=C3=A1n, M. J., & Padua, D. (2004). The Power of Belady=E2= =80=99s Algorithm in Register Allocation for Long Basic Blocks. In Language= s and Compilers for Parallel Computing (Vol. 2958, pp. 374=E2=80=93389). Be= rlin, Heidelberg: Springer Berlin Heidelberg. http://doi.org/10.1007/978-3-= 540-24644-2_24 Braun, M., & Hack, S. (2009). Register spilling and live-range splitting fo= r SSA-form programs. International Conference on Compiler Construction. When you look at register allocation that way, the graph coloring aspect al= most disappears. The optimum approach is probably somewhere in the middle. A third important aspect is register constraints on individual instructions= . Sometimes you almost need a little constraint solver just to figure out a= valid register assignment for a single instruction. Preston Briggs dealt w= ith this in his thesis, but it hasn=E2=80=99t gotten as much attention as g= raph coloring since. Pereira, F. Q., & Palsberg, J. (2008). Register allocation by puzzle solvin= g. Regards, /jakob