Skip to content

Commit c3b478c

Browse files
kmiller68kmiller68
committed
Array allocation sinking should split allocations into two, an Array allocation and a Butterfly allocation
rdar://159207754 https://bugs.webkit.org/show_bug.cgi?id=298606 Reviewed by Yusuke Suzuki. This patch minorly rearchitects how we do Array allocation sinking in DFG. Previously we tried to model Arrays in ObjectAllocationSinking as two allocations one where the actual Array was allocated and a "Butterfly" at each `GetButterfly`. This meant that there was now a reverse data dependency between the GetButterfly and the Array allocation Nodes. This was a little unintuitive but also meant that any control flow that would merge two `GetButterfly`s would escape the Array. This PR simplifies things by more directly representing the heap in ObjectAllocationSinking. There are now two nodes that get sunk when sinking an Array: NewButterflyWithSize and NewArrayWithButterfly. All the indexed properties and the Butterfly's location are stored on the NewArrayWithButterfly's Allocation. The NewButterflyWithSize only contains the Array's length. If we ever wanted to extend Array allocation sinking to support out of bounds stores we'd have to teach `handleNode` how to deal with writes to multiple allocations. Originally I had all the indexed properties and the length are stored on the LocalHeap of NewButterflyWithSize and NewArrayWithButterfly's LocalHeap only contains the butterfly. But I realized that we crash while trying to materialize a phantom array that contains itself or another newly materialized object that's in a cycle. This is because we have to materialize the pointer as a PutByVal. We can't emit this PutByVal without the Array since we need to write barrier after the store. Overall, this change is perf neutral or maybe a slight progression on JetStream 3. Canonical link: https://commits.webkit.org/300129@main
1 parent 1d2530a commit c3b478c

41 files changed

Lines changed: 1303 additions & 471 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎JSTests/stress/array-allocation-elimination-closure-capture.js‎

Lines changed: 207 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,207 @@
1+
function assert(condition, message) {
2+
if (!condition)
3+
throw new Error(message || "Assertion failed");
4+
}
5+
6+
// Test array allocation with closure capture scenarios
7+
8+
// Function that creates a closure value
9+
function createClosureValue(multiplier) {
10+
return function(x) {
11+
return x * multiplier;
12+
};
13+
}
14+
15+
// Function that allocates an array with fixed size
16+
function allocateArrayForClosure(baseValue) {
17+
const arr = new Array(5);
18+
for (let i = 0; i < 5; i++) {
19+
arr[i] = baseValue + i;
20+
}
21+
return arr;
22+
}
23+
24+
// Function that uses array and captures closure
25+
function processWithClosure(closureFn, arr) {
26+
let result = 0;
27+
for (let i = 0; i < arr.length; i++) {
28+
result += closureFn(arr[i]);
29+
}
30+
return result;
31+
}
32+
33+
// Complex scenario: array allocation, closure capture, and usage all in different functions
34+
function complexClosureTest(multiplier, baseValue) {
35+
const closureFn = createClosureValue(multiplier);
36+
const arr = allocateArrayForClosure(baseValue);
37+
return processWithClosure(closureFn, arr);
38+
}
39+
40+
// Scenario where closure modifies array behavior
41+
function closureModifiesArray(capturedValue) {
42+
return function(baseValue) {
43+
const arr = new Array(4);
44+
for (let i = 0; i < 4; i++) {
45+
arr[i] = (baseValue + i) + capturedValue;
46+
}
47+
48+
// Array usage within the closure
49+
let sum = 0;
50+
for (let i = 0; i < arr.length; i++) {
51+
sum += arr[i] * 2;
52+
}
53+
return sum;
54+
};
55+
}
56+
57+
// Nested closure with array
58+
function nestedClosureWithArray(outerValue) {
59+
return function(middleValue) {
60+
return function(baseValue) {
61+
const arr = new Array(3);
62+
for (let i = 0; i < 3; i++) {
63+
arr[i] = baseValue + i + outerValue + middleValue;
64+
}
65+
66+
// Process array using captured values
67+
let product = 1;
68+
for (let i = 0; i < arr.length; i++) {
69+
product *= (arr[i] % 10) || 1; // avoid zero
70+
}
71+
return product;
72+
};
73+
};
74+
}
75+
76+
let escapedArray = null;
77+
// Array that sometimes escapes through closure
78+
function conditionalEscapeViaClosure(shouldEscape) {
79+
80+
return function(baseValue) {
81+
const arr = new Array(4);
82+
for (let i = 0; i < 4; i++) {
83+
arr[i] = baseValue + i * 2;
84+
}
85+
86+
if (shouldEscape) {
87+
escapedArray = arr;
88+
return arr.length;
89+
} else {
90+
// Use array locally
91+
let sum = 0;
92+
for (let i = 0; i < arr.length; i++) {
93+
sum += arr[i];
94+
}
95+
return sum;
96+
}
97+
};
98+
}
99+
100+
// Closure that captures array from outer scope
101+
function captureArrayInClosure(baseValue) {
102+
const arr = new Array(6);
103+
for (let i = 0; i < 6; i++) {
104+
arr[i] = baseValue + i;
105+
}
106+
107+
// Return closure that uses the captured array
108+
return function(multiplier) {
109+
let result = 0;
110+
for (let i = 0; i < arr.length; i++) {
111+
result += arr[i] * multiplier;
112+
}
113+
return result;
114+
};
115+
}
116+
117+
// Multiple arrays with closure interactions
118+
function multiArrayClosure(factor1, factor2) {
119+
return function(baseValue) {
120+
const arr1 = new Array(3);
121+
const arr2 = new Array(3);
122+
123+
for (let i = 0; i < 3; i++) {
124+
arr1[i] = (baseValue + i) * factor1;
125+
arr2[i] = (baseValue + i) * factor2;
126+
}
127+
128+
// Combine arrays using closure variables
129+
let combined = 0;
130+
for (let i = 0; i < 3; i++) {
131+
combined += arr1[i] + arr2[i];
132+
}
133+
return combined;
134+
};
135+
}
136+
137+
noInline(complexClosureTest);
138+
noInline(closureModifiesArray);
139+
noInline(nestedClosureWithArray);
140+
noInline(conditionalEscapeViaClosure);
141+
noInline(captureArrayInClosure);
142+
noInline(multiArrayClosure);
143+
144+
// Run tests
145+
for (let i = 0; i < testLoopCount; i++) {
146+
const baseValue = i % 8;
147+
const multiplier = 1 + (i % 3); // multipliers 1-3
148+
149+
// Test complex closure scenario (array size 5)
150+
let result1 = complexClosureTest(multiplier, baseValue);
151+
let expected1 = 0;
152+
for (let j = 0; j < 5; j++) {
153+
expected1 += (baseValue + j) * multiplier;
154+
}
155+
assert(result1 === expected1, `complexClosureTest(${multiplier}, ${baseValue}) failed: got ${result1}, expected ${expected1}`);
156+
157+
// Test closure that modifies array behavior (array size 4)
158+
const closureFn = closureModifiesArray(i % 5);
159+
let result2 = closureFn(baseValue);
160+
let expected2 = 0;
161+
for (let j = 0; j < 4; j++) {
162+
expected2 += (baseValue + j + (i % 5)) * 2;
163+
}
164+
assert(result2 === expected2, `closureModifiesArray test failed: got ${result2}, expected ${expected2}`);
165+
166+
// Test nested closure (array size 3)
167+
const nestedFn = nestedClosureWithArray(i % 3)(i % 4);
168+
let result3 = nestedFn(baseValue);
169+
let expected3 = 1;
170+
for (let j = 0; j < 3; j++) {
171+
let val = (baseValue + j + (i % 3) + (i % 4)) % 10;
172+
if (val !== 0) expected3 *= val;
173+
}
174+
assert(result3 === expected3, `nestedClosureWithArray test failed: got ${result3}, expected ${expected3}`);
175+
176+
// Test conditional escape via closure - non-escaping case (array size 4)
177+
const condEscapeFn = conditionalEscapeViaClosure(false);
178+
let result4 = condEscapeFn(baseValue);
179+
let expected4 = 0;
180+
for (let j = 0; j < 4; j++) {
181+
expected4 += baseValue + j * 2;
182+
}
183+
assert(result4 === expected4, `conditionalEscapeViaClosure(false) test failed: got ${result4}, expected ${expected4}`);
184+
185+
// Test conditional escape via closure - escaping case (array size 4)
186+
const condEscapeFn2 = conditionalEscapeViaClosure(true);
187+
let result5 = condEscapeFn2(baseValue);
188+
assert(result5 === 4, `conditionalEscapeViaClosure(true) test failed: got ${result5}, expected 4`);
189+
190+
// Test capture array in closure (array size 6)
191+
const capturedFn = captureArrayInClosure(baseValue);
192+
let result6 = capturedFn(multiplier);
193+
let expected6 = 0;
194+
for (let j = 0; j < 6; j++) {
195+
expected6 += (baseValue + j) * multiplier;
196+
}
197+
assert(result6 === expected6, `captureArrayInClosure test failed: got ${result6}, expected ${expected6}`);
198+
199+
// Test multiple arrays with closure (arrays size 3 each)
200+
const multiArrayFn = multiArrayClosure(2, 3);
201+
let result7 = multiArrayFn(baseValue);
202+
let expected7 = 0;
203+
for (let j = 0; j < 3; j++) {
204+
expected7 += (baseValue + j) * 2 + (baseValue + j) * 3; // factor1 + factor2
205+
}
206+
assert(result7 === expected7, `multiArrayClosure test failed: got ${result7}, expected ${expected7}`);
207+
}

‎JSTests/stress/array-allocation-elimination-conditional-usage.js‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
function assert(condition, message) {
2+
if (!condition)
3+
throw new Error(message || "Assertion failed");
4+
}
5+
6+
// Test conditional array usage - some branches use array, others don't
7+
function testConditionalArrayUsage(useArray, writeValue) {
8+
const arr = new Array(5);
9+
10+
if (useArray) {
11+
// Branch that uses the array
12+
arr[0] = writeValue;
13+
arr[2] = writeValue + 10;
14+
arr[4] = writeValue + 20;
15+
16+
let sum = 0;
17+
for (let i = 0; i < 5; i++) {
18+
if (arr[i] !== undefined) {
19+
sum += arr[i];
20+
}
21+
}
22+
return sum;
23+
} else {
24+
// Branch that doesn't use the array at all
25+
return writeValue * 3 + 30; // Same result as the sum above when writeValue = 0
26+
}
27+
}
28+
29+
// Test with nested conditionals
30+
function testNestedConditionalArray(outer, inner, value) {
31+
const arr = new Array(3);
32+
33+
if (outer) {
34+
arr[0] = value;
35+
36+
if (inner) {
37+
arr[1] = value * 2;
38+
arr[2] = value * 3;
39+
return arr[0] + arr[1] + arr[2]; // value * 6
40+
} else {
41+
// Only use first element
42+
return arr[0]; // value
43+
}
44+
} else {
45+
// Don't use array at all
46+
return inner ? value * 6 : value;
47+
}
48+
}
49+
50+
// Test with early return that skips array usage
51+
function testEarlyReturnArray(shouldReturn, value) {
52+
const arr = new Array(4);
53+
54+
if (shouldReturn) {
55+
return value * 42;
56+
}
57+
58+
// This array usage should be eliminated when shouldReturn is true
59+
arr[0] = value;
60+
arr[1] = value + 1;
61+
arr[3] = value + 3;
62+
63+
return arr[0] + arr[1] + arr[3]; // value * 3 + 4
64+
}
65+
66+
noInline(testConditionalArrayUsage);
67+
noInline(testNestedConditionalArray);
68+
noInline(testEarlyReturnArray);
69+
70+
// Run tests to trigger optimization
71+
for (let i = 0; i < testLoopCount; i++) {
72+
// Test the branch that uses the array
73+
let result1 = testConditionalArrayUsage(true, i % 100);
74+
let expected1 = (i % 100) + (i % 100 + 10) + (i % 100 + 20);
75+
assert(result1 === expected1, `testConditionalArrayUsage(true, ${i % 100}) failed: got ${result1}, expected ${expected1}`);
76+
77+
// Test the branch that doesn't use the array
78+
let result2 = testConditionalArrayUsage(false, i % 100);
79+
let expected2 = (i % 100) * 3 + 30;
80+
assert(result2 === expected2, `testConditionalArrayUsage(false, ${i % 100}) failed: got ${result2}, expected ${expected2}`);
81+
82+
// Test nested conditionals
83+
let val = i % 10;
84+
85+
// outer=true, inner=true
86+
let result3 = testNestedConditionalArray(true, true, val);
87+
assert(result3 === val * 6, `testNestedConditionalArray(true, true, ${val}) failed: got ${result3}, expected ${val * 6}`);
88+
89+
// outer=true, inner=false
90+
let result4 = testNestedConditionalArray(true, false, val);
91+
assert(result4 === val, `testNestedConditionalArray(true, false, ${val}) failed: got ${result4}, expected ${val}`);
92+
93+
// outer=false, inner=true
94+
let result5 = testNestedConditionalArray(false, true, val);
95+
assert(result5 === val * 6, `testNestedConditionalArray(false, true, ${val}) failed: got ${result5}, expected ${val * 6}`);
96+
97+
// outer=false, inner=false
98+
let result6 = testNestedConditionalArray(false, false, val);
99+
assert(result6 === val, `testNestedConditionalArray(false, false, ${val}) failed: got ${result6}, expected ${val}`);
100+
101+
// Test early return
102+
let result7 = testEarlyReturnArray(true, val);
103+
assert(result7 === val * 42, `testEarlyReturnArray(true, ${val}) failed: got ${result7}, expected ${val * 42}`);
104+
105+
let result8 = testEarlyReturnArray(false, val);
106+
let expected8 = val * 3 + 4;
107+
assert(result8 === expected8, `testEarlyReturnArray(false, ${val}) failed: got ${result8}, expected ${expected8}`);
108+
}

0 commit comments

Comments
 (0)