81181eb0b4b3e9ccd8a4eaccec446cff6151358d
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGIntegerRangeOptimizationPhase.cpp
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
41 namespace JSC { namespace DFG {
42
43 namespace {
44
45 namespace DFGIntegerRangeOptimizationPhaseInternal {
46 static const bool verbose = false;
47 }
48 const unsigned giveUpThreshold = 50;
49
50 int64_t clampedSumImpl() { return 0; }
51
52 template<typename... Args>
53 int64_t clampedSumImpl(int left, Args... args)
54 {
55     return static_cast<int64_t>(left) + clampedSumImpl(args...);
56 }
57
58 template<typename... Args>
59 int 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
69 bool isGeneralOffset(int offset)
70 {
71     return offset >= -1 && offset <= 1;
72 }
73
74 class Relationship {
75 public:
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     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     
654 private:
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
1001 typedef HashMap<NodeFlowProjection, Vector<Relationship>> RelationshipMap;
1002
1003 class IntegerRangeOptimizationPhase : public Phase {
1004 public:
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
1379 private:
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
1875 bool performIntegerRangeOptimization(Graph& graph)
1876 {
1877     return runPhase<IntegerRangeOptimizationPhase>(graph);
1878 }
1879
1880 } } // namespace JSC::DFG
1881
1882 #endif // ENABLE(DFG_JIT)
1883