1// Copyright (C) 2022 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 "qqmljsbasicblocks_p.h"
5
6QT_BEGIN_NAMESPACE
7
8template<typename Container>
9void deduplicate(Container &container)
10{
11 std::sort(container.begin(), container.end());
12 auto erase = std::unique(container.begin(), container.end());
13 container.erase(erase, container.end());
14}
15
16QQmlJSCompilePass::InstructionAnnotations QQmlJSBasicBlocks::run(
17 const Function *function,
18 const InstructionAnnotations &annotations,
19 QQmlJS::DiagnosticMessage *error)
20{
21 m_function = function;
22 m_annotations = annotations;
23 m_error = error;
24
25 for (int i = 0, end = function->argumentTypes.size(); i != end; ++i) {
26 InstructionAnnotation annotation;
27 annotation.changedRegisterIndex = FirstArgument + i;
28 annotation.changedRegister = function->argumentTypes[i];
29 m_annotations[-annotation.changedRegisterIndex] = annotation;
30 }
31
32 for (int i = 0, end = function->registerTypes.size(); i != end; ++i) {
33 InstructionAnnotation annotation;
34 annotation.changedRegisterIndex = firstRegisterIndex() + i;
35 annotation.changedRegister = function->registerTypes[i];
36 m_annotations[-annotation.changedRegisterIndex] = annotation;
37 }
38
39 m_basicBlocks.insert_or_assign(key: m_annotations.begin().key(), obj: BasicBlock());
40
41 const QByteArray byteCode = function->code;
42 decode(code: byteCode.constData(), len: static_cast<uint>(byteCode.size()));
43 if (m_hadBackJumps) {
44 // We may have missed some connections between basic blocks if there were back jumps.
45 // Fill them in via a second pass.
46
47 // We also need to re-calculate the jump targets then because the basic block boundaries
48 // may have shifted.
49 for (auto it = m_basicBlocks.begin(), end = m_basicBlocks.end(); it != end; ++it) {
50 it->second.jumpTarget = -1;
51 it->second.jumpIsUnconditional = false;
52 }
53
54 m_skipUntilNextLabel = false;
55
56 reset();
57 decode(code: byteCode.constData(), len: static_cast<uint>(byteCode.size()));
58 for (auto it = m_basicBlocks.begin(), end = m_basicBlocks.end(); it != end; ++it)
59 deduplicate(container&: it->second.jumpOrigins);
60 }
61
62 populateBasicBlocks();
63 populateReaderLocations();
64 adjustTypes();
65 return std::move(m_annotations);
66}
67
68QV4::Moth::ByteCodeHandler::Verdict QQmlJSBasicBlocks::startInstruction(QV4::Moth::Instr::Type type)
69{
70 auto it = m_basicBlocks.find(key: currentInstructionOffset());
71 if (it != m_basicBlocks.end()) {
72 m_skipUntilNextLabel = false;
73 } else if (m_skipUntilNextLabel && !instructionManipulatesContext(type)) {
74 return SkipInstruction;
75 }
76
77 return ProcessInstruction;
78}
79
80void QQmlJSBasicBlocks::endInstruction(QV4::Moth::Instr::Type)
81{
82 if (m_skipUntilNextLabel)
83 return;
84 auto it = m_basicBlocks.find(key: nextInstructionOffset());
85 if (it != m_basicBlocks.end())
86 it->second.jumpOrigins.append(t: currentInstructionOffset());
87}
88
89void QQmlJSBasicBlocks::generate_Jump(int offset)
90{
91 processJump(offset, mode: Unconditional);
92}
93
94void QQmlJSBasicBlocks::generate_JumpTrue(int offset)
95{
96 processJump(offset, mode: Conditional);
97}
98
99void QQmlJSBasicBlocks::generate_JumpFalse(int offset)
100{
101 processJump(offset, mode: Conditional);
102}
103
104void QQmlJSBasicBlocks::generate_JumpNoException(int offset)
105{
106 processJump(offset, mode: Conditional);
107}
108
109void QQmlJSBasicBlocks::generate_JumpNotUndefined(int offset)
110{
111 processJump(offset, mode: Conditional);
112}
113
114void QQmlJSBasicBlocks::generate_Ret()
115{
116 m_skipUntilNextLabel = true;
117}
118
119void QQmlJSBasicBlocks::generate_ThrowException()
120{
121 m_skipUntilNextLabel = true;
122}
123
124void QQmlJSBasicBlocks::generate_DefineArray(int argc, int)
125{
126 if (argc == 0)
127 return; // empty array/list, nothing to do
128
129 m_arrayDefinitions.append(t: currentInstructionOffset());
130}
131
132void QQmlJSBasicBlocks::processJump(int offset, JumpMode mode)
133{
134 if (offset < 0)
135 m_hadBackJumps = true;
136 const int jumpTarget = absoluteOffset(relativeOffset: offset);
137 Q_ASSERT(!m_basicBlocks.isEmpty());
138 auto currentBlock = m_basicBlocks.lower_bound(key: currentInstructionOffset());
139 if (currentBlock == m_basicBlocks.end() || currentBlock->first != currentInstructionOffset())
140 --currentBlock;
141 currentBlock->second.jumpTarget = jumpTarget;
142 currentBlock->second.jumpIsUnconditional = (mode == Unconditional);
143 m_basicBlocks[jumpTarget].jumpOrigins.append(t: currentInstructionOffset());
144 if (mode == Unconditional)
145 m_skipUntilNextLabel = true;
146 else
147 m_basicBlocks[nextInstructionOffset()].jumpOrigins.append(t: currentInstructionOffset());
148}
149
150template<typename ContainerA, typename ContainerB>
151static bool containsAny(const ContainerA &container, const ContainerB &elements)
152{
153 for (const auto &element : elements) {
154 if (container.contains(element))
155 return true;
156 }
157 return false;
158}
159
160template<typename ContainerA, typename ContainerB>
161static bool containsAll(const ContainerA &container, const ContainerB &elements)
162{
163 for (const auto &element : elements) {
164 if (!container.contains(element))
165 return false;
166 }
167 return true;
168}
169
170template<class Key, class T, class Compare = std::less<Key>,
171 class KeyContainer = QList<Key>, class MappedContainer = QList<T>>
172class NewFlatMap
173{
174public:
175 using OriginalFlatMap = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>;
176
177 void appendOrdered(const typename OriginalFlatMap::iterator &i) {
178 keys.append(i.key());
179 values.append(i.value());
180 }
181
182 OriginalFlatMap take() {
183 OriginalFlatMap result(Qt::OrderedUniqueRange, std::move(keys), std::move(values));
184 keys.clear();
185 values.clear();
186 return result;
187 }
188
189private:
190 typename OriginalFlatMap::key_container_type keys;
191 typename OriginalFlatMap::mapped_container_type values;
192};
193
194struct PendingBlock
195{
196 QList<int> conversions;
197 int start = -1;
198 bool registerActive = false;
199};
200
201void QQmlJSBasicBlocks::populateReaderLocations()
202{
203 using NewInstructionAnnotations = NewFlatMap<int, InstructionAnnotation>;
204
205 bool erasedReaders = false;
206 auto eraseDeadStore = [&](const InstructionAnnotations::iterator &it) {
207 auto reader = m_readerLocations.find(key: it.key());
208 if (reader != m_readerLocations.end()
209 && (reader->typeReaders.isEmpty()
210 || reader->registerReadersAndConversions.isEmpty())) {
211
212 if (it->second.isRename) {
213 // If it's a rename, it doesn't "own" its output type. The type may
214 // still be read elsewhere, even if this register isn't. However, we're
215 // not interested in the variant or any other details of the register.
216 // Therefore just delete it.
217 it->second.changedRegisterIndex = InvalidRegister;
218 it->second.changedRegister = QQmlJSRegisterContent();
219 } else {
220 // void the output, rather than deleting it. We still need its variant.
221 bool adjusted = m_typeResolver->adjustTrackedType(
222 tracked: it->second.changedRegister.storedType(),
223 conversion: m_typeResolver->voidType());
224 Q_ASSERT(adjusted); // Can always convert to void
225
226 adjusted = m_typeResolver->adjustTrackedType(
227 tracked: m_typeResolver->containedType(container: it->second.changedRegister),
228 conversion: m_typeResolver->voidType());
229 Q_ASSERT(adjusted); // Can always convert to void
230 }
231 m_readerLocations.erase(it: reader);
232
233 // If it's not a label and has no side effects, we can drop the instruction.
234 if (!it->second.hasSideEffects) {
235 if (!it->second.readRegisters.isEmpty()) {
236 it->second.readRegisters.clear();
237 erasedReaders = true;
238 }
239 if (m_basicBlocks.find(key: it.key()) == m_basicBlocks.end())
240 return true;
241 }
242 }
243 return false;
244 };
245
246 NewInstructionAnnotations newAnnotations;
247 for (auto writeIt = m_annotations.begin(), writeEnd = m_annotations.end();
248 writeIt != writeEnd; ++writeIt) {
249 const int writtenRegister = writeIt->second.changedRegisterIndex;
250 if (writtenRegister == InvalidRegister) {
251 newAnnotations.appendOrdered(i: writeIt);
252 continue;
253 }
254
255 RegisterAccess &access = m_readerLocations[writeIt.key()];
256 access.trackedRegister = writtenRegister;
257 if (writeIt->second.changedRegister.isConversion()) {
258 // If it's a conversion, we have to check for all readers of the conversion origins.
259 // This happens at jump targets where different types are merged. A StoreReg or similar
260 // instruction must be optimized out if none of the types it can hold is read anymore.
261 access.trackedTypes = writeIt->second.changedRegister.conversionOrigins();
262 } else {
263 access.trackedTypes.append(
264 t: m_typeResolver->trackedContainedType(container: writeIt->second.changedRegister));
265 }
266
267 auto blockIt = m_basicBlocks.lower_bound(key: writeIt.key());
268 if (blockIt == m_basicBlocks.end() || blockIt->first != writeIt.key())
269 --blockIt;
270
271 QList<PendingBlock> blocks = { { .conversions: {}, .start: blockIt->first, .registerActive: true } };
272 QHash<int, PendingBlock> processedBlocks;
273 bool isFirstBlock = true;
274
275 while (!blocks.isEmpty()) {
276 const PendingBlock block = blocks.takeLast();
277
278 // We can re-enter the first block from the beginning.
279 // We will then find any reads before the write we're currently examining.
280 if (!isFirstBlock)
281 processedBlocks.insert(key: block.start, value: block);
282
283 auto nextBlock = m_basicBlocks.find(key: block.start);
284 auto currentBlock = nextBlock++;
285 bool registerActive = block.registerActive;
286 QList<int> conversions = block.conversions;
287
288 const auto blockEnd = (nextBlock == m_basicBlocks.end())
289 ? m_annotations.end()
290 : m_annotations.find(key: nextBlock->first);
291
292 auto blockInstr = isFirstBlock
293 ? (writeIt + 1)
294 : m_annotations.find(key: currentBlock->first);
295 for (; blockInstr != blockEnd; ++blockInstr) {
296 if (registerActive
297 && blockInstr->second.typeConversions.contains(key: writtenRegister)) {
298 conversions.append(t: blockInstr.key());
299 }
300
301 for (auto readIt = blockInstr->second.readRegisters.constBegin(),
302 end = blockInstr->second.readRegisters.constEnd();
303 readIt != end; ++readIt) {
304 if (!blockInstr->second.isRename && containsAny(
305 container: readIt->second.content.conversionOrigins(), elements: access.trackedTypes)) {
306 Q_ASSERT(readIt->second.content.isConversion());
307 Q_ASSERT(readIt->second.content.conversionResult());
308 access.typeReaders[blockInstr.key()]
309 = readIt->second.content.conversionResult();
310 }
311 if (registerActive && readIt->first == writtenRegister)
312 access.registerReadersAndConversions[blockInstr.key()] = conversions;
313 }
314
315 if (blockInstr->second.changedRegisterIndex == writtenRegister) {
316 conversions.clear();
317 registerActive = false;
318 }
319 }
320
321 auto scheduleBlock = [&](int blockStart) {
322 // If we find that an already processed block has the register activated by this jump,
323 // we need to re-evaluate it. We also need to propagate any newly found conversions.
324 const auto processed = processedBlocks.find(key: blockStart);
325 if (processed == processedBlocks.end())
326 blocks.append(t: {.conversions: conversions, .start: blockStart, .registerActive: registerActive});
327 else if (registerActive && !processed->registerActive)
328 blocks.append(t: {.conversions: conversions, .start: blockStart, .registerActive: registerActive});
329 else if (!containsAll(container: processed->conversions, elements: conversions))
330 blocks.append(t: {.conversions: processed->conversions + conversions, .start: blockStart, .registerActive: registerActive});
331 };
332
333 if (!currentBlock->second.jumpIsUnconditional && nextBlock != m_basicBlocks.end())
334 scheduleBlock(nextBlock->first);
335
336 const int jumpTarget = currentBlock->second.jumpTarget;
337 if (jumpTarget != -1)
338 scheduleBlock(jumpTarget);
339
340 if (isFirstBlock)
341 isFirstBlock = false;
342 }
343
344 if (!eraseDeadStore(writeIt))
345 newAnnotations.appendOrdered(i: writeIt);
346 }
347 m_annotations = newAnnotations.take();
348
349 while (erasedReaders) {
350 erasedReaders = false;
351
352 for (auto it = m_annotations.begin(), end = m_annotations.end(); it != end; ++it) {
353 InstructionAnnotation &instruction = it->second;
354 if (instruction.changedRegisterIndex < InvalidRegister) {
355 newAnnotations.appendOrdered(i: it);
356 continue;
357 }
358
359 auto readers = m_readerLocations.find(key: it.key());
360 if (readers != m_readerLocations.end()) {
361 for (auto typeIt = readers->typeReaders.begin();
362 typeIt != readers->typeReaders.end();) {
363 if (m_annotations.contains(key: typeIt.key()))
364 ++typeIt;
365 else
366 typeIt = readers->typeReaders.erase(it: typeIt);
367 }
368
369 for (auto registerIt = readers->registerReadersAndConversions.begin();
370 registerIt != readers->registerReadersAndConversions.end();) {
371 if (m_annotations.contains(key: registerIt.key()))
372 ++registerIt;
373 else
374 registerIt = readers->registerReadersAndConversions.erase(it: registerIt);
375 }
376 }
377
378 if (!eraseDeadStore(it))
379 newAnnotations.appendOrdered(i: it);
380 }
381
382 m_annotations = newAnnotations.take();
383 }
384}
385
386bool QQmlJSBasicBlocks::canMove(int instructionOffset, const RegisterAccess &access) const
387{
388 if (access.registerReadersAndConversions.size() != 1)
389 return false;
390 const auto basicBlockForInstruction = [this](int instruction) {
391 auto block = m_basicBlocks.lower_bound(key: instruction);
392 if (block == m_basicBlocks.end() || block.key() == instruction)
393 return block;
394 Q_ASSERT(block.key() > instruction);
395 if (block == m_basicBlocks.begin())
396 return m_basicBlocks.end();
397 return --block;
398 };
399 return basicBlockForInstruction(instructionOffset)
400 == basicBlockForInstruction(access.registerReadersAndConversions.begin().key());
401}
402
403static QString adjustErrorMessage(
404 const QQmlJSScope::ConstPtr &origin, const QQmlJSScope::ConstPtr &conversion) {
405 return QLatin1String("Cannot convert from ")
406 + origin->internalName() + QLatin1String(" to ") + conversion->internalName();
407}
408
409static QString adjustErrorMessage(
410 const QQmlJSScope::ConstPtr &origin, const QList<QQmlJSScope::ConstPtr> &conversions) {
411 if (conversions.size() == 1)
412 return adjustErrorMessage(origin, conversion: conversions[0]);
413
414 QString types;
415 for (const QQmlJSScope::ConstPtr &type : conversions) {
416 if (!types.isEmpty())
417 types += QLatin1String(", ");
418 types += type->internalName();
419 }
420 return QLatin1String("Cannot convert from ")
421 + origin->internalName() + QLatin1String(" to union of ") + types;
422}
423
424void QQmlJSBasicBlocks::adjustTypes()
425{
426 using NewVirtualRegisters = NewFlatMap<int, VirtualRegister>;
427
428 QHash<int, QList<int>> liveConversions;
429 QHash<int, QList<int>> movableReads;
430
431 const auto handleRegisterReadersAndConversions
432 = [&](QHash<int, RegisterAccess>::const_iterator it) {
433 for (auto conversions = it->registerReadersAndConversions.constBegin(),
434 end = it->registerReadersAndConversions.constEnd(); conversions != end;
435 ++conversions) {
436 if (conversions->isEmpty() && canMove(instructionOffset: it.key(), access: it.value()))
437 movableReads[conversions.key()].append(t: it->trackedRegister);
438 for (int conversion : *conversions)
439 liveConversions[conversion].append(t: it->trackedRegister);
440 }
441 };
442
443 // Handle the array definitions first.
444 // Changing the array type changes the expected element types.
445 for (int instructionOffset : m_arrayDefinitions) {
446 auto it = m_readerLocations.find(key: instructionOffset);
447 if (it == m_readerLocations.end())
448 continue;
449
450 const InstructionAnnotation &annotation = m_annotations[instructionOffset];
451
452 Q_ASSERT(it->trackedTypes.size() == 1);
453 Q_ASSERT(it->trackedTypes[0] == m_typeResolver->containedType(annotation.changedRegister));
454 Q_ASSERT(!annotation.readRegisters.isEmpty());
455
456 if (!m_typeResolver->adjustTrackedType(tracked: it->trackedTypes[0], conversions: it->typeReaders.values()))
457 setError(adjustErrorMessage(origin: it->trackedTypes[0], conversions: it->typeReaders.values()));
458
459 // Now we don't adjust the type we store, but rather the type we expect to read. We
460 // can do this because we've tracked the read type when we defined the array in
461 // QQmlJSTypePropagator.
462 if (QQmlJSScope::ConstPtr valueType = it->trackedTypes[0]->valueType()) {
463 const QQmlJSScope::ConstPtr contained
464 = m_typeResolver->containedType(
465 container: annotation.readRegisters.begin().value().content);
466 if (!m_typeResolver->adjustTrackedType(tracked: contained, conversion: valueType))
467 setError(adjustErrorMessage(origin: contained, conversion: valueType));
468 }
469
470 handleRegisterReadersAndConversions(it);
471 m_readerLocations.erase(it);
472 }
473
474 for (auto it = m_readerLocations.begin(), end = m_readerLocations.end(); it != end; ++it) {
475 handleRegisterReadersAndConversions(it);
476
477 // There is always one first occurrence of any tracked type. Conversions don't change
478 // the type.
479 if (it->trackedTypes.size() != 1)
480 continue;
481
482 if (!m_typeResolver->adjustTrackedType(tracked: it->trackedTypes[0], conversions: it->typeReaders.values()))
483 setError(adjustErrorMessage(origin: it->trackedTypes[0], conversions: it->typeReaders.values()));
484 }
485
486 const auto transformRegister = [&](QQmlJSRegisterContent &content) {
487 const QQmlJSScope::ConstPtr conversion
488 = m_typeResolver->storedType(type: m_typeResolver->containedType(container: content));
489 if (!m_typeResolver->adjustTrackedType(tracked: content.storedType(), conversion))
490 setError(adjustErrorMessage(origin: content.storedType(), conversion));
491 };
492
493 NewVirtualRegisters newRegisters;
494 for (auto i = m_annotations.begin(), iEnd = m_annotations.end(); i != iEnd; ++i) {
495 if (i->second.changedRegisterIndex != InvalidRegister)
496 transformRegister(i->second.changedRegister);
497
498 for (auto conversion = i->second.typeConversions.begin(),
499 conversionEnd = i->second.typeConversions.end(); conversion != conversionEnd;
500 ++conversion) {
501 if (!liveConversions[i.key()].contains(t: conversion.key()))
502 continue;
503
504 QQmlJSScope::ConstPtr conversionResult = conversion->second.content.conversionResult();
505 const auto conversionOrigins = conversion->second.content.conversionOrigins();
506 QQmlJSScope::ConstPtr newResult;
507 for (const auto &origin : conversionOrigins)
508 newResult = m_typeResolver->merge(a: newResult, b: origin);
509 if (!m_typeResolver->adjustTrackedType(tracked: conversionResult, conversion: newResult))
510 setError(adjustErrorMessage(origin: conversionResult, conversion: newResult));
511 transformRegister(conversion->second.content);
512 newRegisters.appendOrdered(i: conversion);
513 }
514 i->second.typeConversions = newRegisters.take();
515
516 for (int movable : std::as_const(t&: movableReads[i.key()]))
517 i->second.readRegisters[movable].canMove = true;
518 }
519}
520
521void QQmlJSBasicBlocks::populateBasicBlocks()
522{
523 for (auto blockNext = m_basicBlocks.begin(), blockEnd = m_basicBlocks.end();
524 blockNext != blockEnd;) {
525
526 const auto blockIt = blockNext++;
527 BasicBlock &block = blockIt->second;
528 QList<QQmlJSScope::ConstPtr> writtenTypes;
529 QList<int> writtenRegisters;
530
531 const auto instrEnd = (blockNext == blockEnd)
532 ? m_annotations.end()
533 : m_annotations.find(key: blockNext->first);
534 for (auto instrIt = m_annotations.find(key: blockIt->first); instrIt != instrEnd; ++instrIt) {
535 const InstructionAnnotation &instruction = instrIt->second;
536 for (auto it = instruction.readRegisters.begin(), end = instruction.readRegisters.end();
537 it != end; ++it) {
538 if (!instruction.isRename) {
539 Q_ASSERT(it->second.content.isConversion());
540 for (const QQmlJSScope::ConstPtr &origin :
541 it->second.content.conversionOrigins()) {
542 if (!writtenTypes.contains(t: origin))
543 block.readTypes.append(t: origin);
544 }
545 }
546 if (!writtenRegisters.contains(t: it->first))
547 block.readRegisters.append(t: it->first);
548 }
549
550 // If it's just a renaming, the type has existed in a different register before.
551 if (instruction.changedRegisterIndex != InvalidRegister) {
552 if (!instruction.isRename) {
553 writtenTypes.append(t: m_typeResolver->trackedContainedType(
554 container: instruction.changedRegister));
555 }
556 writtenRegisters.append(t: instruction.changedRegisterIndex);
557 }
558 }
559
560 deduplicate(container&: block.readTypes);
561 deduplicate(container&: block.readRegisters);
562 }
563}
564
565QT_END_NAMESPACE
566

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