[tree-ssa-branch]: Steensgaard alias analysis
Daniel Berlin
dberlin@dberlin.org
Mon Jul 15 10:54:00 GMT 2002
Diego, I added a flag to turn it on and off, commented most of it, and
have worked more on it (It now handles pointers to members properly, etc).
I'm still having trouble unifying prototypes with their function
definitions, so that all the arguments alias properly.
This is an interprocedural problem only, of course.
I've not yet added the 10 line routine to do intraprocedural calls
instead.
I'll do that next, since intraprocedural will be our main mode of
operation anyway.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.5
diff -c -3 -p -w -B -b -r1.903.2.5 Makefile.in
*** Makefile.in 10 Jul 2002 22:05:12 -0000 1.903.2.5
--- Makefile.in 15 Jul 2002 17:46:38 -0000
*************** C_AND_OBJC_OBJS = attribs.o c-errors.o c
*** 715,721 ****
c-objc-common.o libcpp.a $(C_TARGET_OBJS) \
tree-cfg.o tree-dfa.o tree-ssa.o tree-optimize.o c-pretty-print.o \
c-simplify.o c-call-graph.o tree-simple.o simple-break-elim.o \
! simple-goto-elim.o tree-dchain.o tree-ssa-pre.o tree-ssa-ccp.o
# Language-specific object files for C.
C_OBJS = c-parse.o c-lang.o $(C_AND_OBJC_OBJS)
--- 715,722 ----
c-objc-common.o libcpp.a $(C_TARGET_OBJS) \
tree-cfg.o tree-dfa.o tree-ssa.o tree-optimize.o c-pretty-print.o \
c-simplify.o c-call-graph.o tree-simple.o simple-break-elim.o \
! simple-goto-elim.o tree-dchain.o tree-ssa-pre.o tree-alias-type.o \
! tree-alias-ecr.o tree-alias-steen.o disjoint-set.o tree-ssa-ccp.o
# Language-specific object files for C.
C_OBJS = c-parse.o c-lang.o $(C_AND_OBJC_OBJS)
*************** tree-inline.o : tree-inline.c $(CONFIG_H
*** 1373,1378 ****
--- 1374,1383 ----
$(C_COMMON_H) tree-inline.h
print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(GGC_H) \
langhooks.h real.h
+ disjoint-set.o: disjoint-set.c disjoint-set.h $(SYSTEM_H) $(CONFIG_H) $(GGC_H)
+ tree-alias-ecr.o: tree-alias-ecr.c tree-alias-ecr.h disjoint-set.h tree-alias-type.h $(SYSTEM_H) $(CONFIG_H) $(GGC_H)
+ tree-alias-type.o: tree-alias-type.c tree-alias-type.h $(SYSTEM_H) $(CONFIG_H) $(GGC_H)
+ tree-alias-steen.o: tree-alias-steen.c tree-alias-steen.h $(SYSTEM_H) $(CONFIG_H) $(GGC_H) gt-tree-alias-steen.h tree-flow.h
tree-ssa.o : tree-ssa.c tree-optimize.h tree-flow.h $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) $(EXPR_H) $(C_COMMON_H) \
$(GGC_H) output.h diagnostic.h ssa.h errors.h toplev.h
*************** GTFILES = $(GCONFIG_H) \
*** 1848,1853 ****
--- 1853,1859 ----
$(srcdir)/tree.h $(srcdir)/libfuncs.h $(srcdir)/hashtable.h $(srcdir)/real.h \
$(srcdir)/varray.h $(srcdir)/ssa.h $(srcdir)/insn-addr.h $(srcdir)/cselib.h \
$(srcdir)/c-common.h $(srcdir)/c-tree.h \
+ $(srcdir)/disjoint-set.h \
$(srcdir)/basic-block.h \
$(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c \
$(srcdir)/dependence.c $(srcdir)/dwarf2out.c $(srcdir)/emit-rtl.c \
*************** GTFILES = $(GCONFIG_H) \
*** 1856,1862 ****
--- 1862,1872 ----
$(srcdir)/gcse.c $(srcdir)/integrate.c $(srcdir)/lists.c $(srcdir)/optabs.c \
$(srcdir)/profile.c $(srcdir)/regclass.c $(srcdir)/reg-stack.c \
$(srcdir)/sdbout.c $(srcdir)/stmt.c $(srcdir)/stor-layout.c \
+ $(srcdir)/disjoint-set.c \
$(srcdir)/tree.c $(srcdir)/varasm.c \
+ $(srcdir)/tree-alias-type.h $(srcdir)/tree-alias-ecr.h $(srcdir)/tree-alias-steen.h \
+ $(srcdir)/tree-alias-type.c $(srcdir)/tree-alias-ecr.c $(srcdir)/tree-alias-steen.c \
+ $(srcdir)/tree-flow.h \
$(srcdir)/c-objc-common.c $(srcdir)/c-common.c $(srcdir)/c-parse.in \
$(out_file) \
$(srcdir)/c-decl.c $(srcdir)/c-pragma.c \
*************** gt-expr.h gt-sdbout.h gt-optabs.h gt-bit
*** 1870,1875 ****
--- 1880,1886 ----
gt-reg-stack.h gt-dependence.h : s-gtype ; @true
gt-c-common.h gt-c-decl.h gt-c-parse.h gt-c-pragma.h : s-gtype; @true
gt-c-objc-common.h gtype-c.h : s-gtype ; @true
+ gt-tree-alias-steen.h : s-gtype ; @true
s-gtype: gengtype$(build_exeext) $(GTFILES)
./gengtype $(GTFILES)
Index: disjoint-set.c
===================================================================
RCS file: disjoint-set.c
diff -N disjoint-set.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- disjoint-set.c 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,124 ----
+
+ #include "config.h"
+ #include "system.h"
+ #include "ggc.h"
+ #include "disjoint-set.h"
+
+ disjoint_set
+ disjoint_set_new (void)
+ {
+ disjoint_set ret = ggc_alloc (sizeof (struct disjoint_set_def));
+ ret->parent = NULL;
+ ret->rank = 0;
+ ret->elements = NULL;
+ return ret;
+
+ }
+
+ disjoint_set
+ disjoint_set_union (x, y)
+ disjoint_set x;
+ disjoint_set y;
+ {
+ disjoint_set elemx = disjoint_set_find (x);
+ disjoint_set elemy = disjoint_set_find (y);
+
+ if (elemx == elemy)
+ return elemx;
+ if (elemx->rank > elemy->rank)
+ {
+ elemy->parent = elemx;
+ disjoint_set_merge_elems (elemx, elemy);
+ return elemx;
+ }
+ elemx->parent = elemy;
+ if (elemx->rank == elemy->rank)
+ elemy->rank += 1;
+ disjoint_set_merge_elems (elemy, elemx);
+ return elemy;
+ }
+
+ disjoint_set
+ disjoint_set_find (x)
+ disjoint_set x;
+ {
+ if (x->parent == NULL)
+ return x;
+ return disjoint_set_find (x->parent);
+ }
+
+ bool
+ disjoint_set_is_rep (x)
+ disjoint_set x;
+ {
+ return x->parent == NULL;
+ }
+
+ int
+ disjoint_set_size (x)
+ disjoint_set x;
+ {
+ disjoint_set rep = disjoint_set_find (x);
+ if (rep->elements == NULL)
+ return 1;
+ return VARRAY_ACTIVE_SIZE (rep->elements);
+ }
+
+ varray_type
+ disjoint_set_elems (x)
+ disjoint_set x;
+ {
+ /* XXX: This sucks, since we have to copy the varray. */
+ varray_type ret;
+ size_t i;
+ disjoint_set rep = disjoint_set_find (x);
+ VARRAY_GENERIC_PTR_INIT (ret, 1, "Disjoint set elements");
+ if (rep->elements == NULL)
+ {
+ VARRAY_PUSH_GENERIC_PTR (ret, x);
+ return ret;
+ }
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (rep->elements); i++)
+ {
+ VARRAY_PUSH_GENERIC_PTR (ret, VARRAY_GENERIC_PTR (rep->elements, i));
+ }
+ return ret;
+ }
+
+ bool
+ disjoint_set_equiv (x, y)
+ disjoint_set x;
+ disjoint_set y;
+ {
+ if (x == y)
+ return true;
+ if (disjoint_set_find (x) == disjoint_set_find (y))
+ return true;
+ return false;
+ }
+
+ void
+ disjoint_set_merge_elems (x, y)
+ disjoint_set x;
+ disjoint_set y;
+ {
+ size_t ysize;
+ size_t i;
+ if (x == y)
+ return;
+ if (x->elements == NULL)
+ {
+ VARRAY_GENERIC_PTR_INIT (x->elements, 1, "Disjoint set elements");
+ VARRAY_PUSH_GENERIC_PTR (x->elements, x);
+ }
+ if (y->elements == NULL)
+ {
+
+ VARRAY_PUSH_GENERIC_PTR (x->elements, y);
+ return;
+ }
+ ysize = VARRAY_ACTIVE_SIZE (y->elements);
+ for (i = 0; i < ysize; i++)
+ VARRAY_PUSH_GENERIC_PTR (x->elements,
+ VARRAY_GENERIC_PTR (y->elements, i));
+ }
Index: disjoint-set.h
===================================================================
RCS file: disjoint-set.h
diff -N disjoint-set.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- disjoint-set.h 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,22 ----
+ #ifndef DISJOINT_SET_H
+ #define DISJOINT_SET_H
+ #include "varray.h"
+
+
+ struct disjoint_set_def GTY (())
+ {
+ struct disjoint_set_def *parent;
+ int rank;
+ varray_type GTY ((param_is (struct ECR_def))) elements;
+ };
+ typedef struct disjoint_set_def *disjoint_set;
+
+ disjoint_set disjoint_set_new PARAMS ((void));
+ disjoint_set disjoint_set_union PARAMS ((disjoint_set, disjoint_set));
+ disjoint_set disjoint_set_find PARAMS ((disjoint_set));
+ bool disjoint_set_is_rep PARAMS ((disjoint_set));
+ int disjoint_set_size PARAMS ((disjoint_set));
+ varray_type disjoint_set_elems PARAMS ((disjoint_set));
+ bool disjoint_set_equiv PARAMS ((disjoint_set, disjoint_set));
+ void disjoint_set_merge_elems PARAMS ((disjoint_set, disjoint_set));
+ #endif
Index: tree-alias-ecr.c
===================================================================
RCS file: tree-alias-ecr.c
diff -N tree-alias-ecr.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-alias-ecr.c 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,201 ----
+
+ #include "config.h"
+ #include "system.h"
+ #include "ggc.h"
+ #include "varray.h"
+ #include "tree-alias-ecr.h"
+ #include "splay-tree.h"
+ #include "bitmap.h"
+ static unsigned int ECR_num = 0;
+ /*static GTY((param_is (struct ECR_def)))*/
+ static splay_tree ECR_mapping = NULL;
+ #include "gt-tree-alias-ecr.h"
+
+ ECR
+ ECR_new (void)
+ {
+ return ECR_new_with_type (alias_bottom, NULL);
+ }
+
+ ECR
+ ECR_new_with_type (type, var)
+ alias_type type;
+ alias_typevar var;
+ {
+ ECR ret = ggc_alloc (sizeof (struct ECR_def));
+ ret->set.parent = NULL;
+ ret->set.rank = 0;
+ ret->set.elements = NULL;
+ ret->type = type;
+ ret->color = 0;
+ ret->var = var;
+ ret->pending = NULL;
+ ret->id = ECR_num++;
+ if (!ECR_mapping)
+ {
+ ECR_mapping = splay_tree_new (splay_tree_compare_ints, NULL, NULL);
+ }
+ splay_tree_insert (ECR_mapping, (splay_tree_key) ECR_num, (splay_tree_value) ret);
+ return ret;
+ }
+
+ alias_type
+ ECR_get_type (ecr)
+ ECR ecr;
+ {
+ ECR rep = ECR_find (ecr);
+ return rep->type;
+ }
+
+ int
+ ECR_get_setid (ecr)
+ ECR ecr;
+ {
+ ECR rep = ECR_find (ecr);
+ return rep->id;
+ }
+
+ void
+ ECR_union_pending_sets (e1, e2, e3)
+ ECR e1;
+ ECR e2;
+ ECR e3;
+ {
+ if ((e1->pending != NULL) && (e2->pending != NULL))
+ {
+ if (e3->pending == NULL)
+ {
+ e3->pending = BITMAP_GGC_ALLOC ();
+ bitmap_clear (e3->pending);
+ }
+ bitmap_a_or_b (e3->pending, e2->pending, e1->pending);
+ }
+ else if (e2->pending != NULL)
+ {
+ if (e3->pending == NULL)
+ {
+ e3->pending = BITMAP_GGC_ALLOC ();
+ bitmap_clear (e3->pending);
+ }
+ bitmap_copy (e3->pending, e2->pending);
+ }
+ else if (e1->pending != NULL)
+ {
+ if (e3->pending == NULL)
+ {
+ e3->pending = BITMAP_GGC_ALLOC ();
+ bitmap_clear (e3->pending);
+ }
+ bitmap_copy (e3->pending, e1->pending);
+ }
+
+ if (e3 != e1)
+ {
+ bitmap_clear (e1->pending);
+ e1->pending = NULL;
+ }
+ if (e3 != e2)
+ {
+ bitmap_clear (e2->pending);
+ e2->pending = NULL;
+ }
+ }
+
+ static void
+ ECR_add_pending (e1, e2)
+ ECR e1;
+ ECR e2;
+ {
+ ECR rep = ECR_find (e1);
+ if (rep->pending == NULL)
+ {
+ rep->pending = BITMAP_GGC_ALLOC ();
+ bitmap_clear (rep->pending);
+ }
+ bitmap_set_bit (rep->pending, ECR_get_id (e2));
+ }
+
+ void
+ ECR_cjoin (e1, e2)
+ ECR e1;
+ ECR e2;
+ {
+ if (ECR_get_type (e2) == alias_bottom)
+ ECR_add_pending (e2, e1);
+ else
+ ECR_join (e1, e2);
+ }
+
+ void
+ ECR_join (e1, e2)
+ ECR e1;
+ ECR e2;
+ {
+ alias_type t1 = ECR_get_type (e1);
+ alias_type t2 = ECR_get_type (e2);
+
+ ECR u = ECR_union (e1, e2);
+
+ if (t1 == alias_bottom)
+ {
+ u->type = t2;
+ if (t2 == alias_bottom)
+ {
+ ECR_union_pending_sets (u, e1, e2);
+ }
+ else
+ {
+ if (e1->pending != NULL)
+ {
+ int i;
+ EXECUTE_IF_SET_IN_BITMAP (e1->pending, 0, i,
+ {
+ ECR_join (u, (ECR) splay_tree_lookup (ECR_mapping, i)->value);
+ });
+ bitmap_clear (e1->pending);
+ e1->pending = NULL;
+ }
+ }
+ }
+ else
+ {
+ u->type = t1;
+ if (t2 == alias_bottom)
+ {
+ if (e2->pending != NULL)
+ {
+ int i;
+ EXECUTE_IF_SET_IN_BITMAP (e2->pending, 0, i,
+ {
+ ECR_join (u, (ECR) splay_tree_lookup (ECR_mapping, i)->value);
+ });
+ bitmap_clear (e2->pending);
+ e2->pending = NULL;
+ }
+
+ }
+ else
+ {
+ ALIAS_TYPE_UNIFY (t1, t2);
+ }
+ }
+ }
+
+ void
+ ECR_set_type (e1, t)
+ ECR e1;
+ alias_type t;
+ {
+ ECR rep = ECR_find (e1);
+ rep->type = t;
+ if (e1->pending != NULL)
+ {
+ int i;
+ EXECUTE_IF_SET_IN_BITMAP (e1->pending, 0, i,
+ {
+ ECR_join (e1, (ECR) splay_tree_lookup (ECR_mapping, i)->value);
+ });
+ bitmap_clear (e1->pending);
+ e1->pending = NULL;
+ }
+ }
Index: tree-alias-ecr.h
===================================================================
RCS file: tree-alias-ecr.h
diff -N tree-alias-ecr.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-alias-ecr.h 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,33 ----
+ #ifndef TREE_ALIAS_ECR_H_
+ #define TREE_ALIAS_ECR_H_
+ #include "bitmap.h"
+ #include "disjoint-set.h"
+ #include "tree-alias-type.h"
+
+ struct ECR_def GTY (())
+ {
+ struct disjoint_set_def set;
+ alias_type type;
+ bitmap pending;
+ unsigned int color;
+ unsigned int id;
+ alias_typevar var;
+ };
+
+ ECR ECR_new PARAMS ((void));
+ ECR ECR_new_with_type PARAMS ((alias_type, alias_typevar));
+ alias_type ECR_get_type PARAMS ((ECR));
+ #define ECR_get_id(x) ((x)->id)
+ int ECR_get_setid PARAMS ((ECR));
+ #define ECR_get_typevar(x) ((x)->var)
+ void ECR_union_pending_sets PARAMS ((ECR, ECR, ECR));
+ void ECR_cjoin PARAMS ((ECR, ECR));
+ void ECR_join PARAMS ((ECR, ECR));
+ void ECR_set_type PARAMS ((ECR, alias_type));
+ #define ECR_find(x) ((ECR) disjoint_set_find ((disjoint_set)(x)))
+ #define ECR_union(x,y) ((ECR) disjoint_set_union ((disjoint_set)(x), (disjoint_set)(y)))
+ #define ECR_equiv(x,y) (disjoint_set_equiv ((disjoint_set)(x), (disjoint_set)(y)))
+ #define ECR_size(x) (disjoint_set_size ((disjoint_set)(x)))
+ #define ECR_elems(x) (disjoint_set_elems ((disjoint_set)(x)))
+
+ #endif
Index: tree-alias-steen.c
===================================================================
RCS file: tree-alias-steen.c
diff -N tree-alias-steen.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-alias-steen.c 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,1142 ----
+ #include "config.h"
+ #include "system.h"
+ #include "ggc.h"
+ #include "tree-alias-type.h"
+ #include "tree-alias-ecr.h"
+ #include "tree-alias-steen.h"
+
+ #include "flags.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "errors.h"
+ #include "expr.h"
+ #include "diagnostic.h"
+ #include "tree-optimize.h"
+ #include "tree-flow.h"
+ #include "tree-inline.h"
+ #include "ssa.h"
+ #include "varray.h"
+ #include "c-tree.h"
+ #include "tree-simple.h"
+ #include "hashtab.h"
+ #include "splay-tree.h"
+ /* Steensgaard's almost-linear interprocedural points-to analysis.
+ This is a flow-insensitive, context insensitive algorithm. It
+ also does not distinguish structure fields, or direction of
+ assignments.
+ It works through non-standard type inferencing.
+ By non-standard types, we do not mean "integer, float", etc. The
+ types here represent sets of abstract locations, including
+ relations between abstract locations (thus modeling the store).
+
+ We then perform type inferencing, which attempts to infer the
+ non-standard types involved in each expression, and get the
+ points-to sets as a result (Since the types represent the store
+ locations).
+
+ See "Points-to analysis in almost linear time." by Bjarne
+ Steensgaard. */
+ static splay_tree alias_annot;
+ static GTY ((param_is (struct alias_typevar_def))) varray_type alias_vars = NULL;
+ static varray_type local_alias_vars;
+ static varray_type local_alias_varnums;
+ #include "gt-tree-alias-steen.h"
+ #define STEEN_DEBUG 1
+ static void steen_simple_assign PARAMS ((struct tree_alias_ops *,
+ alias_typevar, alias_typevar));
+ static void steen_addr_assign PARAMS ((struct tree_alias_ops *,
+ alias_typevar, alias_typevar));
+ static void steen_ptr_assign PARAMS ((struct tree_alias_ops *,
+ alias_typevar, alias_typevar));
+ static void steen_op_assign PARAMS ((struct tree_alias_ops *,
+ alias_typevar, varray_type));
+ static void steen_heap_assign PARAMS ((struct tree_alias_ops *,
+ alias_typevar));
+ static void steen_assign_ptr PARAMS ((struct tree_alias_ops *,
+ alias_typevar, alias_typevar));
+ static void steen_function_def PARAMS ((struct tree_alias_ops *,
+ alias_typevar, varray_type,
+ alias_typevar));
+ static void steen_function_call PARAMS ((struct tree_alias_ops *,
+ alias_typevar, alias_typevar,
+ varray_type));
+ static void steen_init PARAMS ((struct tree_alias_ops *));
+ static void steen_cleanup PARAMS ((struct tree_alias_ops *));
+ static alias_typevar steen_add_var PARAMS ((struct tree_alias_ops *, tree));
+ static alias_typevar steen_add_var_same PARAMS ((struct tree_alias_ops *,
+ tree, alias_typevar));
+ static alias_typevar get_alias_var_decl PARAMS ((tree));
+ static alias_typevar get_alias_var PARAMS ((tree));
+ static tree find_func_aliases PARAMS ((tree *, int *, void *));
+ static tree find_func_decls PARAMS ((tree *, int *, void *));
+ static alias_typevar create_fun_alias_var PARAMS ((tree, int));
+ static alias_typevar create_alias_var PARAMS ((tree));
+
+ static struct tree_alias_ops steen_ops = {
+ steen_init,
+ steen_cleanup,
+ steen_add_var,
+ steen_add_var_same,
+ steen_simple_assign,
+ steen_addr_assign,
+ steen_ptr_assign,
+ steen_op_assign,
+ steen_heap_assign,
+ steen_assign_ptr,
+ steen_function_def,
+ steen_function_call,
+ 0
+ };
+ struct tree_alias_ops *steen_alias_ops = &steen_ops;
+
+ /* Initialize Steensgaard alias analysis.
+ Currently does nothing. */
+ static void
+ steen_init (ops)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ {
+ }
+
+ /* Cleanup after Steensgaard alias analysis.
+ Currently does nothing. */
+ static void
+ steen_cleanup (ops)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ {
+ }
+
+ /* Add decl to the analyzer, and return a typevar for it. For
+ Steensgaard, we create a new alias typevar for the declaration, and
+ return that. */
+
+ static alias_typevar
+ steen_add_var (ops, decl)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ tree decl;
+ {
+ #if STEEN_DEBUG
+ fprintf (stderr, "Steen: Adding variable " );
+ print_c_node (stderr, decl);
+ fprintf (stderr, "\n");
+ #endif
+ return alias_tvar_new (decl);
+
+ }
+
+ /* Add a variable to the analyzer that is equivalent (as far as
+ aliases go) to some existing typevar.
+ For Steensgaard, we just call a function that does this for us. */
+ static alias_typevar
+ steen_add_var_same (ops, decl, tv)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ tree decl;
+ alias_typevar tv;
+ {
+ #if STEEN_DEBUG
+ fprintf (stderr, "Steen: Adding variable " );
+ print_c_node (stderr, decl);
+ fprintf (stderr, " same as ");
+ print_c_node (stderr, tv->decl);
+ fprintf (stderr, "\n");
+ #endif
+ return alias_tvar_new_equiv_to (decl, tv);
+ }
+
+ /* Inference for simple assignment (lhs = rhs) */
+ static void
+ steen_simple_assign (ops, lhs, rhs)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar lhs;
+ alias_typevar rhs;
+ {
+ alias_type type1, type2;
+ ECR tau1, tau2, lambda1, lambda2;
+
+ #if STEEN_DEBUG
+ fprintf (stderr, "Steen: simple assignment ");
+ print_c_node (stderr, lhs->decl);
+ fprintf (stderr, " = ");
+ print_c_node (stderr, rhs->decl);
+ fprintf (stderr, "\n");
+ #endif
+
+ /* Get the non-standard types involved. */
+ type1 = ECR_get_type (alias_tvar_get_ECR (lhs));
+ type2 = ECR_get_type (alias_tvar_get_ECR (rhs));
+
+ /* Conditionally join the locations those types represent, if they
+ aren't equivalent. */
+ tau1 = alias_ltype_loc (type1);
+ tau2 = alias_ltype_loc (type2);
+ if (!ECR_equiv (tau1, tau2))
+ ECR_cjoin (tau1, tau2);
+
+ /* Ditto on the functions. */
+ lambda1 = alias_ltype_func (type1);
+ lambda2 = alias_ltype_func (type2);
+ if (!ECR_equiv (lambda1, lambda2))
+ ECR_cjoin (lambda1, lambda2);
+ }
+
+ /* Inference for address assignment (lhs = &addr) */
+ static void
+ steen_addr_assign (ops, lhs, addr)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar lhs;
+ alias_typevar addr;
+ {
+ alias_type type1;
+ ECR tau1, tau2;
+
+ if (addr == NULL)
+ return;
+
+ #if STEEN_DEBUG
+ fprintf (stderr, "Steen: address assignment ");
+ print_c_node (stderr, lhs->decl);
+ fprintf (stderr, " = &");
+ print_c_node (stderr, addr->decl);
+ fprintf (stderr, "\n");
+ #endif
+
+ /* Get the non-standard type for the lhs. */
+ type1 = ECR_get_type (alias_tvar_get_ECR (lhs));
+
+ /* Get the location set for the lhs's non-std type, and if it's not
+ equivalent to the ADDR's ECR (rather than that ECR's set of
+ locations), join them. */
+ tau1 = alias_ltype_loc (type1);
+ tau2 = alias_tvar_get_ECR (addr);
+ if (!ECR_equiv (tau1, tau2))
+ ECR_join (tau1, tau2);
+ }
+
+
+ /* Inference for pointer assignment (lhs = *ptr) */
+ static void
+ steen_ptr_assign (ops, lhs, ptr)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar lhs;
+ alias_typevar ptr;
+ {
+ alias_type type1, type2;
+ ECR tau1, tau2, lambda1;
+
+ if (ptr == NULL)
+ return;
+ #if STEEN_DEBUG
+ fprintf (stderr, "Steen: pointer assignment ");
+ print_c_node (stderr, lhs->decl);
+ fprintf (stderr, " = *");
+ print_c_node (stderr, ptr->decl);
+ fprintf (stderr, "\n");
+ #endif
+
+ /* Get the non-standard types for the lhs, and the ptr. */
+ type1 = ECR_get_type (alias_tvar_get_ECR (lhs));
+ type2 = ECR_get_type (alias_tvar_get_ECR (ptr));
+
+ /* Get the location sets for those types, and the function for the
+ lhs. */
+ tau1 = alias_ltype_loc (type1);
+ tau2 = alias_ltype_loc (type2);
+ lambda1 = alias_ltype_func (type1);
+
+ /* If ptr is BOTTOM, then set ptr's non-std type to type1 (since
+ we consider assignments transitive, and we have nothing to
+ join). */
+ if (ECR_get_type (tau2) == alias_bottom)
+ {
+ ECR_set_type (tau2, type1);
+ }
+ /* Otherwise, get the location set for tau2's type (tau2 is the non-std type
+ representing the things type2 could point to), which is the
+ location set that could be pointed to by the locations of type2
+ (IE location set for things *ptr could point to), and cjoin with
+ tau1 it if it's not equivalent. */
+ else
+ {
+ alias_type type3;
+ ECR tau3, lambda3;
+
+ type3 = ECR_get_type (tau2);
+ tau3 = alias_ltype_loc (type3);
+ if (!ECR_equiv (tau1, tau3))
+ ECR_cjoin (tau1, tau3);
+
+ lambda3 = alias_ltype_func (type3);
+ if (!ECR_equiv (lambda1, lambda3))
+ ECR_cjoin (lambda1, lambda3);
+ }
+ }
+
+ /* Inference rule for operations (lhs = operation(operands)) */
+ static void
+ steen_op_assign (ops, lhs, operands)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar lhs;
+ varray_type operands;
+ {
+ size_t i;
+ ECR ecr, tau1, lambda1;
+ alias_type type1;
+
+ #if STEEN_DEBUG
+ fprintf (stderr, "Steen: op assignment ");
+ print_c_node (stderr, lhs->decl);
+ fprintf (stderr, " = op(...)");
+ fprintf (stderr, "\n");
+ #endif
+
+ ecr = alias_tvar_get_ECR (lhs);
+ type1 = ECR_get_type (ecr);
+
+ tau1 = alias_ltype_loc (type1);
+ lambda1 = alias_ltype_func (type1);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (operands); i++)
+ {
+ alias_typevar tv = VARRAY_GENERIC_PTR (operands, i);
+ ECR operand, taui, lambdai;
+ alias_type typei;
+
+ if (tv == NULL)
+ continue;
+
+ operand = alias_tvar_get_ECR (tv);
+ typei = ECR_get_type (operand);
+ taui = alias_ltype_loc (typei);
+ lambdai = alias_ltype_func (typei);
+
+ if (!ECR_equiv (tau1, taui))
+ ECR_cjoin (tau1, taui);
+ if (!ECR_equiv (lambda1, lambdai))
+ ECR_cjoin (lambda1, lambdai);
+ }
+ }
+
+ /* Inference for heap assignment (lhs = alloc) */
+ static void
+ steen_heap_assign (ops, lhs)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar lhs;
+ {
+ alias_type type1;
+ ECR tau;
+ type1 = ECR_get_type (alias_tvar_get_ECR (lhs));
+ tau = alias_ltype_loc (type1);
+
+ if (ECR_get_type (tau) == alias_bottom)
+ ECR_set_type (tau, alias_ltype_new ());
+ }
+
+ /* Inference for assignment to a pointer (*ptr = rhs) */
+ static void
+ steen_assign_ptr (ops, ptr, rhs)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar ptr;
+ alias_typevar rhs;
+ {
+ alias_type type1, type2;
+ ECR tau1, tau2, lambda2;
+
+ if (rhs == NULL)
+ return;
+
+ #if STEEN_DEBUG
+ fprintf (stderr, "Steen: assignment to pointer *");
+ print_c_node (stderr, ptr->decl);
+ fprintf (stderr, " = ");
+ print_c_node (stderr, rhs->decl);
+ fprintf (stderr, "\n");
+ #endif
+ type1 = ECR_get_type (alias_tvar_get_ECR (ptr));
+ type2 = ECR_get_type (alias_tvar_get_ECR (rhs));
+
+ tau1 = alias_ltype_loc (type1);
+ tau2 = alias_ltype_loc (type2);
+ lambda2 = alias_ltype_func (type2);
+
+ if (ECR_get_type (tau1) == alias_bottom)
+ {
+ ECR_set_type (tau1, type2);
+ }
+ else
+ {
+ alias_type type3;
+ ECR tau3, lambda3;
+
+ type3 = ECR_get_type (tau1);
+ tau3 = alias_ltype_loc (type3);
+ lambda3 = alias_ltype_func (type3);
+ if (!ECR_equiv (tau2, tau3))
+ ECR_cjoin (tau3, tau2);
+ if (!ECR_equiv (lambda2, lambda3))
+ ECR_cjoin (lambda3, lambda2);
+ }
+ }
+
+ /* Inference for a function definition. */
+
+ static void
+ steen_function_def (ops, func, params, retval)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar func;
+ varray_type params;
+ alias_typevar retval;
+ {
+ alias_type type;
+ ECR lambda;
+
+ type = ECR_get_type (alias_tvar_get_ECR (func));
+ lambda = alias_ltype_func (type);
+ /* If we've never seen the function before, it'll be alias_bottom. */
+ if (ECR_get_type (lambda) == alias_bottom)
+ {
+ alias_type ftype = alias_ftype_new ();
+ alias_type typea;
+ varray_type *args = &ALIAS_FTYPE_ARGUMENTS (ftype);
+ size_t l = VARRAY_ACTIVE_SIZE (params);
+ size_t i;
+
+ /* Set up the arguments for the new function type. */
+ for (i = 0; i < l; i++)
+ {
+ alias_type newarg;
+ alias_typevar tv = VARRAY_GENERIC_PTR (params, i);
+ typea = ECR_get_type (alias_tvar_get_ECR (tv));
+ newarg = alias_vtype_new_with_lf (alias_ltype_loc (typea),
+ alias_ltype_func (typea));
+ VARRAY_PUSH_GENERIC_PTR (*args, newarg);
+ }
+ /* Set up the return value location. */
+ typea = ECR_get_type (alias_tvar_get_ECR (retval));
+ ALIAS_FTYPE_RETVAL (ftype) =
+ alias_vtype_new_with_lf (alias_ltype_loc (typea),
+ alias_ltype_func (typea));
+ /* Lastly, set the ECR type to the new function type. */
+ ECR_set_type (lambda, ftype);
+ }
+ else
+ {
+ varray_type args = ALIAS_FTYPE_ARGUMENTS (ECR_get_type (lambda));
+ size_t la = VARRAY_ACTIVE_SIZE (args);
+ size_t lp = VARRAY_ACTIVE_SIZE (params);
+ size_t i;
+ ECR tau1, tau2, lambda1, lambda2, alphar;
+ alias_type type1, type2, alpha;
+ #if STEEN_DEBUG
+ fprintf (stderr, "Merging function definitions!\n");
+ #endif
+ /* Number of actual and formal parameters should match */
+ if (lp != la)
+ abort ();
+
+ for (i = 0; i < lp; i++)
+ {
+ type1 = ECR_get_type (alias_tvar_get_ECR ((alias_typevar) VARRAY_GENERIC_PTR (params, i)));
+ type2 = VARRAY_GENERIC_PTR (args, i);
+
+ tau1 = alias_vtype_loc (type1);
+ tau2 = alias_vtype_loc (type2);
+ if (!ECR_equiv (tau1, tau2))
+ ECR_join (tau1, tau2);
+
+ lambda1 = alias_vtype_func (type1);
+ lambda2 = alias_vtype_func (type2);
+ if (!ECR_equiv (lambda1, lambda2))
+ ECR_join (lambda1, lambda2);
+ }
+
+ alpha = ALIAS_FTYPE_RETVAL (ECR_get_type (lambda));
+ alphar = alias_tvar_get_ECR (retval);
+
+ tau1 = alias_vtype_loc (alpha);
+ tau2 = alias_vtype_loc (ECR_get_type (alphar));
+
+ if (!ECR_equiv (tau1, tau2))
+ ECR_join (tau1, tau2);
+
+ lambda1 = alias_vtype_func (alpha);
+ lambda2 = alias_vtype_func (ECR_get_type (alphar));
+ if (!ECR_equiv (lambda1, lambda2))
+ ECR_join (lambda1, lambda2);
+ }
+ }
+
+ /* Inference for a function call assignment */
+ static void
+ steen_function_call (ops, lhs, func, args)
+ struct tree_alias_ops *ops ATTRIBUTE_UNUSED;
+ alias_typevar lhs;
+ alias_typevar func;
+ varray_type args;
+ {
+ alias_type type, type1;
+ ECR lambda;
+ varray_type largs;
+ size_t l1, la;
+ size_t i;
+
+ type = ECR_get_type (alias_tvar_get_ECR (func));
+ lambda = alias_ltype_func (type);
+
+ if (ECR_get_type (lambda) == alias_bottom)
+ {
+ alias_type lam = alias_ftype_new ();
+
+ alias_ftype_add_new_arguments (lam, VARRAY_ACTIVE_SIZE (args));
+ ALIAS_FTYPE_RETVAL (lam) = alias_vtype_new ();
+ ECR_set_type (lambda, lam);
+ }
+ largs = ALIAS_FTYPE_ARGUMENTS (ECR_get_type (lambda));
+ l1 = VARRAY_ACTIVE_SIZE (largs);
+ la = VARRAY_ACTIVE_SIZE (args);
+ type1 = NULL;
+
+ if ((l1 <= 0) && (la > 0))
+ abort ();
+
+ for (i = 0; i < la; i++)
+ {
+ alias_type type2;
+ ECR tau1, tau2;
+ ECR lambda1, lambda2;
+ alias_typevar tvar;
+
+ if (i < l1)
+ type1 = VARRAY_GENERIC_PTR (largs, i);
+
+ tvar = VARRAY_GENERIC_PTR (args, i);
+
+ type2 = ECR_get_type (alias_tvar_get_ECR (tvar));
+
+
+ tau1 = alias_vtype_loc (type1);
+ tau2 = alias_ltype_loc (type2);
+ if (!ECR_equiv (tau1, tau2))
+ ECR_cjoin (tau1, tau2);
+
+ lambda1 = alias_vtype_func (type1);
+ lambda2 = alias_ltype_func (type2);
+ if (!ECR_equiv (lambda1, lambda2))
+ ECR_cjoin (lambda1, lambda2);
+ }
+
+ if (lhs != NULL)
+ {
+ alias_type alpha;
+ ECR alphar;
+ ECR tau1, tau2;
+ ECR lambda1, lambda2;
+
+ alpha = ALIAS_FTYPE_RETVAL (ECR_get_type (lambda));
+ alphar = alias_tvar_get_ECR (lhs);
+
+ tau1 = alias_vtype_loc (alpha);
+ tau2 = alias_ltype_loc (ECR_get_type (alphar));
+ if (!ECR_equiv (tau1, tau2))
+ ECR_cjoin (tau1, tau2);
+
+ lambda1 = alias_vtype_func (alpha);
+ lambda2 = alias_ltype_func (ECR_get_type (alphar));
+ if (!ECR_equiv (lambda1, lambda2))
+ ECR_cjoin (lambda1, lambda2);
+ }
+ }
+
+ extern int next_color;
+ void test_assign PARAMS((void));
+
+ /* Test Steensgaard points-to alias through a series of simple
+ assignments. */
+ void
+ test_assign ()
+ {
+ alias_typevar a, b, c, d;
+ varray_type temp;
+ init_ggc ();
+ /* Simulate variable creation for variables a,b,c,d */
+ a = alias_tvar_new (NULL);
+ b = alias_tvar_new (NULL);
+ c = alias_tvar_new (NULL);
+ d = alias_tvar_new (NULL);
+
+ /* a = &b */
+ steen_addr_assign (0, a, b);
+ temp = alias_tvar_pointsto (a);
+ VARRAY_CLEAR (temp);
+
+ /* c = &b */
+ steen_addr_assign (0, c, b);
+ temp = alias_tvar_pointsto (c);
+ VARRAY_CLEAR (temp);
+
+ /* d = a */
+ steen_simple_assign (0, d, a);
+ temp = alias_tvar_pointsto (d);
+ VARRAY_CLEAR (temp);
+
+ /* Now get all the points to sets */
+ VARRAY_GENERIC_PTR_INIT (temp, 1, "all points to");
+ alias_tvar_allpointsto (d, &temp);
+ VARRAY_CLEAR (temp);
+ next_color++;
+ VARRAY_GENERIC_PTR_INIT (temp, 1, "all points to");
+ alias_tvar_allpointsto (c, &temp);
+ VARRAY_CLEAR (temp);
+ next_color++;
+ VARRAY_GENERIC_PTR_INIT (temp, 1, "all points to");
+ alias_tvar_allpointsto (b, &temp);
+ VARRAY_CLEAR (temp);
+ next_color++;
+ VARRAY_GENERIC_PTR_INIT (temp, 1, "all points to");
+ alias_tvar_allpointsto (a, &temp);
+ }
+
+ static alias_typevar
+ get_alias_var_decl (decl)
+ tree decl;
+ {
+ splay_tree_node node;
+ node = splay_tree_lookup (alias_annot, (splay_tree_key) decl);
+ if (node != NULL && node->value != 0)
+ return (alias_typevar) node->value;
+ /* For debugging, remove this, and re-enable the find_func_decls call. */
+ return create_alias_var (decl);
+ abort ();
+ }
+
+ static alias_typevar
+ get_alias_var (expr)
+ tree expr;
+ {
+ alias_typevar tvar;
+ splay_tree_node node;
+
+ node = splay_tree_lookup (alias_annot, (splay_tree_key) expr);
+
+
+ /* If it's a decl, get the alias var of the decl. We farm this off
+ to get_alias_var_decl so it can abort if the alias var doesn't
+ exist, and in case something else *knows* it has a decl, and
+ wants the alias var. */
+
+ if (DECL_P (expr))
+ return get_alias_var_decl (expr);
+
+ /* Non-DECL's alias vars must be temporary alias vars for an
+ expression, since we never create non-temporary ones on anything
+ but DECL's.
+ Since they are temporary, we want to erase it from the annotation
+ since they are use once. */
+
+ if (node != NULL && node->value != 0)
+ {
+ tvar = (alias_typevar) node->value;
+ splay_tree_remove (alias_annot, (splay_tree_key)expr);
+ return tvar;
+ }
+
+ /* True constants have no aliases (unless modifiable strings are on,
+ in which case i don't think we'll end up with a STRING_CST anyway) */
+ if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
+ return NULL;
+
+
+ switch (TREE_CODE (expr))
+ {
+ case ARRAY_REF:
+ {
+ /* Find the first non-array ref, and return it's alias
+ variable */
+ tree p;
+ for (p = expr; TREE_CODE (p) == ARRAY_REF;
+ p = TREE_OPERAND (p, 0));
+ return get_alias_var (p);
+ }
+ break;
+
+ case COMPONENT_REF:
+ {
+ /* Find the first non-component ref, and return it's alias
+ variable */
+ tree p;
+ for (p = expr; TREE_CODE (p) == COMPONENT_REF;
+ p = TREE_OPERAND (p, 0));
+ return get_alias_var (p);
+ }
+ break;
+
+ case NOP_EXPR:
+ case CONVERT_EXPR:
+ case FIX_TRUNC_EXPR:
+ case FIX_CEIL_EXPR:
+ case FIX_FLOOR_EXPR:
+ case FIX_ROUND_EXPR:
+ case ADDR_EXPR:
+ case INDIRECT_REF:
+ /* If it's a ref or cast or conversion of sometmhing, get the
+ alias var of the something. */
+ return get_alias_var (TREE_OPERAND (expr, 0));
+ break;
+
+ default:
+ {
+ /* Otherwise, we need a new temporary alias variable for this
+ expression. */
+ alias_typevar tempvar
+ = steen_alias_ops->add_var (steen_alias_ops,
+ create_tmp_alias_var
+ (void_type_node,
+ "aliastmp"));
+ return tempvar;
+ }
+ }
+ }
+ static tree
+ find_func_aliases (tp, walk_subtrees, data)
+ tree *tp;
+ int *walk_subtrees ATTRIBUTE_UNUSED;
+ void *data ATTRIBUTE_UNUSED;
+ {
+ if (TREE_CODE (*tp) == SCOPE_STMT)
+ {
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+
+ if (is_simple_modify_expr (*tp))
+ {
+ tree op0, op1;
+ alias_typevar lhsAV = NULL;
+ alias_typevar rhsAV = NULL;
+
+ *walk_subtrees = 0;
+ op0 = TREE_OPERAND (*tp, 0);
+ STRIP_NOPS (op0);
+ op1 = TREE_OPERAND (*tp, 1);
+ STRIP_NOPS (op1);
+
+ /* lhsAV should always have an alias variable */
+ lhsAV = get_alias_var (op0);
+ /* rhsAV might not have one, c.f. c = 5 */
+ rhsAV = get_alias_var (op1);
+
+ /* You would think we could test rhsAV at the top, rather than
+ 50 separate times, but we can't, because it can be NULL for
+ operator assignments, where we'd still collect the individual
+ alias typevars for the operator. */
+
+ /* Note that structures are treated as a single alias
+ variable, since we can disambiguate based on TBAA first,
+ and fall back on points-to. */
+ /* x = <something> */
+ if (is_simple_varname (op0))
+ {
+ /* x = y or x = foo.y */
+ if (is_simple_varname (op1))
+ {
+ if (rhsAV != NULL)
+ steen_alias_ops->simple_assign (steen_alias_ops, lhsAV,
+ rhsAV);
+ }
+ /* x = *y or x = foo->y */
+ else if (TREE_CODE (op1) == INDIRECT_REF
+ && is_simple_varname (TREE_OPERAND (op1, 0)))
+ {
+ if (rhsAV != NULL)
+ steen_alias_ops->ptr_assign (steen_alias_ops, lhsAV,
+ rhsAV);
+ }
+ /* x = &y = x = &foo.y */
+ else if (TREE_CODE (op1) == ADDR_EXPR
+ && is_simple_varname (TREE_OPERAND (op1, 0)))
+ {
+ if (rhsAV != NULL)
+ steen_alias_ops->addr_assign (steen_alias_ops, lhsAV,
+ rhsAV);
+ }
+ /* x = func(...) */
+ else if (is_simple_call_expr (op1))
+ {
+ /* Heap assignment. These are __attribute__ malloc or
+ something, i'll deal with it later. */
+ if (0)
+ {}
+ else
+ {
+ varray_type args;
+ tree arg;
+ tree callop0, callop1;
+ VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
+
+ callop1 = TREE_OPERAND (op1, 1);
+ callop0 = TREE_OPERAND (op1, 0);
+ for (arg = callop1;
+ arg;
+ arg = TREE_CHAIN (arg))
+ {
+ alias_typevar aav = get_alias_var (TREE_VALUE (arg));
+ if (aav)
+ VARRAY_PUSH_GENERIC_PTR (args, aav);
+
+ }
+ create_fun_alias_var (TREE_OPERAND (callop0, 0), 0);
+ steen_alias_ops->function_call (steen_alias_ops, lhsAV,
+ get_alias_var (callop0),
+ args);
+ /* FIXME: If this is the non-interprocedural
+ version, or we don't have the alias info for the
+ called function, we need to handle it.
+ In particular, the actual arguments can alias
+ each other, and could take the address of any
+ global. */
+
+ }
+
+ }
+ /* x = op (...) */
+ else
+ {
+ switch (TREE_CODE_CLASS (TREE_CODE (op1)))
+ {
+ case 'e': /* an expression */
+ case 's': /* an expression with side effects */
+ case '<': /* a comparison expression */
+ case '1': /* a unary arithmetic expression */
+ case 'r': /* a reference */
+ case '2': /* a binary arithmetic expression */
+ {
+ tree op;
+ varray_type ops;
+ int i;
+ VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
+ for (i=0; i < TREE_CODE_LENGTH (TREE_CODE (op1)); i++)
+ {
+ alias_typevar aav;
+ op = TREE_OPERAND (op1, i);
+ aav = get_alias_var (op);
+ if (aav)
+ VARRAY_PUSH_GENERIC_PTR (ops, aav);
+ }
+ steen_alias_ops->op_assign (steen_alias_ops, lhsAV,
+ ops);
+ }
+ break;
+ default:
+ break;
+ }
+ }
+ }
+ /* *x = <something> */
+ else
+ {
+ /* x.f = y or x->f = y */
+ if (TREE_CODE (op0) == COMPONENT_REF)
+ {
+ if (rhsAV != NULL)
+ steen_alias_ops->simple_assign (steen_alias_ops, lhsAV,
+ rhsAV);
+ }
+ /* *x.f = y or *x->f = y */
+ else if (TREE_CODE (op0) == INDIRECT_REF
+ && TREE_CODE (TREE_OPERAND (op0, 0)) == COMPONENT_REF)
+ {
+ if (rhsAV != NULL)
+ steen_alias_ops->assign_ptr (steen_alias_ops, lhsAV,
+ rhsAV);
+ }
+ /* *x = <something else */
+ else
+ {
+ if (rhsAV != NULL)
+ steen_alias_ops->assign_ptr (steen_alias_ops, lhsAV,
+ rhsAV);
+ }
+ }
+ }
+ /* Calls without return values. */
+ else if (is_simple_call_expr (*tp))
+ {
+ varray_type args;
+ tree arg;
+ VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
+ for (arg = TREE_OPERAND (*tp, 1); arg; arg = TREE_CHAIN (arg))
+ {
+ alias_typevar aav = get_alias_var (TREE_VALUE (arg));
+ if (aav)
+ VARRAY_PUSH_GENERIC_PTR (args, aav);
+ }
+ create_fun_alias_var (TREE_OPERAND (TREE_OPERAND (*tp, 0), 0), 0);
+ steen_alias_ops->function_call (steen_alias_ops, NULL,
+ get_alias_var (TREE_OPERAND (*tp, 0)),
+ args);
+ /* FIXME: Same caveats as above for calls to functions we have no
+ alias variables for. */
+
+ }
+
+ return NULL_TREE;
+ }
+
+ static tree
+ find_func_decls (tp, walk_subtrees, data)
+ tree *tp;
+ int *walk_subtrees ATTRIBUTE_UNUSED;
+ void *data ATTRIBUTE_UNUSED;
+ {
+ if (TREE_CODE (*tp) == DECL_STMT)
+ {
+ create_alias_var (DECL_STMT_DECL (*tp));
+ VARRAY_PUSH_INT (local_alias_varnums, VARRAY_ACTIVE_SIZE (alias_vars) - 1);
+ #if STEEN_DEBUG
+ fprintf (stderr, "adding ");
+ print_c_node (stderr, DECL_STMT_DECL (*tp));
+ fprintf (stderr, " to list of local alias vars.\n");
+ #endif
+ VARRAY_PUSH_GENERIC_PTR (local_alias_vars, DECL_STMT_DECL (*tp));
+ }
+ return NULL_TREE;
+ }
+
+ /*
+ Create the alias variables for a function definition.
+
+ This includes:
+ 1. The function itself.
+ 2. The arguments.
+ 3. The locals.
+ 4. The return value.
+ */
+ static alias_typevar
+ create_fun_alias_var (decl, force)
+ tree decl;
+ int force;
+ {
+ alias_typevar avar, retvar;
+ tree rdecl;
+ varray_type params = NULL;
+ splay_tree_node node;
+ node = splay_tree_lookup (alias_annot, (splay_tree_key) decl);
+ if (!force)
+ {
+ if (node != NULL && node->value != 0)
+ return (alias_typevar) node->value;
+ }
+
+ VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
+ if (DECL_ARGUMENTS (decl) != NULL)
+ {
+ tree arg;
+ for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
+ {
+ alias_typevar tvar = create_alias_var (arg);
+ splay_tree_insert (alias_annot, (splay_tree_key) arg, (splay_tree_value) tvar);
+ VARRAY_PUSH_GENERIC_PTR (params, tvar);
+ }
+ }
+ else if (TYPE_ARG_TYPES (TREE_TYPE (decl)) != NULL)
+ {
+ tree arg;
+ /* FIXME: Handle varargs */
+ for (arg = TYPE_ARG_TYPES (TREE_TYPE (decl));
+ arg && TREE_VALUE (arg) != void_type_node;
+ arg = TREE_CHAIN (arg))
+ {
+ tree fakedecl = create_tmp_alias_var (TREE_VALUE (arg), "normarg");
+ alias_typevar tvar = create_alias_var (fakedecl);
+ VARRAY_PUSH_GENERIC_PTR (params, tvar);
+ }
+ }
+ /* Functions declared like void f() are *not* equivalent to void
+ f(void). You can pass an argument to them. Thus, we need to
+ create some fake argument that would alias any actuals that get
+ passed to our function. */
+ else
+ {
+ tree fakedecl = create_tmp_alias_var (void_type_node, "fakearg");
+ alias_typevar fakevar = create_alias_var (fakedecl);
+ VARRAY_PUSH_GENERIC_PTR (params, fakevar);
+ }
+
+ rdecl = create_tmp_alias_var (TREE_TYPE (TREE_TYPE (decl)), "_rv_");
+ retvar = steen_alias_ops->add_var (steen_alias_ops, rdecl);
+ VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
+ avar = steen_alias_ops->add_var (steen_alias_ops, decl);
+ VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
+
+ steen_alias_ops->function_def (steen_alias_ops, avar, params, retvar);
+ #if 0
+ if (node)
+ {
+ ECR tau1, tau2;
+ tau1 = alias_tvar_get_ECR ((alias_typevar)node->value);
+ tau2 = alias_tvar_get_ECR (avar);
+ if (!ECR_equiv (tau1, tau2))
+ ECR_join (tau1, tau2);
+ }
+ #endif
+ splay_tree_insert (alias_annot, (splay_tree_key) decl,
+ (splay_tree_value) avar);
+ /* FIXME: Also, if this is a defining declaration then add the annotation
+ to all extern definitions of the function. */
+ return avar;
+ }
+
+ /*
+ Create the alias variables for a ptf.
+
+ This includes:
+ 1. The function itself.
+ 2. The arguments.
+ 3. The return value.
+ */
+ static alias_typevar
+ create_fun_alias_var_ptf (decl, type)
+ tree decl;
+ tree type;
+ {
+ alias_typevar avar, retvar;
+ tree rdecl;
+ varray_type params = NULL;
+ splay_tree_node node;
+
+ node = splay_tree_lookup (alias_annot, (splay_tree_key) decl);
+
+ if (node != NULL && node->value != 0)
+ return (alias_typevar) node->value;
+
+ VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
+
+ if (TYPE_ARG_TYPES (type) != NULL)
+ {
+ tree arg;
+ /* FIXME: Handle varargs */
+ for (arg = TYPE_ARG_TYPES (type);
+ arg && TREE_VALUE (arg) != void_type_node;
+ arg = TREE_CHAIN (arg))
+ {
+ tree fakedecl = create_tmp_alias_var (TREE_VALUE (arg), "ptfarg");
+ alias_typevar tvar = create_alias_var (fakedecl);
+ VARRAY_PUSH_GENERIC_PTR (params, tvar);
+ }
+ }
+ /* Functions declared like void f() are *not* equivalent to void
+ f(void). You can pass an argument to them. Thus, we need to
+ create some fake argument that would alias any actuals that get
+ passed to our function. */
+ else
+ {
+ tree fakedecl = create_tmp_alias_var (void_type_node, "fakearg");
+ alias_typevar fakevar = create_alias_var (fakedecl);
+ VARRAY_PUSH_GENERIC_PTR (params, fakevar);
+ }
+
+ rdecl = create_tmp_alias_var (TREE_TYPE (type), "_rv_");
+ retvar = steen_alias_ops->add_var (steen_alias_ops, rdecl);
+ VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
+
+ avar = steen_alias_ops->add_var (steen_alias_ops, decl);
+ VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
+
+ steen_alias_ops->function_def (steen_alias_ops, avar, params, retvar);
+ splay_tree_insert (alias_annot, (splay_tree_key) decl,
+ (splay_tree_value) avar);
+
+ return avar;
+ }
+
+ static alias_typevar
+ create_alias_var (decl)
+ tree decl;
+ {
+ splay_tree_node node;
+ alias_typevar avar;
+
+
+ node = splay_tree_lookup (alias_annot, (splay_tree_key)decl);
+
+ if (node != NULL && node->value != 0)
+ return (alias_typevar) node->value;
+
+ /* FIXME: Need to handle creating alias variables for PTF's. The
+ cleanest way is to make create_fun_alias_var take 2 arguments:
+ 1. The function variable decl (IE the name in the case of normal
+ function, the PTF variable's name in the case of PTF's)
+ 2. The function type.
+
+ */
+ if (TREE_CODE (TREE_TYPE (decl)) == POINTER_TYPE)
+ if (TREE_CODE (TREE_TYPE (TREE_TYPE (decl))) == FUNCTION_TYPE)
+ create_fun_alias_var_ptf (decl, TREE_TYPE (TREE_TYPE (decl)));
+
+ avar = steen_alias_ops->add_var (steen_alias_ops, decl);
+ splay_tree_insert (alias_annot, (splay_tree_key)decl,
+ (splay_tree_value) avar);
+ VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
+
+ /* FIXME: Add the annotation to all extern definitions of this variable. */
+ return avar;
+ }
+
+ static unsigned int splaycount = 0;
+ static int splay_tree_count PARAMS ((splay_tree_node, void *));
+ unsigned int splay_tree_size PARAMS ((splay_tree));
+
+ static int
+ splay_tree_count (node, data)
+ splay_tree_node node ATTRIBUTE_UNUSED;
+ void *data ATTRIBUTE_UNUSED;
+ {
+ splaycount++;
+ return 0;
+ }
+
+ unsigned int
+ splay_tree_size (st)
+ splay_tree st;
+ {
+ splaycount = 0;
+ splay_tree_foreach (st, splay_tree_count, NULL);
+ return splaycount;
+ }
+
+ void
+ create_alias_vars ()
+ {
+ size_t i;
+ tree currdecl = getdecls ();
+ init_alias_vars ();
+
+ while (currdecl)
+ {
+ if (TREE_CODE (currdecl) == VAR_DECL)
+ create_alias_var (currdecl);
+ currdecl = TREE_CHAIN (currdecl);
+ }
+ create_fun_alias_var (current_function_decl, 1);
+ /* For debugging, disable the on-the-fly variable creation, and reenable this. */
+ /* walk_tree_without_duplicates (&DECL_SAVED_TREE (current_function_decl),
+ find_func_decls, NULL);*/
+ walk_tree_without_duplicates (&DECL_SAVED_TREE (current_function_decl),
+ find_func_aliases, NULL);
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_vars); i++)
+ splay_tree_remove (alias_annot, (splay_tree_key) VARRAY_GENERIC_PTR (local_alias_vars, i));
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_varnums); i ++)
+ VARRAY_GENERIC_PTR (alias_vars, VARRAY_INT (local_alias_varnums, i)) = NULL;
+ }
+ void
+ init_alias_vars ()
+ {
+ init_alias_type ();
+ VARRAY_GENERIC_PTR_INIT (local_alias_vars, 10, "Local alias vars");
+ VARRAY_INT_INIT (local_alias_varnums, 10, "Local alias varnums");
+ if (alias_vars == NULL)
+ VARRAY_GENERIC_PTR_INIT (alias_vars, 10, "Alias vars");
+ if (alias_annot == NULL)
+ alias_annot = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
+ }
Index: tree-alias-steen.h
===================================================================
RCS file: tree-alias-steen.h
diff -N tree-alias-steen.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-alias-steen.h 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,28 ----
+ #ifndef TREE_ALIAS_STEEN
+ #define TREE_ALIAS_STEEN
+ #include "tree-alias-ecr.h"
+ #include "tree-alias-type.h"
+ struct tree_alias_ops
+ {
+ void (*init) (struct tree_alias_ops *);
+ void (*cleanup) (struct tree_alias_ops *);
+ alias_typevar (*add_var) (struct tree_alias_ops *, tree);
+ alias_typevar (*add_var_same) (struct tree_alias_ops *, tree,
+ alias_typevar);
+ void (*simple_assign) (struct tree_alias_ops *, alias_typevar,
+ alias_typevar);
+ void (*addr_assign) (struct tree_alias_ops *, alias_typevar, alias_typevar);
+ void (*ptr_assign) (struct tree_alias_ops *, alias_typevar, alias_typevar);
+ void (*op_assign) (struct tree_alias_ops *, alias_typevar, varray_type);
+ void (*heap_assign) (struct tree_alias_ops *, alias_typevar);
+ void (*assign_ptr) (struct tree_alias_ops *, alias_typevar, alias_typevar);
+ void (*function_def) (struct tree_alias_ops *, alias_typevar,
+ varray_type, alias_typevar);
+ void (*function_call) (struct tree_alias_ops *, alias_typevar,
+ alias_typevar, varray_type);
+ void *data;
+ };
+ extern struct tree_alias_ops *steen_alias_ops;
+ extern void create_alias_vars PARAMS ((void));
+ extern void init_alias_vars PARAMS ((void));
+ #endif
Index: tree-alias-type.c
===================================================================
RCS file: tree-alias-type.c
diff -N tree-alias-type.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-alias-type.c 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,382 ----
+
+ #include "config.h"
+ #include "system.h"
+ #include "ggc.h"
+ #include "tree-alias-type.h"
+ #include "tree-alias-ecr.h"
+
+ static unsigned int alias_type_num = 1;
+
+ /* For walking operations, we color the alias types rather than have
+ to reset marks. */
+
+ unsigned int next_color = 1;
+
+ static void void_unify PARAMS ((alias_type, alias_type));
+ static varray_type null_pointsto PARAMS ((alias_type));
+ static void location_unify PARAMS ((alias_type, alias_type));
+ static varray_type location_pointsto PARAMS ((alias_type));
+ static void function_unify PARAMS ((alias_type, alias_type));
+ static varray_type function_pointsto PARAMS ((alias_type));
+
+ /* BOTTOM */
+ alias_type alias_bottom = NULL;
+
+ void
+ init_alias_type ()
+ {
+ if (!alias_bottom)
+ {
+ alias_bottom = ggc_alloc (sizeof (union alias_type_def));
+ alias_bottom->common.kind = BOTTOM_ATYPE;
+ alias_bottom->common.id = 0;
+ alias_bottom->common.pointsto = null_pointsto;
+ alias_bottom->common.unify = void_unify;
+ }
+ }
+
+ /* Unification routine that does nothing. */
+ static void
+ void_unify (a, b)
+ alias_type a ATTRIBUTE_UNUSED;
+ alias_type b ATTRIBUTE_UNUSED;
+ {
+ }
+
+ /* Points-to routine that returns an empty points-to set. */
+ static varray_type
+ null_pointsto (a)
+ alias_type a ATTRIBUTE_UNUSED;
+ {
+ return NULL;
+ }
+
+ /* Create a new alias value type */
+ alias_type
+ alias_vtype_new ()
+ {
+ return alias_vtype_new_with_lf (ECR_new (), ECR_new ());
+ }
+
+ /* Create a new alias value type with a given location and
+ function. */
+ alias_type
+ alias_vtype_new_with_lf (loc, func)
+ ECR loc;
+ ECR func;
+ {
+ alias_type ret = ggc_alloc (sizeof (union alias_type_def));
+ ALIAS_TYPE_KIND (ret) = VALUE_ATYPE;
+ ALIAS_TYPE_ID (ret) = alias_type_num++;
+ SET_ALIAS_TYPE_UNIFY (ret, void_unify);
+ SET_ALIAS_TYPE_POINTSTO (ret, null_pointsto);
+ ALIAS_VTYPE_FUNC (ret) = func;
+ ALIAS_VTYPE_LOC (ret) = loc;
+ return ret;
+ }
+
+ /* Return the alias value type's location ECR. */
+ ECR
+ alias_vtype_loc (vt)
+ alias_type vt;
+ {
+ return ECR_find (ALIAS_VTYPE_LOC (vt));
+ }
+
+ /* Return the alias value type's function ECR. */
+ ECR
+ alias_vtype_func (vt)
+ alias_type vt;
+ {
+ return ECR_find (ALIAS_VTYPE_FUNC (vt));
+ }
+
+ /* Create a new location alias type. */
+ alias_type
+ alias_ltype_new ()
+ {
+ return alias_ltype_new_with_lf (ECR_new (), ECR_new ());
+ }
+
+ /* Create a new location alias type with a given location and
+ function. */
+ alias_type
+ alias_ltype_new_with_lf (loc, func)
+ ECR loc;
+ ECR func;
+ {
+ alias_type ret = ggc_alloc (sizeof (union alias_type_def));
+ ALIAS_TYPE_KIND (ret) = LOCATION_ATYPE;
+ ALIAS_TYPE_ID (ret) = alias_type_num++;
+ SET_ALIAS_TYPE_UNIFY (ret, location_unify);
+ SET_ALIAS_TYPE_POINTSTO (ret, location_pointsto);
+ ALIAS_LTYPE_FUNC (ret) = func;
+ ALIAS_LTYPE_LOC (ret) = loc;
+ return ret;
+ }
+
+ /* Return a given alias location type's location ECR. */
+ ECR
+ alias_ltype_loc (vt)
+ alias_type vt;
+ {
+ return ECR_find (ALIAS_LTYPE_LOC (vt));
+ }
+
+ /* Return a given alias location type's function ECR. */
+ ECR
+ alias_ltype_func (vt)
+ alias_type vt;
+ {
+ return ECR_find (ALIAS_LTYPE_FUNC (vt));
+ }
+
+ static void
+ location_unify (t1, t2)
+ alias_type t1;
+ alias_type t2;
+ {
+ ECR tau1 = alias_ltype_loc (t1);
+ ECR tau2 = alias_ltype_loc (t2);
+ ECR lambda1 = alias_ltype_func (t1);
+ ECR lambda2 = alias_ltype_func (t2);
+
+ if (!ECR_equiv (tau1, tau2))
+ ECR_join (tau1, tau2);
+
+ if (!ECR_equiv (lambda1, lambda2))
+ ECR_join (lambda1, lambda2);
+ }
+
+ static varray_type
+ location_pointsto (t)
+ alias_type t;
+ {
+ varray_type ret;
+ VARRAY_GENERIC_PTR_INIT (ret, 1, "Points-to");
+ if (ECR_get_type (ALIAS_LTYPE_LOC (t)) != alias_bottom)
+ VARRAY_PUSH_GENERIC_PTR (ret, ALIAS_LTYPE_LOC (t));
+ if (ECR_get_type (ALIAS_LTYPE_FUNC (t)) != alias_bottom)
+ VARRAY_PUSH_GENERIC_PTR (ret, ALIAS_LTYPE_FUNC (t));
+ return ret;
+ }
+
+
+ alias_typevar
+ alias_tvar_new_with_at (decl, type)
+ tree decl;
+ alias_type type;
+ {
+ alias_typevar ret = ggc_alloc (sizeof (struct alias_typevar_def));
+ ret->decl = decl;
+ ret->ecr = ECR_new_with_type (type, ret);
+ return ret;
+ }
+
+ alias_typevar
+ alias_tvar_new (decl)
+ tree decl;
+ {
+ return alias_tvar_new_with_at (decl, alias_ltype_new ());
+ }
+
+ alias_typevar
+ alias_tvar_new_equiv_to (decl, var)
+ tree decl;
+ alias_typevar var;
+ {
+ alias_typevar ret = ggc_alloc (sizeof (struct alias_typevar_def));
+ ret->decl = decl;
+ ret->ecr = ECR_new_with_type (ECR_get_type (alias_tvar_get_ECR (var)), ret);
+ ECR_union (ret->ecr, alias_tvar_get_ECR (var));
+ return ret;
+ }
+
+ ECR
+ alias_tvar_get_ECR (var)
+ alias_typevar var;
+ {
+ return ECR_find (var->ecr);
+ }
+
+ ECR
+ alias_tvar_get_orig_ECR (var)
+ alias_typevar var;
+ {
+ return var->ecr;
+ }
+
+ bool
+ alias_tvar_is_alias (var)
+ alias_typevar var;
+ {
+ return ECR_size (var->ecr) > 1;
+ }
+
+ varray_type
+ alias_tvar_pointsto (var)
+ alias_typevar var;
+ {
+ varray_type v = ALIAS_TYPE_POINTSTO (ECR_get_type (var->ecr));
+ varray_type p;
+ size_t i, l;
+
+ VARRAY_GENERIC_PTR_INIT (p, 1, "Points to set");
+ l = VARRAY_ACTIVE_SIZE (v);
+ for (i = 0; i < l; i++)
+ {
+ ECR ecr1 = VARRAY_GENERIC_PTR (v, i);
+ size_t j;
+ varray_type e2 = ECR_elems (ecr1);
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (e2); j++)
+ {
+ ECR ecr2 = VARRAY_GENERIC_PTR (e2, j);
+ if (ECR_get_typevar (ecr2) != NULL)
+ {
+ VARRAY_PUSH_GENERIC_PTR (p, ECR_get_typevar (ecr2));
+ }
+ }
+ VARRAY_CLEAR (e2);
+ }
+ VARRAY_CLEAR (v);
+ return p;
+ }
+
+ void
+ alias_tvar_allpointsto (var, tv)
+ alias_typevar var;
+ varray_type *tv;
+ {
+ ECR e;
+ if (ECR_get_type (var->ecr) == alias_bottom)
+ return;
+ e = alias_ltype_loc (ECR_get_type (var->ecr));
+
+ if (e->color == next_color)
+ return;
+
+ if (ECR_get_type (e) == alias_bottom)
+ return;
+
+ VARRAY_PUSH_GENERIC_PTR ((*tv), e);
+ e->color = next_color;
+ if (ECR_get_typevar (e) == NULL)
+ return;
+ alias_tvar_allpointsto (ECR_get_typevar (e), tv);
+ }
+
+ alias_type
+ alias_ftype_new ()
+ {
+ alias_type ret = ggc_alloc (sizeof (union alias_type_def));
+ ALIAS_TYPE_KIND (ret) = FUNCTION_ATYPE;
+ ALIAS_TYPE_ID (ret) = alias_type_num++;
+ SET_ALIAS_TYPE_UNIFY (ret, function_unify);
+ SET_ALIAS_TYPE_POINTSTO (ret, function_pointsto);
+ ALIAS_FTYPE_RETVAL (ret) = NULL;
+ VARRAY_GENERIC_PTR_INIT (ALIAS_FTYPE_ARGUMENTS (ret), 1,
+ "Function arguments");
+ return ret;
+ }
+
+ void
+ alias_ftype_add_argument (ftype, arg)
+ alias_type ftype;
+ alias_type arg;
+ {
+ VARRAY_PUSH_GENERIC_PTR (ALIAS_FTYPE_ARGUMENTS (ftype), arg);
+ }
+
+ void
+ alias_ftype_add_new_arguments (ftype, num)
+ alias_type ftype;
+ int num;
+ {
+ int i;
+ for (i = 0; i < num; i++)
+ alias_ftype_add_argument (ftype, alias_vtype_new ());
+ }
+
+ static varray_type
+ function_pointsto (ftype)
+ alias_type ftype ATTRIBUTE_UNUSED;
+ {
+ varray_type ret;
+ VARRAY_GENERIC_PTR_INIT (ret, 1, "Points-to");
+ return ret;
+ }
+
+ static void
+ function_unify (t1, t2)
+ alias_type t1;
+ alias_type t2;
+ {
+ varray_type args1 = ALIAS_FTYPE_ARGUMENTS (t1);
+ varray_type args2 = ALIAS_FTYPE_ARGUMENTS (t2);
+ size_t l1 = VARRAY_ACTIVE_SIZE (args1);
+ size_t l2 = VARRAY_ACTIVE_SIZE (args2);
+ size_t l = l1;
+ alias_type alpha2i;
+ size_t i;
+ alias_type alpha1, alpha2;
+ ECR tau1, tau2;
+ ECR lambda1, lambda2;
+
+
+ if (l2 > l)
+ l = l2;
+ /* First process the arguments. */
+ alpha2i = NULL;
+ for (i = 0; i < l; i++)
+ {
+
+ /* Get the next argument for this function (t1). if there isn't any,
+ create one. */
+ if (i >= l1)
+ {
+ alpha1 = alias_vtype_new ();
+ alias_ftype_add_argument (t1, alpha1);
+ }
+ else
+ {
+ alpha1 = VARRAY_GENERIC_PTR (args1, i);
+ }
+
+ /* Get the next argument for the given function (t2). If there
+ isn't any, create one. */
+ if (i >= l2)
+ {
+ if (alpha2i == NULL)
+ alpha2i = alias_vtype_new ();
+ alpha2 = alpha2i;
+ }
+ else
+ {
+ alpha2 = VARRAY_GENERIC_PTR (args2, i);
+ }
+ tau1 = alias_vtype_loc (alpha1);
+ tau2 = alias_vtype_loc (alpha2);
+ /* XXX: Is this supposed to be an equivalence check? */
+ if (tau1 != tau2)
+ ECR_join (tau1, tau2);
+ lambda1 = alias_vtype_func (alpha1);
+ lambda2 = alias_vtype_func (alpha2);
+ /* XXX: Ditto */
+ if (lambda1 != lambda2)
+ ECR_join (lambda1, lambda2);
+ }
+ /* Now, process the return type. */
+ alpha1 = ALIAS_FTYPE_RETVAL (t1);
+ alpha2 = ALIAS_FTYPE_RETVAL (t2);
+
+ tau1 = alias_vtype_loc (alpha1);
+ tau2 = alias_vtype_loc (alpha2);
+ /* XXX: Is this supposed to be an equivalence check? */
+ if (tau1 != tau2)
+ ECR_join (tau1, tau2);
+ lambda1 = alias_vtype_func (alpha1);
+ lambda2 = alias_vtype_func (alpha2);
+ /* XXX: Ditto */
+ if (lambda1 != lambda2)
+ ECR_join (lambda1, lambda2);
+ }
Index: tree-alias-type.h
===================================================================
RCS file: tree-alias-type.h
diff -N tree-alias-type.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-alias-type.h 15 Jul 2002 17:46:38 -0000
***************
*** 0 ****
--- 1,123 ----
+ #ifndef TREE_ALIAS_TYPE_H
+ #define TREE_ALIAS_TYPE_H
+ #include "tree.h"
+
+ struct ECR_def;
+ typedef struct ECR_def *ECR;
+
+ struct alias_typevar_def GTY (())
+ {
+ tree decl;
+ ECR ecr;
+ };
+
+ typedef struct alias_typevar_def *alias_typevar;
+
+ union alias_type_def;
+ typedef union alias_type_def *alias_type;
+
+ alias_typevar alias_tvar_new_with_at PARAMS ((tree, alias_type));
+ alias_typevar alias_tvar_new PARAMS ((tree));
+ alias_typevar alias_tvar_new_equiv_to PARAMS ((tree, alias_typevar));
+ ECR alias_tvar_get_ECR PARAMS ((alias_typevar));
+ ECR alias_tvar_get_orig_ECR PARAMS ((alias_typevar));
+ bool alias_tvar_is_alias PARAMS ((alias_typevar));
+ varray_type alias_tvar_pointsto PARAMS ((alias_typevar));
+ void alias_tvar_allpointsto PARAMS ((alias_typevar, varray_type *));
+
+ enum alias_types
+ {
+ BOTTOM_ATYPE,
+ VALUE_ATYPE,
+ LOCATION_ATYPE,
+ FUNCTION_ATYPE
+ };
+ typedef varray_type (*pointsto_func) PARAMS ((alias_type));
+ typedef void (*unify_func) PARAMS ((alias_type, alias_type));
+
+ struct alias_type_common GTY (())
+ {
+ enum alias_types kind;
+ unsigned int id;
+ pointsto_func pointsto;
+ unify_func unify;
+ };
+ /*
+ This struct represents Steensgaard's alpha type, the non-standard
+ type describing values. */
+ struct alias_value_type GTY (())
+ {
+ struct alias_type_common common;
+ ECR location;
+ ECR function;
+ };
+ /*
+ This struct represents what Steensgaard refers to these as tau
+ types, the non-standard types describing locations. A location is
+ either bottom or a value. So this type is representative of a
+ pointer to another tau type (location_type), or a lambda type
+ (function_type).
+
+ In theory, one could get away with just having a pointer to the
+ alpha type (value_type). However, the indirection this would add to
+ the routines isn't worth the one extra pointer it costs to store
+ the alpha type's fields directly.
+ */
+
+
+ struct alias_location_type GTY (())
+ {
+ struct alias_type_common common;
+ ECR location;
+ ECR function;
+ };
+ /* This struct implements what Steensgaard refers to as lambda types,
+ the non-standard type describing functions. */
+ struct alias_function_type GTY (())
+ {
+ struct alias_type_common common;
+ alias_type retval;
+ varray_type GTY ((param_is (union alias_type_def))) arguments;
+ };
+ union alias_type_def GTY ((desc ("%0.common.kind")))
+ {
+ struct alias_type_common GTY ((tag ("BOTTOM_ATYPE"))) common;
+ struct alias_value_type GTY ((tag ("VALUE_ATYPE"))) value;
+ struct alias_location_type GTY ((tag ("LOCATION_ATYPE"))) location;
+ struct alias_function_type GTY ((tag ("FUNCTION_ATYPE"))) function;
+ };
+
+ #define ALIAS_TYPE_KIND(x) ((x)->common.kind)
+ #define ALIAS_TYPE_ID(x) ((x)->common.id)
+ #define SET_ALIAS_TYPE_UNIFY(x, y) ((x)->common.unify = (y))
+ #define SET_ALIAS_TYPE_POINTSTO(x, y) ((x)->common.pointsto = (y))
+ #define ALIAS_TYPE_UNIFY(x, y) ((x)->common.unify((x), (y)))
+ #define ALIAS_TYPE_POINTSTO(x) ((x)->common.pointsto((x)))
+
+ #define ALIAS_VTYPE_FUNC(x) ((x)->value.function)
+ #define ALIAS_VTYPE_LOC(x) ((x)->value.location)
+
+ #define ALIAS_LTYPE_FUNC(x) ((x)->location.function)
+ #define ALIAS_LTYPE_LOC(x) ((x)->location.location)
+
+ #define ALIAS_FTYPE_ARGUMENTS(x) ((x)->function.arguments)
+ #define ALIAS_FTYPE_RETVAL(x) ((x)->function.retval)
+
+ extern GTY (()) alias_type alias_bottom;
+
+ alias_type alias_vtype_new PARAMS ((void));
+ alias_type alias_vtype_new_with_lf PARAMS ((ECR, ECR));
+ ECR alias_vtype_loc PARAMS ((alias_type));
+ ECR alias_vtype_func PARAMS ((alias_type));
+
+ alias_type alias_ltype_new PARAMS ((void));
+ alias_type alias_ltype_new_with_lf PARAMS ((ECR, ECR));
+ ECR alias_ltype_loc PARAMS ((alias_type));
+ ECR alias_ltype_func PARAMS ((alias_type));
+
+ alias_type alias_ftype_new PARAMS ((void));
+ void alias_ftype_add_argument PARAMS ((alias_type, alias_type));
+ void alias_ftype_add_new_arguments PARAMS ((alias_type, int));
+
+ void init_alias_type PARAMS ((void));
+ #endif
Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.26.2.1
diff -c -3 -p -w -B -b -r1.26.2.1 tree-inline.c
*** tree-inline.c 22 Jun 2002 04:39:43 -0000 1.26.2.1
--- tree-inline.c 15 Jul 2002 17:46:39 -0000
*************** Boston, MA 02111-1307, USA. */
*** 46,52 ****
candidates. */
int flag_inline_trees = 0;
!
/* To Do:
o In order to make inlining-on-trees work, we pessimized
--- 46,52 ----
candidates. */
int flag_inline_trees = 0;
! static int inline_label_num = 0;
/* To Do:
o In order to make inlining-on-trees work, we pessimized
*************** expand_call_inline (tp, walk_subtrees, d
*** 789,794 ****
--- 789,795 ----
tree use_stmt;
tree arg_inits;
tree *inlined_body;
+ char *label_name;
splay_tree st;
/* See what we've got. */
*************** expand_call_inline (tp, walk_subtrees, d
*** 913,919 ****
/* Return statements in the function body will be replaced by jumps
to the RET_LABEL. */
! id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
if (! DECL_INITIAL (fn)
--- 914,921 ----
/* Return statements in the function body will be replaced by jumps
to the RET_LABEL. */
! ASM_FORMAT_PRIVATE_NAME (label_name, "inline", inline_label_num++);
! id->ret_label = build_decl (LABEL_DECL, get_identifier (label_name), void_type_node);
DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
if (! DECL_INITIAL (fn)
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.4.2
diff -c -3 -p -w -B -b -r1.1.4.2 tree-optimize.c
*** tree-optimize.c 10 Jul 2002 22:05:14 -0000 1.1.4.2
--- tree-optimize.c 15 Jul 2002 17:46:39 -0000
*************** build_tree_ssa (fndecl)
*** 94,99 ****
--- 96,103 ----
tree_build_ssa ();
tree_compute_rdefs ();
}
+ if (flag_tree_points_to)
+ create_alias_vars ();
}
Index: tree-simple.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.h,v
retrieving revision 1.1.4.2
diff -c -3 -p -w -B -b -r1.1.4.2 tree-simple.h
*** tree-simple.h 29 Jun 2002 18:08:04 -0000 1.1.4.2
--- tree-simple.h 15 Jul 2002 17:46:39 -0000
*************** Boston, MA 02111-1307, USA. */
*** 26,31 ****
--- 26,32 ----
extern void insert_before_continue_end PARAMS ((tree, tree));
extern void tree_build_scope PARAMS ((tree *));
extern tree create_tmp_var PARAMS ((tree, const char *));
+ extern tree create_tmp_alias_var PARAMS ((tree, const char *));
extern bool is_simple_tmp_var PARAMS ((tree));
extern tree get_initialized_tmp_var PARAMS ((tree, tree *));
extern tree declare_tmp_vars PARAMS ((tree, tree));
Index: gengtype.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gengtype.c,v
retrieving revision 1.7.4.2
diff -c -3 -p -w -B -b -r1.7.4.2 gengtype.c
*** gengtype.c 8 Jul 2002 01:45:00 -0000 1.7.4.2
--- gengtype.c 15 Jul 2002 17:46:40 -0000
*************** open_base_files ()
*** 626,635 ****
/* The order of files here matters very much. */
static const char *const ifiles [] = {
"config.h", "system.h", "varray.h", "hashtab.h",
! "bitmap.h", "tree.h", "rtl.h", "function.h", "insn-config.h",
"expr.h", "hard-reg-set.h", "basic-block.h", "cselib.h",
"insn-addr.h", "ssa.h", "optabs.h", "libfuncs.h",
! "debug.h", "ggc.h",
NULL
};
const char *const *ifp;
--- 626,635 ----
/* The order of files here matters very much. */
static const char *const ifiles [] = {
"config.h", "system.h", "varray.h", "hashtab.h",
! "bitmap.h", "disjoint-set.h", "rtl.h", "function.h", "insn-config.h",
"expr.h", "hard-reg-set.h", "basic-block.h", "cselib.h",
"insn-addr.h", "ssa.h", "optabs.h", "libfuncs.h",
! "debug.h", "ggc.h", "tree-alias-type.h", "tree-alias-ecr.h", "tree-flow.h",
NULL
};
const char *const *ifp;
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.2
diff -c -3 -p -w -B -b -r1.86.2.2 flags.h
*** flags.h 10 Jul 2002 22:05:13 -0000 1.86.2.2
--- flags.h 15 Jul 2002 17:46:41 -0000
*************** extern int flag_tree_ssa;
*** 669,674 ****
--- 669,677 ----
/* Enable the SSA-PRE on trees. */
extern int flag_tree_ssa_pre;
+ /* Enable Steengaard's points-to analysis for trees. */
+ extern int flag_tree_points_to;
+
/* Enable SSA-CCP on trees. */
extern int flag_tree_ssa_ccp;
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.3
diff -c -3 -p -w -B -b -r1.654.2.3 toplev.c
*** toplev.c 10 Jul 2002 22:05:13 -0000 1.654.2.3
--- toplev.c 15 Jul 2002 17:46:42 -0000
*************** int flag_tree_ssa = 0;
*** 874,879 ****
--- 874,882 ----
/* Enable the SSA-PRE tree optimization. */
int flag_tree_ssa_pre = 0;
+ /* Enable Steensgaard's points-to analysis on trees. */
+ int flag_tree_points_to = 0;
+
/* Enable SSA-CCP on trees. */
int flag_tree_ssa_ccp = 0;
*************** static const lang_independent_options f_
*** 1191,1196 ****
--- 1194,1201 ----
N_("Enable SSA optimizations on trees") },
{ "tree-ssa-pre", &flag_tree_ssa_pre, 1,
N_("Enable SSA-PRE optimization on trees") },
+ { "tree-points-to", &flag_tree_points_to, 1,
+ N_("Enable Steensgaard's points-to analysis on trees") },
{ "tree-ssa-ccp", &flag_tree_ssa_ccp, 1,
N_("Enable SSA-CCP optimization on trees") },
};
More information about the Gcc-patches
mailing list