Changeset 192292 in webkit


Ignore:
Timestamp:
Nov 10, 2015 9:10:43 PM (8 years ago)
Author:
benjamin@webkit.org
Message:

Air should allocate registers
​https://bugs.webkit.org/show_bug.cgi?id=150457

Patch by Benjamin Poulain <​bpoulain@apple.com> on 2015-11-10
Reviewed by Filip Pizlo.

This is a direct implementation of the Iterated Register Coalescing allocator.

(JSC::B3::Air::generate):

  • b3/air/AirInstInlines.h:
  • b3/air/AirIteratedRegisterCoalescing.cpp: Added.

(JSC::B3::Air::MoveInstHelper<Arg::GP>::mayBeCoalescable):
(JSC::B3::Air::MoveInstHelper<Arg::FP>::mayBeCoalescable):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::absoluteIndex):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::tmpFromAbsoluteIndex):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::absoluteIndex):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::tmpFromAbsoluteIndex):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::IteratedRegisterCoalescingAllocator):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocate):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAlias):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::spilledTmp):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocatedReg):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::tmpArraySize):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::initializeDegrees):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdges):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdge):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::makeWorkList):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::simplify):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachAdjacent):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::hasBeenSimplified):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::decrementDegree):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachNodeMoves):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::isMoveRelated):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValue):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValueAndAdjacents):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::canBeSafelyCoalesced):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::precoloredCoalescingHeuristic):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::conservativeHeuristic):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::addWorkList):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freeze):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpInterferenceGraphInDot):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpWorkLists):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::InterferenceEdge):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::first):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::second):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::operator==):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::isHashTableDeletedValue):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::hash):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::hash):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::equal):
(JSC::B3::Air::isUselessMoveInst):
(JSC::B3::Air::assignRegisterToTmpInProgram):
(JSC::B3::Air::addSpillAndFillToProgram):
(JSC::B3::Air::iteratedRegisterCoalescingOnType):
(JSC::B3::Air::iteratedRegisterCoalescing):

  • b3/air/AirIteratedRegisterCoalescing.h: Added.
  • b3/air/AirTmp.h:

(JSC::B3::Air::Tmp::internalValue):
(JSC::B3::Air::Tmp::tmpForInternalValue):

  • b3/testb3.cpp:

(JSC::B3::testSpillGP):
(JSC::B3::run):

Location:
trunk/Source/JavaScriptCore
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r192291 r192292  
     12015-11-10  Benjamin Poulain  <bpoulain@apple.com>
     2
     3        Air should allocate registers
     4        https://bugs.webkit.org/show_bug.cgi?id=150457
     5
     6        Reviewed by Filip Pizlo.
     7
     8        This is a direct implementation of the Iterated Register Coalescing allocator.
     9
     10        * JavaScriptCore.xcodeproj/project.pbxproj:
     11        * b3/air/AirGenerate.cpp:
     12        (JSC::B3::Air::generate):
     13        * b3/air/AirInstInlines.h:
     14        * b3/air/AirIteratedRegisterCoalescing.cpp: Added.
     15        (JSC::B3::Air::MoveInstHelper<Arg::GP>::mayBeCoalescable):
     16        (JSC::B3::Air::MoveInstHelper<Arg::FP>::mayBeCoalescable):
     17        (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::absoluteIndex):
     18        (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::tmpFromAbsoluteIndex):
     19        (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::absoluteIndex):
     20        (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::tmpFromAbsoluteIndex):
     21        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::IteratedRegisterCoalescingAllocator):
     22        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
     23        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocate):
     24        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAlias):
     25        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::spilledTmp):
     26        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocatedReg):
     27        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::tmpArraySize):
     28        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::initializeDegrees):
     29        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdges):
     30        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdge):
     31        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::makeWorkList):
     32        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::simplify):
     33        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachAdjacent):
     34        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::hasBeenSimplified):
     35        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::decrementDegree):
     36        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachNodeMoves):
     37        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::isMoveRelated):
     38        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValue):
     39        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValueAndAdjacents):
     40        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
     41        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::canBeSafelyCoalesced):
     42        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::precoloredCoalescingHeuristic):
     43        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::conservativeHeuristic):
     44        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addWorkList):
     45        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
     46        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freeze):
     47        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
     48        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
     49        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
     50        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpInterferenceGraphInDot):
     51        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpWorkLists):
     52        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::InterferenceEdge):
     53        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::first):
     54        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::second):
     55        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::operator==):
     56        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::isHashTableDeletedValue):
     57        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::hash):
     58        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::hash):
     59        (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::equal):
     60        (JSC::B3::Air::isUselessMoveInst):
     61        (JSC::B3::Air::assignRegisterToTmpInProgram):
     62        (JSC::B3::Air::addSpillAndFillToProgram):
     63        (JSC::B3::Air::iteratedRegisterCoalescingOnType):
     64        (JSC::B3::Air::iteratedRegisterCoalescing):
     65        * b3/air/AirIteratedRegisterCoalescing.h: Added.
     66        * b3/air/AirTmp.h:
     67        (JSC::B3::Air::Tmp::internalValue):
     68        (JSC::B3::Air::Tmp::tmpForInternalValue):
     69        * b3/testb3.cpp:
     70        (JSC::B3::testSpillGP):
     71        (JSC::B3::run):
     72
    1732015-11-10  Filip Pizlo  <fpizlo@apple.com>
    274

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

    r192273 r192292  
    10751075                2600B5A6152BAAA70091EE5F /* JSStringJoiner.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2600B5A4152BAAA70091EE5F /* JSStringJoiner.cpp */; };
    10761076                2600B5A7152BAAA70091EE5F /* JSStringJoiner.h in Headers */ = {isa = PBXBuildFile; fileRef = 2600B5A5152BAAA70091EE5F /* JSStringJoiner.h */; };
     1077                26718BA41BE99F780052017B /* AirIteratedRegisterCoalescing.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */; };
     1078                26718BA51BE99F780052017B /* AirIteratedRegisterCoalescing.h in Headers */ = {isa = PBXBuildFile; fileRef = 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */; };
    10771079                2A05ABD51961DF2400341750 /* JSPropertyNameEnumerator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */; };
    10781080                2A05ABD61961DF2400341750 /* JSPropertyNameEnumerator.h in Headers */ = {isa = PBXBuildFile; fileRef = 2A05ABD41961DF2400341750 /* JSPropertyNameEnumerator.h */; };
    … …  
    30843086                2600B5A5152BAAA70091EE5F /* JSStringJoiner.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSStringJoiner.h; sourceTree = "<group>"; };
    30853087                264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */ = {isa = PBXFileReference; lastKnownFileType = text; name = AirOpcode.opcodes; path = b3/air/AirOpcode.opcodes; sourceTree = "<group>"; };
     3088                26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirIteratedRegisterCoalescing.cpp; path = b3/air/AirIteratedRegisterCoalescing.cpp; sourceTree = "<group>"; };
     3089                26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirIteratedRegisterCoalescing.h; path = b3/air/AirIteratedRegisterCoalescing.h; sourceTree = "<group>"; };
    30863090                2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSPropertyNameEnumerator.cpp; sourceTree = "<group>"; };
    30873091                2A05ABD41961DF2400341750 /* JSPropertyNameEnumerator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSPropertyNameEnumerator.h; sourceTree = "<group>"; };
    … …  
    45674571                                0FEC855B1BDACDC70080FF74 /* AirInst.h */,
    45684572                                0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */,
     4573                                26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */,
     4574                                26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */,
    45694575                                0FEC855D1BDACDC70080FF74 /* AirLiveness.h */,
    45704576                                264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
    … …  
    66536659                                0FEC851A1BDACDAC0080FF74 /* B3GenericFrequentedBlock.h in Headers */,
    66546660                                0FEC85C31BE167A00080FF74 /* B3HeapRange.h in Headers */,
     6661                                26718BA51BE99F780052017B /* AirIteratedRegisterCoalescing.h in Headers */,
    66556662                                0FEC851B1BDACDAC0080FF74 /* B3IndexMap.h in Headers */,
    66566663                                0FEC851C1BDACDAC0080FF74 /* B3IndexSet.h in Headers */,
    … …  
    89108917                                7B39F76D1B62DE2E00360FB4 /* WASMModuleParser.cpp in Sources */,
    89118918                                7B39F7721B63574D00360FB4 /* WASMReader.cpp in Sources */,
     8919                                26718BA41BE99F780052017B /* AirIteratedRegisterCoalescing.cpp in Sources */,
    89128920                                FED94F2E171E3E2300BE77A4 /* Watchdog.cpp in Sources */,
    89138921                                0F919D2515853CE0004A4E7D /* Watchpoint.cpp in Sources */,

  • trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp

    r192121 r192292  
    3434#include "AirGenerationContext.h"
    3535#include "AirHandleCalleeSaves.h"
     36#include "AirIteratedRegisterCoalescing.h"
    3637#include "AirReportUsedRegisters.h"
    3738#include "AirSimplifyCFG.h"
    … …  
    6970    // This is where we would have a real register allocator. Then, we could use spillEverything()
    7071    // in place of the register allocator only for testing.
    71     // FIXME: https://bugs.webkit.org/show_bug.cgi?id=150457
    72     spillEverything(code);
     72    iteratedRegisterCoalescing(code);
    7373
    7474    // Prior to this point the prologue and epilogue is implicit. This makes it explicit. It also

  • trunk/Source/JavaScriptCore/b3/air/AirInstInlines.h

    r192291 r192292  
    6868               
    6969                functor(stackSlot, role, type);
    70                 arg = Arg::stack(stackSlot);
     70                arg = Arg::stack(stackSlot, arg.offset());
    7171            });
    7272    }

  • trunk/Source/JavaScriptCore/b3/air/AirTmp.h

    r191705 r192292  
    173173        return WTF::IntHash<int>::hash(m_value);
    174174    }
    175    
     175
     176    unsigned internalValue() const { return static_cast<unsigned>(m_value); }
     177
     178    static Tmp tmpForInternalValue(unsigned index)
     179    {
     180        Tmp result;
     181        result.m_value = static_cast<int>(index);
     182        return result;
     183    }
     184
    176185private:
    177186    static int encodeGP(unsigned index)

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

    r192257 r192292  
    18071807        CHECK(compileAndRun<int32_t>(proc, &value - 2, (sizeof(int32_t) * 2) >> logScale) == modelLoad<T>(value));
    18081808    }
     1809}
     1810
     1811void testSpillGP()
     1812{
     1813    Procedure proc;
     1814    BasicBlock* root = proc.addBlock();
     1815
     1816    Vector<Value*> sources;
     1817    sources.append(root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
     1818    sources.append(root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1));
     1819
     1820    for (unsigned i = 0; i < 30; ++i) {
     1821        sources.append(
     1822            root->appendNew<Value>(proc, Add, Origin(), sources[sources.size() - 1], sources[sources.size() - 2])
     1823        );
     1824    }
     1825
     1826    Value* total = root->appendNew<Const64Value>(proc, Origin(), 0);
     1827    for (Value* value : sources)
     1828        total = root->appendNew<Value>(proc, Add, Origin(), total, value);
     1829
     1830    root->appendNew<ControlValue>(proc, Return, Origin(), total);
     1831    compileAndRun<int>(proc, 1, 2);
    18091832}
    18101833
    … …  
    33033326    RUN(testLoad<uint16_t>(Load16Z, -1000000000));
    33043327
     3328    RUN(testSpillGP());
     3329
    33053330    RUN(testCallSimple(1, 2));
    33063331    RUN(testCallFunctionWithHellaArguments());
Note: See TracChangeset for help on using the changeset viewer.