Changeset 1dd1bd2

Timestamp:

Oct 3, 2018, 2:22:44 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum

Children:

588c2b0

Parents:

04bdc26

Message:

Add var count and type specialization costs to resolver model

Location:

src

Files:

• Makefile.am (modified) (1 diff)
• Makefile.in (modified) (6 diffs)
• ResolvExpr/AlternativeFinder.cc (modified) (3 diffs)
• ResolvExpr/ConversionCost.cc (modified) (1 diff)
• ResolvExpr/Cost.h (modified) (11 diffs)
• ResolvExpr/SpecCost.cc (added)
• ResolvExpr/module.mk (modified) (1 diff)
• ResolvExpr/typeops.h (modified) (1 diff)

src/Makefile.am

@@ -128 +128 @@
   ResolvExpr/Resolver.cc \
   ResolvExpr/ResolveTypeof.cc \
+  ResolvExpr/SpecCost.cc \
   ResolvExpr/TypeEnvironment.cc \
   ResolvExpr/Unify.cc \

src/Makefile.in

@@ -205 +205 @@
         ResolvExpr/RenameVars.$(OBJEXT) ResolvExpr/Resolver.$(OBJEXT) \
         ResolvExpr/ResolveTypeof.$(OBJEXT) \
+        ResolvExpr/SpecCost.$(OBJEXT) \
         ResolvExpr/TypeEnvironment.$(OBJEXT) \
         ResolvExpr/Unify.$(OBJEXT) SymTab/Autogen.$(OBJEXT) \
@@ -259 +260 @@
         ResolvExpr/TypeEnvironment.$(OBJEXT) \
         ResolvExpr/CurrentObject.$(OBJEXT) \
-        ResolvExpr/ExplodedActual.$(OBJEXT) SymTab/Indexer.$(OBJEXT) \
+        ResolvExpr/ExplodedActual.$(OBJEXT) \
+        ResolvExpr/SpecCost.$(OBJEXT) SymTab/Indexer.$(OBJEXT) \
         SymTab/Mangler.$(OBJEXT) SymTab/ManglerCommon.$(OBJEXT) \
         SymTab/Validate.$(OBJEXT) SymTab/FixFunction.$(OBJEXT) \
@@ -547 +549 @@
         ResolvExpr/Occurs.cc ResolvExpr/TypeEnvironment.cc \
         ResolvExpr/CurrentObject.cc ResolvExpr/ExplodedActual.cc \
-        SymTab/Indexer.cc SymTab/Mangler.cc SymTab/ManglerCommon.cc \
-        SymTab/Validate.cc SymTab/FixFunction.cc SymTab/Autogen.cc \
-        SynTree/Type.cc SynTree/VoidType.cc SynTree/BasicType.cc \
+        ResolvExpr/SpecCost.cc SymTab/Indexer.cc SymTab/Mangler.cc \
+        SymTab/ManglerCommon.cc SymTab/Validate.cc \
+        SymTab/FixFunction.cc SymTab/Autogen.cc SynTree/Type.cc \
+        SynTree/VoidType.cc SynTree/BasicType.cc \
         SynTree/PointerType.cc SynTree/ArrayType.cc \
         SynTree/ReferenceType.cc SynTree/FunctionType.cc \
@@ -656 +659 @@
   ResolvExpr/Resolver.cc \
   ResolvExpr/ResolveTypeof.cc \
+  ResolvExpr/SpecCost.cc \
   ResolvExpr/TypeEnvironment.cc \
   ResolvExpr/Unify.cc \
@@ -908 +912 @@
 ResolvExpr/ResolveTypeof.$(OBJEXT): ResolvExpr/$(am__dirstamp) \
         ResolvExpr/$(DEPDIR)/$(am__dirstamp)
+ResolvExpr/SpecCost.$(OBJEXT): ResolvExpr/$(am__dirstamp) \
+        ResolvExpr/$(DEPDIR)/$(am__dirstamp)
 ResolvExpr/TypeEnvironment.$(OBJEXT): ResolvExpr/$(am__dirstamp) \
         ResolvExpr/$(DEPDIR)/$(am__dirstamp)
@@ -1160 +1166 @@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/ResolveTypeof.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/Resolver.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/SpecCost.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/TypeEnvironment.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/Unify.Po@am__quote@

src/ResolvExpr/AlternativeFinder.cc

@@ -410 +410 @@
         Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
                 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
-                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
-                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
+                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->function->result );
+                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->base );
 
                 Cost convCost = Cost::zero;
-                std::list< DeclarationWithType* >& formals = function->get_parameters();
+                std::list< DeclarationWithType* >& formals = function->parameters;
                 std::list< DeclarationWithType* >::iterator formal = formals.begin();
-                std::list< Expression* >& actuals = appExpr->get_args();
-
-                for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
-                        Type * actualType = (*actualExpr)->get_result();
+                std::list< Expression* >& actuals = appExpr->args;
+
+                for ( Expression*& actualExpr : actuals ) {
+                        Type * actualType = actualExpr->result;
                         PRINT(
                                 std::cerr << "actual expression:" << std::endl;
-                                (*actualExpr)->print( std::cerr, 8 );
+                                actualExpr->print( std::cerr, 8 );
                                 std::cerr << "--- results are" << std::endl;
                                 actualType->print( std::cerr, 8 );
                         )
                         if ( formal == formals.end() ) {
-                                if ( function->get_isVarArgs() ) {
+                                if ( function->isVarArgs ) {
                                         convCost.incUnsafe();
                                         PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
                                         // convert reference-typed expressions to value-typed expressions
-                                        referenceToRvalueConversion( *actualExpr, convCost );
+                                        referenceToRvalueConversion( actualExpr, convCost );
                                         continue;
                                 } else {
@@ -437 +437 @@
                                 }
                         }
-                        if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( *actualExpr ) ) {
+                        if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( actualExpr ) ) {
                                 // default arguments should be free - don't include conversion cost.
                                 // Unwrap them here because they are not relevant to the rest of the system.
-                                *actualExpr = def->expr;
+                                actualExpr = def->expr;
                                 ++formal;
                                 continue;
                         }
+                        // mark conversion cost to formal and also specialization cost of formal type
                         Type * formalType = (*formal)->get_type();
-                        convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
+                        convCost += computeExpressionConversionCost( actualExpr, formalType, indexer, alt.env );
+                        convCost.decSpec( specCost( formalType ) );
                         ++formal; // can't be in for-loop update because of the continue
                 }
@@ -452 +454 @@
                 }
 
+                // mark specialization cost of return types
+                for ( DeclarationWithType* returnVal : function->returnVals ) {
+                        convCost.decSpec( specCost( returnVal->get_type() ) );
+                }
+
+                // mark type variable and specialization cost of forall clause
+                convCost.incVar( function->forall.size() );
+                for ( TypeDecl* td : function->forall ) {
+                        convCost.decSpec( td->assertions.size() );
+                }
+
+                // xxx -- replace with new costs in resolver
                 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
                         convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );

src/ResolvExpr/ConversionCost.cc

@@ -28 +28 @@
 
 namespace ResolvExpr {
-        const Cost Cost::zero =      Cost(  0,  0,  0,  0 );
-        const Cost Cost::infinity =  Cost( -1, -1, -1, -1 );
-        const Cost Cost::unsafe =    Cost(  1,  0,  0,  0 );
-        const Cost Cost::poly =      Cost(  0,  1,  0,  0 );
-        const Cost Cost::safe =      Cost(  0,  0,  1,  0 );
-        const Cost Cost::reference = Cost(  0,  0,  0,  1 );
+        const Cost Cost::zero =      Cost{  0,  0,  0,  0,  0,  0 };
+        const Cost Cost::infinity =  Cost{ -1, -1, -1,  1, -1, -1 };
+        const Cost Cost::unsafe =    Cost{  1,  0,  0,  0,  0,  0 };
+        const Cost Cost::poly =      Cost{  0,  1,  0,  0,  0,  0 };
+        const Cost Cost::var =       Cost{  0,  0,  1,  0,  0,  0 };
+        const Cost Cost::spec =      Cost{  0,  0,  0, -1,  0,  0 };
+        const Cost Cost::safe =      Cost{  0,  0,  0,  0,  1,  0 };
+        const Cost Cost::reference = Cost{  0,  0,  0,  0,  0,  1 };
 
 #if 0

src/ResolvExpr/Cost.h

@@ -9 +9 @@
 // Author           : Richard C. Bilson
 // Created On       : Sun May 17 09:39:50 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:35:55 2017
-// Update Count     : 5
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Tue Oct 02 14:40:00 2018
+// Update Count     : 6
 //
 
@@ -21 +21 @@
         class Cost {
           private:
-                Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost );
+                Cost( int unsafeCost, int polyCost, int varCost, int specCost, int safeCost, 
+                      int referenceCost );
 
           public:
                 Cost & incUnsafe( int inc = 1 );
                 Cost & incPoly( int inc = 1 );
+                Cost & incVar( int inc = 1 );
+                Cost & decSpec( int inc = 1 );
                 Cost & incSafe( int inc = 1 );
                 Cost & incReference( int inc = 1 );
@@ -31 +34 @@
                 int get_unsafeCost() const { return unsafeCost; }
                 int get_polyCost() const { return polyCost; }
+                int get_varCost() const { return varCost; }
+                int get_specCost() const { return specCost; }
                 int get_safeCost() const { return safeCost; }
                 int get_referenceCost() const { return referenceCost; }
@@ -47 +52 @@
                 static const Cost unsafe;
                 static const Cost poly;
+                static const Cost var;
+                static const Cost spec;
                 static const Cost safe;
                 static const Cost reference;
@@ -52 +59 @@
                 int compare( const Cost &other ) const;
 
-                int unsafeCost;
-                int polyCost;
-                int safeCost;
-                int referenceCost;
+                int unsafeCost;     ///< Unsafe (narrowing) conversions
+                int polyCost;       ///< Count of parameters and return values bound to some poly type
+                int varCost;        ///< Count of polymorphic type variables
+                int specCost;       ///< Polymorphic type specializations (type assertions), negative cost
+                int safeCost;       ///< Safe (widening) conversions
+                int referenceCost;  ///< reference conversions
         };
 
-        inline Cost::Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost ) : unsafeCost( unsafeCost ), polyCost( polyCost ), safeCost( safeCost ), referenceCost( referenceCost ) {}
+        inline Cost::Cost( int unsafeCost, int polyCost, int varCost, int specCost, int safeCost, 
+                        int referenceCost ) 
+                : unsafeCost( unsafeCost ), polyCost( polyCost ), varCost( varCost ), specCost( specCost ), 
+                  safeCost( safeCost ), referenceCost( referenceCost ) {}
 
         inline Cost & Cost::incUnsafe( int inc ) {
@@ -69 +81 @@
                 if ( *this == infinity ) return *this;
                 polyCost += inc;
+                return *this;
+        }
+
+        inline Cost & Cost::incVar( int inc ) {
+                if ( *this == infinity ) return *this;
+                varCost += inc;
+                return *this;
+        }
+
+        inline Cost& Cost::decSpec( int dec ) {
+                if ( *this == infinity ) return *this;
+                specCost -= dec;
                 return *this;
         }
@@ -86 +110 @@
         inline Cost Cost::operator+( const Cost &other ) const {
                 if ( *this == infinity || other == infinity ) return infinity;
-                return Cost( unsafeCost + other.unsafeCost, polyCost + other.polyCost, safeCost + other.safeCost, referenceCost + other.referenceCost );
+                return Cost{ 
+                        unsafeCost + other.unsafeCost, polyCost + other.polyCost, 
+                        varCost + other.varCost, specCost + other.specCost, 
+                        safeCost + other.safeCost, referenceCost + other.referenceCost };
         }
 
         inline Cost Cost::operator-( const Cost &other ) const {
                 if ( *this == infinity || other == infinity ) return infinity;
-                return Cost( unsafeCost - other.unsafeCost, polyCost - other.polyCost, safeCost - other.safeCost, referenceCost - other.referenceCost );
+                return Cost{ 
+                        unsafeCost - other.unsafeCost, polyCost - other.polyCost, 
+                        varCost - other.varCost, specCost - other.specCost, 
+                        safeCost - other.safeCost, referenceCost - other.referenceCost };
         }
 
@@ -102 +132 @@
                 unsafeCost += other.unsafeCost;
                 polyCost += other.polyCost;
+                varCost += other.varCost;
+                specCost += other.specCost;
                 safeCost += other.safeCost;
                 referenceCost += other.referenceCost;
@@ -119 +151 @@
                 } else if ( polyCost < other.polyCost ) {
                         return true;
+                } else if ( varCost > other.varCost ) {
+                        return false;
+                } else if ( varCost < other.varCost ) {
+                        return true;
+                } else if ( specCost > other.specCost ) {
+                        return false;
+                } else if ( specCost > other.specCost ) {
+                        return true;
                 } else if ( safeCost > other.safeCost ) {
                         return false;
@@ -135 +175 @@
                 return unsafeCost == other.unsafeCost
                         && polyCost == other.polyCost
+                        && varCost == other.varCost
+                        && specCost == other.specCost
                         && safeCost == other.safeCost
                         && referenceCost == other.referenceCost;
@@ -144 +186 @@
 
         inline std::ostream &operator<<( std::ostream &os, const Cost &cost ) {
-                os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", " << cost.safeCost << ", " << cost.referenceCost << " )";
-                return os;
+                return os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", " 
+                          << cost.varCost << ", " << cost.specCost << ", "
+                          << cost.safeCost << ", " << cost.referenceCost << " )";
         }
 } // namespace ResolvExpr

src/ResolvExpr/module.mk

@@ -33 +33 @@
        ResolvExpr/TypeEnvironment.cc \
        ResolvExpr/CurrentObject.cc \
-       ResolvExpr/ExplodedActual.cc
+       ResolvExpr/ExplodedActual.cc \
+       ResolvExpr/SpecCost.cc

src/ResolvExpr/typeops.h

@@ -102 +102 @@
         int polyCost( Type *type, const TypeEnvironment &env, const SymTab::Indexer &indexer );
 
+        // in SpecCost.cc
+        int specCost( Type *type );
+
         // in Occurs.cc
         bool occurs( Type *type, std::string varName, const TypeEnvironment &env );