| // Copyright (c) 2018 Google LLC. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #ifndef SOURCE_OPT_SSA_REWRITE_PASS_H_ |
| #define SOURCE_OPT_SSA_REWRITE_PASS_H_ |
| |
| #include <queue> |
| #include <string> |
| #include <unordered_map> |
| #include <unordered_set> |
| #include <utility> |
| #include <vector> |
| |
| #include "source/opt/basic_block.h" |
| #include "source/opt/ir_context.h" |
| #include "source/opt/mem_pass.h" |
| |
| namespace spvtools { |
| namespace opt { |
| |
| // Utility class for passes that need to rewrite a function into SSA. This |
| // converts load/store operations on function-local variables into SSA IDs, |
| // which allows them to be the target of optimizing transformations. |
| // |
| // Store and load operations to these variables are converted into |
| // operations on SSA IDs. Phi instructions are added when needed. See the |
| // SSA construction paper for algorithmic details |
| // (https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6) |
| class SSARewriter { |
| public: |
| SSARewriter(MemPass* pass) : pass_(pass) {} |
| |
| // Rewrites SSA-target variables in function |fp| into SSA. This is the |
| // entry point for the SSA rewrite algorithm. SSA-target variables are |
| // locally defined variables that meet the criteria set by IsSSATargetVar. |
| // |
| // Returns whether the function was modified or not, and whether or not the |
| // rewrite was successful. |
| Pass::Status RewriteFunctionIntoSSA(Function* fp); |
| |
| private: |
| class PhiCandidate { |
| public: |
| explicit PhiCandidate(uint32_t var, uint32_t result, BasicBlock* block) |
| : var_id_(var), |
| result_id_(result), |
| bb_(block), |
| phi_args_(), |
| copy_of_(0), |
| is_complete_(false), |
| users_() {} |
| |
| uint32_t var_id() const { return var_id_; } |
| uint32_t result_id() const { return result_id_; } |
| BasicBlock* bb() const { return bb_; } |
| std::vector<uint32_t>& phi_args() { return phi_args_; } |
| const std::vector<uint32_t>& phi_args() const { return phi_args_; } |
| uint32_t copy_of() const { return copy_of_; } |
| bool is_complete() const { return is_complete_; } |
| std::vector<uint32_t>& users() { return users_; } |
| const std::vector<uint32_t>& users() const { return users_; } |
| |
| // Marks this phi candidate as a trivial copy of |orig_id|. |
| void MarkCopyOf(uint32_t orig_id) { copy_of_ = orig_id; } |
| |
| // Marks this phi candidate as incomplete. |
| void MarkIncomplete() { is_complete_ = false; } |
| |
| // Marks this phi candidate as complete. |
| void MarkComplete() { is_complete_ = true; } |
| |
| // Returns true if this Phi candidate is ready to be emitted. |
| bool IsReady() const { return is_complete() && copy_of() == 0; } |
| |
| // Pretty prints this Phi candidate into a string and returns it. |cfg| is |
| // needed to lookup basic block predecessors. |
| std::string PrettyPrint(const CFG* cfg) const; |
| |
| // Registers |operand_id| as a user of this Phi candidate. |
| void AddUser(uint32_t operand_id) { users_.push_back(operand_id); } |
| |
| private: |
| // Variable ID that this Phi is merging. |
| uint32_t var_id_; |
| |
| // SSA ID generated by this Phi (i.e., this is the result ID of the eventual |
| // Phi instruction). |
| uint32_t result_id_; |
| |
| // Basic block to hold this Phi. |
| BasicBlock* bb_; |
| |
| // Vector of operands for every predecessor block of |bb|. This vector is |
| // organized so that the Ith slot contains the argument coming from the Ith |
| // predecessor of |bb|. |
| std::vector<uint32_t> phi_args_; |
| |
| // If this Phi is a trivial copy of another Phi, this is the ID of the |
| // original. If this is 0, it means that this is not a trivial Phi. |
| uint32_t copy_of_; |
| |
| // False, if this Phi candidate has no arguments or at least one argument is |
| // %0. |
| bool is_complete_; |
| |
| // List of all users for this Phi instruction. Each element is the result ID |
| // of the load instruction replaced by this Phi, or the result ID of a Phi |
| // candidate that has this Phi in its list of operands. |
| std::vector<uint32_t> users_; |
| }; |
| |
| // Type used to keep track of store operations in each basic block. |
| typedef std::unordered_map<BasicBlock*, |
| std::unordered_map<uint32_t, uint32_t>> |
| BlockDefsMap; |
| |
| // Generates all the SSA rewriting decisions for basic block |bb|. This |
| // populates the Phi candidate table (|phi_candidate_|) and the load |
| // replacement table (|load_replacement_). Returns true if successful. |
| bool GenerateSSAReplacements(BasicBlock* bb); |
| |
| // Seals block |bb|. Sealing a basic block means |bb| and all its |
| // predecessors of |bb| have been scanned for loads/stores. |
| void SealBlock(BasicBlock* bb); |
| |
| // Returns true if |bb| has been sealed. |
| bool IsBlockSealed(BasicBlock* bb) { return sealed_blocks_.count(bb) != 0; } |
| |
| // Returns the Phi candidate with result ID |id| if it exists in the table |
| // |phi_candidates_|. If no such Phi candidate exists, it returns nullptr. |
| PhiCandidate* GetPhiCandidate(uint32_t id) { |
| auto it = phi_candidates_.find(id); |
| return (it != phi_candidates_.end()) ? &it->second : nullptr; |
| } |
| |
| // Replaces all the users of Phi candidate |phi_cand| to be users of |
| // |repl_id|. |
| void ReplacePhiUsersWith(const PhiCandidate& phi_cand, uint32_t repl_id); |
| |
| // Returns the value ID that should replace the load ID in the given |
| // replacement pair |repl|. The replacement is a pair (|load_id|, |val_id|). |
| // If |val_id| is itself replaced by another value in the table, this function |
| // will look the replacement for |val_id| until it finds one that is not |
| // itself replaced. For instance, given: |
| // |
| // %34 = OpLoad %float %f1 |
| // OpStore %t %34 |
| // %36 = OpLoad %float %t |
| // |
| // Assume that %f1 is reached by a Phi candidate %42, the load |
| // replacement table will have the following entries: |
| // |
| // %34 -> %42 |
| // %36 -> %34 |
| // |
| // So, when looking for the replacement for %36, we should not use |
| // %34. Rather, we should use %42. To do this, the chain of |
| // replacements must be followed until we reach an element that has |
| // no replacement. |
| uint32_t GetReplacement(std::pair<uint32_t, uint32_t> repl); |
| |
| // Returns the argument at index |ix| from |phi_candidate|. If argument |ix| |
| // comes from a trivial Phi, it follows the copy-of chain from that trivial |
| // Phi until it finds the original Phi candidate. |
| // |
| // This is only valid after all Phi candidates have been completed. It can |
| // only be called when generating the IR for these Phis. |
| uint32_t GetPhiArgument(const PhiCandidate* phi_candidate, uint32_t ix); |
| |
| // Applies all the SSA replacement decisions. This replaces loads/stores to |
| // SSA target variables with their corresponding SSA IDs, and inserts Phi |
| // instructions for them. |
| bool ApplyReplacements(); |
| |
| // Registers a definition for variable |var_id| in basic block |bb| with |
| // value |val_id|. |
| void WriteVariable(uint32_t var_id, BasicBlock* bb, uint32_t val_id) { |
| defs_at_block_[bb][var_id] = val_id; |
| if (auto* pc = GetPhiCandidate(val_id)) { |
| pc->AddUser(bb->id()); |
| } |
| } |
| |
| // Returns the value of |var_id| at |bb| if |defs_at_block_| contains it. |
| // Otherwise, returns 0. |
| uint32_t GetValueAtBlock(uint32_t var_id, BasicBlock* bb); |
| |
| // Processes the store operation |inst| in basic block |bb|. This extracts |
| // the variable ID being stored into, determines whether the variable is an |
| // SSA-target variable, and, if it is, it stores its value in the |
| // |defs_at_block_| map. |
| void ProcessStore(Instruction* inst, BasicBlock* bb); |
| |
| // Processes the load operation |inst| in basic block |bb|. This extracts |
| // the variable ID being stored into, determines whether the variable is an |
| // SSA-target variable, and, if it is, it reads its reaching definition by |
| // calling |GetReachingDef|. Returns true if successful. |
| bool ProcessLoad(Instruction* inst, BasicBlock* bb); |
| |
| // Reads the current definition for variable |var_id| in basic block |bb|. |
| // If |var_id| is not defined in block |bb| it walks up the predecessors of |
| // |bb|, creating new Phi candidates along the way, if needed. |
| // |
| // It returns the value for |var_id| from the RHS of the current reaching |
| // definition for |var_id|. |
| uint32_t GetReachingDef(uint32_t var_id, BasicBlock* bb); |
| |
| // Adds arguments to |phi_candidate| by getting the reaching definition of |
| // |phi_candidate|'s variable on each of the predecessors of its basic |
| // block. After populating the argument list, it determines whether all its |
| // arguments are the same. If so, it returns the ID of the argument that |
| // this Phi copies. |
| uint32_t AddPhiOperands(PhiCandidate* phi_candidate); |
| |
| // Creates a Phi candidate instruction for variable |var_id| in basic block |
| // |bb|. |
| // |
| // Since the rewriting algorithm may remove Phi candidates when it finds |
| // them to be trivial, we avoid the expense of creating actual Phi |
| // instructions by keeping a pool of Phi candidates (|phi_candidates_|) |
| // during rewriting. |
| // |
| // Once the candidate Phi is created, it returns its ID. |
| PhiCandidate& CreatePhiCandidate(uint32_t var_id, BasicBlock* bb); |
| |
| // Attempts to remove a trivial Phi candidate |phi_cand|. Trivial Phis are |
| // those that only reference themselves and one other value |val| any number |
| // of times. This will try to remove any other Phis that become trivial |
| // after |phi_cand| is removed. |
| // |
| // If |phi_cand| is trivial, it returns the SSA ID for the value that should |
| // replace it. Otherwise, it returns the SSA ID for |phi_cand|. |
| uint32_t TryRemoveTrivialPhi(PhiCandidate* phi_cand); |
| |
| // Finalizes |phi_candidate| by replacing every argument that is still %0 |
| // with its reaching definition. |
| void FinalizePhiCandidate(PhiCandidate* phi_candidate); |
| |
| // Finalizes processing of Phi candidates. Once the whole function has been |
| // scanned for loads and stores, the CFG will still have some incomplete and |
| // trivial Phis. This will add missing arguments and remove trivial Phi |
| // candidates. |
| void FinalizePhiCandidates(); |
| |
| // Prints the table of Phi candidates to std::cerr. |
| void PrintPhiCandidates() const; |
| |
| // Prints the load replacement table to std::cerr. |
| void PrintReplacementTable() const; |
| |
| // Map holding the value of every SSA-target variable at every basic block |
| // where the variable is stored. defs_at_block_[block][var_id] = val_id |
| // means that there is a store or Phi instruction for variable |var_id| at |
| // basic block |block| with value |val_id|. |
| BlockDefsMap defs_at_block_; |
| |
| // Map, indexed by Phi ID, holding all the Phi candidates created during SSA |
| // rewriting. |phi_candidates_[id]| returns the Phi candidate whose result |
| // is |id|. |
| std::unordered_map<uint32_t, PhiCandidate> phi_candidates_; |
| |
| // Queue of incomplete Phi candidates. These are Phi candidates created at |
| // unsealed blocks. They need to be completed before they are instantiated |
| // in ApplyReplacements. |
| std::queue<PhiCandidate*> incomplete_phis_; |
| |
| // List of completed Phi candidates. These are the only candidates that |
| // will become real Phi instructions. |
| std::vector<PhiCandidate*> phis_to_generate_; |
| |
| // SSA replacement table. This maps variable IDs, resulting from a load |
| // operation, to the value IDs that will replace them after SSA rewriting. |
| // After all the rewriting decisions are made, a final scan through the IR |
| // is done to replace all uses of the original load ID with the value ID. |
| std::unordered_map<uint32_t, uint32_t> load_replacement_; |
| |
| // Set of blocks that have been sealed already. |
| std::unordered_set<BasicBlock*> sealed_blocks_; |
| |
| // Memory pass requesting the SSA rewriter. |
| MemPass* pass_; |
| }; |
| |
| class SSARewritePass : public MemPass { |
| public: |
| SSARewritePass() = default; |
| |
| const char* name() const override { return "ssa-rewrite"; } |
| Status Process() override; |
| }; |
| |
| } // namespace opt |
| } // namespace spvtools |
| |
| #endif // SOURCE_OPT_SSA_REWRITE_PASS_H_ |