gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2007 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 3, 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 COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "ggc.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "tree-gimple.h"
  29 #include "tree-flow.h"
  30 #include "output.h"
  31 #include "rtl.h"
  32 #include "expr.h"
  33 #include "bitmap.h"
  34
  35 /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi.  */
  36
  37 /* Validation of GIMPLE expressions.  */
  38
  39 /* Return true if T is a GIMPLE RHS for an assignment to a temporary.  */
  40
  41 bool
  42 is_gimple_formal_tmp_rhs (tree t)
  43 {
  44   enum tree_code code = TREE_CODE (t);
  45
  46   switch (TREE_CODE_CLASS (code))
  47     {
  48     case tcc_unary:
  49     case tcc_binary:
  50     case tcc_comparison:
  51       return true;
  52
  53     default:
  54       break;
  55     }
  56
  57   switch (code)
  58     {
  59     case TRUTH_NOT_EXPR:
  60     case TRUTH_AND_EXPR:
  61     case TRUTH_OR_EXPR:
  62     case TRUTH_XOR_EXPR:
  63     case ADDR_EXPR:
  64     case CALL_EXPR:
  65     case CONSTRUCTOR:
  66     case COMPLEX_EXPR:
  67     case INTEGER_CST:
  68     case REAL_CST:
  69     case STRING_CST:
  70     case COMPLEX_CST:
  71     case VECTOR_CST:
  72     case OBJ_TYPE_REF:
  73     case ASSERT_EXPR:
  74       return true;
  75
  76     default:
  77       break;
  78     }
  79
  80   return is_gimple_lvalue (t) || is_gimple_val (t);
  81 }
  82
  83 /* Returns true iff T is a valid RHS for an assignment to a renamed
  84    user -- or front-end generated artificial -- variable.  */
  85
  86 bool
  87 is_gimple_reg_rhs (tree t)
  88 {
  89   /* If the RHS of the MODIFY_EXPR may throw or make a nonlocal goto
  90      and the LHS is a user variable, then we need to introduce a formal
  91      temporary.  This way the optimizers can determine that the user
  92      variable is only modified if evaluation of the RHS does not throw.
  93
  94      Don't force a temp of a non-renamable type; the copy could be
  95      arbitrarily expensive.  Instead we will generate a V_MAY_DEF for
  96      the assignment.  */
  97
  98   if (is_gimple_reg_type (TREE_TYPE (t))
  99       && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t))
 100           || tree_could_throw_p (t)))
 101     return false;
 102
 103   return is_gimple_formal_tmp_rhs (t);
 104 }
 105
 106 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 107    LHS, or for a call argument.  */
 108
 109 bool
 110 is_gimple_mem_rhs (tree t)
 111 {
 112   /* If we're dealing with a renamable type, either source or dest must be
 113      a renamed variable.  Also force a temporary if the type doesn't need
 114      to be stored in memory, since it's cheap and prevents erroneous
 115      tailcalls (PR 17526).  */
 116   if (is_gimple_reg_type (TREE_TYPE (t))
 117       || (TYPE_MODE (TREE_TYPE (t)) != BLKmode
 118           && (TREE_CODE (t) != CALL_EXPR
 119               || ! aggregate_value_p (t, t))))
 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   switch (code)
 198     {
 199     case NOP_EXPR:
 200       /* The only valid NOP_EXPR is the empty statement.  */
 201       return IS_EMPTY_STMT (t);
 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     case OMP_PARALLEL:
 222     case OMP_FOR:
 223     case OMP_SECTIONS:
 224     case OMP_SECTION:
 225     case OMP_SINGLE:
 226     case OMP_MASTER:
 227     case OMP_ORDERED:
 228     case OMP_CRITICAL:
 229     case OMP_RETURN:
 230     case OMP_CONTINUE:
 231       /* These are always void.  */
 232       return true;
 233
 234     case CALL_EXPR:
 235     case MODIFY_EXPR:
 236       /* These are valid regardless of their type.  */
 237       return true;
 238
 239     default:
 240       return false;
 241     }
 242 }
 243
 244 /* Return true if T is a variable.  */
 245
 246 bool
 247 is_gimple_variable (tree t)
 248 {
 249   return (TREE_CODE (t) == VAR_DECL
 250           || TREE_CODE (t) == PARM_DECL
 251           || TREE_CODE (t) == RESULT_DECL
 252           || TREE_CODE (t) == SSA_NAME);
 253 }
 254
 255 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 256
 257 bool
 258 is_gimple_id (tree t)
 259 {
 260   return (is_gimple_variable (t)
 261           || TREE_CODE (t) == FUNCTION_DECL
 262           || TREE_CODE (t) == LABEL_DECL
 263           || TREE_CODE (t) == CONST_DECL
 264           /* Allow string constants, since they are addressable.  */
 265           || TREE_CODE (t) == STRING_CST);
 266 }
 267
 268 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 269
 270 bool
 271 is_gimple_reg_type (tree type)
 272 {
 273   return !AGGREGATE_TYPE_P (type);
 274 }
 275
 276 /* Return true if T is a non-aggregate register variable.  */
 277
 278 bool
 279 is_gimple_reg (tree t)
 280 {
 281   if (TREE_CODE (t) == SSA_NAME)
 282     t = SSA_NAME_VAR (t);
 283
 284   if (MTAG_P (t))
 285     return false;
 286
 287   if (!is_gimple_variable (t))
 288     return false;
 289
 290   if (!is_gimple_reg_type (TREE_TYPE (t)))
 291     return false;
 292
 293   /* A volatile decl is not acceptable because we can't reuse it as
 294      needed.  We need to copy it into a temp first.  */
 295   if (TREE_THIS_VOLATILE (t))
 296     return false;
 297
 298   /* We define "registers" as things that can be renamed as needed,
 299      which with our infrastructure does not apply to memory.  */
 300   if (needs_to_live_in_memory (t))
 301     return false;
 302
 303   /* Hard register variables are an interesting case.  For those that
 304      are call-clobbered, we don't know where all the calls are, since
 305      we don't (want to) take into account which operations will turn
 306      into libcalls at the rtl level.  For those that are call-saved,
 307      we don't currently model the fact that calls may in fact change
 308      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 309      level, and so miss variable changes that might imply.  All around,
 310      it seems safest to not do too much optimization with these at the
 311      tree level at all.  We'll have to rely on the rtl optimizers to
 312      clean this up, as there we've got all the appropriate bits exposed.  */
 313   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 314     return false;
 315
 316   /* Complex values must have been put into ssa form.  That is, no
 317      assignments to the individual components.  */
 318   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE)
 319     return DECL_COMPLEX_GIMPLE_REG_P (t);
 320
 321   return true;
 322 }
 323
 324
 325 /* Returns true if T is a GIMPLE formal temporary variable.  */
 326
 327 bool
 328 is_gimple_formal_tmp_var (tree t)
 329 {
 330   if (TREE_CODE (t) == SSA_NAME)
 331     return true;
 332
 333   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 334 }
 335
 336 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 337
 338 bool
 339 is_gimple_formal_tmp_reg (tree t)
 340 {
 341   /* The intent of this is to get hold of a value that won't change.
 342      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 343   if (TREE_CODE (t) == SSA_NAME)
 344     return true;
 345
 346   /* We don't know the lifetime characteristics of user variables.  */
 347   if (!is_gimple_formal_tmp_var (t))
 348     return false;
 349
 350   /* Finally, it must be capable of being placed in a register.  */
 351   return is_gimple_reg (t);
 352 }
 353
 354 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 355
 356 bool
 357 is_gimple_non_addressable (tree t)
 358 {
 359   if (TREE_CODE (t) == SSA_NAME)
 360     t = SSA_NAME_VAR (t);
 361
 362   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 363 }
 364
 365 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 366
 367 bool
 368 is_gimple_val (tree t)
 369 {
 370   /* Make loads from volatiles and memory vars explicit.  */
 371   if (is_gimple_variable (t)
 372       && is_gimple_reg_type (TREE_TYPE (t))
 373       && !is_gimple_reg (t))
 374     return false;
 375
 376   /* FIXME make these decls.  That can happen only when we expose the
 377      entire landing-pad construct at the tree level.  */
 378   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 379     return 1;
 380
 381   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 382 }
 383
 384 /* Similarly, but accept hard registers as inputs to asm statements.  */
 385
 386 bool
 387 is_gimple_asm_val (tree t)
 388 {
 389   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 390     return true;
 391
 392   return is_gimple_val (t);
 393 }
 394
 395 /* Return true if T is a GIMPLE minimal lvalue.  */
 396
 397 bool
 398 is_gimple_min_lval (tree t)
 399 {
 400   return (is_gimple_id (t)
 401           || TREE_CODE (t) == INDIRECT_REF);
 402 }
 403
 404 /* Return true if T is a typecast operation.  */
 405
 406 bool
 407 is_gimple_cast (tree t)
 408 {
 409   return (TREE_CODE (t) == NOP_EXPR
 410           || TREE_CODE (t) == CONVERT_EXPR
 411           || TREE_CODE (t) == FIX_TRUNC_EXPR
 412           || TREE_CODE (t) == FIX_CEIL_EXPR
 413           || TREE_CODE (t) == FIX_FLOOR_EXPR
 414           || TREE_CODE (t) == FIX_ROUND_EXPR);
 415 }
 416
 417 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 418
 419 bool
 420 is_gimple_call_addr (tree t)
 421 {
 422   return (TREE_CODE (t) == OBJ_TYPE_REF
 423           || is_gimple_val (t));
 424 }
 425
 426 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 427    Otherwise, return NULL_TREE.  */
 428
 429 tree
 430 get_call_expr_in (tree t)
 431 {
 432   if (TREE_CODE (t) == MODIFY_EXPR)
 433     t = TREE_OPERAND (t, 1);
 434   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 435     t = TREE_OPERAND (t, 0);
 436   if (TREE_CODE (t) == CALL_EXPR)
 437     return t;
 438   return NULL_TREE;
 439 }
 440
 441 /* Given a memory reference expression T, return its base address.
 442    The base address of a memory reference expression is the main
 443    object being referenced.  For instance, the base address for
 444    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 445    away the offset part from a memory address.
 446
 447    This function calls handled_component_p to strip away all the inner
 448    parts of the memory reference until it reaches the base object.  */
 449
 450 tree
 451 get_base_address (tree t)
 452 {
 453   while (handled_component_p (t))
 454     t = TREE_OPERAND (t, 0);
 455
 456   if (SSA_VAR_P (t)
 457       || TREE_CODE (t) == STRING_CST
 458       || TREE_CODE (t) == CONSTRUCTOR
 459       || INDIRECT_REF_P (t))
 460     return t;
 461   else
 462     return NULL_TREE;
 463 }
 464
 465 void
 466 recalculate_side_effects (tree t)
 467 {
 468   enum tree_code code = TREE_CODE (t);
 469   int len = TREE_CODE_LENGTH (code);
 470   int i;
 471
 472   switch (TREE_CODE_CLASS (code))
 473     {
 474     case tcc_expression:
 475       switch (code)
 476         {
 477         case INIT_EXPR:
 478         case MODIFY_EXPR:
 479         case VA_ARG_EXPR:
 480         case PREDECREMENT_EXPR:
 481         case PREINCREMENT_EXPR:
 482         case POSTDECREMENT_EXPR:
 483         case POSTINCREMENT_EXPR:
 484           /* All of these have side-effects, no matter what their
 485              operands are.  */
 486           return;
 487
 488         default:
 489           break;
 490         }
 491       /* Fall through.  */
 492
 493     case tcc_comparison:  /* a comparison expression */
 494     case tcc_unary:       /* a unary arithmetic expression */
 495     case tcc_binary:      /* a binary arithmetic expression */
 496     case tcc_reference:   /* a reference */
 497       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 498       for (i = 0; i < len; ++i)
 499         {
 500           tree op = TREE_OPERAND (t, i);
 501           if (op && TREE_SIDE_EFFECTS (op))
 502             TREE_SIDE_EFFECTS (t) = 1;
 503         }
 504       break;
 505
 506     default:
 507       /* Can never be used with non-expressions.  */
 508       gcc_unreachable ();
 509    }
 510 }