source: src/Tuples/TupleAssignment.cc@ 4cc9b13

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 4cc9b13 was 8135d4c, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

Merge branch 'master' into references
  • Property mode set to 100644
File size: 12.8 KB
Line 
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//
7// TupleAssignment.cc --
8//
9// Author : Rodolfo G. Esteves
10// Created On : Mon May 18 07:44:20 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Fri Mar 17 09:43:03 2017
13// Update Count : 8
14//
15
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
22
23#include "CodeGen/OperatorTable.h"
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
42
43namespace Tuples {
44 class TupleAssignSpotter {
45 public:
46 // dispatcher for Tuple (multiple and mass) assignment operations
47 TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
48 void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
49
50 private:
51 void match();
52
53 struct Matcher {
54 public:
55 Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
56 virtual ~Matcher() {}
57 virtual void match( std::list< Expression * > &out ) = 0;
58 ObjectDecl * newObject( UniqueName & namer, Expression * expr );
59 ResolvExpr::AltList lhs, rhs;
60 TupleAssignSpotter &spotter;
61 ResolvExpr::Cost baseCost;
62 std::list< ObjectDecl * > tmpDecls;
63 ResolvExpr::TypeEnvironment compositeEnv;
64 };
65
66 struct MassAssignMatcher : public Matcher {
67 public:
68 MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
69 virtual void match( std::list< Expression * > &out );
70 };
71
72 struct MultipleAssignMatcher : public Matcher {
73 public:
74 MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
75 virtual void match( std::list< Expression * > &out );
76 };
77
78 ResolvExpr::AlternativeFinder &currentFinder;
79 std::string fname;
80 std::unique_ptr< Matcher > matcher;
81 };
82
83 /// true if expr is an expression of tuple type
84 bool isTuple( Expression *expr ) {
85 if ( ! expr ) return false;
86 assert( expr->has_result() );
87 return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
88 }
89
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
99 bool refToTuple( Expression *expr ) {
100 assert( expr->get_result() );
101 // also check for function returning tuple of reference types
102 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
103 return refToTuple( castExpr->get_arg() );
104 } else {
105 return isTuple( expr );
106 }
107 return false;
108 }
109
110 void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
111 TupleAssignSpotter spotter( currentFinder );
112 spotter.spot( expr, possibilities );
113 }
114
115 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
116 : currentFinder(f) {}
117
118 void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
119 if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
120 if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
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
124 if ( ali->size() <= 1 && CodeGen::isAssignment( op->get_name() ) ) {
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 }
128
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();
133 if ( refToTuple(alt1.expr) ) {
134 if ( isMultAssign( begin, end ) ) {
135 matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
136 } else {
137 // mass assignment
138 matcher.reset( new MassAssignMatcher( *this, *ali ) );
139 }
140 match();
141 }
142 }
143 }
144 }
145 }
146
147 void TupleAssignSpotter::match() {
148 assert ( matcher != 0 );
149
150 std::list< Expression * > new_assigns;
151 matcher->match( new_assigns );
152
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 }
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() );
162 try {
163 finder.findWithAdjustment(*i);
164 } catch (...) {
165 return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
166 }
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 );
171 current.push_back( alts.front() );
172 }
173
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 }
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 ) );
183 }
184
185 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
186 assert( ! alts.empty() );
187 // combine argument environments into combined expression environment
188 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
189
190 ResolvExpr::Alternative lhsAlt = alts.front();
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() ) );
194 }
195
196 // explode the lhs so that each field of the tuple-valued-expr is assigned.
197 explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
198
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 }
205 }
206
207 TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
208 assert( alts.size() == 1 || alts.size() == 2 );
209 if ( alts.size() == 2 ) {
210 rhs.push_back( alts.back() );
211 }
212 }
213
214 TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
215 // explode the rhs so that each field of the tuple-valued-expr is assigned.
216 explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
217 }
218
219 UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
220 assert( left );
221 std::list< Expression * > args;
222 args.push_back( new VariableExpr( left ) );
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 );
226 }
227
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 ) {
240 assert( expr->has_result() && ! expr->get_result()->isVoid() );
241 ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
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 }
250 return ret;
251 }
252
253 void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
254 static UniqueName lhsNamer( "__massassign_L" );
255 static UniqueName rhsNamer( "__massassign_R" );
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()) );
258
259 ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
260 for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
261 // create a temporary object for each value in the lhs and create a call involving the rhs
262 ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
263 out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
264 tmpDecls.push_back( ltmp );
265 }
266 if ( rtmp ) tmpDecls.push_back( rtmp );
267 }
268
269 void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
270 static UniqueName lhsNamer( "__multassign_L" );
271 static UniqueName rhsNamer( "__multassign_R" );
272
273 if ( lhs.size() == rhs.size() ) {
274 // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
275 std::list< ObjectDecl * > ltmp;
276 std::list< ObjectDecl * > rtmp;
277 std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
278 return newObject( lhsNamer, alt.expr );
279 });
280 std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
281 return newObject( rhsNamer, alt.expr );
282 });
283 zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
284 tmpDecls.splice( tmpDecls.end(), ltmp );
285 tmpDecls.splice( tmpDecls.end(), rtmp );
286 }
287 }
288} // namespace Tuples
289
290// Local Variables: //
291// tab-width: 4 //
292// mode: c++ //
293// compile-command: "make install" //
294// End: //
Note: See TracBrowser for help on using the repository browser.