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