US5896537A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Partition based alias analyzer for pointers
Assignee: Siemens Corp
•
Filing: 1996-05-13
•
Granted: 1999-04-20
•
Expires: 2016-05-13
Abstract
Abstract An apparatus that provides for the safe and efficient alias analysis for programs written in programming languages which use pointers combines a representation generator with a partitioned based alias analyzer and provides safe alias solutions using partitions to consumers of alias solutions. The source code of the program to be analyzed enters a parser of the representation generator and an abstract syntax tree representation of the syntactic structure of the source program is derived Next, a control flow graph (CFG) builder within the representation generator derives the program's control flow graph for the abstract syntax tree. The control flow graph is then used by the partition based alias analyzer which is divided into three phases; phase one--type one alias effects, phase two--type two alias effects and phase three--function pointer effects, to produce safe alias solutions using partitions.
Inventors
- 👤 William A. Landi
- 👤 Rita Z. Altucher
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 16:14
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/43; G06F8/433; G06F8/434
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
53 words
A system for providing a partition based alias analysis comprising: representation generator means for receiving a source program; and, partitioned based alias analyzer means connected to said representation generator means for providing safe alias solutions using partitions; wherein order of statements in said source program does not affect said partition based alias analysis.
Claim 2
Independent Claim
53 words
A system for providing a partition based alias analysis comprising: representation generator means for receiving a source program; and, partitioned based alias analyzer means connected to said representation generator means for providing safe alias solutions using partitions; wherein order of statements in said source program does not affect said partition based alias analysis.
Claim 3
Dependent Claim
24 words
A system for providing a partition based alias analysis as claimed in claim 1 wherein union/find data structures are used to represent alias solutions.
Claim 4
Independent Claim
56 words
A system for providing a partition based alias analysis comprising: representation generator means for receiving a source program; and, partitioned based alias analyzer means connected to said representation generator means for providing safe alias solutions using partitions; wherein there is a restriction of explicitly finding aliases only for names that are physically in said source program.
Claim 5
Independent Claim
56 words
A system for providing a partition based alias analysis comprising: representation generator means for receiving a source program; and, partitioned based alias analyzer means connected to said representation generator means for providing safe alias solutions using partitions; wherein there is a restriction of explicitly finding aliases only for names that are physically in said source program.
Claim 6
Dependent Claim
31 words
A system for providing a partition based alias analysis as claimed in claim 1 wherein accounting for function pointer resolution is a separate phase of said partitioned based alias analyzer means.
Claim 7
Dependent Claim
61 words
A system for providing a partition based alias analysis as claimed in claim 1 wherein said representation generator means comprises: parser means for receiving a source program to be analyzed and for providing an abstract syntax tree; and, control flow graph builder means connected to said parser means for receiving said abstract syntax tree and for providing a control flow graph.
Claim 8
Dependent Claim
37 words
A system for providing a partition based alias analysis as claimed in claim 1 wherein said partition based alias analyzer means comprises: phase one--type one alias effects; phase two--type two alias effects; and, phase three--function pointer effects.
Claim 9
Dependent Claim
34 words
A system for providing a partition based alias analysis as claimed in claim 6 wherein said phase one--type one alias effects accounts for unions needed because of type one alias effects of all assignments.
Claim 10
Dependent Claim
34 words
A system for providing a partition based alias analysis as claimed in claim 6 wherein said phase two--type two alias effects accounts for unions needed because of type two alias effects of all assignments.
Claim 11
Dependent Claim
40 words
A system for providing a partition based alias analysis as claimed in claim 6 wherein said phase three--function pointer effects accounts for unions needed to ensure that actuals for function pointer call sites are unioned with formals of called procedure.
Claim 12
Dependent Claim
89 words
A system for providing a partition based alias analysis as claimed in claim 1 wherein said partitioned based alias analyzer means comprises: phase one--type one alias effects for receiving said control flow graph and for providing initial partitions; phase two--type two alias effects for receiving said control flow graph and said initial partitions and for providing alias partitions without function pointers effects; and, phase three--function pointer effects for receiving said control flow graph and said alias partitions without function pointers effects and for providing safe alias solutions using partitions.
Claim 13
Independent Claim
117 words
A system for providing a partition based alias analysis comprising: parser means for receiving a source program to be analyzed and for providing an abstract syntax tree; control flow graph builder means connected to said parser means for receiving said abstract syntax tree and for providing a control flow graph; phase one--type one alias effects for receiving said control flow graph and for providing initial partitions; phase two--type two alias effects for receiving said control flow graph and said initial partitions and for providing alias partitions without function pointers effects; and, phase three--function pointer effects for receiving said control flow graph and said alias partitions without function pointers effects and for providing safe alias solutions using partitions.
Claim 14
Independent Claim
117 words
A system for providing a partition based alias analysis comprising: parser means for receiving a source program to be analyzed and for providing an abstract syntax tree; control flow graph builder means connected to said parser means for receiving said abstract syntax tree and for providing a control flow graph; phase one--type one alias effects for receiving said control flow graph and for providing initial partitions; phase two--type two alias effects for receiving said control flow graph and said initial partitions and for providing alias partitions without function pointers effects; and, phase three--function pointer effects for receiving said control flow graph and said alias partitions without function pointers effects and for providing safe alias solutions using partitions.
Claim 15
Independent Claim
49 words
A method of performing partition based alias analysis comprising the steps of: obtaining a control flow graph from a source program; and, obtaining safe alias solutions using partitions from said control flow graph; wherein order of statements in said source program does not affect said partition based alias analysis.
Claim 16
Independent Claim
49 words
A method of performing partition based alias analysis comprising the steps of: obtaining a control flow graph from a source program; and, obtaining safe alias solutions using partitions from said control flow graph; wherein order of statements in said source program does not affect said partition based alias analysis.
Claim 17
Independent Claim
74 words
A method of performing partition based alias analysis comprising the steps of: obtaining a control flow graph from a source program; and, obtaining safe alias solutions using partitions from said control flow graph; wherein obtaining a control flow graph comprises the steps of: utilizing a parser to obtain an abstract syntax tree of said source program; and, utilizing a control flow graph builder on said abstract syntax tree to obtain said control flow graph.
Claim 18
Independent Claim
74 words
A method of performing partition based alias analysis comprising the steps of: obtaining a control flow graph from a source program; and, obtaining safe alias solutions using partitions from said control flow graph; wherein obtaining a control flow graph comprises the steps of: utilizing a parser to obtain an abstract syntax tree of said source program; and, utilizing a control flow graph builder on said abstract syntax tree to obtain said control flow graph.
Claim 19
Dependent Claim
58 words
A method of performing partition based alias analysis as claimed in claim 12 wherein obtaining safe alias solutions using partitions comprises the steps of: utilizing type one alias effects for providing initial partitions; utilizing type two alias effects for providing alias partitions without function pointers effects; and, utilizing function pointer effects for providing safe alias solutions using partitions.
Claim 20
Independent Claim
75 words
A method of performing partition based alias analysis comprising the steps of: obtaining a control flow graph from a source program; and, obtaining safe alias solutions using partitions from said control flow graph; wherein obtaining safe alias solutions using partitions comprises the steps of: utilizing union/find data structures to represent alias solutions; explicitly finding aliases only for names that are physically in said source program; and, accounting for function pointer resolution in a separate phase.
Claim 21
Independent Claim
75 words
A method of performing partition based alias analysis comprising the steps of: obtaining a control flow graph from a source program; and, obtaining safe alias solutions using partitions from said control flow graph; wherein obtaining safe alias solutions using partitions comprises the steps of: utilizing union/find data structures to represent alias solutions; explicitly finding aliases only for names that are physically in said source program; and, accounting for function pointer resolution in a separate phase.
Claim 22
Dependent Claim
117 words
A partition based alias analyzer comprising: phase one--type one alias effects for receiving a control flow graph and for providing initial partitions; phase two--type two alias effects for receiving said control flow graph and said initial partitions and for providing alias partitions without function pointers effects; and, phase three--function pointer effects for receiving said control flow graph and said alias partitions without function pointers effects and for providing safe alias solutions using partitions; wherein: union/find data structures are used to represent alias solutions; there is a restriction of explicitly finding aliases only for names that are physically in a source program; and, accounting for function pointer resolution is a separate phase of said partitioned based alias analyzer.
Claim 23
Dependent Claim
117 words
A partition based alias analyzer comprising: phase one--type one alias effects for receiving a control flow graph and for providing initial partitions; phase two--type two alias effects for receiving said control flow graph and said initial partitions and for providing alias partitions without function pointers effects; and, phase three--function pointer effects for receiving said control flow graph and said alias partitions without function pointers effects and for providing safe alias solutions using partitions; wherein: union/find data structures are used to represent alias solutions; there is a restriction of explicitly finding aliases only for names that are physically in a source program; and, accounting for function pointer resolution is a separate phase of said partitioned based alias analyzer.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-04-19 | 2002-10-19 | 2003-04-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-04-19 | 2006-10-19 | 2007-04-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-04-19 | 2010-10-19 | 2011-04-20 | $7700.00 | Window Closed / Lapsed |