[PATCH] More PRE TLC

[PATCH] More PRE TLC

[Richard Biener]

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

2017-08-02  Richard Biener  <rguenther@suse.de>

	* tree-ssa-pre.c (bitmap_insert_into_set_1): Remove and inline
	into ...
	(bitmap_insert_into_set): ... this.

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 250777)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -540,8 +540,6 @@ static void bitmap_set_copy (bitmap_set_
 static void bitmap_set_and (bitmap_set_t, bitmap_set_t);
 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
-static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
-				      unsigned int, bool);
 static bitmap_set_t bitmap_set_new (void);
 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
 					 tree);
@@ -732,27 +730,22 @@ bitmap_remove_from_set (bitmap_set_t set
     }
 }
 
+/* Insert an expression EXPR into a bitmapped set.  */
+
 static void
-bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
-			  unsigned int val, bool allow_constants)
+bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
 {
-  if (allow_constants || !value_id_constant_p (val))
+  unsigned int val = get_expr_value_id (expr);
+  if (! value_id_constant_p (val))
     {
-      /* We specifically expect this and only this function to be able to
-	 insert constants into a set.  */
+      /* Note this is the only function causing multiple expressions
+         for the same value to appear in a set.  This is needed for
+	 TMP_GEN, PHI_GEN and NEW_SETs.  */
       bitmap_set_bit (&set->values, val);
       bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
     }
 }
 
-/* Insert an expression EXPR into a bitmapped set.  */
-
-static void
-bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
-{
-  bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false);
-}
-
 /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
 
 static void
@@ -2471,7 +2515,8 @@ compute_antic (void)
     {
       /* For partial antic we ignore backedges and thus we do not need
          to perform any iteration when we process blocks in postorder.  */
-      int postorder_num = pre_and_rev_post_order_compute (NULL, postorder.address (), false);
+      int postorder_num
+	= pre_and_rev_post_order_compute (NULL, postorder.address (), false);
       for (i = postorder_num - 1 ; i >= 0; i--)
 	{
 	  basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);

[PATCH] More PRE TLC

[Richard Biener]

This makes get_expr_value_id cheap and completes the
constant value-id simplification by turning the constant_value_expressions
into a direct map instead of a set of pre_exprs for the value.

Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.

2020-11-10  Richard Biener  <rguenther@suse.de>

	* tree-ssa-pre.c (pre_expr_d::value_id): Add.
	(constant_value_expressions): Turn into an array of pre_expr.
	(get_or_alloc_expr_for_nary): New function.
	(get_or_alloc_expr_for_reference): Likewise.
	(add_to_value): For constant values only ever add a single
	CONSTANT.
	(get_expr_value_id): Return the new value_id member.
	(vn_valnum_from_value_id): Split out and simplify constant
	value id handling.
	(get_or_alloc_expr_for_constant): Set the value_id member.
	(phi_translate_1): Use get_or_alloc_expr_for_*.
	(compute_avail): Likewise.
	(bitmap_find_leader): Simplify constant value id handling.
---
 gcc/tree-ssa-pre.c | 183 ++++++++++++++++++++++-----------------------
 1 file changed, 89 insertions(+), 94 deletions(-)

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index fec3b2f80f1..160f3b4593a 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -256,6 +256,7 @@ typedef struct pre_expr_d : nofree_ptr_hash <pre_expr_d>
 {
   enum pre_expr_kind kind;
   unsigned int id;
+  unsigned value_id;
   location_t loc;
   pre_expr_union u;
 
@@ -422,11 +423,65 @@ get_or_alloc_expr_for_name (tree name)
   result = pre_expr_pool.allocate ();
   result->kind = NAME;
   result->loc = UNKNOWN_LOCATION;
+  result->value_id = VN_INFO (name)->value_id;
   PRE_EXPR_NAME (result) = name;
   alloc_expression_id (result);
   return result;
 }
 
+/* Given an NARY, get or create a pre_expr to represent it.  */
+
+static pre_expr
+get_or_alloc_expr_for_nary (vn_nary_op_t nary,
+			    location_t loc = UNKNOWN_LOCATION)
+{
+  struct pre_expr_d expr;
+  pre_expr result;
+  unsigned int result_id;
+
+  expr.kind = NARY;
+  expr.id = 0;
+  PRE_EXPR_NARY (&expr) = nary;
+  result_id = lookup_expression_id (&expr);
+  if (result_id != 0)
+    return expression_for_id (result_id);
+
+  result = pre_expr_pool.allocate ();
+  result->kind = NARY;
+  result->loc = loc;
+  result->value_id = nary->value_id;
+  PRE_EXPR_NARY (result) = nary;
+  alloc_expression_id (result);
+  return result;
+}
+
+/* Given an REFERENCE, get or create a pre_expr to represent it.  */
+
+static pre_expr
+get_or_alloc_expr_for_reference (vn_reference_t reference,
+				 location_t loc = UNKNOWN_LOCATION)
+{
+  struct pre_expr_d expr;
+  pre_expr result;
+  unsigned int result_id;
+
+  expr.kind = REFERENCE;
+  expr.id = 0;
+  PRE_EXPR_REFERENCE (&expr) = reference;
+  result_id = lookup_expression_id (&expr);
+  if (result_id != 0)
+    return expression_for_id (result_id);
+
+  result = pre_expr_pool.allocate ();
+  result->kind = REFERENCE;
+  result->loc = loc;
+  result->value_id = reference->value_id;
+  PRE_EXPR_REFERENCE (result) = reference;
+  alloc_expression_id (result);
+  return result;
+}
+
+
 /* An unordered bitmap set.  One bitmap tracks values, the other,
    expressions.  */
 typedef class bitmap_set
@@ -444,9 +499,9 @@ public:
 
 /* Mapping from value id to expressions with that value_id.  */
 static vec<bitmap> value_expressions;
-/* ???  We want to just record a single expression for each constant
-   value, one of kind CONSTANT.  */
-static vec<bitmap> constant_value_expressions;
+/* We just record a single expression for each constant value,
+   one of kind CONSTANT.  */
+static vec<pre_expr> constant_value_expressions;
 
 
 /* This structure is used to keep track of statistics on what
@@ -640,35 +695,33 @@ phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
 static void
 add_to_value (unsigned int v, pre_expr e)
 {
-  bitmap set;
-
   gcc_checking_assert (get_expr_value_id (e) == v);
 
   if (value_id_constant_p (v))
     {
+      if (e->kind != CONSTANT)
+	return;
+
       if (-v >= constant_value_expressions.length ())
 	constant_value_expressions.safe_grow_cleared (-v + 1);
 
-      set = constant_value_expressions[-v];
-      if (!set)
-	{
-	  set = BITMAP_ALLOC (&grand_bitmap_obstack);
-	  constant_value_expressions[-v] = set;
-	}
+      pre_expr leader = constant_value_expressions[-v];
+      if (!leader)
+	constant_value_expressions[-v] = e;
     }
   else
     {
       if (v >= value_expressions.length ())
 	value_expressions.safe_grow_cleared (v + 1);
 
-      set = value_expressions[v];
+      bitmap set = value_expressions[v];
       if (!set)
 	{
 	  set = BITMAP_ALLOC (&grand_bitmap_obstack);
 	  value_expressions[v] = set;
 	}
+      bitmap_set_bit (set, get_or_alloc_expression_id (e));
     }
-  bitmap_set_bit (set, get_or_alloc_expression_id (e));
 }
 
 /* Create a new bitmap set and return it.  */
@@ -687,29 +740,10 @@ bitmap_set_new (void)
 static unsigned int
 get_expr_value_id (pre_expr expr)
 {
-  unsigned int id;
-  switch (expr->kind)
-    {
-    case CONSTANT:
-      id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
-      break;
-    case NAME:
-      id = VN_INFO (PRE_EXPR_NAME (expr))->value_id;
-      break;
-    case NARY:
-      gcc_assert (!PRE_EXPR_NARY (expr)->predicated_values);
-      id = PRE_EXPR_NARY (expr)->value_id;
-      break;
-    case REFERENCE:
-      id = PRE_EXPR_REFERENCE (expr)->value_id;
-      break;
-    default:
-      gcc_unreachable ();
-    }
   /* ???  We cannot assert that expr has a value-id (it can be 0), because
      we assign value-ids only to expressions that have a result
      in set_hashtable_value_ids.  */
-  return id;
+  return expr->value_id;
 }
 
 /* Return a VN valnum (SSA name or constant) for the PRE value-id VAL.  */
@@ -717,20 +751,22 @@ get_expr_value_id (pre_expr expr)
 static tree
 vn_valnum_from_value_id (unsigned int val)
 {
+  if (value_id_constant_p (val))
+    {
+      pre_expr vexpr = constant_value_expressions[-val];
+      if (vexpr)
+	return PRE_EXPR_CONSTANT (vexpr);
+      return NULL_TREE;
+    }
+
+  bitmap exprset = value_expressions[val];
   bitmap_iterator bi;
   unsigned int i;
-  bitmap exprset;
-  if (value_id_constant_p (val))
-    exprset = constant_value_expressions[-val];
-  else
-    exprset = value_expressions[val];
   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
     {
       pre_expr vexpr = expression_for_id (i);
       if (vexpr->kind == NAME)
 	return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
-      else if (vexpr->kind == CONSTANT)
-	return PRE_EXPR_CONSTANT (vexpr);
     }
   return NULL_TREE;
 }
@@ -1102,7 +1138,6 @@ static pre_expr
 get_or_alloc_expr_for_constant (tree constant)
 {
   unsigned int result_id;
-  unsigned int value_id;
   struct pre_expr_d expr;
   pre_expr newexpr;
 
@@ -1117,8 +1152,8 @@ get_or_alloc_expr_for_constant (tree constant)
   newexpr->loc = UNKNOWN_LOCATION;
   PRE_EXPR_CONSTANT (newexpr) = constant;
   alloc_expression_id (newexpr);
-  value_id = get_or_alloc_constant_value_id (constant);
-  add_to_value (value_id, newexpr);
+  newexpr->value_id = get_or_alloc_constant_value_id (constant);
+  add_to_value (newexpr->value_id, newexpr);
   return newexpr;
 }
 
@@ -1475,17 +1510,7 @@ phi_translate_1 (bitmap_set_t dest,
 	    if (result && is_gimple_min_invariant (result))
 	      return get_or_alloc_expr_for_constant (result);
 
-	    expr = pre_expr_pool.allocate ();
-	    expr->kind = NARY;
-	    expr->id = 0;
-	    expr->loc = expr_loc;
-	    if (nary && !nary->predicated_values)
-	      {
-		PRE_EXPR_NARY (expr) = nary;
-		new_val_id = nary->value_id;
-		get_or_alloc_expression_id (expr);
-	      }
-	    else
+	    if (!nary || nary->predicated_values)
 	      {
 		new_val_id = get_next_value_id ();
 		nary = vn_nary_op_insert_pieces (newnary->length,
@@ -1493,10 +1518,9 @@ phi_translate_1 (bitmap_set_t dest,
 						 newnary->type,
 						 &newnary->op[0],
 						 result, new_val_id);
-		PRE_EXPR_NARY (expr) = nary;
-		get_or_alloc_expression_id (expr);
 	      }
-	    add_to_value (new_val_id, expr);
+	    expr = get_or_alloc_expr_for_nary (nary, expr_loc);
+	    add_to_value (get_expr_value_id (expr), expr);
 	  }
 	return expr;
       }
@@ -1628,11 +1652,6 @@ phi_translate_1 (bitmap_set_t dest,
 		return NULL;
 	      }
 
-	    expr = pre_expr_pool.allocate ();
-	    expr->kind = REFERENCE;
-	    expr->id = 0;
-	    expr->loc = expr_loc;
-
 	    if (newref)
 	      new_val_id = newref->value_id;
 	    else
@@ -1649,8 +1668,7 @@ phi_translate_1 (bitmap_set_t dest,
 						     result, new_val_id);
 		newoperands = vNULL;
 	      }
-	    PRE_EXPR_REFERENCE (expr) = newref;
-	    get_or_alloc_expression_id (expr);
+	    expr = get_or_alloc_expr_for_reference (newref, expr_loc);
 	    add_to_value (new_val_id, expr);
 	  }
 	newoperands.release ();
@@ -1782,19 +1800,8 @@ static pre_expr
 bitmap_find_leader (bitmap_set_t set, unsigned int val)
 {
   if (value_id_constant_p (val))
-    {
-      unsigned int i;
-      bitmap_iterator bi;
-      bitmap exprset = constant_value_expressions[-val];
+    return constant_value_expressions[-val];
 
-      EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
-	{
-	  pre_expr expr = expression_for_id (i);
-	  if (expr->kind == CONSTANT)
-	    return expr;
-	}
-      gcc_unreachable ();
-    }
   if (bitmap_set_contains_value (set, val))
     {
       /* Rather than walk the entire bitmap of expressions, and see
@@ -3932,13 +3939,8 @@ compute_avail (void)
 		    || gimple_bb (SSA_NAME_DEF_STMT
 				    (gimple_vuse (stmt))) != block)
 		  {
-		    result = pre_expr_pool.allocate ();
-		    result->kind = REFERENCE;
-		    result->id = 0;
-		    result->loc = gimple_location (stmt);
-		    PRE_EXPR_REFERENCE (result) = ref;
-
-		    get_or_alloc_expression_id (result);
+		    result = get_or_alloc_expr_for_reference
+			       (ref, gimple_location (stmt));
 		    add_to_value (get_expr_value_id (result), result);
 		    bitmap_value_insert_into_set (EXP_GEN (block), result);
 		  }
@@ -3973,11 +3975,8 @@ compute_avail (void)
 			  && vn_nary_may_trap (nary))
 			continue;
 
-		      result = pre_expr_pool.allocate ();
-		      result->kind = NARY;
-		      result->id = 0;
-		      result->loc = gimple_location (stmt);
-		      PRE_EXPR_NARY (result) = nary;
+		      result = get_or_alloc_expr_for_nary
+				 (nary, gimple_location (stmt));
 		      break;
 		    }
 
@@ -4098,11 +4097,8 @@ compute_avail (void)
 			}
 		      operands.release ();
 
-		      result = pre_expr_pool.allocate ();
-		      result->kind = REFERENCE;
-		      result->id = 0;
-		      result->loc = gimple_location (stmt);
-		      PRE_EXPR_REFERENCE (result) = ref;
+		      result = get_or_alloc_expr_for_reference
+				 (ref, gimple_location (stmt));
 		      break;
 		    }
 
@@ -4110,7 +4106,6 @@ compute_avail (void)
 		    continue;
 		  }
 
-		get_or_alloc_expression_id (result);
 		add_to_value (get_expr_value_id (result), result);
 		bitmap_value_insert_into_set (EXP_GEN (block), result);
 		continue;
-- 
2.26.2

[PATCH] More PRE TLC

[Richard Guenther]

This moves handling of trapping ops to prune_clobbered_mems and
compute_avail, similar to how I moved handling of clobbered mems
earlier.  It fixes one existing testcase even.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

2012-05-03  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-pre.c (valid_in_sets): Remove checking of trapping
	operations.
	(prune_clobbered_mems): Do it here.  Do not uselessly sort
	expressions.
	(compute_avail): Do not add possibly trapping operations to
	EXP_GEN if they might not be executed in the block.

	* gcc.dg/tree-ssa/ssa-pre-27.c: Remove XFAIL.

Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c	(revision 187092)
--- gcc/tree-ssa-pre.c	(working copy)
*************** valid_in_sets (bitmap_set_t set1, bitmap
*** 2069,2081 ****
  	for (i = 0; i < nary->length; i++)
  	  if (!op_valid_in_sets (set1, set2, nary->op[i]))
  	    return false;
- 	/* If the NARY may trap make sure the block does not contain
- 	   a possible exit point.
- 	   ???  This is overly conservative if we translate AVAIL_OUT
- 	   as the available expression might be after the exit point.  */
- 	if (BB_MAY_NOTRETURN (block)
- 	    && vn_nary_may_trap (nary))
- 	  return false;
  	return true;
        }
        break;
--- 2069,2074 ----
*************** clean (bitmap_set_t set, basic_block blo
*** 2140,2174 ****
  }
  
  /* Clean the set of expressions that are no longer valid in SET because
!    they are clobbered in BLOCK.  */
  
  static void
  prune_clobbered_mems (bitmap_set_t set, basic_block block)
  {
!   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
!   pre_expr expr;
!   int i;
  
!   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
      {
!       vn_reference_t ref;
!       if (expr->kind != REFERENCE)
! 	continue;
! 
!       ref = PRE_EXPR_REFERENCE (expr);
!       if (ref->vuse)
  	{
! 	  gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
! 	  if (!gimple_nop_p (def_stmt)
! 	      && ((gimple_bb (def_stmt) != block
! 		   && !dominated_by_p (CDI_DOMINATORS,
! 				       block, gimple_bb (def_stmt)))
! 		  || (gimple_bb (def_stmt) == block
! 		      && value_dies_in_block_x (expr, block))))
  	    bitmap_remove_from_set (set, expr);
  	}
      }
-   VEC_free (pre_expr, heap, exprs);
  }
  
  static sbitmap has_abnormal_preds;
--- 2133,2176 ----
  }
  
  /* Clean the set of expressions that are no longer valid in SET because
!    they are clobbered in BLOCK or because they trap and may not be executed.  */
  
  static void
  prune_clobbered_mems (bitmap_set_t set, basic_block block)
  {
!   bitmap_iterator bi;
!   unsigned i;
  
!   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
      {
!       pre_expr expr = expression_for_id (i);
!       if (expr->kind == REFERENCE)
! 	{
! 	  vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
! 	  if (ref->vuse)
! 	    {
! 	      gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
! 	      if (!gimple_nop_p (def_stmt)
! 		  && ((gimple_bb (def_stmt) != block
! 		       && !dominated_by_p (CDI_DOMINATORS,
! 					   block, gimple_bb (def_stmt)))
! 		      || (gimple_bb (def_stmt) == block
! 			  && value_dies_in_block_x (expr, block))))
! 		bitmap_remove_from_set (set, expr);
! 	    }
! 	}
!       else if (expr->kind == NARY)
  	{
! 	  vn_nary_op_t nary = PRE_EXPR_NARY (expr);
! 	  /* If the NARY may trap make sure the block does not contain
! 	     a possible exit point.
! 	     ???  This is overly conservative if we translate AVAIL_OUT
! 	     as the available expression might be after the exit point.  */
! 	  if (BB_MAY_NOTRETURN (block)
! 	      && vn_nary_may_trap (nary))
  	    bitmap_remove_from_set (set, expr);
  	}
      }
  }
  
  static sbitmap has_abnormal_preds;
*************** compute_avail (void)
*** 4119,4124 ****
--- 4121,4133 ----
  			if (TREE_CODE (nary->op[i]) == SSA_NAME)
  			  add_to_exp_gen (block, nary->op[i]);
  
+ 		      /* If the NARY traps and there was a preceeding
+ 		         point in the block that might not return avoid
+ 			 adding the nary to EXP_GEN.  */
+ 		      if (BB_MAY_NOTRETURN (block)
+ 			  && vn_nary_may_trap (nary))
+ 			continue;
+ 
  		      result = (pre_expr) pool_alloc (pre_expr_pool);
  		      result->kind = NARY;
  		      result->id = 0;
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-27.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-27.c	(revision 187091)
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-27.c	(working copy)
*************** int foo2 (int i, int j, int b)
*** 17,29 ****
    int res = 0;
    if (b)
      res = i/j;
!   /* But we fail so here because of the possibly not returning
!      call in the same basic-block.  */
    res += i/j;
    bar ();
    return res;
  }
  
! /* { dg-final { scan-tree-dump-times "# prephitmp" 1 "pre" } } */
! /* { dg-final { scan-tree-dump-times "# prephitmp" 2 "pre" { xfail *-*-* } } } */
  /* { dg-final { cleanup-tree-dump "pre" } } */
--- 17,28 ----
    int res = 0;
    if (b)
      res = i/j;
!   /* And here, the possibly not returning call in the same basic-block
!      comes after the trapping i/j.  */
    res += i/j;
    bar ();
    return res;
  }
  
! /* { dg-final { scan-tree-dump-times "# prephitmp" 2 "pre" } } */
  /* { dg-final { cleanup-tree-dump "pre" } } */