V4: Remove more jumps.

Do not generate jump instructions when the target immediately follows
the current basic block, even if there are intermediate jumps in between
as long as they jump to the same basic block. In the IR snippet below,
no jumps will be generated at all.

…
L8:  goto L6;
L12: goto L6;
L6:  goto L4;
L11: goto L4;
L4:  goto L2;
L10: goto L2;
L2:  ….

Before this change, the gotos in L8, L6, and L2 were still generated.

Change-Id: I718ed0d41c603a6905f2279b782cd9e9cafb7d55
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

6 files changed, 55 insertions, 1 deletions

diff --git a/src/qml/compiler/qv4isel_masm.cpp b/src/qml/compiler/qv4isel_masm.cpp
index 1146c08d6c..98558bf9bc 100644
--- a/src/qml/compiler/qv4isel_masm.cpp
+++ b/src/qml/compiler/qv4isel_masm.cpp
@@ -667,6 +667,8 @@ void InstructionSelection::run(int functionIndex)
         ConvertTemps().toStackSlots(_function);
     }
     V4IR::Optimizer::showMeTheCode(_function);
+    QSet<V4IR::Jump *> removableJumps = opt.calculateOptionalJumps();
+    qSwap(_removableJumps, removableJumps);
 
     Assembler* oldAssembler = _as;
     _as = new Assembler(this, _function, executableAllocator, 6); // 6 == max argc for calls to built-ins with an argument array
@@ -715,6 +717,7 @@ void InstructionSelection::run(int functionIndex)
     qSwap(_reentryBlocks, reentryBlocks);
     delete _as;
     _as = oldAssembler;
+    qSwap(_removableJumps, removableJumps);
 }
 
 void *InstructionSelection::addConstantTable(QVector<Primitive> *values)
@@ -1675,7 +1678,8 @@ void InstructionSelection::constructValue(V4IR::Temp *value, V4IR::ExprList *arg
 
 void InstructionSelection::visitJump(V4IR::Jump *s)
 {
-    _as->jumpToBlock(_block, s->target);
+    if (!_removableJumps.contains(s))
+        _as->jumpToBlock(_block, s->target);
 }
 
 void InstructionSelection::visitCJump(V4IR::CJump *s)
diff --git a/src/qml/compiler/qv4isel_masm_p.h b/src/qml/compiler/qv4isel_masm_p.h
index 013c2ef8ed..1a8df9a833 100644
--- a/src/qml/compiler/qv4isel_masm_p.h
+++ b/src/qml/compiler/qv4isel_masm_p.h
@@ -1550,6 +1550,7 @@ private:
 
     V4IR::BasicBlock *_block;
     V4IR::Function* _function;
+    QSet<V4IR::Jump *> _removableJumps;
     Assembler* _as;
     QSet<V4IR::BasicBlock*> _reentryBlocks;
 
diff --git a/src/qml/compiler/qv4isel_moth.cpp b/src/qml/compiler/qv4isel_moth.cpp
index 7c999edb59..0b9473b1d3 100644
--- a/src/qml/compiler/qv4isel_moth.cpp
+++ b/src/qml/compiler/qv4isel_moth.cpp
@@ -252,7 +252,11 @@ void InstructionSelection::run(int functionIndex)
         stackSlotAllocator = new StackSlotAllocator(opt.lifeRanges(), _function->tempCount);
         opt.convertOutOfSSA();
     }
+
     qSwap(_stackSlotAllocator, stackSlotAllocator);
+    QSet<V4IR::Jump *> removableJumps = opt.calculateOptionalJumps();
+    qSwap(_removableJumps, removableJumps);
+
     V4IR::Stmt *cs = 0;
     qSwap(_currentStatement, cs);
 
@@ -289,6 +293,7 @@ void InstructionSelection::run(int functionIndex)
     codeRefs.insert(_function, squeezeCode());
 
     qSwap(_currentStatement, cs);
+    qSwap(_removableJumps, removableJumps);
     qSwap(_stackSlotAllocator, stackSlotAllocator);
     delete stackSlotAllocator;
     qSwap(_function, function);
@@ -629,6 +634,8 @@ void InstructionSelection::visitJump(V4IR::Jump *s)
 {
     if (s->target == _nextBlock)
         return;
+    if (_removableJumps.contains(s))
+        return;
 
     Instruction::Jump jump;
     jump.offset = 0;
diff --git a/src/qml/compiler/qv4isel_moth_p.h b/src/qml/compiler/qv4isel_moth_p.h
index ca03c5fa30..725dd264aa 100644
--- a/src/qml/compiler/qv4isel_moth_p.h
+++ b/src/qml/compiler/qv4isel_moth_p.h
@@ -175,6 +175,7 @@ private:
     uchar *_codeEnd;
 
     StackSlotAllocator *_stackSlotAllocator;
+    QSet<V4IR::Jump *> _removableJumps;
     V4IR::Stmt *_currentStatement;
 
     CompilationUnit *compilationUnit;
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 6ad9a5731f..c41c9cfe80 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -2976,6 +2976,45 @@ QVector<LifeTimeInterval> Optimizer::lifeRanges() const
     return lifeRanges.ranges();
 }
 
+QSet<Jump *> Optimizer::calculateOptionalJumps()
+{
+    QSet<Jump *> optional;
+    QSet<BasicBlock *> reachableWithoutJump;
+
+    const int maxSize = function->basicBlocks.size();
+    optional.reserve(maxSize);
+    reachableWithoutJump.reserve(maxSize);
+
+    for (int i = function->basicBlocks.size() - 1; i >= 0; --i) {
+        BasicBlock *bb = function->basicBlocks[i];
+
+        if (Jump *jump = bb->statements.last()->asJump()) {
+            if (reachableWithoutJump.contains(jump->target)) {
+                if (bb->statements.size() > 1)
+                    reachableWithoutJump.clear();
+                optional.insert(jump);
+                reachableWithoutJump.insert(bb);
+                continue;
+            }
+        }
+
+        reachableWithoutJump.clear();
+        reachableWithoutJump.insert(bb);
+    }
+
+#if 0
+    QTextStream out(stdout, QIODevice::WriteOnly);
+    out << "Jumps to ignore:" << endl;
+    foreach (Jump *j, removed) {
+        out << "\t" << j->id << ": ";
+        j->dump(out, Stmt::MIR);
+        out << endl;
+    }
+#endif
+
+    return optional;
+}
+
 void Optimizer::showMeTheCode(Function *function)
 {
     ::showMeTheCode(function);
diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h
index ceaef9f938..fc84ffd551 100644
--- a/src/qml/compiler/qv4ssa_p.h
+++ b/src/qml/compiler/qv4ssa_p.h
@@ -141,6 +141,8 @@ public:
 
     QVector<LifeTimeInterval> lifeRanges() const;
 
+    QSet<V4IR::Jump *> calculateOptionalJumps();
+
     static void showMeTheCode(Function *function);
 
 private: