Merge #427

427: Fix duplicate function generation in the backend r=philberty a=philberty

Fix duplicated function generation for generics
    
When emitting the backend IR we need to check if we have already compiled
one already. This is all due to the fact when we do generic substitutions
in type resolution its only upon usage of a function the function is
substituted it gains a new unique ty_ref HIR ID to make sure new
substituted versions of a type have unique ids.
    
Fixes #403

Co-authored-by: Philip Herron <philip.herron@embecosm.com>

8 files changed, 156 insertions, 82 deletions

diff --git a/gcc/rust/backend/rust-compile-context.h b/gcc/rust/backend/rust-compile-context.h
index 7db4ea2..45fb6c2 100644
--- a/gcc/rust/backend/rust-compile-context.h
+++ b/gcc/rust/backend/rust-compile-context.h
@@ -157,13 +157,38 @@ public:
     return true;
   }
 
-  void insert_function_decl (HirId id, ::Bfunction *fn)
+  void insert_function_decl (HirId id, ::Bfunction *fn,
+			     const TyTy::BaseType *ref)
   {
+    rust_assert (compiled_fn_map.find (id) == compiled_fn_map.end ());
     compiled_fn_map[id] = fn;
+    if (ref != nullptr)
+      {
+	std::pair<HirId, ::Bfunction *> elem (id, fn);
+	mono_fns[ref] = std::move (elem);
+      }
   }
 
-  bool lookup_function_decl (HirId id, ::Bfunction **fn)
+  bool lookup_function_decl (HirId id, ::Bfunction **fn,
+			     const TyTy::BaseType *ref = nullptr)
   {
+    // for for any monomorphized fns
+    if (ref != nullptr)
+      {
+	for (auto it = mono_fns.begin (); it != mono_fns.end (); it++)
+	  {
+	    std::pair<HirId, ::Bfunction *> &val = it->second;
+	    const TyTy::BaseType *r = it->first;
+	    if (ref->is_equal (*r))
+	      {
+		*fn = val.second;
+
+		return true;
+	      }
+	  }
+	return false;
+      }
+
     auto it = compiled_fn_map.find (id);
     if (it == compiled_fn_map.end ())
       return false;
@@ -282,6 +307,7 @@ private:
   std::vector< ::Bvariable *> loop_value_stack;
   std::vector< ::Blabel *> loop_begin_labels;
   std::map<const TyTy::BaseType *, std::pair<HirId, ::Btype *> > mono;
+  std::map<const TyTy::BaseType *, std::pair<HirId, ::Bfunction *> > mono_fns;
 
   // To GCC middle-end
   std::vector< ::Btype *> type_decls;
diff --git a/gcc/rust/backend/rust-compile-implitem.h b/gcc/rust/backend/rust-compile-implitem.h
index f2caa2e..b071d94 100644
--- a/gcc/rust/backend/rust-compile-implitem.h
+++ b/gcc/rust/backend/rust-compile-implitem.h
@@ -66,17 +66,6 @@ public:
     if (!compile_fns)
       return;
 
-    // items can be forward compiled which means we may not need to invoke this
-    // code
-    Bfunction *lookup = nullptr;
-    if (ctx->lookup_function_decl (function.get_mappings ().get_hirid (),
-				   &lookup))
-      {
-	// has this been added to the list then it must be finished
-	if (ctx->function_completed (lookup))
-	  return;
-      }
-
     TyTy::BaseType *fntype_tyty;
     if (!ctx->get_tyctx ()->lookup_type (function.get_mappings ().get_hirid (),
 					 &fntype_tyty))
@@ -86,28 +75,43 @@ public:
 	return;
       }
 
-    if (fntype_tyty->get_kind () != TyTy::TypeKind::FNDEF)
-      {
-	rust_error_at (function.get_locus (), "invalid TyTy for function item");
-	return;
-      }
-
+    rust_assert (fntype_tyty->get_kind () == TyTy::TypeKind::FNDEF);
     TyTy::FnType *fntype = static_cast<TyTy::FnType *> (fntype_tyty);
     if (fntype->has_subsititions_defined ())
       {
-	// we cant do anything for this only when it is used
+	// we cant do anything for this only when it is used and a concrete type
+	// is given
 	if (concrete == nullptr)
 	  return;
 	else
 	  {
 	    rust_assert (concrete->get_kind () == TyTy::TypeKind::FNDEF);
 	    fntype = static_cast<TyTy::FnType *> (concrete);
+	  }
+      }
 
-	    // override the Hir Lookups for the substituions in this context
-	    fntype->override_context ();
+    // items can be forward compiled which means we may not need to invoke this
+    // code. We might also have already compiled this generic function as well.
+    Bfunction *lookup = nullptr;
+    if (ctx->lookup_function_decl (fntype->get_ty_ref (), &lookup, fntype))
+      {
+	// has this been added to the list then it must be finished
+	if (ctx->function_completed (lookup))
+	  {
+	    Bfunction *dummy = nullptr;
+	    if (!ctx->lookup_function_decl (fntype->get_ty_ref (), &dummy))
+	      ctx->insert_function_decl (fntype->get_ty_ref (), lookup, fntype);
+
+	    return;
 	  }
       }
 
+    if (fntype->has_subsititions_defined ())
+      {
+	// override the Hir Lookups for the substituions in this context
+	fntype->override_context ();
+      }
+
     // convert to the actual function type
     ::Btype *compiled_fn_type = TyTyResolveCompile::compile (ctx, fntype);
 
@@ -126,7 +130,7 @@ public:
     Bfunction *fndecl
       = ctx->get_backend ()->function (compiled_fn_type, fn_identifier,
 				       asm_name, flags, function.get_locus ());
-    ctx->insert_function_decl (fntype->get_ty_ref (), fndecl);
+    ctx->insert_function_decl (fntype->get_ty_ref (), fndecl, fntype);
 
     // setup the params
     TyTy::BaseType *tyret = fntype->get_return_type ();
@@ -247,17 +251,6 @@ public:
     if (!compile_fns)
       return;
 
-    // items can be forward compiled which means we may not need to invoke this
-    // code
-    Bfunction *lookup = nullptr;
-    if (ctx->lookup_function_decl (method.get_mappings ().get_hirid (),
-				   &lookup))
-      {
-	// has this been added to the list then it must be finished
-	if (ctx->function_completed (lookup))
-	  return;
-      }
-
     TyTy::BaseType *fntype_tyty;
     if (!ctx->get_tyctx ()->lookup_type (method.get_mappings ().get_hirid (),
 					 &fntype_tyty))
@@ -267,28 +260,43 @@ public:
 	return;
       }
 
-    if (fntype_tyty->get_kind () != TyTy::TypeKind::FNDEF)
-      {
-	rust_error_at (method.get_locus (), "invalid TyTy for function item");
-	return;
-      }
-
+    rust_assert (fntype_tyty->get_kind () == TyTy::TypeKind::FNDEF);
     TyTy::FnType *fntype = static_cast<TyTy::FnType *> (fntype_tyty);
     if (fntype->has_subsititions_defined ())
       {
-	// we cant do anything for this only when it is used
+	// we cant do anything for this only when it is used and a concrete type
+	// is given
 	if (concrete == nullptr)
 	  return;
 	else
 	  {
 	    rust_assert (concrete->get_kind () == TyTy::TypeKind::FNDEF);
 	    fntype = static_cast<TyTy::FnType *> (concrete);
+	  }
+      }
 
-	    // override the Hir Lookups for the substituions in this context
-	    fntype->override_context ();
+    // items can be forward compiled which means we may not need to invoke this
+    // code. We might also have already compiled this generic function as well.
+    Bfunction *lookup = nullptr;
+    if (ctx->lookup_function_decl (fntype->get_ty_ref (), &lookup, fntype))
+      {
+	// has this been added to the list then it must be finished
+	if (ctx->function_completed (lookup))
+	  {
+	    Bfunction *dummy = nullptr;
+	    if (!ctx->lookup_function_decl (fntype->get_ty_ref (), &dummy))
+	      ctx->insert_function_decl (fntype->get_ty_ref (), lookup, fntype);
+
+	    return;
 	  }
       }
 
+    if (fntype->has_subsititions_defined ())
+      {
+	// override the Hir Lookups for the substituions in this context
+	fntype->override_context ();
+      }
+
     // convert to the actual function type
     ::Btype *compiled_fn_type = TyTyResolveCompile::compile (ctx, fntype);
 
@@ -307,7 +315,7 @@ public:
     Bfunction *fndecl
       = ctx->get_backend ()->function (compiled_fn_type, fn_identifier,
 				       asm_name, flags, method.get_locus ());
-    ctx->insert_function_decl (fntype->get_ty_ref (), fndecl);
+    ctx->insert_function_decl (fntype->get_ty_ref (), fndecl, fntype);
 
     // setup the params
     TyTy::BaseType *tyret = fntype->get_return_type ();
diff --git a/gcc/rust/backend/rust-compile-item.h b/gcc/rust/backend/rust-compile-item.h
index 5a7d846..c3dc279 100644
--- a/gcc/rust/backend/rust-compile-item.h
+++ b/gcc/rust/backend/rust-compile-item.h
@@ -92,17 +92,6 @@ public:
     if (!compile_fns)
       return;
 
-    // items can be forward compiled which means we may not need to invoke this
-    // code
-    Bfunction *lookup = nullptr;
-    if (ctx->lookup_function_decl (function.get_mappings ().get_hirid (),
-				   &lookup))
-      {
-	// has this been added to the list then it must be finished
-	if (ctx->function_completed (lookup))
-	  return;
-      }
-
     TyTy::BaseType *fntype_tyty;
     if (!ctx->get_tyctx ()->lookup_type (function.get_mappings ().get_hirid (),
 					 &fntype_tyty))
@@ -112,28 +101,43 @@ public:
 	return;
       }
 
-    if (fntype_tyty->get_kind () != TyTy::TypeKind::FNDEF)
-      {
-	rust_error_at (function.get_locus (), "invalid TyTy for function item");
-	return;
-      }
-
+    rust_assert (fntype_tyty->get_kind () == TyTy::TypeKind::FNDEF);
     TyTy::FnType *fntype = static_cast<TyTy::FnType *> (fntype_tyty);
     if (fntype->has_subsititions_defined ())
       {
-	// we cant do anything for this only when it is used
+	// we cant do anything for this only when it is used and a concrete type
+	// is given
 	if (concrete == nullptr)
 	  return;
 	else
 	  {
 	    rust_assert (concrete->get_kind () == TyTy::TypeKind::FNDEF);
 	    fntype = static_cast<TyTy::FnType *> (concrete);
+	  }
+      }
 
-	    // override the Hir Lookups for the substituions in this context
-	    fntype->override_context ();
+    // items can be forward compiled which means we may not need to invoke this
+    // code. We might also have already compiled this generic function as well.
+    Bfunction *lookup = nullptr;
+    if (ctx->lookup_function_decl (fntype->get_ty_ref (), &lookup, fntype))
+      {
+	// has this been added to the list then it must be finished
+	if (ctx->function_completed (lookup))
+	  {
+	    Bfunction *dummy = nullptr;
+	    if (!ctx->lookup_function_decl (fntype->get_ty_ref (), &dummy))
+	      ctx->insert_function_decl (fntype->get_ty_ref (), lookup, fntype);
+
+	    return;
 	  }
       }
 
+    if (fntype->has_subsititions_defined ())
+      {
+	// override the Hir Lookups for the substituions in this context
+	fntype->override_context ();
+      }
+
     ::Btype *compiled_fn_type = TyTyResolveCompile::compile (ctx, fntype);
 
     unsigned int flags = 0;
@@ -155,7 +159,7 @@ public:
     Bfunction *fndecl
       = ctx->get_backend ()->function (compiled_fn_type, ir_symbol_name,
 				       asm_name, flags, function.get_locus ());
-    ctx->insert_function_decl (fntype->get_ty_ref (), fndecl);
+    ctx->insert_function_decl (fntype->get_ty_ref (), fndecl, fntype);
 
     // setup the params
     TyTy::BaseType *tyret = fntype->get_return_type ();
diff --git a/gcc/rust/rust-diagnostics.h b/gcc/rust/rust-diagnostics.h
index d861267..81f558a 100644
--- a/gcc/rust/rust-diagnostics.h
+++ b/gcc/rust/rust-diagnostics.h
@@ -114,10 +114,13 @@ struct Error
 	 ...) /*RUST_ATTRIBUTE_GCC_DIAG (2, 3)*/ RUST_ATTRIBUTE_GCC_DIAG (3, 4);
 
   // Irreversibly emits the error as an error.
-  void emit_error () const { rust_error_at (locus, message.c_str ()); }
+  void emit_error () const { rust_error_at (locus, "%s", message.c_str ()); }
 
   // Irreversibly emits the error as a fatal error.
-  void emit_fatal_error () const { rust_fatal_error (locus, message.c_str ()); }
+  void emit_fatal_error () const
+  {
+    rust_fatal_error (locus, "%s", message.c_str ());
+  }
 };
 } // namespace Rust
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check-implitem.h b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
index f961bba..2f54d0c 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-implitem.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
@@ -112,7 +112,8 @@ public:
       }
 
     auto fnType = new TyTy::FnType (function.get_mappings ().get_hirid (),
-				    false, std::move (params), ret_type,
+				    function.get_function_name (), false,
+				    std::move (params), ret_type,
 				    std::move (substitutions));
     context->insert_type (function.get_mappings (), fnType);
   }
@@ -189,9 +190,10 @@ public:
 	context->insert_type (param.get_mappings (), param_tyty);
       }
 
-    auto fnType = new TyTy::FnType (method.get_mappings ().get_hirid (), true,
-				    std::move (params), ret_type,
-				    std::move (substitutions));
+    auto fnType
+      = new TyTy::FnType (method.get_mappings ().get_hirid (),
+			  method.get_method_name (), true, std::move (params),
+			  ret_type, std::move (substitutions));
     context->insert_type (method.get_mappings (), fnType);
   }
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check-toplevel.h b/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
index ef940c1..e01b46f 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
@@ -229,7 +229,8 @@ public:
       }
 
     auto fnType = new TyTy::FnType (function.get_mappings ().get_hirid (),
-				    false, std::move (params), ret_type,
+				    function.get_function_name (), false,
+				    std::move (params), ret_type,
 				    std::move (substitutions));
     context->insert_type (function.get_mappings (), fnType);
   }
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index e74ab93..0859570 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -679,9 +679,21 @@ FnType::is_equal (const BaseType &other) const
     return false;
 
   auto other2 = static_cast<const FnType &> (other);
+  if (get_identifier ().compare (other2.get_identifier ()) != 0)
+    return false;
+
   if (!get_return_type ()->is_equal (*other2.get_return_type ()))
     return false;
 
+  if (has_subsititions_defined () != other2.has_subsititions_defined ())
+    return false;
+
+  if (has_subsititions_defined ())
+    {
+      if (get_num_substitutions () != other2.get_num_substitutions ())
+	return false;
+    }
+
   if (num_params () != other2.num_params ())
     return false;
 
@@ -703,9 +715,10 @@ FnType::clone ()
     cloned_params.push_back (
       std::pair<HIR::Pattern *, BaseType *> (p.first, p.second->clone ()));
 
-  return new FnType (get_ref (), get_ty_ref (), is_method_flag,
-		     std::move (cloned_params), get_return_type ()->clone (),
-		     clone_substs (), get_combined_refs ());
+  return new FnType (get_ref (), get_ty_ref (), get_identifier (),
+		     is_method_flag, std::move (cloned_params),
+		     get_return_type ()->clone (), clone_substs (),
+		     get_combined_refs ());
 }
 
 FnType *
@@ -1381,10 +1394,22 @@ ParamType::resolve () const
 bool
 ParamType::is_equal (const BaseType &other) const
 {
-  if (!can_resolve ())
-    return BaseType::is_equal (other);
+  if (get_kind () != other.get_kind ())
+    {
+      if (!can_resolve ())
+	return false;
+
+      return resolve ()->is_equal (other);
+    }
+
+  auto other2 = static_cast<const ParamType &> (other);
+  if (can_resolve () != other2.can_resolve ())
+    return false;
+
+  if (can_resolve ())
+    return resolve ()->can_eq (other2.resolve ());
 
-  return resolve ()->is_equal (other);
+  return get_symbol ().compare (other2.get_symbol ()) == 0;
 }
 
 ParamType *
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index aa709ec..5acc9e7 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -855,24 +855,26 @@ private:
 class FnType : public BaseType, public SubstitutionRef
 {
 public:
-  FnType (HirId ref, bool is_method,
+  FnType (HirId ref, std::string identifier, bool is_method,
 	  std::vector<std::pair<HIR::Pattern *, BaseType *> > params,
 	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
 	  std::set<HirId> refs = std::set<HirId> ())
     : BaseType (ref, ref, TypeKind::FNDEF, refs),
       SubstitutionRef (std::move (subst_refs),
 		       SubstitutionArgumentMappings::error ()),
-      params (std::move (params)), type (type), is_method_flag (is_method)
+      params (std::move (params)), type (type), is_method_flag (is_method),
+      identifier (identifier)
   {}
 
-  FnType (HirId ref, HirId ty_ref, bool is_method,
+  FnType (HirId ref, HirId ty_ref, std::string identifier, bool is_method,
 	  std::vector<std::pair<HIR::Pattern *, BaseType *> > params,
 	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
 	  std::set<HirId> refs = std::set<HirId> ())
     : BaseType (ref, ty_ref, TypeKind::FNDEF, refs),
       SubstitutionRef (std::move (subst_refs),
 		       SubstitutionArgumentMappings::error ()),
-      params (params), type (type), is_method_flag (is_method)
+      params (params), type (type), is_method_flag (is_method),
+      identifier (identifier)
   {}
 
   void accept_vis (TyVisitor &vis) override;
@@ -881,6 +883,8 @@ public:
 
   std::string get_name () const override final { return as_string (); }
 
+  std::string get_identifier () const { return identifier; }
+
   BaseType *unify (BaseType *other) override;
   bool can_eq (BaseType *other) override;
 
@@ -947,6 +951,7 @@ private:
   std::vector<std::pair<HIR::Pattern *, BaseType *> > params;
   BaseType *type;
   bool is_method_flag;
+  std::string identifier;
 };
 
 class FnPtr : public BaseType