//===------ RegularSparseAnalysis.h - Analyzes sparse matrix patterns ----===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//
//===----------------------------------------------------------------------===//
//====  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_REGULARSPARSEANALYSIS_H
#define LLVM_ANALYSIS_REGULARSPARSEANALYSIS_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LegacyAliasAnalysis.h"

namespace llvm {

class Function;
class LoopInfo;
class DominatorTree;
class OptimizationRemarkEmitter;

class SparsificationPass : public PassInfoMixin<SparsificationPass> {
private:
  LoopInfo *LI;
  ScalarEvolution *SE;
  AliasAnalysis *AA;
  DominatorTree *DT;
  DenseMap<StoreInst*, const SCEV*> conditionalSCEV;
  DenseMap<LoadInst*, const SCEV*> conditionalSCEVLoad;
  DenseMap<StoreInst*, Constant*> initializedConst;
  DenseMap<LoadInst*, Constant*> initializedConstLoad;
  DenseMap<Instruction *, std::pair<const SCEV *, const SCEV *>>
      sparseSCEVBounds;
  // Holds the parent of the store instruction, from which it is
  // derived, nullptr if it the root.
  DenseMap<StoreInst*, StoreInst*> Parent;

  const SCEV *computeConditionalSCEV(const Loop *L, const SCEV *array_acess,
                                     const SCEV *condition_lhs,
                                     const SCEV *condition_rhs);
  const SCEV *computeSCEVwrtOuterLoop(const SCEVAddRecExpr *, const SCEV *,
                                      const SCEV *);
  const SCEV *computeSCEVwrtInnerLoop();
  void propagateSCEVInfo(Function&);
  bool isStoreReduction(StoreInst *);
  bool isStoreMulReduction(StoreInst *);

public:
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
  void runImpl(Function &F, LoopInfo *LI, ScalarEvolution *SE,
                AliasAnalysis *AA, DominatorTree *DT);

  // Get the initialized constant
  Constant *getInitializedConst(StoreInst *st) {
    if (initializedConst.find(st) == initializedConst.end())
      return nullptr;
    else
      return initializedConst[st];
  }
  void clearDS() {
    conditionalSCEV.clear();
    initializedConst.clear();
    conditionalSCEVLoad.clear();
    initializedConstLoad.clear();
  }

  DenseMap<StoreInst*, StoreInst*> getStoreChain() {
    return Parent;
  }


  bool isZeroInitialization(StoreInst *st) {
    if (getInitializedConst(st))
      return getInitializedConst(st)->isZeroValue();
    else return false;
  }

  // Returns:
  // Sparse SCEV:
  //          if the analysis able to compute.
  // scCouldNotCompute:
  //          if pattern is found, but could not compute the SCEV.
  // nullptr:
  //          if pattern isn't exist for the given store inst.
  const SCEV *getConditionalSCEV(StoreInst *st) {
    if (conditionalSCEV.find(st) == conditionalSCEV.end())
      return nullptr;
    else
      return conditionalSCEV[st];
  }

  const SCEV *getConditionalSCEV(LoadInst *ld) {
    if (conditionalSCEVLoad.find(ld) == conditionalSCEVLoad.end())
      return nullptr;
    else
      return conditionalSCEVLoad[ld];
  }

  DenseMap<StoreInst*, const SCEV*> &getConditionalSCEVStoreMap() {
    return conditionalSCEV;
  }

  DenseMap<StoreInst *, Constant*> &getConstantStoreMap() {
    return initializedConst;
  }

  DenseMap<LoadInst *, Constant*> &getConstantLoadMap() {
    return initializedConstLoad;
  }

  void print(raw_ostream &O, const Module *M = nullptr) const;
};

class SparsifyLegacy : public FunctionPass {
public:
  static char ID;
  SparsificationPass Impl;
  SparsifyLegacy() : FunctionPass(ID) {
    // The default is set by the caller.
    initializeSparsifyLegacyPass(*PassRegistry::getPassRegistry());
  }
  bool runOnFunction(Function &F) override;
  void getAnalysisUsage(AnalysisUsage &AU) const override;
  SparsificationPass *getSparseAnalysis() { return &Impl; }
  void print(raw_ostream &O, const Module *M = nullptr) const override {
    Impl.print(O, M);
  }
};

class SparseAnalysis :public AnalysisInfoMixin<SparseAnalysis>
{
  friend AnalysisInfoMixin<SparseAnalysis>;
  static AnalysisKey Key;
  SparsificationPass Impl;
public:
  typedef SparsificationPass Result;
  Result run(Function& F, FunctionAnalysisManager& AM);
};

} // end namespace llvm

#endif // LLVM_ANALYSIS_REGULARSPARSEANALYSIS_H
