source: src/Tuples/TupleAssignment.cc @ 141b786

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 141b786 was 141b786, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

rework UniqueExpr?, handle UniqueExpr? in FixInit?, fix translation for UniqueExprs?, refactor explode functions and fix AddressExpr? distribution over exploded tuple exprs

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