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