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 static inline bool is_gimple_id (tree);
  39
  40 /* Validation of GIMPLE expressions.  */
  41
  42 /* Return true if T is a GIMPLE RHS for an assignment to a temporary.  */
  43
  44 bool
  45 is_gimple_formal_tmp_rhs (tree t)
  46 {
  47   enum tree_code code = TREE_CODE (t);
  48
  49   switch (TREE_CODE_CLASS (code))
  50     {
  51     case tcc_unary:
  52     case tcc_binary:
  53     case tcc_comparison:
  54       return true;
  55
  56     default:
  57       break;
  58     }
  59
  60   switch (code)
  61     {
  62     case TRUTH_NOT_EXPR:
  63     case TRUTH_AND_EXPR:
  64     case TRUTH_OR_EXPR:
  65     case TRUTH_XOR_EXPR:
  66     case ADDR_EXPR:
  67     case CALL_EXPR:
  68     case CONSTRUCTOR:
  69     case COMPLEX_EXPR:
  70     case INTEGER_CST:
  71     case REAL_CST:
  72     case STRING_CST:
  73     case COMPLEX_CST:
  74     case VECTOR_CST:
  75     case OBJ_TYPE_REF:
  76     case ASSERT_EXPR:
  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 }
 150
 151 /*  Return true if T is a GIMPLE condition.  */
 152
 153 bool
 154 is_gimple_condexpr (tree t)
 155 {
 156   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 157 }
 158
 159 /*  Return true if T is something whose address can be taken.  */
 160
 161 bool
 162 is_gimple_addressable (tree t)
 163 {
 164   return (is_gimple_id (t) || handled_component_p (t)
 165           || INDIRECT_REF_P (t));
 166 }
 167
 168 /* Return true if T is function invariant.  Or rather a restricted
 169    form of function invariant.  */
 170
 171 bool
 172 is_gimple_min_invariant (tree t)
 173 {
 174   switch (TREE_CODE (t))
 175     {
 176     case ADDR_EXPR:
 177       return TREE_INVARIANT (t);
 178
 179     case INTEGER_CST:
 180     case REAL_CST:
 181     case STRING_CST:
 182     case COMPLEX_CST:
 183     case VECTOR_CST:
 184       return true;
 185
 186     default:
 187       return false;
 188     }
 189 }
 190
 191 /* Return true if T looks like a valid GIMPLE statement.  */
 192
 193 bool
 194 is_gimple_stmt (tree t)
 195 {
 196   enum tree_code code = TREE_CODE (t);
 197
 198   if (IS_EMPTY_STMT (t))
 199     return 1;
 200
 201   switch (code)
 202     {
 203     case BIND_EXPR:
 204     case COND_EXPR:
 205       /* These are only valid if they're void.  */
 206       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 207
 208     case SWITCH_EXPR:
 209     case GOTO_EXPR:
 210     case RETURN_EXPR:
 211     case LABEL_EXPR:
 212     case CASE_LABEL_EXPR:
 213     case TRY_CATCH_EXPR:
 214     case TRY_FINALLY_EXPR:
 215     case EH_FILTER_EXPR:
 216     case CATCH_EXPR:
 217     case ASM_EXPR:
 218     case RESX_EXPR:
 219     case PHI_NODE:
 220     case STATEMENT_LIST:
 221       /* These are always void.  */
 222       return true;
 223
 224     case CALL_EXPR:
 225     case MODIFY_EXPR:
 226       /* These are valid regardless of their type.  */
 227       return true;
 228
 229     default:
 230       return false;
 231     }
 232 }
 233
 234 /* Return true if T is a variable.  */
 235
 236 bool
 237 is_gimple_variable (tree t)
 238 {
 239   return (TREE_CODE (t) == VAR_DECL
 240           || TREE_CODE (t) == PARM_DECL
 241           || TREE_CODE (t) == RESULT_DECL
 242           || TREE_CODE (t) == SSA_NAME);
 243 }
 244
 245 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 246
 247 static inline bool
 248 is_gimple_id (tree t)
 249 {
 250   return (is_gimple_variable (t)
 251           || TREE_CODE (t) == FUNCTION_DECL
 252           || TREE_CODE (t) == LABEL_DECL
 253           || TREE_CODE (t) == CONST_DECL
 254           /* Allow string constants, since they are addressable.  */
 255           || TREE_CODE (t) == STRING_CST);
 256 }
 257
 258 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 259
 260 bool
 261 is_gimple_reg_type (tree type)
 262 {
 263   return !AGGREGATE_TYPE_P (type);
 264 }
 265
 266 /* Return true if T is a non-aggregate register variable.  */
 267
 268 bool
 269 is_gimple_reg (tree t)
 270 {
 271   var_ann_t ann;
 272
 273   if (TREE_CODE (t) == SSA_NAME)
 274     t = SSA_NAME_VAR (t);
 275
 276   if (MTAG_P (t))
 277     return false;
 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
 314   /* Some compiler temporaries are created to be used exclusively in
 315      virtual operands (currently memory tags and sub-variables).
 316      These variables should never be considered GIMPLE registers.  */
 317   if (DECL_ARTIFICIAL (t) && (ann = var_ann (t)) != NULL)
 318     return !MTAG_P (t);
 319
 320   return true;
 321 }
 322
 323
 324 /* Returns true if T is a GIMPLE formal temporary variable.  */
 325
 326 bool
 327 is_gimple_formal_tmp_var (tree t)
 328 {
 329   if (TREE_CODE (t) == SSA_NAME)
 330     return true;
 331
 332   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 333 }
 334
 335 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 336
 337 bool
 338 is_gimple_formal_tmp_reg (tree t)
 339 {
 340   /* The intent of this is to get hold of a value that won't change.
 341      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 342   if (TREE_CODE (t) == SSA_NAME)
 343     return true;
 344
 345   /* We don't know the lifetime characteristics of user variables.  */
 346   if (!is_gimple_formal_tmp_var (t))
 347     return false;
 348
 349   /* Finally, it must be capable of being placed in a register.  */
 350   return is_gimple_reg (t);
 351 }
 352
 353 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 354
 355 bool
 356 is_gimple_non_addressable (tree t)
 357 {
 358   if (TREE_CODE (t) == SSA_NAME)
 359     t = SSA_NAME_VAR (t);
 360
 361   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 362 }
 363
 364 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 365
 366 bool
 367 is_gimple_val (tree t)
 368 {
 369   /* Make loads from volatiles and memory vars explicit.  */
 370   if (is_gimple_variable (t)
 371       && is_gimple_reg_type (TREE_TYPE (t))
 372       && !is_gimple_reg (t))
 373     return false;
 374
 375   /* FIXME make these decls.  That can happen only when we expose the
 376      entire landing-pad construct at the tree level.  */
 377   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 378     return 1;
 379
 380   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 381 }
 382
 383 /* Similarly, but accept hard registers as inputs to asm statements.  */
 384
 385 bool
 386 is_gimple_asm_val (tree t)
 387 {
 388   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 389     return true;
 390
 391   return is_gimple_val (t);
 392 }
 393
 394 /* Return true if T is a GIMPLE minimal lvalue.  */
 395
 396 bool
 397 is_gimple_min_lval (tree t)
 398 {
 399   return (is_gimple_id (t)
 400           || TREE_CODE (t) == INDIRECT_REF);
 401 }
 402
 403 /* Return true if T is a typecast operation.  */
 404
 405 bool
 406 is_gimple_cast (tree t)
 407 {
 408   return (TREE_CODE (t) == NOP_EXPR
 409           || TREE_CODE (t) == CONVERT_EXPR
 410           || TREE_CODE (t) == FIX_TRUNC_EXPR
 411           || TREE_CODE (t) == FIX_CEIL_EXPR
 412           || TREE_CODE (t) == FIX_FLOOR_EXPR
 413           || TREE_CODE (t) == FIX_ROUND_EXPR);
 414 }
 415
 416 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 417
 418 bool
 419 is_gimple_call_addr (tree t)
 420 {
 421   return (TREE_CODE (t) == OBJ_TYPE_REF
 422           || is_gimple_val (t));
 423 }
 424
 425 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 426    Otherwise, return NULL_TREE.  */
 427
 428 tree
 429 get_call_expr_in (tree t)
 430 {
 431   if (TREE_CODE (t) == MODIFY_EXPR)
 432     t = TREE_OPERAND (t, 1);
 433   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 434     t = TREE_OPERAND (t, 0);
 435   if (TREE_CODE (t) == CALL_EXPR)
 436     return t;
 437   return NULL_TREE;
 438 }
 439
 440 /* Given a memory reference expression T, return its base address.
 441    The base address of a memory reference expression is the main
 442    object being referenced.  For instance, the base address for
 443    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 444    away the offset part from a memory address.
 445
 446    This function calls handled_component_p to strip away all the inner
 447    parts of the memory reference until it reaches the base object.  */
 448
 449 tree
 450 get_base_address (tree t)
 451 {
 452   while (handled_component_p (t))
 453     t = TREE_OPERAND (t, 0);
 454
 455   if (SSA_VAR_P (t)
 456       || TREE_CODE (t) == STRING_CST
 457       || TREE_CODE (t) == CONSTRUCTOR
 458       || INDIRECT_REF_P (t))
 459     return t;
 460   else
 461     return NULL_TREE;
 462 }
 463
 464 void
 465 recalculate_side_effects (tree t)
 466 {
 467   enum tree_code code = TREE_CODE (t);
 468   int len = TREE_CODE_LENGTH (code);
 469   int i;
 470
 471   switch (TREE_CODE_CLASS (code))
 472     {
 473     case tcc_expression:
 474       switch (code)
 475         {
 476         case INIT_EXPR:
 477         case MODIFY_EXPR:
 478         case VA_ARG_EXPR:
 479         case PREDECREMENT_EXPR:
 480         case PREINCREMENT_EXPR:
 481         case POSTDECREMENT_EXPR:
 482         case POSTINCREMENT_EXPR:
 483           /* All of these have side-effects, no matter what their
 484              operands are.  */
 485           return;
 486
 487         default:
 488           break;
 489         }
 490       /* Fall through.  */
 491
 492     case tcc_comparison:  /* a comparison expression */
 493     case tcc_unary:       /* a unary arithmetic expression */
 494     case tcc_binary:      /* a binary arithmetic expression */
 495     case tcc_reference:   /* a reference */
 496       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 497       for (i = 0; i < len; ++i)
 498         {
 499           tree op = TREE_OPERAND (t, i);
 500           if (op && TREE_SIDE_EFFECTS (op))
 501             TREE_SIDE_EFFECTS (t) = 1;
 502         }
 503       break;
 504
 505     default:
 506       /* Can never be used with non-expressions.  */
 507       gcc_unreachable ();
 508    }
 509 }