Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6736
Title: Static Analysis of Aliases and Side Effects in Higher-Order Languages
Authors: Neirynck, Anne
Keywords: computer science
technical report
Issue Date: Feb-1988
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-896
Abstract: In recent years, there has been substantial interest in the development of programming languages for new parallel architectures. A basic design conflict arises because languages with simple semantics tend to use storage inefficiently, whereas languages allowing the programmer to access storage explicitly are difficult to analyze. We present a compile-time estimation scheme for determining whether an expression in an imperative language either uses or updates the store. We also determine the aliasing behavior of expressions and in general, we can tell whether the evaluation of two expressions interfere. Current interprocedural dataflow techniques for aliasing and side effect inference are valid for first-order languages. Our inference schemes provide information about aliasing and side effects in a higher-order expression language with call-by-value semantics. The higher order character of the language represents only a partial obstacle. On the other hand, the presence of l-valued expressions has the consequence that aliasing information must be computed for all expressions, and cannot be represented as a relation among identifiers. Furthermore, the introduction of pointers make aliasing and side effects flow-dependent properties. Abstract interpretation techniques allow us to define compositional static inference schemes for aliasing and side effects, which can be proved sound with respect to the standard semantics by structural induction. The abstract interpretation functions are easy to modify, in case a different type of information is requested. We also discuss how different language features may affect the static analyses, simplifying them or making them untractable. The abstract interpretation functions implicitly define static inference algorithms, which can easily be implemented by an attribute grammar, or any other tool capable of performing computations on the abstract syntax tree. The accuracy of these algorithms is better than for the dataflow ones, because we make use of control flow information. Our algorithms also compare favorably in complexity, but the dataflow approach is probably cheaper in most practical settings. In addition, our schemes can give information even in the presence of dynamically allocated data structures.
URI: http://hdl.handle.net/1813/6736
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
88-896.pdf6.71 MBAdobe PDFView/Open
88-896.ps1.31 MBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us