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       /* These are always void.  */
 244       return true;
 245
 246     case CALL_EXPR:
 247     case GIMPLE_MODIFY_STMT:
 248       /* These are valid regardless of their type.  */
 249       return true;
 250
 251     default:
 252       return false;
 253     }
 254 }
 255
 256 /* Return true if T is a variable.  */
 257
 258 bool
 259 is_gimple_variable (tree t)
 260 {
 261   return (TREE_CODE (t) == VAR_DECL
 262           || TREE_CODE (t) == PARM_DECL
 263           || TREE_CODE (t) == RESULT_DECL
 264           || TREE_CODE (t) == SSA_NAME);
 265 }
 266
 267 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 268
 269 bool
 270 is_gimple_id (tree t)
 271 {
 272   return (is_gimple_variable (t)
 273           || TREE_CODE (t) == FUNCTION_DECL
 274           || TREE_CODE (t) == LABEL_DECL
 275           || TREE_CODE (t) == CONST_DECL
 276           /* Allow string constants, since they are addressable.  */
 277           || TREE_CODE (t) == STRING_CST);
 278 }
 279
 280 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 281
 282 bool
 283 is_gimple_reg_type (tree type)
 284 {
 285   return !AGGREGATE_TYPE_P (type);
 286 }
 287
 288 /* Return true if T is a non-aggregate register variable.  */
 289
 290 bool
 291 is_gimple_reg (tree t)
 292 {
 293   if (TREE_CODE (t) == SSA_NAME)
 294     t = SSA_NAME_VAR (t);
 295
 296   if (MTAG_P (t))
 297     return false;
 298
 299   if (!is_gimple_variable (t))
 300     return false;
 301
 302   if (!is_gimple_reg_type (TREE_TYPE (t)))
 303     return false;
 304
 305   /* A volatile decl is not acceptable because we can't reuse it as
 306      needed.  We need to copy it into a temp first.  */
 307   if (TREE_THIS_VOLATILE (t))
 308     return false;
 309
 310   /* We define "registers" as things that can be renamed as needed,
 311      which with our infrastructure does not apply to memory.  */
 312   if (needs_to_live_in_memory (t))
 313     return false;
 314
 315   /* Hard register variables are an interesting case.  For those that
 316      are call-clobbered, we don't know where all the calls are, since
 317      we don't (want to) take into account which operations will turn
 318      into libcalls at the rtl level.  For those that are call-saved,
 319      we don't currently model the fact that calls may in fact change
 320      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 321      level, and so miss variable changes that might imply.  All around,
 322      it seems safest to not do too much optimization with these at the
 323      tree level at all.  We'll have to rely on the rtl optimizers to
 324      clean this up, as there we've got all the appropriate bits exposed.  */
 325   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 326     return false;
 327
 328   /* Complex values must have been put into ssa form.  That is, no
 329      assignments to the individual components.  */
 330   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 331       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 332     return DECL_GIMPLE_REG_P (t);
 333
 334   return true;
 335 }
 336
 337
 338 /* Returns true if T is a GIMPLE formal temporary variable.  */
 339
 340 bool
 341 is_gimple_formal_tmp_var (tree t)
 342 {
 343   if (TREE_CODE (t) == SSA_NAME)
 344     return true;
 345
 346   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 347 }
 348
 349 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 350
 351 bool
 352 is_gimple_formal_tmp_reg (tree t)
 353 {
 354   /* The intent of this is to get hold of a value that won't change.
 355      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 356   if (TREE_CODE (t) == SSA_NAME)
 357     return true;
 358
 359   /* We don't know the lifetime characteristics of user variables.  */
 360   if (!is_gimple_formal_tmp_var (t))
 361     return false;
 362
 363   /* Finally, it must be capable of being placed in a register.  */
 364   return is_gimple_reg (t);
 365 }
 366
 367 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 368
 369 bool
 370 is_gimple_non_addressable (tree t)
 371 {
 372   if (TREE_CODE (t) == SSA_NAME)
 373     t = SSA_NAME_VAR (t);
 374
 375   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 376 }
 377
 378 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 379
 380 bool
 381 is_gimple_val (tree t)
 382 {
 383   /* Make loads from volatiles and memory vars explicit.  */
 384   if (is_gimple_variable (t)
 385       && is_gimple_reg_type (TREE_TYPE (t))
 386       && !is_gimple_reg (t))
 387     return false;
 388
 389   /* FIXME make these decls.  That can happen only when we expose the
 390      entire landing-pad construct at the tree level.  */
 391   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 392     return true;
 393
 394   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 395 }
 396
 397 /* Similarly, but accept hard registers as inputs to asm statements.  */
 398
 399 bool
 400 is_gimple_asm_val (tree t)
 401 {
 402   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 403     return true;
 404
 405   return is_gimple_val (t);
 406 }
 407
 408 /* Return true if T is a GIMPLE minimal lvalue.  */
 409
 410 bool
 411 is_gimple_min_lval (tree t)
 412 {
 413   return (is_gimple_id (t)
 414           || TREE_CODE (t) == INDIRECT_REF);
 415 }
 416
 417 /* Return true if T is a typecast operation.  */
 418
 419 bool
 420 is_gimple_cast (tree t)
 421 {
 422   return (TREE_CODE (t) == NOP_EXPR
 423           || TREE_CODE (t) == CONVERT_EXPR
 424           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 425 }
 426
 427 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 428
 429 bool
 430 is_gimple_call_addr (tree t)
 431 {
 432   return (TREE_CODE (t) == OBJ_TYPE_REF
 433           || is_gimple_val (t));
 434 }
 435
 436 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 437    Otherwise, return NULL_TREE.  */
 438
 439 tree
 440 get_call_expr_in (tree t)
 441 {
 442   /* FIXME tuples: delete the assertion below when conversion complete.  */
 443   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 444   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 445     t = GIMPLE_STMT_OPERAND (t, 1);
 446   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 447     t = TREE_OPERAND (t, 0);
 448   if (TREE_CODE (t) == CALL_EXPR)
 449     return t;
 450   return NULL_TREE;
 451 }
 452
 453 /* Given a memory reference expression T, return its base address.
 454    The base address of a memory reference expression is the main
 455    object being referenced.  For instance, the base address for
 456    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 457    away the offset part from a memory address.
 458
 459    This function calls handled_component_p to strip away all the inner
 460    parts of the memory reference until it reaches the base object.  */
 461
 462 tree
 463 get_base_address (tree t)
 464 {
 465   while (handled_component_p (t))
 466     t = TREE_OPERAND (t, 0);
 467
 468   if (SSA_VAR_P (t)
 469       || TREE_CODE (t) == STRING_CST
 470       || TREE_CODE (t) == CONSTRUCTOR
 471       || INDIRECT_REF_P (t))
 472     return t;
 473   else
 474     return NULL_TREE;
 475 }
 476
 477 void
 478 recalculate_side_effects (tree t)
 479 {
 480   enum tree_code code = TREE_CODE (t);
 481   int len = TREE_OPERAND_LENGTH (t);
 482   int i;
 483
 484   switch (TREE_CODE_CLASS (code))
 485     {
 486     case tcc_expression:
 487       switch (code)
 488         {
 489         case INIT_EXPR:
 490         case GIMPLE_MODIFY_STMT:
 491         case VA_ARG_EXPR:
 492         case PREDECREMENT_EXPR:
 493         case PREINCREMENT_EXPR:
 494         case POSTDECREMENT_EXPR:
 495         case POSTINCREMENT_EXPR:
 496           /* All of these have side-effects, no matter what their
 497              operands are.  */
 498           return;
 499
 500         default:
 501           break;
 502         }
 503       /* Fall through.  */
 504
 505     case tcc_comparison:  /* a comparison expression */
 506     case tcc_unary:       /* a unary arithmetic expression */
 507     case tcc_binary:      /* a binary arithmetic expression */
 508     case tcc_reference:   /* a reference */
 509     case tcc_vl_exp:        /* a function call */
 510       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 511       for (i = 0; i < len; ++i)
 512         {
 513           tree op = TREE_OPERAND (t, i);
 514           if (op && TREE_SIDE_EFFECTS (op))
 515             TREE_SIDE_EFFECTS (t) = 1;
 516         }
 517       break;
 518
 519     default:
 520       /* Can never be used with non-expressions.  */
 521       gcc_unreachable ();
 522    }
 523 }
 524
 525 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
 526    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
 527    we failed to create one.  */
 528
 529 tree
 530 canonicalize_cond_expr_cond (tree t)
 531 {
 532   /* For (bool)x use x != 0.  */
 533   if (TREE_CODE (t) == NOP_EXPR
 534       && TREE_TYPE (t) == boolean_type_node)
 535     {
 536       tree top0 = TREE_OPERAND (t, 0);
 537       t = build2 (NE_EXPR, TREE_TYPE (t),
 538                   top0, build_int_cst (TREE_TYPE (top0), 0));
 539     }
 540   /* For !x use x == 0.  */
 541   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
 542     {
 543       tree top0 = TREE_OPERAND (t, 0);
 544       t = build2 (EQ_EXPR, TREE_TYPE (t),
 545                   top0, build_int_cst (TREE_TYPE (top0), 0));
 546     }
 547   /* For cmp ? 1 : 0 use cmp.  */
 548   else if (TREE_CODE (t) == COND_EXPR
 549            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
 550            && integer_onep (TREE_OPERAND (t, 1))
 551            && integer_zerop (TREE_OPERAND (t, 2)))
 552     {
 553       tree top0 = TREE_OPERAND (t, 0);
 554       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
 555                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
 556     }
 557
 558   /* A valid conditional for a COND_EXPR is either a gimple value
 559      or a comparison with two gimple value operands.  */
 560   if (is_gimple_val (t)
 561       || (COMPARISON_CLASS_P (t)
 562           && is_gimple_val (TREE_OPERAND (t, 0))
 563           && is_gimple_val (TREE_OPERAND (t, 1))))
 564     return t;
 565
 566   return NULL_TREE;
 567 }