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