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
6#include <private/qqmlglobal_p.h>
7#include <private/qqmljsutils_p.h>
8#include <private/qv4instr_moth_p.h>
9
10QT_BEGIN_NAMESPACE
11
12using namespace Qt::Literals::StringLiterals;
13
14DEFINE_BOOL_CONFIG_OPTION(qv4DumpBasicBlocks, QV4_DUMP_BASIC_BLOCKS)
15DEFINE_BOOL_CONFIG_OPTION(qv4ValidateBasicBlocks, QV4_VALIDATE_BASIC_BLOCKS)
16
17void QQmlJSBasicBlocks::dumpBasicBlocks()
18{
19 qDebug().noquote() << "=== Basic Blocks for \"%1\""_L1.arg(args: m_context->name);
20 for (const auto &[blockOffset, block] : m_basicBlocks) {
21 QDebug debug = qDebug().nospace();
22 debug << "Block " << (blockOffset < 0 ? "Function prolog"_L1 : QString::number(blockOffset))
23 << ":\n";
24 debug << " jumpOrigins[" << block.jumpOrigins.size() << "]: ";
25 for (auto origin : std::as_const(t&: block.jumpOrigins)) {
26 debug << origin << ", ";
27 }
28 debug << "\n readRegisters[" << block.readRegisters.size() << "]: ";
29 for (auto reg : std::as_const(t&: block.readRegisters)) {
30 debug << reg << ", ";
31 }
32 debug << "\n jumpTarget: " << block.jumpTarget;
33 debug << "\n jumpIsUnConditional: " << block.jumpIsUnconditional;
34 debug << "\n isReturnBlock: " << block.isReturnBlock;
35 debug << "\n isThrowBlock: " << block.isThrowBlock;
36 }
37 qDebug() << "\n";
38}
39
40void QQmlJSBasicBlocks::dumpDOTGraph()
41{
42 QString output;
43 QTextStream s{ &output };
44 s << "=== Basic Blocks Graph in DOT format for \"%1\" (spaces are encoded as"
45 " &#160; to preserve formatting)\n"_L1.arg(args: m_context->name);
46 s << "digraph BasicBlocks {\n"_L1;
47
48 QFlatMap<int, BasicBlock> blocks{ m_basicBlocks };
49 for (const auto &[blockOffset, block] : blocks) {
50 for (int originOffset : std::as_const(t&: block.jumpOrigins)) {
51 const auto originBlockIt = basicBlockForInstruction(container&: blocks, instructionOffset: originOffset);
52 const auto isBackEdge = originOffset > blockOffset && originBlockIt->second.jumpIsUnconditional;
53 s << " %1 -> %2%3\n"_L1.arg(args: QString::number(originBlockIt.key()))
54 .arg(a: QString::number(blockOffset))
55 .arg(a: isBackEdge ? " [color=blue]"_L1 : ""_L1);
56 }
57 }
58
59 for (const auto &[blockOffset, block] : blocks) {
60 if (blockOffset < 0) {
61 s << " %1 [shape=record, fontname=\"Monospace\", label=\"Function Prolog\"]\n"_L1
62 .arg(args: QString::number(blockOffset));
63 continue;
64 }
65
66 auto nextBlockIt = blocks.lower_bound(key: blockOffset + 1);
67 int nextBlockOffset = nextBlockIt == blocks.end() ? m_context->code.size() : nextBlockIt->first;
68 QString dump = QV4::Moth::dumpBytecode(
69 bytecode: m_context->code.constData(), len: m_context->code.size(), nLocals: m_context->locals.size(),
70 nFormals: m_context->formals->length(), beginOffset: blockOffset, endOffset: nextBlockOffset - 1,
71 lineAndStatementNumberMapping: m_context->lineAndStatementNumberMapping);
72 dump = dump.replace(before: " "_L1, after: "&#160;"_L1); // prevent collapse of extra whitespace for formatting
73 dump = dump.replace(before: "\n"_L1, after: "\\l"_L1); // new line + left aligned
74 dump = dump.replace(before: "<"_L1, after: "\\<"_L1).replace(before: ">"_L1, after: "\\>"_L1); // escape < and > for "SetUnwindHandler <null>" instruction
75 s << " %1 [shape=record, fontname=\"Monospace\", label=\"{Block %1: | %2}\"]\n"_L1
76 .arg(args: QString::number(blockOffset))
77 .arg(a: dump);
78 }
79 s << "}\n"_L1;
80
81 // Have unique names to prevent overwriting of functions with the same name (eg. anonymous functions).
82 static int functionCount = 0;
83 static const auto dumpFolderPath = qEnvironmentVariable(varName: "QV4_DUMP_BASIC_BLOCKS");
84
85 QString expressionName = m_context->name == ""_L1
86 ? "anonymous"_L1
87 : QString(m_context->name).replace(before: " "_L1, after: "_"_L1);
88 QString fileName = "function"_L1 + QString::number(functionCount++) + "_"_L1 + expressionName + ".gv"_L1;
89 QFile dumpFile(dumpFolderPath + (dumpFolderPath.endsWith(s: "/"_L1) ? ""_L1 : "/"_L1) + fileName);
90
91 if (dumpFolderPath == "-"_L1 || dumpFolderPath == "1"_L1 || dumpFolderPath == "true"_L1) {
92 qDebug().noquote() << output;
93 } else {
94 if (!dumpFile.open(flags: QIODeviceBase::Truncate | QIODevice::WriteOnly)) {
95 qDebug() << "Error: Could not open file to dump the basic blocks into";
96 } else {
97 dumpFile.write(data: ("//"_L1 + output).toLatin1().toStdString().c_str());
98 dumpFile.close();
99 }
100 }
101}
102
103QQmlJSCompilePass::BlocksAndAnnotations
104QQmlJSBasicBlocks::run(const Function *function, QQmlJSAotCompiler::Flags compileFlags,
105 bool &basicBlocksValidationFailed)
106{
107 basicBlocksValidationFailed = false;
108
109 m_function = function;
110
111 for (int i = 0, end = function->argumentTypes.size(); i != end; ++i) {
112 InstructionAnnotation annotation;
113 annotation.changedRegisterIndex = FirstArgument + i;
114 annotation.changedRegister = function->argumentTypes[i];
115 m_annotations[-annotation.changedRegisterIndex] = annotation;
116 }
117
118 for (int i = 0, end = function->registerTypes.size(); i != end; ++i) {
119 InstructionAnnotation annotation;
120 annotation.changedRegisterIndex = firstRegisterIndex() + i;
121 annotation.changedRegister = function->registerTypes[i];
122 m_annotations[-annotation.changedRegisterIndex] = annotation;
123 }
124
125 // Insert the function prolog block followed by the first "real" block.
126 m_basicBlocks.insert_or_assign(key: m_annotations.begin().key(), obj: BasicBlock());
127 BasicBlock zeroBlock;
128 zeroBlock.jumpOrigins.append(t: m_basicBlocks.begin().key());
129 m_basicBlocks.insert(key: 0, value: zeroBlock);
130
131 const QByteArray &byteCode = function->code;
132 decode(code: byteCode.constData(), len: static_cast<uint>(byteCode.size()));
133 if (m_hadBackJumps) {
134 // We may have missed some connections between basic blocks if there were back jumps.
135 // Fill them in via a second pass.
136
137 // We also need to re-calculate the jump targets then because the basic block boundaries
138 // may have shifted.
139 for (auto it = m_basicBlocks.begin(), end = m_basicBlocks.end(); it != end; ++it) {
140 it->second.jumpTarget = -1;
141 it->second.jumpIsUnconditional = false;
142 }
143
144 m_skipUntilNextLabel = false;
145
146 reset();
147 decode(code: byteCode.constData(), len: static_cast<uint>(byteCode.size()));
148 for (auto it = m_basicBlocks.begin(), end = m_basicBlocks.end(); it != end; ++it)
149 QQmlJSUtils::deduplicate(container&: it->second.jumpOrigins);
150 }
151
152 if (compileFlags.testFlag(flag: QQmlJSAotCompiler::ValidateBasicBlocks) || qv4ValidateBasicBlocks()) {
153 if (auto validationResult = basicBlocksValidation(); !validationResult.success) {
154 qDebug() << "Basic blocks validation failed: %1."_L1.arg(args&: validationResult.errorMessage);
155 basicBlocksValidationFailed = true;
156 }
157 }
158
159 if (qv4DumpBasicBlocks()) {
160 dumpBasicBlocks();
161 dumpDOTGraph();
162 }
163
164 return { .basicBlocks: std::move(m_basicBlocks), .annotations: std::move(m_annotations) };
165}
166
167QV4::Moth::ByteCodeHandler::Verdict QQmlJSBasicBlocks::startInstruction(QV4::Moth::Instr::Type type)
168{
169 auto it = m_basicBlocks.find(key: currentInstructionOffset());
170 if (it != m_basicBlocks.end()) {
171 m_skipUntilNextLabel = false;
172 } else if (m_skipUntilNextLabel && !instructionManipulatesContext(type)) {
173 return SkipInstruction;
174 }
175
176 return ProcessInstruction;
177}
178
179void QQmlJSBasicBlocks::endInstruction(QV4::Moth::Instr::Type)
180{
181 if (m_skipUntilNextLabel)
182 return;
183 auto it = m_basicBlocks.find(key: nextInstructionOffset());
184 if (it != m_basicBlocks.end())
185 it->second.jumpOrigins.append(t: currentInstructionOffset());
186}
187
188void QQmlJSBasicBlocks::generate_Jump(int offset)
189{
190 processJump(offset, mode: Unconditional);
191}
192
193void QQmlJSBasicBlocks::generate_JumpTrue(int offset)
194{
195 processJump(offset, mode: Conditional);
196}
197
198void QQmlJSBasicBlocks::generate_JumpFalse(int offset)
199{
200 processJump(offset, mode: Conditional);
201}
202
203void QQmlJSBasicBlocks::generate_JumpNoException(int offset)
204{
205 processJump(offset, mode: Conditional);
206}
207
208void QQmlJSBasicBlocks::generate_JumpNotUndefined(int offset)
209{
210 processJump(offset, mode: Conditional);
211}
212
213void QQmlJSBasicBlocks::generate_IteratorNext(int value, int offset)
214{
215 Q_UNUSED(value);
216 processJump(offset, mode: Conditional);
217}
218
219void QQmlJSBasicBlocks::generate_GetOptionalLookup(int index, int offset)
220{
221 Q_UNUSED(index);
222 processJump(offset, mode: Conditional);
223}
224
225void QQmlJSBasicBlocks::generate_Ret()
226{
227 auto currentBlock = basicBlockForInstruction(container&: m_basicBlocks, instructionOffset: currentInstructionOffset());
228 currentBlock.value().isReturnBlock = true;
229 m_skipUntilNextLabel = true;
230}
231
232void QQmlJSBasicBlocks::generate_ThrowException()
233{
234 auto currentBlock = basicBlockForInstruction(container&: m_basicBlocks, instructionOffset: currentInstructionOffset());
235 currentBlock.value().isThrowBlock = true;
236 m_skipUntilNextLabel = true;
237}
238
239void QQmlJSBasicBlocks::generate_DefineArray(int argc, int argv)
240{
241 if (argc == 0)
242 return; // empty array/list, nothing to do
243
244 m_objectAndArrayDefinitions.append(t: {
245 .instructionOffset: currentInstructionOffset(), .internalClassId: ObjectOrArrayDefinition::ArrayClassId, .argc: argc, .argv: argv
246 });
247}
248
249void QQmlJSBasicBlocks::generate_DefineObjectLiteral(int internalClassId, int argc, int argv)
250{
251 if (argc == 0)
252 return;
253
254 m_objectAndArrayDefinitions.append(t: { .instructionOffset: currentInstructionOffset(), .internalClassId: internalClassId, .argc: argc, .argv: argv });
255}
256
257void QQmlJSBasicBlocks::generate_Construct(int func, int argc, int argv)
258{
259 Q_UNUSED(func)
260 if (argc == 0)
261 return; // empty array/list, nothing to do
262
263 m_objectAndArrayDefinitions.append(t: {
264 .instructionOffset: currentInstructionOffset(),
265 .internalClassId: argc == 1
266 ? ObjectOrArrayDefinition::ArrayConstruct1ArgId
267 : ObjectOrArrayDefinition::ArrayClassId,
268 .argc: argc,
269 .argv: argv
270 });
271}
272
273void QQmlJSBasicBlocks::processJump(int offset, JumpMode mode)
274{
275 if (offset < 0)
276 m_hadBackJumps = true;
277 const int jumpTarget = absoluteOffset(relativeOffset: offset);
278 Q_ASSERT(!m_basicBlocks.isEmpty());
279 auto currentBlock = basicBlockForInstruction(container&: m_basicBlocks, instructionOffset: currentInstructionOffset());
280 currentBlock->second.jumpTarget = jumpTarget;
281 currentBlock->second.jumpIsUnconditional = (mode == Unconditional);
282 m_basicBlocks[jumpTarget].jumpOrigins.append(t: currentInstructionOffset());
283 if (mode == Unconditional)
284 m_skipUntilNextLabel = true;
285 else
286 m_basicBlocks.insert(key: nextInstructionOffset(), value: BasicBlock());
287}
288
289QQmlJSCompilePass::BasicBlocks::iterator QQmlJSBasicBlocks::basicBlockForInstruction(
290 QFlatMap<int, BasicBlock> &container, int instructionOffset)
291{
292 auto block = container.lower_bound(key: instructionOffset);
293 if (block == container.end() || block->first != instructionOffset)
294 --block;
295 return block;
296}
297
298QQmlJSCompilePass::BasicBlocks::const_iterator QQmlJSBasicBlocks::basicBlockForInstruction(
299 const BasicBlocks &container, int instructionOffset)
300{
301 return basicBlockForInstruction(container&: const_cast<BasicBlocks &>(container), instructionOffset);
302}
303
304QQmlJSBasicBlocks::BasicBlocksValidationResult QQmlJSBasicBlocks::basicBlocksValidation()
305{
306 if (m_basicBlocks.empty())
307 return {};
308
309 const QFlatMap<int, BasicBlock> blocks{ m_basicBlocks };
310 QList<QFlatMap<int, BasicBlock>::const_iterator> returnOrThrowBlocks;
311 for (auto it = blocks.cbegin(); it != blocks.cend(); ++it) {
312 if (it.value().isReturnBlock || it.value().isThrowBlock)
313 returnOrThrowBlocks.append(t: it);
314 }
315
316 // 1. Return blocks and throw blocks must not have a jump target
317 for (const auto &it : returnOrThrowBlocks) {
318 if (it.value().jumpTarget != -1)
319 return { .success: false, .errorMessage: "Return or throw block jumps to somewhere"_L1 };
320 }
321
322 // 2. The basic blocks graph must be connected.
323 QSet<int> visitedBlockOffsets;
324 QList<QFlatMap<int, BasicBlock>::const_iterator> toVisit;
325 toVisit.append(l: returnOrThrowBlocks);
326
327 while (!toVisit.empty()) {
328 const auto &[offset, block] = *toVisit.takeLast();
329 visitedBlockOffsets.insert(value: offset);
330 for (int originOffset : block.jumpOrigins) {
331 const auto originBlock = basicBlockForInstruction(container: blocks, instructionOffset: originOffset);
332 if (visitedBlockOffsets.find(value: originBlock.key()) == visitedBlockOffsets.end()
333 && !toVisit.contains(t: originBlock))
334 toVisit.append(t: originBlock);
335 }
336 }
337
338 if (visitedBlockOffsets.size() != blocks.size())
339 return { .success: false, .errorMessage: "Basic blocks graph is not fully connected"_L1 };
340
341 // 3. A block's jump target must be the first offset of a block.
342 for (const auto &[blockOffset, block] : blocks) {
343 auto target = block.jumpTarget;
344 if (target != -1 && blocks.find(key: target) == blocks.end())
345 return { .success: false, .errorMessage: "Invalid jump; target is not the start of a block"_L1 };
346 }
347
348 return {};
349}
350
351QT_END_NAMESPACE
352

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