source: src/Tuples/TupleAssignment.cc @ cbce272

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 cbce272 was 615a096, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

fix BFCommon problem on gcc-4.9, and begin consistent renaming

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