blob: 1ca81d41615340dd8a166ce5d3285db191859330 [file] [log] [blame]
// Copyright (c) 2015-2016 The Khronos Group Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "source/val/construct.h"
#include <cassert>
#include <cstddef>
#include <unordered_set>
#include "source/val/function.h"
#include "source/val/validation_state.h"
namespace spvtools {
namespace val {
Construct::Construct(ConstructType construct_type, BasicBlock* entry,
BasicBlock* exit, std::vector<Construct*> constructs)
: type_(construct_type),
corresponding_constructs_(constructs),
entry_block_(entry),
exit_block_(exit) {}
ConstructType Construct::type() const { return type_; }
const std::vector<Construct*>& Construct::corresponding_constructs() const {
return corresponding_constructs_;
}
std::vector<Construct*>& Construct::corresponding_constructs() {
return corresponding_constructs_;
}
bool ValidateConstructSize(ConstructType type, size_t size) {
switch (type) {
case ConstructType::kSelection:
return size == 0;
case ConstructType::kContinue:
return size == 1;
case ConstructType::kLoop:
return size == 1;
case ConstructType::kCase:
return size >= 1;
default:
assert(1 == 0 && "Type not defined");
}
return false;
}
void Construct::set_corresponding_constructs(
std::vector<Construct*> constructs) {
assert(ValidateConstructSize(type_, constructs.size()));
corresponding_constructs_ = constructs;
}
const BasicBlock* Construct::entry_block() const { return entry_block_; }
BasicBlock* Construct::entry_block() { return entry_block_; }
const BasicBlock* Construct::exit_block() const { return exit_block_; }
BasicBlock* Construct::exit_block() { return exit_block_; }
void Construct::set_exit(BasicBlock* block) { exit_block_ = block; }
Construct::ConstructBlockSet Construct::blocks(Function* /*function*/) const {
const auto header = entry_block();
const auto exit = exit_block();
const bool is_continue = type() == ConstructType::kContinue;
const bool is_loop = type() == ConstructType::kLoop;
const BasicBlock* continue_header = nullptr;
if (is_loop) {
// The only corresponding construct for a loop is the continue.
continue_header = (*corresponding_constructs().begin())->entry_block();
}
std::vector<BasicBlock*> stack;
stack.push_back(const_cast<BasicBlock*>(header));
ConstructBlockSet construct_blocks;
while (!stack.empty()) {
auto* block = stack.back();
stack.pop_back();
if (header->structurally_dominates(*block)) {
bool include = false;
if (is_continue && exit->structurally_postdominates(*block)) {
// Continue construct include blocks dominated by the continue target
// and post-dominated by the back-edge block.
include = true;
} else if (!exit->structurally_dominates(*block)) {
// Selection and loop constructs include blocks dominated by the header
// and not dominated by the merge.
include = true;
if (is_loop && continue_header->structurally_dominates(*block)) {
// Loop constructs have an additional constraint that they do not
// include blocks dominated by the continue construct. Since all
// blocks in the continue construct are dominated by the continue
// target, we just test for dominance by continue target.
include = false;
}
}
if (include) {
if (!construct_blocks.insert(block).second) continue;
for (auto succ : *block->structural_successors()) {
stack.push_back(succ);
}
}
}
}
return construct_blocks;
}
bool Construct::IsStructuredExit(ValidationState_t& _, BasicBlock* dest) const {
// Structured Exits:
// - Selection:
// - branch to its merge
// - branch to nearest enclosing loop merge or continue
// - branch to nearest enclosing switch selection merge
// - Loop:
// - branch to its merge
// - branch to its continue
// - Continue:
// - branch to loop header
// - branch to loop merge
//
// Note: we will never see a case construct here.
assert(type() != ConstructType::kCase);
if (type() == ConstructType::kLoop) {
auto header = entry_block();
auto terminator = header->terminator();
auto index = terminator - &_.ordered_instructions()[0];
auto merge_inst = &_.ordered_instructions()[index - 1];
auto merge_block_id = merge_inst->GetOperandAs<uint32_t>(0u);
auto continue_block_id = merge_inst->GetOperandAs<uint32_t>(1u);
if (dest->id() == merge_block_id || dest->id() == continue_block_id) {
return true;
}
} else if (type() == ConstructType::kContinue) {
auto loop_construct = corresponding_constructs()[0];
auto header = loop_construct->entry_block();
auto terminator = header->terminator();
auto index = terminator - &_.ordered_instructions()[0];
auto merge_inst = &_.ordered_instructions()[index - 1];
auto merge_block_id = merge_inst->GetOperandAs<uint32_t>(0u);
if (dest == header || dest->id() == merge_block_id) {
return true;
}
} else {
assert(type() == ConstructType::kSelection);
if (dest == exit_block()) {
return true;
}
// The next block in the traversal is either:
// i. The header block that declares |block| as its merge block.
// ii. The immediate dominator of |block|.
auto NextBlock = [](const BasicBlock* block) -> const BasicBlock* {
for (auto& use : block->label()->uses()) {
if ((use.first->opcode() == spv::Op::OpLoopMerge ||
use.first->opcode() == spv::Op::OpSelectionMerge) &&
use.second == 1 &&
use.first->block()->structurally_dominates(*block) &&
// A header likely declared itself as its merge.
use.first->block() != block) {
return use.first->block();
}
}
return block->immediate_structural_dominator();
};
bool seen_switch = false;
auto header = entry_block();
auto block = NextBlock(header);
while (block) {
auto terminator = block->terminator();
auto index = terminator - &_.ordered_instructions()[0];
auto merge_inst = &_.ordered_instructions()[index - 1];
if (merge_inst->opcode() == spv::Op::OpLoopMerge ||
(header->terminator()->opcode() != spv::Op::OpSwitch &&
merge_inst->opcode() == spv::Op::OpSelectionMerge &&
terminator->opcode() == spv::Op::OpSwitch)) {
auto merge_target = merge_inst->GetOperandAs<uint32_t>(0u);
auto merge_block = merge_inst->function()->GetBlock(merge_target).first;
if (merge_block->structurally_dominates(*header)) {
block = NextBlock(block);
continue;
}
if ((!seen_switch || merge_inst->opcode() == spv::Op::OpLoopMerge) &&
dest->id() == merge_target) {
return true;
} else if (merge_inst->opcode() == spv::Op::OpLoopMerge) {
auto continue_target = merge_inst->GetOperandAs<uint32_t>(1u);
if (dest->id() == continue_target) {
return true;
}
}
if (terminator->opcode() == spv::Op::OpSwitch) {
seen_switch = true;
}
// Hit an enclosing loop and didn't break or continue.
if (merge_inst->opcode() == spv::Op::OpLoopMerge) return false;
}
block = NextBlock(block);
}
}
return false;
}
} // namespace val
} // namespace spvtools