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 -> NULL_TREE
  83               | RESULT_DECL
  84               | MODIFY_EXPR -> RESULT_DECL, varname
  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 | OBJ_TYPE_REF
 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 -> inner_compref
 123        op1 -> CONST
 124        op2 -> var
 125    compref :
 126      COMPONENT_REF
 127        op0 -> inner_compref
 128      | ARRAY_REF
 129        op0 -> inner_compref
 130        op1 -> val
 131        op2 -> val
 132        op3 -> val
 133      | ARRAY_RANGE_REF
 134        op0 -> inner_compref
 135        op1 -> val
 136        op2 -> val
 137        op3 -> val
 138      | REALPART_EXPR
 139        op0 -> inner_compref
 140      | IMAGPART_EXPR
 141        op0 -> inner_compref
 142
 143    inner_compref : compref | min_lval
 144      | VIEW_CONVERT_EXPR
 145        op0 -> inner_compref
 146      | NOP_EXPR
 147        op0 -> inner_compref
 148      | CONVERT_EXPR
 149        op0 -> inner_compref
 150
 151    condition : val | val relop val
 152    val : ID | CONST
 153
 154    rhs        : varname | CONST
 155               | '*' ID
 156               | '&' addr-expr-arg
 157               | call_expr
 158               | unop val
 159               | val binop val
 160               | '(' cast ')' val
 161               | method_ref
 162
 163               (cast here stands for all valid C typecasts)
 164
 165       unop
 166               : '+'
 167               | '-'
 168               | '!'
 169               | '~'
 170
 171       binop
 172               : relop | '-'
 173               | '+'
 174               | '/'
 175               | '*'
 176               | '%'
 177               | '&'
 178               | '|'
 179               | '<<'
 180               | '>>'
 181               | '^'
 182
 183       relop
 184               : '<'
 185               | '<='
 186               | '>'
 187               | '>='
 188               | '=='
 189               | '!='
 190
 191 */
 192
 193 static inline bool is_gimple_id (tree);
 194
 195 /* Validation of GIMPLE expressions.  */
 196
 197 /* Return nonzero if T is a GIMPLE RHS:
 198
 199       rhs     : varname | CONST
 200               | '*' ID
 201               | '&' varname_or_temp
 202               | call_expr
 203               | unop val
 204               | val binop val
 205               | '(' cast ')' val
 206               | <CONSTRUCTOR <gimple_val ...>>
 207
 208    The last option is only valid GIMPLE for vector and complex types;
 209    aggregate types should have their constructors decomposed.  */
 210
 211 bool
 212 is_gimple_rhs (tree t)
 213 {
 214   enum tree_code code = TREE_CODE (t);
 215
 216   switch (TREE_CODE_CLASS (code))
 217     {
 218     case '1':
 219     case '2':
 220     case '<':
 221       return 1;
 222
 223     default:
 224       break;
 225     }
 226
 227   switch (code)
 228     {
 229     case TRUTH_NOT_EXPR:
 230     case TRUTH_AND_EXPR:
 231     case TRUTH_OR_EXPR:
 232     case TRUTH_XOR_EXPR:
 233     case ADDR_EXPR:
 234     case CALL_EXPR:
 235     case CONSTRUCTOR:
 236     case COMPLEX_EXPR:
 237       /* FIXME lower VA_ARG_EXPR.  */
 238     case VA_ARG_EXPR:
 239     case INTEGER_CST:
 240     case REAL_CST:
 241     case STRING_CST:
 242     case COMPLEX_CST:
 243     case VECTOR_CST:
 244     case OBJ_TYPE_REF:
 245       return 1;
 246
 247     default:
 248       break;
 249     }
 250
 251   if (is_gimple_lvalue (t) || is_gimple_val (t))
 252     return 1;
 253
 254   return 0;
 255 }
 256
 257 /* Returns nonzero if T is a valid CONSTRUCTOR component in GIMPLE, either
 258    a val or another CONSTRUCTOR.  */
 259
 260 bool
 261 is_gimple_constructor_elt (tree t)
 262 {
 263   return (is_gimple_val (t)
 264           || TREE_CODE (t) == CONSTRUCTOR);
 265 }
 266
 267 /*  Return nonzero if T is a valid LHS for a GIMPLE assignment expression.  */
 268
 269 bool
 270 is_gimple_lvalue (tree t)
 271 {
 272   return (is_gimple_addr_expr_arg (t)
 273           || TREE_CODE (t) == INDIRECT_REF
 274           /* These are complex lvalues, but don't have addresses, so they
 275              go here.  */
 276           || TREE_CODE (t) == BIT_FIELD_REF);
 277 }
 278
 279
 280 /*  Return nonzero if T is a GIMPLE condition:
 281
 282       condexpr
 283               : val
 284               | val relop val  */
 285
 286 bool
 287 is_gimple_condexpr (tree t)
 288 {
 289   return (is_gimple_val (t)
 290           || TREE_CODE_CLASS (TREE_CODE (t)) == '<');
 291 }
 292
 293
 294 /*  Return nonzero if T is a valid operand for '&':
 295
 296       varname
 297               : arrayref
 298               | compref
 299               | ID     */
 300
 301 bool
 302 is_gimple_addr_expr_arg (tree t)
 303 {
 304   return (is_gimple_id (t)
 305           || TREE_CODE (t) == ARRAY_REF
 306           || TREE_CODE (t) == ARRAY_RANGE_REF
 307           || TREE_CODE (t) == COMPONENT_REF
 308           || TREE_CODE (t) == REALPART_EXPR
 309           || TREE_CODE (t) == IMAGPART_EXPR
 310           || TREE_CODE (t) == INDIRECT_REF);
 311 }
 312
 313 /* Return nonzero if T is function invariant.  Or rather a restricted
 314    form of function invariant.  */
 315
 316 bool
 317 is_gimple_min_invariant (tree t)
 318 {
 319   switch (TREE_CODE (t))
 320     {
 321     case ADDR_EXPR:
 322       return TREE_INVARIANT (t);
 323
 324     case INTEGER_CST:
 325     case REAL_CST:
 326     case STRING_CST:
 327     case COMPLEX_CST:
 328     case VECTOR_CST:
 329       return !TREE_OVERFLOW (t);
 330
 331     default:
 332       return false;
 333     }
 334 }
 335
 336 /* Return nonzero if T looks like a valid GIMPLE statement.  */
 337
 338 bool
 339 is_gimple_stmt (tree t)
 340 {
 341   enum tree_code code = TREE_CODE (t);
 342
 343   if (IS_EMPTY_STMT (t))
 344     return 1;
 345
 346   switch (code)
 347     {
 348     case BIND_EXPR:
 349     case COND_EXPR:
 350       /* These are only valid if they're void.  */
 351       return VOID_TYPE_P (TREE_TYPE (t));
 352
 353     case SWITCH_EXPR:
 354     case GOTO_EXPR:
 355     case RETURN_EXPR:
 356     case LABEL_EXPR:
 357     case CASE_LABEL_EXPR:
 358     case TRY_CATCH_EXPR:
 359     case TRY_FINALLY_EXPR:
 360     case EH_FILTER_EXPR:
 361     case CATCH_EXPR:
 362     case ASM_EXPR:
 363     case RESX_EXPR:
 364     case PHI_NODE:
 365     case STATEMENT_LIST:
 366       /* These are always void.  */
 367       return 1;
 368
 369     case VA_ARG_EXPR:
 370       /* FIXME this should be lowered.  */
 371       return 1;
 372
 373     case COMPOUND_EXPR:
 374       /* FIXME should we work harder to make COMPOUND_EXPRs void?  */
 375     case CALL_EXPR:
 376     case MODIFY_EXPR:
 377       /* These are valid regardless of their type.  */
 378       return 1;
 379
 380     default:
 381       return 0;
 382     }
 383 }
 384
 385 /* Return nonzero if T is a variable.  */
 386
 387 bool
 388 is_gimple_variable (tree t)
 389 {
 390   return (TREE_CODE (t) == VAR_DECL
 391           || TREE_CODE (t) == PARM_DECL
 392           || TREE_CODE (t) == RESULT_DECL
 393           || TREE_CODE (t) == SSA_NAME);
 394 }
 395
 396 /*  Return nonzero if T is a GIMPLE identifier (something with an address).  */
 397
 398 static inline bool
 399 is_gimple_id (tree t)
 400 {
 401   return (is_gimple_variable (t)
 402           || TREE_CODE (t) == FUNCTION_DECL
 403           || TREE_CODE (t) == LABEL_DECL
 404           /* Allow string constants, since they are addressable.  */
 405           || TREE_CODE (t) == STRING_CST);
 406 }
 407
 408 /* Return nonzero if TYPE is a suitable type for a scalar register
 409    variable.  */
 410
 411 bool
 412 is_gimple_reg_type (tree type)
 413 {
 414   return (!AGGREGATE_TYPE_P (type)
 415           && TREE_CODE (type) != COMPLEX_TYPE);
 416 }
 417
 418
 419 /* Return nonzero if T is a scalar register variable.  */
 420
 421 bool
 422 is_gimple_reg (tree t)
 423 {
 424   if (TREE_CODE (t) == SSA_NAME)
 425     t = SSA_NAME_VAR (t);
 426
 427   return (is_gimple_variable (t)
 428           && is_gimple_reg_type (TREE_TYPE (t))
 429           /* A volatile decl is not acceptable because we can't reuse it as
 430              needed.  We need to copy it into a temp first.  */
 431           && ! TREE_THIS_VOLATILE (t)
 432           && ! TREE_ADDRESSABLE (t)
 433           && ! needs_to_live_in_memory (t));
 434 }
 435
 436 /* Return nonzero if T is a GIMPLE variable whose address is not needed.  */
 437
 438 bool
 439 is_gimple_non_addressable (tree t)
 440 {
 441   if (TREE_CODE (t) == SSA_NAME)
 442     t = SSA_NAME_VAR (t);
 443
 444   return (is_gimple_variable (t)
 445           && ! TREE_ADDRESSABLE (t)
 446           && ! needs_to_live_in_memory (t));
 447 }
 448
 449 /*  Return nonzero if T is a GIMPLE rvalue, i.e. an identifier or a
 450     constant.  */
 451
 452 bool
 453 is_gimple_val (tree t)
 454 {
 455   /* Make loads from volatiles and memory vars explicit.  */
 456   if (is_gimple_variable (t)
 457       && is_gimple_reg_type (TREE_TYPE (t))
 458       && !is_gimple_reg (t))
 459     return 0;
 460
 461   /* FIXME make these decls.  That can happen only when we expose the
 462      entire landing-pad construct at the tree level.  */
 463   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 464     return 1;
 465
 466   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 467 }
 468
 469
 470 /*  Return true if T is a GIMPLE minimal lvalue, of the form
 471
 472     min_lval: ID | '(' '*' ID ')'
 473
 474     This never actually appears in the original SIMPLE grammar, but is
 475     repeated in several places.  */
 476
 477 bool
 478 is_gimple_min_lval (tree t)
 479 {
 480   return (is_gimple_id (t)
 481           || TREE_CODE (t) == INDIRECT_REF);
 482 }
 483
 484 /*  Return nonzero if T is a typecast operation of the form
 485     '(' cast ')' val.  */
 486
 487 bool
 488 is_gimple_cast (tree t)
 489 {
 490   return (TREE_CODE (t) == NOP_EXPR
 491           || TREE_CODE (t) == CONVERT_EXPR
 492           || TREE_CODE (t) == FIX_TRUNC_EXPR
 493           || TREE_CODE (t) == FIX_CEIL_EXPR
 494           || TREE_CODE (t) == FIX_FLOOR_EXPR
 495           || TREE_CODE (t) == FIX_ROUND_EXPR);
 496 }
 497
 498 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 499
 500 bool
 501 is_gimple_call_addr (tree t)
 502 {
 503   return (TREE_CODE (t) == OBJ_TYPE_REF
 504           || is_gimple_val (t));
 505 }
 506
 507 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 508    Otherwise, return NULL_TREE.  */
 509
 510 tree
 511 get_call_expr_in (tree t)
 512 {
 513   if (TREE_CODE (t) == CALL_EXPR)
 514     return t;
 515   else if (TREE_CODE (t) == MODIFY_EXPR
 516            && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR)
 517     return TREE_OPERAND (t, 1);
 518   else if (TREE_CODE (t) == RETURN_EXPR
 519            && TREE_OPERAND (t, 0)
 520            && TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
 521            && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == CALL_EXPR)
 522     return TREE_OPERAND (TREE_OPERAND (t, 0), 1);
 523
 524   return NULL_TREE;
 525 }
 526
 527
 528 /* Given an _EXPR TOP, reorganize all of the nested _EXPRs with the same
 529    code so that they only appear as the second operand.  This should only
 530    be used for tree codes which are truly associative, such as
 531    COMPOUND_EXPR and TRUTH_ANDIF_EXPR.  Arithmetic is not associative
 532    enough, due to the limited precision of arithmetic data types.
 533
 534    This transformation is conservative; the operand 0 of a matching tree
 535    node will only change if it is also a matching node.  */
 536
 537 tree
 538 right_assocify_expr (tree top)
 539 {
 540   tree *p = &top;
 541   enum tree_code code = TREE_CODE (*p);
 542   while (TREE_CODE (*p) == code)
 543     {
 544       tree cur = *p;
 545       tree lhs = TREE_OPERAND (cur, 0);
 546       if (TREE_CODE (lhs) == code)
 547         {
 548           /* There's a left-recursion.  If we have ((a, (b, c)), d), we
 549              want to rearrange to (a, (b, (c, d))).  */
 550           tree *q;
 551
 552           /* Replace cur with the lhs; move (a, *) up.  */
 553           *p = lhs;
 554
 555           if (code == COMPOUND_EXPR)
 556             {
 557               /* We need to give (b, c) the type of c; previously lhs had
 558                  the type of b.  */
 559               TREE_TYPE (lhs) = TREE_TYPE (cur);
 560               if (TREE_SIDE_EFFECTS (cur))
 561                 TREE_SIDE_EFFECTS (lhs) = 1;
 562             }
 563
 564           /* Walk through the op1 chain from there until we find something
 565              with a different code.  In this case, c.  */
 566           for (q = &TREE_OPERAND (lhs, 1); TREE_CODE (*q) == code;
 567                q = &TREE_OPERAND (*q, 1))
 568             TREE_TYPE (*q) = TREE_TYPE (cur);
 569
 570           /* Change (*, d) into (c, d).  */
 571           TREE_OPERAND (cur, 0) = *q;
 572
 573           /* And plug it in where c used to be.  */
 574           *q = cur;
 575         }
 576       else
 577         p = &TREE_OPERAND (cur, 1);
 578     }
 579   return top;
 580 }
 581
 582 /* Normalize the statement TOP.  If it is a COMPOUND_EXPR, reorganize it so
 583    that we can traverse it without recursion.  If it is null, replace it
 584    with a nop.  */
 585
 586 tree
 587 rationalize_compound_expr (tree top)
 588 {
 589   if (top == NULL_TREE)
 590     top = build_empty_stmt ();
 591   else if (TREE_CODE (top) == COMPOUND_EXPR)
 592     top = right_assocify_expr (top);
 593
 594   return top;
 595 }
 596
 597 /* Given a memory reference expression, return the base address.  Note that,
 598    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 599    expressions.  Therefore, given the reference PTR->FIELD, this function
 600    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 601
 602 tree
 603 get_base_address (tree t)
 604 {
 605   do
 606     {
 607       if (SSA_VAR_P (t)
 608           || TREE_CODE (t) == STRING_CST
 609           || TREE_CODE (t) == CONSTRUCTOR
 610           || TREE_CODE (t) == INDIRECT_REF)
 611         return t;
 612
 613       if (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR)
 614         t = TREE_OPERAND (t, 0);
 615       else if (handled_component_p (t))
 616         t = get_base_address (TREE_OPERAND (t, 0));
 617       else
 618         return NULL_TREE;
 619     }
 620   while (t);
 621
 622   return t;
 623 }
 624
 625
 626 void
 627 recalculate_side_effects (tree t)
 628 {
 629   enum tree_code code = TREE_CODE (t);
 630   int fro = first_rtl_op (code);
 631   int i;
 632
 633   switch (TREE_CODE_CLASS (code))
 634     {
 635     case 'e':
 636       switch (code)
 637         {
 638         case INIT_EXPR:
 639         case MODIFY_EXPR:
 640         case VA_ARG_EXPR:
 641         case RTL_EXPR:
 642         case PREDECREMENT_EXPR:
 643         case PREINCREMENT_EXPR:
 644         case POSTDECREMENT_EXPR:
 645         case POSTINCREMENT_EXPR:
 646           /* All of these have side-effects, no matter what their
 647              operands are.  */
 648           return;
 649
 650         default:
 651           break;
 652         }
 653       /* Fall through.  */
 654
 655     case '<':  /* a comparison expression */
 656     case '1':  /* a unary arithmetic expression */
 657     case '2':  /* a binary arithmetic expression */
 658     case 'r':  /* a reference */
 659       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 660       for (i = 0; i < fro; ++i)
 661         {
 662           tree op = TREE_OPERAND (t, i);
 663           if (op && TREE_SIDE_EFFECTS (op))
 664             TREE_SIDE_EFFECTS (t) = 1;
 665         }
 666       break;
 667    }
 668 }