LCOV - code coverage report
Current view: top level - include/llvm/Analysis - ValueLattice.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 96 106 90.6 %
Date: 2018-10-20 13:21:21 Functions: 9 16 56.2 %
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     7634736 :   ValueLatticeElement() : Tag(undefined) {}
      65             : 
      66             :   /// Custom destructor to ensure Range is properly destroyed, when the object
      67             :   /// is deallocated.
      68     2413108 :   ~ValueLatticeElement() {
      69    14243172 :     switch (Tag) {
      70             :     case overdefined:
      71             :     case undefined:
      72             :     case constant:
      73             :     case notconstant:
      74             :       break;
      75     1059335 :     case constantrange:
      76     1059335 :       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     2935470 :   ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
      84     2935470 :     *this = Other;
      85             :   }
      86             : 
      87             :   /// Custom assignment operator, to ensure Range gets initialized when
      88             :   /// assigning a constant range lattice element.
      89     9532163 :   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
      90             :     // If we change the state of this from constant range to non constant range,
      91             :     // destroy Range.
      92     9532163 :     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     9532163 :     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
      98             :         !Other.isNotConstant())
      99           0 :       ConstVal = nullptr;
     100             : 
     101     9532163 :     switch (Other.Tag) {
     102      887939 :     case constantrange:
     103      887939 :       if (!isConstantRange())
     104      886804 :         new (&Range) ConstantRange(Other.Range);
     105             :       else
     106             :         Range = Other.Range;
     107             :       break;
     108     2566705 :     case constant:
     109             :     case notconstant:
     110     2566705 :       ConstVal = Other.ConstVal;
     111     2566705 :       break;
     112             :     case overdefined:
     113             :     case undefined:
     114             :       break;
     115             :     }
     116     9532163 :     Tag = Other.Tag;
     117     9532163 :     return *this;
     118             :   }
     119             : 
     120             :   static ValueLatticeElement get(Constant *C) {
     121             :     ValueLatticeElement Res;
     122      275159 :     if (!isa<UndefValue>(C))
     123      275084 :       Res.markConstant(C);
     124             :     return Res;
     125             :   }
     126             :   static ValueLatticeElement getNot(Constant *C) {
     127             :     ValueLatticeElement Res;
     128      172924 :     if (!isa<UndefValue>(C))
     129      172924 :       Res.markNotConstant(C);
     130             :     return Res;
     131             :   }
     132       92006 :   static ValueLatticeElement getRange(ConstantRange CR) {
     133             :     ValueLatticeElement Res;
     134       92006 :     Res.markConstantRange(std::move(CR));
     135       92006 :     return Res;
     136             :   }
     137             :   static ValueLatticeElement getOverdefined() {
     138             :     ValueLatticeElement Res;
     139     4367480 :     Res.markOverdefined();
     140             :     return Res;
     141             :   }
     142             : 
     143           0 :   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           0 :   Constant *getConstant() const {
     150             :     assert(isConstant() && "Cannot get the constant of a non-constant!");
     151           0 :     return ConstVal;
     152             :   }
     153             : 
     154           0 :   Constant *getNotConstant() const {
     155             :     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
     156           0 :     return ConstVal;
     157             :   }
     158             : 
     159             :   const ConstantRange &getConstantRange() const {
     160             :     assert(isConstantRange() &&
     161             :            "Cannot get the constant-range of a non-constant-range!");
     162       91535 :     return Range;
     163             :   }
     164             : 
     165       68552 :   Optional<APInt> asConstantInteger() const {
     166       68552 :     if (isConstant() && isa<ConstantInt>(getConstant())) {
     167             :       return cast<ConstantInt>(getConstant())->getValue();
     168       70044 :     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
     169          69 :       return *getConstantRange().getSingleElement();
     170             :     }
     171             :     return None;
     172             :   }
     173             : 
     174             : private:
     175     4756054 :   void markOverdefined() {
     176     4756054 :     if (isOverdefined())
     177             :       return;
     178     4756054 :     if (isConstant() || isNotConstant())
     179       95414 :       ConstVal = nullptr;
     180     4756054 :     if (isConstantRange())
     181        8052 :       Range.~ConstantRange();
     182     4756054 :     Tag = overdefined;
     183             :   }
     184             : 
     185      275084 :   void markConstant(Constant *V) {
     186             :     assert(V && "Marking constant with NULL");
     187             :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     188       70225 :       markConstantRange(ConstantRange(CI->getValue()));
     189       70225 :       return;
     190             :     }
     191      204859 :     if (isa<UndefValue>(V))
     192             :       return;
     193             : 
     194             :     assert((!isConstant() || getConstant() == V) &&
     195             :            "Marking constant with different value");
     196             :     assert(isUndefined());
     197      204859 :     Tag = constant;
     198      204859 :     ConstVal = V;
     199             :   }
     200             : 
     201      172924 :   void markNotConstant(Constant *V) {
     202             :     assert(V && "Marking constant with NULL");
     203             :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     204       18460 :       markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
     205       18460 :       return;
     206             :     }
     207      154464 :     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      154464 :     Tag = notconstant;
     216      154464 :     ConstVal = V;
     217             :   }
     218             : 
     219      185190 :   void markConstantRange(ConstantRange NewR) {
     220      185190 :     if (isConstantRange()) {
     221        4499 :       if (NewR.isEmptySet())
     222           0 :         markOverdefined();
     223             :       else {
     224        4499 :         Range = std::move(NewR);
     225             :       }
     226        4499 :       return;
     227             :     }
     228             : 
     229             :     assert(isUndefined());
     230      180691 :     if (NewR.isEmptySet())
     231           8 :       markOverdefined();
     232             :     else {
     233      180683 :       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      922113 :   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
     242      922113 :     if (RHS.isUndefined() || isOverdefined())
     243             :       return false;
     244      880724 :     if (RHS.isOverdefined()) {
     245      297092 :       markOverdefined();
     246      297092 :       return true;
     247             :     }
     248             : 
     249      583632 :     if (isUndefined()) {
     250      398139 :       *this = RHS;
     251      398139 :       return !RHS.isUndefined();
     252             :     }
     253             : 
     254      185493 :     if (isConstant()) {
     255       87304 :       if (RHS.isConstant() && getConstant() == RHS.getConstant())
     256             :         return false;
     257       85980 :       markOverdefined();
     258       85980 :       return true;
     259             :     }
     260             : 
     261       98189 :     if (isNotConstant()) {
     262       73770 :       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
     263             :         return false;
     264         415 :       markOverdefined();
     265         415 :       return true;
     266             :     }
     267             : 
     268             :     assert(isConstantRange() && "New ValueLattice type?");
     269       24419 :     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       48838 :     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
     276       24419 :     if (NewR.isFullSet())
     277        5079 :       markOverdefined();
     278       19340 :     else if (NewR == getConstantRange())
     279             :       return false;
     280             :     else
     281        4499 :       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       91338 :   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
     295             :                        const ValueLatticeElement &Other) const {
     296       91338 :     if (isUndefined() || Other.isUndefined())
     297        5683 :       return UndefValue::get(Ty);
     298             : 
     299       85655 :     if (isConstant() && Other.isConstant())
     300         183 :       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
     301             : 
     302             :     // Integer constants are represented as ConstantRanges with single
     303             :     // elements.
     304       85472 :     if (!isConstantRange() || !Other.isConstantRange())
     305             :       return nullptr;
     306             : 
     307             :     const auto &CR = getConstantRange();
     308             :     const auto &OtherCR = Other.getConstantRange();
     309        4731 :     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
     310        3233 :       return ConstantInt::getTrue(Ty);
     311        2996 :     if (ConstantRange::makeSatisfyingICmpRegion(
     312             :             CmpInst::getInversePredicate(Pred), OtherCR)
     313        1498 :             .contains(CR))
     314        1478 :       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