- Two minor improvements to the MachineInstr class to reduce footprint and

    overhead: Merge 3 parallel vectors into 1, change regsUsed hash_set to be a
    bitvector.  Sped up LLC a little less than 10% in a debug build!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4261 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 66 insertions, 57 deletions

diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 2142447f6c..69eed2d72f 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -12,7 +12,6 @@
 #include "llvm/Target/MachineInstrInfo.h"
 #include "llvm/Annotation.h"
 #include <Support/iterator>
-#include <Support/hash_set>
 class Instruction;
 
 //---------------------------------------------------------------------------
@@ -267,17 +266,26 @@ MachineOperand::InitializeReg(int _regNum, bool isCCReg)
 //      a CALL (if any), and return value of a RETURN.
 //---------------------------------------------------------------------------
 
-class MachineInstr :  public Annotable,         // MachineInstrs are annotable
-                      public NonCopyable {      // Disable copy operations
+class MachineInstr : public Annotable,         // MachineInstrs are annotable
+                     public NonCopyable {      // Disable copy operations
   MachineOpCode    opCode;              // the opcode
   OpCodeMask       opCodeMask;          // extra bits for variants of an opcode
   std::vector<MachineOperand> operands; // the operands
-  std::vector<Value*>   implicitRefs;   // values implicitly referenced by this
-  std::vector<bool>     implicitIsDef;  //  machine instruction (eg, call args)
-  std::vector<bool>     implicitIsDefAndUse;
-  hash_set<int>    regsUsed;            // all machine registers used for this
-                                        //  instruction, including regs used
-                                        //  to save values across the instr.
+
+  struct ImplicitRef {
+    Value *Val;
+    bool isDef, isDefAndUse;
+
+    ImplicitRef(Value *V, bool D, bool DU) : Val(V), isDef(D), isDefAndUse(DU){}
+  };
+
+  // implicitRefs - Values implicitly referenced by this machine instruction
+  // (eg, call args)
+  std::vector<ImplicitRef> implicitRefs;
+
+  // regsUsed - all machine registers used for this instruction, including regs
+  // used to save values across the instruction.  This is a bitset of registers.
+  std::vector<bool> regsUsed;
 public:
   /*ctor*/		MachineInstr	(MachineOpCode _opCode,
 					 OpCodeMask    _opCodeMask = 0x0);
@@ -313,7 +321,7 @@ public:
   //
   // Information about implicit operands of the instruction
   // 
-  unsigned             	getNumImplicitRefs() const{return implicitRefs.size();}
+  unsigned             	getNumImplicitRefs() const{ return implicitRefs.size();}
   
   bool			implicitRefIsDefined(unsigned i) const;
   bool			implicitRefIsDefinedAndUsed(unsigned i) const;
@@ -324,9 +332,15 @@ public:
   //
   // Information about registers used in this instruction
   // 
-  const hash_set<int>&  getRegsUsed    () const { return regsUsed; }
-        hash_set<int>&  getRegsUsed    ()       { return regsUsed; }
+  const std::vector<bool> &getRegsUsed    () const { return regsUsed; }
   
+  // insertUsedReg - Add a register to the Used registers set...
+  void insertUsedReg(unsigned Reg) {
+    if (Reg >= regsUsed.size())
+      regsUsed.resize(Reg+1);
+    regsUsed[Reg] = true;
+  }
+
   //
   // Debugging support
   // 
@@ -477,41 +491,38 @@ MachineInstr::operandIsDefinedAndUsed(unsigned int i) const
 }
 
 inline bool
-MachineInstr::implicitRefIsDefined(unsigned int i) const
+MachineInstr::implicitRefIsDefined(unsigned i) const
 {
-  assert(i < implicitIsDef.size() && "operand out of range!");
-  return implicitIsDef[i];
+  assert(i < implicitRefs.size() && "operand out of range!");
+  return implicitRefs[i].isDef;
 }
 
 inline bool
-MachineInstr::implicitRefIsDefinedAndUsed(unsigned int i) const
+MachineInstr::implicitRefIsDefinedAndUsed(unsigned i) const
 {
-  assert(i < implicitIsDefAndUse.size() && "operand out of range!");
-  return implicitIsDefAndUse[i];
+  assert(i < implicitRefs.size() && "operand out of range!");
+  return implicitRefs[i].isDefAndUse;
 }
 
 inline const Value*
-MachineInstr::getImplicitRef(unsigned int i) const
+MachineInstr::getImplicitRef(unsigned i) const
 {
   assert(i < implicitRefs.size() && "getImplicitRef() out of range!");
-  return implicitRefs[i];
+  return implicitRefs[i].Val;
 }
 
 inline Value*
-MachineInstr::getImplicitRef(unsigned int i)
+MachineInstr::getImplicitRef(unsigned i)
 {
   assert(i < implicitRefs.size() && "getImplicitRef() out of range!");
-  return implicitRefs[i];
+  return implicitRefs[i].Val;
 }
 
 inline void
 MachineInstr::addImplicitRef(Value* val, 
                              bool isDef,
-                             bool isDefAndUse)
-{
-  implicitRefs.push_back(val);
-  implicitIsDef.push_back(isDef);
-  implicitIsDefAndUse.push_back(isDefAndUse);
+                             bool isDefAndUse) {
+  implicitRefs.push_back(ImplicitRef(val, isDef, isDefAndUse));
 }
 
 inline void
@@ -521,9 +532,9 @@ MachineInstr::setImplicitRef(unsigned int i,
                              bool isDefAndUse)
 {
   assert(i < implicitRefs.size() && "setImplicitRef() out of range!");
-  implicitRefs[i] = val;
-  implicitIsDef[i] = isDef;
-  implicitIsDefAndUse[i] = isDefAndUse;
+  implicitRefs[i].Val = val;
+  implicitRefs[i].isDef = isDef;
+  implicitRefs[i].isDefAndUse = isDefAndUse;
 }
 
 inline void
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index 02c25fdd7f..df633c6511 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -82,14 +82,14 @@ MachineInstr::SetMachineOperandReg(unsigned int i,
     operands[i].markDef();
   if (isDefAndUse)
     operands[i].markDefAndUse();
-  regsUsed.insert(regNum);
+  insertUsedReg(regNum);
 }
 
 void
 MachineInstr::SetRegForOperand(unsigned i, int regNum)
 {
   operands[i].setRegForValue(regNum);
-  regsUsed.insert(regNum);
+  insertUsedReg(regNum);
 }
 
 
@@ -111,10 +111,10 @@ MachineInstr::substituteValue(const Value* oldVal, Value* newVal, bool defsOnly)
 
   // Subsitute implicit refs
   for (unsigned i=0, N=implicitRefs.size(); i < N; ++i)
-    if (implicitRefs[i] == oldVal)
+    if (getImplicitRef(i) == oldVal)
       if (!defsOnly || implicitRefIsDefined(i))
         {
-          implicitRefs[i] = newVal;
+          implicitRefs[i].Val = newVal;
           ++numSubst;
         }
 
diff --git a/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp b/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp
index c97028a683..5fc6a4d5c0 100644
--- a/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp
+++ b/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp
@@ -691,10 +691,10 @@ void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
   int scratchReg = -1;
   if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
     {
-      scratchReg = this->getUsableUniRegAtMI(scratchRegType, &LVSetBef,
-                                             MInst, MIBef, MIAft);
+      scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
+                                       MInst, MIBef, MIAft);
       assert(scratchReg != MRI.getInvalidRegNum());
-      MInst->getRegsUsed().insert(scratchReg); 
+      MInst->insertUsedReg(scratchReg); 
     }
   
   if (!isDef || isDefAndUse) {
@@ -774,7 +774,7 @@ int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
         // of copying it to memory and back.  But we have to mark the
         // register as used by this instruction, so it does not get used
         // as a scratch reg. by another operand or anyone else.
-        MInst->getRegsUsed().insert(scratchReg); 
+        MInst->insertUsedReg(scratchReg); 
         MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
         MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
       }
@@ -874,12 +874,11 @@ void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
   // Add the registers already marked as used by the instruction. 
   // This should include any scratch registers that are used to save
   // values across the instruction (e.g., for saving state register values).
-  const hash_set<int>& regsUsed = MInst->getRegsUsed();
-  for (hash_set<int>::const_iterator SI=regsUsed.begin(), SE=regsUsed.end();
-       SI != SE; ++SI)
-    {
+  const vector<bool> &regsUsed = MInst->getRegsUsed();
+  for (unsigned i = 0, e = regsUsed.size(); i != e; ++i)
+    if (regsUsed[i]) {
       unsigned classId = 0;
-      int classRegNum = MRI.getClassRegNum(*SI, classId);
+      int classRegNum = MRI.getClassRegNum(i, classId);
       if (RC->getID() == classId)
         {
           assert(classRegNum < (int) IsColorUsedArr.size() &&
diff --git a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp
index c97028a683..5fc6a4d5c0 100644
--- a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp
+++ b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp
@@ -691,10 +691,10 @@ void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
   int scratchReg = -1;
   if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
     {
-      scratchReg = this->getUsableUniRegAtMI(scratchRegType, &LVSetBef,
-                                             MInst, MIBef, MIAft);
+      scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
+                                       MInst, MIBef, MIAft);
       assert(scratchReg != MRI.getInvalidRegNum());
-      MInst->getRegsUsed().insert(scratchReg); 
+      MInst->insertUsedReg(scratchReg); 
     }
   
   if (!isDef || isDefAndUse) {
@@ -774,7 +774,7 @@ int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
         // of copying it to memory and back.  But we have to mark the
         // register as used by this instruction, so it does not get used
         // as a scratch reg. by another operand or anyone else.
-        MInst->getRegsUsed().insert(scratchReg); 
+        MInst->insertUsedReg(scratchReg); 
         MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
         MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
       }
@@ -874,12 +874,11 @@ void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
   // Add the registers already marked as used by the instruction. 
   // This should include any scratch registers that are used to save
   // values across the instruction (e.g., for saving state register values).
-  const hash_set<int>& regsUsed = MInst->getRegsUsed();
-  for (hash_set<int>::const_iterator SI=regsUsed.begin(), SE=regsUsed.end();
-       SI != SE; ++SI)
-    {
+  const vector<bool> &regsUsed = MInst->getRegsUsed();
+  for (unsigned i = 0, e = regsUsed.size(); i != e; ++i)
+    if (regsUsed[i]) {
       unsigned classId = 0;
-      int classRegNum = MRI.getClassRegNum(*SI, classId);
+      int classRegNum = MRI.getClassRegNum(i, classId);
       if (RC->getID() == classId)
         {
           assert(classRegNum < (int) IsColorUsedArr.size() &&
diff --git a/lib/Target/SparcV9/SparcV9RegInfo.cpp b/lib/Target/SparcV9/SparcV9RegInfo.cpp
index d7b20c032f..65539cf87e 100644
--- a/lib/Target/SparcV9/SparcV9RegInfo.cpp
+++ b/lib/Target/SparcV9/SparcV9RegInfo.cpp
@@ -663,7 +663,7 @@ UltraSparcRegInfo::InitializeOutgoingArg(MachineInstr* CallMI,
     {
       isArgInReg = true;
       UniArgReg = (unsigned) UniArgRegOrNone;
-      CallMI->getRegsUsed().insert(UniArgReg); // mark the reg as used
+      CallMI->insertUsedReg(UniArgReg); // mark the reg as used
     }
   
   if (LR->hasColor()) {
@@ -788,7 +788,7 @@ void UltraSparcRegInfo::colorCallArgs(MachineInstr *CallMI,
     UniRetReg = getUnifiedRegNum(RegClassID, CorrectCol);	
 
     // Mark the register as used by this instruction
-    CallMI->getRegsUsed().insert(UniRetReg);
+    CallMI->insertUsedReg(UniRetReg);
     
     // if the LR received the correct color, NOTHING to do
     recvCorrectColor = RetValLR->hasColor()? RetValLR->getColor() == CorrectCol
@@ -1026,7 +1026,7 @@ void UltraSparcRegInfo::colorRetValue(MachineInstr *RetMI,
     unsigned UniRetReg = getUnifiedRegNum(RegClassID, CorrectCol);
 
     // Mark the register as used by this instruction
-    RetMI->getRegsUsed().insert(UniRetReg);
+    RetMI->insertUsedReg(UniRetReg);
     
     // if the LR received the correct color, NOTHING to do
     
@@ -1433,7 +1433,7 @@ UltraSparcRegInfo::insertCallerSavingCode(vector<MachineInstr*>& instrnsBefore,
                 scratchReg = PRA.getUsableUniRegAtMI(scratchRegType, &LVSetBef,
                                                    CallMI, AdIBef, AdIAft);
                 assert(scratchReg != getInvalidRegNum());
-                CallMI->getRegsUsed().insert(scratchReg); 
+                CallMI->insertUsedReg(scratchReg); 
               }
             
             if (AdIBef.size() > 0)
@@ -1461,7 +1461,7 @@ UltraSparcRegInfo::insertCallerSavingCode(vector<MachineInstr*>& instrnsBefore,
                 scratchReg = PRA.getUsableUniRegAtMI(scratchRegType, &LVSetAft,
                                                  CallMI, AdIBef, AdIAft);
                 assert(scratchReg != getInvalidRegNum());
-                CallMI->getRegsUsed().insert(scratchReg); 
+                CallMI->insertUsedReg(scratchReg); 
               }
             
             if (AdIBef.size() > 0)