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/function.h"
16
17 #include <cassert>
18
19 #include <algorithm>
20 #include <sstream>
21 #include <unordered_map>
22 #include <unordered_set>
23 #include <utility>
24
25 #include "source/cfa.h"
26 #include "source/val/basic_block.h"
27 #include "source/val/construct.h"
28 #include "source/val/validate.h"
29
30 namespace spvtools {
31 namespace val {
32
33 // Universal Limit of ResultID + 1
34 static const uint32_t kInvalidId = 0x400000;
35
Function(uint32_t function_id,uint32_t result_type_id,SpvFunctionControlMask function_control,uint32_t function_type_id)36 Function::Function(uint32_t function_id, uint32_t result_type_id,
37 SpvFunctionControlMask function_control,
38 uint32_t function_type_id)
39 : id_(function_id),
40 function_type_id_(function_type_id),
41 result_type_id_(result_type_id),
42 function_control_(function_control),
43 declaration_type_(FunctionDecl::kFunctionDeclUnknown),
44 end_has_been_registered_(false),
45 blocks_(),
46 current_block_(nullptr),
47 pseudo_entry_block_(0),
48 pseudo_exit_block_(kInvalidId),
49 cfg_constructs_(),
50 variable_ids_(),
51 parameter_ids_() {}
52
IsFirstBlock(uint32_t block_id) const53 bool Function::IsFirstBlock(uint32_t block_id) const {
54 return !ordered_blocks_.empty() && *first_block() == block_id;
55 }
56
RegisterFunctionParameter(uint32_t parameter_id,uint32_t type_id)57 spv_result_t Function::RegisterFunctionParameter(uint32_t parameter_id,
58 uint32_t type_id) {
59 assert(current_block_ == nullptr &&
60 "RegisterFunctionParameter can only be called when parsing the binary "
61 "ouside of a block");
62 // TODO(umar): Validate function parameter type order and count
63 // TODO(umar): Use these variables to validate parameter type
64 (void)parameter_id;
65 (void)type_id;
66 return SPV_SUCCESS;
67 }
68
RegisterLoopMerge(uint32_t merge_id,uint32_t continue_id)69 spv_result_t Function::RegisterLoopMerge(uint32_t merge_id,
70 uint32_t continue_id) {
71 RegisterBlock(merge_id, false);
72 RegisterBlock(continue_id, false);
73 BasicBlock& merge_block = blocks_.at(merge_id);
74 BasicBlock& continue_target_block = blocks_.at(continue_id);
75 assert(current_block_ &&
76 "RegisterLoopMerge must be called when called within a block");
77
78 current_block_->set_type(kBlockTypeLoop);
79 merge_block.set_type(kBlockTypeMerge);
80 continue_target_block.set_type(kBlockTypeContinue);
81 Construct& loop_construct =
82 AddConstruct({ConstructType::kLoop, current_block_, &merge_block});
83 Construct& continue_construct =
84 AddConstruct({ConstructType::kContinue, &continue_target_block});
85
86 continue_construct.set_corresponding_constructs({&loop_construct});
87 loop_construct.set_corresponding_constructs({&continue_construct});
88 merge_block_header_[&merge_block] = current_block_;
89 if (continue_target_headers_.find(&continue_target_block) ==
90 continue_target_headers_.end()) {
91 continue_target_headers_[&continue_target_block] = {current_block_};
92 } else {
93 continue_target_headers_[&continue_target_block].push_back(current_block_);
94 }
95
96 return SPV_SUCCESS;
97 }
98
RegisterSelectionMerge(uint32_t merge_id)99 spv_result_t Function::RegisterSelectionMerge(uint32_t merge_id) {
100 RegisterBlock(merge_id, false);
101 BasicBlock& merge_block = blocks_.at(merge_id);
102 current_block_->set_type(kBlockTypeHeader);
103 merge_block.set_type(kBlockTypeMerge);
104 merge_block_header_[&merge_block] = current_block_;
105
106 AddConstruct({ConstructType::kSelection, current_block(), &merge_block});
107
108 return SPV_SUCCESS;
109 }
110
RegisterSetFunctionDeclType(FunctionDecl type)111 spv_result_t Function::RegisterSetFunctionDeclType(FunctionDecl type) {
112 assert(declaration_type_ == FunctionDecl::kFunctionDeclUnknown);
113 declaration_type_ = type;
114 return SPV_SUCCESS;
115 }
116
RegisterBlock(uint32_t block_id,bool is_definition)117 spv_result_t Function::RegisterBlock(uint32_t block_id, bool is_definition) {
118 assert(
119 declaration_type_ == FunctionDecl::kFunctionDeclDefinition &&
120 "RegisterBlocks can only be called after declaration_type_ is defined");
121
122 std::unordered_map<uint32_t, BasicBlock>::iterator inserted_block;
123 bool success = false;
124 tie(inserted_block, success) =
125 blocks_.insert({block_id, BasicBlock(block_id)});
126 if (is_definition) { // new block definition
127 assert(current_block_ == nullptr &&
128 "Register Block can only be called when parsing a binary outside of "
129 "a BasicBlock");
130
131 undefined_blocks_.erase(block_id);
132 current_block_ = &inserted_block->second;
133 ordered_blocks_.push_back(current_block_);
134 if (IsFirstBlock(block_id)) current_block_->set_reachable(true);
135 } else if (success) { // Block doesn't exsist but this is not a definition
136 undefined_blocks_.insert(block_id);
137 }
138
139 return SPV_SUCCESS;
140 }
141
RegisterBlockEnd(std::vector<uint32_t> next_list,SpvOp branch_instruction)142 void Function::RegisterBlockEnd(std::vector<uint32_t> next_list,
143 SpvOp branch_instruction) {
144 assert(
145 current_block_ &&
146 "RegisterBlockEnd can only be called when parsing a binary in a block");
147 std::vector<BasicBlock*> next_blocks;
148 next_blocks.reserve(next_list.size());
149
150 std::unordered_map<uint32_t, BasicBlock>::iterator inserted_block;
151 bool success;
152 for (uint32_t successor_id : next_list) {
153 tie(inserted_block, success) =
154 blocks_.insert({successor_id, BasicBlock(successor_id)});
155 if (success) {
156 undefined_blocks_.insert(successor_id);
157 }
158 next_blocks.push_back(&inserted_block->second);
159 }
160
161 if (current_block_->is_type(kBlockTypeLoop)) {
162 // For each loop header, record the set of its successors, and include
163 // its continue target if the continue target is not the loop header
164 // itself.
165 std::vector<BasicBlock*>& next_blocks_plus_continue_target =
166 loop_header_successors_plus_continue_target_map_[current_block_];
167 next_blocks_plus_continue_target = next_blocks;
168 auto continue_target =
169 FindConstructForEntryBlock(current_block_, ConstructType::kLoop)
170 .corresponding_constructs()
171 .back()
172 ->entry_block();
173 if (continue_target != current_block_) {
174 next_blocks_plus_continue_target.push_back(continue_target);
175 }
176 }
177
178 current_block_->RegisterBranchInstruction(branch_instruction);
179 current_block_->RegisterSuccessors(next_blocks);
180 current_block_ = nullptr;
181 return;
182 }
183
RegisterFunctionEnd()184 void Function::RegisterFunctionEnd() {
185 if (!end_has_been_registered_) {
186 end_has_been_registered_ = true;
187
188 ComputeAugmentedCFG();
189 }
190 }
191
block_count() const192 size_t Function::block_count() const { return blocks_.size(); }
193
undefined_block_count() const194 size_t Function::undefined_block_count() const {
195 return undefined_blocks_.size();
196 }
197
ordered_blocks() const198 const std::vector<BasicBlock*>& Function::ordered_blocks() const {
199 return ordered_blocks_;
200 }
ordered_blocks()201 std::vector<BasicBlock*>& Function::ordered_blocks() { return ordered_blocks_; }
202
current_block() const203 const BasicBlock* Function::current_block() const { return current_block_; }
current_block()204 BasicBlock* Function::current_block() { return current_block_; }
205
constructs() const206 const std::list<Construct>& Function::constructs() const {
207 return cfg_constructs_;
208 }
constructs()209 std::list<Construct>& Function::constructs() { return cfg_constructs_; }
210
first_block() const211 const BasicBlock* Function::first_block() const {
212 if (ordered_blocks_.empty()) return nullptr;
213 return ordered_blocks_[0];
214 }
first_block()215 BasicBlock* Function::first_block() {
216 if (ordered_blocks_.empty()) return nullptr;
217 return ordered_blocks_[0];
218 }
219
IsBlockType(uint32_t merge_block_id,BlockType type) const220 bool Function::IsBlockType(uint32_t merge_block_id, BlockType type) const {
221 bool ret = false;
222 const BasicBlock* block;
223 std::tie(block, std::ignore) = GetBlock(merge_block_id);
224 if (block) {
225 ret = block->is_type(type);
226 }
227 return ret;
228 }
229
GetBlock(uint32_t block_id) const230 std::pair<const BasicBlock*, bool> Function::GetBlock(uint32_t block_id) const {
231 const auto b = blocks_.find(block_id);
232 if (b != end(blocks_)) {
233 const BasicBlock* block = &(b->second);
234 bool defined =
235 undefined_blocks_.find(block->id()) == std::end(undefined_blocks_);
236 return std::make_pair(block, defined);
237 } else {
238 return std::make_pair(nullptr, false);
239 }
240 }
241
GetBlock(uint32_t block_id)242 std::pair<BasicBlock*, bool> Function::GetBlock(uint32_t block_id) {
243 const BasicBlock* out;
244 bool defined;
245 std::tie(out, defined) =
246 const_cast<const Function*>(this)->GetBlock(block_id);
247 return std::make_pair(const_cast<BasicBlock*>(out), defined);
248 }
249
AugmentedCFGSuccessorsFunction() const250 Function::GetBlocksFunction Function::AugmentedCFGSuccessorsFunction() const {
251 return [this](const BasicBlock* block) {
252 auto where = augmented_successors_map_.find(block);
253 return where == augmented_successors_map_.end() ? block->successors()
254 : &(*where).second;
255 };
256 }
257
258 Function::GetBlocksFunction
AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge() const259 Function::AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge() const {
260 return [this](const BasicBlock* block) {
261 auto where = loop_header_successors_plus_continue_target_map_.find(block);
262 return where == loop_header_successors_plus_continue_target_map_.end()
263 ? AugmentedCFGSuccessorsFunction()(block)
264 : &(*where).second;
265 };
266 }
267
AugmentedCFGPredecessorsFunction() const268 Function::GetBlocksFunction Function::AugmentedCFGPredecessorsFunction() const {
269 return [this](const BasicBlock* block) {
270 auto where = augmented_predecessors_map_.find(block);
271 return where == augmented_predecessors_map_.end() ? block->predecessors()
272 : &(*where).second;
273 };
274 }
275
ComputeAugmentedCFG()276 void Function::ComputeAugmentedCFG() {
277 // Compute the successors of the pseudo-entry block, and
278 // the predecessors of the pseudo exit block.
279 auto succ_func = [](const BasicBlock* b) { return b->successors(); };
280 auto pred_func = [](const BasicBlock* b) { return b->predecessors(); };
281 CFA<BasicBlock>::ComputeAugmentedCFG(
282 ordered_blocks_, &pseudo_entry_block_, &pseudo_exit_block_,
283 &augmented_successors_map_, &augmented_predecessors_map_, succ_func,
284 pred_func);
285 }
286
AddConstruct(const Construct & new_construct)287 Construct& Function::AddConstruct(const Construct& new_construct) {
288 cfg_constructs_.push_back(new_construct);
289 auto& result = cfg_constructs_.back();
290 entry_block_to_construct_[std::make_pair(new_construct.entry_block(),
291 new_construct.type())] = &result;
292 return result;
293 }
294
FindConstructForEntryBlock(const BasicBlock * entry_block,ConstructType type)295 Construct& Function::FindConstructForEntryBlock(const BasicBlock* entry_block,
296 ConstructType type) {
297 auto where =
298 entry_block_to_construct_.find(std::make_pair(entry_block, type));
299 assert(where != entry_block_to_construct_.end());
300 auto construct_ptr = (*where).second;
301 assert(construct_ptr);
302 return *construct_ptr;
303 }
304
GetBlockDepth(BasicBlock * bb)305 int Function::GetBlockDepth(BasicBlock* bb) {
306 // Guard against nullptr.
307 if (!bb) {
308 return 0;
309 }
310 // Only calculate the depth if it's not already calculated.
311 // This function uses memoization to avoid duplicate CFG depth calculations.
312 if (block_depth_.find(bb) != block_depth_.end()) {
313 return block_depth_[bb];
314 }
315
316 BasicBlock* bb_dom = bb->immediate_dominator();
317 if (!bb_dom || bb == bb_dom) {
318 // This block has no dominator, so it's at depth 0.
319 block_depth_[bb] = 0;
320 } else if (bb->is_type(kBlockTypeContinue)) {
321 // This rule must precede the rule for merge blocks in order to set up
322 // depths correctly. If a block is both a merge and continue then the merge
323 // is nested within the continue's loop (or the graph is incorrect).
324 // The depth of the continue block entry point is 1 + loop header depth.
325 Construct* continue_construct =
326 entry_block_to_construct_[std::make_pair(bb, ConstructType::kContinue)];
327 assert(continue_construct);
328 // Continue construct has only 1 corresponding construct (loop header).
329 Construct* loop_construct =
330 continue_construct->corresponding_constructs()[0];
331 assert(loop_construct);
332 BasicBlock* loop_header = loop_construct->entry_block();
333 // The continue target may be the loop itself (while 1).
334 // In such cases, the depth of the continue block is: 1 + depth of the
335 // loop's dominator block.
336 if (loop_header == bb) {
337 block_depth_[bb] = 1 + GetBlockDepth(bb_dom);
338 } else {
339 block_depth_[bb] = 1 + GetBlockDepth(loop_header);
340 }
341 } else if (bb->is_type(kBlockTypeMerge)) {
342 // If this is a merge block, its depth is equal to the block before
343 // branching.
344 BasicBlock* header = merge_block_header_[bb];
345 assert(header);
346 block_depth_[bb] = GetBlockDepth(header);
347 } else if (bb_dom->is_type(kBlockTypeHeader) ||
348 bb_dom->is_type(kBlockTypeLoop)) {
349 // The dominator of the given block is a header block. So, the nesting
350 // depth of this block is: 1 + nesting depth of the header.
351 block_depth_[bb] = 1 + GetBlockDepth(bb_dom);
352 } else {
353 block_depth_[bb] = GetBlockDepth(bb_dom);
354 }
355 return block_depth_[bb];
356 }
357
RegisterExecutionModelLimitation(SpvExecutionModel model,const std::string & message)358 void Function::RegisterExecutionModelLimitation(SpvExecutionModel model,
359 const std::string& message) {
360 execution_model_limitations_.push_back(
361 [model, message](SpvExecutionModel in_model, std::string* out_message) {
362 if (model != in_model) {
363 if (out_message) {
364 *out_message = message;
365 }
366 return false;
367 }
368 return true;
369 });
370 }
371
IsCompatibleWithExecutionModel(SpvExecutionModel model,std::string * reason) const372 bool Function::IsCompatibleWithExecutionModel(SpvExecutionModel model,
373 std::string* reason) const {
374 bool return_value = true;
375 std::stringstream ss_reason;
376
377 for (const auto& is_compatible : execution_model_limitations_) {
378 std::string message;
379 if (!is_compatible(model, &message)) {
380 if (!reason) return false;
381 return_value = false;
382 if (!message.empty()) {
383 ss_reason << message << "\n";
384 }
385 }
386 }
387
388 if (!return_value && reason) {
389 *reason = ss_reason.str();
390 }
391
392 return return_value;
393 }
394
CheckLimitations(const ValidationState_t & _,const Function * entry_point,std::string * reason) const395 bool Function::CheckLimitations(const ValidationState_t& _,
396 const Function* entry_point,
397 std::string* reason) const {
398 bool return_value = true;
399 std::stringstream ss_reason;
400
401 for (const auto& is_compatible : limitations_) {
402 std::string message;
403 if (!is_compatible(_, entry_point, &message)) {
404 if (!reason) return false;
405 return_value = false;
406 if (!message.empty()) {
407 ss_reason << message << "\n";
408 }
409 }
410 }
411
412 if (!return_value && reason) {
413 *reason = ss_reason.str();
414 }
415
416 return return_value;
417 }
418
419 } // namespace val
420 } // namespace spvtools
421