#ifndef LLVM_ANALYSIS_OPTIMIZE_ALIAS_CHECK_H
#define LLVM_ANALYSIS_OPTIMIZE_ALIAS_CHECK_H
//=========- OptimizingAliasCheck.h - Alias Check Extention to LAA -==========//
//
//===----------------------------------------------------------------------===//
//                     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/EquivalenceClasses.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/InterProceduralAliasAnalysis.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/InstructionCost.h"
#include "llvm/Analysis/TargetTransformInfo.h"

// Holds a base pointer and set of memory accesses related to it
class MemAccessSet {
public:
  // Base Pointer
  const SCEV *Base;
  // ScalarEvolution
  ScalarEvolution *SE;
  // The Loop
  Loop *L;
  // The minimum read address, from the group of memory accesses
  Value *ReadMin;
  // The maximum read address, from the group of memory accesses
  Value *ReadMax;
  // The minimum write address, from the group of memory accesses
  Value *WriteMin;
  // The maximum write address, from the group of memory accesses
  Value *WriteMax;
  // AccessType
  Type *AccessType;
  // Group identity
  int GroupId;
  // Set of read memory access in the loop
  MapVector<const SCEV *, bool> Read;
  // Set of write memory access in the loop
  MapVector<const SCEV *, bool> Write;
  // Set of read memory access in the loop
  MapVector<const SCEV *, bool> ReadOutside;
  // Set of write memory access in the loop
  MapVector<const SCEV *, bool> WriteOutside;
  // Collection of PointerInfo for memory access in the loop
  SmallVector<const RuntimePointerChecking::PointerInfo *, 2> PointerInfo;

  MemAccessSet(const SCEV *Base, ScalarEvolution *SE, Loop *L, Type *AccessType)
      : Base(Base), SE(SE), L(L), ReadMin(nullptr), ReadMax(nullptr),
        WriteMin(nullptr), WriteMax(nullptr), AccessType(AccessType),
	GroupId(-1) {
    Read.clear();
    Write.clear();
    ReadOutside.clear();
    WriteOutside.clear();
    PointerInfo.clear();
  }
  // Check if memory access in MemAccessSet are Legal to
  // qualify for the alias check.
  bool isLegalGroup();
  // Add the pointer info to respective read/write map
  void addPointerInfo(const RuntimePointerChecking::PointerInfo *);
  // Return true if input SCEV is an invariant SCEV, else return false
  bool scevWithInvariantCompute(const SCEV *S);
  // Compile time reduce the input memory access set.
  // It tries to reduce the memory accesses targetted to find the
  // representative memory access set for the possible
  // range of memory accesses in the input group.
  void reduceMemAccessSet(MapVector<const SCEV *, bool> &Grp);
  // Compile time reduce the memory access set both read & write.
  // It tries to reduce the memory accesses in each MemAccessSet
  // to find the representative memory access set for the possible
  // range of accesses.
  void createReducedMemAccessSet();
  // Remove read write dependency.
  // Its a typical case where read and write to same memory
  // exists in the loop body, in such cases only consider the
  // write access and eliminate the read access from MemAccessSet
  void removeReadWriteDependency();
  // Is possible to represent access outside the outer loop
  // Evaluate all the SCEV exprs for each outer loop and check
  // the computable SCEVs(affinity)
  // Create the Outside access set.
  bool canRepresetAccessOutsideLoop(Loop *OuterLoop,LoopInfo *LI,
                                    bool WholeLoopNestCheck);

  const SCEV * ProcessSCEVAtScope(const SCEV *S, Loop *ParentLoop, LoopInfo *LI, const SCEV *&Base);
  // Returns true if any unsafe/non-computable SCEV
  bool representAccessSetOutsideParentLoop(Loop *ParentLoop, LoopInfo *LI,
                                           bool WholeLoopNestCheck);
};

// Collection of memory access are its properties
class MemAccessDescription {
public:
  // ScalarEvolution
  ScalarEvolution *SE;
  // The Loop
  Loop *L;
  // Struct type represent entries in the sort based array.
  StructType *PointerHolderType;

  LoopInfo *LI = nullptr;
  // Number of MemAccessSet Groups
  int TotalGroups;
  // Collection of MemAccessSet
  SmallVector<MemAccessSet *, 2> AccessGrp;
  // Collection of SCEV/Variables which are assumed to be
  // positive, for these SCEVs a runtime check will be generated
  MapVector<const SCEV *, bool> AssumedPositiveVars;

  MemAccessDescription(ScalarEvolution *SE, Loop *L,
                       StructType *PointerHolderType, LoopInfo *LI)
      : SE(SE), L(L), PointerHolderType(PointerHolderType), LI(LI),
        TotalGroups(0) {
    AccessGrp.clear();
    AssumedPositiveVars.clear();
  }

  // Return the MemAccessSet for the input SCEV
  // If there is already a MemAccessSet it will return same
  // else it will create a new MemAccessSet and return. 
  MemAccessSet *getMemAccessSet(const SCEV *Base, Type *AccessType);
  // Add the PointerInfo to the respective group
  bool addPointerInfoToGroup(const RuntimePointerChecking::PointerInfo *PI);
  // Return true if memory access are legal to qualify for alias check.
  bool hasLegalGroups();
  // Check the possiblity to move the runtime alias check outside outer loop
  bool canMoveChecksOutsideLoop(Loop *OuterLoop,bool WholeLoopNestCheck);
  // Compute & return the cost of runtime alias check
  unsigned getCostRTAliasCheck(const TargetTransformInfo *TTI) const;
  // Reduce the collected memory access from each MemAccessSet
  // This reduction is targetted to reduce the mem access based on
  // the range such that the reduced mem access represent the full group
  void createReducedMemAccessSet();
  // Return true if input MemAccessSet share a common memory access
  // pattern, else return false
  bool matchMemAccessSet(MemAccessSet *PG1, MemAccessSet *PG2);
  // For the ref mapvector SCEV, it finds the SCEV without
  // the base pointer add it to Op mapvetor 
  void getEffectiveSCEV(const SCEV *Base, MapVector<const SCEV *, bool> &Ref,
                        MapVector<const SCEV *, bool> &Op);
  // Create runtime check for min/max for each MemAccessSet
  // Intent to find the min & max address range for the each MemAccessSet
  // This is required for the cases where min max cant be deduced at compile-time
  void createRTMinMaxCheckForGroups(Instruction *InsertionPoint);
  // As we are moving the checks from inside to outside loop, at this point
  // we have computed all the memory access SCEVs to the outermost loop, now
  // its the time to expose outermost loop iteration space on the computed
  // memory accesses and get the final min & max for each access in terms of
  // outer loop.
  void expandMemAccessReadWriteSets(Loop *OuterLoop);
  // Categorize the MemAccessSet[s] based on the same memory access patern
  // Two MemAccessSet share the same memory access pattern if they share
  // a common GroupID.
  void categorizeGroups();
  // Identify variables which need positive value assumption check.
  void identifyVarsForPositiveCheck();
  // Return the number of pointers qualify for the sort based check
  unsigned estimateNumOfRecords();
  // Return true if InnerLoop is part of OuterLoop
  bool loopContainedInLoop(Loop *InnerLoop, Loop *OuterLoop);
  // This create an entry to the allocated array
  void createHolderStructEntry(Function *F, Value *AllocatedNode,
                               unsigned Index, Value *Val,
                               Instruction *InsertionPoint, int RWVal);
  // Find the man max range for the memory accesses in a group by generating
  // runtime checks, if two groups share a common memory access pattern then
  // reuse first min max information for the second group.
  void createRTMinMaxCheckForOneGroup(MemAccessSet *PG, Instruction *);
  // Create the runtime alias check and return it.
  Value *createRTAliasCheck(Function *F, Instruction *InsertionPoint,
                            unsigned VF);
  // Create the runtime alias check for tiling checking for the iteration
  // space and return it.
  Value *createRTAliasCheckForBlocking(Function *F,
                                       Loop *InnermostLoop,
                                       Loop *OutermostLoop);
  // Create Runtime Alias Check Outside Outer Loop
  Value *createRTAliasCheckOutsideOuterLoop(Function *F,
                         Instruction *InsertionPoint, Loop *OuterLoop);
  // Check the iteration space of the given pointer for loop blocking
  const SCEV *IterationSpaceOfPtr (Value *V, Loop *InnerMostLoop,
                              Loop *OuterMostLoop);
  ~MemAccessDescription();
};
/* Collect SCEV Unknowns local to the loop from a SCEV */
struct SCEVCollectLoopTerms {
  SmallVectorImpl<const SCEV *> &Terms;
  Loop * L;

  SCEVCollectLoopTerms(SmallVectorImpl<const SCEV *> &T, Loop *L) : Terms(T),L(L) {}

  bool follow(const SCEV *S) {
    if (isa<SCEVUnknown>(S) ) {
      Value * V = cast<SCEVUnknown>(S)->getValue();
      if (V && !L->isLoopInvariant(V)) {
        Terms.push_back(S);
        return false;
      }
    }
    // Keep looking.
    return true;
  }
  bool isDone() const { return false; }
};

// This function returns the min SCEV by comparing input I & J
// It assumes the non pointer variable involved in the SCEV are all positive.
const SCEV *getMinSCEVWithAssumption(const SCEV *Diff, const SCEV *I,
                                     const SCEV *J, ScalarEvolution *SE);
#endif
