Changeset 195417 in webkit


Ignore:
Timestamp:
Jan 21, 2016 11:54:51 AM (8 years ago)
Author:
fpizlo@apple.com
Message:

B3 should have load elimination
​https://bugs.webkit.org/show_bug.cgi?id=153288

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

This adds a complete GCSE pass that includes load elimination. It would have been super hard
to make this work as part of the reduceStrength() fixpoint, since GCSE needs to analyze
control flow and reduceStrength() is messing with control flow. So, I did a compromise: I
factored out the pure CSE that reduceStrength() was already doing, and now we have:

  • reduceStrength() still does pure CSE using the new PureCSE helper.
  • eliminateCommonSubexpressions() is a separate phase that does general CSE. It uses the PureCSE helper for pure values and does its own special thing for memory values.


Unfortunately, this doesn't help any benchmark right now. It doesn't hurt anything, either,
and it's likely to become a bigger pay-off once we implement other features, like mapping
FTL's abstract heaps onto B3's heap ranges.

  • CMakeLists.txt:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • b3/B3EliminateCommonSubexpressions.cpp: Added.

(JSC::B3::eliminateCommonSubexpressions):

  • b3/B3EliminateCommonSubexpressions.h: Added.
  • b3/B3Generate.cpp:

(JSC::B3::generateToAir):

  • b3/B3HeapRange.h:

(JSC::B3::HeapRange::HeapRange):

  • b3/B3InsertionSet.h:

(JSC::B3::InsertionSet::InsertionSet):
(JSC::B3::InsertionSet::isEmpty):
(JSC::B3::InsertionSet::code):
(JSC::B3::InsertionSet::appendInsertion):

  • b3/B3MemoryValue.h:
  • b3/B3PureCSE.cpp: Added.

(JSC::B3::PureCSE::PureCSE):
(JSC::B3::PureCSE::~PureCSE):
(JSC::B3::PureCSE::clear):
(JSC::B3::PureCSE::process):

  • b3/B3PureCSE.h: Added.
  • b3/B3ReduceStrength.cpp:
  • b3/B3ReduceStrength.h:
  • b3/B3Validate.cpp:

Source/WTF:

I needed a way to track sets of ranges, where there is a high likelihood that all of the
ranges overlap. So I created RangeSet. It's a usually-sorted list of coalesced ranges.
Practically this means that right now, FTL B3 will end up with two kinds of range sets: a set
that just contains top and a set that contains nothing. In the future, most sets will either
be top of empty but some of them will contain a handful of other things.

  • WTF.xcodeproj/project.pbxproj:
  • wtf/CMakeLists.txt:
  • wtf/MathExtras.h:

(WTF::leftShiftWithSaturation):
(WTF::nonEmptyRangesOverlap):
(WTF::rangesOverlap):

  • wtf/RangeSet.h: Added.

(WTF::RangeSet::RangeSet):
(WTF::RangeSet::~RangeSet):
(WTF::RangeSet::add):
(WTF::RangeSet::contains):
(WTF::RangeSet::overlaps):
(WTF::RangeSet::clear):
(WTF::RangeSet::dump):
(WTF::RangeSet::dumpRaw):
(WTF::RangeSet::compact):
(WTF::RangeSet::overlapsNonEmpty):
(WTF::RangeSet::subsumesNonEmpty):
(WTF::RangeSet::findRange):

  • wtf/StdLibExtras.h:

(WTF::binarySearchImpl):
(WTF::binarySearch):
(WTF::tryBinarySearch):
(WTF::approximateBinarySearch):

Location:
trunk/Source
Files:
5 added
15 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/CMakeLists.txt

    r195407 r195417  
    121121    b3/B3DuplicateTails.cpp
    122122    b3/B3Effects.cpp
     123    b3/B3EliminateCommonSubexpressions.cpp
    123124    b3/B3FixSSA.cpp
    124125    b3/B3FoldPathConstants.cpp
    … …  
    143144    b3/B3PhiChildren.cpp
    144145    b3/B3Procedure.cpp
     146    b3/B3PureCSE.cpp
    145147    b3/B3ReduceDoubleToFloat.cpp
    146148    b3/B3ReduceStrength.cpp

  • trunk/Source/JavaScriptCore/ChangeLog

    r195416 r195417  
     12016-01-21  Filip Pizlo  <fpizlo@apple.com>
     2
     3        B3 should have load elimination
     4        https://bugs.webkit.org/show_bug.cgi?id=153288
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        This adds a complete GCSE pass that includes load elimination. It would have been super hard
     9        to make this work as part of the reduceStrength() fixpoint, since GCSE needs to analyze
     10        control flow and reduceStrength() is messing with control flow. So, I did a compromise: I
     11        factored out the pure CSE that reduceStrength() was already doing, and now we have:
     12
     13        - reduceStrength() still does pure CSE using the new PureCSE helper.
     14
     15        - eliminateCommonSubexpressions() is a separate phase that does general CSE. It uses the
     16          PureCSE helper for pure values and does its own special thing for memory values.
     17       
     18        Unfortunately, this doesn't help any benchmark right now. It doesn't hurt anything, either,
     19        and it's likely to become a bigger pay-off once we implement other features, like mapping
     20        FTL's abstract heaps onto B3's heap ranges.
     21
     22        * CMakeLists.txt:
     23        * JavaScriptCore.xcodeproj/project.pbxproj:
     24        * b3/B3EliminateCommonSubexpressions.cpp: Added.
     25        (JSC::B3::eliminateCommonSubexpressions):
     26        * b3/B3EliminateCommonSubexpressions.h: Added.
     27        * b3/B3Generate.cpp:
     28        (JSC::B3::generateToAir):
     29        * b3/B3HeapRange.h:
     30        (JSC::B3::HeapRange::HeapRange):
     31        * b3/B3InsertionSet.h:
     32        (JSC::B3::InsertionSet::InsertionSet):
     33        (JSC::B3::InsertionSet::isEmpty):
     34        (JSC::B3::InsertionSet::code):
     35        (JSC::B3::InsertionSet::appendInsertion):
     36        * b3/B3MemoryValue.h:
     37        * b3/B3PureCSE.cpp: Added.
     38        (JSC::B3::PureCSE::PureCSE):
     39        (JSC::B3::PureCSE::~PureCSE):
     40        (JSC::B3::PureCSE::clear):
     41        (JSC::B3::PureCSE::process):
     42        * b3/B3PureCSE.h: Added.
     43        * b3/B3ReduceStrength.cpp:
     44        * b3/B3ReduceStrength.h:
     45        * b3/B3Validate.cpp:
     46
    1472016-01-21  Keith Miller  <keith_miller@apple.com>
    248

  • trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r195395 r195417  
    468468                0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */; };
    469469                0F714CA516EA92F200F3EBEB /* DFGBackwardsPropagationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */; };
     470                0F725CA71C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */; };
     471                0F725CA81C503DED00AD943A /* B3EliminateCommonSubexpressions.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */; };
     472                0F725CA91C503DED00AD943A /* B3PureCSE.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CA51C503DED00AD943A /* B3PureCSE.cpp */; };
     473                0F725CAA1C503DED00AD943A /* B3PureCSE.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CA61C503DED00AD943A /* B3PureCSE.h */; };
    470474                0F725CAF1C506D3B00AD943A /* B3FoldPathConstants.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */; };
    471475                0F725CB01C506D3B00AD943A /* B3FoldPathConstants.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */; };
    … …  
    26482652                0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBackwardsPropagationPhase.cpp; path = dfg/DFGBackwardsPropagationPhase.cpp; sourceTree = "<group>"; };
    26492653                0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsPropagationPhase.h; path = dfg/DFGBackwardsPropagationPhase.h; sourceTree = "<group>"; };
     2654                0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3EliminateCommonSubexpressions.cpp; path = b3/B3EliminateCommonSubexpressions.cpp; sourceTree = "<group>"; };
     2655                0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3EliminateCommonSubexpressions.h; path = b3/B3EliminateCommonSubexpressions.h; sourceTree = "<group>"; };
     2656                0F725CA51C503DED00AD943A /* B3PureCSE.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3PureCSE.cpp; path = b3/B3PureCSE.cpp; sourceTree = "<group>"; };
     2657                0F725CA61C503DED00AD943A /* B3PureCSE.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3PureCSE.h; path = b3/B3PureCSE.h; sourceTree = "<group>"; };
    26502658                0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3FoldPathConstants.cpp; path = b3/B3FoldPathConstants.cpp; sourceTree = "<group>"; };
    26512659                0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3FoldPathConstants.h; path = b3/B3FoldPathConstants.h; sourceTree = "<group>"; };
    … …  
    47844792                                0FEC85C41BE16F5A0080FF74 /* B3Effects.cpp */,
    47854793                                0FEC85BE1BE167A00080FF74 /* B3Effects.h */,
     4794                                0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */,
     4795                                0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */,
    47864796                                0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */,
    47874797                                0F6B8AE11C4EFE1700969052 /* B3FixSSA.h */,
    … …  
    48354845                                0FEC84E21BDACDAC0080FF74 /* B3Procedure.h */,
    48364846                                0FEC84E31BDACDAC0080FF74 /* B3ProcedureInlines.h */,
     4847                                0F725CA51C503DED00AD943A /* B3PureCSE.cpp */,
     4848                                0F725CA61C503DED00AD943A /* B3PureCSE.h */,
    48374849                                43422A641C16221E00E2EB98 /* B3ReduceDoubleToFloat.cpp */,
    48384850                                43422A651C16221E00E2EB98 /* B3ReduceDoubleToFloat.h */,
    … …  
    73257337                                0FEA0A34170D40BF00BB722C /* DFGJITCode.h in Headers */,
    73267338                                86EC9DCC1328DF82002B2AD7 /* DFGJITCompiler.h in Headers */,
     7339                                0F725CA81C503DED00AD943A /* B3EliminateCommonSubexpressions.h in Headers */,
    73277340                                A78A9779179738B8009DF744 /* DFGJITFinalizer.h in Headers */,
    73287341                                0FC97F4018202119002C9B26 /* DFGJumpReplacement.h in Headers */,
    … …  
    76527665                                A1D792FF1B43864B004516F5 /* IntlNumberFormatConstructor.h in Headers */,
    76537666                                A125846E1B45A36000CC7F6C /* IntlNumberFormatConstructor.lut.h in Headers */,
     7667                                0F725CAA1C503DED00AD943A /* B3PureCSE.h in Headers */,
    76547668                                A1D793011B43864B004516F5 /* IntlNumberFormatPrototype.h in Headers */,
    76557669                                A125846F1B45A36000CC7F6C /* IntlNumberFormatPrototype.lut.h in Headers */,
    … …  
    88818895                                0F666EC61835672B00D017F1 /* DFGAvailability.cpp in Sources */,
    88828896                                0F2B9CE219D0BA7D00B1D1B5 /* DFGAvailabilityMap.cpp in Sources */,
     8897                                0F725CA71C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp in Sources */,
    88838898                                0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */,
    88848899                                A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */,
    … …  
    93299344                                142D6F1113539A4100B02E86 /* MarkStack.cpp in Sources */,
    93309345                                70B791981C024A29002481E2 /* GeneratorPrototype.cpp in Sources */,
     9346                                0F725CA91C503DED00AD943A /* B3PureCSE.cpp in Sources */,
    93319347                                4340A4841A9051AF00D73CCA /* MathCommon.cpp in Sources */,
    93329348                                0F37308C1C0BD29100052BFA /* B3PhiChildren.cpp in Sources */,

  • trunk/Source/JavaScriptCore/b3/B3Generate.cpp

    r195395 r195417  
    3434#include "B3Common.h"
    3535#include "B3DuplicateTails.h"
     36#include "B3EliminateCommonSubexpressions.h"
    3637#include "B3FoldPathConstants.h"
    3738#include "B3LegalizeMemoryOffsets.h"
    … …  
    7980        reduceDoubleToFloat(procedure);
    8081        reduceStrength(procedure);
     82        eliminateCommonSubexpressions(procedure);
    8183        duplicateTails(procedure);
    8284        foldPathConstants(procedure);

  • trunk/Source/JavaScriptCore/b3/B3HeapRange.h

    r191952 r195417  
    4141class HeapRange {
    4242public:
     43    typedef unsigned Type;
     44   
    4345    HeapRange()
    4446        : m_begin(0)

  • trunk/Source/JavaScriptCore/b3/B3InsertionSet.h

    r195395 r195417  
    4949    }
    5050
     51    bool isEmpty() const { return m_insertions.isEmpty(); }
     52
    5153    Procedure& code() { return m_procedure; }
    5254

  • trunk/Source/JavaScriptCore/b3/B3MemoryValue.h

    r195395 r195417  
    6060    const HeapRange& range() const { return m_range; }
    6161    void setRange(const HeapRange& range) { m_range = range; }
     62
     63    bool isStore() const { return type() == Void; }
     64    bool isLoad() const { return type() != Void; }
    6265
    6366    size_t accessByteSize() const;

  • trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp

    r195395 r195417  
    3939#include "B3PhiChildren.h"
    4040#include "B3ProcedureInlines.h"
     41#include "B3PureCSE.h"
    4142#include "B3UpsilonValue.h"
    4243#include "B3UseCounts.h"
    … …  
    283284            m_proc.resetValueOwners();
    284285            m_dominators = &m_proc.dominators(); // Recompute if necessary.
    285             m_pureValues.clear();
     286            m_pureCSE.clear();
    286287
    287288            for (BasicBlock* block : m_proc.blocksInPreOrder()) {
    … …  
    17521753    void replaceIfRedundant()
    17531754    {
    1754         // This does a very simple pure dominator-based CSE. In the future we could add load elimination.
    1755         // Note that if we add load elimination, we should do it by directly matching load and store
    1756         // instructions instead of using the ValueKey functionality or doing DFG HeapLocation-like
    1757         // things.
    1758 
    1759         // Don't bother with identities. We kill those anyway.
    1760         if (m_value->opcode() == Identity)
    1761             return;
    1762 
    1763         ValueKey key = m_value->key();
    1764         if (!key)
    1765             return;
    1766        
    1767         Vector<Value*, 1>& matches = m_pureValues.add(key, Vector<Value*, 1>()).iterator->value;
    1768 
    1769         // Replace this value with whichever value dominates us.
    1770         for (Value* match : matches) {
    1771             if (m_dominators->dominates(match->owner, m_value->owner)) {
    1772                 m_value->replaceWithIdentity(match);
    1773                 m_changed = true;
    1774                 return;
    1775             }
    1776         }
    1777 
    1778         matches.append(m_value);
     1755        m_changed |= m_pureCSE.process(m_value, *m_dominators);
    17791756    }
    17801757
    … …  
    20432020    Value* m_value { nullptr };
    20442021    Dominators* m_dominators { nullptr };
    2045     HashMap<ValueKey, Vector<Value*, 1>> m_pureValues;
     2022    PureCSE m_pureCSE;
    20462023    bool m_changed { false };
    20472024    bool m_changedCFG { false };

  • trunk/Source/JavaScriptCore/b3/B3ReduceStrength.h

    r193987 r195417  
    3333class Procedure;
    3434
    35 // Does strength reduction, constant folding, canonicalization, CFG simplification, DCE, and CSE. This
    36 // phase runs those optimizations to fixpoint. The goal of the phase is to dramatically reduce the
    37 // complexity of the code. In the future, it's preferable to add optimizations to this phase rather than
    38 // creating new optimizations because then the optimizations can participate in the fixpoint. However,
    39 // this phase shouldn't become too expensive, so expensive optimizations should be separate.
     35// Does strength reduction, constant folding, canonicalization, CFG simplification, DCE, and very
     36// simple CSE. This phase runs those optimizations to fixpoint. The goal of the phase is to
     37// dramatically reduce the complexity of the code. In the future, it's preferable to add optimizations
     38// to this phase rather than creating new optimizations because then the optimizations can participate
     39// in the fixpoint. However, because of the many interlocking optimizations, it can be difficult to
     40// add sophisticated optimizations to it. For that reason we have full CSE in a different phase, for
     41// example.
    4042
    4143bool reduceStrength(Procedure&);

  • trunk/Source/JavaScriptCore/b3/B3Validate.cpp

    r195395 r195417  
    372372                break;
    373373            }
     374
     375            VALIDATE(!(value->effects().writes && value->key()), ("At ", *value));
    374376        }
    375377    }

  • trunk/Source/WTF/ChangeLog

    r195412 r195417  
     12016-01-21  Filip Pizlo  <fpizlo@apple.com>
     2
     3        B3 should have load elimination
     4        https://bugs.webkit.org/show_bug.cgi?id=153288
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        I needed a way to track sets of ranges, where there is a high likelihood that all of the
     9        ranges overlap. So I created RangeSet. It's a usually-sorted list of coalesced ranges.
     10        Practically this means that right now, FTL B3 will end up with two kinds of range sets: a set
     11        that just contains top and a set that contains nothing. In the future, most sets will either
     12        be top of empty but some of them will contain a handful of other things.
     13
     14        * WTF.xcodeproj/project.pbxproj:
     15        * wtf/CMakeLists.txt:
     16        * wtf/MathExtras.h:
     17        (WTF::leftShiftWithSaturation):
     18        (WTF::nonEmptyRangesOverlap):
     19        (WTF::rangesOverlap):
     20        * wtf/RangeSet.h: Added.
     21        (WTF::RangeSet::RangeSet):
     22        (WTF::RangeSet::~RangeSet):
     23        (WTF::RangeSet::add):
     24        (WTF::RangeSet::contains):
     25        (WTF::RangeSet::overlaps):
     26        (WTF::RangeSet::clear):
     27        (WTF::RangeSet::dump):
     28        (WTF::RangeSet::dumpRaw):
     29        (WTF::RangeSet::compact):
     30        (WTF::RangeSet::overlapsNonEmpty):
     31        (WTF::RangeSet::subsumesNonEmpty):
     32        (WTF::RangeSet::findRange):
     33        * wtf/StdLibExtras.h:
     34        (WTF::binarySearchImpl):
     35        (WTF::binarySearch):
     36        (WTF::tryBinarySearch):
     37        (WTF::approximateBinarySearch):
     38
    1392016-01-19  Ada Chan  <adachan@apple.com>
    240

  • trunk/Source/WTF/WTF.xcodeproj/project.pbxproj

    r195356 r195417  
    2828                0F4570431BE5B58F0062A629 /* Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570421BE5B58F0062A629 /* Dominators.h */; };
    2929                0F4570451BE834410062A629 /* BubbleSort.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570441BE834410062A629 /* BubbleSort.h */; };
     30                0F725CAC1C50461600AD943A /* RangeSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CAB1C50461600AD943A /* RangeSet.h */; };
    3031                0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
    3132                0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
    … …  
    333334                0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
    334335                0F4570441BE834410062A629 /* BubbleSort.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BubbleSort.h; sourceTree = "<group>"; };
     336                0F725CAB1C50461600AD943A /* RangeSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RangeSet.h; sourceTree = "<group>"; };
    335337                0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
    336338                0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
    … …  
    877879                                A8A472FC151A825B004123FF /* RandomNumber.h */,
    878880                                A8A472FD151A825B004123FF /* RandomNumberSeed.h */,
     881                                0F725CAB1C50461600AD943A /* RangeSet.h */,
    879882                                0F87105916643F190090B0AD /* RawPointer.h */,
    880883                                A8A472FE151A825B004123FF /* RedBlackTree.h */,
    … …  
    11691172                                0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */,
    11701173                                A8A473C4151A825B004123FF /* FastMalloc.h in Headers */,
     1174                                0F725CAC1C50461600AD943A /* RangeSet.h in Headers */,
    11711175                                B38FD7BD168953E80065C969 /* FeatureDefines.h in Headers */,
    11721176                                0F9D3361165DBA73005AD387 /* FilePrintStream.h in Headers */,

  • trunk/Source/WTF/wtf/CMakeLists.txt

    r195304 r195417  
    7878    RandomNumber.h
    7979    RandomNumberSeed.h
     80    RangeSet.h
    8081    RawPointer.h
    8182    RedBlackTree.h

  • trunk/Source/WTF/wtf/MathExtras.h

    r195011 r195417  
    11/*
    2  * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013 Apple Inc. All rights reserved.
     2 * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013, 2016 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    420420}
    421421
     422// Check if two ranges overlap assuming that neither range is empty.
     423template<typename T>
     424inline bool nonEmptyRangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
     425{
     426    ASSERT(leftMin < leftMax);
     427    ASSERT(rightMin < rightMax);
     428   
     429    if (leftMin <= rightMin && leftMax > rightMin)
     430        return true;
     431    if (rightMin <= leftMin && rightMax > leftMin)
     432        return true;
     433    return false;
     434}
     435
    422436// Pass ranges with the min being inclusive and the max being exclusive. For example, this should
    423437// return false:
    … …  
    435449    if (rightMin == rightMax)
    436450        return false;
    437    
    438     if (leftMin <= rightMin && leftMax > rightMin)
    439         return true;
    440     if (rightMin <= leftMin && rightMax > leftMin)
    441         return true;
    442     return false;
     451
     452    return nonEmptyRangesOverlap(leftMin, leftMax, rightMin, rightMax);
    443453}
    444454

  • trunk/Source/WTF/wtf/StdLibExtras.h

    r194784 r195417  
    11/*
    2  * Copyright (C) 2008 Apple Inc. All Rights Reserved.
     2 * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
    33 * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
    44 *
    … …  
    213213    }
    214214   
    215     if (mode == KeyMightNotBePresentInArray && !size)
     215    if (mode != KeyMustBePresentInArray && !size)
    216216        return 0;
    217217   
    … …  
    231231// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
    232232template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    233 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
     233inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
    234234{
    235235    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
    … …  
    238238// Return zero if the element is not found.
    239239template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    240 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
     240inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
    241241{
    242242    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
    … …  
    245245// Return the element that is either to the left, or the right, of where the element would have been found.
    246246template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    247 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
     247inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
    248248{
    249249    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
    … …  
    252252// Variants of the above that use const.
    253253template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    254 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
     254inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
    255255{
    256256    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
    257257}
    258258template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    259 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
     259inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
    260260{
    261261    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
    262262}
    263263template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    264 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
     264inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
    265265{
    266266    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
Note: See TracChangeset for help on using the changeset viewer.