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_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_ 16 #define SOURCE_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_ 17 18 #include "source/opt/def_use_manager.h" 19 #include "source/opt/dominator_analysis.h" 20 #include "source/opt/function.h" 21 #include "source/reduce/reduction_opportunity.h" 22 23 namespace spvtools { 24 namespace reduce { 25 26 // An opportunity to replace a structured loop with a selection. 27 class StructuredLoopToSelectionReductionOpportunity 28 : public ReductionOpportunity { 29 public: 30 // Constructs an opportunity from a loop header block and the function that 31 // encloses it. StructuredLoopToSelectionReductionOpportunity(opt::IRContext * context,opt::BasicBlock * loop_construct_header,opt::Function * enclosing_function)32 explicit StructuredLoopToSelectionReductionOpportunity( 33 opt::IRContext* context, opt::BasicBlock* loop_construct_header, 34 opt::Function* enclosing_function) 35 : context_(context), 36 loop_construct_header_(loop_construct_header), 37 enclosing_function_(enclosing_function) {} 38 39 // Returns true if the loop header is reachable. A structured loop might 40 // become unreachable as a result of turning another structured loop into 41 // a selection. 42 bool PreconditionHolds() override; 43 44 protected: 45 void Apply() override; 46 47 private: 48 // Parameter |original_target_id| is the id of the loop's merge block or 49 // continue target. This method considers each edge of the form 50 // b->original_target_id and transforms it into an edge of the form b->c, 51 // where c is the merge block of the structured control flow construct that 52 // most tightly contains b. 53 void RedirectToClosestMergeBlock(uint32_t original_target_id); 54 55 // |source_id|, |original_target_id| and |new_target_id| are required to all 56 // be distinct, with a CFG edge existing from |source_id| to 57 // |original_target_id|, and |original_target_id| being either the merge block 58 // or continue target for the loop being operated on. 59 // The method removes this edge and adds an edge from 60 // |source_id| to |new_target_id|. It takes care of fixing up any OpPhi 61 // instructions associated with |original_target_id| and |new_target_id|. 62 void RedirectEdge(uint32_t source_id, uint32_t original_target_id, 63 uint32_t new_target_id); 64 65 // Adds components to |to_block|'s phi instructions to account for a new 66 // incoming edge from |from_id|. 67 void AdaptPhiInstructionsForAddedEdge(uint32_t from_id, 68 opt::BasicBlock* to_block); 69 70 // Turns the OpLoopMerge for the loop into OpSelectionMerge, and adapts the 71 // following branch instruction accordingly. 72 void ChangeLoopToSelection(); 73 74 // Fixes any scenarios where, due to CFG changes, ids have uses not dominated 75 // by their definitions, by changing such uses to uses of OpUndef or of 76 // placeholder variables. 77 void FixNonDominatedIdUses(); 78 79 // Returns true if and only if at least one of the following holds: 80 // 1) |def| dominates |use| 81 // 2) |def| is an OpVariable 82 // 3) |use| is part of an OpPhi, with associated incoming block b, and |def| 83 // dominates b. 84 bool DefinitionSufficientlyDominatesUse(opt::Instruction* def, 85 opt::Instruction* use, 86 uint32_t use_index, 87 opt::BasicBlock& def_block); 88 89 opt::IRContext* context_; 90 opt::BasicBlock* loop_construct_header_; 91 opt::Function* enclosing_function_; 92 }; 93 94 } // namespace reduce 95 } // namespace spvtools 96 97 #endif // SOURCE_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_ 98