Re: Constant folding and Constant propagation

Re: Constant folding and Constant propagation

[Rahul Kharche]

I am looking at a related problem in GCSE, GCC 4.3 whereby constants
are propagated to their use irrespective of the final instruction cost
of generating them (machine cycles or instruction count).

Global constant propagation effectively voids common expressions that
form large constants, identified by global CSE. This is especially
true of SYMBOl_REF constants like section-anchors generated while
indexing global arrays.

For the GCC port I work on, I have fixed this by weighing the rtx_cost
of propagating a register copy Vs propagating the constant into an insn.
I have an initial patch for this problem.


Rahul Vijay Kharche

Fwd: Constant folding and Constant propagation

[Jean Christophe Beyler]

Dear all,

I was working on the machine description so I was postponing a bit
this problem but now I have a bit more time on my hands to handle it.
I'm starting to look at the various links and code you've provided me
and will keep you posted if I make any headway or not ;-).

> For the GCC port I work on, I have fixed this by weighing the rtx_cost
> of propagating a register copy Vs propagating the constant into an insn.
> I have an initial patch for this problem.

Do you have a link to that patch? So that I can see if it applies for me ?

Thanks,
Jc


On Tue, Feb 10, 2009 at 2:25 PM, Rahul Kharche <rahul@icerasemi.com> wrote:
> I am looking at a related problem in GCSE, GCC 4.3 whereby constants
> are propagated to their use irrespective of the final instruction cost
> of generating them (machine cycles or instruction count).
>
> Global constant propagation effectively voids common expressions that
> form large constants, identified by global CSE. This is especially
> true of SYMBOl_REF constants like section-anchors generated while
> indexing global arrays.
>
> For the GCC port I work on, I have fixed this by weighing the rtx_cost
> of propagating a register copy Vs propagating the constant into an insn.
> I have an initial patch for this problem.
>
>
> Rahul Vijay Kharche
>

RE: Constant folding and Constant propagation

[Rahul Kharche]

Hi Jean,

> Do you have a link to that patch? So that I can see if it applies for
me ?

See patch below. I put in some comments to try and explain what I have
attempted to do.

The hash SET generation, to track potential candidates in replacing a
register USE, needed some tweaking. This function was not tracking
register copies if the associated INSN had a NOTE attached that
associated the register with a constant. Also, only the last register
or constant in an assignment chain was being added to the hash SET.
It may be profitable to have a closer register copy in the assignment
chain as a potential replacement.

Before the actual replacing operation, the cost of temporary replacement
is determined using rtx_cost. A cost cannot be reliably formed if we
come
across jump INSNs because they may alter jumps or successors. The
default
replacement is used in this case.

Rahul


Index: gcse.c
===================================================================
--- gcse.c	(revision 141156)
+++ gcse.c	(working copy)
@@ -520,7 +520,7 @@
 static void record_set_info (rtx, const_rtx, void *);
 static void compute_sets (void);
 static void hash_scan_insn (rtx, struct hash_table *, int);
-static void hash_scan_set (rtx, rtx, struct hash_table *);
+static void hash_scan_set (rtx, rtx, struct hash_table *, bool);
 static void hash_scan_clobber (rtx, rtx, struct hash_table *);
 static void hash_scan_call (rtx, rtx, struct hash_table *);
 static int want_to_gcse_p (rtx);
@@ -560,7 +560,7 @@
 static void compute_cprop_data (void);
 static void find_used_regs (rtx *, void *);
 static int try_replace_reg (rtx, rtx, rtx);
-static struct expr *find_avail_set (int, rtx);
+static struct expr *find_avail_set (int, rtx, bool);
 static int cprop_jump (basic_block, rtx, rtx, rtx, rtx);
 static void mems_conflict_for_gcse_p (rtx, const_rtx, void *);
 static int load_killed_in_block_p (const_basic_block, int, const_rtx,
int);
@@ -1671,11 +1671,11 @@
    expression one).  */
 
 static void
-hash_scan_set (rtx pat, rtx insn, struct hash_table *table)
+hash_scan_set (rtx pat, rtx insn, struct hash_table *table, bool
use_note)
 {
   rtx src = SET_SRC (pat);
   rtx dest = SET_DEST (pat);
-  rtx note;
+  rtx note = NULL_RTX;
 
   if (GET_CODE (src) == CALL)
     hash_scan_call (src, insn, table);
@@ -1685,16 +1685,21 @@
       unsigned int regno = REGNO (dest);
       rtx tmp;
 
-      /* See if a REG_NOTE shows this equivalent to a simpler
expression.
-	 This allows us to do a single GCSE pass and still eliminate
-	 redundant constants, addresses or other expressions that are
-	 constructed with multiple instructions.  */
-      note = find_reg_equal_equiv_note (insn);
-      if (note != 0
-	  && (table->set_p
-	      ? gcse_constant_p (XEXP (note, 0))
-	      : want_to_gcse_p (XEXP (note, 0))))
-	src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
+      /* Do not substitute insn SET_SRC for note if caller uses
+         uses use_note = false. */
+      if (use_note)
+        {
+	  /* See if a REG_NOTE shows this equivalent to a simpler
expression.
+	     This allows us to do a single GCSE pass and still eliminate
+	     redundant constants, addresses or other expressions that
are
+	     constructed with multiple instructions.  */
+	  note = find_reg_equal_equiv_note (insn);
+	  if (note != 0
+	      && (table->set_p
+		  ? gcse_constant_p (XEXP (note, 0))
+		  : want_to_gcse_p (XEXP (note, 0))))
+	    src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest,
src);
+	}
 
       /* Only record sets of pseudo-regs in the hash table.  */
       if (! table->set_p
@@ -1835,14 +1840,30 @@
      what's been modified.  */
 
   if (GET_CODE (pat) == SET)
-    hash_scan_set (pat, insn, table);
+    {
+      /* If we're hashing SETs for constant/copy propagation
+         also hash a SET ignoring any insn notes. */
+      if (table->set_p)
+        {
+          hash_scan_set (pat, insn, table, false);
+	}
+      hash_scan_set (pat, insn, table, true);
+    }
   else if (GET_CODE (pat) == PARALLEL)
     for (i = 0; i < XVECLEN (pat, 0); i++)
       {
 	rtx x = XVECEXP (pat, 0, i);
 
 	if (GET_CODE (x) == SET)
-	  hash_scan_set (x, insn, table);
+	  {
+	    /* If we're hashing SETs for constant/copy propagation
+	       also hash a SET ignoring any insn notes. */
+	    if (table->set_p)
+	      {
+	        hash_scan_set (x, insn, table, false);
+	      }
+	    hash_scan_set (x, insn, table, true);
+	  }
 	else if (GET_CODE (x) == CLOBBER)
 	  hash_scan_clobber (x, insn, table);
 	else if (GET_CODE (x) == CALL)
@@ -2071,7 +2092,7 @@
       if (table->set_p
 	  && implicit_sets[current_bb->index] != NULL_RTX)
 	hash_scan_set (implicit_sets[current_bb->index],
-		       BB_HEAD (current_bb), table);
+		       BB_HEAD (current_bb), table, true);
 
       /* The next pass builds the hash table.  */
       in_libcall_block = 0;
@@ -2701,7 +2722,7 @@
    NULL no such set is found.  */
 
 static struct expr *
-find_avail_set (int regno, rtx insn)
+find_avail_set (int regno, rtx insn, bool follow_chain)
 {
   /* SET1 contains the last set found that can be returned to the
caller for
      use in a substitution.  */
@@ -2716,7 +2737,7 @@
 
      This can not happen since the set of (reg Y) would have killed the
      set of (reg X) making it unavailable at the start of this block.
*/
-  while (1)
+  do
     {
       rtx src;
       struct expr *set = lookup_set (regno, &set_hash_table);
@@ -2758,6 +2779,7 @@
 	 and see if we have an available copy into SRC.  */
       regno = REGNO (src);
     }
+  while (follow_chain);
 
   /* SET1 holds the last set that was available and anticipatable at
      INSN.  */
@@ -2944,7 +2966,12 @@
       unsigned int regno = REGNO (reg_used->reg_rtx);
       rtx pat, src;
       struct expr *set;
+      int set_cost = INT_MAX;
 
+      rtx src_first;
+      struct expr *set_first;
+      int set_first_cost = INT_MAX;
+
       /* Ignore registers created by GCSE.
 	 We do this because ...  */
       if (regno >= max_gcse_regno)
@@ -2957,10 +2984,72 @@
 
       /* Find an assignment that sets reg_used and is available
 	 at the start of the block.  */
-      set = find_avail_set (regno, insn);
+      set = find_avail_set (regno, insn, true);
       if (! set)
 	continue;
+      src = SET_SRC (set->expr);
+      
+      /* If possible, determine the cost of substituting the
+         last definition in the target insn */
+      rtx insn_set  = make_insn_raw (copy_insn (PATTERN (insn)));
+      if (NONJUMP_INSN_P (insn_set)
+	  && try_replace_reg (reg_used->reg_rtx, src, insn_set))
+	{
+	  set_cost = rtx_cost (PATTERN (insn_set),
+			       GET_CODE (PATTERN (insn_set)));
+	  
+	  /* Bias heavily for last definition if we managed to
+	     delete target insn with this substitution */
+	  if (INSN_DELETED_P (insn_set))
+	    set_cost = 0;
+	}
+	/* Might be a alter_jumps and jump insn case which we neglect
+	   in costing this option */
 
+      /* Find the first definition that sets reg_used 
+         i.e. not following the assignment chain */
+      set_first = find_avail_set (regno, insn, false);
+      
+      /* If we have a closest definition available, cost the
replacement of
+         first definition (set_first) Vs last definition (in the
assignment chain) */
+      if (set_first
+	  /* If we cannot deduce the cost of propagating constants into
+	     jump insns, go with constant propagation */
+	  && (!alter_jumps
+	      || !((any_condjump_p (insn) && onlyjump_p (insn))
+		   || (NEXT_INSN (insn) && any_condjump_p (NEXT_INSN
(insn))
+		       && onlyjump_p (NEXT_INSN (insn))))))
+        {
+	  src_first = SET_SRC (set_first->expr);
+	  
+	  if (REG_P (src_first)
+	      && REGNO (src_first) >= FIRST_PSEUDO_REGISTER
+	      && REGNO (src_first) != regno)
+	    {
+	      rtx insn_set_first  = make_insn_raw (copy_insn (PATTERN
(insn)));
+	      if (try_replace_reg (reg_used->reg_rtx, src_first,
insn_set_first))
+		{
+		  set_first_cost = rtx_cost (PATTERN (insn_set_first),
+				             GET_CODE (PATTERN
(insn_set_first)));
+		}
+	    }
+	    
+	  if (set_first_cost < set_cost)
+	    {
+	      set = set_first;
+	      set_cost = set_first_cost;
+
+	      if (dump_file)
+	        {
+		  fprintf (dump_file, "cprop_insn prefer  ");
+		  print_inline_rtx (dump_file, SET_SRC
(set_first->expr), 2);
+		  fprintf (dump_file, "  cost %d over  ",
set_first_cost);
+		  print_inline_rtx (dump_file, SET_SRC (set->expr), 2);
+		  fprintf (dump_file, "  cost %d\n", set_cost);
+	        }
+	    }
+	}
+      
       pat = set->expr;
       /* ??? We might be able to handle PARALLELs.  Later.  */
       gcc_assert (GET_CODE (pat) == SET);

RE: Constant folding and Constant propagation

[Rahul Kharche]

> - If I patch in this code, actually I get the same results I did
> before where the constants are propagated. It seems that in 4.3.2,
> every part of the compiler is trying to do that.

There are at least two forward propagation passes, one before and
another after GCSE. I haven't tried to tackle those passes, but I
believe they already have a cost model in place.

This patch will prevent partial sums involving registers and
constants from being combined during GCSE.

> - Just for testing I turned off the GCSE pass and it still
> propagated and folded the constants...

GCSE won't help with your trimmed down example

int main(void)
{
    long a = 0xcafecafe;

    printf("Final: %lx %lx %lx\n", a, a+5, a+15);
    return EXIT_SUCCESS;
}

I believe Paolo's canon_reg solution together with tweaking
rtx_cost of constants with outer code PLUS might help. Any
luck with that pass?

Re: Constant folding and Constant propagation

[Adam Nemet]

"Rahul Kharche" <rahul@IceraSemi.com> writes:
> GCSE won't help with your trimmed down example
>
> int main(void)
> {
>     long a = 0xcafecafe;
>
>     printf("Final: %lx %lx %lx\n", a, a+5, a+15);
>     return EXIT_SUCCESS;
> }
>
> I believe Paolo's canon_reg solution together with tweaking
> rtx_cost of constants with outer code PLUS might help. Any
> luck with that pass?

As I understand Paolo's change is to move some of the functionality from cse.c
to a new LCM pass.  However cse.c does not handle the above yet.

I am actually looking at something similar for PR33699 for MIPS.  My plan is
to experiment extending cse.c with putting "anchor" constants to the available
expressions along with the original constant and then querying those later for
constant expressions.

Adam

Re: Constant folding and Constant propagation

[Adam Nemet]

Adam Nemet <anemet@caviumnetworks.com> writes:
> I am actually looking at something similar for PR33699 for MIPS.  My plan is
> to experiment extending cse.c with putting "anchor" constants to the available
> expressions along with the original constant and then querying those later for
> constant expressions.

See http://gcc.gnu.org/ml/gcc-patches/2009-03/msg00161.html.

Adam

Re: Constant folding and Constant propagation

[Jean Christophe Beyler]

I set up your patch and I get an internal error on this test program:

extern void foo(int, int);
extern int bar(void);
int startup;

void foobar()
{
  int i;
  while(1)
  {
    if (bar()) {
        foo(0,0);
    }
  }
}

Here's the error:
/home/beyler/cyclops64/src/tnt/kernel/process_manager/testnode.c: In
function 'foobar':
/home/beyler/cyclops64/src/tnt/kernel/process_manager/testnode.c:15:
internal compiler error: in insert_regs, at cse.c:1156
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.


I think it's got something to do with my machine description but this
only happens when the values of foo are both 0. I haven't found
another case where it fails. It seems when the compiler sees two
constants 0 for the register (r8 which is my first input register), it
fails on the second. Somewhere between both calls, it must remove the
quantity.

Any ideas ?
Jc

Re: Constant folding and Constant propagation

[Jean Christophe Beyler]

If I replace your lines:

    if ((GET_CODE (sets[i].src_elt->exp) == CONST_INT))
        insert_const_anchors (dest, sets[i].src_elt, GET_MODE (dest));

with:

    if ((GET_CODE (sets[i].src_elt->exp) == CONST_INT) && (INTVAL
(sets[i].src_elt->exp) != 0))
        insert_const_anchors (dest, sets[i].src_elt, GET_MODE (dest));

it does not fail anymore since I remove the 0 corner case I am seeing.
I fail to see why it is a problem however. Like I said previously, it
might be a problem with my target architecture but I fail to see why 0
is considered differently in the target files.

Jc

Re: Constant folding and Constant propagation

[Adam Nemet]

Jean Christophe Beyler writes:
> I set up your patch and I get an internal error on this test program:

You're right.  I haven't handled the case properly when the constant itself
was an anchor constant (e.g. 0).  Try this version.

Adam


	* cse.c (get_const_anchors): New function.
	(insert_const_anchors): New function.
	(cse_insn): Set src_related using anchor constants.  Insert
	constant anchors into the table of available expressions.

	* config/mips/mips.c (mips_rtx_costs): Make immediate-add even cheaper
	than loading a simple constant into a register.

Index: gcc/cse.c
===================================================================
--- gcc.orig/cse.c	2009-03-08 12:16:56.000000000 -0700
+++ gcc/cse.c	2009-03-16 23:07:40.000000000 -0700
@@ -3961,6 +3961,55 @@ record_jump_cond (enum rtx_code code, en
 
   merge_equiv_classes (op0_elt, op1_elt);
 }
+
+#define TARGET_CONST_ANCHOR 0x8000
+
+/* Compute the upper and lower anchors for CST as base, offset pairs.  Return
+   NULL_RTX if CST is equal to an anchor.  */
+
+static rtx
+get_const_anchors (rtx cst, rtx *upper_base, HOST_WIDE_INT *upper_offs,
+		   HOST_WIDE_INT *lower_offs)
+{
+  HOST_WIDE_INT n, upper, lower;
+
+  n = INTVAL (cst);
+  lower = n & ~(TARGET_CONST_ANCHOR - 1);
+  if (n == lower)
+    return NULL_RTX;
+  upper = (n + (TARGET_CONST_ANCHOR - 1)) & ~(TARGET_CONST_ANCHOR - 1);
+
+  *upper_base = GEN_INT (upper);
+  *upper_offs = n - upper;
+  *lower_offs = n - lower;
+  return GEN_INT (lower);
+}
+
+/* Create equivalences between the two anchors of a constant value and the
+   corresponding register-offset expressions.  Use the register REG, which is
+   equivalent to the constant value CLASSP->exp.  */
+
+static void
+insert_const_anchors (rtx reg, struct table_elt *classp,
+		      enum machine_mode mode)
+{
+  rtx lower_base, upper_base;
+  HOST_WIDE_INT lower_offs, upper_offs;
+  rtx lower_exp, upper_exp;
+  struct table_elt *celt;
+  rtx cst = classp->exp;
+
+  lower_base = get_const_anchors (cst, &upper_base, &upper_offs, &lower_offs);
+  if (!lower_base)
+    return;
+  lower_exp = plus_constant (reg, -lower_offs);
+  upper_exp = plus_constant (reg, -upper_offs);
+
+  celt = insert (lower_base, NULL, HASH (lower_base, mode), mode);
+  insert (lower_exp, celt, HASH (lower_exp, mode), mode);
+  celt = insert (upper_base, NULL, HASH (upper_base, mode), mode);
+  insert (upper_exp, celt, HASH (upper_exp, mode), mode);
+}
 \f
 /* CSE processing for one instruction.
    First simplify sources and addresses of all assignments
@@ -4595,6 +4644,67 @@ cse_insn (rtx insn)
 	}
 #endif /* LOAD_EXTEND_OP */
 
+      /* Try to express the constant using a register-offset expression using
+	 anchor constants.  */
+
+      if (!src_related && src_const && GET_CODE (src_const) == CONST_INT)
+	{
+	  rtx lower_base, upper_base;
+	  struct table_elt *lower_elt, *upper_elt, *elt;
+	  HOST_WIDE_INT lower_offs, upper_offs, offs;
+
+	  lower_base = get_const_anchors (src_const, &upper_base, &upper_offs,
+					  &lower_offs);
+	  if (lower_base)
+	    {
+	      lower_elt = lookup (lower_base, HASH (lower_base, mode), mode);
+	      upper_elt = lookup (upper_base, HASH (upper_base, mode), mode);
+
+	      /* Loop over LOWER_ELTs and UPPER_ELTs to find a reg-offset pair
+		 that we can use to express SRC_CONST.  */
+	      elt = NULL;
+	      if (lower_elt)
+		{
+		  elt = lower_elt->first_same_value;
+		  offs = lower_offs;
+		}
+	      else if (upper_elt)
+		{
+		  elt = upper_elt->first_same_value;
+		  upper_elt = NULL;
+		  offs = upper_offs;
+		}
+	      while (elt)
+		{
+		  if (REG_P (elt->exp)
+		      || (GET_CODE (elt->exp) == PLUS
+			  && REG_P (XEXP (elt->exp, 0))
+			  && GET_CODE (XEXP (elt->exp, 1)) == CONST_INT))
+		    {
+		      rtx x = plus_constant (elt->exp, offs);
+		      if (REG_P (x)
+			  || (GET_CODE (x) == PLUS
+			      && IN_RANGE (INTVAL (XEXP (x, 1)),
+					   -TARGET_CONST_ANCHOR,
+					   TARGET_CONST_ANCHOR - 1)))
+			{
+			  src_related = x;
+			  break;
+			}
+		    }
+
+		  if (!elt->next_same_value && upper_elt)
+		    {
+		      elt = upper_elt->first_same_value;
+		      upper_elt = NULL;
+		      offs = upper_offs;
+		    }
+		  else
+		    elt = elt->next_same_value;
+		}
+	    }
+	}
+
       if (src == src_folded)
 	src_folded = 0;
 
@@ -5433,6 +5543,11 @@ cse_insn (rtx insn)
 	elt = insert (dest, sets[i].src_elt,
 		      sets[i].dest_hash, GET_MODE (dest));
 
+	/* If this is a constant, insert the constant anchors with the
+	   equivalent register-offset expressions using DEST.  */
+	if (GET_CODE (sets[i].src_elt->exp) == CONST_INT)
+	  insert_const_anchors (dest, sets[i].src_elt, GET_MODE (dest));
+
 	elt->in_memory = (MEM_P (sets[i].inner_dest)
 			  && !MEM_READONLY_P (sets[i].inner_dest));
 
Index: gcc/config/mips/mips.c
===================================================================
--- gcc.orig/config/mips/mips.c	2009-03-08 10:13:18.000000000 -0700
+++ gcc/config/mips/mips.c	2009-03-15 11:37:48.000000000 -0700
@@ -3573,6 +3573,17 @@ mips_rtx_costs (rtx x, int code, int out
 	  return false;
 	}
 
+      /* CSE creates these for loading a constant into a register.  In that
+	 case the first operand is a register used somewhere else holding a
+	 value that can be used to derive the constant value.  Prefer them
+	 even over simple constant sets as these can be propagated into MEM
+	 expressions.  */
+      if (mips_immediate_operand_p (PLUS, INTVAL (XEXP (x, 1))))
+	{
+	  *total = -1;
+	  return true;
+	}
+
       /* Double-word operations require three single-word operations and
 	 an SLTU.  The MIPS16 version then needs to move the result of
 	 the SLTU from $24 to a MIPS16 register.  */