annotate modules/javafx.web/src/main/native/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp @ 11208:db2c977a840b

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