source: src/Tuples/TupleAssignment.cc@ b95fe40

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

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc
  • 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 currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(
254 new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
255 ResolvExpr::sumCost( current ) + matcher->baseCost ) );
256 }
257
258 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
259 const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
260 : lhs(lhs), rhs(rhs), spotter(spotter),
261 baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
262 simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
263 simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
264 }
265
266 UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
267 assert( left );
268 std::list< Expression * > args;
269 args.push_back( new VariableExpr( left ) );
270 // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
271 if ( right ) args.push_back( new VariableExpr( right ) );
272 return new UntypedExpr( new NameExpr( fname ), args );
273 }
274
275 // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
276 // xxx - maybe this should happen in alternative finder for every StmtExpr?
277 // 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
278 struct EnvRemover : public Visitor {
279 virtual void visit( ExprStmt * stmt ) {
280 delete stmt->get_expr()->get_env();
281 stmt->get_expr()->set_env( nullptr );
282 Visitor::visit( stmt );
283 }
284 };
285
286 ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
287 assert( expr->result && ! expr->get_result()->isVoid() );
288 ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
289 // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
290 if ( ! dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
291 ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
292 ret->set_init( ctorInit );
293 ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
294 EnvRemover rm; // remove environments from subexpressions of StmtExprs
295 ctorInit->accept( rm );
296 }
297 PRINT( std::cerr << "new object: " << ret << std::endl; )
298 return ret;
299 }
300
301 void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
302 static UniqueName lhsNamer( "__massassign_L" );
303 static UniqueName rhsNamer( "__massassign_R" );
304 // empty tuple case falls into this matcher, hence the second part of the assert
305 assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
306
307 ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
308 for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
309 // create a temporary object for each value in the lhs and create a call involving the rhs
310 ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
311 out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
312 tmpDecls.push_back( ltmp );
313 }
314 if ( rtmp ) tmpDecls.push_back( rtmp );
315 }
316
317 void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
318 static UniqueName lhsNamer( "__multassign_L" );
319 static UniqueName rhsNamer( "__multassign_R" );
320
321 if ( lhs.size() == rhs.size() ) {
322 // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
323 std::list< ObjectDecl * > ltmp;
324 std::list< ObjectDecl * > rtmp;
325 std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
326 return newObject( lhsNamer, alt.expr );
327 });
328 std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
329 return newObject( rhsNamer, alt.expr );
330 });
331 zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
332 tmpDecls.splice( tmpDecls.end(), ltmp );
333 tmpDecls.splice( tmpDecls.end(), rtmp );
334 }
335 }
336} // namespace Tuples
337
338// Local Variables: //
339// tab-width: 4 //
340// mode: c++ //
341// compile-command: "make install" //
342// End: //
Note: See TracBrowser for help on using the repository browser.