Refactor computeKnownBits alignment handling code

[apilipenko]

Summary

This is a preparatory refactoring for using new alignment attributes/metadata (D12844, D12853) in computeKnownBits.

[reames]

lib/Analysis/ValueTracking.cpp

1488 ↗

(On Diff #35076)

I'm not sure that removing these returns is actually equivalent. Does computeKnownBits guarantee to preserve any known bits on entry? (I don't think so?) If not, then letting these flow down into the generic code may loose information.

[apilipenko]

lib/Analysis/ValueTracking.cpp

1488 ↗

(On Diff #35076)

In all existing code paths computeKnownBits starts with cleared bits on both KnownZero and KnownOne. In my patch I just made it explicit by moving the lines which clear both bit sets before the code which handles aligned values. See line 1466.

[reames]

lib/Analysis/ValueTracking.cpp

1488 ↗

(On Diff #35076)

I wasn't commenting on the movement of the clearing. I was commenting on the removal of the return.

[hfinkel]

lib/Analysis/ValueTracking.cpp

1488 ↗

(On Diff #35076)

I think this is okay because the functions below that clear known bits are only called if V is a GlobalAlias or an Operator, neither of which is true if V is known to be a GlobalObject (or an Argument).

I agree, however, that the relevant logic here is becoming increasingly unclear. How about we move this alignment logic below the computeKnownBitsFromOperator call, so that it is clear (at least based on existing commentary) that we only ever refine this information? This also has the benefit that we can use an 'else if' and elide some unnecessary dyn_cast checks.

[reames]

lib/Analysis/ValueTracking.cpp

1488 ↗

(On Diff #35076)

Hal, I follow your logic for why the current patch is correct. Moving the flow as you suggest would be one option. Adding a couple of assertions that the sets are empty at the point we call each routine would be another. Adding explicit merge code to future proof this code would be a a third. I'd be fine with any of the options. I'd mildly lean towards the explicit merging code since I think that supports the direction Artur wants to take this code (right?).

[apilipenko]

Introduce new function getAlignemnt(Value*). I'm going to use this function from isAligned as well.

Alignment related code in computeKnownBits is moved below the computeKnownBitsFromOperator call.

[reames]

Much, much clearer. LGTM

lib/Analysis/ValueTracking.cpp

1516 ↗

(On Diff #35745)

I might put this inside a check for pointer type, but it's already handled by the called code and would only be a minor improvement on a much larger improvement.

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
                               Depth, Q);
           break;
         }
       }
     }
   }
 }
 
+static unsigned getAlignment(Value *V, const DataLayout &DL) {
+  unsigned Align = 0;
+  if (auto *GO = dyn_cast<GlobalObject>(V)) {
+    Align = GO->getAlignment();
+    if (Align == 0) {
+      if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
+        Type *ObjectType = GVar->getType()->getElementType();
+        if (ObjectType->isSized()) {
+          // If the object is defined in the current Module, we'll be giving
+          // it the preferred alignment. Otherwise, we have to assume that it
+          // may only have the minimum ABI alignment.
+          if (GVar->isStrongDefinitionForLinker())
+            Align = DL.getPreferredAlignment(GVar);
+          else
+            Align = DL.getABITypeAlignment(ObjectType);
+        }
+      }
+    }
+  } else if (Argument *A = dyn_cast<Argument>(V)) {
+    Align = A->getType()->isPointerTy() ? A->getParamAlignment() : 0;
+
+    if (!Align && A->hasStructRetAttr()) {
+      // An sret parameter has at least the ABI alignment of the return type.
+      Type *EltTy = cast<PointerType>(A->getType())->getElementType();
+      if (EltTy->isSized())
+        Align = DL.getABITypeAlignment(EltTy);
+    }
+  }
+  return Align;
+}
+
 /// Determine which bits of V are known to be either zero or one and return
 /// them in the KnownZero/KnownOne bit sets.
 ///
 /// NOTE: we cannot consider 'undef' to be "IsZero" here.  The problem is that
 /// we cannot optimize based on the assumption that it is zero without changing
 /// it to be an explicit zero.  If we don't change it to zero, other code could
 /// optimized based on the contradictory assumption that it is non-zero.
 /// Because instcombine aggressively folds operations with undef args anyway,
if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
     for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
       Elt = CDS->getElementAsInteger(i);
       KnownZero &= ~Elt;
       KnownOne &= Elt;
     }
     return;
   }
 
-  // The address of an aligned GlobalValue has trailing zeros.
-  if (auto *GO = dyn_cast<GlobalObject>(V)) {
-    unsigned Align = GO->getAlignment();
-    if (Align == 0) {
-      if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
-        Type *ObjectType = GVar->getType()->getElementType();
-        if (ObjectType->isSized()) {
-          // If the object is defined in the current Module, we'll be giving
-          // it the preferred alignment. Otherwise, we have to assume that it
-          // may only have the minimum ABI alignment.
-          if (GVar->isStrongDefinitionForLinker())
-            Align = DL.getPreferredAlignment(GVar);
-          else
-            Align = DL.getABITypeAlignment(ObjectType);
-        }
-      }
-    }
-    if (Align > 0)
-      KnownZero = APInt::getLowBitsSet(BitWidth,
-                                       countTrailingZeros(Align));
-    else
-      KnownZero.clearAllBits();
-    KnownOne.clearAllBits();
-    return;
-  }
-
-  if (Argument *A = dyn_cast<Argument>(V)) {
-    unsigned Align = A->getType()->isPointerTy() ? A->getParamAlignment() : 0;
-
-    if (!Align && A->hasStructRetAttr()) {
-      // An sret parameter has at least the ABI alignment of the return type.
-      Type *EltTy = cast<PointerType>(A->getType())->getElementType();
-      if (EltTy->isSized())
-        Align = DL.getABITypeAlignment(EltTy);
-    }
-
-    if (Align)
-      KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
-    else
-      KnownZero.clearAllBits();
-    KnownOne.clearAllBits();
-
-    // Don't give up yet... there might be an assumption that provides more
-    // information...
-    computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
-
-    // Or a dominating condition for that matter
-    if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
-      computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL,
-                                              Depth, Q);
-    return;
-  }
-
   // Start out not knowing anything.
   KnownZero.clearAllBits(); KnownOne.clearAllBits();
 
   // Limit search depth.
   // All recursive calls that increase depth must come after this.
   if (Depth == MaxDepth)
     return;
 
   // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
   // the bits of its aliasee.
   if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
     if (!GA->mayBeOverridden())
       computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, DL, Depth + 1, Q);
     return;
   }
 
   if (Operator *I = dyn_cast<Operator>(V))
     computeKnownBitsFromOperator(I, KnownZero, KnownOne, DL, Depth, Q);
 
+  // Aligned pointers have trailing zeros - refine KnownZero set
+  if (V->getType()->isPointerTy()) {
+    unsigned Align = getAlignment(V, DL);
+    if (Align)
+      KnownZero |= APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
+  }
+
   // computeKnownBitsFromAssume and computeKnownBitsFromDominatingCondition
   // strictly refines KnownZero and KnownOne. Therefore, we run them after
   // computeKnownBitsFromOperator.
 
   // Check whether a nearby assume intrinsic can determine some known bits.
   computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
 
   // Check whether there's a dominating condition which implies something about