class SelectionDAG {
const TargetMachine &TM;
const TargetLowering &TLI;
const TargetSelectionDAGInfo &TSI;
MachineFunction *MF;
LLVMContext *Context;
CodeGenOpt::Level OptLevel;

SDNode EntryNode;
// Root - The root of the entire DAG.
SDValue Root;

// AllNodes - A linked list of nodes in the current DAG.
ilist<SDNode> AllNodes;

// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use

typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
AlignOf<MostAlignedSDNode>::Alignment>
NodeAllocatorType;

BumpPtrAllocator OperandAllocator;

BumpPtrAllocator Allocator;

SDNodeOrdering *Ordering;

public:

struct DAGUpdateListener {

DAGUpdateListener *const Next;

SelectionDAG &DAG;

explicit DAGUpdateListener(SelectionDAG &D)
: Next(D.UpdateListeners), DAG(D) {
DAG.UpdateListeners = this;
}

private:

friend struct DAGUpdateListener;

DAGUpdateListener *UpdateListeners;


void init(MachineFunction &mf);

// Function to set root node of SelectionDAG
const SDValue &setRoot(SDValue N) {
  assert((!N.getNode() || N.getValueType() == MVT::Other) &&
    "DAG root value is not a chain!");
  if (N.getNode())
    checkForCycles(N.getNode());
  Root = N;
  if (N.getNode())
    checkForCycles(this);
  return Root;
}

void Combine(CombineLevel Level, AliasAnalysis &AA,
CodeGenOpt::Level OptLevel);

SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);

SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);

SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT, int64_t offset = 0, bool isTargetGA = false, 
unsigned char TargetFlags = 0);

SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);

SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
unsigned char TargetFlags = 0);

// Function to return Basic Block corresponding to this MachineBasicBlock
SDValue getBasicBlock(MachineBasicBlock *MBB);

SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);

SDValue getExternalSymbol(const char *Sym, EVT VT);

SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);

SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
unsigned char TargetFlags = 0);

// Return the type of the value this SelectionDAG node corresponds // to
SDValue getValueType(EVT);

SDValue getRegister(unsigned Reg, EVT VT);

SDValue getRegisterMask(const uint32_t *RegMask);

SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);

SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
int64_t Offset = 0, bool isTarget = false,
unsigned char TargetFlags = 0);

SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);

SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);

SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);

SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);

// Function to get SelectionDAG node.
SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);

SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);

SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);

SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
SDValue N1, SDValue N2, SDValue N3);

SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
MachinePointerInfo DstPtrInfo,MachinePointerInfo SrcPtrInfo);

SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
SDValue Ptr, SDValue Cmp, SDValue Swp,
MachinePointerInfo PtrInfo, unsigned Alignment,
AtomicOrdering Ordering,
SynchronizationScope SynchScope);

SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);

SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);

SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
SDValue Op3);

SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);

SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);

SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
SDValue Op1, SDValue Op2);

MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
SDValue Op1);

MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
SDValue Op1, SDValue Op2);

void ReplaceAllUsesWith(SDValue From, SDValue Op);

void ReplaceAllUsesWith(SDNode *From, SDNode *To);

void ReplaceAllUsesWith(SDNode *From, const SDValue *To);

bool isBaseWithConstantOffset(SDValue Op) const;

bool isKnownNeverNaN(SDValue Op) const;

bool isKnownNeverZero(SDValue Op) const;

bool isEqualTo(SDValue A, SDValue B) const;

SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);

bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,

unsigned Bytes, int Dist) const;

unsigned InferPtrAlignment(SDValue Ptr) const;

private:

bool RemoveNodeFromCSEMaps(SDNode *N);

void AddModifiedNodeToCSEMaps(SDNode *N);

SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);

SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
void *&InsertPos);

SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,void *&InsertPos);

SDNode *UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc loc);

void DeleteNodeNotInCSEMaps(SDNode *N);

void DeallocateNode(SDNode *N);

unsigned getEVTAlignment(EVT MemoryVT) const;

void allnodes_clear();

std::vector<SDVTList> VTList;

std::vector<CondCodeSDNode*> CondCodeNodes;

std::vector<SDNode*> ValueTypeNodes;

std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;

StringMap<SDNode*> ExternalSymbols;

std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
};