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
40namespace JSC { namespace DFG {
41
42namespace DFGIntegerCheckCombiningPhaseInternal {
43static const bool verbose = false;
44}
45
46class IntegerCheckCombiningPhase : public Phase {
47public:
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
174private:
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
389bool performIntegerCheckCombining(Graph& graph)
390{
391 return runPhase<IntegerCheckCombiningPhase>(graph);
392}
393
394} } // namespace JSC::DFG
395
396#endif // ENABLE(DFG_JIT)
397
398