Re: [llvm-dev] Register Allocation Graph Coloring algorithm and Others

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://gith

Re: [llvm-dev] Register Allocation Graph Coloring algorithm and Others

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 c

Re: Register Allocation Graph Coloring algorithm and Others

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 Les

Re: Register Allocation Graph Coloring algorithm and Others

> 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 col

Re: [llvm-dev] Register Allocation Graph Coloring algorithm and Others

> On Dec 18, 2017, at 8:16 PM, Vladimir Makarov via llvm-dev > wrote: > > > > 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,

Re: Register Allocation Graph Coloring algorithm and Others

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

Re: [llvm-dev] Register Allocation Graph Coloring algorithm and Others

Hi Matthias, Thanks for your hint! It is just for learning and practicing for me, just like migrate DragonEgg http://lists.llvm.org/pipermail/llvm-dev/2017-September/117201.html the motivating is for learning from GCC and LLVM developers. 在 2017年12月19日 10:07, Matthias Braun 写道: On Dec 1

Re: Register Allocation Graph Coloring algorithm and Others

Hi Michael, Thanks for your sharing! I will read the papers as you suggested, and I asked Quantum Computing professionals about solving the NP-complete problem https://github.com/epiqc/ScaffCC/issues/14 but GCC's IRA and LRA proved that there is a solution in SSA form for classical computer.

Re: Register Allocation Graph Coloring algorithm and Others

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

Re: Register Allocation Graph Coloring algorithm and Others

Leslie Zhai writes: > But I like to practice and learn :) > https://github.com/xiangzhai/llvm/blob/avr/lib/CodeGen/RegAllocGraphColoring.cpp#L327because > theory is not always correct, or misunderstood by people, so I > want to compare solutionByHEA, IRA, Greedy, PBQP and other algorithms. That

Re: Register Allocation Graph Coloring algorithm and Others

Hi David, Thanks for your teaching! I am a newbie in compiler area, I only learned Compiler Principle in 2002 https://www.leetcode.cn/2017/12/ilove-compiler-principle.html But I like to practice and learn :) https://github.com/xiangzhai/llvm/blob/avr/lib/CodeGen/RegAllocGraphColoring.cpp#L32

Re: Register Allocation Graph Coloring algorithm and Others

Leslie Zhai writes: > * Memory (20 - 100 cycles) is expensive than Register (1 cycle), but > it has to spill code when PhysReg is unavailable As Vladimir said, the cache makes this kind of analysis much more tricky. It's not necessarily the case that memory=bad and register=good. Since there a

Re: Register Allocation Graph Coloring algorithm and Others

On 12/14/17 9:18 PM, Leslie Zhai wrote: > * The papers by Briggs and Chaiten contradict[2] themselves when examine > the text of the paper vs. the pseudocode provided? I've read both of these papers many times (in the past) and I don't recall any contradictions in them. Can you (Dave?) be more sp

Re: Register Allocation Graph Coloring algorithm and Others

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

Re: Register Allocation Graph Coloring algorithm and Others

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

Register Allocation Graph Coloring algorithm and Others

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 * Fo