summaryrefslogtreecommitdiff
path: root/js/src/jit/LICM.cpp
blob: d661a1c7d72e5884f914097c142821e86b0179f9 (plain)
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "jit/LICM.h"

#include "jit/IonAnalysis.h"
#include "jit/JitSpewer.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"

using namespace js;
using namespace js::jit;

// Test whether any instruction in the loop possiblyCalls().
static bool
LoopContainsPossibleCall(MIRGraph& graph, MBasicBlock* header, MBasicBlock* backedge)
{
    for (auto i(graph.rpoBegin(header)); ; ++i) {
        MOZ_ASSERT(i != graph.rpoEnd(), "Reached end of graph searching for blocks in loop");
        MBasicBlock* block = *i;
        if (!block->isMarked())
            continue;

        for (auto insIter(block->begin()), insEnd(block->end()); insIter != insEnd; ++insIter) {
            MInstruction* ins = *insIter;
            if (ins->possiblyCalls()) {
#ifdef JS_JITSPEW
                JitSpew(JitSpew_LICM, "    Possile call found at %s%u", ins->opName(), ins->id());
#endif
                return true;
            }
        }

        if (block == backedge)
            break;
    }
    return false;
}

// When a nested loop has no exits back into what would be its parent loop,
// MarkLoopBlocks on the parent loop doesn't mark the blocks of the nested
// loop, since they technically aren't part of the loop. However, AliasAnalysis
// currently does consider such nested loops to be part of their parent
// loops. Consequently, we can't use IsInLoop on dependency() values; we must
// test whether a dependency() is *before* the loop, even if it is not
// technically in the loop.
static bool
IsBeforeLoop(MDefinition* ins, MBasicBlock* header)
{
    return ins->block()->id() < header->id();
}

// Test whether the given instruction is inside the loop (and thus not
// loop-invariant).
static bool
IsInLoop(MDefinition* ins)
{
    return ins->block()->isMarked();
}

// Test whether the given instruction is cheap and not worth hoisting unless
// one of its users will be hoisted as well.
static bool
RequiresHoistedUse(const MDefinition* ins, bool hasCalls)
{
    if (ins->isConstantElements())
        return true;

    if (ins->isBox()) {
        MOZ_ASSERT(!ins->toBox()->input()->isBox(),
                "Box of a box could lead to unbounded recursion");
        return true;
    }

    // Integer constants are usually cheap and aren't worth hoisting on their
    // own, in general. Floating-point constants typically are worth hoisting,
    // unless they'll end up being spilled (eg. due to a call).
    if (ins->isConstant() && (!IsFloatingPointType(ins->type()) || hasCalls))
        return true;

    return false;
}

// Test whether the given instruction has any operands defined within the loop.
static bool
HasOperandInLoop(MInstruction* ins, bool hasCalls)
{
    // An instruction is only loop invariant if it and all of its operands can
    // be safely hoisted into the loop preheader.
    for (size_t i = 0, e = ins->numOperands(); i != e; ++i) {
        MDefinition* op = ins->getOperand(i);

        if (!IsInLoop(op))
            continue;

        if (RequiresHoistedUse(op, hasCalls)) {
            // Recursively test for loop invariance. Note that the recursion is
            // bounded because we require RequiresHoistedUse to be set at each
            // level.
            if (!HasOperandInLoop(op->toInstruction(), hasCalls))
                continue;
        }

        return true;
    }
    return false;
}

// Test whether the given instruction is hoistable, ignoring memory
// dependencies.
static bool
IsHoistableIgnoringDependency(MInstruction* ins, bool hasCalls)
{
    return ins->isMovable() && !ins->isEffectful() && !ins->neverHoist() &&
           !HasOperandInLoop(ins, hasCalls);
}

// Test whether the given instruction has a memory dependency inside the loop.
static bool
HasDependencyInLoop(MInstruction* ins, MBasicBlock* header)
{
    // Don't hoist if this instruction depends on a store inside the loop.
    if (MDefinition* dep = ins->dependency())
        return !IsBeforeLoop(dep, header);
    return false;
}

// Test whether the given instruction is hoistable.
static bool
IsHoistable(MInstruction* ins, MBasicBlock* header, bool hasCalls)
{
    return IsHoistableIgnoringDependency(ins, hasCalls) && !HasDependencyInLoop(ins, header);
}

// In preparation for hoisting an instruction, hoist any of its operands which
// were too cheap to hoist on their own.
static void
MoveDeferredOperands(MInstruction* ins, MInstruction* hoistPoint, bool hasCalls)
{
    // If any of our operands were waiting for a user to be hoisted, make a note
    // to hoist them.
    for (size_t i = 0, e = ins->numOperands(); i != e; ++i) {
        MDefinition* op = ins->getOperand(i);
        if (!IsInLoop(op))
            continue;
        MOZ_ASSERT(RequiresHoistedUse(op, hasCalls),
                   "Deferred loop-invariant operand is not cheap");
        MInstruction* opIns = op->toInstruction();

        // Recursively move the operands. Note that the recursion is bounded
        // because we require RequiresHoistedUse to be set at each level.
        MoveDeferredOperands(opIns, hoistPoint, hasCalls);

#ifdef JS_JITSPEW
        JitSpew(JitSpew_LICM, "    Hoisting %s%u (now that a user will be hoisted)",
                opIns->opName(), opIns->id());
#endif

        opIns->block()->moveBefore(hoistPoint, opIns);
    }
}

static void
VisitLoopBlock(MBasicBlock* block, MBasicBlock* header, MInstruction* hoistPoint, bool hasCalls)
{
    for (auto insIter(block->begin()), insEnd(block->end()); insIter != insEnd; ) {
        MInstruction* ins = *insIter++;

        if (!IsHoistable(ins, header, hasCalls)) {
#ifdef JS_JITSPEW
            if (IsHoistableIgnoringDependency(ins, hasCalls)) {
                JitSpew(JitSpew_LICM, "    %s%u isn't hoistable due to dependency on %s%u",
                        ins->opName(), ins->id(),
                        ins->dependency()->opName(), ins->dependency()->id());
            }
#endif
            continue;
        }

        // Don't hoist a cheap constant if it doesn't enable us to hoist one of
        // its uses. We want those instructions as close as possible to their
        // use, to minimize register pressure.
        if (RequiresHoistedUse(ins, hasCalls)) {
#ifdef JS_JITSPEW
            JitSpew(JitSpew_LICM, "    %s%u will be hoisted only if its users are",
                    ins->opName(), ins->id());
#endif
            continue;
        }

        // Hoist operands which were too cheap to hoist on their own.
        MoveDeferredOperands(ins, hoistPoint, hasCalls);

#ifdef JS_JITSPEW
        JitSpew(JitSpew_LICM, "    Hoisting %s%u", ins->opName(), ins->id());
#endif

        // Move the instruction to the hoistPoint.
        block->moveBefore(hoistPoint, ins);
    }
}

static void
VisitLoop(MIRGraph& graph, MBasicBlock* header)
{
    MInstruction* hoistPoint = header->loopPredecessor()->lastIns();

#ifdef JS_JITSPEW
    JitSpew(JitSpew_LICM, "  Visiting loop with header block%u, hoisting to %s%u",
            header->id(), hoistPoint->opName(), hoistPoint->id());
#endif

    MBasicBlock* backedge = header->backedge();

    // This indicates whether the loop contains calls or other things which
    // clobber most or all floating-point registers. In such loops,
    // floating-point constants should not be hoisted unless it enables further
    // hoisting.
    bool hasCalls = LoopContainsPossibleCall(graph, header, backedge);

    for (auto i(graph.rpoBegin(header)); ; ++i) {
        MOZ_ASSERT(i != graph.rpoEnd(), "Reached end of graph searching for blocks in loop");
        MBasicBlock* block = *i;
        if (!block->isMarked())
            continue;

        VisitLoopBlock(block, header, hoistPoint, hasCalls);

        if (block == backedge)
            break;
    }
}

bool
jit::LICM(MIRGenerator* mir, MIRGraph& graph)
{
    JitSpew(JitSpew_LICM, "Beginning LICM pass");

    // Iterate in RPO to visit outer loops before inner loops. We'd hoist the
    // same things either way, but outer first means we do a little less work.
    for (auto i(graph.rpoBegin()), e(graph.rpoEnd()); i != e; ++i) {
        MBasicBlock* header = *i;
        if (!header->isLoopHeader())
            continue;

        bool canOsr;
        size_t numBlocks = MarkLoopBlocks(graph, header, &canOsr);

        if (numBlocks == 0) {
            JitSpew(JitSpew_LICM, "  Loop with header block%u isn't actually a loop", header->id());
            continue;
        }

        // Hoisting out of a loop that has an entry from the OSR block in
        // addition to its normal entry is tricky. In theory we could clone
        // the instruction and insert phis.
        if (!canOsr)
            VisitLoop(graph, header);
        else
            JitSpew(JitSpew_LICM, "  Skipping loop with header block%u due to OSR", header->id());

        UnmarkLoopBlocks(graph, header);

        if (mir->shouldCancel("LICM (main loop)"))
            return false;
    }

    return true;
}