| 1 |
// |
| 2 |
// Copyright (C) 2016 Google, Inc. |
| 3 |
// |
| 4 |
// All rights reserved. |
| 5 |
// |
| 6 |
// Redistribution and use in source and binary forms, with or without |
| 7 |
// modification, are permitted provided that the following conditions |
| 8 |
// are met: |
| 9 |
// |
| 10 |
// Redistributions of source code must retain the above copyright |
| 11 |
// notice, this list of conditions and the following disclaimer. |
| 12 |
// |
| 13 |
// Redistributions in binary form must reproduce the above |
| 14 |
// copyright notice, this list of conditions and the following |
| 15 |
// disclaimer in the documentation and/or other materials provided |
| 16 |
// with the distribution. |
| 17 |
// |
| 18 |
// Neither the name of 3Dlabs Inc. Ltd. nor the names of its |
| 19 |
// contributors may be used to endorse or promote products derived |
| 20 |
// from this software without specific prior written permission. |
| 21 |
// |
| 22 |
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 23 |
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 24 |
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
| 25 |
// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
| 26 |
// COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
| 27 |
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
| 28 |
// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| 29 |
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER |
| 30 |
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 31 |
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN |
| 32 |
// ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 33 |
// POSSIBILITY OF SUCH DAMAGE. |
| 34 |
|
| 35 |
// The SPIR-V spec requires code blocks to appear in an order satisfying the |
| 36 |
// dominator-tree direction (ie, dominator before the dominated). This is, |
| 37 |
// actually, easy to achieve: any pre-order CFG traversal algorithm will do it. |
| 38 |
// Because such algorithms visit a block only after traversing some path to it |
| 39 |
// from the root, they necessarily visit the block's idom first. |
| 40 |
// |
| 41 |
// But not every graph-traversal algorithm outputs blocks in an order that |
| 42 |
// appears logical to human readers. The problem is that unrelated branches may |
| 43 |
// be interspersed with each other, and merge blocks may come before some of the |
| 44 |
// branches being merged. |
| 45 |
// |
| 46 |
// A good, human-readable order of blocks may be achieved by performing |
| 47 |
// depth-first search but delaying merge nodes until after all their branches |
| 48 |
// have been visited. This is implemented below by the inReadableOrder() |
| 49 |
// function. |
| 50 |
|
| 51 |
#include "spvIR.h" |
| 52 |
|
| 53 |
#include <cassert> |
| 54 |
#include <unordered_set> |
| 55 |
|
| 56 |
using spv::Block; |
| 57 |
using spv::Id; |
| 58 |
|
| 59 |
namespace { |
| 60 |
// Traverses CFG in a readable order, invoking a pre-set callback on each block. |
| 61 |
// Use by calling visit() on the root block. |
| 62 |
class ReadableOrderTraverser { |
| 63 |
public: |
| 64 |
ReadableOrderTraverser(std::function<void(Block*, spv::ReachReason, Block*)> callback) |
| 65 |
: callback_(callback) {} |
| 66 |
// Visits the block if it hasn't been visited already and isn't currently |
| 67 |
// being delayed. Invokes callback(block, why, header), then descends into its |
| 68 |
// successors. Delays merge-block and continue-block processing until all |
| 69 |
// the branches have been completed. If |block| is an unreachable merge block or |
| 70 |
// an unreachable continue target, then |header| is the corresponding header block. |
| 71 |
void visit(Block* block, spv::ReachReason why, Block* header) |
| 72 |
{ |
| 73 |
assert(block); |
| 74 |
if (why == spv::ReachViaControlFlow) { |
| 75 |
reachableViaControlFlow_.insert(block); |
| 76 |
} |
| 77 |
if (visited_.count(block) || delayed_.count(block)) |
| 78 |
return; |
| 79 |
callback_(block, why, header); |
| 80 |
visited_.insert(block); |
| 81 |
Block* mergeBlock = nullptr; |
| 82 |
Block* continueBlock = nullptr; |
| 83 |
auto mergeInst = block->getMergeInstruction(); |
| 84 |
if (mergeInst) { |
| 85 |
Id mergeId = mergeInst->getIdOperand(0); |
| 86 |
mergeBlock = block->getParent().getParent().getInstruction(mergeId)->getBlock(); |
| 87 |
delayed_.insert(mergeBlock); |
| 88 |
if (mergeInst->getOpCode() == spv::OpLoopMerge) { |
| 89 |
Id continueId = mergeInst->getIdOperand(1); |
| 90 |
continueBlock = |
| 91 |
block->getParent().getParent().getInstruction(continueId)->getBlock(); |
| 92 |
delayed_.insert(continueBlock); |
| 93 |
} |
| 94 |
} |
| 95 |
if (why == spv::ReachViaControlFlow) { |
| 96 |
const auto& successors = block->getSuccessors(); |
| 97 |
for (auto it = successors.cbegin(); it != successors.cend(); ++it) |
| 98 |
visit(*it, why, nullptr); |
| 99 |
} |
| 100 |
if (continueBlock) { |
| 101 |
const spv::ReachReason continueWhy = |
| 102 |
(reachableViaControlFlow_.count(continueBlock) > 0) |
| 103 |
? spv::ReachViaControlFlow |
| 104 |
: spv::ReachDeadContinue; |
| 105 |
delayed_.erase(continueBlock); |
| 106 |
visit(continueBlock, continueWhy, block); |
| 107 |
} |
| 108 |
if (mergeBlock) { |
| 109 |
const spv::ReachReason mergeWhy = |
| 110 |
(reachableViaControlFlow_.count(mergeBlock) > 0) |
| 111 |
? spv::ReachViaControlFlow |
| 112 |
: spv::ReachDeadMerge; |
| 113 |
delayed_.erase(mergeBlock); |
| 114 |
visit(mergeBlock, mergeWhy, block); |
| 115 |
} |
| 116 |
} |
| 117 |
|
| 118 |
private: |
| 119 |
std::function<void(Block*, spv::ReachReason, Block*)> callback_; |
| 120 |
// Whether a block has already been visited or is being delayed. |
| 121 |
std::unordered_set<Block *> visited_, delayed_; |
| 122 |
|
| 123 |
// The set of blocks that actually are reached via control flow. |
| 124 |
std::unordered_set<Block *> reachableViaControlFlow_; |
| 125 |
}; |
| 126 |
} |
| 127 |
|
| 128 |
void spv::inReadableOrder(Block* root, std::function<void(Block*, spv::ReachReason, Block*)> callback) |
| 129 |
{ |
| 130 |
ReadableOrderTraverser(callback).visit(root, spv::ReachViaControlFlow, nullptr); |
| 131 |
} |