#ifndef LLVM_TRANSFORMS_SCALAR_LOOPCHAIN_H
#define LLVM_TRANSFORMS_SCALAR_LOOPCHAIN_H

#include <map>
#include <string>
#include <vector>
#include <sstream>

#include "llvm/ADT/DirectedGraph.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalModRefInfo.h"
#include "llvm/Analysis/ISLUtils.h"
#include "llvm/Analysis/LoopInductionAccesses.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Support/Casting.h"
#include "llvm/Transforms/Utils/AOCCLoopUtils.h"
#include "llvm/Support/Casting.h"
#include "llvm/Transforms/Utils/AOCCLoopUtils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopSplitUtils.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PassManager.h"


#define DEBUG_TYPE "loopchain"


namespace llvm {


class LCNode;
class LCEdge;
class LCBuilder;
using LCNodeBase = DGNode<LCNode, LCEdge>;
using LCEdgeBase = DGEdge<LCNode, LCEdge>;
using LCBase = DirectedGraph<LCNode, LCEdge>;

  isl_set* dropSetDims(isl_set* set, int numToKeep);
  isl_set* matchSpaceByShrinking(isl_set* set1, isl_set* set2);
  isl_set* matchSpaceByGrowingSS(isl_set* set1, isl_set* set2);
  isl_constraint* matchSpaceByGrowing(isl_constraint* cons,isl_set* set);
  int findPosOfSetDimByName(isl_space* space,std::string name);
  Instruction* findDominantInst(const SmallVector<Instruction*, 4>& Insts,
                                const DominatorTree& DT);
  StoreInst* findDominantStore(const SmallVector<StoreInst*, 4>& Stores,
                               const DominatorTree& DT);
  bool isFlangIntrinsic(Instruction* inst);
  bool hasBackedge(const DominatorTree &DT, BranchInst *BC);
  bool hasBackedge(const LoopInfo &LI, PHINode* PHI);
  bool isConditional(BranchInst* BI);
  std::string valToStr(Value* V);
  std::string valToStr(BasicBlock* BB);
  std::string valToStr(Function* F);
  std::string valToStr(const SmallVector<int>& SV);
  std::string valToStr(const std::vector<int>& V);
  std::string valToStr(const std::vector<std::vector<int>>& V);
  std::string valToStr(isl_aff_list* AL);
  std::string valToStr(isl_aff* IA);
  std::string valToStr(isl_set* IS);
  bool valContains(Value* val, const std::string& sub);
  bool valContains(BasicBlock* BB, const std::string& sub);
  bool strEndsWith(const std::string& str, const std::string& end);
  int strToInt(const std::string& str);

  void addCombinations(const std::vector<int>& arr, std::vector<int>& combo,
                 std::vector<std::vector<int>>& result, int start,
                 int end, int index, int r);
  std::vector<std::vector<int>> intCombinations(int size, int max);

  GlobalVariable *createGlobalVariable(const std::string& Name, Module *M,
                                       Type *Ty = nullptr);
  
  bool moduleLevelDominates(const FunctionAnalysisManager &AM,
                                Instruction *I0, Instruction *I1);
}


namespace llvm {

// This class helps keep track of affine information on the way back up the
// recursive tree in valueToAff. 
class affParts{

  public:
  affParts(isl_aff* aff):aff(aff){
    aff_list = nullptr;
    mul_list = nullptr;
  }
  ~affParts(){
    delete(aff_list);
    delete(mul_list);
  }

  // concatinate the affine portions
  void concat_aff_list(affParts* other){
    // if neither list is null
    if(aff_list != nullptr && other->aff_list != nullptr){
      aff_list->insert(aff_list->end(), other->aff_list->begin(),
                                        other->aff_list->end());
      other->aff_list->clear();
      delete(other->aff_list);
      other->aff_list = nullptr;

    }else if(aff_list == nullptr){
      aff_list = other->aff_list;
      other->aff_list = nullptr;
    }
    return;
  }

// TODO: This function is incomplete
  bool compareAffParts(affParts* other){
    if(other == this){
      return true;
    }
    if(isl_aff_plain_is_equal(aff,other->aff) && 
       aff_list == other->aff_list && mul_list == other->mul_list){
      return true;
    }
    if(aff_list == nullptr){return false;}
    if(mul_list == nullptr){return false;}
    if(other->aff_list == nullptr){return false;}
    if(other->mul_list == nullptr){return false;}

    return false;

  }

  void concat_mul_list(affParts* other){
    if(mul_list != nullptr && other->mul_list != nullptr){
      mul_list->insert(mul_list->end(), other->mul_list->begin(),
                                        other->mul_list->end());
      other->mul_list->clear();
      delete(other->mul_list);
      other->mul_list = nullptr;

    }else if(mul_list == nullptr){
      mul_list = other->mul_list;
      other->mul_list = nullptr;
    }
    return;
  }

  isl_aff* aff;
  SmallVector<isl_aff*>* aff_list;
  SmallVector<isl_aff_list*>* mul_list;
} ;
raw_ostream &operator<<(raw_ostream &OS, const affParts &A);

class ScheduleElement {
  public:
  enum{INT,LOOP} tag;
  union
  {
      int c;
      llvm::Loop* loop;
  };
  ScheduleElement(int c) : c(c){tag=INT;}
  ScheduleElement(llvm::Loop *loop) : loop(loop) {tag=LOOP;}
  bool operator<(ScheduleElement& other){
    if(tag == INT && other.tag == INT){
      return c < other.c;
    }else{
      return true;
    }
  }
  bool operator==(const ScheduleElement& other){
    if(tag == INT && other.tag == INT){
      return c == other.c;
    }
    if(tag == LOOP && other.tag == LOOP){
      return loop == other.loop;
    }
    return false;
  }
  bool operator!=(const ScheduleElement& other){
    return !(*this == other);
  }

};
raw_ostream &operator<<(raw_ostream &OS, const ScheduleElement &S);

class LCNode : public LCNodeBase {
public:

  enum class DepKind { RAW, WAW, WAR, RAR };
  enum class NodeKind { Default, Statement, Data };

  static bool isl_aff_list_lt(isl_aff_list* listA, isl_aff_list* listB);
  static bool isl_aff_list_eq(isl_aff_list* listA, isl_aff_list* listB);
  static int isl_aff_list_cmp(isl_aff_list* listA, isl_aff_list* listB);

  LCNode(const LCNode &other) :
         LCNodeBase(), Kind(other.Kind), name (other.name), value(other.value),
         Dims(isl_aff_list_lt) {
    closedToForward= false;
    constraintsProcessed = false;
    domConstraints.first = nullptr;
    domConstraints.second = NULL;
    iterationSpace=NULL;
    constraintSet=NULL;
    initialIterationSpace=NULL;
  }
  LCNode(const NodeKind Kind, std::string name, Value* value) :
         LCNodeBase(), Kind(Kind), name (name), value(value),
         Dims(isl_aff_list_lt) {
    closedToForward= false;
    constraintsProcessed = false;
    domConstraints.first = nullptr;
    domConstraints.second = NULL;
    iterationSpace=NULL;
    constraintSet=NULL;
    initialIterationSpace=NULL;
  }
  LCNode(SmallVector<int> &sched,
       llvm::Loop* loop, BasicBlock* block,  
       ScalarEvolution& SE, LoopInfo& LI, std::string name = "Stmt") :
       LCNodeBase(), name(name), Kind(LCNode::NodeKind::Statement),
       Dims(isl_aff_list_lt) {
    closedToForward= false;
    constraintsProcessed = false;
    domConstraints.first = nullptr;
    domConstraints.second = NULL;
    outerLoop = NULL;
    constraintSet=NULL;
    initialIterationSpace=NULL;
    iterationSpace = NULL;
    origExecutionScheduleRel = NULL;
    currExecutionScheduleRel = NULL;
    origExecutionScheduleSet = NULL;
    currExecutionScheduleSet = NULL;
    blocks.push_back(block);
    schedule = sched;
  }

  LCNode(SmallVector<int> &sched, BasicBlock* block,
       ScalarEvolution& SE, LoopInfo& LI) :
       LCNodeBase(), name("Stmt"), Kind(LCNode::NodeKind::Statement),
       Dims(isl_aff_list_lt) {
    closedToForward= false;
    constraintsProcessed = false;
    domConstraints.first = nullptr;
    domConstraints.second = NULL;
    outerLoop = NULL;
    constraintSet=NULL;
    initialIterationSpace=NULL;
    iterationSpace = NULL;
    origExecutionScheduleRel = NULL;
    currExecutionScheduleRel = NULL;
    origExecutionScheduleSet = NULL;
    currExecutionScheduleSet = NULL;
    blocks.push_back(block);
    schedule = sched;
  }

  ~LCNode(){}

  bool operator<(LCNode &other){
    int idx = 0;
    while(idx < executionSchedule.size() && idx < other.executionSchedule.size()){
      if(executionSchedule[idx] < other.executionSchedule[idx]){
        return true;
      }
      if(other.executionSchedule[idx] < executionSchedule[idx]){
        return false;
      }
      idx++;
    }
    return false;
  }

  void constructInitialIterationSpace(){

    if(initialIterationSpace != NULL){
      isl_set_free(initialIterationSpace);
      initialIterationSpace = NULL;
    }
  LLVM_DEBUG(
    dbgs() << "======= constructInitialIterationSpace ======\n";
    dbgs() << "Sdom: " <<  
          ((domConstraints.second != NULL) ? 
          isl_set_to_str(domConstraints.second) : "")
          << "\n";
    dbgs() << "ControlFlow: \n";
    for( auto p : controlFlowConstraints ){
      dbgs() << "set: " << isl_set_to_str(p.second) << "\n";
    }
    dbgs() << "phi: \n";
    for( auto p : phiConstraints ){
      dbgs() << "set: " << isl_set_to_str(p.second) << "\n";
    }
  );

    // each phi node constraint needs to be intersected with 
    // its corresponding control flow constraint
    assert( controlFlowConstraints.size() >0 );
    isl_ctx *lctx = isl_set_get_ctx(controlFlowConstraints.begin()->second);
    isl_set_list* phiWithCF = isl_set_list_alloc(lctx,
                         controlFlowConstraints.size() + phiConstraints.size());

    // if there is at least one phi Constraint -- that is the space 
    // we want to match as it is the largest
    isl_set* spaceToMatch = NULL;
    if(phiConstraints.size() > 0){
      spaceToMatch = phiConstraints.begin()->second;
    }else{
      // we have to look through all of the control flow constraints
      // and pick the one with the smallest arity
      for( auto cfPair : controlFlowConstraints ){
        if(spaceToMatch == NULL){
          spaceToMatch = cfPair.second;
          continue;
        }
        if(isl_set_dim(cfPair.second,isl_dim_set) < 
           isl_set_dim(spaceToMatch,isl_dim_set)){
          spaceToMatch = cfPair.second;
        }
      }
    }

    for( auto cfPair : controlFlowConstraints ){
      if( auto search = phiConstraints.find(cfPair.first);
               search != phiConstraints.end()){
        // control flow set may need to shrink (exiting) or grow (entering)
        isl_set* set1 = isl_set_copy(search->second);
        set1 = matchSpaceByShrinking(set1,spaceToMatch);
        set1 = matchSpaceByGrowingSS(set1,spaceToMatch);
        // phi set should already match
        isl_set* set2 = isl_set_copy(cfPair.second);
        set2 = matchSpaceByShrinking(set2,spaceToMatch);
        set2 = matchSpaceByGrowingSS(set2,spaceToMatch);
        isl_set* pwc = isl_set_intersect(set1,set2);
        phiWithCF = isl_set_list_add(phiWithCF,pwc);
      }else{
        isl_set* set2 = isl_set_copy(cfPair.second);
        set2 = matchSpaceByShrinking(set2,spaceToMatch);
        set2 = matchSpaceByGrowingSS(set2,spaceToMatch);
        phiWithCF = isl_set_list_add(phiWithCF,set2);
      }
    }
    // Some of the phi nodes may not yet have corresponding
    //controlFlowConstraints
    for( auto pPair : phiConstraints ){
      if( auto search = controlFlowConstraints.find(pPair.first);
                              search == controlFlowConstraints.end()){
        phiWithCF = isl_set_list_add(phiWithCF,isl_set_copy(pPair.second));
      }
    }

    initialIterationSpace = isl_set_list_union(phiWithCF);

    if(initialIterationSpace == NULL){
      initialIterationSpace = isl_set_copy(domConstraints.second);
    }

    if(domConstraints.second != NULL){
      isl_set* set1 = isl_set_copy(domConstraints.second);
      set1 = matchSpaceByGrowingSS(set1,initialIterationSpace);
      initialIterationSpace = isl_set_intersect(set1,
                                           initialIterationSpace);
    }

    initialIterationSpace = isl_set_coalesce(initialIterationSpace);

    arity = isl_set_dim(initialIterationSpace,isl_dim_set);

    LLVM_DEBUG(dbgs() <<"Is: "<<isl_set_to_str(initialIterationSpace) << "\n"
                      << "=============================================\n");
  }

  // It seems odd that we allow the LOOP elements to not match, but 
  // The loops themselves should not determine execution schedule
  // unless there has been a fusion. In that case, we really consider
  // the two to be one that we can't mess with. So, this comparision
  // ignores the loop components.
  int schedulePrefixMatch(LCNode& other){
    int idx = 0;
    for(;idx<other.executionSchedule.size() &&
        idx<executionSchedule.size();idx++){
      // a prefix match should not require that every element matches
      // just the constants. 
      if(executionSchedule[idx].tag == ScheduleElement::LOOP &&
         other.executionSchedule[idx].tag == ScheduleElement::LOOP){
        continue;
      }
      if(executionSchedule[idx] !=
             other.executionSchedule[idx]){
              return idx;
      }
    }
    return idx;
  }


  SmallVector<std::string*>& collectIDs(SmallVector<std::string*> &ids){
    for( int i = 1; i < executionSchedule.size(); i+=2){
      Value& initial = initialIVValues.find(executionSchedule[i].loop)->second;
      Value& finalv = finalIVValues.find(executionSchedule[i].loop)->second;
      collectIDs(initial,ids);
      collectIDs(finalv,ids);
    }
    return ids;
  }

  SmallVector<std::string*>& collectIDs(Value &val,SmallVector<std::string*> &ids){
    if(ZExtInst* ZEI = dyn_cast<ZExtInst>(&val)){
      return collectIDs(*ZEI->getOperand(0),ids);
    }
    if(BinaryOperator* BO = dyn_cast<BinaryOperator>(&val)){
      collectIDs(*BO->getOperand(0),ids);
      collectIDs(*BO->getOperand(1),ids);
      return ids;
    }
    if(LoadInst* LI = dyn_cast<LoadInst>(&val)){
      return collectIDs(*LI->getPointerOperand(),ids);
    }
    if(Argument* ARG = dyn_cast<Argument>(&val)){
      if(ARG->hasName()){
        std::string* name = new std::string(ARG->getName());
        ids.push_back(name);
      }
    }
    return ids;
  }

  bool addOutgoingEdge(LCEdge &E) { return addEdge(E); }
  bool addIncomingEdge(LCEdge &E) { return IncomingEdges.insert(&E); }

  bool isEqualTo(LCNode const& N) const{
    if(Kind == NodeKind::Statement){
      return (this == &N);
    }
    if(N.Kind == NodeKind::Data && Kind == NodeKind::Data && N.name == name){
      return true;
    }
    return false;
  }

  LCNode &operator=(const LCNode &N) {
    DGNode::operator=(N);
    Kind = N.Kind;
    return *this;
  }

  LCNode &operator=(LCNode &&N) {
    DGNode::operator=(std::move(N));
    Kind = N.Kind;
    return *this;
  }

  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
  static bool classof(const LCNode *N) {
    return N->getKind() == NodeKind::Default;
  }

  void dump() const;
  NodeKind getKind() const { return Kind; }


  void saveDep(LCEdge* re, LCEdge* we, DepKind kind, isl_map* dep){
    if(!isl_map_is_empty(isl_map_copy(dep))){
      E1.push_back(re);
      E2.push_back(we);
      T.push_back(kind);
      Dep.push_back(dep);
      char* dep_str = isl_map_to_str(dep);
      LLVM_DEBUG(
        switch (kind) {
          case DepKind::WAR:
            dbgs() << "WAR: " << dep_str << "\n";
            break;
          case DepKind::RAW:
            dbgs() << "RAW: " << dep_str << "\n";
            break;
          case DepKind::WAW:
            dbgs() << "WAW: " << dep_str << "\n";
            break;
          case DepKind::RAR:
            dbgs() << "RAR: " << dep_str << "\n";
            break;
          default:
            errs() << "Error not matching type of dependencykind \n";
        }
      );
      free(dep_str);
    } 
  }

  SmallVector<int> findSecondWritesinWAWs(LCEdge* wEdge){
    SmallVector<int> retvals;
    int idx = 0;
    for(idx=0;idx<E2.size();idx++){
      if(E2[idx] == wEdge){
        if(T[idx] == DepKind::WAW){
          retvals.push_back(idx);
        }
      }
    }
    return retvals;
  }

  SmallVector<int> findFirstWritesinWAWs(LCEdge* wEdge){
    SmallVector<int> retvals;
    int idx = 0;
    for(idx=0;idx<E1.size();idx++){
      if(E1[idx] == wEdge){
        if(T[idx] == DepKind::WAW){
          retvals.push_back(idx);
        }
      }
    }
    return retvals;
  }

  SmallVector<int> findWritesinWARs(LCEdge* wEdge){
    SmallVector<int> retvals;
    int idx = 0;
    for(idx=0;idx<E2.size();idx++){
      if(E2[idx] == wEdge){
        if(T[idx] == DepKind::WAR){
          retvals.push_back(idx);
        }
      }
    }
    return retvals;
  }

  SmallVector<int> findReadsinWARs(LCEdge* rEdge){
    SmallVector<int> retvals;
    int idx = 0;
    for(idx=0;idx<E1.size();idx++){
      if(E1[idx] == rEdge){
        if(T[idx] == DepKind::WAR){
          retvals.push_back(idx);
        }
      }
    }
    return retvals;
  }

  SmallVector<int> findWritesinRAWs(LCEdge* wEdge){
    SmallVector<int> retvals;
    int idx = 0;
    for(idx=0;idx<E1.size();idx++){
      if(E1[idx] == wEdge){
        if(T[idx] == DepKind::RAW){
          retvals.push_back(idx);
        }
      }
    }
    return retvals;
  }

  SmallVector<int> findReadsinRAWs(LCEdge* rEdge){
    SmallVector<int> retvals;
    int idx = 0;
    for(idx=0;idx<E2.size();idx++){
      if(E2[idx] == rEdge){
        if(T[idx] == DepKind::RAW){
          retvals.push_back(idx);
        }
      }
    }
    return retvals;
  }
  LCEdge* getBeforeEdgeByIndex(int idx){
    return E1[idx];
  }
  LCEdge* getAfterEdgeByIndex(int idx){
    return E2[idx];
  }

  void applyXform(isl_map* xform){

    currExecutionScheduleRel = isl_map_set_tuple_name(
                                currExecutionScheduleRel,
                                isl_dim_out, 
                                isl_map_get_tuple_name(
                                                  currExecutionScheduleRel,
                                                  isl_dim_in));

    currExecutionScheduleRel = isl_map_apply_range(
                                  currExecutionScheduleRel,
                                  isl_map_copy(xform));

    currExecutionScheduleSet = isl_set_apply( 
                                  isl_set_copy(iterationSpace),
                                  isl_map_copy(currExecutionScheduleRel));
    
    currExecutionScheduleSet = isl_set_set_tuple_name(
                                  currExecutionScheduleSet,
                                  isl_set_get_tuple_name(iterationSpace));

    Xforms.push_back(xform);

    return;
  }

  bool valid = true;
  SetVector<LCEdge*> IncomingEdges;
  NodeKind Kind = NodeKind::Default;

  SmallVector<BasicBlock*> blocks;
  SmallVector<int> schedule;
  SmallVector<ScheduleElement> executionSchedule;
  std::string name;
  std::map<const Loop*,Value&> initialIVValues;
  std::map<const Loop*,Value&> finalIVValues;
  std::map<const Loop*,Value&> inductionVars;
  std::map<const Loop*,Value&> steps;

  Loop* outerLoop;
  // support polyhedral analysis
  //std::map<Value*,isl_set*> initialIterationSpaces;
  isl_set *constraintSet;
  isl_set *initialIterationSpace;
  isl_set *iterationSpace;
  isl_map *origExecutionScheduleRel;
  isl_map *currExecutionScheduleRel;
  isl_set *origExecutionScheduleSet;
  isl_set *currExecutionScheduleSet;
  SmallVector<isl_map*> Xforms;
  std::map<BasicBlock*,isl_set*> controlFlowConstraints;
  std::map<BasicBlock*,isl_set*> phiConstraints;
  std::pair<BasicBlock*,isl_set*> domConstraints;
  bool constraintsProcessed;
  bool closedToForward;
  int arity;

  // All of this is to keep track of existentials
  SmallVector<Loop *> loops;
  SmallVector<int > mapToSchedule;
  SmallVector<int > mapToPos;
  SmallVector<Value *> auxInitialIVValues;
  SmallVector<Value *> auxIVValues;
  SmallVector<Value *> auxStepIVValues;

  // Only Data Nodes need the following
  // TODO: time to separate statement nodes and data nodes.
  SmallVector<LCEdge*> E1;
  SmallVector<LCEdge*> E2;
  SmallVector<DepKind> T;
  SmallVector<isl_map*> Dep;
  Value* value;
  std::set<isl_aff_list*,decltype(isl_aff_list_lt)*> Dims;

};


class LCEdge : public LCEdgeBase {
public:
  enum class EdgeKind {
    Read,   
    Write   
  };

  //LCEdge(){};
  LCEdge(const LCEdge &) = delete;
  LCEdge(LCNode &Src, LCNode &N, EdgeKind Kind, Value& Val ) :
         LCEdgeBase(N), SourceNode(Src), Kind(Kind), Val(Val) {
          AccessMap = NULL;
          Multipliers = NULL;
         }
  LCEdge(LCEdge &&E) : LCEdgeBase(std::move(E)), SourceNode(E.SourceNode), 
                                            Kind(E.getKind()), Val(E.Val) {
    AccessMap = NULL;
    Multipliers = NULL;
  }
  ~LCEdge(){}

  LCEdge &operator=(const LCEdge &E) {
    LCEdgeBase::operator=(E);
    Kind = E.Kind;
    return *this;
  }

  LCEdge &operator=(LCEdge &&E) {
    LCEdgeBase::operator=(std::move(E));
    Kind = E.Kind;
    return *this;
  }

  EdgeKind getKind() const { return Kind; }
  LCNode* getNodePtr(){ return &TargetNode;}
  void dump() const;

  LCNode& SourceNode;
  EdgeKind Kind;
  Value& Val;
  SmallVector<isl_aff_list*>* Multipliers;
  SmallVector<isl_mat*> Multiplier_mat;
  isl_basic_map* AccessMap;
};

/// Encapsulate some common data and functionality needed for different
/// variations of data dependence graphs.
template <typename NodeType> class LoopChainGraphInfo {
public:

  LoopChainGraphInfo() = delete;
  LoopChainGraphInfo(const LoopChainGraphInfo &G) = delete;
  LoopChainGraphInfo(const std::string name): Name(name){}
  virtual ~LoopChainGraphInfo() = default;

  /// Return the label that is used to name this graph.
  StringRef getName() const { return Name; }

protected:
  // Name of the graph.
  std::string Name;

};

using LCInfo = LoopChainGraphInfo<LCNode>;

class LoopChainGraph final : public LCBase, public LCInfo {

public:
  using NodeType = LCNode;
  using EdgeType = LCEdge;

  LoopChainGraph() = delete;
  
  LoopChainGraph( Function &F, LoopInfo &LI, ScalarEvolution &SE, isl_ctx *ctx,
                 std::map<std::string,LCNode*> &NamedBlocks,
                 std::map<Value*,std::tuple<int,int,int>> &ParamConstraints):
          LoopChainGraphInfo(F.getName().str()), F(F), LI(LI), SE(SE), ctx(ctx),
          NamedBlocks(NamedBlocks), ParamConstraints(ParamConstraints){
    paramSpace = NULL;
    schedule = NULL;
  }    

  ~LoopChainGraph(){}


  const DirectedGraph::NodeListTy &getNodes() const { return Nodes; }
  void dump() const;


  /// Add the given node \p N to the graph.
  bool addNode(LCNode &N);

  // useful passes through the chain
  int performPtToPtFusion();
  bool alignAllIterationSpaces();
  int tileAllLegal();

  // utilities for analysis
  void getDependenceInfo();
  SmallVector<int> getFusionOptions(int anchor, int N);
  isl_map* getDEPRel(isl_map* a1, isl_map* lexico, LCEdge* ae2);
  isl_map* getDEPRel(LCEdge* ae1,  LCEdge* ae2,
                   isl_map* testTransform1, isl_map* testTranform2);
  bool testXformLegal(LCNode* targetNode, isl_map* transform);
  void consolidateLoopNests();

  // Transformations
  void moveAfter(int anchor, int N);
  isl_ctx *get_context(){return ctx;}
  void padOutArityToMatch(isl_map** m1, isl_map** m2);
  void padOutArityToMatch(isl_basic_map** m1, isl_basic_map** m2);


  void createSchedule();
  std::string scheduleToString();


  Function &F;
  LoopInfo &LI;
  ScalarEvolution &SE;
  SmallVector<LCNode*>  StatementNodes;
  SmallVector<LCNode*>  LoopNestNodes;
  isl_ctx *ctx;
  isl_space *paramSpace;
  isl_schedule* schedule;
  bool valid = true;
  SmallVector<isl_ast_node*> asts;

  std::map<Value*,std::string> NamedCstValues;
  std::map<std::string,LCNode*> &NamedBlocks;
  std::map<Value*,std::tuple<int,int,int>> &ParamConstraints;
  int startIdx=0;
  int endIdx=0;
  std::vector<std::vector<BasicBlock*>> ExcludedBlocks;
  isl_basic_set *Given;

};

raw_ostream &operator<<(raw_ostream &OS, const LCNode &N);
raw_ostream &operator<<(raw_ostream &OS, const LCNode::NodeKind K);
raw_ostream &operator<<(raw_ostream &OS, const LCEdge &E);
raw_ostream &operator<<(raw_ostream &OS, const LCEdge::EdgeKind K);
raw_ostream &operator<<(raw_ostream &OS, const LoopChainGraph &G);

class LoopChainPass : public PassInfoMixin<LoopChainPass> {
public:
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
  bool runOnFunction(Function &F, FunctionAnalysisManager &AM);
};

class AffineBuilder {
public:
  AffineBuilder(FunctionAnalysisManager &AM,DominatorTree &DT, LoopInfo &LI, std::map<Value*,
      std::string> &NamedIdxValues,
      GlobalModRefInfoCollection &GMRC,
      std::map<Value*,std::string> &NamedConstants,
      std::map<Value*,std::string> &NamedSpaces,
      std::map<Value*, LoadInst*,bool (*)(llvm::Value*, llvm::Value*)> &PtrOps,
      isl_space* ParamSpace ) :
        AM(AM), DT(DT),LI(LI),NamedIdxValues(NamedIdxValues), GMRC(GMRC),
        NamedConstants(NamedConstants), NamedSpaces(NamedSpaces),
        PtrOps(PtrOps), ParamSpace(ParamSpace) {

  }

  affParts* valueToAff( Value& val, isl_set* set, bool &error);
  affParts* valueToAff( Value& val, isl_space* space,
                        isl_local_space* ls, bool &error);
  isl_set* conditionToConstraints(Value* cond, isl_set* set);
  isl_set* conditionToConstraintSet(Value* cond, isl_set* set);
  isl_set* indexValueToSet( isl_space* space, PHINode* phi, Value* val);
  isl_set* affPartsToConstraints(affParts *op0Parts, affParts *op1Parts,
                                  CmpInst::Predicate predicate);
  void setVerbose(bool v){
    verbose = v;
  }
  isl_aff* prepAffForMulList(isl_aff* orig);

private:

  bool isaLeaf(Value* val);
  bool rollupBranch(Value* V,isl_set* set);
  isl_set* processCompare(Value* op0,Value*op1, CmpInst::Predicate pred);
  isl_set* processLogical(Value* op0, Value* op1,BinaryOperator *BO,
                          isl_set *inputSet);
  SmallVector<std::pair<affParts*,isl_set*>> processPhi(
    PHINode *PHI, int C, isl_set *set);
  void processUser(Value* V, int C);

  affParts* getZeroAff(isl_set* set);
  affParts* getOneAff(isl_set* set);
  affParts* multAffParts(affParts* op0, affParts* op1,
                       isl_space* space, isl_local_space* ls);

  affParts* addAffParts(affParts* op0, affParts* op1,
                       isl_space* space, isl_local_space* ls,
                       bool sub = false);
  affParts* subtractAffParts(affParts* op0, affParts* op1,
                       isl_space* space, isl_local_space* ls);
  isl_set* compareToConstraints(Value* comp, isl_set* set);
  SmallVector<isl_set*> phiNodeToConstraints(PHINode* phi,
                                               isl_set* inputSet,
                                               affParts* opParts = nullptr,
                                               CmpInst::Predicate predicate =
                                                 CmpInst::Predicate::ICMP_NE,
                                               bool isLHS = true);
  isl_set* intersectSets(const SmallVector<isl_set*>& sets);
  isl_set* unionSets(const SmallVector<isl_set*>& sets);
  Value* replaceArgumentWithParam(Value* val);

  FunctionAnalysisManager &AM;
  DominatorTree &DT;
  LoopInfo &LI;
  isl_space* ParamSpace;
  std::map<Value*,std::string> &NamedIdxValues;
  GlobalModRefInfoCollection &GMRC;
  std::map<Value*,std::string> &NamedConstants;
  std::map<Value*,std::string> &NamedSpaces;
  std::map<Value*, LoadInst*,bool (*)(llvm::Value*, llvm::Value*)> &PtrOps;
  std::map<Value*,affParts*> VisitedPhis;

  SmallVector<std::tuple<Value*,int>> WorkStack;
  std::map<Value*,SmallVector<std::pair<affParts*,isl_set*>>> OperandResults;

  bool verbose = false;

};

class AffineCollector {
public:
  AffineCollector(FunctionAnalysisManager &AM,
   std::map<Value*,std::string> &NamedIdxValues,
   std::map<Value*,std::string> &NamedConstants,
   DominatorTree &DT, LoopInfo &LI) : AM(AM),NamedIdxValues(NamedIdxValues),
            NamedConstants(NamedConstants), DT(DT),LI(LI), PtrOps(Value_lt) {
  
    NameCounter = 0;
  }
  ~AffineCollector(){}

  void dump();

  bool collect(Value* value, bool strict = true);
  bool collectPointers(Value* start, bool strict);

  std::map<Value*,std::string>& getNamedConstants() {
    return NamedConstants;
  }

  GlobalModRefInfoCollection* getGMRC(){
    return &GMRC;
  }

  std::map<Value*, LoadInst*,bool (*)(llvm::Value*, llvm::Value*)> getPtrOps() const {
    return PtrOps;
  }

  std::set<LoadInst*>& getElimLoads() {
    return ElimLoads;
  }

  static bool Value_lt(Value* V1, Value* V2) {
    if (V1 == V2) {
      return false;
    }
    if (V1->getValueID() < V2->getValueID()) {
      return true;
    }
    if (V1->getValueID() > V2->getValueID()) {
      return false;
    }

    if (llvm::isa<Argument>(V1) || llvm::isa<AllocaInst>(V1)) {
      return V1 < V2;
    }

    if (User* U1 = dyn_cast<User>(V1)) {
      User* U2 = dyn_cast<User>(V2);
      if (U1->getNumOperands() < U2->getNumOperands()) {
        return true;
      }
      if (U1->getNumOperands() > U2->getNumOperands()) {
        return false;
      }

      for (unsigned I = 0; I < U1->getNumOperands(); I++) {
        std::string Op1Str = valToStr(U1->getOperand(I));
        std::string Op2Str = valToStr(U2->getOperand(I));
        if (Op1Str < Op2Str) {
          return true;
        }
        if (Op1Str > Op2Str) {
          return false;
        }
      }
    }

    return false;
  }

  std::map<Value*,std::string> &NamedConstants;
  std::string nextName(const std::string& prefix = "cst");
  void markDeleted(BasicBlock *BB);
  void removeDeleted();

protected:
  bool process(Value* V, bool strict);
  bool process(Argument* AI, bool strict);
  bool process(CastInst* CI, bool strict);
  bool process(ConstantInt* CI, bool strict);
  bool process(LoadInst* LI, bool strict);
  bool process(BinaryOperator* BO, bool strict);
  bool process(PHINode* PHI, bool strict);
  bool process(BranchInst* BR, bool strict);
  bool process(CmpInst* CI, bool strict);

  Value* forward(Argument* Arg);
  Value* forwardPointer(Value* ptr);
  bool eliminate(Value* val,LoadInst *LD);
  bool isConstantLoad(LoadInst *LI);
  void addConstant(Value *V, const std::string& name);

private:
  bool replaceInstWithStore(Value* I, LoadInst* L);  

  FunctionAnalysisManager &AM;
  DominatorTree &DT;
  LoopInfo &LI;
  std::map<Value*,std::string> &NamedIdxValues;
  unsigned NameCounter;
  GlobalModRefInfoCollection GMRC;
  SmallVector<Value*> WorkStack;
  SmallVector<Value*> PointerWorkStack;
  std::set<Value*> Processed;
  std::map<Value*, LoadInst*, decltype(Value_lt)*> PtrOps;
  std::set<Value*> BranchConditions;
  std::set<LoadInst*> ElimLoads;
  std::map<Value*, BasicBlock*> ConstantBlocks;
  std::map<Value*, BasicBlock*> DeletedConstants;
};

class LCBuilder{
public:
  LCBuilder( FunctionAnalysisManager &AM, Function &F, LoopInfo &LI,
             ScalarEvolution &SE, 
             PostDominatorTree &PDT, DependenceInfo &DI, DominatorTree &DT,
             DomTreeUpdater &DTU): 
             AM(AM), F(F), LI(LI), SE(SE), PDT(PDT), DI(DI), DT(DT), DTU(DTU){
              idcounter = 0;
              BlockCounter = 0;
              AffCollector = new AffineCollector(AM,NamedIdxValues,NamedConstants,DT,LI);
              AffBuilder = nullptr;                
              ctx = isl_ctx_alloc();
            }    

  virtual ~LCBuilder() {
    delete AffCollector;
  }

  int createChains();
  SmallVector<LoopChainGraph*> getChains(){
    return Chains;
  }
  static bool sortbysec(const std::pair<int,int> &a,
                        const std::pair<int,int> &b) {
    return (a.second < b.second);
  }



  void createInitialChains();
  bool calculateAndForwardConstraints(int idx,
                                 SmallVector<std::pair<int,int>> &returnsToTake,
                                 bool backedge=false);
  void forwardConstraintSet(BasicBlock* srcBlock, LCNode* destNode,
                                           isl_set *forwardSet,bool backedge);
  void forwardConstraints(LCNode *lc,isl_set *set,bool backedge);
  std::vector<std::vector<BasicBlock*>> findLegalChainBreaksNew();
  SmallVector<std::pair<int,int>> findLegalChainBreaks(SmallVector<int>
                                                             &legalChainBreaks);

  void reduceIterationSpace(LCNode* node);
  void buildParamSpace();
  SmallVector<std::pair<int,int>>  collectInitialIterationSpaces(
                      std::vector<std::vector<BasicBlock*>>& legalDeleteBlocks);

  void filterPotentialCstValues(std::map<Value*,std::string> &PCstValues);

  LCNode* createStatementNode(SmallVector<int>& sched, BasicBlock* BB);
  LCNode* createDataNode(Value& I,bool isReg=false);
  LCEdge* createReadEdge(LCNode &s, LCNode& n,Instruction& I);
  LCEdge* createWriteEdge(LCNode &s, LCNode& n,Instruction& I);

  void stageReadNode(int idx, LCNode* node, Value* ptr, Instruction& I,
             SmallVector<SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>>>&
             stagedReads);
  void stageWriteNode(int idx, LCNode* node, Value* ptr, Instruction& I,
             SmallVector<SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>>>&
             stagedWrites);

  bool hasIllegalInstruction(BasicBlock* bb);
  bool isValidIntrinsic(Instruction* inst);
  //bool isFlangIntrinsic(Instruction* inst);
  void handleFlangIntrinsic(int idx ,LCNode* node, CallInst *call,
              SmallVector<SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>>>
              &stagedReads,
              SmallVector<SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>>>
              &stagedWrites);
  void handleFlangIntrinsic(int idx, LCNode* node, CallInst* call,
              SmallVector<SmallVector<std::pair<LCNode*,LCEdge*>>>& stagedReads,
              SmallVector<SmallVector<LCEdge*>>& stagedWriteEdges);

  void addRegisterReadsWrites(LCNode* node, BasicBlock* bb, 
           Instruction &I,Loop* bb_loop,
           SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>> &stagedReads,
           SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>> &stagedWrites);

  void createExecutionSchedule(LCNode &n);
  void createAccessMap(LCEdge*, LCNode* node);
  void collectInductionVariables();
  // Functions used to cleanup and align polyhedral representation
  void determineDataspaceDims(LoopChainGraph* lc, LCNode* node);
  void cleanupAccessMaps(LCNode* node);
  void prepAccessMap(LCNode *node,LCEdge *edge);
  void orderAccessMap(LCEdge *edge);
  bool combineDuplicateMultipliers( LCEdge* edge, isl_set* I );
  bool promoteMultipliers( LCEdge* edge, isl_set* I );
  bool demoteMultipliers(LCEdge* edge, isl_set* I );
  bool swapMultipliers(LCEdge *edge, isl_set *I);
  void addDataspaceDims(LoopChainGraph* lc, LCNode* node, LCEdge* edge,
                        isl_set* I);
  isl_set* projectAllBut(isl_set* set, int pos);
    //void correctIterationSpace(LCNode* node);
    //void finalizePreferredIterationOrder(LCNode* node);
    //void correctAccessMaps(LCNode* node);
    //void correctAccessMap(LCNode* node, LCEdge* edge);
    //void collectConstantsForBounds();
    void correctSpacesAndMaps(LoopChainGraph* lc, LCNode* node);
    void correctMapOut(LCNode* dnode, LCEdge* edge);
    void correctIterationSpaces(LoopChainGraph* lc,LCNode* snode);

    static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
      if (L->getLoopLatch() == nullptr){
        return nullptr;
      }
      if( L->getLoopPredecessor() == nullptr){
        return nullptr;
      }
      for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
        PHINode *PhiVar = cast<PHINode>(I);
        Type *PhiTy = PhiVar->getType();
        if (!PhiTy->isIntegerTy()){
          LLVM_DEBUG(dbgs() << "PhiVar has wrong type (isFloatingPointTy) "
                            << *PhiVar << "\n");
          continue;
        }
        const SCEVAddRecExpr *AddRec =
            dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
        if (!AddRec || !AddRec->isAffine()){
          continue;
        }
        const SCEV *Step = AddRec->getStepRecurrence(*SE);
        if (!isa<SCEVConstant>(Step)){
          continue;
        }
        // Found the induction variable.
        // FIXME: Handle loops with more than one induction variable. Note that,
        // currently, legality makes sure we have only one induction variable.
        if(PhiVar){
          auto bounds = Loop::LoopBounds::getBounds(*L,*PhiVar,*SE);
          if(bounds) return PhiVar;
        }
      }
      return nullptr;
    }

  int checkStepValue(const Value &v);
  Value* GEPtoSpace(Value* val);
  bool blockUsesValue(BasicBlock* block, SmallVector<Value *> &values);


  std::optional<std::pair<BasicBlock*,LCNode*>>
                                    findBlockInStagedNodes(BasicBlock* toFind){

    for(int idx=0; idx<stagedNodes.size(); idx++){
      BasicBlock* bb = stagedNodes[idx].first;
      if(bb == toFind){
        return stagedNodes[idx];
      }
    }
    return {};
  }

  bool isGuarded_tsEQ1(BasicBlock *bb);


  int idcounter;
  LoopInfo &LI;
  ScalarEvolution &SE;
  DependenceInfo &DI;
  PostDominatorTree &PDT;
  DominatorTree &DT;
  DomTreeUpdater &DTU;

  std::vector<std::vector<BasicBlock*>> deleteBlocks;
  SmallVector<LoopChainGraph*> Chains;
  SmallVector<BasicBlock*> Successors;
  SmallVector<std::vector<BasicBlock*>> zeroLvl;
  SmallVector<std::pair<BasicBlock*,LCNode*>> stagedNodes;
  std::map<Value*,isl_aff*> pendingConstraints;
  BasicBlock* CurrPreHeader = nullptr;
  SmallVector<Value*> CurrPHINodes;
  AffineBuilder* AffBuilder;
  GlobalModRefInfoCollection* GMRCp;
  std::map<Value*, LoadInst*,bool (*)(llvm::Value*, llvm::Value*)> PtrOps;
  isl_basic_set *Given = NULL;

  public:
  FunctionAnalysisManager &AM;
  Function &F;
  AffineCollector *AffCollector;
  isl_ctx *ctx;
  isl_space *paramSpace;
  //LoopChainGraph* currLC;
  LoopChainGraph* commonLCInfo;
  std::map<LCNode*,SmallVector<int>> ICorrections;
  std::map<Value*,std::string> NamedConstants;
  std::map<Value*,std::string> NamedIdxValues;
  std::map<Value*,std::string> NamedSpaces;
  std::map<Value*,std::string> NamedRegs;
  std::map<std::string,LCNode*> NamedBlocks;
  std::map<std::string,isl_aff_list*> SpareConstants;
  int BlockCounter;
  std::map<Value*,std::tuple<int,int,int>> ParamConstraints;
};


// Base class for recipe steps
class LCRecipeStep{
  public:
    enum LCRecipeStepKind {
      LK_Split,
      LK_Tile,
      LK_GDup,
      LK_Delete,
      LK_Guard,
      LK_Pad,
      LK_Identity
    };
  private:
    const LCRecipeStepKind Kind;
  public:
    LCRecipeStepKind getKind() const { return Kind;}
    LCRecipeStep* appendStep(LCRecipeStep* step){
      if(next == nullptr){
        next = step;
        return next;
      }
      return next->appendStep(step);
    }

    LCRecipeStep(LCRecipeStepKind K) : Kind(K){
      next=nullptr;
      result_loop=nullptr;
      source = nullptr;
    }
    virtual bool execute() = 0;
    isl_ast_node* ast;
    std::string name;
    LCRecipeStep* next;
    LCRecipeStep* source;
    // result will be saved here as well
    Loop* loop;
    Loop* result_loop;
};

raw_ostream &operator<<(raw_ostream &OS, const LCRecipeStep &S);

class LCBuilder;
class LCRecipeBuilder{

  public:
  enum class XFORM { FUSE, SPLIT, PAD, MOVE };
  LCRecipeBuilder(LCBuilder &LCB, LoopChainGraph* lc, ScalarEvolution& SE,
                  DominatorTree& DT, PostDominatorTree& PDT,
                  const DataLayout& DL,
                  LoopInfo& LI, DomTreeUpdater &DTU):
                  LCB(LCB), lc(lc), SE(SE),DT(DT),PDT(PDT),DL(DL),LI(LI),DTU(DTU){
    nameCntr = 0;
  }
              
  bool executeAllRecipes();
  bool generateInitialRecipe();
  bool generateNextRecipe(int r_idx);
  bool applyNextRecipe(int r_idx);

  std::pair<BranchInst*,bool> identifyTargetBranchForPromotion();
  void combineBranchesAndPlace(BranchInst *anchorBR, bool dir1,
                                             SmallVector<SmallVector<Instruction*,4>> &bll,
                                             SmallVector<SmallVector<int,4>> &sll,
                                             std::vector<Instruction*> &plist,
                                             bool negate);
  std::vector<Instruction*> collectPrecedingInstructions( Instruction *o_br);

  const SCEV* isl_ast_expr_to_SCEV(isl_ast_expr* expr,Value* newID,bool &fdiv);
  const SCEV* isl_ast_expr_to_SCEV(isl_ast_expr* expr,bool &fdiv){
    return isl_ast_expr_to_SCEV(expr,NULL,fdiv);
  }
  static const SCEV* isl_ast_expr_to_SCEV_this(LCRecipeBuilder* th,
                                              isl_ast_expr* expr,
                                              Loop* scope, Value* newID,bool &fdiv){
    th->setCurrentScope(scope);
    return th->isl_ast_expr_to_SCEV(expr,newID,fdiv);
  }

  bool relocateConstLoads();
  void removeAllSkippedBlocks();
  void setCurrentScope(Loop* scope){
    CurrentScope = scope;
  }
  std::string getNextName(){
    return "lcgv" + std::to_string(nameCntr++);
  }

  private:
  std::vector<std::pair<const SCEV*,bool>> stepsForEquivalentTypes(isl_ast_node* strt, isl_ast_node* goal);
  const SCEV *insertGlobalVarStoreAndLoadFromInst(Function *F, Instruction *Inst);
  isl_stat ast_nodelist_foreach(__isl_keep isl_ast_node_list *list, void *user);
  isl_stat ast_node_foreach_descendant_bottom_up(__isl_keep isl_ast_node *node,
                                                 void *user);

  LCBuilder &LCB;
  LoopChainGraph* lc;
  ScalarEvolution &SE;
  DominatorTree &DT;
  PostDominatorTree &PDT;
  const DataLayout &DL;
  LoopInfo &LI;
  DomTreeUpdater &DTU;
  Loop *CurrentScope;
  int nameCntr;

  std::vector<std::vector<LCRecipeStep*>*> recipes;

};
// The split step holds information to 
// split the iteration space of a loop into two or more partitions.
class LCRecipeSplit : public LCRecipeStep{

  public:
  LCRecipeSplit(): LCRecipeStep(LK_Split){
    guard = false;
    executed = false;
  }

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_Split;
  }

  bool guard;
  std::string name;
  std::vector<Partition*> partition;
  bool executed;

};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeSplit &S);

// Remove Loop
// This step is required during some of the more complex fusions
class LCRecipeDelete : public LCRecipeStep{

  public:
  LCRecipeDelete(): LCRecipeStep(LK_Delete){ }

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_Delete;
  }

};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeDelete &S);

// The tile class holds information required to
// tile a single loop. Tiling a multi-dimensional loop nest
// requires a series of tile objects.
class LCRecipeTile : public LCRecipeStep{
  public:
  LCRecipeTile(): LCRecipeStep(LK_Tile){ }
  const SCEV* getInnerSCEV(Value* newIV);

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_Tile;
  }

  const SCEV* getInnerLowerBound(Value* iv,  void* ast, Loop* scope, void* obj, bool &fdiv){
    isl_ast_node* forloop = (isl_ast_node*)ast;
    dbgs() << "Lower bound AST: " << isl_ast_expr_to_C_str(isl_ast_node_for_get_init(forloop)) << "\n";
    const SCEV* lb=LCRecipeBuilder::isl_ast_expr_to_SCEV_this(
                                         (LCRecipeBuilder*)obj,
                                         isl_ast_node_for_get_init(forloop),
                                         scope, iv, fdiv);

    return lb;
  }
  static const SCEV* getInnerLowerBound(void* th,Value* iv,void* ast,Loop* scope,void* obj, bool &fdiv){
    LCRecipeTile* tile = static_cast<LCRecipeTile*>(th);
    tile->CurrentScope = scope;
    return tile->getInnerLowerBound(iv,ast,scope,obj,fdiv);
  }

  const SCEV* getInnerUpperBound(Value* iv,  void* ast, Loop* scope, void* obj,bool &fdiv){
    isl_ast_node* forloop = (isl_ast_node*)ast;
    dbgs() << "Upper bound AST: " << isl_ast_expr_to_C_str(isl_ast_node_for_get_cond(forloop)) << "\n";
    const SCEV* ub = LCRecipeBuilder::isl_ast_expr_to_SCEV_this(
                                         (LCRecipeBuilder*)obj,
                                         isl_ast_node_for_get_cond(forloop),
                                         scope, iv, fdiv);
    return ub;
  }
  static const SCEV* getInnerUpperBound(void* th,Value* iv,void* ast, Loop* scope, void* obj, bool &fdiv){
    LCRecipeTile* tile = static_cast<LCRecipeTile*>(th);
    tile->CurrentScope = scope;
    return tile->getInnerUpperBound(iv,ast,scope,obj,fdiv);
  }

  LCRecipeTile* corresponding;
  std::vector<const SCEV*> lbs;
  std::vector<const SCEV*> ubs;
  std::vector<isl_ast_node*> outer;
  std::vector<isl_ast_node*> inner;
  Loop* CurrentScope;
};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeTile &S);

class LCRecipeGDup : public LCRecipeStep{
  public:
  LCRecipeGDup(): LCRecipeStep(LK_GDup){ }

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_GDup;
  }

  const SCEV* getInnerLowerBound(Value* iv,  void* ast,Loop *scope, void* obj, bool &fdiv){
    isl_ast_node* forloop = (isl_ast_node*)ast;
    const SCEV* lb=LCRecipeBuilder::isl_ast_expr_to_SCEV_this(
                                         (LCRecipeBuilder*)obj,
                                         isl_ast_node_for_get_init(forloop),
                                         scope, iv, fdiv);
    return lb;
  }
  static const SCEV* getInnerLowerBound(void* th,Value* iv,void* ast,Loop* scope,
  void* obj, bool &fdiv){
    LCRecipeGDup* gdup = static_cast<LCRecipeGDup*>(th);
    return gdup->getInnerLowerBound(iv,ast,scope,obj,fdiv);
  }

  const SCEV* getInnerUpperBound(Value* iv,  void* ast,Loop* scope, void* obj, bool &fdiv){
    isl_ast_node* forloop = (isl_ast_node*)ast;
    const SCEV* ub = LCRecipeBuilder::isl_ast_expr_to_SCEV_this(
                                         (LCRecipeBuilder*)obj,
                                         isl_ast_node_for_get_cond(forloop),
                                         scope, iv, fdiv);
    return ub;
  }
  static const SCEV* getInnerUpperBound(void* th,Value* iv,void* ast,Loop* scope,void* obj, bool &fdiv){
    LCRecipeGDup* gdup = static_cast<LCRecipeGDup*>(th);
    return gdup->getInnerUpperBound(iv,ast,scope,obj,fdiv);
  }
  std::vector<isl_ast_node*> inner;

};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeGDup &S);

class LCRecipeIdentity : public LCRecipeStep{
  public:
  LCRecipeIdentity(): LCRecipeStep(LK_Identity){ }

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_Identity;
  }

};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeIdentity &S);

class LCRecipePad : public LCRecipeStep{
  public:
  LCRecipePad(): LCRecipeStep(LK_Pad){ }

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_Pad;
  }

};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipePad &S);

class LCRecipeGuard : public LCRecipeStep{
  public:
  LCRecipeGuard(): LCRecipeStep(LK_Guard){ }

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_Guard;
  }

};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeGuard &S);



//===
// LoopChainGraphInfo Implementation
//===

//==
// GraphTraits specialization for the LC -- used for printing
//==
/// non-const versions of the graph trait specializations for LC
template <> struct GraphTraits<LCNode *> {
  using NodeRef = LCNode *;

  static LCNode *LCGetTargetNode(DGEdge<LCNode, LCEdge> *P) {
    return &P->getTargetNode();
  }

  // Provide a mapped iterator so that the GraphTrait-based implementations can
  // find the target nodes without having to explicitly go through the edges.
  using ChildIteratorType =
      mapped_iterator<LCNode::iterator, decltype(&LCGetTargetNode)>;
  using ChildEdgeIteratorType = LCNode::iterator;

  static NodeRef getEntryNode(NodeRef N) { return N; }
  static ChildIteratorType child_begin(NodeRef N) {
    return ChildIteratorType(N->begin(), &LCGetTargetNode);
  }
  static ChildIteratorType child_end(NodeRef N) {
    return ChildIteratorType(N->end(), &LCGetTargetNode);
  }

  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
    return N->begin();
  }
  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
};

template <> struct GraphTraits<LoopChainGraph *> : public GraphTraits<LCNode *>{
  using nodes_iterator = LoopChainGraph::iterator;
  static NodeRef getEntryNode(LoopChainGraph *DG) {
    return *DG->begin();
  }
  static nodes_iterator nodes_begin(LoopChainGraph *DG) {
    return DG->begin();
  }
  static nodes_iterator nodes_end(LoopChainGraph *DG) { return DG->end(); }
};

/// const versions of the graph trait specializations for LC
template <> struct GraphTraits<const LCNode *> {
  using NodeRef = const LCNode *;

  static const LCNode *LCGetTargetNode(const DGEdge<LCNode, LCEdge> *P) {
    return &P->getTargetNode();
  }

  // Provide a mapped iterator so that the GraphTrait-based implementations can
  // find the target nodes without having to explicitly go through the edges.
  using ChildIteratorType =
      mapped_iterator<LCNode::const_iterator, decltype(&LCGetTargetNode)>;
  using ChildEdgeIteratorType = LCNode::const_iterator;

  static NodeRef getEntryNode(NodeRef N) { return N; }
  static ChildIteratorType child_begin(NodeRef N) {
    return ChildIteratorType(N->begin(), &LCGetTargetNode);
  }
  static ChildIteratorType child_end(NodeRef N) {
    return ChildIteratorType(N->end(), &LCGetTargetNode);
  }

  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
    return N->begin();
  }
  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
};

template <> struct GraphTraits<const LoopChainGraph *>
    : public GraphTraits<const LCNode *> {
  using nodes_iterator = LoopChainGraph::const_iterator;
  static NodeRef getEntryNode(const LoopChainGraph *DG) {
    return *DG->begin();
  }
  static nodes_iterator nodes_begin(const LoopChainGraph *DG) {
    return DG->begin();
  }
  static nodes_iterator nodes_end(const LoopChainGraph *DG) {
    return DG->end();
  }
};

struct IVSearchVisitor : public InstVisitor<IVSearchVisitor> {
  IVSearchVisitor( LoopInfo &LI,
                   ScalarEvolution &SE,
                   std::map<Value*,std::string> &NamedIVs,
                   int& name_id) :LI(LI), SE(SE), NamedIVs(NamedIVs), name_id(name_id) {}

  void visitPHINode( PHINode &phi){
    BasicBlock *Incoming = nullptr, *Backedge = nullptr;
    if(Loop* loop = LI.getLoopFor(phi.getParent())){
      if(!loop->getIncomingAndBackEdge( Incoming, Backedge)){
        return;
      }
    }
    std::string name = "idx";
    if(phi.hasName()){
      name = phi.getName().str();
    }else{
      name += std::to_string( name_id );
      name_id++;
    }
    if(!SE.isSCEVable(phi.getType())){return;}
    const SCEV* sc = SE.getSCEV(&phi);
    if(!sc){return;}
    if(const SCEVAddRecExpr *dar = dyn_cast<SCEVAddRecExpr>(sc)){
      if(dar->isAffine()){
        int count = phi.getNumIncomingValues();
        if(count != 2){
          LLVM_DEBUG(dbgs() << "PHI has too many incoming: " << phi << "\n");
          return;
        } // supporting very specific patterns

        // TODO: Ensure that inc is 1 or -1
        NamedIVs.insert({(Value*)&phi,name});
        return;
      }
    }
    LLVM_DEBUG(dbgs() << "PHI not index var: " << phi << "\n");
    return;
  }

  int& name_id;
  LoopInfo& LI;
  ScalarEvolution& SE;
  std::map<Value*,std::string> &NamedIVs;
};

} // namespace llvm

#endif // LLVM_TRANSFORMS_SCALAR_LOOPCHAIN_H