[ValueTracking] do not overwrite analysis results already computed

[jingyue]

Summary

ValueTracking used to overwrite the analysis results computed from
assumes and dominating conditions. This patch fixes this issue.

[majnemer]

This change is quite large even if it is mostly mechanical. I don't understand how your change is connected to @llvm.assume.

[jingyue]

How about this patch? It is equivalent to the old patch but requires much less
source code modification.

The old patch writes the known bits computed from arithmetics (the big switch
starting from around L1080) to KnownZero1/2 and KnownOne1/2 locally, and updates
KnownZero and KnownOne afterwards.

The new patch saves KnownOne and KnownZero before the switch, and later merges
the saved results with the known bits computed from arithmetics.

I am fine with either approach. I slightly prefer the first one because
KnownOne and KnownZero consistently holds everything ValueTracking knows so
far. But the second approach requires less source code change.

[majnemer]

In D10283#186475, @jingyue wrote:

How about this patch? It is equivalent to the old patch but requires much less
source code modification.

The old patch writes the known bits computed from arithmetics (the big switch
starting from around L1080) to KnownZero1/2 and KnownOne1/2 locally, and updates
KnownZero and KnownOne afterwards.

The new patch saves KnownOne and KnownZero before the switch, and later merges
the saved results with the known bits computed from arithmetics.

I am fine with either approach. I slightly prefer the first one because
KnownOne and KnownZero consistently holds everything ValueTracking knows so
far. But the second approach requires less source code change.

OK, so the issue is that computeKnownBitsFromAssume and computeKnownBitsFromDominatingCondition compute a result which is clobbered by the subsequent calls to computeKnownBits on the value operands?

It seems to me that computeKnownBitsFromAssume and computeKnownBitsFromDominatingCondition strictly refines their input. Could we just call them on line 1530?

[jingyue]

computeKnonwBitsFromAssume only refines their inputs, but computeKnownBitsFromDominatingCondition calls computeKnownBitsFromTrueCondition which may clobber the inputs at http://llvm.org/docs/doxygen/html/ValueTracking_8cpp_source.html#l00555. That is the only place I found that may clobber KnownZero/KnownOne in these two functions, so if I remove the clobbering in computeKnownBitsFromTrueCondition, I agree I can call them at Line 1530.

However, it sounds weird that computeKnownBits may clobber inputs but some (if not all) computeKnownBitsXXX functions don't. Ideally, none of them should clobber inputs, right?

[jingyue]

change the order of computeKnownBitsFrom* calls

1. extract the code that computes known bits from an operator into

computeKnownBitsFromOperator.

2. call computeKnownBitsFromAssume and

computeKnownBitsFromDominatingConditions after
computeKnownBitsFromOperator so that computeKnownBitsFromOperator
doesn't clobber the results computed by the other two.

3. add dom-cond.ll to verify computeKnownBitsFromOperator does not

clobber the results computed by computeKnownBitsFromDominatingConditions.

[jingyue]

misdeleted some lines in the previous patch

[majnemer]

LGTM, thanks!

lib/Analysis/ValueTracking.cpp

void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
   }
 
   // Check whether a nearby assume intrinsic can determine some known bits.
   computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
 
   // Check whether there's a dominating condition which implies something about
   // this value at the given context.
   if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
+    // FIXME: this call may overwrite the known bits computed from assumes.
     computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL, Depth,
                                             Q);
 
   Operator *I = dyn_cast<Operator>(V);
   if (!I) return;
 
+  // Save KnownZero and KnownOne so that they won't be overwritten by the
+  // following computeKnownBits calls.
+  APInt SavedKnownZero(KnownZero), SavedKnownOne(KnownOne);
   APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
   switch (I->getOpcode()) {
   default: break;
   case Instruction::Load:
     if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range))
       computeKnownBitsFromRangeMetadata(*MD, KnownZero);
     break;
   case Instruction::And: {
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
           computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false,
                               KnownZero, KnownOne, KnownZero2, KnownOne2, DL,
                               Depth, Q);
           break;
         }
       }
     }
   }
+  KnownZero |= SavedKnownZero;
+  KnownOne |= SavedKnownOne;
 
   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 }
 
 /// Determine whether the sign bit is known to be zero or one.
 /// Convenience wrapper around computeKnownBits.
 void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
                     const DataLayout &DL, unsigned Depth, const Query &Q) {

test/Analysis/ValueTracking/assume.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define i32 @assume_add(i32 %a, i32 %b) {
+; CHECK-LABEL: @assume_add(
+  %1 = add i32 %a, %b
+  %last_two_digits = and i32 %1, 3
+  %2 = icmp eq i32 %last_two_digits, 0
+  call void @llvm.assume(i1 %2)
+  %3 = add i32 %1, 3
+; CHECK: %3 = or i32 %1, 3
+  ret i32 %3
+}
+
+declare void @llvm.assume(i1)