gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003, 2004 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 "tree-flow.h"
  31 #include "output.h"
  32 #include "rtl.h"
  33 #include "expr.h"
  34 #include "bitmap.h"
  35
  36 /* GCC GIMPLE structure
  37
  38    Inspired by the SIMPLE C grammar at
  39
  40         http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html
  41
  42    function     : FUNCTION_DECL
  43                         DECL_SAVED_TREE -> compound-stmt
  44
  45    compound-stmt: STATEMENT_LIST
  46                         members -> stmt
  47
  48    stmt         : block
  49                 | if-stmt
  50                 | switch-stmt
  51                 | goto-stmt
  52                 | return-stmt
  53                 | resx-stmt
  54                 | label-stmt
  55                 | try-stmt
  56                 | modify-stmt
  57                 | call-stmt
  58
  59    block        : BIND_EXPR
  60                         BIND_EXPR_VARS -> chain of DECLs
  61                         BIND_EXPR_BLOCK -> BLOCK
  62                         BIND_EXPR_BODY -> compound-stmt
  63
  64    if-stmt      : COND_EXPR
  65                         op0 -> condition
  66                         op1 -> compound-stmt
  67                         op2 -> compound-stmt
  68
  69    switch-stmt  : SWITCH_EXPR
  70                         op0 -> val
  71                         op1 -> NULL
  72                         op2 -> TREE_VEC of CASE_LABEL_EXPRs
  73                             The CASE_LABEL_EXPRs are sorted by CASE_LOW,
  74                             and default is last.
  75
  76    goto-stmt    : GOTO_EXPR
  77                         op0 -> LABEL_DECL | val
  78
  79    return-stmt  : RETURN_EXPR
  80                         op0 -> return-value
  81
  82    return-value : NULL
  83                 | RESULT_DECL
  84                 | MODIFY_EXPR
  85                         op0 -> RESULT_DECL
  86                         op1 -> lhs
  87
  88    resx-stmt    : RESX_EXPR
  89
  90    label-stmt   : LABEL_EXPR
  91                         op0 -> LABEL_DECL
  92
  93    try-stmt     : TRY_CATCH_EXPR
  94                         op0 -> compound-stmt
  95                         op1 -> handler
  96                 | TRY_FINALLY_EXPR
  97                         op0 -> compound-stmt
  98                         op1 -> compound-stmt
  99
 100    handler      : catch-seq
 101                 | EH_FILTER_EXPR
 102                 | compound-stmt
 103
 104    catch-seq    : STATEMENT_LIST
 105                         members -> CATCH_EXPR
 106
 107    modify-stmt  : MODIFY_EXPR
 108                         op0 -> lhs
 109                         op1 -> rhs
 110
 111    call-stmt    : CALL_EXPR
 112                         op0 -> val | OBJ_TYPE_REF
 113                         op1 -> call-arg-list
 114
 115    call-arg-list: TREE_LIST
 116                         members -> lhs
 117
 118    addr-expr-arg: ID
 119                 | compref
 120
 121    addressable  : addr-expr-arg
 122                 | indirectref
 123
 124    with-size-arg: addressable
 125                 | call-stmt
 126
 127    indirectref  : INDIRECT_REF
 128                         op0 -> val
 129
 130    lhs          : addressable
 131                 | bitfieldref
 132                 | WITH_SIZE_EXPR
 133                         op0 -> with-size-arg
 134                         op1 -> val
 135
 136    min-lval     : ID
 137                 | indirectref
 138
 139    bitfieldref  : BIT_FIELD_REF
 140                         op0 -> inner-compref
 141                         op1 -> CONST
 142                         op2 -> var
 143
 144    compref      : inner-compref
 145                 | REALPART_EXPR
 146                         op0 -> inner-compref
 147                 | IMAGPART_EXPR
 148                         op0 -> inner-compref
 149
 150    inner-compref: min-lval
 151                 | COMPONENT_REF
 152                         op0 -> inner-compref
 153                         op1 -> FIELD_DECL
 154                         op2 -> val
 155                 | ARRAY_REF
 156                         op0 -> inner-compref
 157                         op1 -> val
 158                         op2 -> val
 159                         op3 -> val
 160                 | ARRAY_RANGE_REF
 161                         op0 -> inner-compref
 162                         op1 -> val
 163                         op2 -> val
 164                         op3 -> val
 165                 | VIEW_CONVERT_EXPR
 166                         op0 -> inner-compref
 167
 168    condition    : val
 169                 | RELOP
 170                         op0 -> val
 171                         op1 -> val
 172
 173    val          : ID
 174                 | CONST
 175
 176    rhs          : lhs
 177                 | CONST
 178                 | call-stmt
 179                 | ADDR_EXPR
 180                         op0 -> addr-expr-arg
 181                 | UNOP
 182                         op0 -> val
 183                 | BINOP
 184                         op0 -> val
 185                         op1 -> val
 186                 | RELOP
 187                         op0 -> val
 188                         op1 -> val
 189 */
 190
 191 static inline bool is_gimple_id (tree);
 192
 193 /* Validation of GIMPLE expressions.  */
 194
 195 /* Return true if T is a GIMPLE RHS for an assignment to a temporary.  */
 196
 197 bool
 198 is_gimple_formal_tmp_rhs (tree t)
 199 {
 200   enum tree_code code = TREE_CODE (t);
 201
 202   switch (TREE_CODE_CLASS (code))
 203     {
 204     case tcc_unary:
 205     case tcc_binary:
 206     case tcc_comparison:
 207       return true;
 208
 209     default:
 210       break;
 211     }
 212
 213   switch (code)
 214     {
 215     case TRUTH_NOT_EXPR:
 216     case TRUTH_AND_EXPR:
 217     case TRUTH_OR_EXPR:
 218     case TRUTH_XOR_EXPR:
 219     case ADDR_EXPR:
 220     case CALL_EXPR:
 221     case CONSTRUCTOR:
 222     case COMPLEX_EXPR:
 223     case INTEGER_CST:
 224     case REAL_CST:
 225     case STRING_CST:
 226     case COMPLEX_CST:
 227     case VECTOR_CST:
 228     case OBJ_TYPE_REF:
 229       return true;
 230
 231     default:
 232       break;
 233     }
 234
 235   return is_gimple_lvalue (t) || is_gimple_val (t);
 236 }
 237
 238 /* Returns true iff T is a valid RHS for an assignment to a renamed
 239    user -- or front-end generated artificial -- variable.  */
 240
 241 bool
 242 is_gimple_reg_rhs (tree t)
 243 {
 244   /* If the RHS of the MODIFY_EXPR may throw or make a nonlocal goto
 245      and the LHS is a user variable, then we need to introduce a formal
 246      temporary.  This way the optimizers can determine that the user
 247      variable is only modified if evaluation of the RHS does not throw.
 248
 249      Don't force a temp of a non-renamable type; the copy could be
 250      arbitrarily expensive.  Instead we will generate a V_MAY_DEF for
 251      the assignment.  */
 252
 253   if (is_gimple_reg_type (TREE_TYPE (t))
 254       && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t))
 255           || tree_could_throw_p (t)))
 256     return false;
 257
 258   return is_gimple_formal_tmp_rhs (t);
 259 }
 260
 261 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 262    LHS, or for a call argument.  */
 263
 264 bool
 265 is_gimple_mem_rhs (tree t)
 266 {
 267   /* If we're dealing with a renamable type, either source or dest
 268      must be a renamed variable.  */
 269   if (is_gimple_reg_type (TREE_TYPE (t)))
 270     return is_gimple_val (t);
 271   else
 272     return is_gimple_formal_tmp_rhs (t);
 273 }
 274
 275 /* Returns the appropriate RHS predicate for this LHS.  */
 276
 277 gimple_predicate
 278 rhs_predicate_for (tree lhs)
 279 {
 280   if (is_gimple_formal_tmp_var (lhs))
 281     return is_gimple_formal_tmp_rhs;
 282   else if (is_gimple_reg (lhs))
 283     return is_gimple_reg_rhs;
 284   else
 285     return is_gimple_mem_rhs;
 286 }
 287
 288 /* Returns true if T is a valid CONSTRUCTOR component in GIMPLE, either
 289    a val or another CONSTRUCTOR.  */
 290
 291 bool
 292 is_gimple_constructor_elt (tree t)
 293 {
 294   return (is_gimple_val (t)
 295           || TREE_CODE (t) == CONSTRUCTOR);
 296 }
 297
 298 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 299
 300 bool
 301 is_gimple_lvalue (tree t)
 302 {
 303   return (is_gimple_addressable (t)
 304           || TREE_CODE (t) == WITH_SIZE_EXPR
 305           /* These are complex lvalues, but don't have addresses, so they
 306              go here.  */
 307           || TREE_CODE (t) == BIT_FIELD_REF);
 308 }
 309
 310 /*  Return true if T is a GIMPLE condition.  */
 311
 312 bool
 313 is_gimple_condexpr (tree t)
 314 {
 315   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 316 }
 317
 318 /*  Return true if T is something whose address can be taken.  */
 319
 320 bool
 321 is_gimple_addressable (tree t)
 322 {
 323   return (is_gimple_id (t) || handled_component_p (t)
 324           || TREE_CODE (t) == REALPART_EXPR
 325           || TREE_CODE (t) == IMAGPART_EXPR
 326           || TREE_CODE (t) == INDIRECT_REF);
 327 }
 328
 329 /* Return true if T is function invariant.  Or rather a restricted
 330    form of function invariant.  */
 331
 332 bool
 333 is_gimple_min_invariant (tree t)
 334 {
 335   switch (TREE_CODE (t))
 336     {
 337     case ADDR_EXPR:
 338       return TREE_INVARIANT (t);
 339
 340     case INTEGER_CST:
 341     case REAL_CST:
 342     case STRING_CST:
 343     case COMPLEX_CST:
 344     case VECTOR_CST:
 345       return !TREE_OVERFLOW (t);
 346
 347     default:
 348       return false;
 349     }
 350 }
 351
 352 /* Return true if T looks like a valid GIMPLE statement.  */
 353
 354 bool
 355 is_gimple_stmt (tree t)
 356 {
 357   enum tree_code code = TREE_CODE (t);
 358
 359   if (IS_EMPTY_STMT (t))
 360     return 1;
 361
 362   switch (code)
 363     {
 364     case BIND_EXPR:
 365     case COND_EXPR:
 366       /* These are only valid if they're void.  */
 367       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 368
 369     case SWITCH_EXPR:
 370     case GOTO_EXPR:
 371     case RETURN_EXPR:
 372     case LABEL_EXPR:
 373     case CASE_LABEL_EXPR:
 374     case TRY_CATCH_EXPR:
 375     case TRY_FINALLY_EXPR:
 376     case EH_FILTER_EXPR:
 377     case CATCH_EXPR:
 378     case ASM_EXPR:
 379     case RESX_EXPR:
 380     case PHI_NODE:
 381     case STATEMENT_LIST:
 382       /* These are always void.  */
 383       return true;
 384
 385     case CALL_EXPR:
 386     case MODIFY_EXPR:
 387       /* These are valid regardless of their type.  */
 388       return true;
 389
 390     default:
 391       return false;
 392     }
 393 }
 394
 395 /* Return true if T is a variable.  */
 396
 397 bool
 398 is_gimple_variable (tree t)
 399 {
 400   return (TREE_CODE (t) == VAR_DECL
 401           || TREE_CODE (t) == PARM_DECL
 402           || TREE_CODE (t) == RESULT_DECL
 403           || TREE_CODE (t) == SSA_NAME);
 404 }
 405
 406 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 407
 408 static inline bool
 409 is_gimple_id (tree t)
 410 {
 411   return (is_gimple_variable (t)
 412           || TREE_CODE (t) == FUNCTION_DECL
 413           || TREE_CODE (t) == LABEL_DECL
 414           || TREE_CODE (t) == CONST_DECL
 415           /* Allow string constants, since they are addressable.  */
 416           || TREE_CODE (t) == STRING_CST);
 417 }
 418
 419 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 420
 421 bool
 422 is_gimple_reg_type (tree type)
 423 {
 424   return (!AGGREGATE_TYPE_P (type)
 425           && TREE_CODE (type) != COMPLEX_TYPE);
 426 }
 427
 428
 429 /* Return true if T is a scalar register variable.  */
 430
 431 bool
 432 is_gimple_reg (tree t)
 433 {
 434   if (TREE_CODE (t) == SSA_NAME)
 435     t = SSA_NAME_VAR (t);
 436
 437   return (is_gimple_variable (t)
 438           && is_gimple_reg_type (TREE_TYPE (t))
 439           /* A volatile decl is not acceptable because we can't reuse it as
 440              needed.  We need to copy it into a temp first.  */
 441           && ! TREE_THIS_VOLATILE (t)
 442           && ! needs_to_live_in_memory (t));
 443 }
 444
 445 /* Returns true if T is a GIMPLE formal temporary variable.  */
 446
 447 bool
 448 is_gimple_formal_tmp_var (tree t)
 449 {
 450   if (TREE_CODE (t) == SSA_NAME)
 451     return true;
 452
 453   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 454 }
 455
 456 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 457
 458 bool
 459 is_gimple_formal_tmp_reg (tree t)
 460 {
 461   /* The intent of this is to get hold of a value that won't change.
 462      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 463   if (TREE_CODE (t) == SSA_NAME)
 464     return true;
 465
 466   /* We don't know the lifetime characteristics of user variables.  */
 467   if (!is_gimple_formal_tmp_var (t))
 468     return false;
 469
 470   /* Finally, it must be capable of being placed in a register.  */
 471   return is_gimple_reg (t);
 472 }
 473
 474 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 475
 476 bool
 477 is_gimple_non_addressable (tree t)
 478 {
 479   if (TREE_CODE (t) == SSA_NAME)
 480     t = SSA_NAME_VAR (t);
 481
 482   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 483 }
 484
 485 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 486
 487 bool
 488 is_gimple_val (tree t)
 489 {
 490   /* Make loads from volatiles and memory vars explicit.  */
 491   if (is_gimple_variable (t)
 492       && is_gimple_reg_type (TREE_TYPE (t))
 493       && !is_gimple_reg (t))
 494     return false;
 495
 496   /* FIXME make these decls.  That can happen only when we expose the
 497      entire landing-pad construct at the tree level.  */
 498   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 499     return 1;
 500
 501   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 502 }
 503
 504
 505 /* Return true if T is a GIMPLE minimal lvalue.  */
 506
 507 bool
 508 is_gimple_min_lval (tree t)
 509 {
 510   return (is_gimple_id (t)
 511           || TREE_CODE (t) == INDIRECT_REF);
 512 }
 513
 514 /* Return true if T is a typecast operation.  */
 515
 516 bool
 517 is_gimple_cast (tree t)
 518 {
 519   return (TREE_CODE (t) == NOP_EXPR
 520           || TREE_CODE (t) == CONVERT_EXPR
 521           || TREE_CODE (t) == FIX_TRUNC_EXPR
 522           || TREE_CODE (t) == FIX_CEIL_EXPR
 523           || TREE_CODE (t) == FIX_FLOOR_EXPR
 524           || TREE_CODE (t) == FIX_ROUND_EXPR);
 525 }
 526
 527 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 528
 529 bool
 530 is_gimple_call_addr (tree t)
 531 {
 532   return (TREE_CODE (t) == OBJ_TYPE_REF
 533           || is_gimple_val (t));
 534 }
 535
 536 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 537    Otherwise, return NULL_TREE.  */
 538
 539 tree
 540 get_call_expr_in (tree t)
 541 {
 542   if (TREE_CODE (t) == MODIFY_EXPR)
 543     t = TREE_OPERAND (t, 1);
 544   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 545     t = TREE_OPERAND (t, 0);
 546   if (TREE_CODE (t) == CALL_EXPR)
 547     return t;
 548   return NULL_TREE;
 549 }
 550
 551 /* Given a memory reference expression, return the base address.  Note that,
 552    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 553    expressions.  Therefore, given the reference PTR->FIELD, this function
 554    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 555
 556 tree
 557 get_base_address (tree t)
 558 {
 559   while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
 560          || handled_component_p (t))
 561     t = TREE_OPERAND (t, 0);
 562
 563   if (SSA_VAR_P (t)
 564       || TREE_CODE (t) == STRING_CST
 565       || TREE_CODE (t) == CONSTRUCTOR
 566       || TREE_CODE (t) == INDIRECT_REF)
 567     return t;
 568   else
 569     return NULL_TREE;
 570 }
 571
 572 void
 573 recalculate_side_effects (tree t)
 574 {
 575   enum tree_code code = TREE_CODE (t);
 576   int fro = first_rtl_op (code);
 577   int i;
 578
 579   switch (TREE_CODE_CLASS (code))
 580     {
 581     case tcc_expression:
 582       switch (code)
 583         {
 584         case INIT_EXPR:
 585         case MODIFY_EXPR:
 586         case VA_ARG_EXPR:
 587         case PREDECREMENT_EXPR:
 588         case PREINCREMENT_EXPR:
 589         case POSTDECREMENT_EXPR:
 590         case POSTINCREMENT_EXPR:
 591           /* All of these have side-effects, no matter what their
 592              operands are.  */
 593           return;
 594
 595         default:
 596           break;
 597         }
 598       /* Fall through.  */
 599
 600     case tcc_comparison:  /* a comparison expression */
 601     case tcc_unary:       /* a unary arithmetic expression */
 602     case tcc_binary:      /* a binary arithmetic expression */
 603     case tcc_reference:   /* a reference */
 604       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 605       for (i = 0; i < fro; ++i)
 606         {
 607           tree op = TREE_OPERAND (t, i);
 608           if (op && TREE_SIDE_EFFECTS (op))
 609             TREE_SIDE_EFFECTS (t) = 1;
 610         }
 611       break;
 612
 613     default:
 614       /* Can never be used with non-expressions.  */
 615       gcc_unreachable ();
 616    }
 617 }