Daily bump.
[official-gcc.git] / gcc / value-range-equiv.cc
blob255776828ab0cb3ff2c5e7514abf6e93cd3dfa95
1 /* Support routines for value ranges with equivalences.
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "ssa.h"
27 #include "tree-pretty-print.h"
28 #include "value-range-equiv.h"
30 value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv,
31 value_range_kind kind)
33 m_equiv = NULL;
34 set (min, max, equiv, kind);
37 value_range_equiv::value_range_equiv (const value_range &other)
39 m_equiv = NULL;
40 set (other.min(), other.max (), NULL, other.kind ());
43 void
44 value_range_equiv::set (tree min, tree max, bitmap equiv,
45 value_range_kind kind)
47 value_range::set (min, max, kind);
48 set_equiv (equiv);
49 if (flag_checking)
50 check ();
53 void
54 value_range_equiv::set (tree val)
56 gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
57 if (TREE_OVERFLOW_P (val))
58 val = drop_tree_overflow (val);
59 set (val, val);
62 void
63 value_range_equiv::set_undefined ()
65 set (NULL, NULL, NULL, VR_UNDEFINED);
68 void
69 value_range_equiv::set_varying (tree type)
71 value_range::set_varying (type);
72 equiv_clear ();
75 /* Like set, but keep the equivalences in place. */
77 void
78 value_range_equiv::update (tree min, tree max, value_range_kind kind)
80 set (min, max,
81 (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL, kind);
84 /* Copy value_range in FROM into THIS while avoiding bitmap sharing.
86 Note: The code that avoids the bitmap sharing looks at the existing
87 this->m_equiv, so this function cannot be used to initalize an
88 object. Use the constructors for initialization. */
90 void
91 value_range_equiv::deep_copy (const value_range_equiv *from)
93 set (from->min (), from->max (), from->m_equiv, from->kind ());
96 void
97 value_range_equiv::move (value_range_equiv *from)
99 set (from->min (), from->max (), NULL, from->kind ());
100 m_equiv = from->m_equiv;
101 from->m_equiv = NULL;
104 void
105 value_range_equiv::set_equiv (bitmap equiv)
107 if (undefined_p () || varying_p ())
108 equiv = NULL;
109 /* Since updating the equivalence set involves deep copying the
110 bitmaps, only do it if absolutely necessary.
112 All equivalence bitmaps are allocated from the same obstack. So
113 we can use the obstack associated with EQUIV to allocate vr->equiv. */
114 if (m_equiv == NULL
115 && equiv != NULL)
116 m_equiv = BITMAP_ALLOC (equiv->obstack);
118 if (equiv != m_equiv)
120 if (equiv && !bitmap_empty_p (equiv))
121 bitmap_copy (m_equiv, equiv);
122 else
123 bitmap_clear (m_equiv);
127 void
128 value_range_equiv::check ()
130 value_range::verify_range ();
131 switch (kind ())
133 case VR_UNDEFINED:
134 case VR_VARYING:
135 gcc_assert (!m_equiv || bitmap_empty_p (m_equiv));
136 default:;
140 /* Return true if the bitmaps B1 and B2 are equal. */
142 static bool
143 vr_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
145 return (b1 == b2
146 || ((!b1 || bitmap_empty_p (b1))
147 && (!b2 || bitmap_empty_p (b2)))
148 || (b1 && b2
149 && bitmap_equal_p (b1, b2)));
152 /* Returns TRUE if THIS == OTHER. Ignores the equivalence bitmap if
153 IGNORE_EQUIVS is TRUE. */
155 bool
156 value_range_equiv::equal_p (const value_range_equiv &other,
157 bool ignore_equivs) const
159 return (value_range::equal_p (other)
160 && (ignore_equivs || vr_bitmap_equal_p (m_equiv, other.m_equiv)));
163 void
164 value_range_equiv::equiv_clear ()
166 if (m_equiv)
167 bitmap_clear (m_equiv);
170 /* Add VAR and VAR's equivalence set (VAR_VR) to the equivalence
171 bitmap. If no equivalence table has been created, OBSTACK is the
172 obstack to use (NULL for the default obstack).
174 This is the central point where equivalence processing can be
175 turned on/off. */
177 void
178 value_range_equiv::equiv_add (const_tree var,
179 const value_range_equiv *var_vr,
180 bitmap_obstack *obstack)
182 if (!m_equiv)
183 m_equiv = BITMAP_ALLOC (obstack);
184 unsigned ver = SSA_NAME_VERSION (var);
185 bitmap_set_bit (m_equiv, ver);
186 if (var_vr && var_vr->m_equiv)
187 bitmap_ior_into (m_equiv, var_vr->m_equiv);
190 void
191 value_range_equiv::intersect (const value_range_equiv *other)
193 if (dump_file && (dump_flags & TDF_DETAILS))
195 fprintf (dump_file, "Intersecting\n ");
196 dump_value_range (dump_file, this);
197 fprintf (dump_file, "\nand\n ");
198 dump_value_range (dump_file, other);
199 fprintf (dump_file, "\n");
202 /* If THIS is varying we want to pick up equivalences from OTHER.
203 Just special-case this here rather than trying to fixup after the
204 fact. */
205 if (this->varying_p ())
206 this->deep_copy (other);
207 else
209 legacy_intersect (this, other);
210 if (varying_p () || undefined_p ())
211 equiv_clear ();
213 /* If the result is VR_UNDEFINED there is no need to mess with
214 equivalencies. */
215 if (!undefined_p ())
217 /* The resulting set of equivalences for range intersection
218 is the union of the two sets. */
219 if (m_equiv && other->m_equiv && m_equiv != other->m_equiv)
220 bitmap_ior_into (m_equiv, other->m_equiv);
221 else if (other->m_equiv && !m_equiv)
223 /* All equivalence bitmaps are allocated from the same
224 obstack. So we can use the obstack associated with
225 VR to allocate this->m_equiv. */
226 m_equiv = BITMAP_ALLOC (other->m_equiv->obstack);
227 bitmap_copy (m_equiv, other->m_equiv);
232 if (dump_file && (dump_flags & TDF_DETAILS))
234 fprintf (dump_file, "to\n ");
235 dump_value_range (dump_file, this);
236 fprintf (dump_file, "\n");
240 void
241 value_range_equiv::union_ (const value_range_equiv *other)
243 if (dump_file && (dump_flags & TDF_DETAILS))
245 fprintf (dump_file, "Meeting\n ");
246 dump_value_range (dump_file, this);
247 fprintf (dump_file, "\nand\n ");
248 dump_value_range (dump_file, other);
249 fprintf (dump_file, "\n");
252 /* If THIS is undefined we want to pick up equivalences from OTHER.
253 Just special-case this here rather than trying to fixup after the fact. */
254 if (this->undefined_p ())
255 this->deep_copy (other);
256 else
258 legacy_union (this, other);
259 if (varying_p () || undefined_p ())
260 equiv_clear ();
262 /* The resulting set of equivalences is always the intersection of
263 the two sets. */
264 if (this->m_equiv && other->m_equiv && this->m_equiv != other->m_equiv)
265 bitmap_and_into (this->m_equiv, other->m_equiv);
266 else if (this->m_equiv && !other->m_equiv)
267 bitmap_clear (this->m_equiv);
270 if (dump_file && (dump_flags & TDF_DETAILS))
272 fprintf (dump_file, "to\n ");
273 dump_value_range (dump_file, this);
274 fprintf (dump_file, "\n");
278 void
279 value_range_equiv::dump (FILE *file) const
281 value_range::dump (file);
282 if ((kind () == VR_RANGE || kind () == VR_ANTI_RANGE)
283 && m_equiv)
285 bitmap_iterator bi;
286 unsigned i, c = 0;
288 fprintf (file, " EQUIVALENCES: { ");
289 EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi)
291 print_generic_expr (file, ssa_name (i));
292 fprintf (file, " ");
293 c++;
295 fprintf (file, "} (%u elements)", c);
299 void
300 value_range_equiv::dump () const
302 dump (stderr);
305 void
306 dump_value_range (FILE *file, const value_range_equiv *vr)
308 if (!vr)
309 fprintf (file, "[]");
310 else
311 vr->dump (file);
314 DEBUG_FUNCTION void
315 debug (const value_range_equiv *vr)
317 dump_value_range (stderr, vr);
320 DEBUG_FUNCTION void
321 debug (const value_range_equiv &vr)
323 dump_value_range (stderr, &vr);