JP3625878B2 - Stack area allocation method by the compiler - Google Patents

Description

[0001]
[Industrial application fields]
The present invention relates to a stack area allocation method by a compiler (translation routine) applied to a system description language such as C language.
[0002]
[Technical background]
A system description language represented by C language has higher development efficiency than assembly language and is suitable for the development of a large-scale system, but has a drawback that it uses a large amount of memory. When creating a program for a system, unlike the case of creating a program that runs on a personal computer or workstation, it is required to reduce the memory capacity even with a single byte. It has become.
[0003]
[Prior art]
A program written in a system description language is translated into a machine language that can be executed by the controller by a dedicated compiler, and then loaded into a memory and executed. The arrangement of programs in the memory space is divided into code (instructions) and data (variables) portions, and appropriate codes are executed with reference to the values of the variables. For example, if there is an addition instruction called ADD, the execution result of the instruction ADD (A, B) is an addition value of the contents of variables A and B.
[0004]
Here, there are two types of variables: those that are always secured during execution of the program (static variables) and those that are secured only when a predetermined function is called (dynamic variables). The area of static variables is fixedly secured on the memory, while each variable is allocated to the stack area on the memory as needed for dynamic variables.
FIG. 5 is a conceptual diagram of a conventional stack area. Here, for convenience of explanation, a stack area having a width of 4 bytes is shown, but the present invention is not limited to this.
[0005]
Each of V _{1 to} V ₁₄ is a variable and has a type (type; for example, a fixed-point numeric type, a floating-point single-precision numeric type, a floating-point double-precision numeric type,...) In order of address from the largest to the smallest. Assigned. That is, V _{1 to} V ₄ have a maximum size (4 byte size), V _{5 to} V ₁₀ have an intermediate size (2 byte size), and V _{11 to} V ₁₄ have a minimum size (1 Byte size) type. Note that these types and sizes are for illustrative purposes and do not specify actual variables.
[0006]
Here, the relationship between the declaration order of variables and the memory reduction effect will be described. Assuming that the order of declaration of variables is “1 byte”, “4 bytes”, “2 bytes”, and “4 bytes”, the memory image at this time is as shown in FIG. The numbers (1, 4, 2, 4) in the figure indicate the size of the variable type. According to this, there is a space of 3 bytes next to the 1-byte variable, and a space of 2 bytes next to the 2-byte variable. The number (1 + 4 + 2 + 4 = 11 bytes) plus an empty byte (5 bytes) results in a size (16 bytes). On the other hand, the memory image when the declaration order is descending, that is, “4 bytes”, “4 bytes”, “2 bytes”, “1 byte” is as shown in FIG. The empty space is only the last one byte, and the size of the stack memory is 12 bytes including the empty bytes. Therefore, the memory can be reduced by 4 bytes as compared with FIG.
[0007]
[Problems to be solved by the invention]
However, in the stack area allocation method by such a conventional compiler, the allocation order is changed from the largest type to the smallest type. For example, in the case of an architecture whose access range differs depending on the size of the type, stack There is a problem that the number of accesses to a variable located behind the area (that is, a variable with a small type size) increases, resulting in poor efficiency.
[0008]
FIG. 7 is a conceptual diagram showing a range in which the stack area can be accessed by one instruction, and the access range (the range of 1-byte access) for the variable located at the end of the stack area is the narrowest. Therefore, for example, since V _{11 to} V ₁₄ in FIG. 5 cannot be accessed at a time, there is a problem that the execution speed of the program becomes slower as the call frequency of the variable having a smaller type size increases.
[0009]
【the purpose】
Therefore, an object of the present invention is to solve the problem of a decrease in execution speed when applied to an architecture whose access range differs depending on the type size by reversing the variable allocation order.
[0010]
[Means for Solving the Problems]
In order to achieve the above object, the present invention provides a step of allocating each variable according to type size, a step of selecting the sort order of the variables as either ascending or descending, and a size when ascending order is selected. characterized in that the sort of small variable to large variable, comprising the steps of rearranging to less variable from longer variables when descending is selected, the steps of allocating the stack area in the order of the sort, the And
Note that the ascending order may be selected when the required specifications of the system prioritize the file size or speed, and the descending order may be selected when the required specifications prioritize the stack size reduction.
[0011]
Also, a step of allocating each variable according to type size, a step of rearranging from a small variable to a large variable in ascending order, and a step of allocating to the stack area in the order of rearrangement so that the small variable comes first And dividing the total size for each allocated size by a predetermined size, allocating the quotient part according to the order of the sizes, and allocating the remainder of the division after the allocation is completed. , Including.
The predetermined size may be a size that can be accessed with one instruction.
[0012]
Also, a step of allocating each variable according to type size, a step of rearranging from a small variable to a large variable in ascending order, and a step of allocating to the stack area in the order of rearrangement so that the small variable comes first And dividing a variable in the stack area and allocating the divided portion to the end of the stack.
[0013]
[Action]
In the present invention, a variable having a small size is placed in front of the stack area. Therefore, even when applied to an architecture whose access range differs depending on the type size, a small variable can be accessed with one instruction, and the execution speed of the program can be improved.
[0014]
【Example】
Embodiments of the present invention will be described below with reference to the drawings.
1 to 4 are views showing an embodiment of a stack area allocation method by a compiler according to the present invention.
In FIG. 1, 1 is a pre-processing unit, and 2 is a variable allocation unit. As shown in FIG. 2, the preprocessing unit 1 distributes each variable (data) for each type size (boundary matching value) and reduces the stack size according to the design specifications of the program. And step 12 for deciding whether to prioritize execution speed (or program size; also referred to as file size), branching to (1) if priority is given to stack size, and if priority is given to execution speed Branch to (2).
[0015]
Again, in FIG. 1, 20 and 21 are stack areas to which variables are assigned, but 20 corresponds to limb (1) and 21 corresponds to limb (2). In the stack area 20, as in the conventional example described at the beginning, each variable is rearranged in descending order from the largest size to the smallest size, and assigned so that the large size variable comes first. On the other hand, in the stack area 21, the variables are rearranged in ascending order from the smallest size to the largest, and assigned so that the small size variable comes first.
[0016]
For example, 4 bytes of variables V _{1 to} V ₄ are allocated to the 4th line from the first line of the left stack area 20, and 2 bytes of variables V _{5 to} V ₁₀ are allocated to the 5th to 7th lines. assigned, the last line is the variable _V 11 _{~V 14} of 1 byte size assigned, the variable _V 11 _{~V 14} of 1 byte size in the first line of the right-hand stack area 21 is allocated, the second line the fourth line is variable _V 5 _{~V 10} of 2-byte size assigned from the last line variables _V 1 ~V ₄ of 4 byte size is allocated from the line 5. That is, the stack area 20 is assigned in “descending order”, and the stack area 21 is assigned in “ascending order”.
[0017]
Here, a range that can be accessed with one instruction is shown between the two stack areas 20 and 21 according to the size of the mold. In the case of 4-byte data access, the entire area falls within the range, but 2-byte data access and 1-byte data access are limited to a part of the area.
Therefore, when the variables V _{11 to} V ₁₄ in the left stack area 20 are accessed, it is necessary to perform 1-byte access with a plurality of instructions, which is not efficient, but the variables V _{11 to} V ₁₄ in the right stack area 21 are set. In the case of access, since the variables V _{11 to} V ₁₄ are located at the head of the area, that is, within the range of 1-byte access, only one instruction is required and efficiency is high.
[0018]
As described above, according to the present embodiment, by arranging the variable allocation in the stack area in ascending order, it is possible to improve the access efficiency with respect to a variable having a small type size, and to obtain an excellent effect that the execution speed of the program can be improved. . In the case of prioritizing the stack size, the assignment may be in descending order as before, and “ascending order” and “descending order” may be appropriately selected according to the required specifications.
[0019]
Also, when sorting variables in ascending order, the total size of each type of variable is divided by a predetermined size, the quotient part is the target of sorting, and the remainder is allocated after the sorting order. You may do it.
FIG. 3 is a schematic flow of the rearrangement. In this flow, first, in step 31, all variables (data) are distributed for each type size (boundary matching value), and then in step 32, the total size of the distributed data (that is, the variable of each type is changed). Total size) and data are checked. Next, in step 33, the total size is divided by a predetermined size (for example, the maximum boundary alignment value) and divided into a quotient part (divided part) and a remainder part. The loop is repeated for each type of matching value, and each variable is assigned in ascending order from the smallest boundary matching value. Finally, in step 36, the remainder is allocated thereafter.
[0020]
For example, as shown in FIG. 4 (a), when data having a 1-byte type ("1" in the figure) continues nine times, the 1-byte type data can be accessed with one instruction. If the range is A, the total size of this data type is 9 bytes, and the maximum boundary alignment value is 8 bytes, so the quotient part is 8 bytes and the remainder part is 1 byte. Therefore, in this case, the last 1 byte of 1-byte type data is allocated at the end of the stack.
[0021]
Or, if it is a variable that can be divided in the stack, it can be as follows. For example, as shown in FIG. 4B, when this variable can be divided by one variable (“5” in the figure) having a 5-byte type, the 3-byte portions (3) and 2 It may be divided into a byte part (2) and the 2-byte part (2) may be allocated at the end of the stack.
[0022]
【The invention's effect】
According to the present invention, by arranging the variable allocation in the stack area in ascending order, even when applied to an architecture whose access range differs depending on the type size, a small variable can be accessed with one instruction, and the execution speed of the program is improved. it can.
[Brief description of the drawings]
FIG. 1 is a conceptual diagram of an embodiment.
FIG. 2 is a schematic flow of pre-processing of one embodiment.
FIG. 3 is a schematic flow of variable division that is preferably applied to one embodiment.
FIG. 4 is a conceptual diagram of variable division that is preferably applied to one embodiment.
FIG. 5 is a conceptual diagram of a conventional stack area.
FIG. 6 is a relationship diagram between the declaration order of variables and the memory reduction effect.
FIG. 7 is a conceptual diagram showing a relationship between a mold size and an access range.
[Explanation of symbols]
V ₁ ~V _14: variable 20 and 21: the stack area

Claims (5)

Distributing each variable by type size; and
Selecting the order of rearranging the variables as either ascending or descending;
Reordering from a small variable to a large variable when ascending order is selected , and reordering from a large variable to a small variable when descending order is selected ;
Stack area allocation method according to the compiler, which comprises the steps of: allocating a stack area in the order of the sort. If the system requirement specification gives priority to file size or speed, select the ascending order,
2. The stack area allocation method by a compiler according to claim 1, wherein the descending order is selected when the requirement specification gives priority to the reduction of the stack size. Distributing each variable by type size; and
Reordering small to large variables in ascending order;
Allocating the stack area in the order of the rearrangement so that the variable with the smallest size comes first,
Dividing the total size for each allocated size by a predetermined size, and assigning the quotient portion according to the order of the sizes;
Allocating the remainder of the division after the allocation is completed, and a stack area allocation method by a compiler. 4. The stack area allocation method by a compiler according to claim 3, wherein the predetermined size is a size that can be accessed by one instruction. Distributing each variable by type size; and
Reordering small to large variables in ascending order;
Allocating the stack area in the order of the rearrangement so that the variable with the smallest size comes first,
Splitting a variable in the stack area and allocating the divided part to the end of the stack.

Images