1// Copyright (C) 2024 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
3
4#include "qqmljsoptimizations_p.h"
5#include "qqmljsbasicblocks_p.h"
6#include "qqmljsutils_p.h"
7
8QT_BEGIN_NAMESPACE
9
10using namespace Qt::Literals::StringLiterals;
11
12QQmlJSCompilePass::BlocksAndAnnotations QQmlJSOptimizations::run(const Function *function)
13{
14 m_function = function;
15
16 populateBasicBlocks();
17 populateReaderLocations();
18 removeDeadStoresUntilStable();
19 adjustTypes();
20
21 return { .basicBlocks: std::move(m_basicBlocks), .annotations: std::move(m_annotations) };
22}
23
24struct PendingBlock
25{
26 QQmlJSOptimizations::Conversions conversions;
27 int start = -1;
28 bool registerActive = false;
29};
30
31template<typename ContainerA, typename ContainerB>
32static bool containsAny(const ContainerA &container, const ContainerB &elements)
33{
34 for (const auto &element : elements) {
35 if (container.contains(element))
36 return true;
37 }
38 return false;
39}
40
41template<class Key, class T, class Compare = std::less<Key>,
42 class KeyContainer = QList<Key>, class MappedContainer = QList<T>>
43class NewFlatMap
44{
45public:
46 using OriginalFlatMap = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>;
47
48 void appendOrdered(const typename OriginalFlatMap::iterator &i)
49 {
50 keys.append(i.key());
51 values.append(i.value());
52 }
53
54 OriginalFlatMap take()
55 {
56 OriginalFlatMap result(Qt::OrderedUniqueRange, std::move(keys), std::move(values));
57 keys.clear();
58 values.clear();
59 return result;
60 }
61
62private:
63 typename OriginalFlatMap::key_container_type keys;
64 typename OriginalFlatMap::mapped_container_type values;
65};
66
67void QQmlJSOptimizations::populateReaderLocations()
68{
69 for (auto writeIt = m_annotations.begin(), writeEnd = m_annotations.end();
70 writeIt != writeEnd; ++writeIt) {
71 const int writtenRegister = writeIt->second.changedRegisterIndex;
72
73 // Instructions that don't write can't be dead stores, no need to populate reader locations
74 if (writtenRegister == InvalidRegister)
75 continue;
76
77 RegisterAccess &access = m_readerLocations[writeIt.key()];
78 access.trackedRegister = writtenRegister;
79 if (writeIt->second.changedRegister.isConversion()) {
80 // If it's a conversion, we have to check for all readers of the conversion origins.
81 // This happens at jump targets where different types are merged. A StoreReg or similar
82 // instruction must be optimized out if none of the types it can hold is read anymore.
83 access.trackedTypes.clear();
84 const auto origins = writeIt->second.changedRegister.conversionOrigins();
85 for (QQmlJSRegisterContent origin : origins)
86 access.trackedTypes.append(t: origin);
87 } else {
88 access.trackedTypes.append(t: writeIt->second.changedRegister);
89 Q_ASSERT(!access.trackedTypes.last().isNull());
90 }
91
92 auto blockIt = QQmlJSBasicBlocks::basicBlockForInstruction(container&: m_basicBlocks, instructionOffset: writeIt.key());
93 QList<PendingBlock> blocks = { { .conversions: {}, .start: blockIt->first, .registerActive: true } };
94 QHash<int, PendingBlock> processedBlocks;
95 bool isFirstBlock = true;
96
97 while (!blocks.isEmpty()) {
98 const PendingBlock block = blocks.takeLast();
99
100 // We can re-enter the first block from the beginning.
101 // We will then find any reads before the write we're currently examining.
102 if (!isFirstBlock)
103 processedBlocks.insert(key: block.start, value: block);
104
105 auto nextBlock = m_basicBlocks.find(key: block.start);
106 auto currentBlock = nextBlock++;
107 bool registerActive = block.registerActive;
108 Conversions conversions = block.conversions;
109
110 const auto blockEnd = (nextBlock == m_basicBlocks.end())
111 ? m_annotations.end()
112 : m_annotations.find(key: nextBlock->first);
113
114 auto blockInstr = isFirstBlock
115 ? (writeIt + 1)
116 : m_annotations.find(key: currentBlock->first);
117 for (; blockInstr != blockEnd; ++blockInstr) {
118 if (registerActive
119 && blockInstr->second.typeConversions.contains(key: writtenRegister)) {
120 conversions.insert(value: blockInstr.key());
121 }
122
123 for (auto readIt = blockInstr->second.readRegisters.constBegin(),
124 end = blockInstr->second.readRegisters.constEnd();
125 readIt != end; ++readIt) {
126 if (blockInstr->second.isRename) {
127 // Nothing to do
128 } else if (readIt->second.content.isConversion()) {
129 const QList<QQmlJSRegisterContent> conversionOrigins
130 = readIt->second.content.conversionOrigins();
131 for (QQmlJSRegisterContent origin : conversionOrigins) {
132 if (!access.trackedTypes.contains(t: origin))
133 continue;
134
135 Q_ASSERT(readIt->second.content.conversionResultType());
136 access.typeReaders[blockInstr.key()] = readIt->second.content;
137 break;
138 }
139 } else if (access.trackedTypes.contains(t: readIt->second.content)) {
140 // We've used the original content instead of converting it
141 access.typeReaders[blockInstr.key()] = readIt->second.content;
142 }
143 if (registerActive && readIt->first == writtenRegister)
144 access.registerReadersAndConversions[blockInstr.key()] = conversions;
145 }
146
147 if (blockInstr->second.changedRegisterIndex == writtenRegister) {
148 conversions.clear();
149 registerActive = false;
150 }
151 }
152
153 auto scheduleBlock = [&](int blockStart) {
154 // If we find that an already processed block has the register activated by this jump,
155 // we need to re-evaluate it. We also need to propagate any newly found conversions.
156 const auto processed = processedBlocks.find(key: blockStart);
157 if (processed == processedBlocks.end()) {
158 blocks.append(t: {.conversions: conversions, .start: blockStart, .registerActive: registerActive});
159 } else if (registerActive && !processed->registerActive) {
160 blocks.append(t: {.conversions: conversions, .start: blockStart, .registerActive: registerActive});
161 } else {
162 Conversions merged = processed->conversions;
163 merged.unite(other: conversions);
164
165 if (merged.size() > processed->conversions.size())
166 blocks.append(t: {.conversions: std::move(merged), .start: blockStart, .registerActive: registerActive});
167 }
168 };
169
170 if (!currentBlock->second.jumpIsUnconditional && nextBlock != m_basicBlocks.end())
171 scheduleBlock(nextBlock->first);
172
173 const int jumpTarget = currentBlock->second.jumpTarget;
174 if (jumpTarget != -1)
175 scheduleBlock(jumpTarget);
176
177 if (isFirstBlock)
178 isFirstBlock = false;
179 }
180 }
181}
182
183bool QQmlJSOptimizations::eraseDeadStore(const InstructionAnnotations::iterator &it,
184 bool &erasedReaders)
185{
186 auto reader = m_readerLocations.find(key: it.key());
187 if (reader != m_readerLocations.end()
188 && (reader->typeReaders.isEmpty() || reader->registerReadersAndConversions.isEmpty())) {
189
190 if (it->second.isRename) {
191 // If it's a rename, it doesn't "own" its output type. The type may
192 // still be read elsewhere, even if this register isn't. However, we're
193 // not interested in the variant or any other details of the register.
194 // Therefore just delete it.
195 it->second.changedRegisterIndex = InvalidRegister;
196 it->second.changedRegister = QQmlJSRegisterContent();
197 } else {
198 // We can't do this with certain QObjects because they still need tracking as
199 // implicitly destructible by the garbage collector. We may be calling a factory
200 // function and then forgetting the object after all.
201 //
202 // However, objects we need to track that way can only be produced through external
203 // side effects (i.e. function calls).
204
205 const QQmlJSScope::ConstPtr contained = it->second.changedRegister.containedType();
206 if (!it->second.hasExternalSideEffects
207 || (!contained->isReferenceType()
208 && !m_typeResolver->canHold(container: contained, contained: m_typeResolver->qObjectType()))) {
209 // void the output, rather than deleting it. We still need its variant.
210 const bool adjusted = m_typeResolver->adjustTrackedType(
211 tracked: it->second.changedRegister, conversion: m_typeResolver->voidType());
212 Q_ASSERT(adjusted); // Can always convert to void
213 }
214 }
215 m_readerLocations.erase(it: reader);
216
217 // If it's not a label and has no side effects, we can drop the instruction.
218 if (!it->second.hasInternalSideEffects) {
219 if (!it->second.readRegisters.isEmpty()) {
220 it->second.readRegisters.clear();
221 erasedReaders = true;
222 }
223 if (m_basicBlocks.find(key: it.key()) == m_basicBlocks.end())
224 return true;
225 }
226 }
227 return false;
228}
229
230void QQmlJSOptimizations::removeDeadStoresUntilStable()
231{
232 using NewInstructionAnnotations = NewFlatMap<int, InstructionAnnotation>;
233 NewInstructionAnnotations newAnnotations;
234
235 bool erasedReaders = true;
236 while (erasedReaders) {
237 erasedReaders = false;
238
239 for (auto it = m_annotations.begin(), end = m_annotations.end(); it != end; ++it) {
240 InstructionAnnotation &instruction = it->second;
241
242 // Don't touch the function prolog instructions
243 if (instruction.changedRegisterIndex < InvalidRegister) {
244 newAnnotations.appendOrdered(i: it);
245 continue;
246 }
247
248 removeReadsFromErasedInstructions(it);
249
250 if (!eraseDeadStore(it, erasedReaders))
251 newAnnotations.appendOrdered(i: it);
252 }
253
254 m_annotations = newAnnotations.take();
255 }
256}
257
258void QQmlJSOptimizations::removeReadsFromErasedInstructions(
259 const QFlatMap<int, InstructionAnnotation>::const_iterator &it)
260{
261 auto readers = m_readerLocations.find(key: it.key());
262 if (readers == m_readerLocations.end())
263 return;
264
265 for (auto typeIt = readers->typeReaders.begin(); typeIt != readers->typeReaders.end();) {
266 if (m_annotations.contains(key: typeIt.key()))
267 ++typeIt;
268 else
269 typeIt = readers->typeReaders.erase(it: typeIt);
270 }
271
272 for (auto registerIt = readers->registerReadersAndConversions.begin();
273 registerIt != readers->registerReadersAndConversions.end();) {
274 if (m_annotations.contains(key: registerIt.key()))
275 ++registerIt;
276 else
277 registerIt = readers->registerReadersAndConversions.erase(it: registerIt);
278 }
279}
280
281bool QQmlJSOptimizations::canMove(int instructionOffset,
282 const QQmlJSOptimizations::RegisterAccess &access) const
283{
284 if (access.typeReaders.size() != 1)
285 return false;
286 return QQmlJSBasicBlocks::basicBlockForInstruction(container: m_basicBlocks, instructionOffset)
287 == QQmlJSBasicBlocks::basicBlockForInstruction(container: m_basicBlocks, instructionOffset: access.typeReaders.begin().key());
288}
289
290QList<QQmlJSCompilePass::ObjectOrArrayDefinition>
291QQmlJSBasicBlocks::objectAndArrayDefinitions() const
292{
293 return m_objectAndArrayDefinitions;
294}
295
296static QString adjustErrorMessage(
297 QQmlJSRegisterContent origin, const QQmlJSScope::ConstPtr &conversion) {
298 return QLatin1String("Cannot convert from ")
299 + origin.containedType()->internalName() + QLatin1String(" to ")
300 + conversion->internalName();
301}
302
303static QString adjustErrorMessage(
304 QQmlJSRegisterContent origin, QQmlJSRegisterContent conversion) {
305 return adjustErrorMessage(origin, conversion: conversion.containedType());
306}
307
308static QString adjustErrorMessage(
309 QQmlJSRegisterContent origin, const QList<QQmlJSRegisterContent> &conversions) {
310 if (conversions.size() == 1)
311 return adjustErrorMessage(origin, conversion: conversions[0]);
312
313 QString types;
314 for (QQmlJSRegisterContent type : conversions) {
315 if (!types.isEmpty())
316 types += QLatin1String(", ");
317 types += type.containedType()->internalName();
318 }
319 return QLatin1String("Cannot convert from ")
320 + origin.containedType()->internalName() + QLatin1String(" to union of ") + types;
321}
322
323void QQmlJSOptimizations::adjustTypes()
324{
325 using NewVirtualRegisters = NewFlatMap<int, VirtualRegister>;
326
327 QHash<int, QList<int>> liveConversions;
328 QHash<int, QList<int>> movableReads;
329
330 const auto handleRegisterReadersAndConversions
331 = [&](QHash<int, RegisterAccess>::const_iterator it) {
332 for (auto conversions = it->registerReadersAndConversions.constBegin(),
333 end = it->registerReadersAndConversions.constEnd(); conversions != end;
334 ++conversions) {
335 if (conversions->isEmpty() && canMove(instructionOffset: it.key(), access: it.value()))
336 movableReads[conversions.key()].append(t: it->trackedRegister);
337 for (int conversion : *conversions)
338 liveConversions[conversion].append(t: it->trackedRegister);
339 }
340 };
341
342 // Handle the array definitions first.
343 // Changing the array type changes the expected element types.
344 auto adjustArray = [&](int instructionOffset, int mode) {
345 auto it = m_readerLocations.constFind(key: instructionOffset);
346 if (it == m_readerLocations.cend())
347 return;
348
349 const InstructionAnnotation &annotation = m_annotations[instructionOffset];
350 if (annotation.readRegisters.isEmpty())
351 return;
352
353 Q_ASSERT(it->trackedTypes.size() == 1);
354 Q_ASSERT(it->trackedTypes[0] == annotation.changedRegister);
355
356 if (it->trackedTypes[0].containedType()->accessSemantics()
357 != QQmlJSScope::AccessSemantics::Sequence) {
358 return; // Constructed something else.
359 }
360
361 if (!m_typeResolver->adjustTrackedType(tracked: it->trackedTypes[0], conversions: it->typeReaders.values()))
362 addError(message: adjustErrorMessage(origin: it->trackedTypes[0], conversions: it->typeReaders.values()));
363
364 // Now we don't adjust the type we store, but rather the type we expect to read. We
365 // can do this because we've tracked the read type when we defined the array in
366 // QQmlJSTypePropagator.
367 if (QQmlJSScope::ConstPtr valueType = it->trackedTypes[0].containedType()->valueType()) {
368 const QQmlJSRegisterContent content = annotation.readRegisters.begin().value().content;
369 const QQmlJSScope::ConstPtr contained = content.containedType();
370
371 // If it's the 1-arg Array ctor, and the argument is a number, that's special.
372 if (mode != ObjectOrArrayDefinition::ArrayConstruct1ArgId
373 || contained != m_typeResolver->realType()) {
374 if (!m_typeResolver->adjustTrackedType(tracked: content, conversion: valueType))
375 addError(message: adjustErrorMessage(origin: content, conversion: valueType));
376 }
377 }
378
379 handleRegisterReadersAndConversions(it);
380 m_readerLocations.erase(it);
381 };
382
383 // Handle the object definitions.
384 // Changing the object type changes the expected property types.
385 const auto adjustObject = [&](const ObjectOrArrayDefinition &object) {
386 auto it = m_readerLocations.find(key: object.instructionOffset);
387 if (it == m_readerLocations.end())
388 return;
389
390 const InstructionAnnotation &annotation = m_annotations[object.instructionOffset];
391
392 Q_ASSERT(it->trackedTypes.size() == 1);
393 const QQmlJSRegisterContent resultType = it->trackedTypes[0];
394
395 Q_ASSERT(resultType == annotation.changedRegister);
396 Q_ASSERT(!annotation.readRegisters.isEmpty());
397
398 if (!m_typeResolver->adjustTrackedType(tracked: resultType, conversions: it->typeReaders.values()))
399 addError(message: adjustErrorMessage(origin: resultType, conversions: it->typeReaders.values()));
400
401 m_readerLocations.erase(it);
402
403 if (resultType.contains(type: m_typeResolver->varType())
404 || resultType.contains(type: m_typeResolver->variantMapType())
405 || resultType.contains(type: m_typeResolver->jsValueType())) {
406 // It's all variant anyway
407 return;
408 }
409
410 const int classSize = m_jsUnitGenerator->jsClassSize(jsClassId: object.internalClassId);
411 Q_ASSERT(object.argc >= classSize);
412
413 for (int i = 0; i < classSize; ++i) {
414 // Now we don't adjust the type we store, but rather the types we expect to read. We
415 // can do this because we've tracked the read types when we defined the object in
416 // QQmlJSTypePropagator.
417
418 const QString propName = m_jsUnitGenerator->jsClassMember(jsClassId: object.internalClassId, member: i);
419 const QQmlJSMetaProperty property = resultType.containedType()->property(name: propName);
420 if (!property.isValid()) {
421 addError(message: resultType.containedType()->internalName()
422 + QLatin1String(" has no property called ") + propName);
423 continue;
424 }
425 const QQmlJSScope::ConstPtr propType = property.type();
426 if (propType.isNull()) {
427 addError(message: QLatin1String("Cannot resolve type of property ") + propName);
428 continue;
429 }
430 const QQmlJSRegisterContent content = annotation.readRegisters[object.argv + i].content;
431 if (!m_typeResolver->adjustTrackedType(tracked: content, conversion: propType))
432 addError(message: adjustErrorMessage(origin: content, conversion: propType));
433 }
434
435 // The others cannot be adjusted. We don't know their names, yet.
436 // But we might still be able to use the variants.
437 };
438
439 // Iterate in reverse so that we can have nested lists and objects and the types are propagated
440 // from the outer lists/objects to the inner ones.
441 for (auto it = m_objectAndArrayDefinitions.crbegin(), end = m_objectAndArrayDefinitions.crend();
442 it != end; ++it) {
443 switch (it->internalClassId) {
444 case ObjectOrArrayDefinition::ArrayClassId:
445 case ObjectOrArrayDefinition::ArrayConstruct1ArgId:
446 adjustArray(it->instructionOffset, it->internalClassId);
447 break;
448 default:
449 adjustObject(*it);
450 break;
451 }
452 }
453
454 for (auto it = m_readerLocations.cbegin(), end = m_readerLocations.cend(); it != end; ++it) {
455 handleRegisterReadersAndConversions(it);
456
457 // There is always one first occurrence of any tracked type. Conversions don't change
458 // the type.
459 if (it->trackedTypes.size() != 1)
460 continue;
461
462 // Don't adjust renamed values. We only adjust the originals.
463 const int writeLocation = it.key();
464 if (writeLocation >= 0 && m_annotations[writeLocation].isRename)
465 continue;
466
467 if (!m_typeResolver->adjustTrackedType(tracked: it->trackedTypes[0], conversions: it->typeReaders.values()))
468 addError(message: adjustErrorMessage(origin: it->trackedTypes[0], conversions: it->typeReaders.values()));
469 }
470
471
472 NewVirtualRegisters newRegisters;
473 for (auto i = m_annotations.begin(), iEnd = m_annotations.end(); i != iEnd; ++i) {
474 for (auto conversion = i->second.typeConversions.begin(),
475 conversionEnd = i->second.typeConversions.end(); conversion != conversionEnd;
476 ++conversion) {
477 if (!liveConversions[i.key()].contains(t: conversion.key()))
478 continue;
479
480 QQmlJSScope::ConstPtr newResult;
481 const auto content = conversion->second.content;
482 if (content.isConversion()) {
483 const auto conversionOrigins = content.conversionOrigins();
484 for (const auto &origin : conversionOrigins)
485 newResult = m_typeResolver->merge(a: newResult, b: origin.containedType());
486 if (!m_typeResolver->adjustTrackedType(tracked: content, conversion: newResult))
487 addError(message: adjustErrorMessage(origin: content, conversion: newResult));
488 }
489 newRegisters.appendOrdered(i: conversion);
490 }
491 i->second.typeConversions = newRegisters.take();
492
493 for (int movable : std::as_const(t&: movableReads[i.key()]))
494 i->second.readRegisters[movable].canMove = true;
495 }
496}
497
498void QQmlJSOptimizations::populateBasicBlocks()
499{
500 for (auto blockNext = m_basicBlocks.begin(), blockEnd = m_basicBlocks.end();
501 blockNext != blockEnd;) {
502
503 const auto blockIt = blockNext++;
504 BasicBlock &block = blockIt->second;
505 QList<QQmlJSScope::ConstPtr> writtenTypes;
506 QList<int> writtenRegisters;
507
508 const auto instrEnd = (blockNext == blockEnd) ? m_annotations.end()
509 : m_annotations.find(key: blockNext->first);
510 for (auto instrIt = m_annotations.find(key: blockIt->first); instrIt != instrEnd; ++instrIt) {
511 const InstructionAnnotation &instruction = instrIt->second;
512 for (auto it = instruction.readRegisters.begin(), end = instruction.readRegisters.end();
513 it != end; ++it) {
514 if (!writtenRegisters.contains(t: it->first))
515 block.readRegisters.append(t: it->first);
516 }
517
518 // If it's just a renaming, the type has existed in a different register before.
519 if (instruction.changedRegisterIndex != InvalidRegister) {
520 if (!instruction.isRename)
521 writtenTypes.append(t: instruction.changedRegister.containedType());
522 writtenRegisters.append(t: instruction.changedRegisterIndex);
523 }
524 }
525
526 QQmlJSUtils::deduplicate(container&: block.readRegisters);
527 }
528}
529
530
531QT_END_NAMESPACE
532

source code of qtdeclarative/src/qmlcompiler/qqmljsoptimizations.cpp