[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 | // |
---|
[5af62f1] | 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 | |
---|
[51b7345] | 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" |
---|
[51b7345] | 22 | |
---|
| 23 | #include <functional> |
---|
| 24 | #include <algorithm> |
---|
| 25 | #include <iterator> |
---|
| 26 | #include <iostream> |
---|
| 27 | #include <cassert> |
---|
| 28 | #include <set> |
---|
[5af62f1] | 29 | #include <unordered_set> |
---|
[51b7345] | 30 | |
---|
| 31 | namespace Tuples { |
---|
[5af62f1] | 32 | class TupleAssignSpotter { |
---|
| 33 | public: |
---|
| 34 | // dispatcher for Tuple (multiple and mass) assignment operations |
---|
| 35 | TupleAssignSpotter( ResolvExpr::AlternativeFinder & ); |
---|
| 36 | void spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ); |
---|
| 37 | |
---|
| 38 | private: |
---|
| 39 | void match(); |
---|
| 40 | // records for assignment generation |
---|
| 41 | struct Options { |
---|
| 42 | std::list< ResolvExpr::AltList > get_best(); |
---|
| 43 | void print( std::ostream & ); |
---|
| 44 | int size() const { return options.size(); } |
---|
| 45 | bool empty() const { return options.empty(); } |
---|
| 46 | typedef std::list< ResolvExpr::AltList >::iterator iterator; |
---|
| 47 | iterator begin() { return options.begin(); } |
---|
| 48 | iterator end() { return options.end(); } |
---|
| 49 | |
---|
| 50 | std::list< ResolvExpr::AltList > options; |
---|
| 51 | }; |
---|
| 52 | |
---|
| 53 | class Matcher { |
---|
| 54 | public: |
---|
| 55 | Matcher( TupleAssignSpotter &spotter, Expression *_lhs, Expression *_rhs ); |
---|
| 56 | virtual ~Matcher() {} |
---|
| 57 | virtual void match( std::list< Expression * > &out ) = 0; |
---|
| 58 | virtual void solve( std::list< Expression * > &assigns ) = 0; |
---|
| 59 | static UntypedExpr *createAssgn( Expression *left, Expression *right ); |
---|
| 60 | protected: |
---|
| 61 | std::list< Expression * > lhs, rhs; |
---|
| 62 | TupleAssignSpotter &spotter; |
---|
| 63 | }; |
---|
| 64 | |
---|
| 65 | class MassAssignMatcher : public Matcher { |
---|
| 66 | public: |
---|
| 67 | MassAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) { |
---|
| 68 | this->rhs.push_back( rhs ); |
---|
| 69 | } |
---|
| 70 | virtual void match( std::list< Expression * > &out ); |
---|
| 71 | virtual void solve( std::list< Expression * > &assigns ); |
---|
| 72 | }; |
---|
| 73 | |
---|
| 74 | class MultipleAssignMatcher : public Matcher { |
---|
| 75 | public: |
---|
| 76 | MultipleAssignMatcher( TupleAssignSpotter &spot, Expression *lhs, Expression *rhs ); |
---|
| 77 | virtual void match( std::list< Expression * > &out ); |
---|
| 78 | virtual void solve( std::list< Expression * > &assigns ); |
---|
| 79 | }; |
---|
| 80 | |
---|
| 81 | ResolvExpr::AlternativeFinder ¤tFinder; |
---|
| 82 | Expression *rhs, *lhs; |
---|
| 83 | Matcher *matcher = nullptr; |
---|
| 84 | Options options; |
---|
| 85 | }; |
---|
| 86 | |
---|
| 87 | bool isTupleVar( DeclarationWithType *decl ) { |
---|
| 88 | return dynamic_cast< TupleType * >( decl->get_type() ); |
---|
[51587aa] | 89 | } |
---|
| 90 | |
---|
[5af62f1] | 91 | /// true if expr is an expression of tuple type, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function |
---|
| 92 | bool isTuple( Expression *expr ) { |
---|
[51587aa] | 93 | if ( ! expr ) return false; |
---|
| 94 | |
---|
[5af62f1] | 95 | // xxx - used to include cast to varExpr and call to isTupleVar, but this doesn't seem like it should be necessary |
---|
| 96 | return dynamic_cast<TupleExpr *>(expr) || expr->get_results().size() > 1; |
---|
[51587aa] | 97 | } |
---|
| 98 | |
---|
[5af62f1] | 99 | bool pointsToTuple( Expression *expr ) { |
---|
| 100 | // also check for function returning tuple of reference types |
---|
| 101 | if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) { |
---|
| 102 | return isTuple( addr->get_arg() ); |
---|
[51587aa] | 103 | } |
---|
| 104 | return false; |
---|
| 105 | } |
---|
| 106 | |
---|
[5af62f1] | 107 | bool isTupleExpr( Expression *expr ) { |
---|
| 108 | return expr->get_results().size() > 1; |
---|
[51587aa] | 109 | } |
---|
| 110 | |
---|
[5af62f1] | 111 | void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) { |
---|
| 112 | TupleAssignSpotter spotter( currentFinder ); |
---|
| 113 | spotter.spot( expr, possibilities ); |
---|
| 114 | } |
---|
[51587aa] | 115 | |
---|
[5af62f1] | 116 | TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f ) |
---|
| 117 | : currentFinder(f) {} |
---|
[51587aa] | 118 | |
---|
[5af62f1] | 119 | void TupleAssignSpotter::spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) { |
---|
| 120 | if ( NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) { |
---|
| 121 | if ( assgnop->get_name() == std::string("?=?") ) { |
---|
[51587aa] | 122 | for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) { |
---|
| 123 | assert( ali->size() == 2 ); |
---|
[5af62f1] | 124 | ResolvExpr::Alternative op1 = ali->front(), op2 = ali->back(); |
---|
[51587aa] | 125 | |
---|
[5af62f1] | 126 | MultipleAssignMatcher multiMatcher( *this, op1.expr, op2.expr ); |
---|
| 127 | MassAssignMatcher massMatcher( *this, op1.expr, op2.expr ); |
---|
[51587aa] | 128 | if ( pointsToTuple(op1.expr) ) { // also handles tuple vars |
---|
[5af62f1] | 129 | if ( isTuple( op2.expr ) ) { |
---|
| 130 | matcher = &multiMatcher; |
---|
| 131 | } else { |
---|
[51587aa] | 132 | // mass assignment |
---|
[5af62f1] | 133 | matcher = &massMatcher; |
---|
[51587aa] | 134 | } |
---|
[5af62f1] | 135 | match(); |
---|
| 136 | } else if ( isTuple( op2.expr ) ) { |
---|
| 137 | throw SemanticError("Cannot assign a tuple value into a non-tuple lvalue.", expr); |
---|
[51587aa] | 138 | } |
---|
| 139 | } |
---|
| 140 | } |
---|
| 141 | } |
---|
| 142 | } |
---|
| 143 | |
---|
[5af62f1] | 144 | void TupleAssignSpotter::match() { |
---|
| 145 | assert ( matcher != 0 ); |
---|
[51587aa] | 146 | |
---|
[5af62f1] | 147 | std::list< Expression * > new_assigns; |
---|
| 148 | matcher->match( new_assigns ); |
---|
| 149 | |
---|
| 150 | if ( new_assigns.empty() ) return; |
---|
| 151 | std::list< Expression * > solved_assigns; |
---|
| 152 | ResolvExpr::AltList solved_alts; |
---|
| 153 | ResolvExpr::AltList current; |
---|
| 154 | // now resolve new assignments |
---|
| 155 | for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { |
---|
| 156 | ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() ); |
---|
| 157 | finder.findWithAdjustment(*i); |
---|
| 158 | // prune expressions that don't coincide with |
---|
| 159 | ResolvExpr::AltList alts = finder.get_alternatives(); |
---|
| 160 | assert( alts.size() == 1 ); |
---|
| 161 | assert( alts.front().expr != 0 ); |
---|
| 162 | current.push_back( finder.get_alternatives().front() ); |
---|
| 163 | solved_assigns.push_back( alts.front().expr->clone() ); |
---|
| 164 | } |
---|
| 165 | options.options.push_back( current ); |
---|
| 166 | |
---|
| 167 | matcher->solve( new_assigns ); |
---|
[51587aa] | 168 | } |
---|
| 169 | |
---|
[5af62f1] | 170 | TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : spotter(spotter) { |
---|
| 171 | // xxx - shouldn't need to be &<tuple-expr>, just &<lvalue-tuple-type> |
---|
| 172 | if (AddressExpr *addr = dynamic_cast<AddressExpr *>(lhs) ) |
---|
| 173 | if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) ) |
---|
| 174 | std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->lhs) ); |
---|
[51587aa] | 175 | } |
---|
| 176 | |
---|
[5af62f1] | 177 | TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) { |
---|
[51587aa] | 178 | |
---|
[5af62f1] | 179 | if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(rhs) ) |
---|
| 180 | std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->rhs) ); |
---|
[51587aa] | 181 | } |
---|
| 182 | |
---|
| 183 | UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) { |
---|
[5af62f1] | 184 | assert( left && right ); |
---|
| 185 | std::list< Expression * > args; |
---|
| 186 | args.push_back( new AddressExpr( left->clone() ) ); |
---|
| 187 | args.push_back( right->clone() ); |
---|
| 188 | return new UntypedExpr( new NameExpr( "?=?" ), args ); |
---|
[51587aa] | 189 | } |
---|
| 190 | |
---|
[5af62f1] | 191 | void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) { |
---|
| 192 | assert ( ! lhs.empty() && rhs.size() == 1); |
---|
[51587aa] | 193 | |
---|
[5af62f1] | 194 | for ( Expression * l : lhs ) { |
---|
| 195 | out.push_back( createAssgn( l, rhs.front() ) ); |
---|
[51587aa] | 196 | } |
---|
| 197 | } |
---|
| 198 | |
---|
[5af62f1] | 199 | void TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) { |
---|
| 200 | assert( ! spotter.options.empty() ); |
---|
| 201 | ResolvExpr::AltList winners; |
---|
| 202 | for ( std::list< ResolvExpr::AltList >::iterator i = spotter.options.begin(); i != spotter.options.end(); ++i ) { |
---|
| 203 | findMinCost( i->begin(), i->end(), back_inserter(winners) ); |
---|
| 204 | } |
---|
| 205 | |
---|
| 206 | std::list< Expression *> solved_assigns; |
---|
| 207 | for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i ) { |
---|
| 208 | solved_assigns.push_back( i->expr ); |
---|
| 209 | } |
---|
| 210 | spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) ); |
---|
[51b7345] | 211 | } |
---|
| 212 | |
---|
[5af62f1] | 213 | void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) { |
---|
| 214 | // xxx - need more complicated matching? |
---|
[51587aa] | 215 | if ( lhs.size() == rhs.size() ) { |
---|
| 216 | zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn ); |
---|
[5af62f1] | 217 | } |
---|
[51587aa] | 218 | } |
---|
| 219 | |
---|
[5af62f1] | 220 | void TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) { |
---|
| 221 | // options.print( std::cerr ); |
---|
| 222 | std::list< ResolvExpr::AltList > best = spotter.options.get_best(); |
---|
| 223 | if ( best.size() == 1 ) { |
---|
| 224 | std::list<Expression *> solved_assigns; |
---|
| 225 | for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) { |
---|
| 226 | solved_assigns.push_back( i->expr ); |
---|
| 227 | } |
---|
| 228 | /* assigning cost zero? */ |
---|
| 229 | spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) ); |
---|
| 230 | } |
---|
[51587aa] | 231 | } |
---|
[51b7345] | 232 | |
---|
[51587aa] | 233 | std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() { |
---|
[5af62f1] | 234 | std::list< ResolvExpr::AltList > ret; |
---|
| 235 | std::list< ResolvExpr::AltList > solns; |
---|
| 236 | for ( ResolvExpr::AltList & i : options ) { |
---|
| 237 | ResolvExpr::AltList current; |
---|
| 238 | findMinCost( i.begin(), i.end(), back_inserter(current) ); |
---|
| 239 | solns.push_back( ResolvExpr::AltList(current.begin(), current.end()) ); |
---|
[51587aa] | 240 | } |
---|
[5af62f1] | 241 | // need to combine -- previously "lift_intersection", which |
---|
| 242 | // did some madness involving, effectively, the intersection of |
---|
| 243 | // a bunch of AltLists |
---|
| 244 | std::list<ResolvExpr::AltList> result = solns; |
---|
| 245 | if ( result.size() != 1 ) { |
---|
[51587aa] | 246 | throw SemanticError("Ambiguous tuple expression"); |
---|
[5af62f1] | 247 | } |
---|
| 248 | ret.push_back( *result.begin() ); |
---|
[51587aa] | 249 | return ret; |
---|
| 250 | } |
---|
| 251 | |
---|
| 252 | void TupleAssignSpotter::Options::print( std::ostream &ostr ) { |
---|
[5af62f1] | 253 | for ( ResolvExpr::AltList & l : options ) { |
---|
| 254 | for ( ResolvExpr::Alternative & alt : l ) { |
---|
| 255 | alt.print( ostr ); |
---|
| 256 | ostr << " "; |
---|
| 257 | } |
---|
[51587aa] | 258 | ostr << std::endl; |
---|
| 259 | } // for |
---|
| 260 | } |
---|
[51b7345] | 261 | } // namespace Tuples |
---|
[51587aa] | 262 | |
---|
| 263 | // Local Variables: // |
---|
| 264 | // tab-width: 4 // |
---|
| 265 | // mode: c++ // |
---|
| 266 | // compile-command: "make install" // |
---|
| 267 | // End: // |
---|