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

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