[ValueTracking] Let isGuaranteedNotToBeUndefOrPoison look into more constants and bitcast/alloca/gep

[aqjune]

Summary

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

To deal with bitcast, Depth is added to isGuaranteedNotToBeUndefOrPoison.

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

Checked with Alive2

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 = 6);
 
   /// 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

auto AllUsesGuardedByBranch = [&](const BranchInst *BI) {
     return true;
   };
 
   return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch);
 }
 
 bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                             const Instruction *CtxI,
-                                            const DominatorTree *DT) {
+                                            const DominatorTree *DT,
+                                            unsigned Depth) {
+  if (!Depth)
+    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.
 
   // TODO: Deal with other Constant subclasses.
-  if (isa<ConstantInt>(V) || isa<GlobalVariable>(V))
+  if (isa<ConstantInt>(V) || isa<ConstantFP>(V) || isa<GlobalVariable>(V) ||
+      isa<Function>(V) || isa<ConstantPointerNull>(V))
+    return true;
+
+  // Alloca instruction cannot be undef or poison.
+  if (isa<AllocaInst>(V))
     return true;
 
+  if (auto BI = dyn_cast<BitCastInst>(V))
+    return isGuaranteedNotToBeUndefOrPoison(BI->getOperand(0), CtxI, DT,
+                                            Depth - 1);
+
+  if (auto GEPI = dyn_cast<GetElementPtrInst>(V)) {
+    if (!GEPI->isInBounds()) {
+      if (llvm::all_of(GEPI->operands(), [&](const Value *V) {
+            return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth - 1);
+          }))
+        return true;
+    } else {
+      if (GEPI->hasAllZeroIndices())
+        return isGuaranteedNotToBeUndefOrPoison(GEPI->getPointerOperand(),
+                                                CtxI, DT, Depth - 1);
+    }
+  }
+
   if (auto PN = dyn_cast<PHINode>(V)) {
     if (llvm::all_of(PN->incoming_values(), [](const Use &U) {
           return isa<ConstantInt>(U.get());
         }))
       return true;
   }
 
   if (auto II = dyn_cast<ICmpInst>(V)) {
-    if (llvm::all_of(II->operands(), [](const Value *V) {
-          return isGuaranteedNotToBeUndefOrPoison(V);
+    if (llvm::all_of(II->operands(), [&](const Value *V) {
+          return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth - 1);
         }))
       return true;
   }
 
   if (auto I = dyn_cast<Instruction>(V)) {
     if (programUndefinedIfFullPoison(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.

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
 }
 
+define float @make_const2() {
+; CHECK-LABEL: @make_const2(
+; 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
+}
+
+define i32()* @make_const_fn() {
+; CHECK-LABEL: @make_const_fn(
+; 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
+;
+  %k = freeze i32* null
+  ret i32* %k
+}
+
+define void @alloca() {
+; CHECK-LABEL: @alloca(
+; CHECK-NEXT:    [[P:%.*]] = alloca i8
+; 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 5
+; CHECK-NEXT:    ret i8* [[Q]]
+;
+  %p = alloca [4 x i8]
+  %q = getelementptr [4 x i8], [4 x i8]* %p, i32 0, i32 5
+  %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:    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 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:
;
   br i1 %c, label %A, label %B
 A:
   ret i1 0
 B:
   ret i1 1
 }
 declare void @f1(i1)
 declare void @f2()
+declare void @f3(i8*)