Polaris: AIRangeDict Class Reference
Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members

AIRangeDict Class Reference

file AIRangeDict.h Collection of ranges that were generated by abstract interpretation More...

#include <AIRangeDict.h>

Inheritance diagram for AIRangeDict:

Inheritance graph
[legend]
List of all members.

Public Member Functions

 AIRangeDict (ProgramUnit &pgm, int debug=0)
 AIRangeDict (const AIRangeDict &other)
virtual ~AIRangeDict ()
 Destructor.
virtual AIRangeDict & operator= (const AIRangeDict &other)
 Completely copy the contents of the other range dictionary into myself.
RefSet< Symbol > * range_vars (const String &tag) const
 Return the set of variables that have ranges for a particular statement.
virtual StmtRanges & _s_ranges (const String &tag)
 Return a reference to the StmtRanges object associated with the given statement tag.
Expression * elim_known_facts (const String &, Expression *)
 Accept a statement tag and a conditional expression and use the range dictionary attached to the Statement to eliminate tests from the conditional which are known to be true within the dictionary.
virtual void print (ostream &o) const
 Print out the range dictionary.
virtual void pretty_print (ostream &o, const Statement &stmt) const
 Print out the range dictionary in a more user-readable manner.
virtual Listable * listable_clone (void) const
 listable_clone
virtual int structures_OK () const
 Methods required by Listable.

Protected Member Functions

virtual void _set_range (const Symbol &var, const Statement &stmt, Expression *range)
 Set the given variable to the given range.
virtual void _del_range (const Symbol &var, const Statement &stmt)
 Delete the range associated with the given variable.
virtual const Expression * _get_range_ref (const Symbol &var, const Statement &stmt)
 Return the range associated with the given variable.

Friends

class AbstractAccess

Detailed Description

file AIRangeDict.h Collection of ranges that were generated by abstract interpretation

Polaris Range

See also:
AIRangeDict.h

AIRangeDict.h

AIRangeDict.cc

Overview

A AIRangeDict object is a repository for variable ranges for a program unit. AI stands for Abstract Interpretation, which is the method used to generate these ranges from the given program unit.

Description

A AIRangeDict object is a repository of the variable ranges for all points of a program unit. Abstract interpretation is used to compute these ranges. Abstract interpretation is a generalization of data flow analysis techniques. It computes the ranges by "executing" the given program unit at compile time, by following the control flow paths of the program, updating the current ranges to reflect the side effects of the statements encountered along these paths, until a fixed point is reached. See Blume and Eigenmann, "Symbolic Range Propagation", for more details.

The computed ranges are stored in a collection of StmtRanges objects. Each StmtRanges object holds all the variable constraints for a single Statement in the program.

Switches

By setting "range_block" to 1, the AIRangeDict constructor would automatically clear all ranges whenever it sees a BEGIN BLOCK or END BLOCK assertion when it is computing ranges. This switch should approximate the ranges computed for uninlined programs when run on a partially or fully inlined program. Basically, this switch causes the AIRangeDict to compute less accurate ranges for the sake of speed and memory used.

Setting switch "pc_call_mods" to 1 causes the AIRangeDict constructor to assume that subroutine and function calls only modify thier arguments. That is, global varaibles and subroutine parameters are assumed to be unmodified by a subroutine call unless they also appear in that call's arguments. Results in more accurate ranges. May also result in incorrect ranges, if this assumption does not hold in actuality.

Known Bugs or Limitations

AIRangeDict objects can consume large amounts of time and large amounts of memory. This is because the time and space requirements are O(V*S), where S is the number of statements in a program and V is the number of integer variables in a program. (In actuality, V can be improved to be the average number of integer variables that have constraints.)

Definition at line 72 of file AIRangeDict.h.

Constructor & Destructor Documentation

AIRangeDict::AIRangeDict (  ProgramUnit &  pgm,
int  debug = 0
) 
 

Referenced by listable_clone().

AIRangeDict::AIRangeDict (  const AIRangeDict &  other  ) 
 

Definition at line 1243 of file AIRangeDict.cc.

References register_instance().

AIRangeDict::~AIRangeDict (   )  [virtual]
 

Destructor.

... nothing to do

Definition at line 1256 of file AIRangeDict.cc.

References unregister_instance().

Member Function Documentation

AIRangeDict & AIRangeDict::operator= (  const AIRangeDict &  other  )  [virtual]
 

Completely copy the contents of the other range dictionary into myself.

Definition at line 1269 of file AIRangeDict.cc.

References RangeDict::operator=().

RefSet< Symbol > * AIRangeDict::range_vars (  const String &  tag  )  const
 

Return the set of variables that have ranges for a particular statement.

Return the set of symbols in the range dictionary for a given statement If no symbols exist for a statement, return 0.

Definition at line 1286 of file AIRangeDict.cc.

References ProtoDatabase< S, T >::find_ref(), and StmtRanges::range_vars().

Referenced by AbstractAccess::remap_interface_vars().

StmtRanges & AIRangeDict::_s_ranges (  const String &  tag  )  [virtual]
 

Return a reference to the StmtRanges object associated with the given statement tag.

Definition at line 1403 of file AIRangeDict.cc.

Expression * AIRangeDict::elim_known_facts (  const String &  ,
Expression * 
) 
 

Accept a statement tag and a conditional expression and use the range dictionary attached to the Statement to eliminate tests from the conditional which are known to be true within the dictionary.

Works for Fortran logical operators (.LE., .GT., etc) and for MIN and MAX.

Definition at line 1301 of file AIRangeDict.cc.

References elim_known_facts(), and ProtoDatabase< S, T >::find_ref().

void AIRangeDict::print (  ostream &  o  )  const [virtual]
 

Print out the range dictionary.

This operation is essentially just a dump of the data structures of the range dictionary.

Implements Listable.

Definition at line 1358 of file AIRangeDict.cc.

References KeyIterator< S, T >::current_data(), KeyIterator< S, T >::current_key(), and KeyIterator< S, T >::valid().

void AIRangeDict::pretty_print (  ostream &  o,
const Statement &  stmt
)  const [virtual]
 

Print out the range dictionary in a more user-readable manner.

Implements RangeDict.

Definition at line 1371 of file AIRangeDict.cc.

References ProtoDatabase< S, T >::find_ref(), and BaseStmtRanges::pretty_print().

Listable * AIRangeDict::listable_clone (  void   )  const [virtual]
 

listable_clone

Implements Listable.

Definition at line 1385 of file AIRangeDict.cc.

References AIRangeDict().

int AIRangeDict::structures_OK (   )  const [virtual]
 

Methods required by Listable.

Definition at line 1395 of file AIRangeDict.cc.

References BaseMapRoot::structures_OK().

void AIRangeDict::_set_range (  const Symbol &  var,
const Statement &  stmt,
Expression *  range
)  [protected, virtual]
 

Set the given variable to the given range.

Implements RangeDict.

Definition at line 1312 of file AIRangeDict.cc.

References ProtoDatabase< S, T >::find_ref(), Database< S, T >::ins(), StmtRanges::set_range(), and RangeDict::symtab().

void AIRangeDict::_del_range (  const Symbol &  var,
const Statement &  stmt
)  [protected, virtual]
 

Delete the range associated with the given variable.

Implements RangeDict.

Definition at line 1330 of file AIRangeDict.cc.

References StmtRanges::del_range(), and ProtoDatabase< S, T >::find_ref().

const Expression * AIRangeDict::_get_range_ref (  const Symbol &  var,
const Statement &  stmt
)  [protected, virtual]
 

Return the range associated with the given variable.

If the variable doesn't have an associated range, return 0;

Implements RangeDict.

Definition at line 1343 of file AIRangeDict.cc.

References ProtoDatabase< S, T >::find_ref(), and BaseStmtRanges::get_range_ref().

Referenced by AbstractAccess::remap_interface_vars().

Friends And Related Function Documentation

friend class AbstractAccess [friend]
 

Reimplemented from RangeDict.

Definition at line 73 of file AIRangeDict.h.

The documentation for this class was generated from the following files:
 © 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:06:37 2005