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