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