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    with-size-arg: addr-expr-arg
 122                 | indirectref
 123                 | call-stmt
 124
 125    indirectref  : INDIRECT_REF
 126                         op0 -> val
 127
 128    lhs          : addr-expr-arg
 129                 | bitfieldref
 130                 | indirectref
 131                 | WITH_SIZE_EXPR
 132                         op0 -> with-size-arg
 133                         op1 -> val
 134
 135    min-lval     : ID
 136                 | indirectref
 137
 138    bitfieldref  : BIT_FIELD_REF
 139                         op0 -> inner-compref
 140                         op1 -> CONST
 141                         op2 -> var
 142
 143    compref      : inner-compref
 144                 | REALPART_EXPR
 145                         op0 -> inner-compref
 146                 | IMAGPART_EXPR
 147                         op0 -> inner-compref
 148
 149    inner-compref: min-lval
 150                 | COMPONENT_REF
 151                         op0 -> inner-compref
 152                         op1 -> FIELD_DECL
 153                         op2 -> val
 154                 | ARRAY_REF
 155                         op0 -> inner-compref
 156                         op1 -> val
 157                         op2 -> val
 158                         op3 -> val
 159                 | ARRAY_RANGE_REF
 160                         op0 -> inner-compref
 161                         op1 -> val
 162                         op2 -> val
 163                         op3 -> val
 164                 | VIEW_CONVERT_EXPR
 165                         op0 -> inner-compref
 166
 167    condition    : val
 168                 | RELOP
 169                         op0 -> val
 170                         op1 -> val
 171
 172    val          : ID
 173                 | CONST
 174
 175    rhs          : lhs
 176                 | CONST
 177                 | call-stmt
 178                 | ADDR_EXPR
 179                         op0 -> addr-expr-arg
 180                 | UNOP
 181                         op0 -> val
 182                 | BINOP
 183                         op0 -> val
 184                         op1 -> val
 185                 | RELOP
 186                         op0 -> val
 187                         op1 -> val
 188 */
 189
 190 static inline bool is_gimple_id (tree);
 191
 192 /* Validation of GIMPLE expressions.  */
 193
 194 /* Return true if T is a GIMPLE RHS for an assignment to a temporary.  */
 195
 196 bool
 197 is_gimple_tmp_rhs (tree t)
 198 {
 199   enum tree_code code = TREE_CODE (t);
 200
 201   switch (TREE_CODE_CLASS (code))
 202     {
 203     case '1':
 204     case '2':
 205     case '<':
 206       return true;
 207
 208     default:
 209       break;
 210     }
 211
 212   switch (code)
 213     {
 214     case TRUTH_NOT_EXPR:
 215     case TRUTH_AND_EXPR:
 216     case TRUTH_OR_EXPR:
 217     case TRUTH_XOR_EXPR:
 218     case ADDR_EXPR:
 219     case CALL_EXPR:
 220     case CONSTRUCTOR:
 221     case COMPLEX_EXPR:
 222       /* FIXME lower VA_ARG_EXPR.  */
 223     case VA_ARG_EXPR:
 224     case INTEGER_CST:
 225     case REAL_CST:
 226     case STRING_CST:
 227     case COMPLEX_CST:
 228     case VECTOR_CST:
 229     case OBJ_TYPE_REF:
 230       return true;
 231
 232     default:
 233       break;
 234     }
 235
 236   return is_gimple_lvalue (t) || is_gimple_val (t);
 237 }
 238
 239 /* Returns true iff T is a valid RHS for an assignment to a renamed user
 240    variable.  */
 241
 242 bool
 243 is_gimple_reg_rhs (tree t)
 244 {
 245   /* If the RHS of the MODIFY_EXPR may throw or make a nonlocal goto and
 246      the LHS is a user variable, then we need to introduce a temporary.
 247      ie temp = RHS; LHS = temp.
 248
 249      This way the optimizers can determine that the user variable is
 250      only modified if evaluation of the RHS does not throw.  */
 251   if (is_gimple_reg_type (TREE_TYPE (t))
 252       && TREE_SIDE_EFFECTS (t)
 253       && (TREE_CODE (t) == CALL_EXPR
 254           || (flag_non_call_exceptions && tree_could_trap_p (t))))
 255     return is_gimple_val (t);
 256   else
 257     /* Don't force a temp of a non-renamable type; the copy could be
 258        arbitrarily expensive.  Instead we will generate a V_MAY_DEF for
 259        the assignment.  */
 260     return is_gimple_tmp_rhs (t);
 261 }
 262
 263 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 264    LHS, or for a call argument.  */
 265
 266 bool
 267 is_gimple_mem_rhs (tree t)
 268 {
 269   /* If we're dealing with a renamable type, either source or dest
 270      must be a renamed variable.  */
 271   if (is_gimple_reg_type (TREE_TYPE (t)))
 272     return is_gimple_val (t);
 273   else
 274     return is_gimple_tmp_rhs (t);
 275 }
 276
 277 /* Returns the appropriate RHS predicate for this LHS.  */
 278
 279 gimple_predicate
 280 rhs_predicate_for (tree lhs)
 281 {
 282   if (is_gimple_tmp_var (lhs))
 283     return is_gimple_tmp_rhs;
 284   else if (is_gimple_reg (lhs))
 285     return is_gimple_reg_rhs;
 286   else
 287     return is_gimple_mem_rhs;
 288 }
 289
 290 /* Returns true if T is a valid CONSTRUCTOR component in GIMPLE, either
 291    a val or another CONSTRUCTOR.  */
 292
 293 bool
 294 is_gimple_constructor_elt (tree t)
 295 {
 296   return (is_gimple_val (t)
 297           || TREE_CODE (t) == CONSTRUCTOR);
 298 }
 299
 300 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 301
 302 bool
 303 is_gimple_lvalue (tree t)
 304 {
 305   return (is_gimple_addr_expr_arg (t)
 306           || TREE_CODE (t) == INDIRECT_REF
 307           || TREE_CODE (t) == WITH_SIZE_EXPR
 308           /* These are complex lvalues, but don't have addresses, so they
 309              go here.  */
 310           || TREE_CODE (t) == BIT_FIELD_REF);
 311 }
 312
 313 /*  Return true if T is a GIMPLE condition.  */
 314
 315 bool
 316 is_gimple_condexpr (tree t)
 317 {
 318   return (is_gimple_val (t)
 319           || TREE_CODE_CLASS (TREE_CODE (t)) == '<');
 320 }
 321
 322 /*  Return true if T is a valid operand for ADDR_EXPR.  */
 323
 324 bool
 325 is_gimple_addr_expr_arg (tree t)
 326 {
 327   return (is_gimple_id (t)
 328           || TREE_CODE (t) == ARRAY_REF
 329           || TREE_CODE (t) == ARRAY_RANGE_REF
 330           || TREE_CODE (t) == COMPONENT_REF
 331           || TREE_CODE (t) == REALPART_EXPR
 332           || TREE_CODE (t) == IMAGPART_EXPR
 333           || TREE_CODE (t) == INDIRECT_REF);
 334 }
 335
 336 /* Return true if T is function invariant.  Or rather a restricted
 337    form of function invariant.  */
 338
 339 bool
 340 is_gimple_min_invariant (tree t)
 341 {
 342   switch (TREE_CODE (t))
 343     {
 344     case ADDR_EXPR:
 345       return TREE_INVARIANT (t);
 346
 347     case INTEGER_CST:
 348     case REAL_CST:
 349     case STRING_CST:
 350     case COMPLEX_CST:
 351     case VECTOR_CST:
 352       return !TREE_OVERFLOW (t);
 353
 354     default:
 355       return false;
 356     }
 357 }
 358
 359 /* Return true if T looks like a valid GIMPLE statement.  */
 360
 361 bool
 362 is_gimple_stmt (tree t)
 363 {
 364   enum tree_code code = TREE_CODE (t);
 365
 366   if (IS_EMPTY_STMT (t))
 367     return 1;
 368
 369   switch (code)
 370     {
 371     case BIND_EXPR:
 372     case COND_EXPR:
 373       /* These are only valid if they're void.  */
 374       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 375
 376     case SWITCH_EXPR:
 377     case GOTO_EXPR:
 378     case RETURN_EXPR:
 379     case LABEL_EXPR:
 380     case CASE_LABEL_EXPR:
 381     case TRY_CATCH_EXPR:
 382     case TRY_FINALLY_EXPR:
 383     case EH_FILTER_EXPR:
 384     case CATCH_EXPR:
 385     case ASM_EXPR:
 386     case RESX_EXPR:
 387     case PHI_NODE:
 388     case STATEMENT_LIST:
 389       /* These are always void.  */
 390       return true;
 391
 392     case VA_ARG_EXPR:
 393       /* FIXME this should be lowered.  */
 394       return true;
 395
 396     case CALL_EXPR:
 397     case MODIFY_EXPR:
 398       /* These are valid regardless of their type.  */
 399       return true;
 400
 401     default:
 402       return false;
 403     }
 404 }
 405
 406 /* Return true if T is a variable.  */
 407
 408 bool
 409 is_gimple_variable (tree t)
 410 {
 411   return (TREE_CODE (t) == VAR_DECL
 412           || TREE_CODE (t) == PARM_DECL
 413           || TREE_CODE (t) == RESULT_DECL
 414           || TREE_CODE (t) == SSA_NAME);
 415 }
 416
 417 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 418
 419 static inline bool
 420 is_gimple_id (tree t)
 421 {
 422   return (is_gimple_variable (t)
 423           || TREE_CODE (t) == FUNCTION_DECL
 424           || TREE_CODE (t) == LABEL_DECL
 425           /* Allow string constants, since they are addressable.  */
 426           || TREE_CODE (t) == STRING_CST);
 427 }
 428
 429 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 430
 431 bool
 432 is_gimple_reg_type (tree type)
 433 {
 434   return (!AGGREGATE_TYPE_P (type)
 435           && TREE_CODE (type) != COMPLEX_TYPE);
 436 }
 437
 438
 439 /* Return true if T is a scalar register variable.  */
 440
 441 bool
 442 is_gimple_reg (tree t)
 443 {
 444   if (TREE_CODE (t) == SSA_NAME)
 445     t = SSA_NAME_VAR (t);
 446
 447   return (is_gimple_variable (t)
 448           && is_gimple_reg_type (TREE_TYPE (t))
 449           /* A volatile decl is not acceptable because we can't reuse it as
 450              needed.  We need to copy it into a temp first.  */
 451           && ! TREE_THIS_VOLATILE (t)
 452           && ! TREE_ADDRESSABLE (t)
 453           && ! needs_to_live_in_memory (t));
 454 }
 455
 456 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 457
 458 bool
 459 is_gimple_non_addressable (tree t)
 460 {
 461   if (TREE_CODE (t) == SSA_NAME)
 462     t = SSA_NAME_VAR (t);
 463
 464   return (is_gimple_variable (t)
 465           && ! TREE_ADDRESSABLE (t)
 466           && ! needs_to_live_in_memory (t));
 467 }
 468
 469 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 470
 471 bool
 472 is_gimple_val (tree t)
 473 {
 474   /* Make loads from volatiles and memory vars explicit.  */
 475   if (is_gimple_variable (t)
 476       && is_gimple_reg_type (TREE_TYPE (t))
 477       && !is_gimple_reg (t))
 478     return false;
 479
 480   /* FIXME make these decls.  That can happen only when we expose the
 481      entire landing-pad construct at the tree level.  */
 482   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 483     return 1;
 484
 485   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 486 }
 487
 488
 489 /* Return true if T is a GIMPLE minimal lvalue.  */
 490
 491 bool
 492 is_gimple_min_lval (tree t)
 493 {
 494   return (is_gimple_id (t)
 495           || TREE_CODE (t) == INDIRECT_REF);
 496 }
 497
 498 /* Return true if T is a typecast operation.  */
 499
 500 bool
 501 is_gimple_cast (tree t)
 502 {
 503   return (TREE_CODE (t) == NOP_EXPR
 504           || TREE_CODE (t) == CONVERT_EXPR
 505           || TREE_CODE (t) == FIX_TRUNC_EXPR
 506           || TREE_CODE (t) == FIX_CEIL_EXPR
 507           || TREE_CODE (t) == FIX_FLOOR_EXPR
 508           || TREE_CODE (t) == FIX_ROUND_EXPR);
 509 }
 510
 511 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 512
 513 bool
 514 is_gimple_call_addr (tree t)
 515 {
 516   return (TREE_CODE (t) == OBJ_TYPE_REF
 517           || is_gimple_val (t));
 518 }
 519
 520 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 521    Otherwise, return NULL_TREE.  */
 522
 523 tree
 524 get_call_expr_in (tree t)
 525 {
 526   if (TREE_CODE (t) == MODIFY_EXPR)
 527     t = TREE_OPERAND (t, 1);
 528   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 529     t = TREE_OPERAND (t, 0);
 530   if (TREE_CODE (t) == CALL_EXPR)
 531     return t;
 532   return NULL_TREE;
 533 }
 534
 535 /* Given a memory reference expression, return the base address.  Note that,
 536    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 537    expressions.  Therefore, given the reference PTR->FIELD, this function
 538    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 539
 540 tree
 541 get_base_address (tree t)
 542 {
 543   while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
 544          || handled_component_p (t))
 545     t = TREE_OPERAND (t, 0);
 546
 547   if (SSA_VAR_P (t)
 548       || TREE_CODE (t) == STRING_CST
 549       || TREE_CODE (t) == CONSTRUCTOR
 550       || TREE_CODE (t) == INDIRECT_REF)
 551     return t;
 552   else
 553     return NULL_TREE;
 554 }
 555
 556 void
 557 recalculate_side_effects (tree t)
 558 {
 559   enum tree_code code = TREE_CODE (t);
 560   int fro = first_rtl_op (code);
 561   int i;
 562
 563   switch (TREE_CODE_CLASS (code))
 564     {
 565     case 'e':
 566       switch (code)
 567         {
 568         case INIT_EXPR:
 569         case MODIFY_EXPR:
 570         case VA_ARG_EXPR:
 571         case PREDECREMENT_EXPR:
 572         case PREINCREMENT_EXPR:
 573         case POSTDECREMENT_EXPR:
 574         case POSTINCREMENT_EXPR:
 575           /* All of these have side-effects, no matter what their
 576              operands are.  */
 577           return;
 578
 579         default:
 580           break;
 581         }
 582       /* Fall through.  */
 583
 584     case '<':  /* a comparison expression */
 585     case '1':  /* a unary arithmetic expression */
 586     case '2':  /* a binary arithmetic expression */
 587     case 'r':  /* a reference */
 588       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 589       for (i = 0; i < fro; ++i)
 590         {
 591           tree op = TREE_OPERAND (t, i);
 592           if (op && TREE_SIDE_EFFECTS (op))
 593             TREE_SIDE_EFFECTS (t) = 1;
 594         }
 595       break;
 596    }
 597 }