gcc/c-gimplify.c

   1 /* Tree lowering pass.  This pass gimplifies the tree representation built
   2    by the C-based front ends.  The structure of gimplified, or
   3    language-independent, trees is dictated by the grammar described in this
   4    file.
   5    Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
   6    Lowering of expressions contributed by Sebastian Pop <s.pop@laposte.net>
   7    Re-written to support lowering of whole function trees, documentation
   8    and miscellaneous cleanups by Diego Novillo <dnovillo@redhat.com>
   9
  10 This file is part of GCC.
  11
  12 GCC is free software; you can redistribute it and/or modify it under
  13 the terms of the GNU General Public License as published by the Free
  14 Software Foundation; either version 2, or (at your option) any later
  15 version.
  16
  17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20 for more details.
  21
  22 You should have received a copy of the GNU General Public License
  23 along with GCC; see the file COPYING.  If not, write to the Free
  24 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  25 02111-1307, USA.  */
  26
  27 #include "config.h"
  28 #include "system.h"
  29 #include "coretypes.h"
  30 #include "tm.h"
  31 #include "tree.h"
  32 #include "errors.h"
  33 #include "varray.h"
  34 #include "c-tree.h"
  35 #include "c-common.h"
  36 #include "tree-gimple.h"
  37 #include "hard-reg-set.h"
  38 #include "basic-block.h"
  39 #include "tree-flow.h"
  40 #include "tree-inline.h"
  41 #include "diagnostic.h"
  42 #include "langhooks.h"
  43 #include "langhooks-def.h"
  44 #include "flags.h"
  45 #include "rtl.h"
  46 #include "toplev.h"
  47 #include "tree-dump.h"
  48 #include "c-pretty-print.h"
  49 #include "cgraph.h"
  50
  51
  52 /*  The gimplification pass converts the language-dependent trees
  53     (ld-trees) emitted by the parser into language-independent trees
  54     (li-trees) that are the target of SSA analysis and transformations.
  55
  56     Language-independent trees are based on the SIMPLE intermediate
  57     representation used in the McCAT compiler framework:
  58
  59     "Designing the McCAT Compiler Based on a Family of Structured
  60     Intermediate Representations,"
  61     L. Hendren, C. Donawa, M. Emami, G. Gao, Justiani, and B. Sridharan,
  62     Proceedings of the 5th International Workshop on Languages and
  63     Compilers for Parallel Computing, no. 757 in Lecture Notes in
  64     Computer Science, New Haven, Connecticut, pp. 406-420,
  65     Springer-Verlag, August 3-5, 1992.
  66
  67     http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html
  68
  69     Basically, we walk down gimplifying the nodes that we encounter.  As we
  70     walk back up, we check that they fit our constraints, and copy them
  71     into temporaries if not.  */
  72
  73 /* Local declarations.  */
  74
  75 enum bc_t { bc_break = 0, bc_continue = 1 };
  76
  77 static struct c_gimplify_ctx
  78 {
  79   /* For handling break and continue.  */
  80   tree current_bc_label;
  81   tree bc_id[2];
  82 } *ctxp;
  83
  84 static void
  85 push_context (void)
  86 {
  87   if (ctxp)
  88     abort ();
  89   ctxp = (struct c_gimplify_ctx *) xcalloc (1, sizeof (struct c_gimplify_ctx));
  90   ctxp->bc_id[bc_continue] = get_identifier ("continue");
  91   ctxp->bc_id[bc_break] = get_identifier ("break");
  92 }
  93
  94 static void
  95 pop_context (void)
  96 {
  97   if (!ctxp || ctxp->current_bc_label)
  98     abort ();
  99   free (ctxp);
 100   ctxp = NULL;
 101 }
 102
 103 /* Gimplification of statement trees.  */
 104
 105 /* Convert the tree representation of FNDECL from C frontend trees to
 106    GENERIC.  */
 107
 108 void
 109 c_genericize (tree fndecl)
 110 {
 111   FILE *dump_file;
 112   int local_dump_flags;
 113   struct cgraph_node *cgn;
 114
 115   /* Dump the C-specific tree IR.  */
 116   dump_file = dump_begin (TDI_original, &local_dump_flags);
 117   if (dump_file)
 118     {
 119       fprintf (dump_file, "\n;; Function %s",
 120                lang_hooks.decl_printable_name (fndecl, 2));
 121       fprintf (dump_file, " (%s)\n",
 122                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)));
 123       fprintf (dump_file, ";; enabled by -%s\n", dump_flag_name (TDI_original));
 124       fprintf (dump_file, "\n");
 125
 126       if (local_dump_flags & TDF_RAW)
 127         dump_node (DECL_SAVED_TREE (fndecl),
 128                    TDF_SLIM | local_dump_flags, dump_file);
 129       else
 130         print_c_tree (dump_file, DECL_SAVED_TREE (fndecl));
 131       fprintf (dump_file, "\n");
 132
 133       dump_end (TDI_original, dump_file);
 134     }
 135
 136   /* Go ahead and gimplify for now.  */
 137   push_context ();
 138   gimplify_function_tree (fndecl);
 139   pop_context ();
 140
 141   /* Dump the genericized tree IR.  */
 142   dump_function (TDI_generic, fndecl);
 143
 144   /* Genericize all nested functions now.  We do things in this order so
 145      that items like VLA sizes are expanded properly in the context of
 146      the correct function.  */
 147   cgn = cgraph_node (fndecl);
 148   for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
 149     c_genericize (cgn->decl);
 150 }
 151
 152 static void
 153 add_block_to_enclosing (tree block)
 154 {
 155   tree enclosing;
 156
 157   for (enclosing = gimple_current_bind_expr ();
 158        enclosing; enclosing = TREE_CHAIN (enclosing))
 159     if (BIND_EXPR_BLOCK (enclosing))
 160       break;
 161
 162   enclosing = BIND_EXPR_BLOCK (enclosing);
 163   BLOCK_SUBBLOCKS (enclosing) = chainon (BLOCK_SUBBLOCKS (enclosing), block);
 164 }
 165
 166 /* Genericize a scope by creating a new BIND_EXPR.
 167    BLOCK is either a BLOCK representing the scope or a chain of _DECLs.
 168      In the latter case, we need to create a new BLOCK and add it to the
 169      BLOCK_SUBBLOCKS of the enclosing block.
 170    BODY is a chain of C _STMT nodes for the contents of the scope, to be
 171      genericized.  */
 172
 173 tree
 174 c_build_bind_expr (tree block, tree body)
 175 {
 176   tree decls, bind;
 177
 178   if (block == NULL_TREE)
 179     decls = NULL_TREE;
 180   else if (TREE_CODE (block) == BLOCK)
 181     decls = BLOCK_VARS (block);
 182   else
 183     {
 184       decls = block;
 185       if (DECL_ARTIFICIAL (decls))
 186         block = NULL_TREE;
 187       else
 188         {
 189           block = make_node (BLOCK);
 190           BLOCK_VARS (block) = decls;
 191           add_block_to_enclosing (block);
 192         }
 193     }
 194
 195   if (!body)
 196     body = build_empty_stmt ();
 197   if (decls || block)
 198     {
 199       bind = build (BIND_EXPR, void_type_node, decls, body, block);
 200       TREE_SIDE_EFFECTS (bind) = 1;
 201     }
 202   else
 203     bind = body;
 204
 205   return bind;
 206 }
 207
 208 /*  Gimplify an EXPR_STMT node.
 209
 210     STMT is the statement node.
 211
 212     PRE_P points to the list where side effects that must happen before
 213         STMT should be stored.
 214
 215     POST_P points to the list where side effects that must happen after
 216         STMT should be stored.  */
 217
 218 static enum gimplify_status
 219 gimplify_expr_stmt (tree *stmt_p)
 220 {
 221   tree stmt = EXPR_STMT_EXPR (*stmt_p);
 222
 223   if (stmt == error_mark_node)
 224     stmt = NULL;
 225
 226   /* Gimplification of a statement expression will nullify the
 227      statement if all its side effects are moved to *PRE_P and *POST_P.
 228
 229      In this case we will not want to emit the gimplified statement.
 230      However, we may still want to emit a warning, so we do that before
 231      gimplification.  */
 232   if (stmt && (extra_warnings || warn_unused_value))
 233     {
 234       if (!TREE_SIDE_EFFECTS (stmt))
 235         {
 236           if (!IS_EMPTY_STMT (stmt)
 237               && !VOID_TYPE_P (TREE_TYPE (stmt))
 238               && !TREE_NO_WARNING (stmt))
 239             warning ("statement with no effect");
 240         }
 241       else if (warn_unused_value)
 242         warn_if_unused_value (stmt, input_location);
 243     }
 244
 245   if (stmt == NULL_TREE)
 246     stmt = alloc_stmt_list ();
 247
 248   *stmt_p = stmt;
 249
 250   return GS_OK;
 251 }
 252
 253 /* Begin a scope which can be exited by a break or continue statement.  BC
 254    indicates which.
 255
 256    Just creates a label and pushes it into the current context.  */
 257
 258 static tree
 259 begin_bc_block (enum bc_t bc)
 260 {
 261   tree label = create_artificial_label ();
 262   DECL_NAME (label) = ctxp->bc_id[bc];
 263   TREE_CHAIN (label) = ctxp->current_bc_label;
 264   ctxp->current_bc_label = label;
 265   return label;
 266 }
 267
 268 /* Finish a scope which can be exited by a break or continue statement.
 269    LABEL was returned from the most recent call to begin_bc_block.  BODY is
 270    an expression for the contents of the scope.
 271
 272    If we saw a break (or continue) in the scope, append a LABEL_EXPR to
 273    body.  Otherwise, just forget the label.  */
 274
 275 static tree
 276 finish_bc_block (tree label, tree body)
 277 {
 278   if (label != ctxp->current_bc_label)
 279     abort ();
 280
 281   if (TREE_USED (label))
 282     {
 283       tree t, sl = NULL;
 284
 285       /* Clear the name so flow can delete the label.  */
 286       DECL_NAME (label) = NULL_TREE;
 287       t = build1 (LABEL_EXPR, void_type_node, label);
 288
 289       append_to_statement_list (body, &sl);
 290       append_to_statement_list (t, &sl);
 291       body = sl;
 292     }
 293
 294   ctxp->current_bc_label = TREE_CHAIN (label);
 295   TREE_CHAIN (label) = NULL_TREE;
 296   return body;
 297 }
 298
 299 /* Build a GOTO_EXPR to represent a break or continue statement.  BC
 300    indicates which.  */
 301
 302 static tree
 303 build_bc_goto (enum bc_t bc)
 304 {
 305   tree label;
 306   tree target_name = ctxp->bc_id[bc];
 307
 308   /* Look for the appropriate type of label.  */
 309   for (label = ctxp->current_bc_label;
 310        label;
 311        label = TREE_CHAIN (label))
 312     if (DECL_NAME (label) == target_name)
 313       break;
 314
 315   if (label == NULL_TREE)
 316     {
 317       if (bc == bc_break)
 318         error ("break statement not within loop or switch");
 319       else
 320         error ("continue statement not within loop or switch");
 321
 322       return NULL_TREE;
 323     }
 324
 325   /* Mark the label used for finish_bc_block.  */
 326   TREE_USED (label) = 1;
 327   return build1 (GOTO_EXPR, void_type_node, label);
 328 }
 329
 330 /* Build a generic representation of one of the C loop forms.  COND is the
 331    loop condition or NULL_TREE.  BODY is the (possibly compound) statement
 332    controlled by the loop.  INCR is the increment expression of a for-loop,
 333    or NULL_TREE.  COND_IS_FIRST indicates whether the condition is
 334    evaluated before the loop body as in while and for loops, or after the
 335    loop body as in do-while loops.  */
 336
 337 static tree
 338 gimplify_c_loop (tree cond, tree body, tree incr, bool cond_is_first)
 339 {
 340   tree top, entry, exit, cont_block, break_block, stmt_list, t;
 341   location_t stmt_locus;
 342
 343   stmt_locus = input_location;
 344
 345   /* Detect do { ... } while (0) and don't generate loop construct.  */
 346   if (!cond_is_first && cond && integer_zerop (cond))
 347     top = cond = NULL;
 348   else
 349     {
 350       /* If we use a LOOP_EXPR here, we have to feed the whole thing
 351          back through the main gimplifier to lower it.  Given that we
 352          have to gimplify the loop body NOW so that we can resolve
 353          break/continue stmts, seems easier to just expand to gotos.  */
 354       top = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 355     }
 356
 357   break_block = begin_bc_block (bc_break);
 358
 359   if (top)
 360     {
 361       /* If we have an exit condition, then we build an IF with gotos either
 362          out of the loop, or to the top of it.  If there's no exit condition,
 363          then we just build a jump back to the top.  */
 364       exit = build_and_jump (&LABEL_EXPR_LABEL (top));
 365       if (cond)
 366         {
 367           t = build_bc_goto (bc_break);
 368           exit = build (COND_EXPR, void_type_node, cond, exit, t);
 369           exit = fold (exit);
 370           gimplify_stmt (&exit);
 371         }
 372     }
 373   else
 374     exit = NULL_TREE;
 375
 376   cont_block = begin_bc_block (bc_continue);
 377
 378   gimplify_stmt (&body);
 379   gimplify_stmt (&incr);
 380
 381   body = finish_bc_block (cont_block, body);
 382
 383   stmt_list = NULL;
 384
 385   if (cond_is_first && cond)
 386     {
 387       entry = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 388       t = build_and_jump (&LABEL_EXPR_LABEL (entry));
 389       append_to_statement_list (t, &stmt_list);
 390     }
 391   else
 392     entry = NULL_TREE;
 393
 394   append_to_statement_list (top, &stmt_list);
 395   append_to_statement_list (body, &stmt_list);
 396   append_to_statement_list (incr, &stmt_list);
 397   append_to_statement_list (entry, &stmt_list);
 398   append_to_statement_list (exit, &stmt_list);
 399
 400   annotate_all_with_locus (&stmt_list, stmt_locus);
 401
 402   return finish_bc_block (break_block, stmt_list);
 403 }
 404
 405 /* Gimplify a FOR_STMT node.  Move the stuff in the for-init-stmt into the
 406    prequeue and hand off to gimplify_c_loop.  */
 407
 408 static enum gimplify_status
 409 gimplify_for_stmt (tree *stmt_p, tree *pre_p)
 410 {
 411   tree stmt = *stmt_p;
 412
 413   if (FOR_INIT_STMT (stmt))
 414     {
 415       gimplify_stmt (&FOR_INIT_STMT (stmt));
 416       append_to_statement_list (FOR_INIT_STMT (stmt), pre_p);
 417     }
 418   *stmt_p = gimplify_c_loop (FOR_COND (stmt), FOR_BODY (stmt),
 419                              FOR_EXPR (stmt), 1);
 420
 421   return GS_ALL_DONE;
 422 }
 423
 424 /* Gimplify a WHILE_STMT node.  */
 425
 426 static enum gimplify_status
 427 gimplify_while_stmt (tree *stmt_p)
 428 {
 429   tree stmt = *stmt_p;
 430   *stmt_p = gimplify_c_loop (WHILE_COND (stmt), WHILE_BODY (stmt),
 431                              NULL_TREE, 1);
 432   return GS_ALL_DONE;
 433 }
 434
 435 /* Gimplify a DO_STMT node.  */
 436
 437 static enum gimplify_status
 438 gimplify_do_stmt (tree *stmt_p)
 439 {
 440   tree stmt = *stmt_p;
 441   *stmt_p = gimplify_c_loop (DO_COND (stmt), DO_BODY (stmt),
 442                              NULL_TREE, 0);
 443   return GS_ALL_DONE;
 444 }
 445
 446 /* Genericize a SWITCH_STMT by turning it into a SWITCH_EXPR.  */
 447
 448 static enum gimplify_status
 449 gimplify_switch_stmt (tree *stmt_p)
 450 {
 451   tree stmt = *stmt_p;
 452   tree break_block, body;
 453   location_t stmt_locus = input_location;
 454
 455   break_block = begin_bc_block (bc_break);
 456
 457   body = SWITCH_BODY (stmt);
 458   if (!body)
 459     body = build_empty_stmt ();
 460
 461   *stmt_p = build (SWITCH_EXPR, SWITCH_TYPE (stmt), SWITCH_COND (stmt),
 462                    body, NULL_TREE);
 463   annotate_with_locus (*stmt_p, stmt_locus);
 464   gimplify_stmt (stmt_p);
 465
 466   *stmt_p = finish_bc_block (break_block, *stmt_p);
 467   return GS_ALL_DONE;
 468 }
 469
 470 /* Gimplifies a DECL_STMT node *STMT_P by making any necessary allocation
 471    and initialization explicit.  */
 472
 473 static enum gimplify_status
 474 gimplify_decl_stmt (tree *stmt_p)
 475 {
 476   tree stmt = *stmt_p;
 477   tree decl = DECL_STMT_DECL (stmt);
 478
 479   *stmt_p = NULL_TREE;
 480
 481   if (TREE_TYPE (decl) == error_mark_node)
 482     return GS_ERROR;
 483
 484   if (TREE_CODE (decl) == TYPE_DECL)
 485     gimplify_type_sizes (TREE_TYPE (decl), stmt_p);
 486
 487   else if (TREE_CODE (decl) == VAR_DECL && !DECL_EXTERNAL (decl))
 488     {
 489       tree init = DECL_INITIAL (decl);
 490
 491       gimplify_one_sizepos (&DECL_SIZE (decl), stmt_p);
 492       gimplify_one_sizepos (&DECL_SIZE_UNIT (decl), stmt_p);
 493
 494       if (!TREE_CONSTANT (DECL_SIZE (decl)))
 495         {
 496           /* This is a variable-sized decl.  Simplify its size and mark it
 497              for deferred expansion.  Note that mudflap depends on the format
 498              of the emitted code: see mx_register_decls().  */
 499
 500           tree pt_type = build_pointer_type (TREE_TYPE (decl));
 501           tree alloc_stmt
 502             = (build_function_call_expr
 503                (implicit_built_in_decls[BUILT_IN_STACK_ALLOC],
 504                 tree_cons (NULL_TREE,
 505                            build1 (ADDR_EXPR, pt_type, decl),
 506                            tree_cons (NULL_TREE, DECL_SIZE_UNIT (decl),
 507                                       NULL_TREE))));
 508
 509           gimplify_and_add (alloc_stmt, stmt_p);
 510           DECL_DEFER_OUTPUT (decl) = 1;
 511         }
 512
 513       if (init && init != error_mark_node)
 514         {
 515           if (!TREE_STATIC (decl))
 516             {
 517               /* Do not warn about int x = x; as it is a GCC extension
 518                  to turn off this warning but only if warn_init_self
 519                  is zero.  */
 520               if (init == decl && !warn_init_self)
 521                 TREE_NO_WARNING (decl) = 1;
 522
 523               DECL_INITIAL (decl) = NULL_TREE;
 524               init = build (MODIFY_EXPR, void_type_node, decl, init);
 525               gimplify_and_add (init, stmt_p);
 526             }
 527           else
 528             /* We must still examine initializers for static variables
 529                as they may contain a label address.  */
 530             walk_tree (&init, force_labels_r, NULL, NULL);
 531         }
 532
 533       /* This decl isn't mentioned in the enclosing block, so add it to the
 534          list of temps.  FIXME it seems a bit of a kludge to say that
 535          anonymous artificial vars aren't pushed, but everything else is.  */
 536       if (DECL_ARTIFICIAL (decl) && DECL_NAME (decl) == NULL_TREE)
 537         gimple_add_tmp_var (decl);
 538     }
 539
 540   return GS_ALL_DONE;
 541 }
 542
 543 /* Gimplification of expression trees.  */
 544
 545 /* Gimplify a C99 compound literal expression.  This just means adding the
 546    DECL_STMT before the current EXPR_STMT and using its anonymous decl
 547    instead.  */
 548
 549 static enum gimplify_status
 550 gimplify_compound_literal_expr (tree *expr_p, tree *pre_p)
 551 {
 552   tree decl_s = COMPOUND_LITERAL_EXPR_DECL_STMT (*expr_p);
 553   tree decl = DECL_STMT_DECL (decl_s);
 554
 555   /* This decl isn't mentioned in the enclosing block, so add it to the
 556      list of temps.  FIXME it seems a bit of a kludge to say that
 557      anonymous artificial vars aren't pushed, but everything else is.  */
 558   if (DECL_NAME (decl) == NULL_TREE)
 559     gimple_add_tmp_var (decl);
 560
 561   gimplify_decl_stmt (&decl_s);
 562   append_to_statement_list (decl_s, pre_p);
 563   *expr_p = decl;
 564   return GS_OK;
 565 }
 566
 567 /* Do C-specific gimplification.  Args are as for gimplify_expr.  */
 568
 569 int
 570 c_gimplify_expr (tree *expr_p, tree *pre_p, tree *post_p ATTRIBUTE_UNUSED)
 571 {
 572   enum tree_code code = TREE_CODE (*expr_p);
 573
 574   switch (code)
 575     {
 576     case COMPOUND_LITERAL_EXPR:
 577       return gimplify_compound_literal_expr (expr_p, pre_p);
 578
 579     case FOR_STMT:
 580       return gimplify_for_stmt (expr_p, pre_p);
 581
 582     case WHILE_STMT:
 583       return gimplify_while_stmt (expr_p);
 584
 585     case DO_STMT:
 586       return gimplify_do_stmt (expr_p);
 587
 588     case SWITCH_STMT:
 589       return gimplify_switch_stmt (expr_p);
 590
 591     case EXPR_STMT:
 592       return gimplify_expr_stmt (expr_p);
 593
 594     case DECL_STMT:
 595       return gimplify_decl_stmt (expr_p);
 596
 597     case CONTINUE_STMT:
 598       *expr_p = build_bc_goto (bc_continue);
 599       return GS_ALL_DONE;
 600
 601     case BREAK_STMT:
 602       *expr_p = build_bc_goto (bc_break);
 603       return GS_ALL_DONE;
 604
 605     default:
 606       return GS_UNHANDLED;
 607     }
 608 }