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
56using spv::Block;
57using spv::Id;
58
59namespace {
60// Traverses CFG in a readable order, invoking a pre-set callback on each block.
61// Use by calling visit() on the root block.
62class ReadableOrderTraverser {
63public:
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
118private:
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
128void spv::inReadableOrder(Block* root, std::function<void(Block*, spv::ReachReason, Block*)> callback)
129{
130 ReadableOrderTraverser(callback).visit(root, spv::ReachViaControlFlow, nullptr);
131}
132