LCOV - code coverage report
Current view: top level - include/llvm/Analysis - ValueLattice.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 89 94 94.7 %
Date: 2018-02-18 03:11:45 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    11202278 :   ValueLatticeElement() : Tag(undefined) {}
      65             : 
      66             :   /// Custom destructor to ensure Range is properly destroyed, when the object
      67             :   /// is deallocated.
      68     5129858 :   ~ValueLatticeElement() {
      69    20236774 :     switch (Tag) {
      70             :     case overdefined:
      71             :     case undefined:
      72             :     case constant:
      73             :     case notconstant:
      74             :       break;
      75      604846 :     case constantrange:
      76      604846 :       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     9034495 :   ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
      84     9034495 :     *this = Other;
      85             :   }
      86             : 
      87             :   /// Custom assignment operator, to ensure Range gets initialized when
      88             :   /// assigning a constant range lattice element.
      89    14869984 :   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
      90             :     // If we change the state of this from constant range to non constant range,
      91             :     // destroy Range.
      92    14869984 :     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    14869985 :     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
      98             :         !Other.isNotConstant())
      99           0 :       ConstVal = nullptr;
     100             : 
     101    14869985 :     switch (Other.Tag) {
     102      529046 :     case constantrange:
     103      529046 :       if (!isConstantRange())
     104      528658 :         new (&Range) ConstantRange(Other.Range);
     105             :       else
     106             :         Range = Other.Range;
     107             :       break;
     108     1846550 :     case constant:
     109             :     case notconstant:
     110     1846550 :       ConstVal = Other.ConstVal;
     111     1846550 :       break;
     112             :     case overdefined:
     113             :     case undefined:
     114             :       break;
     115             :     }
     116    14869985 :     Tag = Other.Tag;
     117    14869985 :     return *this;
     118             :   }
     119             : 
     120             :   static ValueLatticeElement get(Constant *C) {
     121             :     ValueLatticeElement Res;
     122      125556 :     if (!isa<UndefValue>(C))
     123      125524 :       Res.markConstant(C);
     124             :     return Res;
     125             :   }
     126             :   static ValueLatticeElement getNot(Constant *C) {
     127             :     ValueLatticeElement Res;
     128      157646 :     if (!isa<UndefValue>(C))
     129      157646 :       Res.markNotConstant(C);
     130             :     return Res;
     131             :   }
     132       54366 :   static ValueLatticeElement getRange(ConstantRange CR) {
     133             :     ValueLatticeElement Res;
     134       54366 :     Res.markConstantRange(std::move(CR));
     135       54366 :     return Res;
     136             :   }
     137             :   static ValueLatticeElement getOverdefined() {
     138             :     ValueLatticeElement Res;
     139     4327973 :     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           6 :   bool isConstantRange() const { return Tag == constantrange; }
     147           2 :   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       68749 :     return Range;
     163             :   }
     164             : 
     165       37387 :   Optional<APInt> asConstantInteger() const {
     166       37387 :     if (isConstant() && isa<ConstantInt>(getConstant())) {
     167             :       return cast<ConstantInt>(getConstant())->getValue();
     168       39779 :     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
     169         924 :       return *getConstantRange().getSingleElement();
     170             :     }
     171             :     return None;
     172             :   }
     173             : 
     174             : private:
     175     4530636 :   void markOverdefined() {
     176     4530636 :     if (isOverdefined())
     177             :       return;
     178     4530636 :     if (isConstant() || isNotConstant())
     179        5668 :       ConstVal = nullptr;
     180     4530636 :     if (isConstantRange())
     181        6607 :       Range.~ConstantRange();
     182     4530636 :     Tag = overdefined;
     183             :   }
     184             : 
     185      125524 :   void markConstant(Constant *V) {
     186             :     assert(V && "Marking constant with NULL");
     187             :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     188       31806 :       markConstantRange(ConstantRange(CI->getValue()));
     189       15903 :       return;
     190             :     }
     191      109621 :     if (isa<UndefValue>(V))
     192             :       return;
     193             : 
     194             :     assert((!isConstant() || getConstant() == V) &&
     195             :            "Marking constant with different value");
     196             :     assert(isUndefined());
     197      109621 :     Tag = constant;
     198      109621 :     ConstVal = V;
     199             :   }
     200             : 
     201      157646 :   void markNotConstant(Constant *V) {
     202             :     assert(V && "Marking constant with NULL");
     203             :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     204       50148 :       markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
     205       12537 :       return;
     206             :     }
     207      145109 :     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      145109 :     Tag = notconstant;
     216      145109 :     ConstVal = V;
     217             :   }
     218             : 
     219       93301 :   void markConstantRange(ConstantRange NewR) {
     220       93301 :     if (isConstantRange()) {
     221       10495 :       if (NewR.isEmptySet())
     222           0 :         markOverdefined();
     223             :       else {
     224       10495 :         Range = std::move(NewR);
     225             :       }
     226             :       return;
     227             :     }
     228             : 
     229             :     assert(isUndefined());
     230       82806 :     if (NewR.isEmptySet())
     231          11 :       markOverdefined();
     232             :     else {
     233       82795 :       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      577399 :   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
     242      577399 :     if (RHS.isUndefined() || isOverdefined())
     243             :       return false;
     244      476560 :     if (RHS.isOverdefined()) {
     245      198695 :       markOverdefined();
     246      198695 :       return true;
     247             :     }
     248             : 
     249      277865 :     if (isUndefined()) {
     250      213083 :       *this = RHS;
     251      213083 :       return !RHS.isUndefined();
     252             :     }
     253             : 
     254       64782 :     if (isConstant()) {
     255        1473 :       if (RHS.isConstant() && getConstant() == RHS.getConstant())
     256             :         return false;
     257         524 :       markOverdefined();
     258         524 :       return true;
     259             :     }
     260             : 
     261       63309 :     if (isNotConstant()) {
     262       49549 :       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
     263             :         return false;
     264         169 :       markOverdefined();
     265         169 :       return true;
     266             :     }
     267             : 
     268             :     assert(isConstantRange() && "New ValueLattice type?");
     269       13760 :     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       27520 :     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
     276       13760 :     if (NewR.isFullSet())
     277        3265 :       markOverdefined();
     278             :     else
     279       10495 :       markConstantRange(std::move(NewR));
     280             :     return true;
     281             :   }
     282             : 
     283             :   ConstantInt *getConstantInt() const {
     284             :     assert(isConstant() && isa<ConstantInt>(getConstant()) &&
     285             :            "No integer constant");
     286             :     return cast<ConstantInt>(getConstant());
     287             :   }
     288             : 
     289          56 :   bool satisfiesPredicate(CmpInst::Predicate Pred,
     290             :                           const ValueLatticeElement &Other) const {
     291             :     // TODO: share with LVI getPredicateResult.
     292             : 
     293          56 :     if (isUndefined() || Other.isUndefined())
     294             :       return true;
     295             : 
     296          56 :     if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ)
     297           1 :       return getConstant() == Other.getConstant();
     298             : 
     299             :     // Integer constants are represented as ConstantRanges with single
     300             :     // elements.
     301          95 :     if (!isConstantRange() || !Other.isConstantRange())
     302             :       return false;
     303             : 
     304             :     const auto &CR = getConstantRange();
     305             :     const auto &OtherCR = Other.getConstantRange();
     306          40 :     return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
     307             :   }
     308             : };
     309             : 
     310             : raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
     311             : 
     312             : } // end namespace llvm
     313             : #endif

Generated by: LCOV version 1.13