OSDN Git Service

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