Changeset 51587aa for translator/Tuples/TupleAssignment.cc
- Timestamp:
- May 18, 2015, 11:45:33 PM (9 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, gc_noraii, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, string, with_gc
- Children:
- 01aeade
- Parents:
- 0dd3a2f
- File:
-
- 1 edited
-
translator/Tuples/TupleAssignment.cc (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
translator/Tuples/TupleAssignment.cc
r0dd3a2f r51587aa 1 // 2 // Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo 3 // 4 // The contents of this file are covered under the licence agreement in the 5 // file "LICENCE" distributed with Cforall. 6 // 7 // TupleAssignment.cc -- 8 // 9 // Author : Richard C. Bilson 10 // Created On : Mon May 18 07:44:20 2015 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon May 18 15:02:53 2015 13 // Update Count : 2 14 // 15 1 16 #include "ResolvExpr/AlternativeFinder.h" 2 17 #include "ResolvExpr/Alternative.h" … … 14 29 15 30 namespace Tuples { 16 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder *f = 0 ) 17 : currentFinder(f), matcher(0), hasMatched( false ) {} 18 19 bool TupleAssignSpotter::pointsToTuple( Expression *expr ) { 20 // also check for function returning tuple of reference types 21 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(expr) ) 22 if ( isTuple(addr->get_arg() ) ) 23 return true; 24 return false; 25 } 26 27 bool TupleAssignSpotter::isTupleVar( DeclarationWithType *decl ) { 28 if ( dynamic_cast<TupleType *>(decl->get_type()) ) 29 return true; 30 return false; 31 } 32 33 bool TupleAssignSpotter::isTuple( Expression *expr, bool isRight ) { 34 // true if `expr' is an expression returning a tuple: tuple, tuple variable or MRV function 35 if ( ! expr ) return false; 36 37 if ( dynamic_cast<TupleExpr *>(expr) ) 38 return true; 39 else if ( VariableExpr *var = dynamic_cast<VariableExpr *>(expr) ) { 40 if ( isTupleVar(var->get_var()) ) 41 return true; 42 } 43 44 return false; 45 } 46 47 bool TupleAssignSpotter::match() { 48 assert ( matcher != 0 ); 49 50 std::list< Expression * > new_assigns; 51 if (! matcher->match(new_assigns) ) 52 return false; 53 54 if ( new_assigns.empty() ) return false; 55 /*return */matcher->solve( new_assigns ); 56 if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) { 57 // now resolve new assignments 58 std::list< Expression * > solved_assigns; 59 ResolvExpr::AltList solved_alts; 60 assert( currentFinder != 0 ); 61 62 ResolvExpr::AltList current; 63 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { 64 //try { 65 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 66 finder.findWithAdjustment(*i); 67 // prune expressions that don't coincide with 68 ResolvExpr::AltList alts = finder.get_alternatives(); 69 assert( alts.size() == 1 ); 70 assert(alts.front().expr != 0 ); 71 current.push_back( finder.get_alternatives().front() ); 72 solved_assigns.push_back( alts.front().expr->clone() ); 73 //solved_assigns.back()->print(std::cerr); 74 /*} catch( ... ) { 75 continue; // no reasonable alternative found 76 }*/ 77 } 78 options.add_option( current ); 79 80 return true; 81 } else { // mass assignment 82 //if ( new_assigns.empty() ) return false; 83 std::list< Expression * > solved_assigns; 84 ResolvExpr::AltList solved_alts; 85 assert( currentFinder != 0 ); 86 87 ResolvExpr::AltList current; 88 if ( optMass.empty() ) { 89 for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i ) 90 optMass.push_back( ResolvExpr::AltList() ); 91 } 92 int cnt = 0; 93 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) { 94 95 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 96 finder.findWithAdjustment(*i); 97 ResolvExpr::AltList alts = finder.get_alternatives(); 98 assert( alts.size() == 1 ); 99 assert(alts.front().expr != 0 ); 100 current.push_back( finder.get_alternatives().front() ); 101 optMass[cnt].push_back( finder.get_alternatives().front() ); 102 solved_assigns.push_back( alts.front().expr->clone() ); 103 } 104 105 return true; 106 } 107 108 return false; 109 } 110 111 bool TupleAssignSpotter::isMVR( Expression *expr ) { 112 if ( expr->get_results().size() > 1 ) { 113 // MVR processing 114 return true; 115 } 116 return false; 117 } 118 119 bool TupleAssignSpotter::isTupleAssignment( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) { 120 if ( NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) { 121 122 if ( assgnop->get_name() == std::string("?=?") ) { 123 124 for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) { 125 assert( ali->size() == 2 ); 126 ResolvExpr::AltList::iterator opit = ali->begin(); 127 ResolvExpr::Alternative op1 = *opit, op2 = *(++opit); 128 129 if ( pointsToTuple(op1.expr) ) { // also handles tuple vars 130 if ( isTuple( op2.expr, true ) ) 131 matcher = new MultipleAssignMatcher(op1.expr, op2.expr); 132 else if ( isMVR( op2.expr ) ) { 133 // handle MVR differently 134 } else 135 // mass assignment 136 matcher = new MassAssignMatcher(op1.expr, op2.expr); 137 138 std::list< ResolvExpr::AltList > options; 139 if ( match() ) 140 /* 141 if ( hasMatched ) { 142 // throw SemanticError("Ambiguous tuple assignment"); 143 } else {*/ 144 // Matched for the first time 145 hasMatched = true; 146 /*} */ 147 } /* else if ( isTuple( op2 ) ) 148 throw SemanticError("Inapplicable tuple assignment."); 149 */ 150 } 151 152 if ( hasMatched ) { 153 if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) { 154 //options.print( std::cerr ); 155 std::list< ResolvExpr::AltList >best = options.get_best(); 156 if ( best.size() == 1 ) { 157 std::list<Expression *> solved_assigns; 158 for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ){ 159 solved_assigns.push_back( i->expr ); 160 } 161 /* assigning cost zero? */ 162 currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MULTIPLE*/), currentFinder->get_environ(), ResolvExpr::Cost() ) ); 163 } 164 } else { 165 assert(! optMass.empty() ); 166 ResolvExpr::AltList winners; 167 for ( std::vector< ResolvExpr::AltList >::iterator i = optMass.begin(); i != optMass.end(); ++i ) 168 findMinCostAlt( i->begin(), i->end(), back_inserter(winners) ); 169 170 std::list< Expression *> solved_assigns; 171 for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i ) 172 solved_assigns.push_back( i->expr ); 173 currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MASS*/), currentFinder->get_environ(), ResolvExpr::Cost() ) ); 174 } 175 } 176 } 177 } 178 return hasMatched; 179 } 180 181 void TupleAssignSpotter::Matcher::init( Expression *_lhs, Expression *_rhs ) { 182 lhs.clear(); 183 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(_lhs) ) 184 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) ) 185 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(lhs) ); 186 187 rhs.clear(); 188 } 189 190 TupleAssignSpotter::Matcher::Matcher( /*TupleAssignSpotter &spot,*/ Expression *_lhs, Expression *_rhs ) /*: own_spotter(spot) */{ 191 init(_lhs,_rhs); 192 } 193 194 TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( Expression *_lhs, Expression *_rhs )/* : own_spotter(spot) */{ 195 init(_lhs,_rhs); 196 197 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(_rhs) ) 198 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(rhs) ); 199 } 200 201 UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) { 202 if ( left && right ) { 203 std::list< Expression * > args; 204 args.push_back(new AddressExpr(left->clone())); args.push_back(right->clone()); 205 return new UntypedExpr(new NameExpr("?=?"), args); 206 } else 207 throw 0; // xxx - diagnose the problem 208 } 209 210 bool TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) { 211 if ( lhs.empty() || (rhs.size() != 1) ) return false; 212 213 for ( std::list< Expression * >::iterator l = lhs.begin(); l != lhs.end(); l++ ) { 214 std::list< Expression * > args; 215 args.push_back( new AddressExpr(*l) ); 216 args.push_back( rhs.front() ); 217 out.push_back( new UntypedExpr(new NameExpr("?=?"), args) ); 218 } 219 220 return true; 221 } 222 223 bool TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) { 224 /* 225 std::list< Expression * > solved_assigns; 226 ResolvExpr::AltList solved_alts; 227 assert( currentFinder != 0 ); 228 229 ResolvExpr::AltList current; 230 if ( optMass.empty() ) { 231 for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i ) 232 optMass.push_back( ResolvExpr::AltList() ); 233 } 234 int cnt = 0; 235 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) { 236 237 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 238 finder.findWithAdjustment(*i); 239 ResolvExpr::AltList alts = finder.get_alternatives(); 240 assert( alts.size() == 1 ); 241 assert(alts.front().expr != 0 ); 242 current.push_back( finder.get_alternatives().front() ); 243 optMass[cnt].push_back( finder.get_alternatives().front() ); 244 solved_assigns.push_back( alts.front().expr->clone() ); 245 } 246 */ 247 return true; 248 } 249 250 bool TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) { 251 // need more complicated matching 252 if ( lhs.size() == rhs.size() ) { 253 zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn ); 254 return true; 255 } //else 256 //std::cerr << "The length of (left, right) is: (" << lhs.size() << "," << rhs.size() << ")" << std::endl;*/ 257 return false; 258 } 259 260 bool TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) { 261 /* 262 std::list< Expression * > solved_assigns; 263 ResolvExpr::AltList solved_alts; 264 assert( currentFinder != 0 ); 265 266 ResolvExpr::AltList current; 267 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { 268 //try { 269 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 270 finder.findWithAdjustment(*i); 271 // prune expressions that don't coincide with 272 ResolvExpr::AltList alts = finder.get_alternatives(); 273 assert( alts.size() == 1 ); 274 assert(alts.front().expr != 0 ); 275 current.push_back( finder.get_alternatives().front() ); 276 solved_assigns.push_back( alts.front().expr->clone() ); 277 //solved_assigns.back()->print(std::cerr); 278 //} catch( ... ) { 279 //continue; // no reasonable alternative found 280 //} 281 } 282 options.add_option( current ); 283 */ 284 285 return true; 286 } 287 288 void TupleAssignSpotter::Options::add_option( ResolvExpr::AltList &opt ) { 289 using namespace std; 290 291 options.push_back( opt ); 292 /* 293 vector< Cost > costs; 294 costs.reserve( opt.size() ); 295 transform( opt.begin(), opt.end(), back_inserter(costs), ptr_fun(extract_cost) ); 296 */ 297 // transpose matrix 298 if ( costMatrix.empty() ) 299 for ( unsigned int i = 0; i< opt.size(); ++i) 300 costMatrix.push_back( vector<ResolvExpr::Cost>() ); 301 302 int cnt = 0; 303 for ( ResolvExpr::AltList::iterator i = opt.begin(); i != opt.end(); ++i, cnt++ ) 304 costMatrix[cnt].push_back( i->cost ); 305 306 return; 307 } 308 309 std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() { 310 using namespace std; 311 using namespace ResolvExpr; 312 list< ResolvExpr::AltList > ret; 313 list< multiset<int> > solns; 314 for ( vector< vector<Cost> >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) { 315 list<int> current; 316 findMinCost( i->begin(), i->end(), back_inserter(current) ); 317 solns.push_back( multiset<int>(current.begin(), current.end()) ); 318 } 319 // need to combine 320 multiset<int> result; 321 lift_intersection( solns.begin(), solns.end(), inserter( result, result.begin() ) ); 322 if ( result.size() != 1 ) 323 throw SemanticError("Ambiguous tuple expression"); 324 ret.push_back(get_option( *(result.begin() ))); 325 return ret; 326 } 327 328 void TupleAssignSpotter::Options::print( std::ostream &ostr ) { 329 using namespace std; 330 331 for ( vector< vector < ResolvExpr::Cost > >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) { 332 for ( vector < ResolvExpr::Cost >::iterator j = i->begin(); j != i->end(); ++j ) 333 ostr << *j << " " ; 334 ostr << std::endl; 335 } 336 337 return; 338 } 339 340 ResolvExpr::Cost extract_cost( ResolvExpr::Alternative &alt ) { 341 return alt.cost; 342 } 343 344 template< typename InputIterator, typename OutputIterator > 345 void 346 TupleAssignSpotter::Options::findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) 347 { 348 using namespace ResolvExpr; 349 std::list<int> alternatives; 350 351 // select the alternatives that have the minimum parameter cost 352 Cost minCost = Cost::infinity; 353 unsigned int index = 0; 354 for ( InputIterator i = begin; i != end; ++i, index++ ) { 355 if ( *i < minCost ) { 356 minCost = *i; 357 alternatives.clear(); 358 alternatives.push_back( index ); 359 } else if ( *i == minCost ) { 360 alternatives.push_back( index ); 361 } 362 } 363 std::copy( alternatives.begin(), alternatives.end(), out ); 364 } 365 366 template< class InputIterator, class OutputIterator > 367 void TupleAssignSpotter::Options::lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ){ 368 if ( begin == end ) return; 369 InputIterator test = begin; 370 371 if (++test == end) 372 { copy(begin->begin(), begin->end(), out); return; } 373 374 375 std::multiset<int> cur; // InputIterator::value_type::value_type 376 copy( begin->begin(), begin->end(), inserter( cur, cur.begin() ) ); 377 378 while ( test != end ) { 379 std::multiset<int> temp; 380 set_intersection( cur.begin(), cur.end(), test->begin(), test->end(), inserter(temp,temp.begin()) ); 381 cur.clear(); 382 copy( temp.begin(), temp.end(), inserter(cur,cur.begin())); 383 ++test; 384 } 385 386 copy( cur.begin(), cur.end(), out ); 387 return; 388 } 389 390 391 ResolvExpr::AltList TupleAssignSpotter::Options::get_option( std::list< ResolvExpr::AltList >::size_type index ) { 392 if ( index >= options.size() ) 393 throw 0; // XXX 394 std::list< ResolvExpr::AltList >::iterator it = options.begin(); 395 for ( std::list< ResolvExpr::AltList >::size_type i = 0; i < index; ++i, ++it ); 396 return *it; 397 } 398 399 31 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder *f = 0 ) 32 : currentFinder(f), matcher(0), hasMatched( false ) {} 33 34 bool TupleAssignSpotter::pointsToTuple( Expression *expr ) { 35 // also check for function returning tuple of reference types 36 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(expr) ) 37 if ( isTuple(addr->get_arg() ) ) 38 return true; 39 return false; 40 } 41 42 bool TupleAssignSpotter::isTupleVar( DeclarationWithType *decl ) { 43 if ( dynamic_cast<TupleType *>(decl->get_type()) ) 44 return true; 45 return false; 46 } 47 48 bool TupleAssignSpotter::isTuple( Expression *expr, bool isRight ) { 49 // true if `expr' is an expression returning a tuple: tuple, tuple variable or MRV function 50 if ( ! expr ) return false; 51 52 if ( dynamic_cast<TupleExpr *>(expr) ) 53 return true; 54 else if ( VariableExpr *var = dynamic_cast<VariableExpr *>(expr) ) { 55 if ( isTupleVar(var->get_var()) ) 56 return true; 57 } 58 59 return false; 60 } 61 62 bool TupleAssignSpotter::match() { 63 assert ( matcher != 0 ); 64 65 std::list< Expression * > new_assigns; 66 if (! matcher->match(new_assigns) ) 67 return false; 68 69 if ( new_assigns.empty() ) return false; 70 /*return */matcher->solve( new_assigns ); 71 if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) { 72 // now resolve new assignments 73 std::list< Expression * > solved_assigns; 74 ResolvExpr::AltList solved_alts; 75 assert( currentFinder != 0 ); 76 77 ResolvExpr::AltList current; 78 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { 79 //try { 80 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 81 finder.findWithAdjustment(*i); 82 // prune expressions that don't coincide with 83 ResolvExpr::AltList alts = finder.get_alternatives(); 84 assert( alts.size() == 1 ); 85 assert(alts.front().expr != 0 ); 86 current.push_back( finder.get_alternatives().front() ); 87 solved_assigns.push_back( alts.front().expr->clone() ); 88 //solved_assigns.back()->print(std::cerr); 89 /*} catch( ... ) { 90 continue; // no reasonable alternative found 91 }*/ 92 } 93 options.add_option( current ); 94 95 return true; 96 } else { // mass assignment 97 //if ( new_assigns.empty() ) return false; 98 std::list< Expression * > solved_assigns; 99 ResolvExpr::AltList solved_alts; 100 assert( currentFinder != 0 ); 101 102 ResolvExpr::AltList current; 103 if ( optMass.empty() ) { 104 for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i ) 105 optMass.push_back( ResolvExpr::AltList() ); 106 } 107 int cnt = 0; 108 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) { 109 110 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 111 finder.findWithAdjustment(*i); 112 ResolvExpr::AltList alts = finder.get_alternatives(); 113 assert( alts.size() == 1 ); 114 assert(alts.front().expr != 0 ); 115 current.push_back( finder.get_alternatives().front() ); 116 optMass[cnt].push_back( finder.get_alternatives().front() ); 117 solved_assigns.push_back( alts.front().expr->clone() ); 118 } 119 120 return true; 121 } 122 123 return false; 124 } 125 126 bool TupleAssignSpotter::isMVR( Expression *expr ) { 127 if ( expr->get_results().size() > 1 ) { 128 // MVR processing 129 return true; 130 } 131 return false; 132 } 133 134 bool TupleAssignSpotter::isTupleAssignment( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) { 135 if ( NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) { 136 137 if ( assgnop->get_name() == std::string("?=?") ) { 138 139 for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) { 140 assert( ali->size() == 2 ); 141 ResolvExpr::AltList::iterator opit = ali->begin(); 142 ResolvExpr::Alternative op1 = *opit, op2 = *(++opit); 143 144 if ( pointsToTuple(op1.expr) ) { // also handles tuple vars 145 if ( isTuple( op2.expr, true ) ) 146 matcher = new MultipleAssignMatcher(op1.expr, op2.expr); 147 else if ( isMVR( op2.expr ) ) { 148 // handle MVR differently 149 } else 150 // mass assignment 151 matcher = new MassAssignMatcher(op1.expr, op2.expr); 152 153 std::list< ResolvExpr::AltList > options; 154 if ( match() ) 155 /* 156 if ( hasMatched ) { 157 // throw SemanticError("Ambiguous tuple assignment"); 158 } else {*/ 159 // Matched for the first time 160 hasMatched = true; 161 /*} */ 162 } /* else if ( isTuple( op2 ) ) 163 throw SemanticError("Inapplicable tuple assignment."); 164 */ 165 } 166 167 if ( hasMatched ) { 168 if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) { 169 //options.print( std::cerr ); 170 std::list< ResolvExpr::AltList >best = options.get_best(); 171 if ( best.size() == 1 ) { 172 std::list<Expression *> solved_assigns; 173 for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ){ 174 solved_assigns.push_back( i->expr ); 175 } 176 /* assigning cost zero? */ 177 currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MULTIPLE*/), currentFinder->get_environ(), ResolvExpr::Cost() ) ); 178 } 179 } else { 180 assert(! optMass.empty() ); 181 ResolvExpr::AltList winners; 182 for ( std::vector< ResolvExpr::AltList >::iterator i = optMass.begin(); i != optMass.end(); ++i ) 183 findMinCostAlt( i->begin(), i->end(), back_inserter(winners) ); 184 185 std::list< Expression *> solved_assigns; 186 for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i ) 187 solved_assigns.push_back( i->expr ); 188 currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MASS*/), currentFinder->get_environ(), ResolvExpr::Cost() ) ); 189 } 190 } 191 } 192 } 193 return hasMatched; 194 } 195 196 void TupleAssignSpotter::Matcher::init( Expression *_lhs, Expression *_rhs ) { 197 lhs.clear(); 198 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(_lhs) ) 199 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) ) 200 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(lhs) ); 201 202 rhs.clear(); 203 } 204 205 TupleAssignSpotter::Matcher::Matcher( /*TupleAssignSpotter &spot,*/ Expression *_lhs, Expression *_rhs ) /*: own_spotter(spot) */{ 206 init(_lhs,_rhs); 207 } 208 209 TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( Expression *_lhs, Expression *_rhs )/* : own_spotter(spot) */{ 210 init(_lhs,_rhs); 211 212 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(_rhs) ) 213 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(rhs) ); 214 } 215 216 UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) { 217 if ( left && right ) { 218 std::list< Expression * > args; 219 args.push_back(new AddressExpr(left->clone())); args.push_back(right->clone()); 220 return new UntypedExpr(new NameExpr("?=?"), args); 221 } else 222 throw 0; // xxx - diagnose the problem 223 } 224 225 bool TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) { 226 if ( lhs.empty() || (rhs.size() != 1) ) return false; 227 228 for ( std::list< Expression * >::iterator l = lhs.begin(); l != lhs.end(); l++ ) { 229 std::list< Expression * > args; 230 args.push_back( new AddressExpr(*l) ); 231 args.push_back( rhs.front() ); 232 out.push_back( new UntypedExpr(new NameExpr("?=?"), args) ); 233 } 234 235 return true; 236 } 237 238 bool TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) { 239 /* 240 std::list< Expression * > solved_assigns; 241 ResolvExpr::AltList solved_alts; 242 assert( currentFinder != 0 ); 243 244 ResolvExpr::AltList current; 245 if ( optMass.empty() ) { 246 for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i ) 247 optMass.push_back( ResolvExpr::AltList() ); 248 } 249 int cnt = 0; 250 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) { 251 252 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 253 finder.findWithAdjustment(*i); 254 ResolvExpr::AltList alts = finder.get_alternatives(); 255 assert( alts.size() == 1 ); 256 assert(alts.front().expr != 0 ); 257 current.push_back( finder.get_alternatives().front() ); 258 optMass[cnt].push_back( finder.get_alternatives().front() ); 259 solved_assigns.push_back( alts.front().expr->clone() ); 260 } 261 */ 262 return true; 263 } 264 265 bool TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) { 266 // need more complicated matching 267 if ( lhs.size() == rhs.size() ) { 268 zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn ); 269 return true; 270 } //else 271 //std::cerr << "The length of (left, right) is: (" << lhs.size() << "," << rhs.size() << ")" << std::endl;*/ 272 return false; 273 } 274 275 bool TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) { 276 /* 277 std::list< Expression * > solved_assigns; 278 ResolvExpr::AltList solved_alts; 279 assert( currentFinder != 0 ); 280 281 ResolvExpr::AltList current; 282 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { 283 //try { 284 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); 285 finder.findWithAdjustment(*i); 286 // prune expressions that don't coincide with 287 ResolvExpr::AltList alts = finder.get_alternatives(); 288 assert( alts.size() == 1 ); 289 assert(alts.front().expr != 0 ); 290 current.push_back( finder.get_alternatives().front() ); 291 solved_assigns.push_back( alts.front().expr->clone() ); 292 //solved_assigns.back()->print(std::cerr); 293 //} catch( ... ) { 294 //continue; // no reasonable alternative found 295 //} 296 } 297 options.add_option( current ); 298 */ 299 300 return true; 301 } 302 303 void TupleAssignSpotter::Options::add_option( ResolvExpr::AltList &opt ) { 304 using namespace std; 305 306 options.push_back( opt ); 307 /* 308 vector< Cost > costs; 309 costs.reserve( opt.size() ); 310 transform( opt.begin(), opt.end(), back_inserter(costs), ptr_fun(extract_cost) ); 311 */ 312 // transpose matrix 313 if ( costMatrix.empty() ) 314 for ( unsigned int i = 0; i< opt.size(); ++i) 315 costMatrix.push_back( vector<ResolvExpr::Cost>() ); 316 317 int cnt = 0; 318 for ( ResolvExpr::AltList::iterator i = opt.begin(); i != opt.end(); ++i, cnt++ ) 319 costMatrix[cnt].push_back( i->cost ); 320 321 return; 322 } 323 324 std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() { 325 using namespace std; 326 using namespace ResolvExpr; 327 list< ResolvExpr::AltList > ret; 328 list< multiset<int> > solns; 329 for ( vector< vector<Cost> >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) { 330 list<int> current; 331 findMinCost( i->begin(), i->end(), back_inserter(current) ); 332 solns.push_back( multiset<int>(current.begin(), current.end()) ); 333 } 334 // need to combine 335 multiset<int> result; 336 lift_intersection( solns.begin(), solns.end(), inserter( result, result.begin() ) ); 337 if ( result.size() != 1 ) 338 throw SemanticError("Ambiguous tuple expression"); 339 ret.push_back(get_option( *(result.begin() ))); 340 return ret; 341 } 342 343 void TupleAssignSpotter::Options::print( std::ostream &ostr ) { 344 using namespace std; 345 346 for ( vector< vector < ResolvExpr::Cost > >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) { 347 for ( vector < ResolvExpr::Cost >::iterator j = i->begin(); j != i->end(); ++j ) 348 ostr << *j << " " ; 349 ostr << std::endl; 350 } // for 351 return; 352 } 353 354 ResolvExpr::Cost extract_cost( ResolvExpr::Alternative &alt ) { 355 return alt.cost; 356 } 357 358 template< typename InputIterator, typename OutputIterator > 359 void TupleAssignSpotter::Options::findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) { 360 using namespace ResolvExpr; 361 std::list<int> alternatives; 362 363 // select the alternatives that have the minimum parameter cost 364 Cost minCost = Cost::infinity; 365 unsigned int index = 0; 366 for ( InputIterator i = begin; i != end; ++i, index++ ) { 367 if ( *i < minCost ) { 368 minCost = *i; 369 alternatives.clear(); 370 alternatives.push_back( index ); 371 } else if ( *i == minCost ) { 372 alternatives.push_back( index ); 373 } 374 } 375 std::copy( alternatives.begin(), alternatives.end(), out ); 376 } 377 378 template< class InputIterator, class OutputIterator > 379 void TupleAssignSpotter::Options::lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ){ 380 if ( begin == end ) return; 381 InputIterator test = begin; 382 383 if (++test == end) 384 { copy(begin->begin(), begin->end(), out); return; } 385 386 387 std::multiset<int> cur; // InputIterator::value_type::value_type 388 copy( begin->begin(), begin->end(), inserter( cur, cur.begin() ) ); 389 390 while ( test != end ) { 391 std::multiset<int> temp; 392 set_intersection( cur.begin(), cur.end(), test->begin(), test->end(), inserter(temp,temp.begin()) ); 393 cur.clear(); 394 copy( temp.begin(), temp.end(), inserter(cur,cur.begin())); 395 ++test; 396 } 397 398 copy( cur.begin(), cur.end(), out ); 399 return; 400 } 401 402 ResolvExpr::AltList TupleAssignSpotter::Options::get_option( std::list< ResolvExpr::AltList >::size_type index ) { 403 if ( index >= options.size() ) 404 throw 0; // XXX 405 std::list< ResolvExpr::AltList >::iterator it = options.begin(); 406 for ( std::list< ResolvExpr::AltList >::size_type i = 0; i < index; ++i, ++it ); 407 return *it; 408 } 400 409 } // namespace Tuples 410 411 // Local Variables: // 412 // tab-width: 4 // 413 // mode: c++ // 414 // compile-command: "make install" // 415 // End: //
Note: See TracChangeset
for help on using the changeset viewer.
