* g++.dg/cpp/ucn-1.C: Fix typo.
[official-gcc.git] / gcc / tree-ssa-scopedtables.c
blob6034f79df69e2ac60cf22d2c100df02c184a125f
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
9 version.
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.
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/>. */
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"
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. */
46 void
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 ();
53 expr_hash_elt **slot;
55 if (victim.first == NULL)
56 break;
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)
71 delete *slot;
72 *slot = victim.second;
74 else
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. */
82 void
83 avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
84 class expr_hash_elt *elt2,
85 char type)
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. */
103 namespace inchash
106 static void
107 add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
109 hash one, two;
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. */
122 static void
123 add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
125 switch (expr->kind)
127 case EXPR_SINGLE:
128 inchash::add_expr (expr->ops.single.rhs, hstate);
129 break;
131 case EXPR_UNARY:
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);
143 break;
145 case EXPR_BINARY:
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);
150 else
152 inchash::add_expr (expr->ops.binary.opnd0, hstate);
153 inchash::add_expr (expr->ops.binary.opnd1, hstate);
155 break;
157 case EXPR_TERNARY:
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);
162 else
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);
168 break;
170 case EXPR_CALL:
172 size_t i;
173 enum tree_code code = CALL_EXPR;
174 gcall *fn_from;
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));
180 else
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);
185 break;
187 case EXPR_PHI:
189 size_t i;
191 for (i = 0; i < expr->ops.phi.nargs; i++)
192 inchash::add_expr (expr->ops.phi.args[i], hstate);
194 break;
196 default:
197 gcc_unreachable ();
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. */
206 static hashval_t
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 */
222 static bool
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))
231 return false;
233 /* If both types don't have the same signedness, precision, and mode,
234 then we can't consider them equal. */
235 if (type0 != type1
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)))
241 return false;
243 if (expr0->kind != expr1->kind)
244 return false;
246 switch (expr0->kind)
248 case EXPR_SINGLE:
249 return operand_equal_p (expr0->ops.single.rhs,
250 expr1->ops.single.rhs, 0);
252 case EXPR_UNARY:
253 if (expr0->ops.unary.op != expr1->ops.unary.op)
254 return false;
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))
259 return false;
261 return operand_equal_p (expr0->ops.unary.opnd,
262 expr1->ops.unary.opnd, 0);
264 case EXPR_BINARY:
265 if (expr0->ops.binary.op != expr1->ops.binary.op)
266 return false;
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))
272 return true;
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));
281 case EXPR_TERNARY:
282 if (expr0->ops.ternary.op != expr1->ops.ternary.op
283 || !operand_equal_p (expr0->ops.ternary.opnd2,
284 expr1->ops.ternary.opnd2, 0))
285 return false;
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))
291 return true;
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));
300 case EXPR_CALL:
302 size_t i;
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))
308 return false;
310 if (! expr0->ops.call.pure)
311 return false;
313 if (expr0->ops.call.nargs != expr1->ops.call.nargs)
314 return false;
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))
319 return false;
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)
326 return false;
329 return true;
332 case EXPR_PHI:
334 size_t i;
336 if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
337 return false;
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))
342 return false;
344 return true;
347 default:
348 gcc_unreachable ();
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);
369 break;
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))
374 subcode = NOP_EXPR;
375 expr->ops.unary.op = subcode;
376 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
377 break;
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);
384 break;
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);
392 break;
393 default:
394 gcc_unreachable ();
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);
408 size_t i;
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;
418 else
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);
441 size_t i;
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);
450 else
451 gcc_unreachable ();
453 m_lhs = orig_lhs;
454 m_vop = gimple_vuse (stmt);
455 m_hash = avail_expr_hash (this);
456 m_stamp = 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)
464 m_expr = *orig;
465 m_lhs = orig_lhs;
466 m_vop = NULL_TREE;
467 m_hash = avail_expr_hash (this);
468 m_stamp = 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;
479 m_stamp = this;
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;
485 size_t i;
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;
494 size_t i;
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. */
515 void
516 expr_hash_elt::print (FILE *stream)
518 fprintf (stream, "STMT ");
520 if (m_lhs)
522 print_generic_expr (stream, m_lhs, 0);
523 fprintf (stream, " = ");
526 switch (m_expr.kind)
528 case EXPR_SINGLE:
529 print_generic_expr (stream, m_expr.ops.single.rhs, 0);
530 break;
532 case EXPR_UNARY:
533 fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op));
534 print_generic_expr (stream, m_expr.ops.unary.opnd, 0);
535 break;
537 case EXPR_BINARY:
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);
541 break;
543 case EXPR_TERNARY:
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);
550 fputs (">", stream);
551 break;
553 case EXPR_CALL:
555 size_t i;
556 size_t nargs = m_expr.ops.call.nargs;
557 gcall *fn_from;
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)),
562 stream);
563 else
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);
569 if (i + 1 < nargs)
570 fprintf (stream, ", ");
572 fprintf (stream, ")");
574 break;
576 case EXPR_PHI:
578 size_t i;
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);
585 if (i + 1 < nargs)
586 fprintf (stream, ", ");
588 fprintf (stream, ">");
590 break;
593 if (m_vop)
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. */
606 void
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. */
617 if (dest == NULL)
618 break;
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. */
636 void
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. */
644 void
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);
651 y = tmp ? tmp : 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);
664 m_stack.reserve (2);
665 m_stack.quick_push (prev_x);
666 m_stack.quick_push (x);
669 bool
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)
679 return true;
681 if (p1->hash () != p2->hash ())
682 return false;
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))
688 return true;
690 return false;
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
696 not permitted. */
698 void
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);
716 else
717 gcc_unreachable ();