re PR middle-end/64922 (runtime error: member call on misaligned address for type...
[official-gcc.git] / gcc / gimple-fold.c
blobf89220c5a68a89576f586de581797b61df3814f1
1 /* Statement simplification on GIMPLE.
2 Copyright (C) 2010-2015 Free Software Foundation, Inc.
3 Split out from tree-ssa-ccp.c.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "wide-int.h"
33 #include "inchash.h"
34 #include "tree.h"
35 #include "fold-const.h"
36 #include "stringpool.h"
37 #include "hashtab.h"
38 #include "hard-reg-set.h"
39 #include "function.h"
40 #include "rtl.h"
41 #include "flags.h"
42 #include "statistics.h"
43 #include "real.h"
44 #include "fixed-value.h"
45 #include "insn-config.h"
46 #include "expmed.h"
47 #include "dojump.h"
48 #include "explow.h"
49 #include "calls.h"
50 #include "emit-rtl.h"
51 #include "varasm.h"
52 #include "stmt.h"
53 #include "expr.h"
54 #include "stor-layout.h"
55 #include "dumpfile.h"
56 #include "bitmap.h"
57 #include "predict.h"
58 #include "dominance.h"
59 #include "basic-block.h"
60 #include "tree-ssa-alias.h"
61 #include "internal-fn.h"
62 #include "gimple-fold.h"
63 #include "gimple-expr.h"
64 #include "is-a.h"
65 #include "gimple.h"
66 #include "gimplify.h"
67 #include "gimple-iterator.h"
68 #include "gimple-ssa.h"
69 #include "tree-ssanames.h"
70 #include "tree-into-ssa.h"
71 #include "tree-dfa.h"
72 #include "tree-ssa.h"
73 #include "tree-ssa-propagate.h"
74 #include "target.h"
75 #include "hash-map.h"
76 #include "plugin-api.h"
77 #include "ipa-ref.h"
78 #include "cgraph.h"
79 #include "ipa-utils.h"
80 #include "gimple-pretty-print.h"
81 #include "tree-ssa-address.h"
82 #include "langhooks.h"
83 #include "gimplify-me.h"
84 #include "dbgcnt.h"
85 #include "builtins.h"
86 #include "output.h"
87 #include "tree-eh.h"
88 #include "gimple-match.h"
89 #include "tree-phinodes.h"
90 #include "ssa-iterators.h"
92 /* Return true when DECL can be referenced from current unit.
93 FROM_DECL (if non-null) specify constructor of variable DECL was taken from.
94 We can get declarations that are not possible to reference for various
95 reasons:
97 1) When analyzing C++ virtual tables.
98 C++ virtual tables do have known constructors even
99 when they are keyed to other compilation unit.
100 Those tables can contain pointers to methods and vars
101 in other units. Those methods have both STATIC and EXTERNAL
102 set.
103 2) In WHOPR mode devirtualization might lead to reference
104 to method that was partitioned elsehwere.
105 In this case we have static VAR_DECL or FUNCTION_DECL
106 that has no corresponding callgraph/varpool node
107 declaring the body.
108 3) COMDAT functions referred by external vtables that
109 we devirtualize only during final compilation stage.
110 At this time we already decided that we will not output
111 the function body and thus we can't reference the symbol
112 directly. */
114 static bool
115 can_refer_decl_in_current_unit_p (tree decl, tree from_decl)
117 varpool_node *vnode;
118 struct cgraph_node *node;
119 symtab_node *snode;
121 if (DECL_ABSTRACT_P (decl))
122 return false;
124 /* We are concerned only about static/external vars and functions. */
125 if ((!TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
126 || (TREE_CODE (decl) != VAR_DECL && TREE_CODE (decl) != FUNCTION_DECL))
127 return true;
129 /* Static objects can be referred only if they was not optimized out yet. */
130 if (!TREE_PUBLIC (decl) && !DECL_EXTERNAL (decl))
132 /* Before we start optimizing unreachable code we can be sure all
133 static objects are defined. */
134 if (symtab->function_flags_ready)
135 return true;
136 snode = symtab_node::get (decl);
137 if (!snode || !snode->definition)
138 return false;
139 node = dyn_cast <cgraph_node *> (snode);
140 return !node || !node->global.inlined_to;
143 /* We will later output the initializer, so we can refer to it.
144 So we are concerned only when DECL comes from initializer of
145 external var or var that has been optimized out. */
146 if (!from_decl
147 || TREE_CODE (from_decl) != VAR_DECL
148 || (!DECL_EXTERNAL (from_decl)
149 && (vnode = varpool_node::get (from_decl)) != NULL
150 && vnode->definition)
151 || (flag_ltrans
152 && (vnode = varpool_node::get (from_decl)) != NULL
153 && vnode->in_other_partition))
154 return true;
155 /* We are folding reference from external vtable. The vtable may reffer
156 to a symbol keyed to other compilation unit. The other compilation
157 unit may be in separate DSO and the symbol may be hidden. */
158 if (DECL_VISIBILITY_SPECIFIED (decl)
159 && DECL_EXTERNAL (decl)
160 && DECL_VISIBILITY (decl) != VISIBILITY_DEFAULT
161 && (!(snode = symtab_node::get (decl)) || !snode->in_other_partition))
162 return false;
163 /* When function is public, we always can introduce new reference.
164 Exception are the COMDAT functions where introducing a direct
165 reference imply need to include function body in the curren tunit. */
166 if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
167 return true;
168 /* We have COMDAT. We are going to check if we still have definition
169 or if the definition is going to be output in other partition.
170 Bypass this when gimplifying; all needed functions will be produced.
172 As observed in PR20991 for already optimized out comdat virtual functions
173 it may be tempting to not necessarily give up because the copy will be
174 output elsewhere when corresponding vtable is output.
175 This is however not possible - ABI specify that COMDATs are output in
176 units where they are used and when the other unit was compiled with LTO
177 it is possible that vtable was kept public while the function itself
178 was privatized. */
179 if (!symtab->function_flags_ready)
180 return true;
182 snode = symtab_node::get (decl);
183 if (!snode
184 || ((!snode->definition || DECL_EXTERNAL (decl))
185 && (!snode->in_other_partition
186 || (!snode->forced_by_abi && !snode->force_output))))
187 return false;
188 node = dyn_cast <cgraph_node *> (snode);
189 return !node || !node->global.inlined_to;
192 /* CVAL is value taken from DECL_INITIAL of variable. Try to transform it into
193 acceptable form for is_gimple_min_invariant.
194 FROM_DECL (if non-NULL) specify variable whose constructor contains CVAL. */
196 tree
197 canonicalize_constructor_val (tree cval, tree from_decl)
199 tree orig_cval = cval;
200 STRIP_NOPS (cval);
201 if (TREE_CODE (cval) == POINTER_PLUS_EXPR
202 && TREE_CODE (TREE_OPERAND (cval, 1)) == INTEGER_CST)
204 tree ptr = TREE_OPERAND (cval, 0);
205 if (is_gimple_min_invariant (ptr))
206 cval = build1_loc (EXPR_LOCATION (cval),
207 ADDR_EXPR, TREE_TYPE (ptr),
208 fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (ptr)),
209 ptr,
210 fold_convert (ptr_type_node,
211 TREE_OPERAND (cval, 1))));
213 if (TREE_CODE (cval) == ADDR_EXPR)
215 tree base = NULL_TREE;
216 if (TREE_CODE (TREE_OPERAND (cval, 0)) == COMPOUND_LITERAL_EXPR)
218 base = COMPOUND_LITERAL_EXPR_DECL (TREE_OPERAND (cval, 0));
219 if (base)
220 TREE_OPERAND (cval, 0) = base;
222 else
223 base = get_base_address (TREE_OPERAND (cval, 0));
224 if (!base)
225 return NULL_TREE;
227 if ((TREE_CODE (base) == VAR_DECL
228 || TREE_CODE (base) == FUNCTION_DECL)
229 && !can_refer_decl_in_current_unit_p (base, from_decl))
230 return NULL_TREE;
231 if (TREE_CODE (base) == VAR_DECL)
232 TREE_ADDRESSABLE (base) = 1;
233 else if (TREE_CODE (base) == FUNCTION_DECL)
235 /* Make sure we create a cgraph node for functions we'll reference.
236 They can be non-existent if the reference comes from an entry
237 of an external vtable for example. */
238 cgraph_node::get_create (base);
240 /* Fixup types in global initializers. */
241 if (TREE_TYPE (TREE_TYPE (cval)) != TREE_TYPE (TREE_OPERAND (cval, 0)))
242 cval = build_fold_addr_expr (TREE_OPERAND (cval, 0));
244 if (!useless_type_conversion_p (TREE_TYPE (orig_cval), TREE_TYPE (cval)))
245 cval = fold_convert (TREE_TYPE (orig_cval), cval);
246 return cval;
248 if (TREE_OVERFLOW_P (cval))
249 return drop_tree_overflow (cval);
250 return orig_cval;
253 /* If SYM is a constant variable with known value, return the value.
254 NULL_TREE is returned otherwise. */
256 tree
257 get_symbol_constant_value (tree sym)
259 tree val = ctor_for_folding (sym);
260 if (val != error_mark_node)
262 if (val)
264 val = canonicalize_constructor_val (unshare_expr (val), sym);
265 if (val && is_gimple_min_invariant (val))
266 return val;
267 else
268 return NULL_TREE;
270 /* Variables declared 'const' without an initializer
271 have zero as the initializer if they may not be
272 overridden at link or run time. */
273 if (!val
274 && is_gimple_reg_type (TREE_TYPE (sym)))
275 return build_zero_cst (TREE_TYPE (sym));
278 return NULL_TREE;
283 /* Subroutine of fold_stmt. We perform several simplifications of the
284 memory reference tree EXPR and make sure to re-gimplify them properly
285 after propagation of constant addresses. IS_LHS is true if the
286 reference is supposed to be an lvalue. */
288 static tree
289 maybe_fold_reference (tree expr, bool is_lhs)
291 tree result;
293 if ((TREE_CODE (expr) == VIEW_CONVERT_EXPR
294 || TREE_CODE (expr) == REALPART_EXPR
295 || TREE_CODE (expr) == IMAGPART_EXPR)
296 && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
297 return fold_unary_loc (EXPR_LOCATION (expr),
298 TREE_CODE (expr),
299 TREE_TYPE (expr),
300 TREE_OPERAND (expr, 0));
301 else if (TREE_CODE (expr) == BIT_FIELD_REF
302 && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
303 return fold_ternary_loc (EXPR_LOCATION (expr),
304 TREE_CODE (expr),
305 TREE_TYPE (expr),
306 TREE_OPERAND (expr, 0),
307 TREE_OPERAND (expr, 1),
308 TREE_OPERAND (expr, 2));
310 if (!is_lhs
311 && (result = fold_const_aggregate_ref (expr))
312 && is_gimple_min_invariant (result))
313 return result;
315 return NULL_TREE;
319 /* Attempt to fold an assignment statement pointed-to by SI. Returns a
320 replacement rhs for the statement or NULL_TREE if no simplification
321 could be made. It is assumed that the operands have been previously
322 folded. */
324 static tree
325 fold_gimple_assign (gimple_stmt_iterator *si)
327 gimple stmt = gsi_stmt (*si);
328 enum tree_code subcode = gimple_assign_rhs_code (stmt);
329 location_t loc = gimple_location (stmt);
331 tree result = NULL_TREE;
333 switch (get_gimple_rhs_class (subcode))
335 case GIMPLE_SINGLE_RHS:
337 tree rhs = gimple_assign_rhs1 (stmt);
339 if (TREE_CLOBBER_P (rhs))
340 return NULL_TREE;
342 if (REFERENCE_CLASS_P (rhs))
343 return maybe_fold_reference (rhs, false);
345 else if (TREE_CODE (rhs) == OBJ_TYPE_REF)
347 tree val = OBJ_TYPE_REF_EXPR (rhs);
348 if (is_gimple_min_invariant (val))
349 return val;
350 else if (flag_devirtualize && virtual_method_call_p (rhs))
352 bool final;
353 vec <cgraph_node *>targets
354 = possible_polymorphic_call_targets (rhs, stmt, &final);
355 if (final && targets.length () <= 1 && dbg_cnt (devirt))
357 if (dump_enabled_p ())
359 location_t loc = gimple_location_safe (stmt);
360 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
361 "resolving virtual function address "
362 "reference to function %s\n",
363 targets.length () == 1
364 ? targets[0]->name ()
365 : "NULL");
367 if (targets.length () == 1)
369 val = fold_convert (TREE_TYPE (val),
370 build_fold_addr_expr_loc
371 (loc, targets[0]->decl));
372 STRIP_USELESS_TYPE_CONVERSION (val);
374 else
375 /* We can not use __builtin_unreachable here because it
376 can not have address taken. */
377 val = build_int_cst (TREE_TYPE (val), 0);
378 return val;
383 else if (TREE_CODE (rhs) == ADDR_EXPR)
385 tree ref = TREE_OPERAND (rhs, 0);
386 tree tem = maybe_fold_reference (ref, true);
387 if (tem
388 && TREE_CODE (tem) == MEM_REF
389 && integer_zerop (TREE_OPERAND (tem, 1)))
390 result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (tem, 0));
391 else if (tem)
392 result = fold_convert (TREE_TYPE (rhs),
393 build_fold_addr_expr_loc (loc, tem));
394 else if (TREE_CODE (ref) == MEM_REF
395 && integer_zerop (TREE_OPERAND (ref, 1)))
396 result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (ref, 0));
399 else if (TREE_CODE (rhs) == CONSTRUCTOR
400 && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
401 && (CONSTRUCTOR_NELTS (rhs)
402 == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
404 /* Fold a constant vector CONSTRUCTOR to VECTOR_CST. */
405 unsigned i;
406 tree val;
408 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
409 if (TREE_CODE (val) != INTEGER_CST
410 && TREE_CODE (val) != REAL_CST
411 && TREE_CODE (val) != FIXED_CST)
412 return NULL_TREE;
414 return build_vector_from_ctor (TREE_TYPE (rhs),
415 CONSTRUCTOR_ELTS (rhs));
418 else if (DECL_P (rhs))
419 return get_symbol_constant_value (rhs);
421 /* If we couldn't fold the RHS, hand over to the generic
422 fold routines. */
423 if (result == NULL_TREE)
424 result = fold (rhs);
426 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR
427 that may have been added by fold, and "useless" type
428 conversions that might now be apparent due to propagation. */
429 STRIP_USELESS_TYPE_CONVERSION (result);
431 if (result != rhs && valid_gimple_rhs_p (result))
432 return result;
434 return NULL_TREE;
436 break;
438 case GIMPLE_UNARY_RHS:
439 break;
441 case GIMPLE_BINARY_RHS:
442 /* Try to canonicalize for boolean-typed X the comparisons
443 X == 0, X == 1, X != 0, and X != 1. */
444 if (gimple_assign_rhs_code (stmt) == EQ_EXPR
445 || gimple_assign_rhs_code (stmt) == NE_EXPR)
447 tree lhs = gimple_assign_lhs (stmt);
448 tree op1 = gimple_assign_rhs1 (stmt);
449 tree op2 = gimple_assign_rhs2 (stmt);
450 tree type = TREE_TYPE (op1);
452 /* Check whether the comparison operands are of the same boolean
453 type as the result type is.
454 Check that second operand is an integer-constant with value
455 one or zero. */
456 if (TREE_CODE (op2) == INTEGER_CST
457 && (integer_zerop (op2) || integer_onep (op2))
458 && useless_type_conversion_p (TREE_TYPE (lhs), type))
460 enum tree_code cmp_code = gimple_assign_rhs_code (stmt);
461 bool is_logical_not = false;
463 /* X == 0 and X != 1 is a logical-not.of X
464 X == 1 and X != 0 is X */
465 if ((cmp_code == EQ_EXPR && integer_zerop (op2))
466 || (cmp_code == NE_EXPR && integer_onep (op2)))
467 is_logical_not = true;
469 if (is_logical_not == false)
470 result = op1;
471 /* Only for one-bit precision typed X the transformation
472 !X -> ~X is valied. */
473 else if (TYPE_PRECISION (type) == 1)
474 result = build1_loc (gimple_location (stmt), BIT_NOT_EXPR,
475 type, op1);
476 /* Otherwise we use !X -> X ^ 1. */
477 else
478 result = build2_loc (gimple_location (stmt), BIT_XOR_EXPR,
479 type, op1, build_int_cst (type, 1));
484 if (!result)
485 result = fold_binary_loc (loc, subcode,
486 TREE_TYPE (gimple_assign_lhs (stmt)),
487 gimple_assign_rhs1 (stmt),
488 gimple_assign_rhs2 (stmt));
490 if (result)
492 STRIP_USELESS_TYPE_CONVERSION (result);
493 if (valid_gimple_rhs_p (result))
494 return result;
496 break;
498 case GIMPLE_TERNARY_RHS:
499 /* Try to fold a conditional expression. */
500 if (gimple_assign_rhs_code (stmt) == COND_EXPR)
502 tree op0 = gimple_assign_rhs1 (stmt);
503 tree tem;
504 bool set = false;
505 location_t cond_loc = gimple_location (stmt);
507 if (COMPARISON_CLASS_P (op0))
509 fold_defer_overflow_warnings ();
510 tem = fold_binary_loc (cond_loc,
511 TREE_CODE (op0), TREE_TYPE (op0),
512 TREE_OPERAND (op0, 0),
513 TREE_OPERAND (op0, 1));
514 /* This is actually a conditional expression, not a GIMPLE
515 conditional statement, however, the valid_gimple_rhs_p
516 test still applies. */
517 set = (tem && is_gimple_condexpr (tem)
518 && valid_gimple_rhs_p (tem));
519 fold_undefer_overflow_warnings (set, stmt, 0);
521 else if (is_gimple_min_invariant (op0))
523 tem = op0;
524 set = true;
526 else
527 return NULL_TREE;
529 if (set)
530 result = fold_build3_loc (cond_loc, COND_EXPR,
531 TREE_TYPE (gimple_assign_lhs (stmt)), tem,
532 gimple_assign_rhs2 (stmt),
533 gimple_assign_rhs3 (stmt));
536 if (!result)
537 result = fold_ternary_loc (loc, subcode,
538 TREE_TYPE (gimple_assign_lhs (stmt)),
539 gimple_assign_rhs1 (stmt),
540 gimple_assign_rhs2 (stmt),
541 gimple_assign_rhs3 (stmt));
543 if (result)
545 STRIP_USELESS_TYPE_CONVERSION (result);
546 if (valid_gimple_rhs_p (result))
547 return result;
549 break;
551 case GIMPLE_INVALID_RHS:
552 gcc_unreachable ();
555 return NULL_TREE;
558 /* Attempt to fold a conditional statement. Return true if any changes were
559 made. We only attempt to fold the condition expression, and do not perform
560 any transformation that would require alteration of the cfg. It is
561 assumed that the operands have been previously folded. */
563 static bool
564 fold_gimple_cond (gcond *stmt)
566 tree result = fold_binary_loc (gimple_location (stmt),
567 gimple_cond_code (stmt),
568 boolean_type_node,
569 gimple_cond_lhs (stmt),
570 gimple_cond_rhs (stmt));
572 if (result)
574 STRIP_USELESS_TYPE_CONVERSION (result);
575 if (is_gimple_condexpr (result) && valid_gimple_rhs_p (result))
577 gimple_cond_set_condition_from_tree (stmt, result);
578 return true;
582 return false;
586 /* Replace a statement at *SI_P with a sequence of statements in STMTS,
587 adjusting the replacement stmts location and virtual operands.
588 If the statement has a lhs the last stmt in the sequence is expected
589 to assign to that lhs. */
591 static void
592 gsi_replace_with_seq_vops (gimple_stmt_iterator *si_p, gimple_seq stmts)
594 gimple stmt = gsi_stmt (*si_p);
596 if (gimple_has_location (stmt))
597 annotate_all_with_location (stmts, gimple_location (stmt));
599 /* First iterate over the replacement statements backward, assigning
600 virtual operands to their defining statements. */
601 gimple laststore = NULL;
602 for (gimple_stmt_iterator i = gsi_last (stmts);
603 !gsi_end_p (i); gsi_prev (&i))
605 gimple new_stmt = gsi_stmt (i);
606 if ((gimple_assign_single_p (new_stmt)
607 && !is_gimple_reg (gimple_assign_lhs (new_stmt)))
608 || (is_gimple_call (new_stmt)
609 && (gimple_call_flags (new_stmt)
610 & (ECF_NOVOPS | ECF_PURE | ECF_CONST | ECF_NORETURN)) == 0))
612 tree vdef;
613 if (!laststore)
614 vdef = gimple_vdef (stmt);
615 else
616 vdef = make_ssa_name (gimple_vop (cfun), new_stmt);
617 gimple_set_vdef (new_stmt, vdef);
618 if (vdef && TREE_CODE (vdef) == SSA_NAME)
619 SSA_NAME_DEF_STMT (vdef) = new_stmt;
620 laststore = new_stmt;
624 /* Second iterate over the statements forward, assigning virtual
625 operands to their uses. */
626 tree reaching_vuse = gimple_vuse (stmt);
627 for (gimple_stmt_iterator i = gsi_start (stmts);
628 !gsi_end_p (i); gsi_next (&i))
630 gimple new_stmt = gsi_stmt (i);
631 /* If the new statement possibly has a VUSE, update it with exact SSA
632 name we know will reach this one. */
633 if (gimple_has_mem_ops (new_stmt))
634 gimple_set_vuse (new_stmt, reaching_vuse);
635 gimple_set_modified (new_stmt, true);
636 if (gimple_vdef (new_stmt))
637 reaching_vuse = gimple_vdef (new_stmt);
640 /* If the new sequence does not do a store release the virtual
641 definition of the original statement. */
642 if (reaching_vuse
643 && reaching_vuse == gimple_vuse (stmt))
645 tree vdef = gimple_vdef (stmt);
646 if (vdef
647 && TREE_CODE (vdef) == SSA_NAME)
649 unlink_stmt_vdef (stmt);
650 release_ssa_name (vdef);
654 /* Finally replace the original statement with the sequence. */
655 gsi_replace_with_seq (si_p, stmts, false);
658 /* Convert EXPR into a GIMPLE value suitable for substitution on the
659 RHS of an assignment. Insert the necessary statements before
660 iterator *SI_P. The statement at *SI_P, which must be a GIMPLE_CALL
661 is replaced. If the call is expected to produces a result, then it
662 is replaced by an assignment of the new RHS to the result variable.
663 If the result is to be ignored, then the call is replaced by a
664 GIMPLE_NOP. A proper VDEF chain is retained by making the first
665 VUSE and the last VDEF of the whole sequence be the same as the replaced
666 statement and using new SSA names for stores in between. */
668 void
669 gimplify_and_update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
671 tree lhs;
672 gimple stmt, new_stmt;
673 gimple_stmt_iterator i;
674 gimple_seq stmts = NULL;
676 stmt = gsi_stmt (*si_p);
678 gcc_assert (is_gimple_call (stmt));
680 push_gimplify_context (gimple_in_ssa_p (cfun));
682 lhs = gimple_call_lhs (stmt);
683 if (lhs == NULL_TREE)
685 gimplify_and_add (expr, &stmts);
686 /* We can end up with folding a memcpy of an empty class assignment
687 which gets optimized away by C++ gimplification. */
688 if (gimple_seq_empty_p (stmts))
690 pop_gimplify_context (NULL);
691 if (gimple_in_ssa_p (cfun))
693 unlink_stmt_vdef (stmt);
694 release_defs (stmt);
696 gsi_replace (si_p, gimple_build_nop (), true);
697 return;
700 else
702 tree tmp = get_initialized_tmp_var (expr, &stmts, NULL);
703 new_stmt = gimple_build_assign (lhs, tmp);
704 i = gsi_last (stmts);
705 gsi_insert_after_without_update (&i, new_stmt,
706 GSI_CONTINUE_LINKING);
709 pop_gimplify_context (NULL);
711 gsi_replace_with_seq_vops (si_p, stmts);
715 /* Replace the call at *GSI with the gimple value VAL. */
717 static void
718 replace_call_with_value (gimple_stmt_iterator *gsi, tree val)
720 gimple stmt = gsi_stmt (*gsi);
721 tree lhs = gimple_call_lhs (stmt);
722 gimple repl;
723 if (lhs)
725 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (val)))
726 val = fold_convert (TREE_TYPE (lhs), val);
727 repl = gimple_build_assign (lhs, val);
729 else
730 repl = gimple_build_nop ();
731 tree vdef = gimple_vdef (stmt);
732 if (vdef && TREE_CODE (vdef) == SSA_NAME)
734 unlink_stmt_vdef (stmt);
735 release_ssa_name (vdef);
737 gsi_replace (gsi, repl, true);
740 /* Replace the call at *GSI with the new call REPL and fold that
741 again. */
743 static void
744 replace_call_with_call_and_fold (gimple_stmt_iterator *gsi, gimple repl)
746 gimple stmt = gsi_stmt (*gsi);
747 gimple_call_set_lhs (repl, gimple_call_lhs (stmt));
748 gimple_set_location (repl, gimple_location (stmt));
749 if (gimple_vdef (stmt)
750 && TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
752 gimple_set_vdef (repl, gimple_vdef (stmt));
753 gimple_set_vuse (repl, gimple_vuse (stmt));
754 SSA_NAME_DEF_STMT (gimple_vdef (repl)) = repl;
756 gsi_replace (gsi, repl, true);
757 fold_stmt (gsi);
760 /* Return true if VAR is a VAR_DECL or a component thereof. */
762 static bool
763 var_decl_component_p (tree var)
765 tree inner = var;
766 while (handled_component_p (inner))
767 inner = TREE_OPERAND (inner, 0);
768 return SSA_VAR_P (inner);
771 /* Fold function call to builtin mem{{,p}cpy,move}. Return
772 NULL_TREE if no simplification can be made.
773 If ENDP is 0, return DEST (like memcpy).
774 If ENDP is 1, return DEST+LEN (like mempcpy).
775 If ENDP is 2, return DEST+LEN-1 (like stpcpy).
776 If ENDP is 3, return DEST, additionally *SRC and *DEST may overlap
777 (memmove). */
779 static bool
780 gimple_fold_builtin_memory_op (gimple_stmt_iterator *gsi,
781 tree dest, tree src, int endp)
783 gimple stmt = gsi_stmt (*gsi);
784 tree lhs = gimple_call_lhs (stmt);
785 tree len = gimple_call_arg (stmt, 2);
786 tree destvar, srcvar;
787 location_t loc = gimple_location (stmt);
789 /* If the LEN parameter is zero, return DEST. */
790 if (integer_zerop (len))
792 gimple repl;
793 if (gimple_call_lhs (stmt))
794 repl = gimple_build_assign (gimple_call_lhs (stmt), dest);
795 else
796 repl = gimple_build_nop ();
797 tree vdef = gimple_vdef (stmt);
798 if (vdef && TREE_CODE (vdef) == SSA_NAME)
800 unlink_stmt_vdef (stmt);
801 release_ssa_name (vdef);
803 gsi_replace (gsi, repl, true);
804 return true;
807 /* If SRC and DEST are the same (and not volatile), return
808 DEST{,+LEN,+LEN-1}. */
809 if (operand_equal_p (src, dest, 0))
811 unlink_stmt_vdef (stmt);
812 if (gimple_vdef (stmt) && TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
813 release_ssa_name (gimple_vdef (stmt));
814 if (!lhs)
816 gsi_replace (gsi, gimple_build_nop (), true);
817 return true;
819 goto done;
821 else
823 tree srctype, desttype;
824 unsigned int src_align, dest_align;
825 tree off0;
827 /* Build accesses at offset zero with a ref-all character type. */
828 off0 = build_int_cst (build_pointer_type_for_mode (char_type_node,
829 ptr_mode, true), 0);
831 /* If we can perform the copy efficiently with first doing all loads
832 and then all stores inline it that way. Currently efficiently
833 means that we can load all the memory into a single integer
834 register which is what MOVE_MAX gives us. */
835 src_align = get_pointer_alignment (src);
836 dest_align = get_pointer_alignment (dest);
837 if (tree_fits_uhwi_p (len)
838 && compare_tree_int (len, MOVE_MAX) <= 0
839 /* ??? Don't transform copies from strings with known length this
840 confuses the tree-ssa-strlen.c. This doesn't handle
841 the case in gcc.dg/strlenopt-8.c which is XFAILed for that
842 reason. */
843 && !c_strlen (src, 2))
845 unsigned ilen = tree_to_uhwi (len);
846 if (exact_log2 (ilen) != -1)
848 tree type = lang_hooks.types.type_for_size (ilen * 8, 1);
849 if (type
850 && TYPE_MODE (type) != BLKmode
851 && (GET_MODE_SIZE (TYPE_MODE (type)) * BITS_PER_UNIT
852 == ilen * 8)
853 /* If the destination pointer is not aligned we must be able
854 to emit an unaligned store. */
855 && (dest_align >= GET_MODE_ALIGNMENT (TYPE_MODE (type))
856 || !SLOW_UNALIGNED_ACCESS (TYPE_MODE (type), dest_align)))
858 tree srctype = type;
859 tree desttype = type;
860 if (src_align < GET_MODE_ALIGNMENT (TYPE_MODE (type)))
861 srctype = build_aligned_type (type, src_align);
862 tree srcmem = fold_build2 (MEM_REF, srctype, src, off0);
863 tree tem = fold_const_aggregate_ref (srcmem);
864 if (tem)
865 srcmem = tem;
866 else if (src_align < GET_MODE_ALIGNMENT (TYPE_MODE (type))
867 && SLOW_UNALIGNED_ACCESS (TYPE_MODE (type),
868 src_align))
869 srcmem = NULL_TREE;
870 if (srcmem)
872 gimple new_stmt;
873 if (is_gimple_reg_type (TREE_TYPE (srcmem)))
875 new_stmt = gimple_build_assign (NULL_TREE, srcmem);
876 if (gimple_in_ssa_p (cfun))
877 srcmem = make_ssa_name (TREE_TYPE (srcmem),
878 new_stmt);
879 else
880 srcmem = create_tmp_reg (TREE_TYPE (srcmem));
881 gimple_assign_set_lhs (new_stmt, srcmem);
882 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
883 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
885 if (dest_align < GET_MODE_ALIGNMENT (TYPE_MODE (type)))
886 desttype = build_aligned_type (type, dest_align);
887 new_stmt
888 = gimple_build_assign (fold_build2 (MEM_REF, desttype,
889 dest, off0),
890 srcmem);
891 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
892 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
893 if (gimple_vdef (new_stmt)
894 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
895 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
896 if (!lhs)
898 gsi_replace (gsi, new_stmt, true);
899 return true;
901 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
902 goto done;
908 if (endp == 3)
910 /* Both DEST and SRC must be pointer types.
911 ??? This is what old code did. Is the testing for pointer types
912 really mandatory?
914 If either SRC is readonly or length is 1, we can use memcpy. */
915 if (!dest_align || !src_align)
916 return false;
917 if (readonly_data_expr (src)
918 || (tree_fits_uhwi_p (len)
919 && (MIN (src_align, dest_align) / BITS_PER_UNIT
920 >= tree_to_uhwi (len))))
922 tree fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
923 if (!fn)
924 return false;
925 gimple_call_set_fndecl (stmt, fn);
926 gimple_call_set_arg (stmt, 0, dest);
927 gimple_call_set_arg (stmt, 1, src);
928 fold_stmt (gsi);
929 return true;
932 /* If *src and *dest can't overlap, optimize into memcpy as well. */
933 if (TREE_CODE (src) == ADDR_EXPR
934 && TREE_CODE (dest) == ADDR_EXPR)
936 tree src_base, dest_base, fn;
937 HOST_WIDE_INT src_offset = 0, dest_offset = 0;
938 HOST_WIDE_INT size = -1;
939 HOST_WIDE_INT maxsize = -1;
941 srcvar = TREE_OPERAND (src, 0);
942 src_base = get_ref_base_and_extent (srcvar, &src_offset,
943 &size, &maxsize);
944 destvar = TREE_OPERAND (dest, 0);
945 dest_base = get_ref_base_and_extent (destvar, &dest_offset,
946 &size, &maxsize);
947 if (tree_fits_uhwi_p (len))
948 maxsize = tree_to_uhwi (len);
949 else
950 maxsize = -1;
951 src_offset /= BITS_PER_UNIT;
952 dest_offset /= BITS_PER_UNIT;
953 if (SSA_VAR_P (src_base)
954 && SSA_VAR_P (dest_base))
956 if (operand_equal_p (src_base, dest_base, 0)
957 && ranges_overlap_p (src_offset, maxsize,
958 dest_offset, maxsize))
959 return false;
961 else if (TREE_CODE (src_base) == MEM_REF
962 && TREE_CODE (dest_base) == MEM_REF)
964 if (! operand_equal_p (TREE_OPERAND (src_base, 0),
965 TREE_OPERAND (dest_base, 0), 0))
966 return false;
967 offset_int off = mem_ref_offset (src_base) + src_offset;
968 if (!wi::fits_shwi_p (off))
969 return false;
970 src_offset = off.to_shwi ();
972 off = mem_ref_offset (dest_base) + dest_offset;
973 if (!wi::fits_shwi_p (off))
974 return false;
975 dest_offset = off.to_shwi ();
976 if (ranges_overlap_p (src_offset, maxsize,
977 dest_offset, maxsize))
978 return false;
980 else
981 return false;
983 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
984 if (!fn)
985 return false;
986 gimple_call_set_fndecl (stmt, fn);
987 gimple_call_set_arg (stmt, 0, dest);
988 gimple_call_set_arg (stmt, 1, src);
989 fold_stmt (gsi);
990 return true;
993 /* If the destination and source do not alias optimize into
994 memcpy as well. */
995 if ((is_gimple_min_invariant (dest)
996 || TREE_CODE (dest) == SSA_NAME)
997 && (is_gimple_min_invariant (src)
998 || TREE_CODE (src) == SSA_NAME))
1000 ao_ref destr, srcr;
1001 ao_ref_init_from_ptr_and_size (&destr, dest, len);
1002 ao_ref_init_from_ptr_and_size (&srcr, src, len);
1003 if (!refs_may_alias_p_1 (&destr, &srcr, false))
1005 tree fn;
1006 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1007 if (!fn)
1008 return false;
1009 gimple_call_set_fndecl (stmt, fn);
1010 gimple_call_set_arg (stmt, 0, dest);
1011 gimple_call_set_arg (stmt, 1, src);
1012 fold_stmt (gsi);
1013 return true;
1017 return false;
1020 if (!tree_fits_shwi_p (len))
1021 return false;
1022 /* FIXME:
1023 This logic lose for arguments like (type *)malloc (sizeof (type)),
1024 since we strip the casts of up to VOID return value from malloc.
1025 Perhaps we ought to inherit type from non-VOID argument here? */
1026 STRIP_NOPS (src);
1027 STRIP_NOPS (dest);
1028 if (!POINTER_TYPE_P (TREE_TYPE (src))
1029 || !POINTER_TYPE_P (TREE_TYPE (dest)))
1030 return false;
1031 /* In the following try to find a type that is most natural to be
1032 used for the memcpy source and destination and that allows
1033 the most optimization when memcpy is turned into a plain assignment
1034 using that type. In theory we could always use a char[len] type
1035 but that only gains us that the destination and source possibly
1036 no longer will have their address taken. */
1037 /* As we fold (void *)(p + CST) to (void *)p + CST undo this here. */
1038 if (TREE_CODE (src) == POINTER_PLUS_EXPR)
1040 tree tem = TREE_OPERAND (src, 0);
1041 STRIP_NOPS (tem);
1042 if (tem != TREE_OPERAND (src, 0))
1043 src = build1 (NOP_EXPR, TREE_TYPE (tem), src);
1045 if (TREE_CODE (dest) == POINTER_PLUS_EXPR)
1047 tree tem = TREE_OPERAND (dest, 0);
1048 STRIP_NOPS (tem);
1049 if (tem != TREE_OPERAND (dest, 0))
1050 dest = build1 (NOP_EXPR, TREE_TYPE (tem), dest);
1052 srctype = TREE_TYPE (TREE_TYPE (src));
1053 if (TREE_CODE (srctype) == ARRAY_TYPE
1054 && !tree_int_cst_equal (TYPE_SIZE_UNIT (srctype), len))
1056 srctype = TREE_TYPE (srctype);
1057 STRIP_NOPS (src);
1058 src = build1 (NOP_EXPR, build_pointer_type (srctype), src);
1060 desttype = TREE_TYPE (TREE_TYPE (dest));
1061 if (TREE_CODE (desttype) == ARRAY_TYPE
1062 && !tree_int_cst_equal (TYPE_SIZE_UNIT (desttype), len))
1064 desttype = TREE_TYPE (desttype);
1065 STRIP_NOPS (dest);
1066 dest = build1 (NOP_EXPR, build_pointer_type (desttype), dest);
1068 if (TREE_ADDRESSABLE (srctype)
1069 || TREE_ADDRESSABLE (desttype))
1070 return false;
1072 /* Make sure we are not copying using a floating-point mode or
1073 a type whose size possibly does not match its precision. */
1074 if (FLOAT_MODE_P (TYPE_MODE (desttype))
1075 || TREE_CODE (desttype) == BOOLEAN_TYPE
1076 || TREE_CODE (desttype) == ENUMERAL_TYPE)
1077 desttype = bitwise_type_for_mode (TYPE_MODE (desttype));
1078 if (FLOAT_MODE_P (TYPE_MODE (srctype))
1079 || TREE_CODE (srctype) == BOOLEAN_TYPE
1080 || TREE_CODE (srctype) == ENUMERAL_TYPE)
1081 srctype = bitwise_type_for_mode (TYPE_MODE (srctype));
1082 if (!srctype)
1083 srctype = desttype;
1084 if (!desttype)
1085 desttype = srctype;
1086 if (!srctype)
1087 return false;
1089 src_align = get_pointer_alignment (src);
1090 dest_align = get_pointer_alignment (dest);
1091 if (dest_align < TYPE_ALIGN (desttype)
1092 || src_align < TYPE_ALIGN (srctype))
1093 return false;
1095 destvar = dest;
1096 STRIP_NOPS (destvar);
1097 if (TREE_CODE (destvar) == ADDR_EXPR
1098 && var_decl_component_p (TREE_OPERAND (destvar, 0))
1099 && tree_int_cst_equal (TYPE_SIZE_UNIT (desttype), len))
1100 destvar = fold_build2 (MEM_REF, desttype, destvar, off0);
1101 else
1102 destvar = NULL_TREE;
1104 srcvar = src;
1105 STRIP_NOPS (srcvar);
1106 if (TREE_CODE (srcvar) == ADDR_EXPR
1107 && var_decl_component_p (TREE_OPERAND (srcvar, 0))
1108 && tree_int_cst_equal (TYPE_SIZE_UNIT (srctype), len))
1110 if (!destvar
1111 || src_align >= TYPE_ALIGN (desttype))
1112 srcvar = fold_build2 (MEM_REF, destvar ? desttype : srctype,
1113 srcvar, off0);
1114 else if (!STRICT_ALIGNMENT)
1116 srctype = build_aligned_type (TYPE_MAIN_VARIANT (desttype),
1117 src_align);
1118 srcvar = fold_build2 (MEM_REF, srctype, srcvar, off0);
1120 else
1121 srcvar = NULL_TREE;
1123 else
1124 srcvar = NULL_TREE;
1126 if (srcvar == NULL_TREE && destvar == NULL_TREE)
1127 return false;
1129 if (srcvar == NULL_TREE)
1131 STRIP_NOPS (src);
1132 if (src_align >= TYPE_ALIGN (desttype))
1133 srcvar = fold_build2 (MEM_REF, desttype, src, off0);
1134 else
1136 if (STRICT_ALIGNMENT)
1137 return false;
1138 srctype = build_aligned_type (TYPE_MAIN_VARIANT (desttype),
1139 src_align);
1140 srcvar = fold_build2 (MEM_REF, srctype, src, off0);
1143 else if (destvar == NULL_TREE)
1145 STRIP_NOPS (dest);
1146 if (dest_align >= TYPE_ALIGN (srctype))
1147 destvar = fold_build2 (MEM_REF, srctype, dest, off0);
1148 else
1150 if (STRICT_ALIGNMENT)
1151 return false;
1152 desttype = build_aligned_type (TYPE_MAIN_VARIANT (srctype),
1153 dest_align);
1154 destvar = fold_build2 (MEM_REF, desttype, dest, off0);
1158 gimple new_stmt;
1159 if (is_gimple_reg_type (TREE_TYPE (srcvar)))
1161 new_stmt = gimple_build_assign (NULL_TREE, srcvar);
1162 if (gimple_in_ssa_p (cfun))
1163 srcvar = make_ssa_name (TREE_TYPE (srcvar), new_stmt);
1164 else
1165 srcvar = create_tmp_reg (TREE_TYPE (srcvar));
1166 gimple_assign_set_lhs (new_stmt, srcvar);
1167 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
1168 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1170 new_stmt = gimple_build_assign (destvar, srcvar);
1171 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
1172 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
1173 if (gimple_vdef (new_stmt)
1174 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
1175 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
1176 if (!lhs)
1178 gsi_replace (gsi, new_stmt, true);
1179 return true;
1181 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1184 done:
1185 if (endp == 0 || endp == 3)
1186 len = NULL_TREE;
1187 else if (endp == 2)
1188 len = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (len), len,
1189 ssize_int (1));
1190 if (endp == 2 || endp == 1)
1191 dest = fold_build_pointer_plus_loc (loc, dest, len);
1193 dest = force_gimple_operand_gsi (gsi, dest, false, NULL_TREE, true,
1194 GSI_SAME_STMT);
1195 gimple repl = gimple_build_assign (lhs, dest);
1196 gsi_replace (gsi, repl, true);
1197 return true;
1200 /* Fold function call to builtin memset or bzero at *GSI setting the
1201 memory of size LEN to VAL. Return whether a simplification was made. */
1203 static bool
1204 gimple_fold_builtin_memset (gimple_stmt_iterator *gsi, tree c, tree len)
1206 gimple stmt = gsi_stmt (*gsi);
1207 tree etype;
1208 unsigned HOST_WIDE_INT length, cval;
1210 /* If the LEN parameter is zero, return DEST. */
1211 if (integer_zerop (len))
1213 replace_call_with_value (gsi, gimple_call_arg (stmt, 0));
1214 return true;
1217 if (! tree_fits_uhwi_p (len))
1218 return false;
1220 if (TREE_CODE (c) != INTEGER_CST)
1221 return false;
1223 tree dest = gimple_call_arg (stmt, 0);
1224 tree var = dest;
1225 if (TREE_CODE (var) != ADDR_EXPR)
1226 return false;
1228 var = TREE_OPERAND (var, 0);
1229 if (TREE_THIS_VOLATILE (var))
1230 return false;
1232 etype = TREE_TYPE (var);
1233 if (TREE_CODE (etype) == ARRAY_TYPE)
1234 etype = TREE_TYPE (etype);
1236 if (!INTEGRAL_TYPE_P (etype)
1237 && !POINTER_TYPE_P (etype))
1238 return NULL_TREE;
1240 if (! var_decl_component_p (var))
1241 return NULL_TREE;
1243 length = tree_to_uhwi (len);
1244 if (GET_MODE_SIZE (TYPE_MODE (etype)) != length
1245 || get_pointer_alignment (dest) / BITS_PER_UNIT < length)
1246 return NULL_TREE;
1248 if (length > HOST_BITS_PER_WIDE_INT / BITS_PER_UNIT)
1249 return NULL_TREE;
1251 if (integer_zerop (c))
1252 cval = 0;
1253 else
1255 if (CHAR_BIT != 8 || BITS_PER_UNIT != 8 || HOST_BITS_PER_WIDE_INT > 64)
1256 return NULL_TREE;
1258 cval = TREE_INT_CST_LOW (c);
1259 cval &= 0xff;
1260 cval |= cval << 8;
1261 cval |= cval << 16;
1262 cval |= (cval << 31) << 1;
1265 var = fold_build2 (MEM_REF, etype, dest, build_int_cst (ptr_type_node, 0));
1266 gimple store = gimple_build_assign (var, build_int_cst_type (etype, cval));
1267 gimple_set_vuse (store, gimple_vuse (stmt));
1268 tree vdef = gimple_vdef (stmt);
1269 if (vdef && TREE_CODE (vdef) == SSA_NAME)
1271 gimple_set_vdef (store, gimple_vdef (stmt));
1272 SSA_NAME_DEF_STMT (gimple_vdef (stmt)) = store;
1274 gsi_insert_before (gsi, store, GSI_SAME_STMT);
1275 if (gimple_call_lhs (stmt))
1277 gimple asgn = gimple_build_assign (gimple_call_lhs (stmt), dest);
1278 gsi_replace (gsi, asgn, true);
1280 else
1282 gimple_stmt_iterator gsi2 = *gsi;
1283 gsi_prev (gsi);
1284 gsi_remove (&gsi2, true);
1287 return true;
1291 /* Return the string length, maximum string length or maximum value of
1292 ARG in LENGTH.
1293 If ARG is an SSA name variable, follow its use-def chains. If LENGTH
1294 is not NULL and, for TYPE == 0, its value is not equal to the length
1295 we determine or if we are unable to determine the length or value,
1296 return false. VISITED is a bitmap of visited variables.
1297 TYPE is 0 if string length should be returned, 1 for maximum string
1298 length and 2 for maximum value ARG can have. */
1300 static bool
1301 get_maxval_strlen (tree arg, tree *length, bitmap *visited, int type)
1303 tree var, val;
1304 gimple def_stmt;
1306 if (TREE_CODE (arg) != SSA_NAME)
1308 /* We can end up with &(*iftmp_1)[0] here as well, so handle it. */
1309 if (TREE_CODE (arg) == ADDR_EXPR
1310 && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
1311 && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
1313 tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
1314 if (TREE_CODE (aop0) == INDIRECT_REF
1315 && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
1316 return get_maxval_strlen (TREE_OPERAND (aop0, 0),
1317 length, visited, type);
1320 if (type == 2)
1322 val = arg;
1323 if (TREE_CODE (val) != INTEGER_CST
1324 || tree_int_cst_sgn (val) < 0)
1325 return false;
1327 else
1328 val = c_strlen (arg, 1);
1329 if (!val)
1330 return false;
1332 if (*length)
1334 if (type > 0)
1336 if (TREE_CODE (*length) != INTEGER_CST
1337 || TREE_CODE (val) != INTEGER_CST)
1338 return false;
1340 if (tree_int_cst_lt (*length, val))
1341 *length = val;
1342 return true;
1344 else if (simple_cst_equal (val, *length) != 1)
1345 return false;
1348 *length = val;
1349 return true;
1352 /* If ARG is registered for SSA update we cannot look at its defining
1353 statement. */
1354 if (name_registered_for_update_p (arg))
1355 return false;
1357 /* If we were already here, break the infinite cycle. */
1358 if (!*visited)
1359 *visited = BITMAP_ALLOC (NULL);
1360 if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (arg)))
1361 return true;
1363 var = arg;
1364 def_stmt = SSA_NAME_DEF_STMT (var);
1366 switch (gimple_code (def_stmt))
1368 case GIMPLE_ASSIGN:
1369 /* The RHS of the statement defining VAR must either have a
1370 constant length or come from another SSA_NAME with a constant
1371 length. */
1372 if (gimple_assign_single_p (def_stmt)
1373 || gimple_assign_unary_nop_p (def_stmt))
1375 tree rhs = gimple_assign_rhs1 (def_stmt);
1376 return get_maxval_strlen (rhs, length, visited, type);
1378 else if (gimple_assign_rhs_code (def_stmt) == COND_EXPR)
1380 tree op2 = gimple_assign_rhs2 (def_stmt);
1381 tree op3 = gimple_assign_rhs3 (def_stmt);
1382 return get_maxval_strlen (op2, length, visited, type)
1383 && get_maxval_strlen (op3, length, visited, type);
1385 return false;
1387 case GIMPLE_PHI:
1389 /* All the arguments of the PHI node must have the same constant
1390 length. */
1391 unsigned i;
1393 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1395 tree arg = gimple_phi_arg (def_stmt, i)->def;
1397 /* If this PHI has itself as an argument, we cannot
1398 determine the string length of this argument. However,
1399 if we can find a constant string length for the other
1400 PHI args then we can still be sure that this is a
1401 constant string length. So be optimistic and just
1402 continue with the next argument. */
1403 if (arg == gimple_phi_result (def_stmt))
1404 continue;
1406 if (!get_maxval_strlen (arg, length, visited, type))
1407 return false;
1410 return true;
1412 default:
1413 return false;
1417 tree
1418 get_maxval_strlen (tree arg, int type)
1420 bitmap visited = NULL;
1421 tree len = NULL_TREE;
1422 if (!get_maxval_strlen (arg, &len, &visited, type))
1423 len = NULL_TREE;
1424 if (visited)
1425 BITMAP_FREE (visited);
1427 return len;
1431 /* Fold function call to builtin strcpy with arguments DEST and SRC.
1432 If LEN is not NULL, it represents the length of the string to be
1433 copied. Return NULL_TREE if no simplification can be made. */
1435 static bool
1436 gimple_fold_builtin_strcpy (gimple_stmt_iterator *gsi,
1437 tree dest, tree src)
1439 location_t loc = gimple_location (gsi_stmt (*gsi));
1440 tree fn;
1442 /* If SRC and DEST are the same (and not volatile), return DEST. */
1443 if (operand_equal_p (src, dest, 0))
1445 replace_call_with_value (gsi, dest);
1446 return true;
1449 if (optimize_function_for_size_p (cfun))
1450 return false;
1452 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1453 if (!fn)
1454 return false;
1456 tree len = get_maxval_strlen (src, 0);
1457 if (!len)
1458 return false;
1460 len = fold_convert_loc (loc, size_type_node, len);
1461 len = size_binop_loc (loc, PLUS_EXPR, len, build_int_cst (size_type_node, 1));
1462 len = force_gimple_operand_gsi (gsi, len, true,
1463 NULL_TREE, true, GSI_SAME_STMT);
1464 gimple repl = gimple_build_call (fn, 3, dest, src, len);
1465 replace_call_with_call_and_fold (gsi, repl);
1466 return true;
1469 /* Fold function call to builtin strncpy with arguments DEST, SRC, and LEN.
1470 If SLEN is not NULL, it represents the length of the source string.
1471 Return NULL_TREE if no simplification can be made. */
1473 static bool
1474 gimple_fold_builtin_strncpy (gimple_stmt_iterator *gsi,
1475 tree dest, tree src, tree len)
1477 location_t loc = gimple_location (gsi_stmt (*gsi));
1478 tree fn;
1480 /* If the LEN parameter is zero, return DEST. */
1481 if (integer_zerop (len))
1483 replace_call_with_value (gsi, dest);
1484 return true;
1487 /* We can't compare slen with len as constants below if len is not a
1488 constant. */
1489 if (TREE_CODE (len) != INTEGER_CST)
1490 return false;
1492 /* Now, we must be passed a constant src ptr parameter. */
1493 tree slen = get_maxval_strlen (src, 0);
1494 if (!slen || TREE_CODE (slen) != INTEGER_CST)
1495 return false;
1497 slen = size_binop_loc (loc, PLUS_EXPR, slen, ssize_int (1));
1499 /* We do not support simplification of this case, though we do
1500 support it when expanding trees into RTL. */
1501 /* FIXME: generate a call to __builtin_memset. */
1502 if (tree_int_cst_lt (slen, len))
1503 return false;
1505 /* OK transform into builtin memcpy. */
1506 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1507 if (!fn)
1508 return false;
1510 len = fold_convert_loc (loc, size_type_node, len);
1511 len = force_gimple_operand_gsi (gsi, len, true,
1512 NULL_TREE, true, GSI_SAME_STMT);
1513 gimple repl = gimple_build_call (fn, 3, dest, src, len);
1514 replace_call_with_call_and_fold (gsi, repl);
1515 return true;
1518 /* Simplify a call to the strcat builtin. DST and SRC are the arguments
1519 to the call.
1521 Return NULL_TREE if no simplification was possible, otherwise return the
1522 simplified form of the call as a tree.
1524 The simplified form may be a constant or other expression which
1525 computes the same value, but in a more efficient manner (including
1526 calls to other builtin functions).
1528 The call may contain arguments which need to be evaluated, but
1529 which are not useful to determine the result of the call. In
1530 this case we return a chain of COMPOUND_EXPRs. The LHS of each
1531 COMPOUND_EXPR will be an argument which must be evaluated.
1532 COMPOUND_EXPRs are chained through their RHS. The RHS of the last
1533 COMPOUND_EXPR in the chain will contain the tree for the simplified
1534 form of the builtin function call. */
1536 static bool
1537 gimple_fold_builtin_strcat (gimple_stmt_iterator *gsi, tree dst, tree src)
1539 gimple stmt = gsi_stmt (*gsi);
1540 location_t loc = gimple_location (stmt);
1542 const char *p = c_getstr (src);
1544 /* If the string length is zero, return the dst parameter. */
1545 if (p && *p == '\0')
1547 replace_call_with_value (gsi, dst);
1548 return true;
1551 if (!optimize_bb_for_speed_p (gimple_bb (stmt)))
1552 return false;
1554 /* See if we can store by pieces into (dst + strlen(dst)). */
1555 tree newdst;
1556 tree strlen_fn = builtin_decl_implicit (BUILT_IN_STRLEN);
1557 tree memcpy_fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1559 if (!strlen_fn || !memcpy_fn)
1560 return false;
1562 /* If the length of the source string isn't computable don't
1563 split strcat into strlen and memcpy. */
1564 tree len = get_maxval_strlen (src, 0);
1565 if (! len)
1566 return false;
1568 /* Create strlen (dst). */
1569 gimple_seq stmts = NULL, stmts2;
1570 gimple repl = gimple_build_call (strlen_fn, 1, dst);
1571 gimple_set_location (repl, loc);
1572 if (gimple_in_ssa_p (cfun))
1573 newdst = make_ssa_name (size_type_node);
1574 else
1575 newdst = create_tmp_reg (size_type_node);
1576 gimple_call_set_lhs (repl, newdst);
1577 gimple_seq_add_stmt_without_update (&stmts, repl);
1579 /* Create (dst p+ strlen (dst)). */
1580 newdst = fold_build_pointer_plus_loc (loc, dst, newdst);
1581 newdst = force_gimple_operand (newdst, &stmts2, true, NULL_TREE);
1582 gimple_seq_add_seq_without_update (&stmts, stmts2);
1584 len = fold_convert_loc (loc, size_type_node, len);
1585 len = size_binop_loc (loc, PLUS_EXPR, len,
1586 build_int_cst (size_type_node, 1));
1587 len = force_gimple_operand (len, &stmts2, true, NULL_TREE);
1588 gimple_seq_add_seq_without_update (&stmts, stmts2);
1590 repl = gimple_build_call (memcpy_fn, 3, newdst, src, len);
1591 gimple_seq_add_stmt_without_update (&stmts, repl);
1592 if (gimple_call_lhs (stmt))
1594 repl = gimple_build_assign (gimple_call_lhs (stmt), dst);
1595 gimple_seq_add_stmt_without_update (&stmts, repl);
1596 gsi_replace_with_seq_vops (gsi, stmts);
1597 /* gsi now points at the assignment to the lhs, get a
1598 stmt iterator to the memcpy call.
1599 ??? We can't use gsi_for_stmt as that doesn't work when the
1600 CFG isn't built yet. */
1601 gimple_stmt_iterator gsi2 = *gsi;
1602 gsi_prev (&gsi2);
1603 fold_stmt (&gsi2);
1605 else
1607 gsi_replace_with_seq_vops (gsi, stmts);
1608 fold_stmt (gsi);
1610 return true;
1613 /* Fold a call to the __strcat_chk builtin FNDECL. DEST, SRC, and SIZE
1614 are the arguments to the call. */
1616 static bool
1617 gimple_fold_builtin_strcat_chk (gimple_stmt_iterator *gsi)
1619 gimple stmt = gsi_stmt (*gsi);
1620 tree dest = gimple_call_arg (stmt, 0);
1621 tree src = gimple_call_arg (stmt, 1);
1622 tree size = gimple_call_arg (stmt, 2);
1623 tree fn;
1624 const char *p;
1627 p = c_getstr (src);
1628 /* If the SRC parameter is "", return DEST. */
1629 if (p && *p == '\0')
1631 replace_call_with_value (gsi, dest);
1632 return true;
1635 if (! tree_fits_uhwi_p (size) || ! integer_all_onesp (size))
1636 return false;
1638 /* If __builtin_strcat_chk is used, assume strcat is available. */
1639 fn = builtin_decl_explicit (BUILT_IN_STRCAT);
1640 if (!fn)
1641 return false;
1643 gimple repl = gimple_build_call (fn, 2, dest, src);
1644 replace_call_with_call_and_fold (gsi, repl);
1645 return true;
1648 /* Simplify a call to the strncat builtin. */
1650 static bool
1651 gimple_fold_builtin_strncat (gimple_stmt_iterator *gsi)
1653 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
1654 tree dst = gimple_call_arg (stmt, 0);
1655 tree src = gimple_call_arg (stmt, 1);
1656 tree len = gimple_call_arg (stmt, 2);
1658 const char *p = c_getstr (src);
1660 /* If the requested length is zero, or the src parameter string
1661 length is zero, return the dst parameter. */
1662 if (integer_zerop (len) || (p && *p == '\0'))
1664 replace_call_with_value (gsi, dst);
1665 return true;
1668 /* If the requested len is greater than or equal to the string
1669 length, call strcat. */
1670 if (TREE_CODE (len) == INTEGER_CST && p
1671 && compare_tree_int (len, strlen (p)) >= 0)
1673 tree fn = builtin_decl_implicit (BUILT_IN_STRCAT);
1675 /* If the replacement _DECL isn't initialized, don't do the
1676 transformation. */
1677 if (!fn)
1678 return false;
1680 gcall *repl = gimple_build_call (fn, 2, dst, src);
1681 replace_call_with_call_and_fold (gsi, repl);
1682 return true;
1685 return false;
1688 /* Fold a call to the __strncat_chk builtin with arguments DEST, SRC,
1689 LEN, and SIZE. */
1691 static bool
1692 gimple_fold_builtin_strncat_chk (gimple_stmt_iterator *gsi)
1694 gimple stmt = gsi_stmt (*gsi);
1695 tree dest = gimple_call_arg (stmt, 0);
1696 tree src = gimple_call_arg (stmt, 1);
1697 tree len = gimple_call_arg (stmt, 2);
1698 tree size = gimple_call_arg (stmt, 3);
1699 tree fn;
1700 const char *p;
1702 p = c_getstr (src);
1703 /* If the SRC parameter is "" or if LEN is 0, return DEST. */
1704 if ((p && *p == '\0')
1705 || integer_zerop (len))
1707 replace_call_with_value (gsi, dest);
1708 return true;
1711 if (! tree_fits_uhwi_p (size))
1712 return false;
1714 if (! integer_all_onesp (size))
1716 tree src_len = c_strlen (src, 1);
1717 if (src_len
1718 && tree_fits_uhwi_p (src_len)
1719 && tree_fits_uhwi_p (len)
1720 && ! tree_int_cst_lt (len, src_len))
1722 /* If LEN >= strlen (SRC), optimize into __strcat_chk. */
1723 fn = builtin_decl_explicit (BUILT_IN_STRCAT_CHK);
1724 if (!fn)
1725 return false;
1727 gimple repl = gimple_build_call (fn, 3, dest, src, size);
1728 replace_call_with_call_and_fold (gsi, repl);
1729 return true;
1731 return false;
1734 /* If __builtin_strncat_chk is used, assume strncat is available. */
1735 fn = builtin_decl_explicit (BUILT_IN_STRNCAT);
1736 if (!fn)
1737 return false;
1739 gimple repl = gimple_build_call (fn, 3, dest, src, len);
1740 replace_call_with_call_and_fold (gsi, repl);
1741 return true;
1744 /* Fold a call to the fputs builtin. ARG0 and ARG1 are the arguments
1745 to the call. IGNORE is true if the value returned
1746 by the builtin will be ignored. UNLOCKED is true is true if this
1747 actually a call to fputs_unlocked. If LEN in non-NULL, it represents
1748 the known length of the string. Return NULL_TREE if no simplification
1749 was possible. */
1751 static bool
1752 gimple_fold_builtin_fputs (gimple_stmt_iterator *gsi,
1753 tree arg0, tree arg1,
1754 bool unlocked)
1756 gimple stmt = gsi_stmt (*gsi);
1758 /* If we're using an unlocked function, assume the other unlocked
1759 functions exist explicitly. */
1760 tree const fn_fputc = (unlocked
1761 ? builtin_decl_explicit (BUILT_IN_FPUTC_UNLOCKED)
1762 : builtin_decl_implicit (BUILT_IN_FPUTC));
1763 tree const fn_fwrite = (unlocked
1764 ? builtin_decl_explicit (BUILT_IN_FWRITE_UNLOCKED)
1765 : builtin_decl_implicit (BUILT_IN_FWRITE));
1767 /* If the return value is used, don't do the transformation. */
1768 if (gimple_call_lhs (stmt))
1769 return false;
1771 /* Get the length of the string passed to fputs. If the length
1772 can't be determined, punt. */
1773 tree len = get_maxval_strlen (arg0, 0);
1774 if (!len
1775 || TREE_CODE (len) != INTEGER_CST)
1776 return false;
1778 switch (compare_tree_int (len, 1))
1780 case -1: /* length is 0, delete the call entirely . */
1781 replace_call_with_value (gsi, integer_zero_node);
1782 return true;
1784 case 0: /* length is 1, call fputc. */
1786 const char *p = c_getstr (arg0);
1787 if (p != NULL)
1789 if (!fn_fputc)
1790 return false;
1792 gimple repl = gimple_build_call (fn_fputc, 2,
1793 build_int_cst
1794 (integer_type_node, p[0]), arg1);
1795 replace_call_with_call_and_fold (gsi, repl);
1796 return true;
1799 /* FALLTHROUGH */
1800 case 1: /* length is greater than 1, call fwrite. */
1802 /* If optimizing for size keep fputs. */
1803 if (optimize_function_for_size_p (cfun))
1804 return false;
1805 /* New argument list transforming fputs(string, stream) to
1806 fwrite(string, 1, len, stream). */
1807 if (!fn_fwrite)
1808 return false;
1810 gimple repl = gimple_build_call (fn_fwrite, 4, arg0,
1811 size_one_node, len, arg1);
1812 replace_call_with_call_and_fold (gsi, repl);
1813 return true;
1815 default:
1816 gcc_unreachable ();
1818 return false;
1821 /* Fold a call to the __mem{cpy,pcpy,move,set}_chk builtin.
1822 DEST, SRC, LEN, and SIZE are the arguments to the call.
1823 IGNORE is true, if return value can be ignored. FCODE is the BUILT_IN_*
1824 code of the builtin. If MAXLEN is not NULL, it is maximum length
1825 passed as third argument. */
1827 static bool
1828 gimple_fold_builtin_memory_chk (gimple_stmt_iterator *gsi,
1829 tree dest, tree src, tree len, tree size,
1830 enum built_in_function fcode)
1832 gimple stmt = gsi_stmt (*gsi);
1833 location_t loc = gimple_location (stmt);
1834 bool ignore = gimple_call_lhs (stmt) == NULL_TREE;
1835 tree fn;
1837 /* If SRC and DEST are the same (and not volatile), return DEST
1838 (resp. DEST+LEN for __mempcpy_chk). */
1839 if (fcode != BUILT_IN_MEMSET_CHK && operand_equal_p (src, dest, 0))
1841 if (fcode != BUILT_IN_MEMPCPY_CHK)
1843 replace_call_with_value (gsi, dest);
1844 return true;
1846 else
1848 tree temp = fold_build_pointer_plus_loc (loc, dest, len);
1849 temp = force_gimple_operand_gsi (gsi, temp,
1850 false, NULL_TREE, true,
1851 GSI_SAME_STMT);
1852 replace_call_with_value (gsi, temp);
1853 return true;
1857 if (! tree_fits_uhwi_p (size))
1858 return false;
1860 tree maxlen = get_maxval_strlen (len, 2);
1861 if (! integer_all_onesp (size))
1863 if (! tree_fits_uhwi_p (len))
1865 /* If LEN is not constant, try MAXLEN too.
1866 For MAXLEN only allow optimizing into non-_ocs function
1867 if SIZE is >= MAXLEN, never convert to __ocs_fail (). */
1868 if (maxlen == NULL_TREE || ! tree_fits_uhwi_p (maxlen))
1870 if (fcode == BUILT_IN_MEMPCPY_CHK && ignore)
1872 /* (void) __mempcpy_chk () can be optimized into
1873 (void) __memcpy_chk (). */
1874 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1875 if (!fn)
1876 return false;
1878 gimple repl = gimple_build_call (fn, 4, dest, src, len, size);
1879 replace_call_with_call_and_fold (gsi, repl);
1880 return true;
1882 return false;
1885 else
1886 maxlen = len;
1888 if (tree_int_cst_lt (size, maxlen))
1889 return false;
1892 fn = NULL_TREE;
1893 /* If __builtin_mem{cpy,pcpy,move,set}_chk is used, assume
1894 mem{cpy,pcpy,move,set} is available. */
1895 switch (fcode)
1897 case BUILT_IN_MEMCPY_CHK:
1898 fn = builtin_decl_explicit (BUILT_IN_MEMCPY);
1899 break;
1900 case BUILT_IN_MEMPCPY_CHK:
1901 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY);
1902 break;
1903 case BUILT_IN_MEMMOVE_CHK:
1904 fn = builtin_decl_explicit (BUILT_IN_MEMMOVE);
1905 break;
1906 case BUILT_IN_MEMSET_CHK:
1907 fn = builtin_decl_explicit (BUILT_IN_MEMSET);
1908 break;
1909 default:
1910 break;
1913 if (!fn)
1914 return false;
1916 gimple repl = gimple_build_call (fn, 3, dest, src, len);
1917 replace_call_with_call_and_fold (gsi, repl);
1918 return true;
1921 /* Fold a call to the __st[rp]cpy_chk builtin.
1922 DEST, SRC, and SIZE are the arguments to the call.
1923 IGNORE is true if return value can be ignored. FCODE is the BUILT_IN_*
1924 code of the builtin. If MAXLEN is not NULL, it is maximum length of
1925 strings passed as second argument. */
1927 static bool
1928 gimple_fold_builtin_stxcpy_chk (gimple_stmt_iterator *gsi,
1929 tree dest,
1930 tree src, tree size,
1931 enum built_in_function fcode)
1933 gimple stmt = gsi_stmt (*gsi);
1934 location_t loc = gimple_location (stmt);
1935 bool ignore = gimple_call_lhs (stmt) == NULL_TREE;
1936 tree len, fn;
1938 /* If SRC and DEST are the same (and not volatile), return DEST. */
1939 if (fcode == BUILT_IN_STRCPY_CHK && operand_equal_p (src, dest, 0))
1941 replace_call_with_value (gsi, dest);
1942 return true;
1945 if (! tree_fits_uhwi_p (size))
1946 return false;
1948 tree maxlen = get_maxval_strlen (src, 1);
1949 if (! integer_all_onesp (size))
1951 len = c_strlen (src, 1);
1952 if (! len || ! tree_fits_uhwi_p (len))
1954 /* If LEN is not constant, try MAXLEN too.
1955 For MAXLEN only allow optimizing into non-_ocs function
1956 if SIZE is >= MAXLEN, never convert to __ocs_fail (). */
1957 if (maxlen == NULL_TREE || ! tree_fits_uhwi_p (maxlen))
1959 if (fcode == BUILT_IN_STPCPY_CHK)
1961 if (! ignore)
1962 return false;
1964 /* If return value of __stpcpy_chk is ignored,
1965 optimize into __strcpy_chk. */
1966 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1967 if (!fn)
1968 return false;
1970 gimple repl = gimple_build_call (fn, 3, dest, src, size);
1971 replace_call_with_call_and_fold (gsi, repl);
1972 return true;
1975 if (! len || TREE_SIDE_EFFECTS (len))
1976 return false;
1978 /* If c_strlen returned something, but not a constant,
1979 transform __strcpy_chk into __memcpy_chk. */
1980 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1981 if (!fn)
1982 return false;
1984 len = fold_convert_loc (loc, size_type_node, len);
1985 len = size_binop_loc (loc, PLUS_EXPR, len,
1986 build_int_cst (size_type_node, 1));
1987 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE,
1988 true, GSI_SAME_STMT);
1989 gimple repl = gimple_build_call (fn, 4, dest, src, len, size);
1990 replace_call_with_call_and_fold (gsi, repl);
1991 return true;
1994 else
1995 maxlen = len;
1997 if (! tree_int_cst_lt (maxlen, size))
1998 return false;
2001 /* If __builtin_st{r,p}cpy_chk is used, assume st{r,p}cpy is available. */
2002 fn = builtin_decl_explicit (fcode == BUILT_IN_STPCPY_CHK
2003 ? BUILT_IN_STPCPY : BUILT_IN_STRCPY);
2004 if (!fn)
2005 return false;
2007 gimple repl = gimple_build_call (fn, 2, dest, src);
2008 replace_call_with_call_and_fold (gsi, repl);
2009 return true;
2012 /* Fold a call to the __st{r,p}ncpy_chk builtin. DEST, SRC, LEN, and SIZE
2013 are the arguments to the call. If MAXLEN is not NULL, it is maximum
2014 length passed as third argument. IGNORE is true if return value can be
2015 ignored. FCODE is the BUILT_IN_* code of the builtin. */
2017 static bool
2018 gimple_fold_builtin_stxncpy_chk (gimple_stmt_iterator *gsi,
2019 tree dest, tree src,
2020 tree len, tree size,
2021 enum built_in_function fcode)
2023 gimple stmt = gsi_stmt (*gsi);
2024 bool ignore = gimple_call_lhs (stmt) == NULL_TREE;
2025 tree fn;
2027 if (fcode == BUILT_IN_STPNCPY_CHK && ignore)
2029 /* If return value of __stpncpy_chk is ignored,
2030 optimize into __strncpy_chk. */
2031 fn = builtin_decl_explicit (BUILT_IN_STRNCPY_CHK);
2032 if (fn)
2034 gimple repl = gimple_build_call (fn, 4, dest, src, len, size);
2035 replace_call_with_call_and_fold (gsi, repl);
2036 return true;
2040 if (! tree_fits_uhwi_p (size))
2041 return false;
2043 tree maxlen = get_maxval_strlen (len, 2);
2044 if (! integer_all_onesp (size))
2046 if (! tree_fits_uhwi_p (len))
2048 /* If LEN is not constant, try MAXLEN too.
2049 For MAXLEN only allow optimizing into non-_ocs function
2050 if SIZE is >= MAXLEN, never convert to __ocs_fail (). */
2051 if (maxlen == NULL_TREE || ! tree_fits_uhwi_p (maxlen))
2052 return false;
2054 else
2055 maxlen = len;
2057 if (tree_int_cst_lt (size, maxlen))
2058 return false;
2061 /* If __builtin_st{r,p}ncpy_chk is used, assume st{r,p}ncpy is available. */
2062 fn = builtin_decl_explicit (fcode == BUILT_IN_STPNCPY_CHK
2063 ? BUILT_IN_STPNCPY : BUILT_IN_STRNCPY);
2064 if (!fn)
2065 return false;
2067 gimple repl = gimple_build_call (fn, 3, dest, src, len);
2068 replace_call_with_call_and_fold (gsi, repl);
2069 return true;
2072 /* Fold function call to builtin stpcpy with arguments DEST and SRC.
2073 Return NULL_TREE if no simplification can be made. */
2075 static bool
2076 gimple_fold_builtin_stpcpy (gimple_stmt_iterator *gsi)
2078 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
2079 location_t loc = gimple_location (stmt);
2080 tree dest = gimple_call_arg (stmt, 0);
2081 tree src = gimple_call_arg (stmt, 1);
2082 tree fn, len, lenp1;
2084 /* If the result is unused, replace stpcpy with strcpy. */
2085 if (gimple_call_lhs (stmt) == NULL_TREE)
2087 tree fn = builtin_decl_implicit (BUILT_IN_STRCPY);
2088 if (!fn)
2089 return false;
2090 gimple_call_set_fndecl (stmt, fn);
2091 fold_stmt (gsi);
2092 return true;
2095 len = c_strlen (src, 1);
2096 if (!len
2097 || TREE_CODE (len) != INTEGER_CST)
2098 return false;
2100 if (optimize_function_for_size_p (cfun)
2101 /* If length is zero it's small enough. */
2102 && !integer_zerop (len))
2103 return false;
2105 /* If the source has a known length replace stpcpy with memcpy. */
2106 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
2107 if (!fn)
2108 return false;
2110 gimple_seq stmts = NULL;
2111 tree tem = gimple_convert (&stmts, loc, size_type_node, len);
2112 lenp1 = gimple_build (&stmts, loc, PLUS_EXPR, size_type_node,
2113 tem, build_int_cst (size_type_node, 1));
2114 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
2115 gcall *repl = gimple_build_call (fn, 3, dest, src, lenp1);
2116 gimple_set_vuse (repl, gimple_vuse (stmt));
2117 gimple_set_vdef (repl, gimple_vdef (stmt));
2118 if (gimple_vdef (repl)
2119 && TREE_CODE (gimple_vdef (repl)) == SSA_NAME)
2120 SSA_NAME_DEF_STMT (gimple_vdef (repl)) = repl;
2121 gsi_insert_before (gsi, repl, GSI_SAME_STMT);
2122 /* Replace the result with dest + len. */
2123 stmts = NULL;
2124 tem = gimple_convert (&stmts, loc, sizetype, len);
2125 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
2126 gassign *ret = gimple_build_assign (gimple_call_lhs (stmt),
2127 POINTER_PLUS_EXPR, dest, tem);
2128 gsi_replace (gsi, ret, true);
2129 /* Finally fold the memcpy call. */
2130 gimple_stmt_iterator gsi2 = *gsi;
2131 gsi_prev (&gsi2);
2132 fold_stmt (&gsi2);
2133 return true;
2136 /* Fold a call EXP to {,v}snprintf having NARGS passed as ARGS. Return
2137 NULL_TREE if a normal call should be emitted rather than expanding
2138 the function inline. FCODE is either BUILT_IN_SNPRINTF_CHK or
2139 BUILT_IN_VSNPRINTF_CHK. If MAXLEN is not NULL, it is maximum length
2140 passed as second argument. */
2142 static bool
2143 gimple_fold_builtin_snprintf_chk (gimple_stmt_iterator *gsi,
2144 enum built_in_function fcode)
2146 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
2147 tree dest, size, len, fn, fmt, flag;
2148 const char *fmt_str;
2150 /* Verify the required arguments in the original call. */
2151 if (gimple_call_num_args (stmt) < 5)
2152 return false;
2154 dest = gimple_call_arg (stmt, 0);
2155 len = gimple_call_arg (stmt, 1);
2156 flag = gimple_call_arg (stmt, 2);
2157 size = gimple_call_arg (stmt, 3);
2158 fmt = gimple_call_arg (stmt, 4);
2160 if (! tree_fits_uhwi_p (size))
2161 return false;
2163 if (! integer_all_onesp (size))
2165 tree maxlen = get_maxval_strlen (len, 2);
2166 if (! tree_fits_uhwi_p (len))
2168 /* If LEN is not constant, try MAXLEN too.
2169 For MAXLEN only allow optimizing into non-_ocs function
2170 if SIZE is >= MAXLEN, never convert to __ocs_fail (). */
2171 if (maxlen == NULL_TREE || ! tree_fits_uhwi_p (maxlen))
2172 return false;
2174 else
2175 maxlen = len;
2177 if (tree_int_cst_lt (size, maxlen))
2178 return false;
2181 if (!init_target_chars ())
2182 return false;
2184 /* Only convert __{,v}snprintf_chk to {,v}snprintf if flag is 0
2185 or if format doesn't contain % chars or is "%s". */
2186 if (! integer_zerop (flag))
2188 fmt_str = c_getstr (fmt);
2189 if (fmt_str == NULL)
2190 return false;
2191 if (strchr (fmt_str, target_percent) != NULL
2192 && strcmp (fmt_str, target_percent_s))
2193 return false;
2196 /* If __builtin_{,v}snprintf_chk is used, assume {,v}snprintf is
2197 available. */
2198 fn = builtin_decl_explicit (fcode == BUILT_IN_VSNPRINTF_CHK
2199 ? BUILT_IN_VSNPRINTF : BUILT_IN_SNPRINTF);
2200 if (!fn)
2201 return false;
2203 /* Replace the called function and the first 5 argument by 3 retaining
2204 trailing varargs. */
2205 gimple_call_set_fndecl (stmt, fn);
2206 gimple_call_set_fntype (stmt, TREE_TYPE (fn));
2207 gimple_call_set_arg (stmt, 0, dest);
2208 gimple_call_set_arg (stmt, 1, len);
2209 gimple_call_set_arg (stmt, 2, fmt);
2210 for (unsigned i = 3; i < gimple_call_num_args (stmt) - 2; ++i)
2211 gimple_call_set_arg (stmt, i, gimple_call_arg (stmt, i + 2));
2212 gimple_set_num_ops (stmt, gimple_num_ops (stmt) - 2);
2213 fold_stmt (gsi);
2214 return true;
2217 /* Fold a call EXP to __{,v}sprintf_chk having NARGS passed as ARGS.
2218 Return NULL_TREE if a normal call should be emitted rather than
2219 expanding the function inline. FCODE is either BUILT_IN_SPRINTF_CHK
2220 or BUILT_IN_VSPRINTF_CHK. */
2222 static bool
2223 gimple_fold_builtin_sprintf_chk (gimple_stmt_iterator *gsi,
2224 enum built_in_function fcode)
2226 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
2227 tree dest, size, len, fn, fmt, flag;
2228 const char *fmt_str;
2229 unsigned nargs = gimple_call_num_args (stmt);
2231 /* Verify the required arguments in the original call. */
2232 if (nargs < 4)
2233 return false;
2234 dest = gimple_call_arg (stmt, 0);
2235 flag = gimple_call_arg (stmt, 1);
2236 size = gimple_call_arg (stmt, 2);
2237 fmt = gimple_call_arg (stmt, 3);
2239 if (! tree_fits_uhwi_p (size))
2240 return false;
2242 len = NULL_TREE;
2244 if (!init_target_chars ())
2245 return false;
2247 /* Check whether the format is a literal string constant. */
2248 fmt_str = c_getstr (fmt);
2249 if (fmt_str != NULL)
2251 /* If the format doesn't contain % args or %%, we know the size. */
2252 if (strchr (fmt_str, target_percent) == 0)
2254 if (fcode != BUILT_IN_SPRINTF_CHK || nargs == 4)
2255 len = build_int_cstu (size_type_node, strlen (fmt_str));
2257 /* If the format is "%s" and first ... argument is a string literal,
2258 we know the size too. */
2259 else if (fcode == BUILT_IN_SPRINTF_CHK
2260 && strcmp (fmt_str, target_percent_s) == 0)
2262 tree arg;
2264 if (nargs == 5)
2266 arg = gimple_call_arg (stmt, 4);
2267 if (POINTER_TYPE_P (TREE_TYPE (arg)))
2269 len = c_strlen (arg, 1);
2270 if (! len || ! tree_fits_uhwi_p (len))
2271 len = NULL_TREE;
2277 if (! integer_all_onesp (size))
2279 if (! len || ! tree_int_cst_lt (len, size))
2280 return false;
2283 /* Only convert __{,v}sprintf_chk to {,v}sprintf if flag is 0
2284 or if format doesn't contain % chars or is "%s". */
2285 if (! integer_zerop (flag))
2287 if (fmt_str == NULL)
2288 return false;
2289 if (strchr (fmt_str, target_percent) != NULL
2290 && strcmp (fmt_str, target_percent_s))
2291 return false;
2294 /* If __builtin_{,v}sprintf_chk is used, assume {,v}sprintf is available. */
2295 fn = builtin_decl_explicit (fcode == BUILT_IN_VSPRINTF_CHK
2296 ? BUILT_IN_VSPRINTF : BUILT_IN_SPRINTF);
2297 if (!fn)
2298 return false;
2300 /* Replace the called function and the first 4 argument by 2 retaining
2301 trailing varargs. */
2302 gimple_call_set_fndecl (stmt, fn);
2303 gimple_call_set_fntype (stmt, TREE_TYPE (fn));
2304 gimple_call_set_arg (stmt, 0, dest);
2305 gimple_call_set_arg (stmt, 1, fmt);
2306 for (unsigned i = 2; i < gimple_call_num_args (stmt) - 2; ++i)
2307 gimple_call_set_arg (stmt, i, gimple_call_arg (stmt, i + 2));
2308 gimple_set_num_ops (stmt, gimple_num_ops (stmt) - 2);
2309 fold_stmt (gsi);
2310 return true;
2313 /* Simplify a call to the sprintf builtin with arguments DEST, FMT, and ORIG.
2314 ORIG may be null if this is a 2-argument call. We don't attempt to
2315 simplify calls with more than 3 arguments.
2317 Return NULL_TREE if no simplification was possible, otherwise return the
2318 simplified form of the call as a tree. If IGNORED is true, it means that
2319 the caller does not use the returned value of the function. */
2321 static bool
2322 gimple_fold_builtin_sprintf (gimple_stmt_iterator *gsi)
2324 gimple stmt = gsi_stmt (*gsi);
2325 tree dest = gimple_call_arg (stmt, 0);
2326 tree fmt = gimple_call_arg (stmt, 1);
2327 tree orig = NULL_TREE;
2328 const char *fmt_str = NULL;
2330 /* Verify the required arguments in the original call. We deal with two
2331 types of sprintf() calls: 'sprintf (str, fmt)' and
2332 'sprintf (dest, "%s", orig)'. */
2333 if (gimple_call_num_args (stmt) > 3)
2334 return false;
2336 if (gimple_call_num_args (stmt) == 3)
2337 orig = gimple_call_arg (stmt, 2);
2339 /* Check whether the format is a literal string constant. */
2340 fmt_str = c_getstr (fmt);
2341 if (fmt_str == NULL)
2342 return false;
2344 if (!init_target_chars ())
2345 return false;
2347 /* If the format doesn't contain % args or %%, use strcpy. */
2348 if (strchr (fmt_str, target_percent) == NULL)
2350 tree fn = builtin_decl_implicit (BUILT_IN_STRCPY);
2352 if (!fn)
2353 return false;
2355 /* Don't optimize sprintf (buf, "abc", ptr++). */
2356 if (orig)
2357 return false;
2359 /* Convert sprintf (str, fmt) into strcpy (str, fmt) when
2360 'format' is known to contain no % formats. */
2361 gimple_seq stmts = NULL;
2362 gimple repl = gimple_build_call (fn, 2, dest, fmt);
2363 gimple_seq_add_stmt_without_update (&stmts, repl);
2364 if (gimple_call_lhs (stmt))
2366 repl = gimple_build_assign (gimple_call_lhs (stmt),
2367 build_int_cst (integer_type_node,
2368 strlen (fmt_str)));
2369 gimple_seq_add_stmt_without_update (&stmts, repl);
2370 gsi_replace_with_seq_vops (gsi, stmts);
2371 /* gsi now points at the assignment to the lhs, get a
2372 stmt iterator to the memcpy call.
2373 ??? We can't use gsi_for_stmt as that doesn't work when the
2374 CFG isn't built yet. */
2375 gimple_stmt_iterator gsi2 = *gsi;
2376 gsi_prev (&gsi2);
2377 fold_stmt (&gsi2);
2379 else
2381 gsi_replace_with_seq_vops (gsi, stmts);
2382 fold_stmt (gsi);
2384 return true;
2387 /* If the format is "%s", use strcpy if the result isn't used. */
2388 else if (fmt_str && strcmp (fmt_str, target_percent_s) == 0)
2390 tree fn;
2391 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
2393 if (!fn)
2394 return false;
2396 /* Don't crash on sprintf (str1, "%s"). */
2397 if (!orig)
2398 return false;
2400 tree orig_len = NULL_TREE;
2401 if (gimple_call_lhs (stmt))
2403 orig_len = get_maxval_strlen (orig, 0);
2404 if (!orig_len)
2405 return false;
2408 /* Convert sprintf (str1, "%s", str2) into strcpy (str1, str2). */
2409 gimple_seq stmts = NULL;
2410 gimple repl = gimple_build_call (fn, 2, dest, orig);
2411 gimple_seq_add_stmt_without_update (&stmts, repl);
2412 if (gimple_call_lhs (stmt))
2414 if (!useless_type_conversion_p (integer_type_node,
2415 TREE_TYPE (orig_len)))
2416 orig_len = fold_convert (integer_type_node, orig_len);
2417 repl = gimple_build_assign (gimple_call_lhs (stmt), orig_len);
2418 gimple_seq_add_stmt_without_update (&stmts, repl);
2419 gsi_replace_with_seq_vops (gsi, stmts);
2420 /* gsi now points at the assignment to the lhs, get a
2421 stmt iterator to the memcpy call.
2422 ??? We can't use gsi_for_stmt as that doesn't work when the
2423 CFG isn't built yet. */
2424 gimple_stmt_iterator gsi2 = *gsi;
2425 gsi_prev (&gsi2);
2426 fold_stmt (&gsi2);
2428 else
2430 gsi_replace_with_seq_vops (gsi, stmts);
2431 fold_stmt (gsi);
2433 return true;
2435 return false;
2438 /* Simplify a call to the snprintf builtin with arguments DEST, DESTSIZE,
2439 FMT, and ORIG. ORIG may be null if this is a 3-argument call. We don't
2440 attempt to simplify calls with more than 4 arguments.
2442 Return NULL_TREE if no simplification was possible, otherwise return the
2443 simplified form of the call as a tree. If IGNORED is true, it means that
2444 the caller does not use the returned value of the function. */
2446 static bool
2447 gimple_fold_builtin_snprintf (gimple_stmt_iterator *gsi)
2449 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
2450 tree dest = gimple_call_arg (stmt, 0);
2451 tree destsize = gimple_call_arg (stmt, 1);
2452 tree fmt = gimple_call_arg (stmt, 2);
2453 tree orig = NULL_TREE;
2454 const char *fmt_str = NULL;
2456 if (gimple_call_num_args (stmt) > 4)
2457 return false;
2459 if (gimple_call_num_args (stmt) == 4)
2460 orig = gimple_call_arg (stmt, 3);
2462 if (!tree_fits_uhwi_p (destsize))
2463 return false;
2464 unsigned HOST_WIDE_INT destlen = tree_to_uhwi (destsize);
2466 /* Check whether the format is a literal string constant. */
2467 fmt_str = c_getstr (fmt);
2468 if (fmt_str == NULL)
2469 return false;
2471 if (!init_target_chars ())
2472 return false;
2474 /* If the format doesn't contain % args or %%, use strcpy. */
2475 if (strchr (fmt_str, target_percent) == NULL)
2477 tree fn = builtin_decl_implicit (BUILT_IN_STRCPY);
2478 if (!fn)
2479 return false;
2481 /* Don't optimize snprintf (buf, 4, "abc", ptr++). */
2482 if (orig)
2483 return false;
2485 /* We could expand this as
2486 memcpy (str, fmt, cst - 1); str[cst - 1] = '\0';
2487 or to
2488 memcpy (str, fmt_with_nul_at_cstm1, cst);
2489 but in the former case that might increase code size
2490 and in the latter case grow .rodata section too much.
2491 So punt for now. */
2492 size_t len = strlen (fmt_str);
2493 if (len >= destlen)
2494 return false;
2496 gimple_seq stmts = NULL;
2497 gimple repl = gimple_build_call (fn, 2, dest, fmt);
2498 gimple_seq_add_stmt_without_update (&stmts, repl);
2499 if (gimple_call_lhs (stmt))
2501 repl = gimple_build_assign (gimple_call_lhs (stmt),
2502 build_int_cst (integer_type_node, len));
2503 gimple_seq_add_stmt_without_update (&stmts, repl);
2504 gsi_replace_with_seq_vops (gsi, stmts);
2505 /* gsi now points at the assignment to the lhs, get a
2506 stmt iterator to the memcpy call.
2507 ??? We can't use gsi_for_stmt as that doesn't work when the
2508 CFG isn't built yet. */
2509 gimple_stmt_iterator gsi2 = *gsi;
2510 gsi_prev (&gsi2);
2511 fold_stmt (&gsi2);
2513 else
2515 gsi_replace_with_seq_vops (gsi, stmts);
2516 fold_stmt (gsi);
2518 return true;
2521 /* If the format is "%s", use strcpy if the result isn't used. */
2522 else if (fmt_str && strcmp (fmt_str, target_percent_s) == 0)
2524 tree fn = builtin_decl_implicit (BUILT_IN_STRCPY);
2525 if (!fn)
2526 return false;
2528 /* Don't crash on snprintf (str1, cst, "%s"). */
2529 if (!orig)
2530 return false;
2532 tree orig_len = get_maxval_strlen (orig, 0);
2533 if (!orig_len)
2534 return false;
2536 /* We could expand this as
2537 memcpy (str1, str2, cst - 1); str1[cst - 1] = '\0';
2538 or to
2539 memcpy (str1, str2_with_nul_at_cstm1, cst);
2540 but in the former case that might increase code size
2541 and in the latter case grow .rodata section too much.
2542 So punt for now. */
2543 if (compare_tree_int (orig_len, destlen) >= 0)
2544 return false;
2546 /* Convert snprintf (str1, cst, "%s", str2) into
2547 strcpy (str1, str2) if strlen (str2) < cst. */
2548 gimple_seq stmts = NULL;
2549 gimple repl = gimple_build_call (fn, 2, dest, orig);
2550 gimple_seq_add_stmt_without_update (&stmts, repl);
2551 if (gimple_call_lhs (stmt))
2553 if (!useless_type_conversion_p (integer_type_node,
2554 TREE_TYPE (orig_len)))
2555 orig_len = fold_convert (integer_type_node, orig_len);
2556 repl = gimple_build_assign (gimple_call_lhs (stmt), orig_len);
2557 gimple_seq_add_stmt_without_update (&stmts, repl);
2558 gsi_replace_with_seq_vops (gsi, stmts);
2559 /* gsi now points at the assignment to the lhs, get a
2560 stmt iterator to the memcpy call.
2561 ??? We can't use gsi_for_stmt as that doesn't work when the
2562 CFG isn't built yet. */
2563 gimple_stmt_iterator gsi2 = *gsi;
2564 gsi_prev (&gsi2);
2565 fold_stmt (&gsi2);
2567 else
2569 gsi_replace_with_seq_vops (gsi, stmts);
2570 fold_stmt (gsi);
2572 return true;
2574 return false;
2577 /* Fold a call to the {,v}fprintf{,_unlocked} and __{,v}printf_chk builtins.
2578 FP, FMT, and ARG are the arguments to the call. We don't fold calls with
2579 more than 3 arguments, and ARG may be null in the 2-argument case.
2581 Return NULL_TREE if no simplification was possible, otherwise return the
2582 simplified form of the call as a tree. FCODE is the BUILT_IN_*
2583 code of the function to be simplified. */
2585 static bool
2586 gimple_fold_builtin_fprintf (gimple_stmt_iterator *gsi,
2587 tree fp, tree fmt, tree arg,
2588 enum built_in_function fcode)
2590 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
2591 tree fn_fputc, fn_fputs;
2592 const char *fmt_str = NULL;
2594 /* If the return value is used, don't do the transformation. */
2595 if (gimple_call_lhs (stmt) != NULL_TREE)
2596 return false;
2598 /* Check whether the format is a literal string constant. */
2599 fmt_str = c_getstr (fmt);
2600 if (fmt_str == NULL)
2601 return false;
2603 if (fcode == BUILT_IN_FPRINTF_UNLOCKED)
2605 /* If we're using an unlocked function, assume the other
2606 unlocked functions exist explicitly. */
2607 fn_fputc = builtin_decl_explicit (BUILT_IN_FPUTC_UNLOCKED);
2608 fn_fputs = builtin_decl_explicit (BUILT_IN_FPUTS_UNLOCKED);
2610 else
2612 fn_fputc = builtin_decl_implicit (BUILT_IN_FPUTC);
2613 fn_fputs = builtin_decl_implicit (BUILT_IN_FPUTS);
2616 if (!init_target_chars ())
2617 return false;
2619 /* If the format doesn't contain % args or %%, use strcpy. */
2620 if (strchr (fmt_str, target_percent) == NULL)
2622 if (fcode != BUILT_IN_VFPRINTF && fcode != BUILT_IN_VFPRINTF_CHK
2623 && arg)
2624 return false;
2626 /* If the format specifier was "", fprintf does nothing. */
2627 if (fmt_str[0] == '\0')
2629 replace_call_with_value (gsi, NULL_TREE);
2630 return true;
2633 /* When "string" doesn't contain %, replace all cases of
2634 fprintf (fp, string) with fputs (string, fp). The fputs
2635 builtin will take care of special cases like length == 1. */
2636 if (fn_fputs)
2638 gcall *repl = gimple_build_call (fn_fputs, 2, fmt, fp);
2639 replace_call_with_call_and_fold (gsi, repl);
2640 return true;
2644 /* The other optimizations can be done only on the non-va_list variants. */
2645 else if (fcode == BUILT_IN_VFPRINTF || fcode == BUILT_IN_VFPRINTF_CHK)
2646 return false;
2648 /* If the format specifier was "%s", call __builtin_fputs (arg, fp). */
2649 else if (strcmp (fmt_str, target_percent_s) == 0)
2651 if (!arg || ! POINTER_TYPE_P (TREE_TYPE (arg)))
2652 return false;
2653 if (fn_fputs)
2655 gcall *repl = gimple_build_call (fn_fputs, 2, arg, fp);
2656 replace_call_with_call_and_fold (gsi, repl);
2657 return true;
2661 /* If the format specifier was "%c", call __builtin_fputc (arg, fp). */
2662 else if (strcmp (fmt_str, target_percent_c) == 0)
2664 if (!arg
2665 || ! useless_type_conversion_p (integer_type_node, TREE_TYPE (arg)))
2666 return false;
2667 if (fn_fputc)
2669 gcall *repl = gimple_build_call (fn_fputc, 2, arg, fp);
2670 replace_call_with_call_and_fold (gsi, repl);
2671 return true;
2675 return false;
2678 /* Fold a call to the {,v}printf{,_unlocked} and __{,v}printf_chk builtins.
2679 FMT and ARG are the arguments to the call; we don't fold cases with
2680 more than 2 arguments, and ARG may be null if this is a 1-argument case.
2682 Return NULL_TREE if no simplification was possible, otherwise return the
2683 simplified form of the call as a tree. FCODE is the BUILT_IN_*
2684 code of the function to be simplified. */
2686 static bool
2687 gimple_fold_builtin_printf (gimple_stmt_iterator *gsi, tree fmt,
2688 tree arg, enum built_in_function fcode)
2690 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
2691 tree fn_putchar, fn_puts, newarg;
2692 const char *fmt_str = NULL;
2694 /* If the return value is used, don't do the transformation. */
2695 if (gimple_call_lhs (stmt) != NULL_TREE)
2696 return false;
2698 /* Check whether the format is a literal string constant. */
2699 fmt_str = c_getstr (fmt);
2700 if (fmt_str == NULL)
2701 return false;
2703 if (fcode == BUILT_IN_PRINTF_UNLOCKED)
2705 /* If we're using an unlocked function, assume the other
2706 unlocked functions exist explicitly. */
2707 fn_putchar = builtin_decl_explicit (BUILT_IN_PUTCHAR_UNLOCKED);
2708 fn_puts = builtin_decl_explicit (BUILT_IN_PUTS_UNLOCKED);
2710 else
2712 fn_putchar = builtin_decl_implicit (BUILT_IN_PUTCHAR);
2713 fn_puts = builtin_decl_implicit (BUILT_IN_PUTS);
2716 if (!init_target_chars ())
2717 return false;
2719 if (strcmp (fmt_str, target_percent_s) == 0
2720 || strchr (fmt_str, target_percent) == NULL)
2722 const char *str;
2724 if (strcmp (fmt_str, target_percent_s) == 0)
2726 if (fcode == BUILT_IN_VPRINTF || fcode == BUILT_IN_VPRINTF_CHK)
2727 return false;
2729 if (!arg || ! POINTER_TYPE_P (TREE_TYPE (arg)))
2730 return false;
2732 str = c_getstr (arg);
2733 if (str == NULL)
2734 return false;
2736 else
2738 /* The format specifier doesn't contain any '%' characters. */
2739 if (fcode != BUILT_IN_VPRINTF && fcode != BUILT_IN_VPRINTF_CHK
2740 && arg)
2741 return false;
2742 str = fmt_str;
2745 /* If the string was "", printf does nothing. */
2746 if (str[0] == '\0')
2748 replace_call_with_value (gsi, NULL_TREE);
2749 return true;
2752 /* If the string has length of 1, call putchar. */
2753 if (str[1] == '\0')
2755 /* Given printf("c"), (where c is any one character,)
2756 convert "c"[0] to an int and pass that to the replacement
2757 function. */
2758 newarg = build_int_cst (integer_type_node, str[0]);
2759 if (fn_putchar)
2761 gcall *repl = gimple_build_call (fn_putchar, 1, newarg);
2762 replace_call_with_call_and_fold (gsi, repl);
2763 return true;
2766 else
2768 /* If the string was "string\n", call puts("string"). */
2769 size_t len = strlen (str);
2770 if ((unsigned char)str[len - 1] == target_newline
2771 && (size_t) (int) len == len
2772 && (int) len > 0)
2774 char *newstr;
2775 tree offset_node, string_cst;
2777 /* Create a NUL-terminated string that's one char shorter
2778 than the original, stripping off the trailing '\n'. */
2779 newarg = build_string_literal (len, str);
2780 string_cst = string_constant (newarg, &offset_node);
2781 gcc_checking_assert (string_cst
2782 && (TREE_STRING_LENGTH (string_cst)
2783 == (int) len)
2784 && integer_zerop (offset_node)
2785 && (unsigned char)
2786 TREE_STRING_POINTER (string_cst)[len - 1]
2787 == target_newline);
2788 /* build_string_literal creates a new STRING_CST,
2789 modify it in place to avoid double copying. */
2790 newstr = CONST_CAST (char *, TREE_STRING_POINTER (string_cst));
2791 newstr[len - 1] = '\0';
2792 if (fn_puts)
2794 gcall *repl = gimple_build_call (fn_puts, 1, newarg);
2795 replace_call_with_call_and_fold (gsi, repl);
2796 return true;
2799 else
2800 /* We'd like to arrange to call fputs(string,stdout) here,
2801 but we need stdout and don't have a way to get it yet. */
2802 return false;
2806 /* The other optimizations can be done only on the non-va_list variants. */
2807 else if (fcode == BUILT_IN_VPRINTF || fcode == BUILT_IN_VPRINTF_CHK)
2808 return false;
2810 /* If the format specifier was "%s\n", call __builtin_puts(arg). */
2811 else if (strcmp (fmt_str, target_percent_s_newline) == 0)
2813 if (!arg || ! POINTER_TYPE_P (TREE_TYPE (arg)))
2814 return false;
2815 if (fn_puts)
2817 gcall *repl = gimple_build_call (fn_puts, 1, arg);
2818 replace_call_with_call_and_fold (gsi, repl);
2819 return true;
2823 /* If the format specifier was "%c", call __builtin_putchar(arg). */
2824 else if (strcmp (fmt_str, target_percent_c) == 0)
2826 if (!arg || ! useless_type_conversion_p (integer_type_node,
2827 TREE_TYPE (arg)))
2828 return false;
2829 if (fn_putchar)
2831 gcall *repl = gimple_build_call (fn_putchar, 1, arg);
2832 replace_call_with_call_and_fold (gsi, repl);
2833 return true;
2837 return false;
2842 /* Fold a call to __builtin_strlen with known length LEN. */
2844 static bool
2845 gimple_fold_builtin_strlen (gimple_stmt_iterator *gsi)
2847 gimple stmt = gsi_stmt (*gsi);
2848 tree len = get_maxval_strlen (gimple_call_arg (stmt, 0), 0);
2849 if (!len)
2850 return false;
2851 len = force_gimple_operand_gsi (gsi, len, true, NULL, true, GSI_SAME_STMT);
2852 replace_call_with_value (gsi, len);
2853 return true;
2857 /* Fold the non-target builtin at *GSI and return whether any simplification
2858 was made. */
2860 static bool
2861 gimple_fold_builtin (gimple_stmt_iterator *gsi)
2863 gcall *stmt = as_a <gcall *>(gsi_stmt (*gsi));
2864 tree callee = gimple_call_fndecl (stmt);
2866 /* Give up for always_inline inline builtins until they are
2867 inlined. */
2868 if (avoid_folding_inline_builtin (callee))
2869 return false;
2871 unsigned n = gimple_call_num_args (stmt);
2872 enum built_in_function fcode = DECL_FUNCTION_CODE (callee);
2873 switch (fcode)
2875 case BUILT_IN_BZERO:
2876 return gimple_fold_builtin_memset (gsi, integer_zero_node,
2877 gimple_call_arg (stmt, 1));
2878 case BUILT_IN_MEMSET:
2879 return gimple_fold_builtin_memset (gsi,
2880 gimple_call_arg (stmt, 1),
2881 gimple_call_arg (stmt, 2));
2882 case BUILT_IN_BCOPY:
2883 return gimple_fold_builtin_memory_op (gsi, gimple_call_arg (stmt, 1),
2884 gimple_call_arg (stmt, 0), 3);
2885 case BUILT_IN_MEMCPY:
2886 return gimple_fold_builtin_memory_op (gsi, gimple_call_arg (stmt, 0),
2887 gimple_call_arg (stmt, 1), 0);
2888 case BUILT_IN_MEMPCPY:
2889 return gimple_fold_builtin_memory_op (gsi, gimple_call_arg (stmt, 0),
2890 gimple_call_arg (stmt, 1), 1);
2891 case BUILT_IN_MEMMOVE:
2892 return gimple_fold_builtin_memory_op (gsi, gimple_call_arg (stmt, 0),
2893 gimple_call_arg (stmt, 1), 3);
2894 case BUILT_IN_SPRINTF_CHK:
2895 case BUILT_IN_VSPRINTF_CHK:
2896 return gimple_fold_builtin_sprintf_chk (gsi, fcode);
2897 case BUILT_IN_STRCAT_CHK:
2898 return gimple_fold_builtin_strcat_chk (gsi);
2899 case BUILT_IN_STRNCAT_CHK:
2900 return gimple_fold_builtin_strncat_chk (gsi);
2901 case BUILT_IN_STRLEN:
2902 return gimple_fold_builtin_strlen (gsi);
2903 case BUILT_IN_STRCPY:
2904 return gimple_fold_builtin_strcpy (gsi,
2905 gimple_call_arg (stmt, 0),
2906 gimple_call_arg (stmt, 1));
2907 case BUILT_IN_STRNCPY:
2908 return gimple_fold_builtin_strncpy (gsi,
2909 gimple_call_arg (stmt, 0),
2910 gimple_call_arg (stmt, 1),
2911 gimple_call_arg (stmt, 2));
2912 case BUILT_IN_STRCAT:
2913 return gimple_fold_builtin_strcat (gsi, gimple_call_arg (stmt, 0),
2914 gimple_call_arg (stmt, 1));
2915 case BUILT_IN_STRNCAT:
2916 return gimple_fold_builtin_strncat (gsi);
2917 case BUILT_IN_FPUTS:
2918 return gimple_fold_builtin_fputs (gsi, gimple_call_arg (stmt, 0),
2919 gimple_call_arg (stmt, 1), false);
2920 case BUILT_IN_FPUTS_UNLOCKED:
2921 return gimple_fold_builtin_fputs (gsi, gimple_call_arg (stmt, 0),
2922 gimple_call_arg (stmt, 1), true);
2923 case BUILT_IN_MEMCPY_CHK:
2924 case BUILT_IN_MEMPCPY_CHK:
2925 case BUILT_IN_MEMMOVE_CHK:
2926 case BUILT_IN_MEMSET_CHK:
2927 return gimple_fold_builtin_memory_chk (gsi,
2928 gimple_call_arg (stmt, 0),
2929 gimple_call_arg (stmt, 1),
2930 gimple_call_arg (stmt, 2),
2931 gimple_call_arg (stmt, 3),
2932 fcode);
2933 case BUILT_IN_STPCPY:
2934 return gimple_fold_builtin_stpcpy (gsi);
2935 case BUILT_IN_STRCPY_CHK:
2936 case BUILT_IN_STPCPY_CHK:
2937 return gimple_fold_builtin_stxcpy_chk (gsi,
2938 gimple_call_arg (stmt, 0),
2939 gimple_call_arg (stmt, 1),
2940 gimple_call_arg (stmt, 2),
2941 fcode);
2942 case BUILT_IN_STRNCPY_CHK:
2943 case BUILT_IN_STPNCPY_CHK:
2944 return gimple_fold_builtin_stxncpy_chk (gsi,
2945 gimple_call_arg (stmt, 0),
2946 gimple_call_arg (stmt, 1),
2947 gimple_call_arg (stmt, 2),
2948 gimple_call_arg (stmt, 3),
2949 fcode);
2950 case BUILT_IN_SNPRINTF_CHK:
2951 case BUILT_IN_VSNPRINTF_CHK:
2952 return gimple_fold_builtin_snprintf_chk (gsi, fcode);
2953 case BUILT_IN_SNPRINTF:
2954 return gimple_fold_builtin_snprintf (gsi);
2955 case BUILT_IN_SPRINTF:
2956 return gimple_fold_builtin_sprintf (gsi);
2957 case BUILT_IN_FPRINTF:
2958 case BUILT_IN_FPRINTF_UNLOCKED:
2959 case BUILT_IN_VFPRINTF:
2960 if (n == 2 || n == 3)
2961 return gimple_fold_builtin_fprintf (gsi,
2962 gimple_call_arg (stmt, 0),
2963 gimple_call_arg (stmt, 1),
2964 n == 3
2965 ? gimple_call_arg (stmt, 2)
2966 : NULL_TREE,
2967 fcode);
2968 break;
2969 case BUILT_IN_FPRINTF_CHK:
2970 case BUILT_IN_VFPRINTF_CHK:
2971 if (n == 3 || n == 4)
2972 return gimple_fold_builtin_fprintf (gsi,
2973 gimple_call_arg (stmt, 0),
2974 gimple_call_arg (stmt, 2),
2975 n == 4
2976 ? gimple_call_arg (stmt, 3)
2977 : NULL_TREE,
2978 fcode);
2979 break;
2980 case BUILT_IN_PRINTF:
2981 case BUILT_IN_PRINTF_UNLOCKED:
2982 case BUILT_IN_VPRINTF:
2983 if (n == 1 || n == 2)
2984 return gimple_fold_builtin_printf (gsi, gimple_call_arg (stmt, 0),
2985 n == 2
2986 ? gimple_call_arg (stmt, 1)
2987 : NULL_TREE, fcode);
2988 break;
2989 case BUILT_IN_PRINTF_CHK:
2990 case BUILT_IN_VPRINTF_CHK:
2991 if (n == 2 || n == 3)
2992 return gimple_fold_builtin_printf (gsi, gimple_call_arg (stmt, 1),
2993 n == 3
2994 ? gimple_call_arg (stmt, 2)
2995 : NULL_TREE, fcode);
2996 default:;
2999 /* Try the generic builtin folder. */
3000 bool ignore = (gimple_call_lhs (stmt) == NULL);
3001 tree result = fold_call_stmt (stmt, ignore);
3002 if (result)
3004 if (ignore)
3005 STRIP_NOPS (result);
3006 else
3007 result = fold_convert (gimple_call_return_type (stmt), result);
3008 if (!update_call_from_tree (gsi, result))
3009 gimplify_and_update_call_from_tree (gsi, result);
3010 return true;
3013 return false;
3016 /* Return true if ARG0 CODE ARG1 in infinite signed precision operation
3017 doesn't fit into TYPE. The test for overflow should be regardless of
3018 -fwrapv, and even for unsigned types. */
3020 bool
3021 arith_overflowed_p (enum tree_code code, const_tree type,
3022 const_tree arg0, const_tree arg1)
3024 typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION * 2) widest2_int;
3025 typedef generic_wide_int <wi::extended_tree <WIDE_INT_MAX_PRECISION * 2> >
3026 widest2_int_cst;
3027 widest2_int warg0 = widest2_int_cst (arg0);
3028 widest2_int warg1 = widest2_int_cst (arg1);
3029 widest2_int wres;
3030 switch (code)
3032 case PLUS_EXPR: wres = wi::add (warg0, warg1); break;
3033 case MINUS_EXPR: wres = wi::sub (warg0, warg1); break;
3034 case MULT_EXPR: wres = wi::mul (warg0, warg1); break;
3035 default: gcc_unreachable ();
3037 signop sign = TYPE_SIGN (type);
3038 if (sign == UNSIGNED && wi::neg_p (wres))
3039 return true;
3040 return wi::min_precision (wres, sign) > TYPE_PRECISION (type);
3043 /* Attempt to fold a call statement referenced by the statement iterator GSI.
3044 The statement may be replaced by another statement, e.g., if the call
3045 simplifies to a constant value. Return true if any changes were made.
3046 It is assumed that the operands have been previously folded. */
3048 static bool
3049 gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
3051 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
3052 tree callee;
3053 bool changed = false;
3054 unsigned i;
3056 /* Fold *& in call arguments. */
3057 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3058 if (REFERENCE_CLASS_P (gimple_call_arg (stmt, i)))
3060 tree tmp = maybe_fold_reference (gimple_call_arg (stmt, i), false);
3061 if (tmp)
3063 gimple_call_set_arg (stmt, i, tmp);
3064 changed = true;
3068 /* Check for virtual calls that became direct calls. */
3069 callee = gimple_call_fn (stmt);
3070 if (callee && TREE_CODE (callee) == OBJ_TYPE_REF)
3072 if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
3074 if (dump_file && virtual_method_call_p (callee)
3075 && !possible_polymorphic_call_target_p
3076 (callee, stmt, cgraph_node::get (gimple_call_addr_fndecl
3077 (OBJ_TYPE_REF_EXPR (callee)))))
3079 fprintf (dump_file,
3080 "Type inheritance inconsistent devirtualization of ");
3081 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3082 fprintf (dump_file, " to ");
3083 print_generic_expr (dump_file, callee, TDF_SLIM);
3084 fprintf (dump_file, "\n");
3087 gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
3088 changed = true;
3090 else if (flag_devirtualize && !inplace && virtual_method_call_p (callee))
3092 bool final;
3093 vec <cgraph_node *>targets
3094 = possible_polymorphic_call_targets (callee, stmt, &final);
3095 if (final && targets.length () <= 1 && dbg_cnt (devirt))
3097 tree lhs = gimple_call_lhs (stmt);
3098 if (dump_enabled_p ())
3100 location_t loc = gimple_location_safe (stmt);
3101 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
3102 "folding virtual function call to %s\n",
3103 targets.length () == 1
3104 ? targets[0]->name ()
3105 : "__builtin_unreachable");
3107 if (targets.length () == 1)
3109 gimple_call_set_fndecl (stmt, targets[0]->decl);
3110 changed = true;
3111 /* If the call becomes noreturn, remove the lhs. */
3112 if (lhs && (gimple_call_flags (stmt) & ECF_NORETURN))
3114 if (TREE_CODE (lhs) == SSA_NAME)
3116 tree var = create_tmp_var (TREE_TYPE (lhs));
3117 tree def = get_or_create_ssa_default_def (cfun, var);
3118 gimple new_stmt = gimple_build_assign (lhs, def);
3119 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
3121 gimple_call_set_lhs (stmt, NULL_TREE);
3123 maybe_remove_unused_call_args (cfun, stmt);
3125 else
3127 tree fndecl = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
3128 gimple new_stmt = gimple_build_call (fndecl, 0);
3129 gimple_set_location (new_stmt, gimple_location (stmt));
3130 if (lhs && TREE_CODE (lhs) == SSA_NAME)
3132 tree var = create_tmp_var (TREE_TYPE (lhs));
3133 tree def = get_or_create_ssa_default_def (cfun, var);
3135 /* To satisfy condition for
3136 cgraph_update_edges_for_call_stmt_node,
3137 we need to preserve GIMPLE_CALL statement
3138 at position of GSI iterator. */
3139 update_call_from_tree (gsi, def);
3140 gsi_insert_before (gsi, new_stmt, GSI_NEW_STMT);
3142 else
3144 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
3145 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
3146 gsi_replace (gsi, new_stmt, false);
3148 return true;
3154 /* Check for indirect calls that became direct calls, and then
3155 no longer require a static chain. */
3156 if (gimple_call_chain (stmt))
3158 tree fn = gimple_call_fndecl (stmt);
3159 if (fn && !DECL_STATIC_CHAIN (fn))
3161 gimple_call_set_chain (stmt, NULL);
3162 changed = true;
3164 else
3166 tree tmp = maybe_fold_reference (gimple_call_chain (stmt), false);
3167 if (tmp)
3169 gimple_call_set_chain (stmt, tmp);
3170 changed = true;
3175 if (inplace)
3176 return changed;
3178 /* Check for builtins that CCP can handle using information not
3179 available in the generic fold routines. */
3180 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
3182 if (gimple_fold_builtin (gsi))
3183 changed = true;
3185 else if (gimple_call_builtin_p (stmt, BUILT_IN_MD))
3187 changed |= targetm.gimple_fold_builtin (gsi);
3189 else if (gimple_call_internal_p (stmt))
3191 enum tree_code subcode = ERROR_MARK;
3192 tree result = NULL_TREE;
3193 bool cplx_result = false;
3194 tree overflow = NULL_TREE;
3195 switch (gimple_call_internal_fn (stmt))
3197 case IFN_BUILTIN_EXPECT:
3198 result = fold_builtin_expect (gimple_location (stmt),
3199 gimple_call_arg (stmt, 0),
3200 gimple_call_arg (stmt, 1),
3201 gimple_call_arg (stmt, 2));
3202 break;
3203 case IFN_UBSAN_OBJECT_SIZE:
3204 if (integer_all_onesp (gimple_call_arg (stmt, 2))
3205 || (TREE_CODE (gimple_call_arg (stmt, 1)) == INTEGER_CST
3206 && TREE_CODE (gimple_call_arg (stmt, 2)) == INTEGER_CST
3207 && tree_int_cst_le (gimple_call_arg (stmt, 1),
3208 gimple_call_arg (stmt, 2))))
3210 gsi_replace (gsi, gimple_build_nop (), true);
3211 unlink_stmt_vdef (stmt);
3212 release_defs (stmt);
3213 return true;
3215 break;
3216 case IFN_UBSAN_CHECK_ADD:
3217 subcode = PLUS_EXPR;
3218 break;
3219 case IFN_UBSAN_CHECK_SUB:
3220 subcode = MINUS_EXPR;
3221 break;
3222 case IFN_UBSAN_CHECK_MUL:
3223 subcode = MULT_EXPR;
3224 break;
3225 case IFN_ADD_OVERFLOW:
3226 subcode = PLUS_EXPR;
3227 cplx_result = true;
3228 break;
3229 case IFN_SUB_OVERFLOW:
3230 subcode = MINUS_EXPR;
3231 cplx_result = true;
3232 break;
3233 case IFN_MUL_OVERFLOW:
3234 subcode = MULT_EXPR;
3235 cplx_result = true;
3236 break;
3237 default:
3238 break;
3240 if (subcode != ERROR_MARK)
3242 tree arg0 = gimple_call_arg (stmt, 0);
3243 tree arg1 = gimple_call_arg (stmt, 1);
3244 tree type = TREE_TYPE (arg0);
3245 if (cplx_result)
3247 tree lhs = gimple_call_lhs (stmt);
3248 if (lhs == NULL_TREE)
3249 type = NULL_TREE;
3250 else
3251 type = TREE_TYPE (TREE_TYPE (lhs));
3253 if (type == NULL_TREE)
3255 /* x = y + 0; x = y - 0; x = y * 0; */
3256 else if (integer_zerop (arg1))
3257 result = subcode == MULT_EXPR ? integer_zero_node : arg0;
3258 /* x = 0 + y; x = 0 * y; */
3259 else if (subcode != MINUS_EXPR && integer_zerop (arg0))
3260 result = subcode == MULT_EXPR ? integer_zero_node : arg1;
3261 /* x = y - y; */
3262 else if (subcode == MINUS_EXPR && operand_equal_p (arg0, arg1, 0))
3263 result = integer_zero_node;
3264 /* x = y * 1; x = 1 * y; */
3265 else if (subcode == MULT_EXPR && integer_onep (arg1))
3266 result = arg0;
3267 else if (subcode == MULT_EXPR && integer_onep (arg0))
3268 result = arg1;
3269 else if (TREE_CODE (arg0) == INTEGER_CST
3270 && TREE_CODE (arg1) == INTEGER_CST)
3272 if (cplx_result)
3273 result = int_const_binop (subcode, fold_convert (type, arg0),
3274 fold_convert (type, arg1));
3275 else
3276 result = int_const_binop (subcode, arg0, arg1);
3277 if (result && arith_overflowed_p (subcode, type, arg0, arg1))
3279 if (cplx_result)
3280 overflow = build_one_cst (type);
3281 else
3282 result = NULL_TREE;
3285 if (result)
3287 if (result == integer_zero_node)
3288 result = build_zero_cst (type);
3289 else if (cplx_result && TREE_TYPE (result) != type)
3291 if (TREE_CODE (result) == INTEGER_CST)
3293 if (arith_overflowed_p (PLUS_EXPR, type, result,
3294 integer_zero_node))
3295 overflow = build_one_cst (type);
3297 else if ((!TYPE_UNSIGNED (TREE_TYPE (result))
3298 && TYPE_UNSIGNED (type))
3299 || (TYPE_PRECISION (type)
3300 < (TYPE_PRECISION (TREE_TYPE (result))
3301 + (TYPE_UNSIGNED (TREE_TYPE (result))
3302 && !TYPE_UNSIGNED (type)))))
3303 result = NULL_TREE;
3304 if (result)
3305 result = fold_convert (type, result);
3310 if (result)
3312 if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result))
3313 result = drop_tree_overflow (result);
3314 if (cplx_result)
3316 if (overflow == NULL_TREE)
3317 overflow = build_zero_cst (TREE_TYPE (result));
3318 tree ctype = build_complex_type (TREE_TYPE (result));
3319 if (TREE_CODE (result) == INTEGER_CST
3320 && TREE_CODE (overflow) == INTEGER_CST)
3321 result = build_complex (ctype, result, overflow);
3322 else
3323 result = build2_loc (gimple_location (stmt), COMPLEX_EXPR,
3324 ctype, result, overflow);
3326 if (!update_call_from_tree (gsi, result))
3327 gimplify_and_update_call_from_tree (gsi, result);
3328 changed = true;
3332 return changed;
3336 /* Worker for fold_stmt_1 dispatch to pattern based folding with
3337 gimple_simplify.
3339 Replaces *GSI with the simplification result in RCODE and OPS
3340 and the associated statements in *SEQ. Does the replacement
3341 according to INPLACE and returns true if the operation succeeded. */
3343 static bool
3344 replace_stmt_with_simplification (gimple_stmt_iterator *gsi,
3345 code_helper rcode, tree *ops,
3346 gimple_seq *seq, bool inplace)
3348 gimple stmt = gsi_stmt (*gsi);
3350 /* Play safe and do not allow abnormals to be mentioned in
3351 newly created statements. See also maybe_push_res_to_seq. */
3352 if ((TREE_CODE (ops[0]) == SSA_NAME
3353 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[0]))
3354 || (ops[1]
3355 && TREE_CODE (ops[1]) == SSA_NAME
3356 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[1]))
3357 || (ops[2]
3358 && TREE_CODE (ops[2]) == SSA_NAME
3359 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[2])))
3360 return false;
3362 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
3364 gcc_assert (rcode.is_tree_code ());
3365 if (TREE_CODE_CLASS ((enum tree_code)rcode) == tcc_comparison
3366 /* GIMPLE_CONDs condition may not throw. */
3367 && (!flag_exceptions
3368 || !cfun->can_throw_non_call_exceptions
3369 || !operation_could_trap_p (rcode,
3370 FLOAT_TYPE_P (TREE_TYPE (ops[0])),
3371 false, NULL_TREE)))
3372 gimple_cond_set_condition (cond_stmt, rcode, ops[0], ops[1]);
3373 else if (rcode == SSA_NAME)
3374 gimple_cond_set_condition (cond_stmt, NE_EXPR, ops[0],
3375 build_zero_cst (TREE_TYPE (ops[0])));
3376 else if (rcode == INTEGER_CST)
3378 if (integer_zerop (ops[0]))
3379 gimple_cond_make_false (cond_stmt);
3380 else
3381 gimple_cond_make_true (cond_stmt);
3383 else if (!inplace)
3385 tree res = maybe_push_res_to_seq (rcode, boolean_type_node,
3386 ops, seq);
3387 if (!res)
3388 return false;
3389 gimple_cond_set_condition (cond_stmt, NE_EXPR, res,
3390 build_zero_cst (TREE_TYPE (res)));
3392 else
3393 return false;
3394 if (dump_file && (dump_flags & TDF_DETAILS))
3396 fprintf (dump_file, "gimple_simplified to ");
3397 if (!gimple_seq_empty_p (*seq))
3398 print_gimple_seq (dump_file, *seq, 0, TDF_SLIM);
3399 print_gimple_stmt (dump_file, gsi_stmt (*gsi),
3400 0, TDF_SLIM);
3402 gsi_insert_seq_before (gsi, *seq, GSI_SAME_STMT);
3403 return true;
3405 else if (is_gimple_assign (stmt)
3406 && rcode.is_tree_code ())
3408 if (!inplace
3409 || gimple_num_ops (stmt) > get_gimple_rhs_num_ops (rcode))
3411 maybe_build_generic_op (rcode,
3412 TREE_TYPE (gimple_assign_lhs (stmt)),
3413 &ops[0], ops[1], ops[2]);
3414 gimple_assign_set_rhs_with_ops (gsi, rcode, ops[0], ops[1], ops[2]);
3415 if (dump_file && (dump_flags & TDF_DETAILS))
3417 fprintf (dump_file, "gimple_simplified to ");
3418 if (!gimple_seq_empty_p (*seq))
3419 print_gimple_seq (dump_file, *seq, 0, TDF_SLIM);
3420 print_gimple_stmt (dump_file, gsi_stmt (*gsi),
3421 0, TDF_SLIM);
3423 gsi_insert_seq_before (gsi, *seq, GSI_SAME_STMT);
3424 return true;
3427 else if (!inplace)
3429 if (gimple_has_lhs (stmt))
3431 tree lhs = gimple_get_lhs (stmt);
3432 if (!maybe_push_res_to_seq (rcode, TREE_TYPE (lhs),
3433 ops, seq, lhs))
3434 return false;
3435 if (dump_file && (dump_flags & TDF_DETAILS))
3437 fprintf (dump_file, "gimple_simplified to ");
3438 print_gimple_seq (dump_file, *seq, 0, TDF_SLIM);
3440 gsi_replace_with_seq_vops (gsi, *seq);
3441 return true;
3443 else
3444 gcc_unreachable ();
3447 return false;
3450 /* Canonicalize MEM_REFs invariant address operand after propagation. */
3452 static bool
3453 maybe_canonicalize_mem_ref_addr (tree *t)
3455 bool res = false;
3457 if (TREE_CODE (*t) == ADDR_EXPR)
3458 t = &TREE_OPERAND (*t, 0);
3460 while (handled_component_p (*t))
3461 t = &TREE_OPERAND (*t, 0);
3463 /* Canonicalize MEM [&foo.bar, 0] which appears after propagating
3464 of invariant addresses into a SSA name MEM_REF address. */
3465 if (TREE_CODE (*t) == MEM_REF
3466 || TREE_CODE (*t) == TARGET_MEM_REF)
3468 tree addr = TREE_OPERAND (*t, 0);
3469 if (TREE_CODE (addr) == ADDR_EXPR
3470 && (TREE_CODE (TREE_OPERAND (addr, 0)) == MEM_REF
3471 || handled_component_p (TREE_OPERAND (addr, 0))))
3473 tree base;
3474 HOST_WIDE_INT coffset;
3475 base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
3476 &coffset);
3477 if (!base)
3478 gcc_unreachable ();
3480 TREE_OPERAND (*t, 0) = build_fold_addr_expr (base);
3481 TREE_OPERAND (*t, 1) = int_const_binop (PLUS_EXPR,
3482 TREE_OPERAND (*t, 1),
3483 size_int (coffset));
3484 res = true;
3486 gcc_checking_assert (TREE_CODE (TREE_OPERAND (*t, 0)) == DEBUG_EXPR_DECL
3487 || is_gimple_mem_ref_addr (TREE_OPERAND (*t, 0)));
3490 /* Canonicalize back MEM_REFs to plain reference trees if the object
3491 accessed is a decl that has the same access semantics as the MEM_REF. */
3492 if (TREE_CODE (*t) == MEM_REF
3493 && TREE_CODE (TREE_OPERAND (*t, 0)) == ADDR_EXPR
3494 && integer_zerop (TREE_OPERAND (*t, 1))
3495 && MR_DEPENDENCE_CLIQUE (*t) == 0)
3497 tree decl = TREE_OPERAND (TREE_OPERAND (*t, 0), 0);
3498 tree alias_type = TREE_TYPE (TREE_OPERAND (*t, 1));
3499 if (/* Same volatile qualification. */
3500 TREE_THIS_VOLATILE (*t) == TREE_THIS_VOLATILE (decl)
3501 /* Same TBAA behavior with -fstrict-aliasing. */
3502 && !TYPE_REF_CAN_ALIAS_ALL (alias_type)
3503 && (TYPE_MAIN_VARIANT (TREE_TYPE (decl))
3504 == TYPE_MAIN_VARIANT (TREE_TYPE (alias_type)))
3505 /* Same alignment. */
3506 && TYPE_ALIGN (TREE_TYPE (decl)) == TYPE_ALIGN (TREE_TYPE (*t))
3507 /* We have to look out here to not drop a required conversion
3508 from the rhs to the lhs if *t appears on the lhs or vice-versa
3509 if it appears on the rhs. Thus require strict type
3510 compatibility. */
3511 && types_compatible_p (TREE_TYPE (*t), TREE_TYPE (decl)))
3513 *t = TREE_OPERAND (TREE_OPERAND (*t, 0), 0);
3514 res = true;
3518 /* Canonicalize TARGET_MEM_REF in particular with respect to
3519 the indexes becoming constant. */
3520 else if (TREE_CODE (*t) == TARGET_MEM_REF)
3522 tree tem = maybe_fold_tmr (*t);
3523 if (tem)
3525 *t = tem;
3526 res = true;
3530 return res;
3533 /* Worker for both fold_stmt and fold_stmt_inplace. The INPLACE argument
3534 distinguishes both cases. */
3536 static bool
3537 fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace, tree (*valueize) (tree))
3539 bool changed = false;
3540 gimple stmt = gsi_stmt (*gsi);
3541 unsigned i;
3543 /* First do required canonicalization of [TARGET_]MEM_REF addresses
3544 after propagation.
3545 ??? This shouldn't be done in generic folding but in the
3546 propagation helpers which also know whether an address was
3547 propagated. */
3548 switch (gimple_code (stmt))
3550 case GIMPLE_ASSIGN:
3551 if (gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
3553 tree *rhs = gimple_assign_rhs1_ptr (stmt);
3554 if ((REFERENCE_CLASS_P (*rhs)
3555 || TREE_CODE (*rhs) == ADDR_EXPR)
3556 && maybe_canonicalize_mem_ref_addr (rhs))
3557 changed = true;
3558 tree *lhs = gimple_assign_lhs_ptr (stmt);
3559 if (REFERENCE_CLASS_P (*lhs)
3560 && maybe_canonicalize_mem_ref_addr (lhs))
3561 changed = true;
3563 break;
3564 case GIMPLE_CALL:
3566 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3568 tree *arg = gimple_call_arg_ptr (stmt, i);
3569 if (REFERENCE_CLASS_P (*arg)
3570 && maybe_canonicalize_mem_ref_addr (arg))
3571 changed = true;
3573 tree *lhs = gimple_call_lhs_ptr (stmt);
3574 if (*lhs
3575 && REFERENCE_CLASS_P (*lhs)
3576 && maybe_canonicalize_mem_ref_addr (lhs))
3577 changed = true;
3578 break;
3580 case GIMPLE_ASM:
3582 gasm *asm_stmt = as_a <gasm *> (stmt);
3583 for (i = 0; i < gimple_asm_noutputs (asm_stmt); ++i)
3585 tree link = gimple_asm_output_op (asm_stmt, i);
3586 tree op = TREE_VALUE (link);
3587 if (REFERENCE_CLASS_P (op)
3588 && maybe_canonicalize_mem_ref_addr (&TREE_VALUE (link)))
3589 changed = true;
3591 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
3593 tree link = gimple_asm_input_op (asm_stmt, i);
3594 tree op = TREE_VALUE (link);
3595 if ((REFERENCE_CLASS_P (op)
3596 || TREE_CODE (op) == ADDR_EXPR)
3597 && maybe_canonicalize_mem_ref_addr (&TREE_VALUE (link)))
3598 changed = true;
3601 break;
3602 case GIMPLE_DEBUG:
3603 if (gimple_debug_bind_p (stmt))
3605 tree *val = gimple_debug_bind_get_value_ptr (stmt);
3606 if (*val
3607 && (REFERENCE_CLASS_P (*val)
3608 || TREE_CODE (*val) == ADDR_EXPR)
3609 && maybe_canonicalize_mem_ref_addr (val))
3610 changed = true;
3612 break;
3613 default:;
3616 /* Dispatch to pattern-based folding. */
3617 if (!inplace
3618 || is_gimple_assign (stmt)
3619 || gimple_code (stmt) == GIMPLE_COND)
3621 gimple_seq seq = NULL;
3622 code_helper rcode;
3623 tree ops[3] = {};
3624 if (gimple_simplify (stmt, &rcode, ops, inplace ? NULL : &seq, valueize))
3626 if (replace_stmt_with_simplification (gsi, rcode, ops, &seq, inplace))
3627 changed = true;
3628 else
3629 gimple_seq_discard (seq);
3633 stmt = gsi_stmt (*gsi);
3635 /* Fold the main computation performed by the statement. */
3636 switch (gimple_code (stmt))
3638 case GIMPLE_ASSIGN:
3640 unsigned old_num_ops = gimple_num_ops (stmt);
3641 enum tree_code subcode = gimple_assign_rhs_code (stmt);
3642 tree lhs = gimple_assign_lhs (stmt);
3643 tree new_rhs;
3644 /* First canonicalize operand order. This avoids building new
3645 trees if this is the only thing fold would later do. */
3646 if ((commutative_tree_code (subcode)
3647 || commutative_ternary_tree_code (subcode))
3648 && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
3649 gimple_assign_rhs2 (stmt), false))
3651 tree tem = gimple_assign_rhs1 (stmt);
3652 gimple_assign_set_rhs1 (stmt, gimple_assign_rhs2 (stmt));
3653 gimple_assign_set_rhs2 (stmt, tem);
3654 changed = true;
3656 new_rhs = fold_gimple_assign (gsi);
3657 if (new_rhs
3658 && !useless_type_conversion_p (TREE_TYPE (lhs),
3659 TREE_TYPE (new_rhs)))
3660 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
3661 if (new_rhs
3662 && (!inplace
3663 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs)) < old_num_ops))
3665 gimple_assign_set_rhs_from_tree (gsi, new_rhs);
3666 changed = true;
3668 break;
3671 case GIMPLE_COND:
3672 changed |= fold_gimple_cond (as_a <gcond *> (stmt));
3673 break;
3675 case GIMPLE_CALL:
3676 changed |= gimple_fold_call (gsi, inplace);
3677 break;
3679 case GIMPLE_ASM:
3680 /* Fold *& in asm operands. */
3682 gasm *asm_stmt = as_a <gasm *> (stmt);
3683 size_t noutputs;
3684 const char **oconstraints;
3685 const char *constraint;
3686 bool allows_mem, allows_reg;
3688 noutputs = gimple_asm_noutputs (asm_stmt);
3689 oconstraints = XALLOCAVEC (const char *, noutputs);
3691 for (i = 0; i < gimple_asm_noutputs (asm_stmt); ++i)
3693 tree link = gimple_asm_output_op (asm_stmt, i);
3694 tree op = TREE_VALUE (link);
3695 oconstraints[i]
3696 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3697 if (REFERENCE_CLASS_P (op)
3698 && (op = maybe_fold_reference (op, true)) != NULL_TREE)
3700 TREE_VALUE (link) = op;
3701 changed = true;
3704 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
3706 tree link = gimple_asm_input_op (asm_stmt, i);
3707 tree op = TREE_VALUE (link);
3708 constraint
3709 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3710 parse_input_constraint (&constraint, 0, 0, noutputs, 0,
3711 oconstraints, &allows_mem, &allows_reg);
3712 if (REFERENCE_CLASS_P (op)
3713 && (op = maybe_fold_reference (op, !allows_reg && allows_mem))
3714 != NULL_TREE)
3716 TREE_VALUE (link) = op;
3717 changed = true;
3721 break;
3723 case GIMPLE_DEBUG:
3724 if (gimple_debug_bind_p (stmt))
3726 tree val = gimple_debug_bind_get_value (stmt);
3727 if (val
3728 && REFERENCE_CLASS_P (val))
3730 tree tem = maybe_fold_reference (val, false);
3731 if (tem)
3733 gimple_debug_bind_set_value (stmt, tem);
3734 changed = true;
3737 else if (val
3738 && TREE_CODE (val) == ADDR_EXPR)
3740 tree ref = TREE_OPERAND (val, 0);
3741 tree tem = maybe_fold_reference (ref, false);
3742 if (tem)
3744 tem = build_fold_addr_expr_with_type (tem, TREE_TYPE (val));
3745 gimple_debug_bind_set_value (stmt, tem);
3746 changed = true;
3750 break;
3752 default:;
3755 stmt = gsi_stmt (*gsi);
3757 /* Fold *& on the lhs. */
3758 if (gimple_has_lhs (stmt))
3760 tree lhs = gimple_get_lhs (stmt);
3761 if (lhs && REFERENCE_CLASS_P (lhs))
3763 tree new_lhs = maybe_fold_reference (lhs, true);
3764 if (new_lhs)
3766 gimple_set_lhs (stmt, new_lhs);
3767 changed = true;
3772 return changed;
3775 /* Valueziation callback that ends up not following SSA edges. */
3777 tree
3778 no_follow_ssa_edges (tree)
3780 return NULL_TREE;
3783 /* Valueization callback that ends up following single-use SSA edges only. */
3785 tree
3786 follow_single_use_edges (tree val)
3788 if (TREE_CODE (val) == SSA_NAME
3789 && !has_single_use (val))
3790 return NULL_TREE;
3791 return val;
3794 /* Fold the statement pointed to by GSI. In some cases, this function may
3795 replace the whole statement with a new one. Returns true iff folding
3796 makes any changes.
3797 The statement pointed to by GSI should be in valid gimple form but may
3798 be in unfolded state as resulting from for example constant propagation
3799 which can produce *&x = 0. */
3801 bool
3802 fold_stmt (gimple_stmt_iterator *gsi)
3804 return fold_stmt_1 (gsi, false, no_follow_ssa_edges);
3807 bool
3808 fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
3810 return fold_stmt_1 (gsi, false, valueize);
3813 /* Perform the minimal folding on statement *GSI. Only operations like
3814 *&x created by constant propagation are handled. The statement cannot
3815 be replaced with a new one. Return true if the statement was
3816 changed, false otherwise.
3817 The statement *GSI should be in valid gimple form but may
3818 be in unfolded state as resulting from for example constant propagation
3819 which can produce *&x = 0. */
3821 bool
3822 fold_stmt_inplace (gimple_stmt_iterator *gsi)
3824 gimple stmt = gsi_stmt (*gsi);
3825 bool changed = fold_stmt_1 (gsi, true, no_follow_ssa_edges);
3826 gcc_assert (gsi_stmt (*gsi) == stmt);
3827 return changed;
3830 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE
3831 if EXPR is null or we don't know how.
3832 If non-null, the result always has boolean type. */
3834 static tree
3835 canonicalize_bool (tree expr, bool invert)
3837 if (!expr)
3838 return NULL_TREE;
3839 else if (invert)
3841 if (integer_nonzerop (expr))
3842 return boolean_false_node;
3843 else if (integer_zerop (expr))
3844 return boolean_true_node;
3845 else if (TREE_CODE (expr) == SSA_NAME)
3846 return fold_build2 (EQ_EXPR, boolean_type_node, expr,
3847 build_int_cst (TREE_TYPE (expr), 0));
3848 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
3849 return fold_build2 (invert_tree_comparison (TREE_CODE (expr), false),
3850 boolean_type_node,
3851 TREE_OPERAND (expr, 0),
3852 TREE_OPERAND (expr, 1));
3853 else
3854 return NULL_TREE;
3856 else
3858 if (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
3859 return expr;
3860 if (integer_nonzerop (expr))
3861 return boolean_true_node;
3862 else if (integer_zerop (expr))
3863 return boolean_false_node;
3864 else if (TREE_CODE (expr) == SSA_NAME)
3865 return fold_build2 (NE_EXPR, boolean_type_node, expr,
3866 build_int_cst (TREE_TYPE (expr), 0));
3867 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
3868 return fold_build2 (TREE_CODE (expr),
3869 boolean_type_node,
3870 TREE_OPERAND (expr, 0),
3871 TREE_OPERAND (expr, 1));
3872 else
3873 return NULL_TREE;
3877 /* Check to see if a boolean expression EXPR is logically equivalent to the
3878 comparison (OP1 CODE OP2). Check for various identities involving
3879 SSA_NAMEs. */
3881 static bool
3882 same_bool_comparison_p (const_tree expr, enum tree_code code,
3883 const_tree op1, const_tree op2)
3885 gimple s;
3887 /* The obvious case. */
3888 if (TREE_CODE (expr) == code
3889 && operand_equal_p (TREE_OPERAND (expr, 0), op1, 0)
3890 && operand_equal_p (TREE_OPERAND (expr, 1), op2, 0))
3891 return true;
3893 /* Check for comparing (name, name != 0) and the case where expr
3894 is an SSA_NAME with a definition matching the comparison. */
3895 if (TREE_CODE (expr) == SSA_NAME
3896 && TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
3898 if (operand_equal_p (expr, op1, 0))
3899 return ((code == NE_EXPR && integer_zerop (op2))
3900 || (code == EQ_EXPR && integer_nonzerop (op2)));
3901 s = SSA_NAME_DEF_STMT (expr);
3902 if (is_gimple_assign (s)
3903 && gimple_assign_rhs_code (s) == code
3904 && operand_equal_p (gimple_assign_rhs1 (s), op1, 0)
3905 && operand_equal_p (gimple_assign_rhs2 (s), op2, 0))
3906 return true;
3909 /* If op1 is of the form (name != 0) or (name == 0), and the definition
3910 of name is a comparison, recurse. */
3911 if (TREE_CODE (op1) == SSA_NAME
3912 && TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE)
3914 s = SSA_NAME_DEF_STMT (op1);
3915 if (is_gimple_assign (s)
3916 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
3918 enum tree_code c = gimple_assign_rhs_code (s);
3919 if ((c == NE_EXPR && integer_zerop (op2))
3920 || (c == EQ_EXPR && integer_nonzerop (op2)))
3921 return same_bool_comparison_p (expr, c,
3922 gimple_assign_rhs1 (s),
3923 gimple_assign_rhs2 (s));
3924 if ((c == EQ_EXPR && integer_zerop (op2))
3925 || (c == NE_EXPR && integer_nonzerop (op2)))
3926 return same_bool_comparison_p (expr,
3927 invert_tree_comparison (c, false),
3928 gimple_assign_rhs1 (s),
3929 gimple_assign_rhs2 (s));
3932 return false;
3935 /* Check to see if two boolean expressions OP1 and OP2 are logically
3936 equivalent. */
3938 static bool
3939 same_bool_result_p (const_tree op1, const_tree op2)
3941 /* Simple cases first. */
3942 if (operand_equal_p (op1, op2, 0))
3943 return true;
3945 /* Check the cases where at least one of the operands is a comparison.
3946 These are a bit smarter than operand_equal_p in that they apply some
3947 identifies on SSA_NAMEs. */
3948 if (TREE_CODE_CLASS (TREE_CODE (op2)) == tcc_comparison
3949 && same_bool_comparison_p (op1, TREE_CODE (op2),
3950 TREE_OPERAND (op2, 0),
3951 TREE_OPERAND (op2, 1)))
3952 return true;
3953 if (TREE_CODE_CLASS (TREE_CODE (op1)) == tcc_comparison
3954 && same_bool_comparison_p (op2, TREE_CODE (op1),
3955 TREE_OPERAND (op1, 0),
3956 TREE_OPERAND (op1, 1)))
3957 return true;
3959 /* Default case. */
3960 return false;
3963 /* Forward declarations for some mutually recursive functions. */
3965 static tree
3966 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
3967 enum tree_code code2, tree op2a, tree op2b);
3968 static tree
3969 and_var_with_comparison (tree var, bool invert,
3970 enum tree_code code2, tree op2a, tree op2b);
3971 static tree
3972 and_var_with_comparison_1 (gimple stmt,
3973 enum tree_code code2, tree op2a, tree op2b);
3974 static tree
3975 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
3976 enum tree_code code2, tree op2a, tree op2b);
3977 static tree
3978 or_var_with_comparison (tree var, bool invert,
3979 enum tree_code code2, tree op2a, tree op2b);
3980 static tree
3981 or_var_with_comparison_1 (gimple stmt,
3982 enum tree_code code2, tree op2a, tree op2b);
3984 /* Helper function for and_comparisons_1: try to simplify the AND of the
3985 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
3986 If INVERT is true, invert the value of the VAR before doing the AND.
3987 Return NULL_EXPR if we can't simplify this to a single expression. */
3989 static tree
3990 and_var_with_comparison (tree var, bool invert,
3991 enum tree_code code2, tree op2a, tree op2b)
3993 tree t;
3994 gimple stmt = SSA_NAME_DEF_STMT (var);
3996 /* We can only deal with variables whose definitions are assignments. */
3997 if (!is_gimple_assign (stmt))
3998 return NULL_TREE;
4000 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
4001 !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
4002 Then we only have to consider the simpler non-inverted cases. */
4003 if (invert)
4004 t = or_var_with_comparison_1 (stmt,
4005 invert_tree_comparison (code2, false),
4006 op2a, op2b);
4007 else
4008 t = and_var_with_comparison_1 (stmt, code2, op2a, op2b);
4009 return canonicalize_bool (t, invert);
4012 /* Try to simplify the AND of the ssa variable defined by the assignment
4013 STMT with the comparison specified by (OP2A CODE2 OP2B).
4014 Return NULL_EXPR if we can't simplify this to a single expression. */
4016 static tree
4017 and_var_with_comparison_1 (gimple stmt,
4018 enum tree_code code2, tree op2a, tree op2b)
4020 tree var = gimple_assign_lhs (stmt);
4021 tree true_test_var = NULL_TREE;
4022 tree false_test_var = NULL_TREE;
4023 enum tree_code innercode = gimple_assign_rhs_code (stmt);
4025 /* Check for identities like (var AND (var == 0)) => false. */
4026 if (TREE_CODE (op2a) == SSA_NAME
4027 && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
4029 if ((code2 == NE_EXPR && integer_zerop (op2b))
4030 || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
4032 true_test_var = op2a;
4033 if (var == true_test_var)
4034 return var;
4036 else if ((code2 == EQ_EXPR && integer_zerop (op2b))
4037 || (code2 == NE_EXPR && integer_nonzerop (op2b)))
4039 false_test_var = op2a;
4040 if (var == false_test_var)
4041 return boolean_false_node;
4045 /* If the definition is a comparison, recurse on it. */
4046 if (TREE_CODE_CLASS (innercode) == tcc_comparison)
4048 tree t = and_comparisons_1 (innercode,
4049 gimple_assign_rhs1 (stmt),
4050 gimple_assign_rhs2 (stmt),
4051 code2,
4052 op2a,
4053 op2b);
4054 if (t)
4055 return t;
4058 /* If the definition is an AND or OR expression, we may be able to
4059 simplify by reassociating. */
4060 if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
4061 && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
4063 tree inner1 = gimple_assign_rhs1 (stmt);
4064 tree inner2 = gimple_assign_rhs2 (stmt);
4065 gimple s;
4066 tree t;
4067 tree partial = NULL_TREE;
4068 bool is_and = (innercode == BIT_AND_EXPR);
4070 /* Check for boolean identities that don't require recursive examination
4071 of inner1/inner2:
4072 inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
4073 inner1 AND (inner1 OR inner2) => inner1
4074 !inner1 AND (inner1 AND inner2) => false
4075 !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
4076 Likewise for similar cases involving inner2. */
4077 if (inner1 == true_test_var)
4078 return (is_and ? var : inner1);
4079 else if (inner2 == true_test_var)
4080 return (is_and ? var : inner2);
4081 else if (inner1 == false_test_var)
4082 return (is_and
4083 ? boolean_false_node
4084 : and_var_with_comparison (inner2, false, code2, op2a, op2b));
4085 else if (inner2 == false_test_var)
4086 return (is_and
4087 ? boolean_false_node
4088 : and_var_with_comparison (inner1, false, code2, op2a, op2b));
4090 /* Next, redistribute/reassociate the AND across the inner tests.
4091 Compute the first partial result, (inner1 AND (op2a code op2b)) */
4092 if (TREE_CODE (inner1) == SSA_NAME
4093 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
4094 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
4095 && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
4096 gimple_assign_rhs1 (s),
4097 gimple_assign_rhs2 (s),
4098 code2, op2a, op2b)))
4100 /* Handle the AND case, where we are reassociating:
4101 (inner1 AND inner2) AND (op2a code2 op2b)
4102 => (t AND inner2)
4103 If the partial result t is a constant, we win. Otherwise
4104 continue on to try reassociating with the other inner test. */
4105 if (is_and)
4107 if (integer_onep (t))
4108 return inner2;
4109 else if (integer_zerop (t))
4110 return boolean_false_node;
4113 /* Handle the OR case, where we are redistributing:
4114 (inner1 OR inner2) AND (op2a code2 op2b)
4115 => (t OR (inner2 AND (op2a code2 op2b))) */
4116 else if (integer_onep (t))
4117 return boolean_true_node;
4119 /* Save partial result for later. */
4120 partial = t;
4123 /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
4124 if (TREE_CODE (inner2) == SSA_NAME
4125 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
4126 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
4127 && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
4128 gimple_assign_rhs1 (s),
4129 gimple_assign_rhs2 (s),
4130 code2, op2a, op2b)))
4132 /* Handle the AND case, where we are reassociating:
4133 (inner1 AND inner2) AND (op2a code2 op2b)
4134 => (inner1 AND t) */
4135 if (is_and)
4137 if (integer_onep (t))
4138 return inner1;
4139 else if (integer_zerop (t))
4140 return boolean_false_node;
4141 /* If both are the same, we can apply the identity
4142 (x AND x) == x. */
4143 else if (partial && same_bool_result_p (t, partial))
4144 return t;
4147 /* Handle the OR case. where we are redistributing:
4148 (inner1 OR inner2) AND (op2a code2 op2b)
4149 => (t OR (inner1 AND (op2a code2 op2b)))
4150 => (t OR partial) */
4151 else
4153 if (integer_onep (t))
4154 return boolean_true_node;
4155 else if (partial)
4157 /* We already got a simplification for the other
4158 operand to the redistributed OR expression. The
4159 interesting case is when at least one is false.
4160 Or, if both are the same, we can apply the identity
4161 (x OR x) == x. */
4162 if (integer_zerop (partial))
4163 return t;
4164 else if (integer_zerop (t))
4165 return partial;
4166 else if (same_bool_result_p (t, partial))
4167 return t;
4172 return NULL_TREE;
4175 /* Try to simplify the AND of two comparisons defined by
4176 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
4177 If this can be done without constructing an intermediate value,
4178 return the resulting tree; otherwise NULL_TREE is returned.
4179 This function is deliberately asymmetric as it recurses on SSA_DEFs
4180 in the first comparison but not the second. */
4182 static tree
4183 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
4184 enum tree_code code2, tree op2a, tree op2b)
4186 tree truth_type = truth_type_for (TREE_TYPE (op1a));
4188 /* First check for ((x CODE1 y) AND (x CODE2 y)). */
4189 if (operand_equal_p (op1a, op2a, 0)
4190 && operand_equal_p (op1b, op2b, 0))
4192 /* Result will be either NULL_TREE, or a combined comparison. */
4193 tree t = combine_comparisons (UNKNOWN_LOCATION,
4194 TRUTH_ANDIF_EXPR, code1, code2,
4195 truth_type, op1a, op1b);
4196 if (t)
4197 return t;
4200 /* Likewise the swapped case of the above. */
4201 if (operand_equal_p (op1a, op2b, 0)
4202 && operand_equal_p (op1b, op2a, 0))
4204 /* Result will be either NULL_TREE, or a combined comparison. */
4205 tree t = combine_comparisons (UNKNOWN_LOCATION,
4206 TRUTH_ANDIF_EXPR, code1,
4207 swap_tree_comparison (code2),
4208 truth_type, op1a, op1b);
4209 if (t)
4210 return t;
4213 /* If both comparisons are of the same value against constants, we might
4214 be able to merge them. */
4215 if (operand_equal_p (op1a, op2a, 0)
4216 && TREE_CODE (op1b) == INTEGER_CST
4217 && TREE_CODE (op2b) == INTEGER_CST)
4219 int cmp = tree_int_cst_compare (op1b, op2b);
4221 /* If we have (op1a == op1b), we should either be able to
4222 return that or FALSE, depending on whether the constant op1b
4223 also satisfies the other comparison against op2b. */
4224 if (code1 == EQ_EXPR)
4226 bool done = true;
4227 bool val;
4228 switch (code2)
4230 case EQ_EXPR: val = (cmp == 0); break;
4231 case NE_EXPR: val = (cmp != 0); break;
4232 case LT_EXPR: val = (cmp < 0); break;
4233 case GT_EXPR: val = (cmp > 0); break;
4234 case LE_EXPR: val = (cmp <= 0); break;
4235 case GE_EXPR: val = (cmp >= 0); break;
4236 default: done = false;
4238 if (done)
4240 if (val)
4241 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4242 else
4243 return boolean_false_node;
4246 /* Likewise if the second comparison is an == comparison. */
4247 else if (code2 == EQ_EXPR)
4249 bool done = true;
4250 bool val;
4251 switch (code1)
4253 case EQ_EXPR: val = (cmp == 0); break;
4254 case NE_EXPR: val = (cmp != 0); break;
4255 case LT_EXPR: val = (cmp > 0); break;
4256 case GT_EXPR: val = (cmp < 0); break;
4257 case LE_EXPR: val = (cmp >= 0); break;
4258 case GE_EXPR: val = (cmp <= 0); break;
4259 default: done = false;
4261 if (done)
4263 if (val)
4264 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4265 else
4266 return boolean_false_node;
4270 /* Same business with inequality tests. */
4271 else if (code1 == NE_EXPR)
4273 bool val;
4274 switch (code2)
4276 case EQ_EXPR: val = (cmp != 0); break;
4277 case NE_EXPR: val = (cmp == 0); break;
4278 case LT_EXPR: val = (cmp >= 0); break;
4279 case GT_EXPR: val = (cmp <= 0); break;
4280 case LE_EXPR: val = (cmp > 0); break;
4281 case GE_EXPR: val = (cmp < 0); break;
4282 default:
4283 val = false;
4285 if (val)
4286 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4288 else if (code2 == NE_EXPR)
4290 bool val;
4291 switch (code1)
4293 case EQ_EXPR: val = (cmp == 0); break;
4294 case NE_EXPR: val = (cmp != 0); break;
4295 case LT_EXPR: val = (cmp <= 0); break;
4296 case GT_EXPR: val = (cmp >= 0); break;
4297 case LE_EXPR: val = (cmp < 0); break;
4298 case GE_EXPR: val = (cmp > 0); break;
4299 default:
4300 val = false;
4302 if (val)
4303 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4306 /* Chose the more restrictive of two < or <= comparisons. */
4307 else if ((code1 == LT_EXPR || code1 == LE_EXPR)
4308 && (code2 == LT_EXPR || code2 == LE_EXPR))
4310 if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
4311 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4312 else
4313 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4316 /* Likewise chose the more restrictive of two > or >= comparisons. */
4317 else if ((code1 == GT_EXPR || code1 == GE_EXPR)
4318 && (code2 == GT_EXPR || code2 == GE_EXPR))
4320 if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
4321 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4322 else
4323 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4326 /* Check for singleton ranges. */
4327 else if (cmp == 0
4328 && ((code1 == LE_EXPR && code2 == GE_EXPR)
4329 || (code1 == GE_EXPR && code2 == LE_EXPR)))
4330 return fold_build2 (EQ_EXPR, boolean_type_node, op1a, op2b);
4332 /* Check for disjoint ranges. */
4333 else if (cmp <= 0
4334 && (code1 == LT_EXPR || code1 == LE_EXPR)
4335 && (code2 == GT_EXPR || code2 == GE_EXPR))
4336 return boolean_false_node;
4337 else if (cmp >= 0
4338 && (code1 == GT_EXPR || code1 == GE_EXPR)
4339 && (code2 == LT_EXPR || code2 == LE_EXPR))
4340 return boolean_false_node;
4343 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
4344 NAME's definition is a truth value. See if there are any simplifications
4345 that can be done against the NAME's definition. */
4346 if (TREE_CODE (op1a) == SSA_NAME
4347 && (code1 == NE_EXPR || code1 == EQ_EXPR)
4348 && (integer_zerop (op1b) || integer_onep (op1b)))
4350 bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
4351 || (code1 == NE_EXPR && integer_onep (op1b)));
4352 gimple stmt = SSA_NAME_DEF_STMT (op1a);
4353 switch (gimple_code (stmt))
4355 case GIMPLE_ASSIGN:
4356 /* Try to simplify by copy-propagating the definition. */
4357 return and_var_with_comparison (op1a, invert, code2, op2a, op2b);
4359 case GIMPLE_PHI:
4360 /* If every argument to the PHI produces the same result when
4361 ANDed with the second comparison, we win.
4362 Do not do this unless the type is bool since we need a bool
4363 result here anyway. */
4364 if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
4366 tree result = NULL_TREE;
4367 unsigned i;
4368 for (i = 0; i < gimple_phi_num_args (stmt); i++)
4370 tree arg = gimple_phi_arg_def (stmt, i);
4372 /* If this PHI has itself as an argument, ignore it.
4373 If all the other args produce the same result,
4374 we're still OK. */
4375 if (arg == gimple_phi_result (stmt))
4376 continue;
4377 else if (TREE_CODE (arg) == INTEGER_CST)
4379 if (invert ? integer_nonzerop (arg) : integer_zerop (arg))
4381 if (!result)
4382 result = boolean_false_node;
4383 else if (!integer_zerop (result))
4384 return NULL_TREE;
4386 else if (!result)
4387 result = fold_build2 (code2, boolean_type_node,
4388 op2a, op2b);
4389 else if (!same_bool_comparison_p (result,
4390 code2, op2a, op2b))
4391 return NULL_TREE;
4393 else if (TREE_CODE (arg) == SSA_NAME
4394 && !SSA_NAME_IS_DEFAULT_DEF (arg))
4396 tree temp;
4397 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
4398 /* In simple cases we can look through PHI nodes,
4399 but we have to be careful with loops.
4400 See PR49073. */
4401 if (! dom_info_available_p (CDI_DOMINATORS)
4402 || gimple_bb (def_stmt) == gimple_bb (stmt)
4403 || dominated_by_p (CDI_DOMINATORS,
4404 gimple_bb (def_stmt),
4405 gimple_bb (stmt)))
4406 return NULL_TREE;
4407 temp = and_var_with_comparison (arg, invert, code2,
4408 op2a, op2b);
4409 if (!temp)
4410 return NULL_TREE;
4411 else if (!result)
4412 result = temp;
4413 else if (!same_bool_result_p (result, temp))
4414 return NULL_TREE;
4416 else
4417 return NULL_TREE;
4419 return result;
4422 default:
4423 break;
4426 return NULL_TREE;
4429 /* Try to simplify the AND of two comparisons, specified by
4430 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
4431 If this can be simplified to a single expression (without requiring
4432 introducing more SSA variables to hold intermediate values),
4433 return the resulting tree. Otherwise return NULL_TREE.
4434 If the result expression is non-null, it has boolean type. */
4436 tree
4437 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
4438 enum tree_code code2, tree op2a, tree op2b)
4440 tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
4441 if (t)
4442 return t;
4443 else
4444 return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
4447 /* Helper function for or_comparisons_1: try to simplify the OR of the
4448 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
4449 If INVERT is true, invert the value of VAR before doing the OR.
4450 Return NULL_EXPR if we can't simplify this to a single expression. */
4452 static tree
4453 or_var_with_comparison (tree var, bool invert,
4454 enum tree_code code2, tree op2a, tree op2b)
4456 tree t;
4457 gimple stmt = SSA_NAME_DEF_STMT (var);
4459 /* We can only deal with variables whose definitions are assignments. */
4460 if (!is_gimple_assign (stmt))
4461 return NULL_TREE;
4463 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
4464 !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
4465 Then we only have to consider the simpler non-inverted cases. */
4466 if (invert)
4467 t = and_var_with_comparison_1 (stmt,
4468 invert_tree_comparison (code2, false),
4469 op2a, op2b);
4470 else
4471 t = or_var_with_comparison_1 (stmt, code2, op2a, op2b);
4472 return canonicalize_bool (t, invert);
4475 /* Try to simplify the OR of the ssa variable defined by the assignment
4476 STMT with the comparison specified by (OP2A CODE2 OP2B).
4477 Return NULL_EXPR if we can't simplify this to a single expression. */
4479 static tree
4480 or_var_with_comparison_1 (gimple stmt,
4481 enum tree_code code2, tree op2a, tree op2b)
4483 tree var = gimple_assign_lhs (stmt);
4484 tree true_test_var = NULL_TREE;
4485 tree false_test_var = NULL_TREE;
4486 enum tree_code innercode = gimple_assign_rhs_code (stmt);
4488 /* Check for identities like (var OR (var != 0)) => true . */
4489 if (TREE_CODE (op2a) == SSA_NAME
4490 && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
4492 if ((code2 == NE_EXPR && integer_zerop (op2b))
4493 || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
4495 true_test_var = op2a;
4496 if (var == true_test_var)
4497 return var;
4499 else if ((code2 == EQ_EXPR && integer_zerop (op2b))
4500 || (code2 == NE_EXPR && integer_nonzerop (op2b)))
4502 false_test_var = op2a;
4503 if (var == false_test_var)
4504 return boolean_true_node;
4508 /* If the definition is a comparison, recurse on it. */
4509 if (TREE_CODE_CLASS (innercode) == tcc_comparison)
4511 tree t = or_comparisons_1 (innercode,
4512 gimple_assign_rhs1 (stmt),
4513 gimple_assign_rhs2 (stmt),
4514 code2,
4515 op2a,
4516 op2b);
4517 if (t)
4518 return t;
4521 /* If the definition is an AND or OR expression, we may be able to
4522 simplify by reassociating. */
4523 if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
4524 && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
4526 tree inner1 = gimple_assign_rhs1 (stmt);
4527 tree inner2 = gimple_assign_rhs2 (stmt);
4528 gimple s;
4529 tree t;
4530 tree partial = NULL_TREE;
4531 bool is_or = (innercode == BIT_IOR_EXPR);
4533 /* Check for boolean identities that don't require recursive examination
4534 of inner1/inner2:
4535 inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
4536 inner1 OR (inner1 AND inner2) => inner1
4537 !inner1 OR (inner1 OR inner2) => true
4538 !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
4540 if (inner1 == true_test_var)
4541 return (is_or ? var : inner1);
4542 else if (inner2 == true_test_var)
4543 return (is_or ? var : inner2);
4544 else if (inner1 == false_test_var)
4545 return (is_or
4546 ? boolean_true_node
4547 : or_var_with_comparison (inner2, false, code2, op2a, op2b));
4548 else if (inner2 == false_test_var)
4549 return (is_or
4550 ? boolean_true_node
4551 : or_var_with_comparison (inner1, false, code2, op2a, op2b));
4553 /* Next, redistribute/reassociate the OR across the inner tests.
4554 Compute the first partial result, (inner1 OR (op2a code op2b)) */
4555 if (TREE_CODE (inner1) == SSA_NAME
4556 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
4557 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
4558 && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
4559 gimple_assign_rhs1 (s),
4560 gimple_assign_rhs2 (s),
4561 code2, op2a, op2b)))
4563 /* Handle the OR case, where we are reassociating:
4564 (inner1 OR inner2) OR (op2a code2 op2b)
4565 => (t OR inner2)
4566 If the partial result t is a constant, we win. Otherwise
4567 continue on to try reassociating with the other inner test. */
4568 if (is_or)
4570 if (integer_onep (t))
4571 return boolean_true_node;
4572 else if (integer_zerop (t))
4573 return inner2;
4576 /* Handle the AND case, where we are redistributing:
4577 (inner1 AND inner2) OR (op2a code2 op2b)
4578 => (t AND (inner2 OR (op2a code op2b))) */
4579 else if (integer_zerop (t))
4580 return boolean_false_node;
4582 /* Save partial result for later. */
4583 partial = t;
4586 /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
4587 if (TREE_CODE (inner2) == SSA_NAME
4588 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
4589 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
4590 && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
4591 gimple_assign_rhs1 (s),
4592 gimple_assign_rhs2 (s),
4593 code2, op2a, op2b)))
4595 /* Handle the OR case, where we are reassociating:
4596 (inner1 OR inner2) OR (op2a code2 op2b)
4597 => (inner1 OR t)
4598 => (t OR partial) */
4599 if (is_or)
4601 if (integer_zerop (t))
4602 return inner1;
4603 else if (integer_onep (t))
4604 return boolean_true_node;
4605 /* If both are the same, we can apply the identity
4606 (x OR x) == x. */
4607 else if (partial && same_bool_result_p (t, partial))
4608 return t;
4611 /* Handle the AND case, where we are redistributing:
4612 (inner1 AND inner2) OR (op2a code2 op2b)
4613 => (t AND (inner1 OR (op2a code2 op2b)))
4614 => (t AND partial) */
4615 else
4617 if (integer_zerop (t))
4618 return boolean_false_node;
4619 else if (partial)
4621 /* We already got a simplification for the other
4622 operand to the redistributed AND expression. The
4623 interesting case is when at least one is true.
4624 Or, if both are the same, we can apply the identity
4625 (x AND x) == x. */
4626 if (integer_onep (partial))
4627 return t;
4628 else if (integer_onep (t))
4629 return partial;
4630 else if (same_bool_result_p (t, partial))
4631 return t;
4636 return NULL_TREE;
4639 /* Try to simplify the OR of two comparisons defined by
4640 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
4641 If this can be done without constructing an intermediate value,
4642 return the resulting tree; otherwise NULL_TREE is returned.
4643 This function is deliberately asymmetric as it recurses on SSA_DEFs
4644 in the first comparison but not the second. */
4646 static tree
4647 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
4648 enum tree_code code2, tree op2a, tree op2b)
4650 tree truth_type = truth_type_for (TREE_TYPE (op1a));
4652 /* First check for ((x CODE1 y) OR (x CODE2 y)). */
4653 if (operand_equal_p (op1a, op2a, 0)
4654 && operand_equal_p (op1b, op2b, 0))
4656 /* Result will be either NULL_TREE, or a combined comparison. */
4657 tree t = combine_comparisons (UNKNOWN_LOCATION,
4658 TRUTH_ORIF_EXPR, code1, code2,
4659 truth_type, op1a, op1b);
4660 if (t)
4661 return t;
4664 /* Likewise the swapped case of the above. */
4665 if (operand_equal_p (op1a, op2b, 0)
4666 && operand_equal_p (op1b, op2a, 0))
4668 /* Result will be either NULL_TREE, or a combined comparison. */
4669 tree t = combine_comparisons (UNKNOWN_LOCATION,
4670 TRUTH_ORIF_EXPR, code1,
4671 swap_tree_comparison (code2),
4672 truth_type, op1a, op1b);
4673 if (t)
4674 return t;
4677 /* If both comparisons are of the same value against constants, we might
4678 be able to merge them. */
4679 if (operand_equal_p (op1a, op2a, 0)
4680 && TREE_CODE (op1b) == INTEGER_CST
4681 && TREE_CODE (op2b) == INTEGER_CST)
4683 int cmp = tree_int_cst_compare (op1b, op2b);
4685 /* If we have (op1a != op1b), we should either be able to
4686 return that or TRUE, depending on whether the constant op1b
4687 also satisfies the other comparison against op2b. */
4688 if (code1 == NE_EXPR)
4690 bool done = true;
4691 bool val;
4692 switch (code2)
4694 case EQ_EXPR: val = (cmp == 0); break;
4695 case NE_EXPR: val = (cmp != 0); break;
4696 case LT_EXPR: val = (cmp < 0); break;
4697 case GT_EXPR: val = (cmp > 0); break;
4698 case LE_EXPR: val = (cmp <= 0); break;
4699 case GE_EXPR: val = (cmp >= 0); break;
4700 default: done = false;
4702 if (done)
4704 if (val)
4705 return boolean_true_node;
4706 else
4707 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4710 /* Likewise if the second comparison is a != comparison. */
4711 else if (code2 == NE_EXPR)
4713 bool done = true;
4714 bool val;
4715 switch (code1)
4717 case EQ_EXPR: val = (cmp == 0); break;
4718 case NE_EXPR: val = (cmp != 0); break;
4719 case LT_EXPR: val = (cmp > 0); break;
4720 case GT_EXPR: val = (cmp < 0); break;
4721 case LE_EXPR: val = (cmp >= 0); break;
4722 case GE_EXPR: val = (cmp <= 0); break;
4723 default: done = false;
4725 if (done)
4727 if (val)
4728 return boolean_true_node;
4729 else
4730 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4734 /* See if an equality test is redundant with the other comparison. */
4735 else if (code1 == EQ_EXPR)
4737 bool val;
4738 switch (code2)
4740 case EQ_EXPR: val = (cmp == 0); break;
4741 case NE_EXPR: val = (cmp != 0); break;
4742 case LT_EXPR: val = (cmp < 0); break;
4743 case GT_EXPR: val = (cmp > 0); break;
4744 case LE_EXPR: val = (cmp <= 0); break;
4745 case GE_EXPR: val = (cmp >= 0); break;
4746 default:
4747 val = false;
4749 if (val)
4750 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4752 else if (code2 == EQ_EXPR)
4754 bool val;
4755 switch (code1)
4757 case EQ_EXPR: val = (cmp == 0); break;
4758 case NE_EXPR: val = (cmp != 0); break;
4759 case LT_EXPR: val = (cmp > 0); break;
4760 case GT_EXPR: val = (cmp < 0); break;
4761 case LE_EXPR: val = (cmp >= 0); break;
4762 case GE_EXPR: val = (cmp <= 0); break;
4763 default:
4764 val = false;
4766 if (val)
4767 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4770 /* Chose the less restrictive of two < or <= comparisons. */
4771 else if ((code1 == LT_EXPR || code1 == LE_EXPR)
4772 && (code2 == LT_EXPR || code2 == LE_EXPR))
4774 if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
4775 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4776 else
4777 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4780 /* Likewise chose the less restrictive of two > or >= comparisons. */
4781 else if ((code1 == GT_EXPR || code1 == GE_EXPR)
4782 && (code2 == GT_EXPR || code2 == GE_EXPR))
4784 if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
4785 return fold_build2 (code2, boolean_type_node, op2a, op2b);
4786 else
4787 return fold_build2 (code1, boolean_type_node, op1a, op1b);
4790 /* Check for singleton ranges. */
4791 else if (cmp == 0
4792 && ((code1 == LT_EXPR && code2 == GT_EXPR)
4793 || (code1 == GT_EXPR && code2 == LT_EXPR)))
4794 return fold_build2 (NE_EXPR, boolean_type_node, op1a, op2b);
4796 /* Check for less/greater pairs that don't restrict the range at all. */
4797 else if (cmp >= 0
4798 && (code1 == LT_EXPR || code1 == LE_EXPR)
4799 && (code2 == GT_EXPR || code2 == GE_EXPR))
4800 return boolean_true_node;
4801 else if (cmp <= 0
4802 && (code1 == GT_EXPR || code1 == GE_EXPR)
4803 && (code2 == LT_EXPR || code2 == LE_EXPR))
4804 return boolean_true_node;
4807 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
4808 NAME's definition is a truth value. See if there are any simplifications
4809 that can be done against the NAME's definition. */
4810 if (TREE_CODE (op1a) == SSA_NAME
4811 && (code1 == NE_EXPR || code1 == EQ_EXPR)
4812 && (integer_zerop (op1b) || integer_onep (op1b)))
4814 bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
4815 || (code1 == NE_EXPR && integer_onep (op1b)));
4816 gimple stmt = SSA_NAME_DEF_STMT (op1a);
4817 switch (gimple_code (stmt))
4819 case GIMPLE_ASSIGN:
4820 /* Try to simplify by copy-propagating the definition. */
4821 return or_var_with_comparison (op1a, invert, code2, op2a, op2b);
4823 case GIMPLE_PHI:
4824 /* If every argument to the PHI produces the same result when
4825 ORed with the second comparison, we win.
4826 Do not do this unless the type is bool since we need a bool
4827 result here anyway. */
4828 if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
4830 tree result = NULL_TREE;
4831 unsigned i;
4832 for (i = 0; i < gimple_phi_num_args (stmt); i++)
4834 tree arg = gimple_phi_arg_def (stmt, i);
4836 /* If this PHI has itself as an argument, ignore it.
4837 If all the other args produce the same result,
4838 we're still OK. */
4839 if (arg == gimple_phi_result (stmt))
4840 continue;
4841 else if (TREE_CODE (arg) == INTEGER_CST)
4843 if (invert ? integer_zerop (arg) : integer_nonzerop (arg))
4845 if (!result)
4846 result = boolean_true_node;
4847 else if (!integer_onep (result))
4848 return NULL_TREE;
4850 else if (!result)
4851 result = fold_build2 (code2, boolean_type_node,
4852 op2a, op2b);
4853 else if (!same_bool_comparison_p (result,
4854 code2, op2a, op2b))
4855 return NULL_TREE;
4857 else if (TREE_CODE (arg) == SSA_NAME
4858 && !SSA_NAME_IS_DEFAULT_DEF (arg))
4860 tree temp;
4861 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
4862 /* In simple cases we can look through PHI nodes,
4863 but we have to be careful with loops.
4864 See PR49073. */
4865 if (! dom_info_available_p (CDI_DOMINATORS)
4866 || gimple_bb (def_stmt) == gimple_bb (stmt)
4867 || dominated_by_p (CDI_DOMINATORS,
4868 gimple_bb (def_stmt),
4869 gimple_bb (stmt)))
4870 return NULL_TREE;
4871 temp = or_var_with_comparison (arg, invert, code2,
4872 op2a, op2b);
4873 if (!temp)
4874 return NULL_TREE;
4875 else if (!result)
4876 result = temp;
4877 else if (!same_bool_result_p (result, temp))
4878 return NULL_TREE;
4880 else
4881 return NULL_TREE;
4883 return result;
4886 default:
4887 break;
4890 return NULL_TREE;
4893 /* Try to simplify the OR of two comparisons, specified by
4894 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
4895 If this can be simplified to a single expression (without requiring
4896 introducing more SSA variables to hold intermediate values),
4897 return the resulting tree. Otherwise return NULL_TREE.
4898 If the result expression is non-null, it has boolean type. */
4900 tree
4901 maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
4902 enum tree_code code2, tree op2a, tree op2b)
4904 tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
4905 if (t)
4906 return t;
4907 else
4908 return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
4912 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
4914 Either NULL_TREE, a simplified but non-constant or a constant
4915 is returned.
4917 ??? This should go into a gimple-fold-inline.h file to be eventually
4918 privatized with the single valueize function used in the various TUs
4919 to avoid the indirect function call overhead. */
4921 tree
4922 gimple_fold_stmt_to_constant_1 (gimple stmt, tree (*valueize) (tree),
4923 tree (*gvalueize) (tree))
4925 code_helper rcode;
4926 tree ops[3] = {};
4927 /* ??? The SSA propagators do not correctly deal with following SSA use-def
4928 edges if there are intermediate VARYING defs. For this reason
4929 do not follow SSA edges here even though SCCVN can technically
4930 just deal fine with that. */
4931 if (gimple_simplify (stmt, &rcode, ops, NULL, gvalueize)
4932 && rcode.is_tree_code ()
4933 && (TREE_CODE_LENGTH ((tree_code) rcode) == 0
4934 || ((tree_code) rcode) == ADDR_EXPR)
4935 && is_gimple_val (ops[0]))
4937 tree res = ops[0];
4938 if (dump_file && dump_flags & TDF_DETAILS)
4940 fprintf (dump_file, "Match-and-simplified ");
4941 print_gimple_expr (dump_file, stmt, 0, TDF_SLIM);
4942 fprintf (dump_file, " to ");
4943 print_generic_expr (dump_file, res, 0);
4944 fprintf (dump_file, "\n");
4946 return res;
4949 location_t loc = gimple_location (stmt);
4950 switch (gimple_code (stmt))
4952 case GIMPLE_ASSIGN:
4954 enum tree_code subcode = gimple_assign_rhs_code (stmt);
4956 switch (get_gimple_rhs_class (subcode))
4958 case GIMPLE_SINGLE_RHS:
4960 tree rhs = gimple_assign_rhs1 (stmt);
4961 enum tree_code_class kind = TREE_CODE_CLASS (subcode);
4963 if (TREE_CODE (rhs) == SSA_NAME)
4965 /* If the RHS is an SSA_NAME, return its known constant value,
4966 if any. */
4967 return (*valueize) (rhs);
4969 /* Handle propagating invariant addresses into address
4970 operations. */
4971 else if (TREE_CODE (rhs) == ADDR_EXPR
4972 && !is_gimple_min_invariant (rhs))
4974 HOST_WIDE_INT offset = 0;
4975 tree base;
4976 base = get_addr_base_and_unit_offset_1 (TREE_OPERAND (rhs, 0),
4977 &offset,
4978 valueize);
4979 if (base
4980 && (CONSTANT_CLASS_P (base)
4981 || decl_address_invariant_p (base)))
4982 return build_invariant_address (TREE_TYPE (rhs),
4983 base, offset);
4985 else if (TREE_CODE (rhs) == CONSTRUCTOR
4986 && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
4987 && (CONSTRUCTOR_NELTS (rhs)
4988 == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
4990 unsigned i;
4991 tree val, *vec;
4993 vec = XALLOCAVEC (tree,
4994 TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs)));
4995 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
4997 val = (*valueize) (val);
4998 if (TREE_CODE (val) == INTEGER_CST
4999 || TREE_CODE (val) == REAL_CST
5000 || TREE_CODE (val) == FIXED_CST)
5001 vec[i] = val;
5002 else
5003 return NULL_TREE;
5006 return build_vector (TREE_TYPE (rhs), vec);
5008 if (subcode == OBJ_TYPE_REF)
5010 tree val = (*valueize) (OBJ_TYPE_REF_EXPR (rhs));
5011 /* If callee is constant, we can fold away the wrapper. */
5012 if (is_gimple_min_invariant (val))
5013 return val;
5016 if (kind == tcc_reference)
5018 if ((TREE_CODE (rhs) == VIEW_CONVERT_EXPR
5019 || TREE_CODE (rhs) == REALPART_EXPR
5020 || TREE_CODE (rhs) == IMAGPART_EXPR)
5021 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
5023 tree val = (*valueize) (TREE_OPERAND (rhs, 0));
5024 return fold_unary_loc (EXPR_LOCATION (rhs),
5025 TREE_CODE (rhs),
5026 TREE_TYPE (rhs), val);
5028 else if (TREE_CODE (rhs) == BIT_FIELD_REF
5029 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
5031 tree val = (*valueize) (TREE_OPERAND (rhs, 0));
5032 return fold_ternary_loc (EXPR_LOCATION (rhs),
5033 TREE_CODE (rhs),
5034 TREE_TYPE (rhs), val,
5035 TREE_OPERAND (rhs, 1),
5036 TREE_OPERAND (rhs, 2));
5038 else if (TREE_CODE (rhs) == MEM_REF
5039 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
5041 tree val = (*valueize) (TREE_OPERAND (rhs, 0));
5042 if (TREE_CODE (val) == ADDR_EXPR
5043 && is_gimple_min_invariant (val))
5045 tree tem = fold_build2 (MEM_REF, TREE_TYPE (rhs),
5046 unshare_expr (val),
5047 TREE_OPERAND (rhs, 1));
5048 if (tem)
5049 rhs = tem;
5052 return fold_const_aggregate_ref_1 (rhs, valueize);
5054 else if (kind == tcc_declaration)
5055 return get_symbol_constant_value (rhs);
5056 return rhs;
5059 case GIMPLE_UNARY_RHS:
5060 return NULL_TREE;
5062 case GIMPLE_BINARY_RHS:
5064 /* Handle binary operators that can appear in GIMPLE form. */
5065 tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
5066 tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
5068 /* Translate &x + CST into an invariant form suitable for
5069 further propagation. */
5070 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
5071 && TREE_CODE (op0) == ADDR_EXPR
5072 && TREE_CODE (op1) == INTEGER_CST)
5074 tree off = fold_convert (ptr_type_node, op1);
5075 return build_fold_addr_expr_loc
5076 (loc,
5077 fold_build2 (MEM_REF,
5078 TREE_TYPE (TREE_TYPE (op0)),
5079 unshare_expr (op0), off));
5082 return fold_binary_loc (loc, subcode,
5083 gimple_expr_type (stmt), op0, op1);
5086 case GIMPLE_TERNARY_RHS:
5088 /* Handle ternary operators that can appear in GIMPLE form. */
5089 tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
5090 tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
5091 tree op2 = (*valueize) (gimple_assign_rhs3 (stmt));
5093 /* Fold embedded expressions in ternary codes. */
5094 if ((subcode == COND_EXPR
5095 || subcode == VEC_COND_EXPR)
5096 && COMPARISON_CLASS_P (op0))
5098 tree op00 = (*valueize) (TREE_OPERAND (op0, 0));
5099 tree op01 = (*valueize) (TREE_OPERAND (op0, 1));
5100 tree tem = fold_binary_loc (loc, TREE_CODE (op0),
5101 TREE_TYPE (op0), op00, op01);
5102 if (tem)
5103 op0 = tem;
5106 return fold_ternary_loc (loc, subcode,
5107 gimple_expr_type (stmt), op0, op1, op2);
5110 default:
5111 gcc_unreachable ();
5115 case GIMPLE_CALL:
5117 tree fn;
5118 gcall *call_stmt = as_a <gcall *> (stmt);
5120 if (gimple_call_internal_p (stmt))
5122 enum tree_code subcode = ERROR_MARK;
5123 switch (gimple_call_internal_fn (stmt))
5125 case IFN_UBSAN_CHECK_ADD:
5126 subcode = PLUS_EXPR;
5127 break;
5128 case IFN_UBSAN_CHECK_SUB:
5129 subcode = MINUS_EXPR;
5130 break;
5131 case IFN_UBSAN_CHECK_MUL:
5132 subcode = MULT_EXPR;
5133 break;
5134 default:
5135 return NULL_TREE;
5137 tree arg0 = gimple_call_arg (stmt, 0);
5138 tree arg1 = gimple_call_arg (stmt, 1);
5139 tree op0 = (*valueize) (arg0);
5140 tree op1 = (*valueize) (arg1);
5142 if (TREE_CODE (op0) != INTEGER_CST
5143 || TREE_CODE (op1) != INTEGER_CST)
5145 switch (subcode)
5147 case MULT_EXPR:
5148 /* x * 0 = 0 * x = 0 without overflow. */
5149 if (integer_zerop (op0) || integer_zerop (op1))
5150 return build_zero_cst (TREE_TYPE (arg0));
5151 break;
5152 case MINUS_EXPR:
5153 /* y - y = 0 without overflow. */
5154 if (operand_equal_p (op0, op1, 0))
5155 return build_zero_cst (TREE_TYPE (arg0));
5156 break;
5157 default:
5158 break;
5161 tree res
5162 = fold_binary_loc (loc, subcode, TREE_TYPE (arg0), op0, op1);
5163 if (res
5164 && TREE_CODE (res) == INTEGER_CST
5165 && !TREE_OVERFLOW (res))
5166 return res;
5167 return NULL_TREE;
5170 fn = (*valueize) (gimple_call_fn (stmt));
5171 if (TREE_CODE (fn) == ADDR_EXPR
5172 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
5173 && DECL_BUILT_IN (TREE_OPERAND (fn, 0))
5174 && gimple_builtin_call_types_compatible_p (stmt,
5175 TREE_OPERAND (fn, 0)))
5177 tree *args = XALLOCAVEC (tree, gimple_call_num_args (stmt));
5178 tree retval;
5179 unsigned i;
5180 for (i = 0; i < gimple_call_num_args (stmt); ++i)
5181 args[i] = (*valueize) (gimple_call_arg (stmt, i));
5182 retval = fold_builtin_call_array (loc,
5183 gimple_call_return_type (call_stmt),
5184 fn, gimple_call_num_args (stmt), args);
5185 if (retval)
5187 /* fold_call_expr wraps the result inside a NOP_EXPR. */
5188 STRIP_NOPS (retval);
5189 retval = fold_convert (gimple_call_return_type (call_stmt),
5190 retval);
5192 return retval;
5194 return NULL_TREE;
5197 default:
5198 return NULL_TREE;
5202 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
5203 Returns NULL_TREE if folding to a constant is not possible, otherwise
5204 returns a constant according to is_gimple_min_invariant. */
5206 tree
5207 gimple_fold_stmt_to_constant (gimple stmt, tree (*valueize) (tree))
5209 tree res = gimple_fold_stmt_to_constant_1 (stmt, valueize);
5210 if (res && is_gimple_min_invariant (res))
5211 return res;
5212 return NULL_TREE;
5216 /* The following set of functions are supposed to fold references using
5217 their constant initializers. */
5219 /* See if we can find constructor defining value of BASE.
5220 When we know the consructor with constant offset (such as
5221 base is array[40] and we do know constructor of array), then
5222 BIT_OFFSET is adjusted accordingly.
5224 As a special case, return error_mark_node when constructor
5225 is not explicitly available, but it is known to be zero
5226 such as 'static const int a;'. */
5227 static tree
5228 get_base_constructor (tree base, HOST_WIDE_INT *bit_offset,
5229 tree (*valueize)(tree))
5231 HOST_WIDE_INT bit_offset2, size, max_size;
5232 if (TREE_CODE (base) == MEM_REF)
5234 if (!integer_zerop (TREE_OPERAND (base, 1)))
5236 if (!tree_fits_shwi_p (TREE_OPERAND (base, 1)))
5237 return NULL_TREE;
5238 *bit_offset += (mem_ref_offset (base).to_short_addr ()
5239 * BITS_PER_UNIT);
5242 if (valueize
5243 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
5244 base = valueize (TREE_OPERAND (base, 0));
5245 if (!base || TREE_CODE (base) != ADDR_EXPR)
5246 return NULL_TREE;
5247 base = TREE_OPERAND (base, 0);
5250 /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
5251 DECL_INITIAL. If BASE is a nested reference into another
5252 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
5253 the inner reference. */
5254 switch (TREE_CODE (base))
5256 case VAR_DECL:
5257 case CONST_DECL:
5259 tree init = ctor_for_folding (base);
5261 /* Our semantic is exact opposite of ctor_for_folding;
5262 NULL means unknown, while error_mark_node is 0. */
5263 if (init == error_mark_node)
5264 return NULL_TREE;
5265 if (!init)
5266 return error_mark_node;
5267 return init;
5270 case ARRAY_REF:
5271 case COMPONENT_REF:
5272 base = get_ref_base_and_extent (base, &bit_offset2, &size, &max_size);
5273 if (max_size == -1 || size != max_size)
5274 return NULL_TREE;
5275 *bit_offset += bit_offset2;
5276 return get_base_constructor (base, bit_offset, valueize);
5278 case STRING_CST:
5279 case CONSTRUCTOR:
5280 return base;
5282 default:
5283 return NULL_TREE;
5287 /* CTOR is CONSTRUCTOR of an array type. Fold reference of type TYPE and size
5288 SIZE to the memory at bit OFFSET. */
5290 static tree
5291 fold_array_ctor_reference (tree type, tree ctor,
5292 unsigned HOST_WIDE_INT offset,
5293 unsigned HOST_WIDE_INT size,
5294 tree from_decl)
5296 unsigned HOST_WIDE_INT cnt;
5297 tree cfield, cval;
5298 offset_int low_bound;
5299 offset_int elt_size;
5300 offset_int index, max_index;
5301 offset_int access_index;
5302 tree domain_type = NULL_TREE, index_type = NULL_TREE;
5303 HOST_WIDE_INT inner_offset;
5305 /* Compute low bound and elt size. */
5306 if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE)
5307 domain_type = TYPE_DOMAIN (TREE_TYPE (ctor));
5308 if (domain_type && TYPE_MIN_VALUE (domain_type))
5310 /* Static constructors for variably sized objects makes no sense. */
5311 gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
5312 index_type = TREE_TYPE (TYPE_MIN_VALUE (domain_type));
5313 low_bound = wi::to_offset (TYPE_MIN_VALUE (domain_type));
5315 else
5316 low_bound = 0;
5317 /* Static constructors for variably sized objects makes no sense. */
5318 gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))))
5319 == INTEGER_CST);
5320 elt_size = wi::to_offset (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))));
5322 /* We can handle only constantly sized accesses that are known to not
5323 be larger than size of array element. */
5324 if (!TYPE_SIZE_UNIT (type)
5325 || TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST
5326 || wi::lts_p (elt_size, wi::to_offset (TYPE_SIZE_UNIT (type)))
5327 || elt_size == 0)
5328 return NULL_TREE;
5330 /* Compute the array index we look for. */
5331 access_index = wi::udiv_trunc (offset_int (offset / BITS_PER_UNIT),
5332 elt_size);
5333 access_index += low_bound;
5334 if (index_type)
5335 access_index = wi::ext (access_index, TYPE_PRECISION (index_type),
5336 TYPE_SIGN (index_type));
5338 /* And offset within the access. */
5339 inner_offset = offset % (elt_size.to_uhwi () * BITS_PER_UNIT);
5341 /* See if the array field is large enough to span whole access. We do not
5342 care to fold accesses spanning multiple array indexes. */
5343 if (inner_offset + size > elt_size.to_uhwi () * BITS_PER_UNIT)
5344 return NULL_TREE;
5346 index = low_bound - 1;
5347 if (index_type)
5348 index = wi::ext (index, TYPE_PRECISION (index_type),
5349 TYPE_SIGN (index_type));
5351 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
5353 /* Array constructor might explicitely set index, or specify range
5354 or leave index NULL meaning that it is next index after previous
5355 one. */
5356 if (cfield)
5358 if (TREE_CODE (cfield) == INTEGER_CST)
5359 max_index = index = wi::to_offset (cfield);
5360 else
5362 gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
5363 index = wi::to_offset (TREE_OPERAND (cfield, 0));
5364 max_index = wi::to_offset (TREE_OPERAND (cfield, 1));
5367 else
5369 index += 1;
5370 if (index_type)
5371 index = wi::ext (index, TYPE_PRECISION (index_type),
5372 TYPE_SIGN (index_type));
5373 max_index = index;
5376 /* Do we have match? */
5377 if (wi::cmpu (access_index, index) >= 0
5378 && wi::cmpu (access_index, max_index) <= 0)
5379 return fold_ctor_reference (type, cval, inner_offset, size,
5380 from_decl);
5382 /* When memory is not explicitely mentioned in constructor,
5383 it is 0 (or out of range). */
5384 return build_zero_cst (type);
5387 /* CTOR is CONSTRUCTOR of an aggregate or vector.
5388 Fold reference of type TYPE and size SIZE to the memory at bit OFFSET. */
5390 static tree
5391 fold_nonarray_ctor_reference (tree type, tree ctor,
5392 unsigned HOST_WIDE_INT offset,
5393 unsigned HOST_WIDE_INT size,
5394 tree from_decl)
5396 unsigned HOST_WIDE_INT cnt;
5397 tree cfield, cval;
5399 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield,
5400 cval)
5402 tree byte_offset = DECL_FIELD_OFFSET (cfield);
5403 tree field_offset = DECL_FIELD_BIT_OFFSET (cfield);
5404 tree field_size = DECL_SIZE (cfield);
5405 offset_int bitoffset;
5406 offset_int bitoffset_end, access_end;
5408 /* Variable sized objects in static constructors makes no sense,
5409 but field_size can be NULL for flexible array members. */
5410 gcc_assert (TREE_CODE (field_offset) == INTEGER_CST
5411 && TREE_CODE (byte_offset) == INTEGER_CST
5412 && (field_size != NULL_TREE
5413 ? TREE_CODE (field_size) == INTEGER_CST
5414 : TREE_CODE (TREE_TYPE (cfield)) == ARRAY_TYPE));
5416 /* Compute bit offset of the field. */
5417 bitoffset = (wi::to_offset (field_offset)
5418 + wi::lshift (wi::to_offset (byte_offset),
5419 LOG2_BITS_PER_UNIT));
5420 /* Compute bit offset where the field ends. */
5421 if (field_size != NULL_TREE)
5422 bitoffset_end = bitoffset + wi::to_offset (field_size);
5423 else
5424 bitoffset_end = 0;
5426 access_end = offset_int (offset) + size;
5428 /* Is there any overlap between [OFFSET, OFFSET+SIZE) and
5429 [BITOFFSET, BITOFFSET_END)? */
5430 if (wi::cmps (access_end, bitoffset) > 0
5431 && (field_size == NULL_TREE
5432 || wi::lts_p (offset, bitoffset_end)))
5434 offset_int inner_offset = offset_int (offset) - bitoffset;
5435 /* We do have overlap. Now see if field is large enough to
5436 cover the access. Give up for accesses spanning multiple
5437 fields. */
5438 if (wi::cmps (access_end, bitoffset_end) > 0)
5439 return NULL_TREE;
5440 if (wi::lts_p (offset, bitoffset))
5441 return NULL_TREE;
5442 return fold_ctor_reference (type, cval,
5443 inner_offset.to_uhwi (), size,
5444 from_decl);
5447 /* When memory is not explicitely mentioned in constructor, it is 0. */
5448 return build_zero_cst (type);
5451 /* CTOR is value initializing memory, fold reference of type TYPE and size SIZE
5452 to the memory at bit OFFSET. */
5454 tree
5455 fold_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
5456 unsigned HOST_WIDE_INT size, tree from_decl)
5458 tree ret;
5460 /* We found the field with exact match. */
5461 if (useless_type_conversion_p (type, TREE_TYPE (ctor))
5462 && !offset)
5463 return canonicalize_constructor_val (unshare_expr (ctor), from_decl);
5465 /* We are at the end of walk, see if we can view convert the
5466 result. */
5467 if (!AGGREGATE_TYPE_P (TREE_TYPE (ctor)) && !offset
5468 /* VIEW_CONVERT_EXPR is defined only for matching sizes. */
5469 && !compare_tree_int (TYPE_SIZE (type), size)
5470 && !compare_tree_int (TYPE_SIZE (TREE_TYPE (ctor)), size))
5472 ret = canonicalize_constructor_val (unshare_expr (ctor), from_decl);
5473 ret = fold_unary (VIEW_CONVERT_EXPR, type, ret);
5474 if (ret)
5475 STRIP_NOPS (ret);
5476 return ret;
5478 /* For constants and byte-aligned/sized reads try to go through
5479 native_encode/interpret. */
5480 if (CONSTANT_CLASS_P (ctor)
5481 && BITS_PER_UNIT == 8
5482 && offset % BITS_PER_UNIT == 0
5483 && size % BITS_PER_UNIT == 0
5484 && size <= MAX_BITSIZE_MODE_ANY_MODE)
5486 unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT];
5487 if (native_encode_expr (ctor, buf, size / BITS_PER_UNIT,
5488 offset / BITS_PER_UNIT) > 0)
5489 return native_interpret_expr (type, buf, size / BITS_PER_UNIT);
5491 if (TREE_CODE (ctor) == CONSTRUCTOR)
5494 if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE
5495 || TREE_CODE (TREE_TYPE (ctor)) == VECTOR_TYPE)
5496 return fold_array_ctor_reference (type, ctor, offset, size,
5497 from_decl);
5498 else
5499 return fold_nonarray_ctor_reference (type, ctor, offset, size,
5500 from_decl);
5503 return NULL_TREE;
5506 /* Return the tree representing the element referenced by T if T is an
5507 ARRAY_REF or COMPONENT_REF into constant aggregates valuezing SSA
5508 names using VALUEIZE. Return NULL_TREE otherwise. */
5510 tree
5511 fold_const_aggregate_ref_1 (tree t, tree (*valueize) (tree))
5513 tree ctor, idx, base;
5514 HOST_WIDE_INT offset, size, max_size;
5515 tree tem;
5517 if (TREE_THIS_VOLATILE (t))
5518 return NULL_TREE;
5520 if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
5521 return get_symbol_constant_value (t);
5523 tem = fold_read_from_constant_string (t);
5524 if (tem)
5525 return tem;
5527 switch (TREE_CODE (t))
5529 case ARRAY_REF:
5530 case ARRAY_RANGE_REF:
5531 /* Constant indexes are handled well by get_base_constructor.
5532 Only special case variable offsets.
5533 FIXME: This code can't handle nested references with variable indexes
5534 (they will be handled only by iteration of ccp). Perhaps we can bring
5535 get_ref_base_and_extent here and make it use a valueize callback. */
5536 if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME
5537 && valueize
5538 && (idx = (*valueize) (TREE_OPERAND (t, 1)))
5539 && TREE_CODE (idx) == INTEGER_CST)
5541 tree low_bound, unit_size;
5543 /* If the resulting bit-offset is constant, track it. */
5544 if ((low_bound = array_ref_low_bound (t),
5545 TREE_CODE (low_bound) == INTEGER_CST)
5546 && (unit_size = array_ref_element_size (t),
5547 tree_fits_uhwi_p (unit_size)))
5549 offset_int woffset
5550 = wi::sext (wi::to_offset (idx) - wi::to_offset (low_bound),
5551 TYPE_PRECISION (TREE_TYPE (idx)));
5553 if (wi::fits_shwi_p (woffset))
5555 offset = woffset.to_shwi ();
5556 /* TODO: This code seems wrong, multiply then check
5557 to see if it fits. */
5558 offset *= tree_to_uhwi (unit_size);
5559 offset *= BITS_PER_UNIT;
5561 base = TREE_OPERAND (t, 0);
5562 ctor = get_base_constructor (base, &offset, valueize);
5563 /* Empty constructor. Always fold to 0. */
5564 if (ctor == error_mark_node)
5565 return build_zero_cst (TREE_TYPE (t));
5566 /* Out of bound array access. Value is undefined,
5567 but don't fold. */
5568 if (offset < 0)
5569 return NULL_TREE;
5570 /* We can not determine ctor. */
5571 if (!ctor)
5572 return NULL_TREE;
5573 return fold_ctor_reference (TREE_TYPE (t), ctor, offset,
5574 tree_to_uhwi (unit_size)
5575 * BITS_PER_UNIT,
5576 base);
5580 /* Fallthru. */
5582 case COMPONENT_REF:
5583 case BIT_FIELD_REF:
5584 case TARGET_MEM_REF:
5585 case MEM_REF:
5586 base = get_ref_base_and_extent (t, &offset, &size, &max_size);
5587 ctor = get_base_constructor (base, &offset, valueize);
5589 /* Empty constructor. Always fold to 0. */
5590 if (ctor == error_mark_node)
5591 return build_zero_cst (TREE_TYPE (t));
5592 /* We do not know precise address. */
5593 if (max_size == -1 || max_size != size)
5594 return NULL_TREE;
5595 /* We can not determine ctor. */
5596 if (!ctor)
5597 return NULL_TREE;
5599 /* Out of bound array access. Value is undefined, but don't fold. */
5600 if (offset < 0)
5601 return NULL_TREE;
5603 return fold_ctor_reference (TREE_TYPE (t), ctor, offset, size,
5604 base);
5606 case REALPART_EXPR:
5607 case IMAGPART_EXPR:
5609 tree c = fold_const_aggregate_ref_1 (TREE_OPERAND (t, 0), valueize);
5610 if (c && TREE_CODE (c) == COMPLEX_CST)
5611 return fold_build1_loc (EXPR_LOCATION (t),
5612 TREE_CODE (t), TREE_TYPE (t), c);
5613 break;
5616 default:
5617 break;
5620 return NULL_TREE;
5623 tree
5624 fold_const_aggregate_ref (tree t)
5626 return fold_const_aggregate_ref_1 (t, NULL);
5629 /* Lookup virtual method with index TOKEN in a virtual table V
5630 at OFFSET.
5631 Set CAN_REFER if non-NULL to false if method
5632 is not referable or if the virtual table is ill-formed (such as rewriten
5633 by non-C++ produced symbol). Otherwise just return NULL in that calse. */
5635 tree
5636 gimple_get_virt_method_for_vtable (HOST_WIDE_INT token,
5637 tree v,
5638 unsigned HOST_WIDE_INT offset,
5639 bool *can_refer)
5641 tree vtable = v, init, fn;
5642 unsigned HOST_WIDE_INT size;
5643 unsigned HOST_WIDE_INT elt_size, access_index;
5644 tree domain_type;
5646 if (can_refer)
5647 *can_refer = true;
5649 /* First of all double check we have virtual table. */
5650 if (TREE_CODE (v) != VAR_DECL
5651 || !DECL_VIRTUAL_P (v))
5653 /* Pass down that we lost track of the target. */
5654 if (can_refer)
5655 *can_refer = false;
5656 return NULL_TREE;
5659 init = ctor_for_folding (v);
5661 /* The virtual tables should always be born with constructors
5662 and we always should assume that they are avaialble for
5663 folding. At the moment we do not stream them in all cases,
5664 but it should never happen that ctor seem unreachable. */
5665 gcc_assert (init);
5666 if (init == error_mark_node)
5668 gcc_assert (in_lto_p);
5669 /* Pass down that we lost track of the target. */
5670 if (can_refer)
5671 *can_refer = false;
5672 return NULL_TREE;
5674 gcc_checking_assert (TREE_CODE (TREE_TYPE (v)) == ARRAY_TYPE);
5675 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (v))));
5676 offset *= BITS_PER_UNIT;
5677 offset += token * size;
5679 /* Lookup the value in the constructor that is assumed to be array.
5680 This is equivalent to
5681 fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), init,
5682 offset, size, NULL);
5683 but in a constant time. We expect that frontend produced a simple
5684 array without indexed initializers. */
5686 gcc_checking_assert (TREE_CODE (TREE_TYPE (init)) == ARRAY_TYPE);
5687 domain_type = TYPE_DOMAIN (TREE_TYPE (init));
5688 gcc_checking_assert (integer_zerop (TYPE_MIN_VALUE (domain_type)));
5689 elt_size = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (init))));
5691 access_index = offset / BITS_PER_UNIT / elt_size;
5692 gcc_checking_assert (offset % (elt_size * BITS_PER_UNIT) == 0);
5694 /* This code makes an assumption that there are no
5695 indexed fileds produced by C++ FE, so we can directly index the array. */
5696 if (access_index < CONSTRUCTOR_NELTS (init))
5698 fn = CONSTRUCTOR_ELT (init, access_index)->value;
5699 gcc_checking_assert (!CONSTRUCTOR_ELT (init, access_index)->index);
5700 STRIP_NOPS (fn);
5702 else
5703 fn = NULL;
5705 /* For type inconsistent program we may end up looking up virtual method
5706 in virtual table that does not contain TOKEN entries. We may overrun
5707 the virtual table and pick up a constant or RTTI info pointer.
5708 In any case the call is undefined. */
5709 if (!fn
5710 || (TREE_CODE (fn) != ADDR_EXPR && TREE_CODE (fn) != FDESC_EXPR)
5711 || TREE_CODE (TREE_OPERAND (fn, 0)) != FUNCTION_DECL)
5712 fn = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
5713 else
5715 fn = TREE_OPERAND (fn, 0);
5717 /* When cgraph node is missing and function is not public, we cannot
5718 devirtualize. This can happen in WHOPR when the actual method
5719 ends up in other partition, because we found devirtualization
5720 possibility too late. */
5721 if (!can_refer_decl_in_current_unit_p (fn, vtable))
5723 if (can_refer)
5725 *can_refer = false;
5726 return fn;
5728 return NULL_TREE;
5732 /* Make sure we create a cgraph node for functions we'll reference.
5733 They can be non-existent if the reference comes from an entry
5734 of an external vtable for example. */
5735 cgraph_node::get_create (fn);
5737 return fn;
5740 /* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN
5741 is integer form of OBJ_TYPE_REF_TOKEN of the reference expression.
5742 KNOWN_BINFO carries the binfo describing the true type of
5743 OBJ_TYPE_REF_OBJECT(REF).
5744 Set CAN_REFER if non-NULL to false if method
5745 is not referable or if the virtual table is ill-formed (such as rewriten
5746 by non-C++ produced symbol). Otherwise just return NULL in that calse. */
5748 tree
5749 gimple_get_virt_method_for_binfo (HOST_WIDE_INT token, tree known_binfo,
5750 bool *can_refer)
5752 unsigned HOST_WIDE_INT offset;
5753 tree v;
5755 v = BINFO_VTABLE (known_binfo);
5756 /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone. */
5757 if (!v)
5758 return NULL_TREE;
5760 if (!vtable_pointer_value_to_vtable (v, &v, &offset))
5762 if (can_refer)
5763 *can_refer = false;
5764 return NULL_TREE;
5766 return gimple_get_virt_method_for_vtable (token, v, offset, can_refer);
5769 /* Return true iff VAL is a gimple expression that is known to be
5770 non-negative. Restricted to floating-point inputs. */
5772 bool
5773 gimple_val_nonnegative_real_p (tree val)
5775 gimple def_stmt;
5777 gcc_assert (val && SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)));
5779 /* Use existing logic for non-gimple trees. */
5780 if (tree_expr_nonnegative_p (val))
5781 return true;
5783 if (TREE_CODE (val) != SSA_NAME)
5784 return false;
5786 /* Currently we look only at the immediately defining statement
5787 to make this determination, since recursion on defining
5788 statements of operands can lead to quadratic behavior in the
5789 worst case. This is expected to catch almost all occurrences
5790 in practice. It would be possible to implement limited-depth
5791 recursion if important cases are lost. Alternatively, passes
5792 that need this information (such as the pow/powi lowering code
5793 in the cse_sincos pass) could be revised to provide it through
5794 dataflow propagation. */
5796 def_stmt = SSA_NAME_DEF_STMT (val);
5798 if (is_gimple_assign (def_stmt))
5800 tree op0, op1;
5802 /* See fold-const.c:tree_expr_nonnegative_p for additional
5803 cases that could be handled with recursion. */
5805 switch (gimple_assign_rhs_code (def_stmt))
5807 case ABS_EXPR:
5808 /* Always true for floating-point operands. */
5809 return true;
5811 case MULT_EXPR:
5812 /* True if the two operands are identical (since we are
5813 restricted to floating-point inputs). */
5814 op0 = gimple_assign_rhs1 (def_stmt);
5815 op1 = gimple_assign_rhs2 (def_stmt);
5817 if (op0 == op1
5818 || operand_equal_p (op0, op1, 0))
5819 return true;
5821 default:
5822 return false;
5825 else if (is_gimple_call (def_stmt))
5827 tree fndecl = gimple_call_fndecl (def_stmt);
5828 if (fndecl
5829 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
5831 tree arg1;
5833 switch (DECL_FUNCTION_CODE (fndecl))
5835 CASE_FLT_FN (BUILT_IN_ACOS):
5836 CASE_FLT_FN (BUILT_IN_ACOSH):
5837 CASE_FLT_FN (BUILT_IN_CABS):
5838 CASE_FLT_FN (BUILT_IN_COSH):
5839 CASE_FLT_FN (BUILT_IN_ERFC):
5840 CASE_FLT_FN (BUILT_IN_EXP):
5841 CASE_FLT_FN (BUILT_IN_EXP10):
5842 CASE_FLT_FN (BUILT_IN_EXP2):
5843 CASE_FLT_FN (BUILT_IN_FABS):
5844 CASE_FLT_FN (BUILT_IN_FDIM):
5845 CASE_FLT_FN (BUILT_IN_HYPOT):
5846 CASE_FLT_FN (BUILT_IN_POW10):
5847 return true;
5849 CASE_FLT_FN (BUILT_IN_SQRT):
5850 /* sqrt(-0.0) is -0.0, and sqrt is not defined over other
5851 nonnegative inputs. */
5852 if (!HONOR_SIGNED_ZEROS (val))
5853 return true;
5855 break;
5857 CASE_FLT_FN (BUILT_IN_POWI):
5858 /* True if the second argument is an even integer. */
5859 arg1 = gimple_call_arg (def_stmt, 1);
5861 if (TREE_CODE (arg1) == INTEGER_CST
5862 && (TREE_INT_CST_LOW (arg1) & 1) == 0)
5863 return true;
5865 break;
5867 CASE_FLT_FN (BUILT_IN_POW):
5868 /* True if the second argument is an even integer-valued
5869 real. */
5870 arg1 = gimple_call_arg (def_stmt, 1);
5872 if (TREE_CODE (arg1) == REAL_CST)
5874 REAL_VALUE_TYPE c;
5875 HOST_WIDE_INT n;
5877 c = TREE_REAL_CST (arg1);
5878 n = real_to_integer (&c);
5880 if ((n & 1) == 0)
5882 REAL_VALUE_TYPE cint;
5883 real_from_integer (&cint, VOIDmode, n, SIGNED);
5884 if (real_identical (&c, &cint))
5885 return true;
5889 break;
5891 default:
5892 return false;
5897 return false;
5900 /* Given a pointer value OP0, return a simplified version of an
5901 indirection through OP0, or NULL_TREE if no simplification is
5902 possible. Note that the resulting type may be different from
5903 the type pointed to in the sense that it is still compatible
5904 from the langhooks point of view. */
5906 tree
5907 gimple_fold_indirect_ref (tree t)
5909 tree ptype = TREE_TYPE (t), type = TREE_TYPE (ptype);
5910 tree sub = t;
5911 tree subtype;
5913 STRIP_NOPS (sub);
5914 subtype = TREE_TYPE (sub);
5915 if (!POINTER_TYPE_P (subtype))
5916 return NULL_TREE;
5918 if (TREE_CODE (sub) == ADDR_EXPR)
5920 tree op = TREE_OPERAND (sub, 0);
5921 tree optype = TREE_TYPE (op);
5922 /* *&p => p */
5923 if (useless_type_conversion_p (type, optype))
5924 return op;
5926 /* *(foo *)&fooarray => fooarray[0] */
5927 if (TREE_CODE (optype) == ARRAY_TYPE
5928 && TREE_CODE (TYPE_SIZE (TREE_TYPE (optype))) == INTEGER_CST
5929 && useless_type_conversion_p (type, TREE_TYPE (optype)))
5931 tree type_domain = TYPE_DOMAIN (optype);
5932 tree min_val = size_zero_node;
5933 if (type_domain && TYPE_MIN_VALUE (type_domain))
5934 min_val = TYPE_MIN_VALUE (type_domain);
5935 if (TREE_CODE (min_val) == INTEGER_CST)
5936 return build4 (ARRAY_REF, type, op, min_val, NULL_TREE, NULL_TREE);
5938 /* *(foo *)&complexfoo => __real__ complexfoo */
5939 else if (TREE_CODE (optype) == COMPLEX_TYPE
5940 && useless_type_conversion_p (type, TREE_TYPE (optype)))
5941 return fold_build1 (REALPART_EXPR, type, op);
5942 /* *(foo *)&vectorfoo => BIT_FIELD_REF<vectorfoo,...> */
5943 else if (TREE_CODE (optype) == VECTOR_TYPE
5944 && useless_type_conversion_p (type, TREE_TYPE (optype)))
5946 tree part_width = TYPE_SIZE (type);
5947 tree index = bitsize_int (0);
5948 return fold_build3 (BIT_FIELD_REF, type, op, part_width, index);
5952 /* *(p + CST) -> ... */
5953 if (TREE_CODE (sub) == POINTER_PLUS_EXPR
5954 && TREE_CODE (TREE_OPERAND (sub, 1)) == INTEGER_CST)
5956 tree addr = TREE_OPERAND (sub, 0);
5957 tree off = TREE_OPERAND (sub, 1);
5958 tree addrtype;
5960 STRIP_NOPS (addr);
5961 addrtype = TREE_TYPE (addr);
5963 /* ((foo*)&vectorfoo)[1] -> BIT_FIELD_REF<vectorfoo,...> */
5964 if (TREE_CODE (addr) == ADDR_EXPR
5965 && TREE_CODE (TREE_TYPE (addrtype)) == VECTOR_TYPE
5966 && useless_type_conversion_p (type, TREE_TYPE (TREE_TYPE (addrtype)))
5967 && tree_fits_uhwi_p (off))
5969 unsigned HOST_WIDE_INT offset = tree_to_uhwi (off);
5970 tree part_width = TYPE_SIZE (type);
5971 unsigned HOST_WIDE_INT part_widthi
5972 = tree_to_shwi (part_width) / BITS_PER_UNIT;
5973 unsigned HOST_WIDE_INT indexi = offset * BITS_PER_UNIT;
5974 tree index = bitsize_int (indexi);
5975 if (offset / part_widthi
5976 < TYPE_VECTOR_SUBPARTS (TREE_TYPE (addrtype)))
5977 return fold_build3 (BIT_FIELD_REF, type, TREE_OPERAND (addr, 0),
5978 part_width, index);
5981 /* ((foo*)&complexfoo)[1] -> __imag__ complexfoo */
5982 if (TREE_CODE (addr) == ADDR_EXPR
5983 && TREE_CODE (TREE_TYPE (addrtype)) == COMPLEX_TYPE
5984 && useless_type_conversion_p (type, TREE_TYPE (TREE_TYPE (addrtype))))
5986 tree size = TYPE_SIZE_UNIT (type);
5987 if (tree_int_cst_equal (size, off))
5988 return fold_build1 (IMAGPART_EXPR, type, TREE_OPERAND (addr, 0));
5991 /* *(p + CST) -> MEM_REF <p, CST>. */
5992 if (TREE_CODE (addr) != ADDR_EXPR
5993 || DECL_P (TREE_OPERAND (addr, 0)))
5994 return fold_build2 (MEM_REF, type,
5995 addr,
5996 wide_int_to_tree (ptype, off));
5999 /* *(foo *)fooarrptr => (*fooarrptr)[0] */
6000 if (TREE_CODE (TREE_TYPE (subtype)) == ARRAY_TYPE
6001 && TREE_CODE (TYPE_SIZE (TREE_TYPE (TREE_TYPE (subtype)))) == INTEGER_CST
6002 && useless_type_conversion_p (type, TREE_TYPE (TREE_TYPE (subtype))))
6004 tree type_domain;
6005 tree min_val = size_zero_node;
6006 tree osub = sub;
6007 sub = gimple_fold_indirect_ref (sub);
6008 if (! sub)
6009 sub = build1 (INDIRECT_REF, TREE_TYPE (subtype), osub);
6010 type_domain = TYPE_DOMAIN (TREE_TYPE (sub));
6011 if (type_domain && TYPE_MIN_VALUE (type_domain))
6012 min_val = TYPE_MIN_VALUE (type_domain);
6013 if (TREE_CODE (min_val) == INTEGER_CST)
6014 return build4 (ARRAY_REF, type, sub, min_val, NULL_TREE, NULL_TREE);
6017 return NULL_TREE;
6020 /* Return true if CODE is an operation that when operating on signed
6021 integer types involves undefined behavior on overflow and the
6022 operation can be expressed with unsigned arithmetic. */
6024 bool
6025 arith_code_with_undefined_signed_overflow (tree_code code)
6027 switch (code)
6029 case PLUS_EXPR:
6030 case MINUS_EXPR:
6031 case MULT_EXPR:
6032 case NEGATE_EXPR:
6033 case POINTER_PLUS_EXPR:
6034 return true;
6035 default:
6036 return false;
6040 /* Rewrite STMT, an assignment with a signed integer or pointer arithmetic
6041 operation that can be transformed to unsigned arithmetic by converting
6042 its operand, carrying out the operation in the corresponding unsigned
6043 type and converting the result back to the original type.
6045 Returns a sequence of statements that replace STMT and also contain
6046 a modified form of STMT itself. */
6048 gimple_seq
6049 rewrite_to_defined_overflow (gimple stmt)
6051 if (dump_file && (dump_flags & TDF_DETAILS))
6053 fprintf (dump_file, "rewriting stmt with undefined signed "
6054 "overflow ");
6055 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
6058 tree lhs = gimple_assign_lhs (stmt);
6059 tree type = unsigned_type_for (TREE_TYPE (lhs));
6060 gimple_seq stmts = NULL;
6061 for (unsigned i = 1; i < gimple_num_ops (stmt); ++i)
6063 gimple_seq stmts2 = NULL;
6064 gimple_set_op (stmt, i,
6065 force_gimple_operand (fold_convert (type,
6066 gimple_op (stmt, i)),
6067 &stmts2, true, NULL_TREE));
6068 gimple_seq_add_seq (&stmts, stmts2);
6070 gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt));
6071 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
6072 gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
6073 gimple_seq_add_stmt (&stmts, stmt);
6074 gimple cvt = gimple_build_assign (lhs, NOP_EXPR, gimple_assign_lhs (stmt));
6075 gimple_seq_add_stmt (&stmts, cvt);
6077 return stmts;
6081 /* Build the expression CODE OP0 of type TYPE with location LOC,
6082 simplifying it first if possible using VALUEIZE if not NULL.
6083 OP0 is expected to be valueized already. Returns the built
6084 expression value and appends statements possibly defining it
6085 to SEQ. */
6087 tree
6088 gimple_build (gimple_seq *seq, location_t loc,
6089 enum tree_code code, tree type, tree op0,
6090 tree (*valueize)(tree))
6092 tree res = gimple_simplify (code, type, op0, seq, valueize);
6093 if (!res)
6095 if (gimple_in_ssa_p (cfun))
6096 res = make_ssa_name (type);
6097 else
6098 res = create_tmp_reg (type);
6099 gimple stmt;
6100 if (code == REALPART_EXPR
6101 || code == IMAGPART_EXPR
6102 || code == VIEW_CONVERT_EXPR)
6103 stmt = gimple_build_assign (res, code, build1 (code, type, op0));
6104 else
6105 stmt = gimple_build_assign (res, code, op0);
6106 gimple_set_location (stmt, loc);
6107 gimple_seq_add_stmt_without_update (seq, stmt);
6109 return res;
6112 /* Build the expression OP0 CODE OP1 of type TYPE with location LOC,
6113 simplifying it first if possible using VALUEIZE if not NULL.
6114 OP0 and OP1 are expected to be valueized already. Returns the built
6115 expression value and appends statements possibly defining it
6116 to SEQ. */
6118 tree
6119 gimple_build (gimple_seq *seq, location_t loc,
6120 enum tree_code code, tree type, tree op0, tree op1,
6121 tree (*valueize)(tree))
6123 tree res = gimple_simplify (code, type, op0, op1, seq, valueize);
6124 if (!res)
6126 if (gimple_in_ssa_p (cfun))
6127 res = make_ssa_name (type);
6128 else
6129 res = create_tmp_reg (type);
6130 gimple stmt = gimple_build_assign (res, code, op0, op1);
6131 gimple_set_location (stmt, loc);
6132 gimple_seq_add_stmt_without_update (seq, stmt);
6134 return res;
6137 /* Build the expression (CODE OP0 OP1 OP2) of type TYPE with location LOC,
6138 simplifying it first if possible using VALUEIZE if not NULL.
6139 OP0, OP1 and OP2 are expected to be valueized already. Returns the built
6140 expression value and appends statements possibly defining it
6141 to SEQ. */
6143 tree
6144 gimple_build (gimple_seq *seq, location_t loc,
6145 enum tree_code code, tree type, tree op0, tree op1, tree op2,
6146 tree (*valueize)(tree))
6148 tree res = gimple_simplify (code, type, op0, op1, op2,
6149 seq, valueize);
6150 if (!res)
6152 if (gimple_in_ssa_p (cfun))
6153 res = make_ssa_name (type);
6154 else
6155 res = create_tmp_reg (type);
6156 gimple stmt;
6157 if (code == BIT_FIELD_REF)
6158 stmt = gimple_build_assign (res, code,
6159 build3 (code, type, op0, op1, op2));
6160 else
6161 stmt = gimple_build_assign (res, code, op0, op1, op2);
6162 gimple_set_location (stmt, loc);
6163 gimple_seq_add_stmt_without_update (seq, stmt);
6165 return res;
6168 /* Build the call FN (ARG0) with a result of type TYPE
6169 (or no result if TYPE is void) with location LOC,
6170 simplifying it first if possible using VALUEIZE if not NULL.
6171 ARG0 is expected to be valueized already. Returns the built
6172 expression value (or NULL_TREE if TYPE is void) and appends
6173 statements possibly defining it to SEQ. */
6175 tree
6176 gimple_build (gimple_seq *seq, location_t loc,
6177 enum built_in_function fn, tree type, tree arg0,
6178 tree (*valueize)(tree))
6180 tree res = gimple_simplify (fn, type, arg0, seq, valueize);
6181 if (!res)
6183 tree decl = builtin_decl_implicit (fn);
6184 gimple stmt = gimple_build_call (decl, 1, arg0);
6185 if (!VOID_TYPE_P (type))
6187 if (gimple_in_ssa_p (cfun))
6188 res = make_ssa_name (type);
6189 else
6190 res = create_tmp_reg (type);
6191 gimple_call_set_lhs (stmt, res);
6193 gimple_set_location (stmt, loc);
6194 gimple_seq_add_stmt_without_update (seq, stmt);
6196 return res;
6199 /* Build the call FN (ARG0, ARG1) with a result of type TYPE
6200 (or no result if TYPE is void) with location LOC,
6201 simplifying it first if possible using VALUEIZE if not NULL.
6202 ARG0 is expected to be valueized already. Returns the built
6203 expression value (or NULL_TREE if TYPE is void) and appends
6204 statements possibly defining it to SEQ. */
6206 tree
6207 gimple_build (gimple_seq *seq, location_t loc,
6208 enum built_in_function fn, tree type, tree arg0, tree arg1,
6209 tree (*valueize)(tree))
6211 tree res = gimple_simplify (fn, type, arg0, arg1, seq, valueize);
6212 if (!res)
6214 tree decl = builtin_decl_implicit (fn);
6215 gimple stmt = gimple_build_call (decl, 2, arg0, arg1);
6216 if (!VOID_TYPE_P (type))
6218 if (gimple_in_ssa_p (cfun))
6219 res = make_ssa_name (type);
6220 else
6221 res = create_tmp_reg (type);
6222 gimple_call_set_lhs (stmt, res);
6224 gimple_set_location (stmt, loc);
6225 gimple_seq_add_stmt_without_update (seq, stmt);
6227 return res;
6230 /* Build the call FN (ARG0, ARG1, ARG2) with a result of type TYPE
6231 (or no result if TYPE is void) with location LOC,
6232 simplifying it first if possible using VALUEIZE if not NULL.
6233 ARG0 is expected to be valueized already. Returns the built
6234 expression value (or NULL_TREE if TYPE is void) and appends
6235 statements possibly defining it to SEQ. */
6237 tree
6238 gimple_build (gimple_seq *seq, location_t loc,
6239 enum built_in_function fn, tree type,
6240 tree arg0, tree arg1, tree arg2,
6241 tree (*valueize)(tree))
6243 tree res = gimple_simplify (fn, type, arg0, arg1, arg2, seq, valueize);
6244 if (!res)
6246 tree decl = builtin_decl_implicit (fn);
6247 gimple stmt = gimple_build_call (decl, 3, arg0, arg1, arg2);
6248 if (!VOID_TYPE_P (type))
6250 if (gimple_in_ssa_p (cfun))
6251 res = make_ssa_name (type);
6252 else
6253 res = create_tmp_reg (type);
6254 gimple_call_set_lhs (stmt, res);
6256 gimple_set_location (stmt, loc);
6257 gimple_seq_add_stmt_without_update (seq, stmt);
6259 return res;
6262 /* Build the conversion (TYPE) OP with a result of type TYPE
6263 with location LOC if such conversion is neccesary in GIMPLE,
6264 simplifying it first.
6265 Returns the built expression value and appends
6266 statements possibly defining it to SEQ. */
6268 tree
6269 gimple_convert (gimple_seq *seq, location_t loc, tree type, tree op)
6271 if (useless_type_conversion_p (type, TREE_TYPE (op)))
6272 return op;
6273 return gimple_build (seq, loc, NOP_EXPR, type, op);