source: src/GenPoly/Specialize.cc@ 53e3b4a

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 53e3b4a was 626dbc10, checked in by Rob Schluntz <rschlunt@…>, 9 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.