1 /* Header file for SSA dominator optimizations.
2 Copyright (C) 2013-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
24 #include "basic-block.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"
34 #include "internal-fn.h"
39 static bool hashable_expr_equal_p (const struct hashable_expr
*,
40 const struct hashable_expr
*);
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. */
46 /* Pop items off the unwinding stack, removing each from the hash table
47 until a marker is encountered. */
50 avail_exprs_stack::pop_to_marker ()
52 /* Remove all the expressions made available in this block. */
53 while (m_stack
.length () > 0)
55 std::pair
<expr_hash_elt_t
, expr_hash_elt_t
> victim
= m_stack
.pop ();
58 if (victim
.first
== NULL
)
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
))
66 fprintf (dump_file
, "<<<< ");
67 victim
.first
->print (dump_file
);
70 slot
= m_avail_exprs
->find_slot (victim
.first
, NO_INSERT
);
71 gcc_assert (slot
&& *slot
== victim
.first
);
72 if (victim
.second
!= NULL
)
75 *slot
= victim
.second
;
78 m_avail_exprs
->clear_slot (slot
);
82 /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
83 from the hash table. */
86 avail_exprs_stack::record_expr (class expr_hash_elt
*elt1
,
87 class expr_hash_elt
*elt2
,
90 if (elt1
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
92 fprintf (dump_file
, "%c>>> ", type
);
93 elt1
->print (dump_file
);
96 m_stack
.safe_push (std::pair
<expr_hash_elt_t
, expr_hash_elt_t
> (elt1
, elt2
));
99 /* Helper for walk_non_aliased_vuses. Determine if we arrived at
100 the desired memory state. */
103 vuse_eq (ao_ref
*, tree vuse1
, void *data
)
105 tree vuse2
= (tree
) data
;
112 /* We looked for STMT in the hash table, but did not find it.
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. */
119 avail_exprs_stack::simplify_binary_operation (gimple
*stmt
,
120 class expr_hash_elt element
)
122 if (is_gimple_assign (stmt
))
124 struct hashable_expr
*expr
= element
.expr ();
125 if (expr
->kind
== EXPR_BINARY
)
127 enum tree_code code
= expr
->ops
.binary
.op
;
131 /* For these cases, if we know the operands
132 are equal, then we know the result. */
149 /* Build a simple equality expr and query the hash table
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
);
159 = m_avail_exprs
->find_slot (&element2
, NO_INSERT
);
160 tree result_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
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 ()))
176 return gimple_assign_rhs1 (stmt
);
179 /* This is unsafe for certain floats even in non-IEEE
180 formats. In IEEE, it is unsafe because it does
182 if (FLOAT_TYPE_P (result_type
)
183 && HONOR_NANS (result_type
))
191 return build_zero_cst (result_type
);
198 /* Avoid _Fract types where we can't build 1. */
199 if (ALL_FRACT_MODE_P (TYPE_MODE (result_type
)))
201 return build_one_cst (result_type
);
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
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. */
227 avail_exprs_stack::lookup_avail_expr (gimple
*stmt
, bool insert
, bool tbaa_p
)
229 expr_hash_elt
**slot
;
232 /* Get LHS of phi, assignment, or call; else NULL_TREE. */
233 if (gimple_code (stmt
) == GIMPLE_PHI
)
234 lhs
= gimple_phi_result (stmt
);
236 lhs
= gimple_get_lhs (stmt
);
238 class expr_hash_elt
element (stmt
, lhs
);
240 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
242 fprintf (dump_file
, "LKUP ");
243 element
.print (dump_file
);
246 /* Don't bother remembering constant assignments and copy operations.
247 Constants and copy operations are handled by the constant/copy propagator
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
)))
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
));
260 else if (*slot
== NULL
)
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
,
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
272 An uninitialized or empty slot is an indication no prior objects
273 entered into the hash table had a hash collection with ELEMENT.
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
);
280 record_expr (element2
, NULL
, '2');
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 ())
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. */
295 unsigned limit
= PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
);
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
, vuse_eq
, NULL
, NULL
,
302 limit
, vuse1
) != NULL
))
306 class expr_hash_elt
*element2
= new expr_hash_elt (element
);
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');
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 ();
322 /* Valueize the result. */
323 if (TREE_CODE (lhs
) == SSA_NAME
)
325 tree tem
= SSA_NAME_VALUE (lhs
);
330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
332 fprintf (dump_file
, "FIND: ");
333 print_generic_expr (dump_file
, lhs
);
334 fprintf (dump_file
, "\n");
340 /* Enter condition equivalence P into the hash table.
342 This indicates that a conditional expression has a known
346 avail_exprs_stack::record_cond (cond_equivalence
*p
)
348 class expr_hash_elt
*element
= new expr_hash_elt (&p
->cond
, p
->value
);
349 expr_hash_elt
**slot
;
351 slot
= m_avail_exprs
->find_slot_with_hash (element
, element
->hash (), INSERT
);
355 record_expr (element
, NULL
, '1');
361 /* Generate a hash value for a pair of expressions. This can be used
362 iteratively by passing a previous result in HSTATE.
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. */
372 add_expr_commutative (const_tree t1
, const_tree t2
, hash
&hstate
)
376 inchash::add_expr (t1
, one
);
377 inchash::add_expr (t2
, two
);
378 hstate
.add_commutative (one
, two
);
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. */
388 add_hashable_expr (const struct hashable_expr
*expr
, hash
&hstate
)
393 inchash::add_expr (expr
->ops
.single
.rhs
, hstate
);
397 hstate
.add_object (expr
->ops
.unary
.op
);
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
));
407 inchash::add_expr (expr
->ops
.unary
.opnd
, hstate
);
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
);
417 inchash::add_expr (expr
->ops
.binary
.opnd0
, hstate
);
418 inchash::add_expr (expr
->ops
.binary
.opnd1
, hstate
);
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
);
429 inchash::add_expr (expr
->ops
.ternary
.opnd0
, hstate
);
430 inchash::add_expr (expr
->ops
.ternary
.opnd1
, hstate
);
432 inchash::add_expr (expr
->ops
.ternary
.opnd2
, hstate
);
438 enum tree_code code
= CALL_EXPR
;
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
));
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
);
456 for (i
= 0; i
< expr
->ops
.phi
.nargs
; i
++)
457 inchash::add_expr (expr
->ops
.phi
.args
[i
], hstate
);
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. */
472 avail_expr_hash (class expr_hash_elt
*p
)
474 const struct hashable_expr
*expr
= p
->expr ();
475 inchash::hash hstate
;
477 if (expr
->kind
== EXPR_SINGLE
)
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
))
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. */
487 poly_int64 offset
, size
, max_size
;
488 tree base
= get_ref_base_and_extent (t
, &offset
, &size
, &max_size
,
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
))
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 ();
505 inchash::add_hashable_expr (expr
, hstate
);
507 return hstate
.end ();
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.)
513 Return TRUE if the two are so equivalent; FALSE if not (which could still
514 mean the two are equivalent by other means). */
517 equal_mem_array_ref_p (tree t0
, tree t1
)
519 if (TREE_CODE (t0
) != MEM_REF
&& ! handled_component_p (t0
))
521 if (TREE_CODE (t1
) != MEM_REF
&& ! handled_component_p (t1
))
524 if (!types_compatible_p (TREE_TYPE (t0
), TREE_TYPE (t1
)))
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
))
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
))
543 /* Types were compatible, so this is a sanity check. */
544 gcc_assert (known_eq (sz0
, sz1
));
546 return known_eq (off0
, off1
) && operand_equal_p (base0
, base1
, 0);
549 /* Compare two hashable_expr structures for equivalence. They are
550 considered equivalent when the expressions they denote must
551 necessarily be equal. The logic is intended to follow that of
552 operand_equal_p in fold-const.c */
555 hashable_expr_equal_p (const struct hashable_expr
*expr0
,
556 const struct hashable_expr
*expr1
)
558 tree type0
= expr0
->type
;
559 tree type1
= expr1
->type
;
561 /* If either type is NULL, there is nothing to check. */
562 if ((type0
== NULL_TREE
) ^ (type1
== NULL_TREE
))
565 /* If both types don't have the same signedness, precision, and mode,
566 then we can't consider them equal. */
568 && (TREE_CODE (type0
) == ERROR_MARK
569 || TREE_CODE (type1
) == ERROR_MARK
570 || TYPE_UNSIGNED (type0
) != TYPE_UNSIGNED (type1
)
571 || TYPE_PRECISION (type0
) != TYPE_PRECISION (type1
)
572 || TYPE_MODE (type0
) != TYPE_MODE (type1
)))
575 if (expr0
->kind
!= expr1
->kind
)
581 return equal_mem_array_ref_p (expr0
->ops
.single
.rhs
,
582 expr1
->ops
.single
.rhs
)
583 || operand_equal_p (expr0
->ops
.single
.rhs
,
584 expr1
->ops
.single
.rhs
, 0);
586 if (expr0
->ops
.unary
.op
!= expr1
->ops
.unary
.op
)
589 if ((CONVERT_EXPR_CODE_P (expr0
->ops
.unary
.op
)
590 || expr0
->ops
.unary
.op
== NON_LVALUE_EXPR
)
591 && TYPE_UNSIGNED (expr0
->type
) != TYPE_UNSIGNED (expr1
->type
))
594 return operand_equal_p (expr0
->ops
.unary
.opnd
,
595 expr1
->ops
.unary
.opnd
, 0);
598 if (expr0
->ops
.binary
.op
!= expr1
->ops
.binary
.op
)
601 if (operand_equal_p (expr0
->ops
.binary
.opnd0
,
602 expr1
->ops
.binary
.opnd0
, 0)
603 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
604 expr1
->ops
.binary
.opnd1
, 0))
607 /* For commutative ops, allow the other order. */
608 return (commutative_tree_code (expr0
->ops
.binary
.op
)
609 && operand_equal_p (expr0
->ops
.binary
.opnd0
,
610 expr1
->ops
.binary
.opnd1
, 0)
611 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
612 expr1
->ops
.binary
.opnd0
, 0));
615 if (expr0
->ops
.ternary
.op
!= expr1
->ops
.ternary
.op
616 || !operand_equal_p (expr0
->ops
.ternary
.opnd2
,
617 expr1
->ops
.ternary
.opnd2
, 0))
620 /* BIT_INSERT_EXPR has an implict operand as the type precision
621 of op1. Need to check to make sure they are the same. */
622 if (expr0
->ops
.ternary
.op
== BIT_INSERT_EXPR
623 && TREE_CODE (expr0
->ops
.ternary
.opnd1
) == INTEGER_CST
624 && TREE_CODE (expr1
->ops
.ternary
.opnd1
) == INTEGER_CST
625 && TYPE_PRECISION (TREE_TYPE (expr0
->ops
.ternary
.opnd1
))
626 != TYPE_PRECISION (TREE_TYPE (expr1
->ops
.ternary
.opnd1
)))
629 if (operand_equal_p (expr0
->ops
.ternary
.opnd0
,
630 expr1
->ops
.ternary
.opnd0
, 0)
631 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
632 expr1
->ops
.ternary
.opnd1
, 0))
635 /* For commutative ops, allow the other order. */
636 return (commutative_ternary_tree_code (expr0
->ops
.ternary
.op
)
637 && operand_equal_p (expr0
->ops
.ternary
.opnd0
,
638 expr1
->ops
.ternary
.opnd1
, 0)
639 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
640 expr1
->ops
.ternary
.opnd0
, 0));
646 /* If the calls are to different functions, then they
647 clearly cannot be equal. */
648 if (!gimple_call_same_target_p (expr0
->ops
.call
.fn_from
,
649 expr1
->ops
.call
.fn_from
))
652 if (! expr0
->ops
.call
.pure
)
655 if (expr0
->ops
.call
.nargs
!= expr1
->ops
.call
.nargs
)
658 for (i
= 0; i
< expr0
->ops
.call
.nargs
; i
++)
659 if (! operand_equal_p (expr0
->ops
.call
.args
[i
],
660 expr1
->ops
.call
.args
[i
], 0))
663 if (stmt_could_throw_p (cfun
, expr0
->ops
.call
.fn_from
))
665 int lp0
= lookup_stmt_eh_lp (expr0
->ops
.call
.fn_from
);
666 int lp1
= lookup_stmt_eh_lp (expr1
->ops
.call
.fn_from
);
667 if ((lp0
> 0 || lp1
> 0) && lp0
!= lp1
)
678 if (expr0
->ops
.phi
.nargs
!= expr1
->ops
.phi
.nargs
)
681 for (i
= 0; i
< expr0
->ops
.phi
.nargs
; i
++)
682 if (! operand_equal_p (expr0
->ops
.phi
.args
[i
],
683 expr1
->ops
.phi
.args
[i
], 0))
694 /* Given a statement STMT, construct a hash table element. */
696 expr_hash_elt::expr_hash_elt (gimple
*stmt
, tree orig_lhs
)
698 enum gimple_code code
= gimple_code (stmt
);
699 struct hashable_expr
*expr
= this->expr ();
701 if (code
== GIMPLE_ASSIGN
)
703 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
705 switch (get_gimple_rhs_class (subcode
))
707 case GIMPLE_SINGLE_RHS
:
708 expr
->kind
= EXPR_SINGLE
;
709 expr
->type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
710 expr
->ops
.single
.rhs
= gimple_assign_rhs1 (stmt
);
712 case GIMPLE_UNARY_RHS
:
713 expr
->kind
= EXPR_UNARY
;
714 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
715 if (CONVERT_EXPR_CODE_P (subcode
))
717 expr
->ops
.unary
.op
= subcode
;
718 expr
->ops
.unary
.opnd
= gimple_assign_rhs1 (stmt
);
720 case GIMPLE_BINARY_RHS
:
721 expr
->kind
= EXPR_BINARY
;
722 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
723 expr
->ops
.binary
.op
= subcode
;
724 expr
->ops
.binary
.opnd0
= gimple_assign_rhs1 (stmt
);
725 expr
->ops
.binary
.opnd1
= gimple_assign_rhs2 (stmt
);
727 case GIMPLE_TERNARY_RHS
:
728 expr
->kind
= EXPR_TERNARY
;
729 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
730 expr
->ops
.ternary
.op
= subcode
;
731 expr
->ops
.ternary
.opnd0
= gimple_assign_rhs1 (stmt
);
732 expr
->ops
.ternary
.opnd1
= gimple_assign_rhs2 (stmt
);
733 expr
->ops
.ternary
.opnd2
= gimple_assign_rhs3 (stmt
);
739 else if (code
== GIMPLE_COND
)
741 expr
->type
= boolean_type_node
;
742 expr
->kind
= EXPR_BINARY
;
743 expr
->ops
.binary
.op
= gimple_cond_code (stmt
);
744 expr
->ops
.binary
.opnd0
= gimple_cond_lhs (stmt
);
745 expr
->ops
.binary
.opnd1
= gimple_cond_rhs (stmt
);
747 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
749 size_t nargs
= gimple_call_num_args (call_stmt
);
752 gcc_assert (gimple_call_lhs (call_stmt
));
754 expr
->type
= TREE_TYPE (gimple_call_lhs (call_stmt
));
755 expr
->kind
= EXPR_CALL
;
756 expr
->ops
.call
.fn_from
= call_stmt
;
758 if (gimple_call_flags (call_stmt
) & (ECF_CONST
| ECF_PURE
))
759 expr
->ops
.call
.pure
= true;
761 expr
->ops
.call
.pure
= false;
763 expr
->ops
.call
.nargs
= nargs
;
764 expr
->ops
.call
.args
= XCNEWVEC (tree
, nargs
);
765 for (i
= 0; i
< nargs
; i
++)
766 expr
->ops
.call
.args
[i
] = gimple_call_arg (call_stmt
, i
);
768 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
770 expr
->type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
771 expr
->kind
= EXPR_SINGLE
;
772 expr
->ops
.single
.rhs
= gimple_switch_index (swtch_stmt
);
774 else if (code
== GIMPLE_GOTO
)
776 expr
->type
= TREE_TYPE (gimple_goto_dest (stmt
));
777 expr
->kind
= EXPR_SINGLE
;
778 expr
->ops
.single
.rhs
= gimple_goto_dest (stmt
);
780 else if (code
== GIMPLE_PHI
)
782 size_t nargs
= gimple_phi_num_args (stmt
);
785 expr
->type
= TREE_TYPE (gimple_phi_result (stmt
));
786 expr
->kind
= EXPR_PHI
;
787 expr
->ops
.phi
.nargs
= nargs
;
788 expr
->ops
.phi
.args
= XCNEWVEC (tree
, nargs
);
789 for (i
= 0; i
< nargs
; i
++)
790 expr
->ops
.phi
.args
[i
] = gimple_phi_arg_def (stmt
, i
);
796 m_vop
= gimple_vuse (stmt
);
797 m_hash
= avail_expr_hash (this);
801 /* Given a hashable_expr expression ORIG and an ORIG_LHS,
802 construct a hash table element. */
804 expr_hash_elt::expr_hash_elt (struct hashable_expr
*orig
, tree orig_lhs
)
809 m_hash
= avail_expr_hash (this);
813 /* Copy constructor for a hash table element. */
815 expr_hash_elt::expr_hash_elt (class expr_hash_elt
&old_elt
)
817 m_expr
= old_elt
.m_expr
;
818 m_lhs
= old_elt
.m_lhs
;
819 m_vop
= old_elt
.m_vop
;
820 m_hash
= old_elt
.m_hash
;
823 /* Now deep copy the malloc'd space for CALL and PHI args. */
824 if (old_elt
.m_expr
.kind
== EXPR_CALL
)
826 size_t nargs
= old_elt
.m_expr
.ops
.call
.nargs
;
829 m_expr
.ops
.call
.args
= XCNEWVEC (tree
, nargs
);
830 for (i
= 0; i
< nargs
; i
++)
831 m_expr
.ops
.call
.args
[i
] = old_elt
.m_expr
.ops
.call
.args
[i
];
833 else if (old_elt
.m_expr
.kind
== EXPR_PHI
)
835 size_t nargs
= old_elt
.m_expr
.ops
.phi
.nargs
;
838 m_expr
.ops
.phi
.args
= XCNEWVEC (tree
, nargs
);
839 for (i
= 0; i
< nargs
; i
++)
840 m_expr
.ops
.phi
.args
[i
] = old_elt
.m_expr
.ops
.phi
.args
[i
];
844 /* Calls and PHIs have a variable number of arguments that are allocated
845 on the heap. Thus we have to have a special dtor to release them. */
847 expr_hash_elt::~expr_hash_elt ()
849 if (m_expr
.kind
== EXPR_CALL
)
850 free (m_expr
.ops
.call
.args
);
851 else if (m_expr
.kind
== EXPR_PHI
)
852 free (m_expr
.ops
.phi
.args
);
855 /* Print a diagnostic dump of an expression hash table entry. */
858 expr_hash_elt::print (FILE *stream
)
860 fprintf (stream
, "STMT ");
864 print_generic_expr (stream
, m_lhs
);
865 fprintf (stream
, " = ");
871 print_generic_expr (stream
, m_expr
.ops
.single
.rhs
);
875 fprintf (stream
, "%s ", get_tree_code_name (m_expr
.ops
.unary
.op
));
876 print_generic_expr (stream
, m_expr
.ops
.unary
.opnd
);
880 print_generic_expr (stream
, m_expr
.ops
.binary
.opnd0
);
881 fprintf (stream
, " %s ", get_tree_code_name (m_expr
.ops
.binary
.op
));
882 print_generic_expr (stream
, m_expr
.ops
.binary
.opnd1
);
886 fprintf (stream
, " %s <", get_tree_code_name (m_expr
.ops
.ternary
.op
));
887 print_generic_expr (stream
, m_expr
.ops
.ternary
.opnd0
);
888 fputs (", ", stream
);
889 print_generic_expr (stream
, m_expr
.ops
.ternary
.opnd1
);
890 fputs (", ", stream
);
891 print_generic_expr (stream
, m_expr
.ops
.ternary
.opnd2
);
898 size_t nargs
= m_expr
.ops
.call
.nargs
;
901 fn_from
= m_expr
.ops
.call
.fn_from
;
902 if (gimple_call_internal_p (fn_from
))
903 fprintf (stream
, ".%s",
904 internal_fn_name (gimple_call_internal_fn (fn_from
)));
906 print_generic_expr (stream
, gimple_call_fn (fn_from
));
907 fprintf (stream
, " (");
908 for (i
= 0; i
< nargs
; i
++)
910 print_generic_expr (stream
, m_expr
.ops
.call
.args
[i
]);
912 fprintf (stream
, ", ");
914 fprintf (stream
, ")");
921 size_t nargs
= m_expr
.ops
.phi
.nargs
;
923 fprintf (stream
, "PHI <");
924 for (i
= 0; i
< nargs
; i
++)
926 print_generic_expr (stream
, m_expr
.ops
.phi
.args
[i
]);
928 fprintf (stream
, ", ");
930 fprintf (stream
, ">");
937 fprintf (stream
, " with ");
938 print_generic_expr (stream
, m_vop
);
941 fprintf (stream
, "\n");
944 /* Pop entries off the stack until we hit the NULL marker.
945 For each entry popped, use the SRC/DEST pair to restore
946 SRC to its prior value. */
949 const_and_copies::pop_to_marker (void)
951 while (m_stack
.length () > 0)
953 tree prev_value
, dest
;
955 dest
= m_stack
.pop ();
957 /* A NULL value indicates we should stop unwinding, otherwise
958 pop off the next entry as they're recorded in pairs. */
962 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
964 fprintf (dump_file
, "<<<< COPY ");
965 print_generic_expr (dump_file
, dest
);
966 fprintf (dump_file
, " = ");
967 print_generic_expr (dump_file
, SSA_NAME_VALUE (dest
));
968 fprintf (dump_file
, "\n");
971 prev_value
= m_stack
.pop ();
972 set_ssa_name_value (dest
, prev_value
);
976 /* Record that X has the value Y and that X's previous value is PREV_X.
978 This variant does not follow the value chain for Y. */
981 const_and_copies::record_const_or_copy_raw (tree x
, tree y
, tree prev_x
)
983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
985 fprintf (dump_file
, "0>>> COPY ");
986 print_generic_expr (dump_file
, x
);
987 fprintf (dump_file
, " = ");
988 print_generic_expr (dump_file
, y
);
989 fprintf (dump_file
, "\n");
992 set_ssa_name_value (x
, y
);
994 m_stack
.quick_push (prev_x
);
995 m_stack
.quick_push (x
);
998 /* Record that X has the value Y. */
1001 const_and_copies::record_const_or_copy (tree x
, tree y
)
1003 record_const_or_copy (x
, y
, SSA_NAME_VALUE (x
));
1006 /* Record that X has the value Y and that X's previous value is PREV_X.
1008 This variant follow's Y value chain. */
1011 const_and_copies::record_const_or_copy (tree x
, tree y
, tree prev_x
)
1013 /* Y may be NULL if we are invalidating entries in the table. */
1014 if (y
&& TREE_CODE (y
) == SSA_NAME
)
1016 tree tmp
= SSA_NAME_VALUE (y
);
1020 record_const_or_copy_raw (x
, y
, prev_x
);
1024 expr_elt_hasher::equal (const value_type
&p1
, const compare_type
&p2
)
1026 const struct hashable_expr
*expr1
= p1
->expr ();
1027 const struct expr_hash_elt
*stamp1
= p1
->stamp ();
1028 const struct hashable_expr
*expr2
= p2
->expr ();
1029 const struct expr_hash_elt
*stamp2
= p2
->stamp ();
1031 /* This case should apply only when removing entries from the table. */
1032 if (stamp1
== stamp2
)
1035 if (p1
->hash () != p2
->hash ())
1038 /* In case of a collision, both RHS have to be identical and have the
1039 same VUSE operands. */
1040 if (hashable_expr_equal_p (expr1
, expr2
)
1041 && types_compatible_p (expr1
->type
, expr2
->type
))
1047 /* Given a conditional expression COND as a tree, initialize
1048 a hashable_expr expression EXPR. The conditional must be a
1049 comparison or logical negation. A constant or a variable is
1053 initialize_expr_from_cond (tree cond
, struct hashable_expr
*expr
)
1055 expr
->type
= boolean_type_node
;
1057 if (COMPARISON_CLASS_P (cond
))
1059 expr
->kind
= EXPR_BINARY
;
1060 expr
->ops
.binary
.op
= TREE_CODE (cond
);
1061 expr
->ops
.binary
.opnd0
= TREE_OPERAND (cond
, 0);
1062 expr
->ops
.binary
.opnd1
= TREE_OPERAND (cond
, 1);
1064 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1066 expr
->kind
= EXPR_UNARY
;
1067 expr
->ops
.unary
.op
= TRUTH_NOT_EXPR
;
1068 expr
->ops
.unary
.opnd
= TREE_OPERAND (cond
, 0);
1074 /* Build a cond_equivalence record indicating that the comparison
1075 CODE holds between operands OP0 and OP1 and push it to **P. */
1078 build_and_record_new_cond (enum tree_code code
,
1080 vec
<cond_equivalence
> *p
,
1084 struct hashable_expr
*cond
= &c
.cond
;
1086 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
1088 cond
->type
= boolean_type_node
;
1089 cond
->kind
= EXPR_BINARY
;
1090 cond
->ops
.binary
.op
= code
;
1091 cond
->ops
.binary
.opnd0
= op0
;
1092 cond
->ops
.binary
.opnd1
= op1
;
1094 c
.value
= val
? boolean_true_node
: boolean_false_node
;
1098 /* Record that COND is true and INVERTED is false into the edge information
1099 structure. Also record that any conditions dominated by COND are true
1102 For example, if a < b is true, then a <= b must also be true. */
1105 record_conditions (vec
<cond_equivalence
> *p
, tree cond
, tree inverted
)
1110 if (!COMPARISON_CLASS_P (cond
))
1113 op0
= TREE_OPERAND (cond
, 0);
1114 op1
= TREE_OPERAND (cond
, 1);
1116 switch (TREE_CODE (cond
))
1120 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1122 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
, p
);
1123 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
, p
);
1126 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
1127 ? LE_EXPR
: GE_EXPR
),
1129 build_and_record_new_cond (NE_EXPR
, op0
, op1
, p
);
1130 build_and_record_new_cond (EQ_EXPR
, op0
, op1
, p
, false);
1135 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1137 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
, p
);
1142 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1144 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
, p
);
1146 build_and_record_new_cond (LE_EXPR
, op0
, op1
, p
);
1147 build_and_record_new_cond (GE_EXPR
, op0
, op1
, p
);
1150 case UNORDERED_EXPR
:
1151 build_and_record_new_cond (NE_EXPR
, op0
, op1
, p
);
1152 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
, p
);
1153 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
, p
);
1154 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
, p
);
1155 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
, p
);
1156 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
, p
);
1161 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
1162 ? UNLE_EXPR
: UNGE_EXPR
),
1164 build_and_record_new_cond (NE_EXPR
, op0
, op1
, p
);
1168 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
, p
);
1169 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
, p
);
1173 build_and_record_new_cond (NE_EXPR
, op0
, op1
, p
);
1174 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
, p
);
1181 /* Now store the original true and false conditions into the first
1183 initialize_expr_from_cond (cond
, &c
.cond
);
1184 c
.value
= boolean_true_node
;
1187 /* It is possible for INVERTED to be the negation of a comparison,
1188 and not a valid RHS or GIMPLE_COND condition. This happens because
1189 invert_truthvalue may return such an expression when asked to invert
1190 a floating-point comparison. These comparisons are not assumed to
1191 obey the trichotomy law. */
1192 initialize_expr_from_cond (inverted
, &c
.cond
);
1193 c
.value
= boolean_false_node
;