Help with APValue comparisons

Hi,

I'm in the middle of cooking a patch which dramatically speeds up
compilation of constexpr functions. I have a partially working patch
already which "fixes" the bug at http://llvm.org/bugs/show_bug.cgi?id=12850.
I put "fixes" in quotes because at present the fix only works for the
"simple" cases as present, by which I mean where arguments evaluate to
APValues of type interger / float / complex / array / vector / struct.

The question I have is this: the above cases have, lets say, fairly obvious
ways for comparing whether two APValues are the same, however, I'm not sure
about LValue -- does anyone know of a suitable / correct way of comparing
two LValue-type APValues?

Many thanks!

Andy

For LValues that do not come from the same base aggregate, they are known to be != and relational comparisons (< <= >= >) are undefined. This is true even if one of the APValues is a null pointer -- the /representation/ of a null pointer is not guaranteed to be zero, and pointers are not guaranteed to be treated as unsigned.

Be careful about constant folding; this works under C++. (Not sure how to put constexpr into it, though.)

const char * const x = "abc";
const char * const y = "abc";
const bool same = (x == y); // true

For LValues that /do/ come from the same base aggregate, it looks like you can walk the "LValue path" and compare field/element locations along the way. These of course have a well-defined ordering. IIRC base objects always come before fields.

For this, be careful about unions:

const union { int i; unsigned u; } foo;
int * const bar = &foo.i;
unsigned * const baz = &foo.u;
const bool same = (bar == baz); // true

Hope that helps. Testing against runtime behavior isn't a bad idea whenever you're not sure, of course.

Jordan

Hi Jordan,

Thanks for your pointers. I've implemented an "isEqual" function as below.
If you have time, would you mind having a quick skim through please to see
if I've caught the right idea. At the moment, it holds up to the testing I
have performed so far, but I'm always working on more test-cases!

At this point, my concern is not that isEqual may not fully distinguish two
APValues that *are* equal, more that it should never say two APValues are
equal when they aren't. False negatives are much less of an issue than
false positives!

I haven't implemented equality checking for member pointers, yet. Again,
this is due to a lack of understand on exactly how to implement this check
(it seems even the dump / printPretty functions have not been fully
implemented for this type).

If you think my approach is valid, then I will post a tentative patch for
http://llvm.org/bugs/show_bug.cgi?id=12850.

Many, many thanks

Andy

// static member function of APValue
bool APValue::isEqual(const APValue &A, const APValue &B) {
  if (A.getKind() != B.getKind())
    return false;

  switch (A.getKind()) {
    case Uninitialized:
      return true;

    case Int:
      return (A.getInt() == B.getInt());

    case Float:
      return A.getFloat().bitwiseIsEqual(B.getFloat());

    case ComplexInt:
      return (A.getComplexIntReal() == B.getComplexIntReal()) &&
             (A.getComplexIntImag() == B.getComplexIntImag());

    case ComplexFloat:
      return A.getComplexFloatReal().bitwiseIsEqual(B.getComplexFloatReal())
&&
             A.getComplexFloatImag().bitwiseIsEqual(B.getComplexFloatImag());

    case Vector: {
      unsigned len = A.getVectorLength();
      if (len != B.getVectorLength()) return false;
      for (unsigned i = 0; i != len; ++i) {
        if (!isEqual(A.getVectorElt(i), B.getVectorElt(i)))
          return false;
      }
      return true;
    }

    case Array: {
      unsigned len = A.getArraySize();
      if (len != B.getArraySize()) return false;

      APValue FillerA, FillerB;
      if (A.hasArrayFiller()) FillerA = A.getArrayFiller();
      if (B.hasArrayFiller()) FillerB = B.getArrayFiller();

      // Two arrays are equal if their initialised elements are equal,
      // but also where one array is more initialised than another, where
      // those additional initialised elements are equal to the filler
      // of the other. If they both contain uninitialised elements, the
      // fillers must also match.
      for (unsigned i = 0, a = A.getArrayInitializedElts(),
                           b = B.getArrayInitializedElts(); i != len; ++i) {
        if (!isEqual(
              (i < a) ? A.getArrayInitializedElt(i) : FillerA,
              (i < b) ? B.getArrayInitializedElt(i) : FillerB))
          return false;
        if (i >= a && i >= b) // all the initialised elements *and* the
          break; // fillers have been compared; we're equal!
      }
      return true;
    }

    case Struct: {
      unsigned bases = A.getStructNumBases();
      if (bases != B.getStructNumBases()) return false;

      unsigned fields = A.getStructNumFields();
      if (fields != B.getStructNumFields()) return false;

      for (unsigned i = 0; i != bases; ++i) {
        if (!isEqual(A.getStructBase(i), B.getStructBase(i)))
          return false;
      }

      for (unsigned i = 0; i != fields; ++i) {
        if (!isEqual(A.getStructField(i), B.getStructField(i)))
          return false;
      }

      return true;
    }

    case Union:
      return (A.getUnionField() == B.getUnionField()) &&
             (isEqual(A.getUnionValue(), B.getUnionValue()));

    case AddrLabelDiff:
      return (A.getAddrLabelDiffLHS() == B.getAddrLabelDiffLHS()) &&
             (A.getAddrLabelDiffRHS() == B.getAddrLabelDiffRHS());

    case LValue: {
      LValueBase BaseA = A.getLValueBase();
      LValueBase BaseB = B.getLValueBase();

      // null pointers are not comparable
      if (!BaseA || !BaseB || BaseA.isNull() || BaseB.isNull()) return
false;

      bool IsValueDecl = BaseA.is<const ValueDecl*>();
      if (IsValueDecl != BaseB.is<const ValueDecl*>()) return false;

      QualType ElemTy;
      if (IsValueDecl) {
        const ValueDecl *VD = BaseA.get<const ValueDecl*>();
        ElemTy = VD->getType();
        if (VD != BaseB.get<const ValueDecl*>()) return false;
      } else {
        const Expr *E = BaseA.get<const Expr*>();
        ElemTy = E->getType();
        if (E != BaseB.get<const Expr*>()) return false;
      }

      bool HasPath = A.hasLValuePath();
      if (HasPath != B.hasLValuePath()) return false;

      if (!HasPath) {
        return A.getLValueOffset() == B.getLValueOffset();
      }

      ArrayRef<LValuePathEntry> PathA = A.getLValuePath();
      ArrayRef<LValuePathEntry> PathB = B.getLValuePath();
      if (PathA.size() != PathB.size()) return false;

      for (unsigned I = 0, N = PathA.size(); I != N; ++I) {
        if (ElemTy->getAs<RecordType>()) {
          const Decl *BaseOrMemberA =
BaseOrMemberType::getFromOpaqueValue(PathA[I].BaseOrMember).getPointer();
          const Decl *BaseOrMemberB =
BaseOrMemberType::getFromOpaqueValue(PathB[I].BaseOrMember).getPointer();

          if (BaseOrMemberA != BaseOrMemberB) return false;
          if (const CXXRecordDecl *RD =
dyn_cast<CXXRecordDecl>(BaseOrMemberA)) {
            const Type *T = RD->getTypeForDecl();
            assert(T && "getTypeForDecl did not return a valid value");
            ElemTy = QualType(T, 0);
          } else {
            const ValueDecl *VD = cast<ValueDecl>(BaseOrMemberA);
            ElemTy = VD->getType();
          }
        } else {
          if (PathA[I].ArrayIndex != PathB[I].ArrayIndex) return false;

          assert(dyn_cast<ArrayType>(ElemTy) && "Unexpected ElemTy");
          ElemTy = dyn_cast<ArrayType>(ElemTy)->getElementType();
        }
      }

      return true;
    }

    case MemberPointer:
      llvm_unreachable("isEqual unimplemented for this APValue kind!");
      return false;
  }
  llvm_unreachable("Unknown APValue kind!");
  return false;
}

case Float:
return A.getFloat().bitwiseIsEqual(B.getFloat());

I don’t think that this comparison is correct for IEEE floating point numbers. For example, two bit-identical NaN’s will compare equal, when they should compare not-equal. I haven’t used APFloat before, but from browsing the Doxygen, I think the comparison should be:

A.getFloat().compare(B.getFloat()) == cmpEqual

–Sean Silva

Hi,

I'm in the middle of cooking a patch which dramatically speeds up
compilation of constexpr functions. I have a partially working patch
already which "fixes" the bug at http://llvm.org/bugs/show_bug.cgi?id=12850.
I put "fixes" in quotes because at present the fix only works for the
"simple" cases as present, by which I mean where arguments evaluate to
APValues of type interger / float / complex / array / vector / struct.

The question I have is this: the above cases have, lets say, fairly obvious
ways for comparing whether two APValues are the same, however, I'm not sure
about LValue -- does anyone know of a suitable / correct way of comparing
two LValue-type APValues?

It depends what you're trying to compute.

Firstly, if either of them has a non-zero call index, and they weren't
both produced by the same evaluation, you must assume they are
different, because we no longer know what they referred to.

If you want to know whether they point to the same address, compare
the base and the offset.

Otherwise, you need to compare the base, offset and path. That should
always work (the one-past-the-end flag can be deduced in this case, so
that covers all the relevant semantic information). Alternatively, if
both values have paths (as they should for your case), you can compare
the base, path and one-past-the-end flag (the symbolic representation
of the glvalue) -- the offset can be deduced from that information.

Have you measured the memory and performance impact of this work on
well-written constexpr functions (those that don't rely on the
compiler perfoming memoization) and those that manipulate large
objects?

Richard