[ValueLattice] Use union to shave off ptr size bytes from elements.

[fhahn]

Summary

By using a union for Constant* and ConstantRange we can shave off ptr
size bytes off lattice elements. On 64 bit systems, it brings down the
size to 40 bytes from 48 bytes.

Initialization of Range happens on-demand using placement new, if the
state changes to constantrange from non-constantrange. Similarly, the
Range object is destroyed if the state changes from constantrange to
non-constantrange.

[fhahn]

ping

[reames]

Bunch of minor comments, but once those addressed, likely good to go.

include/llvm/Analysis/ValueLattice.h

58

Minor: Calling this const is confusing. I keep reading this as "Const... Range" which is misleading. Val or ConstVal might be more clear.

84

You could initialize to undefined, then just invoke the operator= method on this.

86

Might make sense to add a ConstantRange copy constructor or move constructor. You have this idiom in a couple of places.

105

For error detection, it would be good to null out the Const field when switching away from something containing a Const.

110

Another instance of the move constructor.

182

Same point about nulling Const here.

235

You can use a move here. Or a move constructor if there is one.

275

These uses of cover functions should be NFC on their own. Please separate and commit to reduce the diff in next round of review.

[fhahn]

Thanks for having a look!

include/llvm/Analysis/ValueLattice.h

86

ConstantRange already has a copy constructor and I updated the code to use ìt: new (&Range) ConstantRange(Other.Range);. I hope that I understood what you meant correctly :)

[davide]

LGTM after your changes but please wait for Philip.

[reames]

In D41903#981227, @davide wrote:

LGTM after your changes but please wait for Philip.

In a case like this where I only had minor comments, please don't wait for me. If davade things this is good to go, run with it. I tend to be very busy and blocking anyone's forward progress on my availability is a bad idea.

[reames]

Also, LGTM since I did have time to look through this time. :)

[fhahn]

Great, thanks for having a look!

include/llvm/Analysis/ValueLattice.h

enum ValueLatticeElementTy {
 
     /// 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.
   ValueLatticeElementTy Tag;
-  Constant *Val;
+
+  /// 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:
-  ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {}
+  // 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) {
public:
   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;
+    return ConstVal;
   }
 
   Constant *getNotConstant() const {
     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
-    return Val;
+    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>(Val)) {
-      return cast<ConstantInt>(Val)->getValue();
-    } else if (isConstantRange() && Range.isSingleElement()) {
-      return *Range.getSingleElement();
+    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;
-    Val = V;
+    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;
-    Val = V;
+    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;
-      Range = std::move(NewR);
+      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;
bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
 
     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
       markConstantRange(std::move(NewR));
     return true;
   }
 
   ConstantInt *getConstantInt() const {