Branch data Line data Source code
1 : : /* Header file for SSA dominator optimizations.
2 : : Copyright (C) 2013-2024 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
9 : : version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "function.h"
24 : : #include "basic-block.h"
25 : : #include "tree.h"
26 : : #include "gimple.h"
27 : : #include "tree-pass.h"
28 : : #include "tree-pretty-print.h"
29 : : #include "tree-ssa-scopedtables.h"
30 : : #include "tree-ssa-threadedge.h"
31 : : #include "stor-layout.h"
32 : : #include "fold-const.h"
33 : : #include "tree-eh.h"
34 : : #include "internal-fn.h"
35 : : #include "tree-dfa.h"
36 : : #include "options.h"
37 : :
38 : : static bool hashable_expr_equal_p (const struct hashable_expr *,
39 : : const struct hashable_expr *);
40 : :
41 : : /* Initialize local stacks for this optimizer and record equivalences
42 : : upon entry to BB. Equivalences can come from the edge traversed to
43 : : reach BB or they may come from PHI nodes at the start of BB. */
44 : :
45 : : /* Pop items off the unwinding stack, removing each from the hash table
46 : : until a marker is encountered. */
47 : :
48 : : void
49 : 57916154 : avail_exprs_stack::pop_to_marker ()
50 : : {
51 : : /* Remove all the expressions made available in this block. */
52 : 161185231 : while (m_stack.length () > 0)
53 : : {
54 : 161185231 : std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop ();
55 : 161185231 : expr_hash_elt **slot;
56 : :
57 : 161185231 : if (victim.first == NULL)
58 : : break;
59 : :
60 : : /* This must precede the actual removal from the hash table,
61 : : as ELEMENT and the table entry may share a call argument
62 : : vector which will be freed during removal. */
63 : 103269077 : if (dump_file && (dump_flags & TDF_DETAILS))
64 : : {
65 : 3220 : fprintf (dump_file, "<<<< ");
66 : 3220 : victim.first->print (dump_file);
67 : : }
68 : :
69 : 103269077 : slot = m_avail_exprs->find_slot (victim.first, NO_INSERT);
70 : 103269077 : gcc_assert (slot && *slot == victim.first);
71 : 103269077 : if (victim.second != NULL)
72 : : {
73 : 4073181 : delete *slot;
74 : 4073181 : *slot = victim.second;
75 : : }
76 : : else
77 : 99195896 : m_avail_exprs->clear_slot (slot);
78 : : }
79 : 57916154 : }
80 : :
81 : : /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
82 : : from the hash table. */
83 : :
84 : : void
85 : 161185231 : avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
86 : : class expr_hash_elt *elt2,
87 : : char type)
88 : : {
89 : 161185231 : if (elt1 && dump_file && (dump_flags & TDF_DETAILS))
90 : : {
91 : 3220 : fprintf (dump_file, "%c>>> ", type);
92 : 3220 : elt1->print (dump_file);
93 : : }
94 : :
95 : 161185231 : m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2));
96 : 161185231 : }
97 : :
98 : : /* Helper for walk_non_aliased_vuses. Determine if we arrived at
99 : : the desired memory state. */
100 : :
101 : : static void *
102 : 16215065 : vuse_eq (ao_ref *, tree vuse1, void *data)
103 : : {
104 : 16215065 : tree vuse2 = (tree) data;
105 : 16215065 : if (vuse1 == vuse2)
106 : 345107 : return data;
107 : :
108 : : return NULL;
109 : : }
110 : :
111 : : /* We looked for STMT in the hash table, but did not find it.
112 : :
113 : : If STMT is an assignment from a binary operator, we may know something
114 : : about the operands relationship to each other which would allow
115 : : us to derive a constant value for the RHS of STMT. */
116 : :
117 : : tree
118 : 41080988 : avail_exprs_stack::simplify_binary_operation (gimple *stmt,
119 : : class expr_hash_elt element)
120 : : {
121 : 41080988 : if (is_gimple_assign (stmt))
122 : : {
123 : 32199270 : struct hashable_expr *expr = element.expr ();
124 : 32199270 : if (expr->kind == EXPR_BINARY)
125 : : {
126 : 9078330 : enum tree_code code = expr->ops.binary.op;
127 : :
128 : 9078330 : switch (code)
129 : : {
130 : : /* For these cases, if we know some relationships
131 : : between the operands, then we can simplify. */
132 : 132642 : case MIN_EXPR:
133 : 132642 : case MAX_EXPR:
134 : 132642 : {
135 : : /* Build a simple equality expr and query the hash table
136 : : for it. */
137 : 132642 : struct hashable_expr expr;
138 : 132642 : expr.type = boolean_type_node;
139 : 132642 : expr.kind = EXPR_BINARY;
140 : 132642 : expr.ops.binary.op = LE_EXPR;
141 : 132642 : tree rhs1 = gimple_assign_rhs1 (stmt);
142 : 132642 : tree rhs2 = gimple_assign_rhs2 (stmt);
143 : 132642 : if (tree_swap_operands_p (rhs1, rhs2))
144 : 16933 : std::swap (rhs1, rhs2);
145 : 132642 : expr.ops.binary.opnd0 = rhs1;
146 : 132642 : expr.ops.binary.opnd1 = rhs2;
147 : 132642 : class expr_hash_elt element2 (&expr, NULL_TREE);
148 : 132642 : expr_hash_elt **slot
149 : 132642 : = m_avail_exprs->find_slot (&element2, NO_INSERT);
150 : :
151 : : /* If the query was successful and returned a nonzero
152 : : result, then we know the result of the MIN/MAX, even
153 : : though it is not a constant value. */
154 : 132642 : if (slot && *slot && integer_onep ((*slot)->lhs ()))
155 : 454 : return code == MIN_EXPR ? rhs1 : rhs2;
156 : :
157 : : /* Try again, this time with GE_EXPR. */
158 : 132234 : expr.ops.binary.op = GE_EXPR;
159 : 132234 : class expr_hash_elt element3 (&expr, NULL_TREE);
160 : 132234 : slot = m_avail_exprs->find_slot (&element3, NO_INSERT);
161 : :
162 : : /* If the query was successful and returned a nonzero
163 : : result, then we know the result of the MIN/MAX, even
164 : : though it is not a constant value. */
165 : 132234 : if (slot && *slot && integer_onep ((*slot)->lhs ()))
166 : 426 : return code == MIN_EXPR ? rhs2 : rhs1;
167 : :
168 : 131808 : break;
169 : 132642 : }
170 : :
171 : : /* For these cases, if we know the operands
172 : : are equal, then we know the result. */
173 : 1818344 : case BIT_IOR_EXPR:
174 : 1818344 : case BIT_AND_EXPR:
175 : 1818344 : case BIT_XOR_EXPR:
176 : 1818344 : case MINUS_EXPR:
177 : 1818344 : case TRUNC_DIV_EXPR:
178 : 1818344 : case CEIL_DIV_EXPR:
179 : 1818344 : case FLOOR_DIV_EXPR:
180 : 1818344 : case ROUND_DIV_EXPR:
181 : 1818344 : case EXACT_DIV_EXPR:
182 : 1818344 : case TRUNC_MOD_EXPR:
183 : 1818344 : case CEIL_MOD_EXPR:
184 : 1818344 : case FLOOR_MOD_EXPR:
185 : 1818344 : case ROUND_MOD_EXPR:
186 : 1818344 : {
187 : : /* Build a simple equality expr and query the hash table
188 : : for it. */
189 : 1818344 : struct hashable_expr expr;
190 : 1818344 : expr.type = boolean_type_node;
191 : 1818344 : expr.kind = EXPR_BINARY;
192 : 1818344 : expr.ops.binary.op = EQ_EXPR;
193 : 1818344 : tree rhs1 = gimple_assign_rhs1 (stmt);
194 : 1818344 : tree rhs2 = gimple_assign_rhs2 (stmt);
195 : 1818344 : if (tree_swap_operands_p (rhs1, rhs2))
196 : 470596 : std::swap (rhs1, rhs2);
197 : 1818344 : expr.ops.binary.opnd0 = rhs1;
198 : 1818344 : expr.ops.binary.opnd1 = rhs2;
199 : 1818344 : class expr_hash_elt element2 (&expr, NULL_TREE);
200 : 1818344 : expr_hash_elt **slot
201 : 1818344 : = m_avail_exprs->find_slot (&element2, NO_INSERT);
202 : 1818344 : tree result_type = TREE_TYPE (gimple_assign_lhs (stmt));
203 : :
204 : : /* If the query was successful and returned a nonzero
205 : : result, then we know that the operands of the binary
206 : : expression are the same. In many cases this allows
207 : : us to compute a constant result of the expression
208 : : at compile time, even if we do not know the exact
209 : : values of the operands. */
210 : 1818344 : if (slot && *slot && integer_onep ((*slot)->lhs ()))
211 : : {
212 : 129 : switch (code)
213 : : {
214 : 1 : case BIT_IOR_EXPR:
215 : 1 : case BIT_AND_EXPR:
216 : 1 : return gimple_assign_rhs1 (stmt);
217 : :
218 : 112 : case MINUS_EXPR:
219 : : /* This is unsafe for certain floats even in non-IEEE
220 : : formats. In IEEE, it is unsafe because it does
221 : : wrong for NaNs. */
222 : 82 : if (FLOAT_TYPE_P (result_type)
223 : 112 : && HONOR_NANS (result_type))
224 : : break;
225 : : /* FALLTHRU */
226 : 97 : case BIT_XOR_EXPR:
227 : 97 : case TRUNC_MOD_EXPR:
228 : 97 : case CEIL_MOD_EXPR:
229 : 97 : case FLOOR_MOD_EXPR:
230 : 97 : case ROUND_MOD_EXPR:
231 : 97 : return build_zero_cst (result_type);
232 : :
233 : 1 : case TRUNC_DIV_EXPR:
234 : 1 : case CEIL_DIV_EXPR:
235 : 1 : case FLOOR_DIV_EXPR:
236 : 1 : case ROUND_DIV_EXPR:
237 : 1 : case EXACT_DIV_EXPR:
238 : : /* Avoid _Fract types where we can't build 1. */
239 : 1 : if (ALL_FRACT_MODE_P (TYPE_MODE (result_type)))
240 : : break;
241 : 1 : return build_one_cst (result_type);
242 : :
243 : 0 : default:
244 : 0 : gcc_unreachable ();
245 : : }
246 : : }
247 : 1818245 : break;
248 : 1818344 : }
249 : :
250 : : default:
251 : : break;
252 : : }
253 : : }
254 : : }
255 : : return NULL_TREE;
256 : : }
257 : :
258 : : /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table.
259 : : If found, return its LHS. Otherwise insert STMT in the table and
260 : : return NULL_TREE.
261 : :
262 : : Also, when an expression is first inserted in the table, it is also
263 : : is also added to AVAIL_EXPRS_STACK, so that it can be removed when
264 : : we finish processing this block and its children. */
265 : :
266 : : tree
267 : 108515148 : avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p,
268 : : expr_hash_elt **elt)
269 : : {
270 : 108515148 : expr_hash_elt **slot;
271 : 108515148 : tree lhs;
272 : :
273 : : /* Get LHS of phi, assignment, or call; else NULL_TREE. */
274 : 108515148 : if (gimple_code (stmt) == GIMPLE_PHI)
275 : 7866238 : lhs = gimple_phi_result (stmt);
276 : : else
277 : 100648910 : lhs = gimple_get_lhs (stmt);
278 : :
279 : 108515148 : class expr_hash_elt element (stmt, lhs);
280 : :
281 : 108515148 : if (dump_file && (dump_flags & TDF_DETAILS))
282 : : {
283 : 2906 : fprintf (dump_file, "LKUP ");
284 : 2906 : element.print (dump_file);
285 : : }
286 : :
287 : : /* Don't bother remembering constant assignments and copy operations.
288 : : Constants and copy operations are handled by the constant/copy propagator
289 : : in optimize_stmt. */
290 : 108515148 : if (element.expr()->kind == EXPR_SINGLE
291 : 108515148 : && (TREE_CODE (element.expr()->ops.single.rhs) == SSA_NAME
292 : 49698057 : || is_gimple_min_invariant (element.expr()->ops.single.rhs)))
293 : 11779858 : return NULL_TREE;
294 : :
295 : : /* Finally try to find the expression in the main expression hash table. */
296 : 148036030 : slot = m_avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
297 : 96735290 : if (slot == NULL)
298 : : {
299 : : return NULL_TREE;
300 : : }
301 : 49589565 : else if (*slot == NULL)
302 : : {
303 : : /* We have, in effect, allocated *SLOT for ELEMENT at this point.
304 : : We must initialize *SLOT to a real entry, even if we found a
305 : : way to prove ELEMENT was a constant after not finding ELEMENT
306 : : in the hash table.
307 : :
308 : : An uninitialized or empty slot is an indication no prior objects
309 : : entered into the hash table had a hash collection with ELEMENT.
310 : :
311 : : If we fail to do so and had such entries in the table, they
312 : : would become unreachable. */
313 : 41080988 : class expr_hash_elt *element2 = new expr_hash_elt (element);
314 : 41080988 : *slot = element2;
315 : :
316 : : /* If we did not find the expression in the hash table, we may still
317 : : be able to produce a result for some expressions. */
318 : 41080988 : tree retval = avail_exprs_stack::simplify_binary_operation (stmt,
319 : : element);
320 : :
321 : 41080988 : record_expr (element2, NULL, '2');
322 : 41080988 : return retval;
323 : : }
324 : :
325 : : /* If we found a redundant memory operation do an alias walk to
326 : : check if we can re-use it. */
327 : 16822375 : if (gimple_vuse (stmt) != (*slot)->vop ())
328 : : {
329 : 7256729 : tree vuse1 = (*slot)->vop ();
330 : 7256729 : tree vuse2 = gimple_vuse (stmt);
331 : : /* If we have a load of a register and a candidate in the
332 : : hash with vuse1 then try to reach its stmt by walking
333 : : up the virtual use-def chain using walk_non_aliased_vuses.
334 : : But don't do this when removing expressions from the hash. */
335 : 7256729 : ao_ref ref;
336 : 7256729 : unsigned limit = param_sccvn_max_alias_queries_per_access;
337 : 13631025 : if (!(vuse1 && vuse2
338 : 7256729 : && gimple_assign_single_p (stmt)
339 : 7130852 : && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
340 : 6374296 : && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)),
341 : 6374296 : ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true)
342 : 6374296 : && walk_non_aliased_vuses (&ref, vuse2, true, vuse_eq, NULL, NULL,
343 : : limit, vuse1) != NULL))
344 : : {
345 : 6911622 : if (insert)
346 : : {
347 : 4073181 : class expr_hash_elt *element2 = new expr_hash_elt (element);
348 : :
349 : : /* Insert the expr into the hash by replacing the current
350 : : entry and recording the value to restore in the
351 : : avail_exprs_stack. */
352 : 4073181 : record_expr (element2, *slot, '2');
353 : 4073181 : *slot = element2;
354 : : }
355 : 6911622 : return NULL_TREE;
356 : : }
357 : : }
358 : :
359 : : /* Extract the LHS of the assignment so that it can be used as the current
360 : : definition of another variable. */
361 : 1596955 : lhs = (*slot)->lhs ();
362 : 1596955 : if (elt)
363 : 643598 : *elt = *slot;
364 : :
365 : : /* Valueize the result. */
366 : 1596955 : if (TREE_CODE (lhs) == SSA_NAME)
367 : : {
368 : 1408980 : tree tem = SSA_NAME_VALUE (lhs);
369 : 1187126 : if (tem)
370 : 1596955 : lhs = tem;
371 : : }
372 : :
373 : 1596955 : if (dump_file && (dump_flags & TDF_DETAILS))
374 : : {
375 : 179 : fprintf (dump_file, "FIND: ");
376 : 179 : print_generic_expr (dump_file, lhs);
377 : 179 : fprintf (dump_file, "\n");
378 : : }
379 : :
380 : : return lhs;
381 : 108515148 : }
382 : :
383 : : /* Enter condition equivalence P into the hash table.
384 : :
385 : : This indicates that a conditional expression has a known
386 : : boolean value. */
387 : :
388 : : void
389 : 58570695 : avail_exprs_stack::record_cond (cond_equivalence *p)
390 : : {
391 : 58570695 : class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value);
392 : 58570695 : expr_hash_elt **slot;
393 : :
394 : 58570695 : slot = m_avail_exprs->find_slot_with_hash (element, element->hash (), INSERT);
395 : 58570695 : if (*slot == NULL)
396 : : {
397 : 58114908 : *slot = element;
398 : 58114908 : record_expr (element, NULL, '1');
399 : : }
400 : : else
401 : 455787 : delete element;
402 : 58570695 : }
403 : :
404 : : /* Generate a hash value for a pair of expressions. This can be used
405 : : iteratively by passing a previous result in HSTATE.
406 : :
407 : : The same hash value is always returned for a given pair of expressions,
408 : : regardless of the order in which they are presented. This is useful in
409 : : hashing the operands of commutative functions. */
410 : :
411 : : namespace inchash
412 : : {
413 : :
414 : : static void
415 : 59026817 : add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
416 : : {
417 : 59026817 : hash one, two;
418 : :
419 : 59026817 : inchash::add_expr (t1, one);
420 : 59026817 : inchash::add_expr (t2, two);
421 : 59026817 : hstate.add_commutative (one, two);
422 : 59026817 : }
423 : :
424 : : /* Compute a hash value for a hashable_expr value EXPR and a
425 : : previously accumulated hash value VAL. If two hashable_expr
426 : : values compare equal with hashable_expr_equal_p, they must
427 : : hash to the same value, given an identical value of VAL.
428 : : The logic is intended to follow inchash::add_expr in tree.cc. */
429 : :
430 : : static void
431 : 133348221 : add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
432 : : {
433 : 133348221 : switch (expr->kind)
434 : : {
435 : 19654101 : case EXPR_SINGLE:
436 : 19654101 : inchash::add_expr (expr->ops.single.rhs, hstate);
437 : 19654101 : break;
438 : :
439 : 7296006 : case EXPR_UNARY:
440 : 7296006 : hstate.add_object (expr->ops.unary.op);
441 : :
442 : : /* Make sure to include signedness in the hash computation.
443 : : Don't hash the type, that can lead to having nodes which
444 : : compare equal according to operand_equal_p, but which
445 : : have different hash codes. */
446 : 7296006 : if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
447 : 829569 : || expr->ops.unary.op == NON_LVALUE_EXPR)
448 : 6466437 : hstate.add_int (TYPE_UNSIGNED (expr->type));
449 : :
450 : 7296006 : inchash::add_expr (expr->ops.unary.opnd, hstate);
451 : 7296006 : break;
452 : :
453 : 95674291 : case EXPR_BINARY:
454 : 95674291 : hstate.add_object (expr->ops.binary.op);
455 : 95674291 : if (commutative_tree_code (expr->ops.binary.op))
456 : 59026533 : inchash::add_expr_commutative (expr->ops.binary.opnd0,
457 : 59026533 : expr->ops.binary.opnd1, hstate);
458 : : else
459 : : {
460 : 36647758 : inchash::add_expr (expr->ops.binary.opnd0, hstate);
461 : 36647758 : inchash::add_expr (expr->ops.binary.opnd1, hstate);
462 : : }
463 : : break;
464 : :
465 : 153035 : case EXPR_TERNARY:
466 : 153035 : hstate.add_object (expr->ops.ternary.op);
467 : 153035 : if (commutative_ternary_tree_code (expr->ops.ternary.op))
468 : 284 : inchash::add_expr_commutative (expr->ops.ternary.opnd0,
469 : 284 : expr->ops.ternary.opnd1, hstate);
470 : : else
471 : : {
472 : 152751 : inchash::add_expr (expr->ops.ternary.opnd0, hstate);
473 : 152751 : inchash::add_expr (expr->ops.ternary.opnd1, hstate);
474 : : }
475 : 153035 : inchash::add_expr (expr->ops.ternary.opnd2, hstate);
476 : 153035 : break;
477 : :
478 : 2704550 : case EXPR_CALL:
479 : 2704550 : {
480 : 2704550 : size_t i;
481 : 2704550 : enum tree_code code = CALL_EXPR;
482 : 2704550 : gcall *fn_from;
483 : :
484 : 2704550 : hstate.add_object (code);
485 : 2704550 : fn_from = expr->ops.call.fn_from;
486 : 2704550 : if (gimple_call_internal_p (fn_from))
487 : 195825 : hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
488 : : else
489 : 2508725 : inchash::add_expr (gimple_call_fn (fn_from), hstate);
490 : 7988748 : for (i = 0; i < expr->ops.call.nargs; i++)
491 : 5284198 : inchash::add_expr (expr->ops.call.args[i], hstate);
492 : : }
493 : 2704550 : break;
494 : :
495 : : case EXPR_PHI:
496 : : {
497 : : size_t i;
498 : :
499 : 27546012 : for (i = 0; i < expr->ops.phi.nargs; i++)
500 : 19679774 : inchash::add_expr (expr->ops.phi.args[i], hstate);
501 : : }
502 : : break;
503 : :
504 : 0 : default:
505 : 0 : gcc_unreachable ();
506 : : }
507 : 133348221 : }
508 : :
509 : : }
510 : :
511 : : /* Hashing and equality functions. We compute a value number for expressions
512 : : using the code of the expression and the SSA numbers of its operands. */
513 : :
514 : : static hashval_t
515 : 169169063 : avail_expr_hash (class expr_hash_elt *p)
516 : : {
517 : 169169063 : const struct hashable_expr *expr = p->expr ();
518 : 169169063 : inchash::hash hstate;
519 : :
520 : 169169063 : if (expr->kind == EXPR_SINGLE)
521 : : {
522 : : /* T could potentially be a switch index or a goto dest. */
523 : 55474943 : tree t = expr->ops.single.rhs;
524 : 55474943 : if (TREE_CODE (t) == MEM_REF || handled_component_p (t))
525 : : {
526 : : /* Make equivalent statements of both these kinds hash together.
527 : : Dealing with both MEM_REF and ARRAY_REF allows us not to care
528 : : about equivalence with other statements not considered here. */
529 : 36964644 : bool reverse;
530 : 36964644 : poly_int64 offset, size, max_size;
531 : 36964644 : tree base = get_ref_base_and_extent (t, &offset, &size, &max_size,
532 : : &reverse);
533 : : /* Strictly, we could try to normalize variable-sized accesses too,
534 : : but here we just deal with the common case. */
535 : 36964644 : if (known_size_p (max_size)
536 : 36964644 : && known_eq (size, max_size))
537 : : {
538 : 35820842 : enum tree_code code = MEM_REF;
539 : 35820842 : hstate.add_object (code);
540 : 35820842 : inchash::add_expr (base, hstate,
541 : 35820842 : TREE_CODE (base) == MEM_REF
542 : : ? OEP_ADDRESS_OF : 0);
543 : 35820842 : hstate.add_object (offset);
544 : 35820842 : hstate.add_object (size);
545 : 35820842 : return hstate.end ();
546 : : }
547 : : }
548 : : }
549 : :
550 : 133348221 : inchash::add_hashable_expr (expr, hstate);
551 : :
552 : 133348221 : return hstate.end ();
553 : : }
554 : :
555 : : /* Compares trees T0 and T1 to see if they are MEM_REF or ARRAY_REFs equivalent
556 : : to each other. (That is, they return the value of the same bit of memory.)
557 : :
558 : : Return TRUE if the two are so equivalent; FALSE if not (which could still
559 : : mean the two are equivalent by other means). */
560 : :
561 : : static bool
562 : 7883794 : equal_mem_array_ref_p (tree t0, tree t1)
563 : : {
564 : 7883794 : if (TREE_CODE (t0) != MEM_REF && ! handled_component_p (t0))
565 : : return false;
566 : 8008454 : if (TREE_CODE (t1) != MEM_REF && ! handled_component_p (t1))
567 : : return false;
568 : :
569 : 6733463 : if (!types_compatible_p (TREE_TYPE (t0), TREE_TYPE (t1)))
570 : : return false;
571 : 6730430 : bool rev0;
572 : 6730430 : poly_int64 off0, sz0, max0;
573 : 6730430 : tree base0 = get_ref_base_and_extent (t0, &off0, &sz0, &max0, &rev0);
574 : 6730430 : if (!known_size_p (max0)
575 : 6730430 : || maybe_ne (sz0, max0))
576 : : return false;
577 : :
578 : 6608803 : bool rev1;
579 : 6608803 : poly_int64 off1, sz1, max1;
580 : 6608803 : tree base1 = get_ref_base_and_extent (t1, &off1, &sz1, &max1, &rev1);
581 : 6608803 : if (!known_size_p (max1)
582 : 6608803 : || maybe_ne (sz1, max1))
583 : : return false;
584 : :
585 : 6608803 : if (rev0 != rev1 || maybe_ne (sz0, sz1) || maybe_ne (off0, off1))
586 : : return false;
587 : :
588 : 6608803 : return operand_equal_p (base0, base1,
589 : 6608803 : (TREE_CODE (base0) == MEM_REF
590 : 6608803 : || TREE_CODE (base0) == TARGET_MEM_REF)
591 : 2275212 : && (TREE_CODE (base1) == MEM_REF
592 : 2275212 : || TREE_CODE (base1) == TARGET_MEM_REF)
593 : 6608803 : ? OEP_ADDRESS_OF : 0);
594 : : }
595 : :
596 : : /* Compare two hashable_expr structures for equivalence. They are
597 : : considered equivalent when the expressions they denote must
598 : : necessarily be equal. The logic is intended to follow that of
599 : : operand_equal_p in fold-const.cc */
600 : :
601 : : static bool
602 : 9201620 : hashable_expr_equal_p (const struct hashable_expr *expr0,
603 : : const struct hashable_expr *expr1)
604 : : {
605 : 9201620 : tree type0 = expr0->type;
606 : 9201620 : tree type1 = expr1->type;
607 : :
608 : : /* If either type is NULL, there is nothing to check. */
609 : 9201620 : if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
610 : : return false;
611 : :
612 : : /* If both types don't have the same signedness, precision, and mode,
613 : : then we can't consider them equal. */
614 : 9201620 : if (type0 != type1
615 : 9201620 : && (TREE_CODE (type0) == ERROR_MARK
616 : 1148690 : || TREE_CODE (type1) == ERROR_MARK
617 : 1148690 : || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
618 : 1124317 : || element_precision (type0) != element_precision (type1)
619 : 1033328 : || TYPE_MODE (type0) != TYPE_MODE (type1)))
620 : 184835 : return false;
621 : :
622 : 9016785 : if (expr0->kind != expr1->kind)
623 : : return false;
624 : :
625 : 9016785 : switch (expr0->kind)
626 : : {
627 : 7883794 : case EXPR_SINGLE:
628 : 7883794 : return equal_mem_array_ref_p (expr0->ops.single.rhs,
629 : 7883794 : expr1->ops.single.rhs)
630 : 9159115 : || operand_equal_p (expr0->ops.single.rhs,
631 : 1275321 : expr1->ops.single.rhs, 0);
632 : 133707 : case EXPR_UNARY:
633 : 133707 : if (expr0->ops.unary.op != expr1->ops.unary.op)
634 : : return false;
635 : :
636 : 12961 : if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
637 : 12961 : || expr0->ops.unary.op == NON_LVALUE_EXPR)
638 : 133707 : && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
639 : : return false;
640 : :
641 : 133707 : return operand_equal_p (expr0->ops.unary.opnd,
642 : 133707 : expr1->ops.unary.opnd, 0);
643 : :
644 : 851490 : case EXPR_BINARY:
645 : 851490 : if (expr0->ops.binary.op != expr1->ops.binary.op)
646 : : return false;
647 : :
648 : 851490 : if (operand_equal_p (expr0->ops.binary.opnd0,
649 : 851490 : expr1->ops.binary.opnd0, 0)
650 : 1690851 : && operand_equal_p (expr0->ops.binary.opnd1,
651 : 839361 : expr1->ops.binary.opnd1, 0))
652 : : return true;
653 : :
654 : : /* For commutative ops, allow the other order. */
655 : 14757 : return (commutative_tree_code (expr0->ops.binary.op)
656 : 12826 : && operand_equal_p (expr0->ops.binary.opnd0,
657 : 12826 : expr1->ops.binary.opnd1, 0)
658 : 20021 : && operand_equal_p (expr0->ops.binary.opnd1,
659 : 5264 : expr1->ops.binary.opnd0, 0));
660 : :
661 : 233 : case EXPR_TERNARY:
662 : 233 : if (expr0->ops.ternary.op != expr1->ops.ternary.op
663 : 466 : || !operand_equal_p (expr0->ops.ternary.opnd2,
664 : 233 : expr1->ops.ternary.opnd2, 0))
665 : 0 : return false;
666 : :
667 : : /* BIT_INSERT_EXPR has an implict operand as the type precision
668 : : of op1. Need to check to make sure they are the same. */
669 : 233 : if (expr0->ops.ternary.op == BIT_INSERT_EXPR
670 : 4 : && TREE_CODE (expr0->ops.ternary.opnd1) == INTEGER_CST
671 : 4 : && TREE_CODE (expr1->ops.ternary.opnd1) == INTEGER_CST
672 : 237 : && TYPE_PRECISION (TREE_TYPE (expr0->ops.ternary.opnd1))
673 : 4 : != TYPE_PRECISION (TREE_TYPE (expr1->ops.ternary.opnd1)))
674 : : return false;
675 : :
676 : 233 : if (operand_equal_p (expr0->ops.ternary.opnd0,
677 : 233 : expr1->ops.ternary.opnd0, 0)
678 : 466 : && operand_equal_p (expr0->ops.ternary.opnd1,
679 : 233 : expr1->ops.ternary.opnd1, 0))
680 : : return true;
681 : :
682 : : /* For commutative ops, allow the other order. */
683 : 0 : return (commutative_ternary_tree_code (expr0->ops.ternary.op)
684 : 0 : && operand_equal_p (expr0->ops.ternary.opnd0,
685 : 0 : expr1->ops.ternary.opnd1, 0)
686 : 0 : && operand_equal_p (expr0->ops.ternary.opnd1,
687 : 0 : expr1->ops.ternary.opnd0, 0));
688 : :
689 : 128475 : case EXPR_CALL:
690 : 128475 : {
691 : 128475 : size_t i;
692 : :
693 : : /* If the calls are to different functions, then they
694 : : clearly cannot be equal. */
695 : 128475 : if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
696 : 128475 : expr1->ops.call.fn_from))
697 : : return false;
698 : :
699 : 127853 : if (! expr0->ops.call.pure)
700 : : return false;
701 : :
702 : 127853 : if (expr0->ops.call.nargs != expr1->ops.call.nargs)
703 : : return false;
704 : :
705 : 382841 : for (i = 0; i < expr0->ops.call.nargs; i++)
706 : 255174 : if (! operand_equal_p (expr0->ops.call.args[i],
707 : 255174 : expr1->ops.call.args[i], 0))
708 : : return false;
709 : :
710 : 127667 : if (stmt_could_throw_p (cfun, expr0->ops.call.fn_from))
711 : : {
712 : 34 : int lp0 = lookup_stmt_eh_lp (expr0->ops.call.fn_from);
713 : 34 : int lp1 = lookup_stmt_eh_lp (expr1->ops.call.fn_from);
714 : 34 : if ((lp0 > 0 || lp1 > 0) && lp0 != lp1)
715 : : return false;
716 : : }
717 : :
718 : : return true;
719 : : }
720 : :
721 : 19086 : case EXPR_PHI:
722 : 19086 : {
723 : 19086 : size_t i;
724 : :
725 : 19086 : if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
726 : : return false;
727 : :
728 : 45632 : for (i = 0; i < expr0->ops.phi.nargs; i++)
729 : 26636 : if (! operand_equal_p (expr0->ops.phi.args[i],
730 : 26636 : expr1->ops.phi.args[i], 0))
731 : : return false;
732 : :
733 : : return true;
734 : : }
735 : :
736 : 0 : default:
737 : 0 : gcc_unreachable ();
738 : : }
739 : : }
740 : :
741 : : /* Given a statement STMT, construct a hash table element. */
742 : :
743 : 108515148 : expr_hash_elt::expr_hash_elt (gimple *stmt, tree orig_lhs)
744 : : {
745 : 108515148 : enum gimple_code code = gimple_code (stmt);
746 : 108515148 : struct hashable_expr *expr = this->expr ();
747 : :
748 : 108515148 : if (code == GIMPLE_ASSIGN)
749 : : {
750 : 80195354 : enum tree_code subcode = gimple_assign_rhs_code (stmt);
751 : :
752 : 80195354 : switch (get_gimple_rhs_class (subcode))
753 : : {
754 : 55417477 : case GIMPLE_SINGLE_RHS:
755 : 55417477 : expr->kind = EXPR_SINGLE;
756 : 55417477 : expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
757 : 55417477 : expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
758 : 55417477 : break;
759 : 7199393 : case GIMPLE_UNARY_RHS:
760 : 7199393 : expr->kind = EXPR_UNARY;
761 : 7199393 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
762 : 7199393 : if (CONVERT_EXPR_CODE_P (subcode))
763 : 6466437 : subcode = NOP_EXPR;
764 : 7199393 : expr->ops.unary.op = subcode;
765 : 7199393 : expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
766 : 7199393 : break;
767 : 17425449 : case GIMPLE_BINARY_RHS:
768 : 17425449 : expr->kind = EXPR_BINARY;
769 : 17425449 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
770 : 17425449 : expr->ops.binary.op = subcode;
771 : 17425449 : expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
772 : 17425449 : expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
773 : 17425449 : break;
774 : 153035 : case GIMPLE_TERNARY_RHS:
775 : 153035 : expr->kind = EXPR_TERNARY;
776 : 153035 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
777 : 153035 : expr->ops.ternary.op = subcode;
778 : 153035 : expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
779 : 153035 : expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
780 : 153035 : expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
781 : 153035 : break;
782 : 0 : default:
783 : 0 : gcc_unreachable ();
784 : : }
785 : : }
786 : : else if (code == GIMPLE_COND)
787 : : {
788 : 17691540 : expr->type = boolean_type_node;
789 : 17691540 : expr->kind = EXPR_BINARY;
790 : 17691540 : expr->ops.binary.op = gimple_cond_code (stmt);
791 : 17691540 : expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
792 : 17691540 : expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
793 : : }
794 : 2704550 : else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
795 : : {
796 : 2704550 : size_t nargs = gimple_call_num_args (call_stmt);
797 : 2704550 : size_t i;
798 : :
799 : 2704550 : gcc_assert (gimple_call_lhs (call_stmt));
800 : :
801 : 2704550 : expr->type = TREE_TYPE (gimple_call_lhs (call_stmt));
802 : 2704550 : expr->kind = EXPR_CALL;
803 : 2704550 : expr->ops.call.fn_from = call_stmt;
804 : :
805 : 2704550 : if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE))
806 : 1419202 : expr->ops.call.pure = true;
807 : : else
808 : 1285348 : expr->ops.call.pure = false;
809 : :
810 : 2704550 : expr->ops.call.nargs = nargs;
811 : 2704550 : expr->ops.call.args = XCNEWVEC (tree, nargs);
812 : 7988748 : for (i = 0; i < nargs; i++)
813 : 5284198 : expr->ops.call.args[i] = gimple_call_arg (call_stmt, i);
814 : : }
815 : 57244 : else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
816 : : {
817 : 57244 : expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt));
818 : 57244 : expr->kind = EXPR_SINGLE;
819 : 57244 : expr->ops.single.rhs = gimple_switch_index (swtch_stmt);
820 : : }
821 : : else if (code == GIMPLE_GOTO)
822 : : {
823 : 222 : expr->type = TREE_TYPE (gimple_goto_dest (stmt));
824 : 222 : expr->kind = EXPR_SINGLE;
825 : 222 : expr->ops.single.rhs = gimple_goto_dest (stmt);
826 : : }
827 : : else if (code == GIMPLE_PHI)
828 : : {
829 : 7866238 : size_t nargs = gimple_phi_num_args (stmt);
830 : 7866238 : size_t i;
831 : :
832 : 7866238 : expr->type = TREE_TYPE (gimple_phi_result (stmt));
833 : 7866238 : expr->kind = EXPR_PHI;
834 : 7866238 : expr->ops.phi.nargs = nargs;
835 : 7866238 : expr->ops.phi.args = XCNEWVEC (tree, nargs);
836 : 27546012 : for (i = 0; i < nargs; i++)
837 : 19679774 : expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
838 : : }
839 : : else
840 : 0 : gcc_unreachable ();
841 : :
842 : 108515148 : m_lhs = orig_lhs;
843 : 108515148 : m_vop = gimple_vuse (stmt);
844 : 108515148 : m_hash = avail_expr_hash (this);
845 : 108515148 : m_stamp = this;
846 : 108515148 : }
847 : :
848 : : /* Given a hashable_expr expression ORIG and an ORIG_LHS,
849 : : construct a hash table element. */
850 : :
851 : 60653915 : expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs)
852 : : {
853 : 60653915 : m_expr = *orig;
854 : 60653915 : m_lhs = orig_lhs;
855 : 60653915 : m_vop = NULL_TREE;
856 : 60653915 : m_hash = avail_expr_hash (this);
857 : 60653915 : m_stamp = this;
858 : 60653915 : }
859 : :
860 : : /* Copy constructor for a hash table element. */
861 : :
862 : 86235157 : expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt)
863 : : {
864 : 86235157 : m_expr = old_elt.m_expr;
865 : 86235157 : m_lhs = old_elt.m_lhs;
866 : 86235157 : m_vop = old_elt.m_vop;
867 : 86235157 : m_hash = old_elt.m_hash;
868 : 86235157 : m_stamp = this;
869 : :
870 : : /* Now deep copy the malloc'd space for CALL and PHI args. */
871 : 86235157 : if (old_elt.m_expr.kind == EXPR_CALL)
872 : : {
873 : 2181052 : size_t nargs = old_elt.m_expr.ops.call.nargs;
874 : 2181052 : size_t i;
875 : :
876 : 2181052 : m_expr.ops.call.args = XCNEWVEC (tree, nargs);
877 : 6875315 : for (i = 0; i < nargs; i++)
878 : 4694263 : m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i];
879 : : }
880 : 84054105 : else if (old_elt.m_expr.kind == EXPR_PHI)
881 : : {
882 : 15683612 : size_t nargs = old_elt.m_expr.ops.phi.nargs;
883 : 15683612 : size_t i;
884 : :
885 : 15683612 : m_expr.ops.phi.args = XCNEWVEC (tree, nargs);
886 : 54954020 : for (i = 0; i < nargs; i++)
887 : 39270408 : m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i];
888 : : }
889 : 86235157 : }
890 : :
891 : : /* Calls and PHIs have a variable number of arguments that are allocated
892 : : on the heap. Thus we have to have a special dtor to release them. */
893 : :
894 : 255404220 : expr_hash_elt::~expr_hash_elt ()
895 : : {
896 : 255404220 : if (m_expr.kind == EXPR_CALL)
897 : 4885602 : free (m_expr.ops.call.args);
898 : 250518618 : else if (m_expr.kind == EXPR_PHI)
899 : 23549850 : free (m_expr.ops.phi.args);
900 : 255404220 : }
901 : :
902 : : /* Print a diagnostic dump of an expression hash table entry. */
903 : :
904 : : void
905 : 9346 : expr_hash_elt::print (FILE *stream)
906 : : {
907 : 9346 : fprintf (stream, "STMT ");
908 : :
909 : 9346 : if (m_lhs)
910 : : {
911 : 8735 : print_generic_expr (stream, m_lhs);
912 : 8735 : fprintf (stream, " = ");
913 : : }
914 : :
915 : 9346 : switch (m_expr.kind)
916 : : {
917 : 2523 : case EXPR_SINGLE:
918 : 2523 : print_generic_expr (stream, m_expr.ops.single.rhs);
919 : 2523 : break;
920 : :
921 : 276 : case EXPR_UNARY:
922 : 276 : fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op));
923 : 276 : print_generic_expr (stream, m_expr.ops.unary.opnd);
924 : 276 : break;
925 : :
926 : 5823 : case EXPR_BINARY:
927 : 5823 : print_generic_expr (stream, m_expr.ops.binary.opnd0);
928 : 5823 : fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op));
929 : 5823 : print_generic_expr (stream, m_expr.ops.binary.opnd1);
930 : 5823 : break;
931 : :
932 : 0 : case EXPR_TERNARY:
933 : 0 : fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op));
934 : 0 : print_generic_expr (stream, m_expr.ops.ternary.opnd0);
935 : 0 : fputs (", ", stream);
936 : 0 : print_generic_expr (stream, m_expr.ops.ternary.opnd1);
937 : 0 : fputs (", ", stream);
938 : 0 : print_generic_expr (stream, m_expr.ops.ternary.opnd2);
939 : 0 : fputs (">", stream);
940 : 0 : break;
941 : :
942 : 12 : case EXPR_CALL:
943 : 12 : {
944 : 12 : size_t i;
945 : 12 : size_t nargs = m_expr.ops.call.nargs;
946 : 12 : gcall *fn_from;
947 : :
948 : 12 : fn_from = m_expr.ops.call.fn_from;
949 : 12 : if (gimple_call_internal_p (fn_from))
950 : 0 : fprintf (stream, ".%s",
951 : : internal_fn_name (gimple_call_internal_fn (fn_from)));
952 : : else
953 : 12 : print_generic_expr (stream, gimple_call_fn (fn_from));
954 : 12 : fprintf (stream, " (");
955 : 42 : for (i = 0; i < nargs; i++)
956 : : {
957 : 18 : print_generic_expr (stream, m_expr.ops.call.args[i]);
958 : 18 : if (i + 1 < nargs)
959 : 6 : fprintf (stream, ", ");
960 : : }
961 : 12 : fprintf (stream, ")");
962 : : }
963 : 12 : break;
964 : :
965 : 712 : case EXPR_PHI:
966 : 712 : {
967 : 712 : size_t i;
968 : 712 : size_t nargs = m_expr.ops.phi.nargs;
969 : :
970 : 712 : fprintf (stream, "PHI <");
971 : 3010 : for (i = 0; i < nargs; i++)
972 : : {
973 : 1586 : print_generic_expr (stream, m_expr.ops.phi.args[i]);
974 : 1586 : if (i + 1 < nargs)
975 : 874 : fprintf (stream, ", ");
976 : : }
977 : 712 : fprintf (stream, ">");
978 : : }
979 : 712 : break;
980 : : }
981 : :
982 : 9346 : if (m_vop)
983 : : {
984 : 2322 : fprintf (stream, " with ");
985 : 2322 : print_generic_expr (stream, m_vop);
986 : : }
987 : :
988 : 9346 : fprintf (stream, "\n");
989 : 9346 : }
990 : :
991 : : /* Pop entries off the stack until we hit the NULL marker.
992 : : For each entry popped, use the SRC/DEST pair to restore
993 : : SRC to its prior value. */
994 : :
995 : : void
996 : 48513259 : const_and_copies::pop_to_marker (void)
997 : : {
998 : 82785469 : while (m_stack.length () > 0)
999 : : {
1000 : 82785469 : tree prev_value, dest;
1001 : :
1002 : 82785469 : dest = m_stack.pop ();
1003 : :
1004 : : /* A NULL value indicates we should stop unwinding, otherwise
1005 : : pop off the next entry as they're recorded in pairs. */
1006 : 82785469 : if (dest == NULL)
1007 : : break;
1008 : :
1009 : 34272210 : if (dump_file && (dump_flags & TDF_DETAILS))
1010 : : {
1011 : 1255 : fprintf (dump_file, "<<<< COPY ");
1012 : 1255 : print_generic_expr (dump_file, dest);
1013 : 1255 : fprintf (dump_file, " = ");
1014 : 1255 : print_generic_expr (dump_file, SSA_NAME_VALUE (dest));
1015 : 1255 : fprintf (dump_file, "\n");
1016 : : }
1017 : :
1018 : 34272210 : prev_value = m_stack.pop ();
1019 : 34272210 : set_ssa_name_value (dest, prev_value);
1020 : : }
1021 : 48513259 : }
1022 : :
1023 : : /* Record that X has the value Y and that X's previous value is PREV_X.
1024 : :
1025 : : This variant does not follow the value chain for Y. */
1026 : :
1027 : : void
1028 : 34272210 : const_and_copies::record_const_or_copy_raw (tree x, tree y, tree prev_x)
1029 : : {
1030 : 34272210 : if (dump_file && (dump_flags & TDF_DETAILS))
1031 : : {
1032 : 1255 : fprintf (dump_file, "0>>> COPY ");
1033 : 1255 : print_generic_expr (dump_file, x);
1034 : 1255 : fprintf (dump_file, " = ");
1035 : 1255 : print_generic_expr (dump_file, y);
1036 : 1255 : fprintf (dump_file, "\n");
1037 : : }
1038 : :
1039 : 34272210 : set_ssa_name_value (x, y);
1040 : 34272210 : m_stack.reserve (2);
1041 : 34272210 : m_stack.quick_push (prev_x);
1042 : 34272210 : m_stack.quick_push (x);
1043 : 34272210 : }
1044 : :
1045 : : /* Record that X has the value Y. */
1046 : :
1047 : : void
1048 : 22242948 : const_and_copies::record_const_or_copy (tree x, tree y)
1049 : : {
1050 : 22242948 : record_const_or_copy (x, y, SSA_NAME_VALUE (x));
1051 : 22242948 : }
1052 : :
1053 : : /* Record that X has the value Y and that X's previous value is PREV_X.
1054 : :
1055 : : This variant follow's Y value chain. */
1056 : :
1057 : : void
1058 : 34272210 : const_and_copies::record_const_or_copy (tree x, tree y, tree prev_x)
1059 : : {
1060 : : /* Y may be NULL if we are invalidating entries in the table. */
1061 : 34272210 : if (y && TREE_CODE (y) == SSA_NAME)
1062 : : {
1063 : 15314822 : tree tmp = SSA_NAME_VALUE (y);
1064 : 13876755 : y = tmp ? tmp : y;
1065 : : }
1066 : :
1067 : 34272210 : record_const_or_copy_raw (x, y, prev_x);
1068 : 34272210 : }
1069 : :
1070 : : bool
1071 : 235544776 : expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
1072 : : {
1073 : 235544776 : const struct hashable_expr *expr1 = p1->expr ();
1074 : 235544776 : const class expr_hash_elt *stamp1 = p1->stamp ();
1075 : 235544776 : const struct hashable_expr *expr2 = p2->expr ();
1076 : 235544776 : const class expr_hash_elt *stamp2 = p2->stamp ();
1077 : :
1078 : : /* This case should apply only when removing entries from the table. */
1079 : 235544776 : if (stamp1 == stamp2)
1080 : : return true;
1081 : :
1082 : 132275699 : if (p1->hash () != p2->hash ())
1083 : : return false;
1084 : :
1085 : : /* In case of a collision, both RHS have to be identical and have the
1086 : : same VUSE operands. */
1087 : 9201620 : if (hashable_expr_equal_p (expr1, expr2)
1088 : 9201620 : && types_compatible_p (expr1->type, expr2->type))
1089 : : return true;
1090 : :
1091 : : return false;
1092 : : }
1093 : :
1094 : : /* Given a conditional expression COND as a tree, initialize
1095 : : a hashable_expr expression EXPR. The conditional must be a
1096 : : comparison or logical negation. A constant or a variable is
1097 : : not permitted. */
1098 : :
1099 : : void
1100 : 56591546 : initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
1101 : : {
1102 : 56591546 : expr->type = boolean_type_node;
1103 : :
1104 : 56591546 : if (COMPARISON_CLASS_P (cond))
1105 : : {
1106 : 56423011 : expr->kind = EXPR_BINARY;
1107 : 56423011 : expr->ops.binary.op = TREE_CODE (cond);
1108 : 56423011 : expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
1109 : 56423011 : expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
1110 : : }
1111 : 168535 : else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1112 : : {
1113 : 168535 : expr->kind = EXPR_UNARY;
1114 : 168535 : expr->ops.unary.op = TRUTH_NOT_EXPR;
1115 : 168535 : expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
1116 : : }
1117 : : else
1118 : 0 : gcc_unreachable ();
1119 : 56591546 : }
1120 : :
1121 : : /* Build a cond_equivalence record indicating that the comparison
1122 : : CODE holds between operands OP0 and OP1 and push it to **P. */
1123 : :
1124 : : static void
1125 : 32112328 : build_and_record_new_cond (enum tree_code code,
1126 : : tree op0, tree op1,
1127 : : vec<cond_equivalence> *p,
1128 : : bool val = true)
1129 : : {
1130 : 32112328 : cond_equivalence c;
1131 : 32112328 : struct hashable_expr *cond = &c.cond;
1132 : :
1133 : 32112328 : gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1134 : :
1135 : 32112328 : cond->type = boolean_type_node;
1136 : 32112328 : cond->kind = EXPR_BINARY;
1137 : 32112328 : cond->ops.binary.op = code;
1138 : 32112328 : cond->ops.binary.opnd0 = op0;
1139 : 32112328 : cond->ops.binary.opnd1 = op1;
1140 : :
1141 : 32112328 : c.value = val ? boolean_true_node : boolean_false_node;
1142 : 32112328 : p->safe_push (c);
1143 : 32112328 : }
1144 : :
1145 : : /* Record that COND is true and INVERTED is false into the edge information
1146 : : structure. Also record that any conditions dominated by COND are true
1147 : : as well.
1148 : :
1149 : : For example, if a < b is true, then a <= b must also be true. */
1150 : :
1151 : : void
1152 : 28512964 : record_conditions (vec<cond_equivalence> *p, tree cond, tree inverted)
1153 : : {
1154 : 28512964 : tree op0, op1;
1155 : 28512964 : cond_equivalence c;
1156 : :
1157 : 28512964 : if (!COMPARISON_CLASS_P (cond))
1158 : 217191 : return;
1159 : :
1160 : 28295773 : op0 = TREE_OPERAND (cond, 0);
1161 : 28295773 : op1 = TREE_OPERAND (cond, 1);
1162 : :
1163 : 28295773 : switch (TREE_CODE (cond))
1164 : : {
1165 : 3394760 : case LT_EXPR:
1166 : 3394760 : case GT_EXPR:
1167 : 3394760 : if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1168 : : {
1169 : 92701 : build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
1170 : 92701 : build_and_record_new_cond (LTGT_EXPR, op0, op1, p);
1171 : : }
1172 : :
1173 : 5800618 : build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1174 : : ? LE_EXPR : GE_EXPR),
1175 : : op0, op1, p);
1176 : 3394760 : build_and_record_new_cond (NE_EXPR, op0, op1, p);
1177 : 3394760 : build_and_record_new_cond (EQ_EXPR, op0, op1, p, false);
1178 : 3394760 : break;
1179 : :
1180 : 3485473 : case GE_EXPR:
1181 : 3485473 : case LE_EXPR:
1182 : 3485473 : if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1183 : : {
1184 : 41583 : build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
1185 : : }
1186 : : break;
1187 : :
1188 : 10534031 : case EQ_EXPR:
1189 : 10534031 : if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1190 : : {
1191 : 475499 : build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
1192 : : }
1193 : 10534031 : build_and_record_new_cond (LE_EXPR, op0, op1, p);
1194 : 10534031 : build_and_record_new_cond (GE_EXPR, op0, op1, p);
1195 : 10534031 : break;
1196 : :
1197 : 21350 : case UNORDERED_EXPR:
1198 : 21350 : build_and_record_new_cond (NE_EXPR, op0, op1, p);
1199 : 21350 : build_and_record_new_cond (UNLE_EXPR, op0, op1, p);
1200 : 21350 : build_and_record_new_cond (UNGE_EXPR, op0, op1, p);
1201 : 21350 : build_and_record_new_cond (UNEQ_EXPR, op0, op1, p);
1202 : 21350 : build_and_record_new_cond (UNLT_EXPR, op0, op1, p);
1203 : 21350 : build_and_record_new_cond (UNGT_EXPR, op0, op1, p);
1204 : 21350 : break;
1205 : :
1206 : 13597 : case UNLT_EXPR:
1207 : 13597 : case UNGT_EXPR:
1208 : 23218 : build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1209 : : ? UNLE_EXPR : UNGE_EXPR),
1210 : : op0, op1, p);
1211 : 13597 : build_and_record_new_cond (NE_EXPR, op0, op1, p);
1212 : 13597 : break;
1213 : :
1214 : 1096 : case UNEQ_EXPR:
1215 : 1096 : build_and_record_new_cond (UNLE_EXPR, op0, op1, p);
1216 : 1096 : build_and_record_new_cond (UNGE_EXPR, op0, op1, p);
1217 : 1096 : break;
1218 : :
1219 : 8 : case LTGT_EXPR:
1220 : 8 : build_and_record_new_cond (NE_EXPR, op0, op1, p);
1221 : 8 : build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
1222 : 8 : break;
1223 : :
1224 : : default:
1225 : : break;
1226 : : }
1227 : :
1228 : : /* Now store the original true and false conditions into the first
1229 : : two slots. */
1230 : 28295773 : initialize_expr_from_cond (cond, &c.cond);
1231 : 28295773 : c.value = boolean_true_node;
1232 : 28295773 : p->safe_push (c);
1233 : :
1234 : : /* It is possible for INVERTED to be the negation of a comparison,
1235 : : and not a valid RHS or GIMPLE_COND condition. This happens because
1236 : : invert_truthvalue may return such an expression when asked to invert
1237 : : a floating-point comparison. These comparisons are not assumed to
1238 : : obey the trichotomy law. */
1239 : 28295773 : initialize_expr_from_cond (inverted, &c.cond);
1240 : 28295773 : c.value = boolean_false_node;
1241 : 28295773 : p->safe_push (c);
1242 : : }
|
