gcc/tree-ssa.c

   1 /* Miscellaneous SSA utility functions.
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  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.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "langhooks.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.h"
  34 #include "errors.h"
  35 #include "expr.h"
  36 #include "function.h"
  37 #include "diagnostic.h"
  38 #include "bitmap.h"
  39 #include "tree-flow.h"
  40 #include "tree-gimple.h"
  41 #include "tree-inline.h"
  42 #include "varray.h"
  43 #include "timevar.h"
  44 #include "tree-alias-common.h"
  45 #include "hashtab.h"
  46 #include "tree-dump.h"
  47 #include "tree-pass.h"
  48
  49
  50 /* Remove edge E and remove the corresponding arguments from the PHI nodes
  51    in E's destination block.  */
  52
  53 void
  54 ssa_remove_edge (edge e)
  55 {
  56   tree phi, next;
  57
  58   /* Remove the appropriate PHI arguments in E's destination block.  */
  59   for (phi = phi_nodes (e->dest); phi; phi = next)
  60     {
  61       next = PHI_CHAIN (phi);
  62       remove_phi_arg (phi, e->src);
  63     }
  64
  65   remove_edge (e);
  66 }
  67
  68 /* Remove the corresponding arguments from the PHI nodes in E's
  69    destination block and redirect it to DEST.  Return redirected edge.
  70    The list of removed arguments is stored in PENDING_STMT (e).  */
  71
  72 edge
  73 ssa_redirect_edge (edge e, basic_block dest)
  74 {
  75   tree phi, next;
  76   tree list = NULL, *last = &list;
  77   tree src, dst, node;
  78   int i;
  79
  80   /* Remove the appropriate PHI arguments in E's destination block.  */
  81   for (phi = phi_nodes (e->dest); phi; phi = next)
  82     {
  83       next = PHI_CHAIN (phi);
  84
  85       i = phi_arg_from_edge (phi, e);
  86       if (i < 0)
  87         continue;
  88
  89       src = PHI_ARG_DEF (phi, i);
  90       dst = PHI_RESULT (phi);
  91       node = build_tree_list (dst, src);
  92       *last = node;
  93       last = &TREE_CHAIN (node);
  94
  95       remove_phi_arg_num (phi, i);
  96     }
  97
  98   e = redirect_edge_succ_nodup (e, dest);
  99   PENDING_STMT (e) = list;
 100
 101   return e;
 102 }
 103
 104
 105 /* Return true if the definition of SSA_NAME at block BB is malformed.
 106
 107    STMT is the statement where SSA_NAME is created.
 108
 109    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
 110       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
 111       block in that array slot contains the definition of SSA_NAME.  */
 112
 113 static bool
 114 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
 115             tree stmt)
 116 {
 117   bool err = false;
 118
 119   if (TREE_CODE (ssa_name) != SSA_NAME)
 120     {
 121       error ("Expected an SSA_NAME object");
 122       debug_generic_stmt (ssa_name);
 123       debug_generic_stmt (stmt);
 124     }
 125
 126   if (definition_block[SSA_NAME_VERSION (ssa_name)])
 127     {
 128       error ("SSA_NAME created in two different blocks %i and %i",
 129              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
 130       fprintf (stderr, "SSA_NAME: ");
 131       debug_generic_stmt (ssa_name);
 132       debug_generic_stmt (stmt);
 133       err = true;
 134     }
 135
 136   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
 137
 138   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
 139     {
 140       error ("SSA_NAME_DEF_STMT is wrong");
 141       fprintf (stderr, "SSA_NAME: ");
 142       debug_generic_stmt (ssa_name);
 143       fprintf (stderr, "Expected definition statement:\n");
 144       debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name));
 145       fprintf (stderr, "\nActual definition statement:\n");
 146       debug_generic_stmt (stmt);
 147       err = true;
 148     }
 149
 150   return err;
 151 }
 152
 153
 154 /* Return true if the use of SSA_NAME at statement STMT in block BB is
 155    malformed.
 156
 157    DEF_BB is the block where SSA_NAME was found to be created.
 158
 159    IDOM contains immediate dominator information for the flowgraph.
 160
 161    CHECK_ABNORMAL is true if the caller wants to check whether this use
 162       is flowing through an abnormal edge (only used when checking PHI
 163       arguments).  */
 164
 165 static bool
 166 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
 167             tree stmt, bool check_abnormal)
 168 {
 169   bool err = false;
 170
 171   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)))
 172     ; /* Nothing to do.  */
 173   else if (!def_bb)
 174     {
 175       error ("Missing definition");
 176       err = true;
 177     }
 178   else if (bb != def_bb
 179            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 180     {
 181       error ("Definition in block %i does not dominate use in block %i",
 182              def_bb->index, bb->index);
 183       err = true;
 184     }
 185
 186   if (check_abnormal
 187       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 188     {
 189       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
 190       err = true;
 191     }
 192
 193   if (err)
 194     {
 195       fprintf (stderr, "for SSA_NAME: ");
 196       debug_generic_stmt (ssa_name);
 197       fprintf (stderr, "in statement:\n");
 198       debug_generic_stmt (stmt);
 199     }
 200
 201   return err;
 202 }
 203
 204
 205 /* Return true if any of the arguments for PHI node PHI at block BB is
 206    malformed.
 207
 208    IDOM contains immediate dominator information for the flowgraph.
 209
 210    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
 211       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
 212       block in that array slot contains the definition of SSA_NAME.  */
 213
 214 static bool
 215 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
 216 {
 217   edge e;
 218   bool err = false;
 219   int i, phi_num_args = PHI_NUM_ARGS (phi);
 220
 221   /* Mark all the incoming edges.  */
 222   for (e = bb->pred; e; e = e->pred_next)
 223     e->aux = (void *) 1;
 224
 225   for (i = 0; i < phi_num_args; i++)
 226     {
 227       tree op = PHI_ARG_DEF (phi, i);
 228
 229       e = PHI_ARG_EDGE (phi, i);
 230
 231       if (TREE_CODE (op) == SSA_NAME)
 232         err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
 233                            phi, e->flags & EDGE_ABNORMAL);
 234
 235       if (e->dest != bb)
 236         {
 237           error ("Wrong edge %d->%d for PHI argument\n",
 238                  e->src->index, e->dest->index, bb->index);
 239           err = true;
 240         }
 241
 242       if (e->aux == (void *) 0)
 243         {
 244           error ("PHI argument flowing through dead edge %d->%d\n",
 245                  e->src->index, e->dest->index);
 246           err = true;
 247         }
 248
 249       if (e->aux == (void *) 2)
 250         {
 251           error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
 252                  e->dest->index);
 253           err = true;
 254         }
 255
 256       if (err)
 257         {
 258           fprintf (stderr, "PHI argument\n");
 259           debug_generic_stmt (op);
 260         }
 261
 262       e->aux = (void *) 2;
 263     }
 264
 265   for (e = bb->pred; e; e = e->pred_next)
 266     {
 267       if (e->aux != (void *) 2)
 268         {
 269           error ("No argument flowing through edge %d->%d\n", e->src->index,
 270                  e->dest->index);
 271           err = true;
 272         }
 273       e->aux = (void *) 0;
 274     }
 275
 276   if (err)
 277     {
 278       fprintf (stderr, "for PHI node\n");
 279       debug_generic_stmt (phi);
 280     }
 281
 282
 283   return err;
 284 }
 285
 286
 287 /* Verify common invariants in the SSA web.
 288    TODO: verify the variable annotations.  */
 289
 290 void
 291 verify_ssa (void)
 292 {
 293   bool err = false;
 294   basic_block bb;
 295   basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
 296
 297   timevar_push (TV_TREE_SSA_VERIFY);
 298
 299   calculate_dominance_info (CDI_DOMINATORS);
 300
 301   /* Verify and register all the SSA_NAME definitions found in the
 302      function.  */
 303   FOR_EACH_BB (bb)
 304     {
 305       tree phi;
 306       block_stmt_iterator bsi;
 307
 308       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 309         err |= verify_def (bb, definition_block, PHI_RESULT (phi), phi);
 310
 311       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 312         {
 313           tree stmt;
 314           stmt_ann_t ann;
 315           unsigned int j;
 316           v_may_def_optype v_may_defs;
 317           v_must_def_optype v_must_defs;
 318           def_optype defs;
 319
 320           stmt = bsi_stmt (bsi);
 321           ann = stmt_ann (stmt);
 322           get_stmt_operands (stmt);
 323
 324           v_may_defs = V_MAY_DEF_OPS (ann);
 325           if (ann->makes_aliased_stores && NUM_V_MAY_DEFS (v_may_defs) == 0)
 326             error ("Makes aliased stores, but no V_MAY_DEFS");
 327
 328           for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++)
 329             {
 330               tree op = V_MAY_DEF_RESULT (v_may_defs, j);
 331               if (is_gimple_reg (op))
 332                 {
 333                   error ("Found a virtual definition for a GIMPLE register");
 334                   debug_generic_stmt (op);
 335                   debug_generic_stmt (stmt);
 336                   err = true;
 337                 }
 338               err |= verify_def (bb, definition_block, op, stmt);
 339             }
 340
 341           v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
 342           for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++)
 343             {
 344               tree op = V_MUST_DEF_OP (v_must_defs, j);
 345               if (is_gimple_reg (op))
 346                 {
 347                   error ("Found a virtual must-def for a GIMPLE register");
 348                   debug_generic_stmt (op);
 349                   debug_generic_stmt (stmt);
 350                   err = true;
 351                 }
 352               err |= verify_def (bb, definition_block, op, stmt);
 353             }
 354
 355           defs = DEF_OPS (ann);
 356           for (j = 0; j < NUM_DEFS (defs); j++)
 357             {
 358               tree op = DEF_OP (defs, j);
 359               if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op))
 360                 {
 361                   error ("Found a real definition for a non-GIMPLE register");
 362                   debug_generic_stmt (op);
 363                   debug_generic_stmt (stmt);
 364                   err = true;
 365                 }
 366               err |= verify_def (bb, definition_block, op, stmt);
 367             }
 368         }
 369     }
 370
 371
 372   /* Now verify all the uses and make sure they agree with the definitions
 373      found in the previous pass.  */
 374   FOR_EACH_BB (bb)
 375     {
 376       edge e;
 377       tree phi;
 378       block_stmt_iterator bsi;
 379
 380       /* Make sure that all edges have a clear 'aux' field.  */
 381       for (e = bb->pred; e; e = e->pred_next)
 382         {
 383           if (e->aux)
 384             {
 385               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
 386                       e->dest->index);
 387               err = true;
 388             }
 389         }
 390
 391       /* Verify the arguments for every PHI node in the block.  */
 392       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 393         err |= verify_phi_args (phi, bb, definition_block);
 394
 395       /* Now verify all the uses and vuses in every statement of the block.
 396
 397          Remember, the RHS of a V_MAY_DEF is a use as well.  */
 398       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 399         {
 400           tree stmt = bsi_stmt (bsi);
 401           stmt_ann_t ann = stmt_ann (stmt);
 402           unsigned int j;
 403           vuse_optype vuses;
 404           v_may_def_optype v_may_defs;
 405           use_optype uses;
 406
 407           vuses = VUSE_OPS (ann);
 408           for (j = 0; j < NUM_VUSES (vuses); j++)
 409             {
 410               tree op = VUSE_OP (vuses, j);
 411
 412               if (is_gimple_reg (op))
 413                 {
 414                   error ("Found a virtual use for a GIMPLE register");
 415                   debug_generic_stmt (op);
 416                   debug_generic_stmt (stmt);
 417                   err = true;
 418                 }
 419               err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 420                                  op, stmt, false);
 421             }
 422
 423           v_may_defs = V_MAY_DEF_OPS (ann);
 424           for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++)
 425             {
 426               tree op = V_MAY_DEF_OP (v_may_defs, j);
 427
 428               if (is_gimple_reg (op))
 429                 {
 430                   error ("Found a virtual use for a GIMPLE register");
 431                   debug_generic_stmt (op);
 432                   debug_generic_stmt (stmt);
 433                   err = true;
 434                 }
 435               err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 436                                  op, stmt, false);
 437             }
 438
 439           uses = USE_OPS (ann);
 440           for (j = 0; j < NUM_USES (uses); j++)
 441             {
 442               tree op = USE_OP (uses, j);
 443
 444               if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op))
 445                 {
 446                   error ("Found a real use of a non-GIMPLE register");
 447                   debug_generic_stmt (op);
 448                   debug_generic_stmt (stmt);
 449                   err = true;
 450                 }
 451               err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 452                                  op, stmt, false);
 453             }
 454         }
 455     }
 456
 457   free (definition_block);
 458
 459   timevar_pop (TV_TREE_SSA_VERIFY);
 460
 461   if (err)
 462     internal_error ("verify_ssa failed.");
 463 }
 464
 465
 466 /* Set the USED bit in the annotation for T.  */
 467
 468 void
 469 set_is_used (tree t)
 470 {
 471   while (1)
 472     {
 473       if (SSA_VAR_P (t))
 474         break;
 475
 476       if (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR)
 477         t = TREE_OPERAND (t, 0);
 478       else
 479         while (handled_component_p (t))
 480           t = TREE_OPERAND (t, 0);
 481     }
 482
 483   if (TREE_CODE (t) == SSA_NAME)
 484     t = SSA_NAME_VAR (t);
 485
 486   var_ann (t)->used = 1;
 487 }
 488
 489
 490 /* Initialize global DFA and SSA structures.  */
 491
 492 void
 493 init_tree_ssa (void)
 494 {
 495   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
 496   call_clobbered_vars = BITMAP_XMALLOC ();
 497   addressable_vars = BITMAP_XMALLOC ();
 498   init_ssa_operands ();
 499   init_ssanames ();
 500   init_phinodes ();
 501   global_var = NULL_TREE;
 502   aliases_computed_p = false;
 503 }
 504
 505
 506 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 507
 508 void
 509 delete_tree_ssa (void)
 510 {
 511   size_t i;
 512   basic_block bb;
 513   block_stmt_iterator bsi;
 514
 515   /* Remove annotations from every tree in the function.  */
 516   FOR_EACH_BB (bb)
 517     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 518       bsi_stmt (bsi)->common.ann = NULL;
 519
 520   /* Remove annotations from every referenced variable.  */
 521   if (referenced_vars)
 522     {
 523       for (i = 0; i < num_referenced_vars; i++)
 524         referenced_var (i)->common.ann = NULL;
 525       referenced_vars = NULL;
 526     }
 527
 528   fini_ssanames ();
 529   fini_phinodes ();
 530   fini_ssa_operands ();
 531
 532   global_var = NULL_TREE;
 533   BITMAP_XFREE (call_clobbered_vars);
 534   call_clobbered_vars = NULL;
 535   aliases_computed_p = false;
 536   BITMAP_XFREE (addressable_vars);
 537   addressable_vars = NULL;
 538 }
 539
 540
 541 /* Return true if EXPR is a useless type conversion, otherwise return
 542    false.  */
 543
 544 bool
 545 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 546 {
 547   /* If the inner and outer types are effectively the same, then
 548      strip the type conversion and enter the equivalence into
 549      the table.  */
 550   if (inner_type == outer_type
 551      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
 552     return true;
 553
 554   /* If both types are pointers and the outer type is a (void *), then
 555      the conversion is not necessary.  The opposite is not true since
 556      that conversion would result in a loss of information if the
 557      equivalence was used.  Consider an indirect function call where
 558      we need to know the exact type of the function to correctly
 559      implement the ABI.  */
 560   else if (POINTER_TYPE_P (inner_type)
 561            && POINTER_TYPE_P (outer_type)
 562            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 563     return true;
 564
 565   /* Pointers and references are equivalent once we get to GENERIC,
 566      so strip conversions that just switch between them.  */
 567   else if (POINTER_TYPE_P (inner_type)
 568            && POINTER_TYPE_P (outer_type)
 569            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 570                                              TREE_TYPE (outer_type)))
 571     return true;
 572
 573   /* If both the inner and outer types are integral types, then the
 574      conversion is not necessary if they have the same mode and
 575      signedness and precision, and both or neither are boolean.  Some
 576      code assumes an invariant that boolean types stay boolean and do
 577      not become 1-bit bit-field types.  Note that types with precision
 578      not using all bits of the mode (such as bit-field types in C)
 579      mean that testing of precision is necessary.  */
 580   else if (INTEGRAL_TYPE_P (inner_type)
 581            && INTEGRAL_TYPE_P (outer_type)
 582            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 583            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 584            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 585     {
 586       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
 587       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
 588       if (first_boolean == second_boolean)
 589         return true;
 590     }
 591
 592   /* Recurse for complex types.  */
 593   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 594            && TREE_CODE (outer_type) == COMPLEX_TYPE
 595            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 596                                                   TREE_TYPE (inner_type)))
 597     return true;
 598
 599   return false;
 600 }
 601
 602 /* Return true if EXPR is a useless type conversion, otherwise return
 603    false.  */
 604
 605 bool
 606 tree_ssa_useless_type_conversion (tree expr)
 607 {
 608   /* If we have an assignment that merely uses a NOP_EXPR to change
 609      the top of the RHS to the type of the LHS and the type conversion
 610      is "safe", then strip away the type conversion so that we can
 611      enter LHS = RHS into the const_and_copies table.  */
 612   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
 613       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
 614       || TREE_CODE (expr) == NON_LVALUE_EXPR)
 615     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 616                                                TREE_TYPE (TREE_OPERAND (expr,
 617                                                                         0)));
 618
 619
 620   return false;
 621 }
 622
 623
 624 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 625    described in walk_use_def_chains.  VISITED is a bitmap used to mark
 626    visited SSA_NAMEs to avoid infinite loops.  */
 627
 628 static bool
 629 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 630                        bitmap visited)
 631 {
 632   tree def_stmt;
 633
 634   if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
 635     return false;
 636
 637   bitmap_set_bit (visited, SSA_NAME_VERSION (var));
 638
 639   def_stmt = SSA_NAME_DEF_STMT (var);
 640
 641   if (TREE_CODE (def_stmt) != PHI_NODE)
 642     {
 643       /* If we reached the end of the use-def chain, call FN.  */
 644       return (*fn) (var, def_stmt, data);
 645     }
 646   else
 647     {
 648       int i;
 649
 650       /* Otherwise, follow use-def links out of each PHI argument and call
 651          FN after visiting each one.  */
 652       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 653         {
 654           tree arg = PHI_ARG_DEF (def_stmt, i);
 655           if (TREE_CODE (arg) == SSA_NAME
 656               && walk_use_def_chains_1 (arg, fn, data, visited))
 657             return true;
 658
 659           if ((*fn) (arg, def_stmt, data))
 660             return true;
 661         }
 662     }
 663   return false;
 664 }
 665
 666
 667
 668 /* Walk use-def chains starting at the SSA variable VAR.  Call function FN
 669    at each reaching definition found.  FN takes three arguments: VAR, its
 670    defining statement (DEF_STMT) and a generic pointer to whatever state
 671    information that FN may want to maintain (DATA).  FN is able to stop the
 672    walk by returning true, otherwise in order to continue the walk, FN
 673    should return false.
 674
 675    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 676    different.  For each argument ARG of the PHI node, this function will:
 677
 678         1- Walk the use-def chains for ARG.
 679         2- Call (*FN) (ARG, PHI, DATA).
 680
 681    Note how the first argument to FN is no longer the original variable
 682    VAR, but the PHI argument currently being examined.  If FN wants to get
 683    at VAR, it should call PHI_RESULT (PHI).  */
 684
 685 void
 686 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data)
 687 {
 688   tree def_stmt;
 689
 690 #if defined ENABLE_CHECKING
 691   if (TREE_CODE (var) != SSA_NAME)
 692     abort ();
 693 #endif
 694
 695   def_stmt = SSA_NAME_DEF_STMT (var);
 696
 697   /* We only need to recurse if the reaching definition comes from a PHI
 698      node.  */
 699   if (TREE_CODE (def_stmt) != PHI_NODE)
 700     (*fn) (var, def_stmt, data);
 701   else
 702     {
 703       bitmap visited = BITMAP_XMALLOC ();
 704       walk_use_def_chains_1 (var, fn, data, visited);
 705       BITMAP_XFREE (visited);
 706     }
 707 }
 708
 709 /* Replaces VAR with REPL in memory reference expression *X in
 710    statement STMT.  */
 711
 712 static void
 713 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
 714 {
 715   tree new_var, ass_stmt, addr_var;
 716   basic_block bb;
 717   block_stmt_iterator bsi;
 718
 719   /* There is nothing special to handle in the other cases.  */
 720   if (TREE_CODE (repl) != ADDR_EXPR)
 721     return;
 722   addr_var = TREE_OPERAND (repl, 0);
 723
 724   while (TREE_CODE (*x) == ARRAY_REF
 725          || TREE_CODE (*x) == COMPONENT_REF
 726          || TREE_CODE (*x) == BIT_FIELD_REF)
 727     x = &TREE_OPERAND (*x, 0);
 728
 729   if (TREE_CODE (*x) != INDIRECT_REF
 730       || TREE_OPERAND (*x, 0) != var)
 731     return;
 732
 733   modify_stmt (stmt);
 734   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
 735     {
 736       *x = addr_var;
 737       mark_new_vars_to_rename (stmt, vars_to_rename);
 738       return;
 739     }
 740
 741   /* Frontends sometimes produce expressions like *&a instead of a[0].
 742      Create a temporary variable to handle this case.  */
 743   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
 744   new_var = duplicate_ssa_name (var, ass_stmt);
 745   TREE_OPERAND (*x, 0) = new_var;
 746   TREE_OPERAND (ass_stmt, 0) = new_var;
 747
 748   bb = bb_for_stmt (stmt);
 749   tree_block_label (bb);
 750   bsi = bsi_after_labels (bb);
 751   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
 752
 753   mark_new_vars_to_rename (stmt, vars_to_rename);
 754 }
 755
 756 /* Replaces immediate uses of VAR by REPL.  */
 757
 758 static void
 759 replace_immediate_uses (tree var, tree repl)
 760 {
 761   use_optype uses;
 762   vuse_optype vuses;
 763   v_may_def_optype v_may_defs;
 764   int i, j, n;
 765   dataflow_t df;
 766   tree stmt;
 767   stmt_ann_t ann;
 768   bool mark_new_vars;
 769
 770   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 771   n = num_immediate_uses (df);
 772
 773   for (i = 0; i < n; i++)
 774     {
 775       stmt = immediate_use (df, i);
 776       ann = stmt_ann (stmt);
 777
 778       if (TREE_CODE (stmt) == PHI_NODE)
 779         {
 780           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
 781             if (PHI_ARG_DEF (stmt, j) == var)
 782               {
 783                 SET_PHI_ARG_DEF (stmt, j, repl);
 784                 if (TREE_CODE (repl) == SSA_NAME
 785                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
 786                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
 787               }
 788
 789           continue;
 790         }
 791
 792       get_stmt_operands (stmt);
 793       mark_new_vars = false;
 794       if (is_gimple_reg (SSA_NAME_VAR (var)))
 795         {
 796           if (TREE_CODE (stmt) == MODIFY_EXPR)
 797             {
 798               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
 799               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
 800             }
 801
 802           uses = USE_OPS (ann);
 803           for (j = 0; j < (int) NUM_USES (uses); j++)
 804             if (USE_OP (uses, j) == var)
 805               {
 806                 propagate_value (USE_OP_PTR (uses, j), repl);
 807                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
 808               }
 809         }
 810       else
 811         {
 812           vuses = VUSE_OPS (ann);
 813           for (j = 0; j < (int) NUM_VUSES (vuses); j++)
 814             if (VUSE_OP (vuses, j) == var)
 815               propagate_value (VUSE_OP_PTR (vuses, j), repl);
 816
 817           v_may_defs = V_MAY_DEF_OPS (ann);
 818           for (j = 0; j < (int) NUM_V_MAY_DEFS (v_may_defs); j++)
 819             if (V_MAY_DEF_OP (v_may_defs, j) == var)
 820               propagate_value (V_MAY_DEF_OP_PTR (v_may_defs, j), repl);
 821         }
 822
 823       /* If REPL is a pointer, it may have different memory tags associated
 824          with it.  For instance, VAR may have had a name tag while REPL
 825          only had a type tag.  In these cases, the virtual operands (if
 826          any) in the statement will refer to different symbols which need
 827          to be renamed.  */
 828       if (mark_new_vars)
 829         mark_new_vars_to_rename (stmt, vars_to_rename);
 830       else
 831         modify_stmt (stmt);
 832     }
 833 }
 834
 835 /* Gets the value VAR is equivalent to according to EQ_TO.  */
 836
 837 static tree
 838 get_eq_name (tree *eq_to, tree var)
 839 {
 840   unsigned ver;
 841   tree val = var;
 842
 843   while (TREE_CODE (val) == SSA_NAME)
 844     {
 845       ver = SSA_NAME_VERSION (val);
 846       if (!eq_to[ver])
 847         break;
 848
 849       val = eq_to[ver];
 850     }
 851
 852   while (TREE_CODE (var) == SSA_NAME)
 853     {
 854       ver = SSA_NAME_VERSION (var);
 855       if (!eq_to[ver])
 856         break;
 857
 858       var = eq_to[ver];
 859       eq_to[ver] = val;
 860     }
 861
 862   return val;
 863 }
 864
 865 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
 866    its result is redundant to to EQ_TO array.  */
 867
 868 static void
 869 check_phi_redundancy (tree phi, tree *eq_to)
 870 {
 871   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
 872   unsigned i, ver = SSA_NAME_VERSION (res), n;
 873   dataflow_t df;
 874
 875   /* It is unlikely that such large phi node would be redundant.  */
 876   if (PHI_NUM_ARGS (phi) > 16)
 877     return;
 878
 879   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 880     {
 881       def = PHI_ARG_DEF (phi, i);
 882
 883       if (TREE_CODE (def) == SSA_NAME)
 884         {
 885           def = get_eq_name (eq_to, def);
 886           if (def == res)
 887             continue;
 888         }
 889
 890       if (val
 891           && !operand_equal_p (val, def, 0))
 892         return;
 893
 894       val = def;
 895     }
 896
 897   /* At least one of the arguments should not be equal to the result, or
 898      something strange is happening.  */
 899   if (!val)
 900     abort ();
 901
 902   if (get_eq_name (eq_to, res) == val)
 903     return;
 904
 905   if (!may_propagate_copy (res, val))
 906     return;
 907
 908   eq_to[ver] = val;
 909
 910   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
 911   n = num_immediate_uses (df);
 912
 913   for (i = 0; i < n; i++)
 914     {
 915       stmt = immediate_use (df, i);
 916
 917       if (TREE_CODE (stmt) == PHI_NODE)
 918         check_phi_redundancy (stmt, eq_to);
 919     }
 920 }
 921
 922 /* Removes redundant phi nodes.
 923
 924    A redundant PHI node is a PHI node where all of its PHI arguments
 925    are the same value, excluding any PHI arguments which are the same
 926    as the PHI result.
 927
 928    A redundant PHI node is effectively a copy, so we forward copy propagate
 929    which removes all uses of the destination of the PHI node then
 930    finally we delete the redundant PHI node.
 931
 932    Note that if we can not copy propagate the PHI node, then the PHI
 933    will not be removed.  Thus we do not have to worry about dependencies
 934    between PHIs and the problems serializing PHIs into copies creates.
 935
 936    The most important effect of this pass is to remove degenerate PHI
 937    nodes created by removing unreachable code.  */
 938
 939 void
 940 kill_redundant_phi_nodes (void)
 941 {
 942   tree *eq_to;
 943   unsigned i, old_num_ssa_names;
 944   basic_block bb;
 945   tree phi, var, repl, stmt;
 946
 947   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
 948      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
 949      other value, it may be necessary to follow the chain till the final value.
 950      We perform path shortening (replacing the entries of the EQ_TO array with
 951      heads of these chains) whenever we access the field to prevent quadratic
 952      complexity (probably would not occur in practice anyway, but let us play
 953      it safe).  */
 954   eq_to = xcalloc (num_ssa_names, sizeof (tree));
 955
 956   /* We have had cases where computing immediate uses takes a
 957      significant amount of compile time.  If we run into such
 958      problems here, we may want to only compute immediate uses for
 959      a subset of all the SSA_NAMEs instead of computing it for
 960      all of the SSA_NAMEs.  */
 961   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
 962   old_num_ssa_names = num_ssa_names;
 963
 964   FOR_EACH_BB (bb)
 965     {
 966       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 967         {
 968           var = PHI_RESULT (phi);
 969           check_phi_redundancy (phi, eq_to);
 970         }
 971     }
 972
 973   /* Now propagate the values.  */
 974   for (i = 0; i < old_num_ssa_names; i++)
 975     {
 976       if (!ssa_name (i))
 977         continue;
 978
 979       repl = get_eq_name (eq_to, ssa_name (i));
 980       if (repl != ssa_name (i))
 981         replace_immediate_uses (ssa_name (i), repl);
 982     }
 983
 984   /* And remove the dead phis.  */
 985   for (i = 0; i < old_num_ssa_names; i++)
 986     {
 987       if (!ssa_name (i))
 988         continue;
 989
 990       repl = get_eq_name (eq_to, ssa_name (i));
 991       if (repl != ssa_name (i))
 992         {
 993           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
 994           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
 995         }
 996     }
 997
 998   free_df ();
 999   free (eq_to);
1000 }
1001
1002 struct tree_opt_pass pass_redundant_phi =
1003 {
1004   "redphi",                             /* name */
1005   NULL,                                 /* gate */
1006   kill_redundant_phi_nodes,             /* execute */
1007   NULL,                                 /* sub */
1008   NULL,                                 /* next */
1009   0,                                    /* static_pass_number */
1010   0,                                    /* tv_id */
1011   PROP_cfg | PROP_ssa,                  /* properties_required */
1012   0,                                    /* properties_provided */
1013   0,                                    /* properties_destroyed */
1014   0,                                    /* todo_flags_start */
1015   TODO_dump_func | TODO_rename_vars
1016     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
1017 };
1018 \f
1019 /* Emit warnings for uninitialized variables.  This is done in two passes.
1020
1021    The first pass notices real uses of SSA names with default definitions.
1022    Such uses are unconditionally uninitialized, and we can be certain that
1023    such a use is a mistake.  This pass is run before most optimizations,
1024    so that we catch as many as we can.
1025
1026    The second pass follows PHI nodes to find uses that are potentially
1027    uninitialized.  In this case we can't necessarily prove that the use
1028    is really uninitialized.  This pass is run after most optimizations,
1029    so that we thread as many jumps and possible, and delete as much dead
1030    code as possible, in order to reduce false positives.  We also look
1031    again for plain uninitialized variables, since optimization may have
1032    changed conditionally uninitialized to unconditionally uninitialized.  */
1033
1034 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1035    warning text is in MSGID and LOCUS may contain a location or be null.  */
1036
1037 static void
1038 warn_uninit (tree t, const char *msgid, location_t *locus)
1039 {
1040   tree var = SSA_NAME_VAR (t);
1041   tree def = SSA_NAME_DEF_STMT (t);
1042
1043   /* Default uses (indicated by an empty definition statement),
1044      are uninitialized.  */
1045   if (!IS_EMPTY_STMT (def))
1046     return;
1047
1048   /* Except for PARMs of course, which are always initialized.  */
1049   if (TREE_CODE (var) == PARM_DECL)
1050     return;
1051
1052   /* Hard register variables get their initial value from the ether.  */
1053   if (DECL_HARD_REGISTER (var))
1054     return;
1055
1056   /* TREE_NO_WARNING either means we already warned, or the front end
1057      wishes to suppress the warning.  */
1058   if (TREE_NO_WARNING (var))
1059     return;
1060
1061   if (!locus)
1062     locus = &DECL_SOURCE_LOCATION (var);
1063   warning (msgid, locus, var);
1064   TREE_NO_WARNING (var) = 1;
1065 }
1066
1067 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1068    and warn about them.  */
1069
1070 static tree
1071 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1072 {
1073   location_t *locus = data;
1074   tree t = *tp;
1075
1076   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1077   if (TREE_CODE (t) == SSA_NAME)
1078     {
1079       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1080       *walk_subtrees = 0;
1081     }
1082   else if (DECL_P (t) || TYPE_P (t))
1083     *walk_subtrees = 0;
1084
1085   return NULL_TREE;
1086 }
1087
1088 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1089    and warn about them.  */
1090
1091 static void
1092 warn_uninitialized_phi (tree phi)
1093 {
1094   int i, n = PHI_NUM_ARGS (phi);
1095
1096   /* Don't look at memory tags.  */
1097   if (!is_gimple_reg (PHI_RESULT (phi)))
1098     return;
1099
1100   for (i = 0; i < n; ++i)
1101     {
1102       tree op = PHI_ARG_DEF (phi, i);
1103       if (TREE_CODE (op) == SSA_NAME)
1104         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1105                      NULL);
1106     }
1107 }
1108
1109 static void
1110 execute_early_warn_uninitialized (void)
1111 {
1112   block_stmt_iterator bsi;
1113   basic_block bb;
1114
1115   FOR_EACH_BB (bb)
1116     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1117       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1118                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1119 }
1120
1121 static void
1122 execute_late_warn_uninitialized (void)
1123 {
1124   basic_block bb;
1125   tree phi;
1126
1127   /* Re-do the plain uninitialized variable check, as optimization may have
1128      straightened control flow.  Do this first so that we don't accidentally
1129      get a "may be" warning when we'd have seen an "is" warning later.  */
1130   execute_early_warn_uninitialized ();
1131
1132   FOR_EACH_BB (bb)
1133     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1134       warn_uninitialized_phi (phi);
1135 }
1136
1137 static bool
1138 gate_warn_uninitialized (void)
1139 {
1140   return warn_uninitialized != 0;
1141 }
1142
1143 struct tree_opt_pass pass_early_warn_uninitialized =
1144 {
1145   NULL,                                 /* name */
1146   gate_warn_uninitialized,              /* gate */
1147   execute_early_warn_uninitialized,     /* execute */
1148   NULL,                                 /* sub */
1149   NULL,                                 /* next */
1150   0,                                    /* static_pass_number */
1151   0,                                    /* tv_id */
1152   PROP_ssa,                             /* properties_required */
1153   0,                                    /* properties_provided */
1154   0,                                    /* properties_destroyed */
1155   0,                                    /* todo_flags_start */
1156   0                                     /* todo_flags_finish */
1157 };
1158
1159 struct tree_opt_pass pass_late_warn_uninitialized =
1160 {
1161   NULL,                                 /* name */
1162   gate_warn_uninitialized,              /* gate */
1163   execute_late_warn_uninitialized,      /* execute */
1164   NULL,                                 /* sub */
1165   NULL,                                 /* next */
1166   0,                                    /* static_pass_number */
1167   0,                                    /* tv_id */
1168   PROP_ssa,                             /* properties_required */
1169   0,                                    /* properties_provided */
1170   0,                                    /* properties_destroyed */
1171   0,                                    /* todo_flags_start */
1172   0                                     /* todo_flags_finish */
1173 };