1 /* 2 * Copyright 2016-2021 Arm Limited 3 * SPDX-License-Identifier: Apache-2.0 OR MIT 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 /* 19 * At your option, you may choose to accept this material under either: 20 * 1. The Apache License, Version 2.0, found at <http://www.apache.org/licenses/LICENSE-2.0>, or 21 * 2. The MIT License, found at <http://opensource.org/licenses/MIT>. 22 */ 23 24 #ifndef SPIRV_CROSS_CFG_HPP 25 #define SPIRV_CROSS_CFG_HPP 26 27 #include "spirv_common.hpp" 28 #include <assert.h> 29 30 namespace SPIRV_CROSS_NAMESPACE 31 { 32 class Compiler; 33 class CFG 34 { 35 public: 36 CFG(Compiler &compiler, const SPIRFunction &function); 37 get_compiler()38 Compiler &get_compiler() 39 { 40 return compiler; 41 } 42 get_compiler() const43 const Compiler &get_compiler() const 44 { 45 return compiler; 46 } 47 get_function() const48 const SPIRFunction &get_function() const 49 { 50 return func; 51 } 52 get_immediate_dominator(uint32_t block) const53 uint32_t get_immediate_dominator(uint32_t block) const 54 { 55 auto itr = immediate_dominators.find(block); 56 if (itr != std::end(immediate_dominators)) 57 return itr->second; 58 else 59 return 0; 60 } 61 get_visit_order(uint32_t block) const62 uint32_t get_visit_order(uint32_t block) const 63 { 64 auto itr = visit_order.find(block); 65 assert(itr != std::end(visit_order)); 66 int v = itr->second.get(); 67 assert(v > 0); 68 return uint32_t(v); 69 } 70 71 uint32_t find_common_dominator(uint32_t a, uint32_t b) const; 72 get_preceding_edges(uint32_t block) const73 const SmallVector<uint32_t> &get_preceding_edges(uint32_t block) const 74 { 75 auto itr = preceding_edges.find(block); 76 if (itr != std::end(preceding_edges)) 77 return itr->second; 78 else 79 return empty_vector; 80 } 81 get_succeeding_edges(uint32_t block) const82 const SmallVector<uint32_t> &get_succeeding_edges(uint32_t block) const 83 { 84 auto itr = succeeding_edges.find(block); 85 if (itr != std::end(succeeding_edges)) 86 return itr->second; 87 else 88 return empty_vector; 89 } 90 91 template <typename Op> walk_from(std::unordered_set<uint32_t> & seen_blocks,uint32_t block,const Op & op) const92 void walk_from(std::unordered_set<uint32_t> &seen_blocks, uint32_t block, const Op &op) const 93 { 94 if (seen_blocks.count(block)) 95 return; 96 seen_blocks.insert(block); 97 98 if (op(block)) 99 { 100 for (auto b : get_succeeding_edges(block)) 101 walk_from(seen_blocks, b, op); 102 } 103 } 104 105 uint32_t find_loop_dominator(uint32_t block) const; 106 107 bool node_terminates_control_flow_in_sub_graph(BlockID from, BlockID to) const; 108 109 private: 110 struct VisitOrder 111 { getSPIRV_CROSS_NAMESPACE::CFG::VisitOrder112 int &get() 113 { 114 return v; 115 } 116 getSPIRV_CROSS_NAMESPACE::CFG::VisitOrder117 const int &get() const 118 { 119 return v; 120 } 121 122 int v = -1; 123 }; 124 125 Compiler &compiler; 126 const SPIRFunction &func; 127 std::unordered_map<uint32_t, SmallVector<uint32_t>> preceding_edges; 128 std::unordered_map<uint32_t, SmallVector<uint32_t>> succeeding_edges; 129 std::unordered_map<uint32_t, uint32_t> immediate_dominators; 130 std::unordered_map<uint32_t, VisitOrder> visit_order; 131 SmallVector<uint32_t> post_order; 132 SmallVector<uint32_t> empty_vector; 133 134 void add_branch(uint32_t from, uint32_t to); 135 void build_post_order_visit_order(); 136 void build_immediate_dominators(); 137 bool post_order_visit(uint32_t block); 138 uint32_t visit_count = 0; 139 140 bool is_back_edge(uint32_t to) const; 141 bool has_visited_forward_edge(uint32_t to) const; 142 }; 143 144 class DominatorBuilder 145 { 146 public: 147 DominatorBuilder(const CFG &cfg); 148 149 void add_block(uint32_t block); get_dominator() const150 uint32_t get_dominator() const 151 { 152 return dominator; 153 } 154 155 void lift_continue_block_dominator(); 156 157 private: 158 const CFG &cfg; 159 uint32_t dominator = 0; 160 }; 161 } // namespace SPIRV_CROSS_NAMESPACE 162 163 #endif 164