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 // When operands of a statement are identical ssa_names, return the
187 // approriate relation between operands for NAME == NAME, given RANGE.
190 get_identity_relation (tree name
, vrange
&range ATTRIBUTE_UNUSED
)
192 // Return VREL_UNEQ when it is supported for floats as appropriate.
193 if (frange::supports_p (TREE_TYPE (name
)))
196 // Otherwise return VREL_EQ.
200 // This vector maps a relation to the equivalent tree code.
202 static const tree_code relation_to_code
[VREL_LAST
] = {
203 ERROR_MARK
, ERROR_MARK
, LT_EXPR
, LE_EXPR
, GT_EXPR
, GE_EXPR
, EQ_EXPR
,
206 // This routine validates that a relation can be applied to a specific set of
207 // ranges. In particular, floating point x == x may not be true if the NaN bit
208 // is set in the range. Symbolically the oracle will determine x == x,
209 // but specific range instances may override this.
210 // To verify, attempt to fold the relation using the supplied ranges.
211 // One would expect [1,1] to be returned, anything else means there is something
212 // in the range preventing the relation from applying.
213 // If there is no mechanism to verify, assume the relation is acceptable.
216 relation_oracle::validate_relation (relation_kind rel
, vrange
&op1
, vrange
&op2
)
218 // If there is no mapping to a tree code, leave the relation as is.
219 tree_code code
= relation_to_code
[rel
];
220 if (code
== ERROR_MARK
)
223 // Undefined ranges cannot be checked either.
224 if (op1
.undefined_p () || op2
.undefined_p ())
227 tree t1
= op1
.type ();
228 tree t2
= op2
.type ();
230 // If the range types are not compatible, no relation can exist.
231 if (!range_compatible_p (t1
, t2
))
234 // If there is no handler, leave the relation as is.
235 range_op_handler
handler (code
);
239 // If the relation cannot be folded for any reason, leave as is.
240 Value_Range
result (boolean_type_node
);
241 if (!handler
.fold_range (result
, boolean_type_node
, op1
, op2
,
242 relation_trio::op1_op2 (rel
)))
245 // The expression op1 REL op2 using REL should fold to [1,1].
246 // Any other result means the relation is not verified to be true.
247 if (result
.varying_p () || result
.zero_p ())
253 // If no range is available, create a varying range for each SSA name and
257 relation_oracle::validate_relation (relation_kind rel
, tree ssa1
, tree ssa2
)
259 Value_Range op1
, op2
;
260 op1
.set_varying (TREE_TYPE (ssa1
));
261 op2
.set_varying (TREE_TYPE (ssa2
));
263 return validate_relation (rel
, op1
, op2
);
266 // Given an equivalence set EQUIV, set all the bits in B that are still valid
267 // members of EQUIV in basic block BB.
270 relation_oracle::valid_equivs (bitmap b
, const_bitmap equivs
, basic_block bb
)
274 EXECUTE_IF_SET_IN_BITMAP (equivs
, 0, i
, bi
)
276 tree ssa
= ssa_name (i
);
277 const_bitmap ssa_equiv
= equiv_set (ssa
, bb
);
278 if (ssa_equiv
== equivs
)
279 bitmap_set_bit (b
, i
);
283 // -------------------------------------------------------------------------
285 // The very first element in the m_equiv chain is actually just a summary
286 // element in which the m_names bitmap is used to indicate that an ssa_name
287 // has an equivalence set in this block.
288 // This allows for much faster traversal of the DOM chain, as a search for
289 // SSA_NAME simply requires walking the DOM chain until a block is found
290 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
291 // that block. No previous lists need be searched.
293 // If SSA has an equivalence in this list, find and return it.
294 // Otherwise return NULL.
297 equiv_chain::find (unsigned ssa
)
299 equiv_chain
*ptr
= NULL
;
300 // If there are equiv sets and SSA is in one in this list, find it.
301 // Otherwise return NULL.
302 if (bitmap_bit_p (m_names
, ssa
))
304 for (ptr
= m_next
; ptr
; ptr
= ptr
->m_next
)
305 if (bitmap_bit_p (ptr
->m_names
, ssa
))
311 // Dump the names in this equivalence set.
314 equiv_chain::dump (FILE *f
) const
319 if (!m_names
|| bitmap_empty_p (m_names
))
321 fprintf (f
, "Equivalence set : [");
323 EXECUTE_IF_SET_IN_BITMAP (m_names
, 0, i
, bi
)
329 print_generic_expr (f
, ssa_name (i
), TDF_SLIM
);
335 // Instantiate an equivalency oracle.
337 equiv_oracle::equiv_oracle ()
339 bitmap_obstack_initialize (&m_bitmaps
);
341 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
342 m_equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
343 obstack_init (&m_chain_obstack
);
344 m_self_equiv
.create (0);
345 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
346 m_partial
.create (0);
347 m_partial
.safe_grow_cleared (num_ssa_names
+ 1);
350 // Destruct an equivalency oracle.
352 equiv_oracle::~equiv_oracle ()
354 m_partial
.release ();
355 m_self_equiv
.release ();
356 obstack_free (&m_chain_obstack
, NULL
);
358 bitmap_obstack_release (&m_bitmaps
);
361 // Add a partial equivalence R between OP1 and OP2.
364 equiv_oracle::add_partial_equiv (relation_kind r
, tree op1
, tree op2
)
366 int v1
= SSA_NAME_VERSION (op1
);
367 int v2
= SSA_NAME_VERSION (op2
);
368 int prec2
= TYPE_PRECISION (TREE_TYPE (op2
));
369 int bits
= pe_to_bits (r
);
370 gcc_checking_assert (bits
&& prec2
>= bits
);
372 if (v1
>= (int)m_partial
.length () || v2
>= (int)m_partial
.length ())
373 m_partial
.safe_grow_cleared (num_ssa_names
+ 1);
374 gcc_checking_assert (v1
< (int)m_partial
.length ()
375 && v2
< (int)m_partial
.length ());
377 pe_slice
&pe1
= m_partial
[v1
];
378 pe_slice
&pe2
= m_partial
[v2
];
382 // If the definition pe1 already has an entry, either the stmt is
383 // being re-evaluated, or the def was used before being registered.
384 // In either case, if PE2 has an entry, we simply do nothing.
387 // PE1 is the LHS and already has members, so everything in the set
388 // should be a slice of PE2 rather than PE1.
389 pe2
.code
= pe_min (r
, pe1
.code
);
391 pe2
.members
= pe1
.members
;
394 EXECUTE_IF_SET_IN_BITMAP (pe1
.members
, 0, x
, bi
)
396 m_partial
[x
].ssa_base
= op2
;
397 m_partial
[x
].code
= pe_min (m_partial
[x
].code
, pe2
.code
);
399 bitmap_set_bit (pe1
.members
, v2
);
404 pe1
.ssa_base
= pe2
.ssa_base
;
405 // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
406 // more than an 8 bit equivalence here, so choose MIN value.
407 pe1
.code
= pe_min (r
, pe2
.code
);
408 pe1
.members
= pe2
.members
;
409 bitmap_set_bit (pe1
.members
, v1
);
413 // Neither name has an entry, simply create op1 as slice of op2.
414 pe2
.code
= bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2
)));
415 if (pe2
.code
== VREL_VARYING
)
418 pe2
.members
= BITMAP_ALLOC (&m_bitmaps
);
419 bitmap_set_bit (pe2
.members
, v2
);
422 pe1
.members
= pe2
.members
;
423 bitmap_set_bit (pe1
.members
, v1
);
427 // Return the set of partial equivalences associated with NAME. The bitmap
428 // will be NULL if there are none.
431 equiv_oracle::partial_equiv_set (tree name
)
433 int v
= SSA_NAME_VERSION (name
);
434 if (v
>= (int)m_partial
.length ())
436 return &m_partial
[v
];
439 // Query if there is a partial equivalence between SSA1 and SSA2. Return
440 // VREL_VARYING if there is not one. If BASE is non-null, return the base
441 // ssa-name this is a slice of.
444 equiv_oracle::partial_equiv (tree ssa1
, tree ssa2
, tree
*base
) const
446 int v1
= SSA_NAME_VERSION (ssa1
);
447 int v2
= SSA_NAME_VERSION (ssa2
);
449 if (v1
>= (int)m_partial
.length () || v2
>= (int)m_partial
.length ())
452 const pe_slice
&pe1
= m_partial
[v1
];
453 const pe_slice
&pe2
= m_partial
[v2
];
454 if (pe1
.members
&& pe2
.members
== pe1
.members
)
457 *base
= pe1
.ssa_base
;
458 return pe_min (pe1
.code
, pe2
.code
);
464 // Find and return the equivalency set for SSA along the dominators of BB.
465 // This is the external API.
468 equiv_oracle::equiv_set (tree ssa
, basic_block bb
)
470 // Search the dominator tree for an equivalency.
471 equiv_chain
*equiv
= find_equiv_dom (ssa
, bb
);
473 return equiv
->m_names
;
475 // Otherwise return a cached equiv set containing just this SSA.
476 unsigned v
= SSA_NAME_VERSION (ssa
);
477 if (v
>= m_self_equiv
.length ())
478 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
480 if (!m_self_equiv
[v
])
482 m_self_equiv
[v
] = BITMAP_ALLOC (&m_bitmaps
);
483 bitmap_set_bit (m_self_equiv
[v
], v
);
485 return m_self_equiv
[v
];
488 // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
491 equiv_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
493 // If the 2 ssa names share the same equiv set, they are equal.
494 if (equiv_set (ssa1
, bb
) == equiv_set (ssa2
, bb
))
497 // Check if there is a partial equivalence.
498 return partial_equiv (ssa1
, ssa2
);
501 // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
504 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED
, const_bitmap e1
,
507 // If the 2 ssa names share the same equiv set, they are equal.
508 if (bitmap_equal_p (e1
, e2
))
513 // If SSA has an equivalence in block BB, find and return it.
514 // Otherwise return NULL.
517 equiv_oracle::find_equiv_block (unsigned ssa
, int bb
) const
519 if (bb
>= (int)m_equiv
.length () || !m_equiv
[bb
])
522 return m_equiv
[bb
]->find (ssa
);
525 // Starting at block BB, walk the dominator chain looking for the nearest
526 // equivalence set containing NAME.
529 equiv_oracle::find_equiv_dom (tree name
, basic_block bb
) const
531 unsigned v
= SSA_NAME_VERSION (name
);
532 // Short circuit looking for names which have no equivalences.
533 // Saves time looking for something which does not exist.
534 if (!bitmap_bit_p (m_equiv_set
, v
))
537 // NAME has at least once equivalence set, check to see if it has one along
538 // the dominator tree.
539 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
541 equiv_chain
*ptr
= find_equiv_block (v
, bb
->index
);
548 // Register equivalence between ssa_name V and set EQUIV in block BB,
551 equiv_oracle::register_equiv (basic_block bb
, unsigned v
, equiv_chain
*equiv
)
553 // V will have an equivalency now.
554 bitmap_set_bit (m_equiv_set
, v
);
556 // If that equiv chain is in this block, simply use it.
557 if (equiv
->m_bb
== bb
)
559 bitmap_set_bit (equiv
->m_names
, v
);
560 bitmap_set_bit (m_equiv
[bb
->index
]->m_names
, v
);
564 // Otherwise create an equivalence for this block which is a copy
565 // of equiv, the add V to the set.
566 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
567 valid_equivs (b
, equiv
->m_names
, bb
);
568 bitmap_set_bit (b
, v
);
572 // Register equivalence between set equiv_1 and equiv_2 in block BB.
573 // Return NULL if either name can be merged with the other. Otherwise
574 // return a pointer to the combined bitmap of names. This allows the
575 // caller to do any setup required for a new element.
578 equiv_oracle::register_equiv (basic_block bb
, equiv_chain
*equiv_1
,
579 equiv_chain
*equiv_2
)
581 // If equiv_1 is already in BB, use it as the combined set.
582 if (equiv_1
->m_bb
== bb
)
584 valid_equivs (equiv_1
->m_names
, equiv_2
->m_names
, bb
);
585 // Its hard to delete from a single linked list, so
586 // just clear the second one.
587 if (equiv_2
->m_bb
== bb
)
588 bitmap_clear (equiv_2
->m_names
);
590 // Ensure the new names are in the summary for BB.
591 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_1
->m_names
);
594 // If equiv_2 is in BB, use it for the combined set.
595 if (equiv_2
->m_bb
== bb
)
597 valid_equivs (equiv_2
->m_names
, equiv_1
->m_names
, bb
);
598 // Ensure the new names are in the summary.
599 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_2
->m_names
);
603 // At this point, neither equivalence is from this block.
604 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
605 valid_equivs (b
, equiv_1
->m_names
, bb
);
606 valid_equivs (b
, equiv_2
->m_names
, bb
);
610 // Create an equivalency set containing only SSA in its definition block.
611 // This is done the first time SSA is registered in an equivalency and blocks
612 // any DOM searches past the definition.
615 equiv_oracle::register_initial_def (tree ssa
)
617 if (SSA_NAME_IS_DEFAULT_DEF (ssa
))
619 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (ssa
));
620 gcc_checking_assert (bb
&& !find_equiv_dom (ssa
, bb
));
622 unsigned v
= SSA_NAME_VERSION (ssa
);
623 bitmap_set_bit (m_equiv_set
, v
);
624 bitmap equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
625 bitmap_set_bit (equiv_set
, v
);
626 add_equiv_to_block (bb
, equiv_set
);
629 // Register an equivalence between SSA1 and SSA2 in block BB.
630 // The equivalence oracle maintains a vector of equivalencies indexed by basic
631 // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
632 // a query is made as to what equivalences both names have already, and
633 // any preexisting equivalences are merged to create a single equivalence
634 // containing all the ssa_names in this basic block.
637 equiv_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
640 // Process partial equivalencies.
641 if (relation_partial_equiv_p (k
))
643 add_partial_equiv (k
, ssa1
, ssa2
);
646 // Only handle equality relations.
650 unsigned v1
= SSA_NAME_VERSION (ssa1
);
651 unsigned v2
= SSA_NAME_VERSION (ssa2
);
653 // If this is the first time an ssa_name has an equivalency registered
654 // create a self-equivalency record in the def block.
655 if (!bitmap_bit_p (m_equiv_set
, v1
))
656 register_initial_def (ssa1
);
657 if (!bitmap_bit_p (m_equiv_set
, v2
))
658 register_initial_def (ssa2
);
660 equiv_chain
*equiv_1
= find_equiv_dom (ssa1
, bb
);
661 equiv_chain
*equiv_2
= find_equiv_dom (ssa2
, bb
);
663 // Check if they are the same set
664 if (equiv_1
&& equiv_1
== equiv_2
)
669 // Case where we have 2 SSA_NAMEs that are not in any set.
670 if (!equiv_1
&& !equiv_2
)
672 bitmap_set_bit (m_equiv_set
, v1
);
673 bitmap_set_bit (m_equiv_set
, v2
);
675 equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
676 bitmap_set_bit (equiv_set
, v1
);
677 bitmap_set_bit (equiv_set
, v2
);
679 else if (!equiv_1
&& equiv_2
)
680 equiv_set
= register_equiv (bb
, v1
, equiv_2
);
681 else if (equiv_1
&& !equiv_2
)
682 equiv_set
= register_equiv (bb
, v2
, equiv_1
);
684 equiv_set
= register_equiv (bb
, equiv_1
, equiv_2
);
686 // A non-null return is a bitmap that is to be added to the current
687 // block as a new equivalence.
691 add_equiv_to_block (bb
, equiv_set
);
694 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
695 // Note the internal caller is responsible for allocating EQUIV_SET properly.
698 equiv_oracle::add_equiv_to_block (basic_block bb
, bitmap equiv_set
)
702 // Check if this is the first time a block has an equivalence added.
703 // and create a header block. And set the summary for this block.
704 if (!m_equiv
[bb
->index
])
706 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
707 sizeof (equiv_chain
));
708 ptr
->m_names
= BITMAP_ALLOC (&m_bitmaps
);
709 bitmap_copy (ptr
->m_names
, equiv_set
);
712 m_equiv
[bb
->index
] = ptr
;
715 // Now create the element for this equiv set and initialize it.
716 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
, sizeof (equiv_chain
));
717 ptr
->m_names
= equiv_set
;
719 gcc_checking_assert (bb
->index
< (int)m_equiv
.length ());
720 ptr
->m_next
= m_equiv
[bb
->index
]->m_next
;
721 m_equiv
[bb
->index
]->m_next
= ptr
;
722 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_set
);
725 // Make sure the BB vector is big enough and grow it if needed.
728 equiv_oracle::limit_check (basic_block bb
)
730 int i
= (bb
) ? bb
->index
: last_basic_block_for_fn (cfun
);
731 if (i
>= (int)m_equiv
.length ())
732 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
735 // Dump the equivalence sets in BB to file F.
738 equiv_oracle::dump (FILE *f
, basic_block bb
) const
740 if (bb
->index
>= (int)m_equiv
.length ())
742 // Process equivalences.
743 if (m_equiv
[bb
->index
])
745 equiv_chain
*ptr
= m_equiv
[bb
->index
]->m_next
;
746 for (; ptr
; ptr
= ptr
->m_next
)
749 // Look for partial equivalences defined in this block..
750 for (unsigned i
= 0; i
< num_ssa_names
; i
++)
752 tree name
= ssa_name (i
);
753 if (!gimple_range_ssa_p (name
) || !SSA_NAME_DEF_STMT (name
))
755 if (i
>= m_partial
.length ())
757 tree base
= m_partial
[i
].ssa_base
;
758 if (base
&& name
!= base
&& gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
)
760 relation_kind k
= partial_equiv (name
, base
);
761 if (k
!= VREL_VARYING
)
763 value_relation
vr (k
, name
, base
);
764 fprintf (f
, "Partial equiv ");
772 // Dump all equivalence sets known to the oracle.
775 equiv_oracle::dump (FILE *f
) const
777 fprintf (f
, "Equivalency dump\n");
778 for (unsigned i
= 0; i
< m_equiv
.length (); i
++)
779 if (m_equiv
[i
] && BASIC_BLOCK_FOR_FN (cfun
, i
))
781 fprintf (f
, "BB%d\n", i
);
782 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
787 // --------------------------------------------------------------------------
788 // Negate the current relation.
791 value_relation::negate ()
793 related
= relation_negate (related
);
796 // Perform an intersection between 2 relations. *this &&= p.
799 value_relation::intersect (value_relation
&p
)
801 // Save previous value
802 relation_kind old
= related
;
804 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
805 related
= relation_intersect (kind (), p
.kind ());
806 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
807 related
= relation_intersect (kind (), relation_swap (p
.kind ()));
811 return old
!= related
;
814 // Perform a union between 2 relations. *this ||= p.
817 value_relation::union_ (value_relation
&p
)
819 // Save previous value
820 relation_kind old
= related
;
822 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
823 related
= relation_union (kind(), p
.kind());
824 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
825 related
= relation_union (kind(), relation_swap (p
.kind ()));
829 return old
!= related
;
832 // Identify and apply any transitive relations between REL
833 // and THIS. Return true if there was a transformation.
836 value_relation::apply_transitive (const value_relation
&rel
)
838 relation_kind k
= VREL_VARYING
;
840 // Identify any common operand, and normalize the relations to
841 // the form : A < B B < C produces A < C
842 if (rel
.op1 () == name2
)
845 if (rel
.op2 () == name1
)
847 k
= relation_transitive (kind (), rel
.kind ());
848 if (k
!= VREL_VARYING
)
855 else if (rel
.op1 () == name1
)
858 if (rel
.op2 () == name2
)
860 k
= relation_transitive (relation_swap (kind ()), rel
.kind ());
861 if (k
!= VREL_VARYING
)
869 else if (rel
.op2 () == name2
)
872 if (rel
.op1 () == name1
)
874 k
= relation_transitive (kind (), relation_swap (rel
.kind ()));
875 if (k
!= VREL_VARYING
)
882 else if (rel
.op2 () == name1
)
885 if (rel
.op1 () == name2
)
887 k
= relation_transitive (relation_swap (kind ()),
888 relation_swap (rel
.kind ()));
889 if (k
!= VREL_VARYING
)
900 // Create a trio from this value relation given LHS, OP1 and OP2.
903 value_relation::create_trio (tree lhs
, tree op1
, tree op2
)
906 if (lhs
== name1
&& op1
== name2
)
908 else if (lhs
== name2
&& op1
== name1
)
909 lhs_1
= relation_swap (related
);
911 lhs_1
= VREL_VARYING
;
914 if (lhs
== name1
&& op2
== name2
)
916 else if (lhs
== name2
&& op2
== name1
)
917 lhs_2
= relation_swap (related
);
919 lhs_2
= VREL_VARYING
;
922 if (op1
== name1
&& op2
== name2
)
924 else if (op1
== name2
&& op2
== name1
)
925 op_op
= relation_swap (related
);
929 op_op
= VREL_VARYING
;
931 return relation_trio (lhs_1
, lhs_2
, op_op
);
934 // Dump the relation to file F.
937 value_relation::dump (FILE *f
) const
939 if (!name1
|| !name2
)
941 fprintf (f
, "no relation registered");
945 print_generic_expr (f
, op1 (), TDF_SLIM
);
946 print_relation (f
, kind ());
947 print_generic_expr (f
, op2 (), TDF_SLIM
);
951 // This container is used to link relations in a chain.
953 class relation_chain
: public value_relation
956 relation_chain
*m_next
;
959 // ------------------------------------------------------------------------
961 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
962 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
965 relation_chain_head::find_relation (const_bitmap b1
, const_bitmap b2
) const
970 // If both b1 and b2 aren't referenced in this block, cant be a relation
971 if (!bitmap_intersect_p (m_names
, b1
) || !bitmap_intersect_p (m_names
, b2
))
974 // Search for the first relation that contains BOTH an element from B1
975 // and B2, and return that relation.
976 for (relation_chain
*ptr
= m_head
; ptr
; ptr
= ptr
->m_next
)
978 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
979 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
980 if (bitmap_bit_p (b1
, op1
) && bitmap_bit_p (b2
, op2
))
982 if (bitmap_bit_p (b1
, op2
) && bitmap_bit_p (b2
, op1
))
983 return relation_swap (ptr
->kind ());
989 // Instantiate a relation oracle.
991 dom_oracle::dom_oracle ()
993 m_relations
.create (0);
994 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
995 m_relation_set
= BITMAP_ALLOC (&m_bitmaps
);
996 m_tmp
= BITMAP_ALLOC (&m_bitmaps
);
997 m_tmp2
= BITMAP_ALLOC (&m_bitmaps
);
1000 // Destruct a relation oracle.
1002 dom_oracle::~dom_oracle ()
1004 m_relations
.release ();
1007 // Register relation K between ssa_name OP1 and OP2 on STMT.
1010 relation_oracle::register_stmt (gimple
*stmt
, relation_kind k
, tree op1
,
1013 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
1014 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
1015 gcc_checking_assert (stmt
&& gimple_bb (stmt
));
1017 // Don't register lack of a relation.
1018 if (k
== VREL_VARYING
)
1021 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1023 value_relation
vr (k
, op1
, op2
);
1024 fprintf (dump_file
, " Registering value_relation ");
1025 vr
.dump (dump_file
);
1026 fprintf (dump_file
, " (bb%d) at ", gimple_bb (stmt
)->index
);
1027 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1030 // If an equivalence is being added between a PHI and one of its arguments
1031 // make sure that that argument is not defined in the same block.
1032 // This can happen along back edges and the equivalence will not be
1033 // applicable as it would require a use before def.
1034 if (k
== VREL_EQ
&& is_a
<gphi
*> (stmt
))
1036 tree phi_def
= gimple_phi_result (stmt
);
1037 gcc_checking_assert (phi_def
== op1
|| phi_def
== op2
);
1041 if (gimple_bb (stmt
) == gimple_bb (SSA_NAME_DEF_STMT (arg
)))
1043 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1045 fprintf (dump_file
, " Not registered due to ");
1046 print_generic_expr (dump_file
, arg
, TDF_SLIM
);
1047 fprintf (dump_file
, " being defined in the same block.\n");
1052 register_relation (gimple_bb (stmt
), k
, op1
, op2
);
1055 // Register relation K between ssa_name OP1 and OP2 on edge E.
1058 relation_oracle::register_edge (edge e
, relation_kind k
, tree op1
, tree op2
)
1060 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
1061 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
1063 // Do not register lack of relation, or blocks which have more than
1064 // edge E for a predecessor.
1065 if (k
== VREL_VARYING
|| !single_pred_p (e
->dest
))
1068 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1070 value_relation
vr (k
, op1
, op2
);
1071 fprintf (dump_file
, " Registering value_relation ");
1072 vr
.dump (dump_file
);
1073 fprintf (dump_file
, " on (%d->%d)\n", e
->src
->index
, e
->dest
->index
);
1076 register_relation (e
->dest
, k
, op1
, op2
);
1079 // Register relation K between OP! and OP2 in block BB.
1080 // This creates the record and searches for existing records in the dominator
1081 // tree to merge with.
1084 dom_oracle::register_relation (basic_block bb
, relation_kind k
, tree op1
,
1087 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1088 // and no other relation makes sense.
1092 // Equivalencies are handled by the equivalence oracle.
1093 if (relation_equiv_p (k
))
1094 equiv_oracle::register_relation (bb
, k
, op1
, op2
);
1097 // if neither op1 nor op2 are in a relation before this is registered,
1098 // there will be no transitive.
1099 bool check
= bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op1
))
1100 || bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op2
));
1101 relation_chain
*ptr
= set_one_relation (bb
, k
, op1
, op2
);
1103 register_transitives (bb
, *ptr
);
1107 // Register relation K between OP! and OP2 in block BB.
1108 // This creates the record and searches for existing records in the dominator
1109 // tree to merge with. Return the record, or NULL if no record was created.
1112 dom_oracle::set_one_relation (basic_block bb
, relation_kind k
, tree op1
,
1115 gcc_checking_assert (k
!= VREL_VARYING
&& k
!= VREL_EQ
);
1117 value_relation
vr(k
, op1
, op2
);
1118 int bbi
= bb
->index
;
1120 if (bbi
>= (int)m_relations
.length())
1121 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
1123 // Summary bitmap indicating what ssa_names have relations in this BB.
1124 bitmap bm
= m_relations
[bbi
].m_names
;
1126 bm
= m_relations
[bbi
].m_names
= BITMAP_ALLOC (&m_bitmaps
);
1127 unsigned v1
= SSA_NAME_VERSION (op1
);
1128 unsigned v2
= SSA_NAME_VERSION (op2
);
1131 relation_chain
*ptr
;
1132 curr
= find_relation_block (bbi
, v1
, v2
, &ptr
);
1133 // There is an existing relation in this block, just intersect with it.
1134 if (curr
!= VREL_VARYING
)
1136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1138 fprintf (dump_file
, " Intersecting with existing ");
1139 ptr
->dump (dump_file
);
1141 // Check into whether we can simply replace the relation rather than
1142 // intersecting it. This may help with some optimistic iterative
1143 // updating algorithms.
1144 bool new_rel
= ptr
->intersect (vr
);
1145 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1147 fprintf (dump_file
, " to produce ");
1148 ptr
->dump (dump_file
);
1149 fprintf (dump_file
, " %s.\n", new_rel
? "Updated" : "No Change");
1151 // If there was no change, return no record..
1157 if (m_relations
[bbi
].m_num_relations
>= param_relation_block_limit
)
1159 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1160 fprintf (dump_file
, " Not registered due to bb being full\n");
1163 m_relations
[bbi
].m_num_relations
++;
1164 // Check for an existing relation further up the DOM chain.
1165 // By including dominating relations, The first one found in any search
1166 // will be the aggregate of all the previous ones.
1167 curr
= find_relation_dom (bb
, v1
, v2
);
1168 if (curr
!= VREL_VARYING
)
1169 k
= relation_intersect (curr
, k
);
1171 bitmap_set_bit (bm
, v1
);
1172 bitmap_set_bit (bm
, v2
);
1173 bitmap_set_bit (m_relation_set
, v1
);
1174 bitmap_set_bit (m_relation_set
, v2
);
1176 ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1177 sizeof (relation_chain
));
1178 ptr
->set_relation (k
, op1
, op2
);
1179 ptr
->m_next
= m_relations
[bbi
].m_head
;
1180 m_relations
[bbi
].m_head
= ptr
;
1185 // Starting at ROOT_BB search the DOM tree looking for relations which
1186 // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1187 // bitmaps for op1/op2 and any of their equivalences that should also be
1191 dom_oracle::register_transitives (basic_block root_bb
,
1192 const value_relation
&relation
)
1195 // Only apply transitives to certain kinds of operations.
1196 switch (relation
.kind ())
1207 const_bitmap equiv1
= equiv_set (relation
.op1 (), root_bb
);
1208 const_bitmap equiv2
= equiv_set (relation
.op2 (), root_bb
);
1210 for (bb
= root_bb
; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1212 int bbi
= bb
->index
;
1213 if (bbi
>= (int)m_relations
.length())
1215 const_bitmap bm
= m_relations
[bbi
].m_names
;
1218 if (!bitmap_intersect_p (bm
, equiv1
) && !bitmap_intersect_p (bm
, equiv2
))
1220 // At least one of the 2 ops has a relation in this block.
1221 relation_chain
*ptr
;
1222 for (ptr
= m_relations
[bbi
].m_head
; ptr
; ptr
= ptr
->m_next
)
1224 // In the presence of an equivalence, 2 operands may do not
1225 // naturally match. ie with equivalence a_2 == b_3
1226 // given c_1 < a_2 && b_3 < d_4
1227 // convert the second relation (b_3 < d_4) to match any
1228 // equivalences to found in the first relation.
1229 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1230 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1233 tree p1
= ptr
->op1 ();
1234 tree p2
= ptr
->op2 ();
1235 // Find which equivalence is in the first operand.
1236 if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p1
)))
1238 else if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p2
)))
1243 // Find which equivalence is in the second operand.
1244 if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p1
)))
1246 else if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p2
)))
1251 // Ignore if both NULL (not relevant relation) or the same,
1255 // Any operand not an equivalence, just take the real operand.
1257 r1
= relation
.op1 ();
1259 r2
= relation
.op2 ();
1261 value_relation
nr (relation
.kind (), r1
, r2
);
1262 if (nr
.apply_transitive (*ptr
))
1264 if (!set_one_relation (root_bb
, nr
.kind (), nr
.op1 (), nr
.op2 ()))
1266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1268 fprintf (dump_file
, " Registering transitive relation ");
1269 nr
.dump (dump_file
);
1270 fputc ('\n', dump_file
);
1278 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1279 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1282 dom_oracle::find_relation_block (unsigned bb
, const_bitmap b1
,
1283 const_bitmap b2
) const
1285 if (bb
>= m_relations
.length())
1286 return VREL_VARYING
;
1288 return m_relations
[bb
].find_relation (b1
, b2
);
1291 // Search the DOM tree for a relation between an element of equivalency set B1
1292 // and B2, starting with block BB.
1295 dom_oracle::query_relation (basic_block bb
, const_bitmap b1
,
1299 if (bitmap_equal_p (b1
, b2
))
1302 // If either name does not occur in a relation anywhere, there isn't one.
1303 if (!bitmap_intersect_p (m_relation_set
, b1
)
1304 || !bitmap_intersect_p (m_relation_set
, b2
))
1305 return VREL_VARYING
;
1307 // Search each block in the DOM tree checking.
1308 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1310 r
= find_relation_block (bb
->index
, b1
, b2
);
1311 if (r
!= VREL_VARYING
)
1314 return VREL_VARYING
;
1318 // Find a relation in block BB between ssa version V1 and V2. If a relation
1319 // is found, return a pointer to the chain object in OBJ.
1322 dom_oracle::find_relation_block (int bb
, unsigned v1
, unsigned v2
,
1323 relation_chain
**obj
) const
1325 if (bb
>= (int)m_relations
.length())
1326 return VREL_VARYING
;
1328 const_bitmap bm
= m_relations
[bb
].m_names
;
1330 return VREL_VARYING
;
1332 // If both b1 and b2 aren't referenced in this block, cant be a relation
1333 if (!bitmap_bit_p (bm
, v1
) || !bitmap_bit_p (bm
, v2
))
1334 return VREL_VARYING
;
1336 relation_chain
*ptr
;
1337 for (ptr
= m_relations
[bb
].m_head
; ptr
; ptr
= ptr
->m_next
)
1339 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
1340 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
1341 if (v1
== op1
&& v2
== op2
)
1345 return ptr
->kind ();
1347 if (v1
== op2
&& v2
== op1
)
1351 return relation_swap (ptr
->kind ());
1355 return VREL_VARYING
;
1358 // Find a relation between SSA version V1 and V2 in the dominator tree
1359 // starting with block BB
1362 dom_oracle::find_relation_dom (basic_block bb
, unsigned v1
, unsigned v2
) const
1365 // IF either name does not occur in a relation anywhere, there isn't one.
1366 if (!bitmap_bit_p (m_relation_set
, v1
) || !bitmap_bit_p (m_relation_set
, v2
))
1367 return VREL_VARYING
;
1369 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1371 r
= find_relation_block (bb
->index
, v1
, v2
);
1372 if (r
!= VREL_VARYING
)
1375 return VREL_VARYING
;
1379 // Query if there is a relation between SSA1 and SS2 in block BB or a
1383 dom_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1386 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1387 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1391 // If v1 or v2 do not have any relations or equivalences, a partial
1392 // equivalence is the only possibility.
1393 if ((!bitmap_bit_p (m_relation_set
, v1
) && !has_equiv_p (v1
))
1394 || (!bitmap_bit_p (m_relation_set
, v2
) && !has_equiv_p (v2
)))
1395 return partial_equiv (ssa1
, ssa2
);
1397 // Check for equivalence first. They must be in each equivalency set.
1398 const_bitmap equiv1
= equiv_set (ssa1
, bb
);
1399 const_bitmap equiv2
= equiv_set (ssa2
, bb
);
1400 if (bitmap_bit_p (equiv1
, v2
) && bitmap_bit_p (equiv2
, v1
))
1403 kind
= partial_equiv (ssa1
, ssa2
);
1404 if (kind
!= VREL_VARYING
)
1407 // Initially look for a direct relationship and just return that.
1408 kind
= find_relation_dom (bb
, v1
, v2
);
1409 if (kind
!= VREL_VARYING
)
1412 // Query using the equivalence sets.
1413 kind
= query_relation (bb
, equiv1
, equiv2
);
1417 // Dump all the relations in block BB to file F.
1420 dom_oracle::dump (FILE *f
, basic_block bb
) const
1422 equiv_oracle::dump (f
,bb
);
1424 if (bb
->index
>= (int)m_relations
.length ())
1426 if (!m_relations
[bb
->index
].m_names
)
1429 relation_chain
*ptr
= m_relations
[bb
->index
].m_head
;
1430 for (; ptr
; ptr
= ptr
->m_next
)
1432 fprintf (f
, "Relational : ");
1438 // Dump all the relations known to file F.
1441 dom_oracle::dump (FILE *f
) const
1443 fprintf (f
, "Relation dump\n");
1444 for (unsigned i
= 0; i
< m_relations
.length (); i
++)
1445 if (BASIC_BLOCK_FOR_FN (cfun
, i
))
1447 fprintf (f
, "BB%d\n", i
);
1448 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
1453 relation_oracle::debug () const
1458 path_oracle::path_oracle (relation_oracle
*oracle
)
1460 set_root_oracle (oracle
);
1461 bitmap_obstack_initialize (&m_bitmaps
);
1462 obstack_init (&m_chain_obstack
);
1464 // Initialize header records.
1465 m_equiv
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1466 m_equiv
.m_bb
= NULL
;
1467 m_equiv
.m_next
= NULL
;
1468 m_relations
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1469 m_relations
.m_head
= NULL
;
1470 m_killed_defs
= BITMAP_ALLOC (&m_bitmaps
);
1473 path_oracle::~path_oracle ()
1475 obstack_free (&m_chain_obstack
, NULL
);
1476 bitmap_obstack_release (&m_bitmaps
);
1479 // Return the equiv set for SSA, and if there isn't one, check for equivs
1480 // starting in block BB.
1483 path_oracle::equiv_set (tree ssa
, basic_block bb
)
1485 // Check the list first.
1486 equiv_chain
*ptr
= m_equiv
.find (SSA_NAME_VERSION (ssa
));
1488 return ptr
->m_names
;
1490 // Otherwise defer to the root oracle.
1492 return m_root
->equiv_set (ssa
, bb
);
1494 // Allocate a throw away bitmap if there isn't a root oracle.
1495 bitmap tmp
= BITMAP_ALLOC (&m_bitmaps
);
1496 bitmap_set_bit (tmp
, SSA_NAME_VERSION (ssa
));
1500 // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1504 path_oracle::register_equiv (basic_block bb
, tree ssa1
, tree ssa2
)
1506 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1507 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1509 // Check if they are the same set, if so, we're done.
1510 if (bitmap_equal_p (equiv_1
, equiv_2
))
1513 // Don't mess around, simply create a new record and insert it first.
1514 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1515 valid_equivs (b
, equiv_1
, bb
);
1516 valid_equivs (b
, equiv_2
, bb
);
1518 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1519 sizeof (equiv_chain
));
1522 ptr
->m_next
= m_equiv
.m_next
;
1523 m_equiv
.m_next
= ptr
;
1524 bitmap_ior_into (m_equiv
.m_names
, b
);
1527 // Register killing definition of an SSA_NAME.
1530 path_oracle::killing_def (tree ssa
)
1532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1534 fprintf (dump_file
, " Registering killing_def (path_oracle) ");
1535 print_generic_expr (dump_file
, ssa
, TDF_SLIM
);
1536 fprintf (dump_file
, "\n");
1539 unsigned v
= SSA_NAME_VERSION (ssa
);
1541 bitmap_set_bit (m_killed_defs
, v
);
1542 bitmap_set_bit (m_equiv
.m_names
, v
);
1544 // Now add an equivalency with itself so we don't look to the root oracle.
1545 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1546 bitmap_set_bit (b
, v
);
1547 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1548 sizeof (equiv_chain
));
1551 ptr
->m_next
= m_equiv
.m_next
;
1552 m_equiv
.m_next
= ptr
;
1554 // Walk the relation list and remove SSA from any relations.
1555 if (!bitmap_bit_p (m_relations
.m_names
, v
))
1558 bitmap_clear_bit (m_relations
.m_names
, v
);
1559 relation_chain
**prev
= &(m_relations
.m_head
);
1560 relation_chain
*next
= NULL
;
1561 for (relation_chain
*ptr
= m_relations
.m_head
; ptr
; ptr
= next
)
1563 gcc_checking_assert (*prev
== ptr
);
1565 if (SSA_NAME_VERSION (ptr
->op1 ()) == v
1566 || SSA_NAME_VERSION (ptr
->op2 ()) == v
)
1567 *prev
= ptr
->m_next
;
1569 prev
= &(ptr
->m_next
);
1573 // Register relation K between SSA1 and SSA2, resolving unknowns by
1574 // querying from BB.
1577 path_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
1580 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1581 // and no other relation makes sense.
1585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1587 value_relation
vr (k
, ssa1
, ssa2
);
1588 fprintf (dump_file
, " Registering value_relation (path_oracle) ");
1589 vr
.dump (dump_file
);
1590 fprintf (dump_file
, " (root: bb%d)\n", bb
->index
);
1593 relation_kind curr
= query_relation (bb
, ssa1
, ssa2
);
1594 if (curr
!= VREL_VARYING
)
1595 k
= relation_intersect (curr
, k
);
1599 register_equiv (bb
, ssa1
, ssa2
);
1603 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa1
));
1604 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa2
));
1605 relation_chain
*ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1606 sizeof (relation_chain
));
1607 ptr
->set_relation (k
, ssa1
, ssa2
);
1608 ptr
->m_next
= m_relations
.m_head
;
1609 m_relations
.m_head
= ptr
;
1612 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1613 // starting at block BB.
1616 path_oracle::query_relation (basic_block bb
, const_bitmap b1
, const_bitmap b2
)
1618 if (bitmap_equal_p (b1
, b2
))
1621 relation_kind k
= m_relations
.find_relation (b1
, b2
);
1623 // Do not look at the root oracle for names that have been killed
1625 if (bitmap_intersect_p (m_killed_defs
, b1
)
1626 || bitmap_intersect_p (m_killed_defs
, b2
))
1629 if (k
== VREL_VARYING
&& m_root
)
1630 k
= m_root
->query_relation (bb
, b1
, b2
);
1635 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1636 // starting at block BB.
1639 path_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1641 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1642 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1647 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1648 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1649 if (bitmap_bit_p (equiv_1
, v2
) && bitmap_bit_p (equiv_2
, v1
))
1652 return query_relation (bb
, equiv_1
, equiv_2
);
1655 // Reset any relations registered on this path. ORACLE is the root
1659 path_oracle::reset_path (relation_oracle
*oracle
)
1661 set_root_oracle (oracle
);
1662 m_equiv
.m_next
= NULL
;
1663 bitmap_clear (m_equiv
.m_names
);
1664 m_relations
.m_head
= NULL
;
1665 bitmap_clear (m_relations
.m_names
);
1666 bitmap_clear (m_killed_defs
);
1669 // Dump relation in basic block... Do nothing here.
1672 path_oracle::dump (FILE *, basic_block
) const
1676 // Dump the relations and equivalencies found in the path.
1679 path_oracle::dump (FILE *f
) const
1681 equiv_chain
*ptr
= m_equiv
.m_next
;
1682 relation_chain
*ptr2
= m_relations
.m_head
;
1685 fprintf (f
, "\npath_oracle:\n");
1687 for (; ptr
; ptr
= ptr
->m_next
)
1690 for (; ptr2
; ptr2
= ptr2
->m_next
)
1692 fprintf (f
, "Relational : ");
1698 // ------------------------------------------------------------------------
1699 // EQUIV iterator. Although we have bitmap iterators, don't expose that it
1700 // is currently a bitmap. Use an export iterator to hide future changes.
1702 // Construct a basic iterator over an equivalence bitmap.
1704 equiv_relation_iterator::equiv_relation_iterator (relation_oracle
*oracle
,
1705 basic_block bb
, tree name
,
1706 bool full
, bool partial
)
1710 m_pe
= partial
? oracle
->partial_equiv_set (name
) : NULL
;
1713 m_bm
= oracle
->equiv_set (name
, bb
);
1715 m_bm
= m_pe
->members
;
1717 bmp_iter_set_init (&m_bi
, m_bm
, 1, &m_y
);
1720 // Move to the next export bitmap spot.
1723 equiv_relation_iterator::next ()
1725 bmp_iter_next (&m_bi
, &m_y
);
1728 // Fetch the name of the next export in the export list. Return NULL if
1729 // iteration is done.
1732 equiv_relation_iterator::get_name (relation_kind
*rel
)
1737 while (bmp_iter_set (&m_bi
, &m_y
))
1739 // Do not return self.
1740 tree t
= ssa_name (m_y
);
1741 if (t
&& t
!= m_name
)
1743 relation_kind k
= VREL_EQ
;
1744 if (m_pe
&& m_bm
== m_pe
->members
)
1746 const pe_slice
*equiv_pe
= m_oracle
->partial_equiv_set (t
);
1747 if (equiv_pe
&& equiv_pe
->members
== m_pe
->members
)
1748 k
= pe_min (m_pe
->code
, equiv_pe
->code
);
1752 if (relation_equiv_p (k
))
1762 // Process partial equivs after full equivs if both were requested.
1763 if (m_pe
&& m_bm
!= m_pe
->members
)
1765 m_bm
= m_pe
->members
;
1768 // Recursively call back to process First PE.
1769 bmp_iter_set_init (&m_bi
, m_bm
, 1, &m_y
);
1770 return get_name (rel
);
1777 #include "selftest.h"
1784 // rr_*_table tables use unsigned char rather than relation_kind.
1785 ASSERT_LT (VREL_LAST
, UCHAR_MAX
);
1786 // Verify commutativity of relation_intersect and relation_union.
1787 for (relation_kind r1
= VREL_VARYING
; r1
< VREL_PE8
;
1788 r1
= relation_kind (r1
+ 1))
1789 for (relation_kind r2
= VREL_VARYING
; r2
< VREL_PE8
;
1790 r2
= relation_kind (r2
+ 1))
1792 ASSERT_EQ (relation_intersect (r1
, r2
), relation_intersect (r2
, r1
));
1793 ASSERT_EQ (relation_union (r1
, r2
), relation_union (r2
, r1
));
1797 } // namespace selftest
1799 #endif // CHECKING_P