Speed up regular expression matching

Use the Yarr JIT back-end if possible. Speeds up the RegExp v8 benchmark by a
factor of 3.

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

7 files changed, 114 insertions, 16 deletions

diff --git a/src/3rdparty/masm/masm-defs.pri b/src/3rdparty/masm/masm-defs.pri
index f8055d0ff4..a75de9fd9f 100644
--- a/src/3rdparty/masm/masm-defs.pri
+++ b/src/3rdparty/masm/masm-defs.pri
@@ -8,7 +8,7 @@ DEFINES += ENABLE_DFG_JIT=0
 DEFINES += ENABLE_JIT=1
 DEFINES += ENABLE_JIT_CONSTANT_BLINDING=0
 DEFINES += ENABLE_ASSEMBLER=1
-DEFINES += ENABLE_YARR_JIT=0
+DEFINES += ENABLE_YARR_JIT=1
 DEFINES += BUILDING_QT__
 
 INCLUDEPATH += $$PWD/jit
diff --git a/src/3rdparty/masm/masm.pri b/src/3rdparty/masm/masm.pri
index 683a5b19d3..53a950a6d6 100644
--- a/src/3rdparty/masm/masm.pri
+++ b/src/3rdparty/masm/masm.pri
@@ -30,6 +30,8 @@ HEADERS += $$PWD/wtf/PageReservation.h
 SOURCES += $$PWD/stubs/WTFStubs.cpp
 HEADERS += $$PWD/stubs/WTFStubs.h
 
+SOURCES += $$PWD/stubs/Options.cpp
+
 SOURCES += $$PWD/disassembler/Disassembler.cpp
 SOURCES += $$PWD/disassembler/UDis86Disassembler.cpp
 contains(DEFINES, WTF_USE_UDIS86=1) {
@@ -53,12 +55,7 @@ contains(DEFINES, WTF_USE_UDIS86=1) {
     QMAKE_EXTRA_TARGETS += udis86_tab_cfile
 }
 
-SOURCES += \
-    $$PWD/yarr/YarrCanonicalizeUCS2.cpp \
-    $$PWD/yarr/YarrInterpreter.cpp \
-    $$PWD/yarr/YarrPattern.cpp \
-    $$PWD/yarr/YarrSyntaxChecker.cpp
-
+SOURCES += $$PWD/yarr/*.cpp
 HEADERS += $$PWD/yarr/*.h
 
 retgen.output = RegExpJitTables.h
diff --git a/src/3rdparty/masm/stubs/Options.cpp b/src/3rdparty/masm/stubs/Options.cpp
new file mode 100644
index 0000000000..fa718bd0ad
--- /dev/null
+++ b/src/3rdparty/masm/stubs/Options.cpp
@@ -0,0 +1,55 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the V4VM module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "config.h"
+#include "Options.h"
+
+#include <QByteArray>
+
+namespace JSC {
+
+bool Options::showDisassembly()
+{
+    static bool showCode = !qgetenv("SHOW_CODE").isNull();
+    return showCode;
+}
+
+}
diff --git a/src/3rdparty/masm/stubs/Options.h b/src/3rdparty/masm/stubs/Options.h
index b95e4354e2..522cd7407e 100644
--- a/src/3rdparty/masm/stubs/Options.h
+++ b/src/3rdparty/masm/stubs/Options.h
@@ -44,7 +44,7 @@
 namespace JSC {
 
 struct Options {
-    static bool showDisassembly() { return true; }
+    static bool showDisassembly();
     static bool showDFGDisassembly() { return true; }
 };
 
diff --git a/src/3rdparty/masm/stubs/wtf/Vector.h b/src/3rdparty/masm/stubs/wtf/Vector.h
index 39742d8ab0..836d91c00c 100644
--- a/src/3rdparty/masm/stubs/wtf/Vector.h
+++ b/src/3rdparty/masm/stubs/wtf/Vector.h
@@ -55,15 +55,34 @@ namespace WTF {
 template <typename T, int capacity = 1, int overflowMode = UnsafeVectorOverflow>
 class Vector : public std::vector<T> {
 public:
+    typedef T* iterator;
+    typedef const T* const_iterator;
+
     Vector() {}
     Vector(int initialSize) : std::vector<T>(initialSize) {}
 
     inline void append(const T& value)
     { this->push_back(value); }
 
+    template <typename OtherType>
+    inline void append(const OtherType& other)
+    { this->push_back(T(other)); }
+
     inline void append(const Vector<T>& vector)
     {
-        this->insert(this->end(), vector.begin(), vector.end());
+        this->insert(this->std::vector<T>::end(), vector.std::vector<T>::begin(), vector.std::vector<T>::end());
+    }
+
+    inline void append(const T* ptr, size_t count)
+    {
+        for (size_t i = 0; i < count; ++i)
+            this->push_back(T(ptr[i]));
+    }
+
+    inline void append(typename std::vector<T>::const_iterator it, size_t count)
+    {
+        for (size_t i = 0; i < count; ++i, ++it)
+            this->push_back(*it);
     }
 
     using std::vector<T>::insert;
@@ -71,23 +90,33 @@ public:
     inline void reserveInitialCapacity(size_t size) { this->reserve(size); }
 
     inline void insert(size_t position, T value)
-    { this->insert(this->begin() + position, value); }
+    { this->insert(this->std::vector<T>::begin() + position, value); }
 
     inline void grow(size_t size)
     { this->resize(size); }
 
     inline void shrink(size_t size)
-    { this->erase(this->begin() + size, this->end()); }
+    { this->erase(this->std::vector<T>::begin() + size, this->std::vector<T>::end()); }
 
     inline void shrinkToFit()
     { this->shrink_to_fit(); }
 
     inline void remove(size_t position)
-    { this->erase(this->begin() + position); }
+    { this->erase(this->std::vector<T>::begin() + position); }
 
     inline bool isEmpty() const { return this->empty(); }
 
-    inline T &last() { return *(this->begin() + this->size() - 1); }
+    inline T &last() { return *(this->std::vector<T>::begin() + this->size() - 1); }
+
+    inline iterator begin()
+    { return &(*this->std::vector<T>::begin()); }
+    inline const_iterator begin() const
+    { return &(*this->std::vector<T>::begin()); }
+    inline iterator end()
+    { return &(*this->std::vector<T>::end()); }
+    inline const_iterator end() const
+    { return &(*this->std::vector<T>::end()); }
+
 };
 
 template <typename T, int capacity>
diff --git a/src/qml/qml/v4vm/qv4regexp.cpp b/src/qml/qml/v4vm/qv4regexp.cpp
index 7ee1d6bb95..0ca3ae95c2 100644
--- a/src/qml/qml/v4vm/qv4regexp.cpp
+++ b/src/qml/qml/v4vm/qv4regexp.cpp
@@ -56,12 +56,19 @@ RegExpCache::~RegExpCache()
 
 DEFINE_MANAGED_VTABLE(RegExp);
 
-uint RegExp::match(const QString &string, int start, uint *matchOffsets) const
+uint RegExp::match(const QString &string, int start, uint *matchOffsets)
 {
     if (!isValid())
         return JSC::Yarr::offsetNoMatch;
 
-    return JSC::Yarr::interpret(m_byteCode.get(), WTF::String(string).characters16(), string.length(), start, matchOffsets);
+    WTF::String s(string);
+
+#if ENABLE(YARR_JIT)
+    if (!m_jitCode.isFallBack() && m_jitCode.has16BitCode())
+        return m_jitCode.execute(s.characters16(), start, s.length(), (int*)matchOffsets).start;
+#endif
+
+    return JSC::Yarr::interpret(m_byteCode.get(), s.characters16(), string.length(), start, matchOffsets);
 }
 
 RegExp* RegExp::create(ExecutionEngine* engine, const QString& pattern, bool ignoreCase, bool multiline)
@@ -103,6 +110,12 @@ RegExp::RegExp(ExecutionEngine* engine, const QString &pattern, bool ignoreCase,
         return;
     m_subPatternCount = yarrPattern.m_numSubpatterns;
     m_byteCode = JSC::Yarr::byteCompile(yarrPattern, &engine->bumperPointerAllocator);
+#if ENABLE(YARR_JIT)
+    if (!yarrPattern.m_containsBackreferences) {
+        JSC::JSGlobalData dummy(engine->executableAllocator);
+        JSC::Yarr::jitCompile(yarrPattern, JSC::Yarr::Char16, &dummy, m_jitCode);
+    }
+#endif
 }
 
 RegExp::~RegExp()
diff --git a/src/qml/qml/v4vm/qv4regexp_p.h b/src/qml/qml/v4vm/qv4regexp_p.h
index e8b01953bc..30b707ef4e 100644
--- a/src/qml/qml/v4vm/qv4regexp_p.h
+++ b/src/qml/qml/v4vm/qv4regexp_p.h
@@ -52,6 +52,7 @@
 
 #include <yarr/Yarr.h>
 #include <yarr/YarrInterpreter.h>
+#include <yarr/YarrJIT.h>
 
 #include "qv4managed_p.h"
 #include "qv4engine_p.h"
@@ -101,7 +102,7 @@ public:
 
     bool isValid() const { return m_byteCode.get(); }
 
-    uint match(const QString& string, int start, uint *matchOffsets) const;
+    uint match(const QString& string, int start, uint *matchOffsets);
 
     bool ignoreCase() const { return m_ignoreCase; }
     bool multiLine() const { return m_multiLine; }
@@ -128,6 +129,9 @@ private:
 
     const QString m_pattern;
     OwnPtr<JSC::Yarr::BytecodePattern> m_byteCode;
+#if ENABLE(YARR_JIT)
+    JSC::Yarr::YarrCodeBlock m_jitCode;
+#endif
     RegExpCache *m_cache;
     int m_subPatternCount;
     const bool m_ignoreCase;