solver.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.
 
#include <set>
#include <queue>
 
#include "core/block.h"
#include "core/cast.h"
#include "core/constant.h"
#include "core/func.h"
#include "core/inst_visitor.h"
#include "core/insts.h"
#include "core/prog.h"
#include "passes/sccp/lattice.h"
 
class Target;
 
 
 
class SCCPSolver : InstVisitor<void> {
public:
  SCCPSolver(Prog &prog, const Target *target);
 
  Lattice &GetValue(Ref<Inst> inst);
  bool IsExecutable(const Block &block) { return executable_.count(&block); }
 
private:
  void Visit(Block *block)
  {
    for (auto &inst : *block) {
      Visit(inst);
    }
  }
 
  void Visit(Inst &inst)
  {
    assert(executable_.count(inst.getParent()) && "bb not yet visited");
    Dispatch(inst);
  }
 
  bool CanEvaluate(CallSite &site);
  void MarkOverdefinedCall(TailCallInst &site);
  void MarkCall(CallSite &site, Func &callee, Block *cont);
 
  bool MarkBlock(Block *block);
  bool MarkEdge(Inst &inst, Block *to);
  bool MarkOverdefined(Inst &inst)
  {
    bool changed = false;
    for (unsigned i = 0, n = inst.GetNumRets(); i < n; ++i) {
      changed |= Mark(inst.GetSubValue(i), Lattice::Overdefined());
    }
    return changed;
  }
  bool Mark(Ref<Inst> inst, const Lattice &value);
  bool Mark(Ref<Inst> inst, bool flag);
 
private:
  void VisitArgInst(ArgInst &inst) override;
  void VisitCallInst(CallInst &inst) override;
  void VisitTailCallInst(TailCallInst &inst) override;
  void VisitInvokeInst(InvokeInst &inst) override;
  void VisitReturnInst(ReturnInst &inst) override;
  void VisitLoadInst(LoadInst &inst) override;
  void VisitBinaryInst(BinaryInst &inst) override;
  void VisitCmpInst(CmpInst &inst) override;
  void VisitUnaryInst(UnaryInst &inst) override;
  void VisitJumpInst(JumpInst &inst) override;
  void VisitJumpCondInst(JumpCondInst &inst) override;
  void VisitSwitchInst(SwitchInst &inst) override;
  void VisitSelectInst(SelectInst &inst) override;
  void VisitFrameInst(FrameInst &inst) override;
  void VisitMovInst(MovInst &inst) override;
  void VisitUndefInst(UndefInst &inst) override;
  void VisitPhiInst(PhiInst &inst) override;
  void VisitInst(Inst &inst) override;
 
  void VisitX86_CpuIdInst(X86_CpuIdInst &inst) override;
 
private:
  const Target *target_;
 
  std::queue<Inst *> bottomList_;
  std::queue<Block *> blockList_;
  std::queue<Inst *> instList_;
 
  std::unordered_map<Ref<Inst>, Lattice> values_;
  std::set<std::pair<Block *, Block *>> edges_;
  std::set<const Block *> executable_;
  std::map<const Func *, std::map<unsigned, std::set<ArgInst *>>> args_;
  std::map<const Func *, std::set<std::pair<CallSite *, Block *>>> calls_;
  using ResultMap = std::map<unsigned, std::pair<Type, Lattice>>;
  std::map<const Func *, ResultMap> returns_;
};