[SCCP] Use SimplifyBinOp for non-integer constant/expressions & overdef.

[fhahn]

Summary

For non-integer constants/expressions and overdefined, I think we can
just use SimplifyBinOp to do common folds. By just passing a context
with the DL, SimplifyBinOp should not try to get additional information
from looking at definitions.

For overdefined values, it should be enough to just pass the original
operand.

Note: The comment before the if (isconstant(V1State)... was wrong
originally: isConstant() also matches integer ranges with a single
element. It is correct now.

This patch depends on a few ConstantRange improvements for all tests to
pass.

[fhahn]

Simplified the code a bit, by first trying simplifying to constant if either operand is a constant, followed by simplifying to a constant range as next step.

[efriedma]

By just passing a context with the DL, SimplifyBinOp should not try to get additional information from looking at definitions.

What context is legal to use here?

llvm/lib/Transforms/Scalar/SCCP.cpp

970

Sort of orthogonal, but the thought occurred to me: should we be trying to use the "undef" lattice state here?

[fhahn]

In D76459#1939662, @efriedma wrote:

By just passing a context with the DL, SimplifyBinOp should not try to get additional information from looking at definitions.

What context is legal to use here?

I think SimplifyBinOp is not allowed to look at anything besides the values we pass in. In particular, looking at the definitions of the operands could potentially lead to it making assumption about undef values, which might lead to contradictions with the view SCCP has. I think this would lead to correctness issues similar to what NewGVN currently suffers from.

I initially thought passing in a context without DT & CxtI would be enough to ensure that, but I had another look and now I am not too sure. It seems like the SImplify* functions at least pass to operands to helpers from ValueTracking, which in turn may look at the operands of the operand, if it is an instruction. Not sure how to best prevent that now. One way would be to restrict that behavior via a new flag. Or create some kind of freestanding value that does not leak any information. What do you think?

[efriedma]

The problem I see here is that InstSimplify could take a possibly-undef value, and turn it into a simple constant; then we would lose track of the fact that the value might be undef. (For example, we transform "undef & -2 -> 0", and then incorrectly merge the result with a ConstantRange.)

For NewGVN, you're talking about https://bugs.llvm.org/show_bug.cgi?id=36335 ? I don't think that sort of issue applies here. The operand we're passing to InstSimplify is the operand of the actual operation, so any context InstSimplify could derive is the correct context. We don't try to apply the result to any other instruction.

[fhahn]

Updated to mark constants as may including undef, which in turn will ensure constant ranges are marked as including undef, for integer constants.

In D76459#1940015, @efriedma wrote:

The problem I see here is that InstSimplify could take a possibly-undef value, and turn it into a simple constant; then we would lose track of the fact that the value might be undef. (For example, we transform "undef & -2 -> 0", and then incorrectly merge the result with a ConstantRange.)

Ah I see what you mean. I don't think the example "undef & -2 -> 0" would cause any issues because we get a single constant and will replace all uses. For the AND example, I think the only problem would be if a constant expression could evaluate to either undef or a constant. I cannot think of a case where this might be possible off the top of my head, but we can make sure that the constant range we create includes undef, if we simplify to an integer constant. That should conservatively preserve the fact that the result may include undef.

What do you think?

For NewGVN, you're talking about https://bugs.llvm.org/show_bug.cgi?id=36335 ? I don't think that sort of issue applies here. The operand we're passing to InstSimplify is the operand of the actual operation, so any context InstSimplify could derive is the correct context. We don't try to apply the result to any other instruction.

Yes that was what I was thinking about. But as you said, it seems like it won't be an issue here, as we only pass constants or the original value.

[efriedma]

LGTM

I guess you're right that it doesn't cause any practical problem at the moment. If we actually resolve a value to a single constant, we can treat it as a simple constant in SCCP. The model is technically wrong as we're building it, but SCCP will replace the possibly-undef constant with a plain constant, and at that point the model is consistent with the transform. It would only become problematic if we didn't eventually perform that replacement.

llvm/lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/ValueLatticeUtils.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
void pushToWorkListMsg(ValueLatticeElement &IV, Value *V) {
     if (IV.isOverdefined())
       return OverdefinedInstWorkList.push_back(V);
     InstWorkList.push_back(V);
   }
 
   // markConstant - Make a value be marked as "constant".  If the value
   // is not already a constant, add it to the instruction work list so that
   // the users of the instruction are updated later.
-  bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C) {
-    if (!IV.markConstant(C)) return false;
+  bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,
+                    bool MayIncludeUndef = false) {
+    if (!IV.markConstant(C, MayIncludeUndef))
+      return false;
     LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
     pushToWorkList(IV, V);
     return true;
   }
 
   bool markConstant(Value *V, Constant *C) {
     assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
     return markConstant(ValueState[V], V, C);
void SCCPSolver::visitBinaryOperator(Instruction &I) {
 
   // If something is undef, wait for it to resolve.
   if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
     return;
 
   if (V1State.isOverdefined() && V2State.isOverdefined())
     return (void)markOverdefined(&I);
 
-  // Both operands are non-integer constants or constant expressions.
+  // If either of the operands is a constant, try to fold it to a constant.
   // TODO: Use information from notconstant better.
-  if (isConstant(V1State) && isConstant(V2State)) {
-    Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V1State),
-                                    getConstant(V2State));
+  if ((V1State.isConstant() || V2State.isConstant())) {
+    Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0);
+    Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1);
+    Value *R = SimplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
+    auto *C = dyn_cast_or_null<Constant>(R);
+    if (C) {
       // X op Y -> undef.
       if (isa<UndefValue>(C))
         return;
-    return (void)markConstant(IV, &I, C);
+      // Conservatively assume that the result may be based on operands that may
+      // be undef.
+      return (void)markConstant(IV, &I, C, /*MayIncludeUndef=*/true);
+    }
   }
 
   // Only use ranges for binary operators on integers.
   if (!I.getType()->isIntegerTy())
     return markOverdefined(&I);
 
-  // Operands are either constant ranges, notconstant, overdefined or one of the
-  // operands is a constant.
+  // Try to simplify to a constant range.
   ConstantRange A = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
   ConstantRange B = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
   if (V1State.isConstantRange())
     A = V1State.getConstantRange();
   if (V2State.isConstantRange())
     B = V2State.getConstantRange();
 
   ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);

llvm/test/Transforms/SCCP/ub-shift.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -sccp -S | FileCheck %s
 
 define void @shift_undef_64(i64* %p) {
 ; CHECK-LABEL: @shift_undef_64(
-; CHECK-NEXT:    [[R1:%.*]] = lshr i64 -1, 4294967296
-; CHECK-NEXT:    store i64 [[R1]], i64* [[P:%.*]]
-; CHECK-NEXT:    [[R2:%.*]] = ashr i64 -1, 4294967297
-; CHECK-NEXT:    store i64 [[R2]], i64* [[P]]
+; CHECK-NEXT:    store i64 0, i64* [[P:%.*]]
+; CHECK-NEXT:    store i64 -1, i64* [[P]]
 ; CHECK-NEXT:    [[R3:%.*]] = shl i64 -1, 4294967298
 ; CHECK-NEXT:    store i64 [[R3]], i64* [[P]]
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i64 -1, 4294967296 ; 2^32
   store i64 %r1, i64* %p
 
   %r2 = ashr i64 -1, 4294967297 ; 2^32 + 1
   store i64 %r2, i64* %p
 
   %r3 = shl i64 -1, 4294967298 ; 2^32 + 2
   store i64 %r3, i64* %p
 
   ret void
 }
 
 define void @shift_undef_65(i65* %p) {
 ; CHECK-LABEL: @shift_undef_65(
-; CHECK-NEXT:    [[R1:%.*]] = lshr i65 2, -18446744073709551615
-; CHECK-NEXT:    store i65 [[R1]], i65* [[P:%.*]]
-; CHECK-NEXT:    [[R2:%.*]] = ashr i65 4, -18446744073709551615
-; CHECK-NEXT:    store i65 [[R2]], i65* [[P]]
+; CHECK-NEXT:    store i65 0, i65* [[P:%.*]]
+; CHECK-NEXT:    store i65 0, i65* [[P]]
 ; CHECK-NEXT:    [[R3:%.*]] = shl i65 1, -18446744073709551615
 ; CHECK-NEXT:    store i65 [[R3]], i65* [[P]]
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i65 2, 18446744073709551617
   store i65 %r1, i65* %p
 
   %r2 = ashr i65 4, 18446744073709551617
   store i65 %r2, i65* %p
 
   %r3 = shl i65 1, 18446744073709551617
   store i65 %r3, i65* %p
 
   ret void
 }
 
 define void @shift_undef_256(i256* %p) {
 ; CHECK-LABEL: @shift_undef_256(
-; CHECK-NEXT:    [[R1:%.*]] = lshr i256 2, 18446744073709551617
-; CHECK-NEXT:    store i256 [[R1]], i256* [[P:%.*]]
-; CHECK-NEXT:    [[R2:%.*]] = ashr i256 4, 18446744073709551618
-; CHECK-NEXT:    store i256 [[R2]], i256* [[P]]
+; CHECK-NEXT:    store i256 0, i256* [[P:%.*]]
+; CHECK-NEXT:    store i256 0, i256* [[P]]
 ; CHECK-NEXT:    [[R3:%.*]] = shl i256 1, 18446744073709551619
 ; CHECK-NEXT:    store i256 [[R3]], i256* [[P]]
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i256 2, 18446744073709551617
   store i256 %r1, i256* %p
 
   %r2 = ashr i256 4, 18446744073709551618
   store i256 %r2, i256* %p
 
   %r3 = shl i256 1, 18446744073709551619
   store i256 %r3, i256* %p
 
   ret void
 }
 
 define void @shift_undef_511(i511* %p) {
 ; CHECK-LABEL: @shift_undef_511(
-; CHECK-NEXT:    [[R1:%.*]] = lshr i511 -1, 1208925819614629174706276
-; CHECK-NEXT:    store i511 [[R1]], i511* [[P:%.*]]
-; CHECK-NEXT:    [[R2:%.*]] = ashr i511 -2, 1208925819614629174706200
-; CHECK-NEXT:    store i511 [[R2]], i511* [[P]]
+; CHECK-NEXT:    store i511 0, i511* [[P:%.*]]
+; CHECK-NEXT:    store i511 -1, i511* [[P]]
 ; CHECK-NEXT:    [[R3:%.*]] = shl i511 -3, 1208925819614629174706180
 ; CHECK-NEXT:    store i511 [[R3]], i511* [[P]]
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i511 -1, 1208925819614629174706276 ; 2^80 + 100
   store i511 %r1, i511* %p
 
   %r2 = ashr i511 -2, 1208925819614629174706200
   store i511 %r2, i511* %p
 
   %r3 = shl i511 -3, 1208925819614629174706180
   store i511 %r3, i511* %p
 
   ret void
 }

llvm/test/Transforms/SCCP/vector-bitcast.ll

 ; RUN: opt -sccp -S < %s | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32-S128"
 
-; FIXME: Add back support for handling special values of vector/fp types.
-; CHECK: store volatile <2 x i64> %and.i119.i, <2 x i64>* %p
+; CHECK: store volatile <2 x i64> zeroinitializer, <2 x i64>* %p
 ; rdar://11324230
 
 define void @foo(<2 x i64>* %p) nounwind {
 entry:
   br label %while.body.i
 
 while.body.i:                                     ; preds = %while.body.i, %entry
   %vWorkExponent.i.033 = phi <4 x i32> [ %sub.i.i, %while.body.i ], [ <i32 939524096, i32 939524096, i32 939524096, i32 939524096>, %entry ]
   %sub.i.i = add <4 x i32> %vWorkExponent.i.033, <i32 -8388608, i32 -8388608, i32 -8388608, i32 -8388608>
   %0 = bitcast <4 x i32> %sub.i.i to <2 x i64>
   %and.i119.i = and <2 x i64> %0, zeroinitializer
   store volatile <2 x i64> %and.i119.i, <2 x i64>* %p
   br label %while.body.i
 }