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 /* Replaces VAR with REPL in memory reference expression *X in
 709    statement STMT.  */
 710
 711 static void
 712 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
 713 {
 714   tree new_var, ass_stmt, addr_var;
 715   basic_block bb;
 716   block_stmt_iterator bsi;
 717
 718   /* There is nothing special to handle in the other cases.  */
 719   if (TREE_CODE (repl) != ADDR_EXPR)
 720     return;
 721   addr_var = TREE_OPERAND (repl, 0);
 722
 723   while (TREE_CODE (*x) == ARRAY_REF
 724          || TREE_CODE (*x) == COMPONENT_REF
 725          || TREE_CODE (*x) == BIT_FIELD_REF)
 726     x = &TREE_OPERAND (*x, 0);
 727
 728   if (TREE_CODE (*x) != INDIRECT_REF
 729       || TREE_OPERAND (*x, 0) != var)
 730     return;
 731
 732   modify_stmt (stmt);
 733   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
 734     {
 735       *x = addr_var;
 736       mark_new_vars_to_rename (stmt, vars_to_rename);
 737       return;
 738     }
 739
 740   /* Frontends sometimes produce expressions like *&a instead of a[0].
 741      Create a temporary variable to handle this case.  */
 742   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
 743   new_var = duplicate_ssa_name (var, ass_stmt);
 744   TREE_OPERAND (*x, 0) = new_var;
 745   TREE_OPERAND (ass_stmt, 0) = new_var;
 746
 747   bb = bb_for_stmt (stmt);
 748   tree_block_label (bb);
 749   bsi = bsi_after_labels (bb);
 750   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
 751
 752   mark_new_vars_to_rename (stmt, vars_to_rename);
 753 }
 754
 755 /* Replaces immediate uses of VAR by REPL.  */
 756
 757 static void
 758 replace_immediate_uses (tree var, tree repl)
 759 {
 760   use_optype uses;
 761   vuse_optype vuses;
 762   v_may_def_optype v_may_defs;
 763   int i, j, n;
 764   dataflow_t df;
 765   tree stmt;
 766   stmt_ann_t ann;
 767   bool mark_new_vars;
 768
 769   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 770   n = num_immediate_uses (df);
 771
 772   for (i = 0; i < n; i++)
 773     {
 774       stmt = immediate_use (df, i);
 775       ann = stmt_ann (stmt);
 776
 777       if (TREE_CODE (stmt) == PHI_NODE)
 778         {
 779           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
 780             if (PHI_ARG_DEF (stmt, j) == var)
 781               {
 782                 PHI_ARG_DEF (stmt, j) = repl;
 783                 if (TREE_CODE (repl) == SSA_NAME
 784                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
 785                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
 786               }
 787
 788           continue;
 789         }
 790
 791       get_stmt_operands (stmt);
 792       mark_new_vars = false;
 793       if (is_gimple_reg (SSA_NAME_VAR (var)))
 794         {
 795           if (TREE_CODE (stmt) == MODIFY_EXPR)
 796             {
 797               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
 798               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
 799             }
 800
 801           uses = USE_OPS (ann);
 802           for (j = 0; j < (int) NUM_USES (uses); j++)
 803             if (USE_OP (uses, j) == var)
 804               {
 805                 propagate_value (USE_OP_PTR (uses, j), repl);
 806                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
 807               }
 808         }
 809       else
 810         {
 811           vuses = VUSE_OPS (ann);
 812           for (j = 0; j < (int) NUM_VUSES (vuses); j++)
 813             if (VUSE_OP (vuses, j) == var)
 814               propagate_value (VUSE_OP_PTR (vuses, j), repl);
 815
 816           v_may_defs = V_MAY_DEF_OPS (ann);
 817           for (j = 0; j < (int) NUM_V_MAY_DEFS (v_may_defs); j++)
 818             if (V_MAY_DEF_OP (v_may_defs, j) == var)
 819               propagate_value (V_MAY_DEF_OP_PTR (v_may_defs, j), repl);
 820         }
 821
 822       /* If REPL is a pointer, it may have different memory tags associated
 823          with it.  For instance, VAR may have had a name tag while REPL
 824          only had a type tag.  In these cases, the virtual operands (if
 825          any) in the statement will refer to different symbols which need
 826          to be renamed.  */
 827       if (mark_new_vars)
 828         mark_new_vars_to_rename (stmt, vars_to_rename);
 829       else
 830         modify_stmt (stmt);
 831     }
 832 }
 833
 834 /* Raises value of phi node PHI by joining it with VAL.  Processes immediate
 835    uses of PHI recursively.  */
 836
 837 static void
 838 raise_value (tree phi, tree val, tree *eq_to)
 839 {
 840   int i, n;
 841   tree var = PHI_RESULT (phi), stmt;
 842   int ver = SSA_NAME_VERSION (var);
 843   dataflow_t df;
 844
 845   if (eq_to[ver] == var)
 846     return;
 847
 848   if (eq_to[ver])
 849     {
 850       if (operand_equal_p (eq_to[ver], val, 0))
 851         return;
 852
 853       eq_to[ver] = var;
 854     }
 855   else
 856     eq_to[ver] = val;
 857
 858   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 859   n = num_immediate_uses (df);
 860
 861   for (i = 0; i < n; i++)
 862     {
 863       stmt = immediate_use (df, i);
 864
 865       if (TREE_CODE (stmt) != PHI_NODE)
 866         continue;
 867
 868       raise_value (stmt, eq_to[ver], eq_to);
 869     }
 870 }
 871
 872 /* Removes redundant phi nodes.
 873
 874    A redundant PHI node is a PHI node where all of its PHI arguments
 875    are the same value, excluding any PHI arguments which are the same
 876    as the PHI result.
 877
 878    A redundant PHI node is effectively a copy, so we forward copy propagate
 879    which removes all uses of the destination of the PHI node then
 880    finally we delete the redundant PHI node.
 881
 882    Note that if we can not copy propagate the PHI node, then the PHI
 883    will not be removed.  Thus we do not have to worry about dependencies
 884    between PHIs and the problems serializing PHIs into copies creates.
 885
 886    The most important effect of this pass is to remove degenerate PHI
 887    nodes created by removing unreachable code.  */
 888
 889 static void
 890 kill_redundant_phi_nodes (void)
 891 {
 892   tree *eq_to;
 893   unsigned i;
 894   basic_block bb;
 895   tree phi, t, stmt, var;
 896
 897   /* The EQ_TO array holds the current value of the ssa name in the
 898      lattice:
 899
 900           top
 901          / | \
 902      const   variables
 903          \ | /
 904         bottom
 905
 906      Bottom is represented by NULL and top by the variable itself.
 907
 908      Once the dataflow stabilizes, we know that the phi nodes we need to keep
 909      are exactly those with top as their result.
 910
 911      The remaining phi nodes have their uses replaced with their value
 912      in the lattice and the phi node itself is removed.  */
 913   eq_to = xcalloc (num_ssa_names, sizeof (tree));
 914
 915   /* We have had cases where computing immediate uses takes a
 916      significant amount of compile time.  If we run into such
 917      problems here, we may want to only compute immediate uses for
 918      a subset of all the SSA_NAMEs instead of computing it for
 919      all of the SSA_NAMEs.  */
 920   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
 921
 922   FOR_EACH_BB (bb)
 923     {
 924       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 925         {
 926           var = PHI_RESULT (phi);
 927
 928           /* If the destination of the PHI is associated with an
 929              abnormal edge, then we can not propagate this PHI away.  */
 930           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (var))
 931             {
 932               raise_value (phi, var, eq_to);
 933               continue;
 934             }
 935
 936           for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 937             {
 938               t = PHI_ARG_DEF (phi, i);
 939
 940               if (TREE_CODE (t) != SSA_NAME)
 941                 {
 942                   raise_value (phi, t, eq_to);
 943                   continue;
 944                 }
 945
 946               stmt = SSA_NAME_DEF_STMT (t);
 947
 948               /* If any particular PHI argument is associated with
 949                  an abnormal edge, then we know that we should not
 950                  be propagating away this PHI.  Go ahead and raise
 951                  the result of this PHI to the top of the lattice.  */
 952               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
 953                 {
 954                   raise_value (phi, var, eq_to);
 955                   continue;
 956                 }
 957
 958               /* If the defining statement for this argument is not a
 959                  phi node then we need to recursively start the forward
 960                  dataflow starting with PHI.  */
 961               if (TREE_CODE (stmt) != PHI_NODE)
 962                 {
 963                   eq_to[SSA_NAME_VERSION (t)] = t;
 964                   raise_value (phi, t, eq_to);
 965                 }
 966             }
 967         }
 968     }
 969
 970   /* Now propagate the values.  */
 971   for (i = 0; i < num_ssa_names; i++)
 972     if (eq_to[i]
 973         && eq_to[i] != ssa_name (i))
 974       replace_immediate_uses (ssa_name (i), eq_to[i]);
 975
 976   /* And remove the dead phis.  */
 977   for (i = 0; i < num_ssa_names; i++)
 978     if (eq_to[i]
 979         && eq_to[i] != ssa_name (i))
 980       {
 981         stmt = SSA_NAME_DEF_STMT (ssa_name (i));
 982         remove_phi_node (stmt, 0, bb_for_stmt (stmt));
 983       }
 984
 985   free_df ();
 986   free (eq_to);
 987 }
 988
 989 struct tree_opt_pass pass_redundant_phi =
 990 {
 991   "redphi",                             /* name */
 992   NULL,                                 /* gate */
 993   kill_redundant_phi_nodes,             /* execute */
 994   NULL,                                 /* sub */
 995   NULL,                                 /* next */
 996   0,                                    /* static_pass_number */
 997   0,                                    /* tv_id */
 998   PROP_cfg | PROP_ssa,                  /* properties_required */
 999   0,                                    /* properties_provided */
1000   0,                                    /* properties_destroyed */
1001   0,                                    /* todo_flags_start */
1002   TODO_dump_func | TODO_rename_vars
1003     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
1004 };
1005 \f
1006 /* Emit warnings for uninitialized variables.  This is done in two passes.
1007
1008    The first pass notices real uses of SSA names with default definitions.
1009    Such uses are unconditionally uninitialized, and we can be certain that
1010    such a use is a mistake.  This pass is run before most optimizations,
1011    so that we catch as many as we can.
1012
1013    The second pass follows PHI nodes to find uses that are potentially
1014    uninitialized.  In this case we can't necessarily prove that the use
1015    is really uninitialized.  This pass is run after most optimizations,
1016    so that we thread as many jumps and possible, and delete as much dead
1017    code as possible, in order to reduce false positives.  We also look
1018    again for plain uninitialized variables, since optimization may have
1019    changed conditionally uninitialized to unconditionally uninitialized.  */
1020
1021 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1022    warning text is in MSGID and LOCUS may contain a location or be null.  */
1023
1024 static void
1025 warn_uninit (tree t, const char *msgid, location_t *locus)
1026 {
1027   tree var = SSA_NAME_VAR (t);
1028   tree def = SSA_NAME_DEF_STMT (t);
1029
1030   /* Default uses (indicated by an empty definition statement),
1031      are uninitialized.  */
1032   if (!IS_EMPTY_STMT (def))
1033     return;
1034
1035   /* Except for PARMs of course, which are always initialized.  */
1036   if (TREE_CODE (var) == PARM_DECL)
1037     return;
1038
1039   /* Hard register variables get their initial value from the ether.  */
1040   if (DECL_HARD_REGISTER (var))
1041     return;
1042
1043   /* TREE_NO_WARNING either means we already warned, or the front end
1044      wishes to suppress the warning.  */
1045   if (TREE_NO_WARNING (var))
1046     return;
1047
1048   if (!locus)
1049     locus = &DECL_SOURCE_LOCATION (var);
1050   warning (msgid, locus, var);
1051   TREE_NO_WARNING (var) = 1;
1052 }
1053
1054 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1055    and warn about them.  */
1056
1057 static tree
1058 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1059 {
1060   location_t *locus = data;
1061   tree t = *tp;
1062
1063   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1064   if (TREE_CODE (t) == SSA_NAME)
1065     {
1066       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1067       *walk_subtrees = 0;
1068     }
1069   else if (DECL_P (t) || TYPE_P (t))
1070     *walk_subtrees = 0;
1071
1072   return NULL_TREE;
1073 }
1074
1075 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1076    and warn about them.  */
1077
1078 static void
1079 warn_uninitialized_phi (tree phi)
1080 {
1081   int i, n = PHI_NUM_ARGS (phi);
1082
1083   /* Don't look at memory tags.  */
1084   if (!is_gimple_reg (PHI_RESULT (phi)))
1085     return;
1086
1087   for (i = 0; i < n; ++i)
1088     {
1089       tree op = PHI_ARG_DEF (phi, i);
1090       if (TREE_CODE (op) == SSA_NAME)
1091         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1092                      NULL);
1093     }
1094 }
1095
1096 static void
1097 execute_early_warn_uninitialized (void)
1098 {
1099   block_stmt_iterator bsi;
1100   basic_block bb;
1101
1102   FOR_EACH_BB (bb)
1103     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1104       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1105                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1106 }
1107
1108 static void
1109 execute_late_warn_uninitialized (void)
1110 {
1111   basic_block bb;
1112   tree phi;
1113
1114   /* Re-do the plain uninitialized variable check, as optimization may have
1115      straightened control flow.  Do this first so that we don't accidentally
1116      get a "may be" warning when we'd have seen an "is" warning later.  */
1117   execute_early_warn_uninitialized ();
1118
1119   FOR_EACH_BB (bb)
1120     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1121       warn_uninitialized_phi (phi);
1122 }
1123
1124 static bool
1125 gate_warn_uninitialized (void)
1126 {
1127   return warn_uninitialized != 0;
1128 }
1129
1130 struct tree_opt_pass pass_early_warn_uninitialized =
1131 {
1132   NULL,                                 /* name */
1133   gate_warn_uninitialized,              /* gate */
1134   execute_early_warn_uninitialized,     /* execute */
1135   NULL,                                 /* sub */
1136   NULL,                                 /* next */
1137   0,                                    /* static_pass_number */
1138   0,                                    /* tv_id */
1139   PROP_ssa,                             /* properties_required */
1140   0,                                    /* properties_provided */
1141   0,                                    /* properties_destroyed */
1142   0,                                    /* todo_flags_start */
1143   0                                     /* todo_flags_finish */
1144 };
1145
1146 struct tree_opt_pass pass_late_warn_uninitialized =
1147 {
1148   NULL,                                 /* name */
1149   gate_warn_uninitialized,              /* gate */
1150   execute_late_warn_uninitialized,      /* execute */
1151   NULL,                                 /* sub */
1152   NULL,                                 /* next */
1153   0,                                    /* static_pass_number */
1154   0,                                    /* tv_id */
1155   PROP_ssa,                             /* properties_required */
1156   0,                                    /* properties_provided */
1157   0,                                    /* properties_destroyed */
1158   0,                                    /* todo_flags_start */
1159   0                                     /* todo_flags_finish */
1160 };