608032 - Does closure escape analysis really require an exponential algorithm?

Status: RESOLVED INVALID

(Core :: JavaScript Engine, enhancement)

Description

[Jim Blandy :jimb]

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

[Jim Blandy :jimb]

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

[Brendan Eich [:brendan]]

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

Comment 3

[Jim Blandy :jimb]

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

[Dave Herman [:dherman]]

> 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

Comment 5

[Jim Blandy :jimb]

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

[Luke Wagner [:luke]]

Deleted.