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
30namespace spvtools {
31namespace opt {
32
33namespace {
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.
38const uint32_t kVaryingSSAId = std::numeric_limits<uint32_t>::max();
39
40} // namespace
41
42bool CCPPass::IsVaryingValue(uint32_t id) const { return id == kVaryingSSAId; }
43
44SSAPropagator::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
51SSAPropagator::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
105SSAPropagator::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 if (folded_inst != nullptr) {
142 // We do not want to change the body of the function by adding new
143 // instructions. When folding we can only generate new constants.
144 assert(folded_inst->IsConstant() && "CCP is only interested in constant.");
145 values_[instr->result_id()] = folded_inst->result_id();
146 return SSAPropagator::kInteresting;
147 }
148
149 // Conservatively mark this instruction as varying if any input id is varying.
150 if (!instr->WhileEachInId([this](uint32_t* op_id) {
151 auto iter = values_.find(*op_id);
152 if (iter != values_.end() && IsVaryingValue(iter->second)) return false;
153 return true;
154 })) {
155 return MarkInstructionVarying(instr);
156 }
157
158 // If not, see if there is a least one unknown operand to the instruction. If
159 // so, we might be able to fold it later.
160 if (!instr->WhileEachInId([this](uint32_t* op_id) {
161 auto it = values_.find(*op_id);
162 if (it == values_.end()) return false;
163 return true;
164 })) {
165 return SSAPropagator::kNotInteresting;
166 }
167
168 // Otherwise, we will never be able to fold this instruction, so mark it
169 // varying.
170 return MarkInstructionVarying(instr);
171}
172
173SSAPropagator::PropStatus CCPPass::VisitBranch(Instruction* instr,
174 BasicBlock** dest_bb) const {
175 assert(instr->IsBranch() && "Expected a branch instruction.");
176
177 *dest_bb = nullptr;
178 uint32_t dest_label = 0;
179 if (instr->opcode() == SpvOpBranch) {
180 // An unconditional jump always goes to its unique destination.
181 dest_label = instr->GetSingleWordInOperand(0);
182 } else if (instr->opcode() == SpvOpBranchConditional) {
183 // For a conditional branch, determine whether the predicate selector has a
184 // known value in |values_|. If it does, set the destination block
185 // according to the selector's boolean value.
186 uint32_t pred_id = instr->GetSingleWordOperand(0);
187 auto it = values_.find(pred_id);
188 if (it == values_.end() || IsVaryingValue(it->second)) {
189 // The predicate has an unknown value, either branch could be taken.
190 return SSAPropagator::kVarying;
191 }
192
193 // Get the constant value for the predicate selector from the value table.
194 // Use it to decide which branch will be taken.
195 uint32_t pred_val_id = it->second;
196 const analysis::Constant* c = const_mgr_->FindDeclaredConstant(pred_val_id);
197 assert(c && "Expected to find a constant declaration for a known value.");
198 // Undef values should have returned as varying above.
199 assert(c->AsBoolConstant() || c->AsNullConstant());
200 if (c->AsNullConstant()) {
201 dest_label = instr->GetSingleWordOperand(2u);
202 } else {
203 const analysis::BoolConstant* val = c->AsBoolConstant();
204 dest_label = val->value() ? instr->GetSingleWordOperand(1)
205 : instr->GetSingleWordOperand(2);
206 }
207 } else {
208 // For an OpSwitch, extract the value taken by the switch selector and check
209 // which of the target literals it matches. The branch associated with that
210 // literal is the taken branch.
211 assert(instr->opcode() == SpvOpSwitch);
212 if (instr->GetOperand(0).words.size() != 1) {
213 // If the selector is wider than 32-bits, return varying. TODO(dnovillo):
214 // Add support for wider constants.
215 return SSAPropagator::kVarying;
216 }
217 uint32_t select_id = instr->GetSingleWordOperand(0);
218 auto it = values_.find(select_id);
219 if (it == values_.end() || IsVaryingValue(it->second)) {
220 // The selector has an unknown value, any of the branches could be taken.
221 return SSAPropagator::kVarying;
222 }
223
224 // Get the constant value for the selector from the value table. Use it to
225 // decide which branch will be taken.
226 uint32_t select_val_id = it->second;
227 const analysis::Constant* c =
228 const_mgr_->FindDeclaredConstant(select_val_id);
229 assert(c && "Expected to find a constant declaration for a known value.");
230 // TODO: support 64-bit integer switches.
231 uint32_t constant_cond = 0;
232 if (const analysis::IntConstant* val = c->AsIntConstant()) {
233 constant_cond = val->words()[0];
234 } else {
235 // Undef values should have returned varying above.
236 assert(c->AsNullConstant());
237 constant_cond = 0;
238 }
239
240 // Start assuming that the selector will take the default value;
241 dest_label = instr->GetSingleWordOperand(1);
242 for (uint32_t i = 2; i < instr->NumOperands(); i += 2) {
243 if (constant_cond == instr->GetSingleWordOperand(i)) {
244 dest_label = instr->GetSingleWordOperand(i + 1);
245 break;
246 }
247 }
248 }
249
250 assert(dest_label && "Destination label should be set at this point.");
251 *dest_bb = context()->cfg()->block(dest_label);
252 return SSAPropagator::kInteresting;
253}
254
255SSAPropagator::PropStatus CCPPass::VisitInstruction(Instruction* instr,
256 BasicBlock** dest_bb) {
257 *dest_bb = nullptr;
258 if (instr->opcode() == SpvOpPhi) {
259 return VisitPhi(instr);
260 } else if (instr->IsBranch()) {
261 return VisitBranch(instr, dest_bb);
262 } else if (instr->result_id()) {
263 return VisitAssignment(instr);
264 }
265 return SSAPropagator::kVarying;
266}
267
268bool CCPPass::ReplaceValues() {
269 bool retval = false;
270 for (const auto& it : values_) {
271 uint32_t id = it.first;
272 uint32_t cst_id = it.second;
273 if (!IsVaryingValue(cst_id) && id != cst_id) {
274 context()->KillNamesAndDecorates(id);
275 retval |= context()->ReplaceAllUsesWith(id, cst_id);
276 }
277 }
278 return retval;
279}
280
281bool CCPPass::PropagateConstants(Function* fp) {
282 // Mark function parameters as varying.
283 fp->ForEachParam([this](const Instruction* inst) {
284 values_[inst->result_id()] = kVaryingSSAId;
285 });
286
287 const auto visit_fn = [this](Instruction* instr, BasicBlock** dest_bb) {
288 return VisitInstruction(instr, dest_bb);
289 };
290
291 propagator_ =
292 std::unique_ptr<SSAPropagator>(new SSAPropagator(context(), visit_fn));
293
294 if (propagator_->Run(fp)) {
295 return ReplaceValues();
296 }
297
298 return false;
299}
300
301void CCPPass::Initialize() {
302 const_mgr_ = context()->get_constant_mgr();
303
304 // Populate the constant table with values from constant declarations in the
305 // module. The values of each OpConstant declaration is the identity
306 // assignment (i.e., each constant is its own value).
307 for (const auto& inst : get_module()->types_values()) {
308 // Record compile time constant ids. Treat all other global values as
309 // varying.
310 if (inst.IsConstant()) {
311 values_[inst.result_id()] = inst.result_id();
312 } else {
313 values_[inst.result_id()] = kVaryingSSAId;
314 }
315 }
316}
317
318Pass::Status CCPPass::Process() {
319 Initialize();
320
321 // Process all entry point functions.
322 ProcessFunction pfn = [this](Function* fp) { return PropagateConstants(fp); };
323 bool modified = context()->ProcessReachableCallTree(pfn);
324 return modified ? Pass::Status::SuccessWithChange
325 : Pass::Status::SuccessWithoutChange;
326}
327
328} // namespace opt
329} // namespace spvtools
330