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