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_MERGE_RETURN_PASS_H_ 16 #define SOURCE_OPT_MERGE_RETURN_PASS_H_ 17 18 #include <unordered_map> 19 #include <unordered_set> 20 #include <vector> 21 22 #include "source/opt/basic_block.h" 23 #include "source/opt/function.h" 24 #include "source/opt/mem_pass.h" 25 26 namespace spvtools { 27 namespace opt { 28 29 /******************************************************************************* 30 * 31 * Handling Structured Control Flow: 32 * 33 * Structured control flow guarantees that the CFG will converge at a given 34 * point (the merge block). Within structured control flow, all blocks must be 35 * post-dominated by the merge block, except return blocks and break blocks. 36 * A break block is a block that branches to the innermost loop's merge block. 37 * 38 * Beyond this, we further assume that all unreachable blocks have been 39 * cleaned up. This means that the only unreachable blocks are those necessary 40 * for valid structured control flow. 41 * 42 * Algorithm: 43 * 44 * If a return is encountered, it should record that: i) the function has 45 * "returned" and ii) the value of the return. The return should be replaced 46 * with a branch. If current block is not within structured control flow, this 47 * is the final return. This block should branch to the new return block (its 48 * direct successor). If the current block is within structured control flow, 49 * the branch destination should be the innermost loop's merge. This loop will 50 * always exist because a dummy loop is added around the entire function. 51 * If the merge block produces any live values it will need to be predicated. 52 * While the merge is nested in structured control flow, the predication path 53 *should branch to the merge block of the inner-most loop it is contained in. 54 *Once structured control flow has been exited, it will be at the merge of the 55 *dummy loop, with will simply return. 56 * 57 * In the final return block, the return value should be loaded and returned. 58 * Memory promotion passes should be able to promote the newly introduced 59 * variables ("has returned" and "return value"). 60 * 61 * Predicating the Final Merge: 62 * 63 * At each merge block predication needs to be introduced (optimization: only if 64 * that block produces value live beyond it). This needs to be done carefully. 65 * The merge block should be split into multiple blocks. 66 * 67 * 1 (loop header) 68 * / \ 69 * (ret) 2 3 (merge) 70 * 71 * || 72 * \/ 73 * 74 * 0 (dummy loop header) 75 * | 76 * 1 (loop header) 77 * / \ 78 * 2 | (merge) 79 * \ / 80 * 3' (merge) 81 * / \ 82 * | 3 (original code in 3) 83 * \ / 84 * (ret) 4 (dummy loop merge) 85 * 86 * In the above (simple) example, the return originally in |2| is passed through 87 * the merge. That merge is predicated such that the old body of the block is 88 * the else branch. The branch condition is based on the value of the "has 89 * returned" variable. 90 * 91 ******************************************************************************/ 92 93 // Documented in optimizer.hpp 94 class MergeReturnPass : public MemPass { 95 public: 96 MergeReturnPass() 97 : function_(nullptr), 98 return_flag_(nullptr), 99 return_value_(nullptr), 100 constant_true_(nullptr), 101 final_return_block_(nullptr) {} 102 103 const char* name() const override { return "merge-return"; } 104 Status Process() override; 105 106 IRContext::Analysis GetPreservedAnalyses() override { 107 return IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; 108 } 109 110 private: 111 // This class is used to store the a loop merge instruction and a selection 112 // merge instruction. The intended use is that is represent the inner most 113 // contain selection construct and the inner most loop construct. 114 class StructuredControlState { 115 public: 116 StructuredControlState(Instruction* loop, Instruction* merge) 117 : loop_merge_(loop), current_merge_(merge) {} 118 119 StructuredControlState(const StructuredControlState&) = default; 120 121 bool InLoop() const { return loop_merge_; } 122 bool InStructuredFlow() const { return CurrentMergeId() != 0; } 123 124 uint32_t CurrentMergeId() const { 125 return current_merge_ ? current_merge_->GetSingleWordInOperand(0u) : 0u; 126 } 127 128 uint32_t CurrentMergeHeader() const { 129 return current_merge_ ? current_merge_->context() 130 ->get_instr_block(current_merge_) 131 ->id() 132 : 0; 133 } 134 135 uint32_t LoopMergeId() const { 136 return loop_merge_ ? loop_merge_->GetSingleWordInOperand(0u) : 0u; 137 } 138 139 uint32_t CurrentLoopHeader() const { 140 return loop_merge_ 141 ? loop_merge_->context()->get_instr_block(loop_merge_)->id() 142 : 0; 143 } 144 145 Instruction* LoopMergeInst() const { return loop_merge_; } 146 147 private: 148 Instruction* loop_merge_; 149 Instruction* current_merge_; 150 }; 151 152 // Returns all BasicBlocks terminated by OpReturn or OpReturnValue in 153 // |function|. 154 std::vector<BasicBlock*> CollectReturnBlocks(Function* function); 155 156 // Creates a new basic block with a single return. If |function| returns a 157 // value, a phi node is created to select the correct value to return. 158 // Replaces old returns with an unconditional branch to the new block. 159 void MergeReturnBlocks(Function* function, 160 const std::vector<BasicBlock*>& returnBlocks); 161 162 // Merges the return instruction in |function| so that it has a single return 163 // statement. It is assumed that |function| has structured control flow, and 164 // that |return_blocks| is a list of all of the basic blocks in |function| 165 // that have a return. 166 bool ProcessStructured(Function* function, 167 const std::vector<BasicBlock*>& return_blocks); 168 169 // Changes an OpReturn* or OpUnreachable instruction at the end of |block| 170 // into a store to |return_flag_|, a store to |return_value_| (if necessary), 171 // and a branch to the appropriate merge block. 172 // 173 // Is is assumed that |AddReturnValue| have already been called to created the 174 // variable to store a return value if there is one. 175 // 176 // Note this will break the semantics. To fix this, PredicateBlock will have 177 // to be called on the merge block the branch targets. 178 void ProcessStructuredBlock(BasicBlock* block); 179 180 // Creates a variable used to store whether or not the control flow has 181 // traversed a block that used to have a return. A pointer to the instruction 182 // declaring the variable is stored in |return_flag_|. 183 void AddReturnFlag(); 184 185 // Creates the variable used to store the return value when passing through 186 // a block that use to contain an OpReturnValue. 187 void AddReturnValue(); 188 189 // Adds a store that stores true to |return_flag_| immediately before the 190 // terminator of |block|. It is assumed that |AddReturnFlag| has already been 191 // called. 192 void RecordReturned(BasicBlock* block); 193 194 // Adds an instruction that stores the value being returned in the 195 // OpReturnValue in |block|. The value is stored to |return_value_|, and the 196 // store is placed before the OpReturnValue. 197 // 198 // If |block| does not contain an OpReturnValue, then this function has no 199 // effect. If |block| contains an OpReturnValue, then |AddReturnValue| must 200 // have already been called to create the variable to store to. 201 void RecordReturnValue(BasicBlock* block); 202 203 // Adds an unconditional branch in |block| that branches to |target|. It also 204 // adds stores to |return_flag_| and |return_value_| as needed. 205 // |AddReturnFlag| and |AddReturnValue| must have already been called. 206 void BranchToBlock(BasicBlock* block, uint32_t target); 207 208 // For every basic block that is reachable from |return_block|, extra code is 209 // added to jump around any code that should not be executed because the 210 // original code would have already returned. This involves adding new 211 // selections constructs to jump around these instructions. 212 // 213 // If new blocks that are created will be added to |order|. This way a call 214 // can traverse these new block in structured order. 215 // 216 // Returns true if successful. 217 bool PredicateBlocks(BasicBlock* return_block, 218 std::unordered_set<BasicBlock*>* pSet, 219 std::list<BasicBlock*>* order); 220 221 // Add a conditional branch at the start of |block| that either jumps to 222 // the merge block of |loop_merge_inst| or the original code in |block| 223 // depending on the value in |return_flag_|. The continue target in 224 // |loop_merge_inst| will be updated if needed. 225 // 226 // If new blocks that are created will be added to |order|. This way a call 227 // can traverse these new block in structured order. 228 // 229 // Returns true if successful. 230 bool BreakFromConstruct(BasicBlock* block, 231 std::unordered_set<BasicBlock*>* predicated, 232 std::list<BasicBlock*>* order, 233 Instruction* loop_merge_inst); 234 235 // Add an |OpReturn| or |OpReturnValue| to the end of |block|. If an 236 // |OpReturnValue| is needed, the return value is loaded from |return_value_|. 237 void CreateReturn(BasicBlock* block); 238 239 // Creates a block at the end of the function that will become the single 240 // return block at the end of the pass. 241 void CreateReturnBlock(); 242 243 // Creates a Phi node in |merge_block| for the result of |inst| coming from 244 // |predecessor|. Any uses of the result of |inst| that are no longer 245 // dominated by |inst|, are replaced with the result of the new |OpPhi| 246 // instruction. 247 void CreatePhiNodesForInst(BasicBlock* merge_block, uint32_t predecessor, 248 Instruction& inst); 249 250 // Traverse the nodes in |new_merge_nodes_|, and adds the OpPhi instructions 251 // that are needed to make the code correct. It is assumed that at this point 252 // there are no unreachable blocks in the control flow graph. 253 void AddNewPhiNodes(); 254 255 // Creates any new phi nodes that are needed in |bb| now that |pred| is no 256 // longer the only block that preceedes |bb|. |header_id| is the id of the 257 // basic block for the loop or selection construct that merges at |bb|. 258 void AddNewPhiNodes(BasicBlock* bb, BasicBlock* pred, uint32_t header_id); 259 260 // Saves |block| to a list of basic block that will require OpPhi nodes to be 261 // added by calling |AddNewPhiNodes|. It is assumed that |block| used to have 262 // a single predecessor, |single_original_pred|, but now has more. 263 void MarkForNewPhiNodes(BasicBlock* block, BasicBlock* single_original_pred); 264 265 // Return the original single predcessor of |block| if it was flagged as 266 // having a single predecessor. |nullptr| is returned otherwise. 267 BasicBlock* MarkedSinglePred(BasicBlock* block) { 268 auto it = new_merge_nodes_.find(block); 269 if (it != new_merge_nodes_.end()) { 270 return it->second; 271 } else { 272 return nullptr; 273 } 274 } 275 276 // Modifies existing OpPhi instruction in |target| block to account for the 277 // new edge from |new_source|. The value for that edge will be an Undef. If 278 // |target| only had a single predecessor, then it is marked as needing new 279 // phi nodes. See |MarkForNewPhiNodes|. 280 // 281 // The CFG must not include the edge from |new_source| to |target| yet. 282 void UpdatePhiNodes(BasicBlock* new_source, BasicBlock* target); 283 284 StructuredControlState& CurrentState() { return state_.back(); } 285 286 // Inserts |new_element| into |list| after the first occurrence of |element|. 287 // |element| must be in |list| at least once. 288 void InsertAfterElement(BasicBlock* element, BasicBlock* new_element, 289 std::list<BasicBlock*>* list); 290 291 // Creates a single iteration loop around all of the exectuable code of the 292 // current function and returns after the loop is done. Sets 293 // |final_return_block_|. 294 void AddDummyLoopAroundFunction(); 295 296 // Creates a new basic block that branches to |header_label_id|. Returns the 297 // new basic block. The block will be the second last basic block in the 298 // function. 299 BasicBlock* CreateContinueTarget(uint32_t header_label_id); 300 301 // Creates a loop around the executable code of the function with 302 // |merge_target| as the merge node. 303 void CreateDummyLoop(BasicBlock* merge_target); 304 305 // A stack used to keep track of the innermost contain loop and selection 306 // constructs. 307 std::vector<StructuredControlState> state_; 308 309 // The current function being transformed. 310 Function* function_; 311 312 // The |OpVariable| instruction defining a boolean variable used to keep track 313 // of whether or not the function is trying to return. 314 Instruction* return_flag_; 315 316 // The |OpVariable| instruction defining a variabled to used to keep track of 317 // the value that was returned when passing through a block that use to 318 // contain an |OpReturnValue|. 319 Instruction* return_value_; 320 321 // The instruction defining the boolean constant true. 322 Instruction* constant_true_; 323 324 // The basic block that is suppose to become the contain the only return value 325 // after processing the current function. 326 BasicBlock* final_return_block_; 327 328 // This map contains the set of nodes that use to have a single predcessor, 329 // but now have more. They will need new OpPhi nodes. For each of the nodes, 330 // it is mapped to it original single predcessor. It is assumed there are no 331 // values that will need a phi on the new edges. 332 std::unordered_map<BasicBlock*, BasicBlock*> new_merge_nodes_; 333 bool HasNontrivialUnreachableBlocks(Function* function); 334 }; 335 336 } // namespace opt 337 } // namespace spvtools 338 339 #endif // SOURCE_OPT_MERGE_RETURN_PASS_H_ 340