From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 42341 invoked by alias); 19 Dec 2017 04:16:52 -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 40647 invoked by uid 89); 19 Dec 2017 04:16:49 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.9 required=5.0 tests=BAYES_00,KAM_LAZY_DOMAIN_SECURITY,SPF_HELO_PASS,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=H*f:sk:62E4178, H*i:sk:62E4178, sk:www.res, sk:wwwres X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 19 Dec 2017 04:16:48 +0000 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 2537B8046E; Tue, 19 Dec 2017 04:16:46 +0000 (UTC) Received: from [10.10.121.10] (ovpn-121-10.rdu2.redhat.com [10.10.121.10]) by smtp.corp.redhat.com (Postfix) with ESMTP id 3B50112A5F; Tue, 19 Dec 2017 04:16:43 +0000 (UTC) Subject: Re: Register Allocation Graph Coloring algorithm and Others To: Michael Clark , Leslie Zhai Cc: LewisR9@cf.ac.uk, dag@cray.com, stoklund@2pi.dk, GCC Development , LLVM Developers Mailing List References: <615F0DCE4D5873A9@mac.com> <62E41783-1145-4036-9FD4-75D3B0C22DE6@mac.com> From: Vladimir Makarov Message-ID: Date: Tue, 19 Dec 2017 04:16:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.4.0 MIME-Version: 1.0 In-Reply-To: <62E41783-1145-4036-9FD4-75D3B0C22DE6@mac.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2017-12/txt/msg00119.txt.bz2 On 12/18/2017 07:07 PM, Michael Clark wrote: > Hi Leslie, > > I suggest adding these 3 papers to your reading list. > > Register allocation for programs in SSA-form > Sebastian Hack, Daniel Grund, and Gerhard Goos > http://www.rw.cdl.uni-saarland.de/~grund/papers/cc06-ra_ssa.pdf > > Simple and Efficient Construction of Static Single Assignment Form > Matthias Braun , Sebastian Buchwald , Sebastian Hack , Roland Leißa , Christoph Mallon , and Andreas Zwinkau > https://www.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf > > Optimal register allocation for SSA-form programs in polynomial time > Sebastian Hack, Gerhard Goos > http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoos-ipl06.pdf > > A lot of the earlier literature regarding the register allocation problem describes the general graph colouring problem as NP-complete, however previous research in Register Allocation has been in the context of programs that were not in SSA form. i.e. the Chaitin-Briggs paper states that register allocation is NP-complete and proposes an iterative algorithm. > > I am sceptical about SSA-register allocators for high quality code generation.  But I should acknowledge although I tried a lot of RA algorithms I never tried SSA one. One task of RA is to deal with moves but when you are destroying SSA you are creating moves or swaps.  Of course there are optimizations to decrease its number when you are going out of SSA.  But IMHO a good RA should see all moves created before or during own work. As I already wrote coloring is just one out of many task of RA.  All these tasks in a good RA should be solved in cooperation. Optimistic coloring is good and fast enough (although building a conflict graph for it takes a lot of time).  I think better results can be obtained by improving other tasks than by improving optimistic coloring. For example, nobody mentioned irregular file architectures (with subregisters and register subclasses) like x86/x86-64.  Even regular file architectures with caller/callee saved hard registers have irregularity because it creates register subclasses, e.g. class of saved general registers is a subclass of the overall general register class.  Usually hard registers are present in IR and if some pseudos conflict with the hard registers, it also create a lot (intersected) subclasses. Taking such irregularity, e.g. in coloring criteria based on Kempe's heuristic, can improve the final RA significantly (as I remember GCC generated code for SPECInt2000 even on ppc64 with mostly regular register file was improved by 1% by taking such subclasses into account during coloring). A classical article about this https://www.researchgate.net/publication/2440424_Graph-Coloring_Register_Allocation_for_Irregular_Architectures could be a start point for such implementation.