//===- GlobalSLPVectorize.h ------------------------------------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_VECTORIZE_GLOBALSLPVECTORIZE_H
#define LLVM_TRANSFORMS_VECTORIZE_GLOBALSLPVECTORIZE_H

#include "llvm/IR/PassManager.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LegacyAliasAnalysis.h" // AOCC
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/NoFolder.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/Verifier.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/DOTGraphTraits.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Vectorize.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <iterator>
#include <iostream>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <float.h>

namespace llvm {

#define GSV_NAME "gslp-vectorize"
#undef DEBUG_TYPE
#define DEBUG_TYPE "gslp-vectorize"
#ifndef NDEBUG
static const char *VerboseDebug = DEBUG_TYPE "-verbose";
static const char *VerboseDebugLevel1 = DEBUG_TYPE "-verbose-1";
static const char *VerboseDebugLevel2 = DEBUG_TYPE "-verbose-2";
static const char *VerboseDebugLevel3 = DEBUG_TYPE "-verbose-3";
static const char *VerboseDebugLevel4 = DEBUG_TYPE "-verbose-4";
static const char *VerboseDebugLevel5 = DEBUG_TYPE "-verbose-5";
static const char *DebugCodegen = DEBUG_TYPE "-codegen";
static const char *DebugCliqgen = DEBUG_TYPE "-cliquegen";
static const char *DebugPermute = DEBUG_TYPE "-permute";
static const char *DebugTreeBasedGlue = DEBUG_TYPE "-tree-based-glues";
static const char *DebugPadding = DEBUG_TYPE "-padding";
static const char *DebugQuick = DEBUG_TYPE "-quick";
#endif

class CompatibilityGraph;
class HierCompatibilityGraph;
class GSLPCost;

// Size of the vector registers in x86
enum X86_vec_reg_type {
  XMM_SIZE = 128, YMM_SIZE = 256, ZMM_SIZE = 512
};

// Class to store the region
// Region: Set of Instructions
// Global Region: formed by the entire BB
// Local Region: set of some instructions of the BasicBlock
// In case of normal GSLP, Global Region is used
// Motivation behind Local region: BB might be too large, there will be too
//  many cliques. One way is to divide the BB into smaller sets of instructions
class RegionType {
private:
  BasicBlock *BB;
  // List of instructions belonging to that region
  // Usually not populated (for efficiency reasons) in case of a Global region
  std::vector<Instruction*> Insts;
  // Maps Instruction* to its index in the Insts vector
  // This is required to efficiently convert Global CGNodeId to Local CGNode Id
  // To do so, given a Global CGNode Id, get the Instruction* from GSLP Util
  // The index of the Instruction* in this map is the Local CGNode Id
  // Assumptions: Level 0 CGNode Ids always begin from 0 (just like Inst Ids)
  // To convert Local CGNodeId to Global CGNode Id, use Insts vector then GSLPU
  // Eg: Let BB: I0 I1 I2 I3 I4
  // Level 0 CGNodeIds for the Global Region:  0 1 2 3 4
  // Assume there are 2 regions, Region1 = I0 I1, I4 Region2 = I2, I3
  // Region1, Level 0 CGNodeIds = 0, 1, 2
  // To convert Global CGNodeId 4 to local CGNodeId for Region 1 (which is 2),
  // we first get the Instruction* corresponding to InstId 4. We can then query
  // this map to get the local CGNodeId
  std::map<Instruction*, uint32_t> InstsToIndex;
  // True if it is a local region, false otherwise
  bool IsLocal;
  // True if the number of instructions in the region is large, ie, greater
  // than GSLPLargeBBSize
  bool LargeBB;

public:
  RegionType() : BB(nullptr), IsLocal(false), LargeBB(false) {}

  RegionType(BasicBlock *BB_, bool IsLocal_ = false) {
    BB = BB_;
    IsLocal = IsLocal_;
    LargeBB = false;
  }

  // Number of instructions in the region
  uint32_t size() {
    if (!IsLocal) return BB->size();
    return Insts.size();
  }

  void setLargeBB(bool LargeBB_) { LargeBB = LargeBB_; }
  bool getLargeBB() { return LargeBB; }
  BasicBlock *getBB() { return BB; }
  bool getIsLocal() { return IsLocal; }
  Instruction *getInstAt(uint32_t Index) { return Insts[Index]; }
  std::vector<Instruction *> &getInsts() { return Insts; }

  // Returns if the given instruction is a part of the region
  bool isAvail(Instruction *I) {
    if (!IsLocal) return I->getParent() == BB;
    return InstsToIndex.count(I);
  }

  // Get the index of the instruction
  uint32_t getInstToIndex(Instruction *I) {
    assert(InstsToIndex.count(I) && "Cannot get the Index of given Instruction");
    return InstsToIndex[I];
  }

  void setBB(BasicBlock *BB_) { BB = BB_; }
  void setIsLocal(bool IsLocal_) {IsLocal = IsLocal_;}
  // Add an instruction to the region
  void addInst(Instruction *I) {
    Insts.push_back(I);
    if (IsLocal) InstsToIndex[I] = Insts.size() - 1;
  }

  // Add multiple instructions to the region
  void addInsts(std::vector<Instruction*> Insts_) {
    for (Instruction *I: Insts_) addInst(I);
  }

  // Add all the instructions of BB to the region
  void addAllBBInstructions() {
    for (auto &I: *BB) addInst(&I);
  }

  // Display the region
  void print() {
    dbgs() << "GSLP: Printing Region\n";
    if (IsLocal) {
      dbgs() << "  Local Region\n";
      for (auto &I: Insts) {
        dbgs() << "  InstToIndex: " << getInstToIndex(I) << ", ";
        I->dump();
      }
    }
    else {
      dbgs() << "  Global Region\n";
      for (auto &I: *BB) {
        dbgs() << "  ";
        I.dump();
      }
    }
  }
};


// Class to store all the common data structures used across other classes.
// This is implemented as a SingleTon Class as we need a single instance of
// this object.
class GSLPUtil {
private:
  // The region that is to be vectorized.
  RegionType *Region;
  AliasAnalysis *AA = nullptr;
  ScalarEvolution *SE = nullptr;
  const DataLayout *DL = nullptr;
  DependenceInfo *DI = nullptr;
  LoopInfo *LI = nullptr;
  TargetTransformInfo *TTI = nullptr;
  int32_t MaxVectorRegSize;

  // Map to store unique id for each instruction.
  using InstToIdMapType = SmallDenseMap<Instruction *, uint32_t>;
  InstToIdMapType InstToIdMap;
  // The reverse map of InstToIdMap.
  using IdToInstMapType = SmallDenseMap<uint32_t, Instruction *>;
  IdToInstMapType IdToInstMap;

  // Map to store the number of uses of each instruction within the same BB
  // This is computed (and stored) for each instruction on demand only
  using InstToUsesMapType = SmallDenseMap<Instruction *, uint32_t>;
  InstToUsesMapType InstToUsesMap;

  using InstsWithSameOpcodeType = SmallVector<Instruction *, 8>;
  using OpcodeToInstructionsMapType =
    SmallDenseMap<uint32_t, InstsWithSameOpcodeType>;
  // Map to store opcode to instruction map.
  OpcodeToInstructionsMapType OpcodeToInstsMap;

  // Map of memory fences for a load/store instructions. This information is
  // required to maintain the original ordering during codegen.
  using MemoryFencesListType = SmallVector<uint32_t, 4>;
  SmallDenseMap<uint32_t, MemoryFencesListType> MemoryFencesMap;

  // Conjunction of GSLPEnableRegionBased and candidateForRegionBased()
  // For all the region-based specific things, this flag should be used
  bool RunRegionBased;

  using RegionTypeList = std::vector<RegionType*>;
  using InstToTopologicalRegionMapType = SmallVector<RegionType*>;
  // Map of each Instruction id to RegionType*
  // (Regions are the levels in topological ordering of the Data dependency
  // graph of the BB)
  InstToTopologicalRegionMapType InstToTopologicalRegionMap;

  // Instructions Id1 and Id2 may alias and hence are memory fences for each
  // other. Update the fence map. Add Id2 in the fence list of Id1 and vice
  // versa.
  void updateFenceList(uint32_t Id1, uint32_t Id2);
  // Add Id2 to the fence list of Id1.
  void addFence(uint32_t Id1, uint32_t Id2) {
    if (hasAnyFenceFor(Id1))
      MemoryFencesMap[Id1].push_back(Id2);
    else {
      SmallVector<uint32_t, 4> FenceList;
      FenceList.push_back(Id2);
      MemoryFencesMap.insert(std::make_pair(Id1, FenceList));
    }
  }
  // Print the fence lists.
  void printFenceLists() {
    for (auto &FenceListEntry : MemoryFencesMap) {
      uint32_t Id1 = FenceListEntry.first;
      dbgs() << "  " << Id1 << ": ";
      auto &FenceList = FenceListEntry.second;
      for (uint32_t Id2 : FenceList)
        dbgs() << Id2 << " ";
      dbgs() << "\n";
    }
  }

  // This function returns the stride for a load. It looks at loads with access
  // patter i * numGroups + offset and returns numGroups.
  int64_t getStrideForGEP(Value *Addr, ScalarEvolution *SE);
  // Function to inhibit vectorization of lbm for ArrayRemap.
  bool getStrideDetails(const SCEV *scev, int64_t &gepStep,
                               int64_t &gepOffset, GetElementPtrInst *GEP,
                               ScalarEvolution *SE);
  // Function to inhibit vectorization of lbm for ArrayRemap.
  const SCEV *getExprBase(const SCEV *S);
  // Function to inhibit vectorization of lbm for ArrayRemap
  const SCEV *handleAddExpr(const SCEV *S, int64_t &mulFactor);
public:
  GSLPUtil() { clear(); }
  // Delete the copy constructor as this is a SingleTon class.
  GSLPUtil (const GSLPUtil& Obj) = delete;

  ScalarEvolution *getSE() { return SE; }
  const DataLayout *getDL() { return DL; }
  DependenceInfo *getDI() { return DI; }
  LoopInfo *getLI() { return LI; }
  TargetTransformInfo *getTTI() { return TTI; }

  void init(RegionType *Region_, AliasAnalysis *AA_, ScalarEvolution *SE_,
            const DataLayout *DL_, DependenceInfo *DI_, LoopInfo *LI_,
            TargetTransformInfo *TTI_, bool SetGSLPZn4MaxVecRegSize_,
            int GSLPMaxRegisterWidth, bool RelaxRestrictions) {

    Region = Region_; AA = AA_; SE = SE_; DL = DL_; DI = DI_; LI = LI_;
     TTI = TTI_;
    RunRegionBased = false;
    // Set the maximum register width.
    if (GSLPMaxRegisterWidth > 0)
      MaxVectorRegSize = GSLPMaxRegisterWidth;
    // For cpu >= znver4, we want to use 256 bits vector register size. If
    // -gslp-relax-restrictions is ON, we will still use the TTI max width.
    else if (!RelaxRestrictions &&
        (SetGSLPZn4MaxVecRegSize_ && TTI->isZnFamily() && TTI->hasAVX512()))
      MaxVectorRegSize = 256;
    else MaxVectorRegSize =
      TTI->getRegisterBitWidth(TargetTransformInfo::RGK_FixedWidthVector);
  }
  // Get the unique id for the instruction
  uint32_t getId(Instruction *I) {
    return InstToIdMap[I];
  }
  // Get the instruction for the Id.
  Instruction *getInst(uint32_t Id) {
    return IdToInstMap[Id];
  }

  InstToIdMapType &getInstToIdMap() { return InstToIdMap; }
  IdToInstMapType &getIdToInstMap() { return IdToInstMap; }

  // Assign a unique id to each instruction in the basic block. This creates
  // the reverse map from unique id to instruction too.
  // Called only for Global Region
  void buildInstToIdMap() {
    assert(!Region->getIsLocal() && "Cant build InstToIdMap for Local Region");
    uint32_t Id = 0;
    for (Instruction &I : *getBB()) {
      InstToIdMap[&I] = Id;
      IdToInstMap[Id] = &I;
      Id++;
    }
    LLVM_DEBUG(dbgs() << "GSLP: Instruction to Id Map:\n";
                printInstToIdMap(););
  }

  // Print instructions to id map.
  void printInstToIdMap() {
    for (uint32_t Id = 0; Id < IdToInstMap.size(); Id++) {
      Instruction *I = IdToInstMap[Id];
      dbgs() << "  " << Id << ": "; I->dump();
    }
  }

  // Build list of instructions per opcode in the current block.
  void buildOpcodeToInstsMap();
  OpcodeToInstructionsMapType &getOpcodeToInstsMap() {
    return OpcodeToInstsMap;
  }

  // Print list of instructions per opcode.
  void printOpcodeToinstsMap() {
    for (auto MapEntry : OpcodeToInstsMap) {
      unsigned Opcode = MapEntry.first;
      auto &InstsVec = MapEntry.second;
      dbgs() << "  Opcode: " << Opcode << ":\n";
      for (Instruction *I : InstsVec) {
        dbgs() << "  "; I->dump();
      }
    }
  }
  // Check for pairs of instructions which alias each other. If they are aliases
  // mark the first one as a fence to the other one and vice-versa.
  void computeMemoryDeps();
  // Check if there exist a fence for a node.
  bool hasAnyFenceFor(uint32_t Id) { return MemoryFencesMap.count(Id) != 0; }
  // Get the fence list for the insruction with id InstID.
  MemoryFencesListType &getFenceList(uint32_t ID) { return MemoryFencesMap[ID]; }
  // Check if Id2 is present in the fence list of id1.
  bool isInFenceList(uint32_t Id1, uint32_t Id2) {
    // If no fence for Id1, return false
    if (!hasAnyFenceFor(Id1)) return false;

    auto &FenceList = MemoryFencesMap[Id1];
    for (uint32_t Id : FenceList) {
      if (Id == Id2)
        return true;
    }
    // Not found.
    return false;
  }

  // Return the current basic block being processed.
  BasicBlock *getBB() { return Region->getBB(); }
  // Return the current region being processed
  RegionType *getRegion() { return Region; }
  void setRegion(RegionType *Region_) { Region = Region_; }

  bool getRunRegionBased() { return RunRegionBased; }
  void setRunRegionBased(bool NewVal) { RunRegionBased = NewVal; }

  // Function to inhibit vectorization of lbm for ArrayRemap. Returns true if
  // it is safe to vectorize adjacent loads/stores. Assumes the underlying
  // objects are same for both the addresses.
  bool isSafeToVectorize(Value *Addr1, Value *Addr2, ScalarEvolution *SE);

  // Get the maximum vector register size
  int32_t getMaxVecRegSize() { return MaxVectorRegSize; }
  // Set the maximum vector register size
  void setMaxVecRegSize(uint32_t NewSize) { MaxVectorRegSize = NewSize; }

  // Utility function to generate vector instruction for a list of scalar
  // instructions. We generate scalar instructions also with the same function
  // if the clique width is 1.
  Value *codegen(ArrayRef<Value *> VL, SmallVector<Value *, 4> InputVecs,
                   Instruction *InsertPt);
  // Get an estimate of the performance gain due to vectorizing the
  // instructions in VL. \param ArrayRef list of scalar instructions that
  // would be vectorized. \returns The execution cost improvement due to
  // vectorization.
  InstructionCost getPerfGain(ArrayRef<Value *> VL);

  // Check if Value \param V defined external to basic block \param BB.
  bool isExternal(Value *V, BasicBlock *BB) {
    Instruction *I = dyn_cast<Instruction>(V);
    // If V is an instruction not defined in BB, V is external.
    if ((I && I->getParent() != BB))
      return true;
    // If V is an argument to the function, V is external.
    if (isa<Argument>(V))
      return true;
    // If V is global, V is external.
    if (isa<GlobalValue>(V))
      return true;
    // If V is a constant we can consider it as an external value.
    if (isa<Constant>(V))
      return true;
    // If this a constant expression as in the following case, V is external.
    // ptr getelementptr inbounds (%struct.anon, ptr @pughpriv, i64 0, i32 50)
    if (isa<ConstantExpr>(V) && isa<GEPOperator>(V)) {
      return true;
    }
    // A basic block can be an input value in case of a branch instruction or
    // as parameters to some intrinsics. We treat it as external value then.
    if (isa<BasicBlock>(V))
      return true;
    // A meta data is an external value.
    if (V->getType()->isMetadataTy())
      return true;
    // Make the recursive call to find out if a chain of GEP reaches outside
    // the block through its pointer operand.
    //
    // if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V))
    //   return isExternal(GEP->getPointerOperand(), BB);
    //
    // Earlier we used to have the above code to handle GEP. However, that does
    // not work if the GEP is defined in the current block and its pointer
    // operand reaches a non-GEP instruction within the same block. Hence, we
    // are forcing any GEP to be attached to the DummyRoot, by returning true
    // here. Otherwise the vector node associated with this GEP will become
    // dangling. This might introduce an ordering issue in the generated
    // CliqueDAG. However, we will deal with that in codegen.
    if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V))
      return true;

    // The input is not external.
    return false;
  }

  // For each Instruction Id, assigns it to a RegionType*
  // Regions are the levels in the topological ordering to DDG of BB
  // (This can be used as an additional restricton to define compatibility of
  // 2 nodes. Instructions in different levels can be termed as incompatible)
  void populateInstToTopologicalRegionMap(
    RegionTypeList TopologicalOrderLevels) {
    // Resize the array which maps each Instruction to RegionType*
    InstToTopologicalRegionMap.resize(getBB()->size(), nullptr);
    // Iterate over each instruction in each region, and just populate the map
    for (auto *Region: TopologicalOrderLevels) {
      for (Instruction *I: Region->getInsts()) {
        uint32_t InstId = getId(I);
        InstToTopologicalRegionMap[InstId] = Region;
      }
    }
  }

  // Given an Instruction, returns the number of uses of that instruction
  // within the same BB. It computes the number of uses and saves it in a map
  // so that it doesn't need to be recomputed again
  // Precondition: Instruction is in the same BB as GSLPUtil
  uint32_t getNumUsesInBB(Instruction *Inst) {
    // If the number of uses of the given Inst have been computed, reutrn it
    if (InstToUsesMap.count(Inst)) return InstToUsesMap[Inst];

    // Number of uses of the given instruction have not been computed
    auto *BB = getBB();
    // Set to store the users of the instruction, since we want unique uses
    // For an instruction like a = b + b, we want to count it as 1 user only
    SmallSet<Instruction*, 4> InstUsers;
    for (auto &U: Inst->uses()) {
      // If the use is an instruction
      if (auto *UserInst = dyn_cast<Instruction>(U.getUser())) {
        // User is not in the same BB
        if (UserInst->getParent() != BB) continue;
        // User is a phi node whose operand is available via backedge
        if (isa<PHINode>(UserInst) && UserInst->comesBefore(Inst)) continue;
        InstUsers.insert(UserInst);
      }
    }
    InstToUsesMap[Inst] = InstUsers.size();
    return InstToUsesMap[Inst];
  }

  RegionType *getTopologicalRegion(uint32_t InstId) {
    assert(InstId < getBB()->size()
      && "Invalid Instruction Id, cannot find topological region");
    assert(InstToTopologicalRegionMap[InstId] != nullptr
      && "Region not populated for the given instruction");
    return InstToTopologicalRegionMap[InstId];
  }

  // Clear all the datastructures used.
  void clear() {
    // Clear instruction to id maps.
    InstToIdMap.clear();
    IdToInstMap.clear();
    // Clear opcode to instruction map.
    OpcodeToInstsMap.clear();
    OpcodeToInstsMap.clear();
    // Clear Memory fences list.
    MemoryFencesMap.clear();
    InstToUsesMap.clear();
  }

  ~GSLPUtil() {
    // Clear instruction to id maps.
    InstToIdMap.clear();
    IdToInstMap.clear();
    // Clear opcode to instruction map.
    OpcodeToInstsMap.clear();
    // Clear Memory fences list.
    MemoryFencesMap.clear();
    InstToUsesMap.clear();
  }
};

// A clique in a graph is a subgraph where there is a connection between all
// its nodes. In GSLP, A clique embodies the notion of a cleanly vectorizable
// region. We find cliques for compatibility graphs (CG) at each level. A clique
// can be visalized as a two-dimensional array, where Each row represents a
// vectorizable pack and is fed by the row preceding it. Except the first row,
// all the lanes in the other rows are fed by the corresponding lanes in the
// preceding row. That is, no glue instructions (shuffles) are needed to
// vectorize the clique except at the entry and at the exit.
//
// TODO: Describe different types of cliques.
class Clique {
public:
  // Three types of cliques are possible. 1. MemoryClique 2. Arithmetic
  // 3. ReductionClique. 4. Constant
  //
  // Type is set as Constant when all the values in the clique are constants.
  // This helps in codegen.
  enum class KindType { Memory, Arithmetic, Reduction, Constant };
  KindType Kind;
  // FIXME: Check if we can change this type to ArrayRef<Instruction*>.
  // This might be faster than using a SmallVector.
  using VecRowType = SmallVector<Value*, 4>;
  using VecRowsType = SmallVector<VecRowType, 4>;
  // Type of a row in this clique.
  using VecRowPtrType = std::unique_ptr<VecRowType>;

  // Used to handle phi node whose one or more operands are available via
  // backedge/same phi. For such inuts we use this AvailFromType
  enum class AvailFromType {
    AvailFromBackEdge, AvailFromSamePhi, AvailFromOther
  };

  // When this clique is a part of the CliqueDAG it can be either a vector node
  // or glue node.
  // GlueFromBackEdge: When the glue is an input to phi which is available from
  // backedge
  // GlueFromSamePhi: When the glue is an input to phi which is available from
  // same phi
  // For GlueFromBackEdge and GlueFromSamePhi, we don't populate their input
  // nodes to break the cyclic dependency
  enum class CliqueDAGNodeType { Glue, Vector, GlueFromBackEdge, GlueFromSamePhi };
  CliqueDAGNodeType ClqDAGNodeType;

  // This type will be set during generation of glue instructions to store what
  // all operands of the saved glue instructions are to be relplaced with the
  // available vectors at codegen.
  enum class GlueInstOperandReplaceType {
    ReplaceFirstWithPreviousInput,
    ReplaceFirstWithCurrentInput,
    ReplaceSecondWithCurrentInput,
    ReplaceBoth // Specifically for InputNum = 1
  };
  GlueInstOperandReplaceType GlueInstOprndReplaceType;
  // Types for storing input/output clique nodes for this clique.
  //
  // We use SmallVector to preserve to order of input/output cliques for
  // reproducibility.
  /// TODO: However, there can be multiple entries of same node in a vector.
  /// Currently, we have restricted this at the time of insertion but try to
  /// come up with better storage implementation.
  using InputClqNodeShrdPtrType = std::shared_ptr<Clique>;
  using InputClqNodesType = SmallVector<InputClqNodeShrdPtrType, 2>;
  // Output node types are exactly same as input node types
  //
  using OutputClqNodeShrdPtrType = InputClqNodeShrdPtrType;
  using OutputClqNodesType = InputClqNodesType;
  using OutputClqNodesMapType = std::map<uint32_t, OutputClqNodesType>;
  // Type for storing all the instructions in a clique.
  using InstsInCliqueType = SmallVector<SmallVector<Instruction*>>;
  // Set types to store reaches and reachable nodes for this clique from the
  // CliqueDAG. Note that we use set here since std::set_intersection
  // function expects an already sorted input to work on.
  using ClqNodesSetType = std::set<InputClqNodeShrdPtrType>;
  // A clique can be permuted based on its inputs. When it is permuted, a new
  // permuted clique is created, and the original clique remains the same
  // 3 permutation states of Clique:
  // 1) No permutation has been created based on its inputs
  // 2) Permutation has been created based on its inputs
  // 3) This clique has been created as a result of permuting some clique
  // For Cliques of state 2 and 3, we don't want to create another permutation
  // For cliques of state 3, we might want to prefer them in some cases
  // Refer to comments in the permuteCliques() definition for details
  enum PermStateType { NoPermCreated, PermCreated, PermutedClique };
private:
  // Pointer to GSLPUtil class
  GSLPUtil *GSLPU;
  // The CG from which this clique is gnenerated. This is making the lookup
  // faster even though we have the collection of clique attached to each CG.
  CompatibilityGraph *CG;
  // Level of the GG from which this clique is generated.
  uint32_t Level;
  // Set the kind of the clique.
  void setKind(KindType K) { Kind = K; }
  // The CGNodes in this clique. The order of entries matter at least in case
  // of MemoryClique.
  using CGNodeIDType = uint32_t;
  using CliqueNodeType = SmallVector<CGNodeIDType, 8>;
  CliqueNodeType CliqueNodes;
  // We maintain the instructions too which compose this clique. Doing this
  // makes us easier to create new cliques out of instructions without relying
  // on CGNodes. This makes creating cliques easier at the stage of splitting
  // cliques.
  InstsInCliqueType CliqueInstsMatrix;
  // Unique ID for this clique in the CliqueDAG.
  using CliqueIDType = uint32_t;
  CliqueIDType CliqueId;
  // Width of the clique.
  uint32_t Width;
  // The vector factor of the cliqueReg. The width of the clique may be higher
  // than the VF.
  int32_t VF;
  // Width of the clique in bits
  int32_t CliqueWidthInBits;
  // The estimated execution cost of the vector instructions in instruction
  // matrix w.r.t. the execution cost of their scalar instructions. Cost < 0 ==>
  // profitable Cost > 0 ==> non-profitable cost = 0 ==> neither profitable nor
  // non-profitable.
  InstructionCost Cost;
  // Cost of extractelement instructions requried for live out values.
  InstructionCost LiveOutCost;
  // Boolean flag to keep track of the computation of the cost. The cost is
  // computed only once for a clique.
  bool CostComputed;
  // To store rows of instructions in this clique.
  using CliqueRowsType = SmallVector<VecRowPtrType, 4>;
  CliqueRowsType CliqueRows;
  // Number of rows in this clique.
  uint32_t NumRows;
  // Number of input rows in this clique.
  uint32_t NumInputRows;
  // To store the input clique nodes for this clique for each row. Note that an
  // input node can be either another clique node or a glue node. A glue node
  // is also of type Clique. Also note that this container will not respect the
  // operand order (according to the operand order) of the input vector
  // instructions that will be created during codegen. It can be recovered from
  // the NonReusableBitVector. Refer to printInputCliques for that.
  InputClqNodesType InputClqNodes;
  // Actual number of input node used for a glue node.
  int32_t NumUsedInputNodes = 0;
  // To store the output clique nodes for this clique for each row. Note that an
  // output node can be either another clique node or a glue node.
  InputClqNodesType OutputClqNodes;
  // Other than def-chain input-output nodes, each node in CliqueDAG can have
  // memory dependencies on other nodes. These MemDep input-output nodes are
  // essential in finding out cycles induced in the CliqueDAG and maintaining
  // the ordering of the instructions generated at CodeGen.
  // The MemDep input nodes can be any clique node in the CliqueDAG.
  InputClqNodesType MemDepInputClqNodes;
  // These Mem-Dep output nodes serve the same purpose as Mem-Dep input nodes.
  InputClqNodesType MemDepOutputClqNodes;
  // These sets are created for detecting cycle at the time of adding clique
  // into the CliqueDAG.
  // NodesReachesCurrSet -> A node N belongs to this set if that node 'reaches'
  // the current node that we are adding, through use-def edge or mem-dep edge.
  // NodesReachableFrCurrSet -> A node N belongs to this set if that node is
  // 'reachable' from the current node that we are adding, through use-def edge
  // or mem-dep edge.
  // These sets are of type map for supporting multiple sets that belong to
  // each row of a multi-row clique once we start supporting multi-row cliques.
  ClqNodesSetType NodesReachesCurrSet, NodesReachableFrCurrSet;

  // Map to store the input rows for each row. A row is mapped to a vector of
  // Values. We are using unique_ptr here for efficiency reasons as we need to
  // store the pointers in some other maps.
  //
  using InputRowType = SmallVector<Value *, 4>;
  using InputRowsType = SmallVector<InputRowType, 2>;
  using InputRowPtrType = std::unique_ptr<InputRowsType>;
  // We are using std::map here as we can update the input row for an
  // existing row easily. Also compared SmallDenseMap, the lookup will be
  // efficient.
  using InputRowsMapType = std::map<uint32_t, InputRowPtrType>;
  InputRowsMapType InputRowsMap;
  // Type for storing the vector type for each row.
  //
  using VectorTypesMapType = std::map<uint32_t, VectorType *>;
  VectorTypesMapType VectorTypesMap;
  // Type for storing the insert point for the glue/vector instructions.
  using InsertPointMapType = std::map<uint32_t, Instruction *>;
  InsertPointMapType InsertPointMap;

  // Type for storing the indices of live out values if any for each row of the
  // clique.
  using LiveOutValsIndicesType = SmallVector<int32_t, 4>;
  using LiveOutValsIndicesTypeMap = std::map<uint32_t, LiveOutValsIndicesType>;
  LiveOutValsIndicesTypeMap LiveOutValIndicesMap;

  using CliquePtrType = std::shared_ptr<Clique>;
  // The parent clique from which this clique is generated.
  CliquePtrType *ParentClqPtr = nullptr;
  // Variable to mark if this clique is connected to DummyRoot of the CliqueDAG.
  bool ConnectedToDummyRoot;
  // Variable to mark if this clique is connected to node having external
  // values.
  bool HasExternalVal;
  bool HasAllExternalVal;
  // The final glue instruction generated if it is a glue node.
  Value *GlueInst;
  // Variable to be set if the glue insts are generated using the tree based
  // approach.
  bool HasTreeBasedGlues;
  // To store the intermediate glue instructions generated if we have multiple
  // input nodes.
  using IntermediateGlueInstsType = SmallVector<Value *, 4>;
  IntermediateGlueInstsType IntermediateGlueInsts;
  // Map to store the information that which operand of the saved intermediate
  // glue instructions to be replaced.
  using GlueInstsOperandReplaceTypeMapType =
    std::map<Value *, GlueInstOperandReplaceType>;
  GlueInstsOperandReplaceTypeMapType GlueInstsOprndReplaceTypeMap;

  // Variable to mark if this clique has its width equal to the number of inputs
  // and has all its inputs available from single element nodes.
  bool AllSingleElementInputGlueNode;

  // Variable to makrthe information that second input was expanded for
  // codegen use.
  bool WasSecondInputExpanded = false;

  // Variables for vectorcode gen.
  //
  // List to store the distict indices for a reduction clique which is a
  // candidate for combining.
  SmallVector<int32_t, 4> CombineRedIndices;

  // The vectorized value generated for this clique.
  Value *VectorizedValue = nullptr;

  // For a clique, we will create permutations of it based on its input values
  // only once. Refer to comments in enum class PermStateType for more info
  PermStateType PermState;

  // For cliques whose width is not a power of 2, we can
  // either pad them or split them. This variable is used to indicate if the
  // clique has been padded or not.
  bool isPadded;

  // Add an input value for a row. Note that if there already exists a row the
  // new value will be appended to that.
  void addInputValForRow(uint32_t RowNum, InputRowType IR) {
    // Check if there already exists a row.
    if (InputRowsMap.count(RowNum) == 0) {
      // Make the unique_ptr.
      auto InputRowPtr = std::make_unique<InputRowsType>(InputRowsType{IR});
      // Move it to the map.
      InputRowsMap[RowNum] = std::move(InputRowPtr);
      // Increment the number of input rows.
      NumInputRows++;
      return;
    }
    // If the row exits, append Operand to it.
    InputRowsMap[RowNum]->push_back(IR);
    return;
  }
public:
  // This constructor will be used when creating a dummy root node for a
  // CliqueDAG.
  explicit Clique(CliqueIDType CliqueId_, GSLPUtil *GSLPU_): GSLPU(GSLPU_) {
    // Unique ID for this clique in the CliqueDAG
    CliqueId = CliqueId_;
    // Set the vector factor as uncomputed.
    VF = -1;
    // Set clique width as uncomputed
    CliqueWidthInBits = -1;
    // Cost is yet to be computed.
    CostComputed = false;
    // Set the uncomputed cost as 0.
    Cost = 0;
    // Set the uncomputed cost as 0.
    LiveOutCost = 0;
    // Reset the clique rows.
    CliqueRows.clear();
    // Reset the input rows.
    InputRowsMap.clear();
    // Num of rows in this clique is initialized to zero
    NumRows = 0;
    // Num of input rows in this clique is initialized to zero
    NumInputRows = 0;
    // Reset the input nodes
    InputClqNodes.clear();
    // Actual number of input node used for a glue node.
    NumUsedInputNodes = 0;
    // Reset the output nodes
    OutputClqNodes.clear();
    // Reset the Mem-Dep input nodes
    MemDepInputClqNodes.clear();
    // Reset the Mem-Dep output nodes
    MemDepOutputClqNodes.clear();
    // Reset the ReachesSet set
    NodesReachesCurrSet.clear();
    // Reset the ReachableSet set
    NodesReachableFrCurrSet.clear();
    // Initialize variable to mark if this clique is connected to DummyRoot of
    // the CliqueDAG.
    ConnectedToDummyRoot = false;
    // Initialize that this clique is not connected to external values.
    HasExternalVal = false;
    HasAllExternalVal = false;
    // Clear the intermidiate glue instructions list.
    IntermediateGlueInsts.clear();
    // Clear the operand number replacement types.
    GlueInstsOprndReplaceTypeMap.clear();
    // Initialize the variable which marks if this clique has its width equal to
    // the number of inputs and has all its inputs available from single element
    // nodes.
    AllSingleElementInputGlueNode = false;
    // Initailize that second input was not expanded.
    WasSecondInputExpanded = false;
    // Initialize the glue instruction.
    GlueInst = nullptr;
    // Initialize vectorized value.
    VectorizedValue = nullptr;
    // Mark that no permutation has been created
    PermState = Clique::PermStateType::NoPermCreated;
    // Initialize that we haven't generated tree based glue instructions.
    HasTreeBasedGlues = false;
    // Mark that the clique has not been padded
    isPadded = false;
  }
  // The following constructors are deleted to prevent copying one clique to
  // another. We are allowing to pass the objects of this class only through
  // unique_ptr. Only std::move is allowed.
  Clique(const Clique&) = delete;
  Clique& operator=(const Clique&) = delete;
  ~Clique() = default;
  // Construct the clique. This constructor is used when a clique is created
  // from CGNodes using the function HierCompatibilityGraph::buildCliques.
  Clique(CompatibilityGraph *CG_, KindType K_, CliqueNodeType CliqueNodes_,
         uint32_t Level_, GSLPUtil *GSLPU_) : CG(CG_), Kind(K_),
        Level (Level_), GSLPU (GSLPU_) {
    // Set the vector factor as uncomputed.
    VF = -1;
    // Set clique width as uncomputed
    CliqueWidthInBits = -1;
    // Cost is yet to be computed.
    CostComputed = false;
    // Set the uncomputed cost as 0.
    Cost = 0;
    // Set the uncomputed cost as 0.
    LiveOutCost = 0;
    // Reset the clique rows.
    CliqueRows.clear();
    // Reset the input rows.
    InputRowsMap.clear();
    // Num of rows in this clique is initialized to zero
    NumRows = 0;
    // Num of input rows in this clique is initialized to zero
    NumInputRows = 0;
    // Reset the input nodes
    InputClqNodes.clear();
    // Actual number of input node used for a glue node.
    NumUsedInputNodes = 0;
    // Reset the output nodes
    OutputClqNodes.clear();
    // Reset the Mem-Dep input nodes
    MemDepInputClqNodes.clear();
    // Reset the Mem-Dep output nodes
    MemDepOutputClqNodes.clear();
    // Reset the ReachesSet set
    NodesReachesCurrSet.clear();
    // Reset the ReachableSet set
    NodesReachableFrCurrSet.clear();
    // Initialize variable to mark if this clique is connected to DummyRoot of
    // the CliqueDAG.
    ConnectedToDummyRoot = false;
    // Initialize that this clique is not connected to external values.
    HasExternalVal = false;
    HasAllExternalVal = false;
    // Clear the intermidiate glue instructions list.
    IntermediateGlueInsts.clear();
    // Clear the operand number replacement types.
    GlueInstsOprndReplaceTypeMap.clear();
    // Add nodes after all the data structures have been cleared.
    addNodes(CliqueNodes_);
    // Initialize the variable which marks if this clique has its width equal to
    // the number of inputs and has all its inputs available from single element
    // nodes.
    AllSingleElementInputGlueNode = false;
    // Initailize that second input was not expanded.
    WasSecondInputExpanded = false;
    // Initialize the glue instruction.
    GlueInst = nullptr;
    // Initialize vectorized value.
    VectorizedValue = nullptr;
    // Mark that no permutation has been created
    PermState = Clique::PermStateType::NoPermCreated;
    // Initialize that we haven't generated tree based glue instructions.
    HasTreeBasedGlues = false;
     // Mark that the clique has not been padded
    isPadded = false;
  }
  // Construct the clique. This constructor is used when a clique is created
  // from CliqueInstMatrix while splitting the clique in
  // CliqueDAG::generateSubCliques.
  Clique(CompatibilityGraph *CG_, KindType K_,
         InstsInCliqueType CliqueInstMatrix_, uint32_t Level_,GSLPUtil *GSLPU_)
         : CG(CG_),Kind(K_), Level (Level_), GSLPU (GSLPU_) {
    // Set the vector factor as uncomputed.
    VF = -1;
    // Set clique width as uncomputed
    CliqueWidthInBits = -1;
    // Cost is yet to be computed.
    CostComputed = false;
    // Set the uncomputed cost as 0.
    Cost = 0;
    // Set the uncomputed cost as 0.
    LiveOutCost = 0;
    // Reset the clique rows.
    CliqueRows.clear();
    // Reset the input rows.
    InputRowsMap.clear();
    // Num of rows in this clique is initialized to zero
    NumRows = 0;
    // Num of input rows in this clique is initialized to zero
    NumInputRows = 0;
    // Reset the input nodes
    InputClqNodes.clear();
    // Actual number of input node used for a glue node.
    NumUsedInputNodes = 0;
    // Reset the output nodes
    OutputClqNodes.clear();
    // Reset the Mem-Dep input nodes
    MemDepInputClqNodes.clear();
    // Reset the Mem-Dep output nodes
    MemDepOutputClqNodes.clear();
    // Reset the ReachesSet set
    NodesReachesCurrSet.clear();
    // Reset the ReachableSet set
    NodesReachableFrCurrSet.clear();
    // Initialize variable to mark if this clique is connected to DummyRoot of
    // the CliqueDAG.
    ConnectedToDummyRoot = false;
    // Initialize that this clique is not connected to external values.
    HasExternalVal = false;
    HasAllExternalVal = false;
    // Clear the intermidiate glue instructions list.
    IntermediateGlueInsts.clear();
    // Clear the operand number replacement types.
    GlueInstsOprndReplaceTypeMap.clear();
    // Add nodes after all the data structures have been cleared.
    addNodes(CliqueInstMatrix_);
    // Initialize the variable which marks if this clique has its width equal to
    // the number of inputs and has all its inputs available from single element
    // nodes.
    AllSingleElementInputGlueNode = false;
    // Initailize that second input was not expanded.
    WasSecondInputExpanded = false;
    // Initialize the glue instruction.
    GlueInst = nullptr;
    // Initialize vectorized value.
    VectorizedValue = nullptr;
    // Mark that no permutation has been created
    PermState = Clique::PermStateType::NoPermCreated;
    // Initialize that we haven't generated tree based glue instructions.
    HasTreeBasedGlues = false;
     // Mark that the clique has not been padded
    isPadded = false;
  }
  // This constructor is used when the clique is generated from another clique.
  // while creating nodes in CliqueDAG, using the function
  // HierCompatibilityGraph::buildSetPartition. This clique will just have a
  // single row \param VecRow_. The CG and level of the clique is irrelevent
  // here. The kind for this clique may change from Memory to other kinds when
  // we have single row cliques.
  Clique(CliqueIDType CliqueId_, KindType K_, VecRowType VecRow_,
         Clique::CliqueDAGNodeType NodeType, GSLPUtil *GSLPU_)
        : Kind(K_), ClqDAGNodeType(NodeType), GSLPU(GSLPU_) {
    // Unique ID for this clique in the CliqueDAG
    CliqueId = CliqueId_;
    // Reset the clique rows.
    CliqueRows.clear();
    // Reset the input rows.
    InputRowsMap.clear();
    // Num of rows in this clique is initialized to zero
    NumRows = 0;
    // Num of input rows in this clique is initialized to zero
    NumInputRows = 0;
    // Reset the input nodes
    InputClqNodes.clear();
    // Actual number of input node used for a glue node.
    NumUsedInputNodes = 0;
    // Reset the output nodes
    OutputClqNodes.clear();
    // Reset the Mem-Dep input nodes
    MemDepInputClqNodes.clear();
    // Reset the Mem-Dep output nodes
    MemDepOutputClqNodes.clear();
    // Reset the ReachesSet set
    NodesReachesCurrSet.clear();
    // Reset the ReachableSet set
    NodesReachableFrCurrSet.clear();
    // Add VecRow_ as its single row. This should set the number of rows as
    // 1 too.
    addNodes(VecRow_);
    // Set the width of the clique as width of VecRow_.
    Width = VecRow_.size();
    Level = 0;
    // Set the vector factor as uncomputed.
    VF = -1;
    // Set clique width as uncomputed.
    CliqueWidthInBits = -1;
    // Cost is yet to be computed.
    CostComputed = false;
    // Set the uncomputed cost as 0.
    Cost = 0;
    // Set the uncomputed cost as 0.
    LiveOutCost = 0;
    // Create the vector type for this row. This is useful while generating
    // the glue instructions and vector instructions.
    VectorTypesMap.clear();
    createVectorTypes();
    // Set the insert point after which the glue/vector instructions have to be
    // inserted. This is done in the constructor as we will need to use this at
    // many places.
    setInsertPointAndLiveoutValIndices();
    // Initialize variable to mark if this clique is connected to DummyRoot of
    // the CliqueDAG.
    ConnectedToDummyRoot = false;
    // Initialize that this clique is not connected to external values.
    HasExternalVal = false;
    HasAllExternalVal = false;
    // Clear the intermidiate glue instructions list.
    IntermediateGlueInsts.clear();
    // Clear the operand number replacement types.
    GlueInstsOprndReplaceTypeMap.clear();
    // Initialize the variable which marks if this clique has its width equal to
    // the number of inputs and has all its inputs available from single element
    // nodes.
    AllSingleElementInputGlueNode = false;
    // Initailize that second input was not expanded.
    WasSecondInputExpanded = false;
    // Initialize the glue instruction.
    GlueInst = nullptr;
    // Initialize vectorized value.
    VectorizedValue = nullptr;
    // Mark that no permutation has been created
    PermState = Clique::PermStateType::NoPermCreated;
    // Initialize that we haven't generated tree based glue instructions.
    HasTreeBasedGlues = false;
    // Mark that the clique has not been padded
    isPadded = false;
  }

  // Get the unique clique id in the CliqueDAG.
  CliqueIDType getCliqueId() { return CliqueId; }
  // Add the CGNode to the clique
  void addNode(CGNodeIDType CGNodeId) {
    CliqueNodes.push_back(CGNodeId);
    // This increments the width of the clique.
    Width++;
  }
  // Add a clique from a vector for CGNodes.
  void addNodes(CliqueNodeType);
  // Add a clique from a matrix of instructions.
  void addNodes(InstsInCliqueType);
  // Add a clique from a single row of values.
  void addNodes(VecRowType);
  // Get the width of the clique.
  uint32_t getWidth() { return Width; }
  // Return the list of nodes in this clique.
  CliqueNodeType getCliqueNodes() { return CliqueNodes; }
  // Return the vector of instructions in this clique.
  InstsInCliqueType getCliqueInstsMatrix() { return CliqueInstsMatrix; }
  // Get the level of the CG from which this clique is the generated. That
  // essentially is defined as the level of this clieque too.
  uint32_t getLevel() { return Level; }
  // Get the compatibility graph from which this clique is created.
  CompatibilityGraph *getCG() { return CG; }
  // Get the kind of the clique.
  enum KindType getKind() { return Kind; }
  // Check if this is an arithmatic clique.
  bool isArithmetic() {
    return Kind == KindType::Arithmetic;
  }
  // Check if this is a memory clique
  bool isMemory() { return Kind == KindType::Memory; }
  // Check if this is a reduction clique
  bool isReduction() { return Kind == KindType::Reduction; }
  // Get the VF for this clique.
  int32_t getVF() { return VF; }
  // Set the VF for this clique.
  void setVF(int32_t VF_) { VF = VF_; }
  // Return if the cost is computed or not.
  bool isCostComputed() { return CostComputed; }
  // Mark that cost is computed or not.
  void setCostComputed(bool Computed_) { CostComputed = Computed_; }
  // Get the estimated execution cost improvement due to vectorization of the
  // clique w.r.t., the scalar input.
  InstructionCost getCost();
  // Compute the cost of generataing extractelement instructions for the values
  // which are live outside the current block. Note that here we are not gener-
  // ating the actual extractelement instructions, but just add a cost of 1 for
  // each extractelement. We will generate those during codegen at appropriate
  // places. Then the liveout cost is nothing but the number of indices present
  // for \param RowNum in LiveOutValIndicesMap, which we had initialized while
  // creating this clique.
  InstructionCost getLiveoutValuesCost() {
    return LiveOutValIndicesMap[0/*RowNum*/].size();
  }
  // Compute the minimum vector factor (VF) for this clique. The Minimum VF of
  // a clique is determined by the largest datatype in the use-def chain of a
  // node in this claique.
  uint32_t computeMinVF();
  // Set the cost.
  void setCost(InstructionCost Cost_) {
    Cost = Cost_;
    setCostComputed(true);
  }
  // Set the live out cost.
  void setLiveoutCost(InstructionCost Cost_) {
    LiveOutCost = Cost_;
  }
  // Get the live out cost.
  InstructionCost getLiveoutCost() {
    return LiveOutCost;
  }
  // Return the rows of this clique.
  CliqueRowsType &getCliqueRows() { return CliqueRows; }
  // Return the input row at index \param RowNum.
  VecRowPtrType &getVecRow(uint32_t RowNum_) {
    return CliqueRows[RowNum_];
  }
  // Return the 0th row of the clique.
  VecRowPtrType &getVecRow() {
    return CliqueRows[0];
  }
  // Append a vector row to the clique rows. Note that the parameter is not a
  // reference as we need a copy to be stored.
  void addVectorRow(VecRowPtrType VecRowPtr_) {
    // Make the unique_ptr.
    //ArrayRef<Instruction*> VecRowArrayRef = VecRow_;
    //auto VecRowPtr = std::make_unique<VecRowType>(VecRow_);
    CliqueRows.push_back(std::move(VecRowPtr_));
    // Increment the number of rows.
    NumRows++;
  }
  // Get the scalar value at a particular row and column.
  Value *getScalarVal(uint32_t RowNum, uint32_t ColNum) {
    auto &VecRowPtr = CliqueRows[RowNum];
    Value *ScalarVal = (*VecRowPtr)[ColNum];
    return ScalarVal;
  }
  // Get the scalar value at row 0 and column ColNum.
  Value *getScalarVal(uint32_t ColNum) {
    auto &VecRowPtr = CliqueRows[0];
    Value *ScalarVal = (*VecRowPtr)[ColNum];
    return ScalarVal;
  }

  // Check if a row 0 contains any GEP. If yes, return that. This is useful
  // during vector codegen for load and store cliques, where we store the base
  // address of this clique as the vectorized value.
  GetElementPtrInst *getGEPInstIfAny() {
    auto &VecRowPtr = CliqueRows[0];
    for (Value *V : *VecRowPtr) {
      if (!V->getType()->isPointerTy())
        return nullptr;
      if (auto *GEPInst = dyn_cast<GetElementPtrInst>(V))
        return GEPInst;
    }
    return nullptr;
  }
  // Check if a row 0 contains any GEP. If yes, return true. This is useful
  // during glue instructions generation, to ignore that glue node. Such a glue
  // node will be handled during codegen.
  bool hasAllNonGEPPointers() {
    auto &VecRowPtr = CliqueRows[0];
    for (Value *V : *VecRowPtr) {
      if (!V->getType()->isPointerTy())
        return false;
      if (isa<GetElementPtrInst>(V))
        return false;
    }
    return true;
  }
  // Check if a row 0 contains any GEP. If yes, return true. This is useful
  // during glue instructions generation, to ignore that glue node. Such a glue
  // node will be handled during codegen.
  bool hasAnyGEPInst() {
    auto &VecRowPtr = CliqueRows[0];
    for (Value *V : *VecRowPtr) {
      if (!V->getType()->isPointerTy())
        return false;
      if (auto *GEPInst = dyn_cast<GetElementPtrInst>(V))
        return true;
    }
    return false;
  }
  // Check if a row 0 contains any GEP. If yes, return the pointer value of the
  // column 0. We may return either a ptr or a GEP.
  Value *getBasePtrOrBaseGEP() {
    if (!hasAnyGEPInst())
      return nullptr;
    auto &VecRowPtr = CliqueRows[0];
    auto *PtrOrGEP = (*VecRowPtr)[0];
    // If the gep is indexing to the first element (gep index is 0) return its
    // pointer operand.
    if (auto *GEPInst = dyn_cast<GetElementPtrInst>(PtrOrGEP)) {
      if (GEPInst->hasAllZeroIndices()) {
        return GEPInst->getPointerOperand();
      }
    }
    return PtrOrGEP;
  }
  // Check if the the clique row contains a GEPOperator similar to
  // ptr getelementptr inbounds (%struct.anon, ptr @pughpriv, i64 0, i32 50)
  bool hasGEPOperator() {
    Value *V = getFirstValue();
    return isa<ConstantExpr>(V) && isa<GEPOperator>(V);
  }
  // Check if this node is a singleton vector node with a GEP.
  bool isSingleElementGEP() {
    Value *V = getFirstValue();
    return isa<GetElementPtrInst>(V);
  }
  // Check if this is the DummyRoot.
  bool isDummyRoot() {
    return getCliqueId() == 0;
  }

  // Check if the the clique row contains a any GEPOperator similar to
  // ptr getelementptr inbounds (%struct.anon, ptr @pughpriv, i64 0, i32 50)
  bool hasAnyGEPOperator() {
    auto &VecRowPtr = CliqueRows[0];
    for (Value *V : *VecRowPtr) {
      if (!V->getType()->isPointerTy())
        return false;
      if (isa<ConstantExpr>(V) && isa<GEPOperator>(V))
        return true;
    }
    return false;
  }

  // Check if this is a memory clique and if yes check we the \param InputNum
  // corresponds to the pointer operand.
  bool isPointerOperandToMemoryClique(int32_t InputNum) {
    Instruction *LoadOrStore = dyn_cast<Instruction>(getFirstValue());
    // If this is a load instruction, as it has one operand this should be the
    // pointer operand.
    if (isa<LoadInst>(LoadOrStore))
      return true;
    // If it is a store instruction InputNum should be 1 for it top be pointer
    // operand.
    return isa<StoreInst>(LoadOrStore) && InputNum == 1;
  }
  // Check if this is  a clique with a single element which is a pointer,
  // which is not an instruction in the current block.
  bool isSinglePtrFromOutside(BasicBlock *BB) {
    if (!(getWidth() == 1 || getKind() == KindType::Reduction))
      return false;
    auto &VecRowPtr = CliqueRows[0];
    Value *V = (*VecRowPtr)[0];
    // It should be a pointer type.
    if (!(V->getType()->isPointerTy()))
      return false;
    // If this is an instruction it should be defined outside this block.
    Instruction *I = dyn_cast<Instruction>(V);
    if (I && I->getParent() == BB)
      return false;
    return true;
  }
  // Check if this is  a clique with a single element which is a pointer.
  bool isSingleElementPtr() {
    if (!(getWidth() == 1 || getKind() == KindType::Reduction))
      return false;
    auto &VecRowPtr = CliqueRows[0];
    Value *V = (*VecRowPtr)[0];
    return V->getType()->isPointerTy();
  }
  // Check if this is a clique with a single meta data in it.
  bool isSingleMetadata() {
    if (getWidth() != 1)
      return false;
    auto &VecRowPtr = CliqueRows[0];
    Value *V = (*VecRowPtr)[0];
    return V->getType()->isMetadataTy();
  }

  // Check if this is a clique with a single value with aggregate type
  // (insertvalue, extractvalue).
  bool isSingleAggregateType() {
    if (getWidth() != 1)
      return false;
    auto &VecRowPtr = CliqueRows[0];
    Value *V = (*VecRowPtr)[0];
    return V->getType()->isAggregateType();
  }

  // Get the single element which is a pointer.
  Value *getSingleElementPtr() {
    if (getWidth() != 1)
      return nullptr;
    auto &VecRowPtr = CliqueRows[0];
    Value *V = (*VecRowPtr)[0];
    if (V->getType()->isPointerTy())
      return V;
    return nullptr;
  }
  // Check if this is a single element clique.
  bool isSingleElement() {
    return (getWidth() == 1) && (CliqueRows.size() == 1)
        || (getKind() == KindType::Reduction); // Generates a scalar as output
  }
  // Check if this is a single element node connted to DummyRoot.
  bool hasSingleElementConnectedToDummyRoot() {
    return isSingleElement() && isConnectedToDummyRoot();
  }
  // Get the first Value in the clique.
  Value *getFirstValue() {
    auto &VecRowPtr = CliqueRows[0];
    Value *V = (*VecRowPtr)[0];
    return V;
  }
  // Check if all input nodes are of are single element.
  bool checkIfAllSingleElementInputs() {
    uint32_t NumInputNodes = getNumInputNodes();
    // Check if we have number of input nodes equal to the width of the glue
    // node. Otherwise we don't have all inputs to be single element.
    if (getWidth() != NumInputNodes)
      return false;
    for (auto &InputClqNodePtr : getInputNodes()) {
      // Skip reduction clique's input since it generates a scalar value.
      if (InputClqNodePtr->getKind() == Clique::KindType::Reduction)
        continue;
      if (InputClqNodePtr->getWidth() != 1) {
        return false;
      }
    }
    return true;
  }
  // Mark if this clique has its width equal to the number of inputs and has all
  // its inputs available from single element nodes.
  void markAsAllSingleElementInputGlueNode() {
    AllSingleElementInputGlueNode = true;
  }
  // Check if this clique has its width equal to the number of inputs and has all
  // its inputs available from single element nodes.
  bool isAllSingleElementInputGlueNode() {
    return AllSingleElementInputGlueNode;
  }
  // Correct the input order to align to the order in the glue node. This is
  // required due to the optmization that we did in addGlueNodeInputs to
  // prioritize vector nodes over glue nodes to create glue instructions.
  void reorderAllSingleExternalInteralMixedInputs();
  // Creates vector types for each row. This will help in creating vector
  // instructions (extracts, inserts, shuffles and vector) from this. Note that
  // the vector size is always Powerof2Ceil of the actaul width of the row.
  void createVectorTypes() {
    for (uint32_t RowNum = 0; RowNum < NumRows; RowNum++) {
      auto &VecRowPtr = CliqueRows[RowNum];
      Value *ScalarVal = (*VecRowPtr)[0];
      // Get the scalar Type;
      Instruction *ScalarInst = dyn_cast<Instruction>((*VecRowPtr)[0]);
      Type *ScalarTy = nullptr;
      if (ScalarInst) {
        if(ScalarInst->getOpcode() != Instruction::Store)
          ScalarTy = ScalarInst->getType();
        else
          // Store is special.
          ScalarTy = dyn_cast<StoreInst>(ScalarInst)
                                        ->getValueOperand()->getType();
      } else {
        // Argument, constant, etc.
        ScalarTy = ScalarVal->getType();
      }
      // Cannot have vector types for structure or arrays.
      if (ScalarTy->isAggregateType())
        continue;
      // Cannot have vector types for metadata.
      if (ScalarTy->isMetadataTy())
        continue;
      // Void type cannot be types in a vector.
      if (ScalarTy->isVoidTy())
        continue;
      // Ignore if the scalar type is not a valid element type for vector types
      if (!VectorType::isValidElementType(ScalarTy)) 
        continue;
      // If the value is a basic block nothing more to do.
      if (isa<BasicBlock>(ScalarVal))
        continue;
      uint32_t VecSize = PowerOf2Ceil(getWidth());
      // If VecSize is 1, we should make it 2 as vector size of 1 is
      // unreasonable. Note that reduction clique only generates a single,
      // scalar value.
      if (VecSize == 1 || Kind == KindType::Reduction) VecSize = 2;
      // Create the vector type.
      VectorType *VecTy = FixedVectorType::get(ScalarTy, VecSize);
      VectorTypesMap[RowNum] = VecTy;
    }
  }
  // Get the vector type for a row.
  VectorType *getVectorType(uint32_t RowNum) { return VectorTypesMap[RowNum]; }
  // Get the vector type for a row. if no paramenter is given, return the type
  // of first row.
  VectorType *getVectorType() { return VectorTypesMap[0]; }
  // Add the index of the live out value.
  void addLiveoutValueIndex(Value *V, uint32_t RowNum, int32_t LiveOutValIndex,
                            SmallPtrSet <Value *, 4> &ValuesToBeExtracted, 
                            BasicBlock *BB) {
    for (User *U : V->users()) {
      Instruction *I = dyn_cast<Instruction>(U);
      // FIXME: Not sure if we have to deal with other types of users. For now
      // lets assert if its not an instruction.
      assert(I && "Expecting Instruction as a user\n");
      // No need to add indices for a value for which an index is already added.
      if (I && I->getParent() != BB && !ValuesToBeExtracted.contains(V)) {
        ValuesToBeExtracted.insert(V);
        DEBUG_WITH_TYPE(VerboseDebugLevel5,
                        dbgs() << "    Value used outside the block: " << *V
                               << " in " << *I << "\n");
        LiveOutValIndicesMap[RowNum].push_back(LiveOutValIndex);
      }
    }
  }
  // Get the live out value indices.
  LiveOutValsIndicesType getLiveoutValueIndices() {
    return LiveOutValIndicesMap[/*RowNum*/0];
  }
  // Set insert point for the glue/vector instructions created.
  void setInsertPointAndLiveoutValIndices() {
    BasicBlock *BB = GSLPU->getBB();
    for (uint32_t RowNum = 0; RowNum < NumRows; RowNum++) {
      auto &VecRowPtr = CliqueRows[RowNum];
      // Initialize to the start of the basic block
      Instruction *InsertPoint = BB->getFirstNonPHI();
      // Live out value index
      int32_t LiveOutValIndex = -1;
      // Clear out the live out value indices for this row.
      LiveOutValIndicesMap[RowNum].clear();
      // This is a local storage to check for duplicates. We don't need to
      // create extracts for duplicate values which are used live out in a
      // vector row.
      SmallPtrSet <Value *, 4> ValuesToBeExtracted;
      for (Value *V : *VecRowPtr) {
        // Increment live out value index.
        LiveOutValIndex++;
        Instruction *I = dyn_cast<Instruction>(V);
        // If it is not an instruction no need to update the insert point. This
        // will include constants and arguments too.
        if (!I) continue;
        // If the value is coming from outside the block no need to update
        // insert point.
        if (I->getParent() != BB)
          continue;
        // If I is coming after the current insert point update it to I.
        if (InsertPoint->comesBefore(I))
          InsertPoint = I;
        // Store indices of live out values if this is a vector node.
        //
        if (isVectorNode())
          addLiveoutValueIndex(V, RowNum, LiveOutValIndex,
                               ValuesToBeExtracted, BB);
      }
      // Store the insert point.
      InsertPointMap[RowNum] = InsertPoint;
    }
  }
  // Get the insert point for glue/vector instructions.
  Instruction *getInsertPoint(uint32_t RowNum) {
    return InsertPointMap[RowNum];
  }
  // Set the insertpoint to a specific instruction.
  void setInsertPoint(Instruction *I) {
    InsertPointMap[0/*RowNum*/] = I;
  }
  // Get the insert point for glue/vector instructions. If no paramenter is
  // given, return the insert point of first row.
  Instruction *getInsertPoint() { return InsertPointMap[0/*RowNum*/]; }
  // Undate insert point as the latest instruction among the operands and
  // vectorized values of memory inputs.
  void updateInsertPoint(SmallVector<Value *, 4> &OperandsToVecInst) {
    DEBUG_WITH_TYPE(DebugCodegen, dbgs() << "     Updating InsertPoint:\n"
                                         << "     ---------------------\n");
    // Get the current insert point, which is the latest among the scalar inst-
    // ructions which form this clique.
    Instruction *InsertPoint = getInsertPoint();
    DEBUG_WITH_TYPE(DebugCodegen, dbgs() << "     Current InsertPoint: "
                                         << *InsertPoint << "\n");
    // The insert point should be after all its operands.
    for (Value *Operand : OperandsToVecInst) {
      Instruction *OperandI = dyn_cast<Instruction>(Operand);
      // Operand should be an instruction.
      if (!OperandI)
        continue;
      DEBUG_WITH_TYPE(DebugCodegen, dbgs() << "     Oparand: "
                                           << *Operand << "\n");
      // OperandI should be in the current block.
      if (OperandI->getParent() != GSLPU->getBB())
        continue;
      // Move to the lastest operand's position.
      if (InsertPoint->comesBefore(OperandI)) {
        InsertPoint = OperandI;
        DEBUG_WITH_TYPE(DebugCodegen, dbgs() << "     Updated InsertPoint: "
                                             << *InsertPoint << "\n");
      }
    }

    DEBUG_WITH_TYPE(DebugCodegen, dbgs() << "      Checking memory inputs\n");
    // Update the insert point according to the memory input.
    for (auto &MemInputClqPtr : getMemDepInputNodes()) {
      Value *MemInputVecVal = MemInputClqPtr->getVectorizedValue();
      assert (MemInputVecVal &&
              "Expected vec val for mem input. There can be a cycle here");
      DEBUG_WITH_TYPE(DebugCodegen,
                      dbgs() << "       " << *MemInputVecVal << "\n");
      Instruction *MemInputVecValI = dyn_cast<Instruction>(MemInputVecVal);
      assert (MemInputVecValI && "Expected to find vec val for mem input");
      DEBUG_WITH_TYPE(DebugCodegen,
                      dbgs() << "     Mem input: "
                             << MemInputClqPtr->getCliqueId();
                      dbgs() << " VecVal = " << *MemInputVecValI << "\n");
      if (InsertPoint->comesBefore(MemInputVecValI)) {
        InsertPoint = MemInputVecValI;
        DEBUG_WITH_TYPE(DebugCodegen,
                        dbgs() << "     Updated InsertPoint due to mem input: "
                               << *InsertPoint << "\n");
      }
    }

    // Store the insert point.
    InsertPointMap[/*RowNum*/0] = InsertPoint;
    return;
  }
  // Generate input row for a particular row RowNum.
  void generateInputRow(uint32_t RowNum, VecRowType &VecRow);
  // Generate input row for a reduction clique.
  void generateRedInputRow(uint32_t RowNum, VecRowType &VecRow);

  // Additional cost of scalar additions is incurred when a reduction clique
  // is split into mulitiple cliques. This is the cost for all those additions
  // of splitted reduction's outputs.
  InstructionCost costSplitOverhead() {
    assert(getKind() == KindType::Reduction && "Invalid clique type.");
    // Each split clique row's result is added into the previous one, except
    // for the first row.
    uint32_t NumOverheadAdd = NumRows - 1;
    // No cost incurred for a single reduction clique.
    if (NumOverheadAdd == 0)
      return 0;
    TargetTransformInfo *TTI = GSLPU->getTTI();
    VecRowPtrType &Row = getVecRow();
    Type *ScalarTy = (*Row)[0]->getType();
    uint32_t RdxOpcode = RecurrenceDescriptor::getOpcode(llvm::RecurKind::Add);
    InstructionCost OverheadAddCost =
        TTI->getArithmeticInstrCost(RdxOpcode, ScalarTy) * NumOverheadAdd;
    return OverheadAddCost;
  }
  // Add an input row.
  void addInputRow(uint32_t RowNum, uint32_t NumOperands,
                   InputRowsType InputRow) {
    auto InputRowPtr = std::make_unique<InputRowsType>(InputRow);
    // Move it to the map.
    InputRowsMap[RowNum] = std::move(InputRowPtr);
    // Increment the number of input rows.
    NumInputRows++;
  }
  // Check if the clique has any input in a row.
  bool hasInput(uint32_t RowNum) {
    // It is enough to check if there are any sub rows.
    return getNumSubInputRows(RowNum) != 0;
  }
  // Return the input row for a paritcular row RowNum, if it has input.
  InputRowPtrType &getInputRow(uint32_t RowNum) {
    return InputRowsMap[RowNum];
  }
  // Return the number of rows in this clique.
  uint32_t getNumRows() { return NumRows; }
  // Return the number of input rows in a row of the clique.
  uint32_t getNumSubInputRows(uint32_t RowNum) {
    if (InputRowsMap.count(RowNum) == 0)
      return 0;
    return (*InputRowsMap[RowNum]).size();
  }
  // Return the number of input rows in a row of the clique. This can be
  // invoked with single row cliques.
  uint32_t getNumSubInputRows() {
    if (InputRowsMap.count(/*RowNum*/0) == 0)
      return 0;
    return (*InputRowsMap[/*RowNum*/0]).size();
  }
  // Get the number of instructions in this clique.
  uint32_t getNumInsts() {
    uint32_t NumInsts = 0;
    for (VecRowPtrType &VecRow: CliqueRows)
      NumInsts += (*VecRow).size();
    return NumInsts;
  }
  // Return the number of input rows in this cique.
  uint32_t getNumInputRows() { return NumInputRows; }
  // Get the input row corresponding to operand \param OpNum from an input row
  // \param RowNum.
  InputRowType getInputRowForOpNum(uint32_t RowNum, uint32_t OpNum) {
    InputRowsType InputRows = *InputRowsMap[RowNum];
    return InputRows[OpNum];
  }
  // Use this for single row clique.
  InputRowType getInputRowForOpNum(uint32_t OpNum) {
    return getInputRowForOpNum(/*RowNum*/0, OpNum);
  }
  // Clear the input rows map.
  void clearInputRowsMap() {
    InputRowsMap.clear();
  }
  // Copy input rows from \param ClqNodePtr.
  void copyInputRowsMap(InputClqNodeShrdPtrType ClqNodePtr) {
    NumInputRows = 0;
    for (uint32_t OpNum = 0; OpNum < ClqNodePtr->getNumSubInputRows();
         OpNum++) {
      InputRowType OrigInputRow = ClqNodePtr->getInputRowForOpNum(0, OpNum);
      InputRowType InputRow;
      for (Value *V : OrigInputRow) {
        InputRow.push_back(V);
      }
      addInputValForRow(0, InputRow);
    }
    return;
  }

  // Add an input clique node for this clique.
  void addInputClqNode(InputClqNodeShrdPtrType InputClqNodeShrdPtr) {
    // Since we have moved the implementation to SmallVector, it is possible to
    // add same value multiple times. It is already observed to be happening
    // for glue nodes from addGlueNodeInputs function. Either we should change
    // the implementation or fix all the places where inputs are being updated
    // multiple times. For now, don't add the input that is already available.
    /// TODO: Find a better way of checking and implementing this.
    if (std::find(InputClqNodes.begin(),
                  InputClqNodes.end(), InputClqNodeShrdPtr)
        != InputClqNodes.end())
      return;
    InputClqNodes.push_back(InputClqNodeShrdPtr);
  }
  // Add an input clique node for this clique at an index.
  void addInputClqNode(InputClqNodeShrdPtrType InputClqNodeShrdPtr,
                       int32_t &InsertAt) {
    // Since we have moved the implementation to SmallVector, it is possible to
    // add same value multiple times. It is already observed to be happening
    // for glue nodes from addGlueNodeInputs function. Either we should change
    // the implementation or fix all the places where inputs are being updated
    // multiple times. For now, don't add the input that is already available.
    /// TODO: Find a better way of checking and implementing this.
    if (std::find(InputClqNodes.begin(),
                  InputClqNodes.end(), InputClqNodeShrdPtr)
        != InputClqNodes.end())
      return;
    InputClqNodes.insert(InputClqNodes.begin() + InsertAt, InputClqNodeShrdPtr);
    InsertAt++;
  }

  // Clear the input nodes.
  void clearInputNodes() {
    InputClqNodes.clear();
  }
  // Erase the output node at index \param Index
  void eraseOutputNodeAt(int32_t Index) {
    OutputClqNodes.erase(OutputClqNodes.begin() + Index);
    return;
  }
  // Erase the output node at index \param Index
  void addOutputNodeAt(OutputClqNodeShrdPtrType OutNode, int32_t Index) {
    OutputClqNodes.insert(OutputClqNodes.begin() + Index, OutNode);
    return;
  }

  // We need not use all the input nodes of ClqDAGGlueNodePtr to construct the
  // glue instructions. During codegen, we need to know the actual inputs used.
  // For that we save this actaul inputs used.
  void setNumUsedInputNodes(int32_t NumUsedInputNodes_) {
    NumUsedInputNodes = NumUsedInputNodes_;
  }
  // Get the actual number of input nodes used.
  int32_t getNumUsedInputNodes() {
    return NumUsedInputNodes;
  }
  // Add an output clique node for this clique.
  void addOutputClqNode(OutputClqNodeShrdPtrType OutputClqNodeShrdPtr) {
    // Check if node is already present in the vector.
    if (std::find(OutputClqNodes.begin(),
                  OutputClqNodes.end(), OutputClqNodeShrdPtr)
        != OutputClqNodes.end())
      return;
    OutputClqNodes.push_back(OutputClqNodeShrdPtr);
  }
  // Add a mem-dep input clique node for this clique.
  void addMemDepInputClqNodes(InputClqNodeShrdPtrType InputClqNodeShrdPtr) {
    // Check if node is already present in the vector.
    if (std::find(MemDepInputClqNodes.begin(),
                  MemDepInputClqNodes.end(), InputClqNodeShrdPtr)
        != MemDepInputClqNodes.end())
      return;
    MemDepInputClqNodes.push_back(InputClqNodeShrdPtr);
  }
  // Add a mem-dep output clique node for this clique.
  void addMemDepOutputClqNodes(OutputClqNodeShrdPtrType OutputClqNodeShrdPtr) {
    // Check if node is already present in the vector.
    if (std::find(MemDepOutputClqNodes.begin(),
                  MemDepOutputClqNodes.end(), OutputClqNodeShrdPtr)
        != MemDepOutputClqNodes.end())
      return;
    MemDepOutputClqNodes.push_back(OutputClqNodeShrdPtr);
  }
  // Add the node \param InputClqNodeShrdPtr in ReachesSet of this newly added
  // node. Also, add the ReachesSet of InputClqNodeShrdPtr in the same set for
  // this node as the nodes that reaches InputClqNodeShrdPtr will also reach
  // this node.
  void addToReachesSet(InputClqNodeShrdPtrType InputClqNodeShrdPtr) {
    NodesReachesCurrSet.insert(
      InputClqNodeShrdPtr->NodesReachesCurrSet.begin(),
      InputClqNodeShrdPtr->NodesReachesCurrSet.end());
    NodesReachesCurrSet.insert(InputClqNodeShrdPtr);
  }
  // Add the node \param InputClqNodeShrdPtr in ReachableSet of this newly
  // added node. Also, add the ReachableSet of InputClqNodeShrdPtr in the same
  // set for this node as the nodes that are reachable from InputClqNodeShrdPtr
  // will also be reachable from this node.
  void addToReachableSet(InputClqNodeShrdPtrType InputClqNodeShrdPtr) {
    NodesReachableFrCurrSet.insert(
      InputClqNodeShrdPtr->NodesReachableFrCurrSet.begin(),
      InputClqNodeShrdPtr->NodesReachableFrCurrSet.end());
    NodesReachableFrCurrSet.insert(InputClqNodeShrdPtr);
  }
  // A basic block can be an input value in case of a branch instruction or as
  // parameters to some intrinsics. Check if the first value is a basic block.
  bool isBasicBlockInput() {
    Value *FirstValue = getFirstValue();
    if (isa<BasicBlock>(FirstValue)) {
      return true;
    }
    return false;
  }
  // Check if this clique is a phi node and if the first value in \param
  // OrigInputRow is an incoming value for a phi node.
  bool isIncomingForPhiNodeFromOutside(InputRowType &OrigInputRow) {
    Value *FirstValue = getFirstValue();
    if (!isa<PHINode>(FirstValue))
      return false;
    // Since we do not support vectorizeing phi node, this clique should be of
    // width 1.
    assert(getWidth() == 1 && "Expecting clique width to be 1");
    // Also the size of OrigInputRow should be 1.
    assert(OrigInputRow.size() == 1 && "Size of input row should be 1");
    PHINode *Phi = dyn_cast<PHINode>(FirstValue);
    Value *InVal = OrigInputRow[0];
    Instruction *InValInst = dyn_cast<Instruction>(InVal);
    if (InValInst && InValInst->getParent() != Phi->getParent())
      return true;
    if (isa<Argument>(InVal))
      return true;
    if (isa<GlobalValue>(InVal))
      return true;
    // Now the incoming value is not coming from outside.
    return false;
  }
  // Mark this node as connected to DummyRoot. This is useful later to readily
  // check if the any of the inputs are coming from outside the block.
  void markAsConnectedToDummyRoot() { ConnectedToDummyRoot = true; }
  // Check if the node is connected to the DummyRoot.
  bool isConnectedToDummyRoot() { return ConnectedToDummyRoot; }
  // Store the information that this clique is connected to node having
  // external values. This is usefule in vector codegen. We just have to reuse
  // the glue instruction set during getGlueCost as the vectorized value.
  void setHasExternalVal() { HasExternalVal = true; }
  // Use this to store the information that all value are external.
  void setHasAllExternalVal() { HasAllExternalVal = true; }
  // Get the information that whether this clique is connected to node having
  // external values.
  bool hasExternalValues() { return HasExternalVal; }
  // Check if all the values are external
  bool hasAllExternalValues() { return HasAllExternalVal; }
  // Get the input nodes for a clique node. If no paramter is specified return
  // the inputnodes of 0th row.
  InputClqNodesType& getInputNodes() {
    return InputClqNodes;
  }
  // Get the number of input nodes.
  uint32_t getNumInputNodes() {
    return InputClqNodes.size();
  }
  // Get the output nodes for a clique node. If no paramter is specified return
  // the outputnodes of 0th row.
  OutputClqNodesType& getOutputNodes() {
    return OutputClqNodes;
  }
  // Get mem-dep input nodes for a clique node. If no paramter is specified
  // return the inputnodes of 0th row.
  InputClqNodesType& getMemDepInputNodes() {
    return MemDepInputClqNodes;
  }
  InputClqNodesType getAllInputNodes() {
    InputClqNodesType InputNodes;
    InputNodes.append(InputClqNodes);
    InputNodes.append(MemDepInputClqNodes);
    return InputNodes;
  }
  // Get mem-dep output nodes for a clique node. If no paramter is specified
  // return the inputnodes of 0th row.
  InputClqNodesType& getMemDepOutputNodes() {
    return MemDepOutputClqNodes;
  }
  OutputClqNodesType getAllOutputNodes() {
    OutputClqNodesType OutputNodes;
    OutputNodes.append(OutputClqNodes);
    OutputNodes.append(MemDepOutputClqNodes);
    return OutputNodes;
  }
  // Get the ReachesSet for this clique node.
  ClqNodesSetType& getReachesSet() {
    return NodesReachesCurrSet;
  }
  // Get the ReachableSet for this clique node.
  ClqNodesSetType& getReachableSet() {
    return NodesReachableFrCurrSet;
  }
  Instruction *getFirstInstOrNull() {
    // Clique Rows is empty if a DummyRoot clique calls this function. This is
    // the check for that.
    if (CliqueRows.empty())
      return nullptr;
    Value *Val = (*CliqueRows[0])[0];
    Instruction *I = dyn_cast<Instruction>(Val);
    return I ? I : nullptr;
  }
  // Add the glue instruction. This will be used if this clique turns out to be
  // a glue node in the CliqueDAG. Note that this is the last instruction
  // created in a sequence of shuffle instructions when there are many inputs.
  void addGlueInst(Value *Inst) { GlueInst = Inst; }
  // Get the glue instruction. This will be used if this clique turns out to be
  // be a glue node in the CliqueDAG.
  Value *getGlueInst() { return GlueInst; }
  // In case of multiple shuffle instructions generated we must store those
  // instructions which directly uses the input vectors. Note that GlueInst may
  // also be part of this if it uses the input directly.
  void addToIntermediateGlueInsts(Value *Inst) {
    IntermediateGlueInsts.push_back(Inst);
  }
  // Update the intermediate glue instruction at index \param with a new one
  // \param NewGlueInst.
  void updateIntermediateGlueAt(uint32_t Index, Value *NewGlueInst) {
    IntermediateGlueInsts[Index] = NewGlueInst;
  }
  // Get the list of intermediate glue instructions.
  IntermediateGlueInstsType &getIntermediateGlueInsts() {
    return IntermediateGlueInsts;
  }

  // Set the unique combine indices list to be used while combining reductions
  // using vector addition.
  void setCombineRednIndices(SmallVector<int32_t, 4> Indices) {
    CombineRedIndices = Indices;
  }
  // Get the unique combine indices list to be used while combining reductions
  // using vector addition.
  SmallVector<int32_t, 4>& getCombineRednIndices() {
    return CombineRedIndices;
  }

  // Set of functions to help in determining which operands of a saved glue
  // instruction need to be replaced by the available vectors at codegen.
  void replaceFirstOperandWithPrevInput(Value *V) {
    DEBUG_WITH_TYPE(VerboseDebugLevel3,
        dbgs() << "      Replace first operand with previous input in "
               << *V << "\n");
    GlueInstsOprndReplaceTypeMap.insert(
        std::make_pair(
          V,
          GlueInstOperandReplaceType::ReplaceFirstWithPreviousInput)
        );
  }
  void replaceFirstOperandWithCurrentInput(Value *V) {
    DEBUG_WITH_TYPE(VerboseDebugLevel3,
        dbgs() << "      Replace first operand with current input in"
               << *V << "\n");
    GlueInstsOprndReplaceTypeMap.insert(
        std::make_pair(
          V,
          GlueInstOperandReplaceType::ReplaceFirstWithCurrentInput)
        );
  }
  void replaceSecondWithCurrentInput(Value *V) {
    DEBUG_WITH_TYPE(VerboseDebugLevel3,
        dbgs() << "      Replace second operand with current input in "
               << *V << "\n");
    GlueInstsOprndReplaceTypeMap.insert(
        std::make_pair(
          V,
          GlueInstOperandReplaceType::ReplaceSecondWithCurrentInput)
        );
  }
  void replaceBothOperands(Value *V) {
    DEBUG_WITH_TYPE(VerboseDebugLevel3,
        dbgs() << "      Replace both operands in " << *V << "\n");
    GlueInstsOprndReplaceTypeMap.insert(
        std::make_pair(
          V,
          GlueInstOperandReplaceType::ReplaceBoth)
        );
  }
  // Mark that we have generated glue instructions using the tree based method.
  void setHasTreeBasedGlueInst() { HasTreeBasedGlues = true; }
  // Check if we had generated glue instructions using the tree based method.
  bool hasTreeBasedGlueInsts() { return HasTreeBasedGlues; }
  // Mark the information that second input was expanded for code gen use.
  void setSecondInputWasExpanded() {
    WasSecondInputExpanded = true;
  }
  // Check if the second input was expanded.
  bool hasExpandedSecondInput() {
    return WasSecondInputExpanded;
  }
  GlueInstOperandReplaceType getGlueInstOperandReplaceType(Value *V) {
    return GlueInstsOprndReplaceTypeMap[V];
  }
  // Replace the operands of the glue instruction with the corresponding
  // available vectorized values according to the replace type.
  // TODO: Cleanup this function.
  void replaceGlueOperandsWithAvailableValues(
    Instruction *IntermediateGlueInst, Value *CurrInputVecVal,
    Value *PrevInputVecVal) {

    // Note that if the IntermediateGlueInst is a shuffle (not an insertelement)
    // CurrInputVecVal or PrevInputVecVal should be of vector type. If they are
    // not vector type, we don't make the placement. They can be a scalar if
    // their corresponding input nodes are of single element. This check is
    // made using isShuffleWithNonVecInput on resepctive VecVals.
    auto isShuffleWithNonVecInput = [&IntermediateGlueInst](Value *VecVal) {
      if (isa<ShuffleVectorInst>(IntermediateGlueInst))
        if (!VecVal->getType()->isVectorTy())
          return true;
      return false;
    };

    // Replace the operands of IntermediateGlueIndex with the available
    // Set the operands of IntermediateGlueInst according to the replace type.
    switch (getGlueInstOperandReplaceType(IntermediateGlueInst)) {
      case GlueInstOperandReplaceType::ReplaceFirstWithPreviousInput:
        DEBUG_WITH_TYPE(DebugCodegen,
                        dbgs() << "     Replacing first operand with"
                               << " previous input\n");
        if (isShuffleWithNonVecInput(PrevInputVecVal)) {
          // We should replace the insterelement's first operand,
          // which is the first operand of the shuffle.
          IntermediateGlueInst =
            dyn_cast<Instruction>(IntermediateGlueInst->getOperand(0));
          assert(isa<InsertElementInst>(IntermediateGlueInst) &&
                 "Expecting an insertelement instructions\n");
          IntermediateGlueInst->setOperand(1, PrevInputVecVal);

          return;
        }
        IntermediateGlueInst->setOperand(0, PrevInputVecVal);
        return;

      case GlueInstOperandReplaceType::ReplaceFirstWithCurrentInput:
        DEBUG_WITH_TYPE(DebugCodegen,
                        dbgs() << "     Replacing first operand with"
                               << " current input\n");
        if (isShuffleWithNonVecInput(CurrInputVecVal)) {
          // We should replace the insterelement's first operand,
          // which is the first operand of the shuffle.
          IntermediateGlueInst =
            dyn_cast<Instruction>(IntermediateGlueInst->getOperand(0));
          assert(isa<InsertElementInst>(IntermediateGlueInst) &&
                 "Expecting an insertelement instructions\n");
          IntermediateGlueInst->setOperand(1, CurrInputVecVal);
          return;
        }
        IntermediateGlueInst->setOperand(0, CurrInputVecVal);
        return;

      case GlueInstOperandReplaceType::ReplaceSecondWithCurrentInput:
        DEBUG_WITH_TYPE(DebugCodegen,
                        dbgs() << "     Replacing second operand with"
                               << " current input\n");
        if (isShuffleWithNonVecInput(CurrInputVecVal)) {
          // We should replace the insterelement's first operand,
          // which is the first operand of the shuffle.
          IntermediateGlueInst =
            dyn_cast<Instruction>(IntermediateGlueInst->getOperand(1));
          assert(isa<InsertElementInst>(IntermediateGlueInst) &&
                 "Expecting an insertelement instructions\n");
          IntermediateGlueInst->setOperand(1, CurrInputVecVal);
          return;
        }
        IntermediateGlueInst->setOperand(1, CurrInputVecVal);
        return;

      case GlueInstOperandReplaceType::ReplaceBoth:
        DEBUG_WITH_TYPE(DebugCodegen,
                        dbgs() << "     Replacing both operands\n");
        if (!isShuffleWithNonVecInput(PrevInputVecVal))
          IntermediateGlueInst->setOperand(0, PrevInputVecVal);
        else {
          // We should replace the insterelement's first operand,
          // which is the first operand of the shuffle.
          IntermediateGlueInst =
            dyn_cast<Instruction>(IntermediateGlueInst->getOperand(0));
          assert(isa<InsertElementInst>(IntermediateGlueInst) &&
                 "Expecting an insertelement instructions\n");
          IntermediateGlueInst->setOperand(1, PrevInputVecVal);
          return;
        }
        if (!isShuffleWithNonVecInput(CurrInputVecVal))
          IntermediateGlueInst->setOperand(1, CurrInputVecVal);
        else {
          // We should replace the insterelement's first operand,
          // which is the first operand of the shuffle.
          IntermediateGlueInst =
            dyn_cast<Instruction>(IntermediateGlueInst->getOperand(1));
          assert(isa<InsertElementInst>(IntermediateGlueInst) &&
                 "Expecting an insertelement instructions\n");
          IntermediateGlueInst->setOperand(1, CurrInputVecVal);
        }
        return;
       default:
        llvm_unreachable("Invalid operand replace type.");
        return;
    }
  }

  // Check if the replace type of the value is ReplaceBoth.
  bool isReplaceBothOperand(Value *V) {
    return getGlueInstOperandReplaceType(V)
      == GlueInstOperandReplaceType::ReplaceBoth;
  }

  // Check if the replace type of the value is
  // ReplaceSecondWithCurrentInput.
  bool isReplaceSecondOperandWithCurrentInput(Value *V) {
    return getGlueInstOperandReplaceType(V)
      == GlueInstOperandReplaceType::ReplaceSecondWithCurrentInput;
  }

  // Check if the replace type of the value is
  // ReplaceSecondWithCurrentInput.
  bool isReplaceFirstOperandWithCurrentInput(Value *V) {
    return getGlueInstOperandReplaceType(V)
      == GlueInstOperandReplaceType::ReplaceFirstWithCurrentInput;
  }

  // Get the permutation state of the clique
  PermStateType getPermState() { return PermState; }
  // Set the permutation state of the clique
  void setPermState(PermStateType PermState_) { PermState = PermState_; }

  // Get the width of the clique in bits
  // Returns 0 if the instruction cannot be vectorized (eg call, fence etc)
  int32_t getCliqueWidthInBits() {
    // If the clique width has been computed, return it
    if (CliqueWidthInBits != -1) return CliqueWidthInBits;

    // Clique width has not been computed yet, compute it
    uint32_t VF = computeMinVF();
    const DataLayout *DL = GSLPU->getDL();

    // We need to examine only the first instruction in each row of the clique. By
    // defintion, other instructions will have the same type.
    CliqueWidthInBits = 0;
    for (auto &VecRowPtr: getCliqueRows()) {
      // Get the first instruction in this row (vector chain).
      Instruction *I = dyn_cast<Instruction>((*VecRowPtr)[0]);
      assert(I && "Expected an Instruction");
      uint32_t Sz = 0;
      // Calls and some other instructions are not vectorized, hence VF is 1.
      // Return clique width as 0
      if (isa<CallInst>(I) || isa<FenceInst>(I) || isa<AtomicCmpXchgInst>(I) ||
        isa<AtomicRMWInst>(I) || isa<LandingPadInst>(I) || isa<ReturnInst>(I))
        return 0;
        // Terminators are not vectorized too.
      else if (I->isTerminator())
        return 0;
      else if (isa<StoreInst>(I)) {
        Sz = DL->getTypeSizeInBits(
          dyn_cast<StoreInst>(I)->getValueOperand()->getType());
      } else {
        Sz = DL->getTypeSizeInBits(I->getType());
        // Choose the larger size
        if (isa<CastInst>(I) || isa<ICmpInst>(I)) {
          uint32_t OpSz = DL->getTypeSizeInBits(I->getOperand(0)->getType());
          Sz = std::max(Sz, OpSz);
        }
      }
      CliqueWidthInBits = std::max(CliqueWidthInBits, (int32_t)(Sz * VF));
    }

    return CliqueWidthInBits;
  }

  // Check if the clique is padded
  bool getIsPadded() { return isPadded; }
  // Set isPadded
  void setIsPadded(bool isPadded_) {
    isPadded = isPadded_;
  }

  // Given the first load in the clique (\param Val), width of the clique
  // (\param Width) and the extra pad width (\param PadWidth), return true if
  // the clique can be padded, false otherwise
  //
  // If the first load accesses some field of some structure x, then we check
  // if those extra padded loads are also accessing fields of the same
  // structure x and not going out of bounds
  // One more restriction: Types of all the fields accessed by the original
  // loads and the padded loads are the same. This restriction can be removed
  // if it can be proven that the padded loads don't cross the boundary of the
  // structure.
  //
  // In future, if some other pattern is supported, then the code in this
  // function can be abstracted in another function, say canPadLoadSameStruct()
  // and in this function we can return newPattern() || canPadLoadSameStruct()
  bool canPadLoad(Value *Val, uint32_t Width, uint32_t PadWidth) {
    auto LoadI = dyn_cast<LoadInst>(Val);
    // First value is not a load
    if (!LoadI) return false;

    // Base pointer of the load
    Value *BasePtr = getLoadStorePointerOperand(LoadI);
    DEBUG_WITH_TYPE(DebugPadding,
      dbgs() << "  Base Pointer:" << *BasePtr << "\n"
             << "  Pad Loads - Width:" << Width << ", PadWidth:" << PadWidth
             << '\n';
    );

    // If the base pointer is not a gep
    if (!isa<GetElementPtrInst>(BasePtr)) return false;
    auto *GepI = dyn_cast<GetElementPtrInst>(BasePtr);

    // Type of the source element of gep
    Type *SourceTy = GepI->getSourceElementType();
    auto *StructTy = dyn_cast<StructType>(SourceTy);
    // If the source element of gep is not a struct
    if (!StructTy) return false;

    // Ensure the GEP has exactly two indices: [0, i]
    // Gep will look something like this:
    // %a = getelementptr inbounds %struct_b, ptr %c, i64 0, i32 5
    // In the above gep, we are accessing the 5-th field of the structure
    if (GepI->getNumIndices() != 2) return false;

    // Operand 0: base ptr, 1: first index, 2: field index
    Value *IndexVal = GepI->getOperand(2);
    ConstantInt *CI = dyn_cast<ConstantInt>(IndexVal);
    if (!CI) return false;

    // Field accessed by the first load
    auto StartIndex = CI->getZExtValue();
    // Field accessed by the last load
    auto EndIndex = StartIndex + Width + PadWidth - 1;
    DEBUG_WITH_TYPE(DebugPadding,
      dbgs() << "              StartIndex:" << StartIndex << ", EndIndex:"
             << EndIndex << '\n';
    );

    // If the field accessed by the last load goes out of bounds of the struct
    if (EndIndex >= StructTy->getNumElements())
      return false;

    Type *FirstType = StructTy->getElementType(StartIndex);
    // Ensure that all the elements have the same type
    for (int I = StartIndex; I <= EndIndex; ++I) {
      Type *TypeI = StructTy->getElementType(I);
      if (TypeI == nullptr || TypeI != FirstType) return false;
    }

    return true;
  }

  // Get the pad width of the clique
  // A clique can be padded, if that clique meets the following conditions.
  // 1. It is an arithmetic clique or a  memory clique of loads (if the given
  // argument PadLoads is true) - We can't pad all the loads as it may be
  // unsafe. So we only pad the loads after doing some analysis which proves
  // that the padding of the loads is safe. Based on this analysis, the
  // variable PadLoads will be set
  // 2. It is not a singleton clique
  // 3. The input/output types of each scalar value in each row of the clique
  // are same. This ensures that the same pad width is applicable to each row.
  // 4. The current width of the clique is not a power of 2.
  //
  // If any of these 4 conditions are not met, 0 is returned
  // We compute the padding width as the number of columns required to fill the
  // next power of 2
  //
  // This padded clique is a copy, ie, the original clique is also present
  // which will later be split into powers of 2.
  //
  // Note: Here we don't care about the max vector register size. Suppose the
  // max register can hold 8 values and the cliques size is 14, we will still
  // pad the clique with 2 other values. Later during buildSetPartition, the
  // clique will be split into smaller cliques such that each can fit into a
  // vector register
  uint32_t getPadWidth(bool ForcePadLoads = false) {
     // We want to fill the columns of the clique till the next power of 2
    uint32_t Width = getWidth();
    uint32_t PadWidth = PowerOf2Ceil(Width) - Width;

    if (isSingleElement()) return 0;
    // If it is not an arithmetic clique
    if (!isArithmetic()) {
      // Don't pad reduction clique for now
      if (!isMemory()) return 0;
      bool CanPadClq = true;
      // Iterate over each row to check if the store is present
      for (uint32_t Row = 0; Row < getNumRows(); ++Row) {
        auto FirstVal = getScalarVal(Row, 0);
        if (isa<LoadInst>(FirstVal)) {
          DEBUG_WITH_TYPE(DebugPadding, dbgs() << "  Row :" << Row << '\n';);
          bool CanPadThisRow = canPadLoad(FirstVal, Width, PadWidth);
          DEBUG_WITH_TYPE(DebugPadding,
            dbgs() << "  Row: " << Row << " - Can Pad Load: " << *FirstVal
                   << ": " << CanPadThisRow << '\n';
          );
          if (!CanPadThisRow && !ForcePadLoads) CanPadClq = false;
        }
        else if (isa<StoreInst>(FirstVal)) CanPadClq = false;
      }
      if (!CanPadClq) return 0;
    }

    // Type of the values present in the first row
    auto CliqueType = getScalarVal(0, 0)->getType();
    // For each row, its input and output types must be similar
    // For the first row, we don't care about the input types
    // For the last row, we don't care about the output types
    for (uint32_t Row = 1; Row < getNumRows(); ++Row) {
      // Instruction in the first col in this row
      auto *InstInRow = dyn_cast<Instruction>(getScalarVal(Row, 0));
      // Ensure that all the operands of the instruction have the same type
      for (uint32_t I = 0; I < InstInRow->getNumOperands(); ++I) {
        auto *OperandType = InstInRow->getOperand(I)->getType();
        if (CliqueType != OperandType) return 0;
      }
      // Ensure that the output type of the instruction is same (except last row)
      if (Row != getNumRows() - 1 && InstInRow->getType() != CliqueType)
        return 0;
    }

    return PadWidth;
  }

  // Given a PadWidth, add these many number of columns to the clique
  // Check the comments at the top of getPadWidth() for details
  void padClique(uint32_t PadWidth);

  // Print the saved glue instructions.
  void printSavedGlueInsts() {
    for (Value *GlueInst : IntermediateGlueInsts)
      dbgs() << "      " << *GlueInst << "\n";
  }

  // Print the details about this clique.
  void printClique() {
    dbgs() << "Level: " << getLevel() << " | ";
    for (CGNodeIDType Id : getCliqueNodes())
      dbgs() << Id << " ";
    dbgs() << "|\n";
  }
  // Print the rows in this clique with instruction ids.
  void printCliqueRowsWithInstIds() {
    int RowNum = 0;

    for (VecRowPtrType &VecRow: CliqueRows) {
      dbgs() << "    Row " << RowNum << ": [ ";
      for (Value *V : *VecRow) {
        uint32_t InstId = GSLPU->getId(dyn_cast<Instruction>(V));
        dbgs() << InstId << " ";
      }
      dbgs() << "]\n";
      RowNum++;
    }
    if (CliqueRows.size() == 0) dbgs() << "\n";
  }

  // Print the rows in this clique.
  void printCliqueRows() {
    int RowNum = 0;
    for (VecRowPtrType &VecRow: CliqueRows) {
      dbgs() << "    Row " << RowNum << ": |";
      for (Value *V : *VecRow) {
        dbgs() << *V << "  |";
      }
      if (isConnectedToDummyRoot())
        dbgs() << " Connected to DummyRoot (duplicate if external)";
      if (isGlueNode())
        dbgs() << " (GlueNode)";
      if (isVectorNode())
        dbgs() << " (VectorNode)";
      dbgs() << "\n";
      RowNum++;
    }
    if (CliqueRows.size() == 0) dbgs() << "\n";
  }
  // Print the input rows for each row in this clique.
  void printInputRows() {
    for (uint32_t RowNum = 0; RowNum < getNumRows(); RowNum++) {
      dbgs() << "    Row " << RowNum << ":\n";
      // Check whether input rows exist for this clique.
      if (InputRowsMap.count(RowNum)) {
        InputRowsType &InputRows = *InputRowsMap[RowNum];
        for (InputRowType &IR : InputRows) {
          dbgs() << "      <";
          for (Value *V : IR)
            dbgs() << *V << ", ";
          dbgs() << ">\n";
        }
      }
    }
  }
  // Print a row.
  void printRow(InputRowType &Row) {
    dbgs() << "<";
    for (Value *V: Row) {
      dbgs() << " " << *V << ",";
    }
    dbgs() << ">\n";
  }
  // Print the input clique nodes.
  void printInputCliques() {
    // Only one row will be present.
    dbgs() << "Row 0" << "\n";
    for (auto &InputClqShrdPtr : InputClqNodes) {
      dbgs() << "    ";
      InputClqShrdPtr->printCliqueRows();
    }
  }
  // Print the output clique nodes.
  void printOutputCliques() {
    // Only one row will be present.
    dbgs() << "Row 0" << "\n";
    for (auto &OutputClqShrdPtr : OutputClqNodes) {
      dbgs() << "    ";
      OutputClqShrdPtr->printCliqueRows();
    }
  }
  // Print mem-dep input clique nodes.
  void printMemDepInputCliques() {
    // Only one row will be present.
    dbgs() << "Row 0" << "\n";
    for (auto &InputClqShrdPtr : MemDepInputClqNodes) {
      dbgs() << "    ";
      InputClqShrdPtr->printCliqueRows();
    }
  }
  // Print mem-dep output clique nodes.
  void printMemDepOutputCliques() {
    // Only one row will be present.
    dbgs() << "Row 0" << "\n";
    for (auto &OutputClqShrdPtr : MemDepOutputClqNodes) {
      dbgs() << "    ";
      OutputClqShrdPtr->printCliqueRows();
    }
  }

  // Print the given matrix
  static void printMatrix(InstsInCliqueType &ClqMatrix, GSLPUtil *GSLPU) {
    int RowNum = 0;
    for (auto &InstRow: ClqMatrix) {
      dbgs() << "    Row " << RowNum << ": [ ";
      for (Instruction *I : InstRow) {
        uint32_t InstId = GSLPU->getId(I);
        dbgs() << InstId << " ";
      }
      dbgs() << "]\n";
      RowNum++;
    }
  }


  // Functions used in vector codegen.
  //
  // Set the vectorized value generated out of this clique.
  void setVectorizedValue(Value *VecVal) { VectorizedValue =  VecVal; }
  // Get the vectorized value generated out of this clique.
  Value *getVectorizedValue() { return VectorizedValue; }
  // Set the type of this clique as glue noded when it is part of the CliqueDAG.
  void setAsGlueNode() { ClqDAGNodeType = CliqueDAGNodeType::Glue; }
  // Set the type of this clique as vector noded when it is part of the
  // CliqueDAG.
  void setAsVectorNode() { ClqDAGNodeType = CliqueDAGNodeType::Vector; }
  // Check if this clique is a glue node when it is part of the CliqueDAG.
  bool isGlueNode() { return ClqDAGNodeType == CliqueDAGNodeType::Glue; }
  // Check if this clique is a vector node when it is part of the CliqueDAG.
  bool isVectorNode() { return ClqDAGNodeType == CliqueDAGNodeType::Vector; }
  // Check if the type of the clique is Constant. i.e., All the values in this
  // clique are constants.
  bool isConstantClique() { return getKind() == Clique::KindType::Constant; }

  // returns true if the glue is an input to phi which is avail from backedge
  bool isGlueFromBackEdge() {
    return ClqDAGNodeType == CliqueDAGNodeType::GlueFromBackEdge;
  }

  // returns true if the glue is an input to phi which is avail from same phi
  bool isGlueFromSamePhi() {
    return ClqDAGNodeType == CliqueDAGNodeType::GlueFromSamePhi;
  }
};

// TODO: Update the comments.
//
// The Compatibility graph, as the name suggests, models the "compatibility"
// between a pair of nodes in the form of edges. Two nodes are "compatible" if
// they are connected by an edge. The compatibility graph is an undirected
// graph. If two nodes are compatible to each other, then they can be packed
// together into a vector register. This is a necessary but not a sufficient
// condition. In order for the nodes to be vectorizable, there must not exist
// any flow-dependence between the nodes, in addition to being compatible. We
// use a hierarchical structure of the compatibility graph in this
// implementation. At level = 0, each node of the graph corresponds to an LLVM
// IR instruction. A Compatibility graph at level = 1 is the parent
// Compatibility Graph of the Compatibility Graph at level = 0. Each node in the
// parent compatibility graph is created such that it consists of two nodes of
// the child compatibility graph. The two nodes, let us name them src and dest,
// are such that dest is dependent on src. That is, each node in the parent
// compatibility graph represents a use-def chain of length = 1. The
// compatibility graph at higher levels in the hierarchy follow a recursive
// definition. That is, each node in the compatibility graph at level = 2
// consists of two nodes of the child (compatibility graph at level = 1).
// Therefore, each node of a compatibility graph (at some level 'l') represents
// a use-def chain of length 'l'. Hence the depth of the hierarchy is limited by
// the maximum depth of the use-def chain in the BB.
class CompatibilityGraph {
  // Set of instructions for which CG is constructed
  // For normal GSLP, this set spans the entire BB
  // Refer to the comments in the RegionType class for more info
  RegionType *Region;
  // The pointer to the GSLPUtil SingleTon class. We refer to the common APIs
  // applicable to all classes through this.
  GSLPUtil *GSLPU;

public:
  using CGNodeIDType = uint32_t;
  using CGNodeListType = SmallVector<CGNodeIDType, 2>;
  using CliqueKind = Clique::KindType;
  using MemCliqueType = SmallVector<CGNodeIDType, 8>;
  using ArithmeticCliqueType = SmallVector<CGNodeIDType, 8>;
  using ArithmeticCliquesType = SmallVector<ArithmeticCliqueType, 8>;
  using ReductionCliqueType = SmallVector<CGNodeIDType, 8>;
  using SingletonCliqueType = SmallVector<CGNodeIDType, 8>;
  using CliqueNodeType = SmallVector<CGNodeIDType, 8>;
  using ConnectedSubgraphType = SmallVector<CGNodeIDType, 8>;
  // Data structures to capture dependence Relation between CGNodes:
  // Unknown -- not yet computed
  // Depended,
  // Dependent -- flow dependence
  // Cyclic -- cyclic dependence between two nodes
  // Independent -- no dependence
  enum DepRelation {
    Unknown,          /* Not yet computed */
    Depended,
    Dependent,        /* Flow dependence */
    Cyclic,           /* Cyclic dependence */
    Independent       /* No dependence */
  };
  // Get the dependence relation between two CGNodes
  DepRelation getDepRel(CGNodeIDType U, CGNodeIDType V) {
    return CGNodeDependencies[U][V];
  }
private:
  // The level of this CG in the heirarchy.
  uint32_t Level;

  // A node in this CG.
  //
  // A node is a colleciton of individual instructions, which we have mapped
  // to intergers. This is required as at levels >= 1 we have multiple
  // instructions connected by def-use relation.
  // Since CGNodeIDType begins from 0 and is contiguous, using vector here
  using CGNodesType = std::vector<CGNodeListType>;
  CGNodesType CGNodes;

  // An edge in a CG, connects a CGNOde to its compatible CGNodes.
  using CGEdgeSetType = SmallSet<CGNodeIDType, 4>;
  using CGEdgesType = std::map<CGNodeIDType, CGEdgeSetType>;
  CGEdgesType CGEdges;

  // Handle to Hierarchical CompatibilityGraph.
  HierCompatibilityGraph *HCG;

  // We maintain a map between CGNodeIds and a pair of child Ids. We have a
  // pair as we know that we can have a maximum of two children. The order of
  // the pair matters as the last instruciton in the first pair connects to
  // the first instruction in the second pair with a def-use edge.
  SmallDenseMap<CGNodeIDType/*Id of the node in this CG*/,
    std::pair<CGNodeIDType, CGNodeIDType>/*Ids of the left and right childern
                                            nodes in the lower level CG*/>
      CGChildNodes;

  // To store the operand number through which a level-1 CGNode is expanded.
  std::map<CGNodeIDType, uint32_t> ExpandedOperandNumMap;

  std::vector<std::vector<DepRelation>> CGNodeDependencies;

  // Build nodes for compatibility graph.
  void buildNodes();

  // Add a new node to the node list of CGNodeId. This version is called only
  // for constructing nodes at level 0. Here CGNodeId is same as the
  // instruciton id. CGNodeIds are added in the order (0, 1, ..). 
  // Hence the new CGNodeList can just be appended at the end of CGNodes
  void addToNodeList(CGNodeIDType CGNodeId, CGNodeIDType NewNode) {
    assert(CGNodeId == CGNodes.size() && "Cannot add to node list in random order");
    CGNodeListType NewList;
    NewList.push_back(NewNode);
    CGNodes.push_back(NewList);
  }

  // Set the operand number through which a higher level CGNode is expanded.
  void setExpandedOperandNum(CGNodeIDType CGNodeId, uint32_t OpNum) {
    ExpandedOperandNumMap[CGNodeId] = OpNum;
    return;
  }
  // Get the operand number through which a higher level CGNode is expanded.
  uint32_t getExpandedOperandNum(CGNodeIDType CGNodeId) {
    return ExpandedOperandNumMap[CGNodeId];
  }

  // This version of addToNodeList is for creating CGs with level > 0.
  //
  // Add a new node with NewCGNodeId as the unique id. It essentially appends
  // DedNodeId to SrcList.  CGNodeIds are added in the order (0, 1, ..).
  // Hence the  SrcList can be appended at the end of CGNodes
  //
  // Note that SrcList is not a reference as we need copy of it and DefNodeId
  // is appended to it. Otherwise, it will corrupt level - 1 CGNodes.
  void addToNodeList(CGNodeIDType NewCGNodeId, CGNodeListType SrcList,
                      uint32_t DefNodeId) {
    // The node for NewCGNodeId should not have been already created.
    assert(NewCGNodeId == CGNodes.size() && "Cannot add to node list in random order");
    SrcList.push_back(DefNodeId);
    CGNodes.push_back(SrcList);
  }

  // Add left and right children nodes for a new CGNode.
  void addChildren(CGNodeIDType NewCGNodeId, CGNodeIDType LeftChildId,
                    CGNodeIDType RightChildId) {
      CGChildNodes.insert(
          std::make_pair(NewCGNodeId,
                          std::make_pair(LeftChildId, RightChildId)));
  }
  // Get the left child of of CGNode
  CGNodeIDType getLeftChild(CGNodeIDType CGNodeId) {
    return CGChildNodes[CGNodeId].first;
  }
  // Get the right child of of CGNode
  CGNodeIDType getRightChild(CGNodeIDType CGNodeId) {
    return CGChildNodes[CGNodeId].second;
  }

  // Add an edge between CGNodeId1 and CGNodeId2. As the relation is
  // symmetric, we add the reverse edge too.
  void addEdge(CGNodeIDType U, CGNodeIDType V) {
    // Add edge U --> V
    if(CGEdges.count(U) == 0) {
      CGEdgeSetType EdgeSet;
      EdgeSet.insert(V);
      CGEdges.insert(std::make_pair(U, EdgeSet));
    } else
      CGEdges[U].insert(V);
    // Add edge V --> U
    if(CGEdges.count(V) == 0) {
      CGEdgeSetType EdgeSet;
      EdgeSet.insert(U);
      CGEdges.insert(std::make_pair(V, EdgeSet));
    } else
      CGEdges[V].insert(U);
  }

  // return the degree (no of adjacent nodes) of the given CGNode
  int32_t getDegree(CGNodeIDType U) {
    if (CGEdges.count(U) == 0) return 0;
    return CGEdges[U].size();
  }

  // Get the first instruction in the use-def chain of CGNode with id
  // CGNodeId.
  Instruction *getHeadInst(CGNodeIDType CGNodeId) {
    auto &CGNodeList = CGNodes[CGNodeId];
    return GSLPU->getInst(CGNodeList[0]);
  }

  // Get the last instruction in the use-def chain of CGNode with id CGNodeId.
  Instruction *getTailInst(CGNodeIDType CGNodeId) {
    auto &CGNodeList = CGNodes[CGNodeId];
    return GSLPU->getInst(CGNodeList.back());
  }

  // Check if two CGNodes are compatible.
  bool areCompatible(CGNodeIDType U, CGNodeIDType V) {
    // FIXME: The condition in the second line might be redundant. Avoid it
    // after confirming.
    return (CGEdges.count(U) && CGEdges[U].contains(V)) &&
            (CGEdges.count(V) && CGEdges[V].contains(U));
  }
  // Check if two CGNodes are adjascent.
  bool isAdjacent(CGNodeIDType U, CGNodeIDType V) {
    return areCompatible(U, V);
  }

  // Add compatibility edges for this CG.
  void addCompatibleEdges();
  // Check if two CGNodes are compatible or not.
  bool areCompatibleNodes(CGNodeIDType, CGNodeIDType);

  // Initialize the dependences among all pair of CGNodes as Unknown.
  void initDependences() {
    for (CGNodeIDType CGNodeId = 0; CGNodeId < CGNodes.size(); CGNodeId++) {
      CGNodeDependencies.push_back(
          std::vector<DepRelation> (CGNodes.size(), DepRelation::Unknown));
    }
  }
  // Check if two CGNodes are dependent.
  bool isDependent(CGNodeIDType U, CGNodeIDType V);
  // Check if two CGNodes are dependent specifically at Level 0.
  bool isDependentAtLevel0(CGNodeIDType U, CGNodeIDType V, bool IsReduction);
  // Set the dependence relation between instructions with ids Id1 and Id2.
  // FIXME: Note that here we have instruction ids. This is fine for level 0.
  // We must change them to CGNodeIds.
  void setDepRel(uint32_t Id1, uint32_t Id2, DepRelation DepRel) {
    CGNodeDependencies[Id1][Id2] = DepRel;
  }
  // Set the dependences due to the memory fences.
  bool setDepRelDueToFences(CGNodeIDType U, CGNodeIDType V);
  // Set the dependences due to data flow
  bool setDepRelDueToDataFlow(CGNodeIDType U, CGNodeIDType V);
  /// Wrapper for dataFlowPathExists.
  bool dataFlowPathExists(uint32_t UId, uint32_t VId) {
    SmallSet<uint32_t, 16> Visited;
    return dataFlowPathExists(GSLPU->getInst(UId), GSLPU->getInst(VId),
                              Visited);
  }
  // Check if there exists flow dependence between I1 and I2. Returns true if
  // I2 is dependent on I1. Returns  false, otherwise.
  bool dataFlowPathExists(Instruction *I1, Instruction *I2,
                          SmallSet<uint32_t, 16> &Visited);
  // This function finds the memory instrutions that are used by Inst in the
  // upward slice of its operands in the DDAG.
  std::vector<Instruction *>
    getSourceMemoryInstructions(Instruction *, std::vector<Instruction *> &);
  // This function finds the memory instrutions that uses Inst in the downward
  // slice of its users in the DDAG.
  std::vector<Instruction *>
    getSinkMemoryInstructions(Instruction *, std::vector<Instruction *> &);
  // If two instructions are not connected by a datapath, it is not safe to
  // assume that they are vectorizable. They are vectorizable only when they
  // can be scheduled together. Schedulability depends on intervening memory
  // dependencies.
  bool checkIfSchedulable(uint32_t UId, uint32_t VId);
  // Function to check if two instructions can be collated into a SIMD
  // (vector) instruction.
  bool canBeSimdized(Instruction *I1, Instruction *I2);
  // Some preliminary checks, which can be removed as most of the are
  // artificial restrictions.
  bool canBeSimdizedPreliminary(Instruction *I1, Instruction *I2);
  bool areLoadsStoresInSameDirection(LoadInst *L1, LoadInst *L2,
      StoreInst *S1, StoreInst *S2);
  bool moreUsesConstraintsSatisfied(CGNodeIDType U, CGNodeIDType V);
  // Functions related to generating cliques within this CG.
  //
  // Starting with \param U_id, this function finds the connected subgraph.
  // This follows the standard BFS based algorithm to find connected
  // component in an undirected graph. A worklist based approach is followed.
  ConnectedSubgraphType getConnectedSubgraph(
      CGNodeIDType U_0Id, SmallVector<bool> &AddedToSomeMemClique);

  // Variables and functions related to clique generation.
  //
  // Sort the connected subgraph. Here the sorting is just based on the scev
  // distance.
  void sortConnectedSubGraph(ConnectedSubgraphType &ConnectedSubgraph,
                              bool IsLoadNode);
  // From the sorted list, we will find the final memory cliques by
  // enumerating all the longest consecutive chains which are independent.
  void generateMemoryCliques(ConnectedSubgraphType &ConnectedSubgraph);
  // Get the estimated execution cost improvement due to vectorization of the
  // clique w.r.t., the scalar input.
  InstructionCost getCost(Clique &);
public:
  CompatibilityGraph(RegionType *Region_, uint32_t Level,
                  HierCompatibilityGraph *HCG_, GSLPUtil *GSLPU_) :
    Region(Region_), Level(Level), HCG(HCG_), GSLPU(GSLPU_) {}

  // Build the Compatibility Graph.
  void build();

  // Get the level of this CG;
  uint32_t getLevel() { return Level; }
  // Get the current Region
  RegionType *getRegion() { return Region; }
  // Get the CG at one level lower.
  CompatibilityGraph *getLowerLevelCG();
  // Get the list of individual nodes, which is the use-def chain within
  // a CGNode.
  CGNodeListType &getCGNodeList(CGNodeIDType CGNodeId) {
    return CGNodes[CGNodeId];
  }
  // Get the lower level CGNodes.
  CGNodesType& getLowerLevelCGNodes() {
    return getLowerLevelCG()->getCGNodes();
  }

  // Get the CGNodes.
  CGNodesType &getCGNodes() { return CGNodes; }
  // Get the CGEdges.
  CGEdgesType &getCGEdges() { return CGEdges; }

  // Print CGNodes.
  void printNodes() {
  dbgs() << "  Number of CGNodes = " << CGNodes.size() << '\n';
  dbgs() << "  CGNodeId CGNodeList (-> is def-use edge)\n";
  dbgs() << "  -------- -------------------------------\n";
  for (CGNodeIDType CGNodeId1 = 0; CGNodeId1 < CGNodes.size();
      CGNodeId1++) {
  dbgs() << "     " << CGNodeId1 << "       [ ";
  auto &CGNodeList = CGNodes[CGNodeId1];
  uint32_t NumInsts = CGNodeList.size();
  uint32_t Iter = 0;
  for (uint32_t InstId: CGNodeList) {
      dbgs() << InstId << " ";
      // -> represents a def-use edge.
      if (Iter++ != NumInsts - 1)
      dbgs() << "-> ";
  }
  dbgs() << "]\n";
  }
  }

  // Print left and right children nodes for a new CGNode.
  void printChildren() {
  if (Level == 0) {
  dbgs() << "No children for level 0 CGNodes\n";
  return;
  }
  dbgs() << "  Level " << Level << " Id    Level " << Level - 1
          << " (LeftChild RightChild)\n";
  dbgs() << "  ----------    ------------------------------\n";
  for (auto &CGChildNodesEntry : CGChildNodes) {
  CGNodeIDType CGNodeId = CGChildNodesEntry.first;
  CGNodeIDType LeftChildId = CGChildNodes[CGNodeId].first;
  CGNodeIDType RightChildId = CGChildNodes[CGNodeId].second;
  dbgs() << "       " << CGNodeId << "                      "
          << LeftChildId << "         " << RightChildId << "\n";
  }
  }

  // Print CGEdges.
  void printEdges() {
    dbgs() << "  CGNodeId <---> CGNodeIdSet\n";
    dbgs() << "  --------       -----------\n";
    //for (CGNodeIDType CGNodeId1 = 0; CGNodeId1 < CGEdges.size();
    //    CGNodeId1++)
    for (auto &CGEdgeEntry : CGEdges) {
    CGNodeIDType CGNodeId1 = CGEdgeEntry.first;
    dbgs() << "     " << CGNodeId1 << "     <--->    ";
    CGEdgeSetType CGNodeId2Set = CGEdgeEntry.second;
    for (CGNodeIDType CGNodeId2 : CGNodeId2Set) {
        dbgs() << CGNodeId2 << " ";
    }
    dbgs() << "\n";
    }
  }
  // Get the number of CGNodes.
  uint32_t getNumNodes() { return CGNodes.size(); }
  // Get the number of CGEdges.
  uint32_t getNumEdges() { return CGEdges.size(); }

  // Functions related to generating cliques within this CG.
  //
  // Refer the definition of these functions for more details.

  // Add clique to the list of cliques.
  //
  // Note that we are storing all the cliques irrespective of the level into
  // HCG. This helps iterative over all the cliques easier.
  //
  // We will need to use these cliques across multiple classes. Hence we
  // dynamically allocate them using unique_ptr. Be careful that it cannot
  // be copied, but moved and the ownership will get transferred.
  void addClique(CliqueKind K_, CliqueNodeType CliqueNodes_);
  // Generate Memory Cliques
  void generateMemoryCliques(SmallVector<bool> &AddedToSomeMemClique);
  // Generate Reduction Cliques.
  void generateReductionCliques();
  // Generate Arithmetic cliques.
  void generateArithmeticCliques(SmallVector<bool> &AddedToSomeMemClique);
  // Generate Singleton cliques.
  void generateSingletonCliques();
  // Return the reduction sequence/tree.
  void getReductionTree(Instruction *Root,
                      SmallVector<Instruction *, 8> *RedVec);
  // ReductionTree* getReductionTree(Instruction *Root);
  // The second version (optimized) of the extension operator of Bron
  // Kerbosch algorithm.
  void extendVersion2(SmallVector<CGNodeIDType> Old, int32_t NE, int32_t CE,
                  ArithmeticCliqueType &CompSub,
                  int32_t &NumArithmeticCliques);
~CompatibilityGraph() {}
};

// Class to hold various costs while constructing the set partition.
//
class GSLPCost {
public:
  // Variables to hold the costs related to the temporary clique being
  // considered.
  InstructionCost ClqGlueCost;
  InstructionCost ClqLiveoutCost;
  InstructionCost ClqVectorCost;
  InstructionCost TotalClqCost;
  uint32_t NumInstsCoveredInClq;
  // The below costs are not actually used in decision making. Just keeping it
  // for debugging purposes
  InstructionCost UnfrozenTotalGlueCost;
  InstructionCost UnfrozenTotalLiveoutCost;
  InstructionCost UnfrozenTotalVectorCost;

  // Variables to gold the costs of the current minimum clique.
  InstructionCost MinClqGlueCost;
  InstructionCost MinClqLiveoutCost;
  InstructionCost MinClqVectorCost;
  double MinClqTotalCost;
  uint32_t NumInstsCoveredInMinClq;

  // Variables to hold various cumulative costs of the CliqueDAG.
  // The total vector instruction cost of the partial CliqueDAG.
  InstructionCost TotalVectorCost;
  // The total glue cost of the partial CliqueDAG.
  InstructionCost TotalGlueCost;
  // The total live out cost of the partial CliqueDAG.
  InstructionCost TotalLiveoutCost;


  GSLPCost() {
    // Initialize various total costs of the current clique.
    ClqGlueCost = 0;
    ClqLiveoutCost = 0;
    ClqVectorCost = 0;
    TotalClqCost = 0;
    UnfrozenTotalGlueCost = 0;
    UnfrozenTotalLiveoutCost = 0;
    UnfrozenTotalVectorCost = 0;
    NumInstsCoveredInClq = 0;
    // Initialize various total costs of the minimum clique.
    MinClqGlueCost = 0;
    MinClqLiveoutCost = 0;
    MinClqVectorCost = 0;
    MinClqTotalCost = DBL_MAX;
    NumInstsCoveredInMinClq = 0;
    // Initialize various total costs of the CliqueDAG.
    TotalVectorCost = 0;
    TotalGlueCost = 0;
    TotalLiveoutCost = 0;
  }

  // Reset the cost variables related to the temporary clique being considered
  // to be checked if this is a minimum clique
  void resetCurrentClqCost() {
    ClqGlueCost = 0;
    ClqLiveoutCost = 0;
    ClqVectorCost = 0;
    TotalClqCost = 0;
    UnfrozenTotalGlueCost = 0;
    UnfrozenTotalLiveoutCost = 0;
    UnfrozenTotalVectorCost = 0;
    NumInstsCoveredInClq = 0;
  }

  // Reset the cost variables storing min glue cost, min live out cost, and min
  // vector cost and the cost of the clique with minimum cost among the already
  // processed candidate cliques for the entire inner iteration. We use these to
  // update the final cost once one clique is frozen into CliqueDAG.
  void resetMinClqCosts() {
    MinClqGlueCost = 0;
    MinClqLiveoutCost = 0;
    MinClqVectorCost = 0;
    MinClqTotalCost = DBL_MAX;
  }

  // Get the total unfrozen CliqueDAG cost.
  InstructionCost getTotalUnfroznenCost() {
    return UnfrozenTotalGlueCost + UnfrozenTotalLiveoutCost +
      UnfrozenTotalVectorCost;
  }

  // Update the costs of the current minimum clique.
  void updateMinClqCosts() {
    MinClqGlueCost = ClqGlueCost;
    MinClqLiveoutCost = ClqLiveoutCost;
    MinClqVectorCost = ClqVectorCost;
    MinClqTotalCost = TotalClqCost.getValue().value();
    NumInstsCoveredInMinClq = NumInstsCoveredInClq;
  }
  // Update the vector cost of the whole partial CliqueDAG.
  void updateTotalVectorCost(InstructionCost VectorCost_) {
    TotalVectorCost += VectorCost_;
  }
  // Get the current vector cost the partial CliqueDAG.
  InstructionCost getTotalVectorCost() {
    return TotalVectorCost;
  }
  // Update the glue cost of the whole partial CliqueDAG.
  void updateTotalGlueCost(InstructionCost GlueCost_) {
    TotalGlueCost += GlueCost_;
  }
  // Update the glue cost of the whole partial CliqueDAG.
  void updateTotalLiveoutCost(InstructionCost LiveoutCost_) {
    TotalLiveoutCost += LiveoutCost_;
  }
  // Get the current glue cost the partial CliqueDAG.
  InstructionCost getTotalGlueCost() {
    return TotalGlueCost;
  }
  // Get the current live out cost the partial CliqueDAG.
  InstructionCost getTotalLiveoutCost() {
    return TotalLiveoutCost;
  }
  // Get the total cost for the partial CliqueDAG.
  double getTotalCost() {
    return (TotalGlueCost + TotalLiveoutCost +
            TotalVectorCost).getValue().value();
  }

  // Check if the current clique is cost effective than the current minimum.
  bool isProfitable() {
    bool FoundMin = false;
    if (TotalClqCost.getValue().value() < MinClqTotalCost) {
      DEBUG_WITH_TYPE(VerboseDebugLevel1,
                      dbgs() << "\nFound a minimum clique with a lesser"
                             << " cost\n");
      return true;
    } else if (TotalClqCost.getValue().value() == MinClqTotalCost) {
      if (NumInstsCoveredInClq > NumInstsCoveredInMinClq) {
        DEBUG_WITH_TYPE(VerboseDebugLevel1,
                        dbgs() << "\nFound a minimum clique with equal cost"
                               << " but covering more instructions\n");
        return true;
      }
    }
    return false;
  }
};


// A CliqueDAG is a DAG (Directed Acyclic Graph) composed of Cliques as its
// nodes. In general, each multi-row clique can form a node in a CliqueDAG, but
// for simplicity and for ease of detecting cycles (when a new node is added),
// the nodes will be of single row.
//
// TODO: Implement CliqueDAG of multi-row cliques.
//
// A CliqueDAG node D_i is an input node for another node D_j, if D_j uses D_i
// as one of its input rows. Also, D_j is an output node for D_i.
//
// There is an edge between two CliqueDAG nodes D_i and D_j, if D_i is an input
// node of D_j.
//
// For a node D_i, we keep both its input nodes and output nodes.
//
// A DAG is defined by its nodes, edges and a DummyRoot. A node will be
// connected to a DummyRoot, if that node has any external inputs.
//
// The output of the set partition algorithm will be a CliqueDAG. Later the
// vector codegen will be performed on this CliqueDAG.
class CliqueDAG {
  // The pointer to the GSLPUtil SingleTon class. We refer to the common APIs
  // applicable to all classes through this.
  GSLPUtil *GSLPU;
  HierCompatibilityGraph *HCG;

  using CGNodeIDType = uint32_t;
  using CliquePtrType = std::shared_ptr<Clique>;
  using CliqueShrdPtrType = std::shared_ptr<Clique>;
  using VecRowType = SmallVector<Value*, 4>;
  using VecRowPtrType = std::unique_ptr<VecRowType>;
  using CliqueIDType = uint32_t;
  // A unique ID for each clique added to this CliqueDAG.
  CliqueIDType CliqueId;
  // Value to input row map.
  //
  // Pointer type to an input row.
  using InputRowType = SmallVector<Value *, 4>;
  using InputRowsType = SmallVector<InputRowType, 2>;
  using InputRowPtrType = std::unique_ptr<InputRowsType>;
  // Types for storing map between values and their available rows.
  using InputRowShrdPtrType = std::shared_ptr<InputRowType>;
  // Note that though this is not a set, but a vector, we are keeping
  // the name as it is doing the puropose of a set. We cannot use a
  // set because of reproducibility issues.
  using RowSetType = SmallVector<InputRowShrdPtrType, 16>;
  using ValToRowSetMapType = std::map<Value*, RowSetType>;
  ValToRowSetMapType ValueToRowsMap;
  // This map will be used to store the input nodes coming from outside the
  // basic block.
  ValToRowSetMapType ExternalValueToRowsMap;
  // Types for storing map between an input row and the CliqueDAGNode in which
  // it is originally available.
  using InputClqNodeShrdPtrType = std::shared_ptr<Clique>;
  using InputRowPtrToCliqueDAGNodeType
    = std::map<InputRowShrdPtrType, InputClqNodeShrdPtrType>;
  InputRowPtrToCliqueDAGNodeType InputRowPtrToCliqueDAGNodeMap;
  using OutputClqNodeShrdPtrType = InputClqNodeShrdPtrType;
  // A list to keep track of all InputRowShrdPtrs for efficient deletion of
  // entries in various storages. We iterate this list to delete values from
  // maps which we need to update while removing a clique from CliqueDAG.
  // This list is cleared everytime we freeze a clique into the CliqueDAG so
  // that it will not be deleted in any future iterations.
  std::set<InputRowShrdPtrType> IRSPRefsToDelete;
  // Since fences are maintained between instructions, we also need a mapping
  // from instructions to the CliqueDAGNode for Mem-Dep edge requirements.
  using InstructionToCliqueDAGNodeType
    = std::map<Instruction*, InputClqNodeShrdPtrType>;
  InstructionToCliqueDAGNodeType InstrToCliqueDAGNodeMap;

  // The list of all the glue nodes created while trying to adda multi-row
  // clique to the CliqueDAG.
  using GlueNodesListType = SmallVector<CliqueShrdPtrType, 4>;
  // This must be cleared before trying to add each multi-row clique.
  GlueNodesListType GlueNodesList;
  // Since we create Glue Instructions for Glue Nodes even before we freeze a
  // clique into the CliqueDAG, we need to clear them from BasicBlock after we
  // remove the clique. This list keeps track of all glue instructions created
  // so that they can be removed from BB.
  SmallVector<Value*, 8> GlueNodeInstToDeleteList;
  // List of glue instructions to be costed
  // This list is also used in the permuteClique() to get the glue instructions
  SmallVector<Instruction *, 4> GlueInstsToBeCosted;
  // The dummy root node.
  CliqueShrdPtrType DummyRoot;
  // Bit vector to store the information that if an instruction is already
  // covered or not
  SmallBitVector CoveredInstructions;
  // Bit vector to store the information that if a original scalar instruction
  // is to be deleted or not after vector codegen.
  SmallBitVector ScalarInstsToBeDeleted;
  // The topologically sorted (reverse post order) list of nodes in this
  // CliqueDAG. This will be the input to vector code gen.
  using TopoSortedNodesType = SmallVector<CliqueShrdPtrType, 16>;
  TopoSortedNodesType TopoSortedNodes;
  // Set to store the list of singleton GEP vector nodes.
  std::set<CliqueShrdPtrType> SingletonGEPVectorNodes;

  // We do an optimization to combine reduction to vector addditions. This list
  // store such candidate reduction cliques.
  SmallVector<CliqueShrdPtrType, 4> CandidateRednClqsToCombine;
  // Set to store all the distinct input indices found so far in the above
  // candidate reduction cliques.
  std::unordered_set<int32_t> SetOfAllIndices;

  // List of the all the GEP glue nodes converted to vector nodes via
  // convertGEPGlueNodesToVectorNodes function
  SmallVector<CliqueShrdPtrType, 16> GlueGepsConvertedToVec;

  using InstsInCliqueType = Clique::InstsInCliqueType;
  using GeneratedSubCliquesSetType = std::set<InstsInCliqueType>;
  // Set of all the sub cliques that have been generated (after split)
  // This list is used to ensure that we don't generate duplicate
  // sub cliques
  GeneratedSubCliquesSetType GeneratedSubCliquesSet;
  using AvailFromType = Clique::AvailFromType;

  // For each scalar instruction, we will keep an entry to this type to know
  // where it is present in the final vectorized code
  struct ScalarToVecInstType {
    // Instruction in the vectorized code
    Value *VecVal;
    // Whether the instruction in the vectorized code is a vector instruction
    bool isVector;
    // If it is a vector instruction, the lane number in which the scalar inst
    // is present
    uint32_t LaneNum;

    ScalarToVecInstType() : VecVal(nullptr), isVector(false), LaneNum(0) {}
    ScalarToVecInstType(Value *VecVal_, bool isVector_ = false,
      uint32_t LaneNum_ = 0) : VecVal(VecVal_), isVector(isVector_),
      LaneNum(LaneNum_) {}
  };

  // For each inst id, we keep an entry of the type ScalarToVecInstType
  using ScalarToVecInstMapType = std::vector<ScalarToVecInstType>;
  ScalarToVecInstMapType ScalarToVecInstMap;

  // List of Phi's whose one(or more) operands are available via backedge/
  // same phi. In codegen these operands are converted to poison and such type
  // of cliques are stored in this list. Finally after codegen, poison will be
  // replaced with actual instructions
  using PhiWithBackedgeOperandsType = SmallVector<CliqueShrdPtrType, 4>;
  PhiWithBackedgeOperandsType PhiWithBackedgeOperands;

  // Maps a pair of <Clique, operand number> to its AvailFromType
  // Used for Phi nodes whose operand(s) is available from backedge/same phi
  // Once this info has been computed, it is stored in this map so that it
  // doesn't need to be recomputed again
  using AvailFromMapType = std::map<std::pair<CliquePtrType, int32_t>, AvailFromType>;
  AvailFromMapType AvailFromMap;


  // Map to store the vector factor mix - The number of vector instructions
  // with different vector factors.
  std::map</*VF*/int32_t, /*Number of insts with VF*/int32_t>  VFMix;
  // Map to store the vector width mix - The number of vector instructions
  // with different vector widths.
  std::map</*VectorWidth - VW*/int32_t,
           /*Number of insts with VW*/int32_t>  VWMix;

  // Function to update the VFMix of \pararm VF.
  void addVFToVFMix(int32_t VF) {
    if (VFMix.find(VF) == VFMix.end())
      VFMix[VF] = 1;
    else
      VFMix[VF]++;
  }

  // Function to update the VWMix of \pararm VW.
  void addVWToVWMix(int32_t VW) {
    if (VWMix.find(VW) == VWMix.end())
      VWMix[VW] = 1;
    else
      VWMix[VW]++;
  }

  // Struct to manage data structures/variables in the across various
  // iterations over the input nodes in the createGlueInstructions()
  struct GlueInstUtil {
    uint32_t GlueNodeWidth;
    // Saved values from the previous iteration over input nodes
    Value *PrevInputShuffle;
    Value *PrevInputVector;
    uint32_t PrevInputVecSize;
    uint32_t PrevInputShuffleSize;
    // current iteration values
    Value *InputVector;
    uint32_t InputVecSize;
    Value *ShuffleInst;
    // Bit vector to store if we already found the mask at a particular postion.
    SmallBitVector MaskAlreadyFound;
    // The shuffle mask generated for the inputs. The same mask will be updated
    // for all the inputs.
    SmallVector<int32_t> ShuffleMask;
    // Number of Values available so far in the input (equal to the number of
    // set bits in MaskAlreadyFound). This will be used while compressing the
    // shuffle mask while generating glue instructions.
    uint32_t NumInputValuesAvailable;
    bool SaveExpandedForCodegenUse;
    bool PrevInputExpandedForSecondInput;
    Value *ExpandedShuffleToSave = nullptr;

    GlueInstUtil(uint32_t GlueNodeWidth) {
      this->GlueNodeWidth = GlueNodeWidth;
      PrevInputShuffle = nullptr;
      PrevInputVector = nullptr;
      PrevInputVecSize = 0;
      PrevInputShuffleSize = 0;
      InputVector = nullptr;
      InputVecSize = 0;
      ShuffleInst = nullptr;
      MaskAlreadyFound = SmallBitVector(GlueNodeWidth, false);
      ShuffleMask = SmallVector<int32_t>(GlueNodeWidth);
      SaveExpandedForCodegenUse = false;
      PrevInputExpandedForSecondInput = false;
      ExpandedShuffleToSave = nullptr;
      NumInputValuesAvailable = 0;
    }

    void saveCurrentForNextIteration() {
      PrevInputShuffle = ShuffleInst;
      PrevInputVector = InputVector;
      PrevInputVecSize = InputVecSize;
      PrevInputShuffleSize = ShuffleMask.size();
      SaveExpandedForCodegenUse = false;
      PrevInputExpandedForSecondInput = false;
      ExpandedShuffleToSave = nullptr;
    }

    // Compress the shuffle mask to the total size of input input operands
    // of the shuffle instruction.
    void compressShuffleMask() {
      uint32_t NewSz = 1;
      // Get the max size of compressed. The upper limit is closest power of
      // 2, which is greater than NumInputValuesAvailable.
      while (NewSz < NumInputValuesAvailable)
        NewSz <<= 1;

      SmallVector<int32_t> CompressedMask(NewSz, -1);
      uint32_t CMIndex = 0;
      // Copy the relevant masks from ShuffleMask to CompressedMask.
      for (uint32_t Index = 0; Index < GlueNodeWidth; Index++) {
        if (MaskAlreadyFound.test(Index)) {
          CompressedMask[CMIndex++] = ShuffleMask[Index];
        }
      }
      // Now make the mask to be the compressed mask.
      ShuffleMask = CompressedMask;
    }
  };

  // Create a vector instruction for \param InputNodeRowPtr using a sequence of
  // insert elements. If H <U_0, U_1, ..., U_m-1) the following sequence will be
  // generated.
  Value *createInputVector(VecRowPtrType &InputNodeRowPtr,
                           Value *PrevInputVector, VectorType *VecType,
                           Instruction *InsertPoint, bool ToBeCosted,
                           IRBuilder<> &Builder,
                           InputClqNodeShrdPtrType InputClqNodePtr,
                           int32_t InsertAt);
  // Expand the size of the vector \param ShorterInput to size \param
  // SizeOfLonger.
  Value *expandShorterInput(Value *ShorterInput, uint32_t SizeOfLonger,
                            IRBuilder<> &Builder,
                            Value* &ExpandedShuffleToSave);

  // Expand the input if required.
  void expandInput(CliqueDAG::CliqueShrdPtrType &, int32_t InputNum,
                   uint32_t SizeOfLonger, GlueInstUtil &GlueInstU,
                   IRBuilder<> &Builder /*Ref*/);

  // Create the shuffle instruction for the glue node.
  Value *createGlueInstruction(CliqueDAG::CliqueShrdPtrType &ClqDAGGlueNodePtr,
                               int32_t InputNum, uint32_t NumInputNodes,
                               GlueInstUtil &GlueInstU,
                               CliqueShrdPtrType& InputClqNodePtr,
                               VecRowPtrType &InputNodeRowPtr,
                               IRBuilder<> &Builder);
  // Generate glue instructions in the generalized tree based manner.
  bool generateTreeBasedGlueInsts(CliqueShrdPtrType &ClqDAGGlueNodePtr);
  // For now we are generating tree based glue instructions only if we have a
  // balanced tree. This should satisfy the following 4 conditions.
  //
  // 1. The glue node width should be power of 2 and > 1.
  // 2. Number of input nodes for the glue nodes should be power of 2 and > 1.
  // 3. The number of available nodes from each input should be power of 2.
  // 4. The number of available nodes from each input should be equal.
  // 5. The width of all input nodes should be the same.
  //
  // TODO: Avoid this restriction when we generalize it.
  bool feasibleToGenerateTreeBasedGlueInsts(CliqueShrdPtrType &ClqDAGGlueNodePtr);
  // Generate glue instructions for partitions.
  Value *generateGlueInstsForPartitions(Clique::InputClqNodesType &InputNodes,
      CliqueShrdPtrType &ClqDAGGlueNodePtr,
      SmallVector <int32_t, 4> &CombinedGlueMask);
  // Create glue instruction for a partition of input nodes.
  Value *createGlueInstruction(Clique::InputClqNodesType &InputNodes,
                               CliqueShrdPtrType &ClqDAGGlueNodePtr,
                               SmallVector <int32_t, 4> &CombinedGlueMask);
  // Combine two glue instructions to one.
  Value *combineGlueInsts(Value *GlueInst1, Value *GlueInst2,
                          SmallVector <int32_t, 4> &CombinedGlueMask);
  // Get the local glue mask and local input masks. For details refer to the
  // header of this function.
  SmallVector<int32_t, 4> getLeafNodeShuffleMask(VecRowPtrType &GlueNodeRowPtr,
      VecRowPtrType &InputNodeRowPtr, SmallVector<int32_t, 4> &LocalGlueMask);
  // Function to find postions of values in Vec1 in Vec2. The result will be
  // stored in result.
  void findPositionsOfValuesInOther(
      SmallVector<Value*, 4> &Vec1, SmallVector<Value*, 4> &Vec2,
      SmallVector<int32_t, 4> &Result1, SmallVector<int32_t, 4> &Result2) {
    for (uint32_t Index = 0; Index < Vec1.size(); Index++) {
      auto Val = Vec1[Index];
      // Find the position of Val in Vec2.
      auto Iter = std::find(Vec2.begin(), Vec2.end(), Val);
      // if Val is not found in Vec2 check for next value.
      if (Iter == Vec2.end()) continue;
      // Update the Result.
      int32_t ValIndex = Iter - Vec2.begin();
      Result1.push_back(Index);
      Result2.push_back(ValIndex);
    }
    return;
  };

  SmallVector <int32_t, 4> getInputMask(
      SmallVector<int32_t, 4> &UnsortedGlueMask,
      SmallVector<int32_t, 4> &SortedGlueMask,
      SmallVector<int32_t, 4> &UnsortedInputMask) {
    // Initialize SortedInputMask with UnsortedInputMask.
    SmallVector <int32_t, 4> SortedInputMask = UnsortedInputMask;

    for (uint32_t Index = 0; Index < UnsortedGlueMask.size(); Index++) {
      auto Val = UnsortedGlueMask[Index];
      // Find the position of Val in SortedGlueMask.
      auto Iter = std::find(SortedGlueMask.begin(), SortedGlueMask.end(), Val);
      // if Val is not found in SortedGlueMask check for next value.
      if (Iter == SortedGlueMask.end()) continue;
      // Update the Result.
      int32_t ValIndex = Iter - SortedGlueMask.begin();
      // Make the same udpate into the SortedInputMask from UnsortedInputMask
      SortedInputMask[Index] = UnsortedInputMask[ValIndex];
    }
    return SortedInputMask;
  };

  // Save either ShuffleInst or ExpandedInputVec for usage in codegen.
  void saveIntermediateGlues(CliqueDAG::CliqueShrdPtrType &ClqDAGGlueNodePtr,
                             InputClqNodeShrdPtrType &InputClqNodePtr,
                             InputClqNodeShrdPtrType &PrevInputClqNodePtr,
                             int32_t InputNum, GlueInstUtil &GlueInstU);

  // Add \param GlueInst to the list of instructions to be costed.
  void addToGlueInstsToBeCosted(Value *GlueInst) {
    GlueInstsToBeCosted.push_back(dyn_cast<Instruction>(GlueInst));
  }
  // Print the list of glue instructions to be costed.
  void printGlueInstsToBeCosted() {
    for (Instruction *GlueInst : GlueInstsToBeCosted)
      dbgs() << "   " << *GlueInst << "\n";
  }

  // Update the shuffle mask of the glue (shuffle) instruction to create \param
  // GlueNodeRowPtr from \param InputNodeRowPtr.
  void updateShuffleMask(VecRowPtrType &GlueNodeRowPtr,
                         VecRowPtrType &InputNodeRowPtr,
                         CliqueShrdPtrType& InputClqNodePtr,
                         uint32_t StartMaskIndex,
                         int32_t InputNum,
                         SmallBitVector &MaskAlreadyFound,
                         SmallVector<int32_t> &ShuffleMask,
                         GlueInstUtil &GlueInstU);
  // Update the insert point. The insert point will be the higher insert points
  // of the current and previous input nodes.
  void updateInsertPoint(InputClqNodeShrdPtrType CurrInputClqNodePtr,
                         InputClqNodeShrdPtrType PrevInputClqNodePtr,
                         IRBuilder<> &Builder) {
    auto *CurrInputInsertPoint = CurrInputClqNodePtr->getInsertPoint();
    auto *PrevInputInsertPoint = PrevInputClqNodePtr->getInsertPoint();
    CurrInputInsertPoint->comesBefore(PrevInputInsertPoint) ?
      Builder.SetInsertPoint(PrevInputInsertPoint->getNextNode()) :
      Builder.SetInsertPoint(CurrInputInsertPoint->getNextNode());
    return;
  }
  // Update the current insert point. This is called before a shuffle is
  // created during createGlueInstruction.
  //
  // In case of constant vectors, GlueInputInst1 or GlueInputInst2 can be null.
  // If either of the inputs are null set insert point to the latest of the
  // current insert point and the non-null one. If Both of them are null, no
  // update is required. If both of them are non-null set insert point to the
  // latest among current insert point and both the inputs.
  void updateInsertPoint(Value *GlueInputVector1, Value* GlueInputVector2,
                         IRBuilder<> &Builder) {
    Instruction *CurrInsertPt = &*Builder.GetInsertPoint();
    Instruction *GlueInputInst1 = dyn_cast<Instruction>(GlueInputVector1);
    Instruction *GlueInputInst2 = dyn_cast<Instruction>(GlueInputVector2);
    Instruction *LatestInsertPoint = nullptr;
    if (GlueInputInst1 == nullptr) {
      if (GlueInputInst2 != nullptr) {
        if (CurrInsertPt->comesBefore(GlueInputInst2) ||
            CurrInsertPt == GlueInputInst2) {
          Builder.SetInsertPoint(GlueInputInst2->getNextNode());
        }
      }
    } else if (GlueInputInst2 == nullptr) {
      if (GlueInputInst1 != nullptr)
        if (CurrInsertPt->comesBefore(GlueInputInst1) ||
            CurrInsertPt == GlueInputInst1)
          Builder.SetInsertPoint(GlueInputInst1->getNextNode());
    } else {
      // Both inputs are non-null.
      if (CurrInsertPt->comesBefore(GlueInputInst1) ||
          CurrInsertPt == GlueInputInst1 ||
          CurrInsertPt->comesBefore(GlueInputInst2)||
          CurrInsertPt == GlueInputInst2) {
        GlueInputInst1->comesBefore(GlueInputInst2) ?
          Builder.SetInsertPoint(GlueInputInst2->getNextNode()) :
          Builder.SetInsertPoint(GlueInputInst1->getNextNode());
      }
    }
  }
                         
  // Move the intermediate glue instructions to proper places.
  void moveIntermediatteGlueInsts(CliqueShrdPtrType ClqPtr);

  // Mark the instructions to be deleted in the given \param ClqPtr.
  //
  // All the scalar instructions except the ones which are inputs to other
  // vector instructions are to be deleted. We mark only those instructions
  // which are not be deleted here. Note that ScalarInstsToBeDeleted was
  // initialized to 'true' for all instuctions.
  void markInstructionNotToBeDeleted(Instruction *I) {
    ScalarInstsToBeDeleted.reset(GSLPU->getId(I));
  }

  // Check if the instruction need to be retained in vectorized block.
  bool needToRetainScalarInstruction(Instruction *I) {
    assert(I && "Expecting an instruction");
    switch(I->getOpcode()) {
      case Instruction::Call:
      case Instruction::Alloca:
      case Instruction::ExtractValue:
      case Instruction::InsertValue:
      case Instruction::Resume:
      case Instruction::Fence:
      case Instruction::AtomicRMW:
      case Instruction::AtomicCmpXchg: {
        return true;
      }
    }
    return false;
  }

  // Generate glue instructions for a glue node for which all the available
  // inputs are of single elemennts.
  void createGlueInstsForGlueNodeWithAllSingleInputs(CliqueShrdPtrType&,
                                                     IRBuilder<>&);
  // Convert the vectorized value of this glue node to an extractelement. This
  // is required as otherwise there will be a type mismatch when this vectoriz-
  // ed value is used as an operand of the vectorized value of a vector node.
  //
  // This can happen in the following case.
  //
  // shufflevector <2 x i32> %insert.164, <2 x i32> undef,
  //                                      <1 x i32> zeroinitializer
  Value *convertToExtract(ShuffleVectorInst *GlueInst) {
    ArrayRef <int32_t> Mask = GlueInst->getShuffleMask();
    assert(Mask.size() == 1 && "Mask size is expected to be 1 here\n");
    // Only applicable if the masks size is 1. That means we are getting a
    // single value.Check if mask size is one.
    int32_t ExtractIndex = Mask[0];
    Value *VecOperand = GlueInst->getOperand(0);
    assert(VecOperand && !isa<UndefValue>(VecOperand)
                      && "0perand 0 should not be undef.");
    VectorType *VecTy = dyn_cast<VectorType>(VecOperand->getType());
    assert(VecTy && (ExtractIndex < VecTy->getNumElements()) &&
           "Mask value should be less the size of vector operand.");
    IRBuilder<> Builder(GlueInst/*InsertPoint*/);
    Value *ExtractI = Builder.CreateExtractElement(VecOperand, ExtractIndex);
    return ExtractI;
  }
  // Convert GEP glue nodes to vector nodes.
  bool convertGEPGlueNodesToVectorNodes();
  // Check if this clique as a mix of constants and external values.
  bool hasMixedConstsAndExternals(CliqueShrdPtrType ClqPtr);
  // Create insertelements for an input clique which has a mix of constants
  // and external values. Returns the vectorized values to be set for that glue
  // node.
  Value *createInsertsForGlueNodeWithMixedExternals(CliqueShrdPtrType ClqPtr);
  // Check if we have all exteranal instructions.
  bool hasAllExternalInsts(CliqueShrdPtrType ClqPtr) {
    BasicBlock *CurrBB = GSLPU->getBB();
    SmallVector<Value*, 4> &VecRow = *(ClqPtr->getVecRow());
    for (int32_t Index = 0; Index < VecRow.size(); Index++) {
      Value *V = VecRow[Index];
      // If V is an argument it is an external value.
      if (isa<Argument>(V))
        continue;
      // If V is an instruction not defined in BB, V is external.
      Instruction *I = dyn_cast<Instruction>(V);
      if (!I) return false;
      if (I->getParent() == CurrBB) return false;
    }
    return true;
  }

  // Populates the ScalarToVecInstMap which keeps an entry of the vectorized
  // instruction for each scalar instruction
  void populateScalarToVecInstMap(CliqueShrdPtrType ClqPtr, Value *VecVal);
  void printScalarToVecInstMap();

  // During codegen, to break the cyclic dependency for operands which are
  // available via backedge/same phi, we convert them to poison values.
  // After the codegen, we finally replace those poison values using
  // ScalarToVecInstMap
  void replaceBackEdgeOperandsOfPhi();

public:
  CliqueDAG() = delete;
  CliqueDAG(HierCompatibilityGraph *HCG_, GSLPUtil *GSLPU_)
          : HCG(HCG_), GSLPU(GSLPU_)  {
    // Initialize the id for cliques added to this CliqueDAG.
    CliqueId = 0;
    // Create the dummy root node.
    DummyRoot = std::make_shared<Clique>(CliqueId++, GSLPU);
    // Clear the list of glue nodes.
    GlueNodesList.clear();
    // Initialize the size of CoveredInstructions bit vector to be the size of
    // basic block. All the elements are uncovered initially and hence set the
    // values to be 'false'.
    CoveredInstructions.resize(GSLPU->getRegion()->size(), false);
    ScalarInstsToBeDeleted.clear();
    // Initialize the size of ScalarInstsToBeDeleted to the size of basic block.
    // All Instructions (except terminator instruction) are marked to be deleted
    // initially and hence set the values to be 'true'.
    ScalarInstsToBeDeleted.resize(GSLPU->getRegion()->size(), true);
    // The terminator instruction should not be deleted. So set it to be false.
    // Note that the terminator can be branch, return, invoke, etc...
    ScalarInstsToBeDeleted.reset(GSLPU->getRegion()->size() - 1);
    // Clear the topologically sorted list of nodes.
    TopoSortedNodes.clear();
    // Clear the set storing the GEP vector nodes.
    SingletonGEPVectorNodes.clear();
    // Clear the set of GEP glues which were converted to vector nodes
    GlueGepsConvertedToVec.clear();
    // Clear the set of sub cliques generated so far
    GeneratedSubCliquesSet.clear();
    // Clear and resize the mapping of scalar to vector instruction
    ScalarToVecInstMap.clear();
    ScalarToVecInstMap.resize(GSLPU->getRegion()->size());
    // Clear the VFMix and VWMix.
    VFMix.clear();
    VWMix.clear();
    // Clear the AvailFromMap
    AvailFromMap.clear();
  }

  // Types to check how much the clique has been covered in the CliqueDAG till
  // now.
  enum class Cover { NoCover, Partial, FullCover};

  // A placeholder to store the rectangle coordinates for new clique to split
  // from a parent clique. Since a rectangle can be represented by two
  // cartesian coordinates, Lower and Upper are those two points.
  struct CoordPair {
    struct Coord {
      uint32_t Row; uint32_t Column;
    };
    struct Coord Lower;
    struct Coord Upper;
  };

  // An enum for return type of addNodes function. We use this to determine if
  // a clique can be added in CliqueDAG (CanAdd), cannot be added due to input
  // not available (CantAdd) or should not be added AND should be deleted as it
  // is inducing a cycle in the DAG (CycleInduced).
  enum class AddStatus {CanAdd, CantAdd, CycleInduced};

  // Create CliqueDAG nodes from a multi-row clique.
  AddStatus addNodes(CliquePtrType &ClqPtr, bool Freeze = false);
  // Create a CliqueDAGNode for a particular row of a multi-row clique.
  CliqueShrdPtrType createCliqueDAGNode(VecRowType &VecRow,
                                        Clique::CliqueDAGNodeType NodeType,
                                        Clique::KindType ClqKind,
                                        bool External=false);
  // Get the cost per instructions.
  double getCostPerInst(GSLPCost &Cost) {
    InstructionCost TotalCost =
      Cost.TotalGlueCost + Cost.TotalVectorCost + Cost.TotalLiveoutCost;
    return (double)(TotalCost.getValue().value()) / getNumCovereredInsts();
  }

  // Create Identity shuffle mask. Mask will be updated in \param ShuffleMask.
  void createIdentityShuffleMask(SmallVector<int32_t> &ShuffleMask,
                                 uint32_t MaskSize) {
     // From now on we must use the identity shuffle.
     // TODO: Can we readily create an identity shuffle using a range like
     // 1..n, without using a for loop.
     ShuffleMask.clear();
     for (uint32_t Index = 0; Index < MaskSize; Index++)
       ShuffleMask.push_back(Index);
     return;
  }
  // Create Identity shuffle mask. Mask will be updated in \param ShuffleMask.
  // Same as the above function but vector type is changed.
  void createIdentityShuffleMask(SmallVector<int32_t, 4> &ShuffleMask,
                                 uint32_t MaskSize) {
     // From now on we must use the identity shuffle.
     // TODO: Can we readily create an identity shuffle using a range like
     // 1..n, without using a for loop.
     ShuffleMask.clear();
     for (uint32_t Index = 0; Index < MaskSize; Index++)
       ShuffleMask.push_back(Index);
     return;
  }
  // Get the glue cost of adding set of Cliques (single row) to a partial set
  // partition, represented by this CliqueDAG.
  InstructionCost getGlueCost(CliquePtrType &Clq);
  // Generate the glue instructions referring to the glue nodes generated.
  void createGlueInstructions();

  // Map each value in \param VecRow_ to its row \param VecRow_ where it is
  // available. A value V can be available from multiple rows. The value V is
  // mapped a set containing pointers to these rows.
  //
  // Note that this function has a side effect of setting the Kind of clique.
  // We do this here as any way we need to access each and every values in
  // \param VecRow.
  //
  // We need to store the external and internal nodes in separate maps. This
  // function accepts that info in \param External.
  InputRowShrdPtrType addToValueToRowMap(Clique::VecRowType &VecRow_,
                                         Clique::KindType &ClqKind,
                                         Clique::KindType ParentKind,
                                         Clique::CliqueDAGNodeType NodeType,
                                         bool External=false) {
    // We are using shared_ptr instead of unique_ptr to facilitate multiple
    // values to be mapped to same pointer. If we use unique_pointer we cannot
    // map different values in a row (VecRowPtr_) to the same pointer as the
    // ownership gets transferred to std::set once we std::move it while adding
    // the first value of the row itself. We cannot have the same pointer for
    // the second row.
    auto VecRowPtr = std::make_shared<InputRowType>(VecRow_);
    bool AllConstants = true;
    /// NOTE: This is a special case for ValuesToRowsMap for reduction cliques.
    /// We only add the first entry from VecRow_ in ValuesToRowsMap, since its
    /// that will be the only scalar value available as an output from this
    /// clique. The VecRow_ is arranged in such a way that the first value
    /// represents the addition chain of the entire row for reduction clique.
    if (ParentKind == Clique::KindType::Reduction)
      ValueToRowsMap[VecRow_[0]].push_back(VecRowPtr);
    else {
      // Map each value V to its corresponding set. Change the map to the
      // external value map if \param External is set. Note that though the body
      // of the for loop used below are exactly the same except the map used, we
      // are forced to do this way as we should not make a local copy of the maps
      // as they use shared_ptrs. If we do that the ownerships will move to the
      // copied one and we will lose the values in the global map.
      //
      // Make the VecRow_ with unique elements as we dont want add duplicate
      // entries.
      // FIXME: It is fine to have duplicates if we remove all those while
      // deleting the clique. Need to do something special there. Refer to the
      // FIXME comment in the lambda deleteEntries in removeClqFromCliqueDAG.
      std::set<Value*> VecRowAsSet(VecRow_.begin(), VecRow_.end());
      if (!External) {
        for (Value *V : VecRowAsSet) {
          // If the node is of type GlueFromBackEdge/GlueFromSamePhi, we don't
          // want it to add to the ValueToRowsMap since it is kind of a
          // placeholder for that operand, and hence we don't want to reuse it
          bool DontAdd = NodeType == Clique::CliqueDAGNodeType::GlueFromBackEdge
            || NodeType == Clique::CliqueDAGNodeType::GlueFromSamePhi;
          if (!DontAdd) ValueToRowsMap[V].push_back(VecRowPtr);
          // Set AllConstants to false if at least one value is not a constant.
          if (AllConstants && !isa<Constant>(V))
            AllConstants = false;
        }
      } else {
        for (Value *V : VecRowAsSet) {
          ExternalValueToRowsMap[V].push_back(VecRowPtr);
          // Set AllConstants to false if at least one value is not a constant.
          if (AllConstants && !isa<Constant>(V))
            AllConstants = false;
        }
      }
    }

    // Get the Kind of Clique.
    Value *V0 = VecRow_[0];
    bool IsMemory = isa<LoadInst>(V0) || isa<StoreInst>(V0);
    if (IsMemory)
      ClqKind = Clique::KindType::Memory;
    else if (ParentKind == Clique::KindType::Reduction)
      ClqKind = Clique::KindType::Reduction;
    else if(AllConstants)
      ClqKind = Clique::KindType::Constant;
    else
      ClqKind = Clique::KindType::Arithmetic;

    return VecRowPtr;
  }
  // This function checks if the input row for this is already available in
  // ValToRowsMap. If not mark that row as non-reusable such that we do create a
  // glue node for that and hence not consider while computing glue cost.
  bool createInputNodes(CliqueShrdPtrType ClqDAGNodeShrdPtr,
                        CliquePtrType &ClqPtr, uint32_t RowNum);
  /// This function checks if the input row for this is already available in
  /// ValToRowsMap.
  InputRowShrdPtrType getReusalbeInputRow(InputRowType &OrigInputRow,
                                          bool External);
  // Map an input row shared_ptr \param InputRowShrdPtrType to a CliqueDAGNode
  // \param ClqDAGNodeShrdPtr. This will be useful while creating the input
  // node for another CliqueDAGNode for which this row becomes an input row.
  void addToInputRowToClqDAGNodeMap(InputRowShrdPtrType InputRowShrdPtr,
                                    CliqueShrdPtrType ClqDAGNodeShrdPtr) {
    InputRowPtrToCliqueDAGNodeMap[InputRowShrdPtr] = ClqDAGNodeShrdPtr;
  }
  /// Add newly created \param InputRowShrdPtr for cliques into the list for
  /// references used to delete them.
  void addToRefsToDeleteList(InputRowShrdPtrType InputRowShrdPtr) {
    IRSPRefsToDelete.insert(InputRowShrdPtr);
  }
  /// Add newly created glue instructions to the list for references used to
  /// delete them from BasicBlock.
  /// \param GlueInst Newly created glue instruction.
  void addToGlueNodeInstToDeleteList(Value *GlueInst) {
    GlueNodeInstToDeleteList.push_back(GlueInst);
  }
  /// Delete the unwanted glue instructions.
  void deleteGlueInstructions() {
    while (!GlueNodeInstToDeleteList.empty()) {
      Instruction *I =
        dyn_cast<Instruction>(GlueNodeInstToDeleteList.pop_back_val());
      // We cannot just iterate this list and delete all the entries one by one.
      // The instructions might have uses with an instruction which is not yet
      // deleted. The usual approach of removing an instruction is to mark all
      // its uses as null. These instructions anyways have no use after deleting
      // the clique.
      I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
      I->eraseFromParent();
    }
  }
  /// Clear the InputRows and Glue instructions lists after freezing a clique
  /// into the clique, so that we don't accidentally clear its data structures
  /// later.
  void clearAuxilaryDeleteLists() {
    IRSPRefsToDelete.clear();
    GlueNodeInstToDeleteList.clear();
  }
  // Map each instruction in a Clique Row \param VecRow present in CliqueDAG to
  // the CliqueDAGNode \param ClqDAGNodeShrdPtr. This is useful while creating
  // the mem-dep edges map for each node in CliqueDAG.
  void createInstToCliqueDAGNodeMap(CliqueShrdPtrType ClqDAGNodeShrdPtr,
                                    VecRowType &VecRow) {
    for (Value *V : VecRow) {
      Instruction *I = dyn_cast<Instruction>(V);
      assert(I && "Clique row of type Vector does not "
                  "constitute an instruction!");
      InstrToCliqueDAGNodeMap[I] = ClqDAGNodeShrdPtr;
    }
  }
  // Return true if \param fence instruction is present in a CliqueDAGNode in
  // this CliqueDAG.
  bool isInstClqNodeInCliqueDAG(uint32_t Fence) {
    return (InstrToCliqueDAGNodeMap.count(GSLPU->getInst(Fence)) > 0);
  }
  CompatibilityGraph::DepRelation getDepRelation(uint32_t Id1, uint32_t Id2);
  // Get the input clique node corresponding to the row
  CliqueShrdPtrType getInputClqNodeForRow(
      InputRowShrdPtrType InputRowShrdPtr) {
    return InputRowPtrToCliqueDAGNodeMap[InputRowShrdPtr];
  }
  /// Checks if Value \param V is available from any of the nodes in the current
  /// partial CliqueDAG.
  bool isValueAvailable(Value *V, BasicBlock *BB);
  // This function checks if each of the input values are available from at
  // least one of the input nodes in the partial CliqueDAG constructed so far.
  // If not, we can't consider the entire multi-row clique to be added to the
  // partial CliqueDAG and return false.
  bool isAvailableFromAnyInputNode(InputRowType &OrigInputRow);
  // Add the input nodes for a glue node.
  void addGlueNodeInputs(InputRowType &InputRow,
                         CliqueShrdPtrType &ClqDAGNodeShrdPtr);

  // Reset the list of glue nodes and the list of glue instructions to be
  // costed.
  void resetGlueNodesList() {
    GlueNodesList.clear();
    GlueInstsToBeCosted.clear();
  }
  // Add a glue node to the list of glue nodes.
  void addToGlueNodesList(CliqueShrdPtrType ClqDAGGlueNodePtr) {
    GlueNodesList.push_back(ClqDAGGlueNodePtr);
  }
  // Mark the instructions of a clique as covered if Set and remove them as
  // covered if not Set.
  void markCoveredAs(CliquePtrType &ClqPtr, bool Set);
  // Prin the insturctions which are covered by the CliqueDAG.
  void printCovered() {
    int32_t InstId = CoveredInstructions.find_first();
    while (InstId >= 0) {
      dbgs() << " " << InstId;
      InstId = CoveredInstructions.find_next(InstId);
    }
    dbgs() << "\n";
  }
  // Check if all instructions are covered()
  bool allCovered() {
    return CoveredInstructions.all();
  }
  // Get the number of instructions covered so far.
  int32_t getNumCovereredInsts() {
    return CoveredInstructions.count();
  }

  /// Get the status of cover for instructions in clique \param ClqPtr from
  /// CliqueDAG till now.
  Cover getCoverStatus(CliquePtrType &ClqPtr) {
    bool Covered = false, NotCovered = false;
    // Get instruction vector rows in this clique.
    for (auto InstVector : ClqPtr->getCliqueInstsMatrix()) {
      // Get each instruction ids.
      for (Instruction *I : InstVector) {
        uint32_t InstID = GSLPU->getId(I);
        if (CoveredInstructions[InstID])
          Covered = true;
        else
          NotCovered = true;
      }
    }
    assert(Covered || NotCovered && "Invalid cover status!");
    if (Covered && NotCovered)
      return Cover::Partial;
    if (Covered && !NotCovered)
      return Cover::FullCover;
    if (!Covered && NotCovered)
      return Cover::NoCover;
    return Cover::Partial;
  }

  /// \return true if instruction \param I is already covered in the CliqueDAG,
  /// otherwise false.
  bool isCovered(Instruction *I) {
    return CoveredInstructions[GSLPU->getId(I)];
  }

  // Print the list of glue nodes.
  void printGlueNodesList() {
    for (auto ClqDAGGlueNodePtr : GlueNodesList) {
      ClqDAGGlueNodePtr->printCliqueRows();
    }
  }

  // Print the internal value to row map.
  void printInternalValueToRowMap() {
    for (auto &MapEntry : ValueToRowsMap) {
      Value *KeyV = MapEntry.first;
      RowSetType &RowSet = MapEntry.second;
      dbgs() << "    " << *KeyV << ": ";
      for (auto &VecRowPtr : RowSet) {
        dbgs() << " " << VecRowPtr.get() << " {<";
        for (Value *V : *VecRowPtr)
          dbgs() << *V << ", ";
        dbgs() << ">}, " ;
      }
      dbgs() << "\n";
    }
  }
  // Print the external value to row map.
  void printExternalValueToRowMap() {
    for (auto &MapEntry : ExternalValueToRowsMap) {
      Value *KeyV = MapEntry.first;
      RowSetType &RowSet = MapEntry.second;
      dbgs() << "    " << *KeyV << ": ";
      for (auto &VecRowPtr : RowSet) {
        dbgs() << " " << VecRowPtr.get() << " {<";
        for (Value *V : *VecRowPtr)
          dbgs() << *V << ", ";
        dbgs() << ">}, " ;
      }
      dbgs() << "\n";
    }
  }

  // Print value to row map.
  void printValueToRowMap(bool External = false) {
    dbgs() << "    [\n";
    if (!External)
      printInternalValueToRowMap();
    else
      printExternalValueToRowMap();
    dbgs() << "    ]\n";
  }
  // Print insns to cliqueDAGNode map.
  void printInstToCliqueDAGNodeMap() {
    for (auto &MapEntry : InstrToCliqueDAGNodeMap) {
      Value *KeyVal = MapEntry.first;
      dbgs() << "  "; KeyVal->dump();
      MapEntry.second->printCliqueRows();
    }
  }
  // Print a row.
  void printRow(InputRowType &Row) {
    dbgs() << "<";
    for (Value *V: Row) {
      dbgs() << " " << *V << ",";
    }
    dbgs() << ">\n";
  }

  // Print a partiton of input nodes.
  void printPartition(Clique::InputClqNodesType &InputNodes) {
    for (auto &InputNode: InputNodes) {
      dbgs() << "       "; InputNode->printCliqueRows();
    }
    dbgs() <<"\n";
  }
  // Print a general vector
  void printVector(SmallVector <int32_t, 4> &Vec) {
    dbgs() << "<";
    for (int32_t Idx = 0; Idx < Vec.size(); Idx++) {
      dbgs() << Vec[Idx];
      if (Idx != Vec.size() - 1)
        dbgs() << ",";
    }
    dbgs() << ">\n";
  }
  // Print various statistics of the CliqueDAG
  void printCliqueDAGStats(GSLPCost &Cost) {
    dbgs() << "Total Vector Cost: " << Cost.getTotalVectorCost()
           << "\nTotal Glue Cost: " << Cost.getTotalGlueCost()
           << "\nTotal Liveout Cost: " << Cost.getTotalLiveoutCost()
           << "\nTotal Cost: " << Cost.getTotalCost()
           << "\nNumber of Covered Insts: "
           << getNumCovereredInsts()
           << "\nTotal Cost Per Instruction: " << getCostPerInst(Cost)
           << "\nCovered Instruction Ids: "; printCovered();
  }

  // Function to print the VFMix.
  void printVFMix() {
    dbgs() << "VFMix: ";
    for (auto &VF : VFMix) {
      dbgs() << "(" << VF.first << "," << VF.second << ") ";
    }
    dbgs() << "\n";
  }
  // Function to print the VWMix.
  void printVWMix() {
    dbgs() << "VWMix: ";
    for (auto &VW : VWMix) {
      dbgs() << "(" << VW.first << "," << VW.second << ") ";
    }
    dbgs() << "\n";
  }
  // Function to return the VFMix.
  std::map<int32_t, int32_t> getVFMix() {
    return VFMix;
  }
  // Function to return the VWMix.
  std::map<int32_t, int32_t> getVWMix() {
    return VWMix;
  }


  // Wrapper function to invoke various types of splits.
  bool splitClique(CliquePtrType &Clq, CliqueDAG::Cover &Status);
  // Split cliques into multiple sub cliques if this clique is partially
  // covered.
  void splitClique(CliquePtrType&);
  // Split cliques into multiple sub cliques if a clique's width is not of VF
  bool splitCliqueForVF(CliquePtrType&);
  // Split cliques into multiple sub cliques based on their inputs if a
  // clique's width is not of VF
  bool splitCliqueForVFOnInputs(CliquePtrType&);
  // Split a mutlilevel clique into 2 sub cliques such that inputs for the
  // first clique are available, and for the second clique are not available
  bool splitCliqueTillInputsAvailable(CliquePtrType&);
  // Split cliques into multiple sub cliques if a row of uncovered instructions
  // completely spans the clique width.
  void getMaxHorizonCliques(SmallVector<SmallBitVector>&, uint32_t, uint32_t,
                            SmallVector<struct CoordPair>&);
  // Split reduction clique into only one, multirow clique.
  bool splitReductionClique(CliquePtrType&);
  // Get all possible maximum sub cliques list generated from an initial cover
  // matrix.
  void getMaxSubCliques(SmallVector<SmallBitVector>&, uint32_t, uint32_t,
                        SmallVector<struct CoordPair>&);
  // Check if there are more maximum rectangles that can be identified from
  // this cover matrix.
  bool moreSubCliquesToGen(SmallVector<SmallBitVector>&);
  // Remove a rectangle from cover matrix.
  void removeRectFromMatrix(SmallVector<SmallBitVector>&, struct CoordPair);
  // Generate sub cliques from the parent clique using the list of already
  // identified maximal rectangle cliques.
  void generateSubCliques(CliquePtrType&, SmallVector<struct CoordPair>&);
  // Remove the newly added Clique from CliqueDAG.
  void removeClqFromCliqueDAG(CliquePtrType&);
  // Remove clique's input/output/MemDepInput/MemDepOutput nodes and separate
  // it from CliqueDAG.
  void removeInputOutputNodes(CliqueShrdPtrType);
  /// Print the nodes of the CliqueDAG in DFS order.
  void printCliqueDAG();
  // Populate mem-dep input and output edges mapping for newly added nodes in
  // the CliqueDAG.
  void populateMemDepNodes(CliqueShrdPtrType);
  // Update the Reaches and Reachable set for all of the nodes in the CliqueDAG
  // once a new node is added.
  void updateReachesNReachableSets(CliqueShrdPtrType);
  // Update the Reaches set of all the successors of newly added clique
  // recursively.
  void updateReachesSetOfSuccs(CliqueShrdPtrType, Clique::ClqNodesSetType&);
  // Update the Reachable set of all the predecessors of newly added clique
  // recursively.
  void updateReachableSetOfPreds(CliqueShrdPtrType, Clique::ClqNodesSetType&);
  // Return true once a cycle is detected in the CliqueDAG after adding a new
  // node.
  bool isCycleInduced(CliqueShrdPtrType,
                      std::map<CliqueShrdPtrType, Clique::ClqNodesSetType>&);

  // Functions realted to vector code gen.
  //
  // The function to start the topological sorting of nodes in this CliqueDAG.
  // This will furthe call another version of topoSort which recurively finds
  // the topologically sorted list.
  void topoSort(bool GEPConversionNeeded = true) {
    // Clear the Global list of topologically sorted nodes. This is not a must
    // to do as ideally we should call topoSort only once. But for debugging
    // purposes, we may call topoSort from anywhere. So this should be cleared.
    TopoSortedNodes.clear();
    // Clear the list of singleton GEP vector nodes.
    SingletonGEPVectorNodes.clear();
    // The worklist of nodes.
    SmallVector<CliqueShrdPtrType, 16> Worklist;
    // List which marks if a node is visited or not to avoid recomputation.
    std::set<CliqueIDType> Visited;
    // The worlist is initialized with the DummyRoot.
    Worklist.push_back(DummyRoot);
    // Perform the topological sort. Note that \param TopoSortedNodes is the
    // class variable where the final result will be stored.
    topoSort(Visited, Worklist, TopoSortedNodes, GEPConversionNeeded);
  }

  bool isCycleDetected() {
    // List which marks if a node is visited or not to avoid recomputation.
    std::set<CliqueIDType> Visited;
    // List Stores the DFSSubtree
    std::set<CliqueIDType> DFSSubTree;
    // Perfrom cycle detection.
    return isCycleDetected(DummyRoot, Visited, DFSSubTree);
  }

  bool isCycleDetected(CliqueShrdPtrType ClqPtr,
                       std::set<CliqueIDType> &Visited,
                       std::set<CliqueIDType> &DFSSubTree);

  void topoSort(std::set<CliqueIDType> &Visited,
                SmallVector<CliqueShrdPtrType, 16> &Worklist,
                SmallVector<CliqueShrdPtrType, 16> &Stack, bool);
  // Get a copy of the topologically sorted nodes. Note that we are returning a
  // const reference so that the caller do not update TopoSortedNodes.
  const TopoSortedNodesType& getTopoSortedNodes() { return TopoSortedNodes; }
  
  // Print the topologically sorted list of nodes.
  void printCliqueDAGTopoSorted() {
    const TopoSortedNodesType &Stack = getTopoSortedNodes();
    for (auto &ClqPtr : Stack) {
      CliqueIDType CliqueId = ClqPtr->getCliqueId();
      dbgs() << "    " << CliqueId << " ";
      ClqPtr->printCliqueRows();
    }
  }
  // Print the set of singleton GEP vector nodes.
  void printSingletonGEPVectorNodes() {
    for (auto &ClqPtr : SingletonGEPVectorNodes) {
      CliqueIDType CliqueId = ClqPtr->getCliqueId();
      dbgs() << "    " << CliqueId << " ";
      ClqPtr->printCliqueRows();
    }
  }


  /// Freeze \param \Clq temporarly to the FrozenClqDAG.
  AddStatus tempFreezeClique(CliquePtrType &Clq, GSLPCost &Cost);

  /// Freeze the minumum Clique \param MinClq to the CliqueDAG.
  void freezeMinClique(CliquePtrType &MinClq, GSLPCost &Cost);

  // Permute a clique based on its inputs 
  AddStatus permuteClique(CliquePtrType &Clq);
  // Permute a reduction clique based on its inputs
  AddStatus permuteRedClique(CliquePtrType &Clq);
  // Vector codegen related functions.
  //
  // Generate the vector code for this CliqueDAG.
  void vectorCodegen(bool OptRemarkEnabled=false);
private:
  // Connect a glue node to the DummyRoot, if it has external values as input.
  void connectToDummyRoot(InputRowType &OrigInputRow,
                          CliqueShrdPtrType &ClqDAGGlueNodePtr);
  // Generate the code for a glue node. For more details refer to the comments
  // in the function header.
  void codegenForGlueNode(CliqueShrdPtrType ClqPtr);
  // Generate the code for a vector node. For more details refer to the comments
  // in the function header.
  void codegenForVectorNode(CliqueShrdPtrType ClqPtr);
  // Duplicate the operands to the vector input if required.
  void duplicateInputOperands(CliqueShrdPtrType ClqPtr,
                               SmallVector<Value *, 4> &OperandsToVecInst);
  // Generate the code for a vector node of reduction clique.
  Value* codegenForReduction(CliqueShrdPtrType ClqPtr,
                             SmallVector<Value *, 4> InVecs,
                             Instruction *InsertPt);
  // Combine two reductions if possible.
  bool combineTwoReductions(Value *CurrReduction, Value* PrevReduction,
                              IRBuilder<> &Builder);
  // Check if we can combine multiple reductions.
  bool canCombineMultipleReductions(CliqueShrdPtrType &ClqPtr);
  // This function checks if an input node satisfies certian criteria w.r.t
  // their input indices. For more understanding refer to the example in the
  // header of the function.
  bool areInputIndicesMatching(CliqueShrdPtrType &ClqPtr,
      CliqueShrdPtrType &GlueNode, CliqueShrdPtrType &InputNode, uint32_t Index,
      SmallVector<int32_t, 4> &PrevInputIndices);

  // Combine multiple reductions to vector adds if possible.
  void combineMultipleReductions();

  // We need not cost extracts if those extracts are going to be used in a
  // chain of inserts outside the current block.
  bool allUsersInSameInsertChain(CliqueShrdPtrType &ClqDAGNodeShrdPtr);
  // During glue instruction generation, we could have generated some intermed-
  // iate glue instructions, when the inputs are available from multiple input
  // nodes of a glue node. Now this function process those intermediate glue
  // instructions and replace the operands with corresponding avaialble vector
  // values generated during the codegen.
  void processIntermediateGlueInsts(CliqueShrdPtrType ClqPtr);
  // This function is invoked if we had generated glue instructions using the
  // tree based approach.
  void processTreeBasedIntermediateGlueInsts(CliqueShrdPtrType ClqPtr);
  // Generate extractelement at appropriate insert points for liveout values.
  // There are multiple possibilities here as described below.
  void generateExtractsForLiveouts(CliqueShrdPtrType ClqPtr);
  // Remove the dead scalar instructions. Note that some scalar instructions
  // would be used in the final vector code generated if it turned out to be
  // a single element glue instruction for an other vector node.
  void deleteDeadScalarInstructions() {
    // Deleting from bottom to top to delete the users first.
    for (int32_t InstId = ScalarInstsToBeDeleted.size() - 1; InstId >= 0;
         InstId--) {
      // Check if the instruction was marked to be deleted.
      if (ScalarInstsToBeDeleted.test(InstId)) {
        Instruction *I = GSLPU->getInst(InstId);
        assert(I->getParent() == GSLPU->getBB() && "The instruction to be"
               " deleted must be from the current basic block.");
        DEBUG_WITH_TYPE(DebugCodegen, I->dump());
        if (!I->user_empty())
          I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
        // Erase the instruction.
        I->eraseFromParent();
      }
    }
  }
  // Add \param ClqPtr to the set of singleton GEP vector nodes.
  void addToGEPVectorNodesSet(CliqueShrdPtrType ClqPtr) {
    SingletonGEPVectorNodes.insert(ClqPtr);
  }
  // Check if a GEP vector node is in the set storing the list of singleton
  // GEP vector nodes.
  bool isGEPVectorNodeAdded(CliqueShrdPtrType ClqPtr) {
    return SingletonGEPVectorNodes.count(ClqPtr) > 0;
  }
  // Get the singleton GEP vector node corrsponding a glue node where the GEP
  // as first value is same as that of the GEP in the vector node.
  CliqueShrdPtrType getGEPVectorNode(GetElementPtrInst *GEP) {
    for (auto &ClqPtr : SingletonGEPVectorNodes) {
      if (ClqPtr->getFirstValue() == GEP)
        return ClqPtr;
    }
    return nullptr;
  }
  // Add the Reduction clique as a candidate to be combined for converting into
  // vector additions.
  void addToCandidateRednClqsToCombine(CliqueShrdPtrType &RedClq) {
    CandidateRednClqsToCombine.push_back(RedClq);
  }
  // Clear candidate cliques for combining reduction. Note that it clears the
  // associated set of all indices set too.
  void clearCandidateRednClqsToCombine() {
    CandidateRednClqsToCombine.clear();
    SetOfAllIndices.clear();
  }

  // Adds an Instruction matrix to the set of generate cliques
  void addToGeneratedSubCliquesSet(InstsInCliqueType &InstMat) {
    GeneratedSubCliquesSet.insert(InstMat);
  }

  // Returns true if the given instruction matrix is present in the set of
  // generated sub cliques, returns false otherwise
  bool isPresentSubClique(InstsInCliqueType &InstMat) {
    return GeneratedSubCliquesSet.find(InstMat)!=GeneratedSubCliquesSet.end();
  }
  // Given a clique and its input, returns the type of input(AvailFromBackEdge,
  // AvailFromSamePhi, AvailFromOther)
  AvailFromType getAvailFromType(CliquePtrType &MultiRowClqPtr,
    InputRowType InputRow, int32_t OpNum);

  void reorderInsts();
};

// The Hierarchical Compatibility graph, which is a collection of compatibility
// graphs.
class HierCompatibilityGraph {
public:
  // Type for the cliques stored.
  using CGNodeIDType = uint32_t;
  using CliqueNodeType = SmallVector<CGNodeIDType, 8>;
  using CliquePtrType = std::shared_ptr<Clique>;
  using CliquesType = SmallVector<CliquePtrType, 8>;
  using InstsInCliqueType = SmallVector<SmallVector<Instruction*>>;
  // Option to select which type of cliques to build
  enum class BuildCliqueOptionType {
    All, Arithmetic, Memory, Reduction, Singleton
  };
private:
  // Set of instructions for which CG is constructed
  // For normal GSLP, this set spans the entire BB
  // Refer to the comments in the RegionType class for more info
  RegionType *Region;
  // The pointer to the GSLPUtil SingleTon class. We refer to the common APIs
  // applicable to all classes through this.
  GSLPUtil *GSLPU;
  AliasAnalysis *AA = nullptr;
  // Permuted reduction clique exists in the HCG
  bool PermRedPresent;

  // Vector to store compatibility graphs at each level. The index of the
  // vector is the level of the graph in the heirarchy.
  // TODO: If there is a requirement that given a CG, get the level, change
  // this to a map.
  using CGListType = SmallVector<CompatibilityGraph *, 4>;
  CGListType CGList;
  // Add CG to the list. The level is implicit here.
  void addCG(CompatibilityGraph *CG) { CGList.push_back(CG); }

  // Stores all the cliques generated over all the CGs.
  CliquesType AllCliques;

  // Get the next candidate clique.
  CliquePtrType getNextCandidateClique() {
    if (!AllCliques.empty())
      return AllCliques.pop_back_val();
    return nullptr;
  }

  // Called just before buildSetPartition algorithm
  // Iteraters over all the cliques, and if some clique needs padding
  // creates a copy of it and pads that copy
  // Check the comments at the top of getPadWidth() for details
  void padAllCandidateCliques();

  // Given a clique pointer and a pad width, create a new clique with the
  // PadWidth more number of columns and returns that clique
  // Check the comments at the top of getPadWidth() for details
  CliquePtrType createPaddedClique(CliquePtrType &Clq, uint32_t PadWidth);

  bool BailoutDueToCycle;
public:
  HierCompatibilityGraph(AliasAnalysis  *AA, RegionType *Region_,
  GSLPUtil *GSLPU_): AA(AA), Region(Region_), GSLPU(GSLPU_) {
      BailoutDueToCycle = false;
      PermRedPresent = false;
  }
  // Get the current Region
  RegionType *getRegion() { return Region; }
  // Get the CG at a level.
  CompatibilityGraph *getCGAtLevel(uint32_t Level) { return CGList[Level]; }
  bool getPermRedPresent() { return PermRedPresent; }
  void setPermRedPresent(bool PermRedPresent_) {
    PermRedPresent = PermRedPresent_;
  }
  // Build the Hierarchical Compatibility Graph up to the given level
  // if possible.
  void build(uint32_t MaxLevel = INT_MAX);

  // Build cliques at each level starting from higher level to lower level.
  // (build all types of cliques by default)
  void buildCliques(BuildCliqueOptionType BuildCliqueOption =
                    BuildCliqueOptionType::All);
  // Check if there is at least one clique to process further.
  bool hasAnyClique() {
    return AllCliques.size() != 0;
  }
  // Bailout of vectorization if
  // #Insts coverted by Singleton Cliques/#Total Insts < the given ratio.
  // ie, at least this percentage of instructions should be covered by cliques
  // Done for large BBs only which do not have any non-singleton
  // memory clique
  // Returns true if we have to bailout, returns false otherwise
  bool cliqueMixBailout(int32_t Ratio) {
    // Do not bailout for small BB's
    if (!getRegion()->getLargeBB()) return false;
    // Set of all the instructions coverted by non singleton cliques
    std::set<Instruction*> InstsCovByNonSingleton;
    for (auto &ClqPtr: AllCliques) {
      int32_t Width = ClqPtr->getWidth();
      // Do not bailout if a non-singleton memory clique is present
      if (ClqPtr->isMemory() && Width > 1) return false;
      if (Width == 1) continue;
      auto CliqueInstMatrix = ClqPtr->getCliqueInstsMatrix();
      for (int32_t I = 0, IE = CliqueInstMatrix.size(); I < IE; ++I) {
        for (int32_t J = 0, JE = CliqueInstMatrix[0].size(); J < JE; ++J)
           InstsCovByNonSingleton.insert(CliqueInstMatrix[I][J]);
      }
    }
    // Bailout if the ratio < given ratio
    if (InstsCovByNonSingleton.size() * Ratio < getRegion()->getBB()->size())
      return true;
    return false;
  }
  // Add clique. We will need to use these cliques across multiple classes.
  // Hence we dynamically allocate them using unique_ptr. Be careful that it
  // cannot be copied, but moved and the ownership will get transferred.
  //
  // To maintain the order of instructions in an level 0 arithmetic clique we
  // are sorting it, if the clique is a level 0 arithmetic clique. This
  // generally should facilitate the reuse of glue instructions.
  void addClique(Clique::KindType K_, CliqueNodeType CliqueNodes_,
                 uint32_t Level_, CompatibilityGraph *CG_) {
    // Sort the level 0 arithmetic clique.
    if (Level_ == 0 && K_ == Clique::KindType::Arithmetic) {
      llvm::sort(CliqueNodes_);
    }
    auto ClqPtr = std::make_shared<Clique>(CG_, K_, CliqueNodes_, Level_,GSLPU);
    // While constucting the CliqueDAG, we will be starting to iterate
    // from the back of the list. Here we add the new clique to the back of
    // the list, and finally when all the cliques are added, we'll reverse it
    AllCliques.push_back(std::move(ClqPtr));
  }
  // Add Clique similar to the above method but from a matrix of instructions
  // rather than from CGNodes. We use this while splitting the clique.
  void addClique(Clique::KindType K_, InstsInCliqueType CliqueInstMatrix_,
                 uint32_t Level_, CompatibilityGraph *CG_) {
    auto ClqPtr = std::make_shared<Clique>(CG_, K_, CliqueInstMatrix_, Level_,
                                            GSLPU);
    // The new clique is added at the back of the list. This is because we are
    // iterating from the back of the list in set partitioning but we want to
    // process newly created clique from splitting right away.
    AllCliques.push_back(std::move(ClqPtr));
  }
  // Add a Clique (belonging to the other HCG to this HCG)
  void addClique(CliquePtrType Clq) {
     AllCliques.push_back(std::move(Clq));
  }
  // Get the latest clique added.
  CliquePtrType &getLatestAddedClique() {
    return AllCliques[AllCliques.size() - 1];
  }

  // Create clique rows. Refer to the description of this function for more
  // details.
  void buildCliqueRows();
  // Print the cliques.
  // If PrintInstIds option is true, print the InstIds instead of CGNodeIds
  void printCliques(Clique::KindType K_, bool PrintInstIds = false) {
    // Recall that Cliques is a vector of unique_ptr.
    for (auto &Clq : AllCliques) {
      if (K_ != Clq->getKind())
        continue;
      dbgs() << "    ";
      if (PrintInstIds) Clq->printCliqueRowsWithInstIds();
      else Clq->printClique();
    }
  }
  // Print memory cliques.
  void printMemoryCliques(bool PrintInstIds = false) {
    printCliques(Clique::KindType::Memory, PrintInstIds);
  }
  // Print arithmetic cliques.
  void printArithmeticCliques(bool PrintInstIds = false) {
    printCliques(Clique::KindType::Arithmetic, PrintInstIds);
  }
  // Print reduction cliques.
  void printReductionCliques(bool PrintInstIds = false) {
    printCliques(Clique::KindType::Reduction, PrintInstIds);
  }

  // Print each row of the clique.
  void printCliqueRows() {
    int32_t CliqNo = 0;
    // Recall that Cliques is a vector of unique_ptr.
    for (auto &Clq : AllCliques) {
      dbgs() << "  Clique Id : " << CliqNo << "\n";
      dbgs() << "  Level : " << Clq->getLevel() << "\n";
      Clq->printCliqueRowsWithInstIds();
      Clq->printCliqueRows();
      CliqNo++;
    }
  }

  // Print input row of each row of the clique.
  void printInputRows() {
    int32_t CliqNo = 0;
    for (auto &Clq : AllCliques) {
      dbgs() << "  Clique Id : " << CliqNo << "\n";
      Clq->printInputRows();
      CliqNo++;
    }
  }
  // Set partition related functions follow.
  //
  // Builds the set partition, which is a CliqueDAG. \retrun true if it is
  // profitable to vectorize.
  bool buildSetPartition(CliqueDAG &ClqDAG, GSLPCost &Cost);
  // Set the variable when when a cycle is induced by a single column clique.
  void setBailOutDueToCycle() {
    BailoutDueToCycle = true;
  }
  // Check if there was a cycle induced by a single column clique.
  bool isBailoutDueToCycle() {
    return BailoutDueToCycle;
  }

  // Transfer Arithmetic cliques from HCG to the given vector
  void transferArithmeticCliques(CliquesType &ArithmeticCliques) {
    CliquesType Temp = std::move(AllCliques);
    for (auto &Clq: Temp) {
      if (Clq->getKind() == Clique::KindType::Arithmetic)
        ArithmeticCliques.push_back(std::move(Clq));
      else
        AllCliques.push_back(std::move(Clq));
    }
  }

  // Clear various data structures used.
  ~HierCompatibilityGraph() {
    // Clear the CGList and delete the heap allocated CGs too.
    for (auto *CG: CGList) delete CG;
    CGList.clear();
  }
};

} // end namespace llvm

#endif // LLVM_TRANSFORMS_VECTORIZE_GLOBALSLPVECTORIZE_H
