2008-12-18 Kenneth Zadeck <zadeck@naturalbridge.com>

	PR rtl-optimization/37922
	* dse.c (bb_info): Added regs_live field.
	(look_for_hardregs): New function.
	(replace_read): Added regs_live parameter and code to check that
	shift sequence does not clobber live hardregs.
	(check_mem_read_rtx): Added parameter to replace_read.
	(dse_step1): Added regs_live bitmap and initialize it.
	(rest_of_handle_dse): Added DF_NOTES problem and earlier call to
	df_analyze.
	* df-problems.c Renamed to 
	df_simulate_initialize_backwards.
	(df_simulate_one_insn): Renamed to
	df_simulate_one_insn_backwards.
	(df_simulate_artificial_refs_at_top): Renamed to 
	df_simulate_finalize_backwards.
	(df_simulate_initialized_forwards,
	df_simulate_one_insn_forwards,
	df_simulate_finalize_backwards): New functions.
	* df.h (df_simulate_artificial_refs_at_end): Renamed to 
	df_simulate_initialize_backwards.
	(df_simulate_one_insn): Renamed to
	df_simulate_one_insn_backwards.
	(df_simulate_artificial_refs_at_top): Renamed to 
	df_simulate_finalize_backwards.
	(df_simulate_initialized_forwards,
	df_simulate_one_insn_forwards,
	df_simulate_finalize_backwards): New functions.
	* ra-conflict.c (global_conflicts): Renamed
	df_simulate_artificial_refs_at_end to
	df_simulate_initialize_backwards.
	* sel-sched.c (propagate_lv_set): Renamed df_simulate_one_insn to
	df_simulate_one_insn_backwards.
	* ifcvt.c (dead_or_predicable): Renamed
	df_simulate_artificial_refs_at_end to
	df_simulate_initialize_backwards. Renamed df_simulate_one_insn to
	df_simulate_one_insn_backwards.
	* recog.c (peephole2_optimize): Ditto.
	* rtl-factoring (collect_pattern_seqs, clear_regs_live_in_seq): Ditto.

2008-12-18  Kenneth Zadeck <zadeck@naturalbridge.com>

	PR rtl-optimization/37922
	* g++.dg/torture/pr37922.C: New test.



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

12 files changed, 743 insertions, 35 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a76282c0984..7862b105683 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,44 @@
+2008-12-18  Kenneth Zadeck <zadeck@naturalbridge.com>
+
+	PR rtl-optimization/37922
+	* dse.c (bb_info): Added regs_live field.
+	(look_for_hardregs): New function.
+	(replace_read): Added regs_live parameter and code to check that
+	shift sequence does not clobber live hardregs.
+	(check_mem_read_rtx): Added parameter to replace_read.
+	(dse_step1): Added regs_live bitmap and initialize it.
+	(rest_of_handle_dse): Added DF_NOTES problem and earlier call to
+	df_analyze.
+	* df-problems.c Renamed to 
+	df_simulate_initialize_backwards.
+	(df_simulate_one_insn): Renamed to
+	df_simulate_one_insn_backwards.
+	(df_simulate_artificial_refs_at_top): Renamed to 
+	df_simulate_finalize_backwards.
+	(df_simulate_initialized_forwards,
+	df_simulate_one_insn_forwards,
+	df_simulate_finalize_backwards): New functions.
+	* df.h (df_simulate_artificial_refs_at_end): Renamed to 
+	df_simulate_initialize_backwards.
+	(df_simulate_one_insn): Renamed to
+	df_simulate_one_insn_backwards.
+	(df_simulate_artificial_refs_at_top): Renamed to 
+	df_simulate_finalize_backwards.
+	(df_simulate_initialized_forwards,
+	df_simulate_one_insn_forwards,
+	df_simulate_finalize_backwards): New functions.
+	* ra-conflict.c (global_conflicts): Renamed
+	df_simulate_artificial_refs_at_end to
+	df_simulate_initialize_backwards.
+	* sel-sched.c (propagate_lv_set): Renamed df_simulate_one_insn to
+	df_simulate_one_insn_backwards.
+	* ifcvt.c (dead_or_predicable): Renamed
+	df_simulate_artificial_refs_at_end to
+	df_simulate_initialize_backwards. Renamed df_simulate_one_insn to
+	df_simulate_one_insn_backwards.
+	* recog.c (peephole2_optimize): Ditto.
+	* rtl-factoring (collect_pattern_seqs, clear_regs_live_in_seq): Ditto.
+
 2008-12-18  Jakub Jelinek  <jakub@redhat.com>
 
 	PR middle-end/38533
diff --git a/gcc/dce.c b/gcc/dce.c
index 63ea3806606..1adea75570d 100644
--- a/gcc/dce.c
+++ b/gcc/dce.c
@@ -607,7 +607,7 @@ dce_process_block (basic_block bb, bool redo_out, bitmap au)
 
   bitmap_copy (local_live, DF_LR_OUT (bb));
 
-  df_simulate_artificial_refs_at_end (bb, local_live);
+  df_simulate_initialize_backwards (bb, local_live);
 
   FOR_BB_INSNS_REVERSE (bb, insn)
     if (INSN_P (insn))
@@ -636,7 +636,7 @@ dce_process_block (basic_block bb, bool redo_out, bitmap au)
 	  df_simulate_uses (insn, local_live);
       }
   
-  df_simulate_artificial_refs_at_top (bb, local_live);
+  df_simulate_finalize_backwards (bb, local_live);
 
   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
   if (block_changed)
diff --git a/gcc/df-problems.c b/gcc/df-problems.c
index 25dea30817b..829698ba1b3 100644
--- a/gcc/df-problems.c
+++ b/gcc/df-problems.c
@@ -3759,24 +3759,19 @@ df_simulate_fixup_sets (basic_block bb, bitmap live)
    The following three functions are used only for BACKWARDS scanning:
    i.e. they process the defs before the uses.
 
-   df_simulate_artificial_refs_at_end should be called first with a
+   df_simulate_initialize_backwards should be called first with a
    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
-   df_simulate_one_insn should be called for each insn in the block,
-   starting with the last on.  Finally,
-   df_simulate_artificial_refs_at_top can be called to get a new value
+   df_simulate_one_insn_backwards should be called for each insn in
+   the block, starting with the last on.  Finally,
+   df_simulate_finalize_backwards can be called to get a new value
    of the sets at the top of the block (this is rarely used).
-
-   It would be not be difficult to define a similar set of functions
-   that work in the forwards direction.  In that case the functions
-   would ignore the use sets and look for the REG_DEAD and REG_UNUSED
-   notes.
-----------------------------------------------------------------------------*/
+   ----------------------------------------------------------------------------*/
 
 /* Apply the artificial uses and defs at the end of BB in a backwards
    direction.  */
 
 void 
-df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
+df_simulate_initialize_backwards (basic_block bb, bitmap live)
 {
   df_ref *def_rec;
   df_ref *use_rec;
@@ -3801,7 +3796,7 @@ df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
 
 void 
-df_simulate_one_insn (basic_block bb, rtx insn, bitmap live)
+df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
 {
   if (! INSN_P (insn))
     return;	
@@ -3816,7 +3811,7 @@ df_simulate_one_insn (basic_block bb, rtx insn, bitmap live)
    direction.  */
 
 void 
-df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
+df_simulate_finalize_backwards (basic_block bb, bitmap live)
 {
   df_ref *def_rec;
 #ifdef EH_USES
@@ -3840,3 +3835,92 @@ df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
     }
 #endif
 }
+/*----------------------------------------------------------------------------
+   The following three functions are used only for FORWARDS scanning:
+   i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
+   Thus it is important to add the DF_NOTES problem to the stack of 
+   problems computed before using these functions.
+
+   df_simulate_initialize_forwards should be called first with a
+   bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
+   df_simulate_one_insn_forwards should be called for each insn in
+   the block, starting with the last on.  Finally,
+   df_simulate_finalize_forwards can be called to get a new value
+   of the sets at the bottom of the block (this is rarely used).
+   ----------------------------------------------------------------------------*/
+
+/* Apply the artificial uses and defs at the top of BB in a backwards
+   direction.  */
+
+void 
+df_simulate_initialize_forwards (basic_block bb, bitmap live)
+{
+  df_ref *def_rec;
+  int bb_index = bb->index;
+  
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+	bitmap_clear_bit (live, DF_REF_REGNO (def));
+    }
+}
+
+/* Simulate the backwards effects of INSN on the bitmap LIVE.  */
+
+void 
+df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
+{
+  rtx link;
+  if (! INSN_P (insn))
+    return;	
+
+  /* Make sure that the DF_NOTES really is an active df problem.  */ 
+  gcc_assert (df_note);
+
+  df_simulate_defs (insn, live);
+
+  /* Clear all of the registers that go dead.  */
+  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+    {
+      switch (REG_NOTE_KIND (link))
+	case REG_DEAD:
+	case REG_UNUSED:
+	{
+	  rtx reg = XEXP (link, 0);
+	  int regno = REGNO (reg);
+	  if (regno < FIRST_PSEUDO_REGISTER)
+	    {
+	      int n = hard_regno_nregs[regno][GET_MODE (reg)];
+	      while (--n >= 0)
+		bitmap_clear_bit (live, regno + n);
+	    }
+	  else 
+	    bitmap_clear_bit (live, regno);
+	  break;
+	default:
+	  break;
+	}
+    }
+  df_simulate_fixup_sets (bb, live);
+}
+
+
+/* Apply the artificial uses and defs at the end of BB in a backwards
+   direction.  */
+
+void 
+df_simulate_finalize_forwards (basic_block bb, bitmap live)
+{
+  df_ref *def_rec;
+  int bb_index = bb->index;
+  
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+	bitmap_clear_bit (live, DF_REF_REGNO (def));
+    }
+}
+
+
diff --git a/gcc/df.h b/gcc/df.h
index 979065aa269..5cd5dfccb25 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -959,9 +959,12 @@ extern void df_note_add_problem (void);
 extern void df_simulate_find_defs (rtx, bitmap);
 extern void df_simulate_defs (rtx, bitmap);
 extern void df_simulate_uses (rtx, bitmap);
-extern void df_simulate_artificial_refs_at_end (basic_block, bitmap);
-extern void df_simulate_one_insn (basic_block, rtx, bitmap);
-extern void df_simulate_artificial_refs_at_top (basic_block, bitmap);
+extern void df_simulate_initialize_backwards (basic_block, bitmap);
+extern void df_simulate_one_insn_backwards (basic_block, rtx, bitmap);
+extern void df_simulate_finalize_backwards (basic_block, bitmap);
+extern void df_simulate_initialize_forwards (basic_block, bitmap);
+extern void df_simulate_one_insn_forwards (basic_block, rtx, bitmap);
+extern void df_simulate_finalize_forwards (basic_block, bitmap);
 
 /* Functions defined in df-scan.c.  */
 
diff --git a/gcc/dse.c b/gcc/dse.c
index d7fb2d8aa20..3269c7adaff 100644
--- a/gcc/dse.c
+++ b/gcc/dse.c
@@ -374,6 +374,10 @@ struct bb_info
      operations.  */
   bool apply_wild_read;
 
+  /* The following 4 bitvectors hold information about which positions
+     of which stores are live or dead.  They are indexed by
+     get_bitmap_index.  */
+
   /* The set of store positions that exist in this block before a wild read.  */
   bitmap gen;
   
@@ -401,6 +405,14 @@ struct bb_info
      just initializes the vector from one of the out sets of the
      successors of the block.  */
   bitmap out;
+
+  /* The following bitvector is indexed by the reg number.  It
+     contains the set of regs that are live at the current instruction
+     being processed.  While it contains info for all of the
+     registers, only the pseudos are actually examined.  It is used to
+     assure that shift sequences that are inserted do not accidently
+     clobber live hard regs.  */
+  bitmap regs_live;
 };
 
 typedef struct bb_info *bb_info_t;
@@ -1533,6 +1545,25 @@ find_shift_sequence (int access_size,
 }
 
 
+/* Call back for note_stores to find the hard regs set or clobbered by
+   insn.  Data is a bitmap of the hardregs set so far.  */
+
+static void
+look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
+{
+  bitmap regs_set = (bitmap) data;
+
+  if (REG_P (x)
+      && REGNO (x) < FIRST_PSEUDO_REGISTER)
+    {
+      int regno = REGNO (x);
+      int n = hard_regno_nregs[regno][GET_MODE (x)];
+      while (--n >= 0)
+	bitmap_set_bit (regs_set, regno + n);
+    }
+}
+
+
 /* Take a sequence of:
      A <- r1
      ...
@@ -1566,13 +1597,13 @@ find_shift_sequence (int access_size,
 
 static bool
 replace_read (store_info_t store_info, insn_info_t store_insn, 
-	      read_info_t read_info, insn_info_t read_insn, rtx *loc)
+	      read_info_t read_info, insn_info_t read_insn, rtx *loc, bitmap regs_live)
 {
   enum machine_mode store_mode = GET_MODE (store_info->mem);
   enum machine_mode read_mode = GET_MODE (read_info->mem);
   int shift;
   int access_size; /* In bytes.  */
-  rtx insns, read_reg;
+  rtx insns, this_insn, read_reg;
 
   if (!dbg_cnt (dse))
     return false;
@@ -1624,6 +1655,34 @@ replace_read (store_info_t store_info, insn_info_t store_insn,
   insns = get_insns ();
   end_sequence ();
 
+  if (insns != NULL_RTX)
+    {
+      /* Now we have to scan the set of new instructions to see if the
+	 sequence contains and sets of hardregs that happened to be
+	 live at this point.  For instance, this can happen if one of
+	 the insns sets the CC and the CC happened to be live at that
+	 point.  This does occasionally happen, see PR 37922.  */
+      bitmap regs_set = BITMAP_ALLOC (NULL);
+
+      for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
+	note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
+      
+      bitmap_and_into (regs_set, regs_live);
+      if (!bitmap_empty_p (regs_set))
+	{
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, 
+		       "abandoning replacement because sequence clobbers live hardregs:");
+	      df_print_regset (dump_file, regs_set);
+	    }
+	  
+	  BITMAP_FREE (regs_set);
+	  return false;
+	}
+      BITMAP_FREE (regs_set);
+    }
+
   if (validate_change (read_insn->insn, loc, read_reg, 0))
     {
       deferred_change_t deferred_change =
@@ -1842,7 +1901,7 @@ check_mem_read_rtx (rtx *loc, void *data)
 
 		      if ((store_info->positions_needed & mask) == mask
 			  && replace_read (store_info, i_ptr, 
-					   read_info, insn_info, loc))
+					   read_info, insn_info, loc, bb_info->regs_live))
 			return 0;
 		    }
 		  /* The bases are the same, just see if the offsets
@@ -1911,7 +1970,7 @@ check_mem_read_rtx (rtx *loc, void *data)
 
 	      if ((store_info->positions_needed & mask) == mask
 		  && replace_read (store_info, i_ptr, 
-				   read_info, insn_info, loc))
+				   read_info, insn_info, loc, bb_info->regs_live))
 		return 0;
 	    }
 
@@ -2139,7 +2198,8 @@ static void
 dse_step1 (void)
 {
   basic_block bb;
-
+  bitmap regs_live = BITMAP_ALLOC (NULL);
+  
   cselib_init (false);
   all_blocks = BITMAP_ALLOC (NULL);
   bitmap_set_bit (all_blocks, ENTRY_BLOCK);
@@ -2152,6 +2212,10 @@ dse_step1 (void)
 
       memset (bb_info, 0, sizeof (struct bb_info));
       bitmap_set_bit (all_blocks, bb->index);
+      bb_info->regs_live = regs_live;
+
+      bitmap_copy (regs_live, DF_LR_IN (bb));
+      df_simulate_initialize_forwards (bb, regs_live);
 
       bb_table[bb->index] = bb_info;
       cselib_discard_hook = remove_useless_values;
@@ -2172,6 +2236,8 @@ dse_step1 (void)
 	      if (INSN_P (insn))
 		scan_insn (bb_info, insn);
 	      cselib_process_insn (insn);
+	      if (INSN_P (insn))
+		df_simulate_one_insn_forwards (bb, insn, regs_live);
 	    }
 	  
 	  /* This is something of a hack, because the global algorithm
@@ -2238,8 +2304,10 @@ dse_step1 (void)
 
 	  free_alloc_pool (cse_store_info_pool);
 	}
+      bb_info->regs_live = NULL;
     }
 
+  BITMAP_FREE (regs_live);
   cselib_finish ();
   htab_empty (rtx_group_table);
 }
@@ -3239,6 +3307,11 @@ rest_of_handle_dse (void)
 
   df_set_flags (DF_DEFER_INSN_RESCAN);
 
+  /* Need the notes since we must track live hardregs in the forwards
+     direction.  */
+  df_note_add_problem ();
+  df_analyze ();
+
   dse_step0 ();
   dse_step1 ();
   dse_step2_init ();
diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index cd148abd7a9..dc5788d5440 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -3950,13 +3950,13 @@ dead_or_predicable (basic_block test_bb, basic_block merge_bb,
       /* The loop below takes the set of live registers 
          after JUMP, and calculates the live set before EARLIEST. */
       bitmap_copy (test_live, df_get_live_in (other_bb));
-      df_simulate_artificial_refs_at_end (test_bb, test_live);
+      df_simulate_initialize_backwards (test_bb, test_live);
       for (insn = jump; ; insn = prev)
 	{
 	  if (INSN_P (insn))
 	    {
 	      df_simulate_find_defs (insn, test_set);
-	      df_simulate_one_insn (test_bb, insn, test_live);
+	      df_simulate_one_insn_backwards (test_bb, insn, test_live);
 	    }
 	  prev = PREV_INSN (insn);
 	  if (insn == earliest)
diff --git a/gcc/ra-conflict.c b/gcc/ra-conflict.c
index e0ffbbd4c3f..eb732861442 100644
--- a/gcc/ra-conflict.c
+++ b/gcc/ra-conflict.c
@@ -774,7 +774,7 @@ global_conflicts (void)
       bitmap_iterator bi;
 
       bitmap_copy (live, DF_LIVE_OUT (bb));
-      df_simulate_artificial_refs_at_end (bb, live);
+      df_simulate_initialize_backwards (bb, live);
 
       sparseset_clear (allocnos_live);
       memset (live_subregs_used, 0, max_allocno * sizeof (int));
diff --git a/gcc/recog.c b/gcc/recog.c
index 7ab6a1de4e0..0e2dd1bd60d 100644
--- a/gcc/recog.c
+++ b/gcc/recog.c
@@ -3039,7 +3039,7 @@ peephole2_optimize (void)
 
       /* Start up propagation.  */
       bitmap_copy (live, DF_LR_OUT (bb));
-      df_simulate_artificial_refs_at_end (bb, live);
+      df_simulate_initialize_backwards (bb, live);
       bitmap_copy (peep2_insn_data[MAX_INSNS_PER_PEEP2].live_before, live);
 
       for (insn = BB_END (bb); ; insn = prev)
@@ -3059,7 +3059,7 @@ peephole2_optimize (void)
 		  && peep2_insn_data[peep2_current].insn == NULL_RTX)
 		peep2_current_count++;
 	      peep2_insn_data[peep2_current].insn = insn;
-	      df_simulate_one_insn (bb, insn, live);
+	      df_simulate_one_insn_backwards (bb, insn, live);
 	      COPY_REG_SET (peep2_insn_data[peep2_current].live_before, live);
 
 	      if (RTX_FRAME_RELATED_P (insn))
@@ -3218,7 +3218,7 @@ peephole2_optimize (void)
 			    peep2_current_count++;
 			  peep2_insn_data[i].insn = x;
 			  df_insn_rescan (x);
-			  df_simulate_one_insn (bb, x, live);
+			  df_simulate_one_insn_backwards (bb, x, live);
 			  bitmap_copy (peep2_insn_data[i].live_before, live);
 			}
 		      x = PREV_INSN (x);
diff --git a/gcc/rtl-factoring.c b/gcc/rtl-factoring.c
index 07c66e20cc3..4c879691e9f 100644
--- a/gcc/rtl-factoring.c
+++ b/gcc/rtl-factoring.c
@@ -464,7 +464,7 @@ collect_pattern_seqs (void)
     /* Initialize liveness propagation.  */
     INIT_REG_SET (&live);
     bitmap_copy (&live, DF_LR_OUT (bb));
-    df_simulate_artificial_refs_at_end (bb, &live);
+    df_simulate_initialize_backwards (bb, &live);
 
     /* Propagate liveness info and mark insns where a stack reg is live.  */
     insn = BB_END (bb);
@@ -486,7 +486,7 @@ collect_pattern_seqs (void)
 	  }
 	if (insn == BB_HEAD (bb))
 	  break;
-	df_simulate_one_insn (bb, insn, &live);
+	df_simulate_one_insn_backwards (bb, insn, &live);
 	insn = prev;
       }
 
@@ -572,11 +572,11 @@ clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
   bb = BLOCK_FOR_INSN (insn);
   INIT_REG_SET (&live);
   bitmap_copy (&live, DF_LR_OUT (bb));
-  df_simulate_artificial_refs_at_end (bb, &live);
+  df_simulate_initialize_backwards (bb, &live);
 
   /* Propagate until INSN if found.  */
   for (x = BB_END (bb); x != insn; x = PREV_INSN (x))
-    df_simulate_one_insn (bb, x, &live);
+    df_simulate_one_insn_backwards (bb, x, &live);
 
   /* Clear registers live after INSN.  */
   renumbered_reg_set_to_hard_reg_set (&hlive, &live);
@@ -586,7 +586,7 @@ clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
   for (i = 0; i < length;)
     {
       rtx prev = PREV_INSN (x);
-      df_simulate_one_insn (bb, x, &live);
+      df_simulate_one_insn_backwards (bb, x, &live);
 
       if (INSN_P (x))
         {
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index 9736e34155b..c98a52162dc 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -2947,7 +2947,7 @@ propagate_lv_set (regset lv, insn_t insn)
   if (INSN_NOP_P (insn))
     return;
 
-  df_simulate_one_insn (BLOCK_FOR_INSN (insn), insn, lv);
+  df_simulate_one_insn_backwards (BLOCK_FOR_INSN (insn), insn, lv);
 }
 
 /* Return livness set at the end of BB.  */
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index a6fec3bb0b2..83063037de9 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2008-12-18  Kenneth Zadeck <zadeck@naturalbridge.com>
+
+	PR rtl-optimization/37922
+	* g++.dg/torture/pr37922.C: New test.
+
 2008-12-18  Daniel Kraft  <d@domob.eu>
 
 	PR fortran/31822
diff --git a/gcc/testsuite/g++.dg/torture/pr37922.C b/gcc/testsuite/g++.dg/torture/pr37922.C
new file mode 100644
index 00000000000..a7d05ab0fe8
--- /dev/null
+++ b/gcc/testsuite/g++.dg/torture/pr37922.C
@@ -0,0 +1,502 @@
+// { dg-do run }
+// { dg-options "-fpic" { target fpic } }
+
+typedef __SIZE_TYPE__ size_t;
+
+template <typename NumType>
+inline
+NumType
+absolute(NumType const& x)
+{
+  if (x < NumType(0)) return -x;
+  return x;
+}
+
+class trivial_accessor
+{
+  public:
+    typedef size_t index_type;
+    struct index_value_type {};
+
+    trivial_accessor() : size_(0) {}
+
+    trivial_accessor(size_t const& n) : size_(n) {}
+
+    size_t size_1d() const { return size_; }
+
+  protected:
+    size_t size_;
+};
+
+namespace N0
+{
+  template <typename ElementType,
+            typename AccessorType = trivial_accessor>
+  class const_ref
+  {
+    public:
+      typedef ElementType value_type;
+      typedef size_t size_type;
+
+      typedef AccessorType accessor_type;
+      typedef typename accessor_type::index_type index_type;
+      typedef typename accessor_type::index_value_type index_value_type;
+
+      const_ref() {}
+
+      const_ref(const ElementType* begin, accessor_type const& accessor)
+      : begin_(begin), accessor_(accessor)
+      {
+        init();
+      }
+
+      const_ref(const ElementType* begin, index_value_type const& n0)
+      : begin_(begin), accessor_(n0)
+      {
+        init();
+      }
+
+      const_ref(const ElementType* begin, index_value_type const& n0,
+                                          index_value_type const& n1)
+      : begin_(begin), accessor_(n0, n1)
+      {
+        init();
+      }
+
+      const_ref(const ElementType* begin, index_value_type const& n0,
+                                          index_value_type const& n1,
+                                          index_value_type const& n2)
+      : begin_(begin), accessor_(n0, n1, n2)
+      {
+        init();
+      }
+
+      accessor_type const& accessor() const { return accessor_; }
+      size_type size() const { return size_; }
+
+      const ElementType* begin() const { return begin_; }
+      const ElementType* end() const { return end_; }
+
+      ElementType const&
+      operator[](size_type i) const { return begin_[i]; }
+
+      const_ref<ElementType>
+      as_1d() const
+      {
+        return const_ref<ElementType>(begin_, size_);
+      }
+
+    protected:
+      void
+      init()
+      {
+        size_ = accessor_.size_1d();
+        end_ = begin_ + size_;
+      }
+
+      const ElementType* begin_;
+      accessor_type accessor_;
+      size_type size_;
+      const ElementType* end_;
+  };
+}
+
+template <typename ElementType,
+          typename AccessorType = trivial_accessor>
+class ref : public N0::const_ref<ElementType, AccessorType>
+{
+  public:
+    typedef ElementType value_type;
+    typedef size_t size_type;
+
+    typedef N0::const_ref<ElementType, AccessorType> base_class;
+    typedef AccessorType accessor_type;
+    typedef typename accessor_type::index_type index_type;
+
+    ref() {}
+
+    ElementType*
+    begin() const { return const_cast<ElementType*>(this->begin_); }
+
+    ElementType*
+    end() const { return const_cast<ElementType*>(this->end_); }
+
+    ElementType&
+    operator[](size_type i) const { return begin()[i]; }
+};
+
+namespace N1 {
+  template <typename ElementType, size_t N>
+  class tiny_plain
+  {
+    public:
+      typedef ElementType value_type;
+      typedef size_t size_type;
+
+      static const size_t fixed_size=N;
+
+      ElementType elems[N];
+
+      tiny_plain() {}
+
+      static size_type size() { return N; }
+
+      ElementType* begin() { return elems; }
+      const ElementType* begin() const { return elems; }
+      ElementType* end() { return elems+N; }
+      const ElementType* end() const { return elems+N; }
+      ElementType& operator[](size_type i) { return elems[i]; }
+      ElementType const& operator[](size_type i) const { return elems[i]; }
+  };
+
+  template <typename ElementType, size_t N>
+  class tiny : public tiny_plain<ElementType, N>
+  {
+    public:
+      typedef ElementType value_type;
+      typedef size_t size_type;
+
+      typedef tiny_plain<ElementType, N> base_class;
+
+      tiny() {}
+  };
+}
+
+template <typename NumType>
+class mat3 : public N1::tiny_plain<NumType, 9>
+{
+  public:
+    typedef typename N1::tiny_plain<NumType, 9> base_type;
+
+    mat3() {}
+    mat3(NumType const& e00, NumType const& e01, NumType const& e02,
+         NumType const& e10, NumType const& e11, NumType const& e12,
+         NumType const& e20, NumType const& e21, NumType const& e22)
+      : base_type(e00, e01, e02, e10, e11, e12, e20, e21, e22)
+    {}
+    mat3(base_type const& a)
+      : base_type(a)
+    {}
+
+    NumType const&
+    operator()(size_t r, size_t c) const
+    {
+      return this->elems[r * 3 + c];
+    }
+    NumType&
+    operator()(size_t r, size_t c)
+    {
+      return this->elems[r * 3 + c];
+    }
+
+    NumType
+    trace() const
+    {
+      mat3 const& m = *this;
+      return m[0] + m[4] + m[8];
+    }
+
+    NumType
+    determinant() const
+    {
+      mat3 const& m = *this;
+      return   m[0] * (m[4] * m[8] - m[5] * m[7])
+             - m[1] * (m[3] * m[8] - m[5] * m[6])
+             + m[2] * (m[3] * m[7] - m[4] * m[6]);
+    }
+};
+
+template <typename NumType>
+inline
+mat3<NumType>
+operator-(mat3<NumType> const& v)
+{
+  mat3<NumType> result;
+  for(size_t i=0;i<9;i++) {
+    result[i] = -v[i];
+  }
+  return result;
+}
+
+class mat_grid : public N1::tiny<size_t, 2>
+{
+  public:
+    typedef N1::tiny<size_t, 2> index_type;
+    typedef index_type::value_type index_value_type;
+
+    mat_grid() { this->elems[0]=0; this->elems[1]=0; }
+
+    mat_grid(index_type const& n) : index_type(n) {}
+
+    mat_grid(index_value_type const& n0, index_value_type const& n1)
+    { this->elems[0]=n0; this->elems[1]=n1; }
+
+    size_t size_1d() const { return elems[0] * elems[1]; }
+
+    size_t
+    operator()(index_value_type const& r, index_value_type const& c) const
+    {
+      return r * elems[1] + c;
+    }
+};
+
+template <typename NumType, typename AccessorType = mat_grid>
+class mat_const_ref : public N0::const_ref<NumType, AccessorType>
+{
+  public:
+    typedef AccessorType accessor_type;
+    typedef typename N0::const_ref<NumType, AccessorType> base_type;
+    typedef typename accessor_type::index_value_type index_value_type;
+
+    mat_const_ref() {}
+
+    mat_const_ref(const NumType* begin, accessor_type const& grid)
+    : base_type(begin, grid)
+    {}
+
+    mat_const_ref(const NumType* begin, index_value_type const& n_rows,
+                                        index_value_type const& n_columns)
+    : base_type(begin, accessor_type(n_rows, n_columns))
+    {}
+
+    accessor_type
+    grid() const { return this->accessor(); }
+
+    index_value_type const&
+    n_rows() const { return this->accessor()[0]; }
+
+    index_value_type const&
+    n_columns() const { return this->accessor()[1]; }
+
+    NumType const&
+    operator()(index_value_type const& r, index_value_type const& c) const
+    {
+      return this->begin()[this->accessor()(r, c)];
+    }
+};
+
+template <typename NumType, typename AccessorType = mat_grid>
+class mat_ref : public mat_const_ref<NumType, AccessorType>
+{
+  public:
+    typedef AccessorType accessor_type;
+    typedef mat_const_ref<NumType, AccessorType> base_type;
+    typedef typename accessor_type::index_value_type index_value_type;
+
+    mat_ref() {}
+
+    mat_ref(NumType* begin, accessor_type const& grid)
+    : base_type(begin, grid)
+    {}
+
+    mat_ref(NumType* begin, index_value_type n_rows,
+                            index_value_type n_columns)
+    : base_type(begin, accessor_type(n_rows, n_columns))
+    {}
+
+    NumType*
+    begin() const { return const_cast<NumType*>(this->begin_); }
+
+    NumType*
+    end() const { return const_cast<NumType*>(this->end_); }
+
+    NumType&
+    operator[](index_value_type const& i) const { return begin()[i]; }
+
+    NumType&
+    operator()(index_value_type const& r, index_value_type const& c) const
+    {
+      return this->begin()[this->accessor()(r, c)];
+    }
+};
+
+  template <typename AnyType>
+  inline void
+  swap(AnyType* a, AnyType* b, size_t n)
+  {
+    for(size_t i=0;i<n;i++) {
+      AnyType t = a[i]; a[i] = b[i]; b[i] = t;
+    }
+  }
+
+template <typename IntType>
+size_t
+form_t(mat_ref<IntType>& m,
+       mat_ref<IntType> const& t)
+{
+  typedef size_t size_t;
+  size_t mr = m.n_rows();
+  size_t mc = m.n_columns();
+  size_t tc = t.n_columns();
+  if (tc) {
+  }
+  size_t i, j;
+  for (i = j = 0; i < mr && j < mc;) {
+    size_t k = i; while (k < mr && m(k,j) == 0) k++;
+    if (k == mr)
+      j++;
+    else {
+      if (i != k) {
+                swap(&m(i,0), &m(k,0), mc);
+        if (tc) swap(&t(i,0), &t(k,0), tc);
+      }
+      for (k++; k < mr; k++) {
+        IntType a = absolute(m(k, j));
+        if (a != 0 && a < absolute(m(i,j))) {
+                  swap(&m(i,0), &m(k,0), mc);
+          if (tc) swap(&t(i,0), &t(k,0), tc);
+        }
+      }
+      if (m(i,j) < 0) {
+                for(size_t ic=0;ic<mc;ic++) m(i,ic) *= -1;
+        if (tc) for(size_t ic=0;ic<tc;ic++) t(i,ic) *= -1;
+      }
+      bool cleared = true;
+      for (k = i+1; k < mr; k++) {
+        IntType a = m(k,j) / m(i,j);
+        if (a != 0) {
+                  for(size_t ic=0;ic<mc;ic++) m(k,ic) -= a * m(i,ic);
+          if (tc) for(size_t ic=0;ic<tc;ic++) t(k,ic) -= a * t(i,ic);
+        }
+        if (m(k,j) != 0) cleared = false;
+      }
+      if (cleared) { i++; j++; }
+    }
+  }
+  m = mat_ref<IntType>(m.begin(), i, mc);
+  return i;
+}
+
+template <typename IntType>
+size_t
+form(mat_ref<IntType>& m)
+{
+  mat_ref<IntType> t(0,0,0);
+  return form_t(m, t);
+}
+
+typedef mat3<int> sg_mat3;
+
+class rot_mx
+{
+  public:
+    explicit
+    rot_mx(sg_mat3 const& m, int denominator=1)
+    : num_(m), den_(denominator)
+    {}
+
+    sg_mat3 const&
+    num() const { return num_; }
+    sg_mat3&
+    num()       { return num_; }
+
+    int const&
+    operator[](size_t i) const { return num_[i]; }
+    int&
+    operator[](size_t i)       { return num_[i]; }
+
+    int
+    const& operator()(int r, int c) const { return num_(r, c); }
+    int&
+    operator()(int r, int c)       { return num_(r, c); }
+
+    int const&
+    den() const { return den_; }
+    int&
+    den()       { return den_; }
+
+    rot_mx
+    minus_unit_mx() const
+    {
+      rot_mx result(*this);
+      for (size_t i=0;i<9;i+=4) result[i] -= den_;
+      return result;
+    }
+
+    rot_mx
+    operator-() const { return rot_mx(-num_, den_); }
+
+    int
+    type() const;
+
+    int
+    order(int type=0) const;
+
+  private:
+    sg_mat3 num_;
+    int den_;
+};
+
+class rot_mx_info
+{
+  public:
+    rot_mx_info(rot_mx const& r);
+
+    int type() const { return type_; }
+
+  private:
+    int type_;
+};
+
+int rot_mx::type() const
+{
+  int det = num_.determinant();
+  if (det == -1 || det == 1) {
+    switch (num_.trace()) {
+      case -3:                return -1;
+      case -2:                return -6;
+      case -1: if (det == -1) return -4;
+               else           return  2;
+      case  0: if (det == -1) return -3;
+               else           return  3;
+      case  1: if (det == -1) return -2;
+               else           return  4;
+      case  2:                return  6;
+      case  3:                return  1;
+    }
+  }
+  return 0;
+}
+
+int rot_mx::order(int type) const
+{
+  if (type == 0) type = rot_mx::type();
+  if (type > 0) return  type;
+  if (type % 2) return -type * 2;
+                return -type;
+}
+
+rot_mx_info::rot_mx_info(rot_mx const& r)
+: type_(r.type())
+{
+  if (type_ == 0) {
+    return;
+  }
+  rot_mx proper_r = r;
+  int proper_order = type_;
+  // THE PROBLEM IS AROUND HERE
+  if (proper_order < 0) {
+    proper_order *= -1;
+    proper_r = -proper_r; // THIS FAILS ...
+  }
+  if (proper_order > 1) {
+    rot_mx rmi = proper_r.minus_unit_mx(); // ... THEREFORE WRONG HERE
+    mat_ref<int> re_mx(rmi.num().begin(), 3, 3);
+    if (form(re_mx) != 2) {
+      type_ = 0;
+    }
+  }
+}
+
+int main()
+{
+  N1::tiny<int, 9> e;
+  e[0] = 1; e[1] =  0; e[2] = 0;
+  e[3] = 0; e[4] = -1; e[5] = 0;
+  e[6] = 0; e[7] =  0; e[8] = 1;
+  rot_mx r(e);
+  rot_mx_info ri(r);
+  if (ri.type() != -2)
+    __builtin_abort ();
+  return 0;
+}