spirv_cfg.hpp

   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
  38         Compiler &get_compiler()
  39         {
  40                 return compiler;
  41         }
  42
  43         const Compiler &get_compiler() const
  44         {
  45                 return compiler;
  46         }
  47
  48         const SPIRFunction &get_function() const
  49         {
  50                 return func;
  51         }
  52
  53         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
  62         bool is_reachable(uint32_t block) const
  63         {
  64                 return visit_order.count(block) != 0;
  65         }
  66
  67         uint32_t get_visit_order(uint32_t block) const
  68         {
  69                 auto itr = visit_order.find(block);
  70                 assert(itr != std::end(visit_order));
  71                 int v = itr->second.get();
  72                 assert(v > 0);
  73                 return uint32_t(v);
  74         }
  75
  76         uint32_t find_common_dominator(uint32_t a, uint32_t b) const;
  77
  78         const SmallVector<uint32_t> &get_preceding_edges(uint32_t block) const
  79         {
  80                 auto itr = preceding_edges.find(block);
  81                 if (itr != std::end(preceding_edges))
  82                         return itr->second;
  83                 else
  84                         return empty_vector;
  85         }
  86
  87         const SmallVector<uint32_t> &get_succeeding_edges(uint32_t block) const
  88         {
  89                 auto itr = succeeding_edges.find(block);
  90                 if (itr != std::end(succeeding_edges))
  91                         return itr->second;
  92                 else
  93                         return empty_vector;
  94         }
  95
  96         template <typename Op>
  97         void walk_from(std::unordered_set<uint32_t> &seen_blocks, uint32_t block, const Op &op) const
  98         {
  99                 if (seen_blocks.count(block))
 100                         return;
 101                 seen_blocks.insert(block);
 102
 103                 if (op(block))
 104                 {
 105                         for (auto b : get_succeeding_edges(block))
 106                                 walk_from(seen_blocks, b, op);
 107                 }
 108         }
 109
 110         uint32_t find_loop_dominator(uint32_t block) const;
 111
 112         bool node_terminates_control_flow_in_sub_graph(BlockID from, BlockID to) const;
 113
 114 private:
 115         struct VisitOrder
 116         {
 117                 int &get()
 118                 {
 119                         return v;
 120                 }
 121
 122                 const int &get() const
 123                 {
 124                         return v;
 125                 }
 126
 127                 int v = -1;
 128         };
 129
 130         Compiler &compiler;
 131         const SPIRFunction &func;
 132         std::unordered_map<uint32_t, SmallVector<uint32_t>> preceding_edges;
 133         std::unordered_map<uint32_t, SmallVector<uint32_t>> succeeding_edges;
 134         std::unordered_map<uint32_t, uint32_t> immediate_dominators;
 135         std::unordered_map<uint32_t, VisitOrder> visit_order;
 136         SmallVector<uint32_t> post_order;
 137         SmallVector<uint32_t> empty_vector;
 138
 139         void add_branch(uint32_t from, uint32_t to);
 140         void build_post_order_visit_order();
 141         void build_immediate_dominators();
 142         bool post_order_visit(uint32_t block);
 143         uint32_t visit_count = 0;
 144
 145         bool is_back_edge(uint32_t to) const;
 146         bool has_visited_forward_edge(uint32_t to) const;
 147 };
 148
 149 class DominatorBuilder
 150 {
 151 public:
 152         DominatorBuilder(const CFG &cfg);
 153
 154         void add_block(uint32_t block);
 155         uint32_t get_dominator() const
 156         {
 157                 return dominator;
 158         }
 159
 160         void lift_continue_block_dominator();
 161
 162 private:
 163         const CFG &cfg;
 164         uint32_t dominator = 0;
 165 };
 166 } // namespace SPIRV_CROSS_NAMESPACE
 167
 168 #endif