| 1 |
// Copyright (c) 2018 Google LLC. |
| 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_SSA_REWRITE_PASS_H_ |
| 16 |
#define SOURCE_OPT_SSA_REWRITE_PASS_H_ |
| 17 |
|
| 18 |
#include <queue> |
| 19 |
#include <string> |
| 20 |
#include <unordered_map> |
| 21 |
#include <unordered_set> |
| 22 |
#include <utility> |
| 23 |
#include <vector> |
| 24 |
|
| 25 |
#include "source/opt/basic_block.h" |
| 26 |
#include "source/opt/ir_context.h" |
| 27 |
#include "source/opt/mem_pass.h" |
| 28 |
|
| 29 |
namespace spvtools { |
| 30 |
namespace opt { |
| 31 |
|
| 32 |
// Utility class for passes that need to rewrite a function into SSA. This |
| 33 |
// converts load/store operations on function-local variables into SSA IDs, |
| 34 |
// which allows them to be the target of optimizing transformations. |
| 35 |
// |
| 36 |
// Store and load operations to these variables are converted into |
| 37 |
// operations on SSA IDs. Phi instructions are added when needed. See the |
| 38 |
// SSA construction paper for algorithmic details |
| 39 |
// (https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6) |
| 40 |
class SSARewriter { |
| 41 |
public: |
| 42 |
SSARewriter(MemPass* pass) : pass_(pass) {} |
| 43 |
|
| 44 |
// Rewrites SSA-target variables in function |fp| into SSA. This is the |
| 45 |
// entry point for the SSA rewrite algorithm. SSA-target variables are |
| 46 |
// locally defined variables that meet the criteria set by IsSSATargetVar. |
| 47 |
// |
| 48 |
// Returns whether the function was modified or not, and whether or not the |
| 49 |
// rewrite was successful. |
| 50 |
Pass::Status RewriteFunctionIntoSSA(Function* fp); |
| 51 |
|
| 52 |
private: |
| 53 |
class PhiCandidate { |
| 54 |
public: |
| 55 |
explicit PhiCandidate(uint32_t var, uint32_t result, BasicBlock* block) |
| 56 |
: var_id_(var), |
| 57 |
result_id_(result), |
| 58 |
bb_(block), |
| 59 |
phi_args_(), |
| 60 |
copy_of_(0), |
| 61 |
is_complete_(false), |
| 62 |
users_() {} |
| 63 |
|
| 64 |
uint32_t var_id() const { return var_id_; } |
| 65 |
uint32_t result_id() const { return result_id_; } |
| 66 |
BasicBlock* bb() const { return bb_; } |
| 67 |
std::vector<uint32_t>& phi_args() { return phi_args_; } |
| 68 |
const std::vector<uint32_t>& phi_args() const { return phi_args_; } |
| 69 |
uint32_t copy_of() const { return copy_of_; } |
| 70 |
bool is_complete() const { return is_complete_; } |
| 71 |
std::vector<uint32_t>& users() { return users_; } |
| 72 |
const std::vector<uint32_t>& users() const { return users_; } |
| 73 |
|
| 74 |
// Marks this phi candidate as a trivial copy of |orig_id|. |
| 75 |
void MarkCopyOf(uint32_t orig_id) { copy_of_ = orig_id; } |
| 76 |
|
| 77 |
// Marks this phi candidate as incomplete. |
| 78 |
void MarkIncomplete() { is_complete_ = false; } |
| 79 |
|
| 80 |
// Marks this phi candidate as complete. |
| 81 |
void MarkComplete() { is_complete_ = true; } |
| 82 |
|
| 83 |
// Returns true if this Phi candidate is ready to be emitted. |
| 84 |
bool IsReady() const { return is_complete() && copy_of() == 0; } |
| 85 |
|
| 86 |
// Pretty prints this Phi candidate into a string and returns it. |cfg| is |
| 87 |
// needed to lookup basic block predecessors. |
| 88 |
std::string PrettyPrint(const CFG* cfg) const; |
| 89 |
|
| 90 |
// Registers |operand_id| as a user of this Phi candidate. |
| 91 |
void AddUser(uint32_t operand_id) { users_.push_back(operand_id); } |
| 92 |
|
| 93 |
private: |
| 94 |
// Variable ID that this Phi is merging. |
| 95 |
uint32_t var_id_; |
| 96 |
|
| 97 |
// SSA ID generated by this Phi (i.e., this is the result ID of the eventual |
| 98 |
// Phi instruction). |
| 99 |
uint32_t result_id_; |
| 100 |
|
| 101 |
// Basic block to hold this Phi. |
| 102 |
BasicBlock* bb_; |
| 103 |
|
| 104 |
// Vector of operands for every predecessor block of |bb|. This vector is |
| 105 |
// organized so that the Ith slot contains the argument coming from the Ith |
| 106 |
// predecessor of |bb|. |
| 107 |
std::vector<uint32_t> phi_args_; |
| 108 |
|
| 109 |
// If this Phi is a trivial copy of another Phi, this is the ID of the |
| 110 |
// original. If this is 0, it means that this is not a trivial Phi. |
| 111 |
uint32_t copy_of_; |
| 112 |
|
| 113 |
// False, if this Phi candidate has no arguments or at least one argument is |
| 114 |
// %0. |
| 115 |
bool is_complete_; |
| 116 |
|
| 117 |
// List of all users for this Phi instruction. Each element is the result ID |
| 118 |
// of the load instruction replaced by this Phi, or the result ID of a Phi |
| 119 |
// candidate that has this Phi in its list of operands. |
| 120 |
std::vector<uint32_t> users_; |
| 121 |
}; |
| 122 |
|
| 123 |
// Type used to keep track of store operations in each basic block. |
| 124 |
typedef std::unordered_map<BasicBlock*, |
| 125 |
std::unordered_map<uint32_t, uint32_t>> |
| 126 |
BlockDefsMap; |
| 127 |
|
| 128 |
// Generates all the SSA rewriting decisions for basic block |bb|. This |
| 129 |
// populates the Phi candidate table (|phi_candidate_|) and the load |
| 130 |
// replacement table (|load_replacement_). Returns true if successful. |
| 131 |
bool GenerateSSAReplacements(BasicBlock* bb); |
| 132 |
|
| 133 |
// Seals block |bb|. Sealing a basic block means |bb| and all its |
| 134 |
// predecessors of |bb| have been scanned for loads/stores. |
| 135 |
void SealBlock(BasicBlock* bb); |
| 136 |
|
| 137 |
// Returns true if |bb| has been sealed. |
| 138 |
bool IsBlockSealed(BasicBlock* bb) { return sealed_blocks_.count(bb) != 0; } |
| 139 |
|
| 140 |
// Returns the Phi candidate with result ID |id| if it exists in the table |
| 141 |
// |phi_candidates_|. If no such Phi candidate exists, it returns nullptr. |
| 142 |
PhiCandidate* GetPhiCandidate(uint32_t id) { |
| 143 |
auto it = phi_candidates_.find(id); |
| 144 |
return (it != phi_candidates_.end()) ? &it->second : nullptr; |
| 145 |
} |
| 146 |
|
| 147 |
// Replaces all the users of Phi candidate |phi_cand| to be users of |
| 148 |
// |repl_id|. |
| 149 |
void ReplacePhiUsersWith(const PhiCandidate& phi_cand, uint32_t repl_id); |
| 150 |
|
| 151 |
// Returns the value ID that should replace the load ID in the given |
| 152 |
// replacement pair |repl|. The replacement is a pair (|load_id|, |val_id|). |
| 153 |
// If |val_id| is itself replaced by another value in the table, this function |
| 154 |
// will look the replacement for |val_id| until it finds one that is not |
| 155 |
// itself replaced. For instance, given: |
| 156 |
// |
| 157 |
// %34 = OpLoad %float %f1 |
| 158 |
// OpStore %t %34 |
| 159 |
// %36 = OpLoad %float %t |
| 160 |
// |
| 161 |
// Assume that %f1 is reached by a Phi candidate %42, the load |
| 162 |
// replacement table will have the following entries: |
| 163 |
// |
| 164 |
// %34 -> %42 |
| 165 |
// %36 -> %34 |
| 166 |
// |
| 167 |
// So, when looking for the replacement for %36, we should not use |
| 168 |
// %34. Rather, we should use %42. To do this, the chain of |
| 169 |
// replacements must be followed until we reach an element that has |
| 170 |
// no replacement. |
| 171 |
uint32_t GetReplacement(std::pair<uint32_t, uint32_t> repl); |
| 172 |
|
| 173 |
// Returns the argument at index |ix| from |phi_candidate|. If argument |ix| |
| 174 |
// comes from a trivial Phi, it follows the copy-of chain from that trivial |
| 175 |
// Phi until it finds the original Phi candidate. |
| 176 |
// |
| 177 |
// This is only valid after all Phi candidates have been completed. It can |
| 178 |
// only be called when generating the IR for these Phis. |
| 179 |
uint32_t GetPhiArgument(const PhiCandidate* phi_candidate, uint32_t ix); |
| 180 |
|
| 181 |
// Applies all the SSA replacement decisions. This replaces loads/stores to |
| 182 |
// SSA target variables with their corresponding SSA IDs, and inserts Phi |
| 183 |
// instructions for them. |
| 184 |
bool ApplyReplacements(); |
| 185 |
|
| 186 |
// Registers a definition for variable |var_id| in basic block |bb| with |
| 187 |
// value |val_id|. |
| 188 |
void WriteVariable(uint32_t var_id, BasicBlock* bb, uint32_t val_id) { |
| 189 |
defs_at_block_[bb][var_id] = val_id; |
| 190 |
if (auto* pc = GetPhiCandidate(val_id)) { |
| 191 |
pc->AddUser(bb->id()); |
| 192 |
} |
| 193 |
} |
| 194 |
|
| 195 |
// Returns the value of |var_id| at |bb| if |defs_at_block_| contains it. |
| 196 |
// Otherwise, returns 0. |
| 197 |
uint32_t GetValueAtBlock(uint32_t var_id, BasicBlock* bb); |
| 198 |
|
| 199 |
// Processes the store operation |inst| in basic block |bb|. This extracts |
| 200 |
// the variable ID being stored into, determines whether the variable is an |
| 201 |
// SSA-target variable, and, if it is, it stores its value in the |
| 202 |
// |defs_at_block_| map. |
| 203 |
void ProcessStore(Instruction* inst, BasicBlock* bb); |
| 204 |
|
| 205 |
// Processes the load operation |inst| in basic block |bb|. This extracts |
| 206 |
// the variable ID being stored into, determines whether the variable is an |
| 207 |
// SSA-target variable, and, if it is, it reads its reaching definition by |
| 208 |
// calling |GetReachingDef|. Returns true if successful. |
| 209 |
bool ProcessLoad(Instruction* inst, BasicBlock* bb); |
| 210 |
|
| 211 |
// Reads the current definition for variable |var_id| in basic block |bb|. |
| 212 |
// If |var_id| is not defined in block |bb| it walks up the predecessors of |
| 213 |
// |bb|, creating new Phi candidates along the way, if needed. |
| 214 |
// |
| 215 |
// It returns the value for |var_id| from the RHS of the current reaching |
| 216 |
// definition for |var_id|. |
| 217 |
uint32_t GetReachingDef(uint32_t var_id, BasicBlock* bb); |
| 218 |
|
| 219 |
// Adds arguments to |phi_candidate| by getting the reaching definition of |
| 220 |
// |phi_candidate|'s variable on each of the predecessors of its basic |
| 221 |
// block. After populating the argument list, it determines whether all its |
| 222 |
// arguments are the same. If so, it returns the ID of the argument that |
| 223 |
// this Phi copies. |
| 224 |
uint32_t AddPhiOperands(PhiCandidate* phi_candidate); |
| 225 |
|
| 226 |
// Creates a Phi candidate instruction for variable |var_id| in basic block |
| 227 |
// |bb|. |
| 228 |
// |
| 229 |
// Since the rewriting algorithm may remove Phi candidates when it finds |
| 230 |
// them to be trivial, we avoid the expense of creating actual Phi |
| 231 |
// instructions by keeping a pool of Phi candidates (|phi_candidates_|) |
| 232 |
// during rewriting. |
| 233 |
// |
| 234 |
// Once the candidate Phi is created, it returns its ID. |
| 235 |
PhiCandidate& CreatePhiCandidate(uint32_t var_id, BasicBlock* bb); |
| 236 |
|
| 237 |
// Attempts to remove a trivial Phi candidate |phi_cand|. Trivial Phis are |
| 238 |
// those that only reference themselves and one other value |val| any number |
| 239 |
// of times. This will try to remove any other Phis that become trivial |
| 240 |
// after |phi_cand| is removed. |
| 241 |
// |
| 242 |
// If |phi_cand| is trivial, it returns the SSA ID for the value that should |
| 243 |
// replace it. Otherwise, it returns the SSA ID for |phi_cand|. |
| 244 |
uint32_t TryRemoveTrivialPhi(PhiCandidate* phi_cand); |
| 245 |
|
| 246 |
// Finalizes |phi_candidate| by replacing every argument that is still %0 |
| 247 |
// with its reaching definition. |
| 248 |
void FinalizePhiCandidate(PhiCandidate* phi_candidate); |
| 249 |
|
| 250 |
// Finalizes processing of Phi candidates. Once the whole function has been |
| 251 |
// scanned for loads and stores, the CFG will still have some incomplete and |
| 252 |
// trivial Phis. This will add missing arguments and remove trivial Phi |
| 253 |
// candidates. |
| 254 |
void FinalizePhiCandidates(); |
| 255 |
|
| 256 |
// Adds DebugValues for DebugDeclares in |
| 257 |
// |decls_invisible_to_value_assignment_|. Returns whether the function was |
| 258 |
// modified or not, and whether or not the conversion was successful. |
| 259 |
Pass::Status AddDebugValuesForInvisibleDebugDecls(Function* fp); |
| 260 |
|
| 261 |
// Prints the table of Phi candidates to std::cerr. |
| 262 |
void PrintPhiCandidates() const; |
| 263 |
|
| 264 |
// Prints the load replacement table to std::cerr. |
| 265 |
void PrintReplacementTable() const; |
| 266 |
|
| 267 |
// Map holding the value of every SSA-target variable at every basic block |
| 268 |
// where the variable is stored. defs_at_block_[block][var_id] = val_id |
| 269 |
// means that there is a store or Phi instruction for variable |var_id| at |
| 270 |
// basic block |block| with value |val_id|. |
| 271 |
BlockDefsMap defs_at_block_; |
| 272 |
|
| 273 |
// Map, indexed by Phi ID, holding all the Phi candidates created during SSA |
| 274 |
// rewriting. |phi_candidates_[id]| returns the Phi candidate whose result |
| 275 |
// is |id|. |
| 276 |
std::unordered_map<uint32_t, PhiCandidate> phi_candidates_; |
| 277 |
|
| 278 |
// Queue of incomplete Phi candidates. These are Phi candidates created at |
| 279 |
// unsealed blocks. They need to be completed before they are instantiated |
| 280 |
// in ApplyReplacements. |
| 281 |
std::queue<PhiCandidate*> incomplete_phis_; |
| 282 |
|
| 283 |
// List of completed Phi candidates. These are the only candidates that |
| 284 |
// will become real Phi instructions. |
| 285 |
std::vector<PhiCandidate*> phis_to_generate_; |
| 286 |
|
| 287 |
// SSA replacement table. This maps variable IDs, resulting from a load |
| 288 |
// operation, to the value IDs that will replace them after SSA rewriting. |
| 289 |
// After all the rewriting decisions are made, a final scan through the IR |
| 290 |
// is done to replace all uses of the original load ID with the value ID. |
| 291 |
std::unordered_map<uint32_t, uint32_t> load_replacement_; |
| 292 |
|
| 293 |
// Set of blocks that have been sealed already. |
| 294 |
std::unordered_set<BasicBlock*> sealed_blocks_; |
| 295 |
|
| 296 |
// Memory pass requesting the SSA rewriter. |
| 297 |
MemPass* pass_; |
| 298 |
|
| 299 |
// Set of DebugDeclare instructions that are not added as DebugValue because |
| 300 |
// they are invisible to the store or phi instructions. |
| 301 |
std::unordered_set<Instruction*> decls_invisible_to_value_assignment_; |
| 302 |
}; |
| 303 |
|
| 304 |
class SSARewritePass : public MemPass { |
| 305 |
public: |
| 306 |
SSARewritePass() = default; |
| 307 |
|
| 308 |
const char* name() const override { return "ssa-rewrite"; } |
| 309 |
Status Process() override; |
| 310 |
}; |
| 311 |
|
| 312 |
} // namespace opt |
| 313 |
} // namespace spvtools |
| 314 |
|
| 315 |
#endif // SOURCE_OPT_SSA_REWRITE_PASS_H_ |