gcc/gimple-low.c

   1 /* Tree lowering pass.  Lowers GIMPLE into unstructured form.
   2
   3    Copyright (C) 2003 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "errors.h"
  29 #include "varray.h"
  30 #include "tree-gimple.h"
  31 #include "tree-inline.h"
  32 #include "diagnostic.h"
  33 #include "langhooks.h"
  34 #include "langhooks-def.h"
  35 #include "tree-flow.h"
  36 #include "timevar.h"
  37 #include "except.h"
  38 #include "hashtab.h"
  39 #include "flags.h"
  40 #include "function.h"
  41 #include "expr.h"
  42 #include "toplev.h"
  43 #include "tree-pass.h"
  44
  45 struct lower_data
  46 {
  47   /* Block the current statement belongs to.  */
  48   tree block;
  49 };
  50
  51 static void lower_stmt (tree_stmt_iterator *, struct lower_data *);
  52 static void lower_bind_expr (tree_stmt_iterator *, struct lower_data *);
  53 static void lower_cond_expr (tree_stmt_iterator *, struct lower_data *);
  54 static bool expand_var_p (tree);
  55
  56 /* Lowers the body of current_function_decl.  */
  57
  58 static void
  59 lower_function_body (void)
  60 {
  61   struct lower_data data;
  62   tree *body_p = &DECL_SAVED_TREE (current_function_decl);
  63   tree bind = *body_p;
  64   tree_stmt_iterator i;
  65
  66   if (TREE_CODE (bind) != BIND_EXPR)
  67     abort ();
  68
  69   data.block = DECL_INITIAL (current_function_decl);
  70   BLOCK_SUBBLOCKS (data.block) = NULL_TREE;
  71   BLOCK_CHAIN (data.block) = NULL_TREE;
  72   TREE_ASM_WRITTEN (data.block) = 1;
  73
  74   *body_p = alloc_stmt_list ();
  75   i = tsi_start (*body_p);
  76   tsi_link_after (&i, bind, TSI_NEW_STMT);
  77   lower_bind_expr (&i, &data);
  78
  79   if (data.block != DECL_INITIAL (current_function_decl))
  80     abort ();
  81   BLOCK_SUBBLOCKS (data.block)
  82     = blocks_nreverse (BLOCK_SUBBLOCKS (data.block));
  83
  84   clear_block_marks (data.block);
  85
  86   /* Avoid producing notes for blocks.  */
  87   cfun->dont_emit_block_notes = 1;
  88   reset_block_changes ();
  89 }
  90
  91 struct tree_opt_pass pass_lower_cf =
  92 {
  93   "lower",                              /* name */
  94   NULL,                                 /* gate */
  95   lower_function_body,                  /* execute */
  96   NULL,                                 /* sub */
  97   NULL,                                 /* next */
  98   0,                                    /* static_pass_number */
  99   0,                                    /* tv_id */
 100   PROP_gimple_any,                      /* properties_required */
 101   PROP_gimple_lcf,                      /* properties_provided */
 102   PROP_gimple_any,                      /* properties_destroyed */
 103   0,                                    /* todo_flags_start */
 104   TODO_dump_func                        /* todo_flags_finish */
 105 };
 106
 107
 108 /* Lowers the EXPR.  Unlike gimplification the statements are not relowered
 109    when they are changed -- if this has to be done, the lowering routine must
 110    do it explicitly.  DATA is passed through the recursion.  */
 111
 112 void
 113 lower_stmt_body (tree expr, struct lower_data *data)
 114 {
 115   tree_stmt_iterator tsi;
 116
 117   for (tsi = tsi_start (expr); !tsi_end_p (tsi); )
 118     lower_stmt (&tsi, data);
 119 }
 120
 121 /* Lowers statement TSI.  DATA is passed through the recursion.  */
 122
 123 static void
 124 lower_stmt (tree_stmt_iterator *tsi, struct lower_data *data)
 125 {
 126   tree stmt = tsi_stmt (*tsi);
 127
 128   if (EXPR_HAS_LOCATION (stmt) && data)
 129     TREE_BLOCK (stmt) = data->block;
 130
 131   switch (TREE_CODE (stmt))
 132     {
 133     case BIND_EXPR:
 134       lower_bind_expr (tsi, data);
 135       return;
 136     case COND_EXPR:
 137       lower_cond_expr (tsi, data);
 138       return;
 139
 140     case TRY_FINALLY_EXPR:
 141     case TRY_CATCH_EXPR:
 142       lower_stmt_body (TREE_OPERAND (stmt, 0), data);
 143       lower_stmt_body (TREE_OPERAND (stmt, 1), data);
 144       break;
 145     case CATCH_EXPR:
 146       lower_stmt_body (CATCH_BODY (stmt), data);
 147       break;
 148     case EH_FILTER_EXPR:
 149       lower_stmt_body (EH_FILTER_FAILURE (stmt), data);
 150       break;
 151
 152     case NOP_EXPR:
 153     case ASM_EXPR:
 154     case RETURN_EXPR:
 155     case MODIFY_EXPR:
 156     case CALL_EXPR:
 157     case GOTO_EXPR:
 158     case LABEL_EXPR:
 159     case VA_ARG_EXPR:
 160     case SWITCH_EXPR:
 161       break;
 162
 163     default:
 164       print_node_brief (stderr, "", stmt, 0);
 165     case COMPOUND_EXPR:
 166       abort ();
 167     }
 168
 169   tsi_next (tsi);
 170 }
 171
 172 /* Lowers a bind_expr TSI.  DATA is passed through the recursion.  */
 173
 174 static void
 175 lower_bind_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 176 {
 177   tree old_block = data->block;
 178   tree stmt = tsi_stmt (*tsi);
 179   tree new_block = BIND_EXPR_BLOCK (stmt);
 180
 181   if (new_block)
 182     {
 183       if (new_block == old_block)
 184         {
 185           /* The outermost block of the original function may not be the
 186              outermost statement chain of the gimplified function.  So we
 187              may see the outermost block just inside the function.  */
 188           if (new_block != DECL_INITIAL (current_function_decl))
 189             abort ();
 190           new_block = NULL;
 191         }
 192       else
 193         {
 194           /* We do not expect to handle duplicate blocks.  */
 195           if (TREE_ASM_WRITTEN (new_block))
 196             abort ();
 197           TREE_ASM_WRITTEN (new_block) = 1;
 198
 199           /* Block tree may get clobbered by inlining.  Normally this would
 200              be fixed in rest_of_decl_compilation using block notes, but
 201              since we are not going to emit them, it is up to us.  */
 202           BLOCK_CHAIN (new_block) = BLOCK_SUBBLOCKS (old_block);
 203           BLOCK_SUBBLOCKS (old_block) = new_block;
 204           BLOCK_SUBBLOCKS (new_block) = NULL_TREE;
 205           BLOCK_SUPERCONTEXT (new_block) = old_block;
 206
 207           data->block = new_block;
 208         }
 209     }
 210
 211   record_vars (BIND_EXPR_VARS (stmt));
 212   lower_stmt_body (BIND_EXPR_BODY (stmt), data);
 213
 214   if (new_block)
 215     {
 216       if (data->block != new_block)
 217         abort ();
 218
 219       BLOCK_SUBBLOCKS (new_block)
 220         = blocks_nreverse (BLOCK_SUBBLOCKS (new_block));
 221       data->block = old_block;
 222     }
 223
 224   /* The BIND_EXPR no longer carries any useful information -- kill it.  */
 225   tsi_link_before (tsi, BIND_EXPR_BODY (stmt), TSI_SAME_STMT);
 226   tsi_delink (tsi);
 227 }
 228
 229 /* Try to determine if we can fall out of the bottom of BLOCK.  This guess
 230    need not be 100% accurate; simply be conservative and return true if we
 231    don't know.  This is used only to avoid stupidly generating extra code.
 232    If we're wrong, we'll just delete the extra code later.  */
 233
 234 bool
 235 block_may_fallthru (tree block)
 236 {
 237   tree stmt = expr_last (block);
 238
 239   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
 240     {
 241     case GOTO_EXPR:
 242     case RETURN_EXPR:
 243     case RESX_EXPR:
 244     case SWITCH_EXPR:
 245       /* Easy cases.  If the last statement of the block implies
 246          control transfer, then we can't fall through.  */
 247       return false;
 248
 249     case COND_EXPR:
 250       if (block_may_fallthru (COND_EXPR_THEN (stmt)))
 251         return true;
 252       return block_may_fallthru (COND_EXPR_ELSE (stmt));
 253
 254     case BIND_EXPR:
 255       return block_may_fallthru (BIND_EXPR_BODY (stmt));
 256
 257     case TRY_FINALLY_EXPR:
 258       return block_may_fallthru (TREE_OPERAND (stmt, 1));
 259
 260     case MODIFY_EXPR:
 261       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
 262         stmt = TREE_OPERAND (stmt, 1);
 263       else
 264         return true;
 265       /* FALLTHRU */
 266
 267     case CALL_EXPR:
 268       /* Functions that do not return do not fall through.  */
 269       return (call_expr_flags (stmt) & ECF_NORETURN) == 0;
 270
 271     default:
 272       return true;
 273     }
 274 }
 275
 276 /* Lowers a cond_expr TSI.  DATA is passed through the recursion.  */
 277
 278 static void
 279 lower_cond_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 280 {
 281   tree stmt = tsi_stmt (*tsi);
 282   bool then_is_goto, else_is_goto;
 283   tree then_branch, else_branch;
 284   tree then_goto, else_goto;
 285
 286   then_branch = COND_EXPR_THEN (stmt);
 287   else_branch = COND_EXPR_ELSE (stmt);
 288
 289   lower_stmt_body (then_branch, data);
 290   lower_stmt_body (else_branch, data);
 291
 292   then_goto = expr_only (then_branch);
 293   then_is_goto = then_goto && simple_goto_p (then_goto);
 294
 295   else_goto = expr_only (else_branch);
 296   else_is_goto = else_goto && simple_goto_p (else_goto);
 297
 298   if (!then_is_goto || !else_is_goto)
 299     {
 300       tree then_label, else_label, end_label, t;
 301
 302       then_label = NULL_TREE;
 303       else_label = NULL_TREE;
 304       end_label = NULL_TREE;
 305
 306       /* Replace the cond_expr with explicit gotos.  */
 307       if (!then_is_goto)
 308         {
 309           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 310           if (TREE_SIDE_EFFECTS (then_branch))
 311             then_label = t;
 312           else
 313             end_label = t;
 314           then_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 315         }
 316
 317       if (!else_is_goto)
 318         {
 319           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 320           if (TREE_SIDE_EFFECTS (else_branch))
 321             else_label = t;
 322           else
 323             {
 324               /* Both THEN and ELSE can be no-ops if one or both contained an
 325                  empty BIND_EXPR that was associated with the toplevel block
 326                  of an inlined function.  In that case remove_useless_stmts
 327                  can't have cleaned things up for us; kill the whole
 328                  conditional now.  */
 329               if (end_label)
 330                 {
 331                   tsi_delink (tsi);
 332                   return;
 333                 }
 334               else
 335                 end_label = t;
 336             }
 337           else_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 338         }
 339
 340       if (then_label)
 341         {
 342           bool may_fallthru = block_may_fallthru (then_branch);
 343
 344           tsi_link_after (tsi, then_label, TSI_CONTINUE_LINKING);
 345           tsi_link_after (tsi, then_branch, TSI_CONTINUE_LINKING);
 346
 347           if (else_label && may_fallthru)
 348             {
 349               end_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 350               t = build_and_jump (&LABEL_EXPR_LABEL (end_label));
 351               tsi_link_after (tsi, t, TSI_CONTINUE_LINKING);
 352             }
 353         }
 354
 355       if (else_label)
 356         {
 357           tsi_link_after (tsi, else_label, TSI_CONTINUE_LINKING);
 358           tsi_link_after (tsi, else_branch, TSI_CONTINUE_LINKING);
 359         }
 360
 361       if (end_label)
 362         tsi_link_after (tsi, end_label, TSI_CONTINUE_LINKING);
 363     }
 364
 365   COND_EXPR_THEN (stmt) = then_goto;
 366   COND_EXPR_ELSE (stmt) = else_goto;
 367
 368   tsi_next (tsi);
 369 }
 370 \f
 371
 372 /* Record the variables in VARS.  */
 373
 374 void
 375 record_vars (tree vars)
 376 {
 377   for (; vars; vars = TREE_CHAIN (vars))
 378     {
 379       tree var = vars;
 380
 381       /* Nothing to do in this case.  */
 382       if (DECL_EXTERNAL (var))
 383         continue;
 384       if (TREE_CODE (var) == FUNCTION_DECL)
 385         continue;
 386
 387       /* Record the variable.  */
 388       cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
 389                                              cfun->unexpanded_var_list);
 390     }
 391 }
 392
 393 /* Check whether to expand a variable VAR.  */
 394
 395 static bool
 396 expand_var_p (tree var)
 397 {
 398   struct var_ann_d *ann;
 399
 400   if (TREE_CODE (var) != VAR_DECL)
 401     return true;
 402
 403   ann = var_ann (var);
 404
 405   /* Remove all unused, unaliased temporaries.  Also remove unused, unaliased
 406      local variables during highly optimizing compilations.  */
 407   ann = var_ann (var);
 408   if (ann
 409       && ! ann->may_aliases
 410       && ! ann->used
 411       && ! ann->has_hidden_use
 412       && ! TREE_ADDRESSABLE (var)
 413       && ! TREE_THIS_VOLATILE (var)
 414       && (DECL_ARTIFICIAL (var) || optimize >= 2))
 415     return false;
 416
 417   return true;
 418 }
 419
 420 /* Throw away variables that are unused.  */
 421
 422 static void
 423 remove_useless_vars (void)
 424 {
 425   tree var, *cell;
 426
 427   for (cell = &cfun->unexpanded_var_list; *cell; )
 428     {
 429       var = TREE_VALUE (*cell);
 430
 431       if (!expand_var_p (var))
 432         {
 433           *cell = TREE_CHAIN (*cell);
 434           continue;
 435         }
 436
 437       cell = &TREE_CHAIN (*cell);
 438     }
 439 }
 440
 441 /* Expand variables in the unexpanded_var_list.  */
 442
 443 void
 444 expand_used_vars (void)
 445 {
 446   tree cell;
 447
 448   cfun->unexpanded_var_list = nreverse (cfun->unexpanded_var_list);
 449
 450   for (cell = cfun->unexpanded_var_list; cell; cell = TREE_CHAIN (cell))
 451     expand_var (TREE_VALUE (cell));
 452
 453   cfun->unexpanded_var_list = NULL_TREE;
 454 }
 455
 456 struct tree_opt_pass pass_remove_useless_vars =
 457 {
 458   "vars",                               /* name */
 459   NULL,                                 /* gate */
 460   remove_useless_vars,                  /* execute */
 461   NULL,                                 /* sub */
 462   NULL,                                 /* next */
 463   0,                                    /* static_pass_number */
 464   0,                                    /* tv_id */
 465   0,                                    /* properties_required */
 466   0,                                    /* properties_provided */
 467   0,                                    /* properties_destroyed */
 468   0,                                    /* todo_flags_start */
 469   TODO_dump_func                        /* todo_flags_finish */
 470 };
 471
 472