source: src/GenPoly/Box.cc@ 567bb17

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since 567bb17 was 567bb17, checked in by Aaron Moss <a3moss@…>, 10 years ago

fix (?) void* errors on member offsets
  • Property mode set to 100644
File size: 61.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// Box.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 : Fri Dec 18 14:53:08 2015
13// Update Count : 217
14//
15
16#include <set>
17#include <stack>
18#include <string>
19#include <iterator>
20#include <algorithm>
21#include <cassert>
22
23#include "Box.h"
24#include "InstantiateGeneric.h"
25#include "PolyMutator.h"
26#include "FindFunction.h"
27#include "ScopedMap.h"
28#include "ScrubTyVars.h"
29
30#include "Parser/ParseNode.h"
31
32#include "SynTree/Constant.h"
33#include "SynTree/Type.h"
34#include "SynTree/Expression.h"
35#include "SynTree/Initializer.h"
36#include "SynTree/Statement.h"
37#include "SynTree/Mutator.h"
38
39#include "ResolvExpr/TypeEnvironment.h"
40
41#include "SymTab/Mangler.h"
42
43#include "SemanticError.h"
44#include "UniqueName.h"
45#include "utility.h"
46
47#include <ext/functional> // temporary
48
49namespace GenPoly {
50 namespace {
51 const std::list<Label> noLabels;
52
53 FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
54
55 /// Replaces polymorphic return types with out-parameters, replaces calls to polymorphic functions with adapter calls as needed, and adds appropriate type variables to the function call
56 class Pass1 : public PolyMutator {
57 public:
58 Pass1();
59 virtual Expression *mutate( ApplicationExpr *appExpr );
60 virtual Expression *mutate( AddressExpr *addrExpr );
61 virtual Expression *mutate( UntypedExpr *expr );
62 virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
63 virtual TypeDecl *mutate( TypeDecl *typeDecl );
64 virtual Expression *mutate( CommaExpr *commaExpr );
65 virtual Expression *mutate( ConditionalExpr *condExpr );
66 virtual Statement * mutate( ReturnStmt *returnStmt );
67 virtual Type *mutate( PointerType *pointerType );
68 virtual Type * mutate( FunctionType *functionType );
69
70 virtual void doBeginScope();
71 virtual void doEndScope();
72 private:
73 /// Makes a new temporary array holding the offsets of the fields of `type`, and returns a new variable expression referencing it
74 Expression *makeOffsetArray( StructInstType *type );
75 /// passes extra type parameters into a polymorphic function application
76 void passTypeVars( ApplicationExpr *appExpr, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
77 /// wraps a function application with a new temporary for the out-parameter return value
78 Expression *addRetParam( ApplicationExpr *appExpr, FunctionType *function, Type *retType, std::list< Expression *>::iterator &arg );
79 /// Replaces all the type parameters of a generic type with their concrete equivalents under the current environment
80 void replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params );
81 /// Replaces a polymorphic type with its concrete equivalant under the current environment (returns itself if concrete).
82 /// If `doClone` is set to false, will not clone interior types
83 Type *replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone = true );
84 /// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value
85 Expression *addPolyRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg );
86 Expression *applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
87 void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
88 void boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
89 void addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars );
90 /// Stores assignment operators from assertion list in local map of assignment operations
91 void findAssignOps( const std::list< TypeDecl *> &forall );
92 void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars );
93 FunctionDecl *makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
94 /// Replaces intrinsic operator functions with their arithmetic desugaring
95 Expression *handleIntrinsics( ApplicationExpr *appExpr );
96 /// Inserts a new temporary variable into the current scope with an auto-generated name
97 ObjectDecl *makeTemporary( Type *type );
98
99 typedef std::map< std::string, DeclarationWithType *> AdapterMap;
100 std::map< std::string, DeclarationWithType *> assignOps;
101 ScopedMap< std::string, DeclarationWithType *> scopedAssignOps;
102 std::stack< AdapterMap > adapters;
103 DeclarationWithType *retval;
104 bool useRetval;
105 UniqueName tempNamer;
106 };
107
108 /// Moves polymorphic returns in function types to pointer-type parameters, adds type size and assertion parameters to parameter lists as well
109 class Pass2 : public PolyMutator {
110 public:
111 template< typename DeclClass >
112 DeclClass *handleDecl( DeclClass *decl, Type *type );
113 virtual DeclarationWithType *mutate( FunctionDecl *functionDecl );
114 virtual ObjectDecl *mutate( ObjectDecl *objectDecl );
115 virtual TypeDecl *mutate( TypeDecl *typeDecl );
116 virtual TypedefDecl *mutate( TypedefDecl *typedefDecl );
117 virtual Type *mutate( PointerType *pointerType );
118 virtual Type *mutate( FunctionType *funcType );
119 private:
120 void addAdapters( FunctionType *functionType );
121
122 std::map< UniqueId, std::string > adapterName;
123 };
124
125 /// Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference
126 class MemberExprFixer : public PolyMutator {
127 public:
128 template< typename DeclClass >
129 DeclClass *handleDecl( DeclClass *decl, Type *type );
130 virtual DeclarationWithType *mutate( FunctionDecl *functionDecl );
131 virtual ObjectDecl *mutate( ObjectDecl *objectDecl );
132 virtual TypedefDecl *mutate( TypedefDecl *objectDecl );
133 virtual TypeDecl *mutate( TypeDecl *objectDecl );
134 virtual Statement *mutate( DeclStmt *declStmt );
135 virtual Type *mutate( PointerType *pointerType );
136 virtual Type *mutate( FunctionType *funcType );
137 virtual Expression *mutate( MemberExpr *memberExpr );
138 };
139
140 /// Replaces initialization of polymorphic values with alloca, declaration of dtype/ftype with appropriate void expression, and sizeof expressions of polymorphic types with the proper variable
141 class Pass3 : public PolyMutator {
142 public:
143 template< typename DeclClass >
144 DeclClass *handleDecl( DeclClass *decl, Type *type );
145 virtual DeclarationWithType *mutate( FunctionDecl *functionDecl );
146 virtual ObjectDecl *mutate( ObjectDecl *objectDecl );
147 virtual TypedefDecl *mutate( TypedefDecl *objectDecl );
148 virtual TypeDecl *mutate( TypeDecl *objectDecl );
149 virtual Type *mutate( PointerType *pointerType );
150 virtual Type *mutate( FunctionType *funcType );
151 private:
152 };
153
154 } // anonymous namespace
155
156 void printAllNotBuiltin( const std::list< Declaration *>& translationUnit, std::ostream &os ) {
157 for ( std::list< Declaration *>::const_iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
158 if ( ! LinkageSpec::isBuiltin( (*i)->get_linkage() ) ) {
159 (*i)->print( os );
160 os << std::endl;
161 } // if
162 } // for
163 }
164
165 /// version of mutateAll with special handling for translation unit so you can check the end of the prelude when debugging
166 template< typename MutatorType >
167 inline void mutateTranslationUnit( std::list< Declaration* > &translationUnit, MutatorType &mutator ) {
168 bool seenIntrinsic = false;
169 SemanticError errors;
170 for ( typename std::list< Declaration* >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
171 try {
172 if ( *i ) {
173 if ( (*i)->get_linkage() == LinkageSpec::Intrinsic ) {
174 seenIntrinsic = true;
175 } else if ( seenIntrinsic ) {
176 seenIntrinsic = false; // break on this line when debugging for end of prelude
177 }
178
179 *i = dynamic_cast< Declaration* >( (*i)->acceptMutator( mutator ) );
180 assert( *i );
181 } // if
182 } catch( SemanticError &e ) {
183 errors.append( e );
184 } // try
185 } // for
186 if ( ! errors.isEmpty() ) {
187 throw errors;
188 } // if
189 }
190
191 void box( std::list< Declaration *>& translationUnit ) {
192 Pass1 pass1;
193 Pass2 pass2;
194 MemberExprFixer memberFixer;
195 Pass3 pass3;
196 mutateTranslationUnit/*All*/( translationUnit, pass1 );
197 mutateTranslationUnit/*All*/( translationUnit, pass2 );
198 instantiateGeneric( translationUnit );
199 mutateTranslationUnit/*All*/( translationUnit, memberFixer );
200 mutateTranslationUnit/*All*/( translationUnit, pass3 );
201 }
202
203 ////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////
204
205 namespace {
206 std::string makePolyMonoSuffix( FunctionType * function, const TyVarMap &tyVars ) {
207 std::stringstream name;
208
209 // NOTE: this function previously used isPolyObj, which failed to produce
210 // the correct thing in some situations. It's not clear to me why this wasn't working.
211
212 // if the return type or a parameter type involved polymorphic types, then the adapter will need
213 // to take those polymorphic types as pointers. Therefore, there can be two different functions
214 // with the same mangled name, so we need to further mangle the names.
215 for ( std::list< DeclarationWithType *>::iterator retval = function->get_returnVals().begin(); retval != function->get_returnVals().end(); ++retval ) {
216 if ( isPolyType( (*retval)->get_type(), tyVars ) ) {
217 name << "P";
218 } else {
219 name << "M";
220 }
221 }
222 name << "_";
223 std::list< DeclarationWithType *> &paramList = function->get_parameters();
224 for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
225 if ( isPolyType( (*arg)->get_type(), tyVars ) ) {
226 name << "P";
227 } else {
228 name << "M";
229 }
230 } // for
231 return name.str();
232 }
233
234 std::string mangleAdapterName( FunctionType * function, const TyVarMap &tyVars ) {
235 return SymTab::Mangler::mangle( function ) + makePolyMonoSuffix( function, tyVars );
236 }
237
238 std::string makeAdapterName( const std::string &mangleName ) {
239 return "_adapter" + mangleName;
240 }
241
242 Pass1::Pass1() : useRetval( false ), tempNamer( "_temp" ) {
243 adapters.push(AdapterMap());
244 }
245
246 /// returns T if the given declaration is: (*?=?)(T *, T) for some T (return not checked, but maybe should be), NULL otherwise
247 ReferenceToType *isAssignment( DeclarationWithType *decl ) {
248 if ( decl->get_name() == "?=?" ) {
249 if ( FunctionType *funType = getFunctionType( decl->get_type() ) ) {
250 if ( funType->get_parameters().size() == 2 ) {
251 if ( PointerType *pointer = dynamic_cast< PointerType *>( funType->get_parameters().front()->get_type() ) ) {
252 if ( ReferenceToType *refType = dynamic_cast< ReferenceToType *>( pointer->get_base() ) ) {
253 if ( ReferenceToType *refType2 = dynamic_cast< ReferenceToType *>( funType->get_parameters().back()->get_type() ) ) {
254 if ( refType->get_name() == refType2->get_name() ) {
255 return refType;
256 } // if
257 } // if
258 } // if
259 } // if
260 } // if
261 } // if
262 } // if
263 return 0;
264 }
265
266 void Pass1::findAssignOps( const std::list< TypeDecl *> &forall ) {
267 // what if a nested function uses an assignment operator?
268 // assignOps.clear();
269 for ( std::list< TypeDecl *>::const_iterator i = forall.begin(); i != forall.end(); ++i ) {
270 for ( std::list< DeclarationWithType *>::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) {
271 std::string typeName;
272 if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( isAssignment( *assert ) ) ) {
273 assignOps[ typeInst->get_name() ] = *assert;
274 } // if
275 } // for
276 } // for
277 }
278
279 DeclarationWithType *Pass1::mutate( FunctionDecl *functionDecl ) {
280 // if this is a polymorphic assignment function, put it in the map for this scope
281 if ( ReferenceToType *refType = isAssignment( functionDecl ) ) {
282 if ( ! dynamic_cast< TypeInstType* >( refType ) ) {
283 scopedAssignOps.insert( refType->get_name(), functionDecl );
284 }
285 }
286
287 if ( functionDecl->get_statements() ) { // empty routine body ?
288 doBeginScope();
289 TyVarMap oldtyVars = scopeTyVars;
290 std::map< std::string, DeclarationWithType *> oldassignOps = assignOps;
291 DeclarationWithType *oldRetval = retval;
292 bool oldUseRetval = useRetval;
293
294 // process polymorphic return value
295 retval = 0;
296 if ( isPolyRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() == LinkageSpec::Cforall ) {
297 retval = functionDecl->get_functionType()->get_returnVals().front();
298
299 // give names to unnamed return values
300 if ( retval->get_name() == "" ) {
301 retval->set_name( "_retparm" );
302 retval->set_linkage( LinkageSpec::C );
303 } // if
304 } // if
305
306 FunctionType *functionType = functionDecl->get_functionType();
307 makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
308 findAssignOps( functionDecl->get_functionType()->get_forall() );
309
310 std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
311 std::list< FunctionType *> functions;
312 for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
313 for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
314 findFunction( (*assert)->get_type(), functions, scopeTyVars, needsAdapter );
315 } // for
316 } // for
317 for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
318 findFunction( (*arg)->get_type(), functions, scopeTyVars, needsAdapter );
319 } // for
320
321 AdapterMap & adapters = Pass1::adapters.top();
322 for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
323 std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
324 if ( adapters.find( mangleName ) == adapters.end() ) {
325 std::string adapterName = makeAdapterName( mangleName );
326 adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, new ObjectDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) ) );
327 } // if
328 } // for
329
330 functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
331
332 scopeTyVars = oldtyVars;
333 assignOps = oldassignOps;
334 // std::cerr << "end FunctionDecl: ";
335 // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
336 // std::cerr << i->first << " ";
337 // }
338 // std::cerr << "\n";
339 retval = oldRetval;
340 useRetval = oldUseRetval;
341 doEndScope();
342 } // if
343 return functionDecl;
344 }
345
346 TypeDecl *Pass1::mutate( TypeDecl *typeDecl ) {
347 scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
348 return Mutator::mutate( typeDecl );
349 }
350
351 Expression *Pass1::mutate( CommaExpr *commaExpr ) {
352 bool oldUseRetval = useRetval;
353 useRetval = false;
354 commaExpr->set_arg1( maybeMutate( commaExpr->get_arg1(), *this ) );
355 useRetval = oldUseRetval;
356 commaExpr->set_arg2( maybeMutate( commaExpr->get_arg2(), *this ) );
357 return commaExpr;
358 }
359
360 Expression *Pass1::mutate( ConditionalExpr *condExpr ) {
361 bool oldUseRetval = useRetval;
362 useRetval = false;
363 condExpr->set_arg1( maybeMutate( condExpr->get_arg1(), *this ) );
364 useRetval = oldUseRetval;
365 condExpr->set_arg2( maybeMutate( condExpr->get_arg2(), *this ) );
366 condExpr->set_arg3( maybeMutate( condExpr->get_arg3(), *this ) );
367 return condExpr;
368
369 }
370
371 Expression *Pass1::makeOffsetArray( StructInstType *ty ) {
372 // make a new temporary array
373 Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
374 ObjectDecl *arrayTemp = makeTemporary( new PointerType( Type::Qualifiers(), offsetType ) );
375
376 // build initializer list for temporary
377 std::list< Initializer* > inits;
378 StructDecl *tyBase = ty->get_baseStruct();
379 for ( std::list< Declaration* >::const_iterator member = tyBase->get_members().begin(); member != tyBase->get_members().end(); ++member ) {
380 DeclarationWithType *memberDecl;
381 if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
382 memberDecl = origMember->clone();
383 } else {
384 memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
385 }
386 inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
387 }
388 arrayTemp->set_init( new ListInit( inits ) );
389
390 // return variable pointing to temporary
391 return new VariableExpr( arrayTemp );
392 }
393
394 void Pass1::passTypeVars( ApplicationExpr *appExpr, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
395 // pass size/align for type variables
396 for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
397 ResolvExpr::EqvClass eqvClass;
398 assert( env );
399 if ( tyParm->second == TypeDecl::Any ) {
400 Type *concrete = env->lookup( tyParm->first );
401 if ( concrete ) {
402 arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
403 arg++;
404 arg = appExpr->get_args().insert( arg, new AlignofExpr( concrete->clone() ) );
405 arg++;
406 } else {
407 throw SemanticError( "unbound type variable in application ", appExpr );
408 } // if
409 } // if
410 } // for
411
412 // add size/align for generic types to parameter list
413 if ( appExpr->get_function()->get_results().empty() ) return;
414 FunctionType *funcType = getFunctionType( appExpr->get_function()->get_results().front() );
415 assert( funcType );
416
417 std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
418 std::list< Expression* >::const_iterator fnArg = arg;
419 std::set< std::string > seenTypes; //< names for generic types we've seen
420 for ( ; fnParm != funcType->get_parameters().end() && fnArg != appExpr->get_args().end(); ++fnParm, ++fnArg ) {
421 Type *parmType = (*fnParm)->get_type();
422 if ( ! dynamic_cast< TypeInstType* >( parmType ) && isPolyType( parmType, exprTyVars ) ) {
423 std::string sizeName = sizeofName( parmType );
424 if ( seenTypes.count( sizeName ) ) continue;
425
426 assert( ! (*fnArg)->get_results().empty() );
427 Type *argType = (*fnArg)->get_results().front();
428 arg = appExpr->get_args().insert( arg, new SizeofExpr( argType->clone() ) );
429 arg++;
430 arg = appExpr->get_args().insert( arg, new AlignofExpr( argType->clone() ) );
431 arg++;
432 if ( dynamic_cast< StructInstType* >( parmType ) ) {
433 if ( StructInstType *argStructType = dynamic_cast< StructInstType* >( argType ) ) {
434 arg = appExpr->get_args().insert( arg, makeOffsetArray( argStructType ) );
435 arg++;
436 } else {
437 throw SemanticError( "Cannot pass non-struct type for generic struct" );
438 }
439 }
440
441 seenTypes.insert( sizeName );
442 }
443 }
444 }
445
446 ObjectDecl *Pass1::makeTemporary( Type *type ) {
447 ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, type, 0 );
448 stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
449 return newObj;
450 }
451
452 Expression *Pass1::addRetParam( ApplicationExpr *appExpr, FunctionType *function, Type *retType, std::list< Expression *>::iterator &arg ) {
453 // ***** Code Removal ***** After introducing a temporary variable for all return expressions, the following code appears superfluous.
454 // if ( useRetval ) {
455 // assert( retval );
456 // arg = appExpr->get_args().insert( arg, new VariableExpr( retval ) );
457 // arg++;
458 // } else {
459
460 // Create temporary to hold return value of polymorphic function and produce that temporary as a result
461 // using a comma expression. Possibly change comma expression into statement expression "{}" for multiple
462 // return values.
463 ObjectDecl *newObj = makeTemporary( retType->clone() );
464 Expression *paramExpr = new VariableExpr( newObj );
465 // If the type of the temporary is not polymorphic, box temporary by taking its address; otherwise the
466 // temporary is already boxed and can be used directly.
467 if ( ! isPolyType( newObj->get_type(), scopeTyVars, env ) ) {
468 paramExpr = new AddressExpr( paramExpr );
469 } // if
470 arg = appExpr->get_args().insert( arg, paramExpr ); // add argument to function call
471 arg++;
472 // Build a comma expression to call the function and emulate a normal return.
473 CommaExpr *commaExpr = new CommaExpr( appExpr, new VariableExpr( newObj ) );
474 commaExpr->set_env( appExpr->get_env() );
475 appExpr->set_env( 0 );
476 return commaExpr;
477 // } // if
478 // return appExpr;
479 }
480
481 void Pass1::replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params ) {
482 for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
483 TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
484 assert(paramType && "Aggregate parameters should be type expressions");
485 paramType->set_type( replaceWithConcrete( appExpr, paramType->get_type(), false ) );
486 }
487 }
488
489 Type *Pass1::replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone ) {
490 if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) {
491 Type *concrete = env->lookup( typeInst->get_name() );
492 if ( concrete == 0 ) {
493 throw SemanticError( "Unbound type variable " + typeInst->get_name() + " in ", appExpr );
494 } // if
495 return concrete;
496 } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
497 if ( doClone ) {
498 structType = structType->clone();
499 }
500 replaceParametersWithConcrete( appExpr, structType->get_parameters() );
501 return structType;
502 } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
503 if ( doClone ) {
504 unionType = unionType->clone();
505 }
506 replaceParametersWithConcrete( appExpr, unionType->get_parameters() );
507 return unionType;
508 }
509 return type;
510 }
511
512 Expression *Pass1::addPolyRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg ) {
513 assert( env );
514 Type *concrete = replaceWithConcrete( appExpr, polyType );
515 return addRetParam( appExpr, function, concrete, arg );
516 }
517
518 Expression *Pass1::applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
519 Expression *ret = appExpr;
520 if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
521 ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
522 } // if
523 std::string mangleName = mangleAdapterName( function, tyVars );
524 std::string adapterName = makeAdapterName( mangleName );
525
526 appExpr->get_args().push_front( appExpr->get_function() );
527 appExpr->set_function( new NameExpr( adapterName ) );
528
529 return ret;
530 }
531
532 void Pass1::boxParam( Type *param, Expression *&arg, const TyVarMap &exprTyVars ) {
533 assert( ! arg->get_results().empty() );
534 if ( isPolyType( param, exprTyVars ) ) {
535 if ( dynamic_cast< TypeInstType *>( arg->get_results().front() ) ) {
536 // if the argument's type is a type parameter, we don't need to box again!
537 return;
538 } else if ( arg->get_results().front()->get_isLvalue() ) {
539 // VariableExpr and MemberExpr are lvalues
540 arg = new AddressExpr( arg );
541 } else {
542 ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, arg->get_results().front()->clone(), 0 );
543 newObj->get_type()->get_qualifiers() = Type::Qualifiers(); // TODO: is this right???
544 stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
545 UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
546 assign->get_args().push_back( new VariableExpr( newObj ) );
547 assign->get_args().push_back( arg );
548 stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
549 arg = new AddressExpr( new VariableExpr( newObj ) );
550 } // if
551 } // if
552 }
553
554 void addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars ) {
555 Type *newType = formal->clone();
556 std::list< FunctionType *> functions;
557 // instead of functions needing adapters, this really ought to look for
558 // any function mentioning a polymorphic type
559 findAndReplaceFunction( newType, functions, tyVars, needsAdapter );
560 if ( ! functions.empty() ) {
561 actual = new CastExpr( actual, newType );
562 } else {
563 delete newType;
564 } // if
565 }
566
567 void Pass1::boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
568 for ( std::list< DeclarationWithType *>::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
569 assert( arg != appExpr->get_args().end() );
570 addCast( *arg, (*param)->get_type(), exprTyVars );
571 boxParam( (*param)->get_type(), *arg, exprTyVars );
572 } // for
573 }
574
575 void Pass1::addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
576 std::list< Expression *>::iterator cur = arg;
577 for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
578 for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
579 InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
580 assert( inferParam != appExpr->get_inferParams().end() && "NOTE: Explicit casts of polymorphic functions to compatible monomorphic functions are currently unsupported" );
581 Expression *newExpr = inferParam->second.expr->clone();
582 addCast( newExpr, (*assert)->get_type(), tyVars );
583 boxParam( (*assert)->get_type(), newExpr, tyVars );
584 appExpr->get_args().insert( cur, newExpr );
585 } // for
586 } // for
587 }
588
589 void makeRetParm( FunctionType *funcType ) {
590 DeclarationWithType *retParm = funcType->get_returnVals().front();
591
592 // make a new parameter that is a pointer to the type of the old return value
593 retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
594 funcType->get_parameters().push_front( retParm );
595
596 // we don't need the return value any more
597 funcType->get_returnVals().clear();
598 }
599
600 FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars ) {
601 // actually make the adapter type
602 FunctionType *adapter = adaptee->clone();
603 if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
604 makeRetParm( adapter );
605 } // if
606 adapter->get_parameters().push_front( new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
607 return adapter;
608 }
609
610 Expression *makeAdapterArg( DeclarationWithType *param, DeclarationWithType *arg, DeclarationWithType *realParam, const TyVarMap &tyVars ) {
611 assert( param );
612 assert( arg );
613 if ( isPolyType( realParam->get_type(), tyVars ) ) {
614 if ( dynamic_cast<TypeInstType *>(arg->get_type()) == NULL ) {
615 UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
616 deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
617 deref->get_results().push_back( arg->get_type()->clone() );
618 return deref;
619 } // if
620 } // if
621 return new VariableExpr( param );
622 }
623
624 void addAdapterParams( ApplicationExpr *adapteeApp, std::list< DeclarationWithType *>::iterator arg, std::list< DeclarationWithType *>::iterator param, std::list< DeclarationWithType *>::iterator paramEnd, std::list< DeclarationWithType *>::iterator realParam, const TyVarMap &tyVars ) {
625 UniqueName paramNamer( "_p" );
626 for ( ; param != paramEnd; ++param, ++arg, ++realParam ) {
627 if ( (*param)->get_name() == "" ) {
628 (*param)->set_name( paramNamer.newName() );
629 (*param)->set_linkage( LinkageSpec::C );
630 } // if
631 adapteeApp->get_args().push_back( makeAdapterArg( *param, *arg, *realParam, tyVars ) );
632 } // for
633 }
634
635
636
637 FunctionDecl *Pass1::makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) {
638 FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
639 adapterType = ScrubTyVars::scrub( adapterType, tyVars );
640 DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
641 adapteeDecl->set_name( "_adaptee" );
642 ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
643 Statement *bodyStmt;
644
645 std::list< TypeDecl *>::iterator tyArg = realType->get_forall().begin();
646 std::list< TypeDecl *>::iterator tyParam = adapterType->get_forall().begin();
647 std::list< TypeDecl *>::iterator realTyParam = adaptee->get_forall().begin();
648 for ( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
649 assert( tyArg != realType->get_forall().end() );
650 std::list< DeclarationWithType *>::iterator assertArg = (*tyArg)->get_assertions().begin();
651 std::list< DeclarationWithType *>::iterator assertParam = (*tyParam)->get_assertions().begin();
652 std::list< DeclarationWithType *>::iterator realAssertParam = (*realTyParam)->get_assertions().begin();
653 for ( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
654 assert( assertArg != (*tyArg)->get_assertions().end() );
655 adapteeApp->get_args().push_back( makeAdapterArg( *assertParam, *assertArg, *realAssertParam, tyVars ) );
656 } // for
657 } // for
658
659 std::list< DeclarationWithType *>::iterator arg = realType->get_parameters().begin();
660 std::list< DeclarationWithType *>::iterator param = adapterType->get_parameters().begin();
661 std::list< DeclarationWithType *>::iterator realParam = adaptee->get_parameters().begin();
662 param++; // skip adaptee parameter
663 if ( realType->get_returnVals().empty() ) {
664 addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
665 bodyStmt = new ExprStmt( noLabels, adapteeApp );
666 } else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
667 if ( (*param)->get_name() == "" ) {
668 (*param)->set_name( "_ret" );
669 (*param)->set_linkage( LinkageSpec::C );
670 } // if
671 UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
672 UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
673 deref->get_args().push_back( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
674 assign->get_args().push_back( deref );
675 addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
676 assign->get_args().push_back( adapteeApp );
677 bodyStmt = new ExprStmt( noLabels, assign );
678 } else {
679 // adapter for a function that returns a monomorphic value
680 addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
681 bodyStmt = new ReturnStmt( noLabels, adapteeApp );
682 } // if
683 CompoundStmt *adapterBody = new CompoundStmt( noLabels );
684 adapterBody->get_kids().push_back( bodyStmt );
685 std::string adapterName = makeAdapterName( mangleName );
686 return new FunctionDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, adapterType, adapterBody, false, false );
687 }
688
689 void Pass1::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) {
690 // collect a list of function types passed as parameters or implicit parameters (assertions)
691 std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
692 std::list< FunctionType *> functions;
693 for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
694 for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
695 findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
696 } // for
697 } // for
698 for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
699 findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
700 } // for
701
702 // parameter function types for which an appropriate adapter has been generated. we cannot use the types
703 // after applying substitutions, since two different parameter types may be unified to the same type
704 std::set< std::string > adaptersDone;
705
706 for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
707 FunctionType *originalFunction = (*funType)->clone();
708 FunctionType *realFunction = (*funType)->clone();
709 std::string mangleName = SymTab::Mangler::mangle( realFunction );
710
711 // only attempt to create an adapter or pass one as a parameter if we haven't already done so for this
712 // pre-substitution parameter function type.
713 if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
714 adaptersDone.insert( adaptersDone.begin(), mangleName );
715
716 // apply substitution to type variables to figure out what the adapter's type should look like
717 assert( env );
718 env->apply( realFunction );
719 mangleName = SymTab::Mangler::mangle( realFunction );
720 mangleName += makePolyMonoSuffix( originalFunction, exprTyVars );
721
722 AdapterMap & adapters = Pass1::adapters.top();
723 AdapterMap::iterator adapter = adapters.find( mangleName );
724 if ( adapter == adapters.end() ) {
725 // adapter has not been created yet in the current scope, so define it
726 FunctionDecl *newAdapter = makeAdapter( *funType, realFunction, mangleName, exprTyVars );
727 adapter = adapters.insert( adapters.begin(), std::pair< std::string, DeclarationWithType *>( mangleName, newAdapter ) );
728 stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
729 } // if
730 assert( adapter != adapters.end() );
731
732 // add the appropriate adapter as a parameter
733 appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
734 } // if
735 } // for
736 } // passAdapters
737
738 Expression *makeIncrDecrExpr( ApplicationExpr *appExpr, Type *polyType, bool isIncr ) {
739 NameExpr *opExpr;
740 if ( isIncr ) {
741 opExpr = new NameExpr( "?+=?" );
742 } else {
743 opExpr = new NameExpr( "?-=?" );
744 } // if
745 UntypedExpr *addAssign = new UntypedExpr( opExpr );
746 if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
747 addAssign->get_args().push_back( address->get_arg() );
748 } else {
749 addAssign->get_args().push_back( appExpr->get_args().front() );
750 } // if
751 addAssign->get_args().push_back( new NameExpr( sizeofName( polyType ) ) );
752 addAssign->get_results().front() = appExpr->get_results().front()->clone();
753 if ( appExpr->get_env() ) {
754 addAssign->set_env( appExpr->get_env() );
755 appExpr->set_env( 0 );
756 } // if
757 appExpr->get_args().clear();
758 delete appExpr;
759 return addAssign;
760 }
761
762 Expression *Pass1::handleIntrinsics( ApplicationExpr *appExpr ) {
763 if ( VariableExpr *varExpr = dynamic_cast< VariableExpr *>( appExpr->get_function() ) ) {
764 if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
765 if ( varExpr->get_var()->get_name() == "?[?]" ) {
766 assert( ! appExpr->get_results().empty() );
767 assert( appExpr->get_args().size() == 2 );
768 Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
769 Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
770 assert( ! baseType1 || ! baseType2 ); // the arguments cannot both be polymorphic pointers
771 UntypedExpr *ret = 0;
772 if ( baseType1 || baseType2 ) { // one of the arguments is a polymorphic pointer
773 ret = new UntypedExpr( new NameExpr( "?+?" ) );
774 } // if
775 if ( baseType1 ) {
776 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
777 multiply->get_args().push_back( appExpr->get_args().back() );
778 multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
779 ret->get_args().push_back( appExpr->get_args().front() );
780 ret->get_args().push_back( multiply );
781 } else if ( baseType2 ) {
782 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
783 multiply->get_args().push_back( appExpr->get_args().front() );
784 multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
785 ret->get_args().push_back( multiply );
786 ret->get_args().push_back( appExpr->get_args().back() );
787 } // if
788 if ( baseType1 || baseType2 ) {
789 ret->get_results().push_front( appExpr->get_results().front()->clone() );
790 if ( appExpr->get_env() ) {
791 ret->set_env( appExpr->get_env() );
792 appExpr->set_env( 0 );
793 } // if
794 appExpr->get_args().clear();
795 delete appExpr;
796 return ret;
797 } // if
798 } else if ( varExpr->get_var()->get_name() == "*?" ) {
799 assert( ! appExpr->get_results().empty() );
800 assert( ! appExpr->get_args().empty() );
801 if ( isPolyType( appExpr->get_results().front(), scopeTyVars, env ) ) {
802 Expression *ret = appExpr->get_args().front();
803 delete ret->get_results().front();
804 ret->get_results().front() = appExpr->get_results().front()->clone();
805 if ( appExpr->get_env() ) {
806 ret->set_env( appExpr->get_env() );
807 appExpr->set_env( 0 );
808 } // if
809 appExpr->get_args().clear();
810 delete appExpr;
811 return ret;
812 } // if
813 } else if ( varExpr->get_var()->get_name() == "?++" || varExpr->get_var()->get_name() == "?--" ) {
814 assert( ! appExpr->get_results().empty() );
815 assert( appExpr->get_args().size() == 1 );
816 if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
817 Type *tempType = appExpr->get_results().front()->clone();
818 if ( env ) {
819 env->apply( tempType );
820 } // if
821 ObjectDecl *newObj = makeTemporary( tempType );
822 VariableExpr *tempExpr = new VariableExpr( newObj );
823 UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
824 assignExpr->get_args().push_back( tempExpr->clone() );
825 if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
826 assignExpr->get_args().push_back( address->get_arg()->clone() );
827 } else {
828 assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
829 } // if
830 CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) );
831 return new CommaExpr( firstComma, tempExpr );
832 } // if
833 } else if ( varExpr->get_var()->get_name() == "++?" || varExpr->get_var()->get_name() == "--?" ) {
834 assert( ! appExpr->get_results().empty() );
835 assert( appExpr->get_args().size() == 1 );
836 if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
837 return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" );
838 } // if
839 } else if ( varExpr->get_var()->get_name() == "?+?" || varExpr->get_var()->get_name() == "?-?" ) {
840 assert( ! appExpr->get_results().empty() );
841 assert( appExpr->get_args().size() == 2 );
842 Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
843 Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
844 if ( baseType1 && baseType2 ) {
845 UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
846 divide->get_args().push_back( appExpr );
847 divide->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
848 divide->get_results().push_front( appExpr->get_results().front()->clone() );
849 if ( appExpr->get_env() ) {
850 divide->set_env( appExpr->get_env() );
851 appExpr->set_env( 0 );
852 } // if
853 return divide;
854 } else if ( baseType1 ) {
855 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
856 multiply->get_args().push_back( appExpr->get_args().back() );
857 multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
858 appExpr->get_args().back() = multiply;
859 } else if ( baseType2 ) {
860 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
861 multiply->get_args().push_back( appExpr->get_args().front() );
862 multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
863 appExpr->get_args().front() = multiply;
864 } // if
865 } else if ( varExpr->get_var()->get_name() == "?+=?" || varExpr->get_var()->get_name() == "?-=?" ) {
866 assert( ! appExpr->get_results().empty() );
867 assert( appExpr->get_args().size() == 2 );
868 Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env );
869 if ( baseType ) {
870 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
871 multiply->get_args().push_back( appExpr->get_args().back() );
872 multiply->get_args().push_back( new NameExpr( sizeofName( baseType ) ) );
873 appExpr->get_args().back() = multiply;
874 } // if
875 } // if
876 return appExpr;
877 } // if
878 } // if
879 return 0;
880 }
881
882 Expression *Pass1::mutate( ApplicationExpr *appExpr ) {
883 // std::cerr << "mutate appExpr: ";
884 // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
885 // std::cerr << i->first << " ";
886 // }
887 // std::cerr << "\n";
888 bool oldUseRetval = useRetval;
889 useRetval = false;
890 appExpr->get_function()->acceptMutator( *this );
891 mutateAll( appExpr->get_args(), *this );
892 useRetval = oldUseRetval;
893
894 assert( ! appExpr->get_function()->get_results().empty() );
895 PointerType *pointer = dynamic_cast< PointerType *>( appExpr->get_function()->get_results().front() );
896 assert( pointer );
897 FunctionType *function = dynamic_cast< FunctionType *>( pointer->get_base() );
898 assert( function );
899
900 if ( Expression *newExpr = handleIntrinsics( appExpr ) ) {
901 return newExpr;
902 } // if
903
904 Expression *ret = appExpr;
905
906 std::list< Expression *>::iterator arg = appExpr->get_args().begin();
907 std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin();
908
909 if ( ReferenceToType *polyType = isPolyRet( function ) ) {
910 ret = addPolyRetParam( appExpr, function, polyType, arg );
911 } else if ( needsAdapter( function, scopeTyVars ) ) {
912 // std::cerr << "needs adapter: ";
913 // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
914 // std::cerr << i->first << " ";
915 // }
916 // std::cerr << "\n";
917 // change the application so it calls the adapter rather than the passed function
918 ret = applyAdapter( appExpr, function, arg, scopeTyVars );
919 } // if
920 arg = appExpr->get_args().begin();
921
922 TyVarMap exprTyVars;
923 makeTyVarMap( function, exprTyVars );
924
925 passTypeVars( appExpr, arg, exprTyVars );
926 addInferredParams( appExpr, function, arg, exprTyVars );
927
928 arg = paramBegin;
929
930 boxParams( appExpr, function, arg, exprTyVars );
931
932 passAdapters( appExpr, function, exprTyVars );
933
934 return ret;
935 }
936
937 Expression *Pass1::mutate( UntypedExpr *expr ) {
938 if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
939 if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
940 if ( name->get_name() == "*?" ) {
941 Expression *ret = expr->get_args().front();
942 expr->get_args().clear();
943 delete expr;
944 return ret->acceptMutator( *this );
945 } // if
946 } // if
947 } // if
948 return PolyMutator::mutate( expr );
949 }
950
951 Expression *Pass1::mutate( AddressExpr *addrExpr ) {
952 assert( ! addrExpr->get_arg()->get_results().empty() );
953
954 bool needs = false;
955 if ( UntypedExpr *expr = dynamic_cast< UntypedExpr *>( addrExpr->get_arg() ) ) {
956 if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
957 if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
958 if ( name->get_name() == "*?" ) {
959 if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
960 assert( ! appExpr->get_function()->get_results().empty() );
961 PointerType *pointer = dynamic_cast< PointerType *>( appExpr->get_function()->get_results().front() );
962 assert( pointer );
963 FunctionType *function = dynamic_cast< FunctionType *>( pointer->get_base() );
964 assert( function );
965 needs = needsAdapter( function, scopeTyVars );
966 } // if
967 } // if
968 } // if
969 } // if
970 } // if
971 addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
972 if ( isPolyType( addrExpr->get_arg()->get_results().front(), scopeTyVars, env ) || needs ) {
973 Expression *ret = addrExpr->get_arg();
974 delete ret->get_results().front();
975 ret->get_results().front() = addrExpr->get_results().front()->clone();
976 addrExpr->set_arg( 0 );
977 delete addrExpr;
978 return ret;
979 } else {
980 return addrExpr;
981 } // if
982 }
983
984 Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
985 if ( retval && returnStmt->get_expr() ) {
986 assert( ! returnStmt->get_expr()->get_results().empty() );
987 // ***** Code Removal ***** After introducing a temporary variable for all return expressions, the following code appears superfluous.
988 // if ( returnStmt->get_expr()->get_results().front()->get_isLvalue() ) {
989 // by this point, a cast expr on a polymorphic return value is redundant
990 while ( CastExpr *castExpr = dynamic_cast< CastExpr *>( returnStmt->get_expr() ) ) {
991 returnStmt->set_expr( castExpr->get_arg() );
992 returnStmt->get_expr()->set_env( castExpr->get_env() );
993 castExpr->set_env( 0 );
994 castExpr->set_arg( 0 );
995 delete castExpr;
996 } //while
997
998 // find assignment operator for (polymorphic) return type
999 DeclarationWithType *assignDecl = 0;
1000 if ( TypeInstType *typeInst = dynamic_cast< TypeInstType *>( retval->get_type() ) ) {
1001 std::map< std::string, DeclarationWithType *>::const_iterator assignIter = assignOps.find( typeInst->get_name() );
1002 if ( assignIter == assignOps.end() ) {
1003 throw SemanticError( "Attempt to return dtype or ftype object in ", returnStmt->get_expr() );
1004 } // if
1005 assignDecl = assignIter->second;
1006 } else if ( ReferenceToType *refType = dynamic_cast< ReferenceToType *>( retval->get_type() ) ) {
1007 ScopedMap< std::string, DeclarationWithType *>::const_iterator assignIter = scopedAssignOps.find( refType->get_name() );
1008 if ( assignIter == scopedAssignOps.end() ) {
1009 throw SemanticError( "Attempt to return dtype or ftype generic object in ", returnStmt->get_expr() );
1010 }
1011 DeclarationWithType *functionDecl = assignIter->second;
1012 // line below cloned from FixFunction.cc
1013 assignDecl = new ObjectDecl( functionDecl->get_name(), functionDecl->get_storageClass(), functionDecl->get_linkage(), 0,
1014 new PointerType( Type::Qualifiers(), functionDecl->get_type()->clone() ), 0 );
1015 assignDecl->set_mangleName( functionDecl->get_mangleName() );
1016 }
1017 assert( assignDecl );
1018
1019 // replace return statement with appropriate assignment to out parameter
1020 ApplicationExpr *assignExpr = new ApplicationExpr( new VariableExpr( assignDecl ) );
1021 Expression *retParm = new NameExpr( retval->get_name() );
1022 retParm->get_results().push_back( new PointerType( Type::Qualifiers(), retval->get_type()->clone() ) );
1023 assignExpr->get_args().push_back( retParm );
1024 assignExpr->get_args().push_back( returnStmt->get_expr() );
1025 stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( assignExpr ) ) );
1026 // } else {
1027 // useRetval = true;
1028 // stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( returnStmt->get_expr() ) ) );
1029 // useRetval = false;
1030 // } // if
1031 returnStmt->set_expr( 0 );
1032 } else {
1033 returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
1034 } // if
1035 return returnStmt;
1036 }
1037
1038 Type * Pass1::mutate( PointerType *pointerType ) {
1039 TyVarMap oldtyVars = scopeTyVars;
1040 makeTyVarMap( pointerType, scopeTyVars );
1041
1042 Type *ret = Mutator::mutate( pointerType );
1043
1044 scopeTyVars = oldtyVars;
1045 return ret;
1046 }
1047
1048 Type * Pass1::mutate( FunctionType *functionType ) {
1049 TyVarMap oldtyVars = scopeTyVars;
1050 makeTyVarMap( functionType, scopeTyVars );
1051
1052 Type *ret = Mutator::mutate( functionType );
1053
1054 scopeTyVars = oldtyVars;
1055 return ret;
1056 }
1057
1058 void Pass1::doBeginScope() {
1059 // push a copy of the current map
1060 adapters.push(adapters.top());
1061 scopedAssignOps.beginScope();
1062 }
1063
1064 void Pass1::doEndScope() {
1065 adapters.pop();
1066 scopedAssignOps.endScope();
1067 }
1068
1069////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
1070
1071 void Pass2::addAdapters( FunctionType *functionType ) {
1072 std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
1073 std::list< FunctionType *> functions;
1074 for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
1075 Type *orig = (*arg)->get_type();
1076 findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
1077 (*arg)->set_type( orig );
1078 }
1079 std::set< std::string > adaptersDone;
1080 for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
1081 std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
1082 if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
1083 std::string adapterName = makeAdapterName( mangleName );
1084 paramList.push_front( new ObjectDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
1085 adaptersDone.insert( adaptersDone.begin(), mangleName );
1086 }
1087 }
1088// deleteAll( functions );
1089 }
1090
1091 template< typename DeclClass >
1092 DeclClass * Pass2::handleDecl( DeclClass *decl, Type *type ) {
1093 DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1094
1095 return ret;
1096 }
1097
1098 DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
1099 return handleDecl( functionDecl, functionDecl->get_functionType() );
1100 }
1101
1102 ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
1103 return handleDecl( objectDecl, objectDecl->get_type() );
1104 }
1105
1106 TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
1107 scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1108 if ( typeDecl->get_base() ) {
1109 return handleDecl( typeDecl, typeDecl->get_base() );
1110 } else {
1111 return Mutator::mutate( typeDecl );
1112 }
1113 }
1114
1115 TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
1116 return handleDecl( typedefDecl, typedefDecl->get_base() );
1117 }
1118
1119 Type * Pass2::mutate( PointerType *pointerType ) {
1120 TyVarMap oldtyVars = scopeTyVars;
1121 makeTyVarMap( pointerType, scopeTyVars );
1122
1123 Type *ret = Mutator::mutate( pointerType );
1124
1125 scopeTyVars = oldtyVars;
1126 return ret;
1127 }
1128
1129 Type *Pass2::mutate( FunctionType *funcType ) {
1130 TyVarMap oldtyVars = scopeTyVars;
1131 makeTyVarMap( funcType, scopeTyVars );
1132
1133 // move polymorphic return type to parameter list
1134 if ( isPolyRet( funcType ) ) {
1135 DeclarationWithType *ret = funcType->get_returnVals().front();
1136 ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
1137 funcType->get_parameters().push_front( ret );
1138 funcType->get_returnVals().pop_front();
1139 }
1140
1141 // add size/align and assertions for type parameters to parameter list
1142 std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
1143 std::list< DeclarationWithType *> inferredParams;
1144 ObjectDecl newObj( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
1145 ObjectDecl newPtr( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0,
1146 new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
1147// ObjectDecl *newFunPtr = new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 );
1148 for ( std::list< TypeDecl *>::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
1149 ObjectDecl *sizeParm, *alignParm;
1150 // add all size and alignment parameters to parameter list
1151 if ( (*tyParm)->get_kind() == TypeDecl::Any ) {
1152 TypeInstType parmType( Type::Qualifiers(), (*tyParm)->get_name(), *tyParm );
1153
1154 sizeParm = newObj.clone();
1155 sizeParm->set_name( sizeofName( &parmType ) );
1156 last = funcType->get_parameters().insert( last, sizeParm );
1157 ++last;
1158
1159 alignParm = newObj.clone();
1160 alignParm->set_name( alignofName( &parmType ) );
1161 last = funcType->get_parameters().insert( last, alignParm );
1162 ++last;
1163 }
1164 // move all assertions into parameter list
1165 for ( std::list< DeclarationWithType *>::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
1166// *assert = (*assert)->acceptMutator( *this );
1167 inferredParams.push_back( *assert );
1168 }
1169 (*tyParm)->get_assertions().clear();
1170 }
1171
1172 // add size/align for generic types to parameter list
1173 std::set< std::string > seenTypes; // sizeofName for generic types we've seen
1174 for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
1175 Type *parmType = (*fnParm)->get_type();
1176 if ( ! dynamic_cast< TypeInstType* >( parmType ) && isPolyType( parmType, scopeTyVars ) ) {
1177 std::string sizeName = sizeofName( parmType );
1178 if ( seenTypes.count( sizeName ) ) continue;
1179
1180 ObjectDecl *sizeParm, *alignParm, *offsetParm;
1181 sizeParm = newObj.clone();
1182 sizeParm->set_name( sizeName );
1183 last = funcType->get_parameters().insert( last, sizeParm );
1184 ++last;
1185
1186 alignParm = newObj.clone();
1187 alignParm->set_name( alignofName( parmType ) );
1188 last = funcType->get_parameters().insert( last, alignParm );
1189 ++last;
1190
1191 if ( dynamic_cast< StructInstType* >( parmType ) ) {
1192 offsetParm = newPtr.clone();
1193 offsetParm->set_name( offsetofName( parmType ) );
1194 last = funcType->get_parameters().insert( last, offsetParm );
1195 ++last;
1196 }
1197
1198 seenTypes.insert( sizeName );
1199 }
1200 }
1201
1202 // splice assertion parameters into parameter list
1203 funcType->get_parameters().splice( last, inferredParams );
1204 addAdapters( funcType );
1205 mutateAll( funcType->get_returnVals(), *this );
1206 mutateAll( funcType->get_parameters(), *this );
1207
1208 scopeTyVars = oldtyVars;
1209 return funcType;
1210 }
1211
1212////////////////////////////////////////// MemberExprFixer ////////////////////////////////////////////////////
1213
1214 template< typename DeclClass >
1215 DeclClass * MemberExprFixer::handleDecl( DeclClass *decl, Type *type ) {
1216 TyVarMap oldtyVars = scopeTyVars;
1217 makeTyVarMap( type, scopeTyVars );
1218
1219 DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1220
1221 scopeTyVars = oldtyVars;
1222 return ret;
1223 }
1224
1225 ObjectDecl * MemberExprFixer::mutate( ObjectDecl *objectDecl ) {
1226 return handleDecl( objectDecl, objectDecl->get_type() );
1227 }
1228
1229 DeclarationWithType * MemberExprFixer::mutate( FunctionDecl *functionDecl ) {
1230 return handleDecl( functionDecl, functionDecl->get_functionType() );
1231 }
1232
1233 TypedefDecl * MemberExprFixer::mutate( TypedefDecl *typedefDecl ) {
1234 return handleDecl( typedefDecl, typedefDecl->get_base() );
1235 }
1236
1237 TypeDecl * MemberExprFixer::mutate( TypeDecl *typeDecl ) {
1238 scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1239 return Mutator::mutate( typeDecl );
1240 }
1241
1242 Type * MemberExprFixer::mutate( PointerType *pointerType ) {
1243 TyVarMap oldtyVars = scopeTyVars;
1244 makeTyVarMap( pointerType, scopeTyVars );
1245
1246 Type *ret = Mutator::mutate( pointerType );
1247
1248 scopeTyVars = oldtyVars;
1249 return ret;
1250 }
1251
1252 Type * MemberExprFixer::mutate( FunctionType *functionType ) {
1253 TyVarMap oldtyVars = scopeTyVars;
1254 makeTyVarMap( functionType, scopeTyVars );
1255
1256 Type *ret = Mutator::mutate( functionType );
1257
1258 scopeTyVars = oldtyVars;
1259 return ret;
1260 }
1261
1262 Statement *MemberExprFixer::mutate( DeclStmt *declStmt ) {
1263 if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) {
1264 if ( isPolyType( objectDecl->get_type(), scopeTyVars ) ) {
1265 // change initialization of a polymorphic value object
1266 // to allocate storage with alloca
1267 Type *declType = objectDecl->get_type();
1268 UntypedExpr *alloc = new UntypedExpr( new NameExpr( "__builtin_alloca" ) );
1269 alloc->get_args().push_back( new NameExpr( sizeofName( declType ) ) );
1270
1271 delete objectDecl->get_init();
1272
1273 std::list<Expression*> designators;
1274 objectDecl->set_init( new SingleInit( alloc, designators ) );
1275 }
1276 }
1277 return Mutator::mutate( declStmt );
1278 }
1279
1280 Expression *MemberExprFixer::mutate( MemberExpr *memberExpr ) {
1281 // mutate, exiting early if no longer MemberExpr
1282 Expression *expr = Mutator::mutate( memberExpr );
1283 memberExpr = dynamic_cast< MemberExpr* >( expr );
1284 if ( ! memberExpr ) return expr;
1285
1286 // get declaration for base struct, exiting early if not found
1287 VariableExpr *varExpr = getBaseVar( memberExpr->get_aggregate() );
1288 if ( ! varExpr ) return memberExpr;
1289 ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( varExpr->get_var() );
1290 if ( ! objectDecl ) return memberExpr;
1291
1292 // only mutate member expressions for polymorphic types
1293 Type *objectType = hasPolyBase( objectDecl->get_type(), scopeTyVars );
1294 if ( ! objectType ) return memberExpr;
1295
1296 // get base aggregate for type so members can be looked up
1297 AggregateDecl *memberBase = 0;
1298 if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
1299 memberBase = structType->get_baseStruct();
1300 } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( objectType ) ) {
1301 memberBase = unionType->get_baseUnion();
1302 } else return memberExpr;
1303
1304 // look up numeric index of member in base aggregate
1305 DeclarationWithType *memberDecl = memberExpr->get_member();
1306 std::list< Declaration* > &baseDecls = memberBase->get_members();
1307 std::list< Declaration* >::const_iterator decl = baseDecls.begin();
1308 unsigned long i = 0;
1309 for( ; decl != baseDecls.end(); ++decl, ++i ) {
1310 if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
1311
1312 if ( DeclarationWithType *declWithType = dynamic_cast< DeclarationWithType* >( *decl ) ) {
1313 if ( memberDecl->get_mangleName() == declWithType->get_mangleName() ) break;
1314 else continue;
1315 } else break;
1316 }
1317 if ( decl == baseDecls.end() ) return memberExpr;
1318
1319 // replace member expression with pointer to base plus offset
1320 // this is in a polymorphic context, so maybe keeping it as a void* is fine?
1321 std::stringstream offset_namer;
1322 offset_namer << i;
1323 ConstantExpr *fieldIndex = new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), offset_namer.str() ) );
1324 UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
1325 fieldOffset->get_args().push_back( new NameExpr( offsetofName( objectType ) ) );
1326 fieldOffset->get_args().push_back( fieldIndex );
1327 UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
1328 fieldLoc->get_args().push_back( memberExpr->get_aggregate() );
1329 fieldLoc->get_args().push_back( fieldOffset );
1330
1331 memberExpr->set_aggregate( 0 );
1332 delete memberExpr;
1333 return fieldLoc;
1334 }
1335
1336////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
1337
1338 template< typename DeclClass >
1339 DeclClass * Pass3::handleDecl( DeclClass *decl, Type *type ) {
1340 TyVarMap oldtyVars = scopeTyVars;
1341 makeTyVarMap( type, scopeTyVars );
1342
1343 DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1344 ScrubTyVars::scrub( decl, scopeTyVars );
1345
1346 scopeTyVars = oldtyVars;
1347 return ret;
1348 }
1349
1350 ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
1351 return handleDecl( objectDecl, objectDecl->get_type() );
1352 }
1353
1354 DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
1355 return handleDecl( functionDecl, functionDecl->get_functionType() );
1356 }
1357
1358 TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
1359 return handleDecl( typedefDecl, typedefDecl->get_base() );
1360 }
1361
1362 TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
1363// Initializer *init = 0;
1364// std::list< Expression *> designators;
1365// scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1366// if ( typeDecl->get_base() ) {
1367// init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
1368// }
1369// return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
1370
1371 scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1372 return Mutator::mutate( typeDecl );
1373 }
1374
1375 Type * Pass3::mutate( PointerType *pointerType ) {
1376 TyVarMap oldtyVars = scopeTyVars;
1377 makeTyVarMap( pointerType, scopeTyVars );
1378
1379 Type *ret = Mutator::mutate( pointerType );
1380
1381 scopeTyVars = oldtyVars;
1382 return ret;
1383 }
1384
1385 Type * Pass3::mutate( FunctionType *functionType ) {
1386 TyVarMap oldtyVars = scopeTyVars;
1387 makeTyVarMap( functionType, scopeTyVars );
1388
1389 Type *ret = Mutator::mutate( functionType );
1390
1391 scopeTyVars = oldtyVars;
1392 return ret;
1393 }
1394 } // anonymous namespace
1395} // namespace GenPoly
1396
1397// Local Variables: //
1398// tab-width: 4 //
1399// mode: c++ //
1400// compile-command: "make install" //
1401// End: //
Note: See TracBrowser for help on using the repository browser.