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 explicit ReadableOrderTraverser(std::function<void(Block*)> callback) : callback_(callback) {} 65 // Visits the block if it hasn't been visited already and isn't currently 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. 69 void visit(Block* block) 70 { 71 assert(block); 72 if (visited_.count(block) || delayed_.count(block)) 73 return; 74 callback_(block); 75 visited_.insert(block); 76 Block* mergeBlock = nullptr; 77 Block* continueBlock = nullptr; 78 auto mergeInst = block->getMergeInstruction(); 79 if (mergeInst) { 80 Id mergeId = mergeInst->getIdOperand(0); 81 mergeBlock = block->getParent().getParent().getInstruction(mergeId)->getBlock(); 82 delayed_.insert(mergeBlock); 83 if (mergeInst->getOpCode() == spv::OpLoopMerge) { 84 Id continueId = mergeInst->getIdOperand(1); 85 continueBlock = 86 block->getParent().getParent().getInstruction(continueId)->getBlock(); 87 delayed_.insert(continueBlock); 88 } 89 } 90 const auto successors = block->getSuccessors(); 91 for (auto it = successors.cbegin(); it != successors.cend(); ++it) 92 visit(*it); 93 if (continueBlock) { 94 delayed_.erase(continueBlock); 95 visit(continueBlock); 96 } 97 if (mergeBlock) { 98 delayed_.erase(mergeBlock); 99 visit(mergeBlock); 100 } 101 } 102 103 private: 104 std::function<void(Block*)> callback_; 105 // Whether a block has already been visited or is being delayed. 106 std::unordered_set<Block *> visited_, delayed_; 107 }; 108 } 109 110 void spv::inReadableOrder(Block* root, std::function<void(Block*)> callback) 111 { 112 ReadableOrderTraverser(callback).visit(root); 113 } 114
