similar to: [LLVMdev] Need help for my PBQP regAlloc proj in llvm....

Hi Prasad, The comments at the beginning of RegAllocPBQP.cpp list the two most relevant papers for PBQP register allocation. // (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with // PBQP. In Proceedings of the 7th Joint Modular Languages Conference // (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. // // (2) Scholz, B., Eckstein, E.

Hi Duncan, >> New PBQP solver. > > nice! Any chance of a quick summary of the state of the pbqp allocator and > who might want to use it? Sure. Here's an update, broken into three handy sections: Summary for LLVM users: --- PBQP is a heavyweight register allocator. A quick, not-at-all scientific look at SPEC2006 shows that compiling with -regalloc=pbqp increased runtime

Hi All, I've just committed some changes to the PBQP allocator which are designed to make it easier to implement custom register allocation constraints. This is a quick summary of those changes, and of the status of the PBQP allocator in general. First a quick bit of background: The PBQP allocator is based on ideas described in [1]. I implemented this algorithm (with the improved heuristic

Fernando Magno Quintao Pereira wrote: > Yes, I have a tech report on this page: > > http://compilers/fernando/projects/soc/ Cool. I'm also interested in the Chordal Graph allocator. Are you planning to integrate it into the main llvm repository? It would make an interesting research project to compare allocation algorithms on real-world machines.

Hi everyone, This is a quick status update regarding the PBQP (Partitioned Boolean Quadratic Programming) register allocator. A quick overview of the project: PBQP is a heavyweight allocation technique intended for native code compilation, and compilation of performance critical sections. It works by modeling register allocation problems as PBQP problems, solving these using a generic solver, and

> > What do you think about this approach? Whould it be interesting to > implement something like that for LLVM? May be you already have > considered something like that? Are there any plans to it? We have talked about whole function instruction selection but does not have immediate plan to implement it. If we were to implement it today, it would probably be done on DAGs with

Hi, LLVM already uses dynamic-programming based optimal pattern matching selectors for some of the target architectures. But as far as I know, the code is first converted out of the SSA form, before the selection process takes place. The same approach is used by many other compilers. But there is an article from Erik Eckstein, where a different method is proposed. In the described approach, the

On 4/3/07, David Greene <greened at obbligato.org> wrote: > > I'm just starting to dive into llvm, hoping to implement a > good graph coloring register allocator. I gather that this > has been discussed before. > > What is the RegAllocGraphColoring.cpp currently in the > sources? It seems to be the Fred Chow algorithm but > it's not mentioned in the

Hi all. I’ve heard a couple of times that some of the problems solved by various passes in the optimizer are indeed NP-hard, even though the instances are small enough to be tractable (and very quickly). Is this true? If so, which are these problems? Register allocation? Instruction scheduling? Are they solved exactly or by approximations? Or not solved at all (the need of solving them is

Hi All, I finally had a chance to get back to my pbqp trials, now using the 3.0 release. I still hit the same assert : "Attempting to spill already spilled value." This is triggered because in RegAllocPBQP::mapPBQPToRegAlloc, a vreg node is either : - a physical register (problem.isPRegOption(vreg, alloc)), - or a spill (problem.isSpillOption(vreg, alloc)) The problem is that pass

Hi Lang, > From memory your target is not public, so I won't be able to reproduce > the crash myself. Is that correct? Correct. > If that's the case, I could add functionality to dump the PBQP graphs > during allocation. I think they should give me enough information to > debug the issue. Would you be able to share the PBQP graphs? I can share the pbqp graph if you send

Hi Arnaud, Thanks for attaching those files. I'll take a look at them. Commit r153483 adds an option to the PBQP allocator, "-pbqp-dump-graphs", to dump the PBQP graph for each round of each function in a compilation unit. The generated files are named "<module id>.<function>.<round>.pbqpgraph", and contain a simple text representation of the PBQP graph.

Hi Jakob, > Out of curiosity, how are you dealing with live range splitting and > coalescing in PBQP? I know you added the LoopSplitter pass. > > For linear scan in LLVM we are going in the direction of aggressive > coalescing before allocation, and on-demand splitting during allocation. > > I know that other allocators use no early coalescing, and coalesce during >

On Sep 20, 2010, at 7:53 AM, Lang Hames wrote: > I've just committed some changes to the PBQP allocator which are designed to make it easier to implement custom register allocation constraints. This is a quick summary of those changes, and of the status of the PBQP allocator in general. Thanks, Lang! Out of curiosity, how are you dealing with live range splitting and coalescing in PBQP?

Hi, Please see the two ".ll' files attached. Command line used llc -march=pic16 -pre-RA-sched=list-burr -regalloc=pbqp new.obc The above test case crashes only when I use the combination of list-burr scheduler and pbqp register allocator. If any of them (scheduler or register allocator) is replaced with some alternate then I don't see the crash. I could not figure

Hi, I would like to ask about PBQPs use of InlineSpiller. The code output when using PBQP gets a lot bigger compared to when using RegAllocGreedy. PBQP does not split the live intervals, and a lot more (often redundant) reload instructions are emitted as a result, it seems. I wonder why this is, and if there are any plans to improve on this point? /Jonas Paulsson -------------- next part

This is a known issue with the current PBQP data structures. I'm working on an overhaul of the PBQP allocator at the moment which should address this. - Lang. On Sat, Oct 20, 2012 at 2:08 PM, Benjamin Kramer <benny.kra at gmail.com>wrote: > > On 20.10.2012, at 22:47, Jordan Rose <jordan_rose at apple.com> wrote: > > > Hi, everyone. Today I was trying to build LLVM

Hi all, I was wondering about whether the PBQP register allocator is likely to be maintained in the future. It's proving to be a nice way to encode some instruction encoding constraints for an out-of-tree backend we have, but there's concern about it being abandoned or bitrotting in the future. Also, if PBQP is likely to lapse out of regular maintenance in the future, is there a simple

This looks like a bug in the PBQP solver. I'm currently investigating. Cheers, Lang. On Thu, Nov 12, 2009 at 12:46 AM, <Sachin.Punyani at microchip.com> wrote: > Hi, > > > > Please see the two “.ll’ files attached. > > > > Command line used > > llc –march=pic16  –pre-RA-sched=list-burr –regalloc=pbqp new.obc > > > > The above test case

Hi All, My target has some instructions requiring register pairs. I decided to give a try to the PBQP allocator : it is working fine in 99% of the cases, but I am stumbling on the following issue. Instruction 'MPQD' takes 3 register operands inputs, with the constraint that operands 0 and 2 must be consecutive registers. Operand 1 has no particular constraint. It has no output register.