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   if (!is_gimple_variable (t))
 286     return false;
 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   return true;
 314 }
 315
 316 /* Returns true if T is a GIMPLE formal temporary variable.  */
 317
 318 bool
 319 is_gimple_formal_tmp_var (tree t)
 320 {
 321   if (TREE_CODE (t) == SSA_NAME)
 322     return true;
 323
 324   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 325 }
 326
 327 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 328
 329 bool
 330 is_gimple_formal_tmp_reg (tree t)
 331 {
 332   /* The intent of this is to get hold of a value that won't change.
 333      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 334   if (TREE_CODE (t) == SSA_NAME)
 335     return true;
 336
 337   /* We don't know the lifetime characteristics of user variables.  */
 338   if (!is_gimple_formal_tmp_var (t))
 339     return false;
 340
 341   /* Finally, it must be capable of being placed in a register.  */
 342   return is_gimple_reg (t);
 343 }
 344
 345 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 346
 347 bool
 348 is_gimple_non_addressable (tree t)
 349 {
 350   if (TREE_CODE (t) == SSA_NAME)
 351     t = SSA_NAME_VAR (t);
 352
 353   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 354 }
 355
 356 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 357
 358 bool
 359 is_gimple_val (tree t)
 360 {
 361   /* Make loads from volatiles and memory vars explicit.  */
 362   if (is_gimple_variable (t)
 363       && is_gimple_reg_type (TREE_TYPE (t))
 364       && !is_gimple_reg (t))
 365     return false;
 366
 367   /* FIXME make these decls.  That can happen only when we expose the
 368      entire landing-pad construct at the tree level.  */
 369   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 370     return 1;
 371
 372   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 373 }
 374
 375 /* Similarly, but accept hard registers as inputs to asm statements.  */
 376
 377 bool
 378 is_gimple_asm_val (tree t)
 379 {
 380   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 381     return true;
 382
 383   return is_gimple_val (t);
 384 }
 385
 386 /* Return true if T is a GIMPLE minimal lvalue.  */
 387
 388 bool
 389 is_gimple_min_lval (tree t)
 390 {
 391   return (is_gimple_id (t)
 392           || TREE_CODE (t) == INDIRECT_REF);
 393 }
 394
 395 /* Return true if T is a typecast operation.  */
 396
 397 bool
 398 is_gimple_cast (tree t)
 399 {
 400   return (TREE_CODE (t) == NOP_EXPR
 401           || TREE_CODE (t) == CONVERT_EXPR
 402           || TREE_CODE (t) == FIX_TRUNC_EXPR
 403           || TREE_CODE (t) == FIX_CEIL_EXPR
 404           || TREE_CODE (t) == FIX_FLOOR_EXPR
 405           || TREE_CODE (t) == FIX_ROUND_EXPR);
 406 }
 407
 408 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 409
 410 bool
 411 is_gimple_call_addr (tree t)
 412 {
 413   return (TREE_CODE (t) == OBJ_TYPE_REF
 414           || is_gimple_val (t));
 415 }
 416
 417 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 418    Otherwise, return NULL_TREE.  */
 419
 420 tree
 421 get_call_expr_in (tree t)
 422 {
 423   if (TREE_CODE (t) == MODIFY_EXPR)
 424     t = TREE_OPERAND (t, 1);
 425   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 426     t = TREE_OPERAND (t, 0);
 427   if (TREE_CODE (t) == CALL_EXPR)
 428     return t;
 429   return NULL_TREE;
 430 }
 431
 432 /* Given a memory reference expression, return the base address.  Note that,
 433    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 434    expressions.  Therefore, given the reference PTR->FIELD, this function
 435    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 436
 437 tree
 438 get_base_address (tree t)
 439 {
 440   while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
 441          || handled_component_p (t))
 442     t = TREE_OPERAND (t, 0);
 443
 444   if (SSA_VAR_P (t)
 445       || TREE_CODE (t) == STRING_CST
 446       || TREE_CODE (t) == CONSTRUCTOR
 447       || INDIRECT_REF_P (t))
 448     return t;
 449   else
 450     return NULL_TREE;
 451 }
 452
 453 void
 454 recalculate_side_effects (tree t)
 455 {
 456   enum tree_code code = TREE_CODE (t);
 457   int fro = first_rtl_op (code);
 458   int i;
 459
 460   switch (TREE_CODE_CLASS (code))
 461     {
 462     case tcc_expression:
 463       switch (code)
 464         {
 465         case INIT_EXPR:
 466         case MODIFY_EXPR:
 467         case VA_ARG_EXPR:
 468         case PREDECREMENT_EXPR:
 469         case PREINCREMENT_EXPR:
 470         case POSTDECREMENT_EXPR:
 471         case POSTINCREMENT_EXPR:
 472           /* All of these have side-effects, no matter what their
 473              operands are.  */
 474           return;
 475
 476         default:
 477           break;
 478         }
 479       /* Fall through.  */
 480
 481     case tcc_comparison:  /* a comparison expression */
 482     case tcc_unary:       /* a unary arithmetic expression */
 483     case tcc_binary:      /* a binary arithmetic expression */
 484     case tcc_reference:   /* a reference */
 485       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 486       for (i = 0; i < fro; ++i)
 487         {
 488           tree op = TREE_OPERAND (t, i);
 489           if (op && TREE_SIDE_EFFECTS (op))
 490             TREE_SIDE_EFFECTS (t) = 1;
 491         }
 492       break;
 493
 494     default:
 495       /* Can never be used with non-expressions.  */
 496       gcc_unreachable ();
 497    }
 498 }