source: src/Tuples/TupleAssignment.cc@ 6ba16fa

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 6ba16fa was 82f3226, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

Remove trailing whitespace in TupleAssignment
  • Property mode set to 100644
File size: 13.7 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#include <vector>
23
24#include "CodeGen/OperatorTable.h"
25#include "Common/PassVisitor.h"
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
37#include "ResolvExpr/typeops.h" // for combos
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
45
46#if 0
47#define PRINT(x) x
48#else
49#define PRINT(x)
50#endif
51
52namespace Tuples {
53 class TupleAssignSpotter {
54 public:
55 // dispatcher for Tuple (multiple and mass) assignment operations
56 TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
57 void spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args );
58
59 private:
60 void match();
61
62 struct Matcher {
63 public:
64 Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const
65 ResolvExpr::AltList& rhs );
66 virtual ~Matcher() {}
67 virtual void match( std::list< Expression * > &out ) = 0;
68 ObjectDecl * newObject( UniqueName & namer, Expression * expr );
69 ResolvExpr::AltList lhs, rhs;
70 TupleAssignSpotter &spotter;
71 ResolvExpr::Cost baseCost;
72 std::list< ObjectDecl * > tmpDecls;
73 ResolvExpr::TypeEnvironment compositeEnv;
74 };
75
76 struct MassAssignMatcher : public Matcher {
77 public:
78 MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
79 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
80 virtual void match( std::list< Expression * > &out );
81 };
82
83 struct MultipleAssignMatcher : public Matcher {
84 public:
85 MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
86 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
87 virtual void match( std::list< Expression * > &out );
88 };
89
90 ResolvExpr::AlternativeFinder &currentFinder;
91 std::string fname;
92 std::unique_ptr< Matcher > matcher;
93 };
94
95 /// true if expr is an expression of tuple type
96 bool isTuple( Expression *expr ) {
97 if ( ! expr ) return false;
98 assert( expr->result );
99 return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
100 }
101
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
111 bool refToTuple( Expression *expr ) {
112 assert( expr->get_result() );
113 // also check for function returning tuple of reference types
114 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
115 return refToTuple( castExpr->get_arg() );
116 } else {
117 return isTuple( expr );
118 }
119 return false;
120 }
121
122 void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
123 std::vector<ResolvExpr::AlternativeFinder> &args ) {
124 TupleAssignSpotter spotter( currentFinder );
125 spotter.spot( expr, args );
126 }
127
128 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
129 : currentFinder(f) {}
130
131 void TupleAssignSpotter::spot( UntypedExpr * expr,
132 std::vector<ResolvExpr::AlternativeFinder> &args ) {
133 if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
134 if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
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
140 // if an assignment only takes 1 argument, that's odd, but maybe someone wrote
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
149 // explode is aware of casts - ensure every LHS expression is sent into explode
150 // with a reference cast
151 // xxx - this seems to change the alternatives before the normal
152 // AlternativeFinder flow; maybe this is desired?
153 if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
154 lhsAlt.expr = new CastExpr( lhsAlt.expr,
155 new ReferenceType( Type::Qualifiers(),
156 lhsAlt.expr->get_result()->clone() ) );
157 }
158
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 ) {
163 // each LHS value must be a reference - some come in with a cast expression,
164 // if not just cast to reference here
165 if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
166 alt.expr = new CastExpr( alt.expr,
167 new ReferenceType( Type::Qualifiers(),
168 alt.expr->get_result()->clone() ) );
169 }
170 }
171
172 if ( args.size() == 1 ) {
173 // mass default-initialization/destruction
174 ResolvExpr::AltList rhs{};
175 matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
176 match();
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;
181 combos( std::next(args.begin(), 1), args.end(),
182 std::back_inserter( rhsAlts ) );
183 for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
184 // multiple assignment
185 ResolvExpr::AltList rhs;
186 explode( rhsAlt, currentFinder.get_indexer(),
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
196 explode( rhsAlt, currentFinder.get_indexer(),
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 }
206 }
207 }
208 }
209 }
210 }
211
212 void TupleAssignSpotter::match() {
213 assert ( matcher != 0 );
214
215 std::list< Expression * > new_assigns;
216 matcher->match( new_assigns );
217
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 }
223 ResolvExpr::AltList current;
224 // now resolve new assignments
225 for ( std::list< Expression * >::iterator i = new_assigns.begin();
226 i != new_assigns.end(); ++i ) {
227 PRINT(
228 std::cerr << "== resolving tuple assign ==" << std::endl;
229 std::cerr << *i << std::endl;
230 )
231
232 ResolvExpr::AlternativeFinder finder{ currentFinder.get_indexer(),
233 currentFinder.get_environ() };
234 try {
235 finder.findWithAdjustment(*i);
236 } catch (...) {
237 return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
238 }
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 );
243 current.push_back( alts.front() );
244 }
245
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 }
252 // combine assignment environments into combined expression environment
253 simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
254 // xxx -- was push_front
255 currentFinder.get_alternatives().push_back( ResolvExpr::Alternative(
256 new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
257 ResolvExpr::sumCost( current ) + matcher->baseCost ) );
258 }
259
260 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
261 const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
262 : lhs(lhs), rhs(rhs), spotter(spotter),
263 baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
264 simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
265 simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
266 }
267
268 UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
269 assert( left );
270 std::list< Expression * > args;
271 args.push_back( new VariableExpr( left ) );
272 // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
273 if ( right ) args.push_back( new VariableExpr( right ) );
274 return new UntypedExpr( new NameExpr( fname ), args );
275 }
276
277 // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
278 // xxx - maybe this should happen in alternative finder for every StmtExpr?
279 // 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
280 struct EnvRemover {
281 void previsit( ExprStmt * stmt ) {
282 delete stmt->expr->env;
283 stmt->expr->env = nullptr;
284 }
285 };
286
287 ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
288 assert( expr->result && ! expr->get_result()->isVoid() );
289 ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
290 // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
291 if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
292 ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
293 ret->set_init( ctorInit );
294 ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
295 PassVisitor<EnvRemover> rm; // remove environments from subexpressions of StmtExprs
296 ctorInit->accept( rm );
297 }
298 PRINT( std::cerr << "new object: " << ret << std::endl; )
299 return ret;
300 }
301
302 void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
303 static UniqueName lhsNamer( "__massassign_L" );
304 static UniqueName rhsNamer( "__massassign_R" );
305 // empty tuple case falls into this matcher, hence the second part of the assert
306 assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
307
308 ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
309 for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
310 // create a temporary object for each value in the lhs and create a call involving the rhs
311 ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
312 out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
313 tmpDecls.push_back( ltmp );
314 }
315 if ( rtmp ) tmpDecls.push_back( rtmp );
316 }
317
318 void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
319 static UniqueName lhsNamer( "__multassign_L" );
320 static UniqueName rhsNamer( "__multassign_R" );
321
322 if ( lhs.size() == rhs.size() ) {
323 // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
324 std::list< ObjectDecl * > ltmp;
325 std::list< ObjectDecl * > rtmp;
326 std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
327 return newObject( lhsNamer, alt.expr );
328 });
329 std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
330 return newObject( rhsNamer, alt.expr );
331 });
332 zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
333 tmpDecls.splice( tmpDecls.end(), ltmp );
334 tmpDecls.splice( tmpDecls.end(), rtmp );
335 }
336 }
337} // namespace Tuples
338
339// Local Variables: //
340// tab-width: 4 //
341// mode: c++ //
342// compile-command: "make install" //
343// End: //
Note: See TracBrowser for help on using the repository browser.