source: src/Tuples/TupleAssignment.cc @ be945ac

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since be945ac was d3b7937, checked in by Peter A. Buhr <pabuhr@…>, 9 years ago

building runtime library (first attempt)

  • Property mode set to 100644
File size: 14.1 KB
Line 
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           : Rodolfo G. Esteves
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
16#include "ResolvExpr/AlternativeFinder.h"
17#include "ResolvExpr/Alternative.h"
18#include "ResolvExpr/typeops.h"
19#include "SynTree/Expression.h"
20#include "TupleAssignment.h"
21#include "Common/SemanticError.h"
22
23#include <functional>
24#include <algorithm>
25#include <iterator>
26#include <iostream>
27#include <cassert>
28#include <set>
29
30namespace Tuples {
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        }
409} // namespace Tuples
410
411// Local Variables: //
412// tab-width: 4 //
413// mode: c++ //
414// compile-command: "make install" //
415// End: //
Note: See TracBrowser for help on using the repository browser.