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       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 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   switch (code)
 199     {
 200     case NOP_EXPR:
 201       /* The only valid NOP_EXPR is the empty statement.  */
 202       return IS_EMPTY_STMT (t);
 203
 204     case BIND_EXPR:
 205     case COND_EXPR:
 206       /* These are only valid if they're void.  */
 207       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 208
 209     case SWITCH_EXPR:
 210     case GOTO_EXPR:
 211     case RETURN_EXPR:
 212     case LABEL_EXPR:
 213     case CASE_LABEL_EXPR:
 214     case TRY_CATCH_EXPR:
 215     case TRY_FINALLY_EXPR:
 216     case EH_FILTER_EXPR:
 217     case CATCH_EXPR:
 218     case ASM_EXPR:
 219     case RESX_EXPR:
 220     case PHI_NODE:
 221     case STATEMENT_LIST:
 222     case OMP_PARALLEL:
 223     case OMP_FOR:
 224     case OMP_SECTIONS:
 225     case OMP_SECTION:
 226     case OMP_SINGLE:
 227     case OMP_MASTER:
 228     case OMP_ORDERED:
 229     case OMP_CRITICAL:
 230     case OMP_RETURN:
 231     case OMP_CONTINUE:
 232       /* These are always void.  */
 233       return true;
 234
 235     case CALL_EXPR:
 236     case GIMPLE_MODIFY_STMT:
 237       /* These are valid regardless of their type.  */
 238       return true;
 239
 240     default:
 241       return false;
 242     }
 243 }
 244
 245 /* Return true if T is a variable.  */
 246
 247 bool
 248 is_gimple_variable (tree t)
 249 {
 250   return (TREE_CODE (t) == VAR_DECL
 251           || TREE_CODE (t) == PARM_DECL
 252           || TREE_CODE (t) == RESULT_DECL
 253           || TREE_CODE (t) == SSA_NAME);
 254 }
 255
 256 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 257
 258 bool
 259 is_gimple_id (tree t)
 260 {
 261   return (is_gimple_variable (t)
 262           || TREE_CODE (t) == FUNCTION_DECL
 263           || TREE_CODE (t) == LABEL_DECL
 264           || TREE_CODE (t) == CONST_DECL
 265           /* Allow string constants, since they are addressable.  */
 266           || TREE_CODE (t) == STRING_CST);
 267 }
 268
 269 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 270
 271 bool
 272 is_gimple_reg_type (tree type)
 273 {
 274   return !AGGREGATE_TYPE_P (type);
 275 }
 276
 277 /* Return true if T is a non-aggregate register variable.  */
 278
 279 bool
 280 is_gimple_reg (tree t)
 281 {
 282   if (TREE_CODE (t) == SSA_NAME)
 283     t = SSA_NAME_VAR (t);
 284
 285   if (MTAG_P (t))
 286     return false;
 287
 288   if (!is_gimple_variable (t))
 289     return false;
 290
 291   if (!is_gimple_reg_type (TREE_TYPE (t)))
 292     return false;
 293
 294   /* A volatile decl is not acceptable because we can't reuse it as
 295      needed.  We need to copy it into a temp first.  */
 296   if (TREE_THIS_VOLATILE (t))
 297     return false;
 298
 299   /* We define "registers" as things that can be renamed as needed,
 300      which with our infrastructure does not apply to memory.  */
 301   if (needs_to_live_in_memory (t))
 302     return false;
 303
 304   /* Hard register variables are an interesting case.  For those that
 305      are call-clobbered, we don't know where all the calls are, since
 306      we don't (want to) take into account which operations will turn
 307      into libcalls at the rtl level.  For those that are call-saved,
 308      we don't currently model the fact that calls may in fact change
 309      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 310      level, and so miss variable changes that might imply.  All around,
 311      it seems safest to not do too much optimization with these at the
 312      tree level at all.  We'll have to rely on the rtl optimizers to
 313      clean this up, as there we've got all the appropriate bits exposed.  */
 314   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 315     return false;
 316
 317   /* Complex values must have been put into ssa form.  That is, no
 318      assignments to the individual components.  */
 319   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 320       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 321     return DECL_GIMPLE_REG_P (t);
 322
 323   return true;
 324 }
 325
 326
 327 /* Returns true if T is a GIMPLE formal temporary variable.  */
 328
 329 bool
 330 is_gimple_formal_tmp_var (tree t)
 331 {
 332   if (TREE_CODE (t) == SSA_NAME)
 333     return true;
 334
 335   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 336 }
 337
 338 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 339
 340 bool
 341 is_gimple_formal_tmp_reg (tree t)
 342 {
 343   /* The intent of this is to get hold of a value that won't change.
 344      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 345   if (TREE_CODE (t) == SSA_NAME)
 346     return true;
 347
 348   /* We don't know the lifetime characteristics of user variables.  */
 349   if (!is_gimple_formal_tmp_var (t))
 350     return false;
 351
 352   /* Finally, it must be capable of being placed in a register.  */
 353   return is_gimple_reg (t);
 354 }
 355
 356 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 357
 358 bool
 359 is_gimple_non_addressable (tree t)
 360 {
 361   if (TREE_CODE (t) == SSA_NAME)
 362     t = SSA_NAME_VAR (t);
 363
 364   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 365 }
 366
 367 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 368
 369 bool
 370 is_gimple_val (tree t)
 371 {
 372   /* Make loads from volatiles and memory vars explicit.  */
 373   if (is_gimple_variable (t)
 374       && is_gimple_reg_type (TREE_TYPE (t))
 375       && !is_gimple_reg (t))
 376     return false;
 377
 378   /* FIXME make these decls.  That can happen only when we expose the
 379      entire landing-pad construct at the tree level.  */
 380   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 381     return true;
 382
 383   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 384 }
 385
 386 /* Similarly, but accept hard registers as inputs to asm statements.  */
 387
 388 bool
 389 is_gimple_asm_val (tree t)
 390 {
 391   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 392     return true;
 393
 394   return is_gimple_val (t);
 395 }
 396
 397 /* Return true if T is a GIMPLE minimal lvalue.  */
 398
 399 bool
 400 is_gimple_min_lval (tree t)
 401 {
 402   return (is_gimple_id (t)
 403           || TREE_CODE (t) == INDIRECT_REF);
 404 }
 405
 406 /* Return true if T is a typecast operation.  */
 407
 408 bool
 409 is_gimple_cast (tree t)
 410 {
 411   return (TREE_CODE (t) == NOP_EXPR
 412           || TREE_CODE (t) == CONVERT_EXPR
 413           || TREE_CODE (t) == FIX_TRUNC_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   /* FIXME tuples: delete the assertion below when conversion complete.  */
 432   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 433   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 434     t = GIMPLE_STMT_OPERAND (t, 1);
 435   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 436     t = TREE_OPERAND (t, 0);
 437   if (TREE_CODE (t) == CALL_EXPR)
 438     return t;
 439   return NULL_TREE;
 440 }
 441
 442 /* Given a memory reference expression T, return its base address.
 443    The base address of a memory reference expression is the main
 444    object being referenced.  For instance, the base address for
 445    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 446    away the offset part from a memory address.
 447
 448    This function calls handled_component_p to strip away all the inner
 449    parts of the memory reference until it reaches the base object.  */
 450
 451 tree
 452 get_base_address (tree t)
 453 {
 454   while (handled_component_p (t))
 455     t = TREE_OPERAND (t, 0);
 456
 457   if (SSA_VAR_P (t)
 458       || TREE_CODE (t) == STRING_CST
 459       || TREE_CODE (t) == CONSTRUCTOR
 460       || INDIRECT_REF_P (t))
 461     return t;
 462   else
 463     return NULL_TREE;
 464 }
 465
 466 void
 467 recalculate_side_effects (tree t)
 468 {
 469   enum tree_code code = TREE_CODE (t);
 470   int len = TREE_CODE_LENGTH (code);
 471   int i;
 472
 473   switch (TREE_CODE_CLASS (code))
 474     {
 475     case tcc_expression:
 476       switch (code)
 477         {
 478         case INIT_EXPR:
 479         case GIMPLE_MODIFY_STMT:
 480         case VA_ARG_EXPR:
 481         case PREDECREMENT_EXPR:
 482         case PREINCREMENT_EXPR:
 483         case POSTDECREMENT_EXPR:
 484         case POSTINCREMENT_EXPR:
 485           /* All of these have side-effects, no matter what their
 486              operands are.  */
 487           return;
 488
 489         default:
 490           break;
 491         }
 492       /* Fall through.  */
 493
 494     case tcc_comparison:  /* a comparison expression */
 495     case tcc_unary:       /* a unary arithmetic expression */
 496     case tcc_binary:      /* a binary arithmetic expression */
 497     case tcc_reference:   /* a reference */
 498       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 499       for (i = 0; i < len; ++i)
 500         {
 501           tree op = TREE_OPERAND (t, i);
 502           if (op && TREE_SIDE_EFFECTS (op))
 503             TREE_SIDE_EFFECTS (t) = 1;
 504         }
 505       break;
 506
 507     default:
 508       /* Can never be used with non-expressions.  */
 509       gcc_unreachable ();
 510    }
 511 }