V4: Replace a QSet with a QVector in calculateOptionalJumps

Instead of storing a bunch of statement IDs in a QSet, the parent basic
block of the terminator statement (specifically: the jump) is used as
an index into a bit vector. If the bit is set, this indicates that the
jump can be omitted.

This reduces the number of allocations from 1 hash node per optional
jump, to 1 per function. The allocation will also be smaller then a
hash node.

Change-Id: Ia34468534b96dd9cefa837523bf89ad233de92e8
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

1 files changed, 26 insertions, 10 deletions

diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 283fb24897..6d55b43354 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -5463,14 +5463,30 @@ LifeTimeIntervals::Ptr Optimizer::lifeTimeIntervals() const
     return lifeRanges.intervals();
 }
 
-QSet<Jump *> Optimizer::calculateOptionalJumps()
+static int countPhis(BasicBlock *bb)
 {
-    QSet<Jump *> optional;
-    QSet<BasicBlock *> reachableWithoutJump;
+    int count = 0;
+    for (Stmt *s : bb->statements()) {
+        if (s->isa<Phi>())
+            ++count;
+        else
+            break;
+    }
 
+    return count;
+}
+
+// Basic blocks can have only 1 terminator. This function returns a bit vector, where a 1 on a
+// certain index indicates that the terminator (jump) at the end of the basic block with that index
+// can be omitted.
+BitVector Optimizer::calculateOptionalJumps()
+{
     const int maxSize = function->basicBlockCount();
-    optional.reserve(maxSize);
-    reachableWithoutJump.reserve(maxSize);
+    BitVector optional(maxSize, false);
+    if (maxSize < 2)
+        return optional;
+
+    BitVector reachableWithoutJump(maxSize, false);
 
     for (int i = maxSize - 1; i >= 0; --i) {
         BasicBlock *bb = function->basicBlock(i);
@@ -5478,17 +5494,17 @@ QSet<Jump *> Optimizer::calculateOptionalJumps()
             continue;
 
         if (Jump *jump = bb->statements().last()->asJump()) {
-            if (reachableWithoutJump.contains(jump->target)) {
-                if (bb->statements().size() > 1)
+            if (reachableWithoutJump.at(jump->target->index())) {
+                if (bb->statements().size() - countPhis(bb)> 1)
                     reachableWithoutJump.clear();
-                optional.insert(jump);
-                reachableWithoutJump.insert(bb);
+                optional.setBit(bb->index());
+                reachableWithoutJump.setBit(bb->index());
                 continue;
             }
         }
 
         reachableWithoutJump.clear();
-        reachableWithoutJump.insert(bb);
+        reachableWithoutJump.setBit(bb->index());
     }
 
     return optional;