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) {
  60         has_branch = true;
  61       }
  62     });
  63     if (has_branch) updated_pred_list.push_back(id);
  64   }
  65
  66   label2preds_.at(blk_id) = std::move(updated_pred_list);
  67 }
  68
  69 void CFG::ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root,
  70                                  std::list<ir::BasicBlock*>* order) {
  71   assert(module_->context()->get_feature_mgr()->HasCapability(
  72              SpvCapabilityShader) &&
  73          "This only works on structured control flow");
  74
  75   // Compute structured successors and do DFS.
  76   ComputeStructuredSuccessors(func);
  77   auto ignore_block = [](cbb_ptr) {};
  78   auto ignore_edge = [](cbb_ptr, cbb_ptr) {};
  79   auto get_structured_successors = [this](const ir::BasicBlock* b) {
  80     return &(block2structured_succs_[b]);
  81   };
  82
  83   // TODO(greg-lunarg): Get rid of const_cast by making moving const
  84   // out of the cfa.h prototypes and into the invoking code.
  85   auto post_order = [&](cbb_ptr b) {
  86     order->push_front(const_cast<ir::BasicBlock*>(b));
  87   };
  88   spvtools::CFA<ir::BasicBlock>::DepthFirstTraversal(
  89       root, get_structured_successors, ignore_block, post_order, ignore_edge);
  90 }
  91
  92 void CFG::ForEachBlockInReversePostOrder(
  93     BasicBlock* bb, const std::function<void(BasicBlock*)>& f) {
  94   std::vector<BasicBlock*> po;
  95   std::unordered_set<BasicBlock*> seen;
  96   ComputePostOrderTraversal(bb, &po, &seen);
  97
  98   for (auto current_bb = po.rbegin(); current_bb != po.rend(); ++current_bb) {
  99     if (!IsPseudoExitBlock(*current_bb) && !IsPseudoEntryBlock(*current_bb)) {
 100       f(*current_bb);
 101     }
 102   }
 103 }
 104
 105 void CFG::ComputeStructuredSuccessors(ir::Function* func) {
 106   block2structured_succs_.clear();
 107   for (auto& blk : *func) {
 108     // If no predecessors in function, make successor to pseudo entry.
 109     if (label2preds_[blk.id()].size() == 0)
 110       block2structured_succs_[&pseudo_entry_block_].push_back(&blk);
 111
 112     // If header, make merge block first successor and continue block second
 113     // successor if there is one.
 114     uint32_t mbid = blk.MergeBlockIdIfAny();
 115     if (mbid != 0) {
 116       block2structured_succs_[&blk].push_back(id2block_[mbid]);
 117       uint32_t cbid = blk.ContinueBlockIdIfAny();
 118       if (cbid != 0) block2structured_succs_[&blk].push_back(id2block_[cbid]);
 119     }
 120
 121     // Add true successors.
 122     const auto& const_blk = blk;
 123     const_blk.ForEachSuccessorLabel([&blk, this](const uint32_t sbid) {
 124       block2structured_succs_[&blk].push_back(id2block_[sbid]);
 125     });
 126   }
 127 }
 128
 129 void CFG::ComputePostOrderTraversal(BasicBlock* bb, vector<BasicBlock*>* order,
 130                                     unordered_set<BasicBlock*>* seen) {
 131   seen->insert(bb);
 132   static_cast<const BasicBlock*>(bb)->ForEachSuccessorLabel(
 133       [&order, &seen, this](const uint32_t sbid) {
 134         BasicBlock* succ_bb = id2block_[sbid];
 135         if (!seen->count(succ_bb)) {
 136           ComputePostOrderTraversal(succ_bb, order, seen);
 137         }
 138       });
 139   order->push_back(bb);
 140 }
 141
 142 }  // namespace ir
 143 }  // namespace spvtools