source: src/ResolvExpr/TypeEnvironment.h @ f474e91

arm-ehenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since f474e91 was f474e91, checked in by Aaron Moss <a3moss@…>, 4 years ago

Port unification calculations to new AST

  • Property mode set to 100644
File size: 7.4 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// TypeEnvironment.h --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sun May 17 12:24:58 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Tue Apr 30 23:04:10 2019
13// Update Count     : 9
14//
15
16#pragma once
17
18#include <iostream>                    // for ostream
19#include <list>                        // for list, list<>::iterator, list<>...
20#include <map>                                             // for map, map<>::value_compare
21#include <unordered_map>
22#include <set>                                             // for set
23#include <string>                      // for string
24#include <utility>                     // for move, swap
25
26#include "WidenMode.h"                 // for WidenMode
27
28#include "SynTree/Declaration.h"       // for TypeDecl::Data, DeclarationWit...
29#include "SynTree/SynTree.h"           // for UniqueId
30#include "SynTree/Type.h"              // for Type, Type::ForallList
31#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
32
33namespace ResolvExpr {
34        // adding this comparison operator significantly improves assertion resolution run time for
35        // some cases. The current resolution algorithm's speed partially depends on the order of
36        // assertions. Assertions which have fewer possible matches should appear before
37        // assertions which have more possible matches. This seems to imply that this could
38        // be further improved by providing an indexer as an additional argument and ordering based
39        // on the number of matches of the same kind (object, function) for the names of the
40        // declarations.
41        //
42        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this
43        // comparator.
44        //
45        // Note: since this compares pointers for position, minor changes in the source file that affect
46        // memory layout can alter compilation time in unpredictable ways. For example, the placement
47        // of a line directive can reorder type pointers with respect to each other so that assertions
48        // are seen in different orders, causing a potentially different number of unification calls
49        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering
50        // line directives alone, so it would be nice to fix this comparison so that assertions compare
51        // more consistently. I've tried to modify this to compare on mangle name instead of type as
52        // the second comparator, but this causes some assertions to never be recorded. More
53        // investigation is needed.
54        struct AssertCompare {
55                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
56                        int cmp = d1->get_name().compare( d2->get_name() );
57                        return cmp < 0 ||
58                                ( cmp == 0 && d1->get_type() < d2->get_type() );
59                }
60        };
61        struct AssertionSetValue {
62                bool isUsed;        ///< True if assertion needs to be resolved
63                UniqueId resnSlot;  ///< ID of slot assertion belongs to
64
65                AssertionSetValue() : isUsed(false), resnSlot(0) {}
66        };
67        typedef std::map< DeclarationWithType *, AssertionSetValue, AssertCompare > AssertionSet;
68        typedef std::unordered_map< std::string, TypeDecl::Data > OpenVarSet;
69
70        /// merges one set of open vars into another
71        static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) {
72                for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; }
73        }
74
75        void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
76        void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
77
78        struct EqvClass {
79                std::set< std::string > vars;
80                Type *type;
81                bool allowWidening;
82                TypeDecl::Data data;
83
84                void initialize( const EqvClass &src, EqvClass &dest );
85                void initialize( const EqvClass &src, EqvClass &dest, const Type *ty );
86                EqvClass();
87                EqvClass( const EqvClass &other );
88                EqvClass( const EqvClass &other, const Type *ty );
89                EqvClass( EqvClass &&other );
90                EqvClass &operator=( const EqvClass &other );
91                EqvClass &operator=( EqvClass &&other );
92                ~EqvClass();
93                void print( std::ostream &os, Indenter indent = {} ) const;
94
95                /// Takes ownership of `ty`, freeing old `type`
96                void set_type(Type* ty);
97        };
98
99        class TypeEnvironment {
100                using ClassList = std::list< EqvClass >;
101          public:
102                const EqvClass* lookup( const std::string &var ) const;
103          private:
104                void add( EqvClass &&eqvClass  );
105          public:
106                void add( const Type::ForallList &tyDecls );
107                void add( const TypeSubstitution & sub );
108                template< typename SynTreeClass > int apply( SynTreeClass *&type ) const;
109                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
110                void makeSubstitution( TypeSubstitution &result ) const;
111                bool isEmpty() const { return env.empty(); }
112                void print( std::ostream &os, Indenter indent = {} ) const;
113               
114                /// Simply concatenate the second environment onto this one; no safety checks performed
115                void simpleCombine( const TypeEnvironment &second );
116
117          private:
118                /// Unifies the type bound of to with the type bound of from, returning false if fails
119                bool mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
120
121                /// Merges two type classes from local environment, returning false if fails
122                bool mergeClasses( ClassList::iterator to, ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
123
124          public:
125                /// Merges the second environment with this one, checking compatibility.
126                /// Returns false if fails, but does NOT roll back partial changes.
127                bool combine( const TypeEnvironment& second, OpenVarSet& openVars, const SymTab::Indexer& indexer );
128               
129                void extractOpenVars( OpenVarSet &openVars ) const;
130                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
131
132                /// Iteratively adds the environment of a new actual (with allowWidening = false),
133                /// and extracts open variables.
134                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
135
136                /// Binds the type class represented by `typeInst` to the type `bindTo`; will add
137                /// the class if needed. Returns false on failure.
138                bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
139               
140                /// Binds the type classes represented by `var1` and `var2` together; will add
141                /// one or both classes if needed. Returns false on failure.
142                bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
143
144                /// Disallows widening for all bindings in the environment
145                void forbidWidening();
146
147                using iterator = ClassList::const_iterator;
148                iterator begin() const { return env.begin(); }
149                iterator end() const { return env.end(); }
150
151          private:
152                ClassList env;
153               
154                ClassList::iterator internal_lookup( const std::string &var );
155        };
156
157        template< typename SynTreeClass >
158        int TypeEnvironment::apply( SynTreeClass *&type ) const {
159                TypeSubstitution sub;
160                makeSubstitution( sub );
161                return sub.apply( type );
162        }
163
164        template< typename SynTreeClass >
165        int TypeEnvironment::applyFree( SynTreeClass *&type ) const {
166                TypeSubstitution sub;
167                makeSubstitution( sub );
168                return sub.applyFree( type );
169        }
170
171        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
172} // namespace ResolvExpr
173
174// Local Variables: //
175// tab-width: 4 //
176// mode: c++ //
177// compile-command: "make install" //
178// End: //
Note: See TracBrowser for help on using the repository browser.