source: src/Tuples/TupleAssignment.cc@ 8f7cea1

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 8f7cea1 was 908cc83, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

make mass assignment resolve correctly
  • Property mode set to 100644
File size: 9.2 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 : 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 "TupleAssignment.h"
21#include "Common/SemanticError.h"
22
23#include <functional>
24#include <algorithm>
25#include <iterator>
26#include <iostream>
27#include <cassert>
28#include <set>
29#include <unordered_set>
30
31namespace Tuples {
32 class TupleAssignSpotter {
33 public:
34 // dispatcher for Tuple (multiple and mass) assignment operations
35 TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
36 void spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities );
37
38 private:
39 void match();
40 // records for assignment generation
41 struct Options {
42 std::list< ResolvExpr::AltList > get_best();
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 class Matcher {
54 public:
55 Matcher( TupleAssignSpotter &spotter, Expression *_lhs, Expression *_rhs );
56 virtual ~Matcher() {}
57 virtual void match( std::list< Expression * > &out ) = 0;
58 virtual void solve() = 0;
59 static UntypedExpr *createAssgn( Expression *left, Expression *right );
60 protected:
61 std::list< Expression * > lhs, rhs;
62 TupleAssignSpotter &spotter;
63 };
64
65 class MassAssignMatcher : public Matcher {
66 public:
67 MassAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) {
68 this->rhs.push_back( rhs );
69 }
70 virtual void match( std::list< Expression * > &out );
71 virtual void solve();
72 };
73
74 class MultipleAssignMatcher : public Matcher {
75 public:
76 MultipleAssignMatcher( TupleAssignSpotter &spot, Expression *lhs, Expression *rhs );
77 virtual void match( std::list< Expression * > &out );
78 virtual void solve();
79 };
80
81 ResolvExpr::AlternativeFinder &currentFinder;
82 Expression *rhs, *lhs;
83 Matcher *matcher = nullptr;
84 Options options;
85 };
86
87 bool isTupleVar( DeclarationWithType *decl ) {
88 return dynamic_cast< TupleType * >( decl->get_type() );
89 }
90
91 /// true if expr is an expression of tuple type, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function
92 bool isTuple( Expression *expr ) {
93 if ( ! expr ) return false;
94
95 // xxx - used to include cast to varExpr and call to isTupleVar, but this doesn't seem like it should be necessary
96 return dynamic_cast<TupleExpr *>(expr) || expr->get_results().size() > 1;
97 }
98
99 bool pointsToTuple( Expression *expr ) {
100 // also check for function returning tuple of reference types
101 if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
102 return isTuple( addr->get_arg() );
103 }
104 return false;
105 }
106
107 bool isTupleExpr( Expression *expr ) {
108 return expr->get_results().size() > 1;
109 }
110
111 void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
112 TupleAssignSpotter spotter( currentFinder );
113 spotter.spot( expr, possibilities );
114 }
115
116 TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
117 : currentFinder(f) {}
118
119 void TupleAssignSpotter::spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
120 if ( NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) {
121 if ( assgnop->get_name() == std::string("?=?") ) {
122 for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
123 assert( ali->size() == 2 );
124 ResolvExpr::Alternative op1 = ali->front(), op2 = ali->back();
125
126 MultipleAssignMatcher multiMatcher( *this, op1.expr, op2.expr );
127 MassAssignMatcher massMatcher( *this, op1.expr, op2.expr );
128 if ( pointsToTuple(op1.expr) ) { // also handles tuple vars
129 if ( isTuple( op2.expr ) ) {
130 matcher = &multiMatcher;
131 } else {
132 // mass assignment
133 matcher = &massMatcher;
134 }
135 match();
136 } else if ( isTuple( op2.expr ) ) {
137 throw SemanticError("Cannot assign a tuple value into a non-tuple lvalue.", expr);
138 }
139 }
140 }
141 }
142 }
143
144 void TupleAssignSpotter::match() {
145 assert ( matcher != 0 );
146
147 std::list< Expression * > new_assigns;
148 matcher->match( new_assigns );
149
150 if ( new_assigns.empty() ) return;
151 std::list< Expression * > solved_assigns;
152 ResolvExpr::AltList current;
153 // now resolve new assignments
154 for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
155 ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
156 finder.findWithAdjustment(*i);
157 // prune expressions that don't coincide with
158 ResolvExpr::AltList alts = finder.get_alternatives();
159 assert( alts.size() == 1 );
160 assert( alts.front().expr != 0 );
161 current.push_back( alts.front() );
162 }
163 options.options.push_back( current );
164
165 matcher->solve();
166 }
167
168 TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : spotter(spotter) {
169 // xxx - shouldn't need to be &<tuple-expr>, just &<lvalue-tuple-type>
170 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(lhs) )
171 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) )
172 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->lhs) );
173 }
174
175 TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) {
176
177 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(rhs) )
178 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->rhs) );
179 }
180
181 UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) {
182 assert( left && right );
183 std::list< Expression * > args;
184 args.push_back( new AddressExpr( left->clone() ) );
185 args.push_back( right->clone() );
186 return new UntypedExpr( new NameExpr( "?=?" ), args );
187 }
188
189 void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
190 assert ( ! lhs.empty() && rhs.size() == 1);
191
192 for ( Expression * l : lhs ) {
193 out.push_back( createAssgn( l, rhs.front() ) );
194 }
195 }
196
197 void TupleAssignSpotter::MassAssignMatcher::solve() {
198 assert( ! spotter.options.empty() );
199 for ( std::list< ResolvExpr::AltList >::iterator i = spotter.options.begin(); i != spotter.options.end(); ++i ) {
200 // extract expressions from the alternatives to produce a list of assignments that
201 // together form a single alternative
202 std::list< Expression *> solved_assigns;
203 for ( ResolvExpr::Alternative & alt : *i ) {
204 solved_assigns.push_back( alt.expr );
205 }
206 spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::sumCost( *i ) ) );
207 }
208 }
209
210 void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
211 // xxx - need more complicated matching?
212 if ( lhs.size() == rhs.size() ) {
213 zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn );
214 }
215 }
216
217 void TupleAssignSpotter::MultipleAssignMatcher::solve() {
218 // options.print( std::cerr );
219 std::list< ResolvExpr::AltList > best = spotter.options.get_best();
220 if ( best.size() == 1 ) {
221 std::list<Expression *> solved_assigns;
222 for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) {
223 solved_assigns.push_back( i->expr );
224 }
225 /* assigning cost zero? */
226 spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) );
227 }
228 }
229
230 std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() {
231 std::list< ResolvExpr::AltList > ret;
232 std::list< ResolvExpr::AltList > solns;
233 for ( ResolvExpr::AltList & i : options ) {
234 ResolvExpr::AltList current;
235 findMinCost( i.begin(), i.end(), back_inserter(current) );
236 solns.push_back( ResolvExpr::AltList(current.begin(), current.end()) );
237 }
238 // need to combine -- previously "lift_intersection", which
239 // did some madness involving, effectively, the intersection of
240 // a bunch of AltLists
241 std::list<ResolvExpr::AltList> result = solns;
242 if ( result.size() != 1 ) {
243 throw SemanticError("Ambiguous tuple expression");
244 }
245 ret.push_back( *result.begin() );
246 return ret;
247 }
248
249 void TupleAssignSpotter::Options::print( std::ostream &ostr ) {
250 for ( ResolvExpr::AltList & l : options ) {
251 for ( ResolvExpr::Alternative & alt : l ) {
252 alt.print( ostr );
253 ostr << " ";
254 }
255 ostr << std::endl;
256 } // for
257 }
258} // namespace Tuples
259
260// Local Variables: //
261// tab-width: 4 //
262// mode: c++ //
263// compile-command: "make install" //
264// End: //
Note: See TracBrowser for help on using the repository browser.