summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--docs/LangRef.rst16
-rw-r--r--include/llvm/Analysis/ValueTracking.h5
-rw-r--r--lib/Analysis/ValueTracking.cpp17
-rw-r--r--lib/CodeGen/SelectionDAG/SelectionDAG.cpp2
-rw-r--r--lib/IR/Verifier.cpp3
-rw-r--r--test/Transforms/InstCombine/AddOverFlow.ll38
-rw-r--r--test/Transforms/InstCombine/add2.ll41
-rw-r--r--test/Verifier/range-1.ll2
-rw-r--r--test/Verifier/range-2.ll30
9 files changed, 138 insertions, 16 deletions
diff --git a/docs/LangRef.rst b/docs/LangRef.rst
index cb94d3967b..b75058fa9a 100644
--- a/docs/LangRef.rst
+++ b/docs/LangRef.rst
@@ -2749,11 +2749,12 @@ number representing the maximum relative error, for example:
'``range``' Metadata
^^^^^^^^^^^^^^^^^^^^
-``range`` metadata may be attached only to loads of integer types. It
-expresses the possible ranges the loaded value is in. The ranges are
-represented with a flattened list of integers. The loaded value is known
-to be in the union of the ranges defined by each consecutive pair. Each
-pair has the following properties:
+``range`` metadata may be attached only to ``load``, ``call`` and ``invoke`` of
+integer types. It expresses the possible ranges the loaded value or the value
+returned by the called function at this call site is in. The ranges are
+represented with a flattened list of integers. The loaded value or the value
+returned is known to be in the union of the ranges defined by each consecutive
+pair. Each pair has the following properties:
- The type must match the type loaded by the instruction.
- The pair ``a,b`` represents the range ``[a,b)``.
@@ -2771,8 +2772,9 @@ Examples:
%a = load i8* %x, align 1, !range !0 ; Can only be 0 or 1
%b = load i8* %y, align 1, !range !1 ; Can only be 255 (-1), 0 or 1
- %c = load i8* %z, align 1, !range !2 ; Can only be 0, 1, 3, 4 or 5
- %d = load i8* %z, align 1, !range !3 ; Can only be -2, -1, 3, 4 or 5
+ %c = call i8 @foo(), !range !2 ; Can only be 0, 1, 3, 4 or 5
+ %d = invoke i8 @bar() to label %cont
+ unwind label %lpad, !range !3 ; Can only be -2, -1, 3, 4 or 5
...
!0 = metadata !{ i8 0, i8 2 }
!1 = metadata !{ i8 255, i8 2 }
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index ce7896738d..83b5408fb1 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -37,7 +37,10 @@ namespace llvm {
/// for all of the elements in the vector.
void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
const DataLayout *TD = nullptr, unsigned Depth = 0);
- void computeKnownBitsLoad(const MDNode &Ranges, APInt &KnownZero);
+ /// Compute known bits from the range metadata.
+ /// \p KnownZero the set of bits that are known to be zero
+ void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
+ APInt &KnownZero);
/// ComputeSignBit - Determine whether the sign bit is known to be zero or
/// one. Convenience wrapper around computeKnownBits.
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index 4f48753578..9de945ed70 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -188,7 +188,8 @@ static void computeKnownBitsMul(Value *Op0, Value *Op1, bool NSW,
KnownOne.setBit(BitWidth - 1);
}
-void llvm::computeKnownBitsLoad(const MDNode &Ranges, APInt &KnownZero) {
+void llvm::computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
+ APInt &KnownZero) {
unsigned BitWidth = KnownZero.getBitWidth();
unsigned NumRanges = Ranges.getNumOperands() / 2;
assert(NumRanges >= 1);
@@ -338,7 +339,7 @@ void llvm::computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
default: break;
case Instruction::Load:
if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range))
- computeKnownBitsLoad(*MD, KnownZero);
+ computeKnownBitsFromRangeMetadata(*MD, KnownZero);
break;
case Instruction::And: {
// If either the LHS or the RHS are Zero, the result is zero.
@@ -733,6 +734,12 @@ void llvm::computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
break;
}
case Instruction::Call:
+ case Instruction::Invoke:
+ if (MDNode *MD = cast<Instruction>(I)->getMetadata(LLVMContext::MD_range))
+ computeKnownBitsFromRangeMetadata(*MD, KnownZero);
+ // If a range metadata is attached to this IntrinsicInst, intersect the
+ // explicit range specified by the metadata and the implicit range of
+ // the intrinsic.
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
default: break;
@@ -742,16 +749,16 @@ void llvm::computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
// If this call is undefined for 0, the result will be less than 2^n.
if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
LowBits -= 1;
- KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
+ KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
break;
}
case Intrinsic::ctpop: {
unsigned LowBits = Log2_32(BitWidth)+1;
- KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
+ KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
break;
}
case Intrinsic::x86_sse42_crc32_64_64:
- KnownZero = APInt::getHighBitsSet(64, 32);
+ KnownZero |= APInt::getHighBitsSet(64, 32);
break;
}
}
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 639eb462e7..5923f0e208 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -2084,7 +2084,7 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
unsigned MemBits = VT.getScalarType().getSizeInBits();
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
} else if (const MDNode *Ranges = LD->getRanges()) {
- computeKnownBitsLoad(*Ranges, KnownZero);
+ computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
}
break;
}
diff --git a/lib/IR/Verifier.cpp b/lib/IR/Verifier.cpp
index d1c7f7d25c..ad3c29c564 100644
--- a/lib/IR/Verifier.cpp
+++ b/lib/IR/Verifier.cpp
@@ -2233,7 +2233,8 @@ void Verifier::visitInstruction(Instruction &I) {
}
MDNode *MD = I.getMetadata(LLVMContext::MD_range);
- Assert1(!MD || isa<LoadInst>(I), "Ranges are only for loads!", &I);
+ Assert1(!MD || isa<LoadInst>(I) || isa<CallInst>(I) || isa<InvokeInst>(I),
+ "Ranges are only for loads, calls and invokes!", &I);
InstsInThisBlock.insert(&I);
}
diff --git a/test/Transforms/InstCombine/AddOverFlow.ll b/test/Transforms/InstCombine/AddOverFlow.ll
index 70178ec83b..8f3d429c8d 100644
--- a/test/Transforms/InstCombine/AddOverFlow.ll
+++ b/test/Transforms/InstCombine/AddOverFlow.ll
@@ -34,6 +34,44 @@ define i16 @zero_sign_bit2(i16 %a, i16 %b) {
ret i16 %3
}
+declare i16 @bounded(i16 %input);
+declare i32 @__gxx_personality_v0(...);
+!0 = metadata !{i16 0, i16 32768} ; [0, 32767]
+!1 = metadata !{i16 0, i16 32769} ; [0, 32768]
+
+define i16 @add_bounded_values(i16 %a, i16 %b) {
+; CHECK-LABEL: @add_bounded_values(
+entry:
+ %c = call i16 @bounded(i16 %a), !range !0
+ %d = invoke i16 @bounded(i16 %b) to label %cont unwind label %lpad, !range !0
+cont:
+; %c and %d are in [0, 32767]. Therefore, %c + %d doesn't unsigned overflow.
+ %e = add i16 %c, %d
+; CHECK: add nuw i16 %c, %d
+ ret i16 %e
+lpad:
+ %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
+ filter [0 x i8*] zeroinitializer
+ ret i16 42
+}
+
+define i16 @add_bounded_values_2(i16 %a, i16 %b) {
+; CHECK-LABEL: @add_bounded_values_2(
+entry:
+ %c = call i16 @bounded(i16 %a), !range !1
+ %d = invoke i16 @bounded(i16 %b) to label %cont unwind label %lpad, !range !1
+cont:
+; Similar to add_bounded_values, but %c and %d are in [0, 32768]. Therefore,
+; %c + %d may unsigned overflow and we cannot add NUW.
+ %e = add i16 %c, %d
+; CHECK: add i16 %c, %d
+ ret i16 %e
+lpad:
+ %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
+ filter [0 x i8*] zeroinitializer
+ ret i16 42
+}
+
; CHECK-LABEL: @ripple_nsw1
; CHECK: add nsw i16 %a, %b
define i16 @ripple_nsw1(i16 %x, i16 %y) {
diff --git a/test/Transforms/InstCombine/add2.ll b/test/Transforms/InstCombine/add2.ll
index 0328c4ff6e..821fce0dab 100644
--- a/test/Transforms/InstCombine/add2.ll
+++ b/test/Transforms/InstCombine/add2.ll
@@ -217,3 +217,44 @@ define i32 @mul_add_to_mul_6(i32 %x, i32 %y) {
; CHECK-NEXT: %add = mul nsw i32 %mul1, 6
; CHECK-NEXT: ret i32 %add
}
+
+; This test and the next test verify that when a range metadata is attached to
+; llvm.cttz, ValueTracking correctly intersects the range specified by the
+; metadata and the range implied by the intrinsic.
+;
+; In this test, the range specified by the metadata is more strict. Therefore,
+; ValueTracking uses that range.
+define i16 @add_cttz(i16 %a) {
+; CHECK-LABEL: @add_cttz(
+ ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned
+ ; is in [0, 16). The range metadata indicates the value returned is in [0, 8).
+ ; Intersecting these ranges, we know the value returned is in [0, 8).
+ ; Therefore, InstCombine will transform
+ ; add %cttz, 1111 1111 1111 1000 ; decimal -8
+ ; to
+ ; or %cttz, 1111 1111 1111 1000
+ %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !0
+ %b = add i16 %cttz, -8
+; CHECK: or i16 %cttz, -8
+ ret i16 %b
+}
+declare i16 @llvm.cttz.i16(i16, i1)
+!0 = metadata !{i16 0, i16 8}
+
+; Similar to @add_cttz, but in this test, the range implied by the
+; intrinsic is more strict. Therefore, ValueTracking uses that range.
+define i16 @add_cttz_2(i16 %a) {
+; CHECK-LABEL: @add_cttz_2(
+ ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned
+ ; is in [0, 16). The range metadata indicates the value returned is in
+ ; [0, 32). Intersecting these ranges, we know the value returned is in
+ ; [0, 16). Therefore, InstCombine will transform
+ ; add %cttz, 1111 1111 1111 0000 ; decimal -16
+ ; to
+ ; or %cttz, 1111 1111 1111 0000
+ %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !1
+ %b = add i16 %cttz, -16
+; CHECK: or i16 %cttz, -16
+ ret i16 %b
+}
+!1 = metadata !{i16 0, i16 32}
diff --git a/test/Verifier/range-1.ll b/test/Verifier/range-1.ll
index b6a75d13bb..f15ca3f740 100644
--- a/test/Verifier/range-1.ll
+++ b/test/Verifier/range-1.ll
@@ -6,7 +6,7 @@ entry:
ret void
}
!0 = metadata !{i8 0, i8 1}
-; CHECK: Ranges are only for loads!
+; CHECK: Ranges are only for loads, calls and invokes!
; CHECK-NEXT: store i8 0, i8* %x, align 1, !range !0
define i8 @f2(i8* %x) {
diff --git a/test/Verifier/range-2.ll b/test/Verifier/range-2.ll
index 8d85d19151..1d2e0575d7 100644
--- a/test/Verifier/range-2.ll
+++ b/test/Verifier/range-2.ll
@@ -34,3 +34,33 @@ entry:
ret i8 %y
}
!4 = metadata !{i8 -1, i8 0, i8 1, i8 -2}
+
+; We can annotate the range of the return value of a CALL.
+define void @call_all(i8* %x) {
+entry:
+ %v1 = call i8 @f1(i8* %x), !range !0
+ %v2 = call i8 @f2(i8* %x), !range !1
+ %v3 = call i8 @f3(i8* %x), !range !2
+ %v4 = call i8 @f4(i8* %x), !range !3
+ %v5 = call i8 @f5(i8* %x), !range !4
+ ret void
+}
+
+; We can annotate the range of the return value of an INVOKE.
+define void @invoke_all(i8* %x) {
+entry:
+ %v1 = invoke i8 @f1(i8* %x) to label %cont unwind label %lpad, !range !0
+ %v2 = invoke i8 @f2(i8* %x) to label %cont unwind label %lpad, !range !1
+ %v3 = invoke i8 @f3(i8* %x) to label %cont unwind label %lpad, !range !2
+ %v4 = invoke i8 @f4(i8* %x) to label %cont unwind label %lpad, !range !3
+ %v5 = invoke i8 @f5(i8* %x) to label %cont unwind label %lpad, !range !4
+
+cont:
+ ret void
+
+lpad:
+ %4 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
+ filter [0 x i8*] zeroinitializer
+ ret void
+}
+declare i32 @__gxx_personality_v0(...)
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-09 22:13:06 +0000