gcc/tree-optimize.c

   1 /* Control and data flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License 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
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 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 "tm_p.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "expr.h"
  33 #include "diagnostic.h"
  34 #include "basic-block.h"
  35 #include "flags.h"
  36 #include "tree-flow.h"
  37 #include "tree-dump.h"
  38 #include "timevar.h"
  39 #include "function.h"
  40 #include "langhooks.h"
  41 #include "toplev.h"
  42 #include "flags.h"
  43 #include "cgraph.h"
  44 #include "tree-inline.h"
  45 #include "tree-mudflap.h"
  46 #include "ggc.h"
  47
  48 /* Rewrite a function tree to the SSA form and perform the SSA-based
  49    optimizations on it.  */
  50
  51 /* Main entry point to the tree SSA transformation routines.  FNDECL is the
  52    FUNCTION_DECL node for the function to optimize.  */
  53 void
  54 optimize_function_tree (tree fndecl)
  55 {
  56   tree fnbody;
  57   struct tree_container head;
  58   tree_cell first, last;
  59
  60   /* Don't bother doing anything if the program has errors.  */
  61   if (errorcount || sorrycount)
  62     return;
  63
  64   lower_function_body (&DECL_SAVED_TREE (fndecl));
  65   fnbody = DECL_SAVED_TREE (fndecl);
  66
  67   /* Avoid producing notes for blocks.  */
  68   cfun->dont_emit_block_notes = 1;
  69   reset_block_changes ();
  70
  71   /* Flatten the trees.  */
  72   head.prev = head.next = NULL;
  73   last = &head;
  74   tree_flatten_statement (BIND_EXPR_BODY (fnbody), &last, NULL_TREE);
  75   first = head.next;
  76
  77   if (!first)
  78     {
  79       /* The function is empty, we are done.  */
  80       DECL_SAVED_TREE (fndecl) = build_empty_stmt ();
  81       return;
  82     }
  83
  84   first->prev = NULL;
  85
  86   /* Let the garbage collector release now unnecesary containers.  */
  87   BIND_EXPR_BODY (fnbody) = NULL_TREE;
  88
  89   /* Build the flowgraph.  */
  90   init_flow ();
  91   build_tree_cfg (first);
  92
  93   /* Begin analysis and optimization passes.  After the function is
  94      initially renamed into SSA form, passes are responsible from keeping
  95      it in SSA form.  If a pass exposes new symbols or invalidates the SSA
  96      numbering for existing variables, it should add them to the
  97      VARS_TO_RENAME bitmap and call rewrite_into_ssa() afterwards.  */
  98   if (n_basic_blocks > 0 && ! (errorcount || sorrycount))
  99     {
 100       sbitmap vars_to_rename;
 101
 102       /* Initialize common SSA structures.  */
 103       init_tree_ssa ();
 104
 105       /* Find all the variables referenced in the function.  */
 106       find_referenced_vars (fndecl);
 107
 108       /* Compute aliasing information for all the variables referenced in
 109          the function.  */
 110       compute_may_aliases (fndecl);
 111
 112
 113       /*                        BEGIN SSA PASSES
 114
 115          IMPORTANT: If you change the order in which these passes are
 116                     executed, you also need to change the enum
 117                     TREE_DUMP_INDEX in tree.h and DUMP_FILES in
 118                     tree-dump.c.  */
 119
 120
 121       /* Rewrite the function into SSA form.  Initially, request all
 122          variables to be renamed.  */
 123       rewrite_into_ssa (fndecl, NULL, TDI_ssa_1);
 124
 125       /* Set up VARS_TO_RENAME to allow passes to inform which variables
 126          need to be renamed.  */
 127       vars_to_rename = sbitmap_alloc (num_referenced_vars);
 128
 129       /* Perform dominator optimizations.  */
 130       if (flag_tree_dom)
 131         {
 132           sbitmap_zero (vars_to_rename);
 133           tree_ssa_dominator_optimize (fndecl, vars_to_rename, TDI_dom_1);
 134
 135           /* If the dominator optimizations exposed new variables, we need
 136               to repeat the SSA renaming process for those symbols.  */
 137           if (sbitmap_first_set_bit (vars_to_rename) >= 0)
 138             rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
 139         }
 140
 141       /* Do a first DCE pass prior to must-alias.  This pass will remove
 142          dead pointer assignments taking the address of local variables.  */
 143       if (flag_tree_dce)
 144         tree_ssa_dce (fndecl, TDI_dce_1);
 145
 146       /* The must-alias pass removes the aliasing and addressability bits
 147          from variables that used to have their address taken.  */
 148       if (flag_tree_must_alias)
 149         {
 150           sbitmap_zero (vars_to_rename);
 151           tree_compute_must_alias (fndecl, vars_to_rename, TDI_mustalias);
 152
 153           /* Run the SSA pass again if we need to rename new variables.  */
 154           if (sbitmap_first_set_bit (vars_to_rename) >= 0)
 155             rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_3);
 156         }
 157
 158       /* Run SCCP (Sparse Conditional Constant Propagation).  */
 159       if (flag_tree_ccp)
 160         {
 161           sbitmap_zero (vars_to_rename);
 162           tree_ssa_ccp (fndecl, vars_to_rename, TDI_ccp);
 163
 164           /* Run the SSA pass again if we need to rename new variables.  */
 165           if (sbitmap_first_set_bit (vars_to_rename) >= 0)
 166             rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
 167         }
 168
 169       /* Run SSA-PRE (Partial Redundancy Elimination).  */
 170       if (flag_tree_pre)
 171         tree_perform_ssapre (fndecl, TDI_pre);
 172
 173       /* Perform a second pass of dominator optimizations.  */
 174       if (flag_tree_dom)
 175         {
 176           sbitmap_zero (vars_to_rename);
 177           tree_ssa_dominator_optimize (fndecl, vars_to_rename, TDI_dom_2);
 178
 179           /* Run the SSA pass again if we need to rename new variables.  */
 180           if (sbitmap_first_set_bit (vars_to_rename) >= 0)
 181             rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_5);
 182         }
 183
 184       /* Run copy propagation.  */
 185       if (flag_tree_copyprop)
 186         tree_ssa_copyprop (fndecl, TDI_copyprop);
 187
 188       /* Do a second DCE pass.  */
 189       if (flag_tree_dce)
 190         tree_ssa_dce (fndecl, TDI_dce_2);
 191
 192 #if defined ENABLE_CHECKING
 193       verify_flow_info ();
 194 #endif
 195
 196       /* Rewrite the function out of SSA form.  */
 197       rewrite_out_of_ssa (fndecl, TDI_optimized);
 198
 199       sbitmap_free (vars_to_rename);
 200     }
 201
 202   fnbody = tree_unflatten_statements ();
 203   BIND_EXPR_BODY (DECL_SAVED_TREE (fndecl)) = fnbody;
 204
 205   /* Debugging dump after optimization.  */
 206   dump_function (TDI_optimized, fndecl);
 207 }
 208
 209 \f
 210 /* Called to move the SAVE_EXPRs for parameter declarations in a
 211    nested function into the nested function.  DATA is really the
 212    nested FUNCTION_DECL.  */
 213
 214 static tree
 215 set_save_expr_context (tree *tp,
 216                        int *walk_subtrees,
 217                        void *data)
 218 {
 219   if (TREE_CODE (*tp) == SAVE_EXPR && !SAVE_EXPR_CONTEXT (*tp))
 220     SAVE_EXPR_CONTEXT (*tp) = (tree) data;
 221   /* Do not walk back into the SAVE_EXPR_CONTEXT; that will cause
 222      circularity.  */
 223   else if (DECL_P (*tp))
 224     *walk_subtrees = 0;
 225
 226   return NULL;
 227 }
 228
 229 /* Clear out the DECL_RTL for the non-static local variables in BLOCK and
 230    its sub-blocks.  DATA is the decl of the function being processed.  */
 231
 232 static tree
 233 clear_decl_rtl (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
 234 {
 235   bool nonstatic_p, local_p;
 236   tree t = *tp;
 237
 238   switch (TREE_CODE (t))
 239     {
 240     case VAR_DECL:
 241       nonstatic_p = !TREE_STATIC (t) && !DECL_EXTERNAL (t);
 242       local_p = DECL_CONTEXT (t) == data;
 243       break;
 244
 245     case PARM_DECL:
 246     case LABEL_DECL:
 247       nonstatic_p = true;
 248       local_p = DECL_CONTEXT (t) == data;
 249       break;
 250
 251     case RESULT_DECL:
 252       nonstatic_p = local_p = true;
 253       break;
 254
 255     default:
 256       nonstatic_p = local_p = false;
 257       break;
 258     }
 259
 260   if (nonstatic_p && local_p)
 261     SET_DECL_RTL (t, NULL);
 262
 263   return NULL;
 264 }
 265
 266 /* For functions-as-trees languages, this performs all optimization and
 267    compilation for FNDECL.  */
 268
 269 void
 270 tree_rest_of_compilation (tree fndecl, bool nested_p)
 271 {
 272   location_t saved_loc;
 273   tree saved_tree = NULL;
 274   bool do_optimize;
 275
 276   /* Don't bother doing anything if there are errors.  */
 277   if (errorcount || sorrycount)
 278     {
 279       TREE_ASM_WRITTEN (fndecl) = 1;
 280       return;
 281     }
 282
 283   timevar_push (TV_EXPAND);
 284
 285   if (flag_unit_at_a_time && !cgraph_global_info_ready)
 286     abort ();
 287
 288   /* Initialize the RTL code for the function.  */
 289   current_function_decl = fndecl;
 290   saved_loc = input_location;
 291   input_location = DECL_SOURCE_LOCATION (fndecl);
 292   init_function_start (fndecl);
 293
 294   /* This function is being processed in whole-function mode.  */
 295   cfun->x_whole_function_mode_p = 1;
 296
 297   /* Even though we're inside a function body, we still don't want to
 298      call expand_expr to calculate the size of a variable-sized array.
 299      We haven't necessarily assigned RTL to all variables yet, so it's
 300      not safe to try to expand expressions involving them.  */
 301   immediate_size_expand = 0;
 302   cfun->x_dont_save_pending_sizes_p = 1;
 303
 304   /* We might need the body of this function so that we can expand
 305      it inline somewhere else.  This means not lowering some constructs
 306      such as exception handling.  */
 307   if (DECL_INLINE (fndecl) && flag_inline_trees)
 308     {
 309       saved_tree = lhd_unsave_expr_now (DECL_SAVED_TREE (fndecl));
 310       /* ??? We're saving this value here on the stack.  Don't gc it.  */
 311       nested_p = true;
 312     }
 313
 314   /* Gimplify the function.  Don't try to optimize the function if
 315      gimplification failed.  */
 316   do_optimize = (!flag_disable_gimple
 317                  && (keep_function_tree_in_gimple_form (fndecl)
 318                      || gimplify_function_tree (fndecl)));
 319
 320
 321   /* Do these start-of-function steps now, so that declare_nonlocal_label
 322      (called from gimple-low.c during variable expansion) is happy.  */
 323
 324   /* If the function has a variably modified type, there may be
 325      SAVE_EXPRs in the parameter types.  Their context must be set to
 326      refer to this function; they cannot be expanded in the containing
 327      function.  */
 328   if (decl_function_context (fndecl)
 329       && variably_modified_type_p (TREE_TYPE (fndecl)))
 330     walk_tree (&TREE_TYPE (fndecl), set_save_expr_context, fndecl,
 331                NULL);
 332
 333   /* Set up parameters and prepare for return, for the function.  */
 334   expand_function_start (fndecl, 0);
 335
 336   if (do_optimize)
 337     {
 338       /* Debugging dump after gimplification.  */
 339       dump_function (TDI_gimple, fndecl);
 340
 341       /* Run a pass over the statements deleting any obviously useless
 342          statements before we build the CFG.  */
 343       remove_useless_stmts_and_vars (&DECL_SAVED_TREE (fndecl), false);
 344       {
 345         int flags;
 346         FILE *file = dump_begin (TDI_useless, &flags);
 347         if (file)
 348           {
 349             dump_function_to_file (fndecl, file, flags);
 350             dump_end (TDI_useless, file);
 351           }
 352       }
 353
 354       /* Run a pass to lower magic exception handling constructs into,
 355          well, less magic though not completely mundane constructs.  */
 356       lower_eh_constructs (&DECL_SAVED_TREE (fndecl));
 357
 358       /* Invoke the SSA tree optimizer.  */
 359       if (optimize >= 1 && !flag_disable_tree_ssa)
 360         optimize_function_tree (fndecl);
 361
 362       /* Do some cleanups which reduce the amount of data the
 363          tree->rtl expanders deal with.  */
 364       remove_useless_stmts_and_vars (&DECL_SAVED_TREE (fndecl), true);
 365     }
 366
 367   /* Allow language dialects to perform special processing.  */
 368   (*lang_hooks.rtl_expand.start) ();
 369
 370   /* If this function is `main', emit a call to `__main'
 371      to run global initializers, etc.  */
 372   if (DECL_NAME (fndecl)
 373       && MAIN_NAME_P (DECL_NAME (fndecl))
 374       && DECL_FILE_SCOPE_P (fndecl))
 375     expand_main_function ();
 376
 377   /* Add mudflap instrumentation to a copy of the function body.  */
 378   if (flag_mudflap)
 379     DECL_SAVED_TREE (fndecl) = mudflap_c_function (fndecl);
 380
 381   /* Generate the RTL for this function.  */
 382   (*lang_hooks.rtl_expand.stmt) (DECL_SAVED_TREE (fndecl));
 383
 384   /* We hard-wired immediate_size_expand to zero above.
 385      expand_function_end will decrement this variable.  So, we set the
 386      variable to one here, so that after the decrement it will remain
 387      zero.  */
 388   immediate_size_expand = 1;
 389
 390   /* Make sure the locus is set to the end of the function, so that
 391      epilogue line numbers and warnings are set properly.  */
 392   if (cfun->function_end_locus.file)
 393     input_location = cfun->function_end_locus;
 394
 395   /* Allow language dialects to perform special processing.  */
 396   (*lang_hooks.rtl_expand.end) ();
 397
 398   /* Generate rtl for function exit.  */
 399   expand_function_end ();
 400
 401   /* If this is a nested function, protect the local variables in the stack
 402      above us from being collected while we're compiling this function.  */
 403   if (nested_p)
 404     ggc_push_context ();
 405
 406   /* There's no need to defer outputting this function any more; we
 407      know we want to output it.  */
 408   DECL_DEFER_OUTPUT (fndecl) = 0;
 409
 410   /* Run the optimizers and output the assembler code for this function.  */
 411   rest_of_compilation (fndecl);
 412
 413   /* Undo the GC context switch.  */
 414   if (nested_p)
 415     ggc_pop_context ();
 416
 417   /* If requested, warn about function definitions where the function will
 418      return a value (usually of some struct or union type) which itself will
 419      take up a lot of stack space.  */
 420   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 421     {
 422       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 423
 424       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 425           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 426           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 427                                    larger_than_size))
 428         {
 429           unsigned int size_as_int
 430             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 431
 432           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 433             warning ("%Jsize of return value of '%D' is %u bytes",
 434                      fndecl, fndecl, size_as_int);
 435           else
 436             warning ("%Jsize of return value of '%D' is larger than %wd bytes",
 437                      fndecl, fndecl, larger_than_size);
 438         }
 439     }
 440
 441   /* ??? Looks like some of this could be combined.  */
 442
 443   if (DECL_INLINE (fndecl) && flag_inline_trees)
 444     {
 445       /* We might need the body of this function so that we can expand
 446          it inline somewhere else.  */
 447       DECL_SAVED_TREE (fndecl) = saved_tree;
 448     }
 449
 450   /* If possible, obliterate the body of the function so that it can
 451      be garbage collected.  */
 452   else if (dump_enabled_p (TDI_all))
 453     /* Keep the body; we're going to dump it.  */
 454     ;
 455   else
 456     /* We don't need the body; blow it away.  */
 457     DECL_SAVED_TREE (fndecl) = NULL;
 458
 459   /* Since we don't need the RTL for this function anymore, stop pointing to
 460      it.  That's especially important for LABEL_DECLs, since you can reach all
 461      the instructions in the function from the CODE_LABEL stored in the
 462      DECL_RTL for the LABEL_DECL.  Walk the BLOCK-tree, clearing DECL_RTL for
 463      LABEL_DECLs and non-static local variables.  Note that we must check the
 464      context of the variables, otherwise processing a nested function can kill
 465      the rtl of a variable from an outer function.  */
 466   walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
 467                                 clear_decl_rtl,
 468                                 fndecl);
 469
 470   if (DECL_SAVED_INSNS (fndecl) == 0 && !nested_p && !flag_inline_trees)
 471     {
 472       /* Stop pointing to the local nodes about to be freed.
 473          But DECL_INITIAL must remain nonzero so we know this
 474          was an actual function definition.
 475          For a nested function, this is done in c_pop_function_context.
 476          If rest_of_compilation set this to 0, leave it 0.  */
 477       if (DECL_INITIAL (fndecl) != 0)
 478         DECL_INITIAL (fndecl) = error_mark_node;
 479
 480       DECL_ARGUMENTS (fndecl) = 0;
 481     }
 482
 483   input_location = saved_loc;
 484
 485   timevar_pop (TV_EXPAND);
 486 }