source: src/Tuples/TupleExpansionNew.cpp @ e116db3

pthread-emulation
Last change on this file since e116db3 was e116db3, checked in by Andrew Beach <ajbeach@…>, 4 months ago

Combined some sub-passes in Tuple Expansion, two less tree traversals now have to be preformed.

  • Property mode set to 100644
File size: 10.3 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// TupleExpansionNew.cpp --
8//
9// Author           : Henry Xue
10// Created On       : Mon Aug 23 15:36:09 2021
11// Last Modified By : Andrew Beach
12// Last Modified On : Mon Aug 15 17:00:00 2022
13// Update Count     : 3
14//
15
16#include "Tuples.h"
17
18#include "AST/Pass.hpp"
19#include "Common/ScopedMap.h"
20
21namespace Tuples {
22
23namespace {
24
25struct MemberTupleExpander final : public ast::WithShortCircuiting, public ast::WithVisitorRef< MemberTupleExpander > {
26        void previsit( const ast::UntypedMemberExpr * ) { visit_children = false; }
27        const ast::Expr * postvisit( const ast::UntypedMemberExpr * memberExpr );
28};
29
30struct UniqueExprExpander final : public ast::WithDeclsToAdd<> {
31        const ast::Expr * postvisit( const ast::UniqueExpr * unqExpr );
32        std::map< int, ast::ptr<ast::Expr> > decls; // not vector, because order added may not be increasing order
33};
34
35/// given a expression representing the member and an expression representing the aggregate,
36/// reconstructs a flattened UntypedMemberExpr with the right precedence
37const ast::Expr * reconstructMemberExpr( const ast::Expr * member, const ast::Expr * aggr, const CodeLocation & loc ) {
38        if ( auto memberExpr = dynamic_cast< const ast::UntypedMemberExpr * >( member ) ) {
39                // construct a new UntypedMemberExpr with the correct structure , and recursively
40                // expand that member expression.
41                ast::Pass< MemberTupleExpander > expander;
42                auto inner = new ast::UntypedMemberExpr( loc, memberExpr->aggregate, aggr );
43                auto newMemberExpr = new ast::UntypedMemberExpr( loc, memberExpr->member, inner );
44                return newMemberExpr->accept( expander );
45        } else {
46                // not a member expression, so there is nothing to do but attach and return
47                return new ast::UntypedMemberExpr( loc, member, aggr );
48        }
49}
50
51const ast::Expr * MemberTupleExpander::postvisit( const ast::UntypedMemberExpr * memberExpr ) {
52        const CodeLocation loc = memberExpr->location;
53        if ( auto tupleExpr = memberExpr->member.as< ast::UntypedTupleExpr >() ) {
54                auto mutExpr = mutate( tupleExpr );
55                ast::ptr< ast::Expr > aggr = memberExpr->aggregate->accept( *visitor );
56                // aggregate expressions which might be impure must be wrapped in unique expressions
57                if ( Tuples::maybeImpureIgnoreUnique( memberExpr->aggregate ) ) aggr = new ast::UniqueExpr( loc, aggr );
58                for ( auto & expr : mutExpr->exprs ) {
59                        expr = reconstructMemberExpr( expr, aggr, loc );
60                }
61                return mutExpr;
62        } else {
63                // there may be a tuple expr buried in the aggregate
64                return new ast::UntypedMemberExpr( loc, memberExpr->member, memberExpr->aggregate->accept( *visitor ) );
65        }
66}
67
68const ast::Expr * UniqueExprExpander::postvisit( const ast::UniqueExpr * unqExpr ) {
69        const CodeLocation loc = unqExpr->location;
70        const int id = unqExpr->id;
71
72        // on first time visiting a unique expr with a particular ID, generate the expression that replaces all UniqueExprs with that ID,
73        // and lookup on subsequent hits. This ensures that all unique exprs with the same ID reference the same variable.
74        if ( ! decls.count( id ) ) {
75                ast::ptr< ast::Expr > assignUnq;
76                const ast::VariableExpr * var = unqExpr->var;
77                if ( unqExpr->object ) {
78                        // an object was generated to represent this unique expression -- it should be added to the list of declarations now
79                        declsToAddBefore.push_back( unqExpr->object.as< ast::Decl >() );
80                        // deep copy required due to unresolved issues with UniqueExpr
81                        assignUnq = ast::UntypedExpr::createAssign( loc, var, unqExpr->expr );
82                } else {
83                        const auto commaExpr = unqExpr->expr.strict_as< ast::CommaExpr >();
84                        assignUnq = commaExpr->arg1;
85                }
86                auto finished = new ast::ObjectDecl( loc, toString( "_unq", id, "_finished_" ), new ast::BasicType( ast::BasicType::Kind::Bool ),
87                        new ast::SingleInit( loc, ast::ConstantExpr::from_int( loc, 0 ) ), {}, ast::Linkage::Cforall );
88                declsToAddBefore.push_back( finished );
89                // (finished ? _unq_expr_N : (_unq_expr_N = <unqExpr->get_expr()>, finished = 1, _unq_expr_N))
90                // This pattern ensures that each unique expression is evaluated once, regardless of evaluation order of the generated C code.
91                auto assignFinished = ast::UntypedExpr::createAssign( loc, new ast::VariableExpr( loc, finished ),
92                        ast::ConstantExpr::from_int( loc, 1 ) );
93                auto condExpr = new ast::ConditionalExpr( loc, new ast::VariableExpr( loc, finished ), var,
94                        new ast::CommaExpr( loc, new ast::CommaExpr( loc, assignUnq, assignFinished ), var ) );
95                condExpr->result = var->result;
96                condExpr->env = unqExpr->env;
97                decls[id] = condExpr;
98        }
99        return ast::deepCopy(decls[id].get());
100}
101
102/// Replaces Tuple Assign & Index Expressions, and Tuple Types.
103struct TupleMainExpander :
104                public ast::WithGuards,
105                public ast::WithVisitorRef<TupleMainExpander>,
106                public ast::WithDeclsToAdd<> {
107        ast::Expr const * postvisit( ast::TupleAssignExpr const * expr ) {
108                // Just move the env on the new top level expression.
109                return ast::mutate_field( expr->stmtExpr.get(),
110                        &ast::TupleAssignExpr::env, expr->env.get() );
111        }
112
113        void previsit( ast::ParseNode const * node ) {
114                GuardValue( location ) = &node->location;
115        }
116
117        void previsit( ast::CompoundStmt const * stmt ) {
118                previsit( (ast::ParseNode const *)stmt );
119                GuardScope( typeMap );
120        }
121
122        ast::Expr const * postvisit( ast::Expr const * expr ) {
123                if ( nullptr == expr->env ) {
124                        return expr;
125                }
126                // TypeSubstitutions are never visited in the new Pass template,
127                // so it is done manually here, where all types have to be replaced.
128                return ast::mutate_field( expr, &ast::Expr::env,
129                        expr->env->accept( *visitor ) );
130        }
131
132        ast::Type const * postvisit( ast::TupleType const * type ) {
133                assert( location );
134                unsigned tupleSize = type->size();
135                if ( !typeMap.count( tupleSize ) ) {
136                        ast::StructDecl * decl = new ast::StructDecl( *location,
137                                toString( "_tuple", tupleSize, "_" )
138                        );
139                        decl->body = true;
140
141                        for ( size_t i = 0 ; i < tupleSize ; ++i ) {
142                                ast::TypeDecl * typeParam = new ast::TypeDecl( *location,
143                                        toString( "tuple_param_", tupleSize, "_", i ),
144                                        ast::Storage::Classes(),
145                                        nullptr,
146                                        ast::TypeDecl::Dtype,
147                                        true
148                                        );
149                                ast::ObjectDecl * member = new ast::ObjectDecl( *location,
150                                        toString( "field_", i ),
151                                        new ast::TypeInstType( typeParam )
152                                        );
153                                decl->params.push_back( typeParam );
154                                decl->members.push_back( member );
155                        }
156
157                        // Empty structures are not standard C. Add a dummy field to
158                        // empty tuples to silence warnings when a compound literal
159                        // `_tuple0_` is created.
160                        if ( tupleSize == 0 ) {
161                                decl->members.push_back(
162                                        new ast::ObjectDecl( *location,
163                                                "dummy",
164                                                new ast::BasicType( ast::BasicType::SignedInt ),
165                                                nullptr,
166                                                ast::Storage::Classes(),
167                                                // Does this have to be a C linkage?
168                                                ast::Linkage::C
169                                        )
170                                );
171                        }
172                        typeMap[tupleSize] = decl;
173                        declsToAddBefore.push_back( decl );
174                }
175
176                ast::StructDecl const * decl = typeMap[ tupleSize ];
177                ast::StructInstType * newType =
178                        new ast::StructInstType( decl, type->qualifiers );
179                for ( auto pair : group_iterate( type->types, decl->params ) ) {
180                        ast::Type const * t = std::get<0>( pair );
181                        newType->params.push_back(
182                                new ast::TypeExpr( *location, ast::deepCopy( t ) ) );
183                }
184                return newType;
185        }
186
187        ast::Expr const * postvisit( ast::TupleIndexExpr const * expr ) {
188                CodeLocation const & location = expr->location;
189                ast::Expr const * tuple = expr->tuple.get();
190                assert( tuple );
191                unsigned int index = expr->index;
192                ast::TypeSubstitution const * env = expr->env.get();
193
194                if ( auto tupleExpr = dynamic_cast<ast::TupleExpr const *>( tuple ) ) {
195                        // Optimization: If it is a definitely pure tuple expr,
196                        // then it can reduce to the only relevant component.
197                        if ( !maybeImpureIgnoreUnique( tupleExpr ) ) {
198                                assert( index < tupleExpr->exprs.size() );
199                                ast::ptr<ast::Expr> const & expr =
200                                        *std::next( tupleExpr->exprs.begin(), index );
201                                ast::Expr * ret = ast::mutate( expr.get() );
202                                ret->env = env;
203                                return ret;
204                        }
205                }
206
207                auto type = tuple->result.strict_as<ast::StructInstType>();
208                ast::StructDecl const * structDecl = type->base;
209                assert( index < structDecl->members.size() );
210                ast::ptr<ast::Decl> const & member =
211                        *std::next( structDecl->members.begin(), index );
212                ast::MemberExpr * memberExpr = new ast::MemberExpr( location,
213                        member.strict_as<ast::DeclWithType>(), tuple );
214                memberExpr->env = env;
215                return memberExpr;
216        }
217private:
218        ScopedMap< int, ast::StructDecl const * > typeMap;
219        CodeLocation const * location = nullptr;
220};
221
222ast::Expr const * replaceTupleExpr(
223                CodeLocation const & location,
224                ast::Type const * result,
225                std::vector<ast::ptr<ast::Expr>> const & exprs,
226                ast::TypeSubstitution const * env ) {
227        assert( result );
228        // A void result: It doesn't need to produce a value for cascading,
229        // just output a chain of comma exprs.
230        if ( result->isVoid() ) {
231                assert( !exprs.empty() );
232                std::vector<ast::ptr<ast::Expr>>::const_iterator iter = exprs.begin();
233                ast::Expr * expr = new ast::CastExpr( *iter++ );
234                for ( ; iter != exprs.end() ; ++iter ) {
235                        expr = new ast::CommaExpr( location,
236                                expr, new ast::CastExpr( *iter ) );
237                }
238                expr->env = env;
239                return expr;
240        // Typed tuple expression: Produce a compound literal which performs
241        // each of the expressions as a distinct part of its initializer. The
242        // produced compound literal may be used as part of another expression.
243        } else {
244                auto inits = map_range<std::vector<ast::ptr<ast::Init>>>( exprs,
245                        []( ast::Expr const * expr ) {
246                                return new ast::SingleInit( expr->location, expr );
247                        }
248                );
249                ast::Expr * expr = new ast::CompoundLiteralExpr( location,
250                        result, new ast::ListInit( location, std::move( inits ) ) );
251                expr->env = env;
252                return expr;
253        }
254}
255
256struct TupleExprExpander {
257        ast::Expr const * postvisit( ast::TupleExpr const * expr ) {
258                return replaceTupleExpr( expr->location,
259                        expr->result, expr->exprs, expr->env );
260        }
261};
262
263} // namespace
264
265void expandMemberTuples( ast::TranslationUnit & translationUnit ) {
266        ast::Pass< MemberTupleExpander >::run( translationUnit );
267}
268
269void expandUniqueExpr( ast::TranslationUnit & translationUnit ) {
270        ast::Pass< UniqueExprExpander >::run( translationUnit );
271}
272
273void expandTuples( ast::TranslationUnit & translationUnit ) {
274        // These can't just be combined simply (there might be a way with work).
275        ast::Pass<TupleMainExpander>::run( translationUnit );
276        ast::Pass<TupleExprExpander>::run( translationUnit );
277}
278
279} // namespace Tuples
Note: See TracBrowser for help on using the repository browser.