contrib/llvm/include/llvm/Analysis/ValueLattice.h

   1 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
  11 #define LLVM_ANALYSIS_VALUELATTICE_H
  12
  13 #include "llvm/IR/ConstantRange.h"
  14 #include "llvm/IR/Constants.h"
  15 //
  16 //===----------------------------------------------------------------------===//
  17 //                               ValueLatticeElement
  18 //===----------------------------------------------------------------------===//
  19
  20 /// This class represents lattice values for constants.
  21 ///
  22 /// FIXME: This is basically just for bringup, this can be made a lot more rich
  23 /// in the future.
  24 ///
  25
  26 namespace llvm {
  27 class ValueLatticeElement {
  28   enum ValueLatticeElementTy {
  29     /// This Value has no known value yet.  As a result, this implies the
  30     /// producing instruction is dead.  Caution: We use this as the starting
  31     /// state in our local meet rules.  In this usage, it's taken to mean
  32     /// "nothing known yet".
  33     undefined,
  34
  35     /// This Value has a specific constant value.  (For constant integers,
  36     /// constantrange is used instead.  Integer typed constantexprs can appear
  37     /// as constant.)
  38     constant,
  39
  40     /// This Value is known to not have the specified value.  (For constant
  41     /// integers, constantrange is used instead.  As above, integer typed
  42     /// constantexprs can appear here.)
  43     notconstant,
  44
  45     /// The Value falls within this range. (Used only for integer typed values.)
  46     constantrange,
  47
  48     /// We can not precisely model the dynamic values this value might take.
  49     overdefined
  50   };
  51
  52   ValueLatticeElementTy Tag;
  53
  54   /// The union either stores a pointer to a constant or a constant range,
  55   /// associated to the lattice element. We have to ensure that Range is
  56   /// initialized or destroyed when changing state to or from constantrange.
  57   union {
  58     Constant *ConstVal;
  59     ConstantRange Range;
  60   };
  61
  62 public:
  63   // Const and Range are initialized on-demand.
  64   ValueLatticeElement() : Tag(undefined) {}
  65
  66   /// Custom destructor to ensure Range is properly destroyed, when the object
  67   /// is deallocated.
  68   ~ValueLatticeElement() {
  69     switch (Tag) {
  70     case overdefined:
  71     case undefined:
  72     case constant:
  73     case notconstant:
  74       break;
  75     case constantrange:
  76       Range.~ConstantRange();
  77       break;
  78     };
  79   }
  80
  81   /// Custom copy constructor, to ensure Range gets initialized when
  82   /// copying a constant range lattice element.
  83   ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
  84     *this = Other;
  85   }
  86
  87   /// Custom assignment operator, to ensure Range gets initialized when
  88   /// assigning a constant range lattice element.
  89   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
  90     // If we change the state of this from constant range to non constant range,
  91     // destroy Range.
  92     if (isConstantRange() && !Other.isConstantRange())
  93       Range.~ConstantRange();
  94
  95     // If we change the state of this from a valid ConstVal to another a state
  96     // without a valid ConstVal, zero the pointer.
  97     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
  98         !Other.isNotConstant())
  99       ConstVal = nullptr;
 100
 101     switch (Other.Tag) {
 102     case constantrange:
 103       if (!isConstantRange())
 104         new (&Range) ConstantRange(Other.Range);
 105       else
 106         Range = Other.Range;
 107       break;
 108     case constant:
 109     case notconstant:
 110       ConstVal = Other.ConstVal;
 111       break;
 112     case overdefined:
 113     case undefined:
 114       break;
 115     }
 116     Tag = Other.Tag;
 117     return *this;
 118   }
 119
 120   static ValueLatticeElement get(Constant *C) {
 121     ValueLatticeElement Res;
 122     if (!isa<UndefValue>(C))
 123       Res.markConstant(C);
 124     return Res;
 125   }
 126   static ValueLatticeElement getNot(Constant *C) {
 127     ValueLatticeElement Res;
 128     if (!isa<UndefValue>(C))
 129       Res.markNotConstant(C);
 130     return Res;
 131   }
 132   static ValueLatticeElement getRange(ConstantRange CR) {
 133     ValueLatticeElement Res;
 134     Res.markConstantRange(std::move(CR));
 135     return Res;
 136   }
 137   static ValueLatticeElement getOverdefined() {
 138     ValueLatticeElement Res;
 139     Res.markOverdefined();
 140     return Res;
 141   }
 142
 143   bool isUndefined() const { return Tag == undefined; }
 144   bool isConstant() const { return Tag == constant; }
 145   bool isNotConstant() const { return Tag == notconstant; }
 146   bool isConstantRange() const { return Tag == constantrange; }
 147   bool isOverdefined() const { return Tag == overdefined; }
 148
 149   Constant *getConstant() const {
 150     assert(isConstant() && "Cannot get the constant of a non-constant!");
 151     return ConstVal;
 152   }
 153
 154   Constant *getNotConstant() const {
 155     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
 156     return ConstVal;
 157   }
 158
 159   const ConstantRange &getConstantRange() const {
 160     assert(isConstantRange() &&
 161            "Cannot get the constant-range of a non-constant-range!");
 162     return Range;
 163   }
 164
 165   Optional<APInt> asConstantInteger() const {
 166     if (isConstant() && isa<ConstantInt>(getConstant())) {
 167       return cast<ConstantInt>(getConstant())->getValue();
 168     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
 169       return *getConstantRange().getSingleElement();
 170     }
 171     return None;
 172   }
 173
 174 private:
 175   void markOverdefined() {
 176     if (isOverdefined())
 177       return;
 178     if (isConstant() || isNotConstant())
 179       ConstVal = nullptr;
 180     if (isConstantRange())
 181       Range.~ConstantRange();
 182     Tag = overdefined;
 183   }
 184
 185   void markConstant(Constant *V) {
 186     assert(V && "Marking constant with NULL");
 187     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 188       markConstantRange(ConstantRange(CI->getValue()));
 189       return;
 190     }
 191     if (isa<UndefValue>(V))
 192       return;
 193
 194     assert((!isConstant() || getConstant() == V) &&
 195            "Marking constant with different value");
 196     assert(isUndefined());
 197     Tag = constant;
 198     ConstVal = V;
 199   }
 200
 201   void markNotConstant(Constant *V) {
 202     assert(V && "Marking constant with NULL");
 203     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 204       markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
 205       return;
 206     }
 207     if (isa<UndefValue>(V))
 208       return;
 209
 210     assert((!isConstant() || getConstant() != V) &&
 211            "Marking constant !constant with same value");
 212     assert((!isNotConstant() || getNotConstant() == V) &&
 213            "Marking !constant with different value");
 214     assert(isUndefined() || isConstant());
 215     Tag = notconstant;
 216     ConstVal = V;
 217   }
 218
 219   void markConstantRange(ConstantRange NewR) {
 220     if (isConstantRange()) {
 221       if (NewR.isEmptySet())
 222         markOverdefined();
 223       else {
 224         Range = std::move(NewR);
 225       }
 226       return;
 227     }
 228
 229     assert(isUndefined());
 230     if (NewR.isEmptySet())
 231       markOverdefined();
 232     else {
 233       Tag = constantrange;
 234       new (&Range) ConstantRange(std::move(NewR));
 235     }
 236   }
 237
 238 public:
 239   /// Updates this object to approximate both this object and RHS. Returns
 240   /// true if this object has been changed.
 241   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
 242     if (RHS.isUndefined() || isOverdefined())
 243       return false;
 244     if (RHS.isOverdefined()) {
 245       markOverdefined();
 246       return true;
 247     }
 248
 249     if (isUndefined()) {
 250       *this = RHS;
 251       return !RHS.isUndefined();
 252     }
 253
 254     if (isConstant()) {
 255       if (RHS.isConstant() && getConstant() == RHS.getConstant())
 256         return false;
 257       markOverdefined();
 258       return true;
 259     }
 260
 261     if (isNotConstant()) {
 262       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
 263         return false;
 264       markOverdefined();
 265       return true;
 266     }
 267
 268     assert(isConstantRange() && "New ValueLattice type?");
 269     if (!RHS.isConstantRange()) {
 270       // We can get here if we've encountered a constantexpr of integer type
 271       // and merge it with a constantrange.
 272       markOverdefined();
 273       return true;
 274     }
 275     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
 276     if (NewR.isFullSet())
 277       markOverdefined();
 278     else if (NewR == getConstantRange())
 279       return false;
 280     else
 281       markConstantRange(std::move(NewR));
 282     return true;
 283   }
 284
 285   ConstantInt *getConstantInt() const {
 286     assert(isConstant() && isa<ConstantInt>(getConstant()) &&
 287            "No integer constant");
 288     return cast<ConstantInt>(getConstant());
 289   }
 290
 291   /// Compares this symbolic value with Other using Pred and returns either
 292   /// true, false or undef constants, or nullptr if the comparison cannot be
 293   /// evaluated.
 294   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
 295                        const ValueLatticeElement &Other) const {
 296     if (isUndefined() || Other.isUndefined())
 297       return UndefValue::get(Ty);
 298
 299     if (isConstant() && Other.isConstant())
 300       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
 301
 302     // Integer constants are represented as ConstantRanges with single
 303     // elements.
 304     if (!isConstantRange() || !Other.isConstantRange())
 305       return nullptr;
 306
 307     const auto &CR = getConstantRange();
 308     const auto &OtherCR = Other.getConstantRange();
 309     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
 310       return ConstantInt::getTrue(Ty);
 311     if (ConstantRange::makeSatisfyingICmpRegion(
 312             CmpInst::getInversePredicate(Pred), OtherCR)
 313             .contains(CR))
 314       return ConstantInt::getFalse(Ty);
 315
 316     return nullptr;
 317   }
 318 };
 319
 320 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
 321
 322 } // end namespace llvm
 323 #endif