Switch over from SelectionNodeCSEMap to FoldingSet.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@31240 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 3bd6768..3511b79 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -252,6 +252,144 @@
}
//===----------------------------------------------------------------------===//
+// SDNode Profile Support
+//===----------------------------------------------------------------------===//
+
+/// getNodeIDOpcode - Return the opcode that has been set for this NodeID.
+///
+static unsigned getNodeIDOpcode(FoldingSetNodeID &ID) {
+ return ID.getRawData(0);
+}
+static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
+ ID.AddInteger(OpC);
+}
+
+/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
+/// solely with their pointer.
+void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
+ ID.AddPointer(VTList.VTs);
+}
+
+
+static void AddNodeIDOperand(FoldingSetNodeID &ID, SDOperand Op) {
+ ID.AddPointer(Op.Val);
+ ID.AddInteger(Op.ResNo);
+}
+
+static void AddNodeIDOperands(FoldingSetNodeID &ID) {
+}
+void AddNodeIDOperands(FoldingSetNodeID &ID, SDOperand Op) {
+ AddNodeIDOperand(ID, Op);
+}
+static void AddNodeIDOperands(FoldingSetNodeID &ID,
+ SDOperand Op1, SDOperand Op2) {
+ AddNodeIDOperand(ID, Op1);
+ AddNodeIDOperand(ID, Op2);
+}
+static void AddNodeIDOperands(FoldingSetNodeID &ID,
+ SDOperand Op1, SDOperand Op2, SDOperand Op3) {
+ AddNodeIDOperand(ID, Op1);
+ AddNodeIDOperand(ID, Op2);
+ AddNodeIDOperand(ID, Op3);
+}
+static void AddNodeIDOperands(FoldingSetNodeID &ID,
+ const SDOperand *Ops, unsigned NumOps) {
+ for (; NumOps; --NumOps, ++Ops)
+ AddNodeIDOperand(ID, *Ops);
+}
+
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+ unsigned short OpC, SDVTList VTList) {
+ AddNodeIDOpcode(ID, OpC);
+ AddNodeIDValueTypes(ID, VTList);
+ AddNodeIDOperands(ID);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+ unsigned short OpC, SDVTList VTList,
+ SDOperand Op) {
+ AddNodeIDOpcode(ID, OpC);
+ AddNodeIDValueTypes(ID, VTList);
+ AddNodeIDOperands(ID, Op);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+ unsigned short OpC, SDVTList VTList,
+ SDOperand Op1, SDOperand Op2) {
+ AddNodeIDOpcode(ID, OpC);
+ AddNodeIDValueTypes(ID, VTList);
+ AddNodeIDOperands(ID, Op1, Op2);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+ unsigned short OpC, SDVTList VTList,
+ SDOperand Op1, SDOperand Op2, SDOperand Op3) {
+ AddNodeIDOpcode(ID, OpC);
+ AddNodeIDValueTypes(ID, VTList);
+ AddNodeIDOperands(ID, Op1, Op2);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+ unsigned short OpC, SDVTList VTList,
+ const SDOperand *OpList, unsigned N) {
+ AddNodeIDOpcode(ID, OpC);
+ AddNodeIDValueTypes(ID, VTList);
+ AddNodeIDOperands(ID, OpList, N);
+}
+
+static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
+ AddNodeIDOpcode(ID, N->getOpcode());
+ // Add the return value info.
+ AddNodeIDValueTypes(ID, N->getVTList());
+ // Add the operand info.
+ AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
+
+ // Handle SDNode leafs with special info.
+ if (N->getNumOperands() == 0) {
+ switch (N->getOpcode()) {
+ default: break; // Normal nodes don't need extra info.
+ case ISD::TargetConstant:
+ case ISD::Constant:
+ ID.AddInteger(cast<ConstantSDNode>(N)->getValue());
+ break;
+ case ISD::TargetConstantFP:
+ case ISD::ConstantFP:
+ ID.AddDouble(cast<ConstantFPSDNode>(N)->getValue());
+ break;
+ case ISD::TargetGlobalAddress:
+ case ISD::GlobalAddress:
+ ID.AddPointer(cast<GlobalAddressSDNode>(N)->getGlobal());
+ ID.AddInteger(cast<GlobalAddressSDNode>(N)->getOffset());
+ break;
+ case ISD::BasicBlock:
+ ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
+ break;
+ case ISD::Register:
+ ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
+ break;
+ case ISD::SRCVALUE:
+ ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
+ ID.AddInteger(cast<SrcValueSDNode>(N)->getOffset());
+ break;
+ case ISD::FrameIndex:
+ case ISD::TargetFrameIndex:
+ ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
+ break;
+ case ISD::JumpTable:
+ case ISD::TargetJumpTable:
+ ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
+ break;
+ case ISD::ConstantPool:
+ case ISD::TargetConstantPool:
+ ID.AddInteger(cast<ConstantPoolSDNode>(N)->getAlignment());
+ ID.AddInteger(cast<ConstantPoolSDNode>(N)->getOffset());
+ if (cast<ConstantPoolSDNode>(N)->isMachineConstantPoolEntry())
+ cast<ConstantPoolSDNode>(N)->getMachineCPVal()->
+ AddSelectionDAGCSEId(ID);
+ else
+ ID.AddPointer(cast<ConstantPoolSDNode>(N)->getConstVal());
+ break;
+ }
+ }
+}
+
+//===----------------------------------------------------------------------===//
// SelectionDAG Class
//===----------------------------------------------------------------------===//
@@ -439,10 +577,8 @@
if (N->getValueType(i) == MVT::Flag)
return 0; // Never CSE anything that produces a flag.
- SelectionDAGCSEMap::NodeID ID;
- ID.SetOpcode(N->getOpcode());
- ID.SetValueTypes(N->getVTList());
- ID.SetOperands(Op);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op);
return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
}
@@ -461,10 +597,8 @@
if (N->getValueType(i) == MVT::Flag)
return 0; // Never CSE anything that produces a flag.
- SelectionDAGCSEMap::NodeID ID;
- ID.SetOpcode(N->getOpcode());
- ID.SetValueTypes(N->getVTList());
- ID.SetOperands(Op1, Op2);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op1, Op2);
return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
}
@@ -484,9 +618,9 @@
if (N->getValueType(i) == MVT::Flag)
return 0; // Never CSE anything that produces a flag.
- SelectionDAGCSEMap::NodeID ID;
- ID.SetOpcode(N->getOpcode());
- ID.SetValueTypes(N->getVTList());
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, N->getOpcode(), N->getVTList());
+
if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
ID.AddInteger(LD->getAddressingMode());
ID.AddInteger(LD->getExtensionType());
@@ -504,7 +638,8 @@
ID.AddInteger(ST->getAlignment());
ID.AddInteger(ST->isVolatile());
}
- ID.SetOperands(Ops, NumOps);
+
+ AddNodeIDOperands(ID, Ops, NumOps);
return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
}
@@ -544,7 +679,8 @@
Val &= MVT::getIntVTBitMask(VT);
unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
- SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opc, getVTList(VT));
ID.AddInteger(Val);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -566,8 +702,9 @@
// value, so that we don't have problems with 0.0 comparing equal to -0.0, and
// we don't have issues with SNANs.
unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
- SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
- ID.AddInteger(DoubleToBits(Val));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opc, getVTList(VT));
+ ID.AddDouble(Val);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -581,7 +718,8 @@
MVT::ValueType VT, int Offset,
bool isTargetGA) {
unsigned Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
- SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opc, getVTList(VT));
ID.AddPointer(GV);
ID.AddInteger(Offset);
void *IP = 0;
@@ -596,7 +734,8 @@
SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT,
bool isTarget) {
unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
- SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opc, getVTList(VT));
ID.AddInteger(FI);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -609,7 +748,8 @@
SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){
unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
- SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opc, getVTList(VT));
ID.AddInteger(JTI);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -624,7 +764,8 @@
unsigned Alignment, int Offset,
bool isTarget) {
unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
- SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opc, getVTList(VT));
ID.AddInteger(Alignment);
ID.AddInteger(Offset);
ID.AddPointer(C);
@@ -643,10 +784,11 @@
unsigned Alignment, int Offset,
bool isTarget) {
unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
- SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opc, getVTList(VT));
ID.AddInteger(Alignment);
ID.AddInteger(Offset);
- C->AddSelectionDAGCSEId(&ID);
+ C->AddSelectionDAGCSEId(ID);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -658,7 +800,8 @@
SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
- SelectionDAGCSEMap::NodeID ID(ISD::BasicBlock, getVTList(MVT::Other));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other));
ID.AddPointer(MBB);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -709,7 +852,8 @@
}
SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
- SelectionDAGCSEMap::NodeID ID(ISD::Register, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::Register, getVTList(VT));
ID.AddInteger(RegNo);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -724,7 +868,8 @@
assert((!V || isa<PointerType>(V->getType())) &&
"SrcValue is not a pointer?");
- SelectionDAGCSEMap::NodeID ID(ISD::SRCVALUE, getVTList(MVT::Other));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other));
ID.AddPointer(V);
ID.AddInteger(Offset);
void *IP = 0;
@@ -812,7 +957,8 @@
/// getNode - Gets or creates the specified node.
///
SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
- SelectionDAGCSEMap::NodeID ID(Opcode, getVTList(VT));
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opcode, getVTList(VT));
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -991,7 +1137,8 @@
SDNode *N;
SDVTList VTs = getVTList(VT);
if (VT != MVT::Flag) { // Don't CSE flag producing nodes
- SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Operand);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opcode, VTs, Operand);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -1291,7 +1438,8 @@
SDNode *N;
SDVTList VTs = getVTList(VT);
if (VT != MVT::Flag) {
- SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opcode, VTs, N1, N2);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -1349,7 +1497,8 @@
SDNode *N;
SDVTList VTs = getVTList(VT);
if (VT != MVT::Flag) {
- SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2, N3);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opcode, VTs, N1, N2, N3);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -1386,7 +1535,8 @@
unsigned Alignment = 1;
SDVTList VTs = getVTList(VT, MVT::Other);
SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
- SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef);
ID.AddInteger(ISD::UNINDEXED);
ID.AddInteger(ISD::NON_EXTLOAD);
ID.AddInteger(VT);
@@ -1428,7 +1578,8 @@
unsigned Alignment = 1;
SDVTList VTs = getVTList(VT, MVT::Other);
SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
- SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef);
ID.AddInteger(ISD::UNINDEXED);
ID.AddInteger(ExtType);
ID.AddInteger(EVT);
@@ -1454,7 +1605,8 @@
"Load is already a indexed load!");
MVT::ValueType VT = OrigLoad.getValueType();
SDVTList VTs = getVTList(VT, Base.getValueType(), MVT::Other);
- SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, LD->getChain(), Base, Offset);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::LOAD, VTs, LD->getChain(), Base, Offset);
ID.AddInteger(AM);
ID.AddInteger(LD->getExtensionType());
ID.AddInteger(LD->getLoadedVT());
@@ -1493,7 +1645,8 @@
SDVTList VTs = getVTList(MVT::Other);
SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
SDOperand Ops[] = { Chain, Value, Ptr, Undef };
- SelectionDAGCSEMap::NodeID ID(ISD::STORE, VTs, Ops, 4);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
ID.AddInteger(ISD::UNINDEXED);
ID.AddInteger(false);
ID.AddInteger(VT);
@@ -1528,7 +1681,8 @@
SDVTList VTs = getVTList(MVT::Other);
SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
SDOperand Ops[] = { Chain, Value, Ptr, Undef };
- SelectionDAGCSEMap::NodeID ID(ISD::STORE, VTs, Ops, 4);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
ID.AddInteger(ISD::UNINDEXED);
ID.AddInteger(isTrunc);
ID.AddInteger(SVT);
@@ -1588,7 +1742,8 @@
SDNode *N;
SDVTList VTs = getVTList(VT);
if (VT != MVT::Flag) {
- SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Ops, NumOps);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -1649,10 +1804,8 @@
// Memoize the node unless it returns a flag.
SDNode *N;
if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
- SelectionDAGCSEMap::NodeID ID;
- ID.SetOpcode(Opcode);
- ID.SetValueTypes(VTList);
- ID.SetOperands(&Ops[0], NumOps);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
void *IP = 0;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDOperand(E, 0);
@@ -1872,7 +2025,8 @@
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
MVT::ValueType VT) {
SDVTList VTs = getVTList(VT);
- SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs);
void *IP = 0;
if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
return ON;
@@ -1890,7 +2044,8 @@
MVT::ValueType VT, SDOperand Op1) {
// If an identical node already exists, use it.
SDVTList VTs = getVTList(VT);
- SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1);
void *IP = 0;
if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
return ON;
@@ -1908,7 +2063,8 @@
SDOperand Op2) {
// If an identical node already exists, use it.
SDVTList VTs = getVTList(VT);
- SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
void *IP = 0;
if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
return ON;
@@ -1927,8 +2083,8 @@
SDOperand Op2, SDOperand Op3) {
// If an identical node already exists, use it.
SDVTList VTs = getVTList(VT);
- SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs,
- Op1, Op2, Op3);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2, Op3);
void *IP = 0;
if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
return ON;
@@ -1947,9 +2103,8 @@
unsigned NumOps) {
// If an identical node already exists, use it.
SDVTList VTs = getVTList(VT);
- SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
- for (unsigned i = 0; i != NumOps; ++i)
- ID.AddOperand(Ops[i]);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
void *IP = 0;
if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
return ON;
@@ -1967,7 +2122,8 @@
MVT::ValueType VT1, MVT::ValueType VT2,
SDOperand Op1, SDOperand Op2) {
SDVTList VTs = getVTList(VT1, VT2);
- SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
void *IP = 0;
if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
return ON;
@@ -1987,8 +2143,8 @@
SDOperand Op3) {
// If an identical node already exists, use it.
SDVTList VTs = getVTList(VT1, VT2);
- SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs,
- Op1, Op2, Op3);
+ FoldingSetNodeID ID;
+ AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2, Op3);
void *IP = 0;
if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
return ON;
@@ -2311,6 +2467,12 @@
void SDNode::ANCHOR() {
}
+/// Profile - Gather unique data for the node.
+///
+void SDNode::Profile(FoldingSetNodeID &ID) {
+ AddNodeIDNode(ID, this);
+}
+
/// getValueTypeList - Return a pointer to the specified value type.
///
MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp
deleted file mode 100644
index 498e9ef..0000000
--- a/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp
+++ /dev/null
@@ -1,350 +0,0 @@
-//===-- SelectionDAGCSEMap.cpp - Implement the SelectionDAG CSE Map -------===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file was developed by Chris Lattner and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This implements the SelectionDAGCSEMap class.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/CodeGen/SelectionDAG.h"
-#include "llvm/CodeGen/MachineConstantPool.h"
-#include "llvm/Support/MathExtras.h"
-using namespace llvm;
-
-//===----------------------------------------------------------------------===//
-// SelectionDAGCSEMap::NodeID Implementation
-
-/// SetValueTypes - Value type lists are intern'd so we can represent them
-/// solely with their pointer.
-void SelectionDAGCSEMap::NodeID::SetValueTypes(SDVTList VTList) {
- AddPointer(VTList.VTs);
-}
-
-SelectionDAGCSEMap::NodeID::NodeID(SDNode *N) {
- SetOpcode(N->getOpcode());
- // Add the return value info.
- SetValueTypes(N->getVTList());
- // Add the operand info.
- SetOperands(N->op_begin(), N->getNumOperands());
-
- // Handle SDNode leafs with special info.
- if (N->getNumOperands() == 0) {
- switch (N->getOpcode()) {
- default: break; // Normal nodes don't need extra info.
- case ISD::TargetConstant:
- case ISD::Constant:
- AddInteger(cast<ConstantSDNode>(N)->getValue());
- break;
- case ISD::TargetConstantFP:
- case ISD::ConstantFP:
- AddInteger(DoubleToBits(cast<ConstantFPSDNode>(N)->getValue()));
- break;
- case ISD::TargetGlobalAddress:
- case ISD::GlobalAddress:
- AddPointer(cast<GlobalAddressSDNode>(N)->getGlobal());
- AddInteger(cast<GlobalAddressSDNode>(N)->getOffset());
- break;
- case ISD::BasicBlock:
- AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
- break;
- case ISD::Register:
- AddInteger(cast<RegisterSDNode>(N)->getReg());
- break;
- case ISD::SRCVALUE:
- AddPointer(cast<SrcValueSDNode>(N)->getValue());
- AddInteger(cast<SrcValueSDNode>(N)->getOffset());
- break;
- case ISD::FrameIndex:
- case ISD::TargetFrameIndex:
- AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
- break;
- case ISD::JumpTable:
- case ISD::TargetJumpTable:
- AddInteger(cast<JumpTableSDNode>(N)->getIndex());
- break;
- case ISD::ConstantPool:
- case ISD::TargetConstantPool:
- AddInteger(cast<ConstantPoolSDNode>(N)->getAlignment());
- AddInteger(cast<ConstantPoolSDNode>(N)->getOffset());
- if (cast<ConstantPoolSDNode>(N)->isMachineConstantPoolEntry())
- cast<ConstantPoolSDNode>(N)->getMachineCPVal()->
- AddSelectionDAGCSEId(this);
- else
- AddPointer(cast<ConstantPoolSDNode>(N)->getConstVal());
- break;
- }
- }
-}
-
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList) {
- SetOpcode(ID);
- SetValueTypes(VTList);
- SetOperands();
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList,
- SDOperand Op) {
- SetOpcode(ID);
- SetValueTypes(VTList);
- SetOperands(Op);
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList,
- SDOperand Op1, SDOperand Op2) {
- SetOpcode(ID);
- SetValueTypes(VTList);
- SetOperands(Op1, Op2);
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList,
- SDOperand Op1, SDOperand Op2,
- SDOperand Op3) {
- SetOpcode(ID);
- SetValueTypes(VTList);
- SetOperands(Op1, Op2, Op3);
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList,
- const SDOperand *OpList, unsigned N) {
- SetOpcode(ID);
- SetValueTypes(VTList);
- SetOperands(OpList, N);
-}
-
-void SelectionDAGCSEMap::NodeID::AddPointer(const void *Ptr) {
- // Note: this adds pointers to the hash using sizes and endianness that depend
- // on the host. It doesn't matter however, because hashing on pointer values
- // in inherently unstable. Nothing in the SelectionDAG should depend on the
- // ordering of nodes in the CSEMap.
- intptr_t PtrI = (intptr_t)Ptr;
- Bits.push_back(unsigned(PtrI));
- if (sizeof(intptr_t) > sizeof(unsigned))
- Bits.push_back(unsigned(uint64_t(PtrI) >> 32));
-}
-
-void SelectionDAGCSEMap::NodeID::AddOperand(SDOperand Op) {
- AddPointer(Op.Val);
- Bits.push_back(Op.ResNo);
-}
-
-void SelectionDAGCSEMap::NodeID::SetOperands(const SDOperand *Ops,
- unsigned NumOps) {
- for (; NumOps; --NumOps, ++Ops)
- AddOperand(*Ops);
-}
-
-
-/// ComputeHash - Compute a strong hash value for this NodeID, for lookup in
-/// the SelectionDAGCSEMap.
-unsigned SelectionDAGCSEMap::NodeID::ComputeHash() const {
- // This is adapted from SuperFastHash by Paul Hsieh.
- unsigned Hash = Bits.size();
- for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) {
- unsigned Data = *BP;
- Hash += Data & 0xFFFF;
- unsigned Tmp = ((Data >> 16) << 11) ^ Hash;
- Hash = (Hash << 16) ^ Tmp;
- Hash += Hash >> 11;
- }
-
- // Force "avalanching" of final 127 bits.
- Hash ^= Hash << 3;
- Hash += Hash >> 5;
- Hash ^= Hash << 4;
- Hash += Hash >> 17;
- Hash ^= Hash << 25;
- Hash += Hash >> 6;
- return Hash;
-}
-
-bool SelectionDAGCSEMap::NodeID::operator==(const NodeID &RHS) const {
- if (Bits.size() != RHS.Bits.size()) return false;
- return memcmp(&Bits[0], &RHS.Bits[0], Bits.size()*sizeof(Bits[0])) == 0;
-}
-
-
-//===----------------------------------------------------------------------===//
-// SelectionDAGCSEMap Implementation
-
-SelectionDAGCSEMap::SelectionDAGCSEMap() : NumNodes(0) {
- NumBuckets = 64;
- Buckets = new void*[NumBuckets];
- memset(Buckets, 0, NumBuckets*sizeof(void*));
-}
-SelectionDAGCSEMap::~SelectionDAGCSEMap() {
- delete [] Buckets;
-}
-
-/// GetNextPtr - In order to save space, each bucket is a singly-linked-list. In
-/// order to make deletion more efficient, we make the list circular, so we can
-/// delete a node without computing its hash. The problem with this is that the
-/// start of the hash buckets are not SDNodes. If NextInBucketPtr is a bucket
-/// pointer, this method returns null: use GetBucketPtr when this happens.
-SDNode *SelectionDAGCSEMap::GetNextPtr(void *NextInBucketPtr) {
- if (NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets+NumBuckets)
- return 0;
- return static_cast<SDNode*>(NextInBucketPtr);
-}
-
-/// GetNextPtr - This is just like the previous GetNextPtr implementation, but
-/// allows a bucket array to be specified.
-SDNode *SelectionDAGCSEMap::GetNextPtr(void *NextInBucketPtr, void **Bucks,
- unsigned NumBuck) {
- if (NextInBucketPtr >= Bucks && NextInBucketPtr < Bucks+NumBuck)
- return 0;
- return static_cast<SDNode*>(NextInBucketPtr);
-}
-
-void **SelectionDAGCSEMap::GetBucketPtr(void *NextInBucketPtr) {
- //assert(NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets+NumBuckets &&
- // "NextInBucketPtr is not a bucket ptr");
- return static_cast<void**>(NextInBucketPtr);
-}
-
-/// GetBucketFor - Hash the specified node ID and return the hash bucket for the
-/// specified ID.
-void **SelectionDAGCSEMap::GetBucketFor(const NodeID &ID) const {
- // NumBuckets is always a power of 2.
- unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1);
- return Buckets+BucketNum;
-}
-
-/// GrowHashTable - Double the size of the hash table and rehash everything.
-///
-void SelectionDAGCSEMap::GrowHashTable() {
- void **OldBuckets = Buckets;
- unsigned OldNumBuckets = NumBuckets;
- NumBuckets <<= 1;
-
- // Reset the node count to zero: we're going to reinsert everything.
- NumNodes = 0;
-
- // Clear out new buckets.
- Buckets = new void*[NumBuckets];
- memset(Buckets, 0, NumBuckets*sizeof(void*));
-
- // Walk the old buckets, rehashing nodes into their new place.
- for (unsigned i = 0; i != OldNumBuckets; ++i) {
- void *Probe = OldBuckets[i];
- if (!Probe) continue;
- while (SDNode *NodeInBucket = GetNextPtr(Probe, OldBuckets, OldNumBuckets)){
- // Figure out the next link, remove NodeInBucket from the old link.
- Probe = NodeInBucket->getNextInBucket();
- NodeInBucket->SetNextInBucket(0);
-
- // Insert the node into the new bucket, after recomputing the hash.
- InsertNode(NodeInBucket, GetBucketFor(NodeID(NodeInBucket)));
- }
- }
-
- delete[] OldBuckets;
-}
-
-/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
-/// return it. If not, return the insertion token that will make insertion
-/// faster.
-SDNode *SelectionDAGCSEMap::FindNodeOrInsertPos(const NodeID &ID,
- void *&InsertPos) {
- void **Bucket = GetBucketFor(ID);
- void *Probe = *Bucket;
-
- InsertPos = 0;
-
- unsigned Opc = ID.getOpcode();
- while (SDNode *NodeInBucket = GetNextPtr(Probe)) {
- // If we found a node with the same opcode, it might be a matching node.
- // Because it is in the same bucket as this one, we know the hash values
- // match. Compute the NodeID for the possible match and do a final compare.
- if (NodeInBucket->getOpcode() == Opc) {
- NodeID OtherID(NodeInBucket);
- if (OtherID == ID)
- return NodeInBucket;
- }
-
- Probe = NodeInBucket->getNextInBucket();
- }
-
- // Didn't find the node, return null with the bucket as the InsertPos.
- InsertPos = Bucket;
- return 0;
-}
-
-/// InsertNode - Insert the specified node into the CSE Map, knowing that it
-/// is not already in the map. InsertPos must be obtained from
-/// FindNodeOrInsertPos.
-void SelectionDAGCSEMap::InsertNode(SDNode *N, void *InsertPos) {
- ++NumNodes;
- // Do we need to grow the hashtable?
- if (NumNodes > NumBuckets*2) {
- GrowHashTable();
- InsertPos = GetBucketFor(NodeID(N));
- }
-
- /// The insert position is actually a bucket pointer.
- void **Bucket = static_cast<void**>(InsertPos);
-
- void *Next = *Bucket;
-
- // If this is the first insertion into this bucket, its next pointer will be
- // null. Pretend as if it pointed to itself.
- if (Next == 0)
- Next = Bucket;
-
- // Set the nodes next pointer, and make the bucket point to the node.
- N->SetNextInBucket(Next);
- *Bucket = N;
-}
-
-
-/// RemoveNode - Remove a node from the CSE map, returning true if one was
-/// removed or false if the node was not in the CSE map.
-bool SelectionDAGCSEMap::RemoveNode(SDNode *N) {
-
- // Because each bucket is a circular list, we don't need to compute N's hash
- // to remove it. Chase around the list until we find the node (or bucket)
- // which points to N.
- void *Ptr = N->getNextInBucket();
- if (Ptr == 0) return false; // Not in CSEMap.
-
- --NumNodes;
-
- void *NodeNextPtr = Ptr;
- N->SetNextInBucket(0);
- while (1) {
- if (SDNode *NodeInBucket = GetNextPtr(Ptr)) {
- // Advance pointer.
- Ptr = NodeInBucket->getNextInBucket();
-
- // We found a node that points to N, change it to point to N's next node,
- // removing N from the list.
- if (Ptr == N) {
- NodeInBucket->SetNextInBucket(NodeNextPtr);
- return true;
- }
- } else {
- void **Bucket = GetBucketPtr(Ptr);
- Ptr = *Bucket;
-
- // If we found that the bucket points to N, update the bucket to point to
- // whatever is next.
- if (Ptr == N) {
- *Bucket = NodeNextPtr;
- return true;
- }
- }
- }
-}
-
-/// GetOrInsertSimpleNode - If there is an existing simple SDNode exactly
-/// equal to the specified node, return it. Otherwise, insert 'N' and it
-/// instead. This only works on *simple* SDNodes, not ConstantSDNode or any
-/// other classes derived from SDNode.
-SDNode *SelectionDAGCSEMap::GetOrInsertNode(SDNode *N) {
- SelectionDAGCSEMap::NodeID ID(N);
- void *IP;
- if (SDNode *E = FindNodeOrInsertPos(ID, IP))
- return E;
- InsertNode(N, IP);
- return N;
-}