Home | History | Annotate | Download | only in Analysis 
      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
    251