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 R! 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 // -------------------------------------------------------------------------
 159
 160 // This class represents an equivalency set, and contains a link to the next
 161 // one in the list to be searched.
 162
 163 // The very first element in the m_equiv chain is actually just a summary
 164 // element in which the m_names bitmap is used to indicate that an ssa_name
 165 // has an equivalence set in this block.
 166 // This allows for much faster traversal of the DOM chain, as a search for
 167 // SSA_NAME simply requires walking the DOM chain until a block is found
 168 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
 169 // that block.   No previous blcoks need be searched.
 170
 171 class equiv_chain
 172 {
 173 public:
 174   bitmap m_names;               // ssa-names in equiv set.
 175   basic_block m_bb;             // Block this belongs to
 176   equiv_chain *m_next;          // Next in block list.
 177   void dump (FILE *f) const;    // Show names in this list.
 178 };
 179
 180
 181 // Dump the names in this equivalence set.
 182
 183 void
 184 equiv_chain::dump (FILE *f) const
 185 {
 186   bitmap_iterator bi;
 187   unsigned i;
 188
 189   if (!m_names)
 190     return;
 191   fprintf (f, "Equivalence set : [");
 192   unsigned c = 0;
 193   EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
 194     {
 195       if (ssa_name (i))
 196         {
 197           if (c++)
 198             fprintf (f, ", ");
 199           print_generic_expr (f, ssa_name (i), TDF_SLIM);
 200         }
 201     }
 202   fprintf (f, "]\n");
 203 }
 204
 205 // Instantiate an equivalency oracle.
 206
 207 equiv_oracle::equiv_oracle ()
 208 {
 209   bitmap_obstack_initialize (&m_bitmaps);
 210   m_equiv.create (0);
 211   m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 212   m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
 213   obstack_init (&m_chain_obstack);
 214 }
 215
 216 // Destruct an equivalency oracle.
 217
 218 equiv_oracle::~equiv_oracle ()
 219 {
 220   obstack_free (&m_chain_obstack, NULL);
 221   m_equiv.release ();
 222   bitmap_obstack_release (&m_bitmaps);
 223 }
 224
 225 // Find and return the equivalency set for SSA along the dominators of BB.
 226 // This is the external API.
 227
 228 const_bitmap
 229 equiv_oracle::equiv_set (tree ssa, basic_block bb) const
 230 {
 231   // Search the dominator tree for an equivalency.
 232   equiv_chain *equiv = find_equiv_dom (ssa, bb);
 233   if (equiv)
 234     return equiv->m_names;
 235
 236   return NULL;
 237 }
 238
 239
 240 // If SSA has an equivalence in block BB, find and return it.
 241 // Otherwise return NULL.
 242
 243 equiv_chain *
 244 equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
 245 {
 246   equiv_chain *ptr = NULL;
 247   if (bb >= (int)m_equiv.length ())
 248     return NULL;
 249
 250   // If there are equiv sets and SSA is in one in this block, find it.
 251   // Otherwise return NULL.
 252   if (m_equiv[bb] && bitmap_bit_p (m_equiv[bb]->m_names, ssa))
 253     {
 254       for (ptr = m_equiv[bb]->m_next; ptr; ptr = ptr->m_next)
 255         if (bitmap_bit_p (ptr->m_names, ssa))
 256           break;
 257     }
 258   return ptr;
 259 }
 260
 261 // Starting at block BB, walk the dominator chain looking for the nearest
 262 // equivalence set containing NAME.
 263
 264 equiv_chain *
 265 equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
 266 {
 267   unsigned v = SSA_NAME_VERSION (name);
 268   // Short circuit looking for names which have no equivalences.
 269   // Saves time looking for something which does not exist.
 270   if (!bitmap_bit_p (m_equiv_set, v))
 271     return NULL;
 272
 273   // NAME has at least once equivalence set, check to see if it has one along
 274   // the dominator tree.
 275   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 276     {
 277       equiv_chain *ptr = find_equiv_block (v, bb->index);
 278       if (ptr)
 279         return ptr;
 280     }
 281   return NULL;
 282 }
 283
 284 // Register equivalance between ssa_name V and set EQUIV in block BB,
 285
 286 bitmap
 287 equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
 288 {
 289   // V will have an equivalency now.
 290   bitmap_set_bit (m_equiv_set, v);
 291
 292   // If that equiv chain is in this block, simply use it.
 293   if (equiv->m_bb == bb)
 294     {
 295       bitmap_set_bit (equiv->m_names, v);
 296       bitmap_set_bit (m_equiv[bb->index]->m_names, v);
 297       return NULL;
 298     }
 299
 300   // Otherwise create an equivalence for this block which is a copy
 301   // of equiv, the add V to the set.
 302   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 303   bitmap_copy (b, equiv->m_names);
 304   bitmap_set_bit (b, v);
 305   return b;
 306 }
 307
 308 // Register equivalence between set equiv_1 and equiv_2 in block BB.
 309 // Return NULL if either name can be merged with the other.  Otherwise
 310 // return a pointer to the combined bitmap of names.  This allows the
 311 // caller to do any setup required for a new element.
 312
 313 bitmap
 314 equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
 315                               equiv_chain *equiv_2)
 316 {
 317   // If equiv_1 is alreayd in BB, use it as the combined set.
 318   if (equiv_1->m_bb == bb)
 319     {
 320       bitmap_ior_into  (equiv_1->m_names, equiv_2->m_names);
 321       // Its hard to delete from a single linked list, so
 322       // just clear the second one.
 323       if (equiv_2->m_bb == bb)
 324         bitmap_clear (equiv_2->m_names);
 325       else
 326         // Ensure equiv_2s names are in the summary for BB.
 327         bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
 328       return NULL;
 329     }
 330   // If equiv_2 is in BB, use it for the combined set.
 331   if (equiv_2->m_bb == bb)
 332     {
 333       bitmap_ior_into (equiv_2->m_names, equiv_1->m_names);
 334       // Add equiv_1 names into the summary.
 335       bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
 336       return NULL;
 337     }
 338
 339   // At this point, neither equivalence is from this block.
 340   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 341   bitmap_copy (b, equiv_1->m_names);
 342   bitmap_ior_into (b, equiv_2->m_names);
 343   return b;
 344 }
 345
 346
 347 // Register an equivalence between SSA1 and SSA2 in block BB.
 348 // The equivalence oracle maintains a vector of equivalencies indexed by basic
 349 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
 350 // a query is made as to what equivalences both names have already, and
 351 // any preexisting equivalences are merged to create a single equivalence
 352 // containing all the ssa_names in this basic block.
 353
 354 void
 355 equiv_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
 356 {
 357   unsigned v1 = SSA_NAME_VERSION (ssa1);
 358   unsigned v2 = SSA_NAME_VERSION (ssa2);
 359   equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
 360   equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
 361
 362   // Check if they are the same set
 363   if (equiv_1 && equiv_1 == equiv_2)
 364     return;
 365
 366   bitmap equiv_set;
 367
 368   // Case where we have 2 SSA_NAMEs that are not in any set.
 369   if (!equiv_1 && !equiv_2)
 370     {
 371       bitmap_set_bit (m_equiv_set, v1);
 372       bitmap_set_bit (m_equiv_set, v2);
 373
 374       equiv_set = BITMAP_ALLOC (&m_bitmaps);
 375       bitmap_set_bit (equiv_set, v1);
 376       bitmap_set_bit (equiv_set, v2);
 377     }
 378   else if (!equiv_1 && equiv_2)
 379     equiv_set = register_equiv (bb, v1, equiv_2);
 380   else if (equiv_1 && !equiv_2)
 381     equiv_set = register_equiv (bb, v2, equiv_1);
 382   else
 383     equiv_set = register_equiv (bb, equiv_1, equiv_2);
 384
 385   // A non-null return is a bitmap that is to be added to the current
 386   // block as a new equivalence.
 387   if (!equiv_set)
 388     return;
 389
 390   equiv_chain *ptr;
 391
 392   // Check if this is the first time a block has an equivalence added.
 393   // and create a header block. And set the summary for this block.
 394   if (!m_equiv[bb->index])
 395     {
 396       ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
 397                                            sizeof (equiv_chain));
 398       ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
 399       bitmap_copy (ptr->m_names, equiv_set);
 400       ptr->m_bb = bb;
 401       ptr->m_next = NULL;
 402       m_equiv[bb->index] = ptr;
 403     }
 404
 405   // Now create the element for this equiv set and initialize it.
 406   ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
 407   ptr->m_names = equiv_set;
 408   ptr->m_bb = bb;
 409   gcc_checking_assert (bb->index < (int)m_equiv.length ());
 410   ptr->m_next = m_equiv[bb->index]->m_next;
 411   m_equiv[bb->index]->m_next = ptr;
 412   bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
 413 }
 414
 415 // Make sure the BB vector is big enough and grow it if needed.
 416
 417 void
 418 equiv_oracle::limit_check (basic_block bb)
 419 {
 420   int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
 421   if (i >= (int)m_equiv.length ())
 422     m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 423 }
 424
 425 // Dump the equivalence sets in BB to file F.
 426
 427 void
 428 equiv_oracle::dump (FILE *f, basic_block bb) const
 429 {
 430   if (bb->index >= (int)m_equiv.length ())
 431     return;
 432   if (!m_equiv[bb->index])
 433     return;
 434
 435   equiv_chain *ptr = m_equiv[bb->index]->m_next;
 436   for (; ptr; ptr = ptr->m_next)
 437     ptr->dump (f);
 438 }
 439
 440 // Dump all equivalence sets known to the oracle.
 441
 442 void
 443 equiv_oracle::dump (FILE *f) const
 444 {
 445   fprintf (f, "Equivalency dump\n");
 446   for (unsigned i = 0; i < m_equiv.length (); i++)
 447     if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
 448       {
 449         fprintf (f, "BB%d\n", i);
 450         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
 451       }
 452 }
 453
 454
 455 // --------------------------------------------------------------------------
 456
 457 // The value-relation class is used to encapsulate the represention of an
 458 // individual relation between 2 ssa-names, and to facilitate operating on
 459 // the relation.
 460
 461 class value_relation
 462 {
 463 public:
 464   value_relation ();
 465   value_relation (relation_kind kind, tree n1, tree n2);
 466   void set_relation (relation_kind kind, tree n1, tree n2);
 467
 468   inline relation_kind kind () const { return related; }
 469   inline tree op1 () const { return name1; }
 470   inline tree op2 () const { return name2; }
 471
 472   bool union_ (value_relation &p);
 473   bool intersect (value_relation &p);
 474   void negate ();
 475   void swap ();
 476
 477   void dump (FILE *f) const;
 478 private:
 479   relation_kind related;
 480   tree name1, name2;
 481 };
 482
 483 // Set relation R between ssa_name N1 and N2.
 484
 485 inline void
 486 value_relation::set_relation (relation_kind r, tree n1, tree n2)
 487 {
 488   gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2));
 489   related = r;
 490   name1 = n1;
 491   name2 = n2;
 492 }
 493
 494 // Default constructor.
 495
 496 inline
 497 value_relation::value_relation ()
 498 {
 499   related = VREL_NONE;
 500   name1 = NULL_TREE;
 501   name2 = NULL_TREE;
 502 }
 503
 504 // Constructor for relation R between SSA version N1 nd N2.
 505
 506 inline
 507 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
 508 {
 509   set_relation (kind, n1, n2);
 510 }
 511
 512 // Negate the current relation.
 513
 514 void
 515 value_relation::negate ()
 516 {
 517   related = relation_negate (related);
 518 }
 519
 520 // Modify the relation as if the operands were being swapped.
 521
 522 void
 523 value_relation::swap ()
 524 {
 525   related = relation_swap (related);
 526 }
 527
 528 // Perform an intersection between 2 relations. *this &&= p.
 529
 530 bool
 531 value_relation::intersect (value_relation &p)
 532 {
 533   // Save previous value
 534   relation_kind old = related;
 535
 536   if (p.op1 () == op1 () && p.op2 () == op2 ())
 537     related = relation_intersect (kind (), p.kind ());
 538   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 539     related = relation_intersect (kind (), relation_swap (p.kind ()));
 540   else
 541     return false;
 542
 543   return old != related;
 544 }
 545
 546 // Perform a union between 2 relations. *this ||= p.
 547
 548 bool
 549 value_relation::union_ (value_relation &p)
 550 {
 551   // Save previous value
 552   relation_kind old = related;
 553
 554   if (p.op1 () == op1 () && p.op2 () == op2 ())
 555     related = relation_union (kind(), p.kind());
 556   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 557     related = relation_union (kind(), relation_swap (p.kind ()));
 558   else
 559     return false;
 560
 561   return old != related;
 562 }
 563
 564
 565 // Dump the relation to file F.
 566
 567 void
 568 value_relation::dump (FILE *f) const
 569 {
 570   if (!name1 || !name2)
 571     {
 572       fprintf (f, "uninitialized");
 573       return;
 574     }
 575   fputc ('(', f);
 576   print_generic_expr (f, op1 (), TDF_SLIM);
 577   print_relation (f, kind ());
 578   print_generic_expr (f, op2 (), TDF_SLIM);
 579   fputc(')', f);
 580 }
 581
 582 // This container is used to link relations in a chain.
 583
 584 class relation_chain : public value_relation
 585 {
 586 public:
 587   relation_chain *m_next;
 588 };
 589
 590 // ------------------------------------------------------------------------
 591
 592 // Instantiate a relation oracle.
 593
 594 relation_oracle::relation_oracle ()
 595 {
 596   m_relations.create (0);
 597   m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 598   m_relation_set = BITMAP_ALLOC (&m_bitmaps);
 599   m_tmp = BITMAP_ALLOC (&m_bitmaps);
 600 }
 601
 602 // Destruct a relation oracle.
 603
 604 relation_oracle::~relation_oracle ()
 605 {
 606   m_relations.release ();
 607 }
 608
 609 // Register relation K between ssa_name OP1 and OP2 on STMT.
 610
 611 void
 612 relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1,
 613                                     tree op2)
 614 {
 615   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 616   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 617   gcc_checking_assert (stmt && gimple_bb (stmt));
 618
 619   // Don't register lack of a relation.
 620   if (k == VREL_NONE)
 621     return;
 622
 623   if (dump_file && (dump_flags & TDF_DETAILS))
 624     {
 625       value_relation vr (k, op1, op2);
 626       fprintf (dump_file, " Registering value_relation ");
 627       vr.dump (dump_file);
 628       fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
 629       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 630     }
 631
 632   // This relation applies to the entire block, use STMT's block.
 633   // Equivalencies are handled by the equivalence oracle.
 634   if (k == EQ_EXPR)
 635     register_equiv (gimple_bb (stmt), op1, op2);
 636   else
 637     register_relation (gimple_bb (stmt), k, op1, op2);
 638 }
 639
 640 // Register relation K between ssa_name OP1 and OP2 on edge E.
 641
 642 void
 643 relation_oracle::register_relation (edge e, relation_kind k, tree op1,
 644                                     tree op2)
 645 {
 646   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 647   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 648
 649   // Do not register lack of relation, or blocks which have more than
 650   // edge E for a predecessor.
 651   if (k == VREL_NONE || !single_pred_p (e->dest))
 652     return;
 653
 654   if (dump_file && (dump_flags & TDF_DETAILS))
 655     {
 656       value_relation vr (k, op1, op2);
 657       fprintf (dump_file, " Registering value_relation ");
 658       vr.dump (dump_file);
 659       fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
 660     }
 661
 662   // Equivalencies are handled by the equivalence oracle.
 663   if (k == EQ_EXPR)
 664     register_equiv (e->dest, op1, op2);
 665   else
 666     register_relation (e->dest, k, op1, op2);
 667 }
 668
 669 // Register relation K between OP! and OP2 in block BB.
 670 // This creates the record and searches for existing records in the dominator
 671 // tree to merge with.
 672
 673 void
 674 relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
 675                                     tree op2)
 676 {
 677   gcc_checking_assert (k != VREL_NONE);
 678
 679   value_relation vr(k, op1, op2);
 680   int bbi = bb->index;
 681
 682   if (bbi >= (int)m_relations.length())
 683     m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 684
 685   // Summary bitmap indicating what ssa_names have relations in this BB.
 686   bitmap bm = m_relations[bbi].m_names;
 687   if (!bm)
 688     bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
 689   unsigned v1 = SSA_NAME_VERSION (op1);
 690   unsigned v2 = SSA_NAME_VERSION (op2);
 691
 692   relation_kind curr;
 693   relation_chain *ptr;
 694   curr = find_relation_block (bbi, v1, v2, &ptr);
 695   // There is an existing relation in this block, just intersect with it.
 696   if (curr != VREL_NONE)
 697     {
 698       if (dump_file && (dump_flags & TDF_DETAILS))
 699         {
 700           fprintf (dump_file, "    Intersecting with existing ");
 701           ptr->dump (dump_file);
 702         }
 703       // Check into whether we can simply replace the relation rather than
 704       // intersecting it.  THis may help with some optimistic iterative
 705       // updating algorithms.
 706       ptr->intersect (vr);
 707       if (dump_file && (dump_flags & TDF_DETAILS))
 708         {
 709           fprintf (dump_file, " to produce ");
 710           ptr->dump (dump_file);
 711           fprintf (dump_file, "\n");
 712         }
 713       return;
 714     }
 715
 716   // Check for an existing relation further up the DOM chain.
 717   // By including dominating relations, The first one found in any search
 718   // will be the aggregate of all the previous ones.
 719   curr = find_relation_dom (bb, v1, v2);
 720   if (curr != VREL_NONE)
 721     k = relation_intersect (curr, k);
 722
 723   bitmap_set_bit (bm, v1);
 724   bitmap_set_bit (bm, v2);
 725   bitmap_set_bit (m_relation_set, v1);
 726   bitmap_set_bit (m_relation_set, v2);
 727
 728   ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
 729                                           sizeof (relation_chain));
 730   ptr->set_relation (k, op1, op2);
 731   ptr->m_next = m_relations[bbi].m_head;
 732   m_relations[bbi].m_head = ptr;;
 733 }
 734
 735 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
 736 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
 737
 738 relation_kind
 739 relation_oracle::find_relation_block (unsigned bb, const_bitmap b1,
 740                                       const_bitmap b2)
 741 {
 742   const_bitmap bm;
 743   if (bb >= m_relations.length())
 744     return VREL_NONE;
 745
 746   bm = m_relations[bb].m_names;
 747   if (!bm)
 748     return VREL_NONE;
 749
 750   // If both b1 and b2 aren't referenced in thie block, cant be a relation
 751   if (!bitmap_intersect_p (bm, b1) || !bitmap_intersect_p (bm, b2))
 752     return VREL_NONE;
 753
 754   // Search for the fiorst relation that contains BOTH an element from B1
 755   // and B2, and return that relation.
 756   for (relation_chain *ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
 757     {
 758       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
 759       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
 760       if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
 761         return ptr->kind ();
 762       if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
 763         return relation_swap (ptr->kind ());
 764     }
 765
 766   return VREL_NONE;
 767 }
 768
 769 // Search the DOM tree for a relation between an element of B1 and B2, starting
 770 // with block BB.
 771
 772 relation_kind
 773 relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1,
 774                                     const_bitmap b2)
 775 {
 776   relation_kind r;
 777   // If either name does not occur in a relation anywhere, there isnt one.
 778   if (!bitmap_intersect_p (m_relation_set, b1)
 779       || !bitmap_intersect_p (m_relation_set, b2))
 780     return VREL_NONE;
 781
 782   // Search each block in the DOM tree checking.
 783   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 784     {
 785       r = find_relation_block (bb->index, b1, b2);
 786       if (r != VREL_NONE)
 787         return r;
 788     }
 789   return VREL_NONE;
 790
 791 }
 792
 793 // Find a relation in block BB between ssa version V1 and V2.  If a relation
 794 // is found, return a pointer to the chain object in OBJ.
 795
 796 relation_kind
 797 relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
 798                                      relation_chain **obj)
 799 {
 800   if (bb >= (int)m_relations.length())
 801     return VREL_NONE;
 802
 803   const_bitmap bm = m_relations[bb].m_names;
 804   if (!bm)
 805     return VREL_NONE;
 806
 807   // If both b1 and b2 aren't referenced in thie block, cant be a relation
 808   if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
 809     return VREL_NONE;
 810
 811   relation_chain *ptr;
 812   for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
 813     {
 814       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
 815       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
 816       if (v1 == op1 && v2 == op2)
 817         {
 818           if (obj)
 819             *obj = ptr;
 820           return ptr->kind ();
 821         }
 822       if (v1 == op2 && v2 == op1)
 823         {
 824           if (obj)
 825             *obj = ptr;
 826           return relation_swap (ptr->kind ());
 827         }
 828     }
 829
 830   return VREL_NONE;
 831 }
 832
 833 // Find a relation between SSA version V1 and V2 in the dominator tree
 834 // starting with block BB
 835
 836 relation_kind
 837 relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2)
 838 {
 839   relation_kind r;
 840   // IF either name does not occur in a relation anywhere, there isnt one.
 841   if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
 842     return VREL_NONE;
 843
 844   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 845     {
 846       r = find_relation_block (bb->index, v1, v2);
 847       if (r != VREL_NONE)
 848         return r;
 849     }
 850   return VREL_NONE;
 851
 852 }
 853
 854 // Query if there is a relation between SSA1 and SS2 in block BB or a
 855 // dominator of BB
 856
 857 relation_kind
 858 relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
 859 {
 860   relation_kind kind;
 861   unsigned v1 = SSA_NAME_VERSION (ssa1);
 862   unsigned v2 = SSA_NAME_VERSION (ssa2);
 863   if (v1 == v2)
 864     return EQ_EXPR;
 865
 866   // Check for equivalence first.
 867   const_bitmap equiv1 = equiv_set (ssa1, bb);
 868   if (equiv1 && bitmap_bit_p (equiv1, v2))
 869     return EQ_EXPR;
 870
 871   // Initially look for a direct relationship and just return that.
 872   kind = find_relation_dom (bb, v1, v2);
 873   if (kind != VREL_NONE)
 874     return kind;
 875
 876   // If v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either.
 877   // It is possible for out-of-order dominator processing to have an out of
 878   // sync set of equivalences..  Down the road, when we do full updates,
 879   // change this to an assert to ensure everything is in sync.
 880   const_bitmap equiv2 = equiv_set (ssa2, bb);
 881   if (equiv2 && bitmap_bit_p (equiv2, v1))
 882     return EQ_EXPR;
 883
 884   // If not equal, see if there is a relationship between equivalences.
 885   if (!equiv1 && !equiv2)
 886     kind = VREL_NONE;
 887   else if (!equiv1)
 888     {
 889       bitmap_clear (m_tmp);
 890       bitmap_set_bit (m_tmp, v1);
 891       kind = find_relation_dom (bb, m_tmp, equiv2);
 892     }
 893   else if (!equiv2)
 894     {
 895       bitmap_clear (m_tmp);
 896       bitmap_set_bit (m_tmp, v2);
 897       kind = find_relation_dom (bb, equiv1, m_tmp);
 898     }
 899   else
 900     kind = find_relation_dom (bb, equiv1, equiv2);
 901   return kind;
 902 }
 903
 904 // Dump all the relations in block BB to file F.
 905
 906 void
 907 relation_oracle::dump (FILE *f, basic_block bb) const
 908 {
 909   equiv_oracle::dump (f,bb);
 910
 911   if (bb->index >= (int)m_relations.length ())
 912     return;
 913   if (!m_relations[bb->index].m_names)
 914     return;
 915
 916   relation_chain *ptr = m_relations[bb->index].m_head;
 917   for (; ptr; ptr = ptr->m_next)
 918     {
 919       fprintf (f, "Relational : ");
 920       ptr->dump (f);
 921       fprintf (f, "\n");
 922     }
 923 }
 924
 925 // Dump all the relations known to file F.
 926
 927 void
 928 relation_oracle::dump (FILE *f) const
 929 {
 930   fprintf (f, "Relation dump\n");
 931   for (unsigned i = 0; i < m_relations.length (); i++)
 932     if (BASIC_BLOCK_FOR_FN (cfun, i))
 933       {
 934         fprintf (f, "BB%d\n", i);
 935         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
 936       }
 937 }