gcc/value-relation.cc

   1 /* Header file for the value range relational processing.
   2    Copyright (C) 2020-2021 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 // These VREL codes are arranged such that VREL_NONE is the first
  36 // code, and all the rest are contiguous up to and including VREL_LAST.
  37
  38 #define VREL_FIRST              VREL_NONE
  39 #define VREL_LAST               NE_EXPR
  40 #define VREL_COUNT              (VREL_LAST - VREL_FIRST + 1)
  41
  42 // vrel_range_assert will either assert that the tree code passed is valid,
  43 // or mark invalid codes as unreachable to help with table optimation.
  44 #if CHECKING_P
  45   #define vrel_range_assert(c)                  \
  46     gcc_checking_assert ((c) >= VREL_FIRST && (c) <= VREL_LAST)
  47 #else
  48   #define vrel_range_assert(c)                  \
  49     if ((c) < VREL_FIRST || (c) > VREL_LAST)    \
  50       gcc_unreachable ();
  51 #endif
  52
  53 static const char *kind_string[VREL_COUNT] =
  54 { "none", "<", "<=", ">", ">=", "empty", "==", "!=" };
  55
  56 // Print a relation_kind REL to file F.
  57
  58 void
  59 print_relation (FILE *f, relation_kind rel)
  60 {
  61   vrel_range_assert (rel);
  62   fprintf (f, " %s ", kind_string[rel - VREL_FIRST]);
  63 }
  64
  65 // This table is used to negate the operands.  op1 REL op2 -> !(op1 REL op2).
  66 relation_kind rr_negate_table[VREL_COUNT] = {
  67 //     NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY,      EQ_EXPR, NE_EXPR
  68   VREL_NONE, GE_EXPR, GT_EXPR, LE_EXPR, LT_EXPR, VREL_EMPTY, NE_EXPR, EQ_EXPR };
  69
  70 // Negate the relation, as in logical negation.
  71
  72 relation_kind
  73 relation_negate (relation_kind r)
  74 {
  75   vrel_range_assert (r);
  76   return rr_negate_table [r - VREL_FIRST];
  77 }
  78
  79 // This table is used to swap the operands.  op1 REL op2 -> op2 REL op1.
  80 relation_kind rr_swap_table[VREL_COUNT] = {
  81 //     NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY,      EQ_EXPR, NE_EXPR
  82   VREL_NONE, GT_EXPR, GE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR };
  83
  84 // Return the relation as if the operands were swapped.
  85
  86 relation_kind
  87 relation_swap (relation_kind r)
  88 {
  89   vrel_range_assert (r);
  90   return rr_swap_table [r - VREL_FIRST];
  91 }
  92
  93 // This table is used to perform an intersection between 2 relations.
  94
  95 relation_kind rr_intersect_table[VREL_COUNT][VREL_COUNT] = {
  96 //   NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
  97 // VREL_NONE
  98   { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR },
  99 // LT_EXPR
 100   { LT_EXPR, LT_EXPR, LT_EXPR, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, LT_EXPR },
 101 // LE_EXPR
 102   { LE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, LT_EXPR },
 103 // GT_EXPR
 104   { GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR },
 105 // GE_EXPR
 106   { GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR },
 107 // VREL_EMPTY
 108   { VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY },
 109 // EQ_EXPR
 110   { EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY },
 111 // NE_EXPR
 112   { NE_EXPR, LT_EXPR, LT_EXPR, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, NE_EXPR } };
 113
 114
 115 // Intersect relation R1 with relation R2 and return the resulting relation.
 116
 117 relation_kind
 118 relation_intersect (relation_kind r1, relation_kind r2)
 119 {
 120   vrel_range_assert (r1);
 121   vrel_range_assert (r2);
 122   return rr_intersect_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
 123 }
 124
 125
 126 // This table is used to perform a union between 2 relations.
 127
 128 relation_kind rr_union_table[VREL_COUNT][VREL_COUNT] = {
 129 //       NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
 130 // VREL_NONE
 131   { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
 132 // LT_EXPR
 133   { VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR, VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR },
 134 // LE_EXPR
 135   { VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE },
 136 // GT_EXPR
 137   { VREL_NONE, NE_EXPR, VREL_NONE, GT_EXPR, GE_EXPR, GT_EXPR, GE_EXPR, NE_EXPR },
 138 // GE_EXPR
 139   { VREL_NONE, VREL_NONE, VREL_NONE, GE_EXPR, GE_EXPR, GE_EXPR, GE_EXPR, VREL_NONE },
 140 // VREL_EMPTY
 141   { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR },
 142 // EQ_EXPR
 143   { VREL_NONE, LE_EXPR, LE_EXPR, GE_EXPR, GE_EXPR, EQ_EXPR, EQ_EXPR, VREL_NONE },
 144 // NE_EXPR
 145   { VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR } };
 146
 147 // Union relation R1 with relation R2 and return the result.
 148
 149 relation_kind
 150 relation_union (relation_kind r1, relation_kind r2)
 151 {
 152   vrel_range_assert (r1);
 153   vrel_range_assert (r2);
 154   return rr_union_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
 155 }
 156
 157
 158 // This table is used to determine transitivity between 2 relations.
 159 // (A relation0 B) and (B relation1 C) implies  (A result C)
 160
 161 relation_kind rr_transitive_table[VREL_COUNT][VREL_COUNT] = {
 162 //   NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
 163 // VREL_NONE
 164   { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
 165 // LT_EXPR
 166   { VREL_NONE, LT_EXPR, LT_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LT_EXPR, VREL_NONE },
 167 // LE_EXPR
 168   { VREL_NONE, LT_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LE_EXPR, VREL_NONE },
 169 // GT_EXPR
 170   { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GT_EXPR, VREL_NONE, GT_EXPR, VREL_NONE },
 171 // GE_EXPR
 172   { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GE_EXPR, VREL_NONE, GE_EXPR, VREL_NONE },
 173 // VREL_EMPTY
 174   { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
 175 // EQ_EXPR
 176   { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_NONE, EQ_EXPR, VREL_NONE },
 177 // NE_EXPR
 178   { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE } };
 179
 180 // Apply transitive operation between relation R1 and relation R2, and
 181 // return the resulting relation, if any.
 182
 183 relation_kind
 184 relation_transitive (relation_kind r1, relation_kind r2)
 185 {
 186   vrel_range_assert (r1);
 187   vrel_range_assert (r2);
 188   return rr_transitive_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
 189 }
 190
 191 // -------------------------------------------------------------------------
 192
 193 // The very first element in the m_equiv chain is actually just a summary
 194 // element in which the m_names bitmap is used to indicate that an ssa_name
 195 // has an equivalence set in this block.
 196 // This allows for much faster traversal of the DOM chain, as a search for
 197 // SSA_NAME simply requires walking the DOM chain until a block is found
 198 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
 199 // that block.   No previous lists need be searched.
 200
 201 // If SSA has an equivalence in this list, find and return it.
 202 // Otherwise return NULL.
 203
 204 equiv_chain *
 205 equiv_chain::find (unsigned ssa)
 206 {
 207   equiv_chain *ptr = NULL;
 208   // If there are equiv sets and SSA is in one in this list, find it.
 209   // Otherwise return NULL.
 210   if (bitmap_bit_p (m_names, ssa))
 211     {
 212       for (ptr = m_next; ptr; ptr = ptr->m_next)
 213         if (bitmap_bit_p (ptr->m_names, ssa))
 214           break;
 215     }
 216   return ptr;
 217 }
 218
 219 // Dump the names in this equivalence set.
 220
 221 void
 222 equiv_chain::dump (FILE *f) const
 223 {
 224   bitmap_iterator bi;
 225   unsigned i;
 226
 227   if (!m_names)
 228     return;
 229   fprintf (f, "Equivalence set : [");
 230   unsigned c = 0;
 231   EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
 232     {
 233       if (ssa_name (i))
 234         {
 235           if (c++)
 236             fprintf (f, ", ");
 237           print_generic_expr (f, ssa_name (i), TDF_SLIM);
 238         }
 239     }
 240   fprintf (f, "]\n");
 241 }
 242
 243 // Instantiate an equivalency oracle.
 244
 245 equiv_oracle::equiv_oracle ()
 246 {
 247   bitmap_obstack_initialize (&m_bitmaps);
 248   m_equiv.create (0);
 249   m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 250   m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
 251   obstack_init (&m_chain_obstack);
 252   m_self_equiv.create (0);
 253   m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
 254 }
 255
 256 // Destruct an equivalency oracle.
 257
 258 equiv_oracle::~equiv_oracle ()
 259 {
 260   m_self_equiv.release ();
 261   obstack_free (&m_chain_obstack, NULL);
 262   m_equiv.release ();
 263   bitmap_obstack_release (&m_bitmaps);
 264 }
 265
 266 // Find and return the equivalency set for SSA along the dominators of BB.
 267 // This is the external API.
 268
 269 const_bitmap
 270 equiv_oracle::equiv_set (tree ssa, basic_block bb)
 271 {
 272   // Search the dominator tree for an equivalency.
 273   equiv_chain *equiv = find_equiv_dom (ssa, bb);
 274   if (equiv)
 275     return equiv->m_names;
 276
 277   // Otherwise return a cached equiv set containing just this SSA.
 278   unsigned v = SSA_NAME_VERSION (ssa);
 279   if (v >= m_self_equiv.length ())
 280     m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
 281
 282   if (!m_self_equiv[v])
 283     {
 284       m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps);
 285       bitmap_set_bit (m_self_equiv[v], v);
 286     }
 287   return m_self_equiv[v];
 288 }
 289
 290 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
 291
 292 relation_kind
 293 equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
 294 {
 295   // If the 2 ssa names share the same equiv set, they are equal.
 296   if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
 297     return EQ_EXPR;
 298   return VREL_NONE;
 299 }
 300
 301 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
 302
 303 relation_kind
 304 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
 305                               const_bitmap e2)
 306 {
 307   // If the 2 ssa names share the same equiv set, they are equal.
 308   if (bitmap_equal_p (e1, e2))
 309     return EQ_EXPR;
 310   return VREL_NONE;
 311 }
 312
 313 // If SSA has an equivalence in block BB, find and return it.
 314 // Otherwise return NULL.
 315
 316 equiv_chain *
 317 equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
 318 {
 319   if (bb >= (int)m_equiv.length () || !m_equiv[bb])
 320     return NULL;
 321
 322   return m_equiv[bb]->find (ssa);
 323 }
 324
 325 // Starting at block BB, walk the dominator chain looking for the nearest
 326 // equivalence set containing NAME.
 327
 328 equiv_chain *
 329 equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
 330 {
 331   unsigned v = SSA_NAME_VERSION (name);
 332   // Short circuit looking for names which have no equivalences.
 333   // Saves time looking for something which does not exist.
 334   if (!bitmap_bit_p (m_equiv_set, v))
 335     return NULL;
 336
 337   // NAME has at least once equivalence set, check to see if it has one along
 338   // the dominator tree.
 339   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 340     {
 341       equiv_chain *ptr = find_equiv_block (v, bb->index);
 342       if (ptr)
 343         return ptr;
 344     }
 345   return NULL;
 346 }
 347
 348 // Register equivalance between ssa_name V and set EQUIV in block BB,
 349
 350 bitmap
 351 equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
 352 {
 353   // V will have an equivalency now.
 354   bitmap_set_bit (m_equiv_set, v);
 355
 356   // If that equiv chain is in this block, simply use it.
 357   if (equiv->m_bb == bb)
 358     {
 359       bitmap_set_bit (equiv->m_names, v);
 360       bitmap_set_bit (m_equiv[bb->index]->m_names, v);
 361       return NULL;
 362     }
 363
 364   // Otherwise create an equivalence for this block which is a copy
 365   // of equiv, the add V to the set.
 366   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 367   bitmap_copy (b, equiv->m_names);
 368   bitmap_set_bit (b, v);
 369   return b;
 370 }
 371
 372 // Register equivalence between set equiv_1 and equiv_2 in block BB.
 373 // Return NULL if either name can be merged with the other.  Otherwise
 374 // return a pointer to the combined bitmap of names.  This allows the
 375 // caller to do any setup required for a new element.
 376
 377 bitmap
 378 equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
 379                               equiv_chain *equiv_2)
 380 {
 381   // If equiv_1 is alreayd in BB, use it as the combined set.
 382   if (equiv_1->m_bb == bb)
 383     {
 384       bitmap_ior_into  (equiv_1->m_names, equiv_2->m_names);
 385       // Its hard to delete from a single linked list, so
 386       // just clear the second one.
 387       if (equiv_2->m_bb == bb)
 388         bitmap_clear (equiv_2->m_names);
 389       else
 390         // Ensure equiv_2s names are in the summary for BB.
 391         bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
 392       return NULL;
 393     }
 394   // If equiv_2 is in BB, use it for the combined set.
 395   if (equiv_2->m_bb == bb)
 396     {
 397       bitmap_ior_into (equiv_2->m_names, equiv_1->m_names);
 398       // Add equiv_1 names into the summary.
 399       bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
 400       return NULL;
 401     }
 402
 403   // At this point, neither equivalence is from this block.
 404   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 405   bitmap_copy (b, equiv_1->m_names);
 406   bitmap_ior_into (b, equiv_2->m_names);
 407   return b;
 408 }
 409
 410
 411 // Register an equivalence between SSA1 and SSA2 in block BB.
 412 // The equivalence oracle maintains a vector of equivalencies indexed by basic
 413 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
 414 // a query is made as to what equivalences both names have already, and
 415 // any preexisting equivalences are merged to create a single equivalence
 416 // containing all the ssa_names in this basic block.
 417
 418 void
 419 equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
 420                                  tree ssa2)
 421 {
 422   // Only handle equality relations.
 423   if (k != EQ_EXPR)
 424     return;
 425
 426   unsigned v1 = SSA_NAME_VERSION (ssa1);
 427   unsigned v2 = SSA_NAME_VERSION (ssa2);
 428   equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
 429   equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
 430
 431   // Check if they are the same set
 432   if (equiv_1 && equiv_1 == equiv_2)
 433     return;
 434
 435   bitmap equiv_set;
 436
 437   // Case where we have 2 SSA_NAMEs that are not in any set.
 438   if (!equiv_1 && !equiv_2)
 439     {
 440       bitmap_set_bit (m_equiv_set, v1);
 441       bitmap_set_bit (m_equiv_set, v2);
 442
 443       equiv_set = BITMAP_ALLOC (&m_bitmaps);
 444       bitmap_set_bit (equiv_set, v1);
 445       bitmap_set_bit (equiv_set, v2);
 446     }
 447   else if (!equiv_1 && equiv_2)
 448     equiv_set = register_equiv (bb, v1, equiv_2);
 449   else if (equiv_1 && !equiv_2)
 450     equiv_set = register_equiv (bb, v2, equiv_1);
 451   else
 452     equiv_set = register_equiv (bb, equiv_1, equiv_2);
 453
 454   // A non-null return is a bitmap that is to be added to the current
 455   // block as a new equivalence.
 456   if (!equiv_set)
 457     return;
 458
 459   equiv_chain *ptr;
 460
 461   // Check if this is the first time a block has an equivalence added.
 462   // and create a header block. And set the summary for this block.
 463   if (!m_equiv[bb->index])
 464     {
 465       ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
 466                                            sizeof (equiv_chain));
 467       ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
 468       bitmap_copy (ptr->m_names, equiv_set);
 469       ptr->m_bb = bb;
 470       ptr->m_next = NULL;
 471       m_equiv[bb->index] = ptr;
 472     }
 473
 474   // Now create the element for this equiv set and initialize it.
 475   ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
 476   ptr->m_names = equiv_set;
 477   ptr->m_bb = bb;
 478   gcc_checking_assert (bb->index < (int)m_equiv.length ());
 479   ptr->m_next = m_equiv[bb->index]->m_next;
 480   m_equiv[bb->index]->m_next = ptr;
 481   bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
 482 }
 483
 484 // Make sure the BB vector is big enough and grow it if needed.
 485
 486 void
 487 equiv_oracle::limit_check (basic_block bb)
 488 {
 489   int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
 490   if (i >= (int)m_equiv.length ())
 491     m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 492 }
 493
 494 // Dump the equivalence sets in BB to file F.
 495
 496 void
 497 equiv_oracle::dump (FILE *f, basic_block bb) const
 498 {
 499   if (bb->index >= (int)m_equiv.length ())
 500     return;
 501   if (!m_equiv[bb->index])
 502     return;
 503
 504   equiv_chain *ptr = m_equiv[bb->index]->m_next;
 505   for (; ptr; ptr = ptr->m_next)
 506     ptr->dump (f);
 507 }
 508
 509 // Dump all equivalence sets known to the oracle.
 510
 511 void
 512 equiv_oracle::dump (FILE *f) const
 513 {
 514   fprintf (f, "Equivalency dump\n");
 515   for (unsigned i = 0; i < m_equiv.length (); i++)
 516     if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
 517       {
 518         fprintf (f, "BB%d\n", i);
 519         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
 520       }
 521 }
 522
 523
 524 // --------------------------------------------------------------------------
 525
 526 // The value-relation class is used to encapsulate the represention of an
 527 // individual relation between 2 ssa-names, and to facilitate operating on
 528 // the relation.
 529
 530 class value_relation
 531 {
 532 public:
 533   value_relation ();
 534   value_relation (relation_kind kind, tree n1, tree n2);
 535   void set_relation (relation_kind kind, tree n1, tree n2);
 536
 537   inline relation_kind kind () const { return related; }
 538   inline tree op1 () const { return name1; }
 539   inline tree op2 () const { return name2; }
 540
 541   bool union_ (value_relation &p);
 542   bool intersect (value_relation &p);
 543   void negate ();
 544   bool apply_transitive (const value_relation &rel);
 545
 546   void dump (FILE *f) const;
 547 private:
 548   relation_kind related;
 549   tree name1, name2;
 550 };
 551
 552 // Set relation R between ssa_name N1 and N2.
 553
 554 inline void
 555 value_relation::set_relation (relation_kind r, tree n1, tree n2)
 556 {
 557   gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2));
 558   related = r;
 559   name1 = n1;
 560   name2 = n2;
 561 }
 562
 563 // Default constructor.
 564
 565 inline
 566 value_relation::value_relation ()
 567 {
 568   related = VREL_NONE;
 569   name1 = NULL_TREE;
 570   name2 = NULL_TREE;
 571 }
 572
 573 // Constructor for relation R between SSA version N1 nd N2.
 574
 575 inline
 576 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
 577 {
 578   set_relation (kind, n1, n2);
 579 }
 580
 581 // Negate the current relation.
 582
 583 void
 584 value_relation::negate ()
 585 {
 586   related = relation_negate (related);
 587 }
 588
 589 // Perform an intersection between 2 relations. *this &&= p.
 590
 591 bool
 592 value_relation::intersect (value_relation &p)
 593 {
 594   // Save previous value
 595   relation_kind old = related;
 596
 597   if (p.op1 () == op1 () && p.op2 () == op2 ())
 598     related = relation_intersect (kind (), p.kind ());
 599   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 600     related = relation_intersect (kind (), relation_swap (p.kind ()));
 601   else
 602     return false;
 603
 604   return old != related;
 605 }
 606
 607 // Perform a union between 2 relations. *this ||= p.
 608
 609 bool
 610 value_relation::union_ (value_relation &p)
 611 {
 612   // Save previous value
 613   relation_kind old = related;
 614
 615   if (p.op1 () == op1 () && p.op2 () == op2 ())
 616     related = relation_union (kind(), p.kind());
 617   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 618     related = relation_union (kind(), relation_swap (p.kind ()));
 619   else
 620     return false;
 621
 622   return old != related;
 623 }
 624
 625 // Identify and apply any transitive relations between REL
 626 // and THIS.  Return true if there was a transformation.
 627
 628 bool
 629 value_relation::apply_transitive (const value_relation &rel)
 630 {
 631   relation_kind k = VREL_NONE;
 632
 633   // Idenity any common operand, and notrmalize the relations to
 634   // the form : A < B  B < C produces A < C
 635   if (rel.op1 () == name2)
 636     {
 637       // A < B   B < C
 638       if (rel.op2 () == name1)
 639         return false;
 640       k = relation_transitive (kind (), rel.kind ());
 641       if (k != VREL_NONE)
 642         {
 643           related = k;
 644           name2 = rel.op2 ();
 645           return true;
 646         }
 647     }
 648   else if (rel.op1 () == name1)
 649     {
 650       // B > A   B < C
 651       if (rel.op2 () == name2)
 652         return false;
 653       k = relation_transitive (relation_swap (kind ()), rel.kind ());
 654       if (k != VREL_NONE)
 655         {
 656           related = k;
 657           name1 = name2;
 658           name2 = rel.op2 ();
 659           return true;
 660         }
 661     }
 662   else if (rel.op2 () == name2)
 663     {
 664        // A < B   C > B
 665        if (rel.op1 () == name1)
 666          return false;
 667       k = relation_transitive (kind (), relation_swap (rel.kind ()));
 668       if (k != VREL_NONE)
 669         {
 670           related = k;
 671           name2 = rel.op1 ();
 672           return true;
 673         }
 674     }
 675   else if (rel.op2 () == name1)
 676     {
 677       // B > A  C > B
 678       if (rel.op1 () == name2)
 679         return false;
 680       k = relation_transitive (relation_swap (kind ()),
 681                                relation_swap (rel.kind ()));
 682       if (k != VREL_NONE)
 683         {
 684           related = k;
 685           name1 = name2;
 686           name2 = rel.op1 ();
 687           return true;
 688         }
 689     }
 690   return false;
 691 }
 692
 693 // Dump the relation to file F.
 694
 695 void
 696 value_relation::dump (FILE *f) const
 697 {
 698   if (!name1 || !name2)
 699     {
 700       fprintf (f, "uninitialized");
 701       return;
 702     }
 703   fputc ('(', f);
 704   print_generic_expr (f, op1 (), TDF_SLIM);
 705   print_relation (f, kind ());
 706   print_generic_expr (f, op2 (), TDF_SLIM);
 707   fputc(')', f);
 708 }
 709
 710 // This container is used to link relations in a chain.
 711
 712 class relation_chain : public value_relation
 713 {
 714 public:
 715   relation_chain *m_next;
 716 };
 717
 718 // ------------------------------------------------------------------------
 719
 720 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
 721 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
 722
 723 relation_kind
 724 relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
 725 {
 726   if (!m_names)
 727     return VREL_NONE;
 728
 729   // If both b1 and b2 aren't referenced in thie block, cant be a relation
 730   if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
 731     return VREL_NONE;
 732
 733   // Search for the fiorst relation that contains BOTH an element from B1
 734   // and B2, and return that relation.
 735   for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
 736     {
 737       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
 738       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
 739       if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
 740         return ptr->kind ();
 741       if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
 742         return relation_swap (ptr->kind ());
 743     }
 744
 745   return VREL_NONE;
 746 }
 747
 748 // Instantiate a relation oracle.
 749
 750 dom_oracle::dom_oracle ()
 751 {
 752   m_relations.create (0);
 753   m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 754   m_relation_set = BITMAP_ALLOC (&m_bitmaps);
 755   m_tmp = BITMAP_ALLOC (&m_bitmaps);
 756   m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
 757 }
 758
 759 // Destruct a relation oracle.
 760
 761 dom_oracle::~dom_oracle ()
 762 {
 763   m_relations.release ();
 764 }
 765
 766 // Register relation K between ssa_name OP1 and OP2 on STMT.
 767
 768 void
 769 relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
 770                                 tree op2)
 771 {
 772   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 773   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 774   gcc_checking_assert (stmt && gimple_bb (stmt));
 775
 776   // Don't register lack of a relation.
 777   if (k == VREL_NONE)
 778     return;
 779
 780   if (dump_file && (dump_flags & TDF_DETAILS))
 781     {
 782       value_relation vr (k, op1, op2);
 783       fprintf (dump_file, " Registering value_relation ");
 784       vr.dump (dump_file);
 785       fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
 786       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 787     }
 788
 789   register_relation (gimple_bb (stmt), k, op1, op2);
 790 }
 791
 792 // Register relation K between ssa_name OP1 and OP2 on edge E.
 793
 794 void
 795 relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
 796 {
 797   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 798   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 799
 800   // Do not register lack of relation, or blocks which have more than
 801   // edge E for a predecessor.
 802   if (k == VREL_NONE || !single_pred_p (e->dest))
 803     return;
 804
 805   if (dump_file && (dump_flags & TDF_DETAILS))
 806     {
 807       value_relation vr (k, op1, op2);
 808       fprintf (dump_file, " Registering value_relation ");
 809       vr.dump (dump_file);
 810       fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
 811     }
 812
 813   register_relation (e->dest, k, op1, op2);
 814 }
 815
 816 // Register relation K between OP! and OP2 in block BB.
 817 // This creates the record and searches for existing records in the dominator
 818 // tree to merge with.
 819
 820 void
 821 dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
 822                                tree op2)
 823 {  // Equivalencies are handled by the equivalence oracle.
 824   if (k == EQ_EXPR)
 825     equiv_oracle::register_relation (bb, k, op1, op2);
 826   else
 827     {
 828       relation_chain *ptr = set_one_relation (bb, k, op1, op2);
 829       register_transitives (bb, *ptr);
 830     }
 831 }
 832
 833 // Register relation K between OP! and OP2 in block BB.
 834 // This creates the record and searches for existing records in the dominator
 835 // tree to merge with.
 836
 837 relation_chain *
 838 dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
 839                               tree op2)
 840 {
 841   gcc_checking_assert (k != VREL_NONE && k != EQ_EXPR);
 842
 843   value_relation vr(k, op1, op2);
 844   int bbi = bb->index;
 845
 846   if (bbi >= (int)m_relations.length())
 847     m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 848
 849   // Summary bitmap indicating what ssa_names have relations in this BB.
 850   bitmap bm = m_relations[bbi].m_names;
 851   if (!bm)
 852     bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
 853   unsigned v1 = SSA_NAME_VERSION (op1);
 854   unsigned v2 = SSA_NAME_VERSION (op2);
 855
 856   relation_kind curr;
 857   relation_chain *ptr;
 858   curr = find_relation_block (bbi, v1, v2, &ptr);
 859   // There is an existing relation in this block, just intersect with it.
 860   if (curr != VREL_NONE)
 861     {
 862       if (dump_file && (dump_flags & TDF_DETAILS))
 863         {
 864           fprintf (dump_file, "    Intersecting with existing ");
 865           ptr->dump (dump_file);
 866         }
 867       // Check into whether we can simply replace the relation rather than
 868       // intersecting it.  THis may help with some optimistic iterative
 869       // updating algorithms.
 870       ptr->intersect (vr);
 871       if (dump_file && (dump_flags & TDF_DETAILS))
 872         {
 873           fprintf (dump_file, " to produce ");
 874           ptr->dump (dump_file);
 875           fprintf (dump_file, "\n");
 876         }
 877     }
 878   else
 879     {
 880       // Check for an existing relation further up the DOM chain.
 881       // By including dominating relations, The first one found in any search
 882       // will be the aggregate of all the previous ones.
 883       curr = find_relation_dom (bb, v1, v2);
 884       if (curr != VREL_NONE)
 885         k = relation_intersect (curr, k);
 886
 887       bitmap_set_bit (bm, v1);
 888       bitmap_set_bit (bm, v2);
 889       bitmap_set_bit (m_relation_set, v1);
 890       bitmap_set_bit (m_relation_set, v2);
 891
 892       ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
 893                                               sizeof (relation_chain));
 894       ptr->set_relation (k, op1, op2);
 895       ptr->m_next = m_relations[bbi].m_head;
 896       m_relations[bbi].m_head = ptr;
 897     }
 898   return ptr;
 899 }
 900
 901 // Starting at ROOT_BB search the DOM tree  looking for relations which
 902 // may produce transitive relations to RELATION.  EQUIV1 and EQUIV2 are
 903 // bitmaps for op1/op2 and any of their equivalences that should also be
 904 // considered.
 905
 906 void
 907 dom_oracle::register_transitives (basic_block root_bb,
 908                                   const value_relation &relation)
 909 {
 910   basic_block bb;
 911   // Only apply transitives to certain kinds of operations.
 912   switch (relation.kind ())
 913     {
 914       case LE_EXPR:
 915       case LT_EXPR:
 916       case GT_EXPR:
 917       case GE_EXPR:
 918         break;
 919       default:
 920         return;
 921     }
 922
 923   const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
 924   const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
 925
 926   for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 927     {
 928       int bbi = bb->index;
 929       if (bbi >= (int)m_relations.length())
 930         continue;
 931       const_bitmap bm = m_relations[bbi].m_names;
 932       if (!bm)
 933         continue;
 934       if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
 935         continue;
 936       // At least one of the 2 ops has a relation in this block.
 937       relation_chain *ptr;
 938       for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
 939         {
 940           // In the presence of an equivalence, 2 operands may do not
 941           // naturally match. ie  with equivalence a_2 == b_3
 942           // given c_1 < a_2 && b_3 < d_4
 943           // convert the second relation (b_3 < d_4) to match any
 944           // equivalences to found in the first relation.
 945           // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
 946           // transitive operation:  c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
 947
 948           tree r1, r2;
 949           tree p1 = ptr->op1 ();
 950           tree p2 = ptr->op2 ();
 951           // Find which equivalence is in the first operand.
 952           if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
 953             r1 = p1;
 954           else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
 955             r1 = p2;
 956           else
 957             r1 = NULL_TREE;
 958
 959           // Find which equivalence is in the second operand.
 960           if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
 961             r2 = p1;
 962           else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
 963             r2 = p2;
 964           else
 965             r2 = NULL_TREE;
 966
 967           // Ignore if both NULL (not relevant relation) or the same,
 968           if (r1 == r2)
 969             continue;
 970
 971           // Any operand not an equivalence, just take the real operand.
 972           if (!r1)
 973             r1 = relation.op1 ();
 974           if (!r2)
 975             r2 = relation.op2 ();
 976
 977           value_relation nr (relation.kind (), r1, r2);
 978           if (nr.apply_transitive (*ptr))
 979             {
 980               set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ());
 981               if (dump_file && (dump_flags & TDF_DETAILS))
 982                 {
 983                   fprintf (dump_file, "   Registering transitive relation ");
 984                   nr.dump (dump_file);
 985                   fputc ('\n', dump_file);
 986                 }
 987             }
 988
 989         }
 990     }
 991 }
 992
 993 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
 994 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
 995
 996 relation_kind
 997 dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
 998                                       const_bitmap b2) const
 999 {
1000   if (bb >= m_relations.length())
1001     return VREL_NONE;
1002
1003   return m_relations[bb].find_relation (b1, b2);
1004 }
1005
1006 // Search the DOM tree for a relation between an element of equivalency set B1
1007 // and B2, starting with block BB.
1008
1009 relation_kind
1010 dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1011                             const_bitmap b2)
1012 {
1013   relation_kind r;
1014   if (bitmap_equal_p (b1, b2))
1015     return EQ_EXPR;
1016
1017   // If either name does not occur in a relation anywhere, there isnt one.
1018   if (!bitmap_intersect_p (m_relation_set, b1)
1019       || !bitmap_intersect_p (m_relation_set, b2))
1020     return VREL_NONE;
1021
1022   // Search each block in the DOM tree checking.
1023   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1024     {
1025       r = find_relation_block (bb->index, b1, b2);
1026       if (r != VREL_NONE)
1027         return r;
1028     }
1029   return VREL_NONE;
1030
1031 }
1032
1033 // Find a relation in block BB between ssa version V1 and V2.  If a relation
1034 // is found, return a pointer to the chain object in OBJ.
1035
1036 relation_kind
1037 dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1038                                      relation_chain **obj) const
1039 {
1040   if (bb >= (int)m_relations.length())
1041     return VREL_NONE;
1042
1043   const_bitmap bm = m_relations[bb].m_names;
1044   if (!bm)
1045     return VREL_NONE;
1046
1047   // If both b1 and b2 aren't referenced in thie block, cant be a relation
1048   if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1049     return VREL_NONE;
1050
1051   relation_chain *ptr;
1052   for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1053     {
1054       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1055       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1056       if (v1 == op1 && v2 == op2)
1057         {
1058           if (obj)
1059             *obj = ptr;
1060           return ptr->kind ();
1061         }
1062       if (v1 == op2 && v2 == op1)
1063         {
1064           if (obj)
1065             *obj = ptr;
1066           return relation_swap (ptr->kind ());
1067         }
1068     }
1069
1070   return VREL_NONE;
1071 }
1072
1073 // Find a relation between SSA version V1 and V2 in the dominator tree
1074 // starting with block BB
1075
1076 relation_kind
1077 dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1078 {
1079   relation_kind r;
1080   // IF either name does not occur in a relation anywhere, there isnt one.
1081   if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1082     return VREL_NONE;
1083
1084   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1085     {
1086       r = find_relation_block (bb->index, v1, v2);
1087       if (r != VREL_NONE)
1088         return r;
1089     }
1090   return VREL_NONE;
1091
1092 }
1093
1094 // Query if there is a relation between SSA1 and SS2 in block BB or a
1095 // dominator of BB
1096
1097 relation_kind
1098 dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1099 {
1100   relation_kind kind;
1101   unsigned v1 = SSA_NAME_VERSION (ssa1);
1102   unsigned v2 = SSA_NAME_VERSION (ssa2);
1103   if (v1 == v2)
1104     return EQ_EXPR;
1105
1106   // Check for equivalence first.  They must be in each equivalency set.
1107   const_bitmap equiv1 = equiv_set (ssa1, bb);
1108   const_bitmap equiv2 = equiv_set (ssa2, bb);
1109   if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1110     return EQ_EXPR;
1111
1112   // Initially look for a direct relationship and just return that.
1113   kind = find_relation_dom (bb, v1, v2);
1114   if (kind != VREL_NONE)
1115     return kind;
1116
1117   // Query using the equiovalence sets.
1118   kind = query_relation (bb, equiv1, equiv2);
1119   return kind;
1120 }
1121
1122 // Dump all the relations in block BB to file F.
1123
1124 void
1125 dom_oracle::dump (FILE *f, basic_block bb) const
1126 {
1127   equiv_oracle::dump (f,bb);
1128
1129   if (bb->index >= (int)m_relations.length ())
1130     return;
1131   if (!m_relations[bb->index].m_names)
1132     return;
1133
1134   relation_chain *ptr = m_relations[bb->index].m_head;
1135   for (; ptr; ptr = ptr->m_next)
1136     {
1137       fprintf (f, "Relational : ");
1138       ptr->dump (f);
1139       fprintf (f, "\n");
1140     }
1141 }
1142
1143 // Dump all the relations known to file F.
1144
1145 void
1146 dom_oracle::dump (FILE *f) const
1147 {
1148   fprintf (f, "Relation dump\n");
1149   for (unsigned i = 0; i < m_relations.length (); i++)
1150     if (BASIC_BLOCK_FOR_FN (cfun, i))
1151       {
1152         fprintf (f, "BB%d\n", i);
1153         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1154       }
1155 }
1156
1157 void
1158 relation_oracle::debug () const
1159 {
1160   dump (stderr);
1161 }
1162
1163 path_oracle::path_oracle (relation_oracle *oracle)
1164 {
1165   m_root = oracle;
1166   bitmap_obstack_initialize (&m_bitmaps);
1167   obstack_init (&m_chain_obstack);
1168
1169   // Initialize header records.
1170   m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1171   m_equiv.m_bb = NULL;
1172   m_equiv.m_next = NULL;
1173   m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1174   m_relations.m_head = NULL;
1175 }
1176
1177 path_oracle::~path_oracle ()
1178 {
1179   obstack_free (&m_chain_obstack, NULL);
1180   bitmap_obstack_release (&m_bitmaps);
1181 }
1182
1183 // Return the equiv set for SSA, and if there isn't one, check for equivs
1184 // starting in block BB.
1185
1186 const_bitmap
1187 path_oracle::equiv_set (tree ssa, basic_block bb)
1188 {
1189   // Check the list first.
1190   equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1191   if (ptr)
1192     return ptr->m_names;
1193
1194   // Otherwise defer to the root oracle.
1195   if (m_root)
1196     return m_root->equiv_set (ssa, bb);
1197
1198   // Allocate a throw away bitmap if there isn't a root oracle.
1199   bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1200   bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1201   return tmp;
1202 }
1203
1204 // Register an equivalence between SSA1 and SSA2 resolving unkowns from
1205 // block BB.
1206
1207 void
1208 path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1209 {
1210   const_bitmap equiv_1 = equiv_set (ssa1, bb);
1211   const_bitmap equiv_2 = equiv_set (ssa2, bb);
1212
1213   // Check if they are the same set, if so, we're done.
1214   if (bitmap_equal_p (equiv_1, equiv_2))
1215     return;
1216
1217   // Don't mess around, simply create a new record and insert it first.
1218   bitmap b = BITMAP_ALLOC (&m_bitmaps);
1219   bitmap_copy (b, equiv_1);
1220   bitmap_ior_into (b, equiv_2);
1221
1222   equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1223                                                     sizeof (equiv_chain));
1224   ptr->m_names = b;
1225   ptr->m_bb = NULL;
1226   ptr->m_next = m_equiv.m_next;
1227   m_equiv.m_next = ptr;
1228   bitmap_ior_into (m_equiv.m_names, b);
1229 }
1230
1231 // Register relation K between SSA1 and SSA2, resolving unknowns by
1232 // querying from BB.
1233
1234 void
1235 path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1236                                 tree ssa2)
1237 {
1238   if (dump_file && (dump_flags & TDF_DETAILS))
1239     {
1240       value_relation vr (k, ssa1, ssa2);
1241       fprintf (dump_file, " Registering value_relation (path_oracle) ");
1242       vr.dump (dump_file);
1243       fprintf (dump_file, " (bb%d)\n", bb->index);
1244     }
1245
1246   if (k == EQ_EXPR)
1247     {
1248       register_equiv (bb, ssa1, ssa2);
1249       return;
1250     }
1251
1252   relation_kind curr = query_relation (bb, ssa1, ssa2);
1253   if (curr != VREL_NONE)
1254     k = relation_intersect (curr, k);
1255
1256   bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1257   bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1258   relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1259                                                       sizeof (relation_chain));
1260   ptr->set_relation (k, ssa1, ssa2);
1261   ptr->m_next = m_relations.m_head;
1262   m_relations.m_head = ptr;
1263 }
1264
1265 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1266 // starting at block BB.
1267
1268 relation_kind
1269 path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1270 {
1271   if (bitmap_equal_p (b1, b2))
1272     return EQ_EXPR;
1273
1274   relation_kind k = m_relations.find_relation (b1, b2);
1275
1276   if (k == VREL_NONE && m_root)
1277     k = m_root->query_relation (bb, b1, b2);
1278
1279   return k;
1280 }
1281
1282 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1283 // starting at block BB.
1284
1285 relation_kind
1286 path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1287 {
1288   unsigned v1 = SSA_NAME_VERSION (ssa1);
1289   unsigned v2 = SSA_NAME_VERSION (ssa2);
1290
1291   if (v1 == v2)
1292     return EQ_EXPR;
1293
1294   const_bitmap equiv_1 = equiv_set (ssa1, bb);
1295   const_bitmap equiv_2 = equiv_set (ssa2, bb);
1296   if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1297     return EQ_EXPR;
1298
1299   return query_relation (bb, equiv_1, equiv_2);
1300 }
1301
1302 // Reset any relations registered on this path.
1303
1304 void
1305 path_oracle::reset_path ()
1306 {
1307   m_equiv.m_next = NULL;
1308   bitmap_clear (m_equiv.m_names);
1309   m_relations.m_head = NULL;
1310   bitmap_clear (m_relations.m_names);
1311 }
1312
1313 // Dump relation in basic block... Do nothing here.
1314
1315 void
1316 path_oracle::dump (FILE *, basic_block) const
1317 {
1318 }
1319
1320 // Dump the relations and equivalencies found in the path.
1321
1322 void
1323 path_oracle::dump (FILE *f) const
1324 {
1325   equiv_chain *ptr = m_equiv.m_next;
1326   for (; ptr; ptr = ptr->m_next)
1327     ptr->dump (f);
1328
1329   relation_chain *ptr2 = m_relations.m_head;
1330   for (; ptr2; ptr2 = ptr2->m_next)
1331     {
1332       fprintf (f, "Relational : ");
1333       ptr2->dump (f);
1334       fprintf (f, "\n");
1335     }
1336 }