Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-01-06
2002-04-09
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06370685
ABSTRACT:
RELATED APPLICATIONS
[Not Applicable]
FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
[Not Applicable]
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
MICROFICHE APPENDIX
A microfiche appendix of the presently preferred computer program source code is included and comprises 1 sheets and a total of 91 frames.
The Microfiche Appendix is hereby expressly incorporated herein by reference, and contains material which is subject to copyright protection as set forth above.
FIELD OF INVENTION
The present invention generally relates to software compiler technology. More particularly, the present invention relates to a method for computing definition-use information for lvalues that may be aggregates and/or referenced through pointer expressions.
BACKGROUND OF THE INVENTION
Within the field of compilers, the problem of determining which definitions reach uses in a program is important to many optimizations. For the case where the left sides of definitions are scalars, the problem is well understood. One prior-art technique generalizes the analysis to definitions whose left sides are aggregates and/or pointer expressions. The generalization to aggregates is based on partitioning an aggregate into components, and tracking each component separately. The generalization to lvalues referenced through pointer expressions is based on using two data-flow solvers. A bottom level solver tracks whether a pointer expression to the lvalue changes between the point of definition and point of use, and a top level solver employs said information about said changes to determine where the lvalues reach.
This prior art technique has a number of disadvantages.
(a) It requires two data-flow solvers, which can be expensive in time and memory storage requirements. Particularly expensive in terms of space is the requirement that the results of the bottom analyzer be retained while the top analyzer runs.
(b) It requires up to 9 bits of data-flow solution per definition in the data-flow problems solved. Specifically, the bottom-level solver operates on a lattice of 3-bit vectors, and requires two such vectors for each definition analyzed, one for the address of the defined lvalue, and one for the support of the right side. Thus the bottom-level solver requires up to 6 bits per definition to represent a lattice value. The top-level solver requires yet another 3-bit vector value for each partitioned piece of the lvalue defined by the definition. Furthermore, for each bit in any said vector, there are three possible monotone lattice functions, thus two bits are required to represent each lattice function on a bit. Consequently, for a definition partitioned into n pieces, the solvers need 6+3n bits and 12+6n bits respectively to represent the lattice values and functions related to a single definition.
(c) It fails to find some opportunities for forward substitution, because the bottom solver sometimes reports changes in right sides of definitions that were actually irrelevant because the corresponding definition is no longer live along the paths for which the change occurred. FIG.
1
A and
FIG. 1B
show such an example. Definitions
100
and
101
both reach the use
102
of p in “q=p”. Both have the form “p=x[j]”. The support of x[j] is the set of lvalues {x,j}. If the statement
103
“j=j+1” is executed, then the support of the right side of definition
100
will have changed between its point of definition and the statement “q=p”. The prior art interprets the change as preventing forward substitution. However, along paths including “j=j+1”, definition
100
is dead, and thus would be correct to forward substitute x[j] for p in “q=p”.
(d) It fails to find some opportunities for removing dead stores or scalar replacement, because the bottom solver sometimes reports changes to the support of left sides of definitions that were actually irrelevant because the corresponding definition is no longer live along the paths for which the change occurred. The problem is similar in flavor to said problem with right sides, though the consequent inferiority is different. FIG.
2
A and
FIG. 2B
show such an example. Definition
200
is never used, because it is killed by either definition
201
or
202
, depending upon the path taken. The support of the left side of definition
200
includes k, and along paths through definition
201
, the value of k changes
203
. Unfortunately, when the top-level solver of said prior art inspects definition
202
to check whether it kills definition
200
, the bottom-level solver reports that k changed along some paths and consequently the top-level solver must assume that definition
202
does not kill definition
200
.
BRIEF SUMMARY OF THE INVENTION
Accordingly, the present invention provides a method and apparatus that analyzes definitions and uses of lvalues in a program. For each definition in the program, the method computes where the definition reaches, and whether the support of the definition's left side has changed while the definition is live. The method according to the present invention can also be implemented by computing where each use reaches backwards within a program, and whether the support of the use changes while the use is live. The present invention also demonstrates a novel way of representing lattice elements with binary codes. The lattice is embedded in a boolean hypercube, and binary codes are assigned corresponding to the hypercube coordinates. The codes are then compacted by removing some bit positions and duplicate codes removed by complementing a few bits in some of the codes.
REFERENCES:
patent: 4843545 (1989-06-01), Kikuchi
patent: 5355494 (1994-10-01), Sistare et al.
patent: 5396627 (1995-03-01), Iitsuka
patent: 5448737 (1995-09-01), Burke et al.
patent: 5481708 (1996-01-01), Kukol
DeFouw et al., “Fast interprocedural class analysis”, POPL 98, ACM, 1998, pp 222-236.
Blakely , Sokoloff, Taylor & Zafman LLP
Chaki Kakali
Intel Corporation
LandOfFree
Data-flow method of analyzing definitions and uses of L... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data-flow method of analyzing definitions and uses of L..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data-flow method of analyzing definitions and uses of L... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2933372