source: src/Tuples/TupleExpansion.cc @ 4f68f6d

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerwith_gc
Last change on this file since 4f68f6d was 4f68f6d, checked in by Rob Schluntz <rschlunt@…>, 4 years ago

Minor cleanup

  • Property mode set to 100644
File size: 14.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 : Wed Jun 21 17:35:04 2017
13// Update Count     : 19
14//
15
16#include <stddef.h>               // for size_t
17#include <cassert>                // for assert
18#include <list>                   // for list
19
20#include "Common/PassVisitor.h"   // for PassVisitor, WithDeclsToAdd, WithGu...
21#include "Common/ScopedMap.h"     // for ScopedMap
22#include "Common/utility.h"       // for CodeLocation
23#include "InitTweak/InitTweak.h"  // for getFunction
24#include "Parser/LinkageSpec.h"   // for Spec, C, Intrinsic
25#include "SynTree/Constant.h"     // for Constant
26#include "SynTree/Declaration.h"  // for StructDecl, DeclarationWithType
27#include "SynTree/Expression.h"   // for UntypedMemberExpr, Expression, Uniq...
28#include "SynTree/Label.h"        // for operator==, Label
29#include "SynTree/Mutator.h"      // for Mutator
30#include "SynTree/Type.h"         // for Type, Type::Qualifiers, TupleType
31#include "SynTree/Visitor.h"      // for Visitor
32
33class CompoundStmt;
34class TypeSubstitution;
35
36namespace Tuples {
37        namespace {
38                struct MemberTupleExpander final : public WithShortCircuiting, public WithVisitorRef<MemberTupleExpander> {
39                        void premutate( UntypedMemberExpr * ) { visit_children = false; }
40                        Expression * postmutate( UntypedMemberExpr * memberExpr );
41                };
42
43                struct UniqueExprExpander final : public WithDeclsToAdd {
44                        Expression * postmutate( UniqueExpr * unqExpr );
45
46                        std::map< int, Expression * > decls; // not vector, because order added may not be increasing order
47
48                        ~UniqueExprExpander() {
49                                for ( std::pair<const int, Expression *> & p : decls ) {
50                                        delete p.second;
51                                }
52                        }
53                };
54
55                struct TupleAssignExpander {
56                        Expression * postmutate( TupleAssignExpr * tupleExpr );
57                };
58
59                struct TupleTypeReplacer : public WithDeclsToAdd, public WithGuards, public WithTypeSubstitution {
60                        Type * postmutate( TupleType * tupleType );
61
62                        void premutate( CompoundStmt * ) {
63                                GuardScope( typeMap );
64                        }
65                  private:
66                        ScopedMap< int, StructDecl * > typeMap;
67                };
68
69                struct TupleIndexExpander {
70                        Expression * postmutate( TupleIndexExpr * tupleExpr );
71                };
72
73                struct TupleExprExpander final {
74                        Expression * postmutate( TupleExpr * tupleExpr );
75                };
76        }
77
78        void expandMemberTuples( std::list< Declaration * > & translationUnit ) {
79                PassVisitor<MemberTupleExpander> expander;
80                mutateAll( translationUnit, expander );
81        }
82
83        void expandUniqueExpr( std::list< Declaration * > & translationUnit ) {
84                PassVisitor<UniqueExprExpander> unqExpander;
85                mutateAll( translationUnit, unqExpander );
86        }
87
88        void expandTuples( std::list< Declaration * > & translationUnit ) {
89                PassVisitor<TupleAssignExpander> assnExpander;
90                mutateAll( translationUnit, assnExpander );
91
92                PassVisitor<TupleTypeReplacer> replacer;
93                mutateAll( translationUnit, replacer );
94
95                PassVisitor<TupleIndexExpander> idxExpander;
96                mutateAll( translationUnit, idxExpander );
97
98                PassVisitor<TupleExprExpander> exprExpander;
99                mutateAll( translationUnit, exprExpander );
100        }
101
102        namespace {
103                /// given a expression representing the member and an expression representing the aggregate,
104                /// reconstructs a flattened UntypedMemberExpr with the right precedence
105                Expression * reconstructMemberExpr( Expression * member, Expression * aggr, CodeLocation & loc ) {
106                        if ( UntypedMemberExpr * memberExpr = dynamic_cast< UntypedMemberExpr * >( member ) ) {
107                                // construct a new UntypedMemberExpr with the correct structure , and recursively
108                                // expand that member expression.
109                                PassVisitor<MemberTupleExpander> expander;
110                                UntypedMemberExpr * inner = new UntypedMemberExpr( memberExpr->aggregate, aggr->clone() );
111                                UntypedMemberExpr * newMemberExpr = new UntypedMemberExpr( memberExpr->member, inner );
112                                inner->location = newMemberExpr->location = loc;
113                                memberExpr->member = nullptr;
114                                memberExpr->aggregate = nullptr;
115                                delete memberExpr;
116                                return newMemberExpr->acceptMutator( expander );
117                        } else {
118                                // not a member expression, so there is nothing to do but attach and return
119                                UntypedMemberExpr * newMemberExpr = new UntypedMemberExpr( member, aggr->clone() );
120                                newMemberExpr->location = loc;
121                                return newMemberExpr;
122                        }
123                }
124        }
125
126        Expression * MemberTupleExpander::postmutate( UntypedMemberExpr * memberExpr ) {
127                if ( UntypedTupleExpr * tupleExpr = dynamic_cast< UntypedTupleExpr * > ( memberExpr->member ) ) {
128                        Expression * aggr = memberExpr->aggregate->clone()->acceptMutator( *visitor );
129                        // aggregate expressions which might be impure must be wrapped in unique expressions
130                        // xxx - if there's a member-tuple expression nested in the aggregate, this currently generates the wrong code if a UniqueExpr is not used, and it's purely an optimization to remove the UniqueExpr
131                        // if ( Tuples::maybeImpureIgnoreUnique( memberExpr->get_aggregate() ) ) aggr = new UniqueExpr( aggr );
132                        aggr = new UniqueExpr( aggr );
133                        for ( Expression *& expr : tupleExpr->exprs ) {
134                                expr = reconstructMemberExpr( expr, aggr, memberExpr->location );
135                                expr->location = memberExpr->location;
136                        }
137                        delete aggr;
138                        tupleExpr->location = memberExpr->location;
139                        return tupleExpr;
140                } else {
141                        // there may be a tuple expr buried in the aggregate
142                        // xxx - this is a memory leak
143                        UntypedMemberExpr * newMemberExpr = new UntypedMemberExpr( memberExpr->member->clone(), memberExpr->aggregate->acceptMutator( *visitor ) );
144                        newMemberExpr->location = memberExpr->location;
145                        return newMemberExpr;
146                }
147        }
148
149        Expression * UniqueExprExpander::postmutate( UniqueExpr * unqExpr ) {
150                const int id = unqExpr->get_id();
151
152                // on first time visiting a unique expr with a particular ID, generate the expression that replaces all UniqueExprs with that ID,
153                // and lookup on subsequent hits. This ensures that all unique exprs with the same ID reference the same variable.
154                if ( ! decls.count( id ) ) {
155                        Expression * assignUnq;
156                        Expression * var = unqExpr->get_var();
157                        if ( unqExpr->get_object() ) {
158                                // an object was generated to represent this unique expression -- it should be added to the list of declarations now
159                                declsToAddBefore.push_back( unqExpr->get_object() );
160                                unqExpr->set_object( nullptr );
161                                // steal the expr from the unqExpr
162                                assignUnq = UntypedExpr::createAssign( unqExpr->get_var()->clone(), unqExpr->get_expr() );
163                                unqExpr->set_expr( nullptr );
164                        } else {
165                                // steal the already generated assignment to var from the unqExpr - this has been generated by FixInit
166                                Expression * expr = unqExpr->get_expr();
167                                CommaExpr * commaExpr = strict_dynamic_cast< CommaExpr * >( expr );
168                                assignUnq = commaExpr->get_arg1();
169                                commaExpr->set_arg1( nullptr );
170                        }
171                        ObjectDecl * finished = new ObjectDecl( toString( "_unq", id, "_finished_" ), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, new BasicType( Type::Qualifiers(), BasicType::Bool ),
172                                                                                                        new SingleInit( new ConstantExpr( Constant::from_int( 0 ) ) ) );
173                        declsToAddBefore.push_back( finished );
174                        // (finished ? _unq_expr_N : (_unq_expr_N = <unqExpr->get_expr()>, finished = 1, _unq_expr_N))
175                        // This pattern ensures that each unique expression is evaluated once, regardless of evaluation order of the generated C code.
176                        Expression * assignFinished = UntypedExpr::createAssign( new VariableExpr(finished), new ConstantExpr( Constant::from_int( 1 ) ) );
177                        ConditionalExpr * condExpr = new ConditionalExpr( new VariableExpr( finished ), var->clone(),
178                                new CommaExpr( new CommaExpr( assignUnq, assignFinished ), var->clone() ) );
179                        condExpr->set_result( var->get_result()->clone() );
180                        condExpr->set_env( maybeClone( unqExpr->get_env() ) );
181                        decls[id] = condExpr;
182                }
183                delete unqExpr;
184                return decls[id]->clone();
185        }
186
187        Expression * TupleAssignExpander::postmutate( TupleAssignExpr * assnExpr ) {
188                StmtExpr * ret = assnExpr->get_stmtExpr();
189                assnExpr->set_stmtExpr( nullptr );
190                // move env to StmtExpr
191                ret->set_env( assnExpr->get_env() );
192                assnExpr->set_env( nullptr );
193                delete assnExpr;
194                return ret;
195        }
196
197        Type * TupleTypeReplacer::postmutate( TupleType * tupleType ) {
198                unsigned tupleSize = tupleType->size();
199                if ( ! typeMap.count( tupleSize ) ) {
200                        // generate struct type to replace tuple type based on the number of components in the tuple
201                        StructDecl * decl = new StructDecl( toString( "_tuple", tupleSize, "_" ) );
202                        decl->location = tupleType->location;
203                        decl->set_body( true );
204                        for ( size_t i = 0; i < tupleSize; ++i ) {
205                                TypeDecl * tyParam = new TypeDecl( toString( "tuple_param_", tupleSize, "_", i ), Type::StorageClasses(), nullptr, TypeDecl::Dtype, true );
206                                decl->get_members().push_back( new ObjectDecl( toString("field_", i ), Type::StorageClasses(), LinkageSpec::C, nullptr, new TypeInstType( Type::Qualifiers(), tyParam->get_name(), tyParam ), nullptr ) );
207                                decl->get_parameters().push_back( tyParam );
208                        }
209                        if ( tupleSize == 0 ) {
210                                // empty structs are not standard C. Add a dummy field to empty tuples to silence warnings when a compound literal Tuple0 is created.
211                                decl->get_members().push_back( new ObjectDecl( "dummy", Type::StorageClasses(), LinkageSpec::C, nullptr, new BasicType( Type::Qualifiers(), BasicType::SignedInt ), nullptr ) );
212                        }
213                        typeMap[tupleSize] = decl;
214                        declsToAddBefore.push_back( decl );
215                }
216                Type::Qualifiers qualifiers = tupleType->get_qualifiers();
217
218                StructDecl * decl = typeMap[tupleSize];
219                StructInstType * newType = new StructInstType( qualifiers, decl );
220                for ( auto p : group_iterate( tupleType->get_types(), decl->get_parameters() ) ) {
221                        Type * t = std::get<0>(p);
222                        newType->get_parameters().push_back( new TypeExpr( t->clone() ) );
223                }
224                delete tupleType;
225                return newType;
226        }
227
228        Expression * TupleIndexExpander::postmutate( TupleIndexExpr * tupleExpr ) {
229                Expression * tuple = tupleExpr->tuple;
230                assert( tuple );
231                tupleExpr->tuple = nullptr;
232                unsigned int idx = tupleExpr->index;
233                TypeSubstitution * env = tupleExpr->env;
234                tupleExpr->env = nullptr;
235                delete tupleExpr;
236
237                StructInstType * type = strict_dynamic_cast< StructInstType * >( tuple->result );
238                StructDecl * structDecl = type->baseStruct;
239                assert( structDecl->members.size() > idx );
240                Declaration * member = *std::next(structDecl->members.begin(), idx);
241                MemberExpr * memExpr = new MemberExpr( strict_dynamic_cast< DeclarationWithType * >( member ), tuple );
242                memExpr->env = env;
243                return memExpr;
244        }
245
246        Expression * replaceTupleExpr( Type * result, const std::list< Expression * > & exprs, TypeSubstitution * env ) {
247                if ( result->isVoid() ) {
248                        // void result - don't need to produce a value for cascading - just output a chain of comma exprs
249                        assert( ! exprs.empty() );
250                        std::list< Expression * >::const_iterator iter = exprs.begin();
251                        Expression * expr = new CastExpr( *iter++ );
252                        for ( ; iter != exprs.end(); ++iter ) {
253                                expr = new CommaExpr( expr, new CastExpr( *iter ) );
254                        }
255                        expr->set_env( env );
256                        return expr;
257                } else {
258                        // typed tuple expression - produce a compound literal which performs each of the expressions
259                        // as a distinct part of its initializer - the produced compound literal may be used as part of
260                        // another expression
261                        std::list< Initializer * > inits;
262                        for ( Expression * expr : exprs ) {
263                                inits.push_back( new SingleInit( expr ) );
264                        }
265                        Expression * expr = new CompoundLiteralExpr( result, new ListInit( inits ) );
266                        expr->set_env( env );
267                        return expr;
268                }
269        }
270
271        Expression * TupleExprExpander::postmutate( TupleExpr * tupleExpr ) {
272                Type * result = tupleExpr->get_result();
273                std::list< Expression * > exprs = tupleExpr->get_exprs();
274                assert( result );
275                TypeSubstitution * env = tupleExpr->get_env();
276
277                // remove data from shell and delete it
278                tupleExpr->set_result( nullptr );
279                tupleExpr->get_exprs().clear();
280                tupleExpr->set_env( nullptr );
281                delete tupleExpr;
282
283                return replaceTupleExpr( result, exprs, env );
284        }
285
286        Type * makeTupleType( const std::list< Expression * > & exprs ) {
287                // produce the TupleType which aggregates the types of the exprs
288                std::list< Type * > types;
289                Type::Qualifiers qualifiers( Type::Const | Type::Volatile | Type::Restrict | Type::Lvalue | Type::Atomic | Type::Mutex );
290                for ( Expression * expr : exprs ) {
291                        assert( expr->get_result() );
292                        if ( expr->get_result()->isVoid() ) {
293                                // if the type of any expr is void, the type of the entire tuple is void
294                                return new VoidType( Type::Qualifiers() );
295                        }
296                        Type * type = expr->get_result()->clone();
297                        types.push_back( type );
298                        // the qualifiers on the tuple type are the qualifiers that exist on all component types
299                        qualifiers &= type->get_qualifiers();
300                } // for
301                if ( exprs.empty() ) qualifiers = Type::Qualifiers();
302                return new TupleType( qualifiers, types );
303        }
304
305        TypeInstType * isTtype( Type * type ) {
306                if ( TypeInstType * inst = dynamic_cast< TypeInstType * >( type ) ) {
307                        if ( inst->get_baseType() && inst->get_baseType()->get_kind() == TypeDecl::Ttype ) {
308                                return inst;
309                        }
310                }
311                return nullptr;
312        }
313
314        namespace {
315                /// determines if impurity (read: side-effects) may exist in a piece of code. Currently gives a very crude approximation, wherein any function call expression means the code may be impure
316                struct ImpurityDetector : public WithShortCircuiting {
317                        ImpurityDetector( bool ignoreUnique ) : ignoreUnique( ignoreUnique ) {}
318
319                        void previsit( ApplicationExpr * appExpr ) {
320                                visit_children = false;
321                                if ( DeclarationWithType * function = InitTweak::getFunction( appExpr ) ) {
322                                        if ( function->get_linkage() == LinkageSpec::Intrinsic ) {
323                                                if ( function->get_name() == "*?" || function->get_name() == "?[?]" ) {
324                                                        // intrinsic dereference, subscript are pure, but need to recursively look for impurity
325                                                        visit_children = true;
326                                                        return;
327                                                }
328                                        }
329                                }
330                                maybeImpure = true;
331                        }
332                        void previsit( UntypedExpr * ) { maybeImpure = true; visit_children = false; }
333                        void previsit( UniqueExpr * ) {
334                                if ( ignoreUnique ) {
335                                        // bottom out at unique expression.
336                                        // The existence of a unique expression doesn't change the purity of an expression.
337                                        // That is, even if the wrapped expression is impure, the wrapper protects the rest of the expression.
338                                        visit_children = false;
339                                        return;
340                                }
341                        }
342
343                        bool maybeImpure = false;
344                        bool ignoreUnique;
345                };
346        } // namespace
347
348        bool maybeImpure( Expression * expr ) {
349                PassVisitor<ImpurityDetector> detector( false );
350                expr->accept( detector );
351                return detector.pass.maybeImpure;
352        }
353
354        bool maybeImpureIgnoreUnique( Expression * expr ) {
355                PassVisitor<ImpurityDetector> detector( true );
356                expr->accept( detector );
357                return detector.pass.maybeImpure;
358        }
359} // namespace Tuples
360
361// Local Variables: //
362// tab-width: 4 //
363// mode: c++ //
364// compile-command: "make install" //
365// End: //
Note: See TracBrowser for help on using the repository browser.