* rtl.h (INSN_P): New macro.

	(successor_phi_fn): New typedef.
	(for_each_successor_phi): New prototype.
	(in_ssa_form): New variable.
	(PHI_NODE_P): Likewise.
	* flow.c (calculate_global_regs_live): Add to new_live_at_end from
	phi nodes in successors.
	(mark_used_regs): Add PHI case.
	(set_phi_alternative_reg): New function.
	(life_analysis): Assert that dead code elimination is not selected
	when in SSA form.
	* toplev.c (to_ssa_time): New variable.
	(from_ssa_time): Likewise.
	(compile_file): Zero to_ssa_time and from_ssa_time.
	Print time to convert to and from SSA.
	(rest_of_compilation): Time convert_to_ssa and convert_from_ssa.
	(print_time): Compute percent fraction as integer.
	* ssa.c (PHI_NODE_P): Moved to rtl.h.
	(convert_to_ssa): Check if we're already in SSA.
	Don't eliminate dead code in life_analysis.
	Rerun flow and life analysis at bottom.
	(eliminate_phi): Use canonical regnos when adding nodes.
	(mark_reg_in_phi): New function.
	(mark_phi_and_copy_regs): Likewise.
	(convert_from_ssa): Rerun life analysis at top.
	Use coalesced partition.
	Check for removing a phi node at the end of the block.
	(compute_coalesced_reg_partition): New function.
	(coalesce_regs_in_copies): Likewise.
	(coalesce_reg_in_phi): Likewise.
	(coalesce_regs_in_sucessor_phi_nodes): Likewise.
	(for_each_successor_phi): Likewise.
	(rename_context): New struct.
	(rename_block): Use a rename_context with rename_insn_1.  When
	renaming sets of a subreg, emit a copy of the entire reg first.
	(rename_insn_1): Treat data as a rename_context *.  Save current
	insn in set_data.
	(rename_set_data): Add field set_insn.
	* Makefile.in (HASHTAB_H): Move up in file.
	(OBSTACK_H): New macro.
	(collect2.o): Use OBSTACK_H in dependencies.
	(sdbout.o): Likewise.
	(emit-rtl.o): Likewise.
	(simplify-rtx.o): Likewise.
	(fix-header.o): Likewise.
	(OBJS):	Add conflict.o.
	(conflict.o): New rule.
	* basic-block.h: Include partition.h.
	(conflict_graph): New typedef.
	(conflict_graph_enum_fn): Likewise.
	(conflict_graph_new): New prototype.
	(conflict_graph_delete): Likewise.
	(conflict_graph_add): Likewise.
	(conflict_graph_conflict_p): Likewise.
	(conflict_graph_enum): Likewise.
	(conflict_graph_merge_regs): Likewise.
	(conflict_graph_print): Likewise.
	(conflict_graph_compute): Likewise.
	* conflict.c: New file.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@32979 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 535 insertions, 0 deletions

diff --git a/gcc/conflict.c b/gcc/conflict.c
new file mode 100644
index 00000000000..51851a2b1b5
--- /dev/null
+++ b/gcc/conflict.c
@@ -0,0 +1,535 @@
+/* Register conflict graph computation routines.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+   Contributed by CodeSourcery, LLC
+
+   This file is part of GNU CC.
+
+   GNU CC 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.
+
+   GNU CC 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 GNU CC; see the file COPYING.  If not, write to
+   the Free Software Foundation, 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+/* References:
+
+   Building an Optimizing Compiler
+   Robert Morgan
+   Butterworth-Heinemann, 1998 */
+
+#include "config.h"
+#include "system.h"
+
+#include "obstack.h"
+#include "hashtab.h"
+#include "rtl.h"
+#include "basic-block.h"
+
+/* Use malloc to allocate obstack chunks.  */
+#define obstack_chunk_alloc xmalloc
+#define obstack_chunk_free free
+
+/* A register conflict graph is an undirected graph containing nodes
+   for some or all of the regs used in a function.  Arcs represent
+   conflicts, i.e. two nodes are connected by an arc if there is a
+   point in the function at which the regs corresponding to the two
+   nodes are both live.
+
+   The conflict graph is represented by the data structures described
+   in Morgan section 11.3.1.  Nodes are not stored explicitly; only
+   arcs are.  An arc stores the numbers of the regs it connects.
+
+   Arcs can be located by two methods:
+
+     - The two reg numbers for each arc are hashed into a single
+       value, and the arc is placed in a hash table according to this
+       value.  This permits quick determination of whether a specific
+       conflict is present in the graph.  
+
+     - Additionally, the arc data structures are threaded by a set of
+       linked lists by single reg number.  Since each arc references
+       two regs, there are two next pointers, one for the
+       smaller-numbered reg and one for the larger-numbered reg.  This
+       permits the quick enumeration of conflicts for a single
+       register.
+
+   Arcs are allocated from an obstack.  */
+
+/* An arc in a conflict graph.  */
+
+struct conflict_graph_arc_def
+{
+  /* The next element of the list of conflicts involving the
+     smaller-numbered reg, as an index in the table of arcs of this
+     graph.   Contains NULL if this is the tail.  */
+  struct conflict_graph_arc_def *smaller_next;
+
+  /* The next element of the list of conflicts involving the
+     larger-numbered reg, as an index in the table of arcs of this
+     graph.  Contains NULL if this is the tail.  */
+  struct conflict_graph_arc_def *larger_next;
+
+  /* The smaller-numbered reg involved in this conflict.  */
+  int smaller;
+
+  /* The larger-numbered reg involved in this conflict.  */
+  int larger;
+};
+
+typedef struct conflict_graph_arc_def *conflict_graph_arc;
+
+
+/* A conflict graph.  */
+
+struct conflict_graph_def
+{
+  /* A hash table of arcs.  Used to search for a specific conflict.  */
+  htab_t arc_hash_table;
+
+  /* The number of regs this conflict graph handles.  */
+  int num_regs;
+
+  /* For each reg, the arc at the head of a list that threads through
+     all the arcs involving that reg.  An entry is NULL if no
+     conflicts exist involving that reg.  */
+  conflict_graph_arc *neighbor_heads;
+
+  /* Arcs are allocated from here. */
+  struct obstack arc_obstack;
+};
+
+/* The initial capacity (number of conflict arcs) for newly-created
+   conflict graphs.  */
+#define INITIAL_ARC_CAPACITY (64)
+
+
+/* Computes the hash value of the conflict graph arc connecting regs
+   R1__ and R2__.  R1__ is assumed to be smaller or equal to R2__.  */
+#define CONFLICT_HASH_FN(r1__, r2__) ((r2__) * ((r2__) - 1) / 2 + (r1__))
+
+static unsigned arc_hash
+  PARAMS ((const void *arcp));
+static int arc_eq 
+  PARAMS ((const void *arcp1, const void *arcp2));
+static int print_conflict
+  PARAMS ((int reg1, int reg2, void *contextp));
+static void mark_reg 
+  PARAMS ((rtx reg, rtx setter, void *data));
+
+
+/* Callback function to compute the hash value of an arc.  Uses
+   current_graph to locate the graph to which the arc belongs. */
+
+static unsigned
+arc_hash (arcp)
+     const void *arcp;
+{
+  conflict_graph_arc arc = (conflict_graph_arc) arcp;
+  return CONFLICT_HASH_FN (arc->smaller, arc->larger);
+}
+
+/* Callback function to determine the equality of two arcs in the hash
+   table.  */
+
+static int
+arc_eq (arcp1, arcp2)
+     const void *arcp1;
+     const void *arcp2;
+{
+  conflict_graph_arc arc1 = (conflict_graph_arc) arcp1;
+  conflict_graph_arc arc2 = (conflict_graph_arc) arcp2;
+  return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
+}
+
+/* Creates an empty conflict graph to hold conflicts among NUM_REGS
+   registers.  */
+
+conflict_graph
+conflict_graph_new (num_regs)
+     int num_regs;
+{
+  conflict_graph graph = 
+    (conflict_graph) xmalloc (sizeof (struct conflict_graph_def));
+  graph->num_regs = num_regs;
+
+  /* Set up the hash table.  No delete action is specified; memory
+     management of arcs is through the obstack.  */
+  graph->arc_hash_table = 
+    htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
+
+  /* Create an obstack for allocating arcs.  */
+  obstack_init (&(graph->arc_obstack));
+	     
+  /* Create and zero the lookup table by register number.  */
+  graph->neighbor_heads = (conflict_graph_arc *) 
+    xmalloc (num_regs * sizeof (conflict_graph_arc));
+  memset (graph->neighbor_heads, 0, 
+	  num_regs * sizeof (conflict_graph_arc));
+
+  return graph;
+}
+
+/* Deletes a conflict graph.  */
+
+void
+conflict_graph_delete (graph)
+     conflict_graph graph;
+{
+  obstack_free (&(graph->arc_obstack), NULL);
+  htab_delete (graph->arc_hash_table);
+  free (graph->neighbor_heads);
+  free (graph);
+}
+
+/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
+   distinct.  Returns non-zero, unless the conflict is already present
+   in GRAPH, in which case it does nothing and returns zero.  */
+
+int
+conflict_graph_add (graph, reg1, reg2)
+     conflict_graph graph;
+     int reg1;
+     int reg2;
+{
+  int smaller = MIN (reg1, reg2);
+  int larger = MAX (reg1, reg2);
+  conflict_graph_arc arc;
+  void **hash_table_slot;
+
+  /* A reg cannot conflict with itself.  */
+  if (reg1 == reg2)
+    abort ();
+
+  /* If the conflict is already there, do nothing. 
+
+     FIXME: This is a little wastful; it would be faster to look up the
+     conflict in the hash table, returning it if it exists and
+     inserting a new entry if it doesn't, all in one operation.  This
+     would save an extra hash lookup.  However, the hashtab interface
+     doesn't really allow this right now.  */
+  if (conflict_graph_conflict_p (graph, reg1, reg2))
+    return 0;
+
+  /* Allocate an arc.  */
+  arc = (conflict_graph_arc) 
+    obstack_alloc (&(graph->arc_obstack),
+		   sizeof (struct conflict_graph_arc_def));
+
+  /* Record the reg numbers.  */
+  arc->smaller = smaller;
+  arc->larger = larger;
+
+  /* Link the conflict into into two lists, one for each reg.  */
+  arc->smaller_next = graph->neighbor_heads[smaller];
+  graph->neighbor_heads[smaller] = arc;
+  arc->larger_next = graph->neighbor_heads[larger];
+  graph->neighbor_heads[larger] = arc;
+
+  /* Put it in the hash table.  */
+  hash_table_slot = htab_find_slot (graph->arc_hash_table, 
+				    (void *) arc, 1);
+  *hash_table_slot = (void *) arc;
+
+  return 1;
+}
+
+/* Returns non-zero if a conflict exists in GRAPH between regs REG1
+   and REG2.  */
+
+int
+conflict_graph_conflict_p (graph, reg1, reg2)
+     conflict_graph graph;
+     int reg1;
+     int reg2;
+{
+  /* Build an arc to search for.  */
+  struct conflict_graph_arc_def arc;
+  arc.smaller = MIN (reg1, reg2);
+  arc.larger = MAX (reg1, reg2);
+
+  return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
+}
+
+/* Calls ENUM_FN for each conflict in GRAPH involving REG.  EXTRA is
+   passed back to ENUM_FN.  */
+
+void
+conflict_graph_enum (graph, reg, enum_fn, extra)
+     conflict_graph graph;
+     int reg;
+     conflict_graph_enum_fn enum_fn;
+     void *extra;
+{
+  conflict_graph_arc arc = graph->neighbor_heads[reg];
+  while (arc != NULL)
+    {
+      /* Invoke the callback.  */
+      if ((*enum_fn) (arc->smaller, arc->larger, extra))
+	/* Stop if requested.  */
+	break;
+      
+      /* Which next pointer to follow depends on whether REG is the
+	 smaller or larger reg in this conflict.  */
+      if (reg < arc->larger)
+	arc = arc->smaller_next;
+      else
+	arc = arc->larger_next;
+    }
+}
+
+/* For each conflict between a register x and SRC in GRAPH, adds a
+   conflict to GRAPH between x and TARGET.  */
+
+void
+conflict_graph_merge_regs (graph, target, src)
+     conflict_graph graph;
+     int target;
+     int src;
+{
+  conflict_graph_arc arc = graph->neighbor_heads[src];
+
+  if (target == src)
+    return;
+
+  while (arc != NULL)
+    {
+      int other = arc->smaller;
+      if (other == src)
+	other = arc->larger;
+
+      conflict_graph_add (graph, target, other);
+
+      /* Which next pointer to follow depends on whether REG is the
+	 smaller or larger reg in this conflict.  */
+      if (src < arc->larger)
+	arc = arc->smaller_next;
+      else
+	arc = arc->larger_next;
+    }
+}
+
+/* Holds context information while a conflict graph is being traversed
+   for printing.  */
+
+struct print_context
+{
+  /* The file pointer to which we're printing.  */
+  FILE *fp;
+
+  /* The reg whose conflicts we're printing.  */
+  int reg;
+
+  /* Whether a conflict has already been printed for this reg.  */
+  int started;
+};
+
+/* Callback function when enumerating conflicts during printing.  */
+
+static int
+print_conflict (reg1, reg2, contextp)
+     int reg1;
+     int reg2;
+     void *contextp;
+{
+  struct print_context *context = (struct print_context *) contextp;
+  int reg;
+
+  /* If this is the first conflict printed for this reg, start a new
+     line.  */
+  if (! context->started)
+    {
+      fprintf (context->fp, " %d:", context->reg);
+      context->started = 1;
+    }
+
+  /* Figure out the reg whose conflicts we're printing.  The other reg
+     is the interesting one.  */
+  if (reg1 == context->reg)
+    reg = reg2;
+  else if (reg2 == context->reg)
+    reg = reg1;
+  else
+    abort ();
+
+  /* Print the conflict.  */
+  fprintf (context->fp, " %d", reg);
+
+  /* Continue enumerating.  */
+  return 0;
+}
+
+/* Prints the conflicts in GRAPH to FP.  */
+
+void
+conflict_graph_print (graph, fp)
+     conflict_graph graph;
+     FILE *fp;
+{
+  int reg;
+  struct print_context context;
+  context.fp = fp;
+
+  fprintf (fp, "Conflicts:\n");
+  /* Loop over registers supported in this graph.  */
+  for (reg = 0; reg < graph->num_regs; ++reg)
+    {
+      context.reg = reg;
+      context.started = 0;
+      /* Scan the conflicts for reg, printing as we go.  A label for
+	 this line will be printed the first time a conflict is
+	 printed for the reg; we won't start a new line if this reg
+	 has no conflicts.  */
+      conflict_graph_enum (graph, reg, &print_conflict, &context);
+      /* If this reg does have conflicts, end the line.  */
+      if (context.started)
+	fputc ('\n', fp);
+    }
+}
+
+/* Callback function for note_stores.  */
+
+static void
+mark_reg (reg, setter, data)
+     rtx reg;
+     rtx setter ATTRIBUTE_UNUSED;
+     void *data;
+{
+  regset set = (regset) data;
+
+  if (GET_CODE (reg) == SUBREG)
+    reg = SUBREG_REG (reg);
+
+  /* We're only interested in regs.  */
+  if (GET_CODE (reg) != REG)
+    return;
+
+  SET_REGNO_REG_SET (set, REGNO (reg));
+}
+
+/* Allocates a conflict graph and computes conflicts over the current
+   function for the registers set in REGS.  The caller is responsible
+   for deallocating the return value.  
+
+   Preconditions: the flow graph must be in SSA form, and life
+   analysis (specifically, regs live at exit from each block) must be
+   up-to-date.  
+
+   This algorithm determines conflicts by walking the insns in each
+   block backwards.  We maintain the set of live regs at each insn,
+   starting with the regs live on exit from the block.  For each insn:
+ 
+     1. If a reg is set in this insns, it must be born here, since
+        we're in SSA.  Therefore, it was not live before this insns,
+	so remove it from the set of live regs.  
+
+     2. For each reg born in this insn, record a conflict between it
+	and every other reg live coming into this insn.  For each
+	existing conflict, one of the two regs must be born while the
+	other is alive.  See Morgan or elsewhere for a proof of this.
+
+     3. Regs clobbered by this insn must have been live coming into
+        it, so record them as such.  
+
+   The resulting conflict graph is not built for regs in REGS
+   themselves; rather, partition P is used to obtain the canonical reg
+   for each of these.  The nodes of the conflict graph are these
+   canonical regs instead.  */
+
+conflict_graph
+conflict_graph_compute (regs, p)
+     regset regs;
+     partition p;
+{
+  int b;
+  conflict_graph graph = conflict_graph_new (max_reg_num ());
+
+  for (b = n_basic_blocks; --b >= 0; )
+    {
+      basic_block bb = BASIC_BLOCK (b);
+      regset_head live_head;
+      regset live = &live_head;
+      regset_head born_head;
+      regset born = &born_head;
+      rtx insn;
+      rtx head;
+
+      INIT_REG_SET (live);
+      INIT_REG_SET (born);
+
+      /* Start with the regs that are live on exit, limited to those
+	 we're interested in.  */
+      COPY_REG_SET (live, bb->global_live_at_end);
+      AND_REG_SET (live, regs);
+
+      /* Walk the instruction stream backwards.  */
+      head = bb->head;
+      insn = bb->end;
+      for (insn = bb->end; 
+	   insn != head; 
+	   insn = PREV_INSN (insn))
+	{
+	  int born_reg;
+	  int live_reg;
+	  rtx link;
+
+	  /* Are we interested in this insn? */
+	  if (INSN_P (insn))
+	    {
+	      /* Determine which regs are set in this insn.  Since
+  	         we're in SSA form, if a reg is set here it isn't set
+  	         anywhere elso, so this insn is where the reg is born.  */
+	      CLEAR_REG_SET (born);
+	      note_stores (PATTERN (insn), mark_reg, (void *) born);
+#ifdef AUTO_INC_DEC
+	      for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+		if (REG_NOTE_KIND (link) == REG_INC)
+		  mark_reg (XEXP (link, 0), NULL_RTX, NULL);
+#endif
+	      AND_REG_SET (born, regs);
+	  
+	      /* Regs born here were not live before this insn.  */
+	      AND_COMPL_REG_SET (live, born);
+
+	      /* For every reg born here, add a conflict with every other
+  	         reg live coming into this insn.  */
+	      EXECUTE_IF_SET_IN_REG_SET (born, 
+					 FIRST_PSEUDO_REGISTER, 
+					 born_reg, {
+		EXECUTE_IF_SET_IN_REG_SET (live,
+					   FIRST_PSEUDO_REGISTER,
+					   live_reg, {
+		  /* Build the conflict graph in terms of canonical
+		     regnos.  */
+		  int b = partition_find (p, born_reg);
+		  int l = partition_find (p, live_reg);
+		  if (b != l)
+		    conflict_graph_add (graph, b, l);
+		});
+	      });
+
+	      /* Morgan's algorithm checks the operands of the insn
+	         and adds them to the set of live regs.  Instead, we
+	         use death information added by life analysis.  Regs
+	         dead after this instruction were live before it.  */
+	      for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+		if (REG_NOTE_KIND (link) == REG_DEAD)
+		  {
+		    int regno = REGNO (XEXP (link, 0));
+		    if (REGNO_REG_SET_P (regs, regno))
+		      SET_REGNO_REG_SET (live, regno);
+		  }
+	    }
+	}
+    }
+
+  return graph;
+}
+