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