§
Luxuse
Patent Intelligence
Sign In
← Back to Patent Explorer
US5790866A Expired / Lapsed US ⏱️ 0.0 years remaining

Method of analyzing definitions and uses in programs with pointers and aggregates in an optimizing compiler

Assignee: Intel Corp
•
Filing: 1995-02-13
•
Granted: 1998-08-04
•
Expires: 2015-02-13
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

Abstract A method for analyzing and optimizing programs that contain pointers and/or aggregates, such as found in the languages C, C++, FORTRAN-90, and Ada. The method applies to storage locations (lvalues) and values (rvalues) computed by expressions. Data-flow analysis is performed on two levels. The bottom level determines when an rvalue computed at one point in a program is the same if recomputed at a later point in the program. The top level computes reaching definitions, based upon information provided by the bottom level. Each destination lvalue may be designated by an arbitrary rvalue (pointer-expression). Splitting of data-flow analysis into two levels allows computation of reaching definitions that involve assignments to lvalues with designating rvalues that are arbitrary expressions. Furthermore, for aggregate lvalues, which themselves may contain components that are pointers to other aggregates, data-flow analysis is done on a component-by-component basis. Data-flow analysis is then used to forward-substitute definitions and remove "dead" assignments.

Inventors

  • 👤 Arch D. Robison

Bibliographic Details

Application Number —
Jurisdiction US
Data Source google_patents
Last Synchronized 2026-11-05 11:32
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/43; G06F8/433; G06F8/434; G06F8/4434; G06F8/4435

Claims Analysis

Total Claims: 14
Claim 1
Independent Claim 65 words
A method for analyzing definitions and uses in a compiler including a two-level analyzer having both top and bottom analyzer levels, comprising the steps of: analyzing a support of an lvalue to generate a solution to an is same problem with the bottom level analyzer; and using the solution generated by the bottom-level analyzer to solve a definition reaches problem with the top level analyzer.
Claim 2
Independent Claim 65 words
A method for analyzing definitions and uses in a compiler including a two-level analyzer having both top and bottom analyzer levels, comprising the steps of: analyzing a support of an lvalue to generate a solution to an is same problem with the bottom level analyzer; and using the solution generated by the bottom-level analyzer to solve a definition reaches problem with the top level analyzer.
Claim 3
Dependent Claim 11 words
The method defined in claim 1, wherein the lvalues comprise aggregates.
Claim 4
Dependent Claim 31 words
The method defined in claim 2, further comprising the step of providing for component-wise analysis of definitions that subdivides the aggregates into the smallest component referenced, not the smallest component possible.
Claim 5
Dependent Claim 22 words
The method of claim 2 wherein the aggregates comprise at least one component and the at least one component is analyzed separately.
Claim 6
Dependent Claim 14 words
The method defined in claim 1, wherein the lvalues are referenced by pointer expressions.
Claim 7
Dependent Claim 28 words
The method defined in claim 1, further comprising the step of identifying unused assignments to lvalues and reporting to the programmer the nature and location of these conditions.
Claim 8
Dependent Claim 18 words
The method defined in claim 1, further comprising the step of forward-substituting definitions that have lvalued left-hand sides.
Claim 9
Dependent Claim 19 words
The method defined in claim 1, further comprising the step of removing unused definitions that have lvalued left-hand sides.
Claim 10
Dependent Claim 17 words
The method defined in claim 1, further comprising the step of hoisting invariant expressions out of loops.
Claim 11
Dependent Claim 23 words
The method defined in claim 1, further comprising the step of exploiting a single flow-analysis pass for both removing unused assignments and forward-substitution.
Claim 12
Dependent Claim 28 words
The method defined in claim 1, further comprising the step of constructing definition-use information that allows some assumed dependencies to be ignored, without constructing a complete dependence graph.
Claim 13
Dependent Claim 30 words
The method defined in claim 1, further comprising the step of identifying invariant values within loops that allows some assumed dependencies to be ignored, without constructing a complete dependence graph.
Claim 14
Dependent Claim 35 words
The method defined in claim 1, further comprising the step of providing for forward-substitution of multiple definitions that reach a single use of an lvalue, when all of the reaching definitions have matching right-hand sides.

References Cited (Backward Citations)

US4843545A Cited
US5355494A Cited
US5448737A Cited

USPTO Annuity & Maintenance Windows

Annuity Stage Window Opens Payment Deadline Surcharge Period Until Estimated Fee Status
3.5 Years (Year 4) 2001-08-03 2002-02-02 2002-08-04 $2000.00 Window Closed / Lapsed
7.5 Years (Year 8) 2005-08-03 2006-02-02 2006-08-04 $3760.00 Window Closed / Lapsed
11.5 Years (Year 12) 2009-08-03 2010-02-02 2010-08-04 $7700.00 Window Closed / Lapsed

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag