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>
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
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"
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.
38 #define VREL_FIRST VREL_NONE
39 #define VREL_LAST NE_EXPR
40 #define VREL_COUNT (VREL_LAST - VREL_FIRST + 1)
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.
45 #define vrel_range_assert(c) \
46 gcc_checking_assert ((c) >= VREL_FIRST && (c) <= VREL_LAST)
48 #define vrel_range_assert(c) \
49 if ((c) < VREL_FIRST || (c) > VREL_LAST) \
53 static const char *kind_string
[VREL_COUNT
] =
54 { "none", "<", "<=", ">", ">=", "empty", "==", "!=" };
56 // Print a relation_kind REL to file F.
59 print_relation (FILE *f
, relation_kind rel
)
61 vrel_range_assert (rel
);
62 fprintf (f
, " %s ", kind_string
[rel
- VREL_FIRST
]);
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
};
70 // Negate the relation, as in logical negation.
73 relation_negate (relation_kind r
)
75 vrel_range_assert (r
);
76 return rr_negate_table
[r
- VREL_FIRST
];
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
};
84 // Return the relation as if the operands were swapped.
87 relation_swap (relation_kind r
)
89 vrel_range_assert (r
);
90 return rr_swap_table
[r
- VREL_FIRST
];
93 // This table is used to perform an intersection between 2 relations.
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
98 { VREL_NONE
, LT_EXPR
, LE_EXPR
, GT_EXPR
, GE_EXPR
, VREL_EMPTY
, EQ_EXPR
, NE_EXPR
},
100 { LT_EXPR
, LT_EXPR
, LT_EXPR
, VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
, LT_EXPR
},
102 { LE_EXPR
, LT_EXPR
, LE_EXPR
, VREL_EMPTY
, EQ_EXPR
, VREL_EMPTY
, EQ_EXPR
, LT_EXPR
},
104 { GT_EXPR
, VREL_EMPTY
, VREL_EMPTY
, GT_EXPR
, GT_EXPR
, VREL_EMPTY
, VREL_EMPTY
, GT_EXPR
},
106 { GE_EXPR
, VREL_EMPTY
, EQ_EXPR
, GT_EXPR
, GE_EXPR
, VREL_EMPTY
, EQ_EXPR
, GT_EXPR
},
108 { VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
, VREL_EMPTY
},
110 { EQ_EXPR
, VREL_EMPTY
, EQ_EXPR
, VREL_EMPTY
, EQ_EXPR
, VREL_EMPTY
, EQ_EXPR
, VREL_EMPTY
},
112 { NE_EXPR
, LT_EXPR
, LT_EXPR
, GT_EXPR
, GT_EXPR
, VREL_EMPTY
, VREL_EMPTY
, NE_EXPR
} };
115 // Intersect relation R1 with relation R2 and return the resulting relation.
118 relation_intersect (relation_kind r1
, relation_kind r2
)
120 vrel_range_assert (r1
);
121 vrel_range_assert (r2
);
122 return rr_intersect_table
[r1
- VREL_FIRST
][r2
- VREL_FIRST
];
126 // This table is used to perform a union between 2 relations.
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
131 { VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
},
133 { VREL_NONE
, LT_EXPR
, LE_EXPR
, NE_EXPR
, VREL_NONE
, LT_EXPR
, LE_EXPR
, NE_EXPR
},
135 { VREL_NONE
, LE_EXPR
, LE_EXPR
, VREL_NONE
, VREL_NONE
, LE_EXPR
, LE_EXPR
, VREL_NONE
},
137 { VREL_NONE
, NE_EXPR
, VREL_NONE
, GT_EXPR
, GE_EXPR
, GT_EXPR
, GE_EXPR
, NE_EXPR
},
139 { VREL_NONE
, VREL_NONE
, VREL_NONE
, GE_EXPR
, GE_EXPR
, GE_EXPR
, GE_EXPR
, VREL_NONE
},
141 { VREL_NONE
, LT_EXPR
, LE_EXPR
, GT_EXPR
, GE_EXPR
, VREL_EMPTY
, EQ_EXPR
, NE_EXPR
},
143 { VREL_NONE
, LE_EXPR
, LE_EXPR
, GE_EXPR
, GE_EXPR
, EQ_EXPR
, EQ_EXPR
, VREL_NONE
},
145 { VREL_NONE
, NE_EXPR
, VREL_NONE
, NE_EXPR
, VREL_NONE
, NE_EXPR
, VREL_NONE
, NE_EXPR
} };
147 // Union relation R1 with relation R2 and return the result.
150 relation_union (relation_kind r1
, relation_kind r2
)
152 vrel_range_assert (r1
);
153 vrel_range_assert (r2
);
154 return rr_union_table
[r1
- VREL_FIRST
][r2
- VREL_FIRST
];
158 // This table is used to determine transitivity between 2 relations.
159 // (A relation0 B) and (B relation1 C) implies (A result C)
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
164 { VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
},
166 { VREL_NONE
, LT_EXPR
, LT_EXPR
, VREL_NONE
, VREL_NONE
, VREL_NONE
, LT_EXPR
, VREL_NONE
},
168 { VREL_NONE
, LT_EXPR
, LE_EXPR
, VREL_NONE
, VREL_NONE
, VREL_NONE
, LE_EXPR
, VREL_NONE
},
170 { VREL_NONE
, VREL_NONE
, VREL_NONE
, GT_EXPR
, GT_EXPR
, VREL_NONE
, GT_EXPR
, VREL_NONE
},
172 { VREL_NONE
, VREL_NONE
, VREL_NONE
, GT_EXPR
, GE_EXPR
, VREL_NONE
, GE_EXPR
, VREL_NONE
},
174 { VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
},
176 { VREL_NONE
, LT_EXPR
, LE_EXPR
, GT_EXPR
, GE_EXPR
, VREL_NONE
, EQ_EXPR
, VREL_NONE
},
178 { VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
, VREL_NONE
} };
180 // Apply transitive operation between relation R1 and relation R2, and
181 // return the resulting relation, if any.
184 relation_transitive (relation_kind r1
, relation_kind r2
)
186 vrel_range_assert (r1
);
187 vrel_range_assert (r2
);
188 return rr_transitive_table
[r1
- VREL_FIRST
][r2
- VREL_FIRST
];
191 // -------------------------------------------------------------------------
193 // The very first element in the m_equiv chain is actually just a summary
194 // element in which the m_names bitmap is used to indicate that an ssa_name
195 // has an equivalence set in this block.
196 // This allows for much faster traversal of the DOM chain, as a search for
197 // SSA_NAME simply requires walking the DOM chain until a block is found
198 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
199 // that block. No previous lists need be searched.
201 // If SSA has an equivalence in this list, find and return it.
202 // Otherwise return NULL.
205 equiv_chain::find (unsigned ssa
)
207 equiv_chain
*ptr
= NULL
;
208 // If there are equiv sets and SSA is in one in this list, find it.
209 // Otherwise return NULL.
210 if (bitmap_bit_p (m_names
, ssa
))
212 for (ptr
= m_next
; ptr
; ptr
= ptr
->m_next
)
213 if (bitmap_bit_p (ptr
->m_names
, ssa
))
219 // Dump the names in this equivalence set.
222 equiv_chain::dump (FILE *f
) const
229 fprintf (f
, "Equivalence set : [");
231 EXECUTE_IF_SET_IN_BITMAP (m_names
, 0, i
, bi
)
237 print_generic_expr (f
, ssa_name (i
), TDF_SLIM
);
243 // Instantiate an equivalency oracle.
245 equiv_oracle::equiv_oracle ()
247 bitmap_obstack_initialize (&m_bitmaps
);
249 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
250 m_equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
251 obstack_init (&m_chain_obstack
);
252 m_self_equiv
.create (0);
253 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
256 // Destruct an equivalency oracle.
258 equiv_oracle::~equiv_oracle ()
260 m_self_equiv
.release ();
261 obstack_free (&m_chain_obstack
, NULL
);
263 bitmap_obstack_release (&m_bitmaps
);
266 // Find and return the equivalency set for SSA along the dominators of BB.
267 // This is the external API.
270 equiv_oracle::equiv_set (tree ssa
, basic_block bb
)
272 // Search the dominator tree for an equivalency.
273 equiv_chain
*equiv
= find_equiv_dom (ssa
, bb
);
275 return equiv
->m_names
;
277 // Otherwise return a cached equiv set containing just this SSA.
278 unsigned v
= SSA_NAME_VERSION (ssa
);
279 if (v
>= m_self_equiv
.length ())
280 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
282 if (!m_self_equiv
[v
])
284 m_self_equiv
[v
] = BITMAP_ALLOC (&m_bitmaps
);
285 bitmap_set_bit (m_self_equiv
[v
], v
);
287 return m_self_equiv
[v
];
290 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
293 equiv_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
295 // If the 2 ssa names share the same equiv set, they are equal.
296 if (equiv_set (ssa1
, bb
) == equiv_set (ssa2
, bb
))
301 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
304 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED
, const_bitmap e1
,
307 // If the 2 ssa names share the same equiv set, they are equal.
308 if (bitmap_equal_p (e1
, e2
))
313 // If SSA has an equivalence in block BB, find and return it.
314 // Otherwise return NULL.
317 equiv_oracle::find_equiv_block (unsigned ssa
, int bb
) const
319 if (bb
>= (int)m_equiv
.length () || !m_equiv
[bb
])
322 return m_equiv
[bb
]->find (ssa
);
325 // Starting at block BB, walk the dominator chain looking for the nearest
326 // equivalence set containing NAME.
329 equiv_oracle::find_equiv_dom (tree name
, basic_block bb
) const
331 unsigned v
= SSA_NAME_VERSION (name
);
332 // Short circuit looking for names which have no equivalences.
333 // Saves time looking for something which does not exist.
334 if (!bitmap_bit_p (m_equiv_set
, v
))
337 // NAME has at least once equivalence set, check to see if it has one along
338 // the dominator tree.
339 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
341 equiv_chain
*ptr
= find_equiv_block (v
, bb
->index
);
348 // Register equivalance between ssa_name V and set EQUIV in block BB,
351 equiv_oracle::register_equiv (basic_block bb
, unsigned v
, equiv_chain
*equiv
)
353 // V will have an equivalency now.
354 bitmap_set_bit (m_equiv_set
, v
);
356 // If that equiv chain is in this block, simply use it.
357 if (equiv
->m_bb
== bb
)
359 bitmap_set_bit (equiv
->m_names
, v
);
360 bitmap_set_bit (m_equiv
[bb
->index
]->m_names
, v
);
364 // Otherwise create an equivalence for this block which is a copy
365 // of equiv, the add V to the set.
366 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
367 bitmap_copy (b
, equiv
->m_names
);
368 bitmap_set_bit (b
, v
);
372 // Register equivalence between set equiv_1 and equiv_2 in block BB.
373 // Return NULL if either name can be merged with the other. Otherwise
374 // return a pointer to the combined bitmap of names. This allows the
375 // caller to do any setup required for a new element.
378 equiv_oracle::register_equiv (basic_block bb
, equiv_chain
*equiv_1
,
379 equiv_chain
*equiv_2
)
381 // If equiv_1 is alreayd in BB, use it as the combined set.
382 if (equiv_1
->m_bb
== bb
)
384 bitmap_ior_into (equiv_1
->m_names
, equiv_2
->m_names
);
385 // Its hard to delete from a single linked list, so
386 // just clear the second one.
387 if (equiv_2
->m_bb
== bb
)
388 bitmap_clear (equiv_2
->m_names
);
390 // Ensure equiv_2s names are in the summary for BB.
391 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_2
->m_names
);
394 // If equiv_2 is in BB, use it for the combined set.
395 if (equiv_2
->m_bb
== bb
)
397 bitmap_ior_into (equiv_2
->m_names
, equiv_1
->m_names
);
398 // Add equiv_1 names into the summary.
399 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_1
->m_names
);
403 // At this point, neither equivalence is from this block.
404 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
405 bitmap_copy (b
, equiv_1
->m_names
);
406 bitmap_ior_into (b
, equiv_2
->m_names
);
410 // Create an equivalency set containing only SSA in its definition block.
411 // This is done the first time SSA is registered in an equivalency and blocks
412 // any DOM searches past the definition.
415 equiv_oracle::register_initial_def (tree ssa
)
417 if (SSA_NAME_IS_DEFAULT_DEF (ssa
))
419 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (ssa
));
420 gcc_checking_assert (bb
&& !find_equiv_dom (ssa
, bb
));
422 unsigned v
= SSA_NAME_VERSION (ssa
);
423 bitmap_set_bit (m_equiv_set
, v
);
424 bitmap equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
425 bitmap_set_bit (equiv_set
, v
);
426 add_equiv_to_block (bb
, equiv_set
);
429 // Register an equivalence between SSA1 and SSA2 in block BB.
430 // The equivalence oracle maintains a vector of equivalencies indexed by basic
431 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
432 // a query is made as to what equivalences both names have already, and
433 // any preexisting equivalences are merged to create a single equivalence
434 // containing all the ssa_names in this basic block.
437 equiv_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
440 // Only handle equality relations.
444 unsigned v1
= SSA_NAME_VERSION (ssa1
);
445 unsigned v2
= SSA_NAME_VERSION (ssa2
);
447 // If this is the first time an ssa_name has an equivalency registered
448 // create a self-equivalency record in the def block.
449 if (!bitmap_bit_p (m_equiv_set
, v1
))
450 register_initial_def (ssa1
);
451 if (!bitmap_bit_p (m_equiv_set
, v2
))
452 register_initial_def (ssa2
);
454 equiv_chain
*equiv_1
= find_equiv_dom (ssa1
, bb
);
455 equiv_chain
*equiv_2
= find_equiv_dom (ssa2
, bb
);
457 // Check if they are the same set
458 if (equiv_1
&& equiv_1
== equiv_2
)
463 // Case where we have 2 SSA_NAMEs that are not in any set.
464 if (!equiv_1
&& !equiv_2
)
466 bitmap_set_bit (m_equiv_set
, v1
);
467 bitmap_set_bit (m_equiv_set
, v2
);
469 equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
470 bitmap_set_bit (equiv_set
, v1
);
471 bitmap_set_bit (equiv_set
, v2
);
473 else if (!equiv_1
&& equiv_2
)
474 equiv_set
= register_equiv (bb
, v1
, equiv_2
);
475 else if (equiv_1
&& !equiv_2
)
476 equiv_set
= register_equiv (bb
, v2
, equiv_1
);
478 equiv_set
= register_equiv (bb
, equiv_1
, equiv_2
);
480 // A non-null return is a bitmap that is to be added to the current
481 // block as a new equivalence.
485 add_equiv_to_block (bb
, equiv_set
);
488 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
489 // Note the internal caller is responible for allocating EQUIV_SET properly.
492 equiv_oracle::add_equiv_to_block (basic_block bb
, bitmap equiv_set
)
496 // Check if this is the first time a block has an equivalence added.
497 // and create a header block. And set the summary for this block.
498 if (!m_equiv
[bb
->index
])
500 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
501 sizeof (equiv_chain
));
502 ptr
->m_names
= BITMAP_ALLOC (&m_bitmaps
);
503 bitmap_copy (ptr
->m_names
, equiv_set
);
506 m_equiv
[bb
->index
] = ptr
;
509 // Now create the element for this equiv set and initialize it.
510 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
, sizeof (equiv_chain
));
511 ptr
->m_names
= equiv_set
;
513 gcc_checking_assert (bb
->index
< (int)m_equiv
.length ());
514 ptr
->m_next
= m_equiv
[bb
->index
]->m_next
;
515 m_equiv
[bb
->index
]->m_next
= ptr
;
516 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_set
);
519 // Make sure the BB vector is big enough and grow it if needed.
522 equiv_oracle::limit_check (basic_block bb
)
524 int i
= (bb
) ? bb
->index
: last_basic_block_for_fn (cfun
);
525 if (i
>= (int)m_equiv
.length ())
526 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
529 // Dump the equivalence sets in BB to file F.
532 equiv_oracle::dump (FILE *f
, basic_block bb
) const
534 if (bb
->index
>= (int)m_equiv
.length ())
536 if (!m_equiv
[bb
->index
])
539 equiv_chain
*ptr
= m_equiv
[bb
->index
]->m_next
;
540 for (; ptr
; ptr
= ptr
->m_next
)
544 // Dump all equivalence sets known to the oracle.
547 equiv_oracle::dump (FILE *f
) const
549 fprintf (f
, "Equivalency dump\n");
550 for (unsigned i
= 0; i
< m_equiv
.length (); i
++)
551 if (m_equiv
[i
] && BASIC_BLOCK_FOR_FN (cfun
, i
))
553 fprintf (f
, "BB%d\n", i
);
554 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
559 // --------------------------------------------------------------------------
561 // The value-relation class is used to encapsulate the represention of an
562 // individual relation between 2 ssa-names, and to facilitate operating on
569 value_relation (relation_kind kind
, tree n1
, tree n2
);
570 void set_relation (relation_kind kind
, tree n1
, tree n2
);
572 inline relation_kind
kind () const { return related
; }
573 inline tree
op1 () const { return name1
; }
574 inline tree
op2 () const { return name2
; }
576 bool union_ (value_relation
&p
);
577 bool intersect (value_relation
&p
);
579 bool apply_transitive (const value_relation
&rel
);
581 void dump (FILE *f
) const;
583 relation_kind related
;
587 // Set relation R between ssa_name N1 and N2.
590 value_relation::set_relation (relation_kind r
, tree n1
, tree n2
)
592 gcc_checking_assert (SSA_NAME_VERSION (n1
) != SSA_NAME_VERSION (n2
));
598 // Default constructor.
601 value_relation::value_relation ()
608 // Constructor for relation R between SSA version N1 nd N2.
611 value_relation::value_relation (relation_kind kind
, tree n1
, tree n2
)
613 set_relation (kind
, n1
, n2
);
616 // Negate the current relation.
619 value_relation::negate ()
621 related
= relation_negate (related
);
624 // Perform an intersection between 2 relations. *this &&= p.
627 value_relation::intersect (value_relation
&p
)
629 // Save previous value
630 relation_kind old
= related
;
632 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
633 related
= relation_intersect (kind (), p
.kind ());
634 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
635 related
= relation_intersect (kind (), relation_swap (p
.kind ()));
639 return old
!= related
;
642 // Perform a union between 2 relations. *this ||= p.
645 value_relation::union_ (value_relation
&p
)
647 // Save previous value
648 relation_kind old
= related
;
650 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
651 related
= relation_union (kind(), p
.kind());
652 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
653 related
= relation_union (kind(), relation_swap (p
.kind ()));
657 return old
!= related
;
660 // Identify and apply any transitive relations between REL
661 // and THIS. Return true if there was a transformation.
664 value_relation::apply_transitive (const value_relation
&rel
)
666 relation_kind k
= VREL_NONE
;
668 // Idenity any common operand, and notrmalize the relations to
669 // the form : A < B B < C produces A < C
670 if (rel
.op1 () == name2
)
673 if (rel
.op2 () == name1
)
675 k
= relation_transitive (kind (), rel
.kind ());
683 else if (rel
.op1 () == name1
)
686 if (rel
.op2 () == name2
)
688 k
= relation_transitive (relation_swap (kind ()), rel
.kind ());
697 else if (rel
.op2 () == name2
)
700 if (rel
.op1 () == name1
)
702 k
= relation_transitive (kind (), relation_swap (rel
.kind ()));
710 else if (rel
.op2 () == name1
)
713 if (rel
.op1 () == name2
)
715 k
= relation_transitive (relation_swap (kind ()),
716 relation_swap (rel
.kind ()));
728 // Dump the relation to file F.
731 value_relation::dump (FILE *f
) const
733 if (!name1
|| !name2
)
735 fprintf (f
, "uninitialized");
739 print_generic_expr (f
, op1 (), TDF_SLIM
);
740 print_relation (f
, kind ());
741 print_generic_expr (f
, op2 (), TDF_SLIM
);
745 // This container is used to link relations in a chain.
747 class relation_chain
: public value_relation
750 relation_chain
*m_next
;
753 // ------------------------------------------------------------------------
755 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
756 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
759 relation_chain_head::find_relation (const_bitmap b1
, const_bitmap b2
) const
764 // If both b1 and b2 aren't referenced in thie block, cant be a relation
765 if (!bitmap_intersect_p (m_names
, b1
) || !bitmap_intersect_p (m_names
, b2
))
768 // Search for the fiorst relation that contains BOTH an element from B1
769 // and B2, and return that relation.
770 for (relation_chain
*ptr
= m_head
; ptr
; ptr
= ptr
->m_next
)
772 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
773 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
774 if (bitmap_bit_p (b1
, op1
) && bitmap_bit_p (b2
, op2
))
776 if (bitmap_bit_p (b1
, op2
) && bitmap_bit_p (b2
, op1
))
777 return relation_swap (ptr
->kind ());
783 // Instantiate a relation oracle.
785 dom_oracle::dom_oracle ()
787 m_relations
.create (0);
788 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
789 m_relation_set
= BITMAP_ALLOC (&m_bitmaps
);
790 m_tmp
= BITMAP_ALLOC (&m_bitmaps
);
791 m_tmp2
= BITMAP_ALLOC (&m_bitmaps
);
794 // Destruct a relation oracle.
796 dom_oracle::~dom_oracle ()
798 m_relations
.release ();
801 // Register relation K between ssa_name OP1 and OP2 on STMT.
804 relation_oracle::register_stmt (gimple
*stmt
, relation_kind k
, tree op1
,
807 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
808 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
809 gcc_checking_assert (stmt
&& gimple_bb (stmt
));
811 // Don't register lack of a relation.
815 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
817 value_relation
vr (k
, op1
, op2
);
818 fprintf (dump_file
, " Registering value_relation ");
820 fprintf (dump_file
, " (bb%d) at ", gimple_bb (stmt
)->index
);
821 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
824 // If an equivalence is being added between a PHI and one of its arguments
825 // make sure that that argument is not defined in the same block.
826 // This can happen along back edges and the equivalence will not be
827 // applicable as it would require a use before def.
828 if (k
== EQ_EXPR
&& is_a
<gphi
*> (stmt
))
830 tree phi_def
= gimple_phi_result (stmt
);
831 gcc_checking_assert (phi_def
== op1
|| phi_def
== op2
);
835 if (gimple_bb (stmt
) == gimple_bb (SSA_NAME_DEF_STMT (arg
)))
837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
839 fprintf (dump_file
, " Not registered due to ");
840 print_generic_expr (dump_file
, arg
, TDF_SLIM
);
841 fprintf (dump_file
, " being defined in the same block.\n");
846 register_relation (gimple_bb (stmt
), k
, op1
, op2
);
849 // Register relation K between ssa_name OP1 and OP2 on edge E.
852 relation_oracle::register_edge (edge e
, relation_kind k
, tree op1
, tree op2
)
854 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
855 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
857 // Do not register lack of relation, or blocks which have more than
858 // edge E for a predecessor.
859 if (k
== VREL_NONE
|| !single_pred_p (e
->dest
))
862 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
864 value_relation
vr (k
, op1
, op2
);
865 fprintf (dump_file
, " Registering value_relation ");
867 fprintf (dump_file
, " on (%d->%d)\n", e
->src
->index
, e
->dest
->index
);
870 register_relation (e
->dest
, k
, op1
, op2
);
873 // Register relation K between OP! and OP2 in block BB.
874 // This creates the record and searches for existing records in the dominator
875 // tree to merge with.
878 dom_oracle::register_relation (basic_block bb
, relation_kind k
, tree op1
,
881 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
882 // and no other relation makes sense.
886 // Equivalencies are handled by the equivalence oracle.
888 equiv_oracle::register_relation (bb
, k
, op1
, op2
);
891 relation_chain
*ptr
= set_one_relation (bb
, k
, op1
, op2
);
892 register_transitives (bb
, *ptr
);
896 // Register relation K between OP! and OP2 in block BB.
897 // This creates the record and searches for existing records in the dominator
898 // tree to merge with.
901 dom_oracle::set_one_relation (basic_block bb
, relation_kind k
, tree op1
,
904 gcc_checking_assert (k
!= VREL_NONE
&& k
!= EQ_EXPR
);
906 value_relation
vr(k
, op1
, op2
);
909 if (bbi
>= (int)m_relations
.length())
910 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
912 // Summary bitmap indicating what ssa_names have relations in this BB.
913 bitmap bm
= m_relations
[bbi
].m_names
;
915 bm
= m_relations
[bbi
].m_names
= BITMAP_ALLOC (&m_bitmaps
);
916 unsigned v1
= SSA_NAME_VERSION (op1
);
917 unsigned v2
= SSA_NAME_VERSION (op2
);
921 curr
= find_relation_block (bbi
, v1
, v2
, &ptr
);
922 // There is an existing relation in this block, just intersect with it.
923 if (curr
!= VREL_NONE
)
925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
927 fprintf (dump_file
, " Intersecting with existing ");
928 ptr
->dump (dump_file
);
930 // Check into whether we can simply replace the relation rather than
931 // intersecting it. THis may help with some optimistic iterative
932 // updating algorithms.
934 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
936 fprintf (dump_file
, " to produce ");
937 ptr
->dump (dump_file
);
938 fprintf (dump_file
, "\n");
943 // Check for an existing relation further up the DOM chain.
944 // By including dominating relations, The first one found in any search
945 // will be the aggregate of all the previous ones.
946 curr
= find_relation_dom (bb
, v1
, v2
);
947 if (curr
!= VREL_NONE
)
948 k
= relation_intersect (curr
, k
);
950 bitmap_set_bit (bm
, v1
);
951 bitmap_set_bit (bm
, v2
);
952 bitmap_set_bit (m_relation_set
, v1
);
953 bitmap_set_bit (m_relation_set
, v2
);
955 ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
956 sizeof (relation_chain
));
957 ptr
->set_relation (k
, op1
, op2
);
958 ptr
->m_next
= m_relations
[bbi
].m_head
;
959 m_relations
[bbi
].m_head
= ptr
;
964 // Starting at ROOT_BB search the DOM tree looking for relations which
965 // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
966 // bitmaps for op1/op2 and any of their equivalences that should also be
970 dom_oracle::register_transitives (basic_block root_bb
,
971 const value_relation
&relation
)
974 // Only apply transitives to certain kinds of operations.
975 switch (relation
.kind ())
986 const_bitmap equiv1
= equiv_set (relation
.op1 (), root_bb
);
987 const_bitmap equiv2
= equiv_set (relation
.op2 (), root_bb
);
989 for (bb
= root_bb
; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
992 if (bbi
>= (int)m_relations
.length())
994 const_bitmap bm
= m_relations
[bbi
].m_names
;
997 if (!bitmap_intersect_p (bm
, equiv1
) && !bitmap_intersect_p (bm
, equiv2
))
999 // At least one of the 2 ops has a relation in this block.
1000 relation_chain
*ptr
;
1001 for (ptr
= m_relations
[bbi
].m_head
; ptr
; ptr
= ptr
->m_next
)
1003 // In the presence of an equivalence, 2 operands may do not
1004 // naturally match. ie with equivalence a_2 == b_3
1005 // given c_1 < a_2 && b_3 < d_4
1006 // convert the second relation (b_3 < d_4) to match any
1007 // equivalences to found in the first relation.
1008 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1009 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1012 tree p1
= ptr
->op1 ();
1013 tree p2
= ptr
->op2 ();
1014 // Find which equivalence is in the first operand.
1015 if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p1
)))
1017 else if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p2
)))
1022 // Find which equivalence is in the second operand.
1023 if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p1
)))
1025 else if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p2
)))
1030 // Ignore if both NULL (not relevant relation) or the same,
1034 // Any operand not an equivalence, just take the real operand.
1036 r1
= relation
.op1 ();
1038 r2
= relation
.op2 ();
1040 value_relation
nr (relation
.kind (), r1
, r2
);
1041 if (nr
.apply_transitive (*ptr
))
1043 set_one_relation (root_bb
, nr
.kind (), nr
.op1 (), nr
.op2 ());
1044 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1046 fprintf (dump_file
, " Registering transitive relation ");
1047 nr
.dump (dump_file
);
1048 fputc ('\n', dump_file
);
1056 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1057 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1060 dom_oracle::find_relation_block (unsigned bb
, const_bitmap b1
,
1061 const_bitmap b2
) const
1063 if (bb
>= m_relations
.length())
1066 return m_relations
[bb
].find_relation (b1
, b2
);
1069 // Search the DOM tree for a relation between an element of equivalency set B1
1070 // and B2, starting with block BB.
1073 dom_oracle::query_relation (basic_block bb
, const_bitmap b1
,
1077 if (bitmap_equal_p (b1
, b2
))
1080 // If either name does not occur in a relation anywhere, there isnt one.
1081 if (!bitmap_intersect_p (m_relation_set
, b1
)
1082 || !bitmap_intersect_p (m_relation_set
, b2
))
1085 // Search each block in the DOM tree checking.
1086 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1088 r
= find_relation_block (bb
->index
, b1
, b2
);
1096 // Find a relation in block BB between ssa version V1 and V2. If a relation
1097 // is found, return a pointer to the chain object in OBJ.
1100 dom_oracle::find_relation_block (int bb
, unsigned v1
, unsigned v2
,
1101 relation_chain
**obj
) const
1103 if (bb
>= (int)m_relations
.length())
1106 const_bitmap bm
= m_relations
[bb
].m_names
;
1110 // If both b1 and b2 aren't referenced in thie block, cant be a relation
1111 if (!bitmap_bit_p (bm
, v1
) || !bitmap_bit_p (bm
, v2
))
1114 relation_chain
*ptr
;
1115 for (ptr
= m_relations
[bb
].m_head
; ptr
; ptr
= ptr
->m_next
)
1117 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
1118 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
1119 if (v1
== op1
&& v2
== op2
)
1123 return ptr
->kind ();
1125 if (v1
== op2
&& v2
== op1
)
1129 return relation_swap (ptr
->kind ());
1136 // Find a relation between SSA version V1 and V2 in the dominator tree
1137 // starting with block BB
1140 dom_oracle::find_relation_dom (basic_block bb
, unsigned v1
, unsigned v2
) const
1143 // IF either name does not occur in a relation anywhere, there isnt one.
1144 if (!bitmap_bit_p (m_relation_set
, v1
) || !bitmap_bit_p (m_relation_set
, v2
))
1147 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1149 r
= find_relation_block (bb
->index
, v1
, v2
);
1157 // Query if there is a relation between SSA1 and SS2 in block BB or a
1161 dom_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1164 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1165 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1169 // Check for equivalence first. They must be in each equivalency set.
1170 const_bitmap equiv1
= equiv_set (ssa1
, bb
);
1171 const_bitmap equiv2
= equiv_set (ssa2
, bb
);
1172 if (bitmap_bit_p (equiv1
, v2
) && bitmap_bit_p (equiv2
, v1
))
1175 // Initially look for a direct relationship and just return that.
1176 kind
= find_relation_dom (bb
, v1
, v2
);
1177 if (kind
!= VREL_NONE
)
1180 // Query using the equiovalence sets.
1181 kind
= query_relation (bb
, equiv1
, equiv2
);
1185 // Dump all the relations in block BB to file F.
1188 dom_oracle::dump (FILE *f
, basic_block bb
) const
1190 equiv_oracle::dump (f
,bb
);
1192 if (bb
->index
>= (int)m_relations
.length ())
1194 if (!m_relations
[bb
->index
].m_names
)
1197 relation_chain
*ptr
= m_relations
[bb
->index
].m_head
;
1198 for (; ptr
; ptr
= ptr
->m_next
)
1200 fprintf (f
, "Relational : ");
1206 // Dump all the relations known to file F.
1209 dom_oracle::dump (FILE *f
) const
1211 fprintf (f
, "Relation dump\n");
1212 for (unsigned i
= 0; i
< m_relations
.length (); i
++)
1213 if (BASIC_BLOCK_FOR_FN (cfun
, i
))
1215 fprintf (f
, "BB%d\n", i
);
1216 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
1221 relation_oracle::debug () const
1226 path_oracle::path_oracle (relation_oracle
*oracle
)
1229 bitmap_obstack_initialize (&m_bitmaps
);
1230 obstack_init (&m_chain_obstack
);
1232 // Initialize header records.
1233 m_equiv
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1234 m_equiv
.m_bb
= NULL
;
1235 m_equiv
.m_next
= NULL
;
1236 m_relations
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1237 m_relations
.m_head
= NULL
;
1238 m_killed_defs
= BITMAP_ALLOC (&m_bitmaps
);
1241 path_oracle::~path_oracle ()
1243 obstack_free (&m_chain_obstack
, NULL
);
1244 bitmap_obstack_release (&m_bitmaps
);
1247 // Return the equiv set for SSA, and if there isn't one, check for equivs
1248 // starting in block BB.
1251 path_oracle::equiv_set (tree ssa
, basic_block bb
)
1253 // Check the list first.
1254 equiv_chain
*ptr
= m_equiv
.find (SSA_NAME_VERSION (ssa
));
1256 return ptr
->m_names
;
1258 // Otherwise defer to the root oracle.
1260 return m_root
->equiv_set (ssa
, bb
);
1262 // Allocate a throw away bitmap if there isn't a root oracle.
1263 bitmap tmp
= BITMAP_ALLOC (&m_bitmaps
);
1264 bitmap_set_bit (tmp
, SSA_NAME_VERSION (ssa
));
1268 // Register an equivalence between SSA1 and SSA2 resolving unkowns from
1272 path_oracle::register_equiv (basic_block bb
, tree ssa1
, tree ssa2
)
1274 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1275 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1277 // Check if they are the same set, if so, we're done.
1278 if (bitmap_equal_p (equiv_1
, equiv_2
))
1281 // Don't mess around, simply create a new record and insert it first.
1282 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1283 bitmap_copy (b
, equiv_1
);
1284 bitmap_ior_into (b
, equiv_2
);
1286 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1287 sizeof (equiv_chain
));
1290 ptr
->m_next
= m_equiv
.m_next
;
1291 m_equiv
.m_next
= ptr
;
1292 bitmap_ior_into (m_equiv
.m_names
, b
);
1295 // Register killing definition of an SSA_NAME.
1298 path_oracle::killing_def (tree ssa
)
1300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1302 fprintf (dump_file
, " Registering killing_def (path_oracle) ");
1303 print_generic_expr (dump_file
, ssa
, TDF_SLIM
);
1304 fprintf (dump_file
, "\n");
1307 unsigned v
= SSA_NAME_VERSION (ssa
);
1309 bitmap_set_bit (m_killed_defs
, v
);
1311 // Walk the equivalency list and remove SSA from any equivalencies.
1312 if (bitmap_bit_p (m_equiv
.m_names
, v
))
1314 for (equiv_chain
*ptr
= m_equiv
.m_next
; ptr
; ptr
= ptr
->m_next
)
1315 if (bitmap_bit_p (ptr
->m_names
, v
))
1316 bitmap_clear_bit (ptr
->m_names
, v
);
1319 bitmap_set_bit (m_equiv
.m_names
, v
);
1321 // Now add an equivalency with itself so we don't look to the root oracle.
1322 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1323 bitmap_set_bit (b
, v
);
1324 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1325 sizeof (equiv_chain
));
1328 ptr
->m_next
= m_equiv
.m_next
;
1329 m_equiv
.m_next
= ptr
;
1331 // Walk the relation list and remove SSA from any relations.
1332 if (!bitmap_bit_p (m_relations
.m_names
, v
))
1335 bitmap_clear_bit (m_relations
.m_names
, v
);
1336 relation_chain
**prev
= &(m_relations
.m_head
);
1337 relation_chain
*next
= NULL
;
1338 for (relation_chain
*ptr
= m_relations
.m_head
; ptr
; ptr
= next
)
1340 gcc_checking_assert (*prev
== ptr
);
1342 if (SSA_NAME_VERSION (ptr
->op1 ()) == v
1343 || SSA_NAME_VERSION (ptr
->op2 ()) == v
)
1344 *prev
= ptr
->m_next
;
1346 prev
= &(ptr
->m_next
);
1350 // Register relation K between SSA1 and SSA2, resolving unknowns by
1351 // querying from BB.
1354 path_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
1357 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1359 value_relation
vr (k
, ssa1
, ssa2
);
1360 fprintf (dump_file
, " Registering value_relation (path_oracle) ");
1361 vr
.dump (dump_file
);
1362 fprintf (dump_file
, " (bb%d)\n", bb
->index
);
1367 register_equiv (bb
, ssa1
, ssa2
);
1371 relation_kind curr
= query_relation (bb
, ssa1
, ssa2
);
1372 if (curr
!= VREL_NONE
)
1373 k
= relation_intersect (curr
, k
);
1375 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa1
));
1376 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa2
));
1377 relation_chain
*ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1378 sizeof (relation_chain
));
1379 ptr
->set_relation (k
, ssa1
, ssa2
);
1380 ptr
->m_next
= m_relations
.m_head
;
1381 m_relations
.m_head
= ptr
;
1384 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1385 // starting at block BB.
1388 path_oracle::query_relation (basic_block bb
, const_bitmap b1
, const_bitmap b2
)
1390 if (bitmap_equal_p (b1
, b2
))
1393 relation_kind k
= m_relations
.find_relation (b1
, b2
);
1395 // Do not look at the root oracle for names that have been killed
1397 if (bitmap_intersect_p (m_killed_defs
, b1
)
1398 || bitmap_intersect_p (m_killed_defs
, b2
))
1401 if (k
== VREL_NONE
&& m_root
)
1402 k
= m_root
->query_relation (bb
, b1
, b2
);
1407 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1408 // starting at block BB.
1411 path_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1413 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1414 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1419 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1420 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1421 if (bitmap_bit_p (equiv_1
, v2
) && bitmap_bit_p (equiv_2
, v1
))
1424 return query_relation (bb
, equiv_1
, equiv_2
);
1427 // Reset any relations registered on this path.
1430 path_oracle::reset_path ()
1432 m_equiv
.m_next
= NULL
;
1433 bitmap_clear (m_equiv
.m_names
);
1434 m_relations
.m_head
= NULL
;
1435 bitmap_clear (m_relations
.m_names
);
1438 // Dump relation in basic block... Do nothing here.
1441 path_oracle::dump (FILE *, basic_block
) const
1445 // Dump the relations and equivalencies found in the path.
1448 path_oracle::dump (FILE *f
) const
1450 equiv_chain
*ptr
= m_equiv
.m_next
;
1451 relation_chain
*ptr2
= m_relations
.m_head
;
1454 fprintf (f
, "\npath_oracle:\n");
1456 for (; ptr
; ptr
= ptr
->m_next
)
1459 for (; ptr2
; ptr2
= ptr2
->m_next
)
1461 fprintf (f
, "Relational : ");