[patch] TARGET_MEM_REF
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Fri Mar 4 00:38:00 GMT 2005
Hello,
ivopts make decisions based on what addressing modes are available at
the target machine. However, the tree optimizers that follow do not
use this knowledge, and may sometimes spoil the decisions. An example:
int *p, *q;
for (i = 0; i < 100; i++)
*(p + 4B * i) = *(q + 4B * i) = i;
On i686, ivopts will decide that leaving the loop in this form, since
i686 has addressing mode involving multiplication by four, so all the
computations are for free.
Dom however does not take this into account, transforming the loop to
int *p, *q;
for (i = 0; i < 100; i++)
{
tmp = 4B * i;
*(p + tmp) = *(q + tmp) = i;
}
The multiplication by four now has to be performed separately, which
is a performance regression (we also need one more register,
which sometimes is more important than the one extra shift
instruction).
At the moment, many of such missteps are masked by the old loop
optimizer; so before we are ready to remove the beast, we need to
deal with the problem.
This patch introduces TARGET_MEM_REF tree. This is a memory reference
whose address precisely maps to the addressing mode of the target
architecture. In particular, the multiplication/additions that are
for free are hidden inside the tree, thus they cannot be played with
by optimizations that do not know about the existence of addressing modes.
As a side effect, the address computations that are not expressible
within the addressing mode are exposed to the tree optimizers; which
seems as a nice bonus.
The most complex address TARGET_MEM_REF can express is of form (when
translated to rtl)
((plus (plus (mult INDEX STEP)
BASE)
(const (plus (symbol_ref SYMBOL) OFFSET))))
(and of course all subsets of this addressing mode), which should be
sufficient to capture the reasonable subset of the possible addressing
modes on various architectures. The shape of the memory reference, as
well as the constant values for STEP and OFFSET, are validated using
memory_address_p.
For now, TARGET_MEM_REFs are only generated in ivopts, in order to solve
the problem described above. Later, they can be used to enable
addressing mode selection before expansion to rtl, taking advantage of
the SSA form.
The change does not affect performance of the produced code
significantly (see the results of specint on i686 and ppc below; measured
together with the patch http://gcc.gnu.org/ml/gcc-patches/2005-03/msg00178.html
that fixes a minor performance regression uncovered by this patch).
The patch was bootstrapped & regtested on ia64, i686 and x86_64.
Zdenek
Base without the patch, peak with the patch.
i686:
164.gzip 1400 209 670 * 1400 209 671 *
175.vpr 1400 391 358 * 1400 394 356 *
176.gcc X X
181.mcf 1800 731 246 * 1800 736 245 *
186.crafty 1000 119 839 * 1000 119 838 *
197.parser 1800 399 451 * 1800 396 454 *
252.eon 1300 152 855 * 1300 149 871 *
253.perlbmk 1800 201 896 * 1800 201 897 *
254.gap 1100 175 629 * 1100 176 623 *
255.vortex 1900 233 816 * 1900 232 819 *
256.bzip2 1500 340 441 * 1500 340 441 *
300.twolf 3000 782 384 * 3000 792 379 *
Est. SPECint_base2000 553
Est. SPECint2000 553
ppc:
164.gzip X X
175.vpr 1400 309 452 * 1400 311 450 *
176.gcc X X
181.mcf 1800 548 328 * 1800 547 329 *
186.crafty 1000 86.7 1153 * 1000 86.2 1160 *
197.parser 1800 353 510 * 1800 348 518 *
252.eon X X
253.perlbmk 1800 250 720 * 1800 246 733 *
254.gap 1100 171 643 * 1100 156 703 *
255.vortex 1900 227 839 * 1900 227 839 *
256.bzip2 X X
300.twolf X X
Est. SPECint_base2000 617
Est. SPECint2000 628
* 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.
* gimplify.c (gimplify_addr_expr): Handle TARGET_MEM_REFs.
* tree-dfa.c (create_mem_ref_ann): New function.
* tree-eh.c (tree_could_trap_p): Handle TARGET_MEM_REFs.
* tree-flow-inline.h (mem_ref_ann, get_mem_ref_ann): New functions.
* tree-flow.h (enum tree_ann_type): Add MEM_REF_ANN.
(struct mem_ref_ann_d, mem_ref_ann_t): New.
(union tree_ann_d): Add mem_ref.
(mem_ref_ann, get_mem_ref_ann, create_mem_ref_ann): Declare.
(struct mem_address): New.
(create_mem_ref, addr_for_mem_ref, get_address_description): 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): Removed.
(get_ref_tag, copy_ref_info): New functions.
(rewrite_use_address): Produce TARGET_MEM_REFs.
* tree-ssa-operands.c (get_mem_ref_operands): New function.
(get_expr_operands): Handle TARGET_MEM_REFs.
* tree.c (copy_node_stat): Copy annotations and REF_ORIGINAL for
TARGET_MEM_REFs.
(build): Handle 5 arguments.
(build5_stat): New function.
* tree.def (TARGET_MEM_DEF): New.
* tree.h (REF_ORIGINAL): Expect TARGET_MEM_REF as an argument.
(MEM_REF_SYMBOL, MEM_REF_BASE, MEM_REF_INDEX, MEM_REF_STEP,
MEM_REF_OFFSET, build5): New macros.
(build5_stat, tree_mem_ref_addr): Declare.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1450
diff -c -3 -p -r1.1450 Makefile.in
*** Makefile.in 1 Mar 2005 17:58:59 -0000 1.1450
--- Makefile.in 3 Mar 2005 20:57:32 -0000
*************** OBJS-common = \
*** 901,907 ****
tree-chrec.o tree-scalar-evolution.o tree-data-ref.o \
tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \
gimplify.o tree-pretty-print.o tree-into-ssa.o \
! tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o \
tree-ssa-dce.o tree-ssa-copy.o tree-nrv.o tree-ssa-copyrename.o \
tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o tree-ssa-alias.o \
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \
--- 901,907 ----
tree-chrec.o tree-scalar-evolution.o tree-data-ref.o \
tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \
gimplify.o tree-pretty-print.o tree-into-ssa.o \
! tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o tree-ssa-address.o \
tree-ssa-dce.o tree-ssa-copy.o tree-nrv.o tree-ssa-copyrename.o \
tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o tree-ssa-alias.o \
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \
*************** tree-ssa-loop.o : tree-ssa-loop.c $(TREE
*** 1702,1707 ****
--- 1702,1712 ----
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h $(FLAGS_H) tree-inline.h $(SCEV_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-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) \
*************** GTFILES = $(srcdir)/input.h $(srcdir)/co
*** 2429,2435 ****
$(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-phinodes.c $(srcdir)/tree-cfg.c \
$(srcdir)/tree-dfa.c $(srcdir)/tree-ssa-propagate.c \
$(srcdir)/tree-iterator.c $(srcdir)/gimplify.c \
--- 2434,2440 ----
$(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-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 \
*************** gt-dwarf2out.h gt-reg-stack.h gt-dwarf2a
*** 2453,2459 ****
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-complex.h \
! gt-tree-eh.h \
gt-tree-ssanames.h gt-tree-iterator.h gt-gimplify.h \
gt-tree-phinodes.h gt-tree-cfg.h gt-tree-nested.h \
gt-tree-ssa-operands.h gt-tree-ssa-propagate.h \
--- 2458,2464 ----
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-complex.h \
! gt-tree-eh.h gt-tree-ssa-address.h \
gt-tree-ssanames.h gt-tree-iterator.h gt-gimplify.h \
gt-tree-phinodes.h gt-tree-cfg.h gt-tree-nested.h \
gt-tree-ssa-operands.h gt-tree-ssa-propagate.h \
Index: expr.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expr.c,v
retrieving revision 1.779
diff -c -3 -p -r1.779 expr.c
*** expr.c 2 Mar 2005 16:04:50 -0000 1.779
--- expr.c 3 Mar 2005 20:57:33 -0000
*************** expand_expr_real_1 (tree exp, rtx target
*** 6818,6824 ****
case INDIRECT_REF:
{
tree exp1 = TREE_OPERAND (exp, 0);
- tree orig;
if (modifier != EXPAND_WRITE)
{
--- 6818,6823 ----
*************** expand_expr_real_1 (tree exp, rtx target
*** 6841,6850 ****
temp = gen_rtx_MEM (mode, op0);
! orig = REF_ORIGINAL (exp);
! if (!orig)
! orig = exp;
! set_mem_attributes (temp, orig, 0);
/* Resolve the misalignment now, so that we don't have to remember
to resolve it later. Of course, this only works for reads. */
--- 6840,6846 ----
temp = gen_rtx_MEM (mode, op0);
! 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. */
*************** expand_expr_real_1 (tree exp, rtx target
*** 6876,6881 ****
--- 6872,6889 ----
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, REF_ORIGINAL (exp), 0);
+ }
+ return temp;
+
case ARRAY_REF:
{
Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gimplify.c,v
retrieving revision 2.113
diff -c -3 -p -r2.113 gimplify.c
*** gimplify.c 18 Feb 2005 19:35:37 -0000 2.113
--- gimplify.c 3 Mar 2005 20:57:33 -0000
*************** gimplify_addr_expr (tree *expr_p, tree *
*** 3248,3253 ****
--- 3248,3258 ----
ret = GS_OK;
break;
+ case TARGET_MEM_REF:
+ *expr_p = tree_mem_ref_addr (TREE_TYPE (expr), op0);
+ ret = GS_OK;
+ break;
+
default:
/* We use fb_either here because the C frontend sometimes takes
the address of a call that returns a struct; see
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dfa.c,v
retrieving revision 2.48
diff -c -3 -p -r2.48 tree-dfa.c
*** tree-dfa.c 3 Mar 2005 19:53:47 -0000 2.48
--- tree-dfa.c 3 Mar 2005 20:57:33 -0000
*************** create_stmt_ann (tree t)
*** 446,451 ****
--- 446,470 ----
return ann;
}
+ /* Create a new annotation for a TARGET_MEM_REF node T. */
+
+ mem_ref_ann_t
+ create_mem_ref_ann (tree t)
+ {
+ mem_ref_ann_t ann;
+
+ gcc_assert (TREE_CODE (t) == TARGET_MEM_REF);
+ gcc_assert (!t->common.ann || t->common.ann->common.type == MEM_REF_ANN);
+
+ ann = ggc_alloc (sizeof (*ann));
+ memset ((void *) ann, 0, sizeof (*ann));
+
+ ann->common.type = MEM_REF_ANN;
+
+ t->common.ann = (tree_ann_t) ann;
+
+ return ann;
+ }
/* Create a new annotation for a tree T. */
Index: tree-eh.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-eh.c,v
retrieving revision 2.26
diff -c -3 -p -r2.26 tree-eh.c
*** tree-eh.c 24 Feb 2005 21:47:26 -0000 2.26
--- tree-eh.c 3 Mar 2005 20:57:33 -0000
*************** tree_could_trap_p (tree expr)
*** 1739,1744 ****
--- 1739,1750 ----
restart:
switch (code)
{
+ case TARGET_MEM_REF:
+ /* For MEM_REFs use the information based on the original reference. */
+ expr = REF_ORIGINAL (expr);
+ code = TREE_CODE (expr);
+ goto restart;
+
case COMPONENT_REF:
case REALPART_EXPR:
case IMAGPART_EXPR:
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.31
diff -c -3 -p -r2.31 tree-flow-inline.h
*** tree-flow-inline.h 2 Feb 2005 20:56:18 -0000 2.31
--- tree-flow-inline.h 3 Mar 2005 20:57:33 -0000
*************** get_stmt_ann (tree stmt)
*** 67,72 ****
--- 67,92 ----
}
+ /* Return the annotation for T, which must be a TARGET_MEM_REF
+ node. Return NULL if the statement annotation doesn't exist. */
+ static inline mem_ref_ann_t
+ mem_ref_ann (tree t)
+ {
+ #ifdef ENABLE_CHECKING
+ gcc_assert (TREE_CODE (t) == TARGET_MEM_REF);
+ #endif
+ return (mem_ref_ann_t) t->common.ann;
+ }
+
+ /* Return the annotation for T, which must be a TARGET_MEM_REF
+ node. Create the annotation if it doesn't exist. */
+ static inline mem_ref_ann_t
+ get_mem_ref_ann (tree t)
+ {
+ mem_ref_ann_t ann = mem_ref_ann (t);
+ return ann ? ann : create_mem_ref_ann (t);
+ }
+
/* Return the annotation type for annotation ANN. */
static inline enum tree_ann_type
ann_type (tree_ann_t ann)
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.82
diff -c -3 -p -r2.82 tree-flow.h
*** tree-flow.h 1 Mar 2005 17:59:04 -0000 2.82
--- tree-flow.h 3 Mar 2005 20:57:33 -0000
*************** struct ptr_info_def GTY(())
*** 83,89 ****
/*---------------------------------------------------------------------------
Tree annotations stored in tree_common.ann
---------------------------------------------------------------------------*/
! enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, STMT_ANN };
struct tree_ann_common_d GTY(())
{
--- 83,89 ----
/*---------------------------------------------------------------------------
Tree annotations stored in tree_common.ann
---------------------------------------------------------------------------*/
! enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, STMT_ANN, MEM_REF_ANN };
struct tree_ann_common_d GTY(())
{
*************** struct stmt_ann_d GTY(())
*** 290,300 ****
--- 290,312 ----
unsigned int uid;
};
+ /* Annotation for TARGET_MEM_REFs. */
+
+ struct mem_ref_ann_d GTY(())
+ {
+ struct tree_ann_common_d common;
+
+ /* Name tag, type tag, or base object, whichever is applicable
+ for the reference from that the TARGET_MEM_REF was created. */
+ tree tag;
+ };
+
union tree_ann_d GTY((desc ("ann_type ((tree_ann_t)&%h)")))
{
struct tree_ann_common_d GTY((tag ("TREE_ANN_COMMON"))) common;
struct var_ann_d GTY((tag ("VAR_ANN"))) decl;
struct stmt_ann_d GTY((tag ("STMT_ANN"))) stmt;
+ struct mem_ref_ann_d GTY((tag ("MEM_REF_ANN"))) mem_ref;
};
extern GTY(()) VEC(tree) *modified_noreturn_calls;
*************** extern GTY(()) VEC(tree) *modified_noret
*** 302,307 ****
--- 314,320 ----
typedef union tree_ann_d *tree_ann_t;
typedef struct var_ann_d *var_ann_t;
typedef struct stmt_ann_d *stmt_ann_t;
+ typedef struct mem_ref_ann_d *mem_ref_ann_t;
static inline tree_ann_t tree_ann (tree);
static inline tree_ann_t get_tree_ann (tree);
*************** static inline var_ann_t var_ann (tree);
*** 309,314 ****
--- 322,329 ----
static inline var_ann_t get_var_ann (tree);
static inline stmt_ann_t stmt_ann (tree);
static inline stmt_ann_t get_stmt_ann (tree);
+ static inline mem_ref_ann_t mem_ref_ann (tree);
+ static inline mem_ref_ann_t get_mem_ref_ann (tree);
static inline enum tree_ann_type ann_type (tree_ann_t);
static inline basic_block bb_for_stmt (tree);
extern void set_bb_for_stmt (tree, basic_block);
*************** extern void dump_generic_bb (FILE *, bas
*** 517,522 ****
--- 532,538 ----
/* In tree-dfa.c */
extern var_ann_t create_var_ann (tree);
extern stmt_ann_t create_stmt_ann (tree);
+ extern mem_ref_ann_t create_mem_ref_ann (tree);
extern tree_ann_t create_tree_ann (tree);
extern void reserve_phi_args_for_new_edge (basic_block);
extern tree create_phi_node (tree, basic_block);
*************** extern bool expr_invariant_in_loop_p (st
*** 751,756 ****
--- 767,785 ----
tree force_gimple_operand (tree, tree *, bool, tree);
+ /* In tree-ssa-address.c */
+
+ /* Description of a memory address. */
+
+ struct mem_address
+ {
+ tree symbol, base, index, step, offset;
+ };
+
+ tree create_mem_ref (block_stmt_iterator *, tree, tree);
+ rtx addr_for_mem_ref (struct mem_address *, bool);
+ void get_address_description (tree, struct mem_address *);
+
#include "tree-flow-inline.h"
#endif /* _TREE_FLOW_H */
Index: tree-mudflap.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-mudflap.c,v
retrieving revision 2.35
diff -c -3 -p -r2.35 tree-mudflap.c
*** tree-mudflap.c 4 Jan 2005 18:47:02 -0000 2.35
--- tree-mudflap.c 3 Mar 2005 20:57:33 -0000
*************** mf_xform_derefs_1 (block_stmt_iterator *
*** 853,858 ****
--- 853,866 ----
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 ("mudflap checking not yet implemented for ARRAY_RANGE_REF");
return;
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 2.52
diff -c -3 -p -r2.52 tree-pretty-print.c
*** tree-pretty-print.c 9 Dec 2004 10:54:36 -0000 2.52
--- tree-pretty-print.c 3 Mar 2005 20:57:33 -0000
*************** dump_generic_node (pretty_printer *buffe
*** 445,450 ****
--- 445,507 ----
NIY;
break;
+ case TARGET_MEM_REF:
+ {
+ const char *sep = "";
+ tree tmp;
+
+ pp_string (buffer, "MEM[");
+
+ tmp = MEM_REF_SYMBOL (node);
+ if (tmp)
+ {
+ pp_string (buffer, sep);
+ sep = ", ";
+ pp_string (buffer, "symbol: ");
+ dump_generic_node (buffer, tmp, spc, flags, false);
+ }
+ tmp = MEM_REF_BASE (node);
+ if (tmp)
+ {
+ pp_string (buffer, sep);
+ sep = ", ";
+ pp_string (buffer, "base: ");
+ dump_generic_node (buffer, tmp, spc, flags, false);
+ }
+ tmp = MEM_REF_INDEX (node);
+ if (tmp)
+ {
+ pp_string (buffer, sep);
+ sep = ", ";
+ pp_string (buffer, "index: ");
+ dump_generic_node (buffer, tmp, spc, flags, false);
+ }
+ tmp = MEM_REF_STEP (node);
+ if (tmp)
+ {
+ pp_string (buffer, sep);
+ sep = ", ";
+ pp_string (buffer, "step: ");
+ dump_generic_node (buffer, tmp, spc, flags, false);
+ }
+ tmp = MEM_REF_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, REF_ORIGINAL (node), spc, flags, false);
+ pp_string (buffer, "}");
+ }
+ }
+ break;
+
case ARRAY_TYPE:
{
tree tmp;
Index: tree-ssa-address.c
===================================================================
RCS file: tree-ssa-address.c
diff -N tree-ssa-address.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-address.c 3 Mar 2005 20:57:33 -0000
***************
*** 0 ****
--- 1,814 ----
+ /* 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"
+
+ /* 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. */
+
+ 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))
+
+ /* Invokes force_gimple_operand for EXPR with parameters SIMPLE_P and VAR. If
+ some statements are produced, emits them before BSI. */
+
+ static tree
+ force_gimple_operand_bsi (block_stmt_iterator *bsi, tree expr,
+ bool simple_p, tree var)
+ {
+ tree stmts;
+
+ expr = force_gimple_operand (expr, &stmts, simple_p, var);
+ if (stmts)
+ bsi_insert_before (bsi, stmts, BSI_SAME_STMT);
+
+ return expr;
+ }
+
+ /* 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_fmt_ee (MULT, Pmode, act_elem, step);
+
+ if (step_p)
+ *step_p = &XEXP (act_elem, 1);
+ }
+
+ *addr = act_elem;
+ }
+
+ if (base)
+ {
+ if (*addr)
+ *addr = gen_rtx_fmt_ee (PLUS, Pmode, *addr, base);
+ else
+ *addr = base;
+ }
+
+ if (symbol)
+ {
+ act_elem = symbol;
+ if (offset)
+ {
+ act_elem = gen_rtx_fmt_e (CONST, Pmode,
+ gen_rtx_fmt_ee (PLUS, Pmode,
+ act_elem, offset));
+ if (offset_p)
+ *offset_p = &XEXP (XEXP (act_elem, 0), 1);
+ }
+
+ if (*addr)
+ *addr = gen_rtx_fmt_ee (PLUS, Pmode, *addr, act_elem);
+ else
+ *addr = act_elem;
+ }
+ else if (offset)
+ {
+ if (*addr)
+ {
+ *addr = gen_rtx_fmt_ee (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), 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 = MEM_REF_STEP (mem_ref), offset = MEM_REF_OFFSET (mem_ref);
+
+ act_elem = MEM_REF_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 = MEM_REF_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 = MEM_REF_SYMBOL (mem_ref);
+ if (act_elem)
+ {
+ act_elem = fold_convert (type, build_addr (act_elem));
+ 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 && integer_zerop (addr->offset))
+ addr->offset = NULL_TREE;
+
+ return build5 (TARGET_MEM_REF, type,
+ addr->symbol, addr->base, addr->index,
+ addr->step, addr->offset);
+ }
+
+ /* Adds register REG to the address PARTS, multiplied by MUL.
+ TYPE is the type in that the address computations should be performed.
+ If necessary, computations are emitted in front of BSI. */
+
+ static void
+ add_reg_to_parts (block_stmt_iterator *bsi, tree type,
+ struct mem_address *parts, tree reg, tree mul)
+ {
+ tree tmp;
+
+ /* If REG is INDEX already, just adjust the step. */
+ if (parts->index
+ && operand_equal_p (parts->index, reg, 0))
+ {
+ if (!mul)
+ mul = build_int_cst_type (type, 1);
+
+ if (parts->step)
+ parts->step
+ = fold_binary_to_constant (PLUS_EXPR, type,
+ fold_convert (type, parts->step),
+ mul);
+ else
+ parts->step
+ = fold_binary_to_constant (PLUS_EXPR, type,
+ mul, build_int_cst_type (type, 1));
+
+ return;
+ }
+
+ /* Equal to base; try putting it to the step with an appropriate index. */
+ if (parts->base
+ && operand_equal_p (parts->base, reg, 0))
+ {
+ if (!mul)
+ mul = build_int_cst_type (type, 2);
+ else
+ mul = fold_binary_to_constant (PLUS_EXPR, type, mul,
+ build_int_cst_type (type, 1));
+ if (!parts->step)
+ {
+ parts->base = parts->index;
+ parts->index = reg;
+ parts->step = mul;
+ return;
+ }
+
+ /* MUL * REG + STEP * INDEX. If MUL == STEP, just add REG to INDEX. */
+ if (operand_equal_p (parts->step, mul, 0))
+ {
+ parts->base = NULL_TREE;
+ tmp = build2 (PLUS_EXPR, type,
+ fold_convert (type, reg),
+ fold_convert (type, parts->index));
+ parts->index = force_gimple_operand_bsi (bsi, tmp, true, NULL_TREE);
+ return;
+ }
+
+ /* Replace base by MUL * BASE. */
+ tmp = build2 (MULT_EXPR, type, fold_convert (type, reg), mul);
+ parts->base = force_gimple_operand_bsi (bsi, tmp, true, NULL_TREE);
+ return;
+ }
+
+ /* Step 1 and free BASE. */
+ if (!mul
+ && !parts->base)
+ {
+ parts->base = reg;
+ return;
+ }
+
+ /* Maybe we can move value from INDEX to BASE, thus enabling us to
+ put REG to index. */
+ if (parts->index
+ && !parts->step
+ && !parts->base)
+ {
+ parts->base = parts->index;
+ parts->index = NULL_TREE;
+ }
+
+ /* Free INDEX. */
+ if (!parts->index)
+ {
+ parts->index = reg;
+ parts->step = mul;
+ return;
+ }
+
+ /* Both BASE and INDEX are full, or STEP != 1 and MUL != 1, and
+ BASE and INDEX is different from REG. Check whether
+ step is the same as MUL. */
+ if (mul
+ && parts->step
+ && operand_equal_p (parts->step, mul, 0))
+ {
+ tmp = build2 (PLUS_EXPR, type,
+ fold_convert (type, reg),
+ fold_convert (type, parts->index));
+ parts->index = force_gimple_operand_bsi (bsi, tmp, true, NULL_TREE);
+ return;
+ }
+
+ /* Otherwise add MUL * REG to BASE. */
+ if (mul)
+ tmp = build2 (MULT_EXPR, type, fold_convert (type, reg), mul);
+ else
+ tmp = fold_convert (type, reg);
+ if (parts->base)
+ tmp = build2 (PLUS_EXPR, type, tmp, fold_convert (type, parts->base));
+ parts->base = force_gimple_operand_bsi (bsi, tmp, true, NULL_TREE);
+ }
+
+ /* 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 symbol SYM to the address PARTS. TYPE is the type
+ in that the address computations should be performed. If necessary,
+ computations are emitted in front of BSI. */
+
+ static void
+ add_symbol_to_parts (block_stmt_iterator *bsi, tree type,
+ struct mem_address *parts, tree sym)
+ {
+ tree reg;
+
+ if (!parts->symbol
+ && fixed_address_object_p (sym))
+ {
+ parts->symbol = sym;
+ return;
+ }
+
+ reg = force_gimple_operand_bsi (bsi, build_addr (sym), true, NULL_TREE);
+ add_reg_to_parts (bsi, type, parts, reg, NULL_TREE);
+ }
+
+ /* Adds offset OFF to the address PARTS. TYPE is the type
+ in that the address computations should be performed. */
+
+ static void
+ add_offset_to_parts (tree type, struct mem_address *parts, tree off)
+ {
+ if (!parts->offset)
+ parts->offset = off;
+ else
+ parts->offset
+ = fold_binary_to_constant (PLUS_EXPR, type,
+ fold_convert (type, parts->offset),
+ fold_convert (type, off));
+ }
+
+ /* Sets the address PARTS to sum of addresses P0 and P1. TYPE is the type
+ in that the address computations should be performed. If necessary,
+ computations are emitted in front of BSI. */
+
+ static void
+ add_parts (block_stmt_iterator *bsi, tree type,
+ struct mem_address *p0, struct mem_address *p1,
+ struct mem_address *parts)
+ {
+ *parts = *p0;
+
+ if (p1->offset)
+ add_offset_to_parts (type, parts, p1->offset);
+
+ if (p1->index)
+ add_reg_to_parts (bsi, type, parts, p1->index, p1->step);
+
+ if (p1->base)
+ add_reg_to_parts (bsi, type, parts, p1->base, NULL_TREE);
+
+ if (p1->symbol)
+ add_symbol_to_parts (bsi, type, parts, p1->symbol);
+ }
+
+ /* Sets the address PARTs to difference of addresses P0 and P1. TYPE is the
+ type in that the address computations should be performed. If necessary,
+ computations are emitted in front of BSI. */
+
+ static void
+ rem_parts (block_stmt_iterator *bsi, tree type,
+ struct mem_address *p0, struct mem_address *p1,
+ struct mem_address *parts)
+ {
+ tree tmp;
+
+ *parts = *p0;
+
+ if (p1->offset)
+ {
+ tmp = fold_unary_to_constant (NEGATE_EXPR, type,
+ fold_convert (type, p1->offset));
+ add_offset_to_parts (type, parts, tmp);
+ }
+
+ if (p1->index)
+ {
+ if (p1->step)
+ tmp = fold_unary_to_constant (NEGATE_EXPR, type,
+ fold_convert (type, p1->step));
+ else
+ tmp = build_int_cst_type (type, -1);
+ add_reg_to_parts (bsi, type, parts, p1->index, tmp);
+ }
+
+ if (p1->base)
+ add_reg_to_parts (bsi, type, parts, p1->base,
+ build_int_cst_type (type, -1));
+
+ if (p1->symbol)
+ {
+ tmp = force_gimple_operand_bsi (bsi, build_addr (p1->symbol),
+ true, NULL_TREE);
+ add_reg_to_parts (bsi, type, parts, tmp, build_int_cst_type (type, -1));
+ }
+ }
+
+ /* Sets the address PARTs to MUL times addresses P0. TYPE is the
+ type in that the address computations should be performed. If necessary,
+ computations are emitted in front of BSI. */
+
+ static void
+ mul_parts (block_stmt_iterator *bsi, tree type, struct mem_address *p0,
+ tree mul, struct mem_address *parts)
+ {
+ tree tmp;
+
+ parts->symbol = NULL_TREE;
+ parts->base = NULL_TREE;
+
+ if (p0->offset)
+ parts->offset = fold_binary_to_constant (MULT_EXPR, type, mul,
+ fold_convert (type, p0->offset));
+ else
+ parts->offset = NULL_TREE;
+
+ if (p0->index)
+ {
+ parts->index = p0->index;
+ if (p0->step)
+ parts->step = fold_binary_to_constant (MULT_EXPR, type, mul,
+ fold_convert (type, p0->step));
+ else
+ parts->step = mul;
+ }
+ else
+ {
+ parts->index = NULL_TREE;
+ parts->step = NULL_TREE;
+ }
+
+ if (p0->base)
+ add_reg_to_parts (bsi, type, parts, p0->base, mul);
+
+ if (p0->symbol)
+ {
+ tmp = force_gimple_operand_bsi (bsi, build_addr (p0->symbol),
+ true, NULL_TREE);
+ add_reg_to_parts (bsi, type, parts, tmp, mul);
+ }
+ }
+
+ /* Splits address ADDR into PARTS. If necessary computations, are emitted
+ in front of BSI. */
+
+ static void
+ addr_to_parts (block_stmt_iterator *bsi, tree addr, struct mem_address *parts)
+ {
+ tree type, op0, op1;
+ enum tree_code code = TREE_CODE (addr);
+ struct mem_address p0, p1;
+
+ STRIP_NOPS (addr);
+ type = TREE_TYPE (addr);
+
+ switch (code)
+ {
+ case SSA_NAME:
+ parts->symbol = NULL_TREE;
+ parts->base = addr;
+ parts->index = NULL_TREE;
+ parts->step = NULL_TREE;
+ parts->offset = NULL_TREE;
+ return;
+
+ case INTEGER_CST:
+ parts->symbol = NULL_TREE;
+ parts->base = NULL_TREE;
+ parts->index = NULL_TREE;
+ parts->step = NULL_TREE;
+ parts->offset = addr;
+ return;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ op0 = TREE_OPERAND (addr, 0);
+ op1 = TREE_OPERAND (addr, 1);
+ addr_to_parts (bsi, op0, &p0);
+ addr_to_parts (bsi, op1, &p1);
+
+ if (code == PLUS_EXPR)
+ add_parts (bsi, type, &p0, &p1, parts);
+ else
+ rem_parts (bsi, type, &p0, &p1, parts);
+ return;
+
+ case MULT_EXPR:
+ op0 = TREE_OPERAND (addr, 0);
+ op1 = TREE_OPERAND (addr, 1);
+
+ if (TREE_CODE (op1) != INTEGER_CST)
+ break;
+ addr_to_parts (bsi, op0, &p0);
+ mul_parts (bsi, type, &p0, op1, parts);
+ return;
+
+ case ADDR_EXPR:
+ {
+ tree core, off;
+ enum machine_mode mode;
+ int unsignedp, volatilep;
+ HOST_WIDE_INT bitsize, bitoff;
+
+ core = get_inner_reference (TREE_OPERAND (addr, 0), &bitsize, &bitoff,
+ &off, &mode, &unsignedp, &volatilep,
+ false);
+ gcc_assert (bitoff % BITS_PER_UNIT == 0);
+
+ if (off)
+ addr_to_parts (bsi, off, &p0);
+ else
+ {
+ p0.symbol = NULL_TREE;
+ p0.base = NULL_TREE;
+ p0.index = NULL_TREE;
+ p0.step = NULL_TREE;
+ p0.offset = NULL_TREE;
+ }
+
+ if (bitoff)
+ add_offset_to_parts (type, &p0,
+ build_int_cst_type (type,
+ bitoff / BITS_PER_UNIT));
+
+ if (TREE_CODE (core) == INDIRECT_REF)
+ {
+ addr_to_parts (bsi, TREE_OPERAND (core, 0), &p1);
+ add_parts (bsi, type, &p0, &p1, parts);
+ }
+ else
+ {
+ add_symbol_to_parts (bsi, type, &p0, core);
+ *parts = p0;
+ }
+ return;
+ }
+
+ default:
+ break;
+ }
+
+ addr = force_gimple_operand_bsi (bsi, addr, true, NULL_TREE);
+ parts->symbol = NULL_TREE;
+ parts->base = addr;
+ parts->index = NULL_TREE;
+ parts->step = NULL_TREE;
+ parts->offset = NULL_TREE;
+ return;
+ }
+
+ /* 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, tree addr)
+ {
+ tree mem_ref, tmp;
+ tree addr_type = build_pointer_type (type);
+ struct mem_address parts;
+
+ addr_to_parts (bsi, addr, &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);
+
+ /* 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;
+ }
+
+ 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));
+
+ /* Things won't get any simpler. */
+ gcc_unreachable ();
+ }
+
+ /* Copies components of the address from OP to ADDR. */
+
+ void
+ get_address_description (tree op, struct mem_address *addr)
+ {
+ addr->symbol = MEM_REF_SYMBOL (op);
+ addr->base = MEM_REF_BASE (op);
+ addr->index = MEM_REF_INDEX (op);
+ addr->step = MEM_REF_STEP (op);
+ addr->offset = MEM_REF_OFFSET (op);
+ }
+
+ #include "gt-tree-ssa-address.h"
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-im.c,v
retrieving revision 2.28
diff -c -3 -p -r2.28 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c 19 Feb 2005 09:25:59 -0000 2.28
--- tree-ssa-loop-im.c 3 Mar 2005 20:57:33 -0000
*************** for_each_index (tree *addr_p, bool (*cbc
*** 196,201 ****
--- 196,212 ----
case RESULT_DECL:
return true;
+ case TARGET_MEM_REF:
+ idx = &MEM_REF_BASE (*addr_p);
+ if (*idx
+ && !cbck (*addr_p, idx, data))
+ return false;
+ idx = &MEM_REF_INDEX (*addr_p);
+ if (*idx
+ && !cbck (*addr_p, idx, data))
+ return false;
+ return true;
+
default:
gcc_unreachable ();
}
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.50
diff -c -3 -p -r2.50 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 25 Feb 2005 12:07:11 -0000 2.50
--- tree-ssa-loop-ivopts.c 3 Mar 2005 20:57:33 -0000
*************** may_be_unaligned_p (tree ref)
*** 1480,1485 ****
--- 1480,1490 ----
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. */
*************** may_be_unaligned_p (tree ref)
*** 1502,1508 ****
static void
find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
{
! tree base = unshare_expr (*op_p), step = NULL;
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;
--- 1507,1513 ----
static void
find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
{
! tree base = *op_p, step = NULL;
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;
*************** find_interesting_uses_address (struct iv
*** 1516,1535 ****
&& 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;
! gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
! gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
! if (TREE_CODE (base) == INDIRECT_REF)
! base = TREE_OPERAND (base, 0);
else
! base = build_addr (base);
civ = alloc_iv (base, step);
record_use (data, op_p, civ, stmt, USE_ADDRESS);
--- 1521,1587 ----
&& may_be_unaligned_p (base))
goto fail;
! base = unshare_expr (base);
!
! if (TREE_CODE (base) == TARGET_MEM_REF)
! {
! tree type = build_pointer_type (TREE_TYPE (base));
! tree astep;
!
! if (MEM_REF_BASE (base)
! && TREE_CODE (MEM_REF_BASE (base)) == SSA_NAME)
! {
! civ = get_iv (data, MEM_REF_BASE (base));
! if (!civ)
! goto fail;
!
! MEM_REF_BASE (base) = civ->base;
! step = civ->step;
! }
! if (MEM_REF_INDEX (base)
! && TREE_CODE (MEM_REF_INDEX (base)) == SSA_NAME)
! {
! civ = get_iv (data, MEM_REF_INDEX (base));
! if (!civ)
! goto fail;
!
! MEM_REF_INDEX (base) = civ->base;
! astep = civ->step;
! if (astep)
! {
! if (MEM_REF_STEP (base))
! astep = fold (build2 (MULT_EXPR, type, MEM_REF_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);
!
! if (TREE_CODE (base) == INDIRECT_REF)
! base = TREE_OPERAND (base, 0);
! else
! base = build_addr (base);
! }
civ = alloc_iv (base, step);
record_use (data, op_p, civ, stmt, USE_ADDRESS);
*************** unshare_and_remove_ssa_names (tree ref)
*** 4779,4849 ****
return ref;
}
! /* Rewrites base of memory access OP with expression WITH in statement
! pointed to by BSI. */
! static void
! rewrite_address_base (block_stmt_iterator *bsi, tree *op, tree with)
{
! tree bvar, var, new_var, new_name, copy, name;
! tree orig;
!
! var = bvar = get_base_address (*op);
! if (!var || TREE_CODE (with) != SSA_NAME)
! goto do_rewrite;
- 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;
var = SSA_NAME_VAR (var);
}
! else if (DECL_P (var))
! name = NULL_TREE;
! else
! goto do_rewrite;
!
! if (var_ann (var)->type_mem_tag)
! var = var_ann (var)->type_mem_tag;
!
! /* 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
{
! new_var = create_tmp_var (TREE_TYPE (with), "ruatmp");
! add_referenced_tmp_var (new_var);
! var_ann (new_var)->type_mem_tag = var;
! new_name = make_ssa_name (new_var, copy);
! }
! TREE_OPERAND (copy, 0) = new_name;
! bsi_insert_before (bsi, copy, BSI_SAME_STMT);
! with = new_name;
!
! 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);
! *op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
! /* Record the original reference, for purposes of alias analysis. */
! REF_ORIGINAL (*op) = orig;
}
/* Rewrites USE (address that is an iv) using candidate CAND. */
--- 4831,4893 ----
return ref;
}
! /* 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 tree
! get_ref_tag (tree ref)
{
! tree var = get_base_address (ref);
! tree tag;
! if (!var)
! return NULL_TREE;
if (TREE_CODE (var) == INDIRECT_REF)
var = TREE_OPERAND (var, 0);
if (TREE_CODE (var) == SSA_NAME)
{
! if (SSA_NAME_PTR_INFO (var))
! {
! tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
! if (tag)
! return tag;
! }
!
var = SSA_NAME_VAR (var);
}
!
! if (DECL_P (var))
{
! tag = var_ann (var)->type_mem_tag;
! if (tag)
! return tag;
!
! return var;
! }
!
! return NULL_TREE;
! }
! /* Copies the reference information from OLD_REF to NEW_REF. */
! static void
! copy_ref_info (tree new_ref, tree old_ref)
! {
! if (TREE_CODE (old_ref) == TARGET_MEM_REF)
! {
! REF_ORIGINAL (new_ref) = REF_ORIGINAL (old_ref);
! new_ref->common.ann = tree_ann (old_ref);
! }
! else
! {
! REF_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
! get_mem_ref_ann (new_ref)->tag = get_ref_tag (old_ref);
! }
}
/* Rewrites USE (address that is an iv) using candidate CAND. */
*************** static void
*** 4852,4867 ****
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));
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
! tree stmts;
! tree op = force_gimple_operand (comp, &stmts, true, NULL_TREE);
!
! if (stmts)
! bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
! rewrite_address_base (&bsi, use->op_p, op);
}
/* Rewrites USE (the condition such that one of the arguments is an iv) using
--- 4896,4909 ----
rewrite_use_address (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
+ /* TODO -- produce TARGET_MEM_REF directly. */
tree comp = unshare_expr (get_computation (data->current_loop,
use, cand));
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
! tree ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), comp);
! 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
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.63
diff -c -3 -p -r2.63 tree-ssa-operands.c
*** tree-ssa-operands.c 23 Feb 2005 05:08:24 -0000 2.63
--- tree-ssa-operands.c 3 Mar 2005 20:57:33 -0000
*************** static void note_addressable (tree, stmt
*** 140,145 ****
--- 140,146 ----
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_mem_ref_operands (tree, tree, int);
static void get_call_expr_operands (tree, tree);
static inline void append_def (tree *);
static inline void append_use (tree *);
*************** get_expr_operands (tree stmt, tree *expr
*** 1091,1096 ****
--- 1092,1101 ----
get_indirect_ref_operands (stmt, expr, flags);
return;
+ case TARGET_MEM_REF:
+ get_mem_ref_operands (stmt, expr, flags);
+ return;
+
case ARRAY_REF:
case ARRAY_RANGE_REF:
/* Treat array references as references to the virtual variable
*************** get_indirect_ref_operands (tree stmt, tr
*** 1452,1457 ****
--- 1457,1486 ----
get_expr_operands (stmt, pptr, opf_none);
}
+ /* A subroutine of get_expr_operands to handle TARGET_MEM_REF. */
+
+ static void
+ get_mem_ref_operands (tree stmt, tree expr, int flags)
+ {
+ mem_ref_ann_t ann = mem_ref_ann (expr);
+
+ /* First record the real operands. */
+ get_expr_operands (stmt, &MEM_REF_BASE (expr), opf_none);
+ get_expr_operands (stmt, &MEM_REF_INDEX (expr), opf_none);
+
+ /* MEM_REFs should never be killing. */
+ flags &= ~opf_kill_def;
+
+ if (MEM_REF_SYMBOL (expr))
+ note_addressable (MEM_REF_SYMBOL (expr), stmt_ann (stmt));
+
+ if (ann->tag)
+ add_stmt_operand (&ann->tag, stmt_ann (stmt), flags);
+ else
+ /* Something weird, so ensure we will be careful. */
+ stmt_ann (stmt)->has_volatile_ops = true;
+ }
+
/* A subroutine of get_expr_operands to handle CALL_EXPR. */
static void
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.466
diff -c -3 -p -r1.466 tree.c
*** tree.c 12 Feb 2005 00:26:56 -0000 1.466
--- tree.c 3 Mar 2005 20:57:33 -0000
*************** copy_node_stat (tree node MEM_STAT_DECL)
*** 432,437 ****
--- 432,447 ----
TREE_ASM_WRITTEN (t) = 0;
TREE_VISITED (t) = 0;
t->common.ann = 0;
+ if (code == TARGET_MEM_REF)
+ {
+ /* Copy the annotation as well. */
+ get_mem_ref_ann (t)->tag = mem_ref_ann (node)->tag;
+ }
+
+ /* Copy also the info about the original reference (stored a bit hackily
+ in TREE_CHAIN that is zeroed before). */
+ if (code == TARGET_MEM_REF)
+ REF_ORIGINAL (t) = REF_ORIGINAL (node);
if (TREE_CODE_CLASS (code) == tcc_declaration)
DECL_UID (t) = next_decl_uid++;
*************** build4_stat (enum tree_code code, tree t
*** 2697,2708 ****
return t;
}
/* Backup definition for non-gcc build compilers. */
tree
(build) (enum tree_code code, tree tt, ...)
{
! tree t, arg0, arg1, arg2, arg3;
int length = TREE_CODE_LENGTH (code);
va_list p;
--- 2707,2748 ----
return t;
}
+ tree
+ build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
+ tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
+ {
+ bool constant, read_only, side_effects, invariant;
+ tree t;
+
+ gcc_assert (TREE_CODE_LENGTH (code) == 5);
+
+ 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);
+
+ TREE_SIDE_EFFECTS (t) = side_effects;
+
+ TREE_THIS_VOLATILE (t)
+ = (code != TARGET_MEM_REF
+ && TREE_CODE_CLASS (code) == tcc_reference
+ && arg0 && TREE_THIS_VOLATILE (arg0));
+
+ return t;
+ }
+
/* Backup definition for non-gcc build compilers. */
tree
(build) (enum tree_code code, tree tt, ...)
{
! tree t, arg0, arg1, arg2, arg3, arg4;
int length = TREE_CODE_LENGTH (code);
va_list p;
*************** tree
*** 2734,2739 ****
--- 2774,2787 ----
arg3 = va_arg (p, tree);
t = build4 (code, tt, arg0, arg1, arg2, arg3);
break;
+ case 5:
+ 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);
+ t = build5 (code, tt, arg0, arg1, arg2, arg3, arg4);
+ break;
default:
gcc_unreachable ();
}
Index: tree.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.def,v
retrieving revision 1.112
diff -c -3 -p -r1.112 tree.def
*** tree.def 23 Jan 2005 15:05:34 -0000 1.112
--- tree.def 3 Mar 2005 20:57:33 -0000
*************** DEFTREECODE (WITH_SIZE_EXPR, "with_size_
*** 924,929 ****
--- 924,937 ----
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. */
+
+ DEFTREECODE (TARGET_MEM_REF, "target_mem_ref", tcc_reference, 5)
+
/*
Local variables:
mode:c
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.694
diff -c -3 -p -r1.694 tree.h
*** tree.h 28 Feb 2005 18:18:26 -0000 1.694
--- tree.h 3 Mar 2005 20:57:33 -0000
*************** struct tree_vec GTY(())
*** 1182,1190 ****
#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)
--- 1182,1189 ----
#define TREE_OPERAND(NODE, I) TREE_OPERAND_CHECK (NODE, I)
#define TREE_COMPLEXITY(NODE) (EXPR_CHECK (NODE)->exp.complexity)
! /* In TARGET_MEM_REF. */
! #define REF_ORIGINAL(NODE) TREE_CHAIN (TREE_CHECK (NODE, TARGET_MEM_REF))
/* In a LOOP_EXPR node. */
#define LOOP_EXPR_BODY(NODE) TREE_OPERAND_CHECK_CODE (NODE, LOOP_EXPR, 0)
*************** struct tree_vec GTY(())
*** 1251,1256 ****
--- 1250,1262 ----
#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 MEM_REF_SYMBOL(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 0))
+ #define MEM_REF_BASE(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 1))
+ #define MEM_REF_INDEX(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 2))
+ #define MEM_REF_STEP(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 3))
+ #define MEM_REF_OFFSET(NODE) (TREE_OPERAND (TARGET_MEM_REF_CHECK (NODE), 4))
+
/* 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))
*************** extern tree build3_stat (enum tree_code,
*** 2861,2866 ****
--- 2867,2875 ----
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 build5_stat (enum tree_code, tree, tree, tree, tree, tree,
+ tree MEM_STAT_DECL);
+ #define build5(c,t1,t2,t3,t4,t5,t6) build5_stat (c,t1,t2,t3,t4,t5,t6 MEM_STAT_INFO)
extern tree build_int_cst (tree, HOST_WIDE_INT);
extern tree build_int_cst_type (tree, HOST_WIDE_INT);
*************** extern tree get_base_address (tree t);
*** 3939,3942 ****
--- 3948,3954 ----
/* 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);
+
#endif /* GCC_TREE_H */
More information about the Gcc-patches
mailing list