B3 should have load elimination
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jan 2016 19:54:51 +0000 (19:54 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jan 2016 19:54:51 +0000 (19:54 +0000)
commit72b1502731aa6e28585edd29e54b554ead4bfa20
treee8eb11ff510b0f6926d99c837284ce01bbd4d433
parent4c3eaea00e2bf6fd60593df1334027ad127df1b1
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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@195417 268f45cc-cd09-0410-ab3c-d52691b4dbfc
20 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3Generate.cpp
Source/JavaScriptCore/b3/B3HeapRange.h
Source/JavaScriptCore/b3/B3InsertionSet.h
Source/JavaScriptCore/b3/B3MemoryValue.h
Source/JavaScriptCore/b3/B3PureCSE.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3PureCSE.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3ReduceStrength.cpp
Source/JavaScriptCore/b3/B3ReduceStrength.h
Source/JavaScriptCore/b3/B3Validate.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/MathExtras.h
Source/WTF/wtf/RangeSet.h [new file with mode: 0644]
Source/WTF/wtf/StdLibExtras.h