Home | History | Annotate | Download | only in val 
      1 // Copyright (c) 2015-2016 The Khronos Group Inc.
      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 #include "val/basic_block.h"
     16 
     17 #include <algorithm>
     18 #include <utility>
     19 #include <vector>
     20 
     21 using std::vector;
     22 
     23 namespace libspirv {
     24 
     25 BasicBlock::BasicBlock(uint32_t label_id)
     26     : id_(label_id),
     27       immediate_dominator_(nullptr),
     28       immediate_post_dominator_(nullptr),
     29       predecessors_(),
     30       successors_(),
     31       type_(0),
     32       reachable_(false) {}
     33 
     34 void BasicBlock::SetImmediateDominator(BasicBlock* dom_block) {
     35   immediate_dominator_ = dom_block;
     36 }
     37 
     38 void BasicBlock::SetImmediatePostDominator(BasicBlock* pdom_block) {
     39   immediate_post_dominator_ = pdom_block;
     40 }
     41 
     42 const BasicBlock* BasicBlock::immediate_dominator() const {
     43   return immediate_dominator_;
     44 }
     45 
     46 const BasicBlock* BasicBlock::immediate_post_dominator() const {
     47   return immediate_post_dominator_;
     48 }
     49 
     50 BasicBlock* BasicBlock::immediate_dominator() { return immediate_dominator_; }
     51 BasicBlock* BasicBlock::immediate_post_dominator() {
     52   return immediate_post_dominator_;
     53 }
     54 
     55 void BasicBlock::RegisterSuccessors(const vector<BasicBlock*>& next_blocks) {
     56   for (auto& block : next_blocks) {
     57     block->predecessors_.push_back(this);
     58     successors_.push_back(block);
     59     if (block->reachable_ == false) block->set_reachable(reachable_);
     60   }
     61 }
     62 
     63 void BasicBlock::RegisterBranchInstruction(SpvOp branch_instruction) {
     64   if (branch_instruction == SpvOpUnreachable) reachable_ = false;
     65   return;
     66 }
     67 
     68 bool BasicBlock::dominates(const BasicBlock& other) const {
     69   return (this == &other) ||
     70          !(other.dom_end() ==
     71            std::find(other.dom_begin(), other.dom_end(), this));
     72 }
     73 
     74 bool BasicBlock::postdominates(const BasicBlock& other) const {
     75   return (this == &other) ||
     76          !(other.pdom_end() ==
     77            std::find(other.pdom_begin(), other.pdom_end(), this));
     78 }
     79 
     80 BasicBlock::DominatorIterator::DominatorIterator() : current_(nullptr) {}
     81 
     82 BasicBlock::DominatorIterator::DominatorIterator(
     83     const BasicBlock* block,
     84     std::function<const BasicBlock*(const BasicBlock*)> dominator_func)
     85     : current_(block), dom_func_(dominator_func) {}
     86 
     87 BasicBlock::DominatorIterator& BasicBlock::DominatorIterator::operator++() {
     88   if (current_ == dom_func_(current_)) {
     89     current_ = nullptr;
     90   } else {
     91     current_ = dom_func_(current_);
     92   }
     93   return *this;
     94 }
     95 
     96 const BasicBlock::DominatorIterator BasicBlock::dom_begin() const {
     97   return DominatorIterator(
     98       this, [](const BasicBlock* b) { return b->immediate_dominator(); });
     99 }
    100 
    101 BasicBlock::DominatorIterator BasicBlock::dom_begin() {
    102   return DominatorIterator(
    103       this, [](const BasicBlock* b) { return b->immediate_dominator(); });
    104 }
    105 
    106 const BasicBlock::DominatorIterator BasicBlock::dom_end() const {
    107   return DominatorIterator();
    108 }
    109 
    110 BasicBlock::DominatorIterator BasicBlock::dom_end() {
    111   return DominatorIterator();
    112 }
    113 
    114 const BasicBlock::DominatorIterator BasicBlock::pdom_begin() const {
    115   return DominatorIterator(
    116       this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
    117 }
    118 
    119 BasicBlock::DominatorIterator BasicBlock::pdom_begin() {
    120   return DominatorIterator(
    121     this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
    122 }
    123 
    124 const BasicBlock::DominatorIterator BasicBlock::pdom_end() const {
    125   return DominatorIterator();
    126 }
    127 
    128 BasicBlock::DominatorIterator BasicBlock::pdom_end() {
    129   return DominatorIterator();
    130 }
    131 
    132 bool operator==(const BasicBlock::DominatorIterator& lhs,
    133                 const BasicBlock::DominatorIterator& rhs) {
    134   return lhs.current_ == rhs.current_;
    135 }
    136 
    137 bool operator!=(const BasicBlock::DominatorIterator& lhs,
    138                 const BasicBlock::DominatorIterator& rhs) {
    139   return !(lhs == rhs);
    140 }
    141 
    142 const BasicBlock*& BasicBlock::DominatorIterator::operator*() {
    143   return current_;
    144 }
    145 }  // namespace libspirv
    146