| // Copyright (c) 2017 Google Inc. |
| // |
| // 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_MERGE_RETURN_PASS_H_ |
| #define SOURCE_OPT_MERGE_RETURN_PASS_H_ |
| |
| #include <unordered_map> |
| #include <unordered_set> |
| #include <vector> |
| |
| #include "source/opt/basic_block.h" |
| #include "source/opt/function.h" |
| #include "source/opt/mem_pass.h" |
| |
| namespace spvtools { |
| namespace opt { |
| |
| /******************************************************************************* |
| * |
| * Handling Structured Control Flow: |
| * |
| * Structured control flow guarantees that the CFG will converge at a given |
| * point (the merge block). Within structured control flow, all blocks must be |
| * post-dominated by the merge block, except return blocks and break blocks. |
| * A break block is a block that branches to the innermost loop's merge block. |
| * |
| * Beyond this, we further assume that all unreachable blocks have been |
| * cleaned up. This means that the only unreachable blocks are those necessary |
| * for valid structured control flow. |
| * |
| * Algorithm: |
| * |
| * If a return is encountered, it should record that: i) the function has |
| * "returned" and ii) the value of the return. The return should be replaced |
| * with a branch. If current block is not within structured control flow, this |
| * is the final return. This block should branch to the new return block (its |
| * direct successor). If the current block is within structured control flow, |
| * the branch destination should be the innermost loop's merge. This loop will |
| * always exist because a dummy loop is added around the entire function. |
| * If the merge block produces any live values it will need to be predicated. |
| * While the merge is nested in structured control flow, the predication path |
| *should branch to the merge block of the inner-most loop it is contained in. |
| *Once structured control flow has been exited, it will be at the merge of the |
| *dummy loop, with will simply return. |
| * |
| * In the final return block, the return value should be loaded and returned. |
| * Memory promotion passes should be able to promote the newly introduced |
| * variables ("has returned" and "return value"). |
| * |
| * Predicating the Final Merge: |
| * |
| * At each merge block predication needs to be introduced (optimization: only if |
| * that block produces value live beyond it). This needs to be done carefully. |
| * The merge block should be split into multiple blocks. |
| * |
| * 1 (loop header) |
| * / \ |
| * (ret) 2 3 (merge) |
| * |
| * || |
| * \/ |
| * |
| * 0 (dummy loop header) |
| * | |
| * 1 (loop header) |
| * / \ |
| * 2 | (merge) |
| * \ / |
| * 3' (merge) |
| * / \ |
| * | 3 (original code in 3) |
| * \ / |
| * (ret) 4 (dummy loop merge) |
| * |
| * In the above (simple) example, the return originally in |2| is passed through |
| * the merge. That merge is predicated such that the old body of the block is |
| * the else branch. The branch condition is based on the value of the "has |
| * returned" variable. |
| * |
| ******************************************************************************/ |
| |
| // Documented in optimizer.hpp |
| class MergeReturnPass : public MemPass { |
| public: |
| MergeReturnPass() |
| : function_(nullptr), |
| return_flag_(nullptr), |
| return_value_(nullptr), |
| constant_true_(nullptr), |
| final_return_block_(nullptr) {} |
| |
| const char* name() const override { return "merge-return"; } |
| Status Process() override; |
| |
| IRContext::Analysis GetPreservedAnalyses() override { |
| return IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; |
| } |
| |
| private: |
| // This class is used to store the a loop merge instruction and a selection |
| // merge instruction. The intended use is that is represent the inner most |
| // contain selection construct and the inner most loop construct. |
| class StructuredControlState { |
| public: |
| StructuredControlState(Instruction* loop, Instruction* merge) |
| : loop_merge_(loop), current_merge_(merge) {} |
| |
| StructuredControlState(const StructuredControlState&) = default; |
| |
| bool InLoop() const { return loop_merge_; } |
| bool InStructuredFlow() const { return CurrentMergeId() != 0; } |
| |
| uint32_t CurrentMergeId() const { |
| return current_merge_ ? current_merge_->GetSingleWordInOperand(0u) : 0u; |
| } |
| |
| uint32_t CurrentMergeHeader() const { |
| return current_merge_ ? current_merge_->context() |
| ->get_instr_block(current_merge_) |
| ->id() |
| : 0; |
| } |
| |
| uint32_t LoopMergeId() const { |
| return loop_merge_ ? loop_merge_->GetSingleWordInOperand(0u) : 0u; |
| } |
| |
| uint32_t CurrentLoopHeader() const { |
| return loop_merge_ |
| ? loop_merge_->context()->get_instr_block(loop_merge_)->id() |
| : 0; |
| } |
| |
| Instruction* LoopMergeInst() const { return loop_merge_; } |
| |
| private: |
| Instruction* loop_merge_; |
| Instruction* current_merge_; |
| }; |
| |
| // Returns all BasicBlocks terminated by OpReturn or OpReturnValue in |
| // |function|. |
| std::vector<BasicBlock*> CollectReturnBlocks(Function* function); |
| |
| // Creates a new basic block with a single return. If |function| returns a |
| // value, a phi node is created to select the correct value to return. |
| // Replaces old returns with an unconditional branch to the new block. |
| void MergeReturnBlocks(Function* function, |
| const std::vector<BasicBlock*>& returnBlocks); |
| |
| // Merges the return instruction in |function| so that it has a single return |
| // statement. It is assumed that |function| has structured control flow, and |
| // that |return_blocks| is a list of all of the basic blocks in |function| |
| // that have a return. |
| bool ProcessStructured(Function* function, |
| const std::vector<BasicBlock*>& return_blocks); |
| |
| // Changes an OpReturn* or OpUnreachable instruction at the end of |block| |
| // into a store to |return_flag_|, a store to |return_value_| (if necessary), |
| // and a branch to the appropriate merge block. |
| // |
| // Is is assumed that |AddReturnValue| have already been called to created the |
| // variable to store a return value if there is one. |
| // |
| // Note this will break the semantics. To fix this, PredicateBlock will have |
| // to be called on the merge block the branch targets. |
| void ProcessStructuredBlock(BasicBlock* block); |
| |
| // Creates a variable used to store whether or not the control flow has |
| // traversed a block that used to have a return. A pointer to the instruction |
| // declaring the variable is stored in |return_flag_|. |
| void AddReturnFlag(); |
| |
| // Creates the variable used to store the return value when passing through |
| // a block that use to contain an OpReturnValue. |
| void AddReturnValue(); |
| |
| // Adds a store that stores true to |return_flag_| immediately before the |
| // terminator of |block|. It is assumed that |AddReturnFlag| has already been |
| // called. |
| void RecordReturned(BasicBlock* block); |
| |
| // Adds an instruction that stores the value being returned in the |
| // OpReturnValue in |block|. The value is stored to |return_value_|, and the |
| // store is placed before the OpReturnValue. |
| // |
| // If |block| does not contain an OpReturnValue, then this function has no |
| // effect. If |block| contains an OpReturnValue, then |AddReturnValue| must |
| // have already been called to create the variable to store to. |
| void RecordReturnValue(BasicBlock* block); |
| |
| // Adds an unconditional branch in |block| that branches to |target|. It also |
| // adds stores to |return_flag_| and |return_value_| as needed. |
| // |AddReturnFlag| and |AddReturnValue| must have already been called. |
| void BranchToBlock(BasicBlock* block, uint32_t target); |
| |
| // For every basic block that is reachable from |return_block|, extra code is |
| // added to jump around any code that should not be executed because the |
| // original code would have already returned. This involves adding new |
| // selections constructs to jump around these instructions. |
| // |
| // If new blocks that are created will be added to |order|. This way a call |
| // can traverse these new block in structured order. |
| // |
| // Returns true if successful. |
| bool PredicateBlocks(BasicBlock* return_block, |
| std::unordered_set<BasicBlock*>* pSet, |
| std::list<BasicBlock*>* order); |
| |
| // Add a conditional branch at the start of |block| that either jumps to |
| // the merge block of |loop_merge_inst| or the original code in |block| |
| // depending on the value in |return_flag_|. The continue target in |
| // |loop_merge_inst| will be updated if needed. |
| // |
| // If new blocks that are created will be added to |order|. This way a call |
| // can traverse these new block in structured order. |
| // |
| // Returns true if successful. |
| bool BreakFromConstruct(BasicBlock* block, |
| std::unordered_set<BasicBlock*>* predicated, |
| std::list<BasicBlock*>* order, |
| Instruction* loop_merge_inst); |
| |
| // Add an |OpReturn| or |OpReturnValue| to the end of |block|. If an |
| // |OpReturnValue| is needed, the return value is loaded from |return_value_|. |
| void CreateReturn(BasicBlock* block); |
| |
| // Creates a block at the end of the function that will become the single |
| // return block at the end of the pass. |
| void CreateReturnBlock(); |
| |
| // Creates a Phi node in |merge_block| for the result of |inst| coming from |
| // |predecessor|. Any uses of the result of |inst| that are no longer |
| // dominated by |inst|, are replaced with the result of the new |OpPhi| |
| // instruction. |
| void CreatePhiNodesForInst(BasicBlock* merge_block, uint32_t predecessor, |
| Instruction& inst); |
| |
| // Traverse the nodes in |new_merge_nodes_|, and adds the OpPhi instructions |
| // that are needed to make the code correct. It is assumed that at this point |
| // there are no unreachable blocks in the control flow graph. |
| void AddNewPhiNodes(); |
| |
| // Creates any new phi nodes that are needed in |bb| now that |pred| is no |
| // longer the only block that preceedes |bb|. |header_id| is the id of the |
| // basic block for the loop or selection construct that merges at |bb|. |
| void AddNewPhiNodes(BasicBlock* bb, BasicBlock* pred, uint32_t header_id); |
| |
| // Saves |block| to a list of basic block that will require OpPhi nodes to be |
| // added by calling |AddNewPhiNodes|. It is assumed that |block| used to have |
| // a single predecessor, |single_original_pred|, but now has more. |
| void MarkForNewPhiNodes(BasicBlock* block, BasicBlock* single_original_pred); |
| |
| // Return the original single predcessor of |block| if it was flagged as |
| // having a single predecessor. |nullptr| is returned otherwise. |
| BasicBlock* MarkedSinglePred(BasicBlock* block) { |
| auto it = new_merge_nodes_.find(block); |
| if (it != new_merge_nodes_.end()) { |
| return it->second; |
| } else { |
| return nullptr; |
| } |
| } |
| |
| // Modifies existing OpPhi instruction in |target| block to account for the |
| // new edge from |new_source|. The value for that edge will be an Undef. If |
| // |target| only had a single predecessor, then it is marked as needing new |
| // phi nodes. See |MarkForNewPhiNodes|. |
| // |
| // The CFG must not include the edge from |new_source| to |target| yet. |
| void UpdatePhiNodes(BasicBlock* new_source, BasicBlock* target); |
| |
| StructuredControlState& CurrentState() { return state_.back(); } |
| |
| // Inserts |new_element| into |list| after the first occurrence of |element|. |
| // |element| must be in |list| at least once. |
| void InsertAfterElement(BasicBlock* element, BasicBlock* new_element, |
| std::list<BasicBlock*>* list); |
| |
| // Creates a single iteration loop around all of the exectuable code of the |
| // current function and returns after the loop is done. Sets |
| // |final_return_block_|. |
| void AddDummyLoopAroundFunction(); |
| |
| // Creates a new basic block that branches to |header_label_id|. Returns the |
| // new basic block. The block will be the second last basic block in the |
| // function. |
| BasicBlock* CreateContinueTarget(uint32_t header_label_id); |
| |
| // Creates a loop around the executable code of the function with |
| // |merge_target| as the merge node. |
| void CreateDummyLoop(BasicBlock* merge_target); |
| |
| // A stack used to keep track of the innermost contain loop and selection |
| // constructs. |
| std::vector<StructuredControlState> state_; |
| |
| // The current function being transformed. |
| Function* function_; |
| |
| // The |OpVariable| instruction defining a boolean variable used to keep track |
| // of whether or not the function is trying to return. |
| Instruction* return_flag_; |
| |
| // The |OpVariable| instruction defining a variabled to used to keep track of |
| // the value that was returned when passing through a block that use to |
| // contain an |OpReturnValue|. |
| Instruction* return_value_; |
| |
| // The instruction defining the boolean constant true. |
| Instruction* constant_true_; |
| |
| // The basic block that is suppose to become the contain the only return value |
| // after processing the current function. |
| BasicBlock* final_return_block_; |
| |
| // This map contains the set of nodes that use to have a single predcessor, |
| // but now have more. They will need new OpPhi nodes. For each of the nodes, |
| // it is mapped to it original single predcessor. It is assumed there are no |
| // values that will need a phi on the new edges. |
| std::unordered_map<BasicBlock*, BasicBlock*> new_merge_nodes_; |
| bool HasNontrivialUnreachableBlocks(Function* function); |
| }; |
| |
| } // namespace opt |
| } // namespace spvtools |
| |
| #endif // SOURCE_OPT_MERGE_RETURN_PASS_H_ |