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, 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 /* 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       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 MODIFY_EXPR 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 V_MAY_DEF 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     return is_gimple_val (t);
 121   else
 122     return is_gimple_formal_tmp_rhs (t);
 123 }
 124
 125 /* Returns the appropriate RHS predicate for this LHS.  */
 126
 127 gimple_predicate
 128 rhs_predicate_for (tree lhs)
 129 {
 130   if (is_gimple_formal_tmp_var (lhs))
 131     return is_gimple_formal_tmp_rhs;
 132   else if (is_gimple_reg (lhs))
 133     return is_gimple_reg_rhs;
 134   else
 135     return is_gimple_mem_rhs;
 136 }
 137
 138 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 139
 140 bool
 141 is_gimple_lvalue (tree t)
 142 {
 143   return (is_gimple_addressable (t)
 144           || TREE_CODE (t) == WITH_SIZE_EXPR
 145           /* These are complex lvalues, but don't have addresses, so they
 146              go here.  */
 147           || TREE_CODE (t) == BIT_FIELD_REF);
 148 }
 149
 150 /*  Return true if T is a GIMPLE condition.  */
 151
 152 bool
 153 is_gimple_condexpr (tree t)
 154 {
 155   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 156 }
 157
 158 /*  Return true if T is something whose address can be taken.  */
 159
 160 bool
 161 is_gimple_addressable (tree t)
 162 {
 163   return (is_gimple_id (t) || handled_component_p (t)
 164           || INDIRECT_REF_P (t));
 165 }
 166
 167 /* Return true if T is function invariant.  Or rather a restricted
 168    form of function invariant.  */
 169
 170 bool
 171 is_gimple_min_invariant (tree t)
 172 {
 173   switch (TREE_CODE (t))
 174     {
 175     case ADDR_EXPR:
 176       return TREE_INVARIANT (t);
 177
 178     case INTEGER_CST:
 179     case REAL_CST:
 180     case STRING_CST:
 181     case COMPLEX_CST:
 182     case VECTOR_CST:
 183       return true;
 184
 185     default:
 186       return false;
 187     }
 188 }
 189
 190 /* Return true if T looks like a valid GIMPLE statement.  */
 191
 192 bool
 193 is_gimple_stmt (tree t)
 194 {
 195   enum tree_code code = TREE_CODE (t);
 196
 197   if (IS_EMPTY_STMT (t))
 198     return 1;
 199
 200   switch (code)
 201     {
 202     case BIND_EXPR:
 203     case COND_EXPR:
 204       /* These are only valid if they're void.  */
 205       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 206
 207     case SWITCH_EXPR:
 208     case GOTO_EXPR:
 209     case RETURN_EXPR:
 210     case LABEL_EXPR:
 211     case CASE_LABEL_EXPR:
 212     case TRY_CATCH_EXPR:
 213     case TRY_FINALLY_EXPR:
 214     case EH_FILTER_EXPR:
 215     case CATCH_EXPR:
 216     case ASM_EXPR:
 217     case RESX_EXPR:
 218     case PHI_NODE:
 219     case STATEMENT_LIST:
 220       /* These are always void.  */
 221       return true;
 222
 223     case CALL_EXPR:
 224     case MODIFY_EXPR:
 225       /* These are valid regardless of their type.  */
 226       return true;
 227
 228     default:
 229       return false;
 230     }
 231 }
 232
 233 /* Return true if T is a variable.  */
 234
 235 bool
 236 is_gimple_variable (tree t)
 237 {
 238   return (TREE_CODE (t) == VAR_DECL
 239           || TREE_CODE (t) == PARM_DECL
 240           || TREE_CODE (t) == RESULT_DECL
 241           || TREE_CODE (t) == SSA_NAME);
 242 }
 243
 244 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 245
 246 static inline bool
 247 is_gimple_id (tree t)
 248 {
 249   return (is_gimple_variable (t)
 250           || TREE_CODE (t) == FUNCTION_DECL
 251           || TREE_CODE (t) == LABEL_DECL
 252           || TREE_CODE (t) == CONST_DECL
 253           /* Allow string constants, since they are addressable.  */
 254           || TREE_CODE (t) == STRING_CST);
 255 }
 256
 257 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 258
 259 bool
 260 is_gimple_reg_type (tree type)
 261 {
 262   return (!AGGREGATE_TYPE_P (type)
 263           && TREE_CODE (type) != COMPLEX_TYPE);
 264 }
 265
 266
 267 /* Return true if T is a scalar register variable.  */
 268
 269 bool
 270 is_gimple_reg (tree t)
 271 {
 272   if (TREE_CODE (t) == SSA_NAME)
 273     t = SSA_NAME_VAR (t);
 274
 275   if (!is_gimple_variable (t))
 276     return false;
 277   if (!is_gimple_reg_type (TREE_TYPE (t)))
 278     return false;
 279
 280   /* A volatile decl is not acceptable because we can't reuse it as
 281      needed.  We need to copy it into a temp first.  */
 282   if (TREE_THIS_VOLATILE (t))
 283     return false;
 284
 285   /* We define "registers" as things that can be renamed as needed,
 286      which with our infrastructure does not apply to memory.  */
 287   if (needs_to_live_in_memory (t))
 288     return false;
 289
 290   /* Hard register variables are an interesting case.  For those that
 291      are call-clobbered, we don't know where all the calls are, since
 292      we don't (want to) take into account which operations will turn
 293      into libcalls at the rtl level.  For those that are call-saved,
 294      we don't currently model the fact that calls may in fact change
 295      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 296      level, and so miss variable changes that might imply.  All around,
 297      it seems safest to not do too much optimization with these at the
 298      tree level at all.  We'll have to rely on the rtl optimizers to
 299      clean this up, as there we've got all the appropriate bits exposed.  */
 300   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 301     return false;
 302
 303   return true;
 304 }
 305
 306 /* Returns true if T is a GIMPLE formal temporary variable.  */
 307
 308 bool
 309 is_gimple_formal_tmp_var (tree t)
 310 {
 311   if (TREE_CODE (t) == SSA_NAME)
 312     return true;
 313
 314   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 315 }
 316
 317 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 318
 319 bool
 320 is_gimple_formal_tmp_reg (tree t)
 321 {
 322   /* The intent of this is to get hold of a value that won't change.
 323      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 324   if (TREE_CODE (t) == SSA_NAME)
 325     return true;
 326
 327   /* We don't know the lifetime characteristics of user variables.  */
 328   if (!is_gimple_formal_tmp_var (t))
 329     return false;
 330
 331   /* Finally, it must be capable of being placed in a register.  */
 332   return is_gimple_reg (t);
 333 }
 334
 335 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 336
 337 bool
 338 is_gimple_non_addressable (tree t)
 339 {
 340   if (TREE_CODE (t) == SSA_NAME)
 341     t = SSA_NAME_VAR (t);
 342
 343   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 344 }
 345
 346 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 347
 348 bool
 349 is_gimple_val (tree t)
 350 {
 351   /* Make loads from volatiles and memory vars explicit.  */
 352   if (is_gimple_variable (t)
 353       && is_gimple_reg_type (TREE_TYPE (t))
 354       && !is_gimple_reg (t))
 355     return false;
 356
 357   /* FIXME make these decls.  That can happen only when we expose the
 358      entire landing-pad construct at the tree level.  */
 359   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 360     return 1;
 361
 362   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 363 }
 364
 365 /* Similarly, but accept hard registers as inputs to asm statements.  */
 366
 367 bool
 368 is_gimple_asm_val (tree t)
 369 {
 370   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 371     return true;
 372
 373   return is_gimple_val (t);
 374 }
 375
 376 /* Return true if T is a GIMPLE minimal lvalue.  */
 377
 378 bool
 379 is_gimple_min_lval (tree t)
 380 {
 381   return (is_gimple_id (t)
 382           || TREE_CODE (t) == INDIRECT_REF);
 383 }
 384
 385 /* Return true if T is a typecast operation.  */
 386
 387 bool
 388 is_gimple_cast (tree t)
 389 {
 390   return (TREE_CODE (t) == NOP_EXPR
 391           || TREE_CODE (t) == CONVERT_EXPR
 392           || TREE_CODE (t) == FIX_TRUNC_EXPR
 393           || TREE_CODE (t) == FIX_CEIL_EXPR
 394           || TREE_CODE (t) == FIX_FLOOR_EXPR
 395           || TREE_CODE (t) == FIX_ROUND_EXPR);
 396 }
 397
 398 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 399
 400 bool
 401 is_gimple_call_addr (tree t)
 402 {
 403   return (TREE_CODE (t) == OBJ_TYPE_REF
 404           || is_gimple_val (t));
 405 }
 406
 407 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 408    Otherwise, return NULL_TREE.  */
 409
 410 tree
 411 get_call_expr_in (tree t)
 412 {
 413   if (TREE_CODE (t) == MODIFY_EXPR)
 414     t = TREE_OPERAND (t, 1);
 415   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 416     t = TREE_OPERAND (t, 0);
 417   if (TREE_CODE (t) == CALL_EXPR)
 418     return t;
 419   return NULL_TREE;
 420 }
 421
 422 /* Given a memory reference expression T, return its base address.
 423    The base address of a memory reference expression is the main
 424    object being referenced.  For instance, the base address for
 425    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 426    away the offset part from a memory address.
 427
 428    This function calls handled_component_p to strip away all the inner
 429    parts of the memory reference until it reaches the base object.  */
 430
 431 tree
 432 get_base_address (tree t)
 433 {
 434   while (handled_component_p (t))
 435     t = TREE_OPERAND (t, 0);
 436
 437   if (SSA_VAR_P (t)
 438       || TREE_CODE (t) == STRING_CST
 439       || TREE_CODE (t) == CONSTRUCTOR
 440       || INDIRECT_REF_P (t))
 441     return t;
 442   else
 443     return NULL_TREE;
 444 }
 445
 446 void
 447 recalculate_side_effects (tree t)
 448 {
 449   enum tree_code code = TREE_CODE (t);
 450   int len = TREE_CODE_LENGTH (code);
 451   int i;
 452
 453   switch (TREE_CODE_CLASS (code))
 454     {
 455     case tcc_expression:
 456       switch (code)
 457         {
 458         case INIT_EXPR:
 459         case MODIFY_EXPR:
 460         case VA_ARG_EXPR:
 461         case PREDECREMENT_EXPR:
 462         case PREINCREMENT_EXPR:
 463         case POSTDECREMENT_EXPR:
 464         case POSTINCREMENT_EXPR:
 465           /* All of these have side-effects, no matter what their
 466              operands are.  */
 467           return;
 468
 469         default:
 470           break;
 471         }
 472       /* Fall through.  */
 473
 474     case tcc_comparison:  /* a comparison expression */
 475     case tcc_unary:       /* a unary arithmetic expression */
 476     case tcc_binary:      /* a binary arithmetic expression */
 477     case tcc_reference:   /* a reference */
 478       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 479       for (i = 0; i < len; ++i)
 480         {
 481           tree op = TREE_OPERAND (t, i);
 482           if (op && TREE_SIDE_EFFECTS (op))
 483             TREE_SIDE_EFFECTS (t) = 1;
 484         }
 485       break;
 486
 487     default:
 488       /* Can never be used with non-expressions.  */
 489       gcc_unreachable ();
 490    }
 491 }