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 // This class represents an equivalency set, and contains a link to the next
 194 // one in the list to be searched.
 195
 196 // The very first element in the m_equiv chain is actually just a summary
 197 // element in which the m_names bitmap is used to indicate that an ssa_name
 198 // has an equivalence set in this block.
 199 // This allows for much faster traversal of the DOM chain, as a search for
 200 // SSA_NAME simply requires walking the DOM chain until a block is found
 201 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
 202 // that block.   No previous blcoks need be searched.
 203
 204 class equiv_chain
 205 {
 206 public:
 207   bitmap m_names;               // ssa-names in equiv set.
 208   basic_block m_bb;             // Block this belongs to
 209   equiv_chain *m_next;          // Next in block list.
 210   void dump (FILE *f) const;    // Show names in this list.
 211 };
 212
 213
 214 // Dump the names in this equivalence set.
 215
 216 void
 217 equiv_chain::dump (FILE *f) const
 218 {
 219   bitmap_iterator bi;
 220   unsigned i;
 221
 222   if (!m_names)
 223     return;
 224   fprintf (f, "Equivalence set : [");
 225   unsigned c = 0;
 226   EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
 227     {
 228       if (ssa_name (i))
 229         {
 230           if (c++)
 231             fprintf (f, ", ");
 232           print_generic_expr (f, ssa_name (i), TDF_SLIM);
 233         }
 234     }
 235   fprintf (f, "]\n");
 236 }
 237
 238 // Instantiate an equivalency oracle.
 239
 240 equiv_oracle::equiv_oracle ()
 241 {
 242   bitmap_obstack_initialize (&m_bitmaps);
 243   m_equiv.create (0);
 244   m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 245   m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
 246   obstack_init (&m_chain_obstack);
 247 }
 248
 249 // Destruct an equivalency oracle.
 250
 251 equiv_oracle::~equiv_oracle ()
 252 {
 253   obstack_free (&m_chain_obstack, NULL);
 254   m_equiv.release ();
 255   bitmap_obstack_release (&m_bitmaps);
 256 }
 257
 258 // Find and return the equivalency set for SSA along the dominators of BB.
 259 // This is the external API.
 260
 261 const_bitmap
 262 equiv_oracle::equiv_set (tree ssa, basic_block bb) const
 263 {
 264   // Search the dominator tree for an equivalency.
 265   equiv_chain *equiv = find_equiv_dom (ssa, bb);
 266   if (equiv)
 267     return equiv->m_names;
 268
 269   return NULL;
 270 }
 271
 272
 273 // If SSA has an equivalence in block BB, find and return it.
 274 // Otherwise return NULL.
 275
 276 equiv_chain *
 277 equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
 278 {
 279   equiv_chain *ptr = NULL;
 280   if (bb >= (int)m_equiv.length ())
 281     return NULL;
 282
 283   // If there are equiv sets and SSA is in one in this block, find it.
 284   // Otherwise return NULL.
 285   if (m_equiv[bb] && bitmap_bit_p (m_equiv[bb]->m_names, ssa))
 286     {
 287       for (ptr = m_equiv[bb]->m_next; ptr; ptr = ptr->m_next)
 288         if (bitmap_bit_p (ptr->m_names, ssa))
 289           break;
 290     }
 291   return ptr;
 292 }
 293
 294 // Starting at block BB, walk the dominator chain looking for the nearest
 295 // equivalence set containing NAME.
 296
 297 equiv_chain *
 298 equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
 299 {
 300   unsigned v = SSA_NAME_VERSION (name);
 301   // Short circuit looking for names which have no equivalences.
 302   // Saves time looking for something which does not exist.
 303   if (!bitmap_bit_p (m_equiv_set, v))
 304     return NULL;
 305
 306   // NAME has at least once equivalence set, check to see if it has one along
 307   // the dominator tree.
 308   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 309     {
 310       equiv_chain *ptr = find_equiv_block (v, bb->index);
 311       if (ptr)
 312         return ptr;
 313     }
 314   return NULL;
 315 }
 316
 317 // Register equivalance between ssa_name V and set EQUIV in block BB,
 318
 319 bitmap
 320 equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
 321 {
 322   // V will have an equivalency now.
 323   bitmap_set_bit (m_equiv_set, v);
 324
 325   // If that equiv chain is in this block, simply use it.
 326   if (equiv->m_bb == bb)
 327     {
 328       bitmap_set_bit (equiv->m_names, v);
 329       bitmap_set_bit (m_equiv[bb->index]->m_names, v);
 330       return NULL;
 331     }
 332
 333   // Otherwise create an equivalence for this block which is a copy
 334   // of equiv, the add V to the set.
 335   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 336   bitmap_copy (b, equiv->m_names);
 337   bitmap_set_bit (b, v);
 338   return b;
 339 }
 340
 341 // Register equivalence between set equiv_1 and equiv_2 in block BB.
 342 // Return NULL if either name can be merged with the other.  Otherwise
 343 // return a pointer to the combined bitmap of names.  This allows the
 344 // caller to do any setup required for a new element.
 345
 346 bitmap
 347 equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
 348                               equiv_chain *equiv_2)
 349 {
 350   // If equiv_1 is alreayd in BB, use it as the combined set.
 351   if (equiv_1->m_bb == bb)
 352     {
 353       bitmap_ior_into  (equiv_1->m_names, equiv_2->m_names);
 354       // Its hard to delete from a single linked list, so
 355       // just clear the second one.
 356       if (equiv_2->m_bb == bb)
 357         bitmap_clear (equiv_2->m_names);
 358       else
 359         // Ensure equiv_2s names are in the summary for BB.
 360         bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
 361       return NULL;
 362     }
 363   // If equiv_2 is in BB, use it for the combined set.
 364   if (equiv_2->m_bb == bb)
 365     {
 366       bitmap_ior_into (equiv_2->m_names, equiv_1->m_names);
 367       // Add equiv_1 names into the summary.
 368       bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
 369       return NULL;
 370     }
 371
 372   // At this point, neither equivalence is from this block.
 373   bitmap b = BITMAP_ALLOC (&m_bitmaps);
 374   bitmap_copy (b, equiv_1->m_names);
 375   bitmap_ior_into (b, equiv_2->m_names);
 376   return b;
 377 }
 378
 379
 380 // Register an equivalence between SSA1 and SSA2 in block BB.
 381 // The equivalence oracle maintains a vector of equivalencies indexed by basic
 382 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
 383 // a query is made as to what equivalences both names have already, and
 384 // any preexisting equivalences are merged to create a single equivalence
 385 // containing all the ssa_names in this basic block.
 386
 387 void
 388 equiv_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
 389 {
 390   unsigned v1 = SSA_NAME_VERSION (ssa1);
 391   unsigned v2 = SSA_NAME_VERSION (ssa2);
 392   equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
 393   equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
 394
 395   // Check if they are the same set
 396   if (equiv_1 && equiv_1 == equiv_2)
 397     return;
 398
 399   bitmap equiv_set;
 400
 401   // Case where we have 2 SSA_NAMEs that are not in any set.
 402   if (!equiv_1 && !equiv_2)
 403     {
 404       bitmap_set_bit (m_equiv_set, v1);
 405       bitmap_set_bit (m_equiv_set, v2);
 406
 407       equiv_set = BITMAP_ALLOC (&m_bitmaps);
 408       bitmap_set_bit (equiv_set, v1);
 409       bitmap_set_bit (equiv_set, v2);
 410     }
 411   else if (!equiv_1 && equiv_2)
 412     equiv_set = register_equiv (bb, v1, equiv_2);
 413   else if (equiv_1 && !equiv_2)
 414     equiv_set = register_equiv (bb, v2, equiv_1);
 415   else
 416     equiv_set = register_equiv (bb, equiv_1, equiv_2);
 417
 418   // A non-null return is a bitmap that is to be added to the current
 419   // block as a new equivalence.
 420   if (!equiv_set)
 421     return;
 422
 423   equiv_chain *ptr;
 424
 425   // Check if this is the first time a block has an equivalence added.
 426   // and create a header block. And set the summary for this block.
 427   if (!m_equiv[bb->index])
 428     {
 429       ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
 430                                            sizeof (equiv_chain));
 431       ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
 432       bitmap_copy (ptr->m_names, equiv_set);
 433       ptr->m_bb = bb;
 434       ptr->m_next = NULL;
 435       m_equiv[bb->index] = ptr;
 436     }
 437
 438   // Now create the element for this equiv set and initialize it.
 439   ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
 440   ptr->m_names = equiv_set;
 441   ptr->m_bb = bb;
 442   gcc_checking_assert (bb->index < (int)m_equiv.length ());
 443   ptr->m_next = m_equiv[bb->index]->m_next;
 444   m_equiv[bb->index]->m_next = ptr;
 445   bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
 446 }
 447
 448 // Make sure the BB vector is big enough and grow it if needed.
 449
 450 void
 451 equiv_oracle::limit_check (basic_block bb)
 452 {
 453   int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
 454   if (i >= (int)m_equiv.length ())
 455     m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 456 }
 457
 458 // Dump the equivalence sets in BB to file F.
 459
 460 void
 461 equiv_oracle::dump (FILE *f, basic_block bb) const
 462 {
 463   if (bb->index >= (int)m_equiv.length ())
 464     return;
 465   if (!m_equiv[bb->index])
 466     return;
 467
 468   equiv_chain *ptr = m_equiv[bb->index]->m_next;
 469   for (; ptr; ptr = ptr->m_next)
 470     ptr->dump (f);
 471 }
 472
 473 // Dump all equivalence sets known to the oracle.
 474
 475 void
 476 equiv_oracle::dump (FILE *f) const
 477 {
 478   fprintf (f, "Equivalency dump\n");
 479   for (unsigned i = 0; i < m_equiv.length (); i++)
 480     if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
 481       {
 482         fprintf (f, "BB%d\n", i);
 483         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
 484       }
 485 }
 486
 487
 488 // --------------------------------------------------------------------------
 489
 490 // The value-relation class is used to encapsulate the represention of an
 491 // individual relation between 2 ssa-names, and to facilitate operating on
 492 // the relation.
 493
 494 class value_relation
 495 {
 496 public:
 497   value_relation ();
 498   value_relation (relation_kind kind, tree n1, tree n2);
 499   void set_relation (relation_kind kind, tree n1, tree n2);
 500
 501   inline relation_kind kind () const { return related; }
 502   inline tree op1 () const { return name1; }
 503   inline tree op2 () const { return name2; }
 504
 505   bool union_ (value_relation &p);
 506   bool intersect (value_relation &p);
 507   void negate ();
 508   bool apply_transitive (const value_relation &rel);
 509
 510   void dump (FILE *f) const;
 511 private:
 512   relation_kind related;
 513   tree name1, name2;
 514 };
 515
 516 // Set relation R between ssa_name N1 and N2.
 517
 518 inline void
 519 value_relation::set_relation (relation_kind r, tree n1, tree n2)
 520 {
 521   gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2));
 522   related = r;
 523   name1 = n1;
 524   name2 = n2;
 525 }
 526
 527 // Default constructor.
 528
 529 inline
 530 value_relation::value_relation ()
 531 {
 532   related = VREL_NONE;
 533   name1 = NULL_TREE;
 534   name2 = NULL_TREE;
 535 }
 536
 537 // Constructor for relation R between SSA version N1 nd N2.
 538
 539 inline
 540 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
 541 {
 542   set_relation (kind, n1, n2);
 543 }
 544
 545 // Negate the current relation.
 546
 547 void
 548 value_relation::negate ()
 549 {
 550   related = relation_negate (related);
 551 }
 552
 553 // Perform an intersection between 2 relations. *this &&= p.
 554
 555 bool
 556 value_relation::intersect (value_relation &p)
 557 {
 558   // Save previous value
 559   relation_kind old = related;
 560
 561   if (p.op1 () == op1 () && p.op2 () == op2 ())
 562     related = relation_intersect (kind (), p.kind ());
 563   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 564     related = relation_intersect (kind (), relation_swap (p.kind ()));
 565   else
 566     return false;
 567
 568   return old != related;
 569 }
 570
 571 // Perform a union between 2 relations. *this ||= p.
 572
 573 bool
 574 value_relation::union_ (value_relation &p)
 575 {
 576   // Save previous value
 577   relation_kind old = related;
 578
 579   if (p.op1 () == op1 () && p.op2 () == op2 ())
 580     related = relation_union (kind(), p.kind());
 581   else if (p.op2 () == op1 () && p.op1 () == op2 ())
 582     related = relation_union (kind(), relation_swap (p.kind ()));
 583   else
 584     return false;
 585
 586   return old != related;
 587 }
 588
 589 // Identify and apply any transitive relations between REL
 590 // and THIS.  Return true if there was a transformation.
 591
 592 bool
 593 value_relation::apply_transitive (const value_relation &rel)
 594 {
 595   relation_kind k = VREL_NONE;
 596
 597   // Idenity any common operand, and notrmalize the relations to
 598   // the form : A < B  B < C produces A < C
 599   if (rel.op1 () == name2)
 600     {
 601       // A < B   B < C
 602       if (rel.op2 () == name1)
 603         return false;
 604       k = relation_transitive (kind (), rel.kind ());
 605       if (k != VREL_NONE)
 606         {
 607           related = k;
 608           name2 = rel.op2 ();
 609           return true;
 610         }
 611     }
 612   else if (rel.op1 () == name1)
 613     {
 614       // B > A   B < C
 615       if (rel.op2 () == name2)
 616         return false;
 617       k = relation_transitive (relation_swap (kind ()), rel.kind ());
 618       if (k != VREL_NONE)
 619         {
 620           related = k;
 621           name1 = name2;
 622           name2 = rel.op2 ();
 623           return true;
 624         }
 625     }
 626   else if (rel.op2 () == name2)
 627     {
 628        // A < B   C > B
 629        if (rel.op1 () == name1)
 630          return false;
 631       k = relation_transitive (kind (), relation_swap (rel.kind ()));
 632       if (k != VREL_NONE)
 633         {
 634           related = k;
 635           name2 = rel.op1 ();
 636           return true;
 637         }
 638     }
 639   else if (rel.op2 () == name1)
 640     {
 641       // B > A  C > B
 642       if (rel.op1 () == name2)
 643         return false;
 644       k = relation_transitive (relation_swap (kind ()),
 645                                relation_swap (rel.kind ()));
 646       if (k != VREL_NONE)
 647         {
 648           related = k;
 649           name1 = name2;
 650           name2 = rel.op1 ();
 651           return true;
 652         }
 653     }
 654   return false;
 655 }
 656
 657 // Dump the relation to file F.
 658
 659 void
 660 value_relation::dump (FILE *f) const
 661 {
 662   if (!name1 || !name2)
 663     {
 664       fprintf (f, "uninitialized");
 665       return;
 666     }
 667   fputc ('(', f);
 668   print_generic_expr (f, op1 (), TDF_SLIM);
 669   print_relation (f, kind ());
 670   print_generic_expr (f, op2 (), TDF_SLIM);
 671   fputc(')', f);
 672 }
 673
 674 // This container is used to link relations in a chain.
 675
 676 class relation_chain : public value_relation
 677 {
 678 public:
 679   relation_chain *m_next;
 680 };
 681
 682 // ------------------------------------------------------------------------
 683
 684 // Instantiate a relation oracle.
 685
 686 relation_oracle::relation_oracle ()
 687 {
 688   m_relations.create (0);
 689   m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 690   m_relation_set = BITMAP_ALLOC (&m_bitmaps);
 691   m_tmp = BITMAP_ALLOC (&m_bitmaps);
 692   m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
 693 }
 694
 695 // Destruct a relation oracle.
 696
 697 relation_oracle::~relation_oracle ()
 698 {
 699   m_relations.release ();
 700 }
 701
 702 // Register relation K between ssa_name OP1 and OP2 on STMT.
 703
 704 void
 705 relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1,
 706                                     tree op2)
 707 {
 708   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 709   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 710   gcc_checking_assert (stmt && gimple_bb (stmt));
 711
 712   // Don't register lack of a relation.
 713   if (k == VREL_NONE)
 714     return;
 715
 716   if (dump_file && (dump_flags & TDF_DETAILS))
 717     {
 718       value_relation vr (k, op1, op2);
 719       fprintf (dump_file, " Registering value_relation ");
 720       vr.dump (dump_file);
 721       fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
 722       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 723     }
 724
 725   // This relation applies to the entire block, use STMT's block.
 726   // Equivalencies are handled by the equivalence oracle.
 727   if (k == EQ_EXPR)
 728     register_equiv (gimple_bb (stmt), op1, op2);
 729   else
 730     register_relation (gimple_bb (stmt), k, op1, op2);
 731 }
 732
 733 // Register relation K between ssa_name OP1 and OP2 on edge E.
 734
 735 void
 736 relation_oracle::register_relation (edge e, relation_kind k, tree op1,
 737                                     tree op2)
 738 {
 739   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
 740   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
 741
 742   // Do not register lack of relation, or blocks which have more than
 743   // edge E for a predecessor.
 744   if (k == VREL_NONE || !single_pred_p (e->dest))
 745     return;
 746
 747   if (dump_file && (dump_flags & TDF_DETAILS))
 748     {
 749       value_relation vr (k, op1, op2);
 750       fprintf (dump_file, " Registering value_relation ");
 751       vr.dump (dump_file);
 752       fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
 753     }
 754
 755   // Equivalencies are handled by the equivalence oracle.
 756   if (k == EQ_EXPR)
 757     register_equiv (e->dest, op1, op2);
 758   else
 759     register_relation (e->dest, k, op1, op2);
 760 }
 761
 762 // Register relation K between OP! and OP2 in block BB.
 763 // This creates the record and searches for existing records in the dominator
 764 // tree to merge with.
 765 // TRANSITIVE_P is true if this is being registered as a transitive operation,
 766 // and should not try to register further transitives.
 767
 768 void
 769 relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
 770                                     tree op2, bool transitive_p)
 771 {
 772   gcc_checking_assert (k != VREL_NONE);
 773
 774   value_relation vr(k, op1, op2);
 775   int bbi = bb->index;
 776
 777   if (bbi >= (int)m_relations.length())
 778     m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 779
 780   // Summary bitmap indicating what ssa_names have relations in this BB.
 781   bitmap bm = m_relations[bbi].m_names;
 782   if (!bm)
 783     bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
 784   unsigned v1 = SSA_NAME_VERSION (op1);
 785   unsigned v2 = SSA_NAME_VERSION (op2);
 786
 787   relation_kind curr;
 788   relation_chain *ptr;
 789   curr = find_relation_block (bbi, v1, v2, &ptr);
 790   // There is an existing relation in this block, just intersect with it.
 791   if (curr != VREL_NONE)
 792     {
 793       if (dump_file && (dump_flags & TDF_DETAILS))
 794         {
 795           fprintf (dump_file, "    Intersecting with existing ");
 796           ptr->dump (dump_file);
 797         }
 798       // Check into whether we can simply replace the relation rather than
 799       // intersecting it.  THis may help with some optimistic iterative
 800       // updating algorithms.
 801       ptr->intersect (vr);
 802       if (dump_file && (dump_flags & TDF_DETAILS))
 803         {
 804           fprintf (dump_file, " to produce ");
 805           ptr->dump (dump_file);
 806           fprintf (dump_file, "\n");
 807         }
 808     }
 809   else
 810     {
 811       // Check for an existing relation further up the DOM chain.
 812       // By including dominating relations, The first one found in any search
 813       // will be the aggregate of all the previous ones.
 814       curr = find_relation_dom (bb, v1, v2);
 815       if (curr != VREL_NONE)
 816         k = relation_intersect (curr, k);
 817
 818       bitmap_set_bit (bm, v1);
 819       bitmap_set_bit (bm, v2);
 820       bitmap_set_bit (m_relation_set, v1);
 821       bitmap_set_bit (m_relation_set, v2);
 822
 823       ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
 824                                               sizeof (relation_chain));
 825       ptr->set_relation (k, op1, op2);
 826       ptr->m_next = m_relations[bbi].m_head;
 827       m_relations[bbi].m_head = ptr;;
 828     }
 829
 830   if (!transitive_p)
 831     register_transitives (bb, *ptr);
 832 }
 833
 834 // Starting at ROOT_BB search the DOM tree  looking for relations which
 835 // may produce transitive relations to RELATION.  EQUIV1 and EQUIV2 are
 836 // bitmaps for op1/op2 and any of their equivalences that should also be
 837 // considered.
 838
 839 void
 840 relation_oracle::register_transitives (basic_block root_bb,
 841                                        const value_relation &relation,
 842                                        const_bitmap equiv1,
 843                                        const_bitmap equiv2)
 844 {
 845   basic_block bb;
 846   for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 847     {
 848       int bbi = bb->index;
 849       if (bbi >= (int)m_relations.length())
 850         continue;
 851       const_bitmap bm = m_relations[bbi].m_names;
 852       if (!bm)
 853         continue;
 854       if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
 855         continue;
 856       // At least one of the 2 ops has a relation in this block.
 857       relation_chain *ptr;
 858       for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
 859         {
 860           // In the presence of an equivalence, 2 operands may do not
 861           // naturally match. ie  with equivalence a_2 == b_3
 862           // given c_1 < a_2 && b_3 < d_4
 863           // convert the second relation (b_3 < d_4) to match any
 864           // equivalences to found in the first relation.
 865           // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
 866           // transitive operation:  c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
 867
 868           tree r1, r2;
 869           tree p1 = ptr->op1 ();
 870           tree p2 = ptr->op2 ();
 871           // Find which equivalence is in the first operand.
 872           if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
 873             r1 = p1;
 874           else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
 875             r1 = p2;
 876           else
 877             r1 = NULL_TREE;
 878
 879           // Find which equivalence is in the second operand.
 880           if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
 881             r2 = p1;
 882           else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
 883             r2 = p2;
 884           else
 885             r2 = NULL_TREE;
 886
 887           // Ignore if both NULL (not relevant relation) or the same,
 888           if (r1 == r2)
 889             continue;
 890
 891           // Any operand not an equivalence, just take the real operand.
 892           if (!r1)
 893             r1 = relation.op1 ();
 894           if (!r2)
 895             r2 = relation.op2 ();
 896
 897           value_relation nr (relation.kind (), r1, r2);
 898           if (nr.apply_transitive (*ptr))
 899             {
 900               register_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 (),
 901                                  true);
 902               if (dump_file && (dump_flags & TDF_DETAILS))
 903                 {
 904                   fprintf (dump_file, "   Registering transitive relation ");
 905                   nr.dump (dump_file);
 906                   fputc ('\n', dump_file);
 907                 }
 908             }
 909
 910         }
 911     }
 912 }
 913
 914 // Find adn register any transitive relations implied by RELATION occuring
 915 // in block BB.
 916
 917 void
 918 relation_oracle::register_transitives (basic_block bb,
 919                                        const value_relation &relation)
 920 {
 921   // Only apply transitives to certain kinds of operations.
 922   switch (relation.kind ())
 923     {
 924       case LE_EXPR:
 925       case LT_EXPR:
 926       case GT_EXPR:
 927       case GE_EXPR:
 928         break;
 929       default:
 930         return;
 931     }
 932
 933   // Set up the bitmaps for op1 and op2, and if there are no equivalencies,
 934   // set just op1 or op2 in their own bitmap.
 935   const_bitmap equiv1 = equiv_set (relation.op1 (), bb);
 936   const_bitmap equiv2 = equiv_set (relation.op2 (), bb);
 937   if (equiv1)
 938     {
 939       if (equiv2)
 940         register_transitives (bb, relation, equiv1, equiv2);
 941       else
 942         {
 943           bitmap_clear (m_tmp);
 944           bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op2 ()));
 945           register_transitives (bb, relation, equiv1, m_tmp);
 946         }
 947     }
 948   else if (equiv2)
 949     {
 950       bitmap_clear (m_tmp);
 951       bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ()));
 952       register_transitives (bb, relation, m_tmp, equiv2);
 953     }
 954   else
 955     {
 956       bitmap_clear (m_tmp);
 957       bitmap_clear (m_tmp2);
 958       bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ()));
 959       bitmap_set_bit (m_tmp2, SSA_NAME_VERSION (relation.op2 ()));
 960       register_transitives (bb, relation, m_tmp, m_tmp2);
 961     }
 962 }
 963
 964 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
 965 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
 966
 967 relation_kind
 968 relation_oracle::find_relation_block (unsigned bb, const_bitmap b1,
 969                                       const_bitmap b2)
 970 {
 971   const_bitmap bm;
 972   if (bb >= m_relations.length())
 973     return VREL_NONE;
 974
 975   bm = m_relations[bb].m_names;
 976   if (!bm)
 977     return VREL_NONE;
 978
 979   // If both b1 and b2 aren't referenced in thie block, cant be a relation
 980   if (!bitmap_intersect_p (bm, b1) || !bitmap_intersect_p (bm, b2))
 981     return VREL_NONE;
 982
 983   // Search for the fiorst relation that contains BOTH an element from B1
 984   // and B2, and return that relation.
 985   for (relation_chain *ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
 986     {
 987       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
 988       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
 989       if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
 990         return ptr->kind ();
 991       if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
 992         return relation_swap (ptr->kind ());
 993     }
 994
 995   return VREL_NONE;
 996 }
 997
 998 // Search the DOM tree for a relation between an element of B1 and B2, starting
 999 // with block BB.
1000
1001 relation_kind
1002 relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1,
1003                                     const_bitmap b2)
1004 {
1005   relation_kind r;
1006   // If either name does not occur in a relation anywhere, there isnt one.
1007   if (!bitmap_intersect_p (m_relation_set, b1)
1008       || !bitmap_intersect_p (m_relation_set, b2))
1009     return VREL_NONE;
1010
1011   // Search each block in the DOM tree checking.
1012   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1013     {
1014       r = find_relation_block (bb->index, b1, b2);
1015       if (r != VREL_NONE)
1016         return r;
1017     }
1018   return VREL_NONE;
1019
1020 }
1021
1022 // Find a relation in block BB between ssa version V1 and V2.  If a relation
1023 // is found, return a pointer to the chain object in OBJ.
1024
1025 relation_kind
1026 relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1027                                      relation_chain **obj)
1028 {
1029   if (bb >= (int)m_relations.length())
1030     return VREL_NONE;
1031
1032   const_bitmap bm = m_relations[bb].m_names;
1033   if (!bm)
1034     return VREL_NONE;
1035
1036   // If both b1 and b2 aren't referenced in thie block, cant be a relation
1037   if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1038     return VREL_NONE;
1039
1040   relation_chain *ptr;
1041   for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1042     {
1043       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1044       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1045       if (v1 == op1 && v2 == op2)
1046         {
1047           if (obj)
1048             *obj = ptr;
1049           return ptr->kind ();
1050         }
1051       if (v1 == op2 && v2 == op1)
1052         {
1053           if (obj)
1054             *obj = ptr;
1055           return relation_swap (ptr->kind ());
1056         }
1057     }
1058
1059   return VREL_NONE;
1060 }
1061
1062 // Find a relation between SSA version V1 and V2 in the dominator tree
1063 // starting with block BB
1064
1065 relation_kind
1066 relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2)
1067 {
1068   relation_kind r;
1069   // IF either name does not occur in a relation anywhere, there isnt one.
1070   if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1071     return VREL_NONE;
1072
1073   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1074     {
1075       r = find_relation_block (bb->index, v1, v2);
1076       if (r != VREL_NONE)
1077         return r;
1078     }
1079   return VREL_NONE;
1080
1081 }
1082
1083 // Query if there is a relation between SSA1 and SS2 in block BB or a
1084 // dominator of BB
1085
1086 relation_kind
1087 relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1088 {
1089   relation_kind kind;
1090   unsigned v1 = SSA_NAME_VERSION (ssa1);
1091   unsigned v2 = SSA_NAME_VERSION (ssa2);
1092   if (v1 == v2)
1093     return EQ_EXPR;
1094
1095   // Check for equivalence first.
1096   const_bitmap equiv1 = equiv_set (ssa1, bb);
1097   if (equiv1 && bitmap_bit_p (equiv1, v2))
1098     return EQ_EXPR;
1099
1100   // Initially look for a direct relationship and just return that.
1101   kind = find_relation_dom (bb, v1, v2);
1102   if (kind != VREL_NONE)
1103     return kind;
1104
1105   // If v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either.
1106   // It is possible for out-of-order dominator processing to have an out of
1107   // sync set of equivalences..  Down the road, when we do full updates,
1108   // change this to an assert to ensure everything is in sync.
1109   const_bitmap equiv2 = equiv_set (ssa2, bb);
1110   if (equiv2 && bitmap_bit_p (equiv2, v1))
1111     return EQ_EXPR;
1112
1113   // If not equal, see if there is a relationship between equivalences.
1114   if (!equiv1 && !equiv2)
1115     kind = VREL_NONE;
1116   else if (!equiv1)
1117     {
1118       bitmap_clear (m_tmp);
1119       bitmap_set_bit (m_tmp, v1);
1120       kind = find_relation_dom (bb, m_tmp, equiv2);
1121     }
1122   else if (!equiv2)
1123     {
1124       bitmap_clear (m_tmp);
1125       bitmap_set_bit (m_tmp, v2);
1126       kind = find_relation_dom (bb, equiv1, m_tmp);
1127     }
1128   else
1129     kind = find_relation_dom (bb, equiv1, equiv2);
1130   return kind;
1131 }
1132
1133 // Dump all the relations in block BB to file F.
1134
1135 void
1136 relation_oracle::dump (FILE *f, basic_block bb) const
1137 {
1138   equiv_oracle::dump (f,bb);
1139
1140   if (bb->index >= (int)m_relations.length ())
1141     return;
1142   if (!m_relations[bb->index].m_names)
1143     return;
1144
1145   relation_chain *ptr = m_relations[bb->index].m_head;
1146   for (; ptr; ptr = ptr->m_next)
1147     {
1148       fprintf (f, "Relational : ");
1149       ptr->dump (f);
1150       fprintf (f, "\n");
1151     }
1152 }
1153
1154 // Dump all the relations known to file F.
1155
1156 void
1157 relation_oracle::dump (FILE *f) const
1158 {
1159   fprintf (f, "Relation dump\n");
1160   for (unsigned i = 0; i < m_relations.length (); i++)
1161     if (BASIC_BLOCK_FOR_FN (cfun, i))
1162       {
1163         fprintf (f, "BB%d\n", i);
1164         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1165       }
1166 }