source: src/Tuples/TupleAssignment.cc@ 5f95b5f

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 5f95b5f was 9058414, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

Generate reference assignment for reference component of a tuple assignment

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