From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 121026 invoked by alias); 15 Dec 2017 04:59:04 -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 121015 invoked by uid 89); 15 Dec 2017 04:59:03 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=2.0 required=5.0 tests=BAYES_00,FORGED_MUA_MOZILLA,INVALID_MSGID,KAM_LAZY_DOMAIN_SECURITY,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS autolearn=no version=3.3.2 spammy=UD:twimg.com, pbstwimgcom, UD:pbs.twimg.com, pbs.twimg.com X-HELO: smtpbg65.qq.com Received: from smtpbg65.qq.com (HELO smtpbg65.qq.com) (103.7.28.233) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 15 Dec 2017 04:58:58 +0000 X-QQ-mid: bizesmtp9t1513313928ts3vkkncv Received: from iSOFT.localdomain (unknown [114.247.223.226]) by esmtp4.qq.com (ESMTP) with id ; Fri, 15 Dec 2017 12:58:47 +0800 (CST) X-QQ-SSF: 00100000002000F0FI50B00A0000000 X-QQ-FEAT: 8+141AWVx0RJWDLUV6cxhcgKRtJMWRdkYXmC0aEulnfK/Tgw4bLRXqyxDGuH9 +8INgKKqMKa+hBmyCacYJ0yxBq/oYcrbB+uMaoYh69z52pirtOB6w3j53RdxZeadbzrvcbM 9mnIqD1K2FIr3pKyo3azn6fv5+Q/qWTWoNXkChGzZTH5pk1hO+Pma/uOr2LpX1askTNT+p9 lTbTQwd1Vni7aQvcWh0hl72pn6+oho5adRkYtndgVHBQDrh4VDPGcvFox3c5e8CYWS21lAs 68JBGAnSyl8M+8Qs+is1l96fM= X-QQ-GoodBg: 0 Subject: Re: Register Allocation Graph Coloring algorithm and Others To: Vladimir Makarov , LewisR9@cf.ac.uk, dag@cray.com, stoklund@2pi.dk Cc: GCC Development , LLVM Developers Mailing List References: From: Leslie Zhai Message-ID: +F73FED2BC3BCA3FE Date: Fri, 15 Dec 2017 04:59: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: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-QQ-SENDSIZE: 520 Feedback-ID: bizesmtp:llvm.org.cn:qybgforeign:qybgforeign2 X-QQ-Bgrelay: 1 X-SW-Source: 2017-12/txt/msg00085.txt.bz2 Hi Vladimir, Thanks for your kind and very detailed response! 在 2017年12月15日 12:40, Vladimir Makarov 写道: > > > On 12/14/2017 10:18 PM, Leslie Zhai wrote: >> Hi GCC and LLVM developers, >> >> I am learning Register Allocation algorithms and I am clear that: >> >> * Unlimited VirtReg (pseudo) -> limited or fixed or alias[1] PhysReg >> (hard) >> >> * Memory (20 - 100 cycles) is expensive than Register (1 cycle), but >> it has to spill code when PhysReg is unavailable >> > It might be much less if memory value is in L1 cache. >> * Folding spill code into instructions, handling register >> coallescing, splitting live ranges, doing rematerialization, doing >> shrink wrapping are harder than RegAlloc >> > RegAlloc is in a wide sense includes all this tasks and more.  For > some architectures, other tasks like a right live range splitting > might be even more important for generated code quality than just > better graph coloring. >> * LRA and IRA is default Passes in RA for GCC: >> >> $ /opt/gcc-git/bin/gcc hello.c >> DEBUG: ../../gcc/lra.c, lra_init_once, line 2441 >> DEBUG: ../../gcc/ira-build.c, ira_build, line 3409 >> >> * Greedy is default Pass for LLVM >> >> But I have some questions, please give me some hint, thanks a lot! >> >> * IRA is regional register allocator performing graph coloring on a >> top-down traversal of nested regions, is it Global? compares with >> Local LRA > IRA is a global RA.  The description of its initial version can be found > > https://vmakarov.fedorapeople.org/vmakarov-submission-cgo2008.pdf I am reading this paper at present :) > > > LRA in some way is also global RA but it is a very simplified version > of global RA (e.g. LRA does not use conflict graph and its coloring > algoritm is closer to priority coloring).  LRA does a lot of other > very complicated things besides RA, for example instruction selection > which is quite specific to GCC machine description. Usually code > selection task is a separate pass in other compilers. Generally > speaking LRA is more complicated, machine dependent and more buggy > than IRA.  But fortunately LRA is less complicated than its > predecessor so called reload pass. > > IRA and LRA names have a long history and they do not reflect > correctly the current situation. > > It would be possible to incorporate LRA tasks into IRA, but the final > RA would be much slower, even more complicated and hard to maintain > and the generated code would be not much better.  So to improve RA > maintainability, RA is divided on two parts solving a bit different > tasks.  This is a typical engineering approach. I am debugging by printf to be familiar with LRA and IRA. > >> >> * The papers by Briggs and Chaiten contradict[2] themselves when >> examine the text of the paper vs. the pseudocode provided? > I don't examine Preston Briggs work so thoroughly.  So I can not say > that is true.  Even so it is natural that there are discrepancy in > pseudocode and its description especially for such size description. > > For me Preston Briggs is famous for his introduction of optimistic > coloring. >> >> * Why  interference graph is expensive to build[3]? >> > That is because it might be N^2 algorithm.  There are a lot of > publications investigating building conflict graphs and its cost in RAs. >> And I am practicing[4] to use HEA, developed by Dr. Rhydian Lewis, >> for LLVM firstly. >> > When I just started to work on RAs very long ago I used about the same > approach: a lot of tiny transformations directed by a cost function > and using metaheuristics (I also used tabu search as HEA). Nothing > good came out of this. Thanks for your lesson! But are there some benchmarks when you used Tabu search as HEA, AntCol, etc. such as https://pbs.twimg.com/media/DRD-kxcUMAAxZec.jpg > > > If you are interesting in RA algorithms and architectures, I'd > recommend Michael Matz article > > ftp://gcc.gnu.org/pub/gcc/summit/2003/Graph%20Coloring%20Register%20Allocation.pdf > > > as a start point. Thanks! I am reading it. >> >> [1] https://reviews.llvm.org/D39712 >> >> [2] http://lists.llvm.org/pipermail/llvm-dev/2008-March/012940.html >> >> [3] https://github.com/joaotavio/llvm-register-allocator >> >> [4] https://github.com/xiangzhai/llvm/tree/avr/include/llvm/CodeGen/GCol >> > -- Regards, Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/