#ifndef LLVM_IPAA_H
#define LLVM_IPAA_H
//===- InterProceduralAliasAnalysis.h - Inter Procedural Alais Analysis -===//
//
//===----------------------------------------------------------------------===//
//                     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/DenseMap.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/BasicAliasAnalysis.h"
#include "llvm/Analysis/FuncPtrAndStrcutSafetyAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/TypeReconstruction.h"
#include "llvm/Analysis/ValueTracking.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/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/TypeFinder.h"
#include "llvm/IR/ValueSymbolTable.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/IPO.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"

using namespace llvm;

namespace llvm {

// Seed categories:
enum class SeedCategory { Param, Alloc, Call, Unknown };

// Print strings for SeedCategory
static const char *SeedCategoryName[4] = {"Param", "Alloc", "Call", "Unknown"};

// Argument Categories:
enum class ArgumentCategory {
  Pointer,
  ScalarConst,
  KnownFunction,
  NullPtr,
  Unknown
};

// Print strings for ArgumentCategory
static const char *ArgumentCategoryName[5] = {
    "Pointer", "ScalarConst", "KnownFunction", "Pointer", "Unknown"};

// Seed information
class SeedInformation {
public:
  // Seed instruction.
  Value *Seed;

  // Category of the Seed.
  SeedCategory SeedType;

  // If Seed category is Param then the param position, else -1.
  int FormalArgNum;

  // If Seed is a write to memory.
  bool IsWritePtr;

  // Constructor
  SeedInformation()
      : Seed(nullptr), SeedType(SeedCategory::Unknown), FormalArgNum(-1),
        IsWritePtr(false) {}
};

// Passed Argument to a call-site information.
class ActualArgInfo {
public:
  // Arg position number in the call site
  unsigned ArgNum;

  // Passed arg aliasing in the function, 1 if no-alias else 0.
  bool ActualArgNoAlias;

  // Category of argument.
  ArgumentCategory ArgCategory;

  // Seed category of the argument
  SeedCategory SeedType;

  // Seed instruction for the argument.
  Value *Seed;

  // Constructor
  ActualArgInfo(unsigned ArgNum)
      : ArgNum(ArgNum), ActualArgNoAlias(false),
        ArgCategory(ArgumentCategory::Unknown), SeedType(SeedCategory::Unknown),
        Seed(nullptr) {}

  // Set the Seed Details
  void setSeedDetails(Value *S, SeedCategory ST) {
    Seed = S;
    SeedType = ST;
  }

  // Set the aliasing of passed argument.
  void setArgAliasing(bool AliasRes) { ActualArgNoAlias = AliasRes; }

  // Set the argument category
  void setArgCategory(ArgumentCategory AC) { ArgCategory = AC; }

  // Return true if its memory arg with seed as param or mem-alloc.
  bool isMemArgWithParamOrAllocSeed() {
    // Seed should be there.
    if (!Seed)
      return false;
    // Arg category should be of pointer type
    if (ArgCategory != ArgumentCategory::Pointer)
      return false;
    // Look for Param or alloc
    if ((SeedType != SeedCategory::Param) && (SeedType != SeedCategory::Alloc))
      return false;
    return true;
  }

  // Print summary.
  void dump() {
    if (ArgCategory != ArgumentCategory::Pointer &&
        ArgCategory != ArgumentCategory::NullPtr)
      return;
    dbgs() << "                   # Argument-Number   : " << ArgNum << "\n";
    dbgs() << "                        # Argument-NoAlias  : "
           << ActualArgNoAlias << "\n";
    dbgs() << "                             # Seed-Category   : "
           << SeedCategoryName[(int)SeedType] << "\n";
    dbgs() << "                        # Argument-Category   : "
           << ArgumentCategoryName[(int)ArgCategory] << "\n";
  }
};

// Function Call Information
class FunctionCallInfo {
public:
  // The Call Instruction
  CallInst *CI;

  // Is Indirect Call.
  bool IsIndirectCall;

  // Vector to hold passed argument information.
  SmallVector<ActualArgInfo *, 4> ArgInfo;

  // Constructor
  FunctionCallInfo(CallInst *CI) : CI(CI) {
    IsIndirectCall = !CI->getCalledFunction();
    ArgInfo.clear();
  }

  // Return the already computed arg information at input position
  ActualArgInfo *getArgInfoAtPosition(unsigned ArgNum) {
    for (ActualArgInfo *AAI : ArgInfo)
      if (AAI->ArgNum == ArgNum)
        return AAI;
    return nullptr;
  }

  // Set all args with unsafe(not-no-alias) memory access.
  void setAllArgsWithUnSafeMemoryAccess() {
    for (ActualArgInfo *AAI : ArgInfo)
      AAI->setArgAliasing(false);
  }

  // Add the input argument information to the ArgInfo vector.
  void addActualArgInfo(ActualArgInfo *AI) { ArgInfo.push_back(AI); }

  // Print summary information
  void dump() {
    dbgs() << "     # " << *CI << "\n";
    dbgs() << "            # IsIndirectCall           : " << IsIndirectCall
           << "\n";
    dbgs() << "            # Argument Analysis Info :\n";
    for (auto *AI : ArgInfo)
      AI->dump();
  }
};

// Return instruction information.
class ReturnInfo {
public:
  // Return instruction
  ReturnInst *RI;

  // Is no-alias return value
  bool isNoAlias;

  // If return originates from a parameter, then the parameter location else -1
  int ParamPosition;

  // Constructor
  ReturnInfo(ReturnInst *RI) : RI(RI), isNoAlias(false), ParamPosition(-1) {}

  // Set the aliasing for the returnd value.
  void setAliasingForReturnValue(bool AliasRes) { isNoAlias = AliasRes; }

  // When return valye originates from param, set its param position.
  void setParamPosition(int ParamPos) { ParamPosition = ParamPos; }

  // Return true if the return-statement returns no-alias memory
  bool hasNoAliasReturnValue() { return isNoAlias; }

  // Print Summary
  void dump() {
    dbgs() << "            # Return Information :\n";
    dbgs() << "                    # isNoAlias     : " << isNoAlias << "\n";
    dbgs() << "                    # ParamPosition : " << ParamPosition << "\n";
  }
};

// Function Information
class FunctionInfo {
public:
  // The Function
  Function *CurFunc;

  // True if function has any unsafe write to memory
  bool HasUnSafeStores;

  // Information of all the function call[s] within the given function.
  SmallVector<FunctionCallInfo *, 4> FunctionCall;

  // Information of all the return instruction[s] within the given function.
  SmallVector<ReturnInfo *, 4> ReturnInstInfo;

  // Aliasing of input parameters at a given position.
  MapVector<unsigned, bool> InputParameterAliasing;

  // Constructor
  FunctionInfo(Function *F) {
    CurFunc = F;
    HasUnSafeStores = false;
    FunctionCall.clear();
    ReturnInstInfo.clear();
    InputParameterAliasing.clear();
  }

  // Return the existing FunctionCallInfo for the input CallInst.
  FunctionCallInfo *getFunctionCallInfo(CallInst *CI) {
    // Return the existing function call information
    // Return nullptr if it does not exist or not computed yet.
    for (FunctionCallInfo *FCI : FunctionCall)
      if (FCI->CI == CI)
        return FCI;
    return nullptr;
  }

  // Add the input parameter aliasing information
  void addInputParameterAliasingInfo(unsigned Loc, bool AliasRes) {
    if (InputParameterAliasing.find(Loc) != InputParameterAliasing.end())
      InputParameterAliasing[Loc] &= AliasRes;
    else
      InputParameterAliasing[Loc] = AliasRes;
  }

  // Add the input function call infor to the FunctionCall vector
  void addFunctionCallInfo(FunctionCallInfo *FCI) {
    FunctionCall.push_back(FCI);
  }

  // Add Return instruction information to ReturnInstInfo vector
  void addReturnInfo(ReturnInfo *RI) { ReturnInstInfo.push_back(RI); }

  // Returns true if *all* the return statements in the function returns
  // no-alias memory, else returns false.
  bool hasNoAliasReturnValue() {
    bool AlwaysReturnsNoAliasMemory = true;
    for (auto *RI : ReturnInstInfo)
      AlwaysReturnsNoAliasMemory &= RI->hasNoAliasReturnValue();
    return AlwaysReturnsNoAliasMemory;
  }

  // Return true if input parameter at input location does not alias with
  // other memory within the function, else return false.
  bool isNoAliasInputParameter(unsigned ParamPos) {
    if (InputParameterAliasing.find(ParamPos) != InputParameterAliasing.end())
      return InputParameterAliasing[ParamPos];
    return false;
  }

  // Return true if function has any unsafe write to memory.
  bool hasUnSafeStores() { return HasUnSafeStores; }

  // Print summary.
  void dump() {
    dbgs() << "\n*******************************************************\n";
    dbgs() << "Function                 : " << CurFunc->getName() << "\n";
    dbgs() << "HasUnSafeStores          : " << HasUnSafeStores << "\n";

    dbgs() << "Param Alias Information  :\n";
    for (auto &PAI : InputParameterAliasing)
      dbgs() << "     Param Num: (" << PAI.first
             << ") No-Alias(Within-function): " << PAI.second << "\n";

    dbgs() << "List of FunctionCall[s]  :\n";
    for (auto *CI : FunctionCall)
      CI->dump();

    dbgs() << "List of ReturnInst[s]    :\n";
    for (auto *RI : ReturnInstInfo)
      RI->dump();
    dbgs() << "\n*******************************************************\n";
  }
};

// Wrapper to function information, it cache the information about
// all the processed function info.
class FunctionInfoWrapper {
public:
  // Vector of function info.
  SmallVector<FunctionInfo *, 4> FIV;

  // Constructor
  FunctionInfoWrapper() { FIV.clear(); }

  // Destructor
  ~FunctionInfoWrapper() {
    for (auto *FI : FIV)
      delete FI;
  }

  // Add the function info
  void addFI(FunctionInfo *FI) { FIV.push_back(FI); }

  // Find the function information.
  FunctionInfo *findFunctionInfo(Function *F) {
    for (auto *FI : FIV)
      if (FI->CurFunc == F)
        return FI;
    return nullptr;
  }

  // Print Summary
  void dump() {
    for (auto *FI : FIV)
      FI->dump();
  }
};

class IPAAImpl {
public:
  static char ID;

  // Constructor
  IPAAImpl(Module *CurModule, ModulePass *CurPass,
           llvm::AnalysisManager<llvm::Function> *FAM,
           TargetLibraryInfo *TLI, TRF TR)
    : CurModule(CurModule), CurPass(CurPass), FAM(FAM), TLI(TLI) {
    LoopInformation.clear();
    DL = &CurModule->getDataLayout();
    FPA = new FunctionPointerAnalysis;
    FPA->analyzeModule(CurModule, TR);

    for (Module::iterator I = CurModule->begin(), E = CurModule->end(); I != E; I++) {
      Function *F = &*I;
      // Do not consider non-address taken function.
      if (!F->hasAddressTaken())
        continue;
      AddrTakenFuncs.insert(F);
    }
  }

  // Destructor
  ~IPAAImpl() { delete FPA; }

  // The current module
  Module *CurModule;

  // Analysis Manager
  llvm::AnalysisManager<llvm::Function> *FAM;

  // The current pass.
  ModulePass *CurPass;

  // The TargetLibraryInfo
  TargetLibraryInfo *TLI;

  const DataLayout *DL;

  // The FunctionPointerAnalysis
  FunctionPointerAnalysis *FPA;

  // Function information container.
  FunctionInfoWrapper FIW;

  // Map holding LoopInfo
  MapVector<Function *, LoopInfo *> LoopInformation;

  // Set holding the Address taken functions in the module.
  SmallPtrSet<Function *, 16> AddrTakenFuncs;

  // Analyze aliasing of memory within the function and return
  // the generated summary
  FunctionInfo *analyzeFunction(Function *F, unsigned CurDepth = 1);

  // Analyze aliasing of function incoming arguments
  void analyzeFunctionArgs(Function *F, FunctionInfo *FI, unsigned CurDepth);

  // Analyze memory aliasing in the function body.
  void analyzeFunctionBody(Function *F, FunctionInfo *FI, unsigned CurDepth);

  // Analyze return instructions and check the aliasing if return value.
  void analyzeReturnInst(ReturnInst *RI, FunctionInfo *FI, Function *F,
                         unsigned CurDepth);

  // Analyze call instruction and check the memory aliasing of passed params.
  void analyzeCallInst(CallInst *CI, FunctionInfo *FI, Function *F,
                       unsigned CurDepth);

  // Analyze passed args to a function call.
  void analyzePassedArgsToCall(CallInst *CI, FunctionCallInfo *FCI,
                               FunctionInfo *FI, Function *F,
                               unsigned CurDepth);

  // Analyze function calling input function 'F'.
  void analyzeCallingFunctions(Function *F, unsigned CurDepth);

  LoopInfo *getLoopInfoForFunction(Function *F);

  // Find the list of function which can be called by given indirect call.
  // It uses the indirect call possiblity analysis.
  void findFunctionsForIndirectCall(Module *M, CallInst *CI,
                                    SmallVector<Function *, 4> &Functions,
                                    bool &HasExternMatch);

  // Resolve memcpy and check for indirect call possiblities.
  bool findPossiblitiesFromMemCpy(CallInst *CI,
                                  SmallVector<Function *, 4> &Functions,
                                  bool &);

  // Find the list of call-sites which calling the given function
  // It collect indirect call sites as well using indirect call possiblity
  // analysis.
  void findCallsToFunction(Function *F, SmallVector<CallInst *, 4> &Calls);

  // Update the alias information for a call site from the called function
  void syncFunctionCallInfoWithFunctionInfo(FunctionCallInfo *FCI,
                                            FunctionInfo *FI);

  // For a function call, if passed arguments having common origin then mark
  // them as not-no-alias.
  void recheckSameOrigin(FunctionCallInfo *FCI);

  // Check the memory aliasing for the collected memory instruction
  // If any one alias with other memory return false, else return true.
  bool checkAliasInMemDepGraph(Function *F, FunctionInfo *FI,
                               SmallVector<Value *, 4> &SubGraph,
                               unsigned CurDepth);

  // Return true if the return value of the call is always no-alias
  bool checkMemReturnedFromCallDoesNotAlias(CallInst *CI, unsigned CurDepth);

  // Dump the collected summary.
  void dump() { FIW.dump(); }
};

// Find seed instructions and ensure seeds should have unique origin.
// If unique origin return true, else return false.
// Return false when no seed found.
bool FindSeedsAndCheckUnicity(Value *V, Function *F,
                              SmallVector<SeedInformation, 4> &Seeds,
                              const TargetLibraryInfo *TLI, bool IsWritePtr);

} // namespace llvm

#endif
