COMPILER OPTIMIZATION OF COROUTINES

• US 20160321045A1
• Filed: 06/26/2015
• Published: 11/03/2016
• Est. Priority Date: 04/28/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Radigan, James J., Nishanov, Gor
• Granted Patent: US 10,747,511 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/4434 Reducing the memory space required by the program code
• CPC Class Codes: G06F 8/47 Retargetable compilers
• CPC Class Codes: G06F 9/4484 Executing subprograms

Abstract

As a memory usage optimization, a compiler identifies coroutines whose activation frames can be allocated on a caller'"'"'s stack instead of allocating the frame on the heap. For example, when the compiler determines that a coroutine C'"'"'s life cannot extend beyond the life of the routine R that first calls the coroutine C, the compiler generates code to allocate the activation frame for C on the stack of R, instead of generating code to allocate C'"'"'s frame from heap memory. In some cases, as another optimization, code for coroutine C is also inlined with code for the routine R that calls C. Coroutine activation frame content variations and layout variations are also described.

Claims

1. A method for implementing a resumable function, comprising:

a compiler determining at compile time whether the resumable function has a lifespan that will not extend beyond a call to the resumable function made by a caller in a computing system;

when the compiler determines that the resumable function lifespan will not extend beyond the call, the compiler generating code which upon execution will allocate an activation frame of the resumable function from a local stack memory of the caller in the computing system; and

when the compiler determines that the resumable function lifespan can extend beyond the call, the compiler generating code which upon execution will allocate the activation frame from a heap memory in the computing system.

2. The method of claim 1, further comprising the compiler generating code which upon execution places a resumption address in the activation frame, the resumption address being the address of a resumable portion of a function body of the resumable function.

3. The method of claim 1, further comprising the compiler generating code which upon execution sets a resumption index in the activation frame, the resumption index being an ordinal whose value distinguishes between a plurality of execution resumption points in a function body of the resumable function.

4. The method of claim 1, wherein the compiler determines an extent of the resumable function lifespan at least in part by using a static single assignment use-definition chain.

5. The method of claim 1, wherein the resumable function includes at least one of the following:

a yield statement, an await expression.

6. The method of claim 1, wherein the compiler also inlines code of the resumable function in the caller of the resumable function.

7. The method of claim 1, wherein the compiler also generates code which upon execution initializes a promise data structure in the activation frame.

8. The method of claim 1, wherein the compiler includes a front end and a back end, the front end performs lexical analysis and parsing for a particular programming language, the back end converts output from the front end into tuples which include machine-independent opcodes and symbolic operands, and the front end identifies the following to the back end:

(a) an initialization point of the resumable function, (b) at least one suspension point of the resumable function, (c) a resumption point for each suspension point, indicating where execution of the resumable function will resume after execution has been suspended at that suspension point.

9. The method of claim 8, wherein the compiler front end identifies resumable function initialization, suspension, and resumption points to the compiler back end using intrinsics.

10. A computer-readable storage medium configured with data and with instructions that upon execution by at least one processor in a compilation computing system will cause the at least one processor to perform a technical process for coroutine compilation, the process comprising:

determining at compile time whether a coroutine has a lifespan that will not extend beyond a call to the coroutine that will be made by a caller in a target computing system;

when the coroutine lifespan will not extend beyond the call, generating code which upon execution by a processor in the target computing system allocates an activation frame of the coroutine from a local stack memory of the caller in the target computing system;

when the coroutine lifespan can extend beyond the call, generating code which upon execution in the target computing system allocates the activation frame from a heap memory in the target computing system; and

generating code which upon execution in the target computing system places a resumption address in the activation frame, the resumption address being the address of a resumable portion of the coroutine.

11. The computer-readable storage medium of claim 10, wherein the process further comprises generating code which upon execution in the target computing system initializes a promise data structure in the activation frame.

12. The computer-readable storage medium of claim 10, wherein the process further comprises at least one of the following:

generating code which upon execution in the target computing system verifies that a resumption address value specified in the activation frame is a valid value before passing control based on that resumption address value;

generating code which upon execution in the target computing system verifies that a resumption index value specified in the activation frame is a valid value before passing control based on that resumption index value.

13. The computer-readable storage medium of claim 10, wherein the process determines an extent of the coroutine lifespan at least in part by using a static single assignment use-definition chain.

14. A computer system comprising:

a compilation processor;

a memory in operable communication with the compilation processor;

program source code residing in the memory, the program source code including a call to a coroutine by a caller;

a static single assignment use-definition chain residing in the memory and based on a definition of the coroutine in the program source code and also based on at least one use of the coroutine in the program source code;

a compiler residing in the memory and having coroutine compilation code, the coroutine compilation code interacting with the compilation processor and memory to perform, upon execution, a process which includes (a) determining with an analysis of the static single assignment use-definition chain whether the coroutine has a lifespan that will not extend beyond the call when the call is executed by a target processor, (b) when the coroutine lifespan will not extend beyond the call, the compilation processor generating code which upon execution by the target processor allocates an activation frame of the coroutine from a local stack memory of the caller, and (c) when the coroutine lifespan can extend beyond the call, the compilation processor generating code which upon execution by the target processor allocates the activation frame from a heap memory.

15. The system of claim 14, wherein the activation frame comprises a resumption index, namely, an ordinal whose value distinguishes between a plurality of execution resumption points in the coroutine.

16. The system of claim 14, wherein the activation frame comprises a promise portion which the target processor initialized in executing the code compiled from the program source code, and a platform-specific register save area initialized by a runtime.

17. The system of claim 14, further comprising at least a first coroutine piece and a second coroutine piece residing in the memory, the coroutine pieces delimited by an initial suspension point of the coroutine, the first coroutine piece including an initialization portion of the coroutine which the target processor executes up to the initial suspension point, the second coroutine piece including a resumption portion that the target processor executes after at least one suspension point of the coroutine.

18. The system of claim 14, wherein the coroutine compilation code identifies coroutine initialization, suspension, and resumption points using intrinsics in an intermediate language produced from the program source code.

19. The system of claim 14, further comprising compiled coroutine code which upon execution by one or more target processors allocates the activation frame of the coroutine from a local stack memory of the caller and executes at least a portion of the coroutine inline with the caller of the coroutine.

20. The system of claim 14, wherein the coroutine includes at least one of the following:

a yield statement, an await expression.