1 // Copyright (c) 2015-2016 The Khronos Group Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "source/val/basic_block.h"
16
17 #include <algorithm>
18 #include <utility>
19 #include <vector>
20
21 namespace spvtools {
22 namespace val {
23
BasicBlock(uint32_t label_id)24 BasicBlock::BasicBlock(uint32_t label_id)
25 : id_(label_id),
26 immediate_dominator_(nullptr),
27 immediate_post_dominator_(nullptr),
28 predecessors_(),
29 successors_(),
30 type_(0),
31 reachable_(false),
32 label_(nullptr),
33 terminator_(nullptr) {}
34
SetImmediateDominator(BasicBlock * dom_block)35 void BasicBlock::SetImmediateDominator(BasicBlock* dom_block) {
36 immediate_dominator_ = dom_block;
37 }
38
SetImmediatePostDominator(BasicBlock * pdom_block)39 void BasicBlock::SetImmediatePostDominator(BasicBlock* pdom_block) {
40 immediate_post_dominator_ = pdom_block;
41 }
42
immediate_dominator() const43 const BasicBlock* BasicBlock::immediate_dominator() const {
44 return immediate_dominator_;
45 }
46
immediate_post_dominator() const47 const BasicBlock* BasicBlock::immediate_post_dominator() const {
48 return immediate_post_dominator_;
49 }
50
immediate_dominator()51 BasicBlock* BasicBlock::immediate_dominator() { return immediate_dominator_; }
immediate_post_dominator()52 BasicBlock* BasicBlock::immediate_post_dominator() {
53 return immediate_post_dominator_;
54 }
55
RegisterSuccessors(const std::vector<BasicBlock * > & next_blocks)56 void BasicBlock::RegisterSuccessors(
57 const std::vector<BasicBlock*>& next_blocks) {
58 for (auto& block : next_blocks) {
59 block->predecessors_.push_back(this);
60 successors_.push_back(block);
61 if (block->reachable_ == false) block->set_reachable(reachable_);
62 }
63 }
64
RegisterBranchInstruction(SpvOp branch_instruction)65 void BasicBlock::RegisterBranchInstruction(SpvOp branch_instruction) {
66 if (branch_instruction == SpvOpUnreachable) reachable_ = false;
67 return;
68 }
69
dominates(const BasicBlock & other) const70 bool BasicBlock::dominates(const BasicBlock& other) const {
71 return (this == &other) ||
72 !(other.dom_end() ==
73 std::find(other.dom_begin(), other.dom_end(), this));
74 }
75
postdominates(const BasicBlock & other) const76 bool BasicBlock::postdominates(const BasicBlock& other) const {
77 return (this == &other) ||
78 !(other.pdom_end() ==
79 std::find(other.pdom_begin(), other.pdom_end(), this));
80 }
81
DominatorIterator()82 BasicBlock::DominatorIterator::DominatorIterator() : current_(nullptr) {}
83
DominatorIterator(const BasicBlock * block,std::function<const BasicBlock * (const BasicBlock *)> dominator_func)84 BasicBlock::DominatorIterator::DominatorIterator(
85 const BasicBlock* block,
86 std::function<const BasicBlock*(const BasicBlock*)> dominator_func)
87 : current_(block), dom_func_(dominator_func) {}
88
operator ++()89 BasicBlock::DominatorIterator& BasicBlock::DominatorIterator::operator++() {
90 if (current_ == dom_func_(current_)) {
91 current_ = nullptr;
92 } else {
93 current_ = dom_func_(current_);
94 }
95 return *this;
96 }
97
dom_begin() const98 const BasicBlock::DominatorIterator BasicBlock::dom_begin() const {
99 return DominatorIterator(
100 this, [](const BasicBlock* b) { return b->immediate_dominator(); });
101 }
102
dom_begin()103 BasicBlock::DominatorIterator BasicBlock::dom_begin() {
104 return DominatorIterator(
105 this, [](const BasicBlock* b) { return b->immediate_dominator(); });
106 }
107
dom_end() const108 const BasicBlock::DominatorIterator BasicBlock::dom_end() const {
109 return DominatorIterator();
110 }
111
dom_end()112 BasicBlock::DominatorIterator BasicBlock::dom_end() {
113 return DominatorIterator();
114 }
115
pdom_begin() const116 const BasicBlock::DominatorIterator BasicBlock::pdom_begin() const {
117 return DominatorIterator(
118 this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
119 }
120
pdom_begin()121 BasicBlock::DominatorIterator BasicBlock::pdom_begin() {
122 return DominatorIterator(
123 this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
124 }
125
pdom_end() const126 const BasicBlock::DominatorIterator BasicBlock::pdom_end() const {
127 return DominatorIterator();
128 }
129
pdom_end()130 BasicBlock::DominatorIterator BasicBlock::pdom_end() {
131 return DominatorIterator();
132 }
133
operator ==(const BasicBlock::DominatorIterator & lhs,const BasicBlock::DominatorIterator & rhs)134 bool operator==(const BasicBlock::DominatorIterator& lhs,
135 const BasicBlock::DominatorIterator& rhs) {
136 return lhs.current_ == rhs.current_;
137 }
138
operator !=(const BasicBlock::DominatorIterator & lhs,const BasicBlock::DominatorIterator & rhs)139 bool operator!=(const BasicBlock::DominatorIterator& lhs,
140 const BasicBlock::DominatorIterator& rhs) {
141 return !(lhs == rhs);
142 }
143
operator *()144 const BasicBlock*& BasicBlock::DominatorIterator::operator*() {
145 return current_;
146 }
147
148 } // namespace val
149 } // namespace spvtools
150