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