diff options
Diffstat (limited to 'thirdparty/glslang/SPIRV/InReadableOrder.cpp')
| -rw-r--r-- | thirdparty/glslang/SPIRV/InReadableOrder.cpp | 131 |
1 files changed, 131 insertions, 0 deletions
diff --git a/thirdparty/glslang/SPIRV/InReadableOrder.cpp b/thirdparty/glslang/SPIRV/InReadableOrder.cpp new file mode 100644 index 0000000000..9d9410be93 --- /dev/null +++ b/thirdparty/glslang/SPIRV/InReadableOrder.cpp @@ -0,0 +1,131 @@ +// +// Copyright (C) 2016 Google, Inc. +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions +// are met: +// +// Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// +// Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// +// Neither the name of 3Dlabs Inc. Ltd. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS +// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE +// COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, +// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, +// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN +// ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +// POSSIBILITY OF SUCH DAMAGE. + +// The SPIR-V spec requires code blocks to appear in an order satisfying the +// dominator-tree direction (ie, dominator before the dominated). This is, +// actually, easy to achieve: any pre-order CFG traversal algorithm will do it. +// Because such algorithms visit a block only after traversing some path to it +// from the root, they necessarily visit the block's idom first. +// +// But not every graph-traversal algorithm outputs blocks in an order that +// appears logical to human readers. The problem is that unrelated branches may +// be interspersed with each other, and merge blocks may come before some of the +// branches being merged. +// +// A good, human-readable order of blocks may be achieved by performing +// depth-first search but delaying merge nodes until after all their branches +// have been visited. This is implemented below by the inReadableOrder() +// function. + +#include "spvIR.h" + +#include <cassert> +#include <unordered_set> + +using spv::Block; +using spv::Id; + +namespace { +// Traverses CFG in a readable order, invoking a pre-set callback on each block. +// Use by calling visit() on the root block. +class ReadableOrderTraverser { +public: + ReadableOrderTraverser(std::function<void(Block*, spv::ReachReason, Block*)> callback) + : callback_(callback) {} + // Visits the block if it hasn't been visited already and isn't currently + // being delayed. Invokes callback(block, why, header), then descends into its + // successors. Delays merge-block and continue-block processing until all + // the branches have been completed. If |block| is an unreachable merge block or + // an unreachable continue target, then |header| is the corresponding header block. + void visit(Block* block, spv::ReachReason why, Block* header) + { + assert(block); + if (why == spv::ReachViaControlFlow) { + reachableViaControlFlow_.insert(block); + } + if (visited_.count(block) || delayed_.count(block)) + return; + callback_(block, why, header); + visited_.insert(block); + Block* mergeBlock = nullptr; + Block* continueBlock = nullptr; + auto mergeInst = block->getMergeInstruction(); + if (mergeInst) { + Id mergeId = mergeInst->getIdOperand(0); + mergeBlock = block->getParent().getParent().getInstruction(mergeId)->getBlock(); + delayed_.insert(mergeBlock); + if (mergeInst->getOpCode() == spv::OpLoopMerge) { + Id continueId = mergeInst->getIdOperand(1); + continueBlock = + block->getParent().getParent().getInstruction(continueId)->getBlock(); + delayed_.insert(continueBlock); + } + } + if (why == spv::ReachViaControlFlow) { + const auto& successors = block->getSuccessors(); + for (auto it = successors.cbegin(); it != successors.cend(); ++it) + visit(*it, why, nullptr); + } + if (continueBlock) { + const spv::ReachReason continueWhy = + (reachableViaControlFlow_.count(continueBlock) > 0) + ? spv::ReachViaControlFlow + : spv::ReachDeadContinue; + delayed_.erase(continueBlock); + visit(continueBlock, continueWhy, block); + } + if (mergeBlock) { + const spv::ReachReason mergeWhy = + (reachableViaControlFlow_.count(mergeBlock) > 0) + ? spv::ReachViaControlFlow + : spv::ReachDeadMerge; + delayed_.erase(mergeBlock); + visit(mergeBlock, mergeWhy, block); + } + } + +private: + std::function<void(Block*, spv::ReachReason, Block*)> callback_; + // Whether a block has already been visited or is being delayed. + std::unordered_set<Block *> visited_, delayed_; + + // The set of blocks that actually are reached via control flow. + std::unordered_set<Block *> reachableViaControlFlow_; +}; +} + +void spv::inReadableOrder(Block* root, std::function<void(Block*, spv::ReachReason, Block*)> callback) +{ + ReadableOrderTraverser(callback).visit(root, spv::ReachViaControlFlow, nullptr); +} |