source: src/Tuples/TupleAssignment.cc@ 0c286cf

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 0c286cf was 1d2b64f, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

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