Diagnosing alias violations in memory access commands in source code

A computer implemented method, apparatus, and computer usable program code for facilitating debugging of source code. A set of indirect memory references is identified in the source code and points-to records are generated for the source code. The set of indirect memory references are validated using the points-to records and an aliasing rule to identify zero or more indirect memory references having a potential aliasing problem. In a case in which the zero or more indirect memory references comprise at least one indirect memory reference, the at least one indirect memory reference is in the set of indirect memory references. Responsive to a determination that the zero or more indirect memory references comprise at least one indirect memory reference, a report is generated identifying at least one location in the source code associated with the at least one indirect memory reference. The report is stored.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to an improved data processing system and in particular to the compilation of computer usable program code. Still more particularly, the present invention relates to diagnosing alias violations in memory access commands during an optimizing compilation process.

2. Description of the Related Art

Compilers are software programs used to translate program instructions written in a source language to equivalent program instructions written in a target language. The source language is a high-level language designed to be interpreted by humans, the target language is usually a low-level language suitable for execution by computer hardware. Thus, the compiler is said to compile the source code into executable code.

Optimizing compilers are used to improve the quality of the program instruction generated without changing the intended meaning of the source code. For example, an optimizing compiler can reduce the time required to execute the program instructions or the memory footprint of the resulting program. During the optimization process, the source code is often re-ordered so that commands are executed more efficiently.

In the process of translating source code to target code, compilers routinely reorder program instructions to improve the runtime performance of the generated target code. Because instruction reordering may not preserve the original semantics of a program, a compiler must determine that reordered instructions do not reference the same or overlapping memory regions before reordering can be performed. For example, a store instruction can be safely moved prior to a subsequent load instruction if the compiler can determine that the memory region to which the store instruction writes and the memory region which is read by the load instruction do not overlap. If the instructions do reference the same memory region, then reordering could cause the reordered program to perform incorrectly. For example, reordering could cause a new value to be stored in memory before an instruction to load from the same memory is executed, when the value expected to be loaded was the older value (i.e., before the older value was overwritten by the new value). However, some reordered instructions may reference the same memory region. Additionally, two load instructions referencing the same memory region can be freely interchanged, or reordered, if no intervening store instruction to that memory region exists.

A memory region refers to a memory address and size which defines a contiguous block of memory. A read or write instruction to a memory region may be referred to as a memory access. In the context of this application an indirect memory access command or reference refers to one of a set of memory regions and a direct memory access command or reference refers to a single memory region.

Two or more memory accesses which refer to memory regions which overlap are said to alias one another. The presence of aliasing limits the amount of reordering a compiler can safely perform. The alias set of a memory access in a program is the set of the other memory accesses in that program which may refer to a memory region which overlaps with the memory region referred to by that memory access.

A compiler does not always detect all problems that can be caused by aliasing. Determining all possible aliasing relationship in a program is often computationally intractable. Therefore, programming languages have established rules, known as alias rules, which describe which memory references may alias one another. Additionally, compilers often allow the user to choose an alias rule to which the source program must conform. Thus, an alias rule represents a “contract” between the programmer and the compiler. If the program being compiled does not conform to the chosen alias rule, then the compiler might optimize the program in such a way as to modify the original semantics, or meaning, of the program.

Furthermore, aliasing violations often prove costly as unexpected program behavior may only appear at the highest levels of optimization, or in time as code optimizers evolve and take advantage of previously unexploited opportunities. The term highest optimization levels refer to a highest degree of code rearrangement performed by a compiler to maximize efficiency of the resulting executable code.

SUMMARY OF THE INVENTION

The aspects of the present invention provide for a computer implemented method, apparatus, and computer usable program code for facilitating debugging of source code. A set of indirect memory references is identified in the source code and points-to records are generated for the source code. The set of indirect memory references are validated using the points-to records and an aliasing rule to identify zero or more indirect memory references having a potential aliasing problem. In a case in which the zero or more indirect memory references comprise at least one indirect memory reference, the at least one indirect memory reference is in the set of indirect memory references. Responsive to a determination that the zero or more indirect memory references comprise at least one indirect memory reference, a report is generated identifying at least one location in the source code associated with the at least one indirect memory reference. The report is stored.

In another illustrative embodiment the report further includes trace back information. In another illustrative embodiment the trace back information includes a program symbol which the first indirect memory reference is not allowed to alias according to the aliasing rule. In this case, the program symbol refers to a memory region to which the first indirect memory reference also refers.

In another illustrative embodiment the trace back information includes a sequence of statement locations in the source code related to the first indirect memory reference. In another illustrative embodiment the trace back information includes a program symbol which the first indirect memory reference is not allowed to alias according to the aliasing rule. In this case, the program symbol refers to a memory region to which the first indirect memory reference also refers, and the trace back information includes a sequence of statement locations in the source code related to the first indirect memory reference. In another illustrative embodiment validating is further performed using a directed graph built using the points-to records.

Another illustrative embodiment provides for a computer implemented method for facilitating debugging of source code. An alias analysis is performed of the source code to generate points-to records having points-to information. A directed graph is constructed based on the points-to records. The directed graph includes edges and points-to entries. The edges and points-to entries are annotated in the directed graph with coordinate information. The points-to entries are propagated in the directed graph along the edges. An aliasing rule is applied to identify, using the directed graph, zero or more lines of code containing a potential aliasing violation. In a case in which the zero or more lines of code include at least one line of code, the at least one line of code is in the source code. A report is generated. The report includes an identification of the zero or more lines of code. The report is stored.

In another illustrative embodiment, when the zero or more lines of code include at least one line of code, the report further includes trace back information. The trace back information includes locations of program statements in the source code that lead to the potential aliasing violation.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

With reference now to the Figures and in particular with reference toFIG. 1, a pictorial representation of a data processing system is shown in which the aspects of the present invention may be implemented. Computer100is depicted which includes system unit102, video display terminal104, keyboard106, storage devices108, which may include floppy drives and other types of permanent and removable storage media, and mouse110. Additional input devices may be included with personal computer100, such as, for example, a joystick, touchpad, touch screen, trackball, microphone, and the like. Computer100may be any suitable computer, such as an IBM® eServer™ computer or IntelliStation® computer, which are products of International Business Machines Corporation, located in Armonk, N.Y. Although the depicted representation shows a personal computer, other embodiments of the present invention may be implemented in other types of data processing systems, such as a network computer. Computer100also preferably includes a graphical user interface (GUI) that may be implemented by means of systems software residing in computer readable media in operation within computer100.

With reference now toFIG. 2, a block diagram of a data processing system is shown in which aspects of the present invention may be implemented. Data processing system200is an example of a computer, such as computer100inFIG. 1, in which code or instructions implementing the processes of the present invention may be located. In the depicted example, data processing system200employs a hub architecture including a north bridge and memory controller hub (MCH)202and a south bridge and input/output (I/O) controller hub (ICH)204. Processor206, main memory208, and graphics processor210are coupled to north bridge and memory controller hub202. Graphics processor210may be coupled to the MCH through an accelerated graphics port (AGP), for example.

Instructions for the operating system, the object-oriented programming system, and applications or programs are located on storage devices, such as hard disk drive226, and may be loaded into main memory208for execution by processor206. The processes of the present invention may be performed by processor206using computer implemented instructions, which may be located in a memory such as, for example, main memory208, read only memory224, or in one or more peripheral devices.

The aspects of the present invention provide for a computer implemented method, apparatus, and computer usable program code for compiling source code. The methods of the present invention may be performed in a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2.

A “compiler” is a computer program that translates a series of program instructions written in a source computer language into program instructions written in a target computer language, or otherwise modifies the code of the source code. A “compiler” can also be an “optimizing compiler.”

An “optimizing compiler” is a computer program that modifies program source code in order to generate executable code that makes efficient use of the hardware resources available on the target machine. The word “optimization” and related terms are terms that refer to improvements in speed, size, and/or efficiency of a computer program, and do not purport to indicate that a computer program has achieved, or is capable of achieving, an “optimal” or perfectly speedy/perfectly efficient state.

The terms “alias” and “aliasing” refer to a situation in which memory access commands access memory regions that overlap each other.

“Alias analysis” is a technique in compiler theory, used to determine if a storage location may be accessed in more than one manner. Two pointers are said to be aliased if the two pointers point to overlapping memory locations.

“Points-to information” describes to which set of memory regions a memory access command can potentially point. If more than one memory region can possibly exist, the particular memory region cannot, in general, be statically determined.

The aspects of the present invention provide for a computer implemented method, apparatus, and computer usable program code for facilitating debugging of source code. The aspects of the present invention can be implemented in a data processing system, such as data processing system100inFIG. 1or data processing system200inFIG. 2.

In an illustrative example, a set of indirect memory references is identified in the source code and points-to records are generated for the source code. The set of indirect memory references are validated using the points-to records and an aliasing rule to identify zero or more indirect memory references having a potential aliasing problem. In a case in which the zero or more indirect memory references comprise at least one indirect memory reference, the at least one indirect memory reference is in the set of indirect memory references. Responsive to a determination that the zero or more indirect memory references comprise at least one indirect memory reference, a report is generated identifying at least one location in the source code associated with the at least one indirect memory reference. The report is stored.

In the illustrative embodiments described herein, the result of a points-to analysis is a starting point information used for the propagation of source coordinate data. As described herein, the points-to analysis is used such that the content of an alias set can be traced back to the origin in the source code of the alias set.

The illustrative embodiments provide for attaching or labeling coordinate information to the point-to entries of the directed graph as the points-to entries are propagated through the directed graph. This mechanism of recording the coordinate information to the entries and augmenting the coordinate information as points-to entries move along the directed graph through the graph edges allows one to provide trace back information. The trace back information includes, among other features, the line in the source code which contains the potential aliasing violation. Note that what is propagated through the edges in the directed graph are the point-to entries which acquire the coordinate information associated with the graph edges they traverse.

FIG. 3is a block diagram of a known compiler. Source code300is created by one or more of a number of known techniques, such as automatically, or by a human programmer. Compiler302and executable code304are computer usable programs that can be used in a data processing system, such as data processing system100inFIG. 1or data processing system200inFIG. 2.

Source code300defines how a program will eventually operate, but source code300is usually not in a desired format for execution on a data processing system. Instead, source code300is often in a format that is easier for a human to interpret. After source code300has been defined, source code300is provided to compiler302. A typical compiler is a computer program that translates a series of statements written in a first computer language, such as source code300, into a second computer language, such as executable code304. The second computer language, such as executable code304, is often called the object or target language.

Thus, compiler302is, itself, a computer program designed to convert source code300into executable code304. After compiler302has performed its programmed actions on source code300, compiler302outputs executable code304. Executable code304is generally in a desired computer-usable format and is ready for use in a data processing system.

Typical compilers output objects that contain machine code augmented by information about the name and location of entry points and external calls to functions not contained in the object. A set of object files, which need not have come from a single compiler provided that the compilers used share a common output format, may then be linked together to create the final executable code. The executable code can then be run directly by a user.

Most compilers translate a source code text file, written in a high level language, to object code or machine language, such as into an executable .EXE or .COM file that may run on a computer or a virtual machine. However, translation from a low level language to a high level language is also possible. Such a compiler is normally known as a decompiler if the compiler is reconstructing a high level language program which could have generated the low level language program. Compilers also exist which translate from one high level language to another high level language, or sometimes to an intermediate language that still needs further processing.

FIG. 4is a block diagram illustrating aliasing in two memory regions. Memory access command400and402can be implemented using source code300or executable code304in a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2. Memory region404and memory region406are memory regions within a memory of a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2.

Memory access command400and memory access command402each attempt to access two different memory regions, memory region404and memory region406. Memory region404and memory region406overlap as shown by the hatch marks. Because memory access command400and memory access command402access overlapping memory regions, memory access command400and memory access command402are said to alias one another. Thus, the term alias or aliasing refers to a situation in which memory access commands access memory regions that overlap each other. The presence of such aliasing limits the amount of reordering a compiler can safely perform.

The reason for this limitation on reordering is that reordering of instructions can result in memory access command400reading memory region404before memory access command402writes memory region406, when it was intended by the programmer that memory access command400would read the value written by memory access command402. In this event, the original program semantics would have been altered, thereby causing the program to produce unexpected results. In order to avoid this problem, compilers will not reorder dependent instructions.FIGS. 5-7demonstrate this concept with examples of code.

Note that the limitation regarding reordering of instructions that access the same memory regions applies to dependent store/load pairs of instructions and store/store pairs of instructions. Two load instructions referencing the same memory region can be freely interchanged, or reordered, if no intervening store instruction to that memory region exists.

Additionally, memory access commands are governed by aliasing rules. An aliasing rule defines how memory access commands can alias each other; that is, an aliasing rule specifies whether two memory access commands, as coded in the source program, are allowed to potentially access the same or overlapping memory locations. The aliasing rule restricts how the programmer may code the source program. Violation of such rules might lead to invalid, or non-conforming, programs. An implementation of this invention diagnoses occurrences of such potential violations.

The standard aliasing rule used by the C and C++ programming languages is the type-based aliasing rule. A type-based aliasing rule is not the only aliasing rule possible for a programming language. A compiler can always provide other aliasing rules, chosen, for example, by compiler options for the programmer to use. These other aliasing rules can be different than the type-based aliasing rule, or they can be more relaxed or more restrictive than the type-based aliasing rule. The illustrative embodiments described herein can be used on any aliasing rule. Using the illustrative embodiments described herein on the type-based aliasing rule is one implementation of an illustrative embodiment of this invention.

FIG. 5illustrates prior art C/C++ pseudo code having an indirect memory access. The C/C++ pseudo code shown inFIG. 5can be implemented using a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2. The C/C++ pseudo code shown inFIG. 5conforms to the standard “type-based aliasing rules” which are used by the compiler to define the alias set for the indirect memory access in the program.

As shown inFIG. 5, according to the type-based aliasing rule, the write to the variable “i” on line2aliases the write to pointer variable “*pi” on line4because the type of “pi” is “int*” and the type of “i” is “int”. In general, whether a program honors type-based aliasing rules of a programming language cannot be determined statically. Hence, the type-based aliasing rules are assumed by the compiler and guaranteed by the program author. A program that violates the type-based aliasing rules might be optimized, or reordered, in such a way as to cause an undesired change in program semantics after program optimization by the compiler.

FIG. 6illustrates prior art C/C++ pseudo code containing a potential alias violation under the standard type-based alias rule. The pseudo code shown inFIG. 6can be implemented using a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2.

The pseudo code shown inFIG. 6is written in a C or C++ programming language. The pseudo code shown inFIG. 6demonstrates an example of an aliasing violation through a type-cast. In particular, the assignment to variable “i” on line2does not alias the write command to pointer variable “*pf” on line4when the type-based aliasing rules of the C or C++ programming language are used. Nevertheless, an optimizing C or C++ compiler may choose to reorder these two write commands, leading to an unexpected value of “i” after line4.

In the past, one way compilers have dealt with such aliasing violations for C or C++ programs is to diagnose type-casts between incompatible pointer types, as on line3inFIG. 6. This approach is limited, as the type-cast is not the real problem. Although a type-cast is often a precursor to an illegal indirect memory reference (or dereference), a subsequent type-cast may ensure that the indirect memory access is aliased appropriately.

FIG. 7illustrates prior art C/C++ pseudo code containing type casts. The pseudo code shown inFIG. 7can be implemented using a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2.

The C/C++ pseudo code shown inFIG. 7illustrates that two consecutive type-casts may cause the indirect memory reference at line5to be aliased appropriately. The example ofFIG. 7illustrates the disadvantages of detecting aliasing rule violations by the presence of type-casts. In particular, diagnostic messages may be emitted when no alias violation has actually occurred. Additionally, the diagnostic emitted to report type-casts between incompatible pointer types may prove to be too verbose to be useful. Furthermore, the removal of type-casts may prove difficult, as the program design may be heavily dependent on use of the type-casts.

Note that type-casts are not inherently unsafe. Instead, a subsequent indirect memory reference (dereference) of the casted-to pointer makes a type-cast unsafe (that is when the standard type-based aliasing rule are used).

Aliasing violations often prove costly as sometimes the effect of the violation only appears at the highest optimization levels, or in time as code optimizers evolve to take advantage of previously unexploited code specialization or optimization opportunities. Thus, the problematic source code may have to be corrected when a more aggressive optimizing compiler is used to compile the problematic source code.

For example, a new compiler may be distributed to a customer, and the customer uses the new or more aggressive compiler to recompile the customer's existing source code, in the hope of exploiting the advanced capability of the compiler to generate a faster executable program. When the source code contains existing aliasing violations the recompiled program might not behave correctly; not because the compiler is faulty, but simply because the more aggressive optimizing compiler exposes an existing aliasing violation in the source code.

To correct the failure, the program may be recompiled using a less restrictive alias rule. For example, a compiler may provide an option that indicates all indirect memory accesses in a program alias one another. The use of such a relaxed aliasing rule, however, may severely impact the performance improvements a compiler can achieve. For this reason, correcting the aliasing violations in the program source is preferred, although this is often a difficult and time consuming task. Consequently, a technique for detecting violations of the preferred aliasing rules at compile time, such as the techniques disclosed in the illustrative embodiment herein, can save a tremendous amount of development time.

FIG. 8is exemplary output of a compiler program which traces back to source code a potential aliasing violation, in accordance with an illustrative embodiment. The exemplary output shown inFIG. 8can be generated by the algorithm shown inFIGS. 10-12, and in the examples shown inFIG. 13andFIG. 14. In particular, the exemplary output shown inFIG. 8can correspond to the output of the algorithms described herein, after application of the exemplary algorithms to the pseudo code shown inFIG. 6. Thus, the output shown inFIG. 8corresponds to an exemplary report which refers to the exact lines where an aliasing violation might appear in the original pseudo code before compilation has occurred.

The exemplary output shown inFIG. 8is powerful in that the exemplary output not only reports the line corresponding to the illegal dereference (indirect memory reference) at line4(under the type-based aliasing rules), but also reports the pointer assignment at line3. The exemplary output also reports line3because at line3the pointer variable “pf” assumes the address of variable “i”. In a complex source code, simply diagnosing the point of the dereference, which inFIG. 6is at line4, has limited usefulness given the complexity of the code. To correct the program, the programmer identifies where in the program a type-cast exists between incompatible pointer types. In other words, the programmer traces back the program execution until the type cast is found. In a complex program, this process can be onerous. However, in the illustrative example shown inFIG. 8, the report issued identifies the source location of all these assignments, rendering the task of correcting the faulty source code much easier.

Unlike the example shown inFIG. 6, a diagnostic for the valid C/C++ program shown inFIG. 7is not emitted because two type-casts are now used to avoid the aliasing violation. Thus, in large applications where the number of potentially dangerous type-casts can be large, the illustrative embodiments described herein reduce the verbosity of reports resulting from false positives. The false positives result from a diagnostic that simply reports assignments, through a type-cast, between incompatible pointer types.

The output shown inFIG. 8constitutes a trace back that traces potential aliasing violations back to the original source code. Additionally, the trace back provides the program symbols which the indirect memory access commands used in violating the aliasing rule. The trace back also provides a sequence of program statement locations to help the user understand how the aliasing violation arose, and to help the user determine how to eliminate the aliasing violation. In an illustrative example, the trace back provides a determination of how the aliasing violation arose.

Thus, the illustrative embodiments described herein provide for a compiler to detect and diagnose possible violations of the preferred aliasing rules in a computer program. More specifically, the illustrative embodiments described herein allow the compiler to generate a report identifying the locations, in source code, of the indirect memory access commands that violate the aliasing rules that apply to the program defined by the source code. The report also identifies the sequence of program statements leading to the incorrect memory access commands.

Current optimizing compilers use alias analysis to determine whether a program transformation can be safely carried out without changing the original program semantics. The set of transformations applied to the program depends on the aliasing rules to which the program adheres. The semantics of a conforming program are guaranteed to be preserved by the optimizer; however, no such guarantee is made for a non-conforming program.

The methods of the illustrative embodiments described herein are able to effectively diagnose non-conforming programs that do violate aliasing rules. The algorithms described herein allow the identification of the program statements in source code that may lead to an illegal indirect memory access.

FIG. 9is pseudo code illustrating a points-to primitive in a C or C++ programming language in accordance with an illustrative embodiment. The pseudo code shown inFIG. 9can be implemented using a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2.

The pseudo code shown inFIG. 9shows that, in the C or C++ programming languages, points-to primitives are created from address-of operations. In the example shown inFIG. 9, the pointer assignment generates the points-to primitive (pi, ic) where “c” is the coordinate of the assignment in the program source code. Points-to primitives, such as the one generated with respect toFIG. 9, are used by the exemplary embodiments inFIGS. 11-14when performing points-to analysis. The illustrative embodiments herein make use of a directed graph to represent the result of the points-to analysis.

A directed graph is a graph G={V, E} where: V is the set of graph vertices and E is the set of graph edges. Given an edge e in E connecting the pair (v1, v2) of vertices in V, e is considered directed from v1to v2. The vertex v1is the source vertex while the vertex v2is the destination vertex.

In an illustrative method of the embodiments described herein, the process begins as the compiler receives source code. The compiler then performs syntactic and semantic analysis. During semantic analysis, assignments involving memory access commands are collected and a set of points-to primitives is identified. An example of a points-to primitive can be seen inFIG. 9.

The compiler infers the aliasing rules that apply to the program by reading a command line option or parsing a user directive in the program source code. The compiler then parses the program source code to an internal representation and performs semantic analysis on the program statements.

The compiler also annotates a directed graph with coordinate information. Coordinate information gives the location in the source code of relevant program statements. In an illustrative embodiment, coordinate information includes a file name of the source code and line and column number of the source code. During this step, the rules for annotating a points-to graph are created. Next, the compiler propagates coordinate information in the directed graph across the graph edges.

FIG. 10is a flowchart of an algorithm for detecting and reporting possible violations of aliasing rules in source code, in accordance with an illustrative embodiment. The process shown inFIG. 10can be implemented in a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2. In particular, the process shown inFIG. 11can be implemented using a compiler, such as compiler302shown inFIG. 3.

The process begins as the compiler identifies a set of indirect memory references in the source code (step1000). The compiler also generates points-to records for the source code (step1002). The compiler validates the set of indirect memory references using the points-to records and the aliasing rule in effect to determine if a potential aliasing problem exits. The compiler also identifies a first indirect memory reference having this potential aliasing problem, where the first indirect memory reference is in the set of indirect memory references (step1004). The compiler generates a report identifying the location within the source code associated with the first indirect memory reference (step1006). The compiler causes the report to be stored in a memory of a data processing system (step1008). The process terminates thereafter.

FIG. 11is a flowchart illustrating a process of facilitating debugging of source code in accordance with an illustrative embodiment. The process shown inFIG. 11can be implemented in a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2. The process shown inFIG. 11can be implemented using a compiler, such as compiler302shown inFIG. 3.

The process begins as the compiler receives program source code (step1100) and performs syntactic and semantic analysis (step1102). The compiler then computes points-to primitives and indirect memory references (step1104).

The compiler then constructs a directed graph (step1106). The compiler propagates points-to information and coordinate information in the directed graph through edges (step1108). The compiler then receives aliasing rules (step1110).

The compiler identifies potential alias violations (step1112) and generates a report with trace back information (step1114). Finally, the compiler stores the report in a memory (step1116), and the process terminates thereafter.

FIG. 12is a flowchart illustrating a process for facilitating debugging of code in accordance with an illustrative embodiment. The process shown inFIG. 12can be implemented in a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2. The process shown inFIG. 12can be implemented using a compiler, such as compiler302shown inFIG. 3.

The process begins as the compiler performs alias analysis on source code to generate points-to records having points-to information (step1200). The compiler then constructs a directed graph based on the points-to records (step1202). The compiler propagates coordinate information in the directed graph to corresponding call edges of the directed graph (step1204). The compiler also propagates the points-to information to corresponding ones of the call edges associated with the points-to information (step1206).

The compiler then identifies, using the directed graph, zero or more lines of code containing a potential aliasing violation (step1208). That is, the compiler may not identify any lines of code containing a potential aliasing violation, or it may identify at least one line of code containing a potential aliasing violation. It will be appreciated that where the compiler identifies at least one line of code containing a potential aliasing violation, the at least one line of code is in the source code. The complier then generates a report comprising trace back information, wherein the trace back information comprises a location of the at least one line of code (step1210). Finally, the compiler stores the report in a memory (step1212).

FIG. 13shows directed graph1300, which is based off of pseudo code1302. In particular, directed graph1300can be constructed from pseudo code1302to evaluate the points-to set in pseudo code1302. Directed graph1300can be implemented using a data processing system, such as data processing system100shown inFIG. 1or data processing system200shown inFIG. 2.

The directed graph ofFIG. 13shows a number of vertices, such as vertex1304. A vertex can represent a direct memory reference, for example vertices “pp,”1304“qq,”1306“r,”1308“q,”1310and “p”1312are direct vertices. Similarly, a vertex can represent an indirect memory reference, such as vertices “*pp”1314and “*qq”1316. An indirect vertex represents the memory region obtained by dereferencing another vertex in directed graph1300.

Each vertex shown inFIG. 13contains a square box representing the points-to set for the corresponding vertex shown by a box with rounded corners. For example, vertex “pp”1304in the shown rounded box contains points-to set1318in the shown square box. In turn, points-to set1318contains points-to entry “pc3”1320. Each points-to entry is annotated with a sequence of source coordinates describing program locations in source code1302. Thus, points-to entry “pc3”1320shows a sequence of source coordinates that reference line8in pseudo code1302, which corresponds to coordinate c3. Other points-to entries have references which refer to different, or the same, coordinates. Points-to entries with multiple subscripts refer to multiple coordinates and thus multiple lines in pseudo code1302.

As shown inFIG. 13, a points-to set can contain more than one points-to entry. For example, points-to set1330of vertex “*pp”1314contains points-to entries “ic6”1334, ic1c5c3”1336, and “kc2c5c3”1338, which all refer to corresponding lines in pseudo code1302. For example, points-to entry “kc2c5c3”1338refers to lines7,8, and10in pseudo code1302.

Edges in directed graph1300represent assignments between vertices. An edge in directed graph1300may be a directed edge. With respect toFIG. 13, the line1340connecting vertex “*pp”1314to vertex “r”1308is a directed edge. The directed edge1340connects two vertices, with the source vertex being vertex “*pp”1314and the destination vertex being vertex “r”1308. Edges are annotated with the name of the two vertices the edges connect. Thus, for example, directed edge1340is designated as (e*pp,r). Edges in directed graph1300also have a sequence of associated source coordinates. In directed graph1300, edges are annotated with the coordinates corresponding to their associated program statements.

Edges in directed graph1300can be real or implicit. For example, edge1340“e*pp,r” connecting vertex “*pp”1314to vertex “r”1308is a real edge. In contrast, edge1342“e*pp,t” connecting vertex “*pp”1314and vertex “p”1312is an implicit edge.

Generally, for each points-to primitive (r, pc) in source code1302there exists a graph vertex “vr” corresponding to reference “r” with “pc” in the points-to set of graph vertex “vr”. The points-to set entry “pc” is annotated with coordinate “c.” For example, line6in pseudo code1302causes “ic1” to be added to the points-to set of vertex “q”1310.

For each assignment x=y with source coordinates “c” in source code1302, where x and y are memory regions, there exists a real edge ey,xfrom vertex “vy” to the vertex “vx” with coordinates “c,” where “vx” and “vy” correspond to memory regions “x” and “y” respectively. For example, line10in pseudo code1302causes the edge1344eq,pto be added to directed graph1300and to be annotated with coordinate “c5.” Edge1344eq,pcorresponds to the edge between vertex “q”1310and vertex “p”1312.

Additionally, if memory region “x” or “y” is accessed via an indirect memory reference “*r,” there exists an indirect vertex in graph1300corresponding to indirect reference “*r.” For example, line11in pseudo code1302causes indirect vertex “*pp”1314corresponding to vertex pp1304to be added to directed graph1300.

Implicit edges can be identified as follows: Let vertex “*r” be the indirect vertex corresponding to vertex “r.” For any entry “p” in the points-to set of “r,” there exists implicit edges e*r,pand ep,*rin the graph with sequence coordinates of the points-to entry “p.” For example, line13of pseudo code1302causes edge1346e*qq,q, eq,*qqto be added to directed graph1300, because vertex “*qq”1310contains “q” in points-to set1322.

An example of propagating coordinates information in directed graph1300is now given. Propagating coordinates information in directed graph1300corresponds to step1204inFIG. 12.

Directed graph1300has now been annotated with the source coordinate information as described above. For all paths “P” from any vertex “v1” in directed graph1300to any other vertex “v2” in directed graph1300, the following actions are taken. If path “P” does not traverse two consecutive implicit edges, then the points-to set of “v2” is augmented with the points-to set of “v1” by propagating the entries in the points-to set of “v1” across the edges connecting “v1” to “v2.” Additionally, a points-to entry is propagated from source vertex “vs” to destination vertex “vd” across the connecting edge “es,d” by appending the edge source coordinate sequence to the new points-to entry added to the destination vertex “vd” points-to set.

As described above, edges are annotated with the coordinates of the program statement or statements that cause the edges to be added to directed graph1300. Therefore, annotating a points-to entry with a coordinate sequence allows recording, in the entry itself, of the path taken to reach a destination vertex from a source vertex. An analysis of the points-to set of any vertex can then be used to determine the program statements responsible for the presence of an entry in the vertices points-to set.

As an example, points-to entry “ic1”1348in the points-to set of vertex “q”1310is propagated to the points-to set of vertex “p”1312by traversing edge1344connecting the two vertices. Because edge1344is annotated with coordinate “c5,” the entry added to points-to set1328of vertex “p”1312is annotated with both the original coordinate “c1” and the edge coordinate “c5.” By analyzing points-to entry “ic1c5”1350of vertex “p,”1312an inference can be made that “p” may point to “i,” because of the program statements having coordinates “c1” and “c5.”

The identification of possible aliasing rule violations is now described with respect toFIG. 13. In this example, “Av” is defined as the initially empty set of all possible aliasing violations in pseudo code1302. Thus, “Av” can be referred to as the violation set. For all vertices “vr” in directed graph1300the following actions are taken. Let “p” be an entry in the points-to set of “vr.” If, according to the aliasing rules in effect, the memory region described by “p” is not aliased to the memory region represented by the indirect vertex “*vr” corresponding to vertex “vr,” then add the pair (vr, p) to Av.

Additionally, let “L” be the set of indirect memory accesses in pseudo code1302. The set “L” represents the actual indirect memory references in pseudo code1302. For all elements of “*r” of “L,” the following action is taken. Let “vr” be a vertex in directed graph1300corresponding to indirect memory access “*r.” For each pair, (vr, P) in the violation set “Av,” perform the following actions. First, report the illegal dereference “*r.” Second, report the aliasing rule that dereference “*r” violates. Third, let [C] be the coordinate sequence with which “p” is annotated. For each coordinate “c” in [C] emit “c” in the report.

The sequence of source coordinates reported in the diagnostic may be emitted in different order then they appear in [C]. The sequence of source coordinates for the diagnostic may be emitted from any path by which the points-to primitive entry p is propagated to the vertex.

The algorithm described above first collects all possible aliasing violations in the violation set “Av.” The algorithm then checks whether an actual dereference in pseudo code1302appears in the violation set “Av.” If the violation set “Av” contains the vertex “vr” corresponding to the indirect memory access “*r,” the algorithm diagnoses the illegal memory access by emitting the trace back information from the coordinates sequence recorded in element “vr.”

As an example, consider the dereference “*qq” at line13in pseudo code1302. The vertex corresponding to the dereference is vertex “q”1310because “qq” contains “q” in its points-to set. The points-to set for vertex “q”1310contains points-to entries “ic1,”1348, “kc2,”1352and “jc6c7c8c4”1354.

Points-to entry “jc6c7c8c4”1354is considered first. By checking the alias rules in effect, a determination can be made that “*q,” which has type “int,” is not aliased to “j,” which has type “double” (assuming the aliasing rule in effect does not allow an expression of type “double” to alias an expression of type “mint”). At this point in the algorithm, a diagnostic message is reported indicating that the indirect memory access “*qq” at line13of pseudo code1302is illegal. In the resulting report, statements at coordinates c4, c6, c7, and c8are listed in the trace back.

When directed graph1300is initially constructed, the initial points-to sets do not include points-to entries. The points-to sets are initially populated by analyzing the source statements generating points-to primitives in pseudo code1302, such as statements at lines6,7,8,9, and11. Then, the propagation of points-to sets through edges adds points-to entries to the points-to sets of each corresponding vertex.

Each points-to entry in each vertex has corresponding trace back information. Note that vertex “r”1308, vertex “q”1310, vertex “p”1312, vertex “*pp”1314, and vertex “*qq”1316, each contain a point-to entry associated with “j.” Points-to entry “j” collects trace back information as the points-to entry is propagated from vertex “*pp”1314(where it is initially added) through vertex “r”1308, vertex “*qq”1316, and vertex “q”1310. Thus, in vertex “*qq”1316, the points-to entry “j” has trace back information including coordinates c6-c7-c8. Therefore, the trace back information for “j” refers to lines11,12, and13in pseudo code1302. This trace back information can be reported to a user in order to assist the user to find the possible aliasing violation in pseudo code1302. An exemplary report based on this trace back information can be presented in a format similar to the report shown inFIG. 8.

The algorithm described above can be described with respect to the following process. First, syntactic and semantic analysis is performed. Then, in annotating directed graph1300with coordinate information, the following actions are taken to populate directed graph1300with the initial points-to set.

The initial points-to entries in the points-to sets include “ic1”1348in vertex “q”1310, “jc6”1334in vertex “*pp”1314, “kc2”1352in vertex “q”1310, “pc3”1320in vertex “pp”1304, and “qc4”1356in vertex “qq”1306. These initial points-to entries are generated as follows. From line6in pseudo code1302, “i” is added with coordinate c1to points-to set of vertex “q”1310. For line7in pseudo code1302, “k” is added with coordinate c2to the points-to set of vertex “q”1310. For line8of pseudo code1302, “p” is added with coordinate c3to the points-to set of vertex pp1304. For line9of pseudo code1302, “q” is added with coordinate c4to the points-to set of vertex qq1306. For line11of pseudo code1302, “j” is added with coordinate c6to points-to set1330of vertex “*pp”1314. This completes the initial set of points-to entries. Then, edges are added as follows. For line10of pseudo code1302, real edge1344is added with coordinate c5from vertex “q”1310to vertex “p”1312. For line12of pseudo code1302, real edge1340is added with coordinate c7from vertex “*pp”1314to vertex “r”1308. For line13of pseudo code1302, real edge1358is added with coordinate c8from vertex “r”1308to vertex “*qq”1316.

An implicit edge is added between vertex “*pp”1314and any entry in points-to set1318of vertex “pp”1304. Thus, implicit bidirectional edge1342is created between vertex “*pp”1314and vertex “p”1312with coordinate c3.

Similarly, an implicit edge is added between vertex “*qq”1316and entries in points-to set1322of vertex “qq”1306. Implicit bidirectional edge1346between vertex “*qq”1316and vertex “q”1310is created with coordinate c4. With respect to line15of pseudo code1302, dereference “**qq” is stored in the set “L” of indirect memory access.

Next, the coordinate information is propagated. Propagation of points-to sets through edges adds points-to entries to the points-to sets of each vertex in directed graph1300. In particular, points-to entries “ic1c5c3”1336and “kc2c5c3”1338are added to points-to set1330in vertex “*pp”1314; points-to entries “jc6c7”1360, “ic1c5c3c7”1362, and “kc2c5c3c7”1364are added to points-to set1324in vertex “r”1308; points-to entries “jc6c7c8”1366, “ic1c5c3c7c8”1368, and “kc1c5c3c7c8”1370are added to points-to set1332in vertex “*qq”1316; points-to entry “jc6c7c8c4”1354is added to points-to set1326in vertex “q”1310; and points-to entries “ic1c5”1350, “kc2c5”1372, and “jc6c3”1374are added to points-to set1328of vertex “p”1312.

Each points-to entry in each vertex has its own trace back information. For example, points-to reference “j” collects trace back information as points-to entry “j” is propagated from vertex “*pp”1314through vertex “r”1308, vertex “*qq”1316and vertex “q”1310. For example, in vertex “*qq”1316the points-to entry “j” has trace back information c6-c7-c8. This trace-back information refers back to coordinates c6, c7, and c8, which in turn refer to lines11,12, and13in pseudo code1302.

Although not shown inFIG. 13for simplicity, points-to entry “j” could be further propagated from vertex “q”1310to vertex “p”1312which would result in points-to entry “j” in vertex “p”1312having trace back information c6-c7-c8-c4-c5. This would be in addition to the separate points-to entry “j”1374in vertex “p”1312having trace back information c6-c3resulting from propagation from vertex “*pp”1314along virtual edge c31342to vertex “p”1312.

Next, the illustrative algorithm described herein detects and reports violations. After all points-to sets are propagated, the indirect dereference “**qq” from the set “L” of indirect memory accesses is processed by adding vertex “*qq”1316to the violation set “Av.” The violation set “Av” contains [(*qq, jc6c7c8), (*qq, ic1c5c3c7c8), (*qq, kc1c5c3c7c8)] because the entries in points-to set1316of *qq (i, j, k) of type “double” do not alias the type “int” of the indirect access “**qq.” Thus, indirect access command **qq in line15of pseudo code1302is an aliasing violation, under the determined aliasing rules. The aliasing violation is presented to the user in the form of a report.

The report can take the form of the output shown inFIG. 8. The report can also include trace back information that allows a user to relatively easily identify line15in pseudo code1302as the source of the aliasing violation. In this way, a user can correct the aliasing violation in the source code1302and then recompile source code1302using an optimizing compiler, after having eliminated the aliasing violation.

FIG. 14shows a directed graph and associated C/C++ pseudo code, in accordance with an illustrative embodiment. The illustrative example shown inFIG. 14also can be used to illustrate detecting and reporting of violations of alias rules, such as described inFIG. 12. Directed graph1400shown inFIG. 14can be implemented in a data processing system, such as data processing system100shown inFIG. 1and data processing system200shown inFIG. 2. Directed graph1400is similar to, but different than directed graph1300ofFIG. 13. As with directed graph1300, directed graph1400is obtained by propagating the source coordinates, as described above.

The example inFIG. 14is described with respect to the exemplary algorithms described herein. First, syntactic and semantic analysis is performed, points-to primitives and dereferences are computed, and a directed graph is constructed by annotating the directed graph with coordinate information. During these steps directed graph1400is populated with an initial points-to set.

An implicit bidirectional edge is added between vertex “*pppi”1444and any entry in points-to set1442of vertex “pppi”1442. Thus, implicit bidirectional edge1446exists between vertex “*pppi”1444and vertex “ppi”1428with coordinate c11. Additionally, implicit bidirectional edge1448is added between vertex “*pppi”1444and vertex “ppz”1434with coordinate c12.

Next in directed graph1400, the coordinate information is propagated. Propagation of points-to sets through edges adds certain points-to entries and coordinates. Specifically, points-to entries “pic8c11”1454, “pjc9c11”1456, and “pzc10c12”1458are added to points-to set1452of vertex “*pppi”1444.

Each points-to entry in each vertex has its own trace back information. Note how point-to entry “pic8”1422collects trace back information as it is propagated from vertex “ppi”1428through implicit bidirectional edge1446to vertex “*pppi”1444. For example, in vertex “*pppi”1444, the points-to entry “pic8c11”1454has trace back coordinates c8-c11. These trace back coordinates refer back to lines8and11of pseudo code1402.

After propagating “ic5” from vertex “pi”1408to vertex “**pppi”1450through implicit edge1460, points-to entry “ic5” cannot be propagated consecutively through some other implicit edge. For example, points-to entry “ic5”1404in vertex “pi”1408cannot move to vertex “**pppi”1405and then to vertex “pj”1414because points-to entry “ic5”1404would be violating a rule regarding propagation through two consecutive implicit edges. Thus, vertex “pj”1414cannot point to points-to entry “ic5”1404.

In the next step, aliasing violations are detected and reported. After all points-to sets are propagated, the indirect references ***pppi, **pppi and *pppi are processed from the set “L” of indirect memory accesses by adding ***pppi, **pppi, and *pppi to the violation set “Av.” The violation set Av contains [(*pppi, ppzc12), (*pppi, ppic11), (**pppi, pic8c11), (**pppi, pjc9c11), (**pppi, pzc10c12) (***pppi, ic5c8c11), (***pppi, zc7c10c12), (***pppi, jc6c9c11)].

Thus, points-to entry “ppzc12”1438of type “double**” in points-to set1440of vertex “pppi”1442does not alias the type “int**” of the indirect access *pppi. For this reason, trace back c12is emitted to the report, assuming that according to the current alias rules “int**” does not alias “double**”.

Additionally, points-to entry “pzc10c12”1458of type “double*” in points-to set1452of vertex “*pppi”1444does not alias the type “int*” of the indirect access **pppi. Thus, the trace back c10c12is emitted in the resulting report, assuming that according to the current alias rules “int*” does not alias “double*”.

Additionally, points-to entry “zc7c10c12”1470of type “double” in points-to set1472of vertex “**pppi”1450does not alias the type “int” of the indirect access ***pppi. Therefore, trace back c7c10c12is emitted in the resulting report, assuming that according to the current alias rules “int” does not alias “double”.

Finally, points-to entry “jc6c9c11”1468of type “float” in points-to set1472of vertex “**pppi”1450does not alias the type “int” of the indirect access ***pppi. Thus, trace back c6c9cllis emitted in the resulting report, assuming that according to the current alias rules “int” does not alias “float”.

The illustrative embodiments described herein allow detection of type-based aliasing rules at compile time. Furthermore, the illustrative embodiments described herein allow a trace back to be determined at compile time. The trace back identifies particular lines in the source code that may contain aliasing violations. A user can then correct the aliasing violations in the original source code and then recompile the source code using the optimizing compiler. Thus, the optimizing compiler can maximize the efficiency of the resulting executable code.

The invention can take the form of an entirely software embodiment or an embodiment containing both hardware and software elements. In a preferred embodiment, the invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

Further, a computer storage medium may contain or store a computer readable program code such that when the computer readable program code is executed on a computer, the execution of this computer readable program code causes the computer to transmit another computer readable program code over a communications link. This communications link may use a medium that is, for example without limitation, physical or wireless.