gcc/tree-alias-common.c

   1 /* Tree based points-to analysis
   2    Copyright (C) 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dberlin@dberlin.org>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; if not, write to the Free Software
  19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20 */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "ggc.h"
  27 #include "tree-alias-type.h"
  28 #include "bitmap.h"
  29 #include "tree-alias-common.h"
  30
  31 /* If we have andersen's points-to analysis, include it.  */
  32 #ifdef HAVE_BANSHEE
  33 #include "tree-alias-ander.h"
  34 #endif
  35
  36 #include "flags.h"
  37 #include "rtl.h"
  38 #include "tm_p.h"
  39 #include "hard-reg-set.h"
  40 #include "basic-block.h"
  41 #include "output.h"
  42 #include "errors.h"
  43 #include "expr.h"
  44 #include "diagnostic.h"
  45 #include "tree.h"
  46 #include "c-common.h"
  47 #include "tree-flow.h"
  48 #include "tree-inline.h"
  49 #include "varray.h"
  50 #include "c-tree.h"
  51 #include "tree-gimple.h"
  52 #include "hashtab.h"
  53 #include "function.h"
  54 #include "cgraph.h"
  55 #include "tree-pass.h"
  56 #include "timevar.h"
  57
  58 /* Reduce ifdefery later.  */
  59 #ifndef HAVE_BANSHEE
  60 #define HAVE_BANSHEE 0
  61 #endif
  62
  63 /*  This file contains the implementation of the common parts of the
  64     tree points-to analysis infrastructure.
  65
  66     Overview:
  67
  68     This file contains the points-to analysis driver.  It does two main things:
  69     1. Keeps track of the PTA data for each variable (IE the data each
  70     specific PTA implementation wants to keep associated with a
  71     variable).
  72     2. Walks the function trees, calling the appropriate functions that
  73     each PTA implementation has implemented.
  74
  75     In order to speed up PTA queries, the PTA specific data is stored
  76     in the tree for *_DECL's, in DECL_PTA_ALIASVAR.  This way, we only
  77     need to use the hash table for non-DECL's.  */
  78 #define FIELD_BASED 0
  79
  80 /*  Array of all created alias_vars.
  81     Note that this should contain all the alias_vars we wanted
  82     marked during GC.  */
  83 static GTY((param_is (union alias_var_def))) varray_type alias_vars = NULL;
  84 struct tree_alias_ops *current_alias_ops;
  85
  86 /*  Array of local (to a function) alias_vars.
  87     Note that this should contain all the alias_vars that are
  88     local to this function.  We delete these from alias_vars before
  89     collection.  */
  90 static GTY(()) varray_type local_alias_vars;
  91 static GTY(()) varray_type local_alias_varnums;
  92 tree pta_global_var;
  93 static bitmap addrargs;
  94 static alias_var get_alias_var_decl (tree);
  95 static alias_var get_alias_var (tree);
  96 static void find_func_aliases (tree);
  97 static void deal_with_call_aliasing (tree, alias_var);
  98 static alias_var create_fun_alias_var_ptf (tree, tree);
  99 static alias_var create_fun_alias_var (tree, int);
 100 static alias_var create_alias_var (tree);
 101 static void intra_function_call (varray_type);
 102 static void get_values_from_constructor (tree, varray_type *, bitmap, int *);
 103 static bool call_may_clobber (tree);
 104 static bool call_may_return (tree);
 105
 106 /* Return true if a EXPR, which is a CALL_EXPR, may clobber variables.  */
 107
 108 static bool
 109 call_may_clobber (tree expr)
 110 {
 111   int flags;
 112
 113   if (TREE_CODE (expr) != CALL_EXPR)
 114     return false;
 115
 116   flags = call_expr_flags (expr);
 117   return (! (flags & (ECF_CONST | ECF_PURE | ECF_NORETURN)));
 118 }
 119
 120 /* Return true if a EXPR, which is a CALL_EXPR, may return.  */
 121
 122 static bool
 123 call_may_return (tree expr)
 124 {
 125   int flags;
 126
 127   if (TREE_CODE (expr) != CALL_EXPR)
 128     return false;
 129
 130   flags = call_expr_flags (expr);
 131   return ! (flags & ECF_NORETURN);
 132 }
 133
 134 /*  Get the alias_var for DECL.
 135     Creates the alias_var if it does not exist already. Also
 136     handles FUNCTION_DECL properly.  */
 137
 138 static alias_var
 139 get_alias_var_decl (tree decl)
 140 {
 141   alias_var newvar;
 142   if (TREE_CODE (decl) == FIELD_DECL)
 143     abort ();
 144   if (DECL_P (decl))
 145     {
 146       if (DECL_PTA_ALIASVAR (decl))
 147         return DECL_PTA_ALIASVAR (decl);
 148     }
 149
 150   if (TREE_CODE (decl) == FUNCTION_DECL)
 151     newvar = create_fun_alias_var  (decl, 0);
 152   else
 153     {
 154       newvar = create_alias_var (decl);
 155       /* Assign globals to global var for purposes of intraprocedural
 156          analysis.  */
 157       if (TREE_STATIC (decl) && decl != pta_global_var)
 158         {
 159           current_alias_ops->addr_assign (current_alias_ops,
 160                                           get_alias_var (pta_global_var),
 161                                           newvar);
 162           /* If the global has some DECL_INITIAL, we need to process
 163              it here.  */
 164           if (DECL_INITIAL (decl))
 165             find_func_aliases (decl);
 166         }
 167     }
 168
 169   if (!current_alias_ops->ip)
 170     {
 171       if (!current_alias_ops->ip_partial
 172           || (TREE_CODE (decl) != FUNCTION_DECL
 173               && TREE_CODE (decl) != PARM_DECL))
 174         {
 175           VARRAY_PUSH_INT (local_alias_varnums, ALIAS_VAR_VARNUM (newvar));
 176           VARRAY_PUSH_TREE (local_alias_vars, decl);
 177         }
 178     }
 179   return newvar;
 180 }
 181
 182 /* Get the alias_var for an expression EXPR.
 183    Note that this function expects to only be handed a RHS or LHS, not
 184    a MODIFY_EXPR.  */
 185
 186 static alias_var
 187 get_alias_var (tree expr)
 188 {
 189   /* If it's a decl, get the alias var of the decl. We farm this off
 190      to get_alias_var_decl so it can abort if the alias var doesn't
 191      exist, and in case something else *knows* it has a decl, and
 192      wants the alias var.  */
 193
 194   if (DECL_P (expr))
 195     return get_alias_var_decl (expr);
 196
 197   /* True constants have no aliases (unless modifiable strings are on,
 198      in which case i don't think we'll end up with a STRING_CST anyway) */
 199   if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
 200     return NULL;
 201
 202
 203   switch (TREE_CODE (expr))
 204     {
 205     case ARRAY_REF:
 206     case ARRAY_RANGE_REF:
 207       {
 208         /* Find the first non-array ref, and return its alias variable.  */
 209         tree p;
 210
 211         for (p = expr;
 212              TREE_CODE (p) == ARRAY_REF || TREE_CODE (p) == ARRAY_RANGE_REF;
 213              p = TREE_OPERAND (p, 0))
 214           ;
 215         return get_alias_var (p);
 216       }
 217       break;
 218     case COMPONENT_REF:
 219       {
 220 #if FIELD_BASED
 221         bool safe = true;
 222         tree p;
 223         for (p = expr;
 224              TREE_CODE (p) == COMPONENT_REF || TREE_CODE (p) == INDIRECT_REF;
 225              p = TREE_OPERAND (p, 0))
 226           {
 227             if (TREE_CODE (TREE_TYPE (p)) == UNION_TYPE
 228                 || TREE_CODE (TREE_TYPE (p)) == QUAL_UNION_TYPE)
 229               {
 230                 safe = false;
 231                 break;
 232               }
 233           }
 234         if (!safe)
 235           {
 236             for (p = expr; TREE_CODE (p) == COMPONENT_REF;
 237                  p = TREE_OPERAND (p, 0));
 238             return get_alias_var (p);
 239           }
 240         else
 241           {
 242             return get_alias_var (TREE_OPERAND (expr, 1));
 243           }
 244 #else
 245         /* Find the first non-component ref, and return its alias variable.  */
 246         tree p;
 247         for (p = expr; TREE_CODE (p) == COMPONENT_REF;
 248              p = TREE_OPERAND (p, 0));
 249         return get_alias_var (p);
 250 #endif
 251       }
 252       break;
 253     case REALPART_EXPR:
 254     case IMAGPART_EXPR:
 255     case NOP_EXPR:
 256     case CONVERT_EXPR:
 257     case FIX_TRUNC_EXPR:
 258     case FIX_CEIL_EXPR:
 259     case FIX_FLOOR_EXPR:
 260     case FIX_ROUND_EXPR:
 261     case ADDR_EXPR:
 262     case INDIRECT_REF:
 263     case BIT_FIELD_REF:
 264       /* If it's a ref or cast or conversion of something, get the
 265          alias var of the something.  */
 266       return get_alias_var (TREE_OPERAND (expr, 0));
 267       break;
 268
 269     default:
 270       return NULL;
 271     }
 272 }
 273
 274 /*  Perform conservative aliasing for an intraprocedural mode function
 275     call.  ARGS are the arguments that were passed to that function
 276     call.  */
 277
 278 static void
 279 intra_function_call (varray_type args)
 280 {
 281   size_t l = VARRAY_ACTIVE_SIZE (args);
 282   size_t i;
 283   alias_var av = get_alias_var (pta_global_var);
 284
 285   /* We assume assignments among the actual parameters.  */
 286   for (i = 0; i < l; i++)
 287     {
 288       alias_var argi = VARRAY_GENERIC_PTR (args, i);
 289       size_t j;
 290       for (j = 0; j < l; j++)
 291         {
 292           alias_var argj;
 293           if (i == j)
 294             continue;
 295           argj = VARRAY_GENERIC_PTR (args, j);
 296           /* Restricted pointers can't be aliased with other
 297              restricted pointers.  */
 298           if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argi)))
 299               || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argj))))
 300             /* Do a bit of TBAA to avoid pointless assignments.  */
 301             if (alias_sets_conflict_p (get_alias_set (ALIAS_VAR_DECL (argi)),
 302                                        get_alias_set (ALIAS_VAR_DECL (argj))))
 303               current_alias_ops->simple_assign (current_alias_ops, argi, argj);
 304         }
 305     }
 306   /* We assume that an actual parameter can point to any global.  */
 307   for (i = 0; i < l; i++)
 308     {
 309       alias_var argav = VARRAY_GENERIC_PTR (args, i);
 310       /* Restricted pointers can't be aliased with other
 311          restricted pointers.  */
 312       if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argav)))
 313           || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (av))))
 314         {
 315           /* Arguments can alias globals, and whatever they point to
 316              can point to a global as well.  */
 317           current_alias_ops->simple_assign (current_alias_ops, argav, av);
 318         }
 319     }
 320 }
 321
 322 /* Put all pointers in a constructor in an array.  */
 323
 324 static void
 325 get_values_from_constructor (tree constructor, varray_type *vals,
 326                              bitmap addrargs, int *i)
 327 {
 328   tree elt_list;
 329   switch (TREE_CODE (constructor))
 330     {
 331     case CONSTRUCTOR:
 332       {
 333         for (elt_list = CONSTRUCTOR_ELTS (constructor);
 334              elt_list;
 335              elt_list = TREE_CHAIN (elt_list))
 336           {
 337             tree value = TREE_VALUE (elt_list);
 338             if (TREE_CODE (value) == TREE_LIST
 339                 || TREE_CODE (value) == CONSTRUCTOR)
 340               {
 341                 get_values_from_constructor (value, vals, addrargs, i);                       }
 342             else
 343               {
 344                 alias_var aav;
 345                 aav = get_alias_var (value);
 346                 if (aav)
 347                   VARRAY_PUSH_GENERIC_PTR (*vals, aav);
 348                 if (TREE_CODE (value) == ADDR_EXPR)
 349                   bitmap_set_bit (addrargs, *i);
 350                 *i = *i + 1;
 351               }
 352           }
 353       }
 354       break;
 355     case TREE_LIST:
 356       for (elt_list = constructor;
 357            elt_list;
 358            elt_list = TREE_CHAIN (elt_list))
 359         {
 360           get_values_from_constructor (TREE_VALUE (elt_list), vals, addrargs, i);
 361         }
 362       break;
 363     default:
 364       abort();
 365     }
 366 }
 367
 368 /* Deal with the possible return values of a call that we don't have
 369    actual PTA info about.  */
 370
 371 static void
 372 deal_with_call_aliasing (tree callargs, alias_var lhsAV)
 373 {
 374   tree arg, argp;
 375
 376   for (argp = callargs;
 377        argp;
 378        argp = TREE_CHAIN (argp))
 379     {
 380       arg = TREE_VALUE (argp);
 381       /* If we take the address of a variable directly in the
 382          argument, the return value could be the address of that
 383          variable.  */
 384       if (TREE_CODE (arg) == ADDR_EXPR)
 385         current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 386                                         get_alias_var (arg));
 387       /* If we pass in a pointer, we could return that pointer.  */
 388       else if (POINTER_TYPE_P (TREE_TYPE (arg)))
 389         {
 390           alias_var argtv = get_alias_var (arg);
 391           if (argtv)
 392             current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 393                                               argtv);
 394         }
 395     }
 396 }
 397
 398 /* Find the operand of the component ref that actually is doing
 399    something to the DECL  */
 400 static tree
 401 find_op_of_decl (tree cref)
 402 {
 403   while (!DECL_P (TREE_OPERAND (cref, 0)))
 404     {
 405       cref = TREE_OPERAND (cref, 0);
 406     }
 407   return cref;
 408 }
 409
 410
 411 /*  Tree walker that is the heart of the aliasing infrastructure.
 412     TP is a pointer to the current tree.
 413     WALK_SUBTREES specifies whether to continue traversing subtrees or
 414     not.
 415     Returns NULL_TREE when we should stop.
 416
 417     This function is the main part of the aliasing infrastructure. It
 418     walks the trees, calling the appropriate alias analyzer functions to process
 419     various statements.  */
 420
 421 static void
 422 find_func_aliases (tree stp)
 423 {
 424   if (TREE_CODE (stp) == RETURN_EXPR)
 425     {
 426       stp = TREE_OPERAND (stp, 0);
 427       if (!stp)
 428         return;
 429     }
 430
 431   if (TREE_CODE (stp) == MODIFY_EXPR
 432       || (DECL_P (stp) && DECL_INITIAL (stp) != NULL_TREE ))
 433     {
 434       tree op0, op1;
 435       alias_var lhsAV = NULL;
 436       alias_var rhsAV = NULL;
 437
 438       if (DECL_P (stp))
 439         {
 440           op0 = stp;
 441           op1 = DECL_INITIAL (stp);
 442         }
 443       else
 444         {
 445           op0 = TREE_OPERAND (stp, 0);
 446           op1 = TREE_OPERAND (stp, 1);
 447           if (TREE_CODE (op1) == WITH_SIZE_EXPR)
 448             op1 = TREE_OPERAND (op1, 0);
 449         }
 450
 451       /* lhsAV should always have an alias variable */
 452       lhsAV = get_alias_var (op0);
 453       if (!lhsAV)
 454         return;
 455       /* rhsAV might not have one, c.f. c = 5 */
 456       rhsAV = get_alias_var (op1);
 457 #if !FIELD_BASED
 458       while (TREE_CODE (op1) == COMPONENT_REF
 459              && TREE_CODE (TREE_OPERAND (op1, 0)) == COMPONENT_REF)
 460         {
 461           op1 = TREE_OPERAND (op1, 0);
 462         }
 463       while (TREE_CODE (op1) == BIT_FIELD_REF)
 464         {
 465           op1 = TREE_OPERAND (op1, 0);
 466         }
 467       /* Take care of fact that we may have multi-level component
 468          refs.  */
 469       if (TREE_CODE (op1) == COMPONENT_REF)
 470         op1 = find_op_of_decl (op1);
 471 #endif
 472
 473       /* You would think we could test rhsAV at the top, rather than
 474          50 separate times, but we can't, because it can be NULL for
 475          operator assignments, where we'd still collect the individual
 476          alias vars for the operator.  */
 477
 478       /* Note that structures are treated as a single alias
 479          variable, since we can disambiguate based on TBAA first,
 480          and fall back on points-to.  */
 481       /* x = <something> */
 482       if (is_gimple_variable (op0))
 483         {
 484           /* x = y */
 485           if (is_gimple_variable (op1))
 486             {
 487               if (rhsAV != NULL)
 488                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 489                                                   rhsAV);
 490             }
 491           /* x = foo.y */
 492           else if (TREE_CODE (op1) == COMPONENT_REF
 493                    && DECL_P (TREE_OPERAND (op1, 0)))
 494             {
 495                  if (rhsAV != NULL)
 496                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 497                                                   rhsAV);
 498             }
 499           /* x = (cast) [maybe-addr-expr] y */
 500           else if (is_gimple_cast (op1))
 501             {
 502               tree stripped_op1 = op1;
 503               STRIP_NOPS (stripped_op1);
 504               if (rhsAV != NULL)
 505                 {
 506                   if (TREE_CODE (stripped_op1) == ADDR_EXPR)
 507                     current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 508                                                     rhsAV);
 509                   else
 510                     current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 511                                                       rhsAV);
 512                 }
 513             }
 514           /* x = *y or x = foo->y */
 515           else if (TREE_CODE (op1) == INDIRECT_REF
 516                    || TREE_CODE (op1) == ARRAY_REF
 517                    || (TREE_CODE (op1) == COMPONENT_REF
 518                        && TREE_CODE (TREE_OPERAND (op1, 0)) == INDIRECT_REF))
 519             {
 520               if (rhsAV != NULL)
 521                 current_alias_ops->ptr_assign (current_alias_ops, lhsAV,
 522                                                rhsAV);
 523             }
 524           /* x = &y = x = &foo.y */
 525           else if (TREE_CODE (op1) == ADDR_EXPR)
 526             {
 527               if (rhsAV != NULL)
 528                 current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 529                                                 rhsAV);
 530             }
 531           /* x = func(...) */
 532           else if (TREE_CODE (op1) == CALL_EXPR)
 533             {
 534               /* Heap assignment. These are __attribute__ malloc or
 535                  something, I'll deal with it later.  */
 536               if (0)
 537                 {}
 538               else
 539                 {
 540
 541                   /* NORETURN functions have no effect on aliasing.  */
 542                   if (call_may_return (op1))
 543                     {
 544                       varray_type args;
 545                       tree arg;
 546                       tree callop0, callop1;
 547                       int argnum;
 548
 549                       /* Collect the arguments */
 550                       VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
 551                       bitmap_clear (addrargs);
 552                       callop1 = TREE_OPERAND (op1, 1);
 553                       callop0 = TREE_OPERAND (op1, 0);
 554                       for (arg = callop1, argnum = 0;
 555                            arg;
 556                            arg = TREE_CHAIN (arg), argnum++)
 557                         {
 558                           alias_var aav = get_alias_var (TREE_VALUE (arg));
 559                           if (aav)
 560                             {
 561                               VARRAY_PUSH_GENERIC_PTR (args, aav);
 562                               if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
 563                                 bitmap_set_bit (addrargs, argnum);
 564                             }
 565                         }
 566                       /* Simulate the call */
 567                       if (current_alias_ops->function_call (current_alias_ops, lhsAV,
 568                                                             get_alias_var (callop0),
 569                                                             args, addrargs))
 570                         {
 571                           if (call_may_clobber (op1)
 572                               && !current_alias_ops->ip
 573                               && flag_argument_noalias != 2)
 574                             {
 575                               intra_function_call (args);
 576                             }
 577                           if (POINTER_TYPE_P (TREE_TYPE (op0)))
 578                             deal_with_call_aliasing (callop1, lhsAV);
 579                         }
 580                     }
 581                 }
 582             }
 583           /* x = op (...) */
 584           else
 585             {
 586               bitmap_clear (addrargs);
 587               if (TREE_CODE (op1) == CONSTRUCTOR)
 588                 {
 589                   varray_type ops;
 590                   int i = 0;
 591                   VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
 592                   get_values_from_constructor (op1, &ops, addrargs, &i);
 593                   current_alias_ops->op_assign (current_alias_ops, lhsAV,
 594                                                 ops, op1, addrargs);
 595                 }
 596               else
 597                 switch (TREE_CODE_CLASS (TREE_CODE (op1)))
 598                   {
 599                   case 'e':  /* an expression */
 600                   case 's':  /* an expression with side effects */
 601                   case '<':  /* a comparison expression */
 602                   case '1':  /* a unary arithmetic expression */
 603                   case 'r':  /* a reference */
 604                   case '2':  /* a binary arithmetic expression */
 605                     {
 606                       tree op;
 607                       varray_type ops;
 608                       int i;
 609                       VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
 610                       for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (op1)); i++)
 611                         {
 612                           alias_var aav;
 613                           op = TREE_OPERAND (op1, i);
 614                           aav = get_alias_var (op);
 615                           if (aav)
 616                             VARRAY_PUSH_GENERIC_PTR (ops, aav);
 617                           if (TREE_CODE (op) == ADDR_EXPR)
 618                             bitmap_set_bit (addrargs, i);
 619                         }
 620                       current_alias_ops->op_assign (current_alias_ops, lhsAV,
 621                                                     ops, op1, addrargs);
 622                     }
 623                     break;
 624                   default:
 625                     break;
 626                   }
 627             }
 628         }
 629       /* *x = <something> */
 630       else
 631         {
 632           /* x.f = y  or x->f = y */
 633           if ((TREE_CODE (op0) == COMPONENT_REF
 634                || TREE_CODE (op0) == BIT_FIELD_REF)
 635               && is_gimple_variable (op1))
 636             {
 637               if (rhsAV != NULL)
 638                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 639                                                   rhsAV);
 640             }
 641           /* x.f = &y or x->f = &y */
 642           else if (TREE_CODE (op0) == COMPONENT_REF
 643                    && TREE_CODE (op1) == ADDR_EXPR)
 644             {
 645               if (rhsAV != NULL)
 646                 current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 647                                                 rhsAV);
 648             }
 649           /* *x.f = y or *x->f = y */
 650           else if ((TREE_CODE (op0) == INDIRECT_REF
 651                     || TREE_CODE (op0) == ARRAY_REF)
 652                    && TREE_CODE (TREE_OPERAND (op0, 0)) == COMPONENT_REF
 653                    && is_gimple_variable (op1))
 654             {
 655               if (rhsAV != NULL)
 656                 current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 657                                                rhsAV);
 658             }
 659           /* *x = &y */
 660           else if ((TREE_CODE (op0) == INDIRECT_REF
 661                     || TREE_CODE (op0) == ARRAY_REF)
 662                    && TREE_CODE (op1) == ADDR_EXPR)
 663             {
 664               /* This becomes temp = &y and *x = temp .  */
 665               alias_var tempvar;
 666               tree temp = create_tmp_var_raw (void_type_node, "aliastmp");
 667               tempvar = current_alias_ops->add_var (current_alias_ops, temp);
 668               current_alias_ops->addr_assign (current_alias_ops, tempvar,
 669                                               rhsAV);
 670               current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 671                                              tempvar);
 672             }
 673
 674           /* *x = *y */
 675           else if ((TREE_CODE (op0) == INDIRECT_REF
 676                     || TREE_CODE (op0) == ARRAY_REF)
 677                    && (TREE_CODE (op1) == INDIRECT_REF
 678                        || TREE_CODE (op1) == ARRAY_REF))
 679             {
 680               /* This becomes temp = *y and *x = temp .  */
 681               alias_var tempvar;
 682               tree temp;
 683               temp = create_tmp_var_raw (void_type_node, "aliastmp");
 684               tempvar = current_alias_ops->add_var (current_alias_ops, temp);
 685               current_alias_ops->ptr_assign (current_alias_ops, tempvar,
 686                                              rhsAV);
 687               current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 688                                              tempvar);
 689             }
 690
 691           /* *x = (cast) y */
 692           else if ((TREE_CODE (op0) == INDIRECT_REF
 693                     || TREE_CODE (op0) == ARRAY_REF)
 694                    && is_gimple_cast (op1))
 695             {
 696               if (rhsAV != NULL)
 697                 {
 698                   /* This becomes temp = (cast) y and  *x = temp.  */
 699                   alias_var tempvar;
 700                   tree temp;
 701                   temp = create_tmp_var_raw (void_type_node, "aliastmp");
 702                   tempvar = current_alias_ops->add_var (current_alias_ops,
 703                                                         temp);
 704                   current_alias_ops->simple_assign (current_alias_ops,
 705                                                     tempvar, rhsAV);
 706                   current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 707                                                  tempvar);
 708                 }
 709             }
 710           /* *x = <something else> */
 711           else
 712             {
 713               if (rhsAV != NULL)
 714                 current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 715                                                rhsAV);
 716             }
 717         }
 718     }
 719   /* Calls without return values.  */
 720   else if (TREE_CODE (stp) == CALL_EXPR)
 721     {
 722       alias_var callvar;
 723       varray_type args;
 724       tree arg;
 725       callvar = get_alias_var (TREE_OPERAND (stp, 0));
 726       if (callvar != NULL)
 727         {
 728
 729           /* NORETURN and CONST functions with no return value
 730              have no effect on aliasing (as may be seen above,
 731              const functions that return a value might have an
 732              effect on aliasing, since the return value can point
 733              to one of the arguments.  */
 734           if (call_may_clobber (stp))
 735             {
 736               int argnum;
 737               VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
 738               bitmap_clear (addrargs);
 739               for (arg = TREE_OPERAND (stp, 1), argnum=0;
 740                    arg;
 741                    arg = TREE_CHAIN (arg), argnum++)
 742                 {
 743                   alias_var aav = get_alias_var (TREE_VALUE (arg));
 744                   if (aav)
 745                     {
 746                       VARRAY_PUSH_GENERIC_PTR (args, aav);
 747                       if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
 748                         bitmap_set_bit (addrargs, argnum);
 749                     }
 750
 751                 }
 752
 753               if (current_alias_ops->function_call (current_alias_ops, NULL,
 754                                                     callvar, args, addrargs))
 755                 if (!current_alias_ops->ip && flag_argument_noalias != 2)
 756                   intra_function_call (args);
 757             }
 758         }
 759   }
 760 }
 761
 762 /*  Create the alias_var for a function definition DECL, it's
 763     arguments, and it's return value. If FORCE is true, we force
 764     creation of the alias_var, regardless of whether one exists already.
 765
 766     This includes creation of alias_var's for
 767     - The function itself.
 768     - The arguments.
 769     - The return value.  */
 770
 771 static alias_var
 772 create_fun_alias_var (tree decl, int force)
 773 {
 774   alias_var avar, retvar;
 775   tree rdecl;
 776   varray_type params = NULL;
 777
 778   if (!force)
 779     {
 780       if (DECL_PTA_ALIASVAR (decl))
 781         return DECL_PTA_ALIASVAR (decl);
 782     }
 783
 784   VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
 785   if (DECL_ARGUMENTS (decl) != NULL)
 786     {
 787       tree arg;
 788       for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
 789         {
 790           alias_var var = get_alias_var (arg);
 791           VARRAY_PUSH_GENERIC_PTR (params, var);
 792           /* Incoming pointers can point to pta_global_var, unless
 793              either we are interprocedural, or we can do ip on all
 794              statics + this function has been defined + it's not an
 795              external function.  */
 796           if (POINTER_TYPE_P (TREE_TYPE (arg))
 797               && !current_alias_ops->ip
 798               /* FIXME: Need to let analyzer decide in partial case.  */
 799               && (!current_alias_ops->ip_partial
 800                   || !cgraph_local_info (decl)->local))
 801             current_alias_ops->simple_assign (current_alias_ops, var,
 802                                               get_alias_var (pta_global_var));
 803         }
 804     }
 805   else if (TYPE_ARG_TYPES (TREE_TYPE (decl)) != NULL)
 806     {
 807       tree arg;
 808       /* FIXME: Handle varargs */
 809       for (arg = TYPE_ARG_TYPES (TREE_TYPE (decl));
 810            arg && TREE_VALUE (arg) != void_type_node;
 811            arg = TREE_CHAIN (arg))
 812         {
 813           tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "normarg");
 814           alias_var var;
 815           DECL_CONTEXT (fakedecl) = current_function_decl;
 816           var = get_alias_var (fakedecl);
 817           VARRAY_PUSH_GENERIC_PTR (params, var);
 818
 819           /* Incoming pointers can point to pta_global_var, unless
 820              either we are interprocedural, or we can do ip on all
 821              statics + this function has been defined + it's not an
 822              external function.  */
 823           if (POINTER_TYPE_P (TREE_TYPE (fakedecl))
 824               && !current_alias_ops->ip
 825               /* FIXME: need to let analyzer decide in partial case.  */
 826               && (!current_alias_ops->ip_partial
 827                   || !TREE_STATIC (decl)
 828                   || TREE_PUBLIC (decl)))
 829             current_alias_ops->simple_assign (current_alias_ops, var,
 830                                               get_alias_var (pta_global_var));
 831         }
 832     }
 833   /* Functions declared like void f() are *not* equivalent to void
 834      f(void). You can pass an argument to them. Thus, we need to
 835      create some fake argument that would alias any actuals that get
 836      passed to our function.  */
 837   else
 838     {
 839       tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
 840       alias_var fakevar;
 841       DECL_CONTEXT (fakedecl) = current_function_decl;
 842       fakevar = get_alias_var (fakedecl);
 843       VARRAY_PUSH_GENERIC_PTR (params, fakevar);
 844     }
 845
 846   if (!DECL_RESULT (decl))
 847     {
 848       rdecl = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (decl)), "_rv_");
 849       retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
 850       DECL_PTA_ALIASVAR (rdecl) = retvar;
 851     }
 852   else
 853     {
 854       retvar = current_alias_ops->add_var (current_alias_ops,
 855                                            DECL_RESULT (decl));
 856       DECL_PTA_ALIASVAR (DECL_RESULT (decl)) = retvar;
 857     }
 858   VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
 859   ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 860   avar = current_alias_ops->add_var (current_alias_ops, decl);
 861   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
 862   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 863
 864   current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
 865   DECL_PTA_ALIASVAR (decl) = avar;
 866
 867   /* FIXME: Also, if this is a defining declaration then add the annotation
 868      to all extern definitions of the function.  */
 869   return avar;
 870 }
 871
 872 /*  Create an alias variable for a pointer-to-member function DECL of
 873     type TYPE, it's arguments, and it's return value.
 874     Returns the alias_var for the PTF.
 875
 876     This includes creating alias_var's for
 877     - The function itself.
 878     - The arguments.
 879     - The return value.  */
 880
 881 static alias_var
 882 create_fun_alias_var_ptf (tree decl, tree type)
 883 {
 884   alias_var avar, retvar;
 885   tree rdecl;
 886   varray_type params = NULL;
 887
 888   if (DECL_PTA_ALIASVAR (decl))
 889     return DECL_PTA_ALIASVAR (decl);
 890
 891   VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
 892
 893   if (TYPE_ARG_TYPES  (type) != NULL)
 894     {
 895       tree arg;
 896       /* FIXME: Handle varargs */
 897       for (arg = TYPE_ARG_TYPES (type);
 898            arg && TREE_VALUE (arg) != void_type_node;
 899            arg = TREE_CHAIN (arg))
 900         {
 901           tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "ptfarg");
 902           alias_var var;
 903           DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
 904           var = get_alias_var (fakedecl);
 905           VARRAY_PUSH_GENERIC_PTR (params, var);
 906         }
 907     }
 908   /* Functions declared like void f() are *not* equivalent to void
 909      f(void). You can pass an argument to them. Thus, we need to
 910      create some fake argument that would alias any actuals that get
 911      passed to our function.  */
 912   else
 913     {
 914       tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
 915       alias_var fakevar;
 916       DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
 917       fakevar = get_alias_var (fakedecl);
 918       VARRAY_PUSH_GENERIC_PTR (params, fakevar);
 919     }
 920
 921   rdecl = create_tmp_var_raw (TREE_TYPE (type), "_rv_");
 922   retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
 923   VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
 924   ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 925
 926   avar = current_alias_ops->add_var (current_alias_ops, decl);
 927   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
 928   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 929
 930   current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
 931   DECL_PTA_ALIASVAR (decl) = avar;
 932
 933   return avar;
 934 }
 935
 936 /*  Create the alias_var for a *_DECL node DECL.
 937     Returns the alias_var for DECL.
 938
 939     This function also handles creation of alias_var's for PTF
 940     variables.  */
 941
 942 static alias_var
 943 create_alias_var (tree decl)
 944 {
 945   alias_var avar;
 946
 947   if (!DECL_P (decl))
 948     abort ();
 949
 950   if (DECL_P (decl))
 951     {
 952       if (DECL_PTA_ALIASVAR (decl))
 953         return DECL_PTA_ALIASVAR (decl);
 954     }
 955
 956   if (POINTER_TYPE_P (TREE_TYPE (decl))
 957       && TREE_CODE (TREE_TYPE (TREE_TYPE (decl))) == FUNCTION_TYPE)
 958     {
 959       avar = create_fun_alias_var_ptf (decl, TREE_TYPE (TREE_TYPE (decl)));
 960     }
 961   else
 962     avar = current_alias_ops->add_var (current_alias_ops, decl);
 963
 964   if (DECL_P (decl))
 965     {
 966       DECL_PTA_ALIASVAR (decl) = avar;
 967     }
 968
 969   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
 970   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 971   return avar;
 972 }
 973
 974 /* Create points-to sets for the current function.  */
 975
 976 static void
 977 create_alias_vars (void)
 978 {
 979   basic_block bb;
 980 #if HAVE_BANSHEE
 981   if (flag_tree_points_to == PTA_ANDERSEN)
 982     current_alias_ops = andersen_alias_ops;
 983   else
 984 #endif
 985    {
 986      current_alias_ops = NULL;
 987      flag_tree_points_to = PTA_NONE;
 988      return;
 989    }
 990
 991   pta_global_var = build_decl (VAR_DECL, get_identifier (".pta_global_var"),
 992                                size_type_node);
 993   DECL_ARTIFICIAL (pta_global_var) = 1;
 994   TREE_READONLY (pta_global_var) = 1;
 995   DECL_EXTERNAL (pta_global_var) = 0;
 996   TREE_STATIC (pta_global_var) = 1;
 997   TREE_USED (pta_global_var) = 1;
 998   DECL_CONTEXT (pta_global_var) = current_function_decl;
 999   TREE_THIS_VOLATILE (pta_global_var) = 1;
1000   TREE_ADDRESSABLE (pta_global_var) = 0;
1001
1002   init_alias_vars ();
1003
1004   DECL_PTA_ALIASVAR (current_function_decl) = NULL;
1005   get_alias_var (current_function_decl);
1006
1007   /* First, walk the variables and their DECL_INITIAL's */
1008   if (cfun->unexpanded_var_list)
1009     {
1010       tree vars, var;
1011       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
1012         {
1013           var = TREE_VALUE (vars);
1014           if (TREE_CODE (var) != LABEL_DECL
1015               && TREE_STATIC (var)
1016               && DECL_INITIAL (var))
1017             find_func_aliases (var);
1018         }
1019     }
1020
1021   /* Now walk all statements and derive aliases.  */
1022   FOR_EACH_BB (bb)
1023     {
1024       block_stmt_iterator bsi;
1025       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1026         find_func_aliases (bsi_stmt (bsi));
1027     }
1028
1029   pta_global_var = NULL_TREE;
1030 }
1031
1032 static bool
1033 gate_pta (void)
1034 {
1035 #ifdef HAVE_BANSHEE
1036   return flag_tree_points_to != PTA_NONE;
1037 #else
1038   return false;
1039 #endif
1040 }
1041
1042 struct tree_opt_pass pass_build_pta =
1043 {
1044   "pta",                                /* name */
1045   gate_pta,                             /* gate */
1046   create_alias_vars,                    /* execute */
1047   NULL,                                 /* sub */
1048   NULL,                                 /* next */
1049   0,                                    /* static_pass_number */
1050   TV_TREE_PTA,                          /* tv_id */
1051   PROP_cfg,                             /* properties_required */
1052   PROP_pta,                             /* properties_provided */
1053   0,                                    /* properties_destroyed */
1054   0,                                    /* todo_flags_start */
1055   0                                     /* todo_flags_finish */
1056 };
1057
1058
1059 /* Delete created points-to sets.  */
1060
1061 static void
1062 delete_alias_vars (void)
1063 {
1064   size_t i;
1065
1066   for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_vars); i++)
1067     {
1068       tree key = VARRAY_TREE (local_alias_vars, i);
1069       if (DECL_P (key))
1070         DECL_PTA_ALIASVAR (key) = NULL;
1071       else
1072         abort ();
1073     }
1074
1075   for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_varnums); i ++)
1076     VARRAY_GENERIC_PTR (alias_vars, VARRAY_INT (local_alias_varnums, i)) = NULL;
1077   if (!current_alias_ops->ip && !current_alias_ops->ip_partial)
1078     {
1079       /*      VARRAY_CLEAR (alias_vars); */
1080       VARRAY_CLEAR (local_alias_vars);
1081       VARRAY_CLEAR (local_alias_varnums);
1082     }
1083   BITMAP_XFREE (addrargs);
1084   current_alias_ops->cleanup (current_alias_ops);
1085 }
1086
1087 struct tree_opt_pass pass_del_pta =
1088 {
1089   "pta",                                /* name */
1090   gate_pta,                             /* gate */
1091   delete_alias_vars,                    /* execute */
1092   NULL,                                 /* sub */
1093   NULL,                                 /* next */
1094   0,                                    /* static_pass_number */
1095   TV_TREE_PTA,                          /* tv_id */
1096   PROP_pta,                             /* properties_required */
1097   0,                                    /* properties_provided */
1098   PROP_pta,                             /* properties_destroyed */
1099   0,                                    /* todo_flags_start */
1100   0                                     /* todo_flags_finish */
1101 };
1102
1103
1104 /*  Initialize points-to analysis machinery.  */
1105
1106 void
1107 init_alias_vars (void)
1108 {
1109   current_alias_ops->init (current_alias_ops);
1110   addrargs = BITMAP_XMALLOC ();
1111   VARRAY_TREE_INIT (local_alias_vars, 10, "Local alias vars");
1112   VARRAY_INT_INIT (local_alias_varnums, 10, "Local alias varnums");
1113   if ((!current_alias_ops->ip && !current_alias_ops->ip_partial)
1114       || alias_vars == NULL)
1115     VARRAY_GENERIC_PTR_INIT (alias_vars, 10, "Alias vars");
1116 }
1117
1118 /* Return true if PTR can't point to anything (i.e. it has an empty
1119    points-to set.  */
1120 bool
1121 empty_points_to_set (tree ptr)
1122 {
1123  alias_var ptrtv;
1124
1125 #if !FIELD_BASED
1126 #else
1127   if (TREE_CODE (ptr) == COMPONENT_REF)
1128     ptr = TREE_OPERAND (ptr, 1);
1129 #endif
1130
1131   if (DECL_P (ptr))
1132     {
1133       ptrtv = DECL_PTA_ALIASVAR (ptr);
1134       if (!ptrtv)
1135         return true;
1136     }
1137   else
1138     abort ();
1139
1140   return current_alias_ops->empty_points_to_set (current_alias_ops, ptrtv);
1141 }
1142
1143 /* Return true if PTR and VAR have the same points-to set.  */
1144
1145 bool
1146 same_points_to_set (tree ptr, tree var)
1147 {
1148   alias_var ptrtv, vartv;
1149
1150 #if !FIELD_BASED
1151 #else
1152   if (TREE_CODE (ptr) == COMPONENT_REF)
1153     ptr = TREE_OPERAND (ptr, 1);
1154   if (TREE_CODE (var) == COMPONENT_REF)
1155     var = TREE_OPERAND (var, 1);
1156 #endif
1157
1158   if (ptr == var)
1159     return true;
1160
1161   if (DECL_P (ptr))
1162     {
1163       ptrtv = DECL_PTA_ALIASVAR (ptr);
1164       if (!ptrtv)
1165         return false;
1166     }
1167   else
1168     abort ();
1169
1170   if (DECL_P (var))
1171     {
1172       vartv = DECL_PTA_ALIASVAR (var);
1173       if (!vartv)
1174         return false;
1175     }
1176   else
1177     abort ();
1178
1179   return current_alias_ops->same_points_to_set (current_alias_ops, vartv, ptrtv);
1180 }
1181
1182 /*  Determine whether two variables (PTR and VAR) may-alias.
1183     Returns TRUE if PTR may-alias VAR.  */
1184
1185 bool
1186 ptr_may_alias_var (tree ptr, tree var)
1187 {
1188   alias_var ptrtv, vartv;
1189
1190 #if !FIELD_BASED
1191 #else
1192   if (TREE_CODE (ptr) == COMPONENT_REF)
1193     ptr = TREE_OPERAND (ptr, 1);
1194   if (TREE_CODE (var) == COMPONENT_REF)
1195     var = TREE_OPERAND (var, 1);
1196 #endif
1197
1198   if (ptr == var)
1199     return true;
1200
1201   if (DECL_P (ptr))
1202     {
1203       ptrtv = DECL_PTA_ALIASVAR (ptr);
1204       if (!ptrtv)
1205         return false;
1206     }
1207   else
1208     abort ();
1209
1210   if (DECL_P (var))
1211     {
1212       vartv = DECL_PTA_ALIASVAR (var);
1213       if (!vartv)
1214         return false;
1215     }
1216   else
1217     abort ();
1218
1219   return current_alias_ops->may_alias (current_alias_ops, ptrtv, vartv);
1220 }
1221
1222 #define MASK_POINTER(P) ((unsigned)((unsigned long)(P) & 0xffff))
1223
1224 const char *
1225 alias_get_name (tree t)
1226 {
1227   const char *name;
1228
1229 #if FIELD_BASED
1230   if (TREE_CODE (t) == FIELD_DECL)
1231     {
1232       /* First get the name of the field, then the prefix, then smash them
1233          together.  */
1234       const char *fieldname = IDENTIFIER_POINTER (DECL_NAME (t));
1235       const char *prefix = alias_get_name (DECL_CONTEXT (t));
1236       char *smashed;
1237       size_t neededlen = strlen (fieldname) + strlen (prefix) + 2;
1238       smashed = ggc_alloc (neededlen);
1239       sprintf (smashed, "%s.%s", prefix, fieldname);
1240       name = smashed;
1241
1242     }
1243   else if (TYPE_P (t))
1244     {
1245       if (TYPE_NAME (t) && IDENTIFIER_POINTER (TYPE_NAME (t)))
1246         name = IDENTIFIER_POINTER (TYPE_NAME (t));
1247       else
1248         name = "<unnamed type>";
1249     }
1250   else
1251 #endif
1252     {
1253       if (TREE_CODE (t) == FUNCTION_DECL)
1254         name = IDENTIFIER_POINTER (DECL_NAME (t));
1255       else if (TREE_CODE (t) == RESULT_DECL)
1256         name = "<return value>";
1257       else
1258         name = get_name (t);
1259     }
1260
1261   if (!name)
1262     {
1263       char *namep;
1264       /* 2 = UF
1265          4 = the masked pointer
1266          2 = the <> around it
1267          1 = the terminator.  */
1268       namep = ggc_alloc (2 + 4 + 2 + 1);
1269       sprintf (namep, "<UV%x>", MASK_POINTER (t));
1270       return namep;
1271     }
1272
1273   return name;
1274 }
1275
1276 #include "gt-tree-alias-common.h"