QmlCompiler: Add basic block analysis pass

This basic block analysis pass uses the tracked types to determine dead stores. This is better than the one we already have in the code generator because it also tracks dead stores through renames and it allows removal of lookup results. Furthermore, it adjusts each store to write the type most favorable to its readers. This avoids unnecessary conversions at run time. It cannot replace the other dead store elimination, yet, because it doesn't see whether the results of rename operations are read after the rename. This capability will be added in a separate change that also tracks the register numbers. Once this is in place, we can delete the other basic blocks pass. Task-number: QTBUG-100157 Change-Id: I766c919412b6cf43befa7bdb1a6e5e11b41fe55b Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
author: Ulf Hermann <ulf.hermann@qt.io> 2022-02-16 16:34:56 +0100
committer: Ulf Hermann <ulf.hermann@qt.io> 2022-03-09 12:40:06 +0100
commit: 9ee2df1e3b648d706805ef1e32c853c19d27e1a2 (patch)
tree: 67795bace9e2ad26d9c4c1f176423e8b313ba794 /src/qmlcompiler/qqmljsbasicblocks.cpp
parent: e86019ecbddd76d6551a18595ef9dcff8560f1d4 (diff)
1 files changed, 397 insertions, 0 deletions
diff --git a/src/qmlcompiler/qqmljsbasicblocks.cpp b/src/qmlcompiler/qqmljsbasicblocks.cpp
new file mode 100644
index 0000000000..ebd0458897
--- /dev/null
+++ b/src/qmlcompiler/qqmljsbasicblocks.cpp
@@ -0,0 +1,397 @@
+/****************************************************************************
+**
+** Copyright (C) 2022 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the tools applications of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** 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 The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qqmljsbasicblocks_p.h"
+
+QT_BEGIN_NAMESPACE
+
+template<typename Container>
+void deduplicate(Container &container)
+{
+    std::sort(container.begin(), container.end());
+    auto erase = std::unique(container.begin(), container.end());
+    container.erase(erase, container.end());
+}
+
+static bool instructionManipulatesContext(QV4::Moth::Instr::Type type)
+{
+    using Type = QV4::Moth::Instr::Type;
+    switch (type) {
+    case Type::PopContext:
+    case Type::PopScriptContext:
+    case Type::CreateCallContext:
+    case Type::CreateCallContext_Wide:
+    case Type::PushCatchContext:
+    case Type::PushCatchContext_Wide:
+    case Type::PushWithContext:
+    case Type::PushWithContext_Wide:
+    case Type::PushBlockContext:
+    case Type::PushBlockContext_Wide:
+    case Type::CloneBlockContext:
+    case Type::CloneBlockContext_Wide:
+    case Type::PushScriptContext:
+    case Type::PushScriptContext_Wide:
+        return true;
+    default:
+        break;
+    }
+    return false;
+}
+
+QQmlJSCompilePass::InstructionAnnotations QQmlJSBasicBlocks::run(
+        const Function *function,
+        const InstructionAnnotations &annotations)
+{
+    m_annotations = annotations;
+    m_basicBlocks.insert_or_assign(0, BasicBlock());
+
+    const QByteArray byteCode = function->code;
+    decode(byteCode.constData(), static_cast<uint>(byteCode.length()));
+    if (m_hadBackJumps) {
+        // We may have missed some connections between basic blocks if there were back jumps.
+        // Fill them in via a second pass.
+        reset();
+        decode(byteCode.constData(), static_cast<uint>(byteCode.length()));
+        for (auto it = m_basicBlocks.begin(), end = m_basicBlocks.end(); it != end; ++it)
+            deduplicate(it->second.jumpOrigins);
+    }
+
+    populateBasicBlocks();
+    populateReaderLocations();
+    adjustTypes();
+    return std::move(m_annotations);
+}
+
+QV4::Moth::ByteCodeHandler::Verdict QQmlJSBasicBlocks::startInstruction(QV4::Moth::Instr::Type type)
+{
+    auto it = m_basicBlocks.find(currentInstructionOffset());
+    if (it != m_basicBlocks.end()) {
+        if (!m_skipUntilNextLabel && it != m_basicBlocks.begin())
+            it->second.jumpOrigins.append((--it)->first);
+        m_skipUntilNextLabel = false;
+    } else if (m_skipUntilNextLabel && !instructionManipulatesContext(type)) {
+        return SkipInstruction;
+    }
+
+    return ProcessInstruction;
+}
+
+void QQmlJSBasicBlocks::endInstruction(QV4::Moth::Instr::Type)
+{
+}
+
+void QQmlJSBasicBlocks::generate_Jump(int offset)
+{
+    processJump(offset, Unconditional);
+}
+
+void QQmlJSBasicBlocks::generate_JumpTrue(int offset)
+{
+    processJump(offset, Conditional);
+}
+
+void QQmlJSBasicBlocks::generate_JumpFalse(int offset)
+{
+    processJump(offset, Conditional);
+}
+
+void QQmlJSBasicBlocks::generate_JumpNoException(int offset)
+{
+    processJump(offset, Conditional);
+}
+
+void QQmlJSBasicBlocks::generate_JumpNotUndefined(int offset)
+{
+    processJump(offset, Conditional);
+}
+
+void QQmlJSBasicBlocks::generate_Ret()
+{
+    m_skipUntilNextLabel = true;
+}
+
+void QQmlJSBasicBlocks::generate_ThrowException()
+{
+    m_skipUntilNextLabel = true;
+}
+
+void QQmlJSBasicBlocks::processJump(int offset, JumpMode mode)
+{
+    if (offset < 0)
+        m_hadBackJumps = true;
+    const int jumpTarget = absoluteOffset(offset);
+    Q_ASSERT(!m_basicBlocks.isEmpty());
+    auto currentBlock = m_basicBlocks.lower_bound(currentInstructionOffset());
+    if (currentBlock == m_basicBlocks.end() || currentBlock->first != currentInstructionOffset())
+        --currentBlock;
+    currentBlock->second.jumpTarget = jumpTarget;
+    currentBlock->second.jumpIsUnconditional = (mode == Unconditional);
+    m_basicBlocks[jumpTarget].jumpOrigins.append(currentInstructionOffset());
+    if (mode == Unconditional)
+        m_skipUntilNextLabel = true;
+    else
+        m_basicBlocks[nextInstructionOffset()].jumpOrigins.append(currentInstructionOffset());
+}
+
+template<typename ContainerA, typename ContainerB>
+static bool containsAny(const ContainerA &container, const ContainerB &elements)
+{
+    for (const auto &element : elements) {
+        if (container.contains(element))
+            return true;
+    }
+    return false;
+}
+
+template<class Key, class T, class Compare = std::less<Key>,
+         class KeyContainer = QList<Key>, class MappedContainer = QList<T>>
+class NewFlatMap
+{
+public:
+    using OriginalFlatMap = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>;
+
+    void appendOrdered(const typename OriginalFlatMap::iterator &i) {
+        keys.append(i.key());
+        values.append(i.value());
+    }
+
+    OriginalFlatMap take() {
+        OriginalFlatMap result(Qt::OrderedUniqueRange, std::move(keys), std::move(values));
+        keys.clear();
+        values.clear();
+        return result;
+    }
+
+private:
+    typename OriginalFlatMap::key_container_type keys;
+    typename OriginalFlatMap::mapped_container_type values;
+};
+
+void QQmlJSBasicBlocks::populateReaderLocations()
+{
+    using NewInstructionAnnotations = NewFlatMap<int, InstructionAnnotation>;
+
+    bool erasedReaders = false;
+    auto eraseDeadStore = [&](const InstructionAnnotations::iterator &it) {
+        auto reader = m_readerLocations.find(it.key());
+        if (reader != m_readerLocations.end() && reader->readers.isEmpty()) {
+
+            // void the output, rather than deleting it. We still need its variant.
+            m_typeResolver->adjustTrackedType(
+                        it->second.changedRegister.storedType(),
+                        m_typeResolver->voidType());
+            m_typeResolver->adjustTrackedType(
+                        m_typeResolver->containedType(it->second.changedRegister),
+                        m_typeResolver->voidType());
+            m_readerLocations.erase(reader);
+
+            // If it's not a label and has no side effects, we can drop the instruction.
+            if (!it->second.hasSideEffects && m_basicBlocks.find(it.key()) == m_basicBlocks.end()) {
+                if (!it->second.readRegisters.isEmpty()) {
+                    it->second.readRegisters.clear();
+                    erasedReaders = true;
+                }
+                return true;
+            }
+        }
+        return false;
+    };
+
+    NewInstructionAnnotations newAnnotations;
+    for (auto writeIt = m_annotations.begin(), writeEnd = m_annotations.end();
+         writeIt != writeEnd; ++writeIt) {
+        const int writtenRegister = writeIt->second.changedRegisterIndex;
+        if (writtenRegister == InvalidRegister) {
+            newAnnotations.appendOrdered(writeIt);
+            continue;
+        }
+
+        RegisterAccess &access = m_readerLocations[writeIt.key()];
+        if (writeIt->second.changedRegister.isConversion()) {
+            // If it's a conversion, we have to check for all readers of the conversion origins.
+            // This happens at jump targets where different types are merged. A StoreReg or similar
+            // instruction must be optimized out if none of the types it can hold is read anymore.
+            access.trackedTypes = writeIt->second.changedRegister.conversionOrigins();
+        } else {
+            access.trackedTypes.append(
+                    m_typeResolver->trackedContainedType(writeIt->second.changedRegister));
+        }
+
+        auto blockIt = m_basicBlocks.lower_bound(writeIt.key());
+        if (blockIt == m_basicBlocks.end() || blockIt->first != writeIt.key())
+            --blockIt;
+
+        QList<int> blocks = { blockIt->first };
+        QList<int> processedBlocks;
+        bool isFirstBlock = true;
+
+        while (!blocks.isEmpty()) {
+            auto nextBlock = m_basicBlocks.find(blocks.takeLast());
+            auto currentBlock = nextBlock++;
+
+            if (isFirstBlock
+                    || containsAny(currentBlock->second.readRegisters, access.trackedTypes)) {
+                const auto blockEnd = (nextBlock == m_basicBlocks.end())
+                        ? m_annotations.end()
+                        : m_annotations.find(nextBlock->first);
+
+                auto blockInstr = isFirstBlock
+                        ? (writeIt + 1)
+                        : m_annotations.find(currentBlock->first);
+                for (; blockInstr != blockEnd; ++blockInstr) {
+                    for (auto readIt = blockInstr->second.readRegisters.constBegin(),
+                         end = blockInstr->second.readRegisters.constEnd();
+                         readIt != end; ++readIt) {
+                        Q_ASSERT(readIt->second.isConversion());
+                        if (containsAny(readIt->second.conversionOrigins(), access.trackedTypes))
+                            access.readers[blockInstr.key()] = readIt->second.conversionResult();
+                    }
+                }
+            }
+
+            if (!currentBlock->second.jumpIsUnconditional && nextBlock != m_basicBlocks.end()
+                    && !processedBlocks.contains(nextBlock->first)) {
+                blocks.append(nextBlock->first);
+            }
+
+            const int jumpTarget = currentBlock->second.jumpTarget;
+            if (jumpTarget != -1 && !processedBlocks.contains(jumpTarget))
+                blocks.append(jumpTarget);
+
+            // We can re-enter the first block from the beginning.
+            // We will then find any reads before the write we're currently examining.
+            if (isFirstBlock)
+                isFirstBlock = false;
+            else
+                processedBlocks.append(currentBlock->first);
+        }
+
+        if (!eraseDeadStore(writeIt))
+            newAnnotations.appendOrdered(writeIt);
+    }
+    m_annotations = newAnnotations.take();
+
+    while (erasedReaders) {
+        erasedReaders = false;
+
+        for (auto it = m_annotations.begin(), end = m_annotations.end(); it != end; ++it) {
+            InstructionAnnotation &instruction = it->second;
+            if (instruction.changedRegisterIndex < InvalidRegister) {
+                newAnnotations.appendOrdered(it);
+                continue;
+            }
+
+            auto readers = m_readerLocations.find(it.key());
+            if (readers != m_readerLocations.end()) {
+                for (auto it = readers->readers.begin(); it != readers->readers.end();) {
+                    if (m_annotations.contains(it.key()))
+                        ++it;
+                    else
+                        it = readers->readers.erase(it);
+                }
+            }
+
+            if (!eraseDeadStore(it))
+                newAnnotations.appendOrdered(it);
+        }
+
+        m_annotations = newAnnotations.take();
+    }
+}
+
+void QQmlJSBasicBlocks::adjustTypes()
+{
+    using NewVirtualRegisters = NewFlatMap<int, QQmlJSRegisterContent>;
+
+    for (auto it = m_readerLocations.begin(), end = m_readerLocations.end(); it != end; ++it) {
+        // There is always one first occurrence of any tracked type. Conversions don't change
+        // the type.
+        if (it->trackedTypes.length() != 1)
+            continue;
+
+        m_typeResolver->adjustTrackedType(it->trackedTypes[0], it->readers.values());
+    }
+
+    const auto transformRegister = [&](QQmlJSRegisterContent &content) {
+        m_typeResolver->adjustTrackedType(
+                    content.storedType(),
+                    m_typeResolver->storedType(m_typeResolver->containedType(content)));
+    };
+
+    NewVirtualRegisters newRegisters;
+    for (auto i = m_annotations.begin(), iEnd = m_annotations.end(); i != iEnd; ++i) {
+        if (i->second.changedRegisterIndex != InvalidRegister)
+            transformRegister(i->second.changedRegister);
+        for (auto content : i->second.typeConversions) {
+            QQmlJSScope::ConstPtr conversionResult = content.second.conversionResult();
+            const auto conversionOrigins = content.second.conversionOrigins();
+            QQmlJSScope::ConstPtr newResult;
+            for (const auto &origin : conversionOrigins)
+                newResult = m_typeResolver->merge(newResult, origin);
+            m_typeResolver->adjustTrackedType(conversionResult, newResult);
+            transformRegister(content.second);
+        }
+        i->second.typeConversions = newRegisters.take();
+    }
+}
+
+void QQmlJSBasicBlocks::populateBasicBlocks()
+{
+    for (auto blockNext = m_basicBlocks.begin(), blockEnd = m_basicBlocks.end();
+         blockNext != blockEnd;) {
+
+        const auto blockIt = blockNext++;
+        BasicBlock &block = blockIt->second;
+        QList<QQmlJSScope::ConstPtr> writtenRegisters;
+
+        const auto instrEnd = (blockNext == blockEnd)
+                ? m_annotations.end()
+                : m_annotations.find(blockNext->first);
+        for (auto instrIt = m_annotations.find(blockIt->first); instrIt != instrEnd; ++instrIt) {
+            const InstructionAnnotation &instruction = instrIt->second;
+            for (auto it = instruction.readRegisters.begin(), end = instruction.readRegisters.end();
+                 it != end; ++it) {
+                Q_ASSERT(it->second.isConversion());
+                for (const QQmlJSScope::ConstPtr &origin : it->second.conversionOrigins()) {
+                    if (!writtenRegisters.contains(origin))
+                        block.readRegisters.append(origin);
+                }
+            }
+
+            // If it's just a renaming, the type has existed in a different register before.
+            if (instruction.changedRegisterIndex != InvalidRegister && !instruction.isRename) {
+                writtenRegisters.append(m_typeResolver->trackedContainedType(
+                                            instruction.changedRegister));
+            }
+        }
+
+        deduplicate(block.readRegisters);
+    }
+}
+
+QT_END_NAMESPACE
author	Ulf Hermann <ulf.hermann@qt.io>	2022-02-16 16:34:56 +0100
committer	Ulf Hermann <ulf.hermann@qt.io>	2022-03-09 12:40:06 +0100
commit	9ee2df1e3b648d706805ef1e32c853c19d27e1a2 (patch)
tree	67795bace9e2ad26d9c4c1f176423e8b313ba794 /src/qmlcompiler/qqmljsbasicblocks.cpp
parent	e86019ecbddd76d6551a18595ef9dcff8560f1d4 (diff)