Subversion Repositories openrisc

/* Tree based points-to analysis

   Copyright (C) 2005, 2006 Free Software Foundation, Inc.

   Contributed by Daniel Berlin <dberlin@dberlin.org>

   This file is part of GCC.

   GCC is free software; you can redistribute it and/or modify

   under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 3 of the License, 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 COPYING3.  If not see

   <http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "ggc.h"

#include "obstack.h"

#include "bitmap.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 "diagnostic.h"

#include "tree.h"

#include "c-common.h"

#include "tree-flow.h"

#include "tree-inline.h"

#include "varray.h"

#include "c-tree.h"

#include "tree-gimple.h"

#include "hashtab.h"

#include "function.h"

#include "cgraph.h"

#include "tree-pass.h"

#include "timevar.h"

#include "alloc-pool.h"

#include "splay-tree.h"

#include "params.h"

#include "tree-ssa-structalias.h"

#include "cgraph.h"

#include "pointer-set.h"

/* The idea behind this analyzer is to generate set constraints from the

   program, then solve the resulting constraints in order to generate the

   points-to sets.

   Set constraints are a way of modeling program analysis problems that

   involve sets.  They consist of an inclusion constraint language,

   describing the variables (each variable is a set) and operations that

   are involved on the variables, and a set of rules that derive facts

   from these operations.  To solve a system of set constraints, you derive

   all possible facts under the rules, which gives you the correct sets

   as a consequence.

   See  "Efficient Field-sensitive pointer analysis for C" by "David

   J. Pearce and Paul H. J. Kelly and Chris Hankin, at

   http://citeseer.ist.psu.edu/pearce04efficient.html

   Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines

   of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at

   http://citeseer.ist.psu.edu/heintze01ultrafast.html

   There are three types of real constraint expressions, DEREF,

   ADDRESSOF, and SCALAR.  Each constraint expression consists

   of a constraint type, a variable, and an offset.

   SCALAR is a constraint expression type used to represent x, whether

   it appears on the LHS or the RHS of a statement.

   DEREF is a constraint expression type used to represent *x, whether

   it appears on the LHS or the RHS of a statement.

   ADDRESSOF is a constraint expression used to represent &x, whether

   it appears on the LHS or the RHS of a statement.

   Each pointer variable in the program is assigned an integer id, and

   each field of a structure variable is assigned an integer id as well.

   Structure variables are linked to their list of fields through a "next

   field" in each variable that points to the next field in offset

   order.

   Each variable for a structure field has

   1. "size", that tells the size in bits of that field.

   2. "fullsize, that tells the size in bits of the entire structure.

   3. "offset", that tells the offset in bits from the beginning of the

   structure to this field.

   Thus,

   struct f

   {

     int a;

     int b;

   } foo;

   int *bar;

   looks like

   foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b

   foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL

   bar -> id 3, size 32, offset 0, fullsize 32, next NULL

  In order to solve the system of set constraints, the following is

  done:

  1. Each constraint variable x has a solution set associated with it,

  Sol(x).

  2. Constraints are separated into direct, copy, and complex.

  Direct constraints are ADDRESSOF constraints that require no extra

  processing, such as P = &Q

  Copy constraints are those of the form P = Q.

  Complex constraints are all the constraints involving dereferences

  and offsets (including offsetted copies).

  3. All direct constraints of the form P = &Q are processed, such

  that Q is added to Sol(P)

  4. All complex constraints for a given constraint variable are stored in a

  linked list attached to that variable's node.

  5. A directed graph is built out of the copy constraints. Each

  constraint variable is a node in the graph, and an edge from

  Q to P is added for each copy constraint of the form P = Q

  6. The graph is then walked, and solution sets are

  propagated along the copy edges, such that an edge from Q to P

  causes Sol(P) <- Sol(P) union Sol(Q).

  7.  As we visit each node, all complex constraints associated with

  that node are processed by adding appropriate copy edges to the graph, or the

  appropriate variables to the solution set.

  8. The process of walking the graph is iterated until no solution

  sets change.

  Prior to walking the graph in steps 6 and 7, We perform static

  cycle elimination on the constraint graph, as well

  as off-line variable substitution.

  TODO: Adding offsets to pointer-to-structures can be handled (IE not punted

  on and turned into anything), but isn't.  You can just see what offset

  inside the pointed-to struct it's going to access.

  TODO: Constant bounded arrays can be handled as if they were structs of the

  same number of elements.

  TODO: Modeling heap and incoming pointers becomes much better if we

  add fields to them as we discover them, which we could do.

  TODO: We could handle unions, but to be honest, it's probably not

  worth the pain or slowdown.  */

static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) htab_t heapvar_for_stmt;

/* One variable to represent all non-local accesses.  */

tree nonlocal_all;

static bool use_field_sensitive = true;

static int in_ipa_mode = 0;

/* Used for predecessor bitmaps. */

static bitmap_obstack predbitmap_obstack;

/* Used for points-to sets.  */

static bitmap_obstack pta_obstack;

/* Used for oldsolution members of variables. */

static bitmap_obstack oldpta_obstack;

/* Used for per-solver-iteration bitmaps.  */

static bitmap_obstack iteration_obstack;

static unsigned int create_variable_info_for (tree, const char *);

typedef struct constraint_graph *constraint_graph_t;

static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);

DEF_VEC_P(constraint_t);

DEF_VEC_ALLOC_P(constraint_t,heap);

#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d)        \

  if (a)                                                \

    EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)

static struct constraint_stats

{

  unsigned int total_vars;

  unsigned int nonpointer_vars;

  unsigned int unified_vars_static;

  unsigned int unified_vars_dynamic;

  unsigned int iterations;

  unsigned int num_edges;

  unsigned int num_implicit_edges;

  unsigned int points_to_sets_created;

} stats;

struct variable_info

{

  /* ID of this variable  */

  unsigned int id;

  /* Name of this variable */

  const char *name;

  /* Tree that this variable is associated with.  */

  tree decl;

  /* Offset of this variable, in bits, from the base variable  */

  unsigned HOST_WIDE_INT offset;

  /* Size of the variable, in bits.  */

  unsigned HOST_WIDE_INT size;

  /* Full size of the base variable, in bits.  */

  unsigned HOST_WIDE_INT fullsize;

  /* A link to the variable for the next field in this structure.  */

  struct variable_info *next;

  /* True if the variable is directly the target of a dereference.

     This is used to track which variables are *actually* dereferenced

     so we can prune their points to listed. */

  unsigned int directly_dereferenced:1;

  /* True if this is a variable created by the constraint analysis, such as

     heap variables and constraints we had to break up.  */

  unsigned int is_artificial_var:1;

  /* True if this is a special variable whose solution set should not be

     changed.  */

  unsigned int is_special_var:1;

  /* True for variables whose size is not known or variable.  */

  unsigned int is_unknown_size_var:1;

  /* True for variables that have unions somewhere in them.  */

  unsigned int has_union:1;

  /* True if this is a heap variable.  */

  unsigned int is_heap_var:1;

  /* Points-to set for this variable.  */

  bitmap solution;

  /* Old points-to set for this variable.  */

  bitmap oldsolution;

  /* Variable ids represented by this node.  */

  bitmap variables;

  /* Variable id this was collapsed to due to type unsafety.  This

     should be unused completely after build_succ_graph, or something

     is broken.  */

  struct variable_info *collapsed_to;

};

typedef struct variable_info *varinfo_t;

static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);

/* Pool of variable info structures.  */

static alloc_pool variable_info_pool;

DEF_VEC_P(varinfo_t);

DEF_VEC_ALLOC_P(varinfo_t, heap);

/* Table of variable info structures for constraint variables.

   Indexed directly by variable info id.  */

static VEC(varinfo_t,heap) *varmap;

/* Return the varmap element N */

static inline varinfo_t

get_varinfo (unsigned int n)

{

  return VEC_index (varinfo_t, varmap, n);

}

/* Return the varmap element N, following the collapsed_to link.  */

static inline varinfo_t

get_varinfo_fc (unsigned int n)

{

  varinfo_t v = VEC_index (varinfo_t, varmap, n);

  if (v->collapsed_to)

    return v->collapsed_to;

  return v;

}

/* Variable that represents the unknown pointer.  */

static varinfo_t var_anything;

static tree anything_tree;

static unsigned int anything_id;

/* Variable that represents the NULL pointer.  */

static varinfo_t var_nothing;

static tree nothing_tree;

static unsigned int nothing_id;

/* Variable that represents read only memory.  */

static varinfo_t var_readonly;

static tree readonly_tree;

static unsigned int readonly_id;

/* Variable that represents integers.  This is used for when people do things

   like &0->a.b.  */

static varinfo_t var_integer;

static tree integer_tree;

static unsigned int integer_id;

/* Variable that represents escaped variables.  This is used to give

   incoming pointer variables a better set than ANYTHING.  */

static varinfo_t var_escaped_vars;

static tree escaped_vars_tree;

static unsigned int escaped_vars_id;

/* Variable that represents non-local variables before we expand it to

   one for each type.  */

static unsigned int nonlocal_vars_id;

/* Lookup a heap var for FROM, and return it if we find one.  */

static tree

heapvar_lookup (tree from)

{

  struct tree_map *h, in;

  in.from = from;

  h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));

  if (h)

    return h->to;

  return NULL_TREE;

}

/* Insert a mapping FROM->TO in the heap var for statement

   hashtable.  */

static void

heapvar_insert (tree from, tree to)

{

  struct tree_map *h;

  void **loc;

  h = ggc_alloc (sizeof (struct tree_map));

  h->hash = htab_hash_pointer (from);

  h->from = from;

  h->to = to;

  loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);

  *(struct tree_map **) loc = h;

}

/* Return a new variable info structure consisting for a variable

   named NAME, and using constraint graph node NODE.  */

static varinfo_t

new_var_info (tree t, unsigned int id, const char *name)

{

  varinfo_t ret = pool_alloc (variable_info_pool);

  ret->id = id;

  ret->name = name;

  ret->decl = t;

  ret->directly_dereferenced = false;

  ret->is_artificial_var = false;

  ret->is_heap_var = false;

  ret->is_special_var = false;

  ret->is_unknown_size_var = false;

  ret->has_union = false;

  ret->solution = BITMAP_ALLOC (&pta_obstack);

  ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);

  ret->next = NULL;

  ret->collapsed_to = NULL;

  return ret;

}

typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;

/* An expression that appears in a constraint.  */

struct constraint_expr

{

  /* Constraint type.  */

  constraint_expr_type type;

  /* Variable we are referring to in the constraint.  */

  unsigned int var;

  /* Offset, in bits, of this constraint from the beginning of

     variables it ends up referring to.

     IOW, in a deref constraint, we would deref, get the result set,

     then add OFFSET to each member.   */

  unsigned HOST_WIDE_INT offset;

};

typedef struct constraint_expr ce_s;

DEF_VEC_O(ce_s);

DEF_VEC_ALLOC_O(ce_s, heap);

static void get_constraint_for (tree, VEC(ce_s, heap) **);

static void do_deref (VEC (ce_s, heap) **);

/* Our set constraints are made up of two constraint expressions, one

   LHS, and one RHS.

   As described in the introduction, our set constraints each represent an

   operation between set valued variables.

*/

struct constraint

{

  struct constraint_expr lhs;

  struct constraint_expr rhs;

};

/* List of constraints that we use to build the constraint graph from.  */

static VEC(constraint_t,heap) *constraints;

static alloc_pool constraint_pool;

DEF_VEC_I(int);

DEF_VEC_ALLOC_I(int, heap);

/* The constraint graph is represented as an array of bitmaps

   containing successor nodes.  */

struct constraint_graph

{

  /* Size of this graph, which may be different than the number of

     nodes in the variable map.  */

  unsigned int size;

  /* Explicit successors of each node. */

  bitmap *succs;

  /* Implicit predecessors of each node (Used for variable

     substitution). */

  bitmap *implicit_preds;

  /* Explicit predecessors of each node (Used for variable substitution).  */

  bitmap *preds;

  /* Indirect cycle representatives, or -1 if the node has no indirect

     cycles.  */

  int *indirect_cycles;

  /* Representative node for a node.  rep[a] == a unless the node has

     been unified. */

  unsigned int *rep;

  /* Equivalence class representative for a node.  This is used for

     variable substitution.  */

  int *eq_rep;

  /* Label for each node, used during variable substitution.  */

  unsigned int *label;

  /* Bitmap of nodes where the bit is set if the node is a direct

     node.  Used for variable substitution.  */

  sbitmap direct_nodes;

  /* Vector of complex constraints for each graph node.  Complex

     constraints are those involving dereferences or offsets that are

     not 0.  */

  VEC(constraint_t,heap) **complex;

};

static constraint_graph_t graph;

/* During variable substitution and the offline version of indirect

   cycle finding, we create nodes to represent dereferences and

   address taken constraints.  These represent where these start and

   end.  */

#define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))

#define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))

#define FIRST_ADDR_NODE (LAST_REF_NODE + 1)

/* Return the representative node for NODE, if NODE has been unioned

   with another NODE.

   This function performs path compression along the way to finding

   the representative.  */

static unsigned int

find (unsigned int node)

{

  gcc_assert (node < graph->size);

  if (graph->rep[node] != node)

    return graph->rep[node] = find (graph->rep[node]);

  return node;

}

/* Union the TO and FROM nodes to the TO nodes.

   Note that at some point in the future, we may want to do

   union-by-rank, in which case we are going to have to return the

   node we unified to.  */

static bool

unite (unsigned int to, unsigned int from)

{

  gcc_assert (to < graph->size && from < graph->size);

  if (to != from && graph->rep[from] != to)

    {

      graph->rep[from] = to;

      return true;

    }

  return false;

}

/* Create a new constraint consisting of LHS and RHS expressions.  */

static constraint_t

new_constraint (const struct constraint_expr lhs,

                const struct constraint_expr rhs)

{

  constraint_t ret = pool_alloc (constraint_pool);

  ret->lhs = lhs;

  ret->rhs = rhs;

  return ret;

}

/* Print out constraint C to FILE.  */

void

dump_constraint (FILE *file, constraint_t c)

{

  if (c->lhs.type == ADDRESSOF)

    fprintf (file, "&");

  else if (c->lhs.type == DEREF)

    fprintf (file, "*");

  fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);

  if (c->lhs.offset != 0)

    fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);

  fprintf (file, " = ");

  if (c->rhs.type == ADDRESSOF)

    fprintf (file, "&");

  else if (c->rhs.type == DEREF)

    fprintf (file, "*");

  fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);

  if (c->rhs.offset != 0)

    fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);

  fprintf (file, "\n");

}

/* Print out constraint C to stderr.  */

void

debug_constraint (constraint_t c)

{

  dump_constraint (stderr, c);

}

/* Print out all constraints to FILE */

void

dump_constraints (FILE *file)

{

  int i;

  constraint_t c;

  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)

    dump_constraint (file, c);

}

/* Print out all constraints to stderr.  */

void

debug_constraints (void)

{

  dump_constraints (stderr);

}

/* SOLVER FUNCTIONS

   The solver is a simple worklist solver, that works on the following

   algorithm:

   sbitmap changed_nodes = all zeroes;

   changed_count = 0;

   For each node that is not already collapsed:

       changed_count++;

       set bit in changed nodes

   while (changed_count > 0)

   {

     compute topological ordering for constraint graph

     find and collapse cycles in the constraint graph (updating

     changed if necessary)

     for each node (n) in the graph in topological order:

       changed_count--;

       Process each complex constraint associated with the node,

       updating changed if necessary.

       For each outgoing edge from n, propagate the solution from n to

       the destination of the edge, updating changed as necessary.

   }  */

/* Return true if two constraint expressions A and B are equal.  */

static bool

constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)

{

  return a.type == b.type && a.var == b.var && a.offset == b.offset;

}

/* Return true if constraint expression A is less than constraint expression

   B.  This is just arbitrary, but consistent, in order to give them an

   ordering.  */

static bool

constraint_expr_less (struct constraint_expr a, struct constraint_expr b)

{

  if (a.type == b.type)

    {

      if (a.var == b.var)

        return a.offset < b.offset;

      else

        return a.var < b.var;

    }

  else

    return a.type < b.type;

}

/* Return true if constraint A is less than constraint B.  This is just

   arbitrary, but consistent, in order to give them an ordering.  */

static bool

constraint_less (const constraint_t a, const constraint_t b)

{

  if (constraint_expr_less (a->lhs, b->lhs))

    return true;

  else if (constraint_expr_less (b->lhs, a->lhs))

    return false;

  else

    return constraint_expr_less (a->rhs, b->rhs);

}

/* Return true if two constraints A and B are equal.  */

static bool

constraint_equal (struct constraint a, struct constraint b)

{

  return constraint_expr_equal (a.lhs, b.lhs)

    && constraint_expr_equal (a.rhs, b.rhs);

}

/* Find a constraint LOOKFOR in the sorted constraint vector VEC */

static constraint_t

constraint_vec_find (VEC(constraint_t,heap) *vec,

                     struct constraint lookfor)

{

  unsigned int place;

  constraint_t found;

  if (vec == NULL)

    return NULL;

  place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);

  if (place >= VEC_length (constraint_t, vec))

    return NULL;

  found = VEC_index (constraint_t, vec, place);

  if (!constraint_equal (*found, lookfor))

    return NULL;

  return found;

}

/* Union two constraint vectors, TO and FROM.  Put the result in TO.  */

static void

constraint_set_union (VEC(constraint_t,heap) **to,

                      VEC(constraint_t,heap) **from)

{

  int i;

  constraint_t c;

  for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)

    {

      if (constraint_vec_find (*to, *c) == NULL)

        {

          unsigned int place = VEC_lower_bound (constraint_t, *to, c,

                                                constraint_less);

          VEC_safe_insert (constraint_t, heap, *to, place, c);

        }

    }

}

/* Take a solution set SET, add OFFSET to each member of the set, and

   overwrite SET with the result when done.  */

static void

solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)

{

  bitmap result = BITMAP_ALLOC (&iteration_obstack);

  unsigned int i;

  bitmap_iterator bi;

  unsigned HOST_WIDE_INT min = -1, max = 0;

  /* Compute set of vars we can reach from set + offset.  */

  EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)

    {

      if (get_varinfo (i)->is_artificial_var

          || get_varinfo (i)->has_union

          || get_varinfo (i)->is_unknown_size_var)

        continue;

      if (get_varinfo (i)->offset + offset < min)

        min = get_varinfo (i)->offset + offset;

      if (get_varinfo (i)->offset + get_varinfo (i)->size + offset > max)

        {

          max = get_varinfo (i)->offset + get_varinfo (i)->size + offset;

          if (max > get_varinfo (i)->fullsize)

            max = get_varinfo (i)->fullsize;

        }

    }

  EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)

    {

      /* If this is a properly sized variable, only add offset if it's

         less than end.  Otherwise, it is globbed to a single

         variable.  */

      if (get_varinfo (i)->offset + get_varinfo (i)->size - 1 >= min

          && get_varinfo (i)->offset < max)

        {

          bitmap_set_bit (result, i);

        }

      else if (get_varinfo (i)->is_artificial_var

               || get_varinfo (i)->has_union

               || get_varinfo (i)->is_unknown_size_var)

        {

          bitmap_set_bit (result, i);

        }

    }

  bitmap_copy (set, result);

  BITMAP_FREE (result);

}

/* Union solution sets TO and FROM, and add INC to each member of FROM in the

   process.  */