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

/* Web construction code for GNU compiler.
   Contributed by Jan Hubicka.
   Copyright (C) 2001-2015 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 "backend.h"
#include "rtl.h"
#include "df.h"
#include "diagnostic-core.h"

#include "flags.h"
#include "obstack.h"
#include "insn-config.h"
#include "recog.h"
#include "tree-pass.h"


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

web_entry_base *
web_entry_base::unionfind_root ()
{
  web_entry_base *element = this, *element1 = this, *element2;

  while (element->pred ())
    element = element->pred ();
  while (element1->pred ())
    {
      element2 = element1->pred ();
      element1->set_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 (web_entry_base *first, web_entry_base *second)
{
  first = first->unionfind_root ();
  second = second->unionfind_root ();
  if (first == second)
    return true;
  second->set_pred (first);
  return false;
}

class web_entry : public web_entry_base
{
 private:
  rtx reg_pvt;

 public:
  rtx reg () { return reg_pvt; }
  void set_reg (rtx r) { reg_pvt = r; }
};

/* 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 *insn, web_entry *def_entry, web_entry *use_entry,
		  bool (*fun) (web_entry_base *, web_entry_base *))
{
  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);
  struct web_entry *dup_entry;
  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;

      dup_entry = use_entry;
      for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
	if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
	  break;

      if (dupref == NULL && type == OP_INOUT)
	{
	  dup_entry = def_entry;
	  for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
	    if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
	      break;
	}
      /* ??? *DUPREF can still be zero, because when an operand matches
	 a memory, DF_REF_LOC (use_link[n]) points to the register part
	 of the address, whereas recog_data.dup_loc[m] points to the
	 entire memory ref, thus we fail to find the duplicate entry,
         even though it is there.
         Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
		  -O3 -fomit-frame-pointer -funroll-loops  */
      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 = DF_REF_NEXT_LOC (ref))
	{
	  rtx *l = DF_REF_LOC (ref);
	  if (l == recog_data.operand_loc[op])
	    break;
	  if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
	    break;
	}

      if (!ref && type == OP_INOUT)
	{
	  entry = use_entry;
	  for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
	    {
	      rtx *l = DF_REF_LOC (ref);
	      if (l == recog_data.operand_loc[op])
		break;
	      if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
		break;
	    }
	}

      gcc_assert (ref);
      (*fun) (dup_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, web_entry *def_entry,
	    unsigned int *used, web_entry *use_entry,
 	    bool (*fun) (web_entry_base *, web_entry_base *))
{
  struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
  struct df_link *link = DF_REF_CHAIN (use);
  rtx set;

  if (insn_info)
    {
      df_ref eq_use;

      set = single_set (insn_info->insn);
      FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
	if (use != eq_use
	    && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
	  (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use));
    }
  else
    set = NULL;

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

  /* 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))
    {
      df_ref def;

      FOR_EACH_INSN_INFO_DEF (def, insn_info)
	if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
	  (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
    }

  /* 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)
    if (insn_info)
      {
	df_ref def;

	FOR_EACH_INSN_INFO_DEF (def, insn_info)
	  if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
	    (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
      }
}

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

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

  /* Find the corresponding web and see if it has been visited.  */
  root = (web_entry *)entry->unionfind_root ();
  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->set_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
namespace {

const pass_data pass_data_web =
{
  RTL_PASS, /* type */
  "web", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_WEB, /* tv_id */
  0, /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  TODO_df_finish, /* todo_flags_finish */
};

class pass_web : public rtl_opt_pass
{
public:
  pass_web (gcc::context *ctxt)
    : rtl_opt_pass (pass_data_web, ctxt)
  {}

  /* opt_pass methods: */
  virtual bool gate (function *) { return (optimize > 0 && flag_web); }
  virtual unsigned int execute (function *);

}; // class pass_web

unsigned int
pass_web::execute (function *fun)
{
  web_entry *def_entry;
  web_entry *use_entry;
  unsigned int max = max_reg_num ();
  unsigned int *used;
  basic_block bb;
  unsigned int uses_num = 0;
  rtx_insn *insn;

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

  /* Assign ids to the uses.  */
  FOR_ALL_BB_FN (bb, fun)
    FOR_BB_INSNS (bb, insn)
    {
      if (NONDEBUG_INSN_P (insn))
	{
	  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
	  df_ref use;
	  FOR_EACH_INSN_INFO_USE (use, insn_info)
	    if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	      DF_REF_ID (use) = uses_num++;
	  FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
	    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 (web_entry, DF_DEFS_TABLE_SIZE ());
  used = XCNEWVEC (unsigned, max);
  use_entry = XCNEWVEC (web_entry, uses_num);

  /* Produce the web.  */
  FOR_ALL_BB_FN (bb, fun)
    FOR_BB_INSNS (bb, insn)
      if (NONDEBUG_INSN_P (insn))
	{
	  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
	  df_ref use;
	  union_match_dups (insn, def_entry, use_entry, unionfind_union);
	  FOR_EACH_INSN_INFO_USE (use, insn_info)
	    if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	      union_defs (use, def_entry, used, use_entry, unionfind_union);
	  FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
	    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_FN (bb, fun)
    FOR_BB_INSNS (bb, 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)
	{
	  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
	  df_ref def, use;
	  FOR_EACH_INSN_INFO_USE (use, insn_info)
	    if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	      replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
						use, used));
	  FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
	    if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
	      replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
						use, used));
	  FOR_EACH_INSN_INFO_DEF (def, insn_info)
	    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
} // anon namespace

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