Replace the LSRA stack with a hash table.

LSRA currently uses a stack to find the `LocationInfo` for each register consumed
by a node. The changes in this stack's contents given a particular node are
governed by three factors:
- The number of registers the node consumes (`gtLsraInfo.srcCount`)
- The number of registers the node produces (`gtLstaInfo.dstCount`)
- Whether or not the node produces an unused value (`gtLsraInfo.isLocalDefUse`)

In all cases, `gtLsraInfo.srcCount` values are popped off of the stack in the
order in which they were pushed (i.e. in FIFO rather than LIFO order). If the
node produces a value that will be used, `gtLsraInfo.dstCount` values are
then pushed onto the stack. If the node produces an unused value, nothing is
pushed onto the stack.

Naively, it would appear that the number of registers a node consumes would be
at least the count of the node's non-leaf operands (to put it differently, one
might assume that any non-leaf operator that produces a value would define at
least one register). However, contained nodes complicate the situation: because
a contained node's execution is subsumed by its user, the contained node's
sources become sources for its user and the contained node does not define any
registers. As a result, both the number of registers consumed and the number of
registers produced by a contained node are 0. Thus, contained nodes do not
update the stack, and the node's parent (if it is not also contained) will
pop the values produced by the contained node's operands. Logically speaking,
it is as if a contained node defines the transitive closure of the registers
defined by its own non-contained operands.

The use of the stack relies on the property that even in linear order the
JIT's IR is still tree ordered. That is to say, given an operator and its
operands, any nodes that execute between any two operands do not produce
SDSU temps that are consumed after the second operand. IR with such a
shape would unbalance the stack.

The planned move to the LIR design given in #6366 removes the tree order
constraint in order to simplify understanding and manipulating the IR in the
backend. Because LIR may not be tree ordered, LSRA may no longer use a stack
to find the `LocationInfo` for a node's operands. This change replaces the
stack with a map from nodes to lists of `LocationInfo` values, each of
which describes a register that is logically defined (if not physically
defined) by that node. Only contained nodes logically define registers that
they do not physically define: contained nodes map to the list of
`LocationInfo` values logically defined by their operands. All non-contained
nodes map to the list of `LocationInfo` values that they physically define.
Non-contained nodes that do not define any registers are not inserted into
the map.

1 files changed, 42 insertions, 0 deletions

diff --git a/src/jit/utils.h b/src/jit/utils.h
index 7d77e76840..f9fb39131e 100644
--- a/src/jit/utils.h
+++ b/src/jit/utils.h
@@ -39,6 +39,48 @@ inline bool isPow2(T i)
     return (i > 0 && ((i-1)&i) == 0);
 }
 
+// Adapter for iterators to a type that is compatible with C++11
+// range-based for loops.
+template<typename TIterator>
+class IteratorPair
+{
+    TIterator m_begin;
+    TIterator m_end;
+
+public:
+    IteratorPair(TIterator begin, TIterator end)
+        : m_begin(begin)
+        , m_end(end)
+    {
+    }
+
+    inline TIterator begin()
+    {
+        return m_begin;
+    }
+
+    inline TIterator end()
+    {
+        return m_end;
+    }
+};
+
+template<typename TIterator>
+inline IteratorPair<TIterator> MakeIteratorPair(TIterator begin, TIterator end)
+{
+    return IteratorPair<TIterator>(begin, end);
+}
+
+// Recursive template definition to calculate the base-2 logarithm
+// of a constant value.
+template <unsigned val, unsigned acc = 0>
+struct ConstLog2 { enum { value = ConstLog2<val / 2, acc + 1>::value }; };
+
+template <unsigned acc>
+struct ConstLog2<0, acc> { enum { value = acc }; };
+
+template <unsigned acc>
+struct ConstLog2<1, acc> { enum { value = acc }; };
 
 inline const char* dspBool(bool b)
 {