Polaris: SimGraph.cc Source File

SimGraph.cc Go to the documentation of this file. /// /// \file SimGraph.cc /// #ifdef POLARIS_GNU_PRAGMAS #pragma implementation #endif /// #include "SimGraph.h" #include "UEdge.h" #include "utilities/access_util.h" #include "utilities/stmt_util.h" #include "Range/Relation.h" #include "Range/RangeAccessor.h" #include "UBiGraphIterator.h" /// Create an empty graph SimGraph::SimGraph( ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_GRAPH, sizeof(SimGraph), this); #endif _descr_exists = new Array< bool >; _ptrs = new Array< RefElement< AbstractAccess > >; _graph = new Array<Array<SimEdgeKernel> >; _nodes = 0; _range_acc = 0; } /// Create a complete graph with given number of nodes SimGraph::SimGraph( List<AbstractAccess> & list ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_GRAPH, sizeof(SimGraph), this); #endif /// ... Make a complete graph with the proper number of nodes _nodes = list.entries(); if (_nodes < 2) { _range_acc = 0; _ptrs = 0; _descr_exists = 0; _graph = 0; return; } _ptrs = new Array< RefElement< AbstractAccess > >; _graph = new Array<Array<SimEdgeKernel> >; _ptrs->resize(_nodes); _graph->resize(_nodes); _descr_exists = new Array< bool >; _descr_exists->resize( _nodes ); /// ... Mark that all nodes are valid to start with for (int i=0; i < _nodes; ++i) { (*_descr_exists)[i] = true; } Iterator<AbstractAccess> iter = list; for (int i = 0; iter.valid(); ++iter,++i) { (*_ptrs)[i] = iter.current(); (*_graph)[i].resize(_nodes); } /// ... Initialized each edge to SIM_UNKNOWN for (int i=0; i<_nodes; ++i) { for (int j=0; j<_nodes; ++j) { (((*_graph)[i])[j]).type(SIM_UNKNOWN); } } Statement * r_stmt = range_stmt(*(list[0]._summarized_to)); String stmt_tag = r_stmt->tag(); _range_acc = new RangeAccessor(list[0]._pgm_summarized_to->range_dict_guarded(), *r_stmt ); /// ... Compare each pair of descriptors, building the Similarity graph as we go for (int i=0; i<_nodes; ++i) { if (!(*_descr_exists)[i]) continue; for (int j=i+1; j<_nodes; ++j) { if (!(*_descr_exists)[j]) continue; calc_similarity( i, j ); } } } void SimGraph::print_similarities( ) const { if (_ar_logging && _ar_logging % 5 == 0) { for (int i=0; i<_nodes; ++i) { if (!(*_descr_exists)[i]) continue; arlog << "[" << i << "]" ; AbstractAccess & aa = *((*_ptrs)[i]); int ndims1 = aa.number_of_dimensions(); for (int j=0; j<_nodes; ++j) { if (!(*_descr_exists)[j]) continue; AbstractAccess & aa2 = *((*_ptrs)[j]); SimEdgeKernel & sek = ((*_graph)[i])[j]; int ndims2 = aa2.number_of_dimensions(); arlog << " " << sek.type_name() << "[" ; if ((i != j) && (ndims1 == ndims2) && (sek.type() != SIM_NOT_SIMILAR)) { for (int k=0; k<aa.number_of_dimensions(); ++k) { arlog << (*(sek.stridematch()))[k] << ":" ; if ((*(sek.spanmatch()))[k]) { arlog << "T"; } else { arlog << "F"; } } } arlog << "]"; } arlog << endl; } } } /// Add edges determined by transitivity - Given a matching from new to mid, want to construct a matching from new to old void SimGraph::_add_corresp_edge_forward(SimilarityType type, int index_new, int index_mid, int index_old, Array<int> * stride_match_new_mid, Array<bool> * span_match_new_mid) { /// ... The stride_match must be the matching from index_new to index_mid SimEdgeKernel & kernel_mid_old = ((*_graph)[index_mid])[index_old]; Array<int> * stride_match_mid_old = kernel_mid_old.stridematch( ); Array<bool> * span_match_mid_old = kernel_mid_old.spanmatch( ); int new_dims = ((*_ptrs)[index_new])->number_of_dimensions(); Array<int> * stride_match_new_old = new Array<int>; (*stride_match_new_old).resize( new_dims ); Array<bool> * span_match_new_old = new Array<bool>; (*span_match_new_old).resize( new_dims ); for (int i=0; i<new_dims; ++i) { if ( (*stride_match_new_mid)[i] == -1 ) { (*stride_match_new_old)[i] = -1; (*span_match_new_old)[i] = false; } else { (*stride_match_new_old)[i] = (*stride_match_mid_old)[ (*stride_match_new_mid)[i] ]; (*span_match_new_old)[i] = (*span_match_new_mid)[i] && (*span_match_mid_old)[ (*stride_match_new_mid)[i] ]; } } SimEdgeKernel & kernel_new_old = ((*_graph)[index_new])[index_old]; kernel_new_old.dump_in_match( type, stride_match_new_old, span_match_new_old ); } /// Given a matching from mid to new, need to construct a matching from old to new void SimGraph::_add_corresp_edge_backward(SimilarityType type, int index_old, int index_mid, int index_new, Array<int> * stride_match_mid_new, Array<bool> * span_match_mid_new) { /// ... The stride_match must be the matching from index_mid to index_new SimEdgeKernel & kernel_old_mid = ((*_graph)[index_old])[index_mid]; Array<int> * stride_match_old_mid = kernel_old_mid.stridematch( ); Array<bool> * span_match_old_mid = kernel_old_mid.spanmatch( ); int old_dims = ((*_ptrs)[index_old])->number_of_dimensions(); Array<int> * stride_match_old_new = new Array<int>; (*stride_match_old_new).resize( old_dims ); Array<bool> * span_match_old_new = new Array<bool>; (*span_match_old_new).resize( old_dims ); for (int i=0; i<old_dims; ++i) { if ( (*stride_match_old_mid)[i] == -1 ) { (*stride_match_old_new)[i] = -1; (*span_match_old_new)[i] = false; } else { (*stride_match_old_new)[i] = (*stride_match_mid_new)[ (*stride_match_old_mid)[i] ]; (*span_match_old_new)[i] = (*span_match_old_mid)[i] && (*span_match_mid_new)[ (*stride_match_old_mid)[i] ]; } } SimEdgeKernel & kernel_old_new = ((*_graph)[index_old])[index_new]; kernel_old_new.dump_in_match( type, stride_match_old_new, span_match_old_new ); } /// Create a copy of a given graph SimGraph::SimGraph( const SimGraph & other ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_GRAPH, sizeof(SimGraph), this); #endif _nodes = other._nodes; _ptrs = new Array< RefElement< AbstractAccess > >; _descr_exists = new Array< bool >; _graph = new Array< Array< SimEdgeKernel > >; _ptrs->resize(_nodes); _descr_exists->resize( _nodes ); _graph->resize(_nodes); for (int i = 0; i<_nodes; ++i) { (*_ptrs)[i] = (*(other._ptrs))[i]; (*_descr_exists)[i] = (*_descr_exists)[i]; (*_graph)[i].resize(_nodes); } for (int i=0; i < _nodes; ++i) { for (int j=0; j < _nodes; ++j) { ((*_graph)[i])[j] = ((*(other._graph))[i])[j]; } } } /// Return the number of nodes in the graph int SimGraph::nodes( ) { return _nodes; } SimGraph::~SimGraph( ) { #ifdef CLASS_INSTANCE_REGISTRY unregister_instance(SIM_GRAPH, this); #endif if (_ptrs) { delete _ptrs; } if (_descr_exists) { delete _descr_exists; } if (_graph) { delete _graph; } if (_range_acc) { delete _range_acc; } } /// Calculate the similarity relationship between nodes i and j in the Similarity graph void SimGraph::calc_similarity( int i, int j ) { AbstractAccess & descr1 = *((*_ptrs)[ i ]); int ndims1 = descr1.number_of_dimensions(); AbstractAccess & descr2 = *((*_ptrs)[ j ]); int ndims2 = descr2.number_of_dimensions(); SimEdgeKernel & kernelij = ((*_graph)[i])[j]; SimEdgeKernel & kernelji = ((*_graph)[j])[i]; SimilarityType orig_ij_type = kernelij.type(); SimilarityType calc_ij_type; /// ... If already filled in, skip it if ((orig_ij_type != SIM_UNKNOWN ) && (orig_ij_type != SIM_DIM_EQUIV_UP ) && (orig_ij_type != SIM_STRIDE_EQUIV_UP )) return; bool equal_dim_count; if (ndims1 == ndims2) { equal_dim_count = true; } else { equal_dim_count = false; } bool matchoff = false; bool matchstrides, matchspans; Array<int> * stride_match1; Array<int> * stride_match2; Array<bool> * span_match1; Array<bool> * span_match2; /// ... Do the offsets match? matchoff = ar_offsets_match(descr1, descr2); /// ... If these two descriptors were already found dimension-equivalent, /// ... check offsets to see whether they are totally equivalent. Then we /// ... can avoid all the rest of the equivalency checks. if (orig_ij_type == SIM_DIM_EQUIV_UP) { if (matchoff) { calc_ij_type = SIM_EQUIV; } else { calc_ij_type = SIM_DIM_EQUIV; } kernelij.type(calc_ij_type); kernelji.type(calc_ij_type); stride_match1 = kernelij.stridematch(); span_match1 = kernelij.spanmatch(); stride_match2 = kernelji.stridematch(); span_match2 = kernelji.spanmatch(); } else { /// ... Compare one dimension from each descriptor stride_match1 = new Array<int>; stride_match1->resize(ndims1); stride_match2 = new Array<int>; stride_match2->resize(ndims2); span_match1 = new Array<bool>; span_match1->resize(ndims1); span_match2 = new Array<bool>; span_match2->resize(ndims2); if (orig_ij_type == SIM_STRIDE_EQUIV_UP) { /// ... Check only for a span match based on the previous stride match Array<int> * temp1 = kernelij.stridematch(); for (int ii=0; ii<ndims1; ++ii) { (*stride_match1)[ii] = (*temp1)[ii]; (*span_match1)[ii] = false; } Array<int> * temp2 = kernelji.stridematch(); for (int ii=0; ii<ndims2; ++ii) { (*stride_match2)[ii] = (*temp2)[ii]; (*span_match2)[ii] = false; } } else { calc_stride_span_match(descr1, descr2, *_range_acc, *stride_match1, *stride_match2, *span_match1, *span_match2); } /// ... Now, check for a match. if (orig_ij_type == SIM_STRIDE_EQUIV_UP) { matchstrides = true; /// ... Already asserted that strides are equiv } else { matchstrides = true; /// ... Check whether all dimensions of at least one descriptor /// ... have a matching dimension. int count1 = 0; for (int ii=0; ii<ndims1; ++ii) { if ((*stride_match1)[ii] != -1) { count1++; } } int count2 = 0; for (int ii=0; ii<ndims2; ++ii) { if ((*stride_match2)[ii] != -1) { count2++; } } p_assert(count1 == count2, "Stride-match is not reflexive"); if ((count1 != ndims1) && (count1 != ndims2)) { matchstrides = false; } } matchspans = true; for (int ii=0; ii<ndims1; ++ii) { if (((*stride_match1)[ii] != -1) && (! (*span_match1)[ii])) { matchspans = false; break; } } if (matchoff && matchstrides && matchspans && equal_dim_count) { calc_ij_type = SIM_EQUIV; } else if (matchoff && matchstrides && matchspans) { calc_ij_type = SIM_EQUIV_SEMI; } else if (matchstrides && matchspans && equal_dim_count) { calc_ij_type = SIM_DIM_EQUIV; } else if (matchstrides && matchspans) { calc_ij_type = SIM_DIM_EQUIV_SEMI; } else if (matchstrides && equal_dim_count) { calc_ij_type = SIM_STRIDE_EQUIV; } else if (matchstrides) { calc_ij_type = SIM_STRIDE_EQUIV_SEMI; } else { calc_ij_type = SIM_NOT_SIMILAR; } kernelij.dump_in_match( calc_ij_type, stride_match1, span_match1 ); kernelji.dump_in_match( calc_ij_type, stride_match2, span_match2 ); } if (kernelij.type( ) == SIM_NOT_SIMILAR) return; /// ... Now, see if we can fill in any more nodes in the graph /// ... The above tested descriptor i against descriptor j /// ... Now, we check all other nodes (k) connected to i for a relationship with j for (int k=0; k<_nodes; ++k) { if (!(*_descr_exists)[k]) continue; if (k == i) continue; /// ... The above tested i vs j if (k == j) continue; /// ... This would be testing j vs itself SimilarityType ik_type = ((*_graph)[i])[k].type(); if ((ik_type != SIM_NOT_SIMILAR) && (ik_type != SIM_UNKNOWN)) { if (calc_ij_type == SIM_EQUIV) { /// ... j = i && i ? k => j ? k _add_corresp_edge_forward ( ik_type, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( ik_type, k, i, j, stride_match1, span_match1 ); } else if (ik_type == SIM_EQUIV) { /// ... j ? i && i = k => j ? k _add_corresp_edge_forward ( calc_ij_type, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( calc_ij_type, k, i, j, stride_match1, span_match1 ); } else if ((calc_ij_type == SIM_DIM_EQUIV) && /// ... j =d i && i =d k => j =d^ k (ik_type == SIM_DIM_EQUIV)) { _add_corresp_edge_forward ( SIM_DIM_EQUIV_UP, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( SIM_DIM_EQUIV_UP, k, i, j, stride_match1, span_match1 ); } else if ((calc_ij_type == SIM_STRIDE_EQUIV) && /// ... j =s i && i =s k => j =s^ k (ik_type == SIM_STRIDE_EQUIV)) { _add_corresp_edge_forward ( SIM_STRIDE_EQUIV_UP, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( SIM_STRIDE_EQUIV_UP, k, i, j, stride_match1, span_match1 ); } else if (((calc_ij_type == SIM_STRIDE_EQUIV) && /// ... j =s i && i =d k => j =s k (ik_type == SIM_DIM_EQUIV)) || /// ... j =d i && i =s k => j =s k ((calc_ij_type == SIM_DIM_EQUIV) && (ik_type == SIM_STRIDE_EQUIV))) { _add_corresp_edge_forward ( SIM_STRIDE_EQUIV, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( SIM_STRIDE_EQUIV, k, i, j, stride_match1, span_match1 ); } else if ((calc_ij_type == SIM_DIM_EQUIV) && /// ... j =d i && i =d^ k => j =d^ k (ik_type == SIM_DIM_EQUIV_UP)) { _add_corresp_edge_forward ( SIM_DIM_EQUIV_UP, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( SIM_DIM_EQUIV_UP, k, i, j, stride_match1, span_match1 ); } else if ((calc_ij_type == SIM_DIM_EQUIV) && /// ... j =d i && i =s^ k => j =s^ k (ik_type == SIM_STRIDE_EQUIV_UP)) { _add_corresp_edge_forward ( SIM_STRIDE_EQUIV_UP, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( SIM_STRIDE_EQUIV_UP, k, i, j, stride_match1, span_match1 ); } else if ((calc_ij_type == SIM_STRIDE_EQUIV) && /// ... j =s i && i =d^ k => j =s k (ik_type == SIM_DIM_EQUIV_UP)) { _add_corresp_edge_forward ( SIM_STRIDE_EQUIV, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( SIM_STRIDE_EQUIV, k, i, j, stride_match1, span_match1 ); } else if ((calc_ij_type == SIM_STRIDE_EQUIV) && /// ... j =s i && i =s^ k => j =s^ k (ik_type == SIM_STRIDE_EQUIV_UP)) { _add_corresp_edge_forward ( SIM_STRIDE_EQUIV_UP, j, i, k, stride_match2, span_match2 ); _add_corresp_edge_backward( SIM_STRIDE_EQUIV_UP, k, i, j, stride_match1, span_match1 ); } else { continue; } } } } /// Check connections for the node which was in an aggregation. When a SIM_DIM_EQUIV /// is found, set the appropriate span-match flag false (since the span is changed /// by the aggregation. void SimGraph::redo_spanmatch( SimEdge & edge, int which_node, int which_dim ) { for (int i=0; i<_nodes; ++i) { if (!(*_descr_exists)[i]) continue; if (i==which_node) continue; SimEdgeKernel & edgek = ((*_graph)[which_node])[i]; if ((edgek.type() == SIM_DIM_EQUIV) || (edgek.type() == SIM_DIM_EQUIV_UP)) { (*(edgek.spanmatch()))[which_dim] = false; SimEdgeKernel & edgek2 = ((*_graph)[i])[which_node]; (*(edgek2.spanmatch()))[(*(edgek.stridematch()))[which_dim]] = false; } } } void SimGraph::set_unknown( SimEdge & edge, int which_node) { for (int i=0; i<_nodes; ++i) { if (!(*_descr_exists)[i]) continue; if (i==which_node) continue; ((*_graph)[which_node])[i].type(SIM_UNKNOWN); ((*_graph)[i])[which_node].type(SIM_UNKNOWN); } } RangeAccessor * SimGraph::range_acc( ) { return _range_acc; } SimGraph * SimGraph::clone() const { return new SimGraph( (SimGraph &)*this ); } Listable * SimGraph::listable_clone() const { return (Listable *) clone(); } void SimGraph::print(ostream & o) const { o << "{ Nodes: " << _nodes << "; Ptrs: " << *_ptrs << "; Graph: " << *_graph << "}"; } ostream & operator << (ostream & o, const SimGraph & graph) { graph.print(o); return o; } SimEdgeKernel & SimGraph::kernel(int i, int j) { return ((*_graph)[i])[j]; } void SimGraph::set_ptr(int i, AbstractAccess & aa) { (*_ptrs)[i] = aa; }

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