| 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 |
// This file implements conditional constant propagation as described in |
| 16 |
// |
| 17 |
// Constant propagation with conditional branches, |
| 18 |
// Wegman and Zadeck, ACM TOPLAS 13(2):181-210. |
| 19 |
|
| 20 |
#include "source/opt/ccp_pass.h" |
| 21 |
|
| 22 |
#include <algorithm> |
| 23 |
#include <limits> |
| 24 |
|
| 25 |
#include "source/opt/fold.h" |
| 26 |
#include "source/opt/function.h" |
| 27 |
#include "source/opt/module.h" |
| 28 |
#include "source/opt/propagator.h" |
| 29 |
|
| 30 |
namespace spvtools { |
| 31 |
namespace opt { |
| 32 |
|
| 33 |
namespace { |
| 34 |
|
| 35 |
// This SSA id is never defined nor referenced in the IR. It is a special ID |
| 36 |
// which represents varying values. When an ID is found to have a varying |
| 37 |
// value, its entry in the |values_| table maps to kVaryingSSAId. |
| 38 |
const uint32_t kVaryingSSAId = std::numeric_limits<uint32_t>::max(); |
| 39 |
|
| 40 |
} // namespace |
| 41 |
|
| 42 |
bool CCPPass::IsVaryingValue(uint32_t id) const { return id == kVaryingSSAId; } |
| 43 |
|
| 44 |
SSAPropagator::PropStatus CCPPass::MarkInstructionVarying(Instruction* instr) { |
| 45 |
assert(instr->result_id() != 0 && |
| 46 |
"Instructions with no result cannot be marked varying."); |
| 47 |
values_[instr->result_id()] = kVaryingSSAId; |
| 48 |
return SSAPropagator::kVarying; |
| 49 |
} |
| 50 |
|
| 51 |
SSAPropagator::PropStatus CCPPass::VisitPhi(Instruction* phi) { |
| 52 |
uint32_t meet_val_id = 0; |
| 53 |
|
| 54 |
// Implement the lattice meet operation. The result of this Phi instruction is |
| 55 |
// interesting only if the meet operation over arguments coming through |
| 56 |
// executable edges yields the same constant value. |
| 57 |
for (uint32_t i = 2; i < phi->NumOperands(); i += 2) { |
| 58 |
if (!propagator_->IsPhiArgExecutable(phi, i)) { |
| 59 |
// Ignore arguments coming through non-executable edges. |
| 60 |
continue; |
| 61 |
} |
| 62 |
uint32_t phi_arg_id = phi->GetSingleWordOperand(i); |
| 63 |
auto it = values_.find(phi_arg_id); |
| 64 |
if (it != values_.end()) { |
| 65 |
// We found an argument with a constant value. Apply the meet operation |
| 66 |
// with the previous arguments. |
| 67 |
if (it->second == kVaryingSSAId) { |
| 68 |
// The "constant" value is actually a placeholder for varying. Return |
| 69 |
// varying for this phi. |
| 70 |
return MarkInstructionVarying(phi); |
| 71 |
} else if (meet_val_id == 0) { |
| 72 |
// This is the first argument we find. Initialize the result to its |
| 73 |
// constant value id. |
| 74 |
meet_val_id = it->second; |
| 75 |
} else if (it->second == meet_val_id) { |
| 76 |
// The argument is the same constant value already computed. Continue |
| 77 |
// looking. |
| 78 |
continue; |
| 79 |
} else { |
| 80 |
// We either found a varying value, or another constant value different |
| 81 |
// from the previous computed meet value. This Phi will never be |
| 82 |
// constant. |
| 83 |
return MarkInstructionVarying(phi); |
| 84 |
} |
| 85 |
} else { |
| 86 |
// The incoming value has no recorded value and is therefore not |
| 87 |
// interesting. A not interesting value joined with any other value is the |
| 88 |
// other value. |
| 89 |
continue; |
| 90 |
} |
| 91 |
} |
| 92 |
|
| 93 |
// If there are no incoming executable edges, the meet ID will still be 0. In |
| 94 |
// that case, return not interesting to evaluate the Phi node again. |
| 95 |
if (meet_val_id == 0) { |
| 96 |
return SSAPropagator::kNotInteresting; |
| 97 |
} |
| 98 |
|
| 99 |
// All the operands have the same constant value represented by |meet_val_id|. |
| 100 |
// Set the Phi's result to that value and declare it interesting. |
| 101 |
values_[phi->result_id()] = meet_val_id; |
| 102 |
return SSAPropagator::kInteresting; |
| 103 |
} |
| 104 |
|
| 105 |
SSAPropagator::PropStatus CCPPass::VisitAssignment(Instruction* instr) { |
| 106 |
assert(instr->result_id() != 0 && |
| 107 |
"Expecting an instruction that produces a result"); |
| 108 |
|
| 109 |
// If this is a copy operation, and the RHS is a known constant, assign its |
| 110 |
// value to the LHS. |
| 111 |
if (instr->opcode() == SpvOpCopyObject) { |
| 112 |
uint32_t rhs_id = instr->GetSingleWordInOperand(0); |
| 113 |
auto it = values_.find(rhs_id); |
| 114 |
if (it != values_.end()) { |
| 115 |
if (IsVaryingValue(it->second)) { |
| 116 |
return MarkInstructionVarying(instr); |
| 117 |
} else { |
| 118 |
values_[instr->result_id()] = it->second; |
| 119 |
return SSAPropagator::kInteresting; |
| 120 |
} |
| 121 |
} |
| 122 |
return SSAPropagator::kNotInteresting; |
| 123 |
} |
| 124 |
|
| 125 |
// Instructions with a RHS that cannot produce a constant are always varying. |
| 126 |
if (!instr->IsFoldable()) { |
| 127 |
return MarkInstructionVarying(instr); |
| 128 |
} |
| 129 |
|
| 130 |
// See if the RHS of the assignment folds into a constant value. |
| 131 |
auto map_func = [this](uint32_t id) { |
| 132 |
auto it = values_.find(id); |
| 133 |
if (it == values_.end() || IsVaryingValue(it->second)) { |
| 134 |
return id; |
| 135 |
} |
| 136 |
return it->second; |
| 137 |
}; |
| 138 |
Instruction* folded_inst = |
| 139 |
context()->get_instruction_folder().FoldInstructionToConstant(instr, |
| 140 |
map_func); |
| 141 |
|
| 142 |
if (folded_inst != nullptr) { |
| 143 |
// We do not want to change the body of the function by adding new |
| 144 |
// instructions. When folding we can only generate new constants. |
| 145 |
assert(folded_inst->IsConstant() && "CCP is only interested in constant."); |
| 146 |
values_[instr->result_id()] = folded_inst->result_id(); |
| 147 |
return SSAPropagator::kInteresting; |
| 148 |
} |
| 149 |
|
| 150 |
// Conservatively mark this instruction as varying if any input id is varying. |
| 151 |
if (!instr->WhileEachInId([this](uint32_t* op_id) { |
| 152 |
auto iter = values_.find(*op_id); |
| 153 |
if (iter != values_.end() && IsVaryingValue(iter->second)) return false; |
| 154 |
return true; |
| 155 |
})) { |
| 156 |
return MarkInstructionVarying(instr); |
| 157 |
} |
| 158 |
|
| 159 |
// If not, see if there is a least one unknown operand to the instruction. If |
| 160 |
// so, we might be able to fold it later. |
| 161 |
if (!instr->WhileEachInId([this](uint32_t* op_id) { |
| 162 |
auto it = values_.find(*op_id); |
| 163 |
if (it == values_.end()) return false; |
| 164 |
return true; |
| 165 |
})) { |
| 166 |
return SSAPropagator::kNotInteresting; |
| 167 |
} |
| 168 |
|
| 169 |
// Otherwise, we will never be able to fold this instruction, so mark it |
| 170 |
// varying. |
| 171 |
return MarkInstructionVarying(instr); |
| 172 |
} |
| 173 |
|
| 174 |
SSAPropagator::PropStatus CCPPass::VisitBranch(Instruction* instr, |
| 175 |
BasicBlock** dest_bb) const { |
| 176 |
assert(instr->IsBranch() && "Expected a branch instruction."); |
| 177 |
|
| 178 |
*dest_bb = nullptr; |
| 179 |
uint32_t dest_label = 0; |
| 180 |
if (instr->opcode() == SpvOpBranch) { |
| 181 |
// An unconditional jump always goes to its unique destination. |
| 182 |
dest_label = instr->GetSingleWordInOperand(0); |
| 183 |
} else if (instr->opcode() == SpvOpBranchConditional) { |
| 184 |
// For a conditional branch, determine whether the predicate selector has a |
| 185 |
// known value in |values_|. If it does, set the destination block |
| 186 |
// according to the selector's boolean value. |
| 187 |
uint32_t pred_id = instr->GetSingleWordOperand(0); |
| 188 |
auto it = values_.find(pred_id); |
| 189 |
if (it == values_.end() || IsVaryingValue(it->second)) { |
| 190 |
// The predicate has an unknown value, either branch could be taken. |
| 191 |
return SSAPropagator::kVarying; |
| 192 |
} |
| 193 |
|
| 194 |
// Get the constant value for the predicate selector from the value table. |
| 195 |
// Use it to decide which branch will be taken. |
| 196 |
uint32_t pred_val_id = it->second; |
| 197 |
const analysis::Constant* c = const_mgr_->FindDeclaredConstant(pred_val_id); |
| 198 |
assert(c && "Expected to find a constant declaration for a known value."); |
| 199 |
// Undef values should have returned as varying above. |
| 200 |
assert(c->AsBoolConstant() || c->AsNullConstant()); |
| 201 |
if (c->AsNullConstant()) { |
| 202 |
dest_label = instr->GetSingleWordOperand(2u); |
| 203 |
} else { |
| 204 |
const analysis::BoolConstant* val = c->AsBoolConstant(); |
| 205 |
dest_label = val->value() ? instr->GetSingleWordOperand(1) |
| 206 |
: instr->GetSingleWordOperand(2); |
| 207 |
} |
| 208 |
} else { |
| 209 |
// For an OpSwitch, extract the value taken by the switch selector and check |
| 210 |
// which of the target literals it matches. The branch associated with that |
| 211 |
// literal is the taken branch. |
| 212 |
assert(instr->opcode() == SpvOpSwitch); |
| 213 |
if (instr->GetOperand(0).words.size() != 1) { |
| 214 |
// If the selector is wider than 32-bits, return varying. TODO(dnovillo): |
| 215 |
// Add support for wider constants. |
| 216 |
return SSAPropagator::kVarying; |
| 217 |
} |
| 218 |
uint32_t select_id = instr->GetSingleWordOperand(0); |
| 219 |
auto it = values_.find(select_id); |
| 220 |
if (it == values_.end() || IsVaryingValue(it->second)) { |
| 221 |
// The selector has an unknown value, any of the branches could be taken. |
| 222 |
return SSAPropagator::kVarying; |
| 223 |
} |
| 224 |
|
| 225 |
// Get the constant value for the selector from the value table. Use it to |
| 226 |
// decide which branch will be taken. |
| 227 |
uint32_t select_val_id = it->second; |
| 228 |
const analysis::Constant* c = |
| 229 |
const_mgr_->FindDeclaredConstant(select_val_id); |
| 230 |
assert(c && "Expected to find a constant declaration for a known value."); |
| 231 |
// TODO: support 64-bit integer switches. |
| 232 |
uint32_t constant_cond = 0; |
| 233 |
if (const analysis::IntConstant* val = c->AsIntConstant()) { |
| 234 |
constant_cond = val->words()[0]; |
| 235 |
} else { |
| 236 |
// Undef values should have returned varying above. |
| 237 |
assert(c->AsNullConstant()); |
| 238 |
constant_cond = 0; |
| 239 |
} |
| 240 |
|
| 241 |
// Start assuming that the selector will take the default value; |
| 242 |
dest_label = instr->GetSingleWordOperand(1); |
| 243 |
for (uint32_t i = 2; i < instr->NumOperands(); i += 2) { |
| 244 |
if (constant_cond == instr->GetSingleWordOperand(i)) { |
| 245 |
dest_label = instr->GetSingleWordOperand(i + 1); |
| 246 |
break; |
| 247 |
} |
| 248 |
} |
| 249 |
} |
| 250 |
|
| 251 |
assert(dest_label && "Destination label should be set at this point."); |
| 252 |
*dest_bb = context()->cfg()->block(dest_label); |
| 253 |
return SSAPropagator::kInteresting; |
| 254 |
} |
| 255 |
|
| 256 |
SSAPropagator::PropStatus CCPPass::VisitInstruction(Instruction* instr, |
| 257 |
BasicBlock** dest_bb) { |
| 258 |
*dest_bb = nullptr; |
| 259 |
if (instr->opcode() == SpvOpPhi) { |
| 260 |
return VisitPhi(instr); |
| 261 |
} else if (instr->IsBranch()) { |
| 262 |
return VisitBranch(instr, dest_bb); |
| 263 |
} else if (instr->result_id()) { |
| 264 |
return VisitAssignment(instr); |
| 265 |
} |
| 266 |
return SSAPropagator::kVarying; |
| 267 |
} |
| 268 |
|
| 269 |
bool CCPPass::ReplaceValues() { |
| 270 |
// Even if we make no changes to the function's IR, propagation may have |
| 271 |
// created new constants. Even if those constants cannot be replaced in |
| 272 |
// the IR, the constant definition itself is a change. To reflect this, |
| 273 |
// we check whether the next ID to be given by the module is different than |
| 274 |
// the original bound ID. If that happens, new instructions were added to the |
| 275 |
// module during propagation. |
| 276 |
// |
| 277 |
// See https://github.com/KhronosGroup/SPIRV-Tools/issues/3636 and |
| 278 |
// https://github.com/KhronosGroup/SPIRV-Tools/issues/3991 for details. |
| 279 |
bool changed_ir = (context()->module()->IdBound() > original_id_bound_); |
| 280 |
|
| 281 |
for (const auto& it : values_) { |
| 282 |
uint32_t id = it.first; |
| 283 |
uint32_t cst_id = it.second; |
| 284 |
if (!IsVaryingValue(cst_id) && id != cst_id) { |
| 285 |
context()->KillNamesAndDecorates(id); |
| 286 |
changed_ir |= context()->ReplaceAllUsesWith(id, cst_id); |
| 287 |
} |
| 288 |
} |
| 289 |
|
| 290 |
return changed_ir; |
| 291 |
} |
| 292 |
|
| 293 |
bool CCPPass::PropagateConstants(Function* fp) { |
| 294 |
// Mark function parameters as varying. |
| 295 |
fp->ForEachParam([this](const Instruction* inst) { |
| 296 |
values_[inst->result_id()] = kVaryingSSAId; |
| 297 |
}); |
| 298 |
|
| 299 |
const auto visit_fn = [this](Instruction* instr, BasicBlock** dest_bb) { |
| 300 |
return VisitInstruction(instr, dest_bb); |
| 301 |
}; |
| 302 |
|
| 303 |
propagator_ = |
| 304 |
std::unique_ptr<SSAPropagator>(new SSAPropagator(context(), visit_fn)); |
| 305 |
|
| 306 |
if (propagator_->Run(fp)) { |
| 307 |
return ReplaceValues(); |
| 308 |
} |
| 309 |
|
| 310 |
return false; |
| 311 |
} |
| 312 |
|
| 313 |
void CCPPass::Initialize() { |
| 314 |
const_mgr_ = context()->get_constant_mgr(); |
| 315 |
|
| 316 |
// Populate the constant table with values from constant declarations in the |
| 317 |
// module. The values of each OpConstant declaration is the identity |
| 318 |
// assignment (i.e., each constant is its own value). |
| 319 |
for (const auto& inst : get_module()->types_values()) { |
| 320 |
// Record compile time constant ids. Treat all other global values as |
| 321 |
// varying. |
| 322 |
if (inst.IsConstant()) { |
| 323 |
values_[inst.result_id()] = inst.result_id(); |
| 324 |
} else { |
| 325 |
values_[inst.result_id()] = kVaryingSSAId; |
| 326 |
} |
| 327 |
} |
| 328 |
|
| 329 |
original_id_bound_ = context()->module()->IdBound(); |
| 330 |
} |
| 331 |
|
| 332 |
Pass::Status CCPPass::Process() { |
| 333 |
Initialize(); |
| 334 |
|
| 335 |
// Process all entry point functions. |
| 336 |
ProcessFunction pfn = [this](Function* fp) { return PropagateConstants(fp); }; |
| 337 |
bool modified = context()->ProcessReachableCallTree(pfn); |
| 338 |
return modified ? Pass::Status::SuccessWithChange |
| 339 |
: Pass::Status::SuccessWithoutChange; |
| 340 |
} |
| 341 |
|
| 342 |
} // namespace opt |
| 343 |
} // namespace spvtools |