Skip to content

Commit 5009fc2

Browse files
ConstellationConstellation
committed
[JSC] DFG should branch on op_instanceof result in each arm when jtrue / jfalse follows
https://bugs.webkit.org/show_bug.cgi?id=327327 rdar://189865582 Reviewed by Keith Miller and Tadeu Zagallo. Currently, when we have a code like, function notInstance(term) { if (!(term instanceof Pair)) return term; return term.car; } `instanceof` creates a graph due to multiple complicated arms, and then all of boolean results are combined into one phi, and then we jump based on this phi result. However this form pessimizes the optimizations. #3 MatchStructure arm D@74: MatchStructure(D@63, Object=>true) D@76: SetLocal(D@74, loc5) D@77: Jump(T:#7) #4 value-not-object arm D@59: JSConstant(False) D@61: SetLocal(D@59, loc5) D@62: Jump(T:#7) #5 custom hasInstance arm D@47: InstanceOfCustom(...) D@49: SetLocal(D@47, loc5) D@50: Jump(T:#7) #7 (bc#25) preds: #5 #3 #4 D@78: GetLocal(loc5) D@79: Branch(D@78, T:#9, F:#8) #8 (bc#28) return term #9 (bc#30) CheckStructure(term, [Object]); GetByOffset(car); Return In the above graph, due to unified blocks, D@74 MatchStructure's filtering result is gone, and CheckStructure remains while we already did Structure check via MatchStructure in one of the most common case. So, we connect each jump directly when `instanceof` result is used with `jtrue` / `jfalse`, like #3 MatchStructure arm D@74: MatchStructure(D@63, Object=>true) D@76: SetLocal(D@74, loc5) D@77: Branch(D@74, T:#8, F:#7) #4 value-not-object arm D@59: JSConstant(False) D@61: SetLocal(D@59, loc5) D@62: Branch(D@59, T:#8, F:#7) #5 custom hasInstance arm D@47: InstanceOfCustom(...) D@49: SetLocal(D@47, loc5) D@50: Branch(D@47, T:#8, F:#7) #7 (bc#28) preds: #5 #3 #4 return term #8 (bc#30) preds: #5 #3 #4 CheckStructure(term, [Object]); GetByOffset(car); Return D@76: SetLocal(D@74, loc5) D@77: Jump(T:#7) D@61: SetLocal(D@59, loc5) D@62: Jump(T:#7) D@49: SetLocal(D@47, loc5) D@50: Jump(T:#7) D@79: Branch(D@78, T:#9, F:#8) Then, eventually each MatchStructure, etc. are foled into constant, and proper constant is propagated through the following blocks instead of propagating the phi. Test: JSTests/stress/instanceof-branch-fusion.js * JSTests/stress/instanceof-branch-fusion.js: Added. (shouldBe): (Pair): (Custom.Symbol.hasInstance): (Custom): (notInstance): (isInstance): (resultUsedAfterBranch): (custom): (loop): (customJtrue): (argumentDst): (longBody): (longBodyExpected): (inlinedPredicate): (inlinedCaller): (catch): * Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp: (JSC::DFG::ByteCodeParser::parseBlock): Canonical link: https://commits.webkit.org/323664@main
1 parent c468f0d commit 5009fc2

2 files changed

Lines changed: 197 additions & 15 deletions

File tree

‎JSTests/stress/instanceof-branch-fusion.js‎

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
function shouldBe(actual, expected) {
2+
if (actual !== expected)
3+
throw new Error('bad value: ' + actual + ' expected: ' + expected);
4+
}
5+
6+
function Pair(car, cdr) {
7+
this.car = car;
8+
this.cdr = cdr;
9+
}
10+
11+
class Custom {
12+
static [Symbol.hasInstance](value) { return value === 42; }
13+
}
14+
15+
function notInstance(term) {
16+
if (!(term instanceof Pair))
17+
return term;
18+
return term.car;
19+
}
20+
noInline(notInstance);
21+
22+
function isInstance(term) {
23+
if (term instanceof Pair)
24+
return term.cdr;
25+
return -1;
26+
}
27+
noInline(isInstance);
28+
29+
function resultUsedAfterBranch(term) {
30+
var result = term instanceof Pair;
31+
if (result)
32+
return [result, term.car];
33+
return [result, term];
34+
}
35+
noInline(resultUsedAfterBranch);
36+
37+
function custom(value, constructor) {
38+
if (value instanceof constructor)
39+
return "yes";
40+
return "no";
41+
}
42+
noInline(custom);
43+
44+
function loop(list) {
45+
var count = 0;
46+
while (list instanceof Pair) {
47+
count += list.car;
48+
list = list.cdr;
49+
}
50+
return count;
51+
}
52+
noInline(loop);
53+
54+
function customJtrue(value, constructor) {
55+
if (!(value instanceof constructor))
56+
return "no";
57+
return "yes";
58+
}
59+
noInline(customJtrue);
60+
61+
function argumentDst(a, b) {
62+
a = a instanceof Pair;
63+
if (a)
64+
return b;
65+
return -b;
66+
}
67+
noInline(argumentDst);
68+
69+
function longBody(term) {
70+
if (term instanceof Pair) {
71+
var x = term.car;
72+
x = (x * 3 + 1) | 0; x = (x * 5 + 2) | 0; x = (x * 7 + 3) | 0; x = (x * 11 + 4) | 0;
73+
x = (x * 3 + 5) | 0; x = (x * 5 + 6) | 0; x = (x * 7 + 7) | 0; x = (x * 11 + 8) | 0;
74+
x = (x * 3 + 9) | 0; x = (x * 5 + 10) | 0; x = (x * 7 + 11) | 0; x = (x * 11 + 12) | 0;
75+
x = (x * 3 + 13) | 0; x = (x * 5 + 14) | 0; x = (x * 7 + 15) | 0; x = (x * 11 + 16) | 0;
76+
x = (x * 3 + 17) | 0; x = (x * 5 + 18) | 0; x = (x * 7 + 19) | 0; x = (x * 11 + 20) | 0;
77+
return x;
78+
}
79+
return -1;
80+
}
81+
noInline(longBody);
82+
83+
function longBodyExpected(car) {
84+
var x = car;
85+
var muls = [3, 5, 7, 11];
86+
for (var j = 1; j <= 20; ++j)
87+
x = (x * muls[(j - 1) % 4] + j) | 0;
88+
return x;
89+
}
90+
91+
function inlinedPredicate(term) {
92+
if (!(term instanceof Pair))
93+
return 0;
94+
return term.car + term.cdr;
95+
}
96+
97+
function inlinedCaller(term) {
98+
return inlinedPredicate(term) + 1;
99+
}
100+
noInline(inlinedCaller);
101+
102+
var list = new Pair(1, new Pair(2, new Pair(3, null)));
103+
for (var i = 0; i < testLoopCount; ++i) {
104+
var pair = new Pair(i, i + 1);
105+
shouldBe(notInstance(pair), i);
106+
shouldBe(notInstance("str"), "str");
107+
shouldBe(notInstance(i), i);
108+
shouldBe(notInstance({ car: 1 }).car, 1);
109+
shouldBe(isInstance(pair), i + 1);
110+
shouldBe(isInstance(null), -1);
111+
shouldBe(isInstance({ cdr: 2 }), -1);
112+
113+
var r = resultUsedAfterBranch(pair);
114+
shouldBe(r[0], true);
115+
shouldBe(r[1], i);
116+
r = resultUsedAfterBranch(undefined);
117+
shouldBe(r[0], false);
118+
shouldBe(r[1], undefined);
119+
120+
shouldBe(custom(pair, Pair), "yes");
121+
shouldBe(custom(42, Custom), "yes");
122+
shouldBe(custom(pair, Custom), "no");
123+
shouldBe(custom(1, Pair), "no");
124+
125+
shouldBe(loop(list), 6);
126+
127+
shouldBe(customJtrue(pair, Pair), "yes");
128+
shouldBe(customJtrue(42, Custom), "yes");
129+
shouldBe(customJtrue(pair, Custom), "no");
130+
shouldBe(customJtrue(1, Pair), "no");
131+
132+
shouldBe(argumentDst(pair, i), i);
133+
shouldBe(argumentDst({ car: 1 }, i), -i);
134+
135+
shouldBe(longBody(pair), longBodyExpected(i));
136+
shouldBe(longBody({ car: 1 }), -1);
137+
138+
shouldBe(inlinedCaller(pair), 2 * i + 2);
139+
shouldBe(inlinedCaller("str"), 1);
140+
}
141+
142+
var threw = false;
143+
try {
144+
custom(1, 2);
145+
} catch (e) {
146+
threw = e instanceof TypeError;
147+
}
148+
shouldBe(threw, true);

‎Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp‎

Lines changed: 49 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@
8989
#include "ObjectConstructor.h"
9090
#include "OpcodeInlines.h"
9191
#include "PreciseJumpTargets.h"
92+
#include "PreciseJumpTargetsInlines.h"
9293
#include "PrivateFieldPutKind.h"
9394
#include "PropertyInlineCache.h"
9495
#include "PutByIdFlags.h"
@@ -8869,6 +8870,27 @@ void ByteCodeParser::parseBlock(unsigned limit)
88698870
case op_instanceof: {
88708871
auto bytecode = currentInstruction->as<OpInstanceof>();
88718872

8873+
// If a jtrue / jfalse on the result follows, each arm branches by itself instead of
8874+
// joining at a boolean Phi, so an arm whose result is or folds to a constant keeps it.
8875+
const JSInstruction* fusedBranch = nullptr;
8876+
unsigned fusedTaken = 0;
8877+
unsigned fusedNotTaken = 0;
8878+
unsigned fusedFallThrough = 0;
8879+
BytecodeIndex branchIndex = nextOpcodeIndex();
8880+
if (branchIndex.offset() < limit) {
8881+
auto next = instructions.at(branchIndex);
8882+
fusedFallThrough = branchIndex.offset() + next->size();
8883+
if (next->is<OpJtrue>() && next->as<OpJtrue>().m_condition == bytecode.m_dst) {
8884+
fusedBranch = next.ptr();
8885+
fusedTaken = branchIndex.offset() + jumpTargetForInstruction<OpJtrue>(codeBlock, next);
8886+
fusedNotTaken = fusedFallThrough;
8887+
} else if (next->is<OpJfalse>() && next->as<OpJfalse>().m_condition == bytecode.m_dst) {
8888+
fusedBranch = next.ptr();
8889+
fusedTaken = fusedFallThrough;
8890+
fusedNotTaken = branchIndex.offset() + jumpTargetForInstruction<OpJfalse>(codeBlock, next);
8891+
}
8892+
}
8893+
88728894
BytecodeIndex startIndex = m_currentIndex;
88738895
BytecodeIndex itermediateIndex = m_currentIndex;
88748896
BasicBlock* constructorIsObjectBlock = allocateUntargetableBlock();
@@ -8877,7 +8899,25 @@ void ByteCodeParser::parseBlock(unsigned limit)
88778899
BasicBlock* valueIsNotObjectBlock = allocateUntargetableBlock();
88788900
BasicBlock* isCustomBlock = allocateUntargetableBlock();
88798901
BasicBlock* isNotCustomBlock = allocateUntargetableBlock();
8880-
BasicBlock* continuation = allocateUntargetableBlock();
8902+
BasicBlock* continuation = fusedBranch ? nullptr : allocateUntargetableBlock();
8903+
8904+
auto finishArm = [&] {
8905+
m_currentIndex = nextOpcodeIndex();
8906+
m_exitOK = true;
8907+
processSetLocalQueue();
8908+
8909+
if (!fusedBranch) {
8910+
addToGraph(Jump, OpInfo(continuation));
8911+
return;
8912+
}
8913+
// The fused jump is never visited by the parse loop, so count it here.
8914+
if (m_graph.compilation()) [[unlikely]] {
8915+
addToGraph(CountExecution, OpInfo(m_graph.compilation()->executionCounterFor(
8916+
Profiler::OriginStack(*m_vm->m_perBytecodeProfiler, m_codeBlock, currentCodeOrigin()))));
8917+
}
8918+
addToGraph(Branch, OpInfo(branchData(fusedTaken, fusedNotTaken)), get(bytecode.m_dst));
8919+
m_inlineStackTop->m_unlinkedBlocks.append(m_currentBlock);
8920+
};
88818921

88828922
// 1. Get hasInstance
88838923
// 1.1 Check whether the constructor is an object.
@@ -8933,11 +8973,7 @@ void ByteCodeParser::parseBlock(unsigned limit)
89338973

89348974
set(bytecode.m_dst, addToGraph(InstanceOfCustom, get(bytecode.m_value), get(bytecode.m_constructor), get(bytecode.m_hasInstanceOrPrototype)));
89358975

8936-
m_currentIndex = nextOpcodeIndex();
8937-
m_exitOK = true;
8938-
processSetLocalQueue();
8939-
8940-
addToGraph(Jump, OpInfo(continuation));
8976+
finishArm();
89418977
}
89428978

89438979
m_currentIndex = itermediateIndex;
@@ -8961,11 +8997,7 @@ void ByteCodeParser::parseBlock(unsigned limit)
89618997

89628998
set(bytecode.m_dst, jsConstant(jsBoolean(false)));
89638999

8964-
m_currentIndex = nextOpcodeIndex();
8965-
m_exitOK = true;
8966-
processSetLocalQueue();
8967-
8968-
addToGraph(Jump, OpInfo(continuation));
9000+
finishArm();
89699001
}
89709002

89719003
m_currentIndex = itermediateIndex;
@@ -9033,11 +9065,13 @@ void ByteCodeParser::parseBlock(unsigned limit)
90339065
set(bytecode.m_dst, addToGraph(op, value, prototype));
90349066
})();
90359067

9036-
m_currentIndex = nextOpcodeIndex();
9037-
m_exitOK = true;
9038-
processSetLocalQueue();
9068+
finishArm();
9069+
}
90399070

9040-
addToGraph(Jump, OpInfo(continuation));
9071+
if (fusedBranch) {
9072+
m_currentIndex = BytecodeIndex(fusedFallThrough);
9073+
m_exitOK = false;
9074+
return;
90419075
}
90429076

90439077
m_currentIndex = startIndex;

0 commit comments

Comments
 (0)