1 /* Header file for SSA dominator optimizations.
2 Copyright (C) 2013-2015 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"
36 static bool hashable_expr_equal_p (const struct hashable_expr
*,
37 const struct hashable_expr
*);
39 /* Initialize local stacks for this optimizer and record equivalences
40 upon entry to BB. Equivalences can come from the edge traversed to
41 reach BB or they may come from PHI nodes at the start of BB. */
43 /* Pop items off the unwinding stack, removing each from the hash table
44 until a marker is encountered. */
47 avail_exprs_stack::pop_to_marker ()
49 /* Remove all the expressions made available in this block. */
50 while (m_stack
.length () > 0)
52 std::pair
<expr_hash_elt_t
, expr_hash_elt_t
> victim
= m_stack
.pop ();
55 if (victim
.first
== NULL
)
58 /* This must precede the actual removal from the hash table,
59 as ELEMENT and the table entry may share a call argument
60 vector which will be freed during removal. */
61 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
63 fprintf (dump_file
, "<<<< ");
64 victim
.first
->print (dump_file
);
67 slot
= m_avail_exprs
->find_slot (victim
.first
, NO_INSERT
);
68 gcc_assert (slot
&& *slot
== victim
.first
);
69 if (victim
.second
!= NULL
)
72 *slot
= victim
.second
;
75 m_avail_exprs
->clear_slot (slot
);
79 /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
80 from the hash table. */
83 avail_exprs_stack::record_expr (class expr_hash_elt
*elt1
,
84 class expr_hash_elt
*elt2
,
87 if (elt1
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
89 fprintf (dump_file
, "%c>>> ", type
);
90 elt1
->print (dump_file
);
93 m_stack
.safe_push (std::pair
<expr_hash_elt_t
, expr_hash_elt_t
> (elt1
, elt2
));
96 /* Generate a hash value for a pair of expressions. This can be used
97 iteratively by passing a previous result in HSTATE.
99 The same hash value is always returned for a given pair of expressions,
100 regardless of the order in which they are presented. This is useful in
101 hashing the operands of commutative functions. */
107 add_expr_commutative (const_tree t1
, const_tree t2
, hash
&hstate
)
111 inchash::add_expr (t1
, one
);
112 inchash::add_expr (t2
, two
);
113 hstate
.add_commutative (one
, two
);
116 /* Compute a hash value for a hashable_expr value EXPR and a
117 previously accumulated hash value VAL. If two hashable_expr
118 values compare equal with hashable_expr_equal_p, they must
119 hash to the same value, given an identical value of VAL.
120 The logic is intended to follow inchash::add_expr in tree.c. */
123 add_hashable_expr (const struct hashable_expr
*expr
, hash
&hstate
)
128 inchash::add_expr (expr
->ops
.single
.rhs
, hstate
);
132 hstate
.add_object (expr
->ops
.unary
.op
);
134 /* Make sure to include signedness in the hash computation.
135 Don't hash the type, that can lead to having nodes which
136 compare equal according to operand_equal_p, but which
137 have different hash codes. */
138 if (CONVERT_EXPR_CODE_P (expr
->ops
.unary
.op
)
139 || expr
->ops
.unary
.op
== NON_LVALUE_EXPR
)
140 hstate
.add_int (TYPE_UNSIGNED (expr
->type
));
142 inchash::add_expr (expr
->ops
.unary
.opnd
, hstate
);
146 hstate
.add_object (expr
->ops
.binary
.op
);
147 if (commutative_tree_code (expr
->ops
.binary
.op
))
148 inchash::add_expr_commutative (expr
->ops
.binary
.opnd0
,
149 expr
->ops
.binary
.opnd1
, hstate
);
152 inchash::add_expr (expr
->ops
.binary
.opnd0
, hstate
);
153 inchash::add_expr (expr
->ops
.binary
.opnd1
, hstate
);
158 hstate
.add_object (expr
->ops
.ternary
.op
);
159 if (commutative_ternary_tree_code (expr
->ops
.ternary
.op
))
160 inchash::add_expr_commutative (expr
->ops
.ternary
.opnd0
,
161 expr
->ops
.ternary
.opnd1
, hstate
);
164 inchash::add_expr (expr
->ops
.ternary
.opnd0
, hstate
);
165 inchash::add_expr (expr
->ops
.ternary
.opnd1
, hstate
);
167 inchash::add_expr (expr
->ops
.ternary
.opnd2
, hstate
);
173 enum tree_code code
= CALL_EXPR
;
176 hstate
.add_object (code
);
177 fn_from
= expr
->ops
.call
.fn_from
;
178 if (gimple_call_internal_p (fn_from
))
179 hstate
.merge_hash ((hashval_t
) gimple_call_internal_fn (fn_from
));
181 inchash::add_expr (gimple_call_fn (fn_from
), hstate
);
182 for (i
= 0; i
< expr
->ops
.call
.nargs
; i
++)
183 inchash::add_expr (expr
->ops
.call
.args
[i
], hstate
);
191 for (i
= 0; i
< expr
->ops
.phi
.nargs
; i
++)
192 inchash::add_expr (expr
->ops
.phi
.args
[i
], hstate
);
203 /* Hashing and equality functions. We compute a value number for expressions
204 using the code of the expression and the SSA numbers of its operands. */
207 avail_expr_hash (class expr_hash_elt
*p
)
209 const struct hashable_expr
*expr
= p
->expr ();
210 inchash::hash hstate
;
212 inchash::add_hashable_expr (expr
, hstate
);
214 return hstate
.end ();
217 /* Compare two hashable_expr structures for equivalence. They are
218 considered equivalent when the expressions they denote must
219 necessarily be equal. The logic is intended to follow that of
220 operand_equal_p in fold-const.c */
223 hashable_expr_equal_p (const struct hashable_expr
*expr0
,
224 const struct hashable_expr
*expr1
)
226 tree type0
= expr0
->type
;
227 tree type1
= expr1
->type
;
229 /* If either type is NULL, there is nothing to check. */
230 if ((type0
== NULL_TREE
) ^ (type1
== NULL_TREE
))
233 /* If both types don't have the same signedness, precision, and mode,
234 then we can't consider them equal. */
236 && (TREE_CODE (type0
) == ERROR_MARK
237 || TREE_CODE (type1
) == ERROR_MARK
238 || TYPE_UNSIGNED (type0
) != TYPE_UNSIGNED (type1
)
239 || TYPE_PRECISION (type0
) != TYPE_PRECISION (type1
)
240 || TYPE_MODE (type0
) != TYPE_MODE (type1
)))
243 if (expr0
->kind
!= expr1
->kind
)
249 return operand_equal_p (expr0
->ops
.single
.rhs
,
250 expr1
->ops
.single
.rhs
, 0);
253 if (expr0
->ops
.unary
.op
!= expr1
->ops
.unary
.op
)
256 if ((CONVERT_EXPR_CODE_P (expr0
->ops
.unary
.op
)
257 || expr0
->ops
.unary
.op
== NON_LVALUE_EXPR
)
258 && TYPE_UNSIGNED (expr0
->type
) != TYPE_UNSIGNED (expr1
->type
))
261 return operand_equal_p (expr0
->ops
.unary
.opnd
,
262 expr1
->ops
.unary
.opnd
, 0);
265 if (expr0
->ops
.binary
.op
!= expr1
->ops
.binary
.op
)
268 if (operand_equal_p (expr0
->ops
.binary
.opnd0
,
269 expr1
->ops
.binary
.opnd0
, 0)
270 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
271 expr1
->ops
.binary
.opnd1
, 0))
274 /* For commutative ops, allow the other order. */
275 return (commutative_tree_code (expr0
->ops
.binary
.op
)
276 && operand_equal_p (expr0
->ops
.binary
.opnd0
,
277 expr1
->ops
.binary
.opnd1
, 0)
278 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
279 expr1
->ops
.binary
.opnd0
, 0));
282 if (expr0
->ops
.ternary
.op
!= expr1
->ops
.ternary
.op
283 || !operand_equal_p (expr0
->ops
.ternary
.opnd2
,
284 expr1
->ops
.ternary
.opnd2
, 0))
287 if (operand_equal_p (expr0
->ops
.ternary
.opnd0
,
288 expr1
->ops
.ternary
.opnd0
, 0)
289 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
290 expr1
->ops
.ternary
.opnd1
, 0))
293 /* For commutative ops, allow the other order. */
294 return (commutative_ternary_tree_code (expr0
->ops
.ternary
.op
)
295 && operand_equal_p (expr0
->ops
.ternary
.opnd0
,
296 expr1
->ops
.ternary
.opnd1
, 0)
297 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
298 expr1
->ops
.ternary
.opnd0
, 0));
304 /* If the calls are to different functions, then they
305 clearly cannot be equal. */
306 if (!gimple_call_same_target_p (expr0
->ops
.call
.fn_from
,
307 expr1
->ops
.call
.fn_from
))
310 if (! expr0
->ops
.call
.pure
)
313 if (expr0
->ops
.call
.nargs
!= expr1
->ops
.call
.nargs
)
316 for (i
= 0; i
< expr0
->ops
.call
.nargs
; i
++)
317 if (! operand_equal_p (expr0
->ops
.call
.args
[i
],
318 expr1
->ops
.call
.args
[i
], 0))
321 if (stmt_could_throw_p (expr0
->ops
.call
.fn_from
))
323 int lp0
= lookup_stmt_eh_lp (expr0
->ops
.call
.fn_from
);
324 int lp1
= lookup_stmt_eh_lp (expr1
->ops
.call
.fn_from
);
325 if ((lp0
> 0 || lp1
> 0) && lp0
!= lp1
)
336 if (expr0
->ops
.phi
.nargs
!= expr1
->ops
.phi
.nargs
)
339 for (i
= 0; i
< expr0
->ops
.phi
.nargs
; i
++)
340 if (! operand_equal_p (expr0
->ops
.phi
.args
[i
],
341 expr1
->ops
.phi
.args
[i
], 0))
352 /* Given a statement STMT, construct a hash table element. */
354 expr_hash_elt::expr_hash_elt (gimple
*stmt
, tree orig_lhs
)
356 enum gimple_code code
= gimple_code (stmt
);
357 struct hashable_expr
*expr
= this->expr ();
359 if (code
== GIMPLE_ASSIGN
)
361 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
363 switch (get_gimple_rhs_class (subcode
))
365 case GIMPLE_SINGLE_RHS
:
366 expr
->kind
= EXPR_SINGLE
;
367 expr
->type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
368 expr
->ops
.single
.rhs
= gimple_assign_rhs1 (stmt
);
370 case GIMPLE_UNARY_RHS
:
371 expr
->kind
= EXPR_UNARY
;
372 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
373 if (CONVERT_EXPR_CODE_P (subcode
))
375 expr
->ops
.unary
.op
= subcode
;
376 expr
->ops
.unary
.opnd
= gimple_assign_rhs1 (stmt
);
378 case GIMPLE_BINARY_RHS
:
379 expr
->kind
= EXPR_BINARY
;
380 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
381 expr
->ops
.binary
.op
= subcode
;
382 expr
->ops
.binary
.opnd0
= gimple_assign_rhs1 (stmt
);
383 expr
->ops
.binary
.opnd1
= gimple_assign_rhs2 (stmt
);
385 case GIMPLE_TERNARY_RHS
:
386 expr
->kind
= EXPR_TERNARY
;
387 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
388 expr
->ops
.ternary
.op
= subcode
;
389 expr
->ops
.ternary
.opnd0
= gimple_assign_rhs1 (stmt
);
390 expr
->ops
.ternary
.opnd1
= gimple_assign_rhs2 (stmt
);
391 expr
->ops
.ternary
.opnd2
= gimple_assign_rhs3 (stmt
);
397 else if (code
== GIMPLE_COND
)
399 expr
->type
= boolean_type_node
;
400 expr
->kind
= EXPR_BINARY
;
401 expr
->ops
.binary
.op
= gimple_cond_code (stmt
);
402 expr
->ops
.binary
.opnd0
= gimple_cond_lhs (stmt
);
403 expr
->ops
.binary
.opnd1
= gimple_cond_rhs (stmt
);
405 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
407 size_t nargs
= gimple_call_num_args (call_stmt
);
410 gcc_assert (gimple_call_lhs (call_stmt
));
412 expr
->type
= TREE_TYPE (gimple_call_lhs (call_stmt
));
413 expr
->kind
= EXPR_CALL
;
414 expr
->ops
.call
.fn_from
= call_stmt
;
416 if (gimple_call_flags (call_stmt
) & (ECF_CONST
| ECF_PURE
))
417 expr
->ops
.call
.pure
= true;
419 expr
->ops
.call
.pure
= false;
421 expr
->ops
.call
.nargs
= nargs
;
422 expr
->ops
.call
.args
= XCNEWVEC (tree
, nargs
);
423 for (i
= 0; i
< nargs
; i
++)
424 expr
->ops
.call
.args
[i
] = gimple_call_arg (call_stmt
, i
);
426 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
428 expr
->type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
429 expr
->kind
= EXPR_SINGLE
;
430 expr
->ops
.single
.rhs
= gimple_switch_index (swtch_stmt
);
432 else if (code
== GIMPLE_GOTO
)
434 expr
->type
= TREE_TYPE (gimple_goto_dest (stmt
));
435 expr
->kind
= EXPR_SINGLE
;
436 expr
->ops
.single
.rhs
= gimple_goto_dest (stmt
);
438 else if (code
== GIMPLE_PHI
)
440 size_t nargs
= gimple_phi_num_args (stmt
);
443 expr
->type
= TREE_TYPE (gimple_phi_result (stmt
));
444 expr
->kind
= EXPR_PHI
;
445 expr
->ops
.phi
.nargs
= nargs
;
446 expr
->ops
.phi
.args
= XCNEWVEC (tree
, nargs
);
447 for (i
= 0; i
< nargs
; i
++)
448 expr
->ops
.phi
.args
[i
] = gimple_phi_arg_def (stmt
, i
);
454 m_vop
= gimple_vuse (stmt
);
455 m_hash
= avail_expr_hash (this);
459 /* Given a hashable_expr expression ORIG and an ORIG_LHS,
460 construct a hash table element. */
462 expr_hash_elt::expr_hash_elt (struct hashable_expr
*orig
, tree orig_lhs
)
467 m_hash
= avail_expr_hash (this);
471 /* Copy constructor for a hash table element. */
473 expr_hash_elt::expr_hash_elt (class expr_hash_elt
&old_elt
)
475 m_expr
= old_elt
.m_expr
;
476 m_lhs
= old_elt
.m_lhs
;
477 m_vop
= old_elt
.m_vop
;
478 m_hash
= old_elt
.m_hash
;
481 /* Now deep copy the malloc'd space for CALL and PHI args. */
482 if (old_elt
.m_expr
.kind
== EXPR_CALL
)
484 size_t nargs
= old_elt
.m_expr
.ops
.call
.nargs
;
487 m_expr
.ops
.call
.args
= XCNEWVEC (tree
, nargs
);
488 for (i
= 0; i
< nargs
; i
++)
489 m_expr
.ops
.call
.args
[i
] = old_elt
.m_expr
.ops
.call
.args
[i
];
491 else if (old_elt
.m_expr
.kind
== EXPR_PHI
)
493 size_t nargs
= old_elt
.m_expr
.ops
.phi
.nargs
;
496 m_expr
.ops
.phi
.args
= XCNEWVEC (tree
, nargs
);
497 for (i
= 0; i
< nargs
; i
++)
498 m_expr
.ops
.phi
.args
[i
] = old_elt
.m_expr
.ops
.phi
.args
[i
];
502 /* Calls and PHIs have a variable number of arguments that are allocated
503 on the heap. Thus we have to have a special dtor to release them. */
505 expr_hash_elt::~expr_hash_elt ()
507 if (m_expr
.kind
== EXPR_CALL
)
508 free (m_expr
.ops
.call
.args
);
509 else if (m_expr
.kind
== EXPR_PHI
)
510 free (m_expr
.ops
.phi
.args
);
513 /* Print a diagnostic dump of an expression hash table entry. */
516 expr_hash_elt::print (FILE *stream
)
518 fprintf (stream
, "STMT ");
522 print_generic_expr (stream
, m_lhs
, 0);
523 fprintf (stream
, " = ");
529 print_generic_expr (stream
, m_expr
.ops
.single
.rhs
, 0);
533 fprintf (stream
, "%s ", get_tree_code_name (m_expr
.ops
.unary
.op
));
534 print_generic_expr (stream
, m_expr
.ops
.unary
.opnd
, 0);
538 print_generic_expr (stream
, m_expr
.ops
.binary
.opnd0
, 0);
539 fprintf (stream
, " %s ", get_tree_code_name (m_expr
.ops
.binary
.op
));
540 print_generic_expr (stream
, m_expr
.ops
.binary
.opnd1
, 0);
544 fprintf (stream
, " %s <", get_tree_code_name (m_expr
.ops
.ternary
.op
));
545 print_generic_expr (stream
, m_expr
.ops
.ternary
.opnd0
, 0);
546 fputs (", ", stream
);
547 print_generic_expr (stream
, m_expr
.ops
.ternary
.opnd1
, 0);
548 fputs (", ", stream
);
549 print_generic_expr (stream
, m_expr
.ops
.ternary
.opnd2
, 0);
556 size_t nargs
= m_expr
.ops
.call
.nargs
;
559 fn_from
= m_expr
.ops
.call
.fn_from
;
560 if (gimple_call_internal_p (fn_from
))
561 fputs (internal_fn_name (gimple_call_internal_fn (fn_from
)),
564 print_generic_expr (stream
, gimple_call_fn (fn_from
), 0);
565 fprintf (stream
, " (");
566 for (i
= 0; i
< nargs
; i
++)
568 print_generic_expr (stream
, m_expr
.ops
.call
.args
[i
], 0);
570 fprintf (stream
, ", ");
572 fprintf (stream
, ")");
579 size_t nargs
= m_expr
.ops
.phi
.nargs
;
581 fprintf (stream
, "PHI <");
582 for (i
= 0; i
< nargs
; i
++)
584 print_generic_expr (stream
, m_expr
.ops
.phi
.args
[i
], 0);
586 fprintf (stream
, ", ");
588 fprintf (stream
, ">");
595 fprintf (stream
, " with ");
596 print_generic_expr (stream
, m_vop
, 0);
599 fprintf (stream
, "\n");
602 /* Pop entries off the stack until we hit the NULL marker.
603 For each entry popped, use the SRC/DEST pair to restore
604 SRC to its prior value. */
607 const_and_copies::pop_to_marker (void)
609 while (m_stack
.length () > 0)
611 tree prev_value
, dest
;
613 dest
= m_stack
.pop ();
615 /* A NULL value indicates we should stop unwinding, otherwise
616 pop off the next entry as they're recorded in pairs. */
620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
622 fprintf (dump_file
, "<<<< COPY ");
623 print_generic_expr (dump_file
, dest
, 0);
624 fprintf (dump_file
, " = ");
625 print_generic_expr (dump_file
, SSA_NAME_VALUE (dest
), 0);
626 fprintf (dump_file
, "\n");
629 prev_value
= m_stack
.pop ();
630 set_ssa_name_value (dest
, prev_value
);
634 /* Record that X has the value Y. */
637 const_and_copies::record_const_or_copy (tree x
, tree y
)
639 record_const_or_copy (x
, y
, SSA_NAME_VALUE (x
));
642 /* Record that X has the value Y and that X's previous value is PREV_X. */
645 const_and_copies::record_const_or_copy (tree x
, tree y
, tree prev_x
)
647 /* Y may be NULL if we are invalidating entries in the table. */
648 if (y
&& TREE_CODE (y
) == SSA_NAME
)
650 tree tmp
= SSA_NAME_VALUE (y
);
654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
656 fprintf (dump_file
, "0>>> COPY ");
657 print_generic_expr (dump_file
, x
, 0);
658 fprintf (dump_file
, " = ");
659 print_generic_expr (dump_file
, y
, 0);
660 fprintf (dump_file
, "\n");
663 set_ssa_name_value (x
, y
);
665 m_stack
.quick_push (prev_x
);
666 m_stack
.quick_push (x
);
670 expr_elt_hasher::equal (const value_type
&p1
, const compare_type
&p2
)
672 const struct hashable_expr
*expr1
= p1
->expr ();
673 const struct expr_hash_elt
*stamp1
= p1
->stamp ();
674 const struct hashable_expr
*expr2
= p2
->expr ();
675 const struct expr_hash_elt
*stamp2
= p2
->stamp ();
677 /* This case should apply only when removing entries from the table. */
678 if (stamp1
== stamp2
)
681 if (p1
->hash () != p2
->hash ())
684 /* In case of a collision, both RHS have to be identical and have the
685 same VUSE operands. */
686 if (hashable_expr_equal_p (expr1
, expr2
)
687 && types_compatible_p (expr1
->type
, expr2
->type
))
693 /* Given a conditional expression COND as a tree, initialize
694 a hashable_expr expression EXPR. The conditional must be a
695 comparison or logical negation. A constant or a variable is
699 initialize_expr_from_cond (tree cond
, struct hashable_expr
*expr
)
701 expr
->type
= boolean_type_node
;
703 if (COMPARISON_CLASS_P (cond
))
705 expr
->kind
= EXPR_BINARY
;
706 expr
->ops
.binary
.op
= TREE_CODE (cond
);
707 expr
->ops
.binary
.opnd0
= TREE_OPERAND (cond
, 0);
708 expr
->ops
.binary
.opnd1
= TREE_OPERAND (cond
, 1);
710 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
712 expr
->kind
= EXPR_UNARY
;
713 expr
->ops
.unary
.op
= TRUTH_NOT_EXPR
;
714 expr
->ops
.unary
.opnd
= TREE_OPERAND (cond
, 0);