View | Details | Return to bug 30052
Collapse All | Expand All

(-)pointer-set.c (-24 / +155 lines)
Lines 22-34 Boston, MA 02110-1301, USA. */ Link Here
22
#include "system.h"
22
#include "system.h"
23
#include "pointer-set.h"
23
#include "pointer-set.h"
24
24
25
/* A pointer sets is represented as a simple open-addressing hash
25
/* A pointer set is represented as a simple open-addressing hash
26
   table.  Simplifications: The hash code is based on the value of the
26
   table.  Simplifications: The hash code is based on the value of the
27
   pointer, not what it points to.  The number of buckets is always a
27
   pointer, not what it points to.  The number of buckets is always a
28
   power of 2.  Null pointers are a reserved value.  Deletion is not
28
   power of 2.  Null pointers are a reserved value.  Deletion is not
29
   supported.  There is no mechanism for user control of hash
29
   supported (yet).  There is no mechanism for user control of hash
30
   function, equality comparison, initial size, or resizing policy.
30
   function, equality comparison, initial size, or resizing policy.  */
31
*/
32
31
33
struct pointer_set_t
32
struct pointer_set_t
34
{
33
{
Lines 114-135 pointer_set_contains (struct pointer_set Link Here
114
    }
113
    }
115
}
114
}
116
115
117
/* Subroutine of pointer_set_insert.  Inserts P into an empty
116
/* Subroutine of pointer_set_insert.  Return the insertion slot for P into
118
   element of SLOTS, an array of length N_SLOTS.  Returns nonzero
117
   an empty element of SLOTS, an array of length N_SLOTS.  */
119
   if P was already present in N_SLOTS.  */
118
static inline size_t
120
static int
121
insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
119
insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
122
{
120
{
123
  size_t n = hash1 (p, n_slots, log_slots);
121
  size_t n = hash1 (p, n_slots, log_slots);
124
  while (true)
122
  while (true)
125
    {
123
    {
126
      if (slots[n] == p)
124
      if (slots[n] == p || slots[n] == 0)
127
	return 1;
125
	return n;
128
      else if (slots[n] == 0)
129
	{
130
	  slots[n] = p;
131
	  return 0;
132
	}
133
      else
126
      else
134
	{
127
	{
135
	  ++n;
128
	  ++n;
Lines 144-155 insert_aux (void *p, void **slots, size_ Link Here
144
int
137
int
145
pointer_set_insert (struct pointer_set_t *pset, void *p)
138
pointer_set_insert (struct pointer_set_t *pset, void *p)
146
{
139
{
147
  if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
140
  size_t n;
148
    return 1;
141
149
      
142
  /* For simplicity, expand the set even if P is already there.  This can be
150
  /* We've inserted a new element.  Expand the table if necessary to keep
143
     superfluous but can happen at most once.  */
151
     the load factor small.  */
152
  ++pset->n_elements;
153
  if (pset->n_elements > pset->n_slots / 4)
144
  if (pset->n_elements > pset->n_slots / 4)
154
    {
145
    {
155
      size_t new_log_slots = pset->log_slots + 1;
146
      size_t new_log_slots = pset->log_slots + 1;
Lines 158-166 pointer_set_insert (struct pointer_set_t Link Here
158
      size_t i;
149
      size_t i;
159
150
160
      for (i = 0; i < pset->n_slots; ++i)
151
      for (i = 0; i < pset->n_slots; ++i)
161
	{
152
        {
162
	  if (pset->slots[i])
153
	  void *value = pset->slots[i];
163
	    insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
154
	  n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
155
	  new_slots[n] = value;
164
	}
156
	}
165
157
166
      XDELETEVEC (pset->slots);
158
      XDELETEVEC (pset->slots);
Lines 169-173 pointer_set_insert (struct pointer_set_t Link Here
169
      pset->slots = new_slots;
161
      pset->slots = new_slots;
170
    }
162
    }
171
163
164
  n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots);
165
  if (pset->slots[n])
166
    return 1;
167
168
  pset->slots[n] = p;
169
  ++pset->n_elements;
172
  return 0;
170
  return 0;
173
}
171
}
172
173
/* Pass each pointer in PSET to the function in FN, together with the fixed
174
   parameter DATA.  If FN returns false, the iteration stops.  */
175
176
void pointer_set_traverse (struct pointer_set_t *pset,
177
			   bool (*fn) (void *, void *), void *data)
178
{
179
  size_t i;
180
  for (i = 0; i < pset->n_slots; ++i)
181
    if (pset->slots[i] && !fn (pset->slots[i], data))
182
      break;
183
}
184
185
186
/* A pointer map is represented the same way as a pointer_set, so
187
   the hash code is based on the address of the key, rather than
188
   its contents.  Null keys are a reserved value.  Deletion is not
189
   supported (yet).  There is no mechanism for user control of hash
190
   function, equality comparison, initial size, or resizing policy.  */
191
192
struct pointer_map_t
193
{
194
  size_t log_slots;
195
  size_t n_slots;		/* n_slots = 2^log_slots */
196
  size_t n_elements;
197
198
  void **keys;
199
  void **values;
200
};
201
202
/* Allocate an empty pointer map.  */
203
struct pointer_map_t *
204
pointer_map_create (void)
205
{
206
  struct pointer_map_t *result = XNEW (struct pointer_map_t);
207
208
  result->n_elements = 0;
209
  result->log_slots = 8;
210
  result->n_slots = (size_t) 1 << result->log_slots;
211
212
  result->keys = XCNEWVEC (void *, result->n_slots);
213
  result->values = XCNEWVEC (void *, result->n_slots);
214
  return result;
215
}
216
217
/* Reclaims all memory associated with PMAP.  */
218
void pointer_map_destroy (struct pointer_map_t *pmap)
219
{
220
  XDELETEVEC (pmap->keys);
221
  XDELETEVEC (pmap->values);
222
  XDELETE (pmap);
223
}
224
225
/* Returns a pointer to the value to which P maps, if PMAP contains P.  P
226
   must be nonnull.  Return NULL if PMAP does not contain P.
227
228
   Collisions are resolved by linear probing.  */
229
void **
230
pointer_map_contains (struct pointer_map_t *pmap, void *p)
231
{
232
  size_t n = hash1 (p, pmap->n_slots, pmap->log_slots);
233
234
  while (true)
235
    {
236
      if (pmap->keys[n] == p)
237
	return &pmap->values[n];
238
      else if (pmap->keys[n] == 0)
239
	return NULL;
240
      else
241
       {
242
         ++n;
243
         if (n == pmap->n_slots)
244
           n = 0;
245
       }
246
    }
247
}
248
249
/* Inserts P into PMAP if it wasn't already there.  Returns a pointer
250
   to the value.  P must be nonnull.  */
251
void **
252
pointer_map_insert (struct pointer_map_t *pmap, void *p)
253
{
254
  size_t n;
255
256
  /* For simplicity, expand the map even if P is already there.  This can be
257
     superfluous but can happen at most once.  */
258
  if (pmap->n_elements > pmap->n_slots / 4)
259
    {
260
      size_t new_log_slots = pmap->log_slots + 1;
261
      size_t new_n_slots = pmap->n_slots * 2;
262
      void **new_keys = XCNEWVEC (void *, new_n_slots);
263
      void **new_values = XCNEWVEC (void *, new_n_slots);
264
      size_t i;
265
266
      for (i = 0; i < pmap->n_slots; ++i)
267
	if (pmap->keys[i])
268
	  {
269
	    void *key = pmap->keys[i];
270
	    n = insert_aux (key, new_keys, new_n_slots, new_log_slots);
271
	    new_keys[n] = key;
272
	    new_values[n] = pmap->values[i];
273
	  }
274
275
      XDELETEVEC (pmap->keys);
276
      XDELETEVEC (pmap->values);
277
      pmap->n_slots = new_n_slots;
278
      pmap->log_slots = new_log_slots;
279
      pmap->keys = new_keys;
280
      pmap->values = new_values;
281
    }
282
283
  n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots);
284
  if (!pmap->keys[n])
285
    {
286
      ++pmap->n_elements;
287
      pmap->keys[n] = p;
288
    }
289
290
  return &pmap->values[n];
291
}
292
293
/* Pass each pointer in PMAP to the function in FN, together with the pointer
294
   to the value and the fixed parameter DATA.  If FN returns false, the
295
   iteration stops.  */
296
297
void pointer_map_traverse (struct pointer_map_t *pmap,
298
			   bool (*fn) (void *, void **, void *), void *data)
299
{
300
  size_t i;
301
  for (i = 0; i < pmap->n_slots; ++i)
302
    if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
303
      break;
304
}
(-)pointer-set.h (-1 / +11 lines)
Lines 22-32 Software Foundation, 51 Franklin Street, Link Here
22
#define POINTER_SET_H
22
#define POINTER_SET_H
23
23
24
struct pointer_set_t;
24
struct pointer_set_t;
25
26
struct pointer_set_t *pointer_set_create (void);
25
struct pointer_set_t *pointer_set_create (void);
27
void pointer_set_destroy (struct pointer_set_t *pset);
26
void pointer_set_destroy (struct pointer_set_t *pset);
28
27
29
int pointer_set_contains (struct pointer_set_t *pset, void *p);
28
int pointer_set_contains (struct pointer_set_t *pset, void *p);
30
int pointer_set_insert (struct pointer_set_t *pset, void *p);
29
int pointer_set_insert (struct pointer_set_t *pset, void *p);
30
void pointer_set_traverse (struct pointer_set_t *, bool (*) (void *, void *),
31
			   void *);
32
33
struct pointer_map_t;
34
struct pointer_map_t *pointer_map_create (void);
35
void pointer_map_destroy (struct pointer_map_t *pmap);
36
37
void **pointer_map_contains (struct pointer_map_t *pmap, void *p);
38
void **pointer_map_insert (struct pointer_map_t *pmap, void *p);
39
void pointer_map_traverse (struct pointer_map_t *,
40
			   bool (*) (void *, void **, void *), void *);
31
41
32
#endif  /* POINTER_SET_H  */
42
#endif  /* POINTER_SET_H  */
(-)Makefile.in (-1 / +1 lines)
Lines 1839-1845 stor-layout.o : stor-layout.c $(CONFIG_H Link Here
1839
tree-ssa-structalias.o: tree-ssa-structalias.c tree-ssa-structalias.h \
1839
tree-ssa-structalias.o: tree-ssa-structalias.c tree-ssa-structalias.h \
1840
   $(SYSTEM_H) $(CONFIG_H) $(GGC_H) $(TREE_H) $(TREE_FLOW_H) \
1840
   $(SYSTEM_H) $(CONFIG_H) $(GGC_H) $(TREE_H) $(TREE_FLOW_H) \
1841
   $(TM_H) coretypes.h $(CGRAPH_H) tree-pass.h $(TIMEVAR_H) \
1841
   $(TM_H) coretypes.h $(CGRAPH_H) tree-pass.h $(TIMEVAR_H) \
1842
   gt-tree-ssa-structalias.h $(PARAMS_H)
1842
   gt-tree-ssa-structalias.h $(PARAMS_H) pointer-set.h
1843
tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
1843
tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
1844
   $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \
1844
   $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \
1845
   toplev.h $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \
1845
   toplev.h $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \
(-)tree-ssa-structalias.c (-1235 / +1255 lines)
Lines 51-60 Foundation, Inc., 51 Franklin Street, Fi Link Here
51
#include "params.h"
51
#include "params.h"
52
#include "tree-ssa-structalias.h"
52
#include "tree-ssa-structalias.h"
53
#include "cgraph.h"
53
#include "cgraph.h"
54
#include "pointer-set.h"
54
55
55
/* The idea behind this analyzer is to generate set constraints from the
56
/* The idea behind this analyzer is to generate set constraints from the
56
   program, then solve the resulting constraints in order to generate the
57
   program, then solve the resulting constraints in order to generate the
57
   points-to sets. 
58
   points-to sets.
58
59
59
   Set constraints are a way of modeling program analysis problems that
60
   Set constraints are a way of modeling program analysis problems that
60
   involve sets.  They consist of an inclusion constraint language,
61
   involve sets.  They consist of an inclusion constraint language,
Lines 70-102 Foundation, Inc., 51 Franklin Street, Fi Link Here
70
71
71
   Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
72
   Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
72
   of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
73
   of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
73
   http://citeseer.ist.psu.edu/heintze01ultrafast.html 
74
   http://citeseer.ist.psu.edu/heintze01ultrafast.html
75
76
   There are three types of real constraint expressions, DEREF,
77
   ADDRESSOF, and SCALAR.  Each constraint expression consists
78
   of a constraint type, a variable, and an offset.
74
79
75
   There are three types of constraint expressions, DEREF, ADDRESSOF, and
76
   SCALAR.  Each constraint expression consists of a constraint type,
77
   a variable, and an offset.  
78
   
79
   SCALAR is a constraint expression type used to represent x, whether
80
   SCALAR is a constraint expression type used to represent x, whether
80
   it appears on the LHS or the RHS of a statement.
81
   it appears on the LHS or the RHS of a statement.
81
   DEREF is a constraint expression type used to represent *x, whether
82
   DEREF is a constraint expression type used to represent *x, whether
82
   it appears on the LHS or the RHS of a statement. 
83
   it appears on the LHS or the RHS of a statement.
83
   ADDRESSOF is a constraint expression used to represent &x, whether
84
   ADDRESSOF is a constraint expression used to represent &x, whether
84
   it appears on the LHS or the RHS of a statement.
85
   it appears on the LHS or the RHS of a statement.
85
   
86
86
   Each pointer variable in the program is assigned an integer id, and
87
   Each pointer variable in the program is assigned an integer id, and
87
   each field of a structure variable is assigned an integer id as well.
88
   each field of a structure variable is assigned an integer id as well.
88
   
89
89
   Structure variables are linked to their list of fields through a "next
90
   Structure variables are linked to their list of fields through a "next
90
   field" in each variable that points to the next field in offset
91
   field" in each variable that points to the next field in offset
91
   order.  
92
   order.
92
   Each variable for a structure field has 
93
   Each variable for a structure field has
93
94
94
   1. "size", that tells the size in bits of that field.
95
   1. "size", that tells the size in bits of that field.
95
   2. "fullsize, that tells the size in bits of the entire structure.
96
   2. "fullsize, that tells the size in bits of the entire structure.
96
   3. "offset", that tells the offset in bits from the beginning of the
97
   3. "offset", that tells the offset in bits from the beginning of the
97
   structure to this field.
98
   structure to this field.
98
99
99
   Thus, 
100
   Thus,
100
   struct f
101
   struct f
101
   {
102
   {
102
     int a;
103
     int a;
Lines 110-159 Foundation, Inc., 51 Franklin Street, Fi Link Here
110
   foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
111
   foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
111
   bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112
   bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112
113
113
   
114
114
  In order to solve the system of set constraints, the following is
115
  In order to solve the system of set constraints, the following is
115
  done:
116
  done:
116
117
117
  1. Each constraint variable x has a solution set associated with it,
118
  1. Each constraint variable x has a solution set associated with it,
118
  Sol(x).
119
  Sol(x).
119
  
120
120
  2. Constraints are separated into direct, copy, and complex.
121
  2. Constraints are separated into direct, copy, and complex.
121
  Direct constraints are ADDRESSOF constraints that require no extra
122
  Direct constraints are ADDRESSOF constraints that require no extra
122
  processing, such as P = &Q
123
  processing, such as P = &Q
123
  Copy constraints are those of the form P = Q.
124
  Copy constraints are those of the form P = Q.
124
  Complex constraints are all the constraints involving dereferences.
125
  Complex constraints are all the constraints involving dereferences
125
  
126
  and offsets (including offsetted copies).
127
126
  3. All direct constraints of the form P = &Q are processed, such
128
  3. All direct constraints of the form P = &Q are processed, such
127
  that Q is added to Sol(P) 
129
  that Q is added to Sol(P)
128
130
129
  4. All complex constraints for a given constraint variable are stored in a
131
  4. All complex constraints for a given constraint variable are stored in a
130
  linked list attached to that variable's node.  
132
  linked list attached to that variable's node.
131
133
132
  5. A directed graph is built out of the copy constraints. Each
134
  5. A directed graph is built out of the copy constraints. Each
133
  constraint variable is a node in the graph, and an edge from 
135
  constraint variable is a node in the graph, and an edge from
134
  Q to P is added for each copy constraint of the form P = Q
136
  Q to P is added for each copy constraint of the form P = Q
135
  
137
136
  6. The graph is then walked, and solution sets are
138
  6. The graph is then walked, and solution sets are
137
  propagated along the copy edges, such that an edge from Q to P
139
  propagated along the copy edges, such that an edge from Q to P
138
  causes Sol(P) <- Sol(P) union Sol(Q).
140
  causes Sol(P) <- Sol(P) union Sol(Q).
139
  
141
140
  7.  As we visit each node, all complex constraints associated with
142
  7.  As we visit each node, all complex constraints associated with
141
  that node are processed by adding appropriate copy edges to the graph, or the
143
  that node are processed by adding appropriate copy edges to the graph, or the
142
  appropriate variables to the solution set.  
144
  appropriate variables to the solution set.
143
145
144
  8. The process of walking the graph is iterated until no solution
146
  8. The process of walking the graph is iterated until no solution
145
  sets change.
147
  sets change.
146
148
147
  Prior to walking the graph in steps 6 and 7, We perform static
149
  Prior to walking the graph in steps 6 and 7, We perform static
148
  cycle elimination on the constraint graph, as well 
150
  cycle elimination on the constraint graph, as well
149
  as off-line variable substitution.
151
  as off-line variable substitution.
150
  
152
151
  TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
153
  TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
152
  on and turned into anything), but isn't.  You can just see what offset
154
  on and turned into anything), but isn't.  You can just see what offset
153
  inside the pointed-to struct it's going to access.
155
  inside the pointed-to struct it's going to access.
154
  
156
155
  TODO: Constant bounded arrays can be handled as if they were structs of the
157
  TODO: Constant bounded arrays can be handled as if they were structs of the
156
  same number of elements. 
158
  same number of elements.
157
159
158
  TODO: Modeling heap and incoming pointers becomes much better if we
160
  TODO: Modeling heap and incoming pointers becomes much better if we
159
  add fields to them as we discover them, which we could do.
161
  add fields to them as we discover them, which we could do.
Lines 161-180 Foundation, Inc., 51 Franklin Street, Fi Link Here
161
  TODO: We could handle unions, but to be honest, it's probably not
163
  TODO: We could handle unions, but to be honest, it's probably not
162
  worth the pain or slowdown.  */
164
  worth the pain or slowdown.  */
163
165
164
static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) 
166
static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) htab_t heapvar_for_stmt;
165
htab_t heapvar_for_stmt;
166
167
167
/* One variable to represent all non-local accesses.  */
168
/* One variable to represent all non-local accesses.  */
168
tree nonlocal_all;
169
tree nonlocal_all;
169
170
170
static bool use_field_sensitive = true;
171
static bool use_field_sensitive = true;
171
static int in_ipa_mode = 0;
172
static int in_ipa_mode = 0;
173
174
/* Used for predecessor bitmaps. */
172
static bitmap_obstack predbitmap_obstack;
175
static bitmap_obstack predbitmap_obstack;
173
static bitmap_obstack ptabitmap_obstack;
176
177
/* Used for points-to sets.  */
178
static bitmap_obstack pta_obstack;
179
180
/* Used for oldsolution members of variables. */
181
static bitmap_obstack oldpta_obstack;
182
183
/* Used for per-solver-iteration bitmaps.  */
174
static bitmap_obstack iteration_obstack;
184
static bitmap_obstack iteration_obstack;
175
185
176
static unsigned int create_variable_info_for (tree, const char *);
186
static unsigned int create_variable_info_for (tree, const char *);
177
static void build_constraint_graph (void);
187
typedef struct constraint_graph *constraint_graph_t;
188
static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
178
189
179
DEF_VEC_P(constraint_t);
190
DEF_VEC_P(constraint_t);
180
DEF_VEC_ALLOC_P(constraint_t,heap);
191
DEF_VEC_ALLOC_P(constraint_t,heap);
Lines 186-196 DEF_VEC_ALLOC_P(constraint_t,heap); Link Here
186
static struct constraint_stats
197
static struct constraint_stats
187
{
198
{
188
  unsigned int total_vars;
199
  unsigned int total_vars;
189
  unsigned int collapsed_vars;
200
  unsigned int nonpointer_vars;
190
  unsigned int unified_vars_static;
201
  unsigned int unified_vars_static;
191
  unsigned int unified_vars_dynamic;
202
  unsigned int unified_vars_dynamic;
192
  unsigned int iterations;
203
  unsigned int iterations;
193
  unsigned int num_edges;
204
  unsigned int num_edges;
205
  unsigned int num_implicit_edges;
206
  unsigned int points_to_sets_created;
194
} stats;
207
} stats;
195
208
196
struct variable_info
209
struct variable_info
Lines 205-211 struct variable_info Link Here
205
  tree decl;
218
  tree decl;
206
219
207
  /* Offset of this variable, in bits, from the base variable  */
220
  /* Offset of this variable, in bits, from the base variable  */
208
  unsigned HOST_WIDE_INT offset;  
221
  unsigned HOST_WIDE_INT offset;
209
222
210
  /* Size of the variable, in bits.  */
223
  /* Size of the variable, in bits.  */
211
  unsigned HOST_WIDE_INT size;
224
  unsigned HOST_WIDE_INT size;
Lines 216-249 struct variable_info Link Here
216
  /* A link to the variable for the next field in this structure.  */
229
  /* A link to the variable for the next field in this structure.  */
217
  struct variable_info *next;
230
  struct variable_info *next;
218
231
219
  /* Node in the graph that represents the constraints and points-to
220
     solution for the variable.  */
221
  unsigned int node;
222
223
  /* True if the address of this variable is taken.  Needed for
224
     variable substitution.  */
225
  unsigned int address_taken:1;
226
227
  /* True if this variable is the target of a dereference.  Needed for
228
     variable substitution.  */
229
  unsigned int indirect_target:1;
230
  
231
  /* True if the variable is directly the target of a dereference.
232
  /* True if the variable is directly the target of a dereference.
232
     This is used to track which variables are *actually* dereferenced
233
     This is used to track which variables are *actually* dereferenced
233
     so we can prune their points to listed. This is equivalent to the
234
     so we can prune their points to listed. */
234
     indirect_target flag when no merging of variables happens.  */
235
  unsigned int directly_dereferenced:1;
235
  unsigned int directly_dereferenced:1;
236
236
237
  /* True if this is a variable created by the constraint analysis, such as
237
  /* True if this is a variable created by the constraint analysis, such as
238
     heap variables and constraints we had to break up.  */
238
     heap variables and constraints we had to break up.  */
239
  unsigned int is_artificial_var:1;
239
  unsigned int is_artificial_var:1;
240
  
240
241
  /* True if this is a special variable whose solution set should not be
241
  /* True if this is a special variable whose solution set should not be
242
     changed.  */
242
     changed.  */
243
  unsigned int is_special_var:1;
243
  unsigned int is_special_var:1;
244
244
245
  /* True for variables whose size is not known or variable.  */
245
  /* True for variables whose size is not known or variable.  */
246
  unsigned int is_unknown_size_var:1;  
246
  unsigned int is_unknown_size_var:1;
247
247
248
  /* True for variables that have unions somewhere in them.  */
248
  /* True for variables that have unions somewhere in them.  */
249
  unsigned int has_union:1;
249
  unsigned int has_union:1;
Lines 254-269 struct variable_info Link Here
254
  /* Points-to set for this variable.  */
254
  /* Points-to set for this variable.  */
255
  bitmap solution;
255
  bitmap solution;
256
256
257
  /* Old points-to set for this variable.  */
258
  bitmap oldsolution;
259
257
  /* Variable ids represented by this node.  */
260
  /* Variable ids represented by this node.  */
258
  bitmap variables;
261
  bitmap variables;
259
262
260
  /* Vector of complex constraints for this node.  Complex
263
  /* Variable id this was collapsed to due to type unsafety.  This
261
     constraints are those involving dereferences.  */
264
     should be unused completely after build_succ_graph, or something
262
  VEC(constraint_t,heap) *complex;
265
     is broken.  */
263
  
264
  /* Variable id this was collapsed to due to type unsafety.
265
     This should be unused completely after build_constraint_graph, or
266
     something is broken.  */
267
  struct variable_info *collapsed_to;
266
  struct variable_info *collapsed_to;
268
};
267
};
269
typedef struct variable_info *varinfo_t;
268
typedef struct variable_info *varinfo_t;
Lines 277-284 DEF_VEC_P(varinfo_t); Link Here
277
276
278
DEF_VEC_ALLOC_P(varinfo_t, heap);
277
DEF_VEC_ALLOC_P(varinfo_t, heap);
279
278
280
/* Table of variable info structures for constraint variables.  Indexed directly
279
/* Table of variable info structures for constraint variables.
281
   by variable info id.  */
280
   Indexed directly by variable info id.  */
282
static VEC(varinfo_t,heap) *varmap;
281
static VEC(varinfo_t,heap) *varmap;
283
282
284
/* Return the varmap element N */
283
/* Return the varmap element N */
Lines 286-292 static VEC(varinfo_t,heap) *varmap; Link Here
286
static inline varinfo_t
285
static inline varinfo_t
287
get_varinfo (unsigned int n)
286
get_varinfo (unsigned int n)
288
{
287
{
289
  return VEC_index(varinfo_t, varmap, n);
288
  return VEC_index (varinfo_t, varmap, n);
290
}
289
}
291
290
292
/* Return the varmap element N, following the collapsed_to link.  */
291
/* Return the varmap element N, following the collapsed_to link.  */
Lines 294-300 get_varinfo (unsigned int n) Link Here
294
static inline varinfo_t
293
static inline varinfo_t
295
get_varinfo_fc (unsigned int n)
294
get_varinfo_fc (unsigned int n)
296
{
295
{
297
  varinfo_t v = VEC_index(varinfo_t, varmap, n);
296
  varinfo_t v = VEC_index (varinfo_t, varmap, n);
298
297
299
  if (v->collapsed_to)
298
  if (v->collapsed_to)
300
    return v->collapsed_to;
299
    return v->collapsed_to;
Lines 331-340 static unsigned int escaped_vars_id; Link Here
331
/* Variable that represents non-local variables before we expand it to
330
/* Variable that represents non-local variables before we expand it to
332
   one for each type.  */
331
   one for each type.  */
333
static unsigned int nonlocal_vars_id;
332
static unsigned int nonlocal_vars_id;
334
335
/* Lookup a heap var for FROM, and return it if we find one.  */
333
/* Lookup a heap var for FROM, and return it if we find one.  */
336
334
337
static tree 
335
static tree
338
heapvar_lookup (tree from)
336
heapvar_lookup (tree from)
339
{
337
{
340
  struct tree_map *h, in;
338
  struct tree_map *h, in;
Lines 367-391 heapvar_insert (tree from, tree to) Link Here
367
   named NAME, and using constraint graph node NODE.  */
365
   named NAME, and using constraint graph node NODE.  */
368
366
369
static varinfo_t
367
static varinfo_t
370
new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
368
new_var_info (tree t, unsigned int id, const char *name)
371
{
369
{
372
  varinfo_t ret = pool_alloc (variable_info_pool);
370
  varinfo_t ret = pool_alloc (variable_info_pool);
373
371
374
  ret->id = id;
372
  ret->id = id;
375
  ret->name = name;
373
  ret->name = name;
376
  ret->decl = t;
374
  ret->decl = t;
377
  ret->node = node;
378
  ret->address_taken = false;
379
  ret->indirect_target = false;
380
  ret->directly_dereferenced = false;
375
  ret->directly_dereferenced = false;
381
  ret->is_artificial_var = false;
376
  ret->is_artificial_var = false;
382
  ret->is_heap_var = false;
377
  ret->is_heap_var = false;
383
  ret->is_special_var = false;
378
  ret->is_special_var = false;
384
  ret->is_unknown_size_var = false;
379
  ret->is_unknown_size_var = false;
385
  ret->has_union = false;
380
  ret->has_union = false;
386
  ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
381
  ret->solution = BITMAP_ALLOC (&pta_obstack);
387
  ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
382
  ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
388
  ret->complex = NULL;
389
  ret->next = NULL;
383
  ret->next = NULL;
390
  ret->collapsed_to = NULL;
384
  ret->collapsed_to = NULL;
391
  return ret;
385
  return ret;
Lines 395-401 typedef enum {SCALAR, DEREF, ADDRESSOF} Link Here
395
389
396
/* An expression that appears in a constraint.  */
390
/* An expression that appears in a constraint.  */
397
391
398
struct constraint_expr 
392
struct constraint_expr
399
{
393
{
400
  /* Constraint type.  */
394
  /* Constraint type.  */
401
  constraint_expr_type type;
395
  constraint_expr_type type;
Lines 418-424 static void get_constraint_for (tree, VE Link Here
418
static void do_deref (VEC (ce_s, heap) **);
412
static void do_deref (VEC (ce_s, heap) **);
419
413
420
/* Our set constraints are made up of two constraint expressions, one
414
/* Our set constraints are made up of two constraint expressions, one
421
   LHS, and one RHS.  
415
   LHS, and one RHS.
422
416
423
   As described in the introduction, our set constraints each represent an
417
   As described in the introduction, our set constraints each represent an
424
   operation between set valued variables.
418
   operation between set valued variables.
Lines 434-496 struct constraint Link Here
434
static VEC(constraint_t,heap) *constraints;
428
static VEC(constraint_t,heap) *constraints;
435
static alloc_pool constraint_pool;
429
static alloc_pool constraint_pool;
436
430
437
/* An edge in the weighted constraint graph.   The edges are weighted,
438
   with a bit set in weights meaning their is an edge with that
439
   weight. 
440
   We don't keep the src in the edge, because we always know what it
441
   is. */
442
431
443
struct constraint_edge
432
DEF_VEC_I(int);
433
DEF_VEC_ALLOC_I(int, heap);
434
435
/* The constraint graph is represented as an array of bitmaps
436
   containing successor nodes.  */
437
438
struct constraint_graph
444
{
439
{
445
  unsigned int dest;
440
  /* Size of this graph, which may be different than the number of
446
  bitmap weights;
441
     nodes in the variable map.  */
447
};
442
  unsigned int size;
448
443
449
typedef struct constraint_edge *constraint_edge_t;
444
  /* Explicit successors of each node. */
450
static alloc_pool constraint_edge_pool;
445
  bitmap *succs;
451
446
452
/* Return a new constraint edge from SRC to DEST.  */
447
  /* Implicit predecessors of each node (Used for variable
448
     substitution). */
449
  bitmap *implicit_preds;
453
450
454
static constraint_edge_t
451
  /* Explicit predecessors of each node (Used for variable substitution).  */
455
new_constraint_edge (unsigned int dest)
452
  bitmap *preds;
456
{
457
  constraint_edge_t ret = pool_alloc (constraint_edge_pool);
458
  ret->dest = dest;
459
  ret->weights = NULL;
460
  return ret;
461
}
462
453
463
DEF_VEC_P(constraint_edge_t);
454
  /* Indirect cycle representatives, or -1 if the node has no indirect
464
DEF_VEC_ALLOC_P(constraint_edge_t,heap);
455
     cycles.  */
456
  int *indirect_cycles;
465
457
458
  /* Representative node for a node.  rep[a] == a unless the node has
459
     been unified. */
460
  unsigned int *rep;
466
461
467
/* The constraint graph is represented internally in two different
462
  /* Equivalence class representative for a node.  This is used for
468
   ways.  The overwhelming majority of edges in the constraint graph
463
     variable substitution.  */
469
   are zero weigh edges, and thus, using a vector of contrainst_edge_t
464
  int *eq_rep;
470
   is a waste of time and memory, since they have no weights.  We
471
   simply use a bitmap to store the preds and succs for each node.
472
   The weighted edges are stored as a set of adjacency vectors, one
473
   per variable. succs[x] is the vector of successors for variable x,
474
   and preds[x] is the vector of predecessors for variable x.  IOW,
475
   all edges are "forward" edges, which is not like our CFG.  So
476
   remember that preds[x]->src == x, and succs[x]->src == x.  */
477
465
478
struct constraint_graph
466
  /* Label for each node, used during variable substitution.  */
479
{
467
  unsigned int *label;
480
  bitmap *zero_weight_succs;
481
  bitmap *zero_weight_preds;
482
  VEC(constraint_edge_t,heap) **succs;
483
  VEC(constraint_edge_t,heap) **preds;
484
};
485
468
486
typedef struct constraint_graph *constraint_graph_t;
469
  /* Bitmap of nodes where the bit is set if the node is a direct
470
     node.  Used for variable substitution.  */
471
  sbitmap direct_nodes;
472
473
  /* Vector of complex constraints for each graph node.  Complex
474
     constraints are those involving dereferences or offsets that are
475
     not 0.  */
476
  VEC(constraint_t,heap) **complex;
477
};
487
478
488
static constraint_graph_t graph;
479
static constraint_graph_t graph;
489
static int graph_size;
480
481
/* During variable substitution and the offline version of indirect
482
   cycle finding, we create nodes to represent dereferences and
483
   address taken constraints.  These represent where these start and
484
   end.  */
485
#define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
486
#define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
487
#define FIRST_ADDR_NODE (LAST_REF_NODE + 1)
488
489
/* Return the representative node for NODE, if NODE has been unioned
490
   with another NODE.
491
   This function performs path compression along the way to finding
492
   the representative.  */
493
494
static unsigned int
495
find (unsigned int node)
496
{
497
  gcc_assert (node < graph->size);
498
  if (graph->rep[node] != node)
499
    return graph->rep[node] = find (graph->rep[node]);
500
  return node;
501
}
502
503
/* Union the TO and FROM nodes to the TO nodes.
504
   Note that at some point in the future, we may want to do
505
   union-by-rank, in which case we are going to have to return the
506
   node we unified to.  */
507
508
static bool
509
unite (unsigned int to, unsigned int from)
510
{
511
  gcc_assert (to < graph->size && from < graph->size);
512
  if (to != from && graph->rep[from] != to)
513
    {
514
      graph->rep[from] = to;
515
      return true;
516
    }
517
  return false;
518
}
490
519
491
/* Create a new constraint consisting of LHS and RHS expressions.  */
520
/* Create a new constraint consisting of LHS and RHS expressions.  */
492
521
493
static constraint_t 
522
static constraint_t
494
new_constraint (const struct constraint_expr lhs,
523
new_constraint (const struct constraint_expr lhs,
495
		const struct constraint_expr rhs)
524
		const struct constraint_expr rhs)
496
{
525
{
Lines 508-514 dump_constraint (FILE *file, constraint_ Link Here
508
  if (c->lhs.type == ADDRESSOF)
537
  if (c->lhs.type == ADDRESSOF)
509
    fprintf (file, "&");
538
    fprintf (file, "&");
510
  else if (c->lhs.type == DEREF)
539
  else if (c->lhs.type == DEREF)
511
    fprintf (file, "*");  
540
    fprintf (file, "*");
512
  fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
541
  fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
513
  if (c->lhs.offset != 0)
542
  if (c->lhs.offset != 0)
514
    fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
543
    fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
Lines 550-572 debug_constraints (void) Link Here
550
  dump_constraints (stderr);
579
  dump_constraints (stderr);
551
}
580
}
552
581
553
/* SOLVER FUNCTIONS 
582
/* SOLVER FUNCTIONS
554
583
555
   The solver is a simple worklist solver, that works on the following
584
   The solver is a simple worklist solver, that works on the following
556
   algorithm:
585
   algorithm:
557
   
586
558
   sbitmap changed_nodes = all ones;
587
   sbitmap changed_nodes = all zeroes;
559
   changed_count = number of nodes;
588
   changed_count = 0;
560
   For each node that was already collapsed:
589
   For each node that is not already collapsed:
561
       changed_count--;
590
       changed_count++;
591
       set bit in changed nodes
562
592
563
   while (changed_count > 0)
593
   while (changed_count > 0)
564
   {
594
   {
565
     compute topological ordering for constraint graph
595
     compute topological ordering for constraint graph
566
  
596
567
     find and collapse cycles in the constraint graph (updating
597
     find and collapse cycles in the constraint graph (updating
568
     changed if necessary)
598
     changed if necessary)
569
     
599
570
     for each node (n) in the graph in topological order:
600
     for each node (n) in the graph in topological order:
571
       changed_count--;
601
       changed_count--;
572
602
Lines 619-629 constraint_less (const constraint_t a, c Link Here
619
}
649
}
620
650
621
/* Return true if two constraints A and B are equal.  */
651
/* Return true if two constraints A and B are equal.  */
622
  
652
623
static bool
653
static bool
624
constraint_equal (struct constraint a, struct constraint b)
654
constraint_equal (struct constraint a, struct constraint b)
625
{
655
{
626
  return constraint_expr_equal (a.lhs, b.lhs) 
656
  return constraint_expr_equal (a.lhs, b.lhs)
627
    && constraint_expr_equal (a.rhs, b.rhs);
657
    && constraint_expr_equal (a.rhs, b.rhs);
628
}
658
}
629
659
Lines 634-640 static constraint_t Link Here
634
constraint_vec_find (VEC(constraint_t,heap) *vec,
664
constraint_vec_find (VEC(constraint_t,heap) *vec,
635
		     struct constraint lookfor)
665
		     struct constraint lookfor)
636
{
666
{
637
  unsigned int place;  
667
  unsigned int place;
638
  constraint_t found;
668
  constraint_t found;
639
669
640
  if (vec == NULL)
670
  if (vec == NULL)
Lines 684-690 solution_set_add (bitmap set, unsigned H Link Here
684
      /* If this is a properly sized variable, only add offset if it's
714
      /* If this is a properly sized variable, only add offset if it's
685
	 less than end.  Otherwise, it is globbed to a single
715
	 less than end.  Otherwise, it is globbed to a single
686
	 variable.  */
716
	 variable.  */
687
      
717
688
      if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
718
      if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
689
	{
719
	{
690
	  unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
720
	  unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
Lines 693-707 solution_set_add (bitmap set, unsigned H Link Here
693
	    continue;
723
	    continue;
694
	  bitmap_set_bit (result, v->id);
724
	  bitmap_set_bit (result, v->id);
695
	}
725
	}
696
      else if (get_varinfo (i)->is_artificial_var 
726
      else if (get_varinfo (i)->is_artificial_var
697
	       || get_varinfo (i)->has_union
727
	       || get_varinfo (i)->has_union
698
	       || get_varinfo (i)->is_unknown_size_var)
728
	       || get_varinfo (i)->is_unknown_size_var)
699
	{
729
	{
700
	  bitmap_set_bit (result, i);
730
	  bitmap_set_bit (result, i);
701
	}
731
	}
702
    }
732
    }
703
  
733
704
  bitmap_copy (set, result);  
734
  bitmap_copy (set, result);
705
  BITMAP_FREE (result);
735
  BITMAP_FREE (result);
706
}
736
}
707
737
Lines 727-1123 set_union_with_increment (bitmap to, bi Link Here
727
    }
757
    }
728
}
758
}
729
759
730
/* Insert constraint C into the list of complex constraints for VAR.  */
760
/* Insert constraint C into the list of complex constraints for graph
761
   node VAR.  */
731
762
732
static void
763
static void
733
insert_into_complex (unsigned int var, constraint_t c)
764
insert_into_complex (constraint_graph_t graph,
765
		     unsigned int var, constraint_t c)
734
{
766
{
735
  varinfo_t vi = get_varinfo (var);
767
  VEC (constraint_t, heap) *complex = graph->complex[var];
736
  unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
768
  unsigned int place = VEC_lower_bound (constraint_t, complex, c,
737
					constraint_less);
769
					constraint_less);
738
  VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
739
}
740
741
742
/* Compare two constraint edges A and B, return true if they are equal.  */
743
744
static bool
745
constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
746
{
747
  return a.dest == b.dest;
748
}
749
770
750
/* Compare two constraint edges, return true if A is less than B */
771
  /* Only insert constraints that do not already exist.  */
751
772
  if (place >= VEC_length (constraint_t, complex)
752
static bool
773
      || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
753
constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
774
    VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
754
{
755
  if (a->dest < b->dest)
756
    return true;
757
  return false;
758
}
775
}
759
776
760
/* Find the constraint edge that matches LOOKFOR, in VEC.
761
   Return the edge, if found, NULL otherwise.  */
762
763
static constraint_edge_t 
764
constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec, 
765
			  struct constraint_edge lookfor)
766
{
767
  unsigned int place;  
768
  constraint_edge_t edge = NULL;
769
770
  place = VEC_lower_bound (constraint_edge_t, vec, &lookfor, 
771
			   constraint_edge_less);
772
  if (place >= VEC_length (constraint_edge_t, vec))
773
    return NULL;
774
  edge = VEC_index (constraint_edge_t, vec, place);
775
  if (!constraint_edge_equal (*edge, lookfor))
776
    return NULL;
777
  return edge;
778
}
779
777
780
/* Condense two variable nodes into a single variable node, by moving
778
/* Condense two variable nodes into a single variable node, by moving
781
   all associated info from SRC to TO.  */
779
   all associated info from SRC to TO.  */
782
780
783
static void 
781
static void
784
condense_varmap_nodes (unsigned int to, unsigned int src)
782
merge_node_constraints (constraint_graph_t graph, unsigned int to,
783
			unsigned int from)
785
{
784
{
786
  varinfo_t tovi = get_varinfo (to);
787
  varinfo_t srcvi = get_varinfo (src);
788
  unsigned int i;
785
  unsigned int i;
789
  constraint_t c;
786
  constraint_t c;
790
  bitmap_iterator bi;
787
791
  
788
  gcc_assert (find (from) == to);
792
  /* the src node, and all its variables, are now the to node.  */
789
793
  srcvi->node = to;
794
  EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
795
    get_varinfo (i)->node = to;
796
  
797
  /* Merge the src node variables and the to node variables.  */
798
  bitmap_set_bit (tovi->variables, src);
799
  bitmap_ior_into (tovi->variables, srcvi->variables);
800
  bitmap_clear (srcvi->variables);
801
  
802
  /* Move all complex constraints from src node into to node  */
790
  /* Move all complex constraints from src node into to node  */
803
  for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
791
  for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
804
    {
792
    {
805
      /* In complex constraints for node src, we may have either
793
      /* In complex constraints for node src, we may have either
806
	 a = *src, and *src = a.  */
794
	 a = *src, and *src = a, or an offseted constraint which are
807
      
795
	 always added to the rhs node's constraints.  */
796
808
      if (c->rhs.type == DEREF)
797
      if (c->rhs.type == DEREF)
809
	c->rhs.var = to;
798
	c->rhs.var = to;
810
      else
799
      else if (c->lhs.type == DEREF)
811
	c->lhs.var = to;
800
	c->lhs.var = to;
801
      else
802
	c->rhs.var = to;
812
    }
803
    }
813
  constraint_set_union (&tovi->complex, &srcvi->complex);
804
  constraint_set_union (&graph->complex[to], &graph->complex[from]);
814
  VEC_free (constraint_t, heap, srcvi->complex);
805
  VEC_free (constraint_t, heap, graph->complex[from]);
815
  srcvi->complex = NULL;
806
  graph->complex[from] = NULL;
816
}
807
}
817
808
818
/* Erase an edge from SRC to SRC from GRAPH.  This routine only
819
   handles self-edges (e.g. an edge from a to a).  */
820
821
static void
822
erase_graph_self_edge (constraint_graph_t graph, unsigned int src)
823
{
824
  VEC(constraint_edge_t,heap) *predvec = graph->preds[src];
825
  VEC(constraint_edge_t,heap) *succvec = graph->succs[src];
826
  struct constraint_edge edge;
827
  unsigned int place;
828
829
  edge.dest = src;
830
831
  /* Remove from the successors.  */
832
  place = VEC_lower_bound (constraint_edge_t, succvec, &edge, 
833
			   constraint_edge_less);
834
  
835
  /* Make sure we found the edge.  */
836
#ifdef ENABLE_CHECKING
837
  {
838
    constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
839
    gcc_assert (constraint_edge_equal (*tmp, edge));
840
  }
841
#endif
842
  VEC_ordered_remove (constraint_edge_t, succvec, place);
843
844
  /* Remove from the predecessors.  */
845
  place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
846
			   constraint_edge_less);
847
848
  /* Make sure we found the edge.  */
849
#ifdef ENABLE_CHECKING
850
  {
851
    constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
852
    gcc_assert (constraint_edge_equal (*tmp, edge));
853
  }
854
#endif
855
  VEC_ordered_remove (constraint_edge_t, predvec, place);
856
}
857
809
858
/* Remove edges involving NODE from GRAPH.  */
810
/* Remove edges involving NODE from GRAPH.  */
859
811
860
static void
812
static void
861
clear_edges_for_node (constraint_graph_t graph, unsigned int node)
813
clear_edges_for_node (constraint_graph_t graph, unsigned int node)
862
{
814
{
863
  VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
815
  if (graph->succs[node])
864
  VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
816
    BITMAP_FREE (graph->succs[node]);
865
  bitmap_iterator bi;
866
  unsigned int j;
867
  constraint_edge_t c = NULL;
868
  int i;
869
870
  /* Walk the successors, erase the associated preds.  */
871
  
872
  EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[node], 0, j, bi)
873
    if (j != node)
874
      bitmap_clear_bit (graph->zero_weight_preds[j], node);
875
  
876
  for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
877
    if (c->dest != node)
878
      {
879
	unsigned int place;
880
	struct constraint_edge lookfor;
881
	constraint_edge_t result;
882
883
	lookfor.dest = node;
884
	place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest], 
885
				 &lookfor, constraint_edge_less);
886
	result = VEC_ordered_remove (constraint_edge_t, 
887
				     graph->preds[c->dest], place);
888
	pool_free (constraint_edge_pool, result);
889
      }
890
891
  /* Walk the preds, erase the associated succs.  */
892
893
  EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[node], 0, j, bi)
894
    if (j != node)
895
      bitmap_clear_bit (graph->zero_weight_succs[j], node);
896
  
897
  for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
898
    if (c->dest != node)
899
      {
900
	unsigned int place;
901
	struct constraint_edge lookfor;
902
	constraint_edge_t result;
903
904
	lookfor.dest = node;
905
	place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
906
				 &lookfor, constraint_edge_less);
907
	result = VEC_ordered_remove (constraint_edge_t, 
908
				     graph->succs[c->dest], place);
909
	pool_free (constraint_edge_pool, result);
910
911
      }    
912
913
  if (graph->zero_weight_preds[node])
914
    {
915
      BITMAP_FREE (graph->zero_weight_preds[node]);
916
      graph->zero_weight_preds[node] = NULL;
917
    } 
918
919
  if (graph->zero_weight_succs[node])
920
    {
921
      BITMAP_FREE (graph->zero_weight_succs[node]);
922
      graph->zero_weight_succs[node] = NULL;
923
    } 
924
925
  VEC_free (constraint_edge_t, heap, graph->preds[node]);
926
  VEC_free (constraint_edge_t, heap, graph->succs[node]);
927
  graph->preds[node] = NULL;
928
  graph->succs[node] = NULL;
929
}
930
931
static bool edge_added = false;
932
  
933
/* Add edge (src, dest) to the graph.  */
934
935
static bool
936
add_graph_edge (constraint_graph_t graph, unsigned int src, unsigned int dest)
937
{
938
  unsigned int place;
939
  VEC(constraint_edge_t,heap) *vec;
940
  struct constraint_edge newe;
941
  newe.dest = dest;
942
943
  vec = graph->preds[src];
944
  place = VEC_lower_bound (constraint_edge_t, vec, &newe, 
945
			   constraint_edge_less);
946
  if (place == VEC_length (constraint_edge_t, vec)
947
      || VEC_index (constraint_edge_t, vec, place)->dest != dest)
948
    {
949
      constraint_edge_t edge = new_constraint_edge (dest);
950
951
      VEC_safe_insert (constraint_edge_t, heap, graph->preds[src], 
952
		       place, edge);
953
      edge = new_constraint_edge (src);
954
955
      place = VEC_lower_bound (constraint_edge_t, graph->succs[dest],
956
			       edge, constraint_edge_less);
957
      VEC_safe_insert (constraint_edge_t, heap, graph->succs[dest], 
958
		       place, edge);
959
      edge_added = true;
960
      stats.num_edges++;
961
      return true;
962
    }
963
  else
964
    return false;
965
}
966
967
968
/* Return the bitmap representing the weights of edge (SRC, DEST).  */
969
970
static bitmap *
971
get_graph_weights (constraint_graph_t graph, unsigned int src,
972
		   unsigned int dest)
973
{
974
  constraint_edge_t edge;
975
  VEC(constraint_edge_t,heap) *vec;
976
  struct constraint_edge lookfor;
977
978
  lookfor.dest = dest;
979
980
  vec = graph->preds[src];
981
  edge = constraint_edge_vec_find (vec, lookfor);
982
  gcc_assert (edge != NULL);
983
  return &edge->weights;
984
}
985
986
/* Allocate graph weight bitmap for the edges associated with SRC and
987
   DEST in GRAPH.  Both the pred and the succ edges share a single
988
   bitmap, so we need to set both edges to that bitmap.  */
989
990
static bitmap
991
allocate_graph_weights (constraint_graph_t graph, unsigned int src, 
992
			unsigned int dest)
993
{
994
  bitmap result;
995
  constraint_edge_t edge;
996
  VEC(constraint_edge_t,heap) *vec;
997
  struct constraint_edge lookfor;
998
  
999
  result = BITMAP_ALLOC (&ptabitmap_obstack);
1000
1001
  /* Set the pred weight.  */
1002
  lookfor.dest = dest;
1003
  vec = graph->preds[src];
1004
  edge = constraint_edge_vec_find (vec, lookfor);
1005
  gcc_assert (edge != NULL);
1006
  edge->weights = result;
1007
1008
  /* Set the succ weight.  */  
1009
  lookfor.dest = src;
1010
  vec = graph->succs[dest];
1011
  edge = constraint_edge_vec_find (vec, lookfor);
1012
  gcc_assert (edge != NULL);
1013
  edge->weights = result;
1014
  
1015
  return result;  
1016
}
817
}
1017
818
1018
1019
/* Merge GRAPH nodes FROM and TO into node TO.  */
819
/* Merge GRAPH nodes FROM and TO into node TO.  */
1020
820
1021
static void
821
static void
1022
merge_graph_nodes (constraint_graph_t graph, unsigned int to, 
822
merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1023
		   unsigned int from)
823
		   unsigned int from)
1024
{
824
{
1025
  VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
825
  if (graph->indirect_cycles[from] != -1)
1026
  VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
1027
  int i;
1028
  constraint_edge_t c;
1029
  unsigned int j;
1030
  bitmap_iterator bi;
1031
1032
  /* Merge all the zero weighted predecessor edges.  */
1033
  if (graph->zero_weight_preds[from])
1034
    {
826
    {
1035
      if (!graph->zero_weight_preds[to])
827
      /* If we have indirect cycles with the from node, and we have
1036
	graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
828
	 none on the to node, the to node has indirect cycles from the
1037
      
829
	 from node now that they are unified.
1038
      EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_preds[from], 0, j, bi)
830
	 If indirect cycles exist on both, unify the nodes that they
831
	 are in a cycle with, since we know they are in a cycle with
832
	 each other.  */
833
      if (graph->indirect_cycles[to] == -1)
1039
	{
834
	{
1040
	  if (j != to)
835
	  graph->indirect_cycles[to] = graph->indirect_cycles[from];
1041
	    {
1042
	      bitmap_clear_bit (graph->zero_weight_succs[j], from);
1043
	      bitmap_set_bit (graph->zero_weight_succs[j], to);
1044
	    }
1045
	}
836
	}
1046
      bitmap_ior_into (graph->zero_weight_preds[to], 
837
      else
1047
		       graph->zero_weight_preds[from]);
1048
    }
1049
1050
  /* Merge all the zero weighted successor edges.  */
1051
  if (graph->zero_weight_succs[from])
1052
    {
1053
      if (!graph->zero_weight_succs[to])
1054
	graph->zero_weight_succs[to] = BITMAP_ALLOC (&ptabitmap_obstack);
1055
      EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_succs[from], 0, j, bi)
1056
	{
838
	{
1057
	  bitmap_clear_bit (graph->zero_weight_preds[j], from);
839
	  unsigned int tonode = find (graph->indirect_cycles[to]);
1058
	  bitmap_set_bit (graph->zero_weight_preds[j], to);
840
	  unsigned int fromnode = find (graph->indirect_cycles[from]);
841
842
	  if (unite (tonode, fromnode))
843
	    unify_nodes (graph, tonode, fromnode, true);
1059
	}
844
	}
1060
      bitmap_ior_into (graph->zero_weight_succs[to], 
1061
		       graph->zero_weight_succs[from]);
1062
    }
845
    }
1063
846
1064
  /* Merge all the nonzero weighted predecessor edges.  */
847
  /* Merge all the successor edges.  */
1065
  for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
848
  if (graph->succs[from])
1066
    {
849
    {
1067
      unsigned int d = c->dest;
850
      if (!graph->succs[to])
1068
      bitmap temp;
851
	graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1069
      bitmap *weights;
852
      bitmap_ior_into (graph->succs[to],
853
		       graph->succs[from]);
854
    }
1070
855
1071
      if (c->dest == from)
856
  clear_edges_for_node (graph, from);
1072
	d = to;
857
}
1073
858
1074
      add_graph_edge (graph, to, d);
1075
859
1076
      temp = *(get_graph_weights (graph, from, c->dest));      
860
/* Add an indirect graph edge to GRAPH, going from TO to FROM if
1077
      if (temp)
861
   it doesn't exist in the graph already.  */
1078
	{
1079
	  weights = get_graph_weights (graph, to, d);
1080
	  if (!*weights)
1081
	    *weights = allocate_graph_weights (graph, to, d);
1082
	  
1083
	  bitmap_ior_into (*weights, temp);
1084
	}
1085
      
1086
    }
1087
  
1088
  /* Merge all the nonzero weighted successor edges.  */
1089
  for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
1090
    {
1091
      unsigned int d = c->dest;
1092
      bitmap temp;
1093
      bitmap *weights;
1094
862
1095
      if (c->dest == from)
863
static void
1096
	d = to;
864
add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
865
			 unsigned int from)
866
{
867
  if (to == from)
868
    return;
1097
869
1098
      add_graph_edge (graph, d, to);
870
  if (!graph->implicit_preds[to])
871
    graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1099
872
1100
      temp = *(get_graph_weights (graph, c->dest, from));
873
  if (!bitmap_bit_p (graph->implicit_preds[to], from))
1101
      if (temp)
874
    {
1102
	{
875
      stats.num_implicit_edges++;
1103
	  weights = get_graph_weights (graph, d, to);
876
      bitmap_set_bit (graph->implicit_preds[to], from);
1104
	  if (!*weights)
1105
	    *weights = allocate_graph_weights (graph, d, to);
1106
	  bitmap_ior_into (*weights, temp);
1107
	}
1108
    }
877
    }
1109
  clear_edges_for_node (graph, from);
1110
}
878
}
1111
879
1112
/* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
880
/* Add a predecessor graph edge to GRAPH, going from TO to FROM if
881
   it doesn't exist in the graph already.
882
   Return false if the edge already existed, true otherwise.  */
883
884
static void
885
add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
886
		     unsigned int from)
887
{
888
  if (!graph->preds[to])
889
    graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
890
  if (!bitmap_bit_p (graph->preds[to], from))
891
    bitmap_set_bit (graph->preds[to], from);
892
}
893
894
/* Add a graph edge to GRAPH, going from FROM to TO if
1113
   it doesn't exist in the graph already.
895
   it doesn't exist in the graph already.
1114
   Return false if the edge already existed, true otherwise.  */
896
   Return false if the edge already existed, true otherwise.  */
1115
897
1116
static bool
898
static bool
1117
int_add_graph_edge (constraint_graph_t graph, unsigned int to, 
899
add_graph_edge (constraint_graph_t graph, unsigned int to,
1118
		    unsigned int from, unsigned HOST_WIDE_INT weight)
900
		unsigned int from)
1119
{
901
{
1120
  if (to == from && weight == 0)
902
  if (to == from)
1121
    {
903
    {
1122
      return false;
904
      return false;
1123
    }
905
    }
Lines 1125-1165 int_add_graph_edge (constraint_graph_t g Link Here
1125
    {
907
    {
1126
      bool r = false;
908
      bool r = false;
1127
909
1128
      if (weight == 0)
910
      if (!graph->succs[from])
1129
	{
911
	graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1130
          if (!graph->zero_weight_preds[to])
912
      if (!bitmap_bit_p (graph->succs[from], to))
1131
	    graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
913
	{
1132
          if (!graph->zero_weight_succs[from])
914
	  r = true;
1133
	    graph->zero_weight_succs[from] = BITMAP_ALLOC (&ptabitmap_obstack);
915
	  if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1134
	  if (!bitmap_bit_p (graph->zero_weight_succs[from], to))
916
	    stats.num_edges++;
1135
	    {
917
	  bitmap_set_bit (graph->succs[from], to);
1136
	      edge_added = true;
1137
	      r = true;
1138
	      stats.num_edges++;
1139
	      bitmap_set_bit (graph->zero_weight_preds[to], from);
1140
	      bitmap_set_bit (graph->zero_weight_succs[from], to);
1141
	    }
1142
	}
1143
      else
1144
	{
1145
	  bitmap *weights;
1146
1147
	  r = add_graph_edge (graph, to, from);
1148
	  weights = get_graph_weights (graph, to, from);
1149
1150
	  if (!*weights)
1151
	    {
1152
	      r = true;
1153
	      *weights = allocate_graph_weights (graph, to, from);
1154
	      bitmap_set_bit (*weights, weight);
1155
	    }
1156
	  else
1157
	    {
1158
	      r |= !bitmap_bit_p (*weights, weight);
1159
	      bitmap_set_bit (*weights, weight);
1160
	    }
1161
	}
918
	}
1162
      
1163
      return r;
919
      return r;
1164
    }
920
    }
1165
}
921
}
Lines 1168-1212 int_add_graph_edge (constraint_graph_t g Link Here
1168
/* Return true if {DEST.SRC} is an existing graph edge in GRAPH.  */
924
/* Return true if {DEST.SRC} is an existing graph edge in GRAPH.  */
1169
925
1170
static bool
926
static bool
1171
valid_graph_edge (constraint_graph_t graph, unsigned int src, 
927
valid_graph_edge (constraint_graph_t graph, unsigned int src,
1172
		  unsigned int dest)
928
		  unsigned int dest)
1173
{
929
{
1174
  struct constraint_edge lookfor;
930
  return (graph->succs[dest]
1175
  lookfor.dest = src;
931
	  && bitmap_bit_p (graph->succs[dest], src));
1176
  
1177
  return (graph->zero_weight_succs[dest] 
1178
      && bitmap_bit_p (graph->zero_weight_succs[dest], src)) 
1179
    || constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1180
}
1181
1182
/* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1183
   a weight other than 0) in GRAPH.  */
1184
static bool
1185
valid_weighted_graph_edge (constraint_graph_t graph, unsigned int src, 
1186
			   unsigned int dest)
1187
{
1188
  struct constraint_edge lookfor;
1189
  lookfor.dest = src;
1190
  
1191
  return graph->preds[src] 
1192
    && constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1193
}
932
}
1194
933
1195
934
/* Build the constraint graph, adding only predecessor edges right now.  */
1196
/* Build the constraint graph.  */
1197
935
1198
static void
936
static void
1199
build_constraint_graph (void)
937
build_pred_graph (void)
1200
{
938
{
1201
  int i = 0;
939
  int i;
1202
  constraint_t c;
940
  constraint_t c;
941
  unsigned int j;
1203
942
1204
  graph = XNEW (struct constraint_graph);
943
  graph = XNEW (struct constraint_graph);
1205
  graph_size = VEC_length (varinfo_t, varmap) + 1;
944
  graph->size = (VEC_length (varinfo_t, varmap)) * 3;
1206
  graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
945
  graph->succs = XCNEWVEC (bitmap, graph->size);
1207
  graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
946
  graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1208
  graph->zero_weight_succs = XCNEWVEC (bitmap, graph_size);
947
  graph->preds = XCNEWVEC (bitmap, graph->size);
1209
  graph->zero_weight_preds = XCNEWVEC (bitmap, graph_size);
948
  graph->indirect_cycles = XNEWVEC (int, VEC_length (varinfo_t, varmap));
949
  graph->label = XCNEWVEC (unsigned int, graph->size);
950
  graph->rep = XNEWVEC (unsigned int, graph->size);
951
  graph->eq_rep = XNEWVEC (int, graph->size);
952
  graph->complex = XCNEWVEC (VEC(constraint_t, heap) *,
953
			     VEC_length (varinfo_t, varmap));
954
  graph->direct_nodes = sbitmap_alloc (graph->size);
955
  sbitmap_zero (graph->direct_nodes);
956
957
  for (j = 0; j < FIRST_REF_NODE; j++)
958
    {
959
      if (!get_varinfo (j)->is_special_var)
960
	SET_BIT (graph->direct_nodes, j);
961
    }
962
963
  for (j = 0; j < graph->size; j++)
964
    {
965
      graph->rep[j] = j;
966
      graph->eq_rep[j] = -1;
967
    }
968
969
  for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
970
    graph->indirect_cycles[j] = -1;
1210
971
1211
  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
972
  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1212
    {
973
    {
Lines 1217-1279 build_constraint_graph (void) Link Here
1217
978
1218
      if (lhs.type == DEREF)
979
      if (lhs.type == DEREF)
1219
	{
980
	{
1220
	  /* *x = y or *x = &y (complex) */
981
	  /* *x = y.  */
1221
	  if (rhs.type == ADDRESSOF || rhsvar > anything_id)
982
	  if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1222
	    insert_into_complex (lhsvar, c);
983
	    add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
984
	  if (rhs.type == ADDRESSOF)
985
	    RESET_BIT (graph->direct_nodes, rhsvar);
1223
	}
986
	}
1224
      else if (rhs.type == DEREF)
987
      else if (rhs.type == DEREF)
1225
	{
988
	{
1226
	  /* !special var= *y */
989
	  /* x = *y */
1227
	  if (!(get_varinfo (lhsvar)->is_special_var))
990
	  if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1228
	    insert_into_complex (rhsvar, c);
991
	    add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
992
	  else
993
	    RESET_BIT (graph->direct_nodes, lhsvar);
1229
	}
994
	}
1230
      else if (rhs.type == ADDRESSOF)
995
      else if (rhs.type == ADDRESSOF)
1231
	{
996
	{
1232
	  /* x = &y */
997
	  /* x = &y */
1233
	  bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
998
	  add_pred_graph_edge (graph, lhsvar, FIRST_ADDR_NODE + rhsvar);
999
	  /* Implicitly, *x = y */
1000
	  add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1001
1002
	  RESET_BIT (graph->direct_nodes, rhsvar);
1234
	}
1003
	}
1235
      else if (lhsvar > anything_id)
1004
      else if (lhsvar > anything_id
1005
	       && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1236
	{
1006
	{
1237
	  /* Ignore 0 weighted self edges, as they can't possibly contribute
1007
	  /* x = y */
1238
	     anything */
1008
	  add_pred_graph_edge (graph, lhsvar, rhsvar);
1239
	  if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
1009
	  /* Implicitly, *x = *y */
1240
	    {
1010
	  add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1241
	      /* x = y (simple) */
1011
				   FIRST_REF_NODE + rhsvar);
1242
	      int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset);
1012
	}
1243
	    }
1013
      else if (lhs.offset != 0 || rhs.offset != 0)
1244
	  
1014
	{
1015
	  if (rhs.offset != 0)
1016
	    RESET_BIT (graph->direct_nodes, lhs.var);
1017
	  if (lhs.offset != 0)
1018
	    RESET_BIT (graph->direct_nodes, rhs.var);
1245
	}
1019
	}
1246
    }
1020
    }
1247
}
1021
}
1248
1022
1023
/* Build the constraint graph, adding successor edges.  */
1249
1024
1250
/* Changed variables on the last iteration.  */
1025
static void
1251
static unsigned int changed_count;
1026
build_succ_graph (void)
1252
static sbitmap changed;
1027
{
1028
  int i;
1029
  constraint_t c;
1253
1030
1254
DEF_VEC_I(unsigned);
1031
  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1255
DEF_VEC_ALLOC_I(unsigned,heap);
1032
    {
1033
      struct constraint_expr lhs;
1034
      struct constraint_expr rhs;
1035
      unsigned int lhsvar;
1036
      unsigned int rhsvar;
1256
1037
1038
      if (!c)
1039
	continue;
1257
1040
1258
/* Strongly Connected Component visitation info.  */
1041
      lhs = c->lhs;
1042
      rhs = c->rhs;
1043
      lhsvar = find (get_varinfo_fc (lhs.var)->id);
1044
      rhsvar = find (get_varinfo_fc (rhs.var)->id);
1259
1045
1260
struct scc_info
1046
      if (lhs.type == DEREF)
1261
{
1047
	{
1262
  sbitmap visited;
1048
	  if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1263
  sbitmap in_component;
1049
	    add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1050
	}
1051
      else if (rhs.type == DEREF)
1052
	{
1053
	  if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1054
	    add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1055
	}
1056
      else if (rhs.type == ADDRESSOF)
1057
	{
1058
	  /* x = &y */
1059
	  gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1060
		      == get_varinfo_fc (rhs.var)->id);
1061
	  bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1062
	}
1063
      else if (lhsvar > anything_id
1064
	       && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1065
	{
1066
	  add_graph_edge (graph, lhsvar, rhsvar);
1067
	}
1068
    }
1069
}
1070
1071
1072
/* Changed variables on the last iteration.  */
1073
static unsigned int changed_count;
1074
static sbitmap changed;
1075
1076
DEF_VEC_I(unsigned);
1077
DEF_VEC_ALLOC_I(unsigned,heap);
1078
1079
1080
/* Strongly Connected Component visitation info.  */
1081
1082
struct scc_info
1083
{
1084
  sbitmap visited;
1085
  sbitmap roots;
1086
  unsigned int *dfs;
1087
  unsigned int *node_mapping;
1264
  int current_index;
1088
  int current_index;
1265
  unsigned int *visited_index;
1266
  VEC(unsigned,heap) *scc_stack;
1089
  VEC(unsigned,heap) *scc_stack;
1267
  VEC(unsigned,heap) *unification_queue;
1268
};
1090
};
1269
1091
1270
1092
1271
/* Recursive routine to find strongly connected components in GRAPH.
1093
/* Recursive routine to find strongly connected components in GRAPH.
1272
   SI is the SCC info to store the information in, and N is the id of current
1094
   SI is the SCC info to store the information in, and N is the id of current
1273
   graph node we are processing.
1095
   graph node we are processing.
1274
   
1096
1275
   This is Tarjan's strongly connected component finding algorithm, as
1097
   This is Tarjan's strongly connected component finding algorithm, as
1276
   modified by Nuutila to keep only non-root nodes on the stack.  
1098
   modified by Nuutila to keep only non-root nodes on the stack.
1277
   The algorithm can be found in "On finding the strongly connected
1099
   The algorithm can be found in "On finding the strongly connected
1278
   connected components in a directed graph" by Esko Nuutila and Eljas
1100
   connected components in a directed graph" by Esko Nuutila and Eljas
1279
   Soisalon-Soininen, in Information Processing Letters volume 49,
1101
   Soisalon-Soininen, in Information Processing Letters volume 49,
Lines 1284-1470 scc_visit (constraint_graph_t graph, str Link Here
1284
{
1106
{
1285
  unsigned int i;
1107
  unsigned int i;
1286
  bitmap_iterator bi;
1108
  bitmap_iterator bi;
1109
  unsigned int my_dfs;
1287
1110
1288
  gcc_assert (get_varinfo (n)->node == n);
1289
  SET_BIT (si->visited, n);
1111
  SET_BIT (si->visited, n);
1290
  RESET_BIT (si->in_component, n);
1112
  si->dfs[n] = si->current_index ++;
1291
  si->visited_index[n] = si->current_index ++;
1113
  my_dfs = si->dfs[n];
1292
  
1114
1293
  /* Visit all the successors.  */
1115
  /* Visit all the successors.  */
1294
  EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi)
1116
  EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1295
    {
1117
    {
1296
      unsigned int w = i;
1118
      unsigned int w;
1119
1120
      if (i > LAST_REF_NODE)
1121
	break;
1122
1123
      w = find (i);
1124
      if (TEST_BIT (si->roots, w))
1125
	continue;
1126
1297
      if (!TEST_BIT (si->visited, w))
1127
      if (!TEST_BIT (si->visited, w))
1298
	scc_visit (graph, si, w);
1128
	scc_visit (graph, si, w);
1299
      if (!TEST_BIT (si->in_component, w))
1129
      {
1300
	{
1130
	unsigned int t = find (w);
1301
	  unsigned int t = get_varinfo (w)->node;
1131
	unsigned int nnode = find (n);
1302
	  unsigned int nnode = get_varinfo (n)->node;
1132
	gcc_assert (nnode == n);
1303
	  if (si->visited_index[t] < si->visited_index[nnode])
1133
1304
	    get_varinfo (n)->node = t;
1134
	if (si->dfs[t] < si->dfs[nnode])
1305
	}
1135
	  si->dfs[n] = si->dfs[t];
1136
      }
1306
    }
1137
    }
1307
  
1138
1308
  /* See if any components have been identified.  */
1139
  /* See if any components have been identified.  */
1309
  if (get_varinfo (n)->node == n)
1140
  if (si->dfs[n] == my_dfs)
1310
    {
1141
    {
1311
      unsigned int t = si->visited_index[n];
1142
      if (VEC_length (unsigned, si->scc_stack) > 0
1312
      SET_BIT (si->in_component, n);
1143
	  && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1313
      while (VEC_length (unsigned, si->scc_stack) != 0 
1314
	     && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1315
	{
1144
	{
1316
	  unsigned int w = VEC_pop (unsigned, si->scc_stack);
1145
	  bitmap scc = BITMAP_ALLOC (NULL);
1317
	  get_varinfo (w)->node = n;
1146
	  bool have_ref_node = n >= FIRST_REF_NODE;
1318
	  SET_BIT (si->in_component, w);
1147
	  unsigned int lowest_node;
1319
	  /* Mark this node for collapsing.  */
1148
	  bitmap_iterator bi;
1320
	  VEC_safe_push (unsigned, heap, si->unification_queue, w);
1321
	} 
1322
    }
1323
  else
1324
    VEC_safe_push (unsigned, heap, si->scc_stack, n);
1325
}
1326
1327
1149
1328
/* Collapse two variables into one variable.  */
1150
	  bitmap_set_bit (scc, n);
1329
1151
1330
static void
1152
	  while (VEC_length (unsigned, si->scc_stack) != 0
1331
collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1153
		 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1332
{
1154
	    {
1333
  bitmap tosol, fromsol;
1155
	      unsigned int w = VEC_pop (unsigned, si->scc_stack);
1334
1156
1335
  condense_varmap_nodes (to, from);
1157
	      bitmap_set_bit (scc, w);
1336
  tosol = get_varinfo (to)->solution;
1158
	      if (w >= FIRST_REF_NODE)
1337
  fromsol = get_varinfo (from)->solution;
1159
		have_ref_node = true;
1338
  bitmap_ior_into (tosol, fromsol);
1160
	    }
1339
  merge_graph_nodes (graph, to, from);
1340
1161
1341
  if (valid_graph_edge (graph, to, to))
1162
	  lowest_node = bitmap_first_set_bit (scc);
1342
    {
1163
	  gcc_assert (lowest_node < FIRST_REF_NODE);
1343
      if (graph->zero_weight_preds[to])
1164
	  EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1344
	{
1165
	    {
1345
	  bitmap_clear_bit (graph->zero_weight_preds[to], to);
1166
	      if (i < FIRST_REF_NODE)
1346
	  bitmap_clear_bit (graph->zero_weight_succs[to], to);
1167
		{
1347
	}
1168
		  /* Mark this node for collapsing.  */
1348
      if (valid_weighted_graph_edge (graph, to, to))
1169
		  if (unite (lowest_node, i))
1349
	{
1170
		    unify_nodes (graph, lowest_node, i, false);
1350
	  bitmap weights = *(get_graph_weights (graph, to, to));
1171
		}
1351
	  if (!weights || bitmap_empty_p (weights))
1172
	      else
1352
	    erase_graph_self_edge (graph, to);
1173
		{
1174
		  unite (lowest_node, i);
1175
		  graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1176
		}
1177
	    }
1353
	}
1178
	}
1179
      SET_BIT (si->roots, n);
1354
    }
1180
    }
1355
  BITMAP_FREE (fromsol);
1181
  else
1356
  get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1182
    VEC_safe_push (unsigned, heap, si->scc_stack, n);
1357
  get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1358
}
1183
}
1359
1184
1360
1185
/* Unify node FROM into node TO, updating the changed count if
1361
/* Unify nodes in GRAPH that we have found to be part of a cycle.
1186
   necessary when UPDATE_CHANGED is true.  */
1362
   SI is the Strongly Connected Components information structure that tells us
1363
   what components to unify.
1364
   UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1365
   count should be updated to reflect the unification.  */
1366
1187
1367
static void
1188
static void
1368
process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1189
unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1369
			   bool update_changed)
1190
	     bool update_changed)
1370
{
1191
{
1371
  size_t i = 0;
1372
  bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1373
  bitmap_clear (tmp);
1374
1375
  /* We proceed as follows:
1376
1192
1377
     For each component in the queue (components are delineated by
1193
  gcc_assert (to != from && find (to) == to);
1378
     when current_queue_element->node != next_queue_element->node):
1194
  if (dump_file && (dump_flags & TDF_DETAILS))
1195
    fprintf (dump_file, "Unifying %s to %s\n",
1196
	     get_varinfo (from)->name,
1197
	     get_varinfo (to)->name);
1379
1198
1380
        rep = representative node for component
1199
  if (update_changed)
1381
1200
    stats.unified_vars_dynamic++;
1382
        For each node (tounify) to be unified in the component,
1201
  else
1383
           merge the solution for tounify into tmp bitmap
1202
    stats.unified_vars_static++;
1384
1385
           clear solution for tounify
1386
1387
           merge edges from tounify into rep
1388
1389
	   merge complex constraints from tounify into rep
1390
1203
1391
	   update changed count to note that tounify will never change
1204
  merge_graph_nodes (graph, to, from);
1392
	   again
1205
  merge_node_constraints (graph, to, from);
1393
1206
1394
	Merge tmp into solution for rep, marking rep changed if this
1207
  if (update_changed && TEST_BIT (changed, from))
1395
	changed rep's solution.
1396
	
1397
	Delete any 0 weighted self-edges we now have for rep.  */
1398
  while (i != VEC_length (unsigned, si->unification_queue))
1399
    {
1208
    {
1400
      unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1209
      RESET_BIT (changed, from);
1401
      unsigned int n = get_varinfo (tounify)->node;
1210
      if (!TEST_BIT (changed, to))
1402
1211
	SET_BIT (changed, to);
1403
      if (dump_file && (dump_flags & TDF_DETAILS))
1404
	fprintf (dump_file, "Unifying %s to %s\n", 
1405
		 get_varinfo (tounify)->name,
1406
		 get_varinfo (n)->name);
1407
      if (update_changed)
1408
	stats.unified_vars_dynamic++;
1409
      else
1212
      else
1410
	stats.unified_vars_static++;
1411
      bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1412
      merge_graph_nodes (graph, n, tounify);
1413
      condense_varmap_nodes (n, tounify);
1414
      
1415
      if (update_changed && TEST_BIT (changed, tounify))
1416
	{
1213
	{
1417
	  RESET_BIT (changed, tounify);
1214
	  gcc_assert (changed_count > 0);
1418
	  if (!TEST_BIT (changed, n))
1215
	  changed_count--;
1419
	    SET_BIT (changed, n);
1420
	  else
1421
	    {
1422
	      gcc_assert (changed_count > 0);
1423
	      changed_count--;
1424
	    }
1425
	}
1216
	}
1217
    }
1426
1218
1427
      bitmap_clear (get_varinfo (tounify)->solution);
1219
  /* If the solution changes because of the merging, we need to mark
1428
      ++i;
1220
     the variable as changed.  */
1221
  if (bitmap_ior_into (get_varinfo (to)->solution,
1222
		       get_varinfo (from)->solution))
1223
    {
1224
      if (update_changed && !TEST_BIT (changed, to))
1225
	{
1226
	  SET_BIT (changed, to);
1227
	  changed_count++;
1228
	}
1229
    }
1429
1230
1430
      /* If we've either finished processing the entire queue, or
1231
  BITMAP_FREE (get_varinfo (from)->solution);
1431
	 finished processing all nodes for component n, update the solution for
1232
  BITMAP_FREE (get_varinfo (from)->oldsolution);
1432
	 n.  */
1433
      if (i == VEC_length (unsigned, si->unification_queue)
1434
	  || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1435
	{
1436
	  /* If the solution changes because of the merging, we need to mark
1437
	     the variable as changed.  */
1438
	  if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1439
	    {
1440
	      if (update_changed && !TEST_BIT (changed, n))
1441
		{
1442
		  SET_BIT (changed, n);
1443
		  changed_count++;
1444
		}
1445
	    }
1446
	  bitmap_clear (tmp);
1447
1233
1448
	  if (valid_graph_edge (graph, n, n))
1234
  if (stats.iterations > 0)
1449
	    {
1235
    {
1450
	      if (graph->zero_weight_succs[n])
1236
      BITMAP_FREE (get_varinfo (to)->oldsolution);
1451
		{
1237
      get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1452
		  if (graph->zero_weight_preds[n])
1453
		    bitmap_clear_bit (graph->zero_weight_preds[n], n);
1454
		  bitmap_clear_bit (graph->zero_weight_succs[n], n);
1455
		}
1456
	      if (valid_weighted_graph_edge (graph, n, n))
1457
		{
1458
		  bitmap weights = *(get_graph_weights (graph, n, n));
1459
		  if (!weights || bitmap_empty_p (weights))
1460
		    erase_graph_self_edge (graph, n);
1461
		}
1462
	    }
1463
	}
1464
    }
1238
    }
1465
  BITMAP_FREE (tmp);
1466
}
1467
1239
1240
  if (valid_graph_edge (graph, to, to))
1241
    {
1242
      if (graph->succs[to])
1243
	bitmap_clear_bit (graph->succs[to], to);
1244
    }
1245
}
1468
1246
1469
/* Information needed to compute the topological ordering of a graph.  */
1247
/* Information needed to compute the topological ordering of a graph.  */
1470
1248
Lines 1509-1545 static void Link Here
1509
topo_visit (constraint_graph_t graph, struct topo_info *ti,
1287
topo_visit (constraint_graph_t graph, struct topo_info *ti,
1510
	    unsigned int n)
1288
	    unsigned int n)
1511
{
1289
{
1512
  VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1513
  bitmap temp;
1514
  bitmap_iterator bi;
1290
  bitmap_iterator bi;
1515
  constraint_edge_t c;
1516
  int i;
1517
  unsigned int j;
1291
  unsigned int j;
1518
1292
1519
  SET_BIT (ti->visited, n);
1293
  SET_BIT (ti->visited, n);
1520
  if (VEC_length (constraint_edge_t, succs) != 0)
1521
    {
1522
      temp = BITMAP_ALLOC (&iteration_obstack);
1523
      if (graph->zero_weight_succs[n])
1524
	bitmap_ior_into (temp, graph->zero_weight_succs[n]);
1525
      for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1526
	bitmap_set_bit (temp, c->dest);
1527
    }
1528
  else 
1529
    temp = graph->zero_weight_succs[n];
1530
1294
1531
  if (temp) 
1295
  if (graph->succs[n])
1532
    EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
1296
    EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1533
      {
1297
      {
1534
	if (!TEST_BIT (ti->visited, j))
1298
	if (!TEST_BIT (ti->visited, j))
1535
	  topo_visit (graph, ti, j);
1299
	  topo_visit (graph, ti, j);
1536
      }
1300
      }
1301
1537
  VEC_safe_push (unsigned, heap, ti->topo_order, n);
1302
  VEC_safe_push (unsigned, heap, ti->topo_order, n);
1538
}
1303
}
1539
1304
1540
/* Return true if variable N + OFFSET is a legal field of N.  */
1305
/* Return true if variable N + OFFSET is a legal field of N.  */
1541
1306
1542
static bool 
1307
static bool
1543
type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1308
type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1544
{
1309
{
1545
  varinfo_t ninfo = get_varinfo (n);
1310
  varinfo_t ninfo = get_varinfo (n);
Lines 1582-1591 do_da_constraint (constraint_graph_t gra Link Here
1582
	  v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1347
	  v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1583
	  if (!v)
1348
	  if (!v)
1584
	    continue;
1349
	    continue;
1585
	  t = v->node;
1350
	  t = find (v->id);
1586
	  sol = get_varinfo (t)->solution;
1351
	  sol = get_varinfo (t)->solution;
1587
	  if (!bitmap_bit_p (sol, rhs))
1352
	  if (!bitmap_bit_p (sol, rhs))
1588
	    {		  
1353
	    {
1589
	      bitmap_set_bit (sol, rhs);
1354
	      bitmap_set_bit (sol, rhs);
1590
	      if (!TEST_BIT (changed, t))
1355
	      if (!TEST_BIT (changed, t))
1591
		{
1356
		{
Lines 1596-1602 do_da_constraint (constraint_graph_t gra Link Here
1596
	}
1361
	}
1597
      else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1362
      else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1598
	fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1363
	fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1599
      
1364
1600
    }
1365
    }
1601
}
1366
}
1602
1367
Lines 1607-1613 static void Link Here
1607
do_sd_constraint (constraint_graph_t graph, constraint_t c,
1372
do_sd_constraint (constraint_graph_t graph, constraint_t c,
1608
		  bitmap delta)
1373
		  bitmap delta)
1609
{
1374
{
1610
  unsigned int lhs = get_varinfo (c->lhs.var)->node;
1375
  unsigned int lhs = find (c->lhs.var);
1611
  bool flag = false;
1376
  bool flag = false;
1612
  bitmap sol = get_varinfo (lhs)->solution;
1377
  bitmap sol = get_varinfo (lhs)->solution;
1613
  unsigned int j;
1378
  unsigned int j;
Lines 1620-1626 do_sd_constraint (constraint_graph_t gra Link Here
1620
       bitmap_set_bit (sol, anything_id);
1385
       bitmap_set_bit (sol, anything_id);
1621
     goto done;
1386
     goto done;
1622
   }
1387
   }
1623
  /* For each variable j in delta (Sol(y)), add    
1388
  /* For each variable j in delta (Sol(y)), add
1624
     an edge in the graph from j to x, and union Sol(j) into Sol(x).  */
1389
     an edge in the graph from j to x, and union Sol(j) into Sol(x).  */
1625
  EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1390
  EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1626
    {
1391
    {
Lines 1634-1651 do_sd_constraint (constraint_graph_t gra Link Here
1634
	  v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1399
	  v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1635
	  if (!v)
1400
	  if (!v)
1636
	    continue;
1401
	    continue;
1637
	  t = v->node;
1402
	  t = find (v->id);
1638
1403
1639
	  /* Adding edges from the special vars is pointless.
1404
	  /* Adding edges from the special vars is pointless.
1640
	     They don't have sets that can change.  */
1405
	     They don't have sets that can change.  */
1641
	  if (get_varinfo (t) ->is_special_var)
1406
	  if (get_varinfo (t) ->is_special_var)
1642
	    flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1407
	    flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1643
	  else if (int_add_graph_edge (graph, lhs, t, 0))
1408
	  else if (add_graph_edge (graph, lhs, t))
1644
	    flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1409
	    flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1645
	}
1410
	}
1646
      else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1411
      else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1647
	fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1412
	fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1648
      
1413
1649
    }
1414
    }
1650
1415
1651
done:
1416
done:
Lines 1658-1672 done: Link Here
1658
	  SET_BIT (changed, lhs);
1423
	  SET_BIT (changed, lhs);
1659
	  changed_count++;
1424
	  changed_count++;
1660
	}
1425
	}
1661
    }    
1426
    }
1662
}
1427
}
1663
1428
1664
/* Process a constraint C that represents *x = y.  */
1429
/* Process a constraint C that represents *x = y.  */
1665
1430
1666
static void
1431
static void
1667
do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1432
do_ds_constraint (constraint_t c, bitmap delta)
1668
{
1433
{
1669
  unsigned int rhs = get_varinfo (c->rhs.var)->node;
1434
  unsigned int rhs = find (c->rhs.var);
1670
  unsigned HOST_WIDE_INT roff = c->rhs.offset;
1435
  unsigned HOST_WIDE_INT roff = c->rhs.offset;
1671
  bitmap sol = get_varinfo (rhs)->solution;
1436
  bitmap sol = get_varinfo (rhs)->solution;
1672
  unsigned int j;
1437
  unsigned int j;
Lines 1685-1692 do_ds_constraint (constraint_graph_t gra Link Here
1685
	 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1450
	 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1686
	 if (!v)
1451
	 if (!v)
1687
	   continue;
1452
	   continue;
1688
	 t = v->node;
1453
	 t = find (v->id);
1689
	 
1454
1690
	 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1455
	 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1691
	   {
1456
	   {
1692
	     bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1457
	     bitmap_set_bit (get_varinfo (t)->solution, anything_id);
Lines 1705-1744 do_ds_constraint (constraint_graph_t gra Link Here
1705
  EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1470
  EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1706
    {
1471
    {
1707
      unsigned HOST_WIDE_INT loff = c->lhs.offset;
1472
      unsigned HOST_WIDE_INT loff = c->lhs.offset;
1708
      if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1473
      if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1709
	{
1474
	{
1710
	  varinfo_t v;
1475
	  varinfo_t v;
1711
	  unsigned int t;
1476
	  unsigned int t;
1712
	  unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1477
	  unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1478
	  bitmap tmp;
1713
1479
1714
	  v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1480
	  v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1715
	  if (!v)
1481
	  if (!v)
1716
	    continue;
1482
	    continue;
1717
	  t = v->node;
1483
	  t = find (v->id);
1718
	  if (int_add_graph_edge (graph, t, rhs, roff))
1484
	  tmp = get_varinfo (t)->solution;
1485
1486
	  if (set_union_with_increment (tmp, sol, roff))
1719
	    {
1487
	    {
1720
	      bitmap tmp = get_varinfo (t)->solution;
1488
	      get_varinfo (t)->solution = tmp;
1721
	      if (set_union_with_increment (tmp, sol, roff))
1489
	      if (t == rhs)
1490
		sol = get_varinfo (rhs)->solution;
1491
	      if (!TEST_BIT (changed, t))
1722
		{
1492
		{
1723
		  get_varinfo (t)->solution = tmp;
1493
		  SET_BIT (changed, t);
1724
		  if (t == rhs)
1494
		  changed_count++;
1725
		    sol = get_varinfo (rhs)->solution;
1726
		  if (!TEST_BIT (changed, t))
1727
		    {
1728
		      SET_BIT (changed, t);
1729
		      changed_count++;
1730
		    }
1731
		}
1495
		}
1732
	    }
1496
	    }
1733
	}    
1497
	}
1734
      else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1498
      else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1735
	fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1499
	fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1736
    }
1500
    }
1737
}
1501
}
1738
1502
1739
/* Handle a non-simple (simple meaning requires no iteration), non-copy
1503
/* Handle a non-simple (simple meaning requires no iteration),
1740
   constraint (IE *x = &y, x = *y, and *x = y).  */
1504
   constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved).  */
1741
   
1505
1742
static void
1506
static void
1743
do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1507
do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1744
{
1508
{
Lines 1752-1784 do_complex_constraint (constraint_graph_ Link Here
1752
      else
1516
      else
1753
	{
1517
	{
1754
	  /* *x = y */
1518
	  /* *x = y */
1755
	  do_ds_constraint (graph, c, delta);
1519
	  do_ds_constraint (c, delta);
1756
	}
1520
	}
1757
    }
1521
    }
1758
  else
1522
  else if (c->rhs.type == DEREF)
1759
    {
1523
    {
1760
      /* x = *y */
1524
      /* x = *y */
1761
      if (!(get_varinfo (c->lhs.var)->is_special_var))
1525
      if (!(get_varinfo (c->lhs.var)->is_special_var))
1762
	do_sd_constraint (graph, c, delta);
1526
	do_sd_constraint (graph, c, delta);
1763
    }
1527
    }
1528
  else
1529
    {
1530
      bitmap tmp;
1531
      bitmap solution;
1532
      bool flag = false;
1533
      unsigned int t;
1534
1535
      gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1536
      t = find (c->rhs.var);
1537
      solution = get_varinfo (t)->solution;
1538
      t = find (c->lhs.var);
1539
      tmp = get_varinfo (t)->solution;
1540
1541
      flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1542
1543
      if (flag)
1544
	{
1545
	  get_varinfo (t)->solution = tmp;
1546
	  if (!TEST_BIT (changed, t))
1547
	    {
1548
	      SET_BIT (changed, t);
1549
	      changed_count++;
1550
	    }
1551
	}
1552
    }
1764
}
1553
}
1765
1554
1766
/* Initialize and return a new SCC info structure.  */
1555
/* Initialize and return a new SCC info structure.  */
1767
1556
1768
static struct scc_info *
1557
static struct scc_info *
1769
init_scc_info (void)
1558
init_scc_info (size_t size)
1770
{
1559
{
1771
  struct scc_info *si = XNEW (struct scc_info);
1560
  struct scc_info *si = XNEW (struct scc_info);
1772
  size_t size = VEC_length (varinfo_t, varmap);
1561
  size_t i;
1773
1562
1774
  si->current_index = 0;
1563
  si->current_index = 0;
1775
  si->visited = sbitmap_alloc (size);
1564
  si->visited = sbitmap_alloc (size);
1776
  sbitmap_zero (si->visited);
1565
  sbitmap_zero (si->visited);
1777
  si->in_component = sbitmap_alloc (size);
1566
  si->roots = sbitmap_alloc (size);
1778
  sbitmap_ones (si->in_component);
1567
  sbitmap_zero (si->roots);
1779
  si->visited_index = XCNEWVEC (unsigned int, size + 1);
1568
  si->node_mapping = XNEWVEC (unsigned int, size);
1569
  si->dfs = XCNEWVEC (unsigned int, size);
1570
1571
  for (i = 0; i < size; i++)
1572
    si->node_mapping[i] = i;
1573
1780
  si->scc_stack = VEC_alloc (unsigned, heap, 1);
1574
  si->scc_stack = VEC_alloc (unsigned, heap, 1);
1781
  si->unification_queue = VEC_alloc (unsigned, heap, 1);
1782
  return si;
1575
  return si;
1783
}
1576
}
1784
1577
Lines 1786-1992 init_scc_info (void) Link Here
1786
1579
1787
static void
1580
static void
1788
free_scc_info (struct scc_info *si)
1581
free_scc_info (struct scc_info *si)
1789
{  
1582
{
1790
  sbitmap_free (si->visited);
1583
  sbitmap_free (si->visited);
1791
  sbitmap_free (si->in_component);
1584
  sbitmap_free (si->roots);
1792
  free (si->visited_index);
1585
  free (si->node_mapping);
1586
  free (si->dfs);
1793
  VEC_free (unsigned, heap, si->scc_stack);
1587
  VEC_free (unsigned, heap, si->scc_stack);
1794
  VEC_free (unsigned, heap, si->unification_queue);
1588
  free (si);
1795
  free(si); 
1796
}
1589
}
1797
1590
1798
1591
1799
/* Find cycles in GRAPH that occur, using strongly connected components, and
1592
/* Find indirect cycles in GRAPH that occur, using strongly connected
1800
   collapse the cycles into a single representative node.  if UPDATE_CHANGED
1593
   components, and note them in the indirect cycles map.
1801
   is true, then update the changed sbitmap to note those nodes whose
1594
1802
   solutions have changed as a result of collapsing.  */
1595
   This technique comes from Ben Hardekopf and Calvin Lin,
1596
   "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1597
   Lines of Code", submitted to PLDI 2007.  */
1803
1598
1804
static void
1599
static void
1805
find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1600
find_indirect_cycles (constraint_graph_t graph)
1806
{
1601
{
1807
  unsigned int i;
1602
  unsigned int i;
1808
  unsigned int size = VEC_length (varinfo_t, varmap);
1603
  unsigned int size = graph->size;
1809
  struct scc_info *si = init_scc_info ();
1604
  struct scc_info *si = init_scc_info (size);
1810
1605
1811
  for (i = 0; i != size; ++i)
1606
  for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1812
    if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1607
    if (!TEST_BIT (si->visited, i) && find (i) == i)
1813
      scc_visit (graph, si, i);
1608
      scc_visit (graph, si, i);
1814
  
1609
1815
  process_unification_queue (graph, si, update_changed);
1816
  free_scc_info (si);
1610
  free_scc_info (si);
1817
}
1611
}
1818
1612
1819
/* Compute a topological ordering for GRAPH, and store the result in the
1613
/* Compute a topological ordering for GRAPH, and store the result in the
1820
   topo_info structure TI.  */
1614
   topo_info structure TI.  */
1821
1615
1822
static void 
1616
static void
1823
compute_topo_order (constraint_graph_t graph,
1617
compute_topo_order (constraint_graph_t graph,
1824
		    struct topo_info *ti)
1618
		    struct topo_info *ti)
1825
{
1619
{
1826
  unsigned int i;
1620
  unsigned int i;
1827
  unsigned int size = VEC_length (varinfo_t, varmap);
1621
  unsigned int size = VEC_length (varinfo_t, varmap);
1828
  
1622
1829
  for (i = 0; i != size; ++i)
1623
  for (i = 0; i != size; ++i)
1830
    if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1624
    if (!TEST_BIT (ti->visited, i) && find (i) == i)
1831
      topo_visit (graph, ti, i);
1625
      topo_visit (graph, ti, i);
1832
}
1626
}
1833
1627
1834
/* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1835
1836
static bool
1837
bitmap_other_than_zero_bit_set (bitmap b)
1838
{
1839
  unsigned int i;
1840
  bitmap_iterator bi;
1841
1842
  if (bitmap_empty_p (b))
1843
    return false;
1844
  EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1845
    return true;
1846
  return false;
1847
}
1848
1849
/* Perform offline variable substitution.
1628
/* Perform offline variable substitution.
1850
   
1629
1851
   This is a linear time way of identifying variables that must have
1630
   This is a linear time way of identifying variables that must have
1852
   equivalent points-to sets, including those caused by static cycles,
1631
   equivalent points-to sets, including those caused by static cycles,
1853
   and single entry subgraphs, in the constraint graph.
1632
   and single entry subgraphs, in the constraint graph.
1854
1633
1855
   The technique is described in "Off-line variable substitution for
1634
   The technique is described in "Off-line variable substitution for
1856
   scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1635
   scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1857
   in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.  */
1636
   in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.
1637
1638
   There is an optimal way to do this involving hash based value
1639
   numbering, once the technique is published i will implement it
1640
   here.  
1641
1642
   The general method of finding equivalence classes is as follows:
1643
   Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1644
   Add fake nodes (ADDRESS nodes) and edges for a = &b constraints.
1645
   Initialize all non-REF/ADDRESS nodes to be direct nodes
1646
   For each SCC in the predecessor graph:
1647
      for each member (x) of the SCC
1648
         if x is not a direct node:
1649
	   set rootnode(SCC) to be not a direct node
1650
	 collapse node x into rootnode(SCC).
1651
      if rootnode(SCC) is not a direct node:
1652
        label rootnode(SCC) with a new equivalence class
1653
      else:
1654
        if all labeled predecessors of rootnode(SCC) have the same
1655
	label:
1656
	  label rootnode(SCC) with this label
1657
	else:
1658
	  label rootnode(SCC) with a new equivalence class
1659
1660
   All direct nodes with the same equivalence class can be replaced
1661
   with a single representative node.
1662
   All unlabeled nodes (label == 0) are not pointers and all edges
1663
   involving them can be eliminated.
1664
   We perform these optimizations during move_complex_constraints.
1665
*/
1666
1667
static int equivalence_class;
1668
1669
/* Recursive routine to find strongly connected components in GRAPH,
1670
   and label it's nodes with equivalence classes.
1671
   This is used during variable substitution to find cycles involving
1672
   the regular or implicit predecessors, and label them as equivalent.
1673
   The SCC finding algorithm used is the same as that for scc_visit.  */
1858
1674
1859
static void
1675
static void
1676
label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1677
{
1678
  unsigned int i;
1679
  bitmap_iterator bi;
1680
  unsigned int my_dfs;
1681
1682
  gcc_assert (si->node_mapping[n] == n);
1683
  SET_BIT (si->visited, n);
1684
  si->dfs[n] = si->current_index ++;
1685
  my_dfs = si->dfs[n];
1686
1687
  /* Visit all the successors.  */
1688
  EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1689
    {
1690
      unsigned int w = si->node_mapping[i];
1691
1692
      if (TEST_BIT (si->roots, w))
1693
	continue;
1694
1695
      if (!TEST_BIT (si->visited, w))
1696
	label_visit (graph, si, w);
1697
      {
1698
	unsigned int t = si->node_mapping[w];
1699
	unsigned int nnode = si->node_mapping[n];
1700
	gcc_assert (nnode == n);
1701
1702
	if (si->dfs[t] < si->dfs[nnode])
1703
	  si->dfs[n] = si->dfs[t];
1704
      }
1705
    }
1706
1707
  /* Visit all the implicit predecessors.  */
1708
  EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1709
    {
1710
      unsigned int w = si->node_mapping[i];
1711
1712
      if (TEST_BIT (si->roots, w))
1713
	continue;
1714
1715
      if (!TEST_BIT (si->visited, w))
1716
	label_visit (graph, si, w);
1717
      {
1718
	unsigned int t = si->node_mapping[w];
1719
	unsigned int nnode = si->node_mapping[n];
1720
	gcc_assert (nnode == n);
1721
1722
	if (si->dfs[t] < si->dfs[nnode])
1723
	  si->dfs[n] = si->dfs[t];
1724
      }
1725
    }
1726
1727
  /* See if any components have been identified.  */
1728
  if (si->dfs[n] == my_dfs)
1729
    {
1730
      while (VEC_length (unsigned, si->scc_stack) != 0
1731
	     && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1732
	{
1733
	  unsigned int w = VEC_pop (unsigned, si->scc_stack);
1734
	  si->node_mapping[w] = n;
1735
1736
	  if (!TEST_BIT (graph->direct_nodes, w))
1737
	    RESET_BIT (graph->direct_nodes, n);
1738
	}
1739
      SET_BIT (si->roots, n);
1740
1741
      if (!TEST_BIT (graph->direct_nodes, n))
1742
	{
1743
	  graph->label[n] = equivalence_class++;
1744
	}
1745
      else
1746
	{
1747
	  unsigned int size = 0;
1748
	  unsigned int firstlabel = ~0;
1749
1750
	  EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1751
	    {
1752
	      unsigned int j = si->node_mapping[i];
1753
1754
	      if (j == n || graph->label[j] == 0)
1755
		continue;
1756
1757
	      if (firstlabel == (unsigned int)~0)
1758
		{
1759
		  firstlabel = graph->label[j];
1760
		  size++;
1761
		}
1762
	      else if (graph->label[j] != firstlabel)
1763
		size++;
1764
	    }
1765
1766
	  if (size == 0)
1767
	    graph->label[n] = 0;
1768
	  else if (size == 1)
1769
	    graph->label[n] = firstlabel;
1770
	  else
1771
	    graph->label[n] = equivalence_class++;
1772
	}
1773
    }
1774
  else
1775
    VEC_safe_push (unsigned, heap, si->scc_stack, n);
1776
}
1777
1778
/* Perform offline variable substitution, discovering equivalence
1779
   classes, and eliminating non-pointer variables.  */
1780
1781
static struct scc_info *
1860
perform_var_substitution (constraint_graph_t graph)
1782
perform_var_substitution (constraint_graph_t graph)
1861
{
1783
{
1862
  struct topo_info *ti = init_topo_info ();
1784
  unsigned int i;
1863
 
1785
  unsigned int size = graph->size;
1786
  struct scc_info *si = init_scc_info (size);
1787
1864
  bitmap_obstack_initialize (&iteration_obstack);
1788
  bitmap_obstack_initialize (&iteration_obstack);
1865
  /* Compute the topological ordering of the graph, then visit each
1789
  equivalence_class = 0;
1866
     node in topological order.  */
1790
1867
  compute_topo_order (graph, ti);
1791
  /* We only need to visit the non-address nodes for labeling
1868
 
1792
     purposes, as the address nodes will never have any predecessors,
1869
  while (VEC_length (unsigned, ti->topo_order) != 0)
1793
     because &x never appears on the LHS of a constraint.  */
1794
  for (i = 0; i < LAST_REF_NODE; i++)
1795
    if (!TEST_BIT (si->visited, si->node_mapping[i]))
1796
      label_visit (graph, si, si->node_mapping[i]);
1797
1798
  if (dump_file && (dump_flags & TDF_DETAILS))
1799
    for (i = 0; i < FIRST_REF_NODE; i++)
1800
      {
1801
	bool direct_node = TEST_BIT (graph->direct_nodes, i);
1802
	fprintf (dump_file,
1803
		 "Equivalence class for %s node id %d:%s is %d\n",
1804
		 direct_node ? "Direct node" : "Indirect node", i,
1805
		 get_varinfo (i)->name,
1806
		 graph->label[si->node_mapping[i]]);
1807
      }
1808
1809
  /* Quickly eliminate our non-pointer variables.  */
1810
1811
  for (i = 0; i < FIRST_REF_NODE; i++)
1870
    {
1812
    {
1871
      unsigned int i = VEC_pop (unsigned, ti->topo_order);
1813
      unsigned int node = si->node_mapping[i];
1872
      unsigned int pred;
1873
      varinfo_t vi = get_varinfo (i);
1874
      bool okay_to_elim = false;
1875
      unsigned int root = VEC_length (varinfo_t, varmap);
1876
      VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1877
      constraint_edge_t ce = NULL;
1878
      bitmap tmp;
1879
      unsigned int k;
1880
      bitmap_iterator bi;
1881
1814
1882
      /* We can't eliminate things whose address is taken, or which is
1815
      if (graph->label[node] == 0 && TEST_BIT (graph->direct_nodes, node))
1883
	 the target of a dereference.  */
1816
	{
1884
      if (vi->address_taken || vi->indirect_target)
1817
	  if (dump_file && (dump_flags & TDF_DETAILS))
1885
	continue;
1818
	    fprintf (dump_file,
1819
		     "%s is a non-pointer variable, eliminating edges.\n",
1820
		     get_varinfo (node)->name);
1821
	  stats.nonpointer_vars++;
1822
	  clear_edges_for_node (graph, node);
1823
	}
1824
    }
1825
  return si;
1826
}
1886
1827
1887
      /* See if all predecessors of I are ripe for elimination */
1828
/* Free information that was only necessary for variable
1888
      EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi)
1829
   substitution.  */
1889
	  {
1890
	    unsigned int w;
1891
	    w = get_varinfo (k)->node;
1892
1830
1893
	    /* We can't eliminate the node if one of the predecessors is
1831
static void
1894
	       part of a different strongly connected component.  */
1832
free_var_substitution_info (struct scc_info *si)
1895
	    if (!okay_to_elim)
1833
{
1896
	      {
1834
  free_scc_info (si);
1897
		root = w;
1835
  free (graph->label);
1898
		okay_to_elim = true;
1836
  free (graph->eq_rep);
1899
	      }
1837
  sbitmap_free (graph->direct_nodes);
1900
	    else if (w != root)
1838
  bitmap_obstack_release (&iteration_obstack);
1901
	      {
1839
}
1902
		okay_to_elim = false;
1903
		break;
1904
	      }
1905
1840
1906
	    /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1841
/* Return an existing node that is equivalent to NODE, which has
1907
	       then Solution(i) is a subset of Solution (w), where w is a
1842
   equivalence class LABEL, if one exists.  Return NODE otherwise.  */
1908
	       predecessor in the graph.  
1909
	       Corollary: If all predecessors of i have the same
1910
	       points-to set, then i has that same points-to set as
1911
	       those predecessors.  */
1912
	    tmp = BITMAP_ALLOC (NULL);
1913
	    bitmap_and_compl (tmp, get_varinfo (i)->solution,
1914
			      get_varinfo (w)->solution);
1915
	    if (!bitmap_empty_p (tmp))
1916
	      {
1917
		okay_to_elim = false;
1918
		BITMAP_FREE (tmp);
1919
		break;
1920
	      }
1921
	    BITMAP_FREE (tmp);
1922
	  }
1923
1843
1924
      if (okay_to_elim)
1844
static unsigned int
1925
	for (pred = 0; 
1845
find_equivalent_node (constraint_graph_t graph,
1926
	     VEC_iterate (constraint_edge_t, predvec, pred, ce); 
1846
		      unsigned int node, unsigned int label)
1927
	     pred++)
1847
{
1928
	  {
1848
  /* If the address version of this variable is unused, we can
1929
	    bitmap weight;
1849
     substitute it for anything else with the same label.
1930
	    unsigned int w;
1850
     Otherwise, we know the pointers are equivalent, but not the
1931
	    weight = *(get_graph_weights (graph, i, ce->dest));
1851
     locations.  */
1932
1933
	    /* We can't eliminate variables that have nonzero weighted
1934
	       edges between them.  */
1935
	    if (weight && bitmap_other_than_zero_bit_set (weight))
1936
	      {
1937
		okay_to_elim = false;
1938
		break;
1939
	      }
1940
	    w = get_varinfo (ce->dest)->node;
1941
1852
1942
	    /* We can't eliminate the node if one of the predecessors is
1853
  if (graph->label[FIRST_ADDR_NODE + node] == 0)
1943
	       part of a different strongly connected component.  */
1854
    {
1944
	    if (!okay_to_elim)
1855
      gcc_assert (label < graph->size);
1945
	      {
1946
		root = w;
1947
		okay_to_elim = true;
1948
	      }
1949
	    else if (w != root)
1950
	      {
1951
		okay_to_elim = false;
1952
		break;
1953
	      }
1954
1856
1955
	    /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1857
      if (graph->eq_rep[label] != -1)
1956
	       then Solution(i) is a subset of Solution (w), where w is a
1858
	{
1957
	       predecessor in the graph.  
1859
	  /* Unify the two variables since we know they are equivalent.  */
1958
	       Corollary: If all predecessors of i have the same
1860
	  if (unite (graph->eq_rep[label], node))
1959
	       points-to set, then i has that same points-to set as
1861
	    unify_nodes (graph, graph->eq_rep[label], node, false);
1960
	       those predecessors.  */
1862
	  return graph->eq_rep[label];
1961
	    tmp = BITMAP_ALLOC (NULL);
1863
	}
1962
	    bitmap_and_compl (tmp, get_varinfo (i)->solution,
1864
      else
1963
			      get_varinfo (w)->solution);
1865
	{
1964
	    if (!bitmap_empty_p (tmp))
1866
	  graph->eq_rep[label] = node;
1965
	      {
1867
	}
1966
		okay_to_elim = false;
1868
    }
1967
		BITMAP_FREE (tmp);
1869
  return node;
1968
		break;
1870
}
1969
	      }
1871
1970
	    BITMAP_FREE (tmp);
1872
/* Move complex constraints to the appropriate nodes, and collapse
1971
	  }
1873
   variables we've discovered are equivalent during variable
1874
   substitution.  SI is the SCC_INFO that is the result of
1875
   perform_variable_substitution.  */
1876
1877
static void
1878
move_complex_constraints (constraint_graph_t graph,
1879
			  struct scc_info *si)
1880
{
1881
  int i;
1882
  unsigned int j;
1883
  constraint_t c;
1884
1885
  for (j = 0; j < graph->size; j++)
1886
    gcc_assert (find (j) == j);
1887
1888
  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1889
    {
1890
      struct constraint_expr lhs = c->lhs;
1891
      struct constraint_expr rhs = c->rhs;
1892
      unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
1893
      unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
1894
      unsigned int lhsnode, rhsnode;
1895
      unsigned int lhslabel, rhslabel;
1896
1897
      lhsnode = si->node_mapping[lhsvar];
1898
      rhsnode = si->node_mapping[rhsvar];
1899
      lhslabel = graph->label[lhsnode];
1900
      rhslabel = graph->label[rhsnode];
1901
1902
      /* See if it is really a non-pointer variable, and if so, ignore
1903
	 the constraint.  */
1904
      if (lhslabel == 0)
1905
	{
1906
	  if (!TEST_BIT (graph->direct_nodes, lhsnode))
1907
	    lhslabel = graph->label[lhsnode] = equivalence_class++;
1908
	  else
1909
	    {
1910
	      if (dump_file && (dump_flags & TDF_DETAILS))
1911
		{
1912
1913
		  fprintf (dump_file, "%s is a non-pointer variable,"
1914
			   "ignoring constraint:",
1915
			   get_varinfo (lhs.var)->name);
1916
		  dump_constraint (dump_file, c);
1917
		}
1918
	      VEC_replace (constraint_t, constraints, i, NULL);
1919
	      continue;
1920
	    }
1921
	}
1922
1923
      if (rhslabel == 0)
1924
	{
1925
	  if (!TEST_BIT (graph->direct_nodes, rhsnode))
1926
	    rhslabel = graph->label[rhsnode] = equivalence_class++;
1927
	  else
1928
	    {
1929
	      if (dump_file && (dump_flags & TDF_DETAILS))
1930
		{
1931
1932
		  fprintf (dump_file, "%s is a non-pointer variable,"
1933
			   "ignoring constraint:",
1934
			   get_varinfo (rhs.var)->name);
1935
		  dump_constraint (dump_file, c);
1936
		}
1937
	      VEC_replace (constraint_t, constraints, i, NULL);
1938
	      continue;
1939
	    }
1940
	}
1941
1942
      lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
1943
      rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
1944
      c->lhs.var = lhsvar;
1945
      c->rhs.var = rhsvar;
1946
1947
      if (lhs.type == DEREF)
1948
	{
1949
	  if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1950
	    insert_into_complex (graph, lhsvar, c);
1951
	}
1952
      else if (rhs.type == DEREF)
1953
	{
1954
	  if (!(get_varinfo (lhsvar)->is_special_var))
1955
	    insert_into_complex (graph, rhsvar, c);
1956
	}
1957
      else if (rhs.type != ADDRESSOF && lhsvar > anything_id
1958
	       && (lhs.offset != 0 || rhs.offset != 0))
1959
	{
1960
	  insert_into_complex (graph, rhsvar, c);
1961
	}
1962
1963
    }
1964
}
1965
1966
/* Eliminate indirect cycles involving NODE.  Return true if NODE was
1967
   part of an SCC, false otherwise.  */
1968
1969
static bool
1970
eliminate_indirect_cycles (unsigned int node)
1971
{
1972
  if (graph->indirect_cycles[node] != -1
1973
      && !bitmap_empty_p (get_varinfo (node)->solution))
1974
    {
1975
      unsigned int i;
1976
      VEC(unsigned,heap) *queue = NULL;
1977
      int queuepos;
1978
      unsigned int to = find (graph->indirect_cycles[node]);
1979
      bitmap_iterator bi;
1972
1980
1973
      /* See if the root is different than the original node. 
1981
      /* We can't touch the solution set and call unify_nodes
1974
	 If so, we've found an equivalence.  */
1982
	 at the same time, because unify_nodes is going to do
1975
      if (root != get_varinfo (i)->node && okay_to_elim)
1983
	 bitmap unions into it. */
1976
	{
1984
1977
	  /* Found an equivalence */
1985
      EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
1978
	  get_varinfo (i)->node = root;
1986
	{
1979
	  collapse_nodes (graph, root, i);
1987
	  if (find (i) == i && i != to)
1980
	  if (dump_file && (dump_flags & TDF_DETAILS))
1988
	    {
1981
	    fprintf (dump_file, "Collapsing %s into %s\n",
1989
	      if (unite (to, i))
1982
		     get_varinfo (i)->name,
1990
		VEC_safe_push (unsigned, heap, queue, i);
1983
		     get_varinfo (root)->name);
1991
	    }
1984
	  stats.collapsed_vars++;
1985
	}
1992
	}
1986
    }
1987
1993
1988
  bitmap_obstack_release (&iteration_obstack);
1994
      for (queuepos = 0;
1989
  free_topo_info (ti);
1995
	   VEC_iterate (unsigned, queue, queuepos, i);
1996
	   queuepos++)
1997
	{
1998
	  unify_nodes (graph, to, i, true);
1999
	}
2000
      VEC_free (unsigned, heap, queue);
2001
      return true;
2002
    }
2003
  return false;
1990
}
2004
}
1991
2005
1992
/* Solve the constraint graph GRAPH using our worklist solver.
2006
/* Solve the constraint graph GRAPH using our worklist solver.
Lines 2001-2017 solve_graph (constraint_graph_t graph) Link Here
2001
{
2015
{
2002
  unsigned int size = VEC_length (varinfo_t, varmap);
2016
  unsigned int size = VEC_length (varinfo_t, varmap);
2003
  unsigned int i;
2017
  unsigned int i;
2018
  bitmap pts;
2004
2019
2005
  changed_count = size;
2020
  changed_count = 0;
2006
  changed = sbitmap_alloc (size);
2021
  changed = sbitmap_alloc (size);
2007
  sbitmap_ones (changed);
2022
  sbitmap_zero (changed);
2008
  
2023
2009
  /* The already collapsed/unreachable nodes will never change, so we
2024
  /* Mark all initial non-collapsed nodes as changed.  */
2010
     need to  account for them in changed_count.  */
2011
  for (i = 0; i < size; i++)
2025
  for (i = 0; i < size; i++)
2012
    if (get_varinfo (i)->node != i)
2026
    {
2013
      changed_count--;
2027
      varinfo_t ivi = get_varinfo (i);
2014
  
2028
      if (find (i) == i && !bitmap_empty_p (ivi->solution)
2029
	  && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2030
	      || VEC_length (constraint_t, graph->complex[i]) > 0))
2031
	{
2032
	  SET_BIT (changed, i);
2033
	  changed_count++;
2034
	}
2035
    }
2036
2037
  /* Allocate a bitmap to be used to store the changed bits.  */
2038
  pts = BITMAP_ALLOC (&pta_obstack);
2039
2015
  while (changed_count > 0)
2040
  while (changed_count > 0)
2016
    {
2041
    {
2017
      unsigned int i;
2042
      unsigned int i;
Lines 2019-2042 solve_graph (constraint_graph_t graph) Link Here
2019
      stats.iterations++;
2044
      stats.iterations++;
2020
2045
2021
      bitmap_obstack_initialize (&iteration_obstack);
2046
      bitmap_obstack_initialize (&iteration_obstack);
2022
      
2023
      if (edge_added)
2024
	{
2025
	  /* We already did cycle elimination once, when we did
2026
	     variable substitution, so we don't need it again for the
2027
	     first iteration.  */
2028
	  if (stats.iterations > 1)
2029
	    find_and_collapse_graph_cycles (graph, true);
2030
2031
	  edge_added = false;
2032
	}
2033
2047
2034
      compute_topo_order (graph, ti);
2048
      compute_topo_order (graph, ti);
2035
2049
2036
      while (VEC_length (unsigned, ti->topo_order) != 0)
2050
      while (VEC_length (unsigned, ti->topo_order) != 0)
2037
	{
2051
	{
2052
2038
	  i = VEC_pop (unsigned, ti->topo_order);
2053
	  i = VEC_pop (unsigned, ti->topo_order);
2039
	  gcc_assert (get_varinfo (i)->node == i);
2054
2055
	  /* If this variable is not a representative, skip it.  */
2056
	  if (find (i) != i)
2057
	    continue;
2058
2059
	  /* In certain indirect cycle cases, we may merge this
2060
	     variable to another.  */
2061
	  if (eliminate_indirect_cycles (i) && find (i) != i)
2062
	    continue;
2040
2063
2041
	  /* If the node has changed, we need to process the
2064
	  /* If the node has changed, we need to process the
2042
	     complex constraints and outgoing edges again.  */
2065
	     complex constraints and outgoing edges again.  */
Lines 2044-2059 solve_graph (constraint_graph_t graph) Link Here
2044
	    {
2067
	    {
2045
	      unsigned int j;
2068
	      unsigned int j;
2046
	      constraint_t c;
2069
	      constraint_t c;
2047
	      constraint_edge_t e = NULL;
2048
	      bitmap solution;
2070
	      bitmap solution;
2049
	      bitmap_iterator bi;
2071
	      VEC(constraint_t,heap) *complex = graph->complex[i];
2050
	      VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
2051
	      VEC(constraint_edge_t,heap) *succs;
2052
	      bool solution_empty;
2072
	      bool solution_empty;
2053
2073
2054
	      RESET_BIT (changed, i);
2074
	      RESET_BIT (changed, i);
2055
	      changed_count--;
2075
	      changed_count--;
2056
2076
2077
	      /* Compute the changed set of solution bits.  */
2078
	      bitmap_and_compl (pts, get_varinfo (i)->solution,
2079
				get_varinfo (i)->oldsolution);
2080
2081
	      if (bitmap_empty_p (pts))
2082
		continue;
2083
2084
	      bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2085
2057
	      solution = get_varinfo (i)->solution;
2086
	      solution = get_varinfo (i)->solution;
2058
	      solution_empty = bitmap_empty_p (solution);
2087
	      solution_empty = bitmap_empty_p (solution);
2059
2088
Lines 2065-2116 solve_graph (constraint_graph_t graph) Link Here
2065
		     is a constraint where the lhs side is receiving
2094
		     is a constraint where the lhs side is receiving
2066
		     some set from elsewhere.  */
2095
		     some set from elsewhere.  */
2067
		  if (!solution_empty || c->lhs.type != DEREF)
2096
		  if (!solution_empty || c->lhs.type != DEREF)
2068
		    do_complex_constraint (graph, c, solution);
2097
		    do_complex_constraint (graph, c, pts);
2069
		}
2098
		}
2070
2099
2071
	      solution_empty = bitmap_empty_p (solution);
2100
	      solution_empty = bitmap_empty_p (solution);
2072
2101
2073
	      if (!solution_empty)
2102
	      if (!solution_empty)
2074
		{
2103
		{
2104
		  bitmap_iterator bi;
2105
2075
		  /* Propagate solution to all successors.  */
2106
		  /* Propagate solution to all successors.  */
2076
		  succs = graph->succs[i];
2107
		  EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2077
		  
2078
		  EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i], 
2079
						0, j, bi)
2108
						0, j, bi)
2080
		    {
2109
		    {
2081
		      bitmap tmp = get_varinfo (j)->solution;
2110
		      bitmap tmp;
2082
		      bool flag = false;
2111
		      bool flag;
2083
		  
2112
2084
		      flag = set_union_with_increment (tmp, solution, 0);
2113
		      unsigned int to = find (j);
2085
		  
2114
		      tmp = get_varinfo (to)->solution;
2086
		      if (flag)
2115
		      flag = false;
2087
			{
2116
2088
			  get_varinfo (j)->solution = tmp;
2117
		      /* Don't try to propagate to ourselves.  */
2089
			  if (!TEST_BIT (changed, j))
2118
		      if (to == i)
2090
			    {
2119
			continue;
2091
			      SET_BIT (changed, j);
2120
2092
			      changed_count++;
2121
		      flag = set_union_with_increment (tmp, pts, 0);
2093
			    }
2094
			}
2095
		    }
2096
		  for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
2097
		    {
2098
		      bitmap tmp = get_varinfo (e->dest)->solution;
2099
		      bool flag = false;
2100
		      unsigned int k;
2101
		      bitmap weights = e->weights;
2102
		      bitmap_iterator bi;
2103
2104
		      gcc_assert (weights && !bitmap_empty_p (weights));
2105
		      EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
2106
			flag |= set_union_with_increment (tmp, solution, k);
2107
2122
2108
		      if (flag)
2123
		      if (flag)
2109
			{
2124
			{
2110
			  get_varinfo (e->dest)->solution = tmp;
2125
			  get_varinfo (to)->solution = tmp;
2111
			  if (!TEST_BIT (changed, e->dest))
2126
			  if (!TEST_BIT (changed, to))
2112
			    {
2127
			    {
2113
			      SET_BIT (changed, e->dest);
2128
			      SET_BIT (changed, to);
2114
			      changed_count++;
2129
			      changed_count++;
2115
			    }
2130
			    }
2116
			}
2131
			}
Lines 2122-2195 solve_graph (constraint_graph_t graph) Link Here
2122
      bitmap_obstack_release (&iteration_obstack);
2137
      bitmap_obstack_release (&iteration_obstack);
2123
    }
2138
    }
2124
2139
2140
  BITMAP_FREE (pts);
2125
  sbitmap_free (changed);
2141
  sbitmap_free (changed);
2142
  bitmap_obstack_release (&oldpta_obstack);
2126
}
2143
}
2127
2144
2145
/* Map from trees to variable infos.  */
2146
static struct pointer_map_t *vi_for_tree;
2128
2147
2129
/* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2130
2131
/* Map from trees to variable ids.  */    
2132
static htab_t id_for_tree;
2133
2134
typedef struct tree_id
2135
{
2136
  tree t;
2137
  unsigned int id;
2138
} *tree_id_t;
2139
2140
/* Hash a tree id structure.  */
2141
2142
static hashval_t 
2143
tree_id_hash (const void *p)
2144
{
2145
  const tree_id_t ta = (tree_id_t) p;
2146
  return htab_hash_pointer (ta->t);
2147
}
2148
2149
/* Return true if the tree in P1 and the tree in P2 are the same.  */
2150
2151
static int
2152
tree_id_eq (const void *p1, const void *p2)
2153
{
2154
  const tree_id_t ta1 = (tree_id_t) p1;
2155
  const tree_id_t ta2 = (tree_id_t) p2;
2156
  return ta1->t == ta2->t;
2157
}
2158
2148
2159
/* Insert ID as the variable id for tree T in the hashtable.  */
2149
/* Insert ID as the variable id for tree T in the vi_for_tree map.  */
2160
2150
2161
static void 
2151
static void
2162
insert_id_for_tree (tree t, int id)
2152
insert_vi_for_tree (tree t, varinfo_t vi)
2163
{
2153
{
2164
  void **slot;
2154
  void **slot = pointer_map_insert (vi_for_tree, t);
2165
  struct tree_id finder;
2155
  gcc_assert (vi);
2166
  tree_id_t new_pair;
2167
  
2168
  finder.t = t;
2169
  slot = htab_find_slot (id_for_tree, &finder, INSERT);
2170
  gcc_assert (*slot == NULL);
2156
  gcc_assert (*slot == NULL);
2171
  new_pair = XNEW (struct tree_id);
2157
  *slot = vi;
2172
  new_pair->t = t;
2173
  new_pair->id = id;
2174
  *slot = (void *)new_pair;
2175
}
2158
}
2176
2159
2177
/* Find the variable id for tree T in ID_FOR_TREE.  If T does not
2160
/* Find the variable info for tree T in VI_FOR_TREE.  If T does not
2178
   exist in the hash table, return false, otherwise, return true and
2161
   exist in the map, return NULL, otherwise, return the varinfo we found.  */
2179
   set *ID to the id we found.  */
2180
2162
2181
static bool
2163
static varinfo_t
2182
lookup_id_for_tree (tree t, unsigned int *id)
2164
lookup_vi_for_tree (tree t)
2183
{
2165
{
2184
  tree_id_t pair;
2166
  void **slot = pointer_map_contains (vi_for_tree, t);
2185
  struct tree_id finder;
2167
  if (slot == NULL)
2168
    return NULL;
2186
2169
2187
  finder.t = t;
2170
  return (varinfo_t) *slot;
2188
  pair = htab_find (id_for_tree,  &finder);
2189
  if (pair == NULL)
2190
    return false;
2191
  *id = pair->id;
2192
  return true;
2193
}
2171
}
2194
2172
2195
/* Return a printable name for DECL  */
2173
/* Return a printable name for DECL  */
Lines 2210-2216 alias_get_name (tree decl) Link Here
2210
2188
2211
  if (TREE_CODE (decl) == SSA_NAME)
2189
  if (TREE_CODE (decl) == SSA_NAME)
2212
    {
2190
    {
2213
      num_printed = asprintf (&temp, "%s_%u", 
2191
      num_printed = asprintf (&temp, "%s_%u",
2214
			      alias_get_name (SSA_NAME_VAR (decl)),
2192
			      alias_get_name (SSA_NAME_VAR (decl)),
2215
			      SSA_NAME_VERSION (decl));
2193
			      SSA_NAME_VERSION (decl));
2216
    }
2194
    }
Lines 2226-2246 alias_get_name (tree decl) Link Here
2226
  return res;
2204
  return res;
2227
}
2205
}
2228
2206
2229
/* Find the variable id for tree T in the hashtable.
2207
/* Find the variable id for tree T in the map.
2230
   If T doesn't exist in the hash table, create an entry for it.  */
2208
   If T doesn't exist in the map, create an entry for it and return it.  */
2231
2209
2232
static unsigned int
2210
static varinfo_t
2233
get_id_for_tree (tree t)
2211
get_vi_for_tree (tree t)
2234
{
2212
{
2235
  tree_id_t pair;
2213
  void **slot = pointer_map_contains (vi_for_tree, t);
2236
  struct tree_id finder;
2214
  if (slot == NULL)
2215
    return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2237
2216
2238
  finder.t = t;
2217
  return (varinfo_t) *slot;
2239
  pair = htab_find (id_for_tree,  &finder);
2240
  if (pair == NULL)
2241
    return create_variable_info_for (t, alias_get_name (t));
2242
  
2243
  return pair->id;
2244
}
2218
}
2245
2219
2246
/* Get a constraint expression from an SSA_VAR_P node.  */
2220
/* Get a constraint expression from an SSA_VAR_P node.  */
Lines 2254-2267 get_constraint_exp_from_ssa_var (tree t) Link Here
2254
2228
2255
  /* For parameters, get at the points-to set for the actual parm
2229
  /* For parameters, get at the points-to set for the actual parm
2256
     decl.  */
2230
     decl.  */
2257
  if (TREE_CODE (t) == SSA_NAME 
2231
  if (TREE_CODE (t) == SSA_NAME
2258
      && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL 
2232
      && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2259
      && default_def (SSA_NAME_VAR (t)) == t)
2233
      && default_def (SSA_NAME_VAR (t)) == t)
2260
    return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2234
    return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2261
2235
2262
  cexpr.type = SCALAR;
2236
  cexpr.type = SCALAR;
2263
  
2237
2264
  cexpr.var = get_id_for_tree (t);
2238
  cexpr.var = get_vi_for_tree (t)->id;
2265
  /* If we determine the result is "anything", and we know this is readonly,
2239
  /* If we determine the result is "anything", and we know this is readonly,
2266
     say it points to readonly memory instead.  */
2240
     say it points to readonly memory instead.  */
2267
  if (cexpr.var == anything_id && TREE_READONLY (t))
2241
  if (cexpr.var == anything_id && TREE_READONLY (t))
Lines 2269-2275 get_constraint_exp_from_ssa_var (tree t) Link Here
2269
      cexpr.type = ADDRESSOF;
2243
      cexpr.type = ADDRESSOF;
2270
      cexpr.var = readonly_id;
2244
      cexpr.var = readonly_id;
2271
    }
2245
    }
2272
    
2246
2273
  cexpr.offset = 0;
2247
  cexpr.offset = 0;
2274
  return cexpr;
2248
  return cexpr;
2275
}
2249
}
Lines 2282-2288 process_constraint (constraint_t t) Link Here
2282
{
2256
{
2283
  struct constraint_expr rhs = t->rhs;
2257
  struct constraint_expr rhs = t->rhs;
2284
  struct constraint_expr lhs = t->lhs;
2258
  struct constraint_expr lhs = t->lhs;
2285
  
2259
2286
  gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2260
  gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2287
  gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2261
  gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2288
2262
Lines 2290-2296 process_constraint (constraint_t t) Link Here
2290
    get_varinfo (lhs.var)->directly_dereferenced = true;
2264
    get_varinfo (lhs.var)->directly_dereferenced = true;
2291
  if (rhs.type == DEREF)
2265
  if (rhs.type == DEREF)
2292
    get_varinfo (rhs.var)->directly_dereferenced = true;
2266
    get_varinfo (rhs.var)->directly_dereferenced = true;
2293
  
2267
2268
  if (!use_field_sensitive)
2269
    {
2270
      t->rhs.offset = 0;
2271
      t->lhs.offset = 0;
2272
    }
2273
2294
  /* ANYTHING == ANYTHING is pointless.  */
2274
  /* ANYTHING == ANYTHING is pointless.  */
2295
  if (lhs.var == anything_id && rhs.var == anything_id)
2275
  if (lhs.var == anything_id && rhs.var == anything_id)
2296
    return;
2276
    return;
Lines 2302-2308 process_constraint (constraint_t t) Link Here
2302
      t->lhs = t->rhs;
2282
      t->lhs = t->rhs;
2303
      t->rhs = rhs;
2283
      t->rhs = rhs;
2304
      process_constraint (t);
2284
      process_constraint (t);
2305
    }   
2285
    }
2306
  /* This can happen in our IR with things like n->a = *p */
2286
  /* This can happen in our IR with things like n->a = *p */
2307
  else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2287
  else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2308
    {
2288
    {
Lines 2312-2344 process_constraint (constraint_t t) Link Here
2312
      tree pointedtotype = TREE_TYPE (pointertype);
2292
      tree pointedtotype = TREE_TYPE (pointertype);
2313
      tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2293
      tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2314
      struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2294
      struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2315
      
2295
2316
      /* If this is an aggregate of known size, we should have passed
2296
      /* If this is an aggregate of known size, we should have passed
2317
	 this off to do_structure_copy, and it should have broken it
2297
	 this off to do_structure_copy, and it should have broken it
2318
	 up.  */
2298
	 up.  */
2319
      gcc_assert (!AGGREGATE_TYPE_P (pointedtotype) 
2299
      gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2320
		  || get_varinfo (rhs.var)->is_unknown_size_var);
2300
		  || get_varinfo (rhs.var)->is_unknown_size_var);
2321
      
2301
2322
      process_constraint (new_constraint (tmplhs, rhs));
2302
      process_constraint (new_constraint (tmplhs, rhs));
2323
      process_constraint (new_constraint (lhs, tmplhs));
2303
      process_constraint (new_constraint (lhs, tmplhs));
2324
    }
2304
    }
2325
  else if (rhs.type == ADDRESSOF)
2326
    {
2327
      varinfo_t vi;
2328
      gcc_assert (rhs.offset == 0);
2329
      
2330
      /* No need to mark address taken simply because of escaped vars
2331
	 constraints.  */
2332
      if (lhs.var != escaped_vars_id)
2333
	for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
2334
	  vi->address_taken = true;
2335
2336
      VEC_safe_push (constraint_t, heap, constraints, t);
2337
    }
2338
  else
2305
  else
2339
    {
2306
    {
2340
      if (lhs.type != DEREF && rhs.type == DEREF)
2307
      gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2341
	get_varinfo (lhs.var)->indirect_target = true;
2342
      VEC_safe_push (constraint_t, heap, constraints, t);
2308
      VEC_safe_push (constraint_t, heap, constraints, t);
2343
    }
2309
    }
2344
}
2310
}
Lines 2350-2359 static bool Link Here
2350
could_have_pointers (tree t)
2316
could_have_pointers (tree t)
2351
{
2317
{
2352
  tree type = TREE_TYPE (t);
2318
  tree type = TREE_TYPE (t);
2353
  
2319
2354
  if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
2320
  if (POINTER_TYPE_P (type)
2321
      || AGGREGATE_TYPE_P (type)
2355
      || TREE_CODE (type) == COMPLEX_TYPE)
2322
      || TREE_CODE (type) == COMPLEX_TYPE)
2356
    return true;
2323
    return true;
2324
2357
  return false;
2325
  return false;
2358
}
2326
}
2359
2327
Lines 2367-2375 bitpos_of_field (const tree fdecl) Link Here
2367
  if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2335
  if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2368
      || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2336
      || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2369
    return -1;
2337
    return -1;
2370
  
2338
2371
  return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) 
2339
  return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2372
         + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2340
	 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2373
}
2341
}
2374
2342
2375
2343
Lines 2388-2394 offset_overlaps_with_access (const unsig Link Here
2388
    return true;
2356
    return true;
2389
  if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2357
  if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2390
    return true;
2358
    return true;
2391
  
2359
2392
  return false;
2360
  return false;
2393
}
2361
}
2394
2362
Lines 2411-2430 get_constraint_for_component_ref (tree t Link Here
2411
  while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2379
  while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2412
    forzero = TREE_OPERAND (forzero, 0);
2380
    forzero = TREE_OPERAND (forzero, 0);
2413
2381
2414
  if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) 
2382
  if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2415
    {
2383
    {
2416
      struct constraint_expr temp;
2384
      struct constraint_expr temp;
2417
      
2385
2418
      temp.offset = 0;
2386
      temp.offset = 0;
2419
      temp.var = integer_id;
2387
      temp.var = integer_id;
2420
      temp.type = SCALAR;
2388
      temp.type = SCALAR;
2421
      VEC_safe_push (ce_s, heap, *results, &temp);
2389
      VEC_safe_push (ce_s, heap, *results, &temp);
2422
      return;
2390
      return;
2423
    }
2391
    }
2424
 
2392
2425
  t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2393
  t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2426
2394
2427
  /* String constants's are readonly, so there is nothing to really do
2395
  /* String constants are readonly, so there is nothing to really do
2428
     here.  */
2396
     here.  */
2429
  if (TREE_CODE (t) == STRING_CST)
2397
  if (TREE_CODE (t) == STRING_CST)
2430
    return;
2398
    return;
Lines 2438-2458 get_constraint_for_component_ref (tree t Link Here
2438
  /* This can also happen due to weird offsetof type macros.  */
2406
  /* This can also happen due to weird offsetof type macros.  */
2439
  if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2407
  if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2440
    result->type = SCALAR;
2408
    result->type = SCALAR;
2441
 
2409
2442
  if (result->type == SCALAR)
2410
  if (result->type == SCALAR)
2443
    {
2411
    {
2444
      /* In languages like C, you can access one past the end of an
2412
      /* In languages like C, you can access one past the end of an
2445
	 array.  You aren't allowed to dereference it, so we can
2413
	 array.  You aren't allowed to dereference it, so we can
2446
	 ignore this constraint. When we handle pointer subtraction,
2414
	 ignore this constraint. When we handle pointer subtraction,
2447
	 we may have to do something cute here.  */
2415
	 we may have to do something cute here.  */
2448
      
2416
2449
      if (result->offset < get_varinfo (result->var)->fullsize
2417
      if (result->offset < get_varinfo (result->var)->fullsize
2450
	  && bitmaxsize != 0)
2418
	  && bitmaxsize != 0)
2451
	{
2419
	{
2452
	  /* It's also not true that the constraint will actually start at the
2420
	  /* It's also not true that the constraint will actually start at the
2453
	     right offset, it may start in some padding.  We only care about
2421
	     right offset, it may start in some padding.  We only care about
2454
	     setting the constraint to the first actual field it touches, so
2422
	     setting the constraint to the first actual field it touches, so
2455
	     walk to find it.  */ 
2423
	     walk to find it.  */
2456
	  varinfo_t curr;
2424
	  varinfo_t curr;
2457
	  for (curr = get_varinfo (result->var); curr; curr = curr->next)
2425
	  for (curr = get_varinfo (result->var); curr; curr = curr->next)
2458
	    {
2426
	    {
Lines 2495-2500 do_deref (VEC (ce_s, heap) **constraints Link Here
2495
{
2463
{
2496
  struct constraint_expr *c;
2464
  struct constraint_expr *c;
2497
  unsigned int i = 0;
2465
  unsigned int i = 0;
2466
2498
  for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2467
  for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2499
    {
2468
    {
2500
      if (c->type == SCALAR)
2469
      if (c->type == SCALAR)
Lines 2576-2581 get_constraint_for (tree t, VEC (ce_s, h Link Here
2576
	      tree pttype = TREE_TYPE (TREE_TYPE (t));
2545
	      tree pttype = TREE_TYPE (TREE_TYPE (t));
2577
2546
2578
	      get_constraint_for (exp, results);
2547
	      get_constraint_for (exp, results);
2548
2579
	      /* Make sure we capture constraints to all elements
2549
	      /* Make sure we capture constraints to all elements
2580
		 of an array.  */
2550
		 of an array.  */
2581
	      if ((handled_component_p (exp)
2551
	      if ((handled_component_p (exp)
Lines 2588-2594 get_constraint_for (tree t, VEC (ce_s, h Link Here
2588
2558
2589
		  if (VEC_length (ce_s, *results) == 0)
2559
		  if (VEC_length (ce_s, *results) == 0)
2590
		    return;
2560
		    return;
2591
		  
2561
2592
		  gcc_assert (VEC_length (ce_s, *results) == 1);
2562
		  gcc_assert (VEC_length (ce_s, *results) == 1);
2593
		  origrhs = VEC_last (ce_s, *results);
2563
		  origrhs = VEC_last (ce_s, *results);
2594
		  tmp = *origrhs;
2564
		  tmp = *origrhs;
Lines 2619-2630 get_constraint_for (tree t, VEC (ce_s, h Link Here
2619
		      VEC_safe_push (ce_s, heap, *results, &tmp);
2589
		      VEC_safe_push (ce_s, heap, *results, &tmp);
2620
		    }
2590
		    }
2621
		}
2591
		}
2622
	      
2592
2623
	      for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2593
	      for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2624
		{
2594
		{
2625
		  if (c->type == DEREF)
2595
		  if (c->type == DEREF)
2626
		    c->type = SCALAR;
2596
		    c->type = SCALAR;
2627
		  else 
2597
		  else
2628
		    c->type = ADDRESSOF;
2598
		    c->type = ADDRESSOF;
2629
		}
2599
		}
2630
	      return;
2600
	      return;
Lines 2638-2646 get_constraint_for (tree t, VEC (ce_s, h Link Here
2638
	      {
2608
	      {
2639
		varinfo_t vi;
2609
		varinfo_t vi;
2640
		tree heapvar = heapvar_lookup (t);
2610
		tree heapvar = heapvar_lookup (t);
2641
		
2611
2642
		if (heapvar == NULL)
2612
		if (heapvar == NULL)
2643
		  {		    
2613
		  {
2644
		    heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2614
		    heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2645
		    DECL_EXTERNAL (heapvar) = 1;
2615
		    DECL_EXTERNAL (heapvar) = 1;
2646
		    if (referenced_vars)
2616
		    if (referenced_vars)
Lines 2650-2656 get_constraint_for (tree t, VEC (ce_s, h Link Here
2650
2620
2651
		temp.var = create_variable_info_for (heapvar,
2621
		temp.var = create_variable_info_for (heapvar,
2652
						     alias_get_name (heapvar));
2622
						     alias_get_name (heapvar));
2653
		
2623
2654
		vi = get_varinfo (temp.var);
2624
		vi = get_varinfo (temp.var);
2655
		vi->is_artificial_var = 1;
2625
		vi->is_artificial_var = 1;
2656
		vi->is_heap_var = 1;
2626
		vi->is_heap_var = 1;
Lines 2712-2718 get_constraint_for (tree t, VEC (ce_s, h Link Here
2712
	  case NON_LVALUE_EXPR:
2682
	  case NON_LVALUE_EXPR:
2713
	    {
2683
	    {
2714
	      tree op = TREE_OPERAND (t, 0);
2684
	      tree op = TREE_OPERAND (t, 0);
2715
	      
2685
2716
	      /* Cast from non-pointer to pointers are bad news for us.
2686
	      /* Cast from non-pointer to pointers are bad news for us.
2717
		 Anything else, we see through */
2687
		 Anything else, we see through */
2718
	      if (!(POINTER_TYPE_P (TREE_TYPE (t))
2688
	      if (!(POINTER_TYPE_P (TREE_TYPE (t))
Lines 2738-2744 get_constraint_for (tree t, VEC (ce_s, h Link Here
2738
      {
2708
      {
2739
	switch (TREE_CODE (t))
2709
	switch (TREE_CODE (t))
2740
	  {
2710
	  {
2741
	  case PHI_NODE:	   
2711
	  case PHI_NODE:
2742
	    {
2712
	    {
2743
	      get_constraint_for (PHI_RESULT (t), results);
2713
	      get_constraint_for (PHI_RESULT (t), results);
2744
	      return;
2714
	      return;
Lines 2782-2789 get_constraint_for (tree t, VEC (ce_s, h Link Here
2782
2752
2783
2753
2784
/* Handle the structure copy case where we have a simple structure copy
2754
/* Handle the structure copy case where we have a simple structure copy
2785
   between LHS and RHS that is of SIZE (in bits) 
2755
   between LHS and RHS that is of SIZE (in bits)
2786
  
2756
2787
   For each field of the lhs variable (lhsfield)
2757
   For each field of the lhs variable (lhsfield)
2788
     For each field of the rhs variable at lhsfield.offset (rhsfield)
2758
     For each field of the rhs variable at lhsfield.offset (rhsfield)
2789
       add the constraint lhsfield = rhsfield
2759
       add the constraint lhsfield = rhsfield
Lines 2808-2814 do_simple_structure_copy (const struct c Link Here
2808
      struct constraint_expr temprhs = rhs;
2778
      struct constraint_expr temprhs = rhs;
2809
      unsigned HOST_WIDE_INT fieldoffset;
2779
      unsigned HOST_WIDE_INT fieldoffset;
2810
2780
2811
      templhs.var = p->id;            
2781
      templhs.var = p->id;
2812
      q = get_varinfo (temprhs.var);
2782
      q = get_varinfo (temprhs.var);
2813
      fieldoffset = p->offset - pstart;
2783
      fieldoffset = p->offset - pstart;
2814
      q = first_vi_for_offset (q, q->offset + fieldoffset);
2784
      q = first_vi_for_offset (q, q->offset + fieldoffset);
Lines 2823-2830 do_simple_structure_copy (const struct c Link Here
2823
2793
2824
/* Handle the structure copy case where we have a  structure copy between a
2794
/* Handle the structure copy case where we have a  structure copy between a
2825
   aggregate on the LHS and a dereference of a pointer on the RHS
2795
   aggregate on the LHS and a dereference of a pointer on the RHS
2826
   that is of SIZE (in bits) 
2796
   that is of SIZE (in bits)
2827
  
2797
2828
   For each field of the lhs variable (lhsfield)
2798
   For each field of the lhs variable (lhsfield)
2829
       rhs.offset = lhsfield->offset
2799
       rhs.offset = lhsfield->offset
2830
       add the constraint lhsfield = rhs
2800
       add the constraint lhsfield = rhs
Lines 2849-2860 do_rhs_deref_structure_copy (const struc Link Here
2849
2819
2850
2820
2851
      if (templhs.type == SCALAR)
2821
      if (templhs.type == SCALAR)
2852
	templhs.var = p->id;      
2822
	templhs.var = p->id;
2853
      else
2823
      else
2854
	templhs.offset = p->offset;
2824
	templhs.offset = p->offset;
2855
      
2825
2856
      q = get_varinfo (temprhs.var);
2826
      q = get_varinfo (temprhs.var);
2857
      fieldoffset = p->offset - pstart;      
2827
      fieldoffset = p->offset - pstart;
2858
      temprhs.offset += fieldoffset;
2828
      temprhs.offset += fieldoffset;
2859
      process_constraint (new_constraint (templhs, temprhs));
2829
      process_constraint (new_constraint (templhs, temprhs));
2860
    }
2830
    }
Lines 2862-2868 do_rhs_deref_structure_copy (const struc Link Here
2862
2832
2863
/* Handle the structure copy case where we have a structure copy
2833
/* Handle the structure copy case where we have a structure copy
2864
   between a aggregate on the RHS and a dereference of a pointer on
2834
   between a aggregate on the RHS and a dereference of a pointer on
2865
   the LHS that is of SIZE (in bits) 
2835
   the LHS that is of SIZE (in bits)
2866
2836
2867
   For each field of the rhs variable (rhsfield)
2837
   For each field of the rhs variable (rhsfield)
2868
       lhs.offset = rhsfield->offset
2838
       lhs.offset = rhsfield->offset
Lines 2888-2899 do_lhs_deref_structure_copy (const struc Link Here
2888
2858
2889
2859
2890
      if (temprhs.type == SCALAR)
2860
      if (temprhs.type == SCALAR)
2891
	temprhs.var = p->id;      
2861
	temprhs.var = p->id;
2892
      else
2862
      else
2893
	temprhs.offset = p->offset;
2863
	temprhs.offset = p->offset;
2894
      
2864
2895
      q = get_varinfo (templhs.var);
2865
      q = get_varinfo (templhs.var);
2896
      fieldoffset = p->offset - pstart;      
2866
      fieldoffset = p->offset - pstart;
2897
      templhs.offset += fieldoffset;
2867
      templhs.offset += fieldoffset;
2898
      process_constraint (new_constraint (templhs, temprhs));
2868
      process_constraint (new_constraint (templhs, temprhs));
2899
    }
2869
    }
Lines 2901-2907 do_lhs_deref_structure_copy (const struc Link Here
2901
2871
2902
/* Sometimes, frontends like to give us bad type information.  This
2872
/* Sometimes, frontends like to give us bad type information.  This
2903
   function will collapse all the fields from VAR to the end of VAR,
2873
   function will collapse all the fields from VAR to the end of VAR,
2904
   into VAR, so that we treat those fields as a single variable. 
2874
   into VAR, so that we treat those fields as a single variable.
2905
   We return the variable they were collapsed into.  */
2875
   We return the variable they were collapsed into.  */
2906
2876
2907
static unsigned int
2877
static unsigned int
Lines 2913-2928 collapse_rest_of_var (unsigned int var) Link Here
2913
  for (field = currvar->next; field; field = field->next)
2883
  for (field = currvar->next; field; field = field->next)
2914
    {
2884
    {
2915
      if (dump_file)
2885
      if (dump_file)
2916
	fprintf (dump_file, "Type safety: Collapsing var %s into %s\n", 
2886
	fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2917
		 field->name, currvar->name);
2887
		 field->name, currvar->name);
2918
      
2888
2919
      gcc_assert (!field->collapsed_to);
2889
      gcc_assert (!field->collapsed_to);
2920
      field->collapsed_to = currvar;
2890
      field->collapsed_to = currvar;
2921
    }
2891
    }
2922
2892
2923
  currvar->next = NULL;
2893
  currvar->next = NULL;
2924
  currvar->size = currvar->fullsize - currvar->offset;
2894
  currvar->size = currvar->fullsize - currvar->offset;
2925
  
2895
2926
  return currvar->id;
2896
  return currvar->id;
2927
}
2897
}
2928
2898
Lines 2944-2950 do_structure_copy (tree lhsop, tree rhso Link Here
2944
  gcc_assert (VEC_length (ce_s, rhsc) == 1);
2914
  gcc_assert (VEC_length (ce_s, rhsc) == 1);
2945
  lhs = *(VEC_last (ce_s, lhsc));
2915
  lhs = *(VEC_last (ce_s, lhsc));
2946
  rhs = *(VEC_last (ce_s, rhsc));
2916
  rhs = *(VEC_last (ce_s, rhsc));
2947
  
2917
2948
  VEC_free (ce_s, heap, lhsc);
2918
  VEC_free (ce_s, heap, lhsc);
2949
  VEC_free (ce_s, heap, rhsc);
2919
  VEC_free (ce_s, heap, rhsc);
2950
2920
Lines 2955-2961 do_structure_copy (tree lhsop, tree rhso Link Here
2955
      lhs = rhs;
2925
      lhs = rhs;
2956
      rhs = tmp;
2926
      rhs = tmp;
2957
    }
2927
    }
2958
  
2928
2959
  /*  This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2929
  /*  This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2960
      possible it's something we could handle.  However, most cases falling
2930
      possible it's something we could handle.  However, most cases falling
2961
      into this are dealing with transparent unions, which are slightly
2931
      into this are dealing with transparent unions, which are slightly
Lines 3021-3031 do_structure_copy (tree lhsop, tree rhso Link Here
3021
      else
2991
      else
3022
	lhssize = TREE_INT_CST_LOW (lhstypesize);
2992
	lhssize = TREE_INT_CST_LOW (lhstypesize);
3023
2993
3024
  
2994
3025
      if (rhs.type == SCALAR && lhs.type == SCALAR)  
2995
      if (rhs.type == SCALAR && lhs.type == SCALAR)
3026
	{
2996
	{
3027
	  if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2997
	  if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3028
	    {	      
2998
	    {
3029
	      lhs.var = collapse_rest_of_var (lhs.var);
2999
	      lhs.var = collapse_rest_of_var (lhs.var);
3030
	      rhs.var = collapse_rest_of_var (rhs.var);
3000
	      rhs.var = collapse_rest_of_var (rhs.var);
3031
	      lhs.offset = 0;
3001
	      lhs.offset = 0;
Lines 3042-3048 do_structure_copy (tree lhsop, tree rhso Link Here
3042
      else
3012
      else
3043
	{
3013
	{
3044
	  tree pointedtotype = lhstype;
3014
	  tree pointedtotype = lhstype;
3045
	  tree tmpvar;  
3015
	  tree tmpvar;
3046
3016
3047
	  gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3017
	  gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3048
	  tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3018
	  tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
Lines 3052-3057 do_structure_copy (tree lhsop, tree rhso Link Here
3052
    }
3022
    }
3053
}
3023
}
3054
3024
3025
3055
/* Update related alias information kept in AI.  This is used when
3026
/* Update related alias information kept in AI.  This is used when
3056
   building name tags, alias sets and deciding grouping heuristics.
3027
   building name tags, alias sets and deciding grouping heuristics.
3057
   STMT is the statement to process.  This function also updates
3028
   STMT is the statement to process.  This function also updates
Lines 3261-3267 update_alias_info (tree stmt, struct ali Link Here
3261
    }
3232
    }
3262
}
3233
}
3263
3234
3264
3265
/* Handle pointer arithmetic EXPR when creating aliasing constraints.
3235
/* Handle pointer arithmetic EXPR when creating aliasing constraints.
3266
   Expressions of the type PTR + CST can be handled in two ways:
3236
   Expressions of the type PTR + CST can be handled in two ways:
3267
3237
Lines 3307-3312 handle_ptr_arith (VEC (ce_s, heap) *lhsc Link Here
3307
  else
3277
  else
3308
    return false;
3278
    return false;
3309
3279
3280
3310
  for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3281
  for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3311
    for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3282
    for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3312
      {
3283
      {
Lines 3360-3371 find_func_aliases (tree origt) Link Here
3360
	{
3331
	{
3361
	  int i;
3332
	  int i;
3362
	  unsigned int j;
3333
	  unsigned int j;
3363
	  
3334
3364
	  /* For a phi node, assign all the arguments to
3335
	  /* For a phi node, assign all the arguments to
3365
	     the result.  */
3336
	     the result.  */
3366
	  get_constraint_for (PHI_RESULT (t), &lhsc);
3337
	  get_constraint_for (PHI_RESULT (t), &lhsc);
3367
	  for (i = 0; i < PHI_NUM_ARGS (t); i++)
3338
	  for (i = 0; i < PHI_NUM_ARGS (t); i++)
3368
	    { 
3339
	    {
3369
	      tree rhstype;
3340
	      tree rhstype;
3370
	      tree strippedrhs = PHI_ARG_DEF (t, i);
3341
	      tree strippedrhs = PHI_ARG_DEF (t, i);
3371
3342
Lines 3401-3407 find_func_aliases (tree origt) Link Here
3401
    {
3372
    {
3402
      tree lhsop;
3373
      tree lhsop;
3403
      tree rhsop;
3374
      tree rhsop;
3404
      unsigned int varid;
3405
      tree arglist;
3375
      tree arglist;
3406
      varinfo_t fi;
3376
      varinfo_t fi;
3407
      int i = 1;
3377
      int i = 1;
Lines 3423-3439 find_func_aliases (tree origt) Link Here
3423
	 we should still be able to handle.  */
3393
	 we should still be able to handle.  */
3424
      if (decl)
3394
      if (decl)
3425
	{
3395
	{
3426
	  varid = get_id_for_tree (decl);
3396
	  fi = get_vi_for_tree (decl);
3427
	}
3397
	}
3428
      else
3398
      else
3429
	{
3399
	{
3430
	  decl = TREE_OPERAND (rhsop, 0);
3400
	  decl = TREE_OPERAND (rhsop, 0);
3431
	  varid = get_id_for_tree (decl);
3401
	  fi = get_vi_for_tree (decl);
3432
	}
3402
	}
3433
3403
3434
      /* Assign all the passed arguments to the appropriate incoming
3404
      /* Assign all the passed arguments to the appropriate incoming
3435
	 parameters of the function.  */
3405
	 parameters of the function.  */
3436
      fi = get_varinfo (varid);
3437
      arglist = TREE_OPERAND (rhsop, 1);
3406
      arglist = TREE_OPERAND (rhsop, 1);
3438
	
3407
	
3439
      for (;arglist; arglist = TREE_CHAIN (arglist))
3408
      for (;arglist; arglist = TREE_CHAIN (arglist))
Lines 3463-3475 find_func_aliases (tree origt) Link Here
3463
	    }
3432
	    }
3464
	  i++;
3433
	  i++;
3465
	}
3434
	}
3435
3466
      /* If we are returning a value, assign it to the result.  */
3436
      /* If we are returning a value, assign it to the result.  */
3467
      if (lhsop)
3437
      if (lhsop)
3468
	{
3438
	{
3469
	  struct constraint_expr rhs;
3439
	  struct constraint_expr rhs;
3470
	  struct constraint_expr *lhsp;
3440
	  struct constraint_expr *lhsp;
3471
	  unsigned int j = 0;
3441
	  unsigned int j = 0;
3472
	  
3442
3473
	  get_constraint_for (lhsop, &lhsc);
3443
	  get_constraint_for (lhsop, &lhsc);
3474
	  if (TREE_CODE (decl) != FUNCTION_DECL)
3444
	  if (TREE_CODE (decl) != FUNCTION_DECL)
3475
	    {
3445
	    {
Lines 3485-3491 find_func_aliases (tree origt) Link Here
3485
	    }
3455
	    }
3486
	  for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3456
	  for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3487
	    process_constraint (new_constraint (*lhsp, rhs));
3457
	    process_constraint (new_constraint (*lhsp, rhs));
3488
	}      
3458
	}
3489
    }
3459
    }
3490
  /* Otherwise, just a regular assignment statement.  */
3460
  /* Otherwise, just a regular assignment statement.  */
3491
  else if (TREE_CODE (t) == MODIFY_EXPR)
3461
  else if (TREE_CODE (t) == MODIFY_EXPR)
Lines 3494-3500 find_func_aliases (tree origt) Link Here
3494
      tree rhsop = TREE_OPERAND (t, 1);
3464
      tree rhsop = TREE_OPERAND (t, 1);
3495
      int i;
3465
      int i;
3496
3466
3497
      if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) 
3467
      if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3498
	   || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3468
	   || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3499
	  && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3469
	  && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3500
	      || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3470
	      || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
Lines 3513-3519 find_func_aliases (tree origt) Link Here
3513
		{
3483
		{
3514
		  /* RHS that consist of unary operations,
3484
		  /* RHS that consist of unary operations,
3515
		     exceptional types, or bare decls/constants, get
3485
		     exceptional types, or bare decls/constants, get
3516
		     handled directly by get_constraint_for.  */ 
3486
		     handled directly by get_constraint_for.  */
3517
		  case tcc_reference:
3487
		  case tcc_reference:
3518
		  case tcc_declaration:
3488
		  case tcc_declaration:
3519
		  case tcc_constant:
3489
		  case tcc_constant:
Lines 3528-3534 find_func_aliases (tree origt) Link Here
3528
			  {
3498
			  {
3529
			    struct constraint_expr *c2;
3499
			    struct constraint_expr *c2;
3530
			    unsigned int k;
3500
			    unsigned int k;
3531
			    
3501
3532
			    for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3502
			    for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3533
			      process_constraint (new_constraint (*c, *c2));
3503
			      process_constraint (new_constraint (*c, *c2));
3534
			  }
3504
			  }
Lines 3570-3576 find_func_aliases (tree origt) Link Here
3570
			      }
3540
			      }
3571
			  }
3541
			  }
3572
		      }
3542
		      }
3573
		}      
3543
		}
3574
	    }
3544
	    }
3575
	}
3545
	}
3576
    }
3546
    }
Lines 3578-3584 find_func_aliases (tree origt) Link Here
3578
  /* After promoting variables and computing aliasing we will
3548
  /* After promoting variables and computing aliasing we will
3579
     need to re-scan most statements.  FIXME: Try to minimize the
3549
     need to re-scan most statements.  FIXME: Try to minimize the
3580
     number of statements re-scanned.  It's not really necessary to
3550
     number of statements re-scanned.  It's not really necessary to
3581
     re-scan *all* statements.  */  
3551
     re-scan *all* statements.  */
3582
  mark_stmt_modified (origt);
3552
  mark_stmt_modified (origt);
3583
  VEC_free (ce_s, heap, rhsc);
3553
  VEC_free (ce_s, heap, rhsc);
3584
  VEC_free (ce_s, heap, lhsc);
3554
  VEC_free (ce_s, heap, lhsc);
Lines 3591-3597 find_func_aliases (tree origt) Link Here
3591
   first field that overlaps with OFFSET.
3561
   first field that overlaps with OFFSET.
3592
   Return NULL if we can't find one.  */
3562
   Return NULL if we can't find one.  */
3593
3563
3594
static varinfo_t 
3564
static varinfo_t
3595
first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3565
first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3596
{
3566
{
3597
  varinfo_t curr = start;
3567
  varinfo_t curr = start;
Lines 3617-3623 insert_into_field_list (varinfo_t base, Link Here
3617
{
3587
{
3618
  varinfo_t prev = base;
3588
  varinfo_t prev = base;
3619
  varinfo_t curr = base->next;
3589
  varinfo_t curr = base->next;
3620
  
3590
3621
  field->next = curr;
3591
  field->next = curr;
3622
  prev->next = field;
3592
  prev->next = field;
3623
}
3593
}
Lines 3630-3636 insert_into_field_list_sorted (varinfo_t Link Here
3630
{
3600
{
3631
  varinfo_t prev = base;
3601
  varinfo_t prev = base;
3632
  varinfo_t curr = base->next;
3602
  varinfo_t curr = base->next;
3633
  
3603
3634
  if (curr == NULL)
3604
  if (curr == NULL)
3635
    {
3605
    {
3636
      prev->next = field;
3606
      prev->next = field;
Lines 3652-3664 insert_into_field_list_sorted (varinfo_t Link Here
3652
3622
3653
/* qsort comparison function for two fieldoff's PA and PB */
3623
/* qsort comparison function for two fieldoff's PA and PB */
3654
3624
3655
static int 
3625
static int
3656
fieldoff_compare (const void *pa, const void *pb)
3626
fieldoff_compare (const void *pa, const void *pb)
3657
{
3627
{
3658
  const fieldoff_s *foa = (const fieldoff_s *)pa;
3628
  const fieldoff_s *foa = (const fieldoff_s *)pa;
3659
  const fieldoff_s *fob = (const fieldoff_s *)pb;
3629
  const fieldoff_s *fob = (const fieldoff_s *)pb;
3660
  HOST_WIDE_INT foasize, fobsize;
3630
  HOST_WIDE_INT foasize, fobsize;
3661
  
3631
3662
  if (foa->offset != fob->offset)
3632
  if (foa->offset != fob->offset)
3663
    return foa->offset - fob->offset;
3633
    return foa->offset - fob->offset;
3664
3634
Lines 3671-3678 fieldoff_compare (const void *pa, const Link Here
3671
void
3641
void
3672
sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3642
sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3673
{
3643
{
3674
  qsort (VEC_address (fieldoff_s, fieldstack), 
3644
  qsort (VEC_address (fieldoff_s, fieldstack),
3675
	 VEC_length (fieldoff_s, fieldstack), 
3645
	 VEC_length (fieldoff_s, fieldstack),
3676
	 sizeof (fieldoff_s),
3646
	 sizeof (fieldoff_s),
3677
	 fieldoff_compare);
3647
	 fieldoff_compare);
3678
}
3648
}
Lines 3686-3697 sort_fieldstack (VEC(fieldoff_s,heap) *f Link Here
3686
   TYPE.  */
3656
   TYPE.  */
3687
3657
3688
int
3658
int
3689
push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, 
3659
push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3690
			     HOST_WIDE_INT offset, bool *has_union)
3660
			     HOST_WIDE_INT offset, bool *has_union)
3691
{
3661
{
3692
  tree field;
3662
  tree field;
3693
  int count = 0;
3663
  int count = 0;
3694
  
3664
3695
  if (TREE_CODE (type) == COMPLEX_TYPE)
3665
  if (TREE_CODE (type) == COMPLEX_TYPE)
3696
    {
3666
    {
3697
      fieldoff_s *real_part, *img_part;
3667
      fieldoff_s *real_part, *img_part;
Lines 3700-3712 push_fields_onto_fieldstack (tree type, Link Here
3700
      real_part->size = TYPE_SIZE (TREE_TYPE (type));
3670
      real_part->size = TYPE_SIZE (TREE_TYPE (type));
3701
      real_part->offset = offset;
3671
      real_part->offset = offset;
3702
      real_part->decl = NULL_TREE;
3672
      real_part->decl = NULL_TREE;
3703
      
3673
3704
      img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3674
      img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3705
      img_part->type = TREE_TYPE (type);
3675
      img_part->type = TREE_TYPE (type);
3706
      img_part->size = TYPE_SIZE (TREE_TYPE (type));
3676
      img_part->size = TYPE_SIZE (TREE_TYPE (type));
3707
      img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3677
      img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3708
      img_part->decl = NULL_TREE;
3678
      img_part->decl = NULL_TREE;
3709
      
3679
3710
      return 2;
3680
      return 2;
3711
    }
3681
    }
3712
3682
Lines 3733-3744 push_fields_onto_fieldstack (tree type, Link Here
3733
	{
3703
	{
3734
	  bool push = false;
3704
	  bool push = false;
3735
	  int pushed = 0;
3705
	  int pushed = 0;
3736
	
3706
3737
	  if (has_union 
3707
	  if (has_union
3738
	      && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3708
	      && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3739
		  || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3709
		  || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3740
	    *has_union = true;
3710
	    *has_union = true;
3741
	
3711
3742
	  if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3712
	  if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3743
	    push = true;
3713
	    push = true;
3744
	  else if (!(pushed = push_fields_onto_fieldstack
3714
	  else if (!(pushed = push_fields_onto_fieldstack
Lines 3772-3783 push_fields_onto_fieldstack (tree type, Link Here
3772
      {
3742
      {
3773
	bool push = false;
3743
	bool push = false;
3774
	int pushed = 0;
3744
	int pushed = 0;
3775
	
3745
3776
	if (has_union 
3746
	if (has_union
3777
	    && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3747
	    && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3778
		|| TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3748
		|| TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3779
	  *has_union = true;
3749
	  *has_union = true;
3780
	
3750
3781
	if (!var_can_have_subvars (field))
3751
	if (!var_can_have_subvars (field))
3782
	  push = true;
3752
	  push = true;
3783
	else if (!(pushed = push_fields_onto_fieldstack
3753
	else if (!(pushed = push_fields_onto_fieldstack
Lines 3789-3795 push_fields_onto_fieldstack (tree type, Link Here
3789
	     see if we didn't push any subfields and the size is
3759
	     see if we didn't push any subfields and the size is
3790
	     nonzero, push the field onto the stack */
3760
	     nonzero, push the field onto the stack */
3791
	  push = true;
3761
	  push = true;
3792
	
3762
3793
	if (push)
3763
	if (push)
3794
	  {
3764
	  {
3795
	    fieldoff_s *pair;
3765
	    fieldoff_s *pair;
Lines 3848-3862 count_num_arguments (tree decl, bool *is Link Here
3848
  unsigned int i = 0;
3818
  unsigned int i = 0;
3849
  tree t;
3819
  tree t;
3850
3820
3851
  for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); 
3821
  for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3852
       t;
3822
       t;
3853
       t = TREE_CHAIN (t))
3823
       t = TREE_CHAIN (t))
3854
    {	
3824
    {
3855
      if (TREE_VALUE (t) == void_type_node)
3825
      if (TREE_VALUE (t) == void_type_node)
3856
	break;
3826
	break;
3857
      i++;
3827
      i++;
3858
    }
3828
    }
3859
  
3829
3860
  if (!t)
3830
  if (!t)
3861
    *is_varargs = true;
3831
    *is_varargs = true;
3862
  return i;
3832
  return i;
Lines 3870-3888 create_function_info_for (tree decl, con Link Here
3870
{
3840
{
3871
  unsigned int index = VEC_length (varinfo_t, varmap);
3841
  unsigned int index = VEC_length (varinfo_t, varmap);
3872
  varinfo_t vi;
3842
  varinfo_t vi;
3873
  tree arg; 
3843
  tree arg;
3874
  unsigned int i;
3844
  unsigned int i;
3875
  bool is_varargs = false;
3845
  bool is_varargs = false;
3876
3846
3877
  /* Create the variable info.  */
3847
  /* Create the variable info.  */
3878
3848
3879
  vi = new_var_info (decl, index, name, index);
3849
  vi = new_var_info (decl, index, name);
3880
  vi->decl = decl;
3850
  vi->decl = decl;
3881
  vi->offset = 0;
3851
  vi->offset = 0;
3882
  vi->has_union = 0;
3852
  vi->has_union = 0;
3883
  vi->size = 1;
3853
  vi->size = 1;
3884
  vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3854
  vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3885
  insert_id_for_tree (vi->decl, index);  
3855
  insert_vi_for_tree (vi->decl, vi);
3886
  VEC_safe_push (varinfo_t, heap, varmap, vi);
3856
  VEC_safe_push (varinfo_t, heap, varmap, vi);
3887
3857
3888
  stats.total_vars++;
3858
  stats.total_vars++;
Lines 3898-3909 create_function_info_for (tree decl, con Link Here
3898
      return index;
3868
      return index;
3899
    }
3869
    }
3900
3870
3901
  
3871
3902
  arg = DECL_ARGUMENTS (decl);
3872
  arg = DECL_ARGUMENTS (decl);
3903
3873
3904
  /* Set up variables for each argument.  */
3874
  /* Set up variables for each argument.  */
3905
  for (i = 1; i < vi->fullsize; i++)
3875
  for (i = 1; i < vi->fullsize; i++)
3906
    {      
3876
    {
3907
      varinfo_t argvi;
3877
      varinfo_t argvi;
3908
      const char *newname;
3878
      const char *newname;
3909
      char *tempname;
3879
      char *tempname;
Lines 3912-3924 create_function_info_for (tree decl, con Link Here
3912
3882
3913
      if (arg)
3883
      if (arg)
3914
	argdecl = arg;
3884
	argdecl = arg;
3915
      
3885
3916
      newindex = VEC_length (varinfo_t, varmap);
3886
      newindex = VEC_length (varinfo_t, varmap);
3917
      asprintf (&tempname, "%s.arg%d", name, i-1);
3887
      asprintf (&tempname, "%s.arg%d", name, i-1);
3918
      newname = ggc_strdup (tempname);
3888
      newname = ggc_strdup (tempname);
3919
      free (tempname);
3889
      free (tempname);
3920
3890
3921
      argvi = new_var_info (argdecl, newindex,newname, newindex);
3891
      argvi = new_var_info (argdecl, newindex, newname);
3922
      argvi->decl = argdecl;
3892
      argvi->decl = argdecl;
3923
      VEC_safe_push (varinfo_t, heap, varmap, argvi);
3893
      VEC_safe_push (varinfo_t, heap, varmap, argvi);
3924
      argvi->offset = i;
3894
      argvi->offset = i;
Lines 3929-3935 create_function_info_for (tree decl, con Link Here
3929
      stats.total_vars ++;
3899
      stats.total_vars ++;
3930
      if (arg)
3900
      if (arg)
3931
	{
3901
	{
3932
	  insert_id_for_tree (arg, newindex);
3902
	  insert_vi_for_tree (arg, argvi);
3933
	  arg = TREE_CHAIN (arg);
3903
	  arg = TREE_CHAIN (arg);
3934
	}
3904
	}
3935
    }
3905
    }
Lines 3948-3960 create_function_info_for (tree decl, con Link Here
3948
3918
3949
      if (DECL_RESULT (decl))
3919
      if (DECL_RESULT (decl))
3950
	resultdecl = DECL_RESULT (decl);
3920
	resultdecl = DECL_RESULT (decl);
3951
      
3921
3952
      newindex = VEC_length (varinfo_t, varmap);
3922
      newindex = VEC_length (varinfo_t, varmap);
3953
      asprintf (&tempname, "%s.result", name);
3923
      asprintf (&tempname, "%s.result", name);
3954
      newname = ggc_strdup (tempname);
3924
      newname = ggc_strdup (tempname);
3955
      free (tempname);
3925
      free (tempname);
3956
3926
3957
      resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3927
      resultvi = new_var_info (resultdecl, newindex, newname);
3958
      resultvi->decl = resultdecl;
3928
      resultvi->decl = resultdecl;
3959
      VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3929
      VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3960
      resultvi->offset = i;
3930
      resultvi->offset = i;
Lines 3964-3976 create_function_info_for (tree decl, con Link Here
3964
      insert_into_field_list_sorted (vi, resultvi);
3934
      insert_into_field_list_sorted (vi, resultvi);
3965
      stats.total_vars ++;
3935
      stats.total_vars ++;
3966
      if (DECL_RESULT (decl))
3936
      if (DECL_RESULT (decl))
3967
	insert_id_for_tree (DECL_RESULT (decl), newindex);
3937
	insert_vi_for_tree (DECL_RESULT (decl), resultvi);
3968
    }
3938
    }
3969
  return index;
3939
  return index;
3970
}  
3940
}
3971
3941
3972
3942
3973
/* Return true if FIELDSTACK contains fields that overlap. 
3943
/* Return true if FIELDSTACK contains fields that overlap.
3974
   FIELDSTACK is assumed to be sorted by offset.  */
3944
   FIELDSTACK is assumed to be sorted by offset.  */
3975
3945
3976
static bool
3946
static bool
Lines 4057-4068 create_variable_info_for (tree decl, con Link Here
4057
  bool hasunion;
4027
  bool hasunion;
4058
  bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4028
  bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4059
  VEC (fieldoff_s,heap) *fieldstack = NULL;
4029
  VEC (fieldoff_s,heap) *fieldstack = NULL;
4060
  
4030
4061
  if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4031
  if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4062
    return create_function_info_for (decl, name);
4032
    return create_function_info_for (decl, name);
4063
4033
4064
  hasunion = TREE_CODE (decltype) == UNION_TYPE
4034
  hasunion = TREE_CODE (decltype) == UNION_TYPE
4065
             || TREE_CODE (decltype) == QUAL_UNION_TYPE;
4035
	     || TREE_CODE (decltype) == QUAL_UNION_TYPE;
4066
  if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
4036
  if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
4067
    {
4037
    {
4068
      push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
4038
      push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
Lines 4072-4083 create_variable_info_for (tree decl, con Link Here
4072
	  notokay = true;
4042
	  notokay = true;
4073
	}
4043
	}
4074
    }
4044
    }
4075
  
4045
4076
4046
4077
  /* If the variable doesn't have subvars, we may end up needing to
4047
  /* If the variable doesn't have subvars, we may end up needing to
4078
     sort the field list and create fake variables for all the
4048
     sort the field list and create fake variables for all the
4079
     fields.  */
4049
     fields.  */
4080
  vi = new_var_info (decl, index, name, index);
4050
  vi = new_var_info (decl, index, name);
4081
  vi->decl = decl;
4051
  vi->decl = decl;
4082
  vi->offset = 0;
4052
  vi->offset = 0;
4083
  vi->has_union = hasunion;
4053
  vi->has_union = hasunion;
Lines 4095-4102 create_variable_info_for (tree decl, con Link Here
4095
      vi->fullsize = TREE_INT_CST_LOW (declsize);
4065
      vi->fullsize = TREE_INT_CST_LOW (declsize);
4096
      vi->size = vi->fullsize;
4066
      vi->size = vi->fullsize;
4097
    }
4067
    }
4098
  
4068
4099
  insert_id_for_tree (vi->decl, index);  
4069
  insert_vi_for_tree (vi->decl, vi);
4100
  VEC_safe_push (varinfo_t, heap, varmap, vi);
4070
  VEC_safe_push (varinfo_t, heap, varmap, vi);
4101
  if (is_global && (!flag_whole_program || !in_ipa_mode))
4071
  if (is_global && (!flag_whole_program || !in_ipa_mode))
4102
    {
4072
    {
Lines 4122-4130 create_variable_info_for (tree decl, con Link Here
4122
    }
4092
    }
4123
4093
4124
  stats.total_vars++;
4094
  stats.total_vars++;
4125
  if (use_field_sensitive 
4095
  if (use_field_sensitive
4126
      && !notokay 
4096
      && !notokay
4127
      && !vi->is_unknown_size_var 
4097
      && !vi->is_unknown_size_var
4128
      && var_can_have_subvars (decl)
4098
      && var_can_have_subvars (decl)
4129
      && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4099
      && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4130
    {
4100
    {
Lines 4148-4154 create_variable_info_for (tree decl, con Link Here
4148
	 without creating varinfos for the fields anyway, so sorting them is a
4118
	 without creating varinfos for the fields anyway, so sorting them is a
4149
	 waste to boot.  */
4119
	 waste to boot.  */
4150
      if (!notokay)
4120
      if (!notokay)
4151
	{	
4121
	{
4152
	  sort_fieldstack (fieldstack);
4122
	  sort_fieldstack (fieldstack);
4153
	  /* Due to some C++ FE issues, like PR 22488, we might end up
4123
	  /* Due to some C++ FE issues, like PR 22488, we might end up
4154
	     what appear to be overlapping fields even though they,
4124
	     what appear to be overlapping fields even though they,
Lines 4156-4163 create_variable_info_for (tree decl, con Link Here
4156
	     we will simply disable field-sensitivity for these cases.  */
4126
	     we will simply disable field-sensitivity for these cases.  */
4157
	  notokay = check_for_overlaps (fieldstack);
4127
	  notokay = check_for_overlaps (fieldstack);
4158
	}
4128
	}
4159
      
4129
4160
      
4130
4161
      if (VEC_length (fieldoff_s, fieldstack) != 0)
4131
      if (VEC_length (fieldoff_s, fieldstack) != 0)
4162
	fo = VEC_index (fieldoff_s, fieldstack, 0);
4132
	fo = VEC_index (fieldoff_s, fieldstack, 0);
4163
4133
Lines 4169-4179 create_variable_info_for (tree decl, con Link Here
4169
	  VEC_free (fieldoff_s, heap, fieldstack);
4139
	  VEC_free (fieldoff_s, heap, fieldstack);
4170
	  return index;
4140
	  return index;
4171
	}
4141
	}
4172
      
4142
4173
      vi->size = TREE_INT_CST_LOW (fo->size);
4143
      vi->size = TREE_INT_CST_LOW (fo->size);
4174
      vi->offset = fo->offset;
4144
      vi->offset = fo->offset;
4175
      for (i = VEC_length (fieldoff_s, fieldstack) - 1; 
4145
      for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4176
	   i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo); 
4146
	   i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4177
	   i--)
4147
	   i--)
4178
	{
4148
	{
4179
	  varinfo_t newvi;
4149
	  varinfo_t newvi;
Lines 4184-4198 create_variable_info_for (tree decl, con Link Here
4184
	  if (dump_file)
4154
	  if (dump_file)
4185
	    {
4155
	    {
4186
	      if (fo->decl)
4156
	      if (fo->decl)
4187
	        asprintf (&tempname, "%s.%s",
4157
		asprintf (&tempname, "%s.%s",
4188
			  vi->name, alias_get_name (fo->decl));
4158
			  vi->name, alias_get_name (fo->decl));
4189
	      else
4159
	      else
4190
	        asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4160
		asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4191
			  vi->name, fo->offset);
4161
			  vi->name, fo->offset);
4192
	      newname = ggc_strdup (tempname);
4162
	      newname = ggc_strdup (tempname);
4193
	      free (tempname);
4163
	      free (tempname);
4194
	    }
4164
	    }
4195
	  newvi = new_var_info (decl, newindex, newname, newindex);
4165
	  newvi = new_var_info (decl, newindex, newname);
4196
	  newvi->offset = fo->offset;
4166
	  newvi->offset = fo->offset;
4197
	  newvi->size = TREE_INT_CST_LOW (fo->size);
4167
	  newvi->size = TREE_INT_CST_LOW (fo->size);
4198
	  newvi->fullsize = vi->fullsize;
4168
	  newvi->fullsize = vi->fullsize;
Lines 4228-4241 dump_solution_for_var (FILE *file, unsig Link Here
4228
{
4198
{
4229
  varinfo_t vi = get_varinfo (var);
4199
  varinfo_t vi = get_varinfo (var);
4230
  unsigned int i;
4200
  unsigned int i;
4231
  bitmap_iterator bi; 
4201
  bitmap_iterator bi;
4232
  
4202
4233
  fprintf (file, "%s = { ", vi->name);
4203
  if (find (var) != var)
4234
  EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
4235
    {
4204
    {
4236
      fprintf (file, "%s ", get_varinfo (i)->name);
4205
      varinfo_t vipt = get_varinfo (find (var));
4206
      fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4207
    }
4208
  else
4209
    {
4210
      fprintf (file, "%s = { ", vi->name);
4211
      EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4212
	{
4213
	  fprintf (file, "%s ", get_varinfo (i)->name);
4214
	}
4215
      fprintf (file, "}\n");
4237
    }
4216
    }
4238
  fprintf (file, "}\n");
4239
}
4217
}
4240
4218
4241
/* Print the points-to solution for VAR to stdout.  */
4219
/* Print the points-to solution for VAR to stdout.  */
Lines 4266-4272 intra_create_variable_infos (void) Link Here
4266
      if (!could_have_pointers (t))
4244
      if (!could_have_pointers (t))
4267
	continue;
4245
	continue;
4268
      
4246
      
4269
      arg_id = get_id_for_tree (t);
4247
      arg_id = get_vi_for_tree (t)->id;
4270
4248
4271
      /* With flag_argument_noalias greater than two means that the incoming
4249
      /* With flag_argument_noalias greater than two means that the incoming
4272
         argument cannot alias anything except for itself so create a HEAP
4250
         argument cannot alias anything except for itself so create a HEAP
Lines 4280-4286 intra_create_variable_infos (void) Link Here
4280
	  
4258
	  
4281
	  lhs.offset = 0;
4259
	  lhs.offset = 0;
4282
	  lhs.type = SCALAR;
4260
	  lhs.type = SCALAR;
4283
	  lhs.var  = get_id_for_tree (t);
4261
	  lhs.var  = get_vi_for_tree (t)->id;
4284
	  
4262
	  
4285
	  if (heapvar == NULL_TREE)
4263
	  if (heapvar == NULL_TREE)
4286
	    {
4264
	    {
Lines 4291-4298 intra_create_variable_infos (void) Link Here
4291
		add_referenced_var (heapvar);
4269
		add_referenced_var (heapvar);
4292
	      heapvar_insert (t, heapvar);
4270
	      heapvar_insert (t, heapvar);
4293
	    }
4271
	    }
4294
	  id = get_id_for_tree (heapvar);
4272
4295
	  vi = get_varinfo (id);
4273
	  vi = get_vi_for_tree (heapvar);
4296
	  vi->is_artificial_var = 1;
4274
	  vi->is_artificial_var = 1;
4297
	  vi->is_heap_var = 1;
4275
	  vi->is_heap_var = 1;
4298
	  rhs.var = id;
4276
	  rhs.var = id;
Lines 4409-4416 static bool have_alias_info = false; Link Here
4409
bool
4387
bool
4410
find_what_p_points_to (tree p)
4388
find_what_p_points_to (tree p)
4411
{
4389
{
4412
  unsigned int id = 0;
4413
  tree lookup_p = p;
4390
  tree lookup_p = p;
4391
  varinfo_t vi;
4414
4392
4415
  if (!have_alias_info)
4393
  if (!have_alias_info)
4416
    return false;
4394
    return false;
Lines 4422-4431 find_what_p_points_to (tree p) Link Here
4422
      && default_def (SSA_NAME_VAR (p)) == p)
4400
      && default_def (SSA_NAME_VAR (p)) == p)
4423
    lookup_p = SSA_NAME_VAR (p);
4401
    lookup_p = SSA_NAME_VAR (p);
4424
4402
4425
  if (lookup_id_for_tree (lookup_p, &id))
4403
  vi = lookup_vi_for_tree (lookup_p);
4404
  if (vi)
4426
    {
4405
    {
4427
      varinfo_t vi = get_varinfo (id);
4406
      
4428
4429
      if (vi->is_artificial_var)
4407
      if (vi->is_artificial_var)
4430
	return false;
4408
	return false;
4431
4409
Lines 4447-4453 find_what_p_points_to (tree p) Link Here
4447
4425
4448
	  /* This variable may have been collapsed, let's get the real
4426
	  /* This variable may have been collapsed, let's get the real
4449
	     variable.  */
4427
	     variable.  */
4450
	  vi = get_varinfo (vi->node);
4428
	  vi = get_varinfo (find (vi->id));
4451
	  
4429
	  
4452
	  /* Translate artificial variables into SSA_NAME_PTR_INFO
4430
	  /* Translate artificial variables into SSA_NAME_PTR_INFO
4453
	     attributes.  */
4431
	     attributes.  */
Lines 4506-4518 dump_sa_points_to_info (FILE *outfile) Link Here
4506
    {
4484
    {
4507
      fprintf (outfile, "Stats:\n");
4485
      fprintf (outfile, "Stats:\n");
4508
      fprintf (outfile, "Total vars:               %d\n", stats.total_vars);
4486
      fprintf (outfile, "Total vars:               %d\n", stats.total_vars);
4487
      fprintf (outfile, "Non-pointer vars:          %d\n",
4488
	       stats.nonpointer_vars);
4509
      fprintf (outfile, "Statically unified vars:  %d\n",
4489
      fprintf (outfile, "Statically unified vars:  %d\n",
4510
	       stats.unified_vars_static);
4490
	       stats.unified_vars_static);
4511
      fprintf (outfile, "Collapsed vars:           %d\n", stats.collapsed_vars);
4512
      fprintf (outfile, "Dynamically unified vars: %d\n",
4491
      fprintf (outfile, "Dynamically unified vars: %d\n",
4513
	       stats.unified_vars_dynamic);
4492
	       stats.unified_vars_dynamic);
4514
      fprintf (outfile, "Iterations:               %d\n", stats.iterations);
4493
      fprintf (outfile, "Iterations:               %d\n", stats.iterations);
4515
      fprintf (outfile, "Number of edges:          %d\n", stats.num_edges);
4494
      fprintf (outfile, "Number of edges:          %d\n", stats.num_edges);
4495
      fprintf (outfile, "Number of implicit edges: %d\n",
4496
	       stats.num_implicit_edges);
4516
    }
4497
    }
4517
4498
4518
  for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4499
  for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
Lines 4540-4547 init_base_vars (void) Link Here
4540
  /* Create the NULL variable, used to represent that a variable points
4521
  /* Create the NULL variable, used to represent that a variable points
4541
     to NULL.  */
4522
     to NULL.  */
4542
  nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4523
  nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4543
  var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4524
  var_nothing = new_var_info (nothing_tree, 0, "NULL");
4544
  insert_id_for_tree (nothing_tree, 0);
4525
  insert_vi_for_tree (nothing_tree, var_nothing);
4545
  var_nothing->is_artificial_var = 1;
4526
  var_nothing->is_artificial_var = 1;
4546
  var_nothing->offset = 0;
4527
  var_nothing->offset = 0;
4547
  var_nothing->size = ~0;
4528
  var_nothing->size = ~0;
Lines 4553-4560 init_base_vars (void) Link Here
4553
  /* Create the ANYTHING variable, used to represent that a variable
4534
  /* Create the ANYTHING variable, used to represent that a variable
4554
     points to some unknown piece of memory.  */
4535
     points to some unknown piece of memory.  */
4555
  anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4536
  anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4556
  var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1); 
4537
  var_anything = new_var_info (anything_tree, 1, "ANYTHING"); 
4557
  insert_id_for_tree (anything_tree, 1);
4538
  insert_vi_for_tree (anything_tree, var_anything);
4558
  var_anything->is_artificial_var = 1;
4539
  var_anything->is_artificial_var = 1;
4559
  var_anything->size = ~0;
4540
  var_anything->size = ~0;
4560
  var_anything->offset = 0;
4541
  var_anything->offset = 0;
Lines 4573-4579 init_base_vars (void) Link Here
4573
  rhs.type = ADDRESSOF;
4554
  rhs.type = ADDRESSOF;
4574
  rhs.var = anything_id;
4555
  rhs.var = anything_id;
4575
  rhs.offset = 0;
4556
  rhs.offset = 0;
4576
  var_anything->address_taken = true;
4577
4557
4578
  /* This specifically does not use process_constraint because
4558
  /* This specifically does not use process_constraint because
4579
     process_constraint ignores all anything = anything constraints, since all
4559
     process_constraint ignores all anything = anything constraints, since all
Lines 4583-4596 init_base_vars (void) Link Here
4583
  /* Create the READONLY variable, used to represent that a variable
4563
  /* Create the READONLY variable, used to represent that a variable
4584
     points to readonly memory.  */
4564
     points to readonly memory.  */
4585
  readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4565
  readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4586
  var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4566
  var_readonly = new_var_info (readonly_tree, 2, "READONLY");
4587
  var_readonly->is_artificial_var = 1;
4567
  var_readonly->is_artificial_var = 1;
4588
  var_readonly->offset = 0;
4568
  var_readonly->offset = 0;
4589
  var_readonly->size = ~0;
4569
  var_readonly->size = ~0;
4590
  var_readonly->fullsize = ~0;
4570
  var_readonly->fullsize = ~0;
4591
  var_readonly->next = NULL;
4571
  var_readonly->next = NULL;
4592
  var_readonly->is_special_var = 1;
4572
  var_readonly->is_special_var = 1;
4593
  insert_id_for_tree (readonly_tree, 2);
4573
  insert_vi_for_tree (readonly_tree, var_readonly);
4594
  readonly_id = 2;
4574
  readonly_id = 2;
4595
  VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4575
  VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4596
4576
Lines 4610-4617 init_base_vars (void) Link Here
4610
  /* Create the INTEGER variable, used to represent that a variable points
4590
  /* Create the INTEGER variable, used to represent that a variable points
4611
     to an INTEGER.  */
4591
     to an INTEGER.  */
4612
  integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4592
  integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4613
  var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4593
  var_integer = new_var_info (integer_tree, 3, "INTEGER");
4614
  insert_id_for_tree (integer_tree, 3);
4594
  insert_vi_for_tree (integer_tree, var_integer);
4615
  var_integer->is_artificial_var = 1;
4595
  var_integer->is_artificial_var = 1;
4616
  var_integer->size = ~0;
4596
  var_integer->size = ~0;
4617
  var_integer->fullsize = ~0;
4597
  var_integer->fullsize = ~0;
Lines 4634-4641 init_base_vars (void) Link Here
4634
  /* Create the ESCAPED_VARS variable used to represent variables that
4614
  /* Create the ESCAPED_VARS variable used to represent variables that
4635
     escape this function.  */
4615
     escape this function.  */
4636
  escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS");
4616
  escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS");
4637
  var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4);
4617
  var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS");
4638
  insert_id_for_tree (escaped_vars_tree, 4);
4618
  insert_vi_for_tree (escaped_vars_tree, var_escaped_vars);
4639
  var_escaped_vars->is_artificial_var = 1;
4619
  var_escaped_vars->is_artificial_var = 1;
4640
  var_escaped_vars->size = ~0;
4620
  var_escaped_vars->size = ~0;
4641
  var_escaped_vars->fullsize = ~0;
4621
  var_escaped_vars->fullsize = ~0;
Lines 4660-4680 init_base_vars (void) Link Here
4660
static void
4640
static void
4661
init_alias_vars (void)
4641
init_alias_vars (void)
4662
{
4642
{
4663
  bitmap_obstack_initialize (&ptabitmap_obstack);
4643
  bitmap_obstack_initialize (&pta_obstack);
4644
  bitmap_obstack_initialize (&oldpta_obstack);
4664
  bitmap_obstack_initialize (&predbitmap_obstack);
4645
  bitmap_obstack_initialize (&predbitmap_obstack);
4665
4646
4666
  constraint_pool = create_alloc_pool ("Constraint pool", 
4647
  constraint_pool = create_alloc_pool ("Constraint pool",
4667
				       sizeof (struct constraint), 30);
4648
				       sizeof (struct constraint), 30);
4668
  variable_info_pool = create_alloc_pool ("Variable info pool",
4649
  variable_info_pool = create_alloc_pool ("Variable info pool",
4669
					  sizeof (struct variable_info), 30);
4650
					  sizeof (struct variable_info), 30);
4670
  constraint_edge_pool = create_alloc_pool ("Constraint edges",
4671
					    sizeof (struct constraint_edge), 30);
4672
  
4673
  constraints = VEC_alloc (constraint_t, heap, 8);
4651
  constraints = VEC_alloc (constraint_t, heap, 8);
4674
  varmap = VEC_alloc (varinfo_t, heap, 8);
4652
  varmap = VEC_alloc (varinfo_t, heap, 8);
4675
  id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4653
  vi_for_tree = pointer_map_create ();
4676
  memset (&stats, 0, sizeof (stats));
4677
4654
4655
  memset (&stats, 0, sizeof (stats));
4678
  init_base_vars ();
4656
  init_base_vars ();
4679
}
4657
}
4680
4658
Lines 4777-4782 find_escape_constraints (tree stmt) Link Here
4777
  VEC_free (ce_s, heap, rhsc);
4755
  VEC_free (ce_s, heap, rhsc);
4778
}
4756
}
4779
4757
4758
4759
/* Remove the REF and ADDRESS edges from GRAPH, as well as all the
4760
   predecessor edges.  */
4761
4762
static void
4763
remove_preds_and_fake_succs (constraint_graph_t graph)
4764
{
4765
  unsigned int i;
4766
4767
  /* Clear the implicit ref and address nodes from the successor
4768
     lists.  */
4769
  for (i = 0; i < FIRST_REF_NODE; i++)
4770
    {
4771
      if (graph->succs[i])
4772
	bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
4773
			    FIRST_REF_NODE * 2);
4774
    }
4775
4776
  /* Free the successor list for the non-ref nodes.  */
4777
  for (i = FIRST_REF_NODE; i < graph->size; i++)
4778
    {
4779
      if (graph->succs[i])
4780
	BITMAP_FREE (graph->succs[i]);
4781
    }
4782
4783
  /* Now reallocate the size of the successor list as, and blow away
4784
     the predecessor bitmaps.  */
4785
  graph->size = VEC_length (varinfo_t, varmap);
4786
  graph->succs = xrealloc (graph->succs, graph->size * sizeof (bitmap));
4787
4788
  free (graph->implicit_preds);
4789
  graph->implicit_preds = NULL;
4790
  free (graph->preds);
4791
  graph->preds = NULL;
4792
  bitmap_obstack_release (&predbitmap_obstack);
4793
}
4794
4780
/* Create points-to sets for the current function.  See the comments
4795
/* Create points-to sets for the current function.  See the comments
4781
   at the start of the file for an algorithmic overview.  */
4796
   at the start of the file for an algorithmic overview.  */
4782
4797
Lines 4784-4794 void Link Here
4784
compute_points_to_sets (struct alias_info *ai)
4799
compute_points_to_sets (struct alias_info *ai)
4785
{
4800
{
4786
  basic_block bb;
4801
  basic_block bb;
4802
  struct scc_info *si;
4787
4803
4788
  timevar_push (TV_TREE_PTA);
4804
  timevar_push (TV_TREE_PTA);
4789
4805
4790
  init_alias_vars ();
4806
  init_alias_vars ();
4791
4807
  init_alias_heapvars ();
4808
  
4792
  intra_create_variable_infos ();
4809
  intra_create_variable_infos ();
4793
4810
4794
  /* Now walk all statements and derive aliases.  */
4811
  /* Now walk all statements and derive aliases.  */
Lines 4824-4859 compute_points_to_sets (struct alias_inf Link Here
4824
	}
4841
	}
4825
    }
4842
    }
4826
4843
4827
  build_constraint_graph ();
4828
4844
4829
  if (dump_file)
4845
  if (dump_file)
4830
    {
4846
    {
4831
      fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4847
      fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4832
      dump_constraints (dump_file);
4848
      dump_constraints (dump_file);
4833
    }
4849
    }
4834
  
4850
4835
  if (dump_file)
4851
  if (dump_file)
4836
    fprintf (dump_file,
4852
    fprintf (dump_file,
4837
	     "\nCollapsing static cycles and doing variable "
4853
	     "\nCollapsing static cycles and doing variable "
4838
	     "substitution:\n");
4854
	     "substitution:\n");
4839
      
4855
4840
  find_and_collapse_graph_cycles (graph, false);
4856
  build_pred_graph ();
4841
  perform_var_substitution (graph);
4857
  si = perform_var_substitution (graph);
4842
      
4858
  move_complex_constraints (graph, si);
4859
  free_var_substitution_info (si);
4860
  
4861
  build_succ_graph ();
4862
  find_indirect_cycles (graph);
4863
4864
  /* Implicit nodes and predecessors are no longer necessary at this
4865
     point. */
4866
  remove_preds_and_fake_succs (graph);
4867
4843
  if (dump_file)
4868
  if (dump_file)
4844
    fprintf (dump_file, "\nSolving graph:\n");
4869
    fprintf (dump_file, "\nSolving graph:\n");
4845
      
4870
4846
  solve_graph (graph);
4871
  solve_graph (graph);
4847
  
4872
4848
  if (dump_file)
4873
  if (dump_file)
4849
    dump_sa_points_to_info (dump_file);
4874
    dump_sa_points_to_info (dump_file);
4850
  
4851
  have_alias_info = true;
4875
  have_alias_info = true;
4852
4876
4853
  timevar_pop (TV_TREE_PTA);
4877
  timevar_pop (TV_TREE_PTA);
4854
}
4878
}
4855
4879
4856
4857
/* Delete created points-to sets.  */
4880
/* Delete created points-to sets.  */
4858
4881
4859
void
4882
void
Lines 4861-4893 delete_points_to_sets (void) Link Here
4861
{
4884
{
4862
  varinfo_t v;
4885
  varinfo_t v;
4863
  int i;
4886
  int i;
4864
  
4887
4865
  htab_delete (id_for_tree);
4888
  if (dump_file && (dump_flags & TDF_STATS))
4866
  bitmap_obstack_release (&ptabitmap_obstack);
4889
    fprintf (dump_file, "Points to sets created:%d\n",
4867
  bitmap_obstack_release (&predbitmap_obstack);
4890
	     stats.points_to_sets_created);
4891
4892
  pointer_map_destroy (vi_for_tree);
4893
  bitmap_obstack_release (&pta_obstack);
4868
  VEC_free (constraint_t, heap, constraints);
4894
  VEC_free (constraint_t, heap, constraints);
4869
  
4895
4870
  for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4896
  for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4871
    {
4897
    VEC_free (constraint_t, heap, graph->complex[i]);
4872
      /* Nonlocal vars may add more varinfos.  */
4898
  free (graph->complex);
4873
      if (i >= graph_size)
4874
	break;
4875
4899
4876
      VEC_free (constraint_edge_t, heap, graph->succs[i]);
4900
  free (graph->rep);
4877
      VEC_free (constraint_edge_t, heap, graph->preds[i]);
4878
      VEC_free (constraint_t, heap, v->complex);
4879
    }
4880
  free (graph->zero_weight_preds);
4881
  free (graph->zero_weight_succs);
4882
  free (graph->succs);
4901
  free (graph->succs);
4883
  free (graph->preds);
4902
  free (graph->indirect_cycles);
4884
  free (graph);
4903
  free (graph);
4885
4904
4886
  VEC_free (varinfo_t, heap, varmap);
4905
  VEC_free (varinfo_t, heap, varmap);
4887
  free_alloc_pool (variable_info_pool);
4906
  free_alloc_pool (variable_info_pool);
4888
  free_alloc_pool (constraint_pool); 
4907
  free_alloc_pool (constraint_pool);
4889
  free_alloc_pool (constraint_edge_pool);
4890
4891
  have_alias_info = false;
4908
  have_alias_info = false;
4892
}
4909
}
4893
4910
Lines 4905-4910 gate_ipa_pta (void) Link Here
4905
static unsigned int
4922
static unsigned int
4906
ipa_pta_execute (void)
4923
ipa_pta_execute (void)
4907
{
4924
{
4925
#if 0
4908
  struct cgraph_node *node;
4926
  struct cgraph_node *node;
4909
  in_ipa_mode = 1;
4927
  in_ipa_mode = 1;
4910
  init_alias_heapvars ();
4928
  init_alias_heapvars ();
Lines 4994-4999 ipa_pta_execute (void) Link Here
4994
  in_ipa_mode = 0;
5012
  in_ipa_mode = 0;
4995
  delete_alias_heapvars ();
5013
  delete_alias_heapvars ();
4996
  delete_points_to_sets ();
5014
  delete_points_to_sets ();
5015
#endif
4997
  return 0;
5016
  return 0;
4998
}
5017
}
4999
  
5018
  
Lines 5018-5025 struct tree_opt_pass pass_ipa_pta = Link Here
5018
void
5037
void
5019
init_alias_heapvars (void)
5038
init_alias_heapvars (void)
5020
{
5039
{
5021
  heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5040
  if (!heapvar_for_stmt)
5022
				      NULL);
5041
    heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5042
					NULL);
5023
  nonlocal_all = NULL_TREE;
5043
  nonlocal_all = NULL_TREE;
5024
}
5044
}
5025
5045
Lines 5028-5034 delete_alias_heapvars (void) Link Here
5028
{
5048
{
5029
  nonlocal_all = NULL_TREE;
5049
  nonlocal_all = NULL_TREE;
5030
  htab_delete (heapvar_for_stmt);
5050
  htab_delete (heapvar_for_stmt);
5051
  heapvar_for_stmt = NULL;
5031
}
5052
}
5032
5033
  
5053
  
5034
#include "gt-tree-ssa-structalias.h"
5054
#include "gt-tree-ssa-structalias.h"

Return to bug 30052