Dejan Mircevski | 57bbde4 | 2016-01-19 11:44:53 -0500 | [diff] [blame^] | 1 | // |
| 2 | //Copyright (C) 2016 LunarG, 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 | // |
| 36 | // Author: Dejan Mircevski, Google |
| 37 | // |
| 38 | |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 39 | // The SPIR-V spec requires code blocks to appear in an order satisfying the |
| 40 | // dominator-tree direction (ie, dominator before the dominated). This is, |
| 41 | // actually, easy to achieve: any pre-order CFG traversal algorithm will do it. |
| 42 | // Because such algorithms visit a block only after traversing some path to it |
| 43 | // from the root, they necessarily visit the block's idom first. |
| 44 | // |
| 45 | // But not every graph-traversal algorithm outputs blocks in an order that |
| 46 | // appears logical to human readers. The problem is that unrelated branches may |
| 47 | // be interspersed with each other, and merge blocks may come before some of the |
| 48 | // branches being merged. |
| 49 | // |
| 50 | // A good, human-readable order of blocks may be achieved by performing |
| 51 | // depth-first search but delaying merge nodes until after all their branches |
| 52 | // have been visited. This is implemented below by the inReadableOrder() |
| 53 | // function. |
| 54 | |
| 55 | #include "spvIR.h" |
| 56 | |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 57 | #include <cassert> |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 58 | #include <unordered_map> |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 59 | |
| 60 | using spv::Block; |
| 61 | using spv::Id; |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 62 | |
| 63 | namespace { |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 64 | // Traverses CFG in a readable order, invoking a pre-set callback on each block. |
| 65 | // Use by calling visit() on the root block. |
| 66 | class ReadableOrderTraverser { |
| 67 | public: |
| 68 | explicit ReadableOrderTraverser(std::function<void(Block*)> callback) |
| 69 | : callback_(callback) {} |
| 70 | |
| 71 | // Visits the block if it hasn't been visited already and isn't currently |
| 72 | // being delayed. Invokes callback(block), then descends into its successors. |
| 73 | // Delays merge-block processing until all the branches have been completed. |
| 74 | void visit(Block* block) { |
| 75 | assert(block); |
| 76 | if (visited_[block] || delayed_[block]) return; |
| 77 | callback_(block); |
| 78 | visited_[block] = true; |
| 79 | Block* mergeBlock = nullptr; |
| 80 | auto mergeInst = block->getMergeInstruction(); |
| 81 | if (mergeInst) { |
| 82 | Id mergeId = mergeInst->getIdOperand(0); |
| 83 | mergeBlock = |
| 84 | block->getParent().getParent().getInstruction(mergeId)->getBlock(); |
| 85 | delayed_[mergeBlock] = true; |
| 86 | } |
| 87 | for (const auto succ : block->getSuccessors()) |
| 88 | if (succ != mergeBlock) visit(succ); |
| 89 | if (mergeBlock) { |
| 90 | delayed_[mergeBlock] = false; |
| 91 | visit(mergeBlock); |
| 92 | } |
| 93 | } |
| 94 | |
| 95 | private: |
| 96 | std::function<void(Block*)> callback_; |
| 97 | // Whether a block has already been visited or is being delayed. |
| 98 | std::unordered_map<Block*, bool> visited_, delayed_; |
| 99 | }; |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 100 | } |
| 101 | |
| 102 | void spv::inReadableOrder(Block* root, std::function<void(Block*)> callback) { |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 103 | ReadableOrderTraverser(callback).visit(root); |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 104 | } |