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 // Create an equivalency set containing only SSA in its definition block.
 411 // This is done the first time SSA is registered in an equivalency and blocks
 412 // any DOM searches past the definition.
 413
 414 void
 415 equiv_oracle::register_initial_def (tree ssa)
 416 {
 417   if (SSA_NAME_IS_DEFAULT_DEF (ssa))
 418     return;
 419   basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
 420   gcc_checking_assert (bb && !find_equiv_dom (ssa, bb));
 421
 422   unsigned v = SSA_NAME_VERSION (ssa);
 423   bitmap_set_bit (m_equiv_set, v);
 424   bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
 425   bitmap_set_bit (equiv_set, v);
 426   add_equiv_to_block (bb, equiv_set);
 427 }
 428
 429 // Register an equivalence between SSA1 and SSA2 in block BB.
 430 // The equivalence oracle maintains a vector of equivalencies indexed by basic
 431 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
 432 // a query is made as to what equivalences both names have already, and
 433 // any preexisting equivalences are merged to create a single equivalence
 434 // containing all the ssa_names in this basic block.
 435
 436 void
 437 equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
 438                                  tree ssa2)
 439 {
 440   // Only handle equality relations.
 441   if (k != EQ_EXPR)
 442     return;
 443
 444   unsigned v1 = SSA_NAME_VERSION (ssa1);
 445   unsigned v2 = SSA_NAME_VERSION (ssa2);
 446
 447   // If this is the first time an ssa_name has an equivalency registered
 448   // create a self-equivalency record in the def block.
 449   if (!bitmap_bit_p (m_equiv_set, v1))
 450     register_initial_def (ssa1);
 451   if (!bitmap_bit_p (m_equiv_set, v2))
 452     register_initial_def (ssa2);
 453
 454   equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
 455   equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
 456
 457   // Check if they are the same set
 458   if (equiv_1 && equiv_1 == equiv_2)
 459     return;
 460
 461   bitmap equiv_set;
 462
 463   // Case where we have 2 SSA_NAMEs that are not in any set.
 464   if (!equiv_1 && !equiv_2)
 465     {
 466       bitmap_set_bit (m_equiv_set, v1);
 467       bitmap_set_bit (m_equiv_set, v2);
 468
 469       equiv_set = BITMAP_ALLOC (&m_bitmaps);
 470       bitmap_set_bit (equiv_set, v1);
 471       bitmap_set_bit (equiv_set, v2);
 472     }
 473   else if (!equiv_1 && equiv_2)
 474     equiv_set = register_equiv (bb, v1, equiv_2);
 475   else if (equiv_1 && !equiv_2)
 476     equiv_set = register_equiv (bb, v2, equiv_1);
 477   else
 478     equiv_set = register_equiv (bb, equiv_1, equiv_2);
 479
 480   // A non-null return is a bitmap that is to be added to the current
 481   // block as a new equivalence.
 482   if (!equiv_set)
 483     return;
 484
 485   add_equiv_to_block (bb, equiv_set);
 486 }
 487
 488 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
 489 // Note the internal caller is responible for allocating EQUIV_SET properly.
 490
 491 void
 492 equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
 493 {
 494   equiv_chain *ptr;
 495
 496   // Check if this is the first time a block has an equivalence added.
 497   // and create a header block. And set the summary for this block.
 498   if (!m_equiv[bb->index])
 499     {
 500       ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
 501                                            sizeof (equiv_chain));
 502       ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
 503       bitmap_copy (ptr->m_names, equiv_set);
 504       ptr->m_bb = bb;
 505       ptr->m_next = NULL;
 506       m_equiv[bb->index] = ptr;
 507     }
 508
 509   // Now create the element for this equiv set and initialize it.
 510   ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
 511   ptr->m_names = equiv_set;
 512   ptr->m_bb = bb;
 513   gcc_checking_assert (bb->index < (int)m_equiv.length ());
 514   ptr->m_next = m_equiv[bb->index]->m_next;
 515   m_equiv[bb->index]->m_next = ptr;
 516   bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
 517 }
 518
 519 // Make sure the BB vector is big enough and grow it if needed.
 520
 521 void
 522 equiv_oracle::limit_check (basic_block bb)
 523 {
 524   int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
 525   if (i >= (int)m_equiv.length ())
 526     m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 527 }
 528
 529 // Dump the equivalence sets in BB to file F.
 530
 531 void
 532 equiv_oracle::dump (FILE *f, basic_block bb) const
 533 {
 534   if (bb->index >= (int)m_equiv.length ())
 535     return;
 536   if (!m_equiv[bb->index])
 537     return;
 538
 539   equiv_chain *ptr = m_equiv[bb->index]->m_next;
 540   for (; ptr; ptr = ptr->m_next)
 541     ptr->dump (f);
 542 }
 543
 544 // Dump all equivalence sets known to the oracle.
 545
 546 void
 547 equiv_oracle::dump (FILE *f) const
 548 {
 549   fprintf (f, "Equivalency dump\n");
 550   for (unsigned i = 0; i < m_equiv.length (); i++)
 551     if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
 552       {
 553         fprintf (f, "BB%d\n", i);
 554         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
 555       }
 556 }
 557
 558
 559 // --------------------------------------------------------------------------
 560
 561 // The value-relation class is used to encapsulate the represention of an
 562 // individual relation between 2 ssa-names, and to facilitate operating on
 563 // the relation.
 564
 565 class value_relation
 566 {
 567 public:
 568   value_relation ();
 569   value_relation (relation_kind kind, tree n1, tree n2);
 570   void set_relation (relation_kind kind, tree n1, tree n2);
 571
 572   inline relation_kind kind () const { return related; }
 573   inline tree op1 () const { return name1; }
 574   inline tree op2 () const { return name2; }
 575
 576   bool union_ (value_relation &p);
 577   bool intersect (value_relation &p);
 578   void negate ();
 579   bool apply_transitive (const value_relation &rel);
 580
 581   void dump (FILE *f) const;
 582 private:
 583   relation_kind related;
 584   tree name1, name2;
 585 };
 586
 587 // Set relation R between ssa_name N1 and N2.
 588
 589 inline void
 590 value_relation::set_relation (relation_kind r, tree n1, tree n2)
 591 {
 592   gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2));
 593   related = r;
 594   name1 = n1;
 595   name2 = n2;
 596 }
 597
 598 // Default constructor.
 599
 600 inline
 601 value_relation::value_relation ()
 602 {
 603   related = VREL_NONE;
 604   name1 = NULL_TREE;
 605   name2 = NULL_TREE;
 606 }
 607
 608 // Constructor for relation R between SSA version N1 nd N2.
 609
 610 inline
 611 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
 612 {
 613   set_relation (kind, n1, n2);
 614 }
 615
 616 // Negate the current relation.
 617
 618 void
 619 value_relation::negate ()
 620 {
 621   related = relation_negate (related);
 622 }
 623
 624 // Perform an intersection between 2 relations. *this &&= p.
 625
 626 bool
 627 value_relation::intersect (value_relation &p)
 628 {
 629   // Save previous value
 630   relation_kind old = related;
 631
 632   if (p.op1 () == op1 () && p.op2 () == op2 ())
 633     related = relation_intersect (kind (), p.kind ());
 634   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 635     related = relation_intersect (kind (), relation_swap (p.kind ()));
 636   else
 637     return false;
 638
 639   return old != related;
 640 }
 641
 642 // Perform a union between 2 relations. *this ||= p.
 643
 644 bool
 645 value_relation::union_ (value_relation &p)
 646 {
 647   // Save previous value
 648   relation_kind old = related;
 649
 650   if (p.op1 () == op1 () && p.op2 () == op2 ())
 651     related = relation_union (kind(), p.kind());
 652   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 653     related = relation_union (kind(), relation_swap (p.kind ()));
 654   else
 655     return false;
 656
 657   return old != related;
 658 }
 659
 660 // Identify and apply any transitive relations between REL
 661 // and THIS.  Return true if there was a transformation.
 662
 663 bool
 664 value_relation::apply_transitive (const value_relation &rel)
 665 {
 666   relation_kind k = VREL_NONE;
 667
 668   // Idenity any common operand, and notrmalize the relations to
 669   // the form : A < B  B < C produces A < C
 670   if (rel.op1 () == name2)
 671     {
 672       // A < B   B < C
 673       if (rel.op2 () == name1)
 674         return false;
 675       k = relation_transitive (kind (), rel.kind ());
 676       if (k != VREL_NONE)
 677         {
 678           related = k;
 679           name2 = rel.op2 ();
 680           return true;
 681         }
 682     }
 683   else if (rel.op1 () == name1)
 684     {
 685       // B > A   B < C
 686       if (rel.op2 () == name2)
 687         return false;
 688       k = relation_transitive (relation_swap (kind ()), rel.kind ());
 689       if (k != VREL_NONE)
 690         {
 691           related = k;
 692           name1 = name2;
 693           name2 = rel.op2 ();
 694           return true;
 695         }
 696     }
 697   else if (rel.op2 () == name2)
 698     {
 699        // A < B   C > B
 700        if (rel.op1 () == name1)
 701          return false;
 702       k = relation_transitive (kind (), relation_swap (rel.kind ()));
 703       if (k != VREL_NONE)
 704         {
 705           related = k;
 706           name2 = rel.op1 ();
 707           return true;
 708         }
 709     }
 710   else if (rel.op2 () == name1)
 711     {
 712       // B > A  C > B
 713       if (rel.op1 () == name2)
 714         return false;
 715       k = relation_transitive (relation_swap (kind ()),
 716                                relation_swap (rel.kind ()));
 717       if (k != VREL_NONE)
 718         {
 719           related = k;
 720           name1 = name2;
 721           name2 = rel.op1 ();
 722           return true;
 723         }
 724     }
 725   return false;
 726 }
 727
 728 // Dump the relation to file F.
 729
 730 void
 731 value_relation::dump (FILE *f) const
 732 {
 733   if (!name1 || !name2)
 734     {
 735       fprintf (f, "uninitialized");
 736       return;
 737     }
 738   fputc ('(', f);
 739   print_generic_expr (f, op1 (), TDF_SLIM);
 740   print_relation (f, kind ());
 741   print_generic_expr (f, op2 (), TDF_SLIM);
 742   fputc(')', f);
 743 }
 744
 745 // This container is used to link relations in a chain.
 746
 747 class relation_chain : public value_relation
 748 {
 749 public:
 750   relation_chain *m_next;
 751 };
 752
 753 // ------------------------------------------------------------------------
 754
 755 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
 756 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
 757
 758 relation_kind
 759 relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
 760 {
 761   if (!m_names)
 762     return VREL_NONE;
 763
 764   // If both b1 and b2 aren't referenced in thie block, cant be a relation
 765   if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
 766     return VREL_NONE;
 767
 768   // Search for the fiorst relation that contains BOTH an element from B1
 769   // and B2, and return that relation.
 770   for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
 771     {
 772       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
 773       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
 774       if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
 775         return ptr->kind ();
 776       if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
 777         return relation_swap (ptr->kind ());
 778     }
 779
 780   return VREL_NONE;
 781 }
 782
 783 // Instantiate a relation oracle.
 784
 785 dom_oracle::dom_oracle ()
 786 {
 787   m_relations.create (0);
 788   m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 789   m_relation_set = BITMAP_ALLOC (&m_bitmaps);
 790   m_tmp = BITMAP_ALLOC (&m_bitmaps);
 791   m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
 792 }
 793
 794 // Destruct a relation oracle.
 795
 796 dom_oracle::~dom_oracle ()
 797 {
 798   m_relations.release ();
 799 }
 800
 801 // Register relation K between ssa_name OP1 and OP2 on STMT.
 802
 803 void
 804 relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
 805                                 tree op2)
 806 {
 807   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 808   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 809   gcc_checking_assert (stmt && gimple_bb (stmt));
 810
 811   // Don't register lack of a relation.
 812   if (k == VREL_NONE)
 813     return;
 814
 815   if (dump_file && (dump_flags & TDF_DETAILS))
 816     {
 817       value_relation vr (k, op1, op2);
 818       fprintf (dump_file, " Registering value_relation ");
 819       vr.dump (dump_file);
 820       fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
 821       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 822     }
 823
 824   // If an equivalence is being added between a PHI and one of its arguments
 825   // make sure that that argument is not defined in the same block.
 826   // This can happen along back edges and the equivalence will not be
 827   // applicable as it would require a use before def.
 828   if (k == EQ_EXPR && is_a<gphi *> (stmt))
 829     {
 830       tree phi_def = gimple_phi_result (stmt);
 831       gcc_checking_assert (phi_def == op1 || phi_def == op2);
 832       tree arg = op2;
 833       if (phi_def == op2)
 834         arg = op1;
 835       if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
 836         {
 837           if (dump_file && (dump_flags & TDF_DETAILS))
 838             {
 839               fprintf (dump_file, "  Not registered due to ");
 840               print_generic_expr (dump_file, arg, TDF_SLIM);
 841               fprintf (dump_file, " being defined in the same block.\n");
 842             }
 843           return;
 844         }
 845     }
 846   register_relation (gimple_bb (stmt), k, op1, op2);
 847 }
 848
 849 // Register relation K between ssa_name OP1 and OP2 on edge E.
 850
 851 void
 852 relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
 853 {
 854   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 855   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 856
 857   // Do not register lack of relation, or blocks which have more than
 858   // edge E for a predecessor.
 859   if (k == VREL_NONE || !single_pred_p (e->dest))
 860     return;
 861
 862   if (dump_file && (dump_flags & TDF_DETAILS))
 863     {
 864       value_relation vr (k, op1, op2);
 865       fprintf (dump_file, " Registering value_relation ");
 866       vr.dump (dump_file);
 867       fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
 868     }
 869
 870   register_relation (e->dest, k, op1, op2);
 871 }
 872
 873 // Register relation K between OP! and OP2 in block BB.
 874 // This creates the record and searches for existing records in the dominator
 875 // tree to merge with.
 876
 877 void
 878 dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
 879                                tree op2)
 880 {  // Equivalencies are handled by the equivalence oracle.
 881   if (k == EQ_EXPR)
 882     equiv_oracle::register_relation (bb, k, op1, op2);
 883   else
 884     {
 885       relation_chain *ptr = set_one_relation (bb, k, op1, op2);
 886       register_transitives (bb, *ptr);
 887     }
 888 }
 889
 890 // Register relation K between OP! and OP2 in block BB.
 891 // This creates the record and searches for existing records in the dominator
 892 // tree to merge with.
 893
 894 relation_chain *
 895 dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
 896                               tree op2)
 897 {
 898   gcc_checking_assert (k != VREL_NONE && k != EQ_EXPR);
 899
 900   value_relation vr(k, op1, op2);
 901   int bbi = bb->index;
 902
 903   if (bbi >= (int)m_relations.length())
 904     m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 905
 906   // Summary bitmap indicating what ssa_names have relations in this BB.
 907   bitmap bm = m_relations[bbi].m_names;
 908   if (!bm)
 909     bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
 910   unsigned v1 = SSA_NAME_VERSION (op1);
 911   unsigned v2 = SSA_NAME_VERSION (op2);
 912
 913   relation_kind curr;
 914   relation_chain *ptr;
 915   curr = find_relation_block (bbi, v1, v2, &ptr);
 916   // There is an existing relation in this block, just intersect with it.
 917   if (curr != VREL_NONE)
 918     {
 919       if (dump_file && (dump_flags & TDF_DETAILS))
 920         {
 921           fprintf (dump_file, "    Intersecting with existing ");
 922           ptr->dump (dump_file);
 923         }
 924       // Check into whether we can simply replace the relation rather than
 925       // intersecting it.  THis may help with some optimistic iterative
 926       // updating algorithms.
 927       ptr->intersect (vr);
 928       if (dump_file && (dump_flags & TDF_DETAILS))
 929         {
 930           fprintf (dump_file, " to produce ");
 931           ptr->dump (dump_file);
 932           fprintf (dump_file, "\n");
 933         }
 934     }
 935   else
 936     {
 937       // Check for an existing relation further up the DOM chain.
 938       // By including dominating relations, The first one found in any search
 939       // will be the aggregate of all the previous ones.
 940       curr = find_relation_dom (bb, v1, v2);
 941       if (curr != VREL_NONE)
 942         k = relation_intersect (curr, k);
 943
 944       bitmap_set_bit (bm, v1);
 945       bitmap_set_bit (bm, v2);
 946       bitmap_set_bit (m_relation_set, v1);
 947       bitmap_set_bit (m_relation_set, v2);
 948
 949       ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
 950                                               sizeof (relation_chain));
 951       ptr->set_relation (k, op1, op2);
 952       ptr->m_next = m_relations[bbi].m_head;
 953       m_relations[bbi].m_head = ptr;
 954     }
 955   return ptr;
 956 }
 957
 958 // Starting at ROOT_BB search the DOM tree  looking for relations which
 959 // may produce transitive relations to RELATION.  EQUIV1 and EQUIV2 are
 960 // bitmaps for op1/op2 and any of their equivalences that should also be
 961 // considered.
 962
 963 void
 964 dom_oracle::register_transitives (basic_block root_bb,
 965                                   const value_relation &relation)
 966 {
 967   basic_block bb;
 968   // Only apply transitives to certain kinds of operations.
 969   switch (relation.kind ())
 970     {
 971       case LE_EXPR:
 972       case LT_EXPR:
 973       case GT_EXPR:
 974       case GE_EXPR:
 975         break;
 976       default:
 977         return;
 978     }
 979
 980   const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
 981   const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
 982
 983   for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 984     {
 985       int bbi = bb->index;
 986       if (bbi >= (int)m_relations.length())
 987         continue;
 988       const_bitmap bm = m_relations[bbi].m_names;
 989       if (!bm)
 990         continue;
 991       if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
 992         continue;
 993       // At least one of the 2 ops has a relation in this block.
 994       relation_chain *ptr;
 995       for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
 996         {
 997           // In the presence of an equivalence, 2 operands may do not
 998           // naturally match. ie  with equivalence a_2 == b_3
 999           // given c_1 < a_2 && b_3 < d_4
1000           // convert the second relation (b_3 < d_4) to match any
1001           // equivalences to found in the first relation.
1002           // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1003           // transitive operation:  c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1004
1005           tree r1, r2;
1006           tree p1 = ptr->op1 ();
1007           tree p2 = ptr->op2 ();
1008           // Find which equivalence is in the first operand.
1009           if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1010             r1 = p1;
1011           else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1012             r1 = p2;
1013           else
1014             r1 = NULL_TREE;
1015
1016           // Find which equivalence is in the second operand.
1017           if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1018             r2 = p1;
1019           else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1020             r2 = p2;
1021           else
1022             r2 = NULL_TREE;
1023
1024           // Ignore if both NULL (not relevant relation) or the same,
1025           if (r1 == r2)
1026             continue;
1027
1028           // Any operand not an equivalence, just take the real operand.
1029           if (!r1)
1030             r1 = relation.op1 ();
1031           if (!r2)
1032             r2 = relation.op2 ();
1033
1034           value_relation nr (relation.kind (), r1, r2);
1035           if (nr.apply_transitive (*ptr))
1036             {
1037               set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ());
1038               if (dump_file && (dump_flags & TDF_DETAILS))
1039                 {
1040                   fprintf (dump_file, "   Registering transitive relation ");
1041                   nr.dump (dump_file);
1042                   fputc ('\n', dump_file);
1043                 }
1044             }
1045
1046         }
1047     }
1048 }
1049
1050 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1051 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1052
1053 relation_kind
1054 dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1055                                       const_bitmap b2) const
1056 {
1057   if (bb >= m_relations.length())
1058     return VREL_NONE;
1059
1060   return m_relations[bb].find_relation (b1, b2);
1061 }
1062
1063 // Search the DOM tree for a relation between an element of equivalency set B1
1064 // and B2, starting with block BB.
1065
1066 relation_kind
1067 dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1068                             const_bitmap b2)
1069 {
1070   relation_kind r;
1071   if (bitmap_equal_p (b1, b2))
1072     return EQ_EXPR;
1073
1074   // If either name does not occur in a relation anywhere, there isnt one.
1075   if (!bitmap_intersect_p (m_relation_set, b1)
1076       || !bitmap_intersect_p (m_relation_set, b2))
1077     return VREL_NONE;
1078
1079   // Search each block in the DOM tree checking.
1080   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1081     {
1082       r = find_relation_block (bb->index, b1, b2);
1083       if (r != VREL_NONE)
1084         return r;
1085     }
1086   return VREL_NONE;
1087
1088 }
1089
1090 // Find a relation in block BB between ssa version V1 and V2.  If a relation
1091 // is found, return a pointer to the chain object in OBJ.
1092
1093 relation_kind
1094 dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1095                                      relation_chain **obj) const
1096 {
1097   if (bb >= (int)m_relations.length())
1098     return VREL_NONE;
1099
1100   const_bitmap bm = m_relations[bb].m_names;
1101   if (!bm)
1102     return VREL_NONE;
1103
1104   // If both b1 and b2 aren't referenced in thie block, cant be a relation
1105   if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1106     return VREL_NONE;
1107
1108   relation_chain *ptr;
1109   for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1110     {
1111       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1112       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1113       if (v1 == op1 && v2 == op2)
1114         {
1115           if (obj)
1116             *obj = ptr;
1117           return ptr->kind ();
1118         }
1119       if (v1 == op2 && v2 == op1)
1120         {
1121           if (obj)
1122             *obj = ptr;
1123           return relation_swap (ptr->kind ());
1124         }
1125     }
1126
1127   return VREL_NONE;
1128 }
1129
1130 // Find a relation between SSA version V1 and V2 in the dominator tree
1131 // starting with block BB
1132
1133 relation_kind
1134 dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1135 {
1136   relation_kind r;
1137   // IF either name does not occur in a relation anywhere, there isnt one.
1138   if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1139     return VREL_NONE;
1140
1141   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1142     {
1143       r = find_relation_block (bb->index, v1, v2);
1144       if (r != VREL_NONE)
1145         return r;
1146     }
1147   return VREL_NONE;
1148
1149 }
1150
1151 // Query if there is a relation between SSA1 and SS2 in block BB or a
1152 // dominator of BB
1153
1154 relation_kind
1155 dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1156 {
1157   relation_kind kind;
1158   unsigned v1 = SSA_NAME_VERSION (ssa1);
1159   unsigned v2 = SSA_NAME_VERSION (ssa2);
1160   if (v1 == v2)
1161     return EQ_EXPR;
1162
1163   // Check for equivalence first.  They must be in each equivalency set.
1164   const_bitmap equiv1 = equiv_set (ssa1, bb);
1165   const_bitmap equiv2 = equiv_set (ssa2, bb);
1166   if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1167     return EQ_EXPR;
1168
1169   // Initially look for a direct relationship and just return that.
1170   kind = find_relation_dom (bb, v1, v2);
1171   if (kind != VREL_NONE)
1172     return kind;
1173
1174   // Query using the equiovalence sets.
1175   kind = query_relation (bb, equiv1, equiv2);
1176   return kind;
1177 }
1178
1179 // Dump all the relations in block BB to file F.
1180
1181 void
1182 dom_oracle::dump (FILE *f, basic_block bb) const
1183 {
1184   equiv_oracle::dump (f,bb);
1185
1186   if (bb->index >= (int)m_relations.length ())
1187     return;
1188   if (!m_relations[bb->index].m_names)
1189     return;
1190
1191   relation_chain *ptr = m_relations[bb->index].m_head;
1192   for (; ptr; ptr = ptr->m_next)
1193     {
1194       fprintf (f, "Relational : ");
1195       ptr->dump (f);
1196       fprintf (f, "\n");
1197     }
1198 }
1199
1200 // Dump all the relations known to file F.
1201
1202 void
1203 dom_oracle::dump (FILE *f) const
1204 {
1205   fprintf (f, "Relation dump\n");
1206   for (unsigned i = 0; i < m_relations.length (); i++)
1207     if (BASIC_BLOCK_FOR_FN (cfun, i))
1208       {
1209         fprintf (f, "BB%d\n", i);
1210         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1211       }
1212 }
1213
1214 void
1215 relation_oracle::debug () const
1216 {
1217   dump (stderr);
1218 }
1219
1220 path_oracle::path_oracle (relation_oracle *oracle)
1221 {
1222   m_root = oracle;
1223   bitmap_obstack_initialize (&m_bitmaps);
1224   obstack_init (&m_chain_obstack);
1225
1226   // Initialize header records.
1227   m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1228   m_equiv.m_bb = NULL;
1229   m_equiv.m_next = NULL;
1230   m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1231   m_relations.m_head = NULL;
1232 }
1233
1234 path_oracle::~path_oracle ()
1235 {
1236   obstack_free (&m_chain_obstack, NULL);
1237   bitmap_obstack_release (&m_bitmaps);
1238 }
1239
1240 // Return the equiv set for SSA, and if there isn't one, check for equivs
1241 // starting in block BB.
1242
1243 const_bitmap
1244 path_oracle::equiv_set (tree ssa, basic_block bb)
1245 {
1246   // Check the list first.
1247   equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1248   if (ptr)
1249     return ptr->m_names;
1250
1251   // Otherwise defer to the root oracle.
1252   if (m_root)
1253     return m_root->equiv_set (ssa, bb);
1254
1255   // Allocate a throw away bitmap if there isn't a root oracle.
1256   bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1257   bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1258   return tmp;
1259 }
1260
1261 // Register an equivalence between SSA1 and SSA2 resolving unkowns from
1262 // block BB.
1263
1264 void
1265 path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1266 {
1267   const_bitmap equiv_1 = equiv_set (ssa1, bb);
1268   const_bitmap equiv_2 = equiv_set (ssa2, bb);
1269
1270   // Check if they are the same set, if so, we're done.
1271   if (bitmap_equal_p (equiv_1, equiv_2))
1272     return;
1273
1274   // Don't mess around, simply create a new record and insert it first.
1275   bitmap b = BITMAP_ALLOC (&m_bitmaps);
1276   bitmap_copy (b, equiv_1);
1277   bitmap_ior_into (b, equiv_2);
1278
1279   equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1280                                                     sizeof (equiv_chain));
1281   ptr->m_names = b;
1282   ptr->m_bb = NULL;
1283   ptr->m_next = m_equiv.m_next;
1284   m_equiv.m_next = ptr;
1285   bitmap_ior_into (m_equiv.m_names, b);
1286 }
1287
1288 // Register killing definition of an SSA_NAME.
1289
1290 void
1291 path_oracle::killing_def (tree ssa)
1292 {
1293   if (dump_file && (dump_flags & TDF_DETAILS))
1294     {
1295       fprintf (dump_file, " Registering killing_def (path_oracle) ");
1296       print_generic_expr (dump_file, ssa, TDF_SLIM);
1297       fprintf (dump_file, "\n");
1298     }
1299
1300   bitmap b = BITMAP_ALLOC (&m_bitmaps);
1301   bitmap_set_bit (b, SSA_NAME_VERSION (ssa));
1302   equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1303                                                     sizeof (equiv_chain));
1304   ptr->m_names = b;
1305   ptr->m_bb = NULL;
1306   ptr->m_next = m_equiv.m_next;
1307   m_equiv.m_next = ptr;
1308   bitmap_ior_into (m_equiv.m_names, b);
1309 }
1310
1311 // Register relation K between SSA1 and SSA2, resolving unknowns by
1312 // querying from BB.
1313
1314 void
1315 path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1316                                 tree ssa2)
1317 {
1318   if (dump_file && (dump_flags & TDF_DETAILS))
1319     {
1320       value_relation vr (k, ssa1, ssa2);
1321       fprintf (dump_file, " Registering value_relation (path_oracle) ");
1322       vr.dump (dump_file);
1323       fprintf (dump_file, " (bb%d)\n", bb->index);
1324     }
1325
1326   if (k == EQ_EXPR)
1327     {
1328       register_equiv (bb, ssa1, ssa2);
1329       return;
1330     }
1331
1332   relation_kind curr = query_relation (bb, ssa1, ssa2);
1333   if (curr != VREL_NONE)
1334     k = relation_intersect (curr, k);
1335
1336   bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1337   bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1338   relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1339                                                       sizeof (relation_chain));
1340   ptr->set_relation (k, ssa1, ssa2);
1341   ptr->m_next = m_relations.m_head;
1342   m_relations.m_head = ptr;
1343 }
1344
1345 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1346 // starting at block BB.
1347
1348 relation_kind
1349 path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1350 {
1351   if (bitmap_equal_p (b1, b2))
1352     return EQ_EXPR;
1353
1354   relation_kind k = m_relations.find_relation (b1, b2);
1355
1356   if (k == VREL_NONE && m_root)
1357     k = m_root->query_relation (bb, b1, b2);
1358
1359   return k;
1360 }
1361
1362 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1363 // starting at block BB.
1364
1365 relation_kind
1366 path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1367 {
1368   unsigned v1 = SSA_NAME_VERSION (ssa1);
1369   unsigned v2 = SSA_NAME_VERSION (ssa2);
1370
1371   if (v1 == v2)
1372     return EQ_EXPR;
1373
1374   const_bitmap equiv_1 = equiv_set (ssa1, bb);
1375   const_bitmap equiv_2 = equiv_set (ssa2, bb);
1376   if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1377     return EQ_EXPR;
1378
1379   return query_relation (bb, equiv_1, equiv_2);
1380 }
1381
1382 // Reset any relations registered on this path.
1383
1384 void
1385 path_oracle::reset_path ()
1386 {
1387   m_equiv.m_next = NULL;
1388   bitmap_clear (m_equiv.m_names);
1389   m_relations.m_head = NULL;
1390   bitmap_clear (m_relations.m_names);
1391 }
1392
1393 // Dump relation in basic block... Do nothing here.
1394
1395 void
1396 path_oracle::dump (FILE *, basic_block) const
1397 {
1398 }
1399
1400 // Dump the relations and equivalencies found in the path.
1401
1402 void
1403 path_oracle::dump (FILE *f) const
1404 {
1405   equiv_chain *ptr = m_equiv.m_next;
1406   for (; ptr; ptr = ptr->m_next)
1407     ptr->dump (f);
1408
1409   relation_chain *ptr2 = m_relations.m_head;
1410   for (; ptr2; ptr2 = ptr2->m_next)
1411     {
1412       fprintf (f, "Relational : ");
1413       ptr2->dump (f);
1414       fprintf (f, "\n");
1415     }
1416 }