symbolic_pointer.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 <optional>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <variant>
 
#include <llvm/Support/raw_ostream.h>
 
#include "core/adt/id.h"
#include "core/adt/hash.h"
#include "core/adt/bitset.h"
 
class Block;
class CallSite;
class Extern;
class Func;
class Atom;
class SymbolicObject;
class SymbolicFrame;
 
 
 
class SymbolicAddress final {
public:
  enum class Kind : uint8_t {
    OBJECT,
    OBJECT_RANGE,
    EXTERN,
    EXTERN_RANGE,
    FUNC,
    BLOCK,
    STACK,
  };
 
  class AddrObject {
  public:
    Kind K;
    ID<SymbolicObject> Object;
    int64_t Offset;
 
  private:
    friend class SymbolicAddress;
 
    AddrObject(ID<SymbolicObject> object, int64_t offset)
        : K(Kind::OBJECT), Object(object), Offset(offset)
    {
    }
  };
 
  class AddrObjectRange {
  public:
    Kind K;
    ID<SymbolicObject> Object;
 
  private:
    friend class SymbolicAddress;
 
    AddrObjectRange(ID<SymbolicObject> object)
        : K(Kind::OBJECT_RANGE), Object(object)
    {
    }
  };
 
  class AddrExtern {
  public:
    Kind K;
    Extern *Symbol;
    int64_t Offset;
 
  private:
    friend class SymbolicAddress;
 
    AddrExtern(Extern *symbol, int64_t offset)
        : K(Kind::EXTERN), Symbol(symbol), Offset(offset)
    {
    }
  };
 
  class AddrExternRange {
  public:
    Kind K;
    Extern *Symbol;
 
  private:
    friend class SymbolicAddress;
 
    AddrExternRange(Extern *symbol)
        : K(Kind::EXTERN_RANGE), Symbol(symbol)
    {
    }
  };
 
  class AddrFunc {
  public:
    Kind K;
    ID<Func> F;
 
  private:
    friend class SymbolicAddress;
 
    AddrFunc(ID<Func> func) : K(Kind::FUNC), F(func) { }
  };
 
  class AddrBlock {
  public:
    Kind K;
    Block *B;
 
  private:
    friend class SymbolicAddress;
 
    AddrBlock(Block *block) : K(Kind::BLOCK), B(block) { }
  };
 
  class AddrStack {
  public:
    Kind K;
    ID<SymbolicFrame> Frame;
 
  private:
    friend class SymbolicAddress;
 
    AddrStack(ID<SymbolicFrame> frame) : K(Kind::STACK), Frame(frame) { }
  };
 
public:
  SymbolicAddress(
      const std::pair
        < std::unordered_map<int64_t, BitSet<SymbolicObject>>::const_iterator
        , BitSet<SymbolicObject>::iterator> &arg)
      : v_(*arg.second, arg.first->first)
  {
  }
 
  SymbolicAddress(BitSet<SymbolicObject>::iterator arg)
    : v_(*arg)
  {
  }
  SymbolicAddress(std::unordered_map<Extern *, int64_t>::const_iterator arg)
    : v_(arg->first, arg->second)
  {
  }
  SymbolicAddress(std::unordered_set<Extern *>::const_iterator arg)
    : v_(*arg)
  {
  }
  SymbolicAddress(BitSet<Func>::iterator func)
    : v_(*func)
  {
  }
  SymbolicAddress(std::unordered_set<Block *>::const_iterator block)
    : v_(*block)
  {
  }
  SymbolicAddress(BitSet<SymbolicFrame>::iterator stack)
    : v_(*stack)
  {
  }
 
  Kind GetKind() const { return v_.K; }
 
  const AddrObject &AsObject() const { return v_.O; }
  const AddrObjectRange &AsObjectRange() const { return v_.OR; }
  const AddrExtern &AsExtern() const { return v_.E; }
  const AddrExternRange &AsExternRange() const { return v_.ER; }
  const AddrFunc &AsFunc() const { return v_.F; }
  const AddrBlock &AsBlock() const { return v_.B; }
  const AddrStack &AsStack() const { return v_.S; }
 
  bool IsPrecise() const;
 
  const AddrObject *ToObject() const
  {
    return v_.K == Kind::OBJECT ? &v_.O : nullptr;
  }
 
  const AddrObjectRange *ToObjectRange() const
  {
    return v_.K == Kind::OBJECT_RANGE ? &v_.OR : nullptr;
  }
 
  bool operator==(const SymbolicAddress &that) const;
 
  void dump(llvm::raw_ostream &os) const;
 
private:
  union P {
    Kind K;
    AddrObject O;
    AddrObjectRange OR;
    AddrExtern E;
    AddrExternRange ER;
    AddrFunc F;
    AddrBlock B;
    AddrStack S;
 
    P(ID<SymbolicObject> object, int64_t offset) : O(object, offset) { }
    P(ID<SymbolicObject> object) : OR(object) { }
 
    P(Extern *symbol, int64_t off) : E(symbol, off) { }
    P(Extern *symbol) : ER(symbol) { }
 
    P(ID<Func> func) : F(func) { }
    P(Block *block) : B(block) { }
    P(ID<SymbolicFrame> stack) : S(stack) { }
  } v_;
};
 
inline llvm::raw_ostream &operator<<(
    llvm::raw_ostream &os,
    const SymbolicAddress &address)
{
  address.dump(os);
  return os;
}
 
 
class SymbolicPointer final {
public:
  using Ref = std::shared_ptr<SymbolicPointer>;
 
  using ObjectMap = std::unordered_map<int64_t, BitSet<SymbolicObject>>;
  using ObjectRangeMap = BitSet<SymbolicObject>;
  using ExternMap = std::unordered_map<Extern *, int64_t>;
  using ExternRangeMap = std::unordered_set<Extern *>;
  using FuncMap = BitSet<Func>;
  using BlockMap = std::unordered_set<Block *>;
  using StackMap = BitSet<SymbolicFrame>;
 
  class address_iterator : public std::iterator
    < std::forward_iterator_tag
    , SymbolicAddress
    >
  {
  public:
    address_iterator() : pointer_(nullptr) {}
 
    template <typename It>
    address_iterator(It it, const SymbolicPointer *pointer)
      : pointer_(pointer)
      , it_(it)
      , current_(SymbolicAddress(it))
    {
    }
 
    bool operator==(const address_iterator &that) const
    {
      return current_ == that.current_;
    }
    bool operator!=(const address_iterator &that) const
    {
      return !(*this == that);
    }
 
    address_iterator &operator++();
    address_iterator operator++(int)
    {
      auto tmp = *this;
      ++*this;
      return tmp;
    }
 
    const SymbolicAddress &operator*() const { return *current_; }
    const SymbolicAddress *operator->() const { return &operator*(); }
 
  private:
    const SymbolicPointer *pointer_;
    std::optional<SymbolicAddress> current_;
    std::optional<std::variant<
        std::pair<ObjectMap::const_iterator, BitSet<SymbolicObject>::iterator>,
        ObjectRangeMap::iterator,
        ExternMap::const_iterator,
        ExternRangeMap::const_iterator,
        FuncMap::iterator,
        BlockMap::const_iterator,
        StackMap::iterator
    >> it_;
  };
 
  using func_iterator = FuncMap::iterator;
  using block_iterator = BlockMap::const_iterator;
  using stack_iterator = StackMap::iterator;
 
public:
  SymbolicPointer();
  SymbolicPointer(ID<SymbolicObject> object, int64_t offset);
  SymbolicPointer(Extern *object, int64_t offset);
  SymbolicPointer(ID<Func> func);
  SymbolicPointer(Block *block);
  SymbolicPointer(ID<SymbolicFrame> frame);
  ~SymbolicPointer();
 
  bool operator==(const SymbolicPointer &that) const;
 
  void Add(ID<SymbolicObject> object) { objectRanges_.Insert(object); }
  void Add(ID<SymbolicObject> object, int64_t offset);
  void Add(Extern *e, int64_t offset);
  void Add(Extern *e) { externRanges_.insert(e); }
  void Add(ID<Func> f) { funcPointers_.Insert(f); }
  void Add(const BitSet<Func> &funcs) { funcPointers_.Union(funcs); }
  void Add(Block *b) { blockPointers_.insert(b); }
  void Add(ID<SymbolicFrame> frame) { stackPointers_.Insert(frame); }
  void Add(const BitSet<SymbolicFrame> &frames) { stackPointers_.Union(frames); }
  void Add(const BitSet<SymbolicObject> &range) { objectRanges_.Union(range); }
 
  Ref Offset(int64_t offset) const;
  Ref Decay() const;
 
  void Merge(const Ref &that);
 
  [[nodiscard]] Ref LUB(const Ref &that) const
  {
    Ref lub = std::make_shared<SymbolicPointer>(*this);
    lub->Merge(that);
    return lub;
  }
 
  void dump(llvm::raw_ostream &os) const;
 
  bool empty() const { return begin() == end(); }
  address_iterator begin() const;
  address_iterator end() const { return address_iterator(); }
 
  size_t func_size() const { return funcPointers_.Size(); }
  func_iterator func_begin() const { return funcPointers_.begin(); }
  func_iterator func_end() const { return funcPointers_.end(); }
  llvm::iterator_range<func_iterator> funcs() const
  {
    return llvm::make_range(func_begin(), func_end());
  }
 
  size_t block_size() const { return std::distance(block_begin(), block_end()); }
  block_iterator block_begin() const { return blockPointers_.begin(); }
  block_iterator block_end() const { return blockPointers_.end(); }
  llvm::iterator_range<block_iterator> blocks() const
  {
    return llvm::make_range(block_begin(), block_end());
  }
 
  size_t stack_size() const { return stackPointers_.Size(); }
  stack_iterator stack_begin() const { return stackPointers_.begin(); }
  stack_iterator stack_end() const { return stackPointers_.end(); }
  llvm::iterator_range<stack_iterator> stacks() const
  {
    return llvm::make_range(stack_begin(), stack_end());
  }
 
private:
  friend class address_iterator;
  ObjectMap objectPointers_;
  ObjectRangeMap objectRanges_;
  ExternMap externPointers_;
  ExternRangeMap externRanges_;
  FuncMap funcPointers_;
  BlockMap blockPointers_;
  StackMap stackPointers_;
};
 
inline llvm::raw_ostream &operator<<(
    llvm::raw_ostream &os,
    const SymbolicPointer &sym)
{
  sym.dump(os);
  return os;
}