Index: src/Tuples/NameMatcher.cc =================================================================== --- src/Tuples/NameMatcher.cc (revision 906e24deeab82aafdd4cbb08fb896c8ffe5b99e0) +++ (revision ) @@ -1,67 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// NameMatcher.cc -- -// -// Author : Rodolfo G. Esteves -// Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Mon May 18 15:00:06 2015 -// Update Count : 1 -// - -#include "NameMatcher.h" -#include "NameMatcher.h" - -namespace Tuples { - NameMatcher::NameMatcher( std::list< DeclarationWithType* > &formals ) : current( 0 ) { - int cnt = 0; - for ( std::list< DeclarationWithType *>::const_iterator f = formals.begin(); f != formals.end(); ++f ) { - table.insert( std::pair< std::string, int >( (*f)->get_name(), cnt++ ) ); - index.push_back(*f); - } // for - exprs.reserve( index.size() ); - } - - NameMatcher::~NameMatcher() {} - - void NameMatcher::match( ResolvExpr::AltList &alternatives ) throw (NoMatch) { - if ( alternatives.size() != index.size() ) - throw NoMatch("Length of actuals and formals differ"); - - for ( ResolvExpr::AltList::const_iterator a = alternatives.begin(); a != alternatives.end(); ++a ) { - if ( a->expr->get_argName() != 0 ) - if ( NameExpr *name = dynamic_cast( a->expr->get_argName() ) ) { - if ( table.find( name->get_name() ) != table.end() ) { - std::cerr << "Rearranging to " << table[ name->get_name() ] << "position in the list." << std::endl; - exprs[ table[ name->get_name() ] ] = &(*a); - } else - throw NoMatch( name->get_name() + "no such designation" ); - } /*else if ( TupleExpr *tup = dynamic_cast( a->expr->get_argName() ) ) - std::cerr << "Designated expression" << std::endl; */ - exprs.push_back( &(*a) ); - } // for - - /*std::cerr << "In matcher/match: "; - if ( exprs.size() != index.size() ) - std::cerr << "exprs and index differ in length" << std::endl; - else - std::cerr << "is all good." << std::endl; - */ - } - - ResolvExpr::Alternative &NameMatcher::get_next() throw (NoMoreElements) { - if ( current++ >= (int)(index.size()) ) - throw NoMoreElements(); - return *(new ResolvExpr::Alternative()); - } -} // namespace Tuples - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/Tuples/NameMatcher.h =================================================================== --- src/Tuples/NameMatcher.h (revision 906e24deeab82aafdd4cbb08fb896c8ffe5b99e0) +++ (revision ) @@ -1,62 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// NameMatcher.h -- -// -// Author : Rodolfo G. Esteves -// Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Mon May 18 15:01:37 2015 -// Update Count : 3 -// - -#ifndef _NAMEMATCHER_H_ -#define _NAMEMATCHER_H_ - -#include -#include -#include - -#include "SynTree/SynTree.h" -#include "SynTree/Mutator.h" - -#include "SynTree/Type.h" -#include "SynTree/Declaration.h" -#include "SynTree/Expression.h" -#include "SynTree/Statement.h" - -#include "ResolvExpr/Alternative.h" - -namespace Tuples { - struct NoMoreElements {}; - struct NoMatch { - NoMatch( std::string msg ) : message( msg ) {} - std::string message; - }; - - class NameMatcher { - public: - NameMatcher( std::list< DeclarationWithType* >& ); - ~NameMatcher(); - - void match( ResolvExpr::AltList &alternatives ) throw (NoMatch) ; - ResolvExpr::Alternative &get_next() throw (NoMoreElements); - - private: - int current; - std::vector< DeclarationWithType* > index; - std::vector< const ResolvExpr::Alternative * > exprs; - std::map< std::string, int> table; - }; -} // namespace Tuples - -#endif // _NAMEMATCHER_H_ - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision 906e24deeab82aafdd4cbb08fb896c8ffe5b99e0) +++ src/Tuples/TupleAssignment.cc (revision aa8f9dfd89cb8d2df9f8a3892703dfc427bce64a) @@ -18,5 +18,6 @@ #include "ResolvExpr/typeops.h" #include "SynTree/Expression.h" -#include "TupleAssignment.h" +#include "SynTree/Initializer.h" +#include "Tuples.h" #include "Common/SemanticError.h" @@ -27,379 +28,213 @@ #include #include +#include namespace Tuples { - TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder *f = 0 ) - : currentFinder(f), matcher(0), hasMatched( false ) {} - - bool TupleAssignSpotter::pointsToTuple( Expression *expr ) { + class TupleAssignSpotter { + public: + // dispatcher for Tuple (multiple and mass) assignment operations + TupleAssignSpotter( ResolvExpr::AlternativeFinder & ); + void spot( UntypedExpr * expr, std::list &possibilities ); + + private: + void match(); + // records for assignment generation + struct Options { + void print( std::ostream & ); + int size() const { return options.size(); } + bool empty() const { return options.empty(); } + typedef std::list< ResolvExpr::AltList >::iterator iterator; + iterator begin() { return options.begin(); } + iterator end() { return options.end(); } + + std::list< ResolvExpr::AltList > options; + }; + + struct Matcher { + public: + Matcher( TupleAssignSpotter &spotter, Expression *_lhs, Expression *_rhs ); + virtual ~Matcher() {} + virtual void match( std::list< Expression * > &out ) = 0; + std::list< Expression * > lhs, rhs; + TupleAssignSpotter &spotter; + std::list< ObjectDecl * > tmpDecls; + }; + + struct MassAssignMatcher : public Matcher { + public: + MassAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) { + this->rhs.push_back( rhs ); + } + virtual void match( std::list< Expression * > &out ); + }; + + struct MultipleAssignMatcher : public Matcher { + public: + MultipleAssignMatcher( TupleAssignSpotter &spot, Expression *lhs, Expression *rhs ); + virtual void match( std::list< Expression * > &out ); + }; + + ResolvExpr::AlternativeFinder ¤tFinder; + // Expression *rhs, *lhs; + Matcher *matcher = nullptr; + Options options; + }; + + bool isTupleVar( DeclarationWithType *decl ) { + return dynamic_cast< TupleType * >( decl->get_type() ); + } + + /// true if expr is an expression of tuple type, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function + bool isTuple( Expression *expr ) { + if ( ! expr ) return false; + assert( expr->has_result() ); + // xxx - used to include cast to varExpr and call to isTupleVar, but this doesn't seem like it should be necessary + return dynamic_cast(expr) || expr->get_result()->size() > 1; + } + + bool pointsToTuple( Expression *expr ) { // also check for function returning tuple of reference types - if (AddressExpr *addr = dynamic_cast(expr) ) - if ( isTuple(addr->get_arg() ) ) - return true; + if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) { + return isTuple( addr->get_arg() ); + } return false; } - bool TupleAssignSpotter::isTupleVar( DeclarationWithType *decl ) { - if ( dynamic_cast(decl->get_type()) ) - return true; - return false; - } - - bool TupleAssignSpotter::isTuple( Expression *expr, bool isRight ) { - // true if `expr' is an expression returning a tuple: tuple, tuple variable or MRV function - if ( ! expr ) return false; - - if ( dynamic_cast(expr) ) - return true; - else if ( VariableExpr *var = dynamic_cast(expr) ) { - if ( isTupleVar(var->get_var()) ) - return true; - } - - return false; - } - - bool TupleAssignSpotter::match() { - assert ( matcher != 0 ); - - std::list< Expression * > new_assigns; - if ( ! matcher->match(new_assigns) ) - return false; - - if ( new_assigns.empty() ) return false; - /*return */matcher->solve( new_assigns ); - if ( dynamic_cast( matcher ) ) { - // now resolve new assignments - std::list< Expression * > solved_assigns; - ResolvExpr::AltList solved_alts; - assert( currentFinder != 0 ); - - ResolvExpr::AltList current; - for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { - //try { - ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); - finder.findWithAdjustment(*i); - // prune expressions that don't coincide with - ResolvExpr::AltList alts = finder.get_alternatives(); - assert( alts.size() == 1 ); - assert(alts.front().expr != 0 ); - current.push_back( finder.get_alternatives().front() ); - solved_assigns.push_back( alts.front().expr->clone() ); - //solved_assigns.back()->print(std::cerr); - /*} catch( ... ) { - continue; // no reasonable alternative found - }*/ - } - options.add_option( current ); - - return true; - } else { // mass assignment - //if ( new_assigns.empty() ) return false; - std::list< Expression * > solved_assigns; - ResolvExpr::AltList solved_alts; - assert( currentFinder != 0 ); - - ResolvExpr::AltList current; - if ( optMass.empty() ) { - for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i ) - optMass.push_back( ResolvExpr::AltList() ); - } - int cnt = 0; - for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) { - - ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); - finder.findWithAdjustment(*i); - ResolvExpr::AltList alts = finder.get_alternatives(); - assert( alts.size() == 1 ); - assert(alts.front().expr != 0 ); - current.push_back( finder.get_alternatives().front() ); - optMass[cnt].push_back( finder.get_alternatives().front() ); - solved_assigns.push_back( alts.front().expr->clone() ); - } - - return true; - } - - return false; - } - - bool TupleAssignSpotter::isMVR( Expression *expr ) { - return isTuple( expr ); - } - - bool TupleAssignSpotter::isTupleAssignment( UntypedExpr * expr, std::list &possibilities ) { + bool isTupleExpr( Expression *expr ) { + assert( expr->has_result() ); + return expr->get_result()->size() > 1; + } + + void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, std::list &possibilities ) { + TupleAssignSpotter spotter( currentFinder ); + spotter.spot( expr, possibilities ); + } + + TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f ) + : currentFinder(f) {} + + void TupleAssignSpotter::spot( UntypedExpr * expr, std::list &possibilities ) { if ( NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) { - if ( assgnop->get_name() == std::string("?=?") ) { - for ( std::list::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) { assert( ali->size() == 2 ); - ResolvExpr::AltList::iterator opit = ali->begin(); - ResolvExpr::Alternative op1 = *opit, op2 = *(++opit); - + ResolvExpr::Alternative op1 = ali->front(), op2 = ali->back(); + + MultipleAssignMatcher multiMatcher( *this, op1.expr, op2.expr ); + MassAssignMatcher massMatcher( *this, op1.expr, op2.expr ); if ( pointsToTuple(op1.expr) ) { // also handles tuple vars - if ( isTuple( op2.expr, true ) ) - matcher = new MultipleAssignMatcher(op1.expr, op2.expr); - else if ( isMVR( op2.expr ) ) { - // handle MVR differently - } else + if ( isTuple( op2.expr ) ) { + matcher = &multiMatcher; + } else { // mass assignment - matcher = new MassAssignMatcher(op1.expr, op2.expr); - - std::list< ResolvExpr::AltList > options; - if ( match() ) - /* - if ( hasMatched ) { - // throw SemanticError("Ambiguous tuple assignment"); - } else {*/ - // Matched for the first time - hasMatched = true; - /*} */ - } /* else if ( isTuple( op2 ) ) - throw SemanticError("Inapplicable tuple assignment."); - */ - } - - if ( hasMatched ) { - if ( dynamic_cast( matcher ) ) { - //options.print( std::cerr ); - std::list< ResolvExpr::AltList >best = options.get_best(); - if ( best.size() == 1 ) { - std::list solved_assigns; - for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) { - solved_assigns.push_back( i->expr ); - } - /* assigning cost zero? */ - currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MULTIPLE*/), currentFinder->get_environ(), ResolvExpr::Cost() ) ); + matcher = &massMatcher; } - } else { - assert( ! optMass.empty() ); - ResolvExpr::AltList winners; - for ( std::vector< ResolvExpr::AltList >::iterator i = optMass.begin(); i != optMass.end(); ++i ) - findMinCostAlt( i->begin(), i->end(), back_inserter(winners) ); - - std::list< Expression *> solved_assigns; - for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i ) - solved_assigns.push_back( i->expr ); - currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MASS*/), currentFinder->get_environ(), ResolvExpr::Cost() ) ); + match(); + } else if ( isTuple( op2.expr ) ) { + throw SemanticError("Cannot assign a tuple value into a non-tuple lvalue.", expr); } } } } - return hasMatched; - } - - void TupleAssignSpotter::Matcher::init( Expression *_lhs, Expression *_rhs ) { - lhs.clear(); - if (AddressExpr *addr = dynamic_cast(_lhs) ) + } + + void TupleAssignSpotter::match() { + assert ( matcher != 0 ); + + std::list< Expression * > new_assigns; + matcher->match( new_assigns ); + + if ( new_assigns.empty() ) return; + ResolvExpr::AltList current; + // now resolve new assignments + for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { + ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() ); + finder.findWithAdjustment(*i); + // prune expressions that don't coincide with + ResolvExpr::AltList alts = finder.get_alternatives(); + assert( alts.size() == 1 ); + assert( alts.front().expr != 0 ); + current.push_back( alts.front() ); + } + + // extract expressions from the assignment alternatives to produce a list of assignments that + // together form a single alternative + std::list< Expression *> solved_assigns; + for ( ResolvExpr::Alternative & alt : current ) { + solved_assigns.push_back( alt.expr->clone() ); + } + // xxx - need to do this?? + // TypeEnvironment compositeEnv; + // simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); + currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), currentFinder.get_environ(), ResolvExpr::sumCost( current ) ) ); + } + + TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : spotter(spotter) { + // xxx - shouldn't need to be &, just & + if (AddressExpr *addr = dynamic_cast(lhs) ) if ( TupleExpr *tuple = dynamic_cast(addr->get_arg()) ) - std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(lhs) ); - - rhs.clear(); - } - - TupleAssignSpotter::Matcher::Matcher( /*TupleAssignSpotter &spot,*/ Expression *_lhs, Expression *_rhs ) /*: own_spotter(spot) */{ - init(_lhs,_rhs); - } - - TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( Expression *_lhs, Expression *_rhs )/* : own_spotter(spot) */{ - init(_lhs,_rhs); - - if ( TupleExpr *tuple = dynamic_cast(_rhs) ) - std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(rhs) ); - } - - UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) { - if ( left && right ) { - std::list< Expression * > args; - args.push_back(new AddressExpr(left->clone())); args.push_back(right->clone()); - return new UntypedExpr(new NameExpr("?=?"), args); - } else - throw 0; // xxx - diagnose the problem - } - - bool TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) { - if ( lhs.empty() || (rhs.size() != 1) ) return false; - - for ( std::list< Expression * >::iterator l = lhs.begin(); l != lhs.end(); l++ ) { - std::list< Expression * > args; - args.push_back( new AddressExpr(*l) ); - args.push_back( rhs.front() ); - out.push_back( new UntypedExpr(new NameExpr("?=?"), args) ); - } - - return true; - } - - bool TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) { - /* - std::list< Expression * > solved_assigns; - ResolvExpr::AltList solved_alts; - assert( currentFinder != 0 ); - - ResolvExpr::AltList current; - if ( optMass.empty() ) { - for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i ) - optMass.push_back( ResolvExpr::AltList() ); - } - int cnt = 0; - for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) { - - ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); - finder.findWithAdjustment(*i); - ResolvExpr::AltList alts = finder.get_alternatives(); - assert( alts.size() == 1 ); - assert(alts.front().expr != 0 ); - current.push_back( finder.get_alternatives().front() ); - optMass[cnt].push_back( finder.get_alternatives().front() ); - solved_assigns.push_back( alts.front().expr->clone() ); - } - */ - return true; - } - - bool TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) { - // need more complicated matching + std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->lhs) ); + } + + TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) { + + if ( TupleExpr *tuple = dynamic_cast(rhs) ) + std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->rhs) ); + } + + UntypedExpr * createAssgn( ObjectDecl *left, ObjectDecl *right ) { + assert( left && right ); + std::list< Expression * > args; + args.push_back( new AddressExpr( new UntypedExpr( new NameExpr("*?"), std::list< Expression * >{ new VariableExpr( left ) } ) ) ); + args.push_back( new VariableExpr( right ) ); + return new UntypedExpr( new NameExpr( "?=?" ), args ); + } + + ObjectDecl * newObject( UniqueName & namer, Expression * expr ) { + assert( expr->has_result() && ! expr->get_result()->isVoid() ); + return new ObjectDecl( namer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) ); + } + + void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) { + static UniqueName lhsNamer( "__massassign_L" ); + static UniqueName rhsNamer( "__massassign_R" ); + assert ( ! lhs.empty() && rhs.size() == 1); + + ObjectDecl * rtmp = newObject( rhsNamer, rhs.front() ); + for ( Expression * l : lhs ) { + ObjectDecl * ltmp = newObject( lhsNamer, new AddressExpr( l ) ); + out.push_back( createAssgn( ltmp, rtmp ) ); + tmpDecls.push_back( ltmp ); + } + tmpDecls.push_back( rtmp ); + } + + void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) { + static UniqueName lhsNamer( "__multassign_L" ); + static UniqueName rhsNamer( "__multassign_R" ); + // xxx - need more complicated matching? if ( lhs.size() == rhs.size() ) { - zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn ); - return true; - } //else - //std::cerr << "The length of (left, right) is: (" << lhs.size() << "," << rhs.size() << ")" << std::endl;*/ - return false; - } - - bool TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) { - /* - std::list< Expression * > solved_assigns; - ResolvExpr::AltList solved_alts; - assert( currentFinder != 0 ); - - ResolvExpr::AltList current; - for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { - //try { - ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() ); - finder.findWithAdjustment(*i); - // prune expressions that don't coincide with - ResolvExpr::AltList alts = finder.get_alternatives(); - assert( alts.size() == 1 ); - assert(alts.front().expr != 0 ); - current.push_back( finder.get_alternatives().front() ); - solved_assigns.push_back( alts.front().expr->clone() ); - //solved_assigns.back()->print(std::cerr); - //} catch( ... ) { - //continue; // no reasonable alternative found - //} - } - options.add_option( current ); - */ - - return true; - } - - void TupleAssignSpotter::Options::add_option( ResolvExpr::AltList &opt ) { - using namespace std; - - options.push_back( opt ); - /* - vector< Cost > costs; - costs.reserve( opt.size() ); - transform( opt.begin(), opt.end(), back_inserter(costs), ptr_fun(extract_cost) ); - */ - // transpose matrix - if ( costMatrix.empty() ) - for ( unsigned int i = 0; i< opt.size(); ++i) - costMatrix.push_back( vector() ); - - int cnt = 0; - for ( ResolvExpr::AltList::iterator i = opt.begin(); i != opt.end(); ++i, cnt++ ) - costMatrix[cnt].push_back( i->cost ); - - return; - } - - std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() { - using namespace std; - using namespace ResolvExpr; - list< ResolvExpr::AltList > ret; - list< multiset > solns; - for ( vector< vector >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) { - list current; - findMinCost( i->begin(), i->end(), back_inserter(current) ); - solns.push_back( multiset(current.begin(), current.end()) ); - } - // need to combine - multiset result; - lift_intersection( solns.begin(), solns.end(), inserter( result, result.begin() ) ); - if ( result.size() != 1 ) - throw SemanticError("Ambiguous tuple expression"); - ret.push_back(get_option( *(result.begin() ))); - return ret; + std::list< ObjectDecl * > ltmp; + std::list< ObjectDecl * > rtmp; + std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), []( Expression * expr ){ + return newObject( lhsNamer, new AddressExpr( expr ) ); + }); + std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), []( Expression * expr ){ + return newObject( rhsNamer, expr ); + }); + zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), createAssgn ); + tmpDecls.splice( tmpDecls.end(), ltmp ); + tmpDecls.splice( tmpDecls.end(), rtmp ); + } } void TupleAssignSpotter::Options::print( std::ostream &ostr ) { - using namespace std; - - for ( vector< vector < ResolvExpr::Cost > >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) { - for ( vector < ResolvExpr::Cost >::iterator j = i->begin(); j != i->end(); ++j ) - ostr << *j << " " ; + for ( ResolvExpr::AltList & l : options ) { + for ( ResolvExpr::Alternative & alt : l ) { + alt.print( ostr ); + ostr << " "; + } ostr << std::endl; } // for - return; - } - - ResolvExpr::Cost extract_cost( ResolvExpr::Alternative &alt ) { - return alt.cost; - } - - template< typename InputIterator, typename OutputIterator > - void TupleAssignSpotter::Options::findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) { - using namespace ResolvExpr; - std::list alternatives; - - // select the alternatives that have the minimum parameter cost - Cost minCost = Cost::infinity; - unsigned int index = 0; - for ( InputIterator i = begin; i != end; ++i, index++ ) { - if ( *i < minCost ) { - minCost = *i; - alternatives.clear(); - alternatives.push_back( index ); - } else if ( *i == minCost ) { - alternatives.push_back( index ); - } - } - std::copy( alternatives.begin(), alternatives.end(), out ); - } - - template< class InputIterator, class OutputIterator > - void TupleAssignSpotter::Options::lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ) { - if ( begin == end ) return; - InputIterator test = begin; - - if (++test == end) - { copy(begin->begin(), begin->end(), out); return; } - - - std::multiset cur; // InputIterator::value_type::value_type - copy( begin->begin(), begin->end(), inserter( cur, cur.begin() ) ); - - while ( test != end ) { - std::multiset temp; - set_intersection( cur.begin(), cur.end(), test->begin(), test->end(), inserter(temp,temp.begin()) ); - cur.clear(); - copy( temp.begin(), temp.end(), inserter(cur,cur.begin())); - ++test; - } - - copy( cur.begin(), cur.end(), out ); - return; - } - - ResolvExpr::AltList TupleAssignSpotter::Options::get_option( std::list< ResolvExpr::AltList >::size_type index ) { - if ( index >= options.size() ) - throw 0; // XXX - std::list< ResolvExpr::AltList >::iterator it = options.begin(); - for ( std::list< ResolvExpr::AltList >::size_type i = 0; i < index; ++i, ++it ); - return *it; } } // namespace Tuples Index: src/Tuples/TupleAssignment.h =================================================================== --- src/Tuples/TupleAssignment.h (revision 906e24deeab82aafdd4cbb08fb896c8ffe5b99e0) +++ (revision ) @@ -1,136 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// TupleAssignment.h -- -// -// Author : Rodolfo G. Esteves -// Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Mon May 18 15:04:02 2015 -// Update Count : 2 -// - -#ifndef _TUPLE_ASSIGNMENT_H_ -#define _TUPLE_ASSIGNMENT_H_ - -#include -#include -#include "ResolvExpr/AlternativeFinder.h" - -#include "SynTree/Expression.h" -#include "SynTree/Declaration.h" -#include "SynTree/Type.h" - -namespace Tuples { - class TupleAssignSpotter { - public: - // dispatcher for Tuple (multiple and mass) assignment operations - TupleAssignSpotter( ResolvExpr::AlternativeFinder * ); - ~TupleAssignSpotter() { delete matcher; matcher = 0; } - - bool pointsToTuple( Expression * ); - static bool isTupleVar( DeclarationWithType * ); - bool isTuple( Expression *, bool isRight = false ); - bool isMVR( Expression * ); - bool isTupleAssignment( UntypedExpr *, std::list & ); - bool match(); - private: - // records for assignment generation - class Options { - public: - void add_option( ResolvExpr::AltList &opt ); - std::list< ResolvExpr::AltList > get_best(); - void print( std::ostream & ); - int size() const { return options.size(); } - ResolvExpr::AltList get_option( std::list< ResolvExpr::AltList >::size_type index ); - - // should really use the one in ResolvExpr/AlternativeFinder, but it's too coupled with the object - template< typename InputIterator, typename OutputIterator > - void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ); - - template< typename InputIterator, typename OutputIterator > - void lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ); - private: - std::list< ResolvExpr::AltList > options; - std::vector< std::vector< ResolvExpr::Cost > > costMatrix; - }; - - class Matcher { - public: - Matcher( /*TupleAssignSpotter &spot, */Expression *_lhs, Expression *_rhs ); - virtual ~Matcher() {} - virtual bool match( std::list< Expression * > &out ) = 0; - virtual bool solve( std::list< Expression * > &assigns ) = 0; - static UntypedExpr *createAssgn( Expression *left, Expression *right ); - protected: - Matcher() /*: own_spotter( TupleAssignSpotter(0) ) */{} - void init(/* TupleAssignSpotter &, */Expression *_lhs, Expression *_rhs ); - std::list< Expression * > lhs, rhs; - //TupleAssignSpotter &own_spotter; - }; - - class MassAssignMatcher : public Matcher { - public: - MassAssignMatcher( Expression *_lhs, Expression *_rhs ) : Matcher( _lhs, _rhs ) { - rhs.push_back( _rhs ); - } - virtual bool match( std::list< Expression * > &out ); - virtual bool solve( std::list< Expression * > &assigns ); - private: - //std::vector< ResolvExpr::AltList > optMass; - }; - - class MultipleAssignMatcher : public Matcher { - public: - MultipleAssignMatcher( Expression *_lhs, Expression *_rhs ); - virtual bool match( std::list< Expression * > &out ); - virtual bool solve( std::list< Expression * > &assigns ); - private: - //Options options; - }; - - friend class Matcher; - - ResolvExpr::AlternativeFinder *currentFinder; - //std::list rhs, lhs; - Expression *rhs, *lhs; - Matcher *matcher; - bool hasMatched; - Options options; - std::vector< ResolvExpr::AltList > optMass; - }; - - ResolvExpr::Cost extract_cost( ResolvExpr::Alternative & ); - - template< typename InputIterator, typename OutputIterator > - void findMinCostAlt( InputIterator begin, InputIterator end, OutputIterator out ) { - using namespace ResolvExpr; - AltList alternatives; - - // select the alternatives that have the minimum parameter cost - Cost minCost = Cost::infinity; - for ( AltList::iterator i = begin; i != end; ++i ) { - if ( i->cost < minCost ) { - minCost = i->cost; - i->cost = i->cvtCost; - alternatives.clear(); - alternatives.push_back( *i ); - } else if ( i->cost == minCost ) { - i->cost = i->cvtCost; - alternatives.push_back( *i ); - } - } - std::copy( alternatives.begin(), alternatives.end(), out ); - } -} // namespace Tuples - -#endif // _TUPLE_ASSIGNMENT_H_ - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/Tuples/TupleExpansion.cc =================================================================== --- src/Tuples/TupleExpansion.cc (revision aa8f9dfd89cb8d2df9f8a3892703dfc427bce64a) +++ src/Tuples/TupleExpansion.cc (revision aa8f9dfd89cb8d2df9f8a3892703dfc427bce64a) @@ -0,0 +1,99 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// TupleAssignment.cc -- +// +// Author : Rodolfo G. Esteves +// Created On : Mon May 18 07:44:20 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Mon May 18 15:02:53 2015 +// Update Count : 2 +// + +#include +#include +#include +#include "Tuples.h" +#include "GenPoly/DeclMutator.h" +#include "SynTree/Mutator.h" +#include "SynTree/Statement.h" +#include "SynTree/Declaration.h" +#include "SynTree/Type.h" +#include "SymTab/Mangler.h" +#include "Common/ScopedMap.h" + +namespace Tuples { + class TupleAssignExpander : public Mutator { + public: + virtual Expression * mutate( TupleAssignExpr * tupleExpr ); + }; + + class TupleTypeReplacer : public GenPoly::DeclMutator { + public: + typedef GenPoly::DeclMutator Parent; + + virtual Type * mutate( TupleType * tupleType ); + + virtual CompoundStmt * mutate( CompoundStmt * stmt ) { + typeMap.beginScope(); + stmt = Parent::mutate( stmt ); + typeMap.endScope(); + return stmt; + } + private: + ScopedMap< std::string, StructDecl * > typeMap; + }; + + void expandTuples( std::list< Declaration * > & translationUnit ) { + TupleAssignExpander expander; + mutateAll( translationUnit, expander ); + + TupleTypeReplacer replacer; + replacer.mutateDeclarationList( translationUnit ); + } + + Expression * TupleAssignExpander::mutate( TupleAssignExpr * tupleExpr ) { + CompoundStmt * compoundStmt = new CompoundStmt( noLabels ); + std::list< Statement * > & stmts = compoundStmt->get_kids(); + for ( ObjectDecl * obj : tupleExpr->get_tempDecls() ) { + stmts.push_back( new DeclStmt( noLabels, obj ) ); + } + for ( Expression * assign : tupleExpr->get_assigns() ) { + stmts.push_back( new ExprStmt( noLabels, assign ) ); + } + tupleExpr->get_tempDecls().clear(); + tupleExpr->get_assigns().clear(); + delete tupleExpr; + return new StmtExpr( compoundStmt ); + } + + Type * TupleTypeReplacer::mutate( TupleType * tupleType ) { + std::string mangleName = SymTab::Mangler::mangleType( tupleType ); + TupleType * newType = safe_dynamic_cast< TupleType * > ( Parent::mutate( tupleType ) ); + if ( ! typeMap.count( mangleName ) ) { + // generate struct type to replace tuple type + StructDecl * decl = new StructDecl( "_tuple_type_" + mangleName ); + decl->set_body( true ); + int cnt = 0; + for ( Type * t : *newType ) { + decl->get_members().push_back( new ObjectDecl( "field_"+std::to_string(++cnt), DeclarationNode::NoStorageClass, LinkageSpec::C, nullptr, t->clone(), nullptr ) ); + } + typeMap[mangleName] = decl; + addDeclaration( decl ); + } + Type::Qualifiers qualifiers = newType->get_qualifiers(); + delete newType; + return new StructInstType( qualifiers, typeMap[mangleName] ); + } + +} // namespace Tuples + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // + Index: src/Tuples/Tuples.h =================================================================== --- src/Tuples/Tuples.h (revision aa8f9dfd89cb8d2df9f8a3892703dfc427bce64a) +++ src/Tuples/Tuples.h (revision aa8f9dfd89cb8d2df9f8a3892703dfc427bce64a) @@ -0,0 +1,41 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Tuples.h -- +// +// Author : Rodolfo G. Esteves +// Created On : Mon May 18 07:44:20 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Mon May 18 15:04:02 2015 +// Update Count : 2 +// + +#ifndef _TUPLES_H_ +#define _TUPLE_H_ + +#include +#include +#include "ResolvExpr/AlternativeFinder.h" + +#include "SynTree/Expression.h" +#include "SynTree/Declaration.h" +#include "SynTree/Type.h" + +namespace Tuples { + // TupleAssignment.cc + void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign, std::list & possibilities ); + + // TupleExpansion.cc + void expandTuples( std::list< Declaration * > & translationUnit ); +} // namespace Tuples + +#endif // _TUPLE_ASSIGNMENT_H_ + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Tuples/module.mk =================================================================== --- src/Tuples/module.mk (revision 906e24deeab82aafdd4cbb08fb896c8ffe5b99e0) +++ src/Tuples/module.mk (revision aa8f9dfd89cb8d2df9f8a3892703dfc427bce64a) @@ -6,5 +6,5 @@ ## file "LICENCE" distributed with Cforall. ## -## module.mk -- +## module.mk -- ## ## Author : Richard C. Bilson @@ -16,3 +16,3 @@ SRC += Tuples/TupleAssignment.cc \ - Tuples/NameMatcher.cc + Tuples/TupleExpansion.cc