diff options
Diffstat (limited to 'record')
| -rw-r--r-- | record/SkRecordOpts.cpp | 265 | ||||
| -rw-r--r-- | record/SkRecordPattern.h | 219 | ||||
| -rw-r--r-- | record/SkRecordTraits.h | 31 |
3 files changed, 340 insertions, 175 deletions
diff --git a/record/SkRecordOpts.cpp b/record/SkRecordOpts.cpp index 5b537de0..aaa611cf 100644 --- a/record/SkRecordOpts.cpp +++ b/record/SkRecordOpts.cpp @@ -7,10 +7,12 @@ #include "SkRecordOpts.h" -#include "SkRecordTraits.h" +#include "SkRecordPattern.h" #include "SkRecords.h" #include "SkTDArray.h" +using namespace SkRecords; + void SkRecordOptimize(SkRecord* record) { // TODO(mtklein): fuse independent optimizations to reduce number of passes? SkRecordNoopSaveRestores(record); @@ -19,205 +21,180 @@ void SkRecordOptimize(SkRecord* record) { SkRecordBoundDrawPosTextH(record); } -namespace { - -// Convenience base class to share some common implementation code. -class Common : SkNoncopyable { -public: - explicit Common(SkRecord* record) : fRecord(record), fIndex(0) {} - - unsigned index() const { return fIndex; } - void next() { ++fIndex; } - -protected: - SkRecord* fRecord; - unsigned fIndex; -}; - -// Turns logical no-op Save-[non-drawing command]*-Restore patterns into actual no-ops. -// TODO(mtklein): state machine diagram -class SaveRestoreNooper : public Common { -public: - explicit SaveRestoreNooper(SkRecord* record) - : Common(record), fSave(kInactive), fChanged(false) {} - - // Drawing commands reset state to inactive without nooping. - template <typename T> - SK_WHEN(SkRecords::IsDraw<T>, void) operator()(T*) { fSave = kInactive; } +// Most of the optimizations in this file are pattern-based. These are all defined as structs with: +// - a Pattern typedef +// - a bool onMatch(SkRceord*, Pattern*, unsigned begin, unsigned end) method, +// which returns true if it made changes and false if not. - // Most non-drawing commands can be ignored. - template <typename T> - SK_WHEN(!SkRecords::IsDraw<T>, void) operator()(T*) {} +// Run a pattern-based optimization once across the SkRecord, returning true if it made any changes. +// It looks for spans which match Pass::Pattern, and when found calls onMatch() with the pattern, +// record, and [begin,end) span of the commands that matched. +template <typename Pass> +static bool apply(Pass* pass, SkRecord* record) { + typename Pass::Pattern pattern; + bool changed = false; + unsigned begin, end = 0; - void operator()(SkRecords::Save* r) { - fSave = SkCanvas::kMatrixClip_SaveFlag == r->flags ? this->index() : kInactive; + while (pattern.search(record, &begin, &end)) { + changed |= pass->onMatch(record, &pattern, begin, end); } + return changed; +} - void operator()(SkRecords::Restore* r) { - if (fSave != kInactive) { - // Remove everything between the save and restore, inclusive on both sides. - fChanged = true; - for (unsigned i = fSave; i <= this->index(); i++) { - fRecord->replace<SkRecords::NoOp>(i); - } - fSave = kInactive; +// Turns logical no-op Save-[non-drawing command]*-Restore patterns into actual no-ops. +struct SaveRestoreNooper { + // Star matches greedily, so we also have to exclude Save and Restore. + typedef Pattern3<Is<Save>, + Star<Not<Or3<Is<Save>, + Is<Restore>, + IsDraw> > >, + Is<Restore> > + Pattern; + + bool onMatch(SkRecord* record, Pattern* pattern, unsigned begin, unsigned end) { + // If restore doesn't revert both matrix and clip, this isn't safe to noop away. + if (pattern->first<Save>()->flags != SkCanvas::kMatrixClip_SaveFlag) { + return false; } - } - - bool changed() const { return fChanged; } - -private: - static const unsigned kInactive = ~0; - unsigned fSave; - bool fChanged; -}; - -// Tries to replace PushCull with PairedPushCull, which lets us skip to the paired PopCull -// when the canvas can quickReject the cull rect. -class CullAnnotator : public Common { -public: - explicit CullAnnotator(SkRecord* record) : Common(record) {} - - // Do nothing to most ops. - template <typename T> void operator()(T*) {} - - void operator()(SkRecords::PushCull* push) { - Pair pair = { this->index(), push }; - fPushStack.push(pair); - } - - void operator()(SkRecords::PopCull* pop) { - Pair push = fPushStack.top(); - fPushStack.pop(); - - SkASSERT(this->index() > push.index); - unsigned skip = this->index() - push.index; - SkRecords::Adopted<SkRecords::PushCull> adopted(push.command); - SkNEW_PLACEMENT_ARGS(fRecord->replace<SkRecords::PairedPushCull>(push.index, adopted), - SkRecords::PairedPushCull, (&adopted, skip)); + // The entire span between Save and Restore (inclusively) does nothing. + for (unsigned i = begin; i < end; i++) { + record->replace<NoOp>(i); + } + return true; } - -private: - struct Pair { - unsigned index; - SkRecords::PushCull* command; - }; - - SkTDArray<Pair> fPushStack; }; +void SkRecordNoopSaveRestores(SkRecord* record) { + SaveRestoreNooper pass; + while (apply(&pass, record)); // Run until it stops changing things. +} // Replaces DrawPosText with DrawPosTextH when all Y coordinates are equal. -class StrengthReducer : public Common { -public: - explicit StrengthReducer(SkRecord* record) : Common(record) {} +struct StrengthReducer { + typedef Pattern1<Is<DrawPosText> > Pattern; - // Do nothing to most ops. - template <typename T> void operator()(T*) {} + bool onMatch(SkRecord* record, Pattern* pattern, unsigned begin, unsigned end) { + SkASSERT(end == begin + 1); + DrawPosText* draw = pattern->first<DrawPosText>(); - void operator()(SkRecords::DrawPosText* r) { - const unsigned points = r->paint.countText(r->text, r->byteLength); + const unsigned points = draw->paint.countText(draw->text, draw->byteLength); if (points == 0) { - // No point (ha!). - return; + return false; // No point (ha!). } - const SkScalar firstY = r->pos[0].fY; + const SkScalar firstY = draw->pos[0].fY; for (unsigned i = 1; i < points; i++) { - if (r->pos[i].fY != firstY) { - // Needs the full strength of DrawPosText. - return; + if (draw->pos[i].fY != firstY) { + return false; // Needs full power of DrawPosText. } } // All ys are the same. We can replace DrawPosText with DrawPosTextH. - // r->pos is points SkPoints, [(x,y),(x,y),(x,y),(x,y), ... ]. + // draw->pos is points SkPoints, [(x,y),(x,y),(x,y),(x,y), ... ]. // We're going to squint and look at that as 2*points SkScalars, [x,y,x,y,x,y,x,y, ...]. // Then we'll rearrange things so all the xs are in order up front, clobbering the ys. SK_COMPILE_ASSERT(sizeof(SkPoint) == 2 * sizeof(SkScalar), SquintingIsNotSafe); - SkScalar* scalars = &r->pos[0].fX; + SkScalar* scalars = &draw->pos[0].fX; for (unsigned i = 0; i < 2*points; i += 2) { scalars[i/2] = scalars[i]; } - // Extend lifetime of r to the end of the method so we can copy its parts. - SkRecords::Adopted<SkRecords::DrawPosText> adopted(r); - SkNEW_PLACEMENT_ARGS(fRecord->replace<SkRecords::DrawPosTextH>(this->index(), adopted), - SkRecords::DrawPosTextH, - (r->text, r->byteLength, scalars, firstY, r->paint)); + // Extend lifetime of draw to the end of the loop so we can copy its paint. + Adopted<DrawPosText> adopted(draw); + SkNEW_PLACEMENT_ARGS(record->replace<DrawPosTextH>(begin, adopted), + DrawPosTextH, + (draw->text, draw->byteLength, scalars, firstY, draw->paint)); + return true; } }; +void SkRecordReduceDrawPosTextStrength(SkRecord* record) { + StrengthReducer pass; + apply(&pass, record); +} // Tries to replace DrawPosTextH with BoundedDrawPosTextH, which knows conservative upper and lower // bounds to use with SkCanvas::quickRejectY. -class TextBounder : public Common { -public: - explicit TextBounder(SkRecord* record) : Common(record) {} +struct TextBounder { + typedef Pattern1<Is<DrawPosTextH> > Pattern; - // Do nothing to most ops. - template <typename T> void operator()(T*) {} + bool onMatch(SkRecord* record, Pattern* pattern, unsigned begin, unsigned end) { + SkASSERT(end == begin + 1); + DrawPosTextH* draw = pattern->first<DrawPosTextH>(); - void operator()(SkRecords::DrawPosTextH* r) { // If we're drawing vertical text, none of the checks we're about to do make any sense. // We'll need to call SkPaint::computeFastBounds() later, so bail if that's not possible. - if (r->paint.isVerticalText() || !r->paint.canComputeFastBounds()) { - return; + if (draw->paint.isVerticalText() || !draw->paint.canComputeFastBounds()) { + return false; } // Rather than checking the top and bottom font metrics, we guess. Actually looking up the // top and bottom metrics is slow, and this overapproximation should be good enough. - const SkScalar buffer = r->paint.getTextSize() * 1.5f; + const SkScalar buffer = draw->paint.getTextSize() * 1.5f; SkDEBUGCODE(SkPaint::FontMetrics metrics;) - SkDEBUGCODE(r->paint.getFontMetrics(&metrics);) + SkDEBUGCODE(draw->paint.getFontMetrics(&metrics);) SkASSERT(-buffer <= metrics.fTop); SkASSERT(+buffer >= metrics.fBottom); // Let the paint adjust the text bounds. We don't care about left and right here, so we use // 0 and 1 respectively just so the bounds rectangle isn't empty. SkRect bounds; - bounds.set(0, r->y - buffer, SK_Scalar1, r->y + buffer); - SkRect adjusted = r->paint.computeFastBounds(bounds, &bounds); - - SkRecords::Adopted<SkRecords::DrawPosTextH> adopted(r); - SkNEW_PLACEMENT_ARGS( - fRecord->replace<SkRecords::BoundedDrawPosTextH>(this->index(), adopted), - SkRecords::BoundedDrawPosTextH, - (&adopted, adjusted.fTop, adjusted.fBottom)); + bounds.set(0, draw->y - buffer, SK_Scalar1, draw->y + buffer); + SkRect adjusted = draw->paint.computeFastBounds(bounds, &bounds); + + Adopted<DrawPosTextH> adopted(draw); + SkNEW_PLACEMENT_ARGS(record->replace<BoundedDrawPosTextH>(begin, adopted), + BoundedDrawPosTextH, + (&adopted, adjusted.fTop, adjusted.fBottom)); + return true; } }; +void SkRecordBoundDrawPosTextH(SkRecord* record) { + TextBounder pass; + apply(&pass, record); +} +// Replaces PushCull with PairedPushCull, which lets us skip to the paired PopCull when the canvas +// can quickReject the cull rect. +// There's no efficient way (yet?) to express this one as a pattern, so we write a custom pass. +class CullAnnotator { +public: + // Do nothing to most ops. + template <typename T> void operator()(T*) {} -template <typename Pass> -static void run_pass(Pass& pass, SkRecord* record) { - for (; pass.index() < record->count(); pass.next()) { - record->mutate(pass.index(), pass); + void operator()(PushCull* push) { + Pair pair = { fIndex, push }; + fPushStack.push(pair); } -} -} // namespace + void operator()(PopCull* pop) { + Pair push = fPushStack.top(); + fPushStack.pop(); + SkASSERT(fIndex > push.index); + unsigned skip = fIndex - push.index; -void SkRecordNoopSaveRestores(SkRecord* record) { - // Run SaveRestoreNooper until it doesn't make any more changes. - bool changed; - do { - SaveRestoreNooper nooper(record); - run_pass(nooper, record); - changed = nooper.changed(); - } while (changed); -} + Adopted<PushCull> adopted(push.command); + SkNEW_PLACEMENT_ARGS(fRecord->replace<PairedPushCull>(push.index, adopted), + PairedPushCull, (&adopted, skip)); + } -void SkRecordAnnotateCullingPairs(SkRecord* record) { - CullAnnotator annotator(record); - run_pass(annotator, record); -} + void apply(SkRecord* record) { + for (fRecord = record, fIndex = 0; fIndex < record->count(); fIndex++) { + fRecord->mutate(fIndex, *this); + } + } -void SkRecordReduceDrawPosTextStrength(SkRecord* record) { - StrengthReducer reducer(record); - run_pass(reducer, record); -} +private: + struct Pair { + unsigned index; + PushCull* command; + }; -void SkRecordBoundDrawPosTextH(SkRecord* record) { - TextBounder bounder(record); - run_pass(bounder, record); + SkTDArray<Pair> fPushStack; + SkRecord* fRecord; + unsigned fIndex; +}; +void SkRecordAnnotateCullingPairs(SkRecord* record) { + CullAnnotator pass; + pass.apply(record); } diff --git a/record/SkRecordPattern.h b/record/SkRecordPattern.h new file mode 100644 index 00000000..2023a905 --- /dev/null +++ b/record/SkRecordPattern.h @@ -0,0 +1,219 @@ +#ifndef SkRecordPattern_DEFINED +#define SkRecordPattern_DEFINED + +#include "SkTLogic.h" + +namespace SkRecords { + +// First, some matchers. These match a single command in the SkRecord, +// and may hang onto some data from it. If so, you can get the data by calling .get(). + +// Matches a command of type T, and stores that command. +template <typename T> +class Is { +public: + Is() : fPtr(NULL) {} + + typedef T type; + type* get() { return fPtr; } + + bool match(T* ptr) { + fPtr = ptr; + return true; + } + + template <typename U> + bool match(U*) { + fPtr = NULL; + return false; + } + +private: + type* fPtr; +}; + +// Matches any command that draws, and stores its paint. +class IsDraw { + SK_CREATE_MEMBER_DETECTOR(paint); +public: + IsDraw() : fPaint(NULL) {} + + typedef SkPaint type; + type* get() { return fPaint; } + + template <typename T> + SK_WHEN(HasMember_paint<T>, bool) match(T* draw) { + fPaint = AsPtr(draw->paint); + return true; + } + + template <typename T> + SK_WHEN(!HasMember_paint<T>, bool) match(T*) { + fPaint = NULL; + return false; + } + +private: + // Abstracts away whether the paint is always part of the command or optional. + template <typename T> static T* AsPtr(SkRecords::Optional<T>& x) { return x; } + template <typename T> static T* AsPtr(T& x) { return &x; } + + type* fPaint; +}; + +// Matches if Matcher doesn't. Stores nothing. +template <typename Matcher> +struct Not { + template <typename T> + bool match(T* ptr) { return !Matcher().match(ptr); } +}; + +// Matches if either of A or B does. Stores nothing. +template <typename A, typename B> +struct Or { + template <typename T> + bool match(T* ptr) { return A().match(ptr) || B().match(ptr); } +}; + +// Matches if any of A, B or C does. Stores nothing. +template <typename A, typename B, typename C> +struct Or3 : Or<A, Or<B, C> > {}; + +// We'll use this to choose which implementation of Star suits each Matcher. +SK_CREATE_TYPE_DETECTOR(type); + +// Star is a special matcher that matches Matcher 0 or more times _greedily_ in the SkRecord. +// This version stores nothing. It's enabled when Matcher stores nothing. +template <typename Matcher, typename = void> +class Star { +public: + void reset() {} + + template <typename T> + bool match(T* ptr) { return Matcher().match(ptr); } +}; + +// This version stores a list of matches. It's enabled if Matcher stores something. +template <typename Matcher> +class Star<Matcher, SK_WHEN(HasType_type<Matcher>, void)> { +public: + typedef SkTDArray<typename Matcher::type*> type; + type* get() { return &fMatches; } + + void reset() { fMatches.rewind(); } + + template <typename T> + bool match(T* ptr) { + Matcher matcher; + if (matcher.match(ptr)) { + fMatches.push(matcher.get()); + return true; + } + return false; + } + +private: + type fMatches; +}; + + +// Cons builds a list of Matchers. +// It first matches Matcher (something from above), then Pattern (another Cons or Nil). +// +// This is the main entry point to pattern matching, and so provides a couple of extra API bits: +// - search scans through the record to look for matches; +// - first, second, and third return the data stored by their respective matchers in the pattern. +// +// These Cons build lists analogously to Lisp's "cons". See Pattern# for the "list" equivalent. +template <typename Matcher, typename Pattern> +class Cons { +public: + // If this pattern matches the SkRecord starting at i, + // return the index just past the end of the pattern, otherwise return 0. + SK_ALWAYS_INLINE unsigned match(SkRecord* record, unsigned i) { + i = this->matchHead(&fHead, record, i); + return i == 0 ? 0 : fTail.match(record, i); + } + + // Starting from *end, walk through the SkRecord to find the first span matching this pattern. + // If there is no such span, return false. If there is, return true and set [*begin, *end). + SK_ALWAYS_INLINE bool search(SkRecord* record, unsigned* begin, unsigned* end) { + for (*begin = *end; *begin < record->count(); ++(*begin)) { + *end = this->match(record, *begin); + if (*end != 0) { + return true; + } + } + return false; + } + + // Once either match or search has succeeded, access the stored data of the first, second, + // or third matcher in this pattern. Add as needed for longer patterns. + // T is checked statically at compile time; no casting is involved. It's just an API wart. + template <typename T> T* first() { return fHead.get(); } + template <typename T> T* second() { return fTail.fHead.get(); } + template <typename T> T* third() { return fTail.fTail.fHead.get(); } + +private: + template <typename T> + void operator()(T* r) { fHeadMatched = fHead.match(r); } + + // If head isn't a Star, try to match at i once. + template <typename T> + unsigned matchHead(T*, SkRecord* record, unsigned i) { + if (i < record->count()) { + fHeadMatched = false; + record->mutate(i, *this); + if (fHeadMatched) { + return i+1; + } + } + return 0; + } + + // If head is a Star, walk i until it doesn't match. + template <typename T> + unsigned matchHead(Star<T>*, SkRecord* record, unsigned i) { + fHead.reset(); + while (i < record->count()) { + fHeadMatched = false; + record->mutate(i, *this); + if (!fHeadMatched) { + return i; + } + i++; + } + return 0; + } + + Matcher fHead; + Pattern fTail; + bool fHeadMatched; + + friend class ::SkRecord; // So operator() can otherwise stay private. + + // All Cons are friends with each other. This lets first, second, and third work. + template <typename, typename> friend class Cons; +}; + +// Nil is the end of every pattern Cons chain. +struct Nil { + // Bottoms out recursion down the fTail chain. Just return whatever i the front decided on. + unsigned match(SkRecord*, unsigned i) { return i; } +}; + +// These Pattern# types are syntax sugar over Cons and Nil, just to help eliminate some of the +// template noise. Use these if you can. Feel free to add more for longer patterns. +// All types A, B, C, ... are Matchers. +template <typename A> +struct Pattern1 : Cons<A, Nil> {}; + +template <typename A, typename B> +struct Pattern2 : Cons<A, Pattern1<B> > {}; + +template <typename A, typename B, typename C> +struct Pattern3 : Cons<A, Pattern2<B, C> > {}; + +} // namespace SkRecords + +#endif//SkRecordPattern_DEFINED diff --git a/record/SkRecordTraits.h b/record/SkRecordTraits.h deleted file mode 100644 index 570a717e..00000000 --- a/record/SkRecordTraits.h +++ /dev/null @@ -1,31 +0,0 @@ -#include "SkRecords.h" -#include "SkTLogic.h" - -// Type traits that are useful for working with SkRecords. - -namespace SkRecords { - -namespace { - -// Abstracts away whether the T is optional or not. -template <typename T> const T* as_ptr(const SkRecords::Optional<T>& x) { return x; } -template <typename T> const T* as_ptr(const T& x) { return &x; } - -} // namespace - -// Gets the paint from any command that may have one. -template <typename Command> const SkPaint* GetPaint(const Command& x) { return as_ptr(x.paint); } - -// Have a paint? You are a draw command! -template <typename Command> struct IsDraw { - SK_CREATE_MEMBER_DETECTOR(paint); - static const bool value = HasMember_paint<Command>::value; -}; - -// Have a clip op? You are a clip command. -template <typename Command> struct IsClip { - SK_CREATE_MEMBER_DETECTOR(op); - static const bool value = HasMember_op<Command>::value; -}; - -} // namespace SkRecords |