Skip to content

Commit f014a32

Browse files
kmiller68kmiller68
committed
Array allocation sinking should split allocations into two, an Array allocation and a Butterfly allocation
https://bugs.webkit.org/show_bug.cgi?id=298606 rdar://159207754 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 length are stored on the LocalHeap of NewButterflyWithSize and NewArrayWithButterfly's LocalHeap only contains the butterfly. Right now we only handle in-bounds loads/stores to the butterfly but this model makes it substantially easier to model growing the Array's Butterfly in the future. One other interesting change in this PR is that we could handle sizes greater than MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH in the slow path. MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH is always bigger than a MarkBlock's max allocation size (by a lot) so any allocation that big will always take the slow path. This patch fixes that issue for the new nodes but we should consider addressing that for other Array allocation Nodes in a follow up. Lastly, this patch "corrects" leastUpperBoundOfIndexingTypeAndType so it no longer recommends Double storage when the value is a NaN. Preivously this would just be a perf issue but with this patch it's needed for correctness. Overall, this change is perf neutral or maybe a slight progression on JetStream 3. Canonical link: https://commits.webkit.org/299806@main
1 parent f6fab61 commit f014a32

35 files changed

Lines changed: 1083 additions & 450 deletions

‎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)