gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5    Rewritten by Jason Merrill <jason@redhat.com>
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 3, or (at your option)
  12 any later version.
  13
  14 GCC is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  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 FIXED_CST:
  71     case STRING_CST:
  72     case COMPLEX_CST:
  73     case VECTOR_CST:
  74     case OBJ_TYPE_REF:
  75     case ASSERT_EXPR:
  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 GIMPLE_MODIFY_STMT 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 VDEF 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           && (TREE_CODE (t) != CALL_EXPR
 121               || ! aggregate_value_p (t, t))))
 122     return is_gimple_val (t);
 123   else
 124     return is_gimple_formal_tmp_rhs (t);
 125 }
 126
 127 /* Returns the appropriate RHS predicate for this LHS.  */
 128
 129 gimple_predicate
 130 rhs_predicate_for (tree lhs)
 131 {
 132   if (is_gimple_formal_tmp_var (lhs))
 133     return is_gimple_formal_tmp_rhs;
 134   else if (is_gimple_reg (lhs))
 135     return is_gimple_reg_rhs;
 136   else
 137     return is_gimple_mem_rhs;
 138 }
 139
 140 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 141
 142 bool
 143 is_gimple_lvalue (tree t)
 144 {
 145   return (is_gimple_addressable (t)
 146           || TREE_CODE (t) == WITH_SIZE_EXPR
 147           /* These are complex lvalues, but don't have addresses, so they
 148              go here.  */
 149           || TREE_CODE (t) == BIT_FIELD_REF);
 150 }
 151
 152 /*  Return true if T is a GIMPLE condition.  */
 153
 154 bool
 155 is_gimple_condexpr (tree t)
 156 {
 157   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 158 }
 159
 160 /*  Return true if T is something whose address can be taken.  */
 161
 162 bool
 163 is_gimple_addressable (tree t)
 164 {
 165   return (is_gimple_id (t) || handled_component_p (t)
 166           || INDIRECT_REF_P (t));
 167 }
 168
 169 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
 170    form of function invariant.  */
 171
 172 bool
 173 is_gimple_min_invariant (const_tree t)
 174 {
 175   switch (TREE_CODE (t))
 176     {
 177     case ADDR_EXPR:
 178       return TREE_INVARIANT (t);
 179
 180     case INTEGER_CST:
 181     case REAL_CST:
 182     case FIXED_CST:
 183     case STRING_CST:
 184     case COMPLEX_CST:
 185     case VECTOR_CST:
 186       return true;
 187
 188     /* Vector constant constructors are gimple invariant.  */
 189     case CONSTRUCTOR:
 190       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 191         return TREE_CONSTANT (t);
 192       else
 193         return false;
 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   const enum tree_code code = TREE_CODE (t);
 206
 207   switch (code)
 208     {
 209     case NOP_EXPR:
 210       /* The only valid NOP_EXPR is the empty statement.  */
 211       return IS_EMPTY_STMT (t);
 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 CHANGE_DYNAMIC_TYPE_EXPR:
 228     case ASM_EXPR:
 229     case RESX_EXPR:
 230     case PHI_NODE:
 231     case STATEMENT_LIST:
 232     case OMP_PARALLEL:
 233     case OMP_FOR:
 234     case OMP_SECTIONS:
 235     case OMP_SECTIONS_SWITCH:
 236     case OMP_SECTION:
 237     case OMP_SINGLE:
 238     case OMP_MASTER:
 239     case OMP_ORDERED:
 240     case OMP_CRITICAL:
 241     case OMP_RETURN:
 242     case OMP_CONTINUE:
 243     case OMP_ATOMIC_LOAD:
 244     case OMP_ATOMIC_STORE:
 245       /* These are always void.  */
 246       return true;
 247
 248     case CALL_EXPR:
 249     case GIMPLE_MODIFY_STMT:
 250       /* These are valid regardless of their type.  */
 251       return true;
 252
 253     default:
 254       return false;
 255     }
 256 }
 257
 258 /* Return true if T is a variable.  */
 259
 260 bool
 261 is_gimple_variable (tree t)
 262 {
 263   return (TREE_CODE (t) == VAR_DECL
 264           || TREE_CODE (t) == PARM_DECL
 265           || TREE_CODE (t) == RESULT_DECL
 266           || TREE_CODE (t) == SSA_NAME);
 267 }
 268
 269 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 270
 271 bool
 272 is_gimple_id (tree t)
 273 {
 274   return (is_gimple_variable (t)
 275           || TREE_CODE (t) == FUNCTION_DECL
 276           || TREE_CODE (t) == LABEL_DECL
 277           || TREE_CODE (t) == CONST_DECL
 278           /* Allow string constants, since they are addressable.  */
 279           || TREE_CODE (t) == STRING_CST);
 280 }
 281
 282 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 283
 284 bool
 285 is_gimple_reg_type (tree type)
 286 {
 287   return !AGGREGATE_TYPE_P (type);
 288 }
 289
 290 /* Return true if T is a non-aggregate register variable.  */
 291
 292 bool
 293 is_gimple_reg (tree t)
 294 {
 295   if (TREE_CODE (t) == SSA_NAME)
 296     t = SSA_NAME_VAR (t);
 297
 298   if (MTAG_P (t))
 299     return false;
 300
 301   if (!is_gimple_variable (t))
 302     return false;
 303
 304   if (!is_gimple_reg_type (TREE_TYPE (t)))
 305     return false;
 306
 307   /* A volatile decl is not acceptable because we can't reuse it as
 308      needed.  We need to copy it into a temp first.  */
 309   if (TREE_THIS_VOLATILE (t))
 310     return false;
 311
 312   /* We define "registers" as things that can be renamed as needed,
 313      which with our infrastructure does not apply to memory.  */
 314   if (needs_to_live_in_memory (t))
 315     return false;
 316
 317   /* Hard register variables are an interesting case.  For those that
 318      are call-clobbered, we don't know where all the calls are, since
 319      we don't (want to) take into account which operations will turn
 320      into libcalls at the rtl level.  For those that are call-saved,
 321      we don't currently model the fact that calls may in fact change
 322      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 323      level, and so miss variable changes that might imply.  All around,
 324      it seems safest to not do too much optimization with these at the
 325      tree level at all.  We'll have to rely on the rtl optimizers to
 326      clean this up, as there we've got all the appropriate bits exposed.  */
 327   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 328     return false;
 329
 330   /* Complex values must have been put into ssa form.  That is, no
 331      assignments to the individual components.  */
 332   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 333       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 334     return DECL_GIMPLE_REG_P (t);
 335
 336   return true;
 337 }
 338
 339
 340 /* Returns true if T is a GIMPLE formal temporary variable.  */
 341
 342 bool
 343 is_gimple_formal_tmp_var (tree t)
 344 {
 345   if (TREE_CODE (t) == SSA_NAME)
 346     return true;
 347
 348   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 349 }
 350
 351 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 352
 353 bool
 354 is_gimple_formal_tmp_reg (tree t)
 355 {
 356   /* The intent of this is to get hold of a value that won't change.
 357      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 358   if (TREE_CODE (t) == SSA_NAME)
 359     return true;
 360
 361   /* We don't know the lifetime characteristics of user variables.  */
 362   if (!is_gimple_formal_tmp_var (t))
 363     return false;
 364
 365   /* Finally, it must be capable of being placed in a register.  */
 366   return is_gimple_reg (t);
 367 }
 368
 369 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 370
 371 bool
 372 is_gimple_non_addressable (tree t)
 373 {
 374   if (TREE_CODE (t) == SSA_NAME)
 375     t = SSA_NAME_VAR (t);
 376
 377   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 378 }
 379
 380 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 381
 382 bool
 383 is_gimple_val (tree t)
 384 {
 385   /* Make loads from volatiles and memory vars explicit.  */
 386   if (is_gimple_variable (t)
 387       && is_gimple_reg_type (TREE_TYPE (t))
 388       && !is_gimple_reg (t))
 389     return false;
 390
 391   /* FIXME make these decls.  That can happen only when we expose the
 392      entire landing-pad construct at the tree level.  */
 393   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 394     return true;
 395
 396   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 397 }
 398
 399 /* Similarly, but accept hard registers as inputs to asm statements.  */
 400
 401 bool
 402 is_gimple_asm_val (tree t)
 403 {
 404   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 405     return true;
 406
 407   return is_gimple_val (t);
 408 }
 409
 410 /* Return true if T is a GIMPLE minimal lvalue.  */
 411
 412 bool
 413 is_gimple_min_lval (tree t)
 414 {
 415   return (is_gimple_id (t)
 416           || TREE_CODE (t) == INDIRECT_REF);
 417 }
 418
 419 /* Return true if T is a typecast operation.  */
 420
 421 bool
 422 is_gimple_cast (tree t)
 423 {
 424   return (TREE_CODE (t) == NOP_EXPR
 425           || TREE_CODE (t) == CONVERT_EXPR
 426           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 427 }
 428
 429 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 430
 431 bool
 432 is_gimple_call_addr (tree t)
 433 {
 434   return (TREE_CODE (t) == OBJ_TYPE_REF
 435           || is_gimple_val (t));
 436 }
 437
 438 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 439    Otherwise, return NULL_TREE.  */
 440
 441 tree
 442 get_call_expr_in (tree t)
 443 {
 444   /* FIXME tuples: delete the assertion below when conversion complete.  */
 445   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 446   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 447     t = GIMPLE_STMT_OPERAND (t, 1);
 448   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 449     t = TREE_OPERAND (t, 0);
 450   if (TREE_CODE (t) == CALL_EXPR)
 451     return t;
 452   return NULL_TREE;
 453 }
 454
 455 /* Given a memory reference expression T, return its base address.
 456    The base address of a memory reference expression is the main
 457    object being referenced.  For instance, the base address for
 458    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 459    away the offset part from a memory address.
 460
 461    This function calls handled_component_p to strip away all the inner
 462    parts of the memory reference until it reaches the base object.  */
 463
 464 tree
 465 get_base_address (tree t)
 466 {
 467   while (handled_component_p (t))
 468     t = TREE_OPERAND (t, 0);
 469
 470   if (SSA_VAR_P (t)
 471       || TREE_CODE (t) == STRING_CST
 472       || TREE_CODE (t) == CONSTRUCTOR
 473       || INDIRECT_REF_P (t))
 474     return t;
 475   else
 476     return NULL_TREE;
 477 }
 478
 479 void
 480 recalculate_side_effects (tree t)
 481 {
 482   enum tree_code code = TREE_CODE (t);
 483   int len = TREE_OPERAND_LENGTH (t);
 484   int i;
 485
 486   switch (TREE_CODE_CLASS (code))
 487     {
 488     case tcc_expression:
 489       switch (code)
 490         {
 491         case INIT_EXPR:
 492         case GIMPLE_MODIFY_STMT:
 493         case VA_ARG_EXPR:
 494         case PREDECREMENT_EXPR:
 495         case PREINCREMENT_EXPR:
 496         case POSTDECREMENT_EXPR:
 497         case POSTINCREMENT_EXPR:
 498           /* All of these have side-effects, no matter what their
 499              operands are.  */
 500           return;
 501
 502         default:
 503           break;
 504         }
 505       /* Fall through.  */
 506
 507     case tcc_comparison:  /* a comparison expression */
 508     case tcc_unary:       /* a unary arithmetic expression */
 509     case tcc_binary:      /* a binary arithmetic expression */
 510     case tcc_reference:   /* a reference */
 511     case tcc_vl_exp:        /* a function call */
 512       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 513       for (i = 0; i < len; ++i)
 514         {
 515           tree op = TREE_OPERAND (t, i);
 516           if (op && TREE_SIDE_EFFECTS (op))
 517             TREE_SIDE_EFFECTS (t) = 1;
 518         }
 519       break;
 520
 521     default:
 522       /* Can never be used with non-expressions.  */
 523       gcc_unreachable ();
 524    }
 525 }
 526
 527 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
 528    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
 529    we failed to create one.  */
 530
 531 tree
 532 canonicalize_cond_expr_cond (tree t)
 533 {
 534   /* For (bool)x use x != 0.  */
 535   if (TREE_CODE (t) == NOP_EXPR
 536       && TREE_TYPE (t) == boolean_type_node)
 537     {
 538       tree top0 = TREE_OPERAND (t, 0);
 539       t = build2 (NE_EXPR, TREE_TYPE (t),
 540                   top0, build_int_cst (TREE_TYPE (top0), 0));
 541     }
 542   /* For !x use x == 0.  */
 543   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
 544     {
 545       tree top0 = TREE_OPERAND (t, 0);
 546       t = build2 (EQ_EXPR, TREE_TYPE (t),
 547                   top0, build_int_cst (TREE_TYPE (top0), 0));
 548     }
 549   /* For cmp ? 1 : 0 use cmp.  */
 550   else if (TREE_CODE (t) == COND_EXPR
 551            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
 552            && integer_onep (TREE_OPERAND (t, 1))
 553            && integer_zerop (TREE_OPERAND (t, 2)))
 554     {
 555       tree top0 = TREE_OPERAND (t, 0);
 556       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
 557                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
 558     }
 559
 560   /* A valid conditional for a COND_EXPR is either a gimple value
 561      or a comparison with two gimple value operands.  */
 562   if (is_gimple_val (t)
 563       || (COMPARISON_CLASS_P (t)
 564           && is_gimple_val (TREE_OPERAND (t, 0))
 565           && is_gimple_val (TREE_OPERAND (t, 1))))
 566     return t;
 567
 568   return NULL_TREE;
 569 }