Changeset 188720 in webkit for trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
- Timestamp:
- Aug 20, 2015, 5:26:41 PM (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
r188432 r188720 62 62 } 63 63 64 bool isGeneralOffset(int offset) 65 { 66 return offset >= -1 && offset <= 1; 67 } 68 64 69 class Relationship { 65 70 public: … … 70 75 GreaterThan 71 76 }; 77 78 // Some relationships provide more information than others. When a relationship provides more 79 // information, it is less vague. 80 static unsigned vagueness(Kind kind) 81 { 82 switch (kind) { 83 case Equal: 84 return 0; 85 case LessThan: 86 case GreaterThan: 87 return 1; 88 case NotEqual: 89 return 2; 90 } 91 RELEASE_ASSERT_NOT_REACHED(); 92 return 0; 93 } 94 95 static const unsigned minVagueness = 0; 96 static const unsigned maxVagueness = 2; 72 97 73 98 static Kind flipped(Kind kind) … … 119 144 Kind kind() const { return m_kind; } 120 145 int offset() const { return m_offset; } 146 147 unsigned vagueness() const { return vagueness(kind()); } 121 148 122 149 Relationship flipped() const … … 239 266 } 240 267 241 // Attempts to create a relationship that summarizes the union of this relationship and 242 // the other relationship. The null relationship is returned to indicate TOP. This is used 268 // Attempts to create relationships that summarize the union of this relationship and 269 // the other relationship. Relationships are returned by calling the functor with the newly 270 // created relationships. No relationships are created to indicate TOP. This is used 243 271 // for merging the current relationship-at-head for some pair of nodes and a new 244 272 // relationship-at-head being proposed by a predecessor. We wish to create a new … … 247 275 // previous ones, we will cause the analysis fixpoint to reexecute. 248 276 // 249 // If *this and other are identical, we just return it.277 // If *this and other are identical, we just pass it to the functor. 250 278 // 251 279 // If they are different, we pick from a finite set of "general" relationships: … … 278 306 // 279 307 // Note that C being constrained to -1,0,1 also ensures that we never have to return a 280 // combination of Lt and Gt, as in for example this<other+C && this>other-D. That's why 281 // this function can return zero or one relationships rather than a list of relationships. 282 // The only possible values of C and D where this would work are -1 and 1, but in that case 283 // we just say this==other. That said, the logic for merging two == relationships, like 284 // this==other+C || this==other+D is to attempt to create these two relationships: 285 // this>other+min(C,D)-1 && this<other+max(C,D)+1. But only one of these relationships will 286 // belong to the set of general relationships. 308 // combination of Lt and Gt, as in for example this<other+C && this>other-D. The only possible 309 // values of C and D where this would work are -1 and 1, but in that case we just say 310 // this==other. That said, the logic for merging two == relationships, like this==other+C || 311 // this==other+D is to attempt to create these two relationships: this>other+min(C,D)-1 && 312 // this<other+max(C,D)+1. But only one of these relationships will belong to the set of general 313 // relationships. 287 314 // 288 315 // Here's an example of this in action: … … 296 323 // realize that only i>a-1 is a valid general relationship. This gives us exactly what we 297 324 // want: a statement that i>=a. 298 Relationship merge(const Relationship& other) const 299 { 300 if (!sameNodesAs(other)) 301 return Relationship(); 302 325 // 326 // However, this may return a pair of relationships when merging relationships involving 327 // constants. For example, if given: 328 // 329 // @x == @c 330 // @x == @d 331 // 332 // where @c and @d are constants, then this may pass two relationships to the functor: 333 // 334 // @x > min(@c, @d) - 1 335 // @x < max(@c, @d) + 1 336 // 337 // This still allows for convergence, because just as when merging relationships over 338 // variables, this always picks from a set of general relationships. Hence although this may 339 // produce two relationships as a result of the merge, the total number of relationships that 340 // can be present at head of block is limited by O(graph.size^2). 341 template<typename Functor> 342 void merge(const Relationship& other, const Functor& functor) const 343 { 303 344 // Handle the super obvious case first. 304 if (*this == other) 305 return *this; 345 if (*this == other) { 346 functor(*this); 347 return; 348 } 349 350 if (m_left != other.m_left) 351 return; 352 353 if (m_right != other.m_right) { 354 mergeConstantsImpl(other, functor); 355 return; 356 } 357 358 ASSERT(sameNodesAs(other)); 306 359 307 360 // This does some interesting permutations to reduce the amount of duplicate code. For … … 330 383 // cases. 331 384 if (!a || !b) 332 return Relationship();385 return; 333 386 334 387 needFlip = true; … … 338 391 // things for that case for now. 339 392 if (a.m_kind == GreaterThan || b.m_kind == GreaterThan) 340 return Relationship();393 return; 341 394 } 342 395 … … 350 403 351 404 Relationship result = a.mergeImpl(b); 405 if (!result) 406 return; 352 407 353 408 if (needFlip) 354 re turnresult.flipped();355 356 return result;409 result = result.flipped(); 410 411 functor(result); 357 412 } 358 413 … … 457 512 return filterFlipped(); 458 513 } 514 515 // Come up with a relationship that is the best description of this && other, provided that left() is 516 // the same and right() is a constant. Also requires that this is at least as vague as other. It may 517 // return this or it may return something else, but whatever it returns, it will have the same nodes as 518 // this. This is not automatically done by filter() because it currently only makes sense to call this 519 // during a very particular part of setOneSide(). 520 Relationship filterConstant(const Relationship& other) const 521 { 522 ASSERT(m_left == other.m_left); 523 ASSERT(m_right->isInt32Constant()); 524 ASSERT(other.m_right->isInt32Constant()); 525 ASSERT(vagueness() >= other.vagueness()); 526 527 if (vagueness() == other.vagueness()) 528 return *this; 529 530 int thisRight = m_right->asInt32(); 531 int otherRight = other.m_right->asInt32(); 532 533 // Ignore funny business. 534 if (sumOverflows<int>(otherRight, other.m_offset)) 535 return *this; 536 537 int otherEffectiveRight = otherRight + other.m_offset; 538 539 switch (other.m_kind) { 540 case Equal: 541 // Return a version of *this that is Equal to other's constant. 542 return Relationship(m_left, m_right, Equal, otherEffectiveRight - thisRight); 543 544 case LessThan: 545 case GreaterThan: 546 ASSERT(m_kind == NotEqual); 547 // We could do smart things here. But we don't currently have an example of when it would be 548 // valuable. Note that you have to be careful. We could refine NotEqual to LessThan, but only 549 // if the LessThan subsumes the NotEqual. 550 return *this; 551 552 case NotEqual: 553 RELEASE_ASSERT_NOT_REACHED(); 554 return Relationship(); 555 } 556 557 RELEASE_ASSERT_NOT_REACHED(); 558 return Relationship(); 559 } 459 560 460 561 int minValueOfLeft() const … … 594 695 // We have something like @a < @b + 2. We can't represent this under the 595 696 // -1,0,1 rule. 596 if ( bestOffset <= 1)697 if (isGeneralOffset(bestOffset)) 597 698 return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1)); 598 699 … … 619 720 620 721 // We have something like @a < @b + 2. We can't do it. 621 if ( bestOffset <= 1)722 if (isGeneralOffset(bestOffset)) 622 723 return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1)); 623 724 … … 647 748 m_left, other.m_right, LessThan, lessThanEqOffset + 1); 648 749 649 ASSERT( lessThan.offset() >= -1 && lessThan.offset() <= 1);750 ASSERT(isGeneralOffset(lessThan.offset())); 650 751 } 651 752 … … 655 756 m_left, other.m_right, GreaterThan, greaterThanEqOffset - 1); 656 757 657 ASSERT( greaterThan.offset() >= -1 && greaterThan.offset() <= 1);758 ASSERT(isGeneralOffset(greaterThan.offset())); 658 759 } 659 760 … … 666 767 667 768 return greaterThan; 769 } 770 771 template<typename Functor> 772 void mergeConstantsImpl(const Relationship& other, const Functor& functor) const 773 { 774 ASSERT(m_left == other.m_left); 775 776 // Only deal with constant right. 777 if (!m_right->isInt32Constant() || !other.m_right->isInt32Constant()) 778 return; 779 780 // What follows is a fairly conservative merge. We could tune this phase to come up with 781 // all possible inequalities between variables and constants, but we focus mainly on cheap 782 // cases for now. 783 784 // Here are some of the the arrangements we can merge usefully assuming @c < @d: 785 // 786 // @x == @c || @x == @d => @x >= c && @x <= @d 787 // @x >= @c || @x <= @d => TOP 788 // @x == @c || @x != @d => @x != @d 789 790 int thisRight = m_right->asInt32(); 791 int otherRight = other.m_right->asInt32(); 792 793 // Ignore funny business. 794 if (sumOverflows<int>(thisRight, m_offset)) 795 return; 796 if (sumOverflows<int>(otherRight, other.m_offset)) 797 return; 798 799 int thisEffectiveRight = thisRight + m_offset; 800 int otherEffectiveRight = otherRight + other.m_offset; 801 802 auto makeUpper = [&] (int64_t upper) { 803 if (upper <= thisRight) { 804 // We want m_right + offset to be equal to upper. Hence we want offset to cancel 805 // with m_right. But there's more to it, since we want +1 to turn the LessThan into 806 // a LessThanOrEqual, and we want to make sure we don't end up with non-general 807 // offsets. 808 int offset = static_cast<int>(std::max( 809 static_cast<int64_t>(1) + upper - static_cast<int64_t>(thisRight), 810 static_cast<int64_t>(-1))); 811 functor(Relationship(m_left, m_right, LessThan, offset)); 812 } 813 if (upper <= otherRight) { 814 int offset = static_cast<int>(std::max( 815 static_cast<int64_t>(1) + upper - static_cast<int64_t>(otherRight), 816 static_cast<int64_t>(-1))); 817 functor(Relationship(m_left, other.m_right, LessThan, offset)); 818 } 819 }; 820 auto makeLower = [&] (int64_t lower) { 821 if (lower >= thisRight) { 822 // We want m_right + offset to be equal to lower. Hence we want offset to cancel with 823 // m_right. But there's more to it, since we want -1 to turn the GreaterThan into a 824 // GreaterThanOrEqual, and we want to make sure we don't end up with non-general 825 // offsets. 826 int offset = static_cast<int>(std::min( 827 static_cast<int64_t>(-1) + lower - static_cast<int64_t>(thisRight), 828 static_cast<int64_t>(1))); 829 functor(Relationship(m_left, m_right, GreaterThan, offset)); 830 } 831 if (lower >= otherRight) { 832 int offset = static_cast<int>(std::min( 833 static_cast<int64_t>(-1) + lower - static_cast<int64_t>(otherRight), 834 static_cast<int64_t>(1))); 835 functor(Relationship(m_left, other.m_right, GreaterThan, offset)); 836 } 837 }; 838 839 switch (m_kind) { 840 case Equal: { 841 switch (other.m_kind) { 842 case Equal: { 843 if (thisEffectiveRight == otherEffectiveRight) { 844 // This probably won't arise often. We can keep whichever relationship is general. 845 if (isGeneralOffset(m_offset)) 846 functor(*this); 847 if (isGeneralOffset(other.m_offset)) 848 functor(other); 849 return; 850 } 851 852 // What follows is the only case where a merge will create more rules than what it 853 // started with. This is fine for convergence because the LessThan/GreaterThan 854 // rules that this creates are general (i.e. have small offsets) and they never 855 // spawn more rules upon subsequent merging. 856 857 makeUpper(std::max(thisEffectiveRight, otherEffectiveRight)); 858 makeLower(std::min(thisEffectiveRight, otherEffectiveRight)); 859 return; 860 } 861 862 case LessThan: { 863 // Either the LessThan condition subsumes the equality, or the LessThan condition 864 // and equality merge together to create a looser LessThan condition. 865 866 // This is @x == thisEffectiveRight 867 // Other is: @x < otherEffectiveRight 868 869 // We want to create @x <= upper. Figure out the value of upper. 870 makeUpper(std::max( 871 static_cast<int64_t>(thisEffectiveRight), 872 static_cast<int64_t>(otherEffectiveRight) - 1)); 873 return; 874 } 875 876 case GreaterThan: { 877 // Opposite of the LessThan case, above. 878 879 // This is: @x == thisEffectiveRight 880 // Other is: @x > otherEffectiveRight 881 882 makeLower(std::min( 883 static_cast<int64_t>(thisEffectiveRight), 884 static_cast<int64_t>(otherEffectiveRight) + 1)); 885 return; 886 } 887 888 case NotEqual: { 889 // We keep the NotEqual so long as it doesn't contradict our Equal. 890 if (otherEffectiveRight == thisEffectiveRight) 891 return; 892 893 // But, we only keep the NotEqual if it is general. This simplifies reasoning about 894 // convergence: merging never introduces a new rule unless that rule is general. 895 if (!isGeneralOffset(other.m_offset)) 896 return; 897 898 functor(other); 899 return; 900 } } 901 902 RELEASE_ASSERT_NOT_REACHED(); 903 return; 904 } 905 906 case LessThan: { 907 switch (other.m_kind) { 908 case Equal: { 909 other.mergeConstantsImpl(*this, functor); 910 return; 911 } 912 913 case LessThan: { 914 makeUpper(std::max( 915 static_cast<int64_t>(thisEffectiveRight) - 1, 916 static_cast<int64_t>(otherEffectiveRight) - 1)); 917 return; 918 } 919 920 case GreaterThan: { 921 // We have a claim that @x > @c || @x < @d. If @d > @c, this is the tautology. If 922 // @d <= @c, it's sort of uninteresting. Just ignore this. 923 return; 924 } 925 926 case NotEqual: { 927 // We have a claim that @x < @c || @x != @d. This isn't interesting. 928 return; 929 } } 930 931 RELEASE_ASSERT_NOT_REACHED(); 932 return; 933 } 934 935 case GreaterThan: { 936 switch (other.m_kind) { 937 case Equal: { 938 other.mergeConstantsImpl(*this, functor); 939 return; 940 } 941 942 case LessThan: { 943 // Not interesting, see above. 944 return; 945 } 946 947 case GreaterThan: { 948 makeLower(std::min( 949 static_cast<int64_t>(thisEffectiveRight) + 1, 950 static_cast<int64_t>(otherEffectiveRight) + 1)); 951 return; 952 } 953 954 case NotEqual: { 955 // Not interesting, see above. 956 return; 957 } } 958 959 RELEASE_ASSERT_NOT_REACHED(); 960 return; 961 } 962 963 case NotEqual: { 964 if (other.m_kind == Equal) 965 other.mergeConstantsImpl(*this, functor); 966 return; 967 } } 968 969 RELEASE_ASSERT_NOT_REACHED(); 668 970 } 669 971 … … 1160 1462 relationship.left(), Vector<Relationship>()); 1161 1463 Vector<Relationship>& relationships = result.iterator->value; 1464 1465 if (relationship.right()->isInt32Constant()) { 1466 // We want to do some work to refine relationships over constants. This is necessary because 1467 // when we introduce a constant into the IR, we don't automatically create relationships 1468 // between that constant and the other constants. That means that when we do introduce 1469 // relationships between a non-constant and a constant, we need to check the other 1470 // relationships between that non-constant and other constants to see if we can make some 1471 // refinements. Possible constant statement filtrations: 1472 // 1473 // - @x == @c and @x != @d, where @c > @d: 1474 // @x == @c and @x > @d 1475 // 1476 // but actually we are more aggressive: 1477 // 1478 // - @x == @c and @x op @d where @c == @d + k 1479 // @x == @c and @x == @d + k 1480 // 1481 // And this is also possible: 1482 // 1483 // - @x > @c and @x != @d where @c == @d + k and k >= 0 1484 // 1485 // @x > @c and @x > @d + k 1486 // 1487 // So, here's what we should do depending on the kind of relationship we're introducing: 1488 // 1489 // Equal constant: Find all LessThan, NotEqual, and GreaterThan constant operations and refine 1490 // them to be Equal constant. Don't worry about contradictions. 1491 // 1492 // LessThan, GreaterThan constant: See if there is any Equal constant, and if so, refine to 1493 // that. Otherwise, find all NotEqual constant operations and refine them to be LessThan or 1494 // GreaterThan constant if possible. 1495 // 1496 // NotEqual constant: See if there is any Equal constant, and if so, refine to that. Otherwise, 1497 // see if there is any LessThan or GreaterThan constant operation, and if so, attempt to 1498 // refine to that. 1499 // 1500 // Seems that the key thing is to have a filterConstant() operation that returns a refined 1501 // version of *this based on other. The code here accomplishes this by using the vagueness 1502 // index (Relationship::vagueness()) to first find less vague relationships and refine this one 1503 // using them, and then find more vague relationships and refine those to this. 1504 1505 if (relationship.vagueness() != Relationship::minVagueness) { 1506 // We're not minimally vague (maximally specific), so try to refine ourselves based on what 1507 // we already know. 1508 for (Relationship& otherRelationship : relationships) { 1509 if (otherRelationship.vagueness() < relationship.vagueness() 1510 && otherRelationship.right()->isInt32Constant()) { 1511 Relationship newRelationship = relationship.filterConstant(otherRelationship); 1512 if (verbose && newRelationship != relationship) 1513 dataLog(" Refined to: ", newRelationship, " based on ", otherRelationship, "\n"); 1514 relationship = newRelationship; 1515 } 1516 } 1517 } 1518 1519 if (relationship.vagueness() != Relationship::maxVagueness) { 1520 // We're not maximally value (minimally specific), so try to refine other relationships 1521 // based on this one. 1522 for (Relationship& otherRelationship : relationships) { 1523 if (otherRelationship.vagueness() > relationship.vagueness() 1524 && otherRelationship.right()->isInt32Constant()) { 1525 Relationship newRelationship = otherRelationship.filterConstant(relationship); 1526 if (verbose && newRelationship != otherRelationship) 1527 dataLog(" Refined ", otherRelationship, " to: ", newRelationship, "\n"); 1528 otherRelationship = newRelationship; 1529 } 1530 } 1531 } 1532 } 1533 1162 1534 Vector<Relationship> toAdd; 1163 1535 bool found = false; … … 1170 1542 } 1171 1543 } 1544 1545 // FIXME: Also add filtration over statements about constants. For example, if we have 1546 // @x == @c and @x != @d, where @d > @c, then we want to turn @x != @d into @x < @d. 1172 1547 1173 1548 if (timeToLive && otherRelationship.kind() == Relationship::Equal) { … … 1263 1638 if (verbose) 1264 1639 dataLog(" Merging ", targetRelationship, " and ", sourceRelationship, ":\n"); 1265 Relationship newRelationship = 1266 targetRelationship.merge(sourceRelationship); 1267 1268 if (verbose) 1269 dataLog(" Got ", newRelationship, "\n"); 1270 1271 if (!newRelationship) 1272 continue; 1273 1274 // We need to filter() to avoid exponential explosion of identical 1275 // relationships. We do this here to avoid making setOneSide() do 1276 // more work, since we expect setOneSide() will be called more 1277 // frequently. Here's an example. At some point someone might start 1278 // with two relationships like @a > @b - C and @a < @b + D. Then 1279 // someone does a setRelationship() passing something that turns 1280 // both of these into @a == @b. Now we have @a == @b duplicated. 1281 // Let's say that this duplicate @a == @b ends up at the head of a 1282 // loop. If we didn't have this rule, then the loop would propagate 1283 // duplicate @a == @b's onto the existing duplicate @a == @b's. 1284 // There would be four pairs of @a == @b, each of which would 1285 // create a new @a == @b. Now we'd have four of these duplicates 1286 // and the next time around we'd have 8, then 16, etc. We avoid 1287 // this here by doing this filtration. That might be a bit of 1288 // overkill, since it's probably just the identical duplicate 1289 // relationship case we want' to avoid. But, I'll keep this until 1290 // we have evidence that this is a performance problem. Remember - 1291 // we are already dealing with a list that is pruned down to 1292 // relationships with identical left operand. It shouldn't be a 1293 // large list. 1294 bool found = false; 1295 for (Relationship& existingRelationship : mergedRelationships) { 1296 if (existingRelationship.sameNodesAs(newRelationship)) { 1297 Relationship filtered = 1298 existingRelationship.filter(newRelationship); 1299 if (filtered) { 1300 existingRelationship = filtered; 1301 found = true; 1302 break; 1640 targetRelationship.merge( 1641 sourceRelationship, 1642 [&] (Relationship newRelationship) { 1643 if (verbose) 1644 dataLog(" Got ", newRelationship, "\n"); 1645 1646 // We need to filter() to avoid exponential explosion of identical 1647 // relationships. We do this here to avoid making setOneSide() do 1648 // more work, since we expect setOneSide() will be called more 1649 // frequently. Here's an example. At some point someone might start 1650 // with two relationships like @a > @b - C and @a < @b + D. Then 1651 // someone does a setRelationship() passing something that turns 1652 // both of these into @a == @b. Now we have @a == @b duplicated. 1653 // Let's say that this duplicate @a == @b ends up at the head of a 1654 // loop. If we didn't have this rule, then the loop would propagate 1655 // duplicate @a == @b's onto the existing duplicate @a == @b's. 1656 // There would be four pairs of @a == @b, each of which would 1657 // create a new @a == @b. Now we'd have four of these duplicates 1658 // and the next time around we'd have 8, then 16, etc. We avoid 1659 // this here by doing this filtration. That might be a bit of 1660 // overkill, since it's probably just the identical duplicate 1661 // relationship case we want' to avoid. But, I'll keep this until 1662 // we have evidence that this is a performance problem. Remember - 1663 // we are already dealing with a list that is pruned down to 1664 // relationships with identical left operand. It shouldn't be a 1665 // large list. 1666 bool found = false; 1667 for (Relationship& existingRelationship : mergedRelationships) { 1668 if (existingRelationship.sameNodesAs(newRelationship)) { 1669 Relationship filtered = 1670 existingRelationship.filter(newRelationship); 1671 if (filtered) { 1672 existingRelationship = filtered; 1673 found = true; 1674 break; 1675 } 1676 } 1303 1677 } 1304 } 1305 } 1306 1307 if (!found) 1308 mergedRelationships.append(newRelationship); 1678 1679 if (!found) 1680 mergedRelationships.append(newRelationship); 1681 }); 1309 1682 } 1310 1683 }
Note:
See TracChangeset
for help on using the changeset viewer.
