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 }
62 }
63
dominates(const BasicBlock & other) const64 bool BasicBlock::dominates(const BasicBlock& other) const {
65 return (this == &other) ||
66 !(other.dom_end() ==
67 std::find(other.dom_begin(), other.dom_end(), this));
68 }
69
postdominates(const BasicBlock & other) const70 bool BasicBlock::postdominates(const BasicBlock& other) const {
71 return (this == &other) ||
72 !(other.pdom_end() ==
73 std::find(other.pdom_begin(), other.pdom_end(), this));
74 }
75
DominatorIterator()76 BasicBlock::DominatorIterator::DominatorIterator() : current_(nullptr) {}
77
DominatorIterator(const BasicBlock * block,std::function<const BasicBlock * (const BasicBlock *)> dominator_func)78 BasicBlock::DominatorIterator::DominatorIterator(
79 const BasicBlock* block,
80 std::function<const BasicBlock*(const BasicBlock*)> dominator_func)
81 : current_(block), dom_func_(dominator_func) {}
82
operator ++()83 BasicBlock::DominatorIterator& BasicBlock::DominatorIterator::operator++() {
84 if (current_ == dom_func_(current_)) {
85 current_ = nullptr;
86 } else {
87 current_ = dom_func_(current_);
88 }
89 return *this;
90 }
91
dom_begin() const92 const BasicBlock::DominatorIterator BasicBlock::dom_begin() const {
93 return DominatorIterator(
94 this, [](const BasicBlock* b) { return b->immediate_dominator(); });
95 }
96
dom_begin()97 BasicBlock::DominatorIterator BasicBlock::dom_begin() {
98 return DominatorIterator(
99 this, [](const BasicBlock* b) { return b->immediate_dominator(); });
100 }
101
dom_end() const102 const BasicBlock::DominatorIterator BasicBlock::dom_end() const {
103 return DominatorIterator();
104 }
105
dom_end()106 BasicBlock::DominatorIterator BasicBlock::dom_end() {
107 return DominatorIterator();
108 }
109
pdom_begin() const110 const BasicBlock::DominatorIterator BasicBlock::pdom_begin() const {
111 return DominatorIterator(
112 this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
113 }
114
pdom_begin()115 BasicBlock::DominatorIterator BasicBlock::pdom_begin() {
116 return DominatorIterator(
117 this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
118 }
119
pdom_end() const120 const BasicBlock::DominatorIterator BasicBlock::pdom_end() const {
121 return DominatorIterator();
122 }
123
pdom_end()124 BasicBlock::DominatorIterator BasicBlock::pdom_end() {
125 return DominatorIterator();
126 }
127
operator ==(const BasicBlock::DominatorIterator & lhs,const BasicBlock::DominatorIterator & rhs)128 bool operator==(const BasicBlock::DominatorIterator& lhs,
129 const BasicBlock::DominatorIterator& rhs) {
130 return lhs.current_ == rhs.current_;
131 }
132
operator !=(const BasicBlock::DominatorIterator & lhs,const BasicBlock::DominatorIterator & rhs)133 bool operator!=(const BasicBlock::DominatorIterator& lhs,
134 const BasicBlock::DominatorIterator& rhs) {
135 return !(lhs == rhs);
136 }
137
operator *()138 const BasicBlock*& BasicBlock::DominatorIterator::operator*() {
139 return current_;
140 }
141
142 } // namespace val
143 } // namespace spvtools
144