Optimized implementation of quickReject()

src/core/SkCanvas.cpp

 /*
  * Copyright 2008 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkBitmapDevice.h"
 #include "SkCanvas.h"
 #include "SkCanvasPriv.h"
 #include "SkClipStack.h"
 #include "SkColorFilter.h"
 #include "SkDraw.h"
 #include "SkDrawable.h"
 #include "SkDrawFilter.h"
 #include "SkDrawLooper.h"
 #include "SkErrorInternals.h"
 #include "SkImage.h"
 #include "SkImage_Base.h"
 #include "SkImageFilter.h"
 #include "SkImageFilterCache.h"
 #include "SkLatticeIter.h"
 #include "SkMatrixUtils.h"
 #include "SkMetaData.h"
+#include "SkNx.h"
 #include "SkPaintPriv.h"
 #include "SkPatchUtils.h"
 #include "SkPicture.h"
 #include "SkRasterClip.h"
 #include "SkReadPixelsRec.h"
 #include "SkRRect.h"
 #include "SkSmallAllocator.h"
 #include "SkSpecialImage.h"
 #include "SkSurface_Base.h"
 #include "SkTextBlob.h"
@@ skipping 222 matching lines @@
 #ifdef SK_DEBUG
         if (!fClip.isEmpty()) {
             SkIRect deviceR;
             deviceR.set(0, 0, width, height);
             SkASSERT(deviceR.contains(fClip.getBounds()));
         }
 #endif
     }
 };
 
+
+static inline void set_qr_clip_bounds(SkRect* dst, const SkIRect& src) {

[mtklein, 2016/08/11 01:24:41]

Give that this is all inline, it'll probably make the same assembly and clearer
C++ to just return dst?

    fDeviceClipBounds = qr_clip_bounds(bounds);

Or going in a different direction,

  this->setDeviceClipBounds(bounds);

[msarett, 2016/08/11 16:04:01]

Agreed.  Went with this->setCachedClipDeviceBounds(bounds).  Thought it made
sense since we already have a this->getClipDeviceBounds().

[msarett, 2016/08/11 20:15:16]

Changed my mind.  Going with qr_clip_bounds().  It's more clearly inlined and
accessible to test/debug code in quickReject().

+    // Expand bounds out by 1 in case we are anti-aliasing.  We store the
+    // bounds as floats to enable a faster quick reject implementation.
+    SkNx_cast<float>(Sk4i::Load(&src.fLeft) + Sk4i(-1, -1, 1, 1)).store(&dst->fLeft);
+}
+
 /*  This is the record we keep for each save/restore level in the stack.
     Since a level optionally copies the matrix and/or stack, we have pointers
     for these fields. If the value is copied for this level, the copy is
     stored in the ...Storage field, and the pointer points to that. If the
     value is not copied for this level, we ignore ...Storage, and just point
     at the corresponding value in the previous level in the stack.
 */
 class SkCanvas::MCRec {
 public:
     SkDrawFilter*   fFilter;    // the current filter (or null)
@@ skipping 16 matching lines @@
         fFilter     = nullptr;
         fLayer      = nullptr;
         fTopLayer   = nullptr;
         fMatrix.reset();
         fDeferredSaveCount = 0;
         fCurDrawDepth      = 0;
 
         // don't bother initializing fNext
         inc_rec();
     }
-    MCRec(const MCRec& prev) : fRasterClip(prev.fRasterClip), fMatrix(prev.fMatrix),
-                               fCurDrawDepth(prev.fCurDrawDepth) {
+    MCRec(const MCRec& prev) : fRasterClip(prev.fRasterClip) , fMatrix(prev.fMatrix)
+                             , fCurDrawDepth(prev.fCurDrawDepth)
+    {
         fFilter = SkSafeRef(prev.fFilter);
         fLayer = nullptr;
         fTopLayer = prev.fTopLayer;
         fDeferredSaveCount = 0;
 
         // don't bother initializing fNext
         inc_rec();
     }
     ~MCRec() {
         SkSafeUnref(fFilter);
@@ skipping 310 matching lines @@
     AutoDrawLooper  looper(this, fProps, paint, false, bounds);     \
     while (looper.next(type)) {                                     \
         SkDrawIter          iter(this);
 
 #define LOOPER_END    }
 
 ////////////////////////////////////////////////////////////////////////////
 
 void SkCanvas::resetForNextPicture(const SkIRect& bounds) {
     this->restoreToCount(1);
-    fCachedLocalClipBounds.setEmpty();
-    fCachedLocalClipBoundsDirty = true;
     fClipStack->reset();
     fMCRec->reset(bounds);
 
     // We're peering through a lot of structs here.  Only at this scope do we
     // know that the device is an SkBitmapDevice (really an SkNoPixelsBitmapDevice).
     static_cast<SkBitmapDevice*>(fMCRec->fLayer->fDevice)->setNewSize(bounds.size());
+    set_qr_clip_bounds(&fDeviceClipBounds, bounds);
+    fIsScaleTranslate = true;
 }
 
 SkBaseDevice* SkCanvas::init(SkBaseDevice* device, InitFlags flags) {
     if (device && device->forceConservativeRasterClip()) {
         flags = InitFlags(flags | kConservativeRasterClip_InitFlag);
     }
     // Since init() is only called once by our constructors, it is safe to perform this
     // const-cast.
     *const_cast<bool*>(&fConservativeRasterClip) = SkToBool(flags & kConservativeRasterClip_InitFlag);
 
-    fCachedLocalClipBounds.setEmpty();
-    fCachedLocalClipBoundsDirty = true;
     fAllowSoftClip = true;
     fAllowSimplifyClip = false;
     fDeviceCMDirty = true;
     fSaveCount = 1;
     fMetaData = nullptr;
 #ifdef SK_EXPERIMENTAL_SHADOWING
     fLights = nullptr;
 #endif
 
     fClipStack.reset(new SkClipStack);
 
     fMCRec = (MCRec*)fMCStack.push_back();
     new (fMCRec) MCRec(fConservativeRasterClip);
 
     SkASSERT(sizeof(DeviceCM) <= sizeof(fDeviceCMStorage));
     fMCRec->fLayer = (DeviceCM*)fDeviceCMStorage;
     new (fDeviceCMStorage) DeviceCM(nullptr, nullptr, nullptr, fConservativeRasterClip,
                                     fMCRec->fMatrix);
 
     fMCRec->fTopLayer = fMCRec->fLayer;
 
     fSurfaceBase = nullptr;
 
     if (device) {
         // The root device and the canvas should always have the same pixel geometry
         SkASSERT(fProps.pixelGeometry() == device->surfaceProps().pixelGeometry());
         fMCRec->fLayer->fDevice = SkRef(device);
         fMCRec->fRasterClip.setRect(device->getGlobalBounds());
+        set_qr_clip_bounds(&fDeviceClipBounds, device->getGlobalBounds());
+        fIsScaleTranslate = true;

[mtklein, 2016/08/11 01:24:41]

Might want to name fConservativeIsScaleTranslate, or something like that to
indicate that it's not catastrophic if we set it to false when it could be true?
 Does a scenario with tension between setting it properly and skipping math to
be fast ever come up?

[msarett, 2016/08/11 16:04:00]

Done.
Potentially on concat().  I'm not really sure whether it's better to always be
correct or to take a shortcut.

     }
+
     return device;
 }
 
 SkCanvas::SkCanvas()
     : fMCStack(sizeof(MCRec), fMCRecStorage, sizeof(fMCRecStorage))
     , fProps(SkSurfaceProps::kLegacyFontHost_InitType)
     , fConservativeRasterClip(false)
 {
     inc_canvas();
 
@@ skipping 394 matching lines @@
     }
     SkIRect ir;
     if (bounds) {
         SkRect r;
 
         ctm.mapRect(&r, *bounds);
         r.roundOut(&ir);
         // early exit if the layer's bounds are clipped out
         if (!ir.intersect(clipBounds)) {
             if (BoundsAffectsClip(saveLayerFlags)) {
-                fCachedLocalClipBoundsDirty = true;
                 fMCRec->fRasterClip.setEmpty();
+                fDeviceClipBounds.setEmpty();
             }
             return false;
         }
     } else {    // no user bounds, so just use the clip
         ir = clipBounds;
     }
     SkASSERT(!ir.isEmpty());
 
     if (BoundsAffectsClip(saveLayerFlags)) {
         // Simplify the current clips since they will be applied properly during restore()
-        fCachedLocalClipBoundsDirty = true;
         fClipStack->clipDevRect(ir, SkRegion::kReplace_Op);
         fMCRec->fRasterClip.setRect(ir);
+        set_qr_clip_bounds(&fDeviceClipBounds, ir);
     }
 
     if (intersection) {
         *intersection = ir;
     }
     return true;
 }
 
 
 int SkCanvas::saveLayer(const SkRect* bounds, const SkPaint* paint) {
@@ skipping 171 matching lines @@
         SkPaint tmpPaint;
         tmpPaint.setAlpha(alpha);
         return this->saveLayer(bounds, &tmpPaint);
     }
 }
 
 void SkCanvas::internalRestore() {
     SkASSERT(fMCStack.count() != 0);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
 
     fClipStack->restore();
 
     // reserve our layer (if any)
     DeviceCM* layer = fMCRec->fLayer;   // may be null
     // now detach it from fMCRec so we can pop(). Gets freed after its drawn
     fMCRec->fLayer = nullptr;
 
     // now do the normal restore()
     fMCRec->~MCRec();       // balanced in save()
@@ skipping 13 matching lines @@
             // reset this, since internalDrawDevice will have set it to true
             fDeviceCMDirty = true;
             delete layer;
         } else {
             // we're at the root
             SkASSERT(layer == (void*)fDeviceCMStorage);
             layer->~DeviceCM();
             // no need to update fMCRec, 'cause we're killing the canvas
         }
     }
+
+    if (fMCRec) {
+        fIsScaleTranslate = fMCRec->fMatrix.isScaleTranslate();
+        set_qr_clip_bounds(&fDeviceClipBounds, fMCRec->fRasterClip.getBounds());
+    }
 }
 
 sk_sp<SkSurface> SkCanvas::makeSurface(const SkImageInfo& info, const SkSurfaceProps* props) {
     if (nullptr == props) {
         props = &fProps;
     }
     return this->onNewSurface(info, *props);
 }
 
 sk_sp<SkSurface> SkCanvas::onNewSurface(const SkImageInfo& info, const SkSurfaceProps& props) {
@@ skipping 134 matching lines @@
     this->concat(m);
 }
 
 void SkCanvas::concat(const SkMatrix& matrix) {
     if (matrix.isIdentity()) {
         return;
     }
 
     this->checkForDeferredSave();
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
     fMCRec->fMatrix.preConcat(matrix);
-
+    fIsScaleTranslate = fMCRec->fMatrix.isScaleTranslate();

[mtklein, 2016/08/11 01:24:41]

I think we can conservatively approximate this as

   fIsScaleTranslate = fIsScaleTranslate && matrix.isScaleTranslate();

This might be quicker, as it's data-independent of the preConcat() math.

There are of course ways that we can have non-scale-transalate x
non-scale-translate == non-scale-translate (i.e. rotate 45°, then -45°), but it
just seems unusual to get into that scenario.

[mtklein, 2016/08/11 01:25:43]

err, meant to write not-st x not-st == st.

[msarett, 2016/08/11 16:04:01]

Got it, I think this is a good guess.

     this->didConcat(matrix);
 }
 
 void SkCanvas::internalSetMatrix(const SkMatrix& matrix) {
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
     fMCRec->fMatrix = matrix;
 }
 
 void SkCanvas::setMatrix(const SkMatrix& matrix) {
     this->checkForDeferredSave();
     this->internalSetMatrix(matrix);
+    fIsScaleTranslate = matrix.isScaleTranslate();
     this->didSetMatrix(matrix);
 }
 
 void SkCanvas::resetMatrix() {
     this->setMatrix(SkMatrix::I());
 }
 
 #ifdef SK_EXPERIMENTAL_SHADOWING
 void SkCanvas::translateZ(SkScalar z) {
     this->checkForDeferredSave();
@@ skipping 80 matching lines @@
                      rect.left(), rect.top(), rect.right(), rect.bottom());
 #endif
             return;
         }
     }
 #endif
 
     AutoValidateClip avc(this);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
 
     if (isScaleTrans) {
         const bool isAA = kSoft_ClipEdgeStyle == edgeStyle;
         fClipStack->clipDevRect(devR, op, isAA);
         fMCRec->fRasterClip.op(devR, this->getTopLayerBounds(), op, isAA);
     } else {
         // since we're rotated or some such thing, we convert the rect to a path
         // and clip against that, since it can handle any matrix. However, to
         // avoid recursion in the case where we are subclassed (e.g. Pictures)
         // we explicitly call "our" version of clipPath.
         SkPath  path;
 
         path.addRect(rect);
         this->SkCanvas::onClipPath(path, op, edgeStyle);
     }
+
+    set_qr_clip_bounds(&fDeviceClipBounds, fMCRec->fRasterClip.getBounds());
 }
 
 void SkCanvas::clipRRect(const SkRRect& rrect, SkRegion::Op op, bool doAA) {
     this->checkForDeferredSave();
     ClipEdgeStyle edgeStyle = doAA ? kSoft_ClipEdgeStyle : kHard_ClipEdgeStyle;
     if (rrect.isRect()) {
         this->onClipRect(rrect.getBounds(), op, edgeStyle);
     } else {
         this->onClipRRect(rrect, op, edgeStyle);
     }
 }
 
 void SkCanvas::onClipRRect(const SkRRect& rrect, SkRegion::Op op, ClipEdgeStyle edgeStyle) {
     SkRRect transformedRRect;
     if (rrect.transform(fMCRec->fMatrix, &transformedRRect)) {
         AutoValidateClip avc(this);
 
         fDeviceCMDirty = true;
-        fCachedLocalClipBoundsDirty = true;
         if (!fAllowSoftClip) {
             edgeStyle = kHard_ClipEdgeStyle;
         }
 
         fClipStack->clipDevRRect(transformedRRect, op, kSoft_ClipEdgeStyle == edgeStyle);
 
         fMCRec->fRasterClip.op(transformedRRect, this->getTopLayerBounds(), op,
                                kSoft_ClipEdgeStyle == edgeStyle);
+        set_qr_clip_bounds(&fDeviceClipBounds, fMCRec->fRasterClip.getBounds());
         return;
     }
 
     SkPath path;
     path.addRRect(rrect);
     // call the non-virtual version
     this->SkCanvas::onClipPath(path, op, edgeStyle);
 }
 
 void SkCanvas::clipPath(const SkPath& path, SkRegion::Op op, bool doAA) {
@@ skipping 35 matching lines @@
             fClipStack->clipEmpty();
             (void)fMCRec->fRasterClip.setEmpty();
             return;
         }
     }
 #endif
 
     AutoValidateClip avc(this);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
     if (!fAllowSoftClip) {
         edgeStyle = kHard_ClipEdgeStyle;
     }
 
     SkPath devPath;
     path.transform(fMCRec->fMatrix, &devPath);
 
     // Check if the transfomation, or the original path itself
     // made us empty. Note this can also happen if we contained NaN
     // values. computing the bounds detects this, and will set our
@@ skipping 10 matching lines @@
     if (fAllowSimplifyClip) {
         bool clipIsAA = getClipStack()->asPath(&devPath);
         if (clipIsAA) {
             edgeStyle = kSoft_ClipEdgeStyle;
         }
 
         op = SkRegion::kReplace_Op;
     }
 
     fMCRec->fRasterClip.op(devPath, this->getTopLayerBounds(), op, edgeStyle);
+    set_qr_clip_bounds(&fDeviceClipBounds, fMCRec->fRasterClip.getBounds());
 }
 
 void SkCanvas::clipRegion(const SkRegion& rgn, SkRegion::Op op) {
     this->checkForDeferredSave();
     this->onClipRegion(rgn, op);
 }
 
 void SkCanvas::onClipRegion(const SkRegion& rgn, SkRegion::Op op) {
     AutoValidateClip avc(this);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
 
     // todo: signal fClipStack that we have a region, and therefore (I guess)
     // we have to ignore it, and use the region directly?
     fClipStack->clipDevRect(rgn.getBounds(), op);
 
     fMCRec->fRasterClip.op(rgn, op);
+    set_qr_clip_bounds(&fDeviceClipBounds, fMCRec->fRasterClip.getBounds());
 }
 
 #ifdef SK_DEBUG
 void SkCanvas::validateClip() const {
     // construct clipRgn from the clipstack
     const SkBaseDevice* device = this->getDevice();
     if (!device) {
         SkASSERT(this->isClipEmpty());
         return;
     }
@@ skipping 36 matching lines @@
 ///////////////////////////////////////////////////////////////////////////////
 
 bool SkCanvas::isClipEmpty() const {
     return fMCRec->fRasterClip.isEmpty();
 }
 
 bool SkCanvas::isClipRect() const {
     return fMCRec->fRasterClip.isRect();
 }
 
-bool SkCanvas::quickReject(const SkRect& rect) const {
-    if (!rect.isFinite())
-        return true;
+static inline bool is_nan_or_clipped(const Sk4f& devRect, const Sk4f& devClip) {
+#if SK_CPU_SSE_LEVEL >= SK_CPU_SSE_LEVEL_SSE2
+    __m128 lltt = _mm_unpacklo_ps(devRect.fVec, devClip.fVec);

[mtklein, 2016/08/11 01:24:41]

Might help to make one rect ltrb and the other LTRB, so you can see the
opposition and symmetry more clearly?

[msarett, 2016/08/11 16:04:01]

Agreed, done.

+    __m128 rrbb = _mm_unpackhi_ps(devClip.fVec, devRect.fVec);
+    __m128 mask = _mm_cmplt_ps(lltt, rrbb);
+    return 0xF != _mm_movemask_ps(mask);
+#elif defined(SK_ARM_HAS_NEON)
+    float32x4_t lltt = vzipq_f32(devRect.fVec, devClip.fVec).val[0];
+    float32x4_t rrbb = vzipq_f32(devClip.fVec, devRect.fVec).val[1];
+    uint32x4_t mask = vcltq_f32(lltt, rrbb);
+    return 0xFFFFFFFFFFFFFFFF != (uint64_t) vmovn_u32(mask);
+#else
+    SkASSERT(false);

[mtklein, 2016/08/11 01:24:41]

ಠ_ಠ

[msarett, 2016/08/11 16:04:00]

Guessing this means I should implement the scalar code... Done.

+    return false;
+#endif
+}
 
-    if (fMCRec->fRasterClip.isEmpty()) {
-        return true;
+// It's important for this function to not be inlined.  Otherwise the compiler will share code
+// between the fast path and the slow path, resulting in two slow paths.
+static __attribute__((noinline)) bool quick_reject_slow_path(const SkRect& src,

[mtklein, 2016/08/11 01:24:41]

Let's add SK_NEVER_INLINE alongside SK_ALWAYS_INLINE?   I think it's
__declspec(noinline) for MSVC.

Another option is to define this outside this translation unit, e.g. in
SkRect.cpp or SkMatrix.cpp.

[msarett, 2016/08/11 16:04:01]

SK_NEVER_INLINE sgtm.

+                                                             const SkRect& deviceClip,
+                                                             const SkMatrix& matrix) {
+    SkRect deviceRect;
+    matrix.mapRect(&deviceRect, src);
+    return !deviceRect.isFinite() || !deviceRect.intersect(deviceClip);
+}
+
+bool SkCanvas::quickReject(const SkRect& src) const {
+    if (!fIsScaleTranslate) {
+        return quick_reject_slow_path(src, fDeviceClipBounds, fMCRec->fMatrix);

[mtklein, 2016/08/11 01:24:41]

We might follow up to see how bad things are if we return false here.

[msarett, 2016/08/11 16:04:00]

SGTM

     }
 
-    if (fMCRec->fMatrix.hasPerspective()) {
-        SkRect dst;
-        fMCRec->fMatrix.mapRect(&dst, rect);
-        return !SkIRect::Intersects(dst.roundOut(), fMCRec->fRasterClip.getBounds());
-    } else {
-        const SkRect& clipR = this->getLocalClipBounds();
+    // We inline the implementation of mapScaleTranslate() for the fast path.
+    float sx = fMCRec->fMatrix.getScaleX();
+    float sy = fMCRec->fMatrix.getScaleY();
+    float tx = fMCRec->fMatrix.getTranslateX();
+    float ty = fMCRec->fMatrix.getTranslateY();
+    Sk4f scale(sx, sy, sx, sy);
+    Sk4f trans(tx, ty, tx, ty);
 
-        // for speed, do the most likely reject compares first
-        // TODO: should we use | instead, or compare all 4 at once?
-        if (rect.fTop >= clipR.fBottom || rect.fBottom <= clipR.fTop) {
-            return true;
-        }
-        if (rect.fLeft >= clipR.fRight || rect.fRight <= clipR.fLeft) {
-            return true;
-        }
+    // Apply matrix.
+    Sk4f ltrb = Sk4f::Load(&src.fLeft) * scale + trans;
+
+    // Make sure left < right, top < bottom.
+    Sk4f rblt(ltrb[2], ltrb[3], ltrb[0], ltrb[1]);
+    Sk4f min = Sk4f::Min(ltrb, rblt);
+    Sk4f max = Sk4f::Max(ltrb, rblt);
+    // We can extract either pair [0,1] or [2,3] from min and max and be correct, but on
+    // ARM this sequence generates the fastest (a single instruction).
+    Sk4f devRect = Sk4f(min[2], min[3], max[0], max[1]);
+
+    // Check if the device rect is NaN or outside the clip.
+    return is_nan_or_clipped(devRect, Sk4f::Load(&fDeviceClipBounds.fLeft));
+}
+
+bool SkCanvas::quickRejectY(SkScalar top, SkScalar bottom) const {

[mtklein, 2016/08/11 01:24:41]

I think we should consider a pre-patch deleting quickRejectY().  I only see old
speed-insensitive picture code calling it:

~/skia (sideways) $ git grep quickRejectY
include/core/SkCanvas.h:    bool quickRejectY(SkScalar top, SkScalar bottom)
const {
src/core/SkPicturePlayback.cpp:            if (!canvas->quickRejectY(top,
bottom) && paint) {
src/core/SkPicturePlayback.cpp:            if (!canvas->quickRejectY(top,
bottom) && paint) {
src/core/SkPicturePlayback.cpp:            if (!canvas->quickRejectY(ptr[2],
ptr[3]) && paint) {

[msarett, 2016/08/11 16:04:00]

SGTM.  I wanted to delete it...  Glad to know the picture code is
speed-insensitive.

+    if (!fIsScaleTranslate) {
+        // This is only called when we draw text.  Will we ever draw rotated or perspective text?
         return false;
     }
+
+    top = top * fMCRec->fMatrix.getScaleY() + fMCRec->fMatrix.getTranslateY();

[mtklein, 2016/08/11 01:24:41]

:,(

"top   " lines up so much more nicely with "bottom"

[msarett, 2016/08/11 16:04:01]

Acknowledged.

+    bottom = bottom * fMCRec->fMatrix.getScaleY() + fMCRec->fMatrix.getTranslateY();
+
+    // In the case where the clip is empty and we are provided with a
+    // negative top and positive bottom parameter then this test will return
+    // false even though it will be clipped. We have chosen to exclude that
+    // check as it is rare and would result double the comparisons.
+    return top >= fDeviceClipBounds.fBottom || bottom <= fDeviceClipBounds.fTop;
 }
 
 bool SkCanvas::quickReject(const SkPath& path) const {
     return path.isEmpty() || this->quickReject(path.getBounds());
 }
 
 bool SkCanvas::getClipBounds(SkRect* bounds) const {
     SkIRect ibounds;
     if (!this->getClipDeviceBounds(&ibounds)) {
         return false;
@@ skipping 1323 matching lines @@
 
 SkAutoCanvasMatrixPaint::~SkAutoCanvasMatrixPaint() {
     fCanvas->restoreToCount(fSaveCount);
 }
 
 #ifdef SK_SUPPORT_LEGACY_NEW_SURFACE_API
 SkSurface* SkCanvas::newSurface(const SkImageInfo& info, const SkSurfaceProps* props) {
     return this->makeSurface(info, props).release();
 }
 #endif