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:
ReadableOrderTraverser(std::function<void (Block *)> callback)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.
visit(Block * block)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
inReadableOrder(Block * root,std::function<void (Block *)> callback)110 void spv::inReadableOrder(Block* root, std::function<void(Block*)> callback)
111 {
112 ReadableOrderTraverser(callback).visit(root);
113 }
114