Polaris: PropCtrlRangeWS.cc Source File

PropCtrlRangeWS.cc Go to the documentation of this file. /// /// /// \file PropCtrlRangeWS.cc #ifndef _PROP_CTRL_RANGE_WS_CC #define _PROP_CTRL_RANGE_WS_CC /// #include "../Collection/Iterator.h" #include "../utilities/equivalence_util.h" #include "PropCtrlRangeWS.h" #include "RangeExpr.h" #include "range_util.h" /// add_to_mod_set /// Add the given set of variables to my mod_set. void PropCtrlRangeWS::_add_to_mod_set(const RefSet<Expression> &refs) { Iterator<Expression> iter = refs; for ( ; iter.valid(); ++iter) { Symbol *symbol = iter.current().base_variable_ref(); if (symbol && symbol->sym_class() == VARIABLE_CLASS) if (symbol->type().data_type() == INTEGER_TYPE) mod_set.ins(*symbol); /// ... Also place any aliased variables in the set. RefSet<Symbol> *aliases = equiv_aliases(*symbol); if (aliases) { Iterator<Symbol> alias_iter = *aliases; for ( ; alias_iter.valid(); ++alias_iter) { Symbol &alias_symbol = alias_iter.current(); if (alias_symbol.type().data_type() == INTEGER_TYPE) mod_set.ins(alias_symbol); } delete aliases; } } } /// add_asserts_to_ranges /// Add any ranges derived from ASSERT directives to my set of new /// variable ranges. void PropCtrlRangeWS::_add_asserts_to_ranges(const Statement &stmt) { Iterator<Assertion> assert_iter = stmt.assertions(); for ( ; assert_iter.valid(); ++assert_iter) { const Assertion &assert = assert_iter.current(); if (assert.type() == AS_RELATION) { Iterator<Expression> arg_iter = assert.arg_list_guarded(); for ( ; arg_iter.valid(); ++arg_iter) { Map< Symbol, Set<Expression> > *assert_ranges = extract_ranges(arg_iter.current()); if (! new_ranges) new_ranges = assert_ranges; else { KeyIterator<Symbol, Set<Expression> > ar_iter = *assert_ranges; for ( ; ar_iter.valid(); ++ar_iter) { const Symbol &var = ar_iter.current_key(); Set<Expression> *var_ranges = new_ranges->find_ref(var); if (! var_ranges) new_ranges->ins(var, new Set<Expression>(ar_iter.current_data())); else { Iterator<Expression> range_iter = ar_iter.current_data(); for ( ; range_iter.valid(); ++range_iter) var_ranges->ins(range_iter.current().clone()); } } delete assert_ranges; } } } } } /// Constructors PropCtrlRangeWS::PropCtrlRangeWS(unsigned long pass_tag, const Statement &stmt) : WorkSpace(pass_tag) { _add_to_mod_set(stmt.out_refs()); /// ... _add_to_mod_set(stmt.act_refs()); new_ranges = 0; new_else_ranges = 0; if (stmt.stmt_class() == IF_STMT || stmt.stmt_class() == ELSEIF_STMT) { new_ranges = extract_ranges(stmt.expr(), false); new_else_ranges = extract_ranges(stmt.expr(), true); } else if (stmt.stmt_class() == DO_STMT && stmt.index().type().data_type() == INTEGER_TYPE && is_integer_constant(stmt.step())) { Expression *bound_cond, *index_range; if (stmt.step().value() >= 0) { bound_cond = le(stmt.init().clone(), stmt.limit().clone()); index_range = new RangeExpr(stmt.init().clone(), stmt.limit().clone()); } else { bound_cond = ge(stmt.init().clone(), stmt.limit().clone()); index_range = new RangeExpr(stmt.limit().clone(), stmt.init().clone()); } new_ranges = extract_ranges(*bound_cond); delete bound_cond; Set<Expression> *index_set = new Set<Expression>; index_set->ins(index_range); new_ranges->ins(stmt.index().symbol(), index_set); new_else_ranges = new Map< Symbol, Set<Expression> >; } _add_asserts_to_ranges(stmt); _num_visits = 0; _visited = false; _toporder = -1; } PropCtrlRangeWS::PropCtrlRangeWS(const PropCtrlRangeWS &other) : WorkSpace(other) { mod_set = other.mod_set; if (other.new_ranges) new_ranges = new Map< Symbol, Set<Expression> >(*other.new_ranges); else new_ranges = 0; if (other.new_else_ranges) new_else_ranges = new Map< Symbol, Set<Expression> >(*other.new_else_ranges); else new_else_ranges = 0; in_ranges = other.in_ranges; out_ranges = other.out_ranges; out_else_ranges = other.out_else_ranges; _num_visits = other._num_visits; _visited = other._visited; _toporder = other._toporder; } /// Destructor PropCtrlRangeWS::~PropCtrlRangeWS() { if (new_ranges) delete new_ranges; if (new_else_ranges) delete new_else_ranges; } /// add_range_refs /// Add references to the ranges of the second range map to the first /// range map. static void _add_range_refs(Map<Symbol, RefSet<Expression> > &ranges, const Map<Symbol, Set<Expression> > &new_ranges) { KeyIterator<Symbol, Set<Expression> > new_iter = new_ranges; for ( ; new_iter.valid(); ++new_iter) { const Symbol &var = new_iter.current_key(); RefSet<Expression> *var_ranges = ranges.find_ref(var); if (! var_ranges) { var_ranges = new RefSet<Expression>; ranges.ins(var, var_ranges); } Iterator<Expression> range_iter = new_iter.current_data(); for ( ; range_iter.valid(); ++range_iter) var_ranges->ins(range_iter.current()); } } /// _are_vars_in_expr /// Return true if the given expression uses any of the variables in the /// given set. static bool _are_vars_in_expr(const Expression &e, const RefSet<Symbol> &vars) { if (e.op() == ID_OP) return vars.member(e.symbol()); else { Iterator<Expression> iter = e.arg_list(); for ( ; iter.valid(); ++iter) if (_are_vars_in_expr(iter.current(), vars)) return true; } return false; } /// update_out_ranges bool PropCtrlRangeWS::update_out_ranges() { bool result = false; out_ranges = in_ranges; if (mod_set.entries() > 0) { KeyIterator<Symbol, RefSet<Expression> > out_iter = out_ranges; for ( ; out_iter.valid(); ++out_iter) { Mutator<Expression> out_range_iter = out_iter.current_data(); for ( ; out_range_iter.valid(); ++out_range_iter) if (_are_vars_in_expr(out_range_iter.current(), mod_set)) { out_range_iter.del(); result = true; } } } if (new_else_ranges) { out_else_ranges = out_ranges; _add_range_refs(out_else_ranges, *new_else_ranges); result = true; } if (new_ranges) { _add_range_refs(out_ranges, *new_ranges); result = true; } return result; } /// print_var_set /// Print the given set of symbols. static void _print_var_set(ostream &o, const RefSet<Symbol> &var_set) { Iterator<Symbol> var_iter = var_set; o << "{"; if (var_iter.valid()) { o << var_iter.current().name_ref(); ++var_iter; for ( ; var_iter.valid(); ++var_iter) o << ", " << var_iter.current().name_ref(); } o << "}"; } /// print_range_map /// Print the given map from variables to set of ranges static void _print_range_map(ostream &o, const Map<Symbol, Set<Expression> > &ranges) { o << "{"; KeyIterator<Symbol, Set<Expression> > rmap_iter = ranges; if (rmap_iter.valid()) { o << rmap_iter.current_key().name_ref() << ": " << rmap_iter.current_data(); ++rmap_iter; for ( ; rmap_iter.valid(); ++rmap_iter) o << ", "<< rmap_iter.current_key().name_ref() << ": " << rmap_iter.current_data(); } o << "}"; } static void _print_range_map(ostream &o, const Map<Symbol, RefSet<Expression> > &ranges) { o << "{"; KeyIterator<Symbol, RefSet<Expression> > rmap_iter = ranges; if (rmap_iter.valid()) { o << rmap_iter.current_key().name_ref() << ": " << rmap_iter.current_data(); ++rmap_iter; for ( ; rmap_iter.valid(); ++rmap_iter) o << ", "<< rmap_iter.current_key().name_ref() << ": " << rmap_iter.current_data(); } o << "}"; } /// print void PropCtrlRangeWS::print(ostream &o) const { o << "RangeWS:{"; o << "mod="; _print_var_set(o, mod_set); o << ", "; o << "new_ranges="; if (new_ranges) _print_range_map(o, *new_ranges); else o << "NULL"; o << ", "; o << "new_else_ranges="; if (new_else_ranges) _print_range_map(o, *new_else_ranges); else o << "NULL"; o << ", "; o << "in_ranges="; _print_range_map(o, in_ranges); o << ", "; o << "out_ranges="; _print_range_map(o, out_ranges); o << ", "; o << "out_else_ranges="; _print_range_map(o, out_else_ranges); o << ", "; o << "num_visits=" << _num_visits << ", "; o << "toporder=" << _toporder << ", "; o << "}"; } /// structures_OK int PropCtrlRangeWS::structures_OK() const { if (! mod_set.structures_OK()) return 0; if (new_ranges && ! new_ranges->structures_OK()) return 0; if (new_else_ranges && ! new_else_ranges->structures_OK()) return 0; if (! in_ranges.structures_OK()) return 0; if (! out_ranges.structures_OK()) return 0; if (! out_else_ranges.structures_OK()) return 0; return 1; } #endif

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:06:03 2005