1 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_ANALYSIS_VALUELATTICE_H 10 #define LLVM_ANALYSIS_VALUELATTICE_H 11 12 #include "llvm/IR/ConstantRange.h" 13 #include "llvm/IR/Constants.h" 14 15 //===----------------------------------------------------------------------===// 16 // ValueLatticeElement 17 //===----------------------------------------------------------------------===// 18 19 namespace llvm { 20 21 /// This class represents lattice values for constants. 22 /// 23 /// FIXME: This is basically just for bringup, this can be made a lot more rich 24 /// in the future. 25 /// 26 class ValueLatticeElement { 27 enum ValueLatticeElementTy { 28 /// This Value has no known value yet. As a result, this implies the 29 /// producing instruction is dead. Caution: We use this as the starting 30 /// state in our local meet rules. In this usage, it's taken to mean 31 /// "nothing known yet". 32 /// Transition to any other state allowed. 33 unknown, 34 35 /// This Value is an UndefValue constant or produces undef. Undefined values 36 /// can be merged with constants (or single element constant ranges), 37 /// assuming all uses of the result will be replaced. 38 /// Transition allowed to the following states: 39 /// constant 40 /// constantrange_including_undef 41 /// overdefined 42 undef, 43 44 /// This Value has a specific constant value. The constant cannot be undef. 45 /// (For constant integers, constantrange is used instead. Integer typed 46 /// constantexprs can appear as constant.) Note that the constant state 47 /// can be reached by merging undef & constant states. 48 /// Transition allowed to the following states: 49 /// overdefined 50 constant, 51 52 /// This Value is known to not have the specified value. (For constant 53 /// integers, constantrange is used instead. As above, integer typed 54 /// constantexprs can appear here.) 55 /// Transition allowed to the following states: 56 /// overdefined 57 notconstant, 58 59 /// The Value falls within this range. (Used only for integer typed values.) 60 /// Transition allowed to the following states: 61 /// constantrange (new range must be a superset of the existing range) 62 /// constantrange_including_undef 63 /// overdefined 64 constantrange, 65 66 /// This Value falls within this range, but also may be undef. 67 /// Merging it with other constant ranges results in 68 /// constantrange_including_undef. 69 /// Transition allowed to the following states: 70 /// overdefined 71 constantrange_including_undef, 72 73 /// We can not precisely model the dynamic values this value might take. 74 /// No transitions are allowed after reaching overdefined. 75 overdefined, 76 }; 77 78 ValueLatticeElementTy Tag : 8; 79 /// Number of times a constant range has been extended with widening enabled. 80 unsigned NumRangeExtensions : 8; 81 82 /// The union either stores a pointer to a constant or a constant range, 83 /// associated to the lattice element. We have to ensure that Range is 84 /// initialized or destroyed when changing state to or from constantrange. 85 union { 86 Constant *ConstVal; 87 ConstantRange Range; 88 }; 89 90 /// Destroy contents of lattice value, without destructing the object. 91 void destroy() { 92 switch (Tag) { 93 case overdefined: 94 case unknown: 95 case undef: 96 case constant: 97 case notconstant: 98 break; 99 case constantrange_including_undef: 100 case constantrange: 101 Range.~ConstantRange(); 102 break; 103 }; 104 } 105 106 public: 107 /// Struct to control some aspects related to merging constant ranges. 108 struct MergeOptions { 109 /// The merge value may include undef. 110 bool MayIncludeUndef; 111 112 /// Handle repeatedly extending a range by going to overdefined after a 113 /// number of steps. 114 bool CheckWiden; 115 116 /// The number of allowed widening steps (including setting the range 117 /// initially). 118 unsigned MaxWidenSteps; 119 120 MergeOptions() : MergeOptions(false, false) {} 121 122 MergeOptions(bool MayIncludeUndef, bool CheckWiden, 123 unsigned MaxWidenSteps = 1) 124 : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden), 125 MaxWidenSteps(MaxWidenSteps) {} 126 127 MergeOptions &setMayIncludeUndef(bool V = true) { 128 MayIncludeUndef = V; 129 return *this; 130 } 131 132 MergeOptions &setCheckWiden(bool V = true) { 133 CheckWiden = V; 134 return *this; 135 } 136 137 MergeOptions &setMaxWidenSteps(unsigned Steps = 1) { 138 CheckWiden = true; 139 MaxWidenSteps = Steps; 140 return *this; 141 } 142 }; 143 144 // ConstVal and Range are initialized on-demand. 145 ValueLatticeElement() : Tag(unknown), NumRangeExtensions(0) {} 146 147 ~ValueLatticeElement() { destroy(); } 148 149 ValueLatticeElement(const ValueLatticeElement &Other) 150 : Tag(Other.Tag), NumRangeExtensions(0) { 151 switch (Other.Tag) { 152 case constantrange: 153 case constantrange_including_undef: 154 new (&Range) ConstantRange(Other.Range); 155 NumRangeExtensions = Other.NumRangeExtensions; 156 break; 157 case constant: 158 case notconstant: 159 ConstVal = Other.ConstVal; 160 break; 161 case overdefined: 162 case unknown: 163 case undef: 164 break; 165 } 166 } 167 168 ValueLatticeElement(ValueLatticeElement &&Other) 169 : Tag(Other.Tag), NumRangeExtensions(0) { 170 switch (Other.Tag) { 171 case constantrange: 172 case constantrange_including_undef: 173 new (&Range) ConstantRange(std::move(Other.Range)); 174 NumRangeExtensions = Other.NumRangeExtensions; 175 break; 176 case constant: 177 case notconstant: 178 ConstVal = Other.ConstVal; 179 break; 180 case overdefined: 181 case unknown: 182 case undef: 183 break; 184 } 185 Other.Tag = unknown; 186 } 187 188 ValueLatticeElement &operator=(const ValueLatticeElement &Other) { 189 destroy(); 190 new (this) ValueLatticeElement(Other); 191 return *this; 192 } 193 194 ValueLatticeElement &operator=(ValueLatticeElement &&Other) { 195 destroy(); 196 new (this) ValueLatticeElement(std::move(Other)); 197 return *this; 198 } 199 200 static ValueLatticeElement get(Constant *C) { 201 ValueLatticeElement Res; 202 Res.markConstant(C); 203 return Res; 204 } 205 static ValueLatticeElement getNot(Constant *C) { 206 ValueLatticeElement Res; 207 assert(!isa<UndefValue>(C) && "!= undef is not supported"); 208 Res.markNotConstant(C); 209 return Res; 210 } 211 static ValueLatticeElement getRange(ConstantRange CR, 212 bool MayIncludeUndef = false) { 213 if (CR.isFullSet()) 214 return getOverdefined(); 215 216 if (CR.isEmptySet()) { 217 ValueLatticeElement Res; 218 if (MayIncludeUndef) 219 Res.markUndef(); 220 return Res; 221 } 222 223 ValueLatticeElement Res; 224 Res.markConstantRange(std::move(CR), 225 MergeOptions().setMayIncludeUndef(MayIncludeUndef)); 226 return Res; 227 } 228 static ValueLatticeElement getOverdefined() { 229 ValueLatticeElement Res; 230 Res.markOverdefined(); 231 return Res; 232 } 233 234 bool isUndef() const { return Tag == undef; } 235 bool isUnknown() const { return Tag == unknown; } 236 bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; } 237 bool isConstant() const { return Tag == constant; } 238 bool isNotConstant() const { return Tag == notconstant; } 239 bool isConstantRangeIncludingUndef() const { 240 return Tag == constantrange_including_undef; 241 } 242 /// Returns true if this value is a constant range. Use \p UndefAllowed to 243 /// exclude non-singleton constant ranges that may also be undef. Note that 244 /// this function also returns true if the range may include undef, but only 245 /// contains a single element. In that case, it can be replaced by a constant. 246 bool isConstantRange(bool UndefAllowed = true) const { 247 return Tag == constantrange || (Tag == constantrange_including_undef && 248 (UndefAllowed || Range.isSingleElement())); 249 } 250 bool isOverdefined() const { return Tag == overdefined; } 251 252 Constant *getConstant() const { 253 assert(isConstant() && "Cannot get the constant of a non-constant!"); 254 return ConstVal; 255 } 256 257 Constant *getNotConstant() const { 258 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); 259 return ConstVal; 260 } 261 262 /// Returns the constant range for this value. Use \p UndefAllowed to exclude 263 /// non-singleton constant ranges that may also be undef. Note that this 264 /// function also returns a range if the range may include undef, but only 265 /// contains a single element. In that case, it can be replaced by a constant. 266 const ConstantRange &getConstantRange(bool UndefAllowed = true) const { 267 assert(isConstantRange(UndefAllowed) && 268 "Cannot get the constant-range of a non-constant-range!"); 269 return Range; 270 } 271 272 std::optional<APInt> asConstantInteger() const { 273 if (isConstant() && isa<ConstantInt>(getConstant())) { 274 return cast<ConstantInt>(getConstant())->getValue(); 275 } else if (isConstantRange() && getConstantRange().isSingleElement()) { 276 return *getConstantRange().getSingleElement(); 277 } 278 return std::nullopt; 279 } 280 281 ConstantRange asConstantRange(unsigned BW, bool UndefAllowed = false) const { 282 if (isConstantRange(UndefAllowed)) 283 return getConstantRange(); 284 if (isConstant()) 285 return getConstant()->toConstantRange(); 286 if (isUnknown()) 287 return ConstantRange::getEmpty(BW); 288 return ConstantRange::getFull(BW); 289 } 290 291 ConstantRange asConstantRange(Type *Ty, bool UndefAllowed = false) const { 292 assert(Ty->isIntOrIntVectorTy() && "Must be integer type"); 293 return asConstantRange(Ty->getScalarSizeInBits(), UndefAllowed); 294 } 295 296 bool markOverdefined() { 297 if (isOverdefined()) 298 return false; 299 destroy(); 300 Tag = overdefined; 301 return true; 302 } 303 304 bool markUndef() { 305 if (isUndef()) 306 return false; 307 308 assert(isUnknown()); 309 Tag = undef; 310 return true; 311 } 312 313 bool markConstant(Constant *V, bool MayIncludeUndef = false) { 314 if (isa<UndefValue>(V)) 315 return markUndef(); 316 317 if (isConstant()) { 318 assert(getConstant() == V && "Marking constant with different value"); 319 return false; 320 } 321 322 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 323 return markConstantRange( 324 ConstantRange(CI->getValue()), 325 MergeOptions().setMayIncludeUndef(MayIncludeUndef)); 326 327 assert(isUnknown() || isUndef()); 328 Tag = constant; 329 ConstVal = V; 330 return true; 331 } 332 333 bool markNotConstant(Constant *V) { 334 assert(V && "Marking constant with NULL"); 335 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 336 return markConstantRange( 337 ConstantRange(CI->getValue() + 1, CI->getValue())); 338 339 if (isa<UndefValue>(V)) 340 return false; 341 342 if (isNotConstant()) { 343 assert(getNotConstant() == V && "Marking !constant with different value"); 344 return false; 345 } 346 347 assert(isUnknown()); 348 Tag = notconstant; 349 ConstVal = V; 350 return true; 351 } 352 353 /// Mark the object as constant range with \p NewR. If the object is already a 354 /// constant range, nothing changes if the existing range is equal to \p 355 /// NewR and the tag. Otherwise \p NewR must be a superset of the existing 356 /// range or the object must be undef. The tag is set to 357 /// constant_range_including_undef if either the existing value or the new 358 /// range may include undef. 359 bool markConstantRange(ConstantRange NewR, 360 MergeOptions Opts = MergeOptions()) { 361 assert(!NewR.isEmptySet() && "should only be called for non-empty sets"); 362 363 if (NewR.isFullSet()) 364 return markOverdefined(); 365 366 ValueLatticeElementTy OldTag = Tag; 367 ValueLatticeElementTy NewTag = 368 (isUndef() || isConstantRangeIncludingUndef() || Opts.MayIncludeUndef) 369 ? constantrange_including_undef 370 : constantrange; 371 if (isConstantRange()) { 372 Tag = NewTag; 373 if (getConstantRange() == NewR) 374 return Tag != OldTag; 375 376 // Simple form of widening. If a range is extended multiple times, go to 377 // overdefined. 378 if (Opts.CheckWiden && ++NumRangeExtensions > Opts.MaxWidenSteps) 379 return markOverdefined(); 380 381 assert(NewR.contains(getConstantRange()) && 382 "Existing range must be a subset of NewR"); 383 Range = std::move(NewR); 384 return true; 385 } 386 387 assert(isUnknown() || isUndef() || isConstant()); 388 assert((!isConstant() || NewR.contains(getConstant()->toConstantRange())) && 389 "Constant must be subset of new range"); 390 391 NumRangeExtensions = 0; 392 Tag = NewTag; 393 new (&Range) ConstantRange(std::move(NewR)); 394 return true; 395 } 396 397 /// Updates this object to approximate both this object and RHS. Returns 398 /// true if this object has been changed. 399 bool mergeIn(const ValueLatticeElement &RHS, 400 MergeOptions Opts = MergeOptions()) { 401 if (RHS.isUnknown() || isOverdefined()) 402 return false; 403 if (RHS.isOverdefined()) { 404 markOverdefined(); 405 return true; 406 } 407 408 if (isUndef()) { 409 assert(!RHS.isUnknown()); 410 if (RHS.isUndef()) 411 return false; 412 if (RHS.isConstant()) 413 return markConstant(RHS.getConstant(), true); 414 if (RHS.isConstantRange()) 415 return markConstantRange(RHS.getConstantRange(true), 416 Opts.setMayIncludeUndef()); 417 return markOverdefined(); 418 } 419 420 if (isUnknown()) { 421 assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier"); 422 *this = RHS; 423 return true; 424 } 425 426 if (isConstant()) { 427 if (RHS.isConstant() && getConstant() == RHS.getConstant()) 428 return false; 429 if (RHS.isUndef()) 430 return false; 431 // If the constant is a vector of integers, try to treat it as a range. 432 if (getConstant()->getType()->isVectorTy() && 433 getConstant()->getType()->getScalarType()->isIntegerTy()) { 434 ConstantRange L = getConstant()->toConstantRange(); 435 ConstantRange NewR = L.unionWith( 436 RHS.asConstantRange(L.getBitWidth(), /*UndefAllowed=*/true)); 437 return markConstantRange( 438 std::move(NewR), 439 Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef())); 440 } 441 markOverdefined(); 442 return true; 443 } 444 445 if (isNotConstant()) { 446 if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant()) 447 return false; 448 markOverdefined(); 449 return true; 450 } 451 452 auto OldTag = Tag; 453 assert(isConstantRange() && "New ValueLattice type?"); 454 if (RHS.isUndef()) { 455 Tag = constantrange_including_undef; 456 return OldTag != Tag; 457 } 458 459 const ConstantRange &L = getConstantRange(); 460 ConstantRange NewR = L.unionWith( 461 RHS.asConstantRange(L.getBitWidth(), /*UndefAllowed=*/true)); 462 return markConstantRange( 463 std::move(NewR), 464 Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef())); 465 } 466 467 // Compares this symbolic value with Other using Pred and returns either 468 /// true, false or undef constants, or nullptr if the comparison cannot be 469 /// evaluated. 470 Constant *getCompare(CmpInst::Predicate Pred, Type *Ty, 471 const ValueLatticeElement &Other, 472 const DataLayout &DL) const; 473 474 /// Combine two sets of facts about the same value into a single set of 475 /// facts. Note that this method is not suitable for merging facts along 476 /// different paths in a CFG; that's what the mergeIn function is for. This 477 /// is for merging facts gathered about the same value at the same location 478 /// through two independent means. 479 /// Notes: 480 /// * This method does not promise to return the most precise possible lattice 481 /// value implied by A and B. It is allowed to return any lattice element 482 /// which is at least as strong as *either* A or B (unless our facts 483 /// conflict, see below). 484 /// * Due to unreachable code, the intersection of two lattice values could be 485 /// contradictory. If this happens, we return some valid lattice value so 486 /// as not confuse the rest of LVI. Ideally, we'd always return Undefined, 487 /// but we do not make this guarantee. TODO: This would be a useful 488 /// enhancement. 489 ValueLatticeElement intersect(const ValueLatticeElement &Other) const; 490 491 unsigned getNumRangeExtensions() const { return NumRangeExtensions; } 492 void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; } 493 }; 494 495 static_assert(sizeof(ValueLatticeElement) <= 40, 496 "size of ValueLatticeElement changed unexpectedly"); 497 498 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val); 499 } // end namespace llvm 500 #endif 501