Changeset 195637 in webkit


Ignore:
Timestamp:
Jan 26, 2016 4:49:03 PM (8 years ago)
Author:
fpizlo@apple.com
Message:

B3's integer range analysis should know that Mul'ing two sufficiently small numbers will yield a number that still has a meaningful range
https://bugs.webkit.org/show_bug.cgi?id=153518

Reviewed by Benjamin Poulain.

Octane/encrypt had an addition overflow check that can be proved away by being sufficiently
sneaky about the analysis of adds, multiplies, and shifts.

I almost added these optimizations to the DFG integer range optimization phase. That phase is
very complicated. B3's integer range analysis is trivial. So I added it to B3. Eventually
we'll want this same machinery in the DFG also.

8% speed-up on Octane/encrypt.

  • b3/B3ReduceStrength.cpp:
  • b3/B3Value.cpp:

(JSC::B3::Value::dump): Dumping a constant value's name now dumps its value. This makes a huge difference for reading IR.
(JSC::B3::Value::cloneImpl):
(JSC::B3::Value::deepDump):

Location:
trunk/Source/JavaScriptCore
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r195622 r195637  
     12016-01-26  Filip Pizlo  <fpizlo@apple.com>
     2
     3        B3's integer range analysis should know that Mul'ing two sufficiently small numbers will yield a number that still has a meaningful range
     4        https://bugs.webkit.org/show_bug.cgi?id=153518
     5
     6        Reviewed by Benjamin Poulain.
     7
     8        Octane/encrypt had an addition overflow check that can be proved away by being sufficiently
     9        sneaky about the analysis of adds, multiplies, and shifts.
     10
     11        I almost added these optimizations to the DFG integer range optimization phase. That phase is
     12        very complicated. B3's integer range analysis is trivial. So I added it to B3. Eventually
     13        we'll want this same machinery in the DFG also.
     14
     15        8% speed-up on Octane/encrypt.
     16
     17        * b3/B3ReduceStrength.cpp:
     18        * b3/B3Value.cpp:
     19        (JSC::B3::Value::dump): Dumping a constant value's name now dumps its value. This makes a huge difference for reading IR.
     20        (JSC::B3::Value::cloneImpl):
     21        (JSC::B3::Value::deepDump):
     22
    1232016-01-26  Filip Pizlo  <fpizlo@apple.com>
    224
  • trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp

    r195621 r195637  
    250250        default:
    251251            return true;
     252        }
     253    }
     254
     255    template<typename T>
     256    IntRange shl(int32_t shiftAmount)
     257    {
     258        T newMin = static_cast<T>(m_min) << shiftAmount;
     259        T newMax = static_cast<T>(m_max) << shiftAmount;
     260
     261        if ((newMin >> shiftAmount) != static_cast<T>(m_min))
     262            newMin = std::numeric_limits<T>::min();
     263        if ((newMax >> shiftAmount) != static_cast<T>(m_max))
     264            newMax = std::numeric_limits<T>::max();
     265
     266        return IntRange(newMin, newMax);
     267    }
     268
     269    IntRange shl(int32_t shiftAmount, Type type)
     270    {
     271        switch (type) {
     272        case Int32:
     273            return shl<int32_t>(shiftAmount);
     274        case Int64:
     275            return shl<int64_t>(shiftAmount);
     276        default:
     277            RELEASE_ASSERT_NOT_REACHED();
     278            return IntRange();
     279        }
     280    }
     281
     282    template<typename T>
     283    IntRange add(const IntRange& other)
     284    {
     285        if (couldOverflowAdd<T>(other))
     286            return top<T>();
     287        return IntRange(m_min + other.m_min, m_max + other.m_max);
     288    }
     289
     290    IntRange add(const IntRange& other, Type type)
     291    {
     292        switch (type) {
     293        case Int32:
     294            return add<int32_t>(other);
     295        case Int64:
     296            return add<int64_t>(other);
     297        default:
     298            RELEASE_ASSERT_NOT_REACHED();
     299            return IntRange();
     300        }
     301    }
     302
     303    template<typename T>
     304    IntRange sub(const IntRange& other)
     305    {
     306        if (couldOverflowSub<T>(other))
     307            return top<T>();
     308        return IntRange(m_min - other.m_max, m_max - other.m_min);
     309    }
     310
     311    IntRange sub(const IntRange& other, Type type)
     312    {
     313        switch (type) {
     314        case Int32:
     315            return sub<int32_t>(other);
     316        case Int64:
     317            return sub<int64_t>(other);
     318        default:
     319            RELEASE_ASSERT_NOT_REACHED();
     320            return IntRange();
     321        }
     322    }
     323
     324    template<typename T>
     325    IntRange mul(const IntRange& other)
     326    {
     327        if (couldOverflowMul<T>(other))
     328            return top<T>();
     329        return IntRange(
     330            std::min(
     331                std::min(m_min * other.m_min, m_min * other.m_max),
     332                std::min(m_max * other.m_min, m_max * other.m_max)),
     333            std::max(
     334                std::max(m_min * other.m_min, m_min * other.m_max),
     335                std::max(m_max * other.m_min, m_max * other.m_max)));
     336    }
     337
     338    IntRange mul(const IntRange& other, Type type)
     339    {
     340        switch (type) {
     341        case Int32:
     342            return mul<int32_t>(other);
     343        case Int64:
     344            return mul<int64_t>(other);
     345        default:
     346            RELEASE_ASSERT_NOT_REACHED();
     347            return IntRange();
    252348        }
    253349    }
     
    18401936    }
    18411937
    1842     IntRange rangeFor(Value* value)
    1843     {
     1938    // FIXME: This should really be a forward analysis. Instead, we uses a bounded-search backwards
     1939    // analysis.
     1940    IntRange rangeFor(Value* value, unsigned timeToLive = 5)
     1941    {
     1942        if (!timeToLive)
     1943            return IntRange::top(value->type());
     1944       
    18441945        switch (value->opcode()) {
    18451946        case Const32:
     
    18631964                return IntRange::rangeForZShr(value->child(1)->asInt32(), value->type());
    18641965            break;
     1966
     1967        case Shl:
     1968            if (value->child(1)->hasInt32())
     1969                return rangeFor(value->child(0), timeToLive - 1).shl(
     1970                    value->child(1)->asInt32(), value->type());
     1971            break;
     1972
     1973        case Add:
     1974            return rangeFor(value->child(0), timeToLive - 1).add(
     1975                rangeFor(value->child(1), timeToLive - 1), value->type());
     1976
     1977        case Sub:
     1978            return rangeFor(value->child(0), timeToLive - 1).sub(
     1979                rangeFor(value->child(1), timeToLive - 1), value->type());
     1980
     1981        case Mul:
     1982            return rangeFor(value->child(0), timeToLive - 1).mul(
     1983                rangeFor(value->child(1), timeToLive - 1), value->type());
    18651984
    18661985        default:
  • trunk/Source/JavaScriptCore/b3/B3Value.cpp

    r195620 r195637  
    112112void Value::dump(PrintStream& out) const
    113113{
     114    bool isConstant = false;
     115
     116    switch (m_opcode) {
     117    case Const32:
     118        out.print("$", asInt32(), "(");
     119        isConstant = true;
     120        break;
     121    case Const64:
     122        out.print("$", asInt64(), "(");
     123        isConstant = true;
     124        break;
     125    case ConstFloat:
     126        out.print("$", asFloat(), "(");
     127        isConstant = true;
     128        break;
     129    case ConstDouble:
     130        out.print("$", asDouble(), "(");
     131        isConstant = true;
     132        break;
     133    default:
     134        break;
     135    }
     136   
    114137    out.print(dumpPrefix, m_index);
     138
     139    if (isConstant)
     140        out.print(")");
    115141}
    116142
     
    128154void Value::deepDump(const Procedure* proc, PrintStream& out) const
    129155{
    130     out.print(m_type, " ", *this, " = ", m_opcode);
     156    out.print(m_type, " ", dumpPrefix, m_index, " = ", m_opcode);
    131157
    132158    out.print("(");
Note: See TracChangeset for help on using the changeset viewer.