Link time program optimization in presence of a linker script

A method for optimizing source code comprises optimizing the source code of files from a computer program at link-time, and receiving, at a linker, a customized linker script defining output sections for files of an executable version of the files of the computer program. The method comprises adding, to intermediate representation files having global or local symbols, metadata comprising default section assignment information for the symbols and recording, for symbols in machine code files, an origin path and an output section. The method further comprises parsing, by the compiler, the intermediate representation files, recording the symbols and related symbol information comprising default section assignment and dependency information of the intermediate representation files, assigning output sections to the symbols based on the default section assignments and instructions from the customized linker script, and linking optimized code of the files of the computer program based on the assigned output sections.

FIELD OF THE DISCLOSURE

The present disclosure relates generally to compilers that compile high-level code to machine code, and more specifically, to link time optimization.

BACKGROUND

In general, a compiler is a computer software program that transforms high-level computer programming code, such as source code written in a human-readable language (e.g. C, C++), into lower-level assembly or machine code (e.g., binary). Compilers utilize various optimization techniques in order to improve the performance of the resulting executable. In general, optimization allows a program to be executed more rapidly or utilize fewer resources. Link time optimization (LTO) is a powerful compilation technique typically utilized in general computing environments, such desktop computers, that allows the broadening of the optimization scope in programming languages that otherwise compile a program one file at a time. That is, the optimization scope can be broadened so that the compiler can compile and optimize more than one file at a time. LTO utilizes a computer program (i.e., a utility) known as a linker, which links together multiple files of a source program, once optimized by the compiler, to a final executable comprising distinct sections of binary code.

A linker script is another utility used in conjunction with a linker, often in embedded application environments. It is used to express a fine degree of control over the final executable image—and namely, the particular sections thereof—produced during the compilation (and optimization) process. Often, though, if a user tries to use a linker script in an LTO environment, the linker utilized in LTO and the linker script itself come into conflict, which makes the two techniques virtually incompatible. Therefore, a need exists to resolve conflicts between these techniques in order to improve compilation and optimization.

SUMMARY

An aspect of the present disclosure provides a method for optimizing source code. The method may comprise optimizing, at a compiler, the source code of files of a computer program at link-time, and receiving, at a linker, a customized linker script defining output sections for files of an executable version of the files of the computer program. The method may then comprise adding, to intermediate representation files having global or local symbols, metadata comprising default section assignment information for the symbols, recording, for symbols in machine code files, an origin path and an output section, and parsing, by the compiler, the intermediate representation files. Then, the method may include recording the symbols and related symbol information comprising default section assignment and dependency information of the intermediate representation files, and then assigning output sections to the symbols based on the default section assignments and instructions from the customized linker script. The method may then comprise linking optimized code of the files of the computer program based on the assigned output sections.

Another aspect of the disclosure provides a system for optimizing source code. The system may comprise a linker and a compiler arranged in a link-time optimization tool flow to produce an link-time optimized executable computer program; a customized linker script that instructs the linker how to arrange output sections in the link-time optimized executable computer program; and an application program interface that enables communication between the linker and compiler and configured to facilitate the arrangement of the output sections of the link-time optimized executable according to the customized linker script. The linker, compiler, and application program interface may be configured to perform a method comprising optimizing, at a compiler, the source code of files of a computer program at link-time, and receiving, at a linker, a customized linker script defining output sections for files of an executable version of the files of the computer program. The method may then comprise adding, to intermediate representation files having global or local symbols, metadata comprising default section assignment information for the symbols, recording, for symbols in machine code files, an origin path and an output section, and parsing, by the compiler, the intermediate representation files. Then, the method may include recording the symbols and related symbol information comprising default section assignment and dependency information of the intermediate representation files, and then assigning output sections to the symbols based on the default section assignments and instructions from the customized linker script. The method may then comprise linking optimized code of the files of the computer program based on the assigned output sections.

Yet another aspect of the disclosure provides a non-transitory, computer-readable storage medium configured to perform a method of optimizing source code. The method may comprise optimizing, at a compiler, the source code of files of a computer program at link-time, and receiving, at a linker, a customized linker script defining output sections for files of an executable version of the files of the computer program. The method may then comprise adding, to intermediate representation files having global or local symbols, metadata comprising default section assignment information for the symbols, recording, for symbols in machine code files, an origin path and an output section, and parsing, by the compiler, the intermediate representation files. Then, the method may include recording the symbols and related symbol information comprising default section assignment and dependency information of the intermediate representation files, and then assigning output sections to the symbols based on the default section assignments and instructions from the customized linker script. The method may then comprise linking optimized code of the files of the computer program based on the assigned output sections.

DETAILED DESCRIPTION

LTO is a highly desirable optimization methodology because it is powerful and works well in very demanding general purpose development environments. In embedded development environments (such as in smartphones), though, LTO is often not used, due to conflicts that exist between LTO and another development technique known as a customized linker script, which is used in order to allow a developer to exert a fine degree of control of an executable in the embedded environment. It would be beneficial to utilize the optimization potential of LTO in conjunction with the fine degree of executable control that is made possible with a linker script, but the two techniques have heretofore been virtually incompatible.

In environments where a customized linker script is used, the linker itself must submit to demands (i.e., conditions or restrictions) specified by the user/developer of the linker script. In traditional build processes, the linker contains default instructions for how a final executable should be linked and arranged, particularly with regard to executable “output sections.” The term “sections,” as used in this disclosure, refers to atomic blocks of code as they are dealt with by the linker. The term “output sections” refers to the sections as they ultimately are arranged in the final executable. When linker scripts are customized by embedded application developers, the instructions contained therein override the default instructions of a linker in order to express fine control over the element assignment to sections and layout of the resulting executable binary image. However, actual LTO code generation is performed by compiler, which is agnostic to custom section assignment to be performed by the linker. Because the linker script overrides default linker instructions, the use of the linker script itself makes traditional LTO (as implemented in general purpose environments) incompatible to use. For the purposes of the present disclosure, all references to “linker scripts” may be considered to refer to customized linker scripts, rather than default instructions in a linker, unless otherwise specified. As one example of the kind of control a linker script may exert over compilation, sometimes a linker script is utilized to prepare the linked image of the executable for more post-processing steps after compilation which might violate implicit assumptions commonly made in compiler. This script creates additional restrictions on the compiler beyond the immediate scope of the compilation process.

In compilation processes wherein a compiler and a linker are used together to build an executable without LTO, there is very limited interaction between the compiler and linker. The only real interaction is a simple progression in which the compiler produces object code that is later linked by the linker. In traditional LTO, the linker might undertake initial pre-processing of code and then invoke the compiler again to implement additional optimizations on extended scope. However, this limited interaction between a compiler and a linker must be changed if a LTO and a linker script are both to be utilized in the same build process. Therefore, the present disclosure provides ways for a higher level of interaction between the compiler and linker.

There are several reasons the lack of real communication between the compiler and the linker creates issues in the presence of a linker script. One reason is that the compiler mainly agnostic of the operating system path information associated with the original source file during the build process. Without path information, it is difficult, if not impossible, to use a linker script. It has not traditionally been desirable to maintain path information inside of a compiler, because it is cumbersome and impractical to do so. Making the compilation procedure sensitive to path information would actually change the very nature of the compilation process, so keeping path information during compilation is not an ideal way to gain linker script functionality. Another reason the LTO process inhibits the use of linker scripts is that the compiler is unaware of the further use of objects (e.g., global, local, and common variables, and objects from a separate object library), and as such, might choose to modify some of them as coming from the same scope, even if they do not. A linker script may demand that multiple copies of particular objects exist in different sections of the final executable.

Yet another reason the LTO process is incompatible with a linker script is because the linker is most often expected to perform garbage collection (i.e., the deletion of unused sections) in the final step of executable construction. The compiler in LTO can inadvertently expose an object needed by the linker script to garbage collection because the compiler typically ignores an object's path or linker script properties. It would not be ideal to restrict the compiler from performing these steps (e.g., modifying objects, and hiding path information) because it would result in suboptimal code generation.

Aspects of the present disclosure provide several additional features that can supplement a traditional LTO process. These features may be referred to as communication channels, interfaces, tools, methods and/or utilities, and they allow the components of an LTO process to work together in a way that enables the use of a linker script in conjunction with the LTO build flow. The sum of each of these features may be referred to as the “solution,” the “system,” or the “method,” but many individual features alone may be novel over prior approaches, and should not necessarily be construed to require the presence of each other individual feature of the solution in all implementations. Still, many embodiments of the system will utilize each inventive feature discussed herein.

FIG. 1is a logical block diagram depicting several aspects of an exemplary embodiment. The diagram depicts a process100of compiling and linking received source code to an executable in an LTO build flow in the presence of a linker script.FIG. 1is a logical diagram and should not be construed to be a hardware diagram. The logical blocks inFIG. 1may be implemented in software, hardware, firmware, or a combination of hardware, software, and firmware. The process outlined inFIG. 1may be implemented by a compiler and a linker that interact with each other and with versions of code at particular steps in the process. The compiler and linker may each be thought of as single software programs broken up into steps to show inputs, outputs, and the timing of communication between each program. For ease of reference, a single compiler is depicted as operating at Compiler (step1)115and Compiler (step2)125with Linker (step1)135and Linker (step2)145. Throughout the disclosure, the compiler may be referred to interchangeably at its first and second steps as “first/second step of the compiler,” “first/second stage of the compilation,” “the compiler at step one/two,” or “the compiler at stage one/two.” The linker may be referred to with similar terminology and reference to the first or second steps or stages.

Compiler (step1)115first receives source code110of a program. As shown, the source code110has example file extensions .c and .cpp, (indicating source code written in C or C++, respectively), but source code may be received in other languages, or may be in a human-readable assembly language. Compiler (step1)115then compiles the source code110into two types of files, the first of which being compiler-specific and platform independent intermediate representations (IR, also referred to as internal representation), designated with a .bc (bit code) file extension, and the second of which being platform specific object code (designated with a .o file extension). Compiler (step1)115performs optimizations that are possible at the level of local scope (i.e., one file or one library) and do not yet require information about the global scope (i.e., a whole program). Most optimizations may be performed later, at Compiler (step2)125.FIG. 2shows how these two types of files compiled at Compiler (step1)115are distinct, and turning now to a discussion of their differences will facilitate an understanding of the present disclosure. While discussing the subsequent figures, reference may still be made to the components inFIG. 1.

As mentioned, and as shown inFIG. 2, the compiler at step one115can generate either compiler-specific IR code220or object code230. Compiler IR code generation includes platform-specific section name generation for each function and object that will be used at link time. The IR code220is often considered “half-baked,” or, in other words, incompletely optimized. Generally, a makefile of the program source code will dictate what portion of the code initially gets compiled into IR and what portion gets compiled into object code, based on considerations such as whether parts of the application should be optimized for speed, size, or a combination of these considerations. Though it contains some optimizations that are possible to perform at the local (file) scope, IR code is typically not readable by the linker (or by the processor, for that matter) until it is further compiled to machine code. It is called “compiler-specific” because it is in a form that is readable only to the particular compiler. Compiler (step1)115does also produce some object code230, which is readable by the linker and ready to be linked. Other aspects ofFIG. 2will be discussed later in the disclosure.

Turning back toFIG. 1, existing libraries140are shown as additional inputs to Linker135,145at steps141and142, respectively. These libraries may, for example, be providing standard C functionality in the embedded environment, or may be libraries from an external project. For example, the libraries140may include firmware code that is presented to Linker135,145as a library, without additional compilation done to it. The existing library140files are designated as .o, because they are present in object code format with all the information needed for linking already present in them.

FIG. 1also shows a linker script148in communication with Linker135,145at interfaces151and152, respectively. As previously discussed, in prior approaches, linker script has been virtually incompatible with LTO flows. The steps that facilitate the linker script support are depicted as interfaces151,153, and154, each of which are highlighted in bold lines. The present disclosure pertains to the functionality of each of these steps, which represent one or more interfaces, communication channels, and/or instructions that allow the linker script to be respected with the LTO tool flow in ways that were not previously available. In particular, the linker script148may interact with Linker (step1)135through interface151, Linker (step1)135may communicate with Compiler (step2)125through interface153, and Linker (step1)135may communicate with Linker (step2)145through interface154. The interface153comprises an application program interface (API) and allows several pertinent aspects of the solution to be implemented, which will be described in detail through the disclosure. Linker (step1)135generates a “preserve list”160to be used by Compiler (step2)125, which is also facilitated by the API153, and which will be described in further detail later in this disclosure. The final steps in the LTO flow100depicted are that Compiler (step2)125compiles all the IR and object files into machine code170, and Linker (step2)145links compiled code from multiple sources to a final executable180.

Each object file, whether it comes from source code that has been compiled in Compiler (step1)115, or from existing object libraries140, includes global, local and common symbols that represent individual named memory objects. The term “symbols” referred to herein is a blanket term that encompasses both functions (i.e., a sequence of instructions in code that executes) and objects (i.e., a declared variable). After this first step of compilation125, the rest of the compilation process is strongly dependent on what symbols are used and where they are used. Dependencies of symbols will be discussed throughout the disclosure, but in particular, each symbol is destined to a particular section of the executable. A problem that exists at this step is that Linker (step1)135cannot parse (or read) the compiler-specific IR to be able to tell what symbols those particular IR files include, or whether the symbols are local, global, or common, and as a result, the linker cannot assign output sections early on in the linking process.

Part of the process of compilation is to remove redundancies in code. Both compilers and linkers, by themselves, can remove redundancies. A compiler, in general, can remove redundancies in a number of ways. A linker can typically also remove redundancies in code, but compilers are generally more efficient and nimble in doing so because they have a better understanding of the code. A compiler performs the bulk of the work of identifying redundancies, and then informs the linker of these redundancies, which allows the linker to perform a process known as garbage collection. Garbage collection is essentially the deletion of code that has been identified as redundant by the compiler. In other words, the compiler gathers up the “garbage” and the linker “collects” it. The ability to eliminate code is a main benefit of the compilation process because it reduces the amount of unnecessary code in the executable, making the final executable shorter and faster to process. However, neither the linker nor the compiler should eliminate code at any point in the compilation process that will ultimately be needed in the final executable, and therefore, if neither the compiler nor the linker know whether a particular symbol will be needed, that code will be preserved and not eliminated. In order to ensure that needed code is not eliminated, the linker provides the preserve list160, in which the linker tells the compiler which symbols it knows of that should be preserved by the compiler. One particular mechanism allows the compiler to more aggressively eliminate code redundancies. Once the preserve list is received by the compiler, all global symbols that are not in the preserve list are recorded and localized to the current module scope. While the process of localization of symbols itself already exists in current compilation processes, localization of global symbols that are not in the preserve list according to the present disclosure allows the compiler to be more aggressive in eliminating redundancies that was previously possible.

As previously discussed, Linker (step1)135cannot read compiler-specific IR, and therefore cannot tell which symbols exist within it. Linkers typically deal with sections, and identify what the linker should do with a particular section (e.g., whether to delete a section, or whether to place the section in a particular part of the output file) based on the symbols in the section. The linker can do this with files that are in object code, but not with files that are in IR. In addition, the compiler itself does not ordinarily keep track of symbols and other symbol information (such as symbol dependencies) within individual files that it is compiling, so it does not typically provide such information to a linker. One aspect of the disclosure is that a new application program interface153is created that allows necessary communication between Linker (step1) and Compiler (step2)125that allows the compiler to assist the linker in identifying symbols within the IR that the compiler has produced, which will be described in further detail presently.

FIG. 3conceptually illustrates an output format of an executable310in traditional LTO without a linker script and an output format of an executable320with a linker script, though the examples depicted are greatly simplified for the purposes of illustration. An executable310in traditional LTO may have a number of predefined sections, such as a .bss section for uninitialized objects, and a .text section for executable code, and a .data section for memory objects. One standard output format of an executable is known as ELF (Extensible and Linkable Format), and can be used here for illustration purposes on how a typical executable produced by a linker in traditional LTO, such as executable310, may have around one or two dozen sections. An executable that is produced as the result of linking under direction of a custom linker script, such as executable320, has sections that are specifically defined by the linker script. These sections likely have different attributes than a typical executable produced by linking in general. Although the linker script-produced executable320does not necessarily have to have more sections, in many implementations, the linker script-produced executable320will have more sections, sometimes numbering in the thousands. This is because, as will be described later, each function and object of a source code file may be placed in its own individual section as part of the present solution. Therefore, executable320is depicted as having many more individual output sections than executable310.

FIG. 4is a logical block diagram showing several components of the LTO tool flow ofFIG. 1in greater detail. The components depicted inFIG. 4are not intended to be a hardware diagram, but are intended to show logical steps and connections implemented in software and/or hardware. Certain components that are present inFIG. 1are omitted fromFIG. 4for the sake of clarity. In one aspect of the disclosure, the solution changes the process of compiler IR code generation to include platform-specific name generation for each function and object destined for LTO. Compiler (step1)415comprises a platform-specific name generation component416. In existing compilation processes, certain flags are provided in source code (more particularly, in the makefile) for particular functions and objects. Certain types of flags, for example, indicate how a particular function should be optimized more for speed or another one more for size. Other types of flags include “-f-function-sections” flags for functions and “-f-data-sections” for objects. These flags allow the assignment of functions and objects to certain output sections. If there is no such flag, all functions will, for example, be placed in the output section “.txt.” However, if a function is flagged with -f-function-section, then the function will be placed in its own specific section, named “.txt.name_of_the_function,” for example. The platform-specific name generation results in a particular function or section being named in this manner. The flagging of functions and objects is an existing capability, but it can be used for implementing aspects of the present disclosure. It is one way that each function and object will be put in its own individual section. A compiler itself can delete sections, but this feature of platform-specific name generation is helpful because the linker itself deals with sections, and has the ability to delete sections, but cannot delete functions or objects. As a result of flagging each function and object, each section now has its own name, and may be dealt with more easily by the linker as well as the compiler. Metadata is used (by the compiler) to store the these flags and other information in association with each symbol. It is contemplated that other ways may be used to name individual sections without departing from the scope or the present disclosure

Turning back toFIG. 2, which shows how the Compiler (step1) produces both IR220and object code230,FIG. 2also illustrates how individual functions and objects may be seen by the linker. IR compilation lines270are shown with individual IR functions271,273and individual objects272,274in their own sections. Metadata275, which is depicted with a small “m,” is associated with each function and object, and is used to store information about each. Similarly, object code compilation lines show function code281and283, and object code282and284. Metadata285is associated with each function and object in object code as well.

Referring again toFIG. 4, the diagram shows how new features in the LTO tool flow facilitate LTO in the presence of a linker script. One aspect of the disclosure is that an API450facilitates communication between the linker at step one435and Compiler (step2)425. Within the API450are several process or method steps, depicted as flowing from either left to right (signifying a communication or request from the linker to compiler) or right to left (signifying a communication or request from compiler to linker). The steps are also depicted in a timing diagram inFIG. 5to more clearly show the sequence of events between the linker and compiler as depicted here inFIG. 4. Each of these process or method steps may be implemented in an algorithm in the API450. Though the process or method steps are depicted in a particular order from top to bottom, they are not necessarily implemented in the particular order, and may be implemented simultaneously or in an overlapping manner in actuality.

Depicted within Linker (step1)435and Compiler (step2)425are various logical block components for implementing aspects of the system. In particular, they implement many of the communications and requests depicted in the API450, as well as other features of the solution. The blocks are logical and are not to be construed as a hardware diagram, and may be implemented by software alone, hardware alone, or a combination of hardware and software.

One aspect of the API450is that it allows Linker (step1)435to request that the compiler parse its own IR in order to identify the symbols contained within the IR and def-use (definition and use) relationships between them at step451. That is, code contained within IR may contain both definitions and uses, but until that IR is parsed, the compiler and linker cannot tell if there are any functions or sections that are not going to be used and could be eliminated. In another aspect, the system API450allows the compiler to delay module dependency analysis at step452. Modules are how calls blocks of code that exist within a particular file are referred to in relation to a compiler and roughly correspond to source code files. During traditional LTO, the linker sends the compiler multiple code modules to be accumulated (or “merged”) into the single optimization scope. In traditional LTO, the sending of the multiple code modules to the compiler for merging is beneficial and allows for greater code optimization by the compiler. However, in the present disclosure, the compiler sends the linker parsed IR with symbol information and dependency information about the symbols with each module that is parsed. If dependency analysis were to be performed by the compiler incrementally as modules are received from the linker, the linker would receive dependency information back incrementally as well, which would be incomplete.

As seen in the API450, at step453, Compiler (step2)425provides the requested symbol table back to Linker (step1)435, which is accomplished by the IR parsing/symbol reading component326. If the dependency analysis is performed by the compiler as each module is received, then Compiler (step2)425cannot tell Linker (step1)435what symbols are used in IR for the whole scope. Therefore, the present solution provides a module dependency analysis delay component427, which accumulates pointers to modules in memory in Compiler (step2)425until all of them are available. Once they are all available, then Compiler (step2)425communicates the symbol resolution (i.e., tells the linker what symbols are used where) at step453. After that, the module merge component428of the compiler merges modules.

An additional drawback to analyzing the dependency of modules incrementally (i.e., as they come in), is that path information, which tells Linker (step2)445in what output section to place certain objects and functions, is also lost. For example, when Linker (step1)435receives files, it receives along with it default path information that says what directory the files come from, and what output sections they should ultimately end up in. As stated previously, there may be default instructions in the linker that specify which files should go in which sections, but in the presence of a linker script, the linker script may also contain different rules that specify particular files to go in different output sections than they otherwise would. In traditional LTO, when the linker provides files to the compiler for optimization, the compiler, as previously discussed, typically takes the modules and merges them for compilation. In this merging process, the path information (also known as “source path” information) of where the content of those files should ultimately end up in the output section, is lost.

In the present solution, Linker (step1)435comprises a path information component436, which has several responsibilities. For one, it memorizes and keeps a list (i.e., records the original source path for each symbol in association with its source module) of the final output section destination for each section. This recording of the original source path for each symbol is necessary for the proper treatment of common symbols at the end of the linking process, which will be discussed in further detail. Additionally, the path information component queries the linker script448, via a linker script query component437, to see whether the linker script specifies a particular output section other than a default one.

The API450of the present solution also allows the linker to correctly place all sections in the final executable in the present of a linker script. As shown, at step470, the API allows Compiler (step2)425to communicate the scope of the optimization to Linker (step1)435. Then the API450, allows the linker to “get,” at step471, the total number of symbols per module that were gathered at the previous step and a way to “get,” each symbol name and default section information at step472and473. The linker receives the symbol information along with the source path at step474to determine the output section for each symbols based on the provided linker script448. Finally, the linker provides the original source path for each symbol at step475, in order to ensure that common symbols are treated properly. By performing these steps, the linker ultimately knows, from the combination of symbols, the source path, and the linker script, where to properly place output sections in the final executable.

Linker (step1)435not only provides the information it has about symbols, sections, and path information to Linker (step2)445, but it also provides resolved section information to Compiler (step2)425, as illustrated in the API450at step454. The compiler keeps this resolved section information along with each object throughout the compilation process.

Additionally, Linker (step1)435provides a preserve list (e.g., preserve list160ofFIG. 1) at step455. A challenge to optimization is presented in an LTO flow in the presence of a linker script because it is the responsibility of Linker (step1)435to not only look at the files in the current scope, but to also look at the files outside that scope to determine what symbols are used in other scopes (to ultimately create the final executable). In existing compilation processes, and in the current implementation, Linker (step1)135gathers a list of these knowable symbols, which is known as a preserve list160, and passes it on to Compiler (step2)125. This list informs Compiler (step2)125which symbols can be discarded, and consequently, which code can be deleted. When a linker script is present, as in the implementations shown, the linker script448also communicates with Linker (step1)435. Both the content of the IR and the linker script are highly influential on the preserve list160. Because the IR is treated conservatively, very few symbols are left off of the preserve list160in case an IR file might need them.

As previously mentioned, one of the tasks a compiler does during compilation in LTO (at Compiler (step2) is to merge all of the modules together before sending them back to Linker (step2). Because of the API450and the steps of communication facilitated therethrough, Compiler (step2)425is able to gather all functions and objects that might be visible to the linker at the final link stage (at Linker (step two)445) and log default output section information that is stored in the IR. This gathering of all functions and objects may be done on the level of each individual module so that the module-to-symbol relationship is not lost. Then, Compiler (step2)425merges all modules into a single optimization scope via the module merge component428. and internalizes symbols with respect to available output section information and the preserve list. This internalization produces different results from existing localization processes.

As a result of the additional communication between the linker and compiler via the APIs, compilation can commence with the use of the additional output section information. InFIG. 4, this is depicted as the section determination component429within the module merge component428, to illustrate that the use of section information by the compiler takes place during the module merge process. Because the compiler now knows what output sections certain functions and objects will ultimately be placed, the compiler can use that information to both restrict and facilitate various compilation decisions. It is contemplated that, in general, that different output sections can be treated differently. When the compiler has this output section information, the compiler can be much more effective at reducing the size of compiler code without an impact on performance. Additionally, more input from a used may be solicited via a linker script to assign various properties to various output sections. These properties might include “hot or cold,” performance vs size tradeoff, or even a “firewall requirement that no control flow transfer is possible between certain output sections. Additional input from a user can also allow for improved security features.

At the end of the compilation process, the compiler materializes local variables and functions to their intended output sections, and leaves global and common objects to be placed by Linker (step2)445. Linker (step2)445also conducts the final assignment of sections and a final step of garbage collection, resulting in the final executable image.

The overall optimization process of the present disclosure as described in relation to various components of the linker, compiler, and API inFIG. 4may also be understood by describing the process in terms of timing.FIG. 5shows a timing diagram with simple linear representations of a compiler510and linker520, with steps1-13of the process shown taking place in the linker, compiler, or both in relation to time. The compiler510and linker520are not depicted as having two separate stages in the way that they are depicted inFIG. 4, but it is to be understood that the functionality described in relation toFIG. 5is the same as that described in relation toFIG. 4. As such, it is also to be understood that the API (depicted inFIG. 4, but not depicted inFIG. 5) enables the communication between the compiler510and the linker520.

Turning now to each of the steps inFIG. 5, at step1, the compiler510receives a selection of source files (e.g., .c, .cpp, etc.). Based on the makefile of the source code, some of the source files are initially compiled to IR (.bc) and others to object code (.o). Then, according to the method of the present disclosure, for each symbol (i.e., function or object) that is destined to be compiled to IR, the compiler adds metadata containing the symbol's default section assignment.

Next, at step2, linking begins in the linker520. The linker520receives a selection of compiled files (both in IR and object code) as well as a linker script. For each symbol that is in object code, both their origin path and their output section is recorded, and their dependency information is updated. For each IR file, the origin path is also recorded, but because their output sections and dependencies cannot be read by the linker, the linker requests the compiler to parse the IR. However, before sending the IR and the request back to the compiler, the linker, at step3, reads the IR file into memory.

Once the linker sends the IR and parsing request to the compiler (as depicted by the arrow between steps3and4), an aspect of the present disclosure is that the compiler, at step4, receives a memory buffer containing the content of the .bc file (the IR) and reads it as a compiler module. The compiler them parses the content of the module and records information about each symbol. Included in this recorded symbol information is the default section assignment that was initially recorded in the metadata for each symbol in step1. Another aspect of the disclosure is that dependencies are recorded for each symbol that exists in the IR module. Then, the module is merged with any previously read IR modules. Once parsing is complete, the compiler informs the linker that it is complete, as represented by the arrow between steps4and5. The requesting, parsing, recording, merging, and communicating back to the linker may be facilitated in whole or in part by the API between the compiler510and the linker520.

Step5is depicted as taking place at both the compiler510and the linker520. At step5, the linker520actually receives the symbol information that has been parsed and recorded from the compiler510. Step6is also depicted as occurring at both the linker520and compiler510. At step6, in the linker520, the linker uses the default section information for all the symbols in IR that were received in step5. Then, using the linker script, the linker520is able to assign output sections to the symbols that were in IR and then inform the compiler about that output section assignment (depicted at compiler510step6). This step allows the fine control of output sections according to the linker script that would not have been possible if the linker520did not have the symbol information for IR files. Steps2-6may be repeated by the linker520and the compiler510until all files of the source code are processed.

Once all input files have been processed, and all symbols for both object code and IR have been accounted for, a full dependency graph between all the symbols is available, and the linker can generate a preserve list, which it does at step7. Then, the linker520sends the preserve list to the compiler (as depicted by the arrow between steps7and8). Then, at step8, at the compiler510, all global symbols that are not in the preserve list are localized to the current module. In prior approaches, symbols could be localized, but in the present disclosure, the preserve list has full symbol information and a dependency graph that allows more aggressive optimizations by the compiler510.

Next, at step9, the compiler520performs global optimization to the whole file scope. These optimizations are performed in view of the assigned output sections for each symbol. If, for some reason, a normal optimization that would be performed by the compiler520at this stage would violate the intended output section assignment as dictated by the linker script, the optimization is not performed, which is one advantage of the present disclosure. An additional advantage to the compiler510having all the output section assignments at this stage is that additional optimizations become available because of the output section information.

Next, at step10, machine specific code generation is performed. During this step, the compiler assigns every symbol to a specific section, as required by ELF standards. As a result of the linker script output section assignment, all local symbols are assigned to their final output sections. All global symbols, however, are assigned to their default sections, as also required by ELF standards. Then, at step11, the original symbol scope is restored. Previously localized symbols and any global symbols that were not eliminated during optimization are restored back to global scope. At step12, one or more object files are generated by the compiler510. These object files are then passed to the linker, as represented by the arrow between steps12and13. At step13, the final linking starts and results in the final executable image being created.

The solution of the present disclosure provides a number of advantages. First and foremost, it provides a way to utilize a linker script in an LTO tool flow, which was not previously possible. The interaction that is made possible by the present solution between the components of the LTO tool flow did not previously exist because it was complex for the linker and compiler to interact. For example, a “positive feedback loop” effect between the linker and compiler made interactions difficult. Another reason interaction between the linker and the compiler was difficult was because in previous approaches, the compiler was not aware of what steps would subsequently be taken or performed by the linker on the code produced by the compiler. The complexity of making the compiler aware of what the linker would do with compiled machine code had previously been deemed impractical. In the present solution, APIs between the compiler and linker allow for communication between the two entities, and algorithms for achieving the communication functionality provide the benefit of being able to perform LTO in the presence of a linker script. Furthermore, the use of resolved output section information allows the linker script to be used during both classical and IPO (Inter Procedural Optimizations). This resolved section information allows additional IPO optimizations that are not possible without it.

FIG. 7is a flowchart which may be traversed to implement a method700of code optimization.

Referring next toFIG. 6, it is a block diagram depicting an exemplary machine that includes a computer system600within which a set of instructions can execute for causing a device to perform or execute any one or more of the aspects and/or methodologies for static code scheduling of the present disclosure. The components inFIG. 4are examples only and do not limit the scope of use or functionality of any hardware, software, embedded logic component, or a combination of two or more such components implementing particular embodiments.

Computer system600may include a processor601, a memory603, and a storage608that communicate with each other, and with other components, via a bus640. The bus640may also link a display632, one or more input devices633(which may, for example, include a keypad, a keyboard, a mouse, a stylus, etc.), one or more output devices634, one or more storage devices635, and various tangible storage media636. All of these elements may interface directly or via one or more interfaces or adaptors to the bus640. For instance, the various tangible storage media636can interface with the bus640via storage medium interface626. Computer system600may have any suitable physical form, including but not limited to one or more integrated circuits (ICs), printed circuit boards (PCBs), mobile handheld devices (such as mobile telephones or PDAs), laptop or notebook computers, distributed computer systems, computing grids, or servers.

Processor(s)601(or central processing unit(s) (CPU(s))) optionally contains a cache memory unit602for temporary local storage of instructions, data, or computer addresses. Processor(s)601are configured to assist in execution of computer readable instructions. Computer system600may provide functionality for the components depicted inFIG. 1as a result of the processor(s)601executing non-transitory, processor-executable instructions embodied in one or more tangible computer-readable storage media, such as memory603, storage608, storage devices635, and/or storage medium636. The computer-readable media may store software that implements particular embodiments, and processor(s)601may execute the software. Memory603may read the software from one or more other computer-readable media (such as mass storage device(s)635,636) or from one or more other sources through a suitable interface, such as network interface620. The software may cause processor(s)601to carry out one or more processes or one or more steps of one or more processes described or illustrated herein. Carrying out such processes or steps may include defining data structures stored in memory603and modifying the data structures as directed by the software.

The memory603may include various components (e.g., machine readable media) including, but not limited to, a random access memory component (e.g., RAM604) (e.g., a static RAM “SRAM”, a dynamic RAM “DRAM, etc.), a read-only component (e.g., ROM605), and any combinations thereof. ROM605may act to communicate data and instructions unidirectionally to processor(s)601, and RAM604may act to communicate data and instructions bidirectionally with processor(s)601. ROM605and RAM604may include any suitable tangible computer-readable media described below. In one example, a basic input/output system606(BIOS), including basic routines that help to transfer information between elements within computer system600, such as during start-up, may be stored in the memory603.

Fixed storage608is connected bidirectionally to processor(s)601, optionally through storage control unit607. Fixed storage608provides additional data storage capacity and may also include any suitable tangible computer-readable media described herein. Storage608may be used to store operating system609, EXECs610(executables), data611, API applications612(application programs), and the like. Often, although not always, storage608is a secondary storage medium (such as a hard disk) that is slower than primary storage (e.g., memory603). Storage608can also include an optical disk drive, a solid-state memory device (e.g., flash-based systems), or a combination of any of the above. Information in storage608may, in appropriate cases, be incorporated as virtual memory in memory603.

In one example, storage device(s)635may be removably interfaced with computer system600(e.g., via an external port connector (not shown)) via a storage device interface625. Particularly, storage device(s)635and an associated machine-readable medium may provide nonvolatile and/or volatile storage of machine-readable instructions, data structures, program modules, and/or other data for the computer system600. In one example, software may reside, completely or partially, within a machine-readable medium on storage device(s)635. In another example, software may reside, completely or partially, within processor(s)601.

Computer system600may also include an input device633. In one example, a user of computer system600may enter commands and/or other information into computer system600via input device(s)633. Examples of an input device(s)633include, but are not limited to, an alpha-numeric input device (e.g., a keyboard), a pointing device (e.g., a mouse or touchpad), a touchpad, a joystick, a gamepad, an audio input device (e.g., a microphone, a voice response system, etc.), an optical scanner, a video or still image capture device (e.g., a camera), and any combinations thereof. Input device(s)633may be interfaced to bus640via any of a variety of input interfaces623(e.g., input interface623) including, but not limited to, serial, parallel, game port, USB, FIREWIRE, THUNDERBOLT, or any combination of the above.

In particular embodiments, when computer system600is connected to network630, computer system600may communicate with other devices, specifically mobile devices and enterprise systems, connected to network630. Communications to and from computer system600may be sent through network interface620. For example, network interface620may receive incoming communications (such as requests or responses from other devices) in the form of one or more packets (such as Internet Protocol (IP) packets) from network630, and computer system600may store the incoming communications in memory603for processing. Computer system600may similarly store outgoing communications (such as requests or responses to other devices) in the form of one or more packets in memory603and communicated to network630from network interface620. Processor(s)601may access these communication packets stored in memory603for processing.

Examples of the network interface620include, but are not limited to, a network interface card, a modem, and any combination thereof. Examples of a network630or network segment630include, but are not limited to, a wide area network (WAN) (e.g., the Internet, an enterprise network), a local area network (LAN) (e.g., a network associated with an office, a building, a campus or other relatively small geographic space), a telephone network, a direct connection between two computing devices, and any combinations thereof. A network, such as network630, may employ a wired and/or a wireless mode of communication. In general, any network topology may be used.

Information and data can be displayed through a display632. Examples of a display632include, but are not limited to, a liquid crystal display (LCD), an organic liquid crystal display (OLED), a cathode ray tube (CRT), a plasma display, and any combinations thereof. The display632can interface to the processor(s)601, memory603, and fixed storage608, as well as other devices, such as input device(s)633, via the bus640. The display632is linked to the bus640via a video interface622, and transport of data between the display632and the bus640can be controlled via the graphics control621.

In addition to a display632, computer system600may include one or more other peripheral output devices634including, but not limited to, an audio speaker, a printer, and any combinations thereof. Such peripheral output devices may be connected to the bus640via an output interface624. Examples of an output interface624include, but are not limited to, a serial port, a parallel connection, a USB port, a FIREWIRE port, a THUNDERBOLT port, and any combinations thereof.

In addition or as an alternative, computer system600may provide functionality as a result of logic hardwired or otherwise embodied in a circuit, which may operate in place of or together with software to execute one or more processes or one or more steps of one or more processes described or illustrated herein. Reference to software in this disclosure may encompass logic, and reference to logic may encompass software. Moreover, reference to a computer-readable medium may encompass a circuit (such as an IC) storing software for execution, a circuit embodying logic for execution, or both, where appropriate. The present disclosure encompasses any suitable combination of hardware, software, or both.