source: src/Tuples/TupleExpansionNew.cpp

Last change on this file was ce1d721, checked in by Andrew Beach <ajbeach@…>, 12 days ago

Changed the indentation in TupleExpansionNew?.cpp to match the standard in porting.md.

  • Property mode set to 100644
File size: 10.4 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 Jul 29 14:06:00 2022
13// Update Count     : 2
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
102struct TupleAssignExpander {
103        ast::Expr const * postvisit( ast::TupleAssignExpr const * expr ) {
104                // Just move the env on the new top level expression.
105                return ast::mutate_field( expr->stmtExpr.get(),
106                        &ast::TupleAssignExpr::env, expr->env.get() );
107        }
108};
109
110struct TupleTypeReplacer :
111                public ast::WithGuards,
112                public ast::WithVisitorRef<TupleTypeReplacer>,
113                public ast::WithDeclsToAdd<> {
114        void previsit( ast::ParseNode const * node ) {
115                GuardValue( location ) = &node->location;
116        }
117
118        void previsit( ast::CompoundStmt const * stmt ) {
119                previsit( (ast::ParseNode const *)stmt );
120                GuardScope( typeMap );
121        }
122
123        ast::Expr const * postvisit( ast::Expr const * expr ) {
124                if ( nullptr == expr->env ) {
125                        return expr;
126                }
127                // TypeSubstitutions are never visited in the new Pass template,
128                // so it is done manually here, where all types have to be replaced.
129                return ast::mutate_field( expr, &ast::Expr::env,
130                        expr->env->accept( *visitor ) );
131        }
132
133        ast::Type const * postvisit( ast::TupleType const * type ) {
134                assert( location );
135                unsigned tupleSize = type->size();
136                if ( !typeMap.count( tupleSize ) ) {
137                        ast::StructDecl * decl = new ast::StructDecl( *location,
138                                toString( "_tuple", tupleSize, "_" )
139                        );
140                        decl->body = true;
141
142                        for ( size_t i = 0 ; i < tupleSize ; ++i ) {
143                                ast::TypeDecl * typeParam = new ast::TypeDecl( *location,
144                                        toString( "tuple_param_", tupleSize, "_", i ),
145                                        ast::Storage::Classes(),
146                                        nullptr,
147                                        ast::TypeDecl::Dtype,
148                                        true
149                                        );
150                                ast::ObjectDecl * member = new ast::ObjectDecl( *location,
151                                        toString( "field_", i ),
152                                        new ast::TypeInstType( typeParam )
153                                        );
154                                decl->params.push_back( typeParam );
155                                decl->members.push_back( member );
156                        }
157
158                        // Empty structures are not standard C. Add a dummy field to
159                        // empty tuples to silence warnings when a compound literal
160                        // `_tuple0_` is created.
161                        if ( tupleSize == 0 ) {
162                                decl->members.push_back(
163                                        new ast::ObjectDecl( *location,
164                                                "dummy",
165                                                new ast::BasicType( ast::BasicType::SignedInt ),
166                                                nullptr,
167                                                ast::Storage::Classes(),
168                                                // Does this have to be a C linkage?
169                                                ast::Linkage::C
170                                        )
171                                );
172                        }
173                        typeMap[tupleSize] = decl;
174                        declsToAddBefore.push_back( decl );
175                }
176
177                ast::StructDecl const * decl = typeMap[ tupleSize ];
178                ast::StructInstType * newType =
179                        new ast::StructInstType( decl, type->qualifiers );
180                for ( auto pair : group_iterate( type->types, decl->params ) ) {
181                        ast::Type const * t = std::get<0>( pair );
182                        newType->params.push_back(
183                                new ast::TypeExpr( *location, ast::deepCopy( t ) ) );
184                }
185                return newType;
186        }
187private:
188        ScopedMap< int, ast::StructDecl const * > typeMap;
189        CodeLocation const * location = nullptr;
190};
191
192struct TupleIndexExpander {
193        ast::Expr const * postvisit( ast::TupleIndexExpr const * expr ) {
194                CodeLocation const & location = expr->location;
195                ast::Expr const * tuple = expr->tuple.get();
196                assert( tuple );
197                unsigned int index = expr->index;
198                ast::TypeSubstitution const * env = expr->env.get();
199
200                if ( auto tupleExpr = dynamic_cast<ast::TupleExpr const *>( tuple ) ) {
201                        // Optimization: If it is a definitely pure tuple expr,
202                        // then it can reduce to the only relevant component.
203                        if ( !maybeImpureIgnoreUnique( tupleExpr ) ) {
204                                assert( index < tupleExpr->exprs.size() );
205                                ast::ptr<ast::Expr> const & expr =
206                                        *std::next( tupleExpr->exprs.begin(), index );
207                                ast::Expr * ret = ast::mutate( expr.get() );
208                                ret->env = env;
209                                return ret;
210                        }
211                }
212
213                auto type = tuple->result.strict_as<ast::StructInstType>();
214                ast::StructDecl const * structDecl = type->base;
215                assert( index < structDecl->members.size() );
216                ast::ptr<ast::Decl> const & member =
217                        *std::next( structDecl->members.begin(), index );
218                ast::MemberExpr * memberExpr = new ast::MemberExpr( location,
219                        member.strict_as<ast::DeclWithType>(), tuple );
220                memberExpr->env = env;
221                return memberExpr;
222        }
223};
224
225ast::Expr const * replaceTupleExpr(
226                CodeLocation const & location,
227                ast::Type const * result,
228                std::vector<ast::ptr<ast::Expr>> const & exprs,
229                ast::TypeSubstitution const * env ) {
230        assert( result );
231        // A void result: It doesn't need to produce a value for cascading,
232        // just output a chain of comma exprs.
233        if ( result->isVoid() ) {
234                assert( !exprs.empty() );
235                std::vector<ast::ptr<ast::Expr>>::const_iterator iter = exprs.begin();
236                ast::Expr * expr = new ast::CastExpr( *iter++ );
237                for ( ; iter != exprs.end() ; ++iter ) {
238                        expr = new ast::CommaExpr( location,
239                                expr, new ast::CastExpr( *iter ) );
240                }
241                expr->env = env;
242                return expr;
243        // Typed tuple expression: Produce a compound literal which performs
244        // each of the expressions as a distinct part of its initializer. The
245        // produced compound literal may be used as part of another expression.
246        } else {
247                auto inits = map_range<std::vector<ast::ptr<ast::Init>>>( exprs,
248                        []( ast::Expr const * expr ) {
249                                return new ast::SingleInit( expr->location, expr );
250                        }
251                );
252                ast::Expr * expr = new ast::CompoundLiteralExpr( location,
253                        result, new ast::ListInit( location, std::move( inits ) ) );
254                expr->env = env;
255                return expr;
256        }
257}
258
259struct TupleExprExpander {
260        ast::Expr const * postvisit( ast::TupleExpr const * expr ) {
261                return replaceTupleExpr( expr->location,
262                        expr->result, expr->exprs, expr->env );
263        }
264};
265
266} // namespace
267
268void expandMemberTuples( ast::TranslationUnit & translationUnit ) {
269        ast::Pass< MemberTupleExpander >::run( translationUnit );
270}
271
272void expandUniqueExpr( ast::TranslationUnit & translationUnit ) {
273        ast::Pass< UniqueExprExpander >::run( translationUnit );
274}
275
276void expandTuples( ast::TranslationUnit & translationUnit ) {
277        // These may not have to be seperate passes.
278        ast::Pass<TupleAssignExpander>::run( translationUnit );
279        ast::Pass<TupleTypeReplacer>::run( translationUnit );
280        ast::Pass<TupleIndexExpander>::run( translationUnit );
281        ast::Pass<TupleExprExpander>::run( translationUnit );
282}
283
284} // namespace Tuples
Note: See TracBrowser for help on using the repository browser.