1 /* Statement simplification on GIMPLE.
2 Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
3 Split out from tree-ssa-ccp.c.
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "function.h"
28 #include "tree-dump.h"
29 #include "tree-flow.h"
30 #include "tree-pass.h"
31 #include "tree-ssa-propagate.h"
32 #include "target.h"
33 #include "gimple-fold.h"
34
35 /* Return true when DECL can be referenced from current unit.
36 We can get declarations that are not possible to reference for
37 various reasons:
38
39 1) When analyzing C++ virtual tables.
40 C++ virtual tables do have known constructors even
41 when they are keyed to other compilation unit.
42 Those tables can contain pointers to methods and vars
43 in other units. Those methods have both STATIC and EXTERNAL
44 set.
45 2) In WHOPR mode devirtualization might lead to reference
46 to method that was partitioned elsehwere.
47 In this case we have static VAR_DECL or FUNCTION_DECL
48 that has no corresponding callgraph/varpool node
49 declaring the body.
50 3) COMDAT functions referred by external vtables that
51 we devirtualize only during final copmilation stage.
52 At this time we already decided that we will not output
53 the function body and thus we can't reference the symbol
54 directly. */
55
56 static bool
can_refer_decl_in_current_unit_p(tree decl)57 can_refer_decl_in_current_unit_p (tree decl)
58 {
59 struct varpool_node *vnode;
60 struct cgraph_node *node;
61
62 if (!TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
63 return true;
64 /* External flag is set, so we deal with C++ reference
65 to static object from other file. */
66 if (DECL_EXTERNAL (decl) && TREE_STATIC (decl)
67 && TREE_CODE (decl) == VAR_DECL)
68 {
69 /* Just be sure it is not big in frontend setting
70 flags incorrectly. Those variables should never
71 be finalized. */
72 gcc_checking_assert (!(vnode = varpool_get_node (decl))
73 || !vnode->finalized);
74 return false;
75 }
76 /* When function is public, we always can introduce new reference.
77 Exception are the COMDAT functions where introducing a direct
78 reference imply need to include function body in the curren tunit. */
79 if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
80 return true;
81 /* We are not at ltrans stage; so don't worry about WHOPR.
82 Also when still gimplifying all referred comdat functions will be
83 produced.
84 ??? as observed in PR20991 for already optimized out comdat virtual functions
85 we may not neccesarily give up because the copy will be output elsewhere when
86 corresponding vtable is output. */
87 if (!flag_ltrans && (!DECL_COMDAT (decl) || !cgraph_function_flags_ready))
88 return true;
89 /* If we already output the function body, we are safe. */
90 if (TREE_ASM_WRITTEN (decl))
91 return true;
92 if (TREE_CODE (decl) == FUNCTION_DECL)
93 {
94 node = cgraph_get_node (decl);
95 /* Check that we still have function body and that we didn't took
96 the decision to eliminate offline copy of the function yet.
97 The second is important when devirtualization happens during final
98 compilation stage when making a new reference no longer makes callee
99 to be compiled. */
100 if (!node || !node->analyzed || node->global.inlined_to)
101 return false;
102 }
103 else if (TREE_CODE (decl) == VAR_DECL)
104 {
105 vnode = varpool_get_node (decl);
106 if (!vnode || !vnode->finalized)
107 return false;
108 }
109 return true;
110 }
111
112 /* CVAL is value taken from DECL_INITIAL of variable. Try to transform it into
113 acceptable form for is_gimple_min_invariant. */
114
115 tree
canonicalize_constructor_val(tree cval)116 canonicalize_constructor_val (tree cval)
117 {
118 tree orig_cval = cval;
119 STRIP_NOPS (cval);
120 if (TREE_CODE (cval) == POINTER_PLUS_EXPR
121 && TREE_CODE (TREE_OPERAND (cval, 1)) == INTEGER_CST)
122 {
123 tree ptr = TREE_OPERAND (cval, 0);
124 if (is_gimple_min_invariant (ptr))
125 cval = build1_loc (EXPR_LOCATION (cval),
126 ADDR_EXPR, TREE_TYPE (ptr),
127 fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (ptr)),
128 ptr,
129 fold_convert (ptr_type_node,
130 TREE_OPERAND (cval, 1))));
131 }
132 if (TREE_CODE (cval) == ADDR_EXPR)
133 {
134 tree base = get_base_address (TREE_OPERAND (cval, 0));
135
136 if (base
137 && (TREE_CODE (base) == VAR_DECL
138 || TREE_CODE (base) == FUNCTION_DECL)
139 && !can_refer_decl_in_current_unit_p (base))
140 return NULL_TREE;
141 if (base && TREE_CODE (base) == VAR_DECL)
142 {
143 TREE_ADDRESSABLE (base) = 1;
144 if (cfun && gimple_referenced_vars (cfun))
145 add_referenced_var (base);
146 }
147 /* Fixup types in global initializers. */
148 if (TREE_TYPE (TREE_TYPE (cval)) != TREE_TYPE (TREE_OPERAND (cval, 0)))
149 cval = build_fold_addr_expr (TREE_OPERAND (cval, 0));
150
151 if (!useless_type_conversion_p (TREE_TYPE (orig_cval), TREE_TYPE (cval)))
152 cval = fold_convert (TREE_TYPE (orig_cval), cval);
153 return cval;
154 }
155 return orig_cval;
156 }
157
158 /* If SYM is a constant variable with known value, return the value.
159 NULL_TREE is returned otherwise. */
160
161 tree
get_symbol_constant_value(tree sym)162 get_symbol_constant_value (tree sym)
163 {
164 if (const_value_known_p (sym))
165 {
166 tree val = DECL_INITIAL (sym);
167 if (val)
168 {
169 val = canonicalize_constructor_val (val);
170 if (val && is_gimple_min_invariant (val))
171 return val;
172 else
173 return NULL_TREE;
174 }
175 /* Variables declared 'const' without an initializer
176 have zero as the initializer if they may not be
177 overridden at link or run time. */
178 if (!val
179 && (INTEGRAL_TYPE_P (TREE_TYPE (sym))
180 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))
181 return build_zero_cst (TREE_TYPE (sym));
182 }
183
184 return NULL_TREE;
185 }
186
187
188
189 /* Subroutine of fold_stmt. We perform several simplifications of the
190 memory reference tree EXPR and make sure to re-gimplify them properly
191 after propagation of constant addresses. IS_LHS is true if the
192 reference is supposed to be an lvalue. */
193
194 static tree
maybe_fold_reference(tree expr,bool is_lhs)195 maybe_fold_reference (tree expr, bool is_lhs)
196 {
197 tree *t = &expr;
198 tree result;
199
200 if ((TREE_CODE (expr) == VIEW_CONVERT_EXPR
201 || TREE_CODE (expr) == REALPART_EXPR
202 || TREE_CODE (expr) == IMAGPART_EXPR)
203 && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
204 return fold_unary_loc (EXPR_LOCATION (expr),
205 TREE_CODE (expr),
206 TREE_TYPE (expr),
207 TREE_OPERAND (expr, 0));
208 else if (TREE_CODE (expr) == BIT_FIELD_REF
209 && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
210 return fold_ternary_loc (EXPR_LOCATION (expr),
211 TREE_CODE (expr),
212 TREE_TYPE (expr),
213 TREE_OPERAND (expr, 0),
214 TREE_OPERAND (expr, 1),
215 TREE_OPERAND (expr, 2));
216
217 while (handled_component_p (*t))
218 t = &TREE_OPERAND (*t, 0);
219
220 /* Canonicalize MEM_REFs invariant address operand. Do this first
221 to avoid feeding non-canonical MEM_REFs elsewhere. */
222 if (TREE_CODE (*t) == MEM_REF
223 && !is_gimple_mem_ref_addr (TREE_OPERAND (*t, 0)))
224 {
225 bool volatile_p = TREE_THIS_VOLATILE (*t);
226 tree tem = fold_binary (MEM_REF, TREE_TYPE (*t),
227 TREE_OPERAND (*t, 0),
228 TREE_OPERAND (*t, 1));
229 if (tem)
230 {
231 TREE_THIS_VOLATILE (tem) = volatile_p;
232 *t = tem;
233 tem = maybe_fold_reference (expr, is_lhs);
234 if (tem)
235 return tem;
236 return expr;
237 }
238 }
239
240 if (!is_lhs
241 && (result = fold_const_aggregate_ref (expr))
242 && is_gimple_min_invariant (result))
243 return result;
244
245 /* Fold back MEM_REFs to reference trees. */
246 if (TREE_CODE (*t) == MEM_REF
247 && TREE_CODE (TREE_OPERAND (*t, 0)) == ADDR_EXPR
248 && integer_zerop (TREE_OPERAND (*t, 1))
249 && (TREE_THIS_VOLATILE (*t)
250 == TREE_THIS_VOLATILE (TREE_OPERAND (TREE_OPERAND (*t, 0), 0)))
251 && !TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (TREE_OPERAND (*t, 1)))
252 && (TYPE_MAIN_VARIANT (TREE_TYPE (*t))
253 == TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (TREE_OPERAND (*t, 1)))))
254 /* We have to look out here to not drop a required conversion
255 from the rhs to the lhs if is_lhs, but we don't have the
256 rhs here to verify that. Thus require strict type
257 compatibility. */
258 && types_compatible_p (TREE_TYPE (*t),
259 TREE_TYPE (TREE_OPERAND
260 (TREE_OPERAND (*t, 0), 0))))
261 {
262 tree tem;
263 *t = TREE_OPERAND (TREE_OPERAND (*t, 0), 0);
264 tem = maybe_fold_reference (expr, is_lhs);
265 if (tem)
266 return tem;
267 return expr;
268 }
269 else if (TREE_CODE (*t) == TARGET_MEM_REF)
270 {
271 tree tem = maybe_fold_tmr (*t);
272 if (tem)
273 {
274 *t = tem;
275 tem = maybe_fold_reference (expr, is_lhs);
276 if (tem)
277 return tem;
278 return expr;
279 }
280 }
281
282 return NULL_TREE;
283 }
284
285
286 /* Attempt to fold an assignment statement pointed-to by SI. Returns a
287 replacement rhs for the statement or NULL_TREE if no simplification
288 could be made. It is assumed that the operands have been previously
289 folded. */
290
291 static tree
fold_gimple_assign(gimple_stmt_iterator * si)292 fold_gimple_assign (gimple_stmt_iterator *si)
293 {
294 gimple stmt = gsi_stmt (*si);
295 enum tree_code subcode = gimple_assign_rhs_code (stmt);
296 location_t loc = gimple_location (stmt);
297
298 tree result = NULL_TREE;
299
300 switch (get_gimple_rhs_class (subcode))
301 {
302 case GIMPLE_SINGLE_RHS:
303 {
304 tree rhs = gimple_assign_rhs1 (stmt);
305
306 if (REFERENCE_CLASS_P (rhs))
307 return maybe_fold_reference (rhs, false);
308
309 else if (TREE_CODE (rhs) == ADDR_EXPR)
310 {
311 tree ref = TREE_OPERAND (rhs, 0);
312 tree tem = maybe_fold_reference (ref, true);
313 if (tem
314 && TREE_CODE (tem) == MEM_REF
315 && integer_zerop (TREE_OPERAND (tem, 1)))
316 result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (tem, 0));
317 else if (tem)
318 result = fold_convert (TREE_TYPE (rhs),
319 build_fold_addr_expr_loc (loc, tem));
320 else if (TREE_CODE (ref) == MEM_REF
321 && integer_zerop (TREE_OPERAND (ref, 1)))
322 result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (ref, 0));
323 }
324
325 else if (TREE_CODE (rhs) == CONSTRUCTOR
326 && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
327 && (CONSTRUCTOR_NELTS (rhs)
328 == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
329 {
330 /* Fold a constant vector CONSTRUCTOR to VECTOR_CST. */
331 unsigned i;
332 tree val;
333
334 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
335 if (TREE_CODE (val) != INTEGER_CST
336 && TREE_CODE (val) != REAL_CST
337 && TREE_CODE (val) != FIXED_CST)
338 return NULL_TREE;
339
340 return build_vector_from_ctor (TREE_TYPE (rhs),
341 CONSTRUCTOR_ELTS (rhs));
342 }
343
344 else if (DECL_P (rhs))
345 return unshare_expr (get_symbol_constant_value (rhs));
346
347 /* If we couldn't fold the RHS, hand over to the generic
348 fold routines. */
349 if (result == NULL_TREE)
350 result = fold (rhs);
351
352 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR
353 that may have been added by fold, and "useless" type
354 conversions that might now be apparent due to propagation. */
355 STRIP_USELESS_TYPE_CONVERSION (result);
356
357 if (result != rhs && valid_gimple_rhs_p (result))
358 return result;
359
360 return NULL_TREE;
361 }
362 break;
363
364 case GIMPLE_UNARY_RHS:
365 {
366 tree rhs = gimple_assign_rhs1 (stmt);
367
368 result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
369 if (result)
370 {
371 /* If the operation was a conversion do _not_ mark a
372 resulting constant with TREE_OVERFLOW if the original
373 constant was not. These conversions have implementation
374 defined behavior and retaining the TREE_OVERFLOW flag
375 here would confuse later passes such as VRP. */
376 if (CONVERT_EXPR_CODE_P (subcode)
377 && TREE_CODE (result) == INTEGER_CST
378 && TREE_CODE (rhs) == INTEGER_CST)
379 TREE_OVERFLOW (result) = TREE_OVERFLOW (rhs);
380
381 STRIP_USELESS_TYPE_CONVERSION (result);
382 if (valid_gimple_rhs_p (result))
383 return result;
384 }
385 }
386 break;
387
388 case GIMPLE_BINARY_RHS:
389 /* Try to canonicalize for boolean-typed X the comparisons
390 X == 0, X == 1, X != 0, and X != 1. */
391 if (gimple_assign_rhs_code (stmt) == EQ_EXPR
392 || gimple_assign_rhs_code (stmt) == NE_EXPR)
393 {
394 tree lhs = gimple_assign_lhs (stmt);
395 tree op1 = gimple_assign_rhs1 (stmt);
396 tree op2 = gimple_assign_rhs2 (stmt);
397 tree type = TREE_TYPE (op1);
398
399 /* Check whether the comparison operands are of the same boolean
400 type as the result type is.
401 Check that second operand is an integer-constant with value
402 one or zero. */
403 if (TREE_CODE (op2) == INTEGER_CST
404 && (integer_zerop (op2) || integer_onep (op2))
405 && useless_type_conversion_p (TREE_TYPE (lhs), type))
406 {
407 enum tree_code cmp_code = gimple_assign_rhs_code (stmt);
408 bool is_logical_not = false;
409
410 /* X == 0 and X != 1 is a logical-not.of X
411 X == 1 and X != 0 is X */
412 if ((cmp_code == EQ_EXPR && integer_zerop (op2))
413 || (cmp_code == NE_EXPR && integer_onep (op2)))
414 is_logical_not = true;
415
416 if (is_logical_not == false)
417 result = op1;
418 /* Only for one-bit precision typed X the transformation
419 !X -> ~X is valied. */
420 else if (TYPE_PRECISION (type) == 1)
421 result = build1_loc (gimple_location (stmt), BIT_NOT_EXPR,
422 type, op1);
423 /* Otherwise we use !X -> X ^ 1. */
424 else
425 result = build2_loc (gimple_location (stmt), BIT_XOR_EXPR,
426 type, op1, build_int_cst (type, 1));
427
428 }
429 }
430
431 if (!result)
432 result = fold_binary_loc (loc, subcode,
433 TREE_TYPE (gimple_assign_lhs (stmt)),
434 gimple_assign_rhs1 (stmt),
435 gimple_assign_rhs2 (stmt));
436
437 if (result)
438 {
439 STRIP_USELESS_TYPE_CONVERSION (result);
440 if (valid_gimple_rhs_p (result))
441 return result;
442 }
443 break;
444
445 case GIMPLE_TERNARY_RHS:
446 /* Try to fold a conditional expression. */
447 if (gimple_assign_rhs_code (stmt) == COND_EXPR)
448 {
449 tree op0 = gimple_assign_rhs1 (stmt);
450 tree tem;
451 bool set = false;
452 location_t cond_loc = gimple_location (stmt);
453
454 if (COMPARISON_CLASS_P (op0))
455 {
456 fold_defer_overflow_warnings ();
457 tem = fold_binary_loc (cond_loc,
458 TREE_CODE (op0), TREE_TYPE (op0),
459 TREE_OPERAND (op0, 0),
460 TREE_OPERAND (op0, 1));
461 /* This is actually a conditional expression, not a GIMPLE
462 conditional statement, however, the valid_gimple_rhs_p
463 test still applies. */
464 set = (tem && is_gimple_condexpr (tem)
465 && valid_gimple_rhs_p (tem));
466 fold_undefer_overflow_warnings (set, stmt, 0);
467 }
468 else if (is_gimple_min_invariant (op0))
469 {
470 tem = op0;
471 set = true;
472 }
473 else
474 return NULL_TREE;
475
476 if (set)
477 result = fold_build3_loc (cond_loc, COND_EXPR,
478 TREE_TYPE (gimple_assign_lhs (stmt)), tem,
479 gimple_assign_rhs2 (stmt),
480 gimple_assign_rhs3 (stmt));
481 }
482
483 if (!result)
484 result = fold_ternary_loc (loc, subcode,
485 TREE_TYPE (gimple_assign_lhs (stmt)),
486 gimple_assign_rhs1 (stmt),
487 gimple_assign_rhs2 (stmt),
488 gimple_assign_rhs3 (stmt));
489
490 if (result)
491 {
492 STRIP_USELESS_TYPE_CONVERSION (result);
493 if (valid_gimple_rhs_p (result))
494 return result;
495 }
496 break;
497
498 case GIMPLE_INVALID_RHS:
499 gcc_unreachable ();
500 }
501
502 return NULL_TREE;
503 }
504
505 /* Attempt to fold a conditional statement. Return true if any changes were
506 made. We only attempt to fold the condition expression, and do not perform
507 any transformation that would require alteration of the cfg. It is
508 assumed that the operands have been previously folded. */
509
510 static bool
fold_gimple_cond(gimple stmt)511 fold_gimple_cond (gimple stmt)
512 {
513 tree result = fold_binary_loc (gimple_location (stmt),
514 gimple_cond_code (stmt),
515 boolean_type_node,
516 gimple_cond_lhs (stmt),
517 gimple_cond_rhs (stmt));
518
519 if (result)
520 {
521 STRIP_USELESS_TYPE_CONVERSION (result);
522 if (is_gimple_condexpr (result) && valid_gimple_rhs_p (result))
523 {
524 gimple_cond_set_condition_from_tree (stmt, result);
525 return true;
526 }
527 }
528
529 return false;
530 }
531
532 /* Convert EXPR into a GIMPLE value suitable for substitution on the
533 RHS of an assignment. Insert the necessary statements before
534 iterator *SI_P. The statement at *SI_P, which must be a GIMPLE_CALL
535 is replaced. If the call is expected to produces a result, then it
536 is replaced by an assignment of the new RHS to the result variable.
537 If the result is to be ignored, then the call is replaced by a
538 GIMPLE_NOP. A proper VDEF chain is retained by making the first
539 VUSE and the last VDEF of the whole sequence be the same as the replaced
540 statement and using new SSA names for stores in between. */
541
542 void
gimplify_and_update_call_from_tree(gimple_stmt_iterator * si_p,tree expr)543 gimplify_and_update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
544 {
545 tree lhs;
546 gimple stmt, new_stmt;
547 gimple_stmt_iterator i;
548 gimple_seq stmts = gimple_seq_alloc();
549 struct gimplify_ctx gctx;
550 gimple last;
551 gimple laststore;
552 tree reaching_vuse;
553
554 stmt = gsi_stmt (*si_p);
555
556 gcc_assert (is_gimple_call (stmt));
557
558 push_gimplify_context (&gctx);
559 gctx.into_ssa = gimple_in_ssa_p (cfun);
560
561 lhs = gimple_call_lhs (stmt);
562 if (lhs == NULL_TREE)
563 {
564 gimplify_and_add (expr, &stmts);
565 /* We can end up with folding a memcpy of an empty class assignment
566 which gets optimized away by C++ gimplification. */
567 if (gimple_seq_empty_p (stmts))
568 {
569 pop_gimplify_context (NULL);
570 if (gimple_in_ssa_p (cfun))
571 {
572 unlink_stmt_vdef (stmt);
573 release_defs (stmt);
574 }
575 gsi_replace (si_p, gimple_build_nop (), true);
576 return;
577 }
578 }
579 else
580 {
581 tree tmp = get_initialized_tmp_var (expr, &stmts, NULL);
582 new_stmt = gimple_build_assign (lhs, tmp);
583 i = gsi_last (stmts);
584 gsi_insert_after_without_update (&i, new_stmt,
585 GSI_CONTINUE_LINKING);
586 }
587
588 pop_gimplify_context (NULL);
589
590 if (gimple_has_location (stmt))
591 annotate_all_with_location (stmts, gimple_location (stmt));
592
593 /* First iterate over the replacement statements backward, assigning
594 virtual operands to their defining statements. */
595 laststore = NULL;
596 for (i = gsi_last (stmts); !gsi_end_p (i); gsi_prev (&i))
597 {
598 new_stmt = gsi_stmt (i);
599 if ((gimple_assign_single_p (new_stmt)
600 && !is_gimple_reg (gimple_assign_lhs (new_stmt)))
601 || (is_gimple_call (new_stmt)
602 && (gimple_call_flags (new_stmt)
603 & (ECF_NOVOPS | ECF_PURE | ECF_CONST | ECF_NORETURN)) == 0))
604 {
605 tree vdef;
606 if (!laststore)
607 vdef = gimple_vdef (stmt);
608 else
609 vdef = make_ssa_name (gimple_vop (cfun), new_stmt);
610 gimple_set_vdef (new_stmt, vdef);
611 if (vdef && TREE_CODE (vdef) == SSA_NAME)
612 SSA_NAME_DEF_STMT (vdef) = new_stmt;
613 laststore = new_stmt;
614 }
615 }
616
617 /* Second iterate over the statements forward, assigning virtual
618 operands to their uses. */
619 last = NULL;
620 reaching_vuse = gimple_vuse (stmt);
621 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
622 {
623 /* Do not insert the last stmt in this loop but remember it
624 for replacing the original statement. */
625 if (last)
626 {
627 gsi_insert_before (si_p, last, GSI_NEW_STMT);
628 gsi_next (si_p);
629 }
630 new_stmt = gsi_stmt (i);
631 /* The replacement can expose previously unreferenced variables. */
632 if (gimple_in_ssa_p (cfun))
633 find_new_referenced_vars (new_stmt);
634 /* If the new statement possibly has a VUSE, update it with exact SSA
635 name we know will reach this one. */
636 if (gimple_has_mem_ops (new_stmt))
637 gimple_set_vuse (new_stmt, reaching_vuse);
638 gimple_set_modified (new_stmt, true);
639 if (gimple_vdef (new_stmt))
640 reaching_vuse = gimple_vdef (new_stmt);
641 last = new_stmt;
642 }
643
644 /* If the new sequence does not do a store release the virtual
645 definition of the original statement. */
646 if (reaching_vuse
647 && reaching_vuse == gimple_vuse (stmt))
648 {
649 tree vdef = gimple_vdef (stmt);
650 if (vdef
651 && TREE_CODE (vdef) == SSA_NAME)
652 {
653 unlink_stmt_vdef (stmt);
654 release_ssa_name (vdef);
655 }
656 }
657
658 /* Finally replace rhe original statement with the last. */
659 gsi_replace (si_p, last, false);
660 }
661
662 /* Return the string length, maximum string length or maximum value of
663 ARG in LENGTH.
664 If ARG is an SSA name variable, follow its use-def chains. If LENGTH
665 is not NULL and, for TYPE == 0, its value is not equal to the length
666 we determine or if we are unable to determine the length or value,
667 return false. VISITED is a bitmap of visited variables.
668 TYPE is 0 if string length should be returned, 1 for maximum string
669 length and 2 for maximum value ARG can have. */
670
671 static bool
get_maxval_strlen(tree arg,tree * length,bitmap visited,int type)672 get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
673 {
674 tree var, val;
675 gimple def_stmt;
676
677 if (TREE_CODE (arg) != SSA_NAME)
678 {
679 /* We can end up with &(*iftmp_1)[0] here as well, so handle it. */
680 if (TREE_CODE (arg) == ADDR_EXPR
681 && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
682 && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
683 {
684 tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
685 if (TREE_CODE (aop0) == INDIRECT_REF
686 && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
687 return get_maxval_strlen (TREE_OPERAND (aop0, 0),
688 length, visited, type);
689 }
690
691 if (type == 2)
692 {
693 val = arg;
694 if (TREE_CODE (val) != INTEGER_CST
695 || tree_int_cst_sgn (val) < 0)
696 return false;
697 }
698 else
699 val = c_strlen (arg, 1);
700 if (!val)
701 return false;
702
703 if (*length)
704 {
705 if (type > 0)
706 {
707 if (TREE_CODE (*length) != INTEGER_CST
708 || TREE_CODE (val) != INTEGER_CST)
709 return false;
710
711 if (tree_int_cst_lt (*length, val))
712 *length = val;
713 return true;
714 }
715 else if (simple_cst_equal (val, *length) != 1)
716 return false;
717 }
718
719 *length = val;
720 return true;
721 }
722
723 /* If we were already here, break the infinite cycle. */
724 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
725 return true;
726
727 var = arg;
728 def_stmt = SSA_NAME_DEF_STMT (var);
729
730 switch (gimple_code (def_stmt))
731 {
732 case GIMPLE_ASSIGN:
733 /* The RHS of the statement defining VAR must either have a
734 constant length or come from another SSA_NAME with a constant
735 length. */
736 if (gimple_assign_single_p (def_stmt)
737 || gimple_assign_unary_nop_p (def_stmt))
738 {
739 tree rhs = gimple_assign_rhs1 (def_stmt);
740 return get_maxval_strlen (rhs, length, visited, type);
741 }
742 else if (gimple_assign_rhs_code (def_stmt) == COND_EXPR)
743 {
744 tree op2 = gimple_assign_rhs2 (def_stmt);
745 tree op3 = gimple_assign_rhs3 (def_stmt);
746 return get_maxval_strlen (op2, length, visited, type)
747 && get_maxval_strlen (op3, length, visited, type);
748 }
749 return false;
750
751 case GIMPLE_PHI:
752 {
753 /* All the arguments of the PHI node must have the same constant
754 length. */
755 unsigned i;
756
757 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
758 {
759 tree arg = gimple_phi_arg (def_stmt, i)->def;
760
761 /* If this PHI has itself as an argument, we cannot
762 determine the string length of this argument. However,
763 if we can find a constant string length for the other
764 PHI args then we can still be sure that this is a
765 constant string length. So be optimistic and just
766 continue with the next argument. */
767 if (arg == gimple_phi_result (def_stmt))
768 continue;
769
770 if (!get_maxval_strlen (arg, length, visited, type))
771 return false;
772 }
773 }
774 return true;
775
776 default:
777 return false;
778 }
779 }
780
781
782 /* Fold builtin call in statement STMT. Returns a simplified tree.
783 We may return a non-constant expression, including another call
784 to a different function and with different arguments, e.g.,
785 substituting memcpy for strcpy when the string length is known.
786 Note that some builtins expand into inline code that may not
787 be valid in GIMPLE. Callers must take care. */
788
789 tree
gimple_fold_builtin(gimple stmt)790 gimple_fold_builtin (gimple stmt)
791 {
792 tree result, val[3];
793 tree callee, a;
794 int arg_idx, type;
795 bitmap visited;
796 bool ignore;
797 int nargs;
798 location_t loc = gimple_location (stmt);
799
800 gcc_assert (is_gimple_call (stmt));
801
802 ignore = (gimple_call_lhs (stmt) == NULL);
803
804 /* First try the generic builtin folder. If that succeeds, return the
805 result directly. */
806 result = fold_call_stmt (stmt, ignore);
807 if (result)
808 {
809 if (ignore)
810 STRIP_NOPS (result);
811 return result;
812 }
813
814 /* Ignore MD builtins. */
815 callee = gimple_call_fndecl (stmt);
816 if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
817 return NULL_TREE;
818
819 /* Give up for always_inline inline builtins until they are
820 inlined. */
821 if (avoid_folding_inline_builtin (callee))
822 return NULL_TREE;
823
824 /* If the builtin could not be folded, and it has no argument list,
825 we're done. */
826 nargs = gimple_call_num_args (stmt);
827 if (nargs == 0)
828 return NULL_TREE;
829
830 /* Limit the work only for builtins we know how to simplify. */
831 switch (DECL_FUNCTION_CODE (callee))
832 {
833 case BUILT_IN_STRLEN:
834 case BUILT_IN_FPUTS:
835 case BUILT_IN_FPUTS_UNLOCKED:
836 arg_idx = 0;
837 type = 0;
838 break;
839 case BUILT_IN_STRCPY:
840 case BUILT_IN_STRNCPY:
841 arg_idx = 1;
842 type = 0;
843 break;
844 case BUILT_IN_MEMCPY_CHK:
845 case BUILT_IN_MEMPCPY_CHK:
846 case BUILT_IN_MEMMOVE_CHK:
847 case BUILT_IN_MEMSET_CHK:
848 case BUILT_IN_STRNCPY_CHK:
849 case BUILT_IN_STPNCPY_CHK:
850 arg_idx = 2;
851 type = 2;
852 break;
853 case BUILT_IN_STRCPY_CHK:
854 case BUILT_IN_STPCPY_CHK:
855 arg_idx = 1;
856 type = 1;
857 break;
858 case BUILT_IN_SNPRINTF_CHK:
859 case BUILT_IN_VSNPRINTF_CHK:
860 arg_idx = 1;
861 type = 2;
862 break;
863 default:
864 return NULL_TREE;
865 }
866
867 if (arg_idx >= nargs)
868 return NULL_TREE;
869
870 /* Try to use the dataflow information gathered by the CCP process. */
871 visited = BITMAP_ALLOC (NULL);
872 bitmap_clear (visited);
873
874 memset (val, 0, sizeof (val));
875 a = gimple_call_arg (stmt, arg_idx);
876 if (!get_maxval_strlen (a, &val[arg_idx], visited, type))
877 val[arg_idx] = NULL_TREE;
878
879 BITMAP_FREE (visited);
880
881 result = NULL_TREE;
882 switch (DECL_FUNCTION_CODE (callee))
883 {
884 case BUILT_IN_STRLEN:
885 if (val[0] && nargs == 1)
886 {
887 tree new_val =
888 fold_convert (TREE_TYPE (gimple_call_lhs (stmt)), val[0]);
889
890 /* If the result is not a valid gimple value, or not a cast
891 of a valid gimple value, then we cannot use the result. */
892 if (is_gimple_val (new_val)
893 || (CONVERT_EXPR_P (new_val)
894 && is_gimple_val (TREE_OPERAND (new_val, 0))))
895 return new_val;
896 }
897 break;
898
899 case BUILT_IN_STRCPY:
900 if (val[1] && is_gimple_val (val[1]) && nargs == 2)
901 result = fold_builtin_strcpy (loc, callee,
902 gimple_call_arg (stmt, 0),
903 gimple_call_arg (stmt, 1),
904 val[1]);
905 break;
906
907 case BUILT_IN_STRNCPY:
908 if (val[1] && is_gimple_val (val[1]) && nargs == 3)
909 result = fold_builtin_strncpy (loc, callee,
910 gimple_call_arg (stmt, 0),
911 gimple_call_arg (stmt, 1),
912 gimple_call_arg (stmt, 2),
913 val[1]);
914 break;
915
916 case BUILT_IN_FPUTS:
917 if (nargs == 2)
918 result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
919 gimple_call_arg (stmt, 1),
920 ignore, false, val[0]);
921 break;
922
923 case BUILT_IN_FPUTS_UNLOCKED:
924 if (nargs == 2)
925 result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
926 gimple_call_arg (stmt, 1),
927 ignore, true, val[0]);
928 break;
929
930 case BUILT_IN_MEMCPY_CHK:
931 case BUILT_IN_MEMPCPY_CHK:
932 case BUILT_IN_MEMMOVE_CHK:
933 case BUILT_IN_MEMSET_CHK:
934 if (val[2] && is_gimple_val (val[2]) && nargs == 4)
935 result = fold_builtin_memory_chk (loc, callee,
936 gimple_call_arg (stmt, 0),
937 gimple_call_arg (stmt, 1),
938 gimple_call_arg (stmt, 2),
939 gimple_call_arg (stmt, 3),
940 val[2], ignore,
941 DECL_FUNCTION_CODE (callee));
942 break;
943
944 case BUILT_IN_STRCPY_CHK:
945 case BUILT_IN_STPCPY_CHK:
946 if (val[1] && is_gimple_val (val[1]) && nargs == 3)
947 result = fold_builtin_stxcpy_chk (loc, callee,
948 gimple_call_arg (stmt, 0),
949 gimple_call_arg (stmt, 1),
950 gimple_call_arg (stmt, 2),
951 val[1], ignore,
952 DECL_FUNCTION_CODE (callee));
953 break;
954
955 case BUILT_IN_STRNCPY_CHK:
956 case BUILT_IN_STPNCPY_CHK:
957 if (val[2] && is_gimple_val (val[2]) && nargs == 4)
958 result = fold_builtin_stxncpy_chk (loc, gimple_call_arg (stmt, 0),
959 gimple_call_arg (stmt, 1),
960 gimple_call_arg (stmt, 2),
961 gimple_call_arg (stmt, 3),
962 val[2], ignore,
963 DECL_FUNCTION_CODE (callee));
964 break;
965
966 case BUILT_IN_SNPRINTF_CHK:
967 case BUILT_IN_VSNPRINTF_CHK:
968 if (val[1] && is_gimple_val (val[1]))
969 result = gimple_fold_builtin_snprintf_chk (stmt, val[1],
970 DECL_FUNCTION_CODE (callee));
971 break;
972
973 default:
974 gcc_unreachable ();
975 }
976
977 if (result && ignore)
978 result = fold_ignored_result (result);
979 return result;
980 }
981
982 /* Generate code adjusting the first parameter of a call statement determined
983 by GSI by DELTA. */
984
985 void
gimple_adjust_this_by_delta(gimple_stmt_iterator * gsi,tree delta)986 gimple_adjust_this_by_delta (gimple_stmt_iterator *gsi, tree delta)
987 {
988 gimple call_stmt = gsi_stmt (*gsi);
989 tree parm, tmp;
990 gimple new_stmt;
991
992 delta = convert_to_ptrofftype (delta);
993 gcc_assert (gimple_call_num_args (call_stmt) >= 1);
994 parm = gimple_call_arg (call_stmt, 0);
995 gcc_assert (POINTER_TYPE_P (TREE_TYPE (parm)));
996 tmp = create_tmp_var (TREE_TYPE (parm), NULL);
997 add_referenced_var (tmp);
998
999 tmp = make_ssa_name (tmp, NULL);
1000 new_stmt = gimple_build_assign_with_ops (POINTER_PLUS_EXPR, tmp, parm, delta);
1001 SSA_NAME_DEF_STMT (tmp) = new_stmt;
1002 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1003 gimple_call_set_arg (call_stmt, 0, tmp);
1004 }
1005
1006 /* Return a binfo to be used for devirtualization of calls based on an object
1007 represented by a declaration (i.e. a global or automatically allocated one)
1008 or NULL if it cannot be found or is not safe. CST is expected to be an
1009 ADDR_EXPR of such object or the function will return NULL. Currently it is
1010 safe to use such binfo only if it has no base binfo (i.e. no ancestors). */
1011
1012 tree
gimple_extract_devirt_binfo_from_cst(tree cst)1013 gimple_extract_devirt_binfo_from_cst (tree cst)
1014 {
1015 HOST_WIDE_INT offset, size, max_size;
1016 tree base, type, expected_type, binfo;
1017 bool last_artificial = false;
1018
1019 if (!flag_devirtualize
1020 || TREE_CODE (cst) != ADDR_EXPR
1021 || TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) != RECORD_TYPE)
1022 return NULL_TREE;
1023
1024 cst = TREE_OPERAND (cst, 0);
1025 expected_type = TREE_TYPE (cst);
1026 base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
1027 type = TREE_TYPE (base);
1028 if (!DECL_P (base)
1029 || max_size == -1
1030 || max_size != size
1031 || TREE_CODE (type) != RECORD_TYPE)
1032 return NULL_TREE;
1033
1034 /* Find the sub-object the constant actually refers to and mark whether it is
1035 an artificial one (as opposed to a user-defined one). */
1036 while (true)
1037 {
1038 HOST_WIDE_INT pos, size;
1039 tree fld;
1040
1041 if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (expected_type))
1042 break;
1043 if (offset < 0)
1044 return NULL_TREE;
1045
1046 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1047 {
1048 if (TREE_CODE (fld) != FIELD_DECL)
1049 continue;
1050
1051 pos = int_bit_position (fld);
1052 size = tree_low_cst (DECL_SIZE (fld), 1);
1053 if (pos <= offset && (pos + size) > offset)
1054 break;
1055 }
1056 if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
1057 return NULL_TREE;
1058
1059 last_artificial = DECL_ARTIFICIAL (fld);
1060 type = TREE_TYPE (fld);
1061 offset -= pos;
1062 }
1063 /* Artifical sub-objects are ancestors, we do not want to use them for
1064 devirtualization, at least not here. */
1065 if (last_artificial)
1066 return NULL_TREE;
1067 binfo = TYPE_BINFO (type);
1068 if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
1069 return NULL_TREE;
1070 else
1071 return binfo;
1072 }
1073
1074 /* Attempt to fold a call statement referenced by the statement iterator GSI.
1075 The statement may be replaced by another statement, e.g., if the call
1076 simplifies to a constant value. Return true if any changes were made.
1077 It is assumed that the operands have been previously folded. */
1078
1079 static bool
gimple_fold_call(gimple_stmt_iterator * gsi,bool inplace)1080 gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
1081 {
1082 gimple stmt = gsi_stmt (*gsi);
1083 tree callee;
1084 bool changed = false;
1085 unsigned i;
1086
1087 /* Fold *& in call arguments. */
1088 for (i = 0; i < gimple_call_num_args (stmt); ++i)
1089 if (REFERENCE_CLASS_P (gimple_call_arg (stmt, i)))
1090 {
1091 tree tmp = maybe_fold_reference (gimple_call_arg (stmt, i), false);
1092 if (tmp)
1093 {
1094 gimple_call_set_arg (stmt, i, tmp);
1095 changed = true;
1096 }
1097 }
1098
1099 /* Check for virtual calls that became direct calls. */
1100 callee = gimple_call_fn (stmt);
1101 if (callee && TREE_CODE (callee) == OBJ_TYPE_REF)
1102 {
1103 if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
1104 {
1105 gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
1106 changed = true;
1107 }
1108 else
1109 {
1110 tree obj = OBJ_TYPE_REF_OBJECT (callee);
1111 tree binfo = gimple_extract_devirt_binfo_from_cst (obj);
1112 if (binfo)
1113 {
1114 HOST_WIDE_INT token
1115 = TREE_INT_CST_LOW (OBJ_TYPE_REF_TOKEN (callee));
1116 tree fndecl = gimple_get_virt_method_for_binfo (token, binfo);
1117 if (fndecl)
1118 {
1119 gimple_call_set_fndecl (stmt, fndecl);
1120 changed = true;
1121 }
1122 }
1123 }
1124 }
1125
1126 if (inplace)
1127 return changed;
1128
1129 /* Check for builtins that CCP can handle using information not
1130 available in the generic fold routines. */
1131 callee = gimple_call_fndecl (stmt);
1132 if (callee && DECL_BUILT_IN (callee))
1133 {
1134 tree result = gimple_fold_builtin (stmt);
1135 if (result)
1136 {
1137 if (!update_call_from_tree (gsi, result))
1138 gimplify_and_update_call_from_tree (gsi, result);
1139 changed = true;
1140 }
1141 }
1142
1143 return changed;
1144 }
1145
1146 /* Worker for both fold_stmt and fold_stmt_inplace. The INPLACE argument
1147 distinguishes both cases. */
1148
1149 static bool
fold_stmt_1(gimple_stmt_iterator * gsi,bool inplace)1150 fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
1151 {
1152 bool changed = false;
1153 gimple stmt = gsi_stmt (*gsi);
1154 unsigned i;
1155 gimple_stmt_iterator gsinext = *gsi;
1156 gimple next_stmt;
1157
1158 gsi_next (&gsinext);
1159 next_stmt = gsi_end_p (gsinext) ? NULL : gsi_stmt (gsinext);
1160
1161 /* Fold the main computation performed by the statement. */
1162 switch (gimple_code (stmt))
1163 {
1164 case GIMPLE_ASSIGN:
1165 {
1166 unsigned old_num_ops = gimple_num_ops (stmt);
1167 enum tree_code subcode = gimple_assign_rhs_code (stmt);
1168 tree lhs = gimple_assign_lhs (stmt);
1169 tree new_rhs;
1170 /* First canonicalize operand order. This avoids building new
1171 trees if this is the only thing fold would later do. */
1172 if ((commutative_tree_code (subcode)
1173 || commutative_ternary_tree_code (subcode))
1174 && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
1175 gimple_assign_rhs2 (stmt), false))
1176 {
1177 tree tem = gimple_assign_rhs1 (stmt);
1178 gimple_assign_set_rhs1 (stmt, gimple_assign_rhs2 (stmt));
1179 gimple_assign_set_rhs2 (stmt, tem);
1180 changed = true;
1181 }
1182 new_rhs = fold_gimple_assign (gsi);
1183 if (new_rhs
1184 && !useless_type_conversion_p (TREE_TYPE (lhs),
1185 TREE_TYPE (new_rhs)))
1186 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1187 if (new_rhs
1188 && (!inplace
1189 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs)) < old_num_ops))
1190 {
1191 gimple_assign_set_rhs_from_tree (gsi, new_rhs);
1192 changed = true;
1193 }
1194 break;
1195 }
1196
1197 case GIMPLE_COND:
1198 changed |= fold_gimple_cond (stmt);
1199 break;
1200
1201 case GIMPLE_CALL:
1202 changed |= gimple_fold_call (gsi, inplace);
1203 break;
1204
1205 case GIMPLE_ASM:
1206 /* Fold *& in asm operands. */
1207 {
1208 size_t noutputs;
1209 const char **oconstraints;
1210 const char *constraint;
1211 bool allows_mem, allows_reg;
1212
1213 noutputs = gimple_asm_noutputs (stmt);
1214 oconstraints = XALLOCAVEC (const char *, noutputs);
1215
1216 for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
1217 {
1218 tree link = gimple_asm_output_op (stmt, i);
1219 tree op = TREE_VALUE (link);
1220 oconstraints[i]
1221 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1222 if (REFERENCE_CLASS_P (op)
1223 && (op = maybe_fold_reference (op, true)) != NULL_TREE)
1224 {
1225 TREE_VALUE (link) = op;
1226 changed = true;
1227 }
1228 }
1229 for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
1230 {
1231 tree link = gimple_asm_input_op (stmt, i);
1232 tree op = TREE_VALUE (link);
1233 constraint
1234 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1235 parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1236 oconstraints, &allows_mem, &allows_reg);
1237 if (REFERENCE_CLASS_P (op)
1238 && (op = maybe_fold_reference (op, !allows_reg && allows_mem))
1239 != NULL_TREE)
1240 {
1241 TREE_VALUE (link) = op;
1242 changed = true;
1243 }
1244 }
1245 }
1246 break;
1247
1248 case GIMPLE_DEBUG:
1249 if (gimple_debug_bind_p (stmt))
1250 {
1251 tree val = gimple_debug_bind_get_value (stmt);
1252 if (val
1253 && REFERENCE_CLASS_P (val))
1254 {
1255 tree tem = maybe_fold_reference (val, false);
1256 if (tem)
1257 {
1258 gimple_debug_bind_set_value (stmt, tem);
1259 changed = true;
1260 }
1261 }
1262 else if (val
1263 && TREE_CODE (val) == ADDR_EXPR)
1264 {
1265 tree ref = TREE_OPERAND (val, 0);
1266 tree tem = maybe_fold_reference (ref, false);
1267 if (tem)
1268 {
1269 tem = build_fold_addr_expr_with_type (tem, TREE_TYPE (val));
1270 gimple_debug_bind_set_value (stmt, tem);
1271 changed = true;
1272 }
1273 }
1274 }
1275 break;
1276
1277 default:;
1278 }
1279
1280 /* If stmt folds into nothing and it was the last stmt in a bb,
1281 don't call gsi_stmt. */
1282 if (gsi_end_p (*gsi))
1283 {
1284 gcc_assert (next_stmt == NULL);
1285 return changed;
1286 }
1287
1288 stmt = gsi_stmt (*gsi);
1289
1290 /* Fold *& on the lhs. Don't do this if stmt folded into nothing,
1291 as we'd changing the next stmt. */
1292 if (gimple_has_lhs (stmt) && stmt != next_stmt)
1293 {
1294 tree lhs = gimple_get_lhs (stmt);
1295 if (lhs && REFERENCE_CLASS_P (lhs))
1296 {
1297 tree new_lhs = maybe_fold_reference (lhs, true);
1298 if (new_lhs)
1299 {
1300 gimple_set_lhs (stmt, new_lhs);
1301 changed = true;
1302 }
1303 }
1304 }
1305
1306 return changed;
1307 }
1308
1309 /* Fold the statement pointed to by GSI. In some cases, this function may
1310 replace the whole statement with a new one. Returns true iff folding
1311 makes any changes.
1312 The statement pointed to by GSI should be in valid gimple form but may
1313 be in unfolded state as resulting from for example constant propagation
1314 which can produce *&x = 0. */
1315
1316 bool
fold_stmt(gimple_stmt_iterator * gsi)1317 fold_stmt (gimple_stmt_iterator *gsi)
1318 {
1319 return fold_stmt_1 (gsi, false);
1320 }
1321
1322 /* Perform the minimal folding on statement *GSI. Only operations like
1323 *&x created by constant propagation are handled. The statement cannot
1324 be replaced with a new one. Return true if the statement was
1325 changed, false otherwise.
1326 The statement *GSI should be in valid gimple form but may
1327 be in unfolded state as resulting from for example constant propagation
1328 which can produce *&x = 0. */
1329
1330 bool
fold_stmt_inplace(gimple_stmt_iterator * gsi)1331 fold_stmt_inplace (gimple_stmt_iterator *gsi)
1332 {
1333 gimple stmt = gsi_stmt (*gsi);
1334 bool changed = fold_stmt_1 (gsi, true);
1335 gcc_assert (gsi_stmt (*gsi) == stmt);
1336 return changed;
1337 }
1338
1339 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE
1340 if EXPR is null or we don't know how.
1341 If non-null, the result always has boolean type. */
1342
1343 static tree
canonicalize_bool(tree expr,bool invert)1344 canonicalize_bool (tree expr, bool invert)
1345 {
1346 if (!expr)
1347 return NULL_TREE;
1348 else if (invert)
1349 {
1350 if (integer_nonzerop (expr))
1351 return boolean_false_node;
1352 else if (integer_zerop (expr))
1353 return boolean_true_node;
1354 else if (TREE_CODE (expr) == SSA_NAME)
1355 return fold_build2 (EQ_EXPR, boolean_type_node, expr,
1356 build_int_cst (TREE_TYPE (expr), 0));
1357 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1358 return fold_build2 (invert_tree_comparison (TREE_CODE (expr), false),
1359 boolean_type_node,
1360 TREE_OPERAND (expr, 0),
1361 TREE_OPERAND (expr, 1));
1362 else
1363 return NULL_TREE;
1364 }
1365 else
1366 {
1367 if (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1368 return expr;
1369 if (integer_nonzerop (expr))
1370 return boolean_true_node;
1371 else if (integer_zerop (expr))
1372 return boolean_false_node;
1373 else if (TREE_CODE (expr) == SSA_NAME)
1374 return fold_build2 (NE_EXPR, boolean_type_node, expr,
1375 build_int_cst (TREE_TYPE (expr), 0));
1376 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1377 return fold_build2 (TREE_CODE (expr),
1378 boolean_type_node,
1379 TREE_OPERAND (expr, 0),
1380 TREE_OPERAND (expr, 1));
1381 else
1382 return NULL_TREE;
1383 }
1384 }
1385
1386 /* Check to see if a boolean expression EXPR is logically equivalent to the
1387 comparison (OP1 CODE OP2). Check for various identities involving
1388 SSA_NAMEs. */
1389
1390 static bool
same_bool_comparison_p(const_tree expr,enum tree_code code,const_tree op1,const_tree op2)1391 same_bool_comparison_p (const_tree expr, enum tree_code code,
1392 const_tree op1, const_tree op2)
1393 {
1394 gimple s;
1395
1396 /* The obvious case. */
1397 if (TREE_CODE (expr) == code
1398 && operand_equal_p (TREE_OPERAND (expr, 0), op1, 0)
1399 && operand_equal_p (TREE_OPERAND (expr, 1), op2, 0))
1400 return true;
1401
1402 /* Check for comparing (name, name != 0) and the case where expr
1403 is an SSA_NAME with a definition matching the comparison. */
1404 if (TREE_CODE (expr) == SSA_NAME
1405 && TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1406 {
1407 if (operand_equal_p (expr, op1, 0))
1408 return ((code == NE_EXPR && integer_zerop (op2))
1409 || (code == EQ_EXPR && integer_nonzerop (op2)));
1410 s = SSA_NAME_DEF_STMT (expr);
1411 if (is_gimple_assign (s)
1412 && gimple_assign_rhs_code (s) == code
1413 && operand_equal_p (gimple_assign_rhs1 (s), op1, 0)
1414 && operand_equal_p (gimple_assign_rhs2 (s), op2, 0))
1415 return true;
1416 }
1417
1418 /* If op1 is of the form (name != 0) or (name == 0), and the definition
1419 of name is a comparison, recurse. */
1420 if (TREE_CODE (op1) == SSA_NAME
1421 && TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE)
1422 {
1423 s = SSA_NAME_DEF_STMT (op1);
1424 if (is_gimple_assign (s)
1425 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
1426 {
1427 enum tree_code c = gimple_assign_rhs_code (s);
1428 if ((c == NE_EXPR && integer_zerop (op2))
1429 || (c == EQ_EXPR && integer_nonzerop (op2)))
1430 return same_bool_comparison_p (expr, c,
1431 gimple_assign_rhs1 (s),
1432 gimple_assign_rhs2 (s));
1433 if ((c == EQ_EXPR && integer_zerop (op2))
1434 || (c == NE_EXPR && integer_nonzerop (op2)))
1435 return same_bool_comparison_p (expr,
1436 invert_tree_comparison (c, false),
1437 gimple_assign_rhs1 (s),
1438 gimple_assign_rhs2 (s));
1439 }
1440 }
1441 return false;
1442 }
1443
1444 /* Check to see if two boolean expressions OP1 and OP2 are logically
1445 equivalent. */
1446
1447 static bool
same_bool_result_p(const_tree op1,const_tree op2)1448 same_bool_result_p (const_tree op1, const_tree op2)
1449 {
1450 /* Simple cases first. */
1451 if (operand_equal_p (op1, op2, 0))
1452 return true;
1453
1454 /* Check the cases where at least one of the operands is a comparison.
1455 These are a bit smarter than operand_equal_p in that they apply some
1456 identifies on SSA_NAMEs. */
1457 if (TREE_CODE_CLASS (TREE_CODE (op2)) == tcc_comparison
1458 && same_bool_comparison_p (op1, TREE_CODE (op2),
1459 TREE_OPERAND (op2, 0),
1460 TREE_OPERAND (op2, 1)))
1461 return true;
1462 if (TREE_CODE_CLASS (TREE_CODE (op1)) == tcc_comparison
1463 && same_bool_comparison_p (op2, TREE_CODE (op1),
1464 TREE_OPERAND (op1, 0),
1465 TREE_OPERAND (op1, 1)))
1466 return true;
1467
1468 /* Default case. */
1469 return false;
1470 }
1471
1472 /* Forward declarations for some mutually recursive functions. */
1473
1474 static tree
1475 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1476 enum tree_code code2, tree op2a, tree op2b);
1477 static tree
1478 and_var_with_comparison (tree var, bool invert,
1479 enum tree_code code2, tree op2a, tree op2b);
1480 static tree
1481 and_var_with_comparison_1 (gimple stmt,
1482 enum tree_code code2, tree op2a, tree op2b);
1483 static tree
1484 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1485 enum tree_code code2, tree op2a, tree op2b);
1486 static tree
1487 or_var_with_comparison (tree var, bool invert,
1488 enum tree_code code2, tree op2a, tree op2b);
1489 static tree
1490 or_var_with_comparison_1 (gimple stmt,
1491 enum tree_code code2, tree op2a, tree op2b);
1492
1493 /* Helper function for and_comparisons_1: try to simplify the AND of the
1494 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1495 If INVERT is true, invert the value of the VAR before doing the AND.
1496 Return NULL_EXPR if we can't simplify this to a single expression. */
1497
1498 static tree
and_var_with_comparison(tree var,bool invert,enum tree_code code2,tree op2a,tree op2b)1499 and_var_with_comparison (tree var, bool invert,
1500 enum tree_code code2, tree op2a, tree op2b)
1501 {
1502 tree t;
1503 gimple stmt = SSA_NAME_DEF_STMT (var);
1504
1505 /* We can only deal with variables whose definitions are assignments. */
1506 if (!is_gimple_assign (stmt))
1507 return NULL_TREE;
1508
1509 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1510 !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
1511 Then we only have to consider the simpler non-inverted cases. */
1512 if (invert)
1513 t = or_var_with_comparison_1 (stmt,
1514 invert_tree_comparison (code2, false),
1515 op2a, op2b);
1516 else
1517 t = and_var_with_comparison_1 (stmt, code2, op2a, op2b);
1518 return canonicalize_bool (t, invert);
1519 }
1520
1521 /* Try to simplify the AND of the ssa variable defined by the assignment
1522 STMT with the comparison specified by (OP2A CODE2 OP2B).
1523 Return NULL_EXPR if we can't simplify this to a single expression. */
1524
1525 static tree
and_var_with_comparison_1(gimple stmt,enum tree_code code2,tree op2a,tree op2b)1526 and_var_with_comparison_1 (gimple stmt,
1527 enum tree_code code2, tree op2a, tree op2b)
1528 {
1529 tree var = gimple_assign_lhs (stmt);
1530 tree true_test_var = NULL_TREE;
1531 tree false_test_var = NULL_TREE;
1532 enum tree_code innercode = gimple_assign_rhs_code (stmt);
1533
1534 /* Check for identities like (var AND (var == 0)) => false. */
1535 if (TREE_CODE (op2a) == SSA_NAME
1536 && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1537 {
1538 if ((code2 == NE_EXPR && integer_zerop (op2b))
1539 || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
1540 {
1541 true_test_var = op2a;
1542 if (var == true_test_var)
1543 return var;
1544 }
1545 else if ((code2 == EQ_EXPR && integer_zerop (op2b))
1546 || (code2 == NE_EXPR && integer_nonzerop (op2b)))
1547 {
1548 false_test_var = op2a;
1549 if (var == false_test_var)
1550 return boolean_false_node;
1551 }
1552 }
1553
1554 /* If the definition is a comparison, recurse on it. */
1555 if (TREE_CODE_CLASS (innercode) == tcc_comparison)
1556 {
1557 tree t = and_comparisons_1 (innercode,
1558 gimple_assign_rhs1 (stmt),
1559 gimple_assign_rhs2 (stmt),
1560 code2,
1561 op2a,
1562 op2b);
1563 if (t)
1564 return t;
1565 }
1566
1567 /* If the definition is an AND or OR expression, we may be able to
1568 simplify by reassociating. */
1569 if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
1570 && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
1571 {
1572 tree inner1 = gimple_assign_rhs1 (stmt);
1573 tree inner2 = gimple_assign_rhs2 (stmt);
1574 gimple s;
1575 tree t;
1576 tree partial = NULL_TREE;
1577 bool is_and = (innercode == BIT_AND_EXPR);
1578
1579 /* Check for boolean identities that don't require recursive examination
1580 of inner1/inner2:
1581 inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
1582 inner1 AND (inner1 OR inner2) => inner1
1583 !inner1 AND (inner1 AND inner2) => false
1584 !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
1585 Likewise for similar cases involving inner2. */
1586 if (inner1 == true_test_var)
1587 return (is_and ? var : inner1);
1588 else if (inner2 == true_test_var)
1589 return (is_and ? var : inner2);
1590 else if (inner1 == false_test_var)
1591 return (is_and
1592 ? boolean_false_node
1593 : and_var_with_comparison (inner2, false, code2, op2a, op2b));
1594 else if (inner2 == false_test_var)
1595 return (is_and
1596 ? boolean_false_node
1597 : and_var_with_comparison (inner1, false, code2, op2a, op2b));
1598
1599 /* Next, redistribute/reassociate the AND across the inner tests.
1600 Compute the first partial result, (inner1 AND (op2a code op2b)) */
1601 if (TREE_CODE (inner1) == SSA_NAME
1602 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
1603 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1604 && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1605 gimple_assign_rhs1 (s),
1606 gimple_assign_rhs2 (s),
1607 code2, op2a, op2b)))
1608 {
1609 /* Handle the AND case, where we are reassociating:
1610 (inner1 AND inner2) AND (op2a code2 op2b)
1611 => (t AND inner2)
1612 If the partial result t is a constant, we win. Otherwise
1613 continue on to try reassociating with the other inner test. */
1614 if (is_and)
1615 {
1616 if (integer_onep (t))
1617 return inner2;
1618 else if (integer_zerop (t))
1619 return boolean_false_node;
1620 }
1621
1622 /* Handle the OR case, where we are redistributing:
1623 (inner1 OR inner2) AND (op2a code2 op2b)
1624 => (t OR (inner2 AND (op2a code2 op2b))) */
1625 else if (integer_onep (t))
1626 return boolean_true_node;
1627
1628 /* Save partial result for later. */
1629 partial = t;
1630 }
1631
1632 /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
1633 if (TREE_CODE (inner2) == SSA_NAME
1634 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
1635 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1636 && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1637 gimple_assign_rhs1 (s),
1638 gimple_assign_rhs2 (s),
1639 code2, op2a, op2b)))
1640 {
1641 /* Handle the AND case, where we are reassociating:
1642 (inner1 AND inner2) AND (op2a code2 op2b)
1643 => (inner1 AND t) */
1644 if (is_and)
1645 {
1646 if (integer_onep (t))
1647 return inner1;
1648 else if (integer_zerop (t))
1649 return boolean_false_node;
1650 /* If both are the same, we can apply the identity
1651 (x AND x) == x. */
1652 else if (partial && same_bool_result_p (t, partial))
1653 return t;
1654 }
1655
1656 /* Handle the OR case. where we are redistributing:
1657 (inner1 OR inner2) AND (op2a code2 op2b)
1658 => (t OR (inner1 AND (op2a code2 op2b)))
1659 => (t OR partial) */
1660 else
1661 {
1662 if (integer_onep (t))
1663 return boolean_true_node;
1664 else if (partial)
1665 {
1666 /* We already got a simplification for the other
1667 operand to the redistributed OR expression. The
1668 interesting case is when at least one is false.
1669 Or, if both are the same, we can apply the identity
1670 (x OR x) == x. */
1671 if (integer_zerop (partial))
1672 return t;
1673 else if (integer_zerop (t))
1674 return partial;
1675 else if (same_bool_result_p (t, partial))
1676 return t;
1677 }
1678 }
1679 }
1680 }
1681 return NULL_TREE;
1682 }
1683
1684 /* Try to simplify the AND of two comparisons defined by
1685 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
1686 If this can be done without constructing an intermediate value,
1687 return the resulting tree; otherwise NULL_TREE is returned.
1688 This function is deliberately asymmetric as it recurses on SSA_DEFs
1689 in the first comparison but not the second. */
1690
1691 static tree
and_comparisons_1(enum tree_code code1,tree op1a,tree op1b,enum tree_code code2,tree op2a,tree op2b)1692 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1693 enum tree_code code2, tree op2a, tree op2b)
1694 {
1695 /* First check for ((x CODE1 y) AND (x CODE2 y)). */
1696 if (operand_equal_p (op1a, op2a, 0)
1697 && operand_equal_p (op1b, op2b, 0))
1698 {
1699 /* Result will be either NULL_TREE, or a combined comparison. */
1700 tree t = combine_comparisons (UNKNOWN_LOCATION,
1701 TRUTH_ANDIF_EXPR, code1, code2,
1702 boolean_type_node, op1a, op1b);
1703 if (t)
1704 return t;
1705 }
1706
1707 /* Likewise the swapped case of the above. */
1708 if (operand_equal_p (op1a, op2b, 0)
1709 && operand_equal_p (op1b, op2a, 0))
1710 {
1711 /* Result will be either NULL_TREE, or a combined comparison. */
1712 tree t = combine_comparisons (UNKNOWN_LOCATION,
1713 TRUTH_ANDIF_EXPR, code1,
1714 swap_tree_comparison (code2),
1715 boolean_type_node, op1a, op1b);
1716 if (t)
1717 return t;
1718 }
1719
1720 /* If both comparisons are of the same value against constants, we might
1721 be able to merge them. */
1722 if (operand_equal_p (op1a, op2a, 0)
1723 && TREE_CODE (op1b) == INTEGER_CST
1724 && TREE_CODE (op2b) == INTEGER_CST)
1725 {
1726 int cmp = tree_int_cst_compare (op1b, op2b);
1727
1728 /* If we have (op1a == op1b), we should either be able to
1729 return that or FALSE, depending on whether the constant op1b
1730 also satisfies the other comparison against op2b. */
1731 if (code1 == EQ_EXPR)
1732 {
1733 bool done = true;
1734 bool val;
1735 switch (code2)
1736 {
1737 case EQ_EXPR: val = (cmp == 0); break;
1738 case NE_EXPR: val = (cmp != 0); break;
1739 case LT_EXPR: val = (cmp < 0); break;
1740 case GT_EXPR: val = (cmp > 0); break;
1741 case LE_EXPR: val = (cmp <= 0); break;
1742 case GE_EXPR: val = (cmp >= 0); break;
1743 default: done = false;
1744 }
1745 if (done)
1746 {
1747 if (val)
1748 return fold_build2 (code1, boolean_type_node, op1a, op1b);
1749 else
1750 return boolean_false_node;
1751 }
1752 }
1753 /* Likewise if the second comparison is an == comparison. */
1754 else if (code2 == EQ_EXPR)
1755 {
1756 bool done = true;
1757 bool val;
1758 switch (code1)
1759 {
1760 case EQ_EXPR: val = (cmp == 0); break;
1761 case NE_EXPR: val = (cmp != 0); break;
1762 case LT_EXPR: val = (cmp > 0); break;
1763 case GT_EXPR: val = (cmp < 0); break;
1764 case LE_EXPR: val = (cmp >= 0); break;
1765 case GE_EXPR: val = (cmp <= 0); break;
1766 default: done = false;
1767 }
1768 if (done)
1769 {
1770 if (val)
1771 return fold_build2 (code2, boolean_type_node, op2a, op2b);
1772 else
1773 return boolean_false_node;
1774 }
1775 }
1776
1777 /* Same business with inequality tests. */
1778 else if (code1 == NE_EXPR)
1779 {
1780 bool val;
1781 switch (code2)
1782 {
1783 case EQ_EXPR: val = (cmp != 0); break;
1784 case NE_EXPR: val = (cmp == 0); break;
1785 case LT_EXPR: val = (cmp >= 0); break;
1786 case GT_EXPR: val = (cmp <= 0); break;
1787 case LE_EXPR: val = (cmp > 0); break;
1788 case GE_EXPR: val = (cmp < 0); break;
1789 default:
1790 val = false;
1791 }
1792 if (val)
1793 return fold_build2 (code2, boolean_type_node, op2a, op2b);
1794 }
1795 else if (code2 == NE_EXPR)
1796 {
1797 bool val;
1798 switch (code1)
1799 {
1800 case EQ_EXPR: val = (cmp == 0); break;
1801 case NE_EXPR: val = (cmp != 0); break;
1802 case LT_EXPR: val = (cmp <= 0); break;
1803 case GT_EXPR: val = (cmp >= 0); break;
1804 case LE_EXPR: val = (cmp < 0); break;
1805 case GE_EXPR: val = (cmp > 0); break;
1806 default:
1807 val = false;
1808 }
1809 if (val)
1810 return fold_build2 (code1, boolean_type_node, op1a, op1b);
1811 }
1812
1813 /* Chose the more restrictive of two < or <= comparisons. */
1814 else if ((code1 == LT_EXPR || code1 == LE_EXPR)
1815 && (code2 == LT_EXPR || code2 == LE_EXPR))
1816 {
1817 if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
1818 return fold_build2 (code1, boolean_type_node, op1a, op1b);
1819 else
1820 return fold_build2 (code2, boolean_type_node, op2a, op2b);
1821 }
1822
1823 /* Likewise chose the more restrictive of two > or >= comparisons. */
1824 else if ((code1 == GT_EXPR || code1 == GE_EXPR)
1825 && (code2 == GT_EXPR || code2 == GE_EXPR))
1826 {
1827 if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
1828 return fold_build2 (code1, boolean_type_node, op1a, op1b);
1829 else
1830 return fold_build2 (code2, boolean_type_node, op2a, op2b);
1831 }
1832
1833 /* Check for singleton ranges. */
1834 else if (cmp == 0
1835 && ((code1 == LE_EXPR && code2 == GE_EXPR)
1836 || (code1 == GE_EXPR && code2 == LE_EXPR)))
1837 return fold_build2 (EQ_EXPR, boolean_type_node, op1a, op2b);
1838
1839 /* Check for disjoint ranges. */
1840 else if (cmp <= 0
1841 && (code1 == LT_EXPR || code1 == LE_EXPR)
1842 && (code2 == GT_EXPR || code2 == GE_EXPR))
1843 return boolean_false_node;
1844 else if (cmp >= 0
1845 && (code1 == GT_EXPR || code1 == GE_EXPR)
1846 && (code2 == LT_EXPR || code2 == LE_EXPR))
1847 return boolean_false_node;
1848 }
1849
1850 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
1851 NAME's definition is a truth value. See if there are any simplifications
1852 that can be done against the NAME's definition. */
1853 if (TREE_CODE (op1a) == SSA_NAME
1854 && (code1 == NE_EXPR || code1 == EQ_EXPR)
1855 && (integer_zerop (op1b) || integer_onep (op1b)))
1856 {
1857 bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
1858 || (code1 == NE_EXPR && integer_onep (op1b)));
1859 gimple stmt = SSA_NAME_DEF_STMT (op1a);
1860 switch (gimple_code (stmt))
1861 {
1862 case GIMPLE_ASSIGN:
1863 /* Try to simplify by copy-propagating the definition. */
1864 return and_var_with_comparison (op1a, invert, code2, op2a, op2b);
1865
1866 case GIMPLE_PHI:
1867 /* If every argument to the PHI produces the same result when
1868 ANDed with the second comparison, we win.
1869 Do not do this unless the type is bool since we need a bool
1870 result here anyway. */
1871 if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
1872 {
1873 tree result = NULL_TREE;
1874 unsigned i;
1875 for (i = 0; i < gimple_phi_num_args (stmt); i++)
1876 {
1877 tree arg = gimple_phi_arg_def (stmt, i);
1878
1879 /* If this PHI has itself as an argument, ignore it.
1880 If all the other args produce the same result,
1881 we're still OK. */
1882 if (arg == gimple_phi_result (stmt))
1883 continue;
1884 else if (TREE_CODE (arg) == INTEGER_CST)
1885 {
1886 if (invert ? integer_nonzerop (arg) : integer_zerop (arg))
1887 {
1888 if (!result)
1889 result = boolean_false_node;
1890 else if (!integer_zerop (result))
1891 return NULL_TREE;
1892 }
1893 else if (!result)
1894 result = fold_build2 (code2, boolean_type_node,
1895 op2a, op2b);
1896 else if (!same_bool_comparison_p (result,
1897 code2, op2a, op2b))
1898 return NULL_TREE;
1899 }
1900 else if (TREE_CODE (arg) == SSA_NAME
1901 && !SSA_NAME_IS_DEFAULT_DEF (arg))
1902 {
1903 tree temp;
1904 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
1905 /* In simple cases we can look through PHI nodes,
1906 but we have to be careful with loops.
1907 See PR49073. */
1908 if (! dom_info_available_p (CDI_DOMINATORS)
1909 || gimple_bb (def_stmt) == gimple_bb (stmt)
1910 || dominated_by_p (CDI_DOMINATORS,
1911 gimple_bb (def_stmt),
1912 gimple_bb (stmt)))
1913 return NULL_TREE;
1914 temp = and_var_with_comparison (arg, invert, code2,
1915 op2a, op2b);
1916 if (!temp)
1917 return NULL_TREE;
1918 else if (!result)
1919 result = temp;
1920 else if (!same_bool_result_p (result, temp))
1921 return NULL_TREE;
1922 }
1923 else
1924 return NULL_TREE;
1925 }
1926 return result;
1927 }
1928
1929 default:
1930 break;
1931 }
1932 }
1933 return NULL_TREE;
1934 }
1935
1936 /* Try to simplify the AND of two comparisons, specified by
1937 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
1938 If this can be simplified to a single expression (without requiring
1939 introducing more SSA variables to hold intermediate values),
1940 return the resulting tree. Otherwise return NULL_TREE.
1941 If the result expression is non-null, it has boolean type. */
1942
1943 tree
maybe_fold_and_comparisons(enum tree_code code1,tree op1a,tree op1b,enum tree_code code2,tree op2a,tree op2b)1944 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
1945 enum tree_code code2, tree op2a, tree op2b)
1946 {
1947 tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
1948 if (t)
1949 return t;
1950 else
1951 return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
1952 }
1953
1954 /* Helper function for or_comparisons_1: try to simplify the OR of the
1955 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1956 If INVERT is true, invert the value of VAR before doing the OR.
1957 Return NULL_EXPR if we can't simplify this to a single expression. */
1958
1959 static tree
or_var_with_comparison(tree var,bool invert,enum tree_code code2,tree op2a,tree op2b)1960 or_var_with_comparison (tree var, bool invert,
1961 enum tree_code code2, tree op2a, tree op2b)
1962 {
1963 tree t;
1964 gimple stmt = SSA_NAME_DEF_STMT (var);
1965
1966 /* We can only deal with variables whose definitions are assignments. */
1967 if (!is_gimple_assign (stmt))
1968 return NULL_TREE;
1969
1970 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1971 !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
1972 Then we only have to consider the simpler non-inverted cases. */
1973 if (invert)
1974 t = and_var_with_comparison_1 (stmt,
1975 invert_tree_comparison (code2, false),
1976 op2a, op2b);
1977 else
1978 t = or_var_with_comparison_1 (stmt, code2, op2a, op2b);
1979 return canonicalize_bool (t, invert);
1980 }
1981
1982 /* Try to simplify the OR of the ssa variable defined by the assignment
1983 STMT with the comparison specified by (OP2A CODE2 OP2B).
1984 Return NULL_EXPR if we can't simplify this to a single expression. */
1985
1986 static tree
or_var_with_comparison_1(gimple stmt,enum tree_code code2,tree op2a,tree op2b)1987 or_var_with_comparison_1 (gimple stmt,
1988 enum tree_code code2, tree op2a, tree op2b)
1989 {
1990 tree var = gimple_assign_lhs (stmt);
1991 tree true_test_var = NULL_TREE;
1992 tree false_test_var = NULL_TREE;
1993 enum tree_code innercode = gimple_assign_rhs_code (stmt);
1994
1995 /* Check for identities like (var OR (var != 0)) => true . */
1996 if (TREE_CODE (op2a) == SSA_NAME
1997 && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1998 {
1999 if ((code2 == NE_EXPR && integer_zerop (op2b))
2000 || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
2001 {
2002 true_test_var = op2a;
2003 if (var == true_test_var)
2004 return var;
2005 }
2006 else if ((code2 == EQ_EXPR && integer_zerop (op2b))
2007 || (code2 == NE_EXPR && integer_nonzerop (op2b)))
2008 {
2009 false_test_var = op2a;
2010 if (var == false_test_var)
2011 return boolean_true_node;
2012 }
2013 }
2014
2015 /* If the definition is a comparison, recurse on it. */
2016 if (TREE_CODE_CLASS (innercode) == tcc_comparison)
2017 {
2018 tree t = or_comparisons_1 (innercode,
2019 gimple_assign_rhs1 (stmt),
2020 gimple_assign_rhs2 (stmt),
2021 code2,
2022 op2a,
2023 op2b);
2024 if (t)
2025 return t;
2026 }
2027
2028 /* If the definition is an AND or OR expression, we may be able to
2029 simplify by reassociating. */
2030 if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
2031 && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
2032 {
2033 tree inner1 = gimple_assign_rhs1 (stmt);
2034 tree inner2 = gimple_assign_rhs2 (stmt);
2035 gimple s;
2036 tree t;
2037 tree partial = NULL_TREE;
2038 bool is_or = (innercode == BIT_IOR_EXPR);
2039
2040 /* Check for boolean identities that don't require recursive examination
2041 of inner1/inner2:
2042 inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
2043 inner1 OR (inner1 AND inner2) => inner1
2044 !inner1 OR (inner1 OR inner2) => true
2045 !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
2046 */
2047 if (inner1 == true_test_var)
2048 return (is_or ? var : inner1);
2049 else if (inner2 == true_test_var)
2050 return (is_or ? var : inner2);
2051 else if (inner1 == false_test_var)
2052 return (is_or
2053 ? boolean_true_node
2054 : or_var_with_comparison (inner2, false, code2, op2a, op2b));
2055 else if (inner2 == false_test_var)
2056 return (is_or
2057 ? boolean_true_node
2058 : or_var_with_comparison (inner1, false, code2, op2a, op2b));
2059
2060 /* Next, redistribute/reassociate the OR across the inner tests.
2061 Compute the first partial result, (inner1 OR (op2a code op2b)) */
2062 if (TREE_CODE (inner1) == SSA_NAME
2063 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
2064 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2065 && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2066 gimple_assign_rhs1 (s),
2067 gimple_assign_rhs2 (s),
2068 code2, op2a, op2b)))
2069 {
2070 /* Handle the OR case, where we are reassociating:
2071 (inner1 OR inner2) OR (op2a code2 op2b)
2072 => (t OR inner2)
2073 If the partial result t is a constant, we win. Otherwise
2074 continue on to try reassociating with the other inner test. */
2075 if (is_or)
2076 {
2077 if (integer_onep (t))
2078 return boolean_true_node;
2079 else if (integer_zerop (t))
2080 return inner2;
2081 }
2082
2083 /* Handle the AND case, where we are redistributing:
2084 (inner1 AND inner2) OR (op2a code2 op2b)
2085 => (t AND (inner2 OR (op2a code op2b))) */
2086 else if (integer_zerop (t))
2087 return boolean_false_node;
2088
2089 /* Save partial result for later. */
2090 partial = t;
2091 }
2092
2093 /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
2094 if (TREE_CODE (inner2) == SSA_NAME
2095 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
2096 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2097 && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2098 gimple_assign_rhs1 (s),
2099 gimple_assign_rhs2 (s),
2100 code2, op2a, op2b)))
2101 {
2102 /* Handle the OR case, where we are reassociating:
2103 (inner1 OR inner2) OR (op2a code2 op2b)
2104 => (inner1 OR t)
2105 => (t OR partial) */
2106 if (is_or)
2107 {
2108 if (integer_zerop (t))
2109 return inner1;
2110 else if (integer_onep (t))
2111 return boolean_true_node;
2112 /* If both are the same, we can apply the identity
2113 (x OR x) == x. */
2114 else if (partial && same_bool_result_p (t, partial))
2115 return t;
2116 }
2117
2118 /* Handle the AND case, where we are redistributing:
2119 (inner1 AND inner2) OR (op2a code2 op2b)
2120 => (t AND (inner1 OR (op2a code2 op2b)))
2121 => (t AND partial) */
2122 else
2123 {
2124 if (integer_zerop (t))
2125 return boolean_false_node;
2126 else if (partial)
2127 {
2128 /* We already got a simplification for the other
2129 operand to the redistributed AND expression. The
2130 interesting case is when at least one is true.
2131 Or, if both are the same, we can apply the identity
2132 (x AND x) == x. */
2133 if (integer_onep (partial))
2134 return t;
2135 else if (integer_onep (t))
2136 return partial;
2137 else if (same_bool_result_p (t, partial))
2138 return t;
2139 }
2140 }
2141 }
2142 }
2143 return NULL_TREE;
2144 }
2145
2146 /* Try to simplify the OR of two comparisons defined by
2147 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2148 If this can be done without constructing an intermediate value,
2149 return the resulting tree; otherwise NULL_TREE is returned.
2150 This function is deliberately asymmetric as it recurses on SSA_DEFs
2151 in the first comparison but not the second. */
2152
2153 static tree
or_comparisons_1(enum tree_code code1,tree op1a,tree op1b,enum tree_code code2,tree op2a,tree op2b)2154 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
2155 enum tree_code code2, tree op2a, tree op2b)
2156 {
2157 /* First check for ((x CODE1 y) OR (x CODE2 y)). */
2158 if (operand_equal_p (op1a, op2a, 0)
2159 && operand_equal_p (op1b, op2b, 0))
2160 {
2161 /* Result will be either NULL_TREE, or a combined comparison. */
2162 tree t = combine_comparisons (UNKNOWN_LOCATION,
2163 TRUTH_ORIF_EXPR, code1, code2,
2164 boolean_type_node, op1a, op1b);
2165 if (t)
2166 return t;
2167 }
2168
2169 /* Likewise the swapped case of the above. */
2170 if (operand_equal_p (op1a, op2b, 0)
2171 && operand_equal_p (op1b, op2a, 0))
2172 {
2173 /* Result will be either NULL_TREE, or a combined comparison. */
2174 tree t = combine_comparisons (UNKNOWN_LOCATION,
2175 TRUTH_ORIF_EXPR, code1,
2176 swap_tree_comparison (code2),
2177 boolean_type_node, op1a, op1b);
2178 if (t)
2179 return t;
2180 }
2181
2182 /* If both comparisons are of the same value against constants, we might
2183 be able to merge them. */
2184 if (operand_equal_p (op1a, op2a, 0)
2185 && TREE_CODE (op1b) == INTEGER_CST
2186 && TREE_CODE (op2b) == INTEGER_CST)
2187 {
2188 int cmp = tree_int_cst_compare (op1b, op2b);
2189
2190 /* If we have (op1a != op1b), we should either be able to
2191 return that or TRUE, depending on whether the constant op1b
2192 also satisfies the other comparison against op2b. */
2193 if (code1 == NE_EXPR)
2194 {
2195 bool done = true;
2196 bool val;
2197 switch (code2)
2198 {
2199 case EQ_EXPR: val = (cmp == 0); break;
2200 case NE_EXPR: val = (cmp != 0); break;
2201 case LT_EXPR: val = (cmp < 0); break;
2202 case GT_EXPR: val = (cmp > 0); break;
2203 case LE_EXPR: val = (cmp <= 0); break;
2204 case GE_EXPR: val = (cmp >= 0); break;
2205 default: done = false;
2206 }
2207 if (done)
2208 {
2209 if (val)
2210 return boolean_true_node;
2211 else
2212 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2213 }
2214 }
2215 /* Likewise if the second comparison is a != comparison. */
2216 else if (code2 == NE_EXPR)
2217 {
2218 bool done = true;
2219 bool val;
2220 switch (code1)
2221 {
2222 case EQ_EXPR: val = (cmp == 0); break;
2223 case NE_EXPR: val = (cmp != 0); break;
2224 case LT_EXPR: val = (cmp > 0); break;
2225 case GT_EXPR: val = (cmp < 0); break;
2226 case LE_EXPR: val = (cmp >= 0); break;
2227 case GE_EXPR: val = (cmp <= 0); break;
2228 default: done = false;
2229 }
2230 if (done)
2231 {
2232 if (val)
2233 return boolean_true_node;
2234 else
2235 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2236 }
2237 }
2238
2239 /* See if an equality test is redundant with the other comparison. */
2240 else if (code1 == EQ_EXPR)
2241 {
2242 bool val;
2243 switch (code2)
2244 {
2245 case EQ_EXPR: val = (cmp == 0); break;
2246 case NE_EXPR: val = (cmp != 0); break;
2247 case LT_EXPR: val = (cmp < 0); break;
2248 case GT_EXPR: val = (cmp > 0); break;
2249 case LE_EXPR: val = (cmp <= 0); break;
2250 case GE_EXPR: val = (cmp >= 0); break;
2251 default:
2252 val = false;
2253 }
2254 if (val)
2255 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2256 }
2257 else if (code2 == EQ_EXPR)
2258 {
2259 bool val;
2260 switch (code1)
2261 {
2262 case EQ_EXPR: val = (cmp == 0); break;
2263 case NE_EXPR: val = (cmp != 0); break;
2264 case LT_EXPR: val = (cmp > 0); break;
2265 case GT_EXPR: val = (cmp < 0); break;
2266 case LE_EXPR: val = (cmp >= 0); break;
2267 case GE_EXPR: val = (cmp <= 0); break;
2268 default:
2269 val = false;
2270 }
2271 if (val)
2272 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2273 }
2274
2275 /* Chose the less restrictive of two < or <= comparisons. */
2276 else if ((code1 == LT_EXPR || code1 == LE_EXPR)
2277 && (code2 == LT_EXPR || code2 == LE_EXPR))
2278 {
2279 if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
2280 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2281 else
2282 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2283 }
2284
2285 /* Likewise chose the less restrictive of two > or >= comparisons. */
2286 else if ((code1 == GT_EXPR || code1 == GE_EXPR)
2287 && (code2 == GT_EXPR || code2 == GE_EXPR))
2288 {
2289 if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
2290 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2291 else
2292 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2293 }
2294
2295 /* Check for singleton ranges. */
2296 else if (cmp == 0
2297 && ((code1 == LT_EXPR && code2 == GT_EXPR)
2298 || (code1 == GT_EXPR && code2 == LT_EXPR)))
2299 return fold_build2 (NE_EXPR, boolean_type_node, op1a, op2b);
2300
2301 /* Check for less/greater pairs that don't restrict the range at all. */
2302 else if (cmp >= 0
2303 && (code1 == LT_EXPR || code1 == LE_EXPR)
2304 && (code2 == GT_EXPR || code2 == GE_EXPR))
2305 return boolean_true_node;
2306 else if (cmp <= 0
2307 && (code1 == GT_EXPR || code1 == GE_EXPR)
2308 && (code2 == LT_EXPR || code2 == LE_EXPR))
2309 return boolean_true_node;
2310 }
2311
2312 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2313 NAME's definition is a truth value. See if there are any simplifications
2314 that can be done against the NAME's definition. */
2315 if (TREE_CODE (op1a) == SSA_NAME
2316 && (code1 == NE_EXPR || code1 == EQ_EXPR)
2317 && (integer_zerop (op1b) || integer_onep (op1b)))
2318 {
2319 bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
2320 || (code1 == NE_EXPR && integer_onep (op1b)));
2321 gimple stmt = SSA_NAME_DEF_STMT (op1a);
2322 switch (gimple_code (stmt))
2323 {
2324 case GIMPLE_ASSIGN:
2325 /* Try to simplify by copy-propagating the definition. */
2326 return or_var_with_comparison (op1a, invert, code2, op2a, op2b);
2327
2328 case GIMPLE_PHI:
2329 /* If every argument to the PHI produces the same result when
2330 ORed with the second comparison, we win.
2331 Do not do this unless the type is bool since we need a bool
2332 result here anyway. */
2333 if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
2334 {
2335 tree result = NULL_TREE;
2336 unsigned i;
2337 for (i = 0; i < gimple_phi_num_args (stmt); i++)
2338 {
2339 tree arg = gimple_phi_arg_def (stmt, i);
2340
2341 /* If this PHI has itself as an argument, ignore it.
2342 If all the other args produce the same result,
2343 we're still OK. */
2344 if (arg == gimple_phi_result (stmt))
2345 continue;
2346 else if (TREE_CODE (arg) == INTEGER_CST)
2347 {
2348 if (invert ? integer_zerop (arg) : integer_nonzerop (arg))
2349 {
2350 if (!result)
2351 result = boolean_true_node;
2352 else if (!integer_onep (result))
2353 return NULL_TREE;
2354 }
2355 else if (!result)
2356 result = fold_build2 (code2, boolean_type_node,
2357 op2a, op2b);
2358 else if (!same_bool_comparison_p (result,
2359 code2, op2a, op2b))
2360 return NULL_TREE;
2361 }
2362 else if (TREE_CODE (arg) == SSA_NAME
2363 && !SSA_NAME_IS_DEFAULT_DEF (arg))
2364 {
2365 tree temp;
2366 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
2367 /* In simple cases we can look through PHI nodes,
2368 but we have to be careful with loops.
2369 See PR49073. */
2370 if (! dom_info_available_p (CDI_DOMINATORS)
2371 || gimple_bb (def_stmt) == gimple_bb (stmt)
2372 || dominated_by_p (CDI_DOMINATORS,
2373 gimple_bb (def_stmt),
2374 gimple_bb (stmt)))
2375 return NULL_TREE;
2376 temp = or_var_with_comparison (arg, invert, code2,
2377 op2a, op2b);
2378 if (!temp)
2379 return NULL_TREE;
2380 else if (!result)
2381 result = temp;
2382 else if (!same_bool_result_p (result, temp))
2383 return NULL_TREE;
2384 }
2385 else
2386 return NULL_TREE;
2387 }
2388 return result;
2389 }
2390
2391 default:
2392 break;
2393 }
2394 }
2395 return NULL_TREE;
2396 }
2397
2398 /* Try to simplify the OR of two comparisons, specified by
2399 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2400 If this can be simplified to a single expression (without requiring
2401 introducing more SSA variables to hold intermediate values),
2402 return the resulting tree. Otherwise return NULL_TREE.
2403 If the result expression is non-null, it has boolean type. */
2404
2405 tree
maybe_fold_or_comparisons(enum tree_code code1,tree op1a,tree op1b,enum tree_code code2,tree op2a,tree op2b)2406 maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
2407 enum tree_code code2, tree op2a, tree op2b)
2408 {
2409 tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
2410 if (t)
2411 return t;
2412 else
2413 return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
2414 }
2415
2416
2417 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2418
2419 Either NULL_TREE, a simplified but non-constant or a constant
2420 is returned.
2421
2422 ??? This should go into a gimple-fold-inline.h file to be eventually
2423 privatized with the single valueize function used in the various TUs
2424 to avoid the indirect function call overhead. */
2425
2426 tree
gimple_fold_stmt_to_constant_1(gimple stmt,tree (* valueize)(tree))2427 gimple_fold_stmt_to_constant_1 (gimple stmt, tree (*valueize) (tree))
2428 {
2429 location_t loc = gimple_location (stmt);
2430 switch (gimple_code (stmt))
2431 {
2432 case GIMPLE_ASSIGN:
2433 {
2434 enum tree_code subcode = gimple_assign_rhs_code (stmt);
2435
2436 switch (get_gimple_rhs_class (subcode))
2437 {
2438 case GIMPLE_SINGLE_RHS:
2439 {
2440 tree rhs = gimple_assign_rhs1 (stmt);
2441 enum tree_code_class kind = TREE_CODE_CLASS (subcode);
2442
2443 if (TREE_CODE (rhs) == SSA_NAME)
2444 {
2445 /* If the RHS is an SSA_NAME, return its known constant value,
2446 if any. */
2447 return (*valueize) (rhs);
2448 }
2449 /* Handle propagating invariant addresses into address
2450 operations. */
2451 else if (TREE_CODE (rhs) == ADDR_EXPR
2452 && !is_gimple_min_invariant (rhs))
2453 {
2454 HOST_WIDE_INT offset;
2455 tree base;
2456 base = get_addr_base_and_unit_offset_1 (TREE_OPERAND (rhs, 0),
2457 &offset,
2458 valueize);
2459 if (base
2460 && (CONSTANT_CLASS_P (base)
2461 || decl_address_invariant_p (base)))
2462 return build_invariant_address (TREE_TYPE (rhs),
2463 base, offset);
2464 }
2465 else if (TREE_CODE (rhs) == CONSTRUCTOR
2466 && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
2467 && (CONSTRUCTOR_NELTS (rhs)
2468 == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
2469 {
2470 unsigned i;
2471 tree val, list;
2472
2473 list = NULL_TREE;
2474 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
2475 {
2476 val = (*valueize) (val);
2477 if (TREE_CODE (val) == INTEGER_CST
2478 || TREE_CODE (val) == REAL_CST
2479 || TREE_CODE (val) == FIXED_CST)
2480 list = tree_cons (NULL_TREE, val, list);
2481 else
2482 return NULL_TREE;
2483 }
2484
2485 return build_vector (TREE_TYPE (rhs), nreverse (list));
2486 }
2487
2488 if (kind == tcc_reference)
2489 {
2490 if ((TREE_CODE (rhs) == VIEW_CONVERT_EXPR
2491 || TREE_CODE (rhs) == REALPART_EXPR
2492 || TREE_CODE (rhs) == IMAGPART_EXPR)
2493 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2494 {
2495 tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2496 return fold_unary_loc (EXPR_LOCATION (rhs),
2497 TREE_CODE (rhs),
2498 TREE_TYPE (rhs), val);
2499 }
2500 else if (TREE_CODE (rhs) == BIT_FIELD_REF
2501 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2502 {
2503 tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2504 return fold_ternary_loc (EXPR_LOCATION (rhs),
2505 TREE_CODE (rhs),
2506 TREE_TYPE (rhs), val,
2507 TREE_OPERAND (rhs, 1),
2508 TREE_OPERAND (rhs, 2));
2509 }
2510 else if (TREE_CODE (rhs) == MEM_REF
2511 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2512 {
2513 tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2514 if (TREE_CODE (val) == ADDR_EXPR
2515 && is_gimple_min_invariant (val))
2516 {
2517 tree tem = fold_build2 (MEM_REF, TREE_TYPE (rhs),
2518 unshare_expr (val),
2519 TREE_OPERAND (rhs, 1));
2520 if (tem)
2521 rhs = tem;
2522 }
2523 }
2524 return fold_const_aggregate_ref_1 (rhs, valueize);
2525 }
2526 else if (kind == tcc_declaration)
2527 return get_symbol_constant_value (rhs);
2528 return rhs;
2529 }
2530
2531 case GIMPLE_UNARY_RHS:
2532 {
2533 /* Handle unary operators that can appear in GIMPLE form.
2534 Note that we know the single operand must be a constant,
2535 so this should almost always return a simplified RHS. */
2536 tree lhs = gimple_assign_lhs (stmt);
2537 tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2538
2539 /* Conversions are useless for CCP purposes if they are
2540 value-preserving. Thus the restrictions that
2541 useless_type_conversion_p places for restrict qualification
2542 of pointer types should not apply here.
2543 Substitution later will only substitute to allowed places. */
2544 if (CONVERT_EXPR_CODE_P (subcode)
2545 && POINTER_TYPE_P (TREE_TYPE (lhs))
2546 && POINTER_TYPE_P (TREE_TYPE (op0))
2547 && TYPE_ADDR_SPACE (TREE_TYPE (lhs))
2548 == TYPE_ADDR_SPACE (TREE_TYPE (op0))
2549 && TYPE_MODE (TREE_TYPE (lhs))
2550 == TYPE_MODE (TREE_TYPE (op0)))
2551 return op0;
2552
2553 return
2554 fold_unary_ignore_overflow_loc (loc, subcode,
2555 gimple_expr_type (stmt), op0);
2556 }
2557
2558 case GIMPLE_BINARY_RHS:
2559 {
2560 /* Handle binary operators that can appear in GIMPLE form. */
2561 tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2562 tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
2563
2564 /* Translate &x + CST into an invariant form suitable for
2565 further propagation. */
2566 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
2567 && TREE_CODE (op0) == ADDR_EXPR
2568 && TREE_CODE (op1) == INTEGER_CST)
2569 {
2570 tree off = fold_convert (ptr_type_node, op1);
2571 return build_fold_addr_expr_loc
2572 (loc,
2573 fold_build2 (MEM_REF,
2574 TREE_TYPE (TREE_TYPE (op0)),
2575 unshare_expr (op0), off));
2576 }
2577
2578 return fold_binary_loc (loc, subcode,
2579 gimple_expr_type (stmt), op0, op1);
2580 }
2581
2582 case GIMPLE_TERNARY_RHS:
2583 {
2584 /* Handle ternary operators that can appear in GIMPLE form. */
2585 tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2586 tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
2587 tree op2 = (*valueize) (gimple_assign_rhs3 (stmt));
2588
2589 /* Fold embedded expressions in ternary codes. */
2590 if ((subcode == COND_EXPR
2591 || subcode == VEC_COND_EXPR)
2592 && COMPARISON_CLASS_P (op0))
2593 {
2594 tree op00 = (*valueize) (TREE_OPERAND (op0, 0));
2595 tree op01 = (*valueize) (TREE_OPERAND (op0, 1));
2596 tree tem = fold_binary_loc (loc, TREE_CODE (op0),
2597 TREE_TYPE (op0), op00, op01);
2598 if (tem)
2599 op0 = tem;
2600 }
2601
2602 return fold_ternary_loc (loc, subcode,
2603 gimple_expr_type (stmt), op0, op1, op2);
2604 }
2605
2606 default:
2607 gcc_unreachable ();
2608 }
2609 }
2610
2611 case GIMPLE_CALL:
2612 {
2613 tree fn;
2614
2615 if (gimple_call_internal_p (stmt))
2616 /* No folding yet for these functions. */
2617 return NULL_TREE;
2618
2619 fn = (*valueize) (gimple_call_fn (stmt));
2620 if (TREE_CODE (fn) == ADDR_EXPR
2621 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
2622 && DECL_BUILT_IN (TREE_OPERAND (fn, 0)))
2623 {
2624 tree *args = XALLOCAVEC (tree, gimple_call_num_args (stmt));
2625 tree call, retval;
2626 unsigned i;
2627 for (i = 0; i < gimple_call_num_args (stmt); ++i)
2628 args[i] = (*valueize) (gimple_call_arg (stmt, i));
2629 call = build_call_array_loc (loc,
2630 gimple_call_return_type (stmt),
2631 fn, gimple_call_num_args (stmt), args);
2632 retval = fold_call_expr (EXPR_LOCATION (call), call, false);
2633 if (retval)
2634 /* fold_call_expr wraps the result inside a NOP_EXPR. */
2635 STRIP_NOPS (retval);
2636 return retval;
2637 }
2638 return NULL_TREE;
2639 }
2640
2641 default:
2642 return NULL_TREE;
2643 }
2644 }
2645
2646 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2647 Returns NULL_TREE if folding to a constant is not possible, otherwise
2648 returns a constant according to is_gimple_min_invariant. */
2649
2650 tree
gimple_fold_stmt_to_constant(gimple stmt,tree (* valueize)(tree))2651 gimple_fold_stmt_to_constant (gimple stmt, tree (*valueize) (tree))
2652 {
2653 tree res = gimple_fold_stmt_to_constant_1 (stmt, valueize);
2654 if (res && is_gimple_min_invariant (res))
2655 return res;
2656 return NULL_TREE;
2657 }
2658
2659
2660 /* The following set of functions are supposed to fold references using
2661 their constant initializers. */
2662
2663 static tree fold_ctor_reference (tree type, tree ctor,
2664 unsigned HOST_WIDE_INT offset,
2665 unsigned HOST_WIDE_INT size);
2666
2667 /* See if we can find constructor defining value of BASE.
2668 When we know the consructor with constant offset (such as
2669 base is array[40] and we do know constructor of array), then
2670 BIT_OFFSET is adjusted accordingly.
2671
2672 As a special case, return error_mark_node when constructor
2673 is not explicitly available, but it is known to be zero
2674 such as 'static const int a;'. */
2675 static tree
get_base_constructor(tree base,HOST_WIDE_INT * bit_offset,tree (* valueize)(tree))2676 get_base_constructor (tree base, HOST_WIDE_INT *bit_offset,
2677 tree (*valueize)(tree))
2678 {
2679 HOST_WIDE_INT bit_offset2, size, max_size;
2680 if (TREE_CODE (base) == MEM_REF)
2681 {
2682 if (!integer_zerop (TREE_OPERAND (base, 1)))
2683 {
2684 if (!host_integerp (TREE_OPERAND (base, 1), 0))
2685 return NULL_TREE;
2686 *bit_offset += (mem_ref_offset (base).low
2687 * BITS_PER_UNIT);
2688 }
2689
2690 if (valueize
2691 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
2692 base = valueize (TREE_OPERAND (base, 0));
2693 if (!base || TREE_CODE (base) != ADDR_EXPR)
2694 return NULL_TREE;
2695 base = TREE_OPERAND (base, 0);
2696 }
2697
2698 /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
2699 DECL_INITIAL. If BASE is a nested reference into another
2700 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
2701 the inner reference. */
2702 switch (TREE_CODE (base))
2703 {
2704 case VAR_DECL:
2705 if (!const_value_known_p (base))
2706 return NULL_TREE;
2707
2708 /* Fallthru. */
2709 case CONST_DECL:
2710 if (!DECL_INITIAL (base)
2711 && (TREE_STATIC (base) || DECL_EXTERNAL (base)))
2712 return error_mark_node;
2713 /* Do not return an error_mark_node DECL_INITIAL. LTO uses this
2714 as special marker (_not_ zero ...) for its own purposes. */
2715 if (DECL_INITIAL (base) == error_mark_node)
2716 return NULL_TREE;
2717 return DECL_INITIAL (base);
2718
2719 case ARRAY_REF:
2720 case COMPONENT_REF:
2721 base = get_ref_base_and_extent (base, &bit_offset2, &size, &max_size);
2722 if (max_size == -1 || size != max_size)
2723 return NULL_TREE;
2724 *bit_offset += bit_offset2;
2725 return get_base_constructor (base, bit_offset, valueize);
2726
2727 case STRING_CST:
2728 case CONSTRUCTOR:
2729 return base;
2730
2731 default:
2732 return NULL_TREE;
2733 }
2734 }
2735
2736 /* CTOR is STRING_CST. Fold reference of type TYPE and size SIZE
2737 to the memory at bit OFFSET.
2738
2739 We do only simple job of folding byte accesses. */
2740
2741 static tree
fold_string_cst_ctor_reference(tree type,tree ctor,unsigned HOST_WIDE_INT offset,unsigned HOST_WIDE_INT size)2742 fold_string_cst_ctor_reference (tree type, tree ctor,
2743 unsigned HOST_WIDE_INT offset,
2744 unsigned HOST_WIDE_INT size)
2745 {
2746 if (INTEGRAL_TYPE_P (type)
2747 && (TYPE_MODE (type)
2748 == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
2749 && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
2750 == MODE_INT)
2751 && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
2752 && size == BITS_PER_UNIT
2753 && !(offset % BITS_PER_UNIT))
2754 {
2755 offset /= BITS_PER_UNIT;
2756 if (offset < (unsigned HOST_WIDE_INT) TREE_STRING_LENGTH (ctor))
2757 return build_int_cst_type (type, (TREE_STRING_POINTER (ctor)
2758 [offset]));
2759 /* Folding
2760 const char a[20]="hello";
2761 return a[10];
2762
2763 might lead to offset greater than string length. In this case we
2764 know value is either initialized to 0 or out of bounds. Return 0
2765 in both cases. */
2766 return build_zero_cst (type);
2767 }
2768 return NULL_TREE;
2769 }
2770
2771 /* CTOR is CONSTRUCTOR of an array type. Fold reference of type TYPE and size
2772 SIZE to the memory at bit OFFSET. */
2773
2774 static tree
fold_array_ctor_reference(tree type,tree ctor,unsigned HOST_WIDE_INT offset,unsigned HOST_WIDE_INT size)2775 fold_array_ctor_reference (tree type, tree ctor,
2776 unsigned HOST_WIDE_INT offset,
2777 unsigned HOST_WIDE_INT size)
2778 {
2779 unsigned HOST_WIDE_INT cnt;
2780 tree cfield, cval;
2781 double_int low_bound, elt_size;
2782 double_int index, max_index;
2783 double_int access_index;
2784 tree domain_type = NULL_TREE;
2785 HOST_WIDE_INT inner_offset;
2786
2787 /* Compute low bound and elt size. */
2788 if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE)
2789 domain_type = TYPE_DOMAIN (TREE_TYPE (ctor));
2790 if (domain_type && TYPE_MIN_VALUE (domain_type))
2791 {
2792 /* Static constructors for variably sized objects makes no sense. */
2793 gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
2794 low_bound = tree_to_double_int (TYPE_MIN_VALUE (domain_type));
2795 }
2796 else
2797 low_bound = double_int_zero;
2798 /* Static constructors for variably sized objects makes no sense. */
2799 gcc_assert (TREE_CODE(TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))))
2800 == INTEGER_CST);
2801 elt_size =
2802 tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))));
2803
2804
2805 /* We can handle only constantly sized accesses that are known to not
2806 be larger than size of array element. */
2807 if (!TYPE_SIZE_UNIT (type)
2808 || TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST
2809 || double_int_cmp (elt_size,
2810 tree_to_double_int (TYPE_SIZE_UNIT (type)), 0) < 0)
2811 return NULL_TREE;
2812
2813 /* Compute the array index we look for. */
2814 access_index = double_int_udiv (uhwi_to_double_int (offset / BITS_PER_UNIT),
2815 elt_size, TRUNC_DIV_EXPR);
2816 access_index = double_int_add (access_index, low_bound);
2817
2818 /* And offset within the access. */
2819 inner_offset = offset % (double_int_to_uhwi (elt_size) * BITS_PER_UNIT);
2820
2821 /* See if the array field is large enough to span whole access. We do not
2822 care to fold accesses spanning multiple array indexes. */
2823 if (inner_offset + size > double_int_to_uhwi (elt_size) * BITS_PER_UNIT)
2824 return NULL_TREE;
2825
2826 index = double_int_sub (low_bound, double_int_one);
2827 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
2828 {
2829 /* Array constructor might explicitely set index, or specify range
2830 or leave index NULL meaning that it is next index after previous
2831 one. */
2832 if (cfield)
2833 {
2834 if (TREE_CODE (cfield) == INTEGER_CST)
2835 max_index = index = tree_to_double_int (cfield);
2836 else
2837 {
2838 gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
2839 index = tree_to_double_int (TREE_OPERAND (cfield, 0));
2840 max_index = tree_to_double_int (TREE_OPERAND (cfield, 1));
2841 }
2842 }
2843 else
2844 max_index = index = double_int_add (index, double_int_one);
2845
2846 /* Do we have match? */
2847 if (double_int_cmp (access_index, index, 1) >= 0
2848 && double_int_cmp (access_index, max_index, 1) <= 0)
2849 return fold_ctor_reference (type, cval, inner_offset, size);
2850 }
2851 /* When memory is not explicitely mentioned in constructor,
2852 it is 0 (or out of range). */
2853 return build_zero_cst (type);
2854 }
2855
2856 /* CTOR is CONSTRUCTOR of an aggregate or vector.
2857 Fold reference of type TYPE and size SIZE to the memory at bit OFFSET. */
2858
2859 static tree
fold_nonarray_ctor_reference(tree type,tree ctor,unsigned HOST_WIDE_INT offset,unsigned HOST_WIDE_INT size)2860 fold_nonarray_ctor_reference (tree type, tree ctor,
2861 unsigned HOST_WIDE_INT offset,
2862 unsigned HOST_WIDE_INT size)
2863 {
2864 unsigned HOST_WIDE_INT cnt;
2865 tree cfield, cval;
2866
2867 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield,
2868 cval)
2869 {
2870 tree byte_offset = DECL_FIELD_OFFSET (cfield);
2871 tree field_offset = DECL_FIELD_BIT_OFFSET (cfield);
2872 tree field_size = DECL_SIZE (cfield);
2873 double_int bitoffset;
2874 double_int byte_offset_cst = tree_to_double_int (byte_offset);
2875 double_int bits_per_unit_cst = uhwi_to_double_int (BITS_PER_UNIT);
2876 double_int bitoffset_end, access_end;
2877
2878 /* Variable sized objects in static constructors makes no sense,
2879 but field_size can be NULL for flexible array members. */
2880 gcc_assert (TREE_CODE (field_offset) == INTEGER_CST
2881 && TREE_CODE (byte_offset) == INTEGER_CST
2882 && (field_size != NULL_TREE
2883 ? TREE_CODE (field_size) == INTEGER_CST
2884 : TREE_CODE (TREE_TYPE (cfield)) == ARRAY_TYPE));
2885
2886 /* Compute bit offset of the field. */
2887 bitoffset = double_int_add (tree_to_double_int (field_offset),
2888 double_int_mul (byte_offset_cst,
2889 bits_per_unit_cst));
2890 /* Compute bit offset where the field ends. */
2891 if (field_size != NULL_TREE)
2892 bitoffset_end = double_int_add (bitoffset,
2893 tree_to_double_int (field_size));
2894 else
2895 bitoffset_end = double_int_zero;
2896
2897 access_end = double_int_add (uhwi_to_double_int (offset),
2898 uhwi_to_double_int (size));
2899
2900 /* Is there any overlap between [OFFSET, OFFSET+SIZE) and
2901 [BITOFFSET, BITOFFSET_END)? */
2902 if (double_int_cmp (access_end, bitoffset, 0) > 0
2903 && (field_size == NULL_TREE
2904 || double_int_cmp (uhwi_to_double_int (offset),
2905 bitoffset_end, 0) < 0))
2906 {
2907 double_int inner_offset = double_int_sub (uhwi_to_double_int (offset),
2908 bitoffset);
2909 /* We do have overlap. Now see if field is large enough to
2910 cover the access. Give up for accesses spanning multiple
2911 fields. */
2912 if (double_int_cmp (access_end, bitoffset_end, 0) > 0)
2913 return NULL_TREE;
2914 if (double_int_cmp (uhwi_to_double_int (offset), bitoffset, 0) < 0)
2915 return NULL_TREE;
2916 return fold_ctor_reference (type, cval,
2917 double_int_to_uhwi (inner_offset), size);
2918 }
2919 }
2920 /* When memory is not explicitely mentioned in constructor, it is 0. */
2921 return build_zero_cst (type);
2922 }
2923
2924 /* CTOR is value initializing memory, fold reference of type TYPE and size SIZE
2925 to the memory at bit OFFSET. */
2926
2927 static tree
fold_ctor_reference(tree type,tree ctor,unsigned HOST_WIDE_INT offset,unsigned HOST_WIDE_INT size)2928 fold_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
2929 unsigned HOST_WIDE_INT size)
2930 {
2931 tree ret;
2932
2933 /* We found the field with exact match. */
2934 if (useless_type_conversion_p (type, TREE_TYPE (ctor))
2935 && !offset)
2936 return canonicalize_constructor_val (ctor);
2937
2938 /* We are at the end of walk, see if we can view convert the
2939 result. */
2940 if (!AGGREGATE_TYPE_P (TREE_TYPE (ctor)) && !offset
2941 /* VIEW_CONVERT_EXPR is defined only for matching sizes. */
2942 && operand_equal_p (TYPE_SIZE (type),
2943 TYPE_SIZE (TREE_TYPE (ctor)), 0))
2944 {
2945 ret = canonicalize_constructor_val (ctor);
2946 ret = fold_unary (VIEW_CONVERT_EXPR, type, ret);
2947 if (ret)
2948 STRIP_NOPS (ret);
2949 return ret;
2950 }
2951 if (TREE_CODE (ctor) == STRING_CST)
2952 return fold_string_cst_ctor_reference (type, ctor, offset, size);
2953 if (TREE_CODE (ctor) == CONSTRUCTOR)
2954 {
2955
2956 if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE
2957 || TREE_CODE (TREE_TYPE (ctor)) == VECTOR_TYPE)
2958 return fold_array_ctor_reference (type, ctor, offset, size);
2959 else
2960 return fold_nonarray_ctor_reference (type, ctor, offset, size);
2961 }
2962
2963 return NULL_TREE;
2964 }
2965
2966 /* Return the tree representing the element referenced by T if T is an
2967 ARRAY_REF or COMPONENT_REF into constant aggregates valuezing SSA
2968 names using VALUEIZE. Return NULL_TREE otherwise. */
2969
2970 tree
fold_const_aggregate_ref_1(tree t,tree (* valueize)(tree))2971 fold_const_aggregate_ref_1 (tree t, tree (*valueize) (tree))
2972 {
2973 tree ctor, idx, base;
2974 HOST_WIDE_INT offset, size, max_size;
2975 tree tem;
2976
2977 if (TREE_THIS_VOLATILE (t))
2978 return NULL_TREE;
2979
2980 if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
2981 return get_symbol_constant_value (t);
2982
2983 tem = fold_read_from_constant_string (t);
2984 if (tem)
2985 return tem;
2986
2987 switch (TREE_CODE (t))
2988 {
2989 case ARRAY_REF:
2990 case ARRAY_RANGE_REF:
2991 /* Constant indexes are handled well by get_base_constructor.
2992 Only special case variable offsets.
2993 FIXME: This code can't handle nested references with variable indexes
2994 (they will be handled only by iteration of ccp). Perhaps we can bring
2995 get_ref_base_and_extent here and make it use a valueize callback. */
2996 if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME
2997 && valueize
2998 && (idx = (*valueize) (TREE_OPERAND (t, 1)))
2999 && host_integerp (idx, 0))
3000 {
3001 tree low_bound, unit_size;
3002
3003 /* If the resulting bit-offset is constant, track it. */
3004 if ((low_bound = array_ref_low_bound (t),
3005 host_integerp (low_bound, 0))
3006 && (unit_size = array_ref_element_size (t),
3007 host_integerp (unit_size, 1)))
3008 {
3009 offset = TREE_INT_CST_LOW (idx);
3010 offset -= TREE_INT_CST_LOW (low_bound);
3011 offset *= TREE_INT_CST_LOW (unit_size);
3012 offset *= BITS_PER_UNIT;
3013
3014 base = TREE_OPERAND (t, 0);
3015 ctor = get_base_constructor (base, &offset, valueize);
3016 /* Empty constructor. Always fold to 0. */
3017 if (ctor == error_mark_node)
3018 return build_zero_cst (TREE_TYPE (t));
3019 /* Out of bound array access. Value is undefined,
3020 but don't fold. */
3021 if (offset < 0)
3022 return NULL_TREE;
3023 /* We can not determine ctor. */
3024 if (!ctor)
3025 return NULL_TREE;
3026 return fold_ctor_reference (TREE_TYPE (t), ctor, offset,
3027 TREE_INT_CST_LOW (unit_size)
3028 * BITS_PER_UNIT);
3029 }
3030 }
3031 /* Fallthru. */
3032
3033 case COMPONENT_REF:
3034 case BIT_FIELD_REF:
3035 case TARGET_MEM_REF:
3036 case MEM_REF:
3037 base = get_ref_base_and_extent (t, &offset, &size, &max_size);
3038 ctor = get_base_constructor (base, &offset, valueize);
3039
3040 /* Empty constructor. Always fold to 0. */
3041 if (ctor == error_mark_node)
3042 return build_zero_cst (TREE_TYPE (t));
3043 /* We do not know precise address. */
3044 if (max_size == -1 || max_size != size)
3045 return NULL_TREE;
3046 /* We can not determine ctor. */
3047 if (!ctor)
3048 return NULL_TREE;
3049
3050 /* Out of bound array access. Value is undefined, but don't fold. */
3051 if (offset < 0)
3052 return NULL_TREE;
3053
3054 return fold_ctor_reference (TREE_TYPE (t), ctor, offset, size);
3055
3056 case REALPART_EXPR:
3057 case IMAGPART_EXPR:
3058 {
3059 tree c = fold_const_aggregate_ref_1 (TREE_OPERAND (t, 0), valueize);
3060 if (c && TREE_CODE (c) == COMPLEX_CST)
3061 return fold_build1_loc (EXPR_LOCATION (t),
3062 TREE_CODE (t), TREE_TYPE (t), c);
3063 break;
3064 }
3065
3066 default:
3067 break;
3068 }
3069
3070 return NULL_TREE;
3071 }
3072
3073 tree
fold_const_aggregate_ref(tree t)3074 fold_const_aggregate_ref (tree t)
3075 {
3076 return fold_const_aggregate_ref_1 (t, NULL);
3077 }
3078
3079 /* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN
3080 is integer form of OBJ_TYPE_REF_TOKEN of the reference expression.
3081 KNOWN_BINFO carries the binfo describing the true type of
3082 OBJ_TYPE_REF_OBJECT(REF). */
3083
3084 tree
gimple_get_virt_method_for_binfo(HOST_WIDE_INT token,tree known_binfo)3085 gimple_get_virt_method_for_binfo (HOST_WIDE_INT token, tree known_binfo)
3086 {
3087 unsigned HOST_WIDE_INT offset, size;
3088 tree v, fn;
3089
3090 v = BINFO_VTABLE (known_binfo);
3091 /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone. */
3092 if (!v)
3093 return NULL_TREE;
3094
3095 if (TREE_CODE (v) == POINTER_PLUS_EXPR)
3096 {
3097 offset = tree_low_cst (TREE_OPERAND (v, 1), 1) * BITS_PER_UNIT;
3098 v = TREE_OPERAND (v, 0);
3099 }
3100 else
3101 offset = 0;
3102
3103 if (TREE_CODE (v) != ADDR_EXPR)
3104 return NULL_TREE;
3105 v = TREE_OPERAND (v, 0);
3106
3107 if (TREE_CODE (v) != VAR_DECL
3108 || !DECL_VIRTUAL_P (v)
3109 || !DECL_INITIAL (v)
3110 || DECL_INITIAL (v) == error_mark_node)
3111 return NULL_TREE;
3112 gcc_checking_assert (TREE_CODE (TREE_TYPE (v)) == ARRAY_TYPE);
3113 size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (v))), 1);
3114 offset += token * size;
3115 fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), DECL_INITIAL (v),
3116 offset, size);
3117 if (!fn || integer_zerop (fn))
3118 return NULL_TREE;
3119 gcc_assert (TREE_CODE (fn) == ADDR_EXPR
3120 || TREE_CODE (fn) == FDESC_EXPR);
3121 fn = TREE_OPERAND (fn, 0);
3122 gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
3123
3124 /* When cgraph node is missing and function is not public, we cannot
3125 devirtualize. This can happen in WHOPR when the actual method
3126 ends up in other partition, because we found devirtualization
3127 possibility too late. */
3128 if (!can_refer_decl_in_current_unit_p (fn))
3129 return NULL_TREE;
3130
3131 return fn;
3132 }
3133
3134 /* Return true iff VAL is a gimple expression that is known to be
3135 non-negative. Restricted to floating-point inputs. */
3136
3137 bool
gimple_val_nonnegative_real_p(tree val)3138 gimple_val_nonnegative_real_p (tree val)
3139 {
3140 gimple def_stmt;
3141
3142 gcc_assert (val && SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)));
3143
3144 /* Use existing logic for non-gimple trees. */
3145 if (tree_expr_nonnegative_p (val))
3146 return true;
3147
3148 if (TREE_CODE (val) != SSA_NAME)
3149 return false;
3150
3151 /* Currently we look only at the immediately defining statement
3152 to make this determination, since recursion on defining
3153 statements of operands can lead to quadratic behavior in the
3154 worst case. This is expected to catch almost all occurrences
3155 in practice. It would be possible to implement limited-depth
3156 recursion if important cases are lost. Alternatively, passes
3157 that need this information (such as the pow/powi lowering code
3158 in the cse_sincos pass) could be revised to provide it through
3159 dataflow propagation. */
3160
3161 def_stmt = SSA_NAME_DEF_STMT (val);
3162
3163 if (is_gimple_assign (def_stmt))
3164 {
3165 tree op0, op1;
3166
3167 /* See fold-const.c:tree_expr_nonnegative_p for additional
3168 cases that could be handled with recursion. */
3169
3170 switch (gimple_assign_rhs_code (def_stmt))
3171 {
3172 case ABS_EXPR:
3173 /* Always true for floating-point operands. */
3174 return true;
3175
3176 case MULT_EXPR:
3177 /* True if the two operands are identical (since we are
3178 restricted to floating-point inputs). */
3179 op0 = gimple_assign_rhs1 (def_stmt);
3180 op1 = gimple_assign_rhs2 (def_stmt);
3181
3182 if (op0 == op1
3183 || operand_equal_p (op0, op1, 0))
3184 return true;
3185
3186 default:
3187 return false;
3188 }
3189 }
3190 else if (is_gimple_call (def_stmt))
3191 {
3192 tree fndecl = gimple_call_fndecl (def_stmt);
3193 if (fndecl
3194 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3195 {
3196 tree arg1;
3197
3198 switch (DECL_FUNCTION_CODE (fndecl))
3199 {
3200 CASE_FLT_FN (BUILT_IN_ACOS):
3201 CASE_FLT_FN (BUILT_IN_ACOSH):
3202 CASE_FLT_FN (BUILT_IN_CABS):
3203 CASE_FLT_FN (BUILT_IN_COSH):
3204 CASE_FLT_FN (BUILT_IN_ERFC):
3205 CASE_FLT_FN (BUILT_IN_EXP):
3206 CASE_FLT_FN (BUILT_IN_EXP10):
3207 CASE_FLT_FN (BUILT_IN_EXP2):
3208 CASE_FLT_FN (BUILT_IN_FABS):
3209 CASE_FLT_FN (BUILT_IN_FDIM):
3210 CASE_FLT_FN (BUILT_IN_HYPOT):
3211 CASE_FLT_FN (BUILT_IN_POW10):
3212 return true;
3213
3214 CASE_FLT_FN (BUILT_IN_SQRT):
3215 /* sqrt(-0.0) is -0.0, and sqrt is not defined over other
3216 nonnegative inputs. */
3217 if (!HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (val))))
3218 return true;
3219
3220 break;
3221
3222 CASE_FLT_FN (BUILT_IN_POWI):
3223 /* True if the second argument is an even integer. */
3224 arg1 = gimple_call_arg (def_stmt, 1);
3225
3226 if (TREE_CODE (arg1) == INTEGER_CST
3227 && (TREE_INT_CST_LOW (arg1) & 1) == 0)
3228 return true;
3229
3230 break;
3231
3232 CASE_FLT_FN (BUILT_IN_POW):
3233 /* True if the second argument is an even integer-valued
3234 real. */
3235 arg1 = gimple_call_arg (def_stmt, 1);
3236
3237 if (TREE_CODE (arg1) == REAL_CST)
3238 {
3239 REAL_VALUE_TYPE c;
3240 HOST_WIDE_INT n;
3241
3242 c = TREE_REAL_CST (arg1);
3243 n = real_to_integer (&c);
3244
3245 if ((n & 1) == 0)
3246 {
3247 REAL_VALUE_TYPE cint;
3248 real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0, 0);
3249 if (real_identical (&c, &cint))
3250 return true;
3251 }
3252 }
3253
3254 break;
3255
3256 default:
3257 return false;
3258 }
3259 }
3260 }
3261
3262 return false;
3263 }
3264