Closed
Bug 608032
Opened 14 years ago
Closed 12 years ago
Does closure escape analysis really require an exponential algorithm?
Categories
(Core :: JavaScript Engine, enhancement)
Core
JavaScript Engine
Tracking
()
RESOLVED
INVALID
People
(Reporter: jimb, Assigned: jimb)
Details
The comments above js/src/jsparse.cpp's FindFunArgs say that the algorithm it and markFunArgs implement is exponential in the size of the code (although well-behaved in practice). It's hard for me to believe there isn't a better algorithm for this, and I have some half-formed ideas. Filing this bug as a placeholder to get back to this post-FF4.
Assignee | ||
Comment 1•14 years ago
|
||
My thought was that identifying functions whose activation records may appear on the stack when their surrounding scope levels are not is something that can be done in an early, linear-time pass. With those "cuts" known, and information about which functions call which, we can make a single pass searching for variable references that cross cuts.
Comment 2•14 years ago
|
||
I wanted something like that too, but later discoveries can cause more work to be needed -- hence the worklist approach. Is it really exponential, though? I never analyzed it fully. /be
Assignee | ||
Comment 3•14 years ago
|
||
Also, we're really abusing the term 'funarg' in our code. The term means 'function-as-argument' --- a function passed as a value to another function, and by extension, a function returned as a value. We use it to mean "a function that refers to variables from enclosing scopes that may have been moved onto the heap". So our code may say "this function is a funarg" when the function in question is only ever called, never passed. Our "funargs" are a category created by the fact that funargs are permitted in our language, but they're not funargs. "needsClosure" or "needsStackOnly" (in the negative sense) would be better.
Comment 4•14 years ago
|
||
> Also, we're really abusing the term 'funarg' in our code.
Maybe, but the term was born into an abusive family (the Lispers). The term "upwards funarg" was used to mean "a function value returned from another function," ie not necessarily an argument at all, and was distinguished from "downwards funarg," meaning, well, "function value that is an argument."
Dave
Assignee | ||
Comment 5•14 years ago
|
||
The algorithm marks 'i' as a funarg, even though it could safely use getupvar. (Right?) function f(fa) { function g(ga) { function h(ha) { function i(ia) { return ia + ga; } return i(4) + fa; } return h(3); } return g; }
Comment 6•12 years ago
|
||
Deleted.
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → INVALID
You need to log in
before you can comment on or make changes to this bug.
Description
•