search for: pbqp

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

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. The PBQP allocato...

Hi Quentin, Jonas, Splitting fits in with PBQP reasonably well, at least conceptually. The PBQP graph is designed to be mutable, so there is no problem with updating it when splitting. As I see it, there are two logical places to integrate splitting into PBQP: 1) Split during spilling -- If a PBQP solution selects the spill option for a node,...

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 me a patch with the added functionality you want. On my side, I already checked the node cost for this register,...

...re the graph, with a global view, and later on use use trySplit (or an equivalent) to handle the local coloring issues. From: Quentin Colombet [mailto:qcolombet at apple.com] Sent: 09 March 2015 23:08 To: Lang Hames Cc: Jonas Paulsson; llvmdev at cs.uiuc.edu; Arnaud De Grandmaison Subject: Re: PBQP spilling Hi Lang, Thanks for the clarifications. On Mar 9, 2015, at 2:30 PM, Lang Hames <lhames at gmail.com> wrote: Hi Quentin, Jonas, Splitting fits in with PBQP reasonably well, at least conceptually. The PBQP graph is designed to be mutable, so there is no problem with...

...ll complete, and the edge between Y and Z will have been added again in handleAddEdge(), and Z:DeniedOpts is again 8! I think this also shows up in a test case for arm. It was found by using the assert mentioned above, and running 'bin/llvm-stress -size 200 -seed 17761'. The attached file (pbqp_reduced.ll) is the failing test case found reduced with bugpoint. Apply patch 2 (the assert), and then run 'llc pbqp_reduced.ll -mtriple=aarch64-none-linux-gnu -mcpu=cortex-a57 -mattr=+neon -optimize-regalloc -regalloc=pbqp'. The assert shows a node that is spilled that was conservatively a...

...as possible. The log of the run and the dumped graphes are attached. Cheers, -- Arnaud de Grandmaison On Tuesday, March 27, 2012 01:20:35 Lang Hames wrote: > 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 grap...

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 t...

...2012 17:30:33 Lang Hames wrote: > Hi Arnaud, > > Apologies for the delayed reply. > > Thank you for the excellent test case - it exposed a subtle bug in the > colorability heuristic. This has been fixed in r153958. > > In case you are curious, the bug was as follows: the PBQP solver applies > applies a simplification step to each matrix. When all elements of a matrix > row or column are equal, the value for those elements is "pushed out" to > the corresponding element of the cost vector, and the row/column is zeroed > out. This is an attempt to tur...

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 > allocation....

...ed to modify the 'ensure pairable' pass (the pass undoing some of the coalescer's work) to always insert register copies for instructions with the pairable constraint, instead of being smart and inserting the copy only when needed. This had no visible effect. Although I am deriving from PBQPBuilder, the PBQP seems to be coalescing some register copy, without taking into account that the source or dest reg may have different constraints. In which part of pbqp would this be happening ? Cheers, -- Arnaud de Grandmaison On 04/05/2012 05:23 PM, Arnaud de Grandmaison wrote: > Hi Lang, &...

Hi, I have worked a little on the PBQP register allocator, and it is quite clear (at least to me) that it is not even a serious alternative to RegAllocGreedy at the moment, due to the poor handling of spilling. As Arnaud wrote below, it is not optimizing spilling at all, but rather just spills anything that does not get an assignment. T...

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.isSpillO...

Hi Arnaud, Apologies for the delayed reply. Thank you for the excellent test case - it exposed a subtle bug in the colorability heuristic. This has been fixed in r153958. In case you are curious, the bug was as follows: the PBQP solver applies applies a simplification step to each matrix. When all elements of a matrix row or column are equal, the value for those elements is "pushed out" to the corresponding element of the cost vector, and the row/column is zeroed out. This is an attempt to turn the matrices into...

...this is sufficient, especially when the node degree > available registers. Cheers, Arnaud From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Lang Hames Sent: 27 January 2015 06:06 To: Jonas Paulsson Cc: llvmdev at cs.uiuc.edu Subject: Re: [LLVMdev] PBQP crash Hi Jonas, > * The problematic node that was spilled again, was in the ConservativelyAllocatableNodes set during reduce(). The comment in reduce() “Conservatively allocatable nodes will never spill…” indicates that perhaps this is an incorrect insertion, as the regs did in fact run...

...9;ensure pairable' pass (the pass undoing some > of the coalescer's work) to always insert register copies for > instructions with the pairable constraint, instead of being smart and > inserting the copy only when needed. This had no visible effect. > Although I am deriving from PBQPBuilder, the PBQP seems to be coalescing > some register copy, without taking into account that the source or dest > reg may have different constraints. In which part of pbqp would this be > happening ? > > If you're deriving PBQPBuilder (and not PBQPBuilderWithCoalescing) then PB...

Hi Arnaud, LiveInterval::markNotSpillable() sets the live interval's spill weight to infinity. For well-formed PBQP graphs (i.e. ones that have some finite-cost solution), PBQP should never chose to spill such an interval. The two possibilities for this crash are that the input graph has no finite-cost solution, or that you've exposed a bug in the PBQP solver. >From memory your target is not public, so I...

Hi Sachin, Confirmed: This is being caused by a subtle issue in the heuristic PBQP solver. Specifically: R1/R2 reductions as currently implemented can, on rare occasions, lead to the heuristic solver failing to find a finite cost solution, even though one exists. The infinite cost solution will always be in violation of some rule of register allocation (failing to handle an inter...

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? I...

...to work on the solution for this. Regards Sachin > -----Original Message----- > From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On > Behalf Of Sachin.Punyani at microchip.com > Sent: Tuesday, November 17, 2009 12:00 PM > Subject: Re: [LLVMdev] Crash in PBQP register allocator > > Thanks Lang! > > I think we can use linear scan as work around for short term. > > Thanks for your help. > > Regards > Sachin > > > -----Original Message----- > > From: Lang Hames [mailto:lhames at gmail.com] > > Sent: Sund...