//===-- AnalyzeReachableMemoryAccesses.h
//                            - Analyze Memory accesses reachable from a
//                            starting pointer  --===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===- --------------------------------------------------------------===//
//
// Given a set of methods, this pass tries to analyze memory accesses of
// given type are reachable from a starting pointer. The pass statically checks
// if these memory accesses are intialized once and not modfied later.
// Also the pass checks if these memory accesses are captured only by the
// start pointer and does not escape out of any the methods.
//
//===----------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
//====  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.
#ifndef LLVM_TRANSFORMS_UTILS_ANALYZEREACHABLEMEMORYACCESSES_H
#define LLVM_TRANSFORMS_UTILS_ANALYZEREACHABLEMEMORYACCESSES_H

/* TO DO:
   If we have allocas interested memory types include class type
   we need to bail out.
*/

/*
Input: set of methods to do the analysis.
Input: set of types memory objects(struct/class types) of interest to analyze.
Input: field offset number (field of struct/class) from where to start the
analysis.

Output: For each method and a given start GEP, it tells whether memory objects
reacheable/accessable from the start GEP is modified more than once or
it could be modified due to escaping to unanalyzable regions/functions.

It does modified more than once and escape analysis together.

Assumption:
We assume that start GEP is a part of heap allocated struct/class object.
All the methods can access the start GEP as (base struct/class  + offset).

In the case where the start GEP is private field of class with special
properties:
they are not inherited (final)
they are not inheriting any members from its base class.
they dont have friend class/function.
We only look for the methods of the class.
*/
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/PointerCacheMissAnalysis.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TBAATypeReconstruction.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstIterator.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/Debug.h"
#include "llvm/Support/xxhash.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/Utils/MemoizationUtils.h"
#include <iostream>
#include <list>
#include <map>
#include <utility>
#include <vector>
#define DEBUG_TYPE "reacheable-memory-modref"
namespace llvm {

#define NOTPROCESSED 0
#define APPENDED 1
#define MODIFIED 2

class AnalyzeReachableMemoryAccesses {
  std::vector<Function *> Methods;
  std::vector<unsigned int> StartGepsoffset;
  std::set<Function *> NewOrMallocFunctionSet;
  std::set<Function *> DeleteOrFreeFunctionSet;

  Module *M;
  ModuleAnalysisManager *AM;
  TBAATypeReconstruction *TypeRecon;
  ClassHierarchyAnalysis *CHA;
  SmallVector<SmallVector<Instruction *>> Chains;
  

  /* Output: Map saying given a function and start GEP is memory objects of
     interest are intialized and not modified later */
  std::map<std::pair<Function *, Value *>, bool> MemoryAccessesModified;
  using InterestingStore =
      std::map<Function *,
               std::map<Value *, std::tuple<bool, std::set<Instruction *>>>>;
  std::map<unsigned int, InterestingStore> InterestingStoreList;
  unsigned int CurrentOffset;

  /* Mark all the stores for the types we are interested that tracked during
     escape analysis This includes memset/memcpy/destructor calls also. */
  std::set<Instruction *> StoreSet;

  /* Escape List is used to record the fact that memory is escaping via argument
     to a function call. We need to process the function and with the argument
     as start GEP.
  */
  std::set<std::tuple<CallBase *, int, bool>> EscapeList;
  std::map<Function *, std::set<BasicBlock *>> ExceptionMap;

  // Store Analysis we need a helper data structure that maps TBAA base type
  // (hash converted to int) to list of stores that has same TBAA base.
  std::map<StringRef, std::set<Instruction *>> TBAABaseTypeToStoreList;
  std::map<Instruction *, unsigned int> MemCallSet;
  std::set<Value *> FreshAllocList;
  std::set<Instruction *> ProcessedInsts;


  struct ClassInfo {
    unsigned long int TBAAClassTypeHash;
    StringRef BaseTypeName;
    std::map<unsigned int, unsigned long int> TBAATypeHashes;
    std::map<unsigned int, StringRef> TBAATypeNames;
  } cxxStartFieldInfo;

  void trackPvtPointerForEscapeAndMod();
  void markAnalysisFailure();
  bool gatherStartGeps(Function *Method, std::vector<Value *> &StartGeps,
                       unsigned int Offset);

  bool gatherStartGepsFromThisPointer(Function *Method, std::vector<Value *> &StartGeps,
                       unsigned int Offset, std::set<Instruction *> &Visited,
                       Instruction ** aliasCheckInst);

  bool gatherStartGepsFromOtherArgs( Function *Method, std::vector<Value *> &StartGeps,
                       unsigned int Offset, std::set<Instruction*>& Visited,
                       Instruction ** aliasCheckInst);

  bool doLegalityChecksForReachableMemoryAccess(Function * Func);
  bool checkRecursiveUses(Use &CurrentUse);
  bool isUsedInArithOrCmp(Instruction * Inst); 


  bool processWorkList(Function *Method, Value *StartGep, bool FreshAlloc);
  bool checkCandidateTypeForStoreWithValueOperandUse(StoreInst *ST);
  bool checkCandidateTypeForStoreWithPointerOperandUse(StoreInst *ST);
  bool checkCandidateTypeForLoad(Value *V);
  bool checkCandidateType(Value *V);
  bool saveStoreForClassification(User *U);
  bool processPhiNode(PHINode *Phi, Value *V);
  bool doesValueEscape(llvm::Value *V);
  void getExceptionBlocks(Function *F, std::set<BasicBlock *> &ExceptionBlocks);
  void performStoreClassification();
  bool classifyStores(
      std::map<uint64_t, std::tuple<unsigned int, std::set<Instruction *>>>
          &GlobalStoreStatus);
  Value * checkAliasingInstWritesorReadsFromFreshAlloc
       (Instruction * FirstI, Instruction *AliasI, Instruction * SecondI);
  Instruction *memoryIsNotModifiedBetween(
      Instruction *FirstI, Instruction *SecondI, AliasAnalysis *AA,
      const DominatorTree &DT,
      std::map<uint64_t, std::tuple<unsigned int, std::set<Instruction *>>>
          &GlobalStoreStatus,
      bool Checkbuckets);
  int checkPointerStoreHappensonNullPtrCondition(Instruction *I);
  int checkStoreHappenstoFreshAllocation(
      Instruction *I,
      std::map<uint64_t, std::tuple<unsigned int, std::set<Instruction *>>>
          &GlobalStoreStatus);
  bool checkDominatingConditionsForInstructions(Instruction *StoreInst,
                                                Instruction *BaseInst);
  bool checkForPostDominanceIgnoringInvokes(Instruction *StoreInst,
                                            Instruction *BaseInst,
                                            PostDominatorTree *PDT);
  int traversePredecessorsAndCheckPostDominance(
      BasicBlock *Block, Instruction *GivenInstruction, PostDominatorTree *PDT,
      std::set<BasicBlock *> &Visited);
  int analyzeSingleBucketAndNonDominatingStores(
      Instruction *I,
      std::map<uint64_t, std::tuple<unsigned int, std::set<Instruction *>>>
          &GlobalStoreStatus);

  int checkAlreadyClassifedStoresInBucket(std::set<Instruction *> &bucketEntries,
                                          Instruction * CurrentInst, unsigned int previousstatus,
                                          unsigned int currentstatus, std::set<Instruction *>& ProcessedInsts);

  void clearHelperDataStructures();
  bool classifyMemoryIntrincsFunctions(
      std::map<uint64_t, std::tuple<unsigned int, std::set<Instruction *>>>
          &GlobalStoreStatus);

  // Interested Types
  std::set<StringRef> InterestedTypes;
  void addInterestTypes() {
    bool start = true;
    for (int I = 0; I < Chains.size(); I++) {
      GetElementPtrInst * GEP = dyn_cast<GetElementPtrInst>(Chains[I][Chains[I].size()-1]);
      if(!GEP)
         LLVM_DEBUG(dbgs() <<"Root of chain is expected to be GEP\n");

      LLVM_DEBUG(dbgs() << "Root Instruction:" << *GEP <<"\n");
      LoadInst * LI = dyn_cast<LoadInst>(Chains[I][Chains[I].size()-2]);
      if(!LI)
          LLVM_DEBUG(dbgs() <<"Load expected next in the chain\n"); 
      LLVM_DEBUG(dbgs() << "Load for the root Instruction:" << *LI<<"\n");
      assert(LI->getPointerOperand() == GEP);

      unsigned int offset =  TypeRecon->getTypeInfoForInstr(LI)->getOffset();
      
      StringRef TypeName = TypeRecon->getTypeInfoForInstr(LI)->getTypeName();
      cxxStartFieldInfo.BaseTypeName = TypeRecon->getTypeInfoForInstr(LI)->getBaseStructLayout()->getTypeName();
      auto *TypeInfo = TypeRecon->getTypeInfoForInstr(LI);
      std::string HashName =
        (Twine(TypeName + cxxStartFieldInfo.BaseTypeName + std::to_string(TypeInfo->getOffset()) +
             std::to_string(TypeInfo->getSize())))
          .str();
       auto HashVal = llvm::xxHash64(HashName);
       if (!cxxStartFieldInfo.TBAATypeHashes.count(offset)) {
            cxxStartFieldInfo.TBAATypeHashes[offset] = HashVal;
          LLVM_DEBUG(dbgs() << "offset:" << offset <<"\n");
          LLVM_DEBUG(dbgs() << "Hash" <<  cxxStartFieldInfo.TBAATypeHashes[offset] <<"\n");
       }
       if (!cxxStartFieldInfo.TBAATypeNames.count(offset)) {
           cxxStartFieldInfo.TBAATypeNames[offset] = TypeName;
          LLVM_DEBUG(dbgs() << "offset:" << offset <<"\n");
          LLVM_DEBUG(dbgs() << "TypeName" <<  cxxStartFieldInfo.TBAATypeNames[offset] <<"\n");
       }

       if (start) {
         cxxStartFieldInfo.BaseTypeName = TypeRecon->getTypeInfoForInstr(LI)->getBaseStructLayout()->getTypeName(); 
         auto HashVal1 = llvm::xxHash64(cxxStartFieldInfo.BaseTypeName);
         cxxStartFieldInfo.TBAAClassTypeHash = HashVal1;
         LLVM_DEBUG(dbgs() << "cxxStartFieldInfo.BaseTypeName" << cxxStartFieldInfo.BaseTypeName <<"\n");
         LLVM_DEBUG(dbgs()<< "cxxStartFieldInfo.TBAAClassTypeHash" << cxxStartFieldInfo.TBAAClassTypeHash <<"\n");
         start = false;
       }
     }
     
     // TypeRecon.getTypeInfoForInstr(LI);
     InterestedTypes = llvm::getTypeInfoForChains(*M, *AM, Chains, TypeRecon);
  }

  void clearEntryInInterestingStoreList(unsigned int CurrentOffset) {
    for (auto Outermap : InterestingStoreList[CurrentOffset]) {
      for (auto Innermap : Outermap.second) {
        std::get<1>(Innermap.second).clear();
      }
      Outermap.second.clear();
    }
    InterestingStoreList[CurrentOffset].clear();
    InterestingStoreList.erase(CurrentOffset);
  }

  bool checkInterestedType(StringRef TypeName) {
    if (std::find(InterestedTypes.begin(), InterestedTypes.end(), TypeName) !=
        InterestedTypes.end()) {
      LLVM_DEBUG(dbgs() << TypeName << "is Interesting\n");
      return true;
    }
    return false;
  }

  bool isFreshAllocStore(Value *Ptr, Value *& AllocPtr);
  bool isIndirectFreshAlloc(Value *Ptr, Value *& AllocPtr);

  void getTBAAdetails(Instruction *I);

  Constant *getNullOperand() {
    if (!NullOp) 
      NullOp = ConstantPointerNull::get(
        Type::getInt32PtrTy(M->getContext()));
    return NullOp;
  }

  Constant * NullOp = nullptr;

public:
  AnalyzeReachableMemoryAccesses(std::vector<Function *> Methods,
                                 std::vector<unsigned int> StartGepsoffset,
                                 TBAATypeReconstruction *TypeRecon,
                                 ClassHierarchyAnalysis *CHA, Module *M,
                                 ModuleAnalysisManager *AM, 
                                 SmallVector<SmallVector<Instruction *>> Chains)
      : Methods(Methods), StartGepsoffset(StartGepsoffset),
        TypeRecon(TypeRecon), CHA(CHA), M(M), AM(AM), Chains(Chains) {}
  void run();

  /* Marks start offsets that fail memory escape analysis and append Anaysis */
  std::set<unsigned int> FailedOffset;

  /* Marks start offsets that fail memory escape analysis and append Anaysis */
  std::set<unsigned int> PassedOffset;
};

} // namespace llvm
#endif
