Inter-procedural type propagation for devirtualization
AssigneeMicrosoft Technology Licensing, LLC
InventorTerry Jack Mahaffey
Life of this patent
Estimating the term…
Abstract
Intra-procedural and inter-procedural dynamic type propagation can be used to optimize code by devirtualizing virtual functions. In the intra-procedural pass each function in the program is inspected. If the dynamic type of a variable within the function is determined, the static type is replaced by the dynamic type. If the dynamic type of a variable within the function is not determinable, a placeholder type is inserted. After each function and each statement in the function and each statement outside of the function is examined, an attempt is made to resolve all of the placeholder types references created in the first pass, replacing the placeholder type with the dynamic type. This process is iterated until additional dynamic type determination ends.
Claims14
A system comprising:
- at least one processor;
- a memory connected to the at least one processor;
- wherein the at least one processor is configured to perform actions comprising:
- examining one or more functions of a plurality of functions in a program in a first intra-procedural pass through a program to determine a class type for at least one variable in the function being examined;
- inserting, in the first intra-procedural pass, a placeholder class type as a class type for a variable in the function being examined that has an unknown class type;
- and
- replacing the inserted placeholder class type in a second inter-procedural pass by propagating a discovered class type for the variable having the unknown class type from an inter-procedural type analysis, the discovered class type being a return type of a virtual function call that is discovered from the inter-procedural type analysis, the virtual function call within the function being examined.
A method comprising:
- performing, prior to runtime, by a processor of a computing device a first intra-procedural pass examining a function in program code to determine a class type for at least one variable whose dynamic type cannot be determined, the at least one variable assigned to a return value of a virtual function within the examined function;
- inserting a placeholder type for the class type of the at least one variable;
- executing a second inter-procedural pass to inspect each caller of the virtual function and each callee of the virtual function;
- and
- determining the dynamic type for the placeholder type based on the second inter-procedural pass;
- and
- replacing the placeholder type with the dynamic type, wherein the dynamic type includes a type of the return value.
A device, comprising:
- at least one processor and a memory;
- wherein the at least one processor is configured to execute instructions that perform actions to:
- perform a first intra-procedural pass during compilation of a program to examine a function in program code to determine a class type for at least one variable of the function;
- detecting an unknown dynamic class type for a first variable of the function during the first intra-procedural pass;
- inserting a placeholder class type for the unknown dynamic class type of the first variable;
- in a second inter-procedural pass during compilation of the program, determining the dynamic type for the placeholder type by inspecting inter-procedural relationships between functions in the program code;
- and
- replacing the dynamic type for the placeholder type, the dynamic type including a return type of a virtual function call, within the function being examined, that is discovered from the inter-procedural type analysis.
Dependencies are inferred from the claim text.