gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4    Rewritten by Jason Merrill <jason@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "ggc.h"
  27 #include "tm.h"
  28 #include "tree.h"
  29 #include "tree-gimple.h"
  30 #include "output.h"
  31 #include "rtl.h"
  32 #include "expr.h"
  33 #include "bitmap.h"
  34
  35 /* GCC GIMPLE structure
  36
  37    Inspired by the SIMPLE C grammar at
  38
  39         http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html
  40
  41    function:
  42      FUNCTION_DECL
  43        DECL_SAVED_TREE -> block
  44    block:
  45      BIND_EXPR
  46        BIND_EXPR_VARS -> DECL chain
  47        BIND_EXPR_BLOCK -> BLOCK
  48        BIND_EXPR_BODY -> compound-stmt
  49    compound-stmt:
  50      COMPOUND_EXPR
  51        op0 -> non-compound-stmt
  52        op1 -> stmt
  53      | EXPR_VEC
  54        (or other alternate solution)
  55    stmt: compound-stmt | non-compound-stmt
  56    non-compound-stmt:
  57      block
  58      | if-stmt
  59      | switch-stmt
  60      | jump-stmt
  61      | label-stmt
  62      | try-stmt
  63      | modify-stmt
  64      | call-stmt
  65    if-stmt:
  66      COND_EXPR
  67        op0 -> condition
  68        op1 -> stmt
  69        op2 -> stmt
  70    switch-stmt:
  71      SWITCH_EXPR
  72        op0 -> val
  73        op1 -> stmt
  74        op2 -> array of case labels (as LABEL_DECLs?)
  75          FIXME: add case value info
  76         The SWITCH_LABELS (op2) are sorted in ascending order, and the
  77         last label in the vector is always the default case.
  78    jump-stmt:
  79        GOTO_EXPR
  80          op0 -> LABEL_DECL | '*' ID
  81      | RETURN_EXPR
  82          op0 -> modify-stmt | NULL_TREE
  83          (maybe -> RESULT_DECL | NULL_TREE? seems like some of expand_return
  84           depends on getting a MODIFY_EXPR.)
  85      | THROW_EXPR?  do we need/want such a thing for opts, perhaps
  86          to generate an ERT_THROW region?  I think so.
  87          Hmm...this would only work at the GIMPLE level, where we know that
  88            the call args don't have any EH impact.  Perhaps
  89            annotation of the CALL_EXPR would work better.
  90      | RESX_EXPR
  91    label-stmt:
  92      LABEL_EXPR
  93          op0 -> LABEL_DECL
  94      | CASE_LABEL_EXPR
  95          CASE_LOW -> val | NULL_TREE
  96          CASE_HIGH -> val | NULL_TREE
  97          CASE_LABEL -> LABEL_DECL  FIXME
  98    try-stmt:
  99      TRY_CATCH_EXPR
 100        op0 -> stmt
 101        op1 -> handler
 102      | TRY_FINALLY_EXPR
 103        op0 -> stmt
 104        op1 -> stmt
 105    handler:
 106      catch-seq
 107      | EH_FILTER_EXPR
 108      | stmt
 109    modify-stmt:
 110      MODIFY_EXPR
 111        op0 -> lhs
 112        op1 -> rhs
 113    call-stmt: CALL_EXPR
 114      op0 -> ID | '&' ID
 115      op1 -> arglist
 116
 117    addr-expr-arg : compref | ID
 118    lhs: addr-expr-arg | '*' ID | bitfieldref
 119    min-lval: ID | '*' ID
 120    bitfieldref :
 121      BIT_FIELD_REF
 122        op0 -> compref | min-lval
 123        op1 -> CONST
 124        op2 -> CONST
 125    compref :
 126      COMPONENT_REF
 127        op0 -> compref | min-lval
 128      | ARRAY_REF
 129        op0 -> compref | min-lval
 130        op1 -> val
 131      | REALPART_EXPR
 132      | IMAGPART_EXPR
 133
 134    condition : val | val relop val
 135    val : ID | CONST
 136
 137    rhs        : varname | CONST
 138               | '*' ID
 139               | '&' addr-expr-arg
 140               | call_expr
 141               | unop val
 142               | val binop val
 143               | '(' cast ')' val
 144
 145               (cast here stands for all valid C typecasts)
 146
 147       unop
 148               : '+'
 149               | '-'
 150               | '!'
 151               | '~'
 152
 153       binop
 154               : relop | '-'
 155               | '+'
 156               | '/'
 157               | '*'
 158               | '%'
 159               | '&'
 160               | '|'
 161               | '<<'
 162               | '>>'
 163               | '^'
 164
 165       relop
 166               : '<'
 167               | '<='
 168               | '>'
 169               | '>='
 170               | '=='
 171               | '!='
 172
 173 */
 174
 175 static inline bool is_gimple_id (tree);
 176
 177 /* Validation of GIMPLE expressions.  */
 178
 179 /* Return nonzero if T is a GIMPLE RHS:
 180
 181       rhs     : varname | CONST
 182               | '*' ID
 183               | '&' varname_or_temp
 184               | call_expr
 185               | unop val
 186               | val binop val
 187               | '(' cast ')' val
 188               | <CONSTRUCTOR <gimple_val ...>>
 189
 190    The last option is only valid GIMPLE for vector and complex types;
 191    aggregate types should have their constructors decomposed.  */
 192
 193 bool
 194 is_gimple_rhs (tree t)
 195 {
 196   enum tree_code code = TREE_CODE (t);
 197
 198   switch (TREE_CODE_CLASS (code))
 199     {
 200     case '1':
 201     case '2':
 202     case '<':
 203       return 1;
 204
 205     default:
 206       break;
 207     }
 208
 209   switch (code)
 210     {
 211     case TRUTH_NOT_EXPR:
 212     case TRUTH_AND_EXPR:
 213     case TRUTH_OR_EXPR:
 214     case TRUTH_XOR_EXPR:
 215     case ADDR_EXPR:
 216     case CALL_EXPR:
 217     case CONSTRUCTOR:
 218     case COMPLEX_EXPR:
 219       /* FIXME lower VA_ARG_EXPR.  */
 220     case VA_ARG_EXPR:
 221     case INTEGER_CST:
 222     case REAL_CST:
 223     case STRING_CST:
 224     case COMPLEX_CST:
 225     case VECTOR_CST:
 226       return 1;
 227
 228     default:
 229       break;
 230     }
 231
 232   if (is_gimple_lvalue (t) || is_gimple_val (t))
 233     return 1;
 234
 235   return 0;
 236 }
 237
 238 /* Returns nonzero if T is a valid CONSTRUCTOR component in GIMPLE, either
 239    a val or another CONSTRUCTOR.  */
 240
 241 bool
 242 is_gimple_constructor_elt (tree t)
 243 {
 244   return (is_gimple_val (t)
 245           || TREE_CODE (t) == CONSTRUCTOR);
 246 }
 247
 248 /*  Return nonzero if T is a valid LHS for a GIMPLE assignment expression.  */
 249
 250 bool
 251 is_gimple_lvalue (tree t)
 252 {
 253   return (is_gimple_addr_expr_arg (t)
 254           || TREE_CODE (t) == INDIRECT_REF
 255           /* These are complex lvalues, but don't have addresses, so they
 256              go here.  */
 257           || TREE_CODE (t) == BIT_FIELD_REF);
 258 }
 259
 260
 261 /*  Return nonzero if T is a GIMPLE condition:
 262
 263       condexpr
 264               : val
 265               | val relop val  */
 266
 267 bool
 268 is_gimple_condexpr (tree t)
 269 {
 270   return (is_gimple_val (t)
 271           || TREE_CODE_CLASS (TREE_CODE (t)) == '<');
 272 }
 273
 274
 275 /*  Return nonzero if T is a valid operand for '&':
 276
 277       varname
 278               : arrayref
 279               | compref
 280               | ID     */
 281
 282 bool
 283 is_gimple_addr_expr_arg (tree t)
 284 {
 285   return (is_gimple_id (t)
 286           || TREE_CODE (t) == ARRAY_REF
 287           || TREE_CODE (t) == COMPONENT_REF
 288           || TREE_CODE (t) == REALPART_EXPR
 289           || TREE_CODE (t) == IMAGPART_EXPR);
 290 }
 291
 292 /* Return nonzero if T is function invariant.  Or rather a restricted
 293    form of function invariant.  */
 294
 295 bool
 296 is_gimple_min_invariant (tree t)
 297 {
 298   switch (TREE_CODE (t))
 299     {
 300     case ADDR_EXPR:
 301       return TREE_INVARIANT (t);
 302
 303     case INTEGER_CST:
 304     case REAL_CST:
 305     case STRING_CST:
 306     case COMPLEX_CST:
 307     case VECTOR_CST:
 308       return !TREE_OVERFLOW (t);
 309
 310     default:
 311       return false;
 312     }
 313 }
 314
 315 /* Return nonzero if T looks like a valid GIMPLE statement.  */
 316
 317 bool
 318 is_gimple_stmt (tree t)
 319 {
 320   enum tree_code code = TREE_CODE (t);
 321
 322   if (IS_EMPTY_STMT (t))
 323     return 1;
 324
 325   switch (code)
 326     {
 327     case BIND_EXPR:
 328     case COND_EXPR:
 329       /* These are only valid if they're void.  */
 330       return VOID_TYPE_P (TREE_TYPE (t));
 331
 332     case SWITCH_EXPR:
 333     case GOTO_EXPR:
 334     case RETURN_EXPR:
 335     case LABEL_EXPR:
 336     case CASE_LABEL_EXPR:
 337     case TRY_CATCH_EXPR:
 338     case TRY_FINALLY_EXPR:
 339     case EH_FILTER_EXPR:
 340     case CATCH_EXPR:
 341     case ASM_EXPR:
 342     case RESX_EXPR:
 343     case PHI_NODE:
 344     case STATEMENT_LIST:
 345       /* These are always void.  */
 346       return 1;
 347
 348     case VA_ARG_EXPR:
 349       /* FIXME this should be lowered.  */
 350       return 1;
 351
 352     case COMPOUND_EXPR:
 353       /* FIXME should we work harder to make COMPOUND_EXPRs void?  */
 354     case CALL_EXPR:
 355     case MODIFY_EXPR:
 356       /* These are valid regardless of their type.  */
 357       return 1;
 358
 359     default:
 360       return 0;
 361     }
 362 }
 363
 364 /* Return nonzero if T is a variable.  */
 365
 366 bool
 367 is_gimple_variable (tree t)
 368 {
 369   return (TREE_CODE (t) == VAR_DECL
 370           || TREE_CODE (t) == PARM_DECL
 371           || TREE_CODE (t) == RESULT_DECL
 372           || TREE_CODE (t) == SSA_NAME);
 373 }
 374
 375 /*  Return nonzero if T is a GIMPLE identifier (something with an address).  */
 376
 377 static inline bool
 378 is_gimple_id (tree t)
 379 {
 380   return (is_gimple_variable (t)
 381           || TREE_CODE (t) == FUNCTION_DECL
 382           || TREE_CODE (t) == LABEL_DECL
 383           /* Allow string constants, since they are addressable.  */
 384           || TREE_CODE (t) == STRING_CST);
 385 }
 386
 387 /* Return nonzero if TYPE is a suitable type for a scalar register
 388    variable.  */
 389
 390 bool
 391 is_gimple_reg_type (tree type)
 392 {
 393   return (!AGGREGATE_TYPE_P (type)
 394           && TREE_CODE (type) != COMPLEX_TYPE);
 395 }
 396
 397
 398 /* Return nonzero if T is a scalar register variable.  */
 399
 400 bool
 401 is_gimple_reg (tree t)
 402 {
 403   if (TREE_CODE (t) == SSA_NAME)
 404     t = SSA_NAME_VAR (t);
 405
 406   return (is_gimple_variable (t)
 407           && is_gimple_reg_type (TREE_TYPE (t))
 408           /* A volatile decl is not acceptable because we can't reuse it as
 409              needed.  We need to copy it into a temp first.  */
 410           && ! TREE_THIS_VOLATILE (t)
 411           && ! TREE_ADDRESSABLE (t)
 412           && ! needs_to_live_in_memory (t));
 413 }
 414
 415 /* Return nonzero if T is a GIMPLE variable whose address is not needed.  */
 416
 417 bool
 418 is_gimple_non_addressable (tree t)
 419 {
 420   if (TREE_CODE (t) == SSA_NAME)
 421     t = SSA_NAME_VAR (t);
 422
 423   return (is_gimple_variable (t)
 424           && ! TREE_ADDRESSABLE (t)
 425           && ! needs_to_live_in_memory (t));
 426 }
 427
 428 /*  Return nonzero if T is a GIMPLE rvalue, i.e. an identifier or a
 429     constant.  */
 430
 431 bool
 432 is_gimple_val (tree t)
 433 {
 434   /* Make loads from volatiles and memory vars explicit.  */
 435   if (is_gimple_variable (t)
 436       && is_gimple_reg_type (TREE_TYPE (t))
 437       && !is_gimple_reg (t))
 438     return 0;
 439
 440   /* FIXME make these decls.  That can happen only when we expose the
 441      entire landing-pad construct at the tree level.  */
 442   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 443     return 1;
 444
 445   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 446 }
 447
 448
 449 /*  Return true if T is a GIMPLE minimal lvalue, of the form
 450
 451     min_lval: ID | '(' '*' ID ')'
 452
 453     This never actually appears in the original SIMPLE grammar, but is
 454     repeated in several places.  */
 455
 456 bool
 457 is_gimple_min_lval (tree t)
 458 {
 459   return (is_gimple_id (t)
 460           || TREE_CODE (t) == INDIRECT_REF);
 461 }
 462
 463 /*  Return nonzero if T is a typecast operation of the form
 464     '(' cast ')' val.  */
 465
 466 bool
 467 is_gimple_cast (tree t)
 468 {
 469   return (TREE_CODE (t) == NOP_EXPR
 470           || TREE_CODE (t) == CONVERT_EXPR
 471           || TREE_CODE (t) == FIX_TRUNC_EXPR
 472           || TREE_CODE (t) == FIX_CEIL_EXPR
 473           || TREE_CODE (t) == FIX_FLOOR_EXPR
 474           || TREE_CODE (t) == FIX_ROUND_EXPR);
 475 }
 476
 477
 478 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 479    Otherwise, return NULL_TREE.  */
 480
 481 tree
 482 get_call_expr_in (tree t)
 483 {
 484   if (TREE_CODE (t) == CALL_EXPR)
 485     return t;
 486   else if (TREE_CODE (t) == MODIFY_EXPR
 487            && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR)
 488     return TREE_OPERAND (t, 1);
 489   else if (TREE_CODE (t) == RETURN_EXPR
 490            && TREE_OPERAND (t, 0)
 491            && TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
 492            && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == CALL_EXPR)
 493     return TREE_OPERAND (TREE_OPERAND (t, 0), 1);
 494
 495   return NULL_TREE;
 496 }
 497
 498
 499 /* Given an _EXPR TOP, reorganize all of the nested _EXPRs with the same
 500    code so that they only appear as the second operand.  This should only
 501    be used for tree codes which are truly associative, such as
 502    COMPOUND_EXPR and TRUTH_ANDIF_EXPR.  Arithmetic is not associative
 503    enough, due to the limited precision of arithmetic data types.
 504
 505    This transformation is conservative; the operand 0 of a matching tree
 506    node will only change if it is also a matching node.  */
 507
 508 tree
 509 right_assocify_expr (tree top)
 510 {
 511   tree *p = &top;
 512   enum tree_code code = TREE_CODE (*p);
 513   while (TREE_CODE (*p) == code)
 514     {
 515       tree cur = *p;
 516       tree lhs = TREE_OPERAND (cur, 0);
 517       if (TREE_CODE (lhs) == code)
 518         {
 519           /* There's a left-recursion.  If we have ((a, (b, c)), d), we
 520              want to rearrange to (a, (b, (c, d))).  */
 521           tree *q;
 522
 523           /* Replace cur with the lhs; move (a, *) up.  */
 524           *p = lhs;
 525
 526           if (code == COMPOUND_EXPR)
 527             {
 528               /* We need to give (b, c) the type of c; previously lhs had
 529                  the type of b.  */
 530               TREE_TYPE (lhs) = TREE_TYPE (cur);
 531               if (TREE_SIDE_EFFECTS (cur))
 532                 TREE_SIDE_EFFECTS (lhs) = 1;
 533             }
 534
 535           /* Walk through the op1 chain from there until we find something
 536              with a different code.  In this case, c.  */
 537           for (q = &TREE_OPERAND (lhs, 1); TREE_CODE (*q) == code;
 538                q = &TREE_OPERAND (*q, 1))
 539             TREE_TYPE (*q) = TREE_TYPE (cur);
 540
 541           /* Change (*, d) into (c, d).  */
 542           TREE_OPERAND (cur, 0) = *q;
 543
 544           /* And plug it in where c used to be.  */
 545           *q = cur;
 546         }
 547       else
 548         p = &TREE_OPERAND (cur, 1);
 549     }
 550   return top;
 551 }
 552
 553 /* Normalize the statement TOP.  If it is a COMPOUND_EXPR, reorganize it so
 554    that we can traverse it without recursion.  If it is null, replace it
 555    with a nop.  */
 556
 557 tree
 558 rationalize_compound_expr (tree top)
 559 {
 560   if (top == NULL_TREE)
 561     top = build_empty_stmt ();
 562   else if (TREE_CODE (top) == COMPOUND_EXPR)
 563     top = right_assocify_expr (top);
 564
 565   return top;
 566 }
 567
 568 /* Given a memory reference expression, return the base address.  Note that,
 569    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 570    expressions.  Therefore, given the reference PTR->FIELD, this function
 571    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 572
 573 tree
 574 get_base_address (tree t)
 575 {
 576   do
 577     {
 578       if (SSA_VAR_P (t)
 579           || TREE_CODE (t) == STRING_CST
 580           || TREE_CODE (t) == CONSTRUCTOR
 581           || TREE_CODE (t) == INDIRECT_REF)
 582         return t;
 583
 584       switch (TREE_CODE (t))
 585         {
 586         case ARRAY_REF:
 587         case COMPONENT_REF:
 588         case REALPART_EXPR:
 589         case IMAGPART_EXPR:
 590         case BIT_FIELD_REF:
 591           t = TREE_OPERAND (t, 0);
 592           break;
 593
 594         default:
 595           return NULL_TREE;
 596         }
 597     }
 598   while (t);
 599
 600   return t;
 601 }
 602
 603
 604 void
 605 recalculate_side_effects (tree t)
 606 {
 607   enum tree_code code = TREE_CODE (t);
 608   int fro = first_rtl_op (code);
 609   int i;
 610
 611   switch (TREE_CODE_CLASS (code))
 612     {
 613     case 'e':
 614       switch (code)
 615         {
 616         case INIT_EXPR:
 617         case MODIFY_EXPR:
 618         case VA_ARG_EXPR:
 619         case RTL_EXPR:
 620         case PREDECREMENT_EXPR:
 621         case PREINCREMENT_EXPR:
 622         case POSTDECREMENT_EXPR:
 623         case POSTINCREMENT_EXPR:
 624           /* All of these have side-effects, no matter what their
 625              operands are.  */
 626           return;
 627
 628         default:
 629           break;
 630         }
 631       /* Fall through.  */
 632
 633     case '<':  /* a comparison expression */
 634     case '1':  /* a unary arithmetic expression */
 635     case '2':  /* a binary arithmetic expression */
 636     case 'r':  /* a reference */
 637       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 638       for (i = 0; i < fro; ++i)
 639         {
 640           tree op = TREE_OPERAND (t, i);
 641           if (op && TREE_SIDE_EFFECTS (op))
 642             TREE_SIDE_EFFECTS (t) = 1;
 643         }
 644       break;
 645    }
 646 }