The DFG Integer Check Combining phase should force an OSR exit for CheckInBounds...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGIntegerCheckCombiningPhase.cpp
1 /*
2  * Copyright (C) 2014-2017 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
40 namespace JSC { namespace DFG {
41
42 namespace {
43
44 static const bool verbose = false;
45
46 enum 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
56 struct 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         if (m_source)
109             out.print(m_source);
110         else
111             out.print("null");
112         out.print(", ");
113         if (m_key)
114             out.print(m_key);
115         else
116             out.print("null");
117         out.print(")");
118     }
119     
120     RangeKind m_kind;
121     Edge m_source;
122     Node* m_key;
123 };
124
125 struct RangeKeyAndAddend {
126     RangeKeyAndAddend()
127         : m_addend(0)
128     {
129     }
130     
131     RangeKeyAndAddend(RangeKey key, int32_t addend)
132         : m_key(key)
133         , m_addend(addend)
134     {
135     }
136     
137     bool operator!() const { return !m_key && !m_addend; }
138     
139     void dump(PrintStream& out) const
140     {
141         out.print(m_key, " + ", m_addend);
142     }
143     
144     RangeKey m_key;
145     int32_t m_addend;
146 };
147
148 struct Range {
149     Range()
150         : m_minBound(0)
151         , m_maxBound(0)
152         , m_count(0)
153         , m_hoisted(false)
154     {
155     }
156     
157     void dump(PrintStream& out) const
158     {
159         out.print("(", m_minBound, " @", m_minOrigin, ") .. (", m_maxBound, " @", m_maxOrigin, "), count = ", m_count, ", hoisted = ", m_hoisted);
160     }
161     
162     int32_t m_minBound;
163     CodeOrigin m_minOrigin;
164     int32_t m_maxBound;
165     CodeOrigin m_maxOrigin;
166     unsigned m_count; // If this is zero then the bounds won't necessarily make sense.
167     bool m_hoisted;
168 };
169
170 } // anonymous namespace
171
172 class IntegerCheckCombiningPhase : public Phase {
173 public:
174     IntegerCheckCombiningPhase(Graph& graph)
175         : Phase(graph, "integer check combining")
176         , m_insertionSet(graph)
177     {
178     }
179     
180     bool run()
181     {
182         ASSERT(m_graph.m_form == SSA);
183         
184         m_changed = false;
185         
186         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
187             handleBlock(blockIndex);
188         
189         return m_changed;
190     }
191
192 private:
193     void handleBlock(BlockIndex blockIndex)
194     {
195         BasicBlock* block = m_graph.block(blockIndex);
196         if (!block)
197             return;
198         
199         m_map.clear();
200         
201         // First we collect Ranges. If operations within the range have enough redundancy,
202         // we hoist. And then we remove additions and checks that fall within the max range.
203         
204         for (auto* node : *block) {
205             RangeKeyAndAddend data = rangeKeyAndAddend(node);
206             if (verbose)
207                 dataLog("For ", node, ": ", data, "\n");
208             if (!data)
209                 continue;
210             
211             Range& range = m_map[data.m_key];
212             if (verbose)
213                 dataLog("    Range: ", range, "\n");
214             if (range.m_count) {
215                 if (data.m_addend > range.m_maxBound) {
216                     range.m_maxBound = data.m_addend;
217                     range.m_maxOrigin = node->origin.semantic;
218                 } else if (data.m_addend < range.m_minBound) {
219                     range.m_minBound = data.m_addend;
220                     range.m_minOrigin = node->origin.semantic;
221                 }
222             } else {
223                 range.m_maxBound = data.m_addend;
224                 range.m_minBound = data.m_addend;
225                 range.m_minOrigin = node->origin.semantic;
226                 range.m_maxOrigin = node->origin.semantic;
227             }
228             range.m_count++;
229             if (verbose)
230                 dataLog("    New range: ", range, "\n");
231         }
232         
233         for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
234             Node* node = block->at(nodeIndex);
235             RangeKeyAndAddend data = rangeKeyAndAddend(node);
236             if (!data)
237                 continue;
238             Range range = m_map[data.m_key];
239             if (!isValid(data.m_key, range))
240                 continue;
241             
242             // Do the hoisting.
243             if (!range.m_hoisted) {
244                 NodeOrigin minOrigin = node->origin.withSemantic(range.m_minOrigin);
245                 NodeOrigin maxOrigin = node->origin.withSemantic(range.m_maxOrigin);
246                 
247                 switch (data.m_key.m_kind) {
248                 case Addition: {
249                     if (range.m_minBound < 0)
250                         insertAdd(nodeIndex, minOrigin, data.m_key.m_source, range.m_minBound);
251                     if (range.m_maxBound > 0)
252                         insertAdd(nodeIndex, maxOrigin, data.m_key.m_source, range.m_maxBound);
253                     break;
254                 }
255                 
256                 case ArrayBounds: {
257                     Node* minNode;
258                     Node* maxNode;
259                     
260                     if (!data.m_key.m_source) {
261                         // data.m_key.m_source being null means that we're comparing against int32 constants (see rangeKeyAndAddend()).
262                         // Since CheckInBounds does an unsigned comparison, if the minBound >= 0, it is also covered by the
263                         // maxBound comparison. However, if minBound < 0, then CheckInBounds should always fail its speculation check.
264                         // We'll force an OSR exit in that case.
265                         minNode = nullptr;
266                         if (range.m_minBound < 0)
267                             m_insertionSet.insertNode(nodeIndex, SpecNone, ForceOSRExit, node->origin);
268                         maxNode = m_insertionSet.insertConstant(
269                             nodeIndex, maxOrigin, jsNumber(range.m_maxBound));
270                     } else {
271                         minNode = insertAdd(
272                             nodeIndex, minOrigin, data.m_key.m_source, range.m_minBound,
273                             Arith::Unchecked);
274                         maxNode = insertAdd(
275                             nodeIndex, maxOrigin, data.m_key.m_source, range.m_maxBound,
276                             Arith::Unchecked);
277                     }
278                     
279                     if (minNode) {
280                         m_insertionSet.insertNode(
281                             nodeIndex, SpecNone, CheckInBounds, node->origin,
282                             Edge(minNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
283                     }
284                     m_insertionSet.insertNode(
285                         nodeIndex, SpecNone, CheckInBounds, node->origin,
286                         Edge(maxNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
287                     break;
288                 }
289                 
290                 default:
291                     RELEASE_ASSERT_NOT_REACHED();
292                 }
293                 
294                 m_changed = true;
295                 m_map[data.m_key].m_hoisted = true;
296             }
297             
298             // Do the elimination.
299             switch (data.m_key.m_kind) {
300             case Addition:
301                 node->setArithMode(Arith::Unchecked);
302                 m_changed = true;
303                 break;
304                 
305             case ArrayBounds:
306                 node->remove();
307                 m_changed = true;
308                 break;
309                 
310             default:
311                 RELEASE_ASSERT_NOT_REACHED();
312             }
313         }
314         
315         m_insertionSet.execute(block);
316     }
317     
318     RangeKeyAndAddend rangeKeyAndAddend(Node* node)
319     {
320         switch (node->op()) {
321         case ArithAdd: {
322             if (node->arithMode() != Arith::CheckOverflow
323                 && node->arithMode() != Arith::CheckOverflowAndNegativeZero)
324                 break;
325             if (!node->child2()->isInt32Constant())
326                 break;
327             return RangeKeyAndAddend(
328                 RangeKey::addition(node->child1()),
329                 node->child2()->asInt32());
330         }
331                 
332         case CheckInBounds: {
333             Edge source;
334             int32_t addend;
335             Node* key = node->child2().node();
336             
337             Edge index = node->child1();
338             
339             if (index->isInt32Constant()) {
340                 source = Edge();
341                 addend = index->asInt32();
342             } else if (
343                 index->op() == ArithAdd
344                 && index->isBinaryUseKind(Int32Use)
345                 && index->child2()->isInt32Constant()) {
346                 source = index->child1();
347                 addend = index->child2()->asInt32();
348             } else {
349                 source = index;
350                 addend = 0;
351             }
352             
353             return RangeKeyAndAddend(RangeKey::arrayBounds(source, key), addend);
354         }
355             
356         default:
357             break;
358         }
359         
360         return RangeKeyAndAddend();
361     }
362     
363     bool isValid(const RangeKey& key, const Range& range)
364     {
365         if (range.m_count < 2)
366             return false;
367         
368         switch (key.m_kind) {
369         case ArrayBounds: {
370             // Have to do this carefully because C++ compilers are too smart. But all we're really doing is detecting if
371             // the difference between the bounds is 2^31 or more. If it was, then we'd have to worry about wrap-around.
372             // The way we'd like to write this expression is (range.m_maxBound - range.m_minBound) >= 0, but that is a
373             // signed subtraction and compare, which allows the C++ compiler to do anything it wants in case of
374             // wrap-around.
375             uint32_t maxBound = range.m_maxBound;
376             uint32_t minBound = range.m_minBound;
377             uint32_t unsignedDifference = maxBound - minBound;
378             return !(unsignedDifference >> 31);
379         }
380             
381         default:
382             return true;
383         }
384     }
385     
386     Node* insertAdd(
387         unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend,
388         Arith::Mode arithMode = Arith::CheckOverflow)
389     {
390         if (!addend)
391             return source.node();
392         return m_insertionSet.insertNode(
393             nodeIndex, source->prediction(), source->result(),
394             ArithAdd, origin, OpInfo(arithMode), source,
395             m_insertionSet.insertConstantForUse(
396                 nodeIndex, origin, jsNumber(addend), source.useKind()));
397     }
398     
399     typedef std::unordered_map<RangeKey, Range, HashMethod<RangeKey>> RangeMap;
400     RangeMap m_map;
401     
402     InsertionSet m_insertionSet;
403     bool m_changed;
404 };
405     
406 bool performIntegerCheckCombining(Graph& graph)
407 {
408     return runPhase<IntegerCheckCombiningPhase>(graph);
409 }
410
411 } } // namespace JSC::DFG
412
413 #endif // ENABLE(DFG_JIT)
414