[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 ↗

(On Diff #277698)

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

4813

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 ↗

(On Diff #277698)

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 ↗

(On Diff #277698)

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 ↗

(On Diff #277698)

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

4770

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

llvm/lib/Analysis/ValueTracking.cpp

bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
 
   // 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))
+      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))
       return false;
 
     if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(V) ||
         isa<ConstantPointerNull>(C) || isa<Function>(C))
bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *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;

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:    [[Y:%.*]] = freeze i8 [[X:%.*]]
-; CHECK-NEXT:    ret i8 [[Y]]
+; CHECK-NEXT:    ret i8 [[X:%.*]]
 ;
   %y = freeze i8 %x
   ret i8 %y
 }
 
 define i1 @icmp(i8 noundef %x, i8 noundef %y) {
 ; CHECK-LABEL: @icmp(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[F:%.*]] = freeze i1 [[C]]
-; CHECK-NEXT:    ret i1 [[F]]
+; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = icmp eq i8 %x, %y
   %f = freeze i1 %c
   ret i1 %f
 }
 
+; TODO: should look into binary operations
 define i1 @or(i1 noundef %x, i1 noundef %x2) {
 ; CHECK-LABEL: @or(
 ; 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 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
 }
 
+; TODO: should look into binary operations
 define i8 @add(i8 noundef %x) {
 ; CHECK-LABEL: @add(
 ; CHECK-NEXT:    [[Y:%.*]] = add i8 [[X:%.*]], 1
 ; CHECK-NEXT:    [[Z:%.*]] = freeze i8 [[Y]]
 ; CHECK-NEXT:    ret i8 [[Z]]
 ;
   %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]]
+; CHECK-NEXT:    ret { i8, i32 } [[X:%.*]]
 ;
   %y = freeze {i8, i32} %x
   ret {i8, i32} %y
 }
 
+; TODO: should look into extract operations
 define i32 @extract({i8, i32} noundef %x) {
 ; CHECK-LABEL: @extract(
 ; CHECK-NEXT:    [[Y:%.*]] = extractvalue { i8, i32 } [[X:%.*]], 1
 ; CHECK-NEXT:    [[Z:%.*]] = freeze i32 [[Y]]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %y = extractvalue {i8, i32} %x, 1
   %z = freeze i32 %y
   ret i32 %z
 }
 
+; TODO: should look into extract operations
 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:    [[W:%.*]] = freeze i32 [[Z]]
 ; CHECK-NEXT:    ret i32 [[W]]
 ;
   %y = extractvalue {i8, {i8, i32}} %x, 1
   %z = extractvalue {i8, i32} %y, 1
   %w = freeze i32 %z
   ret i32 %w
 }