OSDN Git Service

fc40bf46eac26d42547cfe88ceb9de5e73d09e9a
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-forwprop.c
1 /* Forward propagation of expressions for single use variables.
2    Copyright (C) 2004, 2005, 2007, 2008, 2009 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "ggc.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "basic-block.h"
29 #include "timevar.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
33 #include "tree-dump.h"
34 #include "langhooks.h"
35 #include "flags.h"
36 #include "gimple.h"
37
38 /* This pass propagates the RHS of assignment statements into use
39    sites of the LHS of the assignment.  It's basically a specialized
40    form of tree combination.   It is hoped all of this can disappear
41    when we have a generalized tree combiner.
42
43    One class of common cases we handle is forward propagating a single use
44    variable into a COND_EXPR.
45
46      bb0:
47        x = a COND b;
48        if (x) goto ... else goto ...
49
50    Will be transformed into:
51
52      bb0:
53        if (a COND b) goto ... else goto ...
54
55    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
56
57    Or (assuming c1 and c2 are constants):
58
59      bb0:
60        x = a + c1;
61        if (x EQ/NEQ c2) goto ... else goto ...
62
63    Will be transformed into:
64
65      bb0:
66         if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
67
68    Similarly for x = a - c1.
69
70    Or
71
72      bb0:
73        x = !a
74        if (x) goto ... else goto ...
75
76    Will be transformed into:
77
78      bb0:
79         if (a == 0) goto ... else goto ...
80
81    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
82    For these cases, we propagate A into all, possibly more than one,
83    COND_EXPRs that use X.
84
85    Or
86
87      bb0:
88        x = (typecast) a
89        if (x) goto ... else goto ...
90
91    Will be transformed into:
92
93      bb0:
94         if (a != 0) goto ... else goto ...
95
96    (Assuming a is an integral type and x is a boolean or x is an
97     integral and a is a boolean.)
98
99    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
100    For these cases, we propagate A into all, possibly more than one,
101    COND_EXPRs that use X.
102
103    In addition to eliminating the variable and the statement which assigns
104    a value to the variable, we may be able to later thread the jump without
105    adding insane complexity in the dominator optimizer.
106
107    Also note these transformations can cascade.  We handle this by having
108    a worklist of COND_EXPR statements to examine.  As we make a change to
109    a statement, we put it back on the worklist to examine on the next
110    iteration of the main loop.
111
112    A second class of propagation opportunities arises for ADDR_EXPR
113    nodes.
114
115      ptr = &x->y->z;
116      res = *ptr;
117
118    Will get turned into
119
120      res = x->y->z;
121
122    Or
123      ptr = (type1*)&type2var;
124      res = *ptr
125
126    Will get turned into (if type1 and type2 are the same size
127    and neither have volatile on them):
128      res = VIEW_CONVERT_EXPR<type1>(type2var)
129
130    Or
131
132      ptr = &x[0];
133      ptr2 = ptr + <constant>;
134
135    Will get turned into
136
137      ptr2 = &x[constant/elementsize];
138
139   Or
140
141      ptr = &x[0];
142      offset = index * element_size;
143      offset_p = (pointer) offset;
144      ptr2 = ptr + offset_p
145
146   Will get turned into:
147
148      ptr2 = &x[index];
149
150   Or
151     ssa = (int) decl
152     res = ssa & 1
153
154   Provided that decl has known alignment >= 2, will get turned into
155
156     res = 0
157
158   We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
159   allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
160   {NOT_EXPR,NEG_EXPR}.
161
162    This will (of course) be extended as other needs arise.  */
163
164 static bool forward_propagate_addr_expr (tree name, tree rhs);
165
166 /* Set to true if we delete EH edges during the optimization.  */
167 static bool cfg_changed;
168
169 static tree rhs_to_tree (tree type, gimple stmt);
170
171 /* Get the next statement we can propagate NAME's value into skipping
172    trivial copies.  Returns the statement that is suitable as a
173    propagation destination or NULL_TREE if there is no such one.
174    This only returns destinations in a single-use chain.  FINAL_NAME_P
175    if non-NULL is written to the ssa name that represents the use.  */
176
177 static gimple
178 get_prop_dest_stmt (tree name, tree *final_name_p)
179 {
180   use_operand_p use;
181   gimple use_stmt;
182
183   do {
184     /* If name has multiple uses, bail out.  */
185     if (!single_imm_use (name, &use, &use_stmt))
186       return NULL;
187
188     /* If this is not a trivial copy, we found it.  */
189     if (!gimple_assign_ssa_name_copy_p (use_stmt)
190         || gimple_assign_rhs1 (use_stmt) != name)
191       break;
192
193     /* Continue searching uses of the copy destination.  */
194     name = gimple_assign_lhs (use_stmt);
195   } while (1);
196
197   if (final_name_p)
198     *final_name_p = name;
199
200   return use_stmt;
201 }
202
203 /* Get the statement we can propagate from into NAME skipping
204    trivial copies.  Returns the statement which defines the
205    propagation source or NULL_TREE if there is no such one.
206    If SINGLE_USE_ONLY is set considers only sources which have
207    a single use chain up to NAME.  If SINGLE_USE_P is non-null,
208    it is set to whether the chain to NAME is a single use chain
209    or not.  SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set.  */
210
211 static gimple
212 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
213 {
214   bool single_use = true;
215
216   do {
217     gimple def_stmt = SSA_NAME_DEF_STMT (name);
218
219     if (!has_single_use (name))
220       {
221         single_use = false;
222         if (single_use_only)
223           return NULL;
224       }
225
226     /* If name is defined by a PHI node or is the default def, bail out.  */
227     if (!is_gimple_assign (def_stmt))
228       return NULL;
229
230     /* If def_stmt is not a simple copy, we possibly found it.  */
231     if (!gimple_assign_ssa_name_copy_p (def_stmt))
232       {
233         tree rhs;
234
235         if (!single_use_only && single_use_p)
236           *single_use_p = single_use;
237
238         /* We can look through pointer conversions in the search
239            for a useful stmt for the comparison folding.  */
240         rhs = gimple_assign_rhs1 (def_stmt);
241         if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
242             && TREE_CODE (rhs) == SSA_NAME
243             && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
244             && POINTER_TYPE_P (TREE_TYPE (rhs)))
245           name = rhs;
246         else
247           return def_stmt;
248       }
249     else
250       {
251         /* Continue searching the def of the copy source name.  */
252         name = gimple_assign_rhs1 (def_stmt);
253       }
254   } while (1);
255 }
256
257 /* Checks if the destination ssa name in DEF_STMT can be used as
258    propagation source.  Returns true if so, otherwise false.  */
259
260 static bool
261 can_propagate_from (gimple def_stmt)
262 {
263   use_operand_p use_p;
264   ssa_op_iter iter;
265
266   gcc_assert (is_gimple_assign (def_stmt));
267
268   /* If the rhs has side-effects we cannot propagate from it.  */
269   if (gimple_has_volatile_ops (def_stmt))
270     return false;
271
272   /* If the rhs is a load we cannot propagate from it.  */
273   if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
274       || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
275     return false;
276
277   /* Constants can be always propagated.  */
278   if (gimple_assign_single_p (def_stmt)
279       && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
280     return true;
281
282   /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
283   FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_USE)
284     if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
285       return false;
286
287   /* If the definition is a conversion of a pointer to a function type,
288      then we can not apply optimizations as some targets require
289      function pointers to be canonicalized and in this case this
290      optimization could eliminate a necessary canonicalization.  */
291   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
292     {
293       tree rhs = gimple_assign_rhs1 (def_stmt);
294       if (POINTER_TYPE_P (TREE_TYPE (rhs))
295           && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
296         return false;
297     }
298
299   return true;
300 }
301
302 /* Remove a copy chain ending in NAME along the defs but not
303    further or including UP_TO_STMT.  If NAME was replaced in
304    its only use then this function can be used to clean up
305    dead stmts.  Returns true if UP_TO_STMT can be removed
306    as well, otherwise false.  */
307
308 static bool
309 remove_prop_source_from_use (tree name, gimple up_to_stmt)
310 {
311   gimple_stmt_iterator gsi;
312   gimple stmt;
313
314   do {
315     if (!has_zero_uses (name))
316       return false;
317
318     stmt = SSA_NAME_DEF_STMT (name);
319     if (stmt == up_to_stmt)
320       return true;
321
322     gsi = gsi_for_stmt (stmt);
323     release_defs (stmt);
324     gsi_remove (&gsi, true);
325
326     name = (gimple_assign_copy_p (stmt)) ? gimple_assign_rhs1 (stmt) : NULL;
327   } while (name && TREE_CODE (name) == SSA_NAME);
328
329   return false;
330 }
331
332 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
333    converted to type TYPE.
334
335    This should disappear, but is needed so we can combine expressions and use
336    the fold() interfaces. Long term, we need to develop folding and combine
337    routines that deal with gimple exclusively . */
338
339 static tree
340 rhs_to_tree (tree type, gimple stmt)
341 {
342   location_t loc = gimple_location (stmt);
343   enum tree_code code = gimple_assign_rhs_code (stmt);
344   if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
345     return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
346                         gimple_assign_rhs2 (stmt));
347   else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
348     return build1 (code, type, gimple_assign_rhs1 (stmt));
349   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
350     return gimple_assign_rhs1 (stmt);
351   else
352     gcc_unreachable ();
353 }
354
355 /* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
356    the folded result in a form suitable for COND_EXPR_COND or
357    NULL_TREE, if there is no suitable simplified form.  If
358    INVARIANT_ONLY is true only gimple_min_invariant results are
359    considered simplified.  */
360
361 static tree
362 combine_cond_expr_cond (location_t loc, enum tree_code code, tree type,
363                         tree op0, tree op1, bool invariant_only)
364 {
365   tree t;
366
367   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
368
369   t = fold_binary_loc (loc, code, type, op0, op1);
370   if (!t)
371     return NULL_TREE;
372
373   /* Require that we got a boolean type out if we put one in.  */
374   gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
375
376   /* Canonicalize the combined condition for use in a COND_EXPR.  */
377   t = canonicalize_cond_expr_cond (t);
378
379   /* Bail out if we required an invariant but didn't get one.  */
380   if (!t || (invariant_only && !is_gimple_min_invariant (t)))
381     return NULL_TREE;
382
383   return t;
384 }
385
386 /* Propagate from the ssa name definition statements of COND_EXPR
387    in GIMPLE_COND statement STMT into the conditional if that simplifies it.
388    Returns zero if no statement was changed, one if there were
389    changes and two if cfg_cleanup needs to run.
390
391    This must be kept in sync with forward_propagate_into_cond.  */
392
393 static int
394 forward_propagate_into_gimple_cond (gimple stmt)
395 {
396   int did_something = 0;
397   location_t loc = gimple_location (stmt);
398
399   do {
400     tree tmp = NULL_TREE;
401     tree name = NULL_TREE, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
402     gimple def_stmt;
403     bool single_use0_p = false, single_use1_p = false;
404     enum tree_code code = gimple_cond_code (stmt);
405
406     /* We can do tree combining on SSA_NAME and comparison expressions.  */
407     if (TREE_CODE_CLASS (gimple_cond_code (stmt)) == tcc_comparison)
408       {
409         /* For comparisons use the first operand, that is likely to
410            simplify comparisons against constants.  */
411         if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME)
412           {
413             name = gimple_cond_lhs (stmt);
414             def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
415             if (def_stmt && can_propagate_from (def_stmt))
416               {
417                 tree op1 = gimple_cond_rhs (stmt);
418                 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
419                 tmp = combine_cond_expr_cond (loc, code, boolean_type_node,
420                                               rhs0, op1, !single_use0_p);
421               }
422           }
423         /* If that wasn't successful, try the second operand.  */
424         if (tmp == NULL_TREE
425             && TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME)
426           {
427             tree op0 = gimple_cond_lhs (stmt);
428             name = gimple_cond_rhs (stmt);
429             def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
430             if (!def_stmt || !can_propagate_from (def_stmt))
431               return did_something;
432
433             rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
434             tmp = combine_cond_expr_cond (loc, code, boolean_type_node, op0,
435                                           rhs1, !single_use1_p);
436           }
437         /* If that wasn't successful either, try both operands.  */
438         if (tmp == NULL_TREE
439             && rhs0 != NULL_TREE
440             && rhs1 != NULL_TREE)
441           tmp = combine_cond_expr_cond (loc, code, boolean_type_node, rhs0,
442                                         fold_convert_loc (loc,
443                                                           TREE_TYPE (rhs0),
444                                                           rhs1),
445                                         !(single_use0_p && single_use1_p));
446       }
447
448     if (tmp)
449       {
450         if (dump_file && tmp)
451           {
452             tree cond = build2 (gimple_cond_code (stmt),
453                                 boolean_type_node,
454                                 gimple_cond_lhs (stmt),
455                                 gimple_cond_rhs (stmt));
456             fprintf (dump_file, "  Replaced '");
457             print_generic_expr (dump_file, cond, 0);
458             fprintf (dump_file, "' with '");
459             print_generic_expr (dump_file, tmp, 0);
460             fprintf (dump_file, "'\n");
461           }
462
463         gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
464         update_stmt (stmt);
465
466         /* Remove defining statements.  */
467         remove_prop_source_from_use (name, NULL);
468
469         if (is_gimple_min_invariant (tmp))
470           did_something = 2;
471         else if (did_something == 0)
472           did_something = 1;
473
474         /* Continue combining.  */
475         continue;
476       }
477
478     break;
479   } while (1);
480
481   return did_something;
482 }
483
484
485 /* Propagate from the ssa name definition statements of COND_EXPR
486    in the rhs of statement STMT into the conditional if that simplifies it.
487    Returns zero if no statement was changed, one if there were
488    changes and two if cfg_cleanup needs to run.
489
490    This must be kept in sync with forward_propagate_into_gimple_cond.  */
491
492 static int
493 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
494 {
495   gimple stmt = gsi_stmt (*gsi_p);
496   location_t loc = gimple_location (stmt);
497   int did_something = 0;
498
499   do {
500     tree tmp = NULL_TREE;
501     tree cond = gimple_assign_rhs1 (stmt);
502     tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
503     gimple def_stmt;
504     bool single_use0_p = false, single_use1_p = false;
505
506     /* We can do tree combining on SSA_NAME and comparison expressions.  */
507     if (COMPARISON_CLASS_P (cond)
508         && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME)
509       {
510         /* For comparisons use the first operand, that is likely to
511            simplify comparisons against constants.  */
512         name = TREE_OPERAND (cond, 0);
513         def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
514         if (def_stmt && can_propagate_from (def_stmt))
515           {
516             tree op1 = TREE_OPERAND (cond, 1);
517             rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
518             tmp = combine_cond_expr_cond (loc, TREE_CODE (cond),
519                                           boolean_type_node,
520                                           rhs0, op1, !single_use0_p);
521           }
522         /* If that wasn't successful, try the second operand.  */
523         if (tmp == NULL_TREE
524             && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME)
525           {
526             tree op0 = TREE_OPERAND (cond, 0);
527             name = TREE_OPERAND (cond, 1);
528             def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
529             if (!def_stmt || !can_propagate_from (def_stmt))
530               return did_something;
531
532             rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
533             tmp = combine_cond_expr_cond (loc, TREE_CODE (cond),
534                                           boolean_type_node,
535                                           op0, rhs1, !single_use1_p);
536           }
537         /* If that wasn't successful either, try both operands.  */
538         if (tmp == NULL_TREE
539             && rhs0 != NULL_TREE
540             && rhs1 != NULL_TREE)
541           tmp = combine_cond_expr_cond (loc, TREE_CODE (cond),
542                                         boolean_type_node,
543                                         rhs0,
544                                         fold_convert_loc (loc,
545                                                           TREE_TYPE (rhs0),
546                                                           rhs1),
547                                         !(single_use0_p && single_use1_p));
548       }
549     else if (TREE_CODE (cond) == SSA_NAME)
550       {
551         name = cond;
552         def_stmt = get_prop_source_stmt (name, true, NULL);
553         if (def_stmt || !can_propagate_from (def_stmt))
554           return did_something;
555
556         rhs0 = gimple_assign_rhs1 (def_stmt);
557         tmp = combine_cond_expr_cond (loc, NE_EXPR, boolean_type_node, rhs0,
558                                       build_int_cst (TREE_TYPE (rhs0), 0),
559                                       false);
560       }
561
562     if (tmp)
563       {
564         if (dump_file && tmp)
565           {
566             fprintf (dump_file, "  Replaced '");
567             print_generic_expr (dump_file, cond, 0);
568             fprintf (dump_file, "' with '");
569             print_generic_expr (dump_file, tmp, 0);
570             fprintf (dump_file, "'\n");
571           }
572
573         gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp));
574         stmt = gsi_stmt (*gsi_p);
575         update_stmt (stmt);
576
577         /* Remove defining statements.  */
578         remove_prop_source_from_use (name, NULL);
579
580         if (is_gimple_min_invariant (tmp))
581           did_something = 2;
582         else if (did_something == 0)
583           did_something = 1;
584
585         /* Continue combining.  */
586         continue;
587       }
588
589     break;
590   } while (1);
591
592   return did_something;
593 }
594
595 /* We've just substituted an ADDR_EXPR into stmt.  Update all the
596    relevant data structures to match.  */
597
598 static void
599 tidy_after_forward_propagate_addr (gimple stmt)
600 {
601   /* We may have turned a trapping insn into a non-trapping insn.  */
602   if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
603       && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
604     cfg_changed = true;
605
606   if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
607      recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
608 }
609
610 /* DEF_RHS contains the address of the 0th element in an array.
611    USE_STMT uses type of DEF_RHS to compute the address of an
612    arbitrary element within the array.  The (variable) byte offset
613    of the element is contained in OFFSET.
614
615    We walk back through the use-def chains of OFFSET to verify that
616    it is indeed computing the offset of an element within the array
617    and extract the index corresponding to the given byte offset.
618
619    We then try to fold the entire address expression into a form
620    &array[index].
621
622    If we are successful, we replace the right hand side of USE_STMT
623    with the new address computation.  */
624
625 static bool
626 forward_propagate_addr_into_variable_array_index (tree offset,
627                                                   tree def_rhs,
628                                                   gimple_stmt_iterator *use_stmt_gsi)
629 {
630   tree index, tunit;
631   gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
632   tree tmp;
633
634   tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
635   if (!host_integerp (tunit, 1))
636     return false;
637
638   /* Get the offset's defining statement.  */
639   offset_def = SSA_NAME_DEF_STMT (offset);
640
641   /* Try to find an expression for a proper index.  This is either a
642      multiplication expression by the element size or just the ssa name we came
643      along in case the element size is one. In that case, however, we do not
644      allow multiplications because they can be computing index to a higher
645      level dimension (PR 37861). */
646   if (integer_onep (tunit))
647     {
648       if (is_gimple_assign (offset_def)
649           && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
650         return false;
651
652       index = offset;
653     }
654   else
655     {
656       /* The statement which defines OFFSET before type conversion
657          must be a simple GIMPLE_ASSIGN.  */
658       if (!is_gimple_assign (offset_def))
659         return false;
660
661       /* The RHS of the statement which defines OFFSET must be a
662          multiplication of an object by the size of the array elements.
663          This implicitly verifies that the size of the array elements
664          is constant.  */
665      if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
666          && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
667          && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
668        {
669          /* The first operand to the MULT_EXPR is the desired index.  */
670          index = gimple_assign_rhs1 (offset_def);
671        }
672      /* If we have idx * tunit + CST * tunit re-associate that.  */
673      else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
674                || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
675               && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
676               && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
677               && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
678                                                gimple_assign_rhs2 (offset_def),
679                                                tunit)) != NULL_TREE)
680        {
681          gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
682          if (is_gimple_assign (offset_def2)
683              && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
684              && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
685              && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
686            {
687              index = fold_build2 (gimple_assign_rhs_code (offset_def),
688                                   TREE_TYPE (offset),
689                                   gimple_assign_rhs1 (offset_def2), tmp);
690            }
691          else
692            return false;
693        }
694      else
695         return false;
696     }
697
698   /* Replace the pointer addition with array indexing.  */
699   index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
700                                     true, GSI_SAME_STMT);
701   gimple_assign_set_rhs_from_tree (use_stmt_gsi, unshare_expr (def_rhs));
702   use_stmt = gsi_stmt (*use_stmt_gsi);
703   TREE_OPERAND (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0), 1)
704     = index;
705
706   /* That should have created gimple, so there is no need to
707      record information to undo the propagation.  */
708   fold_stmt_inplace (use_stmt);
709   tidy_after_forward_propagate_addr (use_stmt);
710   return true;
711 }
712
713 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
714    ADDR_EXPR <whatever>.
715
716    Try to forward propagate the ADDR_EXPR into the use USE_STMT.
717    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
718    node or for recovery of array indexing from pointer arithmetic.
719
720    Return true if the propagation was successful (the propagation can
721    be not totally successful, yet things may have been changed).  */
722
723 static bool
724 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
725                                gimple_stmt_iterator *use_stmt_gsi,
726                                bool single_use_p)
727 {
728   tree lhs, rhs, rhs2, array_ref;
729   tree *rhsp, *lhsp;
730   gimple use_stmt = gsi_stmt (*use_stmt_gsi);
731   enum tree_code rhs_code;
732   bool res = true;
733
734   gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
735
736   lhs = gimple_assign_lhs (use_stmt);
737   rhs_code = gimple_assign_rhs_code (use_stmt);
738   rhs = gimple_assign_rhs1 (use_stmt);
739
740   /* Trivial cases.  The use statement could be a trivial copy or a
741      useless conversion.  Recurse to the uses of the lhs as copyprop does
742      not copy through different variant pointers and FRE does not catch
743      all useless conversions.  Treat the case of a single-use name and
744      a conversion to def_rhs type separate, though.  */
745   if (TREE_CODE (lhs) == SSA_NAME
746       && ((rhs_code == SSA_NAME && rhs == name)
747           || CONVERT_EXPR_CODE_P (rhs_code)))
748     {
749       /* Only recurse if we don't deal with a single use or we cannot
750          do the propagation to the current statement.  In particular
751          we can end up with a conversion needed for a non-invariant
752          address which we cannot do in a single statement.  */
753       if (!single_use_p
754           || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
755               && (!is_gimple_min_invariant (def_rhs)
756                   || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
757                       && POINTER_TYPE_P (TREE_TYPE (def_rhs))
758                       && (TYPE_PRECISION (TREE_TYPE (lhs))
759                           > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
760         return forward_propagate_addr_expr (lhs, def_rhs);
761
762       gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
763       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
764         gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
765       else
766         gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
767       return true;
768     }
769
770   /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
771      ADDR_EXPR will not appear on the LHS.  */
772   lhsp = gimple_assign_lhs_ptr (use_stmt);
773   while (handled_component_p (*lhsp))
774     lhsp = &TREE_OPERAND (*lhsp, 0);
775   lhs = *lhsp;
776
777   /* Now see if the LHS node is an INDIRECT_REF using NAME.  If so,
778      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
779   if (TREE_CODE (lhs) == INDIRECT_REF
780       && TREE_OPERAND (lhs, 0) == name)
781     {
782       if (may_propagate_address_into_dereference (def_rhs, lhs)
783           && (lhsp != gimple_assign_lhs_ptr (use_stmt)
784               || useless_type_conversion_p
785                    (TREE_TYPE (TREE_OPERAND (def_rhs, 0)), TREE_TYPE (rhs))))
786         {
787           *lhsp = unshare_expr (TREE_OPERAND (def_rhs, 0));
788           fold_stmt_inplace (use_stmt);
789           tidy_after_forward_propagate_addr (use_stmt);
790
791           /* Continue propagating into the RHS if this was not the only use.  */
792           if (single_use_p)
793             return true;
794         }
795       else
796         /* We can have a struct assignment dereferencing our name twice.
797            Note that we didn't propagate into the lhs to not falsely
798            claim we did when propagating into the rhs.  */
799         res = false;
800     }
801
802   /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
803      nodes from the RHS.  */
804   rhsp = gimple_assign_rhs1_ptr (use_stmt);
805   while (handled_component_p (*rhsp)
806          || TREE_CODE (*rhsp) == ADDR_EXPR)
807     rhsp = &TREE_OPERAND (*rhsp, 0);
808   rhs = *rhsp;
809
810   /* Now see if the RHS node is an INDIRECT_REF using NAME.  If so,
811      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
812   if (TREE_CODE (rhs) == INDIRECT_REF
813       && TREE_OPERAND (rhs, 0) == name
814       && may_propagate_address_into_dereference (def_rhs, rhs))
815     {
816       *rhsp = unshare_expr (TREE_OPERAND (def_rhs, 0));
817       fold_stmt_inplace (use_stmt);
818       tidy_after_forward_propagate_addr (use_stmt);
819       return res;
820     }
821
822   /* Now see if the RHS node is an INDIRECT_REF using NAME.  If so,
823      propagate the ADDR_EXPR into the use of NAME and try to
824      create a VCE and fold the result.  */
825   if (TREE_CODE (rhs) == INDIRECT_REF
826       && TREE_OPERAND (rhs, 0) == name
827       && TYPE_SIZE (TREE_TYPE (rhs))
828       && TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0)))
829       /* Function decls should not be used for VCE either as it could be a
830          function descriptor that we want and not the actual function code.  */
831       && TREE_CODE (TREE_OPERAND (def_rhs, 0)) != FUNCTION_DECL
832       /* We should not convert volatile loads to non volatile loads. */
833       && !TYPE_VOLATILE (TREE_TYPE (rhs))
834       && !TYPE_VOLATILE (TREE_TYPE (TREE_OPERAND (def_rhs, 0)))
835       && operand_equal_p (TYPE_SIZE (TREE_TYPE (rhs)),
836                           TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))), 0)
837       /* Make sure we only do TBAA compatible replacements.  */
838       && get_alias_set (TREE_OPERAND (def_rhs, 0)) == get_alias_set (rhs))
839    {
840      tree def_rhs_base, new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
841      new_rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), new_rhs);
842      if (TREE_CODE (new_rhs) != VIEW_CONVERT_EXPR)
843        {
844          /* If we have folded the VIEW_CONVERT_EXPR then the result is only
845             valid if we can replace the whole rhs of the use statement.  */
846          if (rhs != gimple_assign_rhs1 (use_stmt))
847            return false;
848          new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true, NULL,
849                                              true, GSI_NEW_STMT);
850          gimple_assign_set_rhs1 (use_stmt, new_rhs);
851          tidy_after_forward_propagate_addr (use_stmt);
852          return res;
853        }
854      /* If the defining rhs comes from an indirect reference, then do not
855         convert into a VIEW_CONVERT_EXPR.  */
856      def_rhs_base = TREE_OPERAND (def_rhs, 0);
857      while (handled_component_p (def_rhs_base))
858        def_rhs_base = TREE_OPERAND (def_rhs_base, 0);
859      if (!INDIRECT_REF_P (def_rhs_base))
860        {
861          /* We may have arbitrary VIEW_CONVERT_EXPRs in a nested component
862             reference.  Place it there and fold the thing.  */
863          *rhsp = new_rhs;
864          fold_stmt_inplace (use_stmt);
865          tidy_after_forward_propagate_addr (use_stmt);
866          return res;
867        }
868    }
869
870   /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
871      is nothing to do. */
872   if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
873       || gimple_assign_rhs1 (use_stmt) != name)
874     return false;
875
876   /* The remaining cases are all for turning pointer arithmetic into
877      array indexing.  They only apply when we have the address of
878      element zero in an array.  If that is not the case then there
879      is nothing to do.  */
880   array_ref = TREE_OPERAND (def_rhs, 0);
881   if (TREE_CODE (array_ref) != ARRAY_REF
882       || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
883       || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
884     return false;
885
886   rhs2 = gimple_assign_rhs2 (use_stmt);
887   /* Try to optimize &x[C1] p+ C2 where C2 is a multiple of the size
888      of the elements in X into &x[C1 + C2/element size].  */
889   if (TREE_CODE (rhs2) == INTEGER_CST)
890     {
891       tree new_rhs = maybe_fold_stmt_addition (gimple_location (use_stmt),
892                                                TREE_TYPE (def_rhs),
893                                                def_rhs, rhs2);
894       if (new_rhs)
895         {
896           tree type = TREE_TYPE (gimple_assign_lhs (use_stmt));
897           new_rhs = unshare_expr (new_rhs);
898           if (!useless_type_conversion_p (type, TREE_TYPE (new_rhs)))
899             {
900               if (!is_gimple_min_invariant (new_rhs))
901                 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs,
902                                                     true, NULL_TREE,
903                                                     true, GSI_SAME_STMT);
904               new_rhs = fold_convert (type, new_rhs);
905             }
906           gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
907           use_stmt = gsi_stmt (*use_stmt_gsi);
908           update_stmt (use_stmt);
909           tidy_after_forward_propagate_addr (use_stmt);
910           return true;
911         }
912     }
913
914   /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
915      converting a multiplication of an index by the size of the
916      array elements, then the result is converted into the proper
917      type for the arithmetic.  */
918   if (TREE_CODE (rhs2) == SSA_NAME
919       && integer_zerop (TREE_OPERAND (array_ref, 1))
920       && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
921       /* Avoid problems with IVopts creating PLUS_EXPRs with a
922          different type than their operands.  */
923       && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
924     return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
925                                                              use_stmt_gsi);
926   return false;
927 }
928
929 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
930
931    Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
932    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
933    node or for recovery of array indexing from pointer arithmetic.
934    Returns true, if all uses have been propagated into.  */
935
936 static bool
937 forward_propagate_addr_expr (tree name, tree rhs)
938 {
939   int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
940   imm_use_iterator iter;
941   gimple use_stmt;
942   bool all = true;
943   bool single_use_p = has_single_use (name);
944
945   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
946     {
947       bool result;
948       tree use_rhs;
949
950       /* If the use is not in a simple assignment statement, then
951          there is nothing we can do.  */
952       if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
953         {
954           if (!is_gimple_debug (use_stmt))
955             all = false;
956           continue;
957         }
958
959       /* If the use is in a deeper loop nest, then we do not want
960          to propagate non-invariant ADDR_EXPRs into the loop as that
961          is likely adding expression evaluations into the loop.  */
962       if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
963           && !is_gimple_min_invariant (rhs))
964         {
965           all = false;
966           continue;
967         }
968
969       {
970         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
971         result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
972                                                 single_use_p);
973         /* If the use has moved to a different statement adjust
974            the update machinery for the old statement too.  */
975         if (use_stmt != gsi_stmt (gsi))
976           {
977             update_stmt (use_stmt);
978             use_stmt = gsi_stmt (gsi);
979           }
980
981         update_stmt (use_stmt);
982       }
983       all &= result;
984
985       /* Remove intermediate now unused copy and conversion chains.  */
986       use_rhs = gimple_assign_rhs1 (use_stmt);
987       if (result
988           && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
989           && TREE_CODE (use_rhs) == SSA_NAME
990           && has_zero_uses (gimple_assign_lhs (use_stmt)))
991         {
992           gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
993           release_defs (use_stmt);
994           gsi_remove (&gsi, true);
995         }
996     }
997
998   return all;
999 }
1000
1001 /* Forward propagate the comparison defined in STMT like
1002    cond_1 = x CMP y to uses of the form
1003      a_1 = (T')cond_1
1004      a_1 = !cond_1
1005      a_1 = cond_1 != 0
1006    Returns true if stmt is now unused.  */
1007
1008 static bool
1009 forward_propagate_comparison (gimple stmt)
1010 {
1011   tree name = gimple_assign_lhs (stmt);
1012   gimple use_stmt;
1013   tree tmp = NULL_TREE;
1014
1015   /* Don't propagate ssa names that occur in abnormal phis.  */
1016   if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1017        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1018       || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1019         && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1020     return false;
1021
1022   /* Do not un-cse comparisons.  But propagate through copies.  */
1023   use_stmt = get_prop_dest_stmt (name, &name);
1024   if (!use_stmt)
1025     return false;
1026
1027   /* Conversion of the condition result to another integral type.  */
1028   if (is_gimple_assign (use_stmt)
1029       && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
1030           || TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1031              == tcc_comparison
1032           || gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
1033       && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt))))
1034     {
1035       tree lhs = gimple_assign_lhs (use_stmt);
1036
1037       /* We can propagate the condition into a conversion.  */
1038       if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1039         {
1040           /* Avoid using fold here as that may create a COND_EXPR with
1041              non-boolean condition as canonical form.  */
1042           tmp = build2 (gimple_assign_rhs_code (stmt), TREE_TYPE (lhs),
1043                         gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt));
1044         }
1045       /* We can propagate the condition into X op CST where op
1046          is EQ_EXPR or NE_EXPR and CST is either one or zero.  */
1047       else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1048               == tcc_comparison
1049              && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
1050              && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
1051       {
1052         enum tree_code code = gimple_assign_rhs_code (use_stmt);
1053         tree cst = gimple_assign_rhs2 (use_stmt);
1054         tree cond;
1055
1056         cond = build2 (gimple_assign_rhs_code (stmt),
1057                        TREE_TYPE (cst),
1058                        gimple_assign_rhs1 (stmt),
1059                        gimple_assign_rhs2 (stmt));
1060
1061         tmp = combine_cond_expr_cond (gimple_location (use_stmt),
1062                                       code, TREE_TYPE (lhs),
1063                                       cond, cst, false);
1064         if (tmp == NULL_TREE)
1065           return false;
1066       }
1067       /* We can propagate the condition into a statement that
1068          computes the logical negation of the comparison result.  */
1069       else if (gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
1070         {
1071           tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1072           bool nans = HONOR_NANS (TYPE_MODE (type));
1073           enum tree_code code;
1074           code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1075           if (code == ERROR_MARK)
1076             return false;
1077
1078           tmp = build2 (code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1079                         gimple_assign_rhs2 (stmt));
1080         }
1081       else
1082         return false;
1083
1084       {
1085         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1086         gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1087         use_stmt = gsi_stmt (gsi);
1088         update_stmt (use_stmt);
1089       }
1090
1091       /* Remove defining statements.  */
1092       remove_prop_source_from_use (name, stmt);
1093
1094       if (dump_file && (dump_flags & TDF_DETAILS))
1095         {
1096           tree old_rhs = rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt)),
1097                                       stmt);
1098           fprintf (dump_file, "  Replaced '");
1099           print_generic_expr (dump_file, old_rhs, dump_flags);
1100           fprintf (dump_file, "' with '");
1101           print_generic_expr (dump_file, tmp, dump_flags);
1102           fprintf (dump_file, "'\n");
1103         }
1104
1105       return true;
1106     }
1107
1108   return false;
1109 }
1110
1111 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1112    If so, we can change STMT into lhs = y which can later be copy
1113    propagated.  Similarly for negation.
1114
1115    This could trivially be formulated as a forward propagation
1116    to immediate uses.  However, we already had an implementation
1117    from DOM which used backward propagation via the use-def links.
1118
1119    It turns out that backward propagation is actually faster as
1120    there's less work to do for each NOT/NEG expression we find.
1121    Backwards propagation needs to look at the statement in a single
1122    backlink.  Forward propagation needs to look at potentially more
1123    than one forward link.  */
1124
1125 static void
1126 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1127 {
1128   gimple stmt = gsi_stmt (*gsi_p);
1129   tree rhs = gimple_assign_rhs1 (stmt);
1130   gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1131
1132   /* See if the RHS_DEF_STMT has the same form as our statement.  */
1133   if (is_gimple_assign (rhs_def_stmt)
1134       && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1135     {
1136       tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1137
1138       /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME.  */
1139       if (TREE_CODE (rhs_def_operand) == SSA_NAME
1140           && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1141         {
1142           gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1143           stmt = gsi_stmt (*gsi_p);
1144           update_stmt (stmt);
1145         }
1146     }
1147 }
1148
1149 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1150    the condition which we may be able to optimize better.  */
1151
1152 static void
1153 simplify_gimple_switch (gimple stmt)
1154 {
1155   tree cond = gimple_switch_index (stmt);
1156   tree def, to, ti;
1157   gimple def_stmt;
1158
1159   /* The optimization that we really care about is removing unnecessary
1160      casts.  That will let us do much better in propagating the inferred
1161      constant at the switch target.  */
1162   if (TREE_CODE (cond) == SSA_NAME)
1163     {
1164       def_stmt = SSA_NAME_DEF_STMT (cond);
1165       if (is_gimple_assign (def_stmt))
1166         {
1167           if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1168             {
1169               int need_precision;
1170               bool fail;
1171
1172               def = gimple_assign_rhs1 (def_stmt);
1173
1174 #ifdef ENABLE_CHECKING
1175               /* ??? Why was Jeff testing this?  We are gimple...  */
1176               gcc_assert (is_gimple_val (def));
1177 #endif
1178
1179               to = TREE_TYPE (cond);
1180               ti = TREE_TYPE (def);
1181
1182               /* If we have an extension that preserves value, then we
1183                  can copy the source value into the switch.  */
1184
1185               need_precision = TYPE_PRECISION (ti);
1186               fail = false;
1187               if (! INTEGRAL_TYPE_P (ti))
1188                 fail = true;
1189               else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1190                 fail = true;
1191               else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1192                 need_precision += 1;
1193               if (TYPE_PRECISION (to) < need_precision)
1194                 fail = true;
1195
1196               if (!fail)
1197                 {
1198                   gimple_switch_set_index (stmt, def);
1199                   update_stmt (stmt);
1200                 }
1201             }
1202         }
1203     }
1204 }
1205
1206 /* Run bitwise and assignments throug the folder.  If the first argument is an
1207    ssa name that is itself a result of a typecast of an ADDR_EXPR to an
1208    integer, feed the ADDR_EXPR to the folder rather than the ssa name.
1209 */
1210
1211 static void
1212 simplify_bitwise_and (gimple_stmt_iterator *gsi, gimple stmt)
1213 {
1214   tree res;
1215   tree arg1 = gimple_assign_rhs1 (stmt);
1216   tree arg2 = gimple_assign_rhs2 (stmt);
1217
1218   if (TREE_CODE (arg2) != INTEGER_CST)
1219     return;
1220
1221   if (TREE_CODE (arg1) == SSA_NAME && !SSA_NAME_IS_DEFAULT_DEF (arg1))
1222     {
1223       gimple def = SSA_NAME_DEF_STMT (arg1);
1224
1225       if (gimple_assign_cast_p (def)
1226           && INTEGRAL_TYPE_P (gimple_expr_type (def)))
1227         {
1228           tree op = gimple_assign_rhs1 (def);
1229
1230           if (TREE_CODE (op) == ADDR_EXPR)
1231             arg1 = op;
1232         }
1233     }
1234
1235   res = fold_binary_loc (gimple_location (stmt),
1236                      BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
1237                      arg1, arg2);
1238   if (res && is_gimple_min_invariant (res))
1239     {
1240       gimple_assign_set_rhs_from_tree (gsi, res);
1241       update_stmt (stmt);
1242     }
1243   return;
1244 }
1245
1246 /* Main entry point for the forward propagation optimizer.  */
1247
1248 static unsigned int
1249 tree_ssa_forward_propagate_single_use_vars (void)
1250 {
1251   basic_block bb;
1252   unsigned int todoflags = 0;
1253
1254   cfg_changed = false;
1255
1256   FOR_EACH_BB (bb)
1257     {
1258       gimple_stmt_iterator gsi;
1259
1260       /* Note we update GSI within the loop as necessary.  */
1261       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1262         {
1263           gimple stmt = gsi_stmt (gsi);
1264
1265           /* If this statement sets an SSA_NAME to an address,
1266              try to propagate the address into the uses of the SSA_NAME.  */
1267           if (is_gimple_assign (stmt))
1268             {
1269               tree lhs = gimple_assign_lhs (stmt);
1270               tree rhs = gimple_assign_rhs1 (stmt);
1271
1272               if (TREE_CODE (lhs) != SSA_NAME)
1273                 {
1274                   gsi_next (&gsi);
1275                   continue;
1276                 }
1277
1278               if (gimple_assign_rhs_code (stmt) == ADDR_EXPR
1279                   /* Handle pointer conversions on invariant addresses
1280                      as well, as this is valid gimple.  */
1281                   || (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
1282                       && TREE_CODE (rhs) == ADDR_EXPR
1283                       && POINTER_TYPE_P (TREE_TYPE (lhs))))
1284                 {
1285                   STRIP_NOPS (rhs);
1286                   if (!stmt_references_abnormal_ssa_name (stmt)
1287                       && forward_propagate_addr_expr (lhs, rhs))
1288                     {
1289                       release_defs (stmt);
1290                       todoflags |= TODO_remove_unused_locals;
1291                       gsi_remove (&gsi, true);
1292                     }
1293                   else
1294                     gsi_next (&gsi);
1295                 }
1296               else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
1297                        && is_gimple_min_invariant (rhs))
1298                 {
1299                   /* Make sure to fold &a[0] + off_1 here.  */
1300                   fold_stmt_inplace (stmt);
1301                   update_stmt (stmt);
1302                   if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1303                     gsi_next (&gsi);
1304                 }
1305               else if ((gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR
1306                         || gimple_assign_rhs_code (stmt) == NEGATE_EXPR)
1307                        && TREE_CODE (rhs) == SSA_NAME)
1308                 {
1309                   simplify_not_neg_expr (&gsi);
1310                   gsi_next (&gsi);
1311                 }
1312               else if (gimple_assign_rhs_code (stmt) == COND_EXPR)
1313                 {
1314                   /* In this case the entire COND_EXPR is in rhs1. */
1315                   int did_something;
1316                   fold_defer_overflow_warnings ();
1317                   did_something = forward_propagate_into_cond (&gsi);
1318                   stmt = gsi_stmt (gsi);
1319                   if (did_something == 2)
1320                     cfg_changed = true;
1321                   fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs)
1322                     && did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
1323                   gsi_next (&gsi);
1324                 }
1325               else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
1326                                         == tcc_comparison)
1327                 {
1328                   if (forward_propagate_comparison (stmt))
1329                     {
1330                       release_defs (stmt);
1331                       todoflags |= TODO_remove_unused_locals;
1332                       gsi_remove (&gsi, true);
1333                     }
1334                   else
1335                     gsi_next (&gsi);
1336                 }
1337               else if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR)
1338                 {
1339                   simplify_bitwise_and (&gsi, stmt);
1340                   gsi_next (&gsi);
1341                 }
1342               else
1343                 gsi_next (&gsi);
1344             }
1345           else if (gimple_code (stmt) == GIMPLE_SWITCH)
1346             {
1347               simplify_gimple_switch (stmt);
1348               gsi_next (&gsi);
1349             }
1350           else if (gimple_code (stmt) == GIMPLE_COND)
1351             {
1352               int did_something;
1353               fold_defer_overflow_warnings ();
1354               did_something = forward_propagate_into_gimple_cond (stmt);
1355               if (did_something == 2)
1356                 cfg_changed = true;
1357               fold_undefer_overflow_warnings (did_something, stmt,
1358                                               WARN_STRICT_OVERFLOW_CONDITIONAL);
1359               gsi_next (&gsi);
1360             }
1361           else
1362             gsi_next (&gsi);
1363         }
1364     }
1365
1366   if (cfg_changed)
1367     todoflags |= TODO_cleanup_cfg;
1368   return todoflags;
1369 }
1370
1371
1372 static bool
1373 gate_forwprop (void)
1374 {
1375   return flag_tree_forwprop;
1376 }
1377
1378 struct gimple_opt_pass pass_forwprop =
1379 {
1380  {
1381   GIMPLE_PASS,
1382   "forwprop",                   /* name */
1383   gate_forwprop,                /* gate */
1384   tree_ssa_forward_propagate_single_use_vars,   /* execute */
1385   NULL,                         /* sub */
1386   NULL,                         /* next */
1387   0,                            /* static_pass_number */
1388   TV_TREE_FORWPROP,             /* tv_id */
1389   PROP_cfg | PROP_ssa,          /* properties_required */
1390   0,                            /* properties_provided */
1391   0,                            /* properties_destroyed */
1392   0,                            /* todo_flags_start */
1393   TODO_dump_func
1394   | TODO_ggc_collect
1395   | TODO_update_ssa
1396   | TODO_verify_ssa             /* todo_flags_finish */
1397  }
1398 };
1399