#pragma once

#include "IR.h"

namespace sysy {

// 前向声明

class Loop;
// 基本块分析信息类
class BlockAnalysisInfo {

public:
  using block_list = std::vector<BasicBlock*>;
  using block_set = std::unordered_set<BasicBlock*>;

protected:
  // 支配树相关
  int domdepth = 0;          ///< 支配节点所在深度
  BasicBlock* idom = nullptr;    ///< 直接支配结点
  block_list sdoms;              ///< 支配树后继
  block_set dominants;           ///< 必经结点集合
  block_set dominant_frontiers;  ///< 支配边界
  
  // 后续添加循环分析相关
  // Loop* loopbelong = nullptr;    ///< 所属循环
  // int loopdepth = 0;             ///< 循环深度

public:
  // getterface
  const int getDomDepth() const { return domdepth; }
  const BasicBlock* getIdom() const { return idom; }
  const block_list& getSdoms() const { return sdoms; }
  const block_set& getDominants() const { return dominants; }
  const block_set& getDomFrontiers() const { return dominant_frontiers; }
  
  // 支配树操作
  void setDomDepth(int depth) { domdepth = depth; }
  void setIdom(BasicBlock* block) { idom = block; }
  void addSdoms(BasicBlock* block) { sdoms.push_back(block); }
  void clearSdoms() { sdoms.clear(); }
  void removeSdoms(BasicBlock* block) {
    sdoms.erase(std::remove(sdoms.begin(), sdoms.end(), block), sdoms.end());
  }
  void addDominants(BasicBlock* block) { dominants.emplace(block); }
  void addDominants(const block_set& blocks) { dominants.insert(blocks.begin(), blocks.end()); }
  void setDominants(BasicBlock* block) { 
    dominants.clear(); 
    addDominants(block); 
  }
  void setDominants(const block_set& doms) { 
    dominants = doms; 
  }
  void setDomFrontiers(const block_set& df) { 
    dominant_frontiers = df; 
  }
  
  // TODO：循环分析操作方法
  
  // 清空所有分析信息
  void clear() {
    domdepth =  -1;
    idom = nullptr;
    sdoms.clear();
    dominants.clear();
    dominant_frontiers.clear();
    // loopbelong = nullptr;
    // loopdepth = 0;
  }
};

// 函数分析信息类
class FunctionAnalysisInfo {


public:
  // 函数属性
  enum FunctionAttribute : uint64_t {
      PlaceHolder = 0x0UL,
      Pure = 0x1UL << 0,
      SelfRecursive = 0x1UL << 1,
      SideEffect = 0x1UL << 2,
      NoPureCauseMemRead = 0x1UL << 3
  };
  
  // 数据结构
  using Loop_list = std::list<std::unique_ptr<Loop>>;
  using block_loop_map = std::unordered_map<BasicBlock*, Loop*>;
  using value_block_map = std::unordered_map<Value*, BasicBlock*>;
  using value_block_count_map = std::unordered_map<Value*, std::unordered_map<BasicBlock*, int>>;
  
  // 分析数据
  FunctionAttribute attribute = PlaceHolder;  ///< 函数属性
  std::set<Function*> callees;               ///< 函数调用集合
  Loop_list loops;                           ///< 所有循环
  Loop_list topLoops;                        ///< 顶层循环
  // block_loop_map basicblock2Loop;            ///< 基本块到循环映射
  std::list<std::unique_ptr<AllocaInst>> indirectAllocas; ///< 间接分配内存
  
  // 值定义/使用信息
  value_block_map value2AllocBlocks;         ///< 值分配位置映射
  value_block_count_map value2DefBlocks;     ///< 值定义位置映射
  value_block_count_map value2UseBlocks;     ///< 值使用位置映射
  
  // 函数属性操作
  FunctionAttribute getAttribute() const { return attribute; }
  void setAttribute(FunctionAttribute attr) { attribute = static_cast<FunctionAttribute>(attribute | attr); }
  void clearAttribute() { attribute = PlaceHolder; }
  
  // 调用关系操作
  void addCallee(Function* callee) { callees.insert(callee); }
  void removeCallee(Function* callee) { callees.erase(callee); }
  void clearCallees() { callees.clear(); }
  
  
  // 值-块映射操作
  BasicBlock* getAllocBlockByValue(Value* value) { 
      auto it = value2AllocBlocks.find(value);
      return it != value2AllocBlocks.end() ? it->second : nullptr;
  }
  std::unordered_set<BasicBlock *> getDefBlocksByValue(Value *value) {
    std::unordered_set<BasicBlock *> blocks;
    if (value2DefBlocks.count(value) > 0) {
      for (const auto &pair : value2DefBlocks[value]) {
        blocks.insert(pair.first);
      }
    }
    return blocks;
  }
  std::unordered_set<BasicBlock *> getUseBlocksByValue(Value *value) {
    std::unordered_set<BasicBlock *> blocks;
    if (value2UseBlocks.count(value) > 0) {
      for (const auto &pair : value2UseBlocks[value]) {
        blocks.insert(pair.first);
      }
    }
    return blocks;
  }

  // 值定义/使用操作
  void addValue2AllocBlocks(Value* value, BasicBlock* block) { value2AllocBlocks[value] = block; }
  void addValue2DefBlocks(Value* value, BasicBlock* block) { ++value2DefBlocks[value][block]; }
  void addValue2UseBlocks(Value* value, BasicBlock* block) { ++value2UseBlocks[value][block]; }
  

  // 获取值定义/使用信息
  std::unordered_map<Value *, BasicBlock *>& getValue2AllocBlocks() {
    return value2AllocBlocks;
  }
  std::unordered_map<Value *, std::unordered_map<BasicBlock *, int>>& getValue2DefBlocks() {
    return value2DefBlocks;
  } 
  std::unordered_map<Value *, std::unordered_map<BasicBlock *, int>>& getValue2UseBlocks() {
    return value2UseBlocks;
  }
  std::unordered_set<Value *> getValuesOfDefBlock() {
    std::unordered_set<Value *> values;
    for (const auto &pair : value2DefBlocks) {
      values.insert(pair.first);
    }
    return values;
  }

  // 删除信息操作
  void removeValue2AllocBlock(Value *value) { value2AllocBlocks.erase(value); }
  bool removeValue2DefBlock(Value *value, BasicBlock *block) {
    bool changed = false;
    if (--value2DefBlocks[value][block] == 0) {
      value2DefBlocks[value].erase(block);
      if (value2DefBlocks[value].empty()) {
        value2DefBlocks.erase(value);
        changed = true;
      }
    }
    return changed;
  }
  bool removeValue2UseBlock(Value *value, BasicBlock *block) {
    bool changed = false;
    if (--value2UseBlocks[value][block] == 0) {
      value2UseBlocks[value].erase(block);
      if (value2UseBlocks[value].empty()) {
        value2UseBlocks.erase(value);
        changed = true;
      }
    }
    return changed;
  }

  // 间接分配操作
  void addIndirectAlloca(AllocaInst* alloca) { indirectAllocas.emplace_back(alloca); }
  std::list<std::unique_ptr<AllocaInst>>& getIndirectAllocas() { return indirectAllocas; }

  // TODO：循环分析操作

  // 清空所有分析信息
  void clear() {
    attribute = PlaceHolder;
    callees.clear();
    loops.clear();
    topLoops.clear();
    // basicblock2Loop.clear();
    indirectAllocas.clear();
    value2AllocBlocks.clear();
    value2DefBlocks.clear();
    value2UseBlocks.clear();
  }
};
// 循环类 - 未实现优化
class Loop {
public:
  using block_list = std::vector<BasicBlock *>;
  using block_set = std::unordered_set<BasicBlock *>;
  using Loop_list = std::vector<Loop *>;

protected:
  Function *parent;                      // 所属函数
  block_list blocksInLoop;               // 循环内的基本块
  BasicBlock *preheaderBlock = nullptr;  // 前驱块
  BasicBlock *headerBlock = nullptr;     // 循环头
  block_list latchBlock;                 // 回边块
  block_set exitingBlocks;               // 退出块
  block_set exitBlocks;                  // 退出目标块
  Loop *parentloop = nullptr;            // 父循环
  Loop_list subLoops;                    // 子循环
  size_t loopID;                         // 循环ID
  unsigned loopDepth;                    // 循环深度

  Instruction *indCondVar = nullptr;     // 循环条件变量
  Instruction::Kind IcmpKind;            // 比较类型
  Value *indEnd = nullptr;               // 循环结束值
  AllocaInst *IndPhi = nullptr;          // 循环变量

  ConstantValue *indBegin = nullptr;     // 循环起始值
  ConstantValue *indStep = nullptr;      // 循环步长
  
  std::set<GlobalValue *> GlobalValuechange;  // 循环内改变的全局变量
  
  int StepType = 0;                      // 循环步长类型
  bool parallelable = false;             // 是否可并行

public:
  explicit Loop(BasicBlock *header, const std::string &name = "") 
      : headerBlock(header) {
    blocksInLoop.push_back(header);
  }
  
  void setloopID() {
    static unsigned loopCount = 0;
    loopCount = loopCount + 1;
    loopID = loopCount;
  }
  ConstantValue* getindBegin() { return indBegin; }
  ConstantValue* getindStep() { return indStep; }
  void setindBegin(ConstantValue *indBegin2set) { indBegin = indBegin2set; }
  void setindStep(ConstantValue *indStep2set) { indStep = indStep2set; }
  void setStepType(int StepType2Set) { StepType = StepType2Set; }
  int getStepType() { return StepType; }
  size_t getLoopID() { return loopID; }

  BasicBlock* getHeader() const { return headerBlock; }
  BasicBlock* getPreheaderBlock() const { return preheaderBlock; }
  block_list& getLatchBlocks() { return latchBlock; }
  block_set& getExitingBlocks() { return exitingBlocks; }
  block_set& getExitBlocks() { return exitBlocks; }
  Loop* getParentLoop() const { return parentloop; }
  void setParentLoop(Loop *parent) { parentloop = parent; }
  void addBasicBlock(BasicBlock *bb) { blocksInLoop.push_back(bb); }
  void addSubLoop(Loop *loop) { subLoops.push_back(loop); }
  void setLoopDepth(unsigned depth) { loopDepth = depth; }
  block_list& getBasicBlocks() { return blocksInLoop; }
  Loop_list& getSubLoops() { return subLoops; }
  unsigned getLoopDepth() const { return loopDepth; }
  
  bool isLoopContainsBasicBlock(BasicBlock *bb) const {
    return std::find(blocksInLoop.begin(), blocksInLoop.end(), bb) != blocksInLoop.end();
  }
  
  void addExitingBlock(BasicBlock *bb) { exitingBlocks.insert(bb); }
  void addExitBlock(BasicBlock *bb) { exitBlocks.insert(bb); }
  void addLatchBlock(BasicBlock *bb) { latchBlock.push_back(bb); }
  void setPreheaderBlock(BasicBlock *bb) { preheaderBlock = bb; }
  
  void setIndexCondInstr(Instruction *instr) { indCondVar = instr; }
  void setIcmpKind(Instruction::Kind kind) { IcmpKind = kind; }
  Instruction::Kind getIcmpKind() const { return IcmpKind; }
  
  bool isSimpleLoopInvariant(Value *value) ; 
  
  void setIndEnd(Value *value) { indEnd = value; }
  void setIndPhi(AllocaInst *phi) { IndPhi = phi; }
  Value* getIndEnd() const { return indEnd; }
  AllocaInst* getIndPhi() const { return IndPhi; }
  Instruction* getIndCondVar() const { return indCondVar; }
  
  void addGlobalValuechange(GlobalValue *globalvaluechange2add) {
    GlobalValuechange.insert(globalvaluechange2add);
  }
  std::set<GlobalValue *>& getGlobalValuechange() {
    return GlobalValuechange;
  }

  void setParallelable(bool flag) { parallelable = flag; }
  bool isParallelable() const { return parallelable; }
};

// 控制流分析类
class ControlFlowAnalysis {
private:
  Module *pModule;  ///< 模块
  std::unordered_map<BasicBlock*, BlockAnalysisInfo*> blockAnalysisInfo;  // 基本块分析信息表
  std::unordered_map<Function*, FunctionAnalysisInfo*> functionAnalysisInfo;  // 函数分析信息

public:
  explicit ControlFlowAnalysis(Module *pMoudle) : pModule(pMoudle) {} 

  // 获取基本块分析信息
  BlockAnalysisInfo* getBlockAnalysisInfo(BasicBlock *block) {
    auto it = blockAnalysisInfo.find(block);
    if (it != blockAnalysisInfo.end()) {
      return it->second;
    }
    return nullptr;  // 如果未找到，返回nullptr
  }
  FunctionAnalysisInfo* getFunctionAnalysisInfo(Function *func) {
    auto it = functionAnalysisInfo.find(func);
    if (it != functionAnalysisInfo.end()) {
      return it->second;
    }
    return nullptr;  // 如果未找到，返回nullptr
  }

  void init();  // 初始化分析器
  void computeDomNode();  // 计算必经结点
  void computeDomTree();  // 构造支配树
  // std::unordered_set<BasicBlock *> computeDomFrontier(BasicBlock *block) ;  // 计算单个块的支配边界(弃用)
  void computeDomFrontierAllBlk();  // 计算所有块的支配边界
  void runControlFlowAnalysis();  // 运行控制流分析(主要是支配树和支配边界)
  void clear(){
    for (auto &pair : blockAnalysisInfo) {
      delete pair.second;  // 清理基本块分析信息
    }
    blockAnalysisInfo.clear();
    
    for (auto &pair : functionAnalysisInfo) {
      delete pair.second;  // 清理函数分析信息
    }
    functionAnalysisInfo.clear();
  } // 清空分析结果
  ~ControlFlowAnalysis() {
    clear();  // 析构时清理所有分析信息
  }

private:
  void intersectOP4Dom(std::unordered_set<BasicBlock *> &dom, const std::unordered_set<BasicBlock *> &other);  // 交集运算，
  BasicBlock* findCommonDominator(BasicBlock *a, BasicBlock *b);  // 查找两个基本块的共同支配结点
};

// 数据流分析类
// 该类为抽象类，具体的数据流分析器需要继承此类
// 因为每个数据流分析器的分析动作都不一样，所以需要继承并实现analyze方法
class DataFlowAnalysis {
 public:
  virtual ~DataFlowAnalysis() = default;

 public:
  virtual void init(Module *pModule) {}                                              ///< 分析器初始化
  virtual auto analyze(Module *pModule, BasicBlock *block) -> bool { return true; }  ///< 分析动作，若完成则返回true;
  virtual void clear() {}                                                            ///< 清空
};

// 数据流分析工具类
// 该类用于管理多个数据流分析器，提供统一的前向与后向分析接口
class DataFlowAnalysisUtils {
private:
  std::vector<DataFlowAnalysis *> forwardAnalysisList;   ///< 前向分析器列表
  std::vector<DataFlowAnalysis *> backwardAnalysisList;  ///< 后向分析器列表

public:
  DataFlowAnalysisUtils() = default;
  ~DataFlowAnalysisUtils() {
    clear();  // 析构时清理所有分析器
  }
  // 统一添加接口
  void addAnalyzers(
    std::vector<DataFlowAnalysis *> forwardList,
    std::vector<DataFlowAnalysis *> backwardList = {}) 
  {
    forwardAnalysisList.insert(
      forwardAnalysisList.end(), 
      forwardList.begin(), 
      forwardList.end());
    
    backwardAnalysisList.insert(
      backwardAnalysisList.end(),
      backwardList.begin(),
      backwardList.end());
  }
  
  // 单独添加接口
  void addForwardAnalyzer(DataFlowAnalysis *analyzer) {
    forwardAnalysisList.push_back(analyzer);
  }
  
  void addBackwardAnalyzer(DataFlowAnalysis *analyzer) {
    backwardAnalysisList.push_back(analyzer);
  }

  // 设置分析器列表
  void setAnalyzers(
    std::vector<DataFlowAnalysis *> forwardList,
    std::vector<DataFlowAnalysis *> backwardList)
  {
    forwardAnalysisList = std::move(forwardList);
    backwardAnalysisList = std::move(backwardList);
  }

  // 清空列表
  void clear() {
    forwardAnalysisList.clear();
    backwardAnalysisList.clear();
  }

  // 访问器
  const auto& getForwardAnalyzers() const { return forwardAnalysisList; }
  const auto& getBackwardAnalyzers() const { return backwardAnalysisList; }

public:
  void forwardAnalyze(Module *pModule);   ///< 执行前向分析
  void backwardAnalyze(Module *pModule);  ///< 执行后向分析
};

// 活跃变量分析类
// 提供def - use分析
// 未兼容数组变量但是考虑了维度的use信息
class ActiveVarAnalysis : public DataFlowAnalysis {
 private:
  std::map<BasicBlock *, std::vector<std::set<User *>>> activeTable;  ///< 活跃信息表，存储每个基本块内的的活跃变量信息

 public:
  ActiveVarAnalysis() = default;
  ~ActiveVarAnalysis() override = default;

 public:
  static std::set<User*> getUsedSet(Instruction *inst);
  static User* getDefine(Instruction *inst);

 public:
  void init(Module *pModule) override;
  bool analyze(Module *pModule, BasicBlock *block) override;
  // 外部活跃信息表访问器
  const std::map<BasicBlock *, std::vector<std::set<User *>>> &getActiveTable() const;
  void clear() override {
    activeTable.clear();  // 清空活跃信息表
  }
};

// 分析管理器 后续实现
// class AnalysisManager {

// };




}  // namespace sysy