| /* Header file for the value range relational processing. |
| Copyright (C) 2020-2022 Free Software Foundation, Inc. |
| Contributed by Andrew MacLeod <amacleod@redhat.com> |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify it under |
| the terms of the GNU General Public License as published by the Free |
| Software Foundation; either version 3, or (at your option) any later |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "tree.h" |
| #include "gimple.h" |
| #include "ssa.h" |
| |
| #include "gimple-range.h" |
| #include "tree-pretty-print.h" |
| #include "gimple-pretty-print.h" |
| #include "alloc-pool.h" |
| #include "dominance.h" |
| |
| // These VREL codes are arranged such that VREL_NONE is the first |
| // code, and all the rest are contiguous up to and including VREL_LAST. |
| |
| #define VREL_FIRST VREL_NONE |
| #define VREL_LAST NE_EXPR |
| #define VREL_COUNT (VREL_LAST - VREL_FIRST + 1) |
| |
| // vrel_range_assert will either assert that the tree code passed is valid, |
| // or mark invalid codes as unreachable to help with table optimation. |
| #if CHECKING_P |
| #define vrel_range_assert(c) \ |
| gcc_checking_assert ((c) >= VREL_FIRST && (c) <= VREL_LAST) |
| #else |
| #define vrel_range_assert(c) \ |
| if ((c) < VREL_FIRST || (c) > VREL_LAST) \ |
| gcc_unreachable (); |
| #endif |
| |
| static const char *kind_string[VREL_COUNT] = |
| { "none", "<", "<=", ">", ">=", "empty", "==", "!=" }; |
| |
| // Print a relation_kind REL to file F. |
| |
| void |
| print_relation (FILE *f, relation_kind rel) |
| { |
| vrel_range_assert (rel); |
| fprintf (f, " %s ", kind_string[rel - VREL_FIRST]); |
| } |
| |
| // This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2). |
| relation_kind rr_negate_table[VREL_COUNT] = { |
| // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR |
| VREL_NONE, GE_EXPR, GT_EXPR, LE_EXPR, LT_EXPR, VREL_EMPTY, NE_EXPR, EQ_EXPR }; |
| |
| // Negate the relation, as in logical negation. |
| |
| relation_kind |
| relation_negate (relation_kind r) |
| { |
| vrel_range_assert (r); |
| return rr_negate_table [r - VREL_FIRST]; |
| } |
| |
| // This table is used to swap the operands. op1 REL op2 -> op2 REL op1. |
| relation_kind rr_swap_table[VREL_COUNT] = { |
| // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR |
| VREL_NONE, GT_EXPR, GE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR }; |
| |
| // Return the relation as if the operands were swapped. |
| |
| relation_kind |
| relation_swap (relation_kind r) |
| { |
| vrel_range_assert (r); |
| return rr_swap_table [r - VREL_FIRST]; |
| } |
| |
| // This table is used to perform an intersection between 2 relations. |
| |
| relation_kind rr_intersect_table[VREL_COUNT][VREL_COUNT] = { |
| // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR |
| // VREL_NONE |
| { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR }, |
| // LT_EXPR |
| { LT_EXPR, LT_EXPR, LT_EXPR, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, LT_EXPR }, |
| // LE_EXPR |
| { LE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, LT_EXPR }, |
| // GT_EXPR |
| { GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR }, |
| // GE_EXPR |
| { GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR }, |
| // VREL_EMPTY |
| { VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY }, |
| // EQ_EXPR |
| { EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY }, |
| // NE_EXPR |
| { NE_EXPR, LT_EXPR, LT_EXPR, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, NE_EXPR } }; |
| |
| |
| // Intersect relation R1 with relation R2 and return the resulting relation. |
| |
| relation_kind |
| relation_intersect (relation_kind r1, relation_kind r2) |
| { |
| vrel_range_assert (r1); |
| vrel_range_assert (r2); |
| return rr_intersect_table[r1 - VREL_FIRST][r2 - VREL_FIRST]; |
| } |
| |
| |
| // This table is used to perform a union between 2 relations. |
| |
| relation_kind rr_union_table[VREL_COUNT][VREL_COUNT] = { |
| // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR |
| // VREL_NONE |
| { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE }, |
| // LT_EXPR |
| { VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR, VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR }, |
| // LE_EXPR |
| { VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE }, |
| // GT_EXPR |
| { VREL_NONE, NE_EXPR, VREL_NONE, GT_EXPR, GE_EXPR, GT_EXPR, GE_EXPR, NE_EXPR }, |
| // GE_EXPR |
| { VREL_NONE, VREL_NONE, VREL_NONE, GE_EXPR, GE_EXPR, GE_EXPR, GE_EXPR, VREL_NONE }, |
| // VREL_EMPTY |
| { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR }, |
| // EQ_EXPR |
| { VREL_NONE, LE_EXPR, LE_EXPR, GE_EXPR, GE_EXPR, EQ_EXPR, EQ_EXPR, VREL_NONE }, |
| // NE_EXPR |
| { VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR } }; |
| |
| // Union relation R1 with relation R2 and return the result. |
| |
| relation_kind |
| relation_union (relation_kind r1, relation_kind r2) |
| { |
| vrel_range_assert (r1); |
| vrel_range_assert (r2); |
| return rr_union_table[r1 - VREL_FIRST][r2 - VREL_FIRST]; |
| } |
| |
| |
| // This table is used to determine transitivity between 2 relations. |
| // (A relation0 B) and (B relation1 C) implies (A result C) |
| |
| relation_kind rr_transitive_table[VREL_COUNT][VREL_COUNT] = { |
| // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR |
| // VREL_NONE |
| { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE }, |
| // LT_EXPR |
| { VREL_NONE, LT_EXPR, LT_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LT_EXPR, VREL_NONE }, |
| // LE_EXPR |
| { VREL_NONE, LT_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LE_EXPR, VREL_NONE }, |
| // GT_EXPR |
| { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GT_EXPR, VREL_NONE, GT_EXPR, VREL_NONE }, |
| // GE_EXPR |
| { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GE_EXPR, VREL_NONE, GE_EXPR, VREL_NONE }, |
| // VREL_EMPTY |
| { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE }, |
| // EQ_EXPR |
| { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_NONE, EQ_EXPR, VREL_NONE }, |
| // NE_EXPR |
| { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE } }; |
| |
| // Apply transitive operation between relation R1 and relation R2, and |
| // return the resulting relation, if any. |
| |
| relation_kind |
| relation_transitive (relation_kind r1, relation_kind r2) |
| { |
| vrel_range_assert (r1); |
| vrel_range_assert (r2); |
| return rr_transitive_table[r1 - VREL_FIRST][r2 - VREL_FIRST]; |
| } |
| |
| // Given an equivalence set EQUIV, set all the bits in B that are still valid |
| // members of EQUIV in basic block BB. |
| |
| void |
| relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb) |
| { |
| unsigned i; |
| bitmap_iterator bi; |
| EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi) |
| { |
| tree ssa = ssa_name (i); |
| const_bitmap ssa_equiv = equiv_set (ssa, bb); |
| if (ssa_equiv == equivs) |
| bitmap_set_bit (b, i); |
| } |
| } |
| |
| // ------------------------------------------------------------------------- |
| |
| // The very first element in the m_equiv chain is actually just a summary |
| // element in which the m_names bitmap is used to indicate that an ssa_name |
| // has an equivalence set in this block. |
| // This allows for much faster traversal of the DOM chain, as a search for |
| // SSA_NAME simply requires walking the DOM chain until a block is found |
| // which has the bit for SSA_NAME set. Then scan for the equivalency set in |
| // that block. No previous lists need be searched. |
| |
| // If SSA has an equivalence in this list, find and return it. |
| // Otherwise return NULL. |
| |
| equiv_chain * |
| equiv_chain::find (unsigned ssa) |
| { |
| equiv_chain *ptr = NULL; |
| // If there are equiv sets and SSA is in one in this list, find it. |
| // Otherwise return NULL. |
| if (bitmap_bit_p (m_names, ssa)) |
| { |
| for (ptr = m_next; ptr; ptr = ptr->m_next) |
| if (bitmap_bit_p (ptr->m_names, ssa)) |
| break; |
| } |
| return ptr; |
| } |
| |
| // Dump the names in this equivalence set. |
| |
| void |
| equiv_chain::dump (FILE *f) const |
| { |
| bitmap_iterator bi; |
| unsigned i; |
| |
| if (!m_names) |
| return; |
| fprintf (f, "Equivalence set : ["); |
| unsigned c = 0; |
| EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi) |
| { |
| if (ssa_name (i)) |
| { |
| if (c++) |
| fprintf (f, ", "); |
| print_generic_expr (f, ssa_name (i), TDF_SLIM); |
| } |
| } |
| fprintf (f, "]\n"); |
| } |
| |
| // Instantiate an equivalency oracle. |
| |
| equiv_oracle::equiv_oracle () |
| { |
| bitmap_obstack_initialize (&m_bitmaps); |
| m_equiv.create (0); |
| m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); |
| m_equiv_set = BITMAP_ALLOC (&m_bitmaps); |
| obstack_init (&m_chain_obstack); |
| m_self_equiv.create (0); |
| m_self_equiv.safe_grow_cleared (num_ssa_names + 1); |
| } |
| |
| // Destruct an equivalency oracle. |
| |
| equiv_oracle::~equiv_oracle () |
| { |
| m_self_equiv.release (); |
| obstack_free (&m_chain_obstack, NULL); |
| m_equiv.release (); |
| bitmap_obstack_release (&m_bitmaps); |
| } |
| |
| // Find and return the equivalency set for SSA along the dominators of BB. |
| // This is the external API. |
| |
| const_bitmap |
| equiv_oracle::equiv_set (tree ssa, basic_block bb) |
| { |
| // Search the dominator tree for an equivalency. |
| equiv_chain *equiv = find_equiv_dom (ssa, bb); |
| if (equiv) |
| return equiv->m_names; |
| |
| // Otherwise return a cached equiv set containing just this SSA. |
| unsigned v = SSA_NAME_VERSION (ssa); |
| if (v >= m_self_equiv.length ()) |
| m_self_equiv.safe_grow_cleared (num_ssa_names + 1); |
| |
| if (!m_self_equiv[v]) |
| { |
| m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps); |
| bitmap_set_bit (m_self_equiv[v], v); |
| } |
| return m_self_equiv[v]; |
| } |
| |
| // Query if thre is a relation (equivalence) between 2 SSA_NAMEs. |
| |
| relation_kind |
| equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) |
| { |
| // If the 2 ssa names share the same equiv set, they are equal. |
| if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb)) |
| return EQ_EXPR; |
| return VREL_NONE; |
| } |
| |
| // Query if thre is a relation (equivalence) between 2 SSA_NAMEs. |
| |
| relation_kind |
| equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1, |
| const_bitmap e2) |
| { |
| // If the 2 ssa names share the same equiv set, they are equal. |
| if (bitmap_equal_p (e1, e2)) |
| return EQ_EXPR; |
| return VREL_NONE; |
| } |
| |
| // If SSA has an equivalence in block BB, find and return it. |
| // Otherwise return NULL. |
| |
| equiv_chain * |
| equiv_oracle::find_equiv_block (unsigned ssa, int bb) const |
| { |
| if (bb >= (int)m_equiv.length () || !m_equiv[bb]) |
| return NULL; |
| |
| return m_equiv[bb]->find (ssa); |
| } |
| |
| // Starting at block BB, walk the dominator chain looking for the nearest |
| // equivalence set containing NAME. |
| |
| equiv_chain * |
| equiv_oracle::find_equiv_dom (tree name, basic_block bb) const |
| { |
| unsigned v = SSA_NAME_VERSION (name); |
| // Short circuit looking for names which have no equivalences. |
| // Saves time looking for something which does not exist. |
| if (!bitmap_bit_p (m_equiv_set, v)) |
| return NULL; |
| |
| // NAME has at least once equivalence set, check to see if it has one along |
| // the dominator tree. |
| for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) |
| { |
| equiv_chain *ptr = find_equiv_block (v, bb->index); |
| if (ptr) |
| return ptr; |
| } |
| return NULL; |
| } |
| |
| // Register equivalance between ssa_name V and set EQUIV in block BB, |
| |
| bitmap |
| equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) |
| { |
| // V will have an equivalency now. |
| bitmap_set_bit (m_equiv_set, v); |
| |
| // If that equiv chain is in this block, simply use it. |
| if (equiv->m_bb == bb) |
| { |
| bitmap_set_bit (equiv->m_names, v); |
| bitmap_set_bit (m_equiv[bb->index]->m_names, v); |
| return NULL; |
| } |
| |
| // Otherwise create an equivalence for this block which is a copy |
| // of equiv, the add V to the set. |
| bitmap b = BITMAP_ALLOC (&m_bitmaps); |
| valid_equivs (b, equiv->m_names, bb); |
| bitmap_set_bit (b, v); |
| return b; |
| } |
| |
| // Register equivalence between set equiv_1 and equiv_2 in block BB. |
| // Return NULL if either name can be merged with the other. Otherwise |
| // return a pointer to the combined bitmap of names. This allows the |
| // caller to do any setup required for a new element. |
| |
| bitmap |
| equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, |
| equiv_chain *equiv_2) |
| { |
| // If equiv_1 is already in BB, use it as the combined set. |
| if (equiv_1->m_bb == bb) |
| { |
| valid_equivs (equiv_1->m_names, equiv_2->m_names, bb); |
| // Its hard to delete from a single linked list, so |
| // just clear the second one. |
| if (equiv_2->m_bb == bb) |
| bitmap_clear (equiv_2->m_names); |
| else |
| // Ensure the new names are in the summary for BB. |
| bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); |
| return NULL; |
| } |
| // If equiv_2 is in BB, use it for the combined set. |
| if (equiv_2->m_bb == bb) |
| { |
| valid_equivs (equiv_2->m_names, equiv_1->m_names, bb); |
| // Ensure the new names are in the summary. |
| bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); |
| return NULL; |
| } |
| |
| // At this point, neither equivalence is from this block. |
| bitmap b = BITMAP_ALLOC (&m_bitmaps); |
| valid_equivs (b, equiv_1->m_names, bb); |
| valid_equivs (b, equiv_2->m_names, bb); |
| return b; |
| } |
| |
| // Create an equivalency set containing only SSA in its definition block. |
| // This is done the first time SSA is registered in an equivalency and blocks |
| // any DOM searches past the definition. |
| |
| void |
| equiv_oracle::register_initial_def (tree ssa) |
| { |
| if (SSA_NAME_IS_DEFAULT_DEF (ssa)) |
| return; |
| basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa)); |
| gcc_checking_assert (bb && !find_equiv_dom (ssa, bb)); |
| |
| unsigned v = SSA_NAME_VERSION (ssa); |
| bitmap_set_bit (m_equiv_set, v); |
| bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps); |
| bitmap_set_bit (equiv_set, v); |
| add_equiv_to_block (bb, equiv_set); |
| } |
| |
| // Register an equivalence between SSA1 and SSA2 in block BB. |
| // The equivalence oracle maintains a vector of equivalencies indexed by basic |
| // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB, |
| // a query is made as to what equivalences both names have already, and |
| // any preexisting equivalences are merged to create a single equivalence |
| // containing all the ssa_names in this basic block. |
| |
| void |
| equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, |
| tree ssa2) |
| { |
| // Only handle equality relations. |
| if (k != EQ_EXPR) |
| return; |
| |
| unsigned v1 = SSA_NAME_VERSION (ssa1); |
| unsigned v2 = SSA_NAME_VERSION (ssa2); |
| |
| // If this is the first time an ssa_name has an equivalency registered |
| // create a self-equivalency record in the def block. |
| if (!bitmap_bit_p (m_equiv_set, v1)) |
| register_initial_def (ssa1); |
| if (!bitmap_bit_p (m_equiv_set, v2)) |
| register_initial_def (ssa2); |
| |
| equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb); |
| equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb); |
| |
| // Check if they are the same set |
| if (equiv_1 && equiv_1 == equiv_2) |
| return; |
| |
| bitmap equiv_set; |
| |
| // Case where we have 2 SSA_NAMEs that are not in any set. |
| if (!equiv_1 && !equiv_2) |
| { |
| bitmap_set_bit (m_equiv_set, v1); |
| bitmap_set_bit (m_equiv_set, v2); |
| |
| equiv_set = BITMAP_ALLOC (&m_bitmaps); |
| bitmap_set_bit (equiv_set, v1); |
| bitmap_set_bit (equiv_set, v2); |
| } |
| else if (!equiv_1 && equiv_2) |
| equiv_set = register_equiv (bb, v1, equiv_2); |
| else if (equiv_1 && !equiv_2) |
| equiv_set = register_equiv (bb, v2, equiv_1); |
| else |
| equiv_set = register_equiv (bb, equiv_1, equiv_2); |
| |
| // A non-null return is a bitmap that is to be added to the current |
| // block as a new equivalence. |
| if (!equiv_set) |
| return; |
| |
| add_equiv_to_block (bb, equiv_set); |
| } |
| |
| // Add an equivalency record in block BB containing bitmap EQUIV_SET. |
| // Note the internal caller is responible for allocating EQUIV_SET properly. |
| |
| void |
| equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set) |
| { |
| equiv_chain *ptr; |
| |
| // Check if this is the first time a block has an equivalence added. |
| // and create a header block. And set the summary for this block. |
| if (!m_equiv[bb->index]) |
| { |
| ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, |
| sizeof (equiv_chain)); |
| ptr->m_names = BITMAP_ALLOC (&m_bitmaps); |
| bitmap_copy (ptr->m_names, equiv_set); |
| ptr->m_bb = bb; |
| ptr->m_next = NULL; |
| m_equiv[bb->index] = ptr; |
| } |
| |
| // Now create the element for this equiv set and initialize it. |
| ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain)); |
| ptr->m_names = equiv_set; |
| ptr->m_bb = bb; |
| gcc_checking_assert (bb->index < (int)m_equiv.length ()); |
| ptr->m_next = m_equiv[bb->index]->m_next; |
| m_equiv[bb->index]->m_next = ptr; |
| bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set); |
| } |
| |
| // Make sure the BB vector is big enough and grow it if needed. |
| |
| void |
| equiv_oracle::limit_check (basic_block bb) |
| { |
| int i = (bb) ? bb->index : last_basic_block_for_fn (cfun); |
| if (i >= (int)m_equiv.length ()) |
| m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); |
| } |
| |
| // Dump the equivalence sets in BB to file F. |
| |
| void |
| equiv_oracle::dump (FILE *f, basic_block bb) const |
| { |
| if (bb->index >= (int)m_equiv.length ()) |
| return; |
| if (!m_equiv[bb->index]) |
| return; |
| |
| equiv_chain *ptr = m_equiv[bb->index]->m_next; |
| for (; ptr; ptr = ptr->m_next) |
| ptr->dump (f); |
| } |
| |
| // Dump all equivalence sets known to the oracle. |
| |
| void |
| equiv_oracle::dump (FILE *f) const |
| { |
| fprintf (f, "Equivalency dump\n"); |
| for (unsigned i = 0; i < m_equiv.length (); i++) |
| if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i)) |
| { |
| fprintf (f, "BB%d\n", i); |
| dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); |
| } |
| } |
| |
| |
| // -------------------------------------------------------------------------- |
| |
| // The value-relation class is used to encapsulate the represention of an |
| // individual relation between 2 ssa-names, and to facilitate operating on |
| // the relation. |
| |
| class value_relation |
| { |
| public: |
| value_relation (); |
| value_relation (relation_kind kind, tree n1, tree n2); |
| void set_relation (relation_kind kind, tree n1, tree n2); |
| |
| inline relation_kind kind () const { return related; } |
| inline tree op1 () const { return name1; } |
| inline tree op2 () const { return name2; } |
| |
| bool union_ (value_relation &p); |
| bool intersect (value_relation &p); |
| void negate (); |
| bool apply_transitive (const value_relation &rel); |
| |
| void dump (FILE *f) const; |
| private: |
| relation_kind related; |
| tree name1, name2; |
| }; |
| |
| // Set relation R between ssa_name N1 and N2. |
| |
| inline void |
| value_relation::set_relation (relation_kind r, tree n1, tree n2) |
| { |
| gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2)); |
| related = r; |
| name1 = n1; |
| name2 = n2; |
| } |
| |
| // Default constructor. |
| |
| inline |
| value_relation::value_relation () |
| { |
| related = VREL_NONE; |
| name1 = NULL_TREE; |
| name2 = NULL_TREE; |
| } |
| |
| // Constructor for relation R between SSA version N1 nd N2. |
| |
| inline |
| value_relation::value_relation (relation_kind kind, tree n1, tree n2) |
| { |
| set_relation (kind, n1, n2); |
| } |
| |
| // Negate the current relation. |
| |
| void |
| value_relation::negate () |
| { |
| related = relation_negate (related); |
| } |
| |
| // Perform an intersection between 2 relations. *this &&= p. |
| |
| bool |
| value_relation::intersect (value_relation &p) |
| { |
| // Save previous value |
| relation_kind old = related; |
| |
| if (p.op1 () == op1 () && p.op2 () == op2 ()) |
| related = relation_intersect (kind (), p.kind ()); |
| else if (p.op2 () == op1 () && p.op1 () == op2 ()) |
| related = relation_intersect (kind (), relation_swap (p.kind ())); |
| else |
| return false; |
| |
| return old != related; |
| } |
| |
| // Perform a union between 2 relations. *this ||= p. |
| |
| bool |
| value_relation::union_ (value_relation &p) |
| { |
| // Save previous value |
| relation_kind old = related; |
| |
| if (p.op1 () == op1 () && p.op2 () == op2 ()) |
| related = relation_union (kind(), p.kind()); |
| else if (p.op2 () == op1 () && p.op1 () == op2 ()) |
| related = relation_union (kind(), relation_swap (p.kind ())); |
| else |
| return false; |
| |
| return old != related; |
| } |
| |
| // Identify and apply any transitive relations between REL |
| // and THIS. Return true if there was a transformation. |
| |
| bool |
| value_relation::apply_transitive (const value_relation &rel) |
| { |
| relation_kind k = VREL_NONE; |
| |
| // Idenity any common operand, and notrmalize the relations to |
| // the form : A < B B < C produces A < C |
| if (rel.op1 () == name2) |
| { |
| // A < B B < C |
| if (rel.op2 () == name1) |
| return false; |
| k = relation_transitive (kind (), rel.kind ()); |
| if (k != VREL_NONE) |
| { |
| related = k; |
| name2 = rel.op2 (); |
| return true; |
| } |
| } |
| else if (rel.op1 () == name1) |
| { |
| // B > A B < C |
| if (rel.op2 () == name2) |
| return false; |
| k = relation_transitive (relation_swap (kind ()), rel.kind ()); |
| if (k != VREL_NONE) |
| { |
| related = k; |
| name1 = name2; |
| name2 = rel.op2 (); |
| return true; |
| } |
| } |
| else if (rel.op2 () == name2) |
| { |
| // A < B C > B |
| if (rel.op1 () == name1) |
| return false; |
| k = relation_transitive (kind (), relation_swap (rel.kind ())); |
| if (k != VREL_NONE) |
| { |
| related = k; |
| name2 = rel.op1 (); |
| return true; |
| } |
| } |
| else if (rel.op2 () == name1) |
| { |
| // B > A C > B |
| if (rel.op1 () == name2) |
| return false; |
| k = relation_transitive (relation_swap (kind ()), |
| relation_swap (rel.kind ())); |
| if (k != VREL_NONE) |
| { |
| related = k; |
| name1 = name2; |
| name2 = rel.op1 (); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // Dump the relation to file F. |
| |
| void |
| value_relation::dump (FILE *f) const |
| { |
| if (!name1 || !name2) |
| { |
| fprintf (f, "uninitialized"); |
| return; |
| } |
| fputc ('(', f); |
| print_generic_expr (f, op1 (), TDF_SLIM); |
| print_relation (f, kind ()); |
| print_generic_expr (f, op2 (), TDF_SLIM); |
| fputc(')', f); |
| } |
| |
| // This container is used to link relations in a chain. |
| |
| class relation_chain : public value_relation |
| { |
| public: |
| relation_chain *m_next; |
| }; |
| |
| // ------------------------------------------------------------------------ |
| |
| // Find the relation between any ssa_name in B1 and any name in B2 in LIST. |
| // This will allow equivalencies to be applied to any SSA_NAME in a relation. |
| |
| relation_kind |
| relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const |
| { |
| if (!m_names) |
| return VREL_NONE; |
| |
| // If both b1 and b2 aren't referenced in thie block, cant be a relation |
| if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2)) |
| return VREL_NONE; |
| |
| // Search for the fiorst relation that contains BOTH an element from B1 |
| // and B2, and return that relation. |
| for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next) |
| { |
| unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); |
| unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); |
| if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2)) |
| return ptr->kind (); |
| if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1)) |
| return relation_swap (ptr->kind ()); |
| } |
| |
| return VREL_NONE; |
| } |
| |
| // Instantiate a relation oracle. |
| |
| dom_oracle::dom_oracle () |
| { |
| m_relations.create (0); |
| m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); |
| m_relation_set = BITMAP_ALLOC (&m_bitmaps); |
| m_tmp = BITMAP_ALLOC (&m_bitmaps); |
| m_tmp2 = BITMAP_ALLOC (&m_bitmaps); |
| } |
| |
| // Destruct a relation oracle. |
| |
| dom_oracle::~dom_oracle () |
| { |
| m_relations.release (); |
| } |
| |
| // Register relation K between ssa_name OP1 and OP2 on STMT. |
| |
| void |
| relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1, |
| tree op2) |
| { |
| gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); |
| gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); |
| gcc_checking_assert (stmt && gimple_bb (stmt)); |
| |
| // Don't register lack of a relation. |
| if (k == VREL_NONE) |
| return; |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| value_relation vr (k, op1, op2); |
| fprintf (dump_file, " Registering value_relation "); |
| vr.dump (dump_file); |
| fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index); |
| print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
| } |
| |
| // If an equivalence is being added between a PHI and one of its arguments |
| // make sure that that argument is not defined in the same block. |
| // This can happen along back edges and the equivalence will not be |
| // applicable as it would require a use before def. |
| if (k == EQ_EXPR && is_a<gphi *> (stmt)) |
| { |
| tree phi_def = gimple_phi_result (stmt); |
| gcc_checking_assert (phi_def == op1 || phi_def == op2); |
| tree arg = op2; |
| if (phi_def == op2) |
| arg = op1; |
| if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg))) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, " Not registered due to "); |
| print_generic_expr (dump_file, arg, TDF_SLIM); |
| fprintf (dump_file, " being defined in the same block.\n"); |
| } |
| return; |
| } |
| } |
| register_relation (gimple_bb (stmt), k, op1, op2); |
| } |
| |
| // Register relation K between ssa_name OP1 and OP2 on edge E. |
| |
| void |
| relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2) |
| { |
| gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); |
| gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); |
| |
| // Do not register lack of relation, or blocks which have more than |
| // edge E for a predecessor. |
| if (k == VREL_NONE || !single_pred_p (e->dest)) |
| return; |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| value_relation vr (k, op1, op2); |
| fprintf (dump_file, " Registering value_relation "); |
| vr.dump (dump_file); |
| fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index); |
| } |
| |
| register_relation (e->dest, k, op1, op2); |
| } |
| |
| // Register relation K between OP! and OP2 in block BB. |
| // This creates the record and searches for existing records in the dominator |
| // tree to merge with. |
| |
| void |
| dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1, |
| tree op2) |
| { |
| // If the 2 ssa_names are the same, do nothing. An equivalence is implied, |
| // and no other relation makes sense. |
| if (op1 == op2) |
| return; |
| |
| // Equivalencies are handled by the equivalence oracle. |
| if (k == EQ_EXPR) |
| equiv_oracle::register_relation (bb, k, op1, op2); |
| else |
| { |
| relation_chain *ptr = set_one_relation (bb, k, op1, op2); |
| if (ptr) |
| register_transitives (bb, *ptr); |
| } |
| } |
| |
| // Register relation K between OP! and OP2 in block BB. |
| // This creates the record and searches for existing records in the dominator |
| // tree to merge with. Return the record, or NULL if no record was created. |
| |
| relation_chain * |
| dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1, |
| tree op2) |
| { |
| gcc_checking_assert (k != VREL_NONE && k != EQ_EXPR); |
| |
| value_relation vr(k, op1, op2); |
| int bbi = bb->index; |
| |
| if (bbi >= (int)m_relations.length()) |
| m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); |
| |
| // Summary bitmap indicating what ssa_names have relations in this BB. |
| bitmap bm = m_relations[bbi].m_names; |
| if (!bm) |
| bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps); |
| unsigned v1 = SSA_NAME_VERSION (op1); |
| unsigned v2 = SSA_NAME_VERSION (op2); |
| |
| relation_kind curr; |
| relation_chain *ptr; |
| curr = find_relation_block (bbi, v1, v2, &ptr); |
| // There is an existing relation in this block, just intersect with it. |
| if (curr != VREL_NONE) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, " Intersecting with existing "); |
| ptr->dump (dump_file); |
| } |
| // Check into whether we can simply replace the relation rather than |
| // intersecting it. THis may help with some optimistic iterative |
| // updating algorithms. |
| ptr->intersect (vr); |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, " to produce "); |
| ptr->dump (dump_file); |
| fprintf (dump_file, "\n"); |
| } |
| } |
| else |
| { |
| if (m_relations[bbi].m_num_relations >= param_relation_block_limit) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, " Not registered due to bb being full\n"); |
| return NULL; |
| } |
| m_relations[bbi].m_num_relations++; |
| // Check for an existing relation further up the DOM chain. |
| // By including dominating relations, The first one found in any search |
| // will be the aggregate of all the previous ones. |
| curr = find_relation_dom (bb, v1, v2); |
| if (curr != VREL_NONE) |
| k = relation_intersect (curr, k); |
| |
| bitmap_set_bit (bm, v1); |
| bitmap_set_bit (bm, v2); |
| bitmap_set_bit (m_relation_set, v1); |
| bitmap_set_bit (m_relation_set, v2); |
| |
| ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, |
| sizeof (relation_chain)); |
| ptr->set_relation (k, op1, op2); |
| ptr->m_next = m_relations[bbi].m_head; |
| m_relations[bbi].m_head = ptr; |
| } |
| return ptr; |
| } |
| |
| // Starting at ROOT_BB search the DOM tree looking for relations which |
| // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are |
| // bitmaps for op1/op2 and any of their equivalences that should also be |
| // considered. |
| |
| void |
| dom_oracle::register_transitives (basic_block root_bb, |
| const value_relation &relation) |
| { |
| basic_block bb; |
| // Only apply transitives to certain kinds of operations. |
| switch (relation.kind ()) |
| { |
| case LE_EXPR: |
| case LT_EXPR: |
| case GT_EXPR: |
| case GE_EXPR: |
| break; |
| default: |
| return; |
| } |
| |
| const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb); |
| const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb); |
| |
| for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) |
| { |
| int bbi = bb->index; |
| if (bbi >= (int)m_relations.length()) |
| continue; |
| const_bitmap bm = m_relations[bbi].m_names; |
| if (!bm) |
| continue; |
| if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2)) |
| continue; |
| // At least one of the 2 ops has a relation in this block. |
| relation_chain *ptr; |
| for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next) |
| { |
| // In the presence of an equivalence, 2 operands may do not |
| // naturally match. ie with equivalence a_2 == b_3 |
| // given c_1 < a_2 && b_3 < d_4 |
| // convert the second relation (b_3 < d_4) to match any |
| // equivalences to found in the first relation. |
| // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the |
| // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4 |
| |
| tree r1, r2; |
| tree p1 = ptr->op1 (); |
| tree p2 = ptr->op2 (); |
| // Find which equivalence is in the first operand. |
| if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1))) |
| r1 = p1; |
| else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2))) |
| r1 = p2; |
| else |
| r1 = NULL_TREE; |
| |
| // Find which equivalence is in the second operand. |
| if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1))) |
| r2 = p1; |
| else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2))) |
| r2 = p2; |
| else |
| r2 = NULL_TREE; |
| |
| // Ignore if both NULL (not relevant relation) or the same, |
| if (r1 == r2) |
| continue; |
| |
| // Any operand not an equivalence, just take the real operand. |
| if (!r1) |
| r1 = relation.op1 (); |
| if (!r2) |
| r2 = relation.op2 (); |
| |
| value_relation nr (relation.kind (), r1, r2); |
| if (nr.apply_transitive (*ptr)) |
| { |
| if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ())) |
| return; |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, " Registering transitive relation "); |
| nr.dump (dump_file); |
| fputc ('\n', dump_file); |
| } |
| } |
| |
| } |
| } |
| } |
| |
| // Find the relation between any ssa_name in B1 and any name in B2 in block BB. |
| // This will allow equivalencies to be applied to any SSA_NAME in a relation. |
| |
| relation_kind |
| dom_oracle::find_relation_block (unsigned bb, const_bitmap b1, |
| const_bitmap b2) const |
| { |
| if (bb >= m_relations.length()) |
| return VREL_NONE; |
| |
| return m_relations[bb].find_relation (b1, b2); |
| } |
| |
| // Search the DOM tree for a relation between an element of equivalency set B1 |
| // and B2, starting with block BB. |
| |
| relation_kind |
| dom_oracle::query_relation (basic_block bb, const_bitmap b1, |
| const_bitmap b2) |
| { |
| relation_kind r; |
| if (bitmap_equal_p (b1, b2)) |
| return EQ_EXPR; |
| |
| // If either name does not occur in a relation anywhere, there isnt one. |
| if (!bitmap_intersect_p (m_relation_set, b1) |
| || !bitmap_intersect_p (m_relation_set, b2)) |
| return VREL_NONE; |
| |
| // Search each block in the DOM tree checking. |
| for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) |
| { |
| r = find_relation_block (bb->index, b1, b2); |
| if (r != VREL_NONE) |
| return r; |
| } |
| return VREL_NONE; |
| |
| } |
| |
| // Find a relation in block BB between ssa version V1 and V2. If a relation |
| // is found, return a pointer to the chain object in OBJ. |
| |
| relation_kind |
| dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, |
| relation_chain **obj) const |
| { |
| if (bb >= (int)m_relations.length()) |
| return VREL_NONE; |
| |
| const_bitmap bm = m_relations[bb].m_names; |
| if (!bm) |
| return VREL_NONE; |
| |
| // If both b1 and b2 aren't referenced in thie block, cant be a relation |
| if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2)) |
| return VREL_NONE; |
| |
| relation_chain *ptr; |
| for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) |
| { |
| unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); |
| unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); |
| if (v1 == op1 && v2 == op2) |
| { |
| if (obj) |
| *obj = ptr; |
| return ptr->kind (); |
| } |
| if (v1 == op2 && v2 == op1) |
| { |
| if (obj) |
| *obj = ptr; |
| return relation_swap (ptr->kind ()); |
| } |
| } |
| |
| return VREL_NONE; |
| } |
| |
| // Find a relation between SSA version V1 and V2 in the dominator tree |
| // starting with block BB |
| |
| relation_kind |
| dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const |
| { |
| relation_kind r; |
| // IF either name does not occur in a relation anywhere, there isnt one. |
| if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2)) |
| return VREL_NONE; |
| |
| for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) |
| { |
| r = find_relation_block (bb->index, v1, v2); |
| if (r != VREL_NONE) |
| return r; |
| } |
| return VREL_NONE; |
| |
| } |
| |
| // Query if there is a relation between SSA1 and SS2 in block BB or a |
| // dominator of BB |
| |
| relation_kind |
| dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) |
| { |
| relation_kind kind; |
| unsigned v1 = SSA_NAME_VERSION (ssa1); |
| unsigned v2 = SSA_NAME_VERSION (ssa2); |
| if (v1 == v2) |
| return EQ_EXPR; |
| |
| // Check for equivalence first. They must be in each equivalency set. |
| const_bitmap equiv1 = equiv_set (ssa1, bb); |
| const_bitmap equiv2 = equiv_set (ssa2, bb); |
| if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1)) |
| return EQ_EXPR; |
| |
| // Initially look for a direct relationship and just return that. |
| kind = find_relation_dom (bb, v1, v2); |
| if (kind != VREL_NONE) |
| return kind; |
| |
| // Query using the equiovalence sets. |
| kind = query_relation (bb, equiv1, equiv2); |
| return kind; |
| } |
| |
| // Dump all the relations in block BB to file F. |
| |
| void |
| dom_oracle::dump (FILE *f, basic_block bb) const |
| { |
| equiv_oracle::dump (f,bb); |
| |
| if (bb->index >= (int)m_relations.length ()) |
| return; |
| if (!m_relations[bb->index].m_names) |
| return; |
| |
| relation_chain *ptr = m_relations[bb->index].m_head; |
| for (; ptr; ptr = ptr->m_next) |
| { |
| fprintf (f, "Relational : "); |
| ptr->dump (f); |
| fprintf (f, "\n"); |
| } |
| } |
| |
| // Dump all the relations known to file F. |
| |
| void |
| dom_oracle::dump (FILE *f) const |
| { |
| fprintf (f, "Relation dump\n"); |
| for (unsigned i = 0; i < m_relations.length (); i++) |
| if (BASIC_BLOCK_FOR_FN (cfun, i)) |
| { |
| fprintf (f, "BB%d\n", i); |
| dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); |
| } |
| } |
| |
| void |
| relation_oracle::debug () const |
| { |
| dump (stderr); |
| } |
| |
| path_oracle::path_oracle (relation_oracle *oracle) |
| { |
| set_root_oracle (oracle); |
| bitmap_obstack_initialize (&m_bitmaps); |
| obstack_init (&m_chain_obstack); |
| |
| // Initialize header records. |
| m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps); |
| m_equiv.m_bb = NULL; |
| m_equiv.m_next = NULL; |
| m_relations.m_names = BITMAP_ALLOC (&m_bitmaps); |
| m_relations.m_head = NULL; |
| m_killed_defs = BITMAP_ALLOC (&m_bitmaps); |
| } |
| |
| path_oracle::~path_oracle () |
| { |
| obstack_free (&m_chain_obstack, NULL); |
| bitmap_obstack_release (&m_bitmaps); |
| } |
| |
| // Return the equiv set for SSA, and if there isn't one, check for equivs |
| // starting in block BB. |
| |
| const_bitmap |
| path_oracle::equiv_set (tree ssa, basic_block bb) |
| { |
| // Check the list first. |
| equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa)); |
| if (ptr) |
| return ptr->m_names; |
| |
| // Otherwise defer to the root oracle. |
| if (m_root) |
| return m_root->equiv_set (ssa, bb); |
| |
| // Allocate a throw away bitmap if there isn't a root oracle. |
| bitmap tmp = BITMAP_ALLOC (&m_bitmaps); |
| bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa)); |
| return tmp; |
| } |
| |
| // Register an equivalence between SSA1 and SSA2 resolving unkowns from |
| // block BB. |
| |
| void |
| path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) |
| { |
| const_bitmap equiv_1 = equiv_set (ssa1, bb); |
| const_bitmap equiv_2 = equiv_set (ssa2, bb); |
| |
| // Check if they are the same set, if so, we're done. |
| if (bitmap_equal_p (equiv_1, equiv_2)) |
| return; |
| |
| // Don't mess around, simply create a new record and insert it first. |
| bitmap b = BITMAP_ALLOC (&m_bitmaps); |
| valid_equivs (b, equiv_1, bb); |
| valid_equivs (b, equiv_2, bb); |
| |
| equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, |
| sizeof (equiv_chain)); |
| ptr->m_names = b; |
| ptr->m_bb = NULL; |
| ptr->m_next = m_equiv.m_next; |
| m_equiv.m_next = ptr; |
| bitmap_ior_into (m_equiv.m_names, b); |
| } |
| |
| // Register killing definition of an SSA_NAME. |
| |
| void |
| path_oracle::killing_def (tree ssa) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, " Registering killing_def (path_oracle) "); |
| print_generic_expr (dump_file, ssa, TDF_SLIM); |
| fprintf (dump_file, "\n"); |
| } |
| |
| unsigned v = SSA_NAME_VERSION (ssa); |
| |
| bitmap_set_bit (m_killed_defs, v); |
| |
| // Walk the equivalency list and remove SSA from any equivalencies. |
| if (bitmap_bit_p (m_equiv.m_names, v)) |
| { |
| for (equiv_chain *ptr = m_equiv.m_next; ptr; ptr = ptr->m_next) |
| if (bitmap_bit_p (ptr->m_names, v)) |
| bitmap_clear_bit (ptr->m_names, v); |
| } |
| else |
| bitmap_set_bit (m_equiv.m_names, v); |
| |
| // Now add an equivalency with itself so we don't look to the root oracle. |
| bitmap b = BITMAP_ALLOC (&m_bitmaps); |
| bitmap_set_bit (b, v); |
| equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, |
| sizeof (equiv_chain)); |
| ptr->m_names = b; |
| ptr->m_bb = NULL; |
| ptr->m_next = m_equiv.m_next; |
| m_equiv.m_next = ptr; |
| |
| // Walk the relation list and remove SSA from any relations. |
| if (!bitmap_bit_p (m_relations.m_names, v)) |
| return; |
| |
| bitmap_clear_bit (m_relations.m_names, v); |
| relation_chain **prev = &(m_relations.m_head); |
| relation_chain *next = NULL; |
| for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next) |
| { |
| gcc_checking_assert (*prev == ptr); |
| next = ptr->m_next; |
| if (SSA_NAME_VERSION (ptr->op1 ()) == v |
| || SSA_NAME_VERSION (ptr->op2 ()) == v) |
| *prev = ptr->m_next; |
| else |
| prev = &(ptr->m_next); |
| } |
| } |
| |
| // Register relation K between SSA1 and SSA2, resolving unknowns by |
| // querying from BB. |
| |
| void |
| path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, |
| tree ssa2) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| value_relation vr (k, ssa1, ssa2); |
| fprintf (dump_file, " Registering value_relation (path_oracle) "); |
| vr.dump (dump_file); |
| fprintf (dump_file, " (root: bb%d)\n", bb->index); |
| } |
| |
| if (k == EQ_EXPR) |
| { |
| register_equiv (bb, ssa1, ssa2); |
| return; |
| } |
| |
| relation_kind curr = query_relation (bb, ssa1, ssa2); |
| if (curr != VREL_NONE) |
| k = relation_intersect (curr, k); |
| |
| bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1)); |
| bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2)); |
| relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, |
| sizeof (relation_chain)); |
| ptr->set_relation (k, ssa1, ssa2); |
| ptr->m_next = m_relations.m_head; |
| m_relations.m_head = ptr; |
| } |
| |
| // Query for a relationship between equiv set B1 and B2, resolving unknowns |
| // starting at block BB. |
| |
| relation_kind |
| path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2) |
| { |
| if (bitmap_equal_p (b1, b2)) |
| return EQ_EXPR; |
| |
| relation_kind k = m_relations.find_relation (b1, b2); |
| |
| // Do not look at the root oracle for names that have been killed |
| // along the path. |
| if (bitmap_intersect_p (m_killed_defs, b1) |
| || bitmap_intersect_p (m_killed_defs, b2)) |
| return k; |
| |
| if (k == VREL_NONE && m_root) |
| k = m_root->query_relation (bb, b1, b2); |
| |
| return k; |
| } |
| |
| // Query for a relationship between SSA1 and SSA2, resolving unknowns |
| // starting at block BB. |
| |
| relation_kind |
| path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) |
| { |
| unsigned v1 = SSA_NAME_VERSION (ssa1); |
| unsigned v2 = SSA_NAME_VERSION (ssa2); |
| |
| if (v1 == v2) |
| return EQ_EXPR; |
| |
| const_bitmap equiv_1 = equiv_set (ssa1, bb); |
| const_bitmap equiv_2 = equiv_set (ssa2, bb); |
| if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1)) |
| return EQ_EXPR; |
| |
| return query_relation (bb, equiv_1, equiv_2); |
| } |
| |
| // Reset any relations registered on this path. |
| |
| void |
| path_oracle::reset_path () |
| { |
| m_equiv.m_next = NULL; |
| bitmap_clear (m_equiv.m_names); |
| m_relations.m_head = NULL; |
| bitmap_clear (m_relations.m_names); |
| } |
| |
| // Dump relation in basic block... Do nothing here. |
| |
| void |
| path_oracle::dump (FILE *, basic_block) const |
| { |
| } |
| |
| // Dump the relations and equivalencies found in the path. |
| |
| void |
| path_oracle::dump (FILE *f) const |
| { |
| equiv_chain *ptr = m_equiv.m_next; |
| relation_chain *ptr2 = m_relations.m_head; |
| |
| if (ptr || ptr2) |
| fprintf (f, "\npath_oracle:\n"); |
| |
| for (; ptr; ptr = ptr->m_next) |
| ptr->dump (f); |
| |
| for (; ptr2; ptr2 = ptr2->m_next) |
| { |
| fprintf (f, "Relational : "); |
| ptr2->dump (f); |
| fprintf (f, "\n"); |
| } |
| } |