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