Changeset f52ce6e


Ignore:
Timestamp:
Jun 19, 2019, 9:08:01 AM (2 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
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:
5 edited

Legend:

Unmodified
Added
Removed
  • src/AST/porting.md

    r4487667 rf52ce6e  
    305305* switched order of `env`, `symtab` parameters for better consistency
    306306
     307`findMinCost`
     308* pulled out conversion cost promotion into separate `promoteCvtCost` function
     309
    307310[1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes
    308311
  • src/ResolvExpr/CandidateFinder.cpp

    r4487667 rf52ce6e  
    2727#include "Cost.h"
    2828#include "ExplodedArg.hpp"
     29#include "RenameVars.h"           // for renameTyVars
    2930#include "Resolver.h"
    3031#include "ResolveTypeof.h"
     
    557558
    558559        /// Generate a cast expression from `arg` to `toType`
    559         const ast::Expr * restructureCast( const ast::Expr * arg, const ast::Type * toType, bool isGenerated ) {
    560                 #warning unimplemented
    561                 (void)arg; (void)toType; (void)isGenerated;
    562                 assert(false);
    563                 return nullptr;
     560        const ast::Expr * restructureCast(
     561                ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated
     562        ) {
     563                if (
     564                        arg->result->size() > 1
     565                        && ! toType->isVoid()
     566                        && ! dynamic_cast< const ast::ReferenceType * >( toType )
     567                ) {
     568                        // Argument is a tuple and the target type is neither void nor a reference. Cast each
     569                        // member of the tuple to its corresponding target type, producing the tuple of those
     570                        // cast expressions. If there are more components of the tuple than components in the
     571                        // target type, then excess components do not come out in the result expression (but
     572                        // UniqueExpr ensures that the side effects will still be produced)
     573                        if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
     574                                // expressions which may contain side effects require a single unique instance of
     575                                // the expression
     576                                arg = new ast::UniqueExpr{ arg->location, arg };
     577                        }
     578                        std::vector< ast::ptr< ast::Expr > > components;
     579                        for ( unsigned i = 0; i < toType->size(); ++i ) {
     580                                // cast each component
     581                                ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };
     582                                components.emplace_back(
     583                                        restructureCast( idx, toType->getComponent( i ), isGenerated ) );
     584                        }
     585                        return new ast::TupleExpr{ arg->location, move( components ) };
     586                } else {
     587                        // handle normally
     588                        return new ast::CastExpr{ arg->location, arg, toType, isGenerated };
     589                }
     590        }
     591
     592        /// Gets the name from an untyped member expression (must be NameExpr)
     593        const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {
     594                if ( memberExpr->member.as< ast::ConstantExpr >() ) {
     595                        SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );
     596                }
     597
     598                return memberExpr->member.strict_as< ast::NameExpr >()->name;
    564599        }
    565600
     
    764799
    765800                        if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
    766                                 addAggMembers( structInst, aggrExpr, cand, Cost::safe, "" );
     801                                addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );
    767802                        } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
    768                                 addAggMembers( unionInst, aggrExpr, cand, Cost::safe, "" );
     803                                addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );
    769804                        }
    770805                }
     
    773808                void addAggMembers(
    774809                        const ast::ReferenceToType * aggrInst, const ast::Expr * expr,
    775                         const CandidateRef & cand, const Cost & addedCost, const std::string & name
     810                        const Candidate & cand, const Cost & addedCost, const std::string & name
    776811                ) {
    777812                        for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
    778813                                auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
    779814                                CandidateRef newCand = std::make_shared<Candidate>(
    780                                         *cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
     815                                        cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
    781816                                // add anonymous member interpretations whenever an aggregate value type is seen
    782817                                // as a member expression
    783818                                addAnonConversions( newCand );
    784819                                candidates.emplace_back( move( newCand ) );
     820                        }
     821                }
     822
     823                /// Adds tuple member interpretations
     824                void addTupleMembers(
     825                        const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
     826                        const Cost & addedCost, const ast::Expr * member
     827                ) {
     828                        if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {
     829                                // get the value of the constant expression as an int, must be between 0 and the
     830                                // length of the tuple to have meaning
     831                                long long val = constantExpr->intValue();
     832                                if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
     833                                        addCandidate(
     834                                                cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },
     835                                                addedCost );
     836                                }
    785837                        }
    786838                }
     
    10001052                        }
    10011053
    1002                         // castExpr->result should be replaced with toType
    1003                         // candidates => matches
    1004 
    1005                         #warning unimplemented
    1006                         (void)castExpr;
    1007                         assert(false);
     1054                        // select first on argument cost, then conversion cost
     1055                        CandidateList minArgCost = findMinCost( matches );
     1056                        promoteCvtCost( minArgCost );
     1057                        candidates = findMinCost( minArgCost );
    10081058                }
    10091059
     
    10211071
    10221072                void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
    1023                         #warning unimplemented
    1024                         (void)memberExpr;
    1025                         assert(false);
     1073                        CandidateFinder aggFinder{ symtab, tenv };
     1074                        aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );
     1075                        for ( CandidateRef & agg : aggFinder.candidates ) {
     1076                                // it's okay for the aggregate expression to have reference type -- cast it to the
     1077                                // base type to treat the aggregate as the referenced value
     1078                                Cost addedCost = Cost::zero;
     1079                                agg->expr = referenceToRvalueConversion( agg->expr, addedCost );
     1080
     1081                                // find member of the given type
     1082                                if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {
     1083                                        addAggMembers(
     1084                                                structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
     1085                                } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {
     1086                                        addAggMembers(
     1087                                                unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
     1088                                } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {
     1089                                        addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );
     1090                                }
     1091                        }
    10261092                }
    10271093
     
    10301096                }
    10311097
    1032                 void postvisit( const ast::NameExpr * variableExpr ) {
    1033                         #warning unimplemented
    1034                         (void)variableExpr;
    1035                         assert(false);
     1098                void postvisit( const ast::NameExpr * nameExpr ) {
     1099                        std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name );
     1100                        PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
     1101                        for ( auto & data : declList ) {
     1102                                Cost cost = Cost::zero;
     1103                                ast::Expr * newExpr = data.combine( nameExpr->location, cost );
     1104
     1105                                CandidateRef newCand = std::make_shared<Candidate>(
     1106                                        newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero,
     1107                                        cost );
     1108                                PRINT(
     1109                                        std::cerr << "decl is ";
     1110                                        ast::print( std::cerr, data.id );
     1111                                        std::cerr << std::endl;
     1112                                        std::cerr << "newExpr is ";
     1113                                        ast::print( std::cerr, newExpr );
     1114                                        std::cerr << std::endl;
     1115                                )
     1116                                newCand->expr = ast::mutate_field(
     1117                                        newCand->expr.get(), &ast::Expr::result,
     1118                                        renameTyVars( newCand->expr->result ) );
     1119                                // add anonymous member interpretations whenever an aggregate value type is seen
     1120                                // as a name expression
     1121                                addAnonConversions( newCand );
     1122                                candidates.emplace_back( move( newCand ) );
     1123                        }
    10361124                }
    10371125
     
    10481136
    10491137                void postvisit( const ast::SizeofExpr * sizeofExpr ) {
    1050                         #warning unimplemented
    1051                         (void)sizeofExpr;
    1052                         assert(false);
     1138                        if ( sizeofExpr->type ) {
     1139                                addCandidate(
     1140                                        new ast::SizeofExpr{
     1141                                                sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) },
     1142                                        tenv );
     1143                        } else {
     1144                                // find all candidates for the argument to sizeof
     1145                                CandidateFinder finder{ symtab, tenv };
     1146                                finder.find( sizeofExpr->expr );
     1147                                // find the lowest-cost candidate, otherwise ambiguous
     1148                                CandidateList winners = findMinCost( finder.candidates );
     1149                                if ( winners.size() != 1 ) {
     1150                                        SemanticError(
     1151                                                sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );
     1152                                }
     1153                                // return the lowest-cost candidate
     1154                                CandidateRef & choice = winners.front();
     1155                                choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
     1156                                choice->cost = Cost::zero;
     1157                                addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );
     1158                        }
    10531159                }
    10541160
    10551161                void postvisit( const ast::AlignofExpr * alignofExpr ) {
    1056                         #warning unimplemented
    1057                         (void)alignofExpr;
    1058                         assert(false);
     1162                        if ( alignofExpr->type ) {
     1163                                addCandidate(
     1164                                        new ast::AlignofExpr{
     1165                                                alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) },
     1166                                        tenv );
     1167                        } else {
     1168                                // find all candidates for the argument to alignof
     1169                                CandidateFinder finder{ symtab, tenv };
     1170                                finder.find( alignofExpr->expr );
     1171                                // find the lowest-cost candidate, otherwise ambiguous
     1172                                CandidateList winners = findMinCost( finder.candidates );
     1173                                if ( winners.size() != 1 ) {
     1174                                        SemanticError(
     1175                                                alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );
     1176                                }
     1177                                // return the lowest-cost candidate
     1178                                CandidateRef & choice = winners.front();
     1179                                choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
     1180                                choice->cost = Cost::zero;
     1181                                addCandidate(
     1182                                        *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );
     1183                        }
    10591184                }
    10601185
    10611186                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
    1062                         #warning unimplemented
    1063                         (void)offsetofExpr;
    1064                         assert(false);
     1187                        const ast::ReferenceToType * aggInst;
     1188                        if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;
     1189                        else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;
     1190                        else return;
     1191
     1192                        for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {
     1193                                auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );
     1194                                addCandidate(
     1195                                        new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );
     1196                        }
    10651197                }
    10661198
     
    11391271                                                                common )
    11401272                                                ) {
    1141                                                         #warning unimplemented
    1142                                                         assert(false);
     1273                                                        // generate typed expression
     1274                                                        ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{
     1275                                                                conditionalExpr->location, r1->expr, r2->expr, r3->expr };
     1276                                                        newExpr->result = common ? common : r2->expr->result;
     1277                                                        // convert both options to result type
     1278                                                        Cost cost = r1->cost + r2->cost + r3->cost;
     1279                                                        newExpr->arg2 = computeExpressionConversionCost(
     1280                                                                newExpr->arg2, newExpr->result, symtab, env, cost );
     1281                                                        newExpr->arg3 = computeExpressionConversionCost(
     1282                                                                newExpr->arg3, newExpr->result, symtab, env, cost );
     1283                                                        // output candidate
     1284                                                        CandidateRef newCand = std::make_shared<Candidate>(
     1285                                                                newExpr, move( env ), move( open ), move( need ), cost );
     1286                                                        inferParameters( newCand, candidates );
    11431287                                                }
    11441288                                        }
     
    11981342                                                        common )
    11991343                                        ) {
     1344                                                // generate new expression
    12001345                                                ast::RangeExpr * newExpr =
    12011346                                                        new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
    12021347                                                newExpr->result = common ? common : r1->expr->result;
    1203                                                
    1204                                                 #warning unimplemented
    1205                                                 assert(false);
     1348                                                // add candidate
     1349                                                CandidateRef newCand = std::make_shared<Candidate>(
     1350                                                        newExpr, move( env ), move( open ), move( need ),
     1351                                                        r1->cost + r2->cost );
     1352                                                inferParameters( newCand, candidates );
    12061353                                        }
    12071354                                }
  • src/ResolvExpr/RenameVars.cc

    r4487667 rf52ce6e  
    9696                }
    9797        } // namespace
     98
     99        const ast::Type * renameTyVars( const ast::Type * t ) {
     100                #warning unimplemented; make sure resetTyVarRenaming() updated when implemented
     101                (void)t;
     102                assert(false);
     103                return t;
     104        }
    98105} // namespace ResolvExpr
    99106
  • src/ResolvExpr/RenameVars.h

    r4487667 rf52ce6e  
    2323#include "SynTree/Visitor.h"  // for Visitor
    2424
     25namespace ast {
     26        class Type;
     27}
     28
    2529namespace ResolvExpr {
    2630        /// Provides a consistent renaming of forall type names in a hierarchy by prefixing them with a unique "level" ID
    2731        void renameTyVars( Type * );
     32        const ast::Type * renameTyVars( const ast::Type * );
    2833
    2934        /// resets internal state of renamer to avoid overflow
  • src/ResolvExpr/ResolveAssertions.cc

    r4487667 rf52ce6e  
    186186        using InferCache = std::unordered_map< UniqueId, InferredParams >;
    187187
     188        /// Lexicographically-ordered vector of costs
     189        using CostVec = std::vector< Cost >;
     190
     191        int compare( const CostVec & a, const CostVec & b ) {
     192                unsigned i = 0;
     193                do {
     194                        // lex-compare where shorter one is less
     195                        if ( i == a.size() ) {
     196                                return i == b.size() ? 0 : -1;
     197                        }
     198                        if ( i == b.size() /* && i < a.size() */ ) return 1;
     199                       
     200                        int c = a[i].compare( b[i] );
     201                        if ( c != 0 ) return c;
     202                } while ( ++i );
     203                assert(!"unreachable");
     204        }
     205
     206        bool operator< ( const CostVec & a, const CostVec & b ) { return compare( a, b ) < 0; }
     207
    188208        /// Flag for state iteration
    189209        enum IterateFlag { IterateState };
     
    196216                DeferList deferred;        ///< Deferred matches
    197217                InferCache inferred;       ///< Cache of already-inferred parameters
     218                CostVec costs;             ///< Costs of recursive assertion satisfaction for disambiguation
    198219                SymTab::Indexer& indexer;  ///< Name lookup (depends on previous assertions)
    199220
    200221                /// Initial resolution state for an alternative
    201222                ResnState( Alternative& a, SymTab::Indexer& indexer )
    202                 : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
     223                : alt(a), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero }, indexer(indexer) {
    203224                        need.swap( a.need );
    204225                }
     
    207228                ResnState( ResnState&& o, IterateFlag )
    208229                : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(),
    209                   inferred(std::move(o.inferred)), indexer(o.indexer) {}
     230                  inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) {
     231                        costs.emplace_back( Cost::zero );
     232                }
    210233        };
    211234
     
    336359        };
    337360
    338         void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
    339                 PassVisitor<InferMatcher> matcher{ inferred };
    340                 alt.expr = alt.expr->acceptMutator( matcher );
    341                 out.emplace_back( alt );
     361        /// Map of alternative return types to recursive assertion satisfaction costs
     362        using PruneMap = std::unordered_map<std::string, CostVec>;
     363
     364        /// Gets the pruning key for an alternative
     365        std::string pruneKey( const Alternative & alt ) {
     366                Type* resType = alt.expr->result->clone();
     367                alt.env.apply( resType );
     368                std::string resKey = SymTab::Mangler::mangleType( resType );
     369                delete resType;
     370                return std::move( resKey );
     371        }
     372       
     373        /// Replace resnSlots with inferParams and add alternative to output list, if meets pruning
     374        /// threshold.
     375        void finalizeAssertions( ResnState& resn, PruneMap & pruneThresholds, AltList& out ) {
     376                // prune if cheaper alternative for same key has already been generated
     377                std::string resKey = pruneKey( resn.alt );
     378                auto it = pruneThresholds.find( resKey );
     379                if ( it != pruneThresholds.end() ) {
     380                        if ( it->second < resn.costs ) return;
     381                } else {
     382                        pruneThresholds.emplace_hint( it, resKey, resn.costs );
     383                }
     384
     385                // replace resolution slots with inferred params, add to output
     386                PassVisitor<InferMatcher> matcher{ resn.inferred };
     387                resn.alt.expr = resn.alt.expr->acceptMutator( matcher );
     388                out.emplace_back( resn.alt );
    342389        }
    343390
     
    359406                ResnList resns{ ResnState{ alt, root_indexer } };
    360407                ResnList new_resns{};
     408               
     409                // Pruning thresholds by result type of the output alternatives.
     410                // Alternatives *should* be generated in sorted order, so no need to retroactively prune
     411                PruneMap thresholds;
    361412
    362413                // resolve assertions in breadth-first-order up to a limited number of levels deep
     
    364415                        // scan over all mutually-compatible resolutions
    365416                        for ( auto& resn : resns ) {
     417                                // stop this branch if already found a better option
     418                                auto it = thresholds.find( pruneKey( resn.alt ) );
     419                                if ( it != thresholds.end() && it->second < resn.costs ) goto nextResn;
     420
    366421                                // make initial pass at matching assertions
    367422                                for ( auto& assn : resn.need ) {
     
    383438                                        // either add successful match or push back next state
    384439                                        if ( resn.newNeed.empty() ) {
    385                                                 finalizeAssertions( resn.alt, resn.inferred, out );
     440                                                finalizeAssertions( resn, thresholds, out );
    386441                                        } else {
    387442                                                new_resns.emplace_back( std::move(resn), IterateState );
     
    420475                                                goto nextResn;
    421476                                        }
    422                                         // sort by cost
     477                                        // sort by cost for overall pruning
    423478                                        CandidateCost coster{ resn.indexer };
    424479                                        std::sort( compatible.begin(), compatible.end(), coster );
    425480
    426                                         // keep map of detected options
    427                                         std::unordered_map<std::string, Cost> found;
    428481                                        for ( auto& compat : compatible ) {
    429                                                 // filter by environment-adjusted result type, keep only cheapest option
    430                                                 Type* resType = alt.expr->result->clone();
    431                                                 compat.env.apply( resType );
    432                                                 // skip if cheaper alternative already processed with same result type
    433                                                 Cost resCost = coster.get( compat );
    434                                                 auto it = found.emplace( SymTab::Mangler::mangleType( resType ), resCost );
    435                                                 delete resType;
    436                                                 if ( it.second == false && it.first->second < resCost ) continue;
    437 
    438                                                 // proceed with resolution step
    439482                                                ResnState new_resn = resn;
    440483
     
    452495                                                new_resn.alt.openVars = std::move(compat.openVars);
    453496
     497                                                // mark cost of this path
     498                                                new_resn.costs.back() += compat.cost;
     499
    454500                                                // either add sucessful match or push back next state
    455501                                                if ( new_resn.newNeed.empty() ) {
    456                                                         finalizeAssertions( new_resn.alt, new_resn.inferred, out );
     502                                                        finalizeAssertions( new_resn, thresholds, out );
    457503                                                } else {
    458504                                                        new_resns.emplace_back( std::move(new_resn), IterateState );
Note: See TracChangeset for help on using the changeset viewer.