gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003, 2004 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, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, 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 static inline bool is_gimple_id (tree);
  39
  40 /* Validation of GIMPLE expressions.  */
  41
  42 /* Return true if T is a GIMPLE RHS for an assignment to a temporary.  */
  43
  44 bool
  45 is_gimple_formal_tmp_rhs (tree t)
  46 {
  47   enum tree_code code = TREE_CODE (t);
  48
  49   switch (TREE_CODE_CLASS (code))
  50     {
  51     case tcc_unary:
  52     case tcc_binary:
  53     case tcc_comparison:
  54       return true;
  55
  56     default:
  57       break;
  58     }
  59
  60   switch (code)
  61     {
  62     case TRUTH_NOT_EXPR:
  63     case TRUTH_AND_EXPR:
  64     case TRUTH_OR_EXPR:
  65     case TRUTH_XOR_EXPR:
  66     case ADDR_EXPR:
  67     case CALL_EXPR:
  68     case CONSTRUCTOR:
  69     case COMPLEX_EXPR:
  70     case INTEGER_CST:
  71     case REAL_CST:
  72     case STRING_CST:
  73     case COMPLEX_CST:
  74     case VECTOR_CST:
  75     case OBJ_TYPE_REF:
  76       return true;
  77
  78     default:
  79       break;
  80     }
  81
  82   return is_gimple_lvalue (t) || is_gimple_val (t);
  83 }
  84
  85 /* Returns true iff T is a valid RHS for an assignment to a renamed
  86    user -- or front-end generated artificial -- variable.  */
  87
  88 bool
  89 is_gimple_reg_rhs (tree t)
  90 {
  91   /* If the RHS of the MODIFY_EXPR may throw or make a nonlocal goto
  92      and the LHS is a user variable, then we need to introduce a formal
  93      temporary.  This way the optimizers can determine that the user
  94      variable is only modified if evaluation of the RHS does not throw.
  95
  96      Don't force a temp of a non-renamable type; the copy could be
  97      arbitrarily expensive.  Instead we will generate a V_MAY_DEF for
  98      the assignment.  */
  99
 100   if (is_gimple_reg_type (TREE_TYPE (t))
 101       && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t))
 102           || tree_could_throw_p (t)))
 103     return false;
 104
 105   return is_gimple_formal_tmp_rhs (t);
 106 }
 107
 108 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 109    LHS, or for a call argument.  */
 110
 111 bool
 112 is_gimple_mem_rhs (tree t)
 113 {
 114   /* If we're dealing with a renamable type, either source or dest
 115      must be a renamed variable.  */
 116   if (is_gimple_reg_type (TREE_TYPE (t)))
 117     return is_gimple_val (t);
 118   else
 119     return is_gimple_formal_tmp_rhs (t);
 120 }
 121
 122 /* Returns the appropriate RHS predicate for this LHS.  */
 123
 124 gimple_predicate
 125 rhs_predicate_for (tree lhs)
 126 {
 127   if (is_gimple_formal_tmp_var (lhs))
 128     return is_gimple_formal_tmp_rhs;
 129   else if (is_gimple_reg (lhs))
 130     return is_gimple_reg_rhs;
 131   else
 132     return is_gimple_mem_rhs;
 133 }
 134
 135 /* Returns true if T is a valid CONSTRUCTOR component in GIMPLE, either
 136    a val or another CONSTRUCTOR.  */
 137
 138 bool
 139 is_gimple_constructor_elt (tree t)
 140 {
 141   return (is_gimple_val (t)
 142           || TREE_CODE (t) == CONSTRUCTOR);
 143 }
 144
 145 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 146
 147 bool
 148 is_gimple_lvalue (tree t)
 149 {
 150   return (is_gimple_addressable (t)
 151           || TREE_CODE (t) == WITH_SIZE_EXPR
 152           /* These are complex lvalues, but don't have addresses, so they
 153              go here.  */
 154           || TREE_CODE (t) == BIT_FIELD_REF);
 155 }
 156
 157 /*  Return true if T is a GIMPLE condition.  */
 158
 159 bool
 160 is_gimple_condexpr (tree t)
 161 {
 162   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 163 }
 164
 165 /*  Return true if T is something whose address can be taken.  */
 166
 167 bool
 168 is_gimple_addressable (tree t)
 169 {
 170   return (is_gimple_id (t) || handled_component_p (t)
 171           || TREE_CODE (t) == REALPART_EXPR
 172           || TREE_CODE (t) == IMAGPART_EXPR
 173           || INDIRECT_REF_P (t));
 174
 175 }
 176
 177 /* Return true if T is function invariant.  Or rather a restricted
 178    form of function invariant.  */
 179
 180 bool
 181 is_gimple_min_invariant (tree t)
 182 {
 183   switch (TREE_CODE (t))
 184     {
 185     case ADDR_EXPR:
 186       return TREE_INVARIANT (t);
 187
 188     case INTEGER_CST:
 189     case REAL_CST:
 190     case STRING_CST:
 191     case COMPLEX_CST:
 192     case VECTOR_CST:
 193       return !TREE_OVERFLOW (t);
 194
 195     default:
 196       return false;
 197     }
 198 }
 199
 200 /* Return true if T looks like a valid GIMPLE statement.  */
 201
 202 bool
 203 is_gimple_stmt (tree t)
 204 {
 205   enum tree_code code = TREE_CODE (t);
 206
 207   if (IS_EMPTY_STMT (t))
 208     return 1;
 209
 210   switch (code)
 211     {
 212     case BIND_EXPR:
 213     case COND_EXPR:
 214       /* These are only valid if they're void.  */
 215       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 216
 217     case SWITCH_EXPR:
 218     case GOTO_EXPR:
 219     case RETURN_EXPR:
 220     case LABEL_EXPR:
 221     case CASE_LABEL_EXPR:
 222     case TRY_CATCH_EXPR:
 223     case TRY_FINALLY_EXPR:
 224     case EH_FILTER_EXPR:
 225     case CATCH_EXPR:
 226     case ASM_EXPR:
 227     case RESX_EXPR:
 228     case PHI_NODE:
 229     case STATEMENT_LIST:
 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 static inline 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           && TREE_CODE (type) != COMPLEX_TYPE);
 274 }
 275
 276
 277 /* Return true if T is a scalar 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   return (is_gimple_variable (t)
 286           && is_gimple_reg_type (TREE_TYPE (t))
 287           /* A volatile decl is not acceptable because we can't reuse it as
 288              needed.  We need to copy it into a temp first.  */
 289           && ! TREE_THIS_VOLATILE (t)
 290           && ! needs_to_live_in_memory (t));
 291 }
 292
 293 /* Returns true if T is a GIMPLE formal temporary variable.  */
 294
 295 bool
 296 is_gimple_formal_tmp_var (tree t)
 297 {
 298   if (TREE_CODE (t) == SSA_NAME)
 299     return true;
 300
 301   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 302 }
 303
 304 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 305
 306 bool
 307 is_gimple_formal_tmp_reg (tree t)
 308 {
 309   /* The intent of this is to get hold of a value that won't change.
 310      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 311   if (TREE_CODE (t) == SSA_NAME)
 312     return true;
 313
 314   /* We don't know the lifetime characteristics of user variables.  */
 315   if (!is_gimple_formal_tmp_var (t))
 316     return false;
 317
 318   /* Finally, it must be capable of being placed in a register.  */
 319   return is_gimple_reg (t);
 320 }
 321
 322 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 323
 324 bool
 325 is_gimple_non_addressable (tree t)
 326 {
 327   if (TREE_CODE (t) == SSA_NAME)
 328     t = SSA_NAME_VAR (t);
 329
 330   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 331 }
 332
 333 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 334
 335 bool
 336 is_gimple_val (tree t)
 337 {
 338   /* Make loads from volatiles and memory vars explicit.  */
 339   if (is_gimple_variable (t)
 340       && is_gimple_reg_type (TREE_TYPE (t))
 341       && !is_gimple_reg (t))
 342     return false;
 343
 344   /* FIXME make these decls.  That can happen only when we expose the
 345      entire landing-pad construct at the tree level.  */
 346   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 347     return 1;
 348
 349   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 350 }
 351
 352
 353 /* Return true if T is a GIMPLE minimal lvalue.  */
 354
 355 bool
 356 is_gimple_min_lval (tree t)
 357 {
 358   return (is_gimple_id (t)
 359           || TREE_CODE (t) == INDIRECT_REF);
 360 }
 361
 362 /* Return true if T is a typecast operation.  */
 363
 364 bool
 365 is_gimple_cast (tree t)
 366 {
 367   return (TREE_CODE (t) == NOP_EXPR
 368           || TREE_CODE (t) == CONVERT_EXPR
 369           || TREE_CODE (t) == FIX_TRUNC_EXPR
 370           || TREE_CODE (t) == FIX_CEIL_EXPR
 371           || TREE_CODE (t) == FIX_FLOOR_EXPR
 372           || TREE_CODE (t) == FIX_ROUND_EXPR);
 373 }
 374
 375 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 376
 377 bool
 378 is_gimple_call_addr (tree t)
 379 {
 380   return (TREE_CODE (t) == OBJ_TYPE_REF
 381           || is_gimple_val (t));
 382 }
 383
 384 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 385    Otherwise, return NULL_TREE.  */
 386
 387 tree
 388 get_call_expr_in (tree t)
 389 {
 390   if (TREE_CODE (t) == MODIFY_EXPR)
 391     t = TREE_OPERAND (t, 1);
 392   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 393     t = TREE_OPERAND (t, 0);
 394   if (TREE_CODE (t) == CALL_EXPR)
 395     return t;
 396   return NULL_TREE;
 397 }
 398
 399 /* Given a memory reference expression, return the base address.  Note that,
 400    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 401    expressions.  Therefore, given the reference PTR->FIELD, this function
 402    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 403
 404 tree
 405 get_base_address (tree t)
 406 {
 407   while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
 408          || handled_component_p (t))
 409     t = TREE_OPERAND (t, 0);
 410
 411   if (SSA_VAR_P (t)
 412       || TREE_CODE (t) == STRING_CST
 413       || TREE_CODE (t) == CONSTRUCTOR
 414       || INDIRECT_REF_P (t))
 415     return t;
 416   else
 417     return NULL_TREE;
 418 }
 419
 420 void
 421 recalculate_side_effects (tree t)
 422 {
 423   enum tree_code code = TREE_CODE (t);
 424   int fro = first_rtl_op (code);
 425   int i;
 426
 427   switch (TREE_CODE_CLASS (code))
 428     {
 429     case tcc_expression:
 430       switch (code)
 431         {
 432         case INIT_EXPR:
 433         case MODIFY_EXPR:
 434         case VA_ARG_EXPR:
 435         case PREDECREMENT_EXPR:
 436         case PREINCREMENT_EXPR:
 437         case POSTDECREMENT_EXPR:
 438         case POSTINCREMENT_EXPR:
 439           /* All of these have side-effects, no matter what their
 440              operands are.  */
 441           return;
 442
 443         default:
 444           break;
 445         }
 446       /* Fall through.  */
 447
 448     case tcc_comparison:  /* a comparison expression */
 449     case tcc_unary:       /* a unary arithmetic expression */
 450     case tcc_binary:      /* a binary arithmetic expression */
 451     case tcc_reference:   /* a reference */
 452       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 453       for (i = 0; i < fro; ++i)
 454         {
 455           tree op = TREE_OPERAND (t, i);
 456           if (op && TREE_SIDE_EFFECTS (op))
 457             TREE_SIDE_EFFECTS (t) = 1;
 458         }
 459       break;
 460
 461     default:
 462       /* Can never be used with non-expressions.  */
 463       gcc_unreachable ();
 464    }
 465 }