Method for executing a computer program with a parameterised function

Patent metadata

Field	Value
Publication number	US-10146565-B2
Application number	US-201615740192-A
Country	US
Kind code	B2
Filing date	Jun 28, 2016
Priority date	Jun 29, 2015
Publication date	Dec 4, 2018
Grant date	Dec 4, 2018

Abstract

A method for executing a program includes: storing, in a table associated with each address of a specialized code of a parameterized function, a value of each of specialized parameters for generating the specialized code, and each time the address of a specialized code must be modified, deleted from, or added to the table, a microprocessor generates and records in a memory a search routine written in machine language of the microprocessor, this search routine containing, coded as constants, each address and each specialized parameter value stored in the table, such that the search routine does not include any reading operation of the value of a specialized parameter or of the address of a specialized code outside the continuous address range in which this search routine is recorded, and the microprocessor runs this recorded search routine directly.

First claim

The invention claimed is:

1. A method for executing a computer program including at least one parameterized function capable of being executed one or more times during execution of the program, the function including at least one parameter a value of which is obtained at an instant when the function is called to be executed by a microprocessor or during execution thereof by the microprocessor, the method comprising:
a) providing a generic code for the function, in which code each parameter of the function is encoded as a variable such that the generic code does not itself contain the value of the parameter, but contains an operation of reading the value from an address specified by the generic code;
b) recording, in a memory, a plurality of specialized codes for the function that are written in machine language of the microprocessor, each specialized code performing, when it is executed by the microprocessor, the same function as the generic code but, in the case that the function includes a specialized parameter, the specialization of a given parameter of the function comprising assigning a specific value to the given parameter and then processing the given parameter no longer as a variable but as a constant, such that the specialized code does not include any operation of reading the value from an address situated outside of a continuous range of addresses where the specialized code is recorded, the recorded specialized codes differing from one another by the specific value assigned to the same specialized parameter or by the respective parameter that has been specialized;
c) for each specialized code, storing, in a table, an address where each specialized code is recorded in the memory;
d) when the program is executed, the microprocessor obtains a numerical value for each parameter of the function; and
e) the microprocessor looks up, in the table, the address of one of the specialized codes that is able to perform the parameterized function with the numerical values obtained during operation d) when it is executed by the microprocessor; and
f) if such an address exists in the table, the microprocessor performs the function by directly executing the one specialized code recorded in the memory at the address without using the generic code; and if not
g) the microprocessor performs the function using the generic code;
wherein:
operation c) further includes storing, in association with each address of the specialized codes, the specific value of each of the specialized parameters; and
operation e) includes, for an address recorded in the table:
e1) comparing the specific value of each specialized parameter, associated with the address in the table, with the numerical value, obtained during operation d), of the same parameter, and,
e2) if during operation e1), for each specialized parameter, the specific value stored in the table corresponds to the numerical value, obtained during operation d), of the parameter, then the microprocessor selects the address as an address for the specialized code that is able to perform the parameterized function with the numerical values obtained during operation d), and, if not, the microprocessor selects a following address in the table for which operations e1) and e2) have not yet been performed, and then reiterates operations e1) and e2) for the following address; and

each time the address of the specialized code has to be modified, deleted, or added to the table, the microprocessor generates and records in the memory a lookup routine written in the machine language of the microprocessor, the lookup routine, when it is executed by the microprocessor, being able to perform operations e1) and e2), the lookup routine containing, encoded as a constant, each address and each specific value of the specialized parameters stored in the table such that the lookup routine does not include any operation of reading the value of the specialized parameter or the address of the specialized code outside of the continuous range of addresses where the lookup routine is recorded;
each time operation e) is executed, the microprocessor directly executes the lookup routine that is recorded in the memory; and
executing a statistical data collection routine that increments a counter, associated with the parameter of the parameterized function and with a predetermined value of the parameter of the parameterized parameter, each time the numerical value, obtained during operation d), of the parameter of the parameterized function is equal to the predetermined value and, alternately, does not increment this counter if the value obtained during operation d) for the parameter of the parameterized function is different from the predetermined value.

2. The method as claimed in claim 1 , wherein:
generating the lookup routine includes, for each address of a specialized code contained in the table, generating a set of instructions that encodes a direct conditional branch to the address of the specialized code; and
when the conditional branch is executed by the microprocessor, only if the value of each specialized parameter associated with the address in the table is equal to the value, obtained during operation d), of the same parameter, then the microprocessor replaces the current value of an ordinal counter of the microprocessor with the address, such that the next instruction executed by the microprocessor is directly the first instruction of the specialized code.

3. The method as claimed in claim 1 , further comprising:
in response to the crossing of a pre-calculated threshold by the counter, performing h) including generating a new specialized code for the parameterized function by specializing the parameter associated with the counter with the predetermined value associated with the counter, and then storing the new specialized code in the memory and updating the table to incorporate therein the address where the new specialized code is recorded and the value of the specialized parameter.

4. The method as claimed in claim 3 , wherein the method further comprises calculating the pre-calculated threshold on the basis of a relationship Kgen/[Klib−Kdyn], wherein:
Kgen is a cost to execute h),
Kdyn is a cost to execute f),
Klib is a cost to execute g), and
the costs Kgen, Kdyn and Klib are each respective quantities of one and same physical variable or of one and same combination of physical variables that varies depending on whether the microprocessor executes f) or g).

5. The method as claimed in claim 1 , wherein, when the memory is full, each time a new specialized code has to be recorded in the memory, the microprocessor records the new specialized code in the place of the oldest specialized code contained in the memory.

6. The method as claimed in claim 2 , wherein only if none of the direct conditional branches of the lookup routine has triggered the execution of a specialized code, then the statistical data collection routine is executed.

7. The method as claimed in claim 1 , wherein:
operations a) to g) are executed alternately for a first and then a second parameterized function, respectively, the generic codes of which are different; and
operation c) further includes storing, in the table, an identifier of the generic code for the function that has been specialized, which identifier is associated with the address of the specialized code;
during operation d), the microprocessor also obtains the identifier of the generic code for the function to be executed;
during operation e1), the microprocessor compares the identifier, associated with the address of the specialized code in the table, with the identifier obtained during operation d); and
during operation e2), only if, during operation e1), the identifier associated with the address of the sp

Assignees

• Commissariat Energie Atomique
• Commissariat Energie Atomique

Inventors

• Queva Caroline
• Courousse Damien
• Lhuillier Yves

Classifications

• G06F9/45516 Primary

  Runtime code conversion or optimisation · CPC title

• G06F8/4441

  Reducing the execution time required by the program code · CPC title

• G06F9/449

  Object-oriented method invocation or resolution · CPC title

• G06F8/49

  Partial evaluation · CPC title