1/* Support routines for value ranges with equivalences. 2 Copyright (C) 2020-2022 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 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" 29 30value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv, 31 value_range_kind kind) 32{ 33 m_equiv = NULL; 34 set (min, max, equiv, kind); 35} 36 37value_range_equiv::value_range_equiv (const value_range &other) 38{ 39 m_equiv = NULL; 40 set (other.min(), other.max (), NULL, other.kind ()); 41} 42 43void 44value_range_equiv::set (tree min, tree max, bitmap equiv, 45 value_range_kind kind) 46{ 47 value_range::set (min, max, kind); 48 set_equiv (equiv); 49 if (flag_checking) 50 check (); 51} 52 53void 54value_range_equiv::set (tree val) 55{ 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); 60} 61 62void 63value_range_equiv::set_undefined () 64{ 65 set (NULL, NULL, NULL, VR_UNDEFINED); 66} 67 68void 69value_range_equiv::set_varying (tree type) 70{ 71 value_range::set_varying (type); 72 equiv_clear (); 73} 74 75/* Like set, but keep the equivalences in place. */ 76 77void 78value_range_equiv::update (tree min, tree max, value_range_kind kind) 79{ 80 set (min, max, 81 (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL, kind); 82} 83 84/* Copy value_range in FROM into THIS while avoiding bitmap sharing. 85 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. */ 89 90void 91value_range_equiv::deep_copy (const value_range_equiv *from) 92{ 93 set (from->min (), from->max (), from->m_equiv, from->kind ()); 94} 95 96void 97value_range_equiv::move (value_range_equiv *from) 98{ 99 set (from->min (), from->max (), NULL, from->kind ()); 100 m_equiv = from->m_equiv; 101 from->m_equiv = NULL; 102} 103 104void 105value_range_equiv::set_equiv (bitmap equiv) 106{ 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. 111 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); 117 118 if (equiv != m_equiv) 119 { 120 if (equiv && !bitmap_empty_p (equiv)) 121 bitmap_copy (m_equiv, equiv); 122 else 123 bitmap_clear (m_equiv); 124 } 125} 126 127void 128value_range_equiv::check () 129{ 130 value_range::verify_range (); 131 switch (kind ()) 132 { 133 case VR_UNDEFINED: 134 case VR_VARYING: 135 gcc_assert (!m_equiv || bitmap_empty_p (m_equiv)); 136 default:; 137 } 138} 139 140/* Return true if the bitmaps B1 and B2 are equal. */ 141 142static bool 143vr_bitmap_equal_p (const_bitmap b1, const_bitmap b2) 144{ 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))); 150} 151 152/* Returns TRUE if THIS == OTHER. Ignores the equivalence bitmap if 153 IGNORE_EQUIVS is TRUE. */ 154 155bool 156value_range_equiv::equal_p (const value_range_equiv &other, 157 bool ignore_equivs) const 158{ 159 return (value_range::equal_p (other) 160 && (ignore_equivs || vr_bitmap_equal_p (m_equiv, other.m_equiv))); 161} 162 163void 164value_range_equiv::equiv_clear () 165{ 166 if (m_equiv) 167 bitmap_clear (m_equiv); 168} 169 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). 173 174 This is the central point where equivalence processing can be 175 turned on/off. */ 176 177void 178value_range_equiv::equiv_add (const_tree var, 179 const value_range_equiv *var_vr, 180 bitmap_obstack *obstack) 181{ 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); 188} 189 190void 191value_range_equiv::intersect (const value_range_equiv *other) 192{ 193 if (dump_file && (dump_flags & TDF_DETAILS)) 194 { 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"); 200 } 201 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 208 { 209 legacy_intersect (this, other); 210 if (varying_p () || undefined_p ()) 211 equiv_clear (); 212 213 /* If the result is VR_UNDEFINED there is no need to mess with 214 equivalencies. */ 215 if (!undefined_p ()) 216 { 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) 222 { 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); 228 } 229 } 230 } 231 232 if (dump_file && (dump_flags & TDF_DETAILS)) 233 { 234 fprintf (dump_file, "to\n "); 235 dump_value_range (dump_file, this); 236 fprintf (dump_file, "\n"); 237 } 238} 239 240void 241value_range_equiv::union_ (const value_range_equiv *other) 242{ 243 if (dump_file && (dump_flags & TDF_DETAILS)) 244 { 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"); 250 } 251 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 257 { 258 legacy_union (this, other); 259 if (varying_p () || undefined_p ()) 260 equiv_clear (); 261 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); 268 } 269 270 if (dump_file && (dump_flags & TDF_DETAILS)) 271 { 272 fprintf (dump_file, "to\n "); 273 dump_value_range (dump_file, this); 274 fprintf (dump_file, "\n"); 275 } 276} 277 278void 279value_range_equiv::dump (FILE *file) const 280{ 281 value_range::dump (file); 282 if ((kind () == VR_RANGE || kind () == VR_ANTI_RANGE) 283 && m_equiv) 284 { 285 bitmap_iterator bi; 286 unsigned i, c = 0; 287 288 fprintf (file, " EQUIVALENCES: { "); 289 EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi) 290 { 291 print_generic_expr (file, ssa_name (i)); 292 fprintf (file, " "); 293 c++; 294 } 295 fprintf (file, "} (%u elements)", c); 296 } 297} 298 299void 300value_range_equiv::dump () const 301{ 302 dump (stderr); 303} 304 305void 306dump_value_range (FILE *file, const value_range_equiv *vr) 307{ 308 if (!vr) 309 fprintf (file, "[]"); 310 else 311 vr->dump (file); 312} 313 314DEBUG_FUNCTION void 315debug (const value_range_equiv *vr) 316{ 317 dump_value_range (stderr, vr); 318} 319 320DEBUG_FUNCTION void 321debug (const value_range_equiv &vr) 322{ 323 dump_value_range (stderr, &vr); 324} 325