Subversion Repositories openrisc

/* Tree based points-to analysis

   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010

   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 "tree.h"

#include "tree-flow.h"

#include "tree-inline.h"

#include "varray.h"

#include "diagnostic.h"

#include "toplev.h"

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

#include "alias.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;

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);

struct constraint;

typedef struct constraint *constraint_t;

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;

  /* 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 (sub-)fields that represent a whole variable.  */

  unsigned int is_full_var : 1;

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

  unsigned int is_heap_var : 1;

  /* True if this is a variable tracking a restrict pointer source.  */

  unsigned int is_restrict_var : 1;

  /* True if this field may contain pointers.  */

  unsigned int may_have_pointers : 1;

  /* True if this represents a global variable.  */

  unsigned int is_global_var : 1;

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

  struct variable_info *next;

  /* 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;

  /* Name of this variable */

  const char *name;

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

  tree decl;

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

  bitmap solution;

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

  bitmap oldsolution;

};

typedef struct variable_info *varinfo_t;

static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);

static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,

                                                   unsigned HOST_WIDE_INT);

static varinfo_t lookup_vi_for_tree (tree);

/* 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);

}

/* Static IDs for the special variables.  */

enum { nothing_id = 0, anything_id = 1, readonly_id = 2,

       escaped_id = 3, nonlocal_id = 4, callused_id = 5,

       storedanything_id = 6, integer_id = 7 };

struct GTY(()) heapvar_map {

  struct tree_map map;

  unsigned HOST_WIDE_INT offset;

};

static int

heapvar_map_eq (const void *p1, const void *p2)

{

  const struct heapvar_map *h1 = (const struct heapvar_map *)p1;

  const struct heapvar_map *h2 = (const struct heapvar_map *)p2;

  return (h1->map.base.from == h2->map.base.from

          && h1->offset == h2->offset);

}

static unsigned int

heapvar_map_hash (struct heapvar_map *h)

{

  return iterative_hash_host_wide_int (h->offset,

                                       htab_hash_pointer (h->map.base.from));

}

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

static tree

heapvar_lookup (tree from, unsigned HOST_WIDE_INT offset)

{

  struct heapvar_map *h, in;

  in.map.base.from = from;

  in.offset = offset;

  h = (struct heapvar_map *) htab_find_with_hash (heapvar_for_stmt, &in,

                                                  heapvar_map_hash (&in));

  if (h)

    return h->map.to;

  return NULL_TREE;

}

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

   hashtable.  */

static void

heapvar_insert (tree from, unsigned HOST_WIDE_INT offset, tree to)

{

  struct heapvar_map *h;

  void **loc;

  h = GGC_NEW (struct heapvar_map);

  h->map.base.from = from;

  h->offset = offset;

  h->map.hash = heapvar_map_hash (h);

  h->map.to = to;

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

  gcc_assert (*loc == NULL);

  *(struct heapvar_map **) loc = h;

}

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

   named NAME, and using constraint graph node NODE.  Append it

   to the vector of variable info structures.  */

static varinfo_t

new_var_info (tree t, const char *name)

{

  unsigned index = VEC_length (varinfo_t, varmap);

  varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);

  ret->id = index;

  ret->name = name;

  ret->decl = t;

  /* Vars without decl are artificial and do not have sub-variables.  */

  ret->is_artificial_var = (t == NULL_TREE);

  ret->is_special_var = false;

  ret->is_unknown_size_var = false;

  ret->is_full_var = (t == NULL_TREE);

  ret->is_heap_var = false;

  ret->is_restrict_var = false;

  ret->may_have_pointers = true;

  ret->is_global_var = (t == NULL_TREE);

  if (t && DECL_P (t))

    ret->is_global_var = is_global_var (t);

  ret->solution = BITMAP_ALLOC (&pta_obstack);

  ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);

  ret->next = NULL;

  VEC_safe_push (varinfo_t, heap, varmap, ret);

  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.   */

  HOST_WIDE_INT offset;

};

/* Use 0x8000... as special unknown offset.  */

#define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))

typedef struct constraint_expr ce_s;

DEF_VEC_O(ce_s);

DEF_VEC_ALLOC_O(ce_s, heap);

static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);

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;

/* 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 label.  This is used for

     variable substitution.  */

  int *eq_rep;

  /* Pointer equivalence label for a node.  All nodes with the same

     pointer equivalence label can be unified together at some point

     (either during constraint optimization or after the constraint

     graph is built).  */

  unsigned int *pe;

  /* Pointer equivalence representative for a label.  This is used to

     handle nodes that are pointer equivalent but not location

     equivalent.  We can unite these once the addressof constraints

     are transformed into initial points-to sets.  */

  int *pe_rep;

  /* Pointer equivalence label for each node, used during variable

     substitution.  */

  unsigned int *pointer_label;

  /* Location equivalence label for each node, used during location

     equivalence finding.  */

  unsigned int *loc_label;

  /* Pointed-by set for each node, used during location equivalence

     finding.  This is pointed-by rather than pointed-to, because it

     is constructed using the predecessor graph.  */

  bitmap *pointed_by;

  /* Points to sets for pointer equivalence.  This is *not* the actual

     points-to sets for nodes.  */

  bitmap *points_to;

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

     node.  Used for variable substitution.  */

  sbitmap direct_nodes;

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

     taken.  Used for variable substitution.  */

  bitmap address_taken;

  /* 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))

/* 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 = (constraint_t) pool_alloc (constraint_pool);

  ret->lhs = lhs;

  ret->rhs = rhs;

  return ret;

}

/* Print out constraint C to FILE.  */

static 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 (c->lhs.var)->name);

  if (c->lhs.offset == UNKNOWN_OFFSET)

    fprintf (file, " + UNKNOWN");

  else 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 (c->rhs.var)->name);

  if (c->rhs.offset == UNKNOWN_OFFSET)

    fprintf (file, " + UNKNOWN");

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

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

  fprintf (file, "\n");

}

void debug_constraint (constraint_t);

void debug_constraints (void);

void debug_constraint_graph (void);

void debug_solution_for_var (unsigned int);

void debug_sa_points_to_info (void);

/* Print out constraint C to stderr.  */

void

debug_constraint (constraint_t c)

{

  dump_constraint (stderr, c);

}

/* Print out all constraints to FILE */

static 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);

}

/* Print out to FILE the edge in the constraint graph that is created by

   constraint c. The edge may have a label, depending on the type of

   constraint that it represents. If complex1, e.g: a = *b, then the label

   is "=*", if complex2, e.g: *a = b, then the label is "*=", if

   complex with an offset, e.g: a = b + 8, then the label is "+".

   Otherwise the edge has no label.  */

static void

dump_constraint_edge (FILE *file, constraint_t c)

{

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

    {

      const char *src = get_varinfo (c->rhs.var)->name;

      const char *dst = get_varinfo (c->lhs.var)->name;

      fprintf (file, "  \"%s\" -> \"%s\" ", src, dst);

      /* Due to preprocessing of constraints, instructions like *a = *b are

         illegal; thus, we do not have to handle such cases.  */

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

        fprintf (file, " [ label=\"*=\" ] ;\n");

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

        fprintf (file, " [ label=\"=*\" ] ;\n");

      else

        {

          /* We must check the case where the constraint is an offset.

             In this case, it is treated as a complex constraint.  */

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

            fprintf (file, " [ label=\"+\" ] ;\n");

          else

            fprintf (file, " ;\n");

        }

    }

}

/* Print the constraint graph in dot format.  */

static void

dump_constraint_graph (FILE *file)

{

  unsigned int i=0, size;

  constraint_t c;

  /* Only print the graph if it has already been initialized:  */

  if (!graph)

    return;

  /* Print the constraints used to produce the constraint graph. The

     constraints will be printed as comments in the dot file:  */

  fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");

  dump_constraints (file);

  fprintf (file, "*/\n");

  /* Prints the header of the dot file:  */

  fprintf (file, "\n\n// The constraint graph in dot format:\n");

  fprintf (file, "strict digraph {\n");

  fprintf (file, "  node [\n    shape = box\n  ]\n");

  fprintf (file, "  edge [\n    fontsize = \"12\"\n  ]\n");

  fprintf (file, "\n  // List of nodes in the constraint graph:\n");

  /* The next lines print the nodes in the graph. In order to get the

     number of nodes in the graph, we must choose the minimum between the

     vector VEC (varinfo_t, varmap) and graph->size. If the graph has not

     yet been initialized, then graph->size == 0, otherwise we must only

     read nodes that have an entry in VEC (varinfo_t, varmap).  */

  size = VEC_length (varinfo_t, varmap);

  size = size < graph->size ? size : graph->size;

  for (i = 0; i < size; i++)

    {

      const char *name = get_varinfo (graph->rep[i])->name;

      fprintf (file, "  \"%s\" ;\n", name);

    }

  /* Go over the list of constraints printing the edges in the constraint

     graph.  */

  fprintf (file, "\n  // The constraint edges:\n");

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

    if (c)

      dump_constraint_edge (file, c);

  /* Prints the tail of the dot file. By now, only the closing bracket.  */

  fprintf (file, "}\n\n\n");

}

/* Print out the constraint graph to stderr.  */

void

debug_constraint_graph (void)

{

  dump_constraint_graph (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.  */