Line data Source code
1 : /* Conditional constant propagation pass for the GNU compiler.
2 : Copyright (C) 2000-2026 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-iterator.h"
133 : #include "gimple-fold.h"
134 : #include "tree-eh.h"
135 : #include "gimplify.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 "sreal.h"
154 : #include "ipa-cp.h"
155 : #include "ipa-prop.h"
156 : #include "internal-fn.h"
157 : #include "gimple-range.h"
158 : #include "tree-ssa-strlen.h"
159 :
160 : /* Possible lattice values. */
161 : typedef enum
162 : {
163 : UNINITIALIZED,
164 : UNDEFINED,
165 : CONSTANT,
166 : VARYING
167 : } ccp_lattice_t;
168 :
169 771121986 : class ccp_prop_value_t {
170 : public:
171 : /* Lattice value. */
172 : ccp_lattice_t lattice_val;
173 :
174 : /* Propagated value. */
175 : tree value;
176 :
177 : /* Mask that applies to the propagated value during CCP. For X
178 : with a CONSTANT lattice value X & ~mask == value & ~mask. The
179 : zero bits in the mask cover constant values. The ones mean no
180 : information. */
181 : widest_int mask;
182 : };
183 :
184 5568786 : class ccp_propagate : public ssa_propagation_engine
185 : {
186 : public:
187 : enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) final override;
188 : enum ssa_prop_result visit_phi (gphi *) final override;
189 : };
190 :
191 : /* Array of propagated constant values. After propagation,
192 : CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
193 : the constant is held in an SSA name representing a memory store
194 : (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
195 : memory reference used to store (i.e., the LHS of the assignment
196 : doing the store). */
197 : static ccp_prop_value_t *const_val;
198 : static unsigned n_const_val;
199 :
200 : static void canonicalize_value (ccp_prop_value_t *);
201 : static void ccp_lattice_meet (ccp_prop_value_t *, ccp_prop_value_t *);
202 :
203 : /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
204 :
205 : static void
206 55 : dump_lattice_value (FILE *outf, const char *prefix, ccp_prop_value_t val)
207 : {
208 55 : switch (val.lattice_val)
209 : {
210 0 : case UNINITIALIZED:
211 0 : fprintf (outf, "%sUNINITIALIZED", prefix);
212 0 : break;
213 1 : case UNDEFINED:
214 1 : fprintf (outf, "%sUNDEFINED", prefix);
215 1 : break;
216 15 : case VARYING:
217 15 : fprintf (outf, "%sVARYING", prefix);
218 15 : break;
219 39 : case CONSTANT:
220 39 : if (TREE_CODE (val.value) != INTEGER_CST
221 39 : || val.mask == 0)
222 : {
223 36 : fprintf (outf, "%sCONSTANT ", prefix);
224 36 : print_generic_expr (outf, val.value, dump_flags);
225 : }
226 : else
227 : {
228 3 : widest_int cval = wi::bit_and_not (wi::to_widest (val.value),
229 3 : val.mask);
230 3 : fprintf (outf, "%sCONSTANT ", prefix);
231 3 : print_hex (cval, outf);
232 3 : fprintf (outf, " (");
233 3 : print_hex (val.mask, outf);
234 3 : fprintf (outf, ")");
235 3 : }
236 : break;
237 0 : default:
238 0 : gcc_unreachable ();
239 : }
240 55 : }
241 :
242 :
243 : /* Print lattice value VAL to stderr. */
244 :
245 : void debug_lattice_value (ccp_prop_value_t val);
246 :
247 : DEBUG_FUNCTION void
248 0 : debug_lattice_value (ccp_prop_value_t val)
249 : {
250 0 : dump_lattice_value (stderr, "", val);
251 0 : fprintf (stderr, "\n");
252 0 : }
253 :
254 : /* Extend NONZERO_BITS to a full mask, based on sgn. */
255 :
256 : static widest_int
257 50992629 : extend_mask (const wide_int &nonzero_bits, signop sgn)
258 : {
259 50992629 : return widest_int::from (nonzero_bits, sgn);
260 : }
261 :
262 : /* Compute a default value for variable VAR and store it in the
263 : CONST_VAL array. The following rules are used to get default
264 : values:
265 :
266 : 1- Global and static variables that are declared constant are
267 : considered CONSTANT.
268 :
269 : 2- Any other value is considered UNDEFINED. This is useful when
270 : considering PHI nodes. PHI arguments that are undefined do not
271 : change the constant value of the PHI node, which allows for more
272 : constants to be propagated.
273 :
274 : 3- Variables defined by statements other than assignments and PHI
275 : nodes are considered VARYING.
276 :
277 : 4- Initial values of variables that are not GIMPLE registers are
278 : considered VARYING. */
279 :
280 : static ccp_prop_value_t
281 10428642 : get_default_value (tree var)
282 : {
283 10428642 : ccp_prop_value_t val = { UNINITIALIZED, NULL_TREE, 0 };
284 10428642 : gimple *stmt;
285 :
286 10428642 : stmt = SSA_NAME_DEF_STMT (var);
287 :
288 10428642 : if (gimple_nop_p (stmt))
289 : {
290 : /* Variables defined by an empty statement are those used
291 : before being initialized. If VAR is a local variable, we
292 : can assume initially that it is UNDEFINED, otherwise we must
293 : consider it VARYING. */
294 9664550 : if (!virtual_operand_p (var)
295 9664550 : && SSA_NAME_VAR (var)
296 19329000 : && VAR_P (SSA_NAME_VAR (var)))
297 1551828 : val.lattice_val = UNDEFINED;
298 : else
299 : {
300 8112722 : val.lattice_val = VARYING;
301 8112722 : val.mask = -1;
302 8112722 : if (flag_tree_bit_ccp && !VECTOR_TYPE_P (TREE_TYPE (var)))
303 : {
304 7674862 : wide_int nonzero_bits = get_nonzero_bits (var);
305 7674862 : tree value;
306 7674862 : widest_int mask;
307 :
308 7674862 : if (SSA_NAME_VAR (var)
309 7674762 : && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
310 7611581 : && ipcp_get_parm_bits (SSA_NAME_VAR (var), &value, &mask))
311 : {
312 83473 : val.lattice_val = CONSTANT;
313 83473 : val.value = value;
314 83473 : widest_int ipa_value = wi::to_widest (value);
315 : /* Unknown bits from IPA CP must be equal to zero. */
316 83473 : gcc_assert (wi::bit_and (ipa_value, mask) == 0);
317 83473 : val.mask = mask;
318 83473 : if (nonzero_bits != -1)
319 66821 : val.mask &= extend_mask (nonzero_bits,
320 66821 : TYPE_SIGN (TREE_TYPE (var)));
321 83473 : }
322 7591389 : else if (nonzero_bits != -1)
323 : {
324 1843 : val.lattice_val = CONSTANT;
325 1843 : val.value = build_zero_cst (TREE_TYPE (var));
326 1843 : val.mask = extend_mask (nonzero_bits,
327 1843 : TYPE_SIGN (TREE_TYPE (var)));
328 : }
329 7675121 : }
330 : }
331 : }
332 764092 : else if (is_gimple_assign (stmt))
333 : {
334 658660 : tree cst;
335 658660 : if (gimple_assign_single_p (stmt)
336 298506 : && DECL_P (gimple_assign_rhs1 (stmt))
337 671174 : && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
338 : {
339 97 : val.lattice_val = CONSTANT;
340 97 : val.value = cst;
341 : }
342 : else
343 : {
344 : /* Any other variable defined by an assignment is considered
345 : UNDEFINED. */
346 658563 : val.lattice_val = UNDEFINED;
347 : }
348 : }
349 105432 : else if ((is_gimple_call (stmt)
350 24474 : && gimple_call_lhs (stmt) != NULL_TREE)
351 105432 : || gimple_code (stmt) == GIMPLE_PHI)
352 : {
353 : /* A variable defined by a call or a PHI node is considered
354 : UNDEFINED. */
355 105375 : val.lattice_val = UNDEFINED;
356 : }
357 : else
358 : {
359 : /* Otherwise, VAR will never take on a constant value. */
360 57 : val.lattice_val = VARYING;
361 57 : val.mask = -1;
362 : }
363 :
364 10428642 : return val;
365 : }
366 :
367 :
368 : /* Get the constant value associated with variable VAR. */
369 :
370 : static inline ccp_prop_value_t *
371 3016375514 : get_value (tree var)
372 : {
373 3016375514 : ccp_prop_value_t *val;
374 :
375 3016375514 : if (const_val == NULL
376 6032751028 : || SSA_NAME_VERSION (var) >= n_const_val)
377 : return NULL;
378 :
379 3016368813 : val = &const_val[SSA_NAME_VERSION (var)];
380 3016368813 : if (val->lattice_val == UNINITIALIZED)
381 10428642 : *val = get_default_value (var);
382 :
383 3016368813 : canonicalize_value (val);
384 :
385 3016368813 : return val;
386 : }
387 :
388 : /* Return the constant tree value associated with VAR. */
389 :
390 : static inline tree
391 2355620144 : get_constant_value (tree var)
392 : {
393 2355620144 : ccp_prop_value_t *val;
394 2355620144 : if (TREE_CODE (var) != SSA_NAME)
395 : {
396 1152 : if (is_gimple_min_invariant (var))
397 : return var;
398 : return NULL_TREE;
399 : }
400 2355618992 : val = get_value (var);
401 2355618992 : if (val
402 2355612501 : && val->lattice_val == CONSTANT
403 2802712116 : && (TREE_CODE (val->value) != INTEGER_CST
404 2316258916 : || val->mask == 0))
405 60962894 : return val->value;
406 : return NULL_TREE;
407 : }
408 :
409 : /* Sets the value associated with VAR to VARYING. */
410 :
411 : static inline void
412 59172496 : set_value_varying (tree var)
413 : {
414 59172496 : ccp_prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
415 :
416 59172496 : val->lattice_val = VARYING;
417 59172496 : val->value = NULL_TREE;
418 59172496 : val->mask = -1;
419 59172496 : }
420 :
421 : /* For integer constants, make sure to drop TREE_OVERFLOW. */
422 :
423 : static void
424 3427334091 : canonicalize_value (ccp_prop_value_t *val)
425 : {
426 3427334091 : if (val->lattice_val != CONSTANT)
427 : return;
428 :
429 1210110379 : if (TREE_OVERFLOW_P (val->value))
430 62 : val->value = drop_tree_overflow (val->value);
431 : }
432 :
433 : /* Return whether the lattice transition is valid. */
434 :
435 : static bool
436 262611924 : valid_lattice_transition (ccp_prop_value_t old_val, ccp_prop_value_t new_val)
437 : {
438 : /* Lattice transitions must always be monotonically increasing in
439 : value. */
440 262611924 : if (old_val.lattice_val < new_val.lattice_val)
441 : return true;
442 :
443 164309648 : if (old_val.lattice_val != new_val.lattice_val)
444 : return false;
445 :
446 164309648 : if (!old_val.value && !new_val.value)
447 : return true;
448 :
449 : /* Now both lattice values are CONSTANT. */
450 :
451 : /* Allow arbitrary copy changes as we might look through PHI <a_1, ...>
452 : when only a single copy edge is executable. */
453 164273590 : if (TREE_CODE (old_val.value) == SSA_NAME
454 36909 : && TREE_CODE (new_val.value) == SSA_NAME)
455 : return true;
456 :
457 : /* Allow transitioning from a constant to a copy. */
458 164236681 : if (is_gimple_min_invariant (old_val.value)
459 164236681 : && TREE_CODE (new_val.value) == SSA_NAME)
460 : return true;
461 :
462 : /* Allow transitioning from PHI <&x, not executable> == &x
463 : to PHI <&x, &y> == common alignment. */
464 164038025 : if (TREE_CODE (old_val.value) != INTEGER_CST
465 422880 : && TREE_CODE (new_val.value) == INTEGER_CST)
466 : return true;
467 :
468 : /* Bit-lattices have to agree in the still valid bits. */
469 163641056 : if (TREE_CODE (old_val.value) == INTEGER_CST
470 163615145 : && TREE_CODE (new_val.value) == INTEGER_CST)
471 327230290 : return (wi::bit_and_not (wi::to_widest (old_val.value), new_val.mask)
472 490845435 : == wi::bit_and_not (wi::to_widest (new_val.value), new_val.mask));
473 :
474 : /* Otherwise constant values have to agree. */
475 25911 : if (operand_equal_p (old_val.value, new_val.value, 0))
476 : return true;
477 :
478 : /* At least the kinds and types should agree now. */
479 0 : if (TREE_CODE (old_val.value) != TREE_CODE (new_val.value)
480 0 : || !types_compatible_p (TREE_TYPE (old_val.value),
481 0 : TREE_TYPE (new_val.value)))
482 0 : return false;
483 :
484 : /* For floats and !HONOR_NANS allow transitions from (partial) NaN
485 : to non-NaN. */
486 0 : tree type = TREE_TYPE (new_val.value);
487 0 : if (SCALAR_FLOAT_TYPE_P (type)
488 0 : && !HONOR_NANS (type))
489 : {
490 0 : if (REAL_VALUE_ISNAN (TREE_REAL_CST (old_val.value)))
491 : return true;
492 : }
493 0 : else if (VECTOR_FLOAT_TYPE_P (type)
494 0 : && !HONOR_NANS (type))
495 : {
496 0 : unsigned int count
497 0 : = tree_vector_builder::binary_encoded_nelts (old_val.value,
498 0 : new_val.value);
499 0 : for (unsigned int i = 0; i < count; ++i)
500 0 : if (!REAL_VALUE_ISNAN
501 : (TREE_REAL_CST (VECTOR_CST_ENCODED_ELT (old_val.value, i)))
502 0 : && !operand_equal_p (VECTOR_CST_ENCODED_ELT (old_val.value, i),
503 0 : VECTOR_CST_ENCODED_ELT (new_val.value, i), 0))
504 : return false;
505 : return true;
506 : }
507 0 : else if (COMPLEX_FLOAT_TYPE_P (type)
508 0 : && !HONOR_NANS (type))
509 : {
510 0 : if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_REALPART (old_val.value)))
511 0 : && !operand_equal_p (TREE_REALPART (old_val.value),
512 0 : TREE_REALPART (new_val.value), 0))
513 : return false;
514 0 : if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_IMAGPART (old_val.value)))
515 0 : && !operand_equal_p (TREE_IMAGPART (old_val.value),
516 0 : TREE_IMAGPART (new_val.value), 0))
517 : return false;
518 0 : return true;
519 : }
520 : return false;
521 : }
522 :
523 : /* Set the value for variable VAR to NEW_VAL. Return true if the new
524 : value is different from VAR's previous value. */
525 :
526 : static bool
527 262611924 : set_lattice_value (tree var, ccp_prop_value_t *new_val)
528 : {
529 : /* We can deal with old UNINITIALIZED values just fine here. */
530 262611924 : ccp_prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
531 :
532 262611924 : canonicalize_value (new_val);
533 :
534 : /* We have to be careful to not go up the bitwise lattice
535 : represented by the mask. Instead of dropping to VARYING
536 : use the meet operator to retain a conservative value.
537 : Missed optimizations like PR65851 makes this necessary.
538 : It also ensures we converge to a stable lattice solution. */
539 262611924 : if (old_val->lattice_val != UNINITIALIZED
540 : /* But avoid using meet for constant -> copy transitions. */
541 170451835 : && !(old_val->lattice_val == CONSTANT
542 170371889 : && CONSTANT_CLASS_P (old_val->value)
543 167525226 : && new_val->lattice_val == CONSTANT
544 163821781 : && TREE_CODE (new_val->value) == SSA_NAME))
545 170253179 : ccp_lattice_meet (new_val, old_val);
546 :
547 525223848 : gcc_checking_assert (valid_lattice_transition (*old_val, *new_val));
548 :
549 : /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
550 : caller that this was a non-transition. */
551 525223848 : if (old_val->lattice_val != new_val->lattice_val
552 262611924 : || (new_val->lattice_val == CONSTANT
553 164273590 : && (TREE_CODE (new_val->value) != TREE_CODE (old_val->value)
554 163677965 : || (TREE_CODE (new_val->value) == INTEGER_CST
555 163615145 : && (new_val->mask != old_val->mask
556 46119012 : || (wi::bit_and_not (wi::to_widest (old_val->value),
557 : new_val->mask)
558 308668116 : != wi::bit_and_not (wi::to_widest (new_val->value),
559 : new_val->mask))))
560 15414884 : || (TREE_CODE (new_val->value) != INTEGER_CST
561 62820 : && !operand_equal_p (new_val->value, old_val->value, 0)))))
562 : {
563 : /* ??? We would like to delay creation of INTEGER_CSTs from
564 : partially constants here. */
565 :
566 247160982 : if (dump_file && (dump_flags & TDF_DETAILS))
567 : {
568 51 : dump_lattice_value (dump_file, "Lattice value changed to ", *new_val);
569 51 : fprintf (dump_file, ". Adding SSA edges to worklist.\n");
570 : }
571 :
572 247160982 : *old_val = *new_val;
573 :
574 247160982 : gcc_assert (new_val->lattice_val != UNINITIALIZED);
575 : return true;
576 : }
577 :
578 : return false;
579 : }
580 :
581 : static ccp_prop_value_t get_value_for_expr (tree, bool);
582 : static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
583 : void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *,
584 : signop, int, const widest_int &, const widest_int &,
585 : signop, int, const widest_int &, const widest_int &);
586 :
587 : /* Return a widest_int that can be used for bitwise simplifications
588 : from VAL. */
589 :
590 : static widest_int
591 314423103 : value_to_wide_int (ccp_prop_value_t val)
592 : {
593 314423103 : if (val.value
594 249683153 : && TREE_CODE (val.value) == INTEGER_CST)
595 249683153 : return wi::to_widest (val.value);
596 :
597 64739950 : return 0;
598 : }
599 :
600 : /* Return the value for the address expression EXPR based on alignment
601 : information. */
602 :
603 : static ccp_prop_value_t
604 8590456 : get_value_from_alignment (tree expr)
605 : {
606 8590456 : tree type = TREE_TYPE (expr);
607 8590456 : ccp_prop_value_t val;
608 8590456 : unsigned HOST_WIDE_INT bitpos;
609 8590456 : unsigned int align;
610 :
611 8590456 : gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
612 :
613 8590456 : get_pointer_alignment_1 (expr, &align, &bitpos);
614 8590456 : val.mask = wi::bit_and_not
615 17180912 : (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
616 8590456 : ? wi::mask <widest_int> (TYPE_PRECISION (type), false)
617 0 : : -1,
618 17180912 : align / BITS_PER_UNIT - 1);
619 8590456 : val.lattice_val
620 14589503 : = wi::sext (val.mask, TYPE_PRECISION (type)) == -1 ? VARYING : CONSTANT;
621 8590456 : if (val.lattice_val == CONSTANT)
622 5999047 : val.value = build_int_cstu (type, bitpos / BITS_PER_UNIT);
623 : else
624 2591409 : val.value = NULL_TREE;
625 :
626 8590456 : return val;
627 : }
628 :
629 : /* Return the value for the tree operand EXPR. If FOR_BITS_P is true
630 : return constant bits extracted from alignment information for
631 : invariant addresses. */
632 :
633 : static ccp_prop_value_t
634 485688411 : get_value_for_expr (tree expr, bool for_bits_p)
635 : {
636 485688411 : ccp_prop_value_t val;
637 :
638 485688411 : if (TREE_CODE (expr) == SSA_NAME)
639 : {
640 303217381 : ccp_prop_value_t *val_ = get_value (expr);
641 303217381 : if (val_)
642 303217276 : val = *val_;
643 : else
644 : {
645 105 : val.lattice_val = VARYING;
646 105 : val.value = NULL_TREE;
647 105 : val.mask = -1;
648 : }
649 303217381 : if (for_bits_p
650 206284883 : && val.lattice_val == CONSTANT)
651 : {
652 142010057 : if (TREE_CODE (val.value) == ADDR_EXPR)
653 208982 : val = get_value_from_alignment (val.value);
654 141801075 : else if (TREE_CODE (val.value) != INTEGER_CST)
655 : {
656 7517129 : val.lattice_val = VARYING;
657 7517129 : val.value = NULL_TREE;
658 7517129 : val.mask = -1;
659 : }
660 : }
661 : /* Fall back to a copy value. */
662 96932498 : if (!for_bits_p
663 96932498 : && val.lattice_val == VARYING
664 9359596 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr))
665 : {
666 9354567 : val.lattice_val = CONSTANT;
667 9354567 : val.value = expr;
668 9354567 : val.mask = -1;
669 : }
670 : }
671 182471030 : else if (is_gimple_min_invariant (expr)
672 182471030 : && (!for_bits_p || TREE_CODE (expr) == INTEGER_CST))
673 : {
674 148353354 : val.lattice_val = CONSTANT;
675 148353354 : val.value = expr;
676 148353354 : val.mask = 0;
677 148353354 : canonicalize_value (&val);
678 : }
679 34117676 : else if (TREE_CODE (expr) == ADDR_EXPR)
680 8381474 : val = get_value_from_alignment (expr);
681 : else
682 : {
683 25736202 : val.lattice_val = VARYING;
684 25736202 : val.mask = -1;
685 25736202 : val.value = NULL_TREE;
686 : }
687 :
688 485688411 : if (val.lattice_val == VARYING
689 99984532 : && INTEGRAL_TYPE_P (TREE_TYPE (expr))
690 553881635 : && TYPE_UNSIGNED (TREE_TYPE (expr)))
691 33523583 : val.mask = wi::zext (val.mask, TYPE_PRECISION (TREE_TYPE (expr)));
692 :
693 485688411 : return val;
694 : }
695 :
696 : /* Return the likely CCP lattice value for STMT.
697 :
698 : If STMT has no operands, then return CONSTANT.
699 :
700 : Else if undefinedness of operands of STMT cause its value to be
701 : undefined, then return UNDEFINED.
702 :
703 : Else if any operands of STMT are constants, then return CONSTANT.
704 :
705 : Else return VARYING. */
706 :
707 : static ccp_lattice_t
708 237539959 : likely_value (gimple *stmt)
709 : {
710 237539959 : bool has_constant_operand, has_undefined_operand, all_undefined_operands;
711 237539959 : bool has_nsa_operand;
712 237539959 : tree use;
713 237539959 : ssa_op_iter iter;
714 237539959 : unsigned i;
715 :
716 237539959 : enum gimple_code code = gimple_code (stmt);
717 :
718 : /* This function appears to be called only for assignments, calls,
719 : conditionals, and switches, due to the logic in visit_stmt. */
720 237539959 : gcc_assert (code == GIMPLE_ASSIGN
721 : || code == GIMPLE_CALL
722 : || code == GIMPLE_COND
723 : || code == GIMPLE_SWITCH);
724 :
725 : /* If the statement has volatile operands, it won't fold to a
726 : constant value. */
727 432836495 : if (gimple_has_volatile_ops (stmt))
728 : return VARYING;
729 :
730 : /* .DEFERRED_INIT produces undefined. */
731 237539894 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
732 : return UNDEFINED;
733 :
734 : /* Arrive here for more complex cases. */
735 237510268 : has_constant_operand = false;
736 237510268 : has_undefined_operand = false;
737 237510268 : all_undefined_operands = true;
738 237510268 : has_nsa_operand = false;
739 487080896 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
740 : {
741 249570628 : ccp_prop_value_t *val = get_value (use);
742 :
743 249570628 : if (val && val->lattice_val == UNDEFINED)
744 : has_undefined_operand = true;
745 : else
746 249233727 : all_undefined_operands = false;
747 :
748 249570523 : if (val && val->lattice_val == CONSTANT)
749 159391245 : has_constant_operand = true;
750 :
751 249570628 : if (SSA_NAME_IS_DEFAULT_DEF (use)
752 249570628 : || !prop_simulate_again_p (SSA_NAME_DEF_STMT (use)))
753 : has_nsa_operand = true;
754 : }
755 :
756 : /* There may be constants in regular rhs operands. For calls we
757 : have to ignore lhs, fndecl and static chain, otherwise only
758 : the lhs. */
759 475020536 : for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
760 718203975 : i < gimple_num_ops (stmt); ++i)
761 : {
762 480693707 : tree op = gimple_op (stmt, i);
763 480693707 : if (!op || TREE_CODE (op) == SSA_NAME)
764 313027602 : continue;
765 167666105 : if (is_gimple_min_invariant (op))
766 : has_constant_operand = true;
767 32219693 : else if (TREE_CODE (op) == CONSTRUCTOR)
768 : {
769 : unsigned j;
770 : tree val;
771 481226973 : FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (op), j, val)
772 533266 : if (CONSTANT_CLASS_P (val))
773 : {
774 : has_constant_operand = true;
775 : break;
776 : }
777 : }
778 : }
779 :
780 237510268 : if (has_constant_operand)
781 187538731 : all_undefined_operands = false;
782 :
783 237510268 : if (has_undefined_operand
784 237510268 : && code == GIMPLE_CALL
785 237510268 : && gimple_call_internal_p (stmt))
786 20151 : switch (gimple_call_internal_fn (stmt))
787 : {
788 : /* These 3 builtins use the first argument just as a magic
789 : way how to find out a decl uid. */
790 : case IFN_GOMP_SIMD_LANE:
791 : case IFN_GOMP_SIMD_VF:
792 : case IFN_GOMP_SIMD_LAST_LANE:
793 : has_undefined_operand = false;
794 : break;
795 : default:
796 : break;
797 : }
798 :
799 : /* If the operation combines operands like COMPLEX_EXPR make sure to
800 : not mark the result UNDEFINED if only one part of the result is
801 : undefined. */
802 237490213 : if (has_undefined_operand && all_undefined_operands)
803 : return UNDEFINED;
804 237429765 : else if (code == GIMPLE_ASSIGN && has_undefined_operand)
805 : {
806 62420 : switch (gimple_assign_rhs_code (stmt))
807 : {
808 : /* Unary operators are handled with all_undefined_operands. */
809 : case PLUS_EXPR:
810 : case MINUS_EXPR:
811 : case POINTER_PLUS_EXPR:
812 : case BIT_XOR_EXPR:
813 : /* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected.
814 : Not bitwise operators, one VARYING operand may specify the
815 : result completely.
816 : Not logical operators for the same reason, apart from XOR.
817 : Not COMPLEX_EXPR as one VARYING operand makes the result partly
818 : not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because
819 : the undefined operand may be promoted. */
820 : return UNDEFINED;
821 :
822 : case ADDR_EXPR:
823 : /* If any part of an address is UNDEFINED, like the index
824 : of an ARRAY_EXPR, then treat the result as UNDEFINED. */
825 : return UNDEFINED;
826 :
827 : default:
828 : ;
829 : }
830 : }
831 : /* If there was an UNDEFINED operand but the result may be not UNDEFINED
832 : fall back to CONSTANT. During iteration UNDEFINED may still drop
833 : to CONSTANT. */
834 237387791 : if (has_undefined_operand)
835 : return CONSTANT;
836 :
837 : /* We do not consider virtual operands here -- load from read-only
838 : memory may have only VARYING virtual operands, but still be
839 : constant. Also we can combine the stmt with definitions from
840 : operands whose definitions are not simulated again. */
841 237216343 : if (has_constant_operand
842 237216343 : || has_nsa_operand
843 237216343 : || gimple_references_memory_p (stmt))
844 : return CONSTANT;
845 :
846 : return VARYING;
847 : }
848 :
849 : /* Returns true if STMT cannot be constant. */
850 :
851 : static bool
852 322618927 : surely_varying_stmt_p (gimple *stmt)
853 : {
854 : /* If the statement has operands that we cannot handle, it cannot be
855 : constant. */
856 456744454 : if (gimple_has_volatile_ops (stmt))
857 : return true;
858 :
859 : /* If it is a call and does not return a value or is not a
860 : builtin and not an indirect call or a call to function with
861 : assume_aligned/alloc_align attribute, it is varying. */
862 313455415 : if (is_gimple_call (stmt))
863 : {
864 16679556 : tree fndecl, fntype = gimple_call_fntype (stmt);
865 16679556 : if (!gimple_call_lhs (stmt)
866 16679556 : || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
867 6745951 : && !fndecl_built_in_p (fndecl)
868 3966746 : && !lookup_attribute ("assume_aligned",
869 3966746 : TYPE_ATTRIBUTES (fntype))
870 3966704 : && !lookup_attribute ("alloc_align",
871 3966704 : TYPE_ATTRIBUTES (fntype))))
872 12973449 : return true;
873 : }
874 :
875 : /* Any other store operation is not interesting. */
876 405058318 : else if (gimple_vdef (stmt))
877 : return true;
878 :
879 : /* Anything other than assignments and conditional jumps are not
880 : interesting for CCP. */
881 270908373 : if (gimple_code (stmt) != GIMPLE_ASSIGN
882 : && gimple_code (stmt) != GIMPLE_COND
883 : && gimple_code (stmt) != GIMPLE_SWITCH
884 : && gimple_code (stmt) != GIMPLE_CALL)
885 : return true;
886 :
887 : return false;
888 : }
889 :
890 : /* Initialize local data structures for CCP. */
891 :
892 : static void
893 5568786 : ccp_initialize (void)
894 : {
895 5568786 : basic_block bb;
896 :
897 5568786 : n_const_val = num_ssa_names;
898 5568786 : const_val = XCNEWVEC (ccp_prop_value_t, n_const_val);
899 :
900 : /* Initialize simulation flags for PHI nodes and statements. */
901 51946664 : FOR_EACH_BB_FN (bb, cfun)
902 : {
903 46377878 : gimple_stmt_iterator i;
904 :
905 448499361 : for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
906 : {
907 355743605 : gimple *stmt = gsi_stmt (i);
908 355743605 : bool is_varying;
909 :
910 : /* If the statement is a control insn, then we do not
911 : want to avoid simulating the statement once. Failure
912 : to do so means that those edges will never get added. */
913 355743605 : if (stmt_ends_bb_p (stmt))
914 : is_varying = false;
915 : else
916 322618927 : is_varying = surely_varying_stmt_p (stmt);
917 :
918 322618927 : if (is_varying)
919 : {
920 240382209 : tree def;
921 240382209 : ssa_op_iter iter;
922 :
923 : /* If the statement will not produce a constant, mark
924 : all its outputs VARYING. */
925 294886308 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
926 54504099 : set_value_varying (def);
927 : }
928 355743605 : prop_set_simulate_again (stmt, !is_varying);
929 : }
930 : }
931 :
932 : /* Now process PHI nodes. We never clear the simulate_again flag on
933 : phi nodes, since we do not know which edges are executable yet,
934 : except for phi nodes for virtual operands when we do not do store ccp. */
935 51946664 : FOR_EACH_BB_FN (bb, cfun)
936 : {
937 46377878 : gphi_iterator i;
938 :
939 63575159 : for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
940 : {
941 17197281 : gphi *phi = i.phi ();
942 :
943 34394562 : if (virtual_operand_p (gimple_phi_result (phi)))
944 7844578 : prop_set_simulate_again (phi, false);
945 : else
946 9352703 : prop_set_simulate_again (phi, true);
947 : }
948 : }
949 5568786 : }
950 :
951 : /* Debug count support. Reset the values of ssa names
952 : VARYING when the total number ssa names analyzed is
953 : beyond the debug count specified. */
954 :
955 : static void
956 5568786 : do_dbg_cnt (void)
957 : {
958 5568786 : unsigned i;
959 224376386 : for (i = 0; i < num_ssa_names; i++)
960 : {
961 218807600 : if (!dbg_cnt (ccp))
962 : {
963 0 : const_val[i].lattice_val = VARYING;
964 0 : const_val[i].mask = -1;
965 0 : const_val[i].value = NULL_TREE;
966 : }
967 : }
968 5568786 : }
969 :
970 :
971 : /* We want to provide our own GET_VALUE and FOLD_STMT virtual methods. */
972 22275144 : class ccp_folder : public substitute_and_fold_engine
973 : {
974 : public:
975 : tree value_of_expr (tree, gimple *) final override;
976 : bool fold_stmt (gimple_stmt_iterator *) final override;
977 : };
978 :
979 : /* This method just wraps GET_CONSTANT_VALUE for now. Over time
980 : naked calls to GET_CONSTANT_VALUE should be eliminated in favor
981 : of calling member functions. */
982 :
983 : tree
984 297278119 : ccp_folder::value_of_expr (tree op, gimple *)
985 : {
986 297278119 : return get_constant_value (op);
987 : }
988 :
989 : /* Do final substitution of propagated values, cleanup the flowgraph and
990 : free allocated storage. If NONZERO_P, record nonzero bits.
991 :
992 : Return TRUE when something was optimized. */
993 :
994 : static bool
995 5568786 : ccp_finalize (bool nonzero_p)
996 : {
997 5568786 : bool something_changed;
998 5568786 : unsigned i;
999 5568786 : tree name;
1000 :
1001 5568786 : do_dbg_cnt ();
1002 :
1003 : /* Derive alignment and misalignment information from partially
1004 : constant pointers in the lattice or nonzero bits from partially
1005 : constant integers. */
1006 218807600 : FOR_EACH_SSA_NAME (i, name, cfun)
1007 : {
1008 178563099 : ccp_prop_value_t *val;
1009 178563099 : unsigned int tem, align;
1010 :
1011 325709202 : if (!POINTER_TYPE_P (TREE_TYPE (name))
1012 322693086 : && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
1013 : /* Don't record nonzero bits before IPA to avoid
1014 : using too much memory. */
1015 63130308 : || !nonzero_p))
1016 82847660 : continue;
1017 :
1018 95715439 : val = get_value (name);
1019 176724458 : if (val->lattice_val != CONSTANT
1020 26759496 : || TREE_CODE (val->value) != INTEGER_CST
1021 113874249 : || val->mask == 0)
1022 81009019 : continue;
1023 :
1024 14706420 : if (POINTER_TYPE_P (TREE_TYPE (name)))
1025 : {
1026 : /* Trailing mask bits specify the alignment, trailing value
1027 : bits the misalignment. */
1028 1391340 : tem = val->mask.to_uhwi ();
1029 1391340 : align = least_bit_hwi (tem);
1030 1391340 : if (align > 1)
1031 1331823 : set_ptr_info_alignment (get_ptr_info (name), align,
1032 1331823 : (TREE_INT_CST_LOW (val->value)
1033 1331823 : & (align - 1)));
1034 : }
1035 : else
1036 : {
1037 13315080 : unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
1038 13315080 : wide_int value = wi::to_wide (val->value);
1039 13315080 : wide_int mask = wide_int::from (val->mask, precision, UNSIGNED);
1040 13315376 : value = value & ~mask;
1041 13315080 : set_bitmask (name, value, mask);
1042 13315376 : }
1043 : }
1044 :
1045 : /* Perform substitutions based on the known constant values. */
1046 5568786 : class ccp_folder ccp_folder;
1047 5568786 : something_changed = ccp_folder.substitute_and_fold ();
1048 :
1049 5568786 : free (const_val);
1050 5568786 : const_val = NULL;
1051 5568786 : return something_changed;
1052 5568786 : }
1053 :
1054 :
1055 : /* Compute the meet operator between *VAL1 and *VAL2. Store the result
1056 : in VAL1.
1057 :
1058 : any M UNDEFINED = any
1059 : any M VARYING = VARYING
1060 : Ci M Cj = Ci if (i == j)
1061 : Ci M Cj = VARYING if (i != j)
1062 : */
1063 :
1064 : static void
1065 234980837 : ccp_lattice_meet (ccp_prop_value_t *val1, ccp_prop_value_t *val2)
1066 : {
1067 234980837 : if (val1->lattice_val == UNDEFINED
1068 : /* For UNDEFINED M SSA we can't always SSA because its definition
1069 : may not dominate the PHI node. Doing optimistic copy propagation
1070 : also causes a lot of gcc.dg/uninit-pred*.c FAILs. */
1071 172870 : && (val2->lattice_val != CONSTANT
1072 96888 : || TREE_CODE (val2->value) != SSA_NAME))
1073 : {
1074 : /* UNDEFINED M any = any */
1075 97069 : *val1 = *val2;
1076 : }
1077 234883768 : else if (val2->lattice_val == UNDEFINED
1078 : /* See above. */
1079 93580 : && (val1->lattice_val != CONSTANT
1080 59871 : || TREE_CODE (val1->value) != SSA_NAME))
1081 : {
1082 : /* any M UNDEFINED = any
1083 : Nothing to do. VAL1 already contains the value we want. */
1084 : ;
1085 : }
1086 234813837 : else if (val1->lattice_val == VARYING
1087 228878249 : || val2->lattice_val == VARYING)
1088 : {
1089 : /* any M VARYING = VARYING. */
1090 5951278 : val1->lattice_val = VARYING;
1091 5951278 : val1->mask = -1;
1092 5951278 : val1->value = NULL_TREE;
1093 : }
1094 228862559 : else if (val1->lattice_val == CONSTANT
1095 228786758 : && val2->lattice_val == CONSTANT
1096 228763109 : && TREE_CODE (val1->value) == INTEGER_CST
1097 223859254 : && TREE_CODE (val2->value) == INTEGER_CST)
1098 : {
1099 : /* Ci M Cj = Ci if (i == j)
1100 : Ci M Cj = VARYING if (i != j)
1101 :
1102 : For INTEGER_CSTs mask unequal bits. If no equal bits remain,
1103 : drop to varying. */
1104 443789206 : val1->mask = (val1->mask | val2->mask
1105 443789206 : | (wi::to_widest (val1->value)
1106 665683809 : ^ wi::to_widest (val2->value)));
1107 221894603 : if (wi::sext (val1->mask, TYPE_PRECISION (TREE_TYPE (val1->value))) == -1)
1108 : {
1109 505172 : val1->lattice_val = VARYING;
1110 505172 : val1->value = NULL_TREE;
1111 : }
1112 : }
1113 6967956 : else if (val1->lattice_val == CONSTANT
1114 6892155 : && val2->lattice_val == CONSTANT
1115 13836462 : && operand_equal_p (val1->value, val2->value, 0))
1116 : {
1117 : /* Ci M Cj = Ci if (i == j)
1118 : Ci M Cj = VARYING if (i != j)
1119 :
1120 : VAL1 already contains the value we want for equivalent values. */
1121 : }
1122 6564407 : else if (val1->lattice_val == CONSTANT
1123 6488606 : && val2->lattice_val == CONSTANT
1124 6464957 : && (TREE_CODE (val1->value) == ADDR_EXPR
1125 6272038 : || TREE_CODE (val2->value) == ADDR_EXPR))
1126 : {
1127 : /* When not equal addresses are involved try meeting for
1128 : alignment. */
1129 713619 : ccp_prop_value_t tem = *val2;
1130 713619 : if (TREE_CODE (val1->value) == ADDR_EXPR)
1131 192919 : *val1 = get_value_for_expr (val1->value, true);
1132 713619 : if (TREE_CODE (val2->value) == ADDR_EXPR)
1133 618356 : tem = get_value_for_expr (val2->value, true);
1134 713619 : ccp_lattice_meet (val1, &tem);
1135 713619 : }
1136 : else
1137 : {
1138 : /* Any other combination is VARYING. */
1139 5850788 : val1->lattice_val = VARYING;
1140 5850788 : val1->mask = -1;
1141 5850788 : val1->value = NULL_TREE;
1142 : }
1143 234980837 : }
1144 :
1145 :
1146 : /* Loop through the PHI_NODE's parameters for BLOCK and compare their
1147 : lattice values to determine PHI_NODE's lattice value. The value of a
1148 : PHI node is determined calling ccp_lattice_meet with all the arguments
1149 : of the PHI node that are incoming via executable edges. */
1150 :
1151 : enum ssa_prop_result
1152 67315388 : ccp_propagate::visit_phi (gphi *phi)
1153 : {
1154 67315388 : unsigned i;
1155 67315388 : ccp_prop_value_t new_val;
1156 :
1157 67315388 : if (dump_file && (dump_flags & TDF_DETAILS))
1158 : {
1159 1 : fprintf (dump_file, "\nVisiting PHI node: ");
1160 1 : print_gimple_stmt (dump_file, phi, 0, dump_flags);
1161 : }
1162 :
1163 67315388 : new_val.lattice_val = UNDEFINED;
1164 67315388 : new_val.value = NULL_TREE;
1165 67315388 : new_val.mask = 0;
1166 :
1167 67315388 : bool first = true;
1168 67315388 : bool non_exec_edge = false;
1169 198291381 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1170 : {
1171 : /* Compute the meet operator over all the PHI arguments flowing
1172 : through executable edges. */
1173 137186299 : edge e = gimple_phi_arg_edge (phi, i);
1174 :
1175 137186299 : if (dump_file && (dump_flags & TDF_DETAILS))
1176 : {
1177 6 : fprintf (dump_file,
1178 : "\tArgument #%d (%d -> %d %sexecutable)\n",
1179 3 : i, e->src->index, e->dest->index,
1180 3 : (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
1181 : }
1182 :
1183 : /* If the incoming edge is executable, Compute the meet operator for
1184 : the existing value of the PHI node and the current PHI argument. */
1185 137186299 : if (e->flags & EDGE_EXECUTABLE)
1186 : {
1187 131329427 : tree arg = gimple_phi_arg (phi, i)->def;
1188 131329427 : ccp_prop_value_t arg_val = get_value_for_expr (arg, false);
1189 :
1190 131329427 : if (first)
1191 : {
1192 67315388 : new_val = arg_val;
1193 67315388 : first = false;
1194 : }
1195 : else
1196 64014039 : ccp_lattice_meet (&new_val, &arg_val);
1197 :
1198 131329427 : if (dump_file && (dump_flags & TDF_DETAILS))
1199 : {
1200 3 : fprintf (dump_file, "\t");
1201 3 : print_generic_expr (dump_file, arg, dump_flags);
1202 3 : dump_lattice_value (dump_file, "\tValue: ", arg_val);
1203 3 : fprintf (dump_file, "\n");
1204 : }
1205 :
1206 131329427 : if (new_val.lattice_val == VARYING)
1207 : break;
1208 131329427 : }
1209 : else
1210 : non_exec_edge = true;
1211 : }
1212 :
1213 : /* In case there were non-executable edges and the value is a copy
1214 : make sure its definition dominates the PHI node. */
1215 67315388 : if (non_exec_edge
1216 5486269 : && new_val.lattice_val == CONSTANT
1217 5368099 : && TREE_CODE (new_val.value) == SSA_NAME
1218 1442882 : && ! SSA_NAME_IS_DEFAULT_DEF (new_val.value)
1219 68621317 : && ! dominated_by_p (CDI_DOMINATORS, gimple_bb (phi),
1220 1305929 : gimple_bb (SSA_NAME_DEF_STMT (new_val.value))))
1221 : {
1222 81333 : new_val.lattice_val = VARYING;
1223 81333 : new_val.value = NULL_TREE;
1224 81333 : new_val.mask = -1;
1225 : }
1226 :
1227 67315388 : if (dump_file && (dump_flags & TDF_DETAILS))
1228 : {
1229 1 : dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
1230 1 : fprintf (dump_file, "\n\n");
1231 : }
1232 :
1233 : /* Make the transition to the new value. */
1234 67315388 : if (set_lattice_value (gimple_phi_result (phi), &new_val))
1235 : {
1236 65368688 : if (new_val.lattice_val == VARYING)
1237 : return SSA_PROP_VARYING;
1238 : else
1239 59004702 : return SSA_PROP_INTERESTING;
1240 : }
1241 : else
1242 : return SSA_PROP_NOT_INTERESTING;
1243 67315388 : }
1244 :
1245 : /* Return the constant value for OP or OP otherwise. */
1246 :
1247 : static tree
1248 286027632 : valueize_op (tree op)
1249 : {
1250 286027632 : if (TREE_CODE (op) == SSA_NAME)
1251 : {
1252 274203993 : tree tem = get_constant_value (op);
1253 274203993 : if (tem)
1254 : return tem;
1255 : }
1256 : return op;
1257 : }
1258 :
1259 : /* Return the constant value for OP, but signal to not follow SSA
1260 : edges if the definition may be simulated again. */
1261 :
1262 : static tree
1263 3349611928 : valueize_op_1 (tree op)
1264 : {
1265 3349611928 : if (TREE_CODE (op) == SSA_NAME)
1266 : {
1267 : /* If the definition may be simulated again we cannot follow
1268 : this SSA edge as the SSA propagator does not necessarily
1269 : re-visit the use. */
1270 3349611928 : gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1271 3349611928 : if (!gimple_nop_p (def_stmt)
1272 3349611928 : && prop_simulate_again_p (def_stmt))
1273 : return NULL_TREE;
1274 1728401728 : tree tem = get_constant_value (op);
1275 1728401728 : if (tem)
1276 : return tem;
1277 : }
1278 : return op;
1279 : }
1280 :
1281 : /* CCP specific front-end to the non-destructive constant folding
1282 : routines.
1283 :
1284 : Attempt to simplify the RHS of STMT knowing that one or more
1285 : operands are constants.
1286 :
1287 : If simplification is possible, return the simplified RHS,
1288 : otherwise return the original RHS or NULL_TREE. */
1289 :
1290 : static tree
1291 237277671 : ccp_fold (gimple *stmt)
1292 : {
1293 237277671 : switch (gimple_code (stmt))
1294 : {
1295 94909 : case GIMPLE_SWITCH:
1296 94909 : {
1297 : /* Return the constant switch index. */
1298 94909 : return valueize_op (gimple_switch_index (as_a <gswitch *> (stmt)));
1299 : }
1300 :
1301 237182762 : case GIMPLE_COND:
1302 237182762 : case GIMPLE_ASSIGN:
1303 237182762 : case GIMPLE_CALL:
1304 237182762 : return gimple_fold_stmt_to_constant_1 (stmt,
1305 237182762 : valueize_op, valueize_op_1);
1306 :
1307 0 : default:
1308 0 : gcc_unreachable ();
1309 : }
1310 : }
1311 :
1312 : /* Determine the minimum and maximum values, *MIN and *MAX respectively,
1313 : represented by the mask pair VAL and MASK with signedness SGN and
1314 : precision PRECISION. */
1315 :
1316 : static void
1317 29035052 : value_mask_to_min_max (widest_int *min, widest_int *max,
1318 : const widest_int &val, const widest_int &mask,
1319 : signop sgn, int precision)
1320 : {
1321 29035052 : *min = wi::bit_and_not (val, mask);
1322 29035052 : *max = val | mask;
1323 29035052 : if (sgn == SIGNED && wi::neg_p (mask))
1324 : {
1325 6909674 : widest_int sign_bit = wi::lshift (1, precision - 1);
1326 6909674 : *min ^= sign_bit;
1327 6909674 : *max ^= sign_bit;
1328 : /* MAX is zero extended, and MIN is sign extended. */
1329 6909674 : *min = wi::ext (*min, precision, sgn);
1330 6909722 : *max = wi::ext (*max, precision, sgn);
1331 6909674 : }
1332 29035052 : }
1333 :
1334 : /* Apply the operation CODE in type TYPE to the value, mask pair
1335 : RVAL and RMASK representing a value of type RTYPE and set
1336 : the value, mask pair *VAL and *MASK to the result. */
1337 :
1338 : void
1339 84466217 : bit_value_unop (enum tree_code code, signop type_sgn, int type_precision,
1340 : widest_int *val, widest_int *mask,
1341 : signop rtype_sgn, int rtype_precision,
1342 : const widest_int &rval, const widest_int &rmask)
1343 : {
1344 84471587 : switch (code)
1345 : {
1346 690588 : case BIT_NOT_EXPR:
1347 690588 : *mask = rmask;
1348 690588 : *val = ~rval;
1349 690588 : break;
1350 :
1351 289238 : case NEGATE_EXPR:
1352 289238 : {
1353 289238 : widest_int temv, temm;
1354 : /* Return ~rval + 1. */
1355 289238 : bit_value_unop (BIT_NOT_EXPR, type_sgn, type_precision, &temv, &temm,
1356 : type_sgn, type_precision, rval, rmask);
1357 289238 : bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask,
1358 : type_sgn, type_precision, temv, temm,
1359 578476 : type_sgn, type_precision, 1, 0);
1360 289238 : break;
1361 289238 : }
1362 :
1363 83355510 : CASE_CONVERT:
1364 83355510 : {
1365 : /* First extend mask and value according to the original type. */
1366 83355510 : *mask = wi::ext (rmask, rtype_precision, rtype_sgn);
1367 83355510 : *val = wi::ext (rval, rtype_precision, rtype_sgn);
1368 :
1369 : /* Then extend mask and value according to the target type. */
1370 83355510 : *mask = wi::ext (*mask, type_precision, type_sgn);
1371 83355510 : *val = wi::ext (*val, type_precision, type_sgn);
1372 83355510 : break;
1373 : }
1374 :
1375 136248 : case ABS_EXPR:
1376 136248 : case ABSU_EXPR:
1377 136248 : if (wi::sext (rmask, rtype_precision) == -1)
1378 : {
1379 121023 : *mask = -1;
1380 121023 : *val = 0;
1381 : }
1382 15225 : else if (wi::neg_p (rmask))
1383 : {
1384 : /* Result is either rval or -rval. */
1385 376 : widest_int temv, temm;
1386 376 : bit_value_unop (NEGATE_EXPR, rtype_sgn, rtype_precision, &temv,
1387 : &temm, type_sgn, type_precision, rval, rmask);
1388 376 : temm |= (rmask | (rval ^ temv));
1389 : /* Extend the result. */
1390 376 : *mask = wi::ext (temm, type_precision, type_sgn);
1391 376 : *val = wi::ext (temv, type_precision, type_sgn);
1392 376 : }
1393 14849 : else if (wi::neg_p (rval))
1394 : {
1395 : bit_value_unop (NEGATE_EXPR, type_sgn, type_precision, val, mask,
1396 : type_sgn, type_precision, rval, rmask);
1397 : }
1398 : else
1399 : {
1400 9479 : *mask = rmask;
1401 9479 : *val = rval;
1402 : }
1403 : break;
1404 :
1405 3 : default:
1406 3 : *mask = -1;
1407 3 : *val = 0;
1408 3 : break;
1409 : }
1410 84466217 : }
1411 :
1412 : /* Determine the mask pair *VAL and *MASK from multiplying the
1413 : argument mask pair RVAL, RMASK by the unsigned constant C. */
1414 : static void
1415 28851200 : bit_value_mult_const (signop sgn, int width,
1416 : widest_int *val, widest_int *mask,
1417 : const widest_int &rval, const widest_int &rmask,
1418 : widest_int c)
1419 : {
1420 28851200 : widest_int sum_mask = 0;
1421 :
1422 : /* Ensure rval_lo only contains known bits. */
1423 28851200 : widest_int rval_lo = wi::bit_and_not (rval, rmask);
1424 :
1425 28851200 : if (rval_lo != 0)
1426 : {
1427 : /* General case (some bits of multiplicand are known set). */
1428 742039 : widest_int sum_val = 0;
1429 1732579 : while (c != 0)
1430 : {
1431 : /* Determine the lowest bit set in the multiplier. */
1432 990540 : int bitpos = wi::ctz (c);
1433 990540 : widest_int term_mask = rmask << bitpos;
1434 990540 : widest_int term_val = rval_lo << bitpos;
1435 :
1436 : /* sum += term. */
1437 990540 : widest_int lo = sum_val + term_val;
1438 990540 : widest_int hi = (sum_val | sum_mask) + (term_val | term_mask);
1439 990540 : sum_mask |= term_mask | (lo ^ hi);
1440 990540 : sum_val = lo;
1441 :
1442 : /* Clear this bit in the multiplier. */
1443 990540 : c ^= wi::lshift (1, bitpos);
1444 990540 : }
1445 : /* Correctly extend the result value. */
1446 742039 : *val = wi::ext (sum_val, width, sgn);
1447 742039 : }
1448 : else
1449 : {
1450 : /* Special case (no bits of multiplicand are known set). */
1451 74143299 : while (c != 0)
1452 : {
1453 : /* Determine the lowest bit set in the multiplier. */
1454 46034138 : int bitpos = wi::ctz (c);
1455 46034138 : widest_int term_mask = rmask << bitpos;
1456 :
1457 : /* sum += term. */
1458 46034138 : widest_int hi = sum_mask + term_mask;
1459 46034138 : sum_mask |= term_mask | hi;
1460 :
1461 : /* Clear this bit in the multiplier. */
1462 46034147 : c ^= wi::lshift (1, bitpos);
1463 46034194 : }
1464 28109161 : *val = 0;
1465 : }
1466 :
1467 : /* Correctly extend the result mask. */
1468 28851209 : *mask = wi::ext (sum_mask, width, sgn);
1469 28851200 : }
1470 :
1471 : /* Fill up to MAX values in the BITS array with values representing
1472 : each of the non-zero bits in the value X. Returns the number of
1473 : bits in X (capped at the maximum value MAX). For example, an X
1474 : value 11, places 1, 2 and 8 in BITS and returns the value 3. */
1475 :
1476 : static unsigned int
1477 332712 : get_individual_bits (widest_int *bits, widest_int x, unsigned int max)
1478 : {
1479 332712 : unsigned int count = 0;
1480 1320515 : while (count < max && x != 0)
1481 : {
1482 987803 : int bitpos = wi::ctz (x);
1483 987803 : bits[count] = wi::lshift (1, bitpos);
1484 987803 : x ^= bits[count];
1485 987803 : count++;
1486 : }
1487 332712 : return count;
1488 : }
1489 :
1490 : /* Array of 2^N - 1 values representing the bits flipped between
1491 : consecutive Gray codes. This is used to efficiently enumerate
1492 : all permutations on N bits using XOR. */
1493 : static const unsigned char gray_code_bit_flips[63] = {
1494 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1495 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
1496 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1497 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
1498 : };
1499 :
1500 : /* Apply the operation CODE in type TYPE to the value, mask pairs
1501 : R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1502 : and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */
1503 :
1504 : void
1505 250427286 : bit_value_binop (enum tree_code code, signop sgn, int width,
1506 : widest_int *val, widest_int *mask,
1507 : signop r1type_sgn, int r1type_precision,
1508 : const widest_int &r1val, const widest_int &r1mask,
1509 : signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED,
1510 : const widest_int &r2val, const widest_int &r2mask)
1511 : {
1512 250427286 : bool swap_p = false;
1513 :
1514 : /* Assume we'll get a constant result. Use an initial non varying
1515 : value, we fall back to varying in the end if necessary. */
1516 250427286 : *mask = -1;
1517 : /* Ensure that VAL is initialized (to any value). */
1518 250427286 : *val = 0;
1519 :
1520 250427286 : switch (code)
1521 : {
1522 8909471 : case BIT_AND_EXPR:
1523 : /* The mask is constant where there is a known not
1524 : set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1525 8909471 : *mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask);
1526 8909471 : *val = r1val & r2val;
1527 8909471 : break;
1528 :
1529 3061278 : case BIT_IOR_EXPR:
1530 : /* The mask is constant where there is a known
1531 : set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */
1532 6122556 : *mask = wi::bit_and_not (r1mask | r2mask,
1533 6122556 : wi::bit_and_not (r1val, r1mask)
1534 12245112 : | wi::bit_and_not (r2val, r2mask));
1535 3061278 : *val = r1val | r2val;
1536 3061278 : break;
1537 :
1538 233037 : case BIT_XOR_EXPR:
1539 : /* m1 | m2 */
1540 233037 : *mask = r1mask | r2mask;
1541 233037 : *val = r1val ^ r2val;
1542 233037 : break;
1543 :
1544 24182 : case LROTATE_EXPR:
1545 24182 : case RROTATE_EXPR:
1546 24182 : if (r2mask == 0)
1547 : {
1548 15234 : widest_int shift = r2val;
1549 15234 : if (shift == 0)
1550 : {
1551 14 : *mask = r1mask;
1552 14 : *val = r1val;
1553 : }
1554 : else
1555 : {
1556 15220 : if (wi::neg_p (shift, r2type_sgn))
1557 : {
1558 4 : shift = -shift;
1559 4 : if (code == RROTATE_EXPR)
1560 : code = LROTATE_EXPR;
1561 : else
1562 : code = RROTATE_EXPR;
1563 : }
1564 15216 : if (code == RROTATE_EXPR)
1565 : {
1566 14909 : *mask = wi::rrotate (r1mask, shift, width);
1567 14909 : *val = wi::rrotate (r1val, shift, width);
1568 : }
1569 : else
1570 : {
1571 311 : *mask = wi::lrotate (r1mask, shift, width);
1572 311 : *val = wi::lrotate (r1val, shift, width);
1573 : }
1574 15220 : *mask = wi::ext (*mask, width, sgn);
1575 15220 : *val = wi::ext (*val, width, sgn);
1576 : }
1577 15234 : }
1578 17896 : else if (wi::ltu_p (r2val | r2mask, width)
1579 28299 : && wi::popcount (r2mask) <= 4)
1580 : {
1581 29637 : widest_int bits[4];
1582 3293 : widest_int res_val, res_mask;
1583 3293 : widest_int tmp_val, tmp_mask;
1584 3293 : widest_int shift = wi::bit_and_not (r2val, r2mask);
1585 3293 : unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1586 3293 : unsigned int count = (1 << bit_count) - 1;
1587 :
1588 : /* Initialize result to rotate by smallest value of shift. */
1589 3293 : if (code == RROTATE_EXPR)
1590 : {
1591 1584 : res_mask = wi::rrotate (r1mask, shift, width);
1592 1584 : res_val = wi::rrotate (r1val, shift, width);
1593 : }
1594 : else
1595 : {
1596 1709 : res_mask = wi::lrotate (r1mask, shift, width);
1597 1709 : res_val = wi::lrotate (r1val, shift, width);
1598 : }
1599 :
1600 : /* Iterate through the remaining values of shift. */
1601 38672 : for (unsigned int i=0; i<count; i++)
1602 : {
1603 35379 : shift ^= bits[gray_code_bit_flips[i]];
1604 35379 : if (code == RROTATE_EXPR)
1605 : {
1606 17320 : tmp_mask = wi::rrotate (r1mask, shift, width);
1607 17320 : tmp_val = wi::rrotate (r1val, shift, width);
1608 : }
1609 : else
1610 : {
1611 18059 : tmp_mask = wi::lrotate (r1mask, shift, width);
1612 18059 : tmp_val = wi::lrotate (r1val, shift, width);
1613 : }
1614 : /* Accumulate the result. */
1615 35379 : res_mask |= tmp_mask | (res_val ^ tmp_val);
1616 : }
1617 3293 : *val = wi::ext (wi::bit_and_not (res_val, res_mask), width, sgn);
1618 3293 : *mask = wi::ext (res_mask, width, sgn);
1619 16465 : }
1620 : break;
1621 :
1622 6697196 : case LSHIFT_EXPR:
1623 6697196 : case RSHIFT_EXPR:
1624 : /* ??? We can handle partially known shift counts if we know
1625 : its sign. That way we can tell that (x << (y | 8)) & 255
1626 : is zero. */
1627 6697196 : if (r2mask == 0)
1628 : {
1629 5713459 : widest_int shift = r2val;
1630 5713459 : if (shift == 0)
1631 : {
1632 7695 : *mask = r1mask;
1633 7695 : *val = r1val;
1634 : }
1635 : else
1636 : {
1637 5705764 : if (wi::neg_p (shift, r2type_sgn))
1638 : break;
1639 5705586 : if (code == RSHIFT_EXPR)
1640 : {
1641 5317763 : *mask = wi::rshift (wi::ext (r1mask, width, sgn), shift, sgn);
1642 5317730 : *val = wi::rshift (wi::ext (r1val, width, sgn), shift, sgn);
1643 : }
1644 : else
1645 : {
1646 387862 : *mask = wi::ext (r1mask << shift, width, sgn);
1647 387856 : *val = wi::ext (r1val << shift, width, sgn);
1648 : }
1649 : }
1650 5713459 : }
1651 983737 : else if (wi::ltu_p (r2val | r2mask, width))
1652 : {
1653 898366 : if (wi::popcount (r2mask) <= 4)
1654 : {
1655 2964771 : widest_int bits[4];
1656 329419 : widest_int arg_val, arg_mask;
1657 329419 : widest_int res_val, res_mask;
1658 329419 : widest_int tmp_val, tmp_mask;
1659 329419 : widest_int shift = wi::bit_and_not (r2val, r2mask);
1660 329419 : unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1661 329419 : unsigned int count = (1 << bit_count) - 1;
1662 :
1663 : /* Initialize result to shift by smallest value of shift. */
1664 329419 : if (code == RSHIFT_EXPR)
1665 : {
1666 124462 : arg_mask = wi::ext (r1mask, width, sgn);
1667 124462 : arg_val = wi::ext (r1val, width, sgn);
1668 124462 : res_mask = wi::rshift (arg_mask, shift, sgn);
1669 124462 : res_val = wi::rshift (arg_val, shift, sgn);
1670 : }
1671 : else
1672 : {
1673 204957 : arg_mask = r1mask;
1674 204957 : arg_val = r1val;
1675 204957 : res_mask = arg_mask << shift;
1676 204957 : res_val = arg_val << shift;
1677 : }
1678 :
1679 : /* Iterate through the remaining values of shift. */
1680 3121032 : for (unsigned int i=0; i<count; i++)
1681 : {
1682 2791613 : shift ^= bits[gray_code_bit_flips[i]];
1683 2791613 : if (code == RSHIFT_EXPR)
1684 : {
1685 1090470 : tmp_mask = wi::rshift (arg_mask, shift, sgn);
1686 1090470 : tmp_val = wi::rshift (arg_val, shift, sgn);
1687 : }
1688 : else
1689 : {
1690 1701143 : tmp_mask = arg_mask << shift;
1691 1701143 : tmp_val = arg_val << shift;
1692 : }
1693 : /* Accumulate the result. */
1694 2791613 : res_mask |= tmp_mask | (res_val ^ tmp_val);
1695 : }
1696 329419 : res_mask = wi::ext (res_mask, width, sgn);
1697 329419 : res_val = wi::ext (res_val, width, sgn);
1698 329419 : *val = wi::bit_and_not (res_val, res_mask);
1699 329419 : *mask = res_mask;
1700 1647095 : }
1701 568947 : else if ((r1val | r1mask) == 0)
1702 : {
1703 : /* Handle shifts of zero to avoid undefined wi::ctz below. */
1704 0 : *mask = 0;
1705 0 : *val = 0;
1706 : }
1707 568947 : else if (code == LSHIFT_EXPR)
1708 : {
1709 387542 : widest_int tmp = wi::mask <widest_int> (width, false);
1710 387542 : tmp <<= wi::ctz (r1val | r1mask);
1711 387542 : tmp <<= wi::bit_and_not (r2val, r2mask);
1712 387542 : *mask = wi::ext (tmp, width, sgn);
1713 387542 : *val = 0;
1714 387542 : }
1715 181405 : else if (!wi::neg_p (r1val | r1mask, sgn))
1716 : {
1717 : /* Logical right shift, or zero sign bit. */
1718 161496 : widest_int arg = r1val | r1mask;
1719 161496 : int lzcount = wi::clz (arg);
1720 161496 : if (lzcount)
1721 161488 : lzcount -= wi::get_precision (arg) - width;
1722 161496 : widest_int tmp = wi::mask <widest_int> (width, false);
1723 161496 : tmp = wi::lrshift (tmp, lzcount);
1724 161496 : tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1725 161496 : *mask = wi::ext (tmp, width, sgn);
1726 161496 : *val = 0;
1727 161496 : }
1728 19909 : else if (!wi::neg_p (r1mask))
1729 : {
1730 : /* Arithmetic right shift with set sign bit. */
1731 1090 : widest_int arg = wi::bit_and_not (r1val, r1mask);
1732 1090 : int sbcount = wi::clrsb (arg);
1733 1090 : sbcount -= wi::get_precision (arg) - width;
1734 1090 : widest_int tmp = wi::mask <widest_int> (width, false);
1735 1090 : tmp = wi::lrshift (tmp, sbcount);
1736 1090 : tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1737 1090 : *mask = wi::sext (tmp, width);
1738 1090 : tmp = wi::bit_not (tmp);
1739 1090 : *val = wi::sext (tmp, width);
1740 1090 : }
1741 : }
1742 : break;
1743 :
1744 126951506 : case PLUS_EXPR:
1745 126951506 : case POINTER_PLUS_EXPR:
1746 126951506 : {
1747 : /* Do the addition with unknown bits set to zero, to give carry-ins of
1748 : zero wherever possible. */
1749 253903012 : widest_int lo = (wi::bit_and_not (r1val, r1mask)
1750 253903012 : + wi::bit_and_not (r2val, r2mask));
1751 126951506 : lo = wi::ext (lo, width, sgn);
1752 : /* Do the addition with unknown bits set to one, to give carry-ins of
1753 : one wherever possible. */
1754 126951775 : widest_int hi = (r1val | r1mask) + (r2val | r2mask);
1755 126951506 : hi = wi::ext (hi, width, sgn);
1756 : /* Each bit in the result is known if (a) the corresponding bits in
1757 : both inputs are known, and (b) the carry-in to that bit position
1758 : is known. We can check condition (b) by seeing if we got the same
1759 : result with minimised carries as with maximised carries. */
1760 126952048 : *mask = r1mask | r2mask | (lo ^ hi);
1761 126951506 : *mask = wi::ext (*mask, width, sgn);
1762 : /* It shouldn't matter whether we choose lo or hi here. */
1763 126951506 : *val = lo;
1764 126951506 : break;
1765 126951585 : }
1766 :
1767 22201318 : case MINUS_EXPR:
1768 22201318 : case POINTER_DIFF_EXPR:
1769 22201318 : {
1770 : /* Subtraction is derived from the addition algorithm above. */
1771 22201318 : widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask);
1772 22201318 : lo = wi::ext (lo, width, sgn);
1773 22201381 : widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask);
1774 22201318 : hi = wi::ext (hi, width, sgn);
1775 22201444 : *mask = r1mask | r2mask | (lo ^ hi);
1776 22201318 : *mask = wi::ext (*mask, width, sgn);
1777 22201318 : *val = lo;
1778 22201318 : break;
1779 22201418 : }
1780 :
1781 32520587 : case MULT_EXPR:
1782 32520587 : if (r2mask == 0
1783 28878623 : && !wi::neg_p (r2val, sgn)
1784 64039186 : && (flag_expensive_optimizations || wi::popcount (r2val) < 8))
1785 28764527 : bit_value_mult_const (sgn, width, val, mask, r1val, r1mask, r2val);
1786 3756060 : else if (r1mask == 0
1787 88323 : && !wi::neg_p (r1val, sgn)
1788 3857517 : && (flag_expensive_optimizations || wi::popcount (r1val) < 8))
1789 86673 : bit_value_mult_const (sgn, width, val, mask, r2val, r2mask, r1val);
1790 : else
1791 : {
1792 : /* Just track trailing zeros in both operands and transfer
1793 : them to the other. */
1794 3669387 : int r1tz = wi::ctz (r1val | r1mask);
1795 3669387 : int r2tz = wi::ctz (r2val | r2mask);
1796 3669387 : if (r1tz + r2tz >= width)
1797 : {
1798 12 : *mask = 0;
1799 12 : *val = 0;
1800 : }
1801 3669375 : else if (r1tz + r2tz > 0)
1802 : {
1803 896954 : *mask = wi::ext (wi::mask <widest_int> (r1tz + r2tz, true),
1804 448477 : width, sgn);
1805 448477 : *val = 0;
1806 : }
1807 : }
1808 : break;
1809 :
1810 30073230 : case EQ_EXPR:
1811 30073230 : case NE_EXPR:
1812 30073230 : {
1813 30073230 : widest_int m = r1mask | r2mask;
1814 30073230 : if (wi::bit_and_not (r1val, m) != wi::bit_and_not (r2val, m))
1815 : {
1816 2314813 : *mask = 0;
1817 2314813 : *val = ((code == EQ_EXPR) ? 0 : 1);
1818 : }
1819 : else
1820 : {
1821 : /* We know the result of a comparison is always one or zero. */
1822 27758417 : *mask = 1;
1823 27758417 : *val = 0;
1824 : }
1825 30073230 : break;
1826 30073230 : }
1827 :
1828 7558274 : case GE_EXPR:
1829 7558274 : case GT_EXPR:
1830 7558274 : swap_p = true;
1831 7558274 : code = swap_tree_comparison (code);
1832 : /* Fall through. */
1833 12366837 : case LT_EXPR:
1834 12366837 : case LE_EXPR:
1835 12366837 : {
1836 12366837 : widest_int min1, max1, min2, max2;
1837 12366837 : int minmax, maxmin;
1838 :
1839 12366837 : const widest_int &o1val = swap_p ? r2val : r1val;
1840 4808563 : const widest_int &o1mask = swap_p ? r2mask : r1mask;
1841 4808563 : const widest_int &o2val = swap_p ? r1val : r2val;
1842 4808563 : const widest_int &o2mask = swap_p ? r1mask : r2mask;
1843 :
1844 12366837 : value_mask_to_min_max (&min1, &max1, o1val, o1mask,
1845 : r1type_sgn, r1type_precision);
1846 12366837 : value_mask_to_min_max (&min2, &max2, o2val, o2mask,
1847 : r1type_sgn, r1type_precision);
1848 :
1849 : /* For comparisons the signedness is in the comparison operands. */
1850 : /* Do a cross comparison of the max/min pairs. */
1851 12366837 : maxmin = wi::cmp (max1, min2, r1type_sgn);
1852 12366837 : minmax = wi::cmp (min1, max2, r1type_sgn);
1853 19267368 : if (maxmin < (code == LE_EXPR ? 1 : 0)) /* o1 < or <= o2. */
1854 : {
1855 3004486 : *mask = 0;
1856 3004486 : *val = 1;
1857 : }
1858 11914047 : else if (minmax > (code == LT_EXPR ? -1 : 0)) /* o1 >= or > o2. */
1859 : {
1860 443077 : *mask = 0;
1861 443077 : *val = 0;
1862 : }
1863 8919274 : else if (maxmin == minmax) /* o1 and o2 are equal. */
1864 : {
1865 : /* This probably should never happen as we'd have
1866 : folded the thing during fully constant value folding. */
1867 0 : *mask = 0;
1868 0 : *val = (code == LE_EXPR ? 1 : 0);
1869 : }
1870 : else
1871 : {
1872 : /* We know the result of a comparison is always one or zero. */
1873 8919274 : *mask = 1;
1874 8919274 : *val = 0;
1875 : }
1876 12366837 : break;
1877 12366923 : }
1878 :
1879 2150689 : case MIN_EXPR:
1880 2150689 : case MAX_EXPR:
1881 2150689 : {
1882 2150689 : widest_int min1, max1, min2, max2;
1883 :
1884 2150689 : value_mask_to_min_max (&min1, &max1, r1val, r1mask, sgn, width);
1885 2150689 : value_mask_to_min_max (&min2, &max2, r2val, r2mask, sgn, width);
1886 :
1887 2150689 : if (wi::cmp (max1, min2, sgn) <= 0) /* r1 is less than r2. */
1888 : {
1889 28765 : if (code == MIN_EXPR)
1890 : {
1891 27798 : *mask = r1mask;
1892 27798 : *val = r1val;
1893 : }
1894 : else
1895 : {
1896 967 : *mask = r2mask;
1897 967 : *val = r2val;
1898 : }
1899 : }
1900 2121924 : else if (wi::cmp (min1, max2, sgn) >= 0) /* r2 is less than r1. */
1901 : {
1902 110072 : if (code == MIN_EXPR)
1903 : {
1904 1354 : *mask = r2mask;
1905 1354 : *val = r2val;
1906 : }
1907 : else
1908 : {
1909 108718 : *mask = r1mask;
1910 108718 : *val = r1val;
1911 : }
1912 : }
1913 : else
1914 : {
1915 : /* The result is either r1 or r2. */
1916 2011856 : *mask = r1mask | r2mask | (r1val ^ r2val);
1917 2011852 : *val = r1val;
1918 : }
1919 2150689 : break;
1920 2150693 : }
1921 :
1922 1743744 : case TRUNC_MOD_EXPR:
1923 1743744 : {
1924 1743744 : widest_int r1max = r1val | r1mask;
1925 1743744 : widest_int r2max = r2val | r2mask;
1926 1743744 : if (r2mask == 0)
1927 : {
1928 502418 : widest_int shift = wi::exact_log2 (r2val);
1929 502418 : if (shift != -1)
1930 : {
1931 : // Handle modulo by a power of 2 as a bitwise and.
1932 86552 : widest_int tem_val, tem_mask;
1933 86552 : bit_value_binop (BIT_AND_EXPR, sgn, width, &tem_val, &tem_mask,
1934 : r1type_sgn, r1type_precision, r1val, r1mask,
1935 : r2type_sgn, r2type_precision,
1936 86552 : r2val - 1, r2mask);
1937 86552 : if (sgn == UNSIGNED
1938 86403 : || !wi::neg_p (r1max)
1939 132774 : || (tem_mask == 0 && tem_val == 0))
1940 : {
1941 40362 : *val = tem_val;
1942 40362 : *mask = tem_mask;
1943 40362 : return;
1944 : }
1945 86552 : }
1946 502418 : }
1947 1703382 : if (sgn == UNSIGNED
1948 1703382 : || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1949 : {
1950 : /* Confirm R2 has some bits set, to avoid division by zero. */
1951 840990 : widest_int r2min = wi::bit_and_not (r2val, r2mask);
1952 840990 : if (r2min != 0)
1953 : {
1954 : /* R1 % R2 is R1 if R1 is always less than R2. */
1955 314617 : if (wi::ltu_p (r1max, r2min))
1956 : {
1957 15968 : *mask = r1mask;
1958 15968 : *val = r1val;
1959 : }
1960 : else
1961 : {
1962 : /* R1 % R2 is always less than the maximum of R2. */
1963 298649 : unsigned int lzcount = wi::clz (r2max);
1964 298649 : unsigned int bits = wi::get_precision (r2max) - lzcount;
1965 298649 : if (r2max == wi::lshift (1, bits))
1966 0 : bits--;
1967 298649 : *mask = wi::mask <widest_int> (bits, false);
1968 298649 : *val = 0;
1969 : }
1970 : }
1971 840990 : }
1972 1743744 : }
1973 1703382 : break;
1974 :
1975 3474547 : case EXACT_DIV_EXPR:
1976 3474547 : case TRUNC_DIV_EXPR:
1977 3474547 : {
1978 3474547 : widest_int r1max = r1val | r1mask;
1979 3474547 : widest_int r2max = r2val | r2mask;
1980 4837016 : if (r2mask == 0
1981 3474547 : && (code == EXACT_DIV_EXPR
1982 2628708 : || sgn == UNSIGNED
1983 707297 : || !wi::neg_p (r1max)))
1984 : {
1985 2112078 : widest_int shift = wi::exact_log2 (r2val);
1986 2112078 : if (shift != -1)
1987 : {
1988 : // Handle division by a power of 2 as an rshift.
1989 1615442 : bit_value_binop (RSHIFT_EXPR, sgn, width, val, mask,
1990 : r1type_sgn, r1type_precision, r1val, r1mask,
1991 : r2type_sgn, r2type_precision, shift, r2mask);
1992 1615442 : return;
1993 : }
1994 2112078 : }
1995 1859105 : if (sgn == UNSIGNED
1996 1859105 : || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1997 : {
1998 : /* Confirm R2 has some bits set, to avoid division by zero. */
1999 717752 : widest_int r2min = wi::bit_and_not (r2val, r2mask);
2000 717752 : if (r2min != 0)
2001 : {
2002 : /* R1 / R2 is zero if R1 is always less than R2. */
2003 358181 : if (wi::ltu_p (r1max, r2min))
2004 : {
2005 2705 : *mask = 0;
2006 2705 : *val = 0;
2007 : }
2008 : else
2009 : {
2010 355476 : widest_int upper
2011 355476 : = wi::udiv_trunc (wi::zext (r1max, width), r2min);
2012 355476 : unsigned int lzcount = wi::clz (upper);
2013 355476 : unsigned int bits = wi::get_precision (upper) - lzcount;
2014 355476 : *mask = wi::mask <widest_int> (bits, false);
2015 355476 : *val = 0;
2016 355476 : }
2017 : }
2018 717752 : }
2019 3474551 : }
2020 1859105 : break;
2021 :
2022 250427286 : default:;
2023 : }
2024 : }
2025 :
2026 : /* Return the propagation value when applying the operation CODE to
2027 : the value RHS yielding type TYPE. */
2028 :
2029 : static ccp_prop_value_t
2030 30071467 : bit_value_unop (enum tree_code code, tree type, tree rhs)
2031 : {
2032 30071467 : ccp_prop_value_t rval = get_value_for_expr (rhs, true);
2033 30071467 : widest_int value, mask;
2034 30071467 : ccp_prop_value_t val;
2035 :
2036 30071467 : if (rval.lattice_val == UNDEFINED)
2037 0 : return rval;
2038 :
2039 37063337 : gcc_assert ((rval.lattice_val == CONSTANT
2040 : && TREE_CODE (rval.value) == INTEGER_CST)
2041 : || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1);
2042 60142934 : bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2043 30071467 : TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)),
2044 60142934 : value_to_wide_int (rval), rval.mask);
2045 30071663 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2046 : {
2047 23883309 : val.lattice_val = CONSTANT;
2048 23883309 : val.mask = mask;
2049 : /* ??? Delay building trees here. */
2050 23883309 : val.value = wide_int_to_tree (type, value);
2051 : }
2052 : else
2053 : {
2054 6188158 : val.lattice_val = VARYING;
2055 6188158 : val.value = NULL_TREE;
2056 6188158 : val.mask = -1;
2057 : }
2058 30071467 : return val;
2059 30071890 : }
2060 :
2061 : /* Return the propagation value when applying the operation CODE to
2062 : the values RHS1 and RHS2 yielding type TYPE. */
2063 :
2064 : static ccp_prop_value_t
2065 142308355 : bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
2066 : {
2067 142308355 : ccp_prop_value_t r1val = get_value_for_expr (rhs1, true);
2068 142308355 : ccp_prop_value_t r2val = get_value_for_expr (rhs2, true);
2069 142308355 : widest_int value, mask;
2070 142308355 : ccp_prop_value_t val;
2071 :
2072 142308355 : if (r1val.lattice_val == UNDEFINED
2073 142174222 : || r2val.lattice_val == UNDEFINED)
2074 : {
2075 140038 : val.lattice_val = VARYING;
2076 140038 : val.value = NULL_TREE;
2077 140038 : val.mask = -1;
2078 140038 : return val;
2079 : }
2080 :
2081 187083338 : gcc_assert ((r1val.lattice_val == CONSTANT
2082 : && TREE_CODE (r1val.value) == INTEGER_CST)
2083 : || wi::sext (r1val.mask,
2084 : TYPE_PRECISION (TREE_TYPE (rhs1))) == -1);
2085 154994407 : gcc_assert ((r2val.lattice_val == CONSTANT
2086 : && TREE_CODE (r2val.value) == INTEGER_CST)
2087 : || wi::sext (r2val.mask,
2088 : TYPE_PRECISION (TREE_TYPE (rhs2))) == -1);
2089 284336634 : bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2090 142168317 : TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)),
2091 284337203 : value_to_wide_int (r1val), r1val.mask,
2092 142168317 : TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)),
2093 284336634 : value_to_wide_int (r2val), r2val.mask);
2094 :
2095 : /* (x * x) & 2 == 0. */
2096 142168317 : if (code == MULT_EXPR && rhs1 == rhs2 && TYPE_PRECISION (type) > 1)
2097 : {
2098 169170 : widest_int m = 2;
2099 169170 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2100 530 : value = wi::bit_and_not (value, m);
2101 : else
2102 168640 : value = 0;
2103 169170 : mask = wi::bit_and_not (mask, m);
2104 169170 : }
2105 :
2106 142168339 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2107 : {
2108 119887561 : val.lattice_val = CONSTANT;
2109 119887561 : val.mask = mask;
2110 : /* ??? Delay building trees here. */
2111 119887561 : val.value = wide_int_to_tree (type, value);
2112 : }
2113 : else
2114 : {
2115 22280756 : val.lattice_val = VARYING;
2116 22280756 : val.value = NULL_TREE;
2117 22280756 : val.mask = -1;
2118 : }
2119 : return val;
2120 142308662 : }
2121 :
2122 : /* Return the propagation value for __builtin_assume_aligned
2123 : and functions with assume_aligned or alloc_aligned attribute.
2124 : For __builtin_assume_aligned, ATTR is NULL_TREE,
2125 : for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED
2126 : is false, for alloc_aligned attribute ATTR is non-NULL and
2127 : ALLOC_ALIGNED is true. */
2128 :
2129 : static ccp_prop_value_t
2130 7919 : bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval,
2131 : bool alloc_aligned)
2132 : {
2133 7919 : tree align, misalign = NULL_TREE, type;
2134 7919 : unsigned HOST_WIDE_INT aligni, misaligni = 0;
2135 7919 : ccp_prop_value_t alignval;
2136 7919 : widest_int value, mask;
2137 7919 : ccp_prop_value_t val;
2138 :
2139 7919 : if (attr == NULL_TREE)
2140 : {
2141 2991 : tree ptr = gimple_call_arg (stmt, 0);
2142 2991 : type = TREE_TYPE (ptr);
2143 2991 : ptrval = get_value_for_expr (ptr, true);
2144 : }
2145 : else
2146 : {
2147 4928 : tree lhs = gimple_call_lhs (stmt);
2148 4928 : type = TREE_TYPE (lhs);
2149 : }
2150 :
2151 7919 : if (ptrval.lattice_val == UNDEFINED)
2152 0 : return ptrval;
2153 15294 : gcc_assert ((ptrval.lattice_val == CONSTANT
2154 : && TREE_CODE (ptrval.value) == INTEGER_CST)
2155 : || wi::sext (ptrval.mask, TYPE_PRECISION (type)) == -1);
2156 7919 : if (attr == NULL_TREE)
2157 : {
2158 : /* Get aligni and misaligni from __builtin_assume_aligned. */
2159 2991 : align = gimple_call_arg (stmt, 1);
2160 2991 : if (!tree_fits_uhwi_p (align))
2161 47 : return ptrval;
2162 2944 : aligni = tree_to_uhwi (align);
2163 2944 : if (gimple_call_num_args (stmt) > 2)
2164 : {
2165 36 : misalign = gimple_call_arg (stmt, 2);
2166 36 : if (!tree_fits_uhwi_p (misalign))
2167 2 : return ptrval;
2168 34 : misaligni = tree_to_uhwi (misalign);
2169 : }
2170 : }
2171 : else
2172 : {
2173 : /* Get aligni and misaligni from assume_aligned or
2174 : alloc_align attributes. */
2175 4928 : if (TREE_VALUE (attr) == NULL_TREE)
2176 0 : return ptrval;
2177 4928 : attr = TREE_VALUE (attr);
2178 4928 : align = TREE_VALUE (attr);
2179 4928 : if (!tree_fits_uhwi_p (align))
2180 0 : return ptrval;
2181 4928 : aligni = tree_to_uhwi (align);
2182 4928 : if (alloc_aligned)
2183 : {
2184 4886 : if (aligni == 0 || aligni > gimple_call_num_args (stmt))
2185 0 : return ptrval;
2186 4886 : align = gimple_call_arg (stmt, aligni - 1);
2187 4886 : if (!tree_fits_uhwi_p (align))
2188 215 : return ptrval;
2189 4671 : aligni = tree_to_uhwi (align);
2190 : }
2191 42 : else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr)))
2192 : {
2193 21 : misalign = TREE_VALUE (TREE_CHAIN (attr));
2194 21 : if (!tree_fits_uhwi_p (misalign))
2195 0 : return ptrval;
2196 21 : misaligni = tree_to_uhwi (misalign);
2197 : }
2198 : }
2199 7655 : if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni)
2200 154 : return ptrval;
2201 :
2202 7501 : align = build_int_cst_type (type, -aligni);
2203 7501 : alignval = get_value_for_expr (align, true);
2204 15002 : bit_value_binop (BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2205 15002 : TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (ptrval), ptrval.mask,
2206 15002 : TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (alignval), alignval.mask);
2207 :
2208 7501 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2209 : {
2210 7501 : val.lattice_val = CONSTANT;
2211 7501 : val.mask = mask;
2212 7501 : gcc_assert ((mask.to_uhwi () & (aligni - 1)) == 0);
2213 7501 : gcc_assert ((value.to_uhwi () & (aligni - 1)) == 0);
2214 7501 : value |= misaligni;
2215 : /* ??? Delay building trees here. */
2216 7501 : val.value = wide_int_to_tree (type, value);
2217 : }
2218 : else
2219 : {
2220 0 : val.lattice_val = VARYING;
2221 0 : val.value = NULL_TREE;
2222 0 : val.mask = -1;
2223 : }
2224 7501 : return val;
2225 7919 : }
2226 :
2227 : /* Evaluate statement STMT.
2228 : Valid only for assignments, calls, conditionals, and switches. */
2229 :
2230 : static ccp_prop_value_t
2231 237539959 : evaluate_stmt (gimple *stmt)
2232 : {
2233 237539959 : ccp_prop_value_t val;
2234 237539959 : tree simplified = NULL_TREE;
2235 237539959 : ccp_lattice_t likelyvalue = likely_value (stmt);
2236 237539959 : bool is_constant = false;
2237 237539959 : unsigned int align;
2238 237539959 : bool ignore_return_flags = false;
2239 :
2240 237539959 : if (dump_file && (dump_flags & TDF_DETAILS))
2241 : {
2242 66 : fprintf (dump_file, "which is likely ");
2243 66 : switch (likelyvalue)
2244 : {
2245 65 : case CONSTANT:
2246 65 : fprintf (dump_file, "CONSTANT");
2247 65 : break;
2248 1 : case UNDEFINED:
2249 1 : fprintf (dump_file, "UNDEFINED");
2250 1 : break;
2251 0 : case VARYING:
2252 0 : fprintf (dump_file, "VARYING");
2253 0 : break;
2254 66 : default:;
2255 : }
2256 66 : fprintf (dump_file, "\n");
2257 : }
2258 :
2259 : /* If the statement is likely to have a CONSTANT result, then try
2260 : to fold the statement to determine the constant value. */
2261 : /* FIXME. This is the only place that we call ccp_fold.
2262 : Since likely_value never returns CONSTANT for calls, we will
2263 : not attempt to fold them, including builtins that may profit. */
2264 237539959 : if (likelyvalue == CONSTANT)
2265 : {
2266 237277671 : fold_defer_overflow_warnings ();
2267 237277671 : simplified = ccp_fold (stmt);
2268 237277671 : if (simplified
2269 32869670 : && TREE_CODE (simplified) == SSA_NAME)
2270 : {
2271 : /* We may not use values of something that may be simulated again,
2272 : see valueize_op_1. */
2273 16767072 : if (SSA_NAME_IS_DEFAULT_DEF (simplified)
2274 16767072 : || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (simplified)))
2275 : {
2276 12253074 : ccp_prop_value_t *val = get_value (simplified);
2277 12253074 : if (val && val->lattice_val != VARYING)
2278 : {
2279 603500 : fold_undefer_overflow_warnings (true, stmt, 0);
2280 603500 : return *val;
2281 : }
2282 : }
2283 : else
2284 : /* We may also not place a non-valueized copy in the lattice
2285 : as that might become stale if we never re-visit this stmt. */
2286 : simplified = NULL_TREE;
2287 : }
2288 27752172 : is_constant = simplified && is_gimple_min_invariant (simplified);
2289 236674171 : fold_undefer_overflow_warnings (is_constant, stmt, 0);
2290 236674171 : if (is_constant)
2291 : {
2292 : /* The statement produced a constant value. */
2293 13282824 : val.lattice_val = CONSTANT;
2294 13282824 : val.value = simplified;
2295 13282824 : val.mask = 0;
2296 13282824 : return val;
2297 : }
2298 : }
2299 : /* If the statement is likely to have a VARYING result, then do not
2300 : bother folding the statement. */
2301 262288 : else if (likelyvalue == VARYING)
2302 : {
2303 110185 : enum gimple_code code = gimple_code (stmt);
2304 110185 : if (code == GIMPLE_ASSIGN)
2305 : {
2306 770 : enum tree_code subcode = gimple_assign_rhs_code (stmt);
2307 :
2308 : /* Other cases cannot satisfy is_gimple_min_invariant
2309 : without folding. */
2310 770 : if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
2311 770 : simplified = gimple_assign_rhs1 (stmt);
2312 : }
2313 109415 : else if (code == GIMPLE_SWITCH)
2314 0 : simplified = gimple_switch_index (as_a <gswitch *> (stmt));
2315 : else
2316 : /* These cannot satisfy is_gimple_min_invariant without folding. */
2317 109415 : gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
2318 770 : is_constant = simplified && is_gimple_min_invariant (simplified);
2319 0 : if (is_constant)
2320 : {
2321 : /* The statement produced a constant value. */
2322 0 : val.lattice_val = CONSTANT;
2323 0 : val.value = simplified;
2324 0 : val.mask = 0;
2325 : }
2326 : }
2327 : /* If the statement result is likely UNDEFINED, make it so. */
2328 152103 : else if (likelyvalue == UNDEFINED)
2329 : {
2330 152103 : val.lattice_val = UNDEFINED;
2331 152103 : val.value = NULL_TREE;
2332 152103 : val.mask = 0;
2333 152103 : return val;
2334 : }
2335 :
2336 : /* Resort to simplification for bitwise tracking. */
2337 223501532 : if (flag_tree_bit_ccp
2338 223421636 : && (likelyvalue == CONSTANT || is_gimple_call (stmt)
2339 770 : || (gimple_assign_single_p (stmt)
2340 770 : && gimple_assign_rhs_code (stmt) == ADDR_EXPR))
2341 446922432 : && !is_constant)
2342 : {
2343 223420900 : enum gimple_code code = gimple_code (stmt);
2344 223420900 : val.lattice_val = VARYING;
2345 223420900 : val.value = NULL_TREE;
2346 223420900 : val.mask = -1;
2347 223420900 : if (code == GIMPLE_ASSIGN)
2348 : {
2349 179134468 : enum tree_code subcode = gimple_assign_rhs_code (stmt);
2350 179134468 : tree rhs1 = gimple_assign_rhs1 (stmt);
2351 179134468 : tree lhs = gimple_assign_lhs (stmt);
2352 357825663 : if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2353 33954450 : || POINTER_TYPE_P (TREE_TYPE (lhs)))
2354 351637512 : && (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2355 29235666 : || POINTER_TYPE_P (TREE_TYPE (rhs1))))
2356 172605383 : switch (get_gimple_rhs_class (subcode))
2357 : {
2358 38671117 : case GIMPLE_SINGLE_RHS:
2359 38671117 : val = get_value_for_expr (rhs1, true);
2360 38671117 : break;
2361 :
2362 30071467 : case GIMPLE_UNARY_RHS:
2363 30071467 : val = bit_value_unop (subcode, TREE_TYPE (lhs), rhs1);
2364 30071467 : break;
2365 :
2366 103845875 : case GIMPLE_BINARY_RHS:
2367 103845875 : val = bit_value_binop (subcode, TREE_TYPE (lhs), rhs1,
2368 103845875 : gimple_assign_rhs2 (stmt));
2369 103845875 : break;
2370 :
2371 : default:;
2372 : }
2373 : }
2374 44286432 : else if (code == GIMPLE_COND)
2375 : {
2376 39893775 : enum tree_code code = gimple_cond_code (stmt);
2377 39893775 : tree rhs1 = gimple_cond_lhs (stmt);
2378 39893775 : tree rhs2 = gimple_cond_rhs (stmt);
2379 79237368 : if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2380 47678443 : || POINTER_TYPE_P (TREE_TYPE (rhs1)))
2381 38462480 : val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
2382 : }
2383 4392657 : else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2384 : {
2385 2408158 : tree fndecl = gimple_call_fndecl (stmt);
2386 2408158 : switch (DECL_FUNCTION_CODE (fndecl))
2387 : {
2388 230918 : case BUILT_IN_MALLOC:
2389 230918 : case BUILT_IN_REALLOC:
2390 230918 : case BUILT_IN_GOMP_REALLOC:
2391 230918 : case BUILT_IN_CALLOC:
2392 230918 : case BUILT_IN_STRDUP:
2393 230918 : case BUILT_IN_STRNDUP:
2394 230918 : val.lattice_val = CONSTANT;
2395 230918 : val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2396 233197 : val.mask = ~((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT
2397 230918 : / BITS_PER_UNIT - 1);
2398 230918 : break;
2399 :
2400 52436 : CASE_BUILT_IN_ALLOCA:
2401 90153 : align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA
2402 37721 : ? BIGGEST_ALIGNMENT
2403 14715 : : TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2404 52436 : val.lattice_val = CONSTANT;
2405 52436 : val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2406 52436 : val.mask = ~((HOST_WIDE_INT) align / BITS_PER_UNIT - 1);
2407 52436 : break;
2408 :
2409 2723 : case BUILT_IN_ASSUME_ALIGNED:
2410 2723 : val = bit_value_assume_aligned (stmt, NULL_TREE, val, false);
2411 2723 : ignore_return_flags = true;
2412 2723 : break;
2413 :
2414 130 : case BUILT_IN_ALIGNED_ALLOC:
2415 130 : case BUILT_IN_GOMP_ALLOC:
2416 130 : {
2417 130 : tree align = get_constant_value (gimple_call_arg (stmt, 0));
2418 130 : if (align
2419 122 : && tree_fits_uhwi_p (align))
2420 : {
2421 122 : unsigned HOST_WIDE_INT aligni = tree_to_uhwi (align);
2422 122 : if (aligni > 1
2423 : /* align must be power-of-two */
2424 106 : && (aligni & (aligni - 1)) == 0)
2425 : {
2426 106 : val.lattice_val = CONSTANT;
2427 106 : val.value = build_int_cst (ptr_type_node, 0);
2428 106 : val.mask = -aligni;
2429 : }
2430 : }
2431 : break;
2432 : }
2433 :
2434 5169 : case BUILT_IN_BSWAP16:
2435 5169 : case BUILT_IN_BSWAP32:
2436 5169 : case BUILT_IN_BSWAP64:
2437 5169 : case BUILT_IN_BSWAP128:
2438 5169 : val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
2439 5169 : if (val.lattice_val == UNDEFINED)
2440 : break;
2441 5169 : else if (val.lattice_val == CONSTANT
2442 2471 : && val.value
2443 2471 : && TREE_CODE (val.value) == INTEGER_CST)
2444 : {
2445 2471 : tree type = TREE_TYPE (gimple_call_lhs (stmt));
2446 2471 : int prec = TYPE_PRECISION (type);
2447 2471 : wide_int wval = wi::to_wide (val.value);
2448 2471 : val.value
2449 2471 : = wide_int_to_tree (type,
2450 4942 : wi::bswap (wide_int::from (wval, prec,
2451 : UNSIGNED)));
2452 2471 : val.mask
2453 4942 : = widest_int::from (wi::bswap (wide_int::from (val.mask,
2454 : prec,
2455 : UNSIGNED)),
2456 2471 : UNSIGNED);
2457 2471 : if (wi::sext (val.mask, prec) != -1)
2458 : break;
2459 2471 : }
2460 2698 : val.lattice_val = VARYING;
2461 2698 : val.value = NULL_TREE;
2462 2698 : val.mask = -1;
2463 2698 : break;
2464 :
2465 151 : case BUILT_IN_BITREVERSE8:
2466 151 : case BUILT_IN_BITREVERSE16:
2467 151 : case BUILT_IN_BITREVERSE32:
2468 151 : case BUILT_IN_BITREVERSE64:
2469 151 : case BUILT_IN_BITREVERSE128:
2470 151 : val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
2471 151 : if (val.lattice_val == UNDEFINED)
2472 : break;
2473 151 : else if (val.lattice_val == CONSTANT
2474 11 : && val.value
2475 11 : && TREE_CODE (val.value) == INTEGER_CST)
2476 : {
2477 11 : tree type = TREE_TYPE (gimple_call_lhs (stmt));
2478 11 : int prec = TYPE_PRECISION (type);
2479 11 : wide_int wval = wi::to_wide (val.value);
2480 11 : wval = wide_int::from (wval, prec, UNSIGNED);
2481 11 : wide_int wmask = wide_int::from (val.mask, prec, UNSIGNED);
2482 11 : val.value = wide_int_to_tree (type, wi::bitreverse (wval));
2483 22 : val.mask = widest_int::from (wi::bitreverse (wmask),
2484 11 : UNSIGNED);
2485 11 : if (wi::sext (val.mask, prec) != -1)
2486 : break;
2487 11 : }
2488 141 : val.lattice_val = VARYING;
2489 141 : val.value = NULL_TREE;
2490 141 : val.mask = -1;
2491 141 : break;
2492 :
2493 0 : default:;
2494 : }
2495 : }
2496 223420900 : if (is_gimple_call (stmt) && gimple_call_lhs (stmt))
2497 : {
2498 4307814 : tree fntype = gimple_call_fntype (stmt);
2499 4307814 : if (fntype)
2500 : {
2501 3826527 : tree attrs = lookup_attribute ("assume_aligned",
2502 3826527 : TYPE_ATTRIBUTES (fntype));
2503 3826527 : if (attrs)
2504 42 : val = bit_value_assume_aligned (stmt, attrs, val, false);
2505 3826527 : attrs = lookup_attribute ("alloc_align",
2506 3826527 : TYPE_ATTRIBUTES (fntype));
2507 3826527 : if (attrs)
2508 4886 : val = bit_value_assume_aligned (stmt, attrs, val, true);
2509 : }
2510 4307814 : int flags = ignore_return_flags
2511 4307814 : ? 0 : gimple_call_return_flags (as_a <gcall *> (stmt));
2512 4305091 : if (flags & ERF_RETURNS_ARG
2513 4305091 : && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
2514 : {
2515 169880 : val = get_value_for_expr
2516 339760 : (gimple_call_arg (stmt,
2517 169880 : flags & ERF_RETURN_ARG_MASK), true);
2518 : }
2519 : }
2520 223420900 : is_constant = (val.lattice_val == CONSTANT);
2521 : }
2522 :
2523 223501532 : tree lhs = gimple_get_lhs (stmt);
2524 223501532 : if (flag_tree_bit_ccp
2525 223421636 : && lhs && TREE_CODE (lhs) == SSA_NAME && !VECTOR_TYPE_P (TREE_TYPE (lhs))
2526 404961318 : && ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
2527 : || !is_constant))
2528 : {
2529 181459786 : tree lhs = gimple_get_lhs (stmt);
2530 181459786 : wide_int nonzero_bits = get_nonzero_bits (lhs);
2531 181459786 : if (nonzero_bits != -1)
2532 : {
2533 50924384 : if (!is_constant)
2534 : {
2535 3466989 : val.lattice_val = CONSTANT;
2536 3466989 : val.value = build_zero_cst (TREE_TYPE (lhs));
2537 3466989 : val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (lhs)));
2538 3466989 : is_constant = true;
2539 : }
2540 : else
2541 : {
2542 47457513 : if (wi::bit_and_not (wi::to_wide (val.value), nonzero_bits) != 0)
2543 62318 : val.value = wide_int_to_tree (TREE_TYPE (lhs),
2544 : nonzero_bits
2545 124636 : & wi::to_wide (val.value));
2546 47457395 : if (nonzero_bits == 0)
2547 419 : val.mask = 0;
2548 : else
2549 94914051 : val.mask = val.mask & extend_mask (nonzero_bits,
2550 94913952 : TYPE_SIGN (TREE_TYPE (lhs)));
2551 : }
2552 : }
2553 181459786 : }
2554 :
2555 : /* The statement produced a nonconstant value. */
2556 223501532 : if (!is_constant)
2557 : {
2558 : /* The statement produced a copy. */
2559 13984350 : if (simplified && TREE_CODE (simplified) == SSA_NAME
2560 83913723 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (simplified))
2561 : {
2562 11631107 : val.lattice_val = CONSTANT;
2563 11631107 : val.value = simplified;
2564 11631107 : val.mask = -1;
2565 : }
2566 : /* The statement is VARYING. */
2567 : else
2568 : {
2569 60649802 : val.lattice_val = VARYING;
2570 60649802 : val.value = NULL_TREE;
2571 60649802 : val.mask = -1;
2572 : }
2573 : }
2574 :
2575 223501532 : return val;
2576 237539959 : }
2577 :
2578 : typedef hash_table<nofree_ptr_hash<gimple> > gimple_htab;
2579 :
2580 : /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
2581 : each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
2582 :
2583 : static void
2584 498 : insert_clobber_before_stack_restore (tree saved_val, tree var,
2585 : gimple_htab **visited)
2586 : {
2587 498 : gimple *stmt;
2588 498 : gassign *clobber_stmt;
2589 498 : tree clobber;
2590 498 : imm_use_iterator iter;
2591 498 : gimple_stmt_iterator i;
2592 498 : gimple **slot;
2593 :
2594 1000 : FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
2595 502 : if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
2596 : {
2597 489 : clobber = build_clobber (TREE_TYPE (var), CLOBBER_STORAGE_END);
2598 489 : clobber_stmt = gimple_build_assign (var, clobber);
2599 : /* Manually update the vdef/vuse here. */
2600 978 : gimple_set_vuse (clobber_stmt, gimple_vuse (stmt));
2601 489 : gimple_set_vdef (clobber_stmt, make_ssa_name (gimple_vop (cfun)));
2602 978 : gimple_set_vuse (stmt, gimple_vdef (clobber_stmt));
2603 978 : SSA_NAME_DEF_STMT (gimple_vdef (clobber_stmt)) = clobber_stmt;
2604 489 : update_stmt (stmt);
2605 489 : i = gsi_for_stmt (stmt);
2606 489 : gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
2607 : }
2608 13 : else if (gimple_code (stmt) == GIMPLE_PHI)
2609 : {
2610 12 : if (!*visited)
2611 12 : *visited = new gimple_htab (10);
2612 :
2613 12 : slot = (*visited)->find_slot (stmt, INSERT);
2614 12 : if (*slot != NULL)
2615 0 : continue;
2616 :
2617 12 : *slot = stmt;
2618 12 : insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
2619 : visited);
2620 : }
2621 1 : else if (gimple_assign_ssa_name_copy_p (stmt))
2622 0 : insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var,
2623 498 : visited);
2624 498 : }
2625 :
2626 : /* Advance the iterator to the previous non-debug gimple statement in the same
2627 : or dominating basic block. */
2628 :
2629 : static inline void
2630 11412 : gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
2631 : {
2632 11412 : basic_block dom;
2633 :
2634 11412 : gsi_prev_nondebug (i);
2635 23358 : while (gsi_end_p (*i))
2636 : {
2637 542 : dom = get_immediate_dominator (CDI_DOMINATORS, gsi_bb (*i));
2638 542 : if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2639 : return;
2640 :
2641 1068 : *i = gsi_last_bb (dom);
2642 : }
2643 : }
2644 :
2645 : /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
2646 : a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
2647 :
2648 : It is possible that BUILT_IN_STACK_SAVE cannot be found in a dominator when
2649 : a previous pass (such as DOM) duplicated it along multiple paths to a BB.
2650 : In that case the function gives up without inserting the clobbers. */
2651 :
2652 : static void
2653 494 : insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
2654 : {
2655 494 : gimple *stmt;
2656 494 : tree saved_val;
2657 494 : gimple_htab *visited = NULL;
2658 :
2659 11906 : for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
2660 : {
2661 11898 : stmt = gsi_stmt (i);
2662 :
2663 11898 : if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
2664 11412 : continue;
2665 :
2666 486 : saved_val = gimple_call_lhs (stmt);
2667 486 : if (saved_val == NULL_TREE)
2668 0 : continue;
2669 :
2670 486 : insert_clobber_before_stack_restore (saved_val, var, &visited);
2671 486 : break;
2672 : }
2673 :
2674 494 : delete visited;
2675 494 : }
2676 :
2677 : /* Detects a __builtin_alloca_with_align with constant size argument. Declares
2678 : fixed-size array and returns the address, if found, otherwise returns
2679 : NULL_TREE. */
2680 :
2681 : static tree
2682 12018 : fold_builtin_alloca_with_align (gimple *stmt)
2683 : {
2684 12018 : unsigned HOST_WIDE_INT size, threshold, n_elem;
2685 12018 : tree lhs, arg, block, var, elem_type, array_type;
2686 :
2687 : /* Get lhs. */
2688 12018 : lhs = gimple_call_lhs (stmt);
2689 12018 : if (lhs == NULL_TREE)
2690 : return NULL_TREE;
2691 :
2692 : /* Detect constant argument. */
2693 12018 : arg = get_constant_value (gimple_call_arg (stmt, 0));
2694 12018 : if (arg == NULL_TREE
2695 1030 : || TREE_CODE (arg) != INTEGER_CST
2696 1030 : || !tree_fits_uhwi_p (arg))
2697 : return NULL_TREE;
2698 :
2699 1030 : size = tree_to_uhwi (arg);
2700 :
2701 : /* Heuristic: don't fold large allocas. */
2702 1030 : threshold = (unsigned HOST_WIDE_INT)param_large_stack_frame;
2703 : /* In case the alloca is located at function entry, it has the same lifetime
2704 : as a declared array, so we allow a larger size. */
2705 1030 : block = gimple_block (stmt);
2706 1030 : if (!(cfun->after_inlining
2707 669 : && block
2708 641 : && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
2709 645 : threshold /= 10;
2710 1030 : if (size > threshold)
2711 : return NULL_TREE;
2712 :
2713 : /* We have to be able to move points-to info. We used to assert
2714 : that we can but IPA PTA might end up with two UIDs here
2715 : as it might need to handle more than one instance being
2716 : live at the same time. Instead of trying to detect this case
2717 : (using the first UID would be OK) just give up for now. */
2718 500 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
2719 500 : unsigned uid = 0;
2720 500 : if (pi != NULL
2721 334 : && !pi->pt.anything
2722 644 : && !pt_solution_singleton_or_null_p (&pi->pt, &uid))
2723 : return NULL_TREE;
2724 :
2725 : /* Declare array. */
2726 494 : elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
2727 494 : n_elem = size * 8 / BITS_PER_UNIT;
2728 494 : array_type = build_array_type_nelts (elem_type, n_elem);
2729 :
2730 494 : if (tree ssa_name = SSA_NAME_IDENTIFIER (lhs))
2731 : {
2732 : /* Give the temporary a name derived from the name of the VLA
2733 : declaration so it can be referenced in diagnostics. */
2734 454 : const char *name = IDENTIFIER_POINTER (ssa_name);
2735 454 : var = create_tmp_var (array_type, name);
2736 : }
2737 : else
2738 40 : var = create_tmp_var (array_type);
2739 :
2740 494 : if (gimple *lhsdef = SSA_NAME_DEF_STMT (lhs))
2741 : {
2742 : /* Set the temporary's location to that of the VLA declaration
2743 : so it can be pointed to in diagnostics. */
2744 494 : location_t loc = gimple_location (lhsdef);
2745 494 : DECL_SOURCE_LOCATION (var) = loc;
2746 : }
2747 :
2748 494 : SET_DECL_ALIGN (var, TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2749 494 : if (uid != 0)
2750 138 : SET_DECL_PT_UID (var, uid);
2751 :
2752 : /* Fold alloca to the address of the array. */
2753 494 : return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
2754 : }
2755 :
2756 : /* Fold the stmt at *GSI with CCP specific information that propagating
2757 : and regular folding does not catch. */
2758 :
2759 : bool
2760 343138072 : ccp_folder::fold_stmt (gimple_stmt_iterator *gsi)
2761 : {
2762 343138072 : gimple *stmt = gsi_stmt (*gsi);
2763 :
2764 343138072 : switch (gimple_code (stmt))
2765 : {
2766 18642376 : case GIMPLE_COND:
2767 18642376 : {
2768 18642376 : gcond *cond_stmt = as_a <gcond *> (stmt);
2769 18642376 : ccp_prop_value_t val;
2770 : /* Statement evaluation will handle type mismatches in constants
2771 : more gracefully than the final propagation. This allows us to
2772 : fold more conditionals here. */
2773 18642376 : val = evaluate_stmt (stmt);
2774 18642376 : if (val.lattice_val != CONSTANT
2775 18642376 : || val.mask != 0)
2776 18168911 : return false;
2777 :
2778 473465 : if (dump_file)
2779 : {
2780 24 : fprintf (dump_file, "Folding predicate ");
2781 24 : print_gimple_expr (dump_file, stmt, 0);
2782 24 : fprintf (dump_file, " to ");
2783 24 : print_generic_expr (dump_file, val.value);
2784 24 : fprintf (dump_file, "\n");
2785 : }
2786 :
2787 473465 : if (integer_zerop (val.value))
2788 362751 : gimple_cond_make_false (cond_stmt);
2789 : else
2790 110714 : gimple_cond_make_true (cond_stmt);
2791 :
2792 : return true;
2793 18642376 : }
2794 :
2795 23482902 : case GIMPLE_CALL:
2796 23482902 : {
2797 23482902 : tree lhs = gimple_call_lhs (stmt);
2798 23482902 : int flags = gimple_call_flags (stmt);
2799 23482902 : tree val;
2800 23482902 : tree argt;
2801 23482902 : bool changed = false;
2802 23482902 : unsigned i;
2803 :
2804 : /* If the call was folded into a constant make sure it goes
2805 : away even if we cannot propagate into all uses because of
2806 : type issues. */
2807 23482902 : if (lhs
2808 8941495 : && TREE_CODE (lhs) == SSA_NAME
2809 7498714 : && (val = get_constant_value (lhs))
2810 : /* Don't optimize away calls that have side-effects. */
2811 15 : && (flags & (ECF_CONST|ECF_PURE)) != 0
2812 23482902 : && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
2813 : {
2814 0 : tree new_rhs = unshare_expr (val);
2815 0 : if (!useless_type_conversion_p (TREE_TYPE (lhs),
2816 0 : TREE_TYPE (new_rhs)))
2817 0 : new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
2818 0 : gimplify_and_update_call_from_tree (gsi, new_rhs);
2819 0 : return true;
2820 : }
2821 :
2822 : /* Internal calls provide no argument types, so the extra laxity
2823 : for normal calls does not apply. */
2824 23482902 : if (gimple_call_internal_p (stmt))
2825 : return false;
2826 :
2827 : /* The heuristic of fold_builtin_alloca_with_align differs before and
2828 : after inlining, so we don't require the arg to be changed into a
2829 : constant for folding, but just to be constant. */
2830 22757297 : if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)
2831 22757297 : || gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
2832 : {
2833 12018 : tree new_rhs = fold_builtin_alloca_with_align (stmt);
2834 12018 : if (new_rhs)
2835 : {
2836 494 : gimplify_and_update_call_from_tree (gsi, new_rhs);
2837 494 : tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
2838 494 : insert_clobbers_for_var (*gsi, var);
2839 494 : return true;
2840 : }
2841 : }
2842 :
2843 : /* If there's no extra info from an assume_aligned call,
2844 : drop it so it doesn't act as otherwise useless dataflow
2845 : barrier. */
2846 22756803 : if (gimple_call_builtin_p (stmt, BUILT_IN_ASSUME_ALIGNED))
2847 : {
2848 2723 : tree ptr = gimple_call_arg (stmt, 0);
2849 2723 : ccp_prop_value_t ptrval = get_value_for_expr (ptr, true);
2850 2723 : if (ptrval.lattice_val == CONSTANT
2851 268 : && TREE_CODE (ptrval.value) == INTEGER_CST
2852 2991 : && ptrval.mask != 0)
2853 : {
2854 268 : ccp_prop_value_t val
2855 268 : = bit_value_assume_aligned (stmt, NULL_TREE, ptrval, false);
2856 268 : unsigned int ptralign = least_bit_hwi (ptrval.mask.to_uhwi ());
2857 268 : unsigned int align = least_bit_hwi (val.mask.to_uhwi ());
2858 268 : if (ptralign == align
2859 268 : && ((TREE_INT_CST_LOW (ptrval.value) & (align - 1))
2860 256 : == (TREE_INT_CST_LOW (val.value) & (align - 1))))
2861 : {
2862 256 : replace_call_with_value (gsi, ptr);
2863 256 : return true;
2864 : }
2865 268 : }
2866 2723 : }
2867 :
2868 : /* Propagate into the call arguments. Compared to replace_uses_in
2869 : this can use the argument slot types for type verification
2870 : instead of the current argument type. We also can safely
2871 : drop qualifiers here as we are dealing with constants anyway. */
2872 22756547 : argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
2873 62953077 : for (i = 0; i < gimple_call_num_args (stmt) && argt;
2874 40196530 : ++i, argt = TREE_CHAIN (argt))
2875 : {
2876 40196530 : tree arg = gimple_call_arg (stmt, i);
2877 40196530 : if (TREE_CODE (arg) == SSA_NAME
2878 15659506 : && (val = get_constant_value (arg))
2879 40196555 : && useless_type_conversion_p
2880 25 : (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
2881 25 : TYPE_MAIN_VARIANT (TREE_TYPE (val))))
2882 : {
2883 25 : gimple_call_set_arg (stmt, i, unshare_expr (val));
2884 25 : changed = true;
2885 : }
2886 : }
2887 :
2888 : return changed;
2889 : }
2890 :
2891 105448437 : case GIMPLE_ASSIGN:
2892 105448437 : {
2893 105448437 : tree lhs = gimple_assign_lhs (stmt);
2894 105448437 : tree val;
2895 :
2896 : /* If we have a load that turned out to be constant replace it
2897 : as we cannot propagate into all uses in all cases. */
2898 105448437 : if (gimple_assign_single_p (stmt)
2899 70319291 : && TREE_CODE (lhs) == SSA_NAME
2900 138014373 : && (val = get_constant_value (lhs)))
2901 : {
2902 5176 : tree rhs = unshare_expr (val);
2903 5176 : if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2904 0 : rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2905 5176 : gimple_assign_set_rhs_from_tree (gsi, rhs);
2906 5176 : return true;
2907 : }
2908 :
2909 : return false;
2910 : }
2911 :
2912 : default:
2913 : return false;
2914 : }
2915 : }
2916 :
2917 : /* Visit the assignment statement STMT. Set the value of its LHS to the
2918 : value computed by the RHS and store LHS in *OUTPUT_P. If STMT
2919 : creates virtual definitions, set the value of each new name to that
2920 : of the RHS (if we can derive a constant out of the RHS).
2921 : Value-returning call statements also perform an assignment, and
2922 : are handled here. */
2923 :
2924 : static enum ssa_prop_result
2925 196673781 : visit_assignment (gimple *stmt, tree *output_p)
2926 : {
2927 196673781 : ccp_prop_value_t val;
2928 196673781 : enum ssa_prop_result retval = SSA_PROP_NOT_INTERESTING;
2929 :
2930 196673781 : tree lhs = gimple_get_lhs (stmt);
2931 196673781 : if (TREE_CODE (lhs) == SSA_NAME)
2932 : {
2933 : /* Evaluate the statement, which could be
2934 : either a GIMPLE_ASSIGN or a GIMPLE_CALL. */
2935 195296536 : val = evaluate_stmt (stmt);
2936 :
2937 : /* If STMT is an assignment to an SSA_NAME, we only have one
2938 : value to set. */
2939 195296536 : if (set_lattice_value (lhs, &val))
2940 : {
2941 181792294 : *output_p = lhs;
2942 181792294 : if (val.lattice_val == VARYING)
2943 : retval = SSA_PROP_VARYING;
2944 : else
2945 124140273 : retval = SSA_PROP_INTERESTING;
2946 : }
2947 : }
2948 :
2949 196673781 : return retval;
2950 196673781 : }
2951 :
2952 :
2953 : /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
2954 : if it can determine which edge will be taken. Otherwise, return
2955 : SSA_PROP_VARYING. */
2956 :
2957 : static enum ssa_prop_result
2958 23601047 : visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
2959 : {
2960 23601047 : ccp_prop_value_t val;
2961 23601047 : basic_block block;
2962 :
2963 23601047 : block = gimple_bb (stmt);
2964 23601047 : val = evaluate_stmt (stmt);
2965 23601047 : if (val.lattice_val != CONSTANT
2966 23601047 : || val.mask != 0)
2967 18160073 : return SSA_PROP_VARYING;
2968 :
2969 : /* Find which edge out of the conditional block will be taken and add it
2970 : to the worklist. If no single edge can be determined statically,
2971 : return SSA_PROP_VARYING to feed all the outgoing edges to the
2972 : propagation engine. */
2973 5440974 : *taken_edge_p = find_taken_edge (block, val.value);
2974 5440974 : if (*taken_edge_p)
2975 : return SSA_PROP_INTERESTING;
2976 : else
2977 : return SSA_PROP_VARYING;
2978 23601047 : }
2979 :
2980 :
2981 : /* Evaluate statement STMT. If the statement produces an output value and
2982 : its evaluation changes the lattice value of its output, return
2983 : SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2984 : output value.
2985 :
2986 : If STMT is a conditional branch and we can determine its truth
2987 : value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
2988 : value, return SSA_PROP_VARYING. */
2989 :
2990 : enum ssa_prop_result
2991 232218431 : ccp_propagate::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
2992 : {
2993 232218431 : tree def;
2994 232218431 : ssa_op_iter iter;
2995 :
2996 232218431 : if (dump_file && (dump_flags & TDF_DETAILS))
2997 : {
2998 100 : fprintf (dump_file, "\nVisiting statement:\n");
2999 100 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
3000 : }
3001 :
3002 232218431 : switch (gimple_code (stmt))
3003 : {
3004 191430340 : case GIMPLE_ASSIGN:
3005 : /* If the statement is an assignment that produces a single
3006 : output value, evaluate its RHS to see if the lattice value of
3007 : its output has changed. */
3008 191430340 : return visit_assignment (stmt, output_p);
3009 :
3010 10583477 : case GIMPLE_CALL:
3011 : /* A value-returning call also performs an assignment. */
3012 10583477 : if (gimple_call_lhs (stmt) != NULL_TREE)
3013 5243441 : return visit_assignment (stmt, output_p);
3014 : break;
3015 :
3016 23601047 : case GIMPLE_COND:
3017 23601047 : case GIMPLE_SWITCH:
3018 : /* If STMT is a conditional branch, see if we can determine
3019 : which branch will be taken. */
3020 : /* FIXME. It appears that we should be able to optimize
3021 : computed GOTOs here as well. */
3022 23601047 : return visit_cond_stmt (stmt, taken_edge_p);
3023 :
3024 : default:
3025 : break;
3026 : }
3027 :
3028 : /* Any other kind of statement is not interesting for constant
3029 : propagation and, therefore, not worth simulating. */
3030 11943603 : if (dump_file && (dump_flags & TDF_DETAILS))
3031 42 : fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
3032 :
3033 : /* Definitions made by statements other than assignments to
3034 : SSA_NAMEs represent unknown modifications to their outputs.
3035 : Mark them VARYING. */
3036 16612000 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
3037 4668397 : set_value_varying (def);
3038 :
3039 : return SSA_PROP_VARYING;
3040 : }
3041 :
3042 :
3043 : /* Main entry point for SSA Conditional Constant Propagation. If NONZERO_P,
3044 : record nonzero bits. */
3045 :
3046 : static unsigned int
3047 5568786 : do_ssa_ccp (bool nonzero_p)
3048 : {
3049 5568786 : unsigned int todo = 0;
3050 5568786 : calculate_dominance_info (CDI_DOMINATORS);
3051 :
3052 5568786 : ccp_initialize ();
3053 5568786 : class ccp_propagate ccp_propagate;
3054 5568786 : ccp_propagate.ssa_propagate ();
3055 11031006 : if (ccp_finalize (nonzero_p || flag_ipa_bit_cp))
3056 : {
3057 1653704 : todo = TODO_cleanup_cfg;
3058 :
3059 : /* ccp_finalize does not preserve loop-closed ssa. */
3060 1653704 : loops_state_clear (LOOP_CLOSED_SSA);
3061 : }
3062 :
3063 5568786 : free_dominance_info (CDI_DOMINATORS);
3064 5568786 : return todo;
3065 5568786 : }
3066 :
3067 :
3068 : namespace {
3069 :
3070 : const pass_data pass_data_ccp =
3071 : {
3072 : GIMPLE_PASS, /* type */
3073 : "ccp", /* name */
3074 : OPTGROUP_NONE, /* optinfo_flags */
3075 : TV_TREE_CCP, /* tv_id */
3076 : ( PROP_cfg | PROP_ssa ), /* properties_required */
3077 : 0, /* properties_provided */
3078 : 0, /* properties_destroyed */
3079 : 0, /* todo_flags_start */
3080 : TODO_update_address_taken, /* todo_flags_finish */
3081 : };
3082 :
3083 : class pass_ccp : public gimple_opt_pass
3084 : {
3085 : public:
3086 1443835 : pass_ccp (gcc::context *ctxt)
3087 2887670 : : gimple_opt_pass (pass_data_ccp, ctxt), nonzero_p (false)
3088 : {}
3089 :
3090 : /* opt_pass methods: */
3091 1155068 : opt_pass * clone () final override { return new pass_ccp (m_ctxt); }
3092 1443835 : void set_pass_param (unsigned int n, bool param) final override
3093 : {
3094 1443835 : gcc_assert (n == 0);
3095 1443835 : nonzero_p = param;
3096 1443835 : }
3097 5570686 : bool gate (function *) final override { return flag_tree_ccp != 0; }
3098 5568786 : unsigned int execute (function *) final override
3099 : {
3100 5568786 : return do_ssa_ccp (nonzero_p);
3101 : }
3102 :
3103 : private:
3104 : /* Determines whether the pass instance records nonzero bits. */
3105 : bool nonzero_p;
3106 : }; // class pass_ccp
3107 :
3108 : } // anon namespace
3109 :
3110 : gimple_opt_pass *
3111 288767 : make_pass_ccp (gcc::context *ctxt)
3112 : {
3113 288767 : return new pass_ccp (ctxt);
3114 : }
3115 :
3116 : /* A simple pass that emits some warnings post IPA. */
3117 :
3118 : namespace {
3119 :
3120 : const pass_data pass_data_post_ipa_warn =
3121 : {
3122 : GIMPLE_PASS, /* type */
3123 : "post_ipa_warn", /* name */
3124 : OPTGROUP_NONE, /* optinfo_flags */
3125 : TV_NONE, /* tv_id */
3126 : ( PROP_cfg | PROP_ssa ), /* properties_required */
3127 : 0, /* properties_provided */
3128 : 0, /* properties_destroyed */
3129 : 0, /* todo_flags_start */
3130 : 0, /* todo_flags_finish */
3131 : };
3132 :
3133 : class pass_post_ipa_warn : public gimple_opt_pass
3134 : {
3135 : public:
3136 577534 : pass_post_ipa_warn (gcc::context *ctxt)
3137 1155068 : : gimple_opt_pass (pass_data_post_ipa_warn, ctxt)
3138 : {}
3139 :
3140 : /* opt_pass methods: */
3141 288767 : opt_pass * clone () final override { return new pass_post_ipa_warn (m_ctxt); }
3142 1046732 : bool gate (function *) final override { return warn_nonnull != 0; }
3143 : unsigned int execute (function *) final override;
3144 :
3145 : }; // class pass_fold_builtins
3146 :
3147 : unsigned int
3148 112823 : pass_post_ipa_warn::execute (function *fun)
3149 : {
3150 112823 : basic_block bb;
3151 112823 : gimple_ranger *ranger = NULL;
3152 :
3153 1130020 : FOR_EACH_BB_FN (bb, fun)
3154 : {
3155 1017197 : gimple_stmt_iterator gsi;
3156 10958061 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3157 : {
3158 8923667 : gimple *stmt = gsi_stmt (gsi);
3159 8923667 : if (!is_gimple_call (stmt) || warning_suppressed_p (stmt, OPT_Wnonnull))
3160 8368169 : continue;
3161 :
3162 555498 : tree fntype = gimple_call_fntype (stmt);
3163 555498 : if (!fntype)
3164 5525 : continue;
3165 549973 : bitmap nonnullargs = get_nonnull_args (fntype);
3166 :
3167 549973 : tree fndecl = gimple_call_fndecl (stmt);
3168 1066614 : const bool closure = fndecl && DECL_LAMBDA_FUNCTION_P (fndecl);
3169 :
3170 808647 : for (unsigned i = nonnullargs ? 0 : ~0U;
3171 808647 : i < gimple_call_num_args (stmt); i++)
3172 : {
3173 258674 : tree arg = gimple_call_arg (stmt, i);
3174 258674 : if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE)
3175 258569 : continue;
3176 162369 : if (!integer_zerop (arg))
3177 154139 : continue;
3178 8230 : if (i == 0 && closure)
3179 : /* Avoid warning for the first argument to lambda functions. */
3180 18 : continue;
3181 8212 : if (!bitmap_empty_p (nonnullargs)
3182 8212 : && !bitmap_bit_p (nonnullargs, i))
3183 8092 : continue;
3184 :
3185 : /* In C++ non-static member functions argument 0 refers
3186 : to the implicit this pointer. Use the same one-based
3187 : numbering for ordinary arguments. */
3188 120 : unsigned argno = TREE_CODE (fntype) == METHOD_TYPE ? i : i + 1;
3189 120 : location_t loc = (EXPR_HAS_LOCATION (arg)
3190 0 : ? EXPR_LOCATION (arg)
3191 120 : : gimple_location (stmt));
3192 120 : auto_diagnostic_group d;
3193 120 : if (argno == 0)
3194 : {
3195 21 : if (warning_at (loc, OPT_Wnonnull,
3196 : "%qs pointer is null", "this")
3197 15 : && fndecl)
3198 9 : inform (DECL_SOURCE_LOCATION (fndecl),
3199 : "in a call to non-static member function %qD",
3200 : fndecl);
3201 15 : continue;
3202 : }
3203 :
3204 105 : if (!warning_at (loc, OPT_Wnonnull,
3205 : "argument %u null where non-null "
3206 : "expected", argno))
3207 0 : continue;
3208 :
3209 105 : tree fndecl = gimple_call_fndecl (stmt);
3210 105 : if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
3211 53 : inform (loc, "in a call to built-in function %qD",
3212 : fndecl);
3213 52 : else if (fndecl)
3214 52 : inform (DECL_SOURCE_LOCATION (fndecl),
3215 : "in a call to function %qD declared %qs",
3216 : fndecl, "nonnull");
3217 120 : }
3218 549973 : BITMAP_FREE (nonnullargs);
3219 :
3220 549973 : for (tree attrs = TYPE_ATTRIBUTES (fntype);
3221 588177 : (attrs = lookup_attribute ("nonnull_if_nonzero", attrs));
3222 38204 : attrs = TREE_CHAIN (attrs))
3223 : {
3224 38204 : tree args = TREE_VALUE (attrs);
3225 38204 : unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (args)) - 1;
3226 38204 : unsigned int idx2
3227 38204 : = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (args))) - 1;
3228 38204 : unsigned int idx3 = idx2;
3229 38204 : if (tree chain2 = TREE_CHAIN (TREE_CHAIN (args)))
3230 900 : idx3 = TREE_INT_CST_LOW (TREE_VALUE (chain2)) - 1;
3231 38204 : if (idx < gimple_call_num_args (stmt)
3232 38203 : && idx2 < gimple_call_num_args (stmt)
3233 76406 : && idx3 < gimple_call_num_args (stmt))
3234 : {
3235 38202 : tree arg = gimple_call_arg (stmt, idx);
3236 38202 : tree arg2 = gimple_call_arg (stmt, idx2);
3237 38202 : tree arg3 = gimple_call_arg (stmt, idx3);
3238 38202 : if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE
3239 38113 : || !integer_zerop (arg)
3240 290 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg2))
3241 290 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg3))
3242 290 : || integer_zerop (arg2)
3243 214 : || integer_zerop (arg3)
3244 38388 : || ((TREE_CODE (fntype) == METHOD_TYPE || closure)
3245 0 : && (idx == 0 || idx2 == 0 || idx3 == 0)))
3246 38072 : continue;
3247 186 : if (!integer_nonzerop (arg2)
3248 186 : && !tree_expr_nonzero_p (arg2))
3249 : {
3250 98 : if (TREE_CODE (arg2) != SSA_NAME || optimize < 2)
3251 56 : continue;
3252 98 : if (!ranger)
3253 14 : ranger = enable_ranger (cfun);
3254 :
3255 98 : int_range_max vr;
3256 196 : get_range_query (cfun)->range_of_expr (vr, arg2, stmt);
3257 98 : if (range_includes_zero_p (vr))
3258 56 : continue;
3259 98 : }
3260 130 : if (idx2 != idx3
3261 45 : && !integer_nonzerop (arg3)
3262 153 : && !tree_expr_nonzero_p (arg3))
3263 : {
3264 20 : if (TREE_CODE (arg3) != SSA_NAME || optimize < 2)
3265 0 : continue;
3266 20 : if (!ranger)
3267 0 : ranger = enable_ranger (cfun);
3268 :
3269 20 : int_range_max vr;
3270 40 : get_range_query (cfun)->range_of_expr (vr, arg3, stmt);
3271 20 : if (range_includes_zero_p (vr))
3272 0 : continue;
3273 20 : }
3274 130 : unsigned argno = idx + 1;
3275 130 : unsigned argno2 = idx2 + 1;
3276 130 : unsigned argno3 = idx3 + 1;
3277 130 : location_t loc = (EXPR_HAS_LOCATION (arg)
3278 0 : ? EXPR_LOCATION (arg)
3279 130 : : gimple_location (stmt));
3280 130 : auto_diagnostic_group d;
3281 :
3282 130 : if (idx2 != idx3)
3283 : {
3284 45 : if (!warning_at (loc, OPT_Wnonnull,
3285 : "argument %u null where non-null "
3286 : "expected because arguments %u and %u "
3287 : "are nonzero", argno, argno2, argno3))
3288 0 : continue;
3289 : }
3290 85 : else if (!warning_at (loc, OPT_Wnonnull,
3291 : "argument %u null where non-null "
3292 : "expected because argument %u is "
3293 : "nonzero", argno, argno2))
3294 0 : continue;
3295 :
3296 130 : tree fndecl = gimple_call_fndecl (stmt);
3297 130 : if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
3298 37 : inform (loc, "in a call to built-in function %qD",
3299 : fndecl);
3300 93 : else if (fndecl)
3301 93 : inform (DECL_SOURCE_LOCATION (fndecl),
3302 : "in a call to function %qD declared %qs",
3303 : fndecl, "nonnull_if_nonzero");
3304 130 : }
3305 : }
3306 : }
3307 : }
3308 112823 : if (ranger)
3309 14 : disable_ranger (cfun);
3310 112823 : return 0;
3311 : }
3312 :
3313 : } // anon namespace
3314 :
3315 : gimple_opt_pass *
3316 288767 : make_pass_post_ipa_warn (gcc::context *ctxt)
3317 : {
3318 288767 : return new pass_post_ipa_warn (ctxt);
3319 : }
|
