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 COND_EXPR:
  65     case ADDR_EXPR:
  66     case CALL_EXPR:
  67     case CONSTRUCTOR:
  68     case COMPLEX_EXPR:
  69     case INTEGER_CST:
  70     case REAL_CST:
  71     case FIXED_CST:
  72     case STRING_CST:
  73     case COMPLEX_CST:
  74     case VECTOR_CST:
  75     case OBJ_TYPE_REF:
  76     case ASSERT_EXPR:
  77       return true;
  78
  79     default:
  80       break;
  81     }
  82
  83   return is_gimple_lvalue (t) || is_gimple_val (t);
  84 }
  85
  86 /* Returns true iff T is a valid RHS for an assignment to a renamed
  87    user -- or front-end generated artificial -- variable.  */
  88
  89 bool
  90 is_gimple_reg_rhs (tree t)
  91 {
  92   /* If the RHS of the GIMPLE_MODIFY_STMT may throw or make a nonlocal goto
  93      and the LHS is a user variable, then we need to introduce a formal
  94      temporary.  This way the optimizers can determine that the user
  95      variable is only modified if evaluation of the RHS does not throw.
  96
  97      Don't force a temp of a non-renamable type; the copy could be
  98      arbitrarily expensive.  Instead we will generate a VDEF for
  99      the assignment.  */
 100
 101   if (is_gimple_reg_type (TREE_TYPE (t))
 102       && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t))
 103           || tree_could_throw_p (t)))
 104     return false;
 105
 106   return is_gimple_formal_tmp_rhs (t);
 107 }
 108
 109 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 110    LHS, or for a call argument.  */
 111
 112 bool
 113 is_gimple_mem_rhs (tree t)
 114 {
 115   /* If we're dealing with a renamable type, either source or dest must be
 116      a renamed variable.  Also force a temporary if the type doesn't need
 117      to be stored in memory, since it's cheap and prevents erroneous
 118      tailcalls (PR 17526).  */
 119   if (is_gimple_reg_type (TREE_TYPE (t))
 120       || (TYPE_MODE (TREE_TYPE (t)) != BLKmode
 121           && (TREE_CODE (t) != CALL_EXPR
 122               || ! aggregate_value_p (t, t))))
 123     return is_gimple_val (t);
 124   else
 125     return is_gimple_formal_tmp_rhs (t);
 126 }
 127
 128 /* Returns the appropriate RHS predicate for this LHS.  */
 129
 130 gimple_predicate
 131 rhs_predicate_for (tree lhs)
 132 {
 133   if (is_gimple_formal_tmp_var (lhs))
 134     return is_gimple_formal_tmp_rhs;
 135   else if (is_gimple_reg (lhs))
 136     return is_gimple_reg_rhs;
 137   else
 138     return is_gimple_mem_rhs;
 139 }
 140
 141 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 142
 143 bool
 144 is_gimple_lvalue (tree t)
 145 {
 146   return (is_gimple_addressable (t)
 147           || TREE_CODE (t) == WITH_SIZE_EXPR
 148           /* These are complex lvalues, but don't have addresses, so they
 149              go here.  */
 150           || TREE_CODE (t) == BIT_FIELD_REF);
 151 }
 152
 153 /*  Return true if T is a GIMPLE condition.  */
 154
 155 bool
 156 is_gimple_condexpr (tree t)
 157 {
 158   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 159 }
 160
 161 /*  Return true if T is something whose address can be taken.  */
 162
 163 bool
 164 is_gimple_addressable (tree t)
 165 {
 166   return (is_gimple_id (t) || handled_component_p (t)
 167           || INDIRECT_REF_P (t));
 168 }
 169
 170 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
 171    form of function invariant.  */
 172
 173 bool
 174 is_gimple_min_invariant (const_tree t)
 175 {
 176   switch (TREE_CODE (t))
 177     {
 178     case ADDR_EXPR:
 179       return TREE_INVARIANT (t);
 180
 181     case INTEGER_CST:
 182     case REAL_CST:
 183     case FIXED_CST:
 184     case STRING_CST:
 185     case COMPLEX_CST:
 186     case VECTOR_CST:
 187       return true;
 188
 189     /* Vector constant constructors are gimple invariant.  */
 190     case CONSTRUCTOR:
 191       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 192         return TREE_CONSTANT (t);
 193       else
 194         return false;
 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   const enum tree_code code = TREE_CODE (t);
 207
 208   switch (code)
 209     {
 210     case NOP_EXPR:
 211       /* The only valid NOP_EXPR is the empty statement.  */
 212       return IS_EMPTY_STMT (t);
 213
 214     case BIND_EXPR:
 215     case COND_EXPR:
 216       /* These are only valid if they're void.  */
 217       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 218
 219     case SWITCH_EXPR:
 220     case GOTO_EXPR:
 221     case RETURN_EXPR:
 222     case LABEL_EXPR:
 223     case CASE_LABEL_EXPR:
 224     case TRY_CATCH_EXPR:
 225     case TRY_FINALLY_EXPR:
 226     case EH_FILTER_EXPR:
 227     case CATCH_EXPR:
 228     case CHANGE_DYNAMIC_TYPE_EXPR:
 229     case ASM_EXPR:
 230     case RESX_EXPR:
 231     case PHI_NODE:
 232     case STATEMENT_LIST:
 233     case OMP_PARALLEL:
 234     case OMP_FOR:
 235     case OMP_SECTIONS:
 236     case OMP_SECTIONS_SWITCH:
 237     case OMP_SECTION:
 238     case OMP_SINGLE:
 239     case OMP_MASTER:
 240     case OMP_ORDERED:
 241     case OMP_CRITICAL:
 242     case OMP_RETURN:
 243     case OMP_CONTINUE:
 244     case OMP_ATOMIC_LOAD:
 245     case OMP_ATOMIC_STORE:
 246       /* These are always void.  */
 247       return true;
 248
 249     case CALL_EXPR:
 250     case GIMPLE_MODIFY_STMT:
 251       /* These are valid regardless of their type.  */
 252       return true;
 253
 254     default:
 255       return false;
 256     }
 257 }
 258
 259 /* Return true if T is a variable.  */
 260
 261 bool
 262 is_gimple_variable (tree t)
 263 {
 264   return (TREE_CODE (t) == VAR_DECL
 265           || TREE_CODE (t) == PARM_DECL
 266           || TREE_CODE (t) == RESULT_DECL
 267           || TREE_CODE (t) == SSA_NAME);
 268 }
 269
 270 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 271
 272 bool
 273 is_gimple_id (tree t)
 274 {
 275   return (is_gimple_variable (t)
 276           || TREE_CODE (t) == FUNCTION_DECL
 277           || TREE_CODE (t) == LABEL_DECL
 278           || TREE_CODE (t) == CONST_DECL
 279           /* Allow string constants, since they are addressable.  */
 280           || TREE_CODE (t) == STRING_CST);
 281 }
 282
 283 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 284
 285 bool
 286 is_gimple_reg_type (tree type)
 287 {
 288   /* In addition to aggregate types, we also exclude complex types if not
 289      optimizing because they can be subject to partial stores in GNU C by
 290      means of the __real__ and __imag__ operators and we cannot promote
 291      them to total stores (see gimplify_modify_expr_complex_part).  */
 292   return !(AGGREGATE_TYPE_P (type)
 293            || (TREE_CODE (type) == COMPLEX_TYPE && !optimize));
 294
 295 }
 296
 297 /* Return true if T is a non-aggregate register variable.  */
 298
 299 bool
 300 is_gimple_reg (tree t)
 301 {
 302   if (TREE_CODE (t) == SSA_NAME)
 303     t = SSA_NAME_VAR (t);
 304
 305   if (MTAG_P (t))
 306     return false;
 307
 308   if (!is_gimple_variable (t))
 309     return false;
 310
 311   if (!is_gimple_reg_type (TREE_TYPE (t)))
 312     return false;
 313
 314   /* A volatile decl is not acceptable because we can't reuse it as
 315      needed.  We need to copy it into a temp first.  */
 316   if (TREE_THIS_VOLATILE (t))
 317     return false;
 318
 319   /* We define "registers" as things that can be renamed as needed,
 320      which with our infrastructure does not apply to memory.  */
 321   if (needs_to_live_in_memory (t))
 322     return false;
 323
 324   /* Hard register variables are an interesting case.  For those that
 325      are call-clobbered, we don't know where all the calls are, since
 326      we don't (want to) take into account which operations will turn
 327      into libcalls at the rtl level.  For those that are call-saved,
 328      we don't currently model the fact that calls may in fact change
 329      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 330      level, and so miss variable changes that might imply.  All around,
 331      it seems safest to not do too much optimization with these at the
 332      tree level at all.  We'll have to rely on the rtl optimizers to
 333      clean this up, as there we've got all the appropriate bits exposed.  */
 334   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 335     return false;
 336
 337   /* Complex and vector values must have been put into SSA-like form.
 338      That is, no assignments to the individual components.  */
 339   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 340       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 341     return DECL_GIMPLE_REG_P (t);
 342
 343   return true;
 344 }
 345
 346
 347 /* Returns true if T is a GIMPLE formal temporary variable.  */
 348
 349 bool
 350 is_gimple_formal_tmp_var (tree t)
 351 {
 352   if (TREE_CODE (t) == SSA_NAME)
 353     return true;
 354
 355   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 356 }
 357
 358 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 359
 360 bool
 361 is_gimple_formal_tmp_reg (tree t)
 362 {
 363   /* The intent of this is to get hold of a value that won't change.
 364      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 365   if (TREE_CODE (t) == SSA_NAME)
 366     return true;
 367
 368   /* We don't know the lifetime characteristics of user variables.  */
 369   if (!is_gimple_formal_tmp_var (t))
 370     return false;
 371
 372   /* Finally, it must be capable of being placed in a register.  */
 373   return is_gimple_reg (t);
 374 }
 375
 376 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 377
 378 bool
 379 is_gimple_non_addressable (tree t)
 380 {
 381   if (TREE_CODE (t) == SSA_NAME)
 382     t = SSA_NAME_VAR (t);
 383
 384   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 385 }
 386
 387 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 388
 389 bool
 390 is_gimple_val (tree t)
 391 {
 392   /* Make loads from volatiles and memory vars explicit.  */
 393   if (is_gimple_variable (t)
 394       && is_gimple_reg_type (TREE_TYPE (t))
 395       && !is_gimple_reg (t))
 396     return false;
 397
 398   /* FIXME make these decls.  That can happen only when we expose the
 399      entire landing-pad construct at the tree level.  */
 400   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 401     return true;
 402
 403   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 404 }
 405
 406 /* Similarly, but accept hard registers as inputs to asm statements.  */
 407
 408 bool
 409 is_gimple_asm_val (tree t)
 410 {
 411   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 412     return true;
 413
 414   return is_gimple_val (t);
 415 }
 416
 417 /* Return true if T is a GIMPLE minimal lvalue.  */
 418
 419 bool
 420 is_gimple_min_lval (tree t)
 421 {
 422   return (is_gimple_id (t)
 423           || TREE_CODE (t) == INDIRECT_REF);
 424 }
 425
 426 /* Return true if T is a typecast operation.  */
 427
 428 bool
 429 is_gimple_cast (tree t)
 430 {
 431   return (TREE_CODE (t) == NOP_EXPR
 432           || TREE_CODE (t) == CONVERT_EXPR
 433           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 434 }
 435
 436 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 437
 438 bool
 439 is_gimple_call_addr (tree t)
 440 {
 441   return (TREE_CODE (t) == OBJ_TYPE_REF
 442           || is_gimple_val (t));
 443 }
 444
 445 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 446    Otherwise, return NULL_TREE.  */
 447
 448 tree
 449 get_call_expr_in (tree t)
 450 {
 451   /* FIXME tuples: delete the assertion below when conversion complete.  */
 452   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 453   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 454     t = GIMPLE_STMT_OPERAND (t, 1);
 455   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 456     t = TREE_OPERAND (t, 0);
 457   if (TREE_CODE (t) == CALL_EXPR)
 458     return t;
 459   return NULL_TREE;
 460 }
 461
 462 /* Given a memory reference expression T, return its base address.
 463    The base address of a memory reference expression is the main
 464    object being referenced.  For instance, the base address for
 465    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 466    away the offset part from a memory address.
 467
 468    This function calls handled_component_p to strip away all the inner
 469    parts of the memory reference until it reaches the base object.  */
 470
 471 tree
 472 get_base_address (tree t)
 473 {
 474   while (handled_component_p (t))
 475     t = TREE_OPERAND (t, 0);
 476
 477   if (SSA_VAR_P (t)
 478       || TREE_CODE (t) == STRING_CST
 479       || TREE_CODE (t) == CONSTRUCTOR
 480       || INDIRECT_REF_P (t))
 481     return t;
 482   else
 483     return NULL_TREE;
 484 }
 485
 486 void
 487 recalculate_side_effects (tree t)
 488 {
 489   enum tree_code code = TREE_CODE (t);
 490   int len = TREE_OPERAND_LENGTH (t);
 491   int i;
 492
 493   switch (TREE_CODE_CLASS (code))
 494     {
 495     case tcc_expression:
 496       switch (code)
 497         {
 498         case INIT_EXPR:
 499         case GIMPLE_MODIFY_STMT:
 500         case VA_ARG_EXPR:
 501         case PREDECREMENT_EXPR:
 502         case PREINCREMENT_EXPR:
 503         case POSTDECREMENT_EXPR:
 504         case POSTINCREMENT_EXPR:
 505           /* All of these have side-effects, no matter what their
 506              operands are.  */
 507           return;
 508
 509         default:
 510           break;
 511         }
 512       /* Fall through.  */
 513
 514     case tcc_comparison:  /* a comparison expression */
 515     case tcc_unary:       /* a unary arithmetic expression */
 516     case tcc_binary:      /* a binary arithmetic expression */
 517     case tcc_reference:   /* a reference */
 518     case tcc_vl_exp:        /* a function call */
 519       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 520       for (i = 0; i < len; ++i)
 521         {
 522           tree op = TREE_OPERAND (t, i);
 523           if (op && TREE_SIDE_EFFECTS (op))
 524             TREE_SIDE_EFFECTS (t) = 1;
 525         }
 526       break;
 527
 528     default:
 529       /* Can never be used with non-expressions.  */
 530       gcc_unreachable ();
 531    }
 532 }
 533
 534 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
 535    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
 536    we failed to create one.  */
 537
 538 tree
 539 canonicalize_cond_expr_cond (tree t)
 540 {
 541   /* For (bool)x use x != 0.  */
 542   if (TREE_CODE (t) == NOP_EXPR
 543       && TREE_TYPE (t) == boolean_type_node)
 544     {
 545       tree top0 = TREE_OPERAND (t, 0);
 546       t = build2 (NE_EXPR, TREE_TYPE (t),
 547                   top0, build_int_cst (TREE_TYPE (top0), 0));
 548     }
 549   /* For !x use x == 0.  */
 550   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
 551     {
 552       tree top0 = TREE_OPERAND (t, 0);
 553       t = build2 (EQ_EXPR, TREE_TYPE (t),
 554                   top0, build_int_cst (TREE_TYPE (top0), 0));
 555     }
 556   /* For cmp ? 1 : 0 use cmp.  */
 557   else if (TREE_CODE (t) == COND_EXPR
 558            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
 559            && integer_onep (TREE_OPERAND (t, 1))
 560            && integer_zerop (TREE_OPERAND (t, 2)))
 561     {
 562       tree top0 = TREE_OPERAND (t, 0);
 563       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
 564                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
 565     }
 566
 567   /* A valid conditional for a COND_EXPR is either a gimple value
 568      or a comparison with two gimple value operands.  */
 569   if (is_gimple_val (t)
 570       || (COMPARISON_CLASS_P (t)
 571           && is_gimple_val (TREE_OPERAND (t, 0))
 572           && is_gimple_val (TREE_OPERAND (t, 1))))
 573     return t;
 574
 575   return NULL_TREE;
 576 }