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_OPT_STRUCT_CFG_ANALYSIS_H_ 16 #define SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_ 17 18 #include <unordered_map> 19 #include <unordered_set> 20 21 #include "source/opt/function.h" 22 #include "source/util/bit_vector.h" 23 24 namespace spvtools { 25 namespace opt { 26 27 class IRContext; 28 29 // An analysis that, for each basic block, finds the constructs in which it is 30 // contained, so we can easily get headers and merge nodes. 31 class StructuredCFGAnalysis { 32 public: 33 explicit StructuredCFGAnalysis(IRContext* ctx); 34 35 // Returns the id of the header of the innermost merge construct 36 // that contains |bb_id|. Returns |0| if |bb_id| is not contained in any 37 // merge construct. ContainingConstruct(uint32_t bb_id)38 uint32_t ContainingConstruct(uint32_t bb_id) { 39 auto it = bb_to_construct_.find(bb_id); 40 if (it == bb_to_construct_.end()) { 41 return 0; 42 } 43 return it->second.containing_construct; 44 } 45 46 // Returns the id of the header of the innermost merge construct 47 // that contains |inst|. Returns |0| if |inst| is not contained in any 48 // merge construct. 49 uint32_t ContainingConstruct(Instruction* inst); 50 51 // Returns the id of the merge block of the innermost merge construct 52 // that contains |bb_id|. Returns |0| if |bb_id| is not contained in any 53 // merge construct. 54 uint32_t MergeBlock(uint32_t bb_id); 55 56 // Returns the id of the header of the innermost loop construct 57 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop 58 // construct. ContainingLoop(uint32_t bb_id)59 uint32_t ContainingLoop(uint32_t bb_id) { 60 auto it = bb_to_construct_.find(bb_id); 61 if (it == bb_to_construct_.end()) { 62 return 0; 63 } 64 return it->second.containing_loop; 65 } 66 67 // Returns the id of the merge block of the innermost loop construct 68 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop 69 // construct. 70 uint32_t LoopMergeBlock(uint32_t bb_id); 71 72 // Returns the id of the continue block of the innermost loop construct 73 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop 74 // construct. 75 uint32_t LoopContinueBlock(uint32_t bb_id); 76 77 // Returns the id of the header of the innermost switch construct 78 // that contains |bb_id| as long as there is no intervening loop. Returns |0| 79 // if no such construct exists. ContainingSwitch(uint32_t bb_id)80 uint32_t ContainingSwitch(uint32_t bb_id) { 81 auto it = bb_to_construct_.find(bb_id); 82 if (it == bb_to_construct_.end()) { 83 return 0; 84 } 85 return it->second.containing_switch; 86 } 87 // Returns the id of the merge block of the innermost switch construct 88 // that contains |bb_id| as long as there is no intervening loop. Return |0| 89 // if no such block exists. 90 uint32_t SwitchMergeBlock(uint32_t bb_id); 91 92 // Returns true if |bb_id| is the continue block for a loop. 93 bool IsContinueBlock(uint32_t bb_id); 94 95 // Returns true if |bb_id| is in the continue construct for its inner most 96 // containing loop. 97 bool IsInContainingLoopsContinueConstruct(uint32_t bb_id); 98 99 // Returns true if |bb_id| is in the continue construct for any loop in its 100 // function. 101 bool IsInContinueConstruct(uint32_t bb_id); 102 103 // Return true if |bb_id| is the merge block for a construct. 104 bool IsMergeBlock(uint32_t bb_id); 105 106 // Returns the set of function ids that are called directly or indirectly from 107 // a continue construct. 108 std::unordered_set<uint32_t> FindFuncsCalledFromContinue(); 109 110 private: 111 // Struct used to hold the information for a basic block. 112 // |containing_construct| is the header for the innermost containing 113 // construct, or 0 if no such construct exists. It could be a selection 114 // construct or a loop construct. 115 // 116 // |containing_loop| is the innermost containing loop construct, or 0 if the 117 // basic bloc is not in a loop. If the basic block is in a selection 118 // construct that is contained in a loop construct, then these two values will 119 // not be the same. 120 // 121 // |containing_switch| is the innermost contain selection construct with an 122 // |OpSwitch| for the branch, as long as there is not intervening loop. This 123 // is used to identify the selection construct from which it can break. 124 // 125 // |in_continue| is true of the block is in the continue construct for its 126 // innermost containing loop. 127 struct ConstructInfo { 128 uint32_t containing_construct; 129 uint32_t containing_loop; 130 uint32_t containing_switch; 131 bool in_continue; 132 }; 133 134 // Populates |bb_to_construct_| with the innermost containing merge and loop 135 // constructs for each basic block in |func|. 136 void AddBlocksInFunction(Function* func); 137 138 IRContext* context_; 139 140 // A map from a basic block to the headers of its inner most containing 141 // constructs. 142 std::unordered_map<uint32_t, ConstructInfo> bb_to_construct_; 143 utils::BitVector merge_blocks_; 144 }; 145 146 } // namespace opt 147 } // namespace spvtools 148 #endif // SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_ 149