Index: translator/GenPoly/Box.cc
===================================================================
--- translator/GenPoly/Box.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/Box.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,1143 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: Box.cc,v 1.20 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include <set>
+#include <string>
+#include <iterator>
+#include <algorithm>
+#include <cassert>
+
+#include "Box.h"
+#include "PolyMutator.h"
+#include "FindFunction.h"
+#include "ScrubTyVars.h"
+
+#include "SynTree/Declaration.h"
+#include "SynTree/Type.h"
+#include "SynTree/Expression.h"
+#include "SynTree/Initializer.h"
+#include "SynTree/Statement.h"
+#include "SynTree/Mutator.h"
+#include "ResolvExpr/TypeEnvironment.h"
+#include "SymTab/Mangler.h"
+
+#include "SemanticError.h"
+#include "UniqueName.h"
+#include "utility.h"
+
+#include <ext/functional> // temporary
+
+namespace GenPoly {
+
+namespace {
+
+const std::list<Label> noLabels;
+
+class Pass1 : public PolyMutator
+{
+public:
+  Pass1();
+  virtual Expression *mutate( ApplicationExpr *appExpr );
+  virtual Expression *mutate( AddressExpr *addrExpr );
+  virtual Expression *mutate( UntypedExpr *expr );
+  virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
+  virtual TypeDecl* mutate( TypeDecl *typeDecl );
+  virtual Expression *mutate( CommaExpr *commaExpr );
+  virtual Expression *mutate( ConditionalExpr *condExpr );
+  virtual Statement* mutate(ReturnStmt *catchStmt);
+  virtual Type* mutate( PointerType *pointerType );
+  virtual Type* mutate( FunctionType *pointerType );
+  
+  virtual void doEndScope();
+  
+private:
+  void passTypeVars( ApplicationExpr* appExpr, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars );
+  Expression* addRetParam( ApplicationExpr* appExpr, FunctionType *function, Type *retType, std::list< Expression* >::iterator &arg );
+  Expression* addPolyRetParam( ApplicationExpr* appExpr, FunctionType *function, std::string typeName, std::list< Expression* >::iterator &arg );
+  Expression* applyAdapter( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars );
+  void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
+  void boxParams( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars );
+  void addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression* >::iterator &arg, const TyVarMap &tyVars );
+  void findAssignOps( const std::list< TypeDecl* > &forall );
+  void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars );
+  FunctionDecl *makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
+  Expression *handleIntrinsics( ApplicationExpr *appExpr );
+  ObjectDecl *makeTemporary( Type *type );
+  
+  std::map< std::string, DeclarationWithType* > assignOps;
+  std::map< std::string, FunctionDecl* > adapters;
+  DeclarationWithType* retval;
+  bool useRetval;
+  UniqueName tempNamer;
+};
+
+class Pass2 : public PolyMutator
+{
+public:
+  Pass2();
+  template< typename DeclClass >
+  DeclClass* handleDecl( DeclClass *decl, Type *type );
+  virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
+  virtual ObjectDecl* mutate( ObjectDecl *objectDecl );
+  virtual TypeDecl* mutate( TypeDecl *typeDecl );
+  virtual TypedefDecl* mutate( TypedefDecl *typedefDecl );
+  virtual Type* mutate( PointerType *pointerType );
+  virtual Type* mutate( FunctionType *funcType );
+
+private:
+  void addAdapters( FunctionType *functionType );
+  
+  std::map< UniqueId, std::string > adapterName;
+};
+
+class Pass3 : public PolyMutator
+{
+public:
+  template< typename DeclClass >
+  DeclClass* handleDecl( DeclClass *decl, Type *type );
+  virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
+  virtual ObjectDecl* mutate( ObjectDecl *objectDecl );
+  virtual TypedefDecl* mutate( TypedefDecl *objectDecl );
+  virtual TypeDecl* mutate( TypeDecl *objectDecl );
+  virtual Statement* mutate( DeclStmt *declStmt );
+  virtual Type* mutate( PointerType *pointerType );
+  virtual Type* mutate( FunctionType *funcType );
+
+private:
+};
+
+} // anonymous namespace
+
+void
+printAllNotBuiltin( const std::list< Declaration* >& translationUnit, std::ostream &os )
+{
+  for( std::list< Declaration* >::const_iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
+    if( !LinkageSpec::isBuiltin( (*i)->get_linkage() ) ) {
+      (*i)->print( os );
+      os << std::endl;
+    }
+  }
+}
+
+void
+box( std::list< Declaration* >& translationUnit )
+{
+  Pass1 pass1;
+  Pass2 pass2;
+  Pass3 pass3;
+  mutateAll( translationUnit, pass1 );
+  mutateAll( translationUnit, pass2 );
+  mutateAll( translationUnit, pass3 );
+}
+
+////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////
+
+namespace {
+
+bool
+isPolyRet( FunctionType *function, std::string &name, const TyVarMap &otherTyVars )
+{
+  bool doTransform = false;
+  if( !function->get_returnVals().empty() ) {
+    if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( function->get_returnVals().front()->get_type() ) ) {
+    
+      // figure out if the return type is specified by a type parameter
+      for( std::list< TypeDecl* >::const_iterator tyVar = function->get_forall().begin(); tyVar != function->get_forall().end(); ++tyVar ) {
+        if( (*tyVar)->get_name() == typeInst->get_name() ) {
+          doTransform = true;
+          name = typeInst->get_name();
+          break;
+        }
+      }
+      if( !doTransform && otherTyVars.find( typeInst->get_name() ) != otherTyVars.end() ) {
+        doTransform = true;
+      }
+    }
+  }
+  return doTransform;
+}
+
+bool
+isPolyRet( FunctionType *function, std::string &name )
+{
+  TyVarMap dummyTyVars;
+  return isPolyRet( function, name, dummyTyVars );
+}
+
+Pass1::Pass1()
+  : useRetval( false ), tempNamer( "_temp" )
+{
+}
+
+bool
+checkAssignment( DeclarationWithType *decl, std::string &name )
+{
+  if( decl->get_name() == "?=?" ) {
+    if( PointerType *ptrType = dynamic_cast< PointerType* >( decl->get_type() ) ) {
+      if( FunctionType *funType = dynamic_cast< FunctionType* >( ptrType->get_base() ) ) {
+        if( funType->get_parameters().size() == 2 ) {
+          if( PointerType *pointer = dynamic_cast< PointerType* >( funType->get_parameters().front()->get_type() ) ) {
+            if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) {
+              name = typeInst->get_name();
+              return true;
+            }
+          }
+        }
+      }
+    }
+  }
+  return false;
+}
+
+void 
+Pass1::findAssignOps( const std::list< TypeDecl* > &forall )
+{
+  assignOps.clear();
+  for( std::list< TypeDecl* >::const_iterator i = forall.begin(); i != forall.end(); ++i ) {
+    for( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) {
+      std::string typeName;
+      if( checkAssignment( *assert, typeName ) ) {
+        assignOps[ typeName ] = *assert;
+      }
+    }
+  }
+}
+
+DeclarationWithType* 
+Pass1::mutate( FunctionDecl *functionDecl )
+{
+  if( functionDecl->get_statements() ) {
+    TyVarMap oldtyVars = scopeTyVars;
+    DeclarationWithType *oldRetval = retval;
+    bool oldUseRetval = useRetval;
+    
+    retval = 0;
+    std::string typeName;
+    if( isPolyRet( functionDecl->get_functionType(), typeName ) && functionDecl->get_linkage() == LinkageSpec::Cforall ) {
+      retval = functionDecl->get_functionType()->get_returnVals().front();
+  
+      // give names to unnamed return values
+      if( retval->get_name() == "" ) {
+        retval->set_name( "_retparm" );
+        retval->set_linkage( LinkageSpec::C );
+      }
+    }
+    
+    scopeTyVars.clear();
+///     std::cerr << "clear\n";
+    makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
+    findAssignOps( functionDecl->get_functionType()->get_forall() );
+    functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
+  
+    scopeTyVars = oldtyVars;
+///     std::cerr << "end FunctionDecl: ";
+///     for( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
+///       std::cerr << i->first << " ";
+///     }
+///     std::cerr << "\n";
+    retval = oldRetval;
+    useRetval = oldUseRetval;
+    doEndScope();
+  }
+  return functionDecl;
+}
+
+TypeDecl*
+Pass1::mutate( TypeDecl *typeDecl )
+{
+///     std::cerr << "add " << typeDecl->get_name() << "\n";
+  scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
+  return Mutator::mutate( typeDecl );
+}
+
+Expression *
+Pass1::mutate( CommaExpr *commaExpr )
+{
+  bool oldUseRetval = useRetval;
+  useRetval = false;
+  commaExpr->set_arg1( maybeMutate( commaExpr->get_arg1(), *this ) );
+  useRetval = oldUseRetval;
+  commaExpr->set_arg2( maybeMutate( commaExpr->get_arg2(), *this ) );
+  return commaExpr;
+}
+
+Expression *
+Pass1::mutate( ConditionalExpr *condExpr )
+{
+  bool oldUseRetval = useRetval;
+  useRetval = false;
+  condExpr->set_arg1( maybeMutate( condExpr->get_arg1(), *this ) );
+  useRetval = oldUseRetval;
+  condExpr->set_arg2( maybeMutate( condExpr->get_arg2(), *this ) );
+  condExpr->set_arg3( maybeMutate( condExpr->get_arg3(), *this ) );
+  return condExpr;
+
+}
+
+void
+Pass1::passTypeVars( ApplicationExpr* appExpr, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars )
+{
+  for( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
+    ResolvExpr::EqvClass eqvClass;
+    assert( env );
+    if( tyParm->second == TypeDecl::Any ) {
+      Type *concrete = env->lookup( tyParm->first );
+      if( concrete ) {
+        arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
+        arg++;
+      } else {
+        throw SemanticError( "unbound type variable in application ", appExpr );
+      }
+    }
+  }
+}
+
+ObjectDecl*
+Pass1::makeTemporary( Type *type )
+{
+  ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Declaration::NoStorageClass, LinkageSpec::C, 0, type, 0 );
+  stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
+  return newObj;
+}
+
+TypeInstType *
+isPolyType( Type *type, const TypeSubstitution *env, const TyVarMap &tyVars )
+{
+  if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
+    if( env ) {
+      if( Type *newType = env->lookup( typeInst->get_name() ) ) {
+        return isPolyType( newType, env, tyVars );
+      }
+    }
+    if( tyVars.find( typeInst->get_name() ) != tyVars.end() ) {
+      return typeInst;
+    } else {
+      return 0;
+    }
+  } else {
+    return 0;
+  }
+}
+
+Expression*
+Pass1::addRetParam( ApplicationExpr* appExpr, FunctionType *function, Type *retType, std::list< Expression* >::iterator &arg )
+{
+  if( useRetval ) {
+    assert( retval );
+    arg = appExpr->get_args().insert( arg, new VariableExpr( retval ) );
+    arg++;
+  } else {
+    ObjectDecl *newObj = makeTemporary( retType->clone() );
+    Expression *paramExpr = new VariableExpr( newObj );
+    if( !isPolyType( newObj->get_type(), env, scopeTyVars ) ) {
+      paramExpr = new AddressExpr( paramExpr );
+    }
+    arg = appExpr->get_args().insert( arg, paramExpr );
+    arg++;
+///     stmtsToAdd.push_back( new ExprStmt( noLabels, appExpr ) );
+    CommaExpr *commaExpr = new CommaExpr( appExpr, new VariableExpr( newObj ) );
+    commaExpr->set_env( appExpr->get_env() );
+    appExpr->set_env( 0 );
+    return commaExpr;
+  }
+  return appExpr;
+}
+
+Expression*
+Pass1::addPolyRetParam( ApplicationExpr* appExpr, FunctionType *function, std::string typeName, std::list< Expression* >::iterator &arg )
+{
+  ResolvExpr::EqvClass eqvClass;
+  assert( env );
+  Type *concrete = env->lookup( typeName );
+  if( concrete == 0 ) {
+    throw SemanticError( "Unbound type variable " + typeName + " in", appExpr );
+  }
+  return addRetParam( appExpr, function, concrete, arg );
+}
+
+Expression*
+Pass1::applyAdapter( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &tyVars )
+{
+  Expression *ret = appExpr;
+  if( !function->get_returnVals().empty() && isPolyVal( function->get_returnVals().front()->get_type(), tyVars ) ) {
+    ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
+  }
+  appExpr->get_args().push_front( appExpr->get_function() );
+  appExpr->set_function( new NameExpr( "_adapter" + SymTab::Mangler::mangle( function ) ) );
+  
+  return ret;
+}
+
+void
+Pass1::boxParam( Type *param, Expression *&arg, const TyVarMap &exprTyVars )
+{
+  assert( !arg->get_results().empty() );
+///   if( !dynamic_cast< PointerType* >( arg->get_results().front() ) ) {
+    TypeInstType *typeInst = dynamic_cast< TypeInstType* >( param );
+    if( typeInst && exprTyVars.find( typeInst->get_name() ) != exprTyVars.end() ) {
+      if( arg->get_results().front()->get_isLvalue() ) {
+        arg = new AddressExpr( arg );
+      } else {
+        ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Declaration::NoStorageClass, LinkageSpec::C, 0, arg->get_results().front()->clone(), 0 );
+        newObj->get_type()->get_qualifiers() = Type::Qualifiers();
+        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
+        UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
+        assign->get_args().push_back( new VariableExpr( newObj ) );
+        assign->get_args().push_back( arg );
+        stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
+        arg = new AddressExpr( new VariableExpr( newObj ) );
+      }
+    }
+///   }
+}
+
+void
+addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars )
+{
+  Type *newType = formal->clone();
+  std::list< FunctionType* > functions;
+  // instead of functions needing adapters, this really ought to look for
+  // any function mentioning a polymorphic type
+  findAndReplaceFunction( newType, functions, tyVars, needsAdapter );
+  if( !functions.empty() ) {
+    actual = new CastExpr( actual, newType );
+  } else {
+    delete newType;
+  }
+}
+
+void
+Pass1::boxParams( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars )
+{
+///   std::cout << "function is ";
+///   function->print( std::cout );
+  for( std::list< DeclarationWithType* >::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
+///     std::cout << "parameter is ";
+///     (*param)->print( std::cout );
+///     std::cout << std::endl << "argument is ";
+///     (*arg)->print( std::cout );
+    assert( arg != appExpr->get_args().end() );
+    addCast( *arg, (*param)->get_type(), exprTyVars );
+    boxParam( (*param)->get_type(), *arg, exprTyVars );
+  }
+}
+
+void
+Pass1::addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression* >::iterator &arg, const TyVarMap &tyVars )
+{
+  std::list< Expression* >::iterator cur = arg;
+  for( std::list< TypeDecl* >::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
+    for( std::list< DeclarationWithType* >::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
+      InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
+      assert( inferParam != appExpr->get_inferParams().end() );
+      Expression *newExpr = inferParam->second.expr->clone();
+      addCast( newExpr, (*assert)->get_type(), tyVars );
+      boxParam( (*assert)->get_type(), newExpr, tyVars );
+      appExpr->get_args().insert( cur, newExpr );
+    }
+  }
+}
+
+void
+makeRetParm( FunctionType *funcType )
+{
+  DeclarationWithType *retParm = funcType->get_returnVals().front();
+
+  // make a new parameter that is a pointer to the type of the old return value
+  retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
+  funcType->get_parameters().push_front( retParm );
+
+  // we don't need the return value any more
+  funcType->get_returnVals().clear();
+}
+
+FunctionType *
+makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars )
+{
+  // actually make the adapter type
+  FunctionType *adapter = adaptee->clone();
+  if( !adapter->get_returnVals().empty() && isPolyVal( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
+    makeRetParm( adapter );
+  }
+  adapter->get_parameters().push_front( new ObjectDecl( "", Declaration::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
+  return adapter;
+}
+
+Expression*
+makeAdapterArg( DeclarationWithType *param, DeclarationWithType *arg, DeclarationWithType *realParam, const TyVarMap &tyVars )
+{
+  assert( param );
+  assert( arg );
+///   std::cout << "arg type is ";
+///   arg->get_type()->print( std::cout );
+///   std::cout << "param type is ";
+///   param->get_type()->print( std::cout );
+///   std::cout << " tyVars are: ";
+///   printTyVarMap( std::cout, tyVars );
+  if( isPolyVal( realParam->get_type(), tyVars ) ) {
+///     if( dynamic_cast< PointerType* >( arg->get_type() ) ) {
+///       return new CastExpr( new VariableExpr( param ), arg->get_type()->clone() );
+///     } else {
+      UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
+      deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
+      deref->get_results().push_back( arg->get_type()->clone() );
+      return deref;
+///     }
+  }
+  return new VariableExpr( param );
+}
+
+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 )
+{
+  UniqueName paramNamer( "_p" );
+  for( ; param != paramEnd; ++param, ++arg, ++realParam ) {
+    if( (*param)->get_name() == "" ) {
+      (*param)->set_name( paramNamer.newName() );
+      (*param)->set_linkage( LinkageSpec::C );
+    }
+    adapteeApp->get_args().push_back( makeAdapterArg( *param, *arg, *realParam, tyVars ) );
+  }
+}
+
+FunctionDecl *
+Pass1::makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars )
+{
+  FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
+  adapterType = ScrubTyVars::scrub( adapterType, tyVars );
+  DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
+  adapteeDecl->set_name( "_adaptee" );
+  ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
+  Statement *bodyStmt;
+  
+  std::list< TypeDecl* >::iterator tyArg = realType->get_forall().begin();
+  std::list< TypeDecl* >::iterator tyParam = adapterType->get_forall().begin();
+  std::list< TypeDecl* >::iterator realTyParam = adaptee->get_forall().begin();
+  for( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
+    assert( tyArg != realType->get_forall().end() );
+    std::list< DeclarationWithType* >::iterator assertArg = (*tyArg)->get_assertions().begin();
+    std::list< DeclarationWithType* >::iterator assertParam = (*tyParam)->get_assertions().begin();
+    std::list< DeclarationWithType* >::iterator realAssertParam = (*realTyParam)->get_assertions().begin();
+    for( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
+      assert( assertArg != (*tyArg)->get_assertions().end() );
+      adapteeApp->get_args().push_back( makeAdapterArg( *assertParam, *assertArg, *realAssertParam, tyVars ) );
+    }
+  }
+  
+  std::list< DeclarationWithType* >::iterator arg = realType->get_parameters().begin();
+  std::list< DeclarationWithType* >::iterator param = adapterType->get_parameters().begin();
+  std::list< DeclarationWithType* >::iterator realParam = adaptee->get_parameters().begin();
+  param++;		// skip adaptee parameter
+  if( realType->get_returnVals().empty() ) {
+    addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
+    bodyStmt = new ExprStmt( noLabels, adapteeApp );
+  } else if( isPolyVal( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
+    if( (*param)->get_name() == "" ) {
+      (*param)->set_name( "_ret" );
+      (*param)->set_linkage( LinkageSpec::C );
+    }
+    UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
+    UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
+    deref->get_args().push_back( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
+    assign->get_args().push_back( deref );
+    addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
+    assign->get_args().push_back( adapteeApp );
+    bodyStmt = new ExprStmt( noLabels, assign );
+  } else {
+    // adapter for a function that returns a monomorphic value
+    addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
+    bodyStmt = new ReturnStmt( noLabels, adapteeApp );
+  }
+  CompoundStmt *adapterBody = new CompoundStmt( noLabels );
+  adapterBody->get_kids().push_back( bodyStmt );
+  return new FunctionDecl( "_adapter" + mangleName, Declaration::NoStorageClass, LinkageSpec::C, adapterType, adapterBody, false );
+}
+
+void
+Pass1::passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars )
+{
+  std::list< DeclarationWithType* > &paramList = functionType->get_parameters();
+  std::list< FunctionType* > functions;
+  for( std::list< TypeDecl* >::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
+    for( std::list< DeclarationWithType* >::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
+      findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
+    }
+  }
+  for( std::list< DeclarationWithType* >::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
+    findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
+  }
+  std::set< std::string > adaptersDone;
+  for( std::list< FunctionType* >::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
+    FunctionType *realFunction = (*funType)->clone();
+    assert( env );
+    env->apply( realFunction );
+    std::string mangleName = SymTab::Mangler::mangle( realFunction );
+    if( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
+      std::map< std::string, FunctionDecl* >::iterator adapter = adapters.find( mangleName );
+      if( adapter == adapters.end() ) {
+        FunctionDecl *newAdapter = makeAdapter( *funType, realFunction, mangleName, exprTyVars );
+        adapter = adapters.insert( adapters.begin(), std::pair< std::string, FunctionDecl* >( mangleName, newAdapter ) );
+        stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
+      }
+      assert( adapter != adapters.end() );
+      appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
+      adaptersDone.insert( adaptersDone.begin(), mangleName );
+    }
+  }
+}
+
+TypeInstType*
+isPolyPtr( Type *type, const TypeSubstitution *env, const TyVarMap &tyVars )
+{
+  if( PointerType *ptr = dynamic_cast< PointerType* >( type ) ) {
+    return isPolyType( ptr->get_base(), env, tyVars );
+  } else if( env ) {
+    if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
+      if( Type *newType = env->lookup( typeInst->get_name() ) ) {
+        return isPolyPtr( newType, env, tyVars );
+      }
+    }
+  }
+  return 0;
+}
+
+TypeInstType*
+isPolyPtrPtr( Type *type, const TypeSubstitution *env, const TyVarMap &tyVars )
+{
+  if( PointerType *ptr = dynamic_cast< PointerType* >( type ) ) {
+    return isPolyPtr( ptr->get_base(), env, tyVars );
+  } else if( env ) {
+    if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
+      if( Type *newType = env->lookup( typeInst->get_name() ) ) {
+        return isPolyPtrPtr( newType, env, tyVars );
+      }
+    }
+  }
+  return 0;
+}
+
+Expression *
+makeIncrDecrExpr( ApplicationExpr *appExpr, std::string polyName, bool isIncr )
+{
+  NameExpr *opExpr;
+  if( isIncr ) {
+    opExpr = new NameExpr( "?+=?" );
+  } else {
+    opExpr = new NameExpr( "?-=?" );
+  }
+  UntypedExpr *addAssign = new UntypedExpr( opExpr );
+  if( AddressExpr *address = dynamic_cast< AddressExpr* >( appExpr->get_args().front() ) ) {
+    addAssign->get_args().push_back( address->get_arg() );
+  } else {
+    addAssign->get_args().push_back( appExpr->get_args().front() );
+  }
+  addAssign->get_args().push_back( new NameExpr( polyName ) );
+  addAssign->get_results().front() = appExpr->get_results().front()->clone();
+  if( appExpr->get_env() ) {
+    addAssign->set_env( appExpr->get_env() );
+    appExpr->set_env( 0 );
+  }
+  appExpr->get_args().clear();
+  delete appExpr;
+  return addAssign;
+}
+
+Expression*
+Pass1::handleIntrinsics( ApplicationExpr *appExpr )
+{
+  if( VariableExpr *varExpr = dynamic_cast< VariableExpr* >( appExpr->get_function() ) ) {
+    if( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
+      if( varExpr->get_var()->get_name() == "?[?]" ) {
+        assert( !appExpr->get_results().empty() );
+        assert( appExpr->get_args().size() == 2 );
+        TypeInstType *typeInst1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), env, scopeTyVars );
+        TypeInstType *typeInst2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), env, scopeTyVars );
+        assert( !typeInst1 || !typeInst2 );
+        UntypedExpr *ret = 0;
+        if( typeInst1 || typeInst2 ) {
+          ret = new UntypedExpr( new NameExpr( "?+?" ) );
+        }
+        if( typeInst1 ) {
+          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
+          multiply->get_args().push_back( appExpr->get_args().back() );
+          multiply->get_args().push_back( new NameExpr( typeInst1->get_name() ) );
+          ret->get_args().push_back( appExpr->get_args().front() );
+          ret->get_args().push_back( multiply );
+        } else if( typeInst2 ) {
+          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
+          multiply->get_args().push_back( appExpr->get_args().front() );
+          multiply->get_args().push_back( new NameExpr( typeInst2->get_name() ) );
+          ret->get_args().push_back( multiply );
+          ret->get_args().push_back( appExpr->get_args().back() );
+        }
+        if( typeInst1 || typeInst2 ) {
+          ret->get_results().push_front( appExpr->get_results().front()->clone() );
+          if( appExpr->get_env() ) {
+            ret->set_env( appExpr->get_env() );
+            appExpr->set_env( 0 );
+          }
+          appExpr->get_args().clear();
+          delete appExpr;
+          return ret;
+        }
+      } else if( varExpr->get_var()->get_name() == "*?" ) {
+        assert( !appExpr->get_results().empty() );
+        assert( !appExpr->get_args().empty() );
+        if( isPolyType( appExpr->get_results().front(), env, scopeTyVars ) ) {
+          Expression *ret = appExpr->get_args().front();
+          delete ret->get_results().front();
+          ret->get_results().front() = appExpr->get_results().front()->clone();
+          if( appExpr->get_env() ) {
+            ret->set_env( appExpr->get_env() );
+            appExpr->set_env( 0 );
+          }
+          appExpr->get_args().clear();
+          delete appExpr;
+          return ret;
+        }
+      } else if( varExpr->get_var()->get_name() == "?++" || varExpr->get_var()->get_name() == "?--" ) {
+        assert( !appExpr->get_results().empty() );
+        assert( appExpr->get_args().size() == 1 );
+        if( TypeInstType *typeInst = isPolyPtr( appExpr->get_results().front(), env, scopeTyVars ) ) {
+          Type *tempType = appExpr->get_results().front()->clone();
+          if( env ) {
+            env->apply( tempType );
+          }
+          ObjectDecl *newObj = makeTemporary( tempType );
+          VariableExpr *tempExpr = new VariableExpr( newObj );
+          UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
+          assignExpr->get_args().push_back( tempExpr->clone() );
+          if( AddressExpr *address = dynamic_cast< AddressExpr* >( appExpr->get_args().front() ) ) {
+            assignExpr->get_args().push_back( address->get_arg()->clone() );
+          } else {
+            assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
+          }
+          CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, typeInst->get_name(), varExpr->get_var()->get_name() == "?++" ) );
+          return new CommaExpr( firstComma, tempExpr );
+        }
+      } else if( varExpr->get_var()->get_name() == "++?" || varExpr->get_var()->get_name() == "--?" ) {
+        assert( !appExpr->get_results().empty() );
+        assert( appExpr->get_args().size() == 1 );
+        if( TypeInstType *typeInst = isPolyPtr( appExpr->get_results().front(), env, scopeTyVars ) ) {
+           return makeIncrDecrExpr( appExpr, typeInst->get_name(), varExpr->get_var()->get_name() == "++?" );
+        }
+      } else if( varExpr->get_var()->get_name() == "?+?" || varExpr->get_var()->get_name() == "?-?" ) {
+        assert( !appExpr->get_results().empty() );
+        assert( appExpr->get_args().size() == 2 );
+        TypeInstType *typeInst1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), env, scopeTyVars );
+        TypeInstType *typeInst2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), env, scopeTyVars );
+        if( typeInst1 && typeInst2 ) {
+          UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
+          divide->get_args().push_back( appExpr );
+          divide->get_args().push_back( new NameExpr( typeInst1->get_name() ) );
+          divide->get_results().push_front( appExpr->get_results().front()->clone() );
+          if( appExpr->get_env() ) {
+            divide->set_env( appExpr->get_env() );
+            appExpr->set_env( 0 );
+          }
+          return divide;
+        } else if( typeInst1 ) {
+          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
+          multiply->get_args().push_back( appExpr->get_args().back() );
+          multiply->get_args().push_back( new NameExpr( typeInst1->get_name() ) );
+          appExpr->get_args().back() = multiply;
+        } else if( typeInst2 ) {
+          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
+          multiply->get_args().push_back( appExpr->get_args().front() );
+          multiply->get_args().push_back( new NameExpr( typeInst2->get_name() ) );
+          appExpr->get_args().front() = multiply;
+        }
+      } else if( varExpr->get_var()->get_name() == "?+=?" || varExpr->get_var()->get_name() == "?-=?" ) {
+        assert( !appExpr->get_results().empty() );
+        assert( appExpr->get_args().size() == 2 );
+        TypeInstType *typeInst = isPolyPtr( appExpr->get_results().front(), env, scopeTyVars );
+        if( typeInst ) {
+          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
+          multiply->get_args().push_back( appExpr->get_args().back() );
+          multiply->get_args().push_back( new NameExpr( typeInst->get_name() ) );
+          appExpr->get_args().back() = multiply;
+        }
+      }
+      return appExpr;
+    }
+  }
+  return 0;
+}
+
+Expression*
+Pass1::mutate( ApplicationExpr *appExpr )
+{
+///     std::cerr << "mutate appExpr: ";
+///     for( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
+///       std::cerr << i->first << " ";
+///     }
+///     std::cerr << "\n";
+  bool oldUseRetval = useRetval;
+  useRetval = false;
+  appExpr->get_function()->acceptMutator( *this );
+  mutateAll( appExpr->get_args(), *this );
+  useRetval = oldUseRetval;
+  
+  assert( !appExpr->get_function()->get_results().empty() );
+  PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() );
+  assert( pointer );
+  FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() );
+  assert( function );
+  
+  if( Expression *newExpr = handleIntrinsics( appExpr ) ) {
+    return newExpr;
+  }
+  
+  Expression *ret = appExpr;
+  
+  std::list< Expression* >::iterator arg = appExpr->get_args().begin();
+  std::list< Expression* >::iterator paramBegin = appExpr->get_args().begin();
+  
+  std::string typeName;
+  if( isPolyRet( function, typeName ) ) {
+    ret = addPolyRetParam( appExpr, function, typeName, arg );
+  } else if( needsAdapter( function, scopeTyVars ) ) {
+///     std::cerr << "needs adapter: ";
+///     for( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
+///       std::cerr << i->first << " ";
+///     }
+///     std::cerr << "\n";
+    // change the application so it calls the adapter rather than the passed function
+    ret = applyAdapter( appExpr, function, arg, scopeTyVars );
+  }
+  arg = appExpr->get_args().begin();
+  
+  TyVarMap exprTyVars;
+  makeTyVarMap( function, exprTyVars );
+  
+  passTypeVars( appExpr, arg, exprTyVars );
+  addInferredParams( appExpr, function, arg, exprTyVars );
+
+  arg = paramBegin;
+  
+  boxParams( appExpr, function, arg, exprTyVars );
+
+  passAdapters( appExpr, function, exprTyVars );
+
+  return ret;
+}
+
+Expression *
+Pass1::mutate( UntypedExpr *expr )
+{
+  if( !expr->get_results().empty() && isPolyType( expr->get_results().front(), env, scopeTyVars ) ) {
+    if( NameExpr *name = dynamic_cast< NameExpr* >( expr->get_function() ) ) {
+      if( name->get_name() == "*?" ) {
+        Expression *ret = expr->get_args().front();
+        expr->get_args().clear();
+        delete expr;
+        return ret->acceptMutator( *this );
+      }
+    }
+  }
+  return PolyMutator::mutate( expr );
+}
+
+Expression *
+Pass1::mutate( AddressExpr *addrExpr )
+{
+  assert( !addrExpr->get_arg()->get_results().empty() );
+  mutateExpression( addrExpr->get_arg() );
+  if( isPolyType( addrExpr->get_arg()->get_results().front(), env, scopeTyVars ) ) {
+    Expression *ret = addrExpr->get_arg();
+    delete ret->get_results().front();
+    ret->get_results().front() = addrExpr->get_results().front()->clone();
+    addrExpr->set_arg( 0 );
+    delete addrExpr;
+    return ret;
+  } else {
+    return addrExpr;
+  }
+}
+
+Statement* 
+Pass1::mutate(ReturnStmt *retStmt)
+{
+  // a cast expr on a polymorphic return value is either redundant or invalid
+  while( CastExpr *castExpr = dynamic_cast< CastExpr* >( retStmt->get_expr() ) ) {
+    retStmt->set_expr( castExpr->get_arg() );
+    retStmt->get_expr()->set_env( castExpr->get_env() );
+    castExpr->set_env( 0 );
+    castExpr->set_arg( 0 );
+    delete castExpr;
+  }
+  if( retval && retStmt->get_expr() ) {
+    assert( !retStmt->get_expr()->get_results().empty() );
+    if( retStmt->get_expr()->get_results().front()->get_isLvalue() ) {
+///       retStmt->set_expr( mutateExpression( retStmt->get_expr() ) );
+      TypeInstType *typeInst = dynamic_cast< TypeInstType* >( retval->get_type() );
+      assert( typeInst );
+      std::map< std::string, DeclarationWithType* >::const_iterator assignIter = assignOps.find( typeInst->get_name() );
+      if( assignIter == assignOps.end() ) {
+        throw SemanticError( "Attempt to return dtype or ftype object in ", retStmt->get_expr() );
+      }
+      ApplicationExpr *assignExpr = new ApplicationExpr( new VariableExpr( assignIter->second ) );
+      Expression *retParm = new NameExpr( retval->get_name() );
+      retParm->get_results().push_back( new PointerType( Type::Qualifiers(), retval->get_type()->clone() ) );
+      assignExpr->get_args().push_back( retParm );
+      assignExpr->get_args().push_back( retStmt->get_expr() );
+      stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( assignExpr ) ) );
+    } else {
+      useRetval = true;
+      stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( retStmt->get_expr() ) ) );
+      useRetval = false;
+    }
+    retStmt->set_expr( 0 );
+  } else {
+    retStmt->set_expr( mutateExpression( retStmt->get_expr() ) );
+  }
+  return retStmt;
+}
+
+Type* 
+Pass1::mutate( PointerType *pointerType )
+{
+  TyVarMap oldtyVars = scopeTyVars;
+  makeTyVarMap( pointerType, scopeTyVars );
+  
+  Type* ret = Mutator::mutate( pointerType );
+  
+  scopeTyVars = oldtyVars;
+  return ret;
+}
+
+Type* 
+Pass1::mutate( FunctionType *functionType )
+{
+  TyVarMap oldtyVars = scopeTyVars;
+  makeTyVarMap( functionType, scopeTyVars );
+  
+  Type* ret = Mutator::mutate( functionType );
+  
+  scopeTyVars = oldtyVars;
+  return ret;
+}
+
+void
+Pass1::doEndScope()
+{
+  adapters.clear();
+}
+
+////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
+
+Pass2::Pass2()
+{
+}
+
+void 
+Pass2::addAdapters( FunctionType *functionType )
+{
+  std::list< DeclarationWithType* > &paramList = functionType->get_parameters();
+  std::list< FunctionType* > functions;
+  for( std::list< DeclarationWithType* >::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
+    Type *orig = (*arg)->get_type();
+    findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
+    (*arg)->set_type( orig );
+  }
+  std::set< std::string > adaptersDone;
+  for( std::list< FunctionType* >::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
+    std::string mangleName = SymTab::Mangler::mangle( *funType );
+    if( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
+      paramList.push_front( new ObjectDecl( "_adapter" + mangleName, Declaration::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
+      adaptersDone.insert( adaptersDone.begin(), mangleName );
+    }
+  }
+///  deleteAll( functions );
+}
+
+template< typename DeclClass >
+DeclClass* 
+Pass2::handleDecl( DeclClass *decl, Type *type )
+{
+  DeclClass *ret = static_cast< DeclClass* >( Mutator::mutate( decl ) );
+
+  return ret;
+}
+
+DeclarationWithType* 
+Pass2::mutate( FunctionDecl *functionDecl )
+{
+  return handleDecl( functionDecl, functionDecl->get_functionType() );
+}
+
+ObjectDecl* 
+Pass2::mutate( ObjectDecl *objectDecl )
+{
+  return handleDecl( objectDecl, objectDecl->get_type() );
+}
+
+TypeDecl* 
+Pass2::mutate( TypeDecl *typeDecl )
+{
+  scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
+  if( typeDecl->get_base() ) {
+    return handleDecl( typeDecl, typeDecl->get_base() );
+  } else {
+    return Mutator::mutate( typeDecl );
+  }
+}
+
+TypedefDecl* 
+Pass2::mutate( TypedefDecl *typedefDecl )
+{
+  return handleDecl( typedefDecl, typedefDecl->get_base() );
+}
+
+Type* 
+Pass2::mutate( PointerType *pointerType )
+{
+  TyVarMap oldtyVars = scopeTyVars;
+  makeTyVarMap( pointerType, scopeTyVars );
+  
+  Type* ret = Mutator::mutate( pointerType );
+  
+  scopeTyVars = oldtyVars;
+  return ret;
+}
+
+Type *
+Pass2::mutate( FunctionType *funcType )
+{
+  TyVarMap oldtyVars = scopeTyVars;
+  makeTyVarMap( funcType, scopeTyVars );
+  
+  std::string typeName;
+  if( isPolyRet( funcType, typeName ) ) {
+    DeclarationWithType *ret = funcType->get_returnVals().front();
+    ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
+    funcType->get_parameters().push_front( ret );
+    funcType->get_returnVals().pop_front();
+  }
+  
+  std::list< DeclarationWithType* >::iterator last = funcType->get_parameters().begin();
+  std::list< DeclarationWithType* > inferredParams;
+  ObjectDecl *newObj = new ObjectDecl( "", Declaration::NoStorageClass, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
+///   ObjectDecl *newFunPtr = new ObjectDecl( "", Declaration::NoStorageClass, LinkageSpec::Cforall, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 );
+  for( std::list< TypeDecl* >::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
+    ObjectDecl *thisParm;
+    if( (*tyParm)->get_kind() == TypeDecl::Any ) {
+      thisParm = newObj->clone();
+      thisParm->set_name( (*tyParm)->get_name() );
+      last = funcType->get_parameters().insert( last, thisParm );
+      ++last;
+    }
+    for( std::list< DeclarationWithType* >::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
+///       *assert = (*assert)->acceptMutator( *this );
+      inferredParams.push_back( *assert );
+    }
+    (*tyParm)->get_assertions().clear();
+  }
+  delete newObj;
+  funcType->get_parameters().splice( last, inferredParams );
+  addAdapters( funcType );
+  mutateAll( funcType->get_returnVals(), *this );
+  mutateAll( funcType->get_parameters(), *this );
+  
+  scopeTyVars = oldtyVars;
+  return funcType;
+}
+
+////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
+
+template< typename DeclClass >
+DeclClass* 
+Pass3::handleDecl( DeclClass *decl, Type *type )
+{
+  TyVarMap oldtyVars = scopeTyVars;
+  makeTyVarMap( type, scopeTyVars );
+  
+  DeclClass *ret = static_cast< DeclClass* >( Mutator::mutate( decl ) );
+  ScrubTyVars::scrub( decl, scopeTyVars );
+
+  scopeTyVars = oldtyVars;
+  return ret;
+}
+
+ObjectDecl* 
+Pass3::mutate( ObjectDecl *objectDecl )
+{
+  return handleDecl( objectDecl, objectDecl->get_type() );
+}
+
+DeclarationWithType* 
+Pass3::mutate( FunctionDecl *functionDecl )
+{
+  return handleDecl( functionDecl, functionDecl->get_functionType() );
+}
+
+TypedefDecl* 
+Pass3::mutate( TypedefDecl *typedefDecl )
+{
+  return handleDecl( typedefDecl, typedefDecl->get_base() );
+}
+
+TypeDecl* 
+Pass3::mutate( TypeDecl *typeDecl )
+{
+///   Initializer *init = 0;
+///   std::list< Expression *> designators;
+///   scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
+///   if( typeDecl->get_base() ) {
+///     init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
+///   }
+///   return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
+
+  scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
+  return Mutator::mutate( typeDecl );
+}
+
+Type* 
+Pass3::mutate( PointerType *pointerType )
+{
+  TyVarMap oldtyVars = scopeTyVars;
+  makeTyVarMap( pointerType, scopeTyVars );
+  
+  Type* ret = Mutator::mutate( pointerType );
+  
+  scopeTyVars = oldtyVars;
+  return ret;
+}
+
+Type* 
+Pass3::mutate( FunctionType *functionType )
+{
+  TyVarMap oldtyVars = scopeTyVars;
+  makeTyVarMap( functionType, scopeTyVars );
+  
+  Type* ret = Mutator::mutate( functionType );
+  
+  scopeTyVars = oldtyVars;
+  return ret;
+}
+
+Statement*
+Pass3::mutate( DeclStmt *declStmt )
+{
+  if( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( declStmt->get_decl() ) ) {
+    if( isPolyVal( objectDecl->get_type(), scopeTyVars ) ) {
+      TypeInstType *typeInst = dynamic_cast< TypeInstType* >( objectDecl->get_type() );
+      assert( typeInst );
+      UntypedExpr *alloc = new UntypedExpr( new NameExpr( "alloca" ) );
+      alloc->get_args().push_back( new NameExpr( typeInst->get_name() ) );
+      UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
+      assign->get_args().push_back( new VariableExpr( objectDecl ) );
+      assign->get_args().push_back( alloc );
+      stmtsToAddAfter.push_back( new ExprStmt( noLabels, assign ) );
+    }
+  }
+  return Mutator::mutate( declStmt );
+}
+    
+} // anonymous namespace
+
+} // namespace GenPoly
Index: translator/GenPoly/Box.h
===================================================================
--- translator/GenPoly/Box.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/Box.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,21 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: Box.h,v 1.2 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#ifndef GENPOLY_BOX_H
+#define GENPOLY_BOX_H
+
+#include <list>
+
+#include "SynTree/SynTree.h"
+
+namespace GenPoly {
+
+void box( std::list< Declaration* >& translationUnit );
+
+} // namespace GenPoly
+
+#endif /* #ifndef GENPOLY_BOX_H */
Index: translator/GenPoly/CopyParams.cc
===================================================================
--- translator/GenPoly/CopyParams.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/CopyParams.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,97 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: CopyParams.cc,v 1.3 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include <set>
+#include <map>
+#include <cassert>
+
+#include "SynTree/Declaration.h"
+#include "SynTree/Type.h"
+#include "SynTree/Expression.h"
+#include "SynTree/Statement.h"
+#include "SynTree/Visitor.h"
+#include "UniqueName.h"
+
+
+namespace GenPoly {
+
+class CopyParams : public Visitor
+{
+public:
+  CopyParams();
+  
+  virtual void visit( FunctionDecl *funcDecl );
+  virtual void visit( AddressExpr *addrExpr );
+
+private:
+  std::set< UniqueId > modVars;
+  UniqueName namer;
+};
+
+void
+copyParams( std::list< Declaration* > &translationUnit )
+{
+  CopyParams copier;
+  acceptAll( translationUnit, copier );
+}
+
+CopyParams::CopyParams()
+  : namer( "_cp" )
+{
+}
+
+static const std::list< Label > noLabels;
+
+void 
+CopyParams::visit( FunctionDecl *funcDecl )
+{
+  if( funcDecl->get_statements() ) {
+    funcDecl->get_statements()->accept( *this );
+    
+    if( !modVars.empty() ) {
+      std::map< std::string, DeclarationWithType* > assignOps;
+      // assume that the assignment operator is the first assert param after any "type" parameter
+      for( std::list< TypeDecl* >::const_iterator tyVar = funcDecl->get_functionType()->get_forall().begin(); tyVar != funcDecl->get_functionType()->get_forall().end(); ++tyVar ) {
+        if( (*tyVar)->get_kind() == TypeDecl::Any ) {
+          assert( !(*tyVar)->get_assertions().empty() );
+          assignOps[ (*tyVar)->get_name() ] = (*tyVar)->get_assertions().front();
+        }
+      }
+      for( std::list< DeclarationWithType* >::iterator param = funcDecl->get_functionType()->get_parameters().begin(); param != funcDecl->get_functionType()->get_parameters().end(); ++param ) {
+        std::set< UniqueId >::const_iterator var = modVars.find( (*param)->get_uniqueId() );
+        if( var != modVars.end() ) {
+          TypeInstType *typeInst = dynamic_cast< TypeInstType* >( (*param)->get_type() );
+          assert( typeInst );
+          std::map< std::string, DeclarationWithType* >::const_iterator assignOp = assignOps.find( typeInst->get_name() );
+          if( assignOp != assignOps.end() ) {
+            DeclarationWithType *oldParam = *param;
+            *param = (*param)->clone();
+            (*param)->set_name( namer.newName() );
+            ApplicationExpr *assign = new ApplicationExpr( new VariableExpr( assignOp->second ) );
+            assign->get_args().push_back( new VariableExpr( oldParam ) );
+            assign->get_args().push_back( new VariableExpr( *param ) );
+            funcDecl->get_statements()->get_kids().push_front( new ExprStmt( noLabels, assign ) );
+            funcDecl->get_statements()->get_kids().push_front( new DeclStmt( noLabels, oldParam ) );
+          }
+          modVars.erase( var );
+        }
+      }
+    }
+  }
+}
+
+void 
+CopyParams::visit( AddressExpr *addrExpr )
+{
+  if( VariableExpr *varExpr = dynamic_cast< VariableExpr* >( addrExpr->get_arg() ) ) {
+    if( dynamic_cast< TypeInstType* >( varExpr->get_var()->get_type() ) ) {
+      modVars.insert( varExpr->get_var()->get_uniqueId() );
+    }
+  }
+}
+
+} // namespace GenPoly
Index: translator/GenPoly/CopyParams.h
===================================================================
--- translator/GenPoly/CopyParams.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/CopyParams.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,19 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: CopyParams.h,v 1.2 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#ifndef GENPOLY_COPYPARAMS_H
+#define GENPOLY_COPYPARAMS_H
+
+#include "SynTree/SynTree.h"
+
+namespace GenPoly {
+
+void copyParams( std::list< Declaration* > &translationUnit );
+
+} // namespace GenPoly
+
+#endif /* #ifndef GENPOLY_COPYPARAMS_H */
Index: translator/GenPoly/FindFunction.cc
===================================================================
--- translator/GenPoly/FindFunction.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/FindFunction.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,89 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: FindFunction.cc,v 1.5 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include "FindFunction.h"
+#include "SynTree/Type.h"
+#include "SynTree/Declaration.h"
+#include "SynTree/Visitor.h"
+
+namespace GenPoly {
+
+class FindFunction : public Mutator
+{
+public:
+  FindFunction( std::list< FunctionType* > &functions, const TyVarMap &tyVars, bool replaceMode, FindFunctionPredicate predicate );
+  
+  virtual Type *mutate( FunctionType *functionType );
+  virtual Type *mutate( PointerType *pointerType );
+  
+private:
+  void handleForall( const std::list< TypeDecl* > &forall );
+
+  std::list< FunctionType* > &functions;
+  TyVarMap tyVars;
+  bool replaceMode;
+  FindFunctionPredicate predicate;
+};
+
+void
+findFunction( Type *type, std::list< FunctionType* > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate )
+{
+  FindFunction finder( functions, tyVars, false, predicate );
+  type->acceptMutator( finder );
+}
+
+void
+findAndReplaceFunction( Type *&type, std::list< FunctionType* > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate )
+{
+  FindFunction finder( functions, tyVars, true, predicate );
+  type = type->acceptMutator( finder );
+}
+
+FindFunction::FindFunction( std::list< FunctionType* > &functions, const TyVarMap &tyVars, bool replaceMode, FindFunctionPredicate predicate )
+  : functions( functions ), tyVars( tyVars ), replaceMode( replaceMode ), predicate( predicate )
+{
+}
+
+void
+FindFunction::handleForall( const std::list< TypeDecl* > &forall )
+{
+  for( std::list< TypeDecl* >::const_iterator i = forall.begin(); i != forall.end(); ++i ) {
+    TyVarMap::iterator var = tyVars.find( (*i)->get_name() );
+    if( var != tyVars.end() ) {
+      tyVars.erase( var );
+    }
+  }
+}
+
+Type* 
+FindFunction::mutate( FunctionType *functionType )
+{
+  TyVarMap oldTyVars = tyVars;
+  handleForall( functionType->get_forall() );
+  mutateAll( functionType->get_returnVals(), *this );
+  Type *ret = functionType;
+  if( predicate( functionType, tyVars ) ) {
+    functions.push_back( functionType );
+    if( replaceMode ) {
+      ret = new FunctionType( Type::Qualifiers(), true );
+    }
+  }
+  tyVars = oldTyVars;
+  return ret;
+}
+
+Type *
+FindFunction::mutate( PointerType *pointerType )
+{
+  TyVarMap oldTyVars = tyVars;
+  handleForall( pointerType->get_forall() );
+  Type *ret = Mutator::mutate( pointerType );
+  tyVars = oldTyVars;
+  return ret;
+}
+
+} // namespace GenPoly
Index: translator/GenPoly/FindFunction.h
===================================================================
--- translator/GenPoly/FindFunction.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/FindFunction.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,23 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: FindFunction.h,v 1.4 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#ifndef FINDFUNCTION_H
+#define FINDFUNCTION_H
+
+#include "SynTree/SynTree.h"
+#include "GenPoly.h"
+
+namespace GenPoly {
+
+typedef bool (*FindFunctionPredicate)( FunctionType*, const TyVarMap& );
+
+void findFunction( Type *type, std::list< FunctionType* > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate );
+void findAndReplaceFunction( Type *&type, std::list< FunctionType* > &functions, const TyVarMap &tyVars, FindFunctionPredicate predicate );
+
+} // namespace GenPoly
+
+#endif /* #ifndef FINDFUNCTION_H */
Index: translator/GenPoly/GenPoly.cc
===================================================================
--- translator/GenPoly/GenPoly.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/GenPoly.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,52 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: GenPoly.cc,v 1.4 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include "GenPoly.h"
+#include "SynTree/Type.h"
+
+
+namespace GenPoly {
+
+bool
+isPolyVal( Type *type, const TyVarMap &tyVars )
+{
+  if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
+    if( tyVars.find( typeInst->get_name() ) != tyVars.end() ) {
+      return true;
+    }
+  }
+  return false;
+}
+
+// A function needs an adapter if it returns a polymorphic value or if any of its
+// parameters have polymorphic type
+bool
+needsAdapter( FunctionType *adaptee, const TyVarMap &tyVars )
+{
+  bool needsAdapter = false;
+  if( !adaptee->get_returnVals().empty() && isPolyVal( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
+    needsAdapter = true;
+  }
+  for( std::list< DeclarationWithType* >::const_iterator innerArg = adaptee->get_parameters().begin(); !needsAdapter && innerArg != adaptee->get_parameters().end(); ++innerArg ) {
+    if( isPolyVal( (*innerArg)->get_type(), tyVars ) ) {
+      needsAdapter = true;
+    }
+  }
+  
+  return needsAdapter;
+}
+
+void 
+printTyVarMap( std::ostream &os, const TyVarMap &tyVarMap )
+{
+  for( TyVarMap::const_iterator i = tyVarMap.begin(); i != tyVarMap.end(); ++i ) {
+    os << i->first << " (" << i->second << ") ";
+  }
+  os << std::endl;
+}
+
+} // namespace GenPoly
Index: translator/GenPoly/GenPoly.h
===================================================================
--- translator/GenPoly/GenPoly.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/GenPoly.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,22 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: GenPoly.h,v 1.4 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include <map>
+#include <string>
+#include <iostream>
+#include "SynTree/Declaration.h"
+
+namespace GenPoly {
+
+typedef std::map< std::string, TypeDecl::Kind > TyVarMap;
+
+bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVars );
+bool isPolyFun( FunctionType *fun, const TyVarMap &tyVars );
+bool isPolyVal( Type *type, const TyVarMap &tyVars );
+void printTyVarMap( std::ostream &os, const TyVarMap &tyVarMap );
+
+} // namespace GenPoly
Index: translator/GenPoly/Lvalue.cc
===================================================================
--- translator/GenPoly/Lvalue.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/Lvalue.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,168 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: Lvalue.cc,v 1.5 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include <cassert>
+
+#include "Lvalue.h"
+
+#include "SynTree/Declaration.h"
+#include "SynTree/Type.h"
+#include "SynTree/Expression.h"
+#include "SynTree/Statement.h"
+#include "SynTree/Visitor.h"
+#include "SynTree/Mutator.h"
+#include "SymTab/Indexer.h"
+#include "ResolvExpr/Resolver.h"
+#include "ResolvExpr/typeops.h"
+
+#include "UniqueName.h"
+#include "utility.h"
+
+
+namespace GenPoly {
+
+namespace {
+
+const std::list<Label> noLabels;
+
+class Pass1 : public Mutator
+{
+public:
+  Pass1();
+  
+  virtual Expression *mutate( ApplicationExpr *appExpr );
+  virtual Statement *mutate( ReturnStmt *appExpr );
+  virtual DeclarationWithType *mutate( FunctionDecl *funDecl );
+
+private:
+  DeclarationWithType* retval;
+};
+
+class Pass2 : public Visitor
+{
+public:
+  virtual void visit( FunctionType *funType );
+
+private:
+};
+
+} // namespace
+
+void
+convertLvalue( std::list< Declaration* >& translationUnit )
+{
+  Pass1 p1;
+  Pass2 p2;
+  mutateAll( translationUnit, p1 );
+  acceptAll( translationUnit, p2 );
+}
+
+namespace {
+
+bool
+isLvalueRet( FunctionType *function )
+{
+  if( !function->get_returnVals().empty() ) {
+    return function->get_returnVals().front()->get_type()->get_isLvalue();
+  } else {
+    return false;
+  }
+}
+
+bool
+isIntrinsicApp( ApplicationExpr *appExpr )
+{
+  if( VariableExpr *varExpr = dynamic_cast< VariableExpr* >( appExpr->get_function() ) ) {
+    return varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic;
+  } else {
+    return false;
+  }
+}
+
+Pass1::Pass1()
+{
+}
+
+DeclarationWithType* 
+Pass1::mutate( FunctionDecl *funcDecl )
+{
+  if( funcDecl->get_statements() ) {
+    DeclarationWithType* oldRetval = retval;
+    retval = 0;
+    if( !LinkageSpec::isBuiltin( funcDecl->get_linkage() ) && isLvalueRet( funcDecl->get_functionType() ) ) {
+      retval = funcDecl->get_functionType()->get_returnVals().front();
+    }
+    // fix expressions and return statements in this function
+    funcDecl->set_statements( funcDecl->get_statements()->acceptMutator( *this ) );
+    retval = oldRetval;
+  }
+  return funcDecl;
+}
+
+Expression* 
+Pass1::mutate( ApplicationExpr *appExpr )
+{
+  appExpr->get_function()->acceptMutator( *this );
+  mutateAll( appExpr->get_args(), *this );
+  
+  assert( !appExpr->get_function()->get_results().empty() );
+
+  PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() );
+  assert( pointer );
+  FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() );
+  assert( function );
+
+  std::string typeName;
+  if( isLvalueRet( function ) && !isIntrinsicApp( appExpr ) ) {
+    UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
+    deref->get_results().push_back( appExpr->get_results().front() );
+    appExpr->get_results().front() = new PointerType( Type::Qualifiers(), deref->get_results().front()->clone() );
+    deref->get_args().push_back( appExpr );
+    return deref;
+  } else {
+    return appExpr;
+  }
+}
+
+Statement* 
+Pass1::mutate(ReturnStmt *retStmt)
+{
+  if( retval && retStmt->get_expr() ) {
+    assert( !retStmt->get_expr()->get_results().empty() );
+    while( CastExpr *castExpr = dynamic_cast< CastExpr* >( retStmt->get_expr() ) ) {
+      retStmt->set_expr( castExpr->get_arg() );
+      retStmt->get_expr()->set_env( castExpr->get_env() );
+      castExpr->set_env( 0 );
+      castExpr->set_arg( 0 );
+      delete castExpr;
+    }
+    if( retStmt->get_expr()->get_results().front()->get_isLvalue() ) {
+      retStmt->set_expr( new AddressExpr( retStmt->get_expr()->acceptMutator( *this ) ) );
+    } else {
+      throw SemanticError( "Attempt to return non-lvalue from an lvalue-qualified function" );
+    }
+  }
+  return retStmt;
+}
+
+void 
+Pass2::visit( FunctionType *funType )
+{
+  std::string typeName;
+  if( isLvalueRet( funType ) ) {
+    DeclarationWithType *retParm = funType->get_returnVals().front();
+    
+    // make a new parameter that is a pointer to the type of the old return value
+    retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
+  }
+  
+  Visitor::visit( funType );
+}
+
+} // namespace
+
+} // namespace GenPoly
Index: translator/GenPoly/Lvalue.h
===================================================================
--- translator/GenPoly/Lvalue.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/Lvalue.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,21 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: Lvalue.h,v 1.2 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#ifndef GENPOLY_LVALUE_H
+#define GENPOLY_LVALUE_H
+
+#include <list>
+
+#include "SynTree/SynTree.h"
+
+namespace GenPoly {
+
+void convertLvalue( std::list< Declaration* >& translationUnit );
+
+} // namespace GenPoly
+
+#endif /* #ifndef GENPOLY_LVALUE_H */
Index: translator/GenPoly/PolyMutator.cc
===================================================================
--- translator/GenPoly/PolyMutator.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/PolyMutator.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,188 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: PolyMutator.cc,v 1.7 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include "PolyMutator.h"
+#include "SynTree/Declaration.h"
+#include "SynTree/Type.h"
+#include "SynTree/Expression.h"
+#include "SynTree/Statement.h"
+#include "SynTree/Mutator.h"
+
+
+namespace GenPoly {
+
+namespace {
+const std::list<Label> noLabels;
+}
+
+PolyMutator::PolyMutator()
+  : env( 0 )
+{
+}
+
+void
+PolyMutator::mutateStatementList( std::list< Statement* > &statements )
+{
+  for( std::list< Statement* >::iterator i = statements.begin(); i != statements.end(); ++i ) {
+    if( !stmtsToAddAfter.empty() ) {
+      statements.splice( i, stmtsToAddAfter );
+    }
+    *i = (*i)->acceptMutator( *this );
+    if( !stmtsToAdd.empty() ) {
+      statements.splice( i, stmtsToAdd );
+    }
+  }
+  if( !stmtsToAddAfter.empty() ) {
+    statements.splice( statements.end(), stmtsToAddAfter );
+  }
+}
+
+Statement*
+PolyMutator::mutateStatement( Statement *stmt )
+{
+  Statement *newStmt = maybeMutate( stmt, *this );
+  if( !stmtsToAdd.empty() || !stmtsToAddAfter.empty() ) {
+    CompoundStmt *compound = new CompoundStmt( noLabels );
+    compound->get_kids().splice( compound->get_kids().end(), stmtsToAdd );
+    compound->get_kids().push_back( newStmt );
+    compound->get_kids().splice( compound->get_kids().end(), stmtsToAddAfter );
+    doEndScope();
+    return compound;
+  } else {
+    return newStmt;
+  }
+}
+
+Expression*
+PolyMutator::mutateExpression( Expression *expr )
+{
+  if( expr ) {
+    if( expr->get_env() ) {
+      env = expr->get_env();
+    }
+    return expr->acceptMutator( *this );
+  } else {
+    return expr;
+  }
+}
+
+CompoundStmt*
+PolyMutator::mutate(CompoundStmt *compoundStmt)
+{
+  mutateStatementList( compoundStmt->get_kids() );
+  doEndScope();
+  return compoundStmt;
+}
+
+Statement*
+PolyMutator::mutate(IfStmt *ifStmt)
+{
+  ifStmt->set_thenPart(  mutateStatement( ifStmt->get_thenPart() ) );
+  ifStmt->set_elsePart(  mutateStatement( ifStmt->get_elsePart() ) );
+  ifStmt->set_condition(  mutateExpression( ifStmt->get_condition() ) );
+  return ifStmt;
+}
+
+Statement*
+PolyMutator::mutate(WhileStmt *whileStmt)
+{
+  whileStmt->set_body(  mutateStatement( whileStmt->get_body() ) );
+  whileStmt->set_condition(  mutateExpression( whileStmt->get_condition() ) );
+  return whileStmt;
+}
+
+Statement*
+PolyMutator::mutate(ForStmt *forStmt)
+{
+  forStmt->set_body(  mutateStatement( forStmt->get_body() ) );
+  forStmt->set_initialization(  maybeMutate( forStmt->get_initialization(), *this ) );
+  forStmt->set_condition(  mutateExpression( forStmt->get_condition() ) );
+  forStmt->set_increment(  mutateExpression( forStmt->get_increment() ) );
+  return forStmt;
+}
+
+Statement*
+PolyMutator::mutate(SwitchStmt *switchStmt)
+{
+  mutateStatementList( switchStmt->get_branches() );
+  switchStmt->set_condition( mutateExpression( switchStmt->get_condition() ) );
+  return switchStmt;
+}
+
+Statement*
+PolyMutator::mutate(ChooseStmt *switchStmt)
+{
+  mutateStatementList( switchStmt->get_branches() );
+  switchStmt->set_condition( mutateExpression( switchStmt->get_condition() ) );
+  return switchStmt;
+}
+
+Statement*
+PolyMutator::mutate(CaseStmt *caseStmt)
+{
+  mutateStatementList( caseStmt->get_statements() );
+  caseStmt->set_condition(  mutateExpression( caseStmt->get_condition() ) );
+
+  return caseStmt;
+}
+
+Statement*
+PolyMutator::mutate(TryStmt *tryStmt)
+{
+  tryStmt->set_block(  maybeMutate( tryStmt->get_block(), *this ) );
+  mutateAll( tryStmt->get_catchers(), *this );
+  
+  return tryStmt;
+}
+
+Statement*
+PolyMutator::mutate(CatchStmt *cathStmt)
+{
+  cathStmt->set_body(  mutateStatement( cathStmt->get_body() ) );
+  cathStmt->set_decl(  maybeMutate( cathStmt->get_decl(), *this ) );
+  return cathStmt;
+}
+
+Statement* 
+PolyMutator::mutate(ReturnStmt *retStmt)
+{
+  retStmt->set_expr( mutateExpression( retStmt->get_expr() ) );
+  return retStmt;
+}
+
+Statement* 
+PolyMutator::mutate(ExprStmt *exprStmt)
+{
+  exprStmt->set_expr( mutateExpression( exprStmt->get_expr() ) );
+  return exprStmt;
+}
+
+
+Expression* 
+PolyMutator::mutate(UntypedExpr *untypedExpr)
+{
+  for( std::list< Expression* >::iterator i = untypedExpr->get_args().begin(); i != untypedExpr->get_args().end(); ++i ) {
+    *i = mutateExpression( *i );
+  }
+  return untypedExpr;
+}
+ 
+/* static class method */
+void 
+PolyMutator::makeTyVarMap( Type *type, TyVarMap &tyVarMap )
+{
+  for( std::list< TypeDecl* >::const_iterator tyVar = type->get_forall().begin(); tyVar != type->get_forall().end(); ++tyVar ) {
+    assert( *tyVar );
+    tyVarMap[ (*tyVar)->get_name() ] = (*tyVar)->get_kind();
+  }
+  if( PointerType *pointer = dynamic_cast< PointerType* >( type ) ) {
+    makeTyVarMap( pointer->get_base(), tyVarMap );
+  }
+}
+
+/* static class method */
+} // namespace GenPoly
Index: translator/GenPoly/PolyMutator.h
===================================================================
--- translator/GenPoly/PolyMutator.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/PolyMutator.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,59 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: PolyMutator.h,v 1.8 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#ifndef GENPOLY_POLYMUTATOR_H
+#define GENPOLY_POLYMUTATOR_H
+
+#include <map>
+#include <string>
+#include <list>
+
+#include "GenPoly.h"
+
+#include "SynTree/SynTree.h"
+#include "SynTree/Declaration.h"
+#include "SynTree/Mutator.h"
+
+namespace GenPoly {
+
+class PolyMutator : public Mutator
+{
+public:
+  PolyMutator();
+
+  virtual CompoundStmt* mutate(CompoundStmt *compoundStmt);
+  virtual Statement* mutate(IfStmt *ifStmt);
+  virtual Statement* mutate(WhileStmt *whileStmt);
+  virtual Statement* mutate(ForStmt *forStmt);
+  virtual Statement* mutate(SwitchStmt *switchStmt);
+  virtual Statement* mutate(ChooseStmt *chooseStmt);
+  virtual Statement* mutate(CaseStmt *caseStmt);
+  virtual Statement* mutate(TryStmt *returnStmt);
+  virtual Statement* mutate(CatchStmt *catchStmt);
+  virtual Statement* mutate(ExprStmt *catchStmt);
+  virtual Statement* mutate(ReturnStmt *catchStmt);
+  
+  virtual Expression* mutate(UntypedExpr *untypedExpr);
+  
+  // template method
+  virtual void doEndScope() {}
+
+protected:
+  void mutateStatementList( std::list< Statement* > &statements );
+  Statement* mutateStatement( Statement *stmt );
+  Expression* mutateExpression( Expression *expr );
+  static void makeTyVarMap( Type *type, TyVarMap &tyVarMap );
+  
+  TyVarMap scopeTyVars;
+  TypeSubstitution *env;
+  std::list< Statement* > stmtsToAdd;
+  std::list< Statement* > stmtsToAddAfter;
+};
+
+} // namespace 
+
+#endif /* #ifndef GENPOLY_POLYMUTATOR_H */
Index: translator/GenPoly/ScrubTyVars.cc
===================================================================
--- translator/GenPoly/ScrubTyVars.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/ScrubTyVars.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,52 @@
+#include "GenPoly.h"
+#include "ScrubTyVars.h"
+
+#include "SynTree/Mutator.h"
+#include "SynTree/Type.h"
+
+
+namespace GenPoly {
+
+Type* 
+ScrubTyVars::mutate( TypeInstType *typeInst )
+{
+  TyVarMap::const_iterator tyVar = tyVars.find( typeInst->get_name() );
+  if( doAll || tyVar != tyVars.end() ) {
+    switch( tyVar->second ) {
+    case TypeDecl::Any:
+    case TypeDecl::Dtype:
+    {
+      PointerType *ret = new PointerType( Type::Qualifiers(), new VoidType( typeInst->get_qualifiers() ) );
+      delete typeInst;
+      return ret;
+    }
+      
+    case TypeDecl::Ftype:
+      delete typeInst;
+      return new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) );
+    }
+  }
+  return typeInst;
+}
+
+Type* 
+ScrubTyVars::mutate( PointerType *pointer )
+{
+  if( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( pointer->get_base() ) ) {
+    if( doAll || tyVars.find( typeInst->get_name() ) != tyVars.end() ) {
+      Type *ret = mutate( typeInst );
+///       std::cout << "pointer is ";
+///       pointer->print( std::cout );
+///       std::cout << std::endl << "ret is ";
+///       ret->print( std::cout );
+///       std::cout << std::endl;
+      ret->get_qualifiers() += pointer->get_qualifiers();
+      pointer->set_base( 0 );
+      delete pointer;
+      return ret;
+    }
+  }
+  return Mutator::mutate( pointer );
+}
+
+} // namespace GenPoly
Index: translator/GenPoly/ScrubTyVars.h
===================================================================
--- translator/GenPoly/ScrubTyVars.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/ScrubTyVars.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,57 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: ScrubTyVars.h,v 1.4 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#ifndef GENPOLY_SCRUBTYVARS_H
+#define GENPOLY_SCRUBTYVARS_H
+
+#include "GenPoly.h"
+
+#include "SynTree/SynTree.h"
+#include "SynTree/Mutator.h"
+
+namespace GenPoly {
+
+class ScrubTyVars : public Mutator
+{
+public:
+  ScrubTyVars( bool doAll, const TyVarMap &tyVars ): doAll( doAll ), tyVars( tyVars ) {}
+  
+  template< typename SynTreeClass >
+  static SynTreeClass *scrub( SynTreeClass *target, const TyVarMap &tyVars );
+  template< typename SynTreeClass >
+  static SynTreeClass *scrub( SynTreeClass *target );
+  
+  virtual Type* mutate( TypeInstType *typeInst );
+  virtual Type* mutate( PointerType *pointer );
+
+private:
+  bool doAll;
+  const TyVarMap &tyVars;
+};
+
+/* static class method */
+template< typename SynTreeClass >
+SynTreeClass *
+ScrubTyVars::scrub( SynTreeClass *target, const TyVarMap &tyVars )
+{
+  ScrubTyVars scrubber( false, tyVars );
+  return static_cast< SynTreeClass* >( target->acceptMutator( scrubber ) );
+}
+
+/* static class method */
+template< typename SynTreeClass >
+SynTreeClass *
+ScrubTyVars::scrub( SynTreeClass *target )
+{
+  TyVarMap tyVars;
+  ScrubTyVars scrubber( true, tyVars );
+  return static_cast< SynTreeClass* >( target->acceptMutator( scrubber ) );
+}
+
+} // namespace GenPoly
+
+#endif /* #ifndef GENPOLY_SCRUBTYVARS_H */
Index: translator/GenPoly/Specialize.cc
===================================================================
--- translator/GenPoly/Specialize.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/Specialize.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,206 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: Specialize.cc,v 1.4 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#include <cassert>
+
+#include "Specialize.h"
+#include "PolyMutator.h"
+
+#include "SynTree/Declaration.h"
+#include "SynTree/Statement.h"
+#include "SynTree/Expression.h"
+#include "SynTree/Type.h"
+#include "SynTree/TypeSubstitution.h"
+#include "SynTree/Mutator.h"
+#include "ResolvExpr/FindOpenVars.h"
+#include "UniqueName.h"
+#include "utility.h"
+
+
+namespace GenPoly {
+
+const std::list<Label> noLabels;
+
+class Specialize : public PolyMutator
+{
+public:
+  Specialize( std::string paramPrefix = "_p" );
+  
+  virtual Expression* mutate(ApplicationExpr *applicationExpr);
+  virtual Expression* mutate(AddressExpr *castExpr);
+  virtual Expression* mutate(CastExpr *castExpr);
+  virtual Expression* mutate(LogicalExpr *logicalExpr);
+  virtual Expression* mutate(ConditionalExpr *conditionalExpr);
+  virtual Expression* mutate(CommaExpr *commaExpr);
+
+private:
+  Expression *doSpecialization( Type *formalType, Expression *actual, InferredParams *inferParams = 0 );
+  void handleExplicitParams( ApplicationExpr *appExpr );
+  
+  UniqueName thunkNamer;
+  std::string paramPrefix;
+};
+
+void
+convertSpecializations( std::list< Declaration* >& translationUnit )
+{
+  Specialize specializer;
+  mutateAll( translationUnit, specializer );
+}
+
+Specialize::Specialize( std::string paramPrefix )
+  : thunkNamer( "_thunk" ), paramPrefix( paramPrefix )
+{
+}
+
+bool
+needsSpecialization( Type *formalType, Type *actualType, TypeSubstitution *env )
+{
+  if( env ) {
+    using namespace ResolvExpr;
+    OpenVarSet openVars, closedVars;
+    AssertionSet need, have;
+    findOpenVars( formalType, openVars, closedVars, need, have, false );
+    findOpenVars( actualType, openVars, closedVars, need, have, true );
+    for( OpenVarSet::const_iterator openVar = openVars.begin(); openVar != openVars.end(); ++openVar ) {
+      Type *boundType = env->lookup( openVar->first );
+      if( !boundType ) continue;
+      if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( boundType ) ) {
+        if( closedVars.find( typeInst->get_name() ) == closedVars.end() ) {
+          return true;
+        }
+      } else {
+        return true;
+      }
+    }
+    return false;
+  } else {
+    return false;
+  }
+}
+
+Expression*
+Specialize::doSpecialization( Type *formalType, Expression *actual, InferredParams *inferParams )
+{
+  if( needsSpecialization( formalType, actual->get_results().front(), env ) ) {
+    PointerType *ptrType;
+    FunctionType *funType;
+    if( ( ptrType = dynamic_cast< PointerType* >( formalType ) ) && ( funType = dynamic_cast< FunctionType* >( ptrType->get_base() ) ) ) {
+      FunctionType *newType = funType->clone();
+      if( env ) {
+        TypeSubstitution newEnv( *env );
+        // it is important to replace only occurrences of type variables that occur free in the
+        // thunk's type
+        newEnv.applyFree( newType );
+      }
+      FunctionDecl *thunkFunc = new FunctionDecl( thunkNamer.newName(), Declaration::NoStorageClass, LinkageSpec::C, newType, new CompoundStmt( std::list< std::string >() ), false );
+      thunkFunc->fixUniqueId();
+      
+      UniqueName paramNamer( paramPrefix );
+      ApplicationExpr *appExpr = new ApplicationExpr( actual );
+      for( std::list< DeclarationWithType* >::iterator param = thunkFunc->get_functionType()->get_parameters().begin(); param != thunkFunc->get_functionType()->get_parameters().end(); ++param ) {
+        (*param)->set_name( paramNamer.newName() );
+        appExpr->get_args().push_back( new VariableExpr( *param ) );
+      }
+      appExpr->set_env( maybeClone( env ) );
+      if( inferParams ) {
+        appExpr->get_inferParams() = *inferParams;
+      }
+      
+      // handle any specializations that may still be present
+      std::string oldParamPrefix = paramPrefix;
+      paramPrefix += "p";
+      std::list< Statement* > oldStmts;
+      oldStmts.splice( oldStmts.end(), stmtsToAdd );
+      handleExplicitParams( appExpr );
+      paramPrefix = oldParamPrefix;
+      thunkFunc->get_statements()->get_kids().splice( thunkFunc->get_statements()->get_kids().end(), stmtsToAdd );
+      stmtsToAdd.splice( stmtsToAdd.end(), oldStmts );
+      
+      Statement *appStmt;
+      if( funType->get_returnVals().empty() ) {
+        appStmt = new ExprStmt( noLabels, appExpr );
+      } else {
+        appStmt = new ReturnStmt( noLabels, appExpr );
+      }
+      thunkFunc->get_statements()->get_kids().push_back( appStmt );
+      stmtsToAdd.push_back( new DeclStmt( noLabels, thunkFunc ) );
+      return new AddressExpr( new VariableExpr( thunkFunc ) );
+    } else {
+      return actual;
+    }
+  } else {
+    return actual;
+  }
+}
+
+void
+Specialize::handleExplicitParams( ApplicationExpr *appExpr )
+{
+  // create thunks for the explicit parameters
+  assert( !appExpr->get_function()->get_results().empty() );
+  PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() );
+  assert( pointer );
+  FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() );
+  std::list< DeclarationWithType* >::iterator formal;
+  std::list< Expression* >::iterator actual;
+  for( formal = function->get_parameters().begin(), actual = appExpr->get_args().begin(); formal != function->get_parameters().end() && actual != appExpr->get_args().end(); ++formal, ++actual ) {
+    *actual = doSpecialization( (*formal)->get_type(), *actual, &appExpr->get_inferParams() );
+  }
+}
+
+Expression* 
+Specialize::mutate(ApplicationExpr *appExpr)
+{
+  appExpr->get_function()->acceptMutator( *this );
+  mutateAll( appExpr->get_args(), *this );
+  
+  // create thunks for the inferred parameters
+  for( InferredParams::iterator inferParam = appExpr->get_inferParams().begin(); inferParam != appExpr->get_inferParams().end(); ++inferParam ) {
+    inferParam->second.expr = doSpecialization( inferParam->second.formalType, inferParam->second.expr, &appExpr->get_inferParams() );
+  }
+  
+  handleExplicitParams(appExpr);
+  
+  return appExpr;
+}
+
+Expression* 
+Specialize::mutate(AddressExpr *addrExpr)
+{
+  addrExpr->get_arg()->acceptMutator( *this );
+  addrExpr->set_arg( doSpecialization( addrExpr->get_results().front(), addrExpr->get_arg() ) );
+  return addrExpr;
+}
+
+Expression* 
+Specialize::mutate(CastExpr *castExpr)
+{
+  castExpr->get_arg()->acceptMutator( *this );
+  castExpr->set_arg( doSpecialization( castExpr->get_results().front(), castExpr->get_arg() ) );
+  return castExpr;
+}
+
+Expression* 
+Specialize::mutate(LogicalExpr *logicalExpr)
+{
+  return logicalExpr;
+}
+
+Expression* 
+Specialize::mutate(ConditionalExpr *condExpr)
+{
+  return condExpr;
+}
+
+Expression* 
+Specialize::mutate(CommaExpr *commaExpr)
+{
+  return commaExpr;
+}
+
+} // namespace GenPoly
Index: translator/GenPoly/Specialize.h
===================================================================
--- translator/GenPoly/Specialize.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/Specialize.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,21 @@
+/*
+ * This file is part of the Cforall project
+ *
+ * $Id: Specialize.h,v 1.2 2005/08/29 20:14:13 rcbilson Exp $
+ *
+ */
+
+#ifndef GENPOLY_SPECIALIZE_H
+#define GENPOLY_SPECIALIZE_H
+
+#include <list>
+
+#include "SynTree/SynTree.h"
+
+namespace GenPoly {
+
+void convertSpecializations( std::list< Declaration* >& translationUnit );
+
+} // namespace GenPoly
+
+#endif /* #ifndef GENPOLY_SPECIALIZE_H */
Index: translator/GenPoly/module.mk
===================================================================
--- translator/GenPoly/module.mk	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/GenPoly/module.mk	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,9 @@
+SRC += GenPoly/Box.cc \
+       GenPoly/GenPoly.cc \
+       GenPoly/PolyMutator.cc \
+       GenPoly/ScrubTyVars.cc \
+       GenPoly/Lvalue.cc \
+       GenPoly/Specialize.cc \
+       GenPoly/CopyParams.cc \
+       GenPoly/FindFunction.cc
+