[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

27

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

84

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

179

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

233

This can also work for:

• ConstantExpr for ICMP_EQ.
• undefined

245

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

27

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

245

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;
+}  // end namespace llvm
+#endif

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   ScalarEvolutionNormalization.cpp
   SparsePropagation.cpp
   TargetLibraryInfo.cpp
   TargetTransformInfo.cpp
   Trace.cpp
   TypeBasedAliasAnalysis.cpp
   TypeMetadataUtils.cpp
   ScopedNoAliasAA.cpp
+  ValueLattice.cpp
   ValueTracking.cpp
   VectorUtils.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Analysis
 
   DEPENDS
   intrinsics_gen
   )

lib/Analysis/LazyValueInfo.cpp

 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Analysis/ValueLattice.h"
 #include "llvm/IR/AssemblyAnnotationWriter.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
                 "Lazy Value Information Analysis", false, true)
 
 namespace llvm {
   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
 }
 
 AnalysisKey LazyValueAnalysis::Key;
 
-//===----------------------------------------------------------------------===//
-//                               LVILatticeVal
-//===----------------------------------------------------------------------===//
-
-/// This is the information tracked by LazyValueInfo for each value.
-///
-/// FIXME: This is basically just for bringup, this can be made a lot more rich
-/// in the future.
-///
-namespace {
-class LVILatticeVal {
-  enum LatticeValueTy {
-    /// 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.
-  LatticeValueTy 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.
-  void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
-    if (RHS.isUndefined() || isOverdefined())
-      return;
-    if (RHS.isOverdefined()) {
-      markOverdefined();
-      return;
-    }
-
-    if (isUndefined()) {
-      *this = RHS;
-      return;
-    }
-
-    if (isConstant()) {
-      if (RHS.isConstant() && Val == RHS.Val)
-          return;
-      markOverdefined();
-      return;
-    }
-
-    if (isNotConstant()) {
-      if (RHS.isNotConstant() && Val == RHS.Val)
-          return;
-      markOverdefined();
-      return;
-    }
-
-    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;
-    }
-    ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
-    if (NewR.isFullSet())
-      markOverdefined();
-    else
-      markConstantRange(std::move(NewR));
-  }
-};
-
-} // end anonymous namespace.
-
-namespace llvm {
-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() << '>';
-}
-}
-
 /// Returns true if this lattice value represents at most one possible value.
 /// This is as precise as any lattice value can get while still representing
 /// reachable code.
 static bool hasSingleValue(const LVILatticeVal &Val) {
   if (Val.isConstantRange() &&
       Val.getConstantRange().isSingleElement())
     // Integer constants are single element ranges
     return true;

lib/Analysis/ValueLattice.cpp

+//===- ValueLattice.cpp - 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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ValueLattice.h"
+
+namespace llvm {
+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