[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 |
---|
[c0aa336] | 11 | // Last Modified By : Peter A. Buhr |
---|
[615a096] | 12 | // Last Modified On : Fri Mar 17 09:43:03 2017 |
---|
| 13 | // Update Count : 8 |
---|
[51587aa] | 14 | // |
---|
| 15 | |
---|
[51b7345] | 16 | #include "ResolvExpr/AlternativeFinder.h" |
---|
| 17 | #include "ResolvExpr/Alternative.h" |
---|
| 18 | #include "ResolvExpr/typeops.h" |
---|
| 19 | #include "SynTree/Expression.h" |
---|
[6eb8948] | 20 | #include "SynTree/Initializer.h" |
---|
| 21 | #include "Tuples.h" |
---|
[141b786] | 22 | #include "Explode.h" |
---|
[d3b7937] | 23 | #include "Common/SemanticError.h" |
---|
[bff227f] | 24 | #include "CodeGen/OperatorTable.h" |
---|
[65660bd] | 25 | #include "InitTweak/InitTweak.h" |
---|
[1d2b64f] | 26 | #include "InitTweak/GenInit.h" |
---|
[51b7345] | 27 | |
---|
| 28 | #include <functional> |
---|
| 29 | #include <algorithm> |
---|
| 30 | #include <iterator> |
---|
| 31 | #include <iostream> |
---|
| 32 | #include <cassert> |
---|
| 33 | #include <set> |
---|
[5af62f1] | 34 | #include <unordered_set> |
---|
[51b7345] | 35 | |
---|
| 36 | namespace Tuples { |
---|
[5af62f1] | 37 | class TupleAssignSpotter { |
---|
| 38 | public: |
---|
| 39 | // dispatcher for Tuple (multiple and mass) assignment operations |
---|
| 40 | TupleAssignSpotter( ResolvExpr::AlternativeFinder & ); |
---|
[65660bd] | 41 | void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ); |
---|
[5af62f1] | 42 | |
---|
| 43 | private: |
---|
| 44 | void match(); |
---|
| 45 | |
---|
[6eb8948] | 46 | struct Matcher { |
---|
[5af62f1] | 47 | public: |
---|
[65660bd] | 48 | Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ); |
---|
[5af62f1] | 49 | virtual ~Matcher() {} |
---|
| 50 | virtual void match( std::list< Expression * > &out ) = 0; |
---|
[1d2b64f] | 51 | ObjectDecl * newObject( UniqueName & namer, Expression * expr ); |
---|
[3c13c03] | 52 | ResolvExpr::AltList lhs, rhs; |
---|
[5af62f1] | 53 | TupleAssignSpotter &spotter; |
---|
[1d2b64f] | 54 | ResolvExpr::Cost baseCost; |
---|
[6eb8948] | 55 | std::list< ObjectDecl * > tmpDecls; |
---|
[1d2b64f] | 56 | ResolvExpr::TypeEnvironment compositeEnv; |
---|
[5af62f1] | 57 | }; |
---|
| 58 | |
---|
[6eb8948] | 59 | struct MassAssignMatcher : public Matcher { |
---|
[5af62f1] | 60 | public: |
---|
[65660bd] | 61 | MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ); |
---|
[5af62f1] | 62 | virtual void match( std::list< Expression * > &out ); |
---|
| 63 | }; |
---|
| 64 | |
---|
[6eb8948] | 65 | struct MultipleAssignMatcher : public Matcher { |
---|
[5af62f1] | 66 | public: |
---|
[65660bd] | 67 | MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts ); |
---|
[5af62f1] | 68 | virtual void match( std::list< Expression * > &out ); |
---|
| 69 | }; |
---|
| 70 | |
---|
| 71 | ResolvExpr::AlternativeFinder ¤tFinder; |
---|
[65660bd] | 72 | std::string fname; |
---|
| 73 | std::unique_ptr< Matcher > matcher; |
---|
[5af62f1] | 74 | }; |
---|
| 75 | |
---|
[f831177] | 76 | /// true if expr is an expression of tuple type |
---|
[5af62f1] | 77 | bool isTuple( Expression *expr ) { |
---|
[51587aa] | 78 | if ( ! expr ) return false; |
---|
[aa8f9df] | 79 | assert( expr->has_result() ); |
---|
[e6cee92] | 80 | return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() ); |
---|
[51587aa] | 81 | } |
---|
| 82 | |
---|
[65660bd] | 83 | template< typename AltIter > |
---|
| 84 | bool isMultAssign( AltIter begin, AltIter end ) { |
---|
| 85 | // multiple assignment if more than one alternative in the range or if |
---|
| 86 | // the alternative is a tuple |
---|
| 87 | if ( begin == end ) return false; |
---|
| 88 | if ( isTuple( begin->expr ) ) return true; |
---|
| 89 | return ++begin != end; |
---|
| 90 | } |
---|
| 91 | |
---|
[e6cee92] | 92 | bool refToTuple( Expression *expr ) { |
---|
| 93 | assert( expr->get_result() ); |
---|
[5af62f1] | 94 | // also check for function returning tuple of reference types |
---|
[65660bd] | 95 | if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) { |
---|
[e6cee92] | 96 | return refToTuple( castExpr->get_arg() ); |
---|
| 97 | } else { |
---|
| 98 | return isTuple( expr ); |
---|
[51587aa] | 99 | } |
---|
| 100 | return false; |
---|
| 101 | } |
---|
| 102 | |
---|
[65660bd] | 103 | void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) { |
---|
[5af62f1] | 104 | TupleAssignSpotter spotter( currentFinder ); |
---|
| 105 | spotter.spot( expr, possibilities ); |
---|
| 106 | } |
---|
[51587aa] | 107 | |
---|
[5af62f1] | 108 | TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f ) |
---|
| 109 | : currentFinder(f) {} |
---|
[51587aa] | 110 | |
---|
[65660bd] | 111 | void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) { |
---|
| 112 | if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) { |
---|
[bff227f] | 113 | if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) { |
---|
[65660bd] | 114 | fname = op->get_name(); |
---|
| 115 | for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) { |
---|
| 116 | if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal |
---|
[bff227f] | 117 | if ( ali->size() <= 1 && CodeGen::isAssignment( op->get_name() ) ) { |
---|
[65660bd] | 118 | // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it |
---|
| 119 | continue; |
---|
| 120 | } |
---|
[51587aa] | 121 | |
---|
[65660bd] | 122 | assert( ! ali->empty() ); |
---|
| 123 | // grab args 2-N and group into a TupleExpr |
---|
| 124 | const ResolvExpr::Alternative & alt1 = ali->front(); |
---|
| 125 | auto begin = std::next(ali->begin(), 1), end = ali->end(); |
---|
[e6cee92] | 126 | if ( refToTuple(alt1.expr) ) { |
---|
[65660bd] | 127 | if ( isMultAssign( begin, end ) ) { |
---|
| 128 | matcher.reset( new MultipleAssignMatcher( *this, *ali ) ); |
---|
[5af62f1] | 129 | } else { |
---|
[51587aa] | 130 | // mass assignment |
---|
[65660bd] | 131 | matcher.reset( new MassAssignMatcher( *this, *ali ) ); |
---|
[51587aa] | 132 | } |
---|
[5af62f1] | 133 | match(); |
---|
[51587aa] | 134 | } |
---|
| 135 | } |
---|
| 136 | } |
---|
| 137 | } |
---|
| 138 | } |
---|
| 139 | |
---|
[5af62f1] | 140 | void TupleAssignSpotter::match() { |
---|
| 141 | assert ( matcher != 0 ); |
---|
[51587aa] | 142 | |
---|
[5af62f1] | 143 | std::list< Expression * > new_assigns; |
---|
| 144 | matcher->match( new_assigns ); |
---|
| 145 | |
---|
[f831177] | 146 | if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) { |
---|
| 147 | // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty. |
---|
| 148 | // if not the empty tuple case, return early so that no new alternatives are generated. |
---|
| 149 | if ( new_assigns.empty() ) return; |
---|
| 150 | } |
---|
[5af62f1] | 151 | ResolvExpr::AltList current; |
---|
| 152 | // now resolve new assignments |
---|
| 153 | for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { |
---|
| 154 | ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() ); |
---|
[ac9ca96] | 155 | try { |
---|
| 156 | finder.findWithAdjustment(*i); |
---|
| 157 | } catch (...) { |
---|
[1d2b64f] | 158 | return; // no match should not mean failure, it just means this particular tuple assignment isn't valid |
---|
[ac9ca96] | 159 | } |
---|
[5af62f1] | 160 | // prune expressions that don't coincide with |
---|
| 161 | ResolvExpr::AltList alts = finder.get_alternatives(); |
---|
| 162 | assert( alts.size() == 1 ); |
---|
| 163 | assert( alts.front().expr != 0 ); |
---|
[908cc83] | 164 | current.push_back( alts.front() ); |
---|
[5af62f1] | 165 | } |
---|
| 166 | |
---|
[6eb8948] | 167 | // extract expressions from the assignment alternatives to produce a list of assignments that |
---|
| 168 | // together form a single alternative |
---|
| 169 | std::list< Expression *> solved_assigns; |
---|
| 170 | for ( ResolvExpr::Alternative & alt : current ) { |
---|
| 171 | solved_assigns.push_back( alt.expr->clone() ); |
---|
| 172 | } |
---|
[1d2b64f] | 173 | // combine assignment environments into combined expression environment |
---|
| 174 | simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv ); |
---|
| 175 | currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current ) + matcher->baseCost ) ); |
---|
[51587aa] | 176 | } |
---|
| 177 | |
---|
[1d2b64f] | 178 | TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) { |
---|
[65660bd] | 179 | assert( ! alts.empty() ); |
---|
[1d2b64f] | 180 | // combine argument environments into combined expression environment |
---|
| 181 | simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); |
---|
| 182 | |
---|
[65660bd] | 183 | ResolvExpr::Alternative lhsAlt = alts.front(); |
---|
| 184 | // peel off the cast that exists on ctor/dtor expressions |
---|
| 185 | bool isCast = false; |
---|
| 186 | if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) { |
---|
| 187 | lhsAlt.expr = castExpr->get_arg(); |
---|
| 188 | castExpr->set_arg( nullptr ); |
---|
| 189 | delete castExpr; |
---|
| 190 | isCast = true; |
---|
| 191 | } |
---|
[3c13c03] | 192 | |
---|
[65660bd] | 193 | // explode the lhs so that each field of the tuple-valued-expr is assigned. |
---|
[f831177] | 194 | explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true ); |
---|
[b3b2077] | 195 | |
---|
[65660bd] | 196 | // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed |
---|
| 197 | if ( isCast ) { |
---|
| 198 | for ( ResolvExpr::Alternative & alt : lhs ) { |
---|
| 199 | Expression *& expr = alt.expr; |
---|
[e6cee92] | 200 | Type * type = expr->get_result()->clone(); |
---|
[bf4ac09] | 201 | type->get_qualifiers() -= Type::Qualifiers( Type::Const | Type::Volatile | Type::Restrict | Type::Atomic ); |
---|
[e6cee92] | 202 | expr = new CastExpr( expr, new ReferenceType( Type::Qualifiers(), type ) ); |
---|
[65660bd] | 203 | } |
---|
[3c13c03] | 204 | } |
---|
[7d49b72] | 205 | |
---|
| 206 | for ( ResolvExpr::Alternative & alt : lhs ) { |
---|
| 207 | // every LHS value must be a reference - some come in with a cast expression, if it doesn't just cast to reference here. |
---|
| 208 | // TODO: can this somehow be merge with the cast code directly above? |
---|
| 209 | if ( ! dynamic_cast< ReferenceType * >( alt.expr->get_result() ) ) { |
---|
| 210 | alt.expr = new CastExpr( alt.expr, new ReferenceType( Type::Qualifiers(), alt.expr->get_result()->clone() ) ); |
---|
| 211 | } |
---|
| 212 | } |
---|
[3c13c03] | 213 | } |
---|
| 214 | |
---|
[b3b2077] | 215 | TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) { |
---|
[65660bd] | 216 | assert( alts.size() == 1 || alts.size() == 2 ); |
---|
| 217 | if ( alts.size() == 2 ) { |
---|
| 218 | rhs.push_back( alts.back() ); |
---|
| 219 | } |
---|
[51587aa] | 220 | } |
---|
| 221 | |
---|
[65660bd] | 222 | TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) { |
---|
[3c13c03] | 223 | // explode the rhs so that each field of the tuple-valued-expr is assigned. |
---|
[f831177] | 224 | explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true ); |
---|
[51587aa] | 225 | } |
---|
| 226 | |
---|
[65660bd] | 227 | UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) { |
---|
| 228 | assert( left ); |
---|
[5af62f1] | 229 | std::list< Expression * > args; |
---|
[e6cee92] | 230 | args.push_back( new VariableExpr( left ) ); |
---|
[65660bd] | 231 | // args.push_back( new AddressExpr( new VariableExpr( left ) ) ); |
---|
| 232 | if ( right ) args.push_back( new VariableExpr( right ) ); |
---|
| 233 | return new UntypedExpr( new NameExpr( fname ), args ); |
---|
[51587aa] | 234 | } |
---|
| 235 | |
---|
[1d2b64f] | 236 | // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator. |
---|
| 237 | // xxx - maybe this should happen in alternative finder for every StmtExpr? |
---|
| 238 | // xxx - it's possible that these environments could contain some useful information. Maybe the right thing to do is aggregate the environments and pass the aggregate back to be added into the compositeEnv |
---|
| 239 | struct EnvRemover : public Visitor { |
---|
| 240 | virtual void visit( ExprStmt * stmt ) { |
---|
| 241 | delete stmt->get_expr()->get_env(); |
---|
| 242 | stmt->get_expr()->set_env( nullptr ); |
---|
| 243 | Visitor::visit( stmt ); |
---|
| 244 | } |
---|
| 245 | }; |
---|
| 246 | |
---|
| 247 | ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) { |
---|
[aa8f9df] | 248 | assert( expr->has_result() && ! expr->get_result()->isVoid() ); |
---|
[68fe077a] | 249 | ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) ); |
---|
[e6cee92] | 250 | // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient. |
---|
| 251 | if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) { |
---|
| 252 | ConstructorInit * ctorInit = InitTweak::genCtorInit( ret ); |
---|
| 253 | ret->set_init( ctorInit ); |
---|
| 254 | ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object |
---|
| 255 | EnvRemover rm; // remove environments from subexpressions of StmtExprs |
---|
| 256 | ctorInit->accept( rm ); |
---|
| 257 | } |
---|
[1d2b64f] | 258 | return ret; |
---|
[6eb8948] | 259 | } |
---|
| 260 | |
---|
[5af62f1] | 261 | void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) { |
---|
[6eb8948] | 262 | static UniqueName lhsNamer( "__massassign_L" ); |
---|
| 263 | static UniqueName rhsNamer( "__massassign_R" ); |
---|
[f831177] | 264 | // empty tuple case falls into this matcher, hence the second part of the assert |
---|
| 265 | assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) ); |
---|
[51587aa] | 266 | |
---|
[65660bd] | 267 | ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr; |
---|
[3c13c03] | 268 | for ( ResolvExpr::Alternative & lhsAlt : lhs ) { |
---|
[f831177] | 269 | // create a temporary object for each value in the lhs and create a call involving the rhs |
---|
[65660bd] | 270 | ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr ); |
---|
| 271 | out.push_back( createFunc( spotter.fname, ltmp, rtmp ) ); |
---|
[6eb8948] | 272 | tmpDecls.push_back( ltmp ); |
---|
[5af62f1] | 273 | } |
---|
[65660bd] | 274 | if ( rtmp ) tmpDecls.push_back( rtmp ); |
---|
[51b7345] | 275 | } |
---|
| 276 | |
---|
[5af62f1] | 277 | void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) { |
---|
[6eb8948] | 278 | static UniqueName lhsNamer( "__multassign_L" ); |
---|
| 279 | static UniqueName rhsNamer( "__multassign_R" ); |
---|
[b3b2077] | 280 | |
---|
[51587aa] | 281 | if ( lhs.size() == rhs.size() ) { |
---|
[f831177] | 282 | // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls |
---|
[6eb8948] | 283 | std::list< ObjectDecl * > ltmp; |
---|
| 284 | std::list< ObjectDecl * > rtmp; |
---|
[1d2b64f] | 285 | std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){ |
---|
[65660bd] | 286 | return newObject( lhsNamer, alt.expr ); |
---|
[6eb8948] | 287 | }); |
---|
[1d2b64f] | 288 | std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){ |
---|
[3c13c03] | 289 | return newObject( rhsNamer, alt.expr ); |
---|
[6eb8948] | 290 | }); |
---|
[65660bd] | 291 | zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } ); |
---|
[6eb8948] | 292 | tmpDecls.splice( tmpDecls.end(), ltmp ); |
---|
| 293 | tmpDecls.splice( tmpDecls.end(), rtmp ); |
---|
[5af62f1] | 294 | } |
---|
[51587aa] | 295 | } |
---|
[51b7345] | 296 | } // namespace Tuples |
---|
[51587aa] | 297 | |
---|
| 298 | // Local Variables: // |
---|
| 299 | // tab-width: 4 // |
---|
| 300 | // mode: c++ // |
---|
| 301 | // compile-command: "make install" // |
---|
| 302 | // End: // |
---|