gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5    Rewritten by Jason Merrill <jason@redhat.com>
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 2, or (at your option)
  12 any later version.
  13
  14 GCC is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to
  21 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  22 Boston, MA 02110-1301, USA.  */
  23
  24 #include "config.h"
  25 #include "system.h"
  26 #include "coretypes.h"
  27 #include "ggc.h"
  28 #include "tm.h"
  29 #include "tree.h"
  30 #include "tree-gimple.h"
  31 #include "tree-flow.h"
  32 #include "output.h"
  33 #include "rtl.h"
  34 #include "expr.h"
  35 #include "bitmap.h"
  36
  37 /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi.  */
  38
  39 /* Validation of GIMPLE expressions.  */
  40
  41 /* Return true if T is a GIMPLE RHS for an assignment to a temporary.  */
  42
  43 bool
  44 is_gimple_formal_tmp_rhs (tree t)
  45 {
  46   enum tree_code code = TREE_CODE (t);
  47
  48   switch (TREE_CODE_CLASS (code))
  49     {
  50     case tcc_unary:
  51     case tcc_binary:
  52     case tcc_comparison:
  53       return true;
  54
  55     default:
  56       break;
  57     }
  58
  59   switch (code)
  60     {
  61     case TRUTH_NOT_EXPR:
  62     case TRUTH_AND_EXPR:
  63     case TRUTH_OR_EXPR:
  64     case TRUTH_XOR_EXPR:
  65     case ADDR_EXPR:
  66     case CALL_EXPR:
  67     case CONSTRUCTOR:
  68     case COMPLEX_EXPR:
  69     case INTEGER_CST:
  70     case REAL_CST:
  71     case STRING_CST:
  72     case COMPLEX_CST:
  73     case VECTOR_CST:
  74     case OBJ_TYPE_REF:
  75     case ASSERT_EXPR:
  76       return true;
  77
  78     default:
  79       break;
  80     }
  81
  82   return is_gimple_lvalue (t) || is_gimple_val (t);
  83 }
  84
  85 /* Returns true iff T is a valid RHS for an assignment to a renamed
  86    user -- or front-end generated artificial -- variable.  */
  87
  88 bool
  89 is_gimple_reg_rhs (tree t)
  90 {
  91   /* If the RHS of the GIMPLE_MODIFY_STMT may throw or make a nonlocal goto
  92      and the LHS is a user variable, then we need to introduce a formal
  93      temporary.  This way the optimizers can determine that the user
  94      variable is only modified if evaluation of the RHS does not throw.
  95
  96      Don't force a temp of a non-renamable type; the copy could be
  97      arbitrarily expensive.  Instead we will generate a VDEF for
  98      the assignment.  */
  99
 100   if (is_gimple_reg_type (TREE_TYPE (t))
 101       && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t))
 102           || tree_could_throw_p (t)))
 103     return false;
 104
 105   return is_gimple_formal_tmp_rhs (t);
 106 }
 107
 108 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 109    LHS, or for a call argument.  */
 110
 111 bool
 112 is_gimple_mem_rhs (tree t)
 113 {
 114   /* If we're dealing with a renamable type, either source or dest must be
 115      a renamed variable.  Also force a temporary if the type doesn't need
 116      to be stored in memory, since it's cheap and prevents erroneous
 117      tailcalls (PR 17526).  */
 118   if (is_gimple_reg_type (TREE_TYPE (t))
 119       || (TYPE_MODE (TREE_TYPE (t)) != BLKmode
 120           && (TREE_CODE (t) != CALL_EXPR
 121               || ! aggregate_value_p (t, t))))
 122     return is_gimple_val (t);
 123   else
 124     return is_gimple_formal_tmp_rhs (t);
 125 }
 126
 127 /* Returns the appropriate RHS predicate for this LHS.  */
 128
 129 gimple_predicate
 130 rhs_predicate_for (tree lhs)
 131 {
 132   if (is_gimple_formal_tmp_var (lhs))
 133     return is_gimple_formal_tmp_rhs;
 134   else if (is_gimple_reg (lhs))
 135     return is_gimple_reg_rhs;
 136   else
 137     return is_gimple_mem_rhs;
 138 }
 139
 140 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 141
 142 bool
 143 is_gimple_lvalue (tree t)
 144 {
 145   return (is_gimple_addressable (t)
 146           || TREE_CODE (t) == WITH_SIZE_EXPR
 147           /* These are complex lvalues, but don't have addresses, so they
 148              go here.  */
 149           || TREE_CODE (t) == BIT_FIELD_REF);
 150 }
 151
 152 /*  Return true if T is a GIMPLE condition.  */
 153
 154 bool
 155 is_gimple_condexpr (tree t)
 156 {
 157   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 158 }
 159
 160 /*  Return true if T is something whose address can be taken.  */
 161
 162 bool
 163 is_gimple_addressable (tree t)
 164 {
 165   return (is_gimple_id (t) || handled_component_p (t)
 166           || INDIRECT_REF_P (t));
 167 }
 168
 169 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
 170    form of function invariant.  */
 171
 172 bool
 173 is_gimple_min_invariant (tree t)
 174 {
 175   switch (TREE_CODE (t))
 176     {
 177     case ADDR_EXPR:
 178       return TREE_INVARIANT (t);
 179
 180     case INTEGER_CST:
 181     case REAL_CST:
 182     case STRING_CST:
 183     case COMPLEX_CST:
 184     case VECTOR_CST:
 185       return true;
 186
 187     /* Vector constant constructors are gimple invariant.  */
 188     case CONSTRUCTOR:
 189       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 190         return TREE_CONSTANT (t);
 191       else
 192         return false;
 193
 194     default:
 195       return false;
 196     }
 197 }
 198
 199 /* Return true if T looks like a valid GIMPLE statement.  */
 200
 201 bool
 202 is_gimple_stmt (tree t)
 203 {
 204   enum tree_code code = TREE_CODE (t);
 205
 206   switch (code)
 207     {
 208     case NOP_EXPR:
 209       /* The only valid NOP_EXPR is the empty statement.  */
 210       return IS_EMPTY_STMT (t);
 211
 212     case BIND_EXPR:
 213     case COND_EXPR:
 214       /* These are only valid if they're void.  */
 215       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 216
 217     case SWITCH_EXPR:
 218     case GOTO_EXPR:
 219     case RETURN_EXPR:
 220     case LABEL_EXPR:
 221     case CASE_LABEL_EXPR:
 222     case TRY_CATCH_EXPR:
 223     case TRY_FINALLY_EXPR:
 224     case EH_FILTER_EXPR:
 225     case CATCH_EXPR:
 226     case CHANGE_DYNAMIC_TYPE_EXPR:
 227     case ASM_EXPR:
 228     case RESX_EXPR:
 229     case PHI_NODE:
 230     case STATEMENT_LIST:
 231     case OMP_PARALLEL:
 232     case OMP_FOR:
 233     case OMP_SECTIONS:
 234     case OMP_SECTION:
 235     case OMP_SINGLE:
 236     case OMP_MASTER:
 237     case OMP_ORDERED:
 238     case OMP_CRITICAL:
 239     case OMP_RETURN:
 240     case OMP_CONTINUE:
 241       /* These are always void.  */
 242       return true;
 243
 244     case CALL_EXPR:
 245     case GIMPLE_MODIFY_STMT:
 246       /* These are valid regardless of their type.  */
 247       return true;
 248
 249     default:
 250       return false;
 251     }
 252 }
 253
 254 /* Return true if T is a variable.  */
 255
 256 bool
 257 is_gimple_variable (tree t)
 258 {
 259   return (TREE_CODE (t) == VAR_DECL
 260           || TREE_CODE (t) == PARM_DECL
 261           || TREE_CODE (t) == RESULT_DECL
 262           || TREE_CODE (t) == SSA_NAME);
 263 }
 264
 265 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 266
 267 bool
 268 is_gimple_id (tree t)
 269 {
 270   return (is_gimple_variable (t)
 271           || TREE_CODE (t) == FUNCTION_DECL
 272           || TREE_CODE (t) == LABEL_DECL
 273           || TREE_CODE (t) == CONST_DECL
 274           /* Allow string constants, since they are addressable.  */
 275           || TREE_CODE (t) == STRING_CST);
 276 }
 277
 278 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 279
 280 bool
 281 is_gimple_reg_type (tree type)
 282 {
 283   return !AGGREGATE_TYPE_P (type);
 284 }
 285
 286 /* Return true if T is a non-aggregate register variable.  */
 287
 288 bool
 289 is_gimple_reg (tree t)
 290 {
 291   if (TREE_CODE (t) == SSA_NAME)
 292     t = SSA_NAME_VAR (t);
 293
 294   if (MTAG_P (t))
 295     return false;
 296
 297   if (!is_gimple_variable (t))
 298     return false;
 299
 300   if (!is_gimple_reg_type (TREE_TYPE (t)))
 301     return false;
 302
 303   /* A volatile decl is not acceptable because we can't reuse it as
 304      needed.  We need to copy it into a temp first.  */
 305   if (TREE_THIS_VOLATILE (t))
 306     return false;
 307
 308   /* We define "registers" as things that can be renamed as needed,
 309      which with our infrastructure does not apply to memory.  */
 310   if (needs_to_live_in_memory (t))
 311     return false;
 312
 313   /* Hard register variables are an interesting case.  For those that
 314      are call-clobbered, we don't know where all the calls are, since
 315      we don't (want to) take into account which operations will turn
 316      into libcalls at the rtl level.  For those that are call-saved,
 317      we don't currently model the fact that calls may in fact change
 318      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 319      level, and so miss variable changes that might imply.  All around,
 320      it seems safest to not do too much optimization with these at the
 321      tree level at all.  We'll have to rely on the rtl optimizers to
 322      clean this up, as there we've got all the appropriate bits exposed.  */
 323   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 324     return false;
 325
 326   /* Complex values must have been put into ssa form.  That is, no
 327      assignments to the individual components.  */
 328   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 329       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 330     return DECL_GIMPLE_REG_P (t);
 331
 332   return true;
 333 }
 334
 335
 336 /* Returns true if T is a GIMPLE formal temporary variable.  */
 337
 338 bool
 339 is_gimple_formal_tmp_var (tree t)
 340 {
 341   if (TREE_CODE (t) == SSA_NAME)
 342     return true;
 343
 344   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 345 }
 346
 347 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 348
 349 bool
 350 is_gimple_formal_tmp_reg (tree t)
 351 {
 352   /* The intent of this is to get hold of a value that won't change.
 353      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 354   if (TREE_CODE (t) == SSA_NAME)
 355     return true;
 356
 357   /* We don't know the lifetime characteristics of user variables.  */
 358   if (!is_gimple_formal_tmp_var (t))
 359     return false;
 360
 361   /* Finally, it must be capable of being placed in a register.  */
 362   return is_gimple_reg (t);
 363 }
 364
 365 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 366
 367 bool
 368 is_gimple_non_addressable (tree t)
 369 {
 370   if (TREE_CODE (t) == SSA_NAME)
 371     t = SSA_NAME_VAR (t);
 372
 373   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 374 }
 375
 376 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 377
 378 bool
 379 is_gimple_val (tree t)
 380 {
 381   /* Make loads from volatiles and memory vars explicit.  */
 382   if (is_gimple_variable (t)
 383       && is_gimple_reg_type (TREE_TYPE (t))
 384       && !is_gimple_reg (t))
 385     return false;
 386
 387   /* FIXME make these decls.  That can happen only when we expose the
 388      entire landing-pad construct at the tree level.  */
 389   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 390     return true;
 391
 392   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 393 }
 394
 395 /* Similarly, but accept hard registers as inputs to asm statements.  */
 396
 397 bool
 398 is_gimple_asm_val (tree t)
 399 {
 400   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 401     return true;
 402
 403   return is_gimple_val (t);
 404 }
 405
 406 /* Return true if T is a GIMPLE minimal lvalue.  */
 407
 408 bool
 409 is_gimple_min_lval (tree t)
 410 {
 411   return (is_gimple_id (t)
 412           || TREE_CODE (t) == INDIRECT_REF);
 413 }
 414
 415 /* Return true if T is a typecast operation.  */
 416
 417 bool
 418 is_gimple_cast (tree t)
 419 {
 420   return (TREE_CODE (t) == NOP_EXPR
 421           || TREE_CODE (t) == CONVERT_EXPR
 422           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 423 }
 424
 425 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 426
 427 bool
 428 is_gimple_call_addr (tree t)
 429 {
 430   return (TREE_CODE (t) == OBJ_TYPE_REF
 431           || is_gimple_val (t));
 432 }
 433
 434 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 435    Otherwise, return NULL_TREE.  */
 436
 437 tree
 438 get_call_expr_in (tree t)
 439 {
 440   /* FIXME tuples: delete the assertion below when conversion complete.  */
 441   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 442   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 443     t = GIMPLE_STMT_OPERAND (t, 1);
 444   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 445     t = TREE_OPERAND (t, 0);
 446   if (TREE_CODE (t) == CALL_EXPR)
 447     return t;
 448   return NULL_TREE;
 449 }
 450
 451 /* Given a memory reference expression T, return its base address.
 452    The base address of a memory reference expression is the main
 453    object being referenced.  For instance, the base address for
 454    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 455    away the offset part from a memory address.
 456
 457    This function calls handled_component_p to strip away all the inner
 458    parts of the memory reference until it reaches the base object.  */
 459
 460 tree
 461 get_base_address (tree t)
 462 {
 463   while (handled_component_p (t))
 464     t = TREE_OPERAND (t, 0);
 465
 466   if (SSA_VAR_P (t)
 467       || TREE_CODE (t) == STRING_CST
 468       || TREE_CODE (t) == CONSTRUCTOR
 469       || INDIRECT_REF_P (t))
 470     return t;
 471   else
 472     return NULL_TREE;
 473 }
 474
 475 void
 476 recalculate_side_effects (tree t)
 477 {
 478   enum tree_code code = TREE_CODE (t);
 479   int len = TREE_OPERAND_LENGTH (t);
 480   int i;
 481
 482   switch (TREE_CODE_CLASS (code))
 483     {
 484     case tcc_expression:
 485       switch (code)
 486         {
 487         case INIT_EXPR:
 488         case GIMPLE_MODIFY_STMT:
 489         case VA_ARG_EXPR:
 490         case PREDECREMENT_EXPR:
 491         case PREINCREMENT_EXPR:
 492         case POSTDECREMENT_EXPR:
 493         case POSTINCREMENT_EXPR:
 494           /* All of these have side-effects, no matter what their
 495              operands are.  */
 496           return;
 497
 498         default:
 499           break;
 500         }
 501       /* Fall through.  */
 502
 503     case tcc_comparison:  /* a comparison expression */
 504     case tcc_unary:       /* a unary arithmetic expression */
 505     case tcc_binary:      /* a binary arithmetic expression */
 506     case tcc_reference:   /* a reference */
 507     case tcc_vl_exp:        /* a function call */
 508       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 509       for (i = 0; i < len; ++i)
 510         {
 511           tree op = TREE_OPERAND (t, i);
 512           if (op && TREE_SIDE_EFFECTS (op))
 513             TREE_SIDE_EFFECTS (t) = 1;
 514         }
 515       break;
 516
 517     default:
 518       /* Can never be used with non-expressions.  */
 519       gcc_unreachable ();
 520    }
 521 }