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