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 3, 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 COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  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       return true;
  76
  77     default:
  78       break;
  79     }
  80
  81   return is_gimple_lvalue (t) || is_gimple_val (t);
  82 }
  83
  84 /* Returns true iff T is a valid RHS for an assignment to a renamed
  85    user -- or front-end generated artificial -- variable.  */
  86
  87 bool
  88 is_gimple_reg_rhs (tree t)
  89 {
  90   /* If the RHS of the GIMPLE_MODIFY_STMT may throw or make a nonlocal goto
  91      and the LHS is a user variable, then we need to introduce a formal
  92      temporary.  This way the optimizers can determine that the user
  93      variable is only modified if evaluation of the RHS does not throw.
  94
  95      Don't force a temp of a non-renamable type; the copy could be
  96      arbitrarily expensive.  Instead we will generate a VDEF for
  97      the assignment.  */
  98
  99   if (is_gimple_reg_type (TREE_TYPE (t))
 100       && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t))
 101           || tree_could_throw_p (t)))
 102     return false;
 103
 104   return is_gimple_formal_tmp_rhs (t);
 105 }
 106
 107 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 108    LHS, or for a call argument.  */
 109
 110 bool
 111 is_gimple_mem_rhs (tree t)
 112 {
 113   /* If we're dealing with a renamable type, either source or dest must be
 114      a renamed variable.  Also force a temporary if the type doesn't need
 115      to be stored in memory, since it's cheap and prevents erroneous
 116      tailcalls (PR 17526).  */
 117   if (is_gimple_reg_type (TREE_TYPE (t))
 118       || (TYPE_MODE (TREE_TYPE (t)) != BLKmode
 119           && (TREE_CODE (t) != CALL_EXPR
 120               || ! aggregate_value_p (t, t))))
 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 a GIMPLE minimal invariant.  It's a restricted
 169    form of function invariant.  */
 170
 171 bool
 172 is_gimple_min_invariant (const_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     /* Vector constant constructors are gimple invariant.  */
 187     case CONSTRUCTOR:
 188       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 189         return TREE_CONSTANT (t);
 190       else
 191         return false;
 192
 193     default:
 194       return false;
 195     }
 196 }
 197
 198 /* Return true if T looks like a valid GIMPLE statement.  */
 199
 200 bool
 201 is_gimple_stmt (tree t)
 202 {
 203   enum tree_code code = TREE_CODE (t);
 204
 205   switch (code)
 206     {
 207     case NOP_EXPR:
 208       /* The only valid NOP_EXPR is the empty statement.  */
 209       return IS_EMPTY_STMT (t);
 210
 211     case BIND_EXPR:
 212     case COND_EXPR:
 213       /* These are only valid if they're void.  */
 214       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 215
 216     case SWITCH_EXPR:
 217     case GOTO_EXPR:
 218     case RETURN_EXPR:
 219     case LABEL_EXPR:
 220     case CASE_LABEL_EXPR:
 221     case TRY_CATCH_EXPR:
 222     case TRY_FINALLY_EXPR:
 223     case EH_FILTER_EXPR:
 224     case CATCH_EXPR:
 225     case CHANGE_DYNAMIC_TYPE_EXPR:
 226     case ASM_EXPR:
 227     case RESX_EXPR:
 228     case PHI_NODE:
 229     case STATEMENT_LIST:
 230     case OMP_PARALLEL:
 231     case OMP_FOR:
 232     case OMP_SECTIONS:
 233     case OMP_SECTION:
 234     case OMP_SINGLE:
 235     case OMP_MASTER:
 236     case OMP_ORDERED:
 237     case OMP_CRITICAL:
 238     case OMP_RETURN:
 239     case OMP_CONTINUE:
 240       /* These are always void.  */
 241       return true;
 242
 243     case CALL_EXPR:
 244     case GIMPLE_MODIFY_STMT:
 245       /* These are valid regardless of their type.  */
 246       return true;
 247
 248     default:
 249       return false;
 250     }
 251 }
 252
 253 /* Return true if T is a variable.  */
 254
 255 bool
 256 is_gimple_variable (tree t)
 257 {
 258   return (TREE_CODE (t) == VAR_DECL
 259           || TREE_CODE (t) == PARM_DECL
 260           || TREE_CODE (t) == RESULT_DECL
 261           || TREE_CODE (t) == SSA_NAME);
 262 }
 263
 264 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 265
 266 bool
 267 is_gimple_id (tree t)
 268 {
 269   return (is_gimple_variable (t)
 270           || TREE_CODE (t) == FUNCTION_DECL
 271           || TREE_CODE (t) == LABEL_DECL
 272           || TREE_CODE (t) == CONST_DECL
 273           /* Allow string constants, since they are addressable.  */
 274           || TREE_CODE (t) == STRING_CST);
 275 }
 276
 277 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 278
 279 bool
 280 is_gimple_reg_type (tree type)
 281 {
 282   return !AGGREGATE_TYPE_P (type);
 283 }
 284
 285 /* Return true if T is a non-aggregate register variable.  */
 286
 287 bool
 288 is_gimple_reg (tree t)
 289 {
 290   if (TREE_CODE (t) == SSA_NAME)
 291     t = SSA_NAME_VAR (t);
 292
 293   if (MTAG_P (t))
 294     return false;
 295
 296   if (!is_gimple_variable (t))
 297     return false;
 298
 299   if (!is_gimple_reg_type (TREE_TYPE (t)))
 300     return false;
 301
 302   /* A volatile decl is not acceptable because we can't reuse it as
 303      needed.  We need to copy it into a temp first.  */
 304   if (TREE_THIS_VOLATILE (t))
 305     return false;
 306
 307   /* We define "registers" as things that can be renamed as needed,
 308      which with our infrastructure does not apply to memory.  */
 309   if (needs_to_live_in_memory (t))
 310     return false;
 311
 312   /* Hard register variables are an interesting case.  For those that
 313      are call-clobbered, we don't know where all the calls are, since
 314      we don't (want to) take into account which operations will turn
 315      into libcalls at the rtl level.  For those that are call-saved,
 316      we don't currently model the fact that calls may in fact change
 317      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 318      level, and so miss variable changes that might imply.  All around,
 319      it seems safest to not do too much optimization with these at the
 320      tree level at all.  We'll have to rely on the rtl optimizers to
 321      clean this up, as there we've got all the appropriate bits exposed.  */
 322   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 323     return false;
 324
 325   /* Complex values must have been put into ssa form.  That is, no
 326      assignments to the individual components.  */
 327   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 328       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 329     return DECL_GIMPLE_REG_P (t);
 330
 331   return true;
 332 }
 333
 334
 335 /* Returns true if T is a GIMPLE formal temporary variable.  */
 336
 337 bool
 338 is_gimple_formal_tmp_var (tree t)
 339 {
 340   if (TREE_CODE (t) == SSA_NAME)
 341     return true;
 342
 343   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 344 }
 345
 346 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 347
 348 bool
 349 is_gimple_formal_tmp_reg (tree t)
 350 {
 351   /* The intent of this is to get hold of a value that won't change.
 352      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 353   if (TREE_CODE (t) == SSA_NAME)
 354     return true;
 355
 356   /* We don't know the lifetime characteristics of user variables.  */
 357   if (!is_gimple_formal_tmp_var (t))
 358     return false;
 359
 360   /* Finally, it must be capable of being placed in a register.  */
 361   return is_gimple_reg (t);
 362 }
 363
 364 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 365
 366 bool
 367 is_gimple_non_addressable (tree t)
 368 {
 369   if (TREE_CODE (t) == SSA_NAME)
 370     t = SSA_NAME_VAR (t);
 371
 372   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 373 }
 374
 375 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 376
 377 bool
 378 is_gimple_val (tree t)
 379 {
 380   /* Make loads from volatiles and memory vars explicit.  */
 381   if (is_gimple_variable (t)
 382       && is_gimple_reg_type (TREE_TYPE (t))
 383       && !is_gimple_reg (t))
 384     return false;
 385
 386   /* FIXME make these decls.  That can happen only when we expose the
 387      entire landing-pad construct at the tree level.  */
 388   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 389     return true;
 390
 391   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 392 }
 393
 394 /* Similarly, but accept hard registers as inputs to asm statements.  */
 395
 396 bool
 397 is_gimple_asm_val (tree t)
 398 {
 399   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 400     return true;
 401
 402   return is_gimple_val (t);
 403 }
 404
 405 /* Return true if T is a GIMPLE minimal lvalue.  */
 406
 407 bool
 408 is_gimple_min_lval (tree t)
 409 {
 410   return (is_gimple_id (t)
 411           || TREE_CODE (t) == INDIRECT_REF);
 412 }
 413
 414 /* Return true if T is a typecast operation.  */
 415
 416 bool
 417 is_gimple_cast (tree t)
 418 {
 419   return (TREE_CODE (t) == NOP_EXPR
 420           || TREE_CODE (t) == CONVERT_EXPR
 421           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 422 }
 423
 424 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 425
 426 bool
 427 is_gimple_call_addr (tree t)
 428 {
 429   return (TREE_CODE (t) == OBJ_TYPE_REF
 430           || is_gimple_val (t));
 431 }
 432
 433 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 434    Otherwise, return NULL_TREE.  */
 435
 436 tree
 437 get_call_expr_in (tree t)
 438 {
 439   /* FIXME tuples: delete the assertion below when conversion complete.  */
 440   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 441   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 442     t = GIMPLE_STMT_OPERAND (t, 1);
 443   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 444     t = TREE_OPERAND (t, 0);
 445   if (TREE_CODE (t) == CALL_EXPR)
 446     return t;
 447   return NULL_TREE;
 448 }
 449
 450 /* Given a memory reference expression T, return its base address.
 451    The base address of a memory reference expression is the main
 452    object being referenced.  For instance, the base address for
 453    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 454    away the offset part from a memory address.
 455
 456    This function calls handled_component_p to strip away all the inner
 457    parts of the memory reference until it reaches the base object.  */
 458
 459 tree
 460 get_base_address (tree t)
 461 {
 462   while (handled_component_p (t))
 463     t = TREE_OPERAND (t, 0);
 464
 465   if (SSA_VAR_P (t)
 466       || TREE_CODE (t) == STRING_CST
 467       || TREE_CODE (t) == CONSTRUCTOR
 468       || INDIRECT_REF_P (t))
 469     return t;
 470   else
 471     return NULL_TREE;
 472 }
 473
 474 void
 475 recalculate_side_effects (tree t)
 476 {
 477   enum tree_code code = TREE_CODE (t);
 478   int len = TREE_OPERAND_LENGTH (t);
 479   int i;
 480
 481   switch (TREE_CODE_CLASS (code))
 482     {
 483     case tcc_expression:
 484       switch (code)
 485         {
 486         case INIT_EXPR:
 487         case GIMPLE_MODIFY_STMT:
 488         case VA_ARG_EXPR:
 489         case PREDECREMENT_EXPR:
 490         case PREINCREMENT_EXPR:
 491         case POSTDECREMENT_EXPR:
 492         case POSTINCREMENT_EXPR:
 493           /* All of these have side-effects, no matter what their
 494              operands are.  */
 495           return;
 496
 497         default:
 498           break;
 499         }
 500       /* Fall through.  */
 501
 502     case tcc_comparison:  /* a comparison expression */
 503     case tcc_unary:       /* a unary arithmetic expression */
 504     case tcc_binary:      /* a binary arithmetic expression */
 505     case tcc_reference:   /* a reference */
 506     case tcc_vl_exp:        /* a function call */
 507       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 508       for (i = 0; i < len; ++i)
 509         {
 510           tree op = TREE_OPERAND (t, i);
 511           if (op && TREE_SIDE_EFFECTS (op))
 512             TREE_SIDE_EFFECTS (t) = 1;
 513         }
 514       break;
 515
 516     default:
 517       /* Can never be used with non-expressions.  */
 518       gcc_unreachable ();
 519    }
 520 }