← Back to branch summary

~ubuntu-branches/ubuntu/trusty/mozjs24/trusty-proposed

« back to all changes in this revision

Viewing changes to js/src/jit/RegisterAllocator.h

  • Committer: Package Import Robot
  • Author(s): Tim Lunn
  • Date: 2014-02-11 21:55:34 UTC
  • Revision ID: package-import@ubuntu.com-20140211215534-m1zyq5aj59md3y07
Tags: upstream-24.2.0
Import upstream version 24.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
js/src/jit/RegisterAllocator.h
 
1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 
2
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 
3
 * This Source Code Form is subject to the terms of the Mozilla Public
 
4
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 
5
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
6
 
 
7
#ifndef jit_RegisterAllocator_h
 
8
#define jit_RegisterAllocator_h
 
9
 
 
10
#include "mozilla/Attributes.h"
 
11
 
 
12
#include "Ion.h"
 
13
#include "MIR.h"
 
14
#include "MIRGraph.h"
 
15
#include "InlineList.h"
 
16
#include "LIR.h"
 
17
#include "Lowering.h"
 
18
 
 
19
// Generic structures and functions for use by register allocators.
 
20
 
 
21
namespace js {
 
22
namespace jit {
 
23
 
 
24
// Structure for running a liveness analysis on a finished register allocation.
 
25
// This analysis can be used for two purposes:
 
26
//
 
27
// - Check the integrity of the allocation, i.e. that the reads and writes of
 
28
//   physical values preserve the semantics of the original virtual registers.
 
29
//
 
30
// - Populate safepoints with live registers, GC thing and value data, to
 
31
//   streamline the process of prototyping new allocators.
 
32
struct AllocationIntegrityState
 
33
{
 
34
    AllocationIntegrityState(LIRGraph &graph)
 
35
      : graph(graph)
 
36
    {}
 
37
 
 
38
    // Record all virtual registers in the graph. This must be called before
 
39
    // register allocation, to pick up the original LUses.
 
40
    bool record();
 
41
 
 
42
    // Perform the liveness analysis on the graph, and assert on an invalid
 
43
    // allocation. This must be called after register allocation, to pick up
 
44
    // all assigned physical values. If populateSafepoints is specified,
 
45
    // safepoints will be filled in with liveness information.
 
46
    bool check(bool populateSafepoints);
 
47
 
 
48
  private:
 
49
 
 
50
    LIRGraph &graph;
 
51
 
 
52
    // For all instructions and phis in the graph, keep track of the virtual
 
53
    // registers for all inputs and outputs of the nodes. These are overwritten
 
54
    // in place during register allocation. This information is kept on the
 
55
    // side rather than in the instructions and phis themselves to avoid
 
56
    // debug-builds-only bloat in the size of the involved structures.
 
57
 
 
58
    struct InstructionInfo {
 
59
        Vector<LAllocation, 2, SystemAllocPolicy> inputs;
 
60
        Vector<LDefinition, 0, SystemAllocPolicy> temps;
 
61
        Vector<LDefinition, 1, SystemAllocPolicy> outputs;
 
62
 
 
63
        InstructionInfo()
 
64
        { }
 
65
 
 
66
        InstructionInfo(const InstructionInfo &o)
 
67
        {
 
68
            inputs.append(o.inputs);
 
69
            temps.append(o.temps);
 
70
            outputs.append(o.outputs);
 
71
        }
 
72
    };
 
73
    Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;
 
74
 
 
75
    struct BlockInfo {
 
76
        Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
 
77
        BlockInfo() {}
 
78
        BlockInfo(const BlockInfo &o) {
 
79
            phis.append(o.phis);
 
80
        }
 
81
    };
 
82
    Vector<BlockInfo, 0, SystemAllocPolicy> blocks;
 
83
 
 
84
    Vector<LDefinition*, 20, SystemAllocPolicy> virtualRegisters;
 
85
 
 
86
    // Describes a correspondence that should hold at the end of a block.
 
87
    // The value which was written to vreg in the original LIR should be
 
88
    // physically stored in alloc after the register allocation.
 
89
    struct IntegrityItem
 
90
    {
 
91
        LBlock *block;
 
92
        uint32_t vreg;
 
93
        LAllocation alloc;
 
94
 
 
95
        // Order of insertion into seen, for sorting.
 
96
        uint32_t index;
 
97
 
 
98
        typedef IntegrityItem Lookup;
 
99
        static HashNumber hash(const IntegrityItem &item) {
 
100
            HashNumber hash = item.alloc.hash();
 
101
            hash = JS_ROTATE_LEFT32(hash, 4) ^ item.vreg;
 
102
            hash = JS_ROTATE_LEFT32(hash, 4) ^ HashNumber(item.block->mir()->id());
 
103
            return hash;
 
104
        }
 
105
        static bool match(const IntegrityItem &one, const IntegrityItem &two) {
 
106
            return one.block == two.block
 
107
                && one.vreg == two.vreg
 
108
                && one.alloc == two.alloc;
 
109
        }
 
110
    };
 
111
 
 
112
    // Items still to be processed.
 
113
    Vector<IntegrityItem, 10, SystemAllocPolicy> worklist;
 
114
 
 
115
    // Set of all items that have already been processed.
 
116
    typedef HashSet<IntegrityItem, IntegrityItem, SystemAllocPolicy> IntegrityItemSet;
 
117
    IntegrityItemSet seen;
 
118
 
 
119
    bool checkIntegrity(LBlock *block, LInstruction *ins, uint32_t vreg, LAllocation alloc,
 
120
                        bool populateSafepoints);
 
121
    bool checkSafepointAllocation(LInstruction *ins, uint32_t vreg, LAllocation alloc,
 
122
                                  bool populateSafepoints);
 
123
    bool addPredecessor(LBlock *block, uint32_t vreg, LAllocation alloc);
 
124
 
 
125
    void dump();
 
126
};
 
127
 
 
128
// Represents with better-than-instruction precision a position in the
 
129
// instruction stream.
 
130
//
 
131
// An issue comes up when performing register allocation as to how to represent
 
132
// information such as "this register is only needed for the input of
 
133
// this instruction, it can be clobbered in the output". Just having ranges
 
134
// of instruction IDs is insufficiently expressive to denote all possibilities.
 
135
// This class solves this issue by associating an extra bit with the instruction
 
136
// ID which indicates whether the position is the input half or output half of
 
137
// an instruction.
 
138
class CodePosition
 
139
{
 
140
  private:
 
141
    MOZ_CONSTEXPR CodePosition(const uint32_t &bits)
 
142
      : bits_(bits)
 
143
    { }
 
144
 
 
145
    static const unsigned int INSTRUCTION_SHIFT = 1;
 
146
    static const unsigned int SUBPOSITION_MASK = 1;
 
147
    uint32_t bits_;
 
148
 
 
149
  public:
 
150
    static const CodePosition MAX;
 
151
    static const CodePosition MIN;
 
152
 
 
153
    // This is the half of the instruction this code position represents, as
 
154
    // described in the huge comment above.
 
155
    enum SubPosition {
 
156
        INPUT,
 
157
        OUTPUT
 
158
    };
 
159
 
 
160
    MOZ_CONSTEXPR CodePosition() : bits_(0)
 
161
    { }
 
162
 
 
163
    CodePosition(uint32_t instruction, SubPosition where) {
 
164
        JS_ASSERT(instruction < 0x80000000u);
 
165
        JS_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where);
 
166
        bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where;
 
167
    }
 
168
 
 
169
    uint32_t ins() const {
 
170
        return bits_ >> INSTRUCTION_SHIFT;
 
171
    }
 
172
 
 
173
    uint32_t pos() const {
 
174
        return bits_;
 
175
    }
 
176
 
 
177
    SubPosition subpos() const {
 
178
        return (SubPosition)(bits_ & SUBPOSITION_MASK);
 
179
    }
 
180
 
 
181
    bool operator <(const CodePosition &other) const {
 
182
        return bits_ < other.bits_;
 
183
    }
 
184
 
 
185
    bool operator <=(const CodePosition &other) const {
 
186
        return bits_ <= other.bits_;
 
187
    }
 
188
 
 
189
    bool operator !=(const CodePosition &other) const {
 
190
        return bits_ != other.bits_;
 
191
    }
 
192
 
 
193
    bool operator ==(const CodePosition &other) const {
 
194
        return bits_ == other.bits_;
 
195
    }
 
196
 
 
197
    bool operator >(const CodePosition &other) const {
 
198
        return bits_ > other.bits_;
 
199
    }
 
200
 
 
201
    bool operator >=(const CodePosition &other) const {
 
202
        return bits_ >= other.bits_;
 
203
    }
 
204
 
 
205
    CodePosition previous() const {
 
206
        JS_ASSERT(*this != MIN);
 
207
        return CodePosition(bits_ - 1);
 
208
    }
 
209
    CodePosition next() const {
 
210
        JS_ASSERT(*this != MAX);
 
211
        return CodePosition(bits_ + 1);
 
212
    }
 
213
};
 
214
 
 
215
// Structure to track moves inserted before or after an instruction.
 
216
class InstructionData
 
217
{
 
218
    LInstruction *ins_;
 
219
    LBlock *block_;
 
220
    LMoveGroup *inputMoves_;
 
221
    LMoveGroup *movesAfter_;
 
222
 
 
223
  public:
 
224
    void init(LInstruction *ins, LBlock *block) {
 
225
        JS_ASSERT(!ins_);
 
226
        JS_ASSERT(!block_);
 
227
        ins_ = ins;
 
228
        block_ = block;
 
229
    }
 
230
    LInstruction *ins() const {
 
231
        return ins_;
 
232
    }
 
233
    LBlock *block() const {
 
234
        return block_;
 
235
    }
 
236
    void setInputMoves(LMoveGroup *moves) {
 
237
        inputMoves_ = moves;
 
238
    }
 
239
    LMoveGroup *inputMoves() const {
 
240
        return inputMoves_;
 
241
    }
 
242
    void setMovesAfter(LMoveGroup *moves) {
 
243
        movesAfter_ = moves;
 
244
    }
 
245
    LMoveGroup *movesAfter() const {
 
246
        return movesAfter_;
 
247
    }
 
248
};
 
249
 
 
250
// Structure to track all moves inserted next to instructions in a graph.
 
251
class InstructionDataMap
 
252
{
 
253
    InstructionData *insData_;
 
254
    uint32_t numIns_;
 
255
 
 
256
  public:
 
257
    InstructionDataMap()
 
258
      : insData_(NULL),
 
259
        numIns_(0)
 
260
    { }
 
261
 
 
262
    bool init(MIRGenerator *gen, uint32_t numInstructions) {
 
263
        insData_ = gen->allocate<InstructionData>(numInstructions);
 
264
        numIns_ = numInstructions;
 
265
        if (!insData_)
 
266
            return false;
 
267
        memset(insData_, 0, sizeof(InstructionData) * numInstructions);
 
268
        return true;
 
269
    }
 
270
 
 
271
    InstructionData &operator[](const CodePosition &pos) {
 
272
        JS_ASSERT(pos.ins() < numIns_);
 
273
        return insData_[pos.ins()];
 
274
    }
 
275
    InstructionData &operator[](LInstruction *ins) {
 
276
        JS_ASSERT(ins->id() < numIns_);
 
277
        return insData_[ins->id()];
 
278
    }
 
279
    InstructionData &operator[](uint32_t ins) {
 
280
        JS_ASSERT(ins < numIns_);
 
281
        return insData_[ins];
 
282
    }
 
283
};
 
284
 
 
285
// Common superclass for register allocators.
 
286
class RegisterAllocator
 
287
{
 
288
  protected:
 
289
    // Context
 
290
    MIRGenerator *mir;
 
291
    LIRGenerator *lir;
 
292
    LIRGraph &graph;
 
293
 
 
294
    // Pool of all registers that should be considered allocateable
 
295
    RegisterSet allRegisters_;
 
296
 
 
297
    // Computed data
 
298
    InstructionDataMap insData;
 
299
 
 
300
  public:
 
301
    RegisterAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
 
302
      : mir(mir),
 
303
        lir(lir),
 
304
        graph(graph),
 
305
        allRegisters_(RegisterSet::All())
 
306
    {
 
307
        if (FramePointer != InvalidReg && lir->mir()->instrumentedProfiling())
 
308
            allRegisters_.take(AnyRegister(FramePointer));
 
309
#if defined(JS_CPU_X64)
 
310
        if (mir->compilingAsmJS())
 
311
            allRegisters_.take(AnyRegister(HeapReg));
 
312
#elif defined(JS_CPU_ARM)
 
313
        if (mir->compilingAsmJS()) {
 
314
            allRegisters_.take(AnyRegister(HeapReg));
 
315
            allRegisters_.take(AnyRegister(GlobalReg));
 
316
            allRegisters_.take(AnyRegister(NANReg));
 
317
        }
 
318
#endif
 
319
    }
 
320
 
 
321
  protected:
 
322
    bool init();
 
323
 
 
324
    CodePosition outputOf(uint32_t pos) const {
 
325
        return CodePosition(pos, CodePosition::OUTPUT);
 
326
    }
 
327
    CodePosition outputOf(const LInstruction *ins) const {
 
328
        return CodePosition(ins->id(), CodePosition::OUTPUT);
 
329
    }
 
330
    CodePosition inputOf(uint32_t pos) const {
 
331
        return CodePosition(pos, CodePosition::INPUT);
 
332
    }
 
333
    CodePosition inputOf(const LInstruction *ins) const {
 
334
        return CodePosition(ins->id(), CodePosition::INPUT);
 
335
    }
 
336
 
 
337
    LMoveGroup *getInputMoveGroup(uint32_t ins);
 
338
    LMoveGroup *getMoveGroupAfter(uint32_t ins);
 
339
 
 
340
    LMoveGroup *getInputMoveGroup(CodePosition pos) {
 
341
        return getInputMoveGroup(pos.ins());
 
342
    }
 
343
    LMoveGroup *getMoveGroupAfter(CodePosition pos) {
 
344
        return getMoveGroupAfter(pos.ins());
 
345
    }
 
346
 
 
347
    size_t findFirstNonCallSafepoint(CodePosition from) const
 
348
    {
 
349
        size_t i = 0;
 
350
        for (; i < graph.numNonCallSafepoints(); i++) {
 
351
            const LInstruction *ins = graph.getNonCallSafepoint(i);
 
352
            if (from <= inputOf(ins))
 
353
                break;
 
354
        }
 
355
        return i;
 
356
    }
 
357
};
 
358
 
 
359
} // namespace jit
 
360
} // namespace js
 
361
 
 
362
#endif /* jit_RegisterAllocator_h */