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 valid gimple constant.  */
 171
 172 bool
 173 is_gimple_constant (const_tree t)
 174 {
 175   switch (TREE_CODE (t))
 176     {
 177     case INTEGER_CST:
 178     case REAL_CST:
 179     case FIXED_CST:
 180     case STRING_CST:
 181     case COMPLEX_CST:
 182     case VECTOR_CST:
 183       return true;
 184
 185     /* Vector constant constructors are gimple invariant.  */
 186     case CONSTRUCTOR:
 187       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 188         return TREE_CONSTANT (t);
 189       else
 190         return false;
 191
 192     default:
 193       return false;
 194     }
 195 }
 196
 197 /* Return true if T is a gimple invariant address.  */
 198
 199 bool
 200 is_gimple_invariant_address (const_tree t)
 201 {
 202   tree op;
 203
 204   if (TREE_CODE (t) != ADDR_EXPR)
 205     return false;
 206
 207   op = TREE_OPERAND (t, 0);
 208   while (handled_component_p (op))
 209     {
 210       switch (TREE_CODE (op))
 211         {
 212         case ARRAY_REF:
 213         case ARRAY_RANGE_REF:
 214           if (!is_gimple_constant (TREE_OPERAND (op, 1))
 215               || TREE_OPERAND (op, 2) != NULL_TREE
 216               || TREE_OPERAND (op, 3) != NULL_TREE)
 217             return false;
 218           break;
 219
 220         case COMPONENT_REF:
 221           if (TREE_OPERAND (op, 2) != NULL_TREE)
 222             return false;
 223           break;
 224
 225         default:;
 226         }
 227       op = TREE_OPERAND (op, 0);
 228     }
 229
 230   if (CONSTANT_CLASS_P (op))
 231     return true;
 232
 233   if (INDIRECT_REF_P (op))
 234     return false;
 235
 236   switch (TREE_CODE (op))
 237     {
 238     case PARM_DECL:
 239     case RESULT_DECL:
 240     case LABEL_DECL:
 241     case FUNCTION_DECL:
 242       return true;
 243
 244     case VAR_DECL:
 245       if (((TREE_STATIC (op) || DECL_EXTERNAL (op))
 246            && ! DECL_DLLIMPORT_P (op))
 247           || DECL_THREAD_LOCAL_P (op)
 248           || DECL_CONTEXT (op) == current_function_decl
 249           || decl_function_context (op) == current_function_decl)
 250         return true;
 251       break;
 252
 253     case CONST_DECL:
 254       if ((TREE_STATIC (op) || DECL_EXTERNAL (op))
 255           || decl_function_context (op) == current_function_decl)
 256         return true;
 257       break;
 258
 259     default:
 260       gcc_unreachable ();
 261     }
 262
 263   return false;
 264 }
 265
 266 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
 267    form of function invariant.  */
 268
 269 bool
 270 is_gimple_min_invariant (const_tree t)
 271 {
 272   if (TREE_CODE (t) == ADDR_EXPR)
 273     return is_gimple_invariant_address (t);
 274
 275   return is_gimple_constant (t);
 276 }
 277
 278 /* Return true if T looks like a valid GIMPLE statement.  */
 279
 280 bool
 281 is_gimple_stmt (tree t)
 282 {
 283   const enum tree_code code = TREE_CODE (t);
 284
 285   switch (code)
 286     {
 287     case NOP_EXPR:
 288       /* The only valid NOP_EXPR is the empty statement.  */
 289       return IS_EMPTY_STMT (t);
 290
 291     case BIND_EXPR:
 292     case COND_EXPR:
 293       /* These are only valid if they're void.  */
 294       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 295
 296     case SWITCH_EXPR:
 297     case GOTO_EXPR:
 298     case RETURN_EXPR:
 299     case LABEL_EXPR:
 300     case CASE_LABEL_EXPR:
 301     case TRY_CATCH_EXPR:
 302     case TRY_FINALLY_EXPR:
 303     case EH_FILTER_EXPR:
 304     case CATCH_EXPR:
 305     case CHANGE_DYNAMIC_TYPE_EXPR:
 306     case ASM_EXPR:
 307     case RESX_EXPR:
 308     case PHI_NODE:
 309     case STATEMENT_LIST:
 310     case OMP_PARALLEL:
 311     case OMP_FOR:
 312     case OMP_SECTIONS:
 313     case OMP_SECTIONS_SWITCH:
 314     case OMP_SECTION:
 315     case OMP_SINGLE:
 316     case OMP_MASTER:
 317     case OMP_ORDERED:
 318     case OMP_CRITICAL:
 319     case OMP_RETURN:
 320     case OMP_CONTINUE:
 321     case OMP_ATOMIC_LOAD:
 322     case OMP_ATOMIC_STORE:
 323       /* These are always void.  */
 324       return true;
 325
 326     case CALL_EXPR:
 327     case GIMPLE_MODIFY_STMT:
 328     case PREDICT_EXPR:
 329       /* These are valid regardless of their type.  */
 330       return true;
 331
 332     default:
 333       return false;
 334     }
 335 }
 336
 337 /* Return true if T is a variable.  */
 338
 339 bool
 340 is_gimple_variable (tree t)
 341 {
 342   return (TREE_CODE (t) == VAR_DECL
 343           || TREE_CODE (t) == PARM_DECL
 344           || TREE_CODE (t) == RESULT_DECL
 345           || TREE_CODE (t) == SSA_NAME);
 346 }
 347
 348 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 349
 350 bool
 351 is_gimple_id (tree t)
 352 {
 353   return (is_gimple_variable (t)
 354           || TREE_CODE (t) == FUNCTION_DECL
 355           || TREE_CODE (t) == LABEL_DECL
 356           || TREE_CODE (t) == CONST_DECL
 357           /* Allow string constants, since they are addressable.  */
 358           || TREE_CODE (t) == STRING_CST);
 359 }
 360
 361 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 362
 363 bool
 364 is_gimple_reg_type (tree type)
 365 {
 366   /* In addition to aggregate types, we also exclude complex types if not
 367      optimizing because they can be subject to partial stores in GNU C by
 368      means of the __real__ and __imag__ operators and we cannot promote
 369      them to total stores (see gimplify_modify_expr_complex_part).  */
 370   return !(AGGREGATE_TYPE_P (type)
 371            || (TREE_CODE (type) == COMPLEX_TYPE && !optimize));
 372
 373 }
 374
 375 /* Return true if T is a non-aggregate register variable.  */
 376
 377 bool
 378 is_gimple_reg (tree t)
 379 {
 380   if (TREE_CODE (t) == SSA_NAME)
 381     t = SSA_NAME_VAR (t);
 382
 383   if (MTAG_P (t))
 384     return false;
 385
 386   if (!is_gimple_variable (t))
 387     return false;
 388
 389   if (!is_gimple_reg_type (TREE_TYPE (t)))
 390     return false;
 391
 392   /* A volatile decl is not acceptable because we can't reuse it as
 393      needed.  We need to copy it into a temp first.  */
 394   if (TREE_THIS_VOLATILE (t))
 395     return false;
 396
 397   /* We define "registers" as things that can be renamed as needed,
 398      which with our infrastructure does not apply to memory.  */
 399   if (needs_to_live_in_memory (t))
 400     return false;
 401
 402   /* Hard register variables are an interesting case.  For those that
 403      are call-clobbered, we don't know where all the calls are, since
 404      we don't (want to) take into account which operations will turn
 405      into libcalls at the rtl level.  For those that are call-saved,
 406      we don't currently model the fact that calls may in fact change
 407      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 408      level, and so miss variable changes that might imply.  All around,
 409      it seems safest to not do too much optimization with these at the
 410      tree level at all.  We'll have to rely on the rtl optimizers to
 411      clean this up, as there we've got all the appropriate bits exposed.  */
 412   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 413     return false;
 414
 415   /* Complex and vector values must have been put into SSA-like form.
 416      That is, no assignments to the individual components.  */
 417   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 418       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 419     return DECL_GIMPLE_REG_P (t);
 420
 421   return true;
 422 }
 423
 424
 425 /* Returns true if T is a GIMPLE formal temporary variable.  */
 426
 427 bool
 428 is_gimple_formal_tmp_var (tree t)
 429 {
 430   if (TREE_CODE (t) == SSA_NAME)
 431     return true;
 432
 433   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 434 }
 435
 436 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 437
 438 bool
 439 is_gimple_formal_tmp_reg (tree t)
 440 {
 441   /* The intent of this is to get hold of a value that won't change.
 442      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 443   if (TREE_CODE (t) == SSA_NAME)
 444     return true;
 445
 446   /* We don't know the lifetime characteristics of user variables.  */
 447   if (!is_gimple_formal_tmp_var (t))
 448     return false;
 449
 450   /* Finally, it must be capable of being placed in a register.  */
 451   return is_gimple_reg (t);
 452 }
 453
 454 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 455
 456 bool
 457 is_gimple_non_addressable (tree t)
 458 {
 459   if (TREE_CODE (t) == SSA_NAME)
 460     t = SSA_NAME_VAR (t);
 461
 462   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 463 }
 464
 465 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 466
 467 bool
 468 is_gimple_val (tree t)
 469 {
 470   /* Make loads from volatiles and memory vars explicit.  */
 471   if (is_gimple_variable (t)
 472       && is_gimple_reg_type (TREE_TYPE (t))
 473       && !is_gimple_reg (t))
 474     return false;
 475
 476   /* FIXME make these decls.  That can happen only when we expose the
 477      entire landing-pad construct at the tree level.  */
 478   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 479     return true;
 480
 481   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 482 }
 483
 484 /* Similarly, but accept hard registers as inputs to asm statements.  */
 485
 486 bool
 487 is_gimple_asm_val (tree t)
 488 {
 489   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 490     return true;
 491
 492   return is_gimple_val (t);
 493 }
 494
 495 /* Return true if T is a GIMPLE minimal lvalue.  */
 496
 497 bool
 498 is_gimple_min_lval (tree t)
 499 {
 500   return (is_gimple_id (t)
 501           || TREE_CODE (t) == INDIRECT_REF);
 502 }
 503
 504 /* Return true if T is a typecast operation.  */
 505
 506 bool
 507 is_gimple_cast (tree t)
 508 {
 509   return (TREE_CODE (t) == NOP_EXPR
 510           || TREE_CODE (t) == CONVERT_EXPR
 511           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 512 }
 513
 514 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 515
 516 bool
 517 is_gimple_call_addr (tree t)
 518 {
 519   return (TREE_CODE (t) == OBJ_TYPE_REF
 520           || is_gimple_val (t));
 521 }
 522
 523 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 524    Otherwise, return NULL_TREE.  */
 525
 526 tree
 527 get_call_expr_in (tree t)
 528 {
 529   /* FIXME tuples: delete the assertion below when conversion complete.  */
 530   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 531   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 532     t = GIMPLE_STMT_OPERAND (t, 1);
 533   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 534     t = TREE_OPERAND (t, 0);
 535   if (TREE_CODE (t) == CALL_EXPR)
 536     return t;
 537   return NULL_TREE;
 538 }
 539
 540 /* Given a memory reference expression T, return its base address.
 541    The base address of a memory reference expression is the main
 542    object being referenced.  For instance, the base address for
 543    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 544    away the offset part from a memory address.
 545
 546    This function calls handled_component_p to strip away all the inner
 547    parts of the memory reference until it reaches the base object.  */
 548
 549 tree
 550 get_base_address (tree t)
 551 {
 552   while (handled_component_p (t))
 553     t = TREE_OPERAND (t, 0);
 554
 555   if (SSA_VAR_P (t)
 556       || TREE_CODE (t) == STRING_CST
 557       || TREE_CODE (t) == CONSTRUCTOR
 558       || INDIRECT_REF_P (t))
 559     return t;
 560   else
 561     return NULL_TREE;
 562 }
 563
 564 void
 565 recalculate_side_effects (tree t)
 566 {
 567   enum tree_code code = TREE_CODE (t);
 568   int len = TREE_OPERAND_LENGTH (t);
 569   int i;
 570
 571   switch (TREE_CODE_CLASS (code))
 572     {
 573     case tcc_expression:
 574       switch (code)
 575         {
 576         case INIT_EXPR:
 577         case GIMPLE_MODIFY_STMT:
 578         case VA_ARG_EXPR:
 579         case PREDECREMENT_EXPR:
 580         case PREINCREMENT_EXPR:
 581         case POSTDECREMENT_EXPR:
 582         case POSTINCREMENT_EXPR:
 583           /* All of these have side-effects, no matter what their
 584              operands are.  */
 585           return;
 586
 587         default:
 588           break;
 589         }
 590       /* Fall through.  */
 591
 592     case tcc_comparison:  /* a comparison expression */
 593     case tcc_unary:       /* a unary arithmetic expression */
 594     case tcc_binary:      /* a binary arithmetic expression */
 595     case tcc_reference:   /* a reference */
 596     case tcc_vl_exp:        /* a function call */
 597       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 598       for (i = 0; i < len; ++i)
 599         {
 600           tree op = TREE_OPERAND (t, i);
 601           if (op && TREE_SIDE_EFFECTS (op))
 602             TREE_SIDE_EFFECTS (t) = 1;
 603         }
 604       break;
 605
 606     default:
 607       /* Can never be used with non-expressions.  */
 608       gcc_unreachable ();
 609    }
 610 }
 611
 612 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
 613    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
 614    we failed to create one.  */
 615
 616 tree
 617 canonicalize_cond_expr_cond (tree t)
 618 {
 619   /* For (bool)x use x != 0.  */
 620   if (TREE_CODE (t) == NOP_EXPR
 621       && TREE_TYPE (t) == boolean_type_node)
 622     {
 623       tree top0 = TREE_OPERAND (t, 0);
 624       t = build2 (NE_EXPR, TREE_TYPE (t),
 625                   top0, build_int_cst (TREE_TYPE (top0), 0));
 626     }
 627   /* For !x use x == 0.  */
 628   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
 629     {
 630       tree top0 = TREE_OPERAND (t, 0);
 631       t = build2 (EQ_EXPR, TREE_TYPE (t),
 632                   top0, build_int_cst (TREE_TYPE (top0), 0));
 633     }
 634   /* For cmp ? 1 : 0 use cmp.  */
 635   else if (TREE_CODE (t) == COND_EXPR
 636            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
 637            && integer_onep (TREE_OPERAND (t, 1))
 638            && integer_zerop (TREE_OPERAND (t, 2)))
 639     {
 640       tree top0 = TREE_OPERAND (t, 0);
 641       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
 642                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
 643     }
 644
 645   /* A valid conditional for a COND_EXPR is either a gimple value
 646      or a comparison with two gimple value operands.  */
 647   if (is_gimple_val (t)
 648       || (COMPARISON_CLASS_P (t)
 649           && is_gimple_val (TREE_OPERAND (t, 0))
 650           && is_gimple_val (TREE_OPERAND (t, 1))))
 651     return t;
 652
 653   return NULL_TREE;
 654 }