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