source: src/GenPoly/Specialize.cc @ 626dbc10

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 626dbc10 was 626dbc10, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

major refactoring of specialization code, added code to generate thunks for ttype functions, move specialize pass to before tuple expansion

  • Property mode set to 100644
File size: 14.7 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// Specialize.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Mon May 18 07:44:20 2015
11// Last Modified By : Rob Schluntz
12// Last Modified On : Thu Apr 28 15:17:45 2016
13// Update Count     : 24
14//
15
16#include <cassert>
17
18#include "Specialize.h"
19#include "GenPoly.h"
20#include "PolyMutator.h"
21
22#include "Parser/ParseNode.h"
23
24#include "SynTree/Expression.h"
25#include "SynTree/Statement.h"
26#include "SynTree/Type.h"
27#include "SynTree/Attribute.h"
28#include "SynTree/TypeSubstitution.h"
29#include "SynTree/Mutator.h"
30#include "ResolvExpr/FindOpenVars.h"
31#include "Common/UniqueName.h"
32#include "Common/utility.h"
33#include "InitTweak/InitTweak.h"
34
35namespace GenPoly {
36        class Specializer;
37        class Specialize final : public PolyMutator {
38                friend class Specializer;
39          public:
40                using PolyMutator::mutate;
41                virtual Expression * mutate( ApplicationExpr *applicationExpr ) override;
42                virtual Expression * mutate( AddressExpr *castExpr ) override;
43                virtual Expression * mutate( CastExpr *castExpr ) override;
44                // virtual Expression * mutate( LogicalExpr *logicalExpr );
45                // virtual Expression * mutate( ConditionalExpr *conditionalExpr );
46                // virtual Expression * mutate( CommaExpr *commaExpr );
47
48                Specializer * specializer = nullptr;
49                void handleExplicitParams( ApplicationExpr *appExpr );
50        };
51
52        class Specializer {
53          public:
54                Specializer( Specialize & spec ) : spec( spec ), env( spec.env ), stmtsToAdd( spec.stmtsToAdd ) {}
55                virtual bool needsSpecialization( Type * formalType, Type * actualType, TypeSubstitution * env ) = 0;
56                virtual Expression *createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) = 0;
57                virtual Expression *doSpecialization( Type *formalType, Expression *actual, InferredParams *inferParams = 0 );
58
59          protected:
60                Specialize & spec;
61                std::string paramPrefix = "_p";
62                TypeSubstitution *& env;
63                std::list< Statement * > & stmtsToAdd;
64        };
65
66        // for normal polymorphic -> monomorphic function conversion
67        class PolySpecializer : public Specializer {
68          public:
69                PolySpecializer( Specialize & spec ) : Specializer( spec ) {}
70                virtual bool needsSpecialization( Type * formalType, Type * actualType, TypeSubstitution * env ) override;
71                virtual Expression *createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) override;
72        };
73
74        // // for tuple -> non-tuple function conversion
75        class TupleSpecializer : public Specializer {
76          public:
77                TupleSpecializer( Specialize & spec ) : Specializer( spec ) {}
78                virtual bool needsSpecialization( Type * formalType, Type * actualType, TypeSubstitution * env ) override;
79                virtual Expression *createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) override;
80        };
81
82        /// Looks up open variables in actual type, returning true if any of them are bound in the environment or formal type.
83        bool PolySpecializer::needsSpecialization( Type *formalType, Type *actualType, TypeSubstitution *env ) {
84                if ( env ) {
85                        using namespace ResolvExpr;
86                        OpenVarSet openVars, closedVars;
87                        AssertionSet need, have;
88                        findOpenVars( formalType, openVars, closedVars, need, have, false );
89                        findOpenVars( actualType, openVars, closedVars, need, have, true );
90                        for ( OpenVarSet::const_iterator openVar = openVars.begin(); openVar != openVars.end(); ++openVar ) {
91                                Type *boundType = env->lookup( openVar->first );
92                                if ( ! boundType ) continue;
93                                if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( boundType ) ) {
94                                        if ( closedVars.find( typeInst->get_name() ) == closedVars.end() ) {
95                                                return true;
96                                        } // if
97                                } else {
98                                        return true;
99                                } // if
100                        } // for
101                        return false;
102                } else {
103                        return false;
104                } // if
105        }
106
107        /// Generates a thunk that calls `actual` with type `funType` and returns its address
108        Expression * PolySpecializer::createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) {
109                static UniqueName thunkNamer( "_thunk" );
110
111                FunctionType *newType = funType->clone();
112                if ( env ) {
113                        TypeSubstitution newEnv( *env );
114                        // it is important to replace only occurrences of type variables that occur free in the
115                        // thunk's type
116                        newEnv.applyFree( newType );
117                } // if
118                // create new thunk with same signature as formal type (C linkage, empty body)
119                FunctionDecl *thunkFunc = new FunctionDecl( thunkNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, newType, new CompoundStmt( noLabels ), false, false );
120                thunkFunc->fixUniqueId();
121
122                // thunks may be generated and not used - silence warning with attribute
123                thunkFunc->get_attributes().push_back( new Attribute( "unused" ) );
124
125                // thread thunk parameters into call to actual function, naming thunk parameters as we go
126                UniqueName paramNamer( paramPrefix );
127                ApplicationExpr *appExpr = new ApplicationExpr( actual );
128                for ( std::list< DeclarationWithType* >::iterator param = thunkFunc->get_functionType()->get_parameters().begin(); param != thunkFunc->get_functionType()->get_parameters().end(); ++param ) {
129                        (*param )->set_name( paramNamer.newName() );
130                        appExpr->get_args().push_back( new VariableExpr( *param ) );
131                } // for
132                appExpr->set_env( maybeClone( env ) );
133                if ( inferParams ) {
134                        appExpr->get_inferParams() = *inferParams;
135                } // if
136
137                // handle any specializations that may still be present
138                std::string oldParamPrefix = paramPrefix;
139                paramPrefix += "p";
140                // save stmtsToAdd in oldStmts
141                std::list< Statement* > oldStmts;
142                oldStmts.splice( oldStmts.end(), stmtsToAdd );
143                spec.handleExplicitParams( appExpr );
144                paramPrefix = oldParamPrefix;
145                // write any statements added for recursive specializations into the thunk body
146                thunkFunc->get_statements()->get_kids().splice( thunkFunc->get_statements()->get_kids().end(), stmtsToAdd );
147                // restore oldStmts into stmtsToAdd
148                stmtsToAdd.splice( stmtsToAdd.end(), oldStmts );
149
150                // add return (or valueless expression) to the thunk
151                Statement *appStmt;
152                if ( funType->get_returnVals().empty() ) {
153                        appStmt = new ExprStmt( noLabels, appExpr );
154                } else {
155                        appStmt = new ReturnStmt( noLabels, appExpr );
156                } // if
157                thunkFunc->get_statements()->get_kids().push_back( appStmt );
158
159                // add thunk definition to queue of statements to add
160                stmtsToAdd.push_back( new DeclStmt( noLabels, thunkFunc ) );
161                // return address of thunk function as replacement expression
162                return new AddressExpr( new VariableExpr( thunkFunc ) );
163        }
164
165        Expression * Specializer::doSpecialization( Type *formalType, Expression *actual, InferredParams *inferParams ) {
166                assertf( actual->has_result(), "attempting to specialize an untyped expression" );
167                if ( needsSpecialization( formalType, actual->get_result(), env ) ) {
168                        FunctionType *funType;
169                        if ( ( funType = getFunctionType( formalType ) ) ) {
170                                ApplicationExpr *appExpr;
171                                VariableExpr *varExpr;
172                                if ( ( appExpr = dynamic_cast<ApplicationExpr*>( actual ) ) ) {
173                                        return createThunkFunction( funType, appExpr->get_function(), inferParams );
174                                } else if ( ( varExpr = dynamic_cast<VariableExpr*>( actual ) ) ) {
175                                        return createThunkFunction( funType, varExpr, inferParams );
176                                } else {
177                                        // This likely won't work, as anything that could build an ApplicationExpr probably hit one of the previous two branches
178                                        return createThunkFunction( funType, actual, inferParams );
179                                }
180                        } else {
181                                return actual;
182                        } // if
183                } else {
184                        return actual;
185                } // if
186        }
187
188        bool TupleSpecializer::needsSpecialization( Type *formalType, Type *actualType, TypeSubstitution *env ) {
189                // std::cerr << "asking if type needs tuple spec: " << formalType << std::endl;
190                if ( FunctionType * ftype = getFunctionType( formalType ) ) {
191                        return ftype->isTtype();
192                }
193                return false;
194        }
195
196        template< typename Iterator >
197        void fixLastArg( std::list< Expression * > & args, Iterator begin, Iterator end ) {
198                assertf( ! args.empty(), "Somehow args to tuple function are empty" ); // xxx - it's quite possible this will trigger for the nullary case...
199                Expression * last = args.back();
200                // safe_dynamic_cast for the assertion
201                safe_dynamic_cast< TupleType * >( last->get_result() ); // xxx - it's quite possible this will trigger for the unary case...
202                args.pop_back(); // replace last argument in the call with
203                unsigned idx = 0;
204                for ( ; begin != end; ++begin ) {
205                        // DeclarationWithType * formal = *begin;
206                        // Type * formalType = formal->get_type();
207                        args.push_back( new TupleIndexExpr( last->clone(), idx++ ) );
208                }
209                delete last;
210        }
211
212        Expression * TupleSpecializer::createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) {
213                static UniqueName thunkNamer( "_tupleThunk" );
214                // std::cerr << "creating tuple thunk for " << funType << std::endl;
215
216                FunctionType *newType = funType->clone();
217                if ( env ) {
218                        TypeSubstitution newEnv( *env );
219                        // it is important to replace only occurrences of type variables that occur free in the
220                        // thunk's type
221                        newEnv.applyFree( newType );
222                } // if
223                // create new thunk with same signature as formal type (C linkage, empty body)
224                FunctionDecl *thunkFunc = new FunctionDecl( thunkNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, newType, new CompoundStmt( noLabels ), false, false );
225                thunkFunc->fixUniqueId();
226
227                // thunks may be generated and not used - silence warning with attribute
228                thunkFunc->get_attributes().push_back( new Attribute( "unused" ) );
229
230                // thread thunk parameters into call to actual function, naming thunk parameters as we go
231                UniqueName paramNamer( paramPrefix );
232                ApplicationExpr *appExpr = new ApplicationExpr( actual );
233                // std::cerr << actual << std::endl;
234
235                FunctionType * actualType = getFunctionType( actual->get_result() );
236                std::list< DeclarationWithType * >::iterator begin = actualType->get_parameters().begin();
237                std::list< DeclarationWithType * >::iterator end = actualType->get_parameters().end();
238
239                for ( DeclarationWithType* param : thunkFunc->get_functionType()->get_parameters() ) {
240                        ++begin;
241                        assert( begin != end );
242
243                        // std::cerr << "thunk param: " << param << std::endl;
244                        // last param will always be a tuple type... expand it into the actual type(?)
245                        param->set_name( paramNamer.newName() );
246                        appExpr->get_args().push_back( new VariableExpr( param ) );
247                } // for
248                fixLastArg( appExpr->get_args(), --begin, end );
249                appExpr->set_env( maybeClone( env ) );
250                if ( inferParams ) {
251                        appExpr->get_inferParams() = *inferParams;
252                } // if
253
254                // handle any specializations that may still be present
255                std::string oldParamPrefix = paramPrefix;
256                paramPrefix += "p";
257                // save stmtsToAdd in oldStmts
258                std::list< Statement* > oldStmts;
259                oldStmts.splice( oldStmts.end(), stmtsToAdd );
260                spec.handleExplicitParams( appExpr );
261                paramPrefix = oldParamPrefix;
262                // write any statements added for recursive specializations into the thunk body
263                thunkFunc->get_statements()->get_kids().splice( thunkFunc->get_statements()->get_kids().end(), stmtsToAdd );
264                // restore oldStmts into stmtsToAdd
265                stmtsToAdd.splice( stmtsToAdd.end(), oldStmts );
266
267                // add return (or valueless expression) to the thunk
268                Statement *appStmt;
269                if ( funType->get_returnVals().empty() ) {
270                        appStmt = new ExprStmt( noLabels, appExpr );
271                } else {
272                        appStmt = new ReturnStmt( noLabels, appExpr );
273                } // if
274                thunkFunc->get_statements()->get_kids().push_back( appStmt );
275
276                // std::cerr << "thunkFunc is: " << thunkFunc << std::endl;
277
278                // add thunk definition to queue of statements to add
279                stmtsToAdd.push_back( new DeclStmt( noLabels, thunkFunc ) );
280                // return address of thunk function as replacement expression
281                return new AddressExpr( new VariableExpr( thunkFunc ) );
282        }
283
284        void Specialize::handleExplicitParams( ApplicationExpr *appExpr ) {
285                // create thunks for the explicit parameters
286                assert( appExpr->get_function()->has_result() );
287                FunctionType *function = getFunctionType( appExpr->get_function()->get_result() );
288                assert( function );
289                std::list< DeclarationWithType* >::iterator formal;
290                std::list< Expression* >::iterator actual;
291                for ( formal = function->get_parameters().begin(), actual = appExpr->get_args().begin(); formal != function->get_parameters().end() && actual != appExpr->get_args().end(); ++formal, ++actual ) {
292                        *actual = specializer->doSpecialization( (*formal )->get_type(), *actual, &appExpr->get_inferParams() );
293                }
294        }
295
296        Expression * Specialize::mutate( ApplicationExpr *appExpr ) {
297                appExpr->get_function()->acceptMutator( *this );
298                mutateAll( appExpr->get_args(), *this );
299
300                if ( ! InitTweak::isIntrinsicCallExpr( appExpr ) ) {
301                        // create thunks for the inferred parameters
302                        // don't need to do this for intrinsic calls, because they aren't actually passed
303                        for ( InferredParams::iterator inferParam = appExpr->get_inferParams().begin(); inferParam != appExpr->get_inferParams().end(); ++inferParam ) {
304                                inferParam->second.expr = specializer->doSpecialization( inferParam->second.formalType, inferParam->second.expr, &appExpr->get_inferParams() );
305                        }
306                        handleExplicitParams( appExpr );
307                }
308                return appExpr;
309        }
310
311        Expression * Specialize::mutate( AddressExpr *addrExpr ) {
312                addrExpr->get_arg()->acceptMutator( *this );
313                assert( addrExpr->has_result() );
314                addrExpr->set_arg( specializer->doSpecialization( addrExpr->get_result(), addrExpr->get_arg() ) );
315                return addrExpr;
316        }
317
318        Expression * Specialize::mutate( CastExpr *castExpr ) {
319                castExpr->get_arg()->acceptMutator( *this );
320                if ( castExpr->get_result()->isVoid() ) {
321                        // can't specialize if we don't have a return value
322                        return castExpr;
323                }
324                Expression *specialized = specializer->doSpecialization( castExpr->get_result(), castExpr->get_arg() );
325                if ( specialized != castExpr->get_arg() ) {
326                        // assume here that the specialization incorporates the cast
327                        return specialized;
328                } else {
329                        return castExpr;
330                }
331        }
332
333        // Removing these for now. Richard put these in for some reason, but it's not clear why.
334        // In particular, copy constructors produce a comma expression, and with this code the parts
335        // of that comma expression are not specialized, which causes problems.
336
337        // Expression * Specialize::mutate( LogicalExpr *logicalExpr ) {
338        //      return logicalExpr;
339        // }
340
341        // Expression * Specialize::mutate( ConditionalExpr *condExpr ) {
342        //      return condExpr;
343        // }
344
345        // Expression * Specialize::mutate( CommaExpr *commaExpr ) {
346        //      return commaExpr;
347        // }
348
349        void convertSpecializations( std::list< Declaration* >& translationUnit ) {
350                Specialize spec;
351
352                TupleSpecializer tupleSpec( spec );
353                spec.specializer = &tupleSpec;
354                mutateAll( translationUnit, spec );
355
356                PolySpecializer polySpec( spec );
357                spec.specializer = &polySpec;
358                mutateAll( translationUnit, spec );
359        }
360} // namespace GenPoly
361
362// Local Variables: //
363// tab-width: 4 //
364// mode: c++ //
365// compile-command: "make install" //
366// End: //
Note: See TracBrowser for help on using the repository browser.