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