1// Copyright (c) 2018 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_OPT_COPY_PROP_ARRAYS_H_
16#define SOURCE_OPT_COPY_PROP_ARRAYS_H_
17
18#include <memory>
19#include <vector>
20
21#include "source/opt/mem_pass.h"
22
23namespace spvtools {
24namespace opt {
25
26// This pass implements a simple array copy propagation. It does not do a full
27// array data flow. It looks for simple cases that meet the following
28// conditions:
29//
30// 1) The source must never be stored to.
31// 2) The target must be stored to exactly once.
32// 3) The store to the target must be a store to the entire array, and be a
33// copy of the entire source.
34// 4) All loads of the target must be dominated by the store.
35//
36// The hard part is keeping all of the types correct. We do not want to
37// have to do too large a search to update everything, which may not be
38// possible, do we give up if we see any instruction that might be hard to
39// update.
40
41class CopyPropagateArrays : public MemPass {
42 public:
43 const char* name() const override { return "copy-propagate-arrays"; }
44 Status Process() override;
45
46 IRContext::Analysis GetPreservedAnalyses() override {
47 return IRContext::kAnalysisDefUse | IRContext::kAnalysisCFG |
48 IRContext::kAnalysisInstrToBlockMapping |
49 IRContext::kAnalysisLoopAnalysis | IRContext::kAnalysisDecorations |
50 IRContext::kAnalysisDominatorAnalysis | IRContext::kAnalysisNameMap |
51 IRContext::kAnalysisConstants | IRContext::kAnalysisTypes;
52 }
53
54 private:
55 // The class used to identify a particular memory object. This memory object
56 // will be owned by a particular variable, meaning that the memory is part of
57 // that variable. It could be the entire variable or a member of the
58 // variable.
59 class MemoryObject {
60 public:
61 // Construction a memory object that is owned by |var_inst|. The iterator
62 // |begin| and |end| traverse a container of integers that identify which
63 // member of |var_inst| this memory object will represent. These integers
64 // are interpreted the same way they would be in an |OpAccessChain|
65 // instruction.
66 template <class iterator>
67 MemoryObject(Instruction* var_inst, iterator begin, iterator end);
68
69 // Change |this| to now point to the member identified by |access_chain|
70 // (starting from the current member). The elements in |access_chain| are
71 // interpreted the same as the indices in the |OpAccessChain|
72 // instruction.
73 void GetMember(const std::vector<uint32_t>& access_chain);
74
75 // Change |this| to now represent the first enclosing object to which it
76 // belongs. (Remove the last element off the access_chain). It is invalid
77 // to call this function if |this| does not represent a member of its owner.
78 void GetParent() {
79 assert(IsMember());
80 access_chain_.pop_back();
81 }
82
83 // Returns true if |this| represents a member of its owner, and not the
84 // entire variable.
85 bool IsMember() const { return !access_chain_.empty(); }
86
87 // Returns the number of members in the object represented by |this|. If
88 // |this| does not represent a composite type, the return value will be 0.
89 uint32_t GetNumberOfMembers();
90
91 // Returns the owning variable that the memory object is contained in.
92 Instruction* GetVariable() const { return variable_inst_; }
93
94 // Returns a vector of integers that can be used to access the specific
95 // member that |this| represents starting from the owning variable. These
96 // values are to be interpreted the same way the indices are in an
97 // |OpAccessChain| instruction.
98 const std::vector<uint32_t>& AccessChain() const { return access_chain_; }
99
100 // Returns the type id of the pointer type that can be used to point to this
101 // memory object.
102 uint32_t GetPointerTypeId(const CopyPropagateArrays* pass) const {
103 analysis::DefUseManager* def_use_mgr =
104 GetVariable()->context()->get_def_use_mgr();
105 analysis::TypeManager* type_mgr =
106 GetVariable()->context()->get_type_mgr();
107
108 Instruction* var_pointer_inst =
109 def_use_mgr->GetDef(GetVariable()->type_id());
110
111 uint32_t member_type_id = pass->GetMemberTypeId(
112 var_pointer_inst->GetSingleWordInOperand(1), GetAccessIds());
113
114 uint32_t member_pointer_type_id = type_mgr->FindPointerToType(
115 member_type_id, static_cast<SpvStorageClass>(
116 var_pointer_inst->GetSingleWordInOperand(0)));
117 return member_pointer_type_id;
118 }
119
120 // Returns the storage class of the memory object.
121 SpvStorageClass GetStorageClass() const {
122 analysis::TypeManager* type_mgr =
123 GetVariable()->context()->get_type_mgr();
124 const analysis::Pointer* pointer_type =
125 type_mgr->GetType(GetVariable()->type_id())->AsPointer();
126 return pointer_type->storage_class();
127 }
128
129 // Returns true if |other| represents memory that is contains inside of the
130 // memory represented by |this|.
131 bool Contains(MemoryObject* other);
132
133 private:
134 // The variable that owns this memory object.
135 Instruction* variable_inst_;
136
137 // The access chain to reach the particular member the memory object
138 // represents. It should be interpreted the same way the indices in an
139 // |OpAccessChain| are interpreted.
140 std::vector<uint32_t> access_chain_;
141 std::vector<uint32_t> GetAccessIds() const;
142 };
143
144 // Returns the memory object being stored to |var_inst| in the store
145 // instruction |store_inst|, if one exists, that can be used in place of
146 // |var_inst| in all of the loads of |var_inst|. This code is conservative
147 // and only identifies very simple cases. If no such memory object can be
148 // found, the return value is |nullptr|.
149 std::unique_ptr<CopyPropagateArrays::MemoryObject> FindSourceObjectIfPossible(
150 Instruction* var_inst, Instruction* store_inst);
151
152 // Replaces all loads of |var_inst| with a load from |source| instead.
153 // |insertion_pos| is a position where it is possible to construct the
154 // address of |source| and also dominates all of the loads of |var_inst|.
155 void PropagateObject(Instruction* var_inst, MemoryObject* source,
156 Instruction* insertion_pos);
157
158 // Returns true if all of the references to |ptr_inst| can be rewritten and
159 // are dominated by |store_inst|.
160 bool HasValidReferencesOnly(Instruction* ptr_inst, Instruction* store_inst);
161
162 // Returns a memory object that at one time was equivalent to the value in
163 // |result|. If no such memory object exists, the return value is |nullptr|.
164 std::unique_ptr<MemoryObject> GetSourceObjectIfAny(uint32_t result);
165
166 // Returns the memory object that is loaded by |load_inst|. If a memory
167 // object cannot be identified, the return value is |nullptr|. The opcode of
168 // |load_inst| must be |OpLoad|.
169 std::unique_ptr<MemoryObject> BuildMemoryObjectFromLoad(
170 Instruction* load_inst);
171
172 // Returns the memory object that at some point was equivalent to the result
173 // of |extract_inst|. If a memory object cannot be identified, the return
174 // value is |nullptr|. The opcode of |extract_inst| must be
175 // |OpCompositeExtract|.
176 std::unique_ptr<MemoryObject> BuildMemoryObjectFromExtract(
177 Instruction* extract_inst);
178
179 // Returns the memory object that at some point was equivalent to the result
180 // of |construct_inst|. If a memory object cannot be identified, the return
181 // value is |nullptr|. The opcode of |constuct_inst| must be
182 // |OpCompositeConstruct|.
183 std::unique_ptr<MemoryObject> BuildMemoryObjectFromCompositeConstruct(
184 Instruction* conststruct_inst);
185
186 // Returns the memory object that at some point was equivalent to the result
187 // of |insert_inst|. If a memory object cannot be identified, the return
188 // value is |nullptr\. The opcode of |insert_inst| must be
189 // |OpCompositeInsert|. This function looks for a series of
190 // |OpCompositeInsert| instructions that insert the elements one at a time in
191 // order from beginning to end.
192 std::unique_ptr<MemoryObject> BuildMemoryObjectFromInsert(
193 Instruction* insert_inst);
194
195 // Return true if |type_id| is a pointer type whose pointee type is an array.
196 bool IsPointerToArrayType(uint32_t type_id);
197
198 // Returns true of there are not stores using |ptr_inst| or something derived
199 // from it.
200 bool HasNoStores(Instruction* ptr_inst);
201
202 // Creates an |OpAccessChain| instruction whose result is a pointer the memory
203 // represented by |source|. The new instruction will be placed before
204 // |insertion_point|. |insertion_point| must be part of a function. Returns
205 // the new instruction.
206 Instruction* BuildNewAccessChain(Instruction* insertion_point,
207 MemoryObject* source) const;
208
209 // Rewrites all uses of |original_ptr| to use |new_pointer_inst| updating
210 // types of other instructions as needed. This function should not be called
211 // if |CanUpdateUses(original_ptr_inst, new_pointer_inst->type_id())| returns
212 // false.
213 void UpdateUses(Instruction* original_ptr_inst,
214 Instruction* new_pointer_inst);
215
216 // Return true if |UpdateUses| is able to change all of the uses of
217 // |original_ptr_inst| to |type_id| and still have valid code.
218 bool CanUpdateUses(Instruction* original_ptr_inst, uint32_t type_id);
219
220 // Returns a store to |var_inst| that writes to the entire variable, and is
221 // the only store that does so. Note it does not look through OpAccessChain
222 // instruction, so partial stores are not considered.
223 Instruction* FindStoreInstruction(const Instruction* var_inst) const;
224
225 // Return the type id of the member of the type |id| access using
226 // |access_chain|. The elements of |access_chain| are to be interpreted the
227 // same way the indexes are used in an |OpCompositeExtract| instruction.
228 uint32_t GetMemberTypeId(uint32_t id,
229 const std::vector<uint32_t>& access_chain) const;
230};
231
232} // namespace opt
233} // namespace spvtools
234
235#endif // SOURCE_OPT_COPY_PROP_ARRAYS_H_
236