source/opt/dominator_analysis.h

// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef SOURCE_OPT_DOMINATOR_ANALYSIS_H_
#define SOURCE_OPT_DOMINATOR_ANALYSIS_H_

#include <cstdint>
#include <map>

#include "source/opt/dominator_tree.h"

namespace spvtools {
namespace opt {

// Interface to perform dominator or postdominator analysis on a given function.
class DominatorAnalysisBase {
 public:
  explicit DominatorAnalysisBase(bool is_post_dom) : tree_(is_post_dom) {}

  // Calculates the dominator (or postdominator) tree for given function |f|.
  inline void InitializeTree(const CFG& cfg, const Function* f) {
    tree_.InitializeTree(cfg, f);
  }

  // Returns true if BasicBlock |a| dominates BasicBlock |b|.
  inline bool Dominates(const BasicBlock* a, const BasicBlock* b) const {
    if (!a || !b) return false;
    return Dominates(a->id(), b->id());
  }

  // Returns true if BasicBlock |a| dominates BasicBlock |b|. Same as above only
  // using the BasicBlock IDs.
  inline bool Dominates(uint32_t a, uint32_t b) const {
    return tree_.Dominates(a, b);
  }

  // Returns true if instruction |a| dominates instruction |b|.
  bool Dominates(Instruction* a, Instruction* b) const;

  // Returns true if BasicBlock |a| strictly dominates BasicBlock |b|.
  inline bool StrictlyDominates(const BasicBlock* a,
                                const BasicBlock* b) const {
    if (!a || !b) return false;
    return StrictlyDominates(a->id(), b->id());
  }

  // Returns true if BasicBlock |a| strictly dominates BasicBlock |b|. Same as
  // above only using the BasicBlock IDs.
  inline bool StrictlyDominates(uint32_t a, uint32_t b) const {
    return tree_.StrictlyDominates(a, b);
  }

  // Returns the immediate dominator of |node| or returns nullptr if it is has
  // no dominator.
  inline BasicBlock* ImmediateDominator(const BasicBlock* node) const {
    if (!node) return nullptr;
    return tree_.ImmediateDominator(node);
  }

  // Returns the immediate dominator of |node_id| or returns nullptr if it is
  // has no dominator. Same as above but operates on IDs.
  inline BasicBlock* ImmediateDominator(uint32_t node_id) const {
    return tree_.ImmediateDominator(node_id);
  }

  // Returns true if |node| is reachable from the entry.
  inline bool IsReachable(const BasicBlock* node) const {
    if (!node) return false;
    return tree_.ReachableFromRoots(node->id());
  }

  // Returns true if |node_id| is reachable from the entry.
  inline bool IsReachable(uint32_t node_id) const {
    return tree_.ReachableFromRoots(node_id);
  }

  // Dump the tree structure into the given |out| stream in the dot format.
  inline void DumpAsDot(std::ostream& out) const { tree_.DumpTreeAsDot(out); }

  // Returns true if this is a postdomiator tree.
  inline bool IsPostDominator() const { return tree_.IsPostDominator(); }

  // Returns the tree itself for manual operations, such as traversing the
  // roots.
  // For normal dominance relationships the methods above should be used.
  inline DominatorTree& GetDomTree() { return tree_; }
  inline const DominatorTree& GetDomTree() const { return tree_; }

  // Force the dominator tree to be removed
  inline void ClearTree() { tree_.ClearTree(); }

  // Applies the std::function |func| to dominator tree nodes in dominator
  // order.
  void Visit(std::function<bool(DominatorTreeNode*)> func) {
    tree_.Visit(func);
  }

  // Applies the std::function |func| to dominator tree nodes in dominator
  // order.
  void Visit(std::function<bool(const DominatorTreeNode*)> func) const {
    tree_.Visit(func);
  }

  // Returns the most immediate basic block that dominates both |b1| and |b2|.
  // If there is no such basic block, nullptr is returned.
  BasicBlock* CommonDominator(BasicBlock* b1, BasicBlock* b2) const;

 protected:
  DominatorTree tree_;
};

// Derived class for normal dominator analysis.
class DominatorAnalysis : public DominatorAnalysisBase {
 public:
  DominatorAnalysis() : DominatorAnalysisBase(false) {}
};

// Derived class for postdominator analysis.
class PostDominatorAnalysis : public DominatorAnalysisBase {
 public:
  PostDominatorAnalysis() : DominatorAnalysisBase(true) {}
};

}  // namespace opt
}  // namespace spvtools

#endif  // SOURCE_OPT_DOMINATOR_ANALYSIS_H_