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   if (TREE_TYPE (decl) == error_mark_node)
 480     {
 481       *stmt_p = NULL;
 482       return GS_ERROR;
 483     }
 484
 485   if (TREE_CODE (decl) == TYPE_DECL)
 486     *stmt_p = gimplify_type_sizes (TREE_TYPE (decl));
 487
 488   else if (TREE_CODE (decl) == VAR_DECL && !DECL_EXTERNAL (decl))
 489     {
 490       tree init = DECL_INITIAL (decl);
 491
 492       *stmt_p = NULL_TREE;
 493       gimplify_one_sizepos (&DECL_SIZE (decl), stmt_p);
 494       gimplify_one_sizepos (&DECL_SIZE_UNIT (decl), stmt_p);
 495
 496       if (!TREE_CONSTANT (DECL_SIZE (decl)))
 497         {
 498           /* This is a variable-sized decl.  Simplify its size and mark it
 499              for deferred expansion.  Note that mudflap depends on the format
 500              of the emitted code: see mx_register_decls().  */
 501
 502           tree pt_type = build_pointer_type (TREE_TYPE (decl));
 503           tree alloc_stmt
 504             = (build_function_call_expr
 505                (implicit_built_in_decls[BUILT_IN_STACK_ALLOC],
 506                 tree_cons (NULL_TREE,
 507                            build1 (ADDR_EXPR, pt_type, decl),
 508                            tree_cons (NULL_TREE, DECL_SIZE_UNIT (decl),
 509                                       NULL_TREE))));
 510
 511           gimplify_stmt (&alloc_stmt);
 512           append_to_statement_list(alloc_stmt, stmt_p);
 513           DECL_DEFER_OUTPUT (decl) = 1;
 514         }
 515
 516       if (init && init != error_mark_node)
 517         {
 518           if (!TREE_STATIC (decl))
 519             {
 520               /* Do not warn about int x = x; as it is a GCC extension
 521                  to turn off this warning but only if warn_init_self
 522                  is zero.  */
 523               if (init == decl && !warn_init_self)
 524                 TREE_NO_WARNING (decl) = 1;
 525
 526               DECL_INITIAL (decl) = NULL_TREE;
 527               init = build (MODIFY_EXPR, void_type_node, decl, init);
 528               gimplify_stmt (&init);
 529               append_to_statement_list (init, stmt_p);
 530             }
 531           else
 532             /* We must still examine initializers for static variables
 533                as they may contain a label address.  */
 534             walk_tree (&init, force_labels_r, NULL, NULL);
 535         }
 536
 537       /* This decl isn't mentioned in the enclosing block, so add it to the
 538          list of temps.  FIXME it seems a bit of a kludge to say that
 539          anonymous artificial vars aren't pushed, but everything else is.  */
 540       if (DECL_ARTIFICIAL (decl) && DECL_NAME (decl) == NULL_TREE)
 541         gimple_add_tmp_var (decl);
 542     }
 543   else
 544     *stmt_p = alloc_stmt_list ();
 545
 546   return GS_ALL_DONE;
 547 }
 548
 549 /* Gimplification of expression trees.  */
 550
 551 /* Gimplify a C99 compound literal expression.  This just means adding the
 552    DECL_STMT before the current EXPR_STMT and using its anonymous decl
 553    instead.  */
 554
 555 static enum gimplify_status
 556 gimplify_compound_literal_expr (tree *expr_p, tree *pre_p)
 557 {
 558   tree decl_s = COMPOUND_LITERAL_EXPR_DECL_STMT (*expr_p);
 559   tree decl = DECL_STMT_DECL (decl_s);
 560
 561   /* This decl isn't mentioned in the enclosing block, so add it to the
 562      list of temps.  FIXME it seems a bit of a kludge to say that
 563      anonymous artificial vars aren't pushed, but everything else is.  */
 564   if (DECL_NAME (decl) == NULL_TREE)
 565     gimple_add_tmp_var (decl);
 566
 567   gimplify_decl_stmt (&decl_s);
 568   append_to_statement_list (decl_s, pre_p);
 569   *expr_p = decl;
 570   return GS_OK;
 571 }
 572
 573 /* Do C-specific gimplification.  Args are as for gimplify_expr.  */
 574
 575 int
 576 c_gimplify_expr (tree *expr_p, tree *pre_p, tree *post_p ATTRIBUTE_UNUSED)
 577 {
 578   enum tree_code code = TREE_CODE (*expr_p);
 579
 580   switch (code)
 581     {
 582     case COMPOUND_LITERAL_EXPR:
 583       return gimplify_compound_literal_expr (expr_p, pre_p);
 584
 585     case FOR_STMT:
 586       return gimplify_for_stmt (expr_p, pre_p);
 587
 588     case WHILE_STMT:
 589       return gimplify_while_stmt (expr_p);
 590
 591     case DO_STMT:
 592       return gimplify_do_stmt (expr_p);
 593
 594     case SWITCH_STMT:
 595       return gimplify_switch_stmt (expr_p);
 596
 597     case EXPR_STMT:
 598       return gimplify_expr_stmt (expr_p);
 599
 600     case DECL_STMT:
 601       return gimplify_decl_stmt (expr_p);
 602
 603     case CONTINUE_STMT:
 604       *expr_p = build_bc_goto (bc_continue);
 605       return GS_ALL_DONE;
 606
 607     case BREAK_STMT:
 608       *expr_p = build_bc_goto (bc_break);
 609       return GS_ALL_DONE;
 610
 611     default:
 612       return GS_UNHANDLED;
 613     }
 614 }