Use ArrayRecycler for MachineInstr operand lists.

Instead of an std::vector<MachineOperand>, use MachineOperand arrays
from an ArrayRecycler living in MachineFunction.

This has several advantages:

- MachineInstr now has a trivial destructor, making it possible to
  delete them in batches when destroying MachineFunction. This will be
  enabled in a later patch.

- Bypassing malloc() and free() can be faster, depending on the system
  library.

- MachineInstr objects and their operands are allocated from the same
  BumpPtrAllocator, so they will usually be next to each other in
  memory, providing better locality of reference.

- Reduce MachineInstr footprint. A std::vector is 24 bytes, the new
  operand array representation only uses 8+4+1 bytes in MachineInstr.

- Better control over operand array reallocations. In the old
  representation, the use-def chains would be reordered whenever a
  std::vector reached its capacity. The new implementation never changes
  the use-def chain order.

Note that some decisions in the code generator depend on the use-def
chain orders, so this patch may cause different assembly to be produced
in a few cases.

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

3 files changed, 39 insertions, 9 deletions

diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h
index bb5b23b00c..cd704c1c53 100644
--- a/include/llvm/CodeGen/MachineFunction.h
+++ b/include/llvm/CodeGen/MachineFunction.h
@@ -21,6 +21,7 @@
 #include "llvm/ADT/ilist.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/Support/Allocator.h"
+#include "llvm/Support/ArrayRecycler.h"
 #include "llvm/Support/DebugLoc.h"
 #include "llvm/Support/Recycler.h"
 
@@ -105,6 +106,9 @@ class MachineFunction {
   // Allocation management for instructions in function.
   Recycler<MachineInstr> InstructionRecycler;
 
+  // Allocation management for operand arrays on instructions.
+  ArrayRecycler<MachineOperand> OperandRecycler;
+
   // Allocation management for basic blocks in function.
   Recycler<MachineBasicBlock> BasicBlockRecycler;
 
@@ -394,6 +398,21 @@ public:
   MachineMemOperand *getMachineMemOperand(const MachineMemOperand *MMO,
                                           int64_t Offset, uint64_t Size);
 
+  typedef ArrayRecycler<MachineOperand>::Capacity OperandCapacity;
+
+  /// Allocate an array of MachineOperands. This is only intended for use by
+  /// internal MachineInstr functions.
+  MachineOperand *allocateOperandArray(OperandCapacity Cap) {
+    return OperandRecycler.allocate(Cap, Allocator);
+  }
+
+  /// Dellocate an array of MachineOperands and recycle the memory. This is
+  /// only intended for use by internal MachineInstr functions.
+  /// Cap must be the same capacity that was used to allocate the array.
+  void deallocateOperandArray(OperandCapacity Cap, MachineOperand *Array) {
+    OperandRecycler.deallocate(Cap, Array);
+  }
+
   /// allocateMemRefsArray - Allocate an array to hold MachineMemOperand
   /// pointers.  This array is owned by the MachineFunction.
   MachineInstr::mmo_iterator allocateMemRefsArray(unsigned long Num);
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 4af48f74d7..3c7b213533 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -25,6 +25,7 @@
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/MC/MCInstrDesc.h"
+#include "llvm/Support/ArrayRecycler.h"
 #include "llvm/Support/DebugLoc.h"
 #include "llvm/Target/TargetOpcodes.h"
 #include <vector>
@@ -63,6 +64,13 @@ public:
   };
 private:
   const MCInstrDesc *MCID;              // Instruction descriptor.
+  MachineBasicBlock *Parent;            // Pointer to the owning basic block.
+
+  // Operands are allocated by an ArrayRecycler.
+  MachineOperand *Operands;             // Pointer to the first operand.
+  unsigned NumOperands;                 // Number of operands on instruction.
+  typedef ArrayRecycler<MachineOperand>::Capacity OperandCapacity;
+  OperandCapacity CapOperands;          // Capacity of the Operands array.
 
   uint8_t Flags;                        // Various bits of additional
                                         // information about machine
@@ -78,8 +86,6 @@ private:
   uint16_t NumMemRefs;                  // information on memory references
   mmo_iterator MemRefs;
 
-  std::vector<MachineOperand> Operands; // the operands
-  MachineBasicBlock *Parent;            // Pointer to the owning basic block.
   DebugLoc debugLoc;                    // Source line information.
 
   MachineInstr(const MachineInstr&) LLVM_DELETED_FUNCTION;
@@ -252,7 +258,7 @@ public:
 
   /// Access to explicit operands of the instruction.
   ///
-  unsigned getNumOperands() const { return (unsigned)Operands.size(); }
+  unsigned getNumOperands() const { return NumOperands; }
 
   const MachineOperand& getOperand(unsigned i) const {
     assert(i < getNumOperands() && "getOperand() out of range!");
@@ -268,14 +274,14 @@ public:
   unsigned getNumExplicitOperands() const;
 
   /// iterator/begin/end - Iterate over all operands of a machine instruction.
-  typedef std::vector<MachineOperand>::iterator mop_iterator;
-  typedef std::vector<MachineOperand>::const_iterator const_mop_iterator;
+  typedef MachineOperand *mop_iterator;
+  typedef const MachineOperand *const_mop_iterator;
 
-  mop_iterator operands_begin() { return Operands.begin(); }
-  mop_iterator operands_end() { return Operands.end(); }
+  mop_iterator operands_begin() { return Operands; }
+  mop_iterator operands_end() { return Operands + NumOperands; }
 
-  const_mop_iterator operands_begin() const { return Operands.begin(); }
-  const_mop_iterator operands_end() const { return Operands.end(); }
+  const_mop_iterator operands_begin() const { return Operands; }
+  const_mop_iterator operands_end() const { return Operands + NumOperands; }
 
   /// Access to memory operands of the instruction
   mmo_iterator memoperands_begin() const { return MemRefs; }
diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h
index 606833cd40..66a56ed464 100644
--- a/include/llvm/CodeGen/MachineOperand.h
+++ b/include/llvm/CodeGen/MachineOperand.h
@@ -35,6 +35,11 @@ class MCSymbol;
 
 /// MachineOperand class - Representation of each machine instruction operand.
 ///
+/// This class isn't a POD type because it has a private constructor, but its
+/// destructor must be trivial. Functions like MachineInstr::addOperand(),
+/// MachineRegisterInfo::moveOperands(), and MF::DeleteMachineInstr() depend on
+/// not having to call the MachineOperand destructor.
+///
 class MachineOperand {
 public:
   enum MachineOperandType {