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/construct.h"
16
17 #include <cassert>
18 #include <cstddef>
19 #include <unordered_set>
20
21 #include "source/val/function.h"
22
23 namespace spvtools {
24 namespace val {
25
Construct(ConstructType construct_type,BasicBlock * entry,BasicBlock * exit,std::vector<Construct * > constructs)26 Construct::Construct(ConstructType construct_type, BasicBlock* entry,
27 BasicBlock* exit, std::vector<Construct*> constructs)
28 : type_(construct_type),
29 corresponding_constructs_(constructs),
30 entry_block_(entry),
31 exit_block_(exit) {}
32
type() const33 ConstructType Construct::type() const { return type_; }
34
corresponding_constructs() const35 const std::vector<Construct*>& Construct::corresponding_constructs() const {
36 return corresponding_constructs_;
37 }
corresponding_constructs()38 std::vector<Construct*>& Construct::corresponding_constructs() {
39 return corresponding_constructs_;
40 }
41
ValidateConstructSize(ConstructType type,size_t size)42 bool ValidateConstructSize(ConstructType type, size_t size) {
43 switch (type) {
44 case ConstructType::kSelection:
45 return size == 0;
46 case ConstructType::kContinue:
47 return size == 1;
48 case ConstructType::kLoop:
49 return size == 1;
50 case ConstructType::kCase:
51 return size >= 1;
52 default:
53 assert(1 == 0 && "Type not defined");
54 }
55 return false;
56 }
57
set_corresponding_constructs(std::vector<Construct * > constructs)58 void Construct::set_corresponding_constructs(
59 std::vector<Construct*> constructs) {
60 assert(ValidateConstructSize(type_, constructs.size()));
61 corresponding_constructs_ = constructs;
62 }
63
entry_block() const64 const BasicBlock* Construct::entry_block() const { return entry_block_; }
entry_block()65 BasicBlock* Construct::entry_block() { return entry_block_; }
66
exit_block() const67 const BasicBlock* Construct::exit_block() const { return exit_block_; }
exit_block()68 BasicBlock* Construct::exit_block() { return exit_block_; }
69
set_exit(BasicBlock * block)70 void Construct::set_exit(BasicBlock* block) { exit_block_ = block; }
71
blocks(Function * function) const72 Construct::ConstructBlockSet Construct::blocks(Function* function) const {
73 auto header = entry_block();
74 auto merge = exit_block();
75 assert(header);
76 assert(merge);
77 int header_depth = function->GetBlockDepth(const_cast<BasicBlock*>(header));
78 ConstructBlockSet construct_blocks;
79 std::unordered_set<BasicBlock*> corresponding_headers;
80 for (auto& other : corresponding_constructs()) {
81 corresponding_headers.insert(other->entry_block());
82 }
83 std::vector<BasicBlock*> stack;
84 stack.push_back(const_cast<BasicBlock*>(header));
85 while (!stack.empty()) {
86 BasicBlock* block = stack.back();
87 stack.pop_back();
88
89 if (merge == block && ExitBlockIsMergeBlock()) {
90 // Merge block is not part of the construct.
91 continue;
92 }
93
94 if (corresponding_headers.count(block)) {
95 // Entered a corresponding construct.
96 continue;
97 }
98
99 int block_depth = function->GetBlockDepth(block);
100 if (block_depth < header_depth) {
101 // Broke to outer construct.
102 continue;
103 }
104
105 // In a loop, the continue target is at a depth of the loop construct + 1.
106 // A selection construct nested directly within the loop construct is also
107 // at the same depth. It is valid, however, to branch directly to the
108 // continue target from within the selection construct.
109 if (block_depth == header_depth && type() == ConstructType::kSelection &&
110 block->is_type(kBlockTypeContinue)) {
111 // Continued to outer construct.
112 continue;
113 }
114
115 if (!construct_blocks.insert(block).second) continue;
116
117 if (merge != block) {
118 for (auto succ : *block->successors()) {
119 // All blocks in the construct must be dominated by the header.
120 if (header->dominates(*succ)) {
121 stack.push_back(succ);
122 }
123 }
124 }
125 }
126
127 return construct_blocks;
128 }
129
130 } // namespace val
131 } // namespace spvtools
132