Changeset 214827 in webkit


Ignore:
Timestamp:
Apr 3, 2017 11:55:34 AM (7 years ago)
Author:
fpizlo@apple.com
Message:

Inst::forEachArg could compile to more compact code
​https://bugs.webkit.org/show_bug.cgi?id=170406

Reviewed by Sam Weinig.

Prior to this change, Inst::forEachArg compiled to a ginormous ALWAYS_INLINE switch statement.
It had one case for each opcode, and then each of those cases would have a switch statement over
the number of operands. Then the cases of that switch statement would have a sequence of calls to
the passed lambda. This meant that every user of forEachArg would generate an insane amount of
code. It also meant that the inlining achieved nothing, since the lambda would surely then not
be inlined - and if it was, then the icache pressure due to code bloat would surely negate any
benefits.

This replaces that code with a loop over a compact look-up table. We use the opcode and number of
operands as keys into that look-up table. The table only takes about 20KB. It has one byte for
each argument in each overload of each opcode.

I can't measure any reproducible change in performance, but the JavaScriptCore framework binary
shrinks by 2.7 MB. This is a 15% reduction in JavaScriptCore binary size.

  • JavaScriptCore.xcodeproj/project.pbxproj:
  • b3/B3Width.h:
  • b3/air/AirCustom.h:

(JSC::B3::Air::PatchCustom::forEachArg):

  • b3/air/AirFormTable.h: Added.

(JSC::B3::Air::decodeFormRole):
(JSC::B3::Air::decodeFormBank):
(JSC::B3::Air::decodeFormWidth):

  • b3/air/AirInst.h:
  • b3/air/opcode_generator.rb:
Location:
trunk/Source/JavaScriptCore
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r214826 r214827  
     12017-04-03  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Inst::forEachArg could compile to more compact code
     4        https://bugs.webkit.org/show_bug.cgi?id=170406
     5
     6        Reviewed by Sam Weinig.
     7       
     8        Prior to this change, Inst::forEachArg compiled to a ginormous ALWAYS_INLINE switch statement.
     9        It had one case for each opcode, and then each of those cases would have a switch statement over
     10        the number of operands. Then the cases of that switch statement would have a sequence of calls to
     11        the passed lambda. This meant that every user of forEachArg would generate an insane amount of
     12        code. It also meant that the inlining achieved nothing, since the lambda would surely then not
     13        be inlined - and if it was, then the icache pressure due to code bloat would surely negate any
     14        benefits.
     15       
     16        This replaces that code with a loop over a compact look-up table. We use the opcode and number of
     17        operands as keys into that look-up table. The table only takes about 20KB. It has one byte for
     18        each argument in each overload of each opcode.
     19       
     20        I can't measure any reproducible change in performance, but the JavaScriptCore framework binary
     21        shrinks by 2.7 MB. This is a 15% reduction in JavaScriptCore binary size.
     22
     23        * JavaScriptCore.xcodeproj/project.pbxproj:
     24        * b3/B3Width.h:
     25        * b3/air/AirCustom.h:
     26        (JSC::B3::Air::PatchCustom::forEachArg):
     27        * b3/air/AirFormTable.h: Added.
     28        (JSC::B3::Air::decodeFormRole):
     29        (JSC::B3::Air::decodeFormBank):
     30        (JSC::B3::Air::decodeFormWidth):
     31        * b3/air/AirInst.h:
     32        * b3/air/opcode_generator.rb:
     33
    1342017-04-03  Keith Miller  <keith_miller@apple.com>
    235

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

    r214645 r214827  
    190190                0F2AC56E1E8D7B000001EE3F /* AirPhaseInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2AC56C1E8D7AFF0001EE3F /* AirPhaseInsertionSet.cpp */; };
    191191                0F2AC56F1E8D7B030001EE3F /* AirPhaseInsertionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2AC56D1E8D7AFF0001EE3F /* AirPhaseInsertionSet.h */; };
     192                0F2AC5711E8EE4540001EE3F /* AirFormTable.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2AC5701E8EE4520001EE3F /* AirFormTable.h */; };
    192193                0F2B66AC17B6B53F00A7AE3F /* GCIncomingRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A817B6B53D00A7AE3F /* GCIncomingRefCounted.h */; settings = {ATTRIBUTES = (Private, ); }; };
    193194                0F2B66AD17B6B54500A7AE3F /* GCIncomingRefCountedInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A917B6B53D00A7AE3F /* GCIncomingRefCountedInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    27242725                0F2AC56C1E8D7AFF0001EE3F /* AirPhaseInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirPhaseInsertionSet.cpp; path = b3/air/AirPhaseInsertionSet.cpp; sourceTree = "<group>"; };
    27252726                0F2AC56D1E8D7AFF0001EE3F /* AirPhaseInsertionSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirPhaseInsertionSet.h; path = b3/air/AirPhaseInsertionSet.h; sourceTree = "<group>"; };
     2727                0F2AC5701E8EE4520001EE3F /* AirFormTable.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirFormTable.h; path = b3/air/AirFormTable.h; sourceTree = "<group>"; };
    27262728                0F2B66A817B6B53D00A7AE3F /* GCIncomingRefCounted.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = GCIncomingRefCounted.h; sourceTree = "<group>"; };
    27272729                0F2B66A917B6B53D00A7AE3F /* GCIncomingRefCountedInlines.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = GCIncomingRefCountedInlines.h; sourceTree = "<group>"; };
    … …  
    55935595                                0F2AC5641E8A0B760001EE3F /* AirFixSpillsAfterTerminals.cpp */,
    55945596                                0F2AC5651E8A0B760001EE3F /* AirFixSpillsAfterTerminals.h */,
     5597                                0F2AC5701E8EE4520001EE3F /* AirFormTable.h */,
    55955598                                0FEC85521BDACDC70080FF74 /* AirFrequentedBlock.h */,
    55965599                                0FEC85531BDACDC70080FF74 /* AirGenerate.cpp */,
    … …  
    93379340                                0FB7F39D15ED8E4600F167B2 /* TypeError.h in Headers */,
    93389341                                0F2D4DEA19832DAC007D4B19 /* TypeLocation.h in Headers */,
     9342                                0F2AC5711E8EE4540001EE3F /* AirFormTable.h in Headers */,
    93399343                                52B311011975B4670080857C /* TypeLocationCache.h in Headers */,
    93409344                                0FFB6C391AF48DDC00DB1BF7 /* TypeofType.h in Headers */,

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

    r213714 r214827  
    5151    return Width32;
    5252}
     53
     54// Don't use this unless the compiler forces you to.
     55#if CPU(X86_64) || CPU(ARM64)
     56#define POINTER_WIDTH Width64
     57#else
     58#define POINTER_WIDTH Width32
     59#endif
    5360
    5461inline Width widthForType(Type type)

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

    r212970 r214827  
    5858// Special object, which will be the first argument to the instruction.
    5959struct PatchCustom {
    60     template<typename Functor>
    61     static void forEachArg(Inst& inst, const Functor& functor)
     60    static void forEachArg(Inst& inst, ScopedLambda<Inst::EachArgCallback> lambda)
    6261    {
    6362        // This is basically bogus, but it works for analyses that model Special as an
    6463        // immediate.
    65         functor(inst.args[0], Arg::Use, GP, pointerWidth());
     64        lambda(inst.args[0], Arg::Use, GP, pointerWidth());
    6665       
    67         inst.args[0].special()->forEachArg(inst, scopedLambda<Inst::EachArgCallback>(functor));
     66        inst.args[0].special()->forEachArg(inst, lambda);
    6867    }
    6968

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

    r214187 r214827  
    4646
    4747struct Inst {
    48 public:
    4948    typedef Vector<Arg, 3> ArgList;
    5049
    … …  
    208207    Value* origin; // The B3::Value that this originated from.
    209208    Kind kind;
     209
     210private:
     211    template<typename Func>
     212    void forEachArgSimple(const Func&);
     213    void forEachArgCustom(ScopedLambda<EachArgCallback>);
    210214};
    211215

  • trunk/Source/JavaScriptCore/b3/air/opcode_generator.rb

    r213714 r214827  
    5555    def self.widthCode(width)
    5656        if width == "Ptr"
    57             "pointerWidth()"
     57            "POINTER_WIDTH"
    5858        else
    5959            "Width#{width}"
    … …  
    9494    def roleCode
    9595        Arg.roleCode(role)
     96    end
     97   
     98    def to_s
     99        "#{role}:#{bank}:#{width}"
    96100    end
    97101end
    … …  
    515519    outp.puts "namespace JSC { namespace B3 { namespace Air {"
    516520    outp.puts "enum Opcode : int16_t {"
    517     $opcodes.keys.sort.each {
     521    $opcodes.keys.each {
    518522        | opcode |
    519523        outp.puts "    #{opcode},"
    … …  
    646650end
    647651
     652maxNumOperands = 0
     653$opcodes.values.each {
     654    | opcode |
     655    next if opcode.custom
     656    opcode.overloads.each {
     657        | overload |
     658        maxNumOperands = overload.signature.length if overload.signature.length > maxNumOperands
     659    }
     660}
     661
     662formTableWidth = (maxNumOperands + 1) * maxNumOperands / 2
     663
    648664writeH("OpcodeUtils") {
    649665    | outp |
    650666    outp.puts "#include \"AirCustom.h\""
    651667    outp.puts "#include \"AirInst.h\""
     668    outp.puts "#include \"AirFormTable.h\""
    652669    outp.puts "namespace JSC { namespace B3 { namespace Air {"
    653670   
    … …  
    661678
    662679    outp.puts "template<typename Functor>"
    663     outp.puts "void Inst::forEachArg(const Functor& functor)"
     680    outp.puts "ALWAYS_INLINE void Inst::forEachArg(const Functor& functor)"
    664681    outp.puts "{"
    665     matchInstOverload(outp, :fast, "this") {
    666         | opcode, overload |
     682    outp.puts "switch (kind.opcode) {"
     683    $opcodes.values.each {
     684        | opcode |
    667685        if opcode.custom
    668             outp.puts "#{opcode.name}Custom::forEachArg(*this, functor);"
    669         else
    670             overload.signature.each_with_index {
    671                 | arg, index |
    672                 outp.puts "functor(args[#{index}], Arg::#{arg.roleCode}, #{arg.bank}P, #{arg.widthCode});"
    673             }
    674         end
    675     }
     686            outp.puts "case Opcode::#{opcode.name}:"
     687        end
     688    }
     689    outp.puts "forEachArgCustom(scopedLambdaRef<EachArgCallback>(functor));"
     690    outp.puts "return;"
     691    outp.puts "default:"
     692    outp.puts "forEachArgSimple(functor);"
     693    outp.puts "return;"
     694    outp.puts "}"
     695    outp.puts "}"
     696   
     697    outp.puts "template<typename Func>"
     698    outp.puts "ALWAYS_INLINE void Inst::forEachArgSimple(const Func& func)"
     699    outp.puts "{"
     700    outp.puts "    size_t numOperands = args.size();"
     701    outp.puts "    size_t formOffset = (numOperands - 1) * numOperands / 2;"
     702    outp.puts "    uint8_t* formBase = g_formTable + kind.opcode * #{formTableWidth} + formOffset;"
     703    outp.puts "    for (size_t i = 0; i < numOperands; ++i) {"
     704    outp.puts "        uint8_t form = formBase[i];"
     705    outp.puts "        ASSERT(!(form & (1 << formInvalidShift)));"
     706    outp.puts "        func(args[i], decodeFormRole(form), decodeFormBank(form), decodeFormWidth(form));"
     707    outp.puts "    }"
    676708    outp.puts "}"
    677709
    … …  
    790822    outp.puts "} // namespace WTF"
    791823    outp.puts "namespace JSC { namespace B3 { namespace Air {"
     824   
     825    outp.puts "uint8_t g_formTable[#{$opcodes.size * formTableWidth}] = {"
     826    $opcodes.values.each {
     827        | opcode |
     828        overloads = [nil] * (maxNumOperands + 1)
     829        unless opcode.custom
     830            opcode.overloads.each {
     831                | overload |
     832                overloads[overload.signature.length] = overload
     833            }
     834        end
     835       
     836        (0..maxNumOperands).each {
     837            | numOperands |
     838            overload = overloads[numOperands]
     839            if overload
     840                outp.puts "// #{opcode.name} #{overload.signature.join(', ')}"
     841                numOperands.times {
     842                    | index |
     843                    arg = overload.signature[index]
     844                    outp.print "ENCODE_INST_FORM(Arg::#{arg.roleCode}, #{arg.bank}P, #{arg.widthCode}), "
     845                }
     846            else
     847                outp.puts "// Invalid: #{opcode.name} with numOperands = #{numOperands}"
     848                numOperands.times {
     849                    outp.print "INVALID_INST_FORM, "
     850                }
     851            end
     852            outp.puts
     853        }
     854    }
     855    outp.puts "};"
     856   
     857    outp.puts "void Inst::forEachArgCustom(ScopedLambda<EachArgCallback> lambda)"
     858    outp.puts "{"
     859    outp.puts "switch (kind.opcode) {"
     860    $opcodes.values.each {
     861        | opcode |
     862        if opcode.custom
     863            outp.puts "case Opcode::#{opcode.name}:"
     864            outp.puts "#{opcode.name}Custom::forEachArg(*this, lambda);"
     865            outp.puts "break;"
     866        end
     867    }
     868    outp.puts "default:"
     869    outp.puts "dataLog(\"Bad call to forEachArgCustom, not custom opcode: \", kind, \"\\n\");"
     870    outp.puts "RELEASE_ASSERT_NOT_REACHED();"
     871    outp.puts "}"
     872    outp.puts "}"
     873   
    792874    outp.puts "bool Inst::isValidForm()"
    793875    outp.puts "{"
    … …  
    11411223}
    11421224
    1143 # This is a hack for JSAir. It's a joke.
    1144 File.open("JSAir_opcode.js", "w") {
    1145     | outp |
    1146     outp.puts "\"use strict\";"
    1147     outp.puts "// Generated by opcode_generator.rb from #{$fileName} -- do not edit!"
    1148    
    1149     $opcodes.values.each {
    1150         | opcode |
    1151         outp.puts "const #{opcode.name} = Symbol(#{opcode.name.inspect});"
    1152     }
    1153    
    1154     outp.puts "function Inst_forEachArg(inst, func)"
    1155     outp.puts "{"
    1156     outp.puts "let replacement;"
    1157     outp.puts "switch (inst.opcode) {"
    1158     $opcodes.values.each {
    1159         | opcode |
    1160         outp.puts "case Opcode::#{opcode.name}:"
    1161         if opcode.custom
    1162             outp.puts "#{opcode.name}Custom.forEachArg(inst, func);"
    1163         else
    1164             needOverloadSwitch = opcode.overloads.size != 1
    1165             outp.puts "switch (inst.args.length) {" if needOverloadSwitch
    1166             opcode.overloads.each {
    1167                 | overload |
    1168                 outp.puts "case #{overload.signature.length}:" if needOverloadSwitch
    1169                 overload.signature.each_with_index {
    1170                     | arg, index |
    1171                     outp.puts "inst.visitArg(#{index}, func, Arg.#{arg.roleCode}, #{arg.bank}P, #{arg.width});"
    1172                 }
    1173                 outp.puts "break;"
    1174             }
    1175             if needOverloadSwitch
    1176                 outp.puts "default:"
    1177                 outp.puts "throw new Error(\"Bad overload\");"
    1178                 outp.puts "break;"
    1179                 outp.puts "}"
    1180             end
    1181         end
    1182         outp.puts "break;"
    1183     }
    1184     outp.puts "default:"
    1185     outp.puts "throw \"Bad opcode\";"
    1186     outp.puts "}"
    1187     outp.puts "}"
    1188    
    1189     outp.puts "function Inst_hasNonArgEffects(inst)"
    1190     outp.puts "{"
    1191     outp.puts "switch (inst.opcode) {"
    1192     foundTrue = false
    1193     $opcodes.values.each {
    1194         | opcode |
    1195         if opcode.attributes[:terminal] or opcode.attributes[:effects]
    1196             outp.puts "case Opcode::#{opcode.name}:"
    1197             foundTrue = true
    1198         end
    1199     }
    1200     if foundTrue
    1201         outp.puts "return true;"
    1202     end
    1203     $opcodes.values.each {
    1204         | opcode |
    1205         if opcode.custom
    1206             outp.puts "case Opcode::#{opcode.name}:"
    1207             outp.puts "return #{opcode.name}Custom.hasNonArgNonControlEffects(inst);"
    1208         end
    1209     }
    1210     outp.puts "default:"
    1211     outp.puts "return false;"
    1212     outp.puts "}"
    1213     outp.puts "}"
    1214    
    1215     outp.puts "function opcodeCode(opcode)"
    1216     outp.puts "{"
    1217     outp.puts "switch (opcode) {"
    1218     $opcodes.keys.sort.each_with_index {
    1219         | opcode, index |
    1220         outp.puts "case Opcode::#{opcode}:"
    1221         outp.puts "return #{index}"
    1222     }
    1223     outp.puts "default:"
    1224     outp.puts "throw new Error(\"bad opcode\");"
    1225     outp.puts "}"
    1226     outp.puts "}"
    1227 }
    1228 
Note: See TracChangeset for help on using the changeset viewer.