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

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