RISC-V: Implement TARGET_COMPUTE_MULTILIB

Use TARGET_COMPUTE_MULTILIB to search the multi-lib reuse for riscv*-*-elf*,
according following rules:

 1. Check ABI is same.
 2. Check both has atomic extension or both don't have atomic extension.
    - Because mix soft and hard atomic operation doesn't make sense and
      won't work as expect.
 3. Check current arch is superset of the target multi-lib arch.
    - It might result slower performance or larger code size, but it
      safe to run.
 4. Pick most match multi-lib set if more than one multi-lib are pass
    the above checking.

Example for how to select multi-lib:
  We build code with -march=rv32imaf and -mabi=ilp32, and we have
  following 5 multi-lib set:

    1. rv32ia/ilp32
    2. rv32ima/ilp32
    3. rv32imf/ilp32
    4. rv32imaf/ilp32f
    5. rv32imafd/ilp32

  The first and second multi-lib is safe to like, 3rd multi-lib can't
  re-use becasue it don't have atomic extension, which is mismatch according
  rule 2, and the 4th multi-lib can't re-use too due to the ABI mismatch,
  the last multi-lib can't use since current arch is not superset of the
  arch of multi-lib.

And emit error if not found suitable multi-lib set, the error message
only emit when link with standard libraries.

Example for when error will be emitted:

  $ riscv64-unknown-elf-gcc -print-multi-lib
  .;
  rv32i/ilp32;@march=rv32i@mabi=ilp32
  rv32im/ilp32;@march=rv32im@mabi=ilp32
  rv32iac/ilp32;@march=rv32iac@mabi=ilp32
  rv32imac/ilp32;@march=rv32imac@mabi=ilp32
  rv32imafc/ilp32f;@march=rv32imafc@mabi=ilp32f
  rv64imac/lp64;@march=rv64imac@mabi=lp64

  // No actual linking, so no error emitted.
  $ riscv64-unknown-elf-gcc -print-multi-directory -march=rv32ia -mabi=ilp32
  .

  // Link to default libc and libgcc, so check the multi-lib, and emit
  // error because not found suitable multilib.
  $ riscv64-unknown-elf-gcc -march=rv32ia -mabi=ilp32 ~/hello.c
  riscv64-unknown-elf-gcc: fatal error: can't found suitable multilib set for '-march=rv32ia'/'-mabi=ilp32'
  compilation terminated.

  // No error emitted, because not link to stdlib.
  $ riscv64-unknown-elf-gcc -march=rv32ia -mabi=ilp32 ~/hello.c -nostdlib

  // No error emitted, because compile only.
  $ riscv64-unknown-elf-gcc -march=rv32ia -mabi=ilp32 ~/hello.c -c

gcc/ChangeLog:

	* common/config/riscv/riscv-common.cc: Include <vector>.
	(struct riscv_multi_lib_info_t): New.
	(riscv_subset_list::match_score): Ditto.
	(find_last_appear_switch): Ditto.
	(prefixed_with): Ditto.
	(struct multi_lib_info_t): Ditto.
	(riscv_current_arch_str): Ditto.
	(riscv_current_abi_str): Ditto.
	(riscv_multi_lib_info_t::parse): Ditto.
	(riscv_check_cond): Ditto.
	(riscv_check_conds): Ditto.
	(riscv_compute_multilib): Ditto.
	(TARGET_COMPUTE_MULTILIB): Defined.
	* config/riscv/elf.h (LIB_SPEC): Call riscv_multi_lib_check if
	doing link.
	(RISCV_USE_CUSTOMISED_MULTI_LIB): New.
	* config/riscv/riscv.h (riscv_multi_lib_check): New.
	(EXTRA_SPEC_FUNCTIONS): Add riscv_multi_lib_check.
	* config/riscv/riscv-subset.h (riscv_subset_list::match_score): New.

4 files changed, 387 insertions, 2 deletions

diff --git a/gcc/common/config/riscv/riscv-common.cc b/gcc/common/config/riscv/riscv-common.cc
index 4ee1b31..cb3a5d2 100644
--- a/gcc/common/config/riscv/riscv-common.cc
+++ b/gcc/common/config/riscv/riscv-common.cc
@@ -18,6 +18,7 @@ along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
 #include <sstream>
+#include <vector>
 
 #define INCLUDE_STRING
 #include "config.h"
@@ -230,6 +231,26 @@ const riscv_subset_list *riscv_current_subset_list ()
   return current_subset_list;
 }
 
+/* struct for recording multi-lib info.  */
+struct riscv_multi_lib_info_t {
+  std::string path;
+  std::string arch_str;
+  std::string abi_str;
+  std::vector<std::string> conds;
+  riscv_subset_list *subset_list;
+
+  static bool parse (struct riscv_multi_lib_info_t *,
+		     const std::string &,
+		     const std::vector<std::string> &);
+};
+
+/* Flag for checking if there is no suitable multi-lib found.  */
+static bool riscv_no_matched_multi_lib;
+
+/* Used for record value of -march and -mabi.  */
+static std::string riscv_current_arch_str;
+static std::string riscv_current_abi_str;
+
 riscv_subset_t::riscv_subset_t ()
   : name (), major_version (0), minor_version (0), next (NULL),
     explicit_version_p (false), implied_p (false)
@@ -255,6 +276,42 @@ riscv_subset_list::~riscv_subset_list ()
     }
 }
 
+/* Compute the match score of two arch string, return 0 if incompatible.  */
+int
+riscv_subset_list::match_score (riscv_subset_list *list) const
+{
+  riscv_subset_t *s;
+  int score = 0;
+  bool has_a_ext, list_has_a_ext;
+
+  /* Impossible to match if XLEN is different.  */
+  if (list->m_xlen != this->m_xlen)
+    return 0;
+
+  /* There is different code gen in libstdc++ and libatomic between w/ A-ext
+     and w/o A-ext, and it not work if using soft and hard atomic mechanism
+     at same time, so they are incompatible.  */
+  has_a_ext = this->lookup ("a") != NULL;
+  list_has_a_ext = list->lookup ("a") != NULL;
+
+  if (has_a_ext != list_has_a_ext)
+    return 0;
+
+
+  /* list must be subset of current this list, otherwise it not safe to
+     link.
+     TODO: We might give different weight for each extension, but the rule could
+	   be complicated.
+     TODO: We might consider the version of each extension.  */
+  for (s = list->m_head; s != NULL; s = s->next)
+    if (this->lookup (s->name.c_str ()) != NULL)
+      score++;
+    else
+      return 0;
+
+  return score;
+}
+
 /* Get the rank for single-letter subsets, lower value meaning higher
    priority.  */
 
@@ -1305,6 +1362,326 @@ riscv_expand_arch_from_cpu (int argc ATTRIBUTE_UNUSED,
   return xasprintf ("-march=%s", arch.c_str());
 }
 
+/* Find last switch with the prefix, options are take last one in general,
+   return NULL if not found, and return the option value if found, it could
+   return empty string if the option has no value.  */
+
+static const char *
+find_last_appear_switch (
+  const struct switchstr *switches,
+  int n_switches,
+  const char *prefix)
+{
+  int i;
+  size_t len = strlen (prefix);
+
+  for (i = 0; i < n_switches; ++i)
+    {
+      const struct switchstr *this_switch = &switches[n_switches - i - 1];
+
+      if (this_switch->live_cond & SWITCH_FALSE)
+	continue;
+
+      if (strncmp (this_switch->part1, prefix, len) == 0)
+	return this_switch->part1 + len;
+    }
+
+  return NULL;
+}
+
+/* Utils functions to check STR is start with PREFIX or not.  */
+
+static bool
+prefixed_with (const std::string &str, const char *prefix)
+{
+  return strncmp (prefix, str.c_str (), strlen (prefix)) == 0;
+}
+
+/* Parse the path and cond string into riscv_multi_lib_info_t, return false
+   if parsing failed. */
+
+bool
+riscv_multi_lib_info_t::parse (
+  struct riscv_multi_lib_info_t *multi_lib_info,
+  const std::string &path,
+  const std::vector<std::string> &conds)
+{
+  const char *default_arch_str = STRINGIZING (TARGET_RISCV_DEFAULT_ARCH);
+  const char *default_abi_str = STRINGIZING (TARGET_RISCV_DEFAULT_ABI);
+  multi_lib_info->conds = conds;
+  if (path == ".")
+    {
+      multi_lib_info->arch_str = default_arch_str;
+      multi_lib_info->abi_str = default_abi_str;
+    }
+  else
+    {
+      std::vector<std::string>::const_iterator itr;
+      for (itr = conds.begin (); itr != conds.end (); ++itr)
+	if (prefixed_with (*itr, "march="))
+	  multi_lib_info->arch_str = itr->c_str () + strlen ("march=");
+	else if (prefixed_with (*itr, "mabi="))
+	  multi_lib_info->abi_str = itr->c_str () + strlen ("mabi=");
+
+	/* Skip this multi-lib if this configuration is exactly same as
+	   default multi-lib settings.  */
+      if (multi_lib_info->arch_str == default_arch_str
+	  && multi_lib_info->abi_str == default_abi_str)
+	return false;
+    }
+
+  multi_lib_info->subset_list =
+    riscv_subset_list::parse (multi_lib_info->arch_str.c_str (), input_location);
+
+  return true;
+}
+
+/* Report error if not found suitable multilib.  */
+const char *
+riscv_multi_lib_check (int argc ATTRIBUTE_UNUSED,
+		       const char **argv ATTRIBUTE_UNUSED)
+{
+  if (riscv_no_matched_multi_lib)
+    fatal_error (
+      input_location,
+      "Can't find suitable multilib set for %<-march=%s%>/%<-mabi=%s%>",
+      riscv_current_arch_str.c_str (),
+      riscv_current_abi_str.c_str ());
+
+  return "";
+}
+
+/* Checking ARG is not appeared in SWITCHES if NOT_ARG is set or
+   ARG is appeared if NOT_ARG is not set.  */
+
+static bool
+riscv_check_cond (
+  const struct switchstr *switches,
+  int n_switches,
+  const std::string &arg,
+  bool not_arg)
+{
+  int i;
+  for (i = 0; i < n_switches; ++i)
+    {
+      const struct switchstr *this_switch = &switches[n_switches - i - 1];
+
+      if ((this_switch->live_cond & SWITCH_IGNORE) != 0)
+	continue;
+
+      if (this_switch->live_cond & SWITCH_FALSE)
+	continue;
+
+      /* ARG should not appear if NOT_ARG is set.  */
+      if (arg == this_switch->part1)
+	return not_arg ? false : true;
+    }
+
+  /* Not found ARG? that's ok if NOT_ARG is not set.  */
+  return not_arg ? true : false;
+}
+
+/* Check the other cond is found or not, return -1 if we should reject this
+   multi-lib option set, otherwise return updated MATCH_SCORE.   */
+
+static int
+riscv_check_conds (
+  const struct switchstr *switches,
+  int n_switches,
+  int match_score,
+  const std::vector<std::string> &conds)
+{
+  bool not_arg;
+  bool ok;
+  int ok_count = 0;
+  std::vector<std::string>::const_iterator itr;
+  const char *checking_arg;
+
+  if (match_score == 0)
+    return 0;
+
+  for (itr = conds.begin (); itr != conds.end (); ++itr)
+    {
+      /* We'll check march= and mabi= in ohter place.  */
+      if (prefixed_with (*itr, "march=") || prefixed_with (*itr, "mabi="))
+	continue;
+
+      checking_arg = itr->c_str ();
+      if (checking_arg[0] == '!')
+	{
+	  not_arg = true;
+	  /* Skip '!'. */
+	  checking_arg = checking_arg + 1;
+	}
+      else
+	not_arg = false;
+
+      ok = riscv_check_cond (switches, n_switches, checking_arg, not_arg);
+
+      if (!ok)
+	return -1;
+
+      ok_count++;
+    }
+
+  /* 100 is magic number, it's just used for make sure this multi-lib has
+     higher priority if we found any some option is listed in the option check
+     list. */
+  return match_score + ok_count * 100;
+}
+
+/* We only override this in bare-metal toolchain.  */
+#ifdef RISCV_USE_CUSTOMISED_MULTI_LIB
+
+/* Implement TARGET_COMPUTE_MULTILIB.  */
+static const char *
+riscv_compute_multilib (
+  const struct switchstr *switches,
+  int n_switches,
+  const char *multilib_dir,
+  const char *multilib_defaults ATTRIBUTE_UNUSED,
+  const char *multilib_select,
+  const char *multilib_matches ATTRIBUTE_UNUSED,
+  const char *multilib_exclusions ATTRIBUTE_UNUSED,
+  const char *multilib_reuse ATTRIBUTE_UNUSED)
+{
+  const char *p;
+  const char *this_path;
+  size_t this_path_len;
+  bool result;
+  riscv_no_matched_multi_lib = false;
+  riscv_subset_list *subset_list = NULL;
+
+  std::vector<riscv_multi_lib_info_t> multilib_infos;
+  std::vector<std::string> option_conds;
+  std::string option_cond;
+  riscv_multi_lib_info_t multilib_info;
+
+  /* Already found suitable, multi-lib, just use that.  */
+  if (multilib_dir != NULL)
+    return multilib_dir;
+
+  /* Find march.  */
+  riscv_current_arch_str =
+    find_last_appear_switch (switches, n_switches, "march=");
+  /* Find mabi.  */
+  riscv_current_abi_str =
+    find_last_appear_switch (switches, n_switches, "mabi=");
+
+  /* Failed to find -march or -mabi, but it should not happened since we have
+     set both in OPTION_DEFAULT_SPECS.  */
+  if (riscv_current_arch_str.empty () || riscv_current_abi_str.empty ())
+    return multilib_dir;
+
+  subset_list = riscv_subset_list::parse (riscv_current_arch_str.c_str (),
+					  input_location);
+
+  /* Failed to parse -march, fallback to using what gcc use.  */
+  if (subset_list == NULL)
+    return multilib_dir;
+
+  /* Parsing MULTILIB_SELECT, ignore MULTILIB_REUSE here, we have our own rules.
+     TODO: most codes are grab from gcc.c, maybe we should refine that?  */
+  p = multilib_select;
+
+  while (*p != '\0')
+    {
+      /* Ignore newlines.  */
+      if (*p == '\n')
+	{
+	  ++p;
+	  continue;
+	}
+
+      /* Format of each multilib:
+	 <path> <opt1> <opt2> ... <optN>;  */
+      /* Get the path.  */
+      this_path = p;
+      while (*p != ' ')
+	{
+	  if (*p == '\0')
+	    {
+	      fatal_error (input_location, "multilib select %qs %qs is invalid",
+			   multilib_select, multilib_reuse);
+	    }
+	  ++p;
+	}
+
+      this_path_len = p - this_path;
+      multilib_info.path = std::string (this_path, this_path_len);
+
+      option_conds.clear ();
+      /* Pasrse option check list into vector<string>.
+	 e.g. "march=rv64imafd mabi=lp64 !mcmodel=medany" to
+	      ["march=rv64imafd", "mabi=lp64", "!mcmodel=medany"].  */
+      while (*p != ';')
+	{
+	  option_cond = "";
+	  /* Skip space.  */
+	  while (*p == ' ') p++;
+
+	  while (*p && *p != ' ' && *p != ';')
+	      option_cond.push_back (*p++);
+
+	  /* Ignore `!march=` and `!mabi=`, we will handle march and mabi
+	     later. */
+	  if (option_cond.size ()
+	      && !prefixed_with (option_cond, "!march=")
+	      && !prefixed_with (option_cond, "!mabi="))
+	    option_conds.push_back (option_cond);
+	}
+
+      result =
+	riscv_multi_lib_info_t::parse (
+	  &multilib_info,
+	  std::string (this_path, this_path_len),
+	  option_conds);
+
+      if (result)
+	multilib_infos.push_back (multilib_info);
+
+      p++;
+    }
+
+  int match_score = 0;
+  int max_match_score = 0;
+  int best_match_multi_lib = -1;
+  /* Try to decision which set we should used.  */
+  /* We have 3 level decision tree here, ABI, check input arch/ABI must
+     be superset of multi-lib arch, and other rest option checking.  */
+  for (size_t i = 0; i < multilib_infos.size (); ++i)
+    {
+      /* Check ABI is same first.  */
+      if (riscv_current_abi_str != multilib_infos[i].abi_str)
+	continue;
+
+      /* Found a potential compatible multi-lib setting!
+	 Calculate the match score.  */
+      match_score = subset_list->match_score (multilib_infos[i].subset_list);
+
+      /* Checking other cond in the multi-lib setting.  */
+      match_score = riscv_check_conds (switches,
+				       n_switches,
+				       match_score,
+				       multilib_infos[i].conds);
+
+      /* Record highest match score multi-lib setting.  */
+      if (match_score > max_match_score)
+	best_match_multi_lib = i;
+    }
+
+  if (best_match_multi_lib == -1)
+    {
+      riscv_no_matched_multi_lib = true;
+      return multilib_dir;
+    }
+  else
+    return xstrdup (multilib_infos[best_match_multi_lib].path.c_str ());
+}
+
+#undef TARGET_COMPUTE_MULTILIB
+#define TARGET_COMPUTE_MULTILIB riscv_compute_multilib
+#endif
 
 /* Implement TARGET_OPTION_OPTIMIZATION_TABLE.  */
 static const struct default_options riscv_option_optimization_table[] =
diff --git a/gcc/config/riscv/elf.h b/gcc/config/riscv/elf.h
index f0e865d..f3d767c 100644
--- a/gcc/config/riscv/elf.h
+++ b/gcc/config/riscv/elf.h
@@ -27,10 +27,14 @@ along with GCC; see the file COPYING3.  If not see
 /* Link against Newlib libraries, because the ELF backend assumes Newlib.
    Handle the circular dependence between libc and libgloss. */
 #undef  LIB_SPEC
-#define LIB_SPEC "--start-group -lc %{!specs=nosys.specs:-lgloss} --end-group"
+#define LIB_SPEC \
+  "--start-group -lc %{!specs=nosys.specs:-lgloss} --end-group " \
+  "%{!nostartfiles:%{!nodefaultlibs:%{!nolibc:%{!nostdlib:%:riscv_multi_lib_check()}}}}"
 
 #undef  STARTFILE_SPEC
 #define STARTFILE_SPEC "crt0%O%s crtbegin%O%s"
 
 #undef  ENDFILE_SPEC
 #define ENDFILE_SPEC "crtend%O%s"
+
+#define RISCV_USE_CUSTOMISED_MULTI_LIB 1
diff --git a/gcc/config/riscv/riscv-subset.h b/gcc/config/riscv/riscv-subset.h
index c592650..0bb3a9d 100644
--- a/gcc/config/riscv/riscv-subset.h
+++ b/gcc/config/riscv/riscv-subset.h
@@ -89,6 +89,8 @@ public:
 
   const riscv_subset_t *begin () const {return m_head;};
   const riscv_subset_t *end () const {return NULL;};
+
+  int match_score (riscv_subset_list *) const;
 };
 
 extern const riscv_subset_list *riscv_current_subset_list (void);
diff --git a/gcc/config/riscv/riscv.h b/gcc/config/riscv/riscv.h
index 3ee5a93..e35aaa7 100644
--- a/gcc/config/riscv/riscv.h
+++ b/gcc/config/riscv/riscv.h
@@ -50,11 +50,13 @@ along with GCC; see the file COPYING3.  If not see
 extern const char *riscv_expand_arch (int argc, const char **argv);
 extern const char *riscv_expand_arch_from_cpu (int argc, const char **argv);
 extern const char *riscv_default_mtune (int argc, const char **argv);
+extern const char *riscv_multi_lib_check (int argc, const char **argv);
 
 # define EXTRA_SPEC_FUNCTIONS						\
   { "riscv_expand_arch", riscv_expand_arch },				\
   { "riscv_expand_arch_from_cpu", riscv_expand_arch_from_cpu },		\
-  { "riscv_default_mtune", riscv_default_mtune },
+  { "riscv_default_mtune", riscv_default_mtune },			\
+  { "riscv_multi_lib_check", riscv_multi_lib_check },
 
 /* Support for a compile-time default CPU, et cetera.  The rules are:
    --with-arch is ignored if -march or -mcpu is specified.