[thirdparty/gcc.git] / gcc / web.c

/* Web construction code for GNU compiler.
   Contributed by Jan Hubicka.
   Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008, 2010
   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 3, 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 COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

/* Simple optimization pass that splits independent uses of each pseudo,
   increasing effectiveness of other optimizations.  The optimization can
   serve as an example of use for the dataflow module.

   We don't split registers with REG_USERVAR set unless -fmessy-debugging
   is specified, because debugging information about such split variables
   is almost unusable.

   TODO
    - We may use profile information and ignore infrequent use for the
      purpose of web unifying, inserting the compensation code later to
      implement full induction variable expansion for loops (currently
      we expand only if the induction variable is dead afterward, which
      is often the case).  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "diagnostic-core.h"

#include "rtl.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "obstack.h"
#include "basic-block.h"
#include "df.h"
#include "function.h"
#include "insn-config.h"
#include "recog.h"
#include "timevar.h"
#include "tree-pass.h"


/* Find the root of unionfind tree (the representative of set).  */

struct web_entry *
unionfind_root (struct web_entry *element)
{
  struct web_entry *element1 = element, *element2;

  while (element->pred)
    element = element->pred;
  while (element1->pred)
    {
      element2 = element1->pred;
      element1->pred = element;
      element1 = element2;
    }
  return element;
}

/* Union sets.
   Return true if FIRST and SECOND points to the same web entry structure and
   nothing is done.  Otherwise, return false.  */

bool
unionfind_union (struct web_entry *first, struct web_entry *second)
{
  first = unionfind_root (first);
  second = unionfind_root (second);
  if (first == second)
    return true;
  second->pred = first;
  return false;
}

/* For INSN, union all defs and uses that are linked by match_dup.
   FUN is the function that does the union.  */

static void
union_match_dups (rtx insn, struct web_entry *def_entry,
		  struct web_entry *use_entry,
		  bool (*fun) (struct web_entry *, struct web_entry *))
{
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
  df_ref *use_link = DF_INSN_INFO_USES (insn_info);
  df_ref *def_link = DF_INSN_INFO_DEFS (insn_info);
  int i;

  extract_insn (insn);

  for (i = 0; i < recog_data.n_dups; i++)
    {
      int op = recog_data.dup_num[i];
      enum op_type type = recog_data.operand_type[op];
      df_ref *ref, *dupref;
      struct web_entry *entry;

      for (dupref = use_link; *dupref; dupref++)
	if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
	  break;

      if (*dupref == NULL
	  || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
	continue;

      ref = type == OP_IN ? use_link : def_link;
      entry = type == OP_IN ? use_entry : def_entry;
      for (; *ref; ref++)
	if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
	  break;

      (*fun) (use_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
    }
}

/* For each use, all possible defs reaching it must come in the same
   register, union them.
   FUN is the function that does the union.

   In USED, we keep the DF_REF_ID of the first uninitialized uses of a
   register, so that all uninitialized uses of the register can be
   combined into a single web.  We actually offset it by 2, because
   the values 0 and 1 are reserved for use by entry_register.  */

void
union_defs (df_ref use, struct web_entry *def_entry,
	    unsigned int *used, struct web_entry *use_entry,
 	    bool (*fun) (struct web_entry *, struct web_entry *))
{
  struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
  struct df_link *link = DF_REF_CHAIN (use);
  df_ref *eq_use_link;
  df_ref *def_link;
  rtx set;

  if (insn_info)
    {
      rtx insn = insn_info->insn;
      eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
      def_link = DF_INSN_INFO_DEFS (insn_info);
      set = single_set (insn);
    }
  else
    {
      /* An artificial use.  It links up with nothing.  */
      eq_use_link = NULL;
      def_link = NULL;
      set = NULL;
    }

  /* Union all occurrences of the same register in reg notes.  */

  if (eq_use_link)
    while (*eq_use_link)
      {
	if (use != *eq_use_link
	    && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
	  (*fun) (use_entry + DF_REF_ID (use),
		  use_entry + DF_REF_ID (*eq_use_link));
	eq_use_link++;
    }

  /* Recognize trivial noop moves and attempt to keep them as noop.  */

  if (set
      && SET_SRC (set) == DF_REF_REG (use)
      && SET_SRC (set) == SET_DEST (set))
    {
      if (def_link)
	while (*def_link)
	  {
	    if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
	      (*fun) (use_entry + DF_REF_ID (use),
		      def_entry + DF_REF_ID (*def_link));
	    def_link++;
	  }
    }

  /* UD chains of uninitialized REGs are empty.  Keeping all uses of
     the same uninitialized REG in a single web is not necessary for
     correctness, since the uses are undefined, but it's wasteful to
     allocate one register or slot for each reference.  Furthermore,
     creating new pseudos for uninitialized references in debug insns
     (see PR 42631) causes -fcompare-debug failures.  We record the
     number of the first uninitialized reference we found, and merge
     with it any other uninitialized references to the same
     register.  */
  if (!link)
    {
      int regno = REGNO (DF_REF_REAL_REG (use));
      if (used[regno])
	(*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
      else
	used[regno] = DF_REF_ID (use) + 2;
    }

  while (link)
    {
      (*fun) (use_entry + DF_REF_ID (use),
	      def_entry + DF_REF_ID (link->ref));
      link = link->next;
    }

  /* A READ_WRITE use requires the corresponding def to be in the same
     register.  Find it and union.  */
  if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
    {
      df_ref *link;

      if (insn_info)
	link = DF_INSN_INFO_DEFS (insn_info);
      else
	link = NULL;

      if (link)
	while (*link)
	  {
	    if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
	      (*fun) (use_entry + DF_REF_ID (use),
		      def_entry + DF_REF_ID (*link));
	    link++;
	  }
    }
}

/* Find the corresponding register for the given entry.  */

static rtx
entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
{
  struct web_entry *root;
  rtx reg, newreg;

  /* Find the corresponding web and see if it has been visited.  */
  root = unionfind_root (entry);
  if (root->reg)
    return root->reg;

  /* We are seeing this web for the first time, do the assignment.  */
  reg = DF_REF_REAL_REG (ref);

  /* In case the original register is already assigned, generate new
     one.  Since we use USED to merge uninitialized refs into a single
     web, we might found an element to be nonzero without our having
     used it.  Test for 1, because union_defs saves it for our use,
     and there won't be any use for the other values when we get to
     this point.  */
  if (used[REGNO (reg)] != 1)
    newreg = reg, used[REGNO (reg)] = 1;
  else
    {
      newreg = gen_reg_rtx (GET_MODE (reg));
      REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
      REG_POINTER (newreg) = REG_POINTER (reg);
      REG_ATTRS (newreg) = REG_ATTRS (reg);
      if (dump_file)
	fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
		 REGNO (newreg));
    }

  root->reg = newreg;
  return newreg;
}

/* Replace the reference by REG.  */

static void
replace_ref (df_ref ref, rtx reg)
{
  rtx oldreg = DF_REF_REAL_REG (ref);
  rtx *loc = DF_REF_REAL_LOC (ref);
  unsigned int uid = DF_REF_INSN_UID (ref);

  if (oldreg == reg)
    return;
  if (dump_file)
    fprintf (dump_file, "Updating insn %i (%i->%i)\n",
	     uid, REGNO (oldreg), REGNO (reg));
  *loc = reg;
  df_insn_rescan (DF_REF_INSN (ref));
}

\f
static bool
gate_handle_web (void)
{
  return (optimize > 0 && flag_web);
}

/* Main entry point.  */

static unsigned int
web_main (void)
{
  struct web_entry *def_entry;
  struct web_entry *use_entry;
  unsigned int max = max_reg_num ();
  unsigned int *used;
  basic_block bb;
  unsigned int uses_num = 0;
  rtx insn;

  df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
  df_chain_add_problem (DF_UD_CHAIN);
  df_analyze ();
  df_set_flags (DF_DEFER_INSN_RESCAN);

  /* Assign ids to the uses.  */
  FOR_ALL_BB (bb)
    FOR_BB_INSNS (bb, insn)
    {
      unsigned int uid = INSN_UID (insn);
      if (NONDEBUG_INSN_P (insn))
	{
	  df_ref *use_rec;
	  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
	    {
	      df_ref use = *use_rec;
	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
		DF_REF_ID (use) = uses_num++;
	    }
	  for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
	    {
	      df_ref use = *use_rec;
	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
		DF_REF_ID (use) = uses_num++;
	    }
	}
    }

  /* Record the number of uses and defs at the beginning of the optimization.  */
  def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
  used = XCNEWVEC (unsigned, max);
  use_entry = XCNEWVEC (struct web_entry, uses_num);

  /* Produce the web.  */
  FOR_ALL_BB (bb)
    FOR_BB_INSNS (bb, insn)
    {
      unsigned int uid = INSN_UID (insn);
      if (NONDEBUG_INSN_P (insn))
	{
	  df_ref *use_rec;
	  union_match_dups (insn, def_entry, use_entry, unionfind_union);
	  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
	    {
	      df_ref use = *use_rec;
	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
		union_defs (use, def_entry, used, use_entry, unionfind_union);
	    }
	  for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
	    {
	      df_ref use = *use_rec;
	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
		union_defs (use, def_entry, used, use_entry, unionfind_union);
	    }
	}
    }

  /* Update the instruction stream, allocating new registers for split pseudos
     in progress.  */
  FOR_ALL_BB (bb)
    FOR_BB_INSNS (bb, insn)
    {
      unsigned int uid = INSN_UID (insn);

      if (NONDEBUG_INSN_P (insn)
	  /* Ignore naked clobber.  For example, reg 134 in the second insn
	     of the following sequence will not be replaced.

	       (insn (clobber (reg:SI 134)))

	       (insn (set (reg:SI 0 r0) (reg:SI 134)))

	     Thus the later passes can optimize them away.  */
	  && GET_CODE (PATTERN (insn)) != CLOBBER)
	{
	  df_ref *use_rec;
	  df_ref *def_rec;
	  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
	    {
	      df_ref use = *use_rec;
	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
		replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
	    }
	  for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
	    {
	      df_ref use = *use_rec;
	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
		replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
	    }
	  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
	    {
	      df_ref def = *def_rec;
	      if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
		replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
	    }
	}
    }

  free (def_entry);
  free (use_entry);
  free (used);
  return 0;
}
\f
struct rtl_opt_pass pass_web =
{
 {
  RTL_PASS,
  "web",                                /* name */
  gate_handle_web,                      /* gate */
  web_main,		                /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  TV_WEB,                               /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 }
};
Commit	Line	Data
eeb4a70e	1	/* Web construction code for GNU compiler.
8b5b1013	2	Contributed by Jan Hubicka.
73685692	3	Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008, 2010
e011eba9	4	Free Software Foundation, Inc.
eeb4a70e	5
	6	This file is part of GCC.
	7
	8	GCC is free software; you can redistribute it and/or modify it under
	9	the terms of the GNU General Public License as published by the Free
8c4c00c1	10	Software Foundation; either version 3, or (at your option) any later
eeb4a70e	11	version.
	12
	13	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
	14	WARRANTY; without even the implied warranty of MERCHANTABILITY or
	15	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	16	for more details.
	17
	18	You should have received a copy of the GNU General Public License
8c4c00c1	19	along with GCC; see the file COPYING3. If not see
8c4c00c1	20	<http://www.gnu.org/licenses/>. */
eeb4a70e	21
8b5b1013	22	/* Simple optimization pass that splits independent uses of each pseudo,
40e55fbb	23	increasing effectiveness of other optimizations. The optimization can
8b5b1013	24	serve as an example of use for the dataflow module.
eeb4a70e	25
8b5b1013	26	We don't split registers with REG_USERVAR set unless -fmessy-debugging
	27	is specified, because debugging information about such split variables
	28	is almost unusable.
eeb4a70e	29
eeb4a70e	30	TODO
8b5b1013	31	- We may use profile information and ignore infrequent use for the
	32	purpose of web unifying, inserting the compensation code later to
	33	implement full induction variable expansion for loops (currently
	34	we expand only if the induction variable is dead afterward, which
	35	is often the case). */
eeb4a70e	36
	37	#include "config.h"
	38	#include "system.h"
	39	#include "coretypes.h"
	40	#include "tm.h"
0b205f4c	41	#include "diagnostic-core.h"
eeb4a70e	42
	43	#include "rtl.h"
	44	#include "hard-reg-set.h"
	45	#include "flags.h"
42fe97ed	46	#include "obstack.h"
eeb4a70e	47	#include "basic-block.h"
eeb4a70e	48	#include "df.h"
eeb4a70e	49	#include "function.h"
9a3f5556	50	#include "insn-config.h"
9a3f5556	51	#include "recog.h"
77fce4cd	52	#include "timevar.h"
77fce4cd	53	#include "tree-pass.h"
eeb4a70e	54
eeb4a70e	55
8b5b1013	56	/* Find the root of unionfind tree (the representative of set). */
eeb4a70e	57
2b74c150	58	struct web_entry *
6f2c2693	59	unionfind_root (struct web_entry *element)
eeb4a70e	60	{
	61	struct web_entry element1 = element, element2;
	62
	63	while (element->pred)
	64	element = element->pred;
	65	while (element1->pred)
	66	{
	67	element2 = element1->pred;
	68	element1->pred = element;
	69	element1 = element2;
	70	}
	71	return element;
	72	}
	73
48e1416a	74	/* Union sets.
2b74c150	75	Return true if FIRST and SECOND points to the same web entry structure and
2b74c150	76	nothing is done. Otherwise, return false. */
eeb4a70e	77
2b74c150	78	bool
6f2c2693	79	unionfind_union (struct web_entry first, struct web_entry second)
eeb4a70e	80	{
	81	first = unionfind_root (first);
	82	second = unionfind_root (second);
	83	if (first == second)
2b74c150	84	return true;
eeb4a70e	85	second->pred = first;
2b74c150	86	return false;
eeb4a70e	87	}
eeb4a70e	88
9a3f5556	89	/* For INSN, union all defs and uses that are linked by match_dup.
	90	FUN is the function that does the union. */
	91
	92	static void
	93	union_match_dups (rtx insn, struct web_entry *def_entry,
	94	struct web_entry *use_entry,
	95	bool (fun) (struct web_entry , struct web_entry *))
	96	{
	97	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
	98	df_ref *use_link = DF_INSN_INFO_USES (insn_info);
	99	df_ref *def_link = DF_INSN_INFO_DEFS (insn_info);
	100	int i;
	101
	102	extract_insn (insn);
	103
	104	for (i = 0; i < recog_data.n_dups; i++)
	105	{
	106	int op = recog_data.dup_num[i];
	107	enum op_type type = recog_data.operand_type[op];
	108	df_ref ref, dupref;
	109	struct web_entry *entry;
	110
	111	for (dupref = use_link; *dupref; dupref++)
	112	if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
	113	break;
	114
	115	if (*dupref == NULL
	116	\|\| DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
	117	continue;
	118
	119	ref = type == OP_IN ? use_link : def_link;
	120	entry = type == OP_IN ? use_entry : def_entry;
	121	for (; *ref; ref++)
	122	if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
	123	break;
	124
	125	(fun) (use_entry + DF_REF_ID (dupref), entry + DF_REF_ID (*ref));
	126	}
	127	}
	128
8b5b1013	129	/* For each use, all possible defs reaching it must come in the same
2b74c150	130	register, union them.
388bf4a2	131	FUN is the function that does the union.
	132
	133	In USED, we keep the DF_REF_ID of the first uninitialized uses of a
	134	register, so that all uninitialized uses of the register can be
	135	combined into a single web. We actually offset it by 2, because
	136	the values 0 and 1 are reserved for use by entry_register. */
eeb4a70e	137
2b74c150	138	void
ed6e85ae	139	union_defs (df_ref use, struct web_entry *def_entry,
388bf4a2	140	unsigned int used, struct web_entry use_entry,
2b74c150	141	bool (fun) (struct web_entry , struct web_entry *))
eeb4a70e	142	{
158b6cc9	143	struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
eeb4a70e	144	struct df_link *link = DF_REF_CHAIN (use);
ed6e85ae	145	df_ref *eq_use_link;
ed6e85ae	146	df_ref *def_link;
2b74c150	147	rtx set;
2b74c150	148
158b6cc9	149	if (insn_info)
2b74c150	150	{
158b6cc9	151	rtx insn = insn_info->insn;
158b6cc9	152	eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
158b6cc9	153	def_link = DF_INSN_INFO_DEFS (insn_info);
2b74c150	154	set = single_set (insn);
	155	}
	156	else
	157	{
158b6cc9	158	/* An artificial use. It links up with nothing. */
3072d30e	159	eq_use_link = NULL;
2b74c150	160	def_link = NULL;
	161	set = NULL;
	162	}
eeb4a70e	163
9a3f5556	164	/* Union all occurrences of the same register in reg notes. */
3072d30e	165
	166	if (eq_use_link)
	167	while (*eq_use_link)
	168	{
	169	if (use != *eq_use_link
	170	&& DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
	171	(*fun) (use_entry + DF_REF_ID (use),
	172	use_entry + DF_REF_ID (*eq_use_link));
	173	eq_use_link++;
eeb4a70e	174	}
eeb4a70e	175
1e5b92fa	176	/* Recognize trivial noop moves and attempt to keep them as noop. */
eeb4a70e	177
	178	if (set
	179	&& SET_SRC (set) == DF_REF_REG (use)
	180	&& SET_SRC (set) == SET_DEST (set))
	181	{
3072d30e	182	if (def_link)
	183	while (*def_link)
	184	{
	185	if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
	186	(*fun) (use_entry + DF_REF_ID (use),
	187	def_entry + DF_REF_ID (*def_link));
	188	def_link++;
	189	}
eeb4a70e	190	}
388bf4a2	191
	192	/* UD chains of uninitialized REGs are empty. Keeping all uses of
	193	the same uninitialized REG in a single web is not necessary for
	194	correctness, since the uses are undefined, but it's wasteful to
	195	allocate one register or slot for each reference. Furthermore,
	196	creating new pseudos for uninitialized references in debug insns
	197	(see PR 42631) causes -fcompare-debug failures. We record the
	198	number of the first uninitialized reference we found, and merge
	199	with it any other uninitialized references to the same
	200	register. */
	201	if (!link)
	202	{
	203	int regno = REGNO (DF_REF_REAL_REG (use));
	204	if (used[regno])
	205	(*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
	206	else
	207	used[regno] = DF_REF_ID (use) + 2;
	208	}
	209
eeb4a70e	210	while (link)
eeb4a70e	211	{
2b74c150	212	(*fun) (use_entry + DF_REF_ID (use),
2b74c150	213	def_entry + DF_REF_ID (link->ref));
eeb4a70e	214	link = link->next;
	215	}
	216
8b5b1013	217	/* A READ_WRITE use requires the corresponding def to be in the same
eeb4a70e	218	register. Find it and union. */
ed6e85ae	219	if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
eeb4a70e	220	{
ed6e85ae	221	df_ref *link;
2b74c150	222
158b6cc9	223	if (insn_info)
158b6cc9	224	link = DF_INSN_INFO_DEFS (insn_info);
2b74c150	225	else
2b74c150	226	link = NULL;
eeb4a70e	227
3072d30e	228	if (link)
	229	while (*link)
	230	{
	231	if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
	232	(*fun) (use_entry + DF_REF_ID (use),
	233	def_entry + DF_REF_ID (*link));
	234	link++;
	235	}
eeb4a70e	236	}
	237	}
	238
8b5b1013	239	/* Find the corresponding register for the given entry. */
eeb4a70e	240
eeb4a70e	241	static rtx
388bf4a2	242	entry_register (struct web_entry entry, df_ref ref, unsigned int used)
eeb4a70e	243	{
	244	struct web_entry *root;
	245	rtx reg, newreg;
	246
8b5b1013	247	/* Find the corresponding web and see if it has been visited. */
eeb4a70e	248	root = unionfind_root (entry);
	249	if (root->reg)
	250	return root->reg;
	251
8b5b1013	252	/* We are seeing this web for the first time, do the assignment. */
eeb4a70e	253	reg = DF_REF_REAL_REG (ref);
eeb4a70e	254
388bf4a2	255	/* In case the original register is already assigned, generate new
	256	one. Since we use USED to merge uninitialized refs into a single
	257	web, we might found an element to be nonzero without our having
	258	used it. Test for 1, because union_defs saves it for our use,
	259	and there won't be any use for the other values when we get to
	260	this point. */
	261	if (used[REGNO (reg)] != 1)
de963f40	262	newreg = reg, used[REGNO (reg)] = 1;
eeb4a70e	263	else
	264	{
	265	newreg = gen_reg_rtx (GET_MODE (reg));
	266	REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
	267	REG_POINTER (newreg) = REG_POINTER (reg);
eeb4a70e	268	REG_ATTRS (newreg) = REG_ATTRS (reg);
450d042a	269	if (dump_file)
450d042a	270	fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
eeb4a70e	271	REGNO (newreg));
	272	}
	273
	274	root->reg = newreg;
	275	return newreg;
	276	}
	277
	278	/* Replace the reference by REG. */
	279
	280	static void
ed6e85ae	281	replace_ref (df_ref ref, rtx reg)
eeb4a70e	282	{
	283	rtx oldreg = DF_REF_REAL_REG (ref);
	284	rtx *loc = DF_REF_REAL_LOC (ref);
ed6e85ae	285	unsigned int uid = DF_REF_INSN_UID (ref);
eeb4a70e	286
	287	if (oldreg == reg)
	288	return;
450d042a	289	if (dump_file)
450d042a	290	fprintf (dump_file, "Updating insn %i (%i->%i)\n",
48e1416a	291	uid, REGNO (oldreg), REGNO (reg));
eeb4a70e	292	*loc = reg;
3072d30e	293	df_insn_rescan (DF_REF_INSN (ref));
	294	}
	295
	296	\f
	297	static bool
	298	gate_handle_web (void)
	299	{
	300	return (optimize > 0 && flag_web);
eeb4a70e	301	}
eeb4a70e	302
eeb4a70e	303	/* Main entry point. */
eeb4a70e	304
3072d30e	305	static unsigned int
6f2c2693	306	web_main (void)
eeb4a70e	307	{
eeb4a70e	308	struct web_entry *def_entry;
eeb4a70e	309	struct web_entry *use_entry;
3072d30e	310	unsigned int max = max_reg_num ();
388bf4a2	311	unsigned int *used;
3072d30e	312	basic_block bb;
	313	unsigned int uses_num = 0;
	314	rtx insn;
	315
	316	df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
	317	df_chain_add_problem (DF_UD_CHAIN);
	318	df_analyze ();
	319	df_set_flags (DF_DEFER_INSN_RESCAN);
	320
	321	/* Assign ids to the uses. */
	322	FOR_ALL_BB (bb)
	323	FOR_BB_INSNS (bb, insn)
	324	{
	325	unsigned int uid = INSN_UID (insn);
41ceca3d	326	if (NONDEBUG_INSN_P (insn))
3072d30e	327	{
ed6e85ae	328	df_ref *use_rec;
3072d30e	329	for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3072d30e	330	{
ed6e85ae	331	df_ref use = *use_rec;
3072d30e	332	if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	333	DF_REF_ID (use) = uses_num++;
	334	}
	335	for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
	336	{
ed6e85ae	337	df_ref use = *use_rec;
3072d30e	338	if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	339	DF_REF_ID (use) = uses_num++;
	340	}
	341	}
	342	}
eeb4a70e	343
3072d30e	344	/* Record the number of uses and defs at the beginning of the optimization. */
3072d30e	345	def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
388bf4a2	346	used = XCNEWVEC (unsigned, max);
3072d30e	347	use_entry = XCNEWVEC (struct web_entry, uses_num);
eeb4a70e	348
eeb4a70e	349	/* Produce the web. */
3072d30e	350	FOR_ALL_BB (bb)
	351	FOR_BB_INSNS (bb, insn)
	352	{
	353	unsigned int uid = INSN_UID (insn);
41ceca3d	354	if (NONDEBUG_INSN_P (insn))
3072d30e	355	{
ed6e85ae	356	df_ref *use_rec;
9a3f5556	357	union_match_dups (insn, def_entry, use_entry, unionfind_union);
3072d30e	358	for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3072d30e	359	{
ed6e85ae	360	df_ref use = *use_rec;
3072d30e	361	if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
388bf4a2	362	union_defs (use, def_entry, used, use_entry, unionfind_union);
3072d30e	363	}
	364	for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
	365	{
ed6e85ae	366	df_ref use = *use_rec;
3072d30e	367	if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
388bf4a2	368	union_defs (use, def_entry, used, use_entry, unionfind_union);
3072d30e	369	}
	370	}
	371	}
eeb4a70e	372
eeb4a70e	373	/* Update the instruction stream, allocating new registers for split pseudos
eeb4a70e	374	in progress. */
3072d30e	375	FOR_ALL_BB (bb)
	376	FOR_BB_INSNS (bb, insn)
	377	{
	378	unsigned int uid = INSN_UID (insn);
90db8e34	379
	380	if (NONDEBUG_INSN_P (insn)
	381	/* Ignore naked clobber. For example, reg 134 in the second insn
	382	of the following sequence will not be replaced.
	383
	384	(insn (clobber (reg:SI 134)))
	385
	386	(insn (set (reg:SI 0 r0) (reg:SI 134)))
	387
	388	Thus the later passes can optimize them away. */
	389	&& GET_CODE (PATTERN (insn)) != CLOBBER)
3072d30e	390	{
ed6e85ae	391	df_ref *use_rec;
ed6e85ae	392	df_ref *def_rec;
3072d30e	393	for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3072d30e	394	{
ed6e85ae	395	df_ref use = *use_rec;
3072d30e	396	if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	397	replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
	398	}
	399	for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
	400	{
ed6e85ae	401	df_ref use = *use_rec;
3072d30e	402	if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	403	replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
	404	}
	405	for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
	406	{
ed6e85ae	407	df_ref def = *def_rec;
3072d30e	408	if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
	409	replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
	410	}
	411	}
	412	}
	413
eeb4a70e	414	free (def_entry);
	415	free (use_entry);
	416	free (used);
2a1990e9	417	return 0;
77fce4cd	418	}
3072d30e	419	\f
20099e35	420	struct rtl_opt_pass pass_web =
77fce4cd	421	{
20099e35	422	{
20099e35	423	RTL_PASS,
77fce4cd	424	"web", /* name */
77fce4cd	425	gate_handle_web, /* gate */
3072d30e	426	web_main, /* execute */
77fce4cd	427	NULL, /* sub */
	428	NULL, /* next */
	429	0, /* static_pass_number */
	430	TV_WEB, /* tv_id */
	431	0, /* properties_required */
	432	0, /* properties_provided */
	433	0, /* properties_destroyed */
	434	0, /* todo_flags_start */
771e2890	435	TODO_df_finish \| TODO_verify_rtl_sharing /* todo_flags_finish */
20099e35	436	}
77fce4cd	437	};