Dejan Mircevski | 57bbde4 | 2016-01-19 11:44:53 -0500 | [diff] [blame] | 1 | // |
John Kessenich | 927608b | 2017-01-06 12:34:14 -0700 | [diff] [blame] | 2 | // Copyright (C) 2016 Google, Inc. |
Dejan Mircevski | 57bbde4 | 2016-01-19 11:44:53 -0500 | [diff] [blame] | 3 | // |
John Kessenich | 927608b | 2017-01-06 12:34:14 -0700 | [diff] [blame] | 4 | // All rights reserved. |
Dejan Mircevski | 57bbde4 | 2016-01-19 11:44:53 -0500 | [diff] [blame] | 5 | // |
John Kessenich | 927608b | 2017-01-06 12:34:14 -0700 | [diff] [blame] | 6 | // Redistribution and use in source and binary forms, with or without |
| 7 | // modification, are permitted provided that the following conditions |
| 8 | // are met: |
Dejan Mircevski | 57bbde4 | 2016-01-19 11:44:53 -0500 | [diff] [blame] | 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 | // |
John Kessenich | 927608b | 2017-01-06 12:34:14 -0700 | [diff] [blame] | 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. |
Dejan Mircevski | 57bbde4 | 2016-01-19 11:44:53 -0500 | [diff] [blame] | 34 | |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 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 | |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 53 | #include <cassert> |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 54 | #include <unordered_set> |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 55 | |
| 56 | using spv::Block; |
| 57 | using spv::Id; |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 58 | |
| 59 | namespace { |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 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 { |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 63 | public: |
| 64 | explicit ReadableOrderTraverser(std::function<void(Block*)> callback) : callback_(callback) {} |
| 65 | // Visits the block if it hasn't been visited already and isn't currently |
Dejan Mircevski | f3c63cc | 2016-01-19 16:56:45 -0500 | [diff] [blame] | 66 | // being delayed. Invokes callback(block), then descends into its |
| 67 | // successors. Delays merge-block and continue-block processing until all |
| 68 | // the branches have been completed. |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 69 | void visit(Block* block) |
| 70 | { |
| 71 | assert(block); |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 72 | if (visited_.count(block) || delayed_.count(block)) |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 73 | return; |
| 74 | callback_(block); |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 75 | visited_.insert(block); |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 76 | Block* mergeBlock = nullptr; |
Dejan Mircevski | f3c63cc | 2016-01-19 16:56:45 -0500 | [diff] [blame] | 77 | Block* continueBlock = nullptr; |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 78 | auto mergeInst = block->getMergeInstruction(); |
| 79 | if (mergeInst) { |
| 80 | Id mergeId = mergeInst->getIdOperand(0); |
| 81 | mergeBlock = block->getParent().getParent().getInstruction(mergeId)->getBlock(); |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 82 | delayed_.insert(mergeBlock); |
Dejan Mircevski | f3c63cc | 2016-01-19 16:56:45 -0500 | [diff] [blame] | 83 | if (mergeInst->getOpCode() == spv::OpLoopMerge) { |
| 84 | Id continueId = mergeInst->getIdOperand(1); |
| 85 | continueBlock = |
| 86 | block->getParent().getParent().getInstruction(continueId)->getBlock(); |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 87 | delayed_.insert(continueBlock); |
Dejan Mircevski | f3c63cc | 2016-01-19 16:56:45 -0500 | [diff] [blame] | 88 | } |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 89 | } |
rdb | 32084e8 | 2016-02-23 22:17:38 +0100 | [diff] [blame] | 90 | const auto successors = block->getSuccessors(); |
| 91 | for (auto it = successors.cbegin(); it != successors.cend(); ++it) |
| 92 | visit(*it); |
Dejan Mircevski | f3c63cc | 2016-01-19 16:56:45 -0500 | [diff] [blame] | 93 | if (continueBlock) { |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 94 | delayed_.erase(continueBlock); |
Dejan Mircevski | f3c63cc | 2016-01-19 16:56:45 -0500 | [diff] [blame] | 95 | visit(continueBlock); |
| 96 | } |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 97 | if (mergeBlock) { |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 98 | delayed_.erase(mergeBlock); |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 99 | visit(mergeBlock); |
| 100 | } |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 101 | } |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 102 | |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 103 | private: |
| 104 | std::function<void(Block*)> callback_; |
| 105 | // Whether a block has already been visited or is being delayed. |
Lei Zhang | 2840f63 | 2017-05-11 20:46:01 -0400 | [diff] [blame] | 106 | std::unordered_set<Block *> visited_, delayed_; |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 107 | }; |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 108 | } |
| 109 | |
Dejan Mircevski | 159b59f | 2016-01-19 14:52:31 -0500 | [diff] [blame] | 110 | void spv::inReadableOrder(Block* root, std::function<void(Block*)> callback) |
| 111 | { |
| 112 | ReadableOrderTraverser(callback).visit(root); |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 113 | } |