source: src/Tuples/TupleAssignment.cc @ 5af62f1

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 5af62f1 was 5af62f1, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

major refactoring of Rodolfo's tuple assignment code
  • Property mode set to 100644
File size: 9.5 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( std::list< Expression * > &assigns ) = 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( std::list< Expression * > &assigns );
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( std::list< Expression * > &assigns );
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 solved_alts;
153                ResolvExpr::AltList current;
154                // now resolve new assignments
155                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
156                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
157                        finder.findWithAdjustment(*i);
158                        // prune expressions that don't coincide with
159                        ResolvExpr::AltList alts = finder.get_alternatives();
160                        assert( alts.size() == 1 );
161                        assert( alts.front().expr != 0 );
162                        current.push_back( finder.get_alternatives().front() );
163                        solved_assigns.push_back( alts.front().expr->clone() );
164                }
165                options.options.push_back( current );
166
167                matcher->solve( new_assigns );
168        }
169
170        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : spotter(spotter) {
171                // xxx - shouldn't need to be &<tuple-expr>, just &<lvalue-tuple-type>
172                if (AddressExpr *addr = dynamic_cast<AddressExpr *>(lhs) )
173                        if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) )
174                                std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->lhs) );
175        }
176
177        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) {
178
179                if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(rhs) )
180                        std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->rhs) );
181        }
182
183        UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) {
184                assert( left && right );
185                std::list< Expression * > args;
186                args.push_back( new AddressExpr( left->clone() ) );
187                args.push_back( right->clone() );
188                return new UntypedExpr( new NameExpr( "?=?" ), args );
189        }
190
191        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
192                assert ( ! lhs.empty() && rhs.size() == 1);
193
194                for ( Expression * l : lhs ) {
195                        out.push_back( createAssgn( l, rhs.front() ) );
196                }
197        }
198
199        void TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) {
200                assert( ! spotter.options.empty() );
201                ResolvExpr::AltList winners;
202                for ( std::list< ResolvExpr::AltList >::iterator i = spotter.options.begin(); i != spotter.options.end(); ++i ) {
203                        findMinCost( i->begin(), i->end(), back_inserter(winners) );
204                }
205
206                std::list< Expression *> solved_assigns;
207                for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i ) {
208                        solved_assigns.push_back( i->expr );
209                }
210                spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) );
211        }
212
213        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
214                // xxx - need more complicated matching?
215                if ( lhs.size() == rhs.size() ) {
216                        zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn );
217                }
218        }
219
220        void TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) {
221                // options.print( std::cerr );
222                std::list< ResolvExpr::AltList > best = spotter.options.get_best();
223                if ( best.size() == 1 ) {
224                        std::list<Expression *> solved_assigns;
225                        for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) {
226                                solved_assigns.push_back( i->expr );
227                        }
228                        /* assigning cost zero? */
229                        spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) );
230                }
231        }
232
233        std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() {
234                std::list< ResolvExpr::AltList > ret;
235                std::list< ResolvExpr::AltList > solns;
236                for ( ResolvExpr::AltList & i : options ) {
237                        ResolvExpr::AltList current;
238                        findMinCost( i.begin(), i.end(), back_inserter(current) );
239                        solns.push_back( ResolvExpr::AltList(current.begin(), current.end()) );
240                }
241                // need to combine -- previously "lift_intersection", which
242                // did some madness involving, effectively, the intersection of
243                // a bunch of AltLists
244                std::list<ResolvExpr::AltList> result = solns;
245                if ( result.size() != 1 ) {
246                        throw SemanticError("Ambiguous tuple expression");
247                }
248                ret.push_back( *result.begin() );
249                return ret;
250        }
251
252        void TupleAssignSpotter::Options::print( std::ostream &ostr ) {
253                for ( ResolvExpr::AltList & l : options ) {
254                        for ( ResolvExpr::Alternative & alt : l ) {
255                                alt.print( ostr );
256                                ostr << " ";
257                        }
258                        ostr << std::endl;
259                } // for
260        }
261} // namespace Tuples
262
263// Local Variables: //
264// tab-width: 4 //
265// mode: c++ //
266// compile-command: "make install" //
267// End: //
Note: See TracBrowser for help on using the repository browser.