From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 43524 invoked by alias); 21 Dec 2017 16:26:15 -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 43438 invoked by uid 89); 21 Dec 2017 16:26:13 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=4.7 required=5.0 tests=BAYES_50,FORGED_MUA_MOZILLA,INVALID_MSGID,KAM_LAZY_DOMAIN_SECURITY,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS autolearn=no version=3.3.2 spammy=conference, optimum, Conference, guo X-HELO: smtpbgau2.qq.com Received: from smtpbgau2.qq.com (HELO smtpbgau2.qq.com) (54.206.34.216) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 21 Dec 2017 16:26:07 +0000 X-QQ-mid: bizesmtp13t1513873555tfkuavow Received: from [192.168.1.10] (unknown [111.197.235.205]) by esmtp4.qq.com (ESMTP) with id ; Fri, 22 Dec 2017 00:25:53 +0800 (CST) X-QQ-SSF: 00100000000000F0FJ60 X-QQ-FEAT: GY6suCwCPSv5BCSiIpj+zPwwt9rlypVq295fXeVc/aaK8fVt2TbAibgf7WcDF IuGJshHCR8wZYID8IKkqNdFoVfxXXQWoj/cszTpqexb83fifFMJqx4yvGuuqdFlNqpQkGA/ 8zkqqz6ib3O0kqz1h1Vgj0K19RuslG4p6wz8dqLAcyYqa+JOOld1Z8ZiHg0vtHyBQEOXoMU NsVUX05t+7SdrfdU0C1uiMMMrwlqSG4twtWBy3QQyqKjJg7XCudzq87HIcd+3AzcVlXsTwn gnqQTaINQL5B5efANBYx6FpChMkZ3YxZzS2w== X-QQ-GoodBg: 0 Subject: Re: [llvm-dev] Register Allocation Graph Coloring algorithm and Others To: Bruce Hoult Cc: Jakob Stoklund Olesen , GCC Development , LLVM Developers Mailing List , dag@cray.com, vmakarov@redhat.com, LewisR9@cf.ac.uk, Alex Bradbury References: <9CBFCADA170A6854@apple.com> <6708A731-203E-4096-8137-85D4104DA035@apple.com> <80f8f21c-7e07-903c-7557-09ef186ad3ef@llvm.org.cn> <5a3b03ec.01da9f0a.1934a.4b3bSMTPIN_ADDED_BROKEN@mx.google.com> From: Leslie Zhai Message-ID: <89cd7f97-dfa3-3a8c-8d23-6c10ec731274@llvm.org.cn>+18D20B22B795DF4F Date: Thu, 21 Dec 2017 16:26: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:qybgforeign4 X-QQ-Bgrelay: 1 X-SW-Source: 2017-12/txt/msg00142.txt.bz2 Hi Bruce, Thanks for your sharing! I am porting GlobalISel to RISCV target[1], the highest priority in the TODO list[2], welcome to contribute to lowRISC, if fixed all the issues, then I could try to implement RegAllocGraphColoring in HEA and write great Machine Schedulers. [1] https://github.com/lowRISC/riscv-llvm/issues/19 [2] https://github.com/lowRISC/riscv-llvm/issues 在 2017年12月21日 19:09, Bruce Hoult 写道: > So, both AVR and RISC-V are fairly register-rich with usually 32. > RV32E only has 16, but that's still a lot better than i386. If you use > a lot of 16 bit integers then AVR also only has effectively 16 > registers (or a more with a mix of 8 and 16 bit variables). 32 bit > integers should be rare in AVR code, but soft float/double variables > are common in Arduino code (both are implemented as 32 bits), so you > only have room for 8 of those. > > RISC-V doesn't have any hard constraints on something that *must* go > in a certain register, except the usual argument passing/return > convention. There is a an advantage to allocating both the data > src/dst register and the pointer base register for a load or store > from x8-x15 (s0-1,a0-5) as much as possible as this allows the > assembler to use a two byte instruction instead of a four byte > instruction. > > I haven't look at AVR in detail for a while, but I seem to recall the > top six registers make up three 16 bit pointer registers X,Y,Z. Any of > them can be used for (C language) *p, *--p, *p++, only Y&Z can be used > for p->foo, and only Z can be used for computed jumps (including > function link register) or loading constants from program memory. Also > the various multiply instructions take their 8 bit operands from any > registers but always produce the 16 bit result in r1:r0. Annoying but > nowhere near as bad as i386 as r0 and r1 are not used for anything > else. The usual ABI makes r0 a clobber-at-will temp. r1 is supposed to > be "always zero", so you need to CLR it after retrieving (or ignoring) > the high bits of a multiply result. > > On Thu, Dec 21, 2017 at 3:44 AM, Leslie Zhai via llvm-dev > > wrote: > > Hi Jakob, > > Thanks for your kind response! > > My usecase is for AVR and RISCV targets, and I just want to learn > and practice HEA in RA, thanks for your sharing. > > > 在 2017年12月21日 01:25, Jakob Stoklund Olesen 写道: > > > On Dec 18, 2017, at 19:03, Leslie Zhai > > >> wrote: > > > Hi Leslie, > > As others have pointed out, the notion that register > allocation is isomorphic to graph coloring is poppycock. There > are other important aspects, in particular the placement of > spill/fill/copy instructions. The importance of graph coloring > relative to spill code placement depends on how many registers > you have available. If you are generating code for 32-bit x86 > which has only 6-7 general purpose registers, you will have so > much spill code and short live ranges that graph coloring > doesn’t matter much at all. On the other hand, if you have 32 > registers like Chaitin did, you have much less spilling in > typical code, and the graph coloring aspect becomes important. > > Early compilers would keep each local variable in a stack > slot, and the register allocation optimization would literally > allocate a whole local variable to a register. The C > “register” keyword makes sense in that context. Later > improvements like copy coalescing and live range splitting > meant that multiple local variables could use the same > register and a variable could live in different places at > different times. It is sometimes useful to take this > development to its logical extreme and look at register > allocation as a caching problem: The register allocator’s job > is to make sure that values are available to the instructions > the need them, using the registers as a cache to get the > values there in the most efficient way possible. > >     Guo, J., Garzarán, M. J., & Padua, D. (2004). The Power of >     Belady’s Algorithm in Register Allocation for Long Basic > Blocks. >     In Languages and Compilers for Parallel Computing (Vol. > 2958, pp. >     374–389). Berlin, 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 for SSA-form programs. International Conference on >     Compiler Construction. > > > When you look at register allocation that way, the graph > coloring aspect almost 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 with this in his > thesis, but it hasn’t gotten as much attention as graph > coloring since. > >     Pereira, F. Q., & Palsberg, J. (2008). Register allocation by >     puzzle solving. > > > Regards, > /jakob > > > -- > Regards, > Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/ > > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev@lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > -- Regards, Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/