Does closure escape analysis really require an exponential algorithm?




JavaScript Engine
7 years ago
6 years ago


(Reporter: jimb, Assigned: jimb)


Firefox Tracking Flags

(Not tracked)




7 years ago
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.

Comment 1

7 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.
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.


Comment 3

7 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.
> 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."


Comment 5

7 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

6 years ago
Last Resolved: 6 years ago
Resolution: --- → INVALID
You need to log in before you can comment on or make changes to this bug.