[PATCH] Remove dead struct-equiv.c

[PATCH] Remove dead struct-equiv.c

[Andi Kleen]

While looking for something else I noticed that struct-equiv.c is completely
dead in trunk. The only caller outside the file is a function that is only
called by struct-equiv.c itself (condjump_equiv_p)

This patch removes all traces of struct-equiv.c from Makefiles and headers
and the call to the initialization function. It doesn't remove
the file itself; after it is applied a svn rm struct-equiv.c should be done.

Patch successfully bootstraped and test suite run on x86_64-linux.
I get a couple of unexpected failures, but they don't seem to be
related to my patch.

Patch should not change any gcc behaviour, just make the executable a little smaller.

I don't have SVN write access; please commit it if approved. Also
run svn rm gcc/struct-equiv.c while doing so.

-Andi

2007-07-22 Andi Kleen <ak@suse.de>

	* cfg_cleanup.c (condjump_equiv_p): Remove.
	* Makefile.in (OBJS-common): Remove struct-equiv.o
	* basic-block.h (struct_equiv_checkpoint, STRUCT_EQUIV_*,
	insns_match_p, struct_equiv_block_eq, struct_equiv_init, 
	rtx_equiv_p, condjump_equiv_p): Remove prototypes.

Index: gcc/cfgcleanup.c
===================================================================
--- gcc/cfgcleanup.c	(revision 126833)
+++ gcc/cfgcleanup.c	(working copy)
@@ -1130,134 +1130,6 @@
   return ninsns;
 }
 
-/* Return true iff the condbranches at the end of BB1 and BB2 match.  */
-bool
-condjump_equiv_p (struct equiv_info *info, bool call_init)
-{
-  basic_block bb1 = info->x_block;
-  basic_block bb2 = info->y_block;
-  edge b1 = BRANCH_EDGE (bb1);
-  edge b2 = BRANCH_EDGE (bb2);
-  edge f1 = FALLTHRU_EDGE (bb1);
-  edge f2 = FALLTHRU_EDGE (bb2);
-  bool reverse, match;
-  rtx set1, set2, cond1, cond2;
-  rtx src1, src2;
-  enum rtx_code code1, code2;
-
-  /* Get around possible forwarders on fallthru edges.  Other cases
-     should be optimized out already.  */
-  if (FORWARDER_BLOCK_P (f1->dest))
-    f1 = single_succ_edge (f1->dest);
-
-  if (FORWARDER_BLOCK_P (f2->dest))
-    f2 = single_succ_edge (f2->dest);
-
-  /* To simplify use of this function, return false if there are
-     unneeded forwarder blocks.  These will get eliminated later
-     during cleanup_cfg.  */
-  if (FORWARDER_BLOCK_P (f1->dest)
-      || FORWARDER_BLOCK_P (f2->dest)
-      || FORWARDER_BLOCK_P (b1->dest)
-      || FORWARDER_BLOCK_P (b2->dest))
-    return false;
-
-  if (f1->dest == f2->dest && b1->dest == b2->dest)
-    reverse = false;
-  else if (f1->dest == b2->dest && b1->dest == f2->dest)
-    reverse = true;
-  else
-    return false;
-
-  set1 = pc_set (BB_END (bb1));
-  set2 = pc_set (BB_END (bb2));
-  if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
-      != (XEXP (SET_SRC (set2), 1) == pc_rtx))
-    reverse = !reverse;
-
-  src1 = SET_SRC (set1);
-  src2 = SET_SRC (set2);
-  cond1 = XEXP (src1, 0);
-  cond2 = XEXP (src2, 0);
-  code1 = GET_CODE (cond1);
-  if (reverse)
-    code2 = reversed_comparison_code (cond2, BB_END (bb2));
-  else
-    code2 = GET_CODE (cond2);
-
-  if (code2 == UNKNOWN)
-    return false;
-
-  if (call_init && !struct_equiv_init (STRUCT_EQUIV_START | info->mode, info))
-    gcc_unreachable ();
-  /* Make the sources of the pc sets unreadable so that when we call
-     insns_match_p it won't process them.
-     The death_notes_match_p from insns_match_p won't see the local registers
-     used for the pc set, but that could only cause missed optimizations when
-     there are actually condjumps that use stack registers.  */
-  SET_SRC (set1) = pc_rtx;
-  SET_SRC (set2) = pc_rtx;
-  /* Verify codes and operands match.  */
-  if (code1 == code2)
-    {
-      match = (insns_match_p (BB_END (bb1), BB_END (bb2), info)
-	       && rtx_equiv_p (&XEXP (cond1, 0), XEXP (cond2, 0), 1, info)
-	       && rtx_equiv_p (&XEXP (cond1, 1), XEXP (cond2, 1), 1, info));
-
-    }
-  else if (code1 == swap_condition (code2))
-    {
-      match = (insns_match_p (BB_END (bb1), BB_END (bb2), info)
-	       && rtx_equiv_p (&XEXP (cond1, 1), XEXP (cond2, 0), 1, info)
-	       && rtx_equiv_p (&XEXP (cond1, 0), XEXP (cond2, 1), 1, info));
-
-    }
-  else
-    match = false;
-  SET_SRC (set1) = src1;
-  SET_SRC (set2) = src2;
-  match &= verify_changes (0);
-
-  /* If we return true, we will join the blocks.  Which means that
-     we will only have one branch prediction bit to work with.  Thus
-     we require the existing branches to have probabilities that are
-     roughly similar.  */
-  if (match
-      && !optimize_size
-      && maybe_hot_bb_p (bb1)
-      && maybe_hot_bb_p (bb2))
-    {
-      int prob2;
-
-      if (b1->dest == b2->dest)
-	prob2 = b2->probability;
-      else
-	/* Do not use f2 probability as f2 may be forwarded.  */
-	prob2 = REG_BR_PROB_BASE - b2->probability;
-
-      /* Fail if the difference in probabilities is greater than 50%.
-	 This rules out two well-predicted branches with opposite
-	 outcomes.  */
-      if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
-	{
-	  if (dump_file)
-	    fprintf (dump_file,
-		     "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
-		     bb1->index, bb2->index, b1->probability, prob2);
-
-	  match = false;
-	}
-    }
-
-  if (dump_file && match)
-    fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
-	     bb1->index, bb2->index);
-
-  if (!match)
-    cancel_changes (0);
-  return match;
-}
-
 /* Return true iff outgoing edges of BB1 and BB2 match, together with
    the branch instruction.  This means that if we commonize the control
    flow before end of the basic block, the semantic remains unchanged.
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 126833)
+++ gcc/Makefile.in	(working copy)
@@ -1109,7 +1109,6 @@
 	stmt.o \
 	stor-layout.o \
 	stringpool.o \
-	struct-equiv.o \
 	targhooks.o \
 	timevar.o \
 	toplev.o \
Index: gcc/basic-block.h
===================================================================
--- gcc/basic-block.h	(revision 126833)
+++ gcc/basic-block.h	(working copy)
@@ -789,17 +789,6 @@
 					   insns.  */
 #define CLEANUP_CFGLAYOUT	32	/* Do cleanup in cfglayout mode.  */
 
-/* The following are ORed in on top of the CLEANUP* flags in calls to
-   struct_equiv_block_eq.  */
-#define STRUCT_EQUIV_START	64	 /* Initializes the search range.  */
-#define STRUCT_EQUIV_RERUN	128	/* Rerun to find register use in
-					   found equivalence.  */
-#define STRUCT_EQUIV_FINAL	256	/* Make any changes necessary to get
-					   actual equivalence.  */
-#define STRUCT_EQUIV_NEED_FULL_BLOCK 512 /* struct_equiv_block_eq is required
-					     to match only full blocks  */
-#define STRUCT_EQUIV_MATCH_JUMPS 1024	/* Also include the jumps at the end of the block in the comparison.  */
-
 /* In lcm.c */
 extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *,
 				       sbitmap *, sbitmap *, sbitmap **,
@@ -946,171 +935,6 @@
 
 #include "cfghooks.h"
 
-/* In struct-equiv.c */
-
-/* Constants used to size arrays in struct equiv_info (currently only one).
-   When these limits are exceeded, struct_equiv returns zero.
-   The maximum number of pseudo registers that are different in the two blocks,
-   but appear in equivalent places and are dead at the end (or where one of
-   a pair is dead at the end).  */
-#define STRUCT_EQUIV_MAX_LOCAL 16
-/* The maximum number of references to an input register that struct_equiv
-   can handle.  */
-
-/* Structure used to track state during struct_equiv that can be rolled
-   back when we find we can't match an insn, or if we want to match part
-   of it in a different way.
-   This information pertains to the pair of partial blocks that has been
-   matched so far.  Since this pair is structurally equivalent, this is
-   conceptually just one partial block expressed in two potentially
-   different ways.  */
-struct struct_equiv_checkpoint
-{
-  int ninsns;       /* Insns are matched so far.  */
-  int local_count;  /* Number of block-local registers.  */
-  int input_count;  /* Number of inputs to the block.  */
-
-  /* X_START and Y_START are the first insns (in insn stream order)
-     of the partial blocks that have been considered for matching so far.
-     Since we are scanning backwards, they are also the instructions that
-     are currently considered - or the last ones that have been considered -
-     for matching (Unless we tracked back to these because a preceding
-     instruction failed to match).  */
-  rtx x_start, y_start;
-
-  /*  INPUT_VALID indicates if we have actually set up X_INPUT / Y_INPUT
-      during the current pass; we keep X_INPUT / Y_INPUT around between passes
-      so that we can match REG_EQUAL / REG_EQUIV notes referring to these.  */
-  bool input_valid;
-
-  /* Some information would be expensive to exactly checkpoint, so we
-     merely increment VERSION any time information about local
-     registers, inputs and/or register liveness changes.  When backtracking,
-     it is decremented for changes that can be undone, and if a discrepancy
-     remains, NEED_RERUN in the relevant struct equiv_info is set to indicate
-     that a new pass should be made over the entire block match to get
-     accurate register information.  */
-  int version;
-};
-
-/* A struct equiv_info is used to pass information to struct_equiv and
-   to gather state while two basic blocks are checked for structural
-   equivalence.  */
-
-struct equiv_info
-{
-  /* Fields set up by the caller to struct_equiv_block_eq */
-
-  basic_block x_block, y_block;  /* The two blocks being matched.  */
-
-  /* MODE carries the mode bits from cleanup_cfg if we are called from
-     try_crossjump_to_edge, and additionally it carries the
-     STRUCT_EQUIV_* bits described above.  */
-  int mode;
-
-  /* INPUT_COST is the cost that adding an extra input to the matched blocks
-     is supposed to have, and is taken into account when considering if the
-     matched sequence should be extended backwards.  input_cost < 0 means
-     don't accept any inputs at all.  */
-  int input_cost;
-
-
-  /* Fields to track state inside of struct_equiv_block_eq.  Some of these
-     are also outputs.  */
-
-  /* X_INPUT and Y_INPUT are used by struct_equiv to record a register that
-     is used as an input parameter, i.e. where different registers are used
-     as sources.  This is only used for a register that is live at the end
-     of the blocks, or in some identical code at the end of the blocks;
-     Inputs that are dead at the end go into X_LOCAL / Y_LOCAL.  */
-  rtx x_input, y_input;
-  /* When a previous pass has identified a valid input, INPUT_REG is set
-     by struct_equiv_block_eq, and it is henceforth replaced in X_BLOCK
-     for the input.  */
-  rtx input_reg;
-
-  /* COMMON_LIVE keeps track of the registers which are currently live
-     (as we scan backwards from the end) and have the same numbers in both
-     blocks.  N.B. a register that is in common_live is unsuitable to become
-     a local reg.  */
-  regset common_live;
-  /* Likewise, X_LOCAL_LIVE / Y_LOCAL_LIVE keep track of registers that are
-     local to one of the blocks; these registers must not be accepted as
-     identical when encountered in both blocks.  */
-  regset x_local_live, y_local_live;
-
-  /* EQUIV_USED indicates for which insns a REG_EQUAL or REG_EQUIV note is
-     being used, to avoid having to backtrack in the next pass, so that we
-     get accurate life info for this insn then.  For each such insn,
-     the bit with the number corresponding to the CUR.NINSNS value at the
-     time of scanning is set.  */
-  bitmap equiv_used;
-
-  /* Current state that can be saved & restored easily.  */
-  struct struct_equiv_checkpoint cur;
-  /* BEST_MATCH is used to store the best match so far, weighing the
-     cost of matched insns COSTS_N_INSNS (CUR.NINSNS) against the cost
-     CUR.INPUT_COUNT * INPUT_COST of setting up the inputs.  */
-  struct struct_equiv_checkpoint best_match;
-  /* If a checkpoint restore failed, or an input conflict newly arises,
-     NEED_RERUN is set.  This has to be tested by the caller to re-run
-     the comparison if the match appears otherwise sound.  The state kept in
-     x_start, y_start, equiv_used and check_input_conflict ensures that
-     we won't loop indefinitely.  */
-  bool need_rerun;
-  /* If there is indication of an input conflict at the end,
-     CHECK_INPUT_CONFLICT is set so that we'll check for input conflicts
-     for each insn in the next pass.  This is needed so that we won't discard
-     a partial match if there is a longer match that has to be abandoned due
-     to an input conflict.  */
-  bool check_input_conflict;
-  /* HAD_INPUT_CONFLICT is set if CHECK_INPUT_CONFLICT was already set and we
-     have passed a point where there were multiple dying inputs.  This helps
-     us decide if we should set check_input_conflict for the next pass.  */
-  bool had_input_conflict;
-
-  /* LIVE_UPDATE controls if we want to change any life info at all.  We
-     set it to false during REG_EQUAL / REG_EUQIV note comparison of the final
-     pass so that we don't introduce new registers just for the note; if we
-     can't match the notes without the current register information, we drop
-     them.  */
-  bool live_update;
-
-  /* X_LOCAL and Y_LOCAL are used to gather register numbers of register pairs
-     that are local to X_BLOCK and Y_BLOCK, with CUR.LOCAL_COUNT being the index
-     to the next free entry.  */
-  rtx x_local[STRUCT_EQUIV_MAX_LOCAL], y_local[STRUCT_EQUIV_MAX_LOCAL];
-  /* LOCAL_RVALUE is nonzero if the corresponding X_LOCAL / Y_LOCAL entry
-     was a source operand (including STRICT_LOW_PART) for the last invocation
-     of struct_equiv mentioning it, zero if it was a destination-only operand.
-     Since we are scanning backwards, this means the register is input/local
-     for the (partial) block scanned so far.  */
-  bool local_rvalue[STRUCT_EQUIV_MAX_LOCAL];
-
-
-  /* Additional fields that are computed for the convenience of the caller.  */
-
-  /* DYING_INPUTS is set to the number of local registers that turn out
-     to be inputs to the (possibly partial) block.  */
-  int dying_inputs;
-  /* X_END and Y_END are the last insns in X_BLOCK and Y_BLOCK, respectively,
-     that are being compared.  A final jump insn will not be included.  */
-  rtx x_end, y_end;
-
-  /* If we are matching tablejumps, X_LABEL in X_BLOCK corresponds to
-     Y_LABEL in Y_BLOCK.  */
-  rtx x_label, y_label;
-
-};
-
-extern bool insns_match_p (rtx, rtx, struct equiv_info *);
-extern int struct_equiv_block_eq (int, struct equiv_info *);
-extern bool struct_equiv_init (int, struct equiv_info *);
-extern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *);
-
-/* In cfgrtl.c */
-extern bool condjump_equiv_p (struct equiv_info *, bool);
-
 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH.  */
 static inline bool
 bb_has_eh_pred (basic_block bb)

[PATCH] Remove dead struct-equiv.c

[Kenneth Zadeck]

> While looking for something else I noticed that struct-equiv.c is completely
> dead in trunk. The only caller outside the file is a function that is only
> called by struct-equiv.c itself (condjump_equiv_p)
> 
> This patch removes all traces of struct-equiv.c from Makefiles and headers
> and the call to the initialization function. It doesn't remove
> the file itself; after it is applied a svn rm struct-equiv.c should be done.
> 
> Patch successfully bootstraped and test suite run on x86_64-linux.
> I get a couple of unexpected failures, but they don't seem to be
> related to my patch.
> 
> Patch should not change any gcc behaviour, just make the executable a little smaller.
> 
> I don't have SVN write access; please commit it if approved. Also
> run svn rm gcc/struct-equiv.c while doing so.
> 
> -Andi
> 
> 2007-07-22 Andi Kleen <ak@suse.de>
> 
> 	* cfg_cleanup.c (condjump_equiv_p): Remove.
> 	* Makefile.in (OBJS-common): Remove struct-equiv.o
> 	* basic-block.h (struct_equiv_checkpoint, STRUCT_EQUIV_*,
> 	insns_match_p, struct_equiv_block_eq, struct_equiv_init, 
> 	rtx_equiv_p, condjump_equiv_p): Remove prototypes.

I would vote to accept this patch.  However, I do not have the
authority to approve this.  This is going to require a middle end
maintainer to approve.  

According to Steven Bosscher, this code was originally written by
Joern and was turned off because it was too slow. I think that the
fact that it was not orphaned by the dataflow commit puts me off the
list of possible approvers.

In support of the code, (and also according to stevenb) 


>  The original plan with this code was to improve
> if-conversion of longer sequences, such as the examples of PR10050,
> PR20070,  PR21803, and PR29144. It would also allow cross-jumping of
> longer sequences, especially because the live range splitting passes
> (i.e. out-of-ssa and web) tend to destroy ifcvt and crossjump
> opportunities with out current exact insn sequence matching. The
> struct-equiv stuff was supposed to overcome this by comparing
> sequences by semantics, instead of by lexical equivalence. 

However, the methods employed in this code are not suitable for gcc
and a major rewrite is needed to get this function into the compiler.

I will, if this patch is accepted, do the work of actually doing the
commit.  Andi does not have write after access, but according to
Edelsohn, has a proper assignment.  

Kenny