include/llvm/Analysis/ValueLattice.h

   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
  25 namespace llvm {
  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     undefined,
  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
  51   ValueLatticeElementTy Tag;
  52
  53   /// The union either stores a pointer to a constant or a constant range,
  54   /// associated to the lattice element. We have to ensure that Range is
  55   /// initialized or destroyed when changing state to or from constantrange.
  56   union {
  57     Constant *ConstVal;
  58     ConstantRange Range;
  59   };
  60
  61 public:
  62   // Const and Range are initialized on-demand.
  63   ValueLatticeElement() : Tag(undefined) {}
  64
  65   /// Custom destructor to ensure Range is properly destroyed, when the object
  66   /// is deallocated.
  67   ~ValueLatticeElement() {
  68     switch (Tag) {
  69     case overdefined:
  70     case undefined:
  71     case constant:
  72     case notconstant:
  73       break;
  74     case constantrange:
  75       Range.~ConstantRange();
  76       break;
  77     };
  78   }
  79
  80   /// Custom copy constructor, to ensure Range gets initialized when
  81   /// copying a constant range lattice element.
  82   ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
  83     *this = Other;
  84   }
  85
  86   /// Custom assignment operator, to ensure Range gets initialized when
  87   /// assigning a constant range lattice element.
  88   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
  89     // If we change the state of this from constant range to non constant range,
  90     // destroy Range.
  91     if (isConstantRange() && !Other.isConstantRange())
  92       Range.~ConstantRange();
  93
  94     // If we change the state of this from a valid ConstVal to another a state
  95     // without a valid ConstVal, zero the pointer.
  96     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
  97         !Other.isNotConstant())
  98       ConstVal = nullptr;
  99
 100     switch (Other.Tag) {
 101     case constantrange:
 102       if (!isConstantRange())
 103         new (&Range) ConstantRange(Other.Range);
 104       else
 105         Range = Other.Range;
 106       break;
 107     case constant:
 108     case notconstant:
 109       ConstVal = Other.ConstVal;
 110       break;
 111     case overdefined:
 112     case undefined:
 113       break;
 114     }
 115     Tag = Other.Tag;
 116     return *this;
 117   }
 118
 119   static ValueLatticeElement get(Constant *C) {
 120     ValueLatticeElement Res;
 121     if (!isa<UndefValue>(C))
 122       Res.markConstant(C);
 123     return Res;
 124   }
 125   static ValueLatticeElement getNot(Constant *C) {
 126     ValueLatticeElement Res;
 127     if (!isa<UndefValue>(C))
 128       Res.markNotConstant(C);
 129     return Res;
 130   }
 131   static ValueLatticeElement getRange(ConstantRange CR) {
 132     ValueLatticeElement Res;
 133     Res.markConstantRange(std::move(CR));
 134     return Res;
 135   }
 136   static ValueLatticeElement getOverdefined() {
 137     ValueLatticeElement Res;
 138     Res.markOverdefined();
 139     return Res;
 140   }
 141
 142   bool isUndefined() const { return Tag == undefined; }
 143   bool isConstant() const { return Tag == constant; }
 144   bool isNotConstant() const { return Tag == notconstant; }
 145   bool isConstantRange() const { return Tag == constantrange; }
 146   bool isOverdefined() const { return Tag == overdefined; }
 147
 148   Constant *getConstant() const {
 149     assert(isConstant() && "Cannot get the constant of a non-constant!");
 150     return ConstVal;
 151   }
 152
 153   Constant *getNotConstant() const {
 154     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
 155     return ConstVal;
 156   }
 157
 158   const ConstantRange &getConstantRange() const {
 159     assert(isConstantRange() &&
 160            "Cannot get the constant-range of a non-constant-range!");
 161     return Range;
 162   }
 163
 164   Optional<APInt> asConstantInteger() const {
 165     if (isConstant() && isa<ConstantInt>(getConstant())) {
 166       return cast<ConstantInt>(getConstant())->getValue();
 167     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
 168       return *getConstantRange().getSingleElement();
 169     }
 170     return None;
 171   }
 172
 173 private:
 174   void markOverdefined() {
 175     if (isOverdefined())
 176       return;
 177     if (isConstant() || isNotConstant())
 178       ConstVal = nullptr;
 179     if (isConstantRange())
 180       Range.~ConstantRange();
 181     Tag = overdefined;
 182   }
 183
 184   void markConstant(Constant *V) {
 185     assert(V && "Marking constant with NULL");
 186     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 187       markConstantRange(ConstantRange(CI->getValue()));
 188       return;
 189     }
 190     if (isa<UndefValue>(V))
 191       return;
 192
 193     assert((!isConstant() || getConstant() == V) &&
 194            "Marking constant with different value");
 195     assert(isUndefined());
 196     Tag = constant;
 197     ConstVal = V;
 198   }
 199
 200   void markNotConstant(Constant *V) {
 201     assert(V && "Marking constant with NULL");
 202     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 203       markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
 204       return;
 205     }
 206     if (isa<UndefValue>(V))
 207       return;
 208
 209     assert((!isConstant() || getConstant() != V) &&
 210            "Marking constant !constant with same value");
 211     assert((!isNotConstant() || getNotConstant() == V) &&
 212            "Marking !constant with different value");
 213     assert(isUndefined() || isConstant());
 214     Tag = notconstant;
 215     ConstVal = V;
 216   }
 217
 218   void markConstantRange(ConstantRange NewR) {
 219     if (isConstantRange()) {
 220       if (NewR.isEmptySet())
 221         markOverdefined();
 222       else {
 223         Range = std::move(NewR);
 224       }
 225       return;
 226     }
 227
 228     assert(isUndefined());
 229     if (NewR.isEmptySet())
 230       markOverdefined();
 231     else {
 232       Tag = constantrange;
 233       new (&Range) ConstantRange(std::move(NewR));
 234     }
 235   }
 236
 237 public:
 238   /// Updates this object to approximate both this object and RHS. Returns
 239   /// true if this object has been changed.
 240   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
 241     if (RHS.isUndefined() || isOverdefined())
 242       return false;
 243     if (RHS.isOverdefined()) {
 244       markOverdefined();
 245       return true;
 246     }
 247
 248     if (isUndefined()) {
 249       *this = RHS;
 250       return !RHS.isUndefined();
 251     }
 252
 253     if (isConstant()) {
 254       if (RHS.isConstant() && getConstant() == RHS.getConstant())
 255         return false;
 256       markOverdefined();
 257       return true;
 258     }
 259
 260     if (isNotConstant()) {
 261       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
 262         return false;
 263       markOverdefined();
 264       return true;
 265     }
 266
 267     assert(isConstantRange() && "New ValueLattice type?");
 268     if (!RHS.isConstantRange()) {
 269       // We can get here if we've encountered a constantexpr of integer type
 270       // and merge it with a constantrange.
 271       markOverdefined();
 272       return true;
 273     }
 274     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
 275     if (NewR.isFullSet())
 276       markOverdefined();
 277     else if (NewR == getConstantRange())
 278       return false;
 279     else
 280       markConstantRange(std::move(NewR));
 281     return true;
 282   }
 283
 284   ConstantInt *getConstantInt() const {
 285     assert(isConstant() && isa<ConstantInt>(getConstant()) &&
 286            "No integer constant");
 287     return cast<ConstantInt>(getConstant());
 288   }
 289
 290   /// Compares this symbolic value with Other using Pred and returns either
 291   /// true, false or undef constants, or nullptr if the comparison cannot be
 292   /// evaluated.
 293   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
 294                        const ValueLatticeElement &Other) const {
 295     if (isUndefined() || Other.isUndefined())
 296       return UndefValue::get(Ty);
 297
 298     if (isConstant() && Other.isConstant())
 299       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
 300
 301     // Integer constants are represented as ConstantRanges with single
 302     // elements.
 303     if (!isConstantRange() || !Other.isConstantRange())
 304       return nullptr;
 305
 306     const auto &CR = getConstantRange();
 307     const auto &OtherCR = Other.getConstantRange();
 308     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
 309       return ConstantInt::getTrue(Ty);
 310     if (ConstantRange::makeSatisfyingICmpRegion(
 311             CmpInst::getInversePredicate(Pred), OtherCR)
 312             .contains(CR))
 313       return ConstantInt::getFalse(Ty);
 314
 315     return nullptr;
 316   }
 317 };
 318
 319 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
 320
 321 } // end namespace llvm
 322 #endif