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 : Mon May 18 15:02:53 2015 |
---|
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 "Common/SemanticError.h" |
---|
23 | |
---|
24 | #include <functional> |
---|
25 | #include <algorithm> |
---|
26 | #include <iterator> |
---|
27 | #include <iostream> |
---|
28 | #include <cassert> |
---|
29 | #include <set> |
---|
30 | #include <unordered_set> |
---|
31 | |
---|
32 | namespace Tuples { |
---|
33 | class TupleAssignSpotter { |
---|
34 | public: |
---|
35 | // dispatcher for Tuple (multiple and mass) assignment operations |
---|
36 | TupleAssignSpotter( ResolvExpr::AlternativeFinder & ); |
---|
37 | void spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ); |
---|
38 | |
---|
39 | private: |
---|
40 | void match(); |
---|
41 | // records for assignment generation |
---|
42 | struct Options { |
---|
43 | void print( std::ostream & ); |
---|
44 | int size() const { return options.size(); } |
---|
45 | bool empty() const { return options.empty(); } |
---|
46 | typedef std::list< ResolvExpr::AltList >::iterator iterator; |
---|
47 | iterator begin() { return options.begin(); } |
---|
48 | iterator end() { return options.end(); } |
---|
49 | |
---|
50 | std::list< ResolvExpr::AltList > options; |
---|
51 | }; |
---|
52 | |
---|
53 | struct Matcher { |
---|
54 | public: |
---|
55 | Matcher( TupleAssignSpotter &spotter, Expression *_lhs, Expression *_rhs ); |
---|
56 | virtual ~Matcher() {} |
---|
57 | virtual void match( std::list< Expression * > &out ) = 0; |
---|
58 | std::list< Expression * > lhs, rhs; |
---|
59 | TupleAssignSpotter &spotter; |
---|
60 | std::list< ObjectDecl * > tmpDecls; |
---|
61 | }; |
---|
62 | |
---|
63 | struct MassAssignMatcher : public Matcher { |
---|
64 | public: |
---|
65 | MassAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) { |
---|
66 | this->rhs.push_back( rhs ); |
---|
67 | } |
---|
68 | virtual void match( std::list< Expression * > &out ); |
---|
69 | }; |
---|
70 | |
---|
71 | struct MultipleAssignMatcher : public Matcher { |
---|
72 | public: |
---|
73 | MultipleAssignMatcher( TupleAssignSpotter &spot, Expression *lhs, Expression *rhs ); |
---|
74 | virtual void match( std::list< Expression * > &out ); |
---|
75 | }; |
---|
76 | |
---|
77 | ResolvExpr::AlternativeFinder ¤tFinder; |
---|
78 | // Expression *rhs, *lhs; |
---|
79 | Matcher *matcher = nullptr; |
---|
80 | Options options; |
---|
81 | }; |
---|
82 | |
---|
83 | bool isTupleVar( DeclarationWithType *decl ) { |
---|
84 | return dynamic_cast< TupleType * >( decl->get_type() ); |
---|
85 | } |
---|
86 | |
---|
87 | /// true if expr is an expression of tuple type, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function |
---|
88 | bool isTuple( Expression *expr ) { |
---|
89 | if ( ! expr ) return false; |
---|
90 | assert( expr->has_result() ); |
---|
91 | // xxx - used to include cast to varExpr and call to isTupleVar, but this doesn't seem like it should be necessary |
---|
92 | return dynamic_cast<TupleExpr *>(expr) || expr->get_result()->size() > 1; |
---|
93 | } |
---|
94 | |
---|
95 | bool pointsToTuple( Expression *expr ) { |
---|
96 | // also check for function returning tuple of reference types |
---|
97 | if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) { |
---|
98 | return isTuple( addr->get_arg() ); |
---|
99 | } |
---|
100 | return false; |
---|
101 | } |
---|
102 | |
---|
103 | bool isTupleExpr( Expression *expr ) { |
---|
104 | assert( expr->has_result() ); |
---|
105 | return expr->get_result()->size() > 1; |
---|
106 | } |
---|
107 | |
---|
108 | void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, 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, std::list<ResolvExpr::AltList> &possibilities ) { |
---|
117 | if ( NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) { |
---|
118 | if ( assgnop->get_name() == std::string("?=?") ) { |
---|
119 | for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) { |
---|
120 | assert( ali->size() == 2 ); |
---|
121 | ResolvExpr::Alternative op1 = ali->front(), op2 = ali->back(); |
---|
122 | |
---|
123 | MultipleAssignMatcher multiMatcher( *this, op1.expr, op2.expr ); |
---|
124 | MassAssignMatcher massMatcher( *this, op1.expr, op2.expr ); |
---|
125 | if ( pointsToTuple(op1.expr) ) { // also handles tuple vars |
---|
126 | if ( isTuple( op2.expr ) ) { |
---|
127 | matcher = &multiMatcher; |
---|
128 | } else { |
---|
129 | // mass assignment |
---|
130 | matcher = &massMatcher; |
---|
131 | } |
---|
132 | match(); |
---|
133 | } else if ( isTuple( op2.expr ) ) { |
---|
134 | throw SemanticError("Cannot assign a tuple value into a non-tuple lvalue.", expr); |
---|
135 | } |
---|
136 | } |
---|
137 | } |
---|
138 | } |
---|
139 | } |
---|
140 | |
---|
141 | void TupleAssignSpotter::match() { |
---|
142 | assert ( matcher != 0 ); |
---|
143 | |
---|
144 | std::list< Expression * > new_assigns; |
---|
145 | matcher->match( new_assigns ); |
---|
146 | |
---|
147 | if ( new_assigns.empty() ) return; |
---|
148 | ResolvExpr::AltList current; |
---|
149 | // now resolve new assignments |
---|
150 | for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { |
---|
151 | ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() ); |
---|
152 | finder.findWithAdjustment(*i); |
---|
153 | // prune expressions that don't coincide with |
---|
154 | ResolvExpr::AltList alts = finder.get_alternatives(); |
---|
155 | assert( alts.size() == 1 ); |
---|
156 | assert( alts.front().expr != 0 ); |
---|
157 | current.push_back( alts.front() ); |
---|
158 | } |
---|
159 | |
---|
160 | // extract expressions from the assignment alternatives to produce a list of assignments that |
---|
161 | // together form a single alternative |
---|
162 | std::list< Expression *> solved_assigns; |
---|
163 | for ( ResolvExpr::Alternative & alt : current ) { |
---|
164 | solved_assigns.push_back( alt.expr->clone() ); |
---|
165 | } |
---|
166 | // xxx - need to do this?? |
---|
167 | // TypeEnvironment compositeEnv; |
---|
168 | // simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); |
---|
169 | currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), currentFinder.get_environ(), ResolvExpr::sumCost( current ) ) ); |
---|
170 | } |
---|
171 | |
---|
172 | TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : spotter(spotter) { |
---|
173 | // xxx - shouldn't need to be &<tuple-expr>, just &<lvalue-tuple-type> |
---|
174 | if (AddressExpr *addr = dynamic_cast<AddressExpr *>(lhs) ) |
---|
175 | if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) ) |
---|
176 | std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->lhs) ); |
---|
177 | } |
---|
178 | |
---|
179 | TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) { |
---|
180 | |
---|
181 | if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(rhs) ) |
---|
182 | std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->rhs) ); |
---|
183 | } |
---|
184 | |
---|
185 | UntypedExpr * createAssgn( ObjectDecl *left, ObjectDecl *right ) { |
---|
186 | assert( left && right ); |
---|
187 | std::list< Expression * > args; |
---|
188 | args.push_back( new AddressExpr( new UntypedExpr( new NameExpr("*?"), std::list< Expression * >{ new VariableExpr( left ) } ) ) ); |
---|
189 | args.push_back( new VariableExpr( right ) ); |
---|
190 | return new UntypedExpr( new NameExpr( "?=?" ), args ); |
---|
191 | } |
---|
192 | |
---|
193 | ObjectDecl * newObject( UniqueName & namer, Expression * expr ) { |
---|
194 | assert( expr->has_result() && ! expr->get_result()->isVoid() ); |
---|
195 | return new ObjectDecl( namer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) ); |
---|
196 | } |
---|
197 | |
---|
198 | void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) { |
---|
199 | static UniqueName lhsNamer( "__massassign_L" ); |
---|
200 | static UniqueName rhsNamer( "__massassign_R" ); |
---|
201 | assert ( ! lhs.empty() && rhs.size() == 1); |
---|
202 | |
---|
203 | ObjectDecl * rtmp = newObject( rhsNamer, rhs.front() ); |
---|
204 | for ( Expression * l : lhs ) { |
---|
205 | ObjectDecl * ltmp = newObject( lhsNamer, new AddressExpr( l ) ); |
---|
206 | out.push_back( createAssgn( ltmp, rtmp ) ); |
---|
207 | tmpDecls.push_back( ltmp ); |
---|
208 | } |
---|
209 | tmpDecls.push_back( rtmp ); |
---|
210 | } |
---|
211 | |
---|
212 | void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) { |
---|
213 | static UniqueName lhsNamer( "__multassign_L" ); |
---|
214 | static UniqueName rhsNamer( "__multassign_R" ); |
---|
215 | // xxx - need more complicated matching? |
---|
216 | if ( lhs.size() == rhs.size() ) { |
---|
217 | std::list< ObjectDecl * > ltmp; |
---|
218 | std::list< ObjectDecl * > rtmp; |
---|
219 | std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), []( Expression * expr ){ |
---|
220 | return newObject( lhsNamer, new AddressExpr( expr ) ); |
---|
221 | }); |
---|
222 | std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), []( Expression * expr ){ |
---|
223 | return newObject( rhsNamer, expr ); |
---|
224 | }); |
---|
225 | zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), createAssgn ); |
---|
226 | tmpDecls.splice( tmpDecls.end(), ltmp ); |
---|
227 | tmpDecls.splice( tmpDecls.end(), rtmp ); |
---|
228 | } |
---|
229 | } |
---|
230 | |
---|
231 | void TupleAssignSpotter::Options::print( std::ostream &ostr ) { |
---|
232 | for ( ResolvExpr::AltList & l : options ) { |
---|
233 | for ( ResolvExpr::Alternative & alt : l ) { |
---|
234 | alt.print( ostr ); |
---|
235 | ostr << " "; |
---|
236 | } |
---|
237 | ostr << std::endl; |
---|
238 | } // for |
---|
239 | } |
---|
240 | } // namespace Tuples |
---|
241 | |
---|
242 | // Local Variables: // |
---|
243 | // tab-width: 4 // |
---|
244 | // mode: c++ // |
---|
245 | // compile-command: "make install" // |
---|
246 | // End: // |
---|