Merge pull request #3682 from mikedn/emplace

Avoid Interval and RefPosition unnecessary initialization and copying

6 files changed, 170 insertions, 73 deletions

diff --git a/src/jit/jitstd.h b/src/jit/jitstd.h
index 6bb1ddad99..59995fd89f 100644
--- a/src/jit/jitstd.h
+++ b/src/jit/jitstd.h
@@ -5,6 +5,8 @@
 
 
 #include "allocator.h"
+#include "type_traits.h"
+#include "pair.h"
+#include "utility.h"
 #include "unordered_map.h"
 #include "unordered_set.h"
-#include "utility.h"
diff --git a/src/jit/jitstd/list.h b/src/jit/jitstd/list.h
index d5d8361ebe..01043e09b5 100644
--- a/src/jit/jitstd/list.h
+++ b/src/jit/jitstd/list.h
@@ -196,6 +196,8 @@ public:
     allocator_type get_allocator() const;
 
     iterator insert(iterator position, const T& x);
+    template <class... Args>
+    iterator emplace(iterator position, Args&&... args);
     void insert(iterator position, size_type n, const T& x);
     template <class InputIterator>
     void insert(iterator position, InputIterator first, InputIterator last);
@@ -212,7 +214,11 @@ public:
     void pop_front();
 
     void push_back(const T& val);
+    template <class... Args>
+    void emplace_back(Args&&... args);
     void push_front (const T& val);
+    template <class... Args>
+    void emplace_front(Args&&... args);
 
     reverse_iterator rbegin();
     const_reverse_iterator rbegin() const;
@@ -250,10 +256,10 @@ private:
         T m_value;
         Node* m_pNext;
         Node* m_pPrev;
-        Node(Node* pPrev, Node* pNext, const T& value)
-            : m_value(value)
-            , m_pNext(pNext)
-            , m_pPrev(pPrev)
+
+        template <class... Args>
+        Node(Args&&... args)
+            : m_value(jitstd::forward<Args>(args)...)
         {
         }
     };
@@ -271,6 +277,8 @@ private:
     void insert_helper(iterator position, size_type n, const T& value, int_not_an_iterator_tag);
     template <typename InputIterator>
     void insert_helper(iterator position, InputIterator first, InputIterator last, forward_iterator_tag);
+    
+    void insert_new_node_helper(Node* pInsert, Node* pNewNode);
 
     Node* m_pHead;
     Node* m_pTail;
@@ -459,38 +467,19 @@ template <typename T, typename Allocator>
 typename list<T, Allocator>::iterator
     list<T, Allocator>::insert(iterator position, const T& val)
 {
-    ++m_nSize;
+    Node* pNewNode = new (m_nodeAllocator.allocate(1), placement_t()) Node(val);
+    insert_new_node_helper(position.m_pNode, pNewNode);
+    return iterator(pNewNode);
+}
 
-    Node* pInsert = position.m_pNode;
-    if (pInsert == NULL)
-    {
-        Node* pNewTail = new (m_nodeAllocator.allocate(1), placement_t()) Node(m_pTail, NULL, val);
-        if (m_pHead == NULL)
-        {
-            m_pTail = pNewTail;
-            m_pHead = m_pTail;
-        }
-        else
-        {
-            m_pTail->m_pNext = pNewTail;
-            m_pTail = pNewTail;
-        }
-        return iterator(m_pTail);
-    }
-    else
-    {
-        Node* pNode = new (m_nodeAllocator.allocate(1), placement_t()) Node(pInsert->m_pPrev, pInsert, val);
-        if (pInsert->m_pPrev)
-        {
-            pInsert->m_pPrev->m_pNext = pNode;
-        }
-        else
-        {
-            m_pHead = pNode;
-        }
-        pInsert->m_pPrev = pNode;
-        return iterator(pNode);
-    }
+template <typename T, typename Allocator>
+template <typename... Args>
+typename list<T, Allocator>::iterator 
+    list<T, Allocator>::emplace(iterator position, Args&&... args)
+{
+    Node* pNewNode = new (m_nodeAllocator.allocate(1), placement_t()) Node(jitstd::forward<Args>(args)...);
+    insert_new_node_helper(position.m_pNode, pNewNode);
+    return iterator(pNewNode);
 }
 
 template <typename T, typename Allocator>
@@ -614,12 +603,26 @@ void list<T, Allocator>::push_back(const T& val)
 }
 
 template <typename T, typename Allocator>
+template <typename... Args>
+void list<T, Allocator>::emplace_back(Args&&... args)
+{
+    emplace(end(), jitstd::forward<Args>(args)...);
+}
+
+template <typename T, typename Allocator>
 void list<T, Allocator>::push_front(const T& val)
 {
     insert(begin(), val);
 }
 
 template <typename T, typename Allocator>
+template <typename... Args>
+void list<T, Allocator>::emplace_front(Args&&... args)
+{
+    emplace(begin(), jitstd::forward<Args>(args)...);
+}
+
+template <typename T, typename Allocator>
 typename list<T, Allocator>::reverse_iterator
     list<T, Allocator>::rbegin()
 {
@@ -840,6 +843,40 @@ void list<T, Allocator>::insert_helper(iterator position, InputIterator first, I
     }
 }
 
+template <typename T, typename Allocator>
+void list<T, Allocator>::insert_new_node_helper(Node* pInsert, Node* pNewNode)
+{
+    ++m_nSize;
+
+    if (pInsert == nullptr)
+    {
+        pNewNode->m_pPrev = m_pTail;
+        pNewNode->m_pNext = nullptr;
+        if (m_pHead == nullptr)
+        {
+            m_pHead = pNewNode;
+        }
+        else
+        {
+            m_pTail->m_pNext = pNewNode;
+        }
+        m_pTail = pNewNode;
+    }
+    else
+    {
+        pNewNode->m_pPrev = pInsert->m_pPrev;
+        pNewNode->m_pNext = pInsert;
+        if (pInsert->m_pPrev == nullptr)
+        {
+            m_pHead = pNewNode;
+        }
+        else
+        {
+            pInsert->m_pPrev->m_pNext = pNewNode;
+        }
+        pInsert->m_pPrev = pNewNode;
+    }
+}
 
 } // end of namespace jitstd.
 
diff --git a/src/jit/jitstd/type_traits.h b/src/jit/jitstd/type_traits.h
index 21503fbadb..1e853e8cca 100644
--- a/src/jit/jitstd/type_traits.h
+++ b/src/jit/jitstd/type_traits.h
@@ -37,6 +37,36 @@ struct remove_cv : remove_const<typename remove_volatile<T>::type>
 };
 
 template <typename T>
+struct remove_reference
+{
+    typedef T type;
+};
+
+template <typename T>
+struct remove_reference<T&>
+{
+    typedef T type;
+};
+
+template <typename T>
+struct remove_reference<T&&>
+{
+    typedef T type;
+};
+
+template <typename T>
+struct is_lvalue_reference
+{
+    enum { value = false };
+};
+
+template <typename T>
+struct is_lvalue_reference<T&>
+{
+    enum { value = true };
+};
+
+template <typename T>
 struct is_unqualified_pointer
 {
     enum { value = false };
diff --git a/src/jit/jitstd/utility.h b/src/jit/jitstd/utility.h
index 39379cb4bc..80ce58e4d7 100644
--- a/src/jit/jitstd/utility.h
+++ b/src/jit/jitstd/utility.h
@@ -9,6 +9,21 @@
 namespace jitstd
 {
 
+template <typename T>
+inline 
+T&& forward(typename jitstd::remove_reference<T>::type& arg)
+{
+    return static_cast<T&&>(arg);
+}
+
+template <typename T>
+inline 
+T&& forward(typename jitstd::remove_reference<T>::type&& arg)
+{
+    static_assert(!jitstd::is_lvalue_reference<T>::value, "unexpected lvalue reference");
+    return static_cast<T&&>(arg);
+}
+
 namespace utility
 {
     // Template class for scoped execution of a lambda.
diff --git a/src/jit/lsra.cpp b/src/jit/lsra.cpp
index cef80184dc..a52879bbf0 100644
--- a/src/jit/lsra.cpp
+++ b/src/jit/lsra.cpp
@@ -313,12 +313,8 @@ LinearScan::stressLimitRegs(RefPosition* refPosition, regMaskTP mask)
 Interval *
 LinearScan::newInterval(RegisterType theRegisterType)
 {
-    intervals.push_back(Interval());
+    intervals.emplace_back(theRegisterType, allRegs(theRegisterType));
     Interval *newInt = &intervals.back();
-    newInt->init();
-
-    newInt->registerType = theRegisterType;
-    newInt->registerPreferences = allRegs(theRegisterType);
 
 #ifdef DEBUG
     newInt->intervalIndex = intervalCount;
@@ -330,15 +326,13 @@ LinearScan::newInterval(RegisterType theRegisterType)
 }
 
 RefPosition *
-LinearScan::newRefPositionRaw()
+LinearScan::newRefPositionRaw(LsraLocation nodeLocation, GenTree* treeNode, RefType refType)
 {
-    refPositions.push_back(RefPosition());
+    refPositions.emplace_back(curBBNum, nodeLocation, treeNode, refType);
     RefPosition *newRP = &refPositions.back();
-    memset(newRP, 0, sizeof(RefPosition)); // TODO-Cleanup: call a RefPosition constructor instead?
 #ifdef DEBUG
     newRP->rpNum = refPositionCount;
 #endif // DEBUG
-    newRP->bbNum = curBBNum;
     refPositionCount++;
     return newRP;
 }
@@ -647,21 +641,9 @@ LinearScan::newRefPosition(
     RefType theRefType, GenTree * theTreeNode,
     regMaskTP mask)
 {
-    RefPosition *newRP = newRefPositionRaw();
+    RefPosition *newRP = newRefPositionRaw(theLocation, theTreeNode, theRefType);
 
     newRP->setReg(getRegisterRecord(reg));
-    newRP->nextRefPosition = nullptr;
-    newRP->nodeLocation = theLocation;
-    newRP->treeNode = theTreeNode;
-    newRP->refType = theRefType;
-
-    // Last Use - this may be true for multiple RefPositions in the same Interval
-    newRP->lastUse = false;
-
-    // Spill info
-    newRP->reload = false;
-    newRP->spillAfter = false;
-    newRP->isPhysRegRef = true;
 
     newRP->registerAssignment = mask;
     associateRefPosWithInterval(newRP);
@@ -709,19 +691,11 @@ LinearScan::newRefPosition(
         assert((allRegs(theInterval->registerType) & mask) != 0);
     }
 
-    RefPosition *newRP = newRefPositionRaw();
+    RefPosition *newRP = newRefPositionRaw(theLocation, theTreeNode, theRefType);
 
     newRP->setInterval(theInterval);
-    newRP->nextRefPosition = nullptr;
-    newRP->nodeLocation = theLocation;
-    newRP->treeNode = theTreeNode;
-    newRP->refType = theRefType;
-    // Last Use - this may be true for multiple RefPositions in the same Interval
-    newRP->lastUse = false;
 
     // Spill info
-    newRP->reload = false;
-    newRP->spillAfter = false;
     newRP->isFixedRegRef = isFixedRegister;
 
     // We don't need this for AMD because the PInvoke method epilog code is explicit
diff --git a/src/jit/lsra.h b/src/jit/lsra.h
index 27939d7422..9f3f2b3697 100644
--- a/src/jit/lsra.h
+++ b/src/jit/lsra.h
@@ -720,7 +720,7 @@ private:
     }
     RegRecord *     getRegisterRecord(regNumber regNum);
 
-    RefPosition *   newRefPositionRaw();
+    RefPosition *   newRefPositionRaw(LsraLocation nodeLocation, GenTree* treeNode, RefType refType);
 
     RefPosition *   newRefPosition(Interval * theInterval, LsraLocation theLocation,
                                    RefType theRefType, GenTree * theTreeNode,
@@ -1050,11 +1050,28 @@ XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
 class Interval : public Referenceable
 {
 public:
-    // Initialize the interval
-    void init()
+    Interval(RegisterType registerType, regMaskTP registerPreferences)
+        : registerPreferences(registerPreferences)
+        , relatedInterval(nullptr)
+        , assignedReg(nullptr)
+        , registerType(registerType)
+        , isLocalVar(false)
+        , isSplit(false)
+        , isSpilled(false)
+        , isInternal(false)
+        , isStructField(false)
+        , isPromotedStruct(false)
+        , hasConflictingDefUse(false)
+        , hasNonCommutativeRMWDef(false)
+        , isSpecialPutArg(false)
+        , preferCalleeSave(false)
+        , isConstant(false)
+        , physReg(REG_COUNT)
+#ifdef DEBUG
+        , intervalIndex(0)
+#endif
+        , varNum(0)
     {
-        memset(this, 0, sizeof(Interval));
-        physReg = REG_COUNT;
     }
 
 #ifdef DEBUG
@@ -1248,8 +1265,30 @@ public:
 
 class RefPosition
 {
-
 public:
+    RefPosition(unsigned int bbNum, LsraLocation nodeLocation, GenTree* treeNode, RefType refType)
+        : referent(nullptr)
+        , nextRefPosition(nullptr)
+        , treeNode(treeNode)
+        , bbNum(bbNum)
+        , nodeLocation(nodeLocation)
+        , registerAssignment(RBM_NONE)
+        , refType(refType)
+        , lastUse(false)
+        , reload(false)
+        , spillAfter(false)
+        , copyReg(false)
+        , moveReg(false)
+        , isPhysRegRef(false)
+        , isFixedRegRef(false)
+        , isLocalDefUse(false)
+        , delayRegFree(false)
+        , outOfOrder(false)
+#ifdef DEBUG
+        , rpNum(0)
+#endif
+    {
+    }
 
     // A RefPosition refers to either an Interval or a RegRecord. 'referent' points to one
     // of these types. If it refers to a RegRecord, then 'isPhysRegRef' is true. If it