[d249e0b] | 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 |
---|
[ce1d721] | 11 | // Last Modified By : Andrew Beach |
---|
[e9e9f56] | 12 | // Last Modified On : Tue Sep 20 16:17:00 2022 |
---|
| 13 | // Update Count : 4 |
---|
[d249e0b] | 14 | // |
---|
| 15 | |
---|
| 16 | #include "Tuples.h" |
---|
| 17 | |
---|
[b507dcd] | 18 | #include "AST/Pass.hpp" |
---|
| 19 | #include "Common/ScopedMap.h" |
---|
| 20 | |
---|
[d249e0b] | 21 | namespace Tuples { |
---|
[ce1d721] | 22 | |
---|
[d249e0b] | 23 | namespace { |
---|
| 24 | |
---|
[ce1d721] | 25 | struct 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 | }; |
---|
[d249e0b] | 29 | |
---|
[ce1d721] | 30 | struct 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 |
---|
| 37 | const 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 ); |
---|
[d249e0b] | 48 | } |
---|
[ce1d721] | 49 | } |
---|
[d249e0b] | 50 | |
---|
[ce1d721] | 51 | const 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 ); |
---|
[d249e0b] | 60 | } |
---|
[ce1d721] | 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 ) ); |
---|
[d249e0b] | 65 | } |
---|
[01d433e] | 66 | } |
---|
| 67 | |
---|
[ce1d721] | 68 | const ast::Expr * UniqueExprExpander::postvisit( const ast::UniqueExpr * unqExpr ) { |
---|
| 69 | const CodeLocation loc = unqExpr->location; |
---|
| 70 | const int id = unqExpr->id; |
---|
[01d433e] | 71 | |
---|
[ce1d721] | 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; |
---|
[01d433e] | 85 | } |
---|
[ce1d721] | 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; |
---|
[01d433e] | 98 | } |
---|
[ce1d721] | 99 | return ast::deepCopy(decls[id].get()); |
---|
| 100 | } |
---|
[b507dcd] | 101 | |
---|
[e116db3] | 102 | /// Replaces Tuple Assign & Index Expressions, and Tuple Types. |
---|
[c36814a] | 103 | struct TupleMainExpander final : |
---|
[e9e9f56] | 104 | public ast::WithCodeLocation, |
---|
| 105 | public ast::WithDeclsToAdd<>, |
---|
[e116db3] | 106 | public ast::WithGuards, |
---|
[e9e9f56] | 107 | public ast::WithVisitorRef<TupleMainExpander> { |
---|
[b507dcd] | 108 | ast::Expr const * postvisit( ast::TupleAssignExpr const * expr ) { |
---|
| 109 | // Just move the env on the new top level expression. |
---|
| 110 | return ast::mutate_field( expr->stmtExpr.get(), |
---|
| 111 | &ast::TupleAssignExpr::env, expr->env.get() ); |
---|
| 112 | } |
---|
| 113 | |
---|
[e9e9f56] | 114 | void previsit( ast::CompoundStmt const * ) { |
---|
[b507dcd] | 115 | GuardScope( typeMap ); |
---|
| 116 | } |
---|
| 117 | |
---|
| 118 | ast::Expr const * postvisit( ast::Expr const * expr ) { |
---|
| 119 | if ( nullptr == expr->env ) { |
---|
| 120 | return expr; |
---|
| 121 | } |
---|
| 122 | // TypeSubstitutions are never visited in the new Pass template, |
---|
| 123 | // so it is done manually here, where all types have to be replaced. |
---|
| 124 | return ast::mutate_field( expr, &ast::Expr::env, |
---|
| 125 | expr->env->accept( *visitor ) ); |
---|
| 126 | } |
---|
| 127 | |
---|
| 128 | ast::Type const * postvisit( ast::TupleType const * type ) { |
---|
| 129 | assert( location ); |
---|
| 130 | unsigned tupleSize = type->size(); |
---|
| 131 | if ( !typeMap.count( tupleSize ) ) { |
---|
| 132 | ast::StructDecl * decl = new ast::StructDecl( *location, |
---|
| 133 | toString( "_tuple", tupleSize, "_" ) |
---|
| 134 | ); |
---|
| 135 | decl->body = true; |
---|
| 136 | |
---|
| 137 | for ( size_t i = 0 ; i < tupleSize ; ++i ) { |
---|
| 138 | ast::TypeDecl * typeParam = new ast::TypeDecl( *location, |
---|
| 139 | toString( "tuple_param_", tupleSize, "_", i ), |
---|
| 140 | ast::Storage::Classes(), |
---|
| 141 | nullptr, |
---|
| 142 | ast::TypeDecl::Dtype, |
---|
| 143 | true |
---|
| 144 | ); |
---|
| 145 | ast::ObjectDecl * member = new ast::ObjectDecl( *location, |
---|
| 146 | toString( "field_", i ), |
---|
| 147 | new ast::TypeInstType( typeParam ) |
---|
| 148 | ); |
---|
| 149 | decl->params.push_back( typeParam ); |
---|
| 150 | decl->members.push_back( member ); |
---|
| 151 | } |
---|
| 152 | |
---|
| 153 | // Empty structures are not standard C. Add a dummy field to |
---|
| 154 | // empty tuples to silence warnings when a compound literal |
---|
| 155 | // `_tuple0_` is created. |
---|
| 156 | if ( tupleSize == 0 ) { |
---|
| 157 | decl->members.push_back( |
---|
| 158 | new ast::ObjectDecl( *location, |
---|
| 159 | "dummy", |
---|
| 160 | new ast::BasicType( ast::BasicType::SignedInt ), |
---|
| 161 | nullptr, |
---|
| 162 | ast::Storage::Classes(), |
---|
| 163 | // Does this have to be a C linkage? |
---|
| 164 | ast::Linkage::C |
---|
| 165 | ) |
---|
| 166 | ); |
---|
| 167 | } |
---|
| 168 | typeMap[tupleSize] = decl; |
---|
| 169 | declsToAddBefore.push_back( decl ); |
---|
| 170 | } |
---|
| 171 | |
---|
| 172 | ast::StructDecl const * decl = typeMap[ tupleSize ]; |
---|
| 173 | ast::StructInstType * newType = |
---|
| 174 | new ast::StructInstType( decl, type->qualifiers ); |
---|
| 175 | for ( auto pair : group_iterate( type->types, decl->params ) ) { |
---|
| 176 | ast::Type const * t = std::get<0>( pair ); |
---|
| 177 | newType->params.push_back( |
---|
| 178 | new ast::TypeExpr( *location, ast::deepCopy( t ) ) ); |
---|
| 179 | } |
---|
| 180 | return newType; |
---|
| 181 | } |
---|
| 182 | |
---|
| 183 | ast::Expr const * postvisit( ast::TupleIndexExpr const * expr ) { |
---|
| 184 | CodeLocation const & location = expr->location; |
---|
| 185 | ast::Expr const * tuple = expr->tuple.get(); |
---|
| 186 | assert( tuple ); |
---|
| 187 | unsigned int index = expr->index; |
---|
| 188 | ast::TypeSubstitution const * env = expr->env.get(); |
---|
| 189 | |
---|
| 190 | if ( auto tupleExpr = dynamic_cast<ast::TupleExpr const *>( tuple ) ) { |
---|
| 191 | // Optimization: If it is a definitely pure tuple expr, |
---|
| 192 | // then it can reduce to the only relevant component. |
---|
| 193 | if ( !maybeImpureIgnoreUnique( tupleExpr ) ) { |
---|
| 194 | assert( index < tupleExpr->exprs.size() ); |
---|
| 195 | ast::ptr<ast::Expr> const & expr = |
---|
| 196 | *std::next( tupleExpr->exprs.begin(), index ); |
---|
| 197 | ast::Expr * ret = ast::mutate( expr.get() ); |
---|
| 198 | ret->env = env; |
---|
| 199 | return ret; |
---|
| 200 | } |
---|
| 201 | } |
---|
| 202 | |
---|
| 203 | auto type = tuple->result.strict_as<ast::StructInstType>(); |
---|
| 204 | ast::StructDecl const * structDecl = type->base; |
---|
| 205 | assert( index < structDecl->members.size() ); |
---|
| 206 | ast::ptr<ast::Decl> const & member = |
---|
| 207 | *std::next( structDecl->members.begin(), index ); |
---|
| 208 | ast::MemberExpr * memberExpr = new ast::MemberExpr( location, |
---|
| 209 | member.strict_as<ast::DeclWithType>(), tuple ); |
---|
| 210 | memberExpr->env = env; |
---|
| 211 | return memberExpr; |
---|
| 212 | } |
---|
[e116db3] | 213 | private: |
---|
| 214 | ScopedMap< int, ast::StructDecl const * > typeMap; |
---|
[b507dcd] | 215 | }; |
---|
| 216 | |
---|
| 217 | ast::Expr const * replaceTupleExpr( |
---|
| 218 | CodeLocation const & location, |
---|
| 219 | ast::Type const * result, |
---|
| 220 | std::vector<ast::ptr<ast::Expr>> const & exprs, |
---|
| 221 | ast::TypeSubstitution const * env ) { |
---|
| 222 | assert( result ); |
---|
| 223 | // A void result: It doesn't need to produce a value for cascading, |
---|
| 224 | // just output a chain of comma exprs. |
---|
| 225 | if ( result->isVoid() ) { |
---|
| 226 | assert( !exprs.empty() ); |
---|
| 227 | std::vector<ast::ptr<ast::Expr>>::const_iterator iter = exprs.begin(); |
---|
| 228 | ast::Expr * expr = new ast::CastExpr( *iter++ ); |
---|
| 229 | for ( ; iter != exprs.end() ; ++iter ) { |
---|
| 230 | expr = new ast::CommaExpr( location, |
---|
| 231 | expr, new ast::CastExpr( *iter ) ); |
---|
| 232 | } |
---|
| 233 | expr->env = env; |
---|
| 234 | return expr; |
---|
| 235 | // Typed tuple expression: Produce a compound literal which performs |
---|
| 236 | // each of the expressions as a distinct part of its initializer. The |
---|
| 237 | // produced compound literal may be used as part of another expression. |
---|
| 238 | } else { |
---|
| 239 | auto inits = map_range<std::vector<ast::ptr<ast::Init>>>( exprs, |
---|
| 240 | []( ast::Expr const * expr ) { |
---|
| 241 | return new ast::SingleInit( expr->location, expr ); |
---|
| 242 | } |
---|
| 243 | ); |
---|
| 244 | ast::Expr * expr = new ast::CompoundLiteralExpr( location, |
---|
| 245 | result, new ast::ListInit( location, std::move( inits ) ) ); |
---|
| 246 | expr->env = env; |
---|
| 247 | return expr; |
---|
| 248 | } |
---|
| 249 | } |
---|
| 250 | |
---|
[c36814a] | 251 | struct TupleExprExpander final { |
---|
[b507dcd] | 252 | ast::Expr const * postvisit( ast::TupleExpr const * expr ) { |
---|
| 253 | return replaceTupleExpr( expr->location, |
---|
| 254 | expr->result, expr->exprs, expr->env ); |
---|
| 255 | } |
---|
| 256 | }; |
---|
| 257 | |
---|
| 258 | } // namespace |
---|
| 259 | |
---|
[ce1d721] | 260 | void expandMemberTuples( ast::TranslationUnit & translationUnit ) { |
---|
| 261 | ast::Pass< MemberTupleExpander >::run( translationUnit ); |
---|
| 262 | } |
---|
| 263 | |
---|
| 264 | void expandUniqueExpr( ast::TranslationUnit & translationUnit ) { |
---|
| 265 | ast::Pass< UniqueExprExpander >::run( translationUnit ); |
---|
| 266 | } |
---|
| 267 | |
---|
[b507dcd] | 268 | void expandTuples( ast::TranslationUnit & translationUnit ) { |
---|
[e116db3] | 269 | // These can't just be combined simply (there might be a way with work). |
---|
| 270 | ast::Pass<TupleMainExpander>::run( translationUnit ); |
---|
[b507dcd] | 271 | ast::Pass<TupleExprExpander>::run( translationUnit ); |
---|
| 272 | } |
---|
| 273 | |
---|
[d249e0b] | 274 | } // namespace Tuples |
---|