basicaa_trunc.patch

commit 3c4ef3f8cf3347c6aea77fd63ee84555a33af5d7
Author: Nikita Popov <nikita.ppv@gmail.com>
Date:   Wed Sep 29 22:18:54 2021 +0200

    wip

diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index 5d9a5f6a1de6..74a0a7f6fcb1 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -274,41 +274,53 @@ void EarliestEscapeInfo::removeInstruction(Instruction *I) {
 //===----------------------------------------------------------------------===//
 
 namespace {
-/// Represents zext(sext(V)).
+/// Represents zext(sext(trunc(V))).
 struct ExtendedValue {
   const Value *V;
-  unsigned ZExtBits;
-  unsigned SExtBits;
+  unsigned ZExtBits = 0;
+  unsigned SExtBits = 0;
+  unsigned TruncBits = 0;
 
-  explicit ExtendedValue(const Value *V, unsigned ZExtBits = 0,
-                         unsigned SExtBits = 0)
-      : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits) {}
+  explicit ExtendedValue(const Value *V) : V(V) {}
+  ExtendedValue(const Value *V, unsigned ZExtBits, unsigned SExtBits,
+                unsigned TruncBits)
+      : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits) {}
 
   unsigned getBitWidth() const {
-    return V->getType()->getPrimitiveSizeInBits() + ZExtBits + SExtBits;
+    return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits
+               + SExtBits;
   }
 
   ExtendedValue withValue(const Value *NewV) const {
-    return ExtendedValue(NewV, ZExtBits, SExtBits);
+    return ExtendedValue(NewV, ZExtBits, SExtBits, TruncBits);
   }
 
   ExtendedValue withZExtOfValue(const Value *NewV) const {
     unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
                         NewV->getType()->getPrimitiveSizeInBits();
+    if (ExtendBy <= TruncBits)
+      return ExtendedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
+
     // zext(sext(zext(NewV))) == zext(zext(zext(NewV)))
-    return ExtendedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0);
+    ExtendBy -= TruncBits;
+    return ExtendedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0);
   }
 
   ExtendedValue withSExtOfValue(const Value *NewV) const {
     unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
                         NewV->getType()->getPrimitiveSizeInBits();
+    if (ExtendBy <= TruncBits)
+      return ExtendedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
+
     // zext(sext(sext(NewV)))
-    return ExtendedValue(NewV, ZExtBits, SExtBits + ExtendBy);
+    ExtendBy -= TruncBits;
+    return ExtendedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0);
   }
 
   APInt evaluateWith(APInt N) const {
     assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
            "Incompatible bit width");
+    if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits);
     if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits);
     if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits);
     return N;
@@ -317,6 +329,7 @@ struct ExtendedValue {
   KnownBits evaluateWith(KnownBits N) const {
     assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
            "Incompatible bit width");
+    if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits);
     if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits);
     if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits);
     return N;
@@ -325,6 +338,7 @@ struct ExtendedValue {
   ConstantRange evaluateWith(ConstantRange N) const {
     assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
            "Incompatible bit width");
+    if (TruncBits) N = N.truncate(N.getBitWidth() - TruncBits);
     if (SExtBits) N = N.signExtend(N.getBitWidth() + SExtBits);
     if (ZExtBits) N = N.zeroExtend(N.getBitWidth() + ZExtBits);
     return N;
@@ -333,6 +347,7 @@ struct ExtendedValue {
   bool canDistributeOver(bool NUW, bool NSW) const {
     // zext(x op<nuw> y) == zext(x) op<nuw> zext(y)
     // sext(x op<nsw> y) == sext(x) op<nsw> sext(y)
+    // trunc(x op y) == trunc(x) op trunc(y)
     return (!ZExtBits || NUW) && (!SExtBits || NSW);
   }
 
@@ -341,7 +356,7 @@ struct ExtendedValue {
   }
 };
 
-/// Represents zext(sext(V)) * Scale + Offset.
+/// Represents zext(sext(trunc(V))) * Scale + Offset.
 struct LinearExpression {
   ExtendedValue Val;
   APInt Scale;
@@ -388,6 +403,11 @@ static LinearExpression GetLinearExpression(
       if (!Val.canDistributeOver(NUW, NSW))
         return Val;
 
+      // While we can distribute over trunc, we cannot preserve nowrap flags
+      // in that case.
+      if (Val.TruncBits)
+        NUW = NSW = false;
+
       LinearExpression E(Val);
       switch (BOp->getOpcode()) {
       default:
@@ -478,7 +498,7 @@ static unsigned getMaxPointerSize(const DataLayout &DL) {
 
 namespace {
 // A linear transformation of a Value; this class represents
-// ZExt(SExt(V, SExtBits), ZExtBits) * Scale.
+// ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale.
 struct VariableGEPIndex {
   ExtendedValue Val;
   APInt Scale;
@@ -664,8 +684,9 @@ BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
       // sign extended to pointer size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
       unsigned SExtBits = PointerSize > Width ? PointerSize - Width : 0;
+      unsigned TruncBits = PointerSize < Width ? Width - PointerSize : 0;
       LinearExpression LE = GetLinearExpression(
-          ExtendedValue(Index, 0, SExtBits), DL, 0, AC, DT);
+          ExtendedValue(Index, 0, SExtBits, TruncBits), DL, 0, AC, DT);
 
       // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
       // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
@@ -681,7 +702,7 @@ BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
       APInt ScaledOffset = LE.Offset.sextOrTrunc(MaxPointerSize)
                            .smul_ov(Scale, Overflow);
       if (Overflow) {
-        LE = LinearExpression(ExtendedValue(Index, 0, SExtBits));
+        LE = LinearExpression(ExtendedValue(Index, 0, SExtBits, TruncBits));
       } else {
         Decomposed.Offset += ScaledOffset;
         Scale *= LE.Scale.sextOrTrunc(MaxPointerSize);