1 /* Header file for the value range relational processing.
2 Copyright (C) 2020-2023 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 // This vector maps a relation to the equivalent tree code.
188 static const tree_code relation_to_code
[VREL_LAST
] = {
189 ERROR_MARK
, ERROR_MARK
, LT_EXPR
, LE_EXPR
, GT_EXPR
, GE_EXPR
, EQ_EXPR
,
192 // This routine validates that a relation can be applied to a specific set of
193 // ranges. In particular, floating point x == x may not be true if the NaN bit
194 // is set in the range. Symbolically the oracle will determine x == x,
195 // but specific range instances may override this.
196 // To verify, attempt to fold the relation using the supplied ranges.
197 // One would expect [1,1] to be returned, anything else means there is something
198 // in the range preventing the relation from applying.
199 // If there is no mechanism to verify, assume the relation is acceptable.
202 relation_oracle::validate_relation (relation_kind rel
, vrange
&op1
, vrange
&op2
)
204 // If there is no mapping to a tree code, leave the relation as is.
205 tree_code code
= relation_to_code
[rel
];
206 if (code
== ERROR_MARK
)
209 // Undefined ranges cannot be checked either.
210 if (op1
.undefined_p () || op2
.undefined_p ())
213 tree t1
= op1
.type ();
214 tree t2
= op2
.type ();
216 // If the range types are not compatible, no relation can exist.
217 if (!range_compatible_p (t1
, t2
))
220 // If there is no handler, leave the relation as is.
221 range_op_handler
handler (code
);
225 // If the relation cannot be folded for any reason, leave as is.
226 Value_Range
result (boolean_type_node
);
227 if (!handler
.fold_range (result
, boolean_type_node
, op1
, op2
,
228 relation_trio::op1_op2 (rel
)))
231 // The expression op1 REL op2 using REL should fold to [1,1].
232 // Any other result means the relation is not verified to be true.
233 if (result
.varying_p () || result
.zero_p ())
239 // If no range is available, create a varying range for each SSA name and
243 relation_oracle::validate_relation (relation_kind rel
, tree ssa1
, tree ssa2
)
245 Value_Range op1
, op2
;
246 op1
.set_varying (TREE_TYPE (ssa1
));
247 op2
.set_varying (TREE_TYPE (ssa2
));
249 return validate_relation (rel
, op1
, op2
);
252 // Given an equivalence set EQUIV, set all the bits in B that are still valid
253 // members of EQUIV in basic block BB.
256 relation_oracle::valid_equivs (bitmap b
, const_bitmap equivs
, basic_block bb
)
260 EXECUTE_IF_SET_IN_BITMAP (equivs
, 0, i
, bi
)
262 tree ssa
= ssa_name (i
);
263 const_bitmap ssa_equiv
= equiv_set (ssa
, bb
);
264 if (ssa_equiv
== equivs
)
265 bitmap_set_bit (b
, i
);
269 // -------------------------------------------------------------------------
271 // The very first element in the m_equiv chain is actually just a summary
272 // element in which the m_names bitmap is used to indicate that an ssa_name
273 // has an equivalence set in this block.
274 // This allows for much faster traversal of the DOM chain, as a search for
275 // SSA_NAME simply requires walking the DOM chain until a block is found
276 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
277 // that block. No previous lists need be searched.
279 // If SSA has an equivalence in this list, find and return it.
280 // Otherwise return NULL.
283 equiv_chain::find (unsigned ssa
)
285 equiv_chain
*ptr
= NULL
;
286 // If there are equiv sets and SSA is in one in this list, find it.
287 // Otherwise return NULL.
288 if (bitmap_bit_p (m_names
, ssa
))
290 for (ptr
= m_next
; ptr
; ptr
= ptr
->m_next
)
291 if (bitmap_bit_p (ptr
->m_names
, ssa
))
297 // Dump the names in this equivalence set.
300 equiv_chain::dump (FILE *f
) const
305 if (!m_names
|| bitmap_empty_p (m_names
))
307 fprintf (f
, "Equivalence set : [");
309 EXECUTE_IF_SET_IN_BITMAP (m_names
, 0, i
, bi
)
315 print_generic_expr (f
, ssa_name (i
), TDF_SLIM
);
321 // Instantiate an equivalency oracle.
323 equiv_oracle::equiv_oracle ()
325 bitmap_obstack_initialize (&m_bitmaps
);
327 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
328 m_equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
329 obstack_init (&m_chain_obstack
);
330 m_self_equiv
.create (0);
331 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
332 m_partial
.create (0);
333 m_partial
.safe_grow_cleared (num_ssa_names
+ 1);
336 // Destruct an equivalency oracle.
338 equiv_oracle::~equiv_oracle ()
340 m_partial
.release ();
341 m_self_equiv
.release ();
342 obstack_free (&m_chain_obstack
, NULL
);
344 bitmap_obstack_release (&m_bitmaps
);
347 // Add a partial equivalence R between OP1 and OP2.
350 equiv_oracle::add_partial_equiv (relation_kind r
, tree op1
, tree op2
)
352 int v1
= SSA_NAME_VERSION (op1
);
353 int v2
= SSA_NAME_VERSION (op2
);
354 int prec2
= TYPE_PRECISION (TREE_TYPE (op2
));
355 int bits
= pe_to_bits (r
);
356 gcc_checking_assert (bits
&& prec2
>= bits
);
358 if (v1
>= (int)m_partial
.length () || v2
>= (int)m_partial
.length ())
359 m_partial
.safe_grow_cleared (num_ssa_names
+ 1);
360 gcc_checking_assert (v1
< (int)m_partial
.length ()
361 && v2
< (int)m_partial
.length ());
363 pe_slice
&pe1
= m_partial
[v1
];
364 pe_slice
&pe2
= m_partial
[v2
];
368 // If the definition pe1 already has an entry, either the stmt is
369 // being re-evaluated, or the def was used before being registered.
370 // In either case, if PE2 has an entry, we simply do nothing.
373 // PE1 is the LHS and already has members, so everything in the set
374 // should be a slice of PE2 rather than PE1.
375 pe2
.code
= pe_min (r
, pe1
.code
);
377 pe2
.members
= pe1
.members
;
380 EXECUTE_IF_SET_IN_BITMAP (pe1
.members
, 0, x
, bi
)
382 m_partial
[x
].ssa_base
= op2
;
383 m_partial
[x
].code
= pe_min (m_partial
[x
].code
, pe2
.code
);
385 bitmap_set_bit (pe1
.members
, v2
);
390 pe1
.ssa_base
= pe2
.ssa_base
;
391 // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
392 // more than an 8 bit equivalence here, so choose MIN value.
393 pe1
.code
= pe_min (r
, pe2
.code
);
394 pe1
.members
= pe2
.members
;
395 bitmap_set_bit (pe1
.members
, v1
);
399 // Neither name has an entry, simply create op1 as slice of op2.
400 pe2
.code
= bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2
)));
401 if (pe2
.code
== VREL_VARYING
)
404 pe2
.members
= BITMAP_ALLOC (&m_bitmaps
);
405 bitmap_set_bit (pe2
.members
, v2
);
408 pe1
.members
= pe2
.members
;
409 bitmap_set_bit (pe1
.members
, v1
);
413 // Return the set of partial equivalences associated with NAME. The bitmap
414 // will be NULL if there are none.
417 equiv_oracle::partial_equiv_set (tree name
)
419 int v
= SSA_NAME_VERSION (name
);
420 if (v
>= (int)m_partial
.length ())
422 return &m_partial
[v
];
425 // Query if there is a partial equivalence between SSA1 and SSA2. Return
426 // VREL_VARYING if there is not one. If BASE is non-null, return the base
427 // ssa-name this is a slice of.
430 equiv_oracle::partial_equiv (tree ssa1
, tree ssa2
, tree
*base
) const
432 int v1
= SSA_NAME_VERSION (ssa1
);
433 int v2
= SSA_NAME_VERSION (ssa2
);
435 if (v1
>= (int)m_partial
.length () || v2
>= (int)m_partial
.length ())
438 const pe_slice
&pe1
= m_partial
[v1
];
439 const pe_slice
&pe2
= m_partial
[v2
];
440 if (pe1
.members
&& pe2
.members
== pe1
.members
)
443 *base
= pe1
.ssa_base
;
444 return pe_min (pe1
.code
, pe2
.code
);
450 // Find and return the equivalency set for SSA along the dominators of BB.
451 // This is the external API.
454 equiv_oracle::equiv_set (tree ssa
, basic_block bb
)
456 // Search the dominator tree for an equivalency.
457 equiv_chain
*equiv
= find_equiv_dom (ssa
, bb
);
459 return equiv
->m_names
;
461 // Otherwise return a cached equiv set containing just this SSA.
462 unsigned v
= SSA_NAME_VERSION (ssa
);
463 if (v
>= m_self_equiv
.length ())
464 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
466 if (!m_self_equiv
[v
])
468 m_self_equiv
[v
] = BITMAP_ALLOC (&m_bitmaps
);
469 bitmap_set_bit (m_self_equiv
[v
], v
);
471 return m_self_equiv
[v
];
474 // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
477 equiv_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
479 // If the 2 ssa names share the same equiv set, they are equal.
480 if (equiv_set (ssa1
, bb
) == equiv_set (ssa2
, bb
))
483 // Check if there is a partial equivalence.
484 return partial_equiv (ssa1
, ssa2
);
487 // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
490 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED
, const_bitmap e1
,
493 // If the 2 ssa names share the same equiv set, they are equal.
494 if (bitmap_equal_p (e1
, e2
))
499 // If SSA has an equivalence in block BB, find and return it.
500 // Otherwise return NULL.
503 equiv_oracle::find_equiv_block (unsigned ssa
, int bb
) const
505 if (bb
>= (int)m_equiv
.length () || !m_equiv
[bb
])
508 return m_equiv
[bb
]->find (ssa
);
511 // Starting at block BB, walk the dominator chain looking for the nearest
512 // equivalence set containing NAME.
515 equiv_oracle::find_equiv_dom (tree name
, basic_block bb
) const
517 unsigned v
= SSA_NAME_VERSION (name
);
518 // Short circuit looking for names which have no equivalences.
519 // Saves time looking for something which does not exist.
520 if (!bitmap_bit_p (m_equiv_set
, v
))
523 // NAME has at least once equivalence set, check to see if it has one along
524 // the dominator tree.
525 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
527 equiv_chain
*ptr
= find_equiv_block (v
, bb
->index
);
534 // Register equivalence between ssa_name V and set EQUIV in block BB,
537 equiv_oracle::register_equiv (basic_block bb
, unsigned v
, equiv_chain
*equiv
)
539 // V will have an equivalency now.
540 bitmap_set_bit (m_equiv_set
, v
);
542 // If that equiv chain is in this block, simply use it.
543 if (equiv
->m_bb
== bb
)
545 bitmap_set_bit (equiv
->m_names
, v
);
546 bitmap_set_bit (m_equiv
[bb
->index
]->m_names
, v
);
550 // Otherwise create an equivalence for this block which is a copy
551 // of equiv, the add V to the set.
552 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
553 valid_equivs (b
, equiv
->m_names
, bb
);
554 bitmap_set_bit (b
, v
);
558 // Register equivalence between set equiv_1 and equiv_2 in block BB.
559 // Return NULL if either name can be merged with the other. Otherwise
560 // return a pointer to the combined bitmap of names. This allows the
561 // caller to do any setup required for a new element.
564 equiv_oracle::register_equiv (basic_block bb
, equiv_chain
*equiv_1
,
565 equiv_chain
*equiv_2
)
567 // If equiv_1 is already in BB, use it as the combined set.
568 if (equiv_1
->m_bb
== bb
)
570 valid_equivs (equiv_1
->m_names
, equiv_2
->m_names
, bb
);
571 // Its hard to delete from a single linked list, so
572 // just clear the second one.
573 if (equiv_2
->m_bb
== bb
)
574 bitmap_clear (equiv_2
->m_names
);
576 // Ensure the new names are in the summary for BB.
577 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_1
->m_names
);
580 // If equiv_2 is in BB, use it for the combined set.
581 if (equiv_2
->m_bb
== bb
)
583 valid_equivs (equiv_2
->m_names
, equiv_1
->m_names
, bb
);
584 // Ensure the new names are in the summary.
585 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_2
->m_names
);
589 // At this point, neither equivalence is from this block.
590 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
591 valid_equivs (b
, equiv_1
->m_names
, bb
);
592 valid_equivs (b
, equiv_2
->m_names
, bb
);
596 // Create an equivalency set containing only SSA in its definition block.
597 // This is done the first time SSA is registered in an equivalency and blocks
598 // any DOM searches past the definition.
601 equiv_oracle::register_initial_def (tree ssa
)
603 if (SSA_NAME_IS_DEFAULT_DEF (ssa
))
605 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (ssa
));
606 gcc_checking_assert (bb
&& !find_equiv_dom (ssa
, bb
));
608 unsigned v
= SSA_NAME_VERSION (ssa
);
609 bitmap_set_bit (m_equiv_set
, v
);
610 bitmap equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
611 bitmap_set_bit (equiv_set
, v
);
612 add_equiv_to_block (bb
, equiv_set
);
615 // Register an equivalence between SSA1 and SSA2 in block BB.
616 // The equivalence oracle maintains a vector of equivalencies indexed by basic
617 // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
618 // a query is made as to what equivalences both names have already, and
619 // any preexisting equivalences are merged to create a single equivalence
620 // containing all the ssa_names in this basic block.
623 equiv_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
626 // Process partial equivalencies.
627 if (relation_partial_equiv_p (k
))
629 add_partial_equiv (k
, ssa1
, ssa2
);
632 // Only handle equality relations.
636 unsigned v1
= SSA_NAME_VERSION (ssa1
);
637 unsigned v2
= SSA_NAME_VERSION (ssa2
);
639 // If this is the first time an ssa_name has an equivalency registered
640 // create a self-equivalency record in the def block.
641 if (!bitmap_bit_p (m_equiv_set
, v1
))
642 register_initial_def (ssa1
);
643 if (!bitmap_bit_p (m_equiv_set
, v2
))
644 register_initial_def (ssa2
);
646 equiv_chain
*equiv_1
= find_equiv_dom (ssa1
, bb
);
647 equiv_chain
*equiv_2
= find_equiv_dom (ssa2
, bb
);
649 // Check if they are the same set
650 if (equiv_1
&& equiv_1
== equiv_2
)
655 // Case where we have 2 SSA_NAMEs that are not in any set.
656 if (!equiv_1
&& !equiv_2
)
658 bitmap_set_bit (m_equiv_set
, v1
);
659 bitmap_set_bit (m_equiv_set
, v2
);
661 equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
662 bitmap_set_bit (equiv_set
, v1
);
663 bitmap_set_bit (equiv_set
, v2
);
665 else if (!equiv_1
&& equiv_2
)
666 equiv_set
= register_equiv (bb
, v1
, equiv_2
);
667 else if (equiv_1
&& !equiv_2
)
668 equiv_set
= register_equiv (bb
, v2
, equiv_1
);
670 equiv_set
= register_equiv (bb
, equiv_1
, equiv_2
);
672 // A non-null return is a bitmap that is to be added to the current
673 // block as a new equivalence.
677 add_equiv_to_block (bb
, equiv_set
);
680 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
681 // Note the internal caller is responsible for allocating EQUIV_SET properly.
684 equiv_oracle::add_equiv_to_block (basic_block bb
, bitmap equiv_set
)
688 // Check if this is the first time a block has an equivalence added.
689 // and create a header block. And set the summary for this block.
690 if (!m_equiv
[bb
->index
])
692 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
693 sizeof (equiv_chain
));
694 ptr
->m_names
= BITMAP_ALLOC (&m_bitmaps
);
695 bitmap_copy (ptr
->m_names
, equiv_set
);
698 m_equiv
[bb
->index
] = ptr
;
701 // Now create the element for this equiv set and initialize it.
702 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
, sizeof (equiv_chain
));
703 ptr
->m_names
= equiv_set
;
705 gcc_checking_assert (bb
->index
< (int)m_equiv
.length ());
706 ptr
->m_next
= m_equiv
[bb
->index
]->m_next
;
707 m_equiv
[bb
->index
]->m_next
= ptr
;
708 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_set
);
711 // Make sure the BB vector is big enough and grow it if needed.
714 equiv_oracle::limit_check (basic_block bb
)
716 int i
= (bb
) ? bb
->index
: last_basic_block_for_fn (cfun
);
717 if (i
>= (int)m_equiv
.length ())
718 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
721 // Dump the equivalence sets in BB to file F.
724 equiv_oracle::dump (FILE *f
, basic_block bb
) const
726 if (bb
->index
>= (int)m_equiv
.length ())
728 // Process equivalences.
729 if (m_equiv
[bb
->index
])
731 equiv_chain
*ptr
= m_equiv
[bb
->index
]->m_next
;
732 for (; ptr
; ptr
= ptr
->m_next
)
735 // Look for partial equivalences defined in this block..
736 for (unsigned i
= 0; i
< num_ssa_names
; i
++)
738 tree name
= ssa_name (i
);
739 if (!gimple_range_ssa_p (name
) || !SSA_NAME_DEF_STMT (name
))
741 if (i
>= m_partial
.length ())
743 tree base
= m_partial
[i
].ssa_base
;
744 if (base
&& name
!= base
&& gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
)
746 relation_kind k
= partial_equiv (name
, base
);
747 if (k
!= VREL_VARYING
)
749 value_relation
vr (k
, name
, base
);
750 fprintf (f
, "Partial equiv ");
758 // Dump all equivalence sets known to the oracle.
761 equiv_oracle::dump (FILE *f
) const
763 fprintf (f
, "Equivalency dump\n");
764 for (unsigned i
= 0; i
< m_equiv
.length (); i
++)
765 if (m_equiv
[i
] && BASIC_BLOCK_FOR_FN (cfun
, i
))
767 fprintf (f
, "BB%d\n", i
);
768 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
773 // --------------------------------------------------------------------------
774 // Negate the current relation.
777 value_relation::negate ()
779 related
= relation_negate (related
);
782 // Perform an intersection between 2 relations. *this &&= p.
785 value_relation::intersect (value_relation
&p
)
787 // Save previous value
788 relation_kind old
= related
;
790 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
791 related
= relation_intersect (kind (), p
.kind ());
792 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
793 related
= relation_intersect (kind (), relation_swap (p
.kind ()));
797 return old
!= related
;
800 // Perform a union between 2 relations. *this ||= p.
803 value_relation::union_ (value_relation
&p
)
805 // Save previous value
806 relation_kind old
= related
;
808 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
809 related
= relation_union (kind(), p
.kind());
810 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
811 related
= relation_union (kind(), relation_swap (p
.kind ()));
815 return old
!= related
;
818 // Identify and apply any transitive relations between REL
819 // and THIS. Return true if there was a transformation.
822 value_relation::apply_transitive (const value_relation
&rel
)
824 relation_kind k
= VREL_VARYING
;
826 // Identify any common operand, and normalize the relations to
827 // the form : A < B B < C produces A < C
828 if (rel
.op1 () == name2
)
831 if (rel
.op2 () == name1
)
833 k
= relation_transitive (kind (), rel
.kind ());
834 if (k
!= VREL_VARYING
)
841 else if (rel
.op1 () == name1
)
844 if (rel
.op2 () == name2
)
846 k
= relation_transitive (relation_swap (kind ()), rel
.kind ());
847 if (k
!= VREL_VARYING
)
855 else if (rel
.op2 () == name2
)
858 if (rel
.op1 () == name1
)
860 k
= relation_transitive (kind (), relation_swap (rel
.kind ()));
861 if (k
!= VREL_VARYING
)
868 else if (rel
.op2 () == name1
)
871 if (rel
.op1 () == name2
)
873 k
= relation_transitive (relation_swap (kind ()),
874 relation_swap (rel
.kind ()));
875 if (k
!= VREL_VARYING
)
886 // Create a trio from this value relation given LHS, OP1 and OP2.
889 value_relation::create_trio (tree lhs
, tree op1
, tree op2
)
892 if (lhs
== name1
&& op1
== name2
)
894 else if (lhs
== name2
&& op1
== name1
)
895 lhs_1
= relation_swap (related
);
897 lhs_1
= VREL_VARYING
;
900 if (lhs
== name1
&& op2
== name2
)
902 else if (lhs
== name2
&& op2
== name1
)
903 lhs_2
= relation_swap (related
);
905 lhs_2
= VREL_VARYING
;
908 if (op1
== name1
&& op2
== name2
)
910 else if (op1
== name2
&& op2
== name1
)
911 op_op
= relation_swap (related
);
915 op_op
= VREL_VARYING
;
917 return relation_trio (lhs_1
, lhs_2
, op_op
);
920 // Dump the relation to file F.
923 value_relation::dump (FILE *f
) const
925 if (!name1
|| !name2
)
927 fprintf (f
, "no relation registered");
931 print_generic_expr (f
, op1 (), TDF_SLIM
);
932 print_relation (f
, kind ());
933 print_generic_expr (f
, op2 (), TDF_SLIM
);
937 // This container is used to link relations in a chain.
939 class relation_chain
: public value_relation
942 relation_chain
*m_next
;
945 // ------------------------------------------------------------------------
947 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
948 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
951 relation_chain_head::find_relation (const_bitmap b1
, const_bitmap b2
) const
956 // If both b1 and b2 aren't referenced in this block, cant be a relation
957 if (!bitmap_intersect_p (m_names
, b1
) || !bitmap_intersect_p (m_names
, b2
))
960 // Search for the first relation that contains BOTH an element from B1
961 // and B2, and return that relation.
962 for (relation_chain
*ptr
= m_head
; ptr
; ptr
= ptr
->m_next
)
964 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
965 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
966 if (bitmap_bit_p (b1
, op1
) && bitmap_bit_p (b2
, op2
))
968 if (bitmap_bit_p (b1
, op2
) && bitmap_bit_p (b2
, op1
))
969 return relation_swap (ptr
->kind ());
975 // Instantiate a relation oracle.
977 dom_oracle::dom_oracle ()
979 m_relations
.create (0);
980 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
981 m_relation_set
= BITMAP_ALLOC (&m_bitmaps
);
982 m_tmp
= BITMAP_ALLOC (&m_bitmaps
);
983 m_tmp2
= BITMAP_ALLOC (&m_bitmaps
);
986 // Destruct a relation oracle.
988 dom_oracle::~dom_oracle ()
990 m_relations
.release ();
993 // Register relation K between ssa_name OP1 and OP2 on STMT.
996 relation_oracle::register_stmt (gimple
*stmt
, relation_kind k
, tree op1
,
999 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
1000 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
1001 gcc_checking_assert (stmt
&& gimple_bb (stmt
));
1003 // Don't register lack of a relation.
1004 if (k
== VREL_VARYING
)
1007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1009 value_relation
vr (k
, op1
, op2
);
1010 fprintf (dump_file
, " Registering value_relation ");
1011 vr
.dump (dump_file
);
1012 fprintf (dump_file
, " (bb%d) at ", gimple_bb (stmt
)->index
);
1013 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1016 // If an equivalence is being added between a PHI and one of its arguments
1017 // make sure that that argument is not defined in the same block.
1018 // This can happen along back edges and the equivalence will not be
1019 // applicable as it would require a use before def.
1020 if (k
== VREL_EQ
&& is_a
<gphi
*> (stmt
))
1022 tree phi_def
= gimple_phi_result (stmt
);
1023 gcc_checking_assert (phi_def
== op1
|| phi_def
== op2
);
1027 if (gimple_bb (stmt
) == gimple_bb (SSA_NAME_DEF_STMT (arg
)))
1029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1031 fprintf (dump_file
, " Not registered due to ");
1032 print_generic_expr (dump_file
, arg
, TDF_SLIM
);
1033 fprintf (dump_file
, " being defined in the same block.\n");
1038 register_relation (gimple_bb (stmt
), k
, op1
, op2
);
1041 // Register relation K between ssa_name OP1 and OP2 on edge E.
1044 relation_oracle::register_edge (edge e
, relation_kind k
, tree op1
, tree op2
)
1046 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
1047 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
1049 // Do not register lack of relation, or blocks which have more than
1050 // edge E for a predecessor.
1051 if (k
== VREL_VARYING
|| !single_pred_p (e
->dest
))
1054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1056 value_relation
vr (k
, op1
, op2
);
1057 fprintf (dump_file
, " Registering value_relation ");
1058 vr
.dump (dump_file
);
1059 fprintf (dump_file
, " on (%d->%d)\n", e
->src
->index
, e
->dest
->index
);
1062 register_relation (e
->dest
, k
, op1
, op2
);
1065 // Register relation K between OP! and OP2 in block BB.
1066 // This creates the record and searches for existing records in the dominator
1067 // tree to merge with.
1070 dom_oracle::register_relation (basic_block bb
, relation_kind k
, tree op1
,
1073 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1074 // and no other relation makes sense.
1078 // Equivalencies are handled by the equivalence oracle.
1079 if (relation_equiv_p (k
))
1080 equiv_oracle::register_relation (bb
, k
, op1
, op2
);
1083 // if neither op1 nor op2 are in a relation before this is registered,
1084 // there will be no transitive.
1085 bool check
= bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op1
))
1086 || bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op2
));
1087 relation_chain
*ptr
= set_one_relation (bb
, k
, op1
, op2
);
1089 register_transitives (bb
, *ptr
);
1093 // Register relation K between OP! and OP2 in block BB.
1094 // This creates the record and searches for existing records in the dominator
1095 // tree to merge with. Return the record, or NULL if no record was created.
1098 dom_oracle::set_one_relation (basic_block bb
, relation_kind k
, tree op1
,
1101 gcc_checking_assert (k
!= VREL_VARYING
&& k
!= VREL_EQ
);
1103 value_relation
vr(k
, op1
, op2
);
1104 int bbi
= bb
->index
;
1106 if (bbi
>= (int)m_relations
.length())
1107 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
1109 // Summary bitmap indicating what ssa_names have relations in this BB.
1110 bitmap bm
= m_relations
[bbi
].m_names
;
1112 bm
= m_relations
[bbi
].m_names
= BITMAP_ALLOC (&m_bitmaps
);
1113 unsigned v1
= SSA_NAME_VERSION (op1
);
1114 unsigned v2
= SSA_NAME_VERSION (op2
);
1117 relation_chain
*ptr
;
1118 curr
= find_relation_block (bbi
, v1
, v2
, &ptr
);
1119 // There is an existing relation in this block, just intersect with it.
1120 if (curr
!= VREL_VARYING
)
1122 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1124 fprintf (dump_file
, " Intersecting with existing ");
1125 ptr
->dump (dump_file
);
1127 // Check into whether we can simply replace the relation rather than
1128 // intersecting it. This may help with some optimistic iterative
1129 // updating algorithms.
1130 bool new_rel
= ptr
->intersect (vr
);
1131 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1133 fprintf (dump_file
, " to produce ");
1134 ptr
->dump (dump_file
);
1135 fprintf (dump_file
, " %s.\n", new_rel
? "Updated" : "No Change");
1137 // If there was no change, return no record..
1143 if (m_relations
[bbi
].m_num_relations
>= param_relation_block_limit
)
1145 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1146 fprintf (dump_file
, " Not registered due to bb being full\n");
1149 m_relations
[bbi
].m_num_relations
++;
1150 // Check for an existing relation further up the DOM chain.
1151 // By including dominating relations, The first one found in any search
1152 // will be the aggregate of all the previous ones.
1153 curr
= find_relation_dom (bb
, v1
, v2
);
1154 if (curr
!= VREL_VARYING
)
1155 k
= relation_intersect (curr
, k
);
1157 bitmap_set_bit (bm
, v1
);
1158 bitmap_set_bit (bm
, v2
);
1159 bitmap_set_bit (m_relation_set
, v1
);
1160 bitmap_set_bit (m_relation_set
, v2
);
1162 ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1163 sizeof (relation_chain
));
1164 ptr
->set_relation (k
, op1
, op2
);
1165 ptr
->m_next
= m_relations
[bbi
].m_head
;
1166 m_relations
[bbi
].m_head
= ptr
;
1171 // Starting at ROOT_BB search the DOM tree looking for relations which
1172 // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1173 // bitmaps for op1/op2 and any of their equivalences that should also be
1177 dom_oracle::register_transitives (basic_block root_bb
,
1178 const value_relation
&relation
)
1181 // Only apply transitives to certain kinds of operations.
1182 switch (relation
.kind ())
1193 const_bitmap equiv1
= equiv_set (relation
.op1 (), root_bb
);
1194 const_bitmap equiv2
= equiv_set (relation
.op2 (), root_bb
);
1196 for (bb
= root_bb
; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1198 int bbi
= bb
->index
;
1199 if (bbi
>= (int)m_relations
.length())
1201 const_bitmap bm
= m_relations
[bbi
].m_names
;
1204 if (!bitmap_intersect_p (bm
, equiv1
) && !bitmap_intersect_p (bm
, equiv2
))
1206 // At least one of the 2 ops has a relation in this block.
1207 relation_chain
*ptr
;
1208 for (ptr
= m_relations
[bbi
].m_head
; ptr
; ptr
= ptr
->m_next
)
1210 // In the presence of an equivalence, 2 operands may do not
1211 // naturally match. ie with equivalence a_2 == b_3
1212 // given c_1 < a_2 && b_3 < d_4
1213 // convert the second relation (b_3 < d_4) to match any
1214 // equivalences to found in the first relation.
1215 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1216 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1219 tree p1
= ptr
->op1 ();
1220 tree p2
= ptr
->op2 ();
1221 // Find which equivalence is in the first operand.
1222 if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p1
)))
1224 else if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p2
)))
1229 // Find which equivalence is in the second operand.
1230 if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p1
)))
1232 else if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p2
)))
1237 // Ignore if both NULL (not relevant relation) or the same,
1241 // Any operand not an equivalence, just take the real operand.
1243 r1
= relation
.op1 ();
1245 r2
= relation
.op2 ();
1247 value_relation
nr (relation
.kind (), r1
, r2
);
1248 if (nr
.apply_transitive (*ptr
))
1250 if (!set_one_relation (root_bb
, nr
.kind (), nr
.op1 (), nr
.op2 ()))
1252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1254 fprintf (dump_file
, " Registering transitive relation ");
1255 nr
.dump (dump_file
);
1256 fputc ('\n', dump_file
);
1264 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1265 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1268 dom_oracle::find_relation_block (unsigned bb
, const_bitmap b1
,
1269 const_bitmap b2
) const
1271 if (bb
>= m_relations
.length())
1272 return VREL_VARYING
;
1274 return m_relations
[bb
].find_relation (b1
, b2
);
1277 // Search the DOM tree for a relation between an element of equivalency set B1
1278 // and B2, starting with block BB.
1281 dom_oracle::query_relation (basic_block bb
, const_bitmap b1
,
1285 if (bitmap_equal_p (b1
, b2
))
1288 // If either name does not occur in a relation anywhere, there isn't one.
1289 if (!bitmap_intersect_p (m_relation_set
, b1
)
1290 || !bitmap_intersect_p (m_relation_set
, b2
))
1291 return VREL_VARYING
;
1293 // Search each block in the DOM tree checking.
1294 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1296 r
= find_relation_block (bb
->index
, b1
, b2
);
1297 if (r
!= VREL_VARYING
)
1300 return VREL_VARYING
;
1304 // Find a relation in block BB between ssa version V1 and V2. If a relation
1305 // is found, return a pointer to the chain object in OBJ.
1308 dom_oracle::find_relation_block (int bb
, unsigned v1
, unsigned v2
,
1309 relation_chain
**obj
) const
1311 if (bb
>= (int)m_relations
.length())
1312 return VREL_VARYING
;
1314 const_bitmap bm
= m_relations
[bb
].m_names
;
1316 return VREL_VARYING
;
1318 // If both b1 and b2 aren't referenced in this block, cant be a relation
1319 if (!bitmap_bit_p (bm
, v1
) || !bitmap_bit_p (bm
, v2
))
1320 return VREL_VARYING
;
1322 relation_chain
*ptr
;
1323 for (ptr
= m_relations
[bb
].m_head
; ptr
; ptr
= ptr
->m_next
)
1325 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
1326 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
1327 if (v1
== op1
&& v2
== op2
)
1331 return ptr
->kind ();
1333 if (v1
== op2
&& v2
== op1
)
1337 return relation_swap (ptr
->kind ());
1341 return VREL_VARYING
;
1344 // Find a relation between SSA version V1 and V2 in the dominator tree
1345 // starting with block BB
1348 dom_oracle::find_relation_dom (basic_block bb
, unsigned v1
, unsigned v2
) const
1351 // IF either name does not occur in a relation anywhere, there isn't one.
1352 if (!bitmap_bit_p (m_relation_set
, v1
) || !bitmap_bit_p (m_relation_set
, v2
))
1353 return VREL_VARYING
;
1355 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1357 r
= find_relation_block (bb
->index
, v1
, v2
);
1358 if (r
!= VREL_VARYING
)
1361 return VREL_VARYING
;
1365 // Query if there is a relation between SSA1 and SS2 in block BB or a
1369 dom_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1372 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1373 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1377 // If v1 or v2 do not have any relations or equivalences, a partial
1378 // equivalence is the only possibility.
1379 if ((!bitmap_bit_p (m_relation_set
, v1
) && !has_equiv_p (v1
))
1380 || (!bitmap_bit_p (m_relation_set
, v2
) && !has_equiv_p (v2
)))
1381 return partial_equiv (ssa1
, ssa2
);
1383 // Check for equivalence first. They must be in each equivalency set.
1384 const_bitmap equiv1
= equiv_set (ssa1
, bb
);
1385 const_bitmap equiv2
= equiv_set (ssa2
, bb
);
1386 if (bitmap_bit_p (equiv1
, v2
) && bitmap_bit_p (equiv2
, v1
))
1389 kind
= partial_equiv (ssa1
, ssa2
);
1390 if (kind
!= VREL_VARYING
)
1393 // Initially look for a direct relationship and just return that.
1394 kind
= find_relation_dom (bb
, v1
, v2
);
1395 if (kind
!= VREL_VARYING
)
1398 // Query using the equivalence sets.
1399 kind
= query_relation (bb
, equiv1
, equiv2
);
1403 // Dump all the relations in block BB to file F.
1406 dom_oracle::dump (FILE *f
, basic_block bb
) const
1408 equiv_oracle::dump (f
,bb
);
1410 if (bb
->index
>= (int)m_relations
.length ())
1412 if (!m_relations
[bb
->index
].m_names
)
1415 relation_chain
*ptr
= m_relations
[bb
->index
].m_head
;
1416 for (; ptr
; ptr
= ptr
->m_next
)
1418 fprintf (f
, "Relational : ");
1424 // Dump all the relations known to file F.
1427 dom_oracle::dump (FILE *f
) const
1429 fprintf (f
, "Relation dump\n");
1430 for (unsigned i
= 0; i
< m_relations
.length (); i
++)
1431 if (BASIC_BLOCK_FOR_FN (cfun
, i
))
1433 fprintf (f
, "BB%d\n", i
);
1434 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
1439 relation_oracle::debug () const
1444 path_oracle::path_oracle (relation_oracle
*oracle
)
1446 set_root_oracle (oracle
);
1447 bitmap_obstack_initialize (&m_bitmaps
);
1448 obstack_init (&m_chain_obstack
);
1450 // Initialize header records.
1451 m_equiv
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1452 m_equiv
.m_bb
= NULL
;
1453 m_equiv
.m_next
= NULL
;
1454 m_relations
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1455 m_relations
.m_head
= NULL
;
1456 m_killed_defs
= BITMAP_ALLOC (&m_bitmaps
);
1459 path_oracle::~path_oracle ()
1461 obstack_free (&m_chain_obstack
, NULL
);
1462 bitmap_obstack_release (&m_bitmaps
);
1465 // Return the equiv set for SSA, and if there isn't one, check for equivs
1466 // starting in block BB.
1469 path_oracle::equiv_set (tree ssa
, basic_block bb
)
1471 // Check the list first.
1472 equiv_chain
*ptr
= m_equiv
.find (SSA_NAME_VERSION (ssa
));
1474 return ptr
->m_names
;
1476 // Otherwise defer to the root oracle.
1478 return m_root
->equiv_set (ssa
, bb
);
1480 // Allocate a throw away bitmap if there isn't a root oracle.
1481 bitmap tmp
= BITMAP_ALLOC (&m_bitmaps
);
1482 bitmap_set_bit (tmp
, SSA_NAME_VERSION (ssa
));
1486 // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1490 path_oracle::register_equiv (basic_block bb
, tree ssa1
, tree ssa2
)
1492 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1493 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1495 // Check if they are the same set, if so, we're done.
1496 if (bitmap_equal_p (equiv_1
, equiv_2
))
1499 // Don't mess around, simply create a new record and insert it first.
1500 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1501 valid_equivs (b
, equiv_1
, bb
);
1502 valid_equivs (b
, equiv_2
, bb
);
1504 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1505 sizeof (equiv_chain
));
1508 ptr
->m_next
= m_equiv
.m_next
;
1509 m_equiv
.m_next
= ptr
;
1510 bitmap_ior_into (m_equiv
.m_names
, b
);
1513 // Register killing definition of an SSA_NAME.
1516 path_oracle::killing_def (tree ssa
)
1518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1520 fprintf (dump_file
, " Registering killing_def (path_oracle) ");
1521 print_generic_expr (dump_file
, ssa
, TDF_SLIM
);
1522 fprintf (dump_file
, "\n");
1525 unsigned v
= SSA_NAME_VERSION (ssa
);
1527 bitmap_set_bit (m_killed_defs
, v
);
1528 bitmap_set_bit (m_equiv
.m_names
, v
);
1530 // Now add an equivalency with itself so we don't look to the root oracle.
1531 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1532 bitmap_set_bit (b
, v
);
1533 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1534 sizeof (equiv_chain
));
1537 ptr
->m_next
= m_equiv
.m_next
;
1538 m_equiv
.m_next
= ptr
;
1540 // Walk the relation list and remove SSA from any relations.
1541 if (!bitmap_bit_p (m_relations
.m_names
, v
))
1544 bitmap_clear_bit (m_relations
.m_names
, v
);
1545 relation_chain
**prev
= &(m_relations
.m_head
);
1546 relation_chain
*next
= NULL
;
1547 for (relation_chain
*ptr
= m_relations
.m_head
; ptr
; ptr
= next
)
1549 gcc_checking_assert (*prev
== ptr
);
1551 if (SSA_NAME_VERSION (ptr
->op1 ()) == v
1552 || SSA_NAME_VERSION (ptr
->op2 ()) == v
)
1553 *prev
= ptr
->m_next
;
1555 prev
= &(ptr
->m_next
);
1559 // Register relation K between SSA1 and SSA2, resolving unknowns by
1560 // querying from BB.
1563 path_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
1566 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1567 // and no other relation makes sense.
1571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1573 value_relation
vr (k
, ssa1
, ssa2
);
1574 fprintf (dump_file
, " Registering value_relation (path_oracle) ");
1575 vr
.dump (dump_file
);
1576 fprintf (dump_file
, " (root: bb%d)\n", bb
->index
);
1579 relation_kind curr
= query_relation (bb
, ssa1
, ssa2
);
1580 if (curr
!= VREL_VARYING
)
1581 k
= relation_intersect (curr
, k
);
1585 register_equiv (bb
, ssa1
, ssa2
);
1589 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa1
));
1590 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa2
));
1591 relation_chain
*ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1592 sizeof (relation_chain
));
1593 ptr
->set_relation (k
, ssa1
, ssa2
);
1594 ptr
->m_next
= m_relations
.m_head
;
1595 m_relations
.m_head
= ptr
;
1598 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1599 // starting at block BB.
1602 path_oracle::query_relation (basic_block bb
, const_bitmap b1
, const_bitmap b2
)
1604 if (bitmap_equal_p (b1
, b2
))
1607 relation_kind k
= m_relations
.find_relation (b1
, b2
);
1609 // Do not look at the root oracle for names that have been killed
1611 if (bitmap_intersect_p (m_killed_defs
, b1
)
1612 || bitmap_intersect_p (m_killed_defs
, b2
))
1615 if (k
== VREL_VARYING
&& m_root
)
1616 k
= m_root
->query_relation (bb
, b1
, b2
);
1621 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1622 // starting at block BB.
1625 path_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1627 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1628 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1633 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1634 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1635 if (bitmap_bit_p (equiv_1
, v2
) && bitmap_bit_p (equiv_2
, v1
))
1638 return query_relation (bb
, equiv_1
, equiv_2
);
1641 // Reset any relations registered on this path. ORACLE is the root
1645 path_oracle::reset_path (relation_oracle
*oracle
)
1647 set_root_oracle (oracle
);
1648 m_equiv
.m_next
= NULL
;
1649 bitmap_clear (m_equiv
.m_names
);
1650 m_relations
.m_head
= NULL
;
1651 bitmap_clear (m_relations
.m_names
);
1652 bitmap_clear (m_killed_defs
);
1655 // Dump relation in basic block... Do nothing here.
1658 path_oracle::dump (FILE *, basic_block
) const
1662 // Dump the relations and equivalencies found in the path.
1665 path_oracle::dump (FILE *f
) const
1667 equiv_chain
*ptr
= m_equiv
.m_next
;
1668 relation_chain
*ptr2
= m_relations
.m_head
;
1671 fprintf (f
, "\npath_oracle:\n");
1673 for (; ptr
; ptr
= ptr
->m_next
)
1676 for (; ptr2
; ptr2
= ptr2
->m_next
)
1678 fprintf (f
, "Relational : ");
1684 // ------------------------------------------------------------------------
1685 // EQUIV iterator. Although we have bitmap iterators, don't expose that it
1686 // is currently a bitmap. Use an export iterator to hide future changes.
1688 // Construct a basic iterator over an equivalence bitmap.
1690 equiv_relation_iterator::equiv_relation_iterator (relation_oracle
*oracle
,
1691 basic_block bb
, tree name
,
1692 bool full
, bool partial
)
1696 m_pe
= partial
? oracle
->partial_equiv_set (name
) : NULL
;
1699 m_bm
= oracle
->equiv_set (name
, bb
);
1701 m_bm
= m_pe
->members
;
1703 bmp_iter_set_init (&m_bi
, m_bm
, 1, &m_y
);
1706 // Move to the next export bitmap spot.
1709 equiv_relation_iterator::next ()
1711 bmp_iter_next (&m_bi
, &m_y
);
1714 // Fetch the name of the next export in the export list. Return NULL if
1715 // iteration is done.
1718 equiv_relation_iterator::get_name (relation_kind
*rel
)
1723 while (bmp_iter_set (&m_bi
, &m_y
))
1725 // Do not return self.
1726 tree t
= ssa_name (m_y
);
1727 if (t
&& t
!= m_name
)
1729 relation_kind k
= VREL_EQ
;
1730 if (m_pe
&& m_bm
== m_pe
->members
)
1732 const pe_slice
*equiv_pe
= m_oracle
->partial_equiv_set (t
);
1733 if (equiv_pe
&& equiv_pe
->members
== m_pe
->members
)
1734 k
= pe_min (m_pe
->code
, equiv_pe
->code
);
1738 if (relation_equiv_p (k
))
1748 // Process partial equivs after full equivs if both were requested.
1749 if (m_pe
&& m_bm
!= m_pe
->members
)
1751 m_bm
= m_pe
->members
;
1754 // Recursively call back to process First PE.
1755 bmp_iter_set_init (&m_bi
, m_bm
, 1, &m_y
);
1756 return get_name (rel
);
1763 #include "selftest.h"
1770 // rr_*_table tables use unsigned char rather than relation_kind.
1771 ASSERT_LT (VREL_LAST
, UCHAR_MAX
);
1772 // Verify commutativity of relation_intersect and relation_union.
1773 for (relation_kind r1
= VREL_VARYING
; r1
< VREL_PE8
;
1774 r1
= relation_kind (r1
+ 1))
1775 for (relation_kind r2
= VREL_VARYING
; r2
< VREL_PE8
;
1776 r2
= relation_kind (r2
+ 1))
1778 ASSERT_EQ (relation_intersect (r1
, r2
), relation_intersect (r2
, r1
));
1779 ASSERT_EQ (relation_union (r1
, r2
), relation_union (r2
, r1
));
1783 } // namespace selftest
1785 #endif // CHECKING_P