2006-08-02 Michael Matz <matz@suse.de>insn-select

	* select-insn.c: New file.
	* tree-pass.h (pass_insn_select): Declare it.
	* passes.c (init_optimization_passes): Call it.
	* Makefile.in (select-insn.o): New target, add it to OBJS-common.

2006-08-02  Michael Matz  <matz@suse.de>
	* Branch "insn-select" created.


git-svn-id: https://gcc.gnu.org/svn/gcc/branches/insn-select@115876 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 345 insertions, 1 deletions

diff --git a/gcc/ChangeLog.insn-select b/gcc/ChangeLog.insn-select
new file mode 100644
index 00000000000..0923359274f
--- /dev/null
+++ b/gcc/ChangeLog.insn-select
@@ -0,0 +1,9 @@
+2006-08-02  Michael Matz  <matz@suse.de>
+
+	* select-insn.c: New file.
+	* tree-pass.h (pass_insn_select): Declare it.
+	* passes.c (init_optimization_passes): Call it.
+	* Makefile.in (select-insn.o): New target, add it to OBJS-common.
+
+2006-08-02  Michael Matz  <matz@suse.de>
+	* Branch "insn-select" created.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index efb19804637..cde8bca88f2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1008,7 +1008,7 @@ OBJS-common = \
  real.o recog.o reg-stack.o regclass.o regmove.o regrename.o		   \
  reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o	   \
  sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o	   \
- see.o simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o		   \
+ see.o select-insn.o simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o		   \
  struct-equiv.o targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
  varasm.o varray.o vec.o version.o vmsdbgout.o xcoffout.o alloc-pool.o	   \
  et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o passes.o	   \
@@ -2489,6 +2489,10 @@ local-alloc.o : local-alloc.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(RTL_H) $(FLAGS_H) $(REGS_H) hard-reg-set.h insn-config.h $(RECOG_H) \
    output.h $(FUNCTION_H) $(INSN_ATTR_H) toplev.h  except.h reload.h $(TM_P_H) \
    $(GGC_H) $(INTEGRATE_H) $(TIMEVAR_H) tree-pass.h
+select-insn.o : select-insn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
+   $(RTL_H) $(FLAGS_H) $(REGS_H) hard-reg-set.h insn-config.h $(RECOG_H) \
+   output.h $(FUNCTION_H) $(INSN_ATTR_H) toplev.h  except.h reload.h $(TM_P_H) \
+   $(GGC_H) $(INTEGRATE_H) timevar.h tree-pass.h
 bitmap.o : bitmap.c $(CONFIG_H) $(SYSTEM_H)  coretypes.h $(TM_H) $(RTL_H) \
    $(FLAGS_H) $(GGC_H) gt-bitmap.h bitmap.h $(OBSTACK_H)
 global.o : global.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
diff --git a/gcc/passes.c b/gcc/passes.c
index fe6f637e868..8ff29ab668e 100644
--- a/gcc/passes.c
+++ b/gcc/passes.c
@@ -656,6 +656,7 @@ init_optimization_passes (void)
   NEXT_PASS (pass_recompute_reg_usage);
   NEXT_PASS (pass_sms);
   NEXT_PASS (pass_sched);
+  NEXT_PASS (pass_insn_select);
   NEXT_PASS (pass_local_alloc);
   NEXT_PASS (pass_global_alloc);
   NEXT_PASS (pass_postreload);
diff --git a/gcc/select-insn.c b/gcc/select-insn.c
new file mode 100644
index 00000000000..57668059536
--- /dev/null
+++ b/gcc/select-insn.c
@@ -0,0 +1,329 @@
+/* Select alternatives for insns and register classes for each pseudo.
+   Copyright (C) 2006  Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "insn-config.h"
+#include "expr.h"
+#include "optabs.h"
+#include "recog.h"
+#include "reload.h"
+#include "regs.h"
+#include "addresses.h"
+#include "hard-reg-set.h"
+#include "flags.h"
+#include "real.h"
+#include "df.h"
+#include "obstack.h"
+#include "output.h"
+#include "function.h"
+#include "toplev.h"
+#include "params.h"
+#include "target.h"
+#include "timevar.h"
+#include "tree-pass.h"
+
+/* This pass runs directly before register allocation and is responsible
+   for selecting a register class for each pseudo register and an alternative
+   for each instruction.  In cases where it's not possible to define
+   one register class for a pseudo (e.g. one used in integer and float
+   context) compensation code will be added so that it will be possible.
+   That will mostly be simple move instructions into and out of new
+   pseudo registers.  */
+
+struct reg_ref
+{
+  /* Assigned register class for this reference.  -1 if not yet assigned.  */
+  int class;
+  /* The operand in which this regref occured.  */
+  rtx op;
+  /* The number of the operand.  */
+  int op_num;
+  /* The number of match_dup refering to this operand.  -1 if a normal
+     match_operand.  */
+  int dup;
+};
+
+/* XXX It's possible the whole pass will be more natural if we would have
+   a mapping of (insn -> insns operands) where each operand would
+   have a list of all reg_ref.  Might make handling of constraints per operand
+   easier.  Perhaps also dealing with match_dups would be easier.  */
+
+#define UNASSIGNED -1
+
+/* Mapping from insn UID to alternative for that insn.  -1 if not
+   yet selected.  */
+static int *uid2alt;
+static struct df *df;
+static struct obstack si_obstack;
+
+/* Sets the goal alternative of INSN to ALTERNATIVE.  This updates
+   the selected regclasses for all register references in this INSN.
+   This functions requires having preprocess_constraints called.  */
+static void
+assign_alt_to_insn (rtx insn, int alternative)
+{
+  int pass;
+  struct df_ref *ref;
+  uid2alt[INSN_UID (insn)] = alternative;
+  for (pass = 0; pass < 2; pass++)
+    for (ref = (pass == 0)
+	       ? DF_INSN_DEFS (df, insn)
+	       : DF_INSN_USES (df, insn);
+	 ref;
+	 ref = ref->next_ref)
+      {
+	struct reg_ref *r = DF_REF_DATA (ref);
+	if (r->dup >= 0)
+	  {
+	    if (dump_file)
+	      {
+		print_inline_rtx (dump_file, DF_REF_REG (ref), 4);
+	        fprintf (dump_file, "     is a match_dup\n");
+	      }
+	    continue;
+	  }
+	if (!r->op)
+	  abort ();
+	/* If the operand to which this ref belongs is itself a register
+	   then this ref's class is the class of this operand.  */
+	if (REG_P (r->op)
+	    || (GET_CODE (r->op) == SUBREG && REG_P (SUBREG_REG (r->op))))
+	  {
+	    struct operand_alternative *op_alt;
+	    op_alt = &recog_op_alt[r->op_num][alternative];
+	    while (op_alt->matches >= 0)
+	      op_alt = &recog_op_alt[op_alt->matches][alternative];
+	    r->class = op_alt->cl;
+	  }
+	/* Otherwise the op is no register but contains this register,
+	   hence it's something more complicated, like a MEM or a mem
+	   address.  We need backends help in determining which class
+	   this regref needs, at least in more complicated cases.  XXX */
+	else
+	  {
+	    /* XXX For now let's use GENERAL_REGS.  It's wrong, and we could
+	       do better even without backend help, like analysing the
+	       structure, and if it's a MEM or an address assign BASE_REGS
+	       or INDEX_REGS, and similar tricks.  */
+	    r->class = GENERAL_REGS;
+	  }
+	if (dump_file)
+	  {
+	    print_inline_rtx (dump_file, DF_REF_REG (ref), 4);
+	    fprintf (dump_file, "     -> %s\n", reg_class_names[r->class]);
+	  }
+      }
+}
+
+/* Set's up some basic information for the given INSN.  Like the initial
+   insn alternative, the local info per register ref and such.  */
+static void
+init_insn (rtx insn)
+{
+  int alt, valid, n_ops, i;
+  struct df_ref *ref;
+
+  /* Allocate the local info for all refs in this insn.  */
+  for (ref = DF_INSN_DEFS (df, insn); ref; ref = ref->next_ref)
+    {
+      struct reg_ref *r = obstack_alloc (&si_obstack, sizeof (struct reg_ref));
+      r->class = -1;
+      r->op = NULL_RTX;
+      r->op_num = -1;
+      r->dup = -1;
+      DF_REF_DATA (ref) = r;
+    }
+  for (ref = DF_INSN_USES (df, insn); ref; ref = ref->next_ref)
+    {
+      struct reg_ref *r = obstack_alloc (&si_obstack, sizeof (struct reg_ref));
+      r->class = -1;
+      r->op = NULL_RTX;
+      r->op_num = -1;
+      r->dup = -1;
+      DF_REF_DATA (ref) = r;
+    }
+  extract_insn (insn);
+  n_ops = recog_data.n_operands;
+
+  /* Determine to which operand each register ref belongs.  */
+  for (i = 0; i < n_ops; i++)
+    if (*recog_data.constraints[i])
+      {
+	int pass;
+	for (pass = 0; pass < 2; pass++)
+	  for (ref = (pass == 0)
+	             ? DF_INSN_DEFS (df, insn)
+	             : DF_INSN_USES (df, insn);
+	       ref;
+	       ref = ref->next_ref)
+	    if (recog_data.operand_loc[i] == DF_REF_LOC (ref)
+		|| loc_mentioned_in_p (DF_REF_LOC (ref),
+				       *recog_data.operand_loc[i]))
+	      {
+		struct reg_ref * r = DF_REF_DATA (ref);
+		r->op = recog_data.operand[i];
+		r->op_num = i;
+	      }
+      }
+  for (i = 0; i < recog_data.n_dups; i++)
+    {
+      int pass;
+      for (pass = 0; pass < 2; pass++)
+	for (ref = (pass == 0)
+	           ? DF_INSN_DEFS (df, insn)
+		   : DF_INSN_USES (df, insn);
+	     ref;
+	     ref = ref->next_ref)
+	  if (recog_data.dup_loc[i] == DF_REF_LOC (ref)
+	      || loc_mentioned_in_p (DF_REF_LOC (ref),
+				     *recog_data.dup_loc[i]))
+	    {
+	      struct reg_ref * r = DF_REF_DATA (ref);
+	      r->op = recog_data.operand[(int)recog_data.dup_num[i]];
+	      r->op_num = recog_data.dup_num[i];
+	      r->dup = i;
+	    }
+    }
+
+  /* Now determine the initial alternative.  */
+  /* XXX We probably need our own constrain_operands version, so that we
+     can callback to our code whenever we find a certain reg requiring a
+     certain class.  This also enables usage of regclasses in already
+     looked at references in determining which alternative to chose.  */
+  valid = constrain_operands (0);
+  alt = which_alternative;
+  preprocess_constraints ();
+  if (dump_file)
+    fprintf (dump_file, " %d ", INSN_UID (insn));
+  if (recog_data.n_alternatives == 0 || n_ops == 0)
+    {
+      /* has no constrained operands, i.e. must be valid */
+      if (!valid)
+	abort ();
+    }
+  if (valid)
+    {
+      if (dump_file)
+	fprintf (dump_file, "   --> matched alternative %d\n", alt);
+      assign_alt_to_insn (insn, alt);
+    }
+  else
+    {
+      fprintf (dump_file, "  --> invalid insn");
+      fprintf (dump_file, "\n");
+    }
+}
+
+static void
+init_bb (basic_block bb)
+{
+  rtx insn;
+  if (dump_file)
+    fprintf (dump_file, "init_bb (%d) [freq:%d]\n", bb->index, bb->frequency);
+  FOR_BB_INSNS (bb, insn)
+    {
+      /* XXX Defer the handling of move insns until after all other
+	 instructions are dealt with.  Also first look at those instructions
+         which only have one alternative.  Those can determine the regclass
+         for some regs quite specific.  */
+      if (INSN_P (insn))
+	{
+	  enum rtx_code pat_code;
+	  pat_code = GET_CODE (PATTERN (insn));
+	  switch (pat_code)
+	    {
+	      /* Ignore non-insns.  */
+	      case USE: case CLOBBER: case ASM_INPUT: case ADDR_VEC:
+	      case ADDR_DIFF_VEC:
+		break;
+	      default:
+		init_insn (insn);
+		break;
+	    }
+	}
+    }
+  if (dump_file)
+    fprintf (dump_file, "\n");
+}
+
+static int
+bb_cost_cmp (const void *a, const void *b)
+{
+  basic_block ab = *(basic_block *)a;
+  basic_block bb = *(basic_block *)b;
+  if (ab->frequency > bb->frequency)
+    return -1;
+  else if (ab->frequency < bb->frequency)
+    return 1;
+  return ab->index - bb->index;
+}
+
+static unsigned int
+do_select (void)
+{
+  basic_block *bbs, bb;
+  int i, num_bb;
+  df = df_init (DF_SUBREGS);
+  df_analyze (df);
+  gcc_obstack_init (&si_obstack);
+  uid2alt = xmalloc (get_max_uid () * sizeof (uid2alt[0]));
+  memset (uid2alt, -1, get_max_uid () * sizeof (uid2alt[0]));
+  bbs = xmalloc (n_basic_blocks * sizeof (bbs[0]));
+  num_bb = 0;
+  FOR_EACH_BB (bb)
+    bbs[num_bb++] = bb;
+  qsort (bbs, num_bb, sizeof (bbs[0]), bb_cost_cmp);
+  if (dump_file)
+    df_dump (df, dump_file);
+  for (i = 0; i < num_bb; i++)
+    init_bb (bbs[i]);
+
+  free (bbs);
+  free (uid2alt);
+  obstack_free (&si_obstack, NULL);
+  df_finish (df);
+  return 0;
+}
+
+struct tree_opt_pass pass_insn_select =
+{
+  "isel",                               /* name */
+  NULL,                                 /* gate */
+  do_select,                            /* execute */
+  NULL,                                 /* sub */
+  NULL,                                 /* next */
+  0,                                    /* static_pass_number */
+  TV_LOCAL_ALLOC,                       /* tv_id */
+  0,                                    /* properties_required */
+  0,                                    /* properties_provided */
+  0,                                    /* properties_destroyed */
+  0,                                    /* todo_flags_start */
+  TODO_dump_func,                       /* todo_flags_finish */
+  's'                                   /* letter */
+};
+
+/*
+vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
+*/
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 3121735e85a..4361d14fd13 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -360,6 +360,7 @@ extern struct tree_opt_pass pass_see;
 extern struct tree_opt_pass pass_recompute_reg_usage;
 extern struct tree_opt_pass pass_sms;
 extern struct tree_opt_pass pass_sched;
+extern struct tree_opt_pass pass_insn_select;
 extern struct tree_opt_pass pass_local_alloc;
 extern struct tree_opt_pass pass_global_alloc;
 extern struct tree_opt_pass pass_postreload;