OSDN Git Service

87eec7452b7781b8ab102afbd4034a399e16084d
[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
74    operand vector for VUSE, then the new vector will also be modified
75    such that 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
619    initialized to OP and are linked into the immediate uses for STMT.
620    The new vop is appended 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 var, unsigned HOST_WIDE_INT offset,
1393                      unsigned HOST_WIDE_INT size, bool is_def)
1394 {
1395   bool added = false;
1396   tree subvar;
1397   subvar_t sv;
1398   unsigned int i;
1399
1400   if (SFT_IN_NESTED_STRUCT (var))
1401     {
1402       /* Since VAR is an SFT inside a nested structure, the OFFSET
1403          computed by get_ref_base_and_extent is the offset from the
1404          start of the immediately containing structure.  However, to
1405          find out what other SFTs are affected by this reference, we
1406          need to know the offsets starting at the root structure in
1407          the nesting hierarchy.
1408
1409          For instance, given the following structure:
1410
1411                 struct X {
1412                   int a;
1413                   struct Y {
1414                     int b;
1415                     struct Z {
1416                       int c[3];
1417                     } d;
1418                   } e;
1419                 } m;
1420
1421          and the following address expression:
1422
1423                 p_1 = &m.e.d;
1424
1425          This structure will receive 5 SFTs, namely 2 for fields 'a'
1426          and 'b' and 3 for the array 'c' in struct Z.  So, the
1427          reference p_1->c[2] and m.e.d.c[2] access the exact same
1428          memory location (ie, SFT.5).
1429
1430          Now, alias analysis computed the points-to set for pointer
1431          p_1 as  { SFT.3 } because that is the first field that p_1
1432          actually points to.  When the expression p_1->c[2] is
1433          analyzed, get_ref_base_and_extent will return an offset of 96
1434          because we are accessing the third element of the array.  But
1435          the SFT we are looking for is actually at offset 160,
1436          counting from the top of struct X.
1437
1438          Therefore, we adjust OFFSET by the offset of VAR so that we
1439          can get at all the fields starting at VAR.  */
1440       offset += SFT_OFFSET (var);
1441     }
1442
1443   /* Add all subvars of var that overlap with the access.
1444      Binary search for the first relevant SFT.  */
1445   sv = get_subvars_for_var (SFT_PARENT_VAR (var));
1446   if (!get_first_overlapping_subvar (sv, offset, size, &i))
1447     return false;
1448
1449   for (; VEC_iterate (tree, sv, i, subvar); ++i)
1450     {
1451       if (SFT_OFFSET (subvar) > offset
1452           && size <= SFT_OFFSET (subvar) - offset)
1453         break;
1454
1455       if (is_def)
1456         append_vdef (subvar);
1457       else
1458         append_vuse (subvar);
1459       added = true;
1460     }
1461
1462   return added;
1463 }
1464
1465
1466 /* Add VAR to the virtual operands array.  FLAGS is as in
1467    get_expr_operands.  FULL_REF is a tree that contains the entire
1468    pointer dereference expression, if available, or NULL otherwise.
1469    OFFSET and SIZE come from the memory access expression that
1470    generated this virtual operand.  IS_CALL_SITE is true if the
1471    affected statement is a call site.  */
1472
1473 static void
1474 add_virtual_operand (tree var, stmt_ann_t s_ann, int flags,
1475                      tree full_ref, HOST_WIDE_INT offset,
1476                      HOST_WIDE_INT size, bool is_call_site)
1477 {
1478   bitmap aliases = NULL;
1479   tree sym;
1480   var_ann_t v_ann;
1481   
1482   sym = (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
1483   v_ann = var_ann (sym);
1484   
1485   /* Mark the statement as having memory operands.  */
1486   s_ann->references_memory = true;
1487
1488   /* If the variable cannot be modified and this is a VDEF change
1489      it into a VUSE.  This happens when read-only variables are marked
1490      call-clobbered and/or aliased to writable variables.  So we only
1491      check that this only happens on non-specific stores.
1492
1493      Note that if this is a specific store, i.e. associated with a
1494      GIMPLE_MODIFY_STMT, then we can't suppress the VDEF, lest we run
1495      into validation problems.
1496
1497      This can happen when programs cast away const, leaving us with a
1498      store to read-only memory.  If the statement is actually executed
1499      at runtime, then the program is ill formed.  If the statement is
1500      not executed then all is well.  At the very least, we cannot ICE.  */
1501   if ((flags & opf_implicit) && unmodifiable_var_p (var))
1502     flags &= ~opf_def;
1503   
1504   /* The variable is not a GIMPLE register.  Add it (or its aliases) to
1505      virtual operands, unless the caller has specifically requested
1506      not to add virtual operands (used when adding operands inside an
1507      ADDR_EXPR expression).  */
1508   if (flags & opf_no_vops)
1509     return;
1510   
1511   if (MTAG_P (var))
1512     aliases = MTAG_ALIASES (var);
1513
1514   if (aliases == NULL)
1515     {
1516       if (!gimple_aliases_computed_p (cfun)
1517           && (flags & opf_def))
1518         s_ann->has_volatile_ops = true;
1519
1520       /* The variable is not aliased or it is an alias tag.  */
1521       if (flags & opf_def)
1522         append_vdef (var);
1523       else
1524         append_vuse (var);
1525     }
1526   else
1527     {
1528       bitmap_iterator bi;
1529       unsigned int i;
1530       bool none_added = true;
1531       
1532       /* The variable is aliased.  Add its aliases to the virtual
1533          operands.  */
1534       gcc_assert (!bitmap_empty_p (aliases));
1535
1536       EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
1537         {
1538           tree al = referenced_var (i);
1539
1540           /* For SFTs we have to consider all subvariables of the parent var
1541              if it is a potential points-to location.  */
1542           if (TREE_CODE (al) == STRUCT_FIELD_TAG
1543               && TREE_CODE (var) == NAME_MEMORY_TAG)
1544             none_added &= !add_vars_for_offset (al, offset, size,
1545                                                 flags & opf_def);
1546           else
1547             {
1548               /* Call-clobbered tags may have non-call-clobbered
1549                  symbols in their alias sets.  Ignore them if we are
1550                  adding VOPs for a call site.  */
1551               if (is_call_site && !is_call_clobbered (al))
1552                  continue;
1553
1554               /* If we do not know the full reference tree or if the access is
1555                  unspecified [0, -1], we cannot prune it.  Otherwise try doing
1556                  so using access_can_touch_variable.  */
1557               if (full_ref
1558                   && !(offset == 0 && size == -1)
1559                   && !access_can_touch_variable (full_ref, al, offset, size))
1560                 continue;
1561
1562               if (flags & opf_def)
1563                 append_vdef (al);
1564               else
1565                 append_vuse (al);
1566               none_added = false;
1567             }
1568         }
1569
1570       if (flags & opf_def)
1571         {
1572           /* If the variable is also an alias tag, add a virtual
1573              operand for it, otherwise we will miss representing
1574              references to the members of the variable's alias set.          
1575              This fixes the bug in gcc.c-torture/execute/20020503-1.c.
1576              
1577              It is also necessary to add bare defs on clobbers for
1578              SMT's, so that bare SMT uses caused by pruning all the
1579              aliases will link up properly with calls.   In order to
1580              keep the number of these bare defs we add down to the
1581              minimum necessary, we keep track of which SMT's were used
1582              alone in statement vdefs or VUSEs.  */
1583           if (none_added
1584               || (TREE_CODE (var) == SYMBOL_MEMORY_TAG
1585                   && is_call_site))
1586             append_vdef (var);
1587         }
1588       else
1589         {
1590           /* Even if no aliases have been added, we still need to
1591              establish def-use and use-def chains, lest
1592              transformations think that this is not a memory
1593              reference.  For an example of this scenario, see
1594              testsuite/g++.dg/opt/cleanup1.C.  */
1595           if (none_added)
1596             append_vuse (var);
1597         }
1598     }
1599 }
1600
1601
1602 /* Add *VAR_P to the appropriate operand array for S_ANN.  FLAGS is as in
1603    get_expr_operands.  If *VAR_P is a GIMPLE register, it will be added to
1604    the statement's real operands, otherwise it is added to virtual
1605    operands.  */
1606
1607 static void
1608 add_stmt_operand (tree *var_p, stmt_ann_t s_ann, int flags)
1609 {
1610   tree var, sym;
1611   var_ann_t v_ann;
1612
1613   gcc_assert (SSA_VAR_P (*var_p) && s_ann);
1614
1615   var = *var_p;
1616   sym = (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
1617   v_ann = var_ann (sym);
1618
1619   /* Mark statements with volatile operands.  */
1620   if (TREE_THIS_VOLATILE (sym))
1621     s_ann->has_volatile_ops = true;
1622
1623   if (is_gimple_reg (sym))
1624     {
1625       /* The variable is a GIMPLE register.  Add it to real operands.  */
1626       if (flags & opf_def)
1627         append_def (var_p);
1628       else
1629         append_use (var_p);
1630     }
1631   else
1632     add_virtual_operand (var, s_ann, flags, NULL_TREE, 0, -1, false);
1633 }
1634
1635 /* Subroutine of get_indirect_ref_operands.  ADDR is the address
1636    that is dereferenced, the meaning of the rest of the arguments
1637    is the same as in get_indirect_ref_operands.  */
1638
1639 static void
1640 get_addr_dereference_operands (tree stmt, tree *addr, int flags, tree full_ref,
1641                                HOST_WIDE_INT offset, HOST_WIDE_INT size,
1642                                bool recurse_on_base)
1643 {
1644   tree ptr = *addr;
1645   stmt_ann_t s_ann = stmt_ann (stmt);
1646
1647   s_ann->references_memory = true;
1648
1649   if (SSA_VAR_P (ptr))
1650     {
1651       struct ptr_info_def *pi = NULL;
1652
1653       /* If PTR has flow-sensitive points-to information, use it.  */
1654       if (TREE_CODE (ptr) == SSA_NAME
1655           && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1656           && pi->name_mem_tag)
1657         {
1658           /* PTR has its own memory tag.  Use it.  */
1659           add_virtual_operand (pi->name_mem_tag, s_ann, flags,
1660                                full_ref, offset, size, false);
1661         }
1662       else
1663         {
1664           /* If PTR is not an SSA_NAME or it doesn't have a name
1665              tag, use its symbol memory tag.  */
1666           var_ann_t v_ann;
1667
1668           /* If we are emitting debugging dumps, display a warning if
1669              PTR is an SSA_NAME with no flow-sensitive alias
1670              information.  That means that we may need to compute
1671              aliasing again.  */
1672           if (dump_file
1673               && TREE_CODE (ptr) == SSA_NAME
1674               && pi == NULL)
1675             {
1676               fprintf (dump_file,
1677                   "NOTE: no flow-sensitive alias info for ");
1678               print_generic_expr (dump_file, ptr, dump_flags);
1679               fprintf (dump_file, " in ");
1680               print_generic_stmt (dump_file, stmt, dump_flags);
1681             }
1682
1683           if (TREE_CODE (ptr) == SSA_NAME)
1684             ptr = SSA_NAME_VAR (ptr);
1685           v_ann = var_ann (ptr);
1686
1687           /* If we don't know what this pointer points to then we have
1688              to make sure to not prune virtual operands based on offset
1689              and size.  */
1690           if (v_ann->symbol_mem_tag)
1691             add_virtual_operand (v_ann->symbol_mem_tag, s_ann, flags,
1692                                  full_ref, 0, -1, false);
1693
1694           /* Aliasing information is missing; mark statement as
1695              volatile so we won't optimize it out too actively.  */
1696           else if (!gimple_aliases_computed_p (cfun)
1697                    && (flags & opf_def))
1698             s_ann->has_volatile_ops = true;
1699         }
1700     }
1701   else if (TREE_CODE (ptr) == INTEGER_CST)
1702     {
1703       /* If a constant is used as a pointer, we can't generate a real
1704          operand for it but we mark the statement volatile to prevent
1705          optimizations from messing things up.  */
1706       s_ann->has_volatile_ops = true;
1707       return;
1708     }
1709   else
1710     {
1711       /* Ok, this isn't even is_gimple_min_invariant.  Something's broke.  */
1712       gcc_unreachable ();
1713     }
1714
1715   /* If requested, add a USE operand for the base pointer.  */
1716   if (recurse_on_base)
1717     get_expr_operands (stmt, addr, opf_use);
1718 }
1719
1720
1721 /* A subroutine of get_expr_operands to handle INDIRECT_REF,
1722    ALIGN_INDIRECT_REF and MISALIGNED_INDIRECT_REF.  
1723
1724    STMT is the statement being processed, EXPR is the INDIRECT_REF
1725       that got us here.
1726    
1727    FLAGS is as in get_expr_operands.
1728
1729    FULL_REF contains the full pointer dereference expression, if we
1730       have it, or NULL otherwise.
1731
1732    OFFSET and SIZE are the location of the access inside the
1733       dereferenced pointer, if known.
1734
1735    RECURSE_ON_BASE should be set to true if we want to continue
1736       calling get_expr_operands on the base pointer, and false if
1737       something else will do it for us.  */
1738
1739 static void
1740 get_indirect_ref_operands (tree stmt, tree expr, int flags, tree full_ref,
1741                            HOST_WIDE_INT offset, HOST_WIDE_INT size,
1742                            bool recurse_on_base)
1743 {
1744   tree *pptr = &TREE_OPERAND (expr, 0);
1745   stmt_ann_t s_ann = stmt_ann (stmt);
1746
1747   if (TREE_THIS_VOLATILE (expr))
1748     s_ann->has_volatile_ops = true; 
1749
1750   get_addr_dereference_operands (stmt, pptr, flags, full_ref, offset, size,
1751                                  recurse_on_base);
1752 }
1753
1754
1755 /* A subroutine of get_expr_operands to handle TARGET_MEM_REF.  */
1756
1757 static void
1758 get_tmr_operands (tree stmt, tree expr, int flags)
1759 {
1760   tree tag;
1761   stmt_ann_t s_ann = stmt_ann (stmt);
1762
1763   /* This statement references memory.  */
1764   s_ann->references_memory = 1;
1765
1766   /* First record the real operands.  */
1767   get_expr_operands (stmt, &TMR_BASE (expr), opf_use);
1768   get_expr_operands (stmt, &TMR_INDEX (expr), opf_use);
1769
1770   if (TMR_SYMBOL (expr))
1771     add_to_addressable_set (TMR_SYMBOL (expr), &s_ann->addresses_taken);
1772
1773   tag = TMR_TAG (expr);
1774   if (!tag)
1775     {
1776       /* Something weird, so ensure that we will be careful.  */
1777       s_ann->has_volatile_ops = true;
1778       return;
1779     }
1780   if (!MTAG_P (tag))
1781     {
1782       get_expr_operands (stmt, &tag, flags);
1783       return;
1784     }
1785
1786   add_virtual_operand (tag, s_ann, flags, expr, 0, -1, false);
1787 }
1788
1789
1790 /* Add clobbering definitions for .GLOBAL_VAR or for each of the call
1791    clobbered variables in the function.  */
1792
1793 static void
1794 add_call_clobber_ops (tree stmt, tree callee)
1795 {
1796   unsigned u;
1797   bitmap_iterator bi;
1798   stmt_ann_t s_ann = stmt_ann (stmt);
1799   bitmap not_read_b, not_written_b;
1800   
1801   /* If we created .GLOBAL_VAR earlier, just use it.  */
1802   if (gimple_global_var (cfun))
1803     {
1804       tree var = gimple_global_var (cfun);
1805       add_virtual_operand (var, s_ann, opf_def, NULL, 0, -1, true);
1806       return;
1807     }
1808
1809   /* Get info for local and module level statics.  There is a bit
1810      set for each static if the call being processed does not read
1811      or write that variable.  */
1812   not_read_b = callee ? ipa_reference_get_not_read_global (callee) : NULL; 
1813   not_written_b = callee ? ipa_reference_get_not_written_global (callee) : NULL; 
1814
1815   /* Add a VDEF operand for every call clobbered variable.  */
1816   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, u, bi)
1817     {
1818       tree var = referenced_var_lookup (u);
1819       unsigned int escape_mask = var_ann (var)->escape_mask;
1820       tree real_var = var;
1821       bool not_read;
1822       bool not_written;
1823       
1824       /* Not read and not written are computed on regular vars, not
1825          subvars, so look at the parent var if this is an SFT. */
1826       if (TREE_CODE (var) == STRUCT_FIELD_TAG)
1827         real_var = SFT_PARENT_VAR (var);
1828
1829       not_read = not_read_b
1830                  ? bitmap_bit_p (not_read_b, DECL_UID (real_var))
1831                  : false;
1832
1833       not_written = not_written_b
1834                     ? bitmap_bit_p (not_written_b, DECL_UID (real_var))
1835                     : false;
1836       gcc_assert (!unmodifiable_var_p (var));
1837       
1838       clobber_stats.clobbered_vars++;
1839
1840       /* See if this variable is really clobbered by this function.  */
1841
1842       /* Trivial case: Things escaping only to pure/const are not
1843          clobbered by non-pure-const, and only read by pure/const. */
1844       if ((escape_mask & ~(ESCAPE_TO_PURE_CONST)) == 0)
1845         {
1846           tree call = get_call_expr_in (stmt);
1847           if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1848             {
1849               add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1850               clobber_stats.unescapable_clobbers_avoided++;
1851               continue;
1852             }
1853           else
1854             {
1855               clobber_stats.unescapable_clobbers_avoided++;
1856               continue;
1857             }
1858         }
1859             
1860       if (not_written)
1861         {
1862           clobber_stats.static_write_clobbers_avoided++;
1863           if (!not_read)
1864             add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1865           else
1866             clobber_stats.static_read_clobbers_avoided++;
1867         }
1868       else
1869         add_virtual_operand (var, s_ann, opf_def, NULL, 0, -1, true);
1870     }
1871 }
1872
1873
1874 /* Add VUSE operands for .GLOBAL_VAR or all call clobbered variables in the
1875    function.  */
1876
1877 static void
1878 add_call_read_ops (tree stmt, tree callee)
1879 {
1880   unsigned u;
1881   bitmap_iterator bi;
1882   stmt_ann_t s_ann = stmt_ann (stmt);
1883   bitmap not_read_b;
1884
1885   /* if the function is not pure, it may reference memory.  Add
1886      a VUSE for .GLOBAL_VAR if it has been created.  See add_referenced_var
1887      for the heuristic used to decide whether to create .GLOBAL_VAR.  */
1888   if (gimple_global_var (cfun))
1889     {
1890       tree var = gimple_global_var (cfun);
1891       add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1892       return;
1893     }
1894   
1895   not_read_b = callee ? ipa_reference_get_not_read_global (callee) : NULL; 
1896
1897   /* Add a VUSE for each call-clobbered variable.  */
1898   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, u, bi)
1899     {
1900       tree var = referenced_var (u);
1901       tree real_var = var;
1902       bool not_read;
1903       
1904       clobber_stats.readonly_clobbers++;
1905
1906       /* Not read and not written are computed on regular vars, not
1907          subvars, so look at the parent var if this is an SFT. */
1908
1909       if (TREE_CODE (var) == STRUCT_FIELD_TAG)
1910         real_var = SFT_PARENT_VAR (var);
1911
1912       not_read = not_read_b ? bitmap_bit_p (not_read_b, DECL_UID (real_var))
1913                             : false;
1914       
1915       if (not_read)
1916         {
1917           clobber_stats.static_readonly_clobbers_avoided++;
1918           continue;
1919         }
1920             
1921       add_virtual_operand (var, s_ann, opf_use, NULL, 0, -1, true);
1922     }
1923 }
1924
1925
1926 /* A subroutine of get_expr_operands to handle CALL_EXPR.  */
1927
1928 static void
1929 get_call_expr_operands (tree stmt, tree expr)
1930 {
1931   int call_flags = call_expr_flags (expr);
1932   int i, nargs;
1933   stmt_ann_t ann = stmt_ann (stmt);
1934
1935   ann->references_memory = true;
1936
1937   /* If aliases have been computed already, add VDEF or VUSE
1938      operands for all the symbols that have been found to be
1939      call-clobbered.  */
1940   if (gimple_aliases_computed_p (cfun)
1941       && !(call_flags & ECF_NOVOPS))
1942     {
1943       /* A 'pure' or a 'const' function never call-clobbers anything. 
1944          A 'noreturn' function might, but since we don't return anyway 
1945          there is no point in recording that.  */ 
1946       if (TREE_SIDE_EFFECTS (expr)
1947           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1948         add_call_clobber_ops (stmt, get_callee_fndecl (expr));
1949       else if (!(call_flags & ECF_CONST))
1950         add_call_read_ops (stmt, get_callee_fndecl (expr));
1951     }
1952
1953   /* Find uses in the called function.  */
1954   get_expr_operands (stmt, &CALL_EXPR_FN (expr), opf_use);
1955   nargs = call_expr_nargs (expr);
1956   for (i = 0; i < nargs; i++)
1957     get_expr_operands (stmt, &CALL_EXPR_ARG (expr, i), opf_use);
1958
1959   get_expr_operands (stmt, &CALL_EXPR_STATIC_CHAIN (expr), opf_use);
1960 }
1961
1962
1963 /* Scan operands in the ASM_EXPR stmt referred to in INFO.  */
1964
1965 static void
1966 get_asm_expr_operands (tree stmt)
1967 {
1968   stmt_ann_t s_ann;
1969   int i, noutputs;
1970   const char **oconstraints;
1971   const char *constraint;
1972   bool allows_mem, allows_reg, is_inout;
1973   tree link;
1974
1975   s_ann = stmt_ann (stmt);
1976   noutputs = list_length (ASM_OUTPUTS (stmt));
1977   oconstraints = (const char **) alloca ((noutputs) * sizeof (const char *));
1978
1979   /* Gather all output operands.  */
1980   for (i = 0, link = ASM_OUTPUTS (stmt); link; i++, link = TREE_CHAIN (link))
1981     {
1982       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1983       oconstraints[i] = constraint;
1984       parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
1985                                &allows_reg, &is_inout);
1986
1987       /* This should have been split in gimplify_asm_expr.  */
1988       gcc_assert (!allows_reg || !is_inout);
1989
1990       /* Memory operands are addressable.  Note that STMT needs the
1991          address of this operand.  */
1992       if (!allows_reg && allows_mem)
1993         {
1994           tree t = get_base_address (TREE_VALUE (link));
1995           if (t && DECL_P (t) && s_ann)
1996             add_to_addressable_set (t, &s_ann->addresses_taken);
1997         }
1998
1999       get_expr_operands (stmt, &TREE_VALUE (link), opf_def);
2000     }
2001
2002   /* Gather all input operands.  */
2003   for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
2004     {
2005       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
2006       parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
2007                               &allows_mem, &allows_reg);
2008
2009       /* Memory operands are addressable.  Note that STMT needs the
2010          address of this operand.  */
2011       if (!allows_reg && allows_mem)
2012         {
2013           tree t = get_base_address (TREE_VALUE (link));
2014           if (t && DECL_P (t) && s_ann)
2015             add_to_addressable_set (t, &s_ann->addresses_taken);
2016         }
2017
2018       get_expr_operands (stmt, &TREE_VALUE (link), 0);
2019     }
2020
2021   /* Clobber all memory and addressable symbols for asm ("" : : : "memory");  */
2022   for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
2023     if (strcmp (TREE_STRING_POINTER (TREE_VALUE (link)), "memory") == 0)
2024       {
2025         unsigned i;
2026         bitmap_iterator bi;
2027
2028         s_ann->references_memory = true;
2029
2030         EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
2031           {
2032             tree var = referenced_var (i);
2033             add_stmt_operand (&var, s_ann, opf_def | opf_implicit);
2034           }
2035
2036         EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
2037           {
2038             tree var = referenced_var (i);
2039
2040             /* Subvars are explicitly represented in this list, so we
2041                don't need the original to be added to the clobber ops,
2042                but the original *will* be in this list because we keep
2043                the addressability of the original variable up-to-date
2044                to avoid confusing the back-end.  */
2045             if (var_can_have_subvars (var)
2046                 && get_subvars_for_var (var) != NULL)
2047               continue;         
2048
2049             add_stmt_operand (&var, s_ann, opf_def | opf_implicit);
2050           }
2051         break;
2052       }
2053 }
2054
2055
2056 /* Scan operands for the assignment expression EXPR in statement STMT.  */
2057
2058 static void
2059 get_modify_stmt_operands (tree stmt, tree expr)
2060 {
2061   /* First get operands from the RHS.  */
2062   get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (expr, 1), opf_use);
2063
2064   /* For the LHS, use a regular definition (opf_def) for GIMPLE
2065      registers.  If the LHS is a store to memory, we will need
2066      a preserving definition (VDEF).
2067
2068      Preserving definitions are those that modify a part of an
2069      aggregate object for which no subvars have been computed (or the
2070      reference does not correspond exactly to one of them). Stores
2071      through a pointer are also represented with VDEF operators.
2072
2073      We used to distinguish between preserving and killing definitions.
2074      We always emit preserving definitions now.  */
2075   get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (expr, 0), opf_def);
2076 }
2077
2078
2079 /* Recursively scan the expression pointed to by EXPR_P in statement
2080    STMT.  FLAGS is one of the OPF_* constants modifying how to
2081    interpret the operands found.  */
2082
2083 static void
2084 get_expr_operands (tree stmt, tree *expr_p, int flags)
2085 {
2086   enum tree_code code;
2087   enum tree_code_class codeclass;
2088   tree expr = *expr_p;
2089   stmt_ann_t s_ann = stmt_ann (stmt);
2090
2091   if (expr == NULL)
2092     return;
2093
2094   code = TREE_CODE (expr);
2095   codeclass = TREE_CODE_CLASS (code);
2096
2097   switch (code)
2098     {
2099     case ADDR_EXPR:
2100       /* Taking the address of a variable does not represent a
2101          reference to it, but the fact that the statement takes its
2102          address will be of interest to some passes (e.g. alias
2103          resolution).  */
2104       add_to_addressable_set (TREE_OPERAND (expr, 0), &s_ann->addresses_taken);
2105
2106       /* If the address is invariant, there may be no interesting
2107          variable references inside.  */
2108       if (is_gimple_min_invariant (expr))
2109         return;
2110
2111       /* Otherwise, there may be variables referenced inside but there
2112          should be no VUSEs created, since the referenced objects are
2113          not really accessed.  The only operands that we should find
2114          here are ARRAY_REF indices which will always be real operands
2115          (GIMPLE does not allow non-registers as array indices).  */
2116       flags |= opf_no_vops;
2117       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2118       return;
2119
2120     case SSA_NAME:
2121     case STRUCT_FIELD_TAG:
2122     case SYMBOL_MEMORY_TAG:
2123     case NAME_MEMORY_TAG:
2124      add_stmt_operand (expr_p, s_ann, flags);
2125      return;
2126
2127     case VAR_DECL:
2128     case PARM_DECL:
2129     case RESULT_DECL:
2130       {
2131         subvar_t svars;
2132         
2133         /* Add the subvars for a variable, if it has subvars, to DEFS
2134            or USES.  Otherwise, add the variable itself.  Whether it
2135            goes to USES or DEFS depends on the operand flags.  */
2136         if (var_can_have_subvars (expr)
2137             && (svars = get_subvars_for_var (expr)))
2138           {
2139             unsigned int i;
2140             tree subvar;
2141             for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
2142               add_stmt_operand (&subvar, s_ann, flags);
2143           }
2144         else
2145           add_stmt_operand (expr_p, s_ann, flags);
2146
2147         return;
2148       }
2149
2150     case MISALIGNED_INDIRECT_REF:
2151       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
2152       /* fall through */
2153
2154     case ALIGN_INDIRECT_REF:
2155     case INDIRECT_REF:
2156       get_indirect_ref_operands (stmt, expr, flags, expr, 0, -1, true);
2157       return;
2158
2159     case TARGET_MEM_REF:
2160       get_tmr_operands (stmt, expr, flags);
2161       return;
2162
2163     case ARRAY_REF:
2164     case ARRAY_RANGE_REF:
2165     case COMPONENT_REF:
2166     case REALPART_EXPR:
2167     case IMAGPART_EXPR:
2168       {
2169         tree ref;
2170         HOST_WIDE_INT offset, size, maxsize;
2171         bool none = true;
2172
2173         if (TREE_THIS_VOLATILE (expr))
2174           s_ann->has_volatile_ops = true;
2175
2176         /* This component reference becomes an access to all of the
2177            subvariables it can touch, if we can determine that, but
2178            *NOT* the real one.  If we can't determine which fields we
2179            could touch, the recursion will eventually get to a
2180            variable and add *all* of its subvars, or whatever is the
2181            minimum correct subset.  */
2182         ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
2183         if (SSA_VAR_P (ref) && get_subvars_for_var (ref))
2184           {
2185             subvar_t svars = get_subvars_for_var (ref);
2186             unsigned int i;
2187             tree subvar;
2188
2189             for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
2190               {
2191                 bool exact;             
2192
2193                 if (overlap_subvar (offset, maxsize, subvar, &exact))
2194                   {
2195                     int subvar_flags = flags;
2196                     none = false;
2197                     add_stmt_operand (&subvar, s_ann, subvar_flags);
2198                   }
2199               }
2200
2201             if (!none)
2202               flags |= opf_no_vops;
2203
2204             if ((DECL_P (ref) && TREE_THIS_VOLATILE (ref))
2205                 || (TREE_CODE (ref) == SSA_NAME
2206                     && TREE_THIS_VOLATILE (SSA_NAME_VAR (ref))))
2207               s_ann->has_volatile_ops = true;
2208           }
2209         else if (TREE_CODE (ref) == INDIRECT_REF)
2210           {
2211             get_indirect_ref_operands (stmt, ref, flags, expr, offset,
2212                                        maxsize, false);
2213             flags |= opf_no_vops;
2214           }
2215
2216         /* Even if we found subvars above we need to ensure to see
2217            immediate uses for d in s.a[d].  In case of s.a having
2218            a subvar or we would miss it otherwise.  */
2219         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2220         
2221         if (code == COMPONENT_REF)
2222           {
2223             if (TREE_THIS_VOLATILE (TREE_OPERAND (expr, 1)))
2224               s_ann->has_volatile_ops = true; 
2225             get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
2226           }
2227         else if (code == ARRAY_REF || code == ARRAY_RANGE_REF)
2228           {
2229             get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2230             get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
2231             get_expr_operands (stmt, &TREE_OPERAND (expr, 3), opf_use);
2232           }
2233
2234         return;
2235       }
2236
2237     case WITH_SIZE_EXPR:
2238       /* WITH_SIZE_EXPR is a pass-through reference to its first argument,
2239          and an rvalue reference to its second argument.  */
2240       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2241       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2242       return;
2243
2244     case CALL_EXPR:
2245       get_call_expr_operands (stmt, expr);
2246       return;
2247
2248     case COND_EXPR:
2249     case VEC_COND_EXPR:
2250       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_use);
2251       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2252       get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
2253       return;
2254
2255     case GIMPLE_MODIFY_STMT:
2256       get_modify_stmt_operands (stmt, expr);
2257       return;
2258
2259     case CONSTRUCTOR:
2260       {
2261         /* General aggregate CONSTRUCTORs have been decomposed, but they
2262            are still in use as the COMPLEX_EXPR equivalent for vectors.  */
2263         constructor_elt *ce;
2264         unsigned HOST_WIDE_INT idx;
2265
2266         for (idx = 0;
2267              VEC_iterate (constructor_elt, CONSTRUCTOR_ELTS (expr), idx, ce);
2268              idx++)
2269           get_expr_operands (stmt, &ce->value, opf_use);
2270
2271         return;
2272       }
2273
2274     case BIT_FIELD_REF:
2275     case TRUTH_NOT_EXPR:
2276     case VIEW_CONVERT_EXPR:
2277     do_unary:
2278       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2279       return;
2280
2281     case TRUTH_AND_EXPR:
2282     case TRUTH_OR_EXPR:
2283     case TRUTH_XOR_EXPR:
2284     case COMPOUND_EXPR:
2285     case OBJ_TYPE_REF:
2286     case ASSERT_EXPR:
2287     do_binary:
2288       {
2289         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2290         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
2291         return;
2292       }
2293
2294     case DOT_PROD_EXPR:
2295     case REALIGN_LOAD_EXPR:
2296       {
2297         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
2298         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
2299         get_expr_operands (stmt, &TREE_OPERAND (expr, 2), flags);
2300         return;
2301       }
2302
2303     case CHANGE_DYNAMIC_TYPE_EXPR:
2304       get_expr_operands (stmt, &CHANGE_DYNAMIC_TYPE_LOCATION (expr), opf_use);
2305       return;
2306
2307     case OMP_FOR:
2308       {
2309         tree init = OMP_FOR_INIT (expr);
2310         tree cond = OMP_FOR_COND (expr);
2311         tree incr = OMP_FOR_INCR (expr);
2312         tree c, clauses = OMP_FOR_CLAUSES (stmt);
2313
2314         get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (init, 0), opf_def);
2315         get_expr_operands (stmt, &GIMPLE_STMT_OPERAND (init, 1), opf_use);
2316         get_expr_operands (stmt, &TREE_OPERAND (cond, 1), opf_use);
2317         get_expr_operands (stmt,
2318                            &TREE_OPERAND (GIMPLE_STMT_OPERAND (incr, 1), 1),
2319                            opf_use);
2320
2321         c = find_omp_clause (clauses, OMP_CLAUSE_SCHEDULE);
2322         if (c)
2323           get_expr_operands (stmt, &OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (c),
2324                              opf_use);
2325         return;
2326       }
2327
2328     case OMP_CONTINUE:
2329       {
2330         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_def);
2331         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
2332         return;
2333       }
2334
2335     case OMP_PARALLEL:
2336       {
2337         tree c, clauses = OMP_PARALLEL_CLAUSES (stmt);
2338
2339         if (OMP_PARALLEL_DATA_ARG (stmt))
2340           {
2341             get_expr_operands (stmt, &OMP_PARALLEL_DATA_ARG (stmt), opf_use);
2342             add_to_addressable_set (OMP_PARALLEL_DATA_ARG (stmt),
2343                                     &s_ann->addresses_taken);
2344           }
2345
2346         c = find_omp_clause (clauses, OMP_CLAUSE_IF);
2347         if (c)
2348           get_expr_operands (stmt, &OMP_CLAUSE_IF_EXPR (c), opf_use);
2349         c = find_omp_clause (clauses, OMP_CLAUSE_NUM_THREADS);
2350         if (c)
2351           get_expr_operands (stmt, &OMP_CLAUSE_NUM_THREADS_EXPR (c), opf_use);
2352         return;
2353       }
2354
2355     case OMP_SECTIONS:
2356       {
2357         get_expr_operands (stmt, &OMP_SECTIONS_CONTROL (expr), opf_def);
2358         return;
2359       }
2360
2361     case OMP_ATOMIC_LOAD:
2362       {
2363         tree *addr = &TREE_OPERAND (expr, 1);
2364         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_def);
2365
2366         if (TREE_CODE (*addr) == ADDR_EXPR)
2367           get_expr_operands (stmt, &TREE_OPERAND (*addr, 0), opf_def);
2368         else
2369           get_addr_dereference_operands (stmt, addr, opf_def,
2370                                          NULL_TREE, 0, -1, true);
2371         return;
2372       }
2373
2374     case OMP_ATOMIC_STORE:
2375       {
2376         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_use);
2377         return;
2378       }
2379
2380     case BLOCK:
2381     case FUNCTION_DECL:
2382     case EXC_PTR_EXPR:
2383     case FILTER_EXPR:
2384     case LABEL_DECL:
2385     case CONST_DECL:
2386     case OMP_SINGLE:
2387     case OMP_MASTER:
2388     case OMP_ORDERED:
2389     case OMP_CRITICAL:
2390     case OMP_RETURN:
2391     case OMP_SECTION:
2392     case OMP_SECTIONS_SWITCH:
2393       /* Expressions that make no memory references.  */
2394       return;
2395
2396     default:
2397       if (codeclass == tcc_unary)
2398         goto do_unary;
2399       if (codeclass == tcc_binary || codeclass == tcc_comparison)
2400         goto do_binary;
2401       if (codeclass == tcc_constant || codeclass == tcc_type)
2402         return;
2403     }
2404
2405   /* If we get here, something has gone wrong.  */
2406 #ifdef ENABLE_CHECKING
2407   fprintf (stderr, "unhandled expression in get_expr_operands():\n");
2408   debug_tree (expr);
2409   fputs ("\n", stderr);
2410 #endif
2411   gcc_unreachable ();
2412 }
2413
2414
2415 /* Parse STMT looking for operands.  When finished, the various
2416    build_* operand vectors will have potential operands in them.  */
2417
2418 static void
2419 parse_ssa_operands (tree stmt)
2420 {
2421   enum tree_code code;
2422
2423   code = TREE_CODE (stmt);
2424   switch (code)
2425     {
2426     case GIMPLE_MODIFY_STMT:
2427       get_modify_stmt_operands (stmt, stmt);
2428       break;
2429
2430     case COND_EXPR:
2431       get_expr_operands (stmt, &COND_EXPR_COND (stmt), opf_use);
2432       break;
2433
2434     case SWITCH_EXPR:
2435       get_expr_operands (stmt, &SWITCH_COND (stmt), opf_use);
2436       break;
2437
2438     case ASM_EXPR:
2439       get_asm_expr_operands (stmt);
2440       break;
2441
2442     case RETURN_EXPR:
2443       get_expr_operands (stmt, &TREE_OPERAND (stmt, 0), opf_use);
2444       break;
2445
2446     case GOTO_EXPR:
2447       get_expr_operands (stmt, &GOTO_DESTINATION (stmt), opf_use);
2448       break;
2449
2450     case LABEL_EXPR:
2451       get_expr_operands (stmt, &LABEL_EXPR_LABEL (stmt), opf_use);
2452       break;
2453
2454     case BIND_EXPR:
2455     case CASE_LABEL_EXPR:
2456     case TRY_CATCH_EXPR:
2457     case TRY_FINALLY_EXPR:
2458     case EH_FILTER_EXPR:
2459     case CATCH_EXPR:
2460     case RESX_EXPR:
2461       /* These nodes contain no variable references.  */
2462      break;
2463
2464     default:
2465       /* Notice that if get_expr_operands tries to use &STMT as the
2466          operand pointer (which may only happen for USE operands), we
2467          will fail in add_stmt_operand.  This default will handle
2468          statements like empty statements, or CALL_EXPRs that may
2469          appear on the RHS of a statement or as statements themselves.  */
2470       get_expr_operands (stmt, &stmt, opf_use);
2471       break;
2472     }
2473 }
2474
2475
2476 /* Create an operands cache for STMT.  */
2477
2478 static void
2479 build_ssa_operands (tree stmt)
2480 {
2481   stmt_ann_t ann = get_stmt_ann (stmt);
2482   
2483   /* Initially assume that the statement has no volatile operands and
2484      makes no memory references.  */
2485   ann->has_volatile_ops = false;
2486   ann->references_memory = false;
2487   /* Just clear the bitmap so we don't end up reallocating it over and over.  */
2488   if (ann->addresses_taken)
2489     bitmap_clear (ann->addresses_taken);
2490
2491   start_ssa_stmt_operands ();
2492   parse_ssa_operands (stmt);
2493   operand_build_sort_virtual (build_vuses);
2494   operand_build_sort_virtual (build_vdefs);
2495   finalize_ssa_stmt_operands (stmt);
2496
2497   if (ann->addresses_taken && bitmap_empty_p (ann->addresses_taken))
2498     ann->addresses_taken = NULL;
2499
2500   /* For added safety, assume that statements with volatile operands
2501      also reference memory.  */
2502   if (ann->has_volatile_ops)
2503     ann->references_memory = true;
2504 }
2505
2506
2507 /* Releases the operands of STMT back to their freelists, and clears
2508    the stmt operand lists.  */
2509
2510 void
2511 free_stmt_operands (tree stmt)
2512 {
2513   def_optype_p defs = DEF_OPS (stmt), last_def;
2514   use_optype_p uses = USE_OPS (stmt), last_use;
2515   voptype_p vuses = VUSE_OPS (stmt);
2516   voptype_p vdefs = VDEF_OPS (stmt), vdef, next_vdef;
2517   unsigned i;
2518
2519   if (defs)
2520     {
2521       for (last_def = defs; last_def->next; last_def = last_def->next)
2522         continue;
2523       last_def->next = gimple_ssa_operands (cfun)->free_defs;
2524       gimple_ssa_operands (cfun)->free_defs = defs;
2525       DEF_OPS (stmt) = NULL;
2526     }
2527
2528   if (uses)
2529     {
2530       for (last_use = uses; last_use->next; last_use = last_use->next)
2531         delink_imm_use (USE_OP_PTR (last_use));
2532       delink_imm_use (USE_OP_PTR (last_use));
2533       last_use->next = gimple_ssa_operands (cfun)->free_uses;
2534       gimple_ssa_operands (cfun)->free_uses = uses;
2535       USE_OPS (stmt) = NULL;
2536     }
2537
2538   if (vuses)
2539     {
2540       for (i = 0; i < VUSE_NUM (vuses); i++)
2541         delink_imm_use (VUSE_OP_PTR (vuses, i));
2542       add_vop_to_freelist (vuses);
2543       VUSE_OPS (stmt) = NULL;
2544     }
2545
2546   if (vdefs)
2547     {
2548       for (vdef = vdefs; vdef; vdef = next_vdef)
2549         {
2550           next_vdef = vdef->next;
2551           delink_imm_use (VDEF_OP_PTR (vdef, 0));
2552           add_vop_to_freelist (vdef);
2553         }
2554       VDEF_OPS (stmt) = NULL;
2555     }
2556 }
2557
2558
2559 /* Free any operands vectors in OPS.  */
2560
2561 void 
2562 free_ssa_operands (stmt_operands_p ops)
2563 {
2564   ops->def_ops = NULL;
2565   ops->use_ops = NULL;
2566   ops->vdef_ops = NULL;
2567   ops->vuse_ops = NULL;
2568   BITMAP_FREE (ops->loads);
2569   BITMAP_FREE (ops->stores);
2570 }
2571
2572
2573 /* Get the operands of statement STMT.  */
2574
2575 void
2576 update_stmt_operands (tree stmt)
2577 {
2578   stmt_ann_t ann = get_stmt_ann (stmt);
2579
2580   /* If update_stmt_operands is called before SSA is initialized, do
2581      nothing.  */
2582   if (!ssa_operands_active ())
2583     return;
2584
2585   /* The optimizers cannot handle statements that are nothing but a
2586      _DECL.  This indicates a bug in the gimplifier.  */
2587   gcc_assert (!SSA_VAR_P (stmt));
2588
2589   timevar_push (TV_TREE_OPS);
2590
2591   gcc_assert (ann->modified);
2592   build_ssa_operands (stmt);
2593   ann->modified = 0;
2594
2595   timevar_pop (TV_TREE_OPS);
2596 }
2597
2598
2599 /* Copies virtual operands from SRC to DST.  */
2600
2601 void
2602 copy_virtual_operands (tree dest, tree src)
2603 {
2604   unsigned int i, n;
2605   voptype_p src_vuses, dest_vuses;
2606   voptype_p src_vdefs, dest_vdefs;
2607   struct voptype_d vuse;
2608   struct voptype_d vdef;
2609   stmt_ann_t dest_ann;
2610
2611   VDEF_OPS (dest) = NULL;
2612   VUSE_OPS (dest) = NULL;
2613
2614   dest_ann = get_stmt_ann (dest);
2615   BITMAP_FREE (dest_ann->operands.loads);
2616   BITMAP_FREE (dest_ann->operands.stores);
2617
2618   if (LOADED_SYMS (src))
2619     {
2620       dest_ann->operands.loads = BITMAP_ALLOC (&operands_bitmap_obstack);
2621       bitmap_copy (dest_ann->operands.loads, LOADED_SYMS (src));
2622     }
2623
2624   if (STORED_SYMS (src))
2625     {
2626       dest_ann->operands.stores = BITMAP_ALLOC (&operands_bitmap_obstack);
2627       bitmap_copy (dest_ann->operands.stores, STORED_SYMS (src));
2628     }
2629
2630   /* Copy all the VUSE operators and corresponding operands.  */
2631   dest_vuses = &vuse;
2632   for (src_vuses = VUSE_OPS (src); src_vuses; src_vuses = src_vuses->next)
2633     {
2634       n = VUSE_NUM (src_vuses);
2635       dest_vuses = add_vuse_op (dest, NULL_TREE, n, dest_vuses);
2636       for (i = 0; i < n; i++)
2637         SET_USE (VUSE_OP_PTR (dest_vuses, i), VUSE_OP (src_vuses, i));
2638
2639       if (VUSE_OPS (dest) == NULL)
2640         VUSE_OPS (dest) = vuse.next;
2641     }
2642
2643   /* Copy all the VDEF operators and corresponding operands.  */
2644   dest_vdefs = &vdef;
2645   for (src_vdefs = VDEF_OPS (src); src_vdefs; src_vdefs = src_vdefs->next)
2646     {
2647       n = VUSE_NUM (src_vdefs);
2648       dest_vdefs = add_vdef_op (dest, NULL_TREE, n, dest_vdefs);
2649       VDEF_RESULT (dest_vdefs) = VDEF_RESULT (src_vdefs);
2650       for (i = 0; i < n; i++)
2651         SET_USE (VUSE_OP_PTR (dest_vdefs, i), VUSE_OP (src_vdefs, i));
2652
2653       if (VDEF_OPS (dest) == NULL)
2654         VDEF_OPS (dest) = vdef.next;
2655     }
2656 }
2657
2658
2659 /* Specifically for use in DOM's expression analysis.  Given a store, we
2660    create an artificial stmt which looks like a load from the store, this can
2661    be used to eliminate redundant loads.  OLD_OPS are the operands from the 
2662    store stmt, and NEW_STMT is the new load which represents a load of the
2663    values stored.  */
2664
2665 void
2666 create_ssa_artificial_load_stmt (tree new_stmt, tree old_stmt)
2667 {
2668   tree op;
2669   ssa_op_iter iter;
2670   use_operand_p use_p;
2671   unsigned i;
2672
2673   get_stmt_ann (new_stmt);
2674
2675   /* Process NEW_STMT looking for operands.  */
2676   start_ssa_stmt_operands ();
2677   parse_ssa_operands (new_stmt);
2678
2679   for (i = 0; VEC_iterate (tree, build_vuses, i, op); i++)
2680     if (TREE_CODE (op) != SSA_NAME)
2681       var_ann (op)->in_vuse_list = false;
2682    
2683   for (i = 0; VEC_iterate (tree, build_vuses, i, op); i++)
2684     if (TREE_CODE (op) != SSA_NAME)
2685       var_ann (op)->in_vdef_list = false;
2686
2687   /* Remove any virtual operands that were found.  */
2688   VEC_truncate (tree, build_vdefs, 0);
2689   VEC_truncate (tree, build_vuses, 0);
2690
2691   /* For each VDEF on the original statement, we want to create a
2692      VUSE of the VDEF result operand on the new statement.  */
2693   FOR_EACH_SSA_TREE_OPERAND (op, old_stmt, iter, SSA_OP_VDEF)
2694     append_vuse (op);
2695
2696   finalize_ssa_stmt_operands (new_stmt);
2697
2698   /* All uses in this fake stmt must not be in the immediate use lists.  */
2699   FOR_EACH_SSA_USE_OPERAND (use_p, new_stmt, iter, SSA_OP_ALL_USES)
2700     delink_imm_use (use_p);
2701 }
2702
2703
2704 /* Swap operands EXP0 and EXP1 in statement STMT.  No attempt is done
2705    to test the validity of the swap operation.  */
2706
2707 void
2708 swap_tree_operands (tree stmt, tree *exp0, tree *exp1)
2709 {
2710   tree op0, op1;
2711   op0 = *exp0;
2712   op1 = *exp1;
2713
2714   /* If the operand cache is active, attempt to preserve the relative
2715      positions of these two operands in their respective immediate use
2716      lists.  */
2717   if (ssa_operands_active () && op0 != op1)
2718     {
2719       use_optype_p use0, use1, ptr;
2720       use0 = use1 = NULL;
2721
2722       /* Find the 2 operands in the cache, if they are there.  */
2723       for (ptr = USE_OPS (stmt); ptr; ptr = ptr->next)
2724         if (USE_OP_PTR (ptr)->use == exp0)
2725           {
2726             use0 = ptr;
2727             break;
2728           }
2729
2730       for (ptr = USE_OPS (stmt); ptr; ptr = ptr->next)
2731         if (USE_OP_PTR (ptr)->use == exp1)
2732           {
2733             use1 = ptr;
2734             break;
2735           }
2736
2737       /* If both uses don't have operand entries, there isn't much we can do
2738          at this point.  Presumably we don't need to worry about it.  */
2739       if (use0 && use1)
2740         {
2741           tree *tmp = USE_OP_PTR (use1)->use;
2742           USE_OP_PTR (use1)->use = USE_OP_PTR (use0)->use;
2743           USE_OP_PTR (use0)->use = tmp;
2744         }
2745     }
2746
2747   /* Now swap the data.  */
2748   *exp0 = op1;
2749   *exp1 = op0;
2750 }
2751
2752
2753 /* Add the base address of REF to the set *ADDRESSES_TAKEN.  If
2754    *ADDRESSES_TAKEN is NULL, a new set is created.  REF may be
2755    a single variable whose address has been taken or any other valid
2756    GIMPLE memory reference (structure reference, array, etc).  If the
2757    base address of REF is a decl that has sub-variables, also add all
2758    of its sub-variables.  */
2759
2760 void
2761 add_to_addressable_set (tree ref, bitmap *addresses_taken)
2762 {
2763   tree var;
2764   subvar_t svars;
2765
2766   gcc_assert (addresses_taken);
2767
2768   /* Note that it is *NOT OKAY* to use the target of a COMPONENT_REF
2769      as the only thing we take the address of.  If VAR is a structure,
2770      taking the address of a field means that the whole structure may
2771      be referenced using pointer arithmetic.  See PR 21407 and the
2772      ensuing mailing list discussion.  */
2773   var = get_base_address (ref);
2774   if (var && SSA_VAR_P (var))
2775     {
2776       if (*addresses_taken == NULL)
2777         *addresses_taken = BITMAP_GGC_ALLOC ();      
2778       
2779       if (var_can_have_subvars (var)
2780           && (svars = get_subvars_for_var (var)))
2781         {
2782           unsigned int i;
2783           tree subvar;
2784           for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
2785             {
2786               bitmap_set_bit (*addresses_taken, DECL_UID (subvar));
2787               TREE_ADDRESSABLE (subvar) = 1;
2788             }
2789         }
2790       else
2791         {
2792           bitmap_set_bit (*addresses_taken, DECL_UID (var));
2793           TREE_ADDRESSABLE (var) = 1;
2794         }
2795     }
2796 }
2797
2798
2799 /* Scan the immediate_use list for VAR making sure its linked properly.
2800    Return TRUE if there is a problem and emit an error message to F.  */
2801
2802 bool
2803 verify_imm_links (FILE *f, tree var)
2804 {
2805   use_operand_p ptr, prev, list;
2806   int count;
2807
2808   gcc_assert (TREE_CODE (var) == SSA_NAME);
2809
2810   list = &(SSA_NAME_IMM_USE_NODE (var));
2811   gcc_assert (list->use == NULL);
2812
2813   if (list->prev == NULL)
2814     {
2815       gcc_assert (list->next == NULL);
2816       return false;
2817     }
2818
2819   prev = list;
2820   count = 0;
2821   for (ptr = list->next; ptr != list; )
2822     {
2823       if (prev != ptr->prev)
2824         goto error;
2825       
2826       if (ptr->use == NULL)
2827         goto error; /* 2 roots, or SAFE guard node.  */
2828       else if (*(ptr->use) != var)
2829         goto error;
2830
2831       prev = ptr;
2832       ptr = ptr->next;
2833
2834       /* Avoid infinite loops.  50,000,000 uses probably indicates a
2835          problem.  */
2836       if (count++ > 50000000)
2837         goto error;
2838     }
2839
2840   /* Verify list in the other direction.  */
2841   prev = list;
2842   for (ptr = list->prev; ptr != list; )
2843     {
2844       if (prev != ptr->next)
2845         goto error;
2846       prev = ptr;
2847       ptr = ptr->prev;
2848       if (count-- < 0)
2849         goto error;
2850     }
2851
2852   if (count != 0)
2853     goto error;
2854
2855   return false;
2856
2857  error:
2858   if (ptr->stmt && stmt_modified_p (ptr->stmt))
2859     {
2860       fprintf (f, " STMT MODIFIED. - <%p> ", (void *)ptr->stmt);
2861       print_generic_stmt (f, ptr->stmt, TDF_SLIM);
2862     }
2863   fprintf (f, " IMM ERROR : (use_p : tree - %p:%p)", (void *)ptr, 
2864            (void *)ptr->use);
2865   print_generic_expr (f, USE_FROM_PTR (ptr), TDF_SLIM);
2866   fprintf(f, "\n");
2867   return true;
2868 }
2869
2870
2871 /* Dump all the immediate uses to FILE.  */
2872
2873 void
2874 dump_immediate_uses_for (FILE *file, tree var)
2875 {
2876   imm_use_iterator iter;
2877   use_operand_p use_p;
2878
2879   gcc_assert (var && TREE_CODE (var) == SSA_NAME);
2880
2881   print_generic_expr (file, var, TDF_SLIM);
2882   fprintf (file, " : -->");
2883   if (has_zero_uses (var))
2884     fprintf (file, " no uses.\n");
2885   else
2886     if (has_single_use (var))
2887       fprintf (file, " single use.\n");
2888     else
2889       fprintf (file, "%d uses.\n", num_imm_uses (var));
2890
2891   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
2892     {
2893       if (use_p->stmt == NULL && use_p->use == NULL)
2894         fprintf (file, "***end of stmt iterator marker***\n");
2895       else
2896         if (!is_gimple_reg (USE_FROM_PTR (use_p)))
2897           print_generic_stmt (file, USE_STMT (use_p), TDF_VOPS|TDF_MEMSYMS);
2898         else
2899           print_generic_stmt (file, USE_STMT (use_p), TDF_SLIM);
2900     }
2901   fprintf(file, "\n");
2902 }
2903
2904
2905 /* Dump all the immediate uses to FILE.  */
2906
2907 void
2908 dump_immediate_uses (FILE *file)
2909 {
2910   tree var;
2911   unsigned int x;
2912
2913   fprintf (file, "Immediate_uses: \n\n");
2914   for (x = 1; x < num_ssa_names; x++)
2915     {
2916       var = ssa_name(x);
2917       if (!var)
2918         continue;
2919       dump_immediate_uses_for (file, var);
2920     }
2921 }
2922
2923
2924 /* Dump def-use edges on stderr.  */
2925
2926 void
2927 debug_immediate_uses (void)
2928 {
2929   dump_immediate_uses (stderr);
2930 }
2931
2932
2933 /* Dump def-use edges on stderr.  */
2934
2935 void
2936 debug_immediate_uses_for (tree var)
2937 {
2938   dump_immediate_uses_for (stderr, var);
2939 }
2940
2941
2942 /* Create a new change buffer for the statement pointed by STMT_P and
2943    push the buffer into SCB_STACK.  Each change buffer
2944    records state information needed to determine what changed in the
2945    statement.  Mainly, this keeps track of symbols that may need to be
2946    put into SSA form, SSA name replacements and other information
2947    needed to keep the SSA form up to date.  */
2948
2949 void
2950 push_stmt_changes (tree *stmt_p)
2951 {
2952   tree stmt;
2953   scb_t buf;
2954   
2955   stmt = *stmt_p;
2956
2957   /* It makes no sense to keep track of PHI nodes.  */
2958   if (TREE_CODE (stmt) == PHI_NODE)
2959     return;
2960
2961   buf = XNEW (struct scb_d);
2962   memset (buf, 0, sizeof *buf);
2963
2964   buf->stmt_p = stmt_p;
2965
2966   if (stmt_references_memory_p (stmt))
2967     {
2968       tree op;
2969       ssa_op_iter i;
2970
2971       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VUSE)
2972         {
2973           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
2974           if (buf->loads == NULL)
2975             buf->loads = BITMAP_ALLOC (NULL);
2976           bitmap_set_bit (buf->loads, DECL_UID (sym));
2977         }
2978
2979       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VDEF)
2980         {
2981           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
2982           if (buf->stores == NULL)
2983             buf->stores = BITMAP_ALLOC (NULL);
2984           bitmap_set_bit (buf->stores, DECL_UID (sym));
2985         }
2986     }
2987
2988   VEC_safe_push (scb_t, heap, scb_stack, buf);
2989 }
2990
2991
2992 /* Given two sets S1 and S2, mark the symbols that differ in S1 and S2
2993    for renaming.  The set to mark for renaming is (S1 & ~S2) | (S2 & ~S1).  */
2994
2995 static void
2996 mark_difference_for_renaming (bitmap s1, bitmap s2)
2997 {
2998   if (s1 == NULL && s2 == NULL)
2999     return;
3000
3001   if (s1 && s2 == NULL)
3002     mark_set_for_renaming (s1);
3003   else if (s1 == NULL && s2)
3004     mark_set_for_renaming (s2);
3005   else if (!bitmap_equal_p (s1, s2))
3006     {
3007       bitmap t1 = BITMAP_ALLOC (NULL);
3008       bitmap t2 = BITMAP_ALLOC (NULL);
3009
3010       bitmap_and_compl (t1, s1, s2);
3011       bitmap_and_compl (t2, s2, s1);
3012       bitmap_ior_into (t1, t2);
3013       mark_set_for_renaming (t1);
3014
3015       BITMAP_FREE (t1);
3016       BITMAP_FREE (t2);
3017     }
3018 }
3019
3020
3021 /* Pop the top SCB from SCB_STACK and act on the differences between
3022    what was recorded by push_stmt_changes and the current state of
3023    the statement.  */
3024
3025 void
3026 pop_stmt_changes (tree *stmt_p)
3027 {
3028   tree op, stmt;
3029   ssa_op_iter iter;
3030   bitmap loads, stores;
3031   scb_t buf;
3032
3033   stmt = *stmt_p;
3034
3035   /* It makes no sense to keep track of PHI nodes.  */
3036   if (TREE_CODE (stmt) == PHI_NODE)
3037     return;
3038
3039   buf = VEC_pop (scb_t, scb_stack);
3040   gcc_assert (stmt_p == buf->stmt_p);
3041
3042   /* Force an operand re-scan on the statement and mark any newly
3043      exposed variables.  */
3044   update_stmt (stmt);
3045
3046   /* Determine whether any memory symbols need to be renamed.  If the
3047      sets of loads and stores are different after the statement is
3048      modified, then the affected symbols need to be renamed.
3049      
3050      Note that it may be possible for the statement to not reference
3051      memory anymore, but we still need to act on the differences in
3052      the sets of symbols.  */
3053   loads = stores = NULL;
3054   if (stmt_references_memory_p (stmt))
3055     {
3056       tree op;
3057       ssa_op_iter i;
3058
3059       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VUSE)
3060         {
3061           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
3062           if (loads == NULL)
3063             loads = BITMAP_ALLOC (NULL);
3064           bitmap_set_bit (loads, DECL_UID (sym));
3065         }
3066
3067       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_VDEF)
3068         {
3069           tree sym = TREE_CODE (op) == SSA_NAME ? SSA_NAME_VAR (op) : op;
3070           if (stores == NULL)
3071             stores = BITMAP_ALLOC (NULL);
3072           bitmap_set_bit (stores, DECL_UID (sym));
3073         }
3074     }
3075
3076   /* If LOADS is different from BUF->LOADS, the affected
3077      symbols need to be marked for renaming.  */
3078   mark_difference_for_renaming (loads, buf->loads);
3079
3080   /* Similarly for STORES and BUF->STORES.  */
3081   mark_difference_for_renaming (stores, buf->stores);
3082
3083   /* Mark all the naked GIMPLE register operands for renaming.  */
3084   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF|SSA_OP_USE)
3085     if (DECL_P (op))
3086       mark_sym_for_renaming (op);
3087
3088   /* FIXME, need to add more finalizers here.  Cleanup EH info,
3089      recompute invariants for address expressions, add
3090      SSA replacement mappings, etc.  For instance, given
3091      testsuite/gcc.c-torture/compile/pr16808.c, we fold a statement of
3092      the form:
3093
3094           # SMT.4_20 = VDEF <SMT.4_16>
3095           D.1576_11 = 1.0e+0;
3096
3097      So, the VDEF will disappear, but instead of marking SMT.4 for
3098      renaming it would be far more efficient to establish a
3099      replacement mapping that would replace every reference of
3100      SMT.4_20 with SMT.4_16.  */
3101
3102   /* Free memory used by the buffer.  */
3103   BITMAP_FREE (buf->loads);
3104   BITMAP_FREE (buf->stores);
3105   BITMAP_FREE (loads);
3106   BITMAP_FREE (stores);
3107   buf->stmt_p = NULL;
3108   free (buf);
3109 }
3110
3111
3112 /* Discard the topmost change buffer from SCB_STACK.  This is useful
3113    when the caller realized that it did not actually modified the
3114    statement.  It avoids the expensive operand re-scan.  */
3115
3116 void
3117 discard_stmt_changes (tree *stmt_p)
3118 {
3119   scb_t buf;
3120   tree stmt;
3121   
3122   /* It makes no sense to keep track of PHI nodes.  */
3123   stmt = *stmt_p;
3124   if (TREE_CODE (stmt) == PHI_NODE)
3125     return;
3126
3127   buf = VEC_pop (scb_t, scb_stack);
3128   gcc_assert (stmt_p == buf->stmt_p);
3129
3130   /* Free memory used by the buffer.  */
3131   BITMAP_FREE (buf->loads);
3132   BITMAP_FREE (buf->stores);
3133   buf->stmt_p = NULL;
3134   free (buf);
3135 }
3136
3137
3138 /* Returns true if statement STMT may access memory.  */
3139
3140 bool
3141 stmt_references_memory_p (tree stmt)
3142 {
3143   if (!gimple_ssa_operands (cfun)->ops_active || TREE_CODE (stmt) == PHI_NODE)
3144     return false;
3145
3146   return stmt_ann (stmt)->references_memory;
3147 }