node.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 <optional>
#include <unordered_set>
#include <utility>
#include <vector>
 
#include <llvm/ADT/ilist.h>
#include <llvm/ADT/ilist_node.h>
#include <llvm/ADT/iterator.h>
#include <llvm/ADT/iterator_range.h>
 
#include "core/adt/bitset.h"
 
 
 
// Forward declaration of item types.
class Extern;
class Func;
 
// Forward declaration of node types.
class RootNode;
class SetNode;
class DerefNode;
class GraphNode;
 
// Forward declaration of the whole graph.
class Graph;
 
// Solver needs access to traversal fields.
class SCCSolver;
 
 
 
class Node {
public:
  enum class Kind {
    SET,
    DEREF,
    ROOT,
  };
 
  virtual ~Node();
 
  GraphNode *ToGraph();
 
  RootNode *AsRoot();
 
protected:
  Node(Kind kind);
 
protected:
  Kind kind_;
};
 
class GraphNode : public Node {
public:
  GraphNode(Kind kind, uint64_t id);
 
  virtual ~GraphNode();
 
  uint64_t GetID() const { return id_; }
 
  bool IsDeref() const { return kind_ == Kind::DEREF; }
  bool IsSet() const { return kind_ == Kind::SET; }
 
  SetNode *AsSet();
  DerefNode *AsDeref();
 
protected:
  friend class SetNode;
  friend class DerefNode;
  uint64_t id_;
 
private:
  friend class SCCSolver;
  uint32_t Epoch;
  uint32_t Index;
  uint32_t Link;
  bool InComponent;
};
 
class SetNode final : public GraphNode {
public:
  SetNode(uint64_t id);
 
  ~SetNode();
 
  DerefNode *Deref();
 
  void AddFunc(ID<Func *> func) { funcs_.Insert(func); }
  void AddExtern(ID<Extern *> ext) { exts_.Insert(ext); }
  void AddNode(ID<SetNode *> node) { nodes_.Insert(node); }
 
  bool Propagate(SetNode *that);
  bool Equals(SetNode *that);
 
  bool AddSet(SetNode *node);
  bool AddDeref(DerefNode *node);
 
  llvm::iterator_range<BitSet<SetNode *>::iterator> sets()
  {
    return llvm::make_range(sets_.begin(), sets_.end());
  }
 
  llvm::iterator_range<BitSet<DerefNode *>::iterator> derefs()
  {
    return llvm::make_range(derefOuts_.begin(), derefOuts_.end());
  }
 
  llvm::iterator_range<BitSet<Func *>::iterator> points_to_func()
  {
    return llvm::make_range(funcs_.begin(), funcs_.end());
  }
 
  llvm::iterator_range<BitSet<Extern *>::iterator> points_to_ext()
  {
    return llvm::make_range(exts_.begin(), exts_.end());
  }
 
  llvm::iterator_range<BitSet<SetNode *>::iterator> points_to_node()
  {
    return llvm::make_range(nodes_.begin(), nodes_.end());
  }
 
  void sets(std::function<ID<SetNode *>(ID<SetNode *>)> &&f);
  void points_to_node(std::function<ID<SetNode *>(ID<SetNode *>)> &&f);
 
private:
  friend class Graph;
  friend class RootNode;
  friend class DerefNode;
 
  DerefNode *deref_;
 
  BitSet<SetNode *> sets_;
  BitSet<DerefNode *> derefIns_;
  BitSet<DerefNode *> derefOuts_;
 
  BitSet<Func *> funcs_;
  BitSet<Extern *> exts_;
  BitSet<SetNode *> nodes_;
};
 
class DerefNode final : public GraphNode {
public:
  DerefNode(SetNode *node, RootNode *contents, uint64_t id);
 
  ~DerefNode();
 
  SetNode *Node() const { return node_; }
  SetNode *Contents();
 
  bool AddSet(SetNode *node);
 
  llvm::iterator_range<BitSet<SetNode *>::iterator> set_ins()
  {
    return llvm::make_range(setIns_.begin(), setIns_.end());
  }
 
  llvm::iterator_range<BitSet<SetNode *>::iterator> set_outs()
  {
    return llvm::make_range(setOuts_.begin(), setOuts_.end());
  }
 
  void set_ins(std::function<ID<SetNode *>(ID<SetNode *>)> &&f);
  void set_outs(std::function<ID<SetNode *>(ID<SetNode *>)> &&f);
 
private:
  friend class Graph;
  friend class SetNode;
 
  SetNode *node_;
  RootNode *contents_;
 
  BitSet<SetNode *> setIns_;
  BitSet<SetNode *> setOuts_;
};
 
class RootNode : public Node {
public:
  RootNode(Graph *graph, SetNode *actual);
 
  SetNode *Set() const;
 
private:
  friend class Node;
  friend class SetNode;
  friend class DerefNode;
 
  Graph *graph_;
  mutable uint32_t id_;
};