ValueLattice.h revision 363496
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/// This class represents lattice values for constants. 20/// 21/// FIXME: This is basically just for bringup, this can be made a lot more rich 22/// in the future. 23/// 24 25namespace llvm { 26class 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 unknown, 33 34 /// This Value has a specific constant value. (For constant integers, 35 /// constantrange is used instead. Integer typed constantexprs can appear 36 /// as constant.) 37 constant, 38 39 /// This Value is known to not have the specified value. (For constant 40 /// integers, constantrange is used instead. As above, integer typed 41 /// constantexprs can appear here.) 42 notconstant, 43 44 /// The Value falls within this range. (Used only for integer typed values.) 45 constantrange, 46 47 /// We can not precisely model the dynamic values this value might take. 48 overdefined, 49 50 /// This Value is an UndefValue constant or produces undef. Undefined values 51 /// can be merged with constants (or single element constant ranges), 52 /// assuming all uses of the result will be replaced. 53 undef 54 }; 55 56 ValueLatticeElementTy Tag; 57 58 /// The union either stores a pointer to a constant or a constant range, 59 /// associated to the lattice element. We have to ensure that Range is 60 /// initialized or destroyed when changing state to or from constantrange. 61 union { 62 Constant *ConstVal; 63 ConstantRange Range; 64 }; 65 66public: 67 // Const and Range are initialized on-demand. 68 ValueLatticeElement() : Tag(unknown) {} 69 70 /// Custom destructor to ensure Range is properly destroyed, when the object 71 /// is deallocated. 72 ~ValueLatticeElement() { 73 switch (Tag) { 74 case overdefined: 75 case unknown: 76 case undef: 77 case constant: 78 case notconstant: 79 break; 80 case constantrange: 81 Range.~ConstantRange(); 82 break; 83 }; 84 } 85 86 /// Custom copy constructor, to ensure Range gets initialized when 87 /// copying a constant range lattice element. 88 ValueLatticeElement(const ValueLatticeElement &Other) : Tag(unknown) { 89 *this = Other; 90 } 91 92 /// Custom assignment operator, to ensure Range gets initialized when 93 /// assigning a constant range lattice element. 94 ValueLatticeElement &operator=(const ValueLatticeElement &Other) { 95 // If we change the state of this from constant range to non constant range, 96 // destroy Range. 97 if (isConstantRange() && !Other.isConstantRange()) 98 Range.~ConstantRange(); 99 100 // If we change the state of this from a valid ConstVal to another a state 101 // without a valid ConstVal, zero the pointer. 102 if ((isConstant() || isNotConstant()) && !Other.isConstant() && 103 !Other.isNotConstant()) 104 ConstVal = nullptr; 105 106 switch (Other.Tag) { 107 case constantrange: 108 if (!isConstantRange()) 109 new (&Range) ConstantRange(Other.Range); 110 else 111 Range = Other.Range; 112 break; 113 case constant: 114 case notconstant: 115 ConstVal = Other.ConstVal; 116 break; 117 case overdefined: 118 case unknown: 119 case undef: 120 break; 121 } 122 Tag = Other.Tag; 123 return *this; 124 } 125 126 static ValueLatticeElement get(Constant *C) { 127 ValueLatticeElement Res; 128 if (isa<UndefValue>(C)) 129 Res.markUndef(); 130 else 131 Res.markConstant(C); 132 return Res; 133 } 134 static ValueLatticeElement getNot(Constant *C) { 135 ValueLatticeElement Res; 136 assert(!isa<UndefValue>(C) && "!= undef is not supported"); 137 Res.markNotConstant(C); 138 return Res; 139 } 140 static ValueLatticeElement getRange(ConstantRange CR) { 141 ValueLatticeElement Res; 142 Res.markConstantRange(std::move(CR)); 143 return Res; 144 } 145 static ValueLatticeElement getOverdefined() { 146 ValueLatticeElement Res; 147 Res.markOverdefined(); 148 return Res; 149 } 150 151 bool isUndef() const { return Tag == undef; } 152 bool isUnknown() const { return Tag == unknown; } 153 bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; } 154 bool isUndefined() const { return isUnknownOrUndef(); } 155 bool isConstant() const { return Tag == constant; } 156 bool isNotConstant() const { return Tag == notconstant; } 157 bool isConstantRange() const { return Tag == constantrange; } 158 bool isOverdefined() const { return Tag == overdefined; } 159 160 Constant *getConstant() const { 161 assert(isConstant() && "Cannot get the constant of a non-constant!"); 162 return ConstVal; 163 } 164 165 Constant *getNotConstant() const { 166 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); 167 return ConstVal; 168 } 169 170 const ConstantRange &getConstantRange() const { 171 assert(isConstantRange() && 172 "Cannot get the constant-range of a non-constant-range!"); 173 return Range; 174 } 175 176 Optional<APInt> asConstantInteger() const { 177 if (isConstant() && isa<ConstantInt>(getConstant())) { 178 return cast<ConstantInt>(getConstant())->getValue(); 179 } else if (isConstantRange() && getConstantRange().isSingleElement()) { 180 return *getConstantRange().getSingleElement(); 181 } 182 return None; 183 } 184 185 bool markOverdefined() { 186 if (isOverdefined()) 187 return false; 188 if (isConstant() || isNotConstant()) 189 ConstVal = nullptr; 190 if (isConstantRange()) 191 Range.~ConstantRange(); 192 Tag = overdefined; 193 return true; 194 } 195 196 bool markUndef() { 197 if (isUndef()) 198 return false; 199 200 assert(isUnknown()); 201 Tag = undef; 202 return true; 203 } 204 205 bool markConstant(Constant *V) { 206 if (isa<UndefValue>(V)) 207 return markUndef(); 208 209 if (isConstant()) { 210 assert(getConstant() == V && "Marking constant with different value"); 211 return false; 212 } 213 214 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 215 return markConstantRange(ConstantRange(CI->getValue())); 216 217 assert(isUnknown() || isUndef()); 218 Tag = constant; 219 ConstVal = V; 220 return true; 221 } 222 223 bool markNotConstant(Constant *V) { 224 assert(V && "Marking constant with NULL"); 225 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 226 return markConstantRange( 227 ConstantRange(CI->getValue() + 1, CI->getValue())); 228 229 if (isa<UndefValue>(V)) 230 return false; 231 232 if (isNotConstant()) { 233 assert(getNotConstant() == V && "Marking !constant with different value"); 234 return false; 235 } 236 237 assert(isUnknown()); 238 Tag = notconstant; 239 ConstVal = V; 240 return true; 241 } 242 243 /// Mark the object as constant range with \p NewR. If the object is already a 244 /// constant range, nothing changes if the existing range is equal to \p 245 /// NewR. Otherwise \p NewR must be a superset of the existing range or the 246 /// object must be undef. 247 bool markConstantRange(ConstantRange NewR) { 248 if (isConstantRange()) { 249 if (getConstantRange() == NewR) 250 return false; 251 252 if (NewR.isEmptySet()) 253 return markOverdefined(); 254 255 assert(NewR.contains(getConstantRange()) && 256 "Existing range must be a subset of NewR"); 257 Range = std::move(NewR); 258 return true; 259 } 260 261 assert(isUnknown() || isUndef()); 262 if (NewR.isEmptySet()) 263 return markOverdefined(); 264 265 Tag = constantrange; 266 new (&Range) ConstantRange(std::move(NewR)); 267 return true; 268 } 269 270 /// Updates this object to approximate both this object and RHS. Returns 271 /// true if this object has been changed. 272 bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) { 273 if (RHS.isUnknown() || isOverdefined()) 274 return false; 275 if (RHS.isOverdefined()) { 276 markOverdefined(); 277 return true; 278 } 279 280 if (isUndef()) { 281 assert(!RHS.isUnknown()); 282 if (RHS.isUndef()) 283 return false; 284 if (RHS.isConstant()) 285 return markConstant(RHS.getConstant()); 286 if (RHS.isConstantRange() && RHS.getConstantRange().isSingleElement()) 287 return markConstantRange(RHS.getConstantRange()); 288 return markOverdefined(); 289 } 290 291 if (isUnknown()) { 292 assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier"); 293 *this = RHS; 294 return true; 295 } 296 297 if (isConstant()) { 298 if (RHS.isConstant() && getConstant() == RHS.getConstant()) 299 return false; 300 if (RHS.isUndef()) 301 return false; 302 markOverdefined(); 303 return true; 304 } 305 306 if (isNotConstant()) { 307 if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant()) 308 return false; 309 markOverdefined(); 310 return true; 311 } 312 313 assert(isConstantRange() && "New ValueLattice type?"); 314 if (RHS.isUndef() && getConstantRange().isSingleElement()) 315 return false; 316 317 if (!RHS.isConstantRange()) { 318 // We can get here if we've encountered a constantexpr of integer type 319 // and merge it with a constantrange. 320 markOverdefined(); 321 return true; 322 } 323 ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange()); 324 if (NewR.isFullSet()) 325 return markOverdefined(); 326 else if (NewR == getConstantRange()) 327 return false; 328 else 329 return markConstantRange(std::move(NewR)); 330 } 331 332 /// Compares this symbolic value with Other using Pred and returns either 333 /// true, false or undef constants, or nullptr if the comparison cannot be 334 /// evaluated. 335 Constant *getCompare(CmpInst::Predicate Pred, Type *Ty, 336 const ValueLatticeElement &Other) const { 337 if (isUnknownOrUndef() || Other.isUnknownOrUndef()) 338 return UndefValue::get(Ty); 339 340 if (isConstant() && Other.isConstant()) 341 return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant()); 342 343 // Integer constants are represented as ConstantRanges with single 344 // elements. 345 if (!isConstantRange() || !Other.isConstantRange()) 346 return nullptr; 347 348 const auto &CR = getConstantRange(); 349 const auto &OtherCR = Other.getConstantRange(); 350 if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR)) 351 return ConstantInt::getTrue(Ty); 352 if (ConstantRange::makeSatisfyingICmpRegion( 353 CmpInst::getInversePredicate(Pred), OtherCR) 354 .contains(CR)) 355 return ConstantInt::getFalse(Ty); 356 357 return nullptr; 358 } 359}; 360 361raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val); 362 363} // end namespace llvm 364#endif 365