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