[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 |
---|
| 12 | // Last Modified On : Mon Jul 29 14:06:00 2022 |
---|
| 13 | // Update Count : 2 |
---|
[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 | |
---|
| 102 | struct 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 | |
---|
| 110 | struct 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 | } |
---|
| 187 | private: |
---|
| 188 | ScopedMap< int, ast::StructDecl const * > typeMap; |
---|
| 189 | CodeLocation const * location = nullptr; |
---|
| 190 | }; |
---|
| 191 | |
---|
| 192 | struct 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 | |
---|
| 225 | ast::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 | |
---|
| 259 | struct 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 | |
---|
[ce1d721] | 268 | void expandMemberTuples( ast::TranslationUnit & translationUnit ) { |
---|
| 269 | ast::Pass< MemberTupleExpander >::run( translationUnit ); |
---|
| 270 | } |
---|
| 271 | |
---|
| 272 | void expandUniqueExpr( ast::TranslationUnit & translationUnit ) { |
---|
| 273 | ast::Pass< UniqueExprExpander >::run( translationUnit ); |
---|
| 274 | } |
---|
| 275 | |
---|
[b507dcd] | 276 | void 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 | |
---|
[d249e0b] | 284 | } // namespace Tuples |
---|