Line data Source code
1 : /* Header file for SSA dominator optimizations.
2 : Copyright (C) 2013-2026 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 65843682 : avail_exprs_stack::pop_to_marker ()
50 : {
51 : /* Remove all the expressions made available in this block. */
52 161110155 : while (m_stack.length () > 0)
53 : {
54 161110155 : std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop ();
55 161110155 : expr_hash_elt **slot;
56 :
57 161110155 : 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 95266473 : if (dump_file && (dump_flags & TDF_DETAILS))
64 : {
65 2579 : fprintf (dump_file, "<<<< ");
66 2579 : victim.first->print (dump_file);
67 : }
68 :
69 95266473 : slot = m_avail_exprs->find_slot (victim.first, NO_INSERT);
70 95266473 : gcc_assert (slot && *slot == victim.first);
71 95266473 : if (victim.second != NULL)
72 : {
73 4643909 : delete *slot;
74 4643909 : *slot = victim.second;
75 : }
76 : else
77 90622564 : m_avail_exprs->clear_slot (slot);
78 : }
79 65843682 : }
80 :
81 : /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
82 : from the hash table. */
83 :
84 : void
85 161110155 : avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
86 : class expr_hash_elt *elt2,
87 : char type)
88 : {
89 161110155 : if (elt1 && dump_file && (dump_flags & TDF_DETAILS))
90 : {
91 2579 : fprintf (dump_file, "%c>>> ", type);
92 2579 : elt1->print (dump_file);
93 : }
94 :
95 161110155 : m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2));
96 161110155 : }
97 :
98 : /* Helper for walk_non_aliased_vuses. Determine if we arrived at
99 : the desired memory state. */
100 :
101 : static void *
102 19326659 : vuse_eq (ao_ref *, tree vuse1, void *data)
103 : {
104 19326659 : tree vuse2 = (tree) data;
105 19326659 : if (vuse1 == vuse2)
106 548489 : return data;
107 :
108 : return NULL;
109 : }
110 :
111 : /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table.
112 : If found, return its LHS. Otherwise insert STMT in the table and
113 : return NULL_TREE.
114 :
115 : Also, when an expression is first inserted in the table, it is also
116 : is also added to AVAIL_EXPRS_STACK, so that it can be removed when
117 : we finish processing this block and its children. */
118 :
119 : tree
120 122458171 : avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p,
121 : expr_hash_elt **elt)
122 : {
123 122458171 : expr_hash_elt **slot;
124 122458171 : tree lhs;
125 :
126 : /* Get LHS of phi, assignment, or call; else NULL_TREE. */
127 122458171 : if (gimple_code (stmt) == GIMPLE_PHI)
128 9071366 : lhs = gimple_phi_result (stmt);
129 : else
130 113386805 : lhs = gimple_get_lhs (stmt);
131 :
132 122458171 : class expr_hash_elt element (stmt, lhs);
133 :
134 122458171 : if (dump_file && (dump_flags & TDF_DETAILS))
135 : {
136 2905 : fprintf (dump_file, "LKUP ");
137 2905 : element.print (dump_file);
138 : }
139 :
140 : /* Don't bother remembering constant assignments and copy operations.
141 : Constants and copy operations are handled by the constant/copy propagator
142 : in optimize_stmt. */
143 122458171 : if (element.expr()->kind == EXPR_SINGLE
144 122458171 : && (TREE_CODE (element.expr()->ops.single.rhs) == SSA_NAME
145 56279998 : || is_gimple_min_invariant (element.expr()->ops.single.rhs)))
146 : return NULL_TREE;
147 :
148 : /* Finally try to find the expression in the main expression hash table. */
149 165874695 : slot = m_avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
150 108833954 : if (slot == NULL)
151 : {
152 : return NULL_TREE;
153 : }
154 56767724 : else if (*slot == NULL)
155 : {
156 : /* We have, in effect, allocated *SLOT for ELEMENT at this point.
157 : We must initialize *SLOT to a real entry, even if we found a
158 : way to prove ELEMENT was a constant after not finding ELEMENT
159 : in the hash table.
160 :
161 : An uninitialized or empty slot is an indication no prior objects
162 : entered into the hash table had a hash collection with ELEMENT.
163 :
164 : If we fail to do so and had such entries in the table, they
165 : would become unreachable. */
166 46718898 : class expr_hash_elt *element2 = new expr_hash_elt (element);
167 46718898 : *slot = element2;
168 :
169 46718898 : record_expr (element2, NULL, '2');
170 46718898 : return NULL_TREE;
171 : }
172 :
173 : /* If we found a redundant memory operation do an alias walk to
174 : check if we can re-use it. */
175 19880591 : if (gimple_vuse (stmt) != (*slot)->vop ())
176 : {
177 8412453 : tree vuse1 = (*slot)->vop ();
178 8412453 : tree vuse2 = gimple_vuse (stmt);
179 : /* If we have a load of a register and a candidate in the
180 : hash with vuse1 then try to reach its stmt by walking
181 : up the virtual use-def chain using walk_non_aliased_vuses.
182 : But don't do this when removing expressions from the hash. */
183 8412453 : ao_ref ref;
184 8412453 : unsigned limit = param_sccvn_max_alias_queries_per_access;
185 15867243 : if (!(vuse1 && vuse2
186 8412453 : && gimple_assign_single_p (stmt)
187 8294155 : && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
188 7454790 : && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)),
189 7454790 : ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true)
190 7454790 : && walk_non_aliased_vuses (&ref, vuse2, true, vuse_eq, NULL, NULL,
191 : NULL, limit, vuse1) != NULL))
192 : {
193 7863964 : if (insert)
194 : {
195 4643909 : class expr_hash_elt *element2 = new expr_hash_elt (element);
196 :
197 : /* Insert the expr into the hash by replacing the current
198 : entry and recording the value to restore in the
199 : avail_exprs_stack. */
200 4643909 : record_expr (element2, *slot, '2');
201 4643909 : *slot = element2;
202 : }
203 7863964 : return NULL_TREE;
204 : }
205 : }
206 :
207 : /* Extract the LHS of the assignment so that it can be used as the current
208 : definition of another variable. */
209 2184862 : lhs = (*slot)->lhs ();
210 2184862 : if (elt)
211 855564 : *elt = *slot;
212 :
213 : /* Valueize the result. */
214 2184862 : if (TREE_CODE (lhs) == SSA_NAME)
215 : {
216 1860180 : tree tem = SSA_NAME_VALUE (lhs);
217 1586844 : if (tem)
218 2184862 : lhs = tem;
219 : }
220 :
221 2184862 : if (dump_file && (dump_flags & TDF_DETAILS))
222 : {
223 173 : fprintf (dump_file, "FIND: ");
224 173 : print_generic_expr (dump_file, lhs);
225 173 : fprintf (dump_file, "\n");
226 : }
227 :
228 : return lhs;
229 122458171 : }
230 :
231 : /* Enter condition equivalence P into the hash table.
232 :
233 : This indicates that a conditional expression has a known
234 : boolean value. */
235 :
236 : void
237 44270072 : avail_exprs_stack::record_cond (cond_equivalence *p)
238 : {
239 44270072 : class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value);
240 44270072 : expr_hash_elt **slot;
241 :
242 44270072 : slot = m_avail_exprs->find_slot_with_hash (element, element->hash (), INSERT);
243 44270072 : if (*slot == NULL)
244 : {
245 43903666 : *slot = element;
246 43903666 : record_expr (element, NULL, '1');
247 : }
248 : else
249 366406 : delete element;
250 44270072 : }
251 :
252 : /* Generate a hash value for a pair of expressions. This can be used
253 : iteratively by passing a previous result in HSTATE.
254 :
255 : The same hash value is always returned for a given pair of expressions,
256 : regardless of the order in which they are presented. This is useful in
257 : hashing the operands of commutative functions. */
258 :
259 : namespace inchash
260 : {
261 :
262 : static void
263 59534065 : add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
264 : {
265 59534065 : hash one, two;
266 :
267 59534065 : inchash::add_expr (t1, one);
268 59534065 : inchash::add_expr (t2, two);
269 59534065 : hstate.add_commutative (one, two);
270 59534065 : }
271 :
272 : /* Compute a hash value for a hashable_expr value EXPR and a
273 : previously accumulated hash value VAL. If two hashable_expr
274 : values compare equal with hashable_expr_equal_p, they must
275 : hash to the same value, given an identical value of VAL.
276 : The logic is intended to follow inchash::add_expr in tree.cc. */
277 :
278 : static void
279 126068948 : add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
280 : {
281 126068948 : switch (expr->kind)
282 : {
283 22241678 : case EXPR_SINGLE:
284 22241678 : inchash::add_expr (expr->ops.single.rhs, hstate);
285 22241678 : break;
286 :
287 8273190 : case EXPR_UNARY:
288 8273190 : hstate.add_object (expr->ops.unary.op);
289 :
290 : /* Make sure to include signedness in the hash computation.
291 : Don't hash the type, that can lead to having nodes which
292 : compare equal according to operand_equal_p, but which
293 : have different hash codes. */
294 8273190 : if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
295 960221 : || expr->ops.unary.op == NON_LVALUE_EXPR)
296 7312969 : hstate.add_int (TYPE_UNSIGNED (expr->type));
297 :
298 8273190 : inchash::add_expr (expr->ops.unary.opnd, hstate);
299 8273190 : break;
300 :
301 83155740 : case EXPR_BINARY:
302 83155740 : hstate.add_object (expr->ops.binary.op);
303 83155740 : if (commutative_tree_code (expr->ops.binary.op))
304 59533288 : inchash::add_expr_commutative (expr->ops.binary.opnd0,
305 59533288 : expr->ops.binary.opnd1, hstate);
306 : else
307 : {
308 23622452 : inchash::add_expr (expr->ops.binary.opnd0, hstate);
309 23622452 : inchash::add_expr (expr->ops.binary.opnd1, hstate);
310 : }
311 : break;
312 :
313 231213 : case EXPR_TERNARY:
314 231213 : hstate.add_object (expr->ops.ternary.op);
315 231213 : if (commutative_ternary_tree_code (expr->ops.ternary.op))
316 777 : inchash::add_expr_commutative (expr->ops.ternary.opnd0,
317 777 : expr->ops.ternary.opnd1, hstate);
318 : else
319 : {
320 230436 : inchash::add_expr (expr->ops.ternary.opnd0, hstate);
321 230436 : inchash::add_expr (expr->ops.ternary.opnd1, hstate);
322 : }
323 231213 : inchash::add_expr (expr->ops.ternary.opnd2, hstate);
324 231213 : break;
325 :
326 3095761 : case EXPR_CALL:
327 3095761 : {
328 3095761 : size_t i;
329 3095761 : enum tree_code code = CALL_EXPR;
330 3095761 : gcall *fn_from;
331 :
332 3095761 : hstate.add_object (code);
333 3095761 : fn_from = expr->ops.call.fn_from;
334 3095761 : if (gimple_call_internal_p (fn_from))
335 270897 : hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
336 : else
337 2824864 : inchash::add_expr (gimple_call_fn (fn_from), hstate);
338 9126346 : for (i = 0; i < expr->ops.call.nargs; i++)
339 6030585 : inchash::add_expr (expr->ops.call.args[i], hstate);
340 : }
341 3095761 : break;
342 :
343 : case EXPR_PHI:
344 : {
345 : size_t i;
346 :
347 32587096 : for (i = 0; i < expr->ops.phi.nargs; i++)
348 23515730 : inchash::add_expr (expr->ops.phi.args[i], hstate);
349 : }
350 : break;
351 :
352 0 : default:
353 0 : gcc_unreachable ();
354 : }
355 126068948 : }
356 :
357 : }
358 :
359 : /* Hashing and equality functions. We compute a value number for expressions
360 : using the code of the expression and the SSA numbers of its operands. */
361 :
362 : static hashval_t
363 166728243 : avail_expr_hash (class expr_hash_elt *p)
364 : {
365 166728243 : const struct hashable_expr *expr = p->expr ();
366 166728243 : inchash::hash hstate;
367 :
368 166728243 : if (expr->kind == EXPR_SINGLE)
369 : {
370 : /* T could potentially be a switch index or a goto dest. */
371 62900973 : tree t = expr->ops.single.rhs;
372 62900973 : if (TREE_CODE (t) == MEM_REF || handled_component_p (t))
373 : {
374 : /* Make equivalent statements of both these kinds hash together.
375 : Dealing with both MEM_REF and ARRAY_REF allows us not to care
376 : about equivalence with other statements not considered here. */
377 41976524 : bool reverse;
378 41976524 : poly_int64 offset, size, max_size;
379 41976524 : tree base = get_ref_base_and_extent (t, &offset, &size, &max_size,
380 : &reverse);
381 : /* Strictly, we could try to normalize variable-sized accesses too,
382 : but here we just deal with the common case. */
383 41976524 : if (known_size_p (max_size)
384 41976524 : && known_eq (size, max_size))
385 : {
386 40659295 : enum tree_code code = MEM_REF;
387 40659295 : hstate.add_object (code);
388 40659295 : inchash::add_expr (base, hstate,
389 40659295 : TREE_CODE (base) == MEM_REF
390 : ? OEP_ADDRESS_OF : 0);
391 40659295 : hstate.add_object (offset);
392 40659295 : hstate.add_object (size);
393 40659295 : return hstate.end ();
394 : }
395 : }
396 : }
397 :
398 126068948 : inchash::add_hashable_expr (expr, hstate);
399 :
400 126068948 : return hstate.end ();
401 : }
402 :
403 : /* Compares trees T0 and T1 to see if they are MEM_REF or ARRAY_REFs equivalent
404 : to each other. (That is, they return the value of the same bit of memory.)
405 :
406 : Return TRUE if the two are so equivalent; FALSE if not (which could still
407 : mean the two are equivalent by other means). */
408 :
409 : static bool
410 9256946 : equal_mem_array_ref_p (tree t0, tree t1)
411 : {
412 9256946 : if (TREE_CODE (t0) != MEM_REF && ! handled_component_p (t0))
413 : return false;
414 7957283 : if (TREE_CODE (t1) != MEM_REF && ! handled_component_p (t1))
415 : return false;
416 :
417 7957283 : if (!types_compatible_p (TREE_TYPE (t0), TREE_TYPE (t1)))
418 : return false;
419 7953395 : bool rev0;
420 7953395 : poly_int64 off0, sz0, max0;
421 7953395 : tree base0 = get_ref_base_and_extent (t0, &off0, &sz0, &max0, &rev0);
422 7953395 : if (!known_size_p (max0)
423 7953395 : || maybe_ne (sz0, max0))
424 : return false;
425 :
426 7823253 : bool rev1;
427 7823253 : poly_int64 off1, sz1, max1;
428 7823253 : tree base1 = get_ref_base_and_extent (t1, &off1, &sz1, &max1, &rev1);
429 7823253 : if (!known_size_p (max1)
430 7823253 : || maybe_ne (sz1, max1))
431 : return false;
432 :
433 7823253 : if (rev0 != rev1 || maybe_ne (sz0, sz1) || maybe_ne (off0, off1))
434 : return false;
435 :
436 7823253 : return operand_equal_p (base0, base1,
437 7823253 : (TREE_CODE (base0) == MEM_REF
438 7823253 : || TREE_CODE (base0) == TARGET_MEM_REF)
439 2779686 : && (TREE_CODE (base1) == MEM_REF
440 2779686 : || TREE_CODE (base1) == TARGET_MEM_REF)
441 7823253 : ? OEP_ADDRESS_OF : 0);
442 : }
443 :
444 : /* Compare two hashable_expr structures for equivalence. They are
445 : considered equivalent when the expressions they denote must
446 : necessarily be equal. The logic is intended to follow that of
447 : operand_equal_p in fold-const.cc */
448 :
449 : static bool
450 10718899 : hashable_expr_equal_p (const struct hashable_expr *expr0,
451 : const struct hashable_expr *expr1)
452 : {
453 10718899 : tree type0 = expr0->type;
454 10718899 : tree type1 = expr1->type;
455 :
456 : /* If either type is NULL, there is nothing to check. */
457 10718899 : if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
458 : return false;
459 :
460 : /* If both types don't have the same signedness, precision, and mode,
461 : then we can't consider them equal. */
462 10718899 : if (type0 != type1
463 10718899 : && (TREE_CODE (type0) == ERROR_MARK
464 1478163 : || TREE_CODE (type1) == ERROR_MARK
465 1478163 : || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
466 1414217 : || element_precision (type0) != element_precision (type1)
467 1294512 : || TYPE_MODE (type0) != TYPE_MODE (type1)))
468 : return false;
469 :
470 10455931 : if (expr0->kind != expr1->kind)
471 : return false;
472 :
473 10455931 : switch (expr0->kind)
474 : {
475 9256946 : case EXPR_SINGLE:
476 9256946 : return equal_mem_array_ref_p (expr0->ops.single.rhs,
477 9256946 : expr1->ops.single.rhs)
478 10693581 : || operand_equal_p (expr0->ops.single.rhs,
479 1436635 : expr1->ops.single.rhs, 0);
480 211697 : case EXPR_UNARY:
481 211697 : if (expr0->ops.unary.op != expr1->ops.unary.op)
482 : return false;
483 :
484 15879 : if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
485 15879 : || expr0->ops.unary.op == NON_LVALUE_EXPR)
486 211697 : && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
487 : return false;
488 :
489 211697 : return operand_equal_p (expr0->ops.unary.opnd,
490 211697 : expr1->ops.unary.opnd, 0);
491 :
492 826143 : case EXPR_BINARY:
493 826143 : if (expr0->ops.binary.op != expr1->ops.binary.op)
494 : return false;
495 :
496 826137 : if (operand_equal_p (expr0->ops.binary.opnd0,
497 826137 : expr1->ops.binary.opnd0, 0)
498 1638542 : && operand_equal_p (expr0->ops.binary.opnd1,
499 812405 : expr1->ops.binary.opnd1, 0))
500 : return true;
501 :
502 : /* For commutative ops, allow the other order. */
503 15618 : return (commutative_tree_code (expr0->ops.binary.op)
504 13987 : && operand_equal_p (expr0->ops.binary.opnd0,
505 13987 : expr1->ops.binary.opnd1, 0)
506 21087 : && operand_equal_p (expr0->ops.binary.opnd1,
507 5469 : expr1->ops.binary.opnd0, 0));
508 :
509 913 : case EXPR_TERNARY:
510 913 : if (expr0->ops.ternary.op != expr1->ops.ternary.op
511 1826 : || !operand_equal_p (expr0->ops.ternary.opnd2,
512 913 : expr1->ops.ternary.opnd2, 0))
513 : return false;
514 :
515 : /* BIT_INSERT_EXPR has an implicit operand as the type precision
516 : of op1. Need to check to make sure they are the same. */
517 913 : if (expr0->ops.ternary.op == BIT_INSERT_EXPR
518 0 : && TREE_CODE (expr0->ops.ternary.opnd1) == INTEGER_CST
519 0 : && TREE_CODE (expr1->ops.ternary.opnd1) == INTEGER_CST
520 913 : && TYPE_PRECISION (TREE_TYPE (expr0->ops.ternary.opnd1))
521 0 : != TYPE_PRECISION (TREE_TYPE (expr1->ops.ternary.opnd1)))
522 : return false;
523 :
524 913 : if (operand_equal_p (expr0->ops.ternary.opnd0,
525 913 : expr1->ops.ternary.opnd0, 0)
526 1826 : && operand_equal_p (expr0->ops.ternary.opnd1,
527 913 : expr1->ops.ternary.opnd1, 0))
528 : return true;
529 :
530 : /* For commutative ops, allow the other order. */
531 0 : return (commutative_ternary_tree_code (expr0->ops.ternary.op)
532 0 : && operand_equal_p (expr0->ops.ternary.opnd0,
533 0 : expr1->ops.ternary.opnd1, 0)
534 0 : && operand_equal_p (expr0->ops.ternary.opnd1,
535 0 : expr1->ops.ternary.opnd0, 0));
536 :
537 130306 : case EXPR_CALL:
538 130306 : {
539 130306 : size_t i;
540 :
541 : /* If the calls are to different functions, then they
542 : clearly cannot be equal. */
543 130306 : if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
544 130306 : expr1->ops.call.fn_from))
545 : return false;
546 :
547 129685 : if (! expr0->ops.call.pure)
548 : return false;
549 :
550 129685 : if (expr0->ops.call.nargs != expr1->ops.call.nargs)
551 : return false;
552 :
553 374198 : for (i = 0; i < expr0->ops.call.nargs; i++)
554 244555 : if (! operand_equal_p (expr0->ops.call.args[i],
555 244555 : expr1->ops.call.args[i], 0))
556 : return false;
557 :
558 129643 : if (stmt_could_throw_p (cfun, expr0->ops.call.fn_from))
559 : {
560 22 : int lp0 = lookup_stmt_eh_lp (expr0->ops.call.fn_from);
561 22 : int lp1 = lookup_stmt_eh_lp (expr1->ops.call.fn_from);
562 22 : if ((lp0 > 0 || lp1 > 0) && lp0 != lp1)
563 : return false;
564 : }
565 :
566 : return true;
567 : }
568 :
569 29926 : case EXPR_PHI:
570 29926 : {
571 29926 : size_t i;
572 :
573 29926 : if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
574 : return false;
575 :
576 74124 : for (i = 0; i < expr0->ops.phi.nargs; i++)
577 44260 : if (! operand_equal_p (expr0->ops.phi.args[i],
578 44260 : expr1->ops.phi.args[i], 0))
579 : return false;
580 :
581 : return true;
582 : }
583 :
584 0 : default:
585 0 : gcc_unreachable ();
586 : }
587 : }
588 :
589 : /* Given a statement STMT, construct a hash table element. */
590 :
591 122458171 : expr_hash_elt::expr_hash_elt (gimple *stmt, tree orig_lhs)
592 : {
593 122458171 : enum gimple_code code = gimple_code (stmt);
594 122458171 : struct hashable_expr *expr = this->expr ();
595 :
596 122458171 : if (code == GIMPLE_ASSIGN)
597 : {
598 91870275 : enum tree_code subcode = gimple_assign_rhs_code (stmt);
599 :
600 91870275 : switch (get_gimple_rhs_class (subcode))
601 : {
602 62833404 : case GIMPLE_SINGLE_RHS:
603 62833404 : expr->kind = EXPR_SINGLE;
604 62833404 : expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
605 62833404 : expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
606 62833404 : break;
607 8143544 : case GIMPLE_UNARY_RHS:
608 8143544 : expr->kind = EXPR_UNARY;
609 8143544 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
610 8143544 : if (CONVERT_EXPR_CODE_P (subcode))
611 7312969 : subcode = NOP_EXPR;
612 8143544 : expr->ops.unary.op = subcode;
613 8143544 : expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
614 8143544 : break;
615 20662114 : case GIMPLE_BINARY_RHS:
616 20662114 : expr->kind = EXPR_BINARY;
617 20662114 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
618 20662114 : expr->ops.binary.op = subcode;
619 20662114 : expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
620 20662114 : expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
621 20662114 : break;
622 231213 : case GIMPLE_TERNARY_RHS:
623 231213 : expr->kind = EXPR_TERNARY;
624 231213 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
625 231213 : expr->ops.ternary.op = subcode;
626 231213 : expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
627 231213 : expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
628 231213 : expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
629 231213 : break;
630 0 : default:
631 0 : gcc_unreachable ();
632 : }
633 : }
634 : else if (code == GIMPLE_COND)
635 : {
636 18353200 : expr->type = boolean_type_node;
637 18353200 : expr->kind = EXPR_BINARY;
638 18353200 : expr->ops.binary.op = gimple_cond_code (stmt);
639 18353200 : expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
640 18353200 : expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
641 : }
642 3095761 : else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
643 : {
644 3095761 : size_t nargs = gimple_call_num_args (call_stmt);
645 3095761 : size_t i;
646 :
647 3095761 : gcc_assert (gimple_call_lhs (call_stmt));
648 :
649 3095761 : expr->type = TREE_TYPE (gimple_call_lhs (call_stmt));
650 3095761 : expr->kind = EXPR_CALL;
651 3095761 : expr->ops.call.fn_from = call_stmt;
652 :
653 3095761 : if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE))
654 : expr->ops.call.pure = true;
655 : else
656 1501942 : expr->ops.call.pure = false;
657 :
658 3095761 : expr->ops.call.nargs = nargs;
659 3095761 : expr->ops.call.args = XCNEWVEC (tree, nargs);
660 9126346 : for (i = 0; i < nargs; i++)
661 6030585 : expr->ops.call.args[i] = gimple_call_arg (call_stmt, i);
662 : }
663 67329 : else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
664 : {
665 67329 : expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt));
666 67329 : expr->kind = EXPR_SINGLE;
667 67329 : expr->ops.single.rhs = gimple_switch_index (swtch_stmt);
668 : }
669 : else if (code == GIMPLE_GOTO)
670 : {
671 240 : expr->type = TREE_TYPE (gimple_goto_dest (stmt));
672 240 : expr->kind = EXPR_SINGLE;
673 240 : expr->ops.single.rhs = gimple_goto_dest (stmt);
674 : }
675 : else if (code == GIMPLE_PHI)
676 : {
677 9071366 : size_t nargs = gimple_phi_num_args (stmt);
678 9071366 : size_t i;
679 :
680 9071366 : expr->type = TREE_TYPE (gimple_phi_result (stmt));
681 9071366 : expr->kind = EXPR_PHI;
682 9071366 : expr->ops.phi.nargs = nargs;
683 9071366 : expr->ops.phi.args = XCNEWVEC (tree, nargs);
684 32587096 : for (i = 0; i < nargs; i++)
685 23515730 : expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
686 : }
687 : else
688 0 : gcc_unreachable ();
689 :
690 122458171 : m_lhs = orig_lhs;
691 122458171 : m_vop = gimple_vuse (stmt);
692 122458171 : m_hash = avail_expr_hash (this);
693 122458171 : m_stamp = this;
694 122458171 : }
695 :
696 : /* Given a hashable_expr expression ORIG and an ORIG_LHS,
697 : construct a hash table element. */
698 :
699 44270072 : expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs)
700 : {
701 44270072 : m_expr = *orig;
702 44270072 : m_lhs = orig_lhs;
703 44270072 : m_vop = NULL_TREE;
704 44270072 : m_hash = avail_expr_hash (this);
705 44270072 : m_stamp = this;
706 44270072 : }
707 :
708 : /* Copy constructor for a hash table element. */
709 :
710 51362807 : expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt)
711 : {
712 51362807 : m_expr = old_elt.m_expr;
713 51362807 : m_lhs = old_elt.m_lhs;
714 51362807 : m_vop = old_elt.m_vop;
715 51362807 : m_hash = old_elt.m_hash;
716 51362807 : m_stamp = this;
717 :
718 : /* Now deep copy the malloc'd space for CALL and PHI args. */
719 51362807 : if (old_elt.m_expr.kind == EXPR_CALL)
720 : {
721 1208206 : size_t nargs = old_elt.m_expr.ops.call.nargs;
722 1208206 : size_t i;
723 :
724 1208206 : m_expr.ops.call.args = XCNEWVEC (tree, nargs);
725 3848079 : for (i = 0; i < nargs; i++)
726 2639873 : m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i];
727 : }
728 50154601 : else if (old_elt.m_expr.kind == EXPR_PHI)
729 : {
730 9036988 : size_t nargs = old_elt.m_expr.ops.phi.nargs;
731 9036988 : size_t i;
732 :
733 9036988 : m_expr.ops.phi.args = XCNEWVEC (tree, nargs);
734 32489143 : for (i = 0; i < nargs; i++)
735 23452155 : m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i];
736 : }
737 51362807 : }
738 :
739 : /* Calls and PHIs have a variable number of arguments that are allocated
740 : on the heap. Thus we have to have a special dtor to release them. */
741 :
742 218091050 : expr_hash_elt::~expr_hash_elt ()
743 : {
744 218091050 : if (m_expr.kind == EXPR_CALL)
745 4303967 : free (m_expr.ops.call.args);
746 213787083 : else if (m_expr.kind == EXPR_PHI)
747 18108354 : free (m_expr.ops.phi.args);
748 218091050 : }
749 :
750 : /* Print a diagnostic dump of an expression hash table entry. */
751 :
752 : void
753 8063 : expr_hash_elt::print (FILE *stream)
754 : {
755 8063 : fprintf (stream, "STMT ");
756 :
757 8063 : if (m_lhs)
758 : {
759 7504 : print_generic_expr (stream, m_lhs);
760 7504 : fprintf (stream, " = ");
761 : }
762 :
763 8063 : switch (m_expr.kind)
764 : {
765 2622 : case EXPR_SINGLE:
766 2622 : print_generic_expr (stream, m_expr.ops.single.rhs);
767 2622 : break;
768 :
769 276 : case EXPR_UNARY:
770 276 : fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op));
771 276 : print_generic_expr (stream, m_expr.ops.unary.opnd);
772 276 : break;
773 :
774 4447 : case EXPR_BINARY:
775 4447 : print_generic_expr (stream, m_expr.ops.binary.opnd0);
776 4447 : fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op));
777 4447 : print_generic_expr (stream, m_expr.ops.binary.opnd1);
778 4447 : break;
779 :
780 0 : case EXPR_TERNARY:
781 0 : fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op));
782 0 : print_generic_expr (stream, m_expr.ops.ternary.opnd0);
783 0 : fputs (", ", stream);
784 0 : print_generic_expr (stream, m_expr.ops.ternary.opnd1);
785 0 : fputs (", ", stream);
786 0 : print_generic_expr (stream, m_expr.ops.ternary.opnd2);
787 0 : fputs (">", stream);
788 0 : break;
789 :
790 6 : case EXPR_CALL:
791 6 : {
792 6 : size_t i;
793 6 : size_t nargs = m_expr.ops.call.nargs;
794 6 : gcall *fn_from;
795 :
796 6 : fn_from = m_expr.ops.call.fn_from;
797 6 : if (gimple_call_internal_p (fn_from))
798 0 : fprintf (stream, ".%s",
799 : internal_fn_name (gimple_call_internal_fn (fn_from)));
800 : else
801 6 : print_generic_expr (stream, gimple_call_fn (fn_from));
802 6 : fprintf (stream, " (");
803 24 : for (i = 0; i < nargs; i++)
804 : {
805 12 : print_generic_expr (stream, m_expr.ops.call.args[i]);
806 12 : if (i + 1 < nargs)
807 6 : fprintf (stream, ", ");
808 : }
809 6 : fprintf (stream, ")");
810 : }
811 6 : break;
812 :
813 712 : case EXPR_PHI:
814 712 : {
815 712 : size_t i;
816 712 : size_t nargs = m_expr.ops.phi.nargs;
817 :
818 712 : fprintf (stream, "PHI <");
819 3043 : for (i = 0; i < nargs; i++)
820 : {
821 1619 : print_generic_expr (stream, m_expr.ops.phi.args[i]);
822 1619 : if (i + 1 < nargs)
823 907 : fprintf (stream, ", ");
824 : }
825 712 : fprintf (stream, ">");
826 : }
827 712 : break;
828 : }
829 :
830 8063 : if (m_vop)
831 : {
832 2384 : fprintf (stream, " with ");
833 2384 : print_generic_expr (stream, m_vop);
834 : }
835 :
836 8063 : fprintf (stream, "\n");
837 8063 : }
838 :
839 : /* Pop entries off the stack until we hit the NULL marker.
840 : For each entry popped, use the SRC/DEST pair to restore
841 : SRC to its prior value. */
842 :
843 : void
844 55298111 : const_and_copies::pop_to_marker (void)
845 : {
846 94329448 : while (m_stack.length () > 0)
847 : {
848 94329448 : tree prev_value, dest;
849 :
850 94329448 : dest = m_stack.pop ();
851 :
852 : /* A NULL value indicates we should stop unwinding, otherwise
853 : pop off the next entry as they're recorded in pairs. */
854 94329448 : if (dest == NULL)
855 : break;
856 :
857 39031337 : if (dump_file && (dump_flags & TDF_DETAILS))
858 : {
859 1245 : fprintf (dump_file, "<<<< COPY ");
860 1245 : print_generic_expr (dump_file, dest);
861 1245 : fprintf (dump_file, " = ");
862 1245 : print_generic_expr (dump_file, SSA_NAME_VALUE (dest));
863 1245 : fprintf (dump_file, "\n");
864 : }
865 :
866 39031337 : prev_value = m_stack.pop ();
867 39031337 : set_ssa_name_value (dest, prev_value);
868 : }
869 55298111 : }
870 :
871 : /* Record that X has the value Y and that X's previous value is PREV_X.
872 :
873 : This variant does not follow the value chain for Y. */
874 :
875 : void
876 39031337 : const_and_copies::record_const_or_copy_raw (tree x, tree y, tree prev_x)
877 : {
878 39031337 : if (dump_file && (dump_flags & TDF_DETAILS))
879 : {
880 1245 : fprintf (dump_file, "0>>> COPY ");
881 1245 : print_generic_expr (dump_file, x);
882 1245 : fprintf (dump_file, " = ");
883 1245 : print_generic_expr (dump_file, y);
884 1245 : fprintf (dump_file, "\n");
885 : }
886 :
887 39031337 : set_ssa_name_value (x, y);
888 39031337 : m_stack.reserve (2);
889 39031337 : m_stack.quick_push (prev_x);
890 39031337 : m_stack.quick_push (x);
891 39031337 : }
892 :
893 : /* Record that X has the value Y. */
894 :
895 : void
896 25287803 : const_and_copies::record_const_or_copy (tree x, tree y)
897 : {
898 25287803 : record_const_or_copy (x, y, SSA_NAME_VALUE (x));
899 25287803 : }
900 :
901 : /* Record that X has the value Y and that X's previous value is PREV_X.
902 :
903 : This variant follow's Y value chain. */
904 :
905 : void
906 39031337 : const_and_copies::record_const_or_copy (tree x, tree y, tree prev_x)
907 : {
908 : /* Y may be NULL if we are invalidating entries in the table. */
909 39031337 : if (y && TREE_CODE (y) == SSA_NAME)
910 : {
911 17147737 : tree tmp = SSA_NAME_VALUE (y);
912 15567595 : y = tmp ? tmp : y;
913 : }
914 :
915 39031337 : record_const_or_copy_raw (x, y, prev_x);
916 39031337 : }
917 :
918 : bool
919 201012320 : expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
920 : {
921 201012320 : const struct hashable_expr *expr1 = p1->expr ();
922 201012320 : const class expr_hash_elt *stamp1 = p1->stamp ();
923 201012320 : const struct hashable_expr *expr2 = p2->expr ();
924 201012320 : const class expr_hash_elt *stamp2 = p2->stamp ();
925 :
926 : /* This case should apply only when removing entries from the table. */
927 201012320 : if (stamp1 == stamp2)
928 : return true;
929 :
930 105745847 : if (p1->hash () != p2->hash ())
931 : return false;
932 :
933 : /* In case of a collision, both RHS have to be identical and have the
934 : same VUSE operands. */
935 10718899 : if (hashable_expr_equal_p (expr1, expr2)
936 10718899 : && types_compatible_p (expr1->type, expr2->type))
937 : return true;
938 :
939 : return false;
940 : }
941 :
942 : /* Given a conditional expression COND as a tree, initialize
943 : a hashable_expr expression EXPR. The conditional must be a
944 : comparison or logical negation. A constant or a variable is
945 : not permitted. */
946 :
947 : static void
948 67117688 : initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
949 : {
950 67117688 : expr->type = boolean_type_node;
951 :
952 67117688 : if (COMPARISON_CLASS_P (cond))
953 : {
954 66898920 : expr->kind = EXPR_BINARY;
955 66898920 : expr->ops.binary.op = TREE_CODE (cond);
956 66898920 : expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
957 66898920 : expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
958 : }
959 218768 : else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
960 : {
961 218768 : expr->kind = EXPR_UNARY;
962 218768 : expr->ops.unary.op = TRUTH_NOT_EXPR;
963 218768 : expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
964 : }
965 : else
966 0 : gcc_unreachable ();
967 67117688 : }
968 :
969 : /* Record that COND is true and INVERTED is false into the edge information
970 : structure. Also record that any conditions dominated by COND are true
971 : as well.
972 :
973 : For example, if a < b is true, then a <= b must also be true. */
974 :
975 : void
976 33822585 : record_conditions (vec<cond_equivalence> *p, tree cond, tree inverted)
977 : {
978 33822585 : cond_equivalence c;
979 :
980 33822585 : if (!COMPARISON_CLASS_P (cond))
981 : return;
982 :
983 : /* Now store the original true and false conditions into the first
984 : two slots. */
985 33558844 : initialize_expr_from_cond (cond, &c.cond);
986 33558844 : c.value = boolean_true_node;
987 33558844 : p->safe_push (c);
988 :
989 : /* It is possible for INVERTED to be the negation of a comparison,
990 : and not a valid RHS or GIMPLE_COND condition. This happens because
991 : invert_truthvalue may return such an expression when asked to invert
992 : a floating-point comparison. These comparisons are not assumed to
993 : obey the trichotomy law. */
994 33558844 : initialize_expr_from_cond (inverted, &c.cond);
995 33558844 : c.value = boolean_false_node;
996 33558844 : p->safe_push (c);
997 : }
|
