1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
/****************************************************************************
**
** Copyright (C) 2018 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtQml module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/
#include <QtCore/qloggingcategory.h>
#include "qv4blockscheduler_p.h"
#include "qv4domtree_p.h"
#include "qv4loopinfo_p.h"
QT_BEGIN_NAMESPACE
namespace QV4 {
namespace IR {
Q_LOGGING_CATEGORY(lcBlockScheduler, "qt.v4.ir.blockscheduler")
bool BlockScheduler::checkCandidate(MIBlock *candidate)
{
Q_ASSERT(loopInfo.loopHeaderFor(candidate) == currentGroup.group);
for (MIBlock *pred : candidate->inEdges()) {
if (pred->isDeoptBlock())
continue;
if (emitted.alreadyProcessed(pred))
continue;
if (dominatorTree.dominates(candidate->index(), pred->index())) {
// this is a loop, where there in
// -> candidate edge is the jump back to the top of the loop.
continue;
}
if (pred == candidate)
// this is a very tight loop, e.g.:
// L1: ...
// goto L1
// This can happen when, for example, the basic-block merging gets rid of the empty
// body block. In this case, we can safely schedule this block (if all other
// incoming edges are either loop-back edges, or have been scheduled already).
continue;
return false; // an incoming edge that is not yet emitted, and is not a back-edge
}
if (loopInfo.isLoopHeader(candidate)) {
// postpone everything, and schedule the loop first.
postponedGroups.push(currentGroup);
currentGroup = WorkForGroup(candidate);
}
return true;
}
MIBlock *BlockScheduler::pickNext()
{
while (true) {
while (currentGroup.postponed.isEmpty()) {
if (postponedGroups.isEmpty())
return nullptr;
if (currentGroup.group) // record the first and the last node of a group
loopsStartEnd[currentGroup.group] = sequence.back();
currentGroup = postponedGroups.pop();
}
MIBlock *next = currentGroup.postponed.pop();
if (checkCandidate(next))
return next;
}
Q_UNREACHABLE();
return nullptr;
}
void BlockScheduler::emitBlock(MIBlock *bb)
{
if (emitted.alreadyProcessed(bb))
return;
sequence.push_back(bb);
emitted.markAsProcessed(bb);
}
void BlockScheduler::schedule(MIBlock *functionEntryPoint)
{
MIBlock *next = functionEntryPoint;
while (next) {
emitBlock(next);
// postpone all outgoing edges, if they were not already processed
QVarLengthArray<MIBlock *, 32> nonExceptionEdges;
// first postpone all exception edges, so they will be processed last
for (int i = next->outEdges().size(); i != 0; ) {
--i;
MIBlock *out = next->outEdges().at(i);
if (emitted.alreadyProcessed(out))
continue;
if (out == nullptr)
continue;
if (out->instructions().front().opcode() == Meta::OnException)
postpone(out);
else
nonExceptionEdges.append(out);
}
for (MIBlock *edge : nonExceptionEdges)
postpone(edge);
next = pickNext();
}
// finally schedule all de-optimization blocks at the end
for (auto bb : dominatorTree.function()->blocks()) {
if (bb->isDeoptBlock())
emitBlock(bb);
}
}
void BlockScheduler::postpone(MIBlock *bb)
{
if (currentGroup.group == loopInfo.loopHeaderFor(bb)) {
currentGroup.postponed.append(bb);
return;
}
for (int i = postponedGroups.size(); i != 0; ) {
--i;
WorkForGroup &g = postponedGroups[i];
if (g.group == loopInfo.loopHeaderFor(bb)) {
g.postponed.append(bb);
return;
}
}
Q_UNREACHABLE();
}
void BlockScheduler::dump() const
{
if (!lcBlockScheduler().isDebugEnabled())
return;
QString s = QStringLiteral("Scheduled blocks:\n");
for (auto *bb : sequence) {
s += QLatin1String(" L") + QString::number(bb->index());
MIBlock *loopEnd = loopsStartEnd[bb];
if (loopEnd)
s += QLatin1String(", loop start, ends at L") + QString::number(loopEnd->index());
s += QLatin1Char('\n');
}
qCDebug(lcBlockScheduler).noquote().nospace() << s;
}
BlockScheduler::BlockScheduler(const DominatorTree &dominatorTree, const LoopInfo &loopInfo)
: dominatorTree(dominatorTree)
, loopInfo(loopInfo)
, sequence(0)
, emitted(dominatorTree.function())
{
schedule(dominatorTree.function()->blocks().front());
dump();
if (dominatorTree.function()->blockCount() != sequence.size()) {
qFatal("The block scheduler did not schedule all blocks. This is most likely due to"
"a non-natural loop.");
// Usually caused by having an execution path that manages to skip over unwind handler
// reset: any exception happening after will jump back to the unwind handler, and thereby
// creating a loop that can be entered in 2 different ways.
}
}
} // IR namespace
} // QV4 namespace
QT_END_NAMESPACE
|
