On Mon, Aug 4, 2014 at 10:42 AM, Connor Abbott <cwabbo...@gmail.com> wrote: > On Mon, Aug 4, 2014 at 10:17 AM, Eric Anholt <e...@anholt.net> wrote: >> Connor Abbott <cwabbo...@gmail.com> writes: >> >>> On Mon, Aug 4, 2014 at 9:46 AM, Eric Anholt <e...@anholt.net> wrote: >>>> Connor Abbott <cwabbo...@gmail.com> writes: >>>> >>>>> On Fri, Aug 1, 2014 at 12:25 PM, Eric Anholt <e...@anholt.net> wrote: >>>>>> Connor Abbott <cwabbo...@gmail.com> writes: >>>>>> >>>>>>> On Fri, Aug 1, 2014 at 11:51 AM, Eric Anholt <e...@anholt.net> wrote: >>>>>>>> Connor Abbott <cwabbo...@gmail.com> writes: >>>>>>>> >>>>>>>>> On Thu, Jul 31, 2014 at 1:05 PM, Eric Anholt <e...@anholt.net> wrote: >>>>>>>>>> Connor Abbott <cwabbo...@gmail.com> writes: >>>>>>>>>>> That's not necessarily true - you could want to spill a trivially >>>>>>>>>>> colored register that interferes with a non trivially colored >>>>>>>>>>> register, especially if the spill cost of the non trivially colored >>>>>>>>>>> register is higher than that of the trivially colored register >>>>>>>>>>> because >>>>>>>>>>> e.g. the non trivially colored register is used in a loop. >>>>>>>>>>> Especially, >>>>>>>>>>> I ran into trouble with the varying packing tests in piglit which >>>>>>>>>>> after a few rounds of spilling looked something like: >>>>>>>>>> >>>>>>>>>> If it's trivially colorable, then when you're trying to get a >>>>>>>>>> non-conflicting color for a difficult neighbor (an >>>>>>>>>> optimistic-coloring >>>>>>>>>> one near the top of the stack that's triggering the need for >>>>>>>>>> spilling), >>>>>>>>>> it's out consideration because it's deeper in the stack. >>>>>>>>> >>>>>>>>> Right... so in that case, can't we just ignore everything on the stack >>>>>>>>> below the node that couldn't be colored in ra_select()? >>>>>>>> >>>>>>>> Yep, that's what the code's doing currently. >>>>>>> >>>>>>> No, it's also considering other optimistically colored nodes below the >>>>>>> one that failed on the stack... see patch 3 in v3 of my series, which >>>>>>> changes the code to actually do that. >>>>>> >>>>>> Oh, I misread you as saying s/couldn't be colored/first couldn't be >>>>>> trivially colored/. It seems like obviously the behavior we want, to >>>>>> me. >>>>> >>>>> Cool, then can you put your r-b on the last two patches of the v3 >>>>> series so we can push it? >>>> >>>> Not really -- I'm saying that we *do* want to consider the other >>>> optimistically colored nodes. Those ones lower in the stack might >>>> actually be useful to spill, since if spilled they could potentially >>>> make other values trivially colorable, which would change the order of >>>> pushes and might make our node colorable. >>>> >>> >>> Well, you could apply that same argument to *any* spillable node in >>> the graph, which brings us right back to where we started. I think >>> what we have now is a rather arbitrary compromise between "consider >>> everything for spilling because it might make other things trivially >>> colorable" and "only spill the things we know are likely to help." I >>> still think we should go with the former, since it produces numbers >>> equivalent to what we have right now instead of slightly worse >>> numbers. And besides, as I noted in the commit message, considering >>> those nodes doesn't seem to be useful in practice since we get the >>> exact same code anyways - even with reducing the number of registers >>> to make more things spill. >> >> I don't believe that's true. The argument before was about >> trivially-colorable things -- things that always appear in the stack >> before the optimistic things. They can't have an effect on the things >> higher in the stack, becuase they're already in the stack and you know >> you can color them regardless of choices higher in the stack, so you >> don't have to spill them ever. >> >> For your optimistic nodes, though, even though you've put them in the >> stack, you want to consider them for spilling because even once you >> resolve the spills and manage to color things high in the stack (in your >> scheme), you may have to spill that lower-down optimistic node anyway. >> So you failed to consider an important node for spilling, that might >> have also resolved your higher-in-the-stack troubles, and got extra >> spilling as a result. > > How, exactly, could spilling in this case ever resolve the > "higher-in-the-stack troubles"? Say we have an optimistically colored > node A, that is lower on the stack than the optimistically colored > node B that is currently failing to be colored. There are two effects > of spilling A: > > 1) Some of the nodes that we split A into may become trivially > colorable, which will push them down on the stack - but this is all > happening below B on the stack anyways, so it doesn't make any > difference for now. > > 2) Some of the nodes that were interfering with A may no longer > interfere with any of the nodes we split A into - but again, we only > care about B or nodes above B on the stack, so we don't count that > interference anyways, and therefore we still haven't gained anything. > > So although spilling A may help in the future, I still fail to see how > it could help now - we still have to spill nodes above B (or B itself) > before we can make progress.
By the way, I can see how spilling A might help as of now - since we marked A and B as optimistic at the same time, some of the other optimistic nodes above B on the stack might become trivial as we reduced their interference count. But after the next patch, this behavior changes - nodes above A on the stack are pushed on the stack and popped off the stack without considering A at all, so spilling A now won't make any difference. I can update the commit message to explain this if you would like (and if you agree with what I'm saying!). _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
