source: src/Tuples/TupleAssignment.cc@ e50e9ff

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 e50e9ff was 03321e4, checked in by Thierry Delisle <tdelisle@…>, 8 years ago

Fixed headers for tuples folder
  • Property mode set to 100644
File size: 12.9 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 "Common/UniqueName.h" // for UniqueName
24#include "Common/utility.h" // for zipWith
25#include "Explode.h" // for explode
26#include "InitTweak/GenInit.h" // for genCtorInit
27#include "InitTweak/InitTweak.h" // for getPointerBase, isAssignment
28#include "Parser/LinkageSpec.h" // for Cforall
29#include "ResolvExpr/Alternative.h" // for AltList, Alternative
30#include "ResolvExpr/AlternativeFinder.h" // for AlternativeFinder, simpleC...
31#include "ResolvExpr/Cost.h" // for Cost
32#include "ResolvExpr/Resolver.h" // for resolveCtorInit
33#include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment
34#include "SynTree/Declaration.h" // for ObjectDecl
35#include "SynTree/Expression.h" // for Expression, CastExpr, Name...
36#include "SynTree/Initializer.h" // for ConstructorInit, SingleInit
37#include "SynTree/Statement.h" // for ExprStmt
38#include "SynTree/Type.h" // for Type, Type::Qualifiers
39#include "SynTree/TypeSubstitution.h" // for TypeSubstitution
40#include "SynTree/Visitor.h" // for Visitor
41
42namespace Tuples {
43 class TupleAssignSpotter {
44 public:
45 // dispatcher for Tuple (multiple and mass) assignment operations
46 TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
47 void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
48
49 private:
50 void match();
51
52 struct Matcher {
53 public:
54 Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
55 virtual ~Matcher() {}
56 virtual void match( std::list< Expression * > &out ) = 0;
57 ObjectDecl * newObject( UniqueName & namer, Expression * expr );
58 ResolvExpr::AltList lhs, rhs;
59 TupleAssignSpotter &spotter;
60 ResolvExpr::Cost baseCost;
61 std::list< ObjectDecl * > tmpDecls;
62 ResolvExpr::TypeEnvironment compositeEnv;
63 };
64
65 struct MassAssignMatcher : public Matcher {
66 public:
67 MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
68 virtual void match( std::list< Expression * > &out );
69 };
70
71 struct MultipleAssignMatcher : public Matcher {
72 public:
73 MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
74 virtual void match( std::list< Expression * > &out );
75 };
76
77 ResolvExpr::AlternativeFinder &currentFinder;
78 std::string fname;
79 std::unique_ptr< Matcher > matcher;
80 };
81
82 /// true if expr is an expression of tuple type
83 bool isTuple( Expression *expr ) {
84 if ( ! expr ) return false;
85 assert( expr->has_result() );
86 return dynamic_cast< TupleType * >( expr->get_result() );
87 }
88
89 template< typename AltIter >
90 bool isMultAssign( AltIter begin, AltIter end ) {
91 // multiple assignment if more than one alternative in the range or if
92 // the alternative is a tuple
93 if ( begin == end ) return false;
94 if ( isTuple( begin->expr ) ) return true;
95 return ++begin != end;
96 }
97
98 bool pointsToTuple( Expression *expr ) {
99 // also check for function returning tuple of reference types
100 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
101 return pointsToTuple( castExpr->get_arg() );
102 } else if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
103 return isTuple( addr->get_arg() );
104 }
105 return false;
106 }
107
108 void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
109 TupleAssignSpotter spotter( currentFinder );
110 spotter.spot( expr, possibilities );
111 }
112
113 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
114 : currentFinder(f) {}
115
116 void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
117 if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
118 if ( InitTweak::isCtorDtorAssign( op->get_name() ) ) {
119 fname = op->get_name();
120 for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
121 if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
122 if ( ali->size() <= 1 && InitTweak::isAssignment( op->get_name() ) ) {
123 // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
124 continue;
125 }
126
127 assert( ! ali->empty() );
128 // grab args 2-N and group into a TupleExpr
129 const ResolvExpr::Alternative & alt1 = ali->front();
130 auto begin = std::next(ali->begin(), 1), end = ali->end();
131 if ( pointsToTuple(alt1.expr) ) {
132 if ( isMultAssign( begin, end ) ) {
133 matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
134 } else {
135 // mass assignment
136 matcher.reset( new MassAssignMatcher( *this, *ali ) );
137 }
138 match();
139 }
140 }
141 }
142 }
143 }
144
145 void TupleAssignSpotter::match() {
146 assert ( matcher != 0 );
147
148 std::list< Expression * > new_assigns;
149 matcher->match( new_assigns );
150
151 if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
152 // if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
153 // if not the empty tuple case, return early so that no new alternatives are generated.
154 if ( new_assigns.empty() ) return;
155 }
156 ResolvExpr::AltList current;
157 // now resolve new assignments
158 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
159 ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
160 try {
161 finder.findWithAdjustment(*i);
162 } catch (...) {
163 return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
164 }
165 // prune expressions that don't coincide with
166 ResolvExpr::AltList alts = finder.get_alternatives();
167 assert( alts.size() == 1 );
168 assert( alts.front().expr != 0 );
169 current.push_back( alts.front() );
170 }
171
172 // extract expressions from the assignment alternatives to produce a list of assignments that
173 // together form a single alternative
174 std::list< Expression *> solved_assigns;
175 for ( ResolvExpr::Alternative & alt : current ) {
176 solved_assigns.push_back( alt.expr->clone() );
177 }
178 // combine assignment environments into combined expression environment
179 simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
180 currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current ) + matcher->baseCost ) );
181 }
182
183 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
184 assert( ! alts.empty() );
185 // combine argument environments into combined expression environment
186 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
187
188 ResolvExpr::Alternative lhsAlt = alts.front();
189 // peel off the cast that exists on ctor/dtor expressions
190 bool isCast = false;
191 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
192 lhsAlt.expr = castExpr->get_arg();
193 castExpr->set_arg( nullptr );
194 delete castExpr;
195 isCast = true;
196 }
197
198 // explode the lhs so that each field of the tuple-valued-expr is assigned.
199 explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
200
201 // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
202 if ( isCast ) {
203 for ( ResolvExpr::Alternative & alt : lhs ) {
204 Expression *& expr = alt.expr;
205 Type * castType = expr->get_result()->clone();
206 Type * type = InitTweak::getPointerBase( castType );
207 assert( type );
208 type->get_qualifiers() -= Type::Qualifiers( Type::Const | Type::Volatile | Type::Restrict | Type::Atomic );
209 type->set_lvalue( true ); // xxx - might not need this
210 expr = new CastExpr( expr, castType );
211 }
212 }
213 }
214
215 TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
216 assert( alts.size() == 1 || alts.size() == 2 );
217 if ( alts.size() == 2 ) {
218 rhs.push_back( alts.back() );
219 }
220 }
221
222 TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
223 // explode the rhs so that each field of the tuple-valued-expr is assigned.
224 explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
225 }
226
227 UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
228 assert( left );
229 std::list< Expression * > args;
230 args.push_back( new AddressExpr( UntypedExpr::createDeref( new VariableExpr( left ) ) ) );
231 // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
232 if ( right ) args.push_back( new VariableExpr( right ) );
233 return new UntypedExpr( new NameExpr( fname ), args );
234 }
235
236 // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
237 // xxx - maybe this should happen in alternative finder for every StmtExpr?
238 // 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
239 struct EnvRemover : public Visitor {
240 virtual void visit( ExprStmt * stmt ) {
241 delete stmt->get_expr()->get_env();
242 stmt->get_expr()->set_env( nullptr );
243 Visitor::visit( stmt );
244 }
245 };
246
247 ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
248 assert( expr->has_result() && ! expr->get_result()->isVoid() );
249 ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
250 ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
251 ret->set_init( ctorInit );
252 ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
253 EnvRemover rm; // remove environments from subexpressions of StmtExprs
254 ctorInit->accept( rm );
255 return ret;
256 }
257
258 void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
259 static UniqueName lhsNamer( "__massassign_L" );
260 static UniqueName rhsNamer( "__massassign_R" );
261 // empty tuple case falls into this matcher, hence the second part of the assert
262 assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );
263
264 ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
265 for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
266 // create a temporary object for each value in the lhs and create a call involving the rhs
267 ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
268 out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
269 tmpDecls.push_back( ltmp );
270 }
271 if ( rtmp ) tmpDecls.push_back( rtmp );
272 }
273
274 void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
275 static UniqueName lhsNamer( "__multassign_L" );
276 static UniqueName rhsNamer( "__multassign_R" );
277
278 if ( lhs.size() == rhs.size() ) {
279 // produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
280 std::list< ObjectDecl * > ltmp;
281 std::list< ObjectDecl * > rtmp;
282 std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
283 return newObject( lhsNamer, alt.expr );
284 });
285 std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
286 return newObject( rhsNamer, alt.expr );
287 });
288 zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
289 tmpDecls.splice( tmpDecls.end(), ltmp );
290 tmpDecls.splice( tmpDecls.end(), rtmp );
291 }
292 }
293} // namespace Tuples
294
295// Local Variables: //
296// tab-width: 4 //
297// mode: c++ //
298// compile-command: "make install" //
299// End: //
Note: See TracBrowser for help on using the repository browser.