On Tue, Feb 17, 2015 at 8:15 AM, Francisco Jerez <curroje...@riseup.net> wrote: > Connor Abbott <cwabbo...@gmail.com> writes: > >> Hi Francisco, >> > Hi Connor, and thank you for your feedback. > >> A few comments: >> >> 1) This is just a difference in definitions, but to me an >> optimistically-colored node is a node that we pushed onto the stack >> without knowing whether we could color it or not. There may be (and >> most certainly are) nodes above the optimistically-colored node on the >> stack that we know we can color, so I wouldn't call those >> optimistically colored even though they probably have the >> characteristics you mentioned. > > Yeah, I mostly agree on the definition, but the distinction is somewhat > arbitrary and consequence of the min-q heuristic, which picks a > preferred node among the whole set of remaining non-trivially colorable > nodes, but that's by no means the only possible choice. We may indeed > know we can trivially color some of the nodes left after we push the > first optimistically node onto the stack, but even that's dependent on > the assumption that we can take the optimistically colored node below > them out of the picture, and that's a bit of an overstatement because we > have no guarantee that the coloring we choose for these nodes won't lead > to a contradiction later on. > >> The distinction is useful since the optimistically colored nodes are >> those which we may have to spill. >> > Now you're using "optimistically colored nodes" to refer to the nodes we > potentially consider for spilling (at most the first optimistically > colorable node and everything above it), which is precisely the same set > of nodes I'm disabling round-robin for. ;)
Whoops, I meant "those which we may fail to find a color for." Goes to show what happens when you try to be pedantic... > >> 2) Given the above, what you're doing here is disabling the >> round-robin strategy for the nodes above the lowest >> optimistically-colored node as well as the lowest >> optimistically-colored node itself. But you don't need to disable >> round-robin for the lowest optimistically-colored node itself, since >> once we're able to find a register (any register!) for that one, we >> know we'll be able to find a register for everything else that's left, >> so it doesn't really matter which register we start searching at. >> > Heh, fair enough, I'll send a v2. > >> 3) Usually, there are a series of registers that are pushed onto the >> stack optimistically until we can go back to the normal strategy, and >> it's one of the registers in the middle of the stack we fail to place, >> so we don't need to disable round-robin for *all* the optimistically >> colored nodes, only everything above the node that would've failed to >> allocate. Another way to think of it is that when I changed the >> handling of optimistic coloring a while ago, we gained ~150 SIMD16 >> shaders. So of the >200 SIMD16 shaders that we optimistically color >> but still successfully allocate after your patch, only 50 -- less than >> a quarter -- actually need to have round-robin disabled. This is just >> an idea, but maybe we could handle this similarly to how we handle >> spilling: first, try ra_select() using round-robin all the way, and >> only when it fails do we disable round-robin for everything above the >> thing that we failed to allocate and try ra_select() again. We would >> keep doing this until disabling round-robin wouldn't make a >> difference. > > We already discussed this shortly on IRC, but let me summarize here. > > I did consider doing that to avoid the regressions (and actually went as > far as to implement it), but it seemed rather ugly to add another loop > of trial-and-error to the already ugly schedule-regalloc loop which > tries out three different scheduling heuristics for two different > dispatch widths until one succeeds, and then you have one more iteration > for each spill. > > I admit that the additional back-tracking would be unlikely to affect > the running time of the register allocator significantly, but I suspect > that the pre-regalloc scheduler is also at fault in the regressing cases > and there's likely to be a better solution for them. I don't have any > evidence either that the additional back-tracking will lead to any > measurable improvement in any of the other cases (actually I would be > very surprised if that's the case), so this suggestion seems a bit of a > premature optimization to me, how about we KISS for now. That sounds sensible to me. By the way, did you ever send a patch to fix the silliness you found in the pre-regalloc scheduler? _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
