<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[191846] trunk/Source/JavaScriptCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/191846">191846</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-10-31 16:12:53 -0700 (Sat, 31 Oct 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Air should eliminate dead code
https://bugs.webkit.org/show_bug.cgi?id=150746
Reviewed by Geoffrey Garen.
This adds a very simple dead code elimination to Air. It simply looks at whether a Tmp or
StackSlot has ever been used by a live instruction. An instruction is live if it has non-arg
effects (branching, returning, calling, etc) or if it stores to a live Arg. An Arg is live if
it references a live Tmp or StackSlot, or if it is neither a Tmp nor a StackSlot. The phase
runs these rules to fixpoint, and then removes the dead instructions.
This also changes the AirOpcodes parser to handle multiple attributes per opcode, so that we
could conceivably say things like "FooBar /branch /effects". It also adds the /effects
attribute, which we currently use for Breakpoint and nothing else. C calls, patchpoints, and
checks are all Specials, and the Special base class by default always claims that the
instruction has effects. In the future, we could have B3 use a Patch in Air to implement
exotic math constructs; then the Special associated with that thing would claim that there
are no effects.
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/air/AirBasicBlock.h:
(JSC::B3::Air::BasicBlock::begin):
(JSC::B3::Air::BasicBlock::end):
(JSC::B3::Air::BasicBlock::at):
(JSC::B3::Air::BasicBlock::last):
(JSC::B3::Air::BasicBlock::resize):
(JSC::B3::Air::BasicBlock::appendInst):
* b3/air/AirEliminateDeadCode.cpp: Added.
(JSC::B3::Air::eliminateDeadCode):
* b3/air/AirEliminateDeadCode.h: Added.
* b3/air/AirGenerate.cpp:
(JSC::B3::Air::generate):
* b3/air/AirInst.h:
* b3/air/AirOpcode.opcodes:
* b3/air/AirSpecial.cpp:
(JSC::B3::Air::Special::name):
(JSC::B3::Air::Special::hasNonArgNonControlEffects):
(JSC::B3::Air::Special::dump):
* b3/air/AirSpecial.h:
* b3/air/opcode_generator.rb:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirBasicBlockh">trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirGeneratecpp">trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirInsth">trunk/Source/JavaScriptCore/b3/air/AirInst.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirOpcodeopcodes">trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirSpecialcpp">trunk/Source/JavaScriptCore/b3/air/AirSpecial.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirSpecialh">trunk/Source/JavaScriptCore/b3/air/AirSpecial.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airopcode_generatorrb">trunk/Source/JavaScriptCore/b3/air/opcode_generator.rb</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3airAirEliminateDeadCodecpp">trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirEliminateDeadCodeh">trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -1,3 +1,46 @@
</span><ins>+2015-10-30 Filip Pizlo <fpizlo@apple.com>
+
+ Air should eliminate dead code
+ https://bugs.webkit.org/show_bug.cgi?id=150746
+
+ Reviewed by Geoffrey Garen.
+
+ This adds a very simple dead code elimination to Air. It simply looks at whether a Tmp or
+ StackSlot has ever been used by a live instruction. An instruction is live if it has non-arg
+ effects (branching, returning, calling, etc) or if it stores to a live Arg. An Arg is live if
+ it references a live Tmp or StackSlot, or if it is neither a Tmp nor a StackSlot. The phase
+ runs these rules to fixpoint, and then removes the dead instructions.
+
+ This also changes the AirOpcodes parser to handle multiple attributes per opcode, so that we
+ could conceivably say things like "FooBar /branch /effects". It also adds the /effects
+ attribute, which we currently use for Breakpoint and nothing else. C calls, patchpoints, and
+ checks are all Specials, and the Special base class by default always claims that the
+ instruction has effects. In the future, we could have B3 use a Patch in Air to implement
+ exotic math constructs; then the Special associated with that thing would claim that there
+ are no effects.
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/air/AirBasicBlock.h:
+ (JSC::B3::Air::BasicBlock::begin):
+ (JSC::B3::Air::BasicBlock::end):
+ (JSC::B3::Air::BasicBlock::at):
+ (JSC::B3::Air::BasicBlock::last):
+ (JSC::B3::Air::BasicBlock::resize):
+ (JSC::B3::Air::BasicBlock::appendInst):
+ * b3/air/AirEliminateDeadCode.cpp: Added.
+ (JSC::B3::Air::eliminateDeadCode):
+ * b3/air/AirEliminateDeadCode.h: Added.
+ * b3/air/AirGenerate.cpp:
+ (JSC::B3::Air::generate):
+ * b3/air/AirInst.h:
+ * b3/air/AirOpcode.opcodes:
+ * b3/air/AirSpecial.cpp:
+ (JSC::B3::Air::Special::name):
+ (JSC::B3::Air::Special::hasNonArgNonControlEffects):
+ (JSC::B3::Air::Special::dump):
+ * b3/air/AirSpecial.h:
+ * b3/air/opcode_generator.rb:
+
</ins><span class="cx"> 2015-10-31 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Air needs a late register liveness phase that calls Special::reportUsedRegisters()
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -311,6 +311,8 @@
</span><span class="cx"> 0F426A491460CBB700131F8F /* VirtualRegister.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F426A461460CBAB00131F8F /* VirtualRegister.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F426A4B1460CD6E00131F8F /* DataFormat.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F426A4A1460CD6B00131F8F /* DataFormat.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F431738146BAC69007E3890 /* ListableHandler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F431736146BAC65007E3890 /* ListableHandler.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><ins>+ 0F4570381BE44C910062A629 /* AirEliminateDeadCode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4570361BE44C910062A629 /* AirEliminateDeadCode.cpp */; };
+ 0F4570391BE44C910062A629 /* AirEliminateDeadCode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570371BE44C910062A629 /* AirEliminateDeadCode.h */; };
</ins><span class="cx"> 0F45703C1BE45F0A0062A629 /* AirReportUsedRegisters.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F45703A1BE45F0A0062A629 /* AirReportUsedRegisters.cpp */; };
</span><span class="cx"> 0F45703D1BE45F0A0062A629 /* AirReportUsedRegisters.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F45703B1BE45F0A0062A629 /* AirReportUsedRegisters.h */; };
</span><span class="cx"> 0F46808214BA572D00BFE272 /* JITExceptions.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F46808014BA572700BFE272 /* JITExceptions.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="lines">@@ -2327,6 +2329,8 @@
</span><span class="cx"> 0F426A461460CBAB00131F8F /* VirtualRegister.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VirtualRegister.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F426A4A1460CD6B00131F8F /* DataFormat.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DataFormat.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F431736146BAC65007E3890 /* ListableHandler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ListableHandler.h; sourceTree = "<group>"; };
</span><ins>+ 0F4570361BE44C910062A629 /* AirEliminateDeadCode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirEliminateDeadCode.cpp; path = b3/air/AirEliminateDeadCode.cpp; sourceTree = "<group>"; };
+ 0F4570371BE44C910062A629 /* AirEliminateDeadCode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirEliminateDeadCode.h; path = b3/air/AirEliminateDeadCode.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F45703A1BE45F0A0062A629 /* AirReportUsedRegisters.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirReportUsedRegisters.cpp; path = b3/air/AirReportUsedRegisters.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F45703B1BE45F0A0062A629 /* AirReportUsedRegisters.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirReportUsedRegisters.h; path = b3/air/AirReportUsedRegisters.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F46807F14BA572700BFE272 /* JITExceptions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JITExceptions.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -4482,6 +4486,8 @@
</span><span class="cx"> 0FEC854F1BDACDC70080FF74 /* AirCCallSpecial.h */,
</span><span class="cx"> 0FEC85501BDACDC70080FF74 /* AirCode.cpp */,
</span><span class="cx"> 0FEC85511BDACDC70080FF74 /* AirCode.h */,
</span><ins>+ 0F4570361BE44C910062A629 /* AirEliminateDeadCode.cpp */,
+ 0F4570371BE44C910062A629 /* AirEliminateDeadCode.h */,
</ins><span class="cx"> 0FEC85521BDACDC70080FF74 /* AirFrequentedBlock.h */,
</span><span class="cx"> 0FEC85531BDACDC70080FF74 /* AirGenerate.cpp */,
</span><span class="cx"> 0FEC85541BDACDC70080FF74 /* AirGenerate.h */,
</span><span class="lines">@@ -7540,6 +7546,7 @@
</span><span class="cx"> A7B601821639FD2A00372BA3 /* UnlinkedCodeBlock.h in Headers */,
</span><span class="cx"> 996B73261BDA08EF00331B84 /* StringIteratorPrototype.lut.h in Headers */,
</span><span class="cx"> 14142E511B796ECE00F4BF4B /* UnlinkedFunctionExecutable.h in Headers */,
</span><ins>+ 0F4570391BE44C910062A629 /* AirEliminateDeadCode.h in Headers */,
</ins><span class="cx"> 0F2E892C16D028AD009E4FD2 /* UnusedPointer.h in Headers */,
</span><span class="cx"> 99DA00B11BD5994E00F4575C /* UpdateContents.py in Headers */,
</span><span class="cx"> 0F963B3813FC6FE90002D9B2 /* ValueProfile.h in Headers */,
</span><span class="lines">@@ -8279,6 +8286,7 @@
</span><span class="cx"> 0FD8A32517D51F5700CA2C40 /* DFGOSREntrypointCreationPhase.cpp in Sources */,
</span><span class="cx"> 0FC09791146A6F7100CF2442 /* DFGOSRExit.cpp in Sources */,
</span><span class="cx"> 0F235BEB17178E7300690C7F /* DFGOSRExitBase.cpp in Sources */,
</span><ins>+ 0F4570381BE44C910062A629 /* AirEliminateDeadCode.cpp in Sources */,
</ins><span class="cx"> 0FC09792146A6F7300CF2442 /* DFGOSRExitCompiler.cpp in Sources */,
</span><span class="cx"> 0FC09776146943B000CF2442 /* DFGOSRExitCompiler32_64.cpp in Sources */,
</span><span class="cx"> 0FC0977214693AF900CF2442 /* DFGOSRExitCompiler64.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirBasicBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -57,12 +57,14 @@
</span><span class="cx"> InstList::const_iterator begin() const { return m_insts.begin(); }
</span><span class="cx"> InstList::const_iterator end() const { return m_insts.end(); }
</span><span class="cx">
</span><del>- const Inst& at(size_t index) const { return m_insts[index]; }
- Inst& at(size_t index) { return m_insts[index]; }
</del><ins>+ const Inst& at(unsigned index) const { return m_insts[index]; }
+ Inst& at(unsigned index) { return m_insts[index]; }
</ins><span class="cx">
</span><span class="cx"> const Inst& last() const { return m_insts.last(); }
</span><span class="cx"> Inst& last() { return m_insts.last(); }
</span><span class="cx">
</span><ins>+ void resize(unsigned size) { m_insts.resize(size); }
+
</ins><span class="cx"> template<typename Inst>
</span><span class="cx"> void appendInst(Inst&& inst)
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirEliminateDeadCodecpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.cpp (0 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.cpp 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -0,0 +1,157 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "AirEliminateDeadCode.h"
+
+#if ENABLE(B3_JIT)
+
+#include "AirCode.h"
+#include "AirInstInlines.h"
+#include "AirPhaseScope.h"
+#include "B3IndexSet.h"
+
+namespace JSC { namespace B3 { namespace Air {
+
+bool eliminateDeadCode(Code& code)
+{
+ PhaseScope phaseScope(code, "eliminateDeadCode");
+
+ HashSet<Tmp> liveTmps;
+ IndexSet<StackSlot> liveStackSlots;
+ bool changed;
+
+ auto isArgLive = [&] (const Arg& arg) -> bool {
+ switch (arg.kind()) {
+ case Arg::Tmp:
+ if (arg.isReg())
+ return true;
+ return liveTmps.contains(arg.tmp());
+ case Arg::Stack:
+ if (arg.stackSlot()->isLocked())
+ return true;
+ return liveStackSlots.contains(arg.stackSlot());
+ default:
+ return true;
+ }
+ };
+
+ auto addLiveArg = [&] (const Arg& arg) -> bool {
+ switch (arg.kind()) {
+ case Arg::Tmp:
+ if (arg.isReg())
+ return false;
+ return liveTmps.add(arg.tmp()).isNewEntry;
+ case Arg::Stack:
+ if (arg.stackSlot()->isLocked())
+ return false;
+ return liveStackSlots.add(arg.stackSlot());
+ default:
+ return false;
+ }
+ };
+
+ auto isInstLive = [&] (Inst& inst) -> bool {
+ if (inst.hasNonArgEffects())
+ return true;
+
+ // This instruction should be presumed dead, if its Args are all dead.
+ bool storesToLive = false;
+ inst.forEachArg(
+ [&] (Arg& arg, Arg::Role role, Arg::Type) {
+ if (!Arg::isDef(role))
+ return;
+ storesToLive |= isArgLive(arg);
+ });
+ return storesToLive;
+ };
+
+ auto handleInst = [&] (Inst& inst) {
+ if (!isInstLive(inst))
+ return;
+
+ // We get here if the Inst is live. For simplicity we say that a live instruction forces
+ // liveness upon everything it mentions.
+ for (Arg& arg : inst.args) {
+ changed |= addLiveArg(arg);
+ arg.forEachTmpFast(
+ [&] (Tmp& tmp) {
+ changed |= addLiveArg(tmp);
+ });
+ }
+ };
+
+ auto runForward = [&] () -> bool {
+ changed = false;
+ for (BasicBlock* block : code) {
+ for (Inst& inst : *block)
+ handleInst(inst);
+ }
+ return changed;
+ };
+
+ auto runBackward = [&] () -> bool {
+ changed = false;
+ for (unsigned blockIndex = code.size(); blockIndex--;) {
+ BasicBlock* block = code[blockIndex];
+ for (unsigned instIndex = block->size(); instIndex--;)
+ handleInst(block->at(instIndex));
+ }
+ return changed;
+ };
+
+ for (;;) {
+ // Propagating backward is most likely to be profitable.
+ if (!runBackward())
+ break;
+ if (!runBackward())
+ break;
+
+ // Occasionally propagating forward greatly reduces the likelihood of pathologies.
+ if (!runForward())
+ break;
+ }
+
+ changed = false;
+ for (BasicBlock* block : code) {
+ unsigned sourceIndex = 0;
+ unsigned targetIndex = 0;
+ while (sourceIndex < block->size()) {
+ Inst inst = WTF::move(block->at(sourceIndex++));
+ if (isInstLive(inst))
+ block->at(targetIndex++) = WTF::move(inst);
+ else
+ changed = true;
+ }
+ block->resize(targetIndex);
+ }
+
+ return changed;
+}
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirEliminateDeadCodeh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.h (0 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirEliminateDeadCode.h 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -0,0 +1,47 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef AirEliminateDeadCode_h
+#define AirEliminateDeadCode_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// This eliminates instructions that have no observable effect. These are instructions whose only
+// effect would be storing to some Arg, except that we proved that the location specified by the Arg
+// is never loaded from. The only Args for which we can do such analysis are non-Reg Tmps and
+// anonymous StackSlots.
+
+bool eliminateDeadCode(Code&);
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
+#endif // AirEliminateDeadCode_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirGeneratecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "AirAllocateStack.h"
</span><span class="cx"> #include "AirCode.h"
</span><ins>+#include "AirEliminateDeadCode.h"
</ins><span class="cx"> #include "AirGenerationContext.h"
</span><span class="cx"> #include "AirHandleCalleeSaves.h"
</span><span class="cx"> #include "AirReportUsedRegisters.h"
</span><span class="lines">@@ -58,6 +59,8 @@
</span><span class="cx"> // This is where we run our optimizations and transformations.
</span><span class="cx"> // FIXME: Add Air optimizations.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=150456
</span><ins>+
+ eliminateDeadCode(code);
</ins><span class="cx">
</span><span class="cx"> // This is where we would have a real register allocator. Then, we could use spillEverything()
</span><span class="cx"> // in place of the register allocator only for testing.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirInsth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirInst.h (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirInst.h 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/b3/air/AirInst.h 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -141,6 +141,14 @@
</span><span class="cx"> // This function is auto-generated by opcode_generator.rb.
</span><span class="cx"> bool admitsStack(unsigned argIndex);
</span><span class="cx">
</span><ins>+ // Returns true if this instruction can have any effects other than control flow or arguments.
+ bool hasNonArgNonControlEffects();
+
+ // Returns true if this instruction can have any effects other than what is implied by arguments.
+ // For example, "Move $42, (%rax)" will return false because the effect of storing to (%rax) is
+ // implied by the second argument.
+ bool hasNonArgEffects();
+
</ins><span class="cx"> // Generate some code for this instruction. This is, like, literally our backend. If this is the
</span><span class="cx"> // terminal, it returns the jump that needs to be linked for the "then" case, with the "else"
</span><span class="cx"> // case being fall-through. This function is auto-generated by opcode_generator.rb.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirOpcodeopcodes"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -131,6 +131,8 @@
</span><span class="cx"> Index, Tmp as load32
</span><span class="cx"> Tmp, Addr as store32
</span><span class="cx"> Tmp, Index as store32
</span><ins>+ Imm, Addr as store32
+ Imm, Index as store32
</ins><span class="cx">
</span><span class="cx"> MoveDouble U:F, D:F
</span><span class="cx"> Tmp, Tmp
</span><span class="lines">@@ -186,7 +188,7 @@
</span><span class="cx">
</span><span class="cx"> Ret /terminal
</span><span class="cx">
</span><del>-Breakpoint /terminal
</del><ins>+Breakpoint /effects
</ins><span class="cx">
</span><span class="cx"> # Air allows for exotic behavior. A Patch's behavior is determined entirely by the Special operand,
</span><span class="cx"> # which must be the first operand.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirSpecialcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirSpecial.cpp (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirSpecial.cpp 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/b3/air/AirSpecial.cpp 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -50,6 +50,11 @@
</span><span class="cx"> return out.toCString();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+bool Special::hasNonArgNonControlEffects()
+{
+ return true;
+}
+
</ins><span class="cx"> void Special::dump(PrintStream& out) const
</span><span class="cx"> {
</span><span class="cx"> out.print(dumpPrefix);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirSpecialh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirSpecial.h (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirSpecial.h 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/b3/air/AirSpecial.h 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -82,6 +82,9 @@
</span><span class="cx">
</span><span class="cx"> virtual const RegisterSet& extraClobberedRegs(Inst&) = 0;
</span><span class="cx">
</span><ins>+ // By default, this returns true.
+ virtual bool hasNonArgNonControlEffects();
+
</ins><span class="cx"> void dump(PrintStream&) const;
</span><span class="cx"> void deepDump(PrintStream&) const;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airopcode_generatorrb"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/opcode_generator.rb (191845 => 191846)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/opcode_generator.rb 2015-10-31 23:01:30 UTC (rev 191845)
+++ trunk/Source/JavaScriptCore/b3/air/opcode_generator.rb 2015-10-31 23:12:53 UTC (rev 191846)
</span><span class="lines">@@ -27,12 +27,12 @@
</span><span class="cx">
</span><span class="cx"> class Opcode
</span><span class="cx"> attr_reader :name, :special, :overloads
</span><del>- attr_accessor :kind
</del><ins>+ attr_reader :attributes
</ins><span class="cx">
</span><span class="cx"> def initialize(name, special)
</span><span class="cx"> @name = name
</span><span class="cx"> @special = special
</span><del>- @kind = :inst
</del><ins>+ @attributes = {}
</ins><span class="cx"> unless special
</span><span class="cx"> @overloads = []
</span><span class="cx"> end
</span><span class="lines">@@ -291,13 +291,15 @@
</span><span class="cx"> }
</span><span class="cx"> end
</span><span class="cx">
</span><del>- if token == "/"
</del><ins>+ while token == "/"
</ins><span class="cx"> consume("/")
</span><span class="cx"> case token.string
</span><span class="cx"> when "branch"
</span><del>- opcode.kind = :branch
</del><ins>+ opcode.attributes[:branch] = true
</ins><span class="cx"> when "terminal"
</span><del>- opcode.kind = :terminal
</del><ins>+ opcode.attributes[:terminal] = true
+ when "effects"
+ opcode.attributes[:effects] = true
</ins><span class="cx"> else
</span><span class="cx"> parseError("Bad / directive")
</span><span class="cx"> end
</span><span class="lines">@@ -580,7 +582,7 @@
</span><span class="cx"> outp.puts "switch (opcode) {"
</span><span class="cx"> $opcodes.values.each {
</span><span class="cx"> | opcode |
</span><del>- if opcode.kind == :terminal or opcode.kind == :branch
</del><ins>+ if opcode.attributes[:terminal] or opcode.attributes[:branch]
</ins><span class="cx"> outp.puts "case #{opcode.name}:"
</span><span class="cx"> end
</span><span class="cx"> }
</span><span class="lines">@@ -786,6 +788,50 @@
</span><span class="cx"> outp.puts "return false;"
</span><span class="cx"> outp.puts "}"
</span><span class="cx">
</span><ins>+ outp.puts "bool Inst::hasNonArgNonControlEffects()"
+ outp.puts "{"
+ outp.puts "switch (opcode) {"
+ $opcodes.values.each {
+ | opcode |
+ if opcode.attributes[:effects]
+ outp.puts "case #{opcode.name}:"
+ end
+ }
+ outp.puts "return true;"
+ $opcodes.values.each {
+ | opcode |
+ if opcode.special
+ outp.puts "case #{opcode.name}:"
+ end
+ }
+ outp.puts "return args[0].special()->hasNonArgNonControlEffects();"
+ outp.puts "default:"
+ outp.puts "return false;"
+ outp.puts "}"
+ outp.puts "}"
+
+ outp.puts "bool Inst::hasNonArgEffects()"
+ outp.puts "{"
+ outp.puts "switch (opcode) {"
+ $opcodes.values.each {
+ | opcode |
+ if opcode.attributes[:branch] or opcode.attributes[:terminal] or opcode.attributes[:effects]
+ outp.puts "case #{opcode.name}:"
+ end
+ }
+ outp.puts "return true;"
+ $opcodes.values.each {
+ | opcode |
+ if opcode.special
+ outp.puts "case #{opcode.name}:"
+ end
+ }
+ outp.puts "return args[0].special()->hasNonArgNonControlEffects();"
+ outp.puts "default:"
+ outp.puts "return false;"
+ outp.puts "}"
+ outp.puts "}"
+
</ins><span class="cx"> outp.puts "CCallHelpers::Jump Inst::generate(CCallHelpers& jit, GenerationContext& context)"
</span><span class="cx"> outp.puts "{"
</span><span class="cx"> outp.puts "UNUSED_PARAM(jit);"
</span><span class="lines">@@ -801,7 +847,7 @@
</span><span class="cx"> else
</span><span class="cx"> methodName = opcode.masmName
</span><span class="cx"> end
</span><del>- if opcode.kind == :branch
</del><ins>+ if opcode.attributes[:branch]
</ins><span class="cx"> outp.print "result = "
</span><span class="cx"> end
</span><span class="cx"> outp.print "jit.#{methodName}("
</span></span></pre>
</div>
</div>
</body>
</html>