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
|
/****************************************************************************
**
** Copyright (C) 2015 The Qt Company Ltd.
** Contact: http://www.qt.io/licensing/
**
** This file is part of the V4VM module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL21$
** 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 http://www.qt.io/terms-conditions. For further
** information use the contact form at http://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 2.1 or version 3 as published by the Free
** Software Foundation and appearing in the file LICENSE.LGPLv21 and
** LICENSE.LGPLv3 included in the packaging of this file. Please review the
** following information to ensure the GNU Lesser General Public License
** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
**
** As a special exception, The Qt Company gives you certain additional
** rights. These rights are described in The Qt Company LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** $QT_END_LICENSE$
**
****************************************************************************/
#ifndef QV4REGALLOC_P_H
#define QV4REGALLOC_P_H
//
// W A R N I N G
// -------------
//
// This file is not part of the Qt API. It exists purely as an
// implementation detail. This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//
#include "qv4global_p.h"
#include "qv4isel_p.h"
#include "qv4ssa_p.h"
#include "qv4registerinfo_p.h"
#include <config.h>
QT_BEGIN_NAMESPACE
namespace QV4 {
namespace JIT {
class RegAllocInfo;
// This class implements a linear-scan register allocator, with a couple of tweaks:
// - Second-chance allocation is used when an interval becomes active after a spill, which results
// in fewer differences between edges, and hence fewer moves before jumps.
// - Use positions are flagged with either "must have" register or "could have" register. This is
// used to decide whether a register is really needed when a temporary is used after a spill
// occurred.
// - Fixed intervals are used to denotate IR positions where certain registers are needed in order
// to implement the operation, and cannot be used by a temporary on that position. An example is
// caller saved registers, where the call will use/clobber those registers.
// - Hints are used to indicate which registers could be used to generate more compact code. An
// example is an addition, where one (or both) operands' life-time ends at that instruction. In
// this case, re-using an operand register for the result will result in an in-place add.
// - SSA form properties are used:
// - to simplify life-times (two temporaries will never interfere as long as their intervals
// are not split), resulting in a slightly faster algorithm;
// - when a temporary needs to be spilled, it is done directly after calculating it, so that
// 1 store is generated even if multiple spills/splits happen.
// - phi-node elimination (SSA form deconstruction) is done when resolving differences between
// CFG edges
class RegisterAllocator
{
typedef IR::LifeTimeInterval LifeTimeInterval;
const RegisterInformation &_registerInformation;
QVector<const RegisterInfo *> _normalRegisters;
QVector<const RegisterInfo *> _fpRegisters;
QScopedPointer<RegAllocInfo> _info;
QVector<LifeTimeInterval *> _fixedRegisterRanges, _fixedFPRegisterRanges;
IR::LifeTimeIntervals::Ptr _lifeTimeIntervals;
typedef QVector<LifeTimeInterval *> Intervals;
Intervals _unhandled, _active, _inactive, _handled;
std::vector<int> _lastAssignedRegister;
std::vector<int> _assignedSpillSlots;
QVector<int> _activeSpillSlots;
QBitArray _regularRegsInUse, _fpRegsInUse;
Q_DISABLE_COPY(RegisterAllocator)
public:
enum { InvalidSpillSlot = -1 };
RegisterAllocator(const RegisterInformation ®isterInformation);
~RegisterAllocator();
void run(IR::Function *function, const IR::Optimizer &opt);
RegisterInformation usedRegisters() const;
private:
void markInUse(int reg, bool isFPReg);
LifeTimeInterval *cloneFixedInterval(int reg, bool isFP, const LifeTimeInterval &original);
void prepareRanges();
void linearScan();
void tryAllocateFreeReg(LifeTimeInterval ¤t);
void allocateBlockedReg(LifeTimeInterval ¤t);
int nextIntersection(const LifeTimeInterval ¤t, const LifeTimeInterval &another) const;
int nextUse(const IR::Temp &t, int startPosition) const;
void split(LifeTimeInterval ¤t, int beforePosition, bool skipOptionalRegisterUses =false);
void splitInactiveAtEndOfLifetimeHole(int reg, bool isFPReg, int position);
void assignSpillSlot(const IR::Temp &t, int startPos, int endPos);
void resolve(IR::Function *function, const IR::Optimizer &opt);
void dump(IR::Function *function) const;
};
} // end of namespace JIT
} // end of namespace QV4
QT_END_NAMESPACE
#endif // QV4REGALLOC_P_H
|
