This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Add "Implicit sets" to GCSE's cprop (take 2)


I believe I've found the problem.  Before gcse we had

(insn 4062 9281 4065 383 0x20000053188 (set (reg/v:DI 82 [ swapped ])
        (eq:DI (reg/v:DI 82 [ swapped ])
            (const_int 0 [0x0]))) 149 {*setcc_internal} (nil)
    (nil))
(jump_insn 4065 4062 9282 383 0x20000053188 (set (pc)
        (if_then_else (eq (reg/v:DI 82 [ swapped ])
                (const_int 0 [0x0]))
            (label_ref 4223)
            (pc))) 174 {*bcc_normal} (nil)
    (expr_list:REG_BR_PRED (concat (const_int 20 [0x14])
            (const_int 7000 [0x1b58]))
        (nil)))

Note that reg 82 is modified and then tested.  Our use of 
get_condition looked back through the first instruction to
return (ne:DI (reg:DI 82) (const_int 0)).  So we wound up
inferring the wrong condition.

My find_reloads test case is fixed by the following patch.
I'm going to start a full bootstrap shortly.

This also brings up an interesting point: swapped is boolean
(I don't know whether it's declared bool or not, but that's
not relevant at the moment).  Ideally, we'd infer equality
with one on the other side of the branch.  Dunno how often
that would make a difference.

In this case I think we were able to make substitutions only
because we had

	swapped = 0;
     label:
	A
	goal_alternative_swapped = swapped;
	B
	swapped = !swapped;
	if (swapped)
	  {
	    C
	    goto label;
	  }

with the inferrence at C of swapped == 0, we've got two identical
sets that together dominate the copy to goal_alternative_swapped.


r~



Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.232
diff -c -p -d -r1.232 gcse.c
*** gcse.c	27 Jan 2003 11:30:35 -0000	1.232
--- gcse.c	7 Feb 2003 01:37:46 -0000
*************** struct ls_expr
*** 479,484 ****
--- 479,487 ----
    rtx reaching_reg;		/* Register to use when re-writing.  */
  };
  
+ /* Array of implicit set patterns indexed by basic block index.  */
+ static rtx *implicit_sets;
+ 
  /* Head of the list of load/store memory refs.  */
  static struct ls_expr * pre_ldst_mems = NULL;
  
*************** static int load_killed_in_block_p    PAR
*** 614,619 ****
--- 617,624 ----
  static void canon_list_insert        PARAMS ((rtx, rtx, void *));
  static int cprop_insn		PARAMS ((rtx, int));
  static int cprop		PARAMS ((int));
+ static rtx fis_get_condition	PARAMS ((rtx));
+ static void find_implicit_sets	PARAMS ((void));
  static int one_cprop_pass	PARAMS ((int, int, int));
  static bool constprop_register	PARAMS ((rtx, rtx, rtx, int));
  static struct expr *find_bypass_set PARAMS ((int, int));
*************** record_last_set_info (dest, setter, data
*** 2470,2476 ****
  
     Currently src must be a pseudo-reg or a const_int.
  
-    F is the first insn.
     TABLE is the table computed.  */
  
  static void
--- 2475,2480 ----
*************** compute_hash_table_work (table)
*** 2532,2537 ****
--- 2536,2547 ----
  	  note_stores (PATTERN (insn), record_last_set_info, insn);
  	}
  
+       /* Insert implicit sets in the hash table.  */
+       if (table->set_p
+ 	  && implicit_sets[current_bb->index] != NULL_RTX)
+ 	hash_scan_set (implicit_sets[current_bb->index],
+ 		       current_bb->head, table);
+ 
        /* The next pass builds the hash table.  */
  
        for (insn = current_bb->head, in_libcall_block = 0;
*************** cprop (alter_jumps)
*** 4478,4483 ****
--- 4488,4604 ----
    return changed;
  }
  
+ /* Similar to get_condition, only the resulting condition must be
+    valid at JUMP, instead of at EARLIEST.
+ 
+    This differs from noce_get_condition in ifcvt.c in that we prefer not to
+    settle for the condition variable in the jump instruction being integral.
+    We prefer to be able to record the value of a user variable, rather than
+    the value of a temporary used in a condition.  This could be solved by
+    recording the value of *every* register scaned by canonicalize_condition,
+    but this would require some code reorganization.  */
+ 
+ static rtx
+ fis_get_condition (jump)
+      rtx jump;
+ {
+   rtx cond, set, tmp, insn, earliest;
+   bool reverse;
+ 
+   if (! any_condjump_p (jump))
+     return NULL_RTX;
+ 
+   set = pc_set (jump);
+   cond = XEXP (SET_SRC (set), 0);
+ 
+   /* If this branches to JUMP_LABEL when the condition is false,
+      reverse the condition.  */
+   reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
+ 	     && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
+ 
+   /* Use canonicalize_condition to do the dirty work of manipulating
+      MODE_CC values and COMPARE rtx codes.  */
+   tmp = canonicalize_condition (jump, cond, reverse, &earliest, NULL_RTX);
+   if (!tmp)
+     return NULL_RTX;
+ 
+   /* Verify that the given condition is valid at JUMP by virtue of not
+      having been modified since EARLIEST.  */
+   for (insn = earliest; insn != jump; insn = NEXT_INSN (insn))
+     if (INSN_P (insn) && modified_in_p (tmp, insn))
+       break;
+   if (insn == jump)
+     return tmp;
+ 
+   /* The condition was modified.  See if we can get a partial result
+      that doesn't follow all the reversals.  Perhaps combine can fold
+      them together later.  */
+   tmp = XEXP (tmp, 0);
+   if (!REG_P (tmp) || GET_MODE_CLASS (GET_MODE (tmp)) != MODE_INT)
+     return NULL_RTX;
+   tmp = canonicalize_condition (jump, cond, reverse, &earliest, tmp);
+   if (!tmp)
+     return NULL_RTX;
+ 
+   /* For sanity's sake, re-validate the new result.  */
+   for (insn = earliest; insn != jump; insn = NEXT_INSN (insn))
+     if (INSN_P (insn) && modified_in_p (tmp, insn))
+       return NULL_RTX;
+ 
+   return tmp;
+ }
+ 
+ /* Find the implicit sets of a function.  An "implicit set" is a constraint
+    on the value of a variable, implied by a conditional jump.  For example,
+    following "if (x == 2)", the then branch may be optimized as though the
+    conditional performed an "explicit set", in this example, "x = 2".  This
+    function records the set patterns that are implicit at the start of each
+    basic block.  */
+ 
+ static void
+ find_implicit_sets ()
+ {
+   basic_block bb, dest;
+   unsigned int count;
+   rtx cond, new;
+ 
+   count = 0;
+   FOR_EACH_BB (bb)
+     /* Check for more than one sucessor.  */
+     if (bb->succ && bb->succ->succ_next)
+       {
+ 	cond = fis_get_condition (bb->end);
+ 
+ 	if (cond
+ 	    && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE)
+ 	    && GET_CODE (XEXP (cond, 0)) == REG
+ 	    && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER
+ 	    && CONSTANT_P (XEXP (cond, 1)))
+ 	  {
+ 	    dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
+ 					 : FALLTHRU_EDGE (bb)->dest;
+ 
+ 	    if (dest && ! dest->pred->pred_next
+ 		&& dest != EXIT_BLOCK_PTR)
+ 	      {
+ 		new = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
+ 					     XEXP (cond, 1));
+ 		implicit_sets[dest->index] = new;
+ 		if (gcse_file)
+ 		  {
+ 		    fprintf(gcse_file, "Implicit set of reg %d in ",
+ 			    REGNO (XEXP (cond, 0)));
+ 		    fprintf(gcse_file, "basic block %d\n", dest->index);
+ 		  }
+ 		count++;
+ 	      }
+ 	  }
+       }
+ 
+   if (gcse_file)
+     fprintf (gcse_file, "Found %d implicit sets\n", count);
+ }
+ 
  /* Perform one copy/constant propagation pass.
     PASS is the pass count.  If CPROP_JUMPS is true, perform constant
     propagation into conditional jumps.  If BYPASS_JUMPS is true,
*************** one_cprop_pass (pass, cprop_jumps, bypas
*** 4496,4503 ****
--- 4617,4633 ----
  
    local_cprop_pass (cprop_jumps);
  
+   /* Determine implicit sets.  */
+   implicit_sets = (rtx *) xcalloc (last_basic_block, sizeof (rtx));
+   find_implicit_sets ();
+ 
    alloc_hash_table (max_cuid, &set_hash_table, 1);
    compute_hash_table (&set_hash_table);
+ 
+   /* Free implicit_sets before peak usage.  */
+   free (implicit_sets);
+   implicit_sets = NULL;
+ 
    if (gcse_file)
      dump_hash_table (gcse_file, "SET", &set_hash_table);
    if (set_hash_table.n_elems > 0)


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]