| 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 |
#ifndef SOURCE_OPT_PROPAGATOR_H_ |
| 16 |
#define SOURCE_OPT_PROPAGATOR_H_ |
| 17 |
|
| 18 |
#include <functional> |
| 19 |
#include <queue> |
| 20 |
#include <set> |
| 21 |
#include <unordered_map> |
| 22 |
#include <unordered_set> |
| 23 |
#include <utility> |
| 24 |
#include <vector> |
| 25 |
|
| 26 |
#include "source/opt/ir_context.h" |
| 27 |
#include "source/opt/module.h" |
| 28 |
|
| 29 |
namespace spvtools { |
| 30 |
namespace opt { |
| 31 |
|
| 32 |
// Represents a CFG control edge. |
| 33 |
struct Edge { |
| 34 |
Edge(BasicBlock* b1, BasicBlock* b2) : source(b1), dest(b2) { |
| 35 |
assert(source && "CFG edges cannot have a null source block."); |
| 36 |
assert(dest && "CFG edges cannot have a null destination block."); |
| 37 |
} |
| 38 |
BasicBlock* source; |
| 39 |
BasicBlock* dest; |
| 40 |
bool operator<(const Edge& o) const { |
| 41 |
return std::make_pair(source->id(), dest->id()) < |
| 42 |
std::make_pair(o.source->id(), o.dest->id()); |
| 43 |
} |
| 44 |
}; |
| 45 |
|
| 46 |
// This class implements a generic value propagation algorithm based on the |
| 47 |
// conditional constant propagation algorithm proposed in |
| 48 |
// |
| 49 |
// Constant propagation with conditional branches, |
| 50 |
// Wegman and Zadeck, ACM TOPLAS 13(2):181-210. |
| 51 |
// |
| 52 |
// A Propagation Engine for GCC |
| 53 |
// Diego Novillo, GCC Summit 2005 |
| 54 |
// http://ols.fedoraproject.org/GCC/Reprints-2005/novillo-Reprint.pdf |
| 55 |
// |
| 56 |
// The purpose of this implementation is to act as a common framework for any |
| 57 |
// transformation that needs to propagate values from statements producing new |
| 58 |
// values to statements using those values. Simulation proceeds as follows: |
| 59 |
// |
| 60 |
// 1- Initially, all edges of the CFG are marked not executable and the CFG |
| 61 |
// worklist is seeded with all the statements in the entry basic block. |
| 62 |
// |
| 63 |
// 2- Every instruction I is simulated by calling a pass-provided function |
| 64 |
// |visit_fn|. This function is responsible for three things: |
| 65 |
// |
| 66 |
// (a) Keep a value table of interesting values. This table maps SSA IDs to |
| 67 |
// their values. For instance, when implementing constant propagation, |
| 68 |
// given a store operation 'OpStore %f %int_3', |visit_fn| should assign |
| 69 |
// the value 3 to the table slot for %f. |
| 70 |
// |
| 71 |
// In general, |visit_fn| will need to use the value table to replace its |
| 72 |
// operands, fold the result and decide whether a new value needs to be |
| 73 |
// stored in the table. |visit_fn| should only create a new mapping in |
| 74 |
// the value table if all the operands in the instruction are known and |
| 75 |
// present in the value table. |
| 76 |
// |
| 77 |
// (b) Return a status indicator to direct the propagator logic. Once the |
| 78 |
// instruction is simulated, the propagator needs to know whether this |
| 79 |
// instruction produced something interesting. This is indicated via |
| 80 |
// |visit_fn|'s return value: |
| 81 |
// |
| 82 |
// SSAPropagator::kNotInteresting: Instruction I produces nothing of |
| 83 |
// interest and does not affect any of the work lists. The |
| 84 |
// propagator will visit the statement again if any of its operands |
| 85 |
// produce an interesting value in the future. |
| 86 |
// |
| 87 |
// |visit_fn| should always return this value when it is not sure |
| 88 |
// whether the instruction will produce an interesting value in the |
| 89 |
// future or not. For instance, for constant propagation, an OpIAdd |
| 90 |
// instruction may produce a constant if its two operands are |
| 91 |
// constant, but the first time we visit the instruction, we still |
| 92 |
// may not have its operands in the value table. |
| 93 |
// |
| 94 |
// SSAPropagator::kVarying: The value produced by I cannot be determined |
| 95 |
// at compile time. Further simulation of I is not required. The |
| 96 |
// propagator will not visit this instruction again. Additionally, |
| 97 |
// the propagator will add all the instructions at the end of SSA |
| 98 |
// def-use edges to be simulated again. |
| 99 |
// |
| 100 |
// If I is a basic block terminator, it will mark all outgoing edges |
| 101 |
// as executable so they are traversed one more time. Eventually |
| 102 |
// the kVarying attribute will be spread out to all the data and |
| 103 |
// control dependents for I. |
| 104 |
// |
| 105 |
// It is important for propagation to use kVarying as a bottom value |
| 106 |
// for the propagation lattice. It should never be possible for an |
| 107 |
// instruction to return kVarying once and kInteresting on a second |
| 108 |
// visit. Otherwise, propagation would not stabilize. |
| 109 |
// |
| 110 |
// SSAPropagator::kInteresting: Instruction I produces a value that can |
| 111 |
// be computed at compile time. In this case, |visit_fn| should |
| 112 |
// create a new mapping between I's result ID and the produced |
| 113 |
// value. Much like the kNotInteresting case, the propagator will |
| 114 |
// visit this instruction again if any of its operands changes. |
| 115 |
// This is useful when the statement changes from one interesting |
| 116 |
// state to another. |
| 117 |
// |
| 118 |
// (c) For conditional branches, |visit_fn| may decide which edge to take out |
| 119 |
// of I's basic block. For example, if the operand for an OpSwitch is |
| 120 |
// known to take a specific constant value, |visit_fn| should figure out |
| 121 |
// the destination basic block and pass it back by setting the second |
| 122 |
// argument to |visit_fn|. |
| 123 |
// |
| 124 |
// At the end of propagation, values in the value table are guaranteed to be |
| 125 |
// stable and can be replaced in the IR. |
| 126 |
// |
| 127 |
// 3- The propagator keeps two work queues. Instructions are only added to |
| 128 |
// these queues if they produce an interesting or varying value. None of this |
| 129 |
// should be handled by |visit_fn|. The propagator keeps track of this |
| 130 |
// automatically (see SSAPropagator::Simulate for implementation). |
| 131 |
// |
| 132 |
// CFG blocks: contains the queue of blocks to be simulated. |
| 133 |
// Blocks are added to this queue if their incoming edges are |
| 134 |
// executable. |
| 135 |
// |
| 136 |
// SSA Edges: An SSA edge is a def-use edge between a value-producing |
| 137 |
// instruction and its use instruction. The SSA edges list |
| 138 |
// contains the statements at the end of a def-use edge that need |
| 139 |
// to be re-visited when an instruction produces a kVarying or |
| 140 |
// kInteresting result. |
| 141 |
// |
| 142 |
// 4- Simulation terminates when all work queues are drained. |
| 143 |
// |
| 144 |
// |
| 145 |
// EXAMPLE: Basic constant store propagator. |
| 146 |
// |
| 147 |
// Suppose we want to propagate all constant assignments of the form "OpStore |
| 148 |
// %id %cst" where "%id" is some variable and "%cst" an OpConstant. The |
| 149 |
// following code builds a table |values| where every id that was assigned a |
| 150 |
// constant value is mapped to the constant value it was assigned. |
| 151 |
// |
| 152 |
// auto ctx = BuildModule(...); |
| 153 |
// std::map<uint32_t, uint32_t> values; |
| 154 |
// const auto visit_fn = [&ctx, &values](Instruction* instr, |
| 155 |
// BasicBlock** dest_bb) { |
| 156 |
// if (instr->opcode() == SpvOpStore) { |
| 157 |
// uint32_t rhs_id = instr->GetSingleWordOperand(1); |
| 158 |
// Instruction* rhs_def = ctx->get_def_use_mgr()->GetDef(rhs_id); |
| 159 |
// if (rhs_def->opcode() == SpvOpConstant) { |
| 160 |
// uint32_t val = rhs_def->GetSingleWordOperand(2); |
| 161 |
// values[rhs_id] = val; |
| 162 |
// return SSAPropagator::kInteresting; |
| 163 |
// } |
| 164 |
// } |
| 165 |
// return SSAPropagator::kVarying; |
| 166 |
// }; |
| 167 |
// SSAPropagator propagator(ctx.get(), &cfg, visit_fn); |
| 168 |
// propagator.Run(&fn); |
| 169 |
// |
| 170 |
// Given the code: |
| 171 |
// |
| 172 |
// %int_4 = OpConstant %int 4 |
| 173 |
// %int_3 = OpConstant %int 3 |
| 174 |
// %int_1 = OpConstant %int 1 |
| 175 |
// OpStore %x %int_4 |
| 176 |
// OpStore %y %int_3 |
| 177 |
// OpStore %z %int_1 |
| 178 |
// |
| 179 |
// After SSAPropagator::Run returns, the |values| map will contain the entries: |
| 180 |
// values[%x] = 4, values[%y] = 3, and, values[%z] = 1. |
| 181 |
class SSAPropagator { |
| 182 |
public: |
| 183 |
// Lattice values used for propagation. See class documentation for |
| 184 |
// a description. |
| 185 |
enum PropStatus { kNotInteresting, kInteresting, kVarying }; |
| 186 |
|
| 187 |
using VisitFunction = std::function<PropStatus(Instruction*, BasicBlock**)>; |
| 188 |
|
| 189 |
SSAPropagator(IRContext* context, const VisitFunction& visit_fn) |
| 190 |
: ctx_(context), visit_fn_(visit_fn) {} |
| 191 |
|
| 192 |
// Runs the propagator on function |fn|. Returns true if changes were made to |
| 193 |
// the function. Otherwise, it returns false. |
| 194 |
bool Run(Function* fn); |
| 195 |
|
| 196 |
// Returns true if the |i|th argument for |phi| comes through a CFG edge that |
| 197 |
// has been marked executable. |i| should be an index value accepted by |
| 198 |
// Instruction::GetSingleWordOperand. |
| 199 |
bool IsPhiArgExecutable(Instruction* phi, uint32_t i) const; |
| 200 |
|
| 201 |
// Returns true if |inst| has a recorded status. This will be true once |inst| |
| 202 |
// has been simulated once. |
| 203 |
bool HasStatus(Instruction* inst) const { return statuses_.count(inst); } |
| 204 |
|
| 205 |
// Returns the current propagation status of |inst|. Assumes |
| 206 |
// |HasStatus(inst)| returns true. |
| 207 |
PropStatus Status(Instruction* inst) const { |
| 208 |
return statuses_.find(inst)->second; |
| 209 |
} |
| 210 |
|
| 211 |
// Records the propagation status |status| for |inst|. Returns true if the |
| 212 |
// status for |inst| has changed or set was set for the first time. |
| 213 |
bool SetStatus(Instruction* inst, PropStatus status); |
| 214 |
|
| 215 |
private: |
| 216 |
// Initialize processing. |
| 217 |
void Initialize(Function* fn); |
| 218 |
|
| 219 |
// Simulate the execution |block| by calling |visit_fn_| on every instruction |
| 220 |
// in it. |
| 221 |
bool Simulate(BasicBlock* block); |
| 222 |
|
| 223 |
// Simulate the execution of |instr| by replacing all the known values in |
| 224 |
// every operand and determining whether the result is interesting for |
| 225 |
// propagation. This invokes the callback function |visit_fn_| to determine |
| 226 |
// the value computed by |instr|. |
| 227 |
bool Simulate(Instruction* instr); |
| 228 |
|
| 229 |
// Returns true if |instr| should be simulated again. |
| 230 |
bool ShouldSimulateAgain(Instruction* instr) const { |
| 231 |
return do_not_simulate_.find(instr) == do_not_simulate_.end(); |
| 232 |
} |
| 233 |
|
| 234 |
// Add |instr| to the set of instructions not to simulate again. |
| 235 |
void DontSimulateAgain(Instruction* instr) { do_not_simulate_.insert(instr); } |
| 236 |
|
| 237 |
// Returns true if |block| has been simulated already. |
| 238 |
bool BlockHasBeenSimulated(BasicBlock* block) const { |
| 239 |
return simulated_blocks_.find(block) != simulated_blocks_.end(); |
| 240 |
} |
| 241 |
|
| 242 |
// Marks block |block| as simulated. |
| 243 |
void MarkBlockSimulated(BasicBlock* block) { |
| 244 |
simulated_blocks_.insert(block); |
| 245 |
} |
| 246 |
|
| 247 |
// Marks |edge| as executable. Returns false if the edge was already marked |
| 248 |
// as executable. |
| 249 |
bool MarkEdgeExecutable(const Edge& edge) { |
| 250 |
return executable_edges_.insert(edge).second; |
| 251 |
} |
| 252 |
|
| 253 |
// Returns true if |edge| has been marked as executable. |
| 254 |
bool IsEdgeExecutable(const Edge& edge) const { |
| 255 |
return executable_edges_.find(edge) != executable_edges_.end(); |
| 256 |
} |
| 257 |
|
| 258 |
// Returns a pointer to the def-use manager for |ctx_|. |
| 259 |
analysis::DefUseManager* get_def_use_mgr() const { |
| 260 |
return ctx_->get_def_use_mgr(); |
| 261 |
} |
| 262 |
|
| 263 |
// If the CFG edge |e| has not been executed, this function adds |e|'s |
| 264 |
// destination block to the work list. |
| 265 |
void AddControlEdge(const Edge& e); |
| 266 |
|
| 267 |
// Adds all the instructions that use the result of |instr| to the SSA edges |
| 268 |
// work list. If |instr| produces no result id, this does nothing. |
| 269 |
void AddSSAEdges(Instruction* instr); |
| 270 |
|
| 271 |
// IR context to use. |
| 272 |
IRContext* ctx_; |
| 273 |
|
| 274 |
// Function that visits instructions during simulation. The output of this |
| 275 |
// function is used to determine if the simulated instruction produced a value |
| 276 |
// interesting for propagation. The function is responsible for keeping |
| 277 |
// track of interesting values by storing them in some user-provided map. |
| 278 |
VisitFunction visit_fn_; |
| 279 |
|
| 280 |
// SSA def-use edges to traverse. Each entry is a destination statement for an |
| 281 |
// SSA def-use edge as returned by |def_use_manager_|. |
| 282 |
std::queue<Instruction*> ssa_edge_uses_; |
| 283 |
|
| 284 |
// Blocks to simulate. |
| 285 |
std::queue<BasicBlock*> blocks_; |
| 286 |
|
| 287 |
// Blocks simulated during propagation. |
| 288 |
std::unordered_set<BasicBlock*> simulated_blocks_; |
| 289 |
|
| 290 |
// Set of instructions that should not be simulated again because they have |
| 291 |
// been found to be in the kVarying state. |
| 292 |
std::unordered_set<Instruction*> do_not_simulate_; |
| 293 |
|
| 294 |
// Map between a basic block and its predecessor edges. |
| 295 |
// TODO(dnovillo): Move this to CFG and always build them. Alternately, |
| 296 |
// move it to IRContext and build CFG preds/succs on-demand. |
| 297 |
std::unordered_map<BasicBlock*, std::vector<Edge>> bb_preds_; |
| 298 |
|
| 299 |
// Map between a basic block and its successor edges. |
| 300 |
// TODO(dnovillo): Move this to CFG and always build them. Alternately, |
| 301 |
// move it to IRContext and build CFG preds/succs on-demand. |
| 302 |
std::unordered_map<BasicBlock*, std::vector<Edge>> bb_succs_; |
| 303 |
|
| 304 |
// Set of executable CFG edges. |
| 305 |
std::set<Edge> executable_edges_; |
| 306 |
|
| 307 |
// Tracks instruction propagation status. |
| 308 |
std::unordered_map<Instruction*, SSAPropagator::PropStatus> statuses_; |
| 309 |
}; |
| 310 |
|
| 311 |
std::ostream& operator<<(std::ostream& str, |
| 312 |
const SSAPropagator::PropStatus& status); |
| 313 |
|
| 314 |
} // namespace opt |
| 315 |
} // namespace spvtools |
| 316 |
|
| 317 |
#endif // SOURCE_OPT_PROPAGATOR_H_ |