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 information 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 527032850 : 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 5714131 : 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 0 : case UNDEFINED:
214 0 : fprintf (outf, "%sUNDEFINED", prefix);
215 0 : break;
216 16 : case VARYING:
217 16 : fprintf (outf, "%sVARYING", prefix);
218 16 : 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 53689399 : extend_mask (const wide_int &nonzero_bits, signop sgn)
258 : {
259 53689399 : 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 10706786 : get_default_value (tree var)
282 : {
283 10706786 : ccp_prop_value_t val = { UNINITIALIZED, NULL_TREE, 0 };
284 10706786 : gimple *stmt;
285 :
286 10706786 : stmt = SSA_NAME_DEF_STMT (var);
287 :
288 10706786 : 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 9951234 : if (!virtual_operand_p (var)
295 9951234 : && SSA_NAME_VAR (var)
296 19902317 : && VAR_P (SSA_NAME_VAR (var)))
297 1631847 : val.lattice_val = UNDEFINED;
298 : else
299 : {
300 8319387 : val.lattice_val = VARYING;
301 8319387 : val.mask = -1;
302 8319387 : if (flag_tree_bit_ccp && !VECTOR_TYPE_P (TREE_TYPE (var)))
303 : {
304 7870096 : wide_int nonzero_bits = get_nonzero_bits (var);
305 7870096 : tree value;
306 7870096 : widest_int mask;
307 :
308 7870096 : if (SSA_NAME_VAR (var)
309 7869945 : && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
310 7804749 : && ipcp_get_parm_bits (SSA_NAME_VAR (var), &value, &mask))
311 : {
312 84751 : val.lattice_val = CONSTANT;
313 84751 : val.value = value;
314 84751 : widest_int ipa_value = wi::to_widest (value);
315 : /* Unknown bits from IPA CP must be equal to zero. */
316 84751 : gcc_assert (wi::bit_and (ipa_value, mask) == 0);
317 84751 : val.mask = mask;
318 84751 : if (nonzero_bits != -1)
319 68339 : val.mask &= extend_mask (nonzero_bits,
320 68339 : TYPE_SIGN (TREE_TYPE (var)));
321 84751 : }
322 7785345 : else if (nonzero_bits != -1)
323 : {
324 2127 : val.lattice_val = CONSTANT;
325 2127 : val.value = build_zero_cst (TREE_TYPE (var));
326 2127 : val.mask = extend_mask (nonzero_bits,
327 2127 : TYPE_SIGN (TREE_TYPE (var)));
328 : }
329 7870415 : }
330 : }
331 : }
332 755552 : else if (is_gimple_assign (stmt))
333 : {
334 653527 : tree cst;
335 653527 : if (gimple_assign_single_p (stmt)
336 297290 : && DECL_P (gimple_assign_rhs1 (stmt))
337 666245 : && (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 653430 : val.lattice_val = UNDEFINED;
347 : }
348 : }
349 102025 : else if ((is_gimple_call (stmt)
350 22458 : && gimple_call_lhs (stmt) != NULL_TREE)
351 102025 : || gimple_code (stmt) == GIMPLE_PHI)
352 : {
353 : /* A variable defined by a call or a PHI node is considered
354 : UNDEFINED. */
355 101968 : 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 10706786 : return val;
365 : }
366 :
367 :
368 : /* Get the constant value associated with variable VAR. */
369 :
370 : static inline ccp_prop_value_t *
371 3257791605 : get_value (tree var)
372 : {
373 3257791605 : ccp_prop_value_t *val;
374 :
375 3257791605 : if (const_val == NULL
376 6515583210 : || SSA_NAME_VERSION (var) >= n_const_val)
377 : return NULL;
378 :
379 3257784284 : val = &const_val[SSA_NAME_VERSION (var)];
380 3257784284 : if (val->lattice_val == UNINITIALIZED)
381 10706786 : *val = get_default_value (var);
382 :
383 3257784284 : canonicalize_value (val);
384 :
385 3257784284 : return val;
386 : }
387 :
388 : /* Return the constant tree value associated with VAR. */
389 :
390 : static inline tree
391 2573834633 : get_constant_value (tree var)
392 : {
393 2573834633 : ccp_prop_value_t *val;
394 2573834633 : if (TREE_CODE (var) != SSA_NAME)
395 : {
396 1211 : if (is_gimple_min_invariant (var))
397 : return var;
398 0 : return NULL_TREE;
399 : }
400 2573833422 : val = get_value (var);
401 2573833422 : if (val
402 2573826335 : && val->lattice_val == CONSTANT
403 3055603592 : && (TREE_CODE (val->value) != INTEGER_CST
404 2573833422 : || val->mask == 0))
405 : return val->value;
406 : return NULL_TREE;
407 : }
408 :
409 : /* Sets the value associated with VAR to VARYING. */
410 :
411 : static inline void
412 61648400 : set_value_varying (tree var)
413 : {
414 61648400 : ccp_prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
415 :
416 61648400 : val->lattice_val = VARYING;
417 61648400 : val->value = NULL_TREE;
418 61648400 : val->mask = -1;
419 61648400 : }
420 :
421 : /* For integer constants, make sure to drop TREE_OVERFLOW. */
422 :
423 : static void
424 3682919331 : canonicalize_value (ccp_prop_value_t *val)
425 : {
426 3682919331 : if (val->lattice_val != CONSTANT)
427 : return;
428 :
429 1270542333 : if (TREE_OVERFLOW_P (val->value))
430 58 : val->value = drop_tree_overflow (val->value);
431 : }
432 :
433 : /* Return whether the lattice transition is valid. */
434 :
435 : static bool
436 272349431 : valid_lattice_transition (const ccp_prop_value_t &old_val,
437 : const ccp_prop_value_t &new_val)
438 : {
439 : /* Lattice transitions must always be monotonically increasing in
440 : value. */
441 272349431 : if (old_val.lattice_val < new_val.lattice_val)
442 : return true;
443 :
444 170097165 : if (old_val.lattice_val != new_val.lattice_val)
445 : return false;
446 :
447 170097165 : if (!old_val.value && !new_val.value)
448 : return true;
449 :
450 : /* Now both lattice values are CONSTANT. */
451 :
452 : /* Allow arbitrary copy changes as we might look through PHI <a_1, ...>
453 : when only a single copy edge is executable. */
454 170062038 : if (TREE_CODE (old_val.value) == SSA_NAME
455 30756 : && TREE_CODE (new_val.value) == SSA_NAME)
456 : return true;
457 :
458 : /* Allow transitioning from a constant to a copy. */
459 170031282 : if (is_gimple_min_invariant (old_val.value)
460 170031282 : && TREE_CODE (new_val.value) == SSA_NAME)
461 : return true;
462 :
463 : /* Allow transitioning from PHI <&x, not executable> == &x
464 : to PHI <&x, &y> == common alignment. */
465 169797239 : if (TREE_CODE (old_val.value) != INTEGER_CST
466 443837 : && TREE_CODE (new_val.value) == INTEGER_CST)
467 : return true;
468 :
469 : /* Bit-lattices have to agree in the still valid bits. */
470 169379549 : if (TREE_CODE (old_val.value) == INTEGER_CST
471 169353402 : && TREE_CODE (new_val.value) == INTEGER_CST)
472 338706804 : return (wi::bit_and_not (wi::to_widest (old_val.value), new_val.mask)
473 508060206 : == wi::bit_and_not (wi::to_widest (new_val.value), new_val.mask));
474 :
475 : /* Otherwise constant values have to agree. */
476 26147 : if (operand_equal_p (old_val.value, new_val.value, 0))
477 : return true;
478 :
479 : /* At least the kinds and types should agree now. */
480 0 : if (TREE_CODE (old_val.value) != TREE_CODE (new_val.value)
481 0 : || !types_compatible_p (TREE_TYPE (old_val.value),
482 0 : TREE_TYPE (new_val.value)))
483 : return false;
484 :
485 : /* For floats and !HONOR_NANS allow transitions from (partial) NaN
486 : to non-NaN. */
487 0 : tree type = TREE_TYPE (new_val.value);
488 0 : if (SCALAR_FLOAT_TYPE_P (type)
489 0 : && !HONOR_NANS (type))
490 : {
491 0 : if (REAL_VALUE_ISNAN (TREE_REAL_CST (old_val.value)))
492 : return true;
493 : }
494 0 : else if (VECTOR_FLOAT_TYPE_P (type)
495 0 : && !HONOR_NANS (type))
496 : {
497 0 : unsigned int count
498 0 : = tree_vector_builder::binary_encoded_nelts (old_val.value,
499 0 : new_val.value);
500 0 : for (unsigned int i = 0; i < count; ++i)
501 0 : if (!REAL_VALUE_ISNAN
502 : (TREE_REAL_CST (VECTOR_CST_ENCODED_ELT (old_val.value, i)))
503 0 : && !operand_equal_p (VECTOR_CST_ENCODED_ELT (old_val.value, i),
504 0 : VECTOR_CST_ENCODED_ELT (new_val.value, i), 0))
505 : return false;
506 : return true;
507 : }
508 0 : else if (COMPLEX_FLOAT_TYPE_P (type)
509 0 : && !HONOR_NANS (type))
510 : {
511 0 : if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_REALPART (old_val.value)))
512 0 : && !operand_equal_p (TREE_REALPART (old_val.value),
513 0 : TREE_REALPART (new_val.value), 0))
514 : return false;
515 0 : if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_IMAGPART (old_val.value)))
516 0 : && !operand_equal_p (TREE_IMAGPART (old_val.value),
517 0 : TREE_IMAGPART (new_val.value), 0))
518 0 : return false;
519 : return true;
520 : }
521 : return false;
522 : }
523 :
524 : /* Set the value for variable VAR to NEW_VAL. Return true if the new
525 : value is different from VAR's previous value. */
526 :
527 : static bool
528 272349431 : set_lattice_value (tree var, ccp_prop_value_t *new_val)
529 : {
530 : /* We can deal with old UNINITIALIZED values just fine here. */
531 272349431 : ccp_prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
532 :
533 272349431 : canonicalize_value (new_val);
534 :
535 : /* We have to be careful to not go up the bitwise lattice
536 : represented by the mask. Instead of dropping to VARYING
537 : use the meet operator to retain a conservative value.
538 : Missed optimizations like PR65851 makes this necessary.
539 : It also ensures we converge to a stable lattice solution. */
540 272349431 : if (old_val->lattice_val != UNINITIALIZED
541 : /* But avoid using meet for constant -> copy transitions. */
542 176594819 : && !(old_val->lattice_val == CONSTANT
543 176513566 : && CONSTANT_CLASS_P (old_val->value)
544 173506643 : && new_val->lattice_val == CONSTANT
545 169595267 : && TREE_CODE (new_val->value) == SSA_NAME))
546 176360776 : ccp_lattice_meet (new_val, old_val);
547 :
548 272349431 : gcc_checking_assert (valid_lattice_transition (*old_val, *new_val));
549 :
550 : /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
551 : caller that this was a non-transition. */
552 544698862 : if (old_val->lattice_val != new_val->lattice_val
553 272349431 : || (new_val->lattice_val == CONSTANT
554 170062038 : && (TREE_CODE (new_val->value) != TREE_CODE (old_val->value)
555 169410305 : || (TREE_CODE (new_val->value) == INTEGER_CST
556 169353402 : && (new_val->mask != old_val->mask
557 32393937 : || (wi::bit_and_not (wi::to_widest (old_val->value),
558 : new_val->mask)
559 320854982 : != wi::bit_and_not (wi::to_widest (new_val->value),
560 : new_val->mask))))
561 16225420 : || (TREE_CODE (new_val->value) != INTEGER_CST
562 56903 : && !operand_equal_p (new_val->value, old_val->value, 0)))))
563 : {
564 : /* ??? We would like to delay creation of INTEGER_CSTs from
565 : partially constants here. */
566 :
567 256088884 : if (dump_file && (dump_flags & TDF_DETAILS))
568 : {
569 51 : dump_lattice_value (dump_file, "Lattice value changed to ", *new_val);
570 51 : fprintf (dump_file, ". Adding SSA edges to worklist.\n");
571 : }
572 :
573 256088884 : *old_val = *new_val;
574 :
575 256088884 : gcc_assert (new_val->lattice_val != UNINITIALIZED);
576 : return true;
577 : }
578 :
579 : return false;
580 : }
581 :
582 : static ccp_prop_value_t get_value_for_expr (tree, bool);
583 : static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
584 : void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *,
585 : signop, int, const widest_int &, const widest_int &,
586 : signop, int, const widest_int &, const widest_int &);
587 :
588 : /* Return a widest_int that can be used for bitwise simplifications
589 : from VAL. */
590 :
591 : static widest_int
592 324016499 : value_to_wide_int (ccp_prop_value_t val)
593 : {
594 324016499 : if (val.value
595 256790768 : && TREE_CODE (val.value) == INTEGER_CST)
596 256790768 : return wi::to_widest (val.value);
597 :
598 67225731 : return 0;
599 : }
600 :
601 : /* Return the value for the address expression EXPR based on alignment
602 : information. */
603 :
604 : static ccp_prop_value_t
605 8843728 : get_value_from_alignment (tree expr)
606 : {
607 8843728 : tree type = TREE_TYPE (expr);
608 8843728 : ccp_prop_value_t val;
609 8843728 : unsigned HOST_WIDE_INT bitpos;
610 8843728 : unsigned int align;
611 :
612 8843728 : gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
613 :
614 8843728 : get_pointer_alignment_1 (expr, &align, &bitpos);
615 8843728 : val.mask = wi::bit_and_not
616 17687456 : (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
617 8843728 : ? wi::mask <widest_int> (TYPE_PRECISION (type), false)
618 0 : : -1,
619 17687456 : align / BITS_PER_UNIT - 1);
620 8843728 : val.lattice_val
621 15005365 : = wi::sext (val.mask, TYPE_PRECISION (type)) == -1 ? VARYING : CONSTANT;
622 8843728 : if (val.lattice_val == CONSTANT)
623 6161637 : val.value = build_int_cstu (type, bitpos / BITS_PER_UNIT);
624 : else
625 2682091 : val.value = NULL_TREE;
626 :
627 8843728 : return val;
628 : }
629 :
630 : /* Return the value for the tree operand EXPR. If FOR_BITS_P is true
631 : return constant bits extracted from alignment information for
632 : invariant addresses. */
633 :
634 : static ccp_prop_value_t
635 502078247 : get_value_for_expr (tree expr, bool for_bits_p)
636 : {
637 502078247 : ccp_prop_value_t val;
638 :
639 502078247 : if (TREE_CODE (expr) == SSA_NAME)
640 : {
641 313920251 : ccp_prop_value_t *val_ = get_value (expr);
642 313920251 : if (val_)
643 313920134 : val = *val_;
644 : else
645 : {
646 117 : val.lattice_val = VARYING;
647 117 : val.value = NULL_TREE;
648 117 : val.mask = -1;
649 : }
650 313920251 : if (for_bits_p
651 213073666 : && val.lattice_val == CONSTANT)
652 : {
653 146320400 : if (TREE_CODE (val.value) == ADDR_EXPR)
654 216955 : val = get_value_from_alignment (val.value);
655 146103445 : else if (TREE_CODE (val.value) != INTEGER_CST)
656 : {
657 7794060 : val.lattice_val = VARYING;
658 7794060 : val.value = NULL_TREE;
659 7794060 : val.mask = -1;
660 : }
661 : }
662 : /* Fall back to a copy value. */
663 : if (!for_bits_p
664 100846585 : && val.lattice_val == VARYING
665 9746729 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr))
666 : {
667 9741540 : val.lattice_val = CONSTANT;
668 9741540 : val.value = expr;
669 9741540 : val.mask = -1;
670 : }
671 : }
672 188157996 : else if (is_gimple_min_invariant (expr)
673 188157996 : && (!for_bits_p || TREE_CODE (expr) == INTEGER_CST))
674 : {
675 152785616 : val.lattice_val = CONSTANT;
676 152785616 : val.value = expr;
677 152785616 : val.mask = 0;
678 152785616 : canonicalize_value (&val);
679 : }
680 35372380 : else if (TREE_CODE (expr) == ADDR_EXPR)
681 8626773 : val = get_value_from_alignment (expr);
682 : else
683 : {
684 26745607 : val.lattice_val = VARYING;
685 26745607 : val.mask = -1;
686 26745607 : val.value = NULL_TREE;
687 : }
688 :
689 502078247 : if (val.lattice_val == VARYING
690 103840706 : && INTEGRAL_TYPE_P (TREE_TYPE (expr))
691 573188070 : && TYPE_UNSIGNED (TREE_TYPE (expr)))
692 34525513 : val.mask = wi::zext (val.mask, TYPE_PRECISION (TREE_TYPE (expr)));
693 :
694 502078247 : return val;
695 : }
696 :
697 : /* Return the likely CCP lattice value for STMT.
698 :
699 : If STMT has no operands, then return CONSTANT.
700 :
701 : Else if undefinedness of operands of STMT cause its value to be
702 : undefined, then return UNDEFINED.
703 :
704 : Else if any operands of STMT are constants, then return CONSTANT.
705 :
706 : Else return VARYING. */
707 :
708 : static ccp_lattice_t
709 245451421 : likely_value (gimple *stmt)
710 : {
711 245451421 : bool has_constant_operand, has_undefined_operand, all_undefined_operands;
712 245451421 : bool has_nsa_operand;
713 245451421 : tree use;
714 245451421 : ssa_op_iter iter;
715 245451421 : unsigned i;
716 :
717 245451421 : enum gimple_code code = gimple_code (stmt);
718 :
719 : /* This function appears to be called only for assignments, calls,
720 : conditionals, and switches, due to the logic in visit_stmt. */
721 245451421 : gcc_assert (code == GIMPLE_ASSIGN
722 : || code == GIMPLE_CALL
723 : || code == GIMPLE_COND
724 : || code == GIMPLE_SWITCH);
725 :
726 : /* If the statement has volatile operands, it won't fold to a
727 : constant value. */
728 447477662 : if (gimple_has_volatile_ops (stmt))
729 : return VARYING;
730 :
731 : /* .DEFERRED_INIT produces undefined except for AUTO_INIT_CXX26
732 : which produces varying because it is undefined that needs to have
733 : the same value in all uses. */
734 245451365 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
735 : {
736 42005 : if (tree_to_uhwi (gimple_call_arg (stmt, 1)) & AUTO_INIT_CXX26)
737 : return VARYING;
738 : else
739 550 : return UNDEFINED;
740 : }
741 :
742 : /* Arrive here for more complex cases. */
743 245409360 : has_constant_operand = false;
744 245409360 : has_undefined_operand = false;
745 245409360 : all_undefined_operands = true;
746 245409360 : has_nsa_operand = false;
747 503532820 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
748 : {
749 258123460 : ccp_prop_value_t *val = get_value (use);
750 :
751 258123460 : if (val && val->lattice_val == UNDEFINED)
752 : has_undefined_operand = true;
753 : else
754 : all_undefined_operands = false;
755 :
756 258123343 : if (val && val->lattice_val == CONSTANT)
757 164332860 : has_constant_operand = true;
758 :
759 258123460 : if (SSA_NAME_IS_DEFAULT_DEF (use)
760 258123460 : || !prop_simulate_again_p (SSA_NAME_DEF_STMT (use)))
761 : has_nsa_operand = true;
762 : }
763 :
764 : /* There may be constants in regular rhs operands. For calls we
765 : have to ignore lhs, fndecl and static chain, otherwise only
766 : the lhs. */
767 490818720 : for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
768 741252782 : i < gimple_num_ops (stmt); ++i)
769 : {
770 495843422 : tree op = gimple_op (stmt, i);
771 495843422 : if (!op || TREE_CODE (op) == SSA_NAME)
772 323002858 : continue;
773 172840564 : if (is_gimple_min_invariant (op))
774 : has_constant_operand = true;
775 33552625 : else if (TREE_CODE (op) == CONSTRUCTOR)
776 : {
777 : unsigned j;
778 : tree val;
779 496437328 : FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (op), j, val)
780 593906 : if (CONSTANT_CLASS_P (val))
781 : {
782 : has_constant_operand = true;
783 : break;
784 : }
785 : }
786 : }
787 :
788 245409360 : if (has_constant_operand)
789 193704455 : all_undefined_operands = false;
790 :
791 245409360 : if (has_undefined_operand
792 245409360 : && code == GIMPLE_CALL
793 245409360 : && gimple_call_internal_p (stmt))
794 20188 : switch (gimple_call_internal_fn (stmt))
795 : {
796 : /* These 3 builtins use the first argument just as a magic
797 : way how to find out a decl uid. */
798 : case IFN_GOMP_SIMD_LANE:
799 : case IFN_GOMP_SIMD_VF:
800 : case IFN_GOMP_SIMD_LAST_LANE:
801 : has_undefined_operand = false;
802 : break;
803 : default:
804 : break;
805 : }
806 :
807 : /* If the operation combines operands like COMPLEX_EXPR make sure to
808 : not mark the result UNDEFINED if only one part of the result is
809 : undefined. */
810 245389295 : if (has_undefined_operand && all_undefined_operands)
811 : return UNDEFINED;
812 245326169 : else if (code == GIMPLE_ASSIGN && has_undefined_operand)
813 : {
814 63464 : switch (gimple_assign_rhs_code (stmt))
815 : {
816 : /* Unary operators are handled with all_undefined_operands. */
817 : case PLUS_EXPR:
818 : case MINUS_EXPR:
819 : case POINTER_PLUS_EXPR:
820 : case BIT_XOR_EXPR:
821 : /* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected.
822 : Not bitwise operators, one VARYING operand may specify the
823 : result completely.
824 : Not logical operators for the same reason, apart from XOR.
825 : Not COMPLEX_EXPR as one VARYING operand makes the result partly
826 : not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because
827 : the undefined operand may be promoted. */
828 : return UNDEFINED;
829 :
830 : case ADDR_EXPR:
831 : /* If any part of an address is UNDEFINED, like the index
832 : of an ARRAY_EXPR, then treat the result as UNDEFINED. */
833 : return UNDEFINED;
834 :
835 : default:
836 : ;
837 : }
838 : }
839 : /* If there was an UNDEFINED operand but the result may be not UNDEFINED
840 : fall back to CONSTANT. During iteration UNDEFINED may still drop
841 : to CONSTANT. */
842 245284130 : if (has_undefined_operand)
843 : return CONSTANT;
844 :
845 : /* We do not consider virtual operands here -- load from read-only
846 : memory may have only VARYING virtual operands, but still be
847 : constant. Also we can combine the stmt with definitions from
848 : operands whose definitions are not simulated again. */
849 245110749 : if (has_constant_operand
850 245110749 : || has_nsa_operand
851 245110749 : || gimple_references_memory_p (stmt))
852 245102869 : return CONSTANT;
853 :
854 : return VARYING;
855 : }
856 :
857 : /* Returns true if STMT cannot be constant. */
858 :
859 : static bool
860 343827268 : surely_varying_stmt_p (gimple *stmt)
861 : {
862 : /* If the statement has operands that we cannot handle, it cannot be
863 : constant. */
864 483241767 : if (gimple_has_volatile_ops (stmt))
865 : return true;
866 :
867 : /* If it is a call and does not return a value or is not a
868 : builtin and not an indirect call or a call to function with
869 : assume_aligned/alloc_align attribute, it is varying. */
870 333899329 : if (is_gimple_call (stmt))
871 : {
872 17180042 : tree fndecl, fntype = gimple_call_fntype (stmt);
873 17180042 : if (!gimple_call_lhs (stmt)
874 17180042 : || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
875 6909985 : && !fndecl_built_in_p (fndecl)
876 4081873 : && !lookup_attribute ("assume_aligned",
877 4081873 : TYPE_ATTRIBUTES (fntype))
878 4081831 : && !lookup_attribute ("alloc_align",
879 4081831 : TYPE_ATTRIBUTES (fntype))))
880 : return true;
881 : }
882 :
883 : /* Any other store operation is not interesting. */
884 429025805 : else if (gimple_vdef (stmt))
885 : return true;
886 :
887 : /* Anything other than assignments and conditional jumps are not
888 : interesting for CCP. */
889 289908647 : if (gimple_code (stmt) != GIMPLE_ASSIGN
890 : && gimple_code (stmt) != GIMPLE_COND
891 : && gimple_code (stmt) != GIMPLE_SWITCH
892 : && gimple_code (stmt) != GIMPLE_CALL)
893 204562077 : return true;
894 :
895 : return false;
896 : }
897 :
898 : /* Initialize local data structures for CCP. */
899 :
900 : static void
901 5714131 : ccp_initialize (void)
902 : {
903 5714131 : basic_block bb;
904 :
905 5714131 : n_const_val = num_ssa_names;
906 5714131 : const_val = XCNEWVEC (ccp_prop_value_t, n_const_val);
907 :
908 : /* Initialize simulation flags for PHI nodes and statements. */
909 55171176 : FOR_EACH_BB_FN (bb, cfun)
910 : {
911 49457045 : gimple_stmt_iterator i;
912 :
913 476887724 : for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
914 : {
915 377973634 : gimple *stmt = gsi_stmt (i);
916 377973634 : bool is_varying;
917 :
918 : /* If the statement is a control insn, then we do not
919 : want to avoid simulating the statement once. Failure
920 : to do so means that those edges will never get added. */
921 377973634 : if (stmt_ends_bb_p (stmt))
922 : is_varying = false;
923 : else
924 343827268 : is_varying = surely_varying_stmt_p (stmt);
925 :
926 343827268 : if (is_varying)
927 : {
928 258480698 : tree def;
929 258480698 : ssa_op_iter iter;
930 :
931 : /* If the statement will not produce a constant, mark
932 : all its outputs VARYING. */
933 315285982 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
934 56805284 : set_value_varying (def);
935 : }
936 377973634 : prop_set_simulate_again (stmt, !is_varying);
937 : }
938 : }
939 :
940 : /* Now process PHI nodes. We never clear the simulate_again flag on
941 : phi nodes, since we do not know which edges are executable yet,
942 : except for phi nodes for virtual operands when we do not do store ccp. */
943 55171176 : FOR_EACH_BB_FN (bb, cfun)
944 : {
945 49457045 : gphi_iterator i;
946 :
947 67386040 : for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
948 : {
949 17928995 : gphi *phi = i.phi ();
950 :
951 35857990 : if (virtual_operand_p (gimple_phi_result (phi)))
952 8118891 : prop_set_simulate_again (phi, false);
953 : else
954 9810104 : prop_set_simulate_again (phi, true);
955 : }
956 : }
957 5714131 : }
958 :
959 : /* Debug count support. Reset the values of ssa names
960 : VARYING when the total number ssa names analyzed is
961 : beyond the debug count specified. */
962 :
963 : static void
964 5714131 : do_dbg_cnt (void)
965 : {
966 5714131 : unsigned i;
967 232888840 : for (i = 0; i < num_ssa_names; i++)
968 : {
969 227174709 : if (!dbg_cnt (ccp))
970 : {
971 0 : const_val[i].lattice_val = VARYING;
972 0 : const_val[i].mask = -1;
973 0 : const_val[i].value = NULL_TREE;
974 : }
975 : }
976 5714131 : }
977 :
978 :
979 : /* We want to provide our own GET_VALUE and FOLD_STMT virtual methods. */
980 22856524 : class ccp_folder : public substitute_and_fold_engine
981 : {
982 : public:
983 : tree value_of_expr (tree, gimple *) final override;
984 : bool fold_stmt (gimple_stmt_iterator *) final override;
985 : };
986 :
987 : /* This method just wraps GET_CONSTANT_VALUE for now. Over time
988 : naked calls to GET_CONSTANT_VALUE should be eliminated in favor
989 : of calling member functions. */
990 :
991 : tree
992 308411917 : ccp_folder::value_of_expr (tree op, gimple *)
993 : {
994 308411917 : return get_constant_value (op);
995 : }
996 :
997 : /* Do final substitution of propagated values, cleanup the flowgraph and
998 : free allocated storage. If NONZERO_P, record nonzero bits.
999 :
1000 : Return TRUE when something was optimized. */
1001 :
1002 : static bool
1003 5714131 : ccp_finalize (bool nonzero_p)
1004 : {
1005 5714131 : bool something_changed;
1006 5714131 : unsigned i;
1007 5714131 : tree name;
1008 :
1009 5714131 : do_dbg_cnt ();
1010 :
1011 : /* Derive nonzero and alignment bits from partially constant integers. */
1012 232888840 : FOR_EACH_SSA_NAME (i, name, cfun)
1013 : {
1014 185489568 : ccp_prop_value_t *val;
1015 :
1016 338705860 : if (!POINTER_TYPE_P (TREE_TYPE (name))
1017 335361065 : && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
1018 : /* Don't record nonzero bits before IPA to avoid
1019 : using too much memory. */
1020 65561313 : || !nonzero_p))
1021 170140401 : continue;
1022 :
1023 99272527 : val = get_value (name);
1024 183195887 : if (val->lattice_val != CONSTANT
1025 27907185 : || TREE_CODE (val->value) != INTEGER_CST
1026 127179712 : || val->mask == 0)
1027 83923360 : continue;
1028 :
1029 15349167 : unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
1030 15349167 : wide_int value = wi::to_wide (val->value);
1031 15349167 : wide_int mask = wide_int::from (val->mask, precision, UNSIGNED);
1032 15349474 : value = value & ~mask;
1033 15349167 : set_bitmask (name, value, mask);
1034 15349474 : }
1035 :
1036 : /* Perform substitutions based on the known constant values. */
1037 5714131 : class ccp_folder ccp_folder;
1038 5714131 : something_changed = ccp_folder.substitute_and_fold ();
1039 :
1040 5714131 : free (const_val);
1041 5714131 : const_val = NULL;
1042 5714131 : return something_changed;
1043 5714131 : }
1044 :
1045 :
1046 : /* Compute the meet operator between *VAL1 and *VAL2. Store the result
1047 : in VAL1.
1048 :
1049 : any M UNDEFINED = any
1050 : any M VARYING = VARYING
1051 : Ci M Cj = Ci if (i == j)
1052 : Ci M Cj = VARYING if (i != j)
1053 : */
1054 :
1055 : static void
1056 243364295 : ccp_lattice_meet (ccp_prop_value_t *val1, ccp_prop_value_t *val2)
1057 : {
1058 243364295 : if (val1->lattice_val == UNDEFINED
1059 : /* For UNDEFINED M SSA we can't always SSA because its definition
1060 : may not dominate the PHI node. Doing optimistic copy propagation
1061 : also causes a lot of gcc.dg/uninit-pred*.c FAILs. */
1062 168859 : && (val2->lattice_val != CONSTANT
1063 95542 : || TREE_CODE (val2->value) != SSA_NAME))
1064 : {
1065 : /* UNDEFINED M any = any */
1066 93921 : *val1 = *val2;
1067 : }
1068 243270374 : else if (val2->lattice_val == UNDEFINED
1069 : /* See above. */
1070 95857 : && (val1->lattice_val != CONSTANT
1071 61519 : || TREE_CODE (val1->value) != SSA_NAME))
1072 : {
1073 : /* any M UNDEFINED = any
1074 : Nothing to do. VAL1 already contains the value we want. */
1075 : ;
1076 : }
1077 243199713 : else if (val1->lattice_val == VARYING
1078 236970882 : || val2->lattice_val == VARYING)
1079 : {
1080 : /* any M VARYING = VARYING. */
1081 6246259 : val1->lattice_val = VARYING;
1082 6246259 : val1->mask = -1;
1083 6246259 : val1->value = NULL_TREE;
1084 : }
1085 236953454 : else if (val1->lattice_val == CONSTANT
1086 236878516 : && val2->lattice_val == CONSTANT
1087 236853320 : && TREE_CODE (val1->value) == INTEGER_CST
1088 231710569 : && TREE_CODE (val2->value) == INTEGER_CST)
1089 : {
1090 : /* Ci M Cj = Ci if (i == j)
1091 : Ci M Cj = VARYING if (i != j)
1092 :
1093 : For INTEGER_CSTs mask unequal bits. If no equal bits remain,
1094 : drop to varying. */
1095 459361556 : val1->mask = (val1->mask | val2->mask
1096 459361556 : | (wi::to_widest (val1->value)
1097 689042334 : ^ wi::to_widest (val2->value)));
1098 229875658 : if (wi::sext (val1->mask, TYPE_PRECISION (TREE_TYPE (val1->value))) == -1)
1099 : {
1100 524537 : val1->lattice_val = VARYING;
1101 524537 : val1->value = NULL_TREE;
1102 : }
1103 : }
1104 7272676 : else if (val1->lattice_val == CONSTANT
1105 7197738 : && val2->lattice_val == CONSTANT
1106 14445218 : && operand_equal_p (val1->value, val2->value, 0))
1107 : {
1108 : /* Ci M Cj = Ci if (i == j)
1109 : Ci M Cj = VARYING if (i != j)
1110 :
1111 : VAL1 already contains the value we want for equivalent values. */
1112 : }
1113 6850809 : else if (val1->lattice_val == CONSTANT
1114 6775871 : && val2->lattice_val == CONSTANT
1115 6750675 : && (TREE_CODE (val1->value) == ADDR_EXPR
1116 6548010 : || TREE_CODE (val2->value) == ADDR_EXPR))
1117 : {
1118 : /* When not equal addresses are involved try meeting for
1119 : alignment. */
1120 765351 : ccp_prop_value_t tem = *val2;
1121 765351 : if (TREE_CODE (val1->value) == ADDR_EXPR)
1122 202665 : *val1 = get_value_for_expr (val1->value, true);
1123 765351 : if (TREE_CODE (val2->value) == ADDR_EXPR)
1124 662386 : tem = get_value_for_expr (val2->value, true);
1125 765351 : ccp_lattice_meet (val1, &tem);
1126 765351 : }
1127 : else
1128 : {
1129 : /* Any other combination is VARYING. */
1130 6085458 : val1->lattice_val = VARYING;
1131 6085458 : val1->mask = -1;
1132 6085458 : val1->value = NULL_TREE;
1133 : }
1134 243364295 : }
1135 :
1136 :
1137 : /* Loop through the PHI_NODE's parameters for BLOCK and compare their
1138 : lattice values to determine PHI_NODE's lattice value. The value of a
1139 : PHI node is determined calling ccp_lattice_meet with all the arguments
1140 : of the PHI node that are incoming via executable edges. */
1141 :
1142 : enum ssa_prop_result
1143 70323190 : ccp_propagate::visit_phi (gphi *phi)
1144 : {
1145 70323190 : unsigned i;
1146 70323190 : ccp_prop_value_t new_val;
1147 :
1148 70323190 : if (dump_file && (dump_flags & TDF_DETAILS))
1149 : {
1150 1 : fprintf (dump_file, "\nVisiting PHI node: ");
1151 1 : print_gimple_stmt (dump_file, phi, 0, dump_flags);
1152 : }
1153 :
1154 70323190 : new_val.lattice_val = UNDEFINED;
1155 70323190 : new_val.value = NULL_TREE;
1156 70323190 : new_val.mask = 0;
1157 :
1158 70323190 : bool first = true;
1159 70323190 : bool non_exec_edge = false;
1160 206905076 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1161 : {
1162 : /* Compute the meet operator over all the PHI arguments flowing
1163 : through executable edges. */
1164 142987406 : edge e = gimple_phi_arg_edge (phi, i);
1165 :
1166 142987406 : if (dump_file && (dump_flags & TDF_DETAILS))
1167 : {
1168 6 : fprintf (dump_file,
1169 : "\tArgument #%d (%d -> %d %sexecutable)\n",
1170 3 : i, e->src->index, e->dest->index,
1171 3 : (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
1172 : }
1173 :
1174 : /* If the incoming edge is executable, Compute the meet operator for
1175 : the existing value of the PHI node and the current PHI argument. */
1176 142987406 : if (e->flags & EDGE_EXECUTABLE)
1177 : {
1178 136561358 : tree arg = gimple_phi_arg (phi, i)->def;
1179 136561358 : ccp_prop_value_t arg_val = get_value_for_expr (arg, false);
1180 :
1181 136561358 : if (first)
1182 : {
1183 70323190 : new_val = arg_val;
1184 70323190 : first = false;
1185 : }
1186 : else
1187 66238168 : ccp_lattice_meet (&new_val, &arg_val);
1188 :
1189 136561358 : if (dump_file && (dump_flags & TDF_DETAILS))
1190 : {
1191 3 : fprintf (dump_file, "\t");
1192 3 : print_generic_expr (dump_file, arg, dump_flags);
1193 3 : dump_lattice_value (dump_file, "\tValue: ", arg_val);
1194 3 : fprintf (dump_file, "\n");
1195 : }
1196 :
1197 136561358 : if (new_val.lattice_val == VARYING)
1198 : break;
1199 136561358 : }
1200 : else
1201 : non_exec_edge = true;
1202 : }
1203 :
1204 : /* In case there were non-executable edges and the value is a copy
1205 : make sure its definition dominates the PHI node. */
1206 70323190 : if (non_exec_edge
1207 6084126 : && new_val.lattice_val == CONSTANT
1208 5979139 : && TREE_CODE (new_val.value) == SSA_NAME
1209 1542500 : && ! SSA_NAME_IS_DEFAULT_DEF (new_val.value)
1210 71724088 : && ! dominated_by_p (CDI_DOMINATORS, gimple_bb (phi),
1211 1400898 : gimple_bb (SSA_NAME_DEF_STMT (new_val.value))))
1212 : {
1213 84074 : new_val.lattice_val = VARYING;
1214 84074 : new_val.value = NULL_TREE;
1215 84074 : new_val.mask = -1;
1216 : }
1217 :
1218 70323190 : if (dump_file && (dump_flags & TDF_DETAILS))
1219 : {
1220 1 : dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
1221 1 : fprintf (dump_file, "\n\n");
1222 : }
1223 :
1224 : /* Make the transition to the new value. */
1225 70323190 : if (set_lattice_value (gimple_phi_result (phi), &new_val))
1226 : {
1227 68552901 : if (new_val.lattice_val == VARYING)
1228 : return SSA_PROP_VARYING;
1229 : else
1230 61938650 : return SSA_PROP_INTERESTING;
1231 : }
1232 : else
1233 : return SSA_PROP_NOT_INTERESTING;
1234 70323190 : }
1235 :
1236 : /* Return the constant value for OP or OP otherwise. */
1237 :
1238 : static tree
1239 295927928 : valueize_op (tree op)
1240 : {
1241 295927928 : if (TREE_CODE (op) == SSA_NAME)
1242 : {
1243 283680547 : tree tem = get_constant_value (op);
1244 283680547 : if (tem)
1245 28216016 : return tem;
1246 : }
1247 : return op;
1248 : }
1249 :
1250 : /* Return the constant value for OP, but signal to not follow SSA
1251 : edges if the definition may be simulated again. */
1252 :
1253 : static tree
1254 3844290186 : valueize_op_1 (tree op)
1255 : {
1256 3844290186 : if (TREE_CODE (op) == SSA_NAME)
1257 : {
1258 : /* If the definition may be simulated again we cannot follow
1259 : this SSA edge as the SSA propagator does not necessarily
1260 : re-visit the use. */
1261 3844290186 : gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1262 3844290186 : if (!gimple_nop_p (def_stmt)
1263 3844290186 : && prop_simulate_again_p (def_stmt))
1264 : return NULL_TREE;
1265 1924046738 : tree tem = get_constant_value (op);
1266 1924046738 : if (tem)
1267 4450892 : return tem;
1268 : }
1269 : return op;
1270 : }
1271 :
1272 : /* CCP specific front-end to the non-destructive constant folding
1273 : routines.
1274 :
1275 : Attempt to simplify the RHS of STMT knowing that one or more
1276 : operands are constants.
1277 :
1278 : If simplification is possible, return the simplified RHS,
1279 : otherwise return the original RHS or NULL_TREE. */
1280 :
1281 : static tree
1282 245276250 : ccp_fold (gimple *stmt)
1283 : {
1284 245276250 : switch (gimple_code (stmt))
1285 : {
1286 104307 : case GIMPLE_SWITCH:
1287 104307 : {
1288 : /* Return the constant switch index. */
1289 104307 : return valueize_op (gimple_switch_index (as_a <gswitch *> (stmt)));
1290 : }
1291 :
1292 245171943 : case GIMPLE_COND:
1293 245171943 : case GIMPLE_ASSIGN:
1294 245171943 : case GIMPLE_CALL:
1295 245171943 : return gimple_fold_stmt_to_constant_1 (stmt,
1296 245171943 : valueize_op, valueize_op_1);
1297 :
1298 0 : default:
1299 0 : gcc_unreachable ();
1300 : }
1301 : }
1302 :
1303 : /* Determine the minimum and maximum values, *MIN and *MAX respectively,
1304 : represented by the mask pair VAL and MASK with signedness SGN and
1305 : precision PRECISION. */
1306 :
1307 : static void
1308 29379294 : value_mask_to_min_max (widest_int *min, widest_int *max,
1309 : const widest_int &val, const widest_int &mask,
1310 : signop sgn, int precision)
1311 : {
1312 29379294 : *min = wi::bit_and_not (val, mask);
1313 29379294 : *max = val | mask;
1314 29379294 : if (sgn == SIGNED && wi::neg_p (mask))
1315 : {
1316 7043644 : widest_int sign_bit = wi::lshift (1, precision - 1);
1317 7043644 : *min ^= sign_bit;
1318 7043644 : *max ^= sign_bit;
1319 : /* MAX is zero extended, and MIN is sign extended. */
1320 7043644 : *min = wi::ext (*min, precision, sgn);
1321 7043692 : *max = wi::ext (*max, precision, sgn);
1322 7043644 : }
1323 29379294 : }
1324 :
1325 : /* Apply the operation CODE in type TYPE to the value, mask pair
1326 : RVAL and RMASK representing a value of type RTYPE and set
1327 : the value, mask pair *VAL and *MASK to the result. */
1328 :
1329 : void
1330 98560314 : bit_value_unop (enum tree_code code, signop type_sgn, int type_precision,
1331 : widest_int *val, widest_int *mask,
1332 : signop rtype_sgn, int rtype_precision,
1333 : const widest_int &rval, const widest_int &rmask)
1334 : {
1335 98565311 : switch (code)
1336 : {
1337 733012 : case BIT_NOT_EXPR:
1338 733012 : *mask = rmask;
1339 733012 : *val = ~rval;
1340 733012 : break;
1341 :
1342 315748 : case NEGATE_EXPR:
1343 315748 : {
1344 315748 : widest_int temv, temm;
1345 : /* Return ~rval + 1. */
1346 315748 : bit_value_unop (BIT_NOT_EXPR, type_sgn, type_precision, &temv, &temm,
1347 : type_sgn, type_precision, rval, rmask);
1348 315748 : bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask,
1349 : type_sgn, type_precision, temv, temm,
1350 631496 : type_sgn, type_precision, 1, 0);
1351 315748 : break;
1352 315748 : }
1353 :
1354 97383652 : CASE_CONVERT:
1355 97383652 : {
1356 : /* First extend mask and value according to the original type. */
1357 97383652 : *mask = wi::ext (rmask, rtype_precision, rtype_sgn);
1358 97383652 : *val = wi::ext (rval, rtype_precision, rtype_sgn);
1359 :
1360 : /* Then extend mask and value according to the target type. */
1361 97383652 : *mask = wi::ext (*mask, type_precision, type_sgn);
1362 97383652 : *val = wi::ext (*val, type_precision, type_sgn);
1363 97383652 : break;
1364 : }
1365 :
1366 132896 : case ABS_EXPR:
1367 132896 : case ABSU_EXPR:
1368 132896 : if (wi::sext (rmask, rtype_precision) == -1)
1369 : {
1370 121202 : *mask = -1;
1371 121202 : *val = 0;
1372 : }
1373 11694 : else if (wi::neg_p (rmask))
1374 : {
1375 : /* Result is either rval or -rval. */
1376 300 : widest_int temv, temm;
1377 300 : bit_value_unop (NEGATE_EXPR, rtype_sgn, rtype_precision, &temv,
1378 : &temm, type_sgn, type_precision, rval, rmask);
1379 300 : temm |= (rmask | (rval ^ temv));
1380 : /* Extend the result. */
1381 300 : *mask = wi::ext (temm, type_precision, type_sgn);
1382 300 : *val = wi::ext (temv, type_precision, type_sgn);
1383 300 : }
1384 11394 : else if (wi::neg_p (rval))
1385 : {
1386 : bit_value_unop (NEGATE_EXPR, type_sgn, type_precision, val, mask,
1387 : type_sgn, type_precision, rval, rmask);
1388 : }
1389 : else
1390 : {
1391 6397 : *mask = rmask;
1392 6397 : *val = rval;
1393 : }
1394 : break;
1395 :
1396 3 : default:
1397 3 : *mask = -1;
1398 3 : *val = 0;
1399 3 : break;
1400 : }
1401 98560314 : }
1402 :
1403 : /* Determine the mask pair *VAL and *MASK from multiplying the
1404 : argument mask pair RVAL, RMASK by the unsigned constant C. */
1405 : static void
1406 31986919 : bit_value_mult_const (signop sgn, int width,
1407 : widest_int *val, widest_int *mask,
1408 : const widest_int &rval, const widest_int &rmask,
1409 : widest_int c)
1410 : {
1411 31986919 : widest_int sum_mask = 0;
1412 :
1413 : /* Ensure rval_lo only contains known bits. */
1414 31986919 : widest_int rval_lo = wi::bit_and_not (rval, rmask);
1415 :
1416 31986919 : if (rval_lo != 0)
1417 : {
1418 : /* General case (some bits of multiplicand are known set). */
1419 867770 : widest_int sum_val = 0;
1420 2090659 : while (c != 0)
1421 : {
1422 : /* Determine the lowest bit set in the multiplier. */
1423 1222889 : int bitpos = wi::ctz (c);
1424 1222889 : widest_int term_mask = rmask << bitpos;
1425 1222889 : widest_int term_val = rval_lo << bitpos;
1426 :
1427 : /* sum += term. */
1428 1222889 : widest_int lo = sum_val + term_val;
1429 1287849 : widest_int hi = (sum_val | sum_mask) + (term_val | term_mask);
1430 1352811 : sum_mask |= term_mask | (lo ^ hi);
1431 1222889 : sum_val = lo;
1432 :
1433 : /* Clear this bit in the multiplier. */
1434 1222889 : c ^= wi::lshift (1, bitpos);
1435 1352809 : }
1436 : /* Correctly extend the result value. */
1437 867770 : *val = wi::ext (sum_val, width, sgn);
1438 867770 : }
1439 : else
1440 : {
1441 : /* Special case (no bits of multiplicand are known set). */
1442 80642277 : while (c != 0)
1443 : {
1444 : /* Determine the lowest bit set in the multiplier. */
1445 49523128 : int bitpos = wi::ctz (c);
1446 49523128 : widest_int term_mask = rmask << bitpos;
1447 :
1448 : /* sum += term. */
1449 49523128 : widest_int hi = sum_mask + term_mask;
1450 49523128 : sum_mask |= term_mask | hi;
1451 :
1452 : /* Clear this bit in the multiplier. */
1453 49523137 : c ^= wi::lshift (1, bitpos);
1454 49523208 : }
1455 31119149 : *val = 0;
1456 : }
1457 :
1458 : /* Correctly extend the result mask. */
1459 32051900 : *mask = wi::ext (sum_mask, width, sgn);
1460 31986919 : }
1461 :
1462 : /* Fill up to MAX values in the BITS array with values representing
1463 : each of the non-zero bits in the value X. Returns the number of
1464 : bits in X (capped at the maximum value MAX). For example, an X
1465 : value 11, places 1, 2 and 8 in BITS and returns the value 3. */
1466 :
1467 : static unsigned int
1468 344570 : get_individual_bits (widest_int *bits, widest_int x, unsigned int max)
1469 : {
1470 344570 : unsigned int count = 0;
1471 1369437 : while (count < max && x != 0)
1472 : {
1473 1024867 : int bitpos = wi::ctz (x);
1474 1024867 : bits[count] = wi::lshift (1, bitpos);
1475 1024867 : x ^= bits[count];
1476 1024867 : count++;
1477 : }
1478 344570 : return count;
1479 : }
1480 :
1481 : /* Array of 2^N - 1 values representing the bits flipped between
1482 : consecutive Gray codes. This is used to efficiently enumerate
1483 : all permutations on N bits using XOR. */
1484 : static const unsigned char gray_code_bit_flips[63] = {
1485 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1486 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
1487 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1488 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
1489 : };
1490 :
1491 : /* Apply the operation CODE in type TYPE to the value, mask pairs
1492 : R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1493 : and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */
1494 :
1495 : void
1496 286270440 : bit_value_binop (enum tree_code code, signop sgn, int width,
1497 : widest_int *val, widest_int *mask,
1498 : signop r1type_sgn, int r1type_precision,
1499 : const widest_int &r1val, const widest_int &r1mask,
1500 : signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED,
1501 : const widest_int &r2val, const widest_int &r2mask)
1502 : {
1503 286270440 : bool swap_p = false;
1504 :
1505 : /* Assume we'll get a constant result. Use an initial non varying
1506 : value, we fall back to varying in the end if necessary. */
1507 286270440 : *mask = -1;
1508 : /* Ensure that VAL is initialized (to any value). */
1509 286270440 : *val = 0;
1510 :
1511 286270440 : switch (code)
1512 : {
1513 9716501 : case BIT_AND_EXPR:
1514 : /* The mask is constant where there is a known not
1515 : set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1516 9716501 : *mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask);
1517 9716501 : *val = r1val & r2val;
1518 9716501 : break;
1519 :
1520 3195070 : case BIT_IOR_EXPR:
1521 : /* The mask is constant where there is a known
1522 : set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */
1523 6390140 : *mask = wi::bit_and_not (r1mask | r2mask,
1524 6390140 : wi::bit_and_not (r1val, r1mask)
1525 12780280 : | wi::bit_and_not (r2val, r2mask));
1526 3195070 : *val = r1val | r2val;
1527 3195070 : break;
1528 :
1529 265384 : case BIT_XOR_EXPR:
1530 : /* m1 | m2 */
1531 265384 : *mask = r1mask | r2mask;
1532 265384 : *val = r1val ^ r2val;
1533 265384 : break;
1534 :
1535 27397 : case LROTATE_EXPR:
1536 27397 : case RROTATE_EXPR:
1537 27397 : if (r2mask == 0)
1538 : {
1539 16687 : widest_int shift = r2val;
1540 16687 : if (shift == 0)
1541 : {
1542 266 : *mask = r1mask;
1543 266 : *val = r1val;
1544 : }
1545 : else
1546 : {
1547 16421 : if (wi::neg_p (shift, r2type_sgn))
1548 : {
1549 4 : shift = -shift;
1550 4 : if (code == RROTATE_EXPR)
1551 : code = LROTATE_EXPR;
1552 : else
1553 : code = RROTATE_EXPR;
1554 : }
1555 16417 : if (code == RROTATE_EXPR)
1556 : {
1557 15978 : *mask = wi::rrotate (r1mask, shift, width);
1558 15978 : *val = wi::rrotate (r1val, shift, width);
1559 : }
1560 : else
1561 : {
1562 443 : *mask = wi::lrotate (r1mask, shift, width);
1563 443 : *val = wi::lrotate (r1val, shift, width);
1564 : }
1565 16421 : *mask = wi::ext (*mask, width, sgn);
1566 16421 : *val = wi::ext (*val, width, sgn);
1567 : }
1568 16687 : }
1569 21420 : else if (wi::ltu_p (r2val | r2mask, width)
1570 35049 : && wi::popcount (r2mask) <= 4)
1571 : {
1572 29619 : widest_int bits[4];
1573 3291 : widest_int res_val, res_mask;
1574 3291 : widest_int tmp_val, tmp_mask;
1575 3291 : widest_int shift = wi::bit_and_not (r2val, r2mask);
1576 3291 : unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1577 3291 : unsigned int count = (1 << bit_count) - 1;
1578 :
1579 : /* Initialize result to rotate by smallest value of shift. */
1580 3291 : if (code == RROTATE_EXPR)
1581 : {
1582 1584 : res_mask = wi::rrotate (r1mask, shift, width);
1583 1584 : res_val = wi::rrotate (r1val, shift, width);
1584 : }
1585 : else
1586 : {
1587 1707 : res_mask = wi::lrotate (r1mask, shift, width);
1588 1707 : res_val = wi::lrotate (r1val, shift, width);
1589 : }
1590 :
1591 : /* Iterate through the remaining values of shift. */
1592 38664 : for (unsigned int i=0; i<count; i++)
1593 : {
1594 35373 : shift ^= bits[gray_code_bit_flips[i]];
1595 35373 : if (code == RROTATE_EXPR)
1596 : {
1597 17320 : tmp_mask = wi::rrotate (r1mask, shift, width);
1598 17320 : tmp_val = wi::rrotate (r1val, shift, width);
1599 : }
1600 : else
1601 : {
1602 18053 : tmp_mask = wi::lrotate (r1mask, shift, width);
1603 18053 : tmp_val = wi::lrotate (r1val, shift, width);
1604 : }
1605 : /* Accumulate the result. */
1606 35373 : res_mask |= tmp_mask | (res_val ^ tmp_val);
1607 : }
1608 3291 : *val = wi::ext (wi::bit_and_not (res_val, res_mask), width, sgn);
1609 3291 : *mask = wi::ext (res_mask, width, sgn);
1610 16455 : }
1611 : break;
1612 :
1613 8076237 : case LSHIFT_EXPR:
1614 8076237 : case RSHIFT_EXPR:
1615 : /* ??? We can handle partially known shift counts if we know
1616 : its sign. That way we can tell that (x << (y | 8)) & 255
1617 : is zero. */
1618 8076237 : if (r2mask == 0)
1619 : {
1620 7028814 : if (r2val == 0)
1621 : {
1622 14980 : *mask = r1mask;
1623 14980 : *val = r1val;
1624 : }
1625 : else
1626 : {
1627 7013834 : if (wi::neg_p (r2val, r2type_sgn))
1628 : break;
1629 7013665 : if (code == RSHIFT_EXPR)
1630 : {
1631 6736926 : *mask = wi::rshift (wi::ext (r1mask, width, sgn), r2val, sgn);
1632 6736893 : *val = wi::rshift (wi::ext (r1val, width, sgn), r2val, sgn);
1633 : }
1634 : else
1635 : {
1636 276778 : *mask = wi::ext (r1mask << r2val, width, sgn);
1637 276772 : *val = wi::ext (r1val << r2val, width, sgn);
1638 : }
1639 : }
1640 : }
1641 1047423 : else if (wi::ltu_p (r2val | r2mask, width))
1642 : {
1643 956908 : if (wi::popcount (r2mask) <= 4)
1644 : {
1645 3071511 : widest_int bits[4];
1646 341279 : widest_int arg_val, arg_mask;
1647 341279 : widest_int res_val, res_mask;
1648 341279 : widest_int tmp_val, tmp_mask;
1649 341279 : widest_int shift = wi::bit_and_not (r2val, r2mask);
1650 341279 : unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1651 341279 : unsigned int count = (1 << bit_count) - 1;
1652 :
1653 : /* Initialize result to shift by smallest value of shift. */
1654 341279 : if (code == RSHIFT_EXPR)
1655 : {
1656 132752 : arg_mask = wi::ext (r1mask, width, sgn);
1657 132752 : arg_val = wi::ext (r1val, width, sgn);
1658 132752 : res_mask = wi::rshift (arg_mask, shift, sgn);
1659 132752 : res_val = wi::rshift (arg_val, shift, sgn);
1660 : }
1661 : else
1662 : {
1663 208527 : arg_mask = r1mask;
1664 208527 : arg_val = r1val;
1665 208527 : res_mask = arg_mask << shift;
1666 208527 : res_val = arg_val << shift;
1667 : }
1668 :
1669 : /* Iterate through the remaining values of shift. */
1670 3245304 : for (unsigned int i=0; i<count; i++)
1671 : {
1672 2904025 : shift ^= bits[gray_code_bit_flips[i]];
1673 2904025 : if (code == RSHIFT_EXPR)
1674 : {
1675 1161996 : tmp_mask = wi::rshift (arg_mask, shift, sgn);
1676 1161996 : tmp_val = wi::rshift (arg_val, shift, sgn);
1677 : }
1678 : else
1679 : {
1680 1742029 : tmp_mask = arg_mask << shift;
1681 1742029 : tmp_val = arg_val << shift;
1682 : }
1683 : /* Accumulate the result. */
1684 2904025 : res_mask |= tmp_mask | (res_val ^ tmp_val);
1685 : }
1686 341279 : res_mask = wi::ext (res_mask, width, sgn);
1687 341279 : res_val = wi::ext (res_val, width, sgn);
1688 341279 : *val = wi::bit_and_not (res_val, res_mask);
1689 341279 : *mask = res_mask;
1690 1706395 : }
1691 615629 : else if ((r1val | r1mask) == 0)
1692 : {
1693 : /* Handle shifts of zero to avoid undefined wi::ctz below. */
1694 0 : *mask = 0;
1695 0 : *val = 0;
1696 : }
1697 615629 : else if (code == LSHIFT_EXPR)
1698 : {
1699 421214 : widest_int tmp = wi::mask <widest_int> (width, false);
1700 421214 : tmp <<= wi::ctz (r1val | r1mask);
1701 421214 : tmp <<= wi::bit_and_not (r2val, r2mask);
1702 421214 : *mask = wi::ext (tmp, width, sgn);
1703 421214 : *val = 0;
1704 421214 : }
1705 194415 : else if (!wi::neg_p (r1val | r1mask, sgn))
1706 : {
1707 : /* Logical right shift, or zero sign bit. */
1708 170812 : widest_int arg = r1val | r1mask;
1709 170812 : int lzcount = wi::clz (arg);
1710 170812 : if (lzcount)
1711 170804 : lzcount -= wi::get_precision (arg) - width;
1712 170812 : widest_int tmp = wi::mask <widest_int> (width, false);
1713 170812 : tmp = wi::lrshift (tmp, lzcount);
1714 170812 : tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1715 170812 : *mask = wi::ext (tmp, width, sgn);
1716 170812 : *val = 0;
1717 170812 : }
1718 23603 : else if (!wi::neg_p (r1mask))
1719 : {
1720 : /* Arithmetic right shift with set sign bit. */
1721 1078 : widest_int arg = wi::bit_and_not (r1val, r1mask);
1722 1078 : int sbcount = wi::clrsb (arg);
1723 1078 : sbcount -= wi::get_precision (arg) - width;
1724 1078 : widest_int tmp = wi::mask <widest_int> (width, false);
1725 1078 : tmp = wi::lrshift (tmp, sbcount);
1726 1078 : tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1727 1078 : *mask = wi::sext (tmp, width);
1728 1078 : tmp = wi::bit_not (tmp);
1729 1078 : *val = wi::sext (tmp, width);
1730 1078 : }
1731 : }
1732 : break;
1733 :
1734 136066994 : case PLUS_EXPR:
1735 136066994 : case POINTER_PLUS_EXPR:
1736 136066994 : {
1737 : /* Do the addition with unknown bits set to zero, to give carry-ins of
1738 : zero wherever possible. */
1739 272133988 : widest_int lo = (wi::bit_and_not (r1val, r1mask)
1740 272133988 : + wi::bit_and_not (r2val, r2mask));
1741 136066994 : lo = wi::ext (lo, width, sgn);
1742 : /* Do the addition with unknown bits set to one, to give carry-ins of
1743 : one wherever possible. */
1744 136067304 : widest_int hi = (r1val | r1mask) + (r2val | r2mask);
1745 136066994 : hi = wi::ext (hi, width, sgn);
1746 : /* Each bit in the result is known if (a) the corresponding bits in
1747 : both inputs are known, and (b) the carry-in to that bit position
1748 : is known. We can check condition (b) by seeing if we got the same
1749 : result with minimised carries as with maximised carries. */
1750 136067618 : *mask = r1mask | r2mask | (lo ^ hi);
1751 136066994 : *mask = wi::ext (*mask, width, sgn);
1752 : /* It shouldn't matter whether we choose lo or hi here. */
1753 136066994 : *val = lo;
1754 136066994 : break;
1755 136067073 : }
1756 :
1757 40408048 : case MINUS_EXPR:
1758 40408048 : case POINTER_DIFF_EXPR:
1759 40408048 : {
1760 : /* Subtraction is derived from the addition algorithm above. */
1761 40408048 : widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask);
1762 40408048 : lo = wi::ext (lo, width, sgn);
1763 40408232 : widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask);
1764 40408048 : hi = wi::ext (hi, width, sgn);
1765 40408416 : *mask = r1mask | r2mask | (lo ^ hi);
1766 40408048 : *mask = wi::ext (*mask, width, sgn);
1767 40408048 : *val = lo;
1768 40408048 : break;
1769 40408148 : }
1770 :
1771 35997569 : case MULT_EXPR:
1772 35997569 : if (r2mask == 0
1773 32015879 : && !wi::neg_p (r2val, sgn)
1774 70719308 : && (flag_expensive_optimizations || wi::popcount (r2val) < 8))
1775 31888943 : bit_value_mult_const (sgn, width, val, mask, r1val, r1mask, r2val);
1776 4108626 : else if (r1mask == 0
1777 100552 : && !wi::neg_p (r1val, sgn)
1778 4221977 : && (flag_expensive_optimizations || wi::popcount (r1val) < 8))
1779 97976 : bit_value_mult_const (sgn, width, val, mask, r2val, r2mask, r1val);
1780 : else
1781 : {
1782 : /* Just track trailing zeros in both operands and transfer
1783 : them to the other. */
1784 4010650 : int r1tz = wi::ctz (r1val | r1mask);
1785 4010650 : int r2tz = wi::ctz (r2val | r2mask);
1786 4010650 : if (r1tz + r2tz >= width)
1787 : {
1788 7 : *mask = 0;
1789 7 : *val = 0;
1790 : }
1791 4010643 : else if (r1tz + r2tz > 0)
1792 : {
1793 952690 : *mask = wi::ext (wi::mask <widest_int> (r1tz + r2tz, true),
1794 476345 : width, sgn);
1795 476345 : *val = 0;
1796 : }
1797 : }
1798 : break;
1799 :
1800 31126452 : case EQ_EXPR:
1801 31126452 : case NE_EXPR:
1802 31126452 : {
1803 31126452 : widest_int m = r1mask | r2mask;
1804 31126452 : if (wi::bit_and_not (r1val, m) != wi::bit_and_not (r2val, m))
1805 : {
1806 2355658 : *mask = 0;
1807 2355658 : *val = ((code == EQ_EXPR) ? 0 : 1);
1808 : }
1809 : else
1810 : {
1811 : /* We know the result of a comparison is always one or zero. */
1812 28770794 : *mask = 1;
1813 28770794 : *val = 0;
1814 : }
1815 31126452 : break;
1816 31126452 : }
1817 :
1818 7602792 : case GE_EXPR:
1819 7602792 : case GT_EXPR:
1820 7602792 : swap_p = true;
1821 7602792 : code = swap_tree_comparison (code);
1822 : /* Fall through. */
1823 12413685 : case LT_EXPR:
1824 12413685 : case LE_EXPR:
1825 12413685 : {
1826 12413685 : widest_int min1, max1, min2, max2;
1827 12413685 : int minmax, maxmin;
1828 :
1829 12413685 : const widest_int &o1val = swap_p ? r2val : r1val;
1830 7602792 : const widest_int &o1mask = swap_p ? r2mask : r1mask;
1831 7602792 : const widest_int &o2val = swap_p ? r1val : r2val;
1832 7602792 : const widest_int &o2mask = swap_p ? r1mask : r2mask;
1833 :
1834 12413685 : value_mask_to_min_max (&min1, &max1, o1val, o1mask,
1835 : r1type_sgn, r1type_precision);
1836 12413685 : value_mask_to_min_max (&min2, &max2, o2val, o2mask,
1837 : r1type_sgn, r1type_precision);
1838 :
1839 : /* For comparisons the signedness is in the comparison operands. */
1840 : /* Do a cross comparison of the max/min pairs. */
1841 12413685 : maxmin = wi::cmp (max1, min2, r1type_sgn);
1842 12413685 : minmax = wi::cmp (min1, max2, r1type_sgn);
1843 19310424 : if (maxmin < (code == LE_EXPR ? 1 : 0)) /* o1 < or <= o2. */
1844 : {
1845 3007235 : *mask = 0;
1846 3007235 : *val = 1;
1847 : }
1848 11998823 : else if (minmax > (code == LT_EXPR ? -1 : 0)) /* o1 >= or > o2. */
1849 : {
1850 416149 : *mask = 0;
1851 416149 : *val = 0;
1852 : }
1853 8990301 : else if (maxmin == minmax) /* o1 and o2 are equal. */
1854 : {
1855 : /* This probably should never happen as we'd have
1856 : folded the thing during fully constant value folding. */
1857 0 : *mask = 0;
1858 0 : *val = (code == LE_EXPR ? 1 : 0);
1859 : }
1860 : else
1861 : {
1862 : /* We know the result of a comparison is always one or zero. */
1863 8990301 : *mask = 1;
1864 8990301 : *val = 0;
1865 : }
1866 12413685 : break;
1867 12413771 : }
1868 :
1869 2275962 : case MIN_EXPR:
1870 2275962 : case MAX_EXPR:
1871 2275962 : {
1872 2275962 : widest_int min1, max1, min2, max2;
1873 :
1874 2275962 : value_mask_to_min_max (&min1, &max1, r1val, r1mask, sgn, width);
1875 2275962 : value_mask_to_min_max (&min2, &max2, r2val, r2mask, sgn, width);
1876 :
1877 2275962 : if (wi::cmp (max1, min2, sgn) <= 0) /* r1 is less than r2. */
1878 : {
1879 27397 : if (code == MIN_EXPR)
1880 : {
1881 26510 : *mask = r1mask;
1882 26510 : *val = r1val;
1883 : }
1884 : else
1885 : {
1886 887 : *mask = r2mask;
1887 887 : *val = r2val;
1888 : }
1889 : }
1890 2248565 : else if (wi::cmp (min1, max2, sgn) >= 0) /* r2 is less than r1. */
1891 : {
1892 114797 : if (code == MIN_EXPR)
1893 : {
1894 1541 : *mask = r2mask;
1895 1541 : *val = r2val;
1896 : }
1897 : else
1898 : {
1899 113256 : *mask = r1mask;
1900 113256 : *val = r1val;
1901 : }
1902 : }
1903 : else
1904 : {
1905 : /* The result is either r1 or r2. */
1906 2133772 : *mask = r1mask | r2mask | (r1val ^ r2val);
1907 2133768 : *val = r1val;
1908 : }
1909 2275962 : break;
1910 2275966 : }
1911 :
1912 2528678 : case TRUNC_MOD_EXPR:
1913 2528678 : {
1914 2528678 : widest_int r1max = r1val | r1mask;
1915 2528678 : widest_int r2max = r2val | r2mask;
1916 2528678 : if (r2mask == 0)
1917 : {
1918 507108 : widest_int shift = wi::exact_log2 (r2val);
1919 507108 : if (shift != -1)
1920 : {
1921 : // Handle modulo by a power of 2 as a bitwise and.
1922 89409 : widest_int tem_val, tem_mask;
1923 89409 : bit_value_binop (BIT_AND_EXPR, sgn, width, &tem_val, &tem_mask,
1924 : r1type_sgn, r1type_precision, r1val, r1mask,
1925 : r2type_sgn, r2type_precision,
1926 89409 : r2val - 1, r2mask);
1927 89409 : if (sgn == UNSIGNED
1928 89239 : || !wi::neg_p (r1max)
1929 178648 : || (tem_mask == 0 && tem_val == 0))
1930 : {
1931 41194 : *val = tem_val;
1932 41194 : *mask = tem_mask;
1933 41194 : return;
1934 : }
1935 89409 : }
1936 507108 : }
1937 2487484 : if (sgn == UNSIGNED
1938 2487484 : || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1939 : {
1940 : /* Confirm R2 has some bits set, to avoid division by zero. */
1941 936161 : widest_int r2min = wi::bit_and_not (r2val, r2mask);
1942 936161 : if (r2min != 0)
1943 : {
1944 : /* R1 % R2 is R1 if R1 is always less than R2. */
1945 327073 : if (wi::ltu_p (r1max, r2min))
1946 : {
1947 16085 : *mask = r1mask;
1948 16085 : *val = r1val;
1949 : }
1950 : else
1951 : {
1952 : /* R1 % R2 is always less than the maximum of R2. */
1953 310988 : unsigned int lzcount = wi::clz (r2max);
1954 310988 : unsigned int bits = wi::get_precision (r2max) - lzcount;
1955 310988 : if (r2max == wi::lshift (1, bits))
1956 0 : bits--;
1957 310988 : *mask = wi::mask <widest_int> (bits, false);
1958 310988 : *val = 0;
1959 : }
1960 : }
1961 936161 : }
1962 2528678 : }
1963 2487484 : break;
1964 :
1965 4152092 : case EXACT_DIV_EXPR:
1966 4152092 : case TRUNC_DIV_EXPR:
1967 4152092 : {
1968 4152092 : widest_int r1max = r1val | r1mask;
1969 4152092 : widest_int r2max = r2val | r2mask;
1970 8304184 : if (r2mask == 0
1971 4152092 : && (code == EXACT_DIV_EXPR
1972 3213227 : || sgn == UNSIGNED
1973 1254219 : || !wi::neg_p (r1max)))
1974 : {
1975 2214152 : widest_int shift = wi::exact_log2 (r2val);
1976 2214152 : if (shift != -1)
1977 : {
1978 : // Handle division by a power of 2 as an rshift.
1979 1715096 : bit_value_binop (RSHIFT_EXPR, sgn, width, val, mask,
1980 : r1type_sgn, r1type_precision, r1val, r1mask,
1981 : r2type_sgn, r2type_precision, shift, r2mask);
1982 1715096 : return;
1983 : }
1984 2214152 : }
1985 2436996 : if (sgn == UNSIGNED
1986 2436996 : || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1987 : {
1988 : /* Confirm R2 has some bits set, to avoid division by zero. */
1989 745075 : widest_int r2min = wi::bit_and_not (r2val, r2mask);
1990 745075 : if (r2min != 0)
1991 : {
1992 : /* R1 / R2 is zero if R1 is always less than R2. */
1993 371054 : if (wi::ltu_p (r1max, r2min))
1994 : {
1995 2560 : *mask = 0;
1996 2560 : *val = 0;
1997 : }
1998 : else
1999 : {
2000 368494 : widest_int upper
2001 368494 : = wi::udiv_trunc (wi::zext (r1max, width), r2min);
2002 368494 : unsigned int lzcount = wi::clz (upper);
2003 368494 : unsigned int bits = wi::get_precision (upper) - lzcount;
2004 368494 : *mask = wi::mask <widest_int> (bits, false);
2005 368494 : *val = 0;
2006 368494 : }
2007 : }
2008 745075 : }
2009 4152096 : }
2010 2436996 : break;
2011 :
2012 169 : default:;
2013 : }
2014 : }
2015 :
2016 : /* Return the propagation value when applying the operation CODE to
2017 : the value RHS yielding type TYPE. */
2018 :
2019 : static ccp_prop_value_t
2020 31260293 : bit_value_unop (enum tree_code code, tree type, tree rhs)
2021 : {
2022 31260293 : ccp_prop_value_t rval = get_value_for_expr (rhs, true);
2023 31260293 : widest_int value, mask;
2024 31260293 : ccp_prop_value_t val;
2025 :
2026 31260293 : if (rval.lattice_val == UNDEFINED)
2027 0 : return rval;
2028 :
2029 31260293 : gcc_assert ((rval.lattice_val == CONSTANT
2030 : && TREE_CODE (rval.value) == INTEGER_CST)
2031 : || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1);
2032 62520586 : bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2033 31260293 : TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)),
2034 62520586 : value_to_wide_int (rval), rval.mask);
2035 31260489 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2036 : {
2037 24735121 : val.lattice_val = CONSTANT;
2038 24735121 : val.mask = mask;
2039 : /* ??? Delay building trees here. */
2040 24735121 : val.value = wide_int_to_tree (type, value);
2041 : }
2042 : else
2043 : {
2044 6525172 : val.lattice_val = VARYING;
2045 6525172 : val.value = NULL_TREE;
2046 6525172 : val.mask = -1;
2047 : }
2048 31260293 : return val;
2049 31260722 : }
2050 :
2051 : /* Return the propagation value when applying the operation CODE to
2052 : the values RHS1 and RHS2 yielding type TYPE. */
2053 :
2054 : static ccp_prop_value_t
2055 146509451 : bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
2056 : {
2057 146509451 : ccp_prop_value_t r1val = get_value_for_expr (rhs1, true);
2058 146509451 : ccp_prop_value_t r2val = get_value_for_expr (rhs2, true);
2059 146509451 : widest_int value, mask;
2060 146509451 : ccp_prop_value_t val;
2061 :
2062 146509451 : if (r1val.lattice_val == UNDEFINED
2063 146376121 : || r2val.lattice_val == UNDEFINED)
2064 : {
2065 139482 : val.lattice_val = VARYING;
2066 139482 : val.value = NULL_TREE;
2067 139482 : val.mask = -1;
2068 139482 : return val;
2069 : }
2070 :
2071 146369969 : gcc_assert ((r1val.lattice_val == CONSTANT
2072 : && TREE_CODE (r1val.value) == INTEGER_CST)
2073 : || wi::sext (r1val.mask,
2074 : TYPE_PRECISION (TREE_TYPE (rhs1))) == -1);
2075 146369969 : gcc_assert ((r2val.lattice_val == CONSTANT
2076 : && TREE_CODE (r2val.value) == INTEGER_CST)
2077 : || wi::sext (r2val.mask,
2078 : TYPE_PRECISION (TREE_TYPE (rhs2))) == -1);
2079 292739938 : bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2080 146369969 : TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)),
2081 292805549 : value_to_wide_int (r1val), r1val.mask,
2082 146369969 : TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)),
2083 292739938 : value_to_wide_int (r2val), r2val.mask);
2084 :
2085 : /* (x * x) & 2 == 0. */
2086 146369969 : if (code == MULT_EXPR && rhs1 == rhs2 && TYPE_PRECISION (type) > 1)
2087 : {
2088 175414 : widest_int m = 2;
2089 175414 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2090 299 : value = wi::bit_and_not (value, m);
2091 : else
2092 175115 : value = 0;
2093 175414 : mask = wi::bit_and_not (mask, m);
2094 175414 : }
2095 :
2096 146434951 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2097 : {
2098 122704759 : val.lattice_val = CONSTANT;
2099 122704759 : val.mask = mask;
2100 : /* ??? Delay building trees here. */
2101 122704759 : val.value = wide_int_to_tree (type, value);
2102 : }
2103 : else
2104 : {
2105 23665210 : val.lattice_val = VARYING;
2106 23665210 : val.value = NULL_TREE;
2107 23665210 : val.mask = -1;
2108 : }
2109 : return val;
2110 146509758 : }
2111 :
2112 : /* Return the propagation value for __builtin_assume_aligned
2113 : and functions with assume_aligned or alloc_aligned attribute.
2114 : For __builtin_assume_aligned, ATTR is NULL_TREE,
2115 : for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED
2116 : is false, for alloc_aligned attribute ATTR is non-NULL and
2117 : ALLOC_ALIGNED is true. */
2118 :
2119 : static ccp_prop_value_t
2120 8563 : bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval,
2121 : bool alloc_aligned)
2122 : {
2123 8563 : tree align, misalign = NULL_TREE, type;
2124 8563 : unsigned HOST_WIDE_INT aligni, misaligni = 0;
2125 8563 : ccp_prop_value_t alignval;
2126 8563 : widest_int value, mask;
2127 8563 : ccp_prop_value_t val;
2128 :
2129 8563 : if (attr == NULL_TREE)
2130 : {
2131 3581 : tree ptr = gimple_call_arg (stmt, 0);
2132 3581 : type = TREE_TYPE (ptr);
2133 3581 : ptrval = get_value_for_expr (ptr, true);
2134 : }
2135 : else
2136 : {
2137 4982 : tree lhs = gimple_call_lhs (stmt);
2138 4982 : type = TREE_TYPE (lhs);
2139 : }
2140 :
2141 8563 : if (ptrval.lattice_val == UNDEFINED)
2142 0 : return ptrval;
2143 8563 : gcc_assert ((ptrval.lattice_val == CONSTANT
2144 : && TREE_CODE (ptrval.value) == INTEGER_CST)
2145 : || wi::sext (ptrval.mask, TYPE_PRECISION (type)) == -1);
2146 8563 : if (attr == NULL_TREE)
2147 : {
2148 : /* Get aligni and misaligni from __builtin_assume_aligned. */
2149 3581 : align = gimple_call_arg (stmt, 1);
2150 3581 : if (!tree_fits_uhwi_p (align))
2151 47 : return ptrval;
2152 3534 : aligni = tree_to_uhwi (align);
2153 3534 : if (gimple_call_num_args (stmt) > 2)
2154 : {
2155 36 : misalign = gimple_call_arg (stmt, 2);
2156 36 : if (!tree_fits_uhwi_p (misalign))
2157 2 : return ptrval;
2158 34 : misaligni = tree_to_uhwi (misalign);
2159 : }
2160 : }
2161 : else
2162 : {
2163 : /* Get aligni and misaligni from assume_aligned or
2164 : alloc_align attributes. */
2165 4982 : if (TREE_VALUE (attr) == NULL_TREE)
2166 0 : return ptrval;
2167 4982 : attr = TREE_VALUE (attr);
2168 4982 : align = TREE_VALUE (attr);
2169 4982 : if (!tree_fits_uhwi_p (align))
2170 0 : return ptrval;
2171 4982 : aligni = tree_to_uhwi (align);
2172 4982 : if (alloc_aligned)
2173 : {
2174 4940 : if (aligni == 0 || aligni > gimple_call_num_args (stmt))
2175 0 : return ptrval;
2176 4940 : align = gimple_call_arg (stmt, aligni - 1);
2177 4940 : if (!tree_fits_uhwi_p (align))
2178 226 : return ptrval;
2179 4714 : aligni = tree_to_uhwi (align);
2180 : }
2181 42 : else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr)))
2182 : {
2183 21 : misalign = TREE_VALUE (TREE_CHAIN (attr));
2184 21 : if (!tree_fits_uhwi_p (misalign))
2185 0 : return ptrval;
2186 21 : misaligni = tree_to_uhwi (misalign);
2187 : }
2188 : }
2189 8288 : if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni)
2190 154 : return ptrval;
2191 :
2192 8134 : align = build_int_cst_type (type, -aligni);
2193 8134 : alignval = get_value_for_expr (align, true);
2194 16268 : bit_value_binop (BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2195 16268 : TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (ptrval), ptrval.mask,
2196 16268 : TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (alignval), alignval.mask);
2197 :
2198 8134 : if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2199 : {
2200 8134 : val.lattice_val = CONSTANT;
2201 8134 : val.mask = mask;
2202 8134 : gcc_assert ((mask.to_uhwi () & (aligni - 1)) == 0);
2203 8134 : gcc_assert ((value.to_uhwi () & (aligni - 1)) == 0);
2204 8134 : value |= misaligni;
2205 : /* ??? Delay building trees here. */
2206 8134 : val.value = wide_int_to_tree (type, value);
2207 : }
2208 : else
2209 : {
2210 0 : val.lattice_val = VARYING;
2211 0 : val.value = NULL_TREE;
2212 0 : val.mask = -1;
2213 : }
2214 8134 : return val;
2215 8563 : }
2216 :
2217 : /* Evaluate statement STMT.
2218 : Valid only for assignments, calls, conditionals, and switches. */
2219 :
2220 : static ccp_prop_value_t
2221 245451421 : evaluate_stmt (gimple *stmt)
2222 : {
2223 245451421 : ccp_prop_value_t val;
2224 245451421 : tree simplified = NULL_TREE;
2225 245451421 : ccp_lattice_t likelyvalue = likely_value (stmt);
2226 245451421 : bool is_constant = false;
2227 245451421 : unsigned int align;
2228 245451421 : bool ignore_return_flags = false;
2229 :
2230 245451421 : if (dump_file && (dump_flags & TDF_DETAILS))
2231 : {
2232 66 : fprintf (dump_file, "which is likely ");
2233 66 : switch (likelyvalue)
2234 : {
2235 65 : case CONSTANT:
2236 65 : fprintf (dump_file, "CONSTANT");
2237 65 : break;
2238 0 : case UNDEFINED:
2239 0 : fprintf (dump_file, "UNDEFINED");
2240 0 : break;
2241 1 : case VARYING:
2242 1 : fprintf (dump_file, "VARYING");
2243 1 : break;
2244 66 : default:;
2245 : }
2246 66 : fprintf (dump_file, "\n");
2247 : }
2248 :
2249 : /* If the statement is likely to have a CONSTANT result, then try
2250 : to fold the statement to determine the constant value. */
2251 : /* FIXME. This is the only place that we call ccp_fold.
2252 : Since likely_value never returns CONSTANT for calls, we will
2253 : not attempt to fold them, including builtins that may profit. */
2254 245451421 : if (likelyvalue == CONSTANT)
2255 : {
2256 245276250 : simplified = ccp_fold (stmt);
2257 245276250 : if (simplified
2258 34034302 : && TREE_CODE (simplified) == SSA_NAME)
2259 : {
2260 : /* We may not use values of something that may be simulated again,
2261 : see valueize_op_1. */
2262 17288045 : if (SSA_NAME_IS_DEFAULT_DEF (simplified)
2263 17288045 : || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (simplified)))
2264 : {
2265 12641945 : ccp_prop_value_t *val = get_value (simplified);
2266 12641945 : if (val && val->lattice_val != VARYING)
2267 612122 : return *val;
2268 : }
2269 : else
2270 : /* We may also not place a non-valueized copy in the lattice
2271 : as that might become stale if we never re-visit this stmt. */
2272 : simplified = NULL_TREE;
2273 : }
2274 28776080 : is_constant = simplified && is_gimple_min_invariant (simplified);
2275 13818831 : if (is_constant)
2276 : {
2277 : /* The statement produced a constant value. */
2278 13818831 : val.lattice_val = CONSTANT;
2279 13818831 : val.value = simplified;
2280 13818831 : val.mask = 0;
2281 13818831 : return val;
2282 : }
2283 : }
2284 : /* If the statement is likely to have a VARYING result, then do not
2285 : bother folding the statement. */
2286 175171 : else if (likelyvalue == VARYING)
2287 : {
2288 49391 : enum gimple_code code = gimple_code (stmt);
2289 49391 : if (code == GIMPLE_ASSIGN)
2290 : {
2291 814 : enum tree_code subcode = gimple_assign_rhs_code (stmt);
2292 :
2293 : /* Other cases cannot satisfy is_gimple_min_invariant
2294 : without folding. */
2295 814 : if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
2296 814 : simplified = gimple_assign_rhs1 (stmt);
2297 : }
2298 48577 : else if (code == GIMPLE_SWITCH)
2299 0 : simplified = gimple_switch_index (as_a <gswitch *> (stmt));
2300 : else
2301 : /* These cannot satisfy is_gimple_min_invariant without folding. */
2302 48577 : gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
2303 814 : is_constant = simplified && is_gimple_min_invariant (simplified);
2304 0 : if (is_constant)
2305 : {
2306 : /* The statement produced a constant value. */
2307 0 : val.lattice_val = CONSTANT;
2308 0 : val.value = simplified;
2309 0 : val.mask = 0;
2310 : }
2311 : }
2312 : /* If the statement result is likely UNDEFINED, make it so. */
2313 125780 : else if (likelyvalue == UNDEFINED)
2314 : {
2315 125780 : val.lattice_val = UNDEFINED;
2316 125780 : val.value = NULL_TREE;
2317 125780 : val.mask = 0;
2318 125780 : return val;
2319 : }
2320 :
2321 : /* Resort to simplification for bitwise tracking. */
2322 230894688 : if (flag_tree_bit_ccp
2323 230814677 : && (likelyvalue == CONSTANT || is_gimple_call (stmt)
2324 814 : || (gimple_assign_single_p (stmt)
2325 814 : && gimple_assign_rhs_code (stmt) == ADDR_EXPR))
2326 461708622 : && !is_constant)
2327 : {
2328 230813934 : enum gimple_code code = gimple_code (stmt);
2329 230813934 : val.lattice_val = VARYING;
2330 230813934 : val.value = NULL_TREE;
2331 230813934 : val.mask = -1;
2332 230813934 : if (code == GIMPLE_ASSIGN)
2333 : {
2334 185306260 : enum tree_code subcode = gimple_assign_rhs_code (stmt);
2335 185306260 : tree rhs1 = gimple_assign_rhs1 (stmt);
2336 185306260 : tree lhs = gimple_assign_lhs (stmt);
2337 370145519 : if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2338 35117448 : || POINTER_TYPE_P (TREE_TYPE (lhs)))
2339 363696721 : && (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2340 30198660 : || POINTER_TYPE_P (TREE_TYPE (rhs1))))
2341 178501587 : switch (get_gimple_rhs_class (subcode))
2342 : {
2343 40194816 : case GIMPLE_SINGLE_RHS:
2344 40194816 : val = get_value_for_expr (rhs1, true);
2345 40194816 : break;
2346 :
2347 31260293 : case GIMPLE_UNARY_RHS:
2348 31260293 : val = bit_value_unop (subcode, TREE_TYPE (lhs), rhs1);
2349 31260293 : break;
2350 :
2351 107025443 : case GIMPLE_BINARY_RHS:
2352 107025443 : val = bit_value_binop (subcode, TREE_TYPE (lhs), rhs1,
2353 107025443 : gimple_assign_rhs2 (stmt));
2354 107025443 : break;
2355 :
2356 : default:;
2357 : }
2358 : }
2359 45507674 : else if (code == GIMPLE_COND)
2360 : {
2361 40959580 : enum tree_code code = gimple_cond_code (stmt);
2362 40959580 : tree rhs1 = gimple_cond_lhs (stmt);
2363 40959580 : tree rhs2 = gimple_cond_rhs (stmt);
2364 81346631 : if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2365 48904115 : || POINTER_TYPE_P (TREE_TYPE (rhs1)))
2366 39484008 : val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
2367 : }
2368 4548094 : else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2369 : {
2370 2421312 : tree fndecl = gimple_call_fndecl (stmt);
2371 2421312 : switch (DECL_FUNCTION_CODE (fndecl))
2372 : {
2373 243515 : case BUILT_IN_MALLOC:
2374 243515 : case BUILT_IN_REALLOC:
2375 243515 : case BUILT_IN_GOMP_REALLOC:
2376 243515 : case BUILT_IN_CALLOC:
2377 243515 : case BUILT_IN_STRDUP:
2378 243515 : case BUILT_IN_STRNDUP:
2379 243515 : val.lattice_val = CONSTANT;
2380 243515 : val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2381 245748 : val.mask = ~((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT
2382 243515 : / BITS_PER_UNIT - 1);
2383 243515 : break;
2384 :
2385 52843 : CASE_BUILT_IN_ALLOCA:
2386 90691 : align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA
2387 37852 : ? BIGGEST_ALIGNMENT
2388 14991 : : TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2389 52843 : val.lattice_val = CONSTANT;
2390 52843 : val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2391 52843 : val.mask = ~((HOST_WIDE_INT) align / BITS_PER_UNIT - 1);
2392 52843 : break;
2393 :
2394 3195 : case BUILT_IN_ASSUME_ALIGNED:
2395 3195 : val = bit_value_assume_aligned (stmt, NULL_TREE, val, false);
2396 3195 : ignore_return_flags = true;
2397 3195 : break;
2398 :
2399 130 : case BUILT_IN_ALIGNED_ALLOC:
2400 130 : case BUILT_IN_GOMP_ALLOC:
2401 130 : {
2402 130 : tree align = get_constant_value (gimple_call_arg (stmt, 0));
2403 130 : if (align
2404 122 : && tree_fits_uhwi_p (align))
2405 : {
2406 122 : unsigned HOST_WIDE_INT aligni = tree_to_uhwi (align);
2407 122 : if (aligni > 1
2408 : /* align must be power-of-two */
2409 106 : && (aligni & (aligni - 1)) == 0)
2410 : {
2411 106 : val.lattice_val = CONSTANT;
2412 106 : val.value = build_int_cst (ptr_type_node, 0);
2413 106 : val.mask = -aligni;
2414 : }
2415 : }
2416 : break;
2417 : }
2418 :
2419 5702 : case BUILT_IN_BSWAP16:
2420 5702 : case BUILT_IN_BSWAP32:
2421 5702 : case BUILT_IN_BSWAP64:
2422 5702 : case BUILT_IN_BSWAP128:
2423 5702 : val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
2424 5702 : if (val.lattice_val == UNDEFINED)
2425 : break;
2426 5702 : else if (val.lattice_val == CONSTANT
2427 2485 : && val.value
2428 2485 : && TREE_CODE (val.value) == INTEGER_CST)
2429 : {
2430 2485 : tree type = TREE_TYPE (gimple_call_lhs (stmt));
2431 2485 : int prec = TYPE_PRECISION (type);
2432 2485 : wide_int wval = wi::to_wide (val.value);
2433 2485 : val.value
2434 2485 : = wide_int_to_tree (type,
2435 4970 : wi::bswap (wide_int::from (wval, prec,
2436 : UNSIGNED)));
2437 2485 : val.mask
2438 4970 : = widest_int::from (wi::bswap (wide_int::from (val.mask,
2439 : prec,
2440 : UNSIGNED)),
2441 2485 : UNSIGNED);
2442 2485 : if (wi::sext (val.mask, prec) != -1)
2443 : break;
2444 2485 : }
2445 3217 : val.lattice_val = VARYING;
2446 3217 : val.value = NULL_TREE;
2447 3217 : val.mask = -1;
2448 3217 : break;
2449 :
2450 408 : case BUILT_IN_BITREVERSE8:
2451 408 : case BUILT_IN_BITREVERSE16:
2452 408 : case BUILT_IN_BITREVERSE32:
2453 408 : case BUILT_IN_BITREVERSE64:
2454 408 : case BUILT_IN_BITREVERSE128:
2455 408 : val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
2456 408 : if (val.lattice_val == UNDEFINED)
2457 : break;
2458 408 : else if (val.lattice_val == CONSTANT
2459 20 : && val.value
2460 20 : && TREE_CODE (val.value) == INTEGER_CST)
2461 : {
2462 20 : tree type = TREE_TYPE (gimple_call_lhs (stmt));
2463 20 : int prec = TYPE_PRECISION (type);
2464 20 : wide_int wval = wi::to_wide (val.value);
2465 20 : wval = wide_int::from (wval, prec, UNSIGNED);
2466 20 : wide_int wmask = wide_int::from (val.mask, prec, UNSIGNED);
2467 20 : val.value = wide_int_to_tree (type, wi::bitreverse (wval));
2468 40 : val.mask = widest_int::from (wi::bitreverse (wmask),
2469 20 : UNSIGNED);
2470 20 : if (wi::sext (val.mask, prec) != -1)
2471 : break;
2472 20 : }
2473 388 : val.lattice_val = VARYING;
2474 388 : val.value = NULL_TREE;
2475 388 : val.mask = -1;
2476 388 : break;
2477 :
2478 0 : default:;
2479 : }
2480 : }
2481 230813934 : if (is_gimple_call (stmt) && gimple_call_lhs (stmt))
2482 : {
2483 4454316 : tree fntype = gimple_call_fntype (stmt);
2484 4454316 : if (fntype)
2485 : {
2486 3922742 : tree attrs = lookup_attribute ("assume_aligned",
2487 3922742 : TYPE_ATTRIBUTES (fntype));
2488 3922742 : if (attrs)
2489 42 : val = bit_value_assume_aligned (stmt, attrs, val, false);
2490 3922742 : attrs = lookup_attribute ("alloc_align",
2491 3922742 : TYPE_ATTRIBUTES (fntype));
2492 3922742 : if (attrs)
2493 4940 : val = bit_value_assume_aligned (stmt, attrs, val, true);
2494 : }
2495 4454316 : int flags = ignore_return_flags
2496 4454316 : ? 0 : gimple_call_return_flags (as_a <gcall *> (stmt));
2497 4451121 : if (flags & ERF_RETURNS_ARG
2498 4451121 : && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
2499 : {
2500 156807 : val = get_value_for_expr
2501 313614 : (gimple_call_arg (stmt,
2502 156807 : flags & ERF_RETURN_ARG_MASK), true);
2503 : }
2504 : }
2505 230813934 : is_constant = (val.lattice_val == CONSTANT);
2506 : }
2507 :
2508 230894688 : tree lhs = gimple_get_lhs (stmt);
2509 230894688 : if (flag_tree_bit_ccp
2510 230814677 : && lhs && TREE_CODE (lhs) == SSA_NAME && !VECTOR_TYPE_P (TREE_TYPE (lhs))
2511 418536506 : && ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
2512 : || !is_constant))
2513 : {
2514 187641818 : tree lhs = gimple_get_lhs (stmt);
2515 187641818 : wide_int nonzero_bits = get_nonzero_bits (lhs);
2516 187641818 : if (nonzero_bits != -1)
2517 : {
2518 53619057 : if (!is_constant)
2519 : {
2520 4301482 : val.lattice_val = CONSTANT;
2521 4301482 : val.value = build_zero_cst (TREE_TYPE (lhs));
2522 4301482 : val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (lhs)));
2523 4301482 : is_constant = true;
2524 : }
2525 : else
2526 : {
2527 49317698 : if (wi::bit_and_not (wi::to_wide (val.value), nonzero_bits) != 0)
2528 63970 : val.value = wide_int_to_tree (TREE_TYPE (lhs),
2529 : nonzero_bits
2530 127940 : & wi::to_wide (val.value));
2531 49317575 : if (nonzero_bits == 0)
2532 124 : val.mask = 0;
2533 : else
2534 98635001 : val.mask = val.mask & extend_mask (nonzero_bits,
2535 98634902 : TYPE_SIGN (TREE_TYPE (lhs)));
2536 : }
2537 : }
2538 187641818 : }
2539 :
2540 : /* The statement produced a nonconstant value. */
2541 230894688 : if (!is_constant)
2542 : {
2543 : /* The statement produced a copy. */
2544 14454272 : if (simplified && TREE_CODE (simplified) == SSA_NAME
2545 87023400 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (simplified))
2546 : {
2547 12010556 : val.lattice_val = CONSTANT;
2548 12010556 : val.value = simplified;
2549 12010556 : val.mask = -1;
2550 : }
2551 : /* The statement is VARYING. */
2552 : else
2553 : {
2554 63000447 : val.lattice_val = VARYING;
2555 63000447 : val.value = NULL_TREE;
2556 63000447 : val.mask = -1;
2557 : }
2558 : }
2559 :
2560 230894688 : return val;
2561 245451421 : }
2562 :
2563 : typedef hash_table<nofree_ptr_hash<gimple> > gimple_htab;
2564 :
2565 : /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
2566 : each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
2567 :
2568 : static void
2569 527 : insert_clobber_before_stack_restore (tree saved_val, tree var,
2570 : gimple_htab **visited)
2571 : {
2572 527 : gimple *stmt;
2573 527 : gassign *clobber_stmt;
2574 527 : tree clobber;
2575 527 : imm_use_iterator iter;
2576 527 : gimple_stmt_iterator i;
2577 527 : gimple **slot;
2578 :
2579 1058 : FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
2580 531 : if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
2581 : {
2582 518 : clobber = build_clobber (TREE_TYPE (var), CLOBBER_STORAGE_END);
2583 518 : clobber_stmt = gimple_build_assign (var, clobber);
2584 : /* Manually update the vdef/vuse here. */
2585 1036 : gimple_set_vuse (clobber_stmt, gimple_vuse (stmt));
2586 518 : gimple_set_vdef (clobber_stmt, make_ssa_name (gimple_vop (cfun)));
2587 1036 : gimple_set_vuse (stmt, gimple_vdef (clobber_stmt));
2588 1036 : SSA_NAME_DEF_STMT (gimple_vdef (clobber_stmt)) = clobber_stmt;
2589 518 : update_stmt (stmt);
2590 518 : i = gsi_for_stmt (stmt);
2591 518 : gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
2592 : }
2593 13 : else if (gimple_code (stmt) == GIMPLE_PHI)
2594 : {
2595 12 : if (!*visited)
2596 12 : *visited = new gimple_htab (10);
2597 :
2598 12 : slot = (*visited)->find_slot (stmt, INSERT);
2599 12 : if (*slot != NULL)
2600 0 : continue;
2601 :
2602 12 : *slot = stmt;
2603 12 : insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
2604 : visited);
2605 : }
2606 1 : else if (gimple_assign_ssa_name_copy_p (stmt))
2607 0 : insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var,
2608 527 : visited);
2609 527 : }
2610 :
2611 : /* Advance the iterator to the previous non-debug gimple statement in the same
2612 : or dominating basic block. */
2613 :
2614 : static inline void
2615 12040 : gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
2616 : {
2617 12040 : basic_block dom;
2618 :
2619 12040 : gsi_prev_nondebug (i);
2620 24702 : while (gsi_end_p (*i))
2621 : {
2622 630 : dom = get_immediate_dominator (CDI_DOMINATORS, gsi_bb (*i));
2623 630 : if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2624 : return;
2625 :
2626 1244 : *i = gsi_last_bb (dom);
2627 : }
2628 : }
2629 :
2630 : /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
2631 : a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
2632 :
2633 : It is possible that BUILT_IN_STACK_SAVE cannot be found in a dominator when
2634 : a previous pass (such as DOM) duplicated it along multiple paths to a BB.
2635 : In that case the function gives up without inserting the clobbers. */
2636 :
2637 : static void
2638 523 : insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
2639 : {
2640 523 : gimple *stmt;
2641 523 : tree saved_val;
2642 523 : gimple_htab *visited = NULL;
2643 :
2644 12563 : for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
2645 : {
2646 12555 : stmt = gsi_stmt (i);
2647 :
2648 12555 : if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
2649 12040 : continue;
2650 :
2651 515 : saved_val = gimple_call_lhs (stmt);
2652 515 : if (saved_val == NULL_TREE)
2653 0 : continue;
2654 :
2655 515 : insert_clobber_before_stack_restore (saved_val, var, &visited);
2656 515 : break;
2657 : }
2658 :
2659 523 : delete visited;
2660 523 : }
2661 :
2662 : /* Detects a __builtin_alloca_with_align with constant size argument. Declares
2663 : fixed-size array and returns the address, if found, otherwise returns
2664 : NULL_TREE. */
2665 :
2666 : static tree
2667 12293 : fold_builtin_alloca_with_align (gimple *stmt)
2668 : {
2669 12293 : unsigned HOST_WIDE_INT size, threshold, n_elem;
2670 12293 : tree lhs, arg, block, var, elem_type, array_type;
2671 :
2672 : /* Get lhs. */
2673 12293 : lhs = gimple_call_lhs (stmt);
2674 12293 : if (lhs == NULL_TREE)
2675 : return NULL_TREE;
2676 :
2677 : /* Detect constant argument. */
2678 12293 : arg = get_constant_value (gimple_call_arg (stmt, 0));
2679 12293 : if (arg == NULL_TREE
2680 1089 : || TREE_CODE (arg) != INTEGER_CST
2681 1089 : || !tree_fits_uhwi_p (arg))
2682 : return NULL_TREE;
2683 :
2684 1089 : size = tree_to_uhwi (arg);
2685 :
2686 : /* Heuristic: don't fold large allocas. */
2687 1089 : threshold = (unsigned HOST_WIDE_INT)param_large_stack_frame;
2688 : /* In case the alloca is located at function entry, it has the same lifetime
2689 : as a declared array, so we allow a larger size. */
2690 1089 : block = gimple_block (stmt);
2691 1089 : if (!(cfun->after_inlining
2692 708 : && block
2693 680 : && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
2694 704 : threshold /= 10;
2695 1089 : if (size > threshold)
2696 : return NULL_TREE;
2697 :
2698 : /* We have to be able to move points-to info. We used to assert
2699 : that we can but IPA PTA might end up with two UIDs here
2700 : as it might need to handle more than one instance being
2701 : live at the same time. Instead of trying to detect this case
2702 : (using the first UID would be OK) just give up for now. */
2703 547 : const pt_solution *pt = ssa_name_pt_solution (lhs);
2704 547 : unsigned uid = 0;
2705 100 : if (pt != NULL
2706 185 : && !pt->anything
2707 611 : && !pt_solution_singleton_or_null_p (pt, &uid))
2708 : return NULL_TREE;
2709 :
2710 : /* Declare array. */
2711 523 : elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
2712 523 : n_elem = size * 8 / BITS_PER_UNIT;
2713 523 : array_type = build_array_type_nelts (elem_type, n_elem);
2714 :
2715 523 : if (tree ssa_name = SSA_NAME_IDENTIFIER (lhs))
2716 : {
2717 : /* Give the temporary a name derived from the name of the VLA
2718 : declaration so it can be referenced in diagnostics. */
2719 481 : const char *name = IDENTIFIER_POINTER (ssa_name);
2720 481 : var = create_tmp_var (array_type, name);
2721 : }
2722 : else
2723 42 : var = create_tmp_var (array_type);
2724 :
2725 523 : if (gimple *lhsdef = SSA_NAME_DEF_STMT (lhs))
2726 : {
2727 : /* Set the temporary's location to that of the VLA declaration
2728 : so it can be pointed to in diagnostics. */
2729 523 : location_t loc = gimple_location (lhsdef);
2730 523 : DECL_SOURCE_LOCATION (var) = loc;
2731 : }
2732 :
2733 523 : SET_DECL_ALIGN (var, TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2734 523 : if (uid != 0)
2735 140 : SET_DECL_PT_UID (var, uid);
2736 :
2737 : /* Fold alloca to the address of the array. */
2738 523 : return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
2739 : }
2740 :
2741 : /* Fold the stmt at *GSI with CCP specific information that propagating
2742 : and regular folding does not catch. */
2743 :
2744 : bool
2745 364907875 : ccp_folder::fold_stmt (gimple_stmt_iterator *gsi)
2746 : {
2747 364907875 : gimple *stmt = gsi_stmt (*gsi);
2748 :
2749 364907875 : switch (gimple_code (stmt))
2750 : {
2751 19174091 : case GIMPLE_COND:
2752 19174091 : {
2753 19174091 : gcond *cond_stmt = as_a <gcond *> (stmt);
2754 19174091 : ccp_prop_value_t val;
2755 : /* Statement evaluation will handle type mismatches in constants
2756 : more gracefully than the final propagation. This allows us to
2757 : fold more conditionals here. */
2758 19174091 : val = evaluate_stmt (stmt);
2759 19174091 : if (val.lattice_val != CONSTANT
2760 19174091 : || val.mask != 0)
2761 : return false;
2762 :
2763 479263 : if (dump_file)
2764 : {
2765 24 : fprintf (dump_file, "Folding predicate ");
2766 24 : print_gimple_expr (dump_file, stmt, 0);
2767 24 : fprintf (dump_file, " to ");
2768 24 : print_generic_expr (dump_file, val.value);
2769 24 : fprintf (dump_file, "\n");
2770 : }
2771 :
2772 479263 : if (integer_zerop (val.value))
2773 355489 : gimple_cond_make_false (cond_stmt);
2774 : else
2775 123774 : gimple_cond_make_true (cond_stmt);
2776 :
2777 : return true;
2778 19174091 : }
2779 :
2780 24227520 : case GIMPLE_CALL:
2781 24227520 : {
2782 24227520 : tree lhs = gimple_call_lhs (stmt);
2783 24227520 : int flags = gimple_call_flags (stmt);
2784 24227520 : tree val;
2785 24227520 : tree argt;
2786 24227520 : bool changed = false;
2787 24227520 : unsigned i;
2788 :
2789 : /* If the call was folded into a constant make sure it goes
2790 : away even if we cannot propagate into all uses because of
2791 : type issues. */
2792 24227520 : if (lhs
2793 9251698 : && TREE_CODE (lhs) == SSA_NAME
2794 7725557 : && (val = get_constant_value (lhs))
2795 : /* Don't optimize away calls that have side-effects. */
2796 15 : && (flags & (ECF_CONST|ECF_PURE)) != 0
2797 24227520 : && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
2798 : {
2799 0 : tree new_rhs = unshare_expr (val);
2800 0 : if (!useless_type_conversion_p (TREE_TYPE (lhs),
2801 0 : TREE_TYPE (new_rhs)))
2802 0 : new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
2803 0 : gimplify_and_update_call_from_tree (gsi, new_rhs);
2804 0 : return true;
2805 : }
2806 :
2807 : /* Internal calls provide no argument types, so the extra laxity
2808 : for normal calls does not apply. */
2809 24227520 : if (gimple_call_internal_p (stmt))
2810 : return false;
2811 :
2812 : /* The heuristic of fold_builtin_alloca_with_align differs before and
2813 : after inlining, so we don't require the arg to be changed into a
2814 : constant for folding, but just to be constant. */
2815 23429049 : if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)
2816 23429049 : || gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
2817 : {
2818 12293 : tree new_rhs = fold_builtin_alloca_with_align (stmt);
2819 12293 : if (new_rhs)
2820 : {
2821 523 : gimplify_and_update_call_from_tree (gsi, new_rhs);
2822 523 : tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
2823 523 : insert_clobbers_for_var (*gsi, var);
2824 523 : return true;
2825 : }
2826 : }
2827 :
2828 : /* If there's no extra info from an assume_aligned call,
2829 : drop it so it doesn't act as otherwise useless dataflow
2830 : barrier. */
2831 23428526 : if (gimple_call_builtin_p (stmt, BUILT_IN_ASSUME_ALIGNED))
2832 : {
2833 3195 : tree ptr = gimple_call_arg (stmt, 0);
2834 3195 : ccp_prop_value_t ptrval = get_value_for_expr (ptr, true);
2835 3195 : if (ptrval.lattice_val == CONSTANT
2836 386 : && TREE_CODE (ptrval.value) == INTEGER_CST
2837 3581 : && ptrval.mask != 0)
2838 : {
2839 386 : ccp_prop_value_t val
2840 386 : = bit_value_assume_aligned (stmt, NULL_TREE, ptrval, false);
2841 386 : unsigned int ptralign = least_bit_hwi (ptrval.mask.to_uhwi ());
2842 386 : unsigned int align = least_bit_hwi (val.mask.to_uhwi ());
2843 386 : if (ptralign == align
2844 386 : && ((TREE_INT_CST_LOW (ptrval.value) & (align - 1))
2845 368 : == (TREE_INT_CST_LOW (val.value) & (align - 1))))
2846 : {
2847 368 : replace_call_with_value (gsi, ptr);
2848 368 : return true;
2849 : }
2850 386 : }
2851 3195 : }
2852 :
2853 : /* Propagate into the call arguments. Compared to replace_uses_in
2854 : this can use the argument slot types for type verification
2855 : instead of the current argument type. We also can safely
2856 : drop qualifiers here as we are dealing with constants anyway. */
2857 23428158 : argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
2858 64993976 : for (i = 0; i < gimple_call_num_args (stmt) && argt;
2859 41565818 : ++i, argt = TREE_CHAIN (argt))
2860 : {
2861 41565818 : tree arg = gimple_call_arg (stmt, i);
2862 41565818 : if (TREE_CODE (arg) == SSA_NAME
2863 16143037 : && (val = get_constant_value (arg))
2864 41565848 : && useless_type_conversion_p
2865 30 : (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
2866 30 : TYPE_MAIN_VARIANT (TREE_TYPE (val))))
2867 : {
2868 30 : gimple_call_set_arg (stmt, i, unshare_expr (val));
2869 30 : changed = true;
2870 : }
2871 : }
2872 :
2873 : return changed;
2874 : }
2875 :
2876 109806843 : case GIMPLE_ASSIGN:
2877 109806843 : {
2878 109806843 : tree lhs = gimple_assign_lhs (stmt);
2879 109806843 : tree val;
2880 :
2881 : /* If we have a load that turned out to be constant replace it
2882 : as we cannot propagate into all uses in all cases. */
2883 109806843 : if (gimple_assign_single_p (stmt)
2884 73375277 : && TREE_CODE (lhs) == SSA_NAME
2885 143621257 : && (val = get_constant_value (lhs)))
2886 : {
2887 5264 : tree rhs = unshare_expr (val);
2888 5264 : if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2889 0 : rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2890 5264 : gimple_assign_set_rhs_from_tree (gsi, rhs);
2891 5264 : return true;
2892 : }
2893 :
2894 : return false;
2895 : }
2896 :
2897 : default:
2898 : return false;
2899 : }
2900 : }
2901 :
2902 : /* Visit the assignment statement STMT. Set the value of its LHS to the
2903 : value computed by the RHS and store LHS in *OUTPUT_P. If STMT
2904 : creates virtual definitions, set the value of each new name to that
2905 : of the RHS (if we can derive a constant out of the RHS).
2906 : Value-returning call statements also perform an assignment, and
2907 : are handled here. */
2908 :
2909 : static enum ssa_prop_result
2910 203471392 : visit_assignment (gimple *stmt, tree *output_p)
2911 : {
2912 203471392 : ccp_prop_value_t val;
2913 203471392 : enum ssa_prop_result retval = SSA_PROP_NOT_INTERESTING;
2914 :
2915 203471392 : tree lhs = gimple_get_lhs (stmt);
2916 203471392 : if (TREE_CODE (lhs) == SSA_NAME)
2917 : {
2918 : /* Evaluate the statement, which could be
2919 : either a GIMPLE_ASSIGN or a GIMPLE_CALL. */
2920 202026241 : val = evaluate_stmt (stmt);
2921 :
2922 : /* If STMT is an assignment to an SSA_NAME, we only have one
2923 : value to set. */
2924 202026241 : if (set_lattice_value (lhs, &val))
2925 : {
2926 187535983 : *output_p = lhs;
2927 187535983 : if (val.lattice_val == VARYING)
2928 : retval = SSA_PROP_VARYING;
2929 : else
2930 127696339 : retval = SSA_PROP_INTERESTING;
2931 : }
2932 : }
2933 :
2934 203471392 : return retval;
2935 203471392 : }
2936 :
2937 :
2938 : /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
2939 : if it can determine which edge will be taken. Otherwise, return
2940 : SSA_PROP_VARYING. */
2941 :
2942 : static enum ssa_prop_result
2943 24251089 : visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
2944 : {
2945 24251089 : ccp_prop_value_t val;
2946 24251089 : basic_block block;
2947 :
2948 24251089 : block = gimple_bb (stmt);
2949 24251089 : val = evaluate_stmt (stmt);
2950 24251089 : if (val.lattice_val != CONSTANT
2951 24251089 : || val.mask != 0)
2952 : return SSA_PROP_VARYING;
2953 :
2954 : /* Find which edge out of the conditional block will be taken and add it
2955 : to the worklist. If no single edge can be determined statically,
2956 : return SSA_PROP_VARYING to feed all the outgoing edges to the
2957 : propagation engine. */
2958 5554682 : *taken_edge_p = find_taken_edge (block, val.value);
2959 5554682 : if (*taken_edge_p)
2960 : return SSA_PROP_INTERESTING;
2961 : else
2962 0 : return SSA_PROP_VARYING;
2963 24251089 : }
2964 :
2965 :
2966 : /* Evaluate statement STMT. If the statement produces an output value and
2967 : its evaluation changes the lattice value of its output, return
2968 : SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2969 : output value.
2970 :
2971 : If STMT is a conditional branch and we can determine its truth
2972 : value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
2973 : value, return SSA_PROP_VARYING. */
2974 :
2975 : enum ssa_prop_result
2976 240080733 : ccp_propagate::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
2977 : {
2978 240080733 : tree def;
2979 240080733 : ssa_op_iter iter;
2980 :
2981 240080733 : if (dump_file && (dump_flags & TDF_DETAILS))
2982 : {
2983 100 : fprintf (dump_file, "\nVisiting statement:\n");
2984 100 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2985 : }
2986 :
2987 240080733 : switch (gimple_code (stmt))
2988 : {
2989 198035988 : case GIMPLE_ASSIGN:
2990 : /* If the statement is an assignment that produces a single
2991 : output value, evaluate its RHS to see if the lattice value of
2992 : its output has changed. */
2993 198035988 : return visit_assignment (stmt, output_p);
2994 :
2995 10960287 : case GIMPLE_CALL:
2996 : /* A value-returning call also performs an assignment. */
2997 10960287 : if (gimple_call_lhs (stmt) != NULL_TREE)
2998 5435404 : return visit_assignment (stmt, output_p);
2999 : break;
3000 :
3001 24251089 : case GIMPLE_COND:
3002 24251089 : case GIMPLE_SWITCH:
3003 : /* If STMT is a conditional branch, see if we can determine
3004 : which branch will be taken. */
3005 : /* FIXME. It appears that we should be able to optimize
3006 : computed GOTOs here as well. */
3007 24251089 : return visit_cond_stmt (stmt, taken_edge_p);
3008 :
3009 : default:
3010 : break;
3011 : }
3012 :
3013 : /* Any other kind of statement is not interesting for constant
3014 : propagation and, therefore, not worth simulating. */
3015 12358252 : if (dump_file && (dump_flags & TDF_DETAILS))
3016 42 : fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
3017 :
3018 : /* Definitions made by statements other than assignments to
3019 : SSA_NAMEs represent unknown modifications to their outputs.
3020 : Mark them VARYING. */
3021 17201368 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
3022 4843116 : set_value_varying (def);
3023 :
3024 : return SSA_PROP_VARYING;
3025 : }
3026 :
3027 :
3028 : /* Main entry point for SSA Conditional Constant Propagation. If NONZERO_P,
3029 : record nonzero bits. */
3030 :
3031 : static unsigned int
3032 5714131 : do_ssa_ccp (bool nonzero_p)
3033 : {
3034 5714131 : unsigned int todo = 0;
3035 :
3036 : /* We want to minimize the number of latches to reduce iteration. */
3037 5714131 : loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
3038 :
3039 5714131 : calculate_dominance_info (CDI_DOMINATORS);
3040 :
3041 5714131 : ccp_initialize ();
3042 5714131 : class ccp_propagate ccp_propagate;
3043 5714131 : ccp_propagate.ssa_propagate ();
3044 11319074 : if (ccp_finalize (nonzero_p || flag_ipa_bit_cp))
3045 : {
3046 1721275 : todo = TODO_cleanup_cfg;
3047 :
3048 : /* ccp_finalize does not preserve loop-closed ssa. */
3049 1721275 : loops_state_clear (LOOP_CLOSED_SSA);
3050 : }
3051 :
3052 5714131 : free_dominance_info (CDI_DOMINATORS);
3053 :
3054 5714131 : loop_optimizer_finalize ();
3055 :
3056 5714131 : return todo;
3057 5714131 : }
3058 :
3059 :
3060 : namespace {
3061 :
3062 : const pass_data pass_data_ccp =
3063 : {
3064 : GIMPLE_PASS, /* type */
3065 : "ccp", /* name */
3066 : OPTGROUP_NONE, /* optinfo_flags */
3067 : TV_TREE_CCP, /* tv_id */
3068 : ( PROP_cfg | PROP_ssa ), /* properties_required */
3069 : 0, /* properties_provided */
3070 : 0, /* properties_destroyed */
3071 : 0, /* todo_flags_start */
3072 : TODO_update_address_taken, /* todo_flags_finish */
3073 : };
3074 :
3075 : class pass_ccp : public gimple_opt_pass
3076 : {
3077 : public:
3078 1485900 : pass_ccp (gcc::context *ctxt)
3079 2971800 : : gimple_opt_pass (pass_data_ccp, ctxt), nonzero_p (false)
3080 : {}
3081 :
3082 : /* opt_pass methods: */
3083 1188720 : opt_pass * clone () final override { return new pass_ccp (m_ctxt); }
3084 1485900 : void set_pass_param (unsigned int n, bool param) final override
3085 : {
3086 1485900 : gcc_assert (n == 0);
3087 1485900 : nonzero_p = param;
3088 1485900 : }
3089 5716205 : bool gate (function *) final override { return flag_tree_ccp != 0; }
3090 5714131 : unsigned int execute (function *) final override
3091 : {
3092 5714131 : return do_ssa_ccp (nonzero_p);
3093 : }
3094 :
3095 : private:
3096 : /* Determines whether the pass instance records nonzero bits. */
3097 : bool nonzero_p;
3098 : }; // class pass_ccp
3099 :
3100 : } // anon namespace
3101 :
3102 : gimple_opt_pass *
3103 297180 : make_pass_ccp (gcc::context *ctxt)
3104 : {
3105 297180 : return new pass_ccp (ctxt);
3106 : }
3107 :
3108 : /* A simple pass that emits some warnings post IPA. */
3109 :
3110 : namespace {
3111 :
3112 : const pass_data pass_data_post_ipa_warn =
3113 : {
3114 : GIMPLE_PASS, /* type */
3115 : "post_ipa_warn", /* name */
3116 : OPTGROUP_NONE, /* optinfo_flags */
3117 : TV_NONE, /* tv_id */
3118 : ( PROP_cfg | PROP_ssa ), /* properties_required */
3119 : 0, /* properties_provided */
3120 : 0, /* properties_destroyed */
3121 : 0, /* todo_flags_start */
3122 : 0, /* todo_flags_finish */
3123 : };
3124 :
3125 : class pass_post_ipa_warn : public gimple_opt_pass
3126 : {
3127 : public:
3128 594360 : pass_post_ipa_warn (gcc::context *ctxt)
3129 1188720 : : gimple_opt_pass (pass_data_post_ipa_warn, ctxt)
3130 : {}
3131 :
3132 : /* opt_pass methods: */
3133 297180 : opt_pass * clone () final override { return new pass_post_ipa_warn (m_ctxt); }
3134 1065452 : bool gate (function *) final override { return warn_nonnull != 0; }
3135 : unsigned int execute (function *) final override;
3136 :
3137 : }; // class pass_fold_builtins
3138 :
3139 : unsigned int
3140 113149 : pass_post_ipa_warn::execute (function *fun)
3141 : {
3142 113149 : basic_block bb;
3143 113149 : gimple_ranger *ranger = NULL;
3144 :
3145 1132946 : FOR_EACH_BB_FN (bb, fun)
3146 : {
3147 1019797 : gimple_stmt_iterator gsi;
3148 11004514 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3149 : {
3150 8964920 : gimple *stmt = gsi_stmt (gsi);
3151 8964920 : if (!is_gimple_call (stmt) || warning_suppressed_p (stmt, OPT_Wnonnull))
3152 8407126 : continue;
3153 :
3154 557794 : tree fntype = gimple_call_fntype (stmt);
3155 557794 : if (!fntype)
3156 5578 : continue;
3157 552216 : bitmap nonnullargs = get_nonnull_args (fntype);
3158 :
3159 552216 : tree fndecl = gimple_call_fndecl (stmt);
3160 1070899 : const bool closure = fndecl && DECL_LAMBDA_FUNCTION_P (fndecl);
3161 :
3162 813505 : for (unsigned i = nonnullargs ? 0 : ~0U;
3163 813505 : i < gimple_call_num_args (stmt); i++)
3164 : {
3165 261289 : tree arg = gimple_call_arg (stmt, i);
3166 261289 : if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE)
3167 261184 : continue;
3168 164493 : if (!integer_zerop (arg))
3169 156264 : continue;
3170 8229 : if (i == 0 && closure)
3171 : /* Avoid warning for the first argument to lambda functions. */
3172 14 : continue;
3173 8215 : if (!bitmap_empty_p (nonnullargs)
3174 8215 : && !bitmap_bit_p (nonnullargs, i))
3175 8095 : continue;
3176 :
3177 : /* In C++ non-static member functions argument 0 refers
3178 : to the implicit this pointer. Use the same one-based
3179 : numbering for ordinary arguments. */
3180 120 : unsigned argno = TREE_CODE (fntype) == METHOD_TYPE ? i : i + 1;
3181 120 : location_t loc = (EXPR_HAS_LOCATION (arg)
3182 0 : ? EXPR_LOCATION (arg)
3183 120 : : gimple_location (stmt));
3184 120 : auto_diagnostic_group d;
3185 120 : if (argno == 0)
3186 : {
3187 21 : if (warning_at (loc, OPT_Wnonnull,
3188 : "%qs pointer is null", "this")
3189 15 : && fndecl)
3190 9 : inform (DECL_SOURCE_LOCATION (fndecl),
3191 : "in a call to non-static member function %qD",
3192 : fndecl);
3193 15 : continue;
3194 : }
3195 :
3196 105 : if (!warning_at (loc, OPT_Wnonnull,
3197 : "argument %u null where non-null "
3198 : "expected", argno))
3199 0 : continue;
3200 :
3201 105 : tree fndecl = gimple_call_fndecl (stmt);
3202 105 : if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
3203 53 : inform (loc, "in a call to built-in function %qD",
3204 : fndecl);
3205 52 : else if (fndecl)
3206 52 : inform (DECL_SOURCE_LOCATION (fndecl),
3207 : "in a call to function %qD declared %qs",
3208 : fndecl, "nonnull");
3209 120 : }
3210 552216 : BITMAP_FREE (nonnullargs);
3211 :
3212 552216 : for (tree attrs = TYPE_ATTRIBUTES (fntype);
3213 590498 : (attrs = lookup_attribute ("nonnull_if_nonzero", attrs));
3214 38282 : attrs = TREE_CHAIN (attrs))
3215 : {
3216 38282 : tree args = TREE_VALUE (attrs);
3217 38282 : unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (args)) - 1;
3218 38282 : unsigned int idx2
3219 38282 : = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (args))) - 1;
3220 38282 : unsigned int idx3 = idx2;
3221 38282 : if (tree chain2 = TREE_CHAIN (TREE_CHAIN (args)))
3222 923 : idx3 = TREE_INT_CST_LOW (TREE_VALUE (chain2)) - 1;
3223 38282 : if (idx < gimple_call_num_args (stmt)
3224 38281 : && idx2 < gimple_call_num_args (stmt)
3225 76562 : && idx3 < gimple_call_num_args (stmt))
3226 : {
3227 38280 : tree arg = gimple_call_arg (stmt, idx);
3228 38280 : tree arg2 = gimple_call_arg (stmt, idx2);
3229 38280 : tree arg3 = gimple_call_arg (stmt, idx3);
3230 38280 : if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE
3231 38191 : || !integer_zerop (arg)
3232 290 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg2))
3233 290 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg3))
3234 290 : || integer_zerop (arg2)
3235 214 : || integer_zerop (arg3)
3236 38466 : || ((TREE_CODE (fntype) == METHOD_TYPE || closure)
3237 0 : && (idx == 0 || idx2 == 0 || idx3 == 0)))
3238 38150 : continue;
3239 186 : if (!integer_nonzerop (arg2)
3240 186 : && !tree_expr_nonzero_p (arg2))
3241 : {
3242 98 : if (TREE_CODE (arg2) != SSA_NAME || optimize < 2)
3243 56 : continue;
3244 98 : if (!ranger)
3245 14 : ranger = enable_ranger (cfun);
3246 :
3247 98 : int_range_max vr;
3248 196 : get_range_query (cfun)->range_of_expr (vr, arg2, stmt);
3249 98 : if (range_includes_zero_p (vr))
3250 56 : continue;
3251 98 : }
3252 130 : if (idx2 != idx3
3253 45 : && !integer_nonzerop (arg3)
3254 153 : && !tree_expr_nonzero_p (arg3))
3255 : {
3256 20 : if (TREE_CODE (arg3) != SSA_NAME || optimize < 2)
3257 0 : continue;
3258 20 : if (!ranger)
3259 0 : ranger = enable_ranger (cfun);
3260 :
3261 20 : int_range_max vr;
3262 40 : get_range_query (cfun)->range_of_expr (vr, arg3, stmt);
3263 20 : if (range_includes_zero_p (vr))
3264 0 : continue;
3265 20 : }
3266 130 : unsigned argno = idx + 1;
3267 130 : unsigned argno2 = idx2 + 1;
3268 130 : unsigned argno3 = idx3 + 1;
3269 130 : location_t loc = (EXPR_HAS_LOCATION (arg)
3270 0 : ? EXPR_LOCATION (arg)
3271 130 : : gimple_location (stmt));
3272 130 : auto_diagnostic_group d;
3273 :
3274 130 : if (idx2 != idx3)
3275 : {
3276 45 : if (!warning_at (loc, OPT_Wnonnull,
3277 : "argument %u null where non-null "
3278 : "expected because arguments %u and %u "
3279 : "are nonzero", argno, argno2, argno3))
3280 0 : continue;
3281 : }
3282 85 : else if (!warning_at (loc, OPT_Wnonnull,
3283 : "argument %u null where non-null "
3284 : "expected because argument %u is "
3285 : "nonzero", argno, argno2))
3286 0 : continue;
3287 :
3288 130 : tree fndecl = gimple_call_fndecl (stmt);
3289 130 : if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
3290 37 : inform (loc, "in a call to built-in function %qD",
3291 : fndecl);
3292 93 : else if (fndecl)
3293 93 : inform (DECL_SOURCE_LOCATION (fndecl),
3294 : "in a call to function %qD declared %qs",
3295 : fndecl, "nonnull_if_nonzero");
3296 130 : }
3297 : }
3298 : }
3299 : }
3300 113149 : if (ranger)
3301 14 : disable_ranger (cfun);
3302 113149 : return 0;
3303 : }
3304 :
3305 : } // anon namespace
3306 :
3307 : gimple_opt_pass *
3308 297180 : make_pass_post_ipa_warn (gcc::context *ctxt)
3309 : {
3310 297180 : return new pass_post_ipa_warn (ctxt);
3311 : }
|