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]

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


On Tue, 28 Jan 2003, Richard Henderson wrote:
> You should be scanning from the end, not the beginning.  Particularly
> since you're interested in the JUMP_INSN, which is guaranteed to be at
> the end.  ;-)

Good point.

> Have you considered using e.g. get_condition?

And another good suggestion.

> You may find that it works best to expand something akin to
> canonicalize_condition locally and record _all_ of the steps.

It turns out that this isn't necessary.  get_condition works great.


The following patch implements both of these improvements.  The function
find_implicit_sets now no longer scans the instruction stream, but uses
get_condition on the last instruction of a basic block.  This should
both improve performance and allow us to share future improvements in
get_condition.

The following patch has been tested with a full bootstrap, all languages
except Ada and treelang, on i686-pc-linux-gnu, and survived a complete
"make -k check" with no new regressions.  I've also confirmed that it
still optimizes both the examples presented in the original posting.


Ok for mainline?


2003-02-01  Roger Sayle  <roger@eyesopen.com>

	* gcse.c (implicit_sets): New global array of implicit set patterns
	indexed by basic block index.
	(find_implicit_sets): New routine to determine the implicit sets of
	a function, i.e. "if (x == 2)".
	(compute_hash_table_work): Include implicit sets in hash table of
	available sets for GCSE's constant/copy propagation passes.
	(one_cprop_pass): Allocate implicit_sets and call find_implicit_sets
	before building set_hash_table for cprop.  Free implicit_sets after
	the hash table is built.


Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.232
diff -c -3 -p -r1.232 gcse.c
*** gcse.c	27 Jan 2003 11:30:35 -0000	1.232
--- gcse.c	1 Feb 2003 05:16:27 -0000
*************** struct null_pointer_info
*** 551,556 ****
--- 551,559 ----
    sbitmap *nonnull_local;
    sbitmap *nonnull_killed;
  };
+
+ /* Array of implicit set patterns indexed by basic block index.  */
+ static rtx *implicit_sets;

  static void compute_can_copy	PARAMS ((void));
  static char *gmalloc		PARAMS ((unsigned int));
*************** static int load_killed_in_block_p    PAR
*** 614,619 ****
--- 617,623 ----
  static void canon_list_insert        PARAMS ((rtx, rtx, void *));
  static int cprop_insn		PARAMS ((rtx, int));
  static int cprop		PARAMS ((int));
+ 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
--- 2474,2479 ----
*************** compute_hash_table_work (table)
*** 2532,2537 ****
--- 2535,2546 ----
  	  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 ****
--- 4487,4543 ----
    return changed;
  }

+ /* 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 = get_condition (bb->end, (rtx*)0);
+
+ 	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 ****
--- 4556,4572 ----

    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)

Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833


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