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