experimental/graphite/src/DrawPass.cpp - skia - Git at Google

 /*
  * Copyright 2021 Google LLC
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */

 #include "experimental/graphite/src/DrawPass.h"

 #include "experimental/graphite/include/GraphiteTypes.h"
 #include "experimental/graphite/include/Recorder.h"
 #include "experimental/graphite/src/Buffer.h"
 #include "experimental/graphite/src/ContextPriv.h"
 #include "experimental/graphite/src/ContextUtils.h"
 #include "experimental/graphite/src/DrawBufferManager.h"
 #include "experimental/graphite/src/DrawContext.h"
 #include "experimental/graphite/src/DrawList.h"
 #include "experimental/graphite/src/DrawWriter.h"
 #include "experimental/graphite/src/GraphicsPipeline.h"
 #include "experimental/graphite/src/GraphicsPipelineDesc.h"
 #include "experimental/graphite/src/Renderer.h"
 #include "experimental/graphite/src/ResourceProvider.h"
 #include "experimental/graphite/src/TextureProxy.h"
 #include "experimental/graphite/src/UniformCache.h"
 #include "experimental/graphite/src/UniformManager.h"
 #include "experimental/graphite/src/geom/BoundsManager.h"

 #include "src/core/SkMathPriv.h"
 #include "src/core/SkTBlockList.h"
 #include "src/gpu/BufferWriter.h"

 #include <algorithm>
 #include <unordered_map>

 namespace skgpu {

 // Helper to manage packed fields within a uint64_t
 template <uint64_t Bits, uint64_t Offset>
 struct Bitfield {
     static constexpr uint64_t kMask = ((uint64_t) 1 << Bits) - 1;
     static constexpr uint64_t kOffset = Offset;
     static constexpr uint64_t kBits = Bits;

     static uint32_t get(uint64_t v) { return static_cast<uint32_t>((v >> kOffset) & kMask); }
     static uint64_t set(uint32_t v) { return (v & kMask) << kOffset; }
 };

 /**
  * Each Draw in a DrawList might be processed by multiple RenderSteps (determined by the Draw's
  * Renderer), which can be sorted independently. Each (step, draw) pair produces its own SortKey.
  *
  * The goal of sorting draws for the DrawPass is to minimize pipeline transitions and dynamic binds
  * within a pipeline, while still respecting the overall painter's order. This decreases the number
  * of low-level draw commands in a command buffer and increases the size of those, allowing the GPU
  * to operate more efficiently and have fewer bubbles within its own instruction stream.
  *
  * The Draw's CompresssedPaintersOrder and DisjointStencilINdex represent the most significant bits
  * of the key, and are shared by all SortKeys produced by the same draw. Next, the pipeline
  * description is encoded in two steps:
  *  1. The index of the RenderStep packed in the high bits to ensure each step for a draw is
  *     ordered correctly.
  *  2. An index into a cache of pipeline descriptions is used to encode the identity of the
  *     pipeline (SortKeys that differ in the bits from #1 necessarily would have different
  *     descriptions, but then the specific ordering of the RenderSteps isn't enforced).
  * Last, the SortKey encodes an index into the set of uniform bindings accumulated for a DrawPass.
  * This allows the SortKey to cluster draw steps that have both a compatible pipeline and do not
  * require rebinding uniform data or other state (e.g. scissor). Since the uniform data index and
  * the pipeline description index are packed into indices and not actual pointers, a given SortKey
  * is only valid for the a specific DrawList->DrawPass conversion.
  */
 class DrawPass::SortKey {
 public:
     SortKey(const DrawList::Draw* draw,
             int renderStep,
             uint32_t pipelineIndex,
             uint32_t geomUniformIndex,
             uint32_t shadingUniformIndex)
         : fPipelineKey(ColorDepthOrderField::set(draw->fOrder.paintOrder().bits()) |
                        StencilIndexField::set(draw->fOrder.stencilIndex().bits())  |
                        RenderStepField::set(static_cast<uint32_t>(renderStep))     |
                        PipelineField::set(pipelineIndex))
         , fUniformKey(GeometryUniformField::set(geomUniformIndex) |
                       ShadingUniformField::set(shadingUniformIndex))
         , fDraw(draw) {
         SkASSERT(renderStep <= draw->fRenderer.numRenderSteps());
     }

     bool operator<(const SortKey& k) const {
         return fPipelineKey < k.fPipelineKey ||
                (fPipelineKey == k.fPipelineKey && fUniformKey < k.fUniformKey);
     }

     const RenderStep& renderStep() const {
         return *fDraw->fRenderer.steps()[RenderStepField::get(fPipelineKey)];
     }

     const DrawList::Draw* draw() const { return fDraw; }

     uint32_t pipeline()          const { return PipelineField::get(fPipelineKey);       }
     uint32_t geometryUniforms()  const { return GeometryUniformField::get(fUniformKey); }
     uint32_t shadingUniforms()   const { return ShadingUniformField::get(fUniformKey);  }

 private:
     // Fields are ordered from most-significant to least when sorting by 128-bit value.
     // NOTE: We don't use bit fields because field ordering is implementation defined and we need
     // to sort consistently.
     using ColorDepthOrderField = Bitfield<16, 48>; // sizeof(CompressedPaintersOrder)
     using StencilIndexField    = Bitfield<16, 32>; // sizeof(DisjointStencilIndex)
     using RenderStepField      = Bitfield<2,  30>; // bits >= log2(Renderer::kMaxRenderSteps)
     using PipelineField        = Bitfield<30, 0>;  // bits >= log2(max steps*DrawList::kMaxDraws)
     uint64_t fPipelineKey;

     using GeometryUniformField = Bitfield<32, 32>; // bits >= log2(max steps * max draw count)
     using ShadingUniformField  = Bitfield<32, 0>;  //  ""
     uint64_t fUniformKey;

     // Backpointer to the draw that produced the sort key
     const DrawList::Draw* fDraw;

     static_assert(ColorDepthOrderField::kBits >= sizeof(CompressedPaintersOrder));
     static_assert(StencilIndexField::kBits    >= sizeof(DisjointStencilIndex));
     static_assert(RenderStepField::kBits      >= SkNextLog2_portable(Renderer::kMaxRenderSteps));
     static_assert(PipelineField::kBits        >=
                         SkNextLog2_portable(Renderer::kMaxRenderSteps * DrawList::kMaxDraws));
     static_assert(GeometryUniformField::kBits >= PipelineField::kBits);
     static_assert(ShadingUniformField::kBits  >= PipelineField::kBits);
 };

 class DrawPass::Drawer final : public DrawDispatcher {
 public:
     Drawer(DrawPass* drawPass) : fPass(drawPass) {}
     ~Drawer() override = default;

     void bindDrawBuffers(BindBufferInfo vertexAttribs,
                          BindBufferInfo instanceAttribs,
                          BindBufferInfo indices) override {
         fPass->fCommands.emplace_back(BindDrawBuffers{vertexAttribs, instanceAttribs, indices});
     }

     void draw(PrimitiveType type, unsigned int baseVertex, unsigned int vertexCount) override {
         fPass->fCommands.emplace_back(Draw{type, baseVertex, vertexCount});
     }

     void drawIndexed(PrimitiveType type, unsigned int baseIndex,
                      unsigned int indexCount, unsigned int baseVertex) override {
         fPass->fCommands.emplace_back(DrawIndexed{type, baseIndex, indexCount, baseVertex});
     }

     void drawInstanced(PrimitiveType type,
                        unsigned int baseVertex, unsigned int vertexCount,
                        unsigned int baseInstance, unsigned int instanceCount) override {
         fPass->fCommands.emplace_back(DrawInstanced{type, baseVertex, vertexCount,
                                                     baseInstance, instanceCount});
     }

     void drawIndexedInstanced(PrimitiveType type,
                               unsigned int baseIndex, unsigned int indexCount,
                               unsigned int baseVertex, unsigned int baseInstance,
                               unsigned int instanceCount) override {
         fPass->fCommands.emplace_back(DrawIndexedInstanced{type, baseIndex, indexCount, baseVertex,
                                                            baseInstance, instanceCount});
     }

 private:
     DrawPass* fPass;
 };

 ///////////////////////////////////////////////////////////////////////////////////////////////////

 namespace {

 class UniformBindingCache {
 public:
     UniformBindingCache(DrawBufferManager* bufferMgr, UniformCache* cache)
             : fBufferMgr(bufferMgr), fCache(cache) {}

     uint32_t addUniforms(sk_sp<UniformData> data) {
         if (!data) {
             return UniformCache::kInvalidUniformID;
         }

         uint32_t index = fCache->insert(data);
         if (fBindings.find(index) == fBindings.end()) {
             // First time encountering this data, so upload to the GPU
             auto [writer, bufferInfo] = fBufferMgr->getUniformWriter(data->dataSize());
             writer.write(data->data(), data->dataSize());
             fBindings.insert({index, bufferInfo});
         }

         return index;
     }

     BindBufferInfo getBinding(uint32_t uniformIndex) {
         auto lookup = fBindings.find(uniformIndex);
         SkASSERT(lookup != fBindings.end());
         return lookup->second;
     }

 private:
     DrawBufferManager* fBufferMgr;
     UniformCache*      fCache;

     std::unordered_map<uint32_t, BindBufferInfo> fBindings;
 };

 // std::unordered_map implementation for GraphicsPipelineDesc* that de-reference the pointers.
 struct Hash {
     size_t operator()(const skgpu::GraphicsPipelineDesc* desc) const noexcept {
         return skgpu::GraphicsPipelineDesc::Hash()(*desc);
     }
 };

 struct Eq {
     bool operator()(const skgpu::GraphicsPipelineDesc* a,
                     const skgpu::GraphicsPipelineDesc* b) const noexcept {
         return *a == *b;
     }
 };

 } // anonymous namespace

 DrawPass::DrawPass(sk_sp<TextureProxy> target,
                    std::pair<LoadOp, StoreOp> ops,
                    std::array<float, 4> clearColor,
                    int renderStepCount)
         : fCommands(std::max(1, renderStepCount / 4), SkBlockAllocator::GrowthPolicy::kFibonacci)
         , fTarget(std::move(target))
         , fBounds(SkIRect::MakeEmpty())
         , fOps(ops)
         , fClearColor(clearColor) {
     // TODO: Tune this estimate and the above "itemPerBlock" value for the command buffer sequence
     // After merging, etc. one pipeline per recorded draw+step combo is likely unnecessary.
     fPipelineDescs.reserve(renderStepCount);
     fCommands.reserve(renderStepCount);
 }

 DrawPass::~DrawPass() = default;

 std::unique_ptr<DrawPass> DrawPass::Make(Recorder* recorder,
                                          std::unique_ptr<DrawList> draws,
                                          sk_sp<TextureProxy> target,
                                          std::pair<LoadOp, StoreOp> ops,
                                          std::array<float, 4> clearColor,
                                          const BoundsManager* occlusionCuller) {
     // NOTE: This assert is here to ensure SortKey is as tightly packed as possible. Any change to
     // its size should be done with care and good reason. The performance of sorting the keys is
     // heavily tied to the total size.
     //
     // At 24 bytes (current), sorting is about 30% slower than if SortKey could be packed into just
     // 16 bytes. There are several ways this could be done if necessary:
     //  - Restricting the max draw count to 16k (14-bits) and only using a single index to refer to
     //    the uniform data => 8 bytes of key, 8 bytes of pointer.
     //  - Restrict the max draw count to 32k (15-bits), use a single uniform index, and steal the
     //    4 low bits from the Draw* pointer since it's 16 byte aligned.
     //  - Compact the Draw* to an index into the original collection, although that has extra
     //    indirection and does not work as well with SkTBlockList.
     // In pseudo tests, manipulating the pointer or having to mask out indices was about 15% slower
     // than an 8 byte key and unmodified pointer.
     static_assert(sizeof(DrawPass::SortKey) == 16 + sizeof(void*));

     // The DrawList is converted directly into the DrawPass' data structures, but once the DrawPass
     // is returned from Make(), it is considered immutable.
     std::unique_ptr<DrawPass> drawPass(new DrawPass(std::move(target), ops, clearColor,
                                                     draws->renderStepCount()));

     Rect passBounds = Rect::InfiniteInverted();

     DrawBufferManager* bufferMgr = recorder->drawBufferManager();
     UniformCache geometryUniforms;
     UniformBindingCache geometryUniformBindings(bufferMgr, &geometryUniforms);
     UniformBindingCache shadingUniformBindings(bufferMgr, recorder->uniformCache());

     std::unordered_map<const GraphicsPipelineDesc*, uint32_t, Hash, Eq> pipelineDescToIndex;

     std::vector<SortKey> keys;
     keys.reserve(draws->renderStepCount()); // will not exceed but may use less with occluded draws

     for (const DrawList::Draw& draw : draws->fDraws.items()) {
         if (occlusionCuller && occlusionCuller->isOccluded(draw.fClip.drawBounds(),
                                                            draw.fOrder.depth())) {
             continue;
         }

         // If we have two different descriptors, such that the uniforms from the PaintParams can be
         // bound independently of those used by the rest of the RenderStep, then we can upload now
         // and remember the location for re-use on any RenderStep that does shading.
         SkUniquePaintParamsID shaderID;
         sk_sp<UniformData> shadingUniforms = nullptr;
         uint32_t shadingIndex = UniformCache::kInvalidUniformID;
         if (draw.fPaintParams.has_value()) {
             std::tie(shaderID, shadingUniforms) = ExtractPaintData(recorder->context(),
                                                                    draw.fPaintParams.value());
             shadingIndex = shadingUniformBindings.addUniforms(shadingUniforms);
         } // else depth-only

         for (int stepIndex = 0; stepIndex < draw.fRenderer.numRenderSteps(); ++stepIndex) {
             const RenderStep* const step = draw.fRenderer.steps()[stepIndex];
             const bool performsShading = draw.fPaintParams.has_value() && step->performsShading();

             SkUniquePaintParamsID stepShaderID;
             uint32_t stepShadingIndex = UniformCache::kInvalidUniformID;
             if (performsShading) {
                 stepShaderID = shaderID;
                 stepShadingIndex = shadingIndex;
             } // else depth-only draw or stencil-only step of renderer so no shading is needed

             uint32_t geometryIndex = UniformCache::kInvalidUniformID;
             if (step->numUniforms() > 0) {
                 // TODO: Get layout from the GPU
                 auto uniforms = step->writeUniforms(Layout::kMetal,
                                                     draw.fClip.scissor(),
                                                     draw.fTransform,
                                                     draw.fShape);
                 geometryIndex = geometryUniformBindings.addUniforms(std::move(uniforms));
             }

             GraphicsPipelineDesc desc;
             desc.setProgram(step, stepShaderID);
             uint32_t pipelineIndex = 0;
             auto pipelineLookup = pipelineDescToIndex.find(&desc);
             if (pipelineLookup == pipelineDescToIndex.end()) {
                 // Assign new index to first appearance of this pipeline description
                 pipelineIndex = SkTo<uint32_t>(drawPass->fPipelineDescs.count());
                 const GraphicsPipelineDesc& finalDesc = drawPass->fPipelineDescs.push_back(desc);
                 pipelineDescToIndex.insert({&finalDesc, pipelineIndex});
             } else {
                 // Reuse the existing pipeline description for better batching after sorting
                 pipelineIndex = pipelineLookup->second;
             }

             keys.push_back({&draw, stepIndex, pipelineIndex, geometryIndex, stepShadingIndex});
         }

         passBounds.join(draw.fClip.drawBounds());
         drawPass->fDepthStencilFlags |= draw.fRenderer.depthStencilFlags();
         drawPass->fRequiresMSAA |= draw.fRenderer.requiresMSAA();
     }

     // TODO: Explore sorting algorithms; in all likelihood this will be mostly sorted already, so
     // algorithms that approach O(n) in that condition may be favorable. Alternatively, could
     // explore radix sort that is always O(n). Brief testing suggested std::sort was faster than
     // std::stable_sort and SkTQSort on my [ml]'s Windows desktop. Also worth considering in-place
     // vs. algorithms that require an extra O(n) storage.
     // TODO: It's not strictly necessary, but would a stable sort be useful or just end up hiding
     // bugs in the DrawOrder determination code?
     std::sort(keys.begin(), keys.end());

     // Used to record vertex/instance data, buffer binds, and draw calls
     Drawer drawer(drawPass.get());
     DrawWriter drawWriter(&drawer, bufferMgr);

     // Used to track when a new pipeline or dynamic state needs recording between draw steps.
     // Setting to # render steps ensures the very first time through the loop will bind a pipeline.
     uint32_t lastPipeline = draws->renderStepCount();
     uint32_t lastShadingUniforms = UniformCache::kInvalidUniformID;
     uint32_t lastGeometryUniforms = UniformCache::kInvalidUniformID;
     SkIRect lastScissor = SkIRect::MakeSize(drawPass->fTarget->dimensions());

     for (const SortKey& key : keys) {
         const DrawList::Draw& draw = *key.draw();
         const RenderStep& renderStep = key.renderStep();

         const bool pipelineChange = key.pipeline() != lastPipeline;
         const bool stateChange = key.geometryUniforms() != lastGeometryUniforms ||
                                  key.shadingUniforms() != lastShadingUniforms ||
                                  draw.fClip.scissor() != lastScissor;

         // Update DrawWriter *before* we actually change any state so that accumulated draws from
         // the previous state use the proper state.
         if (pipelineChange) {
             drawWriter.newPipelineState(renderStep.primitiveType(),
                                         renderStep.vertexStride(),
                                         renderStep.instanceStride());
         } else if (stateChange) {
             drawWriter.newDynamicState();
         }

         // Make state changes before accumulating new draw data
         if (pipelineChange) {
             drawPass->fCommands.emplace_back(BindGraphicsPipeline{key.pipeline()});
             lastPipeline = key.pipeline();
             lastShadingUniforms = UniformCache::kInvalidUniformID;
             lastGeometryUniforms = UniformCache::kInvalidUniformID;
         }
         if (stateChange) {
             if (key.geometryUniforms() != lastGeometryUniforms) {
                 if (key.geometryUniforms() != UniformCache::kInvalidUniformID) {
                     auto binding = geometryUniformBindings.getBinding(key.geometryUniforms());
                     drawPass->fCommands.emplace_back(
                             BindUniformBuffer{binding, UniformSlot::kRenderStep});
                 }
                 lastGeometryUniforms = key.geometryUniforms();
             }
             if (key.shadingUniforms() != lastShadingUniforms) {
                 if (key.shadingUniforms() != UniformCache::kInvalidUniformID) {
                     auto binding = shadingUniformBindings.getBinding(key.shadingUniforms());
                     drawPass->fCommands.emplace_back(
                             BindUniformBuffer{binding, UniformSlot::kPaint});
                 }
                 lastShadingUniforms = key.shadingUniforms();
             }
             if (draw.fClip.scissor() != lastScissor) {
                 drawPass->fCommands.emplace_back(SetScissor{draw.fClip.scissor()});
                 lastScissor = draw.fClip.scissor();
             }
         }

         renderStep.writeVertices(&drawWriter, draw.fClip.scissor(), draw.fTransform, draw.fShape);
     }
     // Finish recording draw calls for any collected data at the end of the loop
     drawWriter.flush();

     passBounds.roundOut();
     drawPass->fBounds = SkIRect::MakeLTRB((int) passBounds.left(), (int) passBounds.top(),
                                           (int) passBounds.right(), (int) passBounds.bot());
     return drawPass;
 }

 void DrawPass::addCommands(Context* context, CommandBuffer* buffer,
                            const RenderPassDesc& renderPassDesc) const {
     auto resourceProvider = context->priv().resourceProvider();

     // TODO: Validate RenderPass state against DrawPass's target and requirements?
     // Generate actual GraphicsPipeline objects combining the target-level properties and each of
     // the GraphicsPipelineDesc's referenced in this DrawPass.

     // Use a vector instead of SkTBlockList for the full pipelines so that random access is fast.
     std::vector<sk_sp<GraphicsPipeline>> fullPipelines;
     fullPipelines.reserve(fPipelineDescs.count());
     for (const GraphicsPipelineDesc& pipelineDesc : fPipelineDescs.items()) {
         fullPipelines.push_back(resourceProvider->findOrCreateGraphicsPipeline(
                 context, pipelineDesc, renderPassDesc));
     }

     // Set viewport to the entire texture for now (eventually, we may have logically smaller bounds
     // within an approx-sized texture). It is assumed that this also configures the sk_rtAdjust
     // intrinsic for programs (however the backend chooses to do so).
     buffer->setViewport(0, 0, fTarget->dimensions().width(), fTarget->dimensions().height());

     for (const Command& c : fCommands.items()) {
         switch(c.fType) {
             case CommandType::kBindGraphicsPipeline: {
                 auto& d = c.fBindGraphicsPipeline;
                 buffer->bindGraphicsPipeline(fullPipelines[d.fPipelineIndex]);
                 break; }
             case CommandType::kBindUniformBuffer: {
                 auto& d = c.fBindUniformBuffer;
                 buffer->bindUniformBuffer(d.fSlot, sk_ref_sp(d.fInfo.fBuffer), d.fInfo.fOffset);
                 break; }
             case CommandType::kBindDrawBuffers: {
                 auto& d = c.fBindDrawBuffers;
                 buffer->bindDrawBuffers(d.fVertices, d.fInstances, d.fIndices);
                 break; }
             case CommandType::kDraw: {
                 auto& d = c.fDraw;
                 buffer->draw(d.fType, d.fBaseVertex, d.fVertexCount);
                 break; }
             case CommandType::kDrawIndexed: {
                 auto& d = c.fDrawIndexed;
                 buffer->drawIndexed(d.fType, d.fBaseIndex, d.fIndexCount, d.fBaseVertex);
                 break; }
             case CommandType::kDrawInstanced: {
                 auto& d = c.fDrawInstanced;
                 buffer->drawInstanced(d.fType, d.fBaseVertex, d.fVertexCount,
                                       d.fBaseInstance, d.fInstanceCount);
                 break; }
             case CommandType::kDrawIndexedInstanced: {
                 auto& d = c.fDrawIndexedInstanced;
                 buffer->drawIndexedInstanced(d.fType, d.fBaseIndex, d.fIndexCount, d.fBaseVertex,
                                              d.fBaseInstance, d.fInstanceCount);
                 break; }
             case CommandType::kSetScissor: {
                 auto& d = c.fSetScissor;
                 buffer->setScissor(d.fScissor.fLeft, d.fScissor.fTop,
                                    d.fScissor.fRight, d.fScissor.fBottom);
                 break;
             }
         }
     }
 }

 } // namespace skgpu
	/*
	* Copyright 2021 Google LLC
	*
	* Use of this source code is governed by a BSD-style license that can be
	* found in the LICENSE file.
	*/

	#include "experimental/graphite/src/DrawPass.h"

	#include "experimental/graphite/include/GraphiteTypes.h"
	#include "experimental/graphite/include/Recorder.h"
	#include "experimental/graphite/src/Buffer.h"
	#include "experimental/graphite/src/ContextPriv.h"
	#include "experimental/graphite/src/ContextUtils.h"
	#include "experimental/graphite/src/DrawBufferManager.h"
	#include "experimental/graphite/src/DrawContext.h"
	#include "experimental/graphite/src/DrawList.h"
	#include "experimental/graphite/src/DrawWriter.h"
	#include "experimental/graphite/src/GraphicsPipeline.h"
	#include "experimental/graphite/src/GraphicsPipelineDesc.h"
	#include "experimental/graphite/src/Renderer.h"
	#include "experimental/graphite/src/ResourceProvider.h"
	#include "experimental/graphite/src/TextureProxy.h"
	#include "experimental/graphite/src/UniformCache.h"
	#include "experimental/graphite/src/UniformManager.h"
	#include "experimental/graphite/src/geom/BoundsManager.h"

	#include "src/core/SkMathPriv.h"
	#include "src/core/SkTBlockList.h"
	#include "src/gpu/BufferWriter.h"

	#include <algorithm>
	#include <unordered_map>

	namespace skgpu {

	// Helper to manage packed fields within a uint64_t
	template <uint64_t Bits, uint64_t Offset>
	struct Bitfield {
	static constexpr uint64_t kMask = ((uint64_t) 1 << Bits) - 1;
	static constexpr uint64_t kOffset = Offset;
	static constexpr uint64_t kBits = Bits;

	static uint32_t get(uint64_t v) { return static_cast<uint32_t>((v >> kOffset) & kMask); }
	static uint64_t set(uint32_t v) { return (v & kMask) << kOffset; }
	};

	/**
	* Each Draw in a DrawList might be processed by multiple RenderSteps (determined by the Draw's
	* Renderer), which can be sorted independently. Each (step, draw) pair produces its own SortKey.
	*
	* The goal of sorting draws for the DrawPass is to minimize pipeline transitions and dynamic binds
	* within a pipeline, while still respecting the overall painter's order. This decreases the number
	* of low-level draw commands in a command buffer and increases the size of those, allowing the GPU
	* to operate more efficiently and have fewer bubbles within its own instruction stream.
	*
	* The Draw's CompresssedPaintersOrder and DisjointStencilINdex represent the most significant bits
	* of the key, and are shared by all SortKeys produced by the same draw. Next, the pipeline
	* description is encoded in two steps:
	* 1. The index of the RenderStep packed in the high bits to ensure each step for a draw is
	* ordered correctly.
	* 2. An index into a cache of pipeline descriptions is used to encode the identity of the
	* pipeline (SortKeys that differ in the bits from #1 necessarily would have different
	* descriptions, but then the specific ordering of the RenderSteps isn't enforced).
	* Last, the SortKey encodes an index into the set of uniform bindings accumulated for a DrawPass.
	* This allows the SortKey to cluster draw steps that have both a compatible pipeline and do not
	* require rebinding uniform data or other state (e.g. scissor). Since the uniform data index and
	* the pipeline description index are packed into indices and not actual pointers, a given SortKey
	* is only valid for the a specific DrawList->DrawPass conversion.
	*/
	class DrawPass::SortKey {
	public:
	SortKey(const DrawList::Draw* draw,
	int renderStep,
	uint32_t pipelineIndex,
	uint32_t geomUniformIndex,
	uint32_t shadingUniformIndex)
	: fPipelineKey(ColorDepthOrderField::set(draw->fOrder.paintOrder().bits()) \|
	StencilIndexField::set(draw->fOrder.stencilIndex().bits()) \|
	RenderStepField::set(static_cast<uint32_t>(renderStep)) \|
	PipelineField::set(pipelineIndex))
	, fUniformKey(GeometryUniformField::set(geomUniformIndex) \|
	ShadingUniformField::set(shadingUniformIndex))
	, fDraw(draw) {
	SkASSERT(renderStep <= draw->fRenderer.numRenderSteps());
	}

	bool operator<(const SortKey& k) const {
	return fPipelineKey < k.fPipelineKey \|\|
	(fPipelineKey == k.fPipelineKey && fUniformKey < k.fUniformKey);
	}

	const RenderStep& renderStep() const {
	return *fDraw->fRenderer.steps()[RenderStepField::get(fPipelineKey)];
	}

	const DrawList::Draw* draw() const { return fDraw; }

	uint32_t pipeline() const { return PipelineField::get(fPipelineKey); }
	uint32_t geometryUniforms() const { return GeometryUniformField::get(fUniformKey); }
	uint32_t shadingUniforms() const { return ShadingUniformField::get(fUniformKey); }

	private:
	// Fields are ordered from most-significant to least when sorting by 128-bit value.
	// NOTE: We don't use bit fields because field ordering is implementation defined and we need
	// to sort consistently.
	using ColorDepthOrderField = Bitfield<16, 48>; // sizeof(CompressedPaintersOrder)
	using StencilIndexField = Bitfield<16, 32>; // sizeof(DisjointStencilIndex)
	using RenderStepField = Bitfield<2, 30>; // bits >= log2(Renderer::kMaxRenderSteps)
	using PipelineField = Bitfield<30, 0>; // bits >= log2(max steps*DrawList::kMaxDraws)
	uint64_t fPipelineKey;

	using GeometryUniformField = Bitfield<32, 32>; // bits >= log2(max steps * max draw count)
	using ShadingUniformField = Bitfield<32, 0>; // ""
	uint64_t fUniformKey;

	// Backpointer to the draw that produced the sort key
	const DrawList::Draw* fDraw;

	static_assert(ColorDepthOrderField::kBits >= sizeof(CompressedPaintersOrder));
	static_assert(StencilIndexField::kBits >= sizeof(DisjointStencilIndex));
	static_assert(RenderStepField::kBits >= SkNextLog2_portable(Renderer::kMaxRenderSteps));
	static_assert(PipelineField::kBits >=
	SkNextLog2_portable(Renderer::kMaxRenderSteps * DrawList::kMaxDraws));
	static_assert(GeometryUniformField::kBits >= PipelineField::kBits);
	static_assert(ShadingUniformField::kBits >= PipelineField::kBits);
	};

	class DrawPass::Drawer final : public DrawDispatcher {
	public:
	Drawer(DrawPass* drawPass) : fPass(drawPass) {}
	~Drawer() override = default;

	void bindDrawBuffers(BindBufferInfo vertexAttribs,
	BindBufferInfo instanceAttribs,
	BindBufferInfo indices) override {
	fPass->fCommands.emplace_back(BindDrawBuffers{vertexAttribs, instanceAttribs, indices});
	}

	void draw(PrimitiveType type, unsigned int baseVertex, unsigned int vertexCount) override {
	fPass->fCommands.emplace_back(Draw{type, baseVertex, vertexCount});
	}

	void drawIndexed(PrimitiveType type, unsigned int baseIndex,
	unsigned int indexCount, unsigned int baseVertex) override {
	fPass->fCommands.emplace_back(DrawIndexed{type, baseIndex, indexCount, baseVertex});
	}

	void drawInstanced(PrimitiveType type,
	unsigned int baseVertex, unsigned int vertexCount,
	unsigned int baseInstance, unsigned int instanceCount) override {
	fPass->fCommands.emplace_back(DrawInstanced{type, baseVertex, vertexCount,
	baseInstance, instanceCount});
	}

	void drawIndexedInstanced(PrimitiveType type,
	unsigned int baseIndex, unsigned int indexCount,
	unsigned int baseVertex, unsigned int baseInstance,
	unsigned int instanceCount) override {
	fPass->fCommands.emplace_back(DrawIndexedInstanced{type, baseIndex, indexCount, baseVertex,
	baseInstance, instanceCount});
	}

	private:
	DrawPass* fPass;
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////

	namespace {

	class UniformBindingCache {
	public:
	UniformBindingCache(DrawBufferManager* bufferMgr, UniformCache* cache)
	: fBufferMgr(bufferMgr), fCache(cache) {}

	uint32_t addUniforms(sk_sp<UniformData> data) {
	if (!data) {
	return UniformCache::kInvalidUniformID;
	}

	uint32_t index = fCache->insert(data);
	if (fBindings.find(index) == fBindings.end()) {
	// First time encountering this data, so upload to the GPU
	auto [writer, bufferInfo] = fBufferMgr->getUniformWriter(data->dataSize());
	writer.write(data->data(), data->dataSize());
	fBindings.insert({index, bufferInfo});
	}

	return index;
	}

	BindBufferInfo getBinding(uint32_t uniformIndex) {
	auto lookup = fBindings.find(uniformIndex);
	SkASSERT(lookup != fBindings.end());
	return lookup->second;
	}

	private:
	DrawBufferManager* fBufferMgr;
	UniformCache* fCache;

	std::unordered_map<uint32_t, BindBufferInfo> fBindings;
	};

	// std::unordered_map implementation for GraphicsPipelineDesc* that de-reference the pointers.
	struct Hash {
	size_t operator()(const skgpu::GraphicsPipelineDesc* desc) const noexcept {
	return skgpu::GraphicsPipelineDesc::Hash()(*desc);
	}
	};

	struct Eq {
	bool operator()(const skgpu::GraphicsPipelineDesc* a,
	const skgpu::GraphicsPipelineDesc* b) const noexcept {
	return a == b;
	}
	};

	} // anonymous namespace

	DrawPass::DrawPass(sk_sp<TextureProxy> target,
	std::pair<LoadOp, StoreOp> ops,
	std::array<float, 4> clearColor,
	int renderStepCount)
	: fCommands(std::max(1, renderStepCount / 4), SkBlockAllocator::GrowthPolicy::kFibonacci)
	, fTarget(std::move(target))
	, fBounds(SkIRect::MakeEmpty())
	, fOps(ops)
	, fClearColor(clearColor) {
	// TODO: Tune this estimate and the above "itemPerBlock" value for the command buffer sequence
	// After merging, etc. one pipeline per recorded draw+step combo is likely unnecessary.
	fPipelineDescs.reserve(renderStepCount);
	fCommands.reserve(renderStepCount);
	}

	DrawPass::~DrawPass() = default;

	std::unique_ptr<DrawPass> DrawPass::Make(Recorder* recorder,
	std::unique_ptr<DrawList> draws,
	sk_sp<TextureProxy> target,
	std::pair<LoadOp, StoreOp> ops,
	std::array<float, 4> clearColor,
	const BoundsManager* occlusionCuller) {
	// NOTE: This assert is here to ensure SortKey is as tightly packed as possible. Any change to
	// its size should be done with care and good reason. The performance of sorting the keys is
	// heavily tied to the total size.
	//
	// At 24 bytes (current), sorting is about 30% slower than if SortKey could be packed into just
	// 16 bytes. There are several ways this could be done if necessary:
	// - Restricting the max draw count to 16k (14-bits) and only using a single index to refer to
	// the uniform data => 8 bytes of key, 8 bytes of pointer.
	// - Restrict the max draw count to 32k (15-bits), use a single uniform index, and steal the
	// 4 low bits from the Draw* pointer since it's 16 byte aligned.
	// - Compact the Draw* to an index into the original collection, although that has extra
	// indirection and does not work as well with SkTBlockList.
	// In pseudo tests, manipulating the pointer or having to mask out indices was about 15% slower
	// than an 8 byte key and unmodified pointer.
	static_assert(sizeof(DrawPass::SortKey) == 16 + sizeof(void*));

	// The DrawList is converted directly into the DrawPass' data structures, but once the DrawPass
	// is returned from Make(), it is considered immutable.
	std::unique_ptr<DrawPass> drawPass(new DrawPass(std::move(target), ops, clearColor,
	draws->renderStepCount()));

	Rect passBounds = Rect::InfiniteInverted();

	DrawBufferManager* bufferMgr = recorder->drawBufferManager();
	UniformCache geometryUniforms;
	UniformBindingCache geometryUniformBindings(bufferMgr, &geometryUniforms);
	UniformBindingCache shadingUniformBindings(bufferMgr, recorder->uniformCache());

	std::unordered_map<const GraphicsPipelineDesc*, uint32_t, Hash, Eq> pipelineDescToIndex;

	std::vector<SortKey> keys;
	keys.reserve(draws->renderStepCount()); // will not exceed but may use less with occluded draws

	for (const DrawList::Draw& draw : draws->fDraws.items()) {
	if (occlusionCuller && occlusionCuller->isOccluded(draw.fClip.drawBounds(),
	draw.fOrder.depth())) {
	continue;
	}

	// If we have two different descriptors, such that the uniforms from the PaintParams can be
	// bound independently of those used by the rest of the RenderStep, then we can upload now
	// and remember the location for re-use on any RenderStep that does shading.
	SkUniquePaintParamsID shaderID;
	sk_sp<UniformData> shadingUniforms = nullptr;
	uint32_t shadingIndex = UniformCache::kInvalidUniformID;
	if (draw.fPaintParams.has_value()) {
	std::tie(shaderID, shadingUniforms) = ExtractPaintData(recorder->context(),
	draw.fPaintParams.value());
	shadingIndex = shadingUniformBindings.addUniforms(shadingUniforms);
	} // else depth-only

	for (int stepIndex = 0; stepIndex < draw.fRenderer.numRenderSteps(); ++stepIndex) {
	const RenderStep* const step = draw.fRenderer.steps()[stepIndex];
	const bool performsShading = draw.fPaintParams.has_value() && step->performsShading();

	SkUniquePaintParamsID stepShaderID;
	uint32_t stepShadingIndex = UniformCache::kInvalidUniformID;
	if (performsShading) {
	stepShaderID = shaderID;
	stepShadingIndex = shadingIndex;
	} // else depth-only draw or stencil-only step of renderer so no shading is needed

	uint32_t geometryIndex = UniformCache::kInvalidUniformID;
	if (step->numUniforms() > 0) {
	// TODO: Get layout from the GPU
	auto uniforms = step->writeUniforms(Layout::kMetal,
	draw.fClip.scissor(),
	draw.fTransform,
	draw.fShape);
	geometryIndex = geometryUniformBindings.addUniforms(std::move(uniforms));
	}

	GraphicsPipelineDesc desc;
	desc.setProgram(step, stepShaderID);
	uint32_t pipelineIndex = 0;
	auto pipelineLookup = pipelineDescToIndex.find(&desc);
	if (pipelineLookup == pipelineDescToIndex.end()) {
	// Assign new index to first appearance of this pipeline description
	pipelineIndex = SkTo<uint32_t>(drawPass->fPipelineDescs.count());
	const GraphicsPipelineDesc& finalDesc = drawPass->fPipelineDescs.push_back(desc);
	pipelineDescToIndex.insert({&finalDesc, pipelineIndex});
	} else {
	// Reuse the existing pipeline description for better batching after sorting
	pipelineIndex = pipelineLookup->second;
	}

	keys.push_back({&draw, stepIndex, pipelineIndex, geometryIndex, stepShadingIndex});
	}

	passBounds.join(draw.fClip.drawBounds());
	drawPass->fDepthStencilFlags \|= draw.fRenderer.depthStencilFlags();
	drawPass->fRequiresMSAA \|= draw.fRenderer.requiresMSAA();
	}

	// TODO: Explore sorting algorithms; in all likelihood this will be mostly sorted already, so
	// algorithms that approach O(n) in that condition may be favorable. Alternatively, could
	// explore radix sort that is always O(n). Brief testing suggested std::sort was faster than
	// std::stable_sort and SkTQSort on my [ml]'s Windows desktop. Also worth considering in-place
	// vs. algorithms that require an extra O(n) storage.
	// TODO: It's not strictly necessary, but would a stable sort be useful or just end up hiding
	// bugs in the DrawOrder determination code?
	std::sort(keys.begin(), keys.end());

	// Used to record vertex/instance data, buffer binds, and draw calls
	Drawer drawer(drawPass.get());
	DrawWriter drawWriter(&drawer, bufferMgr);

	// Used to track when a new pipeline or dynamic state needs recording between draw steps.
	// Setting to # render steps ensures the very first time through the loop will bind a pipeline.
	uint32_t lastPipeline = draws->renderStepCount();
	uint32_t lastShadingUniforms = UniformCache::kInvalidUniformID;
	uint32_t lastGeometryUniforms = UniformCache::kInvalidUniformID;
	SkIRect lastScissor = SkIRect::MakeSize(drawPass->fTarget->dimensions());

	for (const SortKey& key : keys) {
	const DrawList::Draw& draw = *key.draw();
	const RenderStep& renderStep = key.renderStep();

	const bool pipelineChange = key.pipeline() != lastPipeline;
	const bool stateChange = key.geometryUniforms() != lastGeometryUniforms \|\|
	key.shadingUniforms() != lastShadingUniforms \|\|
	draw.fClip.scissor() != lastScissor;

	// Update DrawWriter before we actually change any state so that accumulated draws from
	// the previous state use the proper state.
	if (pipelineChange) {
	drawWriter.newPipelineState(renderStep.primitiveType(),
	renderStep.vertexStride(),
	renderStep.instanceStride());
	} else if (stateChange) {
	drawWriter.newDynamicState();
	}

	// Make state changes before accumulating new draw data
	if (pipelineChange) {
	drawPass->fCommands.emplace_back(BindGraphicsPipeline{key.pipeline()});
	lastPipeline = key.pipeline();
	lastShadingUniforms = UniformCache::kInvalidUniformID;
	lastGeometryUniforms = UniformCache::kInvalidUniformID;
	}
	if (stateChange) {
	if (key.geometryUniforms() != lastGeometryUniforms) {
	if (key.geometryUniforms() != UniformCache::kInvalidUniformID) {
	auto binding = geometryUniformBindings.getBinding(key.geometryUniforms());
	drawPass->fCommands.emplace_back(
	BindUniformBuffer{binding, UniformSlot::kRenderStep});
	}
	lastGeometryUniforms = key.geometryUniforms();
	}
	if (key.shadingUniforms() != lastShadingUniforms) {
	if (key.shadingUniforms() != UniformCache::kInvalidUniformID) {
	auto binding = shadingUniformBindings.getBinding(key.shadingUniforms());
	drawPass->fCommands.emplace_back(
	BindUniformBuffer{binding, UniformSlot::kPaint});
	}
	lastShadingUniforms = key.shadingUniforms();
	}
	if (draw.fClip.scissor() != lastScissor) {
	drawPass->fCommands.emplace_back(SetScissor{draw.fClip.scissor()});
	lastScissor = draw.fClip.scissor();
	}
	}

	renderStep.writeVertices(&drawWriter, draw.fClip.scissor(), draw.fTransform, draw.fShape);
	}
	// Finish recording draw calls for any collected data at the end of the loop
	drawWriter.flush();

	passBounds.roundOut();
	drawPass->fBounds = SkIRect::MakeLTRB((int) passBounds.left(), (int) passBounds.top(),
	(int) passBounds.right(), (int) passBounds.bot());
	return drawPass;
	}

	void DrawPass::addCommands(Context* context, CommandBuffer* buffer,
	const RenderPassDesc& renderPassDesc) const {
	auto resourceProvider = context->priv().resourceProvider();

	// TODO: Validate RenderPass state against DrawPass's target and requirements?
	// Generate actual GraphicsPipeline objects combining the target-level properties and each of
	// the GraphicsPipelineDesc's referenced in this DrawPass.

	// Use a vector instead of SkTBlockList for the full pipelines so that random access is fast.
	std::vector<sk_sp<GraphicsPipeline>> fullPipelines;
	fullPipelines.reserve(fPipelineDescs.count());
	for (const GraphicsPipelineDesc& pipelineDesc : fPipelineDescs.items()) {
	fullPipelines.push_back(resourceProvider->findOrCreateGraphicsPipeline(
	context, pipelineDesc, renderPassDesc));
	}

	// Set viewport to the entire texture for now (eventually, we may have logically smaller bounds
	// within an approx-sized texture). It is assumed that this also configures the sk_rtAdjust
	// intrinsic for programs (however the backend chooses to do so).
	buffer->setViewport(0, 0, fTarget->dimensions().width(), fTarget->dimensions().height());

	for (const Command& c : fCommands.items()) {
	switch(c.fType) {
	case CommandType::kBindGraphicsPipeline: {
	auto& d = c.fBindGraphicsPipeline;
	buffer->bindGraphicsPipeline(fullPipelines[d.fPipelineIndex]);
	break; }
	case CommandType::kBindUniformBuffer: {
	auto& d = c.fBindUniformBuffer;
	buffer->bindUniformBuffer(d.fSlot, sk_ref_sp(d.fInfo.fBuffer), d.fInfo.fOffset);
	break; }
	case CommandType::kBindDrawBuffers: {
	auto& d = c.fBindDrawBuffers;
	buffer->bindDrawBuffers(d.fVertices, d.fInstances, d.fIndices);
	break; }
	case CommandType::kDraw: {
	auto& d = c.fDraw;
	buffer->draw(d.fType, d.fBaseVertex, d.fVertexCount);
	break; }
	case CommandType::kDrawIndexed: {
	auto& d = c.fDrawIndexed;
	buffer->drawIndexed(d.fType, d.fBaseIndex, d.fIndexCount, d.fBaseVertex);
	break; }
	case CommandType::kDrawInstanced: {
	auto& d = c.fDrawInstanced;
	buffer->drawInstanced(d.fType, d.fBaseVertex, d.fVertexCount,
	d.fBaseInstance, d.fInstanceCount);
	break; }
	case CommandType::kDrawIndexedInstanced: {
	auto& d = c.fDrawIndexedInstanced;
	buffer->drawIndexedInstanced(d.fType, d.fBaseIndex, d.fIndexCount, d.fBaseVertex,
	d.fBaseInstance, d.fInstanceCount);
	break; }
	case CommandType::kSetScissor: {
	auto& d = c.fSetScissor;
	buffer->setScissor(d.fScissor.fLeft, d.fScissor.fTop,
	d.fScissor.fRight, d.fScissor.fBottom);
	break;
	}
	}
	}
	}

	} // namespace skgpu