1 // Copyright (c) 2017 Google Inc.
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/value_number_table.h"
16
17 #include <algorithm>
18
19 #include "source/opt/cfg.h"
20 #include "source/opt/ir_context.h"
21
22 namespace spvtools {
23 namespace opt {
24
GetValueNumber(Instruction * inst) const25 uint32_t ValueNumberTable::GetValueNumber(Instruction* inst) const {
26 assert(inst->result_id() != 0 &&
27 "inst must have a result id to get a value number.");
28
29 // Check if this instruction already has a value.
30 auto result_id_to_val = id_to_value_.find(inst->result_id());
31 if (result_id_to_val != id_to_value_.end()) {
32 return result_id_to_val->second;
33 }
34 return 0;
35 }
36
GetValueNumber(uint32_t id) const37 uint32_t ValueNumberTable::GetValueNumber(uint32_t id) const {
38 return GetValueNumber(context()->get_def_use_mgr()->GetDef(id));
39 }
40
AssignValueNumber(Instruction * inst)41 uint32_t ValueNumberTable::AssignValueNumber(Instruction* inst) {
42 // If it already has a value return that.
43 uint32_t value = GetValueNumber(inst);
44 if (value != 0) {
45 return value;
46 }
47
48 // If the instruction has other side effects, then it must
49 // have its own value number.
50 // OpSampledImage and OpImage must remain in the same basic block in which
51 // they are used, because of this we will assign each one it own value number.
52 if (!context()->IsCombinatorInstruction(inst)) {
53 value = TakeNextValueNumber();
54 id_to_value_[inst->result_id()] = value;
55 return value;
56 }
57
58 switch (inst->opcode()) {
59 case SpvOpSampledImage:
60 case SpvOpImage:
61 case SpvOpVariable:
62 value = TakeNextValueNumber();
63 id_to_value_[inst->result_id()] = value;
64 return value;
65 default:
66 break;
67 }
68
69 // If it is a load from memory that can be modified, we have to assume the
70 // memory has been modified, so we give it a new value number.
71 //
72 // Note that this test will also handle volatile loads because they are not
73 // read only. However, if this is ever relaxed because we analyze stores, we
74 // will have to add a new case for volatile loads.
75 if (inst->IsLoad() && !inst->IsReadOnlyLoad()) {
76 value = TakeNextValueNumber();
77 id_to_value_[inst->result_id()] = value;
78 return value;
79 }
80
81 // When we copy an object, the value numbers should be the same.
82 if (inst->opcode() == SpvOpCopyObject) {
83 value = GetValueNumber(inst->GetSingleWordInOperand(0));
84 if (value != 0) {
85 id_to_value_[inst->result_id()] = value;
86 return value;
87 }
88 }
89
90 // Phi nodes are a type of copy. If all of the inputs have the same value
91 // number, then we can assign the result of the phi the same value number.
92 if (inst->opcode() == SpvOpPhi) {
93 value = GetValueNumber(inst->GetSingleWordInOperand(0));
94 if (value != 0) {
95 for (uint32_t op = 2; op < inst->NumInOperands(); op += 2) {
96 if (value != GetValueNumber(inst->GetSingleWordInOperand(op))) {
97 value = 0;
98 break;
99 }
100 }
101 if (value != 0) {
102 id_to_value_[inst->result_id()] = value;
103 return value;
104 }
105 }
106 }
107
108 // Replace all of the operands by their value number. The sign bit will be
109 // set to distinguish between an id and a value number.
110 Instruction value_ins(context(), inst->opcode(), inst->type_id(),
111 inst->result_id(), {});
112 for (uint32_t o = 0; o < inst->NumInOperands(); ++o) {
113 const Operand& op = inst->GetInOperand(o);
114 if (spvIsIdType(op.type)) {
115 uint32_t id_value = op.words[0];
116 auto use_id_to_val = id_to_value_.find(id_value);
117 if (use_id_to_val != id_to_value_.end()) {
118 id_value = (1 << 31) | use_id_to_val->second;
119 }
120 value_ins.AddOperand(Operand(op.type, {id_value}));
121 } else {
122 value_ins.AddOperand(Operand(op.type, op.words));
123 }
124 }
125
126 // TODO: Implement a normal form for opcodes that commute like integer
127 // addition. This will let us know that a+b is the same value as b+a.
128
129 // Otherwise, we check if this value has been computed before.
130 auto value_iterator = instruction_to_value_.find(value_ins);
131 if (value_iterator != instruction_to_value_.end()) {
132 value = id_to_value_[value_iterator->first.result_id()];
133 id_to_value_[inst->result_id()] = value;
134 return value;
135 }
136
137 // If not, assign it a new value number.
138 value = TakeNextValueNumber();
139 id_to_value_[inst->result_id()] = value;
140 instruction_to_value_[value_ins] = value;
141 return value;
142 }
143
BuildDominatorTreeValueNumberTable()144 void ValueNumberTable::BuildDominatorTreeValueNumberTable() {
145 // First value number the headers.
146 for (auto& inst : context()->annotations()) {
147 if (inst.result_id() != 0) {
148 AssignValueNumber(&inst);
149 }
150 }
151
152 for (auto& inst : context()->capabilities()) {
153 if (inst.result_id() != 0) {
154 AssignValueNumber(&inst);
155 }
156 }
157
158 for (auto& inst : context()->types_values()) {
159 if (inst.result_id() != 0) {
160 AssignValueNumber(&inst);
161 }
162 }
163
164 for (auto& inst : context()->module()->ext_inst_imports()) {
165 if (inst.result_id() != 0) {
166 AssignValueNumber(&inst);
167 }
168 }
169
170 for (Function& func : *context()->module()) {
171 // For best results we want to traverse the code in reverse post order.
172 // This happens naturally because of the forward referencing rules.
173 for (BasicBlock& block : func) {
174 for (Instruction& inst : block) {
175 if (inst.result_id() != 0) {
176 AssignValueNumber(&inst);
177 }
178 }
179 }
180 }
181 }
182
operator ()(const Instruction & lhs,const Instruction & rhs) const183 bool ComputeSameValue::operator()(const Instruction& lhs,
184 const Instruction& rhs) const {
185 if (lhs.result_id() == 0 || rhs.result_id() == 0) {
186 return false;
187 }
188
189 if (lhs.opcode() != rhs.opcode()) {
190 return false;
191 }
192
193 if (lhs.type_id() != rhs.type_id()) {
194 return false;
195 }
196
197 if (lhs.NumInOperands() != rhs.NumInOperands()) {
198 return false;
199 }
200
201 for (uint32_t i = 0; i < lhs.NumInOperands(); ++i) {
202 if (lhs.GetInOperand(i) != rhs.GetInOperand(i)) {
203 return false;
204 }
205 }
206
207 return lhs.context()->get_decoration_mgr()->HaveTheSameDecorations(
208 lhs.result_id(), rhs.result_id());
209 }
210
operator ()(const Instruction & inst) const211 std::size_t ValueTableHash::operator()(const Instruction& inst) const {
212 // We hash the opcode and in-operands, not the result, because we want
213 // instructions that are the same except for the result to hash to the
214 // same value.
215 std::u32string h;
216 h.push_back(inst.opcode());
217 h.push_back(inst.type_id());
218 for (uint32_t i = 0; i < inst.NumInOperands(); ++i) {
219 const auto& opnd = inst.GetInOperand(i);
220 for (uint32_t word : opnd.words) {
221 h.push_back(word);
222 }
223 }
224 return std::hash<std::u32string>()(h);
225 }
226 } // namespace opt
227 } // namespace spvtools
228