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