Daily bump.
[official-gcc.git] / gcc / tree-ssa.c
blobfa8f81e9a1a14fda0d76bd1cc39b81d242e1a311
1 /* Miscellaneous SSA utility functions.
2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License 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 "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "cfghooks.h"
27 #include "tree-pass.h"
28 #include "ssa.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "stor-layout.h"
33 #include "gimple-fold.h"
34 #include "gimplify.h"
35 #include "gimple-iterator.h"
36 #include "gimple-walk.h"
37 #include "tree-ssa-loop-manip.h"
38 #include "tree-into-ssa.h"
39 #include "tree-ssa.h"
40 #include "cfgloop.h"
41 #include "cfgexpand.h"
42 #include "tree-cfg.h"
43 #include "tree-dfa.h"
44 #include "asan.h"
46 /* Pointer map of variable mappings, keyed by edge. */
47 static hash_map<edge, auto_vec<edge_var_map> > *edge_var_maps;
50 /* Add a mapping with PHI RESULT and PHI DEF associated with edge E. */
52 void
53 redirect_edge_var_map_add (edge e, tree result, tree def, source_location locus)
55 edge_var_map new_node;
57 if (edge_var_maps == NULL)
58 edge_var_maps = new hash_map<edge, auto_vec<edge_var_map> >;
60 auto_vec<edge_var_map> &slot = edge_var_maps->get_or_insert (e);
61 new_node.def = def;
62 new_node.result = result;
63 new_node.locus = locus;
65 slot.safe_push (new_node);
69 /* Clear the var mappings in edge E. */
71 void
72 redirect_edge_var_map_clear (edge e)
74 if (!edge_var_maps)
75 return;
77 auto_vec<edge_var_map> *head = edge_var_maps->get (e);
79 if (head)
80 head->release ();
84 /* Duplicate the redirected var mappings in OLDE in NEWE.
86 This assumes a hash_map can have multiple edges mapping to the same
87 var_map (many to one mapping), since we don't remove the previous mappings.
90 void
91 redirect_edge_var_map_dup (edge newe, edge olde)
93 if (!edge_var_maps)
94 return;
96 auto_vec<edge_var_map> *new_head = &edge_var_maps->get_or_insert (newe);
97 auto_vec<edge_var_map> *old_head = edge_var_maps->get (olde);
98 if (!old_head)
99 return;
101 new_head->safe_splice (*old_head);
105 /* Return the variable mappings for a given edge. If there is none, return
106 NULL. */
108 vec<edge_var_map> *
109 redirect_edge_var_map_vector (edge e)
111 /* Hey, what kind of idiot would... you'd be surprised. */
112 if (!edge_var_maps)
113 return NULL;
115 auto_vec<edge_var_map> *slot = edge_var_maps->get (e);
116 if (!slot)
117 return NULL;
119 return slot;
122 /* Clear the edge variable mappings. */
124 void
125 redirect_edge_var_map_empty (void)
127 if (edge_var_maps)
128 edge_var_maps->empty ();
132 /* Remove the corresponding arguments from the PHI nodes in E's
133 destination block and redirect it to DEST. Return redirected edge.
134 The list of removed arguments is stored in a vector accessed
135 through edge_var_maps. */
137 edge
138 ssa_redirect_edge (edge e, basic_block dest)
140 gphi_iterator gsi;
141 gphi *phi;
143 redirect_edge_var_map_clear (e);
145 /* Remove the appropriate PHI arguments in E's destination block.
146 If we are redirecting a copied edge the destination has not
147 got PHI argument space reserved nor an interesting argument. */
148 if (! (e->dest->flags & BB_DUPLICATED))
149 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
151 tree def;
152 source_location locus ;
154 phi = gsi.phi ();
155 def = gimple_phi_arg_def (phi, e->dest_idx);
156 locus = gimple_phi_arg_location (phi, e->dest_idx);
158 if (def == NULL_TREE)
159 continue;
161 redirect_edge_var_map_add (e, gimple_phi_result (phi), def, locus);
164 e = redirect_edge_succ_nodup (e, dest);
166 return e;
170 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
171 E->dest. */
173 void
174 flush_pending_stmts (edge e)
176 gphi *phi;
177 edge_var_map *vm;
178 int i;
179 gphi_iterator gsi;
181 vec<edge_var_map> *v = redirect_edge_var_map_vector (e);
182 if (!v)
183 return;
185 for (gsi = gsi_start_phis (e->dest), i = 0;
186 !gsi_end_p (gsi) && v->iterate (i, &vm);
187 gsi_next (&gsi), i++)
189 tree def;
191 phi = gsi.phi ();
192 def = redirect_edge_var_map_def (vm);
193 add_phi_arg (phi, def, e, redirect_edge_var_map_location (vm));
196 redirect_edge_var_map_clear (e);
199 /* Replace the LHS of STMT, an assignment, either a GIMPLE_ASSIGN or a
200 GIMPLE_CALL, with NLHS, in preparation for modifying the RHS to an
201 expression with a different value.
203 This will update any annotations (say debug bind stmts) referring
204 to the original LHS, so that they use the RHS instead. This is
205 done even if NLHS and LHS are the same, for it is understood that
206 the RHS will be modified afterwards, and NLHS will not be assigned
207 an equivalent value.
209 Adjusting any non-annotation uses of the LHS, if needed, is a
210 responsibility of the caller.
212 The effect of this call should be pretty much the same as that of
213 inserting a copy of STMT before STMT, and then removing the
214 original stmt, at which time gsi_remove() would have update
215 annotations, but using this function saves all the inserting,
216 copying and removing. */
218 void
219 gimple_replace_ssa_lhs (gimple *stmt, tree nlhs)
221 if (MAY_HAVE_DEBUG_STMTS)
223 tree lhs = gimple_get_lhs (stmt);
225 gcc_assert (SSA_NAME_DEF_STMT (lhs) == stmt);
227 insert_debug_temp_for_var_def (NULL, lhs);
230 gimple_set_lhs (stmt, nlhs);
234 /* Given a tree for an expression for which we might want to emit
235 locations or values in debug information (generally a variable, but
236 we might deal with other kinds of trees in the future), return the
237 tree that should be used as the variable of a DEBUG_BIND STMT or
238 VAR_LOCATION INSN or NOTE. Return NULL if VAR is not to be tracked. */
240 tree
241 target_for_debug_bind (tree var)
243 if (!MAY_HAVE_DEBUG_STMTS)
244 return NULL_TREE;
246 if (TREE_CODE (var) == SSA_NAME)
248 var = SSA_NAME_VAR (var);
249 if (var == NULL_TREE)
250 return NULL_TREE;
253 if ((!VAR_P (var) || VAR_DECL_IS_VIRTUAL_OPERAND (var))
254 && TREE_CODE (var) != PARM_DECL)
255 return NULL_TREE;
257 if (DECL_HAS_VALUE_EXPR_P (var))
258 return target_for_debug_bind (DECL_VALUE_EXPR (var));
260 if (DECL_IGNORED_P (var))
261 return NULL_TREE;
263 /* var-tracking only tracks registers. */
264 if (!is_gimple_reg_type (TREE_TYPE (var)))
265 return NULL_TREE;
267 return var;
270 /* Called via walk_tree, look for SSA_NAMEs that have already been
271 released. */
273 static tree
274 find_released_ssa_name (tree *tp, int *walk_subtrees, void *data_)
276 struct walk_stmt_info *wi = (struct walk_stmt_info *) data_;
278 if (wi && wi->is_lhs)
279 return NULL_TREE;
281 if (TREE_CODE (*tp) == SSA_NAME)
283 if (SSA_NAME_IN_FREE_LIST (*tp))
284 return *tp;
286 *walk_subtrees = 0;
288 else if (IS_TYPE_OR_DECL_P (*tp))
289 *walk_subtrees = 0;
291 return NULL_TREE;
294 /* Insert a DEBUG BIND stmt before the DEF of VAR if VAR is referenced
295 by other DEBUG stmts, and replace uses of the DEF with the
296 newly-created debug temp. */
298 void
299 insert_debug_temp_for_var_def (gimple_stmt_iterator *gsi, tree var)
301 imm_use_iterator imm_iter;
302 use_operand_p use_p;
303 gimple *stmt;
304 gimple *def_stmt = NULL;
305 int usecount = 0;
306 tree value = NULL;
308 if (!MAY_HAVE_DEBUG_STMTS)
309 return;
311 /* If this name has already been registered for replacement, do nothing
312 as anything that uses this name isn't in SSA form. */
313 if (name_registered_for_update_p (var))
314 return;
316 /* Check whether there are debug stmts that reference this variable and,
317 if there are, decide whether we should use a debug temp. */
318 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
320 stmt = USE_STMT (use_p);
322 if (!gimple_debug_bind_p (stmt))
323 continue;
325 if (usecount++)
326 break;
328 if (gimple_debug_bind_get_value (stmt) != var)
330 /* Count this as an additional use, so as to make sure we
331 use a temp unless VAR's definition has a SINGLE_RHS that
332 can be shared. */
333 usecount++;
334 break;
338 if (!usecount)
339 return;
341 if (gsi)
342 def_stmt = gsi_stmt (*gsi);
343 else
344 def_stmt = SSA_NAME_DEF_STMT (var);
346 /* If we didn't get an insertion point, and the stmt has already
347 been removed, we won't be able to insert the debug bind stmt, so
348 we'll have to drop debug information. */
349 if (gimple_code (def_stmt) == GIMPLE_PHI)
351 value = degenerate_phi_result (as_a <gphi *> (def_stmt));
352 if (value && walk_tree (&value, find_released_ssa_name, NULL, NULL))
353 value = NULL;
354 /* error_mark_node is what fixup_noreturn_call changes PHI arguments
355 to. */
356 else if (value == error_mark_node)
357 value = NULL;
359 else if (is_gimple_assign (def_stmt))
361 bool no_value = false;
363 if (!dom_info_available_p (CDI_DOMINATORS))
365 struct walk_stmt_info wi;
367 memset (&wi, 0, sizeof (wi));
369 /* When removing blocks without following reverse dominance
370 order, we may sometimes encounter SSA_NAMEs that have
371 already been released, referenced in other SSA_DEFs that
372 we're about to release. Consider:
374 <bb X>:
375 v_1 = foo;
377 <bb Y>:
378 w_2 = v_1 + bar;
379 # DEBUG w => w_2
381 If we deleted BB X first, propagating the value of w_2
382 won't do us any good. It's too late to recover their
383 original definition of v_1: when it was deleted, it was
384 only referenced in other DEFs, it couldn't possibly know
385 it should have been retained, and propagating every
386 single DEF just in case it might have to be propagated
387 into a DEBUG STMT would probably be too wasteful.
389 When dominator information is not readily available, we
390 check for and accept some loss of debug information. But
391 if it is available, there's no excuse for us to remove
392 blocks in the wrong order, so we don't even check for
393 dead SSA NAMEs. SSA verification shall catch any
394 errors. */
395 if ((!gsi && !gimple_bb (def_stmt))
396 || walk_gimple_op (def_stmt, find_released_ssa_name, &wi))
397 no_value = true;
400 if (!no_value)
401 value = gimple_assign_rhs_to_tree (def_stmt);
404 if (value)
406 /* If there's a single use of VAR, and VAR is the entire debug
407 expression (usecount would have been incremented again
408 otherwise), and the definition involves only constants and
409 SSA names, then we can propagate VALUE into this single use,
410 avoiding the temp.
412 We can also avoid using a temp if VALUE can be shared and
413 propagated into all uses, without generating expressions that
414 wouldn't be valid gimple RHSs.
416 Other cases that would require unsharing or non-gimple RHSs
417 are deferred to a debug temp, although we could avoid temps
418 at the expense of duplication of expressions. */
420 if (CONSTANT_CLASS_P (value)
421 || gimple_code (def_stmt) == GIMPLE_PHI
422 || (usecount == 1
423 && (!gimple_assign_single_p (def_stmt)
424 || is_gimple_min_invariant (value)))
425 || is_gimple_reg (value))
427 else
429 gdebug *def_temp;
430 tree vexpr = make_node (DEBUG_EXPR_DECL);
432 def_temp = gimple_build_debug_bind (vexpr,
433 unshare_expr (value),
434 def_stmt);
436 DECL_ARTIFICIAL (vexpr) = 1;
437 TREE_TYPE (vexpr) = TREE_TYPE (value);
438 if (DECL_P (value))
439 SET_DECL_MODE (vexpr, DECL_MODE (value));
440 else
441 SET_DECL_MODE (vexpr, TYPE_MODE (TREE_TYPE (value)));
443 if (gsi)
444 gsi_insert_before (gsi, def_temp, GSI_SAME_STMT);
445 else
447 gimple_stmt_iterator ngsi = gsi_for_stmt (def_stmt);
448 gsi_insert_before (&ngsi, def_temp, GSI_SAME_STMT);
451 value = vexpr;
455 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var)
457 if (!gimple_debug_bind_p (stmt))
458 continue;
460 if (value)
462 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
463 /* unshare_expr is not needed here. vexpr is either a
464 SINGLE_RHS, that can be safely shared, some other RHS
465 that was unshared when we found it had a single debug
466 use, or a DEBUG_EXPR_DECL, that can be safely
467 shared. */
468 SET_USE (use_p, unshare_expr (value));
469 /* If we didn't replace uses with a debug decl fold the
470 resulting expression. Otherwise we end up with invalid IL. */
471 if (TREE_CODE (value) != DEBUG_EXPR_DECL)
473 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
474 fold_stmt_inplace (&gsi);
477 else
478 gimple_debug_bind_reset_value (stmt);
480 update_stmt (stmt);
485 /* Insert a DEBUG BIND stmt before STMT for each DEF referenced by
486 other DEBUG stmts, and replace uses of the DEF with the
487 newly-created debug temp. */
489 void
490 insert_debug_temps_for_defs (gimple_stmt_iterator *gsi)
492 gimple *stmt;
493 ssa_op_iter op_iter;
494 def_operand_p def_p;
496 if (!MAY_HAVE_DEBUG_STMTS)
497 return;
499 stmt = gsi_stmt (*gsi);
501 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
503 tree var = DEF_FROM_PTR (def_p);
505 if (TREE_CODE (var) != SSA_NAME)
506 continue;
508 insert_debug_temp_for_var_def (gsi, var);
512 /* Reset all debug stmts that use SSA_NAME(s) defined in STMT. */
514 void
515 reset_debug_uses (gimple *stmt)
517 ssa_op_iter op_iter;
518 def_operand_p def_p;
519 imm_use_iterator imm_iter;
520 gimple *use_stmt;
522 if (!MAY_HAVE_DEBUG_STMTS)
523 return;
525 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
527 tree var = DEF_FROM_PTR (def_p);
529 if (TREE_CODE (var) != SSA_NAME)
530 continue;
532 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, var)
534 if (!gimple_debug_bind_p (use_stmt))
535 continue;
537 gimple_debug_bind_reset_value (use_stmt);
538 update_stmt (use_stmt);
543 /* Delete SSA DEFs for SSA versions in the TOREMOVE bitmap, removing
544 dominated stmts before their dominators, so that release_ssa_defs
545 stands a chance of propagating DEFs into debug bind stmts. */
547 void
548 release_defs_bitset (bitmap toremove)
550 unsigned j;
551 bitmap_iterator bi;
553 /* Performing a topological sort is probably overkill, this will
554 most likely run in slightly superlinear time, rather than the
555 pathological quadratic worst case. */
556 while (!bitmap_empty_p (toremove))
558 unsigned to_remove_bit = -1U;
559 EXECUTE_IF_SET_IN_BITMAP (toremove, 0, j, bi)
561 if (to_remove_bit != -1U)
563 bitmap_clear_bit (toremove, to_remove_bit);
564 to_remove_bit = -1U;
567 bool remove_now = true;
568 tree var = ssa_name (j);
569 gimple *stmt;
570 imm_use_iterator uit;
572 FOR_EACH_IMM_USE_STMT (stmt, uit, var)
574 ssa_op_iter dit;
575 def_operand_p def_p;
577 /* We can't propagate PHI nodes into debug stmts. */
578 if (gimple_code (stmt) == GIMPLE_PHI
579 || is_gimple_debug (stmt))
580 continue;
582 /* If we find another definition to remove that uses
583 the one we're looking at, defer the removal of this
584 one, so that it can be propagated into debug stmts
585 after the other is. */
586 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, dit, SSA_OP_DEF)
588 tree odef = DEF_FROM_PTR (def_p);
590 if (bitmap_bit_p (toremove, SSA_NAME_VERSION (odef)))
592 remove_now = false;
593 break;
597 if (!remove_now)
598 BREAK_FROM_IMM_USE_STMT (uit);
601 if (remove_now)
603 gimple *def = SSA_NAME_DEF_STMT (var);
604 gimple_stmt_iterator gsi = gsi_for_stmt (def);
606 if (gimple_code (def) == GIMPLE_PHI)
607 remove_phi_node (&gsi, true);
608 else
610 gsi_remove (&gsi, true);
611 release_defs (def);
614 to_remove_bit = j;
617 if (to_remove_bit != -1U)
618 bitmap_clear_bit (toremove, to_remove_bit);
623 /* Verify virtual SSA form. */
625 bool
626 verify_vssa (basic_block bb, tree current_vdef, sbitmap visited)
628 bool err = false;
630 if (bitmap_bit_p (visited, bb->index))
631 return false;
633 bitmap_set_bit (visited, bb->index);
635 /* Pick up the single virtual PHI def. */
636 gphi *phi = NULL;
637 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
638 gsi_next (&si))
640 tree res = gimple_phi_result (si.phi ());
641 if (virtual_operand_p (res))
643 if (phi)
645 error ("multiple virtual PHI nodes in BB %d", bb->index);
646 print_gimple_stmt (stderr, phi, 0);
647 print_gimple_stmt (stderr, si.phi (), 0);
648 err = true;
650 else
651 phi = si.phi ();
654 if (phi)
656 current_vdef = gimple_phi_result (phi);
657 if (TREE_CODE (current_vdef) != SSA_NAME)
659 error ("virtual definition is not an SSA name");
660 print_gimple_stmt (stderr, phi, 0);
661 err = true;
665 /* Verify stmts. */
666 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
667 gsi_next (&gsi))
669 gimple *stmt = gsi_stmt (gsi);
670 tree vuse = gimple_vuse (stmt);
671 if (vuse)
673 if (vuse != current_vdef)
675 error ("stmt with wrong VUSE");
676 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
677 fprintf (stderr, "expected ");
678 print_generic_expr (stderr, current_vdef);
679 fprintf (stderr, "\n");
680 err = true;
682 tree vdef = gimple_vdef (stmt);
683 if (vdef)
685 current_vdef = vdef;
686 if (TREE_CODE (current_vdef) != SSA_NAME)
688 error ("virtual definition is not an SSA name");
689 print_gimple_stmt (stderr, phi, 0);
690 err = true;
696 /* Verify destination PHI uses and recurse. */
697 edge_iterator ei;
698 edge e;
699 FOR_EACH_EDGE (e, ei, bb->succs)
701 gphi *phi = get_virtual_phi (e->dest);
702 if (phi
703 && PHI_ARG_DEF_FROM_EDGE (phi, e) != current_vdef)
705 error ("PHI node with wrong VUSE on edge from BB %d",
706 e->src->index);
707 print_gimple_stmt (stderr, phi, 0, TDF_VOPS);
708 fprintf (stderr, "expected ");
709 print_generic_expr (stderr, current_vdef);
710 fprintf (stderr, "\n");
711 err = true;
714 /* Recurse. */
715 err |= verify_vssa (e->dest, current_vdef, visited);
718 return err;
721 /* Return true if SSA_NAME is malformed and mark it visited.
723 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
724 operand. */
726 static bool
727 verify_ssa_name (tree ssa_name, bool is_virtual)
729 if (TREE_CODE (ssa_name) != SSA_NAME)
731 error ("expected an SSA_NAME object");
732 return true;
735 if (SSA_NAME_IN_FREE_LIST (ssa_name))
737 error ("found an SSA_NAME that had been released into the free pool");
738 return true;
741 if (SSA_NAME_VAR (ssa_name) != NULL_TREE
742 && TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
744 error ("type mismatch between an SSA_NAME and its symbol");
745 return true;
748 if (is_virtual && !virtual_operand_p (ssa_name))
750 error ("found a virtual definition for a GIMPLE register");
751 return true;
754 if (is_virtual && SSA_NAME_VAR (ssa_name) != gimple_vop (cfun))
756 error ("virtual SSA name for non-VOP decl");
757 return true;
760 if (!is_virtual && virtual_operand_p (ssa_name))
762 error ("found a real definition for a non-register");
763 return true;
766 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
767 && !gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name)))
769 error ("found a default name with a non-empty defining statement");
770 return true;
773 return false;
777 /* Return true if the definition of SSA_NAME at block BB is malformed.
779 STMT is the statement where SSA_NAME is created.
781 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
782 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
783 it means that the block in that array slot contains the
784 definition of SSA_NAME.
786 IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
788 static bool
789 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
790 gimple *stmt, bool is_virtual)
792 if (verify_ssa_name (ssa_name, is_virtual))
793 goto err;
795 if (SSA_NAME_VAR (ssa_name)
796 && TREE_CODE (SSA_NAME_VAR (ssa_name)) == RESULT_DECL
797 && DECL_BY_REFERENCE (SSA_NAME_VAR (ssa_name)))
799 error ("RESULT_DECL should be read only when DECL_BY_REFERENCE is set");
800 goto err;
803 if (definition_block[SSA_NAME_VERSION (ssa_name)])
805 error ("SSA_NAME created in two different blocks %i and %i",
806 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
807 goto err;
810 definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
812 if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
814 error ("SSA_NAME_DEF_STMT is wrong");
815 fprintf (stderr, "Expected definition statement:\n");
816 print_gimple_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), 4, TDF_VOPS);
817 fprintf (stderr, "\nActual definition statement:\n");
818 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
819 goto err;
822 return false;
824 err:
825 fprintf (stderr, "while verifying SSA_NAME ");
826 print_generic_expr (stderr, ssa_name);
827 fprintf (stderr, " in statement\n");
828 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
830 return true;
834 /* Return true if the use of SSA_NAME at statement STMT in block BB is
835 malformed.
837 DEF_BB is the block where SSA_NAME was found to be created.
839 IDOM contains immediate dominator information for the flowgraph.
841 CHECK_ABNORMAL is true if the caller wants to check whether this use
842 is flowing through an abnormal edge (only used when checking PHI
843 arguments).
845 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
846 that are defined before STMT in basic block BB. */
848 static bool
849 verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
850 gimple *stmt, bool check_abnormal, bitmap names_defined_in_bb)
852 bool err = false;
853 tree ssa_name = USE_FROM_PTR (use_p);
855 if (!TREE_VISITED (ssa_name))
856 if (verify_imm_links (stderr, ssa_name))
857 err = true;
859 TREE_VISITED (ssa_name) = 1;
861 if (gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name))
862 && SSA_NAME_IS_DEFAULT_DEF (ssa_name))
863 ; /* Default definitions have empty statements. Nothing to do. */
864 else if (!def_bb)
866 error ("missing definition");
867 err = true;
869 else if (bb != def_bb
870 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
872 error ("definition in block %i does not dominate use in block %i",
873 def_bb->index, bb->index);
874 err = true;
876 else if (bb == def_bb
877 && names_defined_in_bb != NULL
878 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
880 error ("definition in block %i follows the use", def_bb->index);
881 err = true;
884 if (check_abnormal
885 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
887 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
888 err = true;
891 /* Make sure the use is in an appropriate list by checking the previous
892 element to make sure it's the same. */
893 if (use_p->prev == NULL)
895 error ("no immediate_use list");
896 err = true;
898 else
900 tree listvar;
901 if (use_p->prev->use == NULL)
902 listvar = use_p->prev->loc.ssa_name;
903 else
904 listvar = USE_FROM_PTR (use_p->prev);
905 if (listvar != ssa_name)
907 error ("wrong immediate use list");
908 err = true;
912 if (err)
914 fprintf (stderr, "for SSA_NAME: ");
915 print_generic_expr (stderr, ssa_name, TDF_VOPS);
916 fprintf (stderr, " in statement:\n");
917 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
920 return err;
924 /* Return true if any of the arguments for PHI node PHI at block BB is
925 malformed.
927 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
928 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
929 it means that the block in that array slot contains the
930 definition of SSA_NAME. */
932 static bool
933 verify_phi_args (gphi *phi, basic_block bb, basic_block *definition_block)
935 edge e;
936 bool err = false;
937 size_t i, phi_num_args = gimple_phi_num_args (phi);
939 if (EDGE_COUNT (bb->preds) != phi_num_args)
941 error ("incoming edge count does not match number of PHI arguments");
942 err = true;
943 goto error;
946 for (i = 0; i < phi_num_args; i++)
948 use_operand_p op_p = gimple_phi_arg_imm_use_ptr (phi, i);
949 tree op = USE_FROM_PTR (op_p);
951 e = EDGE_PRED (bb, i);
953 if (op == NULL_TREE)
955 error ("PHI argument is missing for edge %d->%d",
956 e->src->index,
957 e->dest->index);
958 err = true;
959 goto error;
962 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
964 error ("PHI argument is not SSA_NAME, or invariant");
965 err = true;
968 if (TREE_CODE (op) == SSA_NAME)
970 err = verify_ssa_name (op, virtual_operand_p (gimple_phi_result (phi)));
971 err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)],
972 op_p, phi, e->flags & EDGE_ABNORMAL, NULL);
975 if (TREE_CODE (op) == ADDR_EXPR)
977 tree base = TREE_OPERAND (op, 0);
978 while (handled_component_p (base))
979 base = TREE_OPERAND (base, 0);
980 if ((VAR_P (base)
981 || TREE_CODE (base) == PARM_DECL
982 || TREE_CODE (base) == RESULT_DECL)
983 && !TREE_ADDRESSABLE (base))
985 error ("address taken, but ADDRESSABLE bit not set");
986 err = true;
990 if (e->dest != bb)
992 error ("wrong edge %d->%d for PHI argument",
993 e->src->index, e->dest->index);
994 err = true;
997 if (err)
999 fprintf (stderr, "PHI argument\n");
1000 print_generic_stmt (stderr, op, TDF_VOPS);
1001 goto error;
1005 error:
1006 if (err)
1008 fprintf (stderr, "for PHI node\n");
1009 print_gimple_stmt (stderr, phi, 0, TDF_VOPS|TDF_MEMSYMS);
1013 return err;
1017 /* Verify common invariants in the SSA web.
1018 TODO: verify the variable annotations. */
1020 DEBUG_FUNCTION void
1021 verify_ssa (bool check_modified_stmt, bool check_ssa_operands)
1023 basic_block bb;
1024 basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
1025 ssa_op_iter iter;
1026 tree op;
1027 enum dom_state orig_dom_state = dom_info_state (CDI_DOMINATORS);
1028 auto_bitmap names_defined_in_bb;
1030 gcc_assert (!need_ssa_update_p (cfun));
1032 timevar_push (TV_TREE_SSA_VERIFY);
1035 /* Keep track of SSA names present in the IL. */
1036 size_t i;
1037 tree name;
1038 hash_map <void *, tree> ssa_info;
1040 FOR_EACH_SSA_NAME (i, name, cfun)
1042 gimple *stmt;
1043 TREE_VISITED (name) = 0;
1045 verify_ssa_name (name, virtual_operand_p (name));
1047 stmt = SSA_NAME_DEF_STMT (name);
1048 if (!gimple_nop_p (stmt))
1050 basic_block bb = gimple_bb (stmt);
1051 if (verify_def (bb, definition_block,
1052 name, stmt, virtual_operand_p (name)))
1053 goto err;
1056 void *info = NULL;
1057 if (POINTER_TYPE_P (TREE_TYPE (name)))
1058 info = SSA_NAME_PTR_INFO (name);
1059 else if (INTEGRAL_TYPE_P (TREE_TYPE (name)))
1060 info = SSA_NAME_RANGE_INFO (name);
1061 if (info)
1063 bool existed;
1064 tree &val = ssa_info.get_or_insert (info, &existed);
1065 if (existed)
1067 error ("shared SSA name info");
1068 print_generic_expr (stderr, val);
1069 fprintf (stderr, " and ");
1070 print_generic_expr (stderr, name);
1071 fprintf (stderr, "\n");
1072 goto err;
1074 else
1075 val = name;
1080 calculate_dominance_info (CDI_DOMINATORS);
1082 /* Now verify all the uses and make sure they agree with the definitions
1083 found in the previous pass. */
1084 FOR_EACH_BB_FN (bb, cfun)
1086 edge e;
1087 edge_iterator ei;
1089 /* Make sure that all edges have a clear 'aux' field. */
1090 FOR_EACH_EDGE (e, ei, bb->preds)
1092 if (e->aux)
1094 error ("AUX pointer initialized for edge %d->%d", e->src->index,
1095 e->dest->index);
1096 goto err;
1100 /* Verify the arguments for every PHI node in the block. */
1101 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1103 gphi *phi = gsi.phi ();
1104 if (verify_phi_args (phi, bb, definition_block))
1105 goto err;
1107 bitmap_set_bit (names_defined_in_bb,
1108 SSA_NAME_VERSION (gimple_phi_result (phi)));
1111 /* Now verify all the uses and vuses in every statement of the block. */
1112 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1113 gsi_next (&gsi))
1115 gimple *stmt = gsi_stmt (gsi);
1116 use_operand_p use_p;
1118 if (check_modified_stmt && gimple_modified_p (stmt))
1120 error ("stmt (%p) marked modified after optimization pass: ",
1121 (void *)stmt);
1122 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
1123 goto err;
1126 if (check_ssa_operands && verify_ssa_operands (cfun, stmt))
1128 print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
1129 goto err;
1132 if (gimple_debug_bind_p (stmt)
1133 && !gimple_debug_bind_has_value_p (stmt))
1134 continue;
1136 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
1138 op = USE_FROM_PTR (use_p);
1139 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
1140 use_p, stmt, false, names_defined_in_bb))
1141 goto err;
1144 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
1146 if (SSA_NAME_DEF_STMT (op) != stmt)
1148 error ("SSA_NAME_DEF_STMT is wrong");
1149 fprintf (stderr, "Expected definition statement:\n");
1150 print_gimple_stmt (stderr, stmt, 4, TDF_VOPS);
1151 fprintf (stderr, "\nActual definition statement:\n");
1152 print_gimple_stmt (stderr, SSA_NAME_DEF_STMT (op),
1153 4, TDF_VOPS);
1154 goto err;
1156 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
1160 bitmap_clear (names_defined_in_bb);
1163 free (definition_block);
1165 if (gimple_vop (cfun)
1166 && ssa_default_def (cfun, gimple_vop (cfun)))
1168 auto_sbitmap visited (last_basic_block_for_fn (cfun) + 1);
1169 bitmap_clear (visited);
1170 if (verify_vssa (ENTRY_BLOCK_PTR_FOR_FN (cfun),
1171 ssa_default_def (cfun, gimple_vop (cfun)), visited))
1172 goto err;
1175 /* Restore the dominance information to its prior known state, so
1176 that we do not perturb the compiler's subsequent behavior. */
1177 if (orig_dom_state == DOM_NONE)
1178 free_dominance_info (CDI_DOMINATORS);
1179 else
1180 set_dom_info_availability (CDI_DOMINATORS, orig_dom_state);
1182 timevar_pop (TV_TREE_SSA_VERIFY);
1183 return;
1185 err:
1186 internal_error ("verify_ssa failed");
1190 /* Initialize global DFA and SSA structures. */
1192 void
1193 init_tree_ssa (struct function *fn)
1195 fn->gimple_df = ggc_cleared_alloc<gimple_df> ();
1196 fn->gimple_df->default_defs = hash_table<ssa_name_hasher>::create_ggc (20);
1197 pt_solution_reset (&fn->gimple_df->escaped);
1198 init_ssanames (fn, 0);
1201 /* Deallocate memory associated with SSA data structures for FNDECL. */
1203 void
1204 delete_tree_ssa (struct function *fn)
1206 fini_ssanames (fn);
1208 /* We no longer maintain the SSA operand cache at this point. */
1209 if (ssa_operands_active (fn))
1210 fini_ssa_operands (fn);
1212 fn->gimple_df->default_defs->empty ();
1213 fn->gimple_df->default_defs = NULL;
1214 pt_solution_reset (&fn->gimple_df->escaped);
1215 if (fn->gimple_df->decls_to_pointers != NULL)
1216 delete fn->gimple_df->decls_to_pointers;
1217 fn->gimple_df->decls_to_pointers = NULL;
1218 fn->gimple_df = NULL;
1220 /* We no longer need the edge variable maps. */
1221 redirect_edge_var_map_empty ();
1224 /* Return true if EXPR is a useless type conversion, otherwise return
1225 false. */
1227 bool
1228 tree_ssa_useless_type_conversion (tree expr)
1230 /* If we have an assignment that merely uses a NOP_EXPR to change
1231 the top of the RHS to the type of the LHS and the type conversion
1232 is "safe", then strip away the type conversion so that we can
1233 enter LHS = RHS into the const_and_copies table. */
1234 if (CONVERT_EXPR_P (expr)
1235 || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1236 || TREE_CODE (expr) == NON_LVALUE_EXPR)
1237 return useless_type_conversion_p
1238 (TREE_TYPE (expr),
1239 TREE_TYPE (TREE_OPERAND (expr, 0)));
1241 return false;
1244 /* Strip conversions from EXP according to
1245 tree_ssa_useless_type_conversion and return the resulting
1246 expression. */
1248 tree
1249 tree_ssa_strip_useless_type_conversions (tree exp)
1251 while (tree_ssa_useless_type_conversion (exp))
1252 exp = TREE_OPERAND (exp, 0);
1253 return exp;
1256 /* Return true if T, as SSA_NAME, has an implicit default defined value. */
1258 bool
1259 ssa_defined_default_def_p (tree t)
1261 tree var = SSA_NAME_VAR (t);
1263 if (!var)
1265 /* Parameters get their initial value from the function entry. */
1266 else if (TREE_CODE (var) == PARM_DECL)
1267 return true;
1268 /* When returning by reference the return address is actually a hidden
1269 parameter. */
1270 else if (TREE_CODE (var) == RESULT_DECL && DECL_BY_REFERENCE (var))
1271 return true;
1272 /* Hard register variables get their initial value from the ether. */
1273 else if (VAR_P (var) && DECL_HARD_REGISTER (var))
1274 return true;
1276 return false;
1280 /* Return true if T, an SSA_NAME, has an undefined value. PARTIAL is what
1281 should be returned if the value is only partially undefined. */
1283 bool
1284 ssa_undefined_value_p (tree t, bool partial)
1286 gimple *def_stmt;
1288 if (ssa_defined_default_def_p (t))
1289 return false;
1291 /* The value is undefined iff its definition statement is empty. */
1292 def_stmt = SSA_NAME_DEF_STMT (t);
1293 if (gimple_nop_p (def_stmt))
1294 return true;
1296 /* Check if the complex was not only partially defined. */
1297 if (partial && is_gimple_assign (def_stmt)
1298 && gimple_assign_rhs_code (def_stmt) == COMPLEX_EXPR)
1300 tree rhs1, rhs2;
1302 rhs1 = gimple_assign_rhs1 (def_stmt);
1303 rhs2 = gimple_assign_rhs2 (def_stmt);
1304 return (TREE_CODE (rhs1) == SSA_NAME && ssa_undefined_value_p (rhs1))
1305 || (TREE_CODE (rhs2) == SSA_NAME && ssa_undefined_value_p (rhs2));
1307 return false;
1311 /* Return TRUE iff STMT, a gimple statement, references an undefined
1312 SSA name. */
1314 bool
1315 gimple_uses_undefined_value_p (gimple *stmt)
1317 ssa_op_iter iter;
1318 tree op;
1320 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
1321 if (ssa_undefined_value_p (op))
1322 return true;
1324 return false;
1329 /* If necessary, rewrite the base of the reference tree *TP from
1330 a MEM_REF to a plain or converted symbol. */
1332 static void
1333 maybe_rewrite_mem_ref_base (tree *tp, bitmap suitable_for_renaming)
1335 tree sym;
1337 while (handled_component_p (*tp))
1338 tp = &TREE_OPERAND (*tp, 0);
1339 if (TREE_CODE (*tp) == MEM_REF
1340 && TREE_CODE (TREE_OPERAND (*tp, 0)) == ADDR_EXPR
1341 && (sym = TREE_OPERAND (TREE_OPERAND (*tp, 0), 0))
1342 && DECL_P (sym)
1343 && !TREE_ADDRESSABLE (sym)
1344 && bitmap_bit_p (suitable_for_renaming, DECL_UID (sym))
1345 && is_gimple_reg_type (TREE_TYPE (*tp))
1346 && ! VOID_TYPE_P (TREE_TYPE (*tp)))
1348 if (TREE_CODE (TREE_TYPE (sym)) == VECTOR_TYPE
1349 && useless_type_conversion_p (TREE_TYPE (*tp),
1350 TREE_TYPE (TREE_TYPE (sym)))
1351 && multiple_of_p (sizetype, TREE_OPERAND (*tp, 1),
1352 TYPE_SIZE_UNIT (TREE_TYPE (*tp))))
1354 *tp = build3 (BIT_FIELD_REF, TREE_TYPE (*tp), sym,
1355 TYPE_SIZE (TREE_TYPE (*tp)),
1356 int_const_binop (MULT_EXPR,
1357 bitsize_int (BITS_PER_UNIT),
1358 TREE_OPERAND (*tp, 1)));
1360 else if (TREE_CODE (TREE_TYPE (sym)) == COMPLEX_TYPE
1361 && useless_type_conversion_p (TREE_TYPE (*tp),
1362 TREE_TYPE (TREE_TYPE (sym))))
1364 *tp = build1 (integer_zerop (TREE_OPERAND (*tp, 1))
1365 ? REALPART_EXPR : IMAGPART_EXPR,
1366 TREE_TYPE (*tp), sym);
1368 else if (integer_zerop (TREE_OPERAND (*tp, 1))
1369 && DECL_SIZE (sym) == TYPE_SIZE (TREE_TYPE (*tp)))
1371 if (!useless_type_conversion_p (TREE_TYPE (*tp),
1372 TREE_TYPE (sym)))
1373 *tp = build1 (VIEW_CONVERT_EXPR,
1374 TREE_TYPE (*tp), sym);
1375 else
1376 *tp = sym;
1378 else if (DECL_SIZE (sym)
1379 && TREE_CODE (DECL_SIZE (sym)) == INTEGER_CST
1380 && mem_ref_offset (*tp) >= 0
1381 && wi::leu_p (mem_ref_offset (*tp)
1382 + wi::to_offset (TYPE_SIZE_UNIT (TREE_TYPE (*tp))),
1383 wi::to_offset (DECL_SIZE_UNIT (sym)))
1384 && (! INTEGRAL_TYPE_P (TREE_TYPE (*tp))
1385 || (wi::to_offset (TYPE_SIZE (TREE_TYPE (*tp)))
1386 == TYPE_PRECISION (TREE_TYPE (*tp))))
1387 && wi::umod_trunc (wi::to_offset (TYPE_SIZE (TREE_TYPE (*tp))),
1388 BITS_PER_UNIT) == 0)
1390 *tp = build3 (BIT_FIELD_REF, TREE_TYPE (*tp), sym,
1391 TYPE_SIZE (TREE_TYPE (*tp)),
1392 wide_int_to_tree (bitsizetype,
1393 mem_ref_offset (*tp)
1394 << LOG2_BITS_PER_UNIT));
1399 /* For a tree REF return its base if it is the base of a MEM_REF
1400 that cannot be rewritten into SSA form. Otherwise return NULL_TREE. */
1402 static tree
1403 non_rewritable_mem_ref_base (tree ref)
1405 tree base;
1407 /* A plain decl does not need it set. */
1408 if (DECL_P (ref))
1409 return NULL_TREE;
1411 if (! (base = CONST_CAST_TREE (strip_invariant_refs (ref))))
1413 base = get_base_address (ref);
1414 if (DECL_P (base))
1415 return base;
1416 return NULL_TREE;
1419 /* But watch out for MEM_REFs we cannot lower to a
1420 VIEW_CONVERT_EXPR or a BIT_FIELD_REF. */
1421 if (TREE_CODE (base) == MEM_REF
1422 && TREE_CODE (TREE_OPERAND (base, 0)) == ADDR_EXPR)
1424 tree decl = TREE_OPERAND (TREE_OPERAND (base, 0), 0);
1425 if (! DECL_P (decl))
1426 return NULL_TREE;
1427 if (! is_gimple_reg_type (TREE_TYPE (base))
1428 || VOID_TYPE_P (TREE_TYPE (base)))
1429 return decl;
1430 if ((TREE_CODE (TREE_TYPE (decl)) == VECTOR_TYPE
1431 || TREE_CODE (TREE_TYPE (decl)) == COMPLEX_TYPE)
1432 && useless_type_conversion_p (TREE_TYPE (base),
1433 TREE_TYPE (TREE_TYPE (decl)))
1434 && wi::fits_uhwi_p (mem_ref_offset (base))
1435 && wi::gtu_p (wi::to_offset (TYPE_SIZE_UNIT (TREE_TYPE (decl))),
1436 mem_ref_offset (base))
1437 && multiple_of_p (sizetype, TREE_OPERAND (base, 1),
1438 TYPE_SIZE_UNIT (TREE_TYPE (base))))
1439 return NULL_TREE;
1440 /* For same sizes and zero offset we can use a VIEW_CONVERT_EXPR. */
1441 if (integer_zerop (TREE_OPERAND (base, 1))
1442 && DECL_SIZE (decl) == TYPE_SIZE (TREE_TYPE (base)))
1443 return NULL_TREE;
1444 /* For integral typed extracts we can use a BIT_FIELD_REF. */
1445 if (DECL_SIZE (decl)
1446 && TREE_CODE (DECL_SIZE (decl)) == INTEGER_CST
1447 && mem_ref_offset (base) >= 0
1448 && wi::leu_p (mem_ref_offset (base)
1449 + wi::to_offset (TYPE_SIZE_UNIT (TREE_TYPE (base))),
1450 wi::to_offset (DECL_SIZE_UNIT (decl)))
1451 /* ??? We can't handle bitfield precision extracts without
1452 either using an alternate type for the BIT_FIELD_REF and
1453 then doing a conversion or possibly adjusting the offset
1454 according to endianness. */
1455 && (! INTEGRAL_TYPE_P (TREE_TYPE (base))
1456 || (wi::to_offset (TYPE_SIZE (TREE_TYPE (base)))
1457 == TYPE_PRECISION (TREE_TYPE (base))))
1458 && wi::umod_trunc (wi::to_offset (TYPE_SIZE (TREE_TYPE (base))),
1459 BITS_PER_UNIT) == 0)
1460 return NULL_TREE;
1461 return decl;
1464 return NULL_TREE;
1467 /* For an lvalue tree LHS return true if it cannot be rewritten into SSA form.
1468 Otherwise return true. */
1470 static bool
1471 non_rewritable_lvalue_p (tree lhs)
1473 /* A plain decl is always rewritable. */
1474 if (DECL_P (lhs))
1475 return false;
1477 /* We can re-write REALPART_EXPR and IMAGPART_EXPR sets in
1478 a reasonably efficient manner... */
1479 if ((TREE_CODE (lhs) == REALPART_EXPR
1480 || TREE_CODE (lhs) == IMAGPART_EXPR)
1481 && DECL_P (TREE_OPERAND (lhs, 0)))
1482 return false;
1484 /* ??? The following could be relaxed allowing component
1485 references that do not change the access size. */
1486 if (TREE_CODE (lhs) == MEM_REF
1487 && TREE_CODE (TREE_OPERAND (lhs, 0)) == ADDR_EXPR)
1489 tree decl = TREE_OPERAND (TREE_OPERAND (lhs, 0), 0);
1491 /* A decl that is wrapped inside a MEM-REF that covers
1492 it full is also rewritable. */
1493 if (integer_zerop (TREE_OPERAND (lhs, 1))
1494 && DECL_P (decl)
1495 && DECL_SIZE (decl) == TYPE_SIZE (TREE_TYPE (lhs))
1496 /* If the dynamic type of the decl has larger precision than
1497 the decl itself we can't use the decls type for SSA rewriting. */
1498 && ((! INTEGRAL_TYPE_P (TREE_TYPE (decl))
1499 || compare_tree_int (DECL_SIZE (decl),
1500 TYPE_PRECISION (TREE_TYPE (decl))) == 0)
1501 || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1502 && (TYPE_PRECISION (TREE_TYPE (decl))
1503 >= TYPE_PRECISION (TREE_TYPE (lhs)))))
1504 /* Make sure we are not re-writing non-float copying into float
1505 copying as that can incur normalization. */
1506 && (! FLOAT_TYPE_P (TREE_TYPE (decl))
1507 || types_compatible_p (TREE_TYPE (lhs), TREE_TYPE (decl)))
1508 && (TREE_THIS_VOLATILE (decl) == TREE_THIS_VOLATILE (lhs)))
1509 return false;
1511 /* A vector-insert using a MEM_REF or ARRAY_REF is rewritable
1512 using a BIT_INSERT_EXPR. */
1513 if (DECL_P (decl)
1514 && VECTOR_TYPE_P (TREE_TYPE (decl))
1515 && TYPE_MODE (TREE_TYPE (decl)) != BLKmode
1516 && types_compatible_p (TREE_TYPE (lhs),
1517 TREE_TYPE (TREE_TYPE (decl)))
1518 && tree_fits_uhwi_p (TREE_OPERAND (lhs, 1))
1519 && tree_int_cst_lt (TREE_OPERAND (lhs, 1),
1520 TYPE_SIZE_UNIT (TREE_TYPE (decl)))
1521 && (tree_to_uhwi (TREE_OPERAND (lhs, 1))
1522 % tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (lhs)))) == 0)
1523 return false;
1526 /* A vector-insert using a BIT_FIELD_REF is rewritable using
1527 BIT_INSERT_EXPR. */
1528 if (TREE_CODE (lhs) == BIT_FIELD_REF
1529 && DECL_P (TREE_OPERAND (lhs, 0))
1530 && VECTOR_TYPE_P (TREE_TYPE (TREE_OPERAND (lhs, 0)))
1531 && TYPE_MODE (TREE_TYPE (TREE_OPERAND (lhs, 0))) != BLKmode
1532 && types_compatible_p (TREE_TYPE (lhs),
1533 TREE_TYPE (TREE_TYPE (TREE_OPERAND (lhs, 0))))
1534 && (tree_to_uhwi (TREE_OPERAND (lhs, 2))
1535 % tree_to_uhwi (TYPE_SIZE (TREE_TYPE (lhs)))) == 0)
1536 return false;
1538 return true;
1541 /* When possible, clear TREE_ADDRESSABLE bit or set DECL_GIMPLE_REG_P bit and
1542 mark the variable VAR for conversion into SSA. Return true when updating
1543 stmts is required. */
1545 static void
1546 maybe_optimize_var (tree var, bitmap addresses_taken, bitmap not_reg_needs,
1547 bitmap suitable_for_renaming)
1549 /* Global Variables, result decls cannot be changed. */
1550 if (is_global_var (var)
1551 || TREE_CODE (var) == RESULT_DECL
1552 || bitmap_bit_p (addresses_taken, DECL_UID (var)))
1553 return;
1555 if (TREE_ADDRESSABLE (var)
1556 /* Do not change TREE_ADDRESSABLE if we need to preserve var as
1557 a non-register. Otherwise we are confused and forget to
1558 add virtual operands for it. */
1559 && (!is_gimple_reg_type (TREE_TYPE (var))
1560 || TREE_CODE (TREE_TYPE (var)) == VECTOR_TYPE
1561 || TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE
1562 || !bitmap_bit_p (not_reg_needs, DECL_UID (var))))
1564 TREE_ADDRESSABLE (var) = 0;
1565 if (is_gimple_reg (var))
1566 bitmap_set_bit (suitable_for_renaming, DECL_UID (var));
1567 if (dump_file)
1569 fprintf (dump_file, "No longer having address taken: ");
1570 print_generic_expr (dump_file, var);
1571 fprintf (dump_file, "\n");
1575 if (!DECL_GIMPLE_REG_P (var)
1576 && !bitmap_bit_p (not_reg_needs, DECL_UID (var))
1577 && (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE
1578 || TREE_CODE (TREE_TYPE (var)) == VECTOR_TYPE)
1579 && !TREE_THIS_VOLATILE (var)
1580 && (!VAR_P (var) || !DECL_HARD_REGISTER (var)))
1582 DECL_GIMPLE_REG_P (var) = 1;
1583 bitmap_set_bit (suitable_for_renaming, DECL_UID (var));
1584 if (dump_file)
1586 fprintf (dump_file, "Now a gimple register: ");
1587 print_generic_expr (dump_file, var);
1588 fprintf (dump_file, "\n");
1593 /* Return true when STMT is ASAN mark where second argument is an address
1594 of a local variable. */
1596 static bool
1597 is_asan_mark_p (gimple *stmt)
1599 if (!gimple_call_internal_p (stmt, IFN_ASAN_MARK))
1600 return false;
1602 tree addr = get_base_address (gimple_call_arg (stmt, 1));
1603 if (TREE_CODE (addr) == ADDR_EXPR
1604 && VAR_P (TREE_OPERAND (addr, 0)))
1606 tree var = TREE_OPERAND (addr, 0);
1607 if (lookup_attribute (ASAN_USE_AFTER_SCOPE_ATTRIBUTE,
1608 DECL_ATTRIBUTES (var)))
1609 return false;
1611 unsigned addressable = TREE_ADDRESSABLE (var);
1612 TREE_ADDRESSABLE (var) = 0;
1613 bool r = is_gimple_reg (var);
1614 TREE_ADDRESSABLE (var) = addressable;
1615 return r;
1618 return false;
1621 /* Compute TREE_ADDRESSABLE and DECL_GIMPLE_REG_P for local variables. */
1623 void
1624 execute_update_addresses_taken (void)
1626 basic_block bb;
1627 auto_bitmap addresses_taken;
1628 auto_bitmap not_reg_needs;
1629 auto_bitmap suitable_for_renaming;
1630 tree var;
1631 unsigned i;
1633 timevar_push (TV_ADDRESS_TAKEN);
1635 /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1636 the function body. */
1637 FOR_EACH_BB_FN (bb, cfun)
1639 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1640 gsi_next (&gsi))
1642 gimple *stmt = gsi_stmt (gsi);
1643 enum gimple_code code = gimple_code (stmt);
1644 tree decl;
1646 if (code == GIMPLE_CALL)
1648 if (optimize_atomic_compare_exchange_p (stmt))
1650 /* For __atomic_compare_exchange_N if the second argument
1651 is &var, don't mark var addressable;
1652 if it becomes non-addressable, we'll rewrite it into
1653 ATOMIC_COMPARE_EXCHANGE call. */
1654 tree arg = gimple_call_arg (stmt, 1);
1655 gimple_call_set_arg (stmt, 1, null_pointer_node);
1656 gimple_ior_addresses_taken (addresses_taken, stmt);
1657 gimple_call_set_arg (stmt, 1, arg);
1659 else if (is_asan_mark_p (stmt)
1660 || gimple_call_internal_p (stmt, IFN_GOMP_SIMT_ENTER))
1662 else
1663 gimple_ior_addresses_taken (addresses_taken, stmt);
1665 else
1666 /* Note all addresses taken by the stmt. */
1667 gimple_ior_addresses_taken (addresses_taken, stmt);
1669 /* If we have a call or an assignment, see if the lhs contains
1670 a local decl that requires not to be a gimple register. */
1671 if (code == GIMPLE_ASSIGN || code == GIMPLE_CALL)
1673 tree lhs = gimple_get_lhs (stmt);
1674 if (lhs
1675 && TREE_CODE (lhs) != SSA_NAME
1676 && ((code == GIMPLE_CALL && ! DECL_P (lhs))
1677 || non_rewritable_lvalue_p (lhs)))
1679 decl = get_base_address (lhs);
1680 if (DECL_P (decl))
1681 bitmap_set_bit (not_reg_needs, DECL_UID (decl));
1685 if (gimple_assign_single_p (stmt))
1687 tree rhs = gimple_assign_rhs1 (stmt);
1688 if ((decl = non_rewritable_mem_ref_base (rhs)))
1689 bitmap_set_bit (not_reg_needs, DECL_UID (decl));
1692 else if (code == GIMPLE_CALL)
1694 for (i = 0; i < gimple_call_num_args (stmt); ++i)
1696 tree arg = gimple_call_arg (stmt, i);
1697 if ((decl = non_rewritable_mem_ref_base (arg)))
1698 bitmap_set_bit (not_reg_needs, DECL_UID (decl));
1702 else if (code == GIMPLE_ASM)
1704 gasm *asm_stmt = as_a <gasm *> (stmt);
1705 for (i = 0; i < gimple_asm_noutputs (asm_stmt); ++i)
1707 tree link = gimple_asm_output_op (asm_stmt, i);
1708 tree lhs = TREE_VALUE (link);
1709 if (TREE_CODE (lhs) != SSA_NAME)
1711 decl = get_base_address (lhs);
1712 if (DECL_P (decl)
1713 && (non_rewritable_lvalue_p (lhs)
1714 /* We cannot move required conversions from
1715 the lhs to the rhs in asm statements, so
1716 require we do not need any. */
1717 || !useless_type_conversion_p
1718 (TREE_TYPE (lhs), TREE_TYPE (decl))))
1719 bitmap_set_bit (not_reg_needs, DECL_UID (decl));
1722 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
1724 tree link = gimple_asm_input_op (asm_stmt, i);
1725 if ((decl = non_rewritable_mem_ref_base (TREE_VALUE (link))))
1726 bitmap_set_bit (not_reg_needs, DECL_UID (decl));
1731 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1732 gsi_next (&gsi))
1734 size_t i;
1735 gphi *phi = gsi.phi ();
1737 for (i = 0; i < gimple_phi_num_args (phi); i++)
1739 tree op = PHI_ARG_DEF (phi, i), var;
1740 if (TREE_CODE (op) == ADDR_EXPR
1741 && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL
1742 && DECL_P (var))
1743 bitmap_set_bit (addresses_taken, DECL_UID (var));
1748 /* We cannot iterate over all referenced vars because that can contain
1749 unused vars from BLOCK trees, which causes code generation differences
1750 for -g vs. -g0. */
1751 for (var = DECL_ARGUMENTS (cfun->decl); var; var = DECL_CHAIN (var))
1752 maybe_optimize_var (var, addresses_taken, not_reg_needs,
1753 suitable_for_renaming);
1755 FOR_EACH_VEC_SAFE_ELT (cfun->local_decls, i, var)
1756 maybe_optimize_var (var, addresses_taken, not_reg_needs,
1757 suitable_for_renaming);
1759 /* Operand caches need to be recomputed for operands referencing the updated
1760 variables and operands need to be rewritten to expose bare symbols. */
1761 if (!bitmap_empty_p (suitable_for_renaming))
1763 FOR_EACH_BB_FN (bb, cfun)
1764 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1766 gimple *stmt = gsi_stmt (gsi);
1768 /* Re-write TARGET_MEM_REFs of symbols we want to
1769 rewrite into SSA form. */
1770 if (gimple_assign_single_p (stmt))
1772 tree lhs = gimple_assign_lhs (stmt);
1773 tree rhs, *rhsp = gimple_assign_rhs1_ptr (stmt);
1774 tree sym;
1776 /* Rewrite LHS IMAG/REALPART_EXPR similar to
1777 gimplify_modify_expr_complex_part. */
1778 if ((TREE_CODE (lhs) == IMAGPART_EXPR
1779 || TREE_CODE (lhs) == REALPART_EXPR)
1780 && DECL_P (TREE_OPERAND (lhs, 0))
1781 && bitmap_bit_p (suitable_for_renaming,
1782 DECL_UID (TREE_OPERAND (lhs, 0))))
1784 tree other = make_ssa_name (TREE_TYPE (lhs));
1785 tree lrhs = build1 (TREE_CODE (lhs) == IMAGPART_EXPR
1786 ? REALPART_EXPR : IMAGPART_EXPR,
1787 TREE_TYPE (other),
1788 TREE_OPERAND (lhs, 0));
1789 gimple *load = gimple_build_assign (other, lrhs);
1790 location_t loc = gimple_location (stmt);
1791 gimple_set_location (load, loc);
1792 gimple_set_vuse (load, gimple_vuse (stmt));
1793 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1794 gimple_assign_set_lhs (stmt, TREE_OPERAND (lhs, 0));
1795 gimple_assign_set_rhs_with_ops
1796 (&gsi, COMPLEX_EXPR,
1797 TREE_CODE (lhs) == IMAGPART_EXPR
1798 ? other : gimple_assign_rhs1 (stmt),
1799 TREE_CODE (lhs) == IMAGPART_EXPR
1800 ? gimple_assign_rhs1 (stmt) : other, NULL_TREE);
1801 stmt = gsi_stmt (gsi);
1802 unlink_stmt_vdef (stmt);
1803 update_stmt (stmt);
1804 continue;
1807 /* Rewrite a vector insert via a BIT_FIELD_REF on the LHS
1808 into a BIT_INSERT_EXPR. */
1809 if (TREE_CODE (lhs) == BIT_FIELD_REF
1810 && DECL_P (TREE_OPERAND (lhs, 0))
1811 && bitmap_bit_p (suitable_for_renaming,
1812 DECL_UID (TREE_OPERAND (lhs, 0)))
1813 && VECTOR_TYPE_P (TREE_TYPE (TREE_OPERAND (lhs, 0)))
1814 && TYPE_MODE (TREE_TYPE (TREE_OPERAND (lhs, 0))) != BLKmode
1815 && types_compatible_p (TREE_TYPE (lhs),
1816 TREE_TYPE (TREE_TYPE
1817 (TREE_OPERAND (lhs, 0))))
1818 && (tree_to_uhwi (TREE_OPERAND (lhs, 2))
1819 % tree_to_uhwi (TYPE_SIZE (TREE_TYPE (lhs))) == 0))
1821 tree var = TREE_OPERAND (lhs, 0);
1822 tree val = gimple_assign_rhs1 (stmt);
1823 tree bitpos = TREE_OPERAND (lhs, 2);
1824 gimple_assign_set_lhs (stmt, var);
1825 gimple_assign_set_rhs_with_ops
1826 (&gsi, BIT_INSERT_EXPR, var, val, bitpos);
1827 stmt = gsi_stmt (gsi);
1828 unlink_stmt_vdef (stmt);
1829 update_stmt (stmt);
1830 continue;
1833 /* Rewrite a vector insert using a MEM_REF on the LHS
1834 into a BIT_INSERT_EXPR. */
1835 if (TREE_CODE (lhs) == MEM_REF
1836 && TREE_CODE (TREE_OPERAND (lhs, 0)) == ADDR_EXPR
1837 && (sym = TREE_OPERAND (TREE_OPERAND (lhs, 0), 0))
1838 && DECL_P (sym)
1839 && bitmap_bit_p (suitable_for_renaming, DECL_UID (sym))
1840 && VECTOR_TYPE_P (TREE_TYPE (sym))
1841 && TYPE_MODE (TREE_TYPE (sym)) != BLKmode
1842 && types_compatible_p (TREE_TYPE (lhs),
1843 TREE_TYPE (TREE_TYPE (sym)))
1844 && tree_fits_uhwi_p (TREE_OPERAND (lhs, 1))
1845 && tree_int_cst_lt (TREE_OPERAND (lhs, 1),
1846 TYPE_SIZE_UNIT (TREE_TYPE (sym)))
1847 && (tree_to_uhwi (TREE_OPERAND (lhs, 1))
1848 % tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (lhs)))) == 0)
1850 tree val = gimple_assign_rhs1 (stmt);
1851 tree bitpos
1852 = wide_int_to_tree (bitsizetype,
1853 mem_ref_offset (lhs) * BITS_PER_UNIT);
1854 gimple_assign_set_lhs (stmt, sym);
1855 gimple_assign_set_rhs_with_ops
1856 (&gsi, BIT_INSERT_EXPR, sym, val, bitpos);
1857 stmt = gsi_stmt (gsi);
1858 unlink_stmt_vdef (stmt);
1859 update_stmt (stmt);
1860 continue;
1863 /* We shouldn't have any fancy wrapping of
1864 component-refs on the LHS, but look through
1865 VIEW_CONVERT_EXPRs as that is easy. */
1866 while (TREE_CODE (lhs) == VIEW_CONVERT_EXPR)
1867 lhs = TREE_OPERAND (lhs, 0);
1868 if (TREE_CODE (lhs) == MEM_REF
1869 && TREE_CODE (TREE_OPERAND (lhs, 0)) == ADDR_EXPR
1870 && integer_zerop (TREE_OPERAND (lhs, 1))
1871 && (sym = TREE_OPERAND (TREE_OPERAND (lhs, 0), 0))
1872 && DECL_P (sym)
1873 && !TREE_ADDRESSABLE (sym)
1874 && bitmap_bit_p (suitable_for_renaming, DECL_UID (sym)))
1875 lhs = sym;
1876 else
1877 lhs = gimple_assign_lhs (stmt);
1879 /* Rewrite the RHS and make sure the resulting assignment
1880 is validly typed. */
1881 maybe_rewrite_mem_ref_base (rhsp, suitable_for_renaming);
1882 rhs = gimple_assign_rhs1 (stmt);
1883 if (gimple_assign_lhs (stmt) != lhs
1884 && !useless_type_conversion_p (TREE_TYPE (lhs),
1885 TREE_TYPE (rhs)))
1887 if (gimple_clobber_p (stmt))
1889 rhs = build_constructor (TREE_TYPE (lhs), NULL);
1890 TREE_THIS_VOLATILE (rhs) = 1;
1892 else
1893 rhs = fold_build1 (VIEW_CONVERT_EXPR,
1894 TREE_TYPE (lhs), rhs);
1896 if (gimple_assign_lhs (stmt) != lhs)
1897 gimple_assign_set_lhs (stmt, lhs);
1899 if (gimple_assign_rhs1 (stmt) != rhs)
1901 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1902 gimple_assign_set_rhs_from_tree (&gsi, rhs);
1906 else if (gimple_code (stmt) == GIMPLE_CALL)
1908 unsigned i;
1909 if (optimize_atomic_compare_exchange_p (stmt))
1911 tree expected = gimple_call_arg (stmt, 1);
1912 if (bitmap_bit_p (suitable_for_renaming,
1913 DECL_UID (TREE_OPERAND (expected, 0))))
1915 fold_builtin_atomic_compare_exchange (&gsi);
1916 continue;
1919 else if (is_asan_mark_p (stmt))
1921 tree var = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
1922 if (bitmap_bit_p (suitable_for_renaming, DECL_UID (var)))
1924 unlink_stmt_vdef (stmt);
1925 if (asan_mark_p (stmt, ASAN_MARK_POISON))
1927 gcall *call
1928 = gimple_build_call_internal (IFN_ASAN_POISON, 0);
1929 gimple_call_set_lhs (call, var);
1930 gsi_replace (&gsi, call, GSI_SAME_STMT);
1932 else
1934 /* In ASAN_MARK (UNPOISON, &b, ...) the variable
1935 is uninitialized. Avoid dependencies on
1936 previous out of scope value. */
1937 tree clobber
1938 = build_constructor (TREE_TYPE (var), NULL);
1939 TREE_THIS_VOLATILE (clobber) = 1;
1940 gimple *g = gimple_build_assign (var, clobber);
1941 gsi_replace (&gsi, g, GSI_SAME_STMT);
1943 continue;
1946 else if (gimple_call_internal_p (stmt, IFN_GOMP_SIMT_ENTER))
1947 for (i = 1; i < gimple_call_num_args (stmt); i++)
1949 tree *argp = gimple_call_arg_ptr (stmt, i);
1950 if (*argp == null_pointer_node)
1951 continue;
1952 gcc_assert (TREE_CODE (*argp) == ADDR_EXPR
1953 && VAR_P (TREE_OPERAND (*argp, 0)));
1954 tree var = TREE_OPERAND (*argp, 0);
1955 if (bitmap_bit_p (suitable_for_renaming, DECL_UID (var)))
1956 *argp = null_pointer_node;
1958 for (i = 0; i < gimple_call_num_args (stmt); ++i)
1960 tree *argp = gimple_call_arg_ptr (stmt, i);
1961 maybe_rewrite_mem_ref_base (argp, suitable_for_renaming);
1965 else if (gimple_code (stmt) == GIMPLE_ASM)
1967 gasm *asm_stmt = as_a <gasm *> (stmt);
1968 unsigned i;
1969 for (i = 0; i < gimple_asm_noutputs (asm_stmt); ++i)
1971 tree link = gimple_asm_output_op (asm_stmt, i);
1972 maybe_rewrite_mem_ref_base (&TREE_VALUE (link),
1973 suitable_for_renaming);
1975 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
1977 tree link = gimple_asm_input_op (asm_stmt, i);
1978 maybe_rewrite_mem_ref_base (&TREE_VALUE (link),
1979 suitable_for_renaming);
1983 else if (gimple_debug_bind_p (stmt)
1984 && gimple_debug_bind_has_value_p (stmt))
1986 tree *valuep = gimple_debug_bind_get_value_ptr (stmt);
1987 tree decl;
1988 maybe_rewrite_mem_ref_base (valuep, suitable_for_renaming);
1989 decl = non_rewritable_mem_ref_base (*valuep);
1990 if (decl
1991 && bitmap_bit_p (suitable_for_renaming, DECL_UID (decl)))
1992 gimple_debug_bind_reset_value (stmt);
1995 if (gimple_references_memory_p (stmt)
1996 || is_gimple_debug (stmt))
1997 update_stmt (stmt);
1999 gsi_next (&gsi);
2002 /* Update SSA form here, we are called as non-pass as well. */
2003 if (number_of_loops (cfun) > 1
2004 && loops_state_satisfies_p (LOOP_CLOSED_SSA))
2005 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
2006 else
2007 update_ssa (TODO_update_ssa);
2010 timevar_pop (TV_ADDRESS_TAKEN);
2013 namespace {
2015 const pass_data pass_data_update_address_taken =
2017 GIMPLE_PASS, /* type */
2018 "addressables", /* name */
2019 OPTGROUP_NONE, /* optinfo_flags */
2020 TV_ADDRESS_TAKEN, /* tv_id */
2021 PROP_ssa, /* properties_required */
2022 0, /* properties_provided */
2023 0, /* properties_destroyed */
2024 0, /* todo_flags_start */
2025 TODO_update_address_taken, /* todo_flags_finish */
2028 class pass_update_address_taken : public gimple_opt_pass
2030 public:
2031 pass_update_address_taken (gcc::context *ctxt)
2032 : gimple_opt_pass (pass_data_update_address_taken, ctxt)
2035 /* opt_pass methods: */
2037 }; // class pass_update_address_taken
2039 } // anon namespace
2041 gimple_opt_pass *
2042 make_pass_update_address_taken (gcc::context *ctxt)
2044 return new pass_update_address_taken (ctxt);