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