Index: src/Tuples/Explode.cc =================================================================== --- src/Tuples/Explode.cc (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) +++ src/Tuples/Explode.cc (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) @@ -0,0 +1,82 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Explode.cc -- +// +// Author : Rob Schluntz +// Created On : Wed Nov 9 13:12:24 2016 +// Last Modified By : Rob Schluntz +// Last Modified On : Wed Nov 9 13:20:24 2016 +// Update Count : 2 +// + +#include "Explode.h" +#include "SynTree/Mutator.h" + +namespace Tuples { + namespace { + struct AddrExploder : public Mutator { + bool foundUniqueExpr = false; + Expression * applyAddr( Expression * expr, bool first = true ) { + if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( expr ) ){ + std::list< Expression * > exprs; + for ( Expression *& expr : tupleExpr->get_exprs() ) { + // move & into tuple exprs + exprs.push_back( applyAddr( expr, false ) ); + } + // want the top-level expression to be address-taken, but not nested + // tuple expressions + if ( first ) { + return new AddressExpr( new TupleExpr( exprs ) ); + } else { + return new TupleExpr( exprs ); + } + } + // anything else should be address-taken as normal + return new AddressExpr( expr->clone() ); + } + + virtual Expression * mutate( UniqueExpr * uniqueExpr ) { + // move & into unique expr so that the unique expr has type T* rather than + // type T. In particular, this transformation helps with generating the + // correct code for address-taken member tuple expressions, since the result + // should now be a tuple of addresses rather than the address of a tuple. + // Still, this code is a bit awkward, and could use some improvement. + foundUniqueExpr = true; + UniqueExpr * newUniqueExpr = new UniqueExpr( applyAddr( uniqueExpr->get_expr() ), uniqueExpr->get_id() ); + delete uniqueExpr; + UntypedExpr * deref = UntypedExpr::createDeref( Mutator::mutate( newUniqueExpr ) ); + return deref; + } + + virtual Expression * mutate( TupleIndexExpr * tupleExpr ) { + // tuple index expr needs to be rebuilt to ensure that the type of the + // field is consistent with the type of the tuple expr, since the field + // may have changed from type T to T*. + Expression * expr = tupleExpr->get_tuple()->acceptMutator( *this ); + tupleExpr->set_tuple( nullptr ); + TupleIndexExpr * ret = new TupleIndexExpr( expr, tupleExpr->get_index() ); + delete tupleExpr; + return ret; + } + }; + } // namespace + + Expression * distributeAddr( Expression * expr ) { + AddrExploder addrExploder; + expr = expr->acceptMutator( addrExploder ); + if ( ! addrExploder.foundUniqueExpr ) { + expr = new AddressExpr( expr ); + } + return expr; + } +} // namespace Tuples + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Tuples/Explode.h =================================================================== --- src/Tuples/Explode.h (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) +++ src/Tuples/Explode.h (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) @@ -0,0 +1,97 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Explode.h -- +// +// Author : Rob Schluntz +// Created On : Wed Nov 9 13:12:24 2016 +// Last Modified By : Rob Schluntz +// Last Modified On : Wed Nov 9 13:20:24 2016 +// Update Count : 2 +// + +#ifndef _EXPLODE_H_ +#define _EXPLODE_H_ + +#include "ResolvExpr/AlternativeFinder.h" +#include "ResolvExpr/Resolver.h" + +#include "SynTree/Expression.h" +#include "SynTree/Declaration.h" +#include "SynTree/Type.h" + +#include "Tuples.h" + +namespace Tuples { + /// helper function used by explode to properly distribute + /// '&' across a tuple expression + Expression * distributeAddr( Expression * expr ); + + /// helper function used by explode + template< typename OutputIterator > + void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt, const SymTab::Indexer & indexer, OutputIterator out ) { + Type * res = expr->get_result(); + if ( AddressExpr * addrExpr = dynamic_cast< AddressExpr * >( expr ) ) { + ResolvExpr::AltList alts; + explodeUnique( addrExpr->get_arg(), alt, indexer, back_inserter( alts ) ); + for ( ResolvExpr::Alternative & alt : alts ) { + // distribute '&' over all components + alt.expr = distributeAddr( alt.expr ); + *out++ = alt; + } + } else if ( TupleType * tupleType = dynamic_cast< TupleType * > ( res ) ) { + if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( expr ) ) { + // can open tuple expr and dump its exploded components + for ( Expression * expr : tupleExpr->get_exprs() ) { + explodeUnique( expr, alt, indexer, out ); + } + } else { + // tuple type, but not tuple expr - recursively index into its components + Expression * arg = expr->clone(); + if ( Tuples::maybeImpure( arg ) && ! dynamic_cast< UniqueExpr * >( arg ) ) { + // expressions which may contain side effects require a single unique instance of the expression. + arg = new UniqueExpr( arg ); + } + for ( unsigned int i = 0; i < tupleType->size(); i++ ) { + TupleIndexExpr * idx = new TupleIndexExpr( arg->clone(), i ); + explodeUnique( idx, alt, indexer, out ); + delete idx; + } + delete arg; + } + } else { + // atomic (non-tuple) type - output a clone of the expression in a new alternative + *out++ = ResolvExpr::Alternative( expr->clone(), alt.env, alt.cost, alt.cvtCost ); + } + } + + /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type + template< typename OutputIterator > + void explode( const ResolvExpr::Alternative &alt, const SymTab::Indexer & indexer, OutputIterator out ) { + explodeUnique( alt.expr, alt, indexer, out ); + } + + // explode list of alternatives + template< typename AltIterator, typename OutputIterator > + void explode( AltIterator altBegin, AltIterator altEnd, const SymTab::Indexer & indexer, OutputIterator out ) { + for ( ; altBegin != altEnd; ++altBegin ) { + explode( *altBegin, indexer, out ); + } + } + + template< typename OutputIterator > + void explode( const ResolvExpr::AltList & alts, const SymTab::Indexer & indexer, OutputIterator out ) { + explode( alts.begin(), alts.end(), indexer, out ); + } +} // namespace Tuples + +#endif // _TUPLE_ASSIGNMENT_H_ + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision b3b2077b1feda429f174cfb4f374cb1e00580630) +++ src/Tuples/TupleAssignment.cc (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) @@ -20,4 +20,5 @@ #include "SynTree/Initializer.h" #include "Tuples.h" +#include "Explode.h" #include "Common/SemanticError.h" #include "InitTweak/InitTweak.h" Index: src/Tuples/TupleExpansion.cc =================================================================== --- src/Tuples/TupleExpansion.cc (revision b3b2077b1feda429f174cfb4f374cb1e00580630) +++ src/Tuples/TupleExpansion.cc (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) @@ -41,6 +41,14 @@ public: typedef GenPoly::DeclMutator Parent; + virtual Expression * mutate( UniqueExpr * unqExpr ); - std::map< int, ObjectDecl * > decls; // not vector, because order added may not be increasing order + + std::map< int, Expression * > decls; // not vector, because order added may not be increasing order + + ~UniqueExprExpander() { + for ( std::pair & p : decls ) { + delete p.second; + } + } }; @@ -107,5 +115,5 @@ /// given a expression representing the member and an expression representing the aggregate, /// reconstructs a flattened UntypedMemberExpr with the right precedence - Expression * reconstructMemberExpr( Expression * member, UniqueExpr * aggr ) { + Expression * reconstructMemberExpr( Expression * member, Expression * aggr ) { if ( UntypedMemberExpr * memberExpr = dynamic_cast< UntypedMemberExpr * >( member ) ) { // construct a new UntypedMemberExpr with the correct structure , and recursively @@ -127,9 +135,13 @@ Expression * MemberTupleExpander::mutate( UntypedMemberExpr * memberExpr ) { if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * > ( memberExpr->get_member() ) ) { - UniqueExpr * unqExpr = new UniqueExpr( memberExpr->get_aggregate()->clone() ); + Expression * aggr = memberExpr->get_aggregate()->clone()->acceptMutator( *this ); + // aggregate expressions which might be impure must be wrapped in unique expressions + // xxx - if there's a member-tuple expression nested in the aggregate, this currently generates the wrong code if a UniqueExpr is not used, and it's purely an optimization to remove the UniqueExpr + // if ( Tuples::maybeImpure( memberExpr->get_aggregate() ) ) aggr = new UniqueExpr( aggr ); + aggr = new UniqueExpr( aggr ); for ( Expression *& expr : tupleExpr->get_exprs() ) { - expr = reconstructMemberExpr( expr, unqExpr ); - } - delete unqExpr; + expr = reconstructMemberExpr( expr, aggr ); + } + delete aggr; return tupleExpr; } else { @@ -142,31 +154,42 @@ Expression * UniqueExprExpander::mutate( UniqueExpr * unqExpr ) { unqExpr = safe_dynamic_cast< UniqueExpr * > ( Parent::mutate( unqExpr ) ); - if ( ! decls.count( unqExpr->get_id() ) ) { - // xxx - it's possible (likely?) that expressions can appear in the wrong order because of this. Need to ensure they're placed in the correct location. - - // xxx - this doesn't work, because it would need to be placed after fixInit, but fixInit doesn't know (and shouldn't have to know) about the existance of UniqueExprs - i.e. it will visit them twice - // need to construct/destruct unique exprs in general - maybe it's not worth it and fixInit should handle UniqueExpr explicitly? - // currently, tmp is being destructed before unqExpr is used, which suggests there should be a separate lifetime for unqExpr from the tmp_ret - - // if ( CommaExpr * commaExpr = dynamic_cast< CommaExpr * >( unqExpr->get_expr() ) ) { - // if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( commaExpr->get_arg2() ) ) { - // // steal existing decl from expr - // if ( ObjectDecl * decl = dynamic_cast< ObjectDecl * >( varExpr->get_var() ) ) { - // decls[unqExpr->get_id()] = decl; - // return unqExpr->get_expr()->clone(); - // } - // } - // } - - ObjectDecl * objDecl = unqExpr->get_object(); - unqExpr->set_object( nullptr ); - decls[unqExpr->get_id()] = objDecl; - addDeclaration( objDecl ); - } - return new VariableExpr( decls[unqExpr->get_id()] ); + const int id = unqExpr->get_id(); + + // on first time visiting a unique expr with a particular ID, generate the expression that replaces all UniqueExprs with that ID, + // and lookup on subsequent hits. This ensures that all unique exprs with the same ID reference the same variable. + if ( ! decls.count( id ) ) { + Expression * assignUnq; + Expression * var = unqExpr->get_var(); + if ( unqExpr->get_object() ) { + // an object was generated to represent this unique expression -- it should be added to the list of declarations now + addDeclaration( unqExpr->get_object() ); + unqExpr->set_object( nullptr ); + // steal the expr from the unqExpr + assignUnq = UntypedExpr::createAssign( unqExpr->get_var()->clone(), unqExpr->get_expr() ); + unqExpr->set_expr( nullptr ); + } else { + // steal the already generated assignment to var from the unqExpr - this has been generated by FixInit + Expression * expr = unqExpr->get_expr(); + CommaExpr * commaExpr = safe_dynamic_cast< CommaExpr * >( expr ); + assignUnq = commaExpr->get_arg1(); + commaExpr->set_arg1( nullptr ); + } + BasicType * boolType = new BasicType( Type::Qualifiers(), BasicType::Bool ); + ObjectDecl * finished = new ObjectDecl( toString( "_unq_expr_finished_", id ), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, nullptr, new BasicType( Type::Qualifiers(), BasicType::Bool ), new SingleInit( new ConstantExpr( Constant( boolType->clone(), "0" ) ), noDesignators ) ); + addDeclaration( finished ); + // (finished ? _unq_expr_N : (_unq_expr_N = get_expr()>, finished = 1, _unq_expr_N)) + // This pattern ensures that each unique expression is evaluated once, regardless of evaluation order of the generated C code. + Expression * assignFinished = UntypedExpr::createAssign( new VariableExpr(finished), new ConstantExpr( Constant( boolType->clone(), "1" ) ) ); + ConditionalExpr * condExpr = new ConditionalExpr( new VariableExpr( finished ), var->clone(), + new CommaExpr( new CommaExpr( assignUnq, assignFinished ), var->clone() ) ); + condExpr->set_result( var->get_result()->clone() ); + decls[id] = condExpr; + } + delete unqExpr; + return decls[id]->clone(); } Expression * TupleAssignExpander::mutate( TupleAssignExpr * assnExpr ) { - // xxx - Parent::mutate? + assnExpr = safe_dynamic_cast< TupleAssignExpr * >( Parent::mutate( assnExpr ) ); CompoundStmt * compoundStmt = new CompoundStmt( noLabels ); std::list< Statement * > & stmts = compoundStmt->get_kids(); @@ -192,5 +215,5 @@ int cnt = 0; for ( Type * t : *newType ) { - decl->get_members().push_back( new ObjectDecl( "field_"+std::to_string(++cnt), DeclarationNode::NoStorageClass, LinkageSpec::C, nullptr, t->clone(), nullptr ) ); + decl->get_members().push_back( new ObjectDecl( toString("field_", cnt++), DeclarationNode::NoStorageClass, LinkageSpec::C, nullptr, t->clone(), nullptr ) ); } typeMap[mangleName] = decl; Index: src/Tuples/Tuples.h =================================================================== --- src/Tuples/Tuples.h (revision b3b2077b1feda429f174cfb4f374cb1e00580630) +++ src/Tuples/Tuples.h (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) @@ -9,7 +9,7 @@ // Author : Rodolfo G. Esteves // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Mon May 18 15:04:02 2015 -// Update Count : 2 +// Last Modified By : Rob Schluntz +// Last Modified On : Wed Nov 9 13:17:58 2016 +// Update Count : 15 // @@ -18,11 +18,10 @@ #include -#include -#include "ResolvExpr/AlternativeFinder.h" -#include "ResolvExpr/Resolver.h" #include "SynTree/Expression.h" #include "SynTree/Declaration.h" #include "SynTree/Type.h" + +#include "ResolvExpr/AlternativeFinder.h" namespace Tuples { @@ -45,65 +44,4 @@ /// returns true if the expression may contain side-effects. bool maybeImpure( Expression * expr ); - - - /// helper function used by explode - template< typename OutputIterator > - void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt, const SymTab::Indexer & indexer, OutputIterator out ) { - Type * res = expr->get_result(); - if ( AddressExpr * addrExpr = dynamic_cast< AddressExpr * >( expr ) ) { - ResolvExpr::AltList alts; - explodeUnique( addrExpr->get_arg(), alt, indexer, back_inserter( alts ) ); - for ( ResolvExpr::Alternative & alt : alts ) { - // distribute '&' over all components - alt.expr = new AddressExpr( alt.expr ); - *out++ = alt; - } - } else if ( TupleType * tupleType = dynamic_cast< TupleType * > ( res ) ) { - if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( expr ) ) { - // can open tuple expr and dump its exploded components - for ( Expression * expr : tupleExpr->get_exprs() ) { - explodeUnique( expr, alt, indexer, out ); - } - } else { - // tuple type, but not tuple expr - recursively index into its components - Expression * arg = expr->clone(); - if ( Tuples::maybeImpure( arg ) ) { - // expressions which may contain side effects require a single unique instance of the expression. - // resolve the UniqueExpr (which should be relatively cheap, since the argument is already resolved) - // so that its accompanying object is properly constructed and destructed. - arg = new UniqueExpr( arg ); - arg = ResolvExpr::resolveInVoidContext( arg, indexer ); - } - for ( unsigned int i = 0; i < tupleType->size(); i++ ) { - TupleIndexExpr * idx = new TupleIndexExpr( arg->clone(), i ); - explodeUnique( idx, alt, indexer, out ); - delete idx; - } - delete arg; - } - } else { - // atomic (non-tuple) type - output a clone of the expression in a new alternative - *out++ = ResolvExpr::Alternative( expr->clone(), alt.env, alt.cost, alt.cvtCost ); - } - } - - /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type - template< typename OutputIterator > - void explode( const ResolvExpr::Alternative &alt, const SymTab::Indexer & indexer, OutputIterator out ) { - explodeUnique( alt.expr, alt, indexer, out ); - } - - // explode list of alternatives - template< typename AltIterator, typename OutputIterator > - void explode( AltIterator altBegin, AltIterator altEnd, const SymTab::Indexer & indexer, OutputIterator out ) { - for ( ; altBegin != altEnd; ++altBegin ) { - explode( *altBegin, indexer, out ); - } - } - - template< typename OutputIterator > - void explode( const ResolvExpr::AltList & alts, const SymTab::Indexer & indexer, OutputIterator out ) { - explode( alts.begin(), alts.end(), indexer, out ); - } } // namespace Tuples Index: src/Tuples/module.mk =================================================================== --- src/Tuples/module.mk (revision b3b2077b1feda429f174cfb4f374cb1e00580630) +++ src/Tuples/module.mk (revision 141b7868c72c7947affae41e61e4bfcd7f9c6652) @@ -16,3 +16,4 @@ SRC += Tuples/TupleAssignment.cc \ - Tuples/TupleExpansion.cc + Tuples/TupleExpansion.cc \ + Tuples/Explode.cc