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
22namespace spvtools {
23namespace opt {
24
25uint32_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
37uint32_t ValueNumberTable::GetValueNumber(uint32_t id) const {
38 return GetValueNumber(context()->get_def_use_mgr()->GetDef(id));
39}
40
41uint32_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 analysis::DecorationManager* dec_mgr = context()->get_decoration_mgr();
82
83 // When we copy an object, the value numbers should be the same.
84 if (inst->opcode() == SpvOpCopyObject &&
85 dec_mgr->HaveTheSameDecorations(inst->result_id(),
86 inst->GetSingleWordInOperand(0))) {
87 value = GetValueNumber(inst->GetSingleWordInOperand(0));
88 if (value != 0) {
89 id_to_value_[inst->result_id()] = value;
90 return value;
91 }
92 }
93
94 // Phi nodes are a type of copy. If all of the inputs have the same value
95 // number, then we can assign the result of the phi the same value number.
96 if (inst->opcode() == SpvOpPhi && inst->NumInOperands() > 0 &&
97 dec_mgr->HaveTheSameDecorations(inst->result_id(),
98 inst->GetSingleWordInOperand(0))) {
99 value = GetValueNumber(inst->GetSingleWordInOperand(0));
100 if (value != 0) {
101 for (uint32_t op = 2; op < inst->NumInOperands(); op += 2) {
102 if (value != GetValueNumber(inst->GetSingleWordInOperand(op))) {
103 value = 0;
104 break;
105 }
106 }
107 if (value != 0) {
108 id_to_value_[inst->result_id()] = value;
109 return value;
110 }
111 }
112 }
113
114 // Replace all of the operands by their value number. The sign bit will be
115 // set to distinguish between an id and a value number.
116 Instruction value_ins(context(), inst->opcode(), inst->type_id(),
117 inst->result_id(), {});
118 for (uint32_t o = 0; o < inst->NumInOperands(); ++o) {
119 const Operand& op = inst->GetInOperand(o);
120 if (spvIsIdType(op.type)) {
121 uint32_t id_value = op.words[0];
122 auto use_id_to_val = id_to_value_.find(id_value);
123 if (use_id_to_val != id_to_value_.end()) {
124 id_value = (1 << 31) | use_id_to_val->second;
125 }
126 value_ins.AddOperand(Operand(op.type, {id_value}));
127 } else {
128 value_ins.AddOperand(Operand(op.type, op.words));
129 }
130 }
131
132 // TODO: Implement a normal form for opcodes that commute like integer
133 // addition. This will let us know that a+b is the same value as b+a.
134
135 // Otherwise, we check if this value has been computed before.
136 auto value_iterator = instruction_to_value_.find(value_ins);
137 if (value_iterator != instruction_to_value_.end()) {
138 value = id_to_value_[value_iterator->first.result_id()];
139 id_to_value_[inst->result_id()] = value;
140 return value;
141 }
142
143 // If not, assign it a new value number.
144 value = TakeNextValueNumber();
145 id_to_value_[inst->result_id()] = value;
146 instruction_to_value_[value_ins] = value;
147 return value;
148}
149
150void ValueNumberTable::BuildDominatorTreeValueNumberTable() {
151 // First value number the headers.
152 for (auto& inst : context()->annotations()) {
153 if (inst.result_id() != 0) {
154 AssignValueNumber(&inst);
155 }
156 }
157
158 for (auto& inst : context()->capabilities()) {
159 if (inst.result_id() != 0) {
160 AssignValueNumber(&inst);
161 }
162 }
163
164 for (auto& inst : context()->types_values()) {
165 if (inst.result_id() != 0) {
166 AssignValueNumber(&inst);
167 }
168 }
169
170 for (auto& inst : context()->module()->ext_inst_imports()) {
171 if (inst.result_id() != 0) {
172 AssignValueNumber(&inst);
173 }
174 }
175
176 for (Function& func : *context()->module()) {
177 // For best results we want to traverse the code in reverse post order.
178 // This happens naturally because of the forward referencing rules.
179 for (BasicBlock& block : func) {
180 for (Instruction& inst : block) {
181 if (inst.result_id() != 0) {
182 AssignValueNumber(&inst);
183 }
184 }
185 }
186 }
187}
188
189bool ComputeSameValue::operator()(const Instruction& lhs,
190 const Instruction& rhs) const {
191 if (lhs.result_id() == 0 || rhs.result_id() == 0) {
192 return false;
193 }
194
195 if (lhs.opcode() != rhs.opcode()) {
196 return false;
197 }
198
199 if (lhs.type_id() != rhs.type_id()) {
200 return false;
201 }
202
203 if (lhs.NumInOperands() != rhs.NumInOperands()) {
204 return false;
205 }
206
207 for (uint32_t i = 0; i < lhs.NumInOperands(); ++i) {
208 if (lhs.GetInOperand(i) != rhs.GetInOperand(i)) {
209 return false;
210 }
211 }
212
213 return lhs.context()->get_decoration_mgr()->HaveTheSameDecorations(
214 lhs.result_id(), rhs.result_id());
215}
216
217std::size_t ValueTableHash::operator()(const Instruction& inst) const {
218 // We hash the opcode and in-operands, not the result, because we want
219 // instructions that are the same except for the result to hash to the
220 // same value.
221 std::u32string h;
222 h.push_back(inst.opcode());
223 h.push_back(inst.type_id());
224 for (uint32_t i = 0; i < inst.NumInOperands(); ++i) {
225 const auto& opnd = inst.GetInOperand(i);
226 for (uint32_t word : opnd.words) {
227 h.push_back(word);
228 }
229 }
230 return std::hash<std::u32string>()(h);
231}
232} // namespace opt
233} // namespace spvtools
234