source: src/GenPoly/Specialize.cc@ c84e80a

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 c84e80a was 6c3a988f, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

fix inferred parameter data structures to correctly associate parameters with the entity that requested them, modify tuple specialization and unification to work with self-recursive assertions
  • Property mode set to 100644
File size: 15.8 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#include "Tuples/Tuples.h"
35
36namespace GenPoly {
37 class Specializer;
38 class Specialize final : public PolyMutator {
39 friend class Specializer;
40 public:
41 using PolyMutator::mutate;
42 virtual Expression * mutate( ApplicationExpr *applicationExpr ) override;
43 virtual Expression * mutate( AddressExpr *castExpr ) override;
44 virtual Expression * mutate( CastExpr *castExpr ) override;
45 // virtual Expression * mutate( LogicalExpr *logicalExpr );
46 // virtual Expression * mutate( ConditionalExpr *conditionalExpr );
47 // virtual Expression * mutate( CommaExpr *commaExpr );
48
49 Specializer * specializer = nullptr;
50 void handleExplicitParams( ApplicationExpr *appExpr );
51 };
52
53 class Specializer {
54 public:
55 Specializer( Specialize & spec ) : spec( spec ), env( spec.env ), stmtsToAdd( spec.stmtsToAdd ) {}
56 virtual bool needsSpecialization( Type * formalType, Type * actualType, TypeSubstitution * env ) = 0;
57 virtual Expression *createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) = 0;
58 virtual Expression *doSpecialization( Type *formalType, Expression *actual, InferredParams *inferParams = 0 );
59
60 protected:
61 Specialize & spec;
62 std::string paramPrefix = "_p";
63 TypeSubstitution *& env;
64 std::list< Statement * > & stmtsToAdd;
65 };
66
67 // for normal polymorphic -> monomorphic function conversion
68 class PolySpecializer : public Specializer {
69 public:
70 PolySpecializer( Specialize & spec ) : Specializer( spec ) {}
71 virtual bool needsSpecialization( Type * formalType, Type * actualType, TypeSubstitution * env ) override;
72 virtual Expression *createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) override;
73 };
74
75 // // for tuple -> non-tuple function conversion
76 class TupleSpecializer : public Specializer {
77 public:
78 TupleSpecializer( Specialize & spec ) : Specializer( spec ) {}
79 virtual bool needsSpecialization( Type * formalType, Type * actualType, TypeSubstitution * env ) override;
80 virtual Expression *createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) override;
81 };
82
83 /// Looks up open variables in actual type, returning true if any of them are bound in the environment or formal type.
84 bool PolySpecializer::needsSpecialization( Type *formalType, Type *actualType, TypeSubstitution *env ) {
85 if ( env ) {
86 using namespace ResolvExpr;
87 OpenVarSet openVars, closedVars;
88 AssertionSet need, have;
89 findOpenVars( formalType, openVars, closedVars, need, have, false );
90 findOpenVars( actualType, openVars, closedVars, need, have, true );
91 for ( OpenVarSet::const_iterator openVar = openVars.begin(); openVar != openVars.end(); ++openVar ) {
92 Type *boundType = env->lookup( openVar->first );
93 if ( ! boundType ) continue;
94 if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( boundType ) ) {
95 if ( closedVars.find( typeInst->get_name() ) == closedVars.end() ) {
96 return true;
97 } // if
98 } else {
99 return true;
100 } // if
101 } // for
102 return false;
103 } else {
104 return false;
105 } // if
106 }
107
108 /// Generates a thunk that calls `actual` with type `funType` and returns its address
109 Expression * PolySpecializer::createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) {
110 static UniqueName thunkNamer( "_thunk" );
111
112 FunctionType *newType = funType->clone();
113 if ( env ) {
114 // it is important to replace only occurrences of type variables that occur free in the
115 // thunk's type
116 env->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 if ( FunctionType *funType = getFunctionType( formalType ) ) {
169 ApplicationExpr *appExpr;
170 VariableExpr *varExpr;
171 if ( ( appExpr = dynamic_cast<ApplicationExpr*>( actual ) ) ) {
172 return createThunkFunction( funType, appExpr->get_function(), inferParams );
173 } else if ( ( varExpr = dynamic_cast<VariableExpr*>( actual ) ) ) {
174 return createThunkFunction( funType, varExpr, inferParams );
175 } else {
176 // This likely won't work, as anything that could build an ApplicationExpr probably hit one of the previous two branches
177 return createThunkFunction( funType, actual, inferParams );
178 }
179 } else {
180 return actual;
181 } // if
182 } else {
183 return actual;
184 } // if
185 }
186
187 bool TupleSpecializer::needsSpecialization( Type *formalType, Type *actualType, TypeSubstitution *env ) {
188 if ( FunctionType * ftype = getFunctionType( formalType ) ) {
189 return ftype->isTtype();
190 }
191 return false;
192 }
193
194 /// restructures arg to match the structure of a single formal parameter. Assumes that atomic types are compatible (as the Resolver should have ensured this)
195 template< typename OutIterator >
196 void matchOneFormal( Expression * arg, unsigned & idx, Type * formal, OutIterator out ) {
197 if ( TupleType * tupleType = dynamic_cast< TupleType * >( formal ) ) {
198 std::list< Expression * > exprs;
199 for ( Type * t : *tupleType ) {
200 matchOneFormal( arg, idx, t, back_inserter( exprs ) );
201 }
202 *out++ = new TupleExpr( exprs );
203 } else {
204 *out++ = new TupleIndexExpr( arg->clone(), idx++ );
205 }
206 }
207
208 /// restructures the ttype argument to match the structure of the formal parameters of the actual function.
209 // [begin, end) are the formal parameters.
210 // args is the list of arguments currently given to the actual function, the last of which needs to be restructured.
211 template< typename Iterator, typename OutIterator >
212 void fixLastArg( Expression * last, Iterator begin, Iterator end, OutIterator out ) {
213 // safe_dynamic_cast for the assertion
214 safe_dynamic_cast< TupleType * >( last->get_result() );
215 unsigned idx = 0;
216 for ( ; begin != end; ++begin ) {
217 DeclarationWithType * formal = *begin;
218 Type * formalType = formal->get_type();
219 matchOneFormal( last, idx, formalType, out );
220 }
221 delete last;
222 }
223
224 Expression * TupleSpecializer::createThunkFunction( FunctionType *funType, Expression *actual, InferredParams *inferParams ) {
225 static UniqueName thunkNamer( "_tupleThunk" );
226
227 FunctionType *newType = funType->clone();
228 if ( env ) {
229 // it is important to replace only occurrences of type variables that occur free in the
230 // thunk's type
231 env->applyFree( newType );
232 } // if
233 // create new thunk with same signature as formal type (C linkage, empty body)
234 FunctionDecl *thunkFunc = new FunctionDecl( thunkNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, newType, new CompoundStmt( noLabels ), false, false );
235 thunkFunc->fixUniqueId();
236
237 // thunks may be generated and not used - silence warning with attribute
238 thunkFunc->get_attributes().push_back( new Attribute( "unused" ) );
239
240 // thread thunk parameters into call to actual function, naming thunk parameters as we go
241 UniqueName paramNamer( paramPrefix );
242 ApplicationExpr *appExpr = new ApplicationExpr( actual );
243
244 FunctionType * actualType = getFunctionType( actual->get_result() )->clone();
245 if ( env ) {
246 // need to apply the environment to the actual function's type, since it may itself be polymorphic
247 env->apply( actualType );
248 }
249 std::unique_ptr< FunctionType > actualTypeManager( actualType ); // for RAII
250 std::list< DeclarationWithType * >::iterator actualBegin = actualType->get_parameters().begin();
251 std::list< DeclarationWithType * >::iterator actualEnd = actualType->get_parameters().end();
252 std::list< DeclarationWithType * >::iterator formalBegin = funType->get_parameters().begin();
253 std::list< DeclarationWithType * >::iterator formalEnd = funType->get_parameters().end();
254
255 Expression * last = nullptr;
256 for ( DeclarationWithType* param : thunkFunc->get_functionType()->get_parameters() ) {
257 // walk the parameters to the actual function alongside the parameters to the thunk to find the location where the ttype parameter begins to satisfy parameters in the actual function.
258 param->set_name( paramNamer.newName() );
259 assertf( formalBegin != formalEnd, "Reached end of formal parameters before finding ttype parameter" );
260 if ( Tuples::isTtype((*formalBegin)->get_type()) ) {
261 last = new VariableExpr( param );
262 break;
263 }
264 assertf( actualBegin != actualEnd, "reached end of actual function's arguments before finding ttype parameter" );
265 ++actualBegin;
266 ++formalBegin;
267
268 appExpr->get_args().push_back( new VariableExpr( param ) );
269 } // for
270 assert( last );
271 fixLastArg( last, actualBegin, actualEnd, back_inserter( appExpr->get_args() ) );
272 appExpr->set_env( maybeClone( env ) );
273 if ( inferParams ) {
274 appExpr->get_inferParams() = *inferParams;
275 } // if
276
277 // handle any specializations that may still be present
278 std::string oldParamPrefix = paramPrefix;
279 paramPrefix += "p";
280 // save stmtsToAdd in oldStmts
281 std::list< Statement* > oldStmts;
282 oldStmts.splice( oldStmts.end(), stmtsToAdd );
283 spec.mutate( appExpr );
284 paramPrefix = oldParamPrefix;
285 // write any statements added for recursive specializations into the thunk body
286 thunkFunc->get_statements()->get_kids().splice( thunkFunc->get_statements()->get_kids().end(), stmtsToAdd );
287 // restore oldStmts into stmtsToAdd
288 stmtsToAdd.splice( stmtsToAdd.end(), oldStmts );
289
290 // add return (or valueless expression) to the thunk
291 Statement *appStmt;
292 if ( funType->get_returnVals().empty() ) {
293 appStmt = new ExprStmt( noLabels, appExpr );
294 } else {
295 appStmt = new ReturnStmt( noLabels, appExpr );
296 } // if
297 thunkFunc->get_statements()->get_kids().push_back( appStmt );
298
299 // add thunk definition to queue of statements to add
300 stmtsToAdd.push_back( new DeclStmt( noLabels, thunkFunc ) );
301 // return address of thunk function as replacement expression
302 return new AddressExpr( new VariableExpr( thunkFunc ) );
303 }
304
305 void Specialize::handleExplicitParams( ApplicationExpr *appExpr ) {
306 // create thunks for the explicit parameters
307 assert( appExpr->get_function()->has_result() );
308 FunctionType *function = getFunctionType( appExpr->get_function()->get_result() );
309 assert( function );
310 std::list< DeclarationWithType* >::iterator formal;
311 std::list< Expression* >::iterator actual;
312 for ( formal = function->get_parameters().begin(), actual = appExpr->get_args().begin(); formal != function->get_parameters().end() && actual != appExpr->get_args().end(); ++formal, ++actual ) {
313 *actual = specializer->doSpecialization( (*formal )->get_type(), *actual, &appExpr->get_inferParams() );
314 }
315 }
316
317 Expression * Specialize::mutate( ApplicationExpr *appExpr ) {
318 appExpr->get_function()->acceptMutator( *this );
319 mutateAll( appExpr->get_args(), *this );
320
321 if ( ! InitTweak::isIntrinsicCallExpr( appExpr ) ) {
322 // create thunks for the inferred parameters
323 // don't need to do this for intrinsic calls, because they aren't actually passed
324 for ( InferredParams::iterator inferParam = appExpr->get_inferParams().begin(); inferParam != appExpr->get_inferParams().end(); ++inferParam ) {
325 inferParam->second.expr = specializer->doSpecialization( inferParam->second.formalType, inferParam->second.expr, inferParam->second.inferParams.get() );
326 }
327 handleExplicitParams( appExpr );
328 }
329 return appExpr;
330 }
331
332 Expression * Specialize::mutate( AddressExpr *addrExpr ) {
333 addrExpr->get_arg()->acceptMutator( *this );
334 assert( addrExpr->has_result() );
335 addrExpr->set_arg( specializer->doSpecialization( addrExpr->get_result(), addrExpr->get_arg() ) );
336 return addrExpr;
337 }
338
339 Expression * Specialize::mutate( CastExpr *castExpr ) {
340 castExpr->get_arg()->acceptMutator( *this );
341 if ( castExpr->get_result()->isVoid() ) {
342 // can't specialize if we don't have a return value
343 return castExpr;
344 }
345 Expression *specialized = specializer->doSpecialization( castExpr->get_result(), castExpr->get_arg() );
346 if ( specialized != castExpr->get_arg() ) {
347 // assume here that the specialization incorporates the cast
348 return specialized;
349 } else {
350 return castExpr;
351 }
352 }
353
354 // Removing these for now. Richard put these in for some reason, but it's not clear why.
355 // In particular, copy constructors produce a comma expression, and with this code the parts
356 // of that comma expression are not specialized, which causes problems.
357
358 // Expression * Specialize::mutate( LogicalExpr *logicalExpr ) {
359 // return logicalExpr;
360 // }
361
362 // Expression * Specialize::mutate( ConditionalExpr *condExpr ) {
363 // return condExpr;
364 // }
365
366 // Expression * Specialize::mutate( CommaExpr *commaExpr ) {
367 // return commaExpr;
368 // }
369
370 void convertSpecializations( std::list< Declaration* >& translationUnit ) {
371 Specialize spec;
372
373 TupleSpecializer tupleSpec( spec );
374 spec.specializer = &tupleSpec;
375 mutateAll( translationUnit, spec );
376
377 PolySpecializer polySpec( spec );
378 spec.specializer = &polySpec;
379 mutateAll( translationUnit, spec );
380 }
381} // namespace GenPoly
382
383// Local Variables: //
384// tab-width: 4 //
385// mode: c++ //
386// compile-command: "make install" //
387// End: //
Note: See TracBrowser for help on using the repository browser.