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