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           || TREE_CODE (t) == INDIRECT_REF
 174           || TREE_CODE (t) == ALIGN_INDIRECT_REF
 175           || TREE_CODE (t) == MISALIGNED_INDIRECT_REF);
 176 }
 177
 178 /* Return true if T is function invariant.  Or rather a restricted
 179    form of function invariant.  */
 180
 181 bool
 182 is_gimple_min_invariant (tree t)
 183 {
 184   switch (TREE_CODE (t))
 185     {
 186     case ADDR_EXPR:
 187       return TREE_INVARIANT (t);
 188
 189     case INTEGER_CST:
 190     case REAL_CST:
 191     case STRING_CST:
 192     case COMPLEX_CST:
 193     case VECTOR_CST:
 194       return !TREE_OVERFLOW (t);
 195
 196     default:
 197       return false;
 198     }
 199 }
 200
 201 /* Return true if T looks like a valid GIMPLE statement.  */
 202
 203 bool
 204 is_gimple_stmt (tree t)
 205 {
 206   enum tree_code code = TREE_CODE (t);
 207
 208   if (IS_EMPTY_STMT (t))
 209     return 1;
 210
 211   switch (code)
 212     {
 213     case BIND_EXPR:
 214     case COND_EXPR:
 215       /* These are only valid if they're void.  */
 216       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 217
 218     case SWITCH_EXPR:
 219     case GOTO_EXPR:
 220     case RETURN_EXPR:
 221     case LABEL_EXPR:
 222     case CASE_LABEL_EXPR:
 223     case TRY_CATCH_EXPR:
 224     case TRY_FINALLY_EXPR:
 225     case EH_FILTER_EXPR:
 226     case CATCH_EXPR:
 227     case ASM_EXPR:
 228     case RESX_EXPR:
 229     case PHI_NODE:
 230     case STATEMENT_LIST:
 231       /* These are always void.  */
 232       return true;
 233
 234     case CALL_EXPR:
 235     case MODIFY_EXPR:
 236       /* These are valid regardless of their type.  */
 237       return true;
 238
 239     default:
 240       return false;
 241     }
 242 }
 243
 244 /* Return true if T is a variable.  */
 245
 246 bool
 247 is_gimple_variable (tree t)
 248 {
 249   return (TREE_CODE (t) == VAR_DECL
 250           || TREE_CODE (t) == PARM_DECL
 251           || TREE_CODE (t) == RESULT_DECL
 252           || TREE_CODE (t) == SSA_NAME);
 253 }
 254
 255 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 256
 257 static inline bool
 258 is_gimple_id (tree t)
 259 {
 260   return (is_gimple_variable (t)
 261           || TREE_CODE (t) == FUNCTION_DECL
 262           || TREE_CODE (t) == LABEL_DECL
 263           || TREE_CODE (t) == CONST_DECL
 264           /* Allow string constants, since they are addressable.  */
 265           || TREE_CODE (t) == STRING_CST);
 266 }
 267
 268 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 269
 270 bool
 271 is_gimple_reg_type (tree type)
 272 {
 273   return (!AGGREGATE_TYPE_P (type)
 274           && TREE_CODE (type) != COMPLEX_TYPE);
 275 }
 276
 277
 278 /* Return true if T is a scalar register variable.  */
 279
 280 bool
 281 is_gimple_reg (tree t)
 282 {
 283   if (TREE_CODE (t) == SSA_NAME)
 284     t = SSA_NAME_VAR (t);
 285
 286   return (is_gimple_variable (t)
 287           && is_gimple_reg_type (TREE_TYPE (t))
 288           /* A volatile decl is not acceptable because we can't reuse it as
 289              needed.  We need to copy it into a temp first.  */
 290           && ! TREE_THIS_VOLATILE (t)
 291           && ! needs_to_live_in_memory (t));
 292 }
 293
 294 /* Returns true if T is a GIMPLE formal temporary variable.  */
 295
 296 bool
 297 is_gimple_formal_tmp_var (tree t)
 298 {
 299   if (TREE_CODE (t) == SSA_NAME)
 300     return true;
 301
 302   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 303 }
 304
 305 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 306
 307 bool
 308 is_gimple_formal_tmp_reg (tree t)
 309 {
 310   /* The intent of this is to get hold of a value that won't change.
 311      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 312   if (TREE_CODE (t) == SSA_NAME)
 313     return true;
 314
 315   /* We don't know the lifetime characteristics of user variables.  */
 316   if (!is_gimple_formal_tmp_var (t))
 317     return false;
 318
 319   /* Finally, it must be capable of being placed in a register.  */
 320   return is_gimple_reg (t);
 321 }
 322
 323 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 324
 325 bool
 326 is_gimple_non_addressable (tree t)
 327 {
 328   if (TREE_CODE (t) == SSA_NAME)
 329     t = SSA_NAME_VAR (t);
 330
 331   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 332 }
 333
 334 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 335
 336 bool
 337 is_gimple_val (tree t)
 338 {
 339   /* Make loads from volatiles and memory vars explicit.  */
 340   if (is_gimple_variable (t)
 341       && is_gimple_reg_type (TREE_TYPE (t))
 342       && !is_gimple_reg (t))
 343     return false;
 344
 345   /* FIXME make these decls.  That can happen only when we expose the
 346      entire landing-pad construct at the tree level.  */
 347   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 348     return 1;
 349
 350   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 351 }
 352
 353
 354 /* Return true if T is a GIMPLE minimal lvalue.  */
 355
 356 bool
 357 is_gimple_min_lval (tree t)
 358 {
 359   return (is_gimple_id (t)
 360           || TREE_CODE (t) == INDIRECT_REF);
 361 }
 362
 363 /* Return true if T is a typecast operation.  */
 364
 365 bool
 366 is_gimple_cast (tree t)
 367 {
 368   return (TREE_CODE (t) == NOP_EXPR
 369           || TREE_CODE (t) == CONVERT_EXPR
 370           || TREE_CODE (t) == FIX_TRUNC_EXPR
 371           || TREE_CODE (t) == FIX_CEIL_EXPR
 372           || TREE_CODE (t) == FIX_FLOOR_EXPR
 373           || TREE_CODE (t) == FIX_ROUND_EXPR);
 374 }
 375
 376 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 377
 378 bool
 379 is_gimple_call_addr (tree t)
 380 {
 381   return (TREE_CODE (t) == OBJ_TYPE_REF
 382           || is_gimple_val (t));
 383 }
 384
 385 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 386    Otherwise, return NULL_TREE.  */
 387
 388 tree
 389 get_call_expr_in (tree t)
 390 {
 391   if (TREE_CODE (t) == MODIFY_EXPR)
 392     t = TREE_OPERAND (t, 1);
 393   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 394     t = TREE_OPERAND (t, 0);
 395   if (TREE_CODE (t) == CALL_EXPR)
 396     return t;
 397   return NULL_TREE;
 398 }
 399
 400 /* Given a memory reference expression, return the base address.  Note that,
 401    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 402    expressions.  Therefore, given the reference PTR->FIELD, this function
 403    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 404
 405 tree
 406 get_base_address (tree t)
 407 {
 408   while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
 409          || handled_component_p (t))
 410     t = TREE_OPERAND (t, 0);
 411
 412   if (SSA_VAR_P (t)
 413       || TREE_CODE (t) == STRING_CST
 414       || TREE_CODE (t) == CONSTRUCTOR
 415       || TREE_CODE (t) == MISALIGNED_INDIRECT_REF
 416       || TREE_CODE (t) == ALIGN_INDIRECT_REF
 417       || TREE_CODE (t) == INDIRECT_REF)
 418     return t;
 419   else
 420     return NULL_TREE;
 421 }
 422
 423 void
 424 recalculate_side_effects (tree t)
 425 {
 426   enum tree_code code = TREE_CODE (t);
 427   int fro = first_rtl_op (code);
 428   int i;
 429
 430   switch (TREE_CODE_CLASS (code))
 431     {
 432     case tcc_expression:
 433       switch (code)
 434         {
 435         case INIT_EXPR:
 436         case MODIFY_EXPR:
 437         case VA_ARG_EXPR:
 438         case PREDECREMENT_EXPR:
 439         case PREINCREMENT_EXPR:
 440         case POSTDECREMENT_EXPR:
 441         case POSTINCREMENT_EXPR:
 442           /* All of these have side-effects, no matter what their
 443              operands are.  */
 444           return;
 445
 446         default:
 447           break;
 448         }
 449       /* Fall through.  */
 450
 451     case tcc_comparison:  /* a comparison expression */
 452     case tcc_unary:       /* a unary arithmetic expression */
 453     case tcc_binary:      /* a binary arithmetic expression */
 454     case tcc_reference:   /* a reference */
 455       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 456       for (i = 0; i < fro; ++i)
 457         {
 458           tree op = TREE_OPERAND (t, i);
 459           if (op && TREE_SIDE_EFFECTS (op))
 460             TREE_SIDE_EFFECTS (t) = 1;
 461         }
 462       break;
 463
 464     default:
 465       /* Can never be used with non-expressions.  */
 466       gcc_unreachable ();
 467    }
 468 }