[ValueTracking] Let isGuaranteedNotToBeUndefOrPoison consider noundef

[aqjune]

Summary

This patch adds support for noundef arguments.

[aqjune]

Has little impact on compilation time on average:

(unit:sec.)
+-----------------------------------------------+---------+---------+----------+-------+---------+----------+
|                                               | compile |         |          | link  |         |          |
+-----------------------------------------------+---------+---------+----------+-------+---------+----------+
|                                               | base    | noundef | slowdown | base  | noundef | slowdown |
| CTMark/7zip/7zip-benchmark.test               | 89.55   | 89.45   | -0.11%   | 46.86 | 46.87   | 0.04%    |
| CTMark/Bullet/bullet.test                     | 63.06   | 62.84   | -0.35%   | 9.97  | 9.69    | -2.73%   |
| CTMark/ClamAV/clamscan.test                   | 26.89   | 26.88   | -0.05%   | 24.91 | 25.01   | 0.40%    |
| CTMark/SPASS/SPASS.test                       | 26.17   | 26.08   | -0.36%   | 19.68 | 19.70   | 0.10%    |
| CTMark/consumer-typeset/consumer-typeset.test | 19.69   | 19.63   | -0.28%   | 18.44 | 18.56   | 0.63%    |
| CTMark/kimwitu++/kc.test                      | 26.48   | 26.50   | 0.06%    | 14.59 | 14.34   | -1.76%   |
| CTMark/lencod/lencod.test                     | 34.46   | 34.42   | -0.13%   | 38.37 | 38.63   | 0.67%    |
| CTMark/mafft/pairlocalalign.test              | 16.20   | 16.17   | -0.18%   | 8.65  | 8.64    | -0.11%   |
| CTMark/sqlite3/sqlite3.test                   | 24.59   | 24.51   | -0.33%   | 24.52 | 24.52   | -0.02%   |
| CTMark/tramp3d-v4/tramp3d-v4.test             | 49.26   | 49.16   | -0.21%   | 35.74 | 35.71   | -0.09%   |
+-----------------------------------------------+---------+---------+----------+-------+---------+----------+

[nikic]

llvm/include/llvm/Analysis/ValueTracking.h

610

Why do we need this parameter? Padding only matters for the stored representation of a struct. For SSA struct values, the padding cannot be accessed.

llvm/lib/Analysis/ValueTracking.cpp

4792

Why are some of these checked outside the dyn_cast<Operator>(V) below?

[aqjune]

Move relevant code snippets into if branch on dyn_cast<Operator>

[aqjune]

After this patch is accepted, I'll make a separate commit for tests so only diffs are updated.

llvm/include/llvm/Analysis/ValueTracking.h

610

It is because freeze can take an aggregate value.
I found that its behavior w.r.t aggregate values is not specified in LangRef, but I think it is good to make it freeze the paddings too because it guarantees that v = freeze(load p); store v, q will never have undef bits or poison in memory.
If this sounds good, I'll make a patch for this.

[jdoerfert]

This patch adds support for noundef arguments and looking through more operations.

Maybe make it multiple patches then?

[nikic]

llvm/include/llvm/Analysis/ValueTracking.h

610

I don't think something like this can work under current IR semantics. Even if we take a simpler example like %v = freeze(load i1 %p); store %v, %q, the freeze will only freeze the i1 value, it does not do anything to the remaining 7 bits that are present in the store representation. It does make sure that a subsequent load i1 will not see undef/poison, but not that a load i8 won't. For the aggregate case, similarly, it does make sure that loading the same aggregate type will not have undef/poison (because padding does not matter for the SSA value), but does not make sure that loading an appropriately sized iN at the same location will not have undef/poison.

[aqjune]

Will split this patch into (1) noundef patch (2) use operator patch

llvm/include/llvm/Analysis/ValueTracking.h

610

Okay, that makes sense. There is no way to remove the 7-bit undef value when storing i1 value.

[aqjune]

Leave noundef patch only

[nikic]

LG

llvm/lib/Analysis/ValueTracking.cpp

4763

This comment seems a bit out of context now that the IgnorePadding flag is gone.

llvm/include/llvm/Analysis/ValueTracking.h

 //===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
class Value;
   bool canCreatePoison(const Instruction *I);
 
   /// 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.
+  /// If IgnorePadding is true, V's paddings are not inspected. If false,
+  /// the paddings should be frozen as well.
   bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                         const Instruction *CtxI = nullptr,
                                         const DominatorTree *DT = nullptr,
+                                        bool IgnorePadding = false,
                                         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

llvm/lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
default:
     // Be conservative and return true.
     return true;
   }
 }
 
 bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                             const Instruction *CtxI,
                                             const DominatorTree *DT,
+                                            bool IgnorePadding,
                                             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 *A = dyn_cast<Argument>(V)) {
+    // NoUndef does not guarantee that paddings are not undef.
+    if (A->hasAttribute(Attribute::NoUndef) &&
+        (IgnorePadding || !A->getType()->isAggregateType()))
+      return true;
+  }
 
   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))
+    if (isa<UndefValue>(C))
       return false;
 
     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;
   }
 
   // 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))
     return true;
 
   auto OpCheck = [&](const Value *V) {
-    return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth + 1);
+    return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, IgnorePadding,
+                                            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;
-    }
+  if (auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(V)) {
+    if (!OverflowOp->hasNoSignedWrap() && !OverflowOp->hasNoUnsignedWrap() &&
+        OpCheck(OverflowOp->getOperand(0)) &&
+        OpCheck(OverflowOp->getOperand(1)))
+
+  if (auto *GEPOp = dyn_cast<GEPOperator>(V)) {
+    if (!GEPOp->isInBounds() && llvm::all_of(GEPOp->operands(), OpCheck))
+      return true;
+  }
+
+  if (auto *Opr = dyn_cast<Operator>(V)) {
+    switch (Opr->getOpcode()) {
+    case Instruction::FNeg:
+    case Instruction::FAdd:
+    case Instruction::FSub:
+    case Instruction::FMul:
+    case Instruction::FDiv:
+    case Instruction::FRem:
     case Instruction::FCmp: {
-      auto *FI = dyn_cast<FCmpInst>(I);
-      if (FI->getFastMathFlags().none() &&
-          llvm::all_of(FI->operands(), OpCheck))
+      auto *FPOp = dyn_cast<FPMathOperator>(Opr);
+      if (FPOp->getFastMathFlags().none() &&
+          llvm::all_of(FPOp->operands(), OpCheck))
         return true;
       break;
     }
+    case Instruction::ExtractValue:
+      if (isGuaranteedNotToBeUndefOrPoison(Opr->getOperand(0), CtxI, DT, true,
+                                           Depth + 1))
+        return true;
+      break;
+    case Instruction::And:
+    case Instruction::Or:
+    case Instruction::Xor:
     case Instruction::BitCast:
     case Instruction::PHI:
     case Instruction::ICmp:
-      if (llvm::all_of(I->operands(), OpCheck))
+      if (llvm::all_of(Opr->operands(), OpCheck))
         return true;
       break;
     default:
       break;
     }
+  }
 
+  // Conservatively return false
+  if (isa<ConstantExpr>(V))
+    return false;
+
+  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)

llvm/test/Transforms/InstSimplify/freeze-noundef.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+define i8 @noundef(i8 noundef %x) {
+; CHECK-LABEL: @noundef(
+; CHECK-NEXT:    ret i8 [[X:%.*]]
+;
+  %y = freeze i8 %x
+  ret i8 %y
+}
+
+define i1 @or(i1 noundef %x, i1 noundef %x2) {
+; CHECK-LABEL: @or(
+; CHECK-NEXT:    [[Y:%.*]] = or i1 [[X:%.*]], [[X2:%.*]]
+; CHECK-NEXT:    ret i1 [[Y]]
+;
+  %y = or i1 %x, %x2
+  %z = freeze i1 %y
+  ret i1 %z
+}
+
+define i1 @or2(i1 noundef %x, i1 %x2) {
+; CHECK-LABEL: @or2(
+; CHECK-NEXT:    [[Y:%.*]] = or i1 [[X:%.*]], [[X2:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = freeze i1 [[Y]]
+; CHECK-NEXT:    ret i1 [[Z]]
+;
+  %y = or i1 %x, %x2
+  %z = freeze i1 %y
+  ret i1 %z
+}
+
+define i8 @add(i8 noundef %x) {
+; CHECK-LABEL: @add(
+; CHECK-NEXT:    [[Y:%.*]] = add i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i8 [[Y]]
+;
+  %y = add i8 %x, 1
+  %z = freeze i8 %y
+  ret i8 %z
+}
+
+define i8 @addnsw(i8 noundef %x) {
+; CHECK-LABEL: @addnsw(
+; CHECK-NEXT:    [[Y:%.*]] = add nsw i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[Z:%.*]] = freeze i8 [[Y]]
+; CHECK-NEXT:    ret i8 [[Z]]
+;
+  %y = add nsw i8 %x, 1
+  %z = freeze i8 %y
+  ret i8 %z
+}
+
+define {i8, i32} @aggr({i8, i32} noundef %x) {
+; CHECK-LABEL: @aggr(
+; CHECK-NEXT:    [[Y:%.*]] = freeze { i8, i32 } [[X:%.*]]
+; CHECK-NEXT:    ret { i8, i32 } [[Y]]
+;
+  %y = freeze {i8, i32} %x
+  ret {i8, i32} %y
+}
+
+define i32 @extract({i8, i32} noundef %x) {
+; CHECK-LABEL: @extract(
+; CHECK-NEXT:    [[Y:%.*]] = extractvalue { i8, i32 } [[X:%.*]], 1
+; CHECK-NEXT:    ret i32 [[Y]]
+;
+  %y = extractvalue {i8, i32} %x, 1
+  %z = freeze i32 %y
+  ret i32 %z
+}
+
+define i32 @extract2({i8, {i8, i32}} noundef %x) {
+; CHECK-LABEL: @extract2(
+; CHECK-NEXT:    [[Y:%.*]] = extractvalue { i8, { i8, i32 } } [[X:%.*]], 1
+; CHECK-NEXT:    [[Z:%.*]] = extractvalue { i8, i32 } [[Y]], 1
+; CHECK-NEXT:    ret i32 [[Z]]
+;
+  %y = extractvalue {i8, {i8, i32}} %x, 1
+  %z = extractvalue {i8, i32} %y, 1
+  %w = freeze i32 %z
+  ret i32 %w
+}

llvm/test/Transforms/InstSimplify/freeze.ll

 ; CHECK-LABEL: @constant_expr(
 ; CHECK-NEXT:    [[R:%.*]] = freeze float bitcast (i32 ptrtoint (i16* @g to i32) to float)
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %r = freeze float bitcast (i32 ptrtoint (i16* @g to i32) to float)
   ret float %r
 }
 
+define i8* @constant_expr2() {
+; CHECK-LABEL: @constant_expr2(
+; CHECK-NEXT:    ret i8* bitcast (i16* @g to i8*)
+;
+  %r = freeze i8* bitcast (i16* @g to i8*)
+  ret i8* %r
+}
+
 ; Negative test
 
 define <2 x i31> @vector_element_constant_expr() {
 ; CHECK-LABEL: @vector_element_constant_expr(
 ; CHECK-NEXT:    [[R:%.*]] = freeze <2 x i31> <i31 34, i31 ptrtoint (i16* @g to i31)>
 ; CHECK-NEXT:    ret <2 x i31> [[R]]
 ;
   %r = freeze <2 x i31> <i31 34, i31 ptrtoint (i16* @g to i31)>