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   init_ssa_operands ();
 498   init_ssanames ();
 499   init_phinodes ();
 500   vn_init ();
 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   vn_delete ();
 532
 533   global_var = NULL_TREE;
 534   BITMAP_XFREE (call_clobbered_vars);
 535   call_clobbered_vars = NULL;
 536   aliases_computed_p = false;
 537 }
 538
 539
 540 /* Return true if EXPR is a useless type conversion, otherwise return
 541    false.  */
 542
 543 bool
 544 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 545 {
 546   /* If the inner and outer types are effectively the same, then
 547      strip the type conversion and enter the equivalence into
 548      the table.  */
 549   if (inner_type == outer_type
 550      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
 551     return true;
 552
 553   /* If both types are pointers and the outer type is a (void *), then
 554      the conversion is not necessary.  The opposite is not true since
 555      that conversion would result in a loss of information if the
 556      equivalence was used.  Consider an indirect function call where
 557      we need to know the exact type of the function to correctly
 558      implement the ABI.  */
 559   else if (POINTER_TYPE_P (inner_type)
 560            && POINTER_TYPE_P (outer_type)
 561            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 562     return true;
 563
 564   /* Pointers and references are equivalent once we get to GENERIC,
 565      so strip conversions that just switch between them.  */
 566   else if (POINTER_TYPE_P (inner_type)
 567            && POINTER_TYPE_P (outer_type)
 568            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 569                                              TREE_TYPE (outer_type)))
 570     return true;
 571
 572   /* If both the inner and outer types are integral types, then the
 573      conversion is not necessary if they have the same mode and
 574      signedness and precision.  Note that type _Bool can have size of
 575      4 (only happens on powerpc-darwin right now but can happen on any
 576      target that defines BOOL_TYPE_SIZE to be INT_TYPE_SIZE) and a
 577      precision of 1 while unsigned int is the same expect for a
 578      precision of 4 so testing of precision is necessary.  */
 579   else if (INTEGRAL_TYPE_P (inner_type)
 580            && INTEGRAL_TYPE_P (outer_type)
 581            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 582            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 583            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 584     return true;
 585
 586   /* Recurse for complex types.  */
 587   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 588            && TREE_CODE (outer_type) == COMPLEX_TYPE
 589            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 590                                                   TREE_TYPE (inner_type)))
 591     return true;
 592
 593   return false;
 594 }
 595
 596 /* Return true if EXPR is a useless type conversion, otherwise return
 597    false.  */
 598
 599 bool
 600 tree_ssa_useless_type_conversion (tree expr)
 601 {
 602   /* If we have an assignment that merely uses a NOP_EXPR to change
 603      the top of the RHS to the type of the LHS and the type conversion
 604      is "safe", then strip away the type conversion so that we can
 605      enter LHS = RHS into the const_and_copies table.  */
 606   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
 607     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 608                                                TREE_TYPE (TREE_OPERAND (expr,
 609                                                                         0)));
 610
 611
 612   return false;
 613 }
 614
 615
 616 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 617    described in walk_use_def_chains.  VISITED is a bitmap used to mark
 618    visited SSA_NAMEs to avoid infinite loops.  */
 619
 620 static bool
 621 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 622                        bitmap visited)
 623 {
 624   tree def_stmt;
 625
 626   if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
 627     return false;
 628
 629   bitmap_set_bit (visited, SSA_NAME_VERSION (var));
 630
 631   def_stmt = SSA_NAME_DEF_STMT (var);
 632
 633   if (TREE_CODE (def_stmt) != PHI_NODE)
 634     {
 635       /* If we reached the end of the use-def chain, call FN.  */
 636       return (*fn) (var, def_stmt, data);
 637     }
 638   else
 639     {
 640       int i;
 641
 642       /* Otherwise, follow use-def links out of each PHI argument and call
 643          FN after visiting each one.  */
 644       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 645         {
 646           tree arg = PHI_ARG_DEF (def_stmt, i);
 647           if (TREE_CODE (arg) == SSA_NAME
 648               && walk_use_def_chains_1 (arg, fn, data, visited))
 649             return true;
 650
 651           if ((*fn) (arg, def_stmt, data))
 652             return true;
 653         }
 654     }
 655   return false;
 656 }
 657
 658
 659
 660 /* Walk use-def chains starting at the SSA variable VAR.  Call function FN
 661    at each reaching definition found.  FN takes three arguments: VAR, its
 662    defining statement (DEF_STMT) and a generic pointer to whatever state
 663    information that FN may want to maintain (DATA).  FN is able to stop the
 664    walk by returning true, otherwise in order to continue the walk, FN
 665    should return false.
 666
 667    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 668    different.  For each argument ARG of the PHI node, this function will:
 669
 670         1- Walk the use-def chains for ARG.
 671         2- Call (*FN) (ARG, PHI, DATA).
 672
 673    Note how the first argument to FN is no longer the original variable
 674    VAR, but the PHI argument currently being examined.  If FN wants to get
 675    at VAR, it should call PHI_RESULT (PHI).  */
 676
 677 void
 678 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data)
 679 {
 680   tree def_stmt;
 681
 682 #if defined ENABLE_CHECKING
 683   if (TREE_CODE (var) != SSA_NAME)
 684     abort ();
 685 #endif
 686
 687   def_stmt = SSA_NAME_DEF_STMT (var);
 688
 689   /* We only need to recurse if the reaching definition comes from a PHI
 690      node.  */
 691   if (TREE_CODE (def_stmt) != PHI_NODE)
 692     (*fn) (var, def_stmt, data);
 693   else
 694     {
 695       bitmap visited = BITMAP_XMALLOC ();
 696       walk_use_def_chains_1 (var, fn, data, visited);
 697       BITMAP_XFREE (visited);
 698     }
 699 }
 700
 701 /* Replaces VAR with REPL in memory reference expression *X in
 702    statement STMT.  */
 703
 704 static void
 705 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
 706 {
 707   tree new_var, ass_stmt, addr_var;
 708   basic_block bb;
 709   block_stmt_iterator bsi;
 710
 711   /* There is nothing special to handle in the other cases.  */
 712   if (TREE_CODE (repl) != ADDR_EXPR)
 713     return;
 714   addr_var = TREE_OPERAND (repl, 0);
 715
 716   while (TREE_CODE (*x) == ARRAY_REF
 717          || TREE_CODE (*x) == COMPONENT_REF
 718          || TREE_CODE (*x) == BIT_FIELD_REF)
 719     x = &TREE_OPERAND (*x, 0);
 720
 721   if (TREE_CODE (*x) != INDIRECT_REF
 722       || TREE_OPERAND (*x, 0) != var)
 723     return;
 724
 725   modify_stmt (stmt);
 726   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
 727     {
 728       *x = addr_var;
 729       mark_new_vars_to_rename (stmt, vars_to_rename);
 730       return;
 731     }
 732
 733   /* Frontends sometimes produce expressions like *&a instead of a[0].
 734      Create a temporary variable to handle this case.  */
 735   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
 736   new_var = duplicate_ssa_name (var, ass_stmt);
 737   TREE_OPERAND (*x, 0) = new_var;
 738   TREE_OPERAND (ass_stmt, 0) = new_var;
 739
 740   bb = bb_for_stmt (stmt);
 741   tree_block_label (bb);
 742   bsi = bsi_after_labels (bb);
 743   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
 744
 745   mark_new_vars_to_rename (stmt, vars_to_rename);
 746 }
 747
 748 /* Replaces immediate uses of VAR by REPL.  */
 749
 750 static void
 751 replace_immediate_uses (tree var, tree repl)
 752 {
 753   use_optype uses;
 754   vuse_optype vuses;
 755   v_may_def_optype v_may_defs;
 756   int i, j, n;
 757   dataflow_t df;
 758   tree stmt;
 759   stmt_ann_t ann;
 760   bool mark_new_vars;
 761
 762   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 763   n = num_immediate_uses (df);
 764
 765   for (i = 0; i < n; i++)
 766     {
 767       stmt = immediate_use (df, i);
 768       ann = stmt_ann (stmt);
 769
 770       if (TREE_CODE (stmt) == PHI_NODE)
 771         {
 772           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
 773             if (PHI_ARG_DEF (stmt, j) == var)
 774               {
 775                 SET_PHI_ARG_DEF (stmt, j, repl);
 776                 if (TREE_CODE (repl) == SSA_NAME
 777                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
 778                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
 779               }
 780
 781           continue;
 782         }
 783
 784       get_stmt_operands (stmt);
 785       mark_new_vars = false;
 786       if (is_gimple_reg (SSA_NAME_VAR (var)))
 787         {
 788           if (TREE_CODE (stmt) == MODIFY_EXPR)
 789             {
 790               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
 791               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
 792             }
 793
 794           uses = USE_OPS (ann);
 795           for (j = 0; j < (int) NUM_USES (uses); j++)
 796             if (USE_OP (uses, j) == var)
 797               {
 798                 propagate_value (USE_OP_PTR (uses, j), repl);
 799                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
 800               }
 801         }
 802       else
 803         {
 804           vuses = VUSE_OPS (ann);
 805           for (j = 0; j < (int) NUM_VUSES (vuses); j++)
 806             if (VUSE_OP (vuses, j) == var)
 807               propagate_value (VUSE_OP_PTR (vuses, j), repl);
 808
 809           v_may_defs = V_MAY_DEF_OPS (ann);
 810           for (j = 0; j < (int) NUM_V_MAY_DEFS (v_may_defs); j++)
 811             if (V_MAY_DEF_OP (v_may_defs, j) == var)
 812               propagate_value (V_MAY_DEF_OP_PTR (v_may_defs, j), repl);
 813         }
 814
 815       /* If REPL is a pointer, it may have different memory tags associated
 816          with it.  For instance, VAR may have had a name tag while REPL
 817          only had a type tag.  In these cases, the virtual operands (if
 818          any) in the statement will refer to different symbols which need
 819          to be renamed.  */
 820       if (mark_new_vars)
 821         mark_new_vars_to_rename (stmt, vars_to_rename);
 822       else
 823         modify_stmt (stmt);
 824     }
 825 }
 826
 827 /* Gets the value VAR is equivalent to according to EQ_TO.  */
 828
 829 static tree
 830 get_eq_name (tree *eq_to, tree var)
 831 {
 832   unsigned ver;
 833   tree val = var;
 834
 835   while (TREE_CODE (val) == SSA_NAME)
 836     {
 837       ver = SSA_NAME_VERSION (val);
 838       if (!eq_to[ver])
 839         break;
 840
 841       val = eq_to[ver];
 842     }
 843
 844   while (TREE_CODE (var) == SSA_NAME)
 845     {
 846       ver = SSA_NAME_VERSION (var);
 847       if (!eq_to[ver])
 848         break;
 849
 850       var = eq_to[ver];
 851       eq_to[ver] = val;
 852     }
 853
 854   return val;
 855 }
 856
 857 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
 858    its result is redundant to to EQ_TO array.  */
 859
 860 static void
 861 check_phi_redundancy (tree phi, tree *eq_to)
 862 {
 863   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
 864   unsigned i, ver = SSA_NAME_VERSION (res), n;
 865   dataflow_t df;
 866
 867   /* It is unlikely that such large phi node would be redundant.  */
 868   if (PHI_NUM_ARGS (phi) > 16)
 869     return;
 870
 871   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 872     {
 873       def = PHI_ARG_DEF (phi, i);
 874
 875       if (TREE_CODE (def) == SSA_NAME)
 876         {
 877           def = get_eq_name (eq_to, def);
 878           if (def == res)
 879             continue;
 880         }
 881
 882       if (val
 883           && !operand_equal_p (val, def, 0))
 884         return;
 885
 886       val = def;
 887     }
 888
 889   /* At least one of the arguments should not be equal to the result, or
 890      something strange is happening.  */
 891   if (!val)
 892     abort ();
 893
 894   if (get_eq_name (eq_to, res) == val)
 895     return;
 896
 897   if (!may_propagate_copy (res, val))
 898     return;
 899
 900   eq_to[ver] = val;
 901
 902   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
 903   n = num_immediate_uses (df);
 904
 905   for (i = 0; i < n; i++)
 906     {
 907       stmt = immediate_use (df, i);
 908
 909       if (TREE_CODE (stmt) == PHI_NODE)
 910         check_phi_redundancy (stmt, eq_to);
 911     }
 912 }
 913
 914 /* Removes redundant phi nodes.
 915
 916    A redundant PHI node is a PHI node where all of its PHI arguments
 917    are the same value, excluding any PHI arguments which are the same
 918    as the PHI result.
 919
 920    A redundant PHI node is effectively a copy, so we forward copy propagate
 921    which removes all uses of the destination of the PHI node then
 922    finally we delete the redundant PHI node.
 923
 924    Note that if we can not copy propagate the PHI node, then the PHI
 925    will not be removed.  Thus we do not have to worry about dependencies
 926    between PHIs and the problems serializing PHIs into copies creates.
 927
 928    The most important effect of this pass is to remove degenerate PHI
 929    nodes created by removing unreachable code.  */
 930
 931 static void
 932 kill_redundant_phi_nodes (void)
 933 {
 934   tree *eq_to;
 935   unsigned i, old_num_ssa_names;
 936   basic_block bb;
 937   tree phi, var, repl, stmt;
 938
 939   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
 940      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
 941      other value, it may be necessary to follow the chain till the final value.
 942      We perform path shortening (replacing the entries of the EQ_TO array with
 943      heads of these chains) whenever we access the field to prevent quadratic
 944      complexity (probably would not occur in practice anyway, but let us play
 945      it safe).  */
 946   eq_to = xcalloc (num_ssa_names, sizeof (tree));
 947
 948   /* We have had cases where computing immediate uses takes a
 949      significant amount of compile time.  If we run into such
 950      problems here, we may want to only compute immediate uses for
 951      a subset of all the SSA_NAMEs instead of computing it for
 952      all of the SSA_NAMEs.  */
 953   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
 954   old_num_ssa_names = num_ssa_names;
 955
 956   FOR_EACH_BB (bb)
 957     {
 958       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 959         {
 960           var = PHI_RESULT (phi);
 961           check_phi_redundancy (phi, eq_to);
 962         }
 963     }
 964
 965   /* Now propagate the values.  */
 966   for (i = 0; i < old_num_ssa_names; i++)
 967     {
 968       if (!ssa_name (i))
 969         continue;
 970
 971       repl = get_eq_name (eq_to, ssa_name (i));
 972       if (repl != ssa_name (i))
 973         replace_immediate_uses (ssa_name (i), repl);
 974     }
 975
 976   /* And remove the dead phis.  */
 977   for (i = 0; i < old_num_ssa_names; i++)
 978     {
 979       if (!ssa_name (i))
 980         continue;
 981
 982       repl = get_eq_name (eq_to, ssa_name (i));
 983       if (repl != ssa_name (i))
 984         {
 985           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
 986           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
 987         }
 988     }
 989
 990   free_df ();
 991   free (eq_to);
 992 }
 993
 994 struct tree_opt_pass pass_redundant_phi =
 995 {
 996   "redphi",                             /* name */
 997   NULL,                                 /* gate */
 998   kill_redundant_phi_nodes,             /* execute */
 999   NULL,                                 /* sub */
1000   NULL,                                 /* next */
1001   0,                                    /* static_pass_number */
1002   0,                                    /* tv_id */
1003   PROP_cfg | PROP_ssa,                  /* properties_required */
1004   0,                                    /* properties_provided */
1005   0,                                    /* properties_destroyed */
1006   0,                                    /* todo_flags_start */
1007   TODO_dump_func | TODO_rename_vars
1008     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
1009 };
1010 \f
1011 /* Emit warnings for uninitialized variables.  This is done in two passes.
1012
1013    The first pass notices real uses of SSA names with default definitions.
1014    Such uses are unconditionally uninitialized, and we can be certain that
1015    such a use is a mistake.  This pass is run before most optimizations,
1016    so that we catch as many as we can.
1017
1018    The second pass follows PHI nodes to find uses that are potentially
1019    uninitialized.  In this case we can't necessarily prove that the use
1020    is really uninitialized.  This pass is run after most optimizations,
1021    so that we thread as many jumps and possible, and delete as much dead
1022    code as possible, in order to reduce false positives.  We also look
1023    again for plain uninitialized variables, since optimization may have
1024    changed conditionally uninitialized to unconditionally uninitialized.  */
1025
1026 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1027    warning text is in MSGID and LOCUS may contain a location or be null.  */
1028
1029 static void
1030 warn_uninit (tree t, const char *msgid, location_t *locus)
1031 {
1032   tree var = SSA_NAME_VAR (t);
1033   tree def = SSA_NAME_DEF_STMT (t);
1034
1035   /* Default uses (indicated by an empty definition statement),
1036      are uninitialized.  */
1037   if (!IS_EMPTY_STMT (def))
1038     return;
1039
1040   /* Except for PARMs of course, which are always initialized.  */
1041   if (TREE_CODE (var) == PARM_DECL)
1042     return;
1043
1044   /* Hard register variables get their initial value from the ether.  */
1045   if (DECL_HARD_REGISTER (var))
1046     return;
1047
1048   /* TREE_NO_WARNING either means we already warned, or the front end
1049      wishes to suppress the warning.  */
1050   if (TREE_NO_WARNING (var))
1051     return;
1052
1053   if (!locus)
1054     locus = &DECL_SOURCE_LOCATION (var);
1055   warning (msgid, locus, var);
1056   TREE_NO_WARNING (var) = 1;
1057 }
1058
1059 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1060    and warn about them.  */
1061
1062 static tree
1063 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1064 {
1065   location_t *locus = data;
1066   tree t = *tp;
1067
1068   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1069   if (TREE_CODE (t) == SSA_NAME)
1070     {
1071       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1072       *walk_subtrees = 0;
1073     }
1074   else if (DECL_P (t) || TYPE_P (t))
1075     *walk_subtrees = 0;
1076
1077   return NULL_TREE;
1078 }
1079
1080 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1081    and warn about them.  */
1082
1083 static void
1084 warn_uninitialized_phi (tree phi)
1085 {
1086   int i, n = PHI_NUM_ARGS (phi);
1087
1088   /* Don't look at memory tags.  */
1089   if (!is_gimple_reg (PHI_RESULT (phi)))
1090     return;
1091
1092   for (i = 0; i < n; ++i)
1093     {
1094       tree op = PHI_ARG_DEF (phi, i);
1095       if (TREE_CODE (op) == SSA_NAME)
1096         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1097                      NULL);
1098     }
1099 }
1100
1101 static void
1102 execute_early_warn_uninitialized (void)
1103 {
1104   block_stmt_iterator bsi;
1105   basic_block bb;
1106
1107   FOR_EACH_BB (bb)
1108     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1109       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1110                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1111 }
1112
1113 static void
1114 execute_late_warn_uninitialized (void)
1115 {
1116   basic_block bb;
1117   tree phi;
1118
1119   /* Re-do the plain uninitialized variable check, as optimization may have
1120      straightened control flow.  Do this first so that we don't accidentally
1121      get a "may be" warning when we'd have seen an "is" warning later.  */
1122   execute_early_warn_uninitialized ();
1123
1124   FOR_EACH_BB (bb)
1125     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1126       warn_uninitialized_phi (phi);
1127 }
1128
1129 static bool
1130 gate_warn_uninitialized (void)
1131 {
1132   return warn_uninitialized != 0;
1133 }
1134
1135 struct tree_opt_pass pass_early_warn_uninitialized =
1136 {
1137   NULL,                                 /* name */
1138   gate_warn_uninitialized,              /* gate */
1139   execute_early_warn_uninitialized,     /* execute */
1140   NULL,                                 /* sub */
1141   NULL,                                 /* next */
1142   0,                                    /* static_pass_number */
1143   0,                                    /* tv_id */
1144   PROP_ssa,                             /* properties_required */
1145   0,                                    /* properties_provided */
1146   0,                                    /* properties_destroyed */
1147   0,                                    /* todo_flags_start */
1148   0                                     /* todo_flags_finish */
1149 };
1150
1151 struct tree_opt_pass pass_late_warn_uninitialized =
1152 {
1153   NULL,                                 /* name */
1154   gate_warn_uninitialized,              /* gate */
1155   execute_late_warn_uninitialized,      /* execute */
1156   NULL,                                 /* sub */
1157   NULL,                                 /* next */
1158   0,                                    /* static_pass_number */
1159   0,                                    /* tv_id */
1160   PROP_ssa,                             /* properties_required */
1161   0,                                    /* properties_provided */
1162   0,                                    /* properties_destroyed */
1163   0,                                    /* todo_flags_start */
1164   0                                     /* todo_flags_finish */
1165 };