Changeset f52ce6e

Timestamp:

Jun 19, 2019, 9:08:01 AM (5 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

5aa4656

Parents:

4487667 (diff), 73edfe9 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

src

Files:

• AST/porting.md (modified) (1 diff)
• ResolvExpr/CandidateFinder.cpp (modified) (10 diffs)
• ResolvExpr/RenameVars.cc (modified) (1 diff)
• ResolvExpr/RenameVars.h (modified) (1 diff)
• ResolvExpr/ResolveAssertions.cc (modified) (9 diffs)

src/AST/porting.md

@@ -305 +305 @@
 * switched order of `env`, `symtab` parameters for better consistency
 
+`findMinCost`
+* pulled out conversion cost promotion into separate `promoteCvtCost` function
+
 [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes
 

src/ResolvExpr/CandidateFinder.cpp

@@ -27 +27 @@
 #include "Cost.h"
 #include "ExplodedArg.hpp"
+#include "RenameVars.h"           // for renameTyVars
 #include "Resolver.h"
 #include "ResolveTypeof.h"
@@ -557 +558 @@
 
         /// Generate a cast expression from `arg` to `toType`
-        const ast::Expr * restructureCast( const ast::Expr * arg, const ast::Type * toType, bool isGenerated ) {
-                #warning unimplemented
-                (void)arg; (void)toType; (void)isGenerated;
-                assert(false);
-                return nullptr;
+        const ast::Expr * restructureCast( 
+                ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated 
+        ) {
+                if ( 
+                        arg->result->size() > 1 
+                        && ! toType->isVoid() 
+                        && ! dynamic_cast< const ast::ReferenceType * >( toType ) 
+                ) {
+                        // Argument is a tuple and the target type is neither void nor a reference. Cast each 
+                        // member of the tuple to its corresponding target type, producing the tuple of those 
+                        // cast expressions. If there are more components of the tuple than components in the 
+                        // target type, then excess components do not come out in the result expression (but 
+                        // UniqueExpr ensures that the side effects will still be produced)
+                        if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
+                                // expressions which may contain side effects require a single unique instance of 
+                                // the expression
+                                arg = new ast::UniqueExpr{ arg->location, arg };
+                        }
+                        std::vector< ast::ptr< ast::Expr > > components;
+                        for ( unsigned i = 0; i < toType->size(); ++i ) {
+                                // cast each component
+                                ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };
+                                components.emplace_back( 
+                                        restructureCast( idx, toType->getComponent( i ), isGenerated ) );
+                        }
+                        return new ast::TupleExpr{ arg->location, move( components ) };
+                } else {
+                        // handle normally
+                        return new ast::CastExpr{ arg->location, arg, toType, isGenerated };
+                }
+        }
+
+        /// Gets the name from an untyped member expression (must be NameExpr)
+        const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {
+                if ( memberExpr->member.as< ast::ConstantExpr >() ) {
+                        SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );
+                }
+
+                return memberExpr->member.strict_as< ast::NameExpr >()->name;
         }
 
@@ -764 +799 @@
 
                         if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
-                                addAggMembers( structInst, aggrExpr, cand, Cost::safe, "" );
+                                addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );
                         } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
-                                addAggMembers( unionInst, aggrExpr, cand, Cost::safe, "" );
+                                addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );
                         }
                 }
@@ -773 +808 @@
                 void addAggMembers( 
                         const ast::ReferenceToType * aggrInst, const ast::Expr * expr, 
-                        const CandidateRef & cand, const Cost & addedCost, const std::string & name 
+                        const Candidate & cand, const Cost & addedCost, const std::string & name 
                 ) {
                         for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
                                 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
                                 CandidateRef newCand = std::make_shared<Candidate>( 
-                                        *cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
+                                        cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
                                 // add anonymous member interpretations whenever an aggregate value type is seen 
                                 // as a member expression
                                 addAnonConversions( newCand );
                                 candidates.emplace_back( move( newCand ) );
+                        }
+                }
+
+                /// Adds tuple member interpretations
+                void addTupleMembers( 
+                        const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 
+                        const Cost & addedCost, const ast::Expr * member 
+                ) {
+                        if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {
+                                // get the value of the constant expression as an int, must be between 0 and the 
+                                // length of the tuple to have meaning
+                                long long val = constantExpr->intValue();
+                                if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
+                                        addCandidate(
+                                                cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, 
+                                                addedCost );
+                                }
                         }
                 }
@@ -1000 +1052 @@
                         }
 
-                        // castExpr->result should be replaced with toType
-                        // candidates => matches
-
-                        #warning unimplemented
-                        (void)castExpr;
-                        assert(false);
+                        // select first on argument cost, then conversion cost
+                        CandidateList minArgCost = findMinCost( matches );
+                        promoteCvtCost( minArgCost );
+                        candidates = findMinCost( minArgCost );
                 }
 
@@ -1021 +1071 @@
 
                 void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
-                        #warning unimplemented
-                        (void)memberExpr;
-                        assert(false);
+                        CandidateFinder aggFinder{ symtab, tenv };
+                        aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );
+                        for ( CandidateRef & agg : aggFinder.candidates ) {
+                                // it's okay for the aggregate expression to have reference type -- cast it to the 
+                                // base type to treat the aggregate as the referenced value
+                                Cost addedCost = Cost::zero;
+                                agg->expr = referenceToRvalueConversion( agg->expr, addedCost );
+
+                                // find member of the given type
+                                if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {
+                                        addAggMembers( 
+                                                structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
+                                } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {
+                                        addAggMembers( 
+                                                unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
+                                } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {
+                                        addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );
+                                }
+                        }
                 }
 
@@ -1030 +1096 @@
                 }
 
-                void postvisit( const ast::NameExpr * variableExpr ) {
-                        #warning unimplemented
-                        (void)variableExpr;
-                        assert(false);
+                void postvisit( const ast::NameExpr * nameExpr ) {
+                        std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name );
+                        PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
+                        for ( auto & data : declList ) {
+                                Cost cost = Cost::zero;
+                                ast::Expr * newExpr = data.combine( nameExpr->location, cost );
+
+                                CandidateRef newCand = std::make_shared<Candidate>(
+                                        newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 
+                                        cost );
+                                PRINT(
+                                        std::cerr << "decl is ";
+                                        ast::print( std::cerr, data.id );
+                                        std::cerr << std::endl;
+                                        std::cerr << "newExpr is ";
+                                        ast::print( std::cerr, newExpr );
+                                        std::cerr << std::endl;
+                                )
+                                newCand->expr = ast::mutate_field( 
+                                        newCand->expr.get(), &ast::Expr::result, 
+                                        renameTyVars( newCand->expr->result ) );
+                                // add anonymous member interpretations whenever an aggregate value type is seen 
+                                // as a name expression
+                                addAnonConversions( newCand );
+                                candidates.emplace_back( move( newCand ) );
+                        }
                 }
 
@@ -1048 +1136 @@
 
                 void postvisit( const ast::SizeofExpr * sizeofExpr ) {
-                        #warning unimplemented
-                        (void)sizeofExpr;
-                        assert(false);
+                        if ( sizeofExpr->type ) {
+                                addCandidate( 
+                                        new ast::SizeofExpr{ 
+                                                sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) }, 
+                                        tenv );
+                        } else {
+                                // find all candidates for the argument to sizeof
+                                CandidateFinder finder{ symtab, tenv };
+                                finder.find( sizeofExpr->expr );
+                                // find the lowest-cost candidate, otherwise ambiguous
+                                CandidateList winners = findMinCost( finder.candidates );
+                                if ( winners.size() != 1 ) {
+                                        SemanticError( 
+                                                sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );
+                                }
+                                // return the lowest-cost candidate
+                                CandidateRef & choice = winners.front();
+                                choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
+                                choice->cost = Cost::zero;
+                                addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );
+                        }
                 }
 
                 void postvisit( const ast::AlignofExpr * alignofExpr ) {
-                        #warning unimplemented
-                        (void)alignofExpr;
-                        assert(false);
+                        if ( alignofExpr->type ) {
+                                addCandidate( 
+                                        new ast::AlignofExpr{ 
+                                                alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) }, 
+                                        tenv );
+                        } else {
+                                // find all candidates for the argument to alignof
+                                CandidateFinder finder{ symtab, tenv };
+                                finder.find( alignofExpr->expr );
+                                // find the lowest-cost candidate, otherwise ambiguous
+                                CandidateList winners = findMinCost( finder.candidates );
+                                if ( winners.size() != 1 ) {
+                                        SemanticError( 
+                                                alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );
+                                }
+                                // return the lowest-cost candidate
+                                CandidateRef & choice = winners.front();
+                                choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
+                                choice->cost = Cost::zero;
+                                addCandidate( 
+                                        *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );
+                        }
                 }
 
                 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
-                        #warning unimplemented
-                        (void)offsetofExpr;
-                        assert(false);
+                        const ast::ReferenceToType * aggInst;
+                        if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;
+                        else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;
+                        else return;
+
+                        for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {
+                                auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );
+                                addCandidate( 
+                                        new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );
+                        }
                 }
 
@@ -1139 +1271 @@
                                                                 common ) 
                                                 ) {
-                                                        #warning unimplemented
-                                                        assert(false);
+                                                        // generate typed expression
+                                                        ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 
+                                                                conditionalExpr->location, r1->expr, r2->expr, r3->expr };
+                                                        newExpr->result = common ? common : r2->expr->result;
+                                                        // convert both options to result type
+                                                        Cost cost = r1->cost + r2->cost + r3->cost;
+                                                        newExpr->arg2 = computeExpressionConversionCost( 
+                                                                newExpr->arg2, newExpr->result, symtab, env, cost );
+                                                        newExpr->arg3 = computeExpressionConversionCost(
+                                                                newExpr->arg3, newExpr->result, symtab, env, cost );
+                                                        // output candidate
+                                                        CandidateRef newCand = std::make_shared<Candidate>(
+                                                                newExpr, move( env ), move( open ), move( need ), cost );
+                                                        inferParameters( newCand, candidates );
                                                 }
                                         }
@@ -1198 +1342 @@
                                                         common ) 
                                         ) {
+                                                // generate new expression
                                                 ast::RangeExpr * newExpr = 
                                                         new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
                                                 newExpr->result = common ? common : r1->expr->result;
-                                                
-                                                #warning unimplemented
-                                                assert(false);
+                                                // add candidate
+                                                CandidateRef newCand = std::make_shared<Candidate>(
+                                                        newExpr, move( env ), move( open ), move( need ), 
+                                                        r1->cost + r2->cost );
+                                                inferParameters( newCand, candidates );
                                         }
                                 }

src/ResolvExpr/RenameVars.cc

@@ -96 +96 @@
                 }
         } // namespace
+
+        const ast::Type * renameTyVars( const ast::Type * t ) {
+                #warning unimplemented; make sure resetTyVarRenaming() updated when implemented
+                (void)t;
+                assert(false);
+                return t;
+        }
 } // namespace ResolvExpr
 

src/ResolvExpr/RenameVars.h

@@ -23 +23 @@
 #include "SynTree/Visitor.h"  // for Visitor
 
+namespace ast {
+        class Type;
+}
+
 namespace ResolvExpr {
         /// Provides a consistent renaming of forall type names in a hierarchy by prefixing them with a unique "level" ID
         void renameTyVars( Type * );
+        const ast::Type * renameTyVars( const ast::Type * );
 
         /// resets internal state of renamer to avoid overflow

src/ResolvExpr/ResolveAssertions.cc

@@ -186 +186 @@
         using InferCache = std::unordered_map< UniqueId, InferredParams >;
 
+        /// Lexicographically-ordered vector of costs
+        using CostVec = std::vector< Cost >;
+
+        int compare( const CostVec & a, const CostVec & b ) {
+                unsigned i = 0;
+                do {
+                        // lex-compare where shorter one is less
+                        if ( i == a.size() ) {
+                                return i == b.size() ? 0 : -1;
+                        }
+                        if ( i == b.size() /* && i < a.size() */ ) return 1;
+                        
+                        int c = a[i].compare( b[i] );
+                        if ( c != 0 ) return c;
+                } while ( ++i );
+                assert(!"unreachable");
+        }
+
+        bool operator< ( const CostVec & a, const CostVec & b ) { return compare( a, b ) < 0; }
+
         /// Flag for state iteration
         enum IterateFlag { IterateState };
@@ -196 +216 @@
                 DeferList deferred;        ///< Deferred matches
                 InferCache inferred;       ///< Cache of already-inferred parameters
+                CostVec costs;             ///< Costs of recursive assertion satisfaction for disambiguation
                 SymTab::Indexer& indexer;  ///< Name lookup (depends on previous assertions)
 
                 /// Initial resolution state for an alternative
                 ResnState( Alternative& a, SymTab::Indexer& indexer )
-                : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
+                : alt(a), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero }, indexer(indexer) {
                         need.swap( a.need );
                 }
@@ -207 +228 @@
                 ResnState( ResnState&& o, IterateFlag )
                 : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(),
-                  inferred(std::move(o.inferred)), indexer(o.indexer) {}
+                  inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) {
+                        costs.emplace_back( Cost::zero );
+                }
         };
 
@@ -336 +359 @@
         };
 
-        void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
-                PassVisitor<InferMatcher> matcher{ inferred };
-                alt.expr = alt.expr->acceptMutator( matcher );
-                out.emplace_back( alt );
+        /// Map of alternative return types to recursive assertion satisfaction costs
+        using PruneMap = std::unordered_map<std::string, CostVec>;
+
+        /// Gets the pruning key for an alternative
+        std::string pruneKey( const Alternative & alt ) {
+                Type* resType = alt.expr->result->clone();
+                alt.env.apply( resType );
+                std::string resKey = SymTab::Mangler::mangleType( resType );
+                delete resType;
+                return std::move( resKey );
+        }
+        
+        /// Replace resnSlots with inferParams and add alternative to output list, if meets pruning 
+        /// threshold.
+        void finalizeAssertions( ResnState& resn, PruneMap & pruneThresholds, AltList& out ) {
+                // prune if cheaper alternative for same key has already been generated
+                std::string resKey = pruneKey( resn.alt );
+                auto it = pruneThresholds.find( resKey );
+                if ( it != pruneThresholds.end() ) {
+                        if ( it->second < resn.costs ) return;
+                } else {
+                        pruneThresholds.emplace_hint( it, resKey, resn.costs );
+                }
+
+                // replace resolution slots with inferred params, add to output
+                PassVisitor<InferMatcher> matcher{ resn.inferred };
+                resn.alt.expr = resn.alt.expr->acceptMutator( matcher );
+                out.emplace_back( resn.alt );
         }
 
@@ -359 +406 @@
                 ResnList resns{ ResnState{ alt, root_indexer } };
                 ResnList new_resns{};
+                
+                // Pruning thresholds by result type of the output alternatives.
+                // Alternatives *should* be generated in sorted order, so no need to retroactively prune
+                PruneMap thresholds;
 
                 // resolve assertions in breadth-first-order up to a limited number of levels deep
@@ -364 +415 @@
                         // scan over all mutually-compatible resolutions
                         for ( auto& resn : resns ) {
+                                // stop this branch if already found a better option
+                                auto it = thresholds.find( pruneKey( resn.alt ) );
+                                if ( it != thresholds.end() && it->second < resn.costs ) goto nextResn;
+
                                 // make initial pass at matching assertions
                                 for ( auto& assn : resn.need ) {
@@ -383 +438 @@
                                         // either add successful match or push back next state
                                         if ( resn.newNeed.empty() ) {
-                                                finalizeAssertions( resn.alt, resn.inferred, out );
+                                                finalizeAssertions( resn, thresholds, out );
                                         } else {
                                                 new_resns.emplace_back( std::move(resn), IterateState );
@@ -420 +475 @@
                                                 goto nextResn;
                                         }
-                                        // sort by cost
+                                        // sort by cost for overall pruning
                                         CandidateCost coster{ resn.indexer };
                                         std::sort( compatible.begin(), compatible.end(), coster );
 
-                                        // keep map of detected options
-                                        std::unordered_map<std::string, Cost> found;
                                         for ( auto& compat : compatible ) {
-                                                // filter by environment-adjusted result type, keep only cheapest option
-                                                Type* resType = alt.expr->result->clone();
-                                                compat.env.apply( resType );
-                                                // skip if cheaper alternative already processed with same result type
-                                                Cost resCost = coster.get( compat );
-                                                auto it = found.emplace( SymTab::Mangler::mangleType( resType ), resCost );
-                                                delete resType;
-                                                if ( it.second == false && it.first->second < resCost ) continue;
-
-                                                // proceed with resolution step
                                                 ResnState new_resn = resn;
 
@@ -452 +495 @@
                                                 new_resn.alt.openVars = std::move(compat.openVars);
 
+                                                // mark cost of this path
+                                                new_resn.costs.back() += compat.cost;
+
                                                 // either add sucessful match or push back next state
                                                 if ( new_resn.newNeed.empty() ) {
-                                                        finalizeAssertions( new_resn.alt, new_resn.inferred, out );
+                                                        finalizeAssertions( new_resn, thresholds, out );
                                                 } else {
                                                         new_resns.emplace_back( std::move(new_resn), IterateState );