01e1e3c9239bcdc1129721887aeb2786dfe6524d
[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 (auto* node : *block) {
196             RangeKeyAndAddend data = rangeKeyAndAddend(node);
197             if (verbose)
198                 dataLog("For ", node, ": ", data, "\n");
199             if (!data)
200                 continue;
201             
202             Range& range = m_map[data.m_key];
203             if (verbose)
204                 dataLog("    Range: ", range, "\n");
205             if (range.m_count) {
206                 if (data.m_addend > range.m_maxBound) {
207                     range.m_maxBound = data.m_addend;
208                     range.m_maxOrigin = node->origin.semantic;
209                 } else if (data.m_addend < range.m_minBound) {
210                     range.m_minBound = data.m_addend;
211                     range.m_minOrigin = node->origin.semantic;
212                 }
213             } else {
214                 range.m_maxBound = data.m_addend;
215                 range.m_minBound = data.m_addend;
216                 range.m_minOrigin = node->origin.semantic;
217                 range.m_maxOrigin = node->origin.semantic;
218             }
219             range.m_count++;
220             if (verbose)
221                 dataLog("    New range: ", range, "\n");
222         }
223         
224         for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
225             Node* node = block->at(nodeIndex);
226             RangeKeyAndAddend data = rangeKeyAndAddend(node);
227             if (!data)
228                 continue;
229             Range range = m_map[data.m_key];
230             if (!isValid(data.m_key, range))
231                 continue;
232             
233             // Do the hoisting.
234             if (!range.m_hoisted) {
235                 NodeOrigin minOrigin = node->origin.withSemantic(range.m_minOrigin);
236                 NodeOrigin maxOrigin = node->origin.withSemantic(range.m_maxOrigin);
237                 
238                 switch (data.m_key.m_kind) {
239                 case Addition: {
240                     if (range.m_minBound < 0)
241                         insertAdd(nodeIndex, minOrigin, data.m_key.m_source, range.m_minBound);
242                     if (range.m_maxBound > 0)
243                         insertAdd(nodeIndex, maxOrigin, data.m_key.m_source, range.m_maxBound);
244                     break;
245                 }
246                 
247                 case ArrayBounds: {
248                     Node* minNode;
249                     Node* maxNode;
250                     
251                     if (!data.m_key.m_source) {
252                         minNode = 0;
253                         maxNode = m_insertionSet.insertConstant(
254                             nodeIndex, maxOrigin, jsNumber(range.m_maxBound));
255                     } else {
256                         minNode = insertAdd(
257                             nodeIndex, minOrigin, data.m_key.m_source, range.m_minBound,
258                             Arith::Unchecked);
259                         maxNode = insertAdd(
260                             nodeIndex, maxOrigin, data.m_key.m_source, range.m_maxBound,
261                             Arith::Unchecked);
262                     }
263                     
264                     if (minNode) {
265                         m_insertionSet.insertNode(
266                             nodeIndex, SpecNone, CheckInBounds, node->origin,
267                             Edge(minNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
268                     }
269                     m_insertionSet.insertNode(
270                         nodeIndex, SpecNone, CheckInBounds, node->origin,
271                         Edge(maxNode, Int32Use), Edge(data.m_key.m_key, Int32Use));
272                     break;
273                 }
274                 
275                 default:
276                     RELEASE_ASSERT_NOT_REACHED();
277                 }
278                 
279                 m_changed = true;
280                 m_map[data.m_key].m_hoisted = true;
281             }
282             
283             // Do the elimination.
284             switch (data.m_key.m_kind) {
285             case Addition:
286                 node->setArithMode(Arith::Unchecked);
287                 m_changed = true;
288                 break;
289                 
290             case ArrayBounds:
291                 node->remove();
292                 m_changed = true;
293                 break;
294                 
295             default:
296                 RELEASE_ASSERT_NOT_REACHED();
297             }
298         }
299         
300         m_insertionSet.execute(block);
301     }
302     
303     RangeKeyAndAddend rangeKeyAndAddend(Node* node)
304     {
305         switch (node->op()) {
306         case ArithAdd: {
307             if (node->arithMode() != Arith::CheckOverflow
308                 && node->arithMode() != Arith::CheckOverflowAndNegativeZero)
309                 break;
310             if (!node->child2()->isInt32Constant())
311                 break;
312             return RangeKeyAndAddend(
313                 RangeKey::addition(node->child1()),
314                 node->child2()->asInt32());
315         }
316                 
317         case CheckInBounds: {
318             Edge source;
319             int32_t addend;
320             Node* key = node->child2().node();
321             
322             Edge index = node->child1();
323             
324             if (index->isInt32Constant()) {
325                 source = Edge();
326                 addend = index->asInt32();
327             } else if (
328                 index->op() == ArithAdd
329                 && index->isBinaryUseKind(Int32Use)
330                 && index->child2()->isInt32Constant()) {
331                 source = index->child1();
332                 addend = index->child2()->asInt32();
333             } else {
334                 source = index;
335                 addend = 0;
336             }
337             
338             return RangeKeyAndAddend(RangeKey::arrayBounds(source, key), addend);
339         }
340             
341         default:
342             break;
343         }
344         
345         return RangeKeyAndAddend();
346     }
347     
348     bool isValid(const RangeKey& key, const Range& range)
349     {
350         if (range.m_count < 2)
351             return false;
352         
353         switch (key.m_kind) {
354         case ArrayBounds: {
355             // Have to do this carefully because C++ compilers are too smart. But all we're really doing is detecting if
356             // the difference between the bounds is 2^31 or more. If it was, then we'd have to worry about wrap-around.
357             // The way we'd like to write this expression is (range.m_maxBound - range.m_minBound) >= 0, but that is a
358             // signed subtraction and compare, which allows the C++ compiler to do anything it wants in case of
359             // wrap-around.
360             uint32_t maxBound = range.m_maxBound;
361             uint32_t minBound = range.m_minBound;
362             uint32_t unsignedDifference = maxBound - minBound;
363             return !(unsignedDifference >> 31);
364         }
365             
366         default:
367             return true;
368         }
369     }
370     
371     Node* insertAdd(
372         unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend,
373         Arith::Mode arithMode = Arith::CheckOverflow)
374     {
375         if (!addend)
376             return source.node();
377         return m_insertionSet.insertNode(
378             nodeIndex, source->prediction(), source->result(),
379             ArithAdd, origin, OpInfo(arithMode), source,
380             m_insertionSet.insertConstantForUse(
381                 nodeIndex, origin, jsNumber(addend), source.useKind()));
382     }
383     
384     typedef std::unordered_map<RangeKey, Range, HashMethod<RangeKey>> RangeMap;
385     RangeMap m_map;
386     
387     InsertionSet m_insertionSet;
388     bool m_changed;
389 };
390     
391 bool performIntegerCheckCombining(Graph& graph)
392 {
393     return runPhase<IntegerCheckCombiningPhase>(graph);
394 }
395
396 } } // namespace JSC::DFG
397
398 #endif // ENABLE(DFG_JIT)
399