
#ifndef LLVM_ANALYSIS_HIERARCHICALTYPE_H
#define LLVM_ANALYSIS_HIERARCHICALTYPE_H

#include "llvm/Analysis/CallSiteAnalysis.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TBAATypeReconstruction.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Transforms/Utils/CodeMoverUtils.h"
#include "llvm/Analysis/FunctionCallsInfoAnalysis.h"
#include <stack>

namespace llvm {
typedef std::shared_ptr<TBAATypeReconstruction::TypeInfo> TBAATypeInfoTy;
typedef std::vector<std::vector<Value*>> MemAffecPathsTy;

Value *getUniqueSymbolicVal(PHINode *PhiNode);
std::optional<Value*> getValueFromSCEV(const SCEV* S);
std::optional<Value*> getValueFromCast(const SCEV* S);

struct HierarchicalType {
  static std::optional<std::shared_ptr<HierarchicalType>> get(Value* V, TBAATypeReconstruction &TypeRecon, std::optional<std::vector<Value*>> Path);
  TBAATypeReconstruction::TypeInfo *get(int index);
  bool isSameAs(std::shared_ptr<HierarchicalType> &Other);
  int size();
  void dump();
  Value *getSource();
  std::shared_ptr<TBAATypeReconstruction::TypeInfo> getRootType();

private:
  static std::optional<std::stack<Value *>> getLoadChain(Value *V, int MaxDepth, std::optional<std::vector<Value*>> Path);
  std::vector<TBAATypeReconstruction::TypeInfo *> Types;
  Value* Source;
};

struct HierTypeTreeNode {

  HierTypeTreeNode(std::shared_ptr<HierTypeTreeNode>, TBAATypeInfoTy);
  ~HierTypeTreeNode(){}
  std::shared_ptr<HierTypeTreeNode> getParent();
  std::shared_ptr<HierTypeTreeNode> getRoot();
  std::shared_ptr<HierTypeTreeNode> getNodeOfType(std::shared_ptr<HierarchicalType> H);
  std::optional<std::vector<std::shared_ptr<HierTypeTreeNode>>> getSiblings();
  std::vector<std::shared_ptr<HierTypeTreeNode>> getChildren();
  void addChild(std::shared_ptr<HierTypeTreeNode>, unsigned int);
  bool addMemAffInst(Instruction*, std::vector<Value*>&);
  bool isRoot();
  bool isLeaf();
  void setLeaf(bool);
  int getIndex();
  void setIndex(int);
  std::shared_ptr<HierTypeTreeNode> getField(int index);
  int getOffset();
  int getDepth();
  void setInterested(bool interested);
  bool getInterested();
  StringRef getTypeName();
  TBAATypeInfoTy getTypeInfo();
  MemAffecPathsTy getMemAffecPaths();
  std::shared_ptr<HierTypeTreeNode> matchNextType(TBAATypeReconstruction::TypeInfo *NextField, bool MatchOffset=false);
  std::shared_ptr<HierTypeTreeNode> markInterested(std::shared_ptr<HierarchicalType> H);
  void dump();

private:
  int index;
  std::shared_ptr<HierTypeTreeNode> Parent;
  TBAATypeInfoTy TypeInfo;
  std::vector<std::shared_ptr<HierTypeTreeNode>> Fields;
  std::vector<unsigned int> FieldOffsets;
  std::vector<std::vector<Value*>> MemAffecPaths;
  bool interested;
  bool leaf;
};
struct HierarchicalTypeBasedAnalysis {
  typedef std::tuple<Value*, std::vector<Value*>, std::shared_ptr<HierTypeTreeNode>> WorklistItem;
  HierarchicalTypeBasedAnalysis(Module &M, TBAATypeReconstruction &TypeRecon, aocc::CSFunctionProperty &CS, FunctionAnalysisManager &FAM, FunctionCallsInfo &FC);
  std::set<Value*> getInstructionsOfTypeExtended(TBAATypeReconstruction::TypeInfo* TBAAType);
  bool areLockstepEquivalent(Value* V1, Value *V2, std::optional<ControlConditionVector> Predicates);
  bool areSameHierType(Value* V1, Value* V2);
  std::optional<std::set<Function*>> getMemoryAffecFuncs(Value* V);
  
private:
  bool addUsersToWorkList(Value *ValueInst, std::stack<WorklistItem> &Worklist, std::shared_ptr<HierTypeTreeNode> CurrType, std::vector<Value*> &Path);
  bool areSemanticallyEquivalent(StoreInst* V1, StoreInst* V2);
  bool areSimilarOperations(StoreInst* V1, StoreInst* V2);
  bool copiesValueToNewlyCreatedMemory(StoreInst *S);
  bool copiesNewlyCreatedMemoryToFuncArg(StoreInst *S);
  bool isDerivedFromFuncArg(Value *V);
  bool isMemWriteIntrinsic(Value *V);
  bool isaLocationInNewMemory(Value *V);
  bool mayWriteToMemory(Value *V);
  int increments(StoreInst *S);
  int increments(Value *S, Value *T);
  bool areCallEquivalent(Instruction *Inst1, Instruction *Inst2);
  std::optional<std::set<Instruction*>> getMemAffInsts(HierarchicalType HierType);
  std::set<std::pair<int, int>> pairPossibleEquiInst(MemAffecPathsTy &A, MemAffecPathsTy &B);
  std::shared_ptr<HierTypeTreeNode> getTypeTree(std::vector<std::shared_ptr<HierarchicalType>>);
  std::shared_ptr<HierTypeTreeNode> formTypeTree(TBAATypeInfoTy RootType, int depth, std::shared_ptr<HierTypeTreeNode>);
  bool populateMemAffecInst(std::shared_ptr<HierTypeTreeNode> TypeTreeRootNode);
  bool filteroutOverriddenInits(BitVector &AccountedInsts, MemAffecPathsTy &Paths);
  bool areLockstepEquivalent(MemAffecPathsTy A, MemAffecPathsTy B);
  std::optional<std::pair<int,int>> getPairInSameFunction(std::vector<Value*> MemAffPathsA, std::vector<Value*> MemAffPathsB);
  int getPriorCallInPath(std::vector<Value*> MemAffPaths, int lastIndex);
  bool escapes(Value* Inst, Value *LastInst);
  std::optional<bool> isDeleteCall(Value *V);
  std::optional<bool> isNewCall(Value *V);

  Module &M;
  TBAATypeReconstruction &TypeRecon;
  FunctionCallsInfo &FuncCallsInfo;
  aocc::CSFunctionProperty &CS;
  FunctionAnalysisManager &FAM;
};

} // namespace llvm

#endif // LLVM_ANALYSIS_HIERARCHICALTYPE_H
