Revision control
Copy as Markdown
// Copyright (C) 2024 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
// Qt-Security score:significant
#include "qqmljsoptimizations_p.h"
#include "qqmljsbasicblocks_p.h"
#include "qqmljsutils_p.h"
#include <QtCore/qhash.h>
#include <QtCore/qset.h>
QT_BEGIN_NAMESPACE
using namespace Qt::Literals::StringLiterals;
QQmlJSCompilePass::BlocksAndAnnotations QQmlJSOptimizations::run(const Function *function)
{
m_function = function;
populateBasicBlocks();
populateReaderLocationsTrackedTypes();
populateReaderLocationsReadersAndConversions();
removeDeadStoresUntilStable();
adjustTypes();
return { std::move(m_basicBlocks), std::move(m_annotations) };
}
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 QQmlJSOptimizations::populateReaderLocationsTrackedTypes()
{
for (const auto &[offset, annotation] : m_annotations) {
const int writtenRegister = annotation.changedRegisterIndex;
// Instructions that don't write can't be dead stores, no need to populate reader locations
if (writtenRegister == InvalidRegister)
continue;
RegisterAccess &access = m_readerLocations[offset];
access.trackedRegister = writtenRegister;
if (annotation.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.
const auto &origins = annotation.changedRegister.conversionOrigins();
for (QQmlJSRegisterContent origin : origins)
access.trackedTypes.append(origin);
} else {
access.trackedTypes.append(annotation.changedRegister);
Q_ASSERT(!access.trackedTypes.last().isNull());
}
}
}
// Every write that currently reaches this program point for this register, and the
// type-conversion instructions crossed since each one specifically. Almost always a
// single entry; more than one only at a genuine merge of differing reaching writes.
using RegisterState = QHash<int, QQmlJSOptimizations::Conversions>;
struct BlockState
{
QHash<QQmlJSRegisterContent, QSet<int>> availableContent; // content -> writers reaching here
QHash<int, RegisterState> registers; // register index -> reaching state
};
static bool mergeBlockState(BlockState &to, const BlockState &from)
{
bool changed = false;
for (auto contentIt = from.availableContent.constBegin(),
contentEnd = from.availableContent.constEnd(); contentIt != contentEnd; ++contentIt) {
QSet<int> &target = to.availableContent[contentIt.key()];
const qsizetype before = target.size();
target.unite(contentIt.value());
if (target.size() > before)
changed = true;
}
for (const auto &[index, registerState] : from.registers.asKeyValueRange()) {
RegisterState &target = to.registers[index];
for (const auto &[writeOffset, conversions] : registerState.asKeyValueRange()) {
const auto existing = target.find(writeOffset);
if (existing == target.end()) {
target.insert(writeOffset, conversions);
changed = true;
continue;
}
const qsizetype before = existing.value().size();
existing.value().unite(conversions);
if (existing.value().size() > before)
changed = true;
}
}
return changed;
}
void QQmlJSOptimizations::populateReaderLocationsReadersAndConversions()
{
QHash<int, BlockState> entryState; // block start -> state at block entry
std::vector<int> pending;
pending.reserve(m_basicBlocks.size());
for (const auto &[blockStart, block] : m_basicBlocks)
pending.push_back(blockStart);
while (!pending.empty()) {
const int blockStart = pending.back();
pending.pop_back();
const auto blockIt = m_basicBlocks.find(blockStart);
auto nextBlockIt = blockIt;
++nextBlockIt;
BlockState state = entryState.value(blockStart);
auto instrIt = m_annotations.find(blockStart);
const auto blockEnd = (nextBlockIt == m_basicBlocks.end())
? m_annotations.end()
: m_annotations.find(nextBlockIt->first);
for (; instrIt != blockEnd; ++instrIt) {
const int key = instrIt.key();
if (!instrIt->second.isRename) {
for (const auto &read : instrIt->second.readRegisters.values()) {
const QQmlJSRegisterContent &content = read.content;
const auto recordRead = [&](const QQmlJSRegisterContent &r) {
const auto found = state.availableContent.constFind(r);
if (found != state.availableContent.constEnd()) {
for (int writerKey : found.value())
m_readerLocations[writerKey].typeReaders[key] = content;
}
};
if (content.isConversion()) {
Q_ASSERT(content.conversionResultType());
for (QQmlJSRegisterContent origin : content.conversionOrigins())
recordRead(origin);
} else {
recordRead(content);
}
}
}
for (const int convRegister : instrIt->second.typeConversions.keys()) {
const auto tracked = state.registers.find(convRegister);
if (tracked != state.registers.end()) {
for (auto writerIt = tracked.value().begin(), writerEnd = tracked.value().end();
writerIt != writerEnd; ++writerIt) {
writerIt.value().insert(key);
}
}
}
for (const int readRegister : instrIt->second.readRegisters.keys()) {
const auto tracked = state.registers.constFind(readRegister);
if (tracked != state.registers.constEnd()) {
for (const auto &[writerKey, value] : tracked.value().asKeyValueRange())
m_readerLocations[writerKey].registerReadersAndConversions[key] = value;
}
}
// Record this instruction's write, once done reading above.
if (instrIt->second.changedRegisterIndex != InvalidRegister) {
const auto access = m_readerLocations.constFind(key);
if (access != m_readerLocations.constEnd()) {
for (const QQmlJSRegisterContent &tracked : std::as_const(access->trackedTypes))
state.availableContent[tracked].insert(key);
}
// A write unconditionally shadows whatever reached this register before it
RegisterState fresh;
fresh.insert(key, Conversions{});
state.registers[instrIt->second.changedRegisterIndex] = std::move(fresh);
}
}
auto scheduleSuccessor = [&](int successorStart) {
if (mergeBlockState(entryState[successorStart], state))
pending.push_back(successorStart);
};
if (!blockIt->second.jumpIsUnconditional && nextBlockIt != m_basicBlocks.end())
scheduleSuccessor(nextBlockIt->first);
const int jumpTarget = blockIt->second.jumpTarget;
if (jumpTarget != -1)
scheduleSuccessor(jumpTarget);
}
}
bool QQmlJSOptimizations::eraseDeadStore(const InstructionAnnotations::iterator &it,
bool &erasedReaders)
{
auto reader = m_readerLocations.find(it.key());
if (reader != m_readerLocations.end()
&& (reader->typeReaders.isEmpty() || reader->registerReadersAndConversions.isEmpty())) {
if (it->second.isRename) {
// If it's a rename, it doesn't "own" its output type. The type may
// still be read elsewhere, even if this register isn't. However, we're
// not interested in the variant or any other details of the register.
// Therefore just delete it.
it->second.changedRegisterIndex = InvalidRegister;
it->second.changedRegister = QQmlJSRegisterContent();
} else {
// We can't do this with certain QObjects because they still need tracking as
// implicitly destructible by the garbage collector. We may be calling a factory
// function and then forgetting the object after all.
//
// However, objects we need to track that way can only be produced through external
// side effects (i.e. function calls).
const QQmlJSScope::ConstPtr contained = it->second.changedRegister.containedType();
if (!it->second.hasExternalSideEffects
|| (!contained->isReferenceType()
&& !m_typeResolver->canHold(contained, m_typeResolver->qObjectType()))) {
// void the output, rather than deleting it. We still need its variant.
const bool adjusted = m_typeResolver->adjustTrackedType(
it->second.changedRegister, m_typeResolver->voidType());
Q_ASSERT(adjusted); // Can always convert to void
}
}
m_readerLocations.erase(reader);
// If it's not a label and has no side effects, we can drop the instruction.
if (!it->second.hasInternalSideEffects) {
if (!it->second.readRegisters.isEmpty()) {
it->second.readRegisters.clear();
erasedReaders = true;
}
if (m_basicBlocks.find(it.key()) == m_basicBlocks.end())
return true;
}
}
return false;
}
void QQmlJSOptimizations::removeDeadStoresUntilStable()
{
using NewInstructionAnnotations = NewFlatMap<int, InstructionAnnotation>;
NewInstructionAnnotations newAnnotations;
bool erasedReaders = true;
while (erasedReaders) {
erasedReaders = false;
for (auto it = m_annotations.begin(), end = m_annotations.end(); it != end; ++it) {
InstructionAnnotation &instruction = it->second;
// Don't touch the function prolog instructions
if (instruction.changedRegisterIndex < InvalidRegister) {
newAnnotations.appendOrdered(it);
continue;
}
removeReadsFromErasedInstructions(it);
if (!eraseDeadStore(it, erasedReaders))
newAnnotations.appendOrdered(it);
}
m_annotations = newAnnotations.take();
}
}
void QQmlJSOptimizations::removeReadsFromErasedInstructions(
const QFlatMap<int, InstructionAnnotation>::const_iterator &it)
{
auto readers = m_readerLocations.find(it.key());
if (readers == m_readerLocations.end())
return;
for (auto typeIt = readers->typeReaders.begin(); typeIt != readers->typeReaders.end();) {
if (m_annotations.contains(typeIt.key()))
++typeIt;
else
typeIt = readers->typeReaders.erase(typeIt);
}
for (auto registerIt = readers->registerReadersAndConversions.begin();
registerIt != readers->registerReadersAndConversions.end();) {
if (m_annotations.contains(registerIt.key()))
++registerIt;
else
registerIt = readers->registerReadersAndConversions.erase(registerIt);
}
}
bool QQmlJSOptimizations::canMove(int instructionOffset,
const QQmlJSOptimizations::RegisterAccess &access) const
{
if (access.typeReaders.size() != 1)
return false;
return QQmlJSBasicBlocks::constBasicBlockForInstruction(m_basicBlocks, instructionOffset)
== QQmlJSBasicBlocks::constBasicBlockForInstruction(m_basicBlocks, access.typeReaders.begin().key());
}
QList<QQmlJSCompilePass::ObjectOrArrayDefinition>
QQmlJSBasicBlocks::objectAndArrayDefinitions() const
{
return m_objectAndArrayDefinitions;
}
static QString adjustErrorMessage(
QQmlJSRegisterContent origin, const QQmlJSScope::ConstPtr &conversion) {
return QLatin1String("Cannot convert from ")
+ origin.containedType()->internalName() + QLatin1String(" to ")
+ conversion->internalName();
}
static QString adjustErrorMessage(
QQmlJSRegisterContent origin, QQmlJSRegisterContent conversion) {
return adjustErrorMessage(origin, conversion.containedType());
}
static QString adjustErrorMessage(
QQmlJSRegisterContent origin, const QList<QQmlJSRegisterContent> &conversions) {
if (conversions.size() == 1)
return adjustErrorMessage(origin, conversions[0]);
QString types;
for (QQmlJSRegisterContent type : conversions) {
if (!types.isEmpty())
types += QLatin1String(", ");
types += type.containedType()->internalName();
}
return QLatin1String("Cannot convert from ")
+ origin.containedType()->internalName() + QLatin1String(" to union of ") + types;
}
void QQmlJSOptimizations::adjustTypes()
{
using NewVirtualRegisters = NewFlatMap<int, VirtualRegister>;
QHash<int, QList<int>> liveConversions;
QHash<int, QList<int>> movableReads;
const auto handleRegisterReadersAndConversions
= [&](QHash<int, RegisterAccess>::const_iterator it) {
for (auto conversions = it->registerReadersAndConversions.constBegin(),
end = it->registerReadersAndConversions.constEnd(); conversions != end;
++conversions) {
if (conversions->isEmpty() && canMove(it.key(), it.value()))
movableReads[conversions.key()].append(it->trackedRegister);
for (int conversion : *conversions)
liveConversions[conversion].append(it->trackedRegister);
}
};
// Handle the array definitions first.
// Changing the array type changes the expected element types.
auto adjustArray = [&](int instructionOffset, int mode) {
auto it = m_readerLocations.constFind(instructionOffset);
if (it == m_readerLocations.cend())
return;
const InstructionAnnotation &annotation = m_annotations[instructionOffset];
if (annotation.readRegisters.isEmpty())
return;
Q_ASSERT(it->trackedTypes.size() == 1);
Q_ASSERT(it->trackedTypes[0] == annotation.changedRegister);
if (it->trackedTypes[0].containedType()->accessSemantics()
!= QQmlJSScope::AccessSemantics::Sequence) {
return; // Constructed something else.
}
if (!m_typeResolver->adjustTrackedType(it->trackedTypes[0], it->typeReaders.values()))
addError(adjustErrorMessage(it->trackedTypes[0], it->typeReaders.values()));
// Now we don't adjust the type we store, but rather the type we expect to read. We
// can do this because we've tracked the read type when we defined the array in
// QQmlJSTypePropagator.
if (const QQmlJSScope::ConstPtr elementType
= it->trackedTypes[0].containedType()->elementType()) {
const auto adjust = [&](const auto it) {
const QQmlJSRegisterContent content = it.value().content;
const QQmlJSScope::ConstPtr contained = content.containedType();
if (!m_typeResolver->adjustTrackedType(content, elementType)) {
addError(adjustErrorMessage(content, elementType));
return false;
}
return true;
};
const auto &readRegisters = annotation.readRegisters;
if (mode == ObjectOrArrayDefinition::ArrayConstruct1ArgId) {
Q_ASSERT(readRegisters.size() == 1);
const auto it = readRegisters.cbegin();
if (it.value().content.containedType() != m_typeResolver->realType())
adjust(it);
} else {
for (auto it = readRegisters.cbegin(); it != readRegisters.cend(); ++it) {
if (!adjust(it))
break;
}
}
}
handleRegisterReadersAndConversions(it);
m_readerLocations.erase(it);
};
// Handle the object definitions.
// Changing the object type changes the expected property types.
const auto adjustObject = [&](const ObjectOrArrayDefinition &object) {
auto it = m_readerLocations.find(object.instructionOffset);
if (it == m_readerLocations.end())
return;
const InstructionAnnotation &annotation = m_annotations[object.instructionOffset];
Q_ASSERT(it->trackedTypes.size() == 1);
const QQmlJSRegisterContent resultType = it->trackedTypes[0];
Q_ASSERT(resultType == annotation.changedRegister);
Q_ASSERT(!annotation.readRegisters.isEmpty());
if (!m_typeResolver->adjustTrackedType(resultType, it->typeReaders.values()))
addError(adjustErrorMessage(resultType, it->typeReaders.values()));
m_readerLocations.erase(it);
if (resultType.contains(m_typeResolver->varType())
|| resultType.contains(m_typeResolver->variantMapType())
|| resultType.contains(m_typeResolver->jsValueType())) {
// It's all variant anyway
return;
}
const int classSize = m_jsUnitGenerator->jsClassSize(object.internalClassId);
Q_ASSERT(object.argc >= classSize);
for (int i = 0; i < classSize; ++i) {
// Now we don't adjust the type we store, but rather the types we expect to read. We
// can do this because we've tracked the read types when we defined the object in
// QQmlJSTypePropagator.
const QString propName = m_jsUnitGenerator->jsClassMember(object.internalClassId, i);
const QQmlJSMetaProperty property = resultType.containedType()->property(propName);
if (!property.isValid()) {
addError(resultType.containedType()->internalName()
+ QLatin1String(" has no property called ") + propName);
continue;
}
const QQmlJSScope::ConstPtr propType = property.type();
if (propType.isNull()) {
addError(QLatin1String("Cannot resolve type of property ") + propName);
continue;
}
const QQmlJSRegisterContent content = annotation.readRegisters[object.argv + i].content;
if (!m_typeResolver->adjustTrackedType(content, propType))
addError(adjustErrorMessage(content, propType));
}
// The others cannot be adjusted. We don't know their names, yet.
// But we might still be able to use the variants.
};
// Iterate in reverse so that we can have nested lists and objects and the types are propagated
// from the outer lists/objects to the inner ones.
for (auto it = m_objectAndArrayDefinitions.crbegin(), end = m_objectAndArrayDefinitions.crend();
it != end; ++it) {
switch (it->internalClassId) {
case ObjectOrArrayDefinition::ArrayClassId:
case ObjectOrArrayDefinition::ArrayConstruct1ArgId:
adjustArray(it->instructionOffset, it->internalClassId);
break;
default:
adjustObject(*it);
break;
}
}
for (auto it = m_readerLocations.cbegin(), end = m_readerLocations.cend(); it != end; ++it) {
handleRegisterReadersAndConversions(it);
// There is always one first occurrence of any tracked type. Conversions don't change
// the type.
if (it->trackedTypes.size() != 1)
continue;
// Don't adjust renamed values. We only adjust the originals.
const int writeLocation = it.key();
if (writeLocation >= 0 && m_annotations[writeLocation].isRename)
continue;
if (!m_typeResolver->adjustTrackedType(it->trackedTypes[0], it->typeReaders.values()))
addError(adjustErrorMessage(it->trackedTypes[0], it->typeReaders.values()));
}
NewVirtualRegisters newRegisters;
for (auto i = m_annotations.begin(), iEnd = m_annotations.end(); i != iEnd; ++i) {
for (auto conversion = i->second.typeConversions.begin(),
conversionEnd = i->second.typeConversions.end(); conversion != conversionEnd;
++conversion) {
if (!liveConversions[i.key()].contains(conversion.key()))
continue;
QQmlJSScope::ConstPtr newResult;
const auto content = conversion->second.content;
if (content.isConversion() && !content.original().isValid()) {
const auto &conversionOrigins = content.conversionOrigins();
for (const auto &origin : conversionOrigins)
newResult = m_typeResolver->merge(newResult, origin.containedType());
if (!m_typeResolver->adjustTrackedType(content, newResult))
addError(adjustErrorMessage(content, newResult));
}
newRegisters.appendOrdered(conversion);
}
i->second.typeConversions = newRegisters.take();
for (int movable : std::as_const(movableReads[i.key()]))
i->second.readRegisters[movable].canMove = true;
}
}
void QQmlJSOptimizations::populateBasicBlocks()
{
for (auto blockNext = m_basicBlocks.begin(), blockEnd = m_basicBlocks.end();
blockNext != blockEnd;) {
const auto blockIt = blockNext++;
BasicBlock &block = blockIt->second;
QList<QQmlJSScope::ConstPtr> writtenTypes;
QList<int> 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) {
if (!writtenRegisters.contains(it->first))
block.readRegisters.append(it->first);
}
// If it's just a renaming, the type has existed in a different register before.
if (instruction.changedRegisterIndex != InvalidRegister) {
if (!instruction.isRename)
writtenTypes.append(instruction.changedRegister.containedType());
writtenRegisters.append(instruction.changedRegisterIndex);
}
}
QQmlJSUtils::deduplicate(block.readRegisters);
}
}
QT_END_NAMESPACE