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