source: src/GenPoly/Box.cc@ 6d160d7

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 6d160d7 was 32805db, checked in by Aaron Moss <a3moss@…>, 10 years ago

Switched parameter adder over to add for pointer*-to-polymorphic-generic as well
  • Property mode set to 100644
File size: 61.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// 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 std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
373
374 // make a new temporary array
375 Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
376 std::stringstream lenGen;
377 lenGen << baseMembers.size();
378 ConstantExpr *lenExpr = new ConstantExpr( Constant( offsetType->clone(), lenGen.str() ) );
379 ObjectDecl *arrayTemp = makeTemporary( new ArrayType( Type::Qualifiers(), offsetType, lenExpr, false, false ) );
380
381 // build initializer list for temporary
382 std::list< Initializer* > inits;
383 for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
384 DeclarationWithType *memberDecl;
385 if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
386 memberDecl = origMember->clone();
387 } else {
388 memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
389 }
390 inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
391 }
392 arrayTemp->set_init( new ListInit( inits ) );
393
394 // return variable pointing to temporary
395 return new VariableExpr( arrayTemp );
396 }
397
398 void Pass1::passTypeVars( ApplicationExpr *appExpr, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
399 // pass size/align for type variables
400 for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
401 ResolvExpr::EqvClass eqvClass;
402 assert( env );
403 if ( tyParm->second == TypeDecl::Any ) {
404 Type *concrete = env->lookup( tyParm->first );
405 if ( concrete ) {
406 arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
407 arg++;
408 arg = appExpr->get_args().insert( arg, new AlignofExpr( concrete->clone() ) );
409 arg++;
410 } else {
411 throw SemanticError( "unbound type variable in application ", appExpr );
412 } // if
413 } // if
414 } // for
415
416 // add size/align for generic types to parameter list
417 if ( appExpr->get_function()->get_results().empty() ) return;
418 FunctionType *funcType = getFunctionType( appExpr->get_function()->get_results().front() );
419 assert( funcType );
420
421 std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
422 std::list< Expression* >::const_iterator fnArg = arg;
423 std::set< std::string > seenTypes; //< names for generic types we've seen
424 for ( ; fnParm != funcType->get_parameters().end() && fnArg != appExpr->get_args().end(); ++fnParm, ++fnArg ) {
425 Type *polyBase = hasPolyBase( (*fnParm)->get_type(), exprTyVars );
426 if ( polyBase && ! dynamic_cast< TypeInstType* >( polyBase ) ) {
427 std::string sizeName = sizeofName( polyBase );
428 if ( seenTypes.count( sizeName ) ) continue;
429
430 VariableExpr *fnArgBase = getBaseVar( *fnArg );
431 assert( fnArgBase && ! fnArgBase->get_results().empty() );
432 Type *argBaseType = fnArgBase->get_results().front();
433 arg = appExpr->get_args().insert( arg, new SizeofExpr( argBaseType->clone() ) );
434 arg++;
435 arg = appExpr->get_args().insert( arg, new AlignofExpr( argBaseType->clone() ) );
436 arg++;
437 if ( dynamic_cast< StructInstType* >( polyBase ) ) {
438 if ( StructInstType *argBaseStructType = dynamic_cast< StructInstType* >( argBaseType ) ) {
439 arg = appExpr->get_args().insert( arg, makeOffsetArray( argBaseStructType ) );
440 arg++;
441 } else {
442 throw SemanticError( "Cannot pass non-struct type for generic struct" );
443 }
444 }
445
446 seenTypes.insert( sizeName );
447 }
448 }
449 }
450
451 ObjectDecl *Pass1::makeTemporary( Type *type ) {
452 ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, type, 0 );
453 stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
454 return newObj;
455 }
456
457 Expression *Pass1::addRetParam( ApplicationExpr *appExpr, FunctionType *function, Type *retType, std::list< Expression *>::iterator &arg ) {
458 // ***** Code Removal ***** After introducing a temporary variable for all return expressions, the following code appears superfluous.
459 // if ( useRetval ) {
460 // assert( retval );
461 // arg = appExpr->get_args().insert( arg, new VariableExpr( retval ) );
462 // arg++;
463 // } else {
464
465 // Create temporary to hold return value of polymorphic function and produce that temporary as a result
466 // using a comma expression. Possibly change comma expression into statement expression "{}" for multiple
467 // return values.
468 ObjectDecl *newObj = makeTemporary( retType->clone() );
469 Expression *paramExpr = new VariableExpr( newObj );
470 // If the type of the temporary is not polymorphic, box temporary by taking its address; otherwise the
471 // temporary is already boxed and can be used directly.
472 if ( ! isPolyType( newObj->get_type(), scopeTyVars, env ) ) {
473 paramExpr = new AddressExpr( paramExpr );
474 } // if
475 arg = appExpr->get_args().insert( arg, paramExpr ); // add argument to function call
476 arg++;
477 // Build a comma expression to call the function and emulate a normal return.
478 CommaExpr *commaExpr = new CommaExpr( appExpr, new VariableExpr( newObj ) );
479 commaExpr->set_env( appExpr->get_env() );
480 appExpr->set_env( 0 );
481 return commaExpr;
482 // } // if
483 // return appExpr;
484 }
485
486 void Pass1::replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params ) {
487 for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
488 TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
489 assert(paramType && "Aggregate parameters should be type expressions");
490 paramType->set_type( replaceWithConcrete( appExpr, paramType->get_type(), false ) );
491 }
492 }
493
494 Type *Pass1::replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone ) {
495 if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) {
496 Type *concrete = env->lookup( typeInst->get_name() );
497 if ( concrete == 0 ) {
498 throw SemanticError( "Unbound type variable " + typeInst->get_name() + " in ", appExpr );
499 } // if
500 return concrete;
501 } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
502 if ( doClone ) {
503 structType = structType->clone();
504 }
505 replaceParametersWithConcrete( appExpr, structType->get_parameters() );
506 return structType;
507 } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
508 if ( doClone ) {
509 unionType = unionType->clone();
510 }
511 replaceParametersWithConcrete( appExpr, unionType->get_parameters() );
512 return unionType;
513 }
514 return type;
515 }
516
517 Expression *Pass1::addPolyRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg ) {
518 assert( env );
519 Type *concrete = replaceWithConcrete( appExpr, polyType );
520 return addRetParam( appExpr, function, concrete, arg );
521 }
522
523 Expression *Pass1::applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
524 Expression *ret = appExpr;
525 if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
526 ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
527 } // if
528 std::string mangleName = mangleAdapterName( function, tyVars );
529 std::string adapterName = makeAdapterName( mangleName );
530
531 appExpr->get_args().push_front( appExpr->get_function() );
532 appExpr->set_function( new NameExpr( adapterName ) );
533
534 return ret;
535 }
536
537 void Pass1::boxParam( Type *param, Expression *&arg, const TyVarMap &exprTyVars ) {
538 assert( ! arg->get_results().empty() );
539 if ( isPolyType( param, exprTyVars ) ) {
540 if ( dynamic_cast< TypeInstType *>( arg->get_results().front() ) ) {
541 // if the argument's type is a type parameter, we don't need to box again!
542 return;
543 } else if ( arg->get_results().front()->get_isLvalue() ) {
544 // VariableExpr and MemberExpr are lvalues
545 arg = new AddressExpr( arg );
546 } else {
547 ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, arg->get_results().front()->clone(), 0 );
548 newObj->get_type()->get_qualifiers() = Type::Qualifiers(); // TODO: is this right???
549 stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
550 UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
551 assign->get_args().push_back( new VariableExpr( newObj ) );
552 assign->get_args().push_back( arg );
553 stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
554 arg = new AddressExpr( new VariableExpr( newObj ) );
555 } // if
556 } // if
557 }
558
559 void addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars ) {
560 Type *newType = formal->clone();
561 std::list< FunctionType *> functions;
562 // instead of functions needing adapters, this really ought to look for
563 // any function mentioning a polymorphic type
564 findAndReplaceFunction( newType, functions, tyVars, needsAdapter );
565 if ( ! functions.empty() ) {
566 actual = new CastExpr( actual, newType );
567 } else {
568 delete newType;
569 } // if
570 }
571
572 void Pass1::boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
573 for ( std::list< DeclarationWithType *>::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
574 assert( arg != appExpr->get_args().end() );
575 addCast( *arg, (*param)->get_type(), exprTyVars );
576 boxParam( (*param)->get_type(), *arg, exprTyVars );
577 } // for
578 }
579
580 void Pass1::addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
581 std::list< Expression *>::iterator cur = arg;
582 for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
583 for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
584 InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
585 assert( inferParam != appExpr->get_inferParams().end() && "NOTE: Explicit casts of polymorphic functions to compatible monomorphic functions are currently unsupported" );
586 Expression *newExpr = inferParam->second.expr->clone();
587 addCast( newExpr, (*assert)->get_type(), tyVars );
588 boxParam( (*assert)->get_type(), newExpr, tyVars );
589 appExpr->get_args().insert( cur, newExpr );
590 } // for
591 } // for
592 }
593
594 void makeRetParm( FunctionType *funcType ) {
595 DeclarationWithType *retParm = funcType->get_returnVals().front();
596
597 // make a new parameter that is a pointer to the type of the old return value
598 retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
599 funcType->get_parameters().push_front( retParm );
600
601 // we don't need the return value any more
602 funcType->get_returnVals().clear();
603 }
604
605 FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars ) {
606 // actually make the adapter type
607 FunctionType *adapter = adaptee->clone();
608 if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
609 makeRetParm( adapter );
610 } // if
611 adapter->get_parameters().push_front( new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
612 return adapter;
613 }
614
615 Expression *makeAdapterArg( DeclarationWithType *param, DeclarationWithType *arg, DeclarationWithType *realParam, const TyVarMap &tyVars ) {
616 assert( param );
617 assert( arg );
618 if ( isPolyType( realParam->get_type(), tyVars ) ) {
619 if ( dynamic_cast<TypeInstType *>(arg->get_type()) == NULL ) {
620 UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
621 deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
622 deref->get_results().push_back( arg->get_type()->clone() );
623 return deref;
624 } // if
625 } // if
626 return new VariableExpr( param );
627 }
628
629 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 ) {
630 UniqueName paramNamer( "_p" );
631 for ( ; param != paramEnd; ++param, ++arg, ++realParam ) {
632 if ( (*param)->get_name() == "" ) {
633 (*param)->set_name( paramNamer.newName() );
634 (*param)->set_linkage( LinkageSpec::C );
635 } // if
636 adapteeApp->get_args().push_back( makeAdapterArg( *param, *arg, *realParam, tyVars ) );
637 } // for
638 }
639
640
641
642 FunctionDecl *Pass1::makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) {
643 FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
644 adapterType = ScrubTyVars::scrub( adapterType, tyVars );
645 DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
646 adapteeDecl->set_name( "_adaptee" );
647 ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
648 Statement *bodyStmt;
649
650 std::list< TypeDecl *>::iterator tyArg = realType->get_forall().begin();
651 std::list< TypeDecl *>::iterator tyParam = adapterType->get_forall().begin();
652 std::list< TypeDecl *>::iterator realTyParam = adaptee->get_forall().begin();
653 for ( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
654 assert( tyArg != realType->get_forall().end() );
655 std::list< DeclarationWithType *>::iterator assertArg = (*tyArg)->get_assertions().begin();
656 std::list< DeclarationWithType *>::iterator assertParam = (*tyParam)->get_assertions().begin();
657 std::list< DeclarationWithType *>::iterator realAssertParam = (*realTyParam)->get_assertions().begin();
658 for ( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
659 assert( assertArg != (*tyArg)->get_assertions().end() );
660 adapteeApp->get_args().push_back( makeAdapterArg( *assertParam, *assertArg, *realAssertParam, tyVars ) );
661 } // for
662 } // for
663
664 std::list< DeclarationWithType *>::iterator arg = realType->get_parameters().begin();
665 std::list< DeclarationWithType *>::iterator param = adapterType->get_parameters().begin();
666 std::list< DeclarationWithType *>::iterator realParam = adaptee->get_parameters().begin();
667 param++; // skip adaptee parameter
668 if ( realType->get_returnVals().empty() ) {
669 addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
670 bodyStmt = new ExprStmt( noLabels, adapteeApp );
671 } else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
672 if ( (*param)->get_name() == "" ) {
673 (*param)->set_name( "_ret" );
674 (*param)->set_linkage( LinkageSpec::C );
675 } // if
676 UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
677 UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
678 deref->get_args().push_back( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
679 assign->get_args().push_back( deref );
680 addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
681 assign->get_args().push_back( adapteeApp );
682 bodyStmt = new ExprStmt( noLabels, assign );
683 } else {
684 // adapter for a function that returns a monomorphic value
685 addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
686 bodyStmt = new ReturnStmt( noLabels, adapteeApp );
687 } // if
688 CompoundStmt *adapterBody = new CompoundStmt( noLabels );
689 adapterBody->get_kids().push_back( bodyStmt );
690 std::string adapterName = makeAdapterName( mangleName );
691 return new FunctionDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, adapterType, adapterBody, false, false );
692 }
693
694 void Pass1::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) {
695 // collect a list of function types passed as parameters or implicit parameters (assertions)
696 std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
697 std::list< FunctionType *> functions;
698 for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
699 for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
700 findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
701 } // for
702 } // for
703 for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
704 findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
705 } // for
706
707 // parameter function types for which an appropriate adapter has been generated. we cannot use the types
708 // after applying substitutions, since two different parameter types may be unified to the same type
709 std::set< std::string > adaptersDone;
710
711 for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
712 FunctionType *originalFunction = (*funType)->clone();
713 FunctionType *realFunction = (*funType)->clone();
714 std::string mangleName = SymTab::Mangler::mangle( realFunction );
715
716 // only attempt to create an adapter or pass one as a parameter if we haven't already done so for this
717 // pre-substitution parameter function type.
718 if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
719 adaptersDone.insert( adaptersDone.begin(), mangleName );
720
721 // apply substitution to type variables to figure out what the adapter's type should look like
722 assert( env );
723 env->apply( realFunction );
724 mangleName = SymTab::Mangler::mangle( realFunction );
725 mangleName += makePolyMonoSuffix( originalFunction, exprTyVars );
726
727 AdapterMap & adapters = Pass1::adapters.top();
728 AdapterMap::iterator adapter = adapters.find( mangleName );
729 if ( adapter == adapters.end() ) {
730 // adapter has not been created yet in the current scope, so define it
731 FunctionDecl *newAdapter = makeAdapter( *funType, realFunction, mangleName, exprTyVars );
732 adapter = adapters.insert( adapters.begin(), std::pair< std::string, DeclarationWithType *>( mangleName, newAdapter ) );
733 stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
734 } // if
735 assert( adapter != adapters.end() );
736
737 // add the appropriate adapter as a parameter
738 appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
739 } // if
740 } // for
741 } // passAdapters
742
743 Expression *makeIncrDecrExpr( ApplicationExpr *appExpr, Type *polyType, bool isIncr ) {
744 NameExpr *opExpr;
745 if ( isIncr ) {
746 opExpr = new NameExpr( "?+=?" );
747 } else {
748 opExpr = new NameExpr( "?-=?" );
749 } // if
750 UntypedExpr *addAssign = new UntypedExpr( opExpr );
751 if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
752 addAssign->get_args().push_back( address->get_arg() );
753 } else {
754 addAssign->get_args().push_back( appExpr->get_args().front() );
755 } // if
756 addAssign->get_args().push_back( new NameExpr( sizeofName( polyType ) ) );
757 addAssign->get_results().front() = appExpr->get_results().front()->clone();
758 if ( appExpr->get_env() ) {
759 addAssign->set_env( appExpr->get_env() );
760 appExpr->set_env( 0 );
761 } // if
762 appExpr->get_args().clear();
763 delete appExpr;
764 return addAssign;
765 }
766
767 Expression *Pass1::handleIntrinsics( ApplicationExpr *appExpr ) {
768 if ( VariableExpr *varExpr = dynamic_cast< VariableExpr *>( appExpr->get_function() ) ) {
769 if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
770 if ( varExpr->get_var()->get_name() == "?[?]" ) {
771 assert( ! appExpr->get_results().empty() );
772 assert( appExpr->get_args().size() == 2 );
773 Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
774 Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
775 assert( ! baseType1 || ! baseType2 ); // the arguments cannot both be polymorphic pointers
776 UntypedExpr *ret = 0;
777 if ( baseType1 || baseType2 ) { // one of the arguments is a polymorphic pointer
778 ret = new UntypedExpr( new NameExpr( "?+?" ) );
779 } // if
780 if ( baseType1 ) {
781 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
782 multiply->get_args().push_back( appExpr->get_args().back() );
783 multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
784 ret->get_args().push_back( appExpr->get_args().front() );
785 ret->get_args().push_back( multiply );
786 } else if ( baseType2 ) {
787 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
788 multiply->get_args().push_back( appExpr->get_args().front() );
789 multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
790 ret->get_args().push_back( multiply );
791 ret->get_args().push_back( appExpr->get_args().back() );
792 } // if
793 if ( baseType1 || baseType2 ) {
794 ret->get_results().push_front( appExpr->get_results().front()->clone() );
795 if ( appExpr->get_env() ) {
796 ret->set_env( appExpr->get_env() );
797 appExpr->set_env( 0 );
798 } // if
799 appExpr->get_args().clear();
800 delete appExpr;
801 return ret;
802 } // if
803 } else if ( varExpr->get_var()->get_name() == "*?" ) {
804 assert( ! appExpr->get_results().empty() );
805 assert( ! appExpr->get_args().empty() );
806 if ( isPolyType( appExpr->get_results().front(), scopeTyVars, env ) ) {
807 Expression *ret = appExpr->get_args().front();
808 delete ret->get_results().front();
809 ret->get_results().front() = appExpr->get_results().front()->clone();
810 if ( appExpr->get_env() ) {
811 ret->set_env( appExpr->get_env() );
812 appExpr->set_env( 0 );
813 } // if
814 appExpr->get_args().clear();
815 delete appExpr;
816 return ret;
817 } // if
818 } else if ( varExpr->get_var()->get_name() == "?++" || varExpr->get_var()->get_name() == "?--" ) {
819 assert( ! appExpr->get_results().empty() );
820 assert( appExpr->get_args().size() == 1 );
821 if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
822 Type *tempType = appExpr->get_results().front()->clone();
823 if ( env ) {
824 env->apply( tempType );
825 } // if
826 ObjectDecl *newObj = makeTemporary( tempType );
827 VariableExpr *tempExpr = new VariableExpr( newObj );
828 UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
829 assignExpr->get_args().push_back( tempExpr->clone() );
830 if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
831 assignExpr->get_args().push_back( address->get_arg()->clone() );
832 } else {
833 assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
834 } // if
835 CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) );
836 return new CommaExpr( firstComma, tempExpr );
837 } // if
838 } else if ( varExpr->get_var()->get_name() == "++?" || varExpr->get_var()->get_name() == "--?" ) {
839 assert( ! appExpr->get_results().empty() );
840 assert( appExpr->get_args().size() == 1 );
841 if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
842 return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" );
843 } // if
844 } else if ( varExpr->get_var()->get_name() == "?+?" || varExpr->get_var()->get_name() == "?-?" ) {
845 assert( ! appExpr->get_results().empty() );
846 assert( appExpr->get_args().size() == 2 );
847 Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
848 Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
849 if ( baseType1 && baseType2 ) {
850 UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
851 divide->get_args().push_back( appExpr );
852 divide->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
853 divide->get_results().push_front( appExpr->get_results().front()->clone() );
854 if ( appExpr->get_env() ) {
855 divide->set_env( appExpr->get_env() );
856 appExpr->set_env( 0 );
857 } // if
858 return divide;
859 } else if ( baseType1 ) {
860 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
861 multiply->get_args().push_back( appExpr->get_args().back() );
862 multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
863 appExpr->get_args().back() = multiply;
864 } else if ( baseType2 ) {
865 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
866 multiply->get_args().push_back( appExpr->get_args().front() );
867 multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
868 appExpr->get_args().front() = multiply;
869 } // if
870 } else if ( varExpr->get_var()->get_name() == "?+=?" || varExpr->get_var()->get_name() == "?-=?" ) {
871 assert( ! appExpr->get_results().empty() );
872 assert( appExpr->get_args().size() == 2 );
873 Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env );
874 if ( baseType ) {
875 UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
876 multiply->get_args().push_back( appExpr->get_args().back() );
877 multiply->get_args().push_back( new NameExpr( sizeofName( baseType ) ) );
878 appExpr->get_args().back() = multiply;
879 } // if
880 } // if
881 return appExpr;
882 } // if
883 } // if
884 return 0;
885 }
886
887 Expression *Pass1::mutate( ApplicationExpr *appExpr ) {
888 // std::cerr << "mutate appExpr: ";
889 // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
890 // std::cerr << i->first << " ";
891 // }
892 // std::cerr << "\n";
893 bool oldUseRetval = useRetval;
894 useRetval = false;
895 appExpr->get_function()->acceptMutator( *this );
896 mutateAll( appExpr->get_args(), *this );
897 useRetval = oldUseRetval;
898
899 assert( ! appExpr->get_function()->get_results().empty() );
900 PointerType *pointer = dynamic_cast< PointerType *>( appExpr->get_function()->get_results().front() );
901 assert( pointer );
902 FunctionType *function = dynamic_cast< FunctionType *>( pointer->get_base() );
903 assert( function );
904
905 if ( Expression *newExpr = handleIntrinsics( appExpr ) ) {
906 return newExpr;
907 } // if
908
909 Expression *ret = appExpr;
910
911 std::list< Expression *>::iterator arg = appExpr->get_args().begin();
912 std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin();
913
914 if ( ReferenceToType *polyType = isPolyRet( function ) ) {
915 ret = addPolyRetParam( appExpr, function, polyType, arg );
916 } else if ( needsAdapter( function, scopeTyVars ) ) {
917 // std::cerr << "needs adapter: ";
918 // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
919 // std::cerr << i->first << " ";
920 // }
921 // std::cerr << "\n";
922 // change the application so it calls the adapter rather than the passed function
923 ret = applyAdapter( appExpr, function, arg, scopeTyVars );
924 } // if
925 arg = appExpr->get_args().begin();
926
927 TyVarMap exprTyVars;
928 makeTyVarMap( function, exprTyVars );
929
930 passTypeVars( appExpr, arg, exprTyVars );
931 addInferredParams( appExpr, function, arg, exprTyVars );
932
933 arg = paramBegin;
934
935 boxParams( appExpr, function, arg, exprTyVars );
936
937 passAdapters( appExpr, function, exprTyVars );
938
939 return ret;
940 }
941
942 Expression *Pass1::mutate( UntypedExpr *expr ) {
943 if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
944 if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
945 if ( name->get_name() == "*?" ) {
946 Expression *ret = expr->get_args().front();
947 expr->get_args().clear();
948 delete expr;
949 return ret->acceptMutator( *this );
950 } // if
951 } // if
952 } // if
953 return PolyMutator::mutate( expr );
954 }
955
956 Expression *Pass1::mutate( AddressExpr *addrExpr ) {
957 assert( ! addrExpr->get_arg()->get_results().empty() );
958
959 bool needs = false;
960 if ( UntypedExpr *expr = dynamic_cast< UntypedExpr *>( addrExpr->get_arg() ) ) {
961 if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
962 if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
963 if ( name->get_name() == "*?" ) {
964 if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
965 assert( ! appExpr->get_function()->get_results().empty() );
966 PointerType *pointer = dynamic_cast< PointerType *>( appExpr->get_function()->get_results().front() );
967 assert( pointer );
968 FunctionType *function = dynamic_cast< FunctionType *>( pointer->get_base() );
969 assert( function );
970 needs = needsAdapter( function, scopeTyVars );
971 } // if
972 } // if
973 } // if
974 } // if
975 } // if
976 addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
977 if ( isPolyType( addrExpr->get_arg()->get_results().front(), scopeTyVars, env ) || needs ) {
978 Expression *ret = addrExpr->get_arg();
979 delete ret->get_results().front();
980 ret->get_results().front() = addrExpr->get_results().front()->clone();
981 addrExpr->set_arg( 0 );
982 delete addrExpr;
983 return ret;
984 } else {
985 return addrExpr;
986 } // if
987 }
988
989 Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
990 if ( retval && returnStmt->get_expr() ) {
991 assert( ! returnStmt->get_expr()->get_results().empty() );
992 // ***** Code Removal ***** After introducing a temporary variable for all return expressions, the following code appears superfluous.
993 // if ( returnStmt->get_expr()->get_results().front()->get_isLvalue() ) {
994 // by this point, a cast expr on a polymorphic return value is redundant
995 while ( CastExpr *castExpr = dynamic_cast< CastExpr *>( returnStmt->get_expr() ) ) {
996 returnStmt->set_expr( castExpr->get_arg() );
997 returnStmt->get_expr()->set_env( castExpr->get_env() );
998 castExpr->set_env( 0 );
999 castExpr->set_arg( 0 );
1000 delete castExpr;
1001 } //while
1002
1003 // find assignment operator for (polymorphic) return type
1004 DeclarationWithType *assignDecl = 0;
1005 if ( TypeInstType *typeInst = dynamic_cast< TypeInstType *>( retval->get_type() ) ) {
1006 std::map< std::string, DeclarationWithType *>::const_iterator assignIter = assignOps.find( typeInst->get_name() );
1007 if ( assignIter == assignOps.end() ) {
1008 throw SemanticError( "Attempt to return dtype or ftype object in ", returnStmt->get_expr() );
1009 } // if
1010 assignDecl = assignIter->second;
1011 } else if ( ReferenceToType *refType = dynamic_cast< ReferenceToType *>( retval->get_type() ) ) {
1012 ScopedMap< std::string, DeclarationWithType *>::const_iterator assignIter = scopedAssignOps.find( refType->get_name() );
1013 if ( assignIter == scopedAssignOps.end() ) {
1014 throw SemanticError( "Attempt to return dtype or ftype generic object in ", returnStmt->get_expr() );
1015 }
1016 DeclarationWithType *functionDecl = assignIter->second;
1017 // line below cloned from FixFunction.cc
1018 assignDecl = new ObjectDecl( functionDecl->get_name(), functionDecl->get_storageClass(), functionDecl->get_linkage(), 0,
1019 new PointerType( Type::Qualifiers(), functionDecl->get_type()->clone() ), 0 );
1020 assignDecl->set_mangleName( functionDecl->get_mangleName() );
1021 }
1022 assert( assignDecl );
1023
1024 // replace return statement with appropriate assignment to out parameter
1025 ApplicationExpr *assignExpr = new ApplicationExpr( new VariableExpr( assignDecl ) );
1026 Expression *retParm = new NameExpr( retval->get_name() );
1027 retParm->get_results().push_back( new PointerType( Type::Qualifiers(), retval->get_type()->clone() ) );
1028 assignExpr->get_args().push_back( retParm );
1029 assignExpr->get_args().push_back( returnStmt->get_expr() );
1030 stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( assignExpr ) ) );
1031 // } else {
1032 // useRetval = true;
1033 // stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( returnStmt->get_expr() ) ) );
1034 // useRetval = false;
1035 // } // if
1036 returnStmt->set_expr( 0 );
1037 } else {
1038 returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
1039 } // if
1040 return returnStmt;
1041 }
1042
1043 Type * Pass1::mutate( PointerType *pointerType ) {
1044 TyVarMap oldtyVars = scopeTyVars;
1045 makeTyVarMap( pointerType, scopeTyVars );
1046
1047 Type *ret = Mutator::mutate( pointerType );
1048
1049 scopeTyVars = oldtyVars;
1050 return ret;
1051 }
1052
1053 Type * Pass1::mutate( FunctionType *functionType ) {
1054 TyVarMap oldtyVars = scopeTyVars;
1055 makeTyVarMap( functionType, scopeTyVars );
1056
1057 Type *ret = Mutator::mutate( functionType );
1058
1059 scopeTyVars = oldtyVars;
1060 return ret;
1061 }
1062
1063 void Pass1::doBeginScope() {
1064 // push a copy of the current map
1065 adapters.push(adapters.top());
1066 scopedAssignOps.beginScope();
1067 }
1068
1069 void Pass1::doEndScope() {
1070 adapters.pop();
1071 scopedAssignOps.endScope();
1072 }
1073
1074////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
1075
1076 void Pass2::addAdapters( FunctionType *functionType ) {
1077 std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
1078 std::list< FunctionType *> functions;
1079 for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
1080 Type *orig = (*arg)->get_type();
1081 findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
1082 (*arg)->set_type( orig );
1083 }
1084 std::set< std::string > adaptersDone;
1085 for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
1086 std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
1087 if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
1088 std::string adapterName = makeAdapterName( mangleName );
1089 paramList.push_front( new ObjectDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
1090 adaptersDone.insert( adaptersDone.begin(), mangleName );
1091 }
1092 }
1093// deleteAll( functions );
1094 }
1095
1096 template< typename DeclClass >
1097 DeclClass * Pass2::handleDecl( DeclClass *decl, Type *type ) {
1098 DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1099
1100 return ret;
1101 }
1102
1103 DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
1104 return handleDecl( functionDecl, functionDecl->get_functionType() );
1105 }
1106
1107 ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
1108 return handleDecl( objectDecl, objectDecl->get_type() );
1109 }
1110
1111 TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
1112 scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1113 if ( typeDecl->get_base() ) {
1114 return handleDecl( typeDecl, typeDecl->get_base() );
1115 } else {
1116 return Mutator::mutate( typeDecl );
1117 }
1118 }
1119
1120 TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
1121 return handleDecl( typedefDecl, typedefDecl->get_base() );
1122 }
1123
1124 Type * Pass2::mutate( PointerType *pointerType ) {
1125 TyVarMap oldtyVars = scopeTyVars;
1126 makeTyVarMap( pointerType, scopeTyVars );
1127
1128 Type *ret = Mutator::mutate( pointerType );
1129
1130 scopeTyVars = oldtyVars;
1131 return ret;
1132 }
1133
1134 Type *Pass2::mutate( FunctionType *funcType ) {
1135 TyVarMap oldtyVars = scopeTyVars;
1136 makeTyVarMap( funcType, scopeTyVars );
1137
1138 // move polymorphic return type to parameter list
1139 if ( isPolyRet( funcType ) ) {
1140 DeclarationWithType *ret = funcType->get_returnVals().front();
1141 ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
1142 funcType->get_parameters().push_front( ret );
1143 funcType->get_returnVals().pop_front();
1144 }
1145
1146 // add size/align and assertions for type parameters to parameter list
1147 std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
1148 std::list< DeclarationWithType *> inferredParams;
1149 ObjectDecl newObj( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
1150 ObjectDecl newPtr( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0,
1151 new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
1152// ObjectDecl *newFunPtr = new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 );
1153 for ( std::list< TypeDecl *>::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
1154 ObjectDecl *sizeParm, *alignParm;
1155 // add all size and alignment parameters to parameter list
1156 if ( (*tyParm)->get_kind() == TypeDecl::Any ) {
1157 TypeInstType parmType( Type::Qualifiers(), (*tyParm)->get_name(), *tyParm );
1158
1159 sizeParm = newObj.clone();
1160 sizeParm->set_name( sizeofName( &parmType ) );
1161 last = funcType->get_parameters().insert( last, sizeParm );
1162 ++last;
1163
1164 alignParm = newObj.clone();
1165 alignParm->set_name( alignofName( &parmType ) );
1166 last = funcType->get_parameters().insert( last, alignParm );
1167 ++last;
1168 }
1169 // move all assertions into parameter list
1170 for ( std::list< DeclarationWithType *>::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
1171// *assert = (*assert)->acceptMutator( *this );
1172 inferredParams.push_back( *assert );
1173 }
1174 (*tyParm)->get_assertions().clear();
1175 }
1176
1177 // add size/align for generic types to parameter list
1178 std::set< std::string > seenTypes; // sizeofName for generic types we've seen
1179 for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
1180 Type *polyBase = hasPolyBase( (*fnParm)->get_type(), scopeTyVars );
1181 if ( polyBase && ! dynamic_cast< TypeInstType* >( polyBase ) ) {
1182 std::string sizeName = sizeofName( polyBase );
1183 if ( seenTypes.count( sizeName ) ) continue;
1184
1185 ObjectDecl *sizeParm, *alignParm, *offsetParm;
1186 sizeParm = newObj.clone();
1187 sizeParm->set_name( sizeName );
1188 last = funcType->get_parameters().insert( last, sizeParm );
1189 ++last;
1190
1191 alignParm = newObj.clone();
1192 alignParm->set_name( alignofName( polyBase ) );
1193 last = funcType->get_parameters().insert( last, alignParm );
1194 ++last;
1195
1196 if ( dynamic_cast< StructInstType* >( polyBase ) ) {
1197 offsetParm = newPtr.clone();
1198 offsetParm->set_name( offsetofName( polyBase ) );
1199 last = funcType->get_parameters().insert( last, offsetParm );
1200 ++last;
1201 }
1202
1203 seenTypes.insert( sizeName );
1204 }
1205 }
1206
1207 // splice assertion parameters into parameter list
1208 funcType->get_parameters().splice( last, inferredParams );
1209 addAdapters( funcType );
1210 mutateAll( funcType->get_returnVals(), *this );
1211 mutateAll( funcType->get_parameters(), *this );
1212
1213 scopeTyVars = oldtyVars;
1214 return funcType;
1215 }
1216
1217////////////////////////////////////////// MemberExprFixer ////////////////////////////////////////////////////
1218
1219 template< typename DeclClass >
1220 DeclClass * MemberExprFixer::handleDecl( DeclClass *decl, Type *type ) {
1221 TyVarMap oldtyVars = scopeTyVars;
1222 makeTyVarMap( type, scopeTyVars );
1223
1224 DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1225
1226 scopeTyVars = oldtyVars;
1227 return ret;
1228 }
1229
1230 ObjectDecl * MemberExprFixer::mutate( ObjectDecl *objectDecl ) {
1231 return handleDecl( objectDecl, objectDecl->get_type() );
1232 }
1233
1234 DeclarationWithType * MemberExprFixer::mutate( FunctionDecl *functionDecl ) {
1235 return handleDecl( functionDecl, functionDecl->get_functionType() );
1236 }
1237
1238 TypedefDecl * MemberExprFixer::mutate( TypedefDecl *typedefDecl ) {
1239 return handleDecl( typedefDecl, typedefDecl->get_base() );
1240 }
1241
1242 TypeDecl * MemberExprFixer::mutate( TypeDecl *typeDecl ) {
1243 scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1244 return Mutator::mutate( typeDecl );
1245 }
1246
1247 Type * MemberExprFixer::mutate( PointerType *pointerType ) {
1248 TyVarMap oldtyVars = scopeTyVars;
1249 makeTyVarMap( pointerType, scopeTyVars );
1250
1251 Type *ret = Mutator::mutate( pointerType );
1252
1253 scopeTyVars = oldtyVars;
1254 return ret;
1255 }
1256
1257 Type * MemberExprFixer::mutate( FunctionType *functionType ) {
1258 TyVarMap oldtyVars = scopeTyVars;
1259 makeTyVarMap( functionType, scopeTyVars );
1260
1261 Type *ret = Mutator::mutate( functionType );
1262
1263 scopeTyVars = oldtyVars;
1264 return ret;
1265 }
1266
1267 Statement *MemberExprFixer::mutate( DeclStmt *declStmt ) {
1268 if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) {
1269 if ( isPolyType( objectDecl->get_type(), scopeTyVars ) ) {
1270 // change initialization of a polymorphic value object
1271 // to allocate storage with alloca
1272 Type *declType = objectDecl->get_type();
1273 UntypedExpr *alloc = new UntypedExpr( new NameExpr( "__builtin_alloca" ) );
1274 alloc->get_args().push_back( new NameExpr( sizeofName( declType ) ) );
1275
1276 delete objectDecl->get_init();
1277
1278 std::list<Expression*> designators;
1279 objectDecl->set_init( new SingleInit( alloc, designators ) );
1280 }
1281 }
1282 return Mutator::mutate( declStmt );
1283 }
1284
1285 Expression *MemberExprFixer::mutate( MemberExpr *memberExpr ) {
1286 // mutate, exiting early if no longer MemberExpr
1287 Expression *expr = Mutator::mutate( memberExpr );
1288 memberExpr = dynamic_cast< MemberExpr* >( expr );
1289 if ( ! memberExpr ) return expr;
1290
1291 // get declaration for base struct, exiting early if not found
1292 VariableExpr *varExpr = getBaseVar( memberExpr->get_aggregate() );
1293 if ( ! varExpr ) return memberExpr;
1294 ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( varExpr->get_var() );
1295 if ( ! objectDecl ) return memberExpr;
1296
1297 // only mutate member expressions for polymorphic types
1298 Type *objectType = hasPolyBase( objectDecl->get_type(), scopeTyVars );
1299 if ( ! objectType ) return memberExpr;
1300
1301 // get base aggregate for type so members can be looked up
1302 AggregateDecl *memberBase = 0;
1303 if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
1304 memberBase = structType->get_baseStruct();
1305 } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( objectType ) ) {
1306 memberBase = unionType->get_baseUnion();
1307 } else return memberExpr;
1308
1309 // look up numeric index of member in base aggregate
1310 DeclarationWithType *memberDecl = memberExpr->get_member();
1311 std::list< Declaration* > &baseDecls = memberBase->get_members();
1312 std::list< Declaration* >::const_iterator decl = baseDecls.begin();
1313 unsigned long i = 0;
1314 for( ; decl != baseDecls.end(); ++decl, ++i ) {
1315 if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
1316
1317 if ( DeclarationWithType *declWithType = dynamic_cast< DeclarationWithType* >( *decl ) ) {
1318 if ( memberDecl->get_mangleName() == declWithType->get_mangleName() ) break;
1319 else continue;
1320 } else break;
1321 }
1322 if ( decl == baseDecls.end() ) return memberExpr;
1323
1324 // replace member expression with pointer to base plus offset
1325 // this is in a polymorphic context, so maybe keeping it as a void* is fine?
1326 std::stringstream offset_namer;
1327 offset_namer << i;
1328 ConstantExpr *fieldIndex = new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), offset_namer.str() ) );
1329 UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
1330 fieldOffset->get_args().push_back( new NameExpr( offsetofName( objectType ) ) );
1331 fieldOffset->get_args().push_back( fieldIndex );
1332 UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
1333 fieldLoc->get_args().push_back( memberExpr->get_aggregate() );
1334 fieldLoc->get_args().push_back( fieldOffset );
1335
1336 memberExpr->set_aggregate( 0 );
1337 delete memberExpr;
1338 return fieldLoc;
1339 }
1340
1341////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
1342
1343 template< typename DeclClass >
1344 DeclClass * Pass3::handleDecl( DeclClass *decl, Type *type ) {
1345 TyVarMap oldtyVars = scopeTyVars;
1346 makeTyVarMap( type, scopeTyVars );
1347
1348 DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1349 ScrubTyVars::scrub( decl, scopeTyVars );
1350
1351 scopeTyVars = oldtyVars;
1352 return ret;
1353 }
1354
1355 ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
1356 return handleDecl( objectDecl, objectDecl->get_type() );
1357 }
1358
1359 DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
1360 return handleDecl( functionDecl, functionDecl->get_functionType() );
1361 }
1362
1363 TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
1364 return handleDecl( typedefDecl, typedefDecl->get_base() );
1365 }
1366
1367 TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
1368// Initializer *init = 0;
1369// std::list< Expression *> designators;
1370// scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1371// if ( typeDecl->get_base() ) {
1372// init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
1373// }
1374// return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
1375
1376 scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1377 return Mutator::mutate( typeDecl );
1378 }
1379
1380 Type * Pass3::mutate( PointerType *pointerType ) {
1381 TyVarMap oldtyVars = scopeTyVars;
1382 makeTyVarMap( pointerType, scopeTyVars );
1383
1384 Type *ret = Mutator::mutate( pointerType );
1385
1386 scopeTyVars = oldtyVars;
1387 return ret;
1388 }
1389
1390 Type * Pass3::mutate( FunctionType *functionType ) {
1391 TyVarMap oldtyVars = scopeTyVars;
1392 makeTyVarMap( functionType, scopeTyVars );
1393
1394 Type *ret = Mutator::mutate( functionType );
1395
1396 scopeTyVars = oldtyVars;
1397 return ret;
1398 }
1399 } // anonymous namespace
1400} // namespace GenPoly
1401
1402// Local Variables: //
1403// tab-width: 4 //
1404// mode: c++ //
1405// compile-command: "make install" //
1406// End: //
Note: See TracBrowser for help on using the repository browser.