scc.h

// This file if part of the llir-opt project.
// Licensing information can be found in the LICENSE file.
// (C) 2018 Nandor Licker. All rights reserved.
 
#pragma once
 
#include <functional>
#include <stack>
#include <vector>
 
class GraphNode;
class Graph;
 
 
 
class SCCSolver final {
public:
  using SetIter = std::vector<std::unique_ptr<SetNode>>::iterator;
  using Group = std::vector<GraphNode *>;
 
public:
  SCCSolver(Graph *graph);
 
  SCCSolver &Full();
 
  SCCSolver &Single(SetNode *node);
 
  void Solve(std::function<void(const Group &)> &&f);
 
private:
  void VisitFull(GraphNode *node);
 
  void VisitSingle(SetNode *node);
 
  void Pop(GraphNode *node);
 
private:
  Graph *graph_;
  uint32_t epoch_;
  uint32_t index_;
  std::stack<GraphNode *> stack_;
  std::vector<std::vector<GraphNode *>> sccs_;
};