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