similar to: [LLVMdev] PBQP spilling

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. The result is a lot more spill/reload instructions than

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, rather than spill immediately, split the interval

Both approaches are not exclusive. I would even think it makes sense to have a pre-split pass to prepare 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:

> A node should never be put into the conservatively allocatable list if there is a chance of it spilling. I can understand why the logic of NodeMetadata::isConservativelyAllocatable is necessary for the node to be allocatable, but I have not been able to convince myself this is sufficient, especially when the node degree > available registers. Cheers, Arnaud From:

Hi Arnaud, The conservatively allocatable test is supposed to check two conditions, either of which would be sufficient to make a node allocatable: (1) There exists some register that is not aliased by any register option for any neighbor. This is the "safe row" test. It is straightforward, but likely to fire only rarely. (2) The sum of the maximum number of registers aliased by any

Hi, I have run into a test case on an out-of-tree target where PBQP fails to complete register allocation after "Attempting to spill already spilled value" (the triggered assert in InlineSpiller::spill(). First, the original LiveInterval is spilled. It is a load of a symbol into a narrow register class, i.e. a subset of the class of address registers. InlineSpiller decides to

Hi, Sorry for the delay, it has taken some extra time as more than one bug showed up ☺ I continued to look into this with your viewpoint that a node that is conservatively allocatable should never be spilled. The first thing I did was therefore to add some extra code with an assert for this. I believe I then found three bugs and fixed the two: Bug 1: Incorrect transpositions in handleAddEdge()

Hi Jonas, Thanks for your patience. After spending some time looking at the additional output you gave me, I agree that your fix is the right one. I was worried that this problem may arise because we were spilling not real user, but in fact what I thought was the problem is an optimization we could do :). See my comments inlined for a few nitpicks before you commit. Thanks again, -Quentin On

Hi, I have encountered a test case where InlineSpiller generates bad code. A register is reloaded but never spilled, and I suspect a bug in InlineSpiller. A register is live over a loop that also have two inner loops. It is not used or defined over the inner loops. It is split into two sibling registers, where one covers just the inner loops interval, which is then spilled. In spill(),

Hi Quentin, I have tried to find a test case for an official target, but failed. It seems to be a rare case. To do it, I added the 'else' clause in the following: ... if (VNI->def == OrigVNI->def) { DEBUG(dbgs() << "orig phi value\n"); SVI->second.DefByOrigPHI = true; SVI->second.AllDefsAreReloads = false; propagateSiblingValue(SVI); continue;

Hi Quentin, I have rerun the test case on a recent commit, so the numbers have changed. There are also now a few more basic blocks very small basic blocks in the function, and therefore there are some slight differences. I tried to go back to earlier commits, without success for some reason... This is however very similar, except that there becomes two COPYs back to sibling value after the loop.

I will be removing RegAllocLinearScan and VirtRegRewriter from trunk shortly after we cut the 3.0 release branch. LLVM 3.0 will still ship with the linear scan register allocator, but the default will be the new greedy allocator. Linear scan can be enabled by passing '-regalloc=linearscan -join-physregs' to llc. RegAllocLinearScan and VirtRegRewriter need to go away soon because they

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

I also considered this approach, but did not want to dive in the constraint handling for now. The PBQP path seemed easier at first sight --- and was easy to setup. And I always wanted to give a try to the pbqp :) I will add the hook to the pbqp and propose a patch if this looks clean enough. Thanks, -- Arnaud de Grandmaison -----Original Message----- From: Jakob Stoklund Olesen

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, I have reduced the testcase as much 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

- Re-sending to include llvm-dev. HI Jonas, This is great - thank you very much for your analysis! You're spot on about Bug 1 - the row/column checks are transposed there. I have fixed this in r227628. Regarding Bug 2, as discussed on the other thread I'm going to teach the register allocator to prune single-option vregs so that they never make it into the graph. I haven't had a

Hi Lang, Thanks a lot for taking time to look into this. I will test the fix soon and let you know the results. Cheers, -- Arnaud de Grandmaison On Tuesday, April 03, 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

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.