Allocating call stack frame entries at different memory levels to functions in a program

• US 7,512,738 B2
• Filed: 09/30/2004
• Issued: 03/31/2009
• Est. Priority Date: 09/30/2004
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Balakrishnan, Vinod K., Lian, Ruiqi, Zhang, Junchao, Ju, Dz-ching
• Primary Examiner(s): Ellis; Kevin
• Assistant Examiner(s): Farrokh; Hashem
• Application Number:
  US10/956,186
• Publication Number:
  US 20060070046A1
• Time in Patent Office: 1,643 Days
• Field of Search: 711/132
• US Class Current: 711/132
• CPC Class Codes: G06F 9/4486 Formation of subprogram jump address

Abstract

Provided are a method, system, and program for allocating call stack frame entries at different memory levels to functions in a program. Functions in a program accessing state information stored in call stack frame entries are processed. Call stack frame entries are allocated to the state information for each function, wherein the call stack frame entries span multiple memory levels, and wherein one function is capable of being allocated stack entries in multiple memory levels.

Claims

1. A method, comprising:

traversing a call graph to process functions in a program in the call graph accessing state information stored in call stack frame entries;

allocating at least one call stack frame entry to the state information for each function, wherein the call stack frame entries span multiple memory levels, and wherein one function is capable of being allocated stack entries in multiple memory levels; and

updating a node for each function in the call graph to indicate one memory level and an offset into the indicated memory level indicating a location of the call stack frame entries allocated to the function.

2. The method of claim 1, wherein the call stack frame entries allocated to the state information for each function comprise a frame of contiguous call stack frame entries.

3. The method of claim 1, wherein the offset comprises an active stack size indicating a last call stack frame entry in the memory level allocated to one function in the indicated memory level.

4. The method of claim 1, further comprising:

determining one of multiple predecessor functions to the function in the call graph whose state information occupies a greatest number of call stack frame entries, wherein the call stack frame entries allocated to the processed function follow the call stack frame entries allocated to the determined predecessor function.

5. The method of claim 1, wherein updating the node for one function allocated call stack frame entries spanning multiple memory levels comprises:

updating the node for the function in the call graph to indicate each memory level and the offset into each memory level of the location of the call stack frame entries allocated to the function.

6. The method of claim 1, wherein allocating the call stack frame entries comprises:

allocating as many available call stack frame entries in one faster access memory level before allocating call stack frame entries in at least one slower access memory level.

7. The method of claim 1, further comprising:

generating code for one function in response to allocating call stack frame entries to the function; and

including in the generated code the location of the at least one call stack frame entry allocated to the state information to resolve external references of the state information.

8. The method of claim 1,

wherein processing the functions comprises:

estimating a call frequency for each function;

ordering the functions according to their call frequencies, wherein the functions are processed from a highest call frequency to a lowest;

wherein allocating the call stack frame entries for one function processed according to the ordering comprises;

determining all predecessor functions in the call graph of the processed function; and

reserving call stack frame entries to each predecessor function not previously allocated call stack frame entries.

9. The method of claim 8, wherein reserving call stack frame entries to each predecessor function comprises reserving a fixed number of call stack frame entries in a faster access memory level to the predecessor functions, and further comprising:

allocating the reserved fixed number of call stack entries in the faster access memory and a remainder of the call stack frame entries in a slower access memory level for the predecessor functions when allocating call stack entries to the predecessor functions according to the ordering.

10. The method of claim 1, wherein the state information is a member of a set of state information comprising:

local variables, register spills, caller/callee saved registers, spilled arguments, and return objects and values.

11. A method, comprising:

processing functions in a program accessing state information stored in call stack frame entries, wherein the functions are executed by multiple packet engines in a network processor; and

allocating call stack frame entries to the state information for each function, wherein the call stack frame entries span multiple memory levels, wherein one function is capable of being allocated stack entries in multiple memory levels, and wherein the memory levels comprise at least one local memory specific to one packet engine and at least one attached memory device shared by the packet engines.

12. A system for translating code capable of accessing multiple memory levels, comprising:

a processor;

a computer readable storage medium including a compiler program executed by the processor to perform;

traverse a call graph to process functions in a program in the call graph accessing state information stored in call stack frame entries in the memory levels;

allocate at least one call stack frame entry to the state information for each function, wherein the call stack frame entries span the multiple memory levels, and wherein one function is capable of being allocated stack entries in multiple memory levels; and

update a node for each function in the call graph to indicate one memory level and an offset into the indicated memory level indicating a location of the call stack frame entries allocated to the function.

13. The system of claim 12, wherein the call stack frame entries allocated to the state information for each function comprise a frame of contiguous call stack frame entries.

14. The system of claim 12, wherein the offset comprises an active stack size indicating a last call stack frame entry in the memory level allocated to one function in the indicated memory level.

15. The system of claim 12, wherein the compiler program is further executed to:

determine one of multiple predecessor functions to the function in the call graph whose state information occupies a greatest number of call stack frame entries, wherein the call stack frame entries allocated to the processed function follow the call stack frame entries allocated to the determined predecessor function.

16. The system of claim 12, wherein updating the node for one function allocated call stack frame entries spanning multiple memory levels comprises:

updating the node for the function in the call graph to indicate each memory level and the offset into each memory level of the location of the call stack frame entries allocated to the function.

17. The system of claim 12, wherein allocating the call stack frame entries comprises:

allocating as many available call stack frame entries in one faster access memory level before allocating call stack frame entries in at least one slower access memory level.

18. The system of claim 12, wherein the compiler program is further executed to:

generate code for one function in response to allocating call stack frame entries to the function; and

include in the generated code the location of the at least one call stack frame entry allocated to the state information to resolve external references of the state information.

19. The system of claim 12,

wherein processing the functions comprises:

estimating a call frequency for each function;

ordering the functions according to their call frequencies, wherein the functions are processed from a highest call frequency to a lowest;

wherein allocating the call stack frame entries for one function processed according to the ordering comprises;

determining all predecessor functions in the call graph of the processed function; and

reserving call stack frame entries to each predecessor function not previously allocated call stack frame entries.

20. The system of claim 19, wherein reserving call stack frame entries to each predecessor function comprises reserving a fixed number of call stack frame entries in a faster access memory level to the predecessor functions, and further comprising:

allocating the reserved fixed number of call stack entries in the faster access memory and a remainder of the call stack frame entries in a slower access memory level for the predecessor functions when allocating call stack entries to the predecessor functions according to the ordering.

21. The system of claim 12, wherein the state information is a member of a set of state information comprising:

local variables, register spills, caller/callee saved registers, spilled arguments, and return objects and values.

22. A system for translating code capable of accessing multiple memory levels, comprising:

a processor;

a computer readable storage medium including a compiler program executed by the processor to perform;

process functions in a program accessing state information stored in call stack frame entries in the memory levels, wherein the functions are executed by multiple packet engines in a network processor;

allocate call stack frame entries to the state information for each function, wherein the call stack frame entries span the multiple memory levels, wherein one function is capable of being allocated stack entries in multiple memory levels, and wherein the memory levels comprise at least one local memory specific to one packet engine and at least one attached memory device shared by the packet engines.

23. An article of manufacture comprising a computer readable storage medium having a compiler executed by a processor to generate code capable of accessing a plurality of memory levels, wherein the compiler executed to perform operations comprising:

traversing a call graph to process functions in a program in the call graph accessing state information stored in call stack frame entries;

allocating at least one call stack frame entry to the state information for each function, wherein the call stack frame entries span multiple memory levels, and wherein one function is capable of being allocated stack entries in multiple memory levels; and

updating a node for each function in the call graph to indicate one memory level and an offset into the indicated memory level indicating a location of the call stack frame entries allocated to the function.

24. The article of manufacture of claim 23, wherein the call stack frame entries allocated to the state information for each function comprise a frame of contiguous call stack frame entries.

25. The article of manufacture of claim 23, wherein the offset comprises an active stack size indicating a last call stack frame entry in the memory level allocated to one function in the indicated memory level.

26. The article of manufacture of claim 23, wherein the operations further comprise:

determining one of multiple predecessor functions to the function in the call graph whose state information occupies a greatest number of call stack frame entries, wherein the call stack frame entries allocated to the processed function follow the call stack frame entries allocated to the determined predecessor function.

27. The article of manufacture of claim 23, wherein updating the node for one function allocated call stack frame entries spanning multiple memory levels comprises:

updating the node for the function in the call graph to indicate each memory level and the offset into each memory level of the location of the call stack frame entries allocated to the function.

28. The article of manufacture of claim 23, wherein allocating the call stack frame entries comprises:

allocating as many available call stack frame entries in one faster access memory level before allocating call stack frame entries in at least one slower access memory level.

29. The article of manufacture of claim 23, wherein the operations further comprise:

generating code for one function in response to allocating call stack frame entries to the function; and

including in the generated code the location of the at least one call stack frame entry allocated to the state information to resolve external references of the state information.

30. The article of manufacture of claim 23,

wherein processing the functions comprises:

estimating a call frequency for each function;

ordering the functions according to their call frequencies, wherein the functions are processed from a highest call frequency to a lowest;

wherein allocating the call stack frame entries for one function processed according to the ordering comprises;

determining all predecessor function in the call graph of the processed function; and

reserving call stack frame entries to each predecessor function not previously allocated call stack frame entries.

31. The article of manufacture of claim 30, wherein reserving call stack frame entries to each predecessor function comprises reserving a fixed number of call stack frame entries in a faster access memory level to the predecessor functions, and further comprising:

allocating the reserved fixed number of call stack entries in the faster access memory and a remainder of the call stack frame entries in a slower access memory level for the predecessor functions when allocating call stack entries to the predecessor functions according to the ordering.

32. The article of manufacture of claim 23, wherein the state information is a member of a set of state information comprising:

local variables, register spills, caller/callee saved registers, spilled arguments, and return objects and values.

33. An article of manufacture comprising a computer readable storage medium for generating code capable of accessing a plurality of memory levels, wherein the article of manufacture is enabled to perform operations comprising:

processing functions in a program accessing state information stored in call stack frame entries, wherein the functions are executed by multiple packet engines in a network processor; and

allocating call stack frame entries to the state information for each function, wherein the call stack frame entries span multiple memory levels, wherein one function is capable of being allocated stack entries in multiple memory levels, and wherein the memory levels comprise at least one local memory specific to one packet engine and at least one attached memory device shared by the packet engines.