llvm.org GIT mirror llvm / c313a17 include / llvm / Analysis / ValueLattice.h
c313a17

Tree @c313a17 (Download .tar.gz)

ValueLattice.h @c313a17

5133f6f
 
6b54768
 
 
5133f6f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2d05f76
 
 
 
 
 
 
 
5133f6f
 
2d05f76
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5133f6f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2d05f76
5133f6f
 
 
 
2d05f76
5133f6f
 
 
 
 
 
 
 
 
2d05f76
 
 
 
5133f6f
 
 
 
 
 
 
 
2d05f76
 
 
 
5133f6f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2d05f76
5133f6f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2d05f76
5133f6f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2d05f76
5133f6f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
c99a2c4
5133f6f
 
 
 
 
 
c99a2c4
5133f6f
 
 
 
 
 
 
 
 
 
 
 
c99a2c4
5133f6f
 
a0883e0
 
5133f6f
 
 
 
 
 
 
 
 
 
 
dafcef6
 
 
 
 
5133f6f
dafcef6
5133f6f
dafcef6
 
5133f6f
 
 
 
dafcef6
5133f6f
 
 
dafcef6
 
 
 
 
 
 
 
5133f6f
 
 
 
 
 
 
//===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_VALUELATTICE_H
#define LLVM_ANALYSIS_VALUELATTICE_H

#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
//
//===----------------------------------------------------------------------===//
//                               ValueLatticeElement
//===----------------------------------------------------------------------===//

/// This class represents lattice values for constants.
///
/// FIXME: This is basically just for bringup, this can be made a lot more rich
/// in the future.
///

namespace llvm {
class ValueLatticeElement {
  enum ValueLatticeElementTy {
    /// This Value has no known value yet.  As a result, this implies the
    /// producing instruction is dead.  Caution: We use this as the starting
    /// state in our local meet rules.  In this usage, it's taken to mean
    /// "nothing known yet".
    undefined,

    /// This Value has a specific constant value.  (For constant integers,
    /// constantrange is used instead.  Integer typed constantexprs can appear
    /// as constant.)
    constant,

    /// This Value is known to not have the specified value.  (For constant
    /// integers, constantrange is used instead.  As above, integer typed
    /// constantexprs can appear here.)
    notconstant,

    /// The Value falls within this range. (Used only for integer typed values.)
    constantrange,

    /// We can not precisely model the dynamic values this value might take.
    overdefined
  };

  ValueLatticeElementTy Tag;

  /// The union either stores a pointer to a constant or a constant range,
  /// associated to the lattice element. We have to ensure that Range is
  /// initialized or destroyed when changing state to or from constantrange.
  union {
    Constant *ConstVal;
    ConstantRange Range;
  };

public:
  // Const and Range are initialized on-demand.
  ValueLatticeElement() : Tag(undefined) {}

  /// Custom destructor to ensure Range is properly destroyed, when the object
  /// is deallocated.
  ~ValueLatticeElement() {
    switch (Tag) {
    case overdefined:
    case undefined:
    case constant:
    case notconstant:
      break;
    case constantrange:
      Range.~ConstantRange();
      break;
    };
  }

  /// Custom copy constructor, to ensure Range gets initialized when
  /// copying a constant range lattice element.
  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
    *this = Other;
  }

  /// Custom assignment operator, to ensure Range gets initialized when
  /// assigning a constant range lattice element.
  ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
    // If we change the state of this from constant range to non constant range,
    // destroy Range.
    if (isConstantRange() && !Other.isConstantRange())
      Range.~ConstantRange();

    // If we change the state of this from a valid ConstVal to another a state
    // without a valid ConstVal, zero the pointer.
    if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
        !Other.isNotConstant())
      ConstVal = nullptr;

    switch (Other.Tag) {
    case constantrange:
      if (!isConstantRange())
        new (&Range) ConstantRange(Other.Range);
      else
        Range = Other.Range;
      break;
    case constant:
    case notconstant:
      ConstVal = Other.ConstVal;
      break;
    case overdefined:
    case undefined:
      break;
    }
    Tag = Other.Tag;
    return *this;
  }

  static ValueLatticeElement get(Constant *C) {
    ValueLatticeElement Res;
    if (!isa<UndefValue>(C))
      Res.markConstant(C);
    return Res;
  }
  static ValueLatticeElement getNot(Constant *C) {
    ValueLatticeElement Res;
    if (!isa<UndefValue>(C))
      Res.markNotConstant(C);
    return Res;
  }
  static ValueLatticeElement getRange(ConstantRange CR) {
    ValueLatticeElement Res;
    Res.markConstantRange(std::move(CR));
    return Res;
  }
  static ValueLatticeElement getOverdefined() {
    ValueLatticeElement Res;
    Res.markOverdefined();
    return Res;
  }

  bool isUndefined() const { return Tag == undefined; }
  bool isConstant() const { return Tag == constant; }
  bool isNotConstant() const { return Tag == notconstant; }
  bool isConstantRange() const { return Tag == constantrange; }
  bool isOverdefined() const { return Tag == overdefined; }

  Constant *getConstant() const {
    assert(isConstant() && "Cannot get the constant of a non-constant!");
    return ConstVal;
  }

  Constant *getNotConstant() const {
    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
    return ConstVal;
  }

  const ConstantRange &getConstantRange() const {
    assert(isConstantRange() &&
           "Cannot get the constant-range of a non-constant-range!");
    return Range;
  }

  Optional<APInt> asConstantInteger() const {
    if (isConstant() && isa<ConstantInt>(getConstant())) {
      return cast<ConstantInt>(getConstant())->getValue();
    } else if (isConstantRange() && getConstantRange().isSingleElement()) {
      return *getConstantRange().getSingleElement();
    }
    return None;
  }

private:
  void markOverdefined() {
    if (isOverdefined())
      return;
    if (isConstant() || isNotConstant())
      ConstVal = nullptr;
    if (isConstantRange())
      Range.~ConstantRange();
    Tag = overdefined;
  }

  void markConstant(Constant *V) {
    assert(V && "Marking constant with NULL");
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
      markConstantRange(ConstantRange(CI->getValue()));
      return;
    }
    if (isa<UndefValue>(V))
      return;

    assert((!isConstant() || getConstant() == V) &&
           "Marking constant with different value");
    assert(isUndefined());
    Tag = constant;
    ConstVal = V;
  }

  void markNotConstant(Constant *V) {
    assert(V && "Marking constant with NULL");
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
      return;
    }
    if (isa<UndefValue>(V))
      return;

    assert((!isConstant() || getConstant() != V) &&
           "Marking constant !constant with same value");
    assert((!isNotConstant() || getNotConstant() == V) &&
           "Marking !constant with different value");
    assert(isUndefined() || isConstant());
    Tag = notconstant;
    ConstVal = V;
  }

  void markConstantRange(ConstantRange NewR) {
    if (isConstantRange()) {
      if (NewR.isEmptySet())
        markOverdefined();
      else {
        Range = std::move(NewR);
      }
      return;
    }

    assert(isUndefined());
    if (NewR.isEmptySet())
      markOverdefined();
    else {
      Tag = constantrange;
      new (&Range) ConstantRange(std::move(NewR));
    }
  }

public:
  /// Updates this object to approximate both this object and RHS. Returns
  /// true if this object has been changed.
  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
    if (RHS.isUndefined() || isOverdefined())
      return false;
    if (RHS.isOverdefined()) {
      markOverdefined();
      return true;
    }

    if (isUndefined()) {
      *this = RHS;
      return !RHS.isUndefined();
    }

    if (isConstant()) {
      if (RHS.isConstant() && getConstant() == RHS.getConstant())
        return false;
      markOverdefined();
      return true;
    }

    if (isNotConstant()) {
      if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
        return false;
      markOverdefined();
      return true;
    }

    assert(isConstantRange() && "New ValueLattice type?");
    if (!RHS.isConstantRange()) {
      // We can get here if we've encountered a constantexpr of integer type
      // and merge it with a constantrange.
      markOverdefined();
      return true;
    }
    ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
    if (NewR.isFullSet())
      markOverdefined();
    else if (NewR == getConstantRange())
      return false;
    else
      markConstantRange(std::move(NewR));
    return true;
  }

  ConstantInt *getConstantInt() const {
    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
           "No integer constant");
    return cast<ConstantInt>(getConstant());
  }

  /// Compares this symbolic value with Other using Pred and returns either
  /// true, false or undef constants, or nullptr if the comparison cannot be
  /// evaluated.
  Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
                       const ValueLatticeElement &Other) const {
    if (isUndefined() || Other.isUndefined())
      return UndefValue::get(Ty);

    if (isConstant() && Other.isConstant())
      return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());

    // Integer constants are represented as ConstantRanges with single
    // elements.
    if (!isConstantRange() || !Other.isConstantRange())
      return nullptr;

    const auto &CR = getConstantRange();
    const auto &OtherCR = Other.getConstantRange();
    if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
      return ConstantInt::getTrue(Ty);
    if (ConstantRange::makeSatisfyingICmpRegion(
            CmpInst::getInversePredicate(Pred), OtherCR)
            .contains(CR))
      return ConstantInt::getFalse(Ty);

    return nullptr;
  }
};

raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);

} // end namespace llvm
#endif