gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4    Rewritten by Jason Merrill <jason@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  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 "output.h"
  31 #include "rtl.h"
  32 #include "expr.h"
  33 #include "bitmap.h"
  34
  35 /* GCC GIMPLE structure
  36
  37    Inspired by the SIMPLE C grammar at
  38
  39         http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html
  40
  41    function     : FUNCTION_DECL
  42                         DECL_SAVED_TREE -> compound-stmt
  43
  44    compound-stmt: STATEMENT_LIST
  45                         members -> stmt
  46
  47    stmt         : block
  48                 | if-stmt
  49                 | switch-stmt
  50                 | goto-stmt
  51                 | return-stmt
  52                 | resx-stmt
  53                 | label-stmt
  54                 | try-stmt
  55                 | modify-stmt
  56                 | call-stmt
  57
  58    block        : BIND_EXPR
  59                         BIND_EXPR_VARS -> chain of DECLs
  60                         BIND_EXPR_BLOCK -> BLOCK
  61                         BIND_EXPR_BODY -> compound-stmt
  62
  63    if-stmt      : COND_EXPR
  64                         op0 -> condition
  65                         op1 -> compound-stmt
  66                         op2 -> compound-stmt
  67
  68    switch-stmt  : SWITCH_EXPR
  69                         op0 -> val
  70                         op1 -> NULL
  71                         op2 -> TREE_VEC of CASE_LABEL_EXPRs
  72                             The CASE_LABEL_EXPRs are sorted by CASE_LOW,
  73                             and default is last.
  74
  75    goto-stmt    : GOTO_EXPR
  76                         op0 -> LABEL_DECL | val
  77
  78    return-stmt  : RETURN_EXPR
  79                         op0 -> return-value
  80
  81    return-value : NULL
  82                 | RESULT_DECL
  83                 | MODIFY_EXPR
  84                         op0 -> RESULT_DECL
  85                         op1 -> lhs
  86
  87    resx-stmt    : RESX_EXPR
  88
  89    label-stmt   : LABEL_EXPR
  90                         op0 -> LABEL_DECL
  91
  92    try-stmt     : TRY_CATCH_EXPR
  93                         op0 -> compound-stmt
  94                         op1 -> handler
  95                 | TRY_FINALLY_EXPR
  96                         op0 -> compound-stmt
  97                         op1 -> compound-stmt
  98
  99    handler      : catch-seq
 100                 | EH_FILTER_EXPR
 101                 | compound-stmt
 102
 103    catch-seq    : STATEMENT_LIST
 104                         members -> CATCH_EXPR
 105
 106    modify-stmt  : MODIFY_EXPR
 107                         op0 -> lhs
 108                         op1 -> rhs
 109
 110    call-stmt    : CALL_EXPR
 111                         op0 -> val | OBJ_TYPE_REF
 112                         op1 -> call-arg-list
 113
 114    call-arg-list: TREE_LIST
 115                         members -> lhs
 116
 117    addr-expr-arg: ID
 118                 | compref
 119
 120    lhs          : addr-expr-arg
 121                 | '*' val
 122                 | bitfieldref
 123
 124    min-lval     : ID
 125                 | '*' val
 126
 127    bitfieldref  : BIT_FIELD_REF
 128                         op0 -> inner-compref
 129                         op1 -> CONST
 130                         op2 -> var
 131
 132    compref      : inner-compref
 133                 | REALPART_EXPR
 134                         op0 -> inner-compref
 135                 | IMAGPART_EXPR
 136                         op0 -> inner-compref
 137
 138    inner-compref: min-lval
 139                 | COMPONENT_REF
 140                         op0 -> inner-compref
 141                         op1 -> FIELD_DECL
 142                         op2 -> val
 143                 | ARRAY_REF
 144                         op0 -> inner-compref
 145                         op1 -> val
 146                         op2 -> val
 147                         op3 -> val
 148                 | ARRAY_RANGE_REF
 149                         op0 -> inner-compref
 150                         op1 -> val
 151                         op2 -> val
 152                         op3 -> val
 153                 | VIEW_CONVERT_EXPR
 154                         op0 -> inner-compref
 155
 156    condition    : val
 157                 | val RELOP val
 158
 159    val          : ID
 160                 | CONST
 161
 162    rhs          : lhs
 163                 | CONST
 164                 | '&' addr-expr-arg
 165                 | call_expr
 166                 | UNOP val
 167                 | val BINOP val
 168                 | val RELOP val
 169 */
 170
 171 static inline bool is_gimple_id (tree);
 172
 173 /* Validation of GIMPLE expressions.  */
 174
 175 /* Return true if T is a GIMPLE RHS.  */
 176
 177 bool
 178 is_gimple_rhs (tree t)
 179 {
 180   enum tree_code code = TREE_CODE (t);
 181
 182   switch (TREE_CODE_CLASS (code))
 183     {
 184     case '1':
 185     case '2':
 186     case '<':
 187       return true;
 188
 189     default:
 190       break;
 191     }
 192
 193   switch (code)
 194     {
 195     case TRUTH_NOT_EXPR:
 196     case TRUTH_AND_EXPR:
 197     case TRUTH_OR_EXPR:
 198     case TRUTH_XOR_EXPR:
 199     case ADDR_EXPR:
 200     case CALL_EXPR:
 201     case CONSTRUCTOR:
 202     case COMPLEX_EXPR:
 203       /* FIXME lower VA_ARG_EXPR.  */
 204     case VA_ARG_EXPR:
 205     case INTEGER_CST:
 206     case REAL_CST:
 207     case STRING_CST:
 208     case COMPLEX_CST:
 209     case VECTOR_CST:
 210     case OBJ_TYPE_REF:
 211       return true;
 212
 213     default:
 214       break;
 215     }
 216
 217   return is_gimple_lvalue (t) || is_gimple_val (t);
 218 }
 219
 220 /* Returns true if T is a valid CONSTRUCTOR component in GIMPLE, either
 221    a val or another CONSTRUCTOR.  */
 222
 223 bool
 224 is_gimple_constructor_elt (tree t)
 225 {
 226   return (is_gimple_val (t)
 227           || TREE_CODE (t) == CONSTRUCTOR);
 228 }
 229
 230 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 231
 232 bool
 233 is_gimple_lvalue (tree t)
 234 {
 235   return (is_gimple_addr_expr_arg (t)
 236           || TREE_CODE (t) == INDIRECT_REF
 237           /* These are complex lvalues, but don't have addresses, so they
 238              go here.  */
 239           || TREE_CODE (t) == BIT_FIELD_REF);
 240 }
 241
 242 /*  Return true if T is a GIMPLE condition.  */
 243
 244 bool
 245 is_gimple_condexpr (tree t)
 246 {
 247   return (is_gimple_val (t)
 248           || TREE_CODE_CLASS (TREE_CODE (t)) == '<');
 249 }
 250
 251 /*  Return true if T is a valid operand for ADDR_EXPR.  */
 252
 253 bool
 254 is_gimple_addr_expr_arg (tree t)
 255 {
 256   return (is_gimple_id (t)
 257           || TREE_CODE (t) == ARRAY_REF
 258           || TREE_CODE (t) == ARRAY_RANGE_REF
 259           || TREE_CODE (t) == COMPONENT_REF
 260           || TREE_CODE (t) == REALPART_EXPR
 261           || TREE_CODE (t) == IMAGPART_EXPR
 262           || TREE_CODE (t) == INDIRECT_REF);
 263 }
 264
 265 /* Return true if T is function invariant.  Or rather a restricted
 266    form of function invariant.  */
 267
 268 bool
 269 is_gimple_min_invariant (tree t)
 270 {
 271   switch (TREE_CODE (t))
 272     {
 273     case ADDR_EXPR:
 274       return TREE_INVARIANT (t);
 275
 276     case INTEGER_CST:
 277     case REAL_CST:
 278     case STRING_CST:
 279     case COMPLEX_CST:
 280     case VECTOR_CST:
 281       return !TREE_OVERFLOW (t);
 282
 283     default:
 284       return false;
 285     }
 286 }
 287
 288 /* Return true if T looks like a valid GIMPLE statement.  */
 289
 290 bool
 291 is_gimple_stmt (tree t)
 292 {
 293   enum tree_code code = TREE_CODE (t);
 294
 295   if (IS_EMPTY_STMT (t))
 296     return 1;
 297
 298   switch (code)
 299     {
 300     case BIND_EXPR:
 301     case COND_EXPR:
 302       /* These are only valid if they're void.  */
 303       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 304
 305     case SWITCH_EXPR:
 306     case GOTO_EXPR:
 307     case RETURN_EXPR:
 308     case LABEL_EXPR:
 309     case CASE_LABEL_EXPR:
 310     case TRY_CATCH_EXPR:
 311     case TRY_FINALLY_EXPR:
 312     case EH_FILTER_EXPR:
 313     case CATCH_EXPR:
 314     case ASM_EXPR:
 315     case RESX_EXPR:
 316     case PHI_NODE:
 317     case STATEMENT_LIST:
 318       /* These are always void.  */
 319       return true;
 320
 321     case VA_ARG_EXPR:
 322       /* FIXME this should be lowered.  */
 323       return true;
 324
 325     case CALL_EXPR:
 326     case MODIFY_EXPR:
 327       /* These are valid regardless of their type.  */
 328       return true;
 329
 330     default:
 331       return false;
 332     }
 333 }
 334
 335 /* Return true if T is a variable.  */
 336
 337 bool
 338 is_gimple_variable (tree t)
 339 {
 340   return (TREE_CODE (t) == VAR_DECL
 341           || TREE_CODE (t) == PARM_DECL
 342           || TREE_CODE (t) == RESULT_DECL
 343           || TREE_CODE (t) == SSA_NAME);
 344 }
 345
 346 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 347
 348 static inline bool
 349 is_gimple_id (tree t)
 350 {
 351   return (is_gimple_variable (t)
 352           || TREE_CODE (t) == FUNCTION_DECL
 353           || TREE_CODE (t) == LABEL_DECL
 354           /* Allow string constants, since they are addressable.  */
 355           || TREE_CODE (t) == STRING_CST);
 356 }
 357
 358 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 359
 360 bool
 361 is_gimple_reg_type (tree type)
 362 {
 363   return (!AGGREGATE_TYPE_P (type)
 364           && TREE_CODE (type) != COMPLEX_TYPE);
 365 }
 366
 367
 368 /* Return true if T is a scalar register variable.  */
 369
 370 bool
 371 is_gimple_reg (tree t)
 372 {
 373   if (TREE_CODE (t) == SSA_NAME)
 374     t = SSA_NAME_VAR (t);
 375
 376   return (is_gimple_variable (t)
 377           && is_gimple_reg_type (TREE_TYPE (t))
 378           /* A volatile decl is not acceptable because we can't reuse it as
 379              needed.  We need to copy it into a temp first.  */
 380           && ! TREE_THIS_VOLATILE (t)
 381           && ! TREE_ADDRESSABLE (t)
 382           && ! needs_to_live_in_memory (t));
 383 }
 384
 385 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 386
 387 bool
 388 is_gimple_non_addressable (tree t)
 389 {
 390   if (TREE_CODE (t) == SSA_NAME)
 391     t = SSA_NAME_VAR (t);
 392
 393   return (is_gimple_variable (t)
 394           && ! TREE_ADDRESSABLE (t)
 395           && ! needs_to_live_in_memory (t));
 396 }
 397
 398 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 399
 400 bool
 401 is_gimple_val (tree t)
 402 {
 403   /* Make loads from volatiles and memory vars explicit.  */
 404   if (is_gimple_variable (t)
 405       && is_gimple_reg_type (TREE_TYPE (t))
 406       && !is_gimple_reg (t))
 407     return false;
 408
 409   /* FIXME make these decls.  That can happen only when we expose the
 410      entire landing-pad construct at the tree level.  */
 411   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 412     return 1;
 413
 414   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 415 }
 416
 417
 418 /* Return true if T is a GIMPLE minimal lvalue.  */
 419
 420 bool
 421 is_gimple_min_lval (tree t)
 422 {
 423   return (is_gimple_id (t)
 424           || TREE_CODE (t) == INDIRECT_REF);
 425 }
 426
 427 /* Return true if T is a typecast operation.  */
 428
 429 bool
 430 is_gimple_cast (tree t)
 431 {
 432   return (TREE_CODE (t) == NOP_EXPR
 433           || TREE_CODE (t) == CONVERT_EXPR
 434           || TREE_CODE (t) == FIX_TRUNC_EXPR
 435           || TREE_CODE (t) == FIX_CEIL_EXPR
 436           || TREE_CODE (t) == FIX_FLOOR_EXPR
 437           || TREE_CODE (t) == FIX_ROUND_EXPR);
 438 }
 439
 440 /* Return true if T is a valid op0 of a CALL_EXPR.  */
 441
 442 bool
 443 is_gimple_call_addr (tree t)
 444 {
 445   return (TREE_CODE (t) == OBJ_TYPE_REF
 446           || is_gimple_val (t));
 447 }
 448
 449 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 450    Otherwise, return NULL_TREE.  */
 451
 452 tree
 453 get_call_expr_in (tree t)
 454 {
 455   if (TREE_CODE (t) == MODIFY_EXPR)
 456     t = TREE_OPERAND (t, 1);
 457   if (TREE_CODE (t) == CALL_EXPR)
 458     return t;
 459   return NULL_TREE;
 460 }
 461
 462 /* Given a memory reference expression, return the base address.  Note that,
 463    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 464    expressions.  Therefore, given the reference PTR->FIELD, this function
 465    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 466
 467 tree
 468 get_base_address (tree t)
 469 {
 470   while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
 471          || handled_component_p (t))
 472     t = TREE_OPERAND (t, 0);
 473
 474   if (SSA_VAR_P (t)
 475       || TREE_CODE (t) == STRING_CST
 476       || TREE_CODE (t) == CONSTRUCTOR
 477       || TREE_CODE (t) == INDIRECT_REF)
 478     return t;
 479   else
 480     return NULL_TREE;
 481 }
 482
 483 void
 484 recalculate_side_effects (tree t)
 485 {
 486   enum tree_code code = TREE_CODE (t);
 487   int fro = first_rtl_op (code);
 488   int i;
 489
 490   switch (TREE_CODE_CLASS (code))
 491     {
 492     case 'e':
 493       switch (code)
 494         {
 495         case INIT_EXPR:
 496         case MODIFY_EXPR:
 497         case VA_ARG_EXPR:
 498         case PREDECREMENT_EXPR:
 499         case PREINCREMENT_EXPR:
 500         case POSTDECREMENT_EXPR:
 501         case POSTINCREMENT_EXPR:
 502           /* All of these have side-effects, no matter what their
 503              operands are.  */
 504           return;
 505
 506         default:
 507           break;
 508         }
 509       /* Fall through.  */
 510
 511     case '<':  /* a comparison expression */
 512     case '1':  /* a unary arithmetic expression */
 513     case '2':  /* a binary arithmetic expression */
 514     case 'r':  /* a reference */
 515       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 516       for (i = 0; i < fro; ++i)
 517         {
 518           tree op = TREE_OPERAND (t, i);
 519           if (op && TREE_SIDE_EFFECTS (op))
 520             TREE_SIDE_EFFECTS (t) = 1;
 521         }
 522       break;
 523    }
 524 }