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_MERGE_FUNCTION_RETURNS_ 16 #define SOURCE_FUZZ_TRANSFORMATION_MERGE_FUNCTION_RETURNS_ 17 18 #include "source/fuzz/transformation.h" 19 20 namespace spvtools { 21 namespace fuzz { 22 class TransformationMergeFunctionReturns : public Transformation { 23 public: 24 explicit TransformationMergeFunctionReturns( 25 protobufs::TransformationMergeFunctionReturns message); 26 27 TransformationMergeFunctionReturns( 28 uint32_t function_id, uint32_t outer_header_id, 29 uint32_t unreachable_continue_id, uint32_t outer_return_id, 30 uint32_t return_val_id, uint32_t any_returnable_val_id, 31 const std::vector<protobufs::ReturnMergingInfo>& returns_merging_info); 32 33 // - |message_.function_id| is the id of a function. 34 // - The entry block of |message_.function_id| branches unconditionally to 35 // another block. 36 // - |message_.any_returnable_val_id| is an id whose type is the same as the 37 // return type of the function and which is available at the end of the 38 // entry block. If this id is not found in the module, the transformation 39 // will try to find a suitable one. 40 // If the function is void, or no loops in the function contain return 41 // statements, this id will be ignored. 42 // - Merge blocks of reachable loops that contain return statements only 43 // consist of OpLabel, OpPhi or OpBranch instructions. 44 // - The module contains OpConstantTrue and OpConstantFalse instructions. 45 // - For all merge blocks of reachable loops that contain return statements, 46 // either: 47 // - a mapping is provided in |message_.return_merging_info|, all of the 48 // corresponding fresh ids are valid and, for each OpPhi instruction in 49 // the block, there is a mapping to an available id of the same type in 50 // |opphi_to_suitable_id| or a suitable id, available at the end of the 51 // entry block, can be found in the module. 52 // - there is no mapping, but overflow ids are available and, for every 53 // OpPhi instruction in the merge blocks that need to be modified, a 54 // suitable id, available at the end of the entry block, can be found. 55 // - The addition of new predecessors to the relevant merge blocks does not 56 // cause any id use to be invalid (i.e. every id must dominate all its uses 57 // even after the transformation has added new branches). 58 // - All of the fresh ids that are provided and needed by the transformation 59 // are valid. 60 bool IsApplicable( 61 opt::IRContext* ir_context, 62 const TransformationContext& transformation_context) const override; 63 64 // Changes the function so that there is only one reachable return 65 // instruction. The function is enclosed by an outer loop, whose merge block 66 // is the new return block. All existing return statements are replaced by 67 // branch instructions to the merge block of the loop enclosing them, and 68 // OpPhi instructions are used to keep track of the return value and of 69 // whether the function is returning. 70 void Apply(opt::IRContext* ir_context, 71 TransformationContext* transformation_context) const override; 72 73 std::unordered_set<uint32_t> GetFreshIds() const override; 74 75 protobufs::Transformation ToMessage() const override; 76 77 private: 78 // Returns a map from merge block ids to the corresponding info in 79 // |message_.return_merging_info|. 80 std::map<uint32_t, protobufs::ReturnMergingInfo> 81 GetMappingOfMergeBlocksToInfo() const; 82 83 // Returns a map from type ids to an id with that type and which is available 84 // at the end of the entry block of |message_.function_id|. 85 // Assumes that the function exists. 86 std::map<uint32_t, uint32_t> GetTypesToIdAvailableAfterEntryBlock( 87 opt::IRContext* ir_context) const; 88 89 // Returns true if adding new predecessors to the given loop merge blocks 90 // does not render any instructions invalid (each id definition must still 91 // dominate all of its uses). The loop merge blocks and corresponding new 92 // predecessors to consider are given in |merge_blocks_to_new_predecessors|. 93 // All of the new predecessors are assumed to be inside the loop associated 94 // with the corresponding loop merge block. 95 static bool CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors( 96 opt::IRContext* ir_context, const opt::Function* function, 97 const std::map<uint32_t, std::set<uint32_t>>& 98 merge_blocks_to_new_predecessors); 99 100 // Returns true if the required ids for |merge_block| are provided in the 101 // |merge_blocks_to_info| map, or if ids of the suitable type can be found. 102 static bool CheckThatTheCorrectIdsAreGivenForMergeBlock( 103 uint32_t merge_block, 104 const std::map<uint32_t, protobufs::ReturnMergingInfo>& 105 merge_blocks_to_info, 106 const std::map<uint32_t, uint32_t>& types_to_available_id, 107 bool function_is_void, opt::IRContext* ir_context, 108 const TransformationContext& transformation_context, 109 std::set<uint32_t>* used_fresh_ids); 110 111 protobufs::TransformationMergeFunctionReturns message_; 112 }; 113 } // namespace fuzz 114 } // namespace spvtools 115 116 #endif // SOURCE_FUZZ_TRANSFORMATION_MERGE_FUNCTION_RETURNS_ 117