1/*
2 * Copyright (C) 2015-2019 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 "DFGIntegerRangeOptimizationPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBlockMapInlines.h"
32#include "DFGBlockSet.h"
33#include "DFGGraph.h"
34#include "DFGInsertionSet.h"
35#include "DFGNodeFlowProjection.h"
36#include "DFGPhase.h"
37#include "DFGPredictionPropagationPhase.h"
38#include "DFGVariableAccessDataDump.h"
39#include "JSCInlines.h"
40
41namespace JSC { namespace DFG {
42
43namespace {
44
45namespace DFGIntegerRangeOptimizationPhaseInternal {
46static constexpr bool verbose = false;
47}
48const unsigned giveUpThreshold = 50;
49
50int64_t clampedSumImpl() { return 0; }
51
52template<typename... Args>
53int64_t clampedSumImpl(int left, Args... args)
54{
55 return static_cast<int64_t>(left) + clampedSumImpl(args...);
56}
57
58template<typename... Args>
59int clampedSum(Args... args)
60{
61 int64_t result = clampedSumImpl(args...);
62 return static_cast<int>(std::min(
63 static_cast<int64_t>(std::numeric_limits<int>::max()),
64 std::max(
65 static_cast<int64_t>(std::numeric_limits<int>::min()),
66 result)));
67}
68
69bool isGeneralOffset(int offset)
70{
71 return offset >= -1 && offset <= 1;
72}
73
74class Relationship {
75public:
76 enum Kind {
77 LessThan,
78 Equal,
79 NotEqual,
80 GreaterThan
81 };
82
83 // Some relationships provide more information than others. When a relationship provides more
84 // information, it is less vague.
85 static unsigned vagueness(Kind kind)
86 {
87 switch (kind) {
88 case Equal:
89 return 0;
90 case LessThan:
91 case GreaterThan:
92 return 1;
93 case NotEqual:
94 return 2;
95 }
96 RELEASE_ASSERT_NOT_REACHED();
97 return 0;
98 }
99
100 static constexpr unsigned minVagueness = 0;
101 static constexpr unsigned maxVagueness = 2;
102
103 static Kind flipped(Kind kind)
104 {
105 switch (kind) {
106 case LessThan:
107 return GreaterThan;
108 case Equal:
109 return Equal;
110 case NotEqual:
111 return NotEqual;
112 case GreaterThan:
113 return LessThan;
114 }
115 RELEASE_ASSERT_NOT_REACHED();
116 return kind;
117 }
118
119 Relationship()
120 : m_left(nullptr)
121 , m_right(nullptr)
122 , m_kind(Equal)
123 , m_offset(0)
124 {
125 }
126
127 Relationship(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
128 : m_left(left)
129 , m_right(right)
130 , m_kind(kind)
131 , m_offset(offset)
132 {
133 RELEASE_ASSERT(m_left);
134 RELEASE_ASSERT(m_right);
135 RELEASE_ASSERT(m_left != m_right);
136 }
137
138 static Relationship safeCreate(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
139 {
140 if (!left.isStillValid() || !right.isStillValid() || left == right)
141 return Relationship();
142 return Relationship(left, right, kind, offset);
143 }
144
145 explicit operator bool() const { return !!m_left; }
146
147 NodeFlowProjection left() const { return m_left; }
148 NodeFlowProjection right() const { return m_right; }
149 Kind kind() const { return m_kind; }
150 int offset() const { return m_offset; }
151
152 unsigned vagueness() const { return vagueness(kind()); }
153
154 Relationship flipped() const
155 {
156 if (!*this)
157 return Relationship();
158
159 // This should return Relationship() if -m_offset overflows. For example:
160 //
161 // @a > @b - 2**31
162 //
163 // If we flip it we get:
164 //
165 // @b < @a + 2**31
166 //
167 // Except that the sign gets flipped since it's INT_MIN:
168 //
169 // @b < @a - 2**31
170 //
171 // And that makes no sense. To see how little sense it makes, consider:
172 //
173 // @a > @zero - 2**31
174 //
175 // We would flip it to mean:
176 //
177 // @zero < @a - 2**31
178 //
179 // Which is absurd.
180
181 if (m_offset == std::numeric_limits<int>::min())
182 return Relationship();
183
184 return Relationship(m_right, m_left, flipped(m_kind), -m_offset);
185 }
186
187 Relationship inverse() const
188 {
189 if (!*this)
190 return *this;
191
192 switch (m_kind) {
193 case Equal:
194 return Relationship(m_left, m_right, NotEqual, m_offset);
195 case NotEqual:
196 return Relationship(m_left, m_right, Equal, m_offset);
197 case LessThan:
198 if (sumOverflows<int>(m_offset, -1))
199 return Relationship();
200 return Relationship(m_left, m_right, GreaterThan, m_offset - 1);
201 case GreaterThan:
202 if (sumOverflows<int>(m_offset, 1))
203 return Relationship();
204 return Relationship(m_left, m_right, LessThan, m_offset + 1);
205 }
206
207 RELEASE_ASSERT_NOT_REACHED();
208 }
209
210 bool isCanonical() const { return m_left < m_right; }
211
212 Relationship canonical() const
213 {
214 if (isCanonical())
215 return *this;
216 return flipped();
217 }
218
219 bool sameNodesAs(const Relationship& other) const
220 {
221 return m_left == other.m_left
222 && m_right == other.m_right;
223 }
224
225 bool isEquivalentTo(const Relationship& other) const
226 {
227 if (m_left != other.m_left || m_kind != other.m_kind)
228 return false;
229
230 if (*this == other)
231 return true;
232
233 if (m_right->isInt32Constant() && other.m_right->isInt32Constant())
234 return (m_right->asInt32() + m_offset) == (other.m_right->asInt32() + other.m_offset);
235 return false;
236 }
237
238 bool operator==(const Relationship& other) const
239 {
240 return sameNodesAs(other)
241 && m_kind == other.m_kind
242 && m_offset == other.m_offset;
243 }
244
245 bool operator!=(const Relationship& other) const
246 {
247 return !(*this == other);
248 }
249
250 bool operator<(const Relationship& other) const
251 {
252 if (m_left != other.m_left)
253 return m_left < other.m_left;
254 if (m_right != other.m_right)
255 return m_right < other.m_right;
256 if (m_kind != other.m_kind)
257 return m_kind < other.m_kind;
258 return m_offset < other.m_offset;
259 }
260
261 // If possible, returns a form of this relationship where the given node is the left
262 // side. Returns a null relationship if this relationship cannot say anything about this
263 // node.
264 Relationship forNode(NodeFlowProjection node) const
265 {
266 if (m_left == node)
267 return *this;
268 if (m_right == node)
269 return flipped();
270 return Relationship();
271 }
272
273 void setLeft(NodeFlowProjection left)
274 {
275 RELEASE_ASSERT(left != m_right);
276 m_left = left;
277 }
278 void setRight(NodeFlowProjection right)
279 {
280 RELEASE_ASSERT(right != m_left);
281 m_right = right;
282 }
283 bool addToOffset(int offset)
284 {
285 if (sumOverflows<int>(m_offset, offset))
286 return false;
287 m_offset += offset;
288 return true;
289 }
290
291 // Attempts to create relationships that summarize the union of this relationship and
292 // the other relationship. Relationships are returned by calling the functor with the newly
293 // created relationships. No relationships are created to indicate TOP. This is used
294 // for merging the current relationship-at-head for some pair of nodes and a new
295 // relationship-at-head being proposed by a predecessor. We wish to create a new
296 // relationship that is true whenever either of them are true, which ensuring that we don't
297 // do this forever. Anytime we create a relationship that is not equal to either of the
298 // previous ones, we will cause the analysis fixpoint to reexecute.
299 //
300 // If *this and other are identical, we just pass it to the functor.
301 //
302 // If they are different, we pick from a finite set of "general" relationships:
303 //
304 // Eq: this == other + C, where C is -1, 0, or 1.
305 // Lt: this < other + C, where C is -1, 0, or 1.
306 // Gt: this > other + C, where C is -1, 0, or 1.
307 // Ne: this != other + C, where C is -1, 0, or 1.
308 // TOP: the null relationship.
309 //
310 // Constraining C to -1,0,1 is necessary to ensure that the set of general relationships is
311 // finite. This finite set of relationships forms a pretty simple lattice where a
312 // relA->relB means "relB is more general than relA". For example, this<other+1 is more
313 // general than this==other. I'll leave it as an exercise for the reader to see that a
314 // graph between the 13 general relationships is indeed a lattice. The fact that the set of
315 // general relationships is a finite lattice ensures monotonicity of the fixpoint, since
316 // any merge over not-identical relationships returns a relationship that is closer to the
317 // TOP relationship than either of the original relationships. Here's how convergence is
318 // achieved for any pair of relationships over the same nodes:
319 //
320 // - If they are identical, then returning *this means that we won't be responsible for
321 // causing another fixpoint iteration. Once all merges reach this point, we're done.
322 //
323 // - If they are different, then we pick the most constraining of the 13 general
324 // relationships that is true if either *this or other are true. This means that if the
325 // relationships are not identical, the merged relationship will be closer to TOP than
326 // either of the originals. Returning a different relationship means that we will be
327 // responsible for the fixpoint to reloop, but we can only do this at most 13 times since
328 // that's how "deep" the general relationship lattice is.
329 //
330 // Note that C being constrained to -1,0,1 also ensures that we never have to return a
331 // combination of Lt and Gt, as in for example this<other+C && this>other-D. The only possible
332 // values of C and D where this would work are -1 and 1, but in that case we just say
333 // this==other. That said, the logic for merging two == relationships, like this==other+C ||
334 // this==other+D is to attempt to create these two relationships: this>other+min(C,D)-1 &&
335 // this<other+max(C,D)+1. But only one of these relationships will belong to the set of general
336 // relationships.
337 //
338 // Here's an example of this in action:
339 //
340 // for (var i = a; ; ++i) { }
341 //
342 // Without C being constrained to -1,0,1, we could end up looping forever: first we'd say
343 // that i==a, then we might say that i<a+2, then i<a+3, then i<a+4, etc. We won't do this
344 // because i<a+2 is not a valid general relationship: so when we merge i==a from the first
345 // iteration and i==a+1 from the second iteration, we create i>a-1 and i<a+2 but then
346 // realize that only i>a-1 is a valid general relationship. This gives us exactly what we
347 // want: a statement that i>=a.
348 //
349 // However, this may return a pair of relationships when merging relationships involving
350 // constants. For example, if given:
351 //
352 // @x == @c
353 // @x == @d
354 //
355 // where @c and @d are constants, then this may pass two relationships to the functor:
356 //
357 // @x > min(@c, @d) - 1
358 // @x < max(@c, @d) + 1
359 //
360 // This still allows for convergence, because just as when merging relationships over
361 // variables, this always picks from a set of general relationships. Hence although this may
362 // produce two relationships as a result of the merge, the total number of relationships that
363 // can be present at head of block is limited by O(graph.size^2).
364 template<typename Functor>
365 void merge(const Relationship& other, const Functor& functor) const
366 {
367 // Handle the super obvious case first.
368 if (*this == other) {
369 functor(*this);
370 return;
371 }
372
373 if (m_left != other.m_left)
374 return;
375
376 if (m_right != other.m_right) {
377 mergeConstantsImpl(other, functor);
378 return;
379 }
380
381 ASSERT(sameNodesAs(other));
382
383 // This does some interesting permutations to reduce the amount of duplicate code. For
384 // example:
385 //
386 // initially: @a != @b, @a > @b
387 // @b != @a, @b < @a
388 // @b < @a, @b != @a
389 // finally: @b != a, @b < @a
390 //
391 // Another example:
392 //
393 // initially: @a < @b, @a != @b
394 // finally: @a != @b, @a < @b
395
396 Relationship a = *this;
397 Relationship b = other;
398 bool needFlip = false;
399
400 // Get rid of GreaterThan.
401 if (a.m_kind == GreaterThan || b.m_kind == GreaterThan) {
402 a = a.flipped();
403 b = b.flipped();
404
405 // In rare cases, we might not be able to flip. Just give up on life in those
406 // cases.
407 if (!a || !b)
408 return;
409
410 needFlip = true;
411
412 // If we still have GreaterThan, then it means that we started with @a < @b and
413 // @a > @b. That's pretty much always a tautology; we don't attempt to do smart
414 // things for that case for now.
415 if (a.m_kind == GreaterThan || b.m_kind == GreaterThan)
416 return;
417 }
418
419 // Make sure that if we have a LessThan, then it's first.
420 if (b.m_kind == LessThan)
421 std::swap(a, b);
422
423 // Make sure that if we have a NotEqual, then it's first.
424 if (b.m_kind == NotEqual)
425 std::swap(a, b);
426
427 Relationship result = a.mergeImpl(b);
428 if (!result)
429 return;
430
431 if (needFlip)
432 result = result.flipped();
433
434 functor(result);
435 }
436
437 // Attempts to construct one Relationship that adequately summarizes the intersection of
438 // this and other. Returns a null relationship if the filtration should be expressed as two
439 // different relationships. Returning null is always safe because relationship lists in
440 // this phase always imply intersection. So, you could soundly skip calling this method and
441 // just put both relationships into the list. But, that could lead the fixpoint to diverge.
442 // Hence this will attempt to combine the two relationships into one as a convergence hack.
443 // In some cases, it will do something conservative. It's always safe for this to return
444 // *this, or to return other. It'll do that sometimes, mainly to accelerate convergence for
445 // things that we don't think are important enough to slow down the analysis.
446 Relationship filter(const Relationship& other) const
447 {
448 // We are only interested in merging relationships over the same nodes.
449 ASSERT(sameNodesAs(other));
450
451 if (*this == other)
452 return *this;
453
454 // From here we can assume that the two relationships are not identical. Usually we use
455 // this to assume that we have different offsets anytime that everything but the offset
456 // is identical.
457
458 // We want equality to take precedent over everything else, and we don't want multiple
459 // independent claims of equality. That would just be a contradiction. When it does
460 // happen, we will be conservative in the sense that we will pick one.
461 if (m_kind == Equal)
462 return *this;
463 if (other.m_kind == Equal)
464 return other;
465
466 // Useful helper for flipping.
467 auto filterFlipped = [&] () -> Relationship {
468 // If we cannot flip, then just conservatively return *this.
469 Relationship a = flipped();
470 Relationship b = other.flipped();
471 if (!a || !b)
472 return *this;
473 Relationship result = a.filter(b);
474 if (!result)
475 return Relationship();
476 result = result.flipped();
477 if (!result)
478 return *this;
479 return result;
480 };
481
482 if (m_kind == NotEqual) {
483 if (other.m_kind == NotEqual) {
484 // We could do something smarter here. We could even keep both NotEqual's. We
485 // would need to make sure that we correctly collapsed them when merging. But
486 // for now, we just pick one of them and hope for the best.
487 return *this;
488 }
489
490 if (other.m_kind == GreaterThan) {
491 // Implement this in terms of NotEqual.filter(LessThan).
492 return filterFlipped();
493 }
494
495 ASSERT(other.m_kind == LessThan);
496 // We have two claims:
497 // @a != @b + C
498 // @a < @b + D
499 //
500 // If C >= D, then the NotEqual is redundant.
501 // If C < D - 1, then we could keep both, but for now we just keep the LessThan.
502 // If C == D - 1, then the LessThan can be turned into:
503 //
504 // @a < @b + C
505 //
506 // Note that C == this.m_offset, D == other.m_offset.
507
508 if (m_offset == other.m_offset - 1)
509 return Relationship(m_left, m_right, LessThan, m_offset);
510
511 return other;
512 }
513
514 if (other.m_kind == NotEqual)
515 return other.filter(*this);
516
517 if (m_kind == LessThan) {
518 if (other.m_kind == LessThan) {
519 return Relationship(
520 m_left, m_right, LessThan, std::min(m_offset, other.m_offset));
521 }
522
523 ASSERT(other.m_kind == GreaterThan);
524 if (sumOverflows<int>(m_offset, -1))
525 return Relationship();
526 if (sumOverflows<int>(other.m_offset, 1))
527 return Relationship();
528 if (m_offset - 1 == other.m_offset + 1)
529 return Relationship(m_left, m_right, Equal, m_offset - 1);
530
531 return Relationship();
532 }
533
534 ASSERT(m_kind == GreaterThan);
535 return filterFlipped();
536 }
537
538 // Come up with a relationship that is the best description of this && other, provided that left() is
539 // the same and right() is a constant. Also requires that this is at least as vague as other. It may
540 // return this or it may return something else, but whatever it returns, it will have the same nodes as
541 // this. This is not automatically done by filter() because it currently only makes sense to call this
542 // during a very particular part of setOneSide().
543 Relationship filterConstant(const Relationship& other) const
544 {
545 ASSERT(m_left == other.m_left);
546 ASSERT(m_right->isInt32Constant());
547 ASSERT(other.m_right->isInt32Constant());
548 ASSERT(vagueness() >= other.vagueness());
549
550 if (vagueness() == other.vagueness())
551 return *this;
552
553 int thisRight = m_right->asInt32();
554 int otherRight = other.m_right->asInt32();
555
556 // Ignore funny business.
557 if (sumOverflows<int>(otherRight, other.m_offset))
558 return *this;
559
560 int otherEffectiveRight = otherRight + other.m_offset;
561
562 switch (other.m_kind) {
563 case Equal:
564 // Return a version of *this that is Equal to other's constant.
565 return Relationship(m_left, m_right, Equal, otherEffectiveRight - thisRight);
566
567 case LessThan:
568 case GreaterThan:
569 ASSERT(m_kind == NotEqual);
570 // We could do smart things here. But we don't currently have an example of when it would be
571 // valuable. Note that you have to be careful. We could refine NotEqual to LessThan, but only
572 // if the LessThan subsumes the NotEqual.
573 return *this;
574
575 case NotEqual:
576 RELEASE_ASSERT_NOT_REACHED();
577 return Relationship();
578 }
579
580 RELEASE_ASSERT_NOT_REACHED();
581 return Relationship();
582 }
583
584 int minValueOfLeft() const
585 {
586 if (m_left->isInt32Constant())
587 return m_left->asInt32();
588
589 if (m_kind == LessThan || m_kind == NotEqual)
590 return std::numeric_limits<int>::min();
591
592 int minRightValue = std::numeric_limits<int>::min();
593 if (m_right->isInt32Constant())
594 minRightValue = m_right->asInt32();
595
596 if (m_kind == GreaterThan)
597 return clampedSum(minRightValue, m_offset, 1);
598 ASSERT(m_kind == Equal);
599 return clampedSum(minRightValue, m_offset);
600 }
601
602 int maxValueOfLeft() const
603 {
604 if (m_left->isInt32Constant())
605 return m_left->asInt32();
606
607 if (m_kind == GreaterThan || m_kind == NotEqual)
608 return std::numeric_limits<int>::max();
609
610 int maxRightValue = std::numeric_limits<int>::max();
611 if (m_right->isInt32Constant())
612 maxRightValue = m_right->asInt32();
613
614 if (m_kind == LessThan)
615 return clampedSum(maxRightValue, m_offset, -1);
616 ASSERT(m_kind == Equal);
617 return clampedSum(maxRightValue, m_offset);
618 }
619
620 void dump(PrintStream& out) const
621 {
622 // This prints out the relationship without any whitespace, like @x<@y+42. This
623 // optimizes for the clarity of a list of relationships. It's easier to read something
624 // like [@1<@2+3, @4==@5-6] than it would be if there was whitespace inside the
625 // relationships.
626
627 if (!*this) {
628 out.print("null");
629 return;
630 }
631
632 out.print(m_left);
633 switch (m_kind) {
634 case LessThan:
635 out.print("<");
636 break;
637 case Equal:
638 out.print("==");
639 break;
640 case NotEqual:
641 out.print("!=");
642 break;
643 case GreaterThan:
644 out.print(">");
645 break;
646 }
647 out.print(m_right);
648 if (m_offset > 0)
649 out.print("+", m_offset);
650 else if (m_offset < 0)
651 out.print("-", -static_cast<int64_t>(m_offset));
652 }
653
654private:
655 Relationship mergeImpl(const Relationship& other) const
656 {
657 ASSERT(sameNodesAs(other));
658 ASSERT(m_kind != GreaterThan);
659 ASSERT(other.m_kind != GreaterThan);
660 ASSERT(*this != other);
661
662 // The purpose of this method is to guarantee that:
663 //
664 // - We avoid having more than one Relationship over the same two nodes. Therefore, if
665 // the merge could be expressed as two Relationships, we prefer to instead pick the
666 // less precise single Relationship form even if that means TOP.
667 //
668 // - If the difference between two Relationships is just the m_offset, then we create a
669 // Relationship that has an offset of -1, 0, or 1. This is an essential convergence
670 // hack. We need -1 and 1 to support <= and >=.
671
672 // From here we can assume that the two relationships are not identical. Usually we use
673 // this to assume that we have different offsets anytime that everything but the offset
674 // is identical.
675
676 if (m_kind == NotEqual) {
677 if (other.m_kind == NotEqual)
678 return Relationship(); // Different offsets, so tautology.
679
680 if (other.m_kind == Equal) {
681 if (m_offset != other.m_offset) {
682 // Saying that you might be B when you've already said that you're anything
683 // but A, where A and B are different, is a tautology. You could just say
684 // that you're anything but A. Adding "(a == b + 1)" to "(a != b + 5)" has
685 // no value.
686 return *this;
687 }
688 // Otherwise, same offsets: we're saying that you're either A or you're not
689 // equal to A.
690
691 return Relationship();
692 }
693
694 RELEASE_ASSERT(other.m_kind == LessThan);
695 // We have these claims, and we're merging them:
696 // @a != @b + C
697 // @a < @b + D
698 //
699 // If we have C == D, then the merge is clearly just the NotEqual.
700 // If we have C < D, then the merge is a tautology.
701 // If we have C > D, then we could keep both claims, but we are cheap, so we
702 // don't. We just use the NotEqual.
703
704 if (m_offset < other.m_offset)
705 return Relationship();
706
707 return *this;
708 }
709
710 if (m_kind == LessThan) {
711 if (other.m_kind == LessThan) {
712 // Figure out what offset to select to merge them. The appropriate offsets are
713 // -1, 0, or 1.
714
715 // First figure out what offset we'd like to use.
716 int bestOffset = std::max(m_offset, other.m_offset);
717
718 // We have something like @a < @b + 2. We can't represent this under the
719 // -1,0,1 rule.
720 if (isGeneralOffset(bestOffset))
721 return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
722
723 return Relationship();
724 }
725
726 // The only thing left is Equal. We would have eliminated the GreaterThan's, and
727 // if we merge LessThan and NotEqual, the NotEqual always comes first.
728 RELEASE_ASSERT(other.m_kind == Equal);
729
730 // This is the really interesting case. We have:
731 //
732 // @a < @b + C
733 //
734 // and:
735 //
736 // @a == @b + D
737 //
738 // Therefore we'd like to return:
739 //
740 // @a < @b + max(C, D + 1)
741
742 int bestOffset = std::max(m_offset, other.m_offset + 1);
743
744 // We have something like @a < @b + 2. We can't do it.
745 if (isGeneralOffset(bestOffset))
746 return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
747
748 return Relationship();
749 }
750
751 // The only thing left is Equal, since we would have gotten rid of the GreaterThan's.
752 RELEASE_ASSERT(m_kind == Equal);
753
754 // We would never see NotEqual, because those always come first. We would never
755 // see GreaterThan, because we would have eliminated those. We would never see
756 // LessThan, because those always come first.
757
758 RELEASE_ASSERT(other.m_kind == Equal);
759 // We have @a == @b + C and @a == @b + D, where C != D. Turn this into some
760 // inequality that involves a constant that is -1,0,1. Note that we will never have
761 // lessThan and greaterThan because the constants are constrained to -1,0,1. The only
762 // way for both of them to be valid is a<b+1 and a>b-1, but then we would have said
763 // a==b.
764
765 Relationship lessThan;
766 Relationship greaterThan;
767
768 int lessThanEqOffset = std::max(m_offset, other.m_offset);
769 if (lessThanEqOffset >= -2 && lessThanEqOffset <= 0) {
770 lessThan = Relationship(
771 m_left, other.m_right, LessThan, lessThanEqOffset + 1);
772
773 ASSERT(isGeneralOffset(lessThan.offset()));
774 }
775
776 int greaterThanEqOffset = std::min(m_offset, other.m_offset);
777 if (greaterThanEqOffset >= 0 && greaterThanEqOffset <= 2) {
778 greaterThan = Relationship(
779 m_left, other.m_right, GreaterThan, greaterThanEqOffset - 1);
780
781 ASSERT(isGeneralOffset(greaterThan.offset()));
782 }
783
784 if (lessThan) {
785 // Both relationships cannot be valid; see above.
786 RELEASE_ASSERT(!greaterThan);
787
788 return lessThan;
789 }
790
791 return greaterThan;
792 }
793
794 template<typename Functor>
795 void mergeConstantsImpl(const Relationship& other, const Functor& functor) const
796 {
797 ASSERT(m_left == other.m_left);
798
799 // Only deal with constant right.
800 if (!m_right->isInt32Constant() || !other.m_right->isInt32Constant())
801 return;
802
803 // What follows is a fairly conservative merge. We could tune this phase to come up with
804 // all possible inequalities between variables and constants, but we focus mainly on cheap
805 // cases for now.
806
807 // Here are some of the arrangements we can merge usefully assuming @c < @d:
808 //
809 // @x == @c || @x == @d => @x >= c && @x <= @d
810 // @x >= @c || @x <= @d => TOP
811 // @x == @c || @x != @d => @x != @d
812
813 int thisRight = m_right->asInt32();
814 int otherRight = other.m_right->asInt32();
815
816 // Ignore funny business.
817 if (sumOverflows<int>(thisRight, m_offset))
818 return;
819 if (sumOverflows<int>(otherRight, other.m_offset))
820 return;
821
822 int thisEffectiveRight = thisRight + m_offset;
823 int otherEffectiveRight = otherRight + other.m_offset;
824
825 auto makeUpper = [&] (int64_t upper) {
826 if (upper <= thisRight) {
827 // We want m_right + offset to be equal to upper. Hence we want offset to cancel
828 // with m_right. But there's more to it, since we want +1 to turn the LessThan into
829 // a LessThanOrEqual, and we want to make sure we don't end up with non-general
830 // offsets.
831 int offset = static_cast<int>(std::max(
832 static_cast<int64_t>(1) + upper - static_cast<int64_t>(thisRight),
833 static_cast<int64_t>(-1)));
834 functor(Relationship(m_left, m_right, LessThan, offset));
835 }
836 if (upper <= otherRight) {
837 int offset = static_cast<int>(std::max(
838 static_cast<int64_t>(1) + upper - static_cast<int64_t>(otherRight),
839 static_cast<int64_t>(-1)));
840 functor(Relationship(m_left, other.m_right, LessThan, offset));
841 }
842 };
843 auto makeLower = [&] (int64_t lower) {
844 if (lower >= thisRight) {
845 // We want m_right + offset to be equal to lower. Hence we want offset to cancel with
846 // m_right. But there's more to it, since we want -1 to turn the GreaterThan into a
847 // GreaterThanOrEqual, and we want to make sure we don't end up with non-general
848 // offsets.
849 int offset = static_cast<int>(std::min(
850 static_cast<int64_t>(-1) + lower - static_cast<int64_t>(thisRight),
851 static_cast<int64_t>(1)));
852 functor(Relationship(m_left, m_right, GreaterThan, offset));
853 }
854 if (lower >= otherRight) {
855 int offset = static_cast<int>(std::min(
856 static_cast<int64_t>(-1) + lower - static_cast<int64_t>(otherRight),
857 static_cast<int64_t>(1)));
858 functor(Relationship(m_left, other.m_right, GreaterThan, offset));
859 }
860 };
861
862 switch (m_kind) {
863 case Equal: {
864 switch (other.m_kind) {
865 case Equal: {
866 if (thisEffectiveRight == otherEffectiveRight) {
867 // This probably won't arise often. We can keep whichever relationship is general.
868 if (isGeneralOffset(m_offset))
869 functor(*this);
870 if (isGeneralOffset(other.m_offset))
871 functor(other);
872 return;
873 }
874
875 // What follows is the only case where a merge will create more rules than what it
876 // started with. This is fine for convergence because the LessThan/GreaterThan
877 // rules that this creates are general (i.e. have small offsets) and they never
878 // spawn more rules upon subsequent merging.
879
880 makeUpper(std::max(thisEffectiveRight, otherEffectiveRight));
881 makeLower(std::min(thisEffectiveRight, otherEffectiveRight));
882 return;
883 }
884
885 case LessThan: {
886 // Either the LessThan condition subsumes the equality, or the LessThan condition
887 // and equality merge together to create a looser LessThan condition.
888
889 // This is @x == thisEffectiveRight
890 // Other is: @x < otherEffectiveRight
891
892 // We want to create @x <= upper. Figure out the value of upper.
893 makeUpper(std::max(
894 static_cast<int64_t>(thisEffectiveRight),
895 static_cast<int64_t>(otherEffectiveRight) - 1));
896 return;
897 }
898
899 case GreaterThan: {
900 // Opposite of the LessThan case, above.
901
902 // This is: @x == thisEffectiveRight
903 // Other is: @x > otherEffectiveRight
904
905 makeLower(std::min(
906 static_cast<int64_t>(thisEffectiveRight),
907 static_cast<int64_t>(otherEffectiveRight) + 1));
908 return;
909 }
910
911 case NotEqual: {
912 // We keep the NotEqual so long as it doesn't contradict our Equal.
913 if (otherEffectiveRight == thisEffectiveRight)
914 return;
915
916 // But, we only keep the NotEqual if it is general. This simplifies reasoning about
917 // convergence: merging never introduces a new rule unless that rule is general.
918 if (!isGeneralOffset(other.m_offset))
919 return;
920
921 functor(other);
922 return;
923 } }
924
925 RELEASE_ASSERT_NOT_REACHED();
926 return;
927 }
928
929 case LessThan: {
930 switch (other.m_kind) {
931 case Equal: {
932 other.mergeConstantsImpl(*this, functor);
933 return;
934 }
935
936 case LessThan: {
937 makeUpper(std::max(
938 static_cast<int64_t>(thisEffectiveRight) - 1,
939 static_cast<int64_t>(otherEffectiveRight) - 1));
940 return;
941 }
942
943 case GreaterThan: {
944 // We have a claim that @x > @c || @x < @d. If @d > @c, this is the tautology. If
945 // @d <= @c, it's sort of uninteresting. Just ignore this.
946 return;
947 }
948
949 case NotEqual: {
950 // We have a claim that @x < @c || @x != @d. This isn't interesting.
951 return;
952 } }
953
954 RELEASE_ASSERT_NOT_REACHED();
955 return;
956 }
957
958 case GreaterThan: {
959 switch (other.m_kind) {
960 case Equal: {
961 other.mergeConstantsImpl(*this, functor);
962 return;
963 }
964
965 case LessThan: {
966 // Not interesting, see above.
967 return;
968 }
969
970 case GreaterThan: {
971 makeLower(std::min(
972 static_cast<int64_t>(thisEffectiveRight) + 1,
973 static_cast<int64_t>(otherEffectiveRight) + 1));
974 return;
975 }
976
977 case NotEqual: {
978 // Not interesting, see above.
979 return;
980 } }
981
982 RELEASE_ASSERT_NOT_REACHED();
983 return;
984 }
985
986 case NotEqual: {
987 if (other.m_kind == Equal)
988 other.mergeConstantsImpl(*this, functor);
989 return;
990 } }
991
992 RELEASE_ASSERT_NOT_REACHED();
993 }
994
995 NodeFlowProjection m_left;
996 NodeFlowProjection m_right;
997 Kind m_kind;
998 int m_offset; // This offset can be arbitrarily large.
999};
1000
1001typedef HashMap<NodeFlowProjection, Vector<Relationship>> RelationshipMap;
1002
1003class IntegerRangeOptimizationPhase : public Phase {
1004public:
1005 IntegerRangeOptimizationPhase(Graph& graph)
1006 : Phase(graph, "integer range optimization")
1007 , m_zero(nullptr)
1008 , m_relationshipsAtHead(graph)
1009 , m_insertionSet(graph)
1010 {
1011 }
1012
1013 bool run()
1014 {
1015 ASSERT(m_graph.m_form == SSA);
1016
1017 // Before we do anything, make sure that we have a zero constant at the top.
1018 for (Node* node : *m_graph.block(0)) {
1019 if (node->isInt32Constant() && !node->asInt32()) {
1020 m_zero = node;
1021 break;
1022 }
1023 }
1024 if (!m_zero) {
1025 m_zero = m_insertionSet.insertConstant(0, m_graph.block(0)->at(0)->origin, jsNumber(0));
1026 m_insertionSet.execute(m_graph.block(0));
1027 }
1028
1029 if (DFGIntegerRangeOptimizationPhaseInternal::verbose) {
1030 dataLog("Graph before integer range optimization:\n");
1031 m_graph.dump();
1032 }
1033
1034 // This performs a fixpoint over the blocks in reverse post-order. Logically, we
1035 // maintain a list of relationships at each point in the program. The list should be
1036 // read as an intersection. For example if we have {rel1, rel2, ..., relN}, you should
1037 // read this as:
1038 //
1039 // TOP && rel1 && rel2 && ... && relN
1040 //
1041 // This allows us to express things like:
1042 //
1043 // @a > @b - 42 && @a < @b + 25
1044 //
1045 // But not things like:
1046 //
1047 // @a < @b - 42 || @a > @b + 25
1048 //
1049 // We merge two lists by merging each relationship in one list with each relationship
1050 // in the other list. Merging two relationships will yield a relationship list; as with
1051 // all such lists it is an intersection. Merging relationships over different variables
1052 // always yields the empty list (i.e. TOP). This merge style is sound because if we
1053 // have:
1054 //
1055 // (A && B && C) || (D && E && F)
1056 //
1057 // Then a valid merge is just one that will return true if A, B, C are all true, or
1058 // that will return true if D, E, F are all true. Our merge style essentially does:
1059 //
1060 // (A || D) && (A || E) && (A || F) && (B || D) && (B || E) && (B || F) &&
1061 // (C || D) && (C || E) && (C || F)
1062 //
1063 // If A && B && C is true, then this returns true. If D && E && F is true, this also
1064 // returns true.
1065 //
1066 // While this appears at first like a kind of expression explosion, in practice it
1067 // isn't. The code that handles this knows that the merge of two relationships over
1068 // different variables is TOP (i.e. the empty list). For example if A above is @a < @b
1069 // and B above is @c > @d, where @a, @b, @c, and @d are different nodes, the merge will
1070 // yield nothing. In fact, the merge algorithm will skip such merges entirely because
1071 // the relationship lists are actually keyed by node.
1072 //
1073 // Note that it's always safe to drop any of relationship from the relationship list.
1074 // This merely increases the likelihood of the "expression" yielding true, i.e. being
1075 // closer to TOP. Optimizations are only performed if we can establish that the
1076 // expression implied by the relationship list is false for all of those cases where
1077 // some check would have failed.
1078 //
1079 // There is no notion of BOTTOM because we treat blocks that haven't had their
1080 // state-at-head set as a special case: we just transfer all live relationships to such
1081 // a block. After the head of a block is set, we perform the merging as above. In all
1082 // other places where we would ordinarily need BOTTOM, we approximate it by having some
1083 // non-BOTTOM relationship.
1084
1085 BlockList postOrder = m_graph.blocksInPostOrder();
1086
1087 // This loop analyzes the IR to give us m_relationshipsAtHead for each block. This
1088 // may reexecute blocks many times, but it is guaranteed to converge. The state of
1089 // the relationshipsAtHead over any pair of nodes converge monotonically towards the
1090 // TOP relationship (i.e. no relationships in the relationship list). The merge rule
1091 // when between the current relationshipsAtHead and the relationships being propagated
1092 // from a predecessor ensures monotonicity by converting disagreements into one of a
1093 // small set of "general" relationships. There are 12 such relationships, plus TOP. See
1094 // the comment above Relationship::merge() for details.
1095 bool changed = true;
1096 while (changed) {
1097 ++m_iterations;
1098 if (m_iterations >= giveUpThreshold) {
1099 // This case is not necessarily wrong but it can be a sign that this phase
1100 // does not converge. The value giveUpThreshold was chosen emperically based on
1101 // current tests and real world JS.
1102 // If you hit this case for a legitimate reason, update the giveUpThreshold
1103 // to the smallest values that converges.
1104
1105 // Do not risk holding the thread for too long since this phase is really slow.
1106 return false;
1107 }
1108
1109 changed = false;
1110 for (unsigned postOrderIndex = postOrder.size(); postOrderIndex--;) {
1111 BasicBlock* block = postOrder[postOrderIndex];
1112 DFG_ASSERT(
1113 m_graph, nullptr,
1114 block == m_graph.block(0) || m_seenBlocks.contains(block));
1115
1116 m_relationships = m_relationshipsAtHead[block];
1117
1118 for (auto* node : *block) {
1119 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1120 dataLog("Analysis: at ", node, ": ", listDump(sortedRelationships()), "\n");
1121 executeNode(node);
1122 }
1123
1124 // Now comes perhaps the most important piece of cleverness: if we Branch, and
1125 // the predicate involves some relation over integers, we propagate different
1126 // information to the taken and notTaken paths. This handles:
1127 // - Branch on int32.
1128 // - Branch on LogicalNot on int32.
1129 // - Branch on compare on int32's.
1130 // - Branch on LogicalNot of compare on int32's.
1131 Node* terminal = block->terminal();
1132 bool alreadyMerged = false;
1133 if (terminal->op() == Branch) {
1134 Relationship relationshipForTrue;
1135 BranchData* branchData = terminal->branchData();
1136
1137 bool invert = false;
1138 if (terminal->child1()->op() == LogicalNot) {
1139 terminal = terminal->child1().node();
1140 invert = true;
1141 }
1142
1143 if (terminal->child1().useKind() == Int32Use) {
1144 relationshipForTrue = Relationship::safeCreate(
1145 terminal->child1().node(), m_zero, Relationship::NotEqual, 0);
1146 } else {
1147 // FIXME: Handle CompareBelow and CompareBelowEq.
1148 Node* compare = terminal->child1().node();
1149 switch (compare->op()) {
1150 case CompareEq:
1151 case CompareStrictEq:
1152 case CompareLess:
1153 case CompareLessEq:
1154 case CompareGreater:
1155 case CompareGreaterEq: {
1156 if (!compare->isBinaryUseKind(Int32Use))
1157 break;
1158
1159 switch (compare->op()) {
1160 case CompareEq:
1161 case CompareStrictEq:
1162 relationshipForTrue = Relationship::safeCreate(
1163 compare->child1().node(), compare->child2().node(),
1164 Relationship::Equal, 0);
1165 break;
1166 case CompareLess:
1167 relationshipForTrue = Relationship::safeCreate(
1168 compare->child1().node(), compare->child2().node(),
1169 Relationship::LessThan, 0);
1170 break;
1171 case CompareLessEq:
1172 relationshipForTrue = Relationship::safeCreate(
1173 compare->child1().node(), compare->child2().node(),
1174 Relationship::LessThan, 1);
1175 break;
1176 case CompareGreater:
1177 relationshipForTrue = Relationship::safeCreate(
1178 compare->child1().node(), compare->child2().node(),
1179 Relationship::GreaterThan, 0);
1180 break;
1181 case CompareGreaterEq:
1182 relationshipForTrue = Relationship::safeCreate(
1183 compare->child1().node(), compare->child2().node(),
1184 Relationship::GreaterThan, -1);
1185 break;
1186 default:
1187 DFG_CRASH(m_graph, compare, "Invalid comparison node type");
1188 break;
1189 }
1190 break;
1191 }
1192
1193 default:
1194 break;
1195 }
1196 }
1197
1198 if (invert)
1199 relationshipForTrue = relationshipForTrue.inverse();
1200
1201 if (relationshipForTrue) {
1202 RelationshipMap forTrue = m_relationships;
1203 RelationshipMap forFalse = m_relationships;
1204
1205 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1206 dataLog("Dealing with true:\n");
1207 setRelationship(forTrue, relationshipForTrue);
1208 if (Relationship relationshipForFalse = relationshipForTrue.inverse()) {
1209 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1210 dataLog("Dealing with false:\n");
1211 setRelationship(forFalse, relationshipForFalse);
1212 }
1213
1214 changed |= mergeTo(forTrue, branchData->taken.block);
1215 changed |= mergeTo(forFalse, branchData->notTaken.block);
1216 alreadyMerged = true;
1217 }
1218 }
1219
1220 if (!alreadyMerged) {
1221 for (BasicBlock* successor : block->successors())
1222 changed |= mergeTo(m_relationships, successor);
1223 }
1224 }
1225 }
1226
1227 // Now we transform the code based on the results computed in the previous loop.
1228 changed = false;
1229 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
1230 m_relationships = m_relationshipsAtHead[block];
1231 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
1232 Node* node = block->at(nodeIndex);
1233 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1234 dataLog("Transformation: at ", node, ": ", listDump(sortedRelationships()), "\n");
1235
1236 // This ends up being pretty awkward to write because we need to decide if we
1237 // optimize by using the relationships before the operation, but we need to
1238 // call executeNode() before we optimize.
1239 switch (node->op()) {
1240 case ArithAbs: {
1241 if (node->child1().useKind() != Int32Use)
1242 break;
1243
1244 auto iter = m_relationships.find(node->child1().node());
1245 if (iter == m_relationships.end())
1246 break;
1247
1248 int minValue = std::numeric_limits<int>::min();
1249 int maxValue = std::numeric_limits<int>::max();
1250 for (Relationship relationship : iter->value) {
1251 minValue = std::max(minValue, relationship.minValueOfLeft());
1252 maxValue = std::min(maxValue, relationship.maxValueOfLeft());
1253 }
1254
1255 executeNode(block->at(nodeIndex));
1256
1257 if (minValue >= 0) {
1258 node->convertToIdentityOn(node->child1().node());
1259 changed = true;
1260 break;
1261 }
1262 bool absIsUnchecked = !shouldCheckOverflow(node->arithMode());
1263 if (maxValue < 0 || (absIsUnchecked && maxValue <= 0)) {
1264 node->convertToArithNegate();
1265 if (absIsUnchecked || minValue > std::numeric_limits<int>::min())
1266 node->setArithMode(Arith::Unchecked);
1267 changed = true;
1268 break;
1269 }
1270 if (minValue > std::numeric_limits<int>::min()) {
1271 node->setArithMode(Arith::Unchecked);
1272 changed = true;
1273 break;
1274 }
1275
1276 break;
1277 }
1278 case ArithAdd: {
1279 if (!node->isBinaryUseKind(Int32Use))
1280 break;
1281 if (node->arithMode() != Arith::CheckOverflow)
1282 break;
1283 if (!node->child2()->isInt32Constant())
1284 break;
1285
1286 auto iter = m_relationships.find(node->child1().node());
1287 if (iter == m_relationships.end())
1288 break;
1289
1290 int minValue = std::numeric_limits<int>::min();
1291 int maxValue = std::numeric_limits<int>::max();
1292 for (Relationship relationship : iter->value) {
1293 minValue = std::max(minValue, relationship.minValueOfLeft());
1294 maxValue = std::min(maxValue, relationship.maxValueOfLeft());
1295 }
1296
1297 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1298 dataLog(" minValue = ", minValue, ", maxValue = ", maxValue, "\n");
1299
1300 if (sumOverflows<int>(minValue, node->child2()->asInt32()) ||
1301 sumOverflows<int>(maxValue, node->child2()->asInt32()))
1302 break;
1303
1304 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1305 dataLog(" It's in bounds.\n");
1306
1307 executeNode(block->at(nodeIndex));
1308 node->setArithMode(Arith::Unchecked);
1309 changed = true;
1310 break;
1311 }
1312
1313 case CheckInBounds: {
1314 auto iter = m_relationships.find(node->child1().node());
1315 if (iter == m_relationships.end())
1316 break;
1317
1318 bool nonNegative = false;
1319 bool lessThanLength = false;
1320 for (Relationship relationship : iter->value) {
1321 if (relationship.minValueOfLeft() >= 0)
1322 nonNegative = true;
1323
1324 if (relationship.right() == node->child2().node()) {
1325 if (relationship.kind() == Relationship::Equal
1326 && relationship.offset() < 0)
1327 lessThanLength = true;
1328
1329 if (relationship.kind() == Relationship::LessThan
1330 && relationship.offset() <= 0)
1331 lessThanLength = true;
1332 }
1333 }
1334
1335 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1336 dataLogLn("CheckInBounds ", node, " has: ", nonNegative, " ", lessThanLength);
1337
1338 if (nonNegative && lessThanLength) {
1339 executeNode(block->at(nodeIndex));
1340 // We just need to make sure we are a value-producing node.
1341 node->convertToIdentityOn(node->child1().node());
1342 changed = true;
1343 }
1344 break;
1345 }
1346
1347 case GetByVal: {
1348 if (node->arrayMode().type() != Array::Undecided)
1349 break;
1350
1351 auto iter = m_relationships.find(m_graph.varArgChild(node, 1).node());
1352 if (iter == m_relationships.end())
1353 break;
1354
1355 int minValue = std::numeric_limits<int>::min();
1356 for (Relationship relationship : iter->value)
1357 minValue = std::max(minValue, relationship.minValueOfLeft());
1358
1359 if (minValue < 0)
1360 break;
1361
1362 executeNode(block->at(nodeIndex));
1363 m_graph.convertToConstant(node, jsUndefined());
1364 changed = true;
1365 break;
1366 }
1367
1368 default:
1369 break;
1370 }
1371
1372 executeNode(block->at(nodeIndex));
1373 }
1374 }
1375
1376 return changed;
1377 }
1378
1379private:
1380 void executeNode(Node* node)
1381 {
1382 switch (node->op()) {
1383 case CheckInBounds: {
1384 setRelationship(Relationship::safeCreate(node->child1().node(), node->child2().node(), Relationship::LessThan));
1385 setRelationship(Relationship::safeCreate(node->child1().node(), m_zero, Relationship::GreaterThan, -1));
1386 break;
1387 }
1388
1389 case ArithAbs: {
1390 if (node->child1().useKind() != Int32Use)
1391 break;
1392 setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
1393 break;
1394 }
1395
1396 case ArithAdd: {
1397 // We're only interested in int32 additions and we currently only know how to
1398 // handle the non-wrapping ones.
1399 if (!node->isBinaryUseKind(Int32Use))
1400 break;
1401
1402 // FIXME: We could handle the unchecked arithmetic case. We just do it don't right
1403 // now.
1404 if (node->arithMode() != Arith::CheckOverflow)
1405 break;
1406
1407 // Handle add: @value + constant.
1408 if (!node->child2()->isInt32Constant())
1409 break;
1410
1411 int offset = node->child2()->asInt32();
1412
1413 // We add a relationship for @add == @value + constant, and then we copy the
1414 // relationships for @value. This gives us a one-deep view of @value's existing
1415 // relationships, which matches the one-deep search in setRelationship().
1416
1417 setRelationship(
1418 Relationship(node, node->child1().node(), Relationship::Equal, offset));
1419
1420 auto iter = m_relationships.find(node->child1().node());
1421 if (iter != m_relationships.end()) {
1422 Vector<Relationship> toAdd;
1423 for (Relationship relationship : iter->value) {
1424 // We have:
1425 // add: ArithAdd(@x, C)
1426 // @x op @y + D
1427 //
1428 // The following certainly holds:
1429 // @x == @add - C
1430 //
1431 // Which allows us to substitute:
1432 // @add - C op @y + D
1433 //
1434 // And then carry the C over:
1435 // @add op @y + D + C
1436
1437 Relationship newRelationship = relationship;
1438 ASSERT(newRelationship.left() == node->child1().node());
1439
1440 if (newRelationship.right() == node)
1441 continue;
1442 newRelationship.setLeft(node);
1443 if (newRelationship.addToOffset(offset))
1444 toAdd.append(newRelationship);
1445 }
1446 for (Relationship relationship : toAdd)
1447 setRelationship(relationship, 0);
1448 }
1449
1450 // Now we want to establish that both the input and the output of the addition are
1451 // within a particular range of integers.
1452
1453 if (offset > 0) {
1454 // If we have "add: @value + 1" then we know that @value <= max - 1, i.e. that
1455 // @value < max.
1456 if (!sumOverflows<int>(std::numeric_limits<int>::max(), -offset, 1)) {
1457 setRelationship(
1458 Relationship::safeCreate(
1459 node->child1().node(), m_zero, Relationship::LessThan,
1460 std::numeric_limits<int>::max() - offset + 1),
1461 0);
1462 }
1463
1464 // If we have "add: @value + 1" then we know that @add >= min + 1, i.e. that
1465 // @add > min.
1466 if (!sumOverflows<int>(std::numeric_limits<int>::min(), offset, -1)) {
1467 setRelationship(
1468 Relationship(
1469 node, m_zero, Relationship::GreaterThan,
1470 std::numeric_limits<int>::min() + offset - 1),
1471 0);
1472 }
1473 }
1474
1475 if (offset < 0 && offset != std::numeric_limits<int>::min()) {
1476 // If we have "add: @value - 1" then we know that @value >= min + 1, i.e. that
1477 // @value > min.
1478 if (!sumOverflows<int>(std::numeric_limits<int>::min(), offset, -1)) {
1479 setRelationship(
1480 Relationship::safeCreate(
1481 node->child1().node(), m_zero, Relationship::GreaterThan,
1482 std::numeric_limits<int>::min() + offset - 1),
1483 0);
1484 }
1485
1486 // If we have "add: @value + 1" then we know that @add <= max - 1, i.e. that
1487 // @add < max.
1488 if (!sumOverflows<int>(std::numeric_limits<int>::max(), -offset, 1)) {
1489 setRelationship(
1490 Relationship(
1491 node, m_zero, Relationship::LessThan,
1492 std::numeric_limits<int>::max() - offset + 1),
1493 0);
1494 }
1495 }
1496 break;
1497 }
1498
1499 case GetArrayLength:
1500 case GetVectorLength: {
1501 setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
1502 break;
1503 }
1504
1505 case Upsilon: {
1506 setEquivalence(
1507 node->child1().node(),
1508 NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow));
1509 break;
1510 }
1511
1512 case Phi: {
1513 setEquivalence(
1514 NodeFlowProjection(node, NodeFlowProjection::Shadow),
1515 node);
1516 break;
1517 }
1518
1519 default:
1520 break;
1521 }
1522 }
1523
1524 void setEquivalence(NodeFlowProjection oldNode, NodeFlowProjection newNode)
1525 {
1526 setRelationship(Relationship::safeCreate(oldNode, newNode, Relationship::Equal, 0));
1527
1528 auto iter = m_relationships.find(oldNode);
1529 if (iter != m_relationships.end()) {
1530 Vector<Relationship> toAdd;
1531 for (Relationship relationship : iter->value) {
1532 Relationship newRelationship = relationship;
1533 // Avoid creating any kind of self-relationship.
1534 if (newNode.node() == newRelationship.right().node())
1535 continue;
1536 newRelationship.setLeft(newNode);
1537 toAdd.append(newRelationship);
1538 }
1539 for (Relationship relationship : toAdd)
1540 setRelationship(relationship);
1541 }
1542 }
1543
1544 void setRelationship(Relationship relationship, unsigned timeToLive = 1)
1545 {
1546 setRelationship(m_relationships, relationship, timeToLive);
1547 }
1548
1549 void setRelationship(
1550 RelationshipMap& relationshipMap, Relationship relationship, unsigned timeToLive = 1)
1551 {
1552 setOneSide(relationshipMap, relationship, timeToLive);
1553 setOneSide(relationshipMap, relationship.flipped(), timeToLive);
1554 }
1555
1556 void setOneSide(
1557 RelationshipMap& relationshipMap, Relationship relationship, unsigned timeToLive = 1)
1558 {
1559 if (!relationship)
1560 return;
1561
1562 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1563 dataLog(" Setting: ", relationship, " (ttl = ", timeToLive, ")\n");
1564
1565 auto result = relationshipMap.add(
1566 relationship.left(), Vector<Relationship>());
1567 Vector<Relationship>& relationships = result.iterator->value;
1568
1569 if (relationship.right()->isInt32Constant()) {
1570 // We want to do some work to refine relationships over constants. This is necessary because
1571 // when we introduce a constant into the IR, we don't automatically create relationships
1572 // between that constant and the other constants. That means that when we do introduce
1573 // relationships between a non-constant and a constant, we need to check the other
1574 // relationships between that non-constant and other constants to see if we can make some
1575 // refinements. Possible constant statement filtrations:
1576 //
1577 // - @x == @c and @x != @d, where @c > @d:
1578 // @x == @c and @x > @d
1579 //
1580 // but actually we are more aggressive:
1581 //
1582 // - @x == @c and @x op @d where @c == @d + k
1583 // @x == @c and @x == @d + k
1584 //
1585 // And this is also possible:
1586 //
1587 // - @x > @c and @x != @d where @c == @d + k and k >= 0
1588 //
1589 // @x > @c and @x > @d + k
1590 //
1591 // So, here's what we should do depending on the kind of relationship we're introducing:
1592 //
1593 // Equal constant: Find all LessThan, NotEqual, and GreaterThan constant operations and refine
1594 // them to be Equal constant. Don't worry about contradictions.
1595 //
1596 // LessThan, GreaterThan constant: See if there is any Equal constant, and if so, refine to
1597 // that. Otherwise, find all NotEqual constant operations and refine them to be LessThan or
1598 // GreaterThan constant if possible.
1599 //
1600 // NotEqual constant: See if there is any Equal constant, and if so, refine to that. Otherwise,
1601 // see if there is any LessThan or GreaterThan constant operation, and if so, attempt to
1602 // refine to that.
1603 //
1604 // Seems that the key thing is to have a filterConstant() operation that returns a refined
1605 // version of *this based on other. The code here accomplishes this by using the vagueness
1606 // index (Relationship::vagueness()) to first find less vague relationships and refine this one
1607 // using them, and then find more vague relationships and refine those to this.
1608
1609 if (relationship.vagueness() != Relationship::minVagueness) {
1610 // We're not minimally vague (maximally specific), so try to refine ourselves based on what
1611 // we already know.
1612 for (Relationship& otherRelationship : relationships) {
1613 if (otherRelationship.vagueness() < relationship.vagueness()
1614 && otherRelationship.right()->isInt32Constant()) {
1615 Relationship newRelationship = relationship.filterConstant(otherRelationship);
1616 if (DFGIntegerRangeOptimizationPhaseInternal::verbose && newRelationship != relationship)
1617 dataLog(" Refined to: ", newRelationship, " based on ", otherRelationship, "\n");
1618 relationship = newRelationship;
1619 }
1620 }
1621 }
1622
1623 if (relationship.vagueness() != Relationship::maxVagueness) {
1624 // We're not maximally value (minimally specific), so try to refine other relationships
1625 // based on this one.
1626 for (Relationship& otherRelationship : relationships) {
1627 if (otherRelationship.vagueness() > relationship.vagueness()
1628 && otherRelationship.right()->isInt32Constant()) {
1629 Relationship newRelationship = otherRelationship.filterConstant(relationship);
1630 if (DFGIntegerRangeOptimizationPhaseInternal::verbose && newRelationship != otherRelationship)
1631 dataLog(" Refined ", otherRelationship, " to: ", newRelationship, "\n");
1632 otherRelationship = newRelationship;
1633 }
1634 }
1635 }
1636 }
1637
1638 Vector<Relationship> toAdd;
1639 bool found = false;
1640 for (Relationship& otherRelationship : relationships) {
1641 if (otherRelationship.sameNodesAs(relationship)) {
1642 if (Relationship filtered = otherRelationship.filter(relationship)) {
1643 ASSERT(filtered.left() == relationship.left());
1644 otherRelationship = filtered;
1645 found = true;
1646 }
1647 }
1648
1649 // FIXME: Also add filtration over statements about constants. For example, if we have
1650 // @x == @c and @x != @d, where @d > @c, then we want to turn @x != @d into @x < @d.
1651
1652 if (timeToLive && otherRelationship.kind() == Relationship::Equal) {
1653 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1654 dataLog(" Considering (lhs): ", otherRelationship, "\n");
1655
1656 // We have:
1657 // @a op @b + C
1658 // @a == @c + D
1659 //
1660 // This implies:
1661 // @c + D op @b + C
1662 // @c op @b + C - D
1663 //
1664 // Where: @a == relationship.left(), @b == relationship.right(),
1665 // @a == otherRelationship.left(), @c == otherRelationship.right().
1666
1667 if (otherRelationship.offset() != std::numeric_limits<int>::min()) {
1668 Relationship newRelationship = relationship;
1669 if (newRelationship.right() != otherRelationship.right()) {
1670 newRelationship.setLeft(otherRelationship.right());
1671 if (newRelationship.addToOffset(-otherRelationship.offset()))
1672 toAdd.append(newRelationship);
1673 }
1674 }
1675 }
1676 }
1677
1678 if (timeToLive && relationship.kind() != Relationship::Equal) {
1679 for (Relationship& possibleEquality : relationshipMap.get(relationship.right())) {
1680 if (possibleEquality.kind() != Relationship::Equal
1681 || possibleEquality.offset() == std::numeric_limits<int>::min()
1682 || possibleEquality.right() == relationship.left())
1683 continue;
1684 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1685 dataLog(" Considering (rhs): ", possibleEquality, "\n");
1686
1687 // We have:
1688 // @a op @b + C
1689 // @b == @c + D
1690 //
1691 // This implies:
1692 // @a op @c + (C + D)
1693 //
1694 // Where: @a == relationship.left(), @b == relationship.right()
1695
1696 Relationship newRelationship = relationship;
1697 newRelationship.setRight(possibleEquality.right());
1698 if (newRelationship.addToOffset(possibleEquality.offset()))
1699 toAdd.append(newRelationship);
1700 }
1701 }
1702
1703 if (!found)
1704 relationships.append(relationship);
1705
1706 for (Relationship anotherRelationship : toAdd) {
1707 ASSERT(timeToLive);
1708 setOneSide(relationshipMap, anotherRelationship, timeToLive - 1);
1709 }
1710 }
1711
1712 bool mergeTo(RelationshipMap& relationshipMap, BasicBlock* target)
1713 {
1714 if (DFGIntegerRangeOptimizationPhaseInternal::verbose) {
1715 dataLog("Merging to ", pointerDump(target), ":\n");
1716 dataLog(" Incoming: ", listDump(sortedRelationships(relationshipMap)), "\n");
1717 dataLog(" At head: ", listDump(sortedRelationships(m_relationshipsAtHead[target])), "\n");
1718 }
1719
1720 if (m_seenBlocks.add(target)) {
1721 // This is a new block. We copy subject to liveness pruning.
1722 auto isLive = [&] (NodeFlowProjection node) {
1723 if (node == m_zero)
1724 return true;
1725 return target->ssa->liveAtHead.contains(node);
1726 };
1727
1728 for (auto& entry : relationshipMap) {
1729 if (!isLive(entry.key))
1730 continue;
1731
1732 Vector<Relationship> values;
1733 for (Relationship relationship : entry.value) {
1734 ASSERT(relationship.left() == entry.key);
1735 if (isLive(relationship.right())) {
1736 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1737 dataLog(" Propagating ", relationship, "\n");
1738 values.append(relationship);
1739 }
1740 }
1741
1742 std::sort(values.begin(), values.end());
1743 m_relationshipsAtHead[target].add(entry.key, values);
1744 }
1745 return true;
1746 }
1747
1748 // Merge by intersecting. We have no notion of BOTTOM, so we use the omission of
1749 // relationships for a pair of nodes to mean TOP. The reason why we don't need BOTTOM
1750 // is (1) we just overapproximate contradictions and (2) a value never having been
1751 // assigned would only happen if we have not processed the node's predecessor. We
1752 // shouldn't process blocks until we have processed the block's predecessor because we
1753 // are using reverse postorder.
1754 Vector<NodeFlowProjection> toRemove;
1755 bool changed = false;
1756 for (auto& entry : m_relationshipsAtHead[target]) {
1757 auto iter = relationshipMap.find(entry.key);
1758 if (iter == relationshipMap.end()) {
1759 toRemove.append(entry.key);
1760 changed = true;
1761 continue;
1762 }
1763
1764 Vector<Relationship> constantRelationshipsAtHead;
1765 for (Relationship& relationshipAtHead : entry.value) {
1766 if (relationshipAtHead.right()->isInt32Constant())
1767 constantRelationshipsAtHead.append(relationshipAtHead);
1768 }
1769
1770 Vector<Relationship> mergedRelationships;
1771 for (Relationship targetRelationship : entry.value) {
1772 for (Relationship sourceRelationship : iter->value) {
1773 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1774 dataLog(" Merging ", targetRelationship, " and ", sourceRelationship, ":\n");
1775 targetRelationship.merge(
1776 sourceRelationship,
1777 [&] (Relationship newRelationship) {
1778 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
1779 dataLog(" Got ", newRelationship, "\n");
1780
1781 if (newRelationship.right()->isInt32Constant()) {
1782 // We can produce a relationship with a constant equivalent to
1783 // an existing relationship yet of a different form. For example:
1784 //
1785 // @a == @b(42) + 0
1786 // @a == @c(41) + 1
1787 //
1788 // We do not want to perpetually switch between those two forms,
1789 // so we always prefer the one already at head.
1790
1791 for (Relationship& existingRelationshipAtHead : constantRelationshipsAtHead) {
1792 if (existingRelationshipAtHead.isEquivalentTo(newRelationship)) {
1793 newRelationship = existingRelationshipAtHead;
1794 break;
1795 }
1796 }
1797 }
1798
1799 // We need to filter() to avoid exponential explosion of identical
1800 // relationships. We do this here to avoid making setOneSide() do
1801 // more work, since we expect setOneSide() will be called more
1802 // frequently. Here's an example. At some point someone might start
1803 // with two relationships like @a > @b - C and @a < @b + D. Then
1804 // someone does a setRelationship() passing something that turns
1805 // both of these into @a == @b. Now we have @a == @b duplicated.
1806 // Let's say that this duplicate @a == @b ends up at the head of a
1807 // loop. If we didn't have this rule, then the loop would propagate
1808 // duplicate @a == @b's onto the existing duplicate @a == @b's.
1809 // There would be four pairs of @a == @b, each of which would
1810 // create a new @a == @b. Now we'd have four of these duplicates
1811 // and the next time around we'd have 8, then 16, etc. We avoid
1812 // this here by doing this filtration. That might be a bit of
1813 // overkill, since it's probably just the identical duplicate
1814 // relationship case we want' to avoid. But, I'll keep this until
1815 // we have evidence that this is a performance problem. Remember -
1816 // we are already dealing with a list that is pruned down to
1817 // relationships with identical left operand. It shouldn't be a
1818 // large list.
1819 bool found = false;
1820 for (Relationship& existingRelationship : mergedRelationships) {
1821 if (existingRelationship.sameNodesAs(newRelationship)) {
1822 Relationship filtered =
1823 existingRelationship.filter(newRelationship);
1824 if (filtered) {
1825 existingRelationship = filtered;
1826 found = true;
1827 break;
1828 }
1829 }
1830 }
1831
1832 if (!found)
1833 mergedRelationships.append(newRelationship);
1834 });
1835 }
1836 }
1837 std::sort(mergedRelationships.begin(), mergedRelationships.end());
1838 if (entry.value == mergedRelationships)
1839 continue;
1840
1841 entry.value = mergedRelationships;
1842 changed = true;
1843 }
1844 for (NodeFlowProjection node : toRemove)
1845 m_relationshipsAtHead[target].remove(node);
1846
1847 return changed;
1848 }
1849
1850 Vector<Relationship> sortedRelationships(const RelationshipMap& relationships)
1851 {
1852 Vector<Relationship> result;
1853 for (auto& entry : relationships)
1854 result.appendVector(entry.value);
1855 std::sort(result.begin(), result.end());
1856 return result;
1857 }
1858
1859 Vector<Relationship> sortedRelationships()
1860 {
1861 return sortedRelationships(m_relationships);
1862 }
1863
1864 Node* m_zero;
1865 RelationshipMap m_relationships;
1866 BlockSet m_seenBlocks;
1867 BlockMap<RelationshipMap> m_relationshipsAtHead;
1868 InsertionSet m_insertionSet;
1869
1870 unsigned m_iterations { 0 };
1871};
1872
1873} // anonymous namespace
1874
1875bool performIntegerRangeOptimization(Graph& graph)
1876{
1877 return runPhase<IntegerRangeOptimizationPhase>(graph);
1878}
1879
1880} } // namespace JSC::DFG
1881
1882#endif // ENABLE(DFG_JIT)
1883
1884