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