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