//=- ArrayDFA.h - Array data flow 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.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_ARRAYDFA_H
#define LLVM_ANALYSIS_ARRAYDFA_H
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Analysis/ISLQueryBuilder.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/ModuleSlotTracker.h"
#include "llvm/IR/TypeFinder.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/CodeExtractor.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ArrayDFAUtils.h"
#include <iostream>
#include <list>

using namespace llvm;
namespace llvm {

// Forward Declaration
struct DFASet;
struct AM;       // Abbreviation for Array Marker: AM
struct ArrayAcc; // Abbreviation for ArrayAccessInfo: ArrayAcc (or AC)
struct ArrBlock; // Abbreviation for ArrBlockInfo: ArrBlock (or AB)
typedef DenseMap<Value *, Value *> PHEqValMap;

enum ArrAnalyType { ARRAY_ANALYSIS, AOP_ANALYSIS };

struct MemObjAndUse {
  Value *RootMemObj;
  std::list<Value *> *SafeUsesOfRootMemObject;
  Loop *InitLoop;
  BasicBlock *InitLoopExitBB;
  Loop *InitLoopsExitLoop;
};

struct ArrayFuncNode {
  Value *ARR;
  Function *Func;
  std::list<CallInst *> *CIList;
};

struct DeadOpInfoNode {
  BasicBlock *BB;                    // BB were a virtual def could be dead
  Loop *L;                           // Loop of BB
  DFASet *DeadDefs;                  // Dead Defs in terms of scale
  std::list<ArrayAcc *> *DeadACList; // Ac's associated with DeadDefs
  Instruction *MArr;                 // The MArr corresponding to which the dead definition is found
  Function *MArrFunc; // Function in which MArr is present
};

  // Associate Basic block with DFASet
typedef DenseMap<BasicBlock *, DFASet *> BBMapDFASet;

// Utils
Value *GetPtrArg(CallInst *CI);
Value *FindIntArg(CallInst *CI);

class ArrayDFA {
public:

  void InitCommonData(Module &M);

  explicit ArrayDFA() {}

  // Argument info
  // 1. Module
  // 2. AnalyTy (Analysis Type)  = ARRAY_ANALYSIS for Array Analysis
  //                               AOP_ANALYSIS for AOP Analysis
  // 3. MARR is the array for ADFA
  // 4. CILst is a specific set of call instructions list used during AOP
  //    analysis only, it is null during ARR analysis
  explicit ArrayDFA(Module &thisM, 
      function_ref<LoopInfo * (Function&)> LookupLoopInfo,
      function_ref<DominatorTree * (Function&)> LookupDominatorTree,
      function_ref<PostDominatorTree * (Function&)> LookupPostDominatorTree,
      function_ref<ScalarEvolution * (Function&)> LookupScevInfo,
      Value *MARR,
      ArrAnalyType AnalyTy = ARRAY_ANALYSIS,
      std::list<CallInst *> *CILst = nullptr)
      : thisM(&thisM) , 
      LookupLoopInfo(LookupLoopInfo), 
      LookupDominatorTree(LookupDominatorTree),
      LookupPostDominatorTree(LookupPostDominatorTree),
      LookupScevInfo(LookupScevInfo),
      AOPAnalysis(AnalyTy) { }
  
  explicit ArrayDFA(Module &thisM, 
      function_ref<LoopInfo * (Function&)> LookupLoopInfo,
      function_ref<DominatorTree * (Function&)> LookupDominatorTree,
      function_ref<PostDominatorTree * (Function&)> LookupPostDominatorTree,
      function_ref<ScalarEvolution * (Function&)> LookupScevInfo,
      function_ref<BasicBlock*(Loop*, DominatorTree*, LoopInfo*, MemorySSAUpdater*, bool) > InsertPreHeaderFunction,
      Value *MARR,
      ArrAnalyType AnalyTy = ARRAY_ANALYSIS,
      std::list<CallInst *> *CILst = nullptr)
      : thisM(&thisM) , 
      LookupLoopInfo(LookupLoopInfo), 
      LookupDominatorTree(LookupDominatorTree),
      LookupPostDominatorTree(LookupPostDominatorTree),
      LookupScevInfo(LookupScevInfo),
      AOPAnalysis(AnalyTy),
      Preheaderfunc(InsertPreHeaderFunction) { }

  ~ArrayDFA() {
    ClearADFADataStructures();
    ToInsertIfCondList.clear();
  }

  bool runOnModule();

  function_ref<LoopInfo * (Function&)> LookupLoopInfo;
  function_ref<DominatorTree * (Function&)> LookupDominatorTree;
  function_ref<PostDominatorTree * (Function&)> LookupPostDominatorTree;
  function_ref<ScalarEvolution * (Function&)> LookupScevInfo;
  function_ref<BasicBlock*(Loop*, DominatorTree*, LoopInfo*, MemorySSAUpdater*, bool) > Preheaderfunc;
  
  static Type *LTy; // initialized by InitCommonData and dependent upon Module
  
  std::unordered_map<Function*, LoopInfo*> FuncLoopInfoMap;
  std::unordered_map<Function*, ScalarEvolution* > FuncSEMap;
  
  const DataLayout *DL; // initialized by InitCommonData and dependent upon Module
  Module *thisM;
  
  struct MainArrayNode {
    Instruction *MArr;
    Function *MArrFunc; // Function in which MArr is present
    Loop *MArrMainAnlyLoop;
  };
  std::list<MainArrayNode*> MArrNs;

  bool ComputeTransformationData();
  void ComputeTransformDataForScalarInstruction(Instruction *ScalarI, ArrayAcc* ScalarI_AC, std::list<ArrBlock*> LiveOuts, Instruction *MArr);
  void ComputeTransformDataForInstructionInScalarLoop(Instruction *MArr,
                                                      Instruction *I, ArrayAcc* L_AC,
                                                      const SCEV* InitialValueOfInductionVar, const SCEV* FinalValueOfInductionVar,
                                                      const SCEV* IterationCount,
                                                      ArrBlock* LiveArrBlock, ArrBlock* DeadArrBlock);
  void ComputeTransformDataForInstructionInVectorizedLoop(Instruction *MArr, 
                                                          std::list<Instruction*> VI, ArrayAcc* VI_AC,
                                                          PHINode *InductionVariable, const SCEV *InductionVariableSV,
                                                          const SCEV *InitialValueOfInductionVar, const SCEV *FinalValueOfInductionVar,
                                                          const SCEV* IterationCount,
                                                          ArrBlock* LiveArrBlock, ArrBlock* DeadArrBlock);

  std::map<Loop*, std::list<std::pair<const SCEV*, const SCEV*> > > LoopSplitPartitionMap;
  std::map<Loop*, std::list<std::pair<Instruction*, int> > > LoopSplitToDeleteInsMap;

  struct ToInsertIfCond
  {
    Instruction *MArr; // Main Array Instruction
    Instruction *ForInstruction; // Instruction which tries to access MArr
    Instruction *ForInstructionAddr; // Address which forInstruction uses
    const SCEV *Word; // Word size which is accessed by the forInstruction
    const SCEV *DeadStart; 
    const SCEV *DeadEnd;
    const SCEV *UnionLiveOutStart;
    const SCEV *UnionLiveOutEnd;
  };

  std::list<ToInsertIfCond*> ToInsertIfCondList; // List of instructions to insert if condition

  std::list<Instruction*> InsToDeleteList; // Map to track instructions to be deleted

  void InsertSuitablePreHeader(LoopInfo *LI, DominatorTree *DT, MainArrayNode *MArrN);

  // Size of each element in MARR in bytes.
  std::unordered_map<Instruction*, unsigned int> InsMARREleSzMap;  
  std::unordered_map<Instruction*, Type*> InsTypeMap;
  
  // SCEV expression for MARRElemSz
  std::unordered_map<Instruction*, const SCEV*> InsMARREleSzSVMap;

  std::unordered_map<Function*, Value*> FuncVirtualUKmap; 

  /*
    Ask Suresh what is the need of this
  */
  std::unordered_map<Function*, PHEqValMap> FuncPHIEqValMap; 

  int AOPAnalysis;
  std::unordered_map<Instruction*, BBMapDFASet> InsUseSetMap;
  std::unordered_map<Instruction*, BBMapDFASet> InsDefSetMap;
  std::unordered_map<Instruction*, BBMapDFASet> InsOrgUseSetMap; // Redundant data structure to track original Uses.
  std::unordered_map<Instruction*, BBMapDFASet> InsOrgDefSetMap; // Redundant data structure to track original Defs.
  std::unordered_map<Instruction*, BBMapDFASet> InsInSetMap;
  std::unordered_map<Instruction*, BBMapDFASet> InsOutSetMap;

  void ClearBBMapDFASet(BBMapDFASet dfaset);

  // Will be common across all the MArrNs 
  // ?? side-effect is that it can grow very large in size
  std::unordered_map<Instruction*, std::list<ArrBlock *> > InsScaleMap; 
  std::unordered_map<Instruction*, int> InsScaleLenMap;
  std::unordered_map<Instruction*, int> InsSetSzMap;

  static bool IsValueLessThanEqual(AM &Fam, AM &Sam,
                                   std::list<ArrBlock *> &Scale);
  static bool IsValueLessThanEqualForStrictCheck(AM &Fam, AM &Sam,
                                   std::list<ArrBlock *> &Scale);
  static Loop *IsInsnInLoop(LoopInfo *LI, Instruction *Insn);
  static const SCEV *GetImmLoopExitValue(LoopInfo *LI,
                                         ScalarEvolution *SE, ArrayAcc *AC);
  static int GetTySize(Type *Ty, const DataLayout *DL);

  bool IsIterativeAdd(ArrayAcc *AC, MainArrayNode *MArrN);
  
  static bool IsPHIEqual(PHEqValMap &PHIEqValMap, PHINode *PHI1, PHINode *PHI2);
  static int GetIncVal(LoopInfo *LI, const SCEV *SV, int &status,
                       Instruction **AddI = nullptr);
  static int GetSVSize(const SCEV *SV);

  // Following are the external interface routines.
  std::list<DeadOpInfoNode *> DeadOpInfoNodeList; // Will be common for all MARRs

  // Maintain a map for proper mapping of definitions to the preheaders
  // TODO: This is a poor way to maintain a mapping, try to find a better way
  /*
    This is needed because in function RelateUses, defs gets propaged downwards so there may be cases where
    dead def is coming up on a basic block but that definition may not be even there in that basic block as 
    it was came to that basic block from some other basic block.

    Example:

    Label1 : Def [0, 10]
    Label2 : Def [11, 20]
    Label3 : Def [0, N]

    In RelateUseDefs function the defs will be changed

    Label1 : Def [0, 10]
    Label2 : Def [11, 20]
    Label3 : Def [0, N] , Def [11, 20], Def [0, 10], Use [0, 10], Use [11, 20]

    Let's assume Def[11, 20] is dead at Label3 then there's no way to get that Def[11, 20] is actually there
    in Label 2. 

    The following map helps to ensure this mapping.

    Note:
    This resolution happens at the Scale level, so the Defs will get propagated only once. A chain of propagation 
    never happen
  */
  std::map<Instruction*, std::map<BasicBlock*, std::list<BasicBlock *> > > DefPreHeaderMap;
  /*
    To maintain proper mapping from Instruction to the base address the instruction is using.
  */
  std::map<Instruction*, Instruction*> InsAddressInsMap;

  ArrayDFA *ComputeLivenessInfo(Module &M, std::list<Value *> ARRs, ArrAnalyType AnlyTy,
                                std::list<CallInst *> *CILst);

  // Release all the resources allocated by ArrayDFA.
  void ClearADFADataStructures(void);

  // Check if a single ArrBlock is live out of ArrayAcc
  ArrBlock* IsSingleActiveLiveOut(ArrayAcc* AC, ArrBlock** NonDelete, Function* MArrFunc, Instruction *MArr);

  // Finds the LiveOuts of the given Basic block BB
  // 1. BB is the concerned BasicBlock
  // 2. LiveOutSets is dynamically created array of pointers to ArrBlock,
  //    the client is supposed to free this array.
  // 3. Len is the number of entries in LiveOutSets
  void GetLiveOut(BasicBlock *BB, ArrBlock **LiveOutSets, int &Len);

  // Finds the LiveIns of the given Basic block BB
  // 1. BB is the concerned BasicBlock
  // 2. LiveInSets is dynamically created array of pointers to ArrBlock,
  //    the client is supposed to free this array.
  // 3. Len is the number of entries in LiveOutSets
  void GetLiveIn(BasicBlock *BB, ArrBlock **LiveInSets, int &Len);

  // Finds the Uses of the given Basic block BB
  // 1. BB is the concerned BasicBlock
  // 2. UseSets is dynamically created array of pointers to ArrBlock,
  //    the client is supposed to free this array.
  // 3. Len is the number of entries in LiveOutSets
  void GetUse(BasicBlock *BB, ArrBlock **UseSets, int &Len);

  // Finds the Defs of the given Basic block BB
  // 1. BB is the concerned BasicBlock
  // 2. DefSets is dynamically created array of pointers to ArrBlock,
  //    the client is supposed to free this array.
  // 3. Len is the number of entries in LiveOutSets
  void GetDef(BasicBlock *BB, ArrBlock **DefSets, int &Len);

  // Check all criteria of pruning a function.
  // This includes ISL specifics only
  bool isLegalToPrune(Function *F, Value *StartAddr, Value *TotalElements,
                      unsigned ElementSize, PHINode *, PHINode *);

  // Display the dead ops found.
  void DisplayDeadOpInfoNodeList(void);

  // Display the IN and OUT sets computed.
  void DumpFuncsInsOuts(MainArrayNode *MArrN);
 
  void DumpFuncsInsDefsAndOuts(MainArrayNode *MArrN);

  // Display the USE and DEF sets computed.
  void DumpFuncsUseDefs(MainArrayNode *MArrN);

  std::map<Function*, PostDominatorTree*> FuncPostDominatorTreeMap;
  std::map<Function*, DominatorTree*> FuncDominatorTreeMap;
private:

  Type *I8Ty; // initialized by InitCommonData and dependent upon Module
  Type *I8PtrTy; // initialized by InitCommonData and dependent upon Module
  LLVMContext *Cntx; // initialized by InitCommonData and dependent upon Module
  // Instruction *LifeTimeStart;
  bool M64; // initialized by InitCommonData and dependent upon Module
  bool M32; // initialized by InitCommonData and dependent upon Module
  Module *Modl; // initialized by InitCommonData and dependent upon Module

  // RootMemObject is the Mem object whose addresses are stored into
  // MARR (in case of AOP analysis). RootMemObject should not be used
  // for any other purpose apart from initializing the MARR.
  Value *RootMemObject;

  // There could be multiple RootMemObjects used in exclusive paths
  // which could arise in case of function versioning. which is the
  // case with MCF.
  std::list<MemObjAndUse *> RootMemObjectList;

  // MARROtherUses are analysed and access information of each
  // and every accesses in collected in MARRAccList.
  std::unordered_map<Instruction*, std::list<ArrayAcc*> > MARRAccListMap;

  typedef DenseMap<BasicBlock *, int> PresenceBBMap;

  // Reverse order of basic block starting from an exit
  // block to speed up DFA.
  std::unordered_map<Function*,std::list<BasicBlock *> > FuncRevOrdBBMap;
  std::unordered_map<Function*,std::list<BasicBlock *> > FuncNormalOrdBBMap;
  std::unordered_map<Loop*,std::list<BasicBlock *> > LoopRevOrdBBMap;
  std::unordered_map<Loop*,std::list<BasicBlock *> > LoopNormalOrdBBMap;

  // Edges which need to be avoided for proper ADFA.
  // PresenceBBMap HinderEdges; // Ask Suresh if HinderEdges is MArr independent
  std::unordered_map<Instruction*, PresenceBBMap> InsHinderEdgesMap;

  typedef DenseMap<ArrayAcc *, int> AccessIOrdMap;

  typedef DenseMap<Loop *, int> PresenceLoopMap;

  // Loops in which uses and defs cannot be moved to preheaders
  std::unordered_map<Instruction*, PresenceLoopMap> InsConservativeLoopsMap;
  std::unordered_map<Instruction*, PresenceBBMap> InsAvoidPreHeadBlocksMap;


  typedef DenseMap<Value *, int> PresenceValMap;
  PresenceValMap VisitedValMap;

  // This is a list of functions which determine the
  // the criteria for selecting an AOP for analysis.
  // This is implemented for the specific needs of MCF.
  std::list<CallInst *> *StartCIList;

  bool isRootMemObjUsedInMAOPInitOnly(MainArrayNode* MArrN);
  
  Type *GetBaseArrTy(Type *Ty);
  void DumpSafeUsesOfRootMemObject(void);
  bool isLifeTimePattern(Instruction *MainI);
  const SCEV *GetLoopIterCount(Instruction *MainGEPSVI);

  bool GetReverseOrderedBB(Function *F, Loop *MainAnalysisLoop, Instruction *MArr);

  void GetExitBB(Function *F, std::list<BasicBlock *> &ExitBBList);
  BasicBlock *GetExitBB(Function *F);
  bool isFuncOfReqType(Function *Fn);
  void ClearFuncAnalysisInfo(void);
  bool AllLoopAreSame(std::list<Loop *> &AllLoops);

  void AddToMARRAccList(Instruction *AccessI, Instruction *ArrAddrI, MainArrayNode *MArrN);

  void PerformAOP_DFA(Module &M, Instruction *MAOP1,
                                std::list<CallInst *> *CILst);
                                
  void DisplayMARRAccListM(Instruction *MArr, int DispKey,
                          bool DispLoop/*default: False*/, Function *MArrF);

  bool FindAnalysisScopeOfMARR(MainArrayNode *MArrN);

  void MergeSVOfUnRolledAccesses(void);
  
  Loop *IsInsnInLoopDFA(Instruction *Insn, MainArrayNode* MArrN);

  bool ComputeSVEnd(ArrayAcc *AC);
  
  bool ComputeSVStartEndStep(MainArrayNode *MArrN);
  bool ComputeSVStartEndStepForArrayAcc(Instruction *MArr, Function *MArrFunc, ArrayAcc *AC);

  bool CheckSanityOfStartEndWordStep(MainArrayNode *MArrN);
  
  bool ComputeRelationalStart(ArrayAcc *AC);

  void ComputeMARRAccSetScale(MainArrayNode *MArrN);

  int SearchArrSetScale(ArrayAcc *AC, MainArrayNode *MArrN);

  void ComputeUseDefs(MainArrayNode *MArrN);

  bool AreLoopsDifferentInAccessInsList(std::list<Instruction*>& AccessInsList, MainArrayNode *MArrN);

  BasicBlock *GetPreHeadBlock(ArrayAcc *AC, MainArrayNode *MArrN);

  void ComputeMemLiveness(MainArrayNode *MArrN);

  void RelateUseDefs(MainArrayNode *MArrN);

  bool isSortedMergeKeysContinuous(int MergedKeys[], int MergedKeysLen, MainArrayNode *MArrN);

  void EraseRedundantKnownSetEntries(MainArrayNode *MArrN);

  AM GetAlreadyExistingEqArrayMarker(AM AM, MainArrayNode *MArrN);

  void ComposeSubKeyInAllDFASetsHavingSuperKey(int SuperKey, int SubKey, Instruction *MArr);

  void MergeSameSVOfUnRolledAccesses(MainArrayNode *MArrN);

  void PerformARR_DFA(Module &M, std::list<MainArrayNode*> MArrNs);

  const SCEV *ReplaceUnknownWithSV(const SCEV *MainSV, const SCEVUnknown *U1,
                                   const SCEV *SV_Index);

  void ComposeSubKeyInAllDFASetsHavingSuperKeyUnknown(int SuperKey, int SubKey, Instruction *MArr);

  void MergeSVOfUnRollAccesses(MainArrayNode *MArrN);

  void
  PerformSimpleMerge(ScalarEvolution *SE, std::list<ArrayAcc *>::iterator ACCI,
                          std::list<ArrayAcc *> &DelDFAList, MainArrayNode *MArrN);

  void IsAdjVectorBBMerge(std::list<ArrayAcc *>::iterator ACCI,
                          std::list<ArrayAcc *> &DelDFAList, MainArrayNode *MArrN);
  

  void IsAdjVectorLoopMerge(ScalarEvolution *SE, std::list<ArrayAcc *>::iterator ACCI,
                            std::list<ArrayAcc *> &DelDFAList, MainArrayNode *MArrN);

  ArrayAcc *GetAdjVectorLoopAC(BasicBlock *ExitB,
                               std::list<ArrayAcc *> &DelDFAList, Instruction *MArr);

  void ReverseBackWardAccess(Instruction *MArr);

  int GetNumSucc(BasicBlock *BB);
  int GetNumPred(BasicBlock *BB);

  BasicBlock* RememberHinderEdges(BasicBlock *PreHeader, Instruction *MArr);

  ArrayAcc *IsAccessBBAlreadyRecorded(BasicBlock *BB, Instruction *MArr);

  ArrayAcc *IsAccessIAlreadyRecorded(Instruction *NewI, Instruction *AddrI, Instruction *MArr);

  void SortMARRAccList(MainArrayNode *MArrN);

  bool IsVecMiddleBlock(BasicBlock *ExitB);
  BasicBlock *IsPrimLoop(BasicBlock *BB);
  bool IsVecPhBlock(BasicBlock *ExitB);
  bool IsPreheaderForVectorAndEpilogueLoop(BasicBlock *BB, MainArrayNode *MArrN);

  void RecordInfoOnDeadDefs(MainArrayNode *MArrN);

  void CollectDeadACInfo(BasicBlock *CurrBB, DFASet *DeadDefs, MainArrayNode *MArrN);

  void GetKeysInSet(DFASet *TSet, int Keys[], int &NumKeys);

  void ComputeActiveLiveOutsOfAC(void);
  bool IsASucc(BasicBlock *BB, BasicBlock *SuccOfBB);
  bool PathExists(BasicBlock *BBStart, BasicBlock *BBDest);
  MemObjAndUse *GetExistingRootMemObj(Value *NewRoot);
  void DisplayRootMemObjects(void);
  void SkipRawUsesofRootMemObjects(void);

  void AnalyzeAllMARRUses(Instruction *ValI, int &Status, MainArrayNode *MArrN);
  bool AnalyzeArrEleUsage(Instruction *MemAccessI, MainArrayNode *MArrN);
  
  bool AnalyzeStructFieldUsage(Instruction *LoadAddr, MainArrayNode *MArrN);
  bool isPHIPathsUnderstood(Instruction* PHIIns, Instruction* AddrI, MainArrayNode* MArrN);
  
  Value* IsaBinPHIWithOneNullInput(Value* Val);

  Instruction *GetAddrValAOP(Value *Val);
  bool IsCallInStartCIList(Instruction *I);
  Instruction *FindCurrentRootMemObj(Instruction *StoreI,
                                     std::list<Instruction *> &ImmediateUse);
  bool FindTrackCurrentRootMemObj(Instruction *SI);

  Instruction *GetAddrValArr(Instruction *Val, Instruction *MArr);

  void TransferAccessI(ArrayAcc *DestAC, ArrayAcc *SrcAC,
                       std::list<ArrayAcc *> &DelDFAList);

  bool IPostDominatesLoopEntry(Instruction *I, MainArrayNode *MArrN);
  
  bool IsInLoopExitBlocks(Loop *CurrLoop, BasicBlock *BB);
  BasicBlock *GetLoopEntryBB(Loop *CurrLoop);

  void FindConservativeLoops(MainArrayNode *MArrN);

  void PerformSimpleMergeBB(ScalarEvolution *SE, std::list<ArrayAcc *>::iterator ACCI,
                            std::list<ArrayAcc *> &DelDFAList, MainArrayNode *MArrN);

  bool CheckForCompleteWordAcc(ScalarEvolution *SE, MainArrayNode *MArrN);

  BasicBlock *DetermineVecConPreHead(BasicBlock *BB, Instruction *MArr);
  
  BranchInst *GetBranchI(BasicBlock *iBB);

  bool GetMAOPInitLoop(MemObjAndUse *RN, MainArrayNode* MArrN);
  
  bool IsSingleNodeLoop(BasicBlock *BB);
  void ReSolvePHIs(BasicBlock *DummyPreHead, BasicBlock *PreHeader);
  void FreeADFASets(void);
  void ClearFuncsWithArrInp(void);

  void ClearMARRAccListMap(void);
  
  void ClearRootMemObjectList(void);
  void ClearDeadOpInfoNodeList(void);
  bool trackUsageOfInterest(Value *V, Function *F,
                            SmallVector<Value *, 2> &UseInst,
                            SmallVector<CallInst *, 2> &RecursiveCS,
                            MapVector<Value *, bool> &Tracker);

  bool GetPtrEleTy(Value* V, Type** EleTy, PresenceValMap& VisValMap);

  bool IsADeadDefAndBoundVarsNotModifiedInInterveningBBs(BasicBlock *CurrBB, Instruction *MArr, Function *MArrFunc);
  bool CheckIfAllValsAreAvailableAtLoopEntry(ScalarEvolution *SE, Loop *L, ArrBlock *LiveArrBlocks, ArrBlock *DeadArrBlocks);


  bool CheckIfAllValsAreNotModifiedUntilLiveOut(BasicBlock *CurrBB, int AB_Index,
      std::list<Value *> &AllVals, Instruction *MArr);

  bool BBDefinesValue(BasicBlock *BB, std::list<Value *> &AllVals);
};


class ArrayDFALegacyPass :public ModulePass {
public:
    /// AnalysisUsage
    virtual void getAnalysisUsage(AnalysisUsage& AU) const {
        AU.addRequired<DominatorTreeWrapperPass>();
        AU.addRequired<LoopInfoWrapperPass>();
        AU.setPreservesAll();
    }
public:
    static char ID;
    ArrayDFA* Impl;

    /// Constructor
    ArrayDFALegacyPass() : ModulePass(ID) {
        initializeArrayDFALegacyPassPass(*PassRegistry::getPassRegistry());
    }

    virtual bool runOnModule(Module& M);

};

struct ArrayDFAPass : public PassInfoMixin<ArrayDFAPass> {
public:
    PreservedAnalyses run(Module& M, ModuleAnalysisManager& AM);
};

/// Analysis pass that exposes the \c LoopInfo for a function.
class ArrayDFAAnalysis : public AnalysisInfoMixin<ArrayDFAAnalysis> {
    friend AnalysisInfoMixin<ArrayDFAAnalysis>;
    static AnalysisKey Key;

    ArrayDFA Impl;
public:
    typedef ArrayDFA Result;
    Result run(Module& M, ModuleAnalysisManager& AM);
};



// ========================================================================================
// Start: DFASet is an abstract data type to simulate a Set (is used to manage
// USE/DEF/IN/OUT) Here each bit 'AccSet' indicates the presence of absence of
// an element (as indicated by 'Scale[i]'). This helps to compute
// Set Unions/Intersection/Differences faster.
// ========================================================================================

struct DFASet {

  char *AccSet; // Each bit in AccSet corresponds to corresponding element in
                // Scale

  static ArrBlock *
  GetNthArrBlockInScale(std::list<ArrBlock *> &Scale, int PosKey);
  static void DisplayScale(std::list<ArrBlock *> &Scale);
  static void DeleteScale(std::unordered_map<Instruction*, std::list<ArrBlock*> >& ScaleMap);

   DFASet(int SetSz) { AccSet = (char *)calloc(SetSz, sizeof(char)); }
  ~DFASet() { free(AccSet); }

  friend DFASet *DFASetUnion(DFASet *S1, DFASet *S2, int SetSz);
  friend DFASet *DFASetDifference(DFASet *S1, DFASet *S2, int SetSz);
  friend bool isDAFSetEqual(DFASet *S1, DFASet *S2, int SetSz);
  void ComposeSet(int Key);
  void UnComposeSet(int Key);
  bool isBitSet(int Key);
  bool isDFASetEmpty(int SetSz);
  void Display(std::list<ArrBlock *> &Scale, int ScaleLen, int SetSz);
  void GetAllKeysInDFASet(int Keys[], int &NumKeys, int ScaleLen);
  bool GetNumBitsSet(int ScaleLen);
};

// ========================================================================================
// End: DFASet
// ========================================================================================




// ========================================================================================
// Start: AM (Array Marker) is an abstract data type to track a location in ARR.
// ========================================================================================
struct AM { // Abbreviation: AM Stands for Array Marker

  // Contains Scev Expr of ARR loc, if Arr_Index is non constant
  const SCEV *SV_Index;

  friend int isConsAMEqual(AM const &, AM const &);
  //friend int operator<=(AM const &, AM const &);
  friend int isAMLessThanEq(AM const &, AM const &,
                            std::list<ArrBlock *> &Scale, ScalarEvolution *SE);
  friend int isAMEqual(AM &Fam, AM &Sam, ScalarEvolution *SE);

  const SCEV *GetSV_Index(void);
  void SetSV_Index(const SCEV *SV_Idx);
  bool isConst(void) const;
  bool isVar(void) const;
  bool isUK(void) const;
  long GetConVal(void) const;
  void Display(void);
};

// ========================================================================================
// End: AM (Array Marker)
// ========================================================================================

// ========================================================================================
// Start: ArrBlock is an abstract data type to track a block of locations in
// ARR.
// ========================================================================================
struct ArrBlock {
  AM StartAM; // Start of ArrBlock
  AM EndAM;   // End of ArrBlock
  AM StepAM;  // Step size for array accesses happen from StartAM to EndAM
  AM WordSz;  // Word size indicates the size of word accessed

  friend struct DFASet;

  ArrBlock() : StartAM({0}), EndAM({0}), StepAM({0}), WordSz({0}) {
    ScaleKey = -1; // Default value for ScaleKey
  }

  ArrBlock(AM Start_SVI, AM End_SVI, AM StepSzI, AM WrdSz) {
    StartAM = Start_SVI;
    EndAM = End_SVI;
    StepAM = StepSzI;
    WordSz = WrdSz;
  }
  
  ArrBlock(ArrBlock& Other)
  {
    StartAM = Other.StartAM;
    EndAM = Other.EndAM;
    StepAM = Other.StepAM;
    WordSz = Other.WordSz;
    ScaleKey = Other.ScaleKey;
  }
  

  AM *GetStartAM(void);
  AM *GetEndAM(void);
  AM *GetStepAM(void);
  AM *GetWordSz(void);
  void SetStartAM(const SCEV *SV_Idx);
  void SetEndAM(const SCEV *SV_Idx);
  void SetStepAM(const SCEV *SV_Idx);
  void SetWordSz(const SCEV *WSz);
  bool isWordSzAndStepSzSame(ScalarEvolution *SE);
  bool isACompleteWord(ScalarEvolution *SE);

  friend int isABEqual(ArrBlock const &, ArrBlock const &, ScalarEvolution *SE);
  bool isStartAMConst(void);
  bool isEndAMConst(void);
  bool isStepAMConst(void);

  bool isStartAMVar(void);
  bool isEndAMVar(void);
  bool isStepAMVar(void);
  bool isStartAMUK(void);
  bool isEndAMUK(void);
  bool isStepAMUK(void);

  bool isConst(void);
  void Display(void);
  long GetStepVal(void);
  void ReComputeWordSz(ScalarEvolution *SE);

  int ScaleKey; // An internal Data, Key index into ArrayDFA::Scale
};

// ========================================================================================
// End: ArrBlock
// ========================================================================================


// ========================================================================================
// Start: ArrayAcc is an abstract data type to track array accesses. It stores
// all the required information to perform ADFA.
// ========================================================================================
struct ArrayAcc {
  Instruction *ArrayAddr; // Pointer arith instruction
  const SCEV *ArrAddrSV;  // Scev for ArrayAddr
  ArrBlock AB;            // Block of elements which are accessed.


  // Flag to indicate that this ArrayAcc is merged with some other ArrayAcc from a seperate loop
  bool IsAdjVectorLoopMerged;

  // Array Access Insns like Loads/Stores/Calls operating on ArrayAddr
  // Note: Until later merge activity AccessInsList would contain a
  // single instruction.
  std::list<Instruction *> AccessInsList;
  BasicBlock *PreHeadBB; // A block where AccessI is assumed to be use/def

  DFASet *ActiveOutList; // Analysed and collected information on AB's which
                         // could be live outs conservatively.

  ArrayAcc(Instruction *ArrayAddrI, Instruction *ArrayAccI, ScalarEvolution *SE)
      : AB{{0}, {0}, {0}, {0}} {

    ArrayAddr = ArrayAddrI;
    ArrAddrSV = SE->getSCEV(ArrayAddrI);
    AB = ArrBlock{{0}, {0}, {0}, {0}};
    AccessInsList.push_back(ArrayAccI);
    AB.ScaleKey = -1;
    ActiveOutList = nullptr;
    // Initially the PreHeadBB will be equal to BB where ArrayAccI belongs
    PreHeadBB = ArrayAccI->getParent();
    IsAdjVectorLoopMerged = false;
  }

  ArrayAcc(ArrayAcc*& Other):
    ArrayAddr(Other->ArrayAddr),
    ArrAddrSV(Other->ArrAddrSV),
    AccessInsList(Other->AccessInsList),
    PreHeadBB(Other->PreHeadBB),
    ActiveOutList(Other->ActiveOutList),
    IsAdjVectorLoopMerged(Other->IsAdjVectorLoopMerged)
  {
    AB = ArrBlock(Other->AB);
  }

  bool isConst(void);

  bool isInAccessInsList(Instruction* I, Instruction* AddrI);
  bool AccessInsListHasStore(void);
  void Display(LoopInfo *LI, int DispKey, int DispCount, bool DispLoop = false);
  Instruction *GetFirstIAccessInsList(void);
  int GetAccessIListLen(void);
  bool ComputeSVStart(LoopInfo *LI, ScalarEvolution *SE, Value *VirtualUK, Instruction *MARR);
  bool ComputeSVStepSz(LoopInfo *LI, ScalarEvolution *SE, const DataLayout *DL);
  bool ComputeSVEnd(LoopInfo *LI, ScalarEvolution *SE, Instruction *MARR,
                    Value *VirtualUK,
                    unsigned int MARRElemSz);
  bool ComputeRelationalStart(LoopInfo *LI,
                              ScalarEvolution *SE, PHEqValMap &PHIEqValMap);
  const SCEV *GetLoopIterCount(LoopInfo *LI,
                               ScalarEvolution *SE, Instruction *MainGEPSVI);
  const SCEV *GetAccWordSz(ScalarEvolution *SE, const DataLayout *DL);
  Value *GetPossibleVarStart(LoopInfo *LI, Value *temp, Instruction *LoopI);
  Value *GetValAtLoopEntry(LoopInfo *LI, PHINode *PHIN, Loop *L);
  Loop *FindCommonLoop(LoopInfo *LI, PHINode *PHIN);
  Value *AnalyzeLoopEntryExitPHI(const Value *temp);
  Value *GetEquivalentExitingConcreteVals(Value *temp);
  void IsPHIConCurrent(PHEqValMap &PHIEqValMap, Value * ValA, Value *ValB,
                       std::list<Value *> &VisitedPHIA,
                       std::list<Value *> &VisitedPHIB, int &status,
                       Value **EqVal);
  bool HaveVisitedPHI(std::list<Value *> &VisitedPHIX, Value *PHINX);
  bool isBasicAdd(Value *ValA, Value *ValB);
  bool isVectorisedLoop(unsigned int MARRElemSz);
  BasicBlock *GetFirstIParent(void);
  void FindEqVals(PHEqValMap &PHIEqValMap, Value *temp);
  void TraverseConCurrentPHIs(PHEqValMap &PHIEqValMap, Value * PHI);
  bool AllOpsOfPHISame(ScalarEvolution *SE, PHINode *PHIN);
  unsigned GetFirstIOpcode(void);
};

// ========================================================================================
// End: ArrayAcc
// ========================================================================================

} // namespace llvm
#endif
