source: src/Tuples/TupleAssignment.cc@ c8771e9

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 c8771e9 was bd4f2e9, checked in by Aaron Moss <a3moss@…>, 8 years ago

Switch AltList to std::vector from std::list
  • Property mode set to 100644
File size: 13.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#include <vector>
23
24#include "CodeGen/OperatorTable.h"
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
36#include "ResolvExpr/typeops.h" // for combos
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
44
45#if 0
46#define PRINT(x) x
47#else
48#define PRINT(x)
49#endif
50
51namespace Tuples {
52 class TupleAssignSpotter {
53 public:
54 // dispatcher for Tuple (multiple and mass) assignment operations
55 TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
56 void spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args );
57
58 private:
59 void match();
60
61 struct Matcher {
62 public:
63 Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const
64 ResolvExpr::AltList& rhs );
65 virtual ~Matcher() {}
66 virtual void match( std::list< Expression * > &out ) = 0;
67 ObjectDecl * newObject( UniqueName & namer, Expression * expr );
68 ResolvExpr::AltList lhs, rhs;
69 TupleAssignSpotter &spotter;
70 ResolvExpr::Cost baseCost;
71 std::list< ObjectDecl * > tmpDecls;
72 ResolvExpr::TypeEnvironment compositeEnv;
73 };
74
75 struct MassAssignMatcher : public Matcher {
76 public:
77 MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
78 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
79 virtual void match( std::list< Expression * > &out );
80 };
81
82 struct MultipleAssignMatcher : public Matcher {
83 public:
84 MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
85 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
86 virtual void match( std::list< Expression * > &out );
87 };
88
89 ResolvExpr::AlternativeFinder &currentFinder;
90 std::string fname;
91 std::unique_ptr< Matcher > matcher;
92 };
93
94 /// true if expr is an expression of tuple type
95 bool isTuple( Expression *expr ) {
96 if ( ! expr ) return false;
97 assert( expr->result );
98 return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
99 }
100
101 template< typename AltIter >
102 bool isMultAssign( AltIter begin, AltIter end ) {
103 // multiple assignment if more than one alternative in the range or if
104 // the alternative is a tuple
105 if ( begin == end ) return false;
106 if ( isTuple( begin->expr ) ) return true;
107 return ++begin != end;
108 }
109
110 bool refToTuple( Expression *expr ) {
111 assert( expr->get_result() );
112 // also check for function returning tuple of reference types
113 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
114 return refToTuple( castExpr->get_arg() );
115 } else {
116 return isTuple( expr );
117 }
118 return false;
119 }
120
121 void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
122 std::vector<ResolvExpr::AlternativeFinder> &args ) {
123 TupleAssignSpotter spotter( currentFinder );
124 spotter.spot( expr, args );
125 }
126
127 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
128 : currentFinder(f) {}
129
130 void TupleAssignSpotter::spot( UntypedExpr * expr,
131 std::vector<ResolvExpr::AlternativeFinder> &args ) {
132 if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
133 if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
134 fname = op->get_name();
135
136 // AlternativeFinder will naturally handle this case case, if it's legal
137 if ( args.size() == 0 ) return;
138
139 // if an assignment only takes 1 argument, that's odd, but maybe someone wrote
140 // the function, in which case AlternativeFinder will handle it normally
141 if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return;
142
143 // look over all possible left-hand-sides
144 for ( ResolvExpr::Alternative& lhsAlt : args[0] ) {
145 // skip non-tuple LHS
146 if ( ! refToTuple(lhsAlt.expr) ) continue;
147
148 // explode is aware of casts - ensure every LHS expression is sent into explode
149 // with a reference cast
150 // xxx - this seems to change the alternatives before the normal
151 // AlternativeFinder flow; maybe this is desired?
152 if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
153 lhsAlt.expr = new CastExpr( lhsAlt.expr,
154 new ReferenceType( Type::Qualifiers(),
155 lhsAlt.expr->get_result()->clone() ) );
156 }
157
158 // explode the LHS so that each field of a tuple-valued-expr is assigned
159 ResolvExpr::AltList lhs;
160 explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true );
161 for ( ResolvExpr::Alternative& alt : lhs ) {
162 // each LHS value must be a reference - some come in with a cast expression,
163 // if not just cast to reference here
164 if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
165 alt.expr = new CastExpr( alt.expr,
166 new ReferenceType( Type::Qualifiers(),
167 alt.expr->get_result()->clone() ) );
168 }
169 }
170
171 if ( args.size() == 1 ) {
172 // mass default-initialization/destruction
173 ResolvExpr::AltList rhs{};
174 matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
175 match();
176 } else if ( args.size() > 2 ) {
177 // expand all possible RHS possibilities
178 // TODO build iterative version of this instead of using combos
179 std::vector< ResolvExpr::AltList > rhsAlts;
180 combos( std::next(args.begin(), 1), args.end(),
181 std::back_inserter( rhsAlts ) );
182 for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
183 // multiple assignment
184 ResolvExpr::AltList rhs;
185 explode( rhsAlt, currentFinder.get_indexer(),
186 std::back_inserter(rhs), true );
187 matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
188 match();
189 }
190 } else {
191 for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) {
192 ResolvExpr::AltList rhs;
193 if ( isTuple(rhsAlt.expr) ) {
194 // multiple assignment
195 explode( rhsAlt, currentFinder.get_indexer(),
196 std::back_inserter(rhs), true );
197 matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
198 } else {
199 // mass assignment
200 rhs.push_back( rhsAlt );
201 matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
202 }
203 match();
204 }
205 }
206 }
207 }
208 }
209 }
210
211 void TupleAssignSpotter::match() {
212 assert ( matcher != 0 );
213
214 std::list< Expression * > new_assigns;
215 matcher->match( new_assigns );
216
217 if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
218 // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
219 // if not the empty tuple case, return early so that no new alternatives are generated.
220 if ( new_assigns.empty() ) return;
221 }
222 ResolvExpr::AltList current;
223 // now resolve new assignments
224 for ( std::list< Expression * >::iterator i = new_assigns.begin();
225 i != new_assigns.end(); ++i ) {
226 PRINT(
227 std::cerr << "== resolving tuple assign ==" << std::endl;
228 std::cerr << *i << std::endl;
229 )
230
231 ResolvExpr::AlternativeFinder finder{ currentFinder.get_indexer(),
232 currentFinder.get_environ() };
233 try {
234 finder.findWithAdjustment(*i);
235 } catch (...) {
236 return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
237 }
238 // prune expressions that don't coincide with
239 ResolvExpr::AltList alts = finder.get_alternatives();
240 assert( alts.size() == 1 );
241 assert( alts.front().expr != 0 );
242 current.push_back( alts.front() );
243 }
244
245 // extract expressions from the assignment alternatives to produce a list of assignments that
246 // together form a single alternative
247 std::list< Expression *> solved_assigns;
248 for ( ResolvExpr::Alternative & alt : current ) {
249 solved_assigns.push_back( alt.expr->clone() );
250 }
251 // combine assignment environments into combined expression environment
252 simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
253 // xxx -- was push_front
254 currentFinder.get_alternatives().push_back( ResolvExpr::Alternative(
255 new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
256 ResolvExpr::sumCost( current ) + matcher->baseCost ) );
257 }
258
259 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
260 const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
261 : lhs(lhs), rhs(rhs), spotter(spotter),
262 baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
263 simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
264 simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
265 }
266
267 UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
268 assert( left );
269 std::list< Expression * > args;
270 args.push_back( new VariableExpr( left ) );
271 // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
272 if ( right ) args.push_back( new VariableExpr( right ) );
273 return new UntypedExpr( new NameExpr( fname ), args );
274 }
275
276 // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
277 // xxx - maybe this should happen in alternative finder for every StmtExpr?
278 // 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
279 struct EnvRemover : public Visitor {
280 virtual void visit( ExprStmt * stmt ) {
281 delete stmt->get_expr()->get_env();
282 stmt->get_expr()->set_env( nullptr );
283 Visitor::visit( stmt );
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 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.