OSDN Git Service

2009-10-08 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / gimple.c
1 /* Gimple IR support functions.
2
3    Copyright 2007, 2008, 2009 Free Software Foundation, Inc.
4    Contributed by Aldy Hernandez <aldyh@redhat.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "target.h"
27 #include "tree.h"
28 #include "ggc.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "gimple.h"
32 #include "toplev.h"
33 #include "diagnostic.h"
34 #include "tree-flow.h"
35 #include "value-prof.h"
36 #include "flags.h"
37 #include "alias.h"
38 #include "demangle.h"
39
40 /* Global type table.  FIXME lto, it should be possible to re-use some
41    of the type hashing routines in tree.c (type_hash_canon, type_hash_lookup,
42    etc), but those assume that types were built with the various
43    build_*_type routines which is not the case with the streamer.  */
44 static htab_t gimple_types;
45 static struct pointer_map_t *type_hash_cache;
46
47 /* Global type comparison cache.  */
48 static htab_t gtc_visited;
49
50 /* All the tuples have their operand vector (if present) at the very bottom
51    of the structure.  Therefore, the offset required to find the
52    operands vector the size of the structure minus the size of the 1
53    element tree array at the end (see gimple_ops).  */
54 #define DEFGSSTRUCT(SYM, STRUCT, HAS_TREE_OP) \
55         (HAS_TREE_OP ? sizeof (struct STRUCT) - sizeof (tree) : 0),
56 EXPORTED_CONST size_t gimple_ops_offset_[] = {
57 #include "gsstruct.def"
58 };
59 #undef DEFGSSTRUCT
60
61 #define DEFGSSTRUCT(SYM, STRUCT, HAS_TREE_OP) sizeof(struct STRUCT),
62 static const size_t gsstruct_code_size[] = {
63 #include "gsstruct.def"
64 };
65 #undef DEFGSSTRUCT
66
67 #define DEFGSCODE(SYM, NAME, GSSCODE)   NAME,
68 const char *const gimple_code_name[] = {
69 #include "gimple.def"
70 };
71 #undef DEFGSCODE
72
73 #define DEFGSCODE(SYM, NAME, GSSCODE)   GSSCODE,
74 EXPORTED_CONST enum gimple_statement_structure_enum gss_for_code_[] = {
75 #include "gimple.def"
76 };
77 #undef DEFGSCODE
78
79 #ifdef GATHER_STATISTICS
80 /* Gimple stats.  */
81
82 int gimple_alloc_counts[(int) gimple_alloc_kind_all];
83 int gimple_alloc_sizes[(int) gimple_alloc_kind_all];
84
85 /* Keep in sync with gimple.h:enum gimple_alloc_kind.  */
86 static const char * const gimple_alloc_kind_names[] = {
87     "assignments",
88     "phi nodes",
89     "conditionals",
90     "sequences",
91     "everything else"
92 };
93
94 #endif /* GATHER_STATISTICS */
95
96 /* A cache of gimple_seq objects.  Sequences are created and destroyed
97    fairly often during gimplification.  */
98 static GTY ((deletable)) struct gimple_seq_d *gimple_seq_cache;
99
100 /* Private API manipulation functions shared only with some
101    other files.  */
102 extern void gimple_set_stored_syms (gimple, bitmap, bitmap_obstack *);
103 extern void gimple_set_loaded_syms (gimple, bitmap, bitmap_obstack *);
104
105 /* Gimple tuple constructors.
106    Note: Any constructor taking a ``gimple_seq'' as a parameter, can
107    be passed a NULL to start with an empty sequence.  */
108
109 /* Set the code for statement G to CODE.  */
110
111 static inline void
112 gimple_set_code (gimple g, enum gimple_code code)
113 {
114   g->gsbase.code = code;
115 }
116
117 /* Return the number of bytes needed to hold a GIMPLE statement with
118    code CODE.  */
119
120 static inline size_t
121 gimple_size (enum gimple_code code)
122 {
123   return gsstruct_code_size[gss_for_code (code)];
124 }
125
126 /* Allocate memory for a GIMPLE statement with code CODE and NUM_OPS
127    operands.  */
128
129 gimple
130 gimple_alloc_stat (enum gimple_code code, unsigned num_ops MEM_STAT_DECL)
131 {
132   size_t size;
133   gimple stmt;
134
135   size = gimple_size (code);
136   if (num_ops > 0)
137     size += sizeof (tree) * (num_ops - 1);
138
139 #ifdef GATHER_STATISTICS
140   {
141     enum gimple_alloc_kind kind = gimple_alloc_kind (code);
142     gimple_alloc_counts[(int) kind]++;
143     gimple_alloc_sizes[(int) kind] += size;
144   }
145 #endif
146
147   stmt = (gimple) ggc_alloc_cleared_stat (size PASS_MEM_STAT);
148   gimple_set_code (stmt, code);
149   gimple_set_num_ops (stmt, num_ops);
150
151   /* Do not call gimple_set_modified here as it has other side
152      effects and this tuple is still not completely built.  */
153   stmt->gsbase.modified = 1;
154
155   return stmt;
156 }
157
158 /* Set SUBCODE to be the code of the expression computed by statement G.  */
159
160 static inline void
161 gimple_set_subcode (gimple g, unsigned subcode)
162 {
163   /* We only have 16 bits for the RHS code.  Assert that we are not
164      overflowing it.  */
165   gcc_assert (subcode < (1 << 16));
166   g->gsbase.subcode = subcode;
167 }
168
169
170
171 /* Build a tuple with operands.  CODE is the statement to build (which
172    must be one of the GIMPLE_WITH_OPS tuples).  SUBCODE is the sub-code
173    for the new tuple.  NUM_OPS is the number of operands to allocate.  */ 
174
175 #define gimple_build_with_ops(c, s, n) \
176   gimple_build_with_ops_stat (c, s, n MEM_STAT_INFO)
177
178 static gimple
179 gimple_build_with_ops_stat (enum gimple_code code, unsigned subcode,
180                             unsigned num_ops MEM_STAT_DECL)
181 {
182   gimple s = gimple_alloc_stat (code, num_ops PASS_MEM_STAT);
183   gimple_set_subcode (s, subcode);
184
185   return s;
186 }
187
188
189 /* Build a GIMPLE_RETURN statement returning RETVAL.  */
190
191 gimple
192 gimple_build_return (tree retval)
193 {
194   gimple s = gimple_build_with_ops (GIMPLE_RETURN, ERROR_MARK, 1);
195   if (retval)
196     gimple_return_set_retval (s, retval);
197   return s;
198 }
199
200 /* Helper for gimple_build_call, gimple_build_call_vec and
201    gimple_build_call_from_tree.  Build the basic components of a
202    GIMPLE_CALL statement to function FN with NARGS arguments.  */
203
204 static inline gimple
205 gimple_build_call_1 (tree fn, unsigned nargs)
206 {
207   gimple s = gimple_build_with_ops (GIMPLE_CALL, ERROR_MARK, nargs + 3);
208   if (TREE_CODE (fn) == FUNCTION_DECL)
209     fn = build_fold_addr_expr (fn);
210   gimple_set_op (s, 1, fn);
211   return s;
212 }
213
214
215 /* Build a GIMPLE_CALL statement to function FN with the arguments
216    specified in vector ARGS.  */
217
218 gimple
219 gimple_build_call_vec (tree fn, VEC(tree, heap) *args)
220 {
221   unsigned i;
222   unsigned nargs = VEC_length (tree, args);
223   gimple call = gimple_build_call_1 (fn, nargs);
224
225   for (i = 0; i < nargs; i++)
226     gimple_call_set_arg (call, i, VEC_index (tree, args, i));
227
228   return call;
229 }
230
231
232 /* Build a GIMPLE_CALL statement to function FN.  NARGS is the number of
233    arguments.  The ... are the arguments.  */
234
235 gimple
236 gimple_build_call (tree fn, unsigned nargs, ...)
237 {
238   va_list ap;
239   gimple call;
240   unsigned i;
241
242   gcc_assert (TREE_CODE (fn) == FUNCTION_DECL || is_gimple_call_addr (fn));
243
244   call = gimple_build_call_1 (fn, nargs);
245
246   va_start (ap, nargs);
247   for (i = 0; i < nargs; i++)
248     gimple_call_set_arg (call, i, va_arg (ap, tree));
249   va_end (ap);
250
251   return call;
252 }
253
254
255 /* Build a GIMPLE_CALL statement from CALL_EXPR T.  Note that T is
256    assumed to be in GIMPLE form already.  Minimal checking is done of
257    this fact.  */
258
259 gimple
260 gimple_build_call_from_tree (tree t)
261 {
262   unsigned i, nargs;
263   gimple call;
264   tree fndecl = get_callee_fndecl (t);
265
266   gcc_assert (TREE_CODE (t) == CALL_EXPR);
267
268   nargs = call_expr_nargs (t);
269   call = gimple_build_call_1 (fndecl ? fndecl : CALL_EXPR_FN (t), nargs);
270
271   for (i = 0; i < nargs; i++)
272     gimple_call_set_arg (call, i, CALL_EXPR_ARG (t, i));
273
274   gimple_set_block (call, TREE_BLOCK (t));
275
276   /* Carry all the CALL_EXPR flags to the new GIMPLE_CALL.  */
277   gimple_call_set_chain (call, CALL_EXPR_STATIC_CHAIN (t));
278   gimple_call_set_tail (call, CALL_EXPR_TAILCALL (t));
279   gimple_call_set_cannot_inline (call, CALL_CANNOT_INLINE_P (t));
280   gimple_call_set_return_slot_opt (call, CALL_EXPR_RETURN_SLOT_OPT (t));
281   gimple_call_set_from_thunk (call, CALL_FROM_THUNK_P (t));
282   gimple_call_set_va_arg_pack (call, CALL_EXPR_VA_ARG_PACK (t));
283   gimple_set_no_warning (call, TREE_NO_WARNING (t));
284
285   return call;
286 }
287
288
289 /* Extract the operands and code for expression EXPR into *SUBCODE_P,
290    *OP1_P and *OP2_P respectively.  */
291
292 void
293 extract_ops_from_tree (tree expr, enum tree_code *subcode_p, tree *op1_p,
294                        tree *op2_p)
295 {
296   enum gimple_rhs_class grhs_class;
297
298   *subcode_p = TREE_CODE (expr);
299   grhs_class = get_gimple_rhs_class (*subcode_p);
300
301   if (grhs_class == GIMPLE_BINARY_RHS)
302     {
303       *op1_p = TREE_OPERAND (expr, 0);
304       *op2_p = TREE_OPERAND (expr, 1);
305     }
306   else if (grhs_class == GIMPLE_UNARY_RHS)
307     {
308       *op1_p = TREE_OPERAND (expr, 0);
309       *op2_p = NULL_TREE;
310     }
311   else if (grhs_class == GIMPLE_SINGLE_RHS)
312     {
313       *op1_p = expr;
314       *op2_p = NULL_TREE;
315     }
316   else
317     gcc_unreachable ();
318 }
319
320
321 /* Build a GIMPLE_ASSIGN statement.
322
323    LHS of the assignment.
324    RHS of the assignment which can be unary or binary.  */
325
326 gimple
327 gimple_build_assign_stat (tree lhs, tree rhs MEM_STAT_DECL)
328 {
329   enum tree_code subcode;
330   tree op1, op2;
331
332   extract_ops_from_tree (rhs, &subcode, &op1, &op2);
333   return gimple_build_assign_with_ops_stat (subcode, lhs, op1, op2
334                                             PASS_MEM_STAT);
335 }
336
337
338 /* Build a GIMPLE_ASSIGN statement with sub-code SUBCODE and operands
339    OP1 and OP2.  If OP2 is NULL then SUBCODE must be of class
340    GIMPLE_UNARY_RHS or GIMPLE_SINGLE_RHS.  */
341
342 gimple
343 gimple_build_assign_with_ops_stat (enum tree_code subcode, tree lhs, tree op1,
344                                    tree op2 MEM_STAT_DECL)
345 {
346   unsigned num_ops;
347   gimple p;
348
349   /* Need 1 operand for LHS and 1 or 2 for the RHS (depending on the
350      code).  */
351   num_ops = get_gimple_rhs_num_ops (subcode) + 1;
352   
353   p = gimple_build_with_ops_stat (GIMPLE_ASSIGN, (unsigned)subcode, num_ops
354                                   PASS_MEM_STAT);
355   gimple_assign_set_lhs (p, lhs);
356   gimple_assign_set_rhs1 (p, op1);
357   if (op2)
358     {
359       gcc_assert (num_ops > 2);
360       gimple_assign_set_rhs2 (p, op2);
361     }
362
363   return p;
364 }
365
366
367 /* Build a new GIMPLE_ASSIGN tuple and append it to the end of *SEQ_P.
368
369    DST/SRC are the destination and source respectively.  You can pass
370    ungimplified trees in DST or SRC, in which case they will be
371    converted to a gimple operand if necessary.
372
373    This function returns the newly created GIMPLE_ASSIGN tuple.  */
374
375 gimple
376 gimplify_assign (tree dst, tree src, gimple_seq *seq_p)
377
378   tree t = build2 (MODIFY_EXPR, TREE_TYPE (dst), dst, src);
379   gimplify_and_add (t, seq_p);
380   ggc_free (t);
381   return gimple_seq_last_stmt (*seq_p);
382 }
383
384
385 /* Build a GIMPLE_COND statement.
386
387    PRED is the condition used to compare LHS and the RHS.
388    T_LABEL is the label to jump to if the condition is true.
389    F_LABEL is the label to jump to otherwise.  */
390
391 gimple
392 gimple_build_cond (enum tree_code pred_code, tree lhs, tree rhs,
393                    tree t_label, tree f_label)
394 {
395   gimple p;
396
397   gcc_assert (TREE_CODE_CLASS (pred_code) == tcc_comparison);
398   p = gimple_build_with_ops (GIMPLE_COND, pred_code, 4);
399   gimple_cond_set_lhs (p, lhs);
400   gimple_cond_set_rhs (p, rhs);
401   gimple_cond_set_true_label (p, t_label);
402   gimple_cond_set_false_label (p, f_label);
403   return p;
404 }
405
406
407 /* Extract operands for a GIMPLE_COND statement out of COND_EXPR tree COND.  */
408
409 void
410 gimple_cond_get_ops_from_tree (tree cond, enum tree_code *code_p,
411                                tree *lhs_p, tree *rhs_p)
412 {
413   location_t loc = EXPR_LOCATION (cond);
414   gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison
415               || TREE_CODE (cond) == TRUTH_NOT_EXPR
416               || is_gimple_min_invariant (cond)
417               || SSA_VAR_P (cond));
418
419   extract_ops_from_tree (cond, code_p, lhs_p, rhs_p);
420
421   /* Canonicalize conditionals of the form 'if (!VAL)'.  */
422   if (*code_p == TRUTH_NOT_EXPR)
423     {
424       *code_p = EQ_EXPR;
425       gcc_assert (*lhs_p && *rhs_p == NULL_TREE);
426       *rhs_p = fold_convert_loc (loc, TREE_TYPE (*lhs_p), integer_zero_node);
427     }
428   /* Canonicalize conditionals of the form 'if (VAL)'  */
429   else if (TREE_CODE_CLASS (*code_p) != tcc_comparison)
430     {
431       *code_p = NE_EXPR;
432       gcc_assert (*lhs_p && *rhs_p == NULL_TREE);
433       *rhs_p = fold_convert_loc (loc, TREE_TYPE (*lhs_p), integer_zero_node);
434     }
435 }
436
437
438 /* Build a GIMPLE_COND statement from the conditional expression tree
439    COND.  T_LABEL and F_LABEL are as in gimple_build_cond.  */
440
441 gimple
442 gimple_build_cond_from_tree (tree cond, tree t_label, tree f_label)
443 {
444   enum tree_code code;
445   tree lhs, rhs;
446
447   gimple_cond_get_ops_from_tree (cond, &code, &lhs, &rhs);
448   return gimple_build_cond (code, lhs, rhs, t_label, f_label);
449 }
450
451 /* Set code, lhs, and rhs of a GIMPLE_COND from a suitable
452    boolean expression tree COND.  */
453
454 void
455 gimple_cond_set_condition_from_tree (gimple stmt, tree cond)
456 {
457   enum tree_code code;
458   tree lhs, rhs;
459
460   gimple_cond_get_ops_from_tree (cond, &code, &lhs, &rhs);
461   gimple_cond_set_condition (stmt, code, lhs, rhs);
462 }
463
464 /* Build a GIMPLE_LABEL statement for LABEL.  */
465
466 gimple
467 gimple_build_label (tree label)
468 {
469   gimple p = gimple_build_with_ops (GIMPLE_LABEL, ERROR_MARK, 1);
470   gimple_label_set_label (p, label);
471   return p;
472 }
473
474 /* Build a GIMPLE_GOTO statement to label DEST.  */
475
476 gimple
477 gimple_build_goto (tree dest)
478 {
479   gimple p = gimple_build_with_ops (GIMPLE_GOTO, ERROR_MARK, 1);
480   gimple_goto_set_dest (p, dest);
481   return p;
482 }
483
484
485 /* Build a GIMPLE_NOP statement.  */
486
487 gimple 
488 gimple_build_nop (void)
489 {
490   return gimple_alloc (GIMPLE_NOP, 0);
491 }
492
493
494 /* Build a GIMPLE_BIND statement.
495    VARS are the variables in BODY.
496    BLOCK is the containing block.  */
497
498 gimple
499 gimple_build_bind (tree vars, gimple_seq body, tree block)
500 {
501   gimple p = gimple_alloc (GIMPLE_BIND, 0);
502   gimple_bind_set_vars (p, vars);
503   if (body)
504     gimple_bind_set_body (p, body);
505   if (block)
506     gimple_bind_set_block (p, block);
507   return p;
508 }
509
510 /* Helper function to set the simple fields of a asm stmt.
511
512    STRING is a pointer to a string that is the asm blocks assembly code.
513    NINPUT is the number of register inputs.
514    NOUTPUT is the number of register outputs.
515    NCLOBBERS is the number of clobbered registers.
516    */
517
518 static inline gimple
519 gimple_build_asm_1 (const char *string, unsigned ninputs, unsigned noutputs, 
520                     unsigned nclobbers, unsigned nlabels)
521 {
522   gimple p;
523   int size = strlen (string);
524
525   /* ASMs with labels cannot have outputs.  This should have been
526      enforced by the front end.  */
527   gcc_assert (nlabels == 0 || noutputs == 0);
528
529   p = gimple_build_with_ops (GIMPLE_ASM, ERROR_MARK,
530                              ninputs + noutputs + nclobbers + nlabels);
531
532   p->gimple_asm.ni = ninputs;
533   p->gimple_asm.no = noutputs;
534   p->gimple_asm.nc = nclobbers;
535   p->gimple_asm.nl = nlabels;
536   p->gimple_asm.string = ggc_alloc_string (string, size);
537
538 #ifdef GATHER_STATISTICS
539   gimple_alloc_sizes[(int) gimple_alloc_kind (GIMPLE_ASM)] += size;
540 #endif
541   
542   return p;
543 }
544
545 /* Build a GIMPLE_ASM statement.
546
547    STRING is the assembly code.
548    NINPUT is the number of register inputs.
549    NOUTPUT is the number of register outputs.
550    NCLOBBERS is the number of clobbered registers.
551    INPUTS is a vector of the input register parameters.
552    OUTPUTS is a vector of the output register parameters.
553    CLOBBERS is a vector of the clobbered register parameters.
554    LABELS is a vector of destination labels.  */
555
556 gimple
557 gimple_build_asm_vec (const char *string, VEC(tree,gc)* inputs, 
558                       VEC(tree,gc)* outputs, VEC(tree,gc)* clobbers,
559                       VEC(tree,gc)* labels)
560 {
561   gimple p;
562   unsigned i;
563
564   p = gimple_build_asm_1 (string,
565                           VEC_length (tree, inputs),
566                           VEC_length (tree, outputs), 
567                           VEC_length (tree, clobbers),
568                           VEC_length (tree, labels));
569   
570   for (i = 0; i < VEC_length (tree, inputs); i++)
571     gimple_asm_set_input_op (p, i, VEC_index (tree, inputs, i));
572
573   for (i = 0; i < VEC_length (tree, outputs); i++)
574     gimple_asm_set_output_op (p, i, VEC_index (tree, outputs, i));
575
576   for (i = 0; i < VEC_length (tree, clobbers); i++)
577     gimple_asm_set_clobber_op (p, i, VEC_index (tree, clobbers, i));
578   
579   for (i = 0; i < VEC_length (tree, labels); i++)
580     gimple_asm_set_label_op (p, i, VEC_index (tree, labels, i));
581   
582   return p;
583 }
584
585 /* Build a GIMPLE_CATCH statement.
586
587   TYPES are the catch types.
588   HANDLER is the exception handler.  */
589
590 gimple
591 gimple_build_catch (tree types, gimple_seq handler)
592 {
593   gimple p = gimple_alloc (GIMPLE_CATCH, 0);
594   gimple_catch_set_types (p, types);
595   if (handler)
596     gimple_catch_set_handler (p, handler);
597
598   return p;
599 }
600
601 /* Build a GIMPLE_EH_FILTER statement.
602
603    TYPES are the filter's types.
604    FAILURE is the filter's failure action.  */
605
606 gimple
607 gimple_build_eh_filter (tree types, gimple_seq failure)
608 {
609   gimple p = gimple_alloc (GIMPLE_EH_FILTER, 0);
610   gimple_eh_filter_set_types (p, types);
611   if (failure)
612     gimple_eh_filter_set_failure (p, failure);
613
614   return p;
615 }
616
617 /* Build a GIMPLE_EH_MUST_NOT_THROW statement.  */
618
619 gimple
620 gimple_build_eh_must_not_throw (tree decl)
621 {
622   gimple p = gimple_alloc (GIMPLE_EH_MUST_NOT_THROW, 1);
623
624   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
625   gcc_assert (flags_from_decl_or_type (decl) & ECF_NORETURN);
626   gimple_eh_must_not_throw_set_fndecl (p, decl);
627
628   return p;
629 }
630
631 /* Build a GIMPLE_TRY statement.
632
633    EVAL is the expression to evaluate.
634    CLEANUP is the cleanup expression.
635    KIND is either GIMPLE_TRY_CATCH or GIMPLE_TRY_FINALLY depending on
636    whether this is a try/catch or a try/finally respectively.  */
637
638 gimple
639 gimple_build_try (gimple_seq eval, gimple_seq cleanup,
640                   enum gimple_try_flags kind)
641 {
642   gimple p;
643
644   gcc_assert (kind == GIMPLE_TRY_CATCH || kind == GIMPLE_TRY_FINALLY);
645   p = gimple_alloc (GIMPLE_TRY, 0);
646   gimple_set_subcode (p, kind);
647   if (eval)
648     gimple_try_set_eval (p, eval);
649   if (cleanup)
650     gimple_try_set_cleanup (p, cleanup);
651
652   return p;
653 }
654
655 /* Construct a GIMPLE_WITH_CLEANUP_EXPR statement.
656
657    CLEANUP is the cleanup expression.  */
658
659 gimple
660 gimple_build_wce (gimple_seq cleanup)
661 {
662   gimple p = gimple_alloc (GIMPLE_WITH_CLEANUP_EXPR, 0);
663   if (cleanup)
664     gimple_wce_set_cleanup (p, cleanup);
665
666   return p;
667 }
668
669
670 /* Build a GIMPLE_RESX statement.  */
671
672 gimple
673 gimple_build_resx (int region)
674 {
675   gimple p = gimple_build_with_ops (GIMPLE_RESX, ERROR_MARK, 0);
676   p->gimple_eh_ctrl.region = region;
677   return p;
678 }
679
680
681 /* The helper for constructing a gimple switch statement.
682    INDEX is the switch's index.
683    NLABELS is the number of labels in the switch excluding the default.
684    DEFAULT_LABEL is the default label for the switch statement.  */
685
686 gimple 
687 gimple_build_switch_nlabels (unsigned nlabels, tree index, tree default_label)
688 {
689   /* nlabels + 1 default label + 1 index.  */
690   gimple p = gimple_build_with_ops (GIMPLE_SWITCH, ERROR_MARK,
691                                     1 + (default_label != NULL) + nlabels);
692   gimple_switch_set_index (p, index);
693   if (default_label)
694     gimple_switch_set_default_label (p, default_label);
695   return p;
696 }
697
698
699 /* Build a GIMPLE_SWITCH statement.
700
701    INDEX is the switch's index.
702    NLABELS is the number of labels in the switch excluding the DEFAULT_LABEL. 
703    ... are the labels excluding the default.  */
704
705 gimple 
706 gimple_build_switch (unsigned nlabels, tree index, tree default_label, ...)
707 {
708   va_list al;
709   unsigned i, offset;
710   gimple p = gimple_build_switch_nlabels (nlabels, index, default_label);
711
712   /* Store the rest of the labels.  */
713   va_start (al, default_label);
714   offset = (default_label != NULL);
715   for (i = 0; i < nlabels; i++)
716     gimple_switch_set_label (p, i + offset, va_arg (al, tree));
717   va_end (al);
718
719   return p;
720 }
721
722
723 /* Build a GIMPLE_SWITCH statement.
724
725    INDEX is the switch's index.
726    DEFAULT_LABEL is the default label
727    ARGS is a vector of labels excluding the default.  */
728
729 gimple
730 gimple_build_switch_vec (tree index, tree default_label, VEC(tree, heap) *args)
731 {
732   unsigned i, offset, nlabels = VEC_length (tree, args);
733   gimple p = gimple_build_switch_nlabels (nlabels, index, default_label);
734
735   /* Copy the labels from the vector to the switch statement.  */
736   offset = (default_label != NULL);
737   for (i = 0; i < nlabels; i++)
738     gimple_switch_set_label (p, i + offset, VEC_index (tree, args, i));
739
740   return p;
741 }
742
743 /* Build a GIMPLE_EH_DISPATCH statement.  */
744
745 gimple
746 gimple_build_eh_dispatch (int region)
747 {
748   gimple p = gimple_build_with_ops (GIMPLE_EH_DISPATCH, ERROR_MARK, 0);
749   p->gimple_eh_ctrl.region = region;
750   return p;
751 }
752
753 /* Build a new GIMPLE_DEBUG_BIND statement.
754
755    VAR is bound to VALUE; block and location are taken from STMT.  */
756
757 gimple
758 gimple_build_debug_bind_stat (tree var, tree value, gimple stmt MEM_STAT_DECL)
759 {
760   gimple p = gimple_build_with_ops_stat (GIMPLE_DEBUG,
761                                          (unsigned)GIMPLE_DEBUG_BIND, 2
762                                          PASS_MEM_STAT);
763
764   gimple_debug_bind_set_var (p, var);
765   gimple_debug_bind_set_value (p, value);
766   if (stmt)
767     {
768       gimple_set_block (p, gimple_block (stmt));
769       gimple_set_location (p, gimple_location (stmt));
770     }
771
772   return p;
773 }
774
775
776 /* Build a GIMPLE_OMP_CRITICAL statement.
777
778    BODY is the sequence of statements for which only one thread can execute.
779    NAME is optional identifier for this critical block.  */
780
781 gimple 
782 gimple_build_omp_critical (gimple_seq body, tree name)
783 {
784   gimple p = gimple_alloc (GIMPLE_OMP_CRITICAL, 0);
785   gimple_omp_critical_set_name (p, name);
786   if (body)
787     gimple_omp_set_body (p, body);
788
789   return p;
790 }
791
792 /* Build a GIMPLE_OMP_FOR statement.
793
794    BODY is sequence of statements inside the for loop.
795    CLAUSES, are any of the OMP loop construct's clauses: private, firstprivate, 
796    lastprivate, reductions, ordered, schedule, and nowait.
797    COLLAPSE is the collapse count.
798    PRE_BODY is the sequence of statements that are loop invariant.  */
799
800 gimple
801 gimple_build_omp_for (gimple_seq body, tree clauses, size_t collapse,
802                       gimple_seq pre_body)
803 {
804   gimple p = gimple_alloc (GIMPLE_OMP_FOR, 0);
805   if (body)
806     gimple_omp_set_body (p, body);
807   gimple_omp_for_set_clauses (p, clauses);
808   p->gimple_omp_for.collapse = collapse;
809   p->gimple_omp_for.iter = GGC_CNEWVEC (struct gimple_omp_for_iter, collapse);
810   if (pre_body)
811     gimple_omp_for_set_pre_body (p, pre_body);
812
813   return p;
814 }
815
816
817 /* Build a GIMPLE_OMP_PARALLEL statement.
818
819    BODY is sequence of statements which are executed in parallel.
820    CLAUSES, are the OMP parallel construct's clauses.
821    CHILD_FN is the function created for the parallel threads to execute.
822    DATA_ARG are the shared data argument(s).  */
823
824 gimple 
825 gimple_build_omp_parallel (gimple_seq body, tree clauses, tree child_fn, 
826                            tree data_arg)
827 {
828   gimple p = gimple_alloc (GIMPLE_OMP_PARALLEL, 0);
829   if (body)
830     gimple_omp_set_body (p, body);
831   gimple_omp_parallel_set_clauses (p, clauses);
832   gimple_omp_parallel_set_child_fn (p, child_fn);
833   gimple_omp_parallel_set_data_arg (p, data_arg);
834
835   return p;
836 }
837
838
839 /* Build a GIMPLE_OMP_TASK statement.
840
841    BODY is sequence of statements which are executed by the explicit task.
842    CLAUSES, are the OMP parallel construct's clauses.
843    CHILD_FN is the function created for the parallel threads to execute.
844    DATA_ARG are the shared data argument(s).
845    COPY_FN is the optional function for firstprivate initialization.
846    ARG_SIZE and ARG_ALIGN are size and alignment of the data block.  */
847
848 gimple 
849 gimple_build_omp_task (gimple_seq body, tree clauses, tree child_fn,
850                        tree data_arg, tree copy_fn, tree arg_size,
851                        tree arg_align)
852 {
853   gimple p = gimple_alloc (GIMPLE_OMP_TASK, 0);
854   if (body)
855     gimple_omp_set_body (p, body);
856   gimple_omp_task_set_clauses (p, clauses);
857   gimple_omp_task_set_child_fn (p, child_fn);
858   gimple_omp_task_set_data_arg (p, data_arg);
859   gimple_omp_task_set_copy_fn (p, copy_fn);
860   gimple_omp_task_set_arg_size (p, arg_size);
861   gimple_omp_task_set_arg_align (p, arg_align);
862
863   return p;
864 }
865
866
867 /* Build a GIMPLE_OMP_SECTION statement for a sections statement.
868
869    BODY is the sequence of statements in the section.  */
870
871 gimple
872 gimple_build_omp_section (gimple_seq body)
873 {
874   gimple p = gimple_alloc (GIMPLE_OMP_SECTION, 0);
875   if (body)
876     gimple_omp_set_body (p, body);
877
878   return p;
879 }
880
881
882 /* Build a GIMPLE_OMP_MASTER statement.
883
884    BODY is the sequence of statements to be executed by just the master.  */
885
886 gimple 
887 gimple_build_omp_master (gimple_seq body)
888 {
889   gimple p = gimple_alloc (GIMPLE_OMP_MASTER, 0);
890   if (body)
891     gimple_omp_set_body (p, body);
892
893   return p;
894 }
895
896
897 /* Build a GIMPLE_OMP_CONTINUE statement.
898
899    CONTROL_DEF is the definition of the control variable.
900    CONTROL_USE is the use of the control variable.  */
901
902 gimple 
903 gimple_build_omp_continue (tree control_def, tree control_use)
904 {
905   gimple p = gimple_alloc (GIMPLE_OMP_CONTINUE, 0);
906   gimple_omp_continue_set_control_def (p, control_def);
907   gimple_omp_continue_set_control_use (p, control_use);
908   return p;
909 }
910
911 /* Build a GIMPLE_OMP_ORDERED statement.
912
913    BODY is the sequence of statements inside a loop that will executed in
914    sequence.  */
915
916 gimple 
917 gimple_build_omp_ordered (gimple_seq body)
918 {
919   gimple p = gimple_alloc (GIMPLE_OMP_ORDERED, 0);
920   if (body)
921     gimple_omp_set_body (p, body);
922
923   return p;
924 }
925
926
927 /* Build a GIMPLE_OMP_RETURN statement.
928    WAIT_P is true if this is a non-waiting return.  */
929
930 gimple 
931 gimple_build_omp_return (bool wait_p)
932 {
933   gimple p = gimple_alloc (GIMPLE_OMP_RETURN, 0);
934   if (wait_p)
935     gimple_omp_return_set_nowait (p);
936
937   return p;
938 }
939
940
941 /* Build a GIMPLE_OMP_SECTIONS statement.
942
943    BODY is a sequence of section statements.
944    CLAUSES are any of the OMP sections contsruct's clauses: private,
945    firstprivate, lastprivate, reduction, and nowait.  */
946
947 gimple 
948 gimple_build_omp_sections (gimple_seq body, tree clauses)
949 {
950   gimple p = gimple_alloc (GIMPLE_OMP_SECTIONS, 0);
951   if (body)
952     gimple_omp_set_body (p, body);
953   gimple_omp_sections_set_clauses (p, clauses);
954
955   return p;
956 }
957
958
959 /* Build a GIMPLE_OMP_SECTIONS_SWITCH.  */
960
961 gimple
962 gimple_build_omp_sections_switch (void)
963 {
964   return gimple_alloc (GIMPLE_OMP_SECTIONS_SWITCH, 0);
965 }
966
967
968 /* Build a GIMPLE_OMP_SINGLE statement.
969
970    BODY is the sequence of statements that will be executed once.
971    CLAUSES are any of the OMP single construct's clauses: private, firstprivate,
972    copyprivate, nowait.  */
973
974 gimple 
975 gimple_build_omp_single (gimple_seq body, tree clauses)
976 {
977   gimple p = gimple_alloc (GIMPLE_OMP_SINGLE, 0);
978   if (body)
979     gimple_omp_set_body (p, body);
980   gimple_omp_single_set_clauses (p, clauses);
981
982   return p;
983 }
984
985
986 /* Build a GIMPLE_OMP_ATOMIC_LOAD statement.  */
987
988 gimple
989 gimple_build_omp_atomic_load (tree lhs, tree rhs)
990 {
991   gimple p = gimple_alloc (GIMPLE_OMP_ATOMIC_LOAD, 0);
992   gimple_omp_atomic_load_set_lhs (p, lhs);
993   gimple_omp_atomic_load_set_rhs (p, rhs);
994   return p;
995 }
996
997 /* Build a GIMPLE_OMP_ATOMIC_STORE statement.
998
999    VAL is the value we are storing.  */
1000
1001 gimple
1002 gimple_build_omp_atomic_store (tree val)
1003 {
1004   gimple p = gimple_alloc (GIMPLE_OMP_ATOMIC_STORE, 0);
1005   gimple_omp_atomic_store_set_val (p, val);
1006   return p;
1007 }
1008
1009 /* Build a GIMPLE_PREDICT statement.  PREDICT is one of the predictors from
1010    predict.def, OUTCOME is NOT_TAKEN or TAKEN.  */
1011
1012 gimple
1013 gimple_build_predict (enum br_predictor predictor, enum prediction outcome)
1014 {
1015   gimple p = gimple_alloc (GIMPLE_PREDICT, 0);
1016   /* Ensure all the predictors fit into the lower bits of the subcode.  */
1017   gcc_assert ((int) END_PREDICTORS <= GF_PREDICT_TAKEN);
1018   gimple_predict_set_predictor (p, predictor);
1019   gimple_predict_set_outcome (p, outcome);
1020   return p;
1021 }
1022
1023 #if defined ENABLE_GIMPLE_CHECKING
1024 /* Complain of a gimple type mismatch and die.  */
1025
1026 void
1027 gimple_check_failed (const_gimple gs, const char *file, int line,
1028                      const char *function, enum gimple_code code,
1029                      enum tree_code subcode)
1030 {
1031   internal_error ("gimple check: expected %s(%s), have %s(%s) in %s, at %s:%d",
1032                   gimple_code_name[code],
1033                   tree_code_name[subcode],
1034                   gimple_code_name[gimple_code (gs)],
1035                   gs->gsbase.subcode > 0
1036                     ? tree_code_name[gs->gsbase.subcode]
1037                     : "",
1038                   function, trim_filename (file), line);
1039 }
1040 #endif /* ENABLE_GIMPLE_CHECKING */
1041
1042
1043 /* Allocate a new GIMPLE sequence in GC memory and return it.  If
1044    there are free sequences in GIMPLE_SEQ_CACHE return one of those
1045    instead.  */
1046
1047 gimple_seq
1048 gimple_seq_alloc (void)
1049 {
1050   gimple_seq seq = gimple_seq_cache;
1051   if (seq)
1052     {
1053       gimple_seq_cache = gimple_seq_cache->next_free;
1054       gcc_assert (gimple_seq_cache != seq);
1055       memset (seq, 0, sizeof (*seq));
1056     }
1057   else
1058     {
1059       seq = (gimple_seq) ggc_alloc_cleared (sizeof (*seq));
1060 #ifdef GATHER_STATISTICS
1061       gimple_alloc_counts[(int) gimple_alloc_kind_seq]++;
1062       gimple_alloc_sizes[(int) gimple_alloc_kind_seq] += sizeof (*seq);
1063 #endif
1064     }
1065
1066   return seq;
1067 }
1068
1069 /* Return SEQ to the free pool of GIMPLE sequences.  */
1070
1071 void
1072 gimple_seq_free (gimple_seq seq)
1073 {
1074   if (seq == NULL)
1075     return;
1076
1077   gcc_assert (gimple_seq_first (seq) == NULL);
1078   gcc_assert (gimple_seq_last (seq) == NULL);
1079
1080   /* If this triggers, it's a sign that the same list is being freed
1081      twice.  */
1082   gcc_assert (seq != gimple_seq_cache || gimple_seq_cache == NULL);
1083   
1084   /* Add SEQ to the pool of free sequences.  */
1085   seq->next_free = gimple_seq_cache;
1086   gimple_seq_cache = seq;
1087 }
1088
1089
1090 /* Link gimple statement GS to the end of the sequence *SEQ_P.  If
1091    *SEQ_P is NULL, a new sequence is allocated.  */
1092
1093 void
1094 gimple_seq_add_stmt (gimple_seq *seq_p, gimple gs)
1095 {
1096   gimple_stmt_iterator si;
1097
1098   if (gs == NULL)
1099     return;
1100
1101   if (*seq_p == NULL)
1102     *seq_p = gimple_seq_alloc ();
1103
1104   si = gsi_last (*seq_p);
1105   gsi_insert_after (&si, gs, GSI_NEW_STMT);
1106 }
1107
1108
1109 /* Append sequence SRC to the end of sequence *DST_P.  If *DST_P is
1110    NULL, a new sequence is allocated.  */
1111
1112 void
1113 gimple_seq_add_seq (gimple_seq *dst_p, gimple_seq src)
1114 {
1115   gimple_stmt_iterator si;
1116
1117   if (src == NULL)
1118     return;
1119
1120   if (*dst_p == NULL)
1121     *dst_p = gimple_seq_alloc ();
1122
1123   si = gsi_last (*dst_p);
1124   gsi_insert_seq_after (&si, src, GSI_NEW_STMT);
1125 }
1126
1127
1128 /* Helper function of empty_body_p.  Return true if STMT is an empty
1129    statement.  */
1130
1131 static bool
1132 empty_stmt_p (gimple stmt)
1133 {
1134   if (gimple_code (stmt) == GIMPLE_NOP)
1135     return true;
1136   if (gimple_code (stmt) == GIMPLE_BIND)
1137     return empty_body_p (gimple_bind_body (stmt));
1138   return false;
1139 }
1140
1141
1142 /* Return true if BODY contains nothing but empty statements.  */
1143
1144 bool
1145 empty_body_p (gimple_seq body)
1146 {
1147   gimple_stmt_iterator i;
1148
1149   if (gimple_seq_empty_p (body))
1150     return true;
1151   for (i = gsi_start (body); !gsi_end_p (i); gsi_next (&i))
1152     if (!empty_stmt_p (gsi_stmt (i))
1153         && !is_gimple_debug (gsi_stmt (i)))
1154       return false;
1155
1156   return true;
1157 }
1158
1159
1160 /* Perform a deep copy of sequence SRC and return the result.  */
1161
1162 gimple_seq
1163 gimple_seq_copy (gimple_seq src)
1164 {
1165   gimple_stmt_iterator gsi;
1166   gimple_seq new_seq = gimple_seq_alloc ();
1167   gimple stmt;
1168
1169   for (gsi = gsi_start (src); !gsi_end_p (gsi); gsi_next (&gsi))
1170     {
1171       stmt = gimple_copy (gsi_stmt (gsi));
1172       gimple_seq_add_stmt (&new_seq, stmt);
1173     }
1174
1175   return new_seq;
1176 }
1177
1178
1179 /* Walk all the statements in the sequence SEQ calling walk_gimple_stmt
1180    on each one.  WI is as in walk_gimple_stmt.
1181    
1182    If walk_gimple_stmt returns non-NULL, the walk is stopped, the
1183    value is stored in WI->CALLBACK_RESULT and the statement that
1184    produced the value is returned.
1185
1186    Otherwise, all the statements are walked and NULL returned.  */
1187
1188 gimple
1189 walk_gimple_seq (gimple_seq seq, walk_stmt_fn callback_stmt,
1190                  walk_tree_fn callback_op, struct walk_stmt_info *wi)
1191 {
1192   gimple_stmt_iterator gsi;
1193
1194   for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
1195     {
1196       tree ret = walk_gimple_stmt (&gsi, callback_stmt, callback_op, wi);
1197       if (ret)
1198         {
1199           /* If CALLBACK_STMT or CALLBACK_OP return a value, WI must exist
1200              to hold it.  */
1201           gcc_assert (wi);
1202           wi->callback_result = ret;
1203           return gsi_stmt (gsi);
1204         }
1205     }
1206
1207   if (wi)
1208     wi->callback_result = NULL_TREE;
1209
1210   return NULL;
1211 }
1212
1213
1214 /* Helper function for walk_gimple_stmt.  Walk operands of a GIMPLE_ASM.  */
1215
1216 static tree
1217 walk_gimple_asm (gimple stmt, walk_tree_fn callback_op,
1218                  struct walk_stmt_info *wi)
1219 {
1220   tree ret, op;
1221   unsigned noutputs;
1222   const char **oconstraints;
1223   unsigned i, n;
1224   const char *constraint;
1225   bool allows_mem, allows_reg, is_inout;
1226
1227   noutputs = gimple_asm_noutputs (stmt);
1228   oconstraints = (const char **) alloca ((noutputs) * sizeof (const char *));
1229
1230   if (wi)
1231     wi->is_lhs = true;
1232
1233   for (i = 0; i < noutputs; i++)
1234     {
1235       op = gimple_asm_output_op (stmt, i);
1236       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
1237       oconstraints[i] = constraint;
1238       parse_output_constraint (&constraint, i, 0, 0, &allows_mem, &allows_reg,
1239                                &is_inout);
1240       if (wi)
1241         wi->val_only = (allows_reg || !allows_mem);
1242       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1243       if (ret)
1244         return ret;
1245     }
1246
1247   n = gimple_asm_ninputs (stmt);
1248   for (i = 0; i < n; i++)
1249     {
1250       op = gimple_asm_input_op (stmt, i);
1251       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
1252       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1253                               oconstraints, &allows_mem, &allows_reg);
1254       if (wi)
1255         {
1256           wi->val_only = (allows_reg || !allows_mem);
1257           /* Although input "m" is not really a LHS, we need a lvalue.  */
1258           wi->is_lhs = !wi->val_only;
1259         }
1260       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1261       if (ret)
1262         return ret;
1263     }
1264
1265   if (wi)
1266     {
1267       wi->is_lhs = false;
1268       wi->val_only = true;
1269     }
1270
1271   n = gimple_asm_nlabels (stmt);
1272   for (i = 0; i < n; i++)
1273     {
1274       op = gimple_asm_label_op (stmt, i);
1275       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1276       if (ret)
1277         return ret;
1278     }
1279
1280   return NULL_TREE;
1281 }
1282
1283
1284 /* Helper function of WALK_GIMPLE_STMT.  Walk every tree operand in
1285    STMT.  CALLBACK_OP and WI are as in WALK_GIMPLE_STMT.
1286
1287    CALLBACK_OP is called on each operand of STMT via walk_tree.
1288    Additional parameters to walk_tree must be stored in WI.  For each operand
1289    OP, walk_tree is called as:
1290
1291         walk_tree (&OP, CALLBACK_OP, WI, WI->PSET)
1292
1293    If CALLBACK_OP returns non-NULL for an operand, the remaining
1294    operands are not scanned.
1295
1296    The return value is that returned by the last call to walk_tree, or
1297    NULL_TREE if no CALLBACK_OP is specified.  */
1298
1299 inline tree
1300 walk_gimple_op (gimple stmt, walk_tree_fn callback_op,
1301                 struct walk_stmt_info *wi)
1302 {
1303   struct pointer_set_t *pset = (wi) ? wi->pset : NULL;
1304   unsigned i;
1305   tree ret = NULL_TREE;
1306
1307   switch (gimple_code (stmt))
1308     {
1309     case GIMPLE_ASSIGN:
1310       /* Walk the RHS operands.  A formal temporary LHS may use a
1311          COMPONENT_REF RHS.  */
1312       if (wi)
1313         wi->val_only = !is_gimple_reg (gimple_assign_lhs (stmt))
1314                        || !gimple_assign_single_p (stmt);
1315
1316       for (i = 1; i < gimple_num_ops (stmt); i++)
1317         {
1318           ret = walk_tree (gimple_op_ptr (stmt, i), callback_op, wi,
1319                            pset);
1320           if (ret)
1321             return ret;
1322         }
1323
1324       /* Walk the LHS.  If the RHS is appropriate for a memory, we
1325          may use a COMPONENT_REF on the LHS.  */
1326       if (wi)
1327         {
1328           /* If the RHS has more than 1 operand, it is not appropriate
1329              for the memory.  */
1330           wi->val_only = !is_gimple_mem_rhs (gimple_assign_rhs1 (stmt))
1331                          || !gimple_assign_single_p (stmt);
1332           wi->is_lhs = true;
1333         }
1334
1335       ret = walk_tree (gimple_op_ptr (stmt, 0), callback_op, wi, pset);
1336       if (ret)
1337         return ret;
1338
1339       if (wi)
1340         {
1341           wi->val_only = true;
1342           wi->is_lhs = false;
1343         }
1344       break;
1345
1346     case GIMPLE_CALL:
1347       if (wi)
1348         wi->is_lhs = false;
1349
1350       ret = walk_tree (gimple_call_chain_ptr (stmt), callback_op, wi, pset);
1351       if (ret)
1352         return ret;
1353
1354       ret = walk_tree (gimple_call_fn_ptr (stmt), callback_op, wi, pset);
1355       if (ret)
1356         return ret;
1357
1358       for (i = 0; i < gimple_call_num_args (stmt); i++)
1359         {
1360           ret = walk_tree (gimple_call_arg_ptr (stmt, i), callback_op, wi,
1361                            pset);
1362           if (ret)
1363             return ret;
1364         }
1365
1366       if (wi)
1367         wi->is_lhs = true;
1368
1369       ret = walk_tree (gimple_call_lhs_ptr (stmt), callback_op, wi, pset);
1370       if (ret)
1371         return ret;
1372
1373       if (wi)
1374         wi->is_lhs = false;
1375       break;
1376
1377     case GIMPLE_CATCH:
1378       ret = walk_tree (gimple_catch_types_ptr (stmt), callback_op, wi,
1379                        pset);
1380       if (ret)
1381         return ret;
1382       break;
1383
1384     case GIMPLE_EH_FILTER:
1385       ret = walk_tree (gimple_eh_filter_types_ptr (stmt), callback_op, wi,
1386                        pset);
1387       if (ret)
1388         return ret;
1389       break;
1390
1391     case GIMPLE_ASM:
1392       ret = walk_gimple_asm (stmt, callback_op, wi);
1393       if (ret)
1394         return ret;
1395       break;
1396
1397     case GIMPLE_OMP_CONTINUE:
1398       ret = walk_tree (gimple_omp_continue_control_def_ptr (stmt),
1399                        callback_op, wi, pset);
1400       if (ret)
1401         return ret;
1402
1403       ret = walk_tree (gimple_omp_continue_control_use_ptr (stmt),
1404                        callback_op, wi, pset);
1405       if (ret)
1406         return ret;
1407       break;
1408
1409     case GIMPLE_OMP_CRITICAL:
1410       ret = walk_tree (gimple_omp_critical_name_ptr (stmt), callback_op, wi,
1411                        pset);
1412       if (ret)
1413         return ret;
1414       break;
1415
1416     case GIMPLE_OMP_FOR:
1417       ret = walk_tree (gimple_omp_for_clauses_ptr (stmt), callback_op, wi,
1418                        pset);
1419       if (ret)
1420         return ret;
1421       for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
1422         {
1423           ret = walk_tree (gimple_omp_for_index_ptr (stmt, i), callback_op,
1424                            wi, pset);
1425           if (ret)
1426             return ret;
1427           ret = walk_tree (gimple_omp_for_initial_ptr (stmt, i), callback_op,
1428                            wi, pset);
1429           if (ret)
1430             return ret;
1431           ret = walk_tree (gimple_omp_for_final_ptr (stmt, i), callback_op,
1432                            wi, pset);
1433           if (ret)
1434             return ret;
1435           ret = walk_tree (gimple_omp_for_incr_ptr (stmt, i), callback_op,
1436                            wi, pset);
1437         }
1438       if (ret)
1439         return ret;
1440       break;
1441
1442     case GIMPLE_OMP_PARALLEL:
1443       ret = walk_tree (gimple_omp_parallel_clauses_ptr (stmt), callback_op,
1444                        wi, pset);
1445       if (ret)
1446         return ret;
1447       ret = walk_tree (gimple_omp_parallel_child_fn_ptr (stmt), callback_op,
1448                        wi, pset);
1449       if (ret)
1450         return ret;
1451       ret = walk_tree (gimple_omp_parallel_data_arg_ptr (stmt), callback_op,
1452                        wi, pset);
1453       if (ret)
1454         return ret;
1455       break;
1456
1457     case GIMPLE_OMP_TASK:
1458       ret = walk_tree (gimple_omp_task_clauses_ptr (stmt), callback_op,
1459                        wi, pset);
1460       if (ret)
1461         return ret;
1462       ret = walk_tree (gimple_omp_task_child_fn_ptr (stmt), callback_op,
1463                        wi, pset);
1464       if (ret)
1465         return ret;
1466       ret = walk_tree (gimple_omp_task_data_arg_ptr (stmt), callback_op,
1467                        wi, pset);
1468       if (ret)
1469         return ret;
1470       ret = walk_tree (gimple_omp_task_copy_fn_ptr (stmt), callback_op,
1471                        wi, pset);
1472       if (ret)
1473         return ret;
1474       ret = walk_tree (gimple_omp_task_arg_size_ptr (stmt), callback_op,
1475                        wi, pset);
1476       if (ret)
1477         return ret;
1478       ret = walk_tree (gimple_omp_task_arg_align_ptr (stmt), callback_op,
1479                        wi, pset);
1480       if (ret)
1481         return ret;
1482       break;
1483
1484     case GIMPLE_OMP_SECTIONS:
1485       ret = walk_tree (gimple_omp_sections_clauses_ptr (stmt), callback_op,
1486                        wi, pset);
1487       if (ret)
1488         return ret;
1489
1490       ret = walk_tree (gimple_omp_sections_control_ptr (stmt), callback_op,
1491                        wi, pset);
1492       if (ret)
1493         return ret;
1494
1495       break;
1496
1497     case GIMPLE_OMP_SINGLE:
1498       ret = walk_tree (gimple_omp_single_clauses_ptr (stmt), callback_op, wi,
1499                        pset);
1500       if (ret)
1501         return ret;
1502       break;
1503
1504     case GIMPLE_OMP_ATOMIC_LOAD:
1505       ret = walk_tree (gimple_omp_atomic_load_lhs_ptr (stmt), callback_op, wi,
1506                        pset);
1507       if (ret)
1508         return ret;
1509
1510       ret = walk_tree (gimple_omp_atomic_load_rhs_ptr (stmt), callback_op, wi,
1511                        pset);
1512       if (ret)
1513         return ret;
1514       break;
1515
1516     case GIMPLE_OMP_ATOMIC_STORE:
1517       ret = walk_tree (gimple_omp_atomic_store_val_ptr (stmt), callback_op,
1518                        wi, pset);
1519       if (ret)
1520         return ret;
1521       break;
1522
1523       /* Tuples that do not have operands.  */
1524     case GIMPLE_NOP:
1525     case GIMPLE_RESX:
1526     case GIMPLE_OMP_RETURN:
1527     case GIMPLE_PREDICT:
1528       break;
1529
1530     default:
1531       {
1532         enum gimple_statement_structure_enum gss;
1533         gss = gimple_statement_structure (stmt);
1534         if (gss == GSS_WITH_OPS || gss == GSS_WITH_MEM_OPS)
1535           for (i = 0; i < gimple_num_ops (stmt); i++)
1536             {
1537               ret = walk_tree (gimple_op_ptr (stmt, i), callback_op, wi, pset);
1538               if (ret)
1539                 return ret;
1540             }
1541       }
1542       break;
1543     }
1544
1545   return NULL_TREE;
1546 }
1547
1548
1549 /* Walk the current statement in GSI (optionally using traversal state
1550    stored in WI).  If WI is NULL, no state is kept during traversal.
1551    The callback CALLBACK_STMT is called.  If CALLBACK_STMT indicates
1552    that it has handled all the operands of the statement, its return
1553    value is returned.  Otherwise, the return value from CALLBACK_STMT
1554    is discarded and its operands are scanned.
1555
1556    If CALLBACK_STMT is NULL or it didn't handle the operands,
1557    CALLBACK_OP is called on each operand of the statement via
1558    walk_gimple_op.  If walk_gimple_op returns non-NULL for any
1559    operand, the remaining operands are not scanned.  In this case, the
1560    return value from CALLBACK_OP is returned.
1561
1562    In any other case, NULL_TREE is returned.  */
1563
1564 tree
1565 walk_gimple_stmt (gimple_stmt_iterator *gsi, walk_stmt_fn callback_stmt,
1566                   walk_tree_fn callback_op, struct walk_stmt_info *wi)
1567 {
1568   gimple ret;
1569   tree tree_ret;
1570   gimple stmt = gsi_stmt (*gsi);
1571
1572   if (wi)
1573     wi->gsi = *gsi;
1574
1575   if (wi && wi->want_locations && gimple_has_location (stmt))
1576     input_location = gimple_location (stmt);
1577
1578   ret = NULL;
1579
1580   /* Invoke the statement callback.  Return if the callback handled
1581      all of STMT operands by itself.  */
1582   if (callback_stmt)
1583     {
1584       bool handled_ops = false;
1585       tree_ret = callback_stmt (gsi, &handled_ops, wi);
1586       if (handled_ops)
1587         return tree_ret;
1588
1589       /* If CALLBACK_STMT did not handle operands, it should not have
1590          a value to return.  */
1591       gcc_assert (tree_ret == NULL);
1592
1593       /* Re-read stmt in case the callback changed it.  */
1594       stmt = gsi_stmt (*gsi);
1595     }
1596
1597   /* If CALLBACK_OP is defined, invoke it on every operand of STMT.  */
1598   if (callback_op)
1599     {
1600       tree_ret = walk_gimple_op (stmt, callback_op, wi);
1601       if (tree_ret)
1602         return tree_ret;
1603     }
1604
1605   /* If STMT can have statements inside (e.g. GIMPLE_BIND), walk them.  */
1606   switch (gimple_code (stmt))
1607     {
1608     case GIMPLE_BIND:
1609       ret = walk_gimple_seq (gimple_bind_body (stmt), callback_stmt,
1610                              callback_op, wi);
1611       if (ret)
1612         return wi->callback_result;
1613       break;
1614
1615     case GIMPLE_CATCH:
1616       ret = walk_gimple_seq (gimple_catch_handler (stmt), callback_stmt,
1617                              callback_op, wi);
1618       if (ret)
1619         return wi->callback_result;
1620       break;
1621
1622     case GIMPLE_EH_FILTER:
1623       ret = walk_gimple_seq (gimple_eh_filter_failure (stmt), callback_stmt,
1624                              callback_op, wi);
1625       if (ret)
1626         return wi->callback_result;
1627       break;
1628
1629     case GIMPLE_TRY:
1630       ret = walk_gimple_seq (gimple_try_eval (stmt), callback_stmt, callback_op,
1631                              wi);
1632       if (ret)
1633         return wi->callback_result;
1634
1635       ret = walk_gimple_seq (gimple_try_cleanup (stmt), callback_stmt,
1636                              callback_op, wi);
1637       if (ret)
1638         return wi->callback_result;
1639       break;
1640
1641     case GIMPLE_OMP_FOR:
1642       ret = walk_gimple_seq (gimple_omp_for_pre_body (stmt), callback_stmt,
1643                              callback_op, wi);
1644       if (ret)
1645         return wi->callback_result;
1646
1647       /* FALL THROUGH.  */
1648     case GIMPLE_OMP_CRITICAL:
1649     case GIMPLE_OMP_MASTER:
1650     case GIMPLE_OMP_ORDERED:
1651     case GIMPLE_OMP_SECTION:
1652     case GIMPLE_OMP_PARALLEL:
1653     case GIMPLE_OMP_TASK:
1654     case GIMPLE_OMP_SECTIONS:
1655     case GIMPLE_OMP_SINGLE:
1656       ret = walk_gimple_seq (gimple_omp_body (stmt), callback_stmt, callback_op,
1657                              wi);
1658       if (ret)
1659         return wi->callback_result;
1660       break;
1661
1662     case GIMPLE_WITH_CLEANUP_EXPR:
1663       ret = walk_gimple_seq (gimple_wce_cleanup (stmt), callback_stmt,
1664                              callback_op, wi);
1665       if (ret)
1666         return wi->callback_result;
1667       break;
1668
1669     default:
1670       gcc_assert (!gimple_has_substatements (stmt));
1671       break;
1672     }
1673
1674   return NULL;
1675 }
1676
1677
1678 /* Set sequence SEQ to be the GIMPLE body for function FN.  */
1679
1680 void
1681 gimple_set_body (tree fndecl, gimple_seq seq)
1682 {
1683   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1684   if (fn == NULL)
1685     {
1686       /* If FNDECL still does not have a function structure associated
1687          with it, then it does not make sense for it to receive a
1688          GIMPLE body.  */
1689       gcc_assert (seq == NULL);
1690     }
1691   else
1692     fn->gimple_body = seq;
1693 }
1694
1695
1696 /* Return the body of GIMPLE statements for function FN.  */
1697
1698 gimple_seq
1699 gimple_body (tree fndecl)
1700 {
1701   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1702   return fn ? fn->gimple_body : NULL;
1703 }
1704
1705 /* Return true when FNDECL has Gimple body either in unlowered
1706    or CFG form.  */
1707 bool
1708 gimple_has_body_p (tree fndecl)
1709 {
1710   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1711   return (gimple_body (fndecl) || (fn && fn->cfg));
1712 }
1713
1714 /* Detect flags from a GIMPLE_CALL.  This is just like
1715    call_expr_flags, but for gimple tuples.  */
1716
1717 int
1718 gimple_call_flags (const_gimple stmt)
1719 {
1720   int flags;
1721   tree decl = gimple_call_fndecl (stmt);
1722   tree t;
1723
1724   if (decl)
1725     flags = flags_from_decl_or_type (decl);
1726   else
1727     {
1728       t = TREE_TYPE (gimple_call_fn (stmt));
1729       if (t && TREE_CODE (t) == POINTER_TYPE)
1730         flags = flags_from_decl_or_type (TREE_TYPE (t));
1731       else
1732         flags = 0;
1733     }
1734
1735   return flags;
1736 }
1737
1738
1739 /* Return true if GS is a copy assignment.  */
1740
1741 bool
1742 gimple_assign_copy_p (gimple gs)
1743 {
1744   return gimple_code (gs) == GIMPLE_ASSIGN
1745          && get_gimple_rhs_class (gimple_assign_rhs_code (gs))
1746             == GIMPLE_SINGLE_RHS
1747          && is_gimple_val (gimple_op (gs, 1));
1748 }
1749
1750
1751 /* Return true if GS is a SSA_NAME copy assignment.  */
1752
1753 bool
1754 gimple_assign_ssa_name_copy_p (gimple gs)
1755 {
1756   return (gimple_code (gs) == GIMPLE_ASSIGN
1757           && (get_gimple_rhs_class (gimple_assign_rhs_code (gs))
1758               == GIMPLE_SINGLE_RHS)
1759           && TREE_CODE (gimple_assign_lhs (gs)) == SSA_NAME
1760           && TREE_CODE (gimple_assign_rhs1 (gs)) == SSA_NAME);
1761 }
1762
1763
1764 /* Return true if GS is an assignment with a singleton RHS, i.e.,
1765    there is no operator associated with the assignment itself.
1766    Unlike gimple_assign_copy_p, this predicate returns true for
1767    any RHS operand, including those that perform an operation
1768    and do not have the semantics of a copy, such as COND_EXPR.  */
1769
1770 bool
1771 gimple_assign_single_p (gimple gs)
1772 {
1773   return (gimple_code (gs) == GIMPLE_ASSIGN
1774           && get_gimple_rhs_class (gimple_assign_rhs_code (gs))
1775              == GIMPLE_SINGLE_RHS);
1776 }
1777
1778 /* Return true if GS is an assignment with a unary RHS, but the
1779    operator has no effect on the assigned value.  The logic is adapted
1780    from STRIP_NOPS.  This predicate is intended to be used in tuplifying
1781    instances in which STRIP_NOPS was previously applied to the RHS of
1782    an assignment.
1783
1784    NOTE: In the use cases that led to the creation of this function
1785    and of gimple_assign_single_p, it is typical to test for either
1786    condition and to proceed in the same manner.  In each case, the
1787    assigned value is represented by the single RHS operand of the
1788    assignment.  I suspect there may be cases where gimple_assign_copy_p,
1789    gimple_assign_single_p, or equivalent logic is used where a similar
1790    treatment of unary NOPs is appropriate.  */
1791    
1792 bool
1793 gimple_assign_unary_nop_p (gimple gs)
1794 {
1795   return (gimple_code (gs) == GIMPLE_ASSIGN
1796           && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))
1797               || gimple_assign_rhs_code (gs) == NON_LVALUE_EXPR)
1798           && gimple_assign_rhs1 (gs) != error_mark_node
1799           && (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs)))
1800               == TYPE_MODE (TREE_TYPE (gimple_assign_rhs1 (gs)))));
1801 }
1802
1803 /* Set BB to be the basic block holding G.  */
1804
1805 void
1806 gimple_set_bb (gimple stmt, basic_block bb)
1807 {
1808   stmt->gsbase.bb = bb;
1809
1810   /* If the statement is a label, add the label to block-to-labels map
1811      so that we can speed up edge creation for GIMPLE_GOTOs.  */
1812   if (cfun->cfg && gimple_code (stmt) == GIMPLE_LABEL)
1813     {
1814       tree t;
1815       int uid;
1816
1817       t = gimple_label_label (stmt);
1818       uid = LABEL_DECL_UID (t);
1819       if (uid == -1)
1820         {
1821           unsigned old_len = VEC_length (basic_block, label_to_block_map);
1822           LABEL_DECL_UID (t) = uid = cfun->cfg->last_label_uid++;
1823           if (old_len <= (unsigned) uid)
1824             {
1825               unsigned new_len = 3 * uid / 2 + 1;
1826
1827               VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
1828                                      new_len);
1829             }
1830         }
1831
1832       VEC_replace (basic_block, label_to_block_map, uid, bb);
1833     }
1834 }
1835
1836
1837 /* Fold the expression computed by STMT.  If the expression can be
1838    folded, return the folded result, otherwise return NULL.  STMT is
1839    not modified.  */
1840
1841 tree
1842 gimple_fold (const_gimple stmt)
1843 {
1844   location_t loc = gimple_location (stmt);
1845   switch (gimple_code (stmt))
1846     {
1847     case GIMPLE_COND:
1848       return fold_binary_loc (loc, gimple_cond_code (stmt),
1849                           boolean_type_node,
1850                           gimple_cond_lhs (stmt),
1851                           gimple_cond_rhs (stmt));
1852
1853     case GIMPLE_ASSIGN:
1854       switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
1855         {
1856         case GIMPLE_UNARY_RHS:
1857           return fold_unary_loc (loc, gimple_assign_rhs_code (stmt),
1858                              TREE_TYPE (gimple_assign_lhs (stmt)),
1859                              gimple_assign_rhs1 (stmt));
1860         case GIMPLE_BINARY_RHS:
1861           return fold_binary_loc (loc, gimple_assign_rhs_code (stmt),
1862                               TREE_TYPE (gimple_assign_lhs (stmt)),
1863                               gimple_assign_rhs1 (stmt),
1864                               gimple_assign_rhs2 (stmt));
1865         case GIMPLE_SINGLE_RHS:
1866           return fold (gimple_assign_rhs1 (stmt));
1867         default:;
1868         }
1869       break;
1870
1871     case GIMPLE_SWITCH:
1872       return gimple_switch_index (stmt);
1873
1874     case GIMPLE_CALL:
1875       return NULL_TREE;
1876
1877     default:
1878       break;
1879     }
1880
1881   gcc_unreachable ();
1882 }
1883
1884
1885 /* Modify the RHS of the assignment pointed-to by GSI using the
1886    operands in the expression tree EXPR.
1887
1888    NOTE: The statement pointed-to by GSI may be reallocated if it
1889    did not have enough operand slots.
1890
1891    This function is useful to convert an existing tree expression into
1892    the flat representation used for the RHS of a GIMPLE assignment.
1893    It will reallocate memory as needed to expand or shrink the number
1894    of operand slots needed to represent EXPR.
1895
1896    NOTE: If you find yourself building a tree and then calling this
1897    function, you are most certainly doing it the slow way.  It is much
1898    better to build a new assignment or to use the function
1899    gimple_assign_set_rhs_with_ops, which does not require an
1900    expression tree to be built.  */
1901
1902 void
1903 gimple_assign_set_rhs_from_tree (gimple_stmt_iterator *gsi, tree expr)
1904 {
1905   enum tree_code subcode;
1906   tree op1, op2;
1907
1908   extract_ops_from_tree (expr, &subcode, &op1, &op2);
1909   gimple_assign_set_rhs_with_ops (gsi, subcode, op1, op2);
1910 }
1911
1912
1913 /* Set the RHS of assignment statement pointed-to by GSI to CODE with
1914    operands OP1 and OP2.
1915
1916    NOTE: The statement pointed-to by GSI may be reallocated if it
1917    did not have enough operand slots.  */
1918
1919 void
1920 gimple_assign_set_rhs_with_ops (gimple_stmt_iterator *gsi, enum tree_code code,
1921                                 tree op1, tree op2)
1922 {
1923   unsigned new_rhs_ops = get_gimple_rhs_num_ops (code);
1924   gimple stmt = gsi_stmt (*gsi);
1925
1926   /* If the new CODE needs more operands, allocate a new statement.  */
1927   if (gimple_num_ops (stmt) < new_rhs_ops + 1)
1928     {
1929       tree lhs = gimple_assign_lhs (stmt);
1930       gimple new_stmt = gimple_alloc (gimple_code (stmt), new_rhs_ops + 1);
1931       memcpy (new_stmt, stmt, gimple_size (gimple_code (stmt)));
1932       gsi_replace (gsi, new_stmt, true);
1933       stmt = new_stmt;
1934
1935       /* The LHS needs to be reset as this also changes the SSA name
1936          on the LHS.  */
1937       gimple_assign_set_lhs (stmt, lhs);
1938     }
1939
1940   gimple_set_num_ops (stmt, new_rhs_ops + 1);
1941   gimple_set_subcode (stmt, code);
1942   gimple_assign_set_rhs1 (stmt, op1);
1943   if (new_rhs_ops > 1)
1944     gimple_assign_set_rhs2 (stmt, op2);
1945 }
1946
1947
1948 /* Return the LHS of a statement that performs an assignment,
1949    either a GIMPLE_ASSIGN or a GIMPLE_CALL.  Returns NULL_TREE
1950    for a call to a function that returns no value, or for a
1951    statement other than an assignment or a call.  */
1952
1953 tree
1954 gimple_get_lhs (const_gimple stmt)
1955 {
1956   enum gimple_code code = gimple_code (stmt);
1957
1958   if (code == GIMPLE_ASSIGN)
1959     return gimple_assign_lhs (stmt);
1960   else if (code == GIMPLE_CALL)
1961     return gimple_call_lhs (stmt);
1962   else
1963     return NULL_TREE;
1964 }
1965
1966
1967 /* Set the LHS of a statement that performs an assignment,
1968    either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
1969
1970 void
1971 gimple_set_lhs (gimple stmt, tree lhs)
1972 {
1973   enum gimple_code code = gimple_code (stmt);
1974
1975   if (code == GIMPLE_ASSIGN)
1976     gimple_assign_set_lhs (stmt, lhs);
1977   else if (code == GIMPLE_CALL)
1978     gimple_call_set_lhs (stmt, lhs);
1979   else
1980     gcc_unreachable();
1981 }
1982
1983
1984 /* Return a deep copy of statement STMT.  All the operands from STMT
1985    are reallocated and copied using unshare_expr.  The DEF, USE, VDEF
1986    and VUSE operand arrays are set to empty in the new copy.  */
1987
1988 gimple
1989 gimple_copy (gimple stmt)
1990 {
1991   enum gimple_code code = gimple_code (stmt);
1992   unsigned num_ops = gimple_num_ops (stmt);
1993   gimple copy = gimple_alloc (code, num_ops);
1994   unsigned i;
1995
1996   /* Shallow copy all the fields from STMT.  */
1997   memcpy (copy, stmt, gimple_size (code));
1998
1999   /* If STMT has sub-statements, deep-copy them as well.  */
2000   if (gimple_has_substatements (stmt))
2001     {
2002       gimple_seq new_seq;
2003       tree t;
2004
2005       switch (gimple_code (stmt))
2006         {
2007         case GIMPLE_BIND:
2008           new_seq = gimple_seq_copy (gimple_bind_body (stmt));
2009           gimple_bind_set_body (copy, new_seq);
2010           gimple_bind_set_vars (copy, unshare_expr (gimple_bind_vars (stmt)));
2011           gimple_bind_set_block (copy, gimple_bind_block (stmt));
2012           break;
2013
2014         case GIMPLE_CATCH:
2015           new_seq = gimple_seq_copy (gimple_catch_handler (stmt));
2016           gimple_catch_set_handler (copy, new_seq);
2017           t = unshare_expr (gimple_catch_types (stmt));
2018           gimple_catch_set_types (copy, t);
2019           break;
2020
2021         case GIMPLE_EH_FILTER:
2022           new_seq = gimple_seq_copy (gimple_eh_filter_failure (stmt));
2023           gimple_eh_filter_set_failure (copy, new_seq);
2024           t = unshare_expr (gimple_eh_filter_types (stmt));
2025           gimple_eh_filter_set_types (copy, t);
2026           break;
2027
2028         case GIMPLE_TRY:
2029           new_seq = gimple_seq_copy (gimple_try_eval (stmt));
2030           gimple_try_set_eval (copy, new_seq);
2031           new_seq = gimple_seq_copy (gimple_try_cleanup (stmt));
2032           gimple_try_set_cleanup (copy, new_seq);
2033           break;
2034
2035         case GIMPLE_OMP_FOR:
2036           new_seq = gimple_seq_copy (gimple_omp_for_pre_body (stmt));
2037           gimple_omp_for_set_pre_body (copy, new_seq);
2038           t = unshare_expr (gimple_omp_for_clauses (stmt));
2039           gimple_omp_for_set_clauses (copy, t);
2040           copy->gimple_omp_for.iter
2041             = GGC_NEWVEC (struct gimple_omp_for_iter,
2042                           gimple_omp_for_collapse (stmt));
2043           for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
2044             {
2045               gimple_omp_for_set_cond (copy, i,
2046                                        gimple_omp_for_cond (stmt, i));
2047               gimple_omp_for_set_index (copy, i,
2048                                         gimple_omp_for_index (stmt, i));
2049               t = unshare_expr (gimple_omp_for_initial (stmt, i));
2050               gimple_omp_for_set_initial (copy, i, t);
2051               t = unshare_expr (gimple_omp_for_final (stmt, i));
2052               gimple_omp_for_set_final (copy, i, t);
2053               t = unshare_expr (gimple_omp_for_incr (stmt, i));
2054               gimple_omp_for_set_incr (copy, i, t);
2055             }
2056           goto copy_omp_body;
2057
2058         case GIMPLE_OMP_PARALLEL:
2059           t = unshare_expr (gimple_omp_parallel_clauses (stmt));
2060           gimple_omp_parallel_set_clauses (copy, t);
2061           t = unshare_expr (gimple_omp_parallel_child_fn (stmt));
2062           gimple_omp_parallel_set_child_fn (copy, t);
2063           t = unshare_expr (gimple_omp_parallel_data_arg (stmt));
2064           gimple_omp_parallel_set_data_arg (copy, t);
2065           goto copy_omp_body;
2066
2067         case GIMPLE_OMP_TASK:
2068           t = unshare_expr (gimple_omp_task_clauses (stmt));
2069           gimple_omp_task_set_clauses (copy, t);
2070           t = unshare_expr (gimple_omp_task_child_fn (stmt));
2071           gimple_omp_task_set_child_fn (copy, t);
2072           t = unshare_expr (gimple_omp_task_data_arg (stmt));
2073           gimple_omp_task_set_data_arg (copy, t);
2074           t = unshare_expr (gimple_omp_task_copy_fn (stmt));
2075           gimple_omp_task_set_copy_fn (copy, t);
2076           t = unshare_expr (gimple_omp_task_arg_size (stmt));
2077           gimple_omp_task_set_arg_size (copy, t);
2078           t = unshare_expr (gimple_omp_task_arg_align (stmt));
2079           gimple_omp_task_set_arg_align (copy, t);
2080           goto copy_omp_body;
2081
2082         case GIMPLE_OMP_CRITICAL:
2083           t = unshare_expr (gimple_omp_critical_name (stmt));
2084           gimple_omp_critical_set_name (copy, t);
2085           goto copy_omp_body;
2086
2087         case GIMPLE_OMP_SECTIONS:
2088           t = unshare_expr (gimple_omp_sections_clauses (stmt));
2089           gimple_omp_sections_set_clauses (copy, t);
2090           t = unshare_expr (gimple_omp_sections_control (stmt));
2091           gimple_omp_sections_set_control (copy, t);
2092           /* FALLTHRU  */
2093
2094         case GIMPLE_OMP_SINGLE:
2095         case GIMPLE_OMP_SECTION:
2096         case GIMPLE_OMP_MASTER:
2097         case GIMPLE_OMP_ORDERED:
2098         copy_omp_body:
2099           new_seq = gimple_seq_copy (gimple_omp_body (stmt));
2100           gimple_omp_set_body (copy, new_seq);
2101           break;
2102
2103         case GIMPLE_WITH_CLEANUP_EXPR:
2104           new_seq = gimple_seq_copy (gimple_wce_cleanup (stmt));
2105           gimple_wce_set_cleanup (copy, new_seq);
2106           break;
2107
2108         default:
2109           gcc_unreachable ();
2110         }
2111     }
2112
2113   /* Make copy of operands.  */
2114   if (num_ops > 0)
2115     {
2116       for (i = 0; i < num_ops; i++)
2117         gimple_set_op (copy, i, unshare_expr (gimple_op (stmt, i)));
2118
2119       /* Clear out SSA operand vectors on COPY.  */
2120       if (gimple_has_ops (stmt))
2121         {
2122           gimple_set_def_ops (copy, NULL);
2123           gimple_set_use_ops (copy, NULL);
2124         }
2125
2126       if (gimple_has_mem_ops (stmt))
2127         {
2128           gimple_set_vdef (copy, gimple_vdef (stmt));
2129           gimple_set_vuse (copy, gimple_vuse (stmt));
2130         }
2131
2132       /* SSA operands need to be updated.  */
2133       gimple_set_modified (copy, true);
2134     }
2135
2136   return copy;
2137 }
2138
2139
2140 /* Set the MODIFIED flag to MODIFIEDP, iff the gimple statement G has
2141    a MODIFIED field.  */
2142
2143 void
2144 gimple_set_modified (gimple s, bool modifiedp)
2145 {
2146   if (gimple_has_ops (s))
2147     {
2148       s->gsbase.modified = (unsigned) modifiedp;
2149
2150       if (modifiedp
2151           && cfun->gimple_df
2152           && is_gimple_call (s)
2153           && gimple_call_noreturn_p (s))
2154         VEC_safe_push (gimple, gc, MODIFIED_NORETURN_CALLS (cfun), s);
2155     }
2156 }
2157
2158
2159 /* Return true if statement S has side-effects.  We consider a
2160    statement to have side effects if:
2161
2162    - It is a GIMPLE_CALL not marked with ECF_PURE or ECF_CONST.
2163    - Any of its operands are marked TREE_THIS_VOLATILE or TREE_SIDE_EFFECTS.  */
2164
2165 bool
2166 gimple_has_side_effects (const_gimple s)
2167 {
2168   unsigned i;
2169
2170   if (is_gimple_debug (s))
2171     return false;
2172
2173   /* We don't have to scan the arguments to check for
2174      volatile arguments, though, at present, we still
2175      do a scan to check for TREE_SIDE_EFFECTS.  */
2176   if (gimple_has_volatile_ops (s))
2177     return true;
2178
2179   if (is_gimple_call (s))
2180     {
2181       unsigned nargs = gimple_call_num_args (s);
2182
2183       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2184         return true;
2185       else if (gimple_call_flags (s) & ECF_LOOPING_CONST_OR_PURE)
2186         /* An infinite loop is considered a side effect.  */
2187         return true;
2188
2189       if (gimple_call_lhs (s)
2190           && TREE_SIDE_EFFECTS (gimple_call_lhs (s)))
2191         {
2192           gcc_assert (gimple_has_volatile_ops (s));
2193           return true;
2194         }
2195
2196       if (TREE_SIDE_EFFECTS (gimple_call_fn (s)))
2197         return true;
2198
2199       for (i = 0; i < nargs; i++)
2200         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i)))
2201           {
2202             gcc_assert (gimple_has_volatile_ops (s));
2203             return true;
2204           }
2205
2206       return false;
2207     }
2208   else
2209     {
2210       for (i = 0; i < gimple_num_ops (s); i++)
2211         if (TREE_SIDE_EFFECTS (gimple_op (s, i)))
2212           {
2213             gcc_assert (gimple_has_volatile_ops (s));
2214             return true;
2215           }
2216     }
2217
2218   return false;
2219 }
2220
2221 /* Return true if the RHS of statement S has side effects.
2222    We may use it to determine if it is admissable to replace
2223    an assignment or call with a copy of a previously-computed
2224    value.  In such cases, side-effects due the the LHS are
2225    preserved.  */
2226
2227 bool
2228 gimple_rhs_has_side_effects (const_gimple s)
2229 {
2230   unsigned i;
2231
2232   if (is_gimple_call (s))
2233     {
2234       unsigned nargs = gimple_call_num_args (s);
2235
2236       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2237         return true;
2238
2239       /* We cannot use gimple_has_volatile_ops here,
2240          because we must ignore a volatile LHS.  */
2241       if (TREE_SIDE_EFFECTS (gimple_call_fn (s))
2242           || TREE_THIS_VOLATILE (gimple_call_fn (s)))
2243         {
2244           gcc_assert (gimple_has_volatile_ops (s));
2245           return true;
2246         }
2247
2248       for (i = 0; i < nargs; i++)
2249         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i))
2250             || TREE_THIS_VOLATILE (gimple_call_arg (s, i)))
2251           return true;
2252
2253       return false;
2254     }
2255   else if (is_gimple_assign (s))
2256     {
2257       /* Skip the first operand, the LHS. */
2258       for (i = 1; i < gimple_num_ops (s); i++)
2259         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2260             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2261           {
2262             gcc_assert (gimple_has_volatile_ops (s));
2263             return true;
2264           }
2265     }
2266   else if (is_gimple_debug (s))
2267     return false;
2268   else
2269     {
2270       /* For statements without an LHS, examine all arguments.  */
2271       for (i = 0; i < gimple_num_ops (s); i++)
2272         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2273             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2274           {
2275             gcc_assert (gimple_has_volatile_ops (s));
2276             return true;
2277           }
2278     }
2279
2280   return false;
2281 }
2282
2283
2284 /* Helper for gimple_could_trap_p and gimple_assign_rhs_could_trap_p.
2285    Return true if S can trap.  If INCLUDE_LHS is true and S is a
2286    GIMPLE_ASSIGN, the LHS of the assignment is also checked.
2287    Otherwise, only the RHS of the assignment is checked.  */
2288
2289 static bool
2290 gimple_could_trap_p_1 (gimple s, bool include_lhs)
2291 {
2292   unsigned i, start;
2293   tree t, div = NULL_TREE;
2294   enum tree_code op;
2295
2296   start = (is_gimple_assign (s) && !include_lhs) ? 1 : 0;
2297
2298   for (i = start; i < gimple_num_ops (s); i++)
2299     if (tree_could_trap_p (gimple_op (s, i)))
2300       return true;
2301
2302   switch (gimple_code (s))
2303     {
2304     case GIMPLE_ASM:
2305       return gimple_asm_volatile_p (s);
2306
2307     case GIMPLE_CALL:
2308       t = gimple_call_fndecl (s);
2309       /* Assume that calls to weak functions may trap.  */
2310       if (!t || !DECL_P (t) || DECL_WEAK (t))
2311         return true;
2312       return false;
2313
2314     case GIMPLE_ASSIGN:
2315       t = gimple_expr_type (s);
2316       op = gimple_assign_rhs_code (s);
2317       if (get_gimple_rhs_class (op) == GIMPLE_BINARY_RHS)
2318         div = gimple_assign_rhs2 (s);
2319       return (operation_could_trap_p (op, FLOAT_TYPE_P (t),
2320                                       (INTEGRAL_TYPE_P (t)
2321                                        && TYPE_OVERFLOW_TRAPS (t)),
2322                                       div));
2323
2324     default:
2325       break;
2326     }
2327
2328   return false;
2329
2330 }
2331
2332
2333 /* Return true if statement S can trap.  */
2334
2335 bool
2336 gimple_could_trap_p (gimple s)
2337 {
2338   return gimple_could_trap_p_1 (s, true);
2339 }
2340
2341
2342 /* Return true if RHS of a GIMPLE_ASSIGN S can trap.  */
2343
2344 bool
2345 gimple_assign_rhs_could_trap_p (gimple s)
2346 {
2347   gcc_assert (is_gimple_assign (s));
2348   return gimple_could_trap_p_1 (s, false);
2349 }
2350
2351
2352 /* Print debugging information for gimple stmts generated.  */
2353
2354 void
2355 dump_gimple_statistics (void)
2356 {
2357 #ifdef GATHER_STATISTICS
2358   int i, total_tuples = 0, total_bytes = 0;
2359
2360   fprintf (stderr, "\nGIMPLE statements\n");
2361   fprintf (stderr, "Kind                   Stmts      Bytes\n");
2362   fprintf (stderr, "---------------------------------------\n");
2363   for (i = 0; i < (int) gimple_alloc_kind_all; ++i)
2364     {
2365       fprintf (stderr, "%-20s %7d %10d\n", gimple_alloc_kind_names[i],
2366           gimple_alloc_counts[i], gimple_alloc_sizes[i]);
2367       total_tuples += gimple_alloc_counts[i];
2368       total_bytes += gimple_alloc_sizes[i];
2369     }
2370   fprintf (stderr, "---------------------------------------\n");
2371   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_tuples, total_bytes);
2372   fprintf (stderr, "---------------------------------------\n");
2373 #else
2374   fprintf (stderr, "No gimple statistics\n");
2375 #endif
2376 }
2377
2378
2379 /* Return the number of operands needed on the RHS of a GIMPLE
2380    assignment for an expression with tree code CODE.  */
2381
2382 unsigned
2383 get_gimple_rhs_num_ops (enum tree_code code)
2384 {
2385   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
2386
2387   if (rhs_class == GIMPLE_UNARY_RHS || rhs_class == GIMPLE_SINGLE_RHS)
2388     return 1;
2389   else if (rhs_class == GIMPLE_BINARY_RHS)
2390     return 2;
2391   else
2392     gcc_unreachable ();
2393 }
2394
2395 #define DEFTREECODE(SYM, STRING, TYPE, NARGS)                               \
2396   (unsigned char)                                                           \
2397   ((TYPE) == tcc_unary ? GIMPLE_UNARY_RHS                                   \
2398    : ((TYPE) == tcc_binary                                                  \
2399       || (TYPE) == tcc_comparison) ? GIMPLE_BINARY_RHS                      \
2400    : ((TYPE) == tcc_constant                                                \
2401       || (TYPE) == tcc_declaration                                          \
2402       || (TYPE) == tcc_reference) ? GIMPLE_SINGLE_RHS                       \
2403    : ((SYM) == TRUTH_AND_EXPR                                               \
2404       || (SYM) == TRUTH_OR_EXPR                                             \
2405       || (SYM) == TRUTH_XOR_EXPR) ? GIMPLE_BINARY_RHS                       \
2406    : (SYM) == TRUTH_NOT_EXPR ? GIMPLE_UNARY_RHS                             \
2407    : ((SYM) == COND_EXPR                                                    \
2408       || (SYM) == CONSTRUCTOR                                               \
2409       || (SYM) == OBJ_TYPE_REF                                              \
2410       || (SYM) == ASSERT_EXPR                                               \
2411       || (SYM) == ADDR_EXPR                                                 \
2412       || (SYM) == WITH_SIZE_EXPR                                            \
2413       || (SYM) == SSA_NAME                                                  \
2414       || (SYM) == POLYNOMIAL_CHREC                                          \
2415       || (SYM) == DOT_PROD_EXPR                                             \
2416       || (SYM) == VEC_COND_EXPR                                             \
2417       || (SYM) == REALIGN_LOAD_EXPR) ? GIMPLE_SINGLE_RHS                    \
2418    : GIMPLE_INVALID_RHS),
2419 #define END_OF_BASE_TREE_CODES (unsigned char) GIMPLE_INVALID_RHS,
2420
2421 const unsigned char gimple_rhs_class_table[] = {
2422 #include "all-tree.def"
2423 };
2424
2425 #undef DEFTREECODE
2426 #undef END_OF_BASE_TREE_CODES
2427
2428 /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi.  */
2429
2430 /* Validation of GIMPLE expressions.  */
2431
2432 /* Return true if OP is an acceptable tree node to be used as a GIMPLE
2433    operand.  */
2434
2435 bool
2436 is_gimple_operand (const_tree op)
2437 {
2438   return op && get_gimple_rhs_class (TREE_CODE (op)) == GIMPLE_SINGLE_RHS;
2439 }
2440
2441 /* Returns true iff T is a valid RHS for an assignment to a renamed
2442    user -- or front-end generated artificial -- variable.  */
2443
2444 bool
2445 is_gimple_reg_rhs (tree t)
2446 {
2447   return get_gimple_rhs_class (TREE_CODE (t)) != GIMPLE_INVALID_RHS;
2448 }
2449
2450 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
2451    LHS, or for a call argument.  */
2452
2453 bool
2454 is_gimple_mem_rhs (tree t)
2455 {
2456   /* If we're dealing with a renamable type, either source or dest must be
2457      a renamed variable.  */
2458   if (is_gimple_reg_type (TREE_TYPE (t)))
2459     return is_gimple_val (t);
2460   else
2461     return is_gimple_val (t) || is_gimple_lvalue (t);
2462 }
2463
2464 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
2465
2466 bool
2467 is_gimple_lvalue (tree t)
2468 {
2469   return (is_gimple_addressable (t)
2470           || TREE_CODE (t) == WITH_SIZE_EXPR
2471           /* These are complex lvalues, but don't have addresses, so they
2472              go here.  */
2473           || TREE_CODE (t) == BIT_FIELD_REF);
2474 }
2475
2476 /*  Return true if T is a GIMPLE condition.  */
2477
2478 bool
2479 is_gimple_condexpr (tree t)
2480 {
2481   return (is_gimple_val (t) || (COMPARISON_CLASS_P (t)
2482                                 && !tree_could_trap_p (t)
2483                                 && is_gimple_val (TREE_OPERAND (t, 0))
2484                                 && is_gimple_val (TREE_OPERAND (t, 1))));
2485 }
2486
2487 /*  Return true if T is something whose address can be taken.  */
2488
2489 bool
2490 is_gimple_addressable (tree t)
2491 {
2492   return (is_gimple_id (t) || handled_component_p (t) || INDIRECT_REF_P (t));
2493 }
2494
2495 /* Return true if T is a valid gimple constant.  */
2496
2497 bool
2498 is_gimple_constant (const_tree t)
2499 {
2500   switch (TREE_CODE (t))
2501     {
2502     case INTEGER_CST:
2503     case REAL_CST:
2504     case FIXED_CST:
2505     case STRING_CST:
2506     case COMPLEX_CST:
2507     case VECTOR_CST:
2508       return true;
2509
2510     /* Vector constant constructors are gimple invariant.  */
2511     case CONSTRUCTOR:
2512       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2513         return TREE_CONSTANT (t);
2514       else
2515         return false;
2516
2517     default:
2518       return false;
2519     }
2520 }
2521
2522 /* Return true if T is a gimple address.  */
2523
2524 bool
2525 is_gimple_address (const_tree t)
2526 {
2527   tree op;
2528
2529   if (TREE_CODE (t) != ADDR_EXPR)
2530     return false;
2531
2532   op = TREE_OPERAND (t, 0);
2533   while (handled_component_p (op))
2534     {
2535       if ((TREE_CODE (op) == ARRAY_REF
2536            || TREE_CODE (op) == ARRAY_RANGE_REF)
2537           && !is_gimple_val (TREE_OPERAND (op, 1)))
2538             return false;
2539
2540       op = TREE_OPERAND (op, 0);
2541     }
2542
2543   if (CONSTANT_CLASS_P (op) || INDIRECT_REF_P (op))
2544     return true;
2545
2546   switch (TREE_CODE (op))
2547     {
2548     case PARM_DECL:
2549     case RESULT_DECL:
2550     case LABEL_DECL:
2551     case FUNCTION_DECL:
2552     case VAR_DECL:
2553     case CONST_DECL:
2554       return true;
2555
2556     default:
2557       return false;
2558     }
2559 }
2560
2561 /* Strip out all handled components that produce invariant
2562    offsets.  */
2563
2564 static const_tree
2565 strip_invariant_refs (const_tree op)
2566 {
2567   while (handled_component_p (op))
2568     {
2569       switch (TREE_CODE (op))
2570         {
2571         case ARRAY_REF:
2572         case ARRAY_RANGE_REF:
2573           if (!is_gimple_constant (TREE_OPERAND (op, 1))
2574               || TREE_OPERAND (op, 2) != NULL_TREE
2575               || TREE_OPERAND (op, 3) != NULL_TREE)
2576             return NULL;
2577           break;
2578
2579         case COMPONENT_REF:
2580           if (TREE_OPERAND (op, 2) != NULL_TREE)
2581             return NULL;
2582           break;
2583
2584         default:;
2585         }
2586       op = TREE_OPERAND (op, 0);
2587     }
2588
2589   return op;
2590 }
2591
2592 /* Return true if T is a gimple invariant address.  */
2593
2594 bool
2595 is_gimple_invariant_address (const_tree t)
2596 {
2597   const_tree op;
2598
2599   if (TREE_CODE (t) != ADDR_EXPR)
2600     return false;
2601
2602   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2603
2604   return op && (CONSTANT_CLASS_P (op) || decl_address_invariant_p (op));
2605 }
2606
2607 /* Return true if T is a gimple invariant address at IPA level
2608    (so addresses of variables on stack are not allowed).  */
2609
2610 bool
2611 is_gimple_ip_invariant_address (const_tree t)
2612 {
2613   const_tree op;
2614
2615   if (TREE_CODE (t) != ADDR_EXPR)
2616     return false;
2617
2618   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2619
2620   return op && (CONSTANT_CLASS_P (op) || decl_address_ip_invariant_p (op));
2621 }
2622
2623 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
2624    form of function invariant.  */
2625
2626 bool
2627 is_gimple_min_invariant (const_tree t)
2628 {
2629   if (TREE_CODE (t) == ADDR_EXPR)
2630     return is_gimple_invariant_address (t);
2631
2632   return is_gimple_constant (t);
2633 }
2634
2635 /* Return true if T is a GIMPLE interprocedural invariant.  It's a restricted
2636    form of gimple minimal invariant.  */
2637
2638 bool
2639 is_gimple_ip_invariant (const_tree t)
2640 {
2641   if (TREE_CODE (t) == ADDR_EXPR)
2642     return is_gimple_ip_invariant_address (t);
2643
2644   return is_gimple_constant (t);
2645 }
2646
2647 /* Return true if T looks like a valid GIMPLE statement.  */
2648
2649 bool
2650 is_gimple_stmt (tree t)
2651 {
2652   const enum tree_code code = TREE_CODE (t);
2653
2654   switch (code)
2655     {
2656     case NOP_EXPR:
2657       /* The only valid NOP_EXPR is the empty statement.  */
2658       return IS_EMPTY_STMT (t);
2659
2660     case BIND_EXPR:
2661     case COND_EXPR:
2662       /* These are only valid if they're void.  */
2663       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
2664
2665     case SWITCH_EXPR:
2666     case GOTO_EXPR:
2667     case RETURN_EXPR:
2668     case LABEL_EXPR:
2669     case CASE_LABEL_EXPR:
2670     case TRY_CATCH_EXPR:
2671     case TRY_FINALLY_EXPR:
2672     case EH_FILTER_EXPR:
2673     case CATCH_EXPR:
2674     case ASM_EXPR:
2675     case STATEMENT_LIST:
2676     case OMP_PARALLEL:
2677     case OMP_FOR:
2678     case OMP_SECTIONS:
2679     case OMP_SECTION:
2680     case OMP_SINGLE:
2681     case OMP_MASTER:
2682     case OMP_ORDERED:
2683     case OMP_CRITICAL:
2684     case OMP_TASK:
2685       /* These are always void.  */
2686       return true;
2687
2688     case CALL_EXPR:
2689     case MODIFY_EXPR:
2690     case PREDICT_EXPR:
2691       /* These are valid regardless of their type.  */
2692       return true;
2693
2694     default:
2695       return false;
2696     }
2697 }
2698
2699 /* Return true if T is a variable.  */
2700
2701 bool
2702 is_gimple_variable (tree t)
2703 {
2704   return (TREE_CODE (t) == VAR_DECL
2705           || TREE_CODE (t) == PARM_DECL
2706           || TREE_CODE (t) == RESULT_DECL
2707           || TREE_CODE (t) == SSA_NAME);
2708 }
2709
2710 /*  Return true if T is a GIMPLE identifier (something with an address).  */
2711
2712 bool
2713 is_gimple_id (tree t)
2714 {
2715   return (is_gimple_variable (t)
2716           || TREE_CODE (t) == FUNCTION_DECL
2717           || TREE_CODE (t) == LABEL_DECL
2718           || TREE_CODE (t) == CONST_DECL
2719           /* Allow string constants, since they are addressable.  */
2720           || TREE_CODE (t) == STRING_CST);
2721 }
2722
2723 /* Return true if TYPE is a suitable type for a scalar register variable.  */
2724
2725 bool
2726 is_gimple_reg_type (tree type)
2727 {
2728   return !AGGREGATE_TYPE_P (type);
2729 }
2730
2731 /* Return true if T is a non-aggregate register variable.  */
2732
2733 bool
2734 is_gimple_reg (tree t)
2735 {
2736   if (TREE_CODE (t) == SSA_NAME)
2737     t = SSA_NAME_VAR (t);
2738
2739   if (!is_gimple_variable (t))
2740     return false;
2741
2742   if (!is_gimple_reg_type (TREE_TYPE (t)))
2743     return false;
2744
2745   /* A volatile decl is not acceptable because we can't reuse it as
2746      needed.  We need to copy it into a temp first.  */
2747   if (TREE_THIS_VOLATILE (t))
2748     return false;
2749
2750   /* We define "registers" as things that can be renamed as needed,
2751      which with our infrastructure does not apply to memory.  */
2752   if (needs_to_live_in_memory (t))
2753     return false;
2754
2755   /* Hard register variables are an interesting case.  For those that
2756      are call-clobbered, we don't know where all the calls are, since
2757      we don't (want to) take into account which operations will turn
2758      into libcalls at the rtl level.  For those that are call-saved,
2759      we don't currently model the fact that calls may in fact change
2760      global hard registers, nor do we examine ASM_CLOBBERS at the tree
2761      level, and so miss variable changes that might imply.  All around,
2762      it seems safest to not do too much optimization with these at the
2763      tree level at all.  We'll have to rely on the rtl optimizers to
2764      clean this up, as there we've got all the appropriate bits exposed.  */
2765   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
2766     return false;
2767
2768   /* Complex and vector values must have been put into SSA-like form.
2769      That is, no assignments to the individual components.  */
2770   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
2771       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2772     return DECL_GIMPLE_REG_P (t);
2773
2774   return true;
2775 }
2776
2777
2778 /* Return true if T is a GIMPLE variable whose address is not needed.  */
2779
2780 bool
2781 is_gimple_non_addressable (tree t)
2782 {
2783   if (TREE_CODE (t) == SSA_NAME)
2784     t = SSA_NAME_VAR (t);
2785
2786   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
2787 }
2788
2789 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
2790
2791 bool
2792 is_gimple_val (tree t)
2793 {
2794   /* Make loads from volatiles and memory vars explicit.  */
2795   if (is_gimple_variable (t)
2796       && is_gimple_reg_type (TREE_TYPE (t))
2797       && !is_gimple_reg (t))
2798     return false;
2799
2800   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
2801 }
2802
2803 /* Similarly, but accept hard registers as inputs to asm statements.  */
2804
2805 bool
2806 is_gimple_asm_val (tree t)
2807 {
2808   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
2809     return true;
2810
2811   return is_gimple_val (t);
2812 }
2813
2814 /* Return true if T is a GIMPLE minimal lvalue.  */
2815
2816 bool
2817 is_gimple_min_lval (tree t)
2818 {
2819   if (!(t = CONST_CAST_TREE (strip_invariant_refs (t))))
2820     return false;
2821   return (is_gimple_id (t) || TREE_CODE (t) == INDIRECT_REF);
2822 }
2823
2824 /* Return true if T is a typecast operation.  */
2825
2826 bool
2827 is_gimple_cast (tree t)
2828 {
2829   return (CONVERT_EXPR_P (t)
2830           || TREE_CODE (t) == FIX_TRUNC_EXPR);
2831 }
2832
2833 /* Return true if T is a valid function operand of a CALL_EXPR.  */
2834
2835 bool
2836 is_gimple_call_addr (tree t)
2837 {
2838   return (TREE_CODE (t) == OBJ_TYPE_REF || is_gimple_val (t));
2839 }
2840
2841 /* If T makes a function call, return the corresponding CALL_EXPR operand.
2842    Otherwise, return NULL_TREE.  */
2843
2844 tree
2845 get_call_expr_in (tree t)
2846 {
2847   if (TREE_CODE (t) == MODIFY_EXPR)
2848     t = TREE_OPERAND (t, 1);
2849   if (TREE_CODE (t) == WITH_SIZE_EXPR)
2850     t = TREE_OPERAND (t, 0);
2851   if (TREE_CODE (t) == CALL_EXPR)
2852     return t;
2853   return NULL_TREE;
2854 }
2855
2856
2857 /* Given a memory reference expression T, return its base address.
2858    The base address of a memory reference expression is the main
2859    object being referenced.  For instance, the base address for
2860    'array[i].fld[j]' is 'array'.  You can think of this as stripping
2861    away the offset part from a memory address.
2862
2863    This function calls handled_component_p to strip away all the inner
2864    parts of the memory reference until it reaches the base object.  */
2865
2866 tree
2867 get_base_address (tree t)
2868 {
2869   while (handled_component_p (t))
2870     t = TREE_OPERAND (t, 0);
2871   
2872   if (SSA_VAR_P (t)
2873       || TREE_CODE (t) == STRING_CST
2874       || TREE_CODE (t) == CONSTRUCTOR
2875       || INDIRECT_REF_P (t))
2876     return t;
2877   else
2878     return NULL_TREE;
2879 }
2880
2881 void
2882 recalculate_side_effects (tree t)
2883 {
2884   enum tree_code code = TREE_CODE (t);
2885   int len = TREE_OPERAND_LENGTH (t);
2886   int i;
2887
2888   switch (TREE_CODE_CLASS (code))
2889     {
2890     case tcc_expression:
2891       switch (code)
2892         {
2893         case INIT_EXPR:
2894         case MODIFY_EXPR:
2895         case VA_ARG_EXPR:
2896         case PREDECREMENT_EXPR:
2897         case PREINCREMENT_EXPR:
2898         case POSTDECREMENT_EXPR:
2899         case POSTINCREMENT_EXPR:
2900           /* All of these have side-effects, no matter what their
2901              operands are.  */
2902           return;
2903
2904         default:
2905           break;
2906         }
2907       /* Fall through.  */
2908
2909     case tcc_comparison:  /* a comparison expression */
2910     case tcc_unary:       /* a unary arithmetic expression */
2911     case tcc_binary:      /* a binary arithmetic expression */
2912     case tcc_reference:   /* a reference */
2913     case tcc_vl_exp:        /* a function call */
2914       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
2915       for (i = 0; i < len; ++i)
2916         {
2917           tree op = TREE_OPERAND (t, i);
2918           if (op && TREE_SIDE_EFFECTS (op))
2919             TREE_SIDE_EFFECTS (t) = 1;
2920         }
2921       break;
2922
2923     case tcc_constant:
2924       /* No side-effects.  */
2925       return;
2926
2927     default:
2928       gcc_unreachable ();
2929    }
2930 }
2931
2932 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
2933    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
2934    we failed to create one.  */
2935
2936 tree
2937 canonicalize_cond_expr_cond (tree t)
2938 {
2939   /* For (bool)x use x != 0.  */
2940   if (TREE_CODE (t) == NOP_EXPR
2941       && TREE_TYPE (t) == boolean_type_node)
2942     {
2943       tree top0 = TREE_OPERAND (t, 0);
2944       t = build2 (NE_EXPR, TREE_TYPE (t),
2945                   top0, build_int_cst (TREE_TYPE (top0), 0));
2946     }
2947   /* For !x use x == 0.  */
2948   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
2949     {
2950       tree top0 = TREE_OPERAND (t, 0);
2951       t = build2 (EQ_EXPR, TREE_TYPE (t),
2952                   top0, build_int_cst (TREE_TYPE (top0), 0));
2953     }
2954   /* For cmp ? 1 : 0 use cmp.  */
2955   else if (TREE_CODE (t) == COND_EXPR
2956            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
2957            && integer_onep (TREE_OPERAND (t, 1))
2958            && integer_zerop (TREE_OPERAND (t, 2)))
2959     {
2960       tree top0 = TREE_OPERAND (t, 0);
2961       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
2962                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
2963     }
2964
2965   if (is_gimple_condexpr (t))
2966     return t;
2967
2968   return NULL_TREE;
2969 }
2970
2971 /* Build a GIMPLE_CALL identical to STMT but skipping the arguments in
2972    the positions marked by the set ARGS_TO_SKIP.  */
2973
2974 gimple
2975 gimple_call_copy_skip_args (gimple stmt, bitmap args_to_skip)
2976 {
2977   int i;
2978   tree fn = gimple_call_fn (stmt);
2979   int nargs = gimple_call_num_args (stmt);
2980   VEC(tree, heap) *vargs = VEC_alloc (tree, heap, nargs);
2981   gimple new_stmt;
2982
2983   for (i = 0; i < nargs; i++)
2984     if (!bitmap_bit_p (args_to_skip, i))
2985       VEC_quick_push (tree, vargs, gimple_call_arg (stmt, i));
2986
2987   new_stmt = gimple_build_call_vec (fn, vargs);
2988   VEC_free (tree, heap, vargs);
2989   if (gimple_call_lhs (stmt))
2990     gimple_call_set_lhs (new_stmt, gimple_call_lhs (stmt));
2991
2992   gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2993   gimple_set_vdef (new_stmt, gimple_vdef (stmt));
2994
2995   gimple_set_block (new_stmt, gimple_block (stmt));
2996   if (gimple_has_location (stmt))
2997     gimple_set_location (new_stmt, gimple_location (stmt));
2998
2999   /* Carry all the flags to the new GIMPLE_CALL.  */
3000   gimple_call_set_chain (new_stmt, gimple_call_chain (stmt));
3001   gimple_call_set_tail (new_stmt, gimple_call_tail_p (stmt));
3002   gimple_call_set_cannot_inline (new_stmt, gimple_call_cannot_inline_p (stmt));
3003   gimple_call_set_return_slot_opt (new_stmt, gimple_call_return_slot_opt_p (stmt));
3004   gimple_call_set_from_thunk (new_stmt, gimple_call_from_thunk_p (stmt));
3005   gimple_call_set_va_arg_pack (new_stmt, gimple_call_va_arg_pack_p (stmt));
3006
3007   gimple_set_modified (new_stmt, true);
3008
3009   return new_stmt;
3010 }
3011
3012
3013 static hashval_t gimple_type_hash (const void *);
3014
3015 /* Structure used to maintain a cache of some type pairs compared by
3016    gimple_types_compatible_p when comparing aggregate types.  There are
3017    four possible values for SAME_P:
3018
3019         -2: The pair (T1, T2) has just been inserted in the table.
3020         -1: The pair (T1, T2) is currently being compared.
3021          0: T1 and T2 are different types.
3022          1: T1 and T2 are the same type.
3023
3024    This table is only used when comparing aggregate types to avoid
3025    infinite recursion due to self-referential types.  */
3026 struct type_pair_d
3027 {
3028   tree t1;
3029   tree t2;
3030   int same_p;
3031 };
3032 typedef struct type_pair_d *type_pair_t;
3033
3034 /* Return a hash value for the type pair pointed-to by P.  */
3035
3036 static hashval_t
3037 type_pair_hash (const void *p)
3038 {
3039   const struct type_pair_d *pair = (const struct type_pair_d *) p;
3040   hashval_t val1 = iterative_hash_hashval_t (htab_hash_pointer (pair->t1), 0);
3041   hashval_t val2 = iterative_hash_hashval_t (htab_hash_pointer (pair->t2), 0);
3042   return (iterative_hash_hashval_t (val2, val1)
3043           ^ iterative_hash_hashval_t (val1, val2));
3044 }
3045
3046 /* Compare two type pairs pointed-to by P1 and P2.  */
3047
3048 static int
3049 type_pair_eq (const void *p1, const void *p2)
3050 {
3051   const struct type_pair_d *pair1 = (const struct type_pair_d *) p1;
3052   const struct type_pair_d *pair2 = (const struct type_pair_d *) p2;
3053   return ((pair1->t1 == pair2->t1 && pair1->t2 == pair2->t2)
3054           || (pair1->t1 == pair2->t2 && pair1->t2 == pair2->t1));
3055 }
3056
3057 /* Lookup the pair of types T1 and T2 in *VISITED_P.  Insert a new
3058    entry if none existed.  */
3059
3060 static type_pair_t
3061 lookup_type_pair (tree t1, tree t2, htab_t *visited_p)
3062 {
3063   struct type_pair_d pair;
3064   type_pair_t p;
3065   void **slot;
3066
3067   if (*visited_p == NULL)
3068     *visited_p = htab_create (251, type_pair_hash, type_pair_eq, free);
3069
3070   pair.t1 = t1;
3071   pair.t2 = t2;
3072   slot = htab_find_slot (*visited_p, &pair, INSERT);
3073
3074   if (*slot)
3075     p = *((type_pair_t *) slot);
3076   else
3077     {
3078       p = XNEW (struct type_pair_d);
3079       p->t1 = t1;
3080       p->t2 = t2;
3081       p->same_p = -2;
3082       *slot = (void *) p;
3083     }
3084
3085   return p;
3086 }
3087
3088
3089 /* Force merging the type T2 into the type T1.  */
3090
3091 void
3092 gimple_force_type_merge (tree t1, tree t2)
3093 {
3094   void **slot;
3095   type_pair_t p;
3096
3097   /* There's no other way than copying t2 to t1 in this case.
3098      Yuck.  We'll just call this "completing" t1.  */
3099   memcpy (t1, t2, tree_size (t1));
3100
3101   /* Adjust the hash value of T1 if it was computed already.  Otherwise
3102      we would be forced to not hash fields of structs to match the
3103      hash value of an incomplete struct.  */
3104   if (type_hash_cache
3105       && (slot = pointer_map_contains (type_hash_cache, t1)) != NULL)
3106     {
3107       gimple_type_hash (t2);
3108       *slot = *pointer_map_contains (type_hash_cache, t2);
3109     }
3110
3111   /* Adjust cached comparison results for T1 and T2 to make sure
3112      they now compare compatible.  */
3113   p = lookup_type_pair (t1, t2, &gtc_visited);
3114   p->same_p = 1;
3115 }
3116
3117
3118 /* Return true if both types have the same name.  */
3119
3120 static bool
3121 compare_type_names_p (tree t1, tree t2)
3122 {
3123   tree name1 = TYPE_NAME (t1);
3124   tree name2 = TYPE_NAME (t2);
3125
3126   /* Consider anonymous types all unique.  */
3127   if (!name1 || !name2)
3128     return false;
3129
3130   if (TREE_CODE (name1) == TYPE_DECL)
3131     {
3132       name1 = DECL_NAME (name1);
3133       if (!name1)
3134         return false;
3135     }
3136   gcc_assert (TREE_CODE (name1) == IDENTIFIER_NODE);
3137
3138   if (TREE_CODE (name2) == TYPE_DECL)
3139     {
3140       name2 = DECL_NAME (name2);
3141       if (!name2)
3142         return false;
3143     }
3144   gcc_assert (TREE_CODE (name2) == IDENTIFIER_NODE);
3145
3146   /* Identifiers can be compared with pointer equality rather
3147      than a string comparison.  */
3148   if (name1 == name2)
3149     return true;
3150
3151   return false;
3152 }
3153
3154 /* Return true if the field decls F1 and F2 are at the same offset.  */
3155
3156 static bool
3157 compare_field_offset (tree f1, tree f2)
3158 {
3159   if (DECL_OFFSET_ALIGN (f1) == DECL_OFFSET_ALIGN (f2))
3160     return (operand_equal_p (DECL_FIELD_OFFSET (f1),
3161                              DECL_FIELD_OFFSET (f2), 0)
3162             && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (f1),
3163                                    DECL_FIELD_BIT_OFFSET (f2)));
3164
3165   /* Fortran and C do not always agree on what DECL_OFFSET_ALIGN
3166      should be, so handle differing ones specially by decomposing
3167      the offset into a byte and bit offset manually.  */
3168   if (host_integerp (DECL_FIELD_OFFSET (f1), 0)
3169       && host_integerp (DECL_FIELD_OFFSET (f2), 0))
3170     {
3171       unsigned HOST_WIDE_INT byte_offset1, byte_offset2;
3172       unsigned HOST_WIDE_INT bit_offset1, bit_offset2;
3173       bit_offset1 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f1));
3174       byte_offset1 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f1))
3175                       + bit_offset1 / BITS_PER_UNIT);
3176       bit_offset2 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f2));
3177       byte_offset2 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f2))
3178                       + bit_offset2 / BITS_PER_UNIT);
3179       if (byte_offset1 != byte_offset2)
3180         return false;
3181       return bit_offset1 % BITS_PER_UNIT == bit_offset2 % BITS_PER_UNIT;
3182     }
3183
3184   return false;
3185 }
3186
3187 /* Return 1 iff T1 and T2 are structurally identical.
3188    Otherwise, return 0.  */
3189
3190 int
3191 gimple_types_compatible_p (tree t1, tree t2)
3192 {
3193   type_pair_t p = NULL;
3194
3195   /* Check first for the obvious case of pointer identity.  */
3196   if (t1 == t2)
3197     goto same_types;
3198
3199   /* Check that we have two types to compare.  */
3200   if (t1 == NULL_TREE || t2 == NULL_TREE)
3201     goto different_types;
3202
3203   /* Can't be the same type if the types don't have the same code.  */
3204   if (TREE_CODE (t1) != TREE_CODE (t2))
3205     goto different_types;
3206
3207   /* Void types are always the same.  */
3208   if (TREE_CODE (t1) == VOID_TYPE)
3209     goto same_types;
3210
3211   /* Can't be the same type if they have different CV qualifiers.  */
3212   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
3213     goto different_types;
3214
3215   /* If the hash values of t1 and t2 are different the types can't
3216      possibly be the same.  This helps keeping the type-pair hashtable
3217      small, only tracking comparisons for hash collisions.  */
3218   if (gimple_type_hash (t1) != gimple_type_hash (t2))
3219     return 0;
3220
3221   /* If we've visited this type pair before (in the case of aggregates
3222      with self-referential types), and we made a decision, return it.  */
3223   p = lookup_type_pair (t1, t2, &gtc_visited);
3224   if (p->same_p == 0 || p->same_p == 1)
3225     {
3226       /* We have already decided whether T1 and T2 are the
3227          same, return the cached result.  */
3228       return p->same_p == 1;
3229     }
3230   else if (p->same_p == -1)
3231     {
3232       /* We are currently comparing this pair of types, assume
3233          that they are the same and let the caller decide.  */
3234       return 1;
3235     }
3236
3237   gcc_assert (p->same_p == -2);
3238
3239   /* Mark the (T1, T2) comparison in progress.  */
3240   p->same_p = -1;
3241
3242   /* If their attributes are not the same they can't be the same type.  */
3243   if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
3244     goto different_types;
3245
3246   /* For numerical types, the bounds must coincide.  */
3247   if (INTEGRAL_TYPE_P (t1)
3248       || SCALAR_FLOAT_TYPE_P (t1)
3249       || FIXED_POINT_TYPE_P (t1))
3250     {
3251       /* Can't be the same type if they have different size, alignment,
3252          sign, precision or mode.  Note that from now on, comparisons
3253          between *_CST nodes must be done using tree_int_cst_equal because
3254          we cannot assume that constants from T1 and T2 will be shared
3255          since T1 and T2 are distinct pointers.  */
3256       if (!tree_int_cst_equal (TYPE_SIZE (t1), TYPE_SIZE (t2))
3257           || !tree_int_cst_equal (TYPE_SIZE_UNIT (t1), TYPE_SIZE_UNIT (t2))
3258           || TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3259           || TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
3260           || TYPE_MODE (t1) != TYPE_MODE (t2)
3261           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
3262         goto different_types;
3263
3264       /* For non-enumeral types, check type bounds.  FIXME lto, we
3265          cannot check bounds on enumeral types because different front
3266          ends will produce different values.  In C, enumeral types are
3267          integers, while in C++ each element will have its own
3268          symbolic value.  We should decide how enums are to be
3269          represented in GIMPLE and have each front end lower to that.  */
3270       if (TREE_CODE (t1) != ENUMERAL_TYPE)
3271         {
3272           tree min1 = TYPE_MIN_VALUE (t1);
3273           tree max1 = TYPE_MAX_VALUE (t1);
3274           tree min2 = TYPE_MIN_VALUE (t2);
3275           tree max2 = TYPE_MAX_VALUE (t2);
3276           bool min_equal_p = false;
3277           bool max_equal_p = false;
3278
3279           /* If either type has a minimum value, the other type must
3280              have the same.  */
3281           if (min1 == NULL_TREE && min2 == NULL_TREE)
3282             min_equal_p = true;
3283           else if (min1 && min2 && operand_equal_p (min1, min2, 0))
3284             min_equal_p = true;
3285
3286           /* Likewise, if either type has a maximum value, the other
3287              type must have the same.  */
3288           if (max1 == NULL_TREE && max2 == NULL_TREE)
3289             max_equal_p = true;
3290           else if (max1 && max2 && operand_equal_p (max1, max2, 0))
3291             max_equal_p = true;
3292
3293           if (!min_equal_p || !max_equal_p)
3294             goto different_types;
3295         }
3296
3297       if (TREE_CODE (t1) == INTEGER_TYPE)
3298         {
3299           if (TYPE_IS_SIZETYPE (t1) == TYPE_IS_SIZETYPE (t2)
3300               && TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2))
3301             goto same_types;
3302           else
3303             goto different_types;
3304         }
3305       else if (TREE_CODE (t1) == BOOLEAN_TYPE)
3306         goto same_types;
3307       else if (TREE_CODE (t1) == REAL_TYPE)
3308         goto same_types;
3309     }
3310
3311   /* Do type-specific comparisons.  */
3312   switch (TREE_CODE (t1))
3313     {
3314     case ARRAY_TYPE:
3315       /* Array types are the same if the element types are the same and
3316          the number of elements are the same.  */
3317       if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
3318           || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
3319         goto different_types;
3320       else
3321         {
3322           tree i1 = TYPE_DOMAIN (t1);
3323           tree i2 = TYPE_DOMAIN (t2);
3324
3325           /* For an incomplete external array, the type domain can be
3326              NULL_TREE.  Check this condition also.  */
3327           if (i1 == NULL_TREE && i2 == NULL_TREE)
3328             goto same_types;
3329           else if (i1 == NULL_TREE || i2 == NULL_TREE)
3330             goto different_types;
3331           /* If for a complete array type the possibly gimplified sizes
3332              are different the types are different.  */
3333           else if (((TYPE_SIZE (i1) != NULL) ^ (TYPE_SIZE (i2) != NULL))
3334                    || (TYPE_SIZE (i1)
3335                        && TYPE_SIZE (i2)
3336                        && !operand_equal_p (TYPE_SIZE (i1), TYPE_SIZE (i2), 0)))
3337             goto different_types;
3338           else
3339             {
3340               tree min1 = TYPE_MIN_VALUE (i1);
3341               tree min2 = TYPE_MIN_VALUE (i2);
3342               tree max1 = TYPE_MAX_VALUE (i1);
3343               tree max2 = TYPE_MAX_VALUE (i2);
3344
3345               /* The minimum/maximum values have to be the same.  */
3346               if ((min1 == min2
3347                    || (min1 && min2 && operand_equal_p (min1, min2, 0)))
3348                   && (max1 == max2
3349                       || (max1 && max2 && operand_equal_p (max1, max2, 0))))
3350                 goto same_types;
3351               else
3352                 goto different_types;
3353             }
3354         }
3355
3356     case METHOD_TYPE:
3357       /* Method types should belong to the same class.  */
3358       if (!gimple_types_compatible_p (TYPE_METHOD_BASETYPE (t1),
3359                                  TYPE_METHOD_BASETYPE (t2)))
3360         goto different_types;
3361
3362       /* Fallthru  */
3363
3364     case FUNCTION_TYPE:
3365       /* Function types are the same if the return type and arguments types
3366          are the same.  */
3367       if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3368         goto different_types;
3369       else
3370         {
3371           if (!targetm.comp_type_attributes (t1, t2))
3372             goto different_types;
3373
3374           if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
3375             goto same_types;
3376           else
3377             {
3378               tree parms1, parms2;
3379
3380               for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
3381                    parms1 && parms2;
3382                    parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
3383                 {
3384                   if (!gimple_types_compatible_p (TREE_VALUE (parms1),
3385                                              TREE_VALUE (parms2)))
3386                     goto different_types;
3387                 }
3388
3389               if (parms1 || parms2)
3390                 goto different_types;
3391
3392               goto same_types;
3393             }
3394         }
3395
3396     case POINTER_TYPE:
3397     case REFERENCE_TYPE:
3398         {
3399           /* If the two pointers have different ref-all attributes,
3400              they can't be the same type.  */
3401           if (TYPE_REF_CAN_ALIAS_ALL (t1) != TYPE_REF_CAN_ALIAS_ALL (t2))
3402             goto different_types;
3403
3404           /* If one pointer points to an incomplete type variant of
3405              the other pointed-to type they are the same.  */
3406           if (TREE_CODE (TREE_TYPE (t1)) == TREE_CODE (TREE_TYPE (t2))
3407               && (!COMPLETE_TYPE_P (TREE_TYPE (t1))
3408                   || !COMPLETE_TYPE_P (TREE_TYPE (t2)))
3409               && compare_type_names_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3410             {
3411               /* If t2 is complete we want to choose it instead of t1.  */
3412               if (COMPLETE_TYPE_P (TREE_TYPE (t2)))
3413                 gimple_force_type_merge (TREE_TYPE (t1), TREE_TYPE (t2));
3414               goto same_types;
3415             }
3416
3417           /* Otherwise, pointer and reference types are the same if the
3418              pointed-to types are the same.  */
3419           if (gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3420             goto same_types;
3421           
3422           goto different_types;
3423         }
3424
3425     case ENUMERAL_TYPE:
3426         {
3427           /* For enumeral types, all the values must be the same.  */
3428           tree v1, v2;
3429
3430           if (TYPE_VALUES (t1) == TYPE_VALUES (t2))
3431             goto same_types;
3432
3433           for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
3434                v1 && v2;
3435                v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
3436             {
3437               tree c1 = TREE_VALUE (v1);
3438               tree c2 = TREE_VALUE (v2);
3439
3440               if (TREE_CODE (c1) == CONST_DECL)
3441                 c1 = DECL_INITIAL (c1);
3442
3443               if (TREE_CODE (c2) == CONST_DECL)
3444                 c2 = DECL_INITIAL (c2);
3445
3446               if (tree_int_cst_equal (c1, c2) != 1)
3447                 goto different_types;
3448             }
3449
3450           /* If one enumeration has more values than the other, they
3451              are not the same.  */
3452           if (v1 || v2)
3453             goto different_types;
3454
3455           goto same_types;
3456         }
3457
3458     case RECORD_TYPE:
3459     case UNION_TYPE:
3460     case QUAL_UNION_TYPE:
3461         {
3462           /* For aggregate types, all the fields must be the same.  */
3463           tree f1, f2;
3464
3465           /* Compare every field.  */
3466           for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
3467                f1 && f2;
3468                f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
3469             {
3470               /* The fields must have the same name, offset and type.  */
3471               if (DECL_NAME (f1) != DECL_NAME (f2)
3472                   || !compare_field_offset (f1, f2)
3473                   || !gimple_types_compatible_p (TREE_TYPE (f1),
3474                                             TREE_TYPE (f2)))
3475                 goto different_types;
3476             }
3477
3478           /* If one aggregate has more fields than the other, they
3479              are not the same.  */
3480           if (f1 || f2)
3481             goto different_types;
3482
3483           goto same_types;
3484         }
3485
3486     case VECTOR_TYPE:
3487       if (TYPE_VECTOR_SUBPARTS (t1) != TYPE_VECTOR_SUBPARTS (t2))
3488         goto different_types;
3489
3490       /* Fallthru  */
3491     case COMPLEX_TYPE:
3492       if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3493         goto different_types;
3494       goto same_types;
3495
3496     default:
3497       goto different_types;
3498     }
3499
3500   /* Common exit path for types that are not compatible.  */
3501 different_types:
3502   if (p)
3503     p->same_p = 0;
3504   return 0;
3505
3506   /* Common exit path for types that are compatible.  */
3507 same_types:
3508   if (p)
3509     p->same_p = 1;
3510   return 1;
3511 }
3512
3513
3514
3515
3516 /* Per pointer state for the SCC finding.  The on_sccstack flag
3517    is not strictly required, it is true when there is no hash value
3518    recorded for the type and false otherwise.  But querying that
3519    is slower.  */
3520
3521 struct sccs
3522 {
3523   unsigned int dfsnum;
3524   unsigned int low;
3525   bool on_sccstack;
3526   hashval_t hash;
3527 };
3528
3529 static unsigned int next_dfs_num;
3530
3531 static hashval_t
3532 iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
3533                             struct pointer_map_t *, struct obstack *);
3534
3535 /* DFS visit the edge from the callers type with state *STATE to T.
3536    Update the callers type hash V with the hash for T if it is not part
3537    of the SCC containing the callers type and return it.
3538    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3539
3540 static hashval_t
3541 visit (tree t, struct sccs *state, hashval_t v,
3542        VEC (tree, heap) **sccstack,
3543        struct pointer_map_t *sccstate,
3544        struct obstack *sccstate_obstack)
3545 {
3546   struct sccs *cstate = NULL;
3547   void **slot;
3548
3549   /* If there is a hash value recorded for this type then it can't
3550      possibly be part of our parent SCC.  Simply mix in its hash.  */
3551   if ((slot = pointer_map_contains (type_hash_cache, t)))
3552     return iterative_hash_hashval_t ((hashval_t) (size_t) *slot, v);
3553
3554   if ((slot = pointer_map_contains (sccstate, t)) != NULL)
3555     cstate = (struct sccs *)*slot;
3556   if (!cstate)
3557     {
3558       hashval_t tem;
3559       /* Not yet visited.  DFS recurse.  */
3560       tem = iterative_hash_gimple_type (t, v,
3561                                         sccstack, sccstate, sccstate_obstack);
3562       if (!cstate)
3563         cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
3564       state->low = MIN (state->low, cstate->low);
3565       /* If the type is no longer on the SCC stack and thus is not part
3566          of the parents SCC mix in its hash value.  Otherwise we will
3567          ignore the type for hashing purposes and return the unaltered
3568          hash value.  */
3569       if (!cstate->on_sccstack)
3570         return tem;
3571     }
3572   if (cstate->dfsnum < state->dfsnum
3573       && cstate->on_sccstack)
3574     state->low = MIN (cstate->dfsnum, state->low);
3575
3576   /* We are part of our parents SCC, skip this type during hashing
3577      and return the unaltered hash value.  */
3578   return v;
3579 }
3580
3581 /* Hash the name of TYPE with the previous hash value V and return it.  */
3582
3583 static hashval_t
3584 iterative_hash_type_name (tree type, hashval_t v)
3585 {
3586   tree name = TYPE_NAME (TYPE_MAIN_VARIANT (type));
3587   if (!name)
3588     return v;
3589   if (TREE_CODE (name) == TYPE_DECL)
3590     name = DECL_NAME (name);
3591   if (!name)
3592     return v;
3593   gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
3594   /* Do not hash names of anonymous unions.  At least the C++ FE insists
3595      to have a non-NULL TYPE_NAME for them.  See cp/cp-tree.h for all
3596      the glory.  */
3597 #ifndef NO_DOT_IN_LABEL
3598   if (IDENTIFIER_POINTER (name)[0] == '.')
3599     return v;
3600 #else
3601 #ifndef NO_DOLLAR_IN_LABEL
3602   if (IDENTIFIER_POINTER (name)[0] == '$')
3603     return v;
3604 #else
3605   if (!strncmp (IDENTIFIER_POINTER (name), "__anon_", sizeof ("__anon_") - 1))
3606     return v;
3607 #endif
3608 #endif
3609   return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
3610 }
3611
3612 /* Returning a hash value for gimple type TYPE combined with VAL.
3613    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.
3614
3615    To hash a type we end up hashing in types that are reachable.
3616    Through pointers we can end up with cycles which messes up the
3617    required property that we need to compute the same hash value
3618    for structurally equivalent types.  To avoid this we have to
3619    hash all types in a cycle (the SCC) in a commutative way.  The
3620    easiest way is to not mix in the hashes of the SCC members at
3621    all.  To make this work we have to delay setting the hash
3622    values of the SCC until it is complete.  */
3623
3624 static hashval_t
3625 iterative_hash_gimple_type (tree type, hashval_t val,
3626                             VEC(tree, heap) **sccstack,
3627                             struct pointer_map_t *sccstate,
3628                             struct obstack *sccstate_obstack)
3629 {
3630   hashval_t v;
3631   void **slot;
3632   struct sccs *state;
3633
3634 #ifdef ENABLE_CHECKING
3635   /* Not visited during this DFS walk nor during previous walks.  */
3636   gcc_assert (!pointer_map_contains (type_hash_cache, type)
3637               && !pointer_map_contains (sccstate, type));
3638 #endif
3639   state = XOBNEW (sccstate_obstack, struct sccs);
3640   *pointer_map_insert (sccstate, type) = state;
3641
3642   VEC_safe_push (tree, heap, *sccstack, type);
3643   state->dfsnum = next_dfs_num++;
3644   state->low = state->dfsnum;
3645   state->on_sccstack = true;
3646
3647   /* Combine a few common features of types so that types are grouped into
3648      smaller sets; when searching for existing matching types to merge,
3649      only existing types having the same features as the new type will be
3650      checked.  */
3651   v = iterative_hash_hashval_t (TREE_CODE (type), 0);
3652   v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
3653   v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
3654
3655   /* Do not hash the types size as this will cause differences in
3656      hash values for the complete vs. the incomplete type variant.  */
3657
3658   /* Incorporate common features of numerical types.  */
3659   if (INTEGRAL_TYPE_P (type)
3660       || SCALAR_FLOAT_TYPE_P (type)
3661       || FIXED_POINT_TYPE_P (type))
3662     {
3663       v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
3664       v = iterative_hash_hashval_t (TYPE_MODE (type), v);
3665       v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
3666     }
3667
3668   /* For pointer and reference types, fold in information about the type
3669      pointed to but do not recurse into possibly incomplete types to
3670      avoid hash differences for complete vs. incomplete types.  */
3671   if (POINTER_TYPE_P (type))
3672     {
3673       if (AGGREGATE_TYPE_P (TREE_TYPE (type)))
3674         {
3675           v = iterative_hash_hashval_t (TREE_CODE (TREE_TYPE (type)), v);
3676           v = iterative_hash_type_name (type, v);
3677         }
3678       else
3679         v = visit (TREE_TYPE (type), state, v,
3680                    sccstack, sccstate, sccstate_obstack);
3681     }
3682
3683   /* Recurse for aggregates with a single element.  */
3684   if (TREE_CODE (type) == ARRAY_TYPE
3685       || TREE_CODE (type) == COMPLEX_TYPE
3686       || TREE_CODE (type) == VECTOR_TYPE)
3687     v = visit (TREE_TYPE (type), state, v,
3688                sccstack, sccstate, sccstate_obstack);
3689
3690   /* Incorporate function return and argument types.  */
3691   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
3692     {
3693       unsigned na;
3694       tree p;
3695
3696       /* For method types also incorporate their parent class.  */
3697       if (TREE_CODE (type) == METHOD_TYPE)
3698         v = visit (TYPE_METHOD_BASETYPE (type), state, v,
3699                    sccstack, sccstate, sccstate_obstack);
3700
3701       v = visit (TREE_TYPE (type), state, v,
3702                  sccstack, sccstate, sccstate_obstack);
3703
3704       for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
3705         {
3706           v = visit (TREE_VALUE (p), state, v,
3707                      sccstack, sccstate, sccstate_obstack);
3708           na++;
3709         }
3710
3711       v = iterative_hash_hashval_t (na, v);
3712     }
3713
3714   if (TREE_CODE (type) == RECORD_TYPE
3715       || TREE_CODE (type) == UNION_TYPE
3716       || TREE_CODE (type) == QUAL_UNION_TYPE)
3717     {
3718       unsigned nf;
3719       tree f;
3720
3721       v = iterative_hash_type_name (type, v);
3722
3723       for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
3724         {
3725           v = visit (TREE_TYPE (f), state, v,
3726