source: src/Tuples/TupleAssignment.cc@ 906e24d

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new stuck-waitfor-destruct with_gc
Last change on this file since 906e24d was 906e24d, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

replace results list on Expressions with a single Type field
  • Property mode set to 100644
File size: 14.0 KB
RevLine 
[51587aa]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//
[906e24d]7// TupleAssignment.cc --
[51587aa]8//
[843054c2]9// Author : Rodolfo G. Esteves
[51587aa]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
[51b73452]16#include "ResolvExpr/AlternativeFinder.h"
17#include "ResolvExpr/Alternative.h"
18#include "ResolvExpr/typeops.h"
19#include "SynTree/Expression.h"
20#include "TupleAssignment.h"
[d3b7937]21#include "Common/SemanticError.h"
[51b73452]22
23#include <functional>
24#include <algorithm>
25#include <iterator>
26#include <iostream>
27#include <cassert>
28#include <set>
29
30namespace Tuples {
[51587aa]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;
[a08ba92]66 if ( ! matcher->match(new_assigns) )
[51587aa]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 ) {
[906e24d]127 return isTuple( expr );
[51587aa]128 }
129
130 bool TupleAssignSpotter::isTupleAssignment( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
131 if ( NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) {
132
133 if ( assgnop->get_name() == std::string("?=?") ) {
134
135 for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
136 assert( ali->size() == 2 );
137 ResolvExpr::AltList::iterator opit = ali->begin();
138 ResolvExpr::Alternative op1 = *opit, op2 = *(++opit);
139
140 if ( pointsToTuple(op1.expr) ) { // also handles tuple vars
141 if ( isTuple( op2.expr, true ) )
142 matcher = new MultipleAssignMatcher(op1.expr, op2.expr);
143 else if ( isMVR( op2.expr ) ) {
144 // handle MVR differently
145 } else
146 // mass assignment
147 matcher = new MassAssignMatcher(op1.expr, op2.expr);
148
149 std::list< ResolvExpr::AltList > options;
150 if ( match() )
151 /*
152 if ( hasMatched ) {
153 // throw SemanticError("Ambiguous tuple assignment");
154 } else {*/
155 // Matched for the first time
156 hasMatched = true;
157 /*} */
158 } /* else if ( isTuple( op2 ) )
159 throw SemanticError("Inapplicable tuple assignment.");
160 */
161 }
162
163 if ( hasMatched ) {
164 if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) {
165 //options.print( std::cerr );
166 std::list< ResolvExpr::AltList >best = options.get_best();
167 if ( best.size() == 1 ) {
168 std::list<Expression *> solved_assigns;
[a08ba92]169 for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) {
[51587aa]170 solved_assigns.push_back( i->expr );
171 }
172 /* assigning cost zero? */
173 currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MULTIPLE*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
174 }
175 } else {
[a08ba92]176 assert( ! optMass.empty() );
[51587aa]177 ResolvExpr::AltList winners;
178 for ( std::vector< ResolvExpr::AltList >::iterator i = optMass.begin(); i != optMass.end(); ++i )
179 findMinCostAlt( i->begin(), i->end(), back_inserter(winners) );
180
181 std::list< Expression *> solved_assigns;
182 for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i )
183 solved_assigns.push_back( i->expr );
184 currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MASS*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
185 }
186 }
187 }
188 }
189 return hasMatched;
190 }
191
192 void TupleAssignSpotter::Matcher::init( Expression *_lhs, Expression *_rhs ) {
193 lhs.clear();
194 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(_lhs) )
195 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) )
196 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(lhs) );
197
198 rhs.clear();
199 }
200
201 TupleAssignSpotter::Matcher::Matcher( /*TupleAssignSpotter &spot,*/ Expression *_lhs, Expression *_rhs ) /*: own_spotter(spot) */{
202 init(_lhs,_rhs);
203 }
204
205 TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( Expression *_lhs, Expression *_rhs )/* : own_spotter(spot) */{
206 init(_lhs,_rhs);
207
208 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(_rhs) )
209 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(rhs) );
210 }
211
212 UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) {
213 if ( left && right ) {
214 std::list< Expression * > args;
215 args.push_back(new AddressExpr(left->clone())); args.push_back(right->clone());
216 return new UntypedExpr(new NameExpr("?=?"), args);
217 } else
218 throw 0; // xxx - diagnose the problem
219 }
220
221 bool TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
222 if ( lhs.empty() || (rhs.size() != 1) ) return false;
223
224 for ( std::list< Expression * >::iterator l = lhs.begin(); l != lhs.end(); l++ ) {
225 std::list< Expression * > args;
226 args.push_back( new AddressExpr(*l) );
227 args.push_back( rhs.front() );
228 out.push_back( new UntypedExpr(new NameExpr("?=?"), args) );
229 }
230
231 return true;
232 }
233
234 bool TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) {
235 /*
236 std::list< Expression * > solved_assigns;
237 ResolvExpr::AltList solved_alts;
238 assert( currentFinder != 0 );
239
240 ResolvExpr::AltList current;
241 if ( optMass.empty() ) {
242 for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i )
243 optMass.push_back( ResolvExpr::AltList() );
244 }
245 int cnt = 0;
246 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) {
247
248 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
249 finder.findWithAdjustment(*i);
250 ResolvExpr::AltList alts = finder.get_alternatives();
251 assert( alts.size() == 1 );
252 assert(alts.front().expr != 0 );
253 current.push_back( finder.get_alternatives().front() );
254 optMass[cnt].push_back( finder.get_alternatives().front() );
255 solved_assigns.push_back( alts.front().expr->clone() );
256 }
257 */
258 return true;
[51b73452]259 }
260
[51587aa]261 bool TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
262 // need more complicated matching
263 if ( lhs.size() == rhs.size() ) {
264 zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn );
265 return true;
266 } //else
267 //std::cerr << "The length of (left, right) is: (" << lhs.size() << "," << rhs.size() << ")" << std::endl;*/
268 return false;
[51b73452]269 }
270
[51587aa]271 bool TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) {
272 /*
273 std::list< Expression * > solved_assigns;
274 ResolvExpr::AltList solved_alts;
275 assert( currentFinder != 0 );
276
277 ResolvExpr::AltList current;
278 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
279 //try {
280 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
281 finder.findWithAdjustment(*i);
282 // prune expressions that don't coincide with
283 ResolvExpr::AltList alts = finder.get_alternatives();
284 assert( alts.size() == 1 );
285 assert(alts.front().expr != 0 );
286 current.push_back( finder.get_alternatives().front() );
287 solved_assigns.push_back( alts.front().expr->clone() );
288 //solved_assigns.back()->print(std::cerr);
289 //} catch( ... ) {
290 //continue; // no reasonable alternative found
291 //}
292 }
293 options.add_option( current );
294 */
295
296 return true;
297 }
298
299 void TupleAssignSpotter::Options::add_option( ResolvExpr::AltList &opt ) {
300 using namespace std;
301
302 options.push_back( opt );
303 /*
304 vector< Cost > costs;
305 costs.reserve( opt.size() );
306 transform( opt.begin(), opt.end(), back_inserter(costs), ptr_fun(extract_cost) );
307 */
308 // transpose matrix
309 if ( costMatrix.empty() )
310 for ( unsigned int i = 0; i< opt.size(); ++i)
311 costMatrix.push_back( vector<ResolvExpr::Cost>() );
312
313 int cnt = 0;
314 for ( ResolvExpr::AltList::iterator i = opt.begin(); i != opt.end(); ++i, cnt++ )
315 costMatrix[cnt].push_back( i->cost );
316
317 return;
318 }
[51b73452]319
[51587aa]320 std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() {
321 using namespace std;
322 using namespace ResolvExpr;
323 list< ResolvExpr::AltList > ret;
324 list< multiset<int> > solns;
325 for ( vector< vector<Cost> >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
326 list<int> current;
327 findMinCost( i->begin(), i->end(), back_inserter(current) );
328 solns.push_back( multiset<int>(current.begin(), current.end()) );
329 }
330 // need to combine
331 multiset<int> result;
332 lift_intersection( solns.begin(), solns.end(), inserter( result, result.begin() ) );
333 if ( result.size() != 1 )
334 throw SemanticError("Ambiguous tuple expression");
335 ret.push_back(get_option( *(result.begin() )));
336 return ret;
337 }
338
339 void TupleAssignSpotter::Options::print( std::ostream &ostr ) {
340 using namespace std;
341
342 for ( vector< vector < ResolvExpr::Cost > >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
343 for ( vector < ResolvExpr::Cost >::iterator j = i->begin(); j != i->end(); ++j )
344 ostr << *j << " " ;
345 ostr << std::endl;
346 } // for
347 return;
348 }
349
350 ResolvExpr::Cost extract_cost( ResolvExpr::Alternative &alt ) {
351 return alt.cost;
352 }
353
354 template< typename InputIterator, typename OutputIterator >
355 void TupleAssignSpotter::Options::findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) {
356 using namespace ResolvExpr;
357 std::list<int> alternatives;
358
359 // select the alternatives that have the minimum parameter cost
360 Cost minCost = Cost::infinity;
361 unsigned int index = 0;
362 for ( InputIterator i = begin; i != end; ++i, index++ ) {
363 if ( *i < minCost ) {
364 minCost = *i;
365 alternatives.clear();
366 alternatives.push_back( index );
367 } else if ( *i == minCost ) {
368 alternatives.push_back( index );
369 }
370 }
371 std::copy( alternatives.begin(), alternatives.end(), out );
372 }
373
374 template< class InputIterator, class OutputIterator >
[a08ba92]375 void TupleAssignSpotter::Options::lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ) {
[51587aa]376 if ( begin == end ) return;
377 InputIterator test = begin;
378
379 if (++test == end)
380 { copy(begin->begin(), begin->end(), out); return; }
381
382
383 std::multiset<int> cur; // InputIterator::value_type::value_type
384 copy( begin->begin(), begin->end(), inserter( cur, cur.begin() ) );
385
386 while ( test != end ) {
387 std::multiset<int> temp;
388 set_intersection( cur.begin(), cur.end(), test->begin(), test->end(), inserter(temp,temp.begin()) );
389 cur.clear();
390 copy( temp.begin(), temp.end(), inserter(cur,cur.begin()));
391 ++test;
392 }
393
394 copy( cur.begin(), cur.end(), out );
395 return;
396 }
397
398 ResolvExpr::AltList TupleAssignSpotter::Options::get_option( std::list< ResolvExpr::AltList >::size_type index ) {
399 if ( index >= options.size() )
400 throw 0; // XXX
401 std::list< ResolvExpr::AltList >::iterator it = options.begin();
402 for ( std::list< ResolvExpr::AltList >::size_type i = 0; i < index; ++i, ++it );
403 return *it;
404 }
[51b73452]405} // namespace Tuples
[51587aa]406
407// Local Variables: //
408// tab-width: 4 //
409// mode: c++ //
410// compile-command: "make install" //
411// End: //
Note: See TracBrowser for help on using the repository browser.