#ifndef LLVM_GLOBAL_MOD_REF_H
#define LLVM_GLOBAL_MOD_REF_H
//===- GlobalModRefInfo.h - Identifies the MODs & REFs to a global   ---- -===//
//
//===----------------------------------------------------------------------===//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Copyright (c) 2015 Advanced Micro Devices, Inc.  All rights reserved.
// Developed by: Advanced Micro Devices, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// with the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimers.
// Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimers in the documentation
// and/or other materials provided with the distribution.
// Neither the names of Advanced Micro Devices, Inc., nor the names of its
// contributors may be used to endorse or promote products derived from this
// Software without specific prior written permission.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH
// THE SOFTWARE.
//
//===----------------------------------------------------------------------===//
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/RecursionDepthEstimation.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/TypeFinder.h"
#include "llvm/IR/ValueSymbolTable.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/IPO/FunctionSpecialize.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <cstdint>
#include <map>
#include <string>

using namespace llvm;

namespace llvm {

class GlobalModRefInfo {
public:
  GlobalVariable *GlobalVar;
  bool HasValidGlobalModRefInfo;
  MapVector<StoreInst *, bool> ModInfo;
  MapVector<LoadInst *, bool> RefInfo;
  MapVector<CallInst *, bool> CallInfo;

  void collectGlobalModRef();
  bool checkValidGlobalModRefInfo(Value *Val);
  bool isSafeFlangFunction(Function *);
  bool isSafeCallInstruction(CallInst *);
  bool isSameAddress(GEPOperator *, GEPOperator *);
  bool isCoveringAddress(GEPOperator *G1, GEPOperator *G2, FixedVectorType *ty);
  bool isCoveringAddress(GEPOperator *G1, GEPOperator *G2, CallInst *Call);
  bool isCoveringAddress(GEPOperator *G1, GEPOperator *G2,
                         unsigned elSize, unsigned elCount);

  GlobalModRefInfo(GlobalVariable *GlobalVar)
      : GlobalVar(GlobalVar), HasValidGlobalModRefInfo(false) {
    ModInfo.clear();
    RefInfo.clear();
    CallInfo.clear();
    collectGlobalModRef();
  }
  bool hasValidGlobalModRefInfo() { return HasValidGlobalModRefInfo; }
  bool getModsToGlobal(GEPOperator *GEP, SmallVector<StoreInst *, 4> &,
                       SmallVector<CallInst *, 4> &);
  void getRefsToGlobal(GEPOperator *GEP, SmallVector<LoadInst *, 4> &);  
  bool getModsToGlobal(GlobalVariable *GV, SmallVector<StoreInst *, 4> &,
                       SmallVector<CallInst *, 4> &);
  void getRefsToGlobal(GlobalVariable *GV, SmallVector<LoadInst *, 4> &);
  void dump();
};

class GlobalModRefInfoCollection {
private:
  MapVector<GlobalVariable *, GlobalModRefInfo*> ModRefInfoMap;
  FunctionAnalysisManager &FAM;
public:
  GlobalModRefInfoCollection(FunctionAnalysisManager& FAM) : FAM(FAM) {
    ModRefInfoMap.clear();
  }
  GlobalModRefInfo *getGlobalModRefInfo(GlobalVariable *GlobalVar) {
    auto Itr = ModRefInfoMap.find(GlobalVar); 
    if (Itr != ModRefInfoMap.end())
      return Itr->second;
    GlobalModRefInfo *GMRI = new GlobalModRefInfo(GlobalVar);
    ModRefInfoMap[GlobalVar] = GMRI;
    return GMRI;
  }
  Instruction *getPostDominantWrite(Value *GVorGEP);

  /// Computes possible static call stacks that can lead to the given instruction
  /// \p I.
  /// 
  /// @param I The instruction for which to find call stacks
  /// @param CallStacks Output parameter that will contain the discovered call stacks,
  ///                   where each call stack is represented as a vector of instructions
  /// @param MaxCallStacks Maximum number of call stacks to collect (default: 500)
  /// @param MaxStackDepth Maximum depth of each call stack to explore (default: 8)
  /// @return false if callstack information is incomplete, true otherwise
  bool getStaticCallStacks(Instruction *I, SmallVector<SmallVector<Instruction*>> &CallStacks, 
                           const unsigned &MaxCallStacks = 1000,  
                           const unsigned &MaxStackDepth = 100);
  void dump(){
    dbgs() << "GlobalModRefInfo::dump\n";
    for (auto Itr : ModRefInfoMap){
      Itr.second->dump();
    }
  }
  
  ~GlobalModRefInfoCollection() {
    for (auto Itr : ModRefInfoMap)
      delete Itr.second;
  }

  private:
    bool crossFunctionPostDominates( SmallVector<SmallVector<Instruction*>> S1,
                                     SmallVector<SmallVector<Instruction*>> S2);
    bool allPostDominateEntry( SmallVector<SmallVector<Instruction*>> IList);

    void removeUnreachableBlocks(Function *F,
      std::map<BasicBlock*,BasicBlock*> &Unreachables,
      std::map<Instruction*,BasicBlock*> &Branches);
    void replaceUnreachableBlocks(
      std::map<BasicBlock*,BasicBlock*> Unreachables,
      std::map<Instruction*,BasicBlock*> Branches);

};

class InterProceduralLoadBypass {

  public:
    InterProceduralLoadBypass(FunctionAnalysisManager &FAM) : FAM(FAM) {
      GMRC = new GlobalModRefInfoCollection(FAM);
    }
    ~InterProceduralLoadBypass() {}

    Value *getDominantWrite(Value *PTR, Instruction *Inst);

  private:
    void getModsToPtr(Value *Ptr,
                      SmallVector<StoreInst *, 4> &Mods,
                      SmallVector<CallInst *, 4> &Calls);
   void getModsToAlloca(Value *Ptr,
                                 SmallVector<StoreInst *, 4> &ModSet,
                                 SmallVector<CallInst *, 4> &CallSet);
    bool getStaticCallStacks(
    Instruction *I, SmallVector<SmallVector<Instruction *>> &CallStacks,
                           const unsigned &MaxCallStacks = 1000,  
                           const unsigned &MaxStackDepth = 100);
    bool allPostDominateEntry( SmallVector<SmallVector<Instruction*>> IList);
    bool crossFunctionPostDominates(
                             SmallVector<SmallVector<Instruction*>> S1,
                             SmallVector<SmallVector<Instruction*>> S2);
    void removeUnreachableBlocks(Function *F,
      std::map<BasicBlock*,BasicBlock*> &Unreachables,
      std::map<Instruction*,BasicBlock*> &Branches);
    void replaceUnreachableBlocks(
      std::map<BasicBlock*,BasicBlock*> Unreachables,
      std::map<Instruction*,BasicBlock*> Branches);
    Value *getPostDominantWrite(
      SmallVector<StoreInst *, 4> &ModSet,
      SmallVector<CallInst *, 4> &CallSet);
    bool interFunctionDominates( Value *PDI, Instruction *Inst);

    FunctionAnalysisManager &FAM;
    GlobalModRefInfoCollection *GMRC;
};
} // namespace llvm

#endif
