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