| 1 |
// Copyright (c) 2020 Google LLC |
| 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 |
#ifndef SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H_ |
| 16 |
#define SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H_ |
| 17 |
|
| 18 |
#include "source/fuzz/transformation.h" |
| 19 |
|
| 20 |
namespace spvtools { |
| 21 |
namespace fuzz { |
| 22 |
|
| 23 |
class TransformationFlattenConditionalBranch : public Transformation { |
| 24 |
public: |
| 25 |
explicit TransformationFlattenConditionalBranch( |
| 26 |
const protobufs::TransformationFlattenConditionalBranch& message); |
| 27 |
|
| 28 |
TransformationFlattenConditionalBranch( |
| 29 |
uint32_t header_block_id, bool true_branch_first, |
| 30 |
uint32_t fresh_id_for_bvec2_selector, |
| 31 |
uint32_t fresh_id_for_bvec3_selector, |
| 32 |
uint32_t fresh_id_for_bvec4_selector, |
| 33 |
const std::vector<protobufs::SideEffectWrapperInfo>& |
| 34 |
side_effect_wrappers_info); |
| 35 |
|
| 36 |
// - |message_.header_block_id| must be the label id of a reachable selection |
| 37 |
// header, which ends with an OpBranchConditional instruction. |
| 38 |
// - The condition of the OpBranchConditional instruction must not be an |
| 39 |
// irrelevant id. |
| 40 |
// - The header block and the merge block must describe a single-entry, |
| 41 |
// single-exit region. |
| 42 |
// - The region must not contain barrier or OpSampledImage instructions. |
| 43 |
// - The region must not contain selection or loop constructs. |
| 44 |
// - For each instruction that requires additional fresh ids, then: |
| 45 |
// - if the instruction is mapped to the required ids for enclosing it by |
| 46 |
// |message_.side_effect_wrapper_info|, these must be valid (the |
| 47 |
// fresh ids must be non-zero, fresh and distinct); |
| 48 |
// - if there is no such mapping, the transformation context must have |
| 49 |
// overflow ids available. |
| 50 |
bool IsApplicable( |
| 51 |
opt::IRContext* ir_context, |
| 52 |
const TransformationContext& transformation_context) const override; |
| 53 |
|
| 54 |
// Flattens the selection construct with header |message_.header_block_id|, |
| 55 |
// changing any OpPhi in the block where the flow converges to OpSelect and |
| 56 |
// enclosing any instruction with side effects in conditionals so that |
| 57 |
// they are only executed when they should. |
| 58 |
void Apply(opt::IRContext* ir_context, |
| 59 |
TransformationContext* transformation_context) const override; |
| 60 |
|
| 61 |
std::unordered_set<uint32_t> GetFreshIds() const override; |
| 62 |
|
| 63 |
protobufs::Transformation ToMessage() const override; |
| 64 |
|
| 65 |
// Returns true if the conditional headed by |header| can be flattened, |
| 66 |
// according to the conditions of the IsApplicable method, assuming that |
| 67 |
// enough fresh ids would be provided. In this case, it fills the |
| 68 |
// |instructions_that_need_ids| set with all the instructions that would |
| 69 |
// require fresh ids. |
| 70 |
// Returns false otherwise. |
| 71 |
// Assumes that |header| is the header of a conditional, so its last two |
| 72 |
// instructions are OpSelectionMerge and OpBranchConditional. |
| 73 |
static bool GetProblematicInstructionsIfConditionalCanBeFlattened( |
| 74 |
opt::IRContext* ir_context, opt::BasicBlock* header, |
| 75 |
const TransformationContext& transformation_context, |
| 76 |
std::set<opt::Instruction*>* instructions_that_need_ids); |
| 77 |
|
| 78 |
// Returns true iff the given instruction needs a placeholder to be enclosed |
| 79 |
// inside a conditional. So, it returns: |
| 80 |
// - true if the instruction has a non-void result id, |
| 81 |
// - false if the instruction does not have a result id or has a void result |
| 82 |
// id. |
| 83 |
// Assumes that the instruction has side effects, requiring it to be enclosed |
| 84 |
// inside a conditional, and that it can be enclosed inside a conditional |
| 85 |
// keeping the module valid. Assumes that, if the instruction has a void |
| 86 |
// result type, its result id is not used in the module. |
| 87 |
static bool InstructionNeedsPlaceholder(opt::IRContext* ir_context, |
| 88 |
const opt::Instruction& instruction); |
| 89 |
|
| 90 |
// Returns true if and only if the SPIR-V version is such that the arguments |
| 91 |
// to OpSelect are restricted to only scalars, pointers (if the appropriate |
| 92 |
// capability is enabled) and component-wise vectors. |
| 93 |
static bool OpSelectArgumentsAreRestricted(opt::IRContext* ir_context); |
| 94 |
|
| 95 |
// Find the first block where flow converges (it is not necessarily the merge |
| 96 |
// block) by walking the true branch until reaching a block that post- |
| 97 |
// dominates the header. |
| 98 |
// This is necessary because a potential common set of blocks at the end of |
| 99 |
// the construct should not be duplicated. |
| 100 |
static uint32_t FindConvergenceBlock(opt::IRContext* ir_context, |
| 101 |
const opt::BasicBlock& header_block); |
| 102 |
|
| 103 |
private: |
| 104 |
// Returns an unordered_map mapping instructions to the info required to |
| 105 |
// enclose them inside a conditional. It maps the instructions to the |
| 106 |
// corresponding entry in |message_.side_effect_wrapper_info|. |
| 107 |
std::unordered_map<opt::Instruction*, protobufs::SideEffectWrapperInfo> |
| 108 |
GetInstructionsToWrapperInfo(opt::IRContext* ir_context) const; |
| 109 |
|
| 110 |
// Splits the given block, adding a new selection construct so that the given |
| 111 |
// instruction is only executed if the boolean value of |condition_id| matches |
| 112 |
// the value of |exec_if_cond_true|. |
| 113 |
// Assumes that all parameters are consistent. |
| 114 |
// 2 fresh ids are required if the instruction does not have a result id (the |
| 115 |
// first two ids in |wrapper_info| must be valid fresh ids), 5 otherwise. |
| 116 |
// Returns the merge block created. |
| 117 |
// |
| 118 |
// |dead_blocks| and |irrelevant_ids| are used to record the ids of blocks |
| 119 |
// and instructions for which dead block and irrelevant id facts should |
| 120 |
// ultimately be created. |
| 121 |
static opt::BasicBlock* EncloseInstructionInConditional( |
| 122 |
opt::IRContext* ir_context, |
| 123 |
const TransformationContext& transformation_context, |
| 124 |
opt::BasicBlock* block, opt::Instruction* instruction, |
| 125 |
const protobufs::SideEffectWrapperInfo& wrapper_info, |
| 126 |
uint32_t condition_id, bool exec_if_cond_true, |
| 127 |
std::vector<uint32_t>* dead_blocks, |
| 128 |
std::vector<uint32_t>* irrelevant_ids); |
| 129 |
|
| 130 |
// Turns every OpPhi instruction of |convergence_block| -- the convergence |
| 131 |
// block for |header_block| (both in |ir_context|) into an OpSelect |
| 132 |
// instruction. |
| 133 |
void RewriteOpPhiInstructionsAtConvergenceBlock( |
| 134 |
const opt::BasicBlock& header_block, uint32_t convergence_block_id, |
| 135 |
opt::IRContext* ir_context) const; |
| 136 |
|
| 137 |
// Adds an OpCompositeExtract instruction to the start of |block| in |
| 138 |
// |ir_context|, with result id given by |fresh_id|. The instruction will |
| 139 |
// make a |dimension|-dimensional boolean vector with |
| 140 |
// |branch_condition_operand| at every component. |
| 141 |
static void AddBooleanVectorConstructorToBlock( |
| 142 |
uint32_t fresh_id, uint32_t dimension, |
| 143 |
const opt::Operand& branch_condition_operand, opt::IRContext* ir_context, |
| 144 |
opt::BasicBlock* block); |
| 145 |
|
| 146 |
// Returns true if the given instruction either has no side effects or it can |
| 147 |
// be handled by being enclosed in a conditional. |
| 148 |
static bool InstructionCanBeHandled(opt::IRContext* ir_context, |
| 149 |
const opt::Instruction& instruction); |
| 150 |
|
| 151 |
protobufs::TransformationFlattenConditionalBranch message_; |
| 152 |
}; |
| 153 |
|
| 154 |
} // namespace fuzz |
| 155 |
} // namespace spvtools |
| 156 |
|
| 157 |
#endif // SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H_ |