forwarder.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 "core/adt/bitset.h"
#include "core/prog.h"
#include "core/func.h"
#include "core/dag.h"
#include "core/inst_visitor.h"
#include "passes/global_forward/nodes.h"
 
class MovInst;
 
 
 
class GlobalForwarder final {
public:
  GlobalForwarder(Prog &prog, Func &entry);
 
  bool Forward();
  bool Reverse();
 
private:
  struct FuncState {
    DAGFunc &DAG;
    unsigned Active;
    unsigned Accurate;
    std::unordered_map<unsigned, std::unique_ptr<NodeState>> States;
 
    FuncState(DAGFunc &dag)
      : DAG(dag)
      , Active(dag.rbegin()->Index)
      , Accurate(Active)
    {
    }
 
    NodeState &GetState(unsigned index)
    {
      auto it = States.emplace(index, nullptr);
      if (it.second) {
        it.first->second.reset(new NodeState());
      }
      return *it.first->second;
    }
  };
 
  class Approximator : public InstVisitor<void> {
  public:
    Approximator(GlobalForwarder &state) : state_(state) {}
 
    void VisitInst(Inst &inst) override { }
 
    void VisitMovInst(MovInst &mov) override;
    void VisitMemoryStoreInst(MemoryStoreInst &store) override;
    void VisitMemoryLoadInst(MemoryLoadInst &load) override;
    void VisitCallSite(CallSite &site) override;
    void VisitTrapInst(TrapInst &) override { }
    void VisitRaiseInst(RaiseInst &raise) override { Raises = true; }
 
  public:
    bool Raises = false;
    bool Indirect = false;
    BitSet<Func> Funcs;
    BitSet<Object> Escaped;
    BitSet<Object> Loaded;
    BitSet<Object> Stored;
 
  private:
    GlobalForwarder &state_;
  };
 
  class Simplifier final : public InstVisitor<bool> {
  public:
    Simplifier(
        GlobalForwarder &state,
        NodeState &node,
        ReverseNodeState &reverse)
      : state_(state)
      , node_(node)
      , reverse_(reverse)
    {
    }
 
    bool VisitInst(Inst &inst) override { return false; }
 
    bool VisitAddInst(AddInst &add) override;
    bool VisitMovInst(MovInst &mov) override;
    bool VisitMemoryStoreInst(MemoryStoreInst &store) override;
    bool VisitMemoryLoadInst(MemoryLoadInst &load) override;
    bool VisitMemoryExchangeInst(MemoryExchangeInst &xchg) override;
 
    bool VisitTerminatorInst(TerminatorInst &) override
    {
      llvm_unreachable("cannot evaluate terminator");
    }
 
  protected:
    GlobalForwarder &state_;
    NodeState &node_;
    ReverseNodeState &reverse_;
  };
 
 
private:
  void Escape(BitSet<Func> &funcs, BitSet<Object> &escaped, MovInst &mov);
  void Indirect(
      BitSet<Func> &funcs,
      BitSet<Object> &escaped,
      BitSet<Object> &storedImprecise,
      BitSet<Object> &loadedImprecise,
      bool &raises
  );
  void Raise(NodeState &node, ReverseNodeState &reverse);
 
  ID<Func> GetFuncID(Func &func)
  {
    auto it = funcToID_.find(&func);
    assert(it != funcToID_.end() && "missing function");
    return it->second;
  }
 
  ID<Object> GetObjectID(Object *object)
  {
    auto it = objectToID_.find(object);
    assert(it != objectToID_.end() && "missing object");
    return it->second;
  }
 
  DAGFunc &GetDAG(Func &func)
  {
    auto &dag = funcs_[GetFuncID(func)]->DAG;
    if (!dag) {
      dag.reset(new DAGFunc(func));
    }
    return *dag;
  }
 
  ReverseNodeState &GetReverseNode(Func &func, unsigned index)
  {
    std::pair<Func *, unsigned> key(&func, index);
    auto it = reverse_.emplace(key, nullptr);
    if (it.second) {
      it.first->second.reset(new ReverseNodeState(*(GetDAG(func)[index])));
    }
    return *it.first->second;
  }
 
private:
  Prog &prog_;
  Func &entry_;
 
  std::unordered_map<Object *, ID<Object>> objectToID_;
  std::vector<std::unique_ptr<ObjectClosure>> objects_;
  std::vector<Object *> idToObject_;
 
  std::unordered_map<Func *, ID<Func>> funcToID_;
  std::vector<std::unique_ptr<FuncClosure>> funcs_;
 
  std::unordered_map
    < std::pair<Func *, unsigned>
    , std::unique_ptr<ReverseNodeState>
    > reverse_;
 
  std::vector<FuncState> stack_;
};