OSDN Git Service

206c04bd484ddc6e6c855582baf4c24b237299ef
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-operands.c
1 /* SSA operands management for trees.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "flags.h"
26 #include "function.h"
27 #include "diagnostic.h"
28 #include "tree-flow.h"
29 #include "tree-inline.h"
30 #include "tree-pass.h"
31 #include "ggc.h"
32 #include "timevar.h"
33 #include "toplev.h"
34 #include "langhooks.h"
35 #include "ipa-reference.h"
36
37 /* This file contains the code required to manage the operands cache of the 
38    SSA optimizer.  For every stmt, we maintain an operand cache in the stmt 
39    annotation.  This cache contains operands that will be of interest to 
40    optimizers and other passes wishing to manipulate the IL. 
41
42    The operand type are broken up into REAL and VIRTUAL operands.  The real 
43    operands are represented as pointers into the stmt's operand tree.  Thus 
44    any manipulation of the real operands will be reflected in the actual tree.
45    Virtual operands are represented solely in the cache, although the base 
46    variable for the SSA_NAME may, or may not occur in the stmt's tree.  
47    Manipulation of the virtual operands will not be reflected in the stmt tree.
48
49    The routines in this file are concerned with creating this operand cache 
50    from a stmt tree.
51
52    The operand tree is the parsed by the various get_* routines which look 
53    through the stmt tree for the occurrence of operands which may be of 
54    interest, and calls are made to the append_* routines whenever one is 
55    found.  There are 4 of these routines, each representing one of the 
56    4 types of operands. Defs, Uses, Virtual Uses, and Virtual May Defs.
57
58    The append_* routines check for duplication, and simply keep a list of 
59    unique objects for each operand type in the build_* extendable vectors.
60
61    Once the stmt tree is completely parsed, the finalize_ssa_operands() 
62    routine is called, which proceeds to perform the finalization routine 
63    on each of the 4 operand vectors which have been built up.
64
65    If the stmt had a previous operand cache, the finalization routines 
66    attempt to match up the new operands with the old ones.  If it's a perfect 
67    match, the old vector is simply reused.  If it isn't a perfect match, then 
68    a new vector is created and the new operands are placed there.  For 
69    virtual operands, if the previous cache had SSA_NAME version of a 
70    variable, and that same variable occurs in the same operands cache, then 
71    the new cache vector will also get the same SSA_NAME.
72
73   i.e., if a stmt had a VUSE of 'a_5', and 'a' occurs in the new operand 
74   vector for VUSE, then the new vector will also be modified such that 
75   it contains 'a_5' rather than 'a'.  */
76
77
78 /* Structure storing statistics on how many call clobbers we have, and
79    how many where avoided.  */
80
81 static struct 
82 {
83   /* Number of call-clobbered ops we attempt to add to calls in
84      add_call_clobbered_mem_symbols.  */
85   unsigned int clobbered_vars;
86
87   /* Number of write-clobbers (VDEFs) avoided by using
88      not_written information.  */
89   unsigned int static_write_clobbers_avoided;
90
91   /* Number of reads (VUSEs) avoided by using not_read information.  */
92   unsigned int static_read_clobbers_avoided;
93   
94   /* Number of write-clobbers avoided because the variable can't escape to
95      this call.  */
96   unsigned int unescapable_clobbers_avoided;
97
98   /* Number of read-only uses we attempt to add to calls in
99      add_call_read_mem_symbols.  */
100   unsigned int readonly_clobbers;
101
102   /* Number of read-only uses we avoid using not_read information.  */
103   unsigned int static_readonly_clobbers_avoided;
104 } clobber_stats;
105
106
107 /* Flags to describe operand properties in helpers.  */
108
109 /* By default, operands are loaded.  */
110 #define opf_use         0
111
112 /* Operand is the target of an assignment expression or a 
113    call-clobbered variable.  */
114 #define opf_def         (1 << 0)
115
116 /* No virtual operands should be created in the expression.  This is used
117    when traversing ADDR_EXPR nodes which have different semantics than
118    other expressions.  Inside an ADDR_EXPR node, the only operands that we
119    need to consider are indices into arrays.  For instance, &a.b[i] should
120    generate a USE of 'i' but it should not generate a VUSE for 'a' nor a
121    VUSE for 'b'.  */
122 #define opf_no_vops     (1 << 1)
123
124 /* Operand is an implicit reference.  This is used to distinguish
125    explicit assignments in the form of GIMPLE_MODIFY_STMT from
126    clobbering sites like function calls or ASM_EXPRs.  */
127 #define opf_implicit    (1 << 2)
128
129 /* Array for building all the def operands.  */
130 static VEC(tree,heap) *build_defs;
131
132 /* Array for building all the use operands.  */
133 static VEC(tree,heap) *build_uses;
134
135 /* Set for building all the VDEF operands.  */
136 static VEC(tree,heap) *build_vdefs;
137
138 /* Set for building all the VUSE operands.  */
139 static VEC(tree,heap) *build_vuses;
140
141 /* Bitmap obstack for our datastructures that needs to survive across   
142    compilations of multiple functions.  */
143 static bitmap_obstack operands_bitmap_obstack;
144
145 /* Set for building all the loaded symbols.  */
146 static bitmap build_loads;
147
148 /* Set for building all the stored symbols.  */
149 static bitmap build_stores;
150
151 static void get_expr_operands (tree, tree *, int);
152
153 /* Number of functions with initialized ssa_operands.  */
154 static int n_initialized = 0;
155
156 /* Statement change buffer.  Data structure used to record state
157    information for statements.  This is used to determine what needs
158    to be done in order to update the SSA web after a statement is
159    modified by a pass.  If STMT is a statement that has just been
160    created, or needs to be folded via fold_stmt, or anything that
161    changes its physical structure then the pass should:
162
163    1- Call push_stmt_changes (&stmt) to record the current state of
164       STMT before any modifications are made.
165
166    2- Make all appropriate modifications to the statement.
167
168    3- Call pop_stmt_changes (&stmt) to find new symbols that
169       need to be put in SSA form, SSA name mappings for names that
170       have disappeared, recompute invariantness for address
171       expressions, cleanup EH information, etc.
172
173    If it is possible to determine that the statement was not modified,
174    instead of calling pop_stmt_changes it is quicker to call
175    discard_stmt_changes to avoid the expensive and unnecessary operand
176    re-scan and change comparison.  */
177
178 struct scb_d
179 {
180   /* Pointer to the statement being modified.  */
181   tree *stmt_p;
182
183   /* If the statement references memory these are the sets of symbols
184      loaded and stored by the statement.  */
185   bitmap loads;
186   bitmap stores;
187 };
188
189 typedef struct scb_d *scb_t;
190 DEF_VEC_P(scb_t);
191 DEF_VEC_ALLOC_P(scb_t,heap);
192
193 /* Stack of statement change buffers (SCB).  Every call to
194    push_stmt_changes pushes a new buffer onto the stack.  Calls to
195    pop_stmt_changes pop a buffer off of the stack and compute the set
196    of changes for the popped statement.  */
197 static VEC(scb_t,heap) *scb_stack;
198
199 /* Return the DECL_UID of the base variable of T.  */
200
201 static inline unsigned
202 get_name_decl (const_tree t)
203 {
204   if (TREE_CODE (t) != SSA_NAME)
205     return DECL_UID (t);
206   else
207     return DECL_UID (SSA_NAME_VAR (t));
208 }
209
210
211 /* Comparison function for qsort used in operand_build_sort_virtual.  */
212
213 static int
214 operand_build_cmp (const void *p, const void *q)
215 {
216   const_tree const e1 = *((const_tree const *)p);
217   const_tree const e2 = *((const_tree const *)q);
218   const unsigned int u1 = get_name_decl (e1);
219   const unsigned int u2 = get_name_decl (e2);
220
221   /* We want to sort in ascending order.  They can never be equal.  */
222 #ifdef ENABLE_CHECKING
223   gcc_assert (u1 != u2);
224 #endif
225   return (u1 > u2 ? 1 : -1);
226 }
227
228
229 /* Sort the virtual operands in LIST from lowest DECL_UID to highest.  */
230
231 static inline void
232 operand_build_sort_virtual (VEC(tree,heap) *list)
233 {
234   int num = VEC_length (tree, list);
235
236   if (num < 2)
237     return;
238
239   if (num == 2)
240     {
241       if (get_name_decl (VEC_index (tree, list, 0)) 
242           > get_name_decl (VEC_index (tree, list, 1)))
243         {  
244           /* Swap elements if in the wrong order.  */
245           tree tmp = VEC_index (tree, list, 0);
246           VEC_replace (tree, list, 0, VEC_index (tree, list, 1));
247           VEC_replace (tree, list, 1, tmp);
248         }
249       return;
250     }
251
252   /* There are 3 or more elements, call qsort.  */
253   qsort (VEC_address (tree, list), 
254          VEC_length (tree, list), 
255          sizeof (tree),
256          operand_build_cmp);
257 }
258
259
260 /*  Return true if the SSA operands cache is active.  */
261
262 bool
263 ssa_operands_active (void)
264 {
265   return cfun->gimple_df && gimple_ssa_operands (cfun)->ops_active;
266 }
267
268
269 /* VOPs are of variable sized, so the free list maps "free buckets" to the 
270    following table:  
271     bucket   # operands
272     ------   ----------
273         0       1
274         1       2
275           ...
276         15      16
277         16      17-24
278         17      25-32
279         18      31-40
280           ...
281         29      121-128
282    Any VOPs larger than this are simply added to the largest bucket when they
283    are freed.  */
284
285
286 /* Return the number of operands used in bucket BUCKET.  */
287
288 static inline int
289 vop_free_bucket_size (int bucket)
290 {
291 #ifdef ENABLE_CHECKING
292   gcc_assert (bucket >= 0 && bucket < NUM_VOP_FREE_BUCKETS);
293 #endif
294   if (bucket < 16)
295     return bucket + 1;
296   return (bucket - 13) * 8;
297 }
298
299
300 /* For a vop of NUM operands, return the bucket NUM belongs to.  If NUM is 
301    beyond the end of the bucket table, return -1.  */
302
303 static inline int 
304 vop_free_bucket_index (int num)
305 {
306   gcc_assert (num > 0 && NUM_VOP_FREE_BUCKETS > 16);
307
308   /* Sizes 1 through 16 use buckets 0-15.  */
309   if (num <= 16)
310     return num - 1;
311   /* Buckets 16 - NUM_VOP_FREE_BUCKETS represent 8 unit chunks.  */
312   num = 14 + (num - 1) / 8;
313   if (num >= NUM_VOP_FREE_BUCKETS)
314     return -1;
315   else
316     return num;
317 }
318
319
320 /* Initialize the VOP free buckets.  */
321
322 static inline void
323 init_vop_buckets (void)
324 {
325   int x;
326
327   for (x = 0; x < NUM_VOP_FREE_BUCKETS; x++)
328     gimple_ssa_operands (cfun)->vop_free_buckets[x] = NULL;
329 }
330
331
332 /* Add PTR to the appropriate VOP bucket.  */
333
334 static inline void
335 add_vop_to_freelist (voptype_p ptr)
336 {
337   int bucket = vop_free_bucket_index (VUSE_VECT_NUM_ELEM (ptr->usev));
338
339   /* Too large, use the largest bucket so its not a complete throw away.  */
340   if (bucket == -1)
341     bucket = NUM_VOP_FREE_BUCKETS - 1;
342
343   ptr->next = gimple_ssa_operands (cfun)->vop_free_buckets[bucket];
344   gimple_ssa_operands (cfun)->vop_free_buckets[bucket] = ptr;
345 }
346  
347
348 /* These are the sizes of the operand memory  buffer which gets allocated each 
349    time more operands space is required.  The final value is the amount that is
350    allocated every time after that.  */
351   
352 #define OP_SIZE_INIT    0
353 #define OP_SIZE_1       30
354 #define OP_SIZE_2       110
355 #define OP_SIZE_3       511
356
357 /* Initialize the operand cache routines.  */
358
359 void
360 init_ssa_operands (void)
361 {
362   if (!n_initialized++)
363     {
364       build_defs = VEC_alloc (tree, heap, 5);
365       build_uses = VEC_alloc (tree, heap, 10);
366       build_vuses = VEC_alloc (tree, heap, 25);
367       build_vdefs = VEC_alloc (tree, heap, 25);
368       bitmap_obstack_initialize (&operands_bitmap_obstack);
369       build_loads = BITMAP_ALLOC (&operands_bitmap_obstack);
370       build_stores = BITMAP_ALLOC (&operands_bitmap_obstack);
371       scb_stack = VEC_alloc (scb_t, heap, 20);
372     }
373
374   gcc_assert (gimple_ssa_operands (cfun)->operand_memory == NULL);
375   gcc_assert (gimple_ssa_operands (cfun)->mpt_table == NULL);
376   gimple_ssa_operands (cfun)->operand_memory_index
377      = gimple_ssa_operands (cfun)->ssa_operand_mem_size;
378   gimple_ssa_operands (cfun)->ops_active = true;
379   memset (&clobber_stats, 0, sizeof (clobber_stats));
380   init_vop_buckets ();
381   gimple_ssa_operands (cfun)->ssa_operand_mem_size = OP_SIZE_INIT;
382 }
383
384
385 /* Dispose of anything required by the operand routines.  */
386
387 void
388 fini_ssa_operands (void)
389 {
390   struct ssa_operand_memory_d *ptr;
391   unsigned ix;
392   tree mpt;
393
394   if (!--n_initialized)
395     {
396       VEC_free (tree, heap, build_defs);
397       VEC_free (tree, heap, build_uses);
398       VEC_free (tree, heap, build_vdefs);
399       VEC_free (tree, heap, build_vuses);
400       BITMAP_FREE (build_loads);
401       BITMAP_FREE (build_stores);
402
403       /* The change buffer stack had better be empty.  */
404       gcc_assert (VEC_length (scb_t, scb_stack) == 0);
405       VEC_free (scb_t, heap, scb_stack);
406       scb_stack = NULL;
407     }
408
409   gimple_ssa_operands (cfun)->free_defs = NULL;
410   gimple_ssa_operands (cfun)->free_uses = NULL;
411
412   while ((ptr = gimple_ssa_operands (cfun)->operand_memory) != NULL)
413     {
414       gimple_ssa_operands (cfun)->operand_memory
415         = gimple_ssa_operands (cfun)->operand_memory->next;
416       ggc_free (ptr);
417     }
418
419   for (ix = 0;
420        VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, ix, mpt);
421        ix++)
422     {
423       if (mpt)
424         BITMAP_FREE (MPT_SYMBOLS (mpt));
425     }
426
427   VEC_free (tree, heap, gimple_ssa_operands (cfun)->mpt_table);
428
429   gimple_ssa_operands (cfun)->ops_active = false;
430
431   if (!n_initialized)
432     bitmap_obstack_release (&operands_bitmap_obstack);
433   if (dump_file && (dump_flags & TDF_STATS))
434     {
435       fprintf (dump_file, "Original clobbered vars:           %d\n",
436                clobber_stats.clobbered_vars);
437       fprintf (dump_file, "Static write clobbers avoided:     %d\n",
438                clobber_stats.static_write_clobbers_avoided);
439       fprintf (dump_file, "Static read clobbers avoided:      %d\n",
440                clobber_stats.static_read_clobbers_avoided);
441       fprintf (dump_file, "Unescapable clobbers avoided:      %d\n",
442                clobber_stats.unescapable_clobbers_avoided);
443       fprintf (dump_file, "Original read-only clobbers:       %d\n",
444                clobber_stats.readonly_clobbers);
445       fprintf (dump_file, "Static read-only clobbers avoided: %d\n",
446                clobber_stats.static_readonly_clobbers_avoided);
447     }
448 }
449
450
451 /* Return memory for operands of SIZE chunks.  */
452                                                                               
453 static inline void *
454 ssa_operand_alloc (unsigned size)
455 {
456   char *ptr;
457
458   if (gimple_ssa_operands (cfun)->operand_memory_index + size
459       >= gimple_ssa_operands (cfun)->ssa_operand_mem_size)
460     {
461       struct ssa_operand_memory_d *ptr;
462
463       if (gimple_ssa_operands (cfun)->ssa_operand_mem_size == OP_SIZE_INIT)
464         gimple_ssa_operands (cfun)->ssa_operand_mem_size
465            = OP_SIZE_1 * sizeof (struct voptype_d);
466       else
467         if (gimple_ssa_operands (cfun)->ssa_operand_mem_size
468             == OP_SIZE_1 * sizeof (struct voptype_d))
469           gimple_ssa_operands (cfun)->ssa_operand_mem_size
470              = OP_SIZE_2 * sizeof (struct voptype_d);
471         else
472           gimple_ssa_operands (cfun)->ssa_operand_mem_size
473              = OP_SIZE_3 * sizeof (struct voptype_d);
474
475       /* Go right to the maximum size if the request is too large.  */
476       if (size > gimple_ssa_operands (cfun)->ssa_operand_mem_size)
477         gimple_ssa_operands (cfun)->ssa_operand_mem_size
478           = OP_SIZE_3 * sizeof (struct voptype_d);
479
480       /* Fail if there is not enough space.  If there are this many operands
481          required, first make sure there isn't a different problem causing this
482          many operands.  If the decision is that this is OK, then we can 
483          specially allocate a buffer just for this request.  */
484       gcc_assert (size <= gimple_ssa_operands (cfun)->ssa_operand_mem_size);
485
486       ptr = (struct ssa_operand_memory_d *) 
487               ggc_alloc (sizeof (struct ssa_operand_memory_d) 
488                          + gimple_ssa_operands (cfun)->ssa_operand_mem_size - 1);
489       ptr->next = gimple_ssa_operands (cfun)->operand_memory;
490       gimple_ssa_operands (cfun)->operand_memory = ptr;
491       gimple_ssa_operands (cfun)->operand_memory_index = 0;
492     }
493   ptr = &(gimple_ssa_operands (cfun)->operand_memory
494           ->mem[gimple_ssa_operands (cfun)->operand_memory_index]);
495   gimple_ssa_operands (cfun)->operand_memory_index += size;
496   return ptr;
497 }
498
499
500 /* Allocate a DEF operand.  */
501
502 static inline struct def_optype_d *
503 alloc_def (void)
504 {
505   struct def_optype_d *ret;
506   if (gimple_ssa_operands (cfun)->free_defs)
507     {
508       ret = gimple_ssa_operands (cfun)->free_defs;
509       gimple_ssa_operands (cfun)->free_defs
510         = gimple_ssa_operands (cfun)->free_defs->next;
511     }
512   else
513     ret = (struct def_optype_d *)
514           ssa_operand_alloc (sizeof (struct def_optype_d));
515   return ret;
516 }
517
518
519 /* Allocate a USE operand.  */
520
521 static inline struct use_optype_d *
522 alloc_use (void)
523 {
524   struct use_optype_d *ret;
525   if (gimple_ssa_operands (cfun)->free_uses)
526     {
527       ret = gimple_ssa_operands (cfun)->free_uses;
528       gimple_ssa_operands (cfun)->free_uses
529         = gimple_ssa_operands (cfun)->free_uses->next;
530     }
531   else
532     ret = (struct use_optype_d *)
533           ssa_operand_alloc (sizeof (struct use_optype_d));
534   return ret;
535 }
536
537
538 /* Allocate a vop with NUM elements.  */
539
540 static inline struct voptype_d *
541 alloc_vop (int num)
542 {
543   struct voptype_d *ret = NULL;
544   int alloc_size = 0;
545
546   int bucket = vop_free_bucket_index (num);
547   if (bucket != -1)
548     {
549       /* If there is a free operand, use it.  */
550       if (gimple_ssa_operands (cfun)->vop_free_buckets[bucket] != NULL)
551         {
552           ret = gimple_ssa_operands (cfun)->vop_free_buckets[bucket];
553           gimple_ssa_operands (cfun)->vop_free_buckets[bucket] = 
554                   gimple_ssa_operands (cfun)->vop_free_buckets[bucket]->next;
555         }
556       else
557         alloc_size = vop_free_bucket_size(bucket);
558     }
559   else
560     alloc_size = num;
561
562   if (alloc_size > 0)
563     ret = (struct voptype_d *)ssa_operand_alloc (
564         sizeof (struct voptype_d) + (alloc_size - 1) * sizeof (vuse_element_t));
565
566   VUSE_VECT_NUM_ELEM (ret->usev) = num;
567   return ret;
568 }
569
570
571 /* This routine makes sure that PTR is in an immediate use list, and makes
572    sure the stmt pointer is set to the current stmt.  */
573
574 static inline void
575 set_virtual_use_link (use_operand_p ptr, tree stmt)
576 {
577   /*  fold_stmt may have changed the stmt pointers.  */
578   if (ptr->stmt != stmt)
579     ptr->stmt = stmt;
580
581   /* If this use isn't in a list, add it to the correct list.  */
582   if (!ptr->prev)
583     link_imm_use (ptr, *(ptr->use));
584 }
585
586
587 /* Adds OP to the list of defs after LAST.  */
588
589 static inline def_optype_p 
590 add_def_op (tree *op, def_optype_p last)
591 {
592   def_optype_p new_def;
593
594   new_def = alloc_def ();
595   DEF_OP_PTR (new_def) = op;
596   last->next = new_def;
597   new_def->next = NULL;
598   return new_def;
599 }
600
601
602 /* Adds OP to the list of uses of statement STMT after LAST.  */
603
604 static inline use_optype_p
605 add_use_op (tree stmt, tree *op, use_optype_p last)
606 {
607   use_optype_p new_use;
608
609   new_use = alloc_use ();
610   USE_OP_PTR (new_use)->use = op;
611   link_imm_use_stmt (USE_OP_PTR (new_use), *op, stmt);
612   last->next = new_use;
613   new_use->next = NULL;
614   return new_use;
615 }
616
617
618 /* Return a virtual op pointer with NUM elements which are all initialized to OP
619    and are linked into the immediate uses for STMT.  The new vop is appended
620    after PREV.  */
621
622 static inline voptype_p
623 add_vop (tree stmt, tree op, int num, voptype_p prev)
624 {
625   voptype_p new_vop;
626   int x;
627
628   new_vop = alloc_vop (num);
629   for (x = 0; x < num; x++)
630     {
631       VUSE_OP_PTR (new_vop, x)->prev = NULL;
632       SET_VUSE_OP (new_vop, x, op);
633       VUSE_OP_PTR (new_vop, x)->use = &new_vop->usev.uses[x].use_var;
634       link_imm_use_stmt (VUSE_OP_PTR (new_vop, x),
635                          new_vop->usev.uses[x].use_var, stmt);
636     }
637
638   if (prev)
639     prev->next = new_vop;
640   new_vop->next = NULL;
641   return new_vop;
642 }
643
644
645 /* Adds OP to the list of vuses of statement STMT after LAST, and moves
646    LAST to the new element.  */
647
648 static inline voptype_p
649 add_vuse_op (tree stmt, tree op, int num, voptype_p last)
650 {
651   voptype_p new_vop = add_vop (stmt, op, num, last);
652   VDEF_RESULT (new_vop) = NULL_TREE;
653   return new_vop;
654 }
655
656
657 /* Adds OP to the list of vdefs of statement STMT after LAST, and moves
658    LAST to the new element.  */
659
660 static inline voptype_p
661 add_vdef_op (tree stmt, tree op, int num, voptype_p last)
662 {
663   voptype_p new_vop = add_vop (stmt, op, num, last);
664   VDEF_RESULT (new_vop) = op;
665   return new_vop;
666 }
667   
668
669 /* Takes elements from build_defs and turns them into def operands of STMT.
670    TODO -- Make build_defs VEC of tree *.  */
671
672 static inline void
673 finalize_ssa_defs (tree stmt)
674 {
675   unsigned new_i;
676   struct def_optype_d new_list;
677   def_optype_p old_ops, last;
678   unsigned int num = VEC_length (tree, build_defs);
679
680   /* There should only be a single real definition per assignment.  */
681   gcc_assert ((stmt && TREE_CODE (stmt) != GIMPLE_MODIFY_STMT) || num <= 1);
682
683   new_list.next = NULL;
684   last = &new_list;
685
686   old_ops = DEF_OPS (stmt);
687
688   new_i = 0;
689
690   /* Check for the common case of 1 def that hasn't changed.  */
691   if (old_ops && old_ops->next == NULL && num == 1
692       && (tree *) VEC_index (tree, build_defs, 0) == DEF_OP_PTR (old_ops))
693     return;
694
695   /* If there is anything in the old list, free it.  */
696   if (old_ops)
697     {
698       old_ops->next = gimple_ssa_operands (cfun)->free_defs;
699       gimple_ssa_operands (cfun)->free_defs = old_ops;
700     }
701
702   /* If there is anything remaining in the build_defs list, simply emit it.  */
703   for ( ; new_i < num; new_i++)
704     last = add_def_op ((tree *) VEC_index (tree, build_defs, new_i), last);
705
706   /* Now set the stmt's operands.  */
707   DEF_OPS (stmt) = new_list.next;
708
709 #ifdef ENABLE_CHECKING
710   {
711     def_optype_p ptr;
712     unsigned x = 0;
713     for (ptr = DEF_OPS (stmt); ptr; ptr = ptr->next)
714       x++;
715
716     gcc_assert (x == num);
717   }
718 #endif
719 }
720
721
722 /* Takes elements from build_uses and turns them into use operands of STMT.
723    TODO -- Make build_uses VEC of tree *.  */
724
725 static inline void
726 finalize_ssa_uses (tree stmt)
727 {
728   unsigned new_i;
729   struct use_optype_d new_list;
730   use_optype_p old_ops, ptr, last;
731
732 #ifdef ENABLE_CHECKING
733   {
734     unsigned x;
735     unsigned num = VEC_length (tree, build_uses);
736
737     /* If the pointer to the operand is the statement itself, something is
738        wrong.  It means that we are pointing to a local variable (the 
739        initial call to update_stmt_operands does not pass a pointer to a 
740        statement).  */
741     for (x = 0; x < num; x++)
742       gcc_assert (*((tree *)VEC_index (tree, build_uses, x)) != stmt);
743   }
744 #endif
745
746   new_list.next = NULL;
747   last = &new_list;
748
749   old_ops = USE_OPS (stmt);
750
751   /* If there is anything in the old list, free it.  */
752   if (old_ops)
753     {
754       for (ptr = old_ops; ptr; ptr = ptr->next)
755         delink_imm_use (USE_OP_PTR (ptr));
756       old_ops->next = gimple_ssa_operands (cfun)->free_uses;
757       gimple_ssa_operands (cfun)->free_uses = old_ops;
758     }
759
760   /* Now create nodes for all the new nodes.  */
761   for (new_i = 0; new_i < VEC_length (tree, build_uses); new_i++)
762     last = add_use_op (stmt, 
763                        (tree *) VEC_index (tree, build_uses, new_i), 
764                        last);
765
766   /* Now set the stmt's operands.  */
767   USE_OPS (stmt) = new_list.next;
768
769 #ifdef ENABLE_CHECKING
770   {
771     unsigned x = 0;
772     for (ptr = USE_OPS (stmt); ptr; ptr = ptr->next)
773       x++;
774
775     gcc_assert (x == VEC_length (tree, build_uses));
776   }
777 #endif
778 }
779
780
781 /* Takes elements from BUILD_VDEFS and turns them into vdef operands of
782    STMT.  FIXME, for now VDEF operators should have a single operand
783    in their RHS.  */
784
785 static inline void
786 finalize_ssa_vdefs (tree stmt)
787 {
788   unsigned new_i;
789   struct voptype_d new_list;
790   voptype_p old_ops, ptr, last;
791   stmt_ann_t ann = stmt_ann (stmt);
792
793   /* Set the symbols referenced by STMT.  */
794   if (!bitmap_empty_p (build_stores))
795     {
796       if (ann->operands.stores == NULL)
797         ann->operands.stores = BITMAP_ALLOC (&operands_bitmap_obstack);
798
799       bitmap_copy (ann->operands.stores, build_stores);
800     }
801   else
802     BITMAP_FREE (ann->operands.stores);
803
804   /* If aliases have not been computed, do not instantiate a virtual
805      operator on STMT.  Initially, we only compute the SSA form on
806      GIMPLE registers.  The virtual SSA form is only computed after
807      alias analysis, so virtual operators will remain unrenamed and
808      the verifier will complain.  However, alias analysis needs to
809      access symbol load/store information, so we need to compute
810      those.  */
811   if (!gimple_aliases_computed_p (cfun))
812     return;
813
814   new_list.next = NULL;
815   last = &new_list;
816
817   old_ops = VDEF_OPS (stmt);
818   new_i = 0;
819   while (old_ops && new_i < VEC_length (tree, build_vdefs))
820     {
821       tree op = VEC_index (tree, build_vdefs, new_i);
822       unsigned new_uid = get_name_decl (op);
823       unsigned old_uid = get_name_decl (VDEF_RESULT (old_ops));
824
825       /* FIXME, for now each VDEF operator should have at most one
826          operand in their RHS.  */
827       gcc_assert (VDEF_NUM (old_ops) == 1);
828
829       if (old_uid == new_uid)
830         {
831           /* If the symbols are the same, reuse the existing operand.  */
832           last->next = old_ops;
833           last = old_ops;
834           old_ops = old_ops->next;
835           last->next = NULL;
836           set_virtual_use_link (VDEF_OP_PTR (last, 0), stmt);
837           new_i++;
838         }
839       else if (old_uid < new_uid)
840         {
841           /* If old is less than new, old goes to the free list.  */
842           voptype_p next;
843           delink_imm_use (VDEF_OP_PTR (old_ops, 0));
844           next = old_ops->next;
845           add_vop_to_freelist (old_ops);
846           old_ops = next;
847         }
848       else
849         {
850           /* This is a new operand.  */
851           last = add_vdef_op (stmt, op, 1, last);
852           new_i++;
853         }
854     }
855
856   /* If there is anything remaining in BUILD_VDEFS, simply emit it.  */
857   for ( ; new_i < VEC_length (tree, build_vdefs); new_i++)
858     last = add_vdef_op (stmt, VEC_index (tree, build_vdefs, new_i), 1, last);
859
860   /* If there is anything in the old list, free it.  */
861   if (old_ops)
862     {
863       for (ptr = old_ops; ptr; ptr = last)
864         {
865           last = ptr->next;
866           delink_imm_use (VDEF_OP_PTR (ptr, 0));
867           add_vop_to_freelist (ptr);
868         }
869     }
870
871   /* Now set STMT's operands.  */
872   VDEF_OPS (stmt) = new_list.next;
873
874 #ifdef ENABLE_CHECKING
875   {
876     unsigned x = 0;
877     for (ptr = VDEF_OPS (stmt); ptr; ptr = ptr->next)
878       x++;
879
880     gcc_assert (x == VEC_length (tree, build_vdefs));
881   }
882 #endif
883 }
884
885
886 /* Takes elements from BUILD_VUSES and turns them into VUSE operands of
887    STMT.  */
888
889 static inline void
890 finalize_ssa_vuse_ops (tree stmt)
891 {
892   unsigned new_i, old_i;
893   voptype_p old_ops, last;
894   VEC(tree,heap) *new_ops;
895   stmt_ann_t ann;
896
897   /* Set the symbols referenced by STMT.  */
898   ann = stmt_ann (stmt);
899   if (!bitmap_empty_p (build_loads))
900     {
901       if (ann->operands.loads == NULL)
902         ann->operands.loads = BITMAP_ALLOC (&operands_bitmap_obstack);
903
904       bitmap_copy (ann->operands.loads, build_loads);
905     }
906   else
907     BITMAP_FREE (ann->operands.loads);
908
909   /* If aliases have not been computed, do not instantiate a virtual
910      operator on STMT.  Initially, we only compute the SSA form on
911      GIMPLE registers.  The virtual SSA form is only computed after
912      alias analysis, so virtual operators will remain unrenamed and
913      the verifier will complain.  However, alias analysis needs to
914      access symbol load/store information, so we need to compute
915      those.  */
916   if (!gimple_aliases_computed_p (cfun))
917     return;
918
919   /* STMT should have at most one VUSE operator.  */
920   old_ops = VUSE_OPS (stmt);
921   gcc_assert (old_ops == NULL || old_ops->next == NULL);
922
923   new_ops = NULL;
924   new_i = old_i = 0;
925   while (old_ops
926          && old_i < VUSE_NUM (old_ops)
927          && new_i < VEC_length (tree, build_vuses))
928     {
929       tree new_op = VEC_index (tree, build_vuses, new_i);
930       tree old_op = VUSE_OP (old_ops, old_i);
931       unsigned new_uid = get_name_decl (new_op);
932       unsigned old_uid = get_name_decl (old_op);
933
934       if (old_uid == new_uid)
935         {
936           /* If the symbols are the same, reuse the existing operand.  */
937           VEC_safe_push (tree, heap, new_ops, old_op);
938           new_i++;
939           old_i++;
940         }
941       else if (old_uid < new_uid)
942         {
943           /* If OLD_UID is less than NEW_UID, the old operand has
944              disappeared, skip to the next old operand.  */
945           old_i++;
946         }
947       else
948         {
949           /* This is a new operand.  */
950           VEC_safe_push (tree, heap, new_ops, new_op);
951           new_i++;
952         }
953     }
954
955   /* If there is anything remaining in the build_vuses list, simply emit it.  */
956   for ( ; new_i < VEC_length (tree, build_vuses); new_i++)
957     VEC_safe_push (tree, heap, new_ops, VEC_index (tree, build_vuses, new_i));
958
959   /* If there is anything in the old list, free it.  */
960   if (old_ops)
961     {
962       for (old_i = 0; old_i < VUSE_NUM (old_ops); old_i++)
963         delink_imm_use (VUSE_OP_PTR (old_ops, old_i));
964       add_vop_to_freelist (old_ops);
965       VUSE_OPS (stmt) = NULL;
966     }
967
968   /* If there are any operands, instantiate a VUSE operator for STMT.  */
969   if (new_ops)
970     {
971       tree op;
972       unsigned i;
973
974       last = add_vuse_op (stmt, NULL, VEC_length (tree, new_ops), NULL);
975
976       for (i = 0; VEC_iterate (tree, new_ops, i, op); i++)
977         SET_USE (VUSE_OP_PTR (last, (int) i), op);
978
979       VUSE_OPS (stmt) = last;
980       VEC_free (tree, heap, new_ops);
981     }
982
983 #ifdef ENABLE_CHECKING
984   {
985     unsigned x;
986     
987     if (VUSE_OPS (stmt))
988       {
989         gcc_assert (VUSE_OPS (stmt)->next == NULL);
990         x = VUSE_NUM (VUSE_OPS (stmt));
991       }
992     else
993       x = 0;
994
995     gcc_assert (x == VEC_length (tree, build_vuses));
996   }
997 #endif
998 }
999
1000 /* Return a new VUSE operand vector for STMT.  */
1001                                                                               
1002 static void
1003 finalize_ssa_vuses (tree stmt)
1004 {
1005   unsigned num, num_vdefs;
1006   unsigned vuse_index;
1007
1008   /* Remove superfluous VUSE operands.  If the statement already has a
1009      VDEF operator for a variable 'a', then a VUSE for 'a' is not
1010      needed because VDEFs imply a VUSE of the variable.  For instance,
1011      suppose that variable 'a' is pointed-to by p and q:
1012
1013               # VUSE <a_2>
1014               # a_3 = VDEF <a_2>
1015               *p = *q;
1016
1017      The VUSE <a_2> is superfluous because it is implied by the
1018      VDEF operator.  */
1019   num = VEC_length (tree, build_vuses);
1020   num_vdefs = VEC_length (tree, build_vdefs);
1021
1022   if (num > 0 && num_vdefs > 0)
1023     for (vuse_index = 0; vuse_index < VEC_length (tree, build_vuses); )
1024       {
1025         tree vuse;
1026         vuse = VEC_index (tree, build_vuses, vuse_index);
1027         if (TREE_CODE (vuse) != SSA_NAME)
1028           {
1029             var_ann_t ann = var_ann (vuse);
1030             ann->in_vuse_list = 0;
1031             if (ann->in_vdef_list)
1032               {
1033                 VEC_ordered_remove (tree, build_vuses, vuse_index);
1034                 continue;
1035               }
1036           }
1037         vuse_index++;
1038       }
1039
1040   finalize_ssa_vuse_ops (stmt);
1041 }
1042
1043
1044 /* Clear the in_list bits and empty the build array for VDEFs and
1045    VUSEs.  */
1046
1047 static inline void
1048 cleanup_build_arrays (void)
1049 {
1050   unsigned i;
1051   tree t;
1052
1053   for (i = 0; VEC_iterate (tree, build_vdefs, i, t); i++)
1054     if (TREE_CODE (t) != SSA_NAME)
1055       var_ann (t)->in_vdef_list = false;
1056
1057   for (i = 0; VEC_iterate (tree, build_vuses, i, t); i++)
1058     if (TREE_CODE (t) != SSA_NAME)
1059       var_ann (t)->in_vuse_list = false;
1060
1061   VEC_truncate (tree, build_vdefs, 0);
1062   VEC_truncate (tree, build_vuses, 0);
1063   VEC_truncate (tree, build_defs, 0);
1064   VEC_truncate (tree, build_uses, 0);
1065   bitmap_clear (build_loads);
1066   bitmap_clear (build_stores);
1067 }
1068
1069
1070 /* Finalize all the build vectors, fill the new ones into INFO.  */
1071                                                                               
1072 static inline void
1073 finalize_ssa_stmt_operands (tree stmt)
1074 {
1075   finalize_ssa_defs (stmt);
1076   finalize_ssa_uses (stmt);
1077   finalize_ssa_vdefs (stmt);
1078   finalize_ssa_vuses (stmt);
1079   cleanup_build_arrays ();
1080 }
1081
1082
1083 /* Start the process of building up operands vectors in INFO.  */
1084
1085 static inline void
1086 start_ssa_stmt_operands (void)
1087 {
1088   gcc_assert (VEC_length (tree, build_defs) == 0);
1089   gcc_assert (VEC_length (tree, build_uses) == 0);
1090   gcc_assert (VEC_length (tree, build_vuses) == 0);
1091   gcc_assert (VEC_length (tree, build_vdefs) == 0);
1092   gcc_assert (bitmap_empty_p (build_loads));
1093   gcc_assert (bitmap_empty_p (build_stores));
1094 }
1095
1096
1097 /* Add DEF_P to the list of pointers to operands.  */
1098
1099 static inline void
1100 append_def (tree *def_p)
1101 {
1102   VEC_safe_push (tree, heap, build_defs, (tree) def_p);
1103 }
1104
1105
1106 /* Add USE_P to the list of pointers to operands.  */
1107
1108 static inline void
1109 append_use (tree *use_p)
1110 {
1111   VEC_safe_push (tree, heap, build_uses, (tree) use_p);
1112 }
1113
1114
1115 /* Add VAR to the set of variables that require a VDEF operator.  */
1116
1117 static inline void
1118 append_vdef (tree var)
1119 {
1120   tree sym;
1121
1122   if (TREE_CODE (var) != SSA_NAME)
1123     {
1124       tree mpt;
1125       var_ann_t ann;
1126
1127       /* If VAR belongs to a memory partition, use it instead of VAR.  */
1128       mpt = memory_partition (var);
1129       if (mpt)
1130         var = mpt;
1131
1132       /* Don't allow duplicate entries.  */
1133       ann = get_var_ann (var);
1134       if (ann->in_vdef_list)
1135         return;
1136
1137       ann->in_vdef_list = true;
1138       sym = var;
1139     }
1140   else
1141     sym = SSA_NAME_VAR (var);
1142
1143   VEC_safe_push (tree, heap, build_vdefs, var);
1144   bitmap_set_bit (build_stores, DECL_UID (sym));
1145 }
1146
1147
1148 /* Add VAR to the set of variables that require a VUSE operator.  */
1149
1150 static inline void
1151 append_vuse (tree var)
1152 {
1153   tree sym;
1154
1155   if (TREE_CODE (var) != SSA_NAME)
1156     {
1157       tree mpt;
1158       var_ann_t ann;
1159
1160       /* If VAR belongs to a memory partition, use it instead of VAR.  */
1161       mpt = memory_partition (var);
1162       if (mpt)
1163         var = mpt;
1164
1165       /* Don't allow duplicate entries.  */
1166       ann = get_var_ann (var);
1167       if (ann->in_vuse_list)
1168         return;
1169       else if (ann->in_vdef_list)
1170        {
1171          /* We don't want a vuse if we already have a vdef, but we must
1172             still put this in build_loads.  */
1173          bitmap_set_bit (build_loads, DECL_UID (var));
1174          return;
1175        }
1176
1177       ann->in_vuse_list = true;
1178       sym = var;
1179     }
1180   else
1181     sym = SSA_NAME_VAR (var);
1182
1183   VEC_safe_push (tree, heap, build_vuses, var);
1184   bitmap_set_bit (build_loads, DECL_UID (sym));
1185 }
1186
1187
1188 /* REF is a tree that contains the entire pointer dereference
1189    expression, if available, or NULL otherwise.  ALIAS is the variable
1190    we are asking if REF can access.  OFFSET and SIZE come from the
1191    memory access expression that generated this virtual operand.
1192
1193    XXX: We should handle the NO_ALIAS attributes here.  */
1194
1195 static bool
1196 access_can_touch_variable (tree ref, tree alias, HOST_WIDE_INT offset,
1197                            HOST_WIDE_INT size)
1198 {
1199   bool offsetgtz = offset > 0;
1200   unsigned HOST_WIDE_INT uoffset = (unsigned HOST_WIDE_INT) offset;
1201   tree base = ref ? get_base_address (ref) : NULL;
1202
1203   /* If ALIAS is .GLOBAL_VAR then the memory reference REF must be
1204      using a call-clobbered memory tag.  By definition, call-clobbered
1205      memory tags can always touch .GLOBAL_VAR.  */
1206   if (alias == gimple_global_var (cfun))
1207     return true;
1208
1209   /* If ref is a TARGET_MEM_REF, just return true, as we can't really
1210      disambiguate them right now.  */
1211   if (ref && TREE_CODE (ref) == TARGET_MEM_REF)
1212     return true;
1213   
1214   /* If ALIAS is an SFT, it can't be touched if the offset     
1215      and size of the access is not overlapping with the SFT offset and
1216      size.  This is only true if we are accessing through a pointer
1217      to a type that is the same as SFT_PARENT_VAR.  Otherwise, we may
1218      be accessing through a pointer to some substruct of the
1219      structure, and if we try to prune there, we will have the wrong
1220      offset, and get the wrong answer.
1221      i.e., we can't prune without more work if we have something like
1222
1223      struct gcc_target
1224      {
1225        struct asm_out
1226        {
1227          const char *byte_op;
1228          struct asm_int_op
1229          {    
1230            const char *hi;
1231          } aligned_op;
1232        } asm_out;
1233      } targetm;
1234      
1235      foo = &targetm.asm_out.aligned_op;
1236      return foo->hi;
1237
1238      SFT.1, which represents hi, will have SFT_OFFSET=32 because in
1239      terms of SFT_PARENT_VAR, that is where it is.
1240      However, the access through the foo pointer will be at offset 0.  */
1241   if (size != -1
1242       && TREE_CODE (alias) == STRUCT_FIELD_TAG
1243       && base
1244       && TREE_TYPE (base) == TREE_TYPE (SFT_PARENT_VAR (alias))
1245       && !overlap_subvar (offset, size, alias, NULL))
1246     {
1247 #ifdef ACCESS_DEBUGGING
1248       fprintf (stderr, "Access to ");
1249       print_generic_expr (stderr, ref, 0);
1250       fprintf (stderr, " may not touch ");
1251       print_generic_expr (stderr, alias, 0);
1252       fprintf (stderr, " in function %s\n", get_name (current_function_decl));
1253 #endif
1254       return false;
1255     }
1256
1257   /* Without strict aliasing, it is impossible for a component access
1258      through a pointer to touch a random variable, unless that
1259      variable *is* a structure or a pointer.
1260
1261      That is, given p->c, and some random global variable b,
1262      there is no legal way that p->c could be an access to b.
1263      
1264      Without strict aliasing on, we consider it legal to do something
1265      like:
1266
1267      struct foos { int l; };
1268      int foo;
1269      static struct foos *getfoo(void);
1270      int main (void)
1271      {
1272        struct foos *f = getfoo();
1273        f->l = 1;
1274        foo = 2;
1275        if (f->l == 1)
1276          abort();
1277        exit(0);
1278      }
1279      static struct foos *getfoo(void)     
1280      { return (struct foos *)&foo; }
1281      
1282      (taken from 20000623-1.c)
1283
1284      The docs also say/imply that access through union pointers
1285      is legal (but *not* if you take the address of the union member,
1286      i.e. the inverse), such that you can do
1287
1288      typedef union {
1289        int d;
1290      } U;
1291
1292      int rv;
1293      void breakme()
1294      {
1295        U *rv0;
1296        U *pretmp = (U*)&rv;
1297        rv0 = pretmp;
1298        rv0->d = 42;    
1299      }
1300      To implement this, we just punt on accesses through union
1301      pointers entirely.
1302
1303      Another case we have to allow is accessing a variable
1304      through an array access at offset zero.  This happens from
1305      code generated by the fortran frontend like
1306
1307      char[1:1] & my_char_ref;
1308      char my_char;
1309      my_char_ref_1 = (char[1:1] &) &my_char;
1310      D.874_2 = (*my_char_ref_1)[1]{lb: 1 sz: 1};
1311   */
1312   else if (ref 
1313            && flag_strict_aliasing
1314            && TREE_CODE (ref) != INDIRECT_REF
1315            && !MTAG_P (alias)
1316            && base
1317            && (TREE_CODE (base) != INDIRECT_REF
1318                || TREE_CODE (TREE_TYPE (base)) != UNION_TYPE)
1319            && (TREE_CODE (base) != INDIRECT_REF
1320                || TREE_CODE (ref) != ARRAY_REF
1321                || offset != 0
1322                || (DECL_SIZE (alias)
1323                    && TREE_CODE (DECL_SIZE (alias)) == INTEGER_CST
1324                    && size != -1
1325                    && (unsigned HOST_WIDE_INT)size
1326                       != TREE_INT_CST_LOW (DECL_SIZE (alias))))
1327            && !AGGREGATE_TYPE_P (TREE_TYPE (alias))
1328            && TREE_CODE (TREE_TYPE (alias)) != COMPLEX_TYPE
1329            && !var_ann (alias)->is_heapvar
1330            /* When the struct has may_alias attached to it, we need not to
1331               return true.  */
1332            && get_alias_set (base))
1333     {
1334 #ifdef ACCESS_DEBUGGING
1335       fprintf (stderr, "Access to ");
1336       print_generic_expr (stderr, ref, 0);
1337       fprintf (stderr, " may not touch ");
1338       print_generic_expr (stderr, alias, 0);
1339       fprintf (stderr, " in function %s\n", get_name (current_function_decl));
1340 #endif
1341       return false;
1342     }
1343
1344   /* If the offset of the access is greater than the size of one of
1345      the possible aliases, it can't be touching that alias, because it
1346      would be past the end of the structure.  */
1347   else if (ref
1348            && flag_strict_aliasing
1349            && TREE_CODE (ref) != INDIRECT_REF
1350            && !MTAG_P (alias)
1351            && !POINTER_TYPE_P (TREE_TYPE (alias))
1352            && offsetgtz
1353            && DECL_SIZE (alias)
1354            && TREE_CODE (DECL_SIZE (alias)) == INTEGER_CST
1355            && uoffset > TREE_INT_CST_LOW (DECL_SIZE (alias)))
1356     {
1357 #ifdef ACCESS_DEBUGGING
1358       fprintf (stderr, "Access to ");
1359       print_generic_expr (stderr, ref, 0);
1360       fprintf (stderr, " may not touch ");
1361       print_generic_expr (stderr, alias, 0);
1362       fprintf (stderr, " in function %s\n", get_name (current_function_decl));
1363 #endif
1364       return false;
1365     }      
1366
1367   return true;
1368 }
1369
1370 /* Add the actual variables FULL_REF can access, given a member of
1371    full_ref's points-to set VAR, where FULL_REF is an access of SIZE at
1372    OFFSET from var. IS_CALL_SITE is true if this is a call, and IS_DEF
1373    is true if this is supposed to be a vdef, and false if this should
1374    be a VUSE.
1375
1376    The real purpose of this function is to take a points-to set for a
1377    pointer to a structure, say
1378
1379    struct s {
1380      int a;
1381      int b;
1382    } foo, *foop = &foo;
1383
1384    and discover which variables an access, such as foop->b, can alias.
1385    
1386    This is necessary because foop only actually points to foo's first
1387    member, so that is all the points-to set contains.  However, an access
1388    to foop->a may be touching some single SFT if we have created some
1389    SFT's for a structure.  */
1390
1391 static bool
1392 add_vars_for_offset (tree full_ref, tree var, HOST_WIDE_INT offset,
1393                      HOST_WIDE_INT size, bool is_call_site, bool is_def)
1394 {
1395   /* Call-clobbered tags may have non-call-clobbered
1396      symbols in their alias sets.  Ignore them if we are
1397      adding VOPs for a call site.  */
1398   if (is_call_site && !is_call_clobbered (var))
1399     return false;
1400
1401   /* For offset 0, we already have the right variable.  If there is no
1402      full_ref, this is not a place we care about (All component
1403      related accesses that go through pointers will have full_ref not
1404      NULL).
1405      Any var for which we didn't create SFT's can't be
1406      distinguished.  */
1407   if (!full_ref || (offset == 0 && size != -1)
1408       || (TREE_CODE (var) != STRUCT_FIELD_TAG
1409           && (!var_can_have_subvars (var) || !get_subvars_for_var (var))))
1410     {
1411       if (!access_can_touch_variable (full_ref, var, offset, size))
1412         return false;
1413
1414       if (is_def)
1415         append_vdef (var);
1416       else
1417         append_vuse (var);
1418       return true;
1419     }
1420   else if (TREE_CODE (var) == STRUCT_FIELD_TAG)
1421     {      
1422       bool added = false;
1423       subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
1424       for (; sv; sv = sv->next)
1425         {
1426           /* Once we hit the end of the parts that could touch,
1427              stop looking.  */
1428           if (size != -1
1429               && SFT_OFFSET (var) + offset + size <= SFT_OFFSET (sv->var))
1430             break;
1431           if (overlap_subvar (SFT_OFFSET (var) + offset, size, sv->var, NULL))
1432             {
1433               added = true;
1434               if (is_def)
1435                 append_vdef (sv->var);
1436               else
1437                 append_vuse (sv->var);
1438             }
1439         }
1440       return added;
1441     }
1442   
1443   return false;
1444 }
1445
1446 /* Add all aliases from ALIASES as virtual operands for the access
1447    FULL_REF at OFFSET and size SIZE.  IS_CALL_SITE is true if the
1448    stmt of the reference is a call.  IS_DEF is true if we should add
1449    VDEF virtual operands, otherwise we'll add VUSEs.  *NONE_ADDED
1450    is set to false once the first virtual operand was added.  */
1451
1452 static void
1453 add_vars_for_bitmap (bitmap aliases, tree full_ref,
1454                      HOST_WIDE_INT offset, HOST_WIDE_INT size,
1455                      bool is_call_site, bool is_def, bool *none_added)
1456 {
1457   bitmap_iterator bi;
1458   unsigned int i;
1459
1460   EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
1461     {
1462       tree al = referenced_var (i);
1463
1464       if (TREE_CODE (al) == MEMORY_PARTITION_TAG)
1465         add_vars_for_bitmap (MPT_SYMBOLS (al), full_ref,
1466                              offset, size, is_call_site, is_def, none_added);
1467       else
1468         *none_added &= !add_vars_for_offset (full_ref, al, offset, size,
1469                                              is_call_site, is_def);
1470     }
1471 }
1472
1473 /* Add VAR to the virtual operands array.  FLAGS is as in
1474    get_expr_operands.  FULL_REF is a tree that contains the entire
1475    pointer dereference expression, if available, or NULL otherwise.
1476    OFFSET and SIZE come from the memory access expression that
1477    generated this virtual operand.  IS_CALL_SITE is true if the
1478    affected statement is a call site.  */
1479
1480 static void
1481 add_virtual_operand (tree var, stmt_ann_t s_ann, int flags,
1482                      tree full_ref, HOST_WIDE_INT offset,
1483                      HOST_WIDE_INT size, bool is_call_site)
1484 {
1485   bitmap aliases = NULL;
1486   tree sym;
1487   var_ann_t v_ann;
1488   
1489   sym = (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
1490   v_ann = var_ann (sym);
1491   
1492   /* Mark the statement as having memory operands.  */
1493   s_ann->references_memory = true;
1494
1495   /* If the variable cannot be modified and this is a VDEF change
1496      it into a VUSE.  This happens when read-only variables are marked
1497      call-clobbered and/or aliased to writable variables.  So we only
1498      check that this only happens on non-specific stores.
1499
1500      Note that if this is a specific store, i.e. associated with a
1501      GIMPLE_MODIFY_STMT, then we can't suppress the VDEF, lest we run
1502      into validation problems.
1503
1504      This can happen when programs cast away const, leaving us with a
1505      store to read-only memory.  If the statement is actually executed
1506      at runtime, then the program is ill formed.  If the statement is
1507      not executed then all is well.  At the very least, we cannot ICE.  */
1508   if ((flags & opf_implicit) && unmodifiable_var_p (var))
1509     flags &= ~opf_def;
1510   
1511   /* The variable is not a GIMPLE register.  Add it (or its aliases) to
1512      virtual operands, unless the caller has specifically requested
1513      not to add virtual operands (used when adding operands inside an
1514      ADDR_EXPR expression).  */
1515   if (flags & opf_no_vops)
1516     return;
1517   
1518   if (MTAG_P (var))
1519     aliases = MTAG_ALIASES (var);
1520
1521   if (aliases == NULL)
1522     {
1523       if (!gimple_aliases_computed_p (cfun)
1524           && (flags & opf_def))
1525         s_ann->has_volatile_ops = true;
1526
1527       /* The variable is not aliased or it is an alias tag.  */
1528       if (flags & opf_def)
1529         append_vdef (var);
1530       else
1531         append_vuse (var);
1532     }
1533   else
1534     {
1535       bool none_added = true;
1536       
1537       /* The variable is aliased.  Add its aliases to the virtual
1538          operands.  */
1539       gcc_assert (!bitmap_empty_p (aliases));
1540
1541       add_vars_for_bitmap (aliases, full_ref, offset, size,
1542                            is_call_site, flags & opf_def, &none_added);
1543
1544       if (flags & opf_def)
1545         {
1546           /* If the variable is also an alias tag, add a virtual
1547              operand for it, otherwise we will miss representing
1548              references to the members of the variable's alias set.          
1549              This fixes the bug in gcc.c-torture/execute/20020503-1.c.
1550              
1551              It is also necessary to add bare defs on clobbers for
1552              SMT's, so that bare SMT uses caused by pruning all the
1553              aliases will link up properly with calls.   In order to
1554              keep the number of these bare defs we add down to the
1555              minimum necessary, we keep track of which SMT's were used
1556              alone in statement vdefs or VUSEs.  */
1557           if (none_added
1558               || (TREE_CODE (var) == SYMBOL_MEMORY_TAG
1559                   && is_call_site))
1560             append_vdef (var);
1561         }
1562       else
1563         {
1564           /* Even if no aliases have been added, we still need to
1565              establish def-use and use-def chains, lest
1566              transformations think that this is not a memory
1567              reference.  For an example of this scenario, see
1568              testsuite/g++.dg/opt/cleanup1.C.  */
1569           if (none_added)
1570             append_vuse (var);
1571         }
1572     }
1573 }
1574
1575
1576 /* Add *VAR_P to the appropriate operand array for S_ANN.  FLAGS is as in
1577    get_expr_operands.  If *VAR_P is a GIMPLE register, it will be added to
1578    the statement's real operands, otherwise it is added to virtual
1579    operands.  */
1580
1581 static void
1582 add_stmt_operand (tree *var_p, stmt_ann_t s_ann, int flags)
1583 {
1584   tree var, sym;
1585   var_ann_t v_ann;
1586
1587   gcc_assert (SSA_VAR_P (*var_p) && s_ann);
1588
1589   var = *var_p;
1590   sym = (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
1591   v_ann = var_ann (sym);
1592
1593   /* Mark statements with volatile operands.  */
1594   if (TREE_THIS_VOLATILE (sym))
1595     s_ann->has_volatile_ops = true;
1596
1597   if (is_gimple_reg (sym))
1598     {
1599       /* The variable is a GIMPLE register.  Add it to real operands.  */
1600       if (flags & opf_def)
1601         append_def (var_p);
1602       else
1603         append_use (var_p);
1604     }
1605   else
1606     add_virtual_operand (var, s_ann, flags, NULL_TREE, 0, -1, false);
1607 }
1608
1609
1610 /* A subroutine of get_expr_operands to handle INDIRECT_REF,
1611    ALIGN_INDIRECT_REF and MISALIGNED_INDIRECT_REF.  
1612
1613    STMT is the statement being processed, EXPR is the INDIRECT_REF
1614       that got us here.
1615    
1616    FLAGS is as in get_expr_operands.
1617
1618    FULL_REF contains the full pointer dereference expression, if we
1619       have it, or NULL otherwise.
1620
1621    OFFSET and SIZE are the location of the access inside the
1622       dereferenced pointer, if known.
1623
1624    RECURSE_ON_BASE should be set to true if we want to continue
1625       calling get_expr_operands on the base pointer, and false if
1626       something else will do it for us.  */
1627
1628 static void
1629 get_indirect_ref_operands (tree stmt, tree expr, int flags,
1630                            tree full_ref,
1631                            HOST_WIDE_INT offset, HOST_WIDE_INT size,
1632                            bool recurse_on_base)
1633 {
1634   tree *pptr = &TREE_OPERAND (expr, 0);
1635   tree ptr = *pptr;
1636   stmt_ann_t s_ann = stmt_ann (stmt);
1637
1638   s_ann->references_memory = true;
1639   if (TREE_THIS_VOLATILE (expr))
1640     s_ann->has_volatile_ops = true; 
1641
1642   if (SSA_VAR_P (ptr))
1643     {
1644       struct ptr_info_def *pi = NULL;
1645
1646       /* If PTR has flow-sensitive points-to information, use it.  */
1647       if (TREE_CODE (ptr) == SSA_NAME
1648           && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1649           && pi->name_mem_tag)
1650         {
1651           /* PTR has its own memory tag.  Use it.  */
1652           add_virtual_operand (pi->name_mem_tag, s_ann, flags,
1653                                full_ref, offset, size, false);
1654         }
1655       else
1656         {
1657           /* If PTR is not an SSA_NAME or it doesn't have a name
1658              tag, use its symbol memory tag.  */
1659           var_ann_t v_ann;
1660
1661           /* If we are emitting debugging dumps, display a warning if
1662              PTR is an SSA_NAME with no flow-sensitive alias
1663              information.  That means that we may need to compute
1664              aliasing again.  */
1665           if (dump_file
1666               && TREE_CODE (ptr) == SSA_NAME
1667               && pi == NULL)
1668             {
1669               fprintf (dump_file,
1670                   "NOTE: no flow-sensitive alias info for ");
1671               print_generic_expr (dump_file, ptr, dump_flags);
1672               fprintf (dump_file, " in ");
1673               print_generic_stmt (dump_file, stmt, dump_flags);
1674             }
1675
1676           if (TREE_CODE (ptr) == SSA_NAME)
1677             ptr = SSA_NAME_VAR (ptr);
1678           v_ann = var_ann (ptr);
1679
1680           if (v_ann->symbol_mem_tag)
1681             add_virtual_operand (v_ann->symbol_mem_tag, s_ann, flags,
1682                                  full_ref, offset, size, false);
1683
1684           /* Aliasing information is missing; mark statement as
1685              volatile so we won't optimize it out too actively.  */
1686           else if (!gimple_aliases_computed_p (cfun)
1687                    && (flags & opf_def))
1688             s_ann->has_volatile_ops = true;
1689         }
1690     }
1691   else if (TREE_CODE (ptr) == INTEGER_CST)
1692     {
1693       /* If a constant is used as a pointer, we can't generate a real
1694          operand for it but we mark the statement volatile to prevent
1695          optimizations from messing things up.  */
1696       s_ann->has_volatile_ops = true;
1697       return;
1698     }
1699   else
1700     {
1701       /* Ok, this isn't even is_gimple_min_invariant.  Something's broke.  */
1702       gcc_unreachable ();
1703     }
1704
1705   /* If requested, add a USE operand for the base pointer.  */
1706   if (recurse_on_base)
1707     get_expr_operands (stmt, pptr, opf_use);
1708 }
1709
1710
1711 /* A subroutine of get_expr_operands to handle TARGET_MEM_REF.  */
1712
1713 static void
1714 get_tmr_operands (tree stmt, tree expr, int flags)
1715 {
1716   tree tag;
1717   stmt_ann_t s_ann = stmt_ann (stmt);
1718
1719   /* This statement references memory.  */
1720   s_ann->references_memory = 1;
1721
1722   /* First record the real operands.  */
1723   get_expr_operands (stmt, &TMR_BASE (expr), opf_use);
1724   get_expr_operands (stmt, &TMR_INDEX (expr), opf_use);
1725
1726   if (TMR_SYMBOL (expr))
1727     add_to_addressable_set (TMR_SYMBOL (expr), &s_ann->addresses_taken);
1728
1729   tag = TMR_TAG (expr);
1730   if (!tag)
1731     {
1732       /* Something weird, so ensure that we will be careful.  */
1733       s_ann->has_volatile_ops = true;
1734       return;
1735     }
1736   if (!MTAG_P (tag))
1737     {
1738       get_expr_operands (stmt, &tag, flags);
1739       return;
1740     }
1741
1742   add_virtual_operand (tag, s_ann, flags, expr, 0, -1, false);
1743 }
1744
1745
1746 /* Add clobbering definitions for .GLOBAL_VAR or for each of the call
1747    clobbered variables in the function.  */
1748
1749 static void
1750 add_call_clobber_ops (tree stmt, tree callee)
1751 {
1752   unsigned u;
1753   bitmap_iterator bi;
1754   stmt_ann_t s_ann = stmt_ann (stmt);
1755   bitmap not_read_b, not_written_b;
1756   
1757   /* If we created .GLOBAL_VAR earlier, just use it.  */
1758   if (gimple_global_var (cfun))
1759     {
1760       tree var = gimple_global_var (cfun);
1761       add_virtual_operand (var, s_ann, opf_def, NULL, 0, -1, true);
1762       return;
1763     }
1764
1765   /* Get info for local and module level statics.  There is a bit
1766      set for each static if the call being processed does not read
1767      or write that variable.  */
1768   not_read_b = callee ? ipa_reference_get_not_read_global (callee) : NULL; 
1769   not_written_b = callee ? ipa_reference_get_not_written_global (callee) : NULL; 
1770
1771   /* Add a VDEF operand for every call clobbered variable.  */
1772   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, u, bi)
1773     {
1774       tree var = referenced_var_lookup (u);
1775       unsigned int escape_mask = var_ann (var)->escape_mask;
1776       tree real_var = var;
1777       bool not_read;
1778       bool not_written;
1779       
1780       /* Not read and not written are computed on regular vars, not
1781          subvars, so look at the parent var if this is an SFT. */
1782       if (TREE_CODE (var) == STRUCT_FIELD_TAG)
1783         real_var = SFT_PARENT_VAR (var);
1784
1785       not_read = not_read_b
1786                  ? bitmap_bit_p (not_read_b, DECL_UID (real_var))
1787                  : false;
1788
1789       not_written = not_written_b
1790                     ? bitmap_bit_p (not_written_b, DECL_UID (real_var))
1791                     : false;
1792       gcc_assert (!unmodifiable_var_p (var));
1793       
1794       clobber_stats.clobbered_vars++;
1795
1796       /* See if this variable is really clobbered by this function.  */
1797
1798       /* Trivial case: Things escaping only to pure/const are not
1799          clobbered by non-pure-const, and only read by pure/const. */
1800       if ((escape_mask & ~(ESCAPE_TO_PURE_CONST)) == 0)
1801         {
1802           tree call = get_call_expr_in (stmt);
1803           if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1804             {
1805               add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1806               clobber_stats.unescapable_clobbers_avoided++;
1807               continue;
1808             }
1809           else
1810             {
1811               clobber_stats.unescapable_clobbers_avoided++;
1812               continue;
1813             }
1814         }
1815             
1816       if (not_written)
1817         {
1818           clobber_stats.static_write_clobbers_avoided++;
1819           if (!not_read)
1820             add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1821           else
1822             clobber_stats.static_read_clobbers_avoided++;
1823         }
1824       else
1825         add_virtual_operand (var, s_ann, opf_def, NULL, 0, -1, true);
1826     }
1827 }
1828
1829
1830 /* Add VUSE operands for .GLOBAL_VAR or all call clobbered variables in the
1831    function.  */
1832
1833 static void
1834 add_call_read_ops (tree stmt, tree callee)
1835 {
1836   unsigned u;
1837   bitmap_iterator bi;
1838   stmt_ann_t s_ann = stmt_ann (stmt);
1839   bitmap not_read_b;
1840
1841   /* if the function is not pure, it may reference memory.  Add
1842      a VUSE for .GLOBAL_VAR if it has been created.  See add_referenced_var
1843      for the heuristic used to decide whether to create .GLOBAL_VAR.  */
1844   if (gimple_global_var (cfun))
1845     {
1846       tree var = gimple_global_var (cfun);
1847       add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1848       return;
1849     }
1850   
1851   not_read_b = callee ? ipa_reference_get_not_read_global (callee) : NULL; 
1852
1853   /* Add a VUSE for each call-clobbered variable.  */
1854   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, u, bi)
1855     {
1856       tree var = referenced_var (u);
1857       tree real_var = var;
1858       bool not_read;
1859       
1860       clobber_stats.readonly_clobbers++;
1861
1862       /* Not read and not written are computed on regular vars, not
1863          subvars, so look at the parent var if this is an SFT. */
1864
1865       if (TREE_CODE (var) == STRUCT_FIELD_TAG)
1866         real_var = SFT_PARENT_VAR (var);
1867
1868       not_read = not_read_b ? bitmap_bit_p (not_read_b, DECL_UID (real_var))
1869                             : false;
1870       
1871       if (not_read)
1872         {
1873           clobber_stats.static_readonly_clobbers_avoided++;
1874           continue;
1875         }
1876             
1877       add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1878     }
1879 }
1880
1881
1882 /* A subroutine of get_expr_operands to handle CALL_EXPR.  */
1883
1884 static void
1885 get_call_expr_operands (tree stmt, tree expr)
1886 {
1887   int call_flags = call_expr_flags (expr);
1888   int i, nargs;
1889   stmt_ann_t ann = stmt_ann (stmt);
1890
1891   ann->references_memory = true;
1892
1893   /* If aliases have been computed already, add VDEF or VUSE
1894      operands for all the symbols that have been found to be
1895      call-clobbered.  */
1896   if (gimple_aliases_computed_p (cfun)
1897       && !(call_flags & ECF_NOVOPS))
1898     {
1899       /* A 'pure' or a 'const' function never call-clobbers anything. 
1900          A 'noreturn' function might, but since we don't return anyway 
1901          there is no point in recording that.  */ 
1902       if (TREE_SIDE_EFFECTS (expr)
1903           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1904         add_call_clobber_ops (stmt, get_callee_fndecl (expr));
1905       else if (!(call_flags & ECF_CONST))
1906         add_call_read_ops (stmt, get_callee_fndecl (expr));
1907     }
1908
1909   /* Find uses in the called function.  */
1910   get_expr_operands (stmt, &CALL_EXPR_FN (expr), opf_use);
1911   nargs = call_expr_nargs (expr);
1912   for (i = 0; i < nargs; i++)
1913     get_expr_operands (stmt, &CALL_EXPR_ARG (expr, i), opf_use);
1914
1915   get_expr_operands (stmt, &CALL_EXPR_STATIC_CHAIN (expr), opf_use);
1916 }
1917
1918
1919 /* Scan operands in the ASM_EXPR stmt referred to in INFO.  */
1920
1921 static void
1922 get_asm_expr_operands (tree stmt)
1923 {
1924   stmt_ann_t s_ann;
1925   int i, noutputs;
1926   const char **oconstraints;
1927   const char *constraint;
1928   bool allows_mem, allows_reg, is_inout;
1929   tree link;
1930
1931   s_ann = stmt_ann (stmt);
1932   noutputs = list_length (ASM_OUTPUTS (stmt));
1933   oconstraints = (const char **) alloca ((noutputs) * sizeof (const char *));
1934
1935   /* Gather all output operands.  */
1936   for (i = 0, link = ASM_OUTPUTS (stmt); link; i++, link = TREE_CHAIN (link))
1937     {
1938       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1939       oconstraints[i] = constraint;
1940       parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
1941                                &allows_reg, &is_inout);
1942
1943       /* This should have been split in gimplify_asm_expr.  */
1944       gcc_assert (!allows_reg || !is_inout);
1945
1946       /* Memory operands are addressable.  Note that STMT needs the
1947          address of this operand.  */
1948       if (!allows_reg && allows_mem)
1949         {
1950           tree t = get_base_address (TREE_VALUE (link));
1951           if (t && DECL_P (t) && s_ann)
1952             add_to_addressable_set (t, &s_ann->addresses_taken);
1953         }
1954
1955       get_expr_operands (stmt, &TREE_VALUE (link), opf_def);
1956     }
1957
1958   /* Gather all input operands.  */
1959   for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
1960     {
1961       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1962       parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
1963                               &allows_mem, &allows_reg);
1964
1965       /* Memory operands are addressable.  Note that STMT needs the
1966          address of this operand.  */
1967       if (!allows_reg && allows_mem)
1968         {
1969           tree t = get_base_address (TREE_VALUE (link));
1970           if (t && DECL_P (t) && s_ann)
1971             add_to_addressable_set (t, &s_ann->addresses_taken);
1972         }
1973
1974       get_expr_operands (stmt, &TREE_VALUE (link), 0);
1975     }
1976
1977   /* Clobber all memory and addressable symbols for asm ("" : : : "memory");  */
1978   for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
1979     if (strcmp (TREE_STRING_POINTER (TREE_VALUE (link)), "memory") == 0)
1980       {
1981         unsigned i;
1982         bitmap_iterator bi;
1983
1984         s_ann->references_memory = true;
1985
1986         EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
1987           {
1988             tree var = referenced_var (i);
1989             add_stmt_operand (&var, s_ann, opf_def | opf_implicit);
1990           }
1991
1992         EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
1993           {
1994             tree var = referenced_var (i);
1995
1996             /* Subvars are explicitly represented in this list, so we
1997                don't need the original to be added to the clobber ops,
1998                but the original *will* be in this list because we keep
1999                the addressability of the original variable up-to-date
2000                to avoid confusing the back-end.  */
2001             if (var_can_have_subvars (var)
2002                 && get_subvars_for_var (var) != NULL)
2003               continue;         
2004
2005             add_stmt_operand (&var, s_ann, opf_def | opf_implicit);
2006           }
2007         break;
2008       }
2009 }
2010
2011
2012 /* Scan operands for the assignment expression EXPR in statement STMT.  */
2013
2014 static void
2015 get_modify_stmt_operands (tree stmt, tree expr)
2016 {
2017   /* First get operands from the RHS.  */
2018   get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (expr, 1), opf_use);
2019
2020   /* For the LHS, use a regular definition (opf_def) for GIMPLE
2021      registers.  If the LHS is a store to memory, we will need
2022      a preserving definition (VDEF).
2023
2024      Preserving definitions are those that modify a part of an
2025      aggregate object for which no subvars have been computed (or the
2026      reference does not correspond exactly to one of them). Stores
2027      through a pointer are also represented with VDEF operators.
2028
2029      We used to distinguish between preserving and killing definitions.
2030      We always emit preserving definitions now.  */
2031   get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (expr, 0), opf_def);
2032 }
2033
2034
2035 /* Recursively scan the expression pointed to by EXPR_P in statement
2036    STMT.  FLAGS is one of the OPF_* constants modifying how to
2037    interpret the operands found.  */
2038
2039 static void
2040 get_expr_operands (tree stmt, tree *expr_p, int flags)
2041 {
2042   enum tree_code code;
2043   enum tree_code_class codeclass;
2044   tree expr = *expr_p;
2045   stmt_ann_t s_ann = stmt_ann (stmt);
2046
2047   if (expr == NULL)
2048     return;
2049
2050   code = TREE_CODE (expr);
2051   codeclass = TREE_CODE_CLASS (code);
2052
2053   switch (code)
2054     {
2055     case ADDR_EXPR:
2056       /* Taking the address of a variable does not represent a
2057          reference to it, but the fact that the statement takes its
2058          address will be of interest to some passes (e.g. alias
2059          resolution).  */
2060       add_to_addressable_set (TREE_OPERAND (expr, 0), &s_ann->addresses_taken);
2061
2062       /* If the address is invariant, there may be no interesting
2063          variable references inside.  */
2064       if (is_gimple_min_invariant (expr))
2065         return;
2066
2067       /* Otherwise, there may be variables referenced inside but there
2068          should be no VUSEs created, since the referenced objects are
2069          not really accessed.  The only operands that we should find
2070          here are ARRAY_REF indices which will always be real operands
2071          (GIMPLE does not allow non-registers as array indices).  */
2072       flags |= opf_no_vops;
2073       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2074       return;
2075
2076     case SSA_NAME:
2077     case STRUCT_FIELD_TAG:
2078     case SYMBOL_MEMORY_TAG:
2079     case NAME_MEMORY_TAG:
2080      add_stmt_operand (expr_p, s_ann, flags);
2081      return;
2082
2083     case VAR_DECL:
2084     case PARM_DECL:
2085     case RESULT_DECL:
2086       {
2087         subvar_t svars;
2088         
2089         /* Add the subvars for a variable, if it has subvars, to DEFS
2090            or USES.  Otherwise, add the variable itself.  Whether it
2091            goes to USES or DEFS depends on the operand flags.  */
2092         if (var_can_have_subvars (expr)
2093             && (svars = get_subvars_for_var (expr)))
2094           {
2095             subvar_t sv;
2096             for (sv = svars; sv; sv = sv->next)
2097               add_stmt_operand (&sv->var, s_ann, flags);
2098           }
2099         else
2100           add_stmt_operand (expr_p, s_ann, flags);
2101
2102         return;
2103       }
2104
2105     case MISALIGNED_INDIRECT_REF:
2106       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
2107       /* fall through */
2108
2109     case ALIGN_INDIRECT_REF:
2110     case INDIRECT_REF:
2111       get_indirect_ref_operands (stmt, expr, flags, expr, 0, -1, true);
2112       return;
2113
2114     case TARGET_MEM_REF:
2115       get_tmr_operands (stmt, expr, flags);
2116       return;
2117
2118     case ARRAY_REF:
2119     case ARRAY_RANGE_REF:
2120     case COMPONENT_REF:
2121     case REALPART_EXPR:
2122     case IMAGPART_EXPR:
2123       {
2124         tree ref;
2125         HOST_WIDE_INT offset, size, maxsize;
2126         bool none = true;
2127
2128         if (TREE_THIS_VOLATILE (expr))
2129           s_ann->has_volatile_ops = true;
2130
2131         /* This component reference becomes an access to all of the
2132            subvariables it can touch, if we can determine that, but
2133            *NOT* the real one.  If we can't determine which fields we
2134            could touch, the recursion will eventually get to a
2135            variable and add *all* of its subvars, or whatever is the
2136            minimum correct subset.  */
2137         ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
2138         if (SSA_VAR_P (ref) && get_subvars_for_var (ref))
2139           {
2140             subvar_t sv;
2141             subvar_t svars = get_subvars_for_var (ref);
2142
2143             for (sv = svars; sv; sv = sv->next)
2144               {
2145                 bool exact;             
2146
2147                 if (overlap_subvar (offset, maxsize, sv->var, &exact))
2148                   {
2149                     int subvar_flags = flags;
2150                     none = false;
2151                     add_stmt_operand (&sv->var, s_ann, subvar_flags);
2152                   }
2153               }
2154
2155             if (!none)
2156               flags |= opf_no_vops;
2157
2158             if ((DECL_P (ref) && TREE_THIS_VOLATILE (ref))
2159                 || (TREE_CODE (ref) == SSA_NAME
2160                     && TREE_THIS_VOLATILE (SSA_NAME_VAR (ref))))
2161               s_ann->has_volatile_ops = true;
2162           }
2163         else if (TREE_CODE (ref) == INDIRECT_REF)
2164           {
2165             get_indirect_ref_operands (stmt, ref, flags, expr, offset,
2166                                        maxsize, false);
2167             flags |= opf_no_vops;
2168           }
2169
2170         /* Even if we found subvars above we need to ensure to see
2171            immediate uses for d in s.a[d].  In case of s.a having
2172            a subvar or we would miss it otherwise.  */
2173         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2174         
2175         if (code == COMPONENT_REF)
2176           {
2177             if (TREE_THIS_VOLATILE (TREE_OPERAND (expr, 1)))
2178               s_ann->has_volatile_ops = true; 
2179             get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
2180           }
2181         else if (code == ARRAY_REF || code == ARRAY_RANGE_REF)
2182           {
2183             get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2184             get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
2185             get_expr_operands (stmt, &TREE_OPERAND (expr, 3), opf_use);
2186           }
2187
2188         return;
2189       }
2190
2191     case WITH_SIZE_EXPR:
2192       /* WITH_SIZE_EXPR is a pass-through reference to its first argument,
2193          and an rvalue reference to its second argument.  */
2194       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2195       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2196       return;
2197
2198     case CALL_EXPR:
2199       get_call_expr_operands (stmt, expr);
2200       return;
2201
2202     case COND_EXPR:
2203     case VEC_COND_EXPR:
2204       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_use);
2205       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2206       get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
2207       return;
2208
2209     case GIMPLE_MODIFY_STMT:
2210       get_modify_stmt_operands (stmt, expr);
2211       return;
2212
2213     case CONSTRUCTOR:
2214       {
2215         /* General aggregate CONSTRUCTORs have been decomposed, but they
2216            are still in use as the COMPLEX_EXPR equivalent for vectors.  */
2217         constructor_elt *ce;
2218         unsigned HOST_WIDE_INT idx;
2219
2220         for (idx = 0;
2221              VEC_iterate (constructor_elt, CONSTRUCTOR_ELTS (expr), idx, ce);
2222              idx++)
2223           get_expr_operands (stmt, &ce->value, opf_use);
2224
2225         return;
2226       }
2227
2228     case BIT_FIELD_REF:
2229     case TRUTH_NOT_EXPR:
2230     case VIEW_CONVERT_EXPR:
2231     do_unary:
2232       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2233       return;
2234
2235     case TRUTH_AND_EXPR:
2236     case TRUTH_OR_EXPR:
2237     case TRUTH_XOR_EXPR:
2238     case COMPOUND_EXPR:
2239     case OBJ_TYPE_REF:
2240     case ASSERT_EXPR:
2241     do_binary:
2242       {
2243         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2244         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
2245         return;
2246       }
2247
2248     case DOT_PROD_EXPR:
2249     case REALIGN_LOAD_EXPR:
2250       {
2251         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2252         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
2253         get_expr_operands (stmt, &TREE_OPERAND (expr, 2), flags);
2254         return;
2255       }
2256
2257     case CHANGE_DYNAMIC_TYPE_EXPR:
2258       get_expr_operands (stmt, &CHANGE_DYNAMIC_TYPE_LOCATION (expr), opf_use);
2259       return;
2260
2261     case OMP_FOR:
2262       {
2263         tree init = OMP_FOR_INIT (expr);
2264         tree cond = OMP_FOR_COND (expr);
2265         tree incr = OMP_FOR_INCR (expr);
2266         tree c, clauses = OMP_FOR_CLAUSES (stmt);
2267
2268         get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (init, 0), opf_def);
2269         get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (init, 1), opf_use);
2270         get_expr_operands (stmt, &TREE_OPERAND (cond, 1), opf_use);
2271         get_expr_operands (stmt, &TREE_OPERAND (GIMPLE_STMT_OPERAND (incr, 1), 1),
2272                            opf_use);
2273
2274         c = find_omp_clause (clauses, OMP_CLAUSE_SCHEDULE);
2275         if (c)
2276           get_expr_operands (stmt, &OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (c),
2277                              opf_use);
2278         return;
2279       }
2280
2281     case OMP_CONTINUE:
2282       {
2283         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_def);
2284         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2285         return;
2286       }
2287
2288     case OMP_PARALLEL:
2289       {
2290         tree c, clauses = OMP_PARALLEL_CLAUSES (stmt);
2291
2292         if (OMP_PARALLEL_DATA_ARG (stmt))
2293           {
2294             get_expr_operands (stmt, &OMP_PARALLEL_DATA_ARG (stmt), opf_use);
2295             add_to_addressable_set (OMP_PARALLEL_DATA_ARG (stmt),
2296                                     &s_ann->addresses_taken);
2297           }
2298
2299         c = find_omp_clause (clauses, OMP_CLAUSE_IF);
2300         if (c)
2301           get_expr_operands (stmt, &OMP_CLAUSE_IF_EXPR (c), opf_use);
2302         c = find_omp_clause (clauses, OMP_CLAUSE_NUM_THREADS);
2303         if (c)
2304           get_expr_operands (stmt, &OMP_CLAUSE_NUM_THREADS_EXPR (c), opf_use);
2305         return;
2306       }
2307
2308     case OMP_SECTIONS:
2309       {
2310         get_expr_operands (stmt, &OMP_SECTIONS_CONTROL (expr), opf_def);
2311         return;
2312       }
2313
2314     case BLOCK:
2315     case FUNCTION_DECL:
2316     case EXC_PTR_EXPR:
2317     case FILTER_EXPR:
2318     case LABEL_DECL:
2319     case CONST_DECL:
2320     case OMP_SINGLE:
2321     case OMP_MASTER:
2322     case OMP_ORDERED:
2323     case OMP_CRITICAL:
2324     case OMP_RETURN:
2325     case OMP_SECTION:
2326     case OMP_SECTIONS_SWITCH:
2327       /* Expressions that make no memory references.  */
2328       return;
2329
2330     default:
2331       if (codeclass == tcc_unary)
2332         goto do_unary;
2333       if (codeclass == tcc_binary || codeclass == tcc_comparison)
2334         goto do_binary;
2335       if (codeclass == tcc_constant || codeclass == tcc_type)
2336         return;
2337     }
2338
2339   /* If we get here, something has gone wrong.  */
2340 #ifdef ENABLE_CHECKING
2341   fprintf (stderr, "unhandled expression in get_expr_operands():\n");
2342   debug_tree (expr);
2343   fputs ("\n", stderr);
2344 #endif
2345   gcc_unreachable ();
2346 }
2347
2348
2349 /* Parse STMT looking for operands.  When finished, the various
2350    build_* operand vectors will have potential operands in them.  */
2351
2352 static void
2353 parse_ssa_operands (tree stmt)
2354 {
2355   enum tree_code code;
2356
2357   code = TREE_CODE (stmt);
2358   switch (code)
2359     {
2360     case GIMPLE_MODIFY_STMT:
2361       get_modify_stmt_operands (stmt, stmt);
2362       break;
2363
2364     case COND_EXPR:
2365       get_expr_operands (stmt, &COND_EXPR_COND (stmt), opf_use);
2366       break;
2367
2368     case SWITCH_EXPR:
2369       get_expr_operands (stmt, &SWITCH_COND (stmt), opf_use);
2370       break;
2371
2372     case ASM_EXPR:
2373       get_asm_expr_operands (stmt);
2374       break;
2375
2376     case RETURN_EXPR:
2377       get_expr_operands (stmt, &TREE_OPERAND (stmt, 0), opf_use);
2378       break;
2379
2380     case GOTO_EXPR:
2381       get_expr_operands (stmt, &GOTO_DESTINATION (stmt), opf_use);
2382       break;
2383
2384     case LABEL_EXPR:
2385       get_expr_operands (stmt, &LABEL_EXPR_LABEL (stmt), opf_use);
2386       break;
2387
2388     case BIND_EXPR:
2389     case CASE_LABEL_EXPR:
2390     case TRY_CATCH_EXPR:
2391     case TRY_FINALLY_EXPR:
2392     case EH_FILTER_EXPR:
2393     case CATCH_EXPR:
2394     case RESX_EXPR:
2395       /* These nodes contain no variable references.  */
2396      break;
2397
2398     default:
2399       /* Notice that if get_expr_operands tries to use &STMT as the
2400          operand pointer (which may only happen for USE operands), we
2401          will fail in add_stmt_operand.  This default will handle
2402          statements like empty statements, or CALL_EXPRs that may
2403          appear on the RHS of a statement or as statements themselves.  */
2404       get_expr_operands (stmt, &stmt, opf_use);
2405       break;
2406     }
2407 }
2408
2409
2410 /* Create an operands cache for STMT.  */
2411
2412 static void
2413 build_ssa_operands (tree stmt)
2414 {
2415   stmt_ann_t ann = get_stmt_ann (stmt);
2416   
2417   /* Initially assume that the statement has no volatile operands and
2418      makes no memory references.  */
2419   ann->has_volatile_ops = false;
2420   ann->references_memory = false;
2421   /* Just clear the bitmap so we don't end up reallocating it over and over.  */
2422   if (ann->addresses_taken)
2423     bitmap_clear (ann->addresses_taken);
2424
2425   start_ssa_stmt_operands ();
2426   parse_ssa_operands (stmt);
2427   operand_build_sort_virtual (build_vuses);
2428   operand_build_sort_virtual (build_vdefs);
2429   finalize_ssa_stmt_operands (stmt);
2430
2431   if (ann->addresses_taken && bitmap_empty_p (ann->addresses_taken))
2432     ann->addresses_taken = NULL;
2433   /* For added safety, assume that statements with volatile operands
2434      also reference memory.  */
2435   if (ann->has_volatile_ops)
2436     ann->references_memory = true;
2437 }
2438
2439 /* Releases the operands of STMT back to their freelists, and clears
2440    the stmt operand lists.  */
2441
2442 void
2443 free_stmt_operands (tree stmt)
2444 {
2445   def_optype_p defs = DEF_OPS (stmt), last_def;
2446   use_optype_p uses = USE_OPS (stmt), last_use;
2447   voptype_p vuses = VUSE_OPS (stmt);
2448   voptype_p vdefs = VDEF_OPS (stmt), vdef, next_vdef;
2449   unsigned i;
2450
2451   if (defs)
2452     {
2453       for (last_def = defs; last_def->next; last_def = last_def->next)
2454         continue;
2455       last_def->next = gimple_ssa_operands (cfun)->free_defs;
2456       gimple_ssa_operands (cfun)->free_defs = defs;
2457       DEF_OPS (stmt) = NULL;
2458     }
2459
2460   if (uses)
2461     {
2462       for (last_use = uses; last_use->next; last_use = last_use->next)
2463         delink_imm_use (USE_OP_PTR (last_use));
2464       delink_imm_use (USE_OP_PTR (last_use));
2465       last_use->next = gimple_ssa_operands (cfun)->free_uses;
2466       gimple_ssa_operands (cfun)->free_uses = uses;
2467       USE_OPS (stmt) = NULL;
2468     }
2469
2470   if (vuses)
2471     {
2472       for (i = 0; i < VUSE_NUM (vuses); i++)
2473         delink_imm_use (VUSE_OP_PTR (vuses, i));
2474       add_vop_to_freelist (vuses);
2475       VUSE_OPS (stmt) = NULL;
2476     }
2477
2478   if (vdefs)
2479     {
2480       for (vdef = vdefs; vdef; vdef = next_vdef)
2481         {
2482           next_vdef = vdef->next;
2483           delink_imm_use (VDEF_OP_PTR (vdef, 0));
2484           add_vop_to_freelist (vdef);
2485         }
2486       VDEF_OPS (stmt) = NULL;
2487     }
2488 }
2489
2490 /* Free any operands vectors in OPS.  */
2491
2492 void 
2493 free_ssa_operands (stmt_operands_p ops)
2494 {
2495   ops->def_ops = NULL;
2496   ops->use_ops = NULL;
2497   ops->vdef_ops = NULL;
2498   ops->vuse_ops = NULL;
2499   BITMAP_FREE (ops->loads);
2500   BITMAP_FREE (ops->stores);
2501 }
2502
2503
2504 /* Get the operands of statement STMT.  */
2505
2506 void
2507 update_stmt_operands (tree stmt)
2508 {
2509   stmt_ann_t ann = get_stmt_ann (stmt);
2510
2511   /* If update_stmt_operands is called before SSA is initialized, do
2512      nothing.  */
2513   if (!ssa_operands_active ())
2514     return;
2515
2516   /* The optimizers cannot handle statements that are nothing but a
2517      _DECL.  This indicates a bug in the gimplifier.  */
2518   gcc_assert (!SSA_VAR_P (stmt));
2519
2520   timevar_push (TV_TREE_OPS);
2521
2522   gcc_assert (ann->modified);
2523   build_ssa_operands (stmt);
2524   ann->modified = 0;
2525
2526   timevar_pop (TV_TREE_OPS);
2527 }
2528
2529
2530 /* Copies virtual operands from SRC to DST.  */
2531
2532 void
2533 copy_virtual_operands (tree dest, tree src)
2534 {
2535   unsigned int i, n;
2536   voptype_p src_vuses, dest_vuses;
2537   voptype_p src_vdefs, dest_vdefs;
2538   struct voptype_d vuse;
2539   struct voptype_d vdef;
2540   stmt_ann_t dest_ann;
2541
2542   VDEF_OPS (dest) = NULL;
2543   VUSE_OPS (dest) = NULL;
2544
2545   dest_ann = get_stmt_ann (dest);
2546   BITMAP_FREE (dest_ann->operands.loads);
2547   BITMAP_FREE (dest_ann->operands.stores);
2548
2549   if (LOADED_SYMS (src))
2550     {
2551       dest_ann->operands.loads = BITMAP_ALLOC (&operands_bitmap_obstack);
2552       bitmap_copy (dest_ann->operands.loads, LOADED_SYMS (src));
2553     }
2554
2555   if (STORED_SYMS (src))
2556     {
2557       dest_ann->operands.stores = BITMAP_ALLOC (&operands_bitmap_obstack);
2558       bitmap_copy (dest_ann->operands.stores, STORED_SYMS (src));
2559     }
2560
2561   /* Copy all the VUSE operators and corresponding operands.  */
2562   dest_vuses = &vuse;
2563   for (src_vuses = VUSE_OPS (src); src_vuses; src_vuses = src_vuses->next)
2564     {
2565       n = VUSE_NUM (src_vuses);
2566       dest_vuses = add_vuse_op (dest, NULL_TREE, n, dest_vuses);
2567       for (i = 0; i < n; i++)
2568         SET_USE (VUSE_OP_PTR (dest_vuses, i), VUSE_OP (src_vuses, i));
2569
2570       if (VUSE_OPS (dest) == NULL)
2571         VUSE_OPS (dest) = vuse.next;
2572     }
2573
2574   /* Copy all the VDEF operators and corresponding operands.  */
2575   dest_vdefs = &vdef;
2576   for (src_vdefs = VDEF_OPS (src); src_vdefs; src_vdefs = src_vdefs->next)
2577     {
2578       n = VUSE_NUM (src_vdefs);
2579       dest_vdefs = add_vdef_op (dest, NULL_TREE, n, dest_vdefs);
2580       VDEF_RESULT (dest_vdefs) = VDEF_RESULT (src_vdefs);
2581       for (i = 0; i < n; i++)
2582         SET_USE (VUSE_OP_PTR (dest_vdefs, i), VUSE_OP (src_vdefs, i));
2583
2584       if (VDEF_OPS (dest) == NULL)
2585         VDEF_OPS (dest) = vdef.next;
2586     }
2587 }
2588
2589
2590 /* Specifically for use in DOM's expression analysis.  Given a store, we
2591    create an artificial stmt which looks like a load from the store, this can
2592    be used to eliminate redundant loads.  OLD_OPS are the operands from the 
2593    store stmt, and NEW_STMT is the new load which represents a load of the
2594    values stored.  */
2595
2596 void
2597 create_ssa_artificial_load_stmt (tree new_stmt, tree old_stmt)
2598 {
2599   tree op;
2600   ssa_op_iter iter;
2601   use_operand_p use_p;
2602   unsigned i;
2603
2604   get_stmt_ann (new_stmt);
2605
2606   /* Process NEW_STMT looking for operands.  */
2607   start_ssa_stmt_operands ();
2608   parse_ssa_operands (new_stmt);
2609
2610   for (i = 0; VEC_iterate (tree, build_vuses, i, op); i++)
2611     if (TREE_CODE (op) != SSA_NAME)
2612       var_ann (op)->in_vuse_list = false;
2613    
2614   for (i = 0; VEC_iterate (tree, build_vuses, i, op); i++)
2615     if (TREE_CODE (op) != SSA_NAME)
2616       var_ann (op)->in_vdef_list = false;
2617
2618   /* Remove any virtual operands that were found.  */
2619   VEC_truncate (tree, build_vdefs, 0);
2620   VEC_truncate (tree, build_vuses, 0);
2621
2622   /* For each VDEF on the original statement, we want to create a
2623      VUSE of the VDEF result operand on the new statement.  */
2624   FOR_EACH_SSA_TREE_OPERAND (op, old_stmt, iter, SSA_OP_VDEF)
2625     append_vuse (op);
2626
2627   finalize_ssa_stmt_operands (new_stmt);
2628
2629   /* All uses in this fake stmt must not be in the immediate use lists.  */
2630   FOR_EACH_SSA_USE_OPERAND (use_p, new_stmt, iter, SSA_OP_ALL_USES)
2631     delink_imm_use (use_p);
2632 }
2633
2634
2635 /* Swap operands EXP0 and EXP1 in statement STMT.  No attempt is done
2636    to test the validity of the swap operation.  */
2637
2638 void
2639 swap_tree_operands (tree stmt, tree *exp0, tree *exp1)
2640 {
2641   tree op0, op1;
2642   op0 = *exp0;
2643   op1 = *exp1;
2644
2645   /* If the operand cache is active, attempt to preserve the relative
2646      positions of these two operands in their respective immediate use
2647      lists.  */
2648   if (ssa_operands_active () && op0 != op1)
2649     {
2650       use_optype_p use0, use1, ptr;
2651       use0 = use1 = NULL;
2652
2653       /* Find the 2 operands in the cache, if they are there.  */
2654       for (ptr = USE_OPS (stmt); ptr; ptr = ptr->next)
2655         if (USE_OP_PTR (ptr)->use == exp0)
2656           {
2657             use0 = ptr;
2658             break;
2659           }
2660
2661       for (ptr = USE_OPS (stmt); ptr; ptr = ptr->next)
2662         if (USE_OP_PTR (ptr)->use == exp1)
2663           {
2664             use1 = ptr;
2665             break;
2666           }
2667
2668       /* If both uses don't have operand entries, there isn't much we can do
2669          at this point.  Presumably we don't need to worry about it.  */
2670       if (use0 && use1)
2671         {
2672           tree *tmp = USE_OP_PTR (use1)->use;
2673           USE_OP_PTR (use1)->use = USE_OP_PTR (use0)->use;
2674           USE_OP_PTR (use0)->use = tmp;
2675         }
2676     }
2677
2678   /* Now swap the data.  */
2679   *exp0 = op1;
2680   *exp1 = op0;
2681 }
2682
2683
2684 /* Add the base address of REF to the set *ADDRESSES_TAKEN.  If
2685    *ADDRESSES_TAKEN is NULL, a new set is created.  REF may be
2686    a single variable whose address has been taken or any other valid
2687    GIMPLE memory reference (structure reference, array, etc).  If the
2688    base address of REF is a decl that has sub-variables, also add all
2689    of its sub-variables.  */
2690
2691 void
2692 add_to_addressable_set (tree ref, bitmap *addresses_taken)
2693 {
2694   tree var;
2695   subvar_t svars;
2696
2697   gcc_assert (addresses_taken);
2698
2699   /* Note that it is *NOT OKAY* to use the target of a COMPONENT_REF
2700      as the only thing we take the address of.  If VAR is a structure,
2701      taking the address of a field means that the whole structure may
2702      be referenced using pointer arithmetic.  See PR 21407 and the
2703      ensuing mailing list discussion.  */
2704   var = get_base_address (ref);
2705   if (var && SSA_VAR_P (var))
2706     {
2707       if (*addresses_taken == NULL)
2708         *addresses_taken = BITMAP_GGC_ALLOC ();      
2709       
2710       if (var_can_have_subvars (var)
2711           && (svars = get_subvars_for_var (var)))
2712         {
2713           subvar_t sv;
2714           for (sv = svars; sv; sv = sv->next)
2715             {
2716               bitmap_set_bit (*addresses_taken, DECL_UID (sv->var));
2717               TREE_ADDRESSABLE (sv->var) = 1;
2718             }
2719         }
2720       else
2721         {
2722           bitmap_set_bit (*addresses_taken, DECL_UID (var));
2723           TREE_ADDRESSABLE (var) = 1;
2724         }
2725     }
2726 }
2727
2728
2729 /* Scan the immediate_use list for VAR making sure its linked properly.
2730    Return TRUE if there is a problem and emit an error message to F.  */
2731
2732 bool
2733 verify_imm_links (FILE *f, tree var)
2734 {
2735   use_operand_p ptr, prev, list;
2736   int count;
2737
2738   gcc_assert (TREE_CODE (var) == SSA_NAME);
2739
2740   list = &(SSA_NAME_IMM_USE_NODE (var));
2741   gcc_assert (list->use == NULL);
2742
2743   if (list->prev == NULL)
2744     {
2745       gcc_assert (list->next == NULL);
2746       return false;
2747     }
2748
2749   prev = list;
2750   count = 0;
2751   for (ptr = list->next; ptr != list; )
2752     {
2753       if (prev != ptr->prev)
2754         goto error;
2755       
2756       if (ptr->use == NULL)
2757         goto error; /* 2 roots, or SAFE guard node.  */
2758       else if (*(ptr->use) != var)
2759         goto error;
2760
2761       prev = ptr;
2762       ptr = ptr->next;
2763
2764       /* Avoid infinite loops.  50,000,000 uses probably indicates a
2765          problem.  */
2766       if (count++ > 50000000)
2767         goto error;
2768     }
2769
2770   /* Verify list in the other direction.  */
2771   prev = list;
2772   for (ptr = list->prev; ptr != list; )
2773     {
2774       if (prev != ptr->next)
2775         goto error;
2776       prev = ptr;
2777       ptr = ptr->prev;
2778       if (count-- < 0)
2779         goto error;
2780     }
2781
2782   if (count != 0)
2783     goto error;
2784
2785   return false;
2786
2787  error:
2788   if (ptr->stmt && stmt_modified_p (ptr->stmt))
2789     {
2790       fprintf (f, " STMT MODIFIED. - <%p> ", (void *)ptr->stmt);
2791       print_generic_stmt (f, ptr->stmt, TDF_SLIM);
2792     }
2793   fprintf (f, " IMM ERROR : (use_p : tree - %p:%p)", (void *)ptr, 
2794            (void *)ptr->use);
2795   print_generic_expr (f, USE_FROM_PTR (ptr), TDF_SLIM);
2796   fprintf(f, "\n");
2797   return true;
2798 }
2799
2800
2801 /* Dump all the immediate uses to FILE.  */
2802
2803 void
2804 dump_immediate_uses_for (FILE *file, tree var)
2805 {
2806   imm_use_iterator iter;
2807   use_operand_p use_p;
2808
2809   gcc_assert (var && TREE_CODE (var) == SSA_NAME);
2810
2811   print_generic_expr (file, var, TDF_SLIM);
2812   fprintf (file, " : -->");
2813   if (has_zero_uses (var))
2814     fprintf (file, " no uses.\n");
2815   else
2816     if (has_single_use (var))
2817       fprintf (file, " single use.\n");
2818     else
2819       fprintf (file, "%d uses.\n", num_imm_uses (var));
2820
2821   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
2822     {
2823       if (use_p->stmt == NULL && use_p->use == NULL)
2824         fprintf (file, "***end of stmt iterator marker***\n");
2825       else
2826         if (!is_gimple_reg (USE_FROM_PTR (use_p)))
2827           print_generic_stmt (file, USE_STMT (use_p), TDF_VOPS|TDF_MEMSYMS);
2828         else
2829           print_generic_stmt (file, USE_STMT (use_p), TDF_SLIM);
2830     }
2831   fprintf(file, "\n");
2832 }
2833
2834
2835 /* Dump all the immediate uses to FILE.  */
2836
2837 void
2838 dump_immediate_uses (FILE *file)
2839 {
2840   tree var;
2841   unsigned int x;
2842
2843   fprintf (file, "Immediate_uses: \n\n");
2844   for (x = 1; x < num_ssa_names; x++)
2845     {
2846       var = ssa_name(x);
2847       if (!var)
2848         continue;
2849       dump_immediate_uses_for (file, var);
2850     }
2851 }
2852
2853
2854 /* Dump def-use edges on stderr.  */
2855
2856 void
2857 debug_immediate_uses (void)
2858 {
2859   dump_immediate_uses (stderr);
2860 }
2861
2862
2863 /* Dump def-use edges on stderr.  */
2864
2865 void
2866 debug_immediate_uses_for (tree var)
2867 {
2868   dump_immediate_uses_for (stderr, var);
2869 }
2870
2871
2872 /* Create a new change buffer for the statement pointed by STMT_P and
2873    push the buffer into SCB_STACK.  Each change buffer
2874    records state information needed to determine what changed in the
2875    statement.  Mainly, this keeps track of symbols that may need to be
2876    put into SSA form, SSA name replacements and other information
2877    needed to keep the SSA form up to date.  */
2878
2879 void
2880 push_stmt_changes (tree *stmt_p)
2881 {
2882   tree stmt;
2883   scb_t buf;
2884   
2885   stmt = *stmt_p;
2886
2887   /* It makes no sense to keep track of PHI nodes.  */
2888   if (TREE_CODE (stmt) == PHI_NODE)
2889     return;
2890
2891   buf = XNEW (struct scb_d);
2892   memset (buf, 0, sizeof *buf);
2893
2894   buf->stmt_p = stmt_p;
2895
2896   if (stmt_references_memory_p (stmt))
2897     {
2898       tree op;
2899       ssa_op_iter i;
2900
2901       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VUSE)
2902         {
2903           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
2904           if (buf->loads == NULL)
2905             buf->loads = BITMAP_ALLOC (NULL);
2906           bitmap_set_bit (buf->loads, DECL_UID (sym));
2907         }
2908
2909       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VDEF)
2910         {
2911           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
2912           if (buf->stores == NULL)
2913             buf->stores = BITMAP_ALLOC (NULL);
2914           bitmap_set_bit (buf->stores, DECL_UID (sym));
2915         }
2916     }
2917
2918   VEC_safe_push (scb_t, heap, scb_stack, buf);
2919 }
2920
2921
2922 /* Given two sets S1 and S2, mark the symbols that differ in S1 and S2
2923    for renaming.  The set to mark for renaming is (S1 & ~S2) | (S2 & ~S1).  */
2924
2925 static void
2926 mark_difference_for_renaming (bitmap s1, bitmap s2)
2927 {
2928   if (s1 == NULL && s2 == NULL)
2929     return;
2930
2931   if (s1 && s2 == NULL)
2932     mark_set_for_renaming (s1);
2933   else if (s1 == NULL && s2)
2934     mark_set_for_renaming (s2);
2935   else if (!bitmap_equal_p (s1, s2))
2936     {
2937       bitmap t1 = BITMAP_ALLOC (NULL);
2938       bitmap t2 = BITMAP_ALLOC (NULL);
2939
2940       bitmap_and_compl (t1, s1, s2);
2941       bitmap_and_compl (t2, s2, s1);
2942       bitmap_ior_into (t1, t2);
2943       mark_set_for_renaming (t1);
2944
2945       BITMAP_FREE (t1);
2946       BITMAP_FREE (t2);
2947     }
2948 }
2949
2950
2951 /* Pop the top SCB from SCB_STACK and act on the differences between
2952    what was recorded by push_stmt_changes and the current state of
2953    the statement.  */
2954
2955 void
2956 pop_stmt_changes (tree *stmt_p)
2957 {
2958   tree op, stmt;
2959   ssa_op_iter iter;
2960   bitmap loads, stores;
2961   scb_t buf;
2962
2963   stmt = *stmt_p;
2964
2965   /* It makes no sense to keep track of PHI nodes.  */
2966   if (TREE_CODE (stmt) == PHI_NODE)
2967     return;
2968
2969   buf = VEC_pop (scb_t, scb_stack);
2970   gcc_assert (stmt_p == buf->stmt_p);
2971
2972   /* Force an operand re-scan on the statement and mark any newly
2973      exposed variables.  */
2974   update_stmt (stmt);
2975
2976   /* Determine whether any memory symbols need to be renamed.  If the
2977      sets of loads and stores are different after the statement is
2978      modified, then the affected symbols need to be renamed.
2979      
2980      Note that it may be possible for the statement to not reference
2981      memory anymore, but we still need to act on the differences in
2982      the sets of symbols.  */
2983   loads = stores = NULL;
2984   if (stmt_references_memory_p (stmt))
2985     {
2986       tree op;
2987       ssa_op_iter i;
2988
2989       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VUSE)
2990         {
2991           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
2992           if (loads == NULL)
2993             loads = BITMAP_ALLOC (NULL);
2994           bitmap_set_bit (loads, DECL_UID (sym));
2995         }
2996
2997       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VDEF)
2998         {
2999           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
3000           if (stores == NULL)
3001             stores = BITMAP_ALLOC (NULL);
3002           bitmap_set_bit (stores, DECL_UID (sym));
3003         }
3004     }
3005
3006   /* If LOADS is different from BUF->LOADS, the affected
3007      symbols need to be marked for renaming.  */
3008   mark_difference_for_renaming (loads, buf->loads);
3009
3010   /* Similarly for STORES and BUF->STORES.  */
3011   mark_difference_for_renaming (stores, buf->stores);
3012
3013   /* Mark all the naked GIMPLE register operands for renaming.  */
3014   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF|SSA_OP_USE)
3015     if (DECL_P (op))
3016       mark_sym_for_renaming (op);
3017
3018   /* FIXME, need to add more finalizers here.  Cleanup EH info,
3019      recompute invariants for address expressions, add
3020      SSA replacement mappings, etc.  For instance, given
3021      testsuite/gcc.c-torture/compile/pr16808.c, we fold a statement of
3022      the form:
3023
3024           # SMT.4_20 = VDEF <SMT.4_16>
3025           D.1576_11 = 1.0e+0;
3026
3027      So, the VDEF will disappear, but instead of marking SMT.4 for
3028      renaming it would be far more efficient to establish a
3029      replacement mapping that would replace every reference of
3030      SMT.4_20 with SMT.4_16.  */
3031
3032   /* Free memory used by the buffer.  */
3033   BITMAP_FREE (buf->loads);
3034   BITMAP_FREE (buf->stores);
3035   BITMAP_FREE (loads);
3036   BITMAP_FREE (stores);
3037   buf->stmt_p = NULL;
3038   free (buf);
3039 }
3040
3041
3042 /* Discard the topmost change buffer from SCB_STACK.  This is useful
3043    when the caller realized that it did not actually modified the
3044    statement.  It avoids the expensive operand re-scan.  */
3045
3046 void
3047 discard_stmt_changes (tree *stmt_p)
3048 {
3049   scb_t buf;
3050   tree stmt;
3051   
3052   /* It makes no sense to keep track of PHI nodes.  */
3053   stmt = *stmt_p;
3054   if (TREE_CODE (stmt) == PHI_NODE)
3055     return;
3056
3057   buf = VEC_pop (scb_t, scb_stack);
3058   gcc_assert (stmt_p == buf->stmt_p);
3059
3060   /* Free memory used by the buffer.  */
3061   BITMAP_FREE (buf->loads);
3062   BITMAP_FREE (buf->stores);
3063   buf->stmt_p = NULL;
3064   free (buf);
3065 }
3066
3067
3068 /* Returns true if statement STMT may access memory.  */
3069
3070 bool
3071 stmt_references_memory_p (tree stmt)
3072 {
3073   if (!gimple_ssa_operands (cfun)->ops_active || TREE_CODE (stmt) == PHI_NODE)
3074     return false;
3075
3076   return stmt_ann (stmt)->references_memory;
3077 }