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