[CVP] Use LVI to constant fold deopt operands

[reames]

Summary

Deopt operands are generally intended to record information about a site in code with minimal perturbation of the surrounding code. Idiomatically, they also tend to appear down rare paths. Putting these together, we have an obvious case for extending CVP w/deopt operand constant folding. Arguably, we should be doing this for all operands on all instructions, but that's definitely a much larger and risky change.

A few items to note for the review:

• The const_cast is definitely ugly, but the API for operand bundles seemed to require it. Is there a better way to structure this?
• As noted w/a TODO, I initially tried to use a context instruction here, but discovered that the result returned by LVI was actually wrong. It seemed return something true *after* the context instruction, not before it. For an instruction like a guard or assume, that difference is quite material!

[reames]

ping

[anna]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

471

Nit: reasonably.

485

From the code, getConstant calls getValueInBlock which returns the value at the end of the BasicBlock. The BB passed in here is the callsite's parent. We want the value which is true at the beginning of the CS.getParent() right?

[reames]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

485

Eek, good catch. Will have to readjust how I approach this.

[reames]

Switch batch to using the context instruction, and fix the bug it exposed. As far as I can tell, the bug was invisible for all existing code since the context instruction had to be the guard itself.

[anna]

LGTM!

lib/Analysis/LazyValueInfo.cpp

void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
   }
 
   // If guards are not used in the module, don't spend time looking for them
   auto *GuardDecl = BBI->getModule()->getFunction(
           Intrinsic::getName(Intrinsic::experimental_guard));
   if (!GuardDecl || GuardDecl->use_empty())
     return;
 
-  for (Instruction &I : make_range(BBI->getIterator().getReverse(),
+  if (BBI->getIterator() == BBI->getParent()->begin())
+    return;
+  for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
                                    BBI->getParent()->rend())) {
     Value *Cond = nullptr;
     if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
   }
 }
 
 bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
 
   if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
     if (willNotOverflow(II, LVI)) {
       processOverflowIntrinsic(II);
       return true;
     }
   }
 
+  // Deopt bundle operands are intended to capture state with minimal
+  // perturbance of the code otherwise.  If we can find a constant value for
+  // any such operand and remove a use of the original value, that's
+  // desireable since it may allow further optimization of that value (e.g. via
+  // single use rules in instcombine).  Since deopt uses tend to,
+  // idiomatically, appear along rare conditional paths, it's reasonable likely
+  // we may have a conditional fact with which LVI can fold.   
+  if (auto DeoptBundle = CS.getOperandBundle(LLVMContext::OB_deopt)) {
+    bool Progress = false;
+    for (const Use &ConstU : DeoptBundle->Inputs) {
+      Use &U = const_cast<Use&>(ConstU);
+      Value *V = U.get();
+      if (V->getType()->isVectorTy()) continue;
+      if (isa<Constant>(V)) continue;
+
+      Constant *C = LVI->getConstant(V, CS.getParent(), CS.getInstruction());
+      if (!C) continue;
+      U.set(C);
+      Progress = true;
+    }
+    if (Progress)
+      return true;
+  }
+
   for (Value *V : CS.args()) {
     PointerType *Type = dyn_cast<PointerType>(V->getType());
     // Try to mark pointer typed parameters as non-null.  We skip the
     // relatively expensive analysis for constants which are obviously either
     // null or non-null to start with.
     if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) &&
         !isa<Constant>(V) &&
         LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,

test/Transforms/CorrelatedValuePropagation/deopt.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -correlated-propagation -S < %s | FileCheck %s
 
 declare void @use()
 ; test requires a mix of context sensative refinement, and analysis
 ; of the originating IR pattern.  Neither part is enough in isolation.
 define void @test1(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 -1, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 [[SEL]], i64 0
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[SEL2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
-; CHECK-NEXT:    call void @use() [ "deopt"(i64 [[SEL2]]) ]
+; CHECK-NEXT:    call void @use() [ "deopt"(i64 1) ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       untaken:
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 -1, i64 1
   %sel2 = select i1 %c2, i64 %sel, i64 0
   %cmp = icmp sgt i64 %sel2, 0
   br i1 %cmp, label %taken, label %untaken

 
 ; Same as test1, but with assume not branch
 define void @test1_assume(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test1_assume(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 -1, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 [[SEL]], i64 0
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[SEL2]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    call void @use() [ "deopt"(i64 [[SEL2]]) ]
+; CHECK-NEXT:    call void @use() [ "deopt"(i64 1) ]
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 -1, i64 1
   %sel2 = select i1 %c2, i64 %sel, i64 0
   %cmp = icmp sgt i64 %sel2, 0
   call void @llvm.assume(i1 %cmp)
   call void @use() ["deopt" (i64 %sel2)]
   ret void
 }
 
 ; Same as test1, but with guard not branch
 define void @test1_guard(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test1_guard(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 -1, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 [[SEL]], i64 0
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[SEL2]], 0
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[CMP]]) [ "deopt"(i64 [[SEL2]]) ]
-; CHECK-NEXT:    call void @use() [ "deopt"(i64 [[SEL2]]) ]
+; CHECK-NEXT:    call void @use() [ "deopt"(i64 1) ]
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 -1, i64 1
   %sel2 = select i1 %c2, i64 %sel, i64 0
   %cmp = icmp sgt i64 %sel2, 0
   call void (i1, ...) @llvm.experimental.guard(i1 %cmp) ["deopt" (i64 %sel2)]
   call void @use() ["deopt" (i64 %sel2)]
   ret void
 }
 
 ;; The rest of these are slight variations on the patterns
 ;; producing 1 of several adjacent constants to test generality
 
 define void @test2(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 [[SEL]], i64 -1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[SEL2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
-; CHECK-NEXT:    call void @use() [ "deopt"(i64 [[SEL2]]) ]
+; CHECK-NEXT:    call void @use() [ "deopt"(i64 1) ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       untaken:
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 0, i64 1
   %sel2 = select i1 %c2, i64 %sel, i64 -1
   %cmp = icmp sgt i64 %sel2, 0
   br i1 %cmp, label %taken, label %untaken
 taken:
   call void @use() ["deopt" (i64 %sel2)]
   ret void
 untaken:
   ret void
 }
 define void @test3(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 [[SEL]], i64 2
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[SEL2]], 1
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
-; CHECK-NEXT:    call void @use() [ "deopt"(i64 [[SEL2]]) ]
+; CHECK-NEXT:    call void @use() [ "deopt"(i64 2) ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       untaken:
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 0, i64 1
   %sel2 = select i1 %c2, i64 %sel, i64 2
   %cmp = icmp sgt i64 %sel2, 1
   br i1 %cmp, label %taken, label %untaken
 taken:
   call void @use() ["deopt" (i64 %sel2)]
   ret void
 untaken:
   ret void
 }
 
 define void @test4(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[ADD1:%.*]] = add i64 0, [[SEL]]
 ; CHECK-NEXT:    [[ADD2:%.*]] = add i64 [[ADD1]], [[SEL2]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[ADD2]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[ADD2]], 1
 ; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
-; CHECK-NEXT:    call void @use() [ "deopt"(i64 [[ADD2]]) ]
+; CHECK-NEXT:    call void @use() [ "deopt"(i64 2) ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       untaken:
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 0, i64 1
   %sel2 = select i1 %c2, i64 0, i64 1
   %add1 = add i64 0, %sel
   %add2 = add i64 %add1, %sel2
-  %cmp = icmp sgt i64 %add2, 0
+  %cmp = icmp sgt i64 %add2, 1
   br i1 %cmp, label %taken, label %untaken
 taken:
   call void @use() ["deopt" (i64 %add2)]
   ret void
 untaken:
   ret void
 }