OSDN Git Service

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