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