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
21namespace spvtools {
22namespace val {
23
24BasicBlock::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
35void BasicBlock::SetImmediateDominator(BasicBlock* dom_block) {
36 immediate_dominator_ = dom_block;
37}
38
39void BasicBlock::SetImmediatePostDominator(BasicBlock* pdom_block) {
40 immediate_post_dominator_ = pdom_block;
41}
42
43const BasicBlock* BasicBlock::immediate_dominator() const {
44 return immediate_dominator_;
45}
46
47const BasicBlock* BasicBlock::immediate_post_dominator() const {
48 return immediate_post_dominator_;
49}
50
51BasicBlock* BasicBlock::immediate_dominator() { return immediate_dominator_; }
52BasicBlock* BasicBlock::immediate_post_dominator() {
53 return immediate_post_dominator_;
54}
55
56void 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
65void BasicBlock::RegisterBranchInstruction(SpvOp branch_instruction) {
66 if (branch_instruction == SpvOpUnreachable) reachable_ = false;
67 return;
68}
69
70bool 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
76bool 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
82BasicBlock::DominatorIterator::DominatorIterator() : current_(nullptr) {}
83
84BasicBlock::DominatorIterator::DominatorIterator(
85 const BasicBlock* block,
86 std::function<const BasicBlock*(const BasicBlock*)> dominator_func)
87 : current_(block), dom_func_(dominator_func) {}
88
89BasicBlock::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
98const BasicBlock::DominatorIterator BasicBlock::dom_begin() const {
99 return DominatorIterator(
100 this, [](const BasicBlock* b) { return b->immediate_dominator(); });
101}
102
103BasicBlock::DominatorIterator BasicBlock::dom_begin() {
104 return DominatorIterator(
105 this, [](const BasicBlock* b) { return b->immediate_dominator(); });
106}
107
108const BasicBlock::DominatorIterator BasicBlock::dom_end() const {
109 return DominatorIterator();
110}
111
112BasicBlock::DominatorIterator BasicBlock::dom_end() {
113 return DominatorIterator();
114}
115
116const BasicBlock::DominatorIterator BasicBlock::pdom_begin() const {
117 return DominatorIterator(
118 this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
119}
120
121BasicBlock::DominatorIterator BasicBlock::pdom_begin() {
122 return DominatorIterator(
123 this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
124}
125
126const BasicBlock::DominatorIterator BasicBlock::pdom_end() const {
127 return DominatorIterator();
128}
129
130BasicBlock::DominatorIterator BasicBlock::pdom_end() {
131 return DominatorIterator();
132}
133
134bool operator==(const BasicBlock::DominatorIterator& lhs,
135 const BasicBlock::DominatorIterator& rhs) {
136 return lhs.current_ == rhs.current_;
137}
138
139bool operator!=(const BasicBlock::DominatorIterator& lhs,
140 const BasicBlock::DominatorIterator& rhs) {
141 return !(lhs == rhs);
142}
143
144const BasicBlock*& BasicBlock::DominatorIterator::operator*() {
145 return current_;
146}
147
148} // namespace val
149} // namespace spvtools
150