blob: 7b55f474cd8b1ed6282143327ad4a99254a39edb [file] [log] [blame]
// Copyright (c) 2019 Google LLC
// 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
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
#include "source/fuzz/transformation_add_dead_break.h"
#include "source/fuzz/fact_manager.h"
#include "source/opt/basic_block.h"
#include "source/opt/ir_context.h"
#include "source/opt/struct_cfg_analysis.h"
namespace spvtools {
namespace fuzz {
const spvtools::fuzz::protobufs::TransformationAddDeadBreak& message)
: message_(message) {}
uint32_t from_block, uint32_t to_block, bool break_condition_value,
std::vector<uint32_t> phi_id) {
for (auto id : phi_id) {
opt::BasicBlock* TransformationAddDeadBreak::MaybeFindBlock(
opt::IRContext* context, uint32_t maybe_block_id) const {
auto inst = context->get_def_use_mgr()->GetDef(maybe_block_id);
if (inst == nullptr) {
// No instruction defining this id was found.
return nullptr;
if (inst->opcode() != SpvOpLabel) {
// The instruction defining the id is not a label, so it cannot be a block
// id.
return nullptr;
return context->cfg()->block(maybe_block_id);
bool TransformationAddDeadBreak::PhiIdsOk(opt::IRContext* context,
opt::BasicBlock* bb_from,
opt::BasicBlock* bb_to) const {
if (bb_from->IsSuccessor(bb_to)) {
// There is already an edge from |from_block| to |to_block|, so there is
// no need to extend OpPhi instructions. Do not allow phi ids to be
// present. This might turn out to be too strict; perhaps it would be OK
// just to ignore the ids in this case.
return message_.phi_id().empty();
// The break would add a previously non-existent edge from |from_block| to
// |to_block|, so we go through the given phi ids and check that they exactly
// match the OpPhi instructions in |to_block|.
uint32_t phi_index = 0;
// An explicit loop, rather than applying a lambda to each OpPhi in |bb_to|,
// makes sense here because we need to increment |phi_index| for each OpPhi
// instruction.
for (auto& inst : *bb_to) {
if (inst.opcode() != SpvOpPhi) {
// The OpPhi instructions all occur at the start of the block; if we find
// a non-OpPhi then we have seen them all.
if (phi_index == static_cast<uint32_t>(message_.phi_id().size())) {
// Not enough phi ids have been provided to account for the OpPhi
// instructions.
return false;
// Look for an instruction defining the next phi id.
opt::Instruction* phi_extension =
if (!phi_extension) {
// The id given to extend this OpPhi does not exist.
return false;
if (phi_extension->type_id() != inst.type_id()) {
// The instruction given to extend this OpPhi either does not have a type
// or its type does not match that of the OpPhi.
return false;
if (context->get_instr_block(phi_extension)) {
// The instruction defining the phi id has an associated block (i.e., it
// is not a global value). Check whether its definition dominates the
// exit of |from_block|.
auto dominator_analysis =
if (!dominator_analysis->Dominates(phi_extension,
bb_from->terminator())) {
// The given id is no good as its definition does not dominate the exit
// of |from_block|
return false;
// Reject the transformation if not all of the ids for extending OpPhi
// instructions are needed. This might turn out to be stricter than necessary;
// perhaps it would be OK just to not use the ids in this case.
return phi_index == static_cast<uint32_t>(message_.phi_id().size());
bool TransformationAddDeadBreak::FromBlockIsInLoopContinueConstruct(
opt::IRContext* context, uint32_t maybe_loop_header) const {
// We deem a block to be part of a loop's continue construct if the loop's
// continue target dominates the block.
auto containing_construct_block = context->cfg()->block(maybe_loop_header);
if (containing_construct_block->IsLoopHeader()) {
auto continue_target = containing_construct_block->ContinueBlockId();
if (context->GetDominatorAnalysis(containing_construct_block->GetParent())
->Dominates(continue_target, message_.from_block())) {
return true;
return false;
bool TransformationAddDeadBreak::AddingBreakRespectsStructuredControlFlow(
opt::IRContext* context, opt::BasicBlock* bb_from) const {
// Look at the structured control flow associated with |from_block| and
// check whether it is contained in an appropriate construct with merge id
// |to_block| such that a break from |from_block| to |to_block| is legal.
// There are three legal cases to consider:
// (1) |from_block| is a loop header and |to_block| is its merge
// (2) |from_block| is a non-header node of a construct, and |to_block|
// is the merge for that construct
// (3) |from_block| is a non-header node of a selection construct, and
// |to_block| is the merge for the innermost loop containing
// |from_block|
// TODO( It may be
// possible to be more aggressive in breaking from switch constructs.
// The reason we need to distinguish between cases (1) and (2) is that the
// structured CFG analysis does not deem a header to be part of the construct
// that it heads.
// Consider case (1)
if (bb_from->IsLoopHeader()) {
// Case (1) holds if |to_block| is the merge block for the loop;
// otherwise no case holds
return bb_from->MergeBlockId() == message_.to_block();
// Both cases (2) and (3) require that |from_block| is inside some
// structured control flow construct.
auto containing_construct =
if (!containing_construct) {
// |from_block| is not in a construct from which we can break.
return false;
// Consider case (2)
if (message_.to_block() ==
context->cfg()->block(containing_construct)->MergeBlockId()) {
// This looks like an instance of case (2).
// However, the structured CFG analysis regards the continue construct of a
// loop as part of the loop, but it is not legal to jump from a loop's
// continue construct to the loop's merge (except from the back-edge block),
// so we need to check for this case.
// TODO( We do not
// currently allow a dead break from a back edge block, but we could and
// ultimately should.
return !FromBlockIsInLoopContinueConstruct(context, containing_construct);
// Case (3) holds if and only if |to_block| is the merge block for this
// innermost loop that contains |from_block|
auto containing_loop_header =
if (containing_loop_header &&
message_.to_block() ==
context->cfg()->block(containing_loop_header)->MergeBlockId()) {
return !FromBlockIsInLoopContinueConstruct(context, containing_loop_header);
return false;
bool TransformationAddDeadBreak::IsApplicable(
opt::IRContext* context, const FactManager& /*unused*/) const {
// First, we check that a constant with the same value as
// |break_condition_value| is present.
opt::analysis::Bool bool_type;
auto registered_bool_type =
if (!registered_bool_type) {
return false;
opt::analysis::BoolConstant bool_constant(registered_bool_type->AsBool(),
if (!context->get_constant_mgr()->FindConstant(&bool_constant)) {
// The required constant is not present, so the transformation cannot be
// applied.
return false;
// Check that |from_block| and |to_block| really are block ids
opt::BasicBlock* bb_from = MaybeFindBlock(context, message_.from_block());
if (bb_from == nullptr) {
return false;
opt::BasicBlock* bb_to = MaybeFindBlock(context, message_.to_block());
if (bb_to == nullptr) {
return false;
// Check that |from_block| ends with an unconditional branch.
if (bb_from->terminator()->opcode() != SpvOpBranch) {
// The block associated with the id does not end with an unconditional
// branch.
return false;
assert(bb_from != nullptr &&
"We should have found a block if this line of code is reached.");
bb_from->id() == message_.from_block() &&
"The id of the block we found should match the source id for the break.");
assert(bb_to != nullptr &&
"We should have found a block if this line of code is reached.");
bb_to->id() == message_.to_block() &&
"The id of the block we found should match the target id for the break.");
// Check whether the data passed to extend OpPhi instructions is appropriate.
if (!PhiIdsOk(context, bb_from, bb_to)) {
return false;
// Finally, check that adding the break would respect the rules of structured
// control flow.
return AddingBreakRespectsStructuredControlFlow(context, bb_from);
void TransformationAddDeadBreak::Apply(opt::IRContext* context,
FactManager* /*unused*/) const {
// Get the id of the boolean constant to be used as the break condition.
opt::analysis::Bool bool_type;
opt::analysis::BoolConstant bool_constant(
uint32_t bool_id = context->get_constant_mgr()->FindDeclaredConstant(
&bool_constant, context->get_type_mgr()->GetId(&bool_type));
auto bb_from = context->cfg()->block(message_.from_block());
auto bb_to = context->cfg()->block(message_.to_block());
const bool from_to_edge_already_exists = bb_from->IsSuccessor(bb_to);
auto successor = bb_from->terminator()->GetSingleWordInOperand(0);
assert(bb_from->terminator()->opcode() == SpvOpBranch &&
"Precondition for the transformation requires that the source block "
"ends with OpBranch");
// Add the dead break, by turning OpBranch into OpBranchConditional, and
// ordering the targets depending on whether the given boolean corresponds to
// true or false.
{{SPV_OPERAND_TYPE_ID, {bool_id}},
{message_.break_condition_value() ? successor : message_.to_block()}},
{message_.break_condition_value() ? message_.to_block() : successor}}});
// Update OpPhi instructions in the target block if this break adds a
// previously non-existent edge from source to target.
if (!from_to_edge_already_exists) {
uint32_t phi_index = 0;
for (auto& inst : *bb_to) {
if (inst.opcode() != SpvOpPhi) {
assert(phi_index < static_cast<uint32_t>(message_.phi_id().size()) &&
"There should be exactly one phi id per OpPhi instruction.");
inst.AddOperand({SPV_OPERAND_TYPE_ID, {message_.phi_id()[phi_index]}});
inst.AddOperand({SPV_OPERAND_TYPE_ID, {message_.from_block()}});
assert(phi_index == static_cast<uint32_t>(message_.phi_id().size()) &&
"There should be exactly one phi id per OpPhi instruction.");
// Invalidate all analyses
protobufs::Transformation TransformationAddDeadBreak::ToMessage() const {
protobufs::Transformation result;
*result.mutable_add_dead_break() = message_;
return result;
} // namespace fuzz
} // namespace spvtools