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   /// Val: This stores the current lattice value along with the Constant* for
  53   /// the constant if this is a 'constant' or 'notconstant' value.
  54   ValueLatticeElementTy Tag;
  55   Constant *Val;
  56   ConstantRange Range;
  57
  58 public:
  59   ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {}
  60
  61   static ValueLatticeElement get(Constant *C) {
  62     ValueLatticeElement Res;
  63     if (!isa<UndefValue>(C))
  64       Res.markConstant(C);
  65     return Res;
  66   }
  67   static ValueLatticeElement getNot(Constant *C) {
  68     ValueLatticeElement Res;
  69     if (!isa<UndefValue>(C))
  70       Res.markNotConstant(C);
  71     return Res;
  72   }
  73   static ValueLatticeElement getRange(ConstantRange CR) {
  74     ValueLatticeElement Res;
  75     Res.markConstantRange(std::move(CR));
  76     return Res;
  77   }
  78   static ValueLatticeElement getOverdefined() {
  79     ValueLatticeElement Res;
  80     Res.markOverdefined();
  81     return Res;
  82   }
  83
  84   bool isUndefined() const { return Tag == undefined; }
  85   bool isConstant() const { return Tag == constant; }
  86   bool isNotConstant() const { return Tag == notconstant; }
  87   bool isConstantRange() const { return Tag == constantrange; }
  88   bool isOverdefined() const { return Tag == overdefined; }
  89
  90   Constant *getConstant() const {
  91     assert(isConstant() && "Cannot get the constant of a non-constant!");
  92     return Val;
  93   }
  94
  95   Constant *getNotConstant() const {
  96     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
  97     return Val;
  98   }
  99
 100   const ConstantRange &getConstantRange() const {
 101     assert(isConstantRange() &&
 102            "Cannot get the constant-range of a non-constant-range!");
 103     return Range;
 104   }
 105
 106   Optional<APInt> asConstantInteger() const {
 107     if (isConstant() && isa<ConstantInt>(Val)) {
 108       return cast<ConstantInt>(Val)->getValue();
 109     } else if (isConstantRange() && Range.isSingleElement()) {
 110       return *Range.getSingleElement();
 111     }
 112     return None;
 113   }
 114
 115 private:
 116   void markOverdefined() {
 117     if (isOverdefined())
 118       return;
 119     Tag = overdefined;
 120   }
 121
 122   void markConstant(Constant *V) {
 123     assert(V && "Marking constant with NULL");
 124     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 125       markConstantRange(ConstantRange(CI->getValue()));
 126       return;
 127     }
 128     if (isa<UndefValue>(V))
 129       return;
 130
 131     assert((!isConstant() || getConstant() == V) &&
 132            "Marking constant with different value");
 133     assert(isUndefined());
 134     Tag = constant;
 135     Val = V;
 136   }
 137
 138   void markNotConstant(Constant *V) {
 139     assert(V && "Marking constant with NULL");
 140     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 141       markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
 142       return;
 143     }
 144     if (isa<UndefValue>(V))
 145       return;
 146
 147     assert((!isConstant() || getConstant() != V) &&
 148            "Marking constant !constant with same value");
 149     assert((!isNotConstant() || getNotConstant() == V) &&
 150            "Marking !constant with different value");
 151     assert(isUndefined() || isConstant());
 152     Tag = notconstant;
 153     Val = V;
 154   }
 155
 156   void markConstantRange(ConstantRange NewR) {
 157     if (isConstantRange()) {
 158       if (NewR.isEmptySet())
 159         markOverdefined();
 160       else {
 161         Range = std::move(NewR);
 162       }
 163       return;
 164     }
 165
 166     assert(isUndefined());
 167     if (NewR.isEmptySet())
 168       markOverdefined();
 169     else {
 170       Tag = constantrange;
 171       Range = std::move(NewR);
 172     }
 173   }
 174
 175 public:
 176   /// Updates this object to approximate both this object and RHS. Returns
 177   /// true if this object has been changed.
 178   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
 179     if (RHS.isUndefined() || isOverdefined())
 180       return false;
 181     if (RHS.isOverdefined()) {
 182       markOverdefined();
 183       return true;
 184     }
 185
 186     if (isUndefined()) {
 187       *this = RHS;
 188       return !RHS.isUndefined();
 189     }
 190
 191     if (isConstant()) {
 192       if (RHS.isConstant() && Val == RHS.Val)
 193         return false;
 194       markOverdefined();
 195       return true;
 196     }
 197
 198     if (isNotConstant()) {
 199       if (RHS.isNotConstant() && Val == RHS.Val)
 200         return false;
 201       markOverdefined();
 202       return true;
 203     }
 204
 205     assert(isConstantRange() && "New ValueLattice type?");
 206     if (!RHS.isConstantRange()) {
 207       // We can get here if we've encountered a constantexpr of integer type
 208       // and merge it with a constantrange.
 209       markOverdefined();
 210       return true;
 211     }
 212     ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
 213     if (NewR.isFullSet())
 214       markOverdefined();
 215     else
 216       markConstantRange(std::move(NewR));
 217     return true;
 218   }
 219
 220   ConstantInt *getConstantInt() const {
 221     assert(isConstant() && isa<ConstantInt>(getConstant()) &&
 222            "No integer constant");
 223     return cast<ConstantInt>(getConstant());
 224   }
 225
 226   bool satisfiesPredicate(CmpInst::Predicate Pred,
 227                           const ValueLatticeElement &Other) const {
 228     // TODO: share with LVI getPredicateResult.
 229
 230     if (isUndefined() || Other.isUndefined())
 231       return true;
 232
 233     if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ)
 234       return getConstant() == Other.getConstant();
 235
 236     // Integer constants are represented as ConstantRanges with single
 237     // elements.
 238     if (!isConstantRange() || !Other.isConstantRange())
 239       return false;
 240
 241     const auto &CR = getConstantRange();
 242     const auto &OtherCR = Other.getConstantRange();
 243     return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
 244   }
 245 };
 246
 247 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
 248
 249 } // end namespace llvm
 250 #endif