e1dfd2b340dca05fee99c24bd89fe5ab01d336e6
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGIntegerCheckCombiningPhase.cpp
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
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGIntegerCheckCombiningPhase.h"
31
32 #include "DFGGraph.h"
33 #include "DFGInsertionSet.h"
34 #include "DFGPhase.h"
35 #include "DFGPredictionPropagationPhase.h"
36 #include "DFGVariableAccessDataDump.h"
37 #include "JSCInlines.h"
38 #include <unordered_map>
39 #include <wtf/HashMethod.h>
40
41 namespace JSC { namespace DFG {
42
43 namespace {
44
45 static const bool verbose = false;
46
47 enum RangeKind {
48     InvalidRangeKind,
49     
50     // This means we did ArithAdd with CheckOverflow.
51     Addition,
52     
53     // This means we did CheckInBounds on some length.
54     ArrayBounds
55 };
56
57 struct RangeKey {
58     RangeKey()
59         : m_kind(InvalidRangeKind)
60         , m_key(nullptr)
61     {
62     }
63     
64     static RangeKey addition(Edge edge)
65     {
66         RangeKey result;
67         result.m_kind = Addition;
68         result.m_source = edge.sanitized();
69         result.m_key = 0;
70         return result;
71     }
72     
73     static RangeKey arrayBounds(Edge edge, Node* key)
74     {
75         RangeKey result;
76         result.m_kind = ArrayBounds;
77         result.m_source = edge.sanitized();
78         result.m_key = key;
79         return result;
80     }
81     
82     bool operator!() const { return m_kind == InvalidRangeKind; }
83     
84     unsigned hash() const
85     {
86         return m_kind + m_source.hash() + PtrHash<Node*>::hash(m_key);
87     }
88     
89     bool operator==(const RangeKey& other) const
90     {
91         return m_kind == other.m_kind
92             && m_source == other.m_source
93             && m_key == other.m_key;
94     }
95     
96     void dump(PrintStream& out) const
97     {
98         switch (m_kind) {
99         case InvalidRangeKind:
100             out.print("InvalidRangeKind(");
101             break;
102         case Addition:
103             out.print("Addition(");
104             break;
105         case ArrayBounds:
106             out.print("ArrayBounds(");
107             break;
108         }
109         out.print(m_source, ", ", m_key, ")");
110     }
111     
112     RangeKind m_kind;
113     Edge m_source;
114     Node* m_key;
115 };
116
117 struct RangeKeyAndAddend {
118     RangeKeyAndAddend()
119         : m_addend(0)
120     {
121     }
122     
123     RangeKeyAndAddend(RangeKey key, int32_t addend)
124         : m_key(key)
125         , m_addend(addend)
126     {
127     }
128     
129     bool operator!() const { return !m_key && !m_addend; }
130     
131     void dump(PrintStream& out) const
132     {
133         out.print(m_key, " + ", m_addend);
134     }
135     
136     RangeKey m_key;
137     int32_t m_addend;
138 };
139
140 struct Range {
141     Range()
142         : m_minBound(0)
143         , m_maxBound(0)
144         , m_count(0)
145         , m_hoisted(false)
146     {
147     }
148     
149     void dump(PrintStream& out) const
150     {
151         out.print("(", m_minBound, " @", m_minOrigin, ") .. (", m_maxBound, " @", m_maxOrigin, "), count = ", m_count, ", hoisted = ", m_hoisted);
152     }
153     
154     int32_t m_minBound;
155     CodeOrigin m_minOrigin;
156     int32_t m_maxBound;
157     CodeOrigin m_maxOrigin;
158     unsigned m_count; // If this is zero then the bounds won't necessarily make sense.
159     bool m_hoisted;
160 };
161
162 } // anonymous namespace
163
164 class IntegerCheckCombiningPhase : public Phase {
165 public:
166     IntegerCheckCombiningPhase(Graph& graph)
167         : Phase(graph, "integer check combining")
168         , m_insertionSet(graph)
169     {
170     }
171     
172     bool run()
173     {
174         ASSERT(m_graph.m_form == SSA);
175         
176         m_changed = false;
177         
178         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
179             handleBlock(blockIndex);
180         
181         return m_changed;
182     }
183
184 private:
185     void handleBlock(BlockIndex blockIndex)
186     {
187         BasicBlock* block = m_graph.block(blockIndex);
188         if (!block)
189             return;
190         
191         m_map.clear();
192         
193         // First we collect Ranges. If operations within the range have enough redundancy,
194         // we hoist. And then we remove additions and checks that fall within the max range.
195         
196         for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
197             Node* node = block->at(nodeIndex);
198             RangeKeyAndAddend data = rangeKeyAndAddend(node);
199             if (verbose)
200                 dataLog("For ", node, ": ", data, "\n");
201             if (!data)
202                 continue;
203             
204             Range& range = m_map[data.m_key];
205             if (verbose)
206                 dataLog("    Range: ", range, "\n");
207             if (range.m_count) {
208                 if (data.m_addend > range.m_maxBound) {
209                     range.m_maxBound = data.m_addend;
210                     range.m_maxOrigin = node->origin.semantic;
211                 } else if (data.m_addend < range.m_minBound) {
212                     range.m_minBound = data.m_addend;
213                     range.m_minOrigin = node->origin.semantic;
214                 }
215             } else {
216                 range.m_maxBound = data.m_addend;
217                 range.m_minBound = data.m_addend;
218                 range.m_minOrigin = node->origin.semantic;
219                 range.m_maxOrigin = node->origin.semantic;
220             }
221             range.m_count++;
222             if (verbose)
223                 dataLog("    New range: ", range, "\n");
224         }
225         
226         for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
227             Node* node = block->at(nodeIndex);
228             RangeKeyAndAddend data = rangeKeyAndAddend(node);
229             if (!data)
230                 continue;
231             Range range = m_map[data.m_key];
232             if (!isValid(data.m_key, range))
233                 continue;
234             
235             // Do the hoisting.
236             if (!range.m_hoisted) {
237                 switch (data.m_key.m_kind) {
238                 case Addition: {
239                     if (range.m_minBound < 0) {
240                         insertMustAdd(
241                             nodeIndex, NodeOrigin(range.m_minOrigin, node->origin.forExit),
242                             data.m_key.m_source, range.m_minBound);
243                     }
244                     if (range.m_maxBound > 0) {
245                         insertMustAdd(
246                             nodeIndex, NodeOrigin(range.m_maxOrigin, node->origin.forExit),
247                             data.m_key.m_source, range.m_maxBound);
248                     }
249                     break;
250                 }
251                 
252                 case ArrayBounds: {
253                     Node* minNode;
254                     Node* maxNode;
255                     
256                     if (!data.m_key.m_source) {
257                         minNode = 0;
258                         maxNode = m_insertionSet.insertConstant(
259                             nodeIndex, range.m_maxOrigin, jsNumber(range.m_maxBound));
260                     } else {
261                         minNode = insertAdd(
262                             nodeIndex, NodeOrigin(range.m_minOrigin, node->origin.forExit),
263                             data.m_key.m_source, range.m_minBound, Arith::Unchecked);
264                         maxNode = insertAdd(
265                             nodeIndex, NodeOrigin(range.m_maxOrigin, node->origin.forExit),
266                             data.m_key.m_source, range.m_maxBound, Arith::Unchecked);
267                     }
268                     
269                     if (minNode) {
270                         m_insertionSet.insertNode(
271                             nodeIndex, SpecNone, CheckInBounds, node->origin,
272                             Edge(minNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
273                     }
274                     m_insertionSet.insertNode(
275                         nodeIndex, SpecNone, CheckInBounds, node->origin,
276                         Edge(maxNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
277                     break;
278                 }
279                 
280                 default:
281                     RELEASE_ASSERT_NOT_REACHED();
282                 }
283                 
284                 m_changed = true;
285                 m_map[data.m_key].m_hoisted = true;
286             }
287             
288             // Do the elimination.
289             switch (data.m_key.m_kind) {
290             case Addition:
291                 node->setArithMode(Arith::Unchecked);
292                 m_changed = true;
293                 break;
294                 
295             case ArrayBounds:
296                 node->convertToPhantom();
297                 m_changed = true;
298                 break;
299                 
300             default:
301                 RELEASE_ASSERT_NOT_REACHED();
302             }
303         }
304         
305         m_insertionSet.execute(block);
306     }
307     
308     RangeKeyAndAddend rangeKeyAndAddend(Node* node)
309     {
310         switch (node->op()) {
311         case ArithAdd: {
312             if (node->arithMode() != Arith::CheckOverflow
313                 && node->arithMode() != Arith::CheckOverflowAndNegativeZero)
314                 break;
315             if (!m_graph.isInt32Constant(node->child2().node()))
316                 break;
317             return RangeKeyAndAddend(
318                 RangeKey::addition(node->child1()),
319                 m_graph.valueOfInt32Constant(node->child2().node()));
320         }
321                 
322         case CheckInBounds: {
323             Edge source;
324             int32_t addend;
325             Node* key = node->child2().node();
326             
327             Edge index = node->child1();
328             
329             if (m_graph.isInt32Constant(index.node())) {
330                 source = Edge();
331                 addend = m_graph.valueOfInt32Constant(index.node());
332             } else if (
333                 index->op() == ArithAdd
334                 && index->isBinaryUseKind(Int32Use)
335                 && m_graph.isInt32Constant(index->child2().node())) {
336                 source = index->child1();
337                 addend = m_graph.valueOfInt32Constant(index->child2().node());
338             } else {
339                 source = index;
340                 addend = 0;
341             }
342             
343             return RangeKeyAndAddend(RangeKey::arrayBounds(source, key), addend);
344         }
345                 
346         default:
347             break;
348         }
349         
350         return RangeKeyAndAddend();
351     }
352     
353     bool isValid(const RangeKey& key, const Range& range)
354     {
355         if (range.m_count < 2)
356             return false;
357         
358         switch (key.m_kind) {
359         case ArrayBounds:
360             return (range.m_maxBound - range.m_minBound) >= 0;
361             
362         default:
363             return true;
364         }
365     }
366     
367     Node* insertAdd(
368         unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend,
369         Arith::Mode arithMode = Arith::CheckOverflow)
370     {
371         if (!addend)
372             return source.node();
373         return m_insertionSet.insertNode(
374             nodeIndex, source->prediction(), ArithAdd, origin, OpInfo(arithMode),
375             source, Edge(
376                 m_insertionSet.insertConstant(nodeIndex, origin, jsNumber(addend)),
377                 source.useKind()));
378     }
379     
380     Node* insertMustAdd(
381         unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend)
382     {
383         Node* result = insertAdd(nodeIndex, origin, source, addend);
384         m_insertionSet.insertNode(
385             nodeIndex, SpecNone, HardPhantom, origin, Edge(result, UntypedUse));
386         return result;
387     }
388     
389     typedef std::unordered_map<RangeKey, Range, HashMethod<RangeKey>> RangeMap;
390     RangeMap m_map;
391     
392     InsertionSet m_insertionSet;
393     bool m_changed;
394 };
395     
396 bool performIntegerCheckCombining(Graph& graph)
397 {
398     SamplingRegion samplingRegion("DFG Integer Check Combining Phase");
399     return runPhase<IntegerCheckCombiningPhase>(graph);
400 }
401
402 } } // namespace JSC::DFG
403
404 #endif // ENABLE(DFG_JIT)
405