16 files changed, 749 insertions, 29 deletions

diff --git a/Userland/Libraries/LibJS/Bytecode/BasicBlock.cpp b/Userland/Libraries/LibJS/Bytecode/BasicBlock.cpp
index 0182d4412f..8bac7aa06a 100644
--- a/Userland/Libraries/LibJS/Bytecode/BasicBlock.cpp
+++ b/Userland/Libraries/LibJS/Bytecode/BasicBlock.cpp
@@ -66,6 +66,7 @@ void BasicBlock::grow(size_t additional_size)
 
 void InstructionStreamIterator::operator++()
 {
+    VERIFY(!at_end());
     m_offset += dereference().length();
 }
 
diff --git a/Userland/Libraries/LibJS/Bytecode/Instruction.h b/Userland/Libraries/LibJS/Bytecode/Instruction.h
index 11c9b6b745..ac0e8de028 100644
--- a/Userland/Libraries/LibJS/Bytecode/Instruction.h
+++ b/Userland/Libraries/LibJS/Bytecode/Instruction.h
@@ -80,10 +80,12 @@ public:
 #undef __BYTECODE_OP
     };
 
+    bool is_terminator() const;
     Type type() const { return m_type; }
     size_t length() const;
     String to_string(Bytecode::Executable const&) const;
     void execute(Bytecode::Interpreter&) const;
+    void replace_references(BasicBlock const&, BasicBlock const&);
     static void destroy(Instruction&);
 
 protected:
diff --git a/Userland/Libraries/LibJS/Bytecode/Interpreter.cpp b/Userland/Libraries/LibJS/Bytecode/Interpreter.cpp
index eb63d3f895..4d4441cd7d 100644
--- a/Userland/Libraries/LibJS/Bytecode/Interpreter.cpp
+++ b/Userland/Libraries/LibJS/Bytecode/Interpreter.cpp
@@ -165,4 +165,38 @@ void Interpreter::continue_pending_unwind(Label const& resume_label)
         jump(resume_label);
     }
 }
+
+AK::Array<OwnPtr<PassManager>, static_cast<UnderlyingType<Interpreter::OptimizationLevel>>(Interpreter::OptimizationLevel::__Count)> Interpreter::s_optimization_pipelines {};
+
+Bytecode::PassManager& Interpreter::optimization_pipeline(Interpreter::OptimizationLevel level)
+{
+    auto underlying_level = to_underlying(level);
+    VERIFY(underlying_level <= to_underlying(Interpreter::OptimizationLevel::__Count));
+    auto& entry = s_optimization_pipelines[underlying_level];
+
+    if (entry)
+        return *entry;
+
+    auto pm = make<PassManager>();
+    if (level == OptimizationLevel::Default) {
+        pm->add<Passes::GenerateCFG>();
+        pm->add<Passes::UnifySameBlocks>();
+        pm->add<Passes::GenerateCFG>();
+        pm->add<Passes::MergeBlocks>();
+        pm->add<Passes::GenerateCFG>();
+        pm->add<Passes::UnifySameBlocks>();
+        pm->add<Passes::GenerateCFG>();
+        pm->add<Passes::MergeBlocks>();
+        pm->add<Passes::GenerateCFG>();
+        pm->add<Passes::PlaceBlocks>();
+    } else {
+        VERIFY_NOT_REACHED();
+    }
+
+    auto& passes = *pm;
+    entry = move(pm);
+
+    return passes;
+}
+
 }
diff --git a/Userland/Libraries/LibJS/Bytecode/Interpreter.h b/Userland/Libraries/LibJS/Bytecode/Interpreter.h
index 26b2dc9078..0dda59a99b 100644
--- a/Userland/Libraries/LibJS/Bytecode/Interpreter.h
+++ b/Userland/Libraries/LibJS/Bytecode/Interpreter.h
@@ -7,6 +7,7 @@
 #pragma once
 
 #include "Generator.h"
+#include "PassManager.h"
 #include <LibJS/Bytecode/Label.h>
 #include <LibJS/Bytecode/Register.h>
 #include <LibJS/Forward.h>
@@ -60,9 +61,17 @@ public:
 
     Executable const& current_executable() { return *m_current_executable; }
 
+    enum class OptimizationLevel {
+        Default,
+        __Count,
+    };
+    static Bytecode::PassManager& optimization_pipeline(OptimizationLevel = OptimizationLevel::Default);
+
 private:
     RegisterWindow& registers() { return m_register_windows.last(); }
 
+    static AK::Array<OwnPtr<PassManager>, static_cast<UnderlyingType<Interpreter::OptimizationLevel>>(Interpreter::OptimizationLevel::__Count)> s_optimization_pipelines;
+
     VM& m_vm;
     GlobalObject& m_global_object;
     NonnullOwnPtrVector<RegisterWindow> m_register_windows;
diff --git a/Userland/Libraries/LibJS/Bytecode/Label.h b/Userland/Libraries/LibJS/Bytecode/Label.h
index 8174463f6e..b1634b1d0d 100644
--- a/Userland/Libraries/LibJS/Bytecode/Label.h
+++ b/Userland/Libraries/LibJS/Bytecode/Label.h
@@ -14,14 +14,14 @@ namespace JS::Bytecode {
 class Label {
 public:
     explicit Label(BasicBlock const& block)
-        : m_block(block)
+        : m_block(&block)
     {
     }
 
-    auto& block() const { return m_block; }
+    auto& block() const { return *m_block; }
 
 private:
-    BasicBlock const& m_block;
+    BasicBlock const* m_block { nullptr };
 };
 
 }
diff --git a/Userland/Libraries/LibJS/Bytecode/Op.cpp b/Userland/Libraries/LibJS/Bytecode/Op.cpp
index 676267e4d2..69744b6c22 100644
--- a/Userland/Libraries/LibJS/Bytecode/Op.cpp
+++ b/Userland/Libraries/LibJS/Bytecode/Op.cpp
@@ -165,6 +165,14 @@ void Jump::execute_impl(Bytecode::Interpreter& interpreter) const
     interpreter.jump(*m_true_target);
 }
 
+void Jump::replace_references_impl(BasicBlock const& from, BasicBlock const& to)
+{
+    if (m_true_target.has_value() && &m_true_target->block() == &from)
+        m_true_target = Label { to };
+    if (m_false_target.has_value() && &m_false_target->block() == &from)
+        m_false_target = Label { to };
+}
+
 void JumpConditional::execute_impl(Bytecode::Interpreter& interpreter) const
 {
     VERIFY(m_true_target.has_value());
@@ -261,6 +269,16 @@ void EnterUnwindContext::execute_impl(Bytecode::Interpreter& interpreter) const
     interpreter.jump(m_entry_point);
 }
 
+void EnterUnwindContext::replace_references_impl(BasicBlock const& from, BasicBlock const& to)
+{
+    if (&m_entry_point.block() == &from)
+        m_entry_point = Label { to };
+    if (m_handler_target.has_value() && &m_handler_target->block() == &from)
+        m_handler_target = Label { to };
+    if (m_finalizer_target.has_value() && &m_finalizer_target->block() == &from)
+        m_finalizer_target = Label { to };
+}
+
 void LeaveUnwindContext::execute_impl(Bytecode::Interpreter& interpreter) const
 {
     interpreter.leave_unwind_context();
@@ -271,6 +289,12 @@ void ContinuePendingUnwind::execute_impl(Bytecode::Interpreter& interpreter) con
     interpreter.continue_pending_unwind(m_resume_target);
 }
 
+void ContinuePendingUnwind::replace_references_impl(BasicBlock const& from, BasicBlock const& to)
+{
+    if (&m_resume_target.block() == &from)
+        m_resume_target = Label { to };
+}
+
 void PushLexicalEnvironment::execute_impl(Bytecode::Interpreter& interpreter) const
 {
     HashMap<FlyString, Variable> resolved_variables;
@@ -292,6 +316,12 @@ void Yield::execute_impl(Bytecode::Interpreter& interpreter) const
     interpreter.do_return(object);
 }
 
+void Yield::replace_references_impl(BasicBlock const& from, BasicBlock const& to)
+{
+    if (m_continuation_label.has_value() && &m_continuation_label->block() == &from)
+        m_continuation_label = Label { to };
+}
+
 void GetByValue::execute_impl(Bytecode::Interpreter& interpreter) const
 {
     if (auto* object = interpreter.reg(m_base).to_object(interpreter.global_object())) {
diff --git a/Userland/Libraries/LibJS/Bytecode/Op.h b/Userland/Libraries/LibJS/Bytecode/Op.h
index 0ca7ad91ab..653b9d1889 100644
--- a/Userland/Libraries/LibJS/Bytecode/Op.h
+++ b/Userland/Libraries/LibJS/Bytecode/Op.h
@@ -29,6 +29,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Register m_src;
@@ -44,6 +45,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Value m_value;
@@ -59,6 +61,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Register m_dst;
@@ -88,20 +91,21 @@ private:
     O(RightShift, right_shift)                \
     O(UnsignedRightShift, unsigned_right_shift)
 
-#define JS_DECLARE_COMMON_BINARY_OP(OpTitleCase, op_snake_case)   \
-    class OpTitleCase final : public Instruction {                \
-    public:                                                       \
-        explicit OpTitleCase(Register lhs_reg)                    \
-            : Instruction(Type::OpTitleCase)                      \
-            , m_lhs_reg(lhs_reg)                                  \
-        {                                                         \
-        }                                                         \
-                                                                  \
-        void execute_impl(Bytecode::Interpreter&) const;          \
-        String to_string_impl(Bytecode::Executable const&) const; \
-                                                                  \
-    private:                                                      \
-        Register m_lhs_reg;                                       \
+#define JS_DECLARE_COMMON_BINARY_OP(OpTitleCase, op_snake_case)                \
+    class OpTitleCase final : public Instruction {                             \
+    public:                                                                    \
+        explicit OpTitleCase(Register lhs_reg)                                 \
+            : Instruction(Type::OpTitleCase)                                   \
+            , m_lhs_reg(lhs_reg)                                               \
+        {                                                                      \
+        }                                                                      \
+                                                                               \
+        void execute_impl(Bytecode::Interpreter&) const;                       \
+        String to_string_impl(Bytecode::Executable const&) const;              \
+        void replace_references_impl(BasicBlock const&, BasicBlock const&) { } \
+                                                                               \
+    private:                                                                   \
+        Register m_lhs_reg;                                                    \
     };
 
 JS_ENUMERATE_COMMON_BINARY_OPS(JS_DECLARE_COMMON_BINARY_OP)
@@ -114,16 +118,17 @@ JS_ENUMERATE_COMMON_BINARY_OPS(JS_DECLARE_COMMON_BINARY_OP)
     O(UnaryMinus, unary_minus)           \
     O(Typeof, typeof_)
 
-#define JS_DECLARE_COMMON_UNARY_OP(OpTitleCase, op_snake_case)    \
-    class OpTitleCase final : public Instruction {                \
-    public:                                                       \
-        OpTitleCase()                                             \
-            : Instruction(Type::OpTitleCase)                      \
-        {                                                         \
-        }                                                         \
-                                                                  \
-        void execute_impl(Bytecode::Interpreter&) const;          \
-        String to_string_impl(Bytecode::Executable const&) const; \
+#define JS_DECLARE_COMMON_UNARY_OP(OpTitleCase, op_snake_case)                 \
+    class OpTitleCase final : public Instruction {                             \
+    public:                                                                    \
+        OpTitleCase()                                                          \
+            : Instruction(Type::OpTitleCase)                                   \
+        {                                                                      \
+        }                                                                      \
+                                                                               \
+        void execute_impl(Bytecode::Interpreter&) const;                       \
+        String to_string_impl(Bytecode::Executable const&) const;              \
+        void replace_references_impl(BasicBlock const&, BasicBlock const&) { } \
     };
 
 JS_ENUMERATE_COMMON_UNARY_OPS(JS_DECLARE_COMMON_UNARY_OP)
@@ -139,6 +144,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     StringTableIndex m_string;
@@ -153,6 +159,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 };
 
 class NewBigInt final : public Instruction {
@@ -165,6 +172,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Crypto::SignedBigInteger m_bigint;
@@ -183,8 +191,12 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
-    size_t length_impl() const { return sizeof(*this) + sizeof(Register) * m_element_count; }
+    size_t length_impl() const
+    {
+        return sizeof(*this) + sizeof(Register) * m_element_count;
+    }
 
 private:
     size_t m_element_count { 0 };
@@ -201,6 +213,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Register m_lhs;
@@ -216,6 +229,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     StringTableIndex m_identifier;
@@ -231,6 +245,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     StringTableIndex m_identifier;
@@ -246,6 +261,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     StringTableIndex m_property;
@@ -262,6 +278,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Register m_base;
@@ -278,6 +295,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Register m_base;
@@ -294,6 +312,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     Register m_base;
@@ -326,6 +345,10 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&);
+
+    auto& true_target() const { return m_true_target; }
+    auto& false_target() const { return m_false_target; }
 
 protected:
     Optional<Label> m_true_target;
@@ -375,8 +398,12 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
-    size_t length_impl() const { return sizeof(*this) + sizeof(Register) * m_argument_count; }
+    size_t length_impl() const
+    {
+        return sizeof(*this) + sizeof(Register) * m_argument_count;
+    }
 
 private:
     Register m_callee;
@@ -396,6 +423,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     FunctionNode const& m_function_node;
@@ -412,6 +440,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 };
 
 class Increment final : public Instruction {
@@ -423,6 +452,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 };
 
 class Decrement final : public Instruction {
@@ -434,6 +464,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 };
 
 class Throw final : public Instruction {
@@ -447,6 +478,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 };
 
 class EnterUnwindContext final : public Instruction {
@@ -463,6 +495,11 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&);
+
+    auto& entry_point() const { return m_entry_point; }
+    auto& handler_target() const { return m_handler_target; }
+    auto& finalizer_target() const { return m_finalizer_target; }
 
 private:
     Label m_entry_point;
@@ -479,6 +516,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 };
 
 class ContinuePendingUnwind final : public Instruction {
@@ -493,6 +531,9 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&);
+
+    auto& resume_target() const { return m_resume_target; }
 
 private:
     Label m_resume_target;
@@ -515,6 +556,9 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&);
+
+    auto& continuation() const { return m_continuation_label; }
 
 private:
     Optional<Label> m_continuation_label;
@@ -529,6 +573,7 @@ public:
     }
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     HashMap<u32, Variable> m_variables;
@@ -544,6 +589,7 @@ public:
 
     void execute_impl(Bytecode::Interpreter&) const;
     String to_string_impl(Bytecode::Executable const&) const;
+    void replace_references_impl(BasicBlock const&, BasicBlock const&) { }
 
 private:
     size_t m_index { 0 };
@@ -568,6 +614,21 @@ ALWAYS_INLINE void Instruction::execute(Bytecode::Interpreter& interpreter) cons
 #undef __BYTECODE_OP
 }
 
+ALWAYS_INLINE void Instruction::replace_references(BasicBlock const& from, BasicBlock const& to)
+{
+#define __BYTECODE_OP(op)       \
+    case Instruction::Type::op: \
+        return static_cast<Bytecode::Op::op&>(*this).replace_references_impl(from, to);
+
+    switch (type()) {
+        ENUMERATE_BYTECODE_OPS(__BYTECODE_OP)
+    default:
+        VERIFY_NOT_REACHED();
+    }
+
+#undef __BYTECODE_OP
+}
+
 ALWAYS_INLINE size_t Instruction::length() const
 {
     if (type() == Type::Call)
@@ -587,4 +648,18 @@ ALWAYS_INLINE size_t Instruction::length() const
 #undef __BYTECODE_OP
 }
 
+ALWAYS_INLINE bool Instruction::is_terminator() const
+{
+#define __BYTECODE_OP(op) \
+    case Type::op:        \
+        return Op::op::IsTerminator;
+
+    switch (type()) {
+        ENUMERATE_BYTECODE_OPS(__BYTECODE_OP)
+    default:
+        VERIFY_NOT_REACHED();
+    }
+#undef __BYTECODE_OP
+}
+
 }
diff --git a/Userland/Libraries/LibJS/Bytecode/Pass/DumpCFG.cpp b/Userland/Libraries/LibJS/Bytecode/Pass/DumpCFG.cpp
new file mode 100644
index 0000000000..2d41134cfe
--- /dev/null
+++ b/Userland/Libraries/LibJS/Bytecode/Pass/DumpCFG.cpp
@@ -0,0 +1,27 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibJS/Bytecode/PassManager.h>
+#include <stdio.h>
+
+namespace JS::Bytecode::Passes {
+
+void DumpCFG::perform(PassPipelineExecutable& executable)
+{
+    started();
+
+    VERIFY(executable.cfg.has_value());
+    outln(m_file, "CFG Dump for {} basic blocks:", executable.executable.basic_blocks.size());
+    for (auto& entry : executable.cfg.value()) {
+        for (auto& value : entry.value)
+            outln(m_file, "{} -> {}", entry.key->name(), value->name());
+    }
+    outln(m_file);
+
+    finished();
+}
+
+}
diff --git a/Userland/Libraries/LibJS/Bytecode/Pass/GenerateCFG.cpp b/Userland/Libraries/LibJS/Bytecode/Pass/GenerateCFG.cpp
new file mode 100644
index 0000000000..167e3c6052
--- /dev/null
+++ b/Userland/Libraries/LibJS/Bytecode/Pass/GenerateCFG.cpp
@@ -0,0 +1,102 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibJS/Bytecode/PassManager.h>
+
+namespace JS::Bytecode::Passes {
+
+void GenerateCFG::perform(PassPipelineExecutable& executable)
+{
+    started();
+
+    executable.cfg = HashMap<BasicBlock const*, HashTable<BasicBlock const*>> {};
+    executable.inverted_cfg = HashMap<BasicBlock const*, HashTable<BasicBlock const*>> {};
+    executable.exported_blocks = HashTable<BasicBlock const*> {};
+    Vector<InstructionStreamIterator> iterators;
+    Vector<BasicBlock const&> entered_blocks;
+    HashTable<BasicBlock const*> seen_blocks;
+
+    auto enter_label = [&](auto const& label, auto& entering_block, bool exported = false) {
+        auto& entry = executable.cfg->ensure(&entering_block);
+        entry.set(&label->block());
+        auto& inverse_entry = executable.inverted_cfg->ensure(&label->block());
+        inverse_entry.set(&entering_block);
+
+        if (exported)
+            executable.exported_blocks->set(&label->block());
+
+        if (!seen_blocks.contains(&label->block())) {
+            seen_blocks.set(&label->block());
+            entered_blocks.append(label->block());
+            iterators.empend(label->block().instruction_stream());
+        }
+    };
+
+    seen_blocks.set(&executable.executable.basic_blocks.first());
+    entered_blocks.append(executable.executable.basic_blocks.first());
+    iterators.empend(executable.executable.basic_blocks.first().instruction_stream());
+
+    while (!entered_blocks.is_empty()) {
+        if (iterators.last().at_end()) {
+            entered_blocks.take_last();
+            iterators.take_last();
+            continue;
+        }
+        auto& instruction = *iterators.last();
+        ++iterators.last();
+        if (!instruction.is_terminator())
+            continue;
+
+        auto& current_block = entered_blocks.last();
+
+        if (instruction.type() == Instruction::Type::Jump) {
+            auto& true_target = static_cast<Op::Jump const&>(instruction).true_target();
+            enter_label(true_target, current_block);
+            continue;
+        }
+
+        if (instruction.type() == Instruction::Type::JumpConditional || instruction.type() == Instruction::Type::JumpNullish) {
+            auto& true_target = static_cast<Op::Jump const&>(instruction).true_target();
+            enter_label(true_target, current_block);
+            auto& false_target = static_cast<Op::Jump const&>(instruction).false_target();
+            enter_label(false_target, current_block);
+            continue;
+        }
+
+        if (instruction.type() == Instruction::Type::Yield) {
+            auto& continuation = static_cast<Op::Yield const&>(instruction).continuation();
+            if (continuation.has_value())
+                enter_label(continuation, current_block, true);
+            continue;
+        }
+
+        if (instruction.type() == Instruction::Type::EnterUnwindContext) {
+            auto& entry_point = static_cast<Op::EnterUnwindContext const&>(instruction).entry_point();
+            auto& handler_target = static_cast<Op::EnterUnwindContext const&>(instruction).handler_target();
+            auto& finalizer_target = static_cast<Op::EnterUnwindContext const&>(instruction).finalizer_target();
+            enter_label(&entry_point, current_block);
+            if (handler_target.has_value())
+                enter_label(handler_target, current_block);
+            if (finalizer_target.has_value())
+                enter_label(finalizer_target, current_block);
+            continue;
+        }
+
+        if (instruction.type() == Instruction::Type::ContinuePendingUnwind) {
+            auto& resume_target = static_cast<Op::ContinuePendingUnwind const&>(instruction).resume_target();
+            enter_label(&resume_target, current_block);
+            continue;
+        }
+
+        // Otherwise, pop the current block off, it doesn't jump anywhere.
+        iterators.take_last();
+        entered_blocks.take_last();
+    }
+
+    finished();
+}
+
+}
diff --git a/Userland/Libraries/LibJS/Bytecode/Pass/MergeBlocks.cpp b/Userland/Libraries/LibJS/Bytecode/Pass/MergeBlocks.cpp
new file mode 100644
index 0000000000..a3b00857b9
--- /dev/null
+++ b/Userland/Libraries/LibJS/Bytecode/Pass/MergeBlocks.cpp
@@ -0,0 +1,165 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibJS/Bytecode/PassManager.h>
+
+namespace JS::Bytecode::Passes {
+
+void MergeBlocks::perform(PassPipelineExecutable& executable)
+{
+    started();
+
+    VERIFY(executable.cfg.has_value());
+    VERIFY(executable.inverted_cfg.has_value());
+    auto cfg = executable.cfg.release_value();
+    auto inverted_cfg = executable.inverted_cfg.release_value();
+
+    // Figure out which blocks can be merged
+    HashTable<BasicBlock const*> blocks_to_merge;
+    HashMap<BasicBlock const*, BasicBlock const*> blocks_to_replace;
+    Vector<BasicBlock const*> blocks_to_remove;
+    Vector<size_t> boundaries;
+
+    for (auto& entry : cfg) {
+        if (entry.value.size() != 1)
+            continue;
+
+        if (executable.exported_blocks->contains(*entry.value.begin()))
+            continue;
+
+        {
+            InstructionStreamIterator it { entry.key->instruction_stream() };
+            auto& first_instruction = *it;
+            if (first_instruction.is_terminator()) {
+                if (first_instruction.type() == Instruction::Type::Jump) {
+                    auto replacing_block = &static_cast<Op::Jump const&>(first_instruction).true_target()->block();
+                    if (replacing_block != entry.key)
+                        blocks_to_replace.set(entry.key, replacing_block);
+                    continue;
+                }
+            }
+        }
+
+        if (auto cfg_entry = inverted_cfg.get(*entry.value.begin()); cfg_entry.has_value()) {
+            auto& predecssor_entry = *cfg_entry;
+            if (predecssor_entry.size() != 1)
+                continue;
+        }
+
+        // The two blocks are safe to merge.
+        blocks_to_merge.set(entry.key);
+    }
+
+    for (auto& entry : blocks_to_replace) {
+        auto replacement = entry.value;
+        for (;;) {
+            auto lookup = blocks_to_replace.get(replacement);
+            if (!lookup.has_value())
+                break;
+            if (replacement == *lookup)
+                break;
+            replacement = *lookup;
+        }
+        entry.value = replacement;
+    }
+
+    auto replace_blocks = [&](auto& blocks, auto& replacement) {
+        Optional<size_t> first_successor_position;
+        for (auto& entry : blocks) {
+            blocks_to_remove.append(entry);
+            auto it = executable.executable.basic_blocks.find_if([entry](auto& block) { return entry == block; });
+            VERIFY(!it.is_end());
+            if (!first_successor_position.has_value())
+                first_successor_position = it.index();
+        }
+        for (auto& block : executable.executable.basic_blocks) {
+            InstructionStreamIterator it { block.instruction_stream() };
+            while (!it.at_end()) {
+                auto& instruction = *it;
+                ++it;
+                for (auto& entry : blocks)
+                    const_cast<Instruction&>(instruction).replace_references(*entry, replacement);
+            }
+        }
+        return first_successor_position;
+    };
+
+    for (auto& entry : blocks_to_replace) {
+        AK::Array candidates { entry.key };
+        (void)replace_blocks(candidates, *entry.value);
+    }
+
+    while (!blocks_to_merge.is_empty()) {
+        auto it = blocks_to_merge.begin();
+        auto current_block = *it;
+        blocks_to_merge.remove(it);
+        Vector<BasicBlock const*> successors { current_block };
+        for (;;) {
+            auto last = successors.last();
+            auto entry = cfg.get(last);
+            if (!entry.has_value())
+                break;
+            auto& successor = *entry->begin();
+            successors.append(successor);
+            auto it = blocks_to_merge.find(successor);
+            if (it == blocks_to_merge.end())
+                break;
+            blocks_to_merge.remove(it);
+        }
+
+        auto blocks_to_merge_copy = blocks_to_merge;
+        for (auto& last : blocks_to_merge) {
+            auto entry = cfg.get(last);
+            if (!entry.has_value())
+                continue;
+            auto successor = *entry->begin();
+            if (auto it = successors.find(successor); !it.is_end()) {
+                successors.insert(it.index(), last);
+                blocks_to_merge_copy.remove(last);
+            }
+        }
+
+        blocks_to_merge = move(blocks_to_merge_copy);
+
+        size_t size = 0;
+        StringBuilder builder;
+        builder.append("merge");
+        for (auto& entry : successors) {
+            size += entry->size();
+            builder.append('.');
+            builder.append(entry->name());
+        }
+
+        auto new_block = BasicBlock::create(builder.build(), size);
+        auto& block = *new_block;
+
+        size_t last_successor_index = successors.size() - 1;
+        for (size_t i = 0; i < successors.size(); ++i) {
+            auto& entry = successors[i];
+            InstructionStreamIterator it { entry->instruction_stream() };
+            size_t copy_end = 0;
+            while (!it.at_end()) {
+                auto& instruction = *it;
+                ++it;
+                if (instruction.is_terminator() && last_successor_index != i)
+                    break;
+                copy_end = it.offset();
+            }
+            __builtin_memcpy(block.next_slot(), entry->instruction_stream().data(), copy_end);
+            block.grow(copy_end);
+        }
+
+        auto first_successor_position = replace_blocks(successors, *new_block);
+        VERIFY(first_successor_position.has_value());
+        executable.executable.basic_blocks.insert(*first_successor_position, move(new_block));
+    }
+
+    executable.executable.basic_blocks.remove_all_matching([&blocks_to_remove](auto& candidate) { return blocks_to_remove.contains_slow(candidate.ptr()); });
+
+    finished();
+}
+
+}
diff --git a/Userland/Libraries/LibJS/Bytecode/Pass/PlaceBlocks.cpp b/Userland/Libraries/LibJS/Bytecode/Pass/PlaceBlocks.cpp
new file mode 100644
index 0000000000..4a320ac470
--- /dev/null
+++ b/Userland/Libraries/LibJS/Bytecode/Pass/PlaceBlocks.cpp
@@ -0,0 +1,54 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibJS/Bytecode/PassManager.h>
+
+namespace JS::Bytecode::Passes {
+
+void PlaceBlocks::perform(PassPipelineExecutable& executable)
+{
+    started();
+
+    VERIFY(executable.cfg.has_value());
+    auto cfg = executable.cfg.release_value();
+
+    Vector<BasicBlock&> replaced_blocks;
+    HashTable<BasicBlock const*> reachable_blocks;
+
+    // Visit the blocks in CFG order
+    AK::Function<void(BasicBlock const*)> visit = [&](auto* block) {
+        if (reachable_blocks.contains(block))
+            return;
+
+        reachable_blocks.set(block);
+        replaced_blocks.append(*const_cast<BasicBlock*>(block));
+
+        for (auto& entry : cfg.get(block).value_or({}))
+            visit(entry);
+    };
+
+    // Make sure to visit the entry block first
+    visit(&executable.executable.basic_blocks.first());
+
+    for (auto& entry : cfg)
+        visit(entry.key);
+
+    // Put the unreferenced blocks back in at the end
+    for (auto& entry : static_cast<Vector<NonnullOwnPtr<BasicBlock>>&>(executable.executable.basic_blocks)) {
+        if (reachable_blocks.contains(entry.ptr()))
+            (void)entry.leak_ptr();
+        else
+            replaced_blocks.append(*entry.leak_ptr()); // Don't try to do DCE here.
+    }
+
+    executable.executable.basic_blocks.clear();
+    for (auto& block : replaced_blocks)
+        executable.executable.basic_blocks.append(adopt_own(block));
+
+    finished();
+}
+
+}
diff --git a/Userland/Libraries/LibJS/Bytecode/Pass/UnifySameBlocks.cpp b/Userland/Libraries/LibJS/Bytecode/Pass/UnifySameBlocks.cpp
new file mode 100644
index 0000000000..70be9244e2
--- /dev/null
+++ b/Userland/Libraries/LibJS/Bytecode/Pass/UnifySameBlocks.cpp
@@ -0,0 +1,62 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibJS/Bytecode/PassManager.h>
+#include <string.h>
+
+namespace JS::Bytecode::Passes {
+
+void UnifySameBlocks::perform(PassPipelineExecutable& executable)
+{
+    started();
+
+    VERIFY(executable.cfg.has_value());
+    VERIFY(executable.inverted_cfg.has_value());
+    auto cfg = executable.cfg.release_value();
+    auto inverted_cfg = executable.inverted_cfg.release_value();
+
+    HashMap<BasicBlock const*, BasicBlock const*> equal_blocks;
+
+    for (size_t i = 0; i < executable.executable.basic_blocks.size(); ++i) {
+        auto& block = executable.executable.basic_blocks[i];
+        auto block_bytes = block.instruction_stream();
+        for (auto& candidate_block : executable.executable.basic_blocks.span().slice(i + 1)) {
+            // FIXME: This can probably be relaxed a bit...
+            if (candidate_block->size() != block.size())
+                continue;
+
+            auto candidate_bytes = candidate_block->instruction_stream();
+            if (memcmp(candidate_bytes.data(), block_bytes.data(), candidate_block->size()) == 0)
+                equal_blocks.set(&*candidate_block, &block);
+        }
+    }
+
+    auto replace_blocks = [&](auto& match, auto& replacement) {
+        Optional<size_t> first_successor_position;
+        auto it = executable.executable.basic_blocks.find_if([match](auto& block) { return match == block; });
+        VERIFY(!it.is_end());
+        executable.executable.basic_blocks.remove(it.index());
+        if (!first_successor_position.has_value())
+            first_successor_position = it.index();
+
+        for (auto& block : executable.executable.basic_blocks) {
+            InstructionStreamIterator it { block.instruction_stream() };
+            while (!it.at_end()) {
+                auto& instruction = *it;
+                ++it;
+                const_cast<Instruction&>(instruction).replace_references(*match, replacement);
+            }
+        }
+        return first_successor_position;
+    };
+
+    for (auto& entry : equal_blocks)
+        (void)replace_blocks(entry.key, *entry.value);
+
+    finished();
+}
+
+}
diff --git a/Userland/Libraries/LibJS/Bytecode/PassManager.h b/Userland/Libraries/LibJS/Bytecode/PassManager.h
new file mode 100644
index 0000000000..b4a44da5c5
--- /dev/null
+++ b/Userland/Libraries/LibJS/Bytecode/PassManager.h
@@ -0,0 +1,141 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <LibJS/Bytecode/BasicBlock.h>
+#include <LibJS/Bytecode/Generator.h>
+#include <sys/time.h>
+#include <time.h>
+
+namespace JS::Bytecode {
+
+struct PassPipelineExecutable {
+    Executable& executable;
+    Optional<HashMap<BasicBlock const*, HashTable<BasicBlock const*>>> cfg {};
+    Optional<HashMap<BasicBlock const*, HashTable<BasicBlock const*>>> inverted_cfg {};
+    Optional<HashTable<BasicBlock const*>> exported_blocks {};
+};
+
+class Pass {
+public:
+    Pass() = default;
+    virtual ~Pass() = default;
+
+    virtual void perform(PassPipelineExecutable&) = 0;
+    void started()
+    {
+        gettimeofday(&m_start_time, nullptr);
+    }
+    void finished()
+    {
+        struct timeval end_time {
+            0, 0
+        };
+        gettimeofday(&end_time, nullptr);
+        time_t interval_s = end_time.tv_sec - m_start_time.tv_sec;
+        suseconds_t interval_us = end_time.tv_usec;
+        if (interval_us < m_start_time.tv_usec) {
+            interval_s -= 1;
+            interval_us += 1000000;
+        }
+        interval_us -= m_start_time.tv_usec;
+        m_time_difference = interval_s * 1000000 + interval_us;
+    }
+
+    u64 elapsed() const { return m_time_difference; }
+
+protected:
+    struct timeval m_start_time {
+        0, 0
+    };
+    u64 m_time_difference { 0 };
+};
+
+class PassManager : public Pass {
+public:
+    PassManager() = default;
+    ~PassManager() override = default;
+
+    void add(NonnullOwnPtr<Pass> pass) { m_passes.append(move(pass)); }
+
+    template<typename PassT, typename... Args>
+    void add(Args&&... args) { m_passes.append(make<PassT>(forward<Args>(args)...)); }
+
+    void perform(Executable& executable)
+    {
+        PassPipelineExecutable pipeline_executable { executable };
+        perform(pipeline_executable);
+    }
+
+    virtual void perform(PassPipelineExecutable& executable) override
+    {
+        started();
+        for (auto& pass : m_passes)
+            pass.perform(executable);
+        finished();
+    }
+
+private:
+    NonnullOwnPtrVector<Pass> m_passes;
+};
+
+namespace Passes {
+
+class GenerateCFG : public Pass {
+public:
+    GenerateCFG() = default;
+    ~GenerateCFG() override = default;
+
+private:
+    virtual void perform(PassPipelineExecutable&) override;
+};
+
+class MergeBlocks : public Pass {
+public:
+    MergeBlocks() = default;
+    ~MergeBlocks() override = default;
+
+private:
+    virtual void perform(PassPipelineExecutable&) override;
+};
+
+class PlaceBlocks : public Pass {
+public:
+    PlaceBlocks() = default;
+    ~PlaceBlocks() override = default;
+
+private:
+    virtual void perform(PassPipelineExecutable&) override;
+};
+
+class UnifySameBlocks : public Pass {
+public:
+    UnifySameBlocks() = default;
+    ~UnifySameBlocks() override = default;
+
+private:
+    virtual void perform(PassPipelineExecutable&) override;
+};
+
+class DumpCFG : public Pass {
+public:
+    DumpCFG(FILE* file)
+        : m_file(file)
+    {
+    }
+
+    ~DumpCFG() override = default;
+
+private:
+    virtual void perform(PassPipelineExecutable&) override;
+
+    FILE* m_file { nullptr };
+};
+
+}
+
+}
diff --git a/Userland/Libraries/LibJS/CMakeLists.txt b/Userland/Libraries/LibJS/CMakeLists.txt
index 7838999228..a7369a2440 100644
--- a/Userland/Libraries/LibJS/CMakeLists.txt
+++ b/Userland/Libraries/LibJS/CMakeLists.txt
@@ -6,6 +6,11 @@ set(SOURCES
     Bytecode/Instruction.cpp
     Bytecode/Interpreter.cpp
     Bytecode/Op.cpp
+    Bytecode/Pass/DumpCFG.cpp
+    Bytecode/Pass/GenerateCFG.cpp
+    Bytecode/Pass/MergeBlocks.cpp
+    Bytecode/Pass/PlaceBlocks.cpp
+    Bytecode/Pass/UnifySameBlocks.cpp
     Bytecode/StringTable.cpp
     Console.cpp
     Heap/CellAllocator.cpp
diff --git a/Userland/Libraries/LibJS/Runtime/ScriptFunction.cpp b/Userland/Libraries/LibJS/Runtime/ScriptFunction.cpp
index 433e6cd807..f90304190b 100644
--- a/Userland/Libraries/LibJS/Runtime/ScriptFunction.cpp
+++ b/Userland/Libraries/LibJS/Runtime/ScriptFunction.cpp
@@ -10,6 +10,7 @@
 #include <LibJS/Bytecode/BasicBlock.h>
 #include <LibJS/Bytecode/Generator.h>
 #include <LibJS/Bytecode/Interpreter.h>
+#include <LibJS/Bytecode/PassManager.h>
 #include <LibJS/Interpreter.h>
 #include <LibJS/Runtime/Array.h>
 #include <LibJS/Runtime/Error.h>
@@ -159,7 +160,10 @@ Value ScriptFunction::execute_function_body()
         prepare_arguments();
         if (!m_bytecode_executable.has_value()) {
             m_bytecode_executable = Bytecode::Generator::generate(m_body, m_kind == FunctionKind::Generator);
+            auto& passes = JS::Bytecode::Interpreter::optimization_pipeline();
+            passes.perform(*m_bytecode_executable);
             if constexpr (JS_BYTECODE_DEBUG) {
+                dbgln("Optimisation passes took {}us", passes.elapsed());
                 dbgln("Compiled Bytecode::Block for function '{}':", m_name);
                 for (auto& block : m_bytecode_executable->basic_blocks)
                     block.dump(*m_bytecode_executable);
diff --git a/Userland/Utilities/js.cpp b/Userland/Utilities/js.cpp
index 1ad0d7f852..e7dafdd424 100644
--- a/Userland/Utilities/js.cpp
+++ b/Userland/Utilities/js.cpp
@@ -17,6 +17,7 @@
 #include <LibJS/Bytecode/BasicBlock.h>
 #include <LibJS/Bytecode/Generator.h>
 #include <LibJS/Bytecode/Interpreter.h>
+#include <LibJS/Bytecode/PassManager.h>
 #include <LibJS/Console.h>
 #include <LibJS/Interpreter.h>
 #include <LibJS/Parser.h>
@@ -81,6 +82,7 @@ private:
 static bool s_dump_ast = false;
 static bool s_dump_bytecode = false;
 static bool s_run_bytecode = false;
+static bool s_opt_bytecode = false;
 static bool s_print_last_result = false;
 static RefPtr<Line::Editor> s_editor;
 static String s_history_path = String::formatted("{}/.js-history", Core::StandardPaths::home_directory());
@@ -558,6 +560,12 @@ static bool parse_and_run(JS::Interpreter& interpreter, const StringView& source
     } else {
         if (s_dump_bytecode || s_run_bytecode) {
             auto unit = JS::Bytecode::Generator::generate(*program);
+            if (s_opt_bytecode) {
+                auto& passes = JS::Bytecode::Interpreter::optimization_pipeline();
+                passes.perform(unit);
+                dbgln("Optimisation passes took {}us", passes.elapsed());
+            }
+
             if (s_dump_bytecode) {
                 for (auto& block : unit.basic_blocks)
                     block.dump(unit);
@@ -825,6 +833,7 @@ int main(int argc, char** argv)
     args_parser.add_option(s_dump_ast, "Dump the AST", "dump-ast", 'A');
     args_parser.add_option(s_dump_bytecode, "Dump the bytecode", "dump-bytecode", 'd');
     args_parser.add_option(s_run_bytecode, "Run the bytecode", "run-bytecode", 'b');
+    args_parser.add_option(s_opt_bytecode, "Optimize the bytecode", "optimize-bytecode", 'p');
     args_parser.add_option(s_print_last_result, "Print last result", "print-last-result", 'l');
     args_parser.add_option(gc_on_every_allocation, "GC on every allocation", "gc-on-every-allocation", 'g');
     args_parser.add_option(disable_syntax_highlight, "Disable live syntax highlighting", "no-syntax-highlight", 's');