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 65090066 : avail_exprs_stack::pop_to_marker ()
50 : {
51 : /* Remove all the expressions made available in this block. */
52 159462917 : while (m_stack.length () > 0)
53 : {
54 159462917 : std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop ();
55 159462917 : expr_hash_elt **slot;
56 :
57 159462917 : 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 94372851 : if (dump_file && (dump_flags & TDF_DETAILS))
64 : {
65 2579 : fprintf (dump_file, "<<<< ");
66 2579 : victim.first->print (dump_file);
67 : }
68 :
69 94372851 : slot = m_avail_exprs->find_slot (victim.first, NO_INSERT);
70 94372851 : gcc_assert (slot && *slot == victim.first);
71 94372851 : if (victim.second != NULL)
72 : {
73 4602204 : delete *slot;
74 4602204 : *slot = victim.second;
75 : }
76 : else
77 89770647 : m_avail_exprs->clear_slot (slot);
78 : }
79 65090066 : }
80 :
81 : /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
82 : from the hash table. */
83 :
84 : void
85 159462917 : avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
86 : class expr_hash_elt *elt2,
87 : char type)
88 : {
89 159462917 : 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 159462917 : m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2));
96 159462917 : }
97 :
98 : /* Helper for walk_non_aliased_vuses. Determine if we arrived at
99 : the desired memory state. */
100 :
101 : static void *
102 19188239 : vuse_eq (ao_ref *, tree vuse1, void *data)
103 : {
104 19188239 : tree vuse2 = (tree) data;
105 19188239 : if (vuse1 == vuse2)
106 539809 : 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 121619051 : avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p,
121 : expr_hash_elt **elt)
122 : {
123 121619051 : expr_hash_elt **slot;
124 121619051 : tree lhs;
125 :
126 : /* Get LHS of phi, assignment, or call; else NULL_TREE. */
127 121619051 : if (gimple_code (stmt) == GIMPLE_PHI)
128 8977732 : lhs = gimple_phi_result (stmt);
129 : else
130 112641319 : lhs = gimple_get_lhs (stmt);
131 :
132 121619051 : class expr_hash_elt element (stmt, lhs);
133 :
134 121619051 : 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 121619051 : if (element.expr()->kind == EXPR_SINGLE
144 121619051 : && (TREE_CODE (element.expr()->ops.single.rhs) == SSA_NAME
145 55871519 : || 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 164591603 : slot = m_avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
150 108042448 : if (slot == NULL)
151 : {
152 : return NULL_TREE;
153 : }
154 56408706 : 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 46466192 : class expr_hash_elt *element2 = new expr_hash_elt (element);
167 46466192 : *slot = element2;
168 :
169 46466192 : record_expr (element2, NULL, '2');
170 46466192 : 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 19677482 : if (gimple_vuse (stmt) != (*slot)->vop ())
176 : {
177 8328886 : tree vuse1 = (*slot)->vop ();
178 8328886 : 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 8328886 : ao_ref ref;
184 8328886 : unsigned limit = param_sccvn_max_alias_queries_per_access;
185 15700522 : if (!(vuse1 && vuse2
186 8328886 : && gimple_assign_single_p (stmt)
187 8210594 : && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
188 7371636 : && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)),
189 7371636 : ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true)
190 7371636 : && walk_non_aliased_vuses (&ref, vuse2, true, vuse_eq, NULL, NULL,
191 : NULL, limit, vuse1) != NULL))
192 : {
193 7789077 : if (insert)
194 : {
195 4602204 : 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 4602204 : record_expr (element2, *slot, '2');
201 4602204 : *slot = element2;
202 : }
203 7789077 : 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 2153437 : lhs = (*slot)->lhs ();
210 2153437 : if (elt)
211 850907 : *elt = *slot;
212 :
213 : /* Valueize the result. */
214 2153437 : if (TREE_CODE (lhs) == SSA_NAME)
215 : {
216 1842868 : tree tem = SSA_NAME_VALUE (lhs);
217 1570223 : if (tem)
218 2153437 : lhs = tem;
219 : }
220 :
221 2153437 : 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 121619051 : }
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 43669124 : avail_exprs_stack::record_cond (cond_equivalence *p)
238 : {
239 43669124 : class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value);
240 43669124 : expr_hash_elt **slot;
241 :
242 43669124 : slot = m_avail_exprs->find_slot_with_hash (element, element->hash (), INSERT);
243 43669124 : if (*slot == NULL)
244 : {
245 43304455 : *slot = element;
246 43304455 : record_expr (element, NULL, '1');
247 : }
248 : else
249 364669 : delete element;
250 43669124 : }
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 58937664 : add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
264 : {
265 58937664 : hash one, two;
266 :
267 58937664 : inchash::add_expr (t1, one);
268 58937664 : inchash::add_expr (t2, two);
269 58937664 : hstate.add_commutative (one, two);
270 58937664 : }
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 125013375 : add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
280 : {
281 125013375 : switch (expr->kind)
282 : {
283 22188810 : case EXPR_SINGLE:
284 22188810 : inchash::add_expr (expr->ops.single.rhs, hstate);
285 22188810 : break;
286 :
287 8294365 : case EXPR_UNARY:
288 8294365 : 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 8294365 : if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
295 976209 : || expr->ops.unary.op == NON_LVALUE_EXPR)
296 7318156 : hstate.add_int (TYPE_UNSIGNED (expr->type));
297 :
298 8294365 : inchash::add_expr (expr->ops.unary.opnd, hstate);
299 8294365 : break;
300 :
301 82242529 : case EXPR_BINARY:
302 82242529 : hstate.add_object (expr->ops.binary.op);
303 82242529 : if (commutative_tree_code (expr->ops.binary.op))
304 58936887 : inchash::add_expr_commutative (expr->ops.binary.opnd0,
305 58936887 : expr->ops.binary.opnd1, hstate);
306 : else
307 : {
308 23305642 : inchash::add_expr (expr->ops.binary.opnd0, hstate);
309 23305642 : inchash::add_expr (expr->ops.binary.opnd1, hstate);
310 : }
311 : break;
312 :
313 232038 : case EXPR_TERNARY:
314 232038 : hstate.add_object (expr->ops.ternary.op);
315 232038 : 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 231261 : inchash::add_expr (expr->ops.ternary.opnd0, hstate);
321 231261 : inchash::add_expr (expr->ops.ternary.opnd1, hstate);
322 : }
323 232038 : inchash::add_expr (expr->ops.ternary.opnd2, hstate);
324 232038 : break;
325 :
326 3077901 : case EXPR_CALL:
327 3077901 : {
328 3077901 : size_t i;
329 3077901 : enum tree_code code = CALL_EXPR;
330 3077901 : gcall *fn_from;
331 :
332 3077901 : hstate.add_object (code);
333 3077901 : fn_from = expr->ops.call.fn_from;
334 3077901 : if (gimple_call_internal_p (fn_from))
335 272282 : hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
336 : else
337 2805619 : inchash::add_expr (gimple_call_fn (fn_from), hstate);
338 9065813 : for (i = 0; i < expr->ops.call.nargs; i++)
339 5987912 : inchash::add_expr (expr->ops.call.args[i], hstate);
340 : }
341 3077901 : break;
342 :
343 : case EXPR_PHI:
344 : {
345 : size_t i;
346 :
347 31984754 : for (i = 0; i < expr->ops.phi.nargs; i++)
348 23007022 : inchash::add_expr (expr->ops.phi.args[i], hstate);
349 : }
350 : break;
351 :
352 0 : default:
353 0 : gcc_unreachable ();
354 : }
355 125013375 : }
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 165288175 : avail_expr_hash (class expr_hash_elt *p)
364 : {
365 165288175 : const struct hashable_expr *expr = p->expr ();
366 165288175 : inchash::hash hstate;
367 :
368 165288175 : if (expr->kind == EXPR_SINGLE)
369 : {
370 : /* T could potentially be a switch index or a goto dest. */
371 62463610 : tree t = expr->ops.single.rhs;
372 62463610 : 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 41603094 : bool reverse;
378 41603094 : poly_int64 offset, size, max_size;
379 41603094 : 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 41603094 : if (known_size_p (max_size)
384 41603094 : && known_eq (size, max_size))
385 : {
386 40274800 : enum tree_code code = MEM_REF;
387 40274800 : hstate.add_object (code);
388 40274800 : inchash::add_expr (base, hstate,
389 40274800 : TREE_CODE (base) == MEM_REF
390 : ? OEP_ADDRESS_OF : 0);
391 40274800 : hstate.add_object (offset);
392 40274800 : hstate.add_object (size);
393 40274800 : return hstate.end ();
394 : }
395 : }
396 : }
397 :
398 125013375 : inchash::add_hashable_expr (expr, hstate);
399 :
400 125013375 : 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 9168618 : equal_mem_array_ref_p (tree t0, tree t1)
411 : {
412 9168618 : if (TREE_CODE (t0) != MEM_REF && ! handled_component_p (t0))
413 : return false;
414 7851624 : if (TREE_CODE (t1) != MEM_REF && ! handled_component_p (t1))
415 : return false;
416 :
417 7851624 : if (!types_compatible_p (TREE_TYPE (t0), TREE_TYPE (t1)))
418 : return false;
419 7847740 : bool rev0;
420 7847740 : poly_int64 off0, sz0, max0;
421 7847740 : tree base0 = get_ref_base_and_extent (t0, &off0, &sz0, &max0, &rev0);
422 7847740 : if (!known_size_p (max0)
423 7847740 : || maybe_ne (sz0, max0))
424 : return false;
425 :
426 7717121 : bool rev1;
427 7717121 : poly_int64 off1, sz1, max1;
428 7717121 : tree base1 = get_ref_base_and_extent (t1, &off1, &sz1, &max1, &rev1);
429 7717121 : if (!known_size_p (max1)
430 7717121 : || maybe_ne (sz1, max1))
431 : return false;
432 :
433 7717121 : if (rev0 != rev1 || maybe_ne (sz0, sz1) || maybe_ne (off0, off1))
434 : return false;
435 :
436 7717121 : return operand_equal_p (base0, base1,
437 7717121 : (TREE_CODE (base0) == MEM_REF
438 7717121 : || TREE_CODE (base0) == TARGET_MEM_REF)
439 2740264 : && (TREE_CODE (base1) == MEM_REF
440 2740264 : || TREE_CODE (base1) == TARGET_MEM_REF)
441 7717121 : ? 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 10615968 : hashable_expr_equal_p (const struct hashable_expr *expr0,
451 : const struct hashable_expr *expr1)
452 : {
453 10615968 : tree type0 = expr0->type;
454 10615968 : tree type1 = expr1->type;
455 :
456 : /* If either type is NULL, there is nothing to check. */
457 10615968 : 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 10615968 : if (type0 != type1
463 10615968 : && (TREE_CODE (type0) == ERROR_MARK
464 1429673 : || TREE_CODE (type1) == ERROR_MARK
465 1429673 : || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
466 1366328 : || element_precision (type0) != element_precision (type1)
467 1242809 : || TYPE_MODE (type0) != TYPE_MODE (type1)))
468 : return false;
469 :
470 10348493 : if (expr0->kind != expr1->kind)
471 : return false;
472 :
473 10348493 : switch (expr0->kind)
474 : {
475 9168618 : case EXPR_SINGLE:
476 9168618 : return equal_mem_array_ref_p (expr0->ops.single.rhs,
477 9168618 : expr1->ops.single.rhs)
478 10623091 : || operand_equal_p (expr0->ops.single.rhs,
479 1454473 : expr1->ops.single.rhs, 0);
480 212105 : case EXPR_UNARY:
481 212105 : if (expr0->ops.unary.op != expr1->ops.unary.op)
482 : return false;
483 :
484 15918 : if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
485 15918 : || expr0->ops.unary.op == NON_LVALUE_EXPR)
486 212105 : && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
487 : return false;
488 :
489 212105 : return operand_equal_p (expr0->ops.unary.opnd,
490 212105 : expr1->ops.unary.opnd, 0);
491 :
492 809314 : case EXPR_BINARY:
493 809314 : if (expr0->ops.binary.op != expr1->ops.binary.op)
494 : return false;
495 :
496 809308 : if (operand_equal_p (expr0->ops.binary.opnd0,
497 809308 : expr1->ops.binary.opnd0, 0)
498 1604795 : && operand_equal_p (expr0->ops.binary.opnd1,
499 795487 : expr1->ops.binary.opnd1, 0))
500 : return true;
501 :
502 : /* For commutative ops, allow the other order. */
503 15704 : return (commutative_tree_code (expr0->ops.binary.op)
504 14070 : && operand_equal_p (expr0->ops.binary.opnd0,
505 14070 : expr1->ops.binary.opnd1, 0)
506 21041 : && operand_equal_p (expr0->ops.binary.opnd1,
507 5337 : 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 130154 : case EXPR_CALL:
538 130154 : {
539 130154 : size_t i;
540 :
541 : /* If the calls are to different functions, then they
542 : clearly cannot be equal. */
543 130154 : if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
544 130154 : expr1->ops.call.fn_from))
545 : return false;
546 :
547 129533 : if (! expr0->ops.call.pure)
548 : return false;
549 :
550 129533 : if (expr0->ops.call.nargs != expr1->ops.call.nargs)
551 : return false;
552 :
553 373774 : for (i = 0; i < expr0->ops.call.nargs; i++)
554 244283 : if (! operand_equal_p (expr0->ops.call.args[i],
555 244283 : expr1->ops.call.args[i], 0))
556 : return false;
557 :
558 129491 : 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 27389 : case EXPR_PHI:
570 27389 : {
571 27389 : size_t i;
572 :
573 27389 : if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
574 : return false;
575 :
576 67855 : for (i = 0; i < expr0->ops.phi.nargs; i++)
577 40528 : if (! operand_equal_p (expr0->ops.phi.args[i],
578 40528 : 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 121619051 : expr_hash_elt::expr_hash_elt (gimple *stmt, tree orig_lhs)
592 : {
593 121619051 : enum gimple_code code = gimple_code (stmt);
594 121619051 : struct hashable_expr *expr = this->expr ();
595 :
596 121619051 : if (code == GIMPLE_ASSIGN)
597 : {
598 91412330 : enum tree_code subcode = gimple_assign_rhs_code (stmt);
599 :
600 91412330 : switch (get_gimple_rhs_class (subcode))
601 : {
602 62395773 : case GIMPLE_SINGLE_RHS:
603 62395773 : expr->kind = EXPR_SINGLE;
604 62395773 : expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
605 62395773 : expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
606 62395773 : break;
607 8164733 : case GIMPLE_UNARY_RHS:
608 8164733 : expr->kind = EXPR_UNARY;
609 8164733 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
610 8164733 : if (CONVERT_EXPR_CODE_P (subcode))
611 7318156 : subcode = NOP_EXPR;
612 8164733 : expr->ops.unary.op = subcode;
613 8164733 : expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
614 8164733 : break;
615 20619786 : case GIMPLE_BINARY_RHS:
616 20619786 : expr->kind = EXPR_BINARY;
617 20619786 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
618 20619786 : expr->ops.binary.op = subcode;
619 20619786 : expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
620 20619786 : expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
621 20619786 : break;
622 232038 : case GIMPLE_TERNARY_RHS:
623 232038 : expr->kind = EXPR_TERNARY;
624 232038 : expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
625 232038 : expr->ops.ternary.op = subcode;
626 232038 : expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
627 232038 : expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
628 232038 : expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
629 232038 : break;
630 0 : default:
631 0 : gcc_unreachable ();
632 : }
633 : }
634 : else if (code == GIMPLE_COND)
635 : {
636 18083251 : expr->type = boolean_type_node;
637 18083251 : expr->kind = EXPR_BINARY;
638 18083251 : expr->ops.binary.op = gimple_cond_code (stmt);
639 18083251 : expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
640 18083251 : expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
641 : }
642 3077901 : else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
643 : {
644 3077901 : size_t nargs = gimple_call_num_args (call_stmt);
645 3077901 : size_t i;
646 :
647 3077901 : gcc_assert (gimple_call_lhs (call_stmt));
648 :
649 3077901 : expr->type = TREE_TYPE (gimple_call_lhs (call_stmt));
650 3077901 : expr->kind = EXPR_CALL;
651 3077901 : expr->ops.call.fn_from = call_stmt;
652 :
653 3077901 : if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE))
654 : expr->ops.call.pure = true;
655 : else
656 1496358 : expr->ops.call.pure = false;
657 :
658 3077901 : expr->ops.call.nargs = nargs;
659 3077901 : expr->ops.call.args = XCNEWVEC (tree, nargs);
660 9065813 : for (i = 0; i < nargs; i++)
661 5987912 : expr->ops.call.args[i] = gimple_call_arg (call_stmt, i);
662 : }
663 67593 : else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
664 : {
665 67593 : expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt));
666 67593 : expr->kind = EXPR_SINGLE;
667 67593 : expr->ops.single.rhs = gimple_switch_index (swtch_stmt);
668 : }
669 : else if (code == GIMPLE_GOTO)
670 : {
671 244 : expr->type = TREE_TYPE (gimple_goto_dest (stmt));
672 244 : expr->kind = EXPR_SINGLE;
673 244 : expr->ops.single.rhs = gimple_goto_dest (stmt);
674 : }
675 : else if (code == GIMPLE_PHI)
676 : {
677 8977732 : size_t nargs = gimple_phi_num_args (stmt);
678 8977732 : size_t i;
679 :
680 8977732 : expr->type = TREE_TYPE (gimple_phi_result (stmt));
681 8977732 : expr->kind = EXPR_PHI;
682 8977732 : expr->ops.phi.nargs = nargs;
683 8977732 : expr->ops.phi.args = XCNEWVEC (tree, nargs);
684 31984754 : for (i = 0; i < nargs; i++)
685 23007022 : expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
686 : }
687 : else
688 0 : gcc_unreachable ();
689 :
690 121619051 : m_lhs = orig_lhs;
691 121619051 : m_vop = gimple_vuse (stmt);
692 121619051 : m_hash = avail_expr_hash (this);
693 121619051 : m_stamp = this;
694 121619051 : }
695 :
696 : /* Given a hashable_expr expression ORIG and an ORIG_LHS,
697 : construct a hash table element. */
698 :
699 43669124 : expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs)
700 : {
701 43669124 : m_expr = *orig;
702 43669124 : m_lhs = orig_lhs;
703 43669124 : m_vop = NULL_TREE;
704 43669124 : m_hash = avail_expr_hash (this);
705 43669124 : m_stamp = this;
706 43669124 : }
707 :
708 : /* Copy constructor for a hash table element. */
709 :
710 51068396 : expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt)
711 : {
712 51068396 : m_expr = old_elt.m_expr;
713 51068396 : m_lhs = old_elt.m_lhs;
714 51068396 : m_vop = old_elt.m_vop;
715 51068396 : m_hash = old_elt.m_hash;
716 51068396 : m_stamp = this;
717 :
718 : /* Now deep copy the malloc'd space for CALL and PHI args. */
719 51068396 : if (old_elt.m_expr.kind == EXPR_CALL)
720 : {
721 1201679 : size_t nargs = old_elt.m_expr.ops.call.nargs;
722 1201679 : size_t i;
723 :
724 1201679 : m_expr.ops.call.args = XCNEWVEC (tree, nargs);
725 3827252 : for (i = 0; i < nargs; i++)
726 2625573 : m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i];
727 : }
728 49866717 : else if (old_elt.m_expr.kind == EXPR_PHI)
729 : {
730 8945384 : size_t nargs = old_elt.m_expr.ops.phi.nargs;
731 8945384 : size_t i;
732 :
733 8945384 : m_expr.ops.phi.args = XCNEWVEC (tree, nargs);
734 31891515 : for (i = 0; i < nargs; i++)
735 22946131 : m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i];
736 : }
737 51068396 : }
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 216356571 : expr_hash_elt::~expr_hash_elt ()
743 : {
744 216356571 : if (m_expr.kind == EXPR_CALL)
745 4279580 : free (m_expr.ops.call.args);
746 212076991 : else if (m_expr.kind == EXPR_PHI)
747 17923116 : free (m_expr.ops.phi.args);
748 216356571 : }
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 54672034 : const_and_copies::pop_to_marker (void)
845 : {
846 93406775 : while (m_stack.length () > 0)
847 : {
848 93406775 : tree prev_value, dest;
849 :
850 93406775 : 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 93406775 : if (dest == NULL)
855 : break;
856 :
857 38734741 : 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 38734741 : prev_value = m_stack.pop ();
867 38734741 : set_ssa_name_value (dest, prev_value);
868 : }
869 54672034 : }
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 38734741 : const_and_copies::record_const_or_copy_raw (tree x, tree y, tree prev_x)
877 : {
878 38734741 : 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 38734741 : set_ssa_name_value (x, y);
888 38734741 : m_stack.reserve (2);
889 38734741 : m_stack.quick_push (prev_x);
890 38734741 : m_stack.quick_push (x);
891 38734741 : }
892 :
893 : /* Record that X has the value Y. */
894 :
895 : void
896 25089470 : const_and_copies::record_const_or_copy (tree x, tree y)
897 : {
898 25089470 : record_const_or_copy (x, y, SSA_NAME_VALUE (x));
899 25089470 : }
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 38734741 : 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 38734741 : if (y && TREE_CODE (y) == SSA_NAME)
910 : {
911 16934841 : tree tmp = SSA_NAME_VALUE (y);
912 15372363 : y = tmp ? tmp : y;
913 : }
914 :
915 38734741 : record_const_or_copy_raw (x, y, prev_x);
916 38734741 : }
917 :
918 : bool
919 200043959 : expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
920 : {
921 200043959 : const struct hashable_expr *expr1 = p1->expr ();
922 200043959 : const class expr_hash_elt *stamp1 = p1->stamp ();
923 200043959 : const struct hashable_expr *expr2 = p2->expr ();
924 200043959 : const class expr_hash_elt *stamp2 = p2->stamp ();
925 :
926 : /* This case should apply only when removing entries from the table. */
927 200043959 : if (stamp1 == stamp2)
928 : return true;
929 :
930 105671108 : 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 10615968 : if (hashable_expr_equal_p (expr1, expr2)
936 10615968 : && 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 66241316 : initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
949 : {
950 66241316 : expr->type = boolean_type_node;
951 :
952 66241316 : if (COMPARISON_CLASS_P (cond))
953 : {
954 66023331 : expr->kind = EXPR_BINARY;
955 66023331 : expr->ops.binary.op = TREE_CODE (cond);
956 66023331 : expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
957 66023331 : expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
958 : }
959 217985 : else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
960 : {
961 217985 : expr->kind = EXPR_UNARY;
962 217985 : expr->ops.unary.op = TRUTH_NOT_EXPR;
963 217985 : expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
964 : }
965 : else
966 0 : gcc_unreachable ();
967 66241316 : }
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 33383616 : record_conditions (vec<cond_equivalence> *p, tree cond, tree inverted)
977 : {
978 33383616 : cond_equivalence c;
979 :
980 33383616 : if (!COMPARISON_CLASS_P (cond))
981 : return;
982 :
983 : /* Now store the original true and false conditions into the first
984 : two slots. */
985 33120658 : initialize_expr_from_cond (cond, &c.cond);
986 33120658 : c.value = boolean_true_node;
987 33120658 : 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 33120658 : initialize_expr_from_cond (inverted, &c.cond);
995 33120658 : c.value = boolean_false_node;
996 33120658 : p->safe_push (c);
997 : }
|