Add a new function, ReplaceAllUsesOfValuesWith, which handles bulk

replacement of multiple values. This is slightly more efficient
than doing multiple ReplaceAllUsesOfValueWith calls, and theoretically
could be optimized even further. However, an important property of this
new function is that it handles the case where the source value set and
destination value set overlap. This makes it feasible for isel to use
SelectNodeTo in many very common cases, which is advantageous because
SelectNodeTo avoids a temporary node and it doesn't require CSEMap
updates for users of values that don't change position.

Revamp MorphNodeTo, which is what does all the work of SelectNodeTo, to
handle operand lists more efficiently, and to correctly handle a number
of corner cases to which its new wider use exposes it.

This commit also includes a change to the encoding of post-isel opcodes
in SDNodes; now instead of being sandwiched between the target-independent
pre-isel opcodes and the target-dependent pre-isel opcodes, post-isel
opcodes are now represented as negative values. This makes it possible
to test if an opcode is pre-isel or post-isel without having to know
the size of the current target's post-isel instruction set.

These changes speed up llc overall by 3% and reduce memory usage by 10%
on the InstructionCombining.cpp testcase with -fast and -regalloc=local.

llvm-svn: 53728

11 files changed, 17 insertions, 21 deletions

diff --git a/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp b/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
index 37d647b95ee..2d1136f4363 100644
--- a/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
+++ b/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
@@ -530,9 +530,8 @@ static inline SDOperand getAL(SelectionDAG *CurDAG) {
 
 SDNode *ARMDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  unsigned Opcode = N->getOpcode();
 
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < ARMISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
diff --git a/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp b/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
index 5275f7c5a21..01a6856f079 100644
--- a/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
+++ b/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
@@ -244,8 +244,7 @@ void AlphaDAGToDAGISel::InstructionSelect(SelectionDAG &DAG) {
 // target-specific node if it hasn't already been changed.
 SDNode *AlphaDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < AlphaISD::FIRST_NUMBER) {
+  if (N->isMachineOpcode()) {
     return NULL;   // Already selected.
   }
 
diff --git a/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp b/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
index a672b132ce5..0e935ac35d2 100644
--- a/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
+++ b/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
@@ -587,7 +587,7 @@ SPUDAGToDAGISel::Select(SDOperand Op) {
   MVT OpVT = Op.getValueType();
   SDOperand Ops[8];
 
-  if (Opc >= ISD::BUILTIN_OP_END && Opc < SPUISD::FIRST_NUMBER) {
+  if (N->isMachineOpcode()) {
     return NULL;   // Already selected.
   } else if (Opc == ISD::FrameIndex) {
     // Selects to (add $sp, FI * stackSlotSize)
diff --git a/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp b/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp
index 06f607204c7..8f6840ec941 100644
--- a/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp
@@ -305,8 +305,7 @@ SDNode *IA64DAGToDAGISel::SelectDIV(SDOperand Op) {
 // target-specific node if it hasn't already been changed.
 SDNode *IA64DAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < IA64ISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
diff --git a/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp b/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp
index 0ea146bcf6f..388f5be701a 100644
--- a/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp
+++ b/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp
@@ -205,7 +205,7 @@ Select(SDOperand N)
   #endif
 
   // If we have a custom node, we already have selected!
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < MipsISD::FIRST_NUMBER) {
+  if (Node->isMachineOpcode()) {
     #ifndef NDEBUG
     DOUT << std::string(Indent-2, ' ') << "== ";
     DEBUG(Node->dump(CurDAG));
diff --git a/llvm/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp b/llvm/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp
index 5929675f887..509ba83558d 100644
--- a/llvm/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp
@@ -239,7 +239,7 @@ SDNode* PIC16DAGToDAGISel::Select(SDOperand N)
 #endif
 
   // If we have a custom node, we already have selected!
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < PIC16ISD::FIRST_NUMBER) {
+  if (Node->isMachineOpcode()) {
 #ifndef NDEBUG
     DOUT << std::string(Indent-2, ' ') << "== ";
     DEBUG(Node->dump(CurDAG));
diff --git a/llvm/lib/Target/PowerPC/PPCHazardRecognizers.cpp b/llvm/lib/Target/PowerPC/PPCHazardRecognizers.cpp
index 58df0d6db26..717ce60e51d 100644
--- a/llvm/lib/Target/PowerPC/PPCHazardRecognizers.cpp
+++ b/llvm/lib/Target/PowerPC/PPCHazardRecognizers.cpp
@@ -64,11 +64,11 @@ PPCHazardRecognizer970::GetInstrType(unsigned Opcode,
                                      bool &isFirst, bool &isSingle,
                                      bool &isCracked,
                                      bool &isLoad, bool &isStore) {
-  if (Opcode < ISD::BUILTIN_OP_END) {
+  if ((int)Opcode >= 0) {
     isFirst = isSingle = isCracked = isLoad = isStore = false;
     return PPCII::PPC970_Pseudo;
   }
-  Opcode -= ISD::BUILTIN_OP_END;
+  Opcode = ~Opcode;
   
   const TargetInstrDesc &TID = TII.get(Opcode);
   
@@ -125,7 +125,7 @@ getHazardType(SDNode *Node) {
     GetInstrType(Node->getOpcode(), isFirst, isSingle, isCracked,
                  isLoad, isStore);
   if (InstrType == PPCII::PPC970_Pseudo) return NoHazard;  
-  unsigned Opcode = Node->getOpcode()-ISD::BUILTIN_OP_END;
+  unsigned Opcode = Node->getMachineOpcode();
 
   // We can only issue a PPC970_First/PPC970_Single instruction (such as
   // crand/mtspr/etc) if this is the first cycle of the dispatch group.
@@ -223,7 +223,7 @@ void PPCHazardRecognizer970::EmitInstruction(SDNode *Node) {
     GetInstrType(Node->getOpcode(), isFirst, isSingle, isCracked,
                  isLoad, isStore);
   if (InstrType == PPCII::PPC970_Pseudo) return;  
-  unsigned Opcode = Node->getOpcode()-ISD::BUILTIN_OP_END;
+  unsigned Opcode = Node->getMachineOpcode();
 
   // Update structural hazard information.
   if (Opcode == PPC::MTCTR) HasCTRSet = true;
diff --git a/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
index 09563c4c2af..fb279996462 100644
--- a/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
+++ b/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
@@ -775,8 +775,7 @@ SDNode *PPCDAGToDAGISel::SelectSETCC(SDOperand Op) {
 // target-specific node if it hasn't already been changed.
 SDNode *PPCDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < PPCISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
@@ -962,7 +961,8 @@ SDNode *PPCDAGToDAGISel::Select(SDOperand Op) {
       AddToISelQueue(Offset);
       SDOperand Ops[] = { Offset, Base, Chain };
       // FIXME: PPC64
-      return CurDAG->getTargetNode(Opcode, MVT::i32, MVT::i32,
+      return CurDAG->getTargetNode(Opcode, LD->getValueType(0),
+                                   PPCLowering.getPointerTy(),
                                    MVT::Other, Ops, 3);
     } else {
       assert(0 && "R+R preindex loads not supported yet!");
diff --git a/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp
index df07d510fd0..d1d2b5bdda4 100644
--- a/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp
+++ b/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp
@@ -137,8 +137,7 @@ bool SparcDAGToDAGISel::SelectADDRrr(SDOperand Op, SDOperand Addr,
 
 SDNode *SparcDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < SPISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
diff --git a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
index e646d4d6a01..74100f8362a 100644
--- a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -1159,7 +1159,7 @@ SDNode *X86DAGToDAGISel::Select(SDOperand N) {
   Indent += 2;
 #endif
 
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) {
+  if (Node->isMachineOpcode()) {
 #ifndef NDEBUG
     DOUT << std::string(Indent-2, ' ') << "== ";
     DEBUG(Node->dump(CurDAG));
diff --git a/llvm/lib/Target/X86/X86InstrInfo.cpp b/llvm/lib/Target/X86/X86InstrInfo.cpp
index 2f191ffa4b1..32eb53cb88e 100644
--- a/llvm/lib/Target/X86/X86InstrInfo.cpp
+++ b/llvm/lib/Target/X86/X86InstrInfo.cpp
@@ -2239,11 +2239,11 @@ bool X86InstrInfo::unfoldMemoryOperand(MachineFunction &MF, MachineInstr *MI,
 bool
 X86InstrInfo::unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
                                      SmallVectorImpl<SDNode*> &NewNodes) const {
-  if (!N->isTargetOpcode())
+  if (!N->isMachineOpcode())
     return false;
 
   DenseMap<unsigned*, std::pair<unsigned,unsigned> >::iterator I =
-    MemOp2RegOpTable.find((unsigned*)N->getTargetOpcode());
+    MemOp2RegOpTable.find((unsigned*)N->getMachineOpcode());
   if (I == MemOp2RegOpTable.end())
     return false;
   unsigned Opc = I->second.first;