LCOV - code coverage report
Current view: top level - include/llvm/Analysis - ValueLattice.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 95 100 95.0 %
Date: 2018-07-13 00:08:38 Functions: 9 9 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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     8235664 :   ValueLatticeElement() : Tag(undefined) {}
      65             : 
      66             :   /// Custom destructor to ensure Range is properly destroyed, when the object
      67             :   /// is deallocated.
      68     1700089 :   ~ValueLatticeElement() {
      69    10346106 :     switch (Tag) {
      70             :     case overdefined:
      71             :     case undefined:
      72             :     case constant:
      73             :     case notconstant:
      74             :       break;
      75      657281 :     case constantrange:
      76      657281 :       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     2110442 :   ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
      84     2110442 :     *this = Other;
      85             :   }
      86             : 
      87             :   /// Custom assignment operator, to ensure Range gets initialized when
      88             :   /// assigning a constant range lattice element.
      89     6426400 :   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
      90             :     // If we change the state of this from constant range to non constant range,
      91             :     // destroy Range.
      92     6426400 :     if (isConstantRange() && !Other.isConstantRange())
      93           0 :       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     6426400 :     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
      98             :         !Other.isNotConstant())
      99           0 :       ConstVal = nullptr;
     100             : 
     101     6426400 :     switch (Other.Tag) {
     102      545434 :     case constantrange:
     103      545434 :       if (!isConstantRange())
     104      544917 :         new (&Range) ConstantRange(Other.Range);
     105             :       else
     106             :         Range = Other.Range;
     107             :       break;
     108     1885120 :     case constant:
     109             :     case notconstant:
     110     1885120 :       ConstVal = Other.ConstVal;
     111     1885120 :       break;
     112             :     case overdefined:
     113             :     case undefined:
     114             :       break;
     115             :     }
     116     6426400 :     Tag = Other.Tag;
     117     6426400 :     return *this;
     118             :   }
     119             : 
     120             :   static ValueLatticeElement get(Constant *C) {
     121             :     ValueLatticeElement Res;
     122      153487 :     if (!isa<UndefValue>(C))
     123      153444 :       Res.markConstant(C);
     124             :     return Res;
     125             :   }
     126             :   static ValueLatticeElement getNot(Constant *C) {
     127             :     ValueLatticeElement Res;
     128      165217 :     if (!isa<UndefValue>(C))
     129      165217 :       Res.markNotConstant(C);
     130             :     return Res;
     131             :   }
     132       56863 :   static ValueLatticeElement getRange(ConstantRange CR) {
     133             :     ValueLatticeElement Res;
     134       56863 :     Res.markConstantRange(std::move(CR));
     135       56863 :     return Res;
     136             :   }
     137             :   static ValueLatticeElement getOverdefined() {
     138             :     ValueLatticeElement Res;
     139     2815195 :     Res.markOverdefined();
     140             :     return Res;
     141             :   }
     142             : 
     143             :   bool isUndefined() const { return Tag == undefined; }
     144           1 :   bool isConstant() const { return Tag == constant; }
     145           1 :   bool isNotConstant() const { return Tag == notconstant; }
     146           7 :   bool isConstantRange() const { return Tag == constantrange; }
     147           3 :   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       72319 :     return Range;
     163             :   }
     164             : 
     165       39275 :   Optional<APInt> asConstantInteger() const {
     166       39287 :     if (isConstant() && isa<ConstantInt>(getConstant())) {
     167             :       return cast<ConstantInt>(getConstant())->getValue();
     168       41025 :     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
     169          77 :       return *getConstantRange().getSingleElement();
     170             :     }
     171             :     return None;
     172             :   }
     173             : 
     174             : private:
     175     3026863 :   void markOverdefined() {
     176     3026863 :     if (isOverdefined())
     177             :       return;
     178     3026863 :     if (isConstant() || isNotConstant())
     179        5764 :       ConstVal = nullptr;
     180     3026863 :     if (isConstantRange())
     181        7069 :       Range.~ConstantRange();
     182     3026863 :     Tag = overdefined;
     183             :   }
     184             : 
     185      153444 :   void markConstant(Constant *V) {
     186             :     assert(V && "Marking constant with NULL");
     187             :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     188       99364 :       markConstantRange(ConstantRange(CI->getValue()));
     189       49682 :       return;
     190             :     }
     191      103762 :     if (isa<UndefValue>(V))
     192             :       return;
     193             : 
     194             :     assert((!isConstant() || getConstant() == V) &&
     195             :            "Marking constant with different value");
     196             :     assert(isUndefined());
     197      103762 :     Tag = constant;
     198      103762 :     ConstVal = V;
     199             :   }
     200             : 
     201      165217 :   void markNotConstant(Constant *V) {
     202             :     assert(V && "Marking constant with NULL");
     203             :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     204       51572 :       markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
     205       12893 :       return;
     206             :     }
     207      152324 :     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      152324 :     Tag = notconstant;
     216      152324 :     ConstVal = V;
     217             :   }
     218             : 
     219      122288 :   void markConstantRange(ConstantRange NewR) {
     220      122288 :     if (isConstantRange()) {
     221        2850 :       if (NewR.isEmptySet())
     222           0 :         markOverdefined();
     223             :       else {
     224        2850 :         Range = std::move(NewR);
     225             :       }
     226             :       return;
     227             :     }
     228             : 
     229             :     assert(isUndefined());
     230      119438 :     if (NewR.isEmptySet())
     231           5 :       markOverdefined();
     232             :     else {
     233      119433 :       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      606564 :   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
     242      606564 :     if (RHS.isUndefined() || isOverdefined())
     243             :       return false;
     244      502501 :     if (RHS.isOverdefined()) {
     245      207374 :       markOverdefined();
     246      207374 :       return true;
     247             :     }
     248             : 
     249      295127 :     if (isUndefined()) {
     250      226448 :       *this = RHS;
     251      226448 :       return !RHS.isUndefined();
     252             :     }
     253             : 
     254       68679 :     if (isConstant()) {
     255        1465 :       if (RHS.isConstant() && getConstant() == RHS.getConstant())
     256             :         return false;
     257         517 :       markOverdefined();
     258         517 :       return true;
     259             :     }
     260             : 
     261       67214 :     if (isNotConstant()) {
     262       53056 :       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
     263             :         return false;
     264         194 :       markOverdefined();
     265         194 :       return true;
     266             :     }
     267             : 
     268             :     assert(isConstantRange() && "New ValueLattice type?");
     269       14158 :     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           0 :       markOverdefined();
     273           0 :       return true;
     274             :     }
     275       28316 :     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
     276       14158 :     if (NewR.isFullSet())
     277        3578 :       markOverdefined();
     278       10580 :     else if (NewR == getConstantRange())
     279             :       return false;
     280             :     else
     281        2850 :       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       58578 :   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
     295             :                        const ValueLatticeElement &Other) const {
     296       58578 :     if (isUndefined() || Other.isUndefined())
     297        3423 :       return UndefValue::get(Ty);
     298             : 
     299       55155 :     if (isConstant() && Other.isConstant())
     300         165 :       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
     301             : 
     302             :     // Integer constants are represented as ConstantRanges with single
     303             :     // elements.
     304       60118 :     if (!isConstantRange() || !Other.isConstantRange())
     305             :       return nullptr;
     306             : 
     307             :     const auto &CR = getConstantRange();
     308             :     const auto &OtherCR = Other.getConstantRange();
     309        3611 :     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
     310        2609 :       return ConstantInt::getTrue(Ty);
     311        2004 :     if (ConstantRange::makeSatisfyingICmpRegion(
     312             :             CmpInst::getInversePredicate(Pred), OtherCR)
     313        1002 :             .contains(CR))
     314         982 :       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

Generated by: LCOV version 1.13