[LLVMdev] PBQP crash

[Arnaud A. de Grandmaison]

Hi Jonas,

 

I think you may be facing a problem with the reduction order. I found out it
is important and can affect the quality of the allocation, and with your
case, it affects the allocability.

 

With your example, I think the node should be pushed amongst the last nodes
onto the reduction order list: spilling is not an option, so it is more
constrained and should be allocated first. It should simply not have made it
into the ConservativelyAllocatableNodes. It should have stayed into the
NotProvablyAllocatableNodes set, and the SpillCostComparator will ensure it
is on the top of the reduction list (because its spill cost is +inf).

 

The logic using NodeMetadata::isConservativelyAllocatable should be tweaked
to detect such nodes. This would take place in RegAllocSolverImpl, because
the node costs cannot be accessed in NodeMetadata.

 

Lang will probably be able to give a more educated answer than mine.

 

Thanks for using PBQP !

 

Cheers,

Arnaud

 

From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Jonas Paulsson
Sent: 26 January 2015 16:56
To: llvmdev at cs.uiuc.edu; Lang Hames
Subject: [LLVMdev] PBQP crash

 

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 rematerialize the load of the symbol to lie right
before its only user, which makes good sense. The original def is removed.

 

The new LiveInterval pushed is thus much smaller in the next PBQP round. The
spill cost is marked as 'inf' during graph building. This small interval has
also a lot of overlapping intervals and thus edges in the PBQP graph. It
gets pushed on the node stack to later be popped after 17 others.

Those 17 nodes use up all registers of the narrow reg-class, and the cost
vector has become all infinities. Spill option is selected again, and thus
the error is a fact of spilling an already spilled value.

 

I wonder what has gone wrong here, and have some initial thoughts:

 

* 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 out in this
case.

   In setup(), the node is first put into not-provably-allocatables.
However, one of it's neigbhour invoked handleDisconnectEdge(), and moves it
into conservatively-allocatables, because DeniedOpts had become less than
NumOpts (in isConservativelyAllocatable().

* There are lots of spillable nodes being popped before the one that can't
be spilled.  This seems intuitively wrong, as they are intervals that
actually could be spilled.

 

I would really appreciate some help and pointers on what might be going
wrong here,

 

Jonas Paulsson

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150126/2f9c7d93/attachment.html>