source: src/Tuples/TupleAssignment.cc@ b226721

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 b226721 was f5854507, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

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