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