Index: docs/LangRef.rst =================================================================== --- docs/LangRef.rst +++ docs/LangRef.rst @@ -2749,11 +2749,12 @@ '``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 @@ %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 } Index: include/llvm/Analysis/ValueTracking.h =================================================================== --- include/llvm/Analysis/ValueTracking.h +++ include/llvm/Analysis/ValueTracking.h @@ -37,7 +37,10 @@ /// 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. Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -188,7 +188,8 @@ 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 @@ default: break; case Instruction::Load: if (MDNode *MD = cast(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 @@ break; } case Instruction::Call: + case Instruction::Invoke: + if (MDNode *MD = cast(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(I)) { switch (II->getIntrinsicID()) { default: break; @@ -742,16 +749,16 @@ // 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; } } Index: lib/CodeGen/SelectionDAG/SelectionDAG.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -2084,7 +2084,7 @@ 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; } Index: lib/IR/Verifier.cpp =================================================================== --- lib/IR/Verifier.cpp +++ lib/IR/Verifier.cpp @@ -2233,7 +2233,8 @@ } MDNode *MD = I.getMetadata(LLVMContext::MD_range); - Assert1(!MD || isa(I), "Ranges are only for loads!", &I); + Assert1(!MD || isa(I) || isa(I) || isa(I), + "Ranges are only for loads, calls and invokes!", &I); InstsInThisBlock.insert(&I); } Index: test/Transforms/InstCombine/AddOverFlow.ll =================================================================== --- test/Transforms/InstCombine/AddOverFlow.ll +++ test/Transforms/InstCombine/AddOverFlow.ll @@ -34,6 +34,44 @@ 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) { Index: test/Transforms/InstCombine/add2.ll =================================================================== --- test/Transforms/InstCombine/add2.ll +++ test/Transforms/InstCombine/add2.ll @@ -86,3 +86,44 @@ ; CHECK-NEXT: %d = mul i16 %a, -32767 ; CHECK-NEXT: ret i16 %d } + +; 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 @test10(i16 %a) { +; CHECK-LABEL: @test10( + ; 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 @test10, but in this test, the range implied by the +; intrinsic is more strict. Therefore, ValueTracking uses that range. +define i16 @test11(i16 %a) { +; CHECK-LABEL: @test11( + ; 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} Index: test/Verifier/range-1.ll =================================================================== --- test/Verifier/range-1.ll +++ test/Verifier/range-1.ll @@ -6,7 +6,7 @@ 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) { Index: test/Verifier/range-2.ll =================================================================== --- test/Verifier/range-2.ll +++ test/Verifier/range-2.ll @@ -34,3 +34,33 @@ 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(...)