source/opt/cfg.cpp

   1 // Copyright (c) 2017 Google 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 "cfg.h"
  16 #include "cfa.h"
  17 #include "ir_context.h"
  18 #include "module.h"
  19
  20 namespace spvtools {
  21 namespace ir {
  22
  23 namespace {
  24
  25 // Universal Limit of ResultID + 1
  26 const int kInvalidId = 0x400000;
  27
  28 }  // namespace
  29
  30 CFG::CFG(ir::Module* module)
  31     : module_(module),
  32       pseudo_entry_block_(std::unique_ptr<ir::Instruction>(
  33           new ir::Instruction(module->context(), SpvOpLabel, 0, 0, {}))),
  34       pseudo_exit_block_(std::unique_ptr<ir::Instruction>(new ir::Instruction(
  35           module->context(), SpvOpLabel, 0, kInvalidId, {}))) {
  36   for (auto& fn : *module) {
  37     for (auto& blk : fn) {
  38       RegisterBlock(&blk);
  39     }
  40   }
  41 }
  42
  43 void CFG::AddEdges(ir::BasicBlock* blk) {
  44   uint32_t blk_id = blk->id();
  45   // Force the creation of an entry, not all basic block have predecessors
  46   // (such as the entry blocks and some unreachables).
  47   label2preds_[blk_id];
  48   const auto* const_blk = blk;
  49   const_blk->ForEachSuccessorLabel(
  50       [blk_id, this](const uint32_t succ_id) { AddEdge(blk_id, succ_id); });
  51 }
  52
  53 void CFG::RemoveNonExistingEdges(uint32_t blk_id) {
  54   std::vector<uint32_t> updated_pred_list;
  55   for (uint32_t id : preds(blk_id)) {
  56     const ir::BasicBlock* pred_blk = block(id);
  57     bool has_branch = false;
  58     pred_blk->ForEachSuccessorLabel([&has_branch, blk_id](uint32_t succ) {
  59       if (succ == blk_id) has_branch = true;
  60     });
  61     if (has_branch) updated_pred_list.push_back(id);
  62   }
  63
  64   label2preds_.at(blk_id) = std::move(updated_pred_list);
  65 }
  66
  67 void CFG::ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root,
  68                                  std::list<ir::BasicBlock*>* order) {
  69   assert(module_->context()->get_feature_mgr()->HasCapability(
  70              SpvCapabilityShader) &&
  71          "This only works on structured control flow");
  72
  73   // Compute structured successors and do DFS.
  74   ComputeStructuredSuccessors(func);
  75   auto ignore_block = [](cbb_ptr) {};
  76   auto ignore_edge = [](cbb_ptr, cbb_ptr) {};
  77   auto get_structured_successors = [this](const ir::BasicBlock* b) {
  78     return &(block2structured_succs_[b]);
  79   };
  80
  81   // TODO(greg-lunarg): Get rid of const_cast by making moving const
  82   // out of the cfa.h prototypes and into the invoking code.
  83   auto post_order = [&](cbb_ptr b) {
  84     order->push_front(const_cast<ir::BasicBlock*>(b));
  85   };
  86   spvtools::CFA<ir::BasicBlock>::DepthFirstTraversal(
  87       root, get_structured_successors, ignore_block, post_order, ignore_edge);
  88 }
  89
  90 void CFG::ForEachBlockInReversePostOrder(
  91     BasicBlock* bb, const std::function<void(BasicBlock*)>& f) {
  92   std::vector<BasicBlock*> po;
  93   std::unordered_set<BasicBlock*> seen;
  94   ComputePostOrderTraversal(bb, &po, &seen);
  95
  96   for (auto current_bb = po.rbegin(); current_bb != po.rend(); ++current_bb) {
  97     if (!IsPseudoExitBlock(*current_bb) && !IsPseudoEntryBlock(*current_bb)) {
  98       f(*current_bb);
  99     }
 100   }
 101 }
 102
 103 void CFG::ComputeStructuredSuccessors(ir::Function* func) {
 104   block2structured_succs_.clear();
 105   for (auto& blk : *func) {
 106     // If no predecessors in function, make successor to pseudo entry.
 107     if (label2preds_[blk.id()].size() == 0)
 108       block2structured_succs_[&pseudo_entry_block_].push_back(&blk);
 109
 110     // If header, make merge block first successor and continue block second
 111     // successor if there is one.
 112     uint32_t mbid = blk.MergeBlockIdIfAny();
 113     if (mbid != 0) {
 114       block2structured_succs_[&blk].push_back(id2block_[mbid]);
 115       uint32_t cbid = blk.ContinueBlockIdIfAny();
 116       if (cbid != 0) block2structured_succs_[&blk].push_back(id2block_[cbid]);
 117     }
 118
 119     // Add true successors.
 120     const auto& const_blk = blk;
 121     const_blk.ForEachSuccessorLabel([&blk, this](const uint32_t sbid) {
 122       block2structured_succs_[&blk].push_back(id2block_[sbid]);
 123     });
 124   }
 125 }
 126
 127 void CFG::ComputePostOrderTraversal(BasicBlock* bb, vector<BasicBlock*>* order,
 128                                     unordered_set<BasicBlock*>* seen) {
 129   seen->insert(bb);
 130   static_cast<const BasicBlock*>(bb)->ForEachSuccessorLabel(
 131       [&order, &seen, this](const uint32_t sbid) {
 132         BasicBlock* succ_bb = id2block_[sbid];
 133         if (!seen->count(succ_bb)) {
 134           ComputePostOrderTraversal(succ_bb, order, seen);
 135         }
 136       });
 137   order->push_back(bb);
 138 }
 139
 140 }  // namespace ir
 141 }  // namespace spvtools