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                 SET_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 /* Gets the value VAR is equivalent to according to EQ_TO.  */
 835
 836 static tree
 837 get_eq_name (tree *eq_to, tree var)
 838 {
 839   unsigned ver;
 840   tree val = var;
 841
 842   while (TREE_CODE (val) == SSA_NAME)
 843     {
 844       ver = SSA_NAME_VERSION (val);
 845       if (!eq_to[ver])
 846         break;
 847
 848       val = eq_to[ver];
 849     }
 850
 851   while (TREE_CODE (var) == SSA_NAME)
 852     {
 853       ver = SSA_NAME_VERSION (var);
 854       if (!eq_to[ver])
 855         break;
 856
 857       var = eq_to[ver];
 858       eq_to[ver] = val;
 859     }
 860
 861   return val;
 862 }
 863
 864 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
 865    its result is redundant to to EQ_TO array.  */
 866
 867 static void
 868 check_phi_redundancy (tree phi, tree *eq_to)
 869 {
 870   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
 871   unsigned i, ver = SSA_NAME_VERSION (res), n;
 872   dataflow_t df;
 873
 874   /* It is unlikely that such large phi node would be redundant.  */
 875   if (PHI_NUM_ARGS (phi) > 16)
 876     return;
 877
 878   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 879     {
 880       def = PHI_ARG_DEF (phi, i);
 881
 882       if (TREE_CODE (def) == SSA_NAME)
 883         {
 884           def = get_eq_name (eq_to, def);
 885           if (def == res)
 886             continue;
 887         }
 888
 889       if (val
 890           && !operand_equal_p (val, def, 0))
 891         return;
 892
 893       val = def;
 894     }
 895
 896   /* At least one of the arguments should not be equal to the result, or
 897      something strange is happening.  */
 898   if (!val)
 899     abort ();
 900
 901   if (get_eq_name (eq_to, res) == val)
 902     return;
 903
 904   if (!may_propagate_copy (res, val))
 905     return;
 906
 907   eq_to[ver] = val;
 908
 909   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
 910   n = num_immediate_uses (df);
 911
 912   for (i = 0; i < n; i++)
 913     {
 914       stmt = immediate_use (df, i);
 915
 916       if (TREE_CODE (stmt) == PHI_NODE)
 917         check_phi_redundancy (stmt, eq_to);
 918     }
 919 }
 920
 921 /* Removes redundant phi nodes.
 922
 923    A redundant PHI node is a PHI node where all of its PHI arguments
 924    are the same value, excluding any PHI arguments which are the same
 925    as the PHI result.
 926
 927    A redundant PHI node is effectively a copy, so we forward copy propagate
 928    which removes all uses of the destination of the PHI node then
 929    finally we delete the redundant PHI node.
 930
 931    Note that if we can not copy propagate the PHI node, then the PHI
 932    will not be removed.  Thus we do not have to worry about dependencies
 933    between PHIs and the problems serializing PHIs into copies creates.
 934
 935    The most important effect of this pass is to remove degenerate PHI
 936    nodes created by removing unreachable code.  */
 937
 938 static void
 939 kill_redundant_phi_nodes (void)
 940 {
 941   tree *eq_to;
 942   unsigned i, old_num_ssa_names;
 943   basic_block bb;
 944   tree phi, var, repl, stmt;
 945
 946   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
 947      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
 948      other value, it may be necessary to follow the chain till the final value.
 949      We perform path shortening (replacing the entries of the EQ_TO array with
 950      heads of these chains) whenever we access the field to prevent quadratic
 951      complexity (probably would not occur in practice anyway, but let us play
 952      it safe).  */
 953   eq_to = xcalloc (num_ssa_names, sizeof (tree));
 954
 955   /* We have had cases where computing immediate uses takes a
 956      significant amount of compile time.  If we run into such
 957      problems here, we may want to only compute immediate uses for
 958      a subset of all the SSA_NAMEs instead of computing it for
 959      all of the SSA_NAMEs.  */
 960   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
 961   old_num_ssa_names = num_ssa_names;
 962
 963   FOR_EACH_BB (bb)
 964     {
 965       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 966         {
 967           var = PHI_RESULT (phi);
 968           check_phi_redundancy (phi, eq_to);
 969         }
 970     }
 971
 972   /* Now propagate the values.  */
 973   for (i = 0; i < old_num_ssa_names; i++)
 974     {
 975       if (!ssa_name (i))
 976         continue;
 977
 978       repl = get_eq_name (eq_to, ssa_name (i));
 979       if (repl != ssa_name (i))
 980         replace_immediate_uses (ssa_name (i), repl);
 981     }
 982
 983   /* And remove the dead phis.  */
 984   for (i = 0; i < old_num_ssa_names; i++)
 985     {
 986       if (!ssa_name (i))
 987         continue;
 988
 989       repl = get_eq_name (eq_to, ssa_name (i));
 990       if (repl != ssa_name (i))
 991         {
 992           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
 993           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
 994         }
 995     }
 996
 997   free_df ();
 998   free (eq_to);
 999 }
1000
1001 struct tree_opt_pass pass_redundant_phi =
1002 {
1003   "redphi",                             /* name */
1004   NULL,                                 /* gate */
1005   kill_redundant_phi_nodes,             /* execute */
1006   NULL,                                 /* sub */
1007   NULL,                                 /* next */
1008   0,                                    /* static_pass_number */
1009   0,                                    /* tv_id */
1010   PROP_cfg | PROP_ssa,                  /* properties_required */
1011   0,                                    /* properties_provided */
1012   0,                                    /* properties_destroyed */
1013   0,                                    /* todo_flags_start */
1014   TODO_dump_func | TODO_rename_vars
1015     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
1016 };
1017 \f
1018 /* Emit warnings for uninitialized variables.  This is done in two passes.
1019
1020    The first pass notices real uses of SSA names with default definitions.
1021    Such uses are unconditionally uninitialized, and we can be certain that
1022    such a use is a mistake.  This pass is run before most optimizations,
1023    so that we catch as many as we can.
1024
1025    The second pass follows PHI nodes to find uses that are potentially
1026    uninitialized.  In this case we can't necessarily prove that the use
1027    is really uninitialized.  This pass is run after most optimizations,
1028    so that we thread as many jumps and possible, and delete as much dead
1029    code as possible, in order to reduce false positives.  We also look
1030    again for plain uninitialized variables, since optimization may have
1031    changed conditionally uninitialized to unconditionally uninitialized.  */
1032
1033 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1034    warning text is in MSGID and LOCUS may contain a location or be null.  */
1035
1036 static void
1037 warn_uninit (tree t, const char *msgid, location_t *locus)
1038 {
1039   tree var = SSA_NAME_VAR (t);
1040   tree def = SSA_NAME_DEF_STMT (t);
1041
1042   /* Default uses (indicated by an empty definition statement),
1043      are uninitialized.  */
1044   if (!IS_EMPTY_STMT (def))
1045     return;
1046
1047   /* Except for PARMs of course, which are always initialized.  */
1048   if (TREE_CODE (var) == PARM_DECL)
1049     return;
1050
1051   /* Hard register variables get their initial value from the ether.  */
1052   if (DECL_HARD_REGISTER (var))
1053     return;
1054
1055   /* TREE_NO_WARNING either means we already warned, or the front end
1056      wishes to suppress the warning.  */
1057   if (TREE_NO_WARNING (var))
1058     return;
1059
1060   if (!locus)
1061     locus = &DECL_SOURCE_LOCATION (var);
1062   warning (msgid, locus, var);
1063   TREE_NO_WARNING (var) = 1;
1064 }
1065
1066 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1067    and warn about them.  */
1068
1069 static tree
1070 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1071 {
1072   location_t *locus = data;
1073   tree t = *tp;
1074
1075   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1076   if (TREE_CODE (t) == SSA_NAME)
1077     {
1078       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1079       *walk_subtrees = 0;
1080     }
1081   else if (DECL_P (t) || TYPE_P (t))
1082     *walk_subtrees = 0;
1083
1084   return NULL_TREE;
1085 }
1086
1087 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1088    and warn about them.  */
1089
1090 static void
1091 warn_uninitialized_phi (tree phi)
1092 {
1093   int i, n = PHI_NUM_ARGS (phi);
1094
1095   /* Don't look at memory tags.  */
1096   if (!is_gimple_reg (PHI_RESULT (phi)))
1097     return;
1098
1099   for (i = 0; i < n; ++i)
1100     {
1101       tree op = PHI_ARG_DEF (phi, i);
1102       if (TREE_CODE (op) == SSA_NAME)
1103         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1104                      NULL);
1105     }
1106 }
1107
1108 static void
1109 execute_early_warn_uninitialized (void)
1110 {
1111   block_stmt_iterator bsi;
1112   basic_block bb;
1113
1114   FOR_EACH_BB (bb)
1115     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1116       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1117                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1118 }
1119
1120 static void
1121 execute_late_warn_uninitialized (void)
1122 {
1123   basic_block bb;
1124   tree phi;
1125
1126   /* Re-do the plain uninitialized variable check, as optimization may have
1127      straightened control flow.  Do this first so that we don't accidentally
1128      get a "may be" warning when we'd have seen an "is" warning later.  */
1129   execute_early_warn_uninitialized ();
1130
1131   FOR_EACH_BB (bb)
1132     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1133       warn_uninitialized_phi (phi);
1134 }
1135
1136 static bool
1137 gate_warn_uninitialized (void)
1138 {
1139   return warn_uninitialized != 0;
1140 }
1141
1142 struct tree_opt_pass pass_early_warn_uninitialized =
1143 {
1144   NULL,                                 /* name */
1145   gate_warn_uninitialized,              /* gate */
1146   execute_early_warn_uninitialized,     /* execute */
1147   NULL,                                 /* sub */
1148   NULL,                                 /* next */
1149   0,                                    /* static_pass_number */
1150   0,                                    /* tv_id */
1151   PROP_ssa,                             /* properties_required */
1152   0,                                    /* properties_provided */
1153   0,                                    /* properties_destroyed */
1154   0,                                    /* todo_flags_start */
1155   0                                     /* todo_flags_finish */
1156 };
1157
1158 struct tree_opt_pass pass_late_warn_uninitialized =
1159 {
1160   NULL,                                 /* name */
1161   gate_warn_uninitialized,              /* gate */
1162   execute_late_warn_uninitialized,      /* execute */
1163   NULL,                                 /* sub */
1164   NULL,                                 /* next */
1165   0,                                    /* static_pass_number */
1166   0,                                    /* tv_id */
1167   PROP_ssa,                             /* properties_required */
1168   0,                                    /* properties_provided */
1169   0,                                    /* properties_destroyed */
1170   0,                                    /* todo_flags_start */
1171   0                                     /* todo_flags_finish */
1172 };