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