[LVI] Look through extractvalue of insertvalue

[nikic]

Summary

This addresses the issue mentioned on D19867. When we simplify with.overflow instructions in CVP, we leave behind extractvalue of insertvalue sequences that LVI no longer understands. This means that we can not simplify any instructions based on the with.overflow anymore (until some over pass like InstCombine cleans them up).

This patch extends LVI extractvalue handling by calling SimplifyExtractValueInst (which doesn't do anything more than constant folding + looking through insertvalue) and using the block value of the simplification.

A possible alternative would be to do something similar to SimplifyIndVars, where we instead directly try to replace extractvalue users of the with.overflow. This would need some some additional structural changes to CVP, as it's currently not legal to remove anything but the current instruction -- we'd have to introduce a worklist with instructions scheduled for deletion or similar.

[lebedev.ri]

Looks good to me, but you might want to wait for @reames / @spatel a bit.

llvm/lib/Analysis/LazyValueInfo.cpp

 }
 
 bool LazyValueInfoImpl::solveBlockValueExtractValue(
     ValueLatticeElement &BBLV, ExtractValueInst *EVI, BasicBlock *BB) {
   if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
     if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
       return solveBlockValueOverflowIntrinsic(BBLV, WO, BB);
 
+  // Handle extractvalue of insertvalue to allow further simplification
+  // based on replaced with.overflow intrinsics.
+  if (Value *V = SimplifyExtractValueInst(
+          EVI->getAggregateOperand(), EVI->getIndices(),
+          EVI->getModule()->getDataLayout())) {
+    if (!hasBlockValue(V, BB)) {
+      if (pushBlockValue({ BB, V }))
+        return false;
+      BBLV = ValueLatticeElement::getOverdefined();
+      return true;
+    }
+    BBLV = getBlockValue(V, BB);
+    return true;
+  }
+
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - overdefined (unknown extractvalue).\n");
   BBLV = ValueLatticeElement::getOverdefined();
   return true;
 }
 
 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
                                                      bool isTrueDest) {

llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll

 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y_OFFSET]], 19
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[RES1:%.*]] = add nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[ADD:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp slt i32 [[ADD]], 19
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ true, [[CONT1]] ], [ [[CMP3]], [[CONT3]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %x.offset = add i32 %x, 9
   %cmp1 = icmp ult i32 %x.offset, 19
   br i1 %cmp1, label %cont1, label %out
 
 cont1:
   %y.offset = add i32 %y, 9

 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[RES1:%.*]] = add nuw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[ADD:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[ADD]], 19
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ true, [[CONT1]] ], [ [[CMP3]], [[CONT3]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp1 = icmp ult i32 %x, 10
   br i1 %cmp1, label %cont1, label %out
 
 cont1:
   %cmp2 = icmp ult i32 %y, 10
   br i1 %cmp2, label %cont2, label %out

 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[OFFSET:%.*]] = add nuw nsw i32 [[X]], 9
 ; CHECK-NEXT:    [[RES1:%.*]] = sub nsw i32 [[OFFSET]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[SUB]], 19
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ true, [[CONT1]] ], [ [[CMP3]], [[CONT3]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp1 = icmp ult i32 %x, 10
   br i1 %cmp1, label %cont1, label %out
 
 cont1:
   %cmp2 = icmp ult i32 %y, 10
   br i1 %cmp2, label %cont2, label %out

 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[OFFSET:%.*]] = add nuw nsw i32 [[X]], 9
 ; CHECK-NEXT:    [[RES1:%.*]] = sub nuw i32 [[OFFSET]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[SUB]], 19
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ true, [[CONT1]] ], [ [[CMP3]], [[CONT3]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp1 = icmp ult i32 %x, 10
   br i1 %cmp1, label %cont1, label %out
 
 cont1:
   %cmp2 = icmp ult i32 %y, 10
   br i1 %cmp2, label %cont2, label %out

 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y_OFFSET]], 19
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[RES1:%.*]] = mul nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp sle i32 [[MUL]], 81
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp sge i32 [[MUL]], -81
-; CHECK-NEXT:    [[CMP5:%.*]] = and i1 [[CMP3]], [[CMP4]]
+; CHECK-NEXT:    [[CMP5:%.*]] = and i1 true, true
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ true, [[CONT1]] ], [ [[CMP5]], [[CONT3]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %x.offset = add i32 %x, 9
   %cmp1 = icmp ult i32 %x.offset, 19
   br i1 %cmp1, label %cont1, label %out
 
 cont1:
   %y.offset = add i32 %y, 9

 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 100
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[RES1:%.*]] = mul nuw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ule i32 [[MUL]], 9801
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ true, [[CONT1]] ], [ [[CMP3]], [[CONT3]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp1 = icmp ult i32 %x, 100
   br i1 %cmp1, label %cont1, label %out
 
 cont1:
   %cmp2 = icmp ult i32 %y, 100
   br i1 %cmp2, label %cont2, label %out