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