Changeset fbecee5

Timestamp:

Oct 18, 2018, 4:26:11 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:

2fd9f24

Parents:

2c187378

Message:

rational.cfa passes deferred resolution pass now

Location:

src

Files:

• Common/utility.h (modified) (2 diffs)
• ResolvExpr/AlternativeFinder.cc (modified) (1 diff)
• ResolvExpr/ResolveAssertions.cc (modified) (4 diffs)
• ResolvExpr/typeops.h (modified) (1 diff)

src/Common/utility.h

@@ -26 +26 @@
 #include <string>
 #include <type_traits>
+#include <utility>
 
 #include <cassert>
@@ -462 +463 @@
 std::pair<long long int, bool> eval(Expression * expr);
 
+// -----------------------------------------------------------------------------
+/// Reorders the input range in-place so that the minimal-value elements according to the 
+/// comparator are in front; 
+/// returns the iterator after the last minimal-value element.
+template<typename Iter, typename Compare>
+Iter sort_mins( Iter begin, Iter end, Compare& lt ) {
+        if ( begin == end ) return end;
+        
+        Iter min_pos = begin;
+        for ( Iter i = begin + 1; i != end; ++i ) {
+                if ( lt( *i, *min_pos ) ) {
+                        // new minimum cost; swap into first position
+                        min_pos = begin;
+                        std::iter_swap( min_pos, i );
+                } else if ( ! lt( *min_pos, *i ) ) {
+                        // duplicate minimum cost; swap into next minimum position
+                        ++min_pos;
+                        std::iter_swap( min_pos, i );
+                }
+        }
+        return ++min_pos;
+}
+
+template<typename Iter, typename Compare>
+inline Iter sort_mins( Iter begin, Iter end, Compare&& lt ) {
+        return sort_mins( begin, end, lt );
+}
+
+/// sort_mins defaulted to use std::less
+template<typename Iter>
+inline Iter sort_mins( Iter begin, Iter end ) {
+        return sort_mins( begin, end, std::less<typename std::iterator_traits<Iter>::value_type>{} );
+}
+
 // Local Variables: //
 // tab-width: 4 //

src/ResolvExpr/AlternativeFinder.cc

@@ -254 +254 @@
                         SemanticError( expr, "No reasonable alternatives for expression " );
                 }
-                if ( mode.resolveAssns ) {
+                if ( mode.resolveAssns || mode.prune ) {
                         // trim candidates just to those where the assertions resolve
+                        // - necessary pre-requisite to pruning
                         AltList candidates;
                         for ( unsigned i = 0; i < alternatives.size(); ++i ) {

src/ResolvExpr/ResolveAssertions.cc

@@ -18 +18 @@
 #include <cassert>                // for assertf
 #include <list>                   // for list
+#include <unordered_map>          // for unordered_map
 #include <utility>                // for move
 #include <vector>                 // for vector
@@ -23 +24 @@
 #include "Alternative.h"          // for Alternative, AssertionItem
 #include "Common/FilterCombos.h"  // for filterCombos
+#include "Common/utility.h"       // for sort_mins
 #include "SymTab/Indexer.h"       // for Indexer
 #include "TypeEnvironment.h"      // for TypeEnvironment, etc.
@@ -125 +127 @@
         };
 
+        /// Comparator for CandidateEnvMerger outputs that sums their costs and caches the stored 
+        /// sums
+        struct CandidateCost {
+                using Element = CandidateEnvMerger::OutType;
+        private:
+                using Memo = std::unordered_map<const Element*, Cost>;
+                mutable Memo cache;              ///< cache of element costs
+                const SymTab::Indexer& indexer;  ///< Indexer for costing
+
+        public:
+                CandidateCost( const SymTab::Indexer& indexer ) : indexer(indexer) {}
+
+                /// reports the cost of an element
+                Cost get( const Element& x ) const {
+                        Memo::const_iterator it = cache.find( &x );
+                        if ( it == cache.end() ) {
+                                Cost k = Cost::zero;
+                                for ( const auto& assn : x.assns ) {
+                                        k += computeConversionCost( 
+                                                assn.match.adjType, assn.decl->get_type(), indexer, x.env );
+                                }
+                                it = cache.emplace_hint( it, &x, k );
+                        }
+                        return it->second;
+                }
+                
+                /// compares elements by cost
+                bool operator() ( const Element& a, const Element& b ) const {
+                        return get( a ) < get( b );
+                }
+        };
+
         /// Flag for state iteration
         enum IterateFlag { IterateState };
@@ -275 +309 @@
                                         }
                                 } else {
-                                        // resolve deferred assertions by mutual compatibility
+                                        // resolve deferred assertions by mutual compatibility and sort by cost
                                         std::vector<CandidateEnvMerger::OutType> compatible = filterCombos(
                                                 resn.deferred, 
                                                 CandidateEnvMerger{ resn.alt.env, resn.alt.openVars, resn.indexer } );
+                                        auto lmin = sort_mins( compatible.begin(), compatible.end(), 
+                                                CandidateCost{resn.indexer} );
                                         
-                                        for ( auto& compat : compatible ) {
+                                        // for ( auto& compat : compatible ) {
+                                        for ( auto it = compatible.begin(); it != lmin ; ++it ) {
+                                                auto& compat = *it;
                                                 ResnState new_resn = resn;
 

src/ResolvExpr/typeops.h

@@ -72 +72 @@
         Cost conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env );
 
+        // in AlternativeFinder.cc
+        Cost computeConversionCost( Type *actualType, Type *formalType, 
+                const SymTab::Indexer &indexer, const TypeEnvironment &env );
+
         // in PtrsAssignable.cc
         int ptrsAssignable( Type *src, Type *dest, const TypeEnvironment &env );