#ifndef LLVM_TRANSFORMS_SCALAR_LOOPCHAIN_H
#define LLVM_TRANSFORMS_SCALAR_LOOPCHAIN_H

#include <limits>
#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/LoopChainOptReport.h"
#include "llvm/Analysis/LoopInductionAccesses.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/Casting.h"
#include "llvm/Transforms/Scalar/LoopChainOutline.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/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PassManager.h"


#define DEBUG_TYPE "loopchain"
#define DEBUG_LEVEL 0
#define LLVM_DEBUG_LVL(LVL, X) LLVM_DEBUG_WITH_LVL(LVL, DEBUG_LEVEL, X)
#define LLVM_DEBUG_WITH_LVL(LVL, D_LVL, X) if( D_LVL >= LVL) { LLVM_DEBUG(X); }

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);
  CallInst* findDominantCall(const SmallVector<CallInst*, 4>& Calls,
                             const DominatorTree& DT);
  bool isFlangIntrinsic(Instruction* inst);
  bool isMemoryIntrinsic(const Instruction *I);
  bool hasBackedge(const DominatorTree &DT, BranchInst *BC);
  bool hasBackedge(const LoopInfo &LI, PHINode* PHI);
  bool isConditional(BranchInst* BI);
  bool isl_ast_node_is_equiv(isl_ast_node *N1, isl_ast_node *N2);
  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);
  bool verifyFunc(Function *Func, const std::string& Loc = "",
                  bool PrintOnFail = false, bool AssertOnFail = true);

  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);
  
  PHINode *getInductionVariableLC_NOSCEV(Loop *L, ScalarEvolution *SE);
  PHINode *getInductionVariableLC(Loop *L, ScalarEvolution *SE);

  MDNode *setMetadata(BasicBlock *BB, const std::string& Data,
                      const std::string& Name = "");
  MDNode *setMetadata(Instruction *I, const std::string& Data,
                      const std::string& Name = "");
}


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;
    complementSet=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;
    complementSet=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;
    complementSet=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;
    complementSet=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();

  // 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, bool print = false){
    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);

      if (!print)
        return;

      char* dep_str = isl_map_to_str(dep);
      LLVM_DEBUG_LVL(0,
        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,int VIdx){

    Versions[VIdx].CurrExecutionScheduleRel = isl_map_set_tuple_name(
                                Versions[VIdx].CurrExecutionScheduleRel,
                                isl_dim_out, 
                                isl_map_get_tuple_name(
                                       Versions[VIdx].CurrExecutionScheduleRel,
                                                  isl_dim_in));

    Versions[VIdx].CurrExecutionScheduleRel = isl_map_apply_range(
                                  Versions[VIdx].CurrExecutionScheduleRel,
                                  isl_map_copy(xform));

    Versions[VIdx].CurrExecutionScheduleSet = isl_set_apply( 
                        isl_set_copy(Versions[VIdx].IterationSpace),
                        isl_map_copy(Versions[VIdx].CurrExecutionScheduleRel));
    
    Versions[VIdx].CurrExecutionScheduleSet = isl_set_set_tuple_name(
                         Versions[VIdx].CurrExecutionScheduleSet,
                         isl_set_get_tuple_name(Versions[VIdx].IterationSpace));


    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
  isl_set *constraintSet;
  isl_set *complementSet;
  isl_set *initialIterationSpace;
  isl_set *iterationSpace;
  isl_map *origExecutionScheduleRel;
  isl_map *currExecutionScheduleRel;
  isl_set *origExecutionScheduleSet;
  isl_set *currExecutionScheduleSet;
  std::map<BasicBlock*,isl_set*> controlFlowConstraints;
  std::map<BasicBlock*,isl_set*> phiConstraints;
  std::pair<BasicBlock*,isl_set*> domConstraints;
  bool constraintsProcessed;
  bool closedToForward;
  int arity = 0;

  // Support Versioning
  struct Version {
    isl_set *InitialIterationSpace;
    isl_set *IterationSpace;
    isl_map *OrigExecutionScheduleRel;
    isl_map *CurrExecutionScheduleRel;
    isl_set *OrigExecutionScheduleSet;
    isl_set *CurrExecutionScheduleSet;
    //SmallVector<isl_map*> Xforms;
  };
  Version Versions[2];

  // 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;

  // Keep track of the chosen alignment affs for each dim
  SmallVector<isl_aff*> AlignmentAffs;

};


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), EqualitySubs(isl_constraint_list_lt){
    paramSpace = NULL;
    schedule = NULL;
    VersionsInitialized = false;
    Given = nullptr;
    RequiredConstraints = nullptr;
  }    

  ~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, int V = -1);
  isl_map* getDEPRel(LCEdge* ae1,  LCEdge* ae2,
                   isl_map* testTransform1, isl_map* testTranform2,int V = -1);
  bool testXformLegal(LCNode* targetNode, isl_map* transform, int VIdx);
  bool tilingImpactful(LCNode *Node, isl_map *TileMap, int NTileTVs, int VIdx);
  void consolidateLoopNests();
  void chooseVersioningConstraints(SmallVector<isl_set*>VCs);
  SmallVector<LCNode*> getAlignmentOrdering(LCNode *AlignmentNode);

  // 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();
  void reduceEqualities(SmallVector<std::string> Spares);
  void applyExecutionConstraintSet();
  static bool isl_constraint_list_lt(isl_constraint_list *CL1, isl_constraint_list *CL2){
    if(isl_constraint_list_n_constraint(CL1) < 
       isl_constraint_list_n_constraint(CL2)){ return true;}
    if(isl_constraint_list_n_constraint(CL1) > 
       isl_constraint_list_n_constraint(CL2)){ return false;}
    // They have the same number of constraints
    if(isl_constraint_list_n_constraint(CL1) == 0){ return false;}
    // Check to see if they match
    isl_basic_set *BM1 = isl_basic_set_from_constraint(isl_constraint_list_get_constraint(CL1, 0));
    isl_basic_set *BM2 = isl_basic_set_from_constraint(isl_constraint_list_get_constraint(CL2, 0));
    for(unsigned Idx=1; Idx < isl_constraint_list_n_constraint((CL1));Idx++){
      BM1 = isl_basic_set_add_constraint(BM1, isl_constraint_list_get_constraint(CL1, Idx));
      BM2 = isl_basic_set_add_constraint(BM2, isl_constraint_list_get_constraint(CL2, Idx));
    }
    if(isl_basic_set_plain_is_equal(BM1, BM2)){ return false;}
    // This is where it gets arbitray
    // Decide which is "less than" the other
    return strcmp(isl_basic_set_to_str(BM1),isl_basic_set_to_str(BM1)) < 0;
  }


  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[2];

  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_set *ExecutionSpace;
  isl_basic_set *RequiredConstraints;
  isl_basic_set *Given;
  isl_set* ChosenVersioningConstraintSet;
  bool VersionsInitialized;
  std::map<isl_constraint_list*,std::string, decltype(isl_constraint_list_lt)*> EqualitySubs;
  std::string ErrorMessage;
};

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> {
  class LoopChainFindGuardPassVisitor
      : public InstVisitor<LoopChainFindGuardPassVisitor> {
    std::string Name;
    bool useCloned;
    
  public:
    LoopChainFindGuardPassVisitor(std::string Name, bool useCloned, bool success = false) 
      : Name(Name), useCloned(useCloned), success(success) {}  
    void visitCallInst(CallInst &CI){}
    bool success = false;
  };
  void writeModuleToFile(Module &M, StringRef BaseName);
public:
  LoopChainPass(LoopChainOutlineOptions Opts = {}) : OutlineOpts(Opts) {}
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
  bool runOnFunction(Function &F, FunctionAnalysisManager &AM);

private:
  LoopChainOutlineOptions OutlineOpts;
};

class AffineBuilder {
public:
  AffineBuilder(FunctionAnalysisManager &AM, Function &F, const DataLayout &DL,
      DominatorTree &DT, PostDominatorTree &PDT, LoopInfo &LI, std::map<Value*,
      std::string> &NamedIdxValues,std::map<Value*,isl_aff*> &AuxToIdxAffs,
      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), F(F), DL(DL), DT(DT),PDT(PDT),LI(LI),
        NamedIdxValues(NamedIdxValues),AuxToIdxAffs(AuxToIdxAffs),
        GMRC(GMRC),NamedConstants(NamedConstants), NamedSpaces(NamedSpaces),
        PtrOps(PtrOps), ParamSpace(ParamSpace) {
  }

  bool isSameAddress(GEPOperator *G1, GEPOperator *G2) ;
  unsigned  getVectorElementIdx(GEPOperator *LDG, GEPOperator *STG,
                                                   FixedVectorType *Ty);
  affParts* valueToAff( Value& val, isl_set* set, bool &error);
  affParts* valueToAff( Value& val, isl_set* set, bool &error, bool &nonRecoverableError);
  affParts* valueToAff( Value& val, isl_space* space,
                        isl_local_space* ls, bool &error, unsigned elemP=0);
  affParts* valueToAff( Value& val, isl_space* space,
                        isl_local_space* ls, bool &error, bool &nonRecoverableError, unsigned elemP=0);
  affParts *globalToAff(GlobalVariable* GV, isl_space* space,
                        isl_local_space* ls, bool &error, unsigned elemP=0);
  affParts *globalToAff(GlobalVariable* GV, GEPOperator *GEP, isl_space* space,
                        isl_local_space* ls, bool &error, unsigned elemP=0);
  affParts* gepToAff(GEPOperator* GEP, isl_space* Space,
                             isl_local_space* LS, bool &Error, 
                             bool &NonRecoverableError, unsigned ElemP);
  isl_set* conditionToConstraints(Value* cond, isl_set* set);
  isl_set* conditionToConstraintSet(Value* cond, isl_set* set, bool& nonRecoverableError);
  isl_set* indexValueToSet( isl_space* space, PHINode* phi, Value* val);
  isl_set* affPartsToConstraints(affParts *op0Parts, affParts *op1Parts,
                                  CmpInst::Predicate predicate);
  isl_aff* prepAffForMulList(isl_aff* orig);
  std::pair<int, int>& addConstantBounds(const std::string& Name,
                                         Value *Lower, Value *Upper,
                                         bool &nonRecoverableError,
                                         bool isVectorized = false,
                                         unsigned elemP = 0,
                                         unsigned nElems = 0);
  std::map<std::string, std::pair<int, int>>& getConstantBounds() {
    return ConstantBounds;
  }
  void setVerbose(bool v){
    verbose = v;
  }
  bool interFunctionDominatesChain(Instruction *DomWrite);
  SmallVector<isl_set*> getVersioningConstraints(){
    return VersioningConstraints;
  }

private:

  bool isaLeaf(Value* val);
  bool rollupBranch(Value* V,isl_set* set, bool &nonRecoverableError);
  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);
  Instruction *findLoopIncrement(Loop *L);

  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);
  void updateArgumentMap(Argument *Arg, Value *Operand);

  FunctionAnalysisManager &AM;
  Function &F;
  const DataLayout &DL;
  DominatorTree &DT;
  PostDominatorTree &PDT;
  LoopInfo &LI;
  isl_space* ParamSpace;
  std::map<Value*,std::string> &NamedIdxValues;
  std::map<Value*,isl_aff*> &AuxToIdxAffs;
  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;
  std::map<Value *, Argument *> ArgumentMap;
  SmallVector<isl_set*> VersioningConstraints;
  std::map<std::string, std::pair<int, int>> ConstantBounds;

  bool verbose = false;

};

class AffineCollector {
public:
  AffineCollector(FunctionAnalysisManager &AM, Function &F,
   std::map<Value*,std::string> &NamedIdxValues,
   std::map<Value*,std::string> &NamedConstants,
   DominatorTree &DT, PostDominatorTree &PDT, LoopInfo &LI) :
            AM(AM),F(F),GMRC(GlobalModRefInfoCollection(AM)),
            NamedIdxValues(NamedIdxValues),
            NamedConstants(NamedConstants), DT(DT),PDT(PDT),
            LI(LI), PtrOps(Value_lt) {
  
    NameCounter = 0;
  }
  ~AffineCollector(){}
  bool exceedsUpperBound();
  void dump();

  bool isSameAddress(GEPOperator *G1, GEPOperator *G2); 
  unsigned  getVectorElementIdx(GEPOperator *LDG, GEPOperator *STG,
                                                   FixedVectorType *Ty);
  bool collect(Value* value, bool strict = true);
  bool collectPointers(Value* start, bool strict);

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

  std::map<Value *, Argument *>& getArgumentMap() {
    return ArgumentMap;
  }

  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();
  bool interFunctionDominatesChain(Instruction *DomWrite);

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);
  void updateArgumentMap(Argument *Arg, Value *Operand);

  FunctionAnalysisManager &AM;
  Function &F;
  DominatorTree &DT;
  PostDominatorTree &PDT;
  LoopInfo &LI;
  std::map<Value*,std::string> &NamedIdxValues;
  unsigned NameCounter;
  GlobalModRefInfoCollection GMRC;
  SmallVector<Value*> WorkStack;
  SmallVector<Value*> PointerWorkStack;
  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;
  std::map<Value *, Argument *> ArgumentMap;
  std::set<std::string> uniqueConstants;

public:
  std::set<Value*> Processed;


};

class LCBuilder{
  bool invalidLC = false;

public:
  LCBuilder( FunctionAnalysisManager &AM, Function &F, LoopInfo &LI,
             ScalarEvolution &SE, 
             PostDominatorTree &PDT, DependenceInfo &DI, DominatorTree &DT,
             DomTreeUpdater &DTU, TargetLibraryInfo &TLI,
             unsigned MinStat = 1) :
             AM(AM), F(F), LI(LI), SE(SE), PDT(PDT), DI(DI), DT(DT), DTU(DTU),
             TLI(TLI) {
              idcounter = 0;
              BlockCounter = 0;
              AffCollector = new AffineCollector(AM,F,
                                                 NamedIdxValues,NamedConstants,
                                                 DT,PDT,LI);
              AffBuilder = nullptr;
              ctx = isl_ctx_alloc();
              isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
              MinStatements = MinStat < 2 ? MinStat : 2; 
            }    

  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);
  }


  isl_aff_list *buildIdentityMapExcludeTV(isl_basic_map* Map,int TV);

  void createInitialChains();
  bool calculateAndForwardConstraints(int idx,
                                 SmallVector<std::pair<int,int>> &returnsToTake,
                                 bool &success, bool backedge=false);
  void forwardConstraintSet(BasicBlock* srcBlock, LCNode* destNode,
                                           isl_set *forwardSet,bool backedge);
  void forwardConstraints(LCNode *lc,isl_set *set,bool backedge);
  bool adjustForwardingSetsForLoopBackedge(Value *CondVal, PHINode *Phi, isl_set **ConstraintSet,
                           isl_set **ShiftedFalseSet);
  std::vector<std::vector<BasicBlock*>> findLegalChainBreaksNew();
  SmallVector<std::pair<int,int>> findLegalChainBreaks(SmallVector<int>
                                                             &legalChainBreaks);
  std::string getSpareCstName(isl_aff_list *AffList);

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

  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);
  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);
  bool 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 split_output_tuples_by_input_dependency(LCEdge *Edge);
  void prepAccessMap(LCNode *node,LCEdge *edge);
  void organizeCompileTimeConstants(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);
  bool matchMultipliers( LCEdge* edge, isl_set* I );
  std::pair<int,int> findCountPosOfNonMatchingAffs(isl_aff_list **AL1, isl_aff_list **AL2, int &NegateCount);
  isl_aff* prepAffForMulList(isl_aff* orig);
  int findPosMatchingAffs(isl_aff_list *AL1, isl_aff_list *AL2);
  bool isl_aff_lists_equiv(isl_aff_list *aff_list_i,isl_aff_list *aff_list_j);
  isl_aff* constraint_to_aff(isl_constraint* Constraint, isl_dim_type DimType, int Dim);
  isl_aff* findUnmatchedAff(isl_aff_list* FirstList, isl_aff_list* SecondList);
  bool attemptAccessMapFactoring(LCEdge *Edge, LCNode *Dnode);
  bool ensureRangeComplianceAll(LoopChainGraph *); 
  bool ensureRangeCompliance(LoopChainGraph *CurrLC, LCEdge *Edge);
  void addDataspaceDims(LoopChainGraph* lc, LCNode* node, LCEdge* edge,
                        isl_set* I);
  void alignIterationSpaces(LoopChainGraph* lc,
                                           LCNode* AlignmentNode,
                                           LCNode* snode);
  SmallVector<isl_aff*> ChooseAffForEachDim(LCNode *snode, LCNode *dnode);
  isl_aff_list *buildIdentityMap(isl_basic_map* Map);
  bool  isDimensionConstant(isl_set *set, int dim);
  isl_aff *extractOutputTupleAsAff(isl_basic_map *P,int dim, isl_space* space);
  isl_set* projectAllBut(isl_set* set, int pos);
  isl_aff *isl_set_combine_to_aff(isl_set *TmpSet,isl_set *EqSet);
  void PropagateAlignmentAffs(LCNode *snode);
  isl_constraint* ChooseConstantForIncompleteIterationSpace(LCNode *snode,int pos);
  isl_aff_list * aff_list_from_basic_map(isl_basic_map *bmap);
    void correctSpacesAndMaps(LoopChainGraph* lc, LCNode* node);
    void correctMapOut(LCNode* dnode, LCEdge* edge);
    void correctIterationSpaces(LoopChainGraph* lc,LCNode* snode);
  isl_basic_map *addZeroOutputDimension(isl_basic_map *BMap, int Pos);

    isl_aff *affFromValue(int value, isl_space *space);
    isl_aff *affFromValue(const std::string& param, isl_space *space);
    isl_constraint *constraintFromAffs(isl_aff *lhs, isl_aff *rhs);

  int checkStepValue(const Value &v);
  Value* GEPtoSpace(Value* val);
  bool blockUsesValue(BasicBlock* block, SmallVector<Value *> &values);
std::vector<BasicBlock*> findSmallestDeleteList( BasicBlock* BB, 
    const std::vector<std::vector<BasicBlock*>>& legalDeleteBlocks, bool CAndFC = true);


  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 {};
  }

isl_constraint *subIslConstraints(isl_constraint *C1, isl_constraint *C2){

    assert(!isl_constraint_is_equality(C1));
    assert(!isl_constraint_is_equality(C2));

    isl_constraint *NewC = isl_constraint_copy(C1);

    // Add params
    for(int idx=0;idx<isl_constraint_dim(NewC,isl_dim_param);idx++){
      NewC = isl_constraint_set_coefficient_val(NewC,isl_dim_param,idx,
              isl_val_sub(
                isl_constraint_get_coefficient_val(NewC,isl_dim_param,idx),
                isl_constraint_get_coefficient_val(C2,isl_dim_param,idx)));
    }
    // Add set dims
    for(int idx=0;idx<isl_constraint_dim(NewC,isl_dim_set);idx++){
      NewC = isl_constraint_set_coefficient_val(NewC,isl_dim_set,idx,
              isl_val_sub(
                isl_constraint_get_coefficient_val(NewC,isl_dim_set,idx),
                isl_constraint_get_coefficient_val(C2,isl_dim_set,idx)));
    }
    // Add constants
    NewC = isl_constraint_set_constant_val(NewC,
                                      isl_val_sub(
                                        isl_constraint_get_constant_val(NewC),
                                        isl_constraint_get_constant_val(C2)));
    return NewC;
  }
  isl_constraint *addIslConstraints(isl_constraint *C1, isl_constraint *C2){

    assert(!isl_constraint_is_equality(C1));
    assert(!isl_constraint_is_equality(C2));

    isl_constraint *NewC = isl_constraint_copy(C1);

    // Add params
    for(int idx=0;idx<isl_constraint_dim(NewC,isl_dim_param);idx++){
      NewC = isl_constraint_set_coefficient_val(NewC,isl_dim_param,idx,
              isl_val_add(
                isl_constraint_get_coefficient_val(NewC,isl_dim_param,idx),
                isl_constraint_get_coefficient_val(C2,isl_dim_param,idx)));
    }
    // Add set dims
    for(int idx=0;idx<isl_constraint_dim(NewC,isl_dim_set);idx++){
      NewC = isl_constraint_set_coefficient_val(NewC,isl_dim_set,idx,
              isl_val_add(
                isl_constraint_get_coefficient_val(NewC,isl_dim_set,idx),
                isl_constraint_get_coefficient_val(C2,isl_dim_set,idx)));
    }
    // Add constants
    NewC = isl_constraint_set_constant_val(NewC,
                                      isl_val_add(
                                        isl_constraint_get_constant_val(NewC),
                                        isl_constraint_get_constant_val(C2)));
    return NewC;
  }
  void createExecutionConstraintSet(LoopChainGraph *LC);
  bool hasIllegalStagedAccessMap(int idx);


  bool checkEdge(LCEdge *edge, isl_set *I) {
    if (edge == nullptr) {
      LLVM_DEBUG_LVL(1, dbgs() << "Edge must be valid\n");
      return false;
    }
    if (edge->AccessMap == nullptr) {
      LLVM_DEBUG_LVL(1, dbgs() << "Access Map must be valid\n");
      return false;
    }
    if (I == nullptr) {
      LLVM_DEBUG_LVL(1, dbgs() << "Ieration space must be valid\n");
      return false;
    }
    return true;
  }

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

  std::vector<std::vector<BasicBlock*>> deleteBlocks;
  SmallVector<LoopChainGraph*> Chains;
  SmallVector<BasicBlock*> Successors;
  SmallVector<std::vector<BasicBlock*>> zeroLvl;
  SmallVector<std::pair<BasicBlock*,LCNode*>> stagedNodes;
  SmallVector<SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>>> stagedReads;
  SmallVector<SmallVector<std::tuple<LCNode*,LCNode*,Instruction*>>> stagedWrites;
  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;
  isl_space *SharedSpace = nullptr;

  public:
  FunctionAnalysisManager &AM;
  Function &F;
  AffineCollector *AffCollector;
  TargetLibraryInfo &TLI;
  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*,isl_aff*> AuxToIdxAffs;
  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;
  std::set<BasicBlock *> EmptySetBlocks;
  std::map<std::string,isl_aff_list*> ShiftFactors;
  std::string ErrorMessage;
};

class LCRecipeStep;
using BoundUpdateTuple = std::tuple<Instruction*,isl_ast_node*,std::string,Value*,bool,bool,bool>;
using RecipeResultTuple = std::tuple<Instruction*,int>;
// Base class for recipe steps
class LCRecipeStep{
  public:
    enum LCRecipeStepKind {
      LK_Split,
      LK_Tile,
      LK_GDup,
      LK_For_Update,
      LK_If_Update,
      LK_Delete,
      LK_Guard,
      LK_Pad,
      LK_Clone,
      LK_Identity
    };
    enum LCRecipeResultKind {
      LK_For,
      LK_Branch,
      LK_Switch,
      LK_Stmt
    };
  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;
      OrStep=nullptr;
      FusePoint=nullptr;
      result_loop=nullptr;
      source = nullptr;
      firstInRow = false;
      IsElseBlock = false;
      SNode = nullptr;
    }
    virtual bool execute() = 0;
    isl_ast_node* ast = NULL;
    isl_ast_node* OrStep;
    std::string name;
    LCRecipeStep* next = nullptr;
    LCRecipeStep* source = nullptr;
    LCRecipeStep* FusePoint = nullptr;
    // result will be saved here as well
    // the result tuple is
    // Header, LK_For, 0
    // Branching bb, LK_Branch, 0|1
    // Switching BB, LK_Switch, N of taken branch or -1 for default
    RecipeResultTuple result;
    Loop* loop;
    Loop* result_loop;
    bool firstInRow;
    bool IsElseBlock;
    LCNode *SNode;
};


class LCRecipeTile;

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

class LCBuilder;
class LCRecipeStep;
class LCRecipePad;
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 checkRulesForTransformation();
  bool executeAllRecipes();
  bool generateInitialRecipe();
  bool generateNextRecipe(int r_idx);
  bool applyFirstRecipe();
  bool applyNextRecipe(int r_idx);

  void printLoopIndices(Loop *L, StringRef PreStr);
  void getLoopInfoToPrint(Loop *L, BasicBlock *toInsert);
  ///BB is the LoopHeader of the outermost loop
  void printLoopInfo(BasicBlock *BB, StringRef PreStringToPrint);
  BasicBlock *identifyLastBBOfChain(BasicBlock *InsertBeforeBB,
                                                std::set<Loop*> &LoopsToDelete);
  void makeRangeUnreachable(BasicBlock *StartBB, BasicBlock *EndBB);
  void relocateForBadDomHack(BasicBlock *newPH, BasicBlock * newE);
  BasicBlock *InsertLoopGuard(BasicBlock *&oldPH,BasicBlock *oldE,
                                SmallVector<BoundUpdateTuple> &BoundUpdates,
                                isl_ast_node *ast);

  void executeFuse(LCRecipeStep *toFuse,
                  BasicBlock *&InsertAfterBB);
  bool advanceToNextSyncPoint(Function::iterator &MovingIter,
                              Function::iterator &AnchorIter,
                              Function::iterator &EndIter);
  bool advanceToNextSyncPoint(Function::iterator &MovingIter,
                                         Function::iterator &AnchorIter,
                                         Function::iterator &EndIter,
                                         SmallVector<Instruction*> &InstToMove);
  bool IsSyncPoint(Function::iterator FIter);
  RecipeResultTuple executeTile(LCRecipeTile *tile, Loop *L, Loop *OuterLoop);

  RecipeResultTuple executeGuardAroundLoopbody(LCRecipeStep *guard,
                                  SmallVector<BoundUpdateTuple> &BoundUpdates,
                                  BasicBlock *&InsertAfterBB);
  RecipeResultTuple executeGuard(LCRecipeStep *guard,
                                  SmallVector<BoundUpdateTuple> &BoundUpdates,
                                  BasicBlock *&InsertAfterBB);
   RecipeResultTuple executePad(LCRecipeStep *pad,
      RecipeResultTuple srcResult, SmallVector<BoundUpdateTuple> &BoundUpdates,
      std::map<std::string,Value*> &LocalIterNames, BasicBlock *&InsertAfterBB);
  bool isIfBlock(isl_ast_node *an, isl_ast_node *anp) const;
  void updateBoundOrCond(Instruction* BB, isl_ast_node* ast,
                         std::map<std::string,Value*> &localIDs,
                                        std::string idstr, Value* toReplace,
                                        bool lower, bool isElseBlock,
                                        bool updateLoopGuard);
  Loop* findInnerLoopInCFG(RecipeResultTuple result);
  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);

  Value* generateBoolFromCmp(Value *Op0,Value *Op1, int Pred, IRBuilder<> &Bldr);
  Value* isl_constraint_list_to_value(isl_constraint_list *CL, IRBuilder<> &Bldr);
  Value* isl_ast_expr_to_value(
              isl_ast_expr *expr, std::map<std::string,Value*> IDs,
              IRBuilder<> &Bldr, bool &fdiv);
  Value *isl_aff_to_value(isl_aff *aff, std::map<std::string,Value*> IDs,
              IRBuilder<> &Bldr);
  Value* isl_ast_expr_to_value(
              isl_ast_expr *expr, std::map<std::string,Value*> IDs, bool &fdiv);
  Value *constant_name_to_value(std::string name, IRBuilder<> &Bldr);
  const SCEV* isl_ast_expr_to_SCEV(isl_ast_expr *expr,
                                  std::map<std::string,Value*> &IDs,bool &fdiv);
  const SCEV* isl_ast_expr_to_SCEV(isl_ast_expr* iter, 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(NULL, expr, NULL, fdiv);
  }
  static const SCEV* isl_ast_expr_to_SCEV_this(LCRecipeBuilder* th,
                                              isl_ast_expr* iter,
                                              isl_ast_expr* expr,
                                              Loop* scope, Value* newID,bool &fdiv){
    th->setCurrentScope(scope);
    return th->isl_ast_expr_to_SCEV(iter,expr,newID,fdiv);
  }

  bool relocateConstLoads();
  void correctSurroundingCF();
  void setCurrentScope(Loop* scope){
    CurrentScope = scope;
  }
  std::string getNextName(){
    return "lcgv" + std::to_string(nameCntr++);
  }
  void findEscapingValues(BasicBlock* StartBlock, BasicBlock* EndBlock, 
                        Function* F, SmallVectorImpl<Value*>& EscapingValues);

  private:
  BasicBlock *sinkInstructionsStepUp(BasicBlock *BB);
  void sinkInstructions(BasicBlock *BB);
  std::vector<std::pair<const SCEV*,bool>> stepsForEquivalentTypes(isl_ast_node* strt, isl_ast_node* goal);
  Value *insertGlobalVarStoreAndLoadFromInst_Value(Function *F, Instruction *Inst, unsigned vectorLane);
  const SCEV *insertGlobalVarStoreAndLoadFromInst(Function *F, Instruction *Inst, unsigned vectorLane);
  std::string getNodeName(isl_ast_node *node) const;
  std::map<std::string, int> getBlockCounts(const std::vector<std::vector<isl_ast_node*>*>& scheduleTable);
  LCRecipeStep *createIdentRecipe(const std::string& name,
                                  LCRecipeStep* sourceStep, int idx,
                                  std::vector<LCRecipeStep*>& recipe,
                                  isl_ast_node *ast);
  LCRecipeStep *createCloneRecipe(const std::string& name,
                                  LCRecipeStep* sourceStep, int idx,
                                  std::vector<LCRecipeStep*>& recipe,
                                  isl_ast_node *ast);
  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);
  RecipeResultTuple  RetreatInCFG( RecipeResultTuple current);
  RecipeResultTuple AdvanceInCFG(RecipeResultTuple current);
  int getSuccessorIdx(Instruction *Term, Instruction *Work);
  //std::tuple<BasicBlock*,LCRecipeStep::LCRecipeResultKind,int> getResultAsCFParent(
    //std::tuple<BasicBlock*,LCRecipeStep::LCRecipeResultKind,int> current );
  //Print AST to file
  void writeASTToFile(unsigned r_idx, StringRef BaseName);

  LCBuilder &LCB;
  LoopChainGraph* lc;
  ScalarEvolution &SE;
  DominatorTree &DT;
  PostDominatorTree &PDT;
  const DataLayout &DL;
  LoopInfo &LI;
  DomTreeUpdater &DTU;
  Loop *CurrentScope;
  int nameCntr;
  std::vector<isl_ast_expr*> NeHack;
  std::vector<BasicBlock*> BranchesCreated;
  std::vector<std::vector<LCRecipeStep*>*> recipes;
  std::map<BasicBlock*,BasicBlock*> FastForward;
  std::map<Instruction*,LoadInst*> NewGlobalLoads;
};
// 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){
    NewConstant = nullptr;
    NewConstantSet = false;
   }

  bool execute() override;

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

  isl_ast_expr *NewConstant;
  bool NewConstantSet;

};
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;
    const SCEV* lb=LCRecipeBuilder::isl_ast_expr_to_SCEV_this(
                                         (LCRecipeBuilder*)obj,
                                         isl_ast_node_for_get_iterator(forloop),
                                         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;
    const SCEV* ub = LCRecipeBuilder::isl_ast_expr_to_SCEV_this(
                                         (LCRecipeBuilder*)obj,
                                         isl_ast_node_for_get_iterator(forloop),
                                         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_iterator(forloop),
                                         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_iterator(forloop),
                                         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 LCRecipeClone : public LCRecipeStep{
  public:
  LCRecipeClone(): LCRecipeStep(LK_Clone){ }

  bool execute() override;

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

};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeClone &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);

class LCRecipeForUpdate : public LCRecipeStep{
  public:
  LCRecipeForUpdate(): LCRecipeStep(LK_For_Update){}
  LCRecipeForUpdate(bool IsLower, bool IsUpper, bool IsIter):
    LCRecipeStep(LK_For_Update), IsLower(IsLower), IsUpper(IsUpper),
    IsIter(IsIter) {}

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_For_Update;
  }
    bool IsLower;
    bool IsUpper;    
    bool IsIter;
};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeForUpdate &S);

class LCRecipeIfUpdate : public LCRecipeStep{
  public:
  LCRecipeIfUpdate(): LCRecipeStep(LK_If_Update){}

  bool execute() override;

  static bool classof( const LCRecipeStep *S){
    return S->getKind() == LK_If_Update;
  }
};
raw_ostream &operator<<(raw_ostream &OS, const LCRecipeIfUpdate &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_LVL(3, 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_LVL(3, dbgs() << "PHI not index var: " << phi << "\n");
    return;
  }

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

class printfVisitor : public InstVisitor<printfVisitor>{
  // Add addtional printf to the BB.
  public:
  void visitCallInst(CallInst &CI){
    Function *CalledF;
    if (!(CalledF = dyn_cast_or_null<Function>(CI.getCalledOperand())))
      return;
    if(!CalledF->getName().contains("printf"))
      return;

    PrintCalls.push_back(&CI);
  }
  Value *InsertPrintfInBlockBefore(Module *M, Instruction *InsertBefore, StringRef InpString,
                                 SmallVector<Value *, 4> &Args) {
    Function *func_printf = M->getFunction("printf");
    CallInst *PrintCI;
    if (!func_printf) {
      PointerType::get(IntegerType::get(M->getContext(), 8), 0);
      FunctionType *FuncTy9 =
          FunctionType::get(IntegerType::get(M->getContext(), 32), true);

      func_printf =
          Function::Create(FuncTy9, GlobalValue::ExternalLinkage, "printf", M);
      func_printf->setCallingConv(CallingConv::C);

      AttributeList func_printf_PAL;
      func_printf->setAttributes(func_printf_PAL);
    }
    IRBuilder<> Builder(InsertBefore);
    Value *Str = Builder.CreateGlobalStringPtr(InpString);
    std::vector<Value *> int32_call_params;
    int32_call_params.push_back(Str);

    for (auto &Arg : Args) {
      int32_call_params.push_back(Arg);
    }

    PrintCI = CallInst::Create(func_printf, int32_call_params, "call",
                                InsertBefore);
    return PrintCI;
  }

  void insertPrintCalls() {
    for (CallInst *CI : PrintCalls) {
      SmallVector<Value*, 4> ValsVec;
      BasicBlock *BB = CI->getParent();
      Module *M = BB->getParent()->getParent();
      // InsertPrintfInBlockBefore(M,&CI,valToStr(BB) + " ",ValsVec);
      InsertPrintfInBlock(M,BB, valToStr(BB) + "\n", ValsVec, nullptr);
    }
  }

private:
  SmallVector<CallInst *, 4> PrintCalls;
};

} // namespace llvm

#endif // LLVM_TRANSFORMS_SCALAR_LOOPCHAIN_H