1/*
2 * Copyright (C) 2014 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "DFGIntegerCheckCombiningPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGGraph.h"
32#include "DFGInsertionSet.h"
33#include "DFGPhase.h"
34#include "DFGPredictionPropagationPhase.h"
35#include "DFGVariableAccessDataDump.h"
36#include "JSCInlines.h"
37#include <unordered_map>
38#include <wtf/HashMethod.h>
39
40namespace JSC { namespace DFG {
41
42namespace {
43
44static const bool verbose = false;
45
46enum RangeKind {
47    InvalidRangeKind,
48
49    // This means we did ArithAdd with CheckOverflow.
50    Addition,
51
52    // This means we did CheckInBounds on some length.
53    ArrayBounds
54};
55
56struct RangeKey {
57    RangeKey()
58        : m_kind(InvalidRangeKind)
59        , m_key(nullptr)
60    {
61    }
62
63    static RangeKey addition(Edge edge)
64    {
65        RangeKey result;
66        result.m_kind = Addition;
67        result.m_source = edge.sanitized();
68        result.m_key = 0;
69        return result;
70    }
71
72    static RangeKey arrayBounds(Edge edge, Node* key)
73    {
74        RangeKey result;
75        result.m_kind = ArrayBounds;
76        result.m_source = edge.sanitized();
77        result.m_key = key;
78        return result;
79    }
80
81    bool operator!() const { return m_kind == InvalidRangeKind; }
82
83    unsigned hash() const
84    {
85        return m_kind + m_source.hash() + PtrHash<Node*>::hash(m_key);
86    }
87
88    bool operator==(const RangeKey& other) const
89    {
90        return m_kind == other.m_kind
91            && m_source == other.m_source
92            && m_key == other.m_key;
93    }
94
95    void dump(PrintStream& out) const
96    {
97        switch (m_kind) {
98        case InvalidRangeKind:
99            out.print("InvalidRangeKind(");
100            break;
101        case Addition:
102            out.print("Addition(");
103            break;
104        case ArrayBounds:
105            out.print("ArrayBounds(");
106            break;
107        }
108        out.print(m_source, ", ", m_key, ")");
109    }
110
111    RangeKind m_kind;
112    Edge m_source;
113    Node* m_key;
114};
115
116struct RangeKeyAndAddend {
117    RangeKeyAndAddend()
118        : m_addend(0)
119    {
120    }
121
122    RangeKeyAndAddend(RangeKey key, int32_t addend)
123        : m_key(key)
124        , m_addend(addend)
125    {
126    }
127
128    bool operator!() const { return !m_key && !m_addend; }
129
130    void dump(PrintStream& out) const
131    {
132        out.print(m_key, " + ", m_addend);
133    }
134
135    RangeKey m_key;
136    int32_t m_addend;
137};
138
139struct Range {
140    Range()
141        : m_minBound(0)
142        , m_maxBound(0)
143        , m_count(0)
144        , m_hoisted(false)
145    {
146    }
147
148    void dump(PrintStream& out) const
149    {
150        out.print("(", m_minBound, " @", m_minOrigin, ") .. (", m_maxBound, " @", m_maxOrigin, "), count = ", m_count, ", hoisted = ", m_hoisted);
151    }
152
153    int32_t m_minBound;
154    CodeOrigin m_minOrigin;
155    int32_t m_maxBound;
156    CodeOrigin m_maxOrigin;
157    unsigned m_count; // If this is zero then the bounds won't necessarily make sense.
158    bool m_hoisted;
159};
160
161} // anonymous namespace
162
163class IntegerCheckCombiningPhase : public Phase {
164public:
165    IntegerCheckCombiningPhase(Graph& graph)
166        : Phase(graph, "integer check combining")
167        , m_insertionSet(graph)
168    {
169    }
170
171    bool run()
172    {
173        ASSERT(m_graph.m_form == SSA);
174
175        m_changed = false;
176
177        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
178            handleBlock(blockIndex);
179
180        return m_changed;
181    }
182
183private:
184    void handleBlock(BlockIndex blockIndex)
185    {
186        BasicBlock* block = m_graph.block(blockIndex);
187        if (!block)
188            return;
189
190        m_map.clear();
191
192        // First we collect Ranges. If operations within the range have enough redundancy,
193        // we hoist. And then we remove additions and checks that fall within the max range.
194
195        for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
196            Node* node = block->at(nodeIndex);
197            RangeKeyAndAddend data = rangeKeyAndAddend(node);
198            if (verbose)
199                dataLog("For ", node, ": ", data, "\n");
200            if (!data)
201                continue;
202
203            Range& range = m_map[data.m_key];
204            if (verbose)
205                dataLog("    Range: ", range, "\n");
206            if (range.m_count) {
207                if (data.m_addend > range.m_maxBound) {
208                    range.m_maxBound = data.m_addend;
209                    range.m_maxOrigin = node->origin.semantic;
210                } else if (data.m_addend < range.m_minBound) {
211                    range.m_minBound = data.m_addend;
212                    range.m_minOrigin = node->origin.semantic;
213                }
214            } else {
215                range.m_maxBound = data.m_addend;
216                range.m_minBound = data.m_addend;
217                range.m_minOrigin = node->origin.semantic;
218                range.m_maxOrigin = node->origin.semantic;
219            }
220            range.m_count++;
221            if (verbose)
222                dataLog("    New range: ", range, "\n");
223        }
224
225        for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
226            Node* node = block->at(nodeIndex);
227            RangeKeyAndAddend data = rangeKeyAndAddend(node);
228            if (!data)
229                continue;
230            Range range = m_map[data.m_key];
231            if (!isValid(data.m_key, range))
232                continue;
233
234            // Do the hoisting.
235            if (!range.m_hoisted) {
236                switch (data.m_key.m_kind) {
237                case Addition: {
238                    if (range.m_minBound < 0) {
239                        insertMustAdd(
240                            nodeIndex, NodeOrigin(range.m_minOrigin, node->origin.forExit),
241                            data.m_key.m_source, range.m_minBound);
242                    }
243                    if (range.m_maxBound > 0) {
244                        insertMustAdd(
245                            nodeIndex, NodeOrigin(range.m_maxOrigin, node->origin.forExit),
246                            data.m_key.m_source, range.m_maxBound);
247                    }
248                    break;
249                }
250
251                case ArrayBounds: {
252                    Node* minNode;
253                    Node* maxNode;
254
255                    if (!data.m_key.m_source) {
256                        minNode = 0;
257                        maxNode = m_insertionSet.insertConstant(
258                            nodeIndex, range.m_maxOrigin, jsNumber(range.m_maxBound));
259                    } else {
260                        minNode = insertAdd(
261                            nodeIndex, NodeOrigin(range.m_minOrigin, node->origin.forExit),
262                            data.m_key.m_source, range.m_minBound, Arith::Unchecked);
263                        maxNode = insertAdd(
264                            nodeIndex, NodeOrigin(range.m_maxOrigin, node->origin.forExit),
265                            data.m_key.m_source, range.m_maxBound, Arith::Unchecked);
266                    }
267
268                    if (minNode) {
269                        m_insertionSet.insertNode(
270                            nodeIndex, SpecNone, CheckInBounds, node->origin,
271                            Edge(minNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
272                    }
273                    m_insertionSet.insertNode(
274                        nodeIndex, SpecNone, CheckInBounds, node->origin,
275                        Edge(maxNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
276                    break;
277                }
278
279                default:
280                    RELEASE_ASSERT_NOT_REACHED();
281                }
282
283                m_changed = true;
284                m_map[data.m_key].m_hoisted = true;
285            }
286
287            // Do the elimination.
288            switch (data.m_key.m_kind) {
289            case Addition:
290                node->setArithMode(Arith::Unchecked);
291                m_changed = true;
292                break;
293
294            case ArrayBounds:
295                node->convertToPhantom();
296                m_changed = true;
297                break;
298
299            default:
300                RELEASE_ASSERT_NOT_REACHED();
301            }
302        }
303
304        m_insertionSet.execute(block);
305    }
306
307    RangeKeyAndAddend rangeKeyAndAddend(Node* node)
308    {
309        switch (node->op()) {
310        case ArithAdd: {
311            if (node->arithMode() != Arith::CheckOverflow
312                && node->arithMode() != Arith::CheckOverflowAndNegativeZero)
313                break;
314            if (!m_graph.isInt32Constant(node->child2().node()))
315                break;
316            return RangeKeyAndAddend(
317                RangeKey::addition(node->child1()),
318                m_graph.valueOfInt32Constant(node->child2().node()));
319        }
320
321        case CheckInBounds: {
322            Edge source;
323            int32_t addend;
324            Node* key = node->child2().node();
325
326            Edge index = node->child1();
327
328            if (m_graph.isInt32Constant(index.node())) {
329                source = Edge();
330                addend = m_graph.valueOfInt32Constant(index.node());
331            } else if (
332                index->op() == ArithAdd
333                && index->isBinaryUseKind(Int32Use)
334                && m_graph.isInt32Constant(index->child2().node())) {
335                source = index->child1();
336                addend = m_graph.valueOfInt32Constant(index->child2().node());
337            } else {
338                source = index;
339                addend = 0;
340            }
341
342            return RangeKeyAndAddend(RangeKey::arrayBounds(source, key), addend);
343        }
344
345        default:
346            break;
347        }
348
349        return RangeKeyAndAddend();
350    }
351
352    bool isValid(const RangeKey& key, const Range& range)
353    {
354        if (range.m_count < 2)
355            return false;
356
357        switch (key.m_kind) {
358        case ArrayBounds:
359            return (range.m_maxBound - range.m_minBound) >= 0;
360
361        default:
362            return true;
363        }
364    }
365
366    Node* insertAdd(
367        unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend,
368        Arith::Mode arithMode = Arith::CheckOverflow)
369    {
370        if (!addend)
371            return source.node();
372        return m_insertionSet.insertNode(
373            nodeIndex, source->prediction(), source->result(),
374            ArithAdd, origin, OpInfo(arithMode), source,
375            m_insertionSet.insertConstantForUse(
376                nodeIndex, origin, jsNumber(addend), source.useKind()));
377    }
378
379    Node* insertMustAdd(
380        unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend)
381    {
382        Node* result = insertAdd(nodeIndex, origin, source, addend);
383        m_insertionSet.insertNode(
384            nodeIndex, SpecNone, HardPhantom, origin, result->defaultEdge());
385        return result;
386    }
387
388    typedef std::unordered_map<RangeKey, Range, HashMethod<RangeKey>> RangeMap;
389    RangeMap m_map;
390
391    InsertionSet m_insertionSet;
392    bool m_changed;
393};
394
395bool performIntegerCheckCombining(Graph& graph)
396{
397    SamplingRegion samplingRegion("DFG Integer Check Combining Phase");
398    return runPhase<IntegerCheckCombiningPhase>(graph);
399}
400
401} } // namespace JSC::DFG
402
403#endif // ENABLE(DFG_JIT)
404
405