1326938Sdim//===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===// 2326938Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6326938Sdim// 7326938Sdim//===----------------------------------------------------------------------===// 8326938Sdim 9326938Sdim#ifndef LLVM_ANALYSIS_VALUELATTICE_H 10326938Sdim#define LLVM_ANALYSIS_VALUELATTICE_H 11326938Sdim 12326938Sdim#include "llvm/IR/ConstantRange.h" 13326938Sdim#include "llvm/IR/Constants.h" 14326938Sdim// 15326938Sdim//===----------------------------------------------------------------------===// 16326938Sdim// ValueLatticeElement 17326938Sdim//===----------------------------------------------------------------------===// 18326938Sdim 19326938Sdim/// This class represents lattice values for constants. 20326938Sdim/// 21326938Sdim/// FIXME: This is basically just for bringup, this can be made a lot more rich 22326938Sdim/// in the future. 23326938Sdim/// 24326938Sdim 25326938Sdimnamespace llvm { 26326938Sdimclass ValueLatticeElement { 27326938Sdim enum ValueLatticeElementTy { 28326938Sdim /// This Value has no known value yet. As a result, this implies the 29326938Sdim /// producing instruction is dead. Caution: We use this as the starting 30326938Sdim /// state in our local meet rules. In this usage, it's taken to mean 31326938Sdim /// "nothing known yet". 32363496Sdim unknown, 33326938Sdim 34326938Sdim /// This Value has a specific constant value. (For constant integers, 35326938Sdim /// constantrange is used instead. Integer typed constantexprs can appear 36326938Sdim /// as constant.) 37326938Sdim constant, 38326938Sdim 39326938Sdim /// This Value is known to not have the specified value. (For constant 40326938Sdim /// integers, constantrange is used instead. As above, integer typed 41326938Sdim /// constantexprs can appear here.) 42326938Sdim notconstant, 43326938Sdim 44326938Sdim /// The Value falls within this range. (Used only for integer typed values.) 45326938Sdim constantrange, 46326938Sdim 47326938Sdim /// We can not precisely model the dynamic values this value might take. 48363496Sdim overdefined, 49363496Sdim 50363496Sdim /// This Value is an UndefValue constant or produces undef. Undefined values 51363496Sdim /// can be merged with constants (or single element constant ranges), 52363496Sdim /// assuming all uses of the result will be replaced. 53363496Sdim undef 54326938Sdim }; 55326938Sdim 56326938Sdim ValueLatticeElementTy Tag; 57326938Sdim 58341825Sdim /// The union either stores a pointer to a constant or a constant range, 59341825Sdim /// associated to the lattice element. We have to ensure that Range is 60341825Sdim /// initialized or destroyed when changing state to or from constantrange. 61341825Sdim union { 62341825Sdim Constant *ConstVal; 63341825Sdim ConstantRange Range; 64341825Sdim }; 65341825Sdim 66326938Sdimpublic: 67341825Sdim // Const and Range are initialized on-demand. 68363496Sdim ValueLatticeElement() : Tag(unknown) {} 69326938Sdim 70341825Sdim /// Custom destructor to ensure Range is properly destroyed, when the object 71341825Sdim /// is deallocated. 72341825Sdim ~ValueLatticeElement() { 73341825Sdim switch (Tag) { 74341825Sdim case overdefined: 75363496Sdim case unknown: 76363496Sdim case undef: 77341825Sdim case constant: 78341825Sdim case notconstant: 79341825Sdim break; 80341825Sdim case constantrange: 81341825Sdim Range.~ConstantRange(); 82341825Sdim break; 83341825Sdim }; 84341825Sdim } 85341825Sdim 86341825Sdim /// Custom copy constructor, to ensure Range gets initialized when 87341825Sdim /// copying a constant range lattice element. 88363496Sdim ValueLatticeElement(const ValueLatticeElement &Other) : Tag(unknown) { 89341825Sdim *this = Other; 90341825Sdim } 91341825Sdim 92341825Sdim /// Custom assignment operator, to ensure Range gets initialized when 93341825Sdim /// assigning a constant range lattice element. 94341825Sdim ValueLatticeElement &operator=(const ValueLatticeElement &Other) { 95341825Sdim // If we change the state of this from constant range to non constant range, 96341825Sdim // destroy Range. 97341825Sdim if (isConstantRange() && !Other.isConstantRange()) 98341825Sdim Range.~ConstantRange(); 99341825Sdim 100341825Sdim // If we change the state of this from a valid ConstVal to another a state 101341825Sdim // without a valid ConstVal, zero the pointer. 102341825Sdim if ((isConstant() || isNotConstant()) && !Other.isConstant() && 103341825Sdim !Other.isNotConstant()) 104341825Sdim ConstVal = nullptr; 105341825Sdim 106341825Sdim switch (Other.Tag) { 107341825Sdim case constantrange: 108341825Sdim if (!isConstantRange()) 109341825Sdim new (&Range) ConstantRange(Other.Range); 110341825Sdim else 111341825Sdim Range = Other.Range; 112341825Sdim break; 113341825Sdim case constant: 114341825Sdim case notconstant: 115341825Sdim ConstVal = Other.ConstVal; 116341825Sdim break; 117341825Sdim case overdefined: 118363496Sdim case unknown: 119363496Sdim case undef: 120341825Sdim break; 121341825Sdim } 122341825Sdim Tag = Other.Tag; 123341825Sdim return *this; 124341825Sdim } 125341825Sdim 126326938Sdim static ValueLatticeElement get(Constant *C) { 127326938Sdim ValueLatticeElement Res; 128363496Sdim if (isa<UndefValue>(C)) 129363496Sdim Res.markUndef(); 130363496Sdim else 131326938Sdim Res.markConstant(C); 132326938Sdim return Res; 133326938Sdim } 134326938Sdim static ValueLatticeElement getNot(Constant *C) { 135326938Sdim ValueLatticeElement Res; 136363496Sdim assert(!isa<UndefValue>(C) && "!= undef is not supported"); 137363496Sdim Res.markNotConstant(C); 138326938Sdim return Res; 139326938Sdim } 140326938Sdim static ValueLatticeElement getRange(ConstantRange CR) { 141326938Sdim ValueLatticeElement Res; 142326938Sdim Res.markConstantRange(std::move(CR)); 143326938Sdim return Res; 144326938Sdim } 145326938Sdim static ValueLatticeElement getOverdefined() { 146326938Sdim ValueLatticeElement Res; 147326938Sdim Res.markOverdefined(); 148326938Sdim return Res; 149326938Sdim } 150326938Sdim 151363496Sdim bool isUndef() const { return Tag == undef; } 152363496Sdim bool isUnknown() const { return Tag == unknown; } 153363496Sdim bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; } 154363496Sdim bool isUndefined() const { return isUnknownOrUndef(); } 155326938Sdim bool isConstant() const { return Tag == constant; } 156326938Sdim bool isNotConstant() const { return Tag == notconstant; } 157326938Sdim bool isConstantRange() const { return Tag == constantrange; } 158326938Sdim bool isOverdefined() const { return Tag == overdefined; } 159326938Sdim 160326938Sdim Constant *getConstant() const { 161326938Sdim assert(isConstant() && "Cannot get the constant of a non-constant!"); 162341825Sdim return ConstVal; 163326938Sdim } 164326938Sdim 165326938Sdim Constant *getNotConstant() const { 166326938Sdim assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); 167341825Sdim return ConstVal; 168326938Sdim } 169326938Sdim 170326938Sdim const ConstantRange &getConstantRange() const { 171326938Sdim assert(isConstantRange() && 172326938Sdim "Cannot get the constant-range of a non-constant-range!"); 173326938Sdim return Range; 174326938Sdim } 175326938Sdim 176326938Sdim Optional<APInt> asConstantInteger() const { 177341825Sdim if (isConstant() && isa<ConstantInt>(getConstant())) { 178341825Sdim return cast<ConstantInt>(getConstant())->getValue(); 179341825Sdim } else if (isConstantRange() && getConstantRange().isSingleElement()) { 180341825Sdim return *getConstantRange().getSingleElement(); 181326938Sdim } 182326938Sdim return None; 183326938Sdim } 184326938Sdim 185363496Sdim bool markOverdefined() { 186326938Sdim if (isOverdefined()) 187363496Sdim return false; 188341825Sdim if (isConstant() || isNotConstant()) 189341825Sdim ConstVal = nullptr; 190341825Sdim if (isConstantRange()) 191341825Sdim Range.~ConstantRange(); 192326938Sdim Tag = overdefined; 193363496Sdim return true; 194326938Sdim } 195326938Sdim 196363496Sdim bool markUndef() { 197363496Sdim if (isUndef()) 198363496Sdim return false; 199363496Sdim 200363496Sdim assert(isUnknown()); 201363496Sdim Tag = undef; 202363496Sdim return true; 203363496Sdim } 204363496Sdim 205363496Sdim bool markConstant(Constant *V) { 206326938Sdim if (isa<UndefValue>(V)) 207363496Sdim return markUndef(); 208326938Sdim 209363496Sdim if (isConstant()) { 210363496Sdim assert(getConstant() == V && "Marking constant with different value"); 211363496Sdim return false; 212363496Sdim } 213363496Sdim 214363496Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 215363496Sdim return markConstantRange(ConstantRange(CI->getValue())); 216363496Sdim 217363496Sdim assert(isUnknown() || isUndef()); 218326938Sdim Tag = constant; 219341825Sdim ConstVal = V; 220363496Sdim return true; 221326938Sdim } 222326938Sdim 223363496Sdim bool markNotConstant(Constant *V) { 224326938Sdim assert(V && "Marking constant with NULL"); 225363496Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 226363496Sdim return markConstantRange( 227363496Sdim ConstantRange(CI->getValue() + 1, CI->getValue())); 228363496Sdim 229326938Sdim if (isa<UndefValue>(V)) 230363496Sdim return false; 231326938Sdim 232363496Sdim if (isNotConstant()) { 233363496Sdim assert(getNotConstant() == V && "Marking !constant with different value"); 234363496Sdim return false; 235363496Sdim } 236363496Sdim 237363496Sdim assert(isUnknown()); 238326938Sdim Tag = notconstant; 239341825Sdim ConstVal = V; 240363496Sdim return true; 241326938Sdim } 242326938Sdim 243363496Sdim /// Mark the object as constant range with \p NewR. If the object is already a 244363496Sdim /// constant range, nothing changes if the existing range is equal to \p 245363496Sdim /// NewR. Otherwise \p NewR must be a superset of the existing range or the 246363496Sdim /// object must be undef. 247363496Sdim bool markConstantRange(ConstantRange NewR) { 248326938Sdim if (isConstantRange()) { 249363496Sdim if (getConstantRange() == NewR) 250363496Sdim return false; 251363496Sdim 252326938Sdim if (NewR.isEmptySet()) 253363496Sdim return markOverdefined(); 254363496Sdim 255363496Sdim assert(NewR.contains(getConstantRange()) && 256363496Sdim "Existing range must be a subset of NewR"); 257363496Sdim Range = std::move(NewR); 258363496Sdim return true; 259326938Sdim } 260326938Sdim 261363496Sdim assert(isUnknown() || isUndef()); 262326938Sdim if (NewR.isEmptySet()) 263363496Sdim return markOverdefined(); 264363496Sdim 265363496Sdim Tag = constantrange; 266363496Sdim new (&Range) ConstantRange(std::move(NewR)); 267363496Sdim return true; 268326938Sdim } 269326938Sdim 270326938Sdim /// Updates this object to approximate both this object and RHS. Returns 271326938Sdim /// true if this object has been changed. 272326938Sdim bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) { 273363496Sdim if (RHS.isUnknown() || isOverdefined()) 274326938Sdim return false; 275326938Sdim if (RHS.isOverdefined()) { 276326938Sdim markOverdefined(); 277326938Sdim return true; 278326938Sdim } 279326938Sdim 280363496Sdim if (isUndef()) { 281363496Sdim assert(!RHS.isUnknown()); 282363496Sdim if (RHS.isUndef()) 283363496Sdim return false; 284363496Sdim if (RHS.isConstant()) 285363496Sdim return markConstant(RHS.getConstant()); 286363496Sdim if (RHS.isConstantRange() && RHS.getConstantRange().isSingleElement()) 287363496Sdim return markConstantRange(RHS.getConstantRange()); 288363496Sdim return markOverdefined(); 289363496Sdim } 290363496Sdim 291363496Sdim if (isUnknown()) { 292363496Sdim assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier"); 293326938Sdim *this = RHS; 294363496Sdim return true; 295326938Sdim } 296326938Sdim 297326938Sdim if (isConstant()) { 298341825Sdim if (RHS.isConstant() && getConstant() == RHS.getConstant()) 299326938Sdim return false; 300363496Sdim if (RHS.isUndef()) 301363496Sdim return false; 302326938Sdim markOverdefined(); 303326938Sdim return true; 304326938Sdim } 305326938Sdim 306326938Sdim if (isNotConstant()) { 307341825Sdim if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant()) 308326938Sdim return false; 309326938Sdim markOverdefined(); 310326938Sdim return true; 311326938Sdim } 312326938Sdim 313326938Sdim assert(isConstantRange() && "New ValueLattice type?"); 314363496Sdim if (RHS.isUndef() && getConstantRange().isSingleElement()) 315363496Sdim return false; 316363496Sdim 317326938Sdim if (!RHS.isConstantRange()) { 318326938Sdim // We can get here if we've encountered a constantexpr of integer type 319326938Sdim // and merge it with a constantrange. 320326938Sdim markOverdefined(); 321326938Sdim return true; 322326938Sdim } 323341825Sdim ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange()); 324326938Sdim if (NewR.isFullSet()) 325363496Sdim return markOverdefined(); 326341825Sdim else if (NewR == getConstantRange()) 327341825Sdim return false; 328326938Sdim else 329363496Sdim return markConstantRange(std::move(NewR)); 330326938Sdim } 331326938Sdim 332341825Sdim /// Compares this symbolic value with Other using Pred and returns either 333341825Sdim /// true, false or undef constants, or nullptr if the comparison cannot be 334341825Sdim /// evaluated. 335341825Sdim Constant *getCompare(CmpInst::Predicate Pred, Type *Ty, 336341825Sdim const ValueLatticeElement &Other) const { 337363496Sdim if (isUnknownOrUndef() || Other.isUnknownOrUndef()) 338341825Sdim return UndefValue::get(Ty); 339326938Sdim 340341825Sdim if (isConstant() && Other.isConstant()) 341341825Sdim return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant()); 342326938Sdim 343326938Sdim // Integer constants are represented as ConstantRanges with single 344326938Sdim // elements. 345326938Sdim if (!isConstantRange() || !Other.isConstantRange()) 346341825Sdim return nullptr; 347326938Sdim 348326938Sdim const auto &CR = getConstantRange(); 349326938Sdim const auto &OtherCR = Other.getConstantRange(); 350341825Sdim if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR)) 351341825Sdim return ConstantInt::getTrue(Ty); 352341825Sdim if (ConstantRange::makeSatisfyingICmpRegion( 353341825Sdim CmpInst::getInversePredicate(Pred), OtherCR) 354341825Sdim .contains(CR)) 355341825Sdim return ConstantInt::getFalse(Ty); 356341825Sdim 357341825Sdim return nullptr; 358326938Sdim } 359326938Sdim}; 360326938Sdim 361326938Sdimraw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val); 362326938Sdim 363326938Sdim} // end namespace llvm 364326938Sdim#endif 365