OSDN Git Service

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