//========- MemSafetyAnalysis.h - Analyze the memory aceesses safety -======//
//
//===----------------------------------------------------------------------===//
//                     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.
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_MEMSAFETYANALYSIS_H
#define LLVM_ANALYSIS_MEMSAFETYANALYSIS_H

#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/TypeFinder.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <iterator>
#include <map>
#include <stack>
#include <utility>
using namespace llvm;


// Describes the memory property
// Unsafe: Unsafe
// Safe: Proven Safe
// LocalSafe: Analyzed but not yet proven to be safe
enum class MemProperty { Unsafe, Safe, LocalSafe };

// Captures the memory details for the current block
class BlockMemInfo {
public:
  BasicBlock *BB;
  bool GuaranteedToExecute;
  std::map<const SCEV *, MemProperty> BlockMemAccess;
  BlockMemInfo(BasicBlock *BB, bool GuaranteedToExecute)
      : BB(BB), GuaranteedToExecute(GuaranteedToExecute) {
    BlockMemAccess.clear();
  }
  // Add the memory access with its property
  void addMemoryAccess(const SCEV *S, MemProperty AccessTy);
  // Returns GuaranteedToExecute
  bool isBlockGuaranteedToExecute() { return GuaranteedToExecute; }
  // Copies memory accesses and its properties from the input BlockMemInfo
  void copyBlockMemInfo(BlockMemInfo *BMI);
};

// MemoryPaddingAnalysis : Performs the memory padding analysis
class MemoryPaddingAnalysis {
public:
  Value *InitMem;
  const TargetLibraryInfo *TLI;
  const TargetTransformInfo *TTI;
  bool CanPadd;
  MapVector<Value *, bool> ValTracker;
  MapVector<Value *, bool> OriginCollection;
  MemoryPaddingAnalysis(Value *InitMem, const TargetLibraryInfo *TLI,  const TargetTransformInfo *TTI)
    : InitMem(InitMem), TLI(TLI), TTI(TTI), CanPadd(false)  {
    ValTracker.clear();
    OriginCollection.clear();
  }
  // Return true if the value is already analyzed
  bool isVisited(Value *V) {
    return (ValTracker.find(V) != ValTracker.end());
  }
  // Mark visited for analyzed value
  void markVisited(Value *V) {
    ValTracker[V] = true;
  }
  // Add the origin instruction
  void addOrigin(Value *V) {
    OriginCollection[V] = true;
  }
  // Return true if its safe to padd the collected origin
  bool canPadd() { return CanPadd; }
  // Collect the set of origin instructions for the input value
  void collectOriginInsts(Value *V);
  // Analyze the origin instructions and check padding eligiblity
  void checkPaddingEligiblityForOrigins();
  // Analyze the init instruction by collecting and processing the origins
  void analyzeMemAccessForPadding();
};

// MemSafetyAnalysis: Performs the memory access safety analysis
class MemSafetyAnalysis {
private:
  Loop *L;
  LoopInfo *LI;
  ScalarEvolution *SE;
  DominatorTree *DT;
  const TargetLibraryInfo *TLI;
  const TargetTransformInfo *TTI;
  bool IsAnalysisValid;
  // Maps the blocks and its BlockMemInfo
  std::map<BasicBlock *, BlockMemInfo *> BlockMemAccessMap;
  // Keep track of the memory which are guaranteed to execute
  // in the loop body
  std::map<const SCEV *, MemProperty> SafeMemoryAccesses;
  // Map to stores the padding analysis
  MapVector<Value *, MemoryPaddingAnalysis *> MemoryPaddingAnalysisMap;
  // For a input blocks returns its BlockMemInfo 
  BlockMemInfo *getBlockMemInfo(BasicBlock *);
  // Clear the allocated momory
  void clearLocalMemory();
  // Return true if block is guaranteed to execute
  bool blockGuaranteedToExecute(BasicBlock *);
  // Add the memory access to loop level guaranteed execution map
  void addGuaranteedMemoryAccess(const SCEV *S);
  // Return true if the loop structure is legal
  bool isLegalLoopStructure();
  // Analyze the memory access in the current block
  bool processBlock(BasicBlock *);
  // Initiate the analysis by processing blocks for loop
  bool analyzeMemoryAccessesInLoop();
public:
  MemSafetyAnalysis(Loop *L, LoopInfo *LI, ScalarEvolution *SE,
                    DominatorTree *DT, const TargetLibraryInfo *TLI,
		    const TargetTransformInfo * TTI)
      : L(L), LI(LI), SE(SE), DT(DT), TLI(TLI), TTI(TTI), IsAnalysisValid(false) {
    BlockMemAccessMap.clear();
    SafeMemoryAccesses.clear();
    MemoryPaddingAnalysisMap.clear();
    if (!TTI->hasAVX512() && isLegalLoopStructure())
      analyzeMemoryAccessesInLoop();
  }
  ~MemSafetyAnalysis() {
    auto Itr = MemoryPaddingAnalysisMap.begin();
    while (Itr != MemoryPaddingAnalysisMap.end()) {
      delete Itr->second;
      Itr++;
    }
  }
  // Return the memory safety analysis for given value
  MemoryPaddingAnalysis* getMemoryPaddingAnalysis(Value *V);
  // Returns true if the memory padding safe
  bool isMemoryAccessSafeWithPadding(Value *V);
  // Return true if a memory access if a access is guaranteed to
  // execute in loop
  bool isGuaranteedMemoryAccess(const SCEV *S);
  // Return true if a memory access if a access is guaranteed to
  // execute in loop, with the help of memory padding
  bool isGuaranteedMemoryAccessWithMemPadding(Value *V);
  // Return true if the analysis can be used
  // Clients are expected to check this first before accssing the
  // analysis result
  bool isLegalAnalysis() { return IsAnalysisValid; }
  // Prints the analysis
  void printAnalysis();
};
#endif
