source: src/Tuples/TupleExpansionNew.cpp @ 1d66a91

Last change on this file since 1d66a91 was 36cb4d9, checked in by Andrew Beach <ajbeach@…>, 2 years ago

Reorganize the expandTuple pass to hopefully make it easier to follow.

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