[GCC8,22/33] Generate TMR in new reassociation order

Submitted by Bin Cheng on April 18, 2017, 10:49 a.m.

Details

Message ID VI1PR0802MB2176F65B7DB7B77C9B3DA63FE7190@VI1PR0802MB2176.eurprd08.prod.outlook.com
State New
Headers show

Commit Message

Bin Cheng April 18, 2017, 10:49 a.m.
Hi,
This patch generates TMR for ivopts in new re-association order.  General idea is,
by querying target's addressing mode, we put as much address computation as possible
in memory reference.  For computation that has to be done outside of memory reference,
we re-associate the address expression in new order so that loop invariant expression
is kept and exposed for later lim pass.
Is it OK?

Thanks,
bin
2017-04-11  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-address.c: Include header file.
	(move_hint_to_base): Return TRUE if BASE_HINT is moved to memory
	address.
	(add_to_parts): Refactor.
	(addr_to_parts): New parameter.  Update use of move_hint_to_base.
	(create_mem_ref): Update use of addr_to_parts.  Re-associate addr
	in new order.
From 4261c98f8e6dca7a38ed53b9b49c9f59e1906c30 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Thu, 2 Mar 2017 09:29:50 +0000
Subject: [PATCH 22/33] address-iv_use-rewrite-20170220.txt

---
 gcc/tree-ssa-address.c | 160 ++++++++++++++++++++++++++++++++-----------------
 1 file changed, 106 insertions(+), 54 deletions(-)

Patch hide | download patch | download mbox

diff --git a/gcc/tree-ssa-address.c b/gcc/tree-ssa-address.c
index 8aefed6..1b73034 100644
--- a/gcc/tree-ssa-address.c
+++ b/gcc/tree-ssa-address.c
@@ -46,6 +46,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-dfa.h"
 #include "dumpfile.h"
 #include "tree-affine.h"
+#include "gimplify.h"
 
 /* FIXME: We compute address costs using RTL.  */
 #include "tree-ssa-address.h"
@@ -427,9 +428,10 @@  move_fixed_address_to_symbol (struct mem_address *parts, aff_tree *addr)
   aff_combination_remove_elt (addr, i);
 }
 
-/* If ADDR contains an instance of BASE_HINT, move it to PARTS->base.  */
+/* Return true if ADDR contains an instance of BASE_HINT and it's moved to
+   PARTS->base.  */
 
-static void
+static bool
 move_hint_to_base (tree type, struct mem_address *parts, tree base_hint,
 		   aff_tree *addr)
 {
@@ -448,7 +450,7 @@  move_hint_to_base (tree type, struct mem_address *parts, tree base_hint,
     }
 
   if (i == addr->n)
-    return;
+    return false;
 
   /* Cast value to appropriate pointer type.  We cannot use a pointer
      to TYPE directly, as the back-end will assume registers of pointer
@@ -458,6 +460,7 @@  move_hint_to_base (tree type, struct mem_address *parts, tree base_hint,
   type = build_qualified_type (void_type_node, qual);
   parts->base = fold_convert (build_pointer_type (type), val);
   aff_combination_remove_elt (addr, i);
+  return true;
 }
 
 /* If ADDR contains an address of a dereferenced pointer, move it to
@@ -535,8 +538,7 @@  add_to_parts (struct mem_address *parts, tree elt)
   if (POINTER_TYPE_P (type))
     parts->base = fold_build_pointer_plus (parts->base, elt);
   else
-    parts->base = fold_build2 (PLUS_EXPR, type,
-			       parts->base, elt);
+    parts->base = fold_build2 (PLUS_EXPR, type, parts->base, elt);
 }
 
 /* Returns true if multiplying by RATIO is allowed in an address.  Test the
@@ -668,7 +670,8 @@  most_expensive_mult_to_index (tree type, struct mem_address *parts,
 /* Splits address ADDR for a memory access of type TYPE into PARTS.
    If BASE_HINT is non-NULL, it specifies an SSA name to be used
    preferentially as base of the reference, and IV_CAND is the selected
-   iv candidate used in ADDR.
+   iv candidate used in ADDR.  Store true to VAR_IN_BASE if variant
+   part of address is split to PARTS.base.
 
    TODO -- be more clever about the distribution of the elements of ADDR
    to PARTS.  Some architectures do not support anything but single
@@ -678,9 +681,8 @@  most_expensive_mult_to_index (tree type, struct mem_address *parts,
    addressing modes is useless.  */
 
 static void
-addr_to_parts (tree type, aff_tree *addr, tree iv_cand,
-	       tree base_hint, struct mem_address *parts,
-               bool speed)
+addr_to_parts (tree type, aff_tree *addr, tree iv_cand, tree base_hint,
+	       struct mem_address *parts, bool *var_in_base, bool speed)
 {
   tree part;
   unsigned i;
@@ -698,23 +700,20 @@  addr_to_parts (tree type, aff_tree *addr, tree iv_cand,
   /* Try to find a symbol.  */
   move_fixed_address_to_symbol (parts, addr);
 
-  /* No need to do address parts reassociation if the number of parts
-     is <= 2 -- in that case, no loop invariant code motion can be
-     exposed.  */
-
-  if (!base_hint && (addr->n > 2))
+  /* Since at the moment there is no reliable way to know how to
+     distinguish between pointer and its offset, we decide if var
+     part is the pointer based on guess.  */
+  *var_in_base = (base_hint != NULL && parts->symbol == NULL);
+  if (*var_in_base)
+    *var_in_base = move_hint_to_base (type, parts, base_hint, addr);
+  else
     move_variant_to_index (parts, addr, iv_cand);
 
-  /* First move the most expensive feasible multiplication
-     to index.  */
+  /* First move the most expensive feasible multiplication to index.  */
   if (!parts->index)
     most_expensive_mult_to_index (type, parts, addr, speed);
 
-  /* Try to find a base of the reference.  Since at the moment
-     there is no reliable way how to distinguish between pointer and its
-     offset, this is just a guess.  */
-  if (!parts->symbol && base_hint)
-    move_hint_to_base (type, parts, base_hint, addr);
+  /* Move pointer into base.  */
   if (!parts->symbol && !parts->base)
     move_pointer_to_base (parts, addr);
 
@@ -756,10 +755,11 @@  tree
 create_mem_ref (gimple_stmt_iterator *gsi, tree type, aff_tree *addr,
 		tree alias_ptr_type, tree iv_cand, tree base_hint, bool speed)
 {
+  bool var_in_base;
   tree mem_ref, tmp;
   struct mem_address parts;
 
-  addr_to_parts (type, addr, iv_cand, base_hint, &parts, speed);
+  addr_to_parts (type, addr, iv_cand, base_hint, &parts, &var_in_base, speed);
   gimplify_mem_ref_parts (gsi, &parts);
   mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
   if (mem_ref)
@@ -767,6 +767,42 @@  create_mem_ref (gimple_stmt_iterator *gsi, tree type, aff_tree *addr,
 
   /* The expression is too complicated.  Try making it simpler.  */
 
+  /* Distribute symbol to other parts.  */
+  if (parts.symbol)
+    {
+      tmp = parts.symbol;
+      parts.symbol = NULL_TREE;
+      gcc_assert (is_gimple_val (tmp));
+
+      if (parts.base)
+	{
+	  gcc_assert (useless_type_conversion_p (sizetype,
+						 TREE_TYPE (parts.base)));
+
+	  if (parts.index)
+	    {
+	      /* Add the symbol to base, eventually forcing it to register.  */
+	      tmp = fold_build_pointer_plus (tmp, parts.base);
+	      tmp = force_gimple_operand_gsi_1 (gsi, tmp,
+						is_gimple_mem_ref_addr,
+						NULL_TREE, true,
+						GSI_SAME_STMT);
+	    }
+	  else
+	    {
+	      /* Move base to index, then move the symbol to base.  */
+	      parts.index = parts.base;
+	    }
+	  parts.base = tmp;
+	}
+      else
+	parts.base = tmp;
+
+      mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
+      if (mem_ref)
+	return mem_ref;
+    }
+
   if (parts.step && !integer_onep (parts.step))
     {
       /* Move the multiplication to index.  */
@@ -782,50 +818,66 @@  create_mem_ref (gimple_stmt_iterator *gsi, tree type, aff_tree *addr,
 	return mem_ref;
     }
 
-  if (parts.symbol)
+  if (parts.offset && !integer_zerop (parts.offset))
     {
-      tmp = parts.symbol;
-      gcc_assert (is_gimple_val (tmp));
+      tree old_base = unshare_expr (parts.base);
+      tree old_index = unshare_expr (parts.index);
+      tree old_offset = unshare_expr (parts.offset);
 
-      /* Add the symbol to base, eventually forcing it to register.  */
-      if (parts.base)
+      tmp = parts.offset;
+      parts.offset = NULL_TREE;
+      /* Add offset to invariant part.  */
+      if (!var_in_base)
 	{
-	  gcc_assert (useless_type_conversion_p
-				(sizetype, TREE_TYPE (parts.base)));
-
-	  if (parts.index)
+	  if (parts.base)
 	    {
-	      parts.base = force_gimple_operand_gsi_1 (gsi,
-			fold_build_pointer_plus (tmp, parts.base),
-			is_gimple_mem_ref_addr, NULL_TREE, true, GSI_SAME_STMT);
+	      tmp = fold_build_pointer_plus (parts.base, tmp);
+	      tmp = force_gimple_operand_gsi_1 (gsi, tmp,
+						is_gimple_mem_ref_addr,
+						NULL_TREE, true,
+						GSI_SAME_STMT);
 	    }
-	  else
+	  parts.base = tmp;
+	}
+      else
+	{
+	  if (parts.index)
 	    {
-	      parts.index = parts.base;
-	      parts.base = tmp;
+	      tmp = fold_build_pointer_plus (parts.index, tmp);
+	      tmp = force_gimple_operand_gsi_1 (gsi, tmp,
+						is_gimple_mem_ref_addr,
+						NULL_TREE, true,
+						GSI_SAME_STMT);
 	    }
+	  parts.index = tmp;
 	}
-      else
-	parts.base = tmp;
-      parts.symbol = NULL_TREE;
 
       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
       if (mem_ref)
 	return mem_ref;
+
+      /* Restore parts.base, index and offset so that we can check if
+	 [base + offset] addressing mode is supported in next step.
+	 This is necessary for targets only support [base + offset],
+	 but not [base + index] addressing mode.  */
+      parts.base = old_base;
+      parts.index = old_index;
+      parts.offset = old_offset;
     }
 
   if (parts.index)
     {
+      tmp = parts.index;
+      parts.index = NULL_TREE;
       /* Add index to base.  */
       if (parts.base)
 	{
-	  parts.base = force_gimple_operand_gsi_1 (gsi,
-			fold_build_pointer_plus (parts.base, parts.index),
-			is_gimple_mem_ref_addr, NULL_TREE, true, GSI_SAME_STMT);
+	  tmp = fold_build_pointer_plus (parts.base, tmp);
+	  tmp = force_gimple_operand_gsi_1 (gsi, tmp,
+					    is_gimple_mem_ref_addr,
+					    NULL_TREE, true, GSI_SAME_STMT);
 	}
-      else
-	parts.base = parts.index;
-      parts.index = NULL_TREE;
+      parts.base = tmp;
 
       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
       if (mem_ref)
@@ -834,17 +886,17 @@  create_mem_ref (gimple_stmt_iterator *gsi, tree type, aff_tree *addr,
 
   if (parts.offset && !integer_zerop (parts.offset))
     {
-      /* Try adding offset to base.  */
+      tmp = parts.offset;
+      parts.offset = NULL_TREE;
+      /* Add offset to base.  */
       if (parts.base)
 	{
-	  parts.base = force_gimple_operand_gsi_1 (gsi,
-			fold_build_pointer_plus (parts.base, parts.offset),
-			is_gimple_mem_ref_addr, NULL_TREE, true, GSI_SAME_STMT);
+	  tmp = fold_build_pointer_plus (parts.base, tmp);
+	  tmp = force_gimple_operand_gsi_1 (gsi, tmp,
+					    is_gimple_mem_ref_addr,
+					    NULL_TREE, true, GSI_SAME_STMT);
 	}
-      else
-	parts.base = parts.offset;
-
-      parts.offset = NULL_TREE;
+      parts.base = tmp;
 
       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
       if (mem_ref)