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 #include "source/opt/reduce_load_size.h"
16
17 #include <set>
18 #include <vector>
19
20 #include "source/opt/instruction.h"
21 #include "source/opt/ir_builder.h"
22 #include "source/opt/ir_context.h"
23 #include "source/util/bit_vector.h"
24
25 namespace spvtools {
26 namespace opt {
27 namespace {
28 constexpr uint32_t kExtractCompositeIdInIdx = 0;
29 constexpr uint32_t kVariableStorageClassInIdx = 0;
30 constexpr uint32_t kLoadPointerInIdx = 0;
31 } // namespace
32
Process()33 Pass::Status ReduceLoadSize::Process() {
34 bool modified = false;
35
36 for (auto& func : *get_module()) {
37 func.ForEachInst([&modified, this](Instruction* inst) {
38 if (inst->opcode() == spv::Op::OpCompositeExtract) {
39 if (ShouldReplaceExtract(inst)) {
40 modified |= ReplaceExtract(inst);
41 }
42 }
43 });
44 }
45
46 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
47 }
48
ReplaceExtract(Instruction * inst)49 bool ReduceLoadSize::ReplaceExtract(Instruction* inst) {
50 assert(inst->opcode() == spv::Op::OpCompositeExtract &&
51 "Wrong opcode. Should be OpCompositeExtract.");
52 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
53 analysis::TypeManager* type_mgr = context()->get_type_mgr();
54 analysis::ConstantManager* const_mgr = context()->get_constant_mgr();
55
56 uint32_t composite_id =
57 inst->GetSingleWordInOperand(kExtractCompositeIdInIdx);
58 Instruction* composite_inst = def_use_mgr->GetDef(composite_id);
59
60 if (composite_inst->opcode() != spv::Op::OpLoad) {
61 return false;
62 }
63
64 analysis::Type* composite_type = type_mgr->GetType(composite_inst->type_id());
65 if (composite_type->kind() == analysis::Type::kVector ||
66 composite_type->kind() == analysis::Type::kMatrix) {
67 return false;
68 }
69
70 Instruction* var = composite_inst->GetBaseAddress();
71 if (var == nullptr || var->opcode() != spv::Op::OpVariable) {
72 return false;
73 }
74
75 spv::StorageClass storage_class = static_cast<spv::StorageClass>(
76 var->GetSingleWordInOperand(kVariableStorageClassInIdx));
77 switch (storage_class) {
78 case spv::StorageClass::Uniform:
79 case spv::StorageClass::UniformConstant:
80 case spv::StorageClass::Input:
81 break;
82 default:
83 return false;
84 }
85
86 // Create a new access chain and load just after the old load.
87 // We cannot create the new access chain load in the position of the extract
88 // because the storage may have been written to in between.
89 InstructionBuilder ir_builder(
90 inst->context(), composite_inst,
91 IRContext::kAnalysisInstrToBlockMapping | IRContext::kAnalysisDefUse);
92
93 uint32_t pointer_to_result_type_id =
94 type_mgr->FindPointerToType(inst->type_id(), storage_class);
95 assert(pointer_to_result_type_id != 0 &&
96 "We did not find the pointer type that we need.");
97
98 analysis::Integer int_type(32, false);
99 const analysis::Type* uint32_type = type_mgr->GetRegisteredType(&int_type);
100 std::vector<uint32_t> ids;
101 for (uint32_t i = 1; i < inst->NumInOperands(); ++i) {
102 uint32_t index = inst->GetSingleWordInOperand(i);
103 const analysis::Constant* index_const =
104 const_mgr->GetConstant(uint32_type, {index});
105 ids.push_back(const_mgr->GetDefiningInstruction(index_const)->result_id());
106 }
107
108 Instruction* new_access_chain = ir_builder.AddAccessChain(
109 pointer_to_result_type_id,
110 composite_inst->GetSingleWordInOperand(kLoadPointerInIdx), ids);
111 Instruction* new_load =
112 ir_builder.AddLoad(inst->type_id(), new_access_chain->result_id());
113
114 context()->ReplaceAllUsesWith(inst->result_id(), new_load->result_id());
115 context()->KillInst(inst);
116 return true;
117 }
118
ShouldReplaceExtract(Instruction * inst)119 bool ReduceLoadSize::ShouldReplaceExtract(Instruction* inst) {
120 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
121 Instruction* op_inst = def_use_mgr->GetDef(
122 inst->GetSingleWordInOperand(kExtractCompositeIdInIdx));
123
124 if (op_inst->opcode() != spv::Op::OpLoad) {
125 return false;
126 }
127
128 auto cached_result = should_replace_cache_.find(op_inst->result_id());
129 if (cached_result != should_replace_cache_.end()) {
130 return cached_result->second;
131 }
132
133 bool all_elements_used = false;
134 std::set<uint32_t> elements_used;
135
136 all_elements_used =
137 !def_use_mgr->WhileEachUser(op_inst, [&elements_used](Instruction* use) {
138 if (use->IsCommonDebugInstr()) return true;
139 if (use->opcode() != spv::Op::OpCompositeExtract ||
140 use->NumInOperands() == 1) {
141 return false;
142 }
143 elements_used.insert(use->GetSingleWordInOperand(1));
144 return true;
145 });
146
147 bool should_replace = false;
148 if (all_elements_used) {
149 should_replace = false;
150 } else if (1.0 <= replacement_threshold_) {
151 should_replace = true;
152 } else {
153 analysis::ConstantManager* const_mgr = context()->get_constant_mgr();
154 analysis::TypeManager* type_mgr = context()->get_type_mgr();
155 analysis::Type* load_type = type_mgr->GetType(op_inst->type_id());
156 uint32_t total_size = 1;
157 switch (load_type->kind()) {
158 case analysis::Type::kArray: {
159 const analysis::Constant* size_const =
160 const_mgr->FindDeclaredConstant(load_type->AsArray()->LengthId());
161
162 if (size_const) {
163 assert(size_const->AsIntConstant());
164 total_size = size_const->GetU32();
165 } else {
166 // The size is spec constant, so it is unknown at this time. Assume
167 // it is very large.
168 total_size = UINT32_MAX;
169 }
170 } break;
171 case analysis::Type::kStruct:
172 total_size = static_cast<uint32_t>(
173 load_type->AsStruct()->element_types().size());
174 break;
175 default:
176 break;
177 }
178 double percent_used = static_cast<double>(elements_used.size()) /
179 static_cast<double>(total_size);
180 should_replace = (percent_used < replacement_threshold_);
181 }
182
183 should_replace_cache_[op_inst->result_id()] = should_replace;
184 return should_replace;
185 }
186
187 } // namespace opt
188 } // namespace spvtools
189