gcc-4.1.2/gcc/tree-gimple.c

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