Avoid re-rendering stencil clip for every draw with reducable clip stack

Avoid re-rendering stencil clip for every draw with reducable clip stack

Fixes the cases where clip stack reduction would cause clip to be
re-rendered to stencil for each draw call. This causes unneeded
slowdown.

Stencil cache would not be used because the clip stack generation id communicated
by the clip stack element list would be invalid. This happended due to

 a) clip stack reduction creating new elements in the element list.

 b) purging logic removing the generation id, but reduction logic
    selecting already purged element, and thus the generation id, as
    the representative state of the clip.

Cases of a) where reduction would flatten the stack to a single new
element were fixed by assigning the generation id of the top-most
element of the clip stack as the generation id of the new
element. This is not strictly minimal, but enables more caching than
using invalid id.

Cases of a) where reduction would substitute a stack element with a
new element the generation id of the substituted element is used.

The b) part was fixed by removing the purging logic. It was not
exactly correct, as the previously purged states were actually
used. The purging was not used for anything.

Changes SkClipStack API to highlight that invalid generation id is
never returned by SkClipStack. Empty stacks are wide open. Changes the
clients to reflect this.

Fixes a crash when not passing anti-alias out parameter to
GrReducedClip::ReduceClipStack. The crash is not exercised in the
current code.

Committed: http://code.google.com/p/skia/source/detail?r=12084

Committed: http://code.google.com/p/skia/source/detail?r=12127

[Kimmo Kinnunen, 2013-10-28 15:59:56]

This may be the smallest change?

Other option (my preference, maybe) would be to define that the clipstacks and
caches start as wide open. The idea would be to never have "invalid id" states,
and thus not have possibility to bugs like this. That'd be a bit bigger change.

[bsalomon, 2013-10-28 20:11:05]

Adding Rob as he may have more familiarity with SkClipStack than I do.

I believe that a clip stack with no elements is already supposed to be
interpreted as "wide open". Perhaps SkCanvas is always pushing a clip rect the
size of the device?

You've fixed the case where ReduceClipStack creates a new element. But now it
seems like we may miss the cache when the clip stack has grown in a way that is
immaterial (e.g. union with a rect that is already wholly inside the clip).

Mayb ReduceClipStack should return the gen ID of the last non-reducible Element
in the stack?

[Kimmo Kinnunen, 2013-10-29 12:54:30]

On 2013/10/28 20:11:05, bsalomon wrote:
> Adding Rob as he may have more familiarity with SkClipStack than I do.
> 
> I believe that a clip stack with no elements is already supposed to be
> interpreted as "wide open". Perhaps SkCanvas is always pushing a clip rect the
> size of the device?

Ah, there's no extra rects in the stack. What I meant was more like this:
Currently SkClipStack sometimes returns kInvalidID, sometimes something else.
Since it makes sense to interpret empty clip stack as wide open, it might make
it simpler to document that empty SkClipStack would be wide open and that
SkClipStack never would communicate invalid ids in its API. Currently the bug
comes from the fact that the "invalid id" tag exists.. (just a small thing,
nothing of importance)


> You've fixed the case where ReduceClipStack creates a new element. But now it
> seems like we may miss the cache when the clip stack has grown in a way that
is
> immaterial (e.g. union with a rect that is already wholly inside the clip).

I'm not 100% sure, but I think that never worked consistently with the current
code either. See below.

The fix I proposed fixed the obvious incorrect case, and made the stencil
construction to be consistent with the two other clip construction cases.
 
> Mayb ReduceClipStack should return the gen ID of the last non-reducible
Element
> in the stack?

I wonder if it is possible with the current algorithm? There are several cases
of early returns that basically inspect top of the stack. In these cases we can
only return the gen id for the top of the stack. 

Also, the reduction algorithm starts from the top and stops immediately when it
sees an element that fully defines the clip. Using the current algorithm, you
have access only to that gen id. Unless the algorithm would iterate to the very
bottom, it can not guarantee to return the absolute minimal genid.

Also it doesn't matter whether the addition is globally "immaterial" or not.
Reduce will reduce stacks based on the query bounds too. Thus the requirement to
return minimal genid for "union with a rect that is already wholly inside the
clip", but allowing return non-minimal genid for case "union with a rect that is
not already wholly inside the clip" is a bit arbitrary. Both might still reduce
to the same element list.

So if I'm understanding correctly, what you're saying is that if we change the
way gen ids are communicated, the spec is:
Given a clip stack and clip bounds, guarantee the identification of the first
gen id of the clip element that establishes the same clip  as the full clip
stack would establish?

I'll try to fix this without changing the way gen ids are communicated, maybe
that's simpler..

[bsalomon, 2013-10-29 14:33:29]

On 2013/10/29 12:54:30, kkinnunen wrote:
> On 2013/10/28 20:11:05, bsalomon wrote:
> > Adding Rob as he may have more familiarity with SkClipStack than I do.
> > 
> > I believe that a clip stack with no elements is already supposed to be
> > interpreted as "wide open". Perhaps SkCanvas is always pushing a clip rect
the
> > size of the device?
> 
> Ah, there's no extra rects in the stack. What I meant was more like this:
> Currently SkClipStack sometimes returns kInvalidID, sometimes something else.
> Since it makes sense to interpret empty clip stack as wide open, it might make
> it simpler to document that empty SkClipStack would be wide open and that
> SkClipStack never would communicate invalid ids in its API. Currently the bug
> comes from the fact that the "invalid id" tag exists.. (just a small thing,
> nothing of importance)

Gotcha. I think that is just a bug. If the stack is empty it should return
kWideOpen not kInvalid. Are there other cases where it returns kInvalid? The
only other reference I see to it is in SkClipStack::purgeClip(). I think that
should be OK if the comment there saying "The clip state represented by
'element' will never be used again" is actually correct.

> 
> 
> > You've fixed the case where ReduceClipStack creates a new element. But now
it
> > seems like we may miss the cache when the clip stack has grown in a way that
> is
> > immaterial (e.g. union with a rect that is already wholly inside the clip).
> 
> I'm not 100% sure, but I think that never worked consistently with the current
> code either. See below.

Agreed that it was busted. 

> 
> The fix I proposed fixed the obvious incorrect case, and made the stencil
> construction to be consistent with the two other clip construction cases.
>  
> > Mayb ReduceClipStack should return the gen ID of the last non-reducible
> Element
> > in the stack?
> 
> I wonder if it is possible with the current algorithm? There are several cases
> of early returns that basically inspect top of the stack. In these cases we
can
> only return the gen id for the top of the stack. 
> 
> Also, the reduction algorithm starts from the top and stops immediately when
it
> sees an element that fully defines the clip. Using the current algorithm, you
> have access only to that gen id. Unless the algorithm would iterate to the
very
> bottom, it can not guarantee to return the absolute minimal genid.

Agreed. I imagine that ReduceClipStack would init a genId to the top of the
stack and then during it's backwards walk it updates it every time it sees an
ignorable element. It might not be perfect. It doesn't do a perfect reduction of
the clip stack either.

> 
> Also it doesn't matter whether the addition is globally "immaterial" or not.
> Reduce will reduce stacks based on the query bounds too. Thus the requirement
to
> return minimal genid for "union with a rect that is already wholly inside the
> clip", but allowing return non-minimal genid for case "union with a rect that
is
> not already wholly inside the clip" is a bit arbitrary. Both might still
reduce
> to the same element list.
> 
> So if I'm understanding correctly, what you're saying is that if we change the
> way gen ids are communicated, the spec is:
> Given a clip stack and clip bounds, guarantee the identification of the first
> gen id of the clip element that establishes the same clip  as the full clip
> stack would establish?
> 
> I'll try to fix this without changing the way gen ids are communicated, maybe
> that's simpler..

I think for the case of stencil-clipping the bounds passed to ReduceClipStack
are always the same for any given stencil buffer right? So if we know the SB x
contains clipstack genID Y from a previous draw then that is sufficient to know
that the SB is good, right?

Alpha masks could be used across different render targets and when we cache
those, the bounds will matter, but I don't think it's an issue currently.

[Kimmo Kinnunen, 2013-10-30 08:13:33]

On 2013/10/29 14:33:29, bsalomon wrote:
> On 2013/10/29 12:54:30, kkinnunen wrote:
> > Currently SkClipStack sometimes returns kInvalidID, sometimes something
else.
> > Since it makes sense to interpret empty clip stack as wide open, it might
make
> > it simpler to document that empty SkClipStack would be wide open and that
> > SkClipStack never would communicate invalid ids in its API. Currently the
bug
> > comes from the fact that the "invalid id" tag exists.. (just a small thing,
> > nothing of importance)
> 
> Gotcha. I think that is just a bug. If the stack is empty it should return
> kWideOpen not kInvalid. Are there other cases where it returns kInvalid?

Done. (Other cases: at the clients/callsites.)

> The
> only other reference I see to it is in SkClipStack::purgeClip(). I think that
> should be OK if the comment there saying "The clip state represented by
> 'element' will never be used again" is actually correct.

It is not strictly correct..

> > Also, the reduction algorithm starts from the top and stops immediately when
> it
> > sees an element that fully defines the clip. Using the current algorithm,
you
> > have access only to that gen id. Unless the algorithm would iterate to the
> very
> > bottom, it can not guarantee to return the absolute minimal genid.
> 
> Agreed. I imagine that ReduceClipStack would init a genId to the top of the
> stack and then during it's backwards walk it updates it every time it sees an
> ignorable element. It might not be perfect. It doesn't do a perfect reduction
of
> the clip stack either.

Yes, but that solution does not fix the immaterial case either, only in one
case.

Well, doesn't matter, except that using the above requires me to remove the
purge logic. This in turn makes it harder for you to accept the patch, which is
why I thought the other version was better (given neither fix the immaterial
case).

> I think for the case of stencil-clipping the bounds passed to ReduceClipStack
> are always the same for any given stencil buffer right?  So if we know the SB
x
> contains clipstack genID Y from a previous draw then that is sufficient to
know
> that the SB is good, right?

But the assumption that bounds are always the same for given stencil buffer does
not affect ReduceClipStack implementation, i.e. the way which generation id is
selected? The problem never was knowing whether SB is good or not -- the cache
key anyway includes the reduction bounds, so goodness known.  Anyhow, does not
matter.

How about the new version? It tries to preserve the way gen id is passed.

[bsalomon, 2013-10-30 14:24:09]

On 2013/10/30 08:13:33, kkinnunen wrote:
> On 2013/10/29 14:33:29, bsalomon wrote:
> > On 2013/10/29 12:54:30, kkinnunen wrote:
> > > Currently SkClipStack sometimes returns kInvalidID, sometimes something
> else.
> > > Since it makes sense to interpret empty clip stack as wide open, it might
> make
> > > it simpler to document that empty SkClipStack would be wide open and that
> > > SkClipStack never would communicate invalid ids in its API. Currently the
> bug
> > > comes from the fact that the "invalid id" tag exists.. (just a small
thing,
> > > nothing of importance)
> > 
> > Gotcha. I think that is just a bug. If the stack is empty it should return
> > kWideOpen not kInvalid. Are there other cases where it returns kInvalid?
> 
> Done. (Other cases: at the clients/callsites.)
> 
> > The
> > only other reference I see to it is in SkClipStack::purgeClip(). I think
that
> > should be OK if the comment there saying "The clip state represented by
> > 'element' will never be used again" is actually correct.
> 
> It is not strictly correct..

I see. I'm ok with removing this. I think we would base clip cache invalidation
off of the work Mike Klein is doing for SkBitmap pixel changes.

> 
> > > Also, the reduction algorithm starts from the top and stops immediately
when
> > it
> > > sees an element that fully defines the clip. Using the current algorithm,
> you
> > > have access only to that gen id. Unless the algorithm would iterate to the
> > very
> > > bottom, it can not guarantee to return the absolute minimal genid.
> > 
> > Agreed. I imagine that ReduceClipStack would init a genId to the top of the
> > stack and then during it's backwards walk it updates it every time it sees
an
> > ignorable element. It might not be perfect. It doesn't do a perfect
reduction
> of
> > the clip stack either.
> 
> Yes, but that solution does not fix the immaterial case either, only in one
> case.
> 
> Well, doesn't matter, except that using the above requires me to remove the
> purge logic. This in turn makes it harder for you to accept the patch, which
is
> why I thought the other version was better (given neither fix the immaterial
> case).
> 
> > I think for the case of stencil-clipping the bounds passed to
ReduceClipStack
> > are always the same for any given stencil buffer right?  So if we know the
SB
> x
> > contains clipstack genID Y from a previous draw then that is sufficient to
> know
> > that the SB is good, right?
> 
> But the assumption that bounds are always the same for given stencil buffer
does
> not affect ReduceClipStack implementation, i.e. the way which generation id is
> selected? The problem never was knowing whether SB is good or not -- the cache
> key anyway includes the reduction bounds, so goodness known.  Anyhow, does not
> matter.

Sure, the clip elements returned by ReduceClipStack are only valid relative to
the bounds that was passed in. It seems OK for that to be true of the genID as
well.

> 
> How about the new version? It tries to preserve the way gen id is passed.

It seems mostly good to me, inline comments coming.

[bsalomon, 2013-10-30 14:25:58]

https://codereview.chromium.org/48593003/diff/100001/src/core/SkClipStack.cpp
File src/core/SkClipStack.cpp (right):

https://codereview.chromium.org/48593003/diff/100001/src/core/SkClipStack.cpp...
src/core/SkClipStack.cpp:626: return getTopmostGenID() == kWideOpenGenID;
tiny style nit: this->getTopmostGenID()

https://codereview.chromium.org/48593003/diff/100001/src/gpu/GrReducedClip.cpp
File src/gpu/GrReducedClip.cpp (right):

https://codereview.chromium.org/48593003/diff/100001/src/gpu/GrReducedClip.cp...
src/gpu/GrReducedClip.cpp:86: SkNEW_INSERT_AT_LLIST_HEAD(result, Element,
(isectRect, SkRegion::kReplace_Op, doAA,
Rather than assigning a genID to the manufactured element maybe this function
could just take an int32_t* genID param that gets updated?

Then we wouldn't need a public Element constructor that takes a genID. That
seems a like an avenue for someone to introduce future bugs.

https://codereview.chromium.org/48593003/diff/100001/src/gpu/SkGpuDevice.cpp
File src/gpu/SkGpuDevice.cpp (left):

https://codereview.chromium.org/48593003/diff/100001/src/gpu/SkGpuDevice.cpp#...
src/gpu/SkGpuDevice.cpp:372: // TODO: iterate through the clip stack and clean
up any cached clip masks
This comment should go too I think

[Kimmo Kinnunen, 2013-11-01 12:12:19]

https://codereview.chromium.org/48593003/diff/100001/src/core/SkClipStack.cpp
File src/core/SkClipStack.cpp (right):

https://codereview.chromium.org/48593003/diff/100001/src/core/SkClipStack.cpp...
src/core/SkClipStack.cpp:626: return getTopmostGenID() == kWideOpenGenID;
On 2013/10/30 14:25:59, bsalomon wrote:
> tiny style nit: this->getTopmostGenID()

Done. (I must be able to learn this rule some day..)

https://codereview.chromium.org/48593003/diff/100001/src/gpu/GrReducedClip.cpp
File src/gpu/GrReducedClip.cpp (right):

https://codereview.chromium.org/48593003/diff/100001/src/gpu/GrReducedClip.cp...
src/gpu/GrReducedClip.cpp:86: SkNEW_INSERT_AT_LLIST_HEAD(result, Element,
(isectRect, SkRegion::kReplace_Op, doAA,
On 2013/10/30 14:25:59, bsalomon wrote:
> Rather than assigning a genID to the manufactured element maybe this function
> could just take an int32_t* genID param that gets updated?
> 
> Then we wouldn't need a public Element constructor that takes a genID. That
> seems a like an avenue for someone to introduce future bugs.

Done.

https://codereview.chromium.org/48593003/diff/100001/src/gpu/SkGpuDevice.cpp
File src/gpu/SkGpuDevice.cpp (left):

https://codereview.chromium.org/48593003/diff/100001/src/gpu/SkGpuDevice.cpp#...
src/gpu/SkGpuDevice.cpp:372: // TODO: iterate through the clip stack and clean
up any cached clip masks
On 2013/10/30 14:25:59, bsalomon wrote:
> This comment should go too I think

Done.

[bsalomon, 2013-11-01 13:09:24]

lgtm (nice test)

[commit-bot: I haz the power, 2013-11-01 13:20:14]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/kkinnunen@nvidia.com/48593003/180001

[commit-bot: I haz the power, 2013-11-01 15:24:39]

Change committed as 12084

[bsalomon, 2013-11-01 16:36:39]

On 2013/11/01 15:24:39, I haz the power (commit-bot) wrote:
> Change committed as 12084

This change caused some warnings-as-errors to fire on the 10.6 and windows
machines. One attempted fix in r12086 didn't stick either, so we reverted to get
the tree green again.

[Kimmo Kinnunen, 2013-11-04 12:05:15]

On 2013/11/01 16:36:39, bsalomon wrote:
> On 2013/11/01 15:24:39, I haz the power (commit-bot) wrote:
> > Change committed as 12084
> 
> This change caused some warnings-as-errors to fire on the 10.6 and windows
> machines. One attempted fix in r12086 didn't stick either, so we reverted to
get
> the tree green again.

I'm not able to restart 10.6 build, but I believe the new patch fixes the
compile warnings.

[commit-bot: I haz the power, 2013-11-05 06:16:18]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/kkinnunen@nvidia.com/48593003/450001

[commit-bot: I haz the power, 2013-11-05 15:03:15]

Change committed as 12127