gcc/value-relation.cc

   1 /* Header file for the value range relational processing.
   2    Copyright (C) 2020-2022 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15  for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "ssa.h"
  28
  29 #include "gimple-range.h"
  30 #include "tree-pretty-print.h"
  31 #include "gimple-pretty-print.h"
  32 #include "alloc-pool.h"
  33 #include "dominance.h"
  34
  35 #define VREL_LAST               VREL_NE
  36
  37 static const char *kind_string[VREL_LAST + 1] =
  38 { "varying", "undefined", "<", "<=", ">", ">=", "==", "!=" };
  39
  40 // Print a relation_kind REL to file F.
  41
  42 void
  43 print_relation (FILE *f, relation_kind rel)
  44 {
  45   fprintf (f, " %s ", kind_string[rel]);
  46 }
  47
  48 // This table is used to negate the operands.  op1 REL op2 -> !(op1 REL op2).
  49 relation_kind rr_negate_table[VREL_LAST + 1] = {
  50   VREL_VARYING, VREL_UNDEFINED, VREL_GE, VREL_GT, VREL_LE, VREL_LT, VREL_NE,
  51   VREL_EQ };
  52
  53 // Negate the relation, as in logical negation.
  54
  55 relation_kind
  56 relation_negate (relation_kind r)
  57 {
  58   return rr_negate_table [r];
  59 }
  60
  61 // This table is used to swap the operands.  op1 REL op2 -> op2 REL op1.
  62 relation_kind rr_swap_table[VREL_LAST + 1] = {
  63   VREL_VARYING, VREL_UNDEFINED, VREL_GT, VREL_GE, VREL_LT, VREL_LE, VREL_EQ,
  64   VREL_NE };
  65
  66 // Return the relation as if the operands were swapped.
  67
  68 relation_kind
  69 relation_swap (relation_kind r)
  70 {
  71   return rr_swap_table [r];
  72 }
  73
  74 // This table is used to perform an intersection between 2 relations.
  75
  76 relation_kind rr_intersect_table[VREL_LAST + 1][VREL_LAST + 1] = {
  77 // VREL_VARYING
  78   { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
  79     VREL_NE },
  80 // VREL_UNDEFINED
  81   { VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
  82     VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED },
  83 // VREL_LT
  84   { VREL_LT, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_UNDEFINED, VREL_UNDEFINED,
  85     VREL_UNDEFINED, VREL_LT },
  86 // VREL_LE
  87   { VREL_LE, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_UNDEFINED, VREL_EQ,
  88     VREL_EQ, VREL_LT },
  89 // VREL_GT
  90   { VREL_GT, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_GT, VREL_GT,
  91     VREL_UNDEFINED, VREL_GT },
  92 // VREL_GE
  93   { VREL_GE, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_GT, VREL_GE,
  94     VREL_EQ, VREL_GT },
  95 // VREL_EQ
  96   { VREL_EQ, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_UNDEFINED, VREL_EQ,
  97     VREL_EQ, VREL_UNDEFINED },
  98 // VREL_NE
  99   { VREL_NE, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_GT, VREL_GT,
 100     VREL_UNDEFINED, VREL_NE } };
 101
 102
 103 // Intersect relation R1 with relation R2 and return the resulting relation.
 104
 105 relation_kind
 106 relation_intersect (relation_kind r1, relation_kind r2)
 107 {
 108   return rr_intersect_table[r1][r2];
 109 }
 110
 111
 112 // This table is used to perform a union between 2 relations.
 113
 114 relation_kind rr_union_table[VREL_LAST + 1][VREL_LAST + 1] = {
 115 // VREL_VARYING
 116   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
 117     VREL_VARYING, VREL_VARYING, VREL_VARYING },
 118 // VREL_UNDEFINED
 119   { VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_UNDEFINED,
 120     VREL_EQ, VREL_NE },
 121 // VREL_LT
 122   { VREL_VARYING, VREL_LT, VREL_LT, VREL_LE, VREL_NE, VREL_VARYING, VREL_LE,
 123     VREL_NE },
 124 // VREL_LE
 125   { VREL_VARYING, VREL_LE, VREL_LE, VREL_LE, VREL_VARYING, VREL_VARYING,
 126     VREL_LE, VREL_VARYING },
 127 // VREL_GT
 128   { VREL_VARYING, VREL_GT, VREL_NE, VREL_VARYING, VREL_GT, VREL_GE, VREL_GE,
 129     VREL_NE },
 130 // VREL_GE
 131   { VREL_VARYING, VREL_GE, VREL_VARYING, VREL_VARYING, VREL_GE, VREL_GE,
 132     VREL_GE, VREL_VARYING },
 133 // VREL_EQ
 134   { VREL_VARYING, VREL_EQ, VREL_LE, VREL_LE, VREL_GE, VREL_GE, VREL_EQ,
 135     VREL_VARYING },
 136 // VREL_NE
 137   { VREL_VARYING, VREL_NE, VREL_NE, VREL_VARYING, VREL_NE, VREL_VARYING,
 138     VREL_VARYING, VREL_NE } };
 139
 140 // Union relation R1 with relation R2 and return the result.
 141
 142 relation_kind
 143 relation_union (relation_kind r1, relation_kind r2)
 144 {
 145   return rr_union_table[r1][r2];
 146 }
 147
 148
 149 // This table is used to determine transitivity between 2 relations.
 150 // (A relation0 B) and (B relation1 C) implies  (A result C)
 151
 152 relation_kind rr_transitive_table[VREL_LAST + 1][VREL_LAST + 1] = {
 153 // VREL_VARYING
 154   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
 155     VREL_VARYING, VREL_VARYING, VREL_VARYING },
 156 // VREL_UNDEFINED
 157   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
 158     VREL_VARYING, VREL_VARYING, VREL_VARYING },
 159 // VREL_LT
 160   { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LT, VREL_VARYING, VREL_VARYING,
 161     VREL_LT, VREL_VARYING },
 162 // VREL_LE
 163   { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_VARYING, VREL_VARYING,
 164     VREL_LE, VREL_VARYING },
 165 // VREL_GT
 166   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GT,
 167     VREL_GT, VREL_VARYING },
 168 // VREL_GE
 169   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GE,
 170     VREL_GE, VREL_VARYING },
 171 // VREL_EQ
 172   { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
 173     VREL_VARYING },
 174 // VREL_NE
 175   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
 176     VREL_VARYING, VREL_VARYING, VREL_VARYING } };
 177
 178 // Apply transitive operation between relation R1 and relation R2, and
 179 // return the resulting relation, if any.
 180
 181 relation_kind
 182 relation_transitive (relation_kind r1, relation_kind r2)
 183 {
 184   return rr_transitive_table[r1][r2];
 185 }
 186
 187 // This vector maps a relation to the equivalent tree code.
 188
 189 tree_code relation_to_code [VREL_LAST + 1] = {
 190   ERROR_MARK, ERROR_MARK, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EQ_EXPR,
 191   NE_EXPR };
 192
 193 // This routine validates that a relation can be applied to a specific set of
 194 // ranges.  In particular, floating point x == x may not be true if the NaN bit
 195 // is set in the range.  Symbolically the oracle will determine x == x,
 196 // but specific range instances may override this.
 197 // To verify, attempt to fold the relation using the supplied ranges.
 198 // One would expect [1,1] to be returned, anything else means there is something
 199 // in the range preventing the relation from applying.
 200 // If there is no mechanism to verify, assume the relation is acceptable.
 201
 202 relation_kind
 203 relation_oracle::validate_relation (relation_kind rel, vrange &op1, vrange &op2)
 204 {
 205   // If there is no mapping to a tree code, leave the relation as is.
 206   tree_code code = relation_to_code [rel];
 207   if (code == ERROR_MARK)
 208     return rel;
 209
 210   // Undefined ranges cannot be checked either.
 211   if (op1.undefined_p () || op2.undefined_p ())
 212     return rel;
 213
 214   tree t1 = op1.type ();
 215   tree t2 = op2.type ();
 216
 217   // If the range types are not compatible, no relation can exist.
 218   if (!range_compatible_p (t1, t2))
 219     return VREL_VARYING;
 220
 221   // If there is no handler, leave the relation as is.
 222   range_op_handler handler (code, t1);
 223   if (!handler)
 224     return rel;
 225
 226   // If the relation cannot be folded for any reason, leave as is.
 227   Value_Range result (boolean_type_node);
 228   if (!handler.fold_range (result, boolean_type_node, op1, op2, rel))
 229     return rel;
 230
 231   // The expression op1 REL op2 using REL should fold to [1,1].
 232   // Any other result means the relation is not verified to be true.
 233   if (result.varying_p () || result.zero_p ())
 234     return VREL_VARYING;
 235
 236   return rel;
 237 }
 238
 239 // If no range is available, create a varying range for each SSA name and
 240 // verify.
 241
 242 relation_kind
 243 relation_oracle::validate_relation (relation_kind rel, tree ssa1, tree ssa2)
 244 {
 245   Value_Range op1, op2;
 246   op1.set_varying (TREE_TYPE (ssa1));
 247   op2.set_varying (TREE_TYPE (ssa2));
 248
 249   return validate_relation (rel, op1, op2);
 250 }
 251
 252 // Given an equivalence set EQUIV, set all the bits in B that are still valid
 253 // members of EQUIV in basic block BB.
 254
 255 void
 256 relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
 257 {
 258   unsigned i;
 259   bitmap_iterator bi;
 260   EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
 261     {
 262       tree ssa = ssa_name (i);
 263       const_bitmap ssa_equiv = equiv_set (ssa, bb);
 264       if (ssa_equiv == equivs)
 265         bitmap_set_bit (b, i);
 266     }
 267 }
 268
 269 // -------------------------------------------------------------------------
 270
 271 // The very first element in the m_equiv chain is actually just a summary
 272 // element in which the m_names bitmap is used to indicate that an ssa_name
 273 // has an equivalence set in this block.
 274 // This allows for much faster traversal of the DOM chain, as a search for
 275 // SSA_NAME simply requires walking the DOM chain until a block is found
 276 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
 277 // that block.   No previous lists need be searched.
 278
 279 // If SSA has an equivalence in this list, find and return it.
 280 // Otherwise return NULL.
 281
 282 equiv_chain *
 283 equiv_chain::find (unsigned ssa)
 284 {
 285   equiv_chain *ptr = NULL;
 286   // If there are equiv sets and SSA is in one in this list, find it.
 287   // Otherwise return NULL.
 288   if (bitmap_bit_p (m_names, ssa))
 289     {
 290       for (ptr = m_next; ptr; ptr = ptr->m_next)
 291         if (bitmap_bit_p (ptr->m_names, ssa))
 292           break;
 293     }
 294   return ptr;
 295 }
 296
 297 // Dump the names in this equivalence set.
 298
 299 void
 300 equiv_chain::dump (FILE *f) const
 301 {
 302   bitmap_iterator bi;
 303   unsigned i;
 304
 305   if (!m_names)
 306     return;
 307   fprintf (f, "Equivalence set : [");
 308   unsigned c = 0;
 309   EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
 310     {
 311       if (ssa_name (i))
 312         {
 313           if (c++)
 314             fprintf (f, ", ");
 315           print_generic_expr (f, ssa_name (i), TDF_SLIM);
 316         }
 317     }
 318   fprintf (f, "]\n");
 319 }
 320
 321 // Instantiate an equivalency oracle.
 322
 323 equiv_oracle::equiv_oracle ()
 324 {
 325   bitmap_obstack_initialize (&m_bitmaps);
 326   m_equiv.create (0);
 327   m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 328   m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
 329   obstack_init (&m_chain_obstack);
 330   m_self_equiv.create (0);
 331   m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
 332 }
 333
 334 // Destruct an equivalency oracle.
 335
 336 equiv_oracle::~equiv_oracle ()
 337 {
 338   m_self_equiv.release ();
 339   obstack_free (&m_chain_obstack, NULL);
 340   m_equiv.release ();
 341   bitmap_obstack_release (&m_bitmaps);
 342 }
 343
 344 // Find and return the equivalency set for SSA along the dominators of BB.
 345 // This is the external API.
 346
 347 const_bitmap
 348 equiv_oracle::equiv_set (tree ssa, basic_block bb)
 349 {
 350   // Search the dominator tree for an equivalency.
 351   equiv_chain *equiv = find_equiv_dom (ssa, bb);
 352   if (equiv)
 353     return equiv->m_names;
 354
 355   // Otherwise return a cached equiv set containing just this SSA.
 356   unsigned v = SSA_NAME_VERSION (ssa);
 357   if (v >= m_self_equiv.length ())
 358     m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
 359
 360   if (!m_self_equiv[v])
 361     {
 362       m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps);
 363       bitmap_set_bit (m_self_equiv[v], v);
 364     }
 365   return m_self_equiv[v];
 366 }
 367
 368 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
 369
 370 relation_kind
 371 equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
 372 {
 373   // If the 2 ssa names share the same equiv set, they are equal.
 374   if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
 375     return VREL_EQ;
 376   return VREL_VARYING;
 377 }
 378
 379 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
 380
 381 relation_kind
 382 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
 383                               const_bitmap e2)
 384 {
 385   // If the 2 ssa names share the same equiv set, they are equal.
 386   if (bitmap_equal_p (e1, e2))
 387     return VREL_EQ;
 388   return VREL_VARYING;
 389 }
 390
 391 // If SSA has an equivalence in block BB, find and return it.
 392 // Otherwise return NULL.
 393
 394 equiv_chain *
 395 equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
 396 {
 397   if (bb >= (int)m_equiv.length () || !m_equiv[bb])
 398     return NULL;
 399
 400   return m_equiv[bb]->find (ssa);
 401 }
 402
 403 // Starting at block BB, walk the dominator chain looking for the nearest
 404 // equivalence set containing NAME.
 405
 406 equiv_chain *
 407 equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
 408 {
 409   unsigned v = SSA_NAME_VERSION (name);
 410   // Short circuit looking for names which have no equivalences.
 411   // Saves time looking for something which does not exist.
 412   if (!bitmap_bit_p (m_equiv_set, v))
 413     return NULL;
 414
 415   // NAME has at least once equivalence set, check to see if it has one along
 416   // the dominator tree.
 417   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 418     {
 419       equiv_chain *ptr = find_equiv_block (v, bb->index);
 420       if (ptr)
 421         return ptr;
 422     }
 423   return NULL;
 424 }
 425
 426 // Register equivalance between ssa_name V and set EQUIV in block BB,
 427
 428 bitmap
 429 equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
 430 {
 431   // V will have an equivalency now.
 432   bitmap_set_bit (m_equiv_set, v);
 433
 434   // If that equiv chain is in this block, simply use it.
 435   if (equiv->m_bb == bb)
 436     {
 437       bitmap_set_bit (equiv->m_names, v);
 438       bitmap_set_bit (m_equiv[bb->index]->m_names, v);
 439       return NULL;
 440     }
 441
 442   // Otherwise create an equivalence for this block which is a copy
 443   // of equiv, the add V to the set.
 444   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 445   valid_equivs (b, equiv->m_names, bb);
 446   bitmap_set_bit (b, v);
 447   return b;
 448 }
 449
 450 // Register equivalence between set equiv_1 and equiv_2 in block BB.
 451 // Return NULL if either name can be merged with the other.  Otherwise
 452 // return a pointer to the combined bitmap of names.  This allows the
 453 // caller to do any setup required for a new element.
 454
 455 bitmap
 456 equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
 457                               equiv_chain *equiv_2)
 458 {
 459   // If equiv_1 is already in BB, use it as the combined set.
 460   if (equiv_1->m_bb == bb)
 461     {
 462       valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
 463       // Its hard to delete from a single linked list, so
 464       // just clear the second one.
 465       if (equiv_2->m_bb == bb)
 466         bitmap_clear (equiv_2->m_names);
 467       else
 468         // Ensure the new names are in the summary for BB.
 469         bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
 470       return NULL;
 471     }
 472   // If equiv_2 is in BB, use it for the combined set.
 473   if (equiv_2->m_bb == bb)
 474     {
 475       valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
 476       // Ensure the new names are in the summary.
 477       bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
 478       return NULL;
 479     }
 480
 481   // At this point, neither equivalence is from this block.
 482   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 483   valid_equivs (b, equiv_1->m_names, bb);
 484   valid_equivs (b, equiv_2->m_names, bb);
 485   return b;
 486 }
 487
 488 // Create an equivalency set containing only SSA in its definition block.
 489 // This is done the first time SSA is registered in an equivalency and blocks
 490 // any DOM searches past the definition.
 491
 492 void
 493 equiv_oracle::register_initial_def (tree ssa)
 494 {
 495   if (SSA_NAME_IS_DEFAULT_DEF (ssa))
 496     return;
 497   basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
 498   gcc_checking_assert (bb && !find_equiv_dom (ssa, bb));
 499
 500   unsigned v = SSA_NAME_VERSION (ssa);
 501   bitmap_set_bit (m_equiv_set, v);
 502   bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
 503   bitmap_set_bit (equiv_set, v);
 504   add_equiv_to_block (bb, equiv_set);
 505 }
 506
 507 // Register an equivalence between SSA1 and SSA2 in block BB.
 508 // The equivalence oracle maintains a vector of equivalencies indexed by basic
 509 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
 510 // a query is made as to what equivalences both names have already, and
 511 // any preexisting equivalences are merged to create a single equivalence
 512 // containing all the ssa_names in this basic block.
 513
 514 void
 515 equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
 516                                  tree ssa2)
 517 {
 518   // Only handle equality relations.
 519   if (k != VREL_EQ)
 520     return;
 521
 522   unsigned v1 = SSA_NAME_VERSION (ssa1);
 523   unsigned v2 = SSA_NAME_VERSION (ssa2);
 524
 525   // If this is the first time an ssa_name has an equivalency registered
 526   // create a self-equivalency record in the def block.
 527   if (!bitmap_bit_p (m_equiv_set, v1))
 528     register_initial_def (ssa1);
 529   if (!bitmap_bit_p (m_equiv_set, v2))
 530     register_initial_def (ssa2);
 531
 532   equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
 533   equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
 534
 535   // Check if they are the same set
 536   if (equiv_1 && equiv_1 == equiv_2)
 537     return;
 538
 539   bitmap equiv_set;
 540
 541   // Case where we have 2 SSA_NAMEs that are not in any set.
 542   if (!equiv_1 && !equiv_2)
 543     {
 544       bitmap_set_bit (m_equiv_set, v1);
 545       bitmap_set_bit (m_equiv_set, v2);
 546
 547       equiv_set = BITMAP_ALLOC (&m_bitmaps);
 548       bitmap_set_bit (equiv_set, v1);
 549       bitmap_set_bit (equiv_set, v2);
 550     }
 551   else if (!equiv_1 && equiv_2)
 552     equiv_set = register_equiv (bb, v1, equiv_2);
 553   else if (equiv_1 && !equiv_2)
 554     equiv_set = register_equiv (bb, v2, equiv_1);
 555   else
 556     equiv_set = register_equiv (bb, equiv_1, equiv_2);
 557
 558   // A non-null return is a bitmap that is to be added to the current
 559   // block as a new equivalence.
 560   if (!equiv_set)
 561     return;
 562
 563   add_equiv_to_block (bb, equiv_set);
 564 }
 565
 566 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
 567 // Note the internal caller is responible for allocating EQUIV_SET properly.
 568
 569 void
 570 equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
 571 {
 572   equiv_chain *ptr;
 573
 574   // Check if this is the first time a block has an equivalence added.
 575   // and create a header block. And set the summary for this block.
 576   if (!m_equiv[bb->index])
 577     {
 578       ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
 579                                            sizeof (equiv_chain));
 580       ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
 581       bitmap_copy (ptr->m_names, equiv_set);
 582       ptr->m_bb = bb;
 583       ptr->m_next = NULL;
 584       m_equiv[bb->index] = ptr;
 585     }
 586
 587   // Now create the element for this equiv set and initialize it.
 588   ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
 589   ptr->m_names = equiv_set;
 590   ptr->m_bb = bb;
 591   gcc_checking_assert (bb->index < (int)m_equiv.length ());
 592   ptr->m_next = m_equiv[bb->index]->m_next;
 593   m_equiv[bb->index]->m_next = ptr;
 594   bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
 595 }
 596
 597 // Make sure the BB vector is big enough and grow it if needed.
 598
 599 void
 600 equiv_oracle::limit_check (basic_block bb)
 601 {
 602   int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
 603   if (i >= (int)m_equiv.length ())
 604     m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 605 }
 606
 607 // Dump the equivalence sets in BB to file F.
 608
 609 void
 610 equiv_oracle::dump (FILE *f, basic_block bb) const
 611 {
 612   if (bb->index >= (int)m_equiv.length ())
 613     return;
 614   if (!m_equiv[bb->index])
 615     return;
 616
 617   equiv_chain *ptr = m_equiv[bb->index]->m_next;
 618   for (; ptr; ptr = ptr->m_next)
 619     ptr->dump (f);
 620 }
 621
 622 // Dump all equivalence sets known to the oracle.
 623
 624 void
 625 equiv_oracle::dump (FILE *f) const
 626 {
 627   fprintf (f, "Equivalency dump\n");
 628   for (unsigned i = 0; i < m_equiv.length (); i++)
 629     if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
 630       {
 631         fprintf (f, "BB%d\n", i);
 632         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
 633       }
 634 }
 635
 636
 637 // --------------------------------------------------------------------------
 638
 639 // The value-relation class is used to encapsulate the represention of an
 640 // individual relation between 2 ssa-names, and to facilitate operating on
 641 // the relation.
 642
 643 class value_relation
 644 {
 645 public:
 646   value_relation ();
 647   value_relation (relation_kind kind, tree n1, tree n2);
 648   void set_relation (relation_kind kind, tree n1, tree n2);
 649
 650   inline relation_kind kind () const { return related; }
 651   inline tree op1 () const { return name1; }
 652   inline tree op2 () const { return name2; }
 653
 654   bool union_ (value_relation &p);
 655   bool intersect (value_relation &p);
 656   void negate ();
 657   bool apply_transitive (const value_relation &rel);
 658
 659   void dump (FILE *f) const;
 660 private:
 661   relation_kind related;
 662   tree name1, name2;
 663 };
 664
 665 // Set relation R between ssa_name N1 and N2.
 666
 667 inline void
 668 value_relation::set_relation (relation_kind r, tree n1, tree n2)
 669 {
 670   gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2)
 671                        || r == VREL_EQ);
 672   related = r;
 673   name1 = n1;
 674   name2 = n2;
 675 }
 676
 677 // Default constructor.
 678
 679 inline
 680 value_relation::value_relation ()
 681 {
 682   related = VREL_VARYING;
 683   name1 = NULL_TREE;
 684   name2 = NULL_TREE;
 685 }
 686
 687 // Constructor for relation R between SSA version N1 nd N2.
 688
 689 inline
 690 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
 691 {
 692   set_relation (kind, n1, n2);
 693 }
 694
 695 // Negate the current relation.
 696
 697 void
 698 value_relation::negate ()
 699 {
 700   related = relation_negate (related);
 701 }
 702
 703 // Perform an intersection between 2 relations. *this &&= p.
 704
 705 bool
 706 value_relation::intersect (value_relation &p)
 707 {
 708   // Save previous value
 709   relation_kind old = related;
 710
 711   if (p.op1 () == op1 () && p.op2 () == op2 ())
 712     related = relation_intersect (kind (), p.kind ());
 713   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 714     related = relation_intersect (kind (), relation_swap (p.kind ()));
 715   else
 716     return false;
 717
 718   return old != related;
 719 }
 720
 721 // Perform a union between 2 relations. *this ||= p.
 722
 723 bool
 724 value_relation::union_ (value_relation &p)
 725 {
 726   // Save previous value
 727   relation_kind old = related;
 728
 729   if (p.op1 () == op1 () && p.op2 () == op2 ())
 730     related = relation_union (kind(), p.kind());
 731   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 732     related = relation_union (kind(), relation_swap (p.kind ()));
 733   else
 734     return false;
 735
 736   return old != related;
 737 }
 738
 739 // Identify and apply any transitive relations between REL
 740 // and THIS.  Return true if there was a transformation.
 741
 742 bool
 743 value_relation::apply_transitive (const value_relation &rel)
 744 {
 745   relation_kind k = VREL_VARYING;
 746
 747   // Idenity any common operand, and notrmalize the relations to
 748   // the form : A < B  B < C produces A < C
 749   if (rel.op1 () == name2)
 750     {
 751       // A < B   B < C
 752       if (rel.op2 () == name1)
 753         return false;
 754       k = relation_transitive (kind (), rel.kind ());
 755       if (k != VREL_VARYING)
 756         {
 757           related = k;
 758           name2 = rel.op2 ();
 759           return true;
 760         }
 761     }
 762   else if (rel.op1 () == name1)
 763     {
 764       // B > A   B < C
 765       if (rel.op2 () == name2)
 766         return false;
 767       k = relation_transitive (relation_swap (kind ()), rel.kind ());
 768       if (k != VREL_VARYING)
 769         {
 770           related = k;
 771           name1 = name2;
 772           name2 = rel.op2 ();
 773           return true;
 774         }
 775     }
 776   else if (rel.op2 () == name2)
 777     {
 778        // A < B   C > B
 779        if (rel.op1 () == name1)
 780          return false;
 781       k = relation_transitive (kind (), relation_swap (rel.kind ()));
 782       if (k != VREL_VARYING)
 783         {
 784           related = k;
 785           name2 = rel.op1 ();
 786           return true;
 787         }
 788     }
 789   else if (rel.op2 () == name1)
 790     {
 791       // B > A  C > B
 792       if (rel.op1 () == name2)
 793         return false;
 794       k = relation_transitive (relation_swap (kind ()),
 795                                relation_swap (rel.kind ()));
 796       if (k != VREL_VARYING)
 797         {
 798           related = k;
 799           name1 = name2;
 800           name2 = rel.op1 ();
 801           return true;
 802         }
 803     }
 804   return false;
 805 }
 806
 807 // Dump the relation to file F.
 808
 809 void
 810 value_relation::dump (FILE *f) const
 811 {
 812   if (!name1 || !name2)
 813     {
 814       fprintf (f, "uninitialized");
 815       return;
 816     }
 817   fputc ('(', f);
 818   print_generic_expr (f, op1 (), TDF_SLIM);
 819   print_relation (f, kind ());
 820   print_generic_expr (f, op2 (), TDF_SLIM);
 821   fputc(')', f);
 822 }
 823
 824 // This container is used to link relations in a chain.
 825
 826 class relation_chain : public value_relation
 827 {
 828 public:
 829   relation_chain *m_next;
 830 };
 831
 832 // ------------------------------------------------------------------------
 833
 834 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
 835 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
 836
 837 relation_kind
 838 relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
 839 {
 840   if (!m_names)
 841     return VREL_VARYING;
 842
 843   // If both b1 and b2 aren't referenced in thie block, cant be a relation
 844   if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
 845     return VREL_VARYING;
 846
 847   // Search for the fiorst relation that contains BOTH an element from B1
 848   // and B2, and return that relation.
 849   for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
 850     {
 851       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
 852       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
 853       if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
 854         return ptr->kind ();
 855       if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
 856         return relation_swap (ptr->kind ());
 857     }
 858
 859   return VREL_VARYING;
 860 }
 861
 862 // Instantiate a relation oracle.
 863
 864 dom_oracle::dom_oracle ()
 865 {
 866   m_relations.create (0);
 867   m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 868   m_relation_set = BITMAP_ALLOC (&m_bitmaps);
 869   m_tmp = BITMAP_ALLOC (&m_bitmaps);
 870   m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
 871 }
 872
 873 // Destruct a relation oracle.
 874
 875 dom_oracle::~dom_oracle ()
 876 {
 877   m_relations.release ();
 878 }
 879
 880 // Register relation K between ssa_name OP1 and OP2 on STMT.
 881
 882 void
 883 relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
 884                                 tree op2)
 885 {
 886   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 887   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 888   gcc_checking_assert (stmt && gimple_bb (stmt));
 889
 890   // Don't register lack of a relation.
 891   if (k == VREL_VARYING)
 892     return;
 893
 894   if (dump_file && (dump_flags & TDF_DETAILS))
 895     {
 896       value_relation vr (k, op1, op2);
 897       fprintf (dump_file, " Registering value_relation ");
 898       vr.dump (dump_file);
 899       fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
 900       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 901     }
 902
 903   // If an equivalence is being added between a PHI and one of its arguments
 904   // make sure that that argument is not defined in the same block.
 905   // This can happen along back edges and the equivalence will not be
 906   // applicable as it would require a use before def.
 907   if (k == VREL_EQ && is_a<gphi *> (stmt))
 908     {
 909       tree phi_def = gimple_phi_result (stmt);
 910       gcc_checking_assert (phi_def == op1 || phi_def == op2);
 911       tree arg = op2;
 912       if (phi_def == op2)
 913         arg = op1;
 914       if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
 915         {
 916           if (dump_file && (dump_flags & TDF_DETAILS))
 917             {
 918               fprintf (dump_file, "  Not registered due to ");
 919               print_generic_expr (dump_file, arg, TDF_SLIM);
 920               fprintf (dump_file, " being defined in the same block.\n");
 921             }
 922           return;
 923         }
 924     }
 925   register_relation (gimple_bb (stmt), k, op1, op2);
 926 }
 927
 928 // Register relation K between ssa_name OP1 and OP2 on edge E.
 929
 930 void
 931 relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
 932 {
 933   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 934   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 935
 936   // Do not register lack of relation, or blocks which have more than
 937   // edge E for a predecessor.
 938   if (k == VREL_VARYING || !single_pred_p (e->dest))
 939     return;
 940
 941   if (dump_file && (dump_flags & TDF_DETAILS))
 942     {
 943       value_relation vr (k, op1, op2);
 944       fprintf (dump_file, " Registering value_relation ");
 945       vr.dump (dump_file);
 946       fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
 947     }
 948
 949   register_relation (e->dest, k, op1, op2);
 950 }
 951
 952 // Register relation K between OP! and OP2 in block BB.
 953 // This creates the record and searches for existing records in the dominator
 954 // tree to merge with.
 955
 956 void
 957 dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
 958                                tree op2)
 959 {
 960   // If the 2 ssa_names are the same, do nothing.  An equivalence is implied,
 961   // and no other relation makes sense.
 962   if (op1 == op2)
 963     return;
 964
 965   // Equivalencies are handled by the equivalence oracle.
 966   if (k == VREL_EQ)
 967     equiv_oracle::register_relation (bb, k, op1, op2);
 968   else
 969     {
 970       relation_chain *ptr = set_one_relation (bb, k, op1, op2);
 971       if (ptr)
 972         register_transitives (bb, *ptr);
 973     }
 974 }
 975
 976 // Register relation K between OP! and OP2 in block BB.
 977 // This creates the record and searches for existing records in the dominator
 978 // tree to merge with.  Return the record, or NULL if no record was created.
 979
 980 relation_chain *
 981 dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
 982                               tree op2)
 983 {
 984   gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
 985
 986   value_relation vr(k, op1, op2);
 987   int bbi = bb->index;
 988
 989   if (bbi >= (int)m_relations.length())
 990     m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 991
 992   // Summary bitmap indicating what ssa_names have relations in this BB.
 993   bitmap bm = m_relations[bbi].m_names;
 994   if (!bm)
 995     bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
 996   unsigned v1 = SSA_NAME_VERSION (op1);
 997   unsigned v2 = SSA_NAME_VERSION (op2);
 998
 999   relation_kind curr;
1000   relation_chain *ptr;
1001   curr = find_relation_block (bbi, v1, v2, &ptr);
1002   // There is an existing relation in this block, just intersect with it.
1003   if (curr != VREL_VARYING)
1004     {
1005       if (dump_file && (dump_flags & TDF_DETAILS))
1006         {
1007           fprintf (dump_file, "    Intersecting with existing ");
1008           ptr->dump (dump_file);
1009         }
1010       // Check into whether we can simply replace the relation rather than
1011       // intersecting it.  THis may help with some optimistic iterative
1012       // updating algorithms.
1013       ptr->intersect (vr);
1014       if (dump_file && (dump_flags & TDF_DETAILS))
1015         {
1016           fprintf (dump_file, " to produce ");
1017           ptr->dump (dump_file);
1018           fprintf (dump_file, "\n");
1019         }
1020     }
1021   else
1022     {
1023       if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1024         {
1025           if (dump_file && (dump_flags & TDF_DETAILS))
1026             fprintf (dump_file, "  Not registered due to bb being full\n");
1027           return NULL;
1028         }
1029       m_relations[bbi].m_num_relations++;
1030       // Check for an existing relation further up the DOM chain.
1031       // By including dominating relations, The first one found in any search
1032       // will be the aggregate of all the previous ones.
1033       curr = find_relation_dom (bb, v1, v2);
1034       if (curr != VREL_VARYING)
1035         k = relation_intersect (curr, k);
1036
1037       bitmap_set_bit (bm, v1);
1038       bitmap_set_bit (bm, v2);
1039       bitmap_set_bit (m_relation_set, v1);
1040       bitmap_set_bit (m_relation_set, v2);
1041
1042       ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1043                                               sizeof (relation_chain));
1044       ptr->set_relation (k, op1, op2);
1045       ptr->m_next = m_relations[bbi].m_head;
1046       m_relations[bbi].m_head = ptr;
1047     }
1048   return ptr;
1049 }
1050
1051 // Starting at ROOT_BB search the DOM tree  looking for relations which
1052 // may produce transitive relations to RELATION.  EQUIV1 and EQUIV2 are
1053 // bitmaps for op1/op2 and any of their equivalences that should also be
1054 // considered.
1055
1056 void
1057 dom_oracle::register_transitives (basic_block root_bb,
1058                                   const value_relation &relation)
1059 {
1060   basic_block bb;
1061   // Only apply transitives to certain kinds of operations.
1062   switch (relation.kind ())
1063     {
1064       case VREL_LE:
1065       case VREL_LT:
1066       case VREL_GT:
1067       case VREL_GE:
1068         break;
1069       default:
1070         return;
1071     }
1072
1073   const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1074   const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1075
1076   for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1077     {
1078       int bbi = bb->index;
1079       if (bbi >= (int)m_relations.length())
1080         continue;
1081       const_bitmap bm = m_relations[bbi].m_names;
1082       if (!bm)
1083         continue;
1084       if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1085         continue;
1086       // At least one of the 2 ops has a relation in this block.
1087       relation_chain *ptr;
1088       for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1089         {
1090           // In the presence of an equivalence, 2 operands may do not
1091           // naturally match. ie  with equivalence a_2 == b_3
1092           // given c_1 < a_2 && b_3 < d_4
1093           // convert the second relation (b_3 < d_4) to match any
1094           // equivalences to found in the first relation.
1095           // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1096           // transitive operation:  c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1097
1098           tree r1, r2;
1099           tree p1 = ptr->op1 ();
1100           tree p2 = ptr->op2 ();
1101           // Find which equivalence is in the first operand.
1102           if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1103             r1 = p1;
1104           else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1105             r1 = p2;
1106           else
1107             r1 = NULL_TREE;
1108
1109           // Find which equivalence is in the second operand.
1110           if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1111             r2 = p1;
1112           else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1113             r2 = p2;
1114           else
1115             r2 = NULL_TREE;
1116
1117           // Ignore if both NULL (not relevant relation) or the same,
1118           if (r1 == r2)
1119             continue;
1120
1121           // Any operand not an equivalence, just take the real operand.
1122           if (!r1)
1123             r1 = relation.op1 ();
1124           if (!r2)
1125             r2 = relation.op2 ();
1126
1127           value_relation nr (relation.kind (), r1, r2);
1128           if (nr.apply_transitive (*ptr))
1129             {
1130               if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()))
1131                 return;
1132               if (dump_file && (dump_flags & TDF_DETAILS))
1133                 {
1134                   fprintf (dump_file, "   Registering transitive relation ");
1135                   nr.dump (dump_file);
1136                   fputc ('\n', dump_file);
1137                 }
1138             }
1139
1140         }
1141     }
1142 }
1143
1144 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1145 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1146
1147 relation_kind
1148 dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1149                                       const_bitmap b2) const
1150 {
1151   if (bb >= m_relations.length())
1152     return VREL_VARYING;
1153
1154   return m_relations[bb].find_relation (b1, b2);
1155 }
1156
1157 // Search the DOM tree for a relation between an element of equivalency set B1
1158 // and B2, starting with block BB.
1159
1160 relation_kind
1161 dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1162                             const_bitmap b2)
1163 {
1164   relation_kind r;
1165   if (bitmap_equal_p (b1, b2))
1166     return VREL_EQ;
1167
1168   // If either name does not occur in a relation anywhere, there isnt one.
1169   if (!bitmap_intersect_p (m_relation_set, b1)
1170       || !bitmap_intersect_p (m_relation_set, b2))
1171     return VREL_VARYING;
1172
1173   // Search each block in the DOM tree checking.
1174   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1175     {
1176       r = find_relation_block (bb->index, b1, b2);
1177       if (r != VREL_VARYING)
1178         return r;
1179     }
1180   return VREL_VARYING;
1181
1182 }
1183
1184 // Find a relation in block BB between ssa version V1 and V2.  If a relation
1185 // is found, return a pointer to the chain object in OBJ.
1186
1187 relation_kind
1188 dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1189                                      relation_chain **obj) const
1190 {
1191   if (bb >= (int)m_relations.length())
1192     return VREL_VARYING;
1193
1194   const_bitmap bm = m_relations[bb].m_names;
1195   if (!bm)
1196     return VREL_VARYING;
1197
1198   // If both b1 and b2 aren't referenced in thie block, cant be a relation
1199   if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1200     return VREL_VARYING;
1201
1202   relation_chain *ptr;
1203   for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1204     {
1205       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1206       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1207       if (v1 == op1 && v2 == op2)
1208         {
1209           if (obj)
1210             *obj = ptr;
1211           return ptr->kind ();
1212         }
1213       if (v1 == op2 && v2 == op1)
1214         {
1215           if (obj)
1216             *obj = ptr;
1217           return relation_swap (ptr->kind ());
1218         }
1219     }
1220
1221   return VREL_VARYING;
1222 }
1223
1224 // Find a relation between SSA version V1 and V2 in the dominator tree
1225 // starting with block BB
1226
1227 relation_kind
1228 dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1229 {
1230   relation_kind r;
1231   // IF either name does not occur in a relation anywhere, there isnt one.
1232   if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1233     return VREL_VARYING;
1234
1235   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1236     {
1237       r = find_relation_block (bb->index, v1, v2);
1238       if (r != VREL_VARYING)
1239         return r;
1240     }
1241   return VREL_VARYING;
1242
1243 }
1244
1245 // Query if there is a relation between SSA1 and SS2 in block BB or a
1246 // dominator of BB
1247
1248 relation_kind
1249 dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1250 {
1251   relation_kind kind;
1252   unsigned v1 = SSA_NAME_VERSION (ssa1);
1253   unsigned v2 = SSA_NAME_VERSION (ssa2);
1254   if (v1 == v2)
1255     return VREL_EQ;
1256
1257   // Check for equivalence first.  They must be in each equivalency set.
1258   const_bitmap equiv1 = equiv_set (ssa1, bb);
1259   const_bitmap equiv2 = equiv_set (ssa2, bb);
1260   if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1261     return VREL_EQ;
1262
1263   // Initially look for a direct relationship and just return that.
1264   kind = find_relation_dom (bb, v1, v2);
1265   if (kind != VREL_VARYING)
1266     return kind;
1267
1268   // Query using the equivalence sets.
1269   kind = query_relation (bb, equiv1, equiv2);
1270   return kind;
1271 }
1272
1273 // Dump all the relations in block BB to file F.
1274
1275 void
1276 dom_oracle::dump (FILE *f, basic_block bb) const
1277 {
1278   equiv_oracle::dump (f,bb);
1279
1280   if (bb->index >= (int)m_relations.length ())
1281     return;
1282   if (!m_relations[bb->index].m_names)
1283     return;
1284
1285   relation_chain *ptr = m_relations[bb->index].m_head;
1286   for (; ptr; ptr = ptr->m_next)
1287     {
1288       fprintf (f, "Relational : ");
1289       ptr->dump (f);
1290       fprintf (f, "\n");
1291     }
1292 }
1293
1294 // Dump all the relations known to file F.
1295
1296 void
1297 dom_oracle::dump (FILE *f) const
1298 {
1299   fprintf (f, "Relation dump\n");
1300   for (unsigned i = 0; i < m_relations.length (); i++)
1301     if (BASIC_BLOCK_FOR_FN (cfun, i))
1302       {
1303         fprintf (f, "BB%d\n", i);
1304         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1305       }
1306 }
1307
1308 void
1309 relation_oracle::debug () const
1310 {
1311   dump (stderr);
1312 }
1313
1314 path_oracle::path_oracle (relation_oracle *oracle)
1315 {
1316   set_root_oracle (oracle);
1317   bitmap_obstack_initialize (&m_bitmaps);
1318   obstack_init (&m_chain_obstack);
1319
1320   // Initialize header records.
1321   m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1322   m_equiv.m_bb = NULL;
1323   m_equiv.m_next = NULL;
1324   m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1325   m_relations.m_head = NULL;
1326   m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1327 }
1328
1329 path_oracle::~path_oracle ()
1330 {
1331   obstack_free (&m_chain_obstack, NULL);
1332   bitmap_obstack_release (&m_bitmaps);
1333 }
1334
1335 // Return the equiv set for SSA, and if there isn't one, check for equivs
1336 // starting in block BB.
1337
1338 const_bitmap
1339 path_oracle::equiv_set (tree ssa, basic_block bb)
1340 {
1341   // Check the list first.
1342   equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1343   if (ptr)
1344     return ptr->m_names;
1345
1346   // Otherwise defer to the root oracle.
1347   if (m_root)
1348     return m_root->equiv_set (ssa, bb);
1349
1350   // Allocate a throw away bitmap if there isn't a root oracle.
1351   bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1352   bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1353   return tmp;
1354 }
1355
1356 // Register an equivalence between SSA1 and SSA2 resolving unkowns from
1357 // block BB.
1358
1359 void
1360 path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1361 {
1362   const_bitmap equiv_1 = equiv_set (ssa1, bb);
1363   const_bitmap equiv_2 = equiv_set (ssa2, bb);
1364
1365   // Check if they are the same set, if so, we're done.
1366   if (bitmap_equal_p (equiv_1, equiv_2))
1367     return;
1368
1369   // Don't mess around, simply create a new record and insert it first.
1370   bitmap b = BITMAP_ALLOC (&m_bitmaps);
1371   valid_equivs (b, equiv_1, bb);
1372   valid_equivs (b, equiv_2, bb);
1373
1374   equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1375                                                     sizeof (equiv_chain));
1376   ptr->m_names = b;
1377   ptr->m_bb = NULL;
1378   ptr->m_next = m_equiv.m_next;
1379   m_equiv.m_next = ptr;
1380   bitmap_ior_into (m_equiv.m_names, b);
1381 }
1382
1383 // Register killing definition of an SSA_NAME.
1384
1385 void
1386 path_oracle::killing_def (tree ssa)
1387 {
1388   if (dump_file && (dump_flags & TDF_DETAILS))
1389     {
1390       fprintf (dump_file, " Registering killing_def (path_oracle) ");
1391       print_generic_expr (dump_file, ssa, TDF_SLIM);
1392       fprintf (dump_file, "\n");
1393     }
1394
1395   unsigned v = SSA_NAME_VERSION (ssa);
1396
1397   bitmap_set_bit (m_killed_defs, v);
1398
1399   // Walk the equivalency list and remove SSA from any equivalencies.
1400   if (bitmap_bit_p (m_equiv.m_names, v))
1401     {
1402       for (equiv_chain *ptr = m_equiv.m_next; ptr; ptr = ptr->m_next)
1403         if (bitmap_bit_p (ptr->m_names, v))
1404           bitmap_clear_bit (ptr->m_names, v);
1405     }
1406   else
1407     bitmap_set_bit (m_equiv.m_names, v);
1408
1409   // Now add an equivalency with itself so we don't look to the root oracle.
1410   bitmap b = BITMAP_ALLOC (&m_bitmaps);
1411   bitmap_set_bit (b, v);
1412   equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1413                                                     sizeof (equiv_chain));
1414   ptr->m_names = b;
1415   ptr->m_bb = NULL;
1416   ptr->m_next = m_equiv.m_next;
1417   m_equiv.m_next = ptr;
1418
1419   // Walk the relation list and remove SSA from any relations.
1420   if (!bitmap_bit_p (m_relations.m_names, v))
1421     return;
1422
1423   bitmap_clear_bit (m_relations.m_names, v);
1424   relation_chain **prev = &(m_relations.m_head);
1425   relation_chain *next = NULL;
1426   for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1427     {
1428       gcc_checking_assert (*prev == ptr);
1429       next = ptr->m_next;
1430       if (SSA_NAME_VERSION (ptr->op1 ()) == v
1431           || SSA_NAME_VERSION (ptr->op2 ()) == v)
1432         *prev = ptr->m_next;
1433       else
1434         prev = &(ptr->m_next);
1435     }
1436 }
1437
1438 // Register relation K between SSA1 and SSA2, resolving unknowns by
1439 // querying from BB.
1440
1441 void
1442 path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1443                                 tree ssa2)
1444 {
1445   if (dump_file && (dump_flags & TDF_DETAILS))
1446     {
1447       value_relation vr (k, ssa1, ssa2);
1448       fprintf (dump_file, " Registering value_relation (path_oracle) ");
1449       vr.dump (dump_file);
1450       fprintf (dump_file, " (root: bb%d)\n", bb->index);
1451     }
1452
1453   relation_kind curr = query_relation (bb, ssa1, ssa2);
1454   if (curr != VREL_VARYING)
1455     k = relation_intersect (curr, k);
1456
1457   if (k == VREL_EQ)
1458     {
1459       register_equiv (bb, ssa1, ssa2);
1460       return;
1461     }
1462
1463   bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1464   bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1465   relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1466                                                       sizeof (relation_chain));
1467   ptr->set_relation (k, ssa1, ssa2);
1468   ptr->m_next = m_relations.m_head;
1469   m_relations.m_head = ptr;
1470 }
1471
1472 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1473 // starting at block BB.
1474
1475 relation_kind
1476 path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1477 {
1478   if (bitmap_equal_p (b1, b2))
1479     return VREL_EQ;
1480
1481   relation_kind k = m_relations.find_relation (b1, b2);
1482
1483   // Do not look at the root oracle for names that have been killed
1484   // along the path.
1485   if (bitmap_intersect_p (m_killed_defs, b1)
1486       || bitmap_intersect_p (m_killed_defs, b2))
1487     return k;
1488
1489   if (k == VREL_VARYING && m_root)
1490     k = m_root->query_relation (bb, b1, b2);
1491
1492   return k;
1493 }
1494
1495 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1496 // starting at block BB.
1497
1498 relation_kind
1499 path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1500 {
1501   unsigned v1 = SSA_NAME_VERSION (ssa1);
1502   unsigned v2 = SSA_NAME_VERSION (ssa2);
1503
1504   if (v1 == v2)
1505     return VREL_EQ;
1506
1507   const_bitmap equiv_1 = equiv_set (ssa1, bb);
1508   const_bitmap equiv_2 = equiv_set (ssa2, bb);
1509   if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1510     return VREL_EQ;
1511
1512   return query_relation (bb, equiv_1, equiv_2);
1513 }
1514
1515 // Reset any relations registered on this path.
1516
1517 void
1518 path_oracle::reset_path ()
1519 {
1520   m_equiv.m_next = NULL;
1521   bitmap_clear (m_equiv.m_names);
1522   m_relations.m_head = NULL;
1523   bitmap_clear (m_relations.m_names);
1524   bitmap_clear (m_killed_defs);
1525 }
1526
1527 // Dump relation in basic block... Do nothing here.
1528
1529 void
1530 path_oracle::dump (FILE *, basic_block) const
1531 {
1532 }
1533
1534 // Dump the relations and equivalencies found in the path.
1535
1536 void
1537 path_oracle::dump (FILE *f) const
1538 {
1539   equiv_chain *ptr = m_equiv.m_next;
1540   relation_chain *ptr2 = m_relations.m_head;
1541
1542   if (ptr || ptr2)
1543     fprintf (f, "\npath_oracle:\n");
1544
1545   for (; ptr; ptr = ptr->m_next)
1546     ptr->dump (f);
1547
1548   for (; ptr2; ptr2 = ptr2->m_next)
1549     {
1550       fprintf (f, "Relational : ");
1551       ptr2->dump (f);
1552       fprintf (f, "\n");
1553     }
1554 }