* tree-ssa-address.c: New file.

	* Makefile.in (tree-ssa-address.o): Add.
	* expr.c (expand_expr_real_1): Do not handle REF_ORIGINAL on
	INDIRECT_REFs.  Handle TARGET_MEM_REFs.
	* tree-eh.c (tree_could_trap_p): Handle TARGET_MEM_REFs.
	* tree-flow.h (struct mem_address): New.
	(struct affine_tree_combination): Moved from tree-ssa-loop-ivopts.c.
	(create_mem_ref, addr_for_mem_ref, get_address_description,
	maybe_fold_tmr, multiplier_allowed_in_address_p,
	multiply_by_cost):  Declare.
	* tree-mudflap.c (mf_xform_derefs_1): Handle TARGET_MEM_REFs.
	* tree-pretty-print.c (dump_generic_node): Ditto.
	* tree-ssa-loop-im.c (for_each_index): Ditto.
	* tree-ssa-loop-ivopts.c (may_be_unaligned_p,
	find_interesting_uses_address): Ditto.
	(rewrite_address_base, build_addr_strip_iref): Removed.
	(struct affine_tree_combination): Moved to tree-flow.h.
	(get_ref_tag, copy_ref_info): New functions.
	(rewrite_use_address): Produce TARGET_MEM_REFs.
	(tree_ssa_iv_optimize): Do not call update_ssa
	and rewrite_into_loop_closed_ssa.
	(tree_to_aff_combination): Use build_fold_addr_expr instead of
	build_addr_strip_iref.
	(unshare_aff_combination): New function.
	(fold_affine_sum): Removed.
	(get_computation_at): Use get_computation_aff.  Unshare the result.
	(get_computation_aff, multiplier_allowed_in_address_p): New function.
	(multiply_by_cost): Exported.
	(get_address_cost): Use multiplier_allowed_in_address_p.
	* tree-ssa-operands.c (get_tmr_operands): New function.
	(get_expr_operands): Handle TARGET_MEM_REFs.
	* tree.c (copy_node_stat): Copy annotations for TARGET_MEM_REFs.
	(build): Handle 7 arguments.
	(build7_stat): New function.
	* tree.def (TARGET_MEM_DEF): New.
	* tree.h (REF_ORIGINAL): Removed.
	(TMR_SYMBOL, TMR_BASE, TMR_INDEX, TMR_STEP, TMR_OFFSET, TMR_ORIGINAL,
	TMR_TAG, build7): New macros.
	(build7_stat, tree_mem_ref_addr, copy_mem_ref_info): Declare.
	* tree-ssa-ccp.c (fold_stmt_r): Call maybe_fold_tmr.
	* doc/c-tree.texi: Document TARGET_MEM_REF.
	* doc/tree-ssa.texi: Add TARGET_MEM_REF to gimple grammar.

	* gcc.dg/tree-ssa/loop-2.c: Update outcome.
	* gcc.dg/tree-ssa/loop-3.c: Update outcome.
	* gcc.dg/tree-ssa/loop-4.c: Update outcome.
	* gcc.dg/tree-ssa/loop-9.c: New test.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@100708 138bc75d-0d04-0410-961f-82ee72b054a4

24 files changed, 1320 insertions, 238 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c56a403aa97..b4fff9ae7ee 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,48 @@
+2005-06-07  Zdenek Dvorak  <dvorakz@suse.cz>
+
+	* tree-ssa-address.c: New file.
+	* Makefile.in (tree-ssa-address.o): Add.
+	* expr.c (expand_expr_real_1): Do not handle REF_ORIGINAL on
+	INDIRECT_REFs.  Handle TARGET_MEM_REFs.
+	* tree-eh.c (tree_could_trap_p): Handle TARGET_MEM_REFs.
+	* tree-flow.h (struct mem_address): New.
+	(struct affine_tree_combination): Moved from tree-ssa-loop-ivopts.c.
+	(create_mem_ref, addr_for_mem_ref, get_address_description,
+	maybe_fold_tmr, multiplier_allowed_in_address_p,
+	multiply_by_cost):  Declare.
+	* tree-mudflap.c (mf_xform_derefs_1): Handle TARGET_MEM_REFs.
+	* tree-pretty-print.c (dump_generic_node): Ditto.
+	* tree-ssa-loop-im.c (for_each_index): Ditto.
+	* tree-ssa-loop-ivopts.c (may_be_unaligned_p,
+	find_interesting_uses_address): Ditto.
+	(rewrite_address_base, build_addr_strip_iref): Removed.
+	(struct affine_tree_combination): Moved to tree-flow.h.
+	(get_ref_tag, copy_ref_info): New functions.
+	(rewrite_use_address): Produce TARGET_MEM_REFs.
+	(tree_ssa_iv_optimize): Do not call update_ssa
+	and rewrite_into_loop_closed_ssa.
+	(tree_to_aff_combination): Use build_fold_addr_expr instead of
+	build_addr_strip_iref.
+	(unshare_aff_combination): New function.
+	(fold_affine_sum): Removed.
+	(get_computation_at): Use get_computation_aff.  Unshare the result.
+	(get_computation_aff, multiplier_allowed_in_address_p): New function.
+	(multiply_by_cost): Exported.
+	(get_address_cost): Use multiplier_allowed_in_address_p.
+	* tree-ssa-operands.c (get_tmr_operands): New function.
+	(get_expr_operands): Handle TARGET_MEM_REFs.
+	* tree.c (copy_node_stat): Copy annotations for TARGET_MEM_REFs.
+	(build): Handle 7 arguments.
+	(build7_stat): New function.
+	* tree.def (TARGET_MEM_DEF): New.
+	* tree.h (REF_ORIGINAL): Removed.
+	(TMR_SYMBOL, TMR_BASE, TMR_INDEX, TMR_STEP, TMR_OFFSET, TMR_ORIGINAL,
+	TMR_TAG, build7): New macros.
+	(build7_stat, tree_mem_ref_addr, copy_mem_ref_info): Declare.
+	* tree-ssa-ccp.c (fold_stmt_r): Call maybe_fold_tmr.
+	* doc/c-tree.texi: Document TARGET_MEM_REF.
+	* doc/tree-ssa.texi: Add TARGET_MEM_REF to gimple grammar.
+
 2005-06-07  Jakub Jelinek  <jakub@redhat.com>
 
 	PR debug/21946
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 67c91e3430b..b9f0f1edf3d 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -684,7 +684,7 @@ CONFIG_H  = config.h  $(host_xm_file_list)
 TCONFIG_H = tconfig.h $(xm_file_list)
 TM_P_H    = tm_p.h    $(tm_p_file_list)
 GTM_H     = tm.h      $(tm_file_list)
-TM_H      = $(GTM_H) insn-constants.h insn-flags.h
+TM_H      = $(GTM_H) insn-constants.h insn-flags.h options.h
 
 # Variables for version information.
 BASEVER     := $(srcdir)/BASE-VER  # 4.x.y
@@ -935,7 +935,8 @@ OBJS-common = \
  tree-vect-generic.o tree-ssa-loop.o tree-ssa-loop-niter.o		   \
  tree-ssa-loop-manip.o tree-ssa-threadupdate.o				   \
  tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o		   \
- tree-ssa-loop-ivcanon.o tree-ssa-propagate.o tree-ssa-math-opts.o	   \
+ tree-ssa-loop-ivcanon.o tree-ssa-propagate.o tree-ssa-address.o	   \
+ tree-ssa-math-opts.o							   \
  tree-ssa-loop-ivopts.o tree-if-conv.o tree-ssa-loop-unswitch.o		   \
  alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
  cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
@@ -1801,6 +1802,11 @@ tree-ssa-loop-unswitch.o : tree-ssa-loop-unswitch.c $(TREE_FLOW_H) \
    $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
    domwalk.h $(PARAMS_H) output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \
    coretypes.h $(TREE_DUMP_H) tree-pass.h $(BASIC_BLOCK_H) hard-reg-set.h
+tree-ssa-address.o : tree-ssa-address.c $(TREE_FLOW_H) $(CONFIG_H) \
+   $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) \
+   output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+   tree-pass.h $(FLAGS_H) tree-inline.h $(RECOG_H) insn-config.h $(EXPR_H) \
+   gt-tree-ssa-address.h $(GGC_H)
 tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \
    tree-inline.h output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
@@ -2622,7 +2628,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/coretypes.h \
   $(srcdir)/stringpool.c $(srcdir)/tree.c $(srcdir)/varasm.c \
   $(srcdir)/tree-mudflap.c $(srcdir)/tree-flow.h \
   $(srcdir)/c-objc-common.c $(srcdir)/c-common.c $(srcdir)/c-parser.c \
-  $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c \
+  $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c $(srcdir)/tree-ssa-address.c \
   $(srcdir)/tree-phinodes.c $(srcdir)/tree-cfg.c \
   $(srcdir)/tree-dfa.c $(srcdir)/tree-ssa-propagate.c \
   $(srcdir)/tree-iterator.c $(srcdir)/gimplify.c \
@@ -2645,7 +2651,8 @@ gt-expr.h gt-sdbout.h gt-optabs.h gt-bitmap.h gt-dojump.h \
 gt-dwarf2out.h gt-reg-stack.h gt-dwarf2asm.h \
 gt-dbxout.h gt-c-common.h gt-c-decl.h gt-c-parser.h \
 gt-c-pragma.h gtype-c.h gt-cfglayout.h \
-gt-tree-mudflap.h gt-tree-vect-generic.h gt-tree-profile.h \
+gt-tree-mudflap.h gt-tree-vect-generic.h \
+gt-tree-profile.h gt-tree-ssa-address.h \
 gt-tree-ssanames.h gt-tree-iterator.h gt-gimplify.h \
 gt-tree-phinodes.h gt-tree-nested.h \
 gt-tree-ssa-operands.h gt-tree-ssa-propagate.h \
diff --git a/gcc/doc/c-tree.texi b/gcc/doc/c-tree.texi
index a6033f16256..196aa564430 100644
--- a/gcc/doc/c-tree.texi
+++ b/gcc/doc/c-tree.texi
@@ -1712,6 +1712,7 @@ This macro returns the attributes on the type @var{type}.
 @tindex EXACT_DIV_EXPR
 @tindex ARRAY_REF
 @tindex ARRAY_RANGE_REF
+@tindex TARGET_MEM_REF
 @tindex LT_EXPR
 @tindex LE_EXPR
 @tindex GT_EXPR
@@ -2103,6 +2104,26 @@ meanings.  The type of these expressions must be an array whose component
 type is the same as that of the first operand.  The range of that array
 type determines the amount of data these expressions access.
 
+@item TARGET_MEM_REF
+These nodes represent memory accesses whose address directly map to
+an addressing mode of the target architecture.  The first argument
+is @code{TMR_SYMBOL} and must be a @code{VAR_DECL} of an object with
+a fixed address.  The second argument is @code{TMR_BASE} and the
+third one is @code{TMR_INDEX}.  The fourth argument is
+@code{TMR_STEP} and must be an @code{INTEGER_CST}.  The fifth
+argument is @code{TMR_OFFSET} and must be an @code{INTEGER_CST}.
+Any of the arguments may be NULL if the appropriate component
+does not appear in the address.  Address of the @code{TARGET_MEM_REF}
+is determined in the following way.
+
+@smallexample
+&TMR_SYMBOL + TMR_BASE + TMR_INDEX * TMR_STEP + TMR_OFFSET
+@end smallexample
+
+The sixth argument is the reference to the original memory access, which
+is preserved for the purposes of the RTL alias analysis.  The seventh
+argument is a tag representing the results of tree level alias analysis.
+
 @item LT_EXPR
 @itemx LE_EXPR
 @itemx GT_EXPR
diff --git a/gcc/doc/tree-ssa.texi b/gcc/doc/tree-ssa.texi
index 56c605c0b57..7113c394dd5 100644
--- a/gcc/doc/tree-ssa.texi
+++ b/gcc/doc/tree-ssa.texi
@@ -632,6 +632,12 @@ void f()
                         op2 -> var
 
    compref      : inner-compref
+                | TARGET_MEM_REF
+                        op0 -> ID
+                        op1 -> val
+                        op2 -> val
+                        op3 -> CONST
+                        op4 -> CONST
                 | REALPART_EXPR
                         op0 -> inner-compref
                 | IMAGPART_EXPR
diff --git a/gcc/expr.c b/gcc/expr.c
index a3ee9e77a60..8b75ed7c605 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -6862,7 +6862,6 @@ expand_expr_real_1 (tree exp, rtx target, enum machine_mode tmode,
     case INDIRECT_REF:
       {
 	tree exp1 = TREE_OPERAND (exp, 0);
-	tree orig;
 
 	if (modifier != EXPAND_WRITE)
 	  {
@@ -6885,10 +6884,7 @@ expand_expr_real_1 (tree exp, rtx target, enum machine_mode tmode,
 
 	temp = gen_rtx_MEM (mode, op0);
 
-	orig = REF_ORIGINAL (exp);
-	if (!orig)
-	  orig = exp;
-	set_mem_attributes (temp, orig, 0);
+	set_mem_attributes (temp, exp, 0);
 
 	/* Resolve the misalignment now, so that we don't have to remember
 	   to resolve it later.  Of course, this only works for reads.  */
@@ -6920,6 +6916,18 @@ expand_expr_real_1 (tree exp, rtx target, enum machine_mode tmode,
 	return temp;
       }
 
+    case TARGET_MEM_REF:
+      {
+	struct mem_address addr;
+
+	get_address_description (exp, &addr);
+	op0 = addr_for_mem_ref (&addr, true);
+	op0 = memory_address (mode, op0);
+	temp = gen_rtx_MEM (mode, op0);
+	set_mem_attributes (temp, TMR_ORIGINAL (exp), 0);
+      }
+      return temp;
+
     case ARRAY_REF:
 
       {
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index a6edac72e70..d16e6f94b02 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2005-06-07  Zdenek Dvorak  <dvorakz@suse.cz>
+
+	* gcc.dg/tree-ssa/loop-2.c: Update outcome.
+	* gcc.dg/tree-ssa/loop-3.c: Update outcome.
+	* gcc.dg/tree-ssa/loop-4.c: Update outcome.
+	* gcc.dg/tree-ssa/loop-9.c: New test.
+
 2005-06-07  Nathan Sidwell  <nathan@codesourcery.com>
 
 	* g++.dg/parse/defarg10.C: New.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-2.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-2.c
index 381e34e08f9..e086499ca27 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/loop-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-2.c
@@ -21,9 +21,12 @@ void xxx(void)
     arr_base[iter].y = 17 * iter;
 }
 
-/* Access to arr_base[iter].y should be strength reduced.  */
+/* Access to arr_base[iter].y should be strength reduced, i.e., there should
+   be no multiplication.  */
 
-/* { dg-final { scan-tree-dump-times "arr_base\[^\\n\\r\]*=" 0 "vars" } } */
+/* { dg-final { scan-tree-dump-times " \\* \[^\\n\\r\]*=" 0 "vars" } } */
+/* { dg-final { scan-tree-dump-times "\[^\\n\\r\]*= \\* " 0 "vars" } } */
+/* { dg-final { scan-tree-dump-times "MEM" 1 "vars" } } */
 
 /* 17 * iter should be strength reduced.  */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-3.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-3.c
index 35f127e14ad..63e582b6f43 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/loop-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-3.c
@@ -20,7 +20,8 @@ void xxx(void)
 /* Access to arr_base[iter].y should not be strength reduced, since
    we have a memory mode including multiplication by 4.  */
 
-/* { dg-final { scan-tree-dump-times "arr_base.*=" 1 "vars" } } */
+/* { dg-final { scan-tree-dump-times "MEM" 1 "vars" } } */
+/* { dg-final { scan-tree-dump-times "step:" 1 "vars" } } */
 
 /* And original induction variable should be preserved.  */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-4.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-4.c
index 6a6b97d9925..49e5a41e0d5 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/loop-4.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-4.c
@@ -32,9 +32,11 @@ void xxx(void)
    -- induction variable with base 0, the memory access of form
       *(iv + &arr_base[0].y) = ...
 
-   In any case, we should not have 'arr_base[.*] ='  */
+   In any case, we should not have any multiplication.  */
 
-/* { dg-final { scan-tree-dump-times "arr_base\[.*\]\.y =" 0 "vars" } } */
+/* { dg-final { scan-tree-dump-times " \\* \[^\\n\\r\]*=" 0 "vars" } } */
+/* { dg-final { scan-tree-dump-times "\[^\\n\\r\]*= \\* " 0 "vars" } } */
+/* { dg-final { scan-tree-dump-times "MEM" 1 "vars" } } */
 
 /* And the original induction variable should be eliminated.  */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-9.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-9.c
new file mode 100644
index 00000000000..a03ce7214c8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-9.c
@@ -0,0 +1,24 @@
+/* Without TARGET_MEM_REFs, dom creates code like
+   
+   i1 = 4 * i;
+   *(p + i1) = i;
+   *(p + i1 + 4) = i
+   
+   causing us to have unnecessary multiplication by 4 in the
+   result.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O1" } */
+
+void foo (int *p)
+{
+  int i;
+
+  for (i = 0; i < 100; i++)
+    {
+      p[i] = i;
+      p[i + 1] = i;
+    }
+}
+
+/* { dg-final { scan-assembler-times "lea" 0 { target i?86-*-* x86_64-*-* } } } */
diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c
index 7f205c4354d..4288c2c3c70 100644
--- a/gcc/tree-dfa.c
+++ b/gcc/tree-dfa.c
@@ -185,7 +185,6 @@ create_stmt_ann (tree t)
   return ann;
 }
 
-
 /* Create a new annotation for a tree T.  */
 
 tree_ann_t
diff --git a/gcc/tree-eh.c b/gcc/tree-eh.c
index bbe06721f75..0820e6738e1 100644
--- a/gcc/tree-eh.c
+++ b/gcc/tree-eh.c
@@ -1869,6 +1869,13 @@ tree_could_trap_p (tree expr)
  restart:
   switch (code)
     {
+    case TARGET_MEM_REF:
+      /* For TARGET_MEM_REFs use the information based on the original
+	 reference.  */
+      expr = TMR_ORIGINAL (expr);
+      code = TREE_CODE (expr);
+      goto restart;
+
     case COMPONENT_REF:
     case REALPART_EXPR:
     case IMAGPART_EXPR:
diff --git a/gcc/tree-flow-inline.h b/gcc/tree-flow-inline.h
index d7b0aa45b50..68f8562fc3a 100644
--- a/gcc/tree-flow-inline.h
+++ b/gcc/tree-flow-inline.h
@@ -66,7 +66,6 @@ get_stmt_ann (tree stmt)
   return (ann) ? ann : create_stmt_ann (stmt);
 }
 
-
 /* Return the annotation type for annotation ANN.  */
 static inline enum tree_ann_type
 ann_type (tree_ann_t ann)
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 51a2051947d..7d7dc00a01b 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -736,7 +736,9 @@ void insert_edge_copies (tree, basic_block);
 extern void linear_transform_loops (struct loops *);
 
 /* In tree-ssa-loop-ivopts.c  */
-extern bool expr_invariant_in_loop_p (struct loop *, tree);
+bool expr_invariant_in_loop_p (struct loop *, tree);
+bool multiplier_allowed_in_address_p (HOST_WIDE_INT);
+unsigned multiply_by_cost (HOST_WIDE_INT, enum machine_mode);
 
 /* In tree-ssa-threadupdate.c.  */
 extern bool thread_through_all_blocks (bitmap);
@@ -745,6 +747,48 @@ extern bool thread_through_all_blocks (bitmap);
 tree force_gimple_operand (tree, tree *, bool, tree);
 tree force_gimple_operand_bsi (block_stmt_iterator *, tree, bool, tree);
 
+/* In tree-ssa-address.c  */
+
+/* Affine combination of trees.  We keep track of at most MAX_AFF_ELTS elements
+   to make things simpler; this is sufficient in most cases.  */
+
+#define MAX_AFF_ELTS 8
+
+struct affine_tree_combination
+{
+  /* Type of the result of the combination.  */
+  tree type;
+
+  /* Mask modulo that the operations are performed.  */
+  unsigned HOST_WIDE_INT mask;
+
+  /* Constant offset.  */
+  unsigned HOST_WIDE_INT offset;
+
+  /* Number of elements of the combination.  */
+  unsigned n;
+
+  /* Elements and their coefficients.  */
+  tree elts[MAX_AFF_ELTS];
+  unsigned HOST_WIDE_INT coefs[MAX_AFF_ELTS];
+
+  /* Remainder of the expression.  */
+  tree rest;
+};
+
+/* Description of a memory address.  */
+
+struct mem_address
+{
+  tree symbol, base, index, step, offset;
+};
+
+tree create_mem_ref (block_stmt_iterator *, tree, 
+		     struct affine_tree_combination *);
+rtx addr_for_mem_ref (struct mem_address *, bool);
+void get_address_description (tree, struct mem_address *);
+tree maybe_fold_tmr (tree);
+
 #include "tree-flow-inline.h"
 
 #endif /* _TREE_FLOW_H  */
diff --git a/gcc/tree-mudflap.c b/gcc/tree-mudflap.c
index a6d87cc42ae..401e6b15cdb 100644
--- a/gcc/tree-mudflap.c
+++ b/gcc/tree-mudflap.c
@@ -835,6 +835,14 @@ mf_xform_derefs_1 (block_stmt_iterator *iter, tree *tp,
                            integer_one_node));
       break;
 
+    case TARGET_MEM_REF:
+      addr = tree_mem_ref_addr (ptr_type_node, t);
+      base = addr;
+      limit = fold_build2 (MINUS_EXPR, ptr_type_node,
+			   fold_build2 (PLUS_EXPR, ptr_type_node, base, size),
+			   build_int_cst_type (ptr_type_node, 1));
+      break;
+
     case ARRAY_RANGE_REF:
       warning (0, "mudflap checking not yet implemented for ARRAY_RANGE_REF");
       return;
diff --git a/gcc/tree-pretty-print.c b/gcc/tree-pretty-print.c
index 86649458f00..a079f3efb2a 100644
--- a/gcc/tree-pretty-print.c
+++ b/gcc/tree-pretty-print.c
@@ -443,6 +443,64 @@ dump_generic_node (pretty_printer *buffer, tree node, int spc, int flags,
       pp_string (buffer, "::");
       break;
 
+    case TARGET_MEM_REF:
+      {
+	const char *sep = "";
+	tree tmp;
+
+	pp_string (buffer, "MEM[");
+
+	tmp = TMR_SYMBOL (node);
+	if (tmp)
+	  {
+	    pp_string (buffer, sep);
+	    sep = ", ";
+	    pp_string (buffer, "symbol: ");
+	    dump_generic_node (buffer, tmp, spc, flags, false);
+	  }
+	tmp = TMR_BASE (node);
+	if (tmp)
+	  {
+	    pp_string (buffer, sep);
+	    sep = ", ";
+	    pp_string (buffer, "base: ");
+	    dump_generic_node (buffer, tmp, spc, flags, false);
+	  }
+	tmp = TMR_INDEX (node);
+	if (tmp)
+	  {
+	    pp_string (buffer, sep);
+	    sep = ", ";
+	    pp_string (buffer, "index: ");
+	    dump_generic_node (buffer, tmp, spc, flags, false);
+	  }
+	tmp = TMR_STEP (node);
+	if (tmp)
+	  {
+	    pp_string (buffer, sep);
+	    sep = ", ";
+	    pp_string (buffer, "step: ");
+	    dump_generic_node (buffer, tmp, spc, flags, false);
+	  }
+	tmp = TMR_OFFSET (node);
+	if (tmp)
+	  {
+	    pp_string (buffer, sep);
+	    sep = ", ";
+	    pp_string (buffer, "offset: ");
+	    dump_generic_node (buffer, tmp, spc, flags, false);
+	  }
+	pp_string (buffer, "]");
+	if (flags & TDF_DETAILS)
+	  {
+	    pp_string (buffer, "{");
+	    dump_generic_node (buffer, TMR_ORIGINAL (node), spc, flags,
+			       false);
+	    pp_string (buffer, "}");
+	  }
+      }
+      break;
+
     case ARRAY_TYPE:
       {
 	tree tmp;
diff --git a/gcc/tree-ssa-address.c b/gcc/tree-ssa-address.c
new file mode 100644
index 00000000000..0fdaba07024
--- /dev/null
+++ b/gcc/tree-ssa-address.c
@@ -0,0 +1,707 @@
+/* Memory address lowering and addressing mode selection.
+   Copyright (C) 2004 Free Software Foundation, Inc.
+   
+This file is part of GCC.
+   
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+   
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+   
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+/* Utility functions for manipulation with TARGET_MEM_REFs -- tree expressions
+   that directly map to addressing modes of the target.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "tree-pass.h"
+#include "timevar.h"
+#include "flags.h"
+#include "tree-inline.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "expr.h"
+#include "ggc.h"
+
+/* TODO -- handling of symbols (according to Richard Hendersons
+   comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
+   
+   There are at least 5 different kinds of symbols that we can run up against:
+
+     (1) binds_local_p, small data area.
+     (2) binds_local_p, eg local statics
+     (3) !binds_local_p, eg global variables
+     (4) thread local, local_exec
+     (5) thread local, !local_exec
+
+   Now, (1) won't appear often in an array context, but it certainly can.
+   All you have to do is set -GN high enough, or explicitly mark any
+   random object __attribute__((section (".sdata"))).
+
+   All of these affect whether or not a symbol is in fact a valid address.
+   The only one tested here is (3).  And that result may very well
+   be incorrect for (4) or (5).
+
+   An incorrect result here does not cause incorrect results out the
+   back end, because the expander in expr.c validizes the address.  However
+   it would be nice to improve the handling here in order to produce more
+   precise results.  */
+
+/* A "template" for memory address, used to determine whether the address is
+   valid for mode.  */
+
+struct mem_addr_template GTY (())
+{
+  rtx ref;			/* The template.  */
+  rtx * GTY ((skip)) step_p;	/* The point in template where the step should be
+				   filled in.  */
+  rtx * GTY ((skip)) off_p;	/* The point in template where the offset should
+				   be filled in.  */
+};
+
+/* The templates.  Each of the five bits of the index corresponds to one
+   component of TARGET_MEM_REF being present, see TEMPL_IDX.  */
+
+static GTY (()) struct mem_addr_template templates[32];
+
+#define TEMPL_IDX(SYMBOL, BASE, INDEX, STEP, OFFSET) \
+  (((SYMBOL != 0) << 4) \
+   | ((BASE != 0) << 3) \
+   | ((INDEX != 0) << 2) \
+   | ((STEP != 0) << 1) \
+   | (OFFSET != 0))
+
+/* Stores address for memory reference with parameters SYMBOL, BASE, INDEX,
+   STEP and OFFSET to *ADDR.  Stores pointers to where step is placed to
+   *STEP_P and offset to *OFFSET_P.  */
+
+static void
+gen_addr_rtx (rtx symbol, rtx base, rtx index, rtx step, rtx offset,
+	      rtx *addr, rtx **step_p, rtx **offset_p)
+{
+  rtx act_elem;
+
+  *addr = NULL_RTX;
+  if (step_p)
+    *step_p = NULL;
+  if (offset_p)
+    *offset_p = NULL;
+
+  if (index)
+    {
+      act_elem = index;
+      if (step)
+	{
+	  act_elem = gen_rtx_MULT (Pmode, act_elem, step);
+
+	  if (step_p)
+	    *step_p = &XEXP (act_elem, 1);
+	}
+
+      *addr = act_elem;
+    }
+
+  if (base)
+    {
+      if (*addr)
+	*addr = gen_rtx_PLUS (Pmode, *addr, base);
+      else
+	*addr = base;
+    }
+
+  if (symbol)
+    {
+      act_elem = symbol;
+      if (offset)
+	{
+	  act_elem = gen_rtx_CONST (Pmode,
+				    gen_rtx_PLUS (Pmode, act_elem, offset));
+	  if (offset_p)
+	    *offset_p = &XEXP (XEXP (act_elem, 0), 1);
+	}
+
+      if (*addr)
+	*addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
+      else
+	*addr = act_elem;
+    }
+  else if (offset)
+    {
+      if (*addr)
+	{
+	  *addr = gen_rtx_PLUS (Pmode, *addr, offset);
+	  if (offset_p)
+	    *offset_p = &XEXP (*addr, 1);
+	}
+      else
+	{
+	  *addr = offset;
+	  if (offset_p)
+	    *offset_p = addr;
+	}
+    }
+
+  if (!*addr)
+    *addr = const0_rtx;
+}
+
+/* Returns address for TARGET_MEM_REF with parameters given by ADDR.
+   If REALLY_EXPAND is false, just make fake registers instead 
+   of really expanding the operands, and perform the expansion in-place
+   by using one of the "templates".  */
+
+rtx
+addr_for_mem_ref (struct mem_address *addr, bool really_expand)
+{
+  rtx address, sym, bse, idx, st, off;
+  static bool templates_initialized = false;
+  struct mem_addr_template *templ;
+
+  if (addr->step && !integer_onep (addr->step))
+    st = immed_double_const (TREE_INT_CST_LOW (addr->step),
+			     TREE_INT_CST_HIGH (addr->step), Pmode);
+  else
+    st = NULL_RTX;
+
+  if (addr->offset && !integer_zerop (addr->offset))
+    off = immed_double_const (TREE_INT_CST_LOW (addr->offset),
+			      TREE_INT_CST_HIGH (addr->offset), Pmode);
+  else
+    off = NULL_RTX;
+
+  if (!really_expand)
+    {
+      /* Reuse the templates for addresses, so that we do not waste memory.  */
+      if (!templates_initialized)
+	{
+	  unsigned i;
+
+	  templates_initialized = true;
+	  sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup ("test_symbol"));
+	  bse = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
+	  idx = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 1);
+
+	  for (i = 0; i < 32; i++)
+	    gen_addr_rtx ((i & 16 ? sym : NULL_RTX),
+			  (i & 8 ? bse : NULL_RTX),
+			  (i & 4 ? idx : NULL_RTX),
+			  (i & 2 ? const0_rtx : NULL_RTX),
+			  (i & 1 ? const0_rtx : NULL_RTX),
+			  &templates[i].ref,
+			  &templates[i].step_p,
+			  &templates[i].off_p);
+	}
+
+      templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
+				     st, off);
+      if (st)
+	*templ->step_p = st;
+      if (off)
+	*templ->off_p = off;
+
+      return templ->ref;
+    }
+
+  /* Otherwise really expand the expressions.  */
+  sym = (addr->symbol
+	 ? expand_expr (build_addr (addr->symbol, current_function_decl),
+			NULL_RTX, Pmode, EXPAND_NORMAL)
+	 : NULL_RTX);
+  bse = (addr->base
+	 ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
+	 : NULL_RTX);
+  idx = (addr->index
+	 ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
+	 : NULL_RTX);
+
+  gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
+  return address;
+}
+
+/* Returns address of MEM_REF in TYPE.  */
+
+tree
+tree_mem_ref_addr (tree type, tree mem_ref)
+{
+  tree addr = NULL_TREE;
+  tree act_elem;
+  tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
+
+  act_elem = TMR_INDEX (mem_ref);
+  if (act_elem)
+    {
+      act_elem = fold_convert (type, act_elem);
+
+      if (step)
+	act_elem = fold_build2 (MULT_EXPR, type, act_elem,
+				fold_convert (type, step));
+      addr = act_elem;
+    }
+
+  act_elem = TMR_BASE (mem_ref);
+  if (act_elem)
+    {
+      act_elem = fold_convert (type, act_elem);
+
+      if (addr)
+	addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
+      else
+	addr = act_elem;
+    }
+
+  act_elem = TMR_SYMBOL (mem_ref);
+  if (act_elem)
+    {
+      act_elem = fold_convert (type, build_addr (act_elem,
+						 current_function_decl));
+      if (addr)
+	addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
+      else
+	addr = act_elem;
+    }
+
+  if (!zero_p (offset))
+    {
+      act_elem = fold_convert (type, offset);
+
+      if (addr)
+	addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
+      else
+	addr = act_elem;
+    }
+
+  if (!addr)
+    addr = build_int_cst (type, 0);
+
+  return addr;
+}
+
+/* Returns true if a memory reference in MODE and with parameters given by
+   ADDR is valid on the current target.  */
+
+static bool
+valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
+{
+  rtx address;
+
+  address = addr_for_mem_ref (addr, false);
+  if (!address)
+    return false;
+
+  return memory_address_p (mode, address);
+}
+
+/* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
+   is valid on the current target and if so, creates and returns the
+   TARGET_MEM_REF.  */
+
+static tree
+create_mem_ref_raw (tree type, struct mem_address *addr)
+{
+  if (!valid_mem_ref_p (TYPE_MODE (type), addr))
+    return NULL_TREE;
+
+  if (addr->step && integer_onep (addr->step))
+    addr->step = NULL_TREE;
+
+  if (addr->offset && zero_p (addr->offset))
+    addr->offset = NULL_TREE;
+
+  return build7 (TARGET_MEM_REF, type,
+		 addr->symbol, addr->base, addr->index,
+		 addr->step, addr->offset, NULL, NULL);
+}
+
+/* Returns true if OBJ is an object whose address is a link time constant.  */
+
+static bool
+fixed_address_object_p (tree obj)
+{
+  return (TREE_CODE (obj) == VAR_DECL
+	  && (TREE_STATIC (obj)
+	      || DECL_EXTERNAL (obj)));
+}
+
+/* Adds COEF * ELT to PARTS.  TYPE is the type of the address we
+   construct.  */
+
+static void
+add_to_parts (struct mem_address *parts, tree type, tree elt,
+	      unsigned HOST_WIDE_INT coef)
+{
+  /* Check if this is a symbol.  */
+  if (!parts->symbol
+      && coef == 1
+      && TREE_CODE (elt) == ADDR_EXPR
+      && fixed_address_object_p (TREE_OPERAND (elt, 0)))
+    {
+      parts->symbol = TREE_OPERAND (elt, 0);
+      return;
+    }
+
+  if (coef != 1)
+    elt = fold_build2 (MULT_EXPR, type, fold_convert (type, elt),
+		       build_int_cst_type (type, coef));
+  else
+    elt = fold_convert (type, elt);
+
+  if (!parts->base)
+    {
+      parts->base = elt;
+      return;
+    }
+
+  if (!parts->index)
+    {
+      parts->index = elt;
+      return;
+    }
+
+  /* Add ELT to base.  */
+  parts->base = fold_build2 (PLUS_EXPR, type, parts->base, elt);
+}
+
+/* Finds the most expensive multiplication in ADDR that can be
+   expressed in an addressing mode and move the corresponding
+   element(s) to PARTS.  TYPE is the type of the address we
+   construct.  */
+
+static void
+most_expensive_mult_to_index (struct mem_address *parts, tree type,
+			      struct affine_tree_combination *addr)
+{
+  unsigned HOST_WIDE_INT best_mult = 0;
+  unsigned best_mult_cost = 0, acost;
+  tree mult_elt = NULL_TREE, elt;
+  unsigned i, j;
+
+  for (i = 0; i < addr->n; i++)
+    {
+      if (addr->coefs[i] == 1
+	  || !multiplier_allowed_in_address_p (addr->coefs[i]))
+	continue;
+      
+      acost = multiply_by_cost (addr->coefs[i], Pmode);
+
+      if (acost > best_mult_cost)
+	{
+	  best_mult_cost = acost;
+	  best_mult = addr->coefs[i];
+	}
+    }
+
+  if (!best_mult)
+    return;
+
+  for (i = j = 0; i < addr->n; i++)
+    {
+      if (addr->coefs[i] != best_mult)
+	{
+	  addr->coefs[j] = addr->coefs[i];
+	  addr->elts[j] = addr->elts[i];
+	  j++;
+	  continue;
+	}
+
+      elt = fold_convert (type, addr->elts[i]);
+      if (!mult_elt)
+	mult_elt = elt;
+      else
+	mult_elt = fold_build2 (PLUS_EXPR, type, mult_elt, elt);
+    }
+  addr->n = j;
+
+  parts->index = mult_elt;
+  parts->step = build_int_cst_type (type, best_mult);
+}
+
+/* Splits address ADDR into PARTS.
+   
+   TODO -- be more clever about the distribution of the elements of ADDR
+   to PARTS.  Some architectures do not support anything but single
+   register in address, possibly with a small integer offset; while
+   create_mem_ref will simplify the address to an acceptable shape
+   later, it would be a small bit more efficient to know that asking
+   for complicated addressing modes is useless.  */
+
+static void
+addr_to_parts (struct affine_tree_combination *addr, tree type,
+	       struct mem_address *parts)
+{
+  unsigned i;
+
+  parts->symbol = NULL_TREE;
+  parts->base = NULL_TREE;
+  parts->index = NULL_TREE;
+  parts->step = NULL_TREE;
+
+  if (addr->offset)
+    parts->offset = build_int_cst_type (type, addr->offset);
+  else
+    parts->offset = NULL_TREE;
+
+  /* First move the most expensive feasible multiplication
+     to index.  */
+  most_expensive_mult_to_index (parts, type, addr);
+
+  /* Then try to process the remaining elements.  */
+  for (i = 0; i < addr->n; i++)
+    add_to_parts (parts, type, addr->elts[i], addr->coefs[i]);
+  if (addr->rest)
+    add_to_parts (parts, type, addr->rest, 1);
+}
+
+/* Force the PARTS to register.  */
+
+static void
+gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
+{
+  if (parts->base)
+    parts->base = force_gimple_operand_bsi (bsi, parts->base,
+					    true, NULL_TREE);
+  if (parts->index)
+    parts->index = force_gimple_operand_bsi (bsi, parts->index,
+					     true, NULL_TREE);
+}
+
+/* Creates and returns a TARGET_MEM_REF for address ADDR.  If necessary
+   computations are emitted in front of BSI.  TYPE is the mode
+   of created memory reference.  */
+
+tree
+create_mem_ref (block_stmt_iterator *bsi, tree type,
+		struct affine_tree_combination *addr)
+{
+  tree mem_ref, tmp;
+  tree addr_type = build_pointer_type (type);
+  struct mem_address parts;
+
+  addr_to_parts (addr, addr_type, &parts);
+  gimplify_mem_ref_parts (bsi, &parts);
+  mem_ref = create_mem_ref_raw (type, &parts);
+  if (mem_ref)
+    return mem_ref;
+
+  /* The expression is too complicated.  Try making it simpler.  */
+
+  if (parts.step && !integer_onep (parts.step))
+    {
+      /* Move the multiplication to index.  */
+      gcc_assert (parts.index);
+      parts.index = force_gimple_operand_bsi (bsi,
+					      build2 (MULT_EXPR, addr_type,
+						      parts.index, parts.step),
+					      true, NULL_TREE);
+      parts.step = NULL_TREE;
+  
+      mem_ref = create_mem_ref_raw (type, &parts);
+      if (mem_ref)
+	return mem_ref;
+    }
+
+  if (parts.symbol)
+    {
+      tmp = build_addr (parts.symbol, current_function_decl);
+    
+      /* Add the symbol to base, eventually forcing it to register.  */
+      if (parts.base)
+	parts.base = force_gimple_operand_bsi (bsi,
+					       build2 (PLUS_EXPR, addr_type,
+						       parts.base, tmp),
+					       true, NULL_TREE);
+      else
+	parts.base = tmp;
+      parts.symbol = NULL_TREE;
+
+      mem_ref = create_mem_ref_raw (type, &parts);
+      if (mem_ref)
+	return mem_ref;
+    }
+
+  if (parts.base)
+    {
+      /* Add base to index.  */
+      if (parts.index)
+	parts.index = force_gimple_operand_bsi (bsi,
+						build2 (PLUS_EXPR, addr_type,
+							parts.base,
+							parts.index),
+						true, NULL_TREE);
+      else
+	parts.index = parts.base;
+      parts.base = NULL_TREE;
+
+      mem_ref = create_mem_ref_raw (type, &parts);
+      if (mem_ref)
+	return mem_ref;
+    }
+
+  if (parts.offset && !integer_zerop (parts.offset))
+    {
+      /* Try adding offset to index.  */
+      if (parts.index)
+	parts.index = force_gimple_operand_bsi (bsi, 
+						build2 (PLUS_EXPR, addr_type,
+							parts.index,
+							parts.offset),
+						true, NULL_TREE);
+      else
+	parts.index = parts.offset, bsi;
+
+      parts.offset = NULL_TREE;
+
+      mem_ref = create_mem_ref_raw (type, &parts);
+      if (mem_ref)
+	return mem_ref;
+    }
+
+  /* Verify that the address is in the simplest possible shape
+     (only a register).  If we cannot create such a memory reference,
+     something is really wrong.  */
+  gcc_assert (parts.symbol == NULL_TREE);
+  gcc_assert (parts.base == NULL_TREE);
+  gcc_assert (!parts.step || integer_onep (parts.step));
+  gcc_assert (!parts.offset || integer_zerop (parts.offset));
+  gcc_unreachable ();
+}
+
+/* Copies components of the address from OP to ADDR.  */
+
+void
+get_address_description (tree op, struct mem_address *addr)
+{
+  addr->symbol = TMR_SYMBOL (op);
+  addr->base = TMR_BASE (op);
+  addr->index = TMR_INDEX (op);
+  addr->step = TMR_STEP (op);
+  addr->offset = TMR_OFFSET (op);
+}
+
+/* Copies the additional information attached to target_mem_ref FROM to TO.  */
+
+void
+copy_mem_ref_info (tree to, tree from)
+{
+  /* Copy the annotation, to preserve the aliasing information.  */
+  TMR_TAG (to) = TMR_TAG (from);
+
+  /* And the info about the original reference.  */
+  TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
+}
+
+/* Move constants in target_mem_ref REF to offset.  Returns the new target
+   mem ref if anything changes, NULL_TREE otherwise.  */
+
+tree
+maybe_fold_tmr (tree ref)
+{
+  struct mem_address addr;
+  bool changed = false;
+  tree ret, off;
+
+  get_address_description (ref, &addr);
+
+  if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
+    {
+      if (addr.offset)
+	addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
+					       addr.offset, addr.base);
+      else
+	addr.offset = addr.base;
+
+      addr.base = NULL_TREE;
+      changed = true;
+    }
+
+  if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
+    {
+      off = addr.index;
+      if (addr.step)
+	{
+	  off = fold_binary_to_constant (MULT_EXPR, ptr_type_node,
+					 off, addr.step);
+	  addr.step = NULL_TREE;
+	}
+
+      if (addr.offset)
+	{
+	  addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
+						 addr.offset, off);
+	}
+      else
+	addr.offset = off;
+
+      addr.index = NULL_TREE;
+      changed = true;
+    }
+
+  if (!changed)
+    return NULL_TREE;
+  
+  ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
+  if (!ret)
+    return NULL_TREE;
+
+  copy_mem_ref_info (ret, ref);
+  return ret;
+}
+
+/* Dump PARTS to FILE.  */
+
+extern void dump_mem_address (FILE *, struct mem_address *);
+void
+dump_mem_address (FILE *file, struct mem_address *parts)
+{
+  if (parts->symbol)
+    {
+      fprintf (file, "symbol: ");
+      print_generic_expr (file, parts->symbol, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  if (parts->base)
+    {
+      fprintf (file, "base: ");
+      print_generic_expr (file, parts->base, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  if (parts->index)
+    {
+      fprintf (file, "index: ");
+      print_generic_expr (file, parts->index, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  if (parts->step)
+    {
+      fprintf (file, "step: ");
+      print_generic_expr (file, parts->step, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  if (parts->offset)
+    {
+      fprintf (file, "offset: ");
+      print_generic_expr (file, parts->offset, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+}
+
+#include "gt-tree-ssa-address.h"
diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
index 3fe8de37261..6816dafd6c1 100644
--- a/gcc/tree-ssa-ccp.c
+++ b/gcc/tree-ssa-ccp.c
@@ -1874,7 +1874,6 @@ maybe_fold_stmt_addition (tree expr)
   return t;
 }
 
-
 /* Subroutine of fold_stmt called via walk_tree.  We perform several
    simplifications of EXPR_P, mostly having to do with pointer arithmetic.  */
 
@@ -1948,6 +1947,10 @@ fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
       }
       break;
 
+    case TARGET_MEM_REF:
+      t = maybe_fold_tmr (expr);
+      break;
+
     default:
       return NULL_TREE;
     }
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index e7acc5cdc05..b7a57f61ede 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -204,6 +204,17 @@ for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 	case VECTOR_CST:
 	  return true;
 
+	case TARGET_MEM_REF:
+	  idx = &TMR_BASE (*addr_p);
+	  if (*idx
+	      && !cbck (*addr_p, idx, data))
+	    return false;
+	  idx = &TMR_INDEX (*addr_p);
+	  if (*idx
+	      && !cbck (*addr_p, idx, data))
+	    return false;
+	  return true;
+
 	default:
     	  gcc_unreachable ();
 	}
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 81bec044c5f..716d113e75e 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -1494,6 +1494,11 @@ may_be_unaligned_p (tree ref)
   int unsignedp, volatilep;
   unsigned base_align;
 
+  /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
+     thus they are not missaligned.  */
+  if (TREE_CODE (ref) == TARGET_MEM_REF)
+    return false;
+
   /* The test below is basically copy of what expr.c:normal_inner_ref
      does to check whether the object must be loaded by parts when
      STRICT_ALIGNMENT is true.  */
@@ -1516,7 +1521,7 @@ may_be_unaligned_p (tree ref)
 static void
 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
 {
-  tree base = unshare_expr (*op_p), step = NULL;
+  tree base = *op_p, step = NULL;
   struct iv *civ;
   struct ifs_ivopts_data ifs_ivopts_data;
 
@@ -1535,17 +1540,63 @@ find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
       && may_be_unaligned_p (base))
     goto fail;
 
-  ifs_ivopts_data.ivopts_data = data;
-  ifs_ivopts_data.stmt = stmt;
-  ifs_ivopts_data.step_p = &step;
-  if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
-      || zero_p (step))
-    goto fail;
+  base = unshare_expr (base);
+
+  if (TREE_CODE (base) == TARGET_MEM_REF)
+    {
+      tree type = build_pointer_type (TREE_TYPE (base));
+      tree astep;
+
+      if (TMR_BASE (base)
+	  && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
+	{
+	  civ = get_iv (data, TMR_BASE (base));
+	  if (!civ)
+	    goto fail;
+
+	  TMR_BASE (base) = civ->base;
+	  step = civ->step;
+	}
+      if (TMR_INDEX (base)
+	  && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
+	{
+	  civ = get_iv (data, TMR_INDEX (base));
+	  if (!civ)
+	    goto fail;
 
-  gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
-  gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+	  TMR_INDEX (base) = civ->base;
+	  astep = civ->step;
 
-  base = build_fold_addr_expr (base);
+	  if (astep)
+	    {
+	      if (TMR_STEP (base))
+		astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
+
+	      if (step)
+		step = fold_build2 (PLUS_EXPR, type, step, astep);
+	      else
+		step = astep;
+	    }
+	}
+
+      if (zero_p (step))
+	goto fail;
+      base = tree_mem_ref_addr (type, base);
+    }
+  else
+    {
+      ifs_ivopts_data.ivopts_data = data;
+      ifs_ivopts_data.stmt = stmt;
+      ifs_ivopts_data.step_p = &step;
+      if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
+	  || zero_p (step))
+	goto fail;
+
+      gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
+      gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+
+      base = build_fold_addr_expr (base);
+    }
 
   civ = alloc_iv (base, step);
   record_use (data, op_p, civ, stmt, USE_ADDRESS);
@@ -2614,33 +2665,6 @@ constant_multiple_of (tree type, tree top, tree bot)
     }
 }
 
-/* Affine combination of trees.  We keep track of at most MAX_AFF_ELTS elements
-   to make things simpler; this is sufficient in most cases.  */
-
-#define MAX_AFF_ELTS 8
-
-struct affine_tree_combination
-{
-  /* Type of the result of the combination.  */
-  tree type;
-
-  /* Mask modulo that the operations are performed.  */
-  unsigned HOST_WIDE_INT mask;
-
-  /* Constant offset.  */
-  unsigned HOST_WIDE_INT offset;
-
-  /* Number of elements of the combination.  */
-  unsigned n;
-
-  /* Elements and their coefficients.  */
-  tree elts[MAX_AFF_ELTS];
-  unsigned HOST_WIDE_INT coefs[MAX_AFF_ELTS];
-
-  /* Remainder of the expression.  */
-  tree rest;
-};
-
 /* Sets COMB to CST.  */
 
 static void
@@ -2893,6 +2917,19 @@ add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
   return fold_build2 (code, type, expr, elt);
 }
 
+/* Copies the tree elements of COMB to ensure that they are not shared.  */
+
+static void
+unshare_aff_combination (struct affine_tree_combination *comb)
+{
+  unsigned i;
+
+  for (i = 0; i < comb->n; i++)
+    comb->elts[i] = unshare_expr (comb->elts[i]);
+  if (comb->rest)
+    comb->rest = unshare_expr (comb->rest);
+}
+
 /* Makes tree from the affine combination COMB.  */
 
 static tree
@@ -2903,6 +2940,11 @@ aff_combination_to_tree (struct affine_tree_combination *comb)
   unsigned i;
   unsigned HOST_WIDE_INT off, sgn;
 
+  /* Handle the special case produced by get_computation_aff when
+     the type does not fit in HOST_WIDE_INT.  */
+  if (comb->n == 0 && comb->offset == 0)
+    return fold_convert (type, expr);
+
   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
 
   for (i = 0; i < comb->n; i++)
@@ -2924,49 +2966,14 @@ aff_combination_to_tree (struct affine_tree_combination *comb)
 			  comb->mask);
 }
 
-/* Folds X + RATIO * Y in TYPE.  */
-
-static tree
-fold_affine_sum (tree type, tree x, tree y, HOST_WIDE_INT ratio)
-{
-  enum tree_code code;
-  tree cst;
-  struct affine_tree_combination cx, cy;
-
-  if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT)
-    {
-      if (ratio == 1)
-	return fold_build2 (PLUS_EXPR, type, x, y);
-      if (ratio == -1)
-	return fold_build2 (MINUS_EXPR, type, x, y);
-
-      if (ratio < 0)
-	{
-	  code = MINUS_EXPR;
-	  ratio = -ratio;
-	}
-      else
-	code = PLUS_EXPR;
-
-      cst = build_int_cst_type (type, ratio);
-      y = fold_build2 (MULT_EXPR, type, y, cst);
-      return fold_build2 (code, type, x, y);
-    }
-
-  tree_to_aff_combination (x, type, &cx);
-  tree_to_aff_combination (y, type, &cy);
-  aff_combination_scale (&cy, ratio);
-  aff_combination_add (&cx, &cy);
-
-  return aff_combination_to_tree (&cx);
-}
-
 /* Determines the expression by that USE is expressed from induction variable
-   CAND at statement AT in LOOP.  */
+   CAND at statement AT in LOOP.  The expression is stored in a decomposed
+   form into AFF.  Returns false if USE cannot be expressed using CAND.  */
 
-static tree
-get_computation_at (struct loop *loop,
-		    struct iv_use *use, struct iv_cand *cand, tree at)
+static bool
+get_computation_aff (struct loop *loop,
+		     struct iv_use *use, struct iv_cand *cand, tree at,
+		     struct affine_tree_combination *aff)
 {
   tree ubase = use->iv->base;
   tree ustep = use->iv->step;
@@ -2978,11 +2985,12 @@ get_computation_at (struct loop *loop,
   tree ratio;
   unsigned HOST_WIDE_INT ustepi, cstepi;
   HOST_WIDE_INT ratioi;
+  struct affine_tree_combination cbase_aff, expr_aff;
 
   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
     {
       /* We do not have a precision to express the values of use.  */
-      return NULL_TREE;
+      return false;
     }
 
   expr = var_at_stmt (loop, cand, at);
@@ -3020,7 +3028,7 @@ get_computation_at (struct loop *loop,
 	  /* TODO maybe consider case when ustep divides cstep and the ratio is
 	     a power of 2 (so that the division is fast to execute)?  We would
 	     need to be much more careful with overflows etc. then.  */
-	  return NULL_TREE;
+	  return false;
 	}
 
       ratio = build_int_cst_type (uutype, ratioi);
@@ -3029,7 +3037,7 @@ get_computation_at (struct loop *loop,
     {
       ratio = constant_multiple_of (uutype, ustep, cstep);
       if (!ratio)
-	return NULL_TREE;
+	return false;
 
       /* Ratioi is only used to detect special cases when the multiplicative
 	 factor is 1 or -1, so if we cannot convert ratio to HOST_WIDE_INT,
@@ -3058,34 +3066,71 @@ get_computation_at (struct loop *loop,
      happen, fold is able to apply the distributive law to obtain this form
      anyway.  */
 
-  if (ratioi == 1)
+  if (TYPE_PRECISION (uutype) > HOST_BITS_PER_WIDE_INT)
     {
-      delta = fold_affine_sum (uutype, ubase, cbase, -1);
-      expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
-    }
-  else if (ratioi == -1)
-    {
-      delta = fold_affine_sum (uutype, ubase, cbase, 1);
-      expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
-    }
-  else
-    {
-      if (ratioi)
-	delta = fold_affine_sum (uutype, ubase, cbase, -ratioi);
+      /* Let's compute in trees and just return the result in AFF.  This case
+	 should not be very common, and fold itself is not that bad either,
+	 so making the aff. functions more complicated to handle this case
+	 is not that urgent.  */
+      if (ratioi == 1)
+	{
+	  delta = fold_build2 (MINUS_EXPR, uutype, ubase, cbase);
+	  expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
+	}
+      else if (ratioi == -1)
+	{
+	  delta = fold_build2 (PLUS_EXPR, uutype, ubase, cbase);
+	  expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
+	}
       else
 	{
-	  delta = fold_build2 (MULT_EXPR, uutype, ratio, cbase);
-	  delta = fold_affine_sum (uutype, ubase, delta, -1);
+	  delta = fold_build2 (MULT_EXPR, uutype, cbase, ratio);
+	  delta = fold_build2 (MINUS_EXPR, uutype, ubase, delta);
+	  expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
+	  expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
 	}
-      expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
-      expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
+
+      aff->type = uutype;
+      aff->n = 0;
+      aff->offset = 0;
+      aff->mask = 0;
+      aff->rest = expr;
+      return true;
     }
 
-  return fold_convert (utype, expr);
+  /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
+     possible to compute ratioi.  */
+  gcc_assert (ratioi);
+
+  tree_to_aff_combination (ubase, uutype, aff);
+  tree_to_aff_combination (cbase, uutype, &cbase_aff);
+  tree_to_aff_combination (expr, uutype, &expr_aff);
+  aff_combination_scale (&cbase_aff, -ratioi);
+  aff_combination_scale (&expr_aff, ratioi);
+  aff_combination_add (aff, &cbase_aff);
+  aff_combination_add (aff, &expr_aff);
+
+  return true;
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+   CAND at statement AT in LOOP.  The computation is unshared.  */
+
+static tree
+get_computation_at (struct loop *loop,
+		    struct iv_use *use, struct iv_cand *cand, tree at)
+{
+  struct affine_tree_combination aff;
+  tree type = TREE_TYPE (use->iv->base);
+
+  if (!get_computation_aff (loop, use, cand, at, &aff))
+    return NULL_TREE;
+  unshare_aff_combination (&aff);
+  return fold_convert (type, aff_combination_to_tree (&aff));
 }
 
 /* Determines the expression by that USE is expressed from induction variable
-   CAND in LOOP.  */
+   CAND in LOOP.  The computation is unshared.  */
 
 static tree
 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
@@ -3157,7 +3202,7 @@ mbc_entry_eq (const void *entry1, const void *entry2)
 
 /* Returns cost of multiplication by constant CST in MODE.  */
 
-static unsigned
+unsigned
 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
 {
   static htab_t costs;
@@ -3195,6 +3240,47 @@ multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
   return cost;
 }
 
+/* Returns true if multiplying by RATIO is allowed in address.  */
+
+bool
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
+{
+#define MAX_RATIO 128
+  static sbitmap valid_mult;
+  
+  if (!valid_mult)
+    {
+      rtx reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
+      rtx addr;
+      HOST_WIDE_INT i;
+
+      valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
+      sbitmap_zero (valid_mult);
+      addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
+      for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
+	{
+	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
+	  if (memory_address_p (Pmode, addr))
+	    SET_BIT (valid_mult, i + MAX_RATIO);
+	}
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "  allowed multipliers:");
+	  for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
+	    if (TEST_BIT (valid_mult, i + MAX_RATIO))
+	      fprintf (dump_file, " %d", (int) i);
+	  fprintf (dump_file, "\n");
+	  fprintf (dump_file, "\n");
+	}
+    }
+
+  if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
+    return false;
+
+  return TEST_BIT (valid_mult, ratio + MAX_RATIO);
+}
+
 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
    If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
    variable is omitted.  The created memory accesses MODE.
@@ -3205,8 +3291,7 @@ static unsigned
 get_address_cost (bool symbol_present, bool var_present,
 		  unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
 {
-#define MAX_RATIO 128
-  static sbitmap valid_mult;
+  static bool initialized = false;
   static HOST_WIDE_INT rat, off;
   static HOST_WIDE_INT min_offset, max_offset;
   static unsigned costs[2][2][2][2];
@@ -3218,9 +3303,10 @@ get_address_cost (bool symbol_present, bool var_present,
   unsigned HOST_WIDE_INT mask;
   unsigned bits;
 
-  if (!valid_mult)
+  if (!initialized)
     {
       HOST_WIDE_INT i;
+      initialized = true;
 
       reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
 
@@ -3249,29 +3335,13 @@ get_address_cost (bool symbol_present, bool var_present,
 	  fprintf (dump_file, "  max offset %d\n", (int) max_offset);
 	}
 
-      valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
-      sbitmap_zero (valid_mult);
       rat = 1;
-      addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
-      for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
-	{
-	  XEXP (addr, 1) = GEN_INT (i);
-	  if (memory_address_p (Pmode, addr))
-	    {
-	      SET_BIT (valid_mult, i + MAX_RATIO);
-	      rat = i;
-	    }
-	}
-
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "  allowed multipliers:");
-	  for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
-	    if (TEST_BIT (valid_mult, i + MAX_RATIO))
-	      fprintf (dump_file, " %d", (int) i);
-	  fprintf (dump_file, "\n");
-	  fprintf (dump_file, "\n");
-	}
+      for (i = 2; i <= MAX_RATIO; i++)
+	if (multiplier_allowed_in_address_p (i))
+	  {
+	    rat = i;
+	    break;
+	  }
     }
 
   bits = GET_MODE_BITSIZE (Pmode);
@@ -3285,8 +3355,7 @@ get_address_cost (bool symbol_present, bool var_present,
   offset_p = (s_offset != 0
 	      && min_offset <= s_offset && s_offset <= max_offset);
   ratio_p = (ratio != 1
-	     && -MAX_RATIO <= ratio && ratio <= MAX_RATIO
-	     && TEST_BIT (valid_mult, ratio + MAX_RATIO));
+	     && multiplier_allowed_in_address_p (ratio));
 
   if (ratio != 1 && !ratio_p)
     cost += multiply_by_cost (ratio, Pmode);
@@ -5262,8 +5331,7 @@ rewrite_use_nonlinear_expr (struct ivopts_data *data,
 	return;
     }
 
-  comp = unshare_expr (get_computation (data->current_loop,
-					use, cand));
+  comp = get_computation (data->current_loop, use, cand);
   switch (TREE_CODE (use->stmt))
     {
     case PHI_NODE:
@@ -5348,78 +5416,60 @@ unshare_and_remove_ssa_names (tree ref)
   return ref;
 }
 
-/* Rewrites base of memory access OP with expression WITH in statement
-   pointed to by BSI.  */
+/* Extract the alias analysis info for the memory reference REF.  There are
+   several ways how this information may be stored and what precisely is
+   its semantics depending on the type of the reference, but there always is
+   somewhere hidden one _DECL node that is used to determine the set of
+   virtual operands for the reference.  The code below deciphers this jungle
+   and extracts this single useful piece of information.  */
 
-static void
-rewrite_address_base (block_stmt_iterator *bsi, tree *op, tree with)
+static tree
+get_ref_tag (tree ref)
 {
-  tree bvar, var, new_name, copy, name;
-  tree orig;
-
-  var = bvar = get_base_address (*op);
+  tree var = get_base_address (ref);
+  tree tag;
 
-  if (!var || TREE_CODE (with) != SSA_NAME)
-    goto do_rewrite;
+  if (!var)
+    return NULL_TREE;
 
-  gcc_assert (TREE_CODE (var) != ALIGN_INDIRECT_REF);
-  gcc_assert (TREE_CODE (var) != MISALIGNED_INDIRECT_REF);
   if (TREE_CODE (var) == INDIRECT_REF)
     var = TREE_OPERAND (var, 0);
   if (TREE_CODE (var) == SSA_NAME)
     {
-      name = var;
+      if (SSA_NAME_PTR_INFO (var))
+	{
+	  tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
+	  if (tag)
+	    return tag;
+	}
+ 
       var = SSA_NAME_VAR (var);
     }
-  else if (DECL_P (var))
-    name = NULL_TREE;
-  else
-    goto do_rewrite;
-    
-  /* We need to add a memory tag for the variable.  But we do not want
-     to add it to the temporary used for the computations, since this leads
-     to problems in redundancy elimination when there are common parts
-     in two computations referring to the different arrays.  So we copy
-     the variable to a new temporary.  */
-  copy = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, with);
-
-  if (name)
-    new_name = duplicate_ssa_name (name, copy);
-  else
+ 
+  if (DECL_P (var))
     {
-      tree tag = var_ann (var)->type_mem_tag;
-      tree new_ptr = create_tmp_var (TREE_TYPE (with), "ruatmp");
-      add_referenced_tmp_var (new_ptr);
+      tag = var_ann (var)->type_mem_tag;
       if (tag)
-	var_ann (new_ptr)->type_mem_tag = tag;
-      else
-	add_type_alias (new_ptr, var);
-      new_name = make_ssa_name (new_ptr, copy);
-    }
-
-  TREE_OPERAND (copy, 0) = new_name;
-  bsi_insert_before (bsi, copy, BSI_SAME_STMT);
-  with = new_name;
+	return tag;
 
-do_rewrite:
-
-  orig = NULL_TREE;
-  gcc_assert (TREE_CODE (*op) != ALIGN_INDIRECT_REF);
-  gcc_assert (TREE_CODE (*op) != MISALIGNED_INDIRECT_REF);
-
-  if (TREE_CODE (*op) == INDIRECT_REF)
-    orig = REF_ORIGINAL (*op);
-  if (!orig)
-    orig = unshare_and_remove_ssa_names (*op);
+      return var;
+    }
 
-  *op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
+  return NULL_TREE;
+}
 
-  /* Record the original reference, for purposes of alias analysis.  */
-  REF_ORIGINAL (*op) = orig;
+/* Copies the reference information from OLD_REF to NEW_REF.  */
 
-  /* Virtual operands in the original statement may have to be renamed
-     because of the replacement.  */
-  mark_new_vars_to_rename (bsi_stmt (*bsi));
+static void
+copy_ref_info (tree new_ref, tree old_ref)
+{
+  if (TREE_CODE (old_ref) == TARGET_MEM_REF)
+    copy_mem_ref_info (new_ref, old_ref);
+  else
+    {
+      TMR_TAG (new_ref) = get_ref_tag (old_ref);
+      TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
+    }
 }
 
 /* Rewrites USE (address that is an iv) using candidate CAND.  */
@@ -5428,16 +5478,16 @@ static void
 rewrite_use_address (struct ivopts_data *data,
 		     struct iv_use *use, struct iv_cand *cand)
 {
-  tree comp = unshare_expr (get_computation (data->current_loop,
-					     use, cand));
+  struct affine_tree_combination aff;
   block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
-  tree stmts;
-  tree op = force_gimple_operand (comp, &stmts, true, NULL_TREE);
+  tree ref;
 
-  if (stmts)
-    bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+  get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+  unshare_aff_combination (&aff);
 
-  rewrite_address_base (&bsi, use->op_p, op);
+  ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
+  copy_ref_info (ref, *use->op_p);
+  *use->op_p = ref;
 }
 
 /* Rewrites USE (the condition such that one of the arguments is an iv) using
@@ -5474,7 +5524,7 @@ rewrite_use_compare (struct ivopts_data *data,
 
   /* The induction variable elimination failed; just express the original
      giv.  */
-  comp = unshare_expr (get_computation (data->current_loop, use, cand));
+  comp = get_computation (data->current_loop, use, cand);
 
   cond = *use->op_p;
   op_p = &TREE_OPERAND (cond, 0);
@@ -5630,7 +5680,6 @@ rewrite_use_outer (struct ivopts_data *data,
 	value = get_computation_at (data->current_loop,
 				    use, cand, last_stmt (exit->src));
 
-      value = unshare_expr (value);
       op = force_gimple_operand (value, &stmts, true, SSA_NAME_VAR (tgt));
 	  
       /* If we will preserve the iv anyway and we would need to perform
@@ -5935,25 +5984,5 @@ tree_ssa_iv_optimize (struct loops *loops)
 	loop = loop->outer;
     }
 
-  /* FIXME.  IV opts introduces new aliases and call-clobbered
-     variables, which need to be renamed.  However, when we call the
-     renamer, not all statements will be scanned for operands.  In
-     particular, the newly introduced aliases may appear in statements
-     that are considered "unmodified", so the renamer will not get a
-     chance to rename those operands.
-
-     Work around this problem by forcing an operand re-scan on every
-     statement.  This will not be necessary once the new operand
-     scanner is implemented.  */
-  if (need_ssa_update_p ())
-    {
-      basic_block bb;
-      block_stmt_iterator si;
-      FOR_EACH_BB (bb)
-	for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
-	  update_stmt (bsi_stmt (si));
-    }
-
-  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
   tree_ssa_iv_optimize_finalize (loops, &data);
 }
diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c
index 83ec21b9497..12bfc780bd3 100644
--- a/gcc/tree-ssa-operands.c
+++ b/gcc/tree-ssa-operands.c
@@ -152,6 +152,7 @@ static void note_addressable (tree, stmt_ann_t);
 static void get_expr_operands (tree, tree *, int);
 static void get_asm_expr_operands (tree);
 static void get_indirect_ref_operands (tree, tree, int);
+static void get_tmr_operands (tree, tree, int);
 static void get_call_expr_operands (tree, tree);
 static inline void append_def (tree *);
 static inline void append_use (tree *);
@@ -1289,6 +1290,10 @@ get_expr_operands (tree stmt, tree *expr_p, int flags)
       get_indirect_ref_operands (stmt, expr, flags);
       return;
 
+    case TARGET_MEM_REF:
+      get_tmr_operands (stmt, expr, flags);
+      return;
+
     case ARRAY_REF:
     case ARRAY_RANGE_REF:
       /* Treat array references as references to the virtual variable
@@ -1672,6 +1677,30 @@ get_indirect_ref_operands (tree stmt, tree expr, int flags)
   get_expr_operands (stmt, pptr, opf_none);
 }
 
+/* A subroutine of get_expr_operands to handle TARGET_MEM_REF.  */
+
+static void
+get_tmr_operands (tree stmt, tree expr, int flags)
+{
+  tree tag = TMR_TAG (expr);
+
+  /* First record the real operands.  */
+  get_expr_operands (stmt, &TMR_BASE (expr), opf_none);
+  get_expr_operands (stmt, &TMR_INDEX (expr), opf_none);
+
+  /* MEM_REFs should never be killing.  */
+  flags &= ~opf_kill_def;
+
+  if (TMR_SYMBOL (expr))
+    note_addressable (TMR_SYMBOL (expr), stmt_ann (stmt));
+
+  if (tag)
+    add_stmt_operand (&tag, stmt_ann (stmt), flags);
+  else
+    /* Something weird, so ensure that we will be careful.  */
+    stmt_ann (stmt)->has_volatile_ops = true;
+}
+
 /* A subroutine of get_expr_operands to handle CALL_EXPR.  */
 
 static void
diff --git a/gcc/tree.c b/gcc/tree.c
index fc0bf99552f..15488fbc860 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -2739,12 +2739,41 @@ build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
   return t;
 }
 
+tree
+build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
+	     tree arg2, tree arg3, tree arg4, tree arg5,
+	     tree arg6 MEM_STAT_DECL)
+{
+  bool constant, read_only, side_effects, invariant;
+  tree t;
+
+  gcc_assert (code == TARGET_MEM_REF);
+
+  t = make_node_stat (code PASS_MEM_STAT);
+  TREE_TYPE (t) = tt;
+
+  side_effects = TREE_SIDE_EFFECTS (t);
+
+  PROCESS_ARG(0);
+  PROCESS_ARG(1);
+  PROCESS_ARG(2);
+  PROCESS_ARG(3);
+  PROCESS_ARG(4);
+  PROCESS_ARG(5);
+  PROCESS_ARG(6);
+
+  TREE_SIDE_EFFECTS (t) = side_effects;
+  TREE_THIS_VOLATILE (t) = 0;
+
+  return t;
+}
+
 /* Backup definition for non-gcc build compilers.  */
 
 tree
 (build) (enum tree_code code, tree tt, ...)
 {
-  tree t, arg0, arg1, arg2, arg3;
+  tree t, arg0, arg1, arg2, arg3, arg4, arg5, arg6;
   int length = TREE_CODE_LENGTH (code);
   va_list p;
 
@@ -2776,6 +2805,16 @@ tree
       arg3 = va_arg (p, tree);
       t = build4 (code, tt, arg0, arg1, arg2, arg3);
       break;
+    case 7:
+      arg0 = va_arg (p, tree);
+      arg1 = va_arg (p, tree);
+      arg2 = va_arg (p, tree);
+      arg3 = va_arg (p, tree);
+      arg4 = va_arg (p, tree);
+      arg5 = va_arg (p, tree);
+      arg6 = va_arg (p, tree);
+      t = build7 (code, tt, arg0, arg1, arg2, arg3, arg4, arg5, arg6);
+      break;
     default:
       gcc_unreachable ();
     }
diff --git a/gcc/tree.def b/gcc/tree.def
index 3806f5b0043..b8d5a36daf7 100644
--- a/gcc/tree.def
+++ b/gcc/tree.def
@@ -935,6 +935,18 @@ DEFTREECODE (WITH_SIZE_EXPR, "with_size_expr", tcc_expression, 2)
    generated by the builtin targetm.vectorize.mask_for_load_builtin_decl.  */
 DEFTREECODE (REALIGN_LOAD_EXPR, "realign_load", tcc_expression, 3)
 
+/* Low-level memory addressing.  Operands are SYMBOL (static or global
+   variable), BASE (register), INDEX (register), STEP (integer constant),
+   OFFSET (integer constant).  Corresponding address is
+   SYMBOL + BASE + STEP * INDEX + OFFSET.  Only variations and values valid on
+   the target are allowed.
+   
+   The sixth argument is the reference to the original memory access, which
+   is preserved for the purposes of the RTL alias analysis.  The seventh
+   argument is a tag representing results of the tree level alias analysis.  */
+
+DEFTREECODE (TARGET_MEM_REF, "target_mem_ref", tcc_reference, 7)
+
 /*
 Local variables:
 mode:c
diff --git a/gcc/tree.h b/gcc/tree.h
index fd3e45d6781..0af98babc2d 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1171,10 +1171,6 @@ struct tree_vec GTY(())
 #define TREE_OPERAND(NODE, I) TREE_OPERAND_CHECK (NODE, I)
 #define TREE_COMPLEXITY(NODE) (EXPR_CHECK (NODE)->exp.complexity)
 
-/* In INDIRECT_REF, ALIGN_INDIRECT_REF, MISALIGNED_INDIRECT_REF.  */
-#define REF_ORIGINAL(NODE) TREE_CHAIN (TREE_CHECK3 (NODE, 	\
-	INDIRECT_REF, ALIGN_INDIRECT_REF, MISALIGNED_INDIRECT_REF))
-
 /* In a LOOP_EXPR node.  */
 #define LOOP_EXPR_BODY(NODE) TREE_OPERAND_CHECK_CODE (NODE, LOOP_EXPR, 0)
 
@@ -1240,6 +1236,15 @@ struct tree_vec GTY(())
 #define CASE_HIGH(NODE)         	TREE_OPERAND (CASE_LABEL_EXPR_CHECK (NODE), 1)
 #define CASE_LABEL(NODE)		TREE_OPERAND (CASE_LABEL_EXPR_CHECK (NODE), 2)
 
+/* The operands of a TARGET_MEM_REF.  */
+#define TMR_SYMBOL(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 0))
+#define TMR_BASE(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 1))
+#define TMR_INDEX(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 2))
+#define TMR_STEP(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 3))
+#define TMR_OFFSET(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 4))
+#define TMR_ORIGINAL(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 5))
+#define TMR_TAG(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 6))
+
 /* The operands of a BIND_EXPR.  */
 #define BIND_EXPR_VARS(NODE) (TREE_OPERAND (BIND_EXPR_CHECK (NODE), 0))
 #define BIND_EXPR_BODY(NODE) (TREE_OPERAND (BIND_EXPR_CHECK (NODE), 1))
@@ -2897,6 +2902,10 @@ extern tree build3_stat (enum tree_code, tree, tree, tree, tree MEM_STAT_DECL);
 extern tree build4_stat (enum tree_code, tree, tree, tree, tree,
 			 tree MEM_STAT_DECL);
 #define build4(c,t1,t2,t3,t4,t5) build4_stat (c,t1,t2,t3,t4,t5 MEM_STAT_INFO)
+extern tree build7_stat (enum tree_code, tree, tree, tree, tree, tree,
+			 tree, tree, tree MEM_STAT_DECL);
+#define build7(c,t1,t2,t3,t4,t5,t6,t7,t8) \
+  build7_stat (c,t1,t2,t3,t4,t5,t6,t7,t8 MEM_STAT_INFO)
 
 extern tree build_int_cst (tree, HOST_WIDE_INT);
 extern tree build_int_cst_type (tree, HOST_WIDE_INT);
@@ -3990,4 +3999,8 @@ extern tree get_base_address (tree t);
 /* In tree-vectorizer.c.  */
 extern void vect_set_verbosity_level (const char *);
 
+/* In tree-ssa-address.c.  */
+extern tree tree_mem_ref_addr (tree, tree);
+extern void copy_mem_ref_info (tree, tree);
+
 #endif  /* GCC_TREE_H  */