[LVI] Move LVILatticeVal class to separate header file (NFC).

[fhahn]

Summary

This allows sharing the lattice value code between LVI and SCCP (D36656).

It also adds a satisfiesPredicate function, used by D36656.

[fhahn]

Fix formatting issue

[sanjoy]

This isn't a "move" right, since you didn't delete the original?

[fhahn]

In D37591#863991, @sanjoy wrote:

This isn't a "move" right, since you didn't delete the original?

Err yes indeed, I did not upload the latest version of the diff :/ I'll upload the full diff tomorrow.

[fhahn]

Remove duplicated code

[sanjoy]

include/llvm/Analysis/ValueLattice.h

28

I think this should no longer be called LVILatticeVal, now that it is used outside LVI.

85

Since you're moving the code anyway, can you also run clang-format over this file?

180

Now that this lives outside LVI, we need to be clearer about what this actually does (modifies *this to approximate both *this and RHS).

234

This can also work for:

• ConstantExpr for ICMP_EQ.
• undefined

246

Why doesn't ConstantRange::makeSatisfyingICmpRegion work for ICMP_NE and ICMP_EQ?

Please also add a test case to unittests/ for this function.

[fhahn]

@sanjoy thank you very much for the review and sorry for taking a while to update the patch.

[fhahn]

include/llvm/Analysis/ValueLattice.h

28

Agreed, I named it to ValueLatticeVal, which is slightly longer.

246

ConstantRange::makeSatisfyingICmpRegion works on those cases too, thanks! I've added unit tests too

[sanjoy]

LGTM with nits

include/llvm/Analysis/ValueLattice.h

28

Let's call this ValueLatticeElement. It is a bit verbose, but I think it is to the point, and with auto the more verbose type name probably won't bite us as much.

177

Please elaborate on what "Merge" means in this context.

245

Is the LLVM_ATTRIBUTE_USED still needed?

[fhahn]

Thanks @sanjoy! Addressed nits

[fhahn]

include/llvm/Analysis/ValueLattice.h

245

Nope it is not I think. I've removed it.

include/llvm/Analysis/ValueLattice.h

+//===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_VALUELATTICE_H
+#define LLVM_ANALYSIS_VALUELATTICE_H
+
+#include "llvm/IR/ConstantRange.h"
+#include "llvm/IR/Constants.h"
+//
+//===----------------------------------------------------------------------===//
+//                               LVILatticeVal
+//===----------------------------------------------------------------------===//
+
+/// 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 LVILatticeVal {
+  enum LVILatticeValueTy {
+    /// 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
+  };
+
+  /// Val: This stores the current lattice value along with the Constant* for
+  /// the constant if this is a 'constant' or 'notconstant' value.
+  LVILatticeValueTy Tag;
+  Constant *Val;
+  ConstantRange Range;
+
+public:
+  LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
+
+  static LVILatticeVal get(Constant *C) {
+    LVILatticeVal Res;
+    if (!isa<UndefValue>(C))
+      Res.markConstant(C);
+    return Res;
+  }
+  static LVILatticeVal getNot(Constant *C) {
+    LVILatticeVal Res;
+    if (!isa<UndefValue>(C))
+      Res.markNotConstant(C);
+    return Res;
+  }
+  static LVILatticeVal getRange(ConstantRange CR) {
+    LVILatticeVal Res;
+    Res.markConstantRange(std::move(CR));
+    return Res;
+  }
+  static LVILatticeVal getOverdefined() {
+    LVILatticeVal 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 Val;
+  }
+
+  Constant *getNotConstant() const {
+    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
+    return Val;
+  }
+
+  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>(Val)) {
+      return cast<ConstantInt>(Val)->getValue();
+    } else if (isConstantRange() && Range.isSingleElement()) {
+      return *Range.getSingleElement();
+    }
+    return None;
+  }
+
+private:
+  void markOverdefined() {
+    if (isOverdefined())
+      return;
+    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;
+    Val = 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;
+    Val = 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;
+      Range = std::move(NewR);
+    }
+  }
+
+public:
+
+  /// Merge the specified lattice value into this one, updating this
+  /// one and returning true if anything changed.
+  bool mergeIn(const LVILatticeVal &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() && Val == RHS.Val)
+          return false;
+      markOverdefined();
+      return true;
+    }
+
+    if (isNotConstant()) {
+      if (RHS.isNotConstant() && Val == RHS.Val)
+          return false;
+      markOverdefined();
+      return true;
+    }
+
+    assert(isConstantRange() && "New LVILattice 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 = Range.unionWith(RHS.getConstantRange());
+    if (NewR.isFullSet())
+      markOverdefined();
+    else
+      markConstantRange(std::move(NewR));
+    return true;
+  }
+
+  ConstantInt *getConstantInt() const {
+    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
+           "No integer constant");
+    return cast<ConstantInt>(getConstant());
+  }
+
+  bool satisfiesPredicate(CmpInst::Predicate Pred,
+                          const LVILatticeVal &Other) const {
+    // TODO: share with LVI getPredicateResult.
+    // Integer constants are represented as ConstantRanges with single
+    // elements.
+    if (!isConstantRange() || !Other.isConstantRange())
+      return false;
+
+    const auto &CR = getConstantRange();
+    const auto &OtherCR = Other.getConstantRange();
+    switch (Pred) {
+    case CmpInst::ICMP_NE:
+      return CR.intersectWith(OtherCR).isEmptySet();
+    case CmpInst::ICMP_EQ:
+      return CR.isSingleElement() && OtherCR.isSingleElement() &&
+             CR == OtherCR;
+    default:
+      return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
+    }
+  }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
+    LLVM_ATTRIBUTE_USED;
+raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
+  if (Val.isUndefined())
+    return OS << "undefined";
+  if (Val.isOverdefined())
+    return OS << "overdefined";
+
+  if (Val.isNotConstant())
+    return OS << "notconstant<" << *Val.getNotConstant() << '>';
+  if (Val.isConstantRange())
+    return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
+              << Val.getConstantRange().getUpper() << '>';
+  return OS << "constant<" << *Val.getConstant() << '>';
+}
+
+}  // end namespace llvm
+#endif