Improve SSA dominator computation memory usage (#14965)

* Improve SSA DF computation memory usage

DF(b) can be stored in a vector instead of a hashtable (set). Nothing needs a O(1) membership test, the duplicates that may be generated during DF construction can be easily avoided by observing that:
* each block in the graph is processed exactly once
* during processing the block is added to the relevant DF vectors, at the end of each vector. If the same DF vector is encountered multiple times then checking if the block is already a member is trivial.

* Use the same block BitVec for topo sort and IDom

* Add BitVecOps::TryAddElemD

Makes the code more readable and avoids the duplicated IsShort test that a separate IsMember/AddElemD may generate.

* Improve SSA IDF computation memory usage

Like DF(b), IDF(b) can be stored in a vector if duplicates are avoided. This can be done by using a BitVector like TopologicalSort and ComputeImmediateDom already do. It's cheaper than using a hashtable (even though it requires a "clear" for every block that has a frontier).

Also, storing IDF(b) into a vector makes it easier to track newly added blocks - they're at the end of the vector. Using a separate "delta" set is no longer needed.

1 files changed, 33 insertions, 0 deletions

diff --git a/src/jit/bitsetasshortlong.h b/src/jit/bitsetasshortlong.h
index f11aa8e1c2..e5d2bd76c6 100644
--- a/src/jit/bitsetasshortlong.h
+++ b/src/jit/bitsetasshortlong.h
@@ -42,6 +42,7 @@ private:
     static void UnionDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
     static void DiffDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
     static void AddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
+    static bool TryAddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
     static void RemoveElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
     static void ClearDLong(Env env, BitSetShortLongRep& bs);
     static BitSetShortLongRep MakeUninitArrayBits(Env env);
@@ -276,6 +277,23 @@ public:
         return res;
     }
 
+    static bool TryAddElemD(Env env, BitSetShortLongRep& bs, unsigned i)
+    {
+        assert(i < BitSetTraits::GetSize(env));
+        if (IsShort(env))
+        {
+            size_t mask  = ((size_t)1) << i;
+            size_t bits  = (size_t)bs;
+            bool   added = (bits & mask) == 0;
+            bs           = (BitSetShortLongRep)(bits | mask);
+            return added;
+        }
+        else
+        {
+            return TryAddElemDLong(env, bs, i);
+        }
+    }
+
     static bool IsMember(Env env, const BitSetShortLongRep bs, unsigned i)
     {
         assert(i < BitSetTraits::GetSize(env));
@@ -645,6 +663,21 @@ void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 }
 
 template <typename Env, typename BitSetTraits>
+bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
+               /*Brand*/ BSShortLong,
+               /*Env*/ Env,
+               /*BitSetTraits*/ BitSetTraits>::TryAddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i)
+{
+    assert(!IsShort(env));
+    unsigned index = i / BitsInSizeT;
+    size_t   mask  = ((size_t)1) << (i % BitsInSizeT);
+    size_t   bits  = bs[index];
+    bool     added = (bits & mask) == 0;
+    bs[index]      = bits | mask;
+    return added;
+}
+
+template <typename Env, typename BitSetTraits>
 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
                /*Brand*/ BSShortLong,
                /*Env*/ Env,