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