[ValueTracking] Handle conflicts when computing knownbits of PHI nodes in deadcode; PR65022

[goldstein.w.n]

Summary

Bug was introduced in: https://reviews.llvm.org/D157807

The prior logic assumed that the information from the knownbits
returned from analyzing the icmp and its operands in the context
basicblock would be consistent.

This is not necessarily the case if we are analyzing deadcode.

For example with (icmp sgt (select cond, 0, 1), -1). If we take
knownbits for the select using knownbits from the operator, we will
know the signbit is zero. If we are analyzing a not-taken from based
on the icmp (deadcode), we will also "know" that the select must
be negative (signbit is one). This will result in a conflict in
knownbits.

The fix is to just give up on analying the phi-node if its deadcode. We 1) don't want to waste time continuing to analyze it and 2) will be removing it (and its dependencies) later.

[nikic]

llvm/test/Analysis/ValueTracking/knownbits-phi-deadcode.ll

2

Please reduce this to a single pass invocation.

[goldstein.w.n]

Only relies on loop-delete now

[goldstein.w.n]

llvm/test/Analysis/ValueTracking/knownbits-phi-deadcode.ll

2

Done, by chance do you know if there is a way to get llvm-reduce to do this for you?

I ended up going through the -O1 passes manually until I could isolate to a single pass (and get necessary transforms from pre-existing passes) but have to feel there is a better way.

Also tried --print-after-all but that often doesn't give complete IR. Just curious if there is some "good" way to do this or is it just figure it out with pass pipeline + ir dumps?

[goldstein.w.n]

llvm/test/Analysis/ValueTracking/knownbits-phi-deadcode.ll

2

Actually I guess in retrospect what I would do is get pass thats failing (easy enough). Run pipeline up to that pass and dump IR. Then just run that single pass. Shouldn't be as complicated as I made it.

[nikic]

llvm/test/Analysis/ValueTracking/knownbits-phi-deadcode.ll

2

You can use -print-on-crash -print-module-scope. There is also utils/reduce_pipeline.py for cases where that's not feasible.

Also, this test still doesn't look very minimal, can you please run it through llvm-reduce?

[goldstein.w.n]

Re-reduce test

[goldstein.w.n]

ping. Think this is pretty trivial change and fixes active bug so would like to get it in.

[nikic]

LGTM

llvm/test/Analysis/ValueTracking/knownbits-phi-deadcode.ll

58

Is the uselistorder actually needed?

llvm/lib/Analysis/ValueTracking.cpp

if (Depth < MaxAnalysisRecursionDepth - 1 && Known.isUnknown()) {
                          m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc)))) {
             // Check for cases of duplicate successors.
             if ((TrueSucc == P->getParent()) != (FalseSucc == P->getParent())) {
               // If we're using the false successor, invert the predicate.
               if (FalseSucc == P->getParent())
                 Pred = CmpInst::getInversePredicate(Pred);
               // Get the knownbits implied by the incoming phi condition.
               auto CR = ConstantRange::makeExactICmpRegion(Pred, *RHSC);
-              Known2 = Known2.unionWith(CR.toKnownBits());
+              KnownBits KnownUnion = Known2.unionWith(CR.toKnownBits());
+              // We can have conflicts here if we are analyzing deadcode (its
+              // impossible for us reach this BB based the icmp).
+              if (KnownUnion.hasConflict()) {
+                // No reason to continue analyzing in a known dead region, so
+                // just resetAll and break. This will cause us to also exit the
+                // outer loop.
+                Known.resetAll();
+                break;
+              }
+              Known2 = KnownUnion;
             }
           }
         }
 
         Known = Known.intersectWith(Known2);
         // If all bits have been ruled out, there's no need to check
         // more operands.
         if (Known.isUnknown())

llvm/test/Analysis/ValueTracking/knownbits-phi-deadcode.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -O1 -S < %s | FileCheck %s
+; This reduced testcase from pr65022. We are only testing that is doesn't crash.
+
+@b = internal global i32 1
+
+define void @f(i32 %spec.select, ptr %c, i1 %tobool.not) {
+; CHECK-LABEL: define void @f
+; CHECK-SAME: (i32 [[SPEC_SELECT:%.*]], ptr nocapture writeonly [[C:%.*]], i1 [[TOBOOL_NOT:%.*]]) local_unnamed_addr {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL2_NOT:%.*]] = icmp eq i32 [[SPEC_SELECT]], 0
+; CHECK-NEXT:    br label [[L:%.*]]
+; CHECK:       L:
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN1:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    store i32 0, ptr [[C]], align 4
+; CHECK-NEXT:    br label [[IF_THEN1]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    br i1 [[TOBOOL2_NOT]], label [[FOR_END:%.*]], label [[IF_THEN3:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    tail call void (...) @e()
+; CHECK-NEXT:    br label [[L]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %L
+
+L:  ; preds = %while.cond, %if.then3, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %i.0, %if.then3 ], [ 1, %while.cond ]
+  br i1 %tobool.not, label %if.end, label %if.then
+
+if.then:  ; preds = %L
+  store i32 0, ptr %c, align 4
+  br label %if.end
+
+if.end:  ; preds = %if.then, %L
+  %0 = load i32, ptr @b, align 4
+  %not = xor i32 %0, 1
+  %cmp = icmp sgt i32 %0, -1
+  br i1 %cmp, label %if.then1, label %while.cond
+
+if.then1:  ; preds = %if.end
+  %tobool2.not = icmp eq i32 %spec.select, 0
+  br i1 %tobool2.not, label %while.cond, label %if.then3
+
+if.then3:  ; preds = %if.then1
+  call void(...) @e()
+  br label %L
+
+while.cond:  ; preds = %if.then1, %if.end
+  %h.02 = phi i32 [ 0, %if.then1 ], [ %not, %if.end ]
+  %tobool7.not = icmp eq i32 %h.02, 0
+  %spec.select3 = select i1 %tobool7.not, i32 %i.0, i32 %spec.select
+  %tobool10.not = icmp eq i32 %spec.select3, 0
+  br i1 %tobool10.not, label %for.cond, label %L
+
+for.cond:  ; preds = %for.inc, %while.cond
+  %1 = phi i32 [ %inc, %for.inc ], [ %spec.select, %while.cond ]
+  %tobool13.not = icmp eq i32 %1, 0
+  br i1 %tobool13.not, label %for.end, label %for.inc
+
+for.inc:  ; preds = %for.cond
+  %inc = add i32 %1, 1
+  store i32 %inc, ptr @b, align 4
+  br label %for.cond
+
+for.end:  ; preds = %for.cond
+  ret void
+}
+
+declare void @e(...)