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