[webkit-changes] [WebKit/WebKit] 22ac06: [JSC] Loop unrolling

Thu Dec 5 05:17:35 PST 2024

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 22ac06375c5a827734a281c528a643815c847589
      https://github.com/WebKit/WebKit/commit/22ac06375c5a827734a281c528a643815c847589
  Author: Yijia Huang <yijia_huang at apple.com>
  Date:   2024-12-05 (Thu, 05 Dec 2024)

  Changed paths:
    A JSTests/microbenchmarks/loop-unrolling-1.js
    A JSTests/microbenchmarks/loop-unrolling-2.js
    A JSTests/microbenchmarks/loop-unrolling-3.js
    A JSTests/microbenchmarks/loop-unrolling-4.js
    A JSTests/microbenchmarks/loop-unrolling-array-clone-big.js
    A JSTests/microbenchmarks/loop-unrolling-array-clone-small.js
    A JSTests/microbenchmarks/loop-unrolling-constant-small.js
    A JSTests/microbenchmarks/loop-unrolling-core-sha1.js
    A JSTests/microbenchmarks/loop-unrolling-variable-large.js
    A JSTests/microbenchmarks/loop-unrolling-variable-medium-dep.js
    A JSTests/microbenchmarks/loop-unrolling-variable-medium.js
    A JSTests/microbenchmarks/loop-unrolling-variable-small.js
    A JSTests/stress/loop-unrolling-osr-exit.js
    A JSTests/stress/loop-unrolling-overflow.js
    A JSTests/stress/loop-unrolling.js
    M Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
    M Source/JavaScriptCore/Sources.txt
    M Source/JavaScriptCore/b3/B3SparseCollection.h
    M Source/JavaScriptCore/dfg/DFGBasicBlock.h
    M Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h
    M Source/JavaScriptCore/dfg/DFGGraph.h
    A Source/JavaScriptCore/dfg/DFGLoopUnrollingPhase.cpp
    A Source/JavaScriptCore/dfg/DFGLoopUnrollingPhase.h
    M Source/JavaScriptCore/dfg/DFGNode.h
    M Source/JavaScriptCore/dfg/DFGPlan.cpp
    M Source/JavaScriptCore/runtime/OptionsList.h

  Log Message:
  -----------
  [JSC] Loop unrolling
https://bugs.webkit.org/show_bug.cgi?id=265884
rdar://119195561

Reviewed by Yusuke Suzuki and Justin Michaud.

This patch, based on Justin's previous draft patch[1], adds a new loop
unrolling optimization phase to the FTL tier. The loop unrolling phase
enhances performance by reducing loop overhead in tightly nested loops
with a limited number of iterations, while maintaining the correctness
of the execution graph.

Changes:
* Introduced a new DFGLoopUnrollingPhase to optimize small, simple loops
  by unrolling them during DFG JIT compilation.
* Added infrastructure improvements in Graph, BasicBlock, and Node to
  facilitate cloning and unrolling.
* Integrated the phase into the DFG pipeline with configurable options
  (useLoopUnrolling, verboseLoopUnrolling, printEachUnrolledLoop).
* Added benchmarks to validate correctness and performance gains.

Future Work:
* Extend support to complex loops with nested structures and advanced
  control flows. See micro-benchmarks tests in [1].
* Enhance unrolling profitability metrics and speculative optimizations
  for dynamic iteration counts.
* Measure performance impact in real-world scenarios and expand profiling
  capabilities.

Microbenchmark Results:
                                              before                    after

Benchmarks with progressions:

loop-unrolling-1                          2.7693+-0.0279     ^      2.5839+-0.0396        ^ definitely 1.0718x faster
loop-unrolling-2                          3.4357+-0.0358     ^      2.7861+-0.0379        ^ definitely 1.2332x faster
loop-unrolling-3                          2.9092+-0.0304     ^      2.6302+-0.0362        ^ definitely 1.1061x faster

Future work benchmarks:

loop-unrolling-4                          3.1286+-0.0442            3.0581+-0.0490          might be 1.0230x faster
loop-unrolling-array-clone-small          0.8926+-0.0082            0.8918+-0.0082
loop-unrolling-core-sha1                  0.3992+-0.0066            0.3919+-0.0071          might be 1.0188x faster
loop-unrolling-variable-medium            5.9324+-0.0327            5.8792+-0.0220
loop-unrolling-variable-medium-dep        8.3997+-0.7200            8.1726+-0.6305          might be 1.0278x faster
loop-unrolling-array-clone-big            0.8996+-0.0095            0.8941+-0.0099
loop-unrolling-constant-small             0.4556+-0.0080            0.4506+-0.0119          might be 1.0111x faster
loop-unrolling-variable-large            53.8354+-0.0943           53.7705+-0.0802
loop-unrolling-variable-small             0.4518+-0.0075            0.4502+-0.0078

[1] https://github.com/WebKit/WebKit/pull/21342

* JSTests/microbenchmarks/loop-unrolling-1.js: Added.
(assert):
(test):
* JSTests/microbenchmarks/loop-unrolling-2.js: Added.
(assert):
(test):
* JSTests/microbenchmarks/loop-unrolling-3.js: Added.
(assert):
(test):
* JSTests/microbenchmarks/loop-unrolling-4.js: Added.
(assert):
(test):
* Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:
* Source/JavaScriptCore/Sources.txt:
* Source/JavaScriptCore/b3/B3SparseCollection.h:
(JSC::B3::SparseCollection::addNew):
* Source/JavaScriptCore/dfg/DFGBasicBlock.h:
* Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h:
(JSC::DFG::BasicBlock::appendNode):
* Source/JavaScriptCore/dfg/DFGGraph.h:
* Source/JavaScriptCore/dfg/DFGLoopUnrollingPhase.cpp: Added.
(JSC::DFG::LoopUnrollingPhase::LoopData::header const):
(JSC::DFG::LoopUnrollingPhase::LoopData::condition const):
(JSC::DFG::LoopUnrollingPhase::LoopData::isInductionVariable):
(JSC::DFG::LoopUnrollingPhase::LoopUnrollingPhase):
(JSC::DFG::LoopUnrollingPhase::run):
(JSC::DFG::LoopUnrollingPhase::selectDeepestNestedLoop):
(JSC::DFG::LoopUnrollingPhase::tryUnroll):
(JSC::DFG::LoopUnrollingPhase::locatePreHeader):
(JSC::DFG::LoopUnrollingPhase::locateTail):
(JSC::DFG::LoopUnrollingPhase::identifyInductionVariable):
(JSC::DFG::LoopUnrollingPhase::isValid):
(JSC::DFG::LoopUnrollingPhase::makeBlock):
(JSC::DFG::LoopUnrollingPhase::unrollLoop):
(JSC::DFG::performLoopUnrolling):
(JSC::DFG::LoopUnrollingPhase::LoopData::dump const):
(JSC::DFG::LoopUnrollingPhase::isNodeCloneable):
(JSC::DFG::LoopUnrollingPhase::cloneNode):
(JSC::DFG::LoopUnrollingPhase::cloneNodeImpl):
(JSC::DFG::LoopUnrollingPhase::isSupportedConditionOp):
(JSC::DFG::LoopUnrollingPhase::isSupportedUpdateOp):
(JSC::DFG::std::function<bool):
(JSC::DFG::std::function<CheckedInt32):
* Source/JavaScriptCore/dfg/DFGLoopUnrollingPhase.h: Copied from Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h.
* Source/JavaScriptCore/dfg/DFGNode.h:
(JSC::DFG::Node::setOpInfo):
* Source/JavaScriptCore/dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* Source/JavaScriptCore/runtime/OptionsList.h:

Canonical link: https://commits.webkit.org/287398@main

To unsubscribe from these emails, change your notification settings at https://github.com/WebKit/WebKit/settings/notifications