1 /* Conditional constant propagation pass for the GNU compiler.
2 Copyright (C) 2000-2022 Free Software Foundation, Inc.
3 Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
4 Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
11 later version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 /* Conditional constant propagation (CCP) is based on the SSA
23 propagation engine (tree-ssa-propagate.cc). Constant assignments of
24 the form VAR = CST are propagated from the assignments into uses of
25 VAR, which in turn may generate new constants. The simulation uses
26 a four level lattice to keep track of constant values associated
27 with SSA names. Given an SSA name V_i, it may take one of the
28 following values:
29
30 UNINITIALIZED -> the initial state of the value. This value
31 is replaced with a correct initial value
32 the first time the value is used, so the
33 rest of the pass does not need to care about
34 it. Using this value simplifies initialization
35 of the pass, and prevents us from needlessly
36 scanning statements that are never reached.
37
38 UNDEFINED -> V_i is a local variable whose definition
39 has not been processed yet. Therefore we
40 don't yet know if its value is a constant
41 or not.
42
43 CONSTANT -> V_i has been found to hold a constant
44 value C.
45
46 VARYING -> V_i cannot take a constant value, or if it
47 does, it is not possible to determine it
48 at compile time.
49
50 The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
51
52 1- In ccp_visit_stmt, we are interested in assignments whose RHS
53 evaluates into a constant and conditional jumps whose predicate
54 evaluates into a boolean true or false. When an assignment of
55 the form V_i = CONST is found, V_i's lattice value is set to
56 CONSTANT and CONST is associated with it. This causes the
57 propagation engine to add all the SSA edges coming out the
58 assignment into the worklists, so that statements that use V_i
59 can be visited.
60
61 If the statement is a conditional with a constant predicate, we
62 mark the outgoing edges as executable or not executable
63 depending on the predicate's value. This is then used when
64 visiting PHI nodes to know when a PHI argument can be ignored.
65
66
67 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
68 same constant C, then the LHS of the PHI is set to C. This
69 evaluation is known as the "meet operation". Since one of the
70 goals of this evaluation is to optimistically return constant
71 values as often as possible, it uses two main short cuts:
72
73 - If an argument is flowing in through a non-executable edge, it
74 is ignored. This is useful in cases like this:
75
76 if (PRED)
77 a_9 = 3;
78 else
79 a_10 = 100;
80 a_11 = PHI (a_9, a_10)
81
82 If PRED is known to always evaluate to false, then we can
83 assume that a_11 will always take its value from a_10, meaning
84 that instead of consider it VARYING (a_9 and a_10 have
85 different values), we can consider it CONSTANT 100.
86
87 - If an argument has an UNDEFINED value, then it does not affect
88 the outcome of the meet operation. If a variable V_i has an
89 UNDEFINED value, it means that either its defining statement
90 hasn't been visited yet or V_i has no defining statement, in
91 which case the original symbol 'V' is being used
92 uninitialized. Since 'V' is a local variable, the compiler
93 may assume any initial value for it.
94
95
96 After propagation, every variable V_i that ends up with a lattice
97 value of CONSTANT will have the associated constant value in the
98 array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
99 final substitution and folding.
100
101 This algorithm uses wide-ints at the max precision of the target.
102 This means that, with one uninteresting exception, variables with
103 UNSIGNED types never go to VARYING because the bits above the
104 precision of the type of the variable are always zero. The
105 uninteresting case is a variable of UNSIGNED type that has the
106 maximum precision of the target. Such variables can go to VARYING,
107 but this causes no loss of infomation since these variables will
108 never be extended.
109
110 References:
111
112 Constant propagation with conditional branches,
113 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
114
115 Building an Optimizing Compiler,
116 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
117
118 Advanced Compiler Design and Implementation,
119 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
120
121 #include "config.h"
122 #include "system.h"
123 #include "coretypes.h"
124 #include "backend.h"
125 #include "target.h"
126 #include "tree.h"
127 #include "gimple.h"
128 #include "tree-pass.h"
129 #include "ssa.h"
130 #include "gimple-pretty-print.h"
131 #include "fold-const.h"
132 #include "gimple-fold.h"
133 #include "tree-eh.h"
134 #include "gimplify.h"
135 #include "gimple-iterator.h"
136 #include "tree-cfg.h"
137 #include "tree-ssa-propagate.h"
138 #include "dbgcnt.h"
139 #include "builtins.h"
140 #include "cfgloop.h"
141 #include "stor-layout.h"
142 #include "optabs-query.h"
143 #include "tree-ssa-ccp.h"
144 #include "tree-dfa.h"
145 #include "diagnostic-core.h"
146 #include "stringpool.h"
147 #include "attribs.h"
148 #include "tree-vector-builder.h"
149 #include "cgraph.h"
150 #include "alloc-pool.h"
151 #include "symbol-summary.h"
152 #include "ipa-utils.h"
153 #include "ipa-prop.h"
154 #include "internal-fn.h"
155
156 /* Possible lattice values. */
157 typedef enum
158 {
159 UNINITIALIZED,
160 UNDEFINED,
161 CONSTANT,
162 VARYING
163 } ccp_lattice_t;
164
165 class ccp_prop_value_t {
166 public:
167 /* Lattice value. */
168 ccp_lattice_t lattice_val;
169
170 /* Propagated value. */
171 tree value;
172
173 /* Mask that applies to the propagated value during CCP. For X
174 with a CONSTANT lattice value X & ~mask == value & ~mask. The
175 zero bits in the mask cover constant values. The ones mean no
176 information. */
177 widest_int mask;
178 };
179
180 class ccp_propagate : public ssa_propagation_engine
181 {
182 public:
183 enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) FINAL OVERRIDE;
184 enum ssa_prop_result visit_phi (gphi *) FINAL OVERRIDE;
185 };
186
187 /* Array of propagated constant values. After propagation,
188 CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
189 the constant is held in an SSA name representing a memory store
190 (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
191 memory reference used to store (i.e., the LHS of the assignment
192 doing the store). */
193 static ccp_prop_value_t *const_val;
194 static unsigned n_const_val;
195
196 static void canonicalize_value (ccp_prop_value_t *);
197 static void ccp_lattice_meet (ccp_prop_value_t *, ccp_prop_value_t *);
198
199 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
200
201 static void
dump_lattice_value(FILE * outf,const char * prefix,ccp_prop_value_t val)202 dump_lattice_value (FILE *outf, const char *prefix, ccp_prop_value_t val)
203 {
204 switch (val.lattice_val)
205 {
206 case UNINITIALIZED:
207 fprintf (outf, "%sUNINITIALIZED", prefix);
208 break;
209 case UNDEFINED:
210 fprintf (outf, "%sUNDEFINED", prefix);
211 break;
212 case VARYING:
213 fprintf (outf, "%sVARYING", prefix);
214 break;
215 case CONSTANT:
216 if (TREE_CODE (val.value) != INTEGER_CST
217 || val.mask == 0)
218 {
219 fprintf (outf, "%sCONSTANT ", prefix);
220 print_generic_expr (outf, val.value, dump_flags);
221 }
222 else
223 {
224 widest_int cval = wi::bit_and_not (wi::to_widest (val.value),
225 val.mask);
226 fprintf (outf, "%sCONSTANT ", prefix);
227 print_hex (cval, outf);
228 fprintf (outf, " (");
229 print_hex (val.mask, outf);
230 fprintf (outf, ")");
231 }
232 break;
233 default:
234 gcc_unreachable ();
235 }
236 }
237
238
239 /* Print lattice value VAL to stderr. */
240
241 void debug_lattice_value (ccp_prop_value_t val);
242
243 DEBUG_FUNCTION void
debug_lattice_value(ccp_prop_value_t val)244 debug_lattice_value (ccp_prop_value_t val)
245 {
246 dump_lattice_value (stderr, "", val);
247 fprintf (stderr, "\n");
248 }
249
250 /* Extend NONZERO_BITS to a full mask, based on sgn. */
251
252 static widest_int
extend_mask(const wide_int & nonzero_bits,signop sgn)253 extend_mask (const wide_int &nonzero_bits, signop sgn)
254 {
255 return widest_int::from (nonzero_bits, sgn);
256 }
257
258 /* Compute a default value for variable VAR and store it in the
259 CONST_VAL array. The following rules are used to get default
260 values:
261
262 1- Global and static variables that are declared constant are
263 considered CONSTANT.
264
265 2- Any other value is considered UNDEFINED. This is useful when
266 considering PHI nodes. PHI arguments that are undefined do not
267 change the constant value of the PHI node, which allows for more
268 constants to be propagated.
269
270 3- Variables defined by statements other than assignments and PHI
271 nodes are considered VARYING.
272
273 4- Initial values of variables that are not GIMPLE registers are
274 considered VARYING. */
275
276 static ccp_prop_value_t
get_default_value(tree var)277 get_default_value (tree var)
278 {
279 ccp_prop_value_t val = { UNINITIALIZED, NULL_TREE, 0 };
280 gimple *stmt;
281
282 stmt = SSA_NAME_DEF_STMT (var);
283
284 if (gimple_nop_p (stmt))
285 {
286 /* Variables defined by an empty statement are those used
287 before being initialized. If VAR is a local variable, we
288 can assume initially that it is UNDEFINED, otherwise we must
289 consider it VARYING. */
290 if (!virtual_operand_p (var)
291 && SSA_NAME_VAR (var)
292 && TREE_CODE (SSA_NAME_VAR (var)) == VAR_DECL)
293 val.lattice_val = UNDEFINED;
294 else
295 {
296 val.lattice_val = VARYING;
297 val.mask = -1;
298 if (flag_tree_bit_ccp)
299 {
300 wide_int nonzero_bits = get_nonzero_bits (var);
301 tree value;
302 widest_int mask;
303
304 if (SSA_NAME_VAR (var)
305 && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
306 && ipcp_get_parm_bits (SSA_NAME_VAR (var), &value, &mask))
307 {
308 val.lattice_val = CONSTANT;
309 val.value = value;
310 widest_int ipa_value = wi::to_widest (value);
311 /* Unknown bits from IPA CP must be equal to zero. */
312 gcc_assert (wi::bit_and (ipa_value, mask) == 0);
313 val.mask = mask;
314 if (nonzero_bits != -1)
315 val.mask &= extend_mask (nonzero_bits,
316 TYPE_SIGN (TREE_TYPE (var)));
317 }
318 else if (nonzero_bits != -1)
319 {
320 val.lattice_val = CONSTANT;
321 val.value = build_zero_cst (TREE_TYPE (var));
322 val.mask = extend_mask (nonzero_bits,
323 TYPE_SIGN (TREE_TYPE (var)));
324 }
325 }
326 }
327 }
328 else if (is_gimple_assign (stmt))
329 {
330 tree cst;
331 if (gimple_assign_single_p (stmt)
332 && DECL_P (gimple_assign_rhs1 (stmt))
333 && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
334 {
335 val.lattice_val = CONSTANT;
336 val.value = cst;
337 }
338 else
339 {
340 /* Any other variable defined by an assignment is considered
341 UNDEFINED. */
342 val.lattice_val = UNDEFINED;
343 }
344 }
345 else if ((is_gimple_call (stmt)
346 && gimple_call_lhs (stmt) != NULL_TREE)
347 || gimple_code (stmt) == GIMPLE_PHI)
348 {
349 /* A variable defined by a call or a PHI node is considered
350 UNDEFINED. */
351 val.lattice_val = UNDEFINED;
352 }
353 else
354 {
355 /* Otherwise, VAR will never take on a constant value. */
356 val.lattice_val = VARYING;
357 val.mask = -1;
358 }
359
360 return val;
361 }
362
363
364 /* Get the constant value associated with variable VAR. */
365
366 static inline ccp_prop_value_t *
get_value(tree var)367 get_value (tree var)
368 {
369 ccp_prop_value_t *val;
370
371 if (const_val == NULL
372 || SSA_NAME_VERSION (var) >= n_const_val)
373 return NULL;
374
375 val = &const_val[SSA_NAME_VERSION (var)];
376 if (val->lattice_val == UNINITIALIZED)
377 *val = get_default_value (var);
378
379 canonicalize_value (val);
380
381 return val;
382 }
383
384 /* Return the constant tree value associated with VAR. */
385
386 static inline tree
get_constant_value(tree var)387 get_constant_value (tree var)
388 {
389 ccp_prop_value_t *val;
390 if (TREE_CODE (var) != SSA_NAME)
391 {
392 if (is_gimple_min_invariant (var))
393 return var;
394 return NULL_TREE;
395 }
396 val = get_value (var);
397 if (val
398 && val->lattice_val == CONSTANT
399 && (TREE_CODE (val->value) != INTEGER_CST
400 || val->mask == 0))
401 return val->value;
402 return NULL_TREE;
403 }
404
405 /* Sets the value associated with VAR to VARYING. */
406
407 static inline void
set_value_varying(tree var)408 set_value_varying (tree var)
409 {
410 ccp_prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
411
412 val->lattice_val = VARYING;
413 val->value = NULL_TREE;
414 val->mask = -1;
415 }
416
417 /* For integer constants, make sure to drop TREE_OVERFLOW. */
418
419 static void
canonicalize_value(ccp_prop_value_t * val)420 canonicalize_value (ccp_prop_value_t *val)
421 {
422 if (val->lattice_val != CONSTANT)
423 return;
424
425 if (TREE_OVERFLOW_P (val->value))
426 val->value = drop_tree_overflow (val->value);
427 }
428
429 /* Return whether the lattice transition is valid. */
430
431 static bool
valid_lattice_transition(ccp_prop_value_t old_val,ccp_prop_value_t new_val)432 valid_lattice_transition (ccp_prop_value_t old_val, ccp_prop_value_t new_val)
433 {
434 /* Lattice transitions must always be monotonically increasing in
435 value. */
436 if (old_val.lattice_val < new_val.lattice_val)
437 return true;
438
439 if (old_val.lattice_val != new_val.lattice_val)
440 return false;
441
442 if (!old_val.value && !new_val.value)
443 return true;
444
445 /* Now both lattice values are CONSTANT. */
446
447 /* Allow arbitrary copy changes as we might look through PHI <a_1, ...>
448 when only a single copy edge is executable. */
449 if (TREE_CODE (old_val.value) == SSA_NAME
450 && TREE_CODE (new_val.value) == SSA_NAME)
451 return true;
452
453 /* Allow transitioning from a constant to a copy. */
454 if (is_gimple_min_invariant (old_val.value)
455 && TREE_CODE (new_val.value) == SSA_NAME)
456 return true;
457
458 /* Allow transitioning from PHI <&x, not executable> == &x
459 to PHI <&x, &y> == common alignment. */
460 if (TREE_CODE (old_val.value) != INTEGER_CST
461 && TREE_CODE (new_val.value) == INTEGER_CST)
462 return true;
463
464 /* Bit-lattices have to agree in the still valid bits. */
465 if (TREE_CODE (old_val.value) == INTEGER_CST
466 && TREE_CODE (new_val.value) == INTEGER_CST)
467 return (wi::bit_and_not (wi::to_widest (old_val.value), new_val.mask)
468 == wi::bit_and_not (wi::to_widest (new_val.value), new_val.mask));
469
470 /* Otherwise constant values have to agree. */
471 if (operand_equal_p (old_val.value, new_val.value, 0))
472 return true;
473
474 /* At least the kinds and types should agree now. */
475 if (TREE_CODE (old_val.value) != TREE_CODE (new_val.value)
476 || !types_compatible_p (TREE_TYPE (old_val.value),
477 TREE_TYPE (new_val.value)))
478 return false;
479
480 /* For floats and !HONOR_NANS allow transitions from (partial) NaN
481 to non-NaN. */
482 tree type = TREE_TYPE (new_val.value);
483 if (SCALAR_FLOAT_TYPE_P (type)
484 && !HONOR_NANS (type))
485 {
486 if (REAL_VALUE_ISNAN (TREE_REAL_CST (old_val.value)))
487 return true;
488 }
489 else if (VECTOR_FLOAT_TYPE_P (type)
490 && !HONOR_NANS (type))
491 {
492 unsigned int count
493 = tree_vector_builder::binary_encoded_nelts (old_val.value,
494 new_val.value);
495 for (unsigned int i = 0; i < count; ++i)
496 if (!REAL_VALUE_ISNAN
497 (TREE_REAL_CST (VECTOR_CST_ENCODED_ELT (old_val.value, i)))
498 && !operand_equal_p (VECTOR_CST_ENCODED_ELT (old_val.value, i),
499 VECTOR_CST_ENCODED_ELT (new_val.value, i), 0))
500 return false;
501 return true;
502 }
503 else if (COMPLEX_FLOAT_TYPE_P (type)
504 && !HONOR_NANS (type))
505 {
506 if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_REALPART (old_val.value)))
507 && !operand_equal_p (TREE_REALPART (old_val.value),
508 TREE_REALPART (new_val.value), 0))
509 return false;
510 if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_IMAGPART (old_val.value)))
511 && !operand_equal_p (TREE_IMAGPART (old_val.value),
512 TREE_IMAGPART (new_val.value), 0))
513 return false;
514 return true;
515 }
516 return false;
517 }
518
519 /* Set the value for variable VAR to NEW_VAL. Return true if the new
520 value is different from VAR's previous value. */
521
522 static bool
set_lattice_value(tree var,ccp_prop_value_t * new_val)523 set_lattice_value (tree var, ccp_prop_value_t *new_val)
524 {
525 /* We can deal with old UNINITIALIZED values just fine here. */
526 ccp_prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
527
528 canonicalize_value (new_val);
529
530 /* We have to be careful to not go up the bitwise lattice
531 represented by the mask. Instead of dropping to VARYING
532 use the meet operator to retain a conservative value.
533 Missed optimizations like PR65851 makes this necessary.
534 It also ensures we converge to a stable lattice solution. */
535 if (old_val->lattice_val != UNINITIALIZED)
536 ccp_lattice_meet (new_val, old_val);
537
538 gcc_checking_assert (valid_lattice_transition (*old_val, *new_val));
539
540 /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
541 caller that this was a non-transition. */
542 if (old_val->lattice_val != new_val->lattice_val
543 || (new_val->lattice_val == CONSTANT
544 && (TREE_CODE (new_val->value) != TREE_CODE (old_val->value)
545 || (TREE_CODE (new_val->value) == INTEGER_CST
546 && (new_val->mask != old_val->mask
547 || (wi::bit_and_not (wi::to_widest (old_val->value),
548 new_val->mask)
549 != wi::bit_and_not (wi::to_widest (new_val->value),
550 new_val->mask))))
551 || (TREE_CODE (new_val->value) != INTEGER_CST
552 && !operand_equal_p (new_val->value, old_val->value, 0)))))
553 {
554 /* ??? We would like to delay creation of INTEGER_CSTs from
555 partially constants here. */
556
557 if (dump_file && (dump_flags & TDF_DETAILS))
558 {
559 dump_lattice_value (dump_file, "Lattice value changed to ", *new_val);
560 fprintf (dump_file, ". Adding SSA edges to worklist.\n");
561 }
562
563 *old_val = *new_val;
564
565 gcc_assert (new_val->lattice_val != UNINITIALIZED);
566 return true;
567 }
568
569 return false;
570 }
571
572 static ccp_prop_value_t get_value_for_expr (tree, bool);
573 static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
574 void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *,
575 signop, int, const widest_int &, const widest_int &,
576 signop, int, const widest_int &, const widest_int &);
577
578 /* Return a widest_int that can be used for bitwise simplifications
579 from VAL. */
580
581 static widest_int
value_to_wide_int(ccp_prop_value_t val)582 value_to_wide_int (ccp_prop_value_t val)
583 {
584 if (val.value
585 && TREE_CODE (val.value) == INTEGER_CST)
586 return wi::to_widest (val.value);
587
588 return 0;
589 }
590
591 /* Return the value for the address expression EXPR based on alignment
592 information. */
593
594 static ccp_prop_value_t
get_value_from_alignment(tree expr)595 get_value_from_alignment (tree expr)
596 {
597 tree type = TREE_TYPE (expr);
598 ccp_prop_value_t val;
599 unsigned HOST_WIDE_INT bitpos;
600 unsigned int align;
601
602 gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
603
604 get_pointer_alignment_1 (expr, &align, &bitpos);
605 val.mask = wi::bit_and_not
606 (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
607 ? wi::mask <widest_int> (TYPE_PRECISION (type), false)
608 : -1,
609 align / BITS_PER_UNIT - 1);
610 val.lattice_val
611 = wi::sext (val.mask, TYPE_PRECISION (type)) == -1 ? VARYING : CONSTANT;
612 if (val.lattice_val == CONSTANT)
613 val.value = build_int_cstu (type, bitpos / BITS_PER_UNIT);
614 else
615 val.value = NULL_TREE;
616
617 return val;
618 }
619
620 /* Return the value for the tree operand EXPR. If FOR_BITS_P is true
621 return constant bits extracted from alignment information for
622 invariant addresses. */
623
624 static ccp_prop_value_t
get_value_for_expr(tree expr,bool for_bits_p)625 get_value_for_expr (tree expr, bool for_bits_p)
626 {
627 ccp_prop_value_t val;
628
629 if (TREE_CODE (expr) == SSA_NAME)
630 {
631 ccp_prop_value_t *val_ = get_value (expr);
632 if (val_)
633 val = *val_;
634 else
635 {
636 val.lattice_val = VARYING;
637 val.value = NULL_TREE;
638 val.mask = -1;
639 }
640 if (for_bits_p
641 && val.lattice_val == CONSTANT)
642 {
643 if (TREE_CODE (val.value) == ADDR_EXPR)
644 val = get_value_from_alignment (val.value);
645 else if (TREE_CODE (val.value) != INTEGER_CST)
646 {
647 val.lattice_val = VARYING;
648 val.value = NULL_TREE;
649 val.mask = -1;
650 }
651 }
652 /* Fall back to a copy value. */
653 if (!for_bits_p
654 && val.lattice_val == VARYING
655 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr))
656 {
657 val.lattice_val = CONSTANT;
658 val.value = expr;
659 val.mask = -1;
660 }
661 }
662 else if (is_gimple_min_invariant (expr)
663 && (!for_bits_p || TREE_CODE (expr) == INTEGER_CST))
664 {
665 val.lattice_val = CONSTANT;
666 val.value = expr;
667 val.mask = 0;
668 canonicalize_value (&val);
669 }
670 else if (TREE_CODE (expr) == ADDR_EXPR)
671 val = get_value_from_alignment (expr);
672 else
673 {
674 val.lattice_val = VARYING;
675 val.mask = -1;
676 val.value = NULL_TREE;
677 }
678
679 if (val.lattice_val == VARYING
680 && TYPE_UNSIGNED (TREE_TYPE (expr)))
681 val.mask = wi::zext (val.mask, TYPE_PRECISION (TREE_TYPE (expr)));
682
683 return val;
684 }
685
686 /* Return the likely CCP lattice value for STMT.
687
688 If STMT has no operands, then return CONSTANT.
689
690 Else if undefinedness of operands of STMT cause its value to be
691 undefined, then return UNDEFINED.
692
693 Else if any operands of STMT are constants, then return CONSTANT.
694
695 Else return VARYING. */
696
697 static ccp_lattice_t
likely_value(gimple * stmt)698 likely_value (gimple *stmt)
699 {
700 bool has_constant_operand, has_undefined_operand, all_undefined_operands;
701 bool has_nsa_operand;
702 tree use;
703 ssa_op_iter iter;
704 unsigned i;
705
706 enum gimple_code code = gimple_code (stmt);
707
708 /* This function appears to be called only for assignments, calls,
709 conditionals, and switches, due to the logic in visit_stmt. */
710 gcc_assert (code == GIMPLE_ASSIGN
711 || code == GIMPLE_CALL
712 || code == GIMPLE_COND
713 || code == GIMPLE_SWITCH);
714
715 /* If the statement has volatile operands, it won't fold to a
716 constant value. */
717 if (gimple_has_volatile_ops (stmt))
718 return VARYING;
719
720 /* Arrive here for more complex cases. */
721 has_constant_operand = false;
722 has_undefined_operand = false;
723 all_undefined_operands = true;
724 has_nsa_operand = false;
725 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
726 {
727 ccp_prop_value_t *val = get_value (use);
728
729 if (val && val->lattice_val == UNDEFINED)
730 has_undefined_operand = true;
731 else
732 all_undefined_operands = false;
733
734 if (val && val->lattice_val == CONSTANT)
735 has_constant_operand = true;
736
737 if (SSA_NAME_IS_DEFAULT_DEF (use)
738 || !prop_simulate_again_p (SSA_NAME_DEF_STMT (use)))
739 has_nsa_operand = true;
740 }
741
742 /* There may be constants in regular rhs operands. For calls we
743 have to ignore lhs, fndecl and static chain, otherwise only
744 the lhs. */
745 for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
746 i < gimple_num_ops (stmt); ++i)
747 {
748 tree op = gimple_op (stmt, i);
749 if (!op || TREE_CODE (op) == SSA_NAME)
750 continue;
751 if (is_gimple_min_invariant (op))
752 has_constant_operand = true;
753 }
754
755 if (has_constant_operand)
756 all_undefined_operands = false;
757
758 if (has_undefined_operand
759 && code == GIMPLE_CALL
760 && gimple_call_internal_p (stmt))
761 switch (gimple_call_internal_fn (stmt))
762 {
763 /* These 3 builtins use the first argument just as a magic
764 way how to find out a decl uid. */
765 case IFN_GOMP_SIMD_LANE:
766 case IFN_GOMP_SIMD_VF:
767 case IFN_GOMP_SIMD_LAST_LANE:
768 has_undefined_operand = false;
769 break;
770 default:
771 break;
772 }
773
774 /* If the operation combines operands like COMPLEX_EXPR make sure to
775 not mark the result UNDEFINED if only one part of the result is
776 undefined. */
777 if (has_undefined_operand && all_undefined_operands)
778 return UNDEFINED;
779 else if (code == GIMPLE_ASSIGN && has_undefined_operand)
780 {
781 switch (gimple_assign_rhs_code (stmt))
782 {
783 /* Unary operators are handled with all_undefined_operands. */
784 case PLUS_EXPR:
785 case MINUS_EXPR:
786 case POINTER_PLUS_EXPR:
787 case BIT_XOR_EXPR:
788 /* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected.
789 Not bitwise operators, one VARYING operand may specify the
790 result completely.
791 Not logical operators for the same reason, apart from XOR.
792 Not COMPLEX_EXPR as one VARYING operand makes the result partly
793 not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because
794 the undefined operand may be promoted. */
795 return UNDEFINED;
796
797 case ADDR_EXPR:
798 /* If any part of an address is UNDEFINED, like the index
799 of an ARRAY_EXPR, then treat the result as UNDEFINED. */
800 return UNDEFINED;
801
802 default:
803 ;
804 }
805 }
806 /* If there was an UNDEFINED operand but the result may be not UNDEFINED
807 fall back to CONSTANT. During iteration UNDEFINED may still drop
808 to CONSTANT. */
809 if (has_undefined_operand)
810 return CONSTANT;
811
812 /* We do not consider virtual operands here -- load from read-only
813 memory may have only VARYING virtual operands, but still be
814 constant. Also we can combine the stmt with definitions from
815 operands whose definitions are not simulated again. */
816 if (has_constant_operand
817 || has_nsa_operand
818 || gimple_references_memory_p (stmt))
819 return CONSTANT;
820
821 return VARYING;
822 }
823
824 /* Returns true if STMT cannot be constant. */
825
826 static bool
surely_varying_stmt_p(gimple * stmt)827 surely_varying_stmt_p (gimple *stmt)
828 {
829 /* If the statement has operands that we cannot handle, it cannot be
830 constant. */
831 if (gimple_has_volatile_ops (stmt))
832 return true;
833
834 /* If it is a call and does not return a value or is not a
835 builtin and not an indirect call or a call to function with
836 assume_aligned/alloc_align attribute, it is varying. */
837 if (is_gimple_call (stmt))
838 {
839 tree fndecl, fntype = gimple_call_fntype (stmt);
840 if (!gimple_call_lhs (stmt)
841 || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
842 && !fndecl_built_in_p (fndecl)
843 && !lookup_attribute ("assume_aligned",
844 TYPE_ATTRIBUTES (fntype))
845 && !lookup_attribute ("alloc_align",
846 TYPE_ATTRIBUTES (fntype))))
847 return true;
848 }
849
850 /* Any other store operation is not interesting. */
851 else if (gimple_vdef (stmt))
852 return true;
853
854 /* Anything other than assignments and conditional jumps are not
855 interesting for CCP. */
856 if (gimple_code (stmt) != GIMPLE_ASSIGN
857 && gimple_code (stmt) != GIMPLE_COND
858 && gimple_code (stmt) != GIMPLE_SWITCH
859 && gimple_code (stmt) != GIMPLE_CALL)
860 return true;
861
862 return false;
863 }
864
865 /* Initialize local data structures for CCP. */
866
867 static void
ccp_initialize(void)868 ccp_initialize (void)
869 {
870 basic_block bb;
871
872 n_const_val = num_ssa_names;
873 const_val = XCNEWVEC (ccp_prop_value_t, n_const_val);
874
875 /* Initialize simulation flags for PHI nodes and statements. */
876 FOR_EACH_BB_FN (bb, cfun)
877 {
878 gimple_stmt_iterator i;
879
880 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
881 {
882 gimple *stmt = gsi_stmt (i);
883 bool is_varying;
884
885 /* If the statement is a control insn, then we do not
886 want to avoid simulating the statement once. Failure
887 to do so means that those edges will never get added. */
888 if (stmt_ends_bb_p (stmt))
889 is_varying = false;
890 else
891 is_varying = surely_varying_stmt_p (stmt);
892
893 if (is_varying)
894 {
895 tree def;
896 ssa_op_iter iter;
897
898 /* If the statement will not produce a constant, mark
899 all its outputs VARYING. */
900 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
901 set_value_varying (def);
902 }
903 prop_set_simulate_again (stmt, !is_varying);
904 }
905 }
906
907 /* Now process PHI nodes. We never clear the simulate_again flag on
908 phi nodes, since we do not know which edges are executable yet,
909 except for phi nodes for virtual operands when we do not do store ccp. */
910 FOR_EACH_BB_FN (bb, cfun)
911 {
912 gphi_iterator i;
913
914 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
915 {
916 gphi *phi = i.phi ();
917
918 if (virtual_operand_p (gimple_phi_result (phi)))
919 prop_set_simulate_again (phi, false);
920 else
921 prop_set_simulate_again (phi, true);
922 }
923 }
924 }
925
926 /* Debug count support. Reset the values of ssa names
927 VARYING when the total number ssa names analyzed is
928 beyond the debug count specified. */
929
930 static void
do_dbg_cnt(void)931 do_dbg_cnt (void)
932 {
933 unsigned i;
934 for (i = 0; i < num_ssa_names; i++)
935 {
936 if (!dbg_cnt (ccp))
937 {
938 const_val[i].lattice_val = VARYING;
939 const_val[i].mask = -1;
940 const_val[i].value = NULL_TREE;
941 }
942 }
943 }
944
945
946 /* We want to provide our own GET_VALUE and FOLD_STMT virtual methods. */
947 class ccp_folder : public substitute_and_fold_engine
948 {
949 public:
950 tree value_of_expr (tree, gimple *) FINAL OVERRIDE;
951 bool fold_stmt (gimple_stmt_iterator *) FINAL OVERRIDE;
952 };
953
954 /* This method just wraps GET_CONSTANT_VALUE for now. Over time
955 naked calls to GET_CONSTANT_VALUE should be eliminated in favor
956 of calling member functions. */
957
958 tree
value_of_expr(tree op,gimple *)959 ccp_folder::value_of_expr (tree op, gimple *)
960 {
961 return get_constant_value (op);
962 }
963
964 /* Do final substitution of propagated values, cleanup the flowgraph and
965 free allocated storage. If NONZERO_P, record nonzero bits.
966
967 Return TRUE when something was optimized. */
968
969 static bool
ccp_finalize(bool nonzero_p)970 ccp_finalize (bool nonzero_p)
971 {
972 bool something_changed;
973 unsigned i;
974 tree name;
975
976 do_dbg_cnt ();
977
978 /* Derive alignment and misalignment information from partially
979 constant pointers in the lattice or nonzero bits from partially
980 constant integers. */
981 FOR_EACH_SSA_NAME (i, name, cfun)
982 {
983 ccp_prop_value_t *val;
984 unsigned int tem, align;
985
986 if (!POINTER_TYPE_P (TREE_TYPE (name))
987 && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
988 /* Don't record nonzero bits before IPA to avoid
989 using too much memory. */
990 || !nonzero_p))
991 continue;
992
993 val = get_value (name);
994 if (val->lattice_val != CONSTANT
995 || TREE_CODE (val->value) != INTEGER_CST
996 || val->mask == 0)
997 continue;
998
999 if (POINTER_TYPE_P (TREE_TYPE (name)))
1000 {
1001 /* Trailing mask bits specify the alignment, trailing value
1002 bits the misalignment. */
1003 tem = val->mask.to_uhwi ();
1004 align = least_bit_hwi (tem);
1005 if (align > 1)
1006 set_ptr_info_alignment (get_ptr_info (name), align,
1007 (TREE_INT_CST_LOW (val->value)
1008 & (align - 1)));
1009 }
1010 else
1011 {
1012 unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
1013 wide_int nonzero_bits
1014 = (wide_int::from (val->mask, precision, UNSIGNED)
1015 | wi::to_wide (val->value));
1016 nonzero_bits &= get_nonzero_bits (name);
1017 set_nonzero_bits (name, nonzero_bits);
1018 }
1019 }
1020
1021 /* Perform substitutions based on the known constant values. */
1022 class ccp_folder ccp_folder;
1023 something_changed = ccp_folder.substitute_and_fold ();
1024
1025 free (const_val);
1026 const_val = NULL;
1027 return something_changed;
1028 }
1029
1030
1031 /* Compute the meet operator between *VAL1 and *VAL2. Store the result
1032 in VAL1.
1033
1034 any M UNDEFINED = any
1035 any M VARYING = VARYING
1036 Ci M Cj = Ci if (i == j)
1037 Ci M Cj = VARYING if (i != j)
1038 */
1039
1040 static void
ccp_lattice_meet(ccp_prop_value_t * val1,ccp_prop_value_t * val2)1041 ccp_lattice_meet (ccp_prop_value_t *val1, ccp_prop_value_t *val2)
1042 {
1043 if (val1->lattice_val == UNDEFINED
1044 /* For UNDEFINED M SSA we can't always SSA because its definition
1045 may not dominate the PHI node. Doing optimistic copy propagation
1046 also causes a lot of gcc.dg/uninit-pred*.c FAILs. */
1047 && (val2->lattice_val != CONSTANT
1048 || TREE_CODE (val2->value) != SSA_NAME))
1049 {
1050 /* UNDEFINED M any = any */
1051 *val1 = *val2;
1052 }
1053 else if (val2->lattice_val == UNDEFINED
1054 /* See above. */
1055 && (val1->lattice_val != CONSTANT
1056 || TREE_CODE (val1->value) != SSA_NAME))
1057 {
1058 /* any M UNDEFINED = any
1059 Nothing to do. VAL1 already contains the value we want. */
1060 ;
1061 }
1062 else if (val1->lattice_val == VARYING
1063 || val2->lattice_val == VARYING)
1064 {
1065 /* any M VARYING = VARYING. */
1066 val1->lattice_val = VARYING;
1067 val1->mask = -1;
1068 val1->value = NULL_TREE;
1069 }
1070 else if (val1->lattice_val == CONSTANT
1071 && val2->lattice_val == CONSTANT
1072 && TREE_CODE (val1->value) == INTEGER_CST
1073 && TREE_CODE (val2->value) == INTEGER_CST)
1074 {
1075 /* Ci M Cj = Ci if (i == j)
1076 Ci M Cj = VARYING if (i != j)
1077
1078 For INTEGER_CSTs mask unequal bits. If no equal bits remain,
1079 drop to varying. */
1080 val1->mask = (val1->mask | val2->mask
1081 | (wi::to_widest (val1->value)
1082 ^ wi::to_widest (val2->value)));
1083 if (wi::sext (val1->mask, TYPE_PRECISION (TREE_TYPE (val1->value))) == -1)
1084 {
1085 val1->lattice_val = VARYING;
1086 val1->value = NULL_TREE;
1087 }
1088 }
1089 else if (val1->lattice_val == CONSTANT
1090 && val2->lattice_val == CONSTANT
1091 && operand_equal_p (val1->value, val2->value, 0))
1092 {
1093 /* Ci M Cj = Ci if (i == j)
1094 Ci M Cj = VARYING if (i != j)
1095
1096 VAL1 already contains the value we want for equivalent values. */
1097 }
1098 else if (val1->lattice_val == CONSTANT
1099 && val2->lattice_val == CONSTANT
1100 && (TREE_CODE (val1->value) == ADDR_EXPR
1101 || TREE_CODE (val2->value) == ADDR_EXPR))
1102 {
1103 /* When not equal addresses are involved try meeting for
1104 alignment. */
1105 ccp_prop_value_t tem = *val2;
1106 if (TREE_CODE (val1->value) == ADDR_EXPR)
1107 *val1 = get_value_for_expr (val1->value, true);
1108 if (TREE_CODE (val2->value) == ADDR_EXPR)
1109 tem = get_value_for_expr (val2->value, true);
1110 ccp_lattice_meet (val1, &tem);
1111 }
1112 else
1113 {
1114 /* Any other combination is VARYING. */
1115 val1->lattice_val = VARYING;
1116 val1->mask = -1;
1117 val1->value = NULL_TREE;
1118 }
1119 }
1120
1121
1122 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
1123 lattice values to determine PHI_NODE's lattice value. The value of a
1124 PHI node is determined calling ccp_lattice_meet with all the arguments
1125 of the PHI node that are incoming via executable edges. */
1126
1127 enum ssa_prop_result
visit_phi(gphi * phi)1128 ccp_propagate::visit_phi (gphi *phi)
1129 {
1130 unsigned i;
1131 ccp_prop_value_t new_val;
1132
1133 if (dump_file && (dump_flags & TDF_DETAILS))
1134 {
1135 fprintf (dump_file, "\nVisiting PHI node: ");
1136 print_gimple_stmt (dump_file, phi, 0, dump_flags);
1137 }
1138
1139 new_val.lattice_val = UNDEFINED;
1140 new_val.value = NULL_TREE;
1141 new_val.mask = 0;
1142
1143 bool first = true;
1144 bool non_exec_edge = false;
1145 for (i = 0; i < gimple_phi_num_args (phi); i++)
1146 {
1147 /* Compute the meet operator over all the PHI arguments flowing
1148 through executable edges. */
1149 edge e = gimple_phi_arg_edge (phi, i);
1150
1151 if (dump_file && (dump_flags & TDF_DETAILS))
1152 {
1153 fprintf (dump_file,
1154 "\tArgument #%d (%d -> %d %sexecutable)\n",
1155 i, e->src->index, e->dest->index,
1156 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
1157 }
1158
1159 /* If the incoming edge is executable, Compute the meet operator for
1160 the existing value of the PHI node and the current PHI argument. */
1161 if (e->flags & EDGE_EXECUTABLE)
1162 {
1163 tree arg = gimple_phi_arg (phi, i)->def;
1164 ccp_prop_value_t arg_val = get_value_for_expr (arg, false);
1165
1166 if (first)
1167 {
1168 new_val = arg_val;
1169 first = false;
1170 }
1171 else
1172 ccp_lattice_meet (&new_val, &arg_val);
1173
1174 if (dump_file && (dump_flags & TDF_DETAILS))
1175 {
1176 fprintf (dump_file, "\t");
1177 print_generic_expr (dump_file, arg, dump_flags);
1178 dump_lattice_value (dump_file, "\tValue: ", arg_val);
1179 fprintf (dump_file, "\n");
1180 }
1181
1182 if (new_val.lattice_val == VARYING)
1183 break;
1184 }
1185 else
1186 non_exec_edge = true;
1187 }
1188
1189 /* In case there were non-executable edges and the value is a copy
1190 make sure its definition dominates the PHI node. */
1191 if (non_exec_edge
1192 && new_val.lattice_val == CONSTANT
1193 && TREE_CODE (new_val.value) == SSA_NAME
1194 && ! SSA_NAME_IS_DEFAULT_DEF (new_val.value)
1195 && ! dominated_by_p (CDI_DOMINATORS, gimple_bb (phi),
1196 gimple_bb (SSA_NAME_DEF_STMT (new_val.value))))
1197 {
1198 new_val.lattice_val = VARYING;
1199 new_val.value = NULL_TREE;
1200 new_val.mask = -1;
1201 }
1202
1203 if (dump_file && (dump_flags & TDF_DETAILS))
1204 {
1205 dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
1206 fprintf (dump_file, "\n\n");
1207 }
1208
1209 /* Make the transition to the new value. */
1210 if (set_lattice_value (gimple_phi_result (phi), &new_val))
1211 {
1212 if (new_val.lattice_val == VARYING)
1213 return SSA_PROP_VARYING;
1214 else
1215 return SSA_PROP_INTERESTING;
1216 }
1217 else
1218 return SSA_PROP_NOT_INTERESTING;
1219 }
1220
1221 /* Return the constant value for OP or OP otherwise. */
1222
1223 static tree
valueize_op(tree op)1224 valueize_op (tree op)
1225 {
1226 if (TREE_CODE (op) == SSA_NAME)
1227 {
1228 tree tem = get_constant_value (op);
1229 if (tem)
1230 return tem;
1231 }
1232 return op;
1233 }
1234
1235 /* Return the constant value for OP, but signal to not follow SSA
1236 edges if the definition may be simulated again. */
1237
1238 static tree
valueize_op_1(tree op)1239 valueize_op_1 (tree op)
1240 {
1241 if (TREE_CODE (op) == SSA_NAME)
1242 {
1243 /* If the definition may be simulated again we cannot follow
1244 this SSA edge as the SSA propagator does not necessarily
1245 re-visit the use. */
1246 gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1247 if (!gimple_nop_p (def_stmt)
1248 && prop_simulate_again_p (def_stmt))
1249 return NULL_TREE;
1250 tree tem = get_constant_value (op);
1251 if (tem)
1252 return tem;
1253 }
1254 return op;
1255 }
1256
1257 /* CCP specific front-end to the non-destructive constant folding
1258 routines.
1259
1260 Attempt to simplify the RHS of STMT knowing that one or more
1261 operands are constants.
1262
1263 If simplification is possible, return the simplified RHS,
1264 otherwise return the original RHS or NULL_TREE. */
1265
1266 static tree
ccp_fold(gimple * stmt)1267 ccp_fold (gimple *stmt)
1268 {
1269 location_t loc = gimple_location (stmt);
1270 switch (gimple_code (stmt))
1271 {
1272 case GIMPLE_COND:
1273 {
1274 /* Handle comparison operators that can appear in GIMPLE form. */
1275 tree op0 = valueize_op (gimple_cond_lhs (stmt));
1276 tree op1 = valueize_op (gimple_cond_rhs (stmt));
1277 enum tree_code code = gimple_cond_code (stmt);
1278 return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
1279 }
1280
1281 case GIMPLE_SWITCH:
1282 {
1283 /* Return the constant switch index. */
1284 return valueize_op (gimple_switch_index (as_a <gswitch *> (stmt)));
1285 }
1286
1287 case GIMPLE_ASSIGN:
1288 case GIMPLE_CALL:
1289 return gimple_fold_stmt_to_constant_1 (stmt,
1290 valueize_op, valueize_op_1);
1291
1292 default:
1293 gcc_unreachable ();
1294 }
1295 }
1296
1297 /* Determine the minimum and maximum values, *MIN and *MAX respectively,
1298 represented by the mask pair VAL and MASK with signedness SGN and
1299 precision PRECISION. */
1300
1301 void
value_mask_to_min_max(widest_int * min,widest_int * max,const widest_int & val,const widest_int & mask,signop sgn,int precision)1302 value_mask_to_min_max (widest_int *min, widest_int *max,
1303 const widest_int &val, const widest_int &mask,
1304 signop sgn, int precision)
1305 {
1306 *min = wi::bit_and_not (val, mask);
1307 *max = val | mask;
1308 if (sgn == SIGNED && wi::neg_p (mask))
1309 {
1310 widest_int sign_bit = wi::lshift (1, precision - 1);
1311 *min ^= sign_bit;
1312 *max ^= sign_bit;
1313 /* MAX is zero extended, and MIN is sign extended. */
1314 *min = wi::ext (*min, precision, sgn);
1315 *max = wi::ext (*max, precision, sgn);
1316 }
1317 }
1318
1319 /* Apply the operation CODE in type TYPE to the value, mask pair
1320 RVAL and RMASK representing a value of type RTYPE and set
1321 the value, mask pair *VAL and *MASK to the result. */
1322
1323 void
bit_value_unop(enum tree_code code,signop type_sgn,int type_precision,widest_int * val,widest_int * mask,signop rtype_sgn,int rtype_precision,const widest_int & rval,const widest_int & rmask)1324 bit_value_unop (enum tree_code code, signop type_sgn, int type_precision,
1325 widest_int *val, widest_int *mask,
1326 signop rtype_sgn, int rtype_precision,
1327 const widest_int &rval, const widest_int &rmask)
1328 {
1329 switch (code)
1330 {
1331 case BIT_NOT_EXPR:
1332 *mask = rmask;
1333 *val = ~rval;
1334 break;
1335
1336 case NEGATE_EXPR:
1337 {
1338 widest_int temv, temm;
1339 /* Return ~rval + 1. */
1340 bit_value_unop (BIT_NOT_EXPR, type_sgn, type_precision, &temv, &temm,
1341 type_sgn, type_precision, rval, rmask);
1342 bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask,
1343 type_sgn, type_precision, temv, temm,
1344 type_sgn, type_precision, 1, 0);
1345 break;
1346 }
1347
1348 CASE_CONVERT:
1349 {
1350 /* First extend mask and value according to the original type. */
1351 *mask = wi::ext (rmask, rtype_precision, rtype_sgn);
1352 *val = wi::ext (rval, rtype_precision, rtype_sgn);
1353
1354 /* Then extend mask and value according to the target type. */
1355 *mask = wi::ext (*mask, type_precision, type_sgn);
1356 *val = wi::ext (*val, type_precision, type_sgn);
1357 break;
1358 }
1359
1360 case ABS_EXPR:
1361 case ABSU_EXPR:
1362 if (wi::sext (rmask, rtype_precision) == -1)
1363 *mask = -1;
1364 else if (wi::neg_p (rmask))
1365 {
1366 /* Result is either rval or -rval. */
1367 widest_int temv, temm;
1368 bit_value_unop (NEGATE_EXPR, rtype_sgn, rtype_precision, &temv,
1369 &temm, type_sgn, type_precision, rval, rmask);
1370 temm |= (rmask | (rval ^ temv));
1371 /* Extend the result. */
1372 *mask = wi::ext (temm, type_precision, type_sgn);
1373 *val = wi::ext (temv, type_precision, type_sgn);
1374 }
1375 else if (wi::neg_p (rval))
1376 {
1377 bit_value_unop (NEGATE_EXPR, type_sgn, type_precision, val, mask,
1378 type_sgn, type_precision, rval, rmask);
1379 }
1380 else
1381 {
1382 *mask = rmask;
1383 *val = rval;
1384 }
1385 break;
1386
1387 default:
1388 *mask = -1;
1389 break;
1390 }
1391 }
1392
1393 /* Determine the mask pair *VAL and *MASK from multiplying the
1394 argument mask pair RVAL, RMASK by the unsigned constant C. */
1395 void
bit_value_mult_const(signop sgn,int width,widest_int * val,widest_int * mask,const widest_int & rval,const widest_int & rmask,widest_int c)1396 bit_value_mult_const (signop sgn, int width,
1397 widest_int *val, widest_int *mask,
1398 const widest_int &rval, const widest_int &rmask,
1399 widest_int c)
1400 {
1401 widest_int sum_mask = 0;
1402
1403 /* Ensure rval_lo only contains known bits. */
1404 widest_int rval_lo = wi::bit_and_not (rval, rmask);
1405
1406 if (rval_lo != 0)
1407 {
1408 /* General case (some bits of multiplicand are known set). */
1409 widest_int sum_val = 0;
1410 while (c != 0)
1411 {
1412 /* Determine the lowest bit set in the multiplier. */
1413 int bitpos = wi::ctz (c);
1414 widest_int term_mask = rmask << bitpos;
1415 widest_int term_val = rval_lo << bitpos;
1416
1417 /* sum += term. */
1418 widest_int lo = sum_val + term_val;
1419 widest_int hi = (sum_val | sum_mask) + (term_val | term_mask);
1420 sum_mask |= term_mask | (lo ^ hi);
1421 sum_val = lo;
1422
1423 /* Clear this bit in the multiplier. */
1424 c ^= wi::lshift (1, bitpos);
1425 }
1426 /* Correctly extend the result value. */
1427 *val = wi::ext (sum_val, width, sgn);
1428 }
1429 else
1430 {
1431 /* Special case (no bits of multiplicand are known set). */
1432 while (c != 0)
1433 {
1434 /* Determine the lowest bit set in the multiplier. */
1435 int bitpos = wi::ctz (c);
1436 widest_int term_mask = rmask << bitpos;
1437
1438 /* sum += term. */
1439 widest_int hi = sum_mask + term_mask;
1440 sum_mask |= term_mask | hi;
1441
1442 /* Clear this bit in the multiplier. */
1443 c ^= wi::lshift (1, bitpos);
1444 }
1445 *val = 0;
1446 }
1447
1448 /* Correctly extend the result mask. */
1449 *mask = wi::ext (sum_mask, width, sgn);
1450 }
1451
1452 /* Fill up to MAX values in the BITS array with values representing
1453 each of the non-zero bits in the value X. Returns the number of
1454 bits in X (capped at the maximum value MAX). For example, an X
1455 value 11, places 1, 2 and 8 in BITS and returns the value 3. */
1456
1457 unsigned int
get_individual_bits(widest_int * bits,widest_int x,unsigned int max)1458 get_individual_bits (widest_int *bits, widest_int x, unsigned int max)
1459 {
1460 unsigned int count = 0;
1461 while (count < max && x != 0)
1462 {
1463 int bitpos = wi::ctz (x);
1464 bits[count] = wi::lshift (1, bitpos);
1465 x ^= bits[count];
1466 count++;
1467 }
1468 return count;
1469 }
1470
1471 /* Array of 2^N - 1 values representing the bits flipped between
1472 consecutive Gray codes. This is used to efficiently enumerate
1473 all permutations on N bits using XOR. */
1474 static const unsigned char gray_code_bit_flips[63] = {
1475 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1476 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
1477 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1478 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
1479 };
1480
1481 /* Apply the operation CODE in type TYPE to the value, mask pairs
1482 R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1483 and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */
1484
1485 void
bit_value_binop(enum tree_code code,signop sgn,int width,widest_int * val,widest_int * mask,signop r1type_sgn,int r1type_precision,const widest_int & r1val,const widest_int & r1mask,signop r2type_sgn,int r2type_precision ATTRIBUTE_UNUSED,const widest_int & r2val,const widest_int & r2mask)1486 bit_value_binop (enum tree_code code, signop sgn, int width,
1487 widest_int *val, widest_int *mask,
1488 signop r1type_sgn, int r1type_precision,
1489 const widest_int &r1val, const widest_int &r1mask,
1490 signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED,
1491 const widest_int &r2val, const widest_int &r2mask)
1492 {
1493 bool swap_p = false;
1494
1495 /* Assume we'll get a constant result. Use an initial non varying
1496 value, we fall back to varying in the end if necessary. */
1497 *mask = -1;
1498 /* Ensure that VAL is initialized (to any value). */
1499 *val = 0;
1500
1501 switch (code)
1502 {
1503 case BIT_AND_EXPR:
1504 /* The mask is constant where there is a known not
1505 set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1506 *mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask);
1507 *val = r1val & r2val;
1508 break;
1509
1510 case BIT_IOR_EXPR:
1511 /* The mask is constant where there is a known
1512 set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */
1513 *mask = wi::bit_and_not (r1mask | r2mask,
1514 wi::bit_and_not (r1val, r1mask)
1515 | wi::bit_and_not (r2val, r2mask));
1516 *val = r1val | r2val;
1517 break;
1518
1519 case BIT_XOR_EXPR:
1520 /* m1 | m2 */
1521 *mask = r1mask | r2mask;
1522 *val = r1val ^ r2val;
1523 break;
1524
1525 case LROTATE_EXPR:
1526 case RROTATE_EXPR:
1527 if (r2mask == 0)
1528 {
1529 widest_int shift = r2val;
1530 if (shift == 0)
1531 {
1532 *mask = r1mask;
1533 *val = r1val;
1534 }
1535 else
1536 {
1537 if (wi::neg_p (shift, r2type_sgn))
1538 {
1539 shift = -shift;
1540 if (code == RROTATE_EXPR)
1541 code = LROTATE_EXPR;
1542 else
1543 code = RROTATE_EXPR;
1544 }
1545 if (code == RROTATE_EXPR)
1546 {
1547 *mask = wi::rrotate (r1mask, shift, width);
1548 *val = wi::rrotate (r1val, shift, width);
1549 }
1550 else
1551 {
1552 *mask = wi::lrotate (r1mask, shift, width);
1553 *val = wi::lrotate (r1val, shift, width);
1554 }
1555 *mask = wi::ext (*mask, width, sgn);
1556 *val = wi::ext (*val, width, sgn);
1557 }
1558 }
1559 else if (wi::ltu_p (r2val | r2mask, width)
1560 && wi::popcount (r2mask) <= 4)
1561 {
1562 widest_int bits[4];
1563 widest_int res_val, res_mask;
1564 widest_int tmp_val, tmp_mask;
1565 widest_int shift = wi::bit_and_not (r2val, r2mask);
1566 unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1567 unsigned int count = (1 << bit_count) - 1;
1568
1569 /* Initialize result to rotate by smallest value of shift. */
1570 if (code == RROTATE_EXPR)
1571 {
1572 res_mask = wi::rrotate (r1mask, shift, width);
1573 res_val = wi::rrotate (r1val, shift, width);
1574 }
1575 else
1576 {
1577 res_mask = wi::lrotate (r1mask, shift, width);
1578 res_val = wi::lrotate (r1val, shift, width);
1579 }
1580
1581 /* Iterate through the remaining values of shift. */
1582 for (unsigned int i=0; i<count; i++)
1583 {
1584 shift ^= bits[gray_code_bit_flips[i]];
1585 if (code == RROTATE_EXPR)
1586 {
1587 tmp_mask = wi::rrotate (r1mask, shift, width);
1588 tmp_val = wi::rrotate (r1val, shift, width);
1589 }
1590 else
1591 {
1592 tmp_mask = wi::lrotate (r1mask, shift, width);
1593 tmp_val = wi::lrotate (r1val, shift, width);
1594 }
1595 /* Accumulate the result. */
1596 res_mask |= tmp_mask | (res_val ^ tmp_val);
1597 }
1598 *val = wi::ext (wi::bit_and_not (res_val, res_mask), width, sgn);
1599 *mask = wi::ext (res_mask, width, sgn);
1600 }
1601 break;
1602
1603 case LSHIFT_EXPR:
1604 case RSHIFT_EXPR:
1605 /* ??? We can handle partially known shift counts if we know
1606 its sign. That way we can tell that (x << (y | 8)) & 255
1607 is zero. */
1608 if (r2mask == 0)
1609 {
1610 widest_int shift = r2val;
1611 if (shift == 0)
1612 {
1613 *mask = r1mask;
1614 *val = r1val;
1615 }
1616 else
1617 {
1618 if (wi::neg_p (shift, r2type_sgn))
1619 break;
1620 if (code == RSHIFT_EXPR)
1621 {
1622 *mask = wi::rshift (wi::ext (r1mask, width, sgn), shift, sgn);
1623 *val = wi::rshift (wi::ext (r1val, width, sgn), shift, sgn);
1624 }
1625 else
1626 {
1627 *mask = wi::ext (r1mask << shift, width, sgn);
1628 *val = wi::ext (r1val << shift, width, sgn);
1629 }
1630 }
1631 }
1632 else if (wi::ltu_p (r2val | r2mask, width))
1633 {
1634 if (wi::popcount (r2mask) <= 4)
1635 {
1636 widest_int bits[4];
1637 widest_int arg_val, arg_mask;
1638 widest_int res_val, res_mask;
1639 widest_int tmp_val, tmp_mask;
1640 widest_int shift = wi::bit_and_not (r2val, r2mask);
1641 unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1642 unsigned int count = (1 << bit_count) - 1;
1643
1644 /* Initialize result to shift by smallest value of shift. */
1645 if (code == RSHIFT_EXPR)
1646 {
1647 arg_mask = wi::ext (r1mask, width, sgn);
1648 arg_val = wi::ext (r1val, width, sgn);
1649 res_mask = wi::rshift (arg_mask, shift, sgn);
1650 res_val = wi::rshift (arg_val, shift, sgn);
1651 }
1652 else
1653 {
1654 arg_mask = r1mask;
1655 arg_val = r1val;
1656 res_mask = arg_mask << shift;
1657 res_val = arg_val << shift;
1658 }
1659
1660 /* Iterate through the remaining values of shift. */
1661 for (unsigned int i=0; i<count; i++)
1662 {
1663 shift ^= bits[gray_code_bit_flips[i]];
1664 if (code == RSHIFT_EXPR)
1665 {
1666 tmp_mask = wi::rshift (arg_mask, shift, sgn);
1667 tmp_val = wi::rshift (arg_val, shift, sgn);
1668 }
1669 else
1670 {
1671 tmp_mask = arg_mask << shift;
1672 tmp_val = arg_val << shift;
1673 }
1674 /* Accumulate the result. */
1675 res_mask |= tmp_mask | (res_val ^ tmp_val);
1676 }
1677 res_mask = wi::ext (res_mask, width, sgn);
1678 res_val = wi::ext (res_val, width, sgn);
1679 *val = wi::bit_and_not (res_val, res_mask);
1680 *mask = res_mask;
1681 }
1682 else if ((r1val | r1mask) == 0)
1683 {
1684 /* Handle shifts of zero to avoid undefined wi::ctz below. */
1685 *mask = 0;
1686 *val = 0;
1687 }
1688 else if (code == LSHIFT_EXPR)
1689 {
1690 widest_int tmp = wi::mask <widest_int> (width, false);
1691 tmp <<= wi::ctz (r1val | r1mask);
1692 tmp <<= wi::bit_and_not (r2val, r2mask);
1693 *mask = wi::ext (tmp, width, sgn);
1694 *val = 0;
1695 }
1696 else if (!wi::neg_p (r1val | r1mask, sgn))
1697 {
1698 /* Logical right shift, or zero sign bit. */
1699 widest_int arg = r1val | r1mask;
1700 int lzcount = wi::clz (arg);
1701 if (lzcount)
1702 lzcount -= wi::get_precision (arg) - width;
1703 widest_int tmp = wi::mask <widest_int> (width, false);
1704 tmp = wi::lrshift (tmp, lzcount);
1705 tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1706 *mask = wi::ext (tmp, width, sgn);
1707 *val = 0;
1708 }
1709 else if (!wi::neg_p (r1mask))
1710 {
1711 /* Arithmetic right shift with set sign bit. */
1712 widest_int arg = wi::bit_and_not (r1val, r1mask);
1713 int sbcount = wi::clrsb (arg);
1714 sbcount -= wi::get_precision (arg) - width;
1715 widest_int tmp = wi::mask <widest_int> (width, false);
1716 tmp = wi::lrshift (tmp, sbcount);
1717 tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1718 *mask = wi::sext (tmp, width);
1719 tmp = wi::bit_not (tmp);
1720 *val = wi::sext (tmp, width);
1721 }
1722 }
1723 break;
1724
1725 case PLUS_EXPR:
1726 case POINTER_PLUS_EXPR:
1727 {
1728 /* Do the addition with unknown bits set to zero, to give carry-ins of
1729 zero wherever possible. */
1730 widest_int lo = (wi::bit_and_not (r1val, r1mask)
1731 + wi::bit_and_not (r2val, r2mask));
1732 lo = wi::ext (lo, width, sgn);
1733 /* Do the addition with unknown bits set to one, to give carry-ins of
1734 one wherever possible. */
1735 widest_int hi = (r1val | r1mask) + (r2val | r2mask);
1736 hi = wi::ext (hi, width, sgn);
1737 /* Each bit in the result is known if (a) the corresponding bits in
1738 both inputs are known, and (b) the carry-in to that bit position
1739 is known. We can check condition (b) by seeing if we got the same
1740 result with minimised carries as with maximised carries. */
1741 *mask = r1mask | r2mask | (lo ^ hi);
1742 *mask = wi::ext (*mask, width, sgn);
1743 /* It shouldn't matter whether we choose lo or hi here. */
1744 *val = lo;
1745 break;
1746 }
1747
1748 case MINUS_EXPR:
1749 case POINTER_DIFF_EXPR:
1750 {
1751 /* Subtraction is derived from the addition algorithm above. */
1752 widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask);
1753 lo = wi::ext (lo, width, sgn);
1754 widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask);
1755 hi = wi::ext (hi, width, sgn);
1756 *mask = r1mask | r2mask | (lo ^ hi);
1757 *mask = wi::ext (*mask, width, sgn);
1758 *val = lo;
1759 break;
1760 }
1761
1762 case MULT_EXPR:
1763 if (r2mask == 0
1764 && !wi::neg_p (r2val, sgn)
1765 && (flag_expensive_optimizations || wi::popcount (r2val) < 8))
1766 bit_value_mult_const (sgn, width, val, mask, r1val, r1mask, r2val);
1767 else if (r1mask == 0
1768 && !wi::neg_p (r1val, sgn)
1769 && (flag_expensive_optimizations || wi::popcount (r1val) < 8))
1770 bit_value_mult_const (sgn, width, val, mask, r2val, r2mask, r1val);
1771 else
1772 {
1773 /* Just track trailing zeros in both operands and transfer
1774 them to the other. */
1775 int r1tz = wi::ctz (r1val | r1mask);
1776 int r2tz = wi::ctz (r2val | r2mask);
1777 if (r1tz + r2tz >= width)
1778 {
1779 *mask = 0;
1780 *val = 0;
1781 }
1782 else if (r1tz + r2tz > 0)
1783 {
1784 *mask = wi::ext (wi::mask <widest_int> (r1tz + r2tz, true),
1785 width, sgn);
1786 *val = 0;
1787 }
1788 }
1789 break;
1790
1791 case EQ_EXPR:
1792 case NE_EXPR:
1793 {
1794 widest_int m = r1mask | r2mask;
1795 if (wi::bit_and_not (r1val, m) != wi::bit_and_not (r2val, m))
1796 {
1797 *mask = 0;
1798 *val = ((code == EQ_EXPR) ? 0 : 1);
1799 }
1800 else
1801 {
1802 /* We know the result of a comparison is always one or zero. */
1803 *mask = 1;
1804 *val = 0;
1805 }
1806 break;
1807 }
1808
1809 case GE_EXPR:
1810 case GT_EXPR:
1811 swap_p = true;
1812 code = swap_tree_comparison (code);
1813 /* Fall through. */
1814 case LT_EXPR:
1815 case LE_EXPR:
1816 {
1817 widest_int min1, max1, min2, max2;
1818 int minmax, maxmin;
1819
1820 const widest_int &o1val = swap_p ? r2val : r1val;
1821 const widest_int &o1mask = swap_p ? r2mask : r1mask;
1822 const widest_int &o2val = swap_p ? r1val : r2val;
1823 const widest_int &o2mask = swap_p ? r1mask : r2mask;
1824
1825 value_mask_to_min_max (&min1, &max1, o1val, o1mask,
1826 r1type_sgn, r1type_precision);
1827 value_mask_to_min_max (&min2, &max2, o2val, o2mask,
1828 r1type_sgn, r1type_precision);
1829
1830 /* For comparisons the signedness is in the comparison operands. */
1831 /* Do a cross comparison of the max/min pairs. */
1832 maxmin = wi::cmp (max1, min2, r1type_sgn);
1833 minmax = wi::cmp (min1, max2, r1type_sgn);
1834 if (maxmin < (code == LE_EXPR ? 1: 0)) /* o1 < or <= o2. */
1835 {
1836 *mask = 0;
1837 *val = 1;
1838 }
1839 else if (minmax > (code == LT_EXPR ? -1 : 0)) /* o1 >= or > o2. */
1840 {
1841 *mask = 0;
1842 *val = 0;
1843 }
1844 else if (maxmin == minmax) /* o1 and o2 are equal. */
1845 {
1846 /* This probably should never happen as we'd have
1847 folded the thing during fully constant value folding. */
1848 *mask = 0;
1849 *val = (code == LE_EXPR ? 1 : 0);
1850 }
1851 else
1852 {
1853 /* We know the result of a comparison is always one or zero. */
1854 *mask = 1;
1855 *val = 0;
1856 }
1857 break;
1858 }
1859
1860 case MIN_EXPR:
1861 case MAX_EXPR:
1862 {
1863 widest_int min1, max1, min2, max2;
1864
1865 value_mask_to_min_max (&min1, &max1, r1val, r1mask, sgn, width);
1866 value_mask_to_min_max (&min2, &max2, r2val, r2mask, sgn, width);
1867
1868 if (wi::cmp (max1, min2, sgn) <= 0) /* r1 is less than r2. */
1869 {
1870 if (code == MIN_EXPR)
1871 {
1872 *mask = r1mask;
1873 *val = r1val;
1874 }
1875 else
1876 {
1877 *mask = r2mask;
1878 *val = r2val;
1879 }
1880 }
1881 else if (wi::cmp (min1, max2, sgn) >= 0) /* r2 is less than r1. */
1882 {
1883 if (code == MIN_EXPR)
1884 {
1885 *mask = r2mask;
1886 *val = r2val;
1887 }
1888 else
1889 {
1890 *mask = r1mask;
1891 *val = r1val;
1892 }
1893 }
1894 else
1895 {
1896 /* The result is either r1 or r2. */
1897 *mask = r1mask | r2mask | (r1val ^ r2val);
1898 *val = r1val;
1899 }
1900 break;
1901 }
1902
1903 case TRUNC_MOD_EXPR:
1904 {
1905 widest_int r1max = r1val | r1mask;
1906 widest_int r2max = r2val | r2mask;
1907 if (sgn == UNSIGNED
1908 || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1909 {
1910 /* Confirm R2 has some bits set, to avoid division by zero. */
1911 widest_int r2min = wi::bit_and_not (r2val, r2mask);
1912 if (r2min != 0)
1913 {
1914 /* R1 % R2 is R1 if R1 is always less than R2. */
1915 if (wi::ltu_p (r1max, r2min))
1916 {
1917 *mask = r1mask;
1918 *val = r1val;
1919 }
1920 else
1921 {
1922 /* R1 % R2 is always less than the maximum of R2. */
1923 unsigned int lzcount = wi::clz (r2max);
1924 unsigned int bits = wi::get_precision (r2max) - lzcount;
1925 if (r2max == wi::lshift (1, bits))
1926 bits--;
1927 *mask = wi::mask <widest_int> (bits, false);
1928 *val = 0;
1929 }
1930 }
1931 }
1932 }
1933 break;
1934
1935 case TRUNC_DIV_EXPR:
1936 {
1937 widest_int r1max = r1val | r1mask;
1938 widest_int r2max = r2val | r2mask;
1939 if (sgn == UNSIGNED
1940 || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1941 {
1942 /* Confirm R2 has some bits set, to avoid division by zero. */
1943 widest_int r2min = wi::bit_and_not (r2val, r2mask);
1944 if (r2min != 0)
1945 {
1946 /* R1 / R2 is zero if R1 is always less than R2. */
1947 if (wi::ltu_p (r1max, r2min))
1948 {
1949 *mask = 0;
1950 *val = 0;
1951 }
1952 else
1953 {
1954 widest_int upper = wi::udiv_trunc (r1max, r2min);
1955 unsigned int lzcount = wi::clz (upper);
1956 unsigned int bits = wi::get_precision (upper) - lzcount;
1957 *mask = wi::mask <widest_int> (bits, false);
1958 *val = 0;
1959 }
1960 }
1961 }
1962 }
1963 break;
1964
1965 default:;
1966 }
1967 }
1968
1969 /* Return the propagation value when applying the operation CODE to
1970 the value RHS yielding type TYPE. */
1971
1972 static ccp_prop_value_t
bit_value_unop(enum tree_code code,tree type,tree rhs)1973 bit_value_unop (enum tree_code code, tree type, tree rhs)
1974 {
1975 ccp_prop_value_t rval = get_value_for_expr (rhs, true);
1976 widest_int value, mask;
1977 ccp_prop_value_t val;
1978
1979 if (rval.lattice_val == UNDEFINED)
1980 return rval;
1981
1982 gcc_assert ((rval.lattice_val == CONSTANT
1983 && TREE_CODE (rval.value) == INTEGER_CST)
1984 || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1);
1985 bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
1986 TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)),
1987 value_to_wide_int (rval), rval.mask);
1988 if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
1989 {
1990 val.lattice_val = CONSTANT;
1991 val.mask = mask;
1992 /* ??? Delay building trees here. */
1993 val.value = wide_int_to_tree (type, value);
1994 }
1995 else
1996 {
1997 val.lattice_val = VARYING;
1998 val.value = NULL_TREE;
1999 val.mask = -1;
2000 }
2001 return val;
2002 }
2003
2004 /* Return the propagation value when applying the operation CODE to
2005 the values RHS1 and RHS2 yielding type TYPE. */
2006
2007 static ccp_prop_value_t
bit_value_binop(enum tree_code code,tree type,tree rhs1,tree rhs2)2008 bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
2009 {
2010 ccp_prop_value_t r1val = get_value_for_expr (rhs1, true);
2011 ccp_prop_value_t r2val = get_value_for_expr (rhs2, true);
2012 widest_int value, mask;
2013 ccp_prop_value_t val;
2014
2015 if (r1val.lattice_val == UNDEFINED
2016 || r2val.lattice_val == UNDEFINED)
2017 {
2018 val.lattice_val = VARYING;
2019 val.value = NULL_TREE;
2020 val.mask = -1;
2021 return val;
2022 }
2023
2024 gcc_assert ((r1val.lattice_val == CONSTANT
2025 && TREE_CODE (r1val.value) == INTEGER_CST)
2026 || wi::sext (r1val.mask,
2027 TYPE_PRECISION (TREE_TYPE (rhs1))) == -1);
2028 gcc_assert ((r2val.lattice_val == CONSTANT
2029 && TREE_CODE (r2val.value) == INTEGER_CST)
2030 || wi::sext (r2val.mask,
2031 TYPE_PRECISION (TREE_TYPE (rhs2))) == -1);
2032 bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2033 TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)),
2034 value_to_wide_int (r1val), r1val.mask,
2035 TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)),
2036 value_to_wide_int (r2val), r2val.mask);
2037
2038 /* (x * x) & 2 == 0. */
2039 if (code == MULT_EXPR && rhs1 == rhs2 && TYPE_PRECISION (type) > 1)
2040 {
2041 widest_int m = 2;
2042 if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2043 value = wi::bit_and_not (value, m);
2044 else
2045 value = 0;
2046 mask = wi::bit_and_not (mask, m);
2047 }
2048
2049 if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2050 {
2051 val.lattice_val = CONSTANT;
2052 val.mask = mask;
2053 /* ??? Delay building trees here. */
2054 val.value = wide_int_to_tree (type, value);
2055 }
2056 else
2057 {
2058 val.lattice_val = VARYING;
2059 val.value = NULL_TREE;
2060 val.mask = -1;
2061 }
2062 return val;
2063 }
2064
2065 /* Return the propagation value for __builtin_assume_aligned
2066 and functions with assume_aligned or alloc_aligned attribute.
2067 For __builtin_assume_aligned, ATTR is NULL_TREE,
2068 for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED
2069 is false, for alloc_aligned attribute ATTR is non-NULL and
2070 ALLOC_ALIGNED is true. */
2071
2072 static ccp_prop_value_t
bit_value_assume_aligned(gimple * stmt,tree attr,ccp_prop_value_t ptrval,bool alloc_aligned)2073 bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval,
2074 bool alloc_aligned)
2075 {
2076 tree align, misalign = NULL_TREE, type;
2077 unsigned HOST_WIDE_INT aligni, misaligni = 0;
2078 ccp_prop_value_t alignval;
2079 widest_int value, mask;
2080 ccp_prop_value_t val;
2081
2082 if (attr == NULL_TREE)
2083 {
2084 tree ptr = gimple_call_arg (stmt, 0);
2085 type = TREE_TYPE (ptr);
2086 ptrval = get_value_for_expr (ptr, true);
2087 }
2088 else
2089 {
2090 tree lhs = gimple_call_lhs (stmt);
2091 type = TREE_TYPE (lhs);
2092 }
2093
2094 if (ptrval.lattice_val == UNDEFINED)
2095 return ptrval;
2096 gcc_assert ((ptrval.lattice_val == CONSTANT
2097 && TREE_CODE (ptrval.value) == INTEGER_CST)
2098 || wi::sext (ptrval.mask, TYPE_PRECISION (type)) == -1);
2099 if (attr == NULL_TREE)
2100 {
2101 /* Get aligni and misaligni from __builtin_assume_aligned. */
2102 align = gimple_call_arg (stmt, 1);
2103 if (!tree_fits_uhwi_p (align))
2104 return ptrval;
2105 aligni = tree_to_uhwi (align);
2106 if (gimple_call_num_args (stmt) > 2)
2107 {
2108 misalign = gimple_call_arg (stmt, 2);
2109 if (!tree_fits_uhwi_p (misalign))
2110 return ptrval;
2111 misaligni = tree_to_uhwi (misalign);
2112 }
2113 }
2114 else
2115 {
2116 /* Get aligni and misaligni from assume_aligned or
2117 alloc_align attributes. */
2118 if (TREE_VALUE (attr) == NULL_TREE)
2119 return ptrval;
2120 attr = TREE_VALUE (attr);
2121 align = TREE_VALUE (attr);
2122 if (!tree_fits_uhwi_p (align))
2123 return ptrval;
2124 aligni = tree_to_uhwi (align);
2125 if (alloc_aligned)
2126 {
2127 if (aligni == 0 || aligni > gimple_call_num_args (stmt))
2128 return ptrval;
2129 align = gimple_call_arg (stmt, aligni - 1);
2130 if (!tree_fits_uhwi_p (align))
2131 return ptrval;
2132 aligni = tree_to_uhwi (align);
2133 }
2134 else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr)))
2135 {
2136 misalign = TREE_VALUE (TREE_CHAIN (attr));
2137 if (!tree_fits_uhwi_p (misalign))
2138 return ptrval;
2139 misaligni = tree_to_uhwi (misalign);
2140 }
2141 }
2142 if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni)
2143 return ptrval;
2144
2145 align = build_int_cst_type (type, -aligni);
2146 alignval = get_value_for_expr (align, true);
2147 bit_value_binop (BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2148 TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (ptrval), ptrval.mask,
2149 TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (alignval), alignval.mask);
2150
2151 if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2152 {
2153 val.lattice_val = CONSTANT;
2154 val.mask = mask;
2155 gcc_assert ((mask.to_uhwi () & (aligni - 1)) == 0);
2156 gcc_assert ((value.to_uhwi () & (aligni - 1)) == 0);
2157 value |= misaligni;
2158 /* ??? Delay building trees here. */
2159 val.value = wide_int_to_tree (type, value);
2160 }
2161 else
2162 {
2163 val.lattice_val = VARYING;
2164 val.value = NULL_TREE;
2165 val.mask = -1;
2166 }
2167 return val;
2168 }
2169
2170 /* Evaluate statement STMT.
2171 Valid only for assignments, calls, conditionals, and switches. */
2172
2173 static ccp_prop_value_t
evaluate_stmt(gimple * stmt)2174 evaluate_stmt (gimple *stmt)
2175 {
2176 ccp_prop_value_t val;
2177 tree simplified = NULL_TREE;
2178 ccp_lattice_t likelyvalue = likely_value (stmt);
2179 bool is_constant = false;
2180 unsigned int align;
2181 bool ignore_return_flags = false;
2182
2183 if (dump_file && (dump_flags & TDF_DETAILS))
2184 {
2185 fprintf (dump_file, "which is likely ");
2186 switch (likelyvalue)
2187 {
2188 case CONSTANT:
2189 fprintf (dump_file, "CONSTANT");
2190 break;
2191 case UNDEFINED:
2192 fprintf (dump_file, "UNDEFINED");
2193 break;
2194 case VARYING:
2195 fprintf (dump_file, "VARYING");
2196 break;
2197 default:;
2198 }
2199 fprintf (dump_file, "\n");
2200 }
2201
2202 /* If the statement is likely to have a CONSTANT result, then try
2203 to fold the statement to determine the constant value. */
2204 /* FIXME. This is the only place that we call ccp_fold.
2205 Since likely_value never returns CONSTANT for calls, we will
2206 not attempt to fold them, including builtins that may profit. */
2207 if (likelyvalue == CONSTANT)
2208 {
2209 fold_defer_overflow_warnings ();
2210 simplified = ccp_fold (stmt);
2211 if (simplified
2212 && TREE_CODE (simplified) == SSA_NAME)
2213 {
2214 /* We may not use values of something that may be simulated again,
2215 see valueize_op_1. */
2216 if (SSA_NAME_IS_DEFAULT_DEF (simplified)
2217 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (simplified)))
2218 {
2219 ccp_prop_value_t *val = get_value (simplified);
2220 if (val && val->lattice_val != VARYING)
2221 {
2222 fold_undefer_overflow_warnings (true, stmt, 0);
2223 return *val;
2224 }
2225 }
2226 else
2227 /* We may also not place a non-valueized copy in the lattice
2228 as that might become stale if we never re-visit this stmt. */
2229 simplified = NULL_TREE;
2230 }
2231 is_constant = simplified && is_gimple_min_invariant (simplified);
2232 fold_undefer_overflow_warnings (is_constant, stmt, 0);
2233 if (is_constant)
2234 {
2235 /* The statement produced a constant value. */
2236 val.lattice_val = CONSTANT;
2237 val.value = simplified;
2238 val.mask = 0;
2239 return val;
2240 }
2241 }
2242 /* If the statement is likely to have a VARYING result, then do not
2243 bother folding the statement. */
2244 else if (likelyvalue == VARYING)
2245 {
2246 enum gimple_code code = gimple_code (stmt);
2247 if (code == GIMPLE_ASSIGN)
2248 {
2249 enum tree_code subcode = gimple_assign_rhs_code (stmt);
2250
2251 /* Other cases cannot satisfy is_gimple_min_invariant
2252 without folding. */
2253 if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
2254 simplified = gimple_assign_rhs1 (stmt);
2255 }
2256 else if (code == GIMPLE_SWITCH)
2257 simplified = gimple_switch_index (as_a <gswitch *> (stmt));
2258 else
2259 /* These cannot satisfy is_gimple_min_invariant without folding. */
2260 gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
2261 is_constant = simplified && is_gimple_min_invariant (simplified);
2262 if (is_constant)
2263 {
2264 /* The statement produced a constant value. */
2265 val.lattice_val = CONSTANT;
2266 val.value = simplified;
2267 val.mask = 0;
2268 }
2269 }
2270 /* If the statement result is likely UNDEFINED, make it so. */
2271 else if (likelyvalue == UNDEFINED)
2272 {
2273 val.lattice_val = UNDEFINED;
2274 val.value = NULL_TREE;
2275 val.mask = 0;
2276 return val;
2277 }
2278
2279 /* Resort to simplification for bitwise tracking. */
2280 if (flag_tree_bit_ccp
2281 && (likelyvalue == CONSTANT || is_gimple_call (stmt)
2282 || (gimple_assign_single_p (stmt)
2283 && gimple_assign_rhs_code (stmt) == ADDR_EXPR))
2284 && !is_constant)
2285 {
2286 enum gimple_code code = gimple_code (stmt);
2287 val.lattice_val = VARYING;
2288 val.value = NULL_TREE;
2289 val.mask = -1;
2290 if (code == GIMPLE_ASSIGN)
2291 {
2292 enum tree_code subcode = gimple_assign_rhs_code (stmt);
2293 tree rhs1 = gimple_assign_rhs1 (stmt);
2294 tree lhs = gimple_assign_lhs (stmt);
2295 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2296 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2297 && (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2298 || POINTER_TYPE_P (TREE_TYPE (rhs1))))
2299 switch (get_gimple_rhs_class (subcode))
2300 {
2301 case GIMPLE_SINGLE_RHS:
2302 val = get_value_for_expr (rhs1, true);
2303 break;
2304
2305 case GIMPLE_UNARY_RHS:
2306 val = bit_value_unop (subcode, TREE_TYPE (lhs), rhs1);
2307 break;
2308
2309 case GIMPLE_BINARY_RHS:
2310 val = bit_value_binop (subcode, TREE_TYPE (lhs), rhs1,
2311 gimple_assign_rhs2 (stmt));
2312 break;
2313
2314 default:;
2315 }
2316 }
2317 else if (code == GIMPLE_COND)
2318 {
2319 enum tree_code code = gimple_cond_code (stmt);
2320 tree rhs1 = gimple_cond_lhs (stmt);
2321 tree rhs2 = gimple_cond_rhs (stmt);
2322 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2323 || POINTER_TYPE_P (TREE_TYPE (rhs1)))
2324 val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
2325 }
2326 else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2327 {
2328 tree fndecl = gimple_call_fndecl (stmt);
2329 switch (DECL_FUNCTION_CODE (fndecl))
2330 {
2331 case BUILT_IN_MALLOC:
2332 case BUILT_IN_REALLOC:
2333 case BUILT_IN_CALLOC:
2334 case BUILT_IN_STRDUP:
2335 case BUILT_IN_STRNDUP:
2336 val.lattice_val = CONSTANT;
2337 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2338 val.mask = ~((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT
2339 / BITS_PER_UNIT - 1);
2340 break;
2341
2342 CASE_BUILT_IN_ALLOCA:
2343 align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA
2344 ? BIGGEST_ALIGNMENT
2345 : TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2346 val.lattice_val = CONSTANT;
2347 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2348 val.mask = ~((HOST_WIDE_INT) align / BITS_PER_UNIT - 1);
2349 break;
2350
2351 case BUILT_IN_ASSUME_ALIGNED:
2352 val = bit_value_assume_aligned (stmt, NULL_TREE, val, false);
2353 ignore_return_flags = true;
2354 break;
2355
2356 case BUILT_IN_ALIGNED_ALLOC:
2357 case BUILT_IN_GOMP_ALLOC:
2358 {
2359 tree align = get_constant_value (gimple_call_arg (stmt, 0));
2360 if (align
2361 && tree_fits_uhwi_p (align))
2362 {
2363 unsigned HOST_WIDE_INT aligni = tree_to_uhwi (align);
2364 if (aligni > 1
2365 /* align must be power-of-two */
2366 && (aligni & (aligni - 1)) == 0)
2367 {
2368 val.lattice_val = CONSTANT;
2369 val.value = build_int_cst (ptr_type_node, 0);
2370 val.mask = -aligni;
2371 }
2372 }
2373 break;
2374 }
2375
2376 case BUILT_IN_BSWAP16:
2377 case BUILT_IN_BSWAP32:
2378 case BUILT_IN_BSWAP64:
2379 case BUILT_IN_BSWAP128:
2380 val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
2381 if (val.lattice_val == UNDEFINED)
2382 break;
2383 else if (val.lattice_val == CONSTANT
2384 && val.value
2385 && TREE_CODE (val.value) == INTEGER_CST)
2386 {
2387 tree type = TREE_TYPE (gimple_call_lhs (stmt));
2388 int prec = TYPE_PRECISION (type);
2389 wide_int wval = wi::to_wide (val.value);
2390 val.value
2391 = wide_int_to_tree (type,
2392 wide_int::from (wval, prec,
2393 UNSIGNED).bswap ());
2394 val.mask
2395 = widest_int::from (wide_int::from (val.mask, prec,
2396 UNSIGNED).bswap (),
2397 UNSIGNED);
2398 if (wi::sext (val.mask, prec) != -1)
2399 break;
2400 }
2401 val.lattice_val = VARYING;
2402 val.value = NULL_TREE;
2403 val.mask = -1;
2404 break;
2405
2406 default:;
2407 }
2408 }
2409 if (is_gimple_call (stmt) && gimple_call_lhs (stmt))
2410 {
2411 tree fntype = gimple_call_fntype (stmt);
2412 if (fntype)
2413 {
2414 tree attrs = lookup_attribute ("assume_aligned",
2415 TYPE_ATTRIBUTES (fntype));
2416 if (attrs)
2417 val = bit_value_assume_aligned (stmt, attrs, val, false);
2418 attrs = lookup_attribute ("alloc_align",
2419 TYPE_ATTRIBUTES (fntype));
2420 if (attrs)
2421 val = bit_value_assume_aligned (stmt, attrs, val, true);
2422 }
2423 int flags = ignore_return_flags
2424 ? 0 : gimple_call_return_flags (as_a <gcall *> (stmt));
2425 if (flags & ERF_RETURNS_ARG
2426 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
2427 {
2428 val = get_value_for_expr
2429 (gimple_call_arg (stmt,
2430 flags & ERF_RETURN_ARG_MASK), true);
2431 }
2432 }
2433 is_constant = (val.lattice_val == CONSTANT);
2434 }
2435
2436 if (flag_tree_bit_ccp
2437 && ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
2438 || !is_constant)
2439 && gimple_get_lhs (stmt)
2440 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME)
2441 {
2442 tree lhs = gimple_get_lhs (stmt);
2443 wide_int nonzero_bits = get_nonzero_bits (lhs);
2444 if (nonzero_bits != -1)
2445 {
2446 if (!is_constant)
2447 {
2448 val.lattice_val = CONSTANT;
2449 val.value = build_zero_cst (TREE_TYPE (lhs));
2450 val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (lhs)));
2451 is_constant = true;
2452 }
2453 else
2454 {
2455 if (wi::bit_and_not (wi::to_wide (val.value), nonzero_bits) != 0)
2456 val.value = wide_int_to_tree (TREE_TYPE (lhs),
2457 nonzero_bits
2458 & wi::to_wide (val.value));
2459 if (nonzero_bits == 0)
2460 val.mask = 0;
2461 else
2462 val.mask = val.mask & extend_mask (nonzero_bits,
2463 TYPE_SIGN (TREE_TYPE (lhs)));
2464 }
2465 }
2466 }
2467
2468 /* The statement produced a nonconstant value. */
2469 if (!is_constant)
2470 {
2471 /* The statement produced a copy. */
2472 if (simplified && TREE_CODE (simplified) == SSA_NAME
2473 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (simplified))
2474 {
2475 val.lattice_val = CONSTANT;
2476 val.value = simplified;
2477 val.mask = -1;
2478 }
2479 /* The statement is VARYING. */
2480 else
2481 {
2482 val.lattice_val = VARYING;
2483 val.value = NULL_TREE;
2484 val.mask = -1;
2485 }
2486 }
2487
2488 return val;
2489 }
2490
2491 typedef hash_table<nofree_ptr_hash<gimple> > gimple_htab;
2492
2493 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
2494 each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
2495
2496 static void
insert_clobber_before_stack_restore(tree saved_val,tree var,gimple_htab ** visited)2497 insert_clobber_before_stack_restore (tree saved_val, tree var,
2498 gimple_htab **visited)
2499 {
2500 gimple *stmt;
2501 gassign *clobber_stmt;
2502 tree clobber;
2503 imm_use_iterator iter;
2504 gimple_stmt_iterator i;
2505 gimple **slot;
2506
2507 FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
2508 if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
2509 {
2510 clobber = build_clobber (TREE_TYPE (var), CLOBBER_EOL);
2511 clobber_stmt = gimple_build_assign (var, clobber);
2512
2513 i = gsi_for_stmt (stmt);
2514 gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
2515 }
2516 else if (gimple_code (stmt) == GIMPLE_PHI)
2517 {
2518 if (!*visited)
2519 *visited = new gimple_htab (10);
2520
2521 slot = (*visited)->find_slot (stmt, INSERT);
2522 if (*slot != NULL)
2523 continue;
2524
2525 *slot = stmt;
2526 insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
2527 visited);
2528 }
2529 else if (gimple_assign_ssa_name_copy_p (stmt))
2530 insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var,
2531 visited);
2532 }
2533
2534 /* Advance the iterator to the previous non-debug gimple statement in the same
2535 or dominating basic block. */
2536
2537 static inline void
gsi_prev_dom_bb_nondebug(gimple_stmt_iterator * i)2538 gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
2539 {
2540 basic_block dom;
2541
2542 gsi_prev_nondebug (i);
2543 while (gsi_end_p (*i))
2544 {
2545 dom = get_immediate_dominator (CDI_DOMINATORS, gsi_bb (*i));
2546 if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2547 return;
2548
2549 *i = gsi_last_bb (dom);
2550 }
2551 }
2552
2553 /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
2554 a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
2555
2556 It is possible that BUILT_IN_STACK_SAVE cannot be found in a dominator when
2557 a previous pass (such as DOM) duplicated it along multiple paths to a BB.
2558 In that case the function gives up without inserting the clobbers. */
2559
2560 static void
insert_clobbers_for_var(gimple_stmt_iterator i,tree var)2561 insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
2562 {
2563 gimple *stmt;
2564 tree saved_val;
2565 gimple_htab *visited = NULL;
2566
2567 for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
2568 {
2569 stmt = gsi_stmt (i);
2570
2571 if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
2572 continue;
2573
2574 saved_val = gimple_call_lhs (stmt);
2575 if (saved_val == NULL_TREE)
2576 continue;
2577
2578 insert_clobber_before_stack_restore (saved_val, var, &visited);
2579 break;
2580 }
2581
2582 delete visited;
2583 }
2584
2585 /* Detects a __builtin_alloca_with_align with constant size argument. Declares
2586 fixed-size array and returns the address, if found, otherwise returns
2587 NULL_TREE. */
2588
2589 static tree
fold_builtin_alloca_with_align(gimple * stmt)2590 fold_builtin_alloca_with_align (gimple *stmt)
2591 {
2592 unsigned HOST_WIDE_INT size, threshold, n_elem;
2593 tree lhs, arg, block, var, elem_type, array_type;
2594
2595 /* Get lhs. */
2596 lhs = gimple_call_lhs (stmt);
2597 if (lhs == NULL_TREE)
2598 return NULL_TREE;
2599
2600 /* Detect constant argument. */
2601 arg = get_constant_value (gimple_call_arg (stmt, 0));
2602 if (arg == NULL_TREE
2603 || TREE_CODE (arg) != INTEGER_CST
2604 || !tree_fits_uhwi_p (arg))
2605 return NULL_TREE;
2606
2607 size = tree_to_uhwi (arg);
2608
2609 /* Heuristic: don't fold large allocas. */
2610 threshold = (unsigned HOST_WIDE_INT)param_large_stack_frame;
2611 /* In case the alloca is located at function entry, it has the same lifetime
2612 as a declared array, so we allow a larger size. */
2613 block = gimple_block (stmt);
2614 if (!(cfun->after_inlining
2615 && block
2616 && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
2617 threshold /= 10;
2618 if (size > threshold)
2619 return NULL_TREE;
2620
2621 /* We have to be able to move points-to info. We used to assert
2622 that we can but IPA PTA might end up with two UIDs here
2623 as it might need to handle more than one instance being
2624 live at the same time. Instead of trying to detect this case
2625 (using the first UID would be OK) just give up for now. */
2626 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
2627 unsigned uid = 0;
2628 if (pi != NULL
2629 && !pi->pt.anything
2630 && !pt_solution_singleton_or_null_p (&pi->pt, &uid))
2631 return NULL_TREE;
2632
2633 /* Declare array. */
2634 elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
2635 n_elem = size * 8 / BITS_PER_UNIT;
2636 array_type = build_array_type_nelts (elem_type, n_elem);
2637
2638 if (tree ssa_name = SSA_NAME_IDENTIFIER (lhs))
2639 {
2640 /* Give the temporary a name derived from the name of the VLA
2641 declaration so it can be referenced in diagnostics. */
2642 const char *name = IDENTIFIER_POINTER (ssa_name);
2643 var = create_tmp_var (array_type, name);
2644 }
2645 else
2646 var = create_tmp_var (array_type);
2647
2648 if (gimple *lhsdef = SSA_NAME_DEF_STMT (lhs))
2649 {
2650 /* Set the temporary's location to that of the VLA declaration
2651 so it can be pointed to in diagnostics. */
2652 location_t loc = gimple_location (lhsdef);
2653 DECL_SOURCE_LOCATION (var) = loc;
2654 }
2655
2656 SET_DECL_ALIGN (var, TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2657 if (uid != 0)
2658 SET_DECL_PT_UID (var, uid);
2659
2660 /* Fold alloca to the address of the array. */
2661 return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
2662 }
2663
2664 /* Fold the stmt at *GSI with CCP specific information that propagating
2665 and regular folding does not catch. */
2666
2667 bool
fold_stmt(gimple_stmt_iterator * gsi)2668 ccp_folder::fold_stmt (gimple_stmt_iterator *gsi)
2669 {
2670 gimple *stmt = gsi_stmt (*gsi);
2671
2672 switch (gimple_code (stmt))
2673 {
2674 case GIMPLE_COND:
2675 {
2676 gcond *cond_stmt = as_a <gcond *> (stmt);
2677 ccp_prop_value_t val;
2678 /* Statement evaluation will handle type mismatches in constants
2679 more gracefully than the final propagation. This allows us to
2680 fold more conditionals here. */
2681 val = evaluate_stmt (stmt);
2682 if (val.lattice_val != CONSTANT
2683 || val.mask != 0)
2684 return false;
2685
2686 if (dump_file)
2687 {
2688 fprintf (dump_file, "Folding predicate ");
2689 print_gimple_expr (dump_file, stmt, 0);
2690 fprintf (dump_file, " to ");
2691 print_generic_expr (dump_file, val.value);
2692 fprintf (dump_file, "\n");
2693 }
2694
2695 if (integer_zerop (val.value))
2696 gimple_cond_make_false (cond_stmt);
2697 else
2698 gimple_cond_make_true (cond_stmt);
2699
2700 return true;
2701 }
2702
2703 case GIMPLE_CALL:
2704 {
2705 tree lhs = gimple_call_lhs (stmt);
2706 int flags = gimple_call_flags (stmt);
2707 tree val;
2708 tree argt;
2709 bool changed = false;
2710 unsigned i;
2711
2712 /* If the call was folded into a constant make sure it goes
2713 away even if we cannot propagate into all uses because of
2714 type issues. */
2715 if (lhs
2716 && TREE_CODE (lhs) == SSA_NAME
2717 && (val = get_constant_value (lhs))
2718 /* Don't optimize away calls that have side-effects. */
2719 && (flags & (ECF_CONST|ECF_PURE)) != 0
2720 && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
2721 {
2722 tree new_rhs = unshare_expr (val);
2723 if (!useless_type_conversion_p (TREE_TYPE (lhs),
2724 TREE_TYPE (new_rhs)))
2725 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
2726 gimplify_and_update_call_from_tree (gsi, new_rhs);
2727 return true;
2728 }
2729
2730 /* Internal calls provide no argument types, so the extra laxity
2731 for normal calls does not apply. */
2732 if (gimple_call_internal_p (stmt))
2733 return false;
2734
2735 /* The heuristic of fold_builtin_alloca_with_align differs before and
2736 after inlining, so we don't require the arg to be changed into a
2737 constant for folding, but just to be constant. */
2738 if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)
2739 || gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
2740 {
2741 tree new_rhs = fold_builtin_alloca_with_align (stmt);
2742 if (new_rhs)
2743 {
2744 gimplify_and_update_call_from_tree (gsi, new_rhs);
2745 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
2746 insert_clobbers_for_var (*gsi, var);
2747 return true;
2748 }
2749 }
2750
2751 /* If there's no extra info from an assume_aligned call,
2752 drop it so it doesn't act as otherwise useless dataflow
2753 barrier. */
2754 if (gimple_call_builtin_p (stmt, BUILT_IN_ASSUME_ALIGNED))
2755 {
2756 tree ptr = gimple_call_arg (stmt, 0);
2757 ccp_prop_value_t ptrval = get_value_for_expr (ptr, true);
2758 if (ptrval.lattice_val == CONSTANT
2759 && TREE_CODE (ptrval.value) == INTEGER_CST
2760 && ptrval.mask != 0)
2761 {
2762 ccp_prop_value_t val
2763 = bit_value_assume_aligned (stmt, NULL_TREE, ptrval, false);
2764 unsigned int ptralign = least_bit_hwi (ptrval.mask.to_uhwi ());
2765 unsigned int align = least_bit_hwi (val.mask.to_uhwi ());
2766 if (ptralign == align
2767 && ((TREE_INT_CST_LOW (ptrval.value) & (align - 1))
2768 == (TREE_INT_CST_LOW (val.value) & (align - 1))))
2769 {
2770 replace_call_with_value (gsi, ptr);
2771 return true;
2772 }
2773 }
2774 }
2775
2776 /* Propagate into the call arguments. Compared to replace_uses_in
2777 this can use the argument slot types for type verification
2778 instead of the current argument type. We also can safely
2779 drop qualifiers here as we are dealing with constants anyway. */
2780 argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
2781 for (i = 0; i < gimple_call_num_args (stmt) && argt;
2782 ++i, argt = TREE_CHAIN (argt))
2783 {
2784 tree arg = gimple_call_arg (stmt, i);
2785 if (TREE_CODE (arg) == SSA_NAME
2786 && (val = get_constant_value (arg))
2787 && useless_type_conversion_p
2788 (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
2789 TYPE_MAIN_VARIANT (TREE_TYPE (val))))
2790 {
2791 gimple_call_set_arg (stmt, i, unshare_expr (val));
2792 changed = true;
2793 }
2794 }
2795
2796 return changed;
2797 }
2798
2799 case GIMPLE_ASSIGN:
2800 {
2801 tree lhs = gimple_assign_lhs (stmt);
2802 tree val;
2803
2804 /* If we have a load that turned out to be constant replace it
2805 as we cannot propagate into all uses in all cases. */
2806 if (gimple_assign_single_p (stmt)
2807 && TREE_CODE (lhs) == SSA_NAME
2808 && (val = get_constant_value (lhs)))
2809 {
2810 tree rhs = unshare_expr (val);
2811 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2812 rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2813 gimple_assign_set_rhs_from_tree (gsi, rhs);
2814 return true;
2815 }
2816
2817 return false;
2818 }
2819
2820 default:
2821 return false;
2822 }
2823 }
2824
2825 /* Visit the assignment statement STMT. Set the value of its LHS to the
2826 value computed by the RHS and store LHS in *OUTPUT_P. If STMT
2827 creates virtual definitions, set the value of each new name to that
2828 of the RHS (if we can derive a constant out of the RHS).
2829 Value-returning call statements also perform an assignment, and
2830 are handled here. */
2831
2832 static enum ssa_prop_result
visit_assignment(gimple * stmt,tree * output_p)2833 visit_assignment (gimple *stmt, tree *output_p)
2834 {
2835 ccp_prop_value_t val;
2836 enum ssa_prop_result retval = SSA_PROP_NOT_INTERESTING;
2837
2838 tree lhs = gimple_get_lhs (stmt);
2839 if (TREE_CODE (lhs) == SSA_NAME)
2840 {
2841 /* Evaluate the statement, which could be
2842 either a GIMPLE_ASSIGN or a GIMPLE_CALL. */
2843 val = evaluate_stmt (stmt);
2844
2845 /* If STMT is an assignment to an SSA_NAME, we only have one
2846 value to set. */
2847 if (set_lattice_value (lhs, &val))
2848 {
2849 *output_p = lhs;
2850 if (val.lattice_val == VARYING)
2851 retval = SSA_PROP_VARYING;
2852 else
2853 retval = SSA_PROP_INTERESTING;
2854 }
2855 }
2856
2857 return retval;
2858 }
2859
2860
2861 /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
2862 if it can determine which edge will be taken. Otherwise, return
2863 SSA_PROP_VARYING. */
2864
2865 static enum ssa_prop_result
visit_cond_stmt(gimple * stmt,edge * taken_edge_p)2866 visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
2867 {
2868 ccp_prop_value_t val;
2869 basic_block block;
2870
2871 block = gimple_bb (stmt);
2872 val = evaluate_stmt (stmt);
2873 if (val.lattice_val != CONSTANT
2874 || val.mask != 0)
2875 return SSA_PROP_VARYING;
2876
2877 /* Find which edge out of the conditional block will be taken and add it
2878 to the worklist. If no single edge can be determined statically,
2879 return SSA_PROP_VARYING to feed all the outgoing edges to the
2880 propagation engine. */
2881 *taken_edge_p = find_taken_edge (block, val.value);
2882 if (*taken_edge_p)
2883 return SSA_PROP_INTERESTING;
2884 else
2885 return SSA_PROP_VARYING;
2886 }
2887
2888
2889 /* Evaluate statement STMT. If the statement produces an output value and
2890 its evaluation changes the lattice value of its output, return
2891 SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2892 output value.
2893
2894 If STMT is a conditional branch and we can determine its truth
2895 value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
2896 value, return SSA_PROP_VARYING. */
2897
2898 enum ssa_prop_result
visit_stmt(gimple * stmt,edge * taken_edge_p,tree * output_p)2899 ccp_propagate::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
2900 {
2901 tree def;
2902 ssa_op_iter iter;
2903
2904 if (dump_file && (dump_flags & TDF_DETAILS))
2905 {
2906 fprintf (dump_file, "\nVisiting statement:\n");
2907 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2908 }
2909
2910 switch (gimple_code (stmt))
2911 {
2912 case GIMPLE_ASSIGN:
2913 /* If the statement is an assignment that produces a single
2914 output value, evaluate its RHS to see if the lattice value of
2915 its output has changed. */
2916 return visit_assignment (stmt, output_p);
2917
2918 case GIMPLE_CALL:
2919 /* A value-returning call also performs an assignment. */
2920 if (gimple_call_lhs (stmt) != NULL_TREE)
2921 return visit_assignment (stmt, output_p);
2922 break;
2923
2924 case GIMPLE_COND:
2925 case GIMPLE_SWITCH:
2926 /* If STMT is a conditional branch, see if we can determine
2927 which branch will be taken. */
2928 /* FIXME. It appears that we should be able to optimize
2929 computed GOTOs here as well. */
2930 return visit_cond_stmt (stmt, taken_edge_p);
2931
2932 default:
2933 break;
2934 }
2935
2936 /* Any other kind of statement is not interesting for constant
2937 propagation and, therefore, not worth simulating. */
2938 if (dump_file && (dump_flags & TDF_DETAILS))
2939 fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
2940
2941 /* Definitions made by statements other than assignments to
2942 SSA_NAMEs represent unknown modifications to their outputs.
2943 Mark them VARYING. */
2944 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
2945 set_value_varying (def);
2946
2947 return SSA_PROP_VARYING;
2948 }
2949
2950
2951 /* Main entry point for SSA Conditional Constant Propagation. If NONZERO_P,
2952 record nonzero bits. */
2953
2954 static unsigned int
do_ssa_ccp(bool nonzero_p)2955 do_ssa_ccp (bool nonzero_p)
2956 {
2957 unsigned int todo = 0;
2958 calculate_dominance_info (CDI_DOMINATORS);
2959
2960 ccp_initialize ();
2961 class ccp_propagate ccp_propagate;
2962 ccp_propagate.ssa_propagate ();
2963 if (ccp_finalize (nonzero_p || flag_ipa_bit_cp))
2964 {
2965 todo = (TODO_cleanup_cfg | TODO_update_ssa);
2966
2967 /* ccp_finalize does not preserve loop-closed ssa. */
2968 loops_state_clear (LOOP_CLOSED_SSA);
2969 }
2970
2971 free_dominance_info (CDI_DOMINATORS);
2972 return todo;
2973 }
2974
2975
2976 namespace {
2977
2978 const pass_data pass_data_ccp =
2979 {
2980 GIMPLE_PASS, /* type */
2981 "ccp", /* name */
2982 OPTGROUP_NONE, /* optinfo_flags */
2983 TV_TREE_CCP, /* tv_id */
2984 ( PROP_cfg | PROP_ssa ), /* properties_required */
2985 0, /* properties_provided */
2986 0, /* properties_destroyed */
2987 0, /* todo_flags_start */
2988 TODO_update_address_taken, /* todo_flags_finish */
2989 };
2990
2991 class pass_ccp : public gimple_opt_pass
2992 {
2993 public:
pass_ccp(gcc::context * ctxt)2994 pass_ccp (gcc::context *ctxt)
2995 : gimple_opt_pass (pass_data_ccp, ctxt), nonzero_p (false)
2996 {}
2997
2998 /* opt_pass methods: */
clone()2999 opt_pass * clone () { return new pass_ccp (m_ctxt); }
set_pass_param(unsigned int n,bool param)3000 void set_pass_param (unsigned int n, bool param)
3001 {
3002 gcc_assert (n == 0);
3003 nonzero_p = param;
3004 }
gate(function *)3005 virtual bool gate (function *) { return flag_tree_ccp != 0; }
execute(function *)3006 virtual unsigned int execute (function *) { return do_ssa_ccp (nonzero_p); }
3007
3008 private:
3009 /* Determines whether the pass instance records nonzero bits. */
3010 bool nonzero_p;
3011 }; // class pass_ccp
3012
3013 } // anon namespace
3014
3015 gimple_opt_pass *
make_pass_ccp(gcc::context * ctxt)3016 make_pass_ccp (gcc::context *ctxt)
3017 {
3018 return new pass_ccp (ctxt);
3019 }
3020
3021
3022
3023 /* Try to optimize out __builtin_stack_restore. Optimize it out
3024 if there is another __builtin_stack_restore in the same basic
3025 block and no calls or ASM_EXPRs are in between, or if this block's
3026 only outgoing edge is to EXIT_BLOCK and there are no calls or
3027 ASM_EXPRs after this __builtin_stack_restore. */
3028
3029 static tree
optimize_stack_restore(gimple_stmt_iterator i)3030 optimize_stack_restore (gimple_stmt_iterator i)
3031 {
3032 tree callee;
3033 gimple *stmt;
3034
3035 basic_block bb = gsi_bb (i);
3036 gimple *call = gsi_stmt (i);
3037
3038 if (gimple_code (call) != GIMPLE_CALL
3039 || gimple_call_num_args (call) != 1
3040 || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
3041 || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
3042 return NULL_TREE;
3043
3044 for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
3045 {
3046 stmt = gsi_stmt (i);
3047 if (gimple_code (stmt) == GIMPLE_ASM)
3048 return NULL_TREE;
3049 if (gimple_code (stmt) != GIMPLE_CALL)
3050 continue;
3051
3052 callee = gimple_call_fndecl (stmt);
3053 if (!callee
3054 || !fndecl_built_in_p (callee, BUILT_IN_NORMAL)
3055 /* All regular builtins are ok, just obviously not alloca. */
3056 || ALLOCA_FUNCTION_CODE_P (DECL_FUNCTION_CODE (callee)))
3057 return NULL_TREE;
3058
3059 if (fndecl_built_in_p (callee, BUILT_IN_STACK_RESTORE))
3060 goto second_stack_restore;
3061 }
3062
3063 if (!gsi_end_p (i))
3064 return NULL_TREE;
3065
3066 /* Allow one successor of the exit block, or zero successors. */
3067 switch (EDGE_COUNT (bb->succs))
3068 {
3069 case 0:
3070 break;
3071 case 1:
3072 if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3073 return NULL_TREE;
3074 break;
3075 default:
3076 return NULL_TREE;
3077 }
3078 second_stack_restore:
3079
3080 /* If there's exactly one use, then zap the call to __builtin_stack_save.
3081 If there are multiple uses, then the last one should remove the call.
3082 In any case, whether the call to __builtin_stack_save can be removed
3083 or not is irrelevant to removing the call to __builtin_stack_restore. */
3084 if (has_single_use (gimple_call_arg (call, 0)))
3085 {
3086 gimple *stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
3087 if (is_gimple_call (stack_save))
3088 {
3089 callee = gimple_call_fndecl (stack_save);
3090 if (callee && fndecl_built_in_p (callee, BUILT_IN_STACK_SAVE))
3091 {
3092 gimple_stmt_iterator stack_save_gsi;
3093 tree rhs;
3094
3095 stack_save_gsi = gsi_for_stmt (stack_save);
3096 rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
3097 replace_call_with_value (&stack_save_gsi, rhs);
3098 }
3099 }
3100 }
3101
3102 /* No effect, so the statement will be deleted. */
3103 return integer_zero_node;
3104 }
3105
3106 /* If va_list type is a simple pointer and nothing special is needed,
3107 optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
3108 __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
3109 pointer assignment. */
3110
3111 static tree
optimize_stdarg_builtin(gimple * call)3112 optimize_stdarg_builtin (gimple *call)
3113 {
3114 tree callee, lhs, rhs, cfun_va_list;
3115 bool va_list_simple_ptr;
3116 location_t loc = gimple_location (call);
3117
3118 callee = gimple_call_fndecl (call);
3119
3120 cfun_va_list = targetm.fn_abi_va_list (callee);
3121 va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
3122 && (TREE_TYPE (cfun_va_list) == void_type_node
3123 || TREE_TYPE (cfun_va_list) == char_type_node);
3124
3125 switch (DECL_FUNCTION_CODE (callee))
3126 {
3127 case BUILT_IN_VA_START:
3128 if (!va_list_simple_ptr
3129 || targetm.expand_builtin_va_start != NULL
3130 || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG))
3131 return NULL_TREE;
3132
3133 if (gimple_call_num_args (call) != 2)
3134 return NULL_TREE;
3135
3136 lhs = gimple_call_arg (call, 0);
3137 if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3138 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3139 != TYPE_MAIN_VARIANT (cfun_va_list))
3140 return NULL_TREE;
3141
3142 lhs = build_fold_indirect_ref_loc (loc, lhs);
3143 rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG),
3144 1, integer_zero_node);
3145 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3146 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3147
3148 case BUILT_IN_VA_COPY:
3149 if (!va_list_simple_ptr)
3150 return NULL_TREE;
3151
3152 if (gimple_call_num_args (call) != 2)
3153 return NULL_TREE;
3154
3155 lhs = gimple_call_arg (call, 0);
3156 if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3157 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3158 != TYPE_MAIN_VARIANT (cfun_va_list))
3159 return NULL_TREE;
3160
3161 lhs = build_fold_indirect_ref_loc (loc, lhs);
3162 rhs = gimple_call_arg (call, 1);
3163 if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
3164 != TYPE_MAIN_VARIANT (cfun_va_list))
3165 return NULL_TREE;
3166
3167 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3168 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3169
3170 case BUILT_IN_VA_END:
3171 /* No effect, so the statement will be deleted. */
3172 return integer_zero_node;
3173
3174 default:
3175 gcc_unreachable ();
3176 }
3177 }
3178
3179 /* Attemp to make the block of __builtin_unreachable I unreachable by changing
3180 the incoming jumps. Return true if at least one jump was changed. */
3181
3182 static bool
optimize_unreachable(gimple_stmt_iterator i)3183 optimize_unreachable (gimple_stmt_iterator i)
3184 {
3185 basic_block bb = gsi_bb (i);
3186 gimple_stmt_iterator gsi;
3187 gimple *stmt;
3188 edge_iterator ei;
3189 edge e;
3190 bool ret;
3191
3192 if (flag_sanitize & SANITIZE_UNREACHABLE)
3193 return false;
3194
3195 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3196 {
3197 stmt = gsi_stmt (gsi);
3198
3199 if (is_gimple_debug (stmt))
3200 continue;
3201
3202 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
3203 {
3204 /* Verify we do not need to preserve the label. */
3205 if (FORCED_LABEL (gimple_label_label (label_stmt)))
3206 return false;
3207
3208 continue;
3209 }
3210
3211 /* Only handle the case that __builtin_unreachable is the first statement
3212 in the block. We rely on DCE to remove stmts without side-effects
3213 before __builtin_unreachable. */
3214 if (gsi_stmt (gsi) != gsi_stmt (i))
3215 return false;
3216 }
3217
3218 ret = false;
3219 FOR_EACH_EDGE (e, ei, bb->preds)
3220 {
3221 gsi = gsi_last_bb (e->src);
3222 if (gsi_end_p (gsi))
3223 continue;
3224
3225 stmt = gsi_stmt (gsi);
3226 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
3227 {
3228 if (e->flags & EDGE_TRUE_VALUE)
3229 gimple_cond_make_false (cond_stmt);
3230 else if (e->flags & EDGE_FALSE_VALUE)
3231 gimple_cond_make_true (cond_stmt);
3232 else
3233 gcc_unreachable ();
3234 update_stmt (cond_stmt);
3235 }
3236 else
3237 {
3238 /* Todo: handle other cases. Note that unreachable switch case
3239 statements have already been removed. */
3240 continue;
3241 }
3242
3243 ret = true;
3244 }
3245
3246 return ret;
3247 }
3248
3249 /* Convert
3250 _1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3251 _7 = ~_1;
3252 _5 = (_Bool) _7;
3253 to
3254 _1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3255 _8 = _1 & 1;
3256 _5 = _8 == 0;
3257 and convert
3258 _1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3259 _7 = ~_1;
3260 _4 = (_Bool) _7;
3261 to
3262 _1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3263 _8 = _1 & 1;
3264 _4 = (_Bool) _8;
3265
3266 USE_STMT is the gimplt statement which uses the return value of
3267 __atomic_fetch_or_*. LHS is the return value of __atomic_fetch_or_*.
3268 MASK is the mask passed to __atomic_fetch_or_*.
3269 */
3270
3271 static gimple *
convert_atomic_bit_not(enum internal_fn fn,gimple * use_stmt,tree lhs,tree mask)3272 convert_atomic_bit_not (enum internal_fn fn, gimple *use_stmt,
3273 tree lhs, tree mask)
3274 {
3275 tree and_mask;
3276 if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3277 {
3278 /* MASK must be ~1. */
3279 if (!operand_equal_p (build_int_cst (TREE_TYPE (lhs),
3280 ~HOST_WIDE_INT_1), mask, 0))
3281 return nullptr;
3282 and_mask = build_int_cst (TREE_TYPE (lhs), 1);
3283 }
3284 else
3285 {
3286 /* MASK must be 1. */
3287 if (!operand_equal_p (build_int_cst (TREE_TYPE (lhs), 1), mask, 0))
3288 return nullptr;
3289 and_mask = mask;
3290 }
3291
3292 tree use_lhs = gimple_assign_lhs (use_stmt);
3293
3294 use_operand_p use_p;
3295 gimple *use_not_stmt;
3296
3297 if (!single_imm_use (use_lhs, &use_p, &use_not_stmt)
3298 || !is_gimple_assign (use_not_stmt))
3299 return nullptr;
3300
3301 if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_not_stmt)))
3302 return nullptr;
3303
3304 tree use_not_lhs = gimple_assign_lhs (use_not_stmt);
3305 if (TREE_CODE (TREE_TYPE (use_not_lhs)) != BOOLEAN_TYPE)
3306 return nullptr;
3307
3308 gimple_stmt_iterator gsi;
3309 gsi = gsi_for_stmt (use_stmt);
3310 gsi_remove (&gsi, true);
3311 tree var = make_ssa_name (TREE_TYPE (lhs));
3312 use_stmt = gimple_build_assign (var, BIT_AND_EXPR, lhs, and_mask);
3313 gsi = gsi_for_stmt (use_not_stmt);
3314 gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
3315 lhs = gimple_assign_lhs (use_not_stmt);
3316 gimple *g = gimple_build_assign (lhs, EQ_EXPR, var,
3317 build_zero_cst (TREE_TYPE (mask)));
3318 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3319 gsi = gsi_for_stmt (use_not_stmt);
3320 gsi_remove (&gsi, true);
3321 return use_stmt;
3322 }
3323
3324 /* match.pd function to match atomic_bit_test_and pattern which
3325 has nop_convert:
3326 _1 = __atomic_fetch_or_4 (&v, 1, 0);
3327 _2 = (int) _1;
3328 _5 = _2 & 1;
3329 */
3330 extern bool gimple_nop_atomic_bit_test_and_p (tree, tree *,
3331 tree (*) (tree));
3332 extern bool gimple_nop_convert (tree, tree*, tree (*) (tree));
3333
3334 /* Optimize
3335 mask_2 = 1 << cnt_1;
3336 _4 = __atomic_fetch_or_* (ptr_6, mask_2, _3);
3337 _5 = _4 & mask_2;
3338 to
3339 _4 = .ATOMIC_BIT_TEST_AND_SET (ptr_6, cnt_1, 0, _3);
3340 _5 = _4;
3341 If _5 is only used in _5 != 0 or _5 == 0 comparisons, 1
3342 is passed instead of 0, and the builtin just returns a zero
3343 or 1 value instead of the actual bit.
3344 Similarly for __sync_fetch_and_or_* (without the ", _3" part
3345 in there), and/or if mask_2 is a power of 2 constant.
3346 Similarly for xor instead of or, use ATOMIC_BIT_TEST_AND_COMPLEMENT
3347 in that case. And similarly for and instead of or, except that
3348 the second argument to the builtin needs to be one's complement
3349 of the mask instead of mask. */
3350
3351 static bool
optimize_atomic_bit_test_and(gimple_stmt_iterator * gsip,enum internal_fn fn,bool has_model_arg,bool after)3352 optimize_atomic_bit_test_and (gimple_stmt_iterator *gsip,
3353 enum internal_fn fn, bool has_model_arg,
3354 bool after)
3355 {
3356 gimple *call = gsi_stmt (*gsip);
3357 tree lhs = gimple_call_lhs (call);
3358 use_operand_p use_p;
3359 gimple *use_stmt;
3360 tree mask;
3361 optab optab;
3362
3363 if (!flag_inline_atomics
3364 || optimize_debug
3365 || !gimple_call_builtin_p (call, BUILT_IN_NORMAL)
3366 || !lhs
3367 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
3368 || !single_imm_use (lhs, &use_p, &use_stmt)
3369 || !is_gimple_assign (use_stmt)
3370 || !gimple_vdef (call))
3371 return false;
3372
3373 switch (fn)
3374 {
3375 case IFN_ATOMIC_BIT_TEST_AND_SET:
3376 optab = atomic_bit_test_and_set_optab;
3377 break;
3378 case IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT:
3379 optab = atomic_bit_test_and_complement_optab;
3380 break;
3381 case IFN_ATOMIC_BIT_TEST_AND_RESET:
3382 optab = atomic_bit_test_and_reset_optab;
3383 break;
3384 default:
3385 return false;
3386 }
3387
3388 tree bit = nullptr;
3389
3390 mask = gimple_call_arg (call, 1);
3391 tree_code rhs_code = gimple_assign_rhs_code (use_stmt);
3392 if (rhs_code != BIT_AND_EXPR)
3393 {
3394 if (rhs_code != NOP_EXPR && rhs_code != BIT_NOT_EXPR)
3395 return false;
3396
3397 tree use_lhs = gimple_assign_lhs (use_stmt);
3398 if (TREE_CODE (use_lhs) == SSA_NAME
3399 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs))
3400 return false;
3401
3402 tree use_rhs = gimple_assign_rhs1 (use_stmt);
3403 if (lhs != use_rhs)
3404 return false;
3405
3406 if (optab_handler (optab, TYPE_MODE (TREE_TYPE (lhs)))
3407 == CODE_FOR_nothing)
3408 return false;
3409
3410 gimple *g;
3411 gimple_stmt_iterator gsi;
3412 tree var;
3413 int ibit = -1;
3414
3415 if (rhs_code == BIT_NOT_EXPR)
3416 {
3417 g = convert_atomic_bit_not (fn, use_stmt, lhs, mask);
3418 if (!g)
3419 return false;
3420 use_stmt = g;
3421 ibit = 0;
3422 }
3423 else if (TREE_CODE (TREE_TYPE (use_lhs)) == BOOLEAN_TYPE)
3424 {
3425 tree and_mask;
3426 if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3427 {
3428 /* MASK must be ~1. */
3429 if (!operand_equal_p (build_int_cst (TREE_TYPE (lhs),
3430 ~HOST_WIDE_INT_1),
3431 mask, 0))
3432 return false;
3433
3434 /* Convert
3435 _1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3436 _4 = (_Bool) _1;
3437 to
3438 _1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3439 _5 = _1 & 1;
3440 _4 = (_Bool) _5;
3441 */
3442 and_mask = build_int_cst (TREE_TYPE (lhs), 1);
3443 }
3444 else
3445 {
3446 and_mask = build_int_cst (TREE_TYPE (lhs), 1);
3447 if (!operand_equal_p (and_mask, mask, 0))
3448 return false;
3449
3450 /* Convert
3451 _1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3452 _4 = (_Bool) _1;
3453 to
3454 _1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3455 _5 = _1 & 1;
3456 _4 = (_Bool) _5;
3457 */
3458 }
3459 var = make_ssa_name (TREE_TYPE (use_rhs));
3460 replace_uses_by (use_rhs, var);
3461 g = gimple_build_assign (var, BIT_AND_EXPR, use_rhs,
3462 and_mask);
3463 gsi = gsi_for_stmt (use_stmt);
3464 gsi_insert_before (&gsi, g, GSI_NEW_STMT);
3465 use_stmt = g;
3466 ibit = 0;
3467 }
3468 else if (TYPE_PRECISION (TREE_TYPE (use_lhs))
3469 <= TYPE_PRECISION (TREE_TYPE (use_rhs)))
3470 {
3471 gimple *use_nop_stmt;
3472 if (!single_imm_use (use_lhs, &use_p, &use_nop_stmt)
3473 || !is_gimple_assign (use_nop_stmt))
3474 return false;
3475 tree use_nop_lhs = gimple_assign_lhs (use_nop_stmt);
3476 rhs_code = gimple_assign_rhs_code (use_nop_stmt);
3477 if (rhs_code != BIT_AND_EXPR)
3478 {
3479 if (TREE_CODE (use_nop_lhs) == SSA_NAME
3480 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_nop_lhs))
3481 return false;
3482 if (rhs_code == BIT_NOT_EXPR)
3483 {
3484 g = convert_atomic_bit_not (fn, use_nop_stmt, lhs,
3485 mask);
3486 if (!g)
3487 return false;
3488 /* Convert
3489 _1 = __atomic_fetch_or_4 (ptr_6, 1, _3);
3490 _2 = (int) _1;
3491 _7 = ~_2;
3492 _5 = (_Bool) _7;
3493 to
3494 _1 = __atomic_fetch_or_4 (ptr_6, ~1, _3);
3495 _8 = _1 & 1;
3496 _5 = _8 == 0;
3497 and convert
3498 _1 = __atomic_fetch_and_4 (ptr_6, ~1, _3);
3499 _2 = (int) _1;
3500 _7 = ~_2;
3501 _5 = (_Bool) _7;
3502 to
3503 _1 = __atomic_fetch_and_4 (ptr_6, 1, _3);
3504 _8 = _1 & 1;
3505 _5 = _8 == 0;
3506 */
3507 gsi = gsi_for_stmt (use_stmt);
3508 gsi_remove (&gsi, true);
3509 use_stmt = g;
3510 ibit = 0;
3511 }
3512 else
3513 {
3514 if (TREE_CODE (TREE_TYPE (use_nop_lhs)) != BOOLEAN_TYPE)
3515 return false;
3516 if (rhs_code != GE_EXPR && rhs_code != LT_EXPR)
3517 return false;
3518 tree cmp_rhs1 = gimple_assign_rhs1 (use_nop_stmt);
3519 if (use_lhs != cmp_rhs1)
3520 return false;
3521 tree cmp_rhs2 = gimple_assign_rhs2 (use_nop_stmt);
3522 if (!integer_zerop (cmp_rhs2))
3523 return false;
3524
3525 tree and_mask;
3526
3527 unsigned HOST_WIDE_INT bytes
3528 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (use_rhs)));
3529 ibit = bytes * BITS_PER_UNIT - 1;
3530 unsigned HOST_WIDE_INT highest
3531 = HOST_WIDE_INT_1U << ibit;
3532
3533 if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3534 {
3535 /* Get the signed maximum of the USE_RHS type. */
3536 and_mask = build_int_cst (TREE_TYPE (use_rhs),
3537 highest - 1);
3538 if (!operand_equal_p (and_mask, mask, 0))
3539 return false;
3540
3541 /* Convert
3542 _1 = __atomic_fetch_and_4 (ptr_6, 0x7fffffff, _3);
3543 _5 = (signed int) _1;
3544 _4 = _5 < 0 or _5 >= 0;
3545 to
3546 _1 = __atomic_fetch_and_4 (ptr_6, 0x7fffffff, _3);
3547 _6 = _1 & 0x80000000;
3548 _4 = _6 != 0 or _6 == 0;
3549 */
3550 and_mask = build_int_cst (TREE_TYPE (use_rhs),
3551 highest);
3552 }
3553 else
3554 {
3555 /* Get the signed minimum of the USE_RHS type. */
3556 and_mask = build_int_cst (TREE_TYPE (use_rhs),
3557 highest);
3558 if (!operand_equal_p (and_mask, mask, 0))
3559 return false;
3560
3561 /* Convert
3562 _1 = __atomic_fetch_or_4 (ptr_6, 0x80000000, _3);
3563 _5 = (signed int) _1;
3564 _4 = _5 < 0 or _5 >= 0;
3565 to
3566 _1 = __atomic_fetch_or_4 (ptr_6, 0x80000000, _3);
3567 _6 = _1 & 0x80000000;
3568 _4 = _6 != 0 or _6 == 0;
3569 */
3570 }
3571 var = make_ssa_name (TREE_TYPE (use_rhs));
3572 gsi = gsi_for_stmt (use_stmt);
3573 gsi_remove (&gsi, true);
3574 g = gimple_build_assign (var, BIT_AND_EXPR, use_rhs,
3575 and_mask);
3576 gsi = gsi_for_stmt (use_nop_stmt);
3577 gsi_insert_before (&gsi, g, GSI_NEW_STMT);
3578 use_stmt = g;
3579 g = gimple_build_assign (use_nop_lhs,
3580 (rhs_code == GE_EXPR
3581 ? EQ_EXPR : NE_EXPR),
3582 var,
3583 build_zero_cst (TREE_TYPE (use_rhs)));
3584 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3585 gsi = gsi_for_stmt (use_nop_stmt);
3586 gsi_remove (&gsi, true);
3587 }
3588 }
3589 else
3590 {
3591 tree match_op[3];
3592 gimple *g;
3593 if (!gimple_nop_atomic_bit_test_and_p (use_nop_lhs,
3594 &match_op[0], NULL)
3595 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (match_op[2])
3596 || !single_imm_use (match_op[2], &use_p, &g)
3597 || !is_gimple_assign (g))
3598 return false;
3599 mask = match_op[0];
3600 if (TREE_CODE (match_op[1]) == INTEGER_CST)
3601 {
3602 ibit = tree_log2 (match_op[1]);
3603 gcc_assert (ibit >= 0);
3604 }
3605 else
3606 {
3607 g = SSA_NAME_DEF_STMT (match_op[1]);
3608 gcc_assert (is_gimple_assign (g));
3609 bit = gimple_assign_rhs2 (g);
3610 }
3611 /* Convert
3612 _1 = __atomic_fetch_or_4 (ptr_6, mask, _3);
3613 _2 = (int) _1;
3614 _5 = _2 & mask;
3615 to
3616 _1 = __atomic_fetch_or_4 (ptr_6, mask, _3);
3617 _6 = _1 & mask;
3618 _5 = (int) _6;
3619 and convert
3620 _1 = ~mask_7;
3621 _2 = (unsigned int) _1;
3622 _3 = __atomic_fetch_and_4 (ptr_6, _2, 0);
3623 _4 = (int) _3;
3624 _5 = _4 & mask_7;
3625 to
3626 _1 = __atomic_fetch_and_* (ptr_6, ~mask_7, _3);
3627 _12 = _3 & mask_7;
3628 _5 = (int) _12;
3629
3630 and Convert
3631 _1 = __atomic_fetch_and_4 (ptr_6, ~mask, _3);
3632 _2 = (short int) _1;
3633 _5 = _2 & mask;
3634 to
3635 _1 = __atomic_fetch_and_4 (ptr_6, ~mask, _3);
3636 _8 = _1 & mask;
3637 _5 = (short int) _8;
3638 */
3639 gimple_seq stmts = NULL;
3640 match_op[1] = gimple_convert (&stmts,
3641 TREE_TYPE (use_rhs),
3642 match_op[1]);
3643 var = gimple_build (&stmts, BIT_AND_EXPR,
3644 TREE_TYPE (use_rhs), use_rhs, match_op[1]);
3645 gsi = gsi_for_stmt (use_stmt);
3646 gsi_remove (&gsi, true);
3647 release_defs (use_stmt);
3648 use_stmt = gimple_seq_last_stmt (stmts);
3649 gsi = gsi_for_stmt (use_nop_stmt);
3650 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
3651 gimple_assign_set_rhs_with_ops (&gsi, CONVERT_EXPR, var);
3652 update_stmt (use_nop_stmt);
3653 }
3654 }
3655 else
3656 return false;
3657
3658 if (!bit)
3659 {
3660 if (ibit < 0)
3661 gcc_unreachable ();
3662 bit = build_int_cst (TREE_TYPE (lhs), ibit);
3663 }
3664 }
3665 else if (optab_handler (optab, TYPE_MODE (TREE_TYPE (lhs)))
3666 == CODE_FOR_nothing)
3667 return false;
3668
3669 tree use_lhs = gimple_assign_lhs (use_stmt);
3670 if (!use_lhs)
3671 return false;
3672
3673 if (!bit)
3674 {
3675 if (TREE_CODE (mask) == INTEGER_CST)
3676 {
3677 if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3678 mask = const_unop (BIT_NOT_EXPR, TREE_TYPE (mask), mask);
3679 mask = fold_convert (TREE_TYPE (lhs), mask);
3680 int ibit = tree_log2 (mask);
3681 if (ibit < 0)
3682 return false;
3683 bit = build_int_cst (TREE_TYPE (lhs), ibit);
3684 }
3685 else if (TREE_CODE (mask) == SSA_NAME)
3686 {
3687 gimple *g = SSA_NAME_DEF_STMT (mask);
3688 tree match_op;
3689 if (gimple_nop_convert (mask, &match_op, NULL))
3690 {
3691 mask = match_op;
3692 if (TREE_CODE (mask) != SSA_NAME)
3693 return false;
3694 g = SSA_NAME_DEF_STMT (mask);
3695 }
3696 if (!is_gimple_assign (g))
3697 return false;
3698
3699 if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3700 {
3701 if (gimple_assign_rhs_code (g) != BIT_NOT_EXPR)
3702 return false;
3703 mask = gimple_assign_rhs1 (g);
3704 if (TREE_CODE (mask) != SSA_NAME)
3705 return false;
3706 g = SSA_NAME_DEF_STMT (mask);
3707 }
3708
3709 if (!is_gimple_assign (g)
3710 || gimple_assign_rhs_code (g) != LSHIFT_EXPR
3711 || !integer_onep (gimple_assign_rhs1 (g)))
3712 return false;
3713 bit = gimple_assign_rhs2 (g);
3714 }
3715 else
3716 return false;
3717
3718 tree cmp_mask;
3719 if (gimple_assign_rhs1 (use_stmt) == lhs)
3720 cmp_mask = gimple_assign_rhs2 (use_stmt);
3721 else
3722 cmp_mask = gimple_assign_rhs1 (use_stmt);
3723
3724 tree match_op;
3725 if (gimple_nop_convert (cmp_mask, &match_op, NULL))
3726 cmp_mask = match_op;
3727
3728 if (!operand_equal_p (cmp_mask, mask, 0))
3729 return false;
3730 }
3731
3732 bool use_bool = true;
3733 bool has_debug_uses = false;
3734 imm_use_iterator iter;
3735 gimple *g;
3736
3737 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs))
3738 use_bool = false;
3739 FOR_EACH_IMM_USE_STMT (g, iter, use_lhs)
3740 {
3741 enum tree_code code = ERROR_MARK;
3742 tree op0 = NULL_TREE, op1 = NULL_TREE;
3743 if (is_gimple_debug (g))
3744 {
3745 has_debug_uses = true;
3746 continue;
3747 }
3748 else if (is_gimple_assign (g))
3749 switch (gimple_assign_rhs_code (g))
3750 {
3751 case COND_EXPR:
3752 op1 = gimple_assign_rhs1 (g);
3753 code = TREE_CODE (op1);
3754 if (TREE_CODE_CLASS (code) != tcc_comparison)
3755 break;
3756 op0 = TREE_OPERAND (op1, 0);
3757 op1 = TREE_OPERAND (op1, 1);
3758 break;
3759 case EQ_EXPR:
3760 case NE_EXPR:
3761 code = gimple_assign_rhs_code (g);
3762 op0 = gimple_assign_rhs1 (g);
3763 op1 = gimple_assign_rhs2 (g);
3764 break;
3765 default:
3766 break;
3767 }
3768 else if (gimple_code (g) == GIMPLE_COND)
3769 {
3770 code = gimple_cond_code (g);
3771 op0 = gimple_cond_lhs (g);
3772 op1 = gimple_cond_rhs (g);
3773 }
3774
3775 if ((code == EQ_EXPR || code == NE_EXPR)
3776 && op0 == use_lhs
3777 && integer_zerop (op1))
3778 {
3779 use_operand_p use_p;
3780 int n = 0;
3781 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3782 n++;
3783 if (n == 1)
3784 continue;
3785 }
3786
3787 use_bool = false;
3788 break;
3789 }
3790
3791 tree new_lhs = make_ssa_name (TREE_TYPE (lhs));
3792 tree flag = build_int_cst (TREE_TYPE (lhs), use_bool);
3793 if (has_model_arg)
3794 g = gimple_build_call_internal (fn, 5, gimple_call_arg (call, 0),
3795 bit, flag, gimple_call_arg (call, 2),
3796 gimple_call_fn (call));
3797 else
3798 g = gimple_build_call_internal (fn, 4, gimple_call_arg (call, 0),
3799 bit, flag, gimple_call_fn (call));
3800 gimple_call_set_lhs (g, new_lhs);
3801 gimple_set_location (g, gimple_location (call));
3802 gimple_move_vops (g, call);
3803 bool throws = stmt_can_throw_internal (cfun, call);
3804 gimple_call_set_nothrow (as_a <gcall *> (g),
3805 gimple_call_nothrow_p (as_a <gcall *> (call)));
3806 gimple_stmt_iterator gsi = *gsip;
3807 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3808 edge e = NULL;
3809 if (throws)
3810 {
3811 maybe_clean_or_replace_eh_stmt (call, g);
3812 if (after || (use_bool && has_debug_uses))
3813 e = find_fallthru_edge (gsi_bb (gsi)->succs);
3814 }
3815 if (after)
3816 {
3817 /* The internal function returns the value of the specified bit
3818 before the atomic operation. If we are interested in the value
3819 of the specified bit after the atomic operation (makes only sense
3820 for xor, otherwise the bit content is compile time known),
3821 we need to invert the bit. */
3822 tree mask_convert = mask;
3823 gimple_seq stmts = NULL;
3824 if (!use_bool)
3825 mask_convert = gimple_convert (&stmts, TREE_TYPE (lhs), mask);
3826 new_lhs = gimple_build (&stmts, BIT_XOR_EXPR, TREE_TYPE (lhs), new_lhs,
3827 use_bool ? build_int_cst (TREE_TYPE (lhs), 1)
3828 : mask_convert);
3829 if (throws)
3830 {
3831 gsi_insert_seq_on_edge_immediate (e, stmts);
3832 gsi = gsi_for_stmt (gimple_seq_last (stmts));
3833 }
3834 else
3835 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
3836 }
3837 if (use_bool && has_debug_uses)
3838 {
3839 tree temp = NULL_TREE;
3840 if (!throws || after || single_pred_p (e->dest))
3841 {
3842 temp = build_debug_expr_decl (TREE_TYPE (lhs));
3843 tree t = build2 (LSHIFT_EXPR, TREE_TYPE (lhs), new_lhs, bit);
3844 g = gimple_build_debug_bind (temp, t, g);
3845 if (throws && !after)
3846 {
3847 gsi = gsi_after_labels (e->dest);
3848 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3849 }
3850 else
3851 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3852 }
3853 FOR_EACH_IMM_USE_STMT (g, iter, use_lhs)
3854 if (is_gimple_debug (g))
3855 {
3856 use_operand_p use_p;
3857 if (temp == NULL_TREE)
3858 gimple_debug_bind_reset_value (g);
3859 else
3860 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3861 SET_USE (use_p, temp);
3862 update_stmt (g);
3863 }
3864 }
3865 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_lhs)
3866 = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs);
3867 replace_uses_by (use_lhs, new_lhs);
3868 gsi = gsi_for_stmt (use_stmt);
3869 gsi_remove (&gsi, true);
3870 release_defs (use_stmt);
3871 gsi_remove (gsip, true);
3872 release_ssa_name (lhs);
3873 return true;
3874 }
3875
3876 /* Optimize
3877 _4 = __atomic_add_fetch_* (ptr_6, arg_2, _3);
3878 _5 = _4 == 0;
3879 to
3880 _4 = .ATOMIC_ADD_FETCH_CMP_0 (EQ_EXPR, ptr_6, arg_2, _3);
3881 _5 = _4;
3882 Similarly for __sync_add_and_fetch_* (without the ", _3" part
3883 in there). */
3884
3885 static bool
optimize_atomic_op_fetch_cmp_0(gimple_stmt_iterator * gsip,enum internal_fn fn,bool has_model_arg)3886 optimize_atomic_op_fetch_cmp_0 (gimple_stmt_iterator *gsip,
3887 enum internal_fn fn, bool has_model_arg)
3888 {
3889 gimple *call = gsi_stmt (*gsip);
3890 tree lhs = gimple_call_lhs (call);
3891 use_operand_p use_p;
3892 gimple *use_stmt;
3893
3894 if (!flag_inline_atomics
3895 || optimize_debug
3896 || !gimple_call_builtin_p (call, BUILT_IN_NORMAL)
3897 || !lhs
3898 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
3899 || !single_imm_use (lhs, &use_p, &use_stmt)
3900 || !gimple_vdef (call))
3901 return false;
3902
3903 optab optab;
3904 switch (fn)
3905 {
3906 case IFN_ATOMIC_ADD_FETCH_CMP_0:
3907 optab = atomic_add_fetch_cmp_0_optab;
3908 break;
3909 case IFN_ATOMIC_SUB_FETCH_CMP_0:
3910 optab = atomic_sub_fetch_cmp_0_optab;
3911 break;
3912 case IFN_ATOMIC_AND_FETCH_CMP_0:
3913 optab = atomic_and_fetch_cmp_0_optab;
3914 break;
3915 case IFN_ATOMIC_OR_FETCH_CMP_0:
3916 optab = atomic_or_fetch_cmp_0_optab;
3917 break;
3918 case IFN_ATOMIC_XOR_FETCH_CMP_0:
3919 optab = atomic_xor_fetch_cmp_0_optab;
3920 break;
3921 default:
3922 return false;
3923 }
3924
3925 if (optab_handler (optab, TYPE_MODE (TREE_TYPE (lhs)))
3926 == CODE_FOR_nothing)
3927 return false;
3928
3929 tree use_lhs = lhs;
3930 if (gimple_assign_cast_p (use_stmt))
3931 {
3932 use_lhs = gimple_assign_lhs (use_stmt);
3933 if (!tree_nop_conversion_p (TREE_TYPE (use_lhs), TREE_TYPE (lhs))
3934 || (!INTEGRAL_TYPE_P (TREE_TYPE (use_lhs))
3935 && !POINTER_TYPE_P (TREE_TYPE (use_lhs)))
3936 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs)
3937 || !single_imm_use (use_lhs, &use_p, &use_stmt))
3938 return false;
3939 }
3940 enum tree_code code = ERROR_MARK;
3941 tree op0 = NULL_TREE, op1 = NULL_TREE;
3942 if (is_gimple_assign (use_stmt))
3943 switch (gimple_assign_rhs_code (use_stmt))
3944 {
3945 case COND_EXPR:
3946 op1 = gimple_assign_rhs1 (use_stmt);
3947 code = TREE_CODE (op1);
3948 if (TREE_CODE_CLASS (code) == tcc_comparison)
3949 {
3950 op0 = TREE_OPERAND (op1, 0);
3951 op1 = TREE_OPERAND (op1, 1);
3952 }
3953 break;
3954 default:
3955 code = gimple_assign_rhs_code (use_stmt);
3956 if (TREE_CODE_CLASS (code) == tcc_comparison)
3957 {
3958 op0 = gimple_assign_rhs1 (use_stmt);
3959 op1 = gimple_assign_rhs2 (use_stmt);
3960 }
3961 break;
3962 }
3963 else if (gimple_code (use_stmt) == GIMPLE_COND)
3964 {
3965 code = gimple_cond_code (use_stmt);
3966 op0 = gimple_cond_lhs (use_stmt);
3967 op1 = gimple_cond_rhs (use_stmt);
3968 }
3969
3970 switch (code)
3971 {
3972 case LT_EXPR:
3973 case LE_EXPR:
3974 case GT_EXPR:
3975 case GE_EXPR:
3976 if (!INTEGRAL_TYPE_P (TREE_TYPE (use_lhs))
3977 || TREE_CODE (TREE_TYPE (use_lhs)) == BOOLEAN_TYPE
3978 || TYPE_UNSIGNED (TREE_TYPE (use_lhs)))
3979 return false;
3980 /* FALLTHRU */
3981 case EQ_EXPR:
3982 case NE_EXPR:
3983 if (op0 == use_lhs && integer_zerop (op1))
3984 break;
3985 return false;
3986 default:
3987 return false;
3988 }
3989
3990 int encoded;
3991 switch (code)
3992 {
3993 /* Use special encoding of the operation. We want to also
3994 encode the mode in the first argument and for neither EQ_EXPR
3995 etc. nor EQ etc. we can rely it will fit into QImode. */
3996 case EQ_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_EQ; break;
3997 case NE_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_NE; break;
3998 case LT_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_LT; break;
3999 case LE_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_LE; break;
4000 case GT_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_GT; break;
4001 case GE_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_GE; break;
4002 default: gcc_unreachable ();
4003 }
4004
4005 tree new_lhs = make_ssa_name (boolean_type_node);
4006 gimple *g;
4007 tree flag = build_int_cst (TREE_TYPE (lhs), encoded);
4008 if (has_model_arg)
4009 g = gimple_build_call_internal (fn, 5, flag,
4010 gimple_call_arg (call, 0),
4011 gimple_call_arg (call, 1),
4012 gimple_call_arg (call, 2),
4013 gimple_call_fn (call));
4014 else
4015 g = gimple_build_call_internal (fn, 4, flag,
4016 gimple_call_arg (call, 0),
4017 gimple_call_arg (call, 1),
4018 gimple_call_fn (call));
4019 gimple_call_set_lhs (g, new_lhs);
4020 gimple_set_location (g, gimple_location (call));
4021 gimple_move_vops (g, call);
4022 bool throws = stmt_can_throw_internal (cfun, call);
4023 gimple_call_set_nothrow (as_a <gcall *> (g),
4024 gimple_call_nothrow_p (as_a <gcall *> (call)));
4025 gimple_stmt_iterator gsi = *gsip;
4026 gsi_insert_after (&gsi, g, GSI_SAME_STMT);
4027 if (throws)
4028 maybe_clean_or_replace_eh_stmt (call, g);
4029 if (is_gimple_assign (use_stmt))
4030 switch (gimple_assign_rhs_code (use_stmt))
4031 {
4032 case COND_EXPR:
4033 gimple_assign_set_rhs1 (use_stmt, new_lhs);
4034 break;
4035 default:
4036 gsi = gsi_for_stmt (use_stmt);
4037 if (tree ulhs = gimple_assign_lhs (use_stmt))
4038 if (useless_type_conversion_p (TREE_TYPE (ulhs),
4039 boolean_type_node))
4040 {
4041 gimple_assign_set_rhs_with_ops (&gsi, SSA_NAME, new_lhs);
4042 break;
4043 }
4044 gimple_assign_set_rhs_with_ops (&gsi, NOP_EXPR, new_lhs);
4045 break;
4046 }
4047 else if (gimple_code (use_stmt) == GIMPLE_COND)
4048 {
4049 gcond *use_cond = as_a <gcond *> (use_stmt);
4050 gimple_cond_set_code (use_cond, NE_EXPR);
4051 gimple_cond_set_lhs (use_cond, new_lhs);
4052 gimple_cond_set_rhs (use_cond, boolean_false_node);
4053 }
4054
4055 update_stmt (use_stmt);
4056 if (use_lhs != lhs)
4057 {
4058 gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (use_lhs));
4059 gsi_remove (&gsi, true);
4060 release_ssa_name (use_lhs);
4061 }
4062 gsi_remove (gsip, true);
4063 release_ssa_name (lhs);
4064 return true;
4065 }
4066
4067 /* Optimize
4068 a = {};
4069 b = a;
4070 into
4071 a = {};
4072 b = {};
4073 Similarly for memset (&a, ..., sizeof (a)); instead of a = {};
4074 and/or memcpy (&b, &a, sizeof (a)); instead of b = a; */
4075
4076 static void
optimize_memcpy(gimple_stmt_iterator * gsip,tree dest,tree src,tree len)4077 optimize_memcpy (gimple_stmt_iterator *gsip, tree dest, tree src, tree len)
4078 {
4079 gimple *stmt = gsi_stmt (*gsip);
4080 if (gimple_has_volatile_ops (stmt))
4081 return;
4082
4083 tree vuse = gimple_vuse (stmt);
4084 if (vuse == NULL)
4085 return;
4086
4087 gimple *defstmt = SSA_NAME_DEF_STMT (vuse);
4088 tree src2 = NULL_TREE, len2 = NULL_TREE;
4089 poly_int64 offset, offset2;
4090 tree val = integer_zero_node;
4091 if (gimple_store_p (defstmt)
4092 && gimple_assign_single_p (defstmt)
4093 && TREE_CODE (gimple_assign_rhs1 (defstmt)) == CONSTRUCTOR
4094 && !gimple_clobber_p (defstmt))
4095 src2 = gimple_assign_lhs (defstmt);
4096 else if (gimple_call_builtin_p (defstmt, BUILT_IN_MEMSET)
4097 && TREE_CODE (gimple_call_arg (defstmt, 0)) == ADDR_EXPR
4098 && TREE_CODE (gimple_call_arg (defstmt, 1)) == INTEGER_CST)
4099 {
4100 src2 = TREE_OPERAND (gimple_call_arg (defstmt, 0), 0);
4101 len2 = gimple_call_arg (defstmt, 2);
4102 val = gimple_call_arg (defstmt, 1);
4103 /* For non-0 val, we'd have to transform stmt from assignment
4104 into memset (only if dest is addressable). */
4105 if (!integer_zerop (val) && is_gimple_assign (stmt))
4106 src2 = NULL_TREE;
4107 }
4108
4109 if (src2 == NULL_TREE)
4110 return;
4111
4112 if (len == NULL_TREE)
4113 len = (TREE_CODE (src) == COMPONENT_REF
4114 ? DECL_SIZE_UNIT (TREE_OPERAND (src, 1))
4115 : TYPE_SIZE_UNIT (TREE_TYPE (src)));
4116 if (len2 == NULL_TREE)
4117 len2 = (TREE_CODE (src2) == COMPONENT_REF
4118 ? DECL_SIZE_UNIT (TREE_OPERAND (src2, 1))
4119 : TYPE_SIZE_UNIT (TREE_TYPE (src2)));
4120 if (len == NULL_TREE
4121 || !poly_int_tree_p (len)
4122 || len2 == NULL_TREE
4123 || !poly_int_tree_p (len2))
4124 return;
4125
4126 src = get_addr_base_and_unit_offset (src, &offset);
4127 src2 = get_addr_base_and_unit_offset (src2, &offset2);
4128 if (src == NULL_TREE
4129 || src2 == NULL_TREE
4130 || maybe_lt (offset, offset2))
4131 return;
4132
4133 if (!operand_equal_p (src, src2, 0))
4134 return;
4135
4136 /* [ src + offset2, src + offset2 + len2 - 1 ] is set to val.
4137 Make sure that
4138 [ src + offset, src + offset + len - 1 ] is a subset of that. */
4139 if (maybe_gt (wi::to_poly_offset (len) + (offset - offset2),
4140 wi::to_poly_offset (len2)))
4141 return;
4142
4143 if (dump_file && (dump_flags & TDF_DETAILS))
4144 {
4145 fprintf (dump_file, "Simplified\n ");
4146 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4147 fprintf (dump_file, "after previous\n ");
4148 print_gimple_stmt (dump_file, defstmt, 0, dump_flags);
4149 }
4150
4151 /* For simplicity, don't change the kind of the stmt,
4152 turn dest = src; into dest = {}; and memcpy (&dest, &src, len);
4153 into memset (&dest, val, len);
4154 In theory we could change dest = src into memset if dest
4155 is addressable (maybe beneficial if val is not 0), or
4156 memcpy (&dest, &src, len) into dest = {} if len is the size
4157 of dest, dest isn't volatile. */
4158 if (is_gimple_assign (stmt))
4159 {
4160 tree ctor = build_constructor (TREE_TYPE (dest), NULL);
4161 gimple_assign_set_rhs_from_tree (gsip, ctor);
4162 update_stmt (stmt);
4163 }
4164 else /* If stmt is memcpy, transform it into memset. */
4165 {
4166 gcall *call = as_a <gcall *> (stmt);
4167 tree fndecl = builtin_decl_implicit (BUILT_IN_MEMSET);
4168 gimple_call_set_fndecl (call, fndecl);
4169 gimple_call_set_fntype (call, TREE_TYPE (fndecl));
4170 gimple_call_set_arg (call, 1, val);
4171 update_stmt (stmt);
4172 }
4173
4174 if (dump_file && (dump_flags & TDF_DETAILS))
4175 {
4176 fprintf (dump_file, "into\n ");
4177 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4178 }
4179 }
4180
4181 /* A simple pass that attempts to fold all builtin functions. This pass
4182 is run after we've propagated as many constants as we can. */
4183
4184 namespace {
4185
4186 const pass_data pass_data_fold_builtins =
4187 {
4188 GIMPLE_PASS, /* type */
4189 "fab", /* name */
4190 OPTGROUP_NONE, /* optinfo_flags */
4191 TV_NONE, /* tv_id */
4192 ( PROP_cfg | PROP_ssa ), /* properties_required */
4193 0, /* properties_provided */
4194 0, /* properties_destroyed */
4195 0, /* todo_flags_start */
4196 TODO_update_ssa, /* todo_flags_finish */
4197 };
4198
4199 class pass_fold_builtins : public gimple_opt_pass
4200 {
4201 public:
pass_fold_builtins(gcc::context * ctxt)4202 pass_fold_builtins (gcc::context *ctxt)
4203 : gimple_opt_pass (pass_data_fold_builtins, ctxt)
4204 {}
4205
4206 /* opt_pass methods: */
clone()4207 opt_pass * clone () { return new pass_fold_builtins (m_ctxt); }
4208 virtual unsigned int execute (function *);
4209
4210 }; // class pass_fold_builtins
4211
4212 unsigned int
execute(function * fun)4213 pass_fold_builtins::execute (function *fun)
4214 {
4215 bool cfg_changed = false;
4216 basic_block bb;
4217 unsigned int todoflags = 0;
4218
4219 FOR_EACH_BB_FN (bb, fun)
4220 {
4221 gimple_stmt_iterator i;
4222 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
4223 {
4224 gimple *stmt, *old_stmt;
4225 tree callee;
4226 enum built_in_function fcode;
4227
4228 stmt = gsi_stmt (i);
4229
4230 if (gimple_code (stmt) != GIMPLE_CALL)
4231 {
4232 /* Remove all *ssaname_N ={v} {CLOBBER}; stmts,
4233 after the last GIMPLE DSE they aren't needed and might
4234 unnecessarily keep the SSA_NAMEs live. */
4235 if (gimple_clobber_p (stmt))
4236 {
4237 tree lhs = gimple_assign_lhs (stmt);
4238 if (TREE_CODE (lhs) == MEM_REF
4239 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
4240 {
4241 unlink_stmt_vdef (stmt);
4242 gsi_remove (&i, true);
4243 release_defs (stmt);
4244 continue;
4245 }
4246 }
4247 else if (gimple_assign_load_p (stmt) && gimple_store_p (stmt))
4248 optimize_memcpy (&i, gimple_assign_lhs (stmt),
4249 gimple_assign_rhs1 (stmt), NULL_TREE);
4250 gsi_next (&i);
4251 continue;
4252 }
4253
4254 callee = gimple_call_fndecl (stmt);
4255 if (!callee || !fndecl_built_in_p (callee, BUILT_IN_NORMAL))
4256 {
4257 gsi_next (&i);
4258 continue;
4259 }
4260
4261 fcode = DECL_FUNCTION_CODE (callee);
4262 if (fold_stmt (&i))
4263 ;
4264 else
4265 {
4266 tree result = NULL_TREE;
4267 switch (DECL_FUNCTION_CODE (callee))
4268 {
4269 case BUILT_IN_CONSTANT_P:
4270 /* Resolve __builtin_constant_p. If it hasn't been
4271 folded to integer_one_node by now, it's fairly
4272 certain that the value simply isn't constant. */
4273 result = integer_zero_node;
4274 break;
4275
4276 case BUILT_IN_ASSUME_ALIGNED:
4277 /* Remove __builtin_assume_aligned. */
4278 result = gimple_call_arg (stmt, 0);
4279 break;
4280
4281 case BUILT_IN_STACK_RESTORE:
4282 result = optimize_stack_restore (i);
4283 if (result)
4284 break;
4285 gsi_next (&i);
4286 continue;
4287
4288 case BUILT_IN_UNREACHABLE:
4289 if (optimize_unreachable (i))
4290 cfg_changed = true;
4291 break;
4292
4293 case BUILT_IN_ATOMIC_ADD_FETCH_1:
4294 case BUILT_IN_ATOMIC_ADD_FETCH_2:
4295 case BUILT_IN_ATOMIC_ADD_FETCH_4:
4296 case BUILT_IN_ATOMIC_ADD_FETCH_8:
4297 case BUILT_IN_ATOMIC_ADD_FETCH_16:
4298 optimize_atomic_op_fetch_cmp_0 (&i,
4299 IFN_ATOMIC_ADD_FETCH_CMP_0,
4300 true);
4301 break;
4302 case BUILT_IN_SYNC_ADD_AND_FETCH_1:
4303 case BUILT_IN_SYNC_ADD_AND_FETCH_2:
4304 case BUILT_IN_SYNC_ADD_AND_FETCH_4:
4305 case BUILT_IN_SYNC_ADD_AND_FETCH_8:
4306 case BUILT_IN_SYNC_ADD_AND_FETCH_16:
4307 optimize_atomic_op_fetch_cmp_0 (&i,
4308 IFN_ATOMIC_ADD_FETCH_CMP_0,
4309 false);
4310 break;
4311
4312 case BUILT_IN_ATOMIC_SUB_FETCH_1:
4313 case BUILT_IN_ATOMIC_SUB_FETCH_2:
4314 case BUILT_IN_ATOMIC_SUB_FETCH_4:
4315 case BUILT_IN_ATOMIC_SUB_FETCH_8:
4316 case BUILT_IN_ATOMIC_SUB_FETCH_16:
4317 optimize_atomic_op_fetch_cmp_0 (&i,
4318 IFN_ATOMIC_SUB_FETCH_CMP_0,
4319 true);
4320 break;
4321 case BUILT_IN_SYNC_SUB_AND_FETCH_1:
4322 case BUILT_IN_SYNC_SUB_AND_FETCH_2:
4323 case BUILT_IN_SYNC_SUB_AND_FETCH_4:
4324 case BUILT_IN_SYNC_SUB_AND_FETCH_8:
4325 case BUILT_IN_SYNC_SUB_AND_FETCH_16:
4326 optimize_atomic_op_fetch_cmp_0 (&i,
4327 IFN_ATOMIC_SUB_FETCH_CMP_0,
4328 false);
4329 break;
4330
4331 case BUILT_IN_ATOMIC_FETCH_OR_1:
4332 case BUILT_IN_ATOMIC_FETCH_OR_2:
4333 case BUILT_IN_ATOMIC_FETCH_OR_4:
4334 case BUILT_IN_ATOMIC_FETCH_OR_8:
4335 case BUILT_IN_ATOMIC_FETCH_OR_16:
4336 optimize_atomic_bit_test_and (&i,
4337 IFN_ATOMIC_BIT_TEST_AND_SET,
4338 true, false);
4339 break;
4340 case BUILT_IN_SYNC_FETCH_AND_OR_1:
4341 case BUILT_IN_SYNC_FETCH_AND_OR_2:
4342 case BUILT_IN_SYNC_FETCH_AND_OR_4:
4343 case BUILT_IN_SYNC_FETCH_AND_OR_8:
4344 case BUILT_IN_SYNC_FETCH_AND_OR_16:
4345 optimize_atomic_bit_test_and (&i,
4346 IFN_ATOMIC_BIT_TEST_AND_SET,
4347 false, false);
4348 break;
4349
4350 case BUILT_IN_ATOMIC_FETCH_XOR_1:
4351 case BUILT_IN_ATOMIC_FETCH_XOR_2:
4352 case BUILT_IN_ATOMIC_FETCH_XOR_4:
4353 case BUILT_IN_ATOMIC_FETCH_XOR_8:
4354 case BUILT_IN_ATOMIC_FETCH_XOR_16:
4355 optimize_atomic_bit_test_and
4356 (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, true, false);
4357 break;
4358 case BUILT_IN_SYNC_FETCH_AND_XOR_1:
4359 case BUILT_IN_SYNC_FETCH_AND_XOR_2:
4360 case BUILT_IN_SYNC_FETCH_AND_XOR_4:
4361 case BUILT_IN_SYNC_FETCH_AND_XOR_8:
4362 case BUILT_IN_SYNC_FETCH_AND_XOR_16:
4363 optimize_atomic_bit_test_and
4364 (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, false, false);
4365 break;
4366
4367 case BUILT_IN_ATOMIC_XOR_FETCH_1:
4368 case BUILT_IN_ATOMIC_XOR_FETCH_2:
4369 case BUILT_IN_ATOMIC_XOR_FETCH_4:
4370 case BUILT_IN_ATOMIC_XOR_FETCH_8:
4371 case BUILT_IN_ATOMIC_XOR_FETCH_16:
4372 if (optimize_atomic_bit_test_and
4373 (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, true, true))
4374 break;
4375 optimize_atomic_op_fetch_cmp_0 (&i,
4376 IFN_ATOMIC_XOR_FETCH_CMP_0,
4377 true);
4378 break;
4379 case BUILT_IN_SYNC_XOR_AND_FETCH_1:
4380 case BUILT_IN_SYNC_XOR_AND_FETCH_2:
4381 case BUILT_IN_SYNC_XOR_AND_FETCH_4:
4382 case BUILT_IN_SYNC_XOR_AND_FETCH_8:
4383 case BUILT_IN_SYNC_XOR_AND_FETCH_16:
4384 if (optimize_atomic_bit_test_and
4385 (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, false, true))
4386 break;
4387 optimize_atomic_op_fetch_cmp_0 (&i,
4388 IFN_ATOMIC_XOR_FETCH_CMP_0,
4389 false);
4390 break;
4391
4392 case BUILT_IN_ATOMIC_FETCH_AND_1:
4393 case BUILT_IN_ATOMIC_FETCH_AND_2:
4394 case BUILT_IN_ATOMIC_FETCH_AND_4:
4395 case BUILT_IN_ATOMIC_FETCH_AND_8:
4396 case BUILT_IN_ATOMIC_FETCH_AND_16:
4397 optimize_atomic_bit_test_and (&i,
4398 IFN_ATOMIC_BIT_TEST_AND_RESET,
4399 true, false);
4400 break;
4401 case BUILT_IN_SYNC_FETCH_AND_AND_1:
4402 case BUILT_IN_SYNC_FETCH_AND_AND_2:
4403 case BUILT_IN_SYNC_FETCH_AND_AND_4:
4404 case BUILT_IN_SYNC_FETCH_AND_AND_8:
4405 case BUILT_IN_SYNC_FETCH_AND_AND_16:
4406 optimize_atomic_bit_test_and (&i,
4407 IFN_ATOMIC_BIT_TEST_AND_RESET,
4408 false, false);
4409 break;
4410
4411 case BUILT_IN_ATOMIC_AND_FETCH_1:
4412 case BUILT_IN_ATOMIC_AND_FETCH_2:
4413 case BUILT_IN_ATOMIC_AND_FETCH_4:
4414 case BUILT_IN_ATOMIC_AND_FETCH_8:
4415 case BUILT_IN_ATOMIC_AND_FETCH_16:
4416 optimize_atomic_op_fetch_cmp_0 (&i,
4417 IFN_ATOMIC_AND_FETCH_CMP_0,
4418 true);
4419 break;
4420 case BUILT_IN_SYNC_AND_AND_FETCH_1:
4421 case BUILT_IN_SYNC_AND_AND_FETCH_2:
4422 case BUILT_IN_SYNC_AND_AND_FETCH_4:
4423 case BUILT_IN_SYNC_AND_AND_FETCH_8:
4424 case BUILT_IN_SYNC_AND_AND_FETCH_16:
4425 optimize_atomic_op_fetch_cmp_0 (&i,
4426 IFN_ATOMIC_AND_FETCH_CMP_0,
4427 false);
4428 break;
4429
4430 case BUILT_IN_ATOMIC_OR_FETCH_1:
4431 case BUILT_IN_ATOMIC_OR_FETCH_2:
4432 case BUILT_IN_ATOMIC_OR_FETCH_4:
4433 case BUILT_IN_ATOMIC_OR_FETCH_8:
4434 case BUILT_IN_ATOMIC_OR_FETCH_16:
4435 optimize_atomic_op_fetch_cmp_0 (&i,
4436 IFN_ATOMIC_OR_FETCH_CMP_0,
4437 true);
4438 break;
4439 case BUILT_IN_SYNC_OR_AND_FETCH_1:
4440 case BUILT_IN_SYNC_OR_AND_FETCH_2:
4441 case BUILT_IN_SYNC_OR_AND_FETCH_4:
4442 case BUILT_IN_SYNC_OR_AND_FETCH_8:
4443 case BUILT_IN_SYNC_OR_AND_FETCH_16:
4444 optimize_atomic_op_fetch_cmp_0 (&i,
4445 IFN_ATOMIC_OR_FETCH_CMP_0,
4446 false);
4447 break;
4448
4449 case BUILT_IN_MEMCPY:
4450 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
4451 && TREE_CODE (gimple_call_arg (stmt, 0)) == ADDR_EXPR
4452 && TREE_CODE (gimple_call_arg (stmt, 1)) == ADDR_EXPR
4453 && TREE_CODE (gimple_call_arg (stmt, 2)) == INTEGER_CST)
4454 {
4455 tree dest = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
4456 tree src = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
4457 tree len = gimple_call_arg (stmt, 2);
4458 optimize_memcpy (&i, dest, src, len);
4459 }
4460 break;
4461
4462 case BUILT_IN_VA_START:
4463 case BUILT_IN_VA_END:
4464 case BUILT_IN_VA_COPY:
4465 /* These shouldn't be folded before pass_stdarg. */
4466 result = optimize_stdarg_builtin (stmt);
4467 break;
4468
4469 default:;
4470 }
4471
4472 if (!result)
4473 {
4474 gsi_next (&i);
4475 continue;
4476 }
4477
4478 gimplify_and_update_call_from_tree (&i, result);
4479 }
4480
4481 todoflags |= TODO_update_address_taken;
4482
4483 if (dump_file && (dump_flags & TDF_DETAILS))
4484 {
4485 fprintf (dump_file, "Simplified\n ");
4486 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4487 }
4488
4489 old_stmt = stmt;
4490 stmt = gsi_stmt (i);
4491 update_stmt (stmt);
4492
4493 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
4494 && gimple_purge_dead_eh_edges (bb))
4495 cfg_changed = true;
4496
4497 if (dump_file && (dump_flags & TDF_DETAILS))
4498 {
4499 fprintf (dump_file, "to\n ");
4500 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4501 fprintf (dump_file, "\n");
4502 }
4503
4504 /* Retry the same statement if it changed into another
4505 builtin, there might be new opportunities now. */
4506 if (gimple_code (stmt) != GIMPLE_CALL)
4507 {
4508 gsi_next (&i);
4509 continue;
4510 }
4511 callee = gimple_call_fndecl (stmt);
4512 if (!callee
4513 || !fndecl_built_in_p (callee, fcode))
4514 gsi_next (&i);
4515 }
4516 }
4517
4518 /* Delete unreachable blocks. */
4519 if (cfg_changed)
4520 todoflags |= TODO_cleanup_cfg;
4521
4522 return todoflags;
4523 }
4524
4525 } // anon namespace
4526
4527 gimple_opt_pass *
make_pass_fold_builtins(gcc::context * ctxt)4528 make_pass_fold_builtins (gcc::context *ctxt)
4529 {
4530 return new pass_fold_builtins (ctxt);
4531 }
4532
4533 /* A simple pass that emits some warnings post IPA. */
4534
4535 namespace {
4536
4537 const pass_data pass_data_post_ipa_warn =
4538 {
4539 GIMPLE_PASS, /* type */
4540 "post_ipa_warn", /* name */
4541 OPTGROUP_NONE, /* optinfo_flags */
4542 TV_NONE, /* tv_id */
4543 ( PROP_cfg | PROP_ssa ), /* properties_required */
4544 0, /* properties_provided */
4545 0, /* properties_destroyed */
4546 0, /* todo_flags_start */
4547 0, /* todo_flags_finish */
4548 };
4549
4550 class pass_post_ipa_warn : public gimple_opt_pass
4551 {
4552 public:
pass_post_ipa_warn(gcc::context * ctxt)4553 pass_post_ipa_warn (gcc::context *ctxt)
4554 : gimple_opt_pass (pass_data_post_ipa_warn, ctxt)
4555 {}
4556
4557 /* opt_pass methods: */
clone()4558 opt_pass * clone () { return new pass_post_ipa_warn (m_ctxt); }
gate(function *)4559 virtual bool gate (function *) { return warn_nonnull != 0; }
4560 virtual unsigned int execute (function *);
4561
4562 }; // class pass_fold_builtins
4563
4564 unsigned int
execute(function * fun)4565 pass_post_ipa_warn::execute (function *fun)
4566 {
4567 basic_block bb;
4568
4569 FOR_EACH_BB_FN (bb, fun)
4570 {
4571 gimple_stmt_iterator gsi;
4572 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4573 {
4574 gimple *stmt = gsi_stmt (gsi);
4575 if (!is_gimple_call (stmt) || warning_suppressed_p (stmt, OPT_Wnonnull))
4576 continue;
4577
4578 tree fntype = gimple_call_fntype (stmt);
4579 bitmap nonnullargs = get_nonnull_args (fntype);
4580 if (!nonnullargs)
4581 continue;
4582
4583 tree fndecl = gimple_call_fndecl (stmt);
4584 const bool closure = fndecl && DECL_LAMBDA_FUNCTION_P (fndecl);
4585
4586 for (unsigned i = 0; i < gimple_call_num_args (stmt); i++)
4587 {
4588 tree arg = gimple_call_arg (stmt, i);
4589 if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE)
4590 continue;
4591 if (!integer_zerop (arg))
4592 continue;
4593 if (i == 0 && closure)
4594 /* Avoid warning for the first argument to lambda functions. */
4595 continue;
4596 if (!bitmap_empty_p (nonnullargs)
4597 && !bitmap_bit_p (nonnullargs, i))
4598 continue;
4599
4600 /* In C++ non-static member functions argument 0 refers
4601 to the implicit this pointer. Use the same one-based
4602 numbering for ordinary arguments. */
4603 unsigned argno = TREE_CODE (fntype) == METHOD_TYPE ? i : i + 1;
4604 location_t loc = (EXPR_HAS_LOCATION (arg)
4605 ? EXPR_LOCATION (arg)
4606 : gimple_location (stmt));
4607 auto_diagnostic_group d;
4608 if (argno == 0)
4609 {
4610 if (warning_at (loc, OPT_Wnonnull,
4611 "%qs pointer is null", "this")
4612 && fndecl)
4613 inform (DECL_SOURCE_LOCATION (fndecl),
4614 "in a call to non-static member function %qD",
4615 fndecl);
4616 continue;
4617 }
4618
4619 if (!warning_at (loc, OPT_Wnonnull,
4620 "argument %u null where non-null "
4621 "expected", argno))
4622 continue;
4623
4624 tree fndecl = gimple_call_fndecl (stmt);
4625 if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
4626 inform (loc, "in a call to built-in function %qD",
4627 fndecl);
4628 else if (fndecl)
4629 inform (DECL_SOURCE_LOCATION (fndecl),
4630 "in a call to function %qD declared %qs",
4631 fndecl, "nonnull");
4632 }
4633 BITMAP_FREE (nonnullargs);
4634 }
4635 }
4636 return 0;
4637 }
4638
4639 } // anon namespace
4640
4641 gimple_opt_pass *
make_pass_post_ipa_warn(gcc::context * ctxt)4642 make_pass_post_ipa_warn (gcc::context *ctxt)
4643 {
4644 return new pass_post_ipa_warn (ctxt);
4645 }
4646