1 /* Header file for the value range relational processing.
2 Copyright (C) 2020-2024 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 static const char *const kind_string
[VREL_LAST
] =
36 { "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16",
39 // Print a relation_kind REL to file F.
42 print_relation (FILE *f
, relation_kind rel
)
44 fprintf (f
, " %s ", kind_string
[rel
]);
47 // This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2).
48 static const unsigned char rr_negate_table
[VREL_LAST
] = {
49 VREL_VARYING
, VREL_UNDEFINED
, VREL_GE
, VREL_GT
, VREL_LE
, VREL_LT
, VREL_NE
,
52 // Negate the relation, as in logical negation.
55 relation_negate (relation_kind r
)
57 return relation_kind (rr_negate_table
[r
]);
60 // This table is used to swap the operands. op1 REL op2 -> op2 REL op1.
61 static const unsigned char rr_swap_table
[VREL_LAST
] = {
62 VREL_VARYING
, VREL_UNDEFINED
, VREL_GT
, VREL_GE
, VREL_LT
, VREL_LE
, VREL_EQ
,
65 // Return the relation as if the operands were swapped.
68 relation_swap (relation_kind r
)
70 return relation_kind (rr_swap_table
[r
]);
73 // This table is used to perform an intersection between 2 relations.
75 static const unsigned char rr_intersect_table
[VREL_LAST
][VREL_LAST
] = {
77 { VREL_VARYING
, VREL_UNDEFINED
, VREL_LT
, VREL_LE
, VREL_GT
, VREL_GE
, VREL_EQ
,
80 { VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
,
81 VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
},
83 { VREL_LT
, VREL_UNDEFINED
, VREL_LT
, VREL_LT
, VREL_UNDEFINED
, VREL_UNDEFINED
,
84 VREL_UNDEFINED
, VREL_LT
},
86 { VREL_LE
, VREL_UNDEFINED
, VREL_LT
, VREL_LE
, VREL_UNDEFINED
, VREL_EQ
,
89 { VREL_GT
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_GT
, VREL_GT
,
90 VREL_UNDEFINED
, VREL_GT
},
92 { VREL_GE
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_EQ
, VREL_GT
, VREL_GE
,
95 { VREL_EQ
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_EQ
, VREL_UNDEFINED
, VREL_EQ
,
96 VREL_EQ
, VREL_UNDEFINED
},
98 { VREL_NE
, VREL_UNDEFINED
, VREL_LT
, VREL_LT
, VREL_GT
, VREL_GT
,
99 VREL_UNDEFINED
, VREL_NE
} };
102 // Intersect relation R1 with relation R2 and return the resulting relation.
105 relation_intersect (relation_kind r1
, relation_kind r2
)
107 return relation_kind (rr_intersect_table
[r1
][r2
]);
111 // This table is used to perform a union between 2 relations.
113 static const unsigned char rr_union_table
[VREL_LAST
][VREL_LAST
] = {
115 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
116 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
},
118 { VREL_VARYING
, VREL_UNDEFINED
, VREL_LT
, VREL_LE
, VREL_GT
, VREL_GE
,
121 { VREL_VARYING
, VREL_LT
, VREL_LT
, VREL_LE
, VREL_NE
, VREL_VARYING
, VREL_LE
,
124 { VREL_VARYING
, VREL_LE
, VREL_LE
, VREL_LE
, VREL_VARYING
, VREL_VARYING
,
125 VREL_LE
, VREL_VARYING
},
127 { VREL_VARYING
, VREL_GT
, VREL_NE
, VREL_VARYING
, VREL_GT
, VREL_GE
, VREL_GE
,
130 { VREL_VARYING
, VREL_GE
, VREL_VARYING
, VREL_VARYING
, VREL_GE
, VREL_GE
,
131 VREL_GE
, VREL_VARYING
},
133 { VREL_VARYING
, VREL_EQ
, VREL_LE
, VREL_LE
, VREL_GE
, VREL_GE
, VREL_EQ
,
136 { VREL_VARYING
, VREL_NE
, VREL_NE
, VREL_VARYING
, VREL_NE
, VREL_VARYING
,
137 VREL_VARYING
, VREL_NE
} };
139 // Union relation R1 with relation R2 and return the result.
142 relation_union (relation_kind r1
, relation_kind r2
)
144 return relation_kind (rr_union_table
[r1
][r2
]);
148 // This table is used to determine transitivity between 2 relations.
149 // (A relation0 B) and (B relation1 C) implies (A result C)
151 static const unsigned char rr_transitive_table
[VREL_LAST
][VREL_LAST
] = {
153 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
154 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
},
156 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
157 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
},
159 { VREL_VARYING
, VREL_VARYING
, VREL_LT
, VREL_LT
, VREL_VARYING
, VREL_VARYING
,
160 VREL_LT
, VREL_VARYING
},
162 { VREL_VARYING
, VREL_VARYING
, VREL_LT
, VREL_LE
, VREL_VARYING
, VREL_VARYING
,
163 VREL_LE
, VREL_VARYING
},
165 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_GT
, VREL_GT
,
166 VREL_GT
, VREL_VARYING
},
168 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_GT
, VREL_GE
,
169 VREL_GE
, VREL_VARYING
},
171 { VREL_VARYING
, VREL_VARYING
, VREL_LT
, VREL_LE
, VREL_GT
, VREL_GE
, VREL_EQ
,
174 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
175 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
} };
177 // Apply transitive operation between relation R1 and relation R2, and
178 // return the resulting relation, if any.
181 relation_transitive (relation_kind r1
, relation_kind r2
)
183 return relation_kind (rr_transitive_table
[r1
][r2
]);
186 // When one name is an equivalence of another, ensure the equivalence
187 // range is correct. Specifically for floating point, a +0 is also
188 // equivalent to a -0 which may not be reflected. See PR 111694.
191 adjust_equivalence_range (vrange
&range
)
193 if (range
.undefined_p () || !is_a
<frange
> (range
))
196 frange fr
= as_a
<frange
> (range
);
197 // If range includes 0 make sure both signs of zero are included.
198 if (fr
.contains_p (dconst0
) || fr
.contains_p (dconstm0
))
200 frange
zeros (range
.type (), dconstm0
, dconst0
);
201 range
.union_ (zeros
);
205 // This vector maps a relation to the equivalent tree code.
207 static const tree_code relation_to_code
[VREL_LAST
] = {
208 ERROR_MARK
, ERROR_MARK
, LT_EXPR
, LE_EXPR
, GT_EXPR
, GE_EXPR
, EQ_EXPR
,
211 // This routine validates that a relation can be applied to a specific set of
212 // ranges. In particular, floating point x == x may not be true if the NaN bit
213 // is set in the range. Symbolically the oracle will determine x == x,
214 // but specific range instances may override this.
215 // To verify, attempt to fold the relation using the supplied ranges.
216 // One would expect [1,1] to be returned, anything else means there is something
217 // in the range preventing the relation from applying.
218 // If there is no mechanism to verify, assume the relation is acceptable.
221 relation_oracle::validate_relation (relation_kind rel
, vrange
&op1
, vrange
&op2
)
223 // If there is no mapping to a tree code, leave the relation as is.
224 tree_code code
= relation_to_code
[rel
];
225 if (code
== ERROR_MARK
)
228 // Undefined ranges cannot be checked either.
229 if (op1
.undefined_p () || op2
.undefined_p ())
232 tree t1
= op1
.type ();
233 tree t2
= op2
.type ();
235 // If the range types are not compatible, no relation can exist.
236 if (!range_compatible_p (t1
, t2
))
239 // If there is no handler, leave the relation as is.
240 range_op_handler
handler (code
);
244 // If the relation cannot be folded for any reason, leave as is.
245 Value_Range
result (boolean_type_node
);
246 if (!handler
.fold_range (result
, boolean_type_node
, op1
, op2
,
247 relation_trio::op1_op2 (rel
)))
250 // The expression op1 REL op2 using REL should fold to [1,1].
251 // Any other result means the relation is not verified to be true.
252 if (result
.varying_p () || result
.zero_p ())
258 // If no range is available, create a varying range for each SSA name and
262 relation_oracle::validate_relation (relation_kind rel
, tree ssa1
, tree ssa2
)
264 Value_Range op1
, op2
;
265 op1
.set_varying (TREE_TYPE (ssa1
));
266 op2
.set_varying (TREE_TYPE (ssa2
));
268 return validate_relation (rel
, op1
, op2
);
271 // Given an equivalence set EQUIV, set all the bits in B that are still valid
272 // members of EQUIV in basic block BB.
275 relation_oracle::valid_equivs (bitmap b
, const_bitmap equivs
, basic_block bb
)
279 EXECUTE_IF_SET_IN_BITMAP (equivs
, 0, i
, bi
)
281 tree ssa
= ssa_name (i
);
282 if (ssa
&& !SSA_NAME_IN_FREE_LIST (ssa
))
284 const_bitmap ssa_equiv
= equiv_set (ssa
, bb
);
285 if (ssa_equiv
== equivs
)
286 bitmap_set_bit (b
, i
);
291 // -------------------------------------------------------------------------
293 // The very first element in the m_equiv chain is actually just a summary
294 // element in which the m_names bitmap is used to indicate that an ssa_name
295 // has an equivalence set in this block.
296 // This allows for much faster traversal of the DOM chain, as a search for
297 // SSA_NAME simply requires walking the DOM chain until a block is found
298 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
299 // that block. No previous lists need be searched.
301 // If SSA has an equivalence in this list, find and return it.
302 // Otherwise return NULL.
305 equiv_chain::find (unsigned ssa
)
307 equiv_chain
*ptr
= NULL
;
308 // If there are equiv sets and SSA is in one in this list, find it.
309 // Otherwise return NULL.
310 if (bitmap_bit_p (m_names
, ssa
))
312 for (ptr
= m_next
; ptr
; ptr
= ptr
->m_next
)
313 if (bitmap_bit_p (ptr
->m_names
, ssa
))
319 // Dump the names in this equivalence set.
322 equiv_chain::dump (FILE *f
) const
327 if (!m_names
|| bitmap_empty_p (m_names
))
329 fprintf (f
, "Equivalence set : [");
331 EXECUTE_IF_SET_IN_BITMAP (m_names
, 0, i
, bi
)
337 print_generic_expr (f
, ssa_name (i
), TDF_SLIM
);
343 // Instantiate an equivalency oracle.
345 equiv_oracle::equiv_oracle ()
347 bitmap_obstack_initialize (&m_bitmaps
);
349 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
350 m_equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
351 obstack_init (&m_chain_obstack
);
352 m_self_equiv
.create (0);
353 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
354 m_partial
.create (0);
355 m_partial
.safe_grow_cleared (num_ssa_names
+ 1);
358 // Destruct an equivalency oracle.
360 equiv_oracle::~equiv_oracle ()
362 m_partial
.release ();
363 m_self_equiv
.release ();
364 obstack_free (&m_chain_obstack
, NULL
);
366 bitmap_obstack_release (&m_bitmaps
);
369 // Add a partial equivalence R between OP1 and OP2.
372 equiv_oracle::add_partial_equiv (relation_kind r
, tree op1
, tree op2
)
374 int v1
= SSA_NAME_VERSION (op1
);
375 int v2
= SSA_NAME_VERSION (op2
);
376 int prec2
= TYPE_PRECISION (TREE_TYPE (op2
));
377 int bits
= pe_to_bits (r
);
378 gcc_checking_assert (bits
&& prec2
>= bits
);
380 if (v1
>= (int)m_partial
.length () || v2
>= (int)m_partial
.length ())
381 m_partial
.safe_grow_cleared (num_ssa_names
+ 1);
382 gcc_checking_assert (v1
< (int)m_partial
.length ()
383 && v2
< (int)m_partial
.length ());
385 pe_slice
&pe1
= m_partial
[v1
];
386 pe_slice
&pe2
= m_partial
[v2
];
390 // If the definition pe1 already has an entry, either the stmt is
391 // being re-evaluated, or the def was used before being registered.
392 // In either case, if PE2 has an entry, we simply do nothing.
395 // If there are no uses of op2, do not register.
396 if (has_zero_uses (op2
))
398 // PE1 is the LHS and already has members, so everything in the set
399 // should be a slice of PE2 rather than PE1.
400 pe2
.code
= pe_min (r
, pe1
.code
);
402 pe2
.members
= pe1
.members
;
405 EXECUTE_IF_SET_IN_BITMAP (pe1
.members
, 0, x
, bi
)
407 m_partial
[x
].ssa_base
= op2
;
408 m_partial
[x
].code
= pe_min (m_partial
[x
].code
, pe2
.code
);
410 bitmap_set_bit (pe1
.members
, v2
);
415 // If there are no uses of op1, do not register.
416 if (has_zero_uses (op1
))
418 pe1
.ssa_base
= pe2
.ssa_base
;
419 // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
420 // more than an 8 bit equivalence here, so choose MIN value.
421 pe1
.code
= pe_min (r
, pe2
.code
);
422 pe1
.members
= pe2
.members
;
423 bitmap_set_bit (pe1
.members
, v1
);
427 // If there are no uses of either operand, do not register.
428 if (has_zero_uses (op1
) || has_zero_uses (op2
))
430 // Neither name has an entry, simply create op1 as slice of op2.
431 pe2
.code
= bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2
)));
432 if (pe2
.code
== VREL_VARYING
)
435 pe2
.members
= BITMAP_ALLOC (&m_bitmaps
);
436 bitmap_set_bit (pe2
.members
, v2
);
439 pe1
.members
= pe2
.members
;
440 bitmap_set_bit (pe1
.members
, v1
);
444 // Return the set of partial equivalences associated with NAME. The bitmap
445 // will be NULL if there are none.
448 equiv_oracle::partial_equiv_set (tree name
)
450 int v
= SSA_NAME_VERSION (name
);
451 if (v
>= (int)m_partial
.length ())
453 return &m_partial
[v
];
456 // Query if there is a partial equivalence between SSA1 and SSA2. Return
457 // VREL_VARYING if there is not one. If BASE is non-null, return the base
458 // ssa-name this is a slice of.
461 equiv_oracle::partial_equiv (tree ssa1
, tree ssa2
, tree
*base
) const
463 int v1
= SSA_NAME_VERSION (ssa1
);
464 int v2
= SSA_NAME_VERSION (ssa2
);
466 if (v1
>= (int)m_partial
.length () || v2
>= (int)m_partial
.length ())
469 const pe_slice
&pe1
= m_partial
[v1
];
470 const pe_slice
&pe2
= m_partial
[v2
];
471 if (pe1
.members
&& pe2
.members
== pe1
.members
)
474 *base
= pe1
.ssa_base
;
475 return pe_min (pe1
.code
, pe2
.code
);
481 // Find and return the equivalency set for SSA along the dominators of BB.
482 // This is the external API.
485 equiv_oracle::equiv_set (tree ssa
, basic_block bb
)
487 // Search the dominator tree for an equivalency.
488 equiv_chain
*equiv
= find_equiv_dom (ssa
, bb
);
490 return equiv
->m_names
;
492 // Otherwise return a cached equiv set containing just this SSA.
493 unsigned v
= SSA_NAME_VERSION (ssa
);
494 if (v
>= m_self_equiv
.length ())
495 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
497 if (!m_self_equiv
[v
])
499 m_self_equiv
[v
] = BITMAP_ALLOC (&m_bitmaps
);
500 bitmap_set_bit (m_self_equiv
[v
], v
);
502 return m_self_equiv
[v
];
505 // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
508 equiv_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
510 // If the 2 ssa names share the same equiv set, they are equal.
511 if (equiv_set (ssa1
, bb
) == equiv_set (ssa2
, bb
))
514 // Check if there is a partial equivalence.
515 return partial_equiv (ssa1
, ssa2
);
518 // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
521 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED
, const_bitmap e1
,
524 // If the 2 ssa names share the same equiv set, they are equal.
525 if (bitmap_equal_p (e1
, e2
))
530 // If SSA has an equivalence in block BB, find and return it.
531 // Otherwise return NULL.
534 equiv_oracle::find_equiv_block (unsigned ssa
, int bb
) const
536 if (bb
>= (int)m_equiv
.length () || !m_equiv
[bb
])
539 return m_equiv
[bb
]->find (ssa
);
542 // Starting at block BB, walk the dominator chain looking for the nearest
543 // equivalence set containing NAME.
546 equiv_oracle::find_equiv_dom (tree name
, basic_block bb
) const
548 unsigned v
= SSA_NAME_VERSION (name
);
549 // Short circuit looking for names which have no equivalences.
550 // Saves time looking for something which does not exist.
551 if (!bitmap_bit_p (m_equiv_set
, v
))
554 // NAME has at least once equivalence set, check to see if it has one along
555 // the dominator tree.
556 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
558 equiv_chain
*ptr
= find_equiv_block (v
, bb
->index
);
565 // Register equivalence between ssa_name V and set EQUIV in block BB,
568 equiv_oracle::register_equiv (basic_block bb
, unsigned v
, equiv_chain
*equiv
)
570 // V will have an equivalency now.
571 bitmap_set_bit (m_equiv_set
, v
);
573 // If that equiv chain is in this block, simply use it.
574 if (equiv
->m_bb
== bb
)
576 bitmap_set_bit (equiv
->m_names
, v
);
577 bitmap_set_bit (m_equiv
[bb
->index
]->m_names
, v
);
581 // Otherwise create an equivalence for this block which is a copy
582 // of equiv, the add V to the set.
583 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
584 valid_equivs (b
, equiv
->m_names
, bb
);
585 bitmap_set_bit (b
, v
);
589 // Register equivalence between set equiv_1 and equiv_2 in block BB.
590 // Return NULL if either name can be merged with the other. Otherwise
591 // return a pointer to the combined bitmap of names. This allows the
592 // caller to do any setup required for a new element.
595 equiv_oracle::register_equiv (basic_block bb
, equiv_chain
*equiv_1
,
596 equiv_chain
*equiv_2
)
598 // If equiv_1 is already in BB, use it as the combined set.
599 if (equiv_1
->m_bb
== bb
)
601 valid_equivs (equiv_1
->m_names
, equiv_2
->m_names
, bb
);
602 // Its hard to delete from a single linked list, so
603 // just clear the second one.
604 if (equiv_2
->m_bb
== bb
)
605 bitmap_clear (equiv_2
->m_names
);
607 // Ensure the new names are in the summary for BB.
608 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_1
->m_names
);
611 // If equiv_2 is in BB, use it for the combined set.
612 if (equiv_2
->m_bb
== bb
)
614 valid_equivs (equiv_2
->m_names
, equiv_1
->m_names
, bb
);
615 // Ensure the new names are in the summary.
616 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_2
->m_names
);
620 // At this point, neither equivalence is from this block.
621 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
622 valid_equivs (b
, equiv_1
->m_names
, bb
);
623 valid_equivs (b
, equiv_2
->m_names
, bb
);
627 // Create an equivalency set containing only SSA in its definition block.
628 // This is done the first time SSA is registered in an equivalency and blocks
629 // any DOM searches past the definition.
632 equiv_oracle::register_initial_def (tree ssa
)
634 if (SSA_NAME_IS_DEFAULT_DEF (ssa
))
636 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (ssa
));
637 gcc_checking_assert (bb
&& !find_equiv_dom (ssa
, bb
));
639 unsigned v
= SSA_NAME_VERSION (ssa
);
640 bitmap_set_bit (m_equiv_set
, v
);
641 bitmap equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
642 bitmap_set_bit (equiv_set
, v
);
643 add_equiv_to_block (bb
, equiv_set
);
646 // Register an equivalence between SSA1 and SSA2 in block BB.
647 // The equivalence oracle maintains a vector of equivalencies indexed by basic
648 // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
649 // a query is made as to what equivalences both names have already, and
650 // any preexisting equivalences are merged to create a single equivalence
651 // containing all the ssa_names in this basic block.
654 equiv_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
657 // Process partial equivalencies.
658 if (relation_partial_equiv_p (k
))
660 add_partial_equiv (k
, ssa1
, ssa2
);
663 // Only handle equality relations.
667 unsigned v1
= SSA_NAME_VERSION (ssa1
);
668 unsigned v2
= SSA_NAME_VERSION (ssa2
);
670 // If this is the first time an ssa_name has an equivalency registered
671 // create a self-equivalency record in the def block.
672 if (!bitmap_bit_p (m_equiv_set
, v1
))
673 register_initial_def (ssa1
);
674 if (!bitmap_bit_p (m_equiv_set
, v2
))
675 register_initial_def (ssa2
);
677 equiv_chain
*equiv_1
= find_equiv_dom (ssa1
, bb
);
678 equiv_chain
*equiv_2
= find_equiv_dom (ssa2
, bb
);
680 // Check if they are the same set
681 if (equiv_1
&& equiv_1
== equiv_2
)
686 // Case where we have 2 SSA_NAMEs that are not in any set.
687 if (!equiv_1
&& !equiv_2
)
689 bitmap_set_bit (m_equiv_set
, v1
);
690 bitmap_set_bit (m_equiv_set
, v2
);
692 equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
693 bitmap_set_bit (equiv_set
, v1
);
694 bitmap_set_bit (equiv_set
, v2
);
696 else if (!equiv_1
&& equiv_2
)
697 equiv_set
= register_equiv (bb
, v1
, equiv_2
);
698 else if (equiv_1
&& !equiv_2
)
699 equiv_set
= register_equiv (bb
, v2
, equiv_1
);
701 equiv_set
= register_equiv (bb
, equiv_1
, equiv_2
);
703 // A non-null return is a bitmap that is to be added to the current
704 // block as a new equivalence.
708 add_equiv_to_block (bb
, equiv_set
);
711 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
712 // Note the internal caller is responsible for allocating EQUIV_SET properly.
715 equiv_oracle::add_equiv_to_block (basic_block bb
, bitmap equiv_set
)
719 // Check if this is the first time a block has an equivalence added.
720 // and create a header block. And set the summary for this block.
722 if (!m_equiv
[bb
->index
])
724 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
725 sizeof (equiv_chain
));
726 ptr
->m_names
= BITMAP_ALLOC (&m_bitmaps
);
727 bitmap_copy (ptr
->m_names
, equiv_set
);
730 m_equiv
[bb
->index
] = ptr
;
733 // Now create the element for this equiv set and initialize it.
734 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
, sizeof (equiv_chain
));
735 ptr
->m_names
= equiv_set
;
737 gcc_checking_assert (bb
->index
< (int)m_equiv
.length ());
738 ptr
->m_next
= m_equiv
[bb
->index
]->m_next
;
739 m_equiv
[bb
->index
]->m_next
= ptr
;
740 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_set
);
743 // Make sure the BB vector is big enough and grow it if needed.
746 equiv_oracle::limit_check (basic_block bb
)
748 int i
= (bb
) ? bb
->index
: last_basic_block_for_fn (cfun
);
749 if (i
>= (int)m_equiv
.length ())
750 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
753 // Dump the equivalence sets in BB to file F.
756 equiv_oracle::dump (FILE *f
, basic_block bb
) const
758 if (bb
->index
>= (int)m_equiv
.length ())
760 // Process equivalences.
761 if (m_equiv
[bb
->index
])
763 equiv_chain
*ptr
= m_equiv
[bb
->index
]->m_next
;
764 for (; ptr
; ptr
= ptr
->m_next
)
767 // Look for partial equivalences defined in this block..
768 for (unsigned i
= 0; i
< num_ssa_names
; i
++)
770 tree name
= ssa_name (i
);
771 if (!gimple_range_ssa_p (name
) || !SSA_NAME_DEF_STMT (name
))
773 if (i
>= m_partial
.length ())
775 tree base
= m_partial
[i
].ssa_base
;
776 if (base
&& name
!= base
&& gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
)
778 relation_kind k
= partial_equiv (name
, base
);
779 if (k
!= VREL_VARYING
)
781 value_relation
vr (k
, name
, base
);
782 fprintf (f
, "Partial equiv ");
790 // Dump all equivalence sets known to the oracle.
793 equiv_oracle::dump (FILE *f
) const
795 fprintf (f
, "Equivalency dump\n");
796 for (unsigned i
= 0; i
< m_equiv
.length (); i
++)
797 if (m_equiv
[i
] && BASIC_BLOCK_FOR_FN (cfun
, i
))
799 fprintf (f
, "BB%d\n", i
);
800 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
805 // --------------------------------------------------------------------------
806 // Negate the current relation.
809 value_relation::negate ()
811 related
= relation_negate (related
);
814 // Perform an intersection between 2 relations. *this &&= p.
817 value_relation::intersect (value_relation
&p
)
819 // Save previous value
820 relation_kind old
= related
;
822 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
823 related
= relation_intersect (kind (), p
.kind ());
824 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
825 related
= relation_intersect (kind (), relation_swap (p
.kind ()));
829 return old
!= related
;
832 // Perform a union between 2 relations. *this ||= p.
835 value_relation::union_ (value_relation
&p
)
837 // Save previous value
838 relation_kind old
= related
;
840 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
841 related
= relation_union (kind(), p
.kind());
842 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
843 related
= relation_union (kind(), relation_swap (p
.kind ()));
847 return old
!= related
;
850 // Identify and apply any transitive relations between REL
851 // and THIS. Return true if there was a transformation.
854 value_relation::apply_transitive (const value_relation
&rel
)
856 relation_kind k
= VREL_VARYING
;
858 // Identify any common operand, and normalize the relations to
859 // the form : A < B B < C produces A < C
860 if (rel
.op1 () == name2
)
863 if (rel
.op2 () == name1
)
865 k
= relation_transitive (kind (), rel
.kind ());
866 if (k
!= VREL_VARYING
)
873 else if (rel
.op1 () == name1
)
876 if (rel
.op2 () == name2
)
878 k
= relation_transitive (relation_swap (kind ()), rel
.kind ());
879 if (k
!= VREL_VARYING
)
887 else if (rel
.op2 () == name2
)
890 if (rel
.op1 () == name1
)
892 k
= relation_transitive (kind (), relation_swap (rel
.kind ()));
893 if (k
!= VREL_VARYING
)
900 else if (rel
.op2 () == name1
)
903 if (rel
.op1 () == name2
)
905 k
= relation_transitive (relation_swap (kind ()),
906 relation_swap (rel
.kind ()));
907 if (k
!= VREL_VARYING
)
918 // Create a trio from this value relation given LHS, OP1 and OP2.
921 value_relation::create_trio (tree lhs
, tree op1
, tree op2
)
924 if (lhs
== name1
&& op1
== name2
)
926 else if (lhs
== name2
&& op1
== name1
)
927 lhs_1
= relation_swap (related
);
929 lhs_1
= VREL_VARYING
;
932 if (lhs
== name1
&& op2
== name2
)
934 else if (lhs
== name2
&& op2
== name1
)
935 lhs_2
= relation_swap (related
);
937 lhs_2
= VREL_VARYING
;
940 if (op1
== name1
&& op2
== name2
)
942 else if (op1
== name2
&& op2
== name1
)
943 op_op
= relation_swap (related
);
947 op_op
= VREL_VARYING
;
949 return relation_trio (lhs_1
, lhs_2
, op_op
);
952 // Dump the relation to file F.
955 value_relation::dump (FILE *f
) const
957 if (!name1
|| !name2
)
959 fprintf (f
, "no relation registered");
963 print_generic_expr (f
, op1 (), TDF_SLIM
);
964 print_relation (f
, kind ());
965 print_generic_expr (f
, op2 (), TDF_SLIM
);
969 // This container is used to link relations in a chain.
971 class relation_chain
: public value_relation
974 relation_chain
*m_next
;
977 // ------------------------------------------------------------------------
979 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
980 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
983 relation_chain_head::find_relation (const_bitmap b1
, const_bitmap b2
) const
988 // If both b1 and b2 aren't referenced in this block, cant be a relation
989 if (!bitmap_intersect_p (m_names
, b1
) || !bitmap_intersect_p (m_names
, b2
))
992 // Search for the first relation that contains BOTH an element from B1
993 // and B2, and return that relation.
994 for (relation_chain
*ptr
= m_head
; ptr
; ptr
= ptr
->m_next
)
996 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
997 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
998 if (bitmap_bit_p (b1
, op1
) && bitmap_bit_p (b2
, op2
))
1000 if (bitmap_bit_p (b1
, op2
) && bitmap_bit_p (b2
, op1
))
1001 return relation_swap (ptr
->kind ());
1004 return VREL_VARYING
;
1007 // Instantiate a relation oracle.
1009 dom_oracle::dom_oracle ()
1011 m_relations
.create (0);
1012 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
1013 m_relation_set
= BITMAP_ALLOC (&m_bitmaps
);
1014 m_tmp
= BITMAP_ALLOC (&m_bitmaps
);
1015 m_tmp2
= BITMAP_ALLOC (&m_bitmaps
);
1018 // Destruct a relation oracle.
1020 dom_oracle::~dom_oracle ()
1022 m_relations
.release ();
1025 // Register relation K between ssa_name OP1 and OP2 on STMT.
1028 relation_oracle::register_stmt (gimple
*stmt
, relation_kind k
, tree op1
,
1031 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
1032 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
1033 gcc_checking_assert (stmt
&& gimple_bb (stmt
));
1035 // Don't register lack of a relation.
1036 if (k
== VREL_VARYING
)
1039 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1041 value_relation
vr (k
, op1
, op2
);
1042 fprintf (dump_file
, " Registering value_relation ");
1043 vr
.dump (dump_file
);
1044 fprintf (dump_file
, " (bb%d) at ", gimple_bb (stmt
)->index
);
1045 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1048 // If an equivalence is being added between a PHI and one of its arguments
1049 // make sure that that argument is not defined in the same block.
1050 // This can happen along back edges and the equivalence will not be
1051 // applicable as it would require a use before def.
1052 if (k
== VREL_EQ
&& is_a
<gphi
*> (stmt
))
1054 tree phi_def
= gimple_phi_result (stmt
);
1055 gcc_checking_assert (phi_def
== op1
|| phi_def
== op2
);
1059 if (gimple_bb (stmt
) == gimple_bb (SSA_NAME_DEF_STMT (arg
)))
1061 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1063 fprintf (dump_file
, " Not registered due to ");
1064 print_generic_expr (dump_file
, arg
, TDF_SLIM
);
1065 fprintf (dump_file
, " being defined in the same block.\n");
1070 register_relation (gimple_bb (stmt
), k
, op1
, op2
);
1073 // Register relation K between ssa_name OP1 and OP2 on edge E.
1076 relation_oracle::register_edge (edge e
, relation_kind k
, tree op1
, tree op2
)
1078 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
1079 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
1081 // Do not register lack of relation, or blocks which have more than
1082 // edge E for a predecessor.
1083 if (k
== VREL_VARYING
|| !single_pred_p (e
->dest
))
1086 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1088 value_relation
vr (k
, op1
, op2
);
1089 fprintf (dump_file
, " Registering value_relation ");
1090 vr
.dump (dump_file
);
1091 fprintf (dump_file
, " on (%d->%d)\n", e
->src
->index
, e
->dest
->index
);
1094 register_relation (e
->dest
, k
, op1
, op2
);
1097 // Register relation K between OP! and OP2 in block BB.
1098 // This creates the record and searches for existing records in the dominator
1099 // tree to merge with.
1102 dom_oracle::register_relation (basic_block bb
, relation_kind k
, tree op1
,
1105 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1106 // and no other relation makes sense.
1110 // Equivalencies are handled by the equivalence oracle.
1111 if (relation_equiv_p (k
))
1112 equiv_oracle::register_relation (bb
, k
, op1
, op2
);
1115 // if neither op1 nor op2 are in a relation before this is registered,
1116 // there will be no transitive.
1117 bool check
= bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op1
))
1118 || bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op2
));
1119 relation_chain
*ptr
= set_one_relation (bb
, k
, op1
, op2
);
1121 register_transitives (bb
, *ptr
);
1125 // Register relation K between OP! and OP2 in block BB.
1126 // This creates the record and searches for existing records in the dominator
1127 // tree to merge with. Return the record, or NULL if no record was created.
1130 dom_oracle::set_one_relation (basic_block bb
, relation_kind k
, tree op1
,
1133 gcc_checking_assert (k
!= VREL_VARYING
&& k
!= VREL_EQ
);
1135 value_relation
vr(k
, op1
, op2
);
1136 int bbi
= bb
->index
;
1138 if (bbi
>= (int)m_relations
.length())
1139 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
1141 // Summary bitmap indicating what ssa_names have relations in this BB.
1142 bitmap bm
= m_relations
[bbi
].m_names
;
1144 bm
= m_relations
[bbi
].m_names
= BITMAP_ALLOC (&m_bitmaps
);
1145 unsigned v1
= SSA_NAME_VERSION (op1
);
1146 unsigned v2
= SSA_NAME_VERSION (op2
);
1149 relation_chain
*ptr
;
1150 curr
= find_relation_block (bbi
, v1
, v2
, &ptr
);
1151 // There is an existing relation in this block, just intersect with it.
1152 if (curr
!= VREL_VARYING
)
1154 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1156 fprintf (dump_file
, " Intersecting with existing ");
1157 ptr
->dump (dump_file
);
1159 // Check into whether we can simply replace the relation rather than
1160 // intersecting it. This may help with some optimistic iterative
1161 // updating algorithms.
1162 bool new_rel
= ptr
->intersect (vr
);
1163 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1165 fprintf (dump_file
, " to produce ");
1166 ptr
->dump (dump_file
);
1167 fprintf (dump_file
, " %s.\n", new_rel
? "Updated" : "No Change");
1169 // If there was no change, return no record..
1175 if (m_relations
[bbi
].m_num_relations
>= param_relation_block_limit
)
1177 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1178 fprintf (dump_file
, " Not registered due to bb being full\n");
1181 m_relations
[bbi
].m_num_relations
++;
1182 // Check for an existing relation further up the DOM chain.
1183 // By including dominating relations, The first one found in any search
1184 // will be the aggregate of all the previous ones.
1185 curr
= find_relation_dom (bb
, v1
, v2
);
1186 if (curr
!= VREL_VARYING
)
1187 k
= relation_intersect (curr
, k
);
1189 bitmap_set_bit (bm
, v1
);
1190 bitmap_set_bit (bm
, v2
);
1191 bitmap_set_bit (m_relation_set
, v1
);
1192 bitmap_set_bit (m_relation_set
, v2
);
1194 ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1195 sizeof (relation_chain
));
1196 ptr
->set_relation (k
, op1
, op2
);
1197 ptr
->m_next
= m_relations
[bbi
].m_head
;
1198 m_relations
[bbi
].m_head
= ptr
;
1203 // Starting at ROOT_BB search the DOM tree looking for relations which
1204 // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1205 // bitmaps for op1/op2 and any of their equivalences that should also be
1209 dom_oracle::register_transitives (basic_block root_bb
,
1210 const value_relation
&relation
)
1213 // Only apply transitives to certain kinds of operations.
1214 switch (relation
.kind ())
1225 const_bitmap equiv1
= equiv_set (relation
.op1 (), root_bb
);
1226 const_bitmap equiv2
= equiv_set (relation
.op2 (), root_bb
);
1228 for (bb
= root_bb
; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1230 int bbi
= bb
->index
;
1231 if (bbi
>= (int)m_relations
.length())
1233 const_bitmap bm
= m_relations
[bbi
].m_names
;
1236 if (!bitmap_intersect_p (bm
, equiv1
) && !bitmap_intersect_p (bm
, equiv2
))
1238 // At least one of the 2 ops has a relation in this block.
1239 relation_chain
*ptr
;
1240 for (ptr
= m_relations
[bbi
].m_head
; ptr
; ptr
= ptr
->m_next
)
1242 // In the presence of an equivalence, 2 operands may do not
1243 // naturally match. ie with equivalence a_2 == b_3
1244 // given c_1 < a_2 && b_3 < d_4
1245 // convert the second relation (b_3 < d_4) to match any
1246 // equivalences to found in the first relation.
1247 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1248 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1251 tree p1
= ptr
->op1 ();
1252 tree p2
= ptr
->op2 ();
1253 // Find which equivalence is in the first operand.
1254 if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p1
)))
1256 else if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p2
)))
1261 // Find which equivalence is in the second operand.
1262 if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p1
)))
1264 else if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p2
)))
1269 // Ignore if both NULL (not relevant relation) or the same,
1273 // Any operand not an equivalence, just take the real operand.
1275 r1
= relation
.op1 ();
1277 r2
= relation
.op2 ();
1279 value_relation
nr (relation
.kind (), r1
, r2
);
1280 if (nr
.apply_transitive (*ptr
))
1282 if (!set_one_relation (root_bb
, nr
.kind (), nr
.op1 (), nr
.op2 ()))
1284 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1286 fprintf (dump_file
, " Registering transitive relation ");
1287 nr
.dump (dump_file
);
1288 fputc ('\n', dump_file
);
1296 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1297 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1300 dom_oracle::find_relation_block (unsigned bb
, const_bitmap b1
,
1301 const_bitmap b2
) const
1303 if (bb
>= m_relations
.length())
1304 return VREL_VARYING
;
1306 return m_relations
[bb
].find_relation (b1
, b2
);
1309 // Search the DOM tree for a relation between an element of equivalency set B1
1310 // and B2, starting with block BB.
1313 dom_oracle::query_relation (basic_block bb
, const_bitmap b1
,
1317 if (bitmap_equal_p (b1
, b2
))
1320 // If either name does not occur in a relation anywhere, there isn't one.
1321 if (!bitmap_intersect_p (m_relation_set
, b1
)
1322 || !bitmap_intersect_p (m_relation_set
, b2
))
1323 return VREL_VARYING
;
1325 // Search each block in the DOM tree checking.
1326 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1328 r
= find_relation_block (bb
->index
, b1
, b2
);
1329 if (r
!= VREL_VARYING
)
1332 return VREL_VARYING
;
1336 // Find a relation in block BB between ssa version V1 and V2. If a relation
1337 // is found, return a pointer to the chain object in OBJ.
1340 dom_oracle::find_relation_block (int bb
, unsigned v1
, unsigned v2
,
1341 relation_chain
**obj
) const
1343 if (bb
>= (int)m_relations
.length())
1344 return VREL_VARYING
;
1346 const_bitmap bm
= m_relations
[bb
].m_names
;
1348 return VREL_VARYING
;
1350 // If both b1 and b2 aren't referenced in this block, cant be a relation
1351 if (!bitmap_bit_p (bm
, v1
) || !bitmap_bit_p (bm
, v2
))
1352 return VREL_VARYING
;
1354 relation_chain
*ptr
;
1355 for (ptr
= m_relations
[bb
].m_head
; ptr
; ptr
= ptr
->m_next
)
1357 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
1358 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
1359 if (v1
== op1
&& v2
== op2
)
1363 return ptr
->kind ();
1365 if (v1
== op2
&& v2
== op1
)
1369 return relation_swap (ptr
->kind ());
1373 return VREL_VARYING
;
1376 // Find a relation between SSA version V1 and V2 in the dominator tree
1377 // starting with block BB
1380 dom_oracle::find_relation_dom (basic_block bb
, unsigned v1
, unsigned v2
) const
1383 // IF either name does not occur in a relation anywhere, there isn't one.
1384 if (!bitmap_bit_p (m_relation_set
, v1
) || !bitmap_bit_p (m_relation_set
, v2
))
1385 return VREL_VARYING
;
1387 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1389 r
= find_relation_block (bb
->index
, v1
, v2
);
1390 if (r
!= VREL_VARYING
)
1393 return VREL_VARYING
;
1397 // Query if there is a relation between SSA1 and SS2 in block BB or a
1401 dom_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1404 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1405 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1409 // If v1 or v2 do not have any relations or equivalences, a partial
1410 // equivalence is the only possibility.
1411 if ((!bitmap_bit_p (m_relation_set
, v1
) && !has_equiv_p (v1
))
1412 || (!bitmap_bit_p (m_relation_set
, v2
) && !has_equiv_p (v2
)))
1413 return partial_equiv (ssa1
, ssa2
);
1415 // Check for equivalence first. They must be in each equivalency set.
1416 const_bitmap equiv1
= equiv_set (ssa1
, bb
);
1417 const_bitmap equiv2
= equiv_set (ssa2
, bb
);
1418 if (bitmap_bit_p (equiv1
, v2
) && bitmap_bit_p (equiv2
, v1
))
1421 kind
= partial_equiv (ssa1
, ssa2
);
1422 if (kind
!= VREL_VARYING
)
1425 // Initially look for a direct relationship and just return that.
1426 kind
= find_relation_dom (bb
, v1
, v2
);
1427 if (kind
!= VREL_VARYING
)
1430 // Query using the equivalence sets.
1431 kind
= query_relation (bb
, equiv1
, equiv2
);
1435 // Dump all the relations in block BB to file F.
1438 dom_oracle::dump (FILE *f
, basic_block bb
) const
1440 equiv_oracle::dump (f
,bb
);
1442 if (bb
->index
>= (int)m_relations
.length ())
1444 if (!m_relations
[bb
->index
].m_names
)
1447 relation_chain
*ptr
= m_relations
[bb
->index
].m_head
;
1448 for (; ptr
; ptr
= ptr
->m_next
)
1450 fprintf (f
, "Relational : ");
1456 // Dump all the relations known to file F.
1459 dom_oracle::dump (FILE *f
) const
1461 fprintf (f
, "Relation dump\n");
1462 for (unsigned i
= 0; i
< m_relations
.length (); i
++)
1463 if (BASIC_BLOCK_FOR_FN (cfun
, i
))
1465 fprintf (f
, "BB%d\n", i
);
1466 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
1471 relation_oracle::debug () const
1476 path_oracle::path_oracle (relation_oracle
*oracle
)
1478 set_root_oracle (oracle
);
1479 bitmap_obstack_initialize (&m_bitmaps
);
1480 obstack_init (&m_chain_obstack
);
1482 // Initialize header records.
1483 m_equiv
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1484 m_equiv
.m_bb
= NULL
;
1485 m_equiv
.m_next
= NULL
;
1486 m_relations
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1487 m_relations
.m_head
= NULL
;
1488 m_killed_defs
= BITMAP_ALLOC (&m_bitmaps
);
1491 path_oracle::~path_oracle ()
1493 obstack_free (&m_chain_obstack
, NULL
);
1494 bitmap_obstack_release (&m_bitmaps
);
1497 // Return the equiv set for SSA, and if there isn't one, check for equivs
1498 // starting in block BB.
1501 path_oracle::equiv_set (tree ssa
, basic_block bb
)
1503 // Check the list first.
1504 equiv_chain
*ptr
= m_equiv
.find (SSA_NAME_VERSION (ssa
));
1506 return ptr
->m_names
;
1508 // Otherwise defer to the root oracle.
1510 return m_root
->equiv_set (ssa
, bb
);
1512 // Allocate a throw away bitmap if there isn't a root oracle.
1513 bitmap tmp
= BITMAP_ALLOC (&m_bitmaps
);
1514 bitmap_set_bit (tmp
, SSA_NAME_VERSION (ssa
));
1518 // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1522 path_oracle::register_equiv (basic_block bb
, tree ssa1
, tree ssa2
)
1524 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1525 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1527 // Check if they are the same set, if so, we're done.
1528 if (bitmap_equal_p (equiv_1
, equiv_2
))
1531 // Don't mess around, simply create a new record and insert it first.
1532 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1533 valid_equivs (b
, equiv_1
, bb
);
1534 valid_equivs (b
, equiv_2
, bb
);
1536 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1537 sizeof (equiv_chain
));
1540 ptr
->m_next
= m_equiv
.m_next
;
1541 m_equiv
.m_next
= ptr
;
1542 bitmap_ior_into (m_equiv
.m_names
, b
);
1545 // Register killing definition of an SSA_NAME.
1548 path_oracle::killing_def (tree ssa
)
1550 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1552 fprintf (dump_file
, " Registering killing_def (path_oracle) ");
1553 print_generic_expr (dump_file
, ssa
, TDF_SLIM
);
1554 fprintf (dump_file
, "\n");
1557 unsigned v
= SSA_NAME_VERSION (ssa
);
1559 bitmap_set_bit (m_killed_defs
, v
);
1560 bitmap_set_bit (m_equiv
.m_names
, v
);
1562 // Now add an equivalency with itself so we don't look to the root oracle.
1563 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1564 bitmap_set_bit (b
, v
);
1565 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1566 sizeof (equiv_chain
));
1569 ptr
->m_next
= m_equiv
.m_next
;
1570 m_equiv
.m_next
= ptr
;
1572 // Walk the relation list and remove SSA from any relations.
1573 if (!bitmap_bit_p (m_relations
.m_names
, v
))
1576 bitmap_clear_bit (m_relations
.m_names
, v
);
1577 relation_chain
**prev
= &(m_relations
.m_head
);
1578 relation_chain
*next
= NULL
;
1579 for (relation_chain
*ptr
= m_relations
.m_head
; ptr
; ptr
= next
)
1581 gcc_checking_assert (*prev
== ptr
);
1583 if (SSA_NAME_VERSION (ptr
->op1 ()) == v
1584 || SSA_NAME_VERSION (ptr
->op2 ()) == v
)
1585 *prev
= ptr
->m_next
;
1587 prev
= &(ptr
->m_next
);
1591 // Register relation K between SSA1 and SSA2, resolving unknowns by
1592 // querying from BB.
1595 path_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
1598 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1599 // and no other relation makes sense.
1603 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1605 value_relation
vr (k
, ssa1
, ssa2
);
1606 fprintf (dump_file
, " Registering value_relation (path_oracle) ");
1607 vr
.dump (dump_file
);
1608 fprintf (dump_file
, " (root: bb%d)\n", bb
->index
);
1611 relation_kind curr
= query_relation (bb
, ssa1
, ssa2
);
1612 if (curr
!= VREL_VARYING
)
1613 k
= relation_intersect (curr
, k
);
1617 register_equiv (bb
, ssa1
, ssa2
);
1621 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa1
));
1622 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa2
));
1623 relation_chain
*ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1624 sizeof (relation_chain
));
1625 ptr
->set_relation (k
, ssa1
, ssa2
);
1626 ptr
->m_next
= m_relations
.m_head
;
1627 m_relations
.m_head
= ptr
;
1630 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1631 // starting at block BB.
1634 path_oracle::query_relation (basic_block bb
, const_bitmap b1
, const_bitmap b2
)
1636 if (bitmap_equal_p (b1
, b2
))
1639 relation_kind k
= m_relations
.find_relation (b1
, b2
);
1641 // Do not look at the root oracle for names that have been killed
1643 if (bitmap_intersect_p (m_killed_defs
, b1
)
1644 || bitmap_intersect_p (m_killed_defs
, b2
))
1647 if (k
== VREL_VARYING
&& m_root
)
1648 k
= m_root
->query_relation (bb
, b1
, b2
);
1653 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1654 // starting at block BB.
1657 path_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1659 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1660 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1665 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1666 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1667 if (bitmap_bit_p (equiv_1
, v2
) && bitmap_bit_p (equiv_2
, v1
))
1670 return query_relation (bb
, equiv_1
, equiv_2
);
1673 // Reset any relations registered on this path. ORACLE is the root
1677 path_oracle::reset_path (relation_oracle
*oracle
)
1679 set_root_oracle (oracle
);
1680 m_equiv
.m_next
= NULL
;
1681 bitmap_clear (m_equiv
.m_names
);
1682 m_relations
.m_head
= NULL
;
1683 bitmap_clear (m_relations
.m_names
);
1684 bitmap_clear (m_killed_defs
);
1687 // Dump relation in basic block... Do nothing here.
1690 path_oracle::dump (FILE *, basic_block
) const
1694 // Dump the relations and equivalencies found in the path.
1697 path_oracle::dump (FILE *f
) const
1699 equiv_chain
*ptr
= m_equiv
.m_next
;
1700 relation_chain
*ptr2
= m_relations
.m_head
;
1703 fprintf (f
, "\npath_oracle:\n");
1705 for (; ptr
; ptr
= ptr
->m_next
)
1708 for (; ptr2
; ptr2
= ptr2
->m_next
)
1710 fprintf (f
, "Relational : ");
1716 // ------------------------------------------------------------------------
1717 // EQUIV iterator. Although we have bitmap iterators, don't expose that it
1718 // is currently a bitmap. Use an export iterator to hide future changes.
1720 // Construct a basic iterator over an equivalence bitmap.
1722 equiv_relation_iterator::equiv_relation_iterator (relation_oracle
*oracle
,
1723 basic_block bb
, tree name
,
1724 bool full
, bool partial
)
1728 m_pe
= partial
? oracle
->partial_equiv_set (name
) : NULL
;
1731 m_bm
= oracle
->equiv_set (name
, bb
);
1733 m_bm
= m_pe
->members
;
1735 bmp_iter_set_init (&m_bi
, m_bm
, 1, &m_y
);
1738 // Move to the next export bitmap spot.
1741 equiv_relation_iterator::next ()
1743 bmp_iter_next (&m_bi
, &m_y
);
1746 // Fetch the name of the next export in the export list. Return NULL if
1747 // iteration is done.
1750 equiv_relation_iterator::get_name (relation_kind
*rel
)
1755 while (bmp_iter_set (&m_bi
, &m_y
))
1757 // Do not return self.
1758 tree t
= ssa_name (m_y
);
1759 if (t
&& t
!= m_name
)
1761 relation_kind k
= VREL_EQ
;
1762 if (m_pe
&& m_bm
== m_pe
->members
)
1764 const pe_slice
*equiv_pe
= m_oracle
->partial_equiv_set (t
);
1765 if (equiv_pe
&& equiv_pe
->members
== m_pe
->members
)
1766 k
= pe_min (m_pe
->code
, equiv_pe
->code
);
1770 if (relation_equiv_p (k
))
1780 // Process partial equivs after full equivs if both were requested.
1781 if (m_pe
&& m_bm
!= m_pe
->members
)
1783 m_bm
= m_pe
->members
;
1786 // Recursively call back to process First PE.
1787 bmp_iter_set_init (&m_bi
, m_bm
, 1, &m_y
);
1788 return get_name (rel
);
1795 #include "selftest.h"
1802 // rr_*_table tables use unsigned char rather than relation_kind.
1803 ASSERT_LT (VREL_LAST
, UCHAR_MAX
);
1804 // Verify commutativity of relation_intersect and relation_union.
1805 for (relation_kind r1
= VREL_VARYING
; r1
< VREL_PE8
;
1806 r1
= relation_kind (r1
+ 1))
1807 for (relation_kind r2
= VREL_VARYING
; r2
< VREL_PE8
;
1808 r2
= relation_kind (r2
+ 1))
1810 ASSERT_EQ (relation_intersect (r1
, r2
), relation_intersect (r2
, r1
));
1811 ASSERT_EQ (relation_union (r1
, r2
), relation_union (r2
, r1
));
1815 } // namespace selftest
1817 #endif // CHECKING_P