[ValueTracking] Let isGuaranteedNotToBeUndefOrPoison look into more constants/instructions

[aqjune]

Summary

This patch helps isGuaranteedNotToBeUndefOrPoison look into more constants and instructions (bitcast/alloca/gep/fcmp).

To deal with bitcast, Depth is added to isGuaranteedNotToBeUndefOrPoison.

This patch is splitted from https://reviews.llvm.org/D75808.

Checked with Alive2

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4708–4723

misplaced comment

4712

This is not 100% the idea behind stripPointerCastsSameRepresentation:
stripPointerCastsSameRepresentation says the bit-representation stays the same, not that there are no addrspacecasts stripped. If we assume an addressspacecast that is known not to modify the bit-representation will also not modify the poison/undef state, which I think is reasonable, we can do tihs.

[aqjune]

Update comments

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4708–4723

Added more text to the comment, my underlying idea was that null was also allowed in this case as well.

4712

Yes, I think in that case undef/poison should be preserved. LangRef says that addrspacecast can be no-op, I believe this function is dealing with the case.
Updated comment

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4708–4723

I still find it misplaced (and I dislike comments in a single conditional stmt without braces). Where does the GEP come from and why is it inbounds?

4712

As I said, the function will strip (any) casts that are known not to change the bit representation. I agree that this should be fine here but the comment makes it sounds as if only some addrspacecasts are stripped.

[aqjune]

Update comments

[aqjune]

Minor fix

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4712

Made the comment clearer & clarify why gep inbounds was mentioned here

[aqjune]

ping

[jdoerfert]

I don't see a problem in the logic but we need more tests, see below.

llvm/test/Transforms/InstSimplify/freeze.ll

270

We need more (negative) tests that verify we don't do thing we shouldn't. Optimally one for each restriction we have, e.g., gep non-inbounds with potential undef/poison operand (one for base one for index).

[reames]

llvm/lib/Analysis/ValueTracking.cpp

4724–4725

We should have the same recursion here with the depth limit to handle cycles.

4742

As a follow up, it would be nice to re-write this in terms of existing logic. For example, the operand handling part can be done as:
if (propagatesFullPoison(&I) && std::all_of(I.operands(), OpCheck)) return true;

You do need to filter instructions with poison producing flags above that. For that, you could possible factor out a function "localProducesPoison(Op)" based on the function generatePoisonChecks from PoisonChecking.cpp

This is optional follow on.

[aqjune]

Address comments

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4742

Yes, I agree having it would be good. I'll make a follow-up patch for this.

[jdoerfert]

I think I'm fine with this, wait for @reames to accept though.

llvm/lib/Analysis/ValueTracking.cpp

4722

Nit: No braces.
Use OpCheck for BitCastInst as well.

[aqjune]

Use OpCheck for BitCastInst, aggregate cases that only need operand checks

[aqjune]

Support ConstantDataVector too (needed by https://reviews.llvm.org/D76483)

[spatel]

This has already been reviewed by others, so if we are close to approval, it's fine...
But if I were starting this patch/review from scratch, I'd prefer that we add all of the tests with baseline CHECK lines as a preliminary commit, and then build the logic up in the code to improve those tests one-by-one.
IIUC, we can make the vector constant change independently of the recursion logic, so that part can be split off into a small separate patch?

llvm/include/llvm/Analysis/ValueTracking.h

605

Is there some reason we can't use the typical ValueTracking construct here?
We usually set default Depth = 0, and then increment up to "const unsigned MaxDepth = 6". We want to avoid making that "6" any more magical than it already is. :)

[aqjune]

Remove ConstantVector check, update test diff

[aqjune]

Make Depth increment from 0 to MaxDepth

[jdoerfert]

@spatel does this look better?
@reames you requested changes, we'll wait for you.

[spatel]

In D76010#1938205, @jdoerfert wrote:

@spatel does this look better?

Yes - I added a few more inline nits. I don't have a good understanding of the casting part of the patch, but other than that LGTM.

llvm/lib/Analysis/ValueTracking.cpp

4737–4738

nit: "auto *"

4741

nit: "auto *"

4766–4767

nit: "auto *"

4767

Use "I" in all of these clauses for consistency.
If the intent is to grow this list, might want to use a "switch(I->getOpcode())" already so later patches are minimal.

[aqjune]

Use switch

[aqjune]

clang-format

[aqjune]

Rebase

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4722

What does " To guarantee that the result isn't poison, the stripped pointer should be checked whether it is inbounds." mean? You cannot/should bot check the stripped value, e.g. determine how we got here.

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4722

What does " To guarantee that the result isn't poison, the stripped pointer should be checked whether it is inbounds." mean?

It means the stripped pointer should be an in-bounds address of an allocated object, not that it should be gep inbounds again ( .. if the base pointer is not an in bounds address of an allocated object, LangRef's getelementptr instruction).

[aqjune]

Minor update to a comment to clarify its meaning

[spatel]

llvm/test/Transforms/InstSimplify/freeze.ll

21–22

Please remove the TODO comments here and below.
And we could still separate the constant improvements into another patch to make incremental progress...

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4722

I think what you try to say is something along the lines of:

"To guarantee that the result isn't poison, the stripped pointer is checked as it has to be pointing into an allocated object or be null null to ensure inbounds getelement pointers with a zero offset could not produce poison."

[aqjune]

Address comments

[aqjune]

Is there any other change needed?
reames's comment (recursively calling the function with an increased Depth) is addressed too.

[jdoerfert]

I'm fine with this. @reames should probably say something.

[aqjune]

ping @reames

[aqjune]

Polite ping for @reames again - I'll be committing this on Friday.

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// Return true if this function can prove that V is never undef value
   /// or poison value.
   //
   /// If CtxI and DT are specified this method performs flow-sensitive analysis
   /// and returns true if it is guaranteed to be never undef or poison
   /// immediately before the CtxI.
   bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                         const Instruction *CtxI = nullptr,
-                                        const DominatorTree *DT = nullptr);
+                                        const DominatorTree *DT = nullptr,
+                                        unsigned Depth = 0);
 
   /// Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
     SPF_SMIN,                   /// Signed minimum
     SPF_UMIN,                   /// Unsigned minimum
     SPF_SMAX,                   /// Signed maximum
     SPF_UMAX,                   /// Unsigned maximum

llvm/lib/Analysis/ValueTracking.cpp

else if (isa<BinaryOperator>(I))
       return false;
     // Be conservative and return true.
     return true;
   }
 }
 
 bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                             const Instruction *CtxI,
-                                            const DominatorTree *DT) {
+                                            const DominatorTree *DT,
+                                            unsigned Depth) {
+  if (Depth >= MaxDepth)
+    return false;
+
   // If the value is a freeze instruction, then it can never
   // be undef or poison.
   if (isa<FreezeInst>(V))
     return true;
   // TODO: Some instructions are guaranteed to return neither undef
   // nor poison if their arguments are not poison/undef.
 
   if (auto *C = dyn_cast<Constant>(V)) {
     // TODO: We can analyze ConstExpr by opcode to determine if there is any
     //       possibility of poison.
     if (isa<UndefValue>(C) || isa<ConstantExpr>(C))
       return false;
 
-    // TODO: Add ConstantFP.
-    if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) ||
-        isa<ConstantPointerNull>(C))
+    if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(V) ||
+        isa<ConstantPointerNull>(C) || isa<Function>(C))
       return true;
 
     if (C->getType()->isVectorTy())
       return !C->containsUndefElement() && !C->containsConstantExpression();
 
     // TODO: Recursively analyze aggregates or other constants.
     return false;
   }
 
-  if (auto PN = dyn_cast<PHINode>(V)) {
-    if (llvm::all_of(PN->incoming_values(), [](const Use &U) {
-          return isa<ConstantInt>(U.get());
-        }))
-      return true;
-  }
+  // Strip cast operations from a pointer value.
+  // Note that stripPointerCastsSameRepresentation can strip off getelementptr
+  // inbounds with zero offset. To guarantee that the result isn't poison, the
+  // stripped pointer is checked as it has to be pointing into an allocated
+  // object or be null `null` to ensure `inbounds` getelement pointers with a
+  // zero offset could not produce poison.
+  // It can strip off addrspacecast that do not change bit representation as
+  // well. We believe that such addrspacecast is equivalent to no-op.
+  auto *StrippedV = V->stripPointerCastsSameRepresentation();
+  if (isa<AllocaInst>(StrippedV) || isa<GlobalVariable>(StrippedV) ||
+      isa<Function>(StrippedV) || isa<ConstantPointerNull>(StrippedV))
 
-  if (auto II = dyn_cast<ICmpInst>(V)) {
-    if (llvm::all_of(II->operands(), [](const Value *V) {
-          return isGuaranteedNotToBeUndefOrPoison(V);
-        }))
+  auto OpCheck = [&](const Value *V) {
+    return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth + 1);
+  };
+
+  if (auto *I = dyn_cast<Instruction>(V)) {
+    switch (I->getOpcode()) {
+    case Instruction::GetElementPtr: {
+      auto *GEPI = dyn_cast<GetElementPtrInst>(I);
+      if (!GEPI->isInBounds() && llvm::all_of(GEPI->operands(), OpCheck))
         return true;
+      break;
+    }
+    case Instruction::FCmp: {
+      auto *FI = dyn_cast<FCmpInst>(I);
+      if (FI->getFastMathFlags().none() &&
+          llvm::all_of(FI->operands(), OpCheck))
+        return true;
+      break;
+    }
+    case Instruction::BitCast:
+    case Instruction::PHI:
+    case Instruction::ICmp:
+      if (llvm::all_of(I->operands(), OpCheck))
+        return true;
+      break;
+    default:
+      break;
     }
 
-  if (auto I = dyn_cast<Instruction>(V)) {
     if (programUndefinedIfPoison(I) && I->getType()->isIntegerTy(1))
       // Note: once we have an agreement that poison is a value-wise concept,
       // we can remove the isIntegerTy(1) constraint.
       return true;
   }
 
   // CxtI may be null or a cloned instruction.
   if (!CtxI || !CtxI->getParent() || !DT)
     return false;

llvm/test/Transforms/InstSimplify/freeze.ll

 
 define i32 @make_const() {
 ; CHECK-LABEL: @make_const(
 ; CHECK-NEXT:    ret i32 10
 ;
   %x = freeze i32 10
   ret i32 %x
 }
 
-; TODO: This is not poison.
-
 define float @make_const2() {
 ; CHECK-LABEL: @make_const2(
-; CHECK-NEXT:    [[X:%.*]] = freeze float 1.000000e+01
-; CHECK-NEXT:    ret float [[X]]
+; CHECK-NEXT:    ret float 1.000000e+01
 ;
   %x = freeze float 10.0
   ret float %x
 }
 
 @glb = constant i32 0
 
 define i32* @make_const_glb() {
 ; CHECK-LABEL: @make_const_glb(
 ; CHECK-NEXT:    ret i32* @glb
 ;
   %k = freeze i32* @glb
   ret i32* %k
 }
 
-; TODO: This is not poison.
-
 define i32()* @make_const_fn() {
 ; CHECK-LABEL: @make_const_fn(
-; CHECK-NEXT:    [[K:%.*]] = freeze i32 ()* @make_const
-; CHECK-NEXT:    ret i32 ()* [[K]]
+; CHECK-NEXT:    ret i32 ()* @make_const
 ;
   %k = freeze i32()* @make_const
   ret i32()* %k
 }
 
 define i32* @make_const_null() {
 ; CHECK-LABEL: @make_const_null(
 ; CHECK-NEXT:    ret i32* null

 ;
   %r = freeze <2 x i31> <i31 34, i31 ptrtoint (i16* @g to i31)>
   ret <2 x i31> %r
 }
 
 define void @alloca() {
 ; CHECK-LABEL: @alloca(
 ; CHECK-NEXT:    [[P:%.*]] = alloca i8
-; CHECK-NEXT:    [[Y:%.*]] = freeze i8* [[P]]
-; CHECK-NEXT:    call void @f3(i8* [[Y]])
+; CHECK-NEXT:    call void @f3(i8* [[P]])
 ; CHECK-NEXT:    ret void
 ;
   %p = alloca i8
   %y = freeze i8* %p
   call void @f3(i8* %y)
   ret void
 }
 
 define i8* @gep() {
 ; CHECK-LABEL: @gep(
 ; CHECK-NEXT:    [[P:%.*]] = alloca [4 x i8]
 ; CHECK-NEXT:    [[Q:%.*]] = getelementptr [4 x i8], [4 x i8]* [[P]], i32 0, i32 6
-; CHECK-NEXT:    [[Q2:%.*]] = freeze i8* [[Q]]
-; CHECK-NEXT:    ret i8* [[Q2]]
+; CHECK-NEXT:    ret i8* [[Q]]
 ;
   %p = alloca [4 x i8]
   %q = getelementptr [4 x i8], [4 x i8]* %p, i32 0, i32 6
   %q2 = freeze i8* %q
   ret i8* %q2
 }
 
 define i8* @gep_noopt(i32 %arg) {
 ; CHECK-LABEL: @gep_noopt(
 ; CHECK-NEXT:    [[Q:%.*]] = getelementptr [4 x i8], [4 x i8]* null, i32 0, i32 [[ARG:%.*]]
 ; CHECK-NEXT:    [[Q2:%.*]] = freeze i8* [[Q]]
 ; CHECK-NEXT:    ret i8* [[Q2]]
 ;
   %q = getelementptr [4 x i8], [4 x i8]* null, i32 0, i32 %arg
   %q2 = freeze i8* %q
   ret i8* %q2
 }
 
 define i8* @gep_inbounds() {
 ; CHECK-LABEL: @gep_inbounds(
 ; CHECK-NEXT:    [[P:%.*]] = alloca [4 x i8]
 ; CHECK-NEXT:    [[Q:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* [[P]], i32 0, i32 0
-; CHECK-NEXT:    [[Q2:%.*]] = freeze i8* [[Q]]
-; CHECK-NEXT:    ret i8* [[Q2]]
+; CHECK-NEXT:    ret i8* [[Q]]
 ;
   %p = alloca [4 x i8]
   %q = getelementptr inbounds [4 x i8], [4 x i8]* %p, i32 0, i32 0
   %q2 = freeze i8* %q
   ret i8* %q2
 }
 
 define i8* @gep_inbounds_noopt(i32 %arg) {
;
   ret i1 %c.fr
 }
 
 define i1 @fcmp(float %x, float %y) {
 ; CHECK-LABEL: @fcmp(
 ; CHECK-NEXT:    [[FX:%.*]] = freeze float [[X:%.*]]
 ; CHECK-NEXT:    [[FY:%.*]] = freeze float [[Y:%.*]]
 ; CHECK-NEXT:    [[C:%.*]] = fcmp oeq float [[FX]], [[FY]]
-; CHECK-NEXT:    [[FC:%.*]] = freeze i1 [[C]]
-; CHECK-NEXT:    ret i1 [[FC]]
+; CHECK-NEXT:    ret i1 [[C]]
 ;
   %fx = freeze float %x
   %fy = freeze float %y
   %c = fcmp oeq float %fx, %fy
   %fc = freeze i1 %c
   ret i1 %fc
 }
 
 define i1 @fcmp_noopt(float %x, float %y) {
 ; CHECK-LABEL: @fcmp_noopt(
 ; CHECK-NEXT:    [[FX:%.*]] = freeze float [[X:%.*]]
 ; CHECK-NEXT:    [[FY:%.*]] = freeze float [[Y:%.*]]
 ; CHECK-NEXT:    [[C:%.*]] = fcmp nnan oeq float [[FX]], [[FY]]
 ; CHECK-NEXT:    [[FC:%.*]] = freeze i1 [[C]]
 ; CHECK-NEXT:    ret i1 [[FC]]
 ;
   %fx = freeze float %x
   %fy = freeze float %y
   %c = fcmp nnan oeq float %fx, %fy
   %fc = freeze i1 %c
   ret i1 %fc
 }
 
 define i1 @brcond(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @brcond(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       A:
 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[A2:%.*]], label [[B]]
 ; CHECK:       A2:
 ; CHECK-NEXT:    ret i1 [[C]]
 ; CHECK:       B:
 ; CHECK-NEXT:    ret i1 [[C]]

 ; CHECK:       BB1:
 ; CHECK-NEXT:    [[A1_FR:%.*]] = freeze i32 [[A1:%.*]]
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[BB2]], label [[EXIT:%.*]]
 ; CHECK:       BB2:
 ; CHECK-NEXT:    [[PHI1:%.*]] = phi i32 [ [[A0_FR]], [[ENTRY:%.*]] ], [ [[A1_FR]], [[BB1]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       EXIT:
 ; CHECK-NEXT:    [[PHI2:%.*]] = phi i32 [ [[A0_FR]], [[BB1]] ], [ [[PHI1]], [[BB2]] ]
-; CHECK-NEXT:    [[PHI2_FR:%.*]] = freeze i32 [[PHI2]]
-; CHECK-NEXT:    ret i32 [[PHI2_FR]]
+; CHECK-NEXT:    ret i32 [[PHI2]]
 ;
 ENTRY:
   %a0.fr = freeze i32 %a0
   br i1 %cond, label %BB1, label %BB2
 BB1:
   %a1.fr = freeze i32 %a1
   br i1 %cond2, label %BB2, label %EXIT
 BB2: