gcc/tree-alias-ander.c

   1 /* Tree based Andersen 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
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "ggc.h"
  28 #include "bitmap.h"
  29 #include "tree-alias-type.h"
  30 #include "tree-alias-ander.h"
  31 #include "flags.h"
  32 #include "rtl.h"
  33 #include "tm_p.h"
  34 #include "hard-reg-set.h"
  35 #include "basic-block.h"
  36 #include "output.h"
  37 #include "errors.h"
  38 #include "expr.h"
  39 #include "diagnostic.h"
  40 #include "tree.h"
  41 #include "tree-flow.h"
  42 #include "tree-inline.h"
  43 #include "varray.h"
  44 #include "tree-gimple.h"
  45 #include "splay-tree.h"
  46 #include "engine/util.h"
  47 #include "libcompat/regions.h"
  48 #include "andersen_terms.h"
  49 #include "cgraph.h"
  50 #include "tree-pass.h"
  51
  52
  53 /*  Andersen's interprocedural points-to analysis.
  54     This is a flow-insensitive, context insensitive algorithm.
  55
  56     This file is an implementation of the alias_ops structure used by
  57     tree-alias-common.c to drive PTA analysis.
  58
  59     All these functions do is generate constraints for and through
  60     libbanshee. When we query for a points-to set, we ask libbanshee
  61     to solve the constraints and give us the answer.  The terms of the
  62     constraints are the aterms, which are an opaque data structure
  63     that stores libbanshee specific data for the constraints.
  64
  65     The constraints to be generated come from andersen's paper. By
  66     constraint, we mean something like "the points-to set of A must be
  67     a subset or equal to the points-to set of B" or "the points-to set
  68     of A must include Q".  In order to avoid having to write all the
  69     constraints directly in the code, we use helper functions such as
  70     pta_assignment, pta_rvalue, etc, that generate the necessary
  71     constraint terms  for us, making for much more readable code.
  72
  73     One could replace libbanshee with some other constraint solving
  74     engine, and you'd simply have to replace the implementation of the
  75     pta_* functions, and provide replacements for the aterm specific
  76     functions (like making a list of aterms, printing the label of an
  77     aterm).  However, libbanshee is extremely fast, and extremely low
  78     memory usage, so one would be hard pressed to do better than it
  79     anyway.
  80
  81     Understanding how constraint solving and what each constraint means is
  82     beyond the scope of this documentation.  See the libbanshee
  83     documentation, and references therein for more enlightenment.
  84
  85     That said, our constraints inclusion constraints of set
  86     expressions.  Given the helper functions, the various inference
  87     functions we implement should *look* relatively straightforward.
  88
  89     In order to save time during queries, we cache the resulting
  90     points-to sets of each variable, rather than recalculate them
  91     again and again. (libbanshee actually has it's own internal
  92     caching, but the function call overhead for calling the solver is
  93     non-trivial, given the number of queries).
  94
  95     Todo: Don't pass alias ops as first argument, just have a global
  96     "current_alias_ops".  */
  97
  98 static unsigned int id_num = 1;
  99 static region andersen_rgn;
 100 static void andersen_simple_assign (struct tree_alias_ops *,
 101                                     alias_var, alias_var);
 102 static void andersen_addr_assign (struct tree_alias_ops *,
 103                                   alias_var, alias_var);
 104 static void andersen_ptr_assign (struct tree_alias_ops *,
 105                                  alias_var, alias_var);
 106 static void andersen_op_assign (struct tree_alias_ops *,
 107                                 alias_var, varray_type, tree, bitmap);
 108 static void andersen_heap_assign (struct tree_alias_ops *, alias_var);
 109 static void andersen_assign_ptr (struct tree_alias_ops *,
 110                                  alias_var, alias_var);
 111 static void andersen_function_def (struct tree_alias_ops *, alias_var,
 112                                    varray_type, alias_var);
 113 static int andersen_function_call (struct tree_alias_ops *, alias_var,
 114                                    alias_var, varray_type, bitmap);
 115 static void andersen_init (struct tree_alias_ops *);
 116 static int print_out_result (splay_tree_node, void *);
 117 static void andersen_cleanup (struct tree_alias_ops *);
 118 static bool andersen_may_alias (struct tree_alias_ops *, alias_var,
 119                                 alias_var);
 120 static bool andersen_same_points_to_set (struct tree_alias_ops *,
 121                                          alias_var, alias_var);
 122 static bool andersen_empty_points_to_set (struct tree_alias_ops *,
 123                                           alias_var);
 124 static alias_var andersen_add_var (struct tree_alias_ops *, tree);
 125 static alias_var andersen_add_var_same (struct tree_alias_ops *,
 126                                             tree, alias_var);
 127 static bool pointer_destroying_op (tree);
 128 static aterm_list get_ptset (alias_var);
 129 static splay_tree ptamap;
 130
 131
 132 static struct tree_alias_ops andersen_ops = {
 133   andersen_init,
 134   andersen_cleanup,
 135   andersen_add_var,
 136   andersen_add_var_same,
 137   andersen_simple_assign,
 138   andersen_addr_assign,
 139   andersen_ptr_assign,
 140   andersen_op_assign,
 141   andersen_heap_assign,
 142   andersen_assign_ptr,
 143   andersen_function_def,
 144   andersen_function_call,
 145   andersen_may_alias,
 146   andersen_same_points_to_set,
 147   andersen_empty_points_to_set,
 148   0, /* data */
 149   0, /* Currently non-interprocedural */
 150   1  /* Can do IP on all statics without help.  */
 151 };
 152 struct tree_alias_ops *andersen_alias_ops = &andersen_ops;
 153
 154 static void term_inclusion (aterm, aterm);
 155 static void pta_init (void);
 156 static void pta_reset (void);
 157 static aterm get_ref (aterm);
 158 static argterm fun_rec_aterm (aterm_list);
 159 static aterm pta_make_lam (const char *, aterm, aterm_list);
 160 static aterm pta_make_ref (const char *);
 161 static aterm pta_bottom (void);
 162 static aterm pta_join (aterm, aterm);
 163 static aterm pta_deref (aterm);
 164 static aterm pta_rvalue (aterm);
 165 static aterm pta_address (aterm);
 166 static void pta_assignment (aterm, aterm);
 167 static aterm pta_make_fun (const char *, aterm, aterm_list);
 168 static aterm pta_application (aterm, aterm_list);
 169
 170 typedef aterm contents_type;
 171 static contents_type pta_get_contents (aterm);
 172 static void pr_ptset_aterm_elem (aterm);
 173 static void pta_pr_ptset (contents_type);
 174
 175 /* Hook for debugging.  This function is called instead of
 176    aterm_inclusion, and lets us print the actual constraints as they
 177    are generated.  */
 178
 179 static void
 180 term_inclusion (aterm t1, aterm t2)
 181 {
 182   if (dump_file)
 183     {
 184       fprintf (dump_file, "Constraint: ");
 185       aterm_print (dump_file, t1);
 186       fprintf (dump_file, " <= ");
 187       aterm_print (dump_file, t2);
 188       fprintf (dump_file,  "\n");
 189     }
 190
 191   aterm_inclusion (t1, t2);
 192 }
 193
 194 /* Initialize libbanshee's constraint engine.  */
 195
 196 static void
 197 pta_init (void)
 198 {
 199   andersen_terms_init ();
 200 }
 201
 202 /* Reset libbanshee's constraint engine.  We do this when we are done
 203    using it, as it releases the memory libbanshee is using.  */
 204
 205 static void
 206 pta_reset (void)
 207 {
 208   andersen_terms_reset ();
 209 }
 210
 211 static aterm
 212 get_ref (aterm t)
 213 {
 214   struct ref_decon r_decon;
 215   r_decon = ref_decon (t);
 216
 217   assert (r_decon.f1);
 218
 219   return r_decon.f1;
 220 }
 221
 222 /* Make a function record out of the arguments.  */
 223
 224 static argterm
 225 fun_rec_aterm (aterm_list args)
 226 {
 227   region scratch;
 228   int counter = 0;
 229   argterm rest, result;
 230   aterm_list_scanner scan;
 231   aterm temp;
 232   char field_name[512];
 233   argterm_map map;
 234
 235   scratch = newregion ();
 236   map = new_argterm_map (scratch);
 237   aterm_list_scan (args, &scan);
 238   while (aterm_list_next (&scan, &temp))
 239     {
 240       snprintf (field_name, 512, "%d", counter++);
 241       argterm_map_cons (argterm_make_field (field_name, temp), map);
 242     }
 243
 244   rest = argterm_wild ();
 245   /* rest = argterm_fresh(); */
 246
 247   /*  safe since field_add makes a copy of the string*/
 248   result = argterm_row (map, rest);
 249
 250   deleteregion (scratch);
 251
 252   return result;
 253 }
 254
 255
 256 static aterm
 257 pta_make_lam (const char *id, aterm ret, aterm_list args)
 258 {
 259   return lam (label_term_constant (id), fun_rec_aterm (args), ret);
 260 }
 261
 262 /* Make a label reference to the given id.  */
 263
 264 static aterm
 265 pta_make_ref (const char *id)
 266 {
 267
 268   aterm var = aterm_fresh (id);
 269
 270   label_term tag = label_term_constant (id);
 271
 272   return ref (tag, var, var);
 273 }
 274
 275 /* Return the empty set.  */
 276
 277 static aterm
 278 pta_bottom (void)
 279 {
 280   return aterm_zero ();
 281 }
 282
 283 /* Join two terms, such that anything in set t1 will also be in set
 284    t2, and vice versa.  */
 285
 286 static aterm
 287 pta_join (aterm t1, aterm t2)
 288 {
 289   aterm result;
 290   region scratch_rgn = newregion ();
 291   aterm_list list = new_aterm_list (scratch_rgn);
 292
 293   aterm_list_cons (t1, list);
 294   aterm_list_cons (t2, list);
 295
 296
 297   result = aterm_union (list);
 298   deleteregion (scratch_rgn);
 299
 300   return result;
 301 }
 302
 303 /* Generate the constraint for a dereference of term t1.  */
 304
 305 static aterm
 306 pta_deref (aterm t1)
 307 {
 308   return ref_proj2 (t1);
 309 }
 310
 311 /* Generate the constraint for t1 being an rvalue.  */
 312
 313 static aterm
 314 pta_rvalue (aterm t1)
 315 {
 316   return pta_deref (t1);
 317 }
 318
 319 /* Generate the constraint for taking the address of t1.  */
 320
 321 static aterm
 322 pta_address (aterm t1)
 323 {
 324   return ref (label_term_one (), aterm_one (), t1);
 325 }
 326
 327 /* Generate the constraint for assigning t2 to t1.  */
 328
 329 static void
 330 pta_assignment (aterm t1, aterm t2)
 331 {
 332   term_inclusion (t1, ref_pat1 (t2));
 333 }
 334
 335 /* Make a function from the given name, return value, and arguments.  */
 336
 337 static aterm
 338 pta_make_fun (const char *name, aterm ret, aterm_list args)
 339 {
 340   aterm temp;
 341   aterm_list_scanner scan;
 342   region scratch_rgn = newregion ();
 343   aterm_list arg_list = new_aterm_list (scratch_rgn);
 344
 345   aterm_list_scan (args, &scan);
 346
 347   while (aterm_list_next (&scan, &temp))
 348     {
 349       aterm_list_cons (get_ref (temp), arg_list);
 350     }
 351
 352   return pta_make_lam (name, get_ref (ret), arg_list);
 353 }
 354
 355 /* Return the constraint for calling function T with arguments
 356    ACTUALS.  */
 357
 358 static aterm
 359 pta_application (aterm t, aterm_list actuals)
 360 {
 361   argterm args = fun_rec_aterm (actuals);
 362
 363   term_inclusion (t, lam_pat1 (args));
 364   return pta_address (lam_proj2 (t));
 365 }
 366
 367 /* Return the contents of set expression T.  */
 368
 369 static contents_type
 370 pta_get_contents (aterm t)
 371 {
 372   struct ref_decon t_decon;
 373   t_decon = ref_decon (t);
 374
 375   return t_decon.f1;
 376 }
 377
 378 /* Print out a points-to set element.  */
 379
 380 static void
 381 pr_ptset_aterm_elem (aterm t)
 382 {
 383   struct ref_decon ref;
 384   struct lam_decon lam;
 385
 386   ref = ref_decon (t);
 387   lam = lam_decon (t);
 388
 389   fprintf (dump_file, ",");
 390   if (ref.f0)
 391     label_term_print (dump_file, ref.f0);
 392   else if (lam.f0)
 393     label_term_print (dump_file, lam.f0);
 394 }
 395
 396
 397 /* Print out a points-to set.  */
 398
 399 static void
 400 pta_pr_ptset (contents_type t)
 401 {
 402   int size;
 403   region scratch_rgn;
 404   aterm_list ptset;
 405   scratch_rgn = newregion ();
 406   ptset = aterm_list_copy (scratch_rgn, aterm_tlb (t));
 407
 408   size = aterm_list_length (ptset);
 409
 410   fprintf (dump_file, "{");
 411   if (!aterm_list_empty (ptset))
 412     {
 413       struct ref_decon ref;
 414       struct lam_decon lam;
 415       ref = ref_decon (aterm_list_head (ptset));
 416       lam = lam_decon (aterm_list_head (ptset));
 417       if (ref.f0)
 418         label_term_print (dump_file, ref.f0);
 419       else if (lam.f0)
 420         label_term_print (dump_file, lam.f0);
 421
 422       /*      aterm_pr(stdout,aterm_hd(ptset)); */
 423       ptset = aterm_list_tail (ptset);
 424     }
 425   aterm_list_app (ptset, pr_ptset_aterm_elem);
 426   fprintf (dump_file, "}(%d)\n", size);
 427   deleteregion (scratch_rgn);
 428 }
 429
 430 /* Initialize Andersen alias analysis.  */
 431 static int initted = 0;
 432
 433 static void
 434 andersen_init (struct tree_alias_ops *ops ATTRIBUTE_UNUSED)
 435 {
 436 #if 0
 437   /* Don't claim we can do ip partial unless we have unit_at_a_time on.  */
 438   if (!flag_unit_at_a_time)
 439 #endif
 440     andersen_ops.ip_partial = 0;
 441   if (!initted || (!andersen_ops.ip_partial && !andersen_ops.ip))
 442     {
 443       pta_init ();
 444       andersen_rgn = newregion ();
 445       initted = 1;
 446     }
 447
 448   ptamap = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
 449
 450 }
 451
 452 static int
 453 print_out_result (splay_tree_node node, void *data ATTRIBUTE_UNUSED)
 454 {
 455   fprintf (dump_file, "%s :=",
 456            alias_get_name (ALIAS_VAR_DECL (((alias_var) node->value))));
 457   pta_pr_ptset (pta_get_contents ((aterm) node->key));
 458   return 0;
 459 }
 460
 461 /* Cleanup after Andersen alias analysis.  */
 462
 463 static void
 464 andersen_cleanup (struct tree_alias_ops *ops ATTRIBUTE_UNUSED)
 465 {
 466   if (dump_file)
 467     {
 468       if (dump_flags & TDF_STATS)
 469         {
 470           fprintf (dump_file, "\nPoints-to stats:\n");
 471           andersen_terms_stats (dump_file);
 472         }
 473
 474       fprintf (dump_file, "\nPoints-to sets:\n");
 475       splay_tree_foreach (ptamap, print_out_result, NULL);
 476     }
 477
 478   splay_tree_delete (ptamap);
 479
 480   if (!andersen_ops.ip_partial && !andersen_ops.ip)
 481     {
 482       pta_reset ();
 483       deleteregion (andersen_rgn);
 484       andersen_rgn = NULL;
 485     }
 486 }
 487
 488 /* Add decl to the analyzer, and return a var for it.  For
 489    Andersen, we create a new alias var for the declaration, and
 490    return that.  */
 491
 492 static alias_var
 493 andersen_add_var (struct tree_alias_ops *ops ATTRIBUTE_UNUSED, tree decl)
 494 {
 495   alias_var ret;
 496   if (dump_file && (dump_flags & TDF_DETAILS))
 497     fprintf (dump_file, "Adding variable %s\n",
 498              alias_get_name (decl));
 499
 500   if (alias_get_name (decl) != NULL)
 501     {
 502       ret = alias_var_new_with_aterm (decl,
 503                                        pta_make_ref (alias_get_name (decl)));
 504     }
 505   else
 506     {
 507       char *tmp_name;
 508       ASM_FORMAT_PRIVATE_NAME (tmp_name, "unnamed var", id_num++);
 509       ret = alias_var_new_with_aterm (decl, pta_make_ref (tmp_name));
 510     }
 511   splay_tree_insert (ptamap, (splay_tree_key) ALIAS_VAR_ATERM (ret),
 512                      (splay_tree_value) ret);
 513   ALIAS_VAR_PTSET (ret) = NULL;
 514
 515   return ret;
 516 }
 517
 518 /* Add a variable to the analyzer that is equivalent (as far as
 519    aliases go) to some existing alias variable.
 520    For Andersen, we just call a function that does this for us.  */
 521
 522 static alias_var
 523 andersen_add_var_same (struct tree_alias_ops *ops ATTRIBUTE_UNUSED, tree decl,
 524                        alias_var tv)
 525 {
 526   alias_var ret;
 527
 528   if (dump_file && (dump_flags & TDF_DETAILS))
 529     fprintf (dump_file, "Adding variable %s same as %s\n",
 530              alias_get_name (decl), alias_get_name (ALIAS_VAR_DECL (tv)));
 531
 532   if (alias_get_name (decl) != NULL)
 533     ret = alias_var_new_with_aterm (decl,
 534                                      pta_make_ref (alias_get_name (decl)));
 535   else
 536     {
 537       char *tmp_name;
 538       ASM_FORMAT_PRIVATE_NAME (tmp_name, "unnamed var", id_num++);
 539       ret = alias_var_new_with_aterm (decl, pta_make_ref (tmp_name));
 540     }
 541
 542   pta_join (ALIAS_VAR_ATERM (tv), ALIAS_VAR_ATERM (ret));
 543   splay_tree_insert (ptamap, (splay_tree_key) ALIAS_VAR_ATERM (ret),
 544                      (splay_tree_value) ret);
 545   ALIAS_VAR_PTSET (tv) = NULL;
 546   ALIAS_VAR_PTSET (ret) = NULL;
 547
 548   return ret;
 549 }
 550
 551 /* Inference for simple assignment (lhs = rhs) */
 552
 553 static void
 554 andersen_simple_assign (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 555                         alias_var lhs, alias_var rhs)
 556 {
 557   if (dump_file && (dump_flags & TDF_DETAILS))
 558     fprintf (dump_file, "Simple assignment %s = %s\n",
 559              alias_get_name (ALIAS_VAR_DECL (lhs)),
 560              alias_get_name (ALIAS_VAR_DECL (rhs)));
 561   if (lhs == rhs)
 562     return;
 563
 564   /* The rvalue is just the term itself, and we generate a constraint
 565      for assigning it to the lhs.  */
 566   pta_assignment (ALIAS_VAR_ATERM (lhs),
 567                   pta_rvalue (ALIAS_VAR_ATERM (rhs)));
 568 }
 569
 570 /* Inference for address assignment (lhs = &addr) */
 571
 572 static void
 573 andersen_addr_assign (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 574                       alias_var lhs, alias_var addr)
 575 {
 576   if (addr == NULL)
 577     return;
 578  if (dump_file && (dump_flags & TDF_DETAILS))
 579    fprintf (dump_file, "Address assignment %s = &%s\n",
 580             alias_get_name (ALIAS_VAR_DECL (lhs)),
 581             alias_get_name (ALIAS_VAR_DECL (addr)));
 582
 583  /* The rvalue here is the address of a term, and we generate a
 584     constraint to assign this address to the lhs.  */
 585   pta_assignment (ALIAS_VAR_ATERM (lhs),
 586                   pta_rvalue (pta_address (ALIAS_VAR_ATERM (addr))));
 587 }
 588
 589
 590 /* Inference for pointer assignment (lhs = *ptr) */
 591
 592 static void
 593 andersen_ptr_assign (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 594                      alias_var lhs, alias_var ptr)
 595 {
 596
 597   if (ptr == NULL)
 598     return;
 599  if (dump_file && (dump_flags & TDF_DETAILS))
 600    fprintf (dump_file, "Pointer assignment %s = *%s\n",
 601             alias_get_name (ALIAS_VAR_DECL (lhs)),
 602             alias_get_name (ALIAS_VAR_DECL (ptr)));
 603
 604   pta_assignment (ALIAS_VAR_ATERM (lhs),
 605                   pta_rvalue (pta_deref (ALIAS_VAR_ATERM (ptr))));
 606
 607 }
 608
 609 /* Determine if OP destroys the current assumed to be valid pointer
 610    (whether it generates a new valid pointer is not relevant).  */
 611
 612 static bool
 613 pointer_destroying_op (tree op)
 614 {
 615   switch (TREE_CODE (op))
 616     {
 617     case TRUTH_AND_EXPR:
 618     case TRUTH_OR_EXPR:
 619     case TRUTH_NOT_EXPR:
 620     case LT_EXPR:
 621     case GT_EXPR:
 622     case GE_EXPR:
 623     case LE_EXPR:
 624     case EQ_EXPR:
 625     case NE_EXPR:
 626     case MULT_EXPR:
 627     case TRUNC_DIV_EXPR:
 628     case LSHIFT_EXPR:
 629     case RSHIFT_EXPR:
 630     case LROTATE_EXPR:
 631     case RROTATE_EXPR:
 632       return true;
 633     default:
 634       return false;
 635     }
 636   return false;
 637 }
 638
 639 /* Inference rule for operations (lhs = operation(operands)).  */
 640
 641 static void
 642 andersen_op_assign (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 643                     alias_var lhs, varray_type operands, tree operation,
 644                     bitmap addrargs)
 645 {
 646   aterm newvar = NULL;
 647
 648   if (VARRAY_ACTIVE_SIZE (operands) == 0)
 649     return;
 650
 651   if (dump_file && (dump_flags & TDF_DETAILS))
 652     {
 653       fprintf (dump_file, "Op assignment %s = ",
 654                alias_get_name (ALIAS_VAR_DECL (lhs)));
 655       print_generic_stmt (dump_file, operation, dump_flags);
 656       fprintf (dump_file, "\n");
 657     }
 658
 659
 660   /* Pointer destroying operations do not give us the same valid pointer
 661      back, and thus, are assignment to pta_bottom.  */
 662   if (pointer_destroying_op (operation))
 663     {
 664       pta_assignment (ALIAS_VAR_ATERM (lhs), pta_rvalue (pta_bottom ()));
 665       return;
 666     }
 667
 668   /* Operations in general we can't track the exact effect of.  Thus,
 669      we conservatively assume that it could make the LHS point to
 670      *anything* the RHS points to.  To signify this, we join the RHS
 671      variables together and assign it to the LHS.  */
 672   /* The >2 case occurs when we are dealing with constructors.  */
 673   if (VARRAY_ACTIVE_SIZE (operands) > 2)
 674     {
 675       size_t i;
 676       alias_var tv1 = VARRAY_GENERIC_PTR (operands, 0);
 677       newvar = ALIAS_VAR_ATERM (tv1);
 678       for (i = 1; i < VARRAY_ACTIVE_SIZE (operands); i++)
 679         {
 680           alias_var tempvar = VARRAY_GENERIC_PTR (operands, i);
 681           aterm t2 = ALIAS_VAR_ATERM (tempvar);
 682           if (bitmap_bit_p (addrargs, i))
 683             newvar = pta_join (newvar, pta_address (t2));
 684           else
 685             newvar = pta_join (newvar, t2);
 686         }
 687     }
 688   else if (VARRAY_ACTIVE_SIZE (operands) == 2)
 689     {
 690       alias_var tv1 = VARRAY_GENERIC_PTR (operands, 0);
 691       alias_var tv2 = VARRAY_GENERIC_PTR (operands, 1);
 692       aterm t1 = ALIAS_VAR_ATERM (tv1);
 693       aterm t2 = ALIAS_VAR_ATERM (tv2);
 694       if (bitmap_bit_p (addrargs, 0) && bitmap_bit_p (addrargs, 1))
 695         newvar = pta_join (pta_address (t1), pta_address (t2));
 696       else if (bitmap_bit_p (addrargs, 0))
 697         newvar = pta_join (pta_address (t1), t2);
 698       else if (bitmap_bit_p (addrargs, 1))
 699         newvar = pta_join (t1, pta_address (t2));
 700       else
 701         newvar = pta_join (t1, t2);
 702     }
 703   else if (VARRAY_ACTIVE_SIZE (operands) == 1)
 704     {
 705       alias_var tv1 = VARRAY_GENERIC_PTR (operands, 0);
 706       aterm t1 = ALIAS_VAR_ATERM (tv1);
 707       if (bitmap_bit_p (addrargs, 0))
 708         newvar = pta_address (t1);
 709       else
 710         newvar = t1;
 711     }
 712   pta_assignment (ALIAS_VAR_ATERM (lhs), pta_rvalue (newvar));
 713 }
 714
 715 /* Inference for heap assignment (lhs = alloc).  */
 716
 717 static void
 718 andersen_heap_assign (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 719                       alias_var lhs ATTRIBUTE_UNUSED)
 720 {
 721 #if 0
 722   alias_type type1;
 723   ECR tau;
 724   type1 = ECR_get_type (alias_var_get_ECR (lhs));
 725   tau = alias_ltype_loc (type1);
 726
 727   if (ECR_get_type (tau) == alias_bottom)
 728     ECR_set_type (tau, alias_ltype_new ());
 729 #endif
 730 }
 731
 732 /* Inference for assignment to a pointer (*ptr = rhs).  */
 733
 734 static void
 735 andersen_assign_ptr (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 736                      alias_var ptr, alias_var rhs)
 737 {
 738
 739   if (rhs == NULL)
 740     return;
 741   if (dump_file && (dump_flags & TDF_DETAILS))
 742     fprintf (dump_file, "Assignment to pointer  *%s = %s\n",
 743              alias_get_name (ALIAS_VAR_DECL (ptr)),
 744              alias_get_name (ALIAS_VAR_DECL (rhs)));
 745   /* The RHS is a standard rvalue, and the LHS is a pointer
 746      dereference.  */
 747   pta_assignment (pta_deref (ALIAS_VAR_ATERM (ptr)),
 748                   pta_rvalue (ALIAS_VAR_ATERM (rhs)));
 749 }
 750
 751 /* Inference for a function definition.  */
 752
 753 static void
 754 andersen_function_def (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 755                        alias_var func, varray_type params,
 756                        alias_var retval)
 757 {
 758   aterm_list args = new_aterm_list (andersen_rgn);
 759   aterm fun_type;
 760
 761   size_t l = VARRAY_ACTIVE_SIZE (params);
 762   size_t i;
 763
 764   /* Set up the arguments for the new function type.  */
 765   for (i = 0; i < l; i++)
 766     {
 767       alias_var tv = VARRAY_GENERIC_PTR (params, i);
 768       aterm_list_cons (ALIAS_VAR_ATERM (tv), args);
 769     }
 770   /* Create the function type.  */
 771   fun_type = pta_make_fun (alias_get_name (ALIAS_VAR_DECL (func)),
 772                            ALIAS_VAR_ATERM (retval), args);
 773
 774   /* Assign the function type itself to the function.  */
 775   pta_assignment (ALIAS_VAR_ATERM (func), fun_type);
 776 }
 777
 778 /* Inference for a function call assignment.  */
 779
 780 static int
 781 andersen_function_call (struct tree_alias_ops *ops,
 782                         alias_var lhs, alias_var func,
 783                         varray_type args, bitmap addrargs)
 784 {
 785   aterm_list actuals = new_aterm_list (andersen_rgn);
 786   aterm ftype = ALIAS_VAR_ATERM (func);
 787   aterm ret = NULL;
 788   aterm res;
 789   tree decl = ALIAS_VAR_DECL (func);
 790
 791   size_t i;
 792
 793   if (lhs)
 794     ret = ALIAS_VAR_ATERM (lhs);
 795   for (i = 0; i < VARRAY_ACTIVE_SIZE (args); i++)
 796     {
 797       alias_var argtv = VARRAY_GENERIC_PTR (args, i);
 798       aterm arg = ALIAS_VAR_ATERM (argtv);
 799       if (bitmap_bit_p (addrargs, i))
 800         aterm_list_cons (pta_rvalue (pta_address (arg)), actuals);
 801       else
 802         aterm_list_cons (pta_rvalue (arg), actuals);
 803     }
 804   aterm_list_reverse (actuals);
 805
 806   /* Generate the constraint that calls the function with it's
 807      arguments, and gives us the result.  This in turn applies
 808      whatever constraints are in that function.  */
 809   res = pta_application (pta_rvalue (ftype), actuals);
 810   /* We only need care about the result if we have an LHS.  If we do,
 811      assign the result of function application back to the LHS.  */
 812   if (ret)
 813     pta_assignment (ret, pta_rvalue (res));
 814
 815   /* We can handle functions we've got trees for. non-statics will
 816      just have incoming parameters assigned to global_var if
 817      necessary.  */
 818   if (TREE_CODE (decl) == FUNCTION_DECL
 819       && DECL_PTA_ALIASVAR (decl)
 820       && ops->ip_partial
 821       && (cgraph_local_info (decl)->local))
 822     {
 823       return 0;
 824     }
 825   return 1;
 826 }
 827
 828
 829 /* Simple pointer comparison function for list sorting.  */
 830
 831 static int
 832 simple_cmp (const aterm a, const aterm b)
 833 {
 834   return (int *)a - (int *)b;
 835 }
 836
 837
 838 /* Get the points-to set for TV, caching if it we had to compute it.  */
 839
 840 static aterm_list
 841 get_ptset (alias_var tv)
 842 {
 843   aterm_list ptset;
 844   ptset = ALIAS_VAR_PTSET (tv);
 845   if (ptset != NULL)
 846     return ptset;
 847   ptset = aterm_tlb (pta_get_contents (ALIAS_VAR_ATERM (tv)));
 848   ALIAS_VAR_PTSET (tv) = ptset;
 849   return ptset;
 850 }
 851
 852
 853 /* Determine if two aterm's have the same points-to set.  */
 854
 855 static bool
 856 andersen_same_points_to_set (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 857                              alias_var ptrtv, alias_var vartv)
 858 {
 859   aterm_list ptset1, ptset2;
 860   aterm_list_scanner scan1, scan2;
 861   aterm data1, data2;
 862   region scratch_rgn = newregion ();
 863
 864   ptset1 = get_ptset (ptrtv);
 865   ptset2 = get_ptset (vartv);
 866
 867   if (aterm_list_length (ptset1) != aterm_list_length (ptset2))
 868     {
 869       deleteregion (scratch_rgn);
 870       return false;
 871     }
 872
 873   if (ptset1 == ptset2)
 874     {
 875       deleteregion (scratch_rgn);
 876       return true;
 877     }
 878
 879   ptset1 = aterm_list_copy (scratch_rgn, ptset1);
 880   ptset2 = aterm_list_copy (scratch_rgn, ptset2);
 881
 882   if (aterm_list_length (ptset1) != aterm_list_length (ptset2))
 883     {
 884       deleteregion (scratch_rgn);
 885       return false;
 886     }
 887
 888   ptset1 = aterm_list_sort (ptset1, simple_cmp);
 889   ptset2 = aterm_list_sort (ptset2, simple_cmp);
 890
 891   aterm_list_scan (ptset1, &scan1);
 892   aterm_list_scan (ptset2, &scan2);
 893   while (aterm_list_next (&scan1, &data1))
 894     {
 895       aterm_list_next (&scan2, &data2);
 896       if (data1 != data2)
 897         {
 898           deleteregion(scratch_rgn);
 899           return false;
 900         }
 901     }
 902   deleteregion(scratch_rgn);
 903   return true;
 904 }
 905
 906
 907 /* Determine if two variables may alias.  In our case, this means
 908    whether the decl represented by PTRTV can point to VARTV.  */
 909
 910 static bool
 911 andersen_may_alias (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 912                     alias_var ptrtv, alias_var vartv)
 913 {
 914   aterm_list ptset;
 915   ptset = get_ptset (ptrtv);
 916
 917   if (aterm_list_empty (ptset))
 918     return false;
 919
 920   return aterm_list_member (ptset, ALIAS_VAR_ATERM (vartv));
 921 }
 922
 923 /* Determine whether PTRTV has an empty points-to set. IE it may not
 924    point to anything.  */
 925
 926 static bool
 927 andersen_empty_points_to_set (struct tree_alias_ops *ops ATTRIBUTE_UNUSED,
 928                               alias_var ptrtv)
 929 {
 930   aterm_list ptset;
 931   ptset = get_ptset (ptrtv);
 932   return aterm_list_empty (ptset);
 933 }