Move back primary header includes next to config.h
[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 #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         out.print(m_source, ", ", m_key, ")");
109     }
110     
111     RangeKind m_kind;
112     Edge m_source;
113     Node* m_key;
114 };
115
116 struct 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
139 struct 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
163 class IntegerCheckCombiningPhase : public Phase {
164 public:
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
183 private:
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(), ArithAdd, origin, OpInfo(arithMode),
374             source, Edge(
375                 m_insertionSet.insertConstant(nodeIndex, origin, jsNumber(addend)),
376                 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, Edge(result, UntypedUse));
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     
395 bool 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