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