From f12684d36ef3d9c40963993f3c891656ffa87f94 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Sat, 15 Oct 2022 18:34:02 +0100 Subject: [PATCH] [ConstraintElim] Support signed decomposition of `add nsw`. Add support decomposition for `add nsw` for signed queries. `add nsw` won't wrap and can be directly added to the signed system. --- .../Transforms/Scalar/ConstraintElimination.cpp | 27 ++++++---- .../Transforms/ConstraintElimination/add-nsw.ll | 63 ++++++++++++++++++---- .../mixed-signed-unsigned-predicates.ll | 2 +- 3 files changed, 71 insertions(+), 21 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index 81b15c0..d2f4e73 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -326,12 +326,28 @@ static SmallVector decompose(Value *V, SmallVector &Preconditions, bool IsSigned, const DataLayout &DL) { + auto MergeResults = [&Preconditions, IsSigned, + DL](Value *A, Value *B, + bool IsSignedB) -> SmallVector { + auto ResA = decompose(A, Preconditions, IsSigned, DL); + auto ResB = decompose(B, Preconditions, IsSignedB, DL); + if (ResA.empty() || ResB.empty()) + return {}; + ResA[0].Coefficient += ResB[0].Coefficient; + append_range(ResA, drop_begin(ResB)); + return ResA; + }; + // Decompose \p V used with a signed predicate. if (IsSigned) { if (auto *CI = dyn_cast(V)) { if (canUseSExt(CI)) return {{CI->getSExtValue(), nullptr}}; } + Value *Op0; + Value *Op1; + if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) + return MergeResults(Op0, Op1, IsSigned); return {{0, nullptr}, {1, V}}; } @@ -352,17 +368,6 @@ decompose(Value *V, SmallVector &Preconditions, V = Op0; } - auto MergeResults = [&Preconditions, IsSigned, - DL](Value *A, Value *B, - bool IsSignedB) -> SmallVector { - auto ResA = decompose(A, Preconditions, IsSigned, DL); - auto ResB = decompose(B, Preconditions, IsSignedB, DL); - if (ResA.empty() || ResB.empty()) - return {}; - ResA[0].Coefficient += ResB[0].Coefficient; - append_range(ResA, drop_begin(ResB)); - return ResA; - }; Value *Op1; ConstantInt *CI; if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) { diff --git a/llvm/test/Transforms/ConstraintElimination/add-nsw.ll b/llvm/test/Transforms/ConstraintElimination/add-nsw.ll index be65c38..6e5e152 100644 --- a/llvm/test/Transforms/ConstraintElimination/add-nsw.ll +++ b/llvm/test/Transforms/ConstraintElimination/add-nsw.ll @@ -1,7 +1,9 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s -define void @test.not.uge.ult(i8 %start, i8 %low, i8 %high) { +declare void @use(i1) + +define void @test.not.uge.ult(i8 %start, i8 %high) { ; CHECK-LABEL: @test.not.uge.ult( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[ADD_PTR_I:%.*]] = add nsw i8 [[START:%.*]], 3 @@ -52,7 +54,7 @@ if.end: ; preds = %entry ret void } -define void @test.not.sge.slt(i8 %start, i8 %low, i8 %high) { +define void @test.not.sge.slt(i8 %start, i8 %high) { ; CHECK-LABEL: @test.not.sge.slt( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[ADD_PTR_I:%.*]] = add nsw i8 [[START:%.*]], 3 @@ -62,16 +64,16 @@ define void @test.not.sge.slt(i8 %start, i8 %low, i8 %high) { ; CHECK-NEXT: ret void ; CHECK: if.end: ; CHECK-NEXT: [[T_0:%.*]] = icmp slt i8 [[START]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_0]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_1:%.*]] = add nsw i8 [[START]], 1 ; CHECK-NEXT: [[T_1:%.*]] = icmp slt i8 [[START_1]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_2:%.*]] = add nsw i8 [[START]], 2 ; CHECK-NEXT: [[T_2:%.*]] = icmp slt i8 [[START_2]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_3:%.*]] = add nsw i8 [[START]], 3 ; CHECK-NEXT: [[T_3:%.*]] = icmp slt i8 [[START_3]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_4:%.*]] = add nsw i8 [[START]], 4 ; CHECK-NEXT: [[C_4:%.*]] = icmp slt i8 [[START_4]], [[HIGH]] ; CHECK-NEXT: call void @use(i1 [[C_4]]) @@ -118,10 +120,10 @@ define void @test.decompose.nonconst(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK: if.then.2: ; CHECK-NEXT: [[ADD_0:%.*]] = add nsw i8 [[A]], [[B]] ; CHECK-NEXT: [[T_0:%.*]] = icmp sge i8 [[ADD_0]], [[C]] -; CHECK-NEXT: call void @use(i1 [[T_0]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[ADD_1:%.*]] = add nsw i8 [[A]], [[A]] ; CHECK-NEXT: [[T_1:%.*]] = icmp sge i8 [[ADD_0]], [[C]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[ADD_2:%.*]] = add nsw i8 [[A]], [[D:%.*]] ; CHECK-NEXT: [[C_4:%.*]] = icmp sge i8 [[ADD_2]], [[C]] ; CHECK-NEXT: call void @use(i1 [[C_4]]) @@ -200,4 +202,47 @@ if.end: ; preds = %entry ret void } -declare void @use(i1) +define void @test.sge.slt.add.neg(i8 %start, i8 %high) { +; CHECK-LABEL: @test.sge.slt.add.neg( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[ADD_PTR_I:%.*]] = add nsw i8 [[START:%.*]], -3 +; CHECK-NEXT: [[C_1:%.*]] = icmp slt i8 [[ADD_PTR_I]], [[HIGH:%.*]] +; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp slt i8 [[START]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[START_1:%.*]] = add nsw i8 [[START]], 1 +; CHECK-NEXT: [[C_3:%.*]] = icmp slt i8 [[START_1]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: [[START_2:%.*]] = add nsw i8 [[START]], -2 +; CHECK-NEXT: [[C_4:%.*]] = icmp slt i8 [[START_2]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: [[START_3:%.*]] = add nsw i8 [[START]], -3 +; CHECK-NEXT: [[T_1:%.*]] = icmp slt i8 [[START_3]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[START_4:%.*]] = add nsw i8 [[START]], -4 +; CHECK-NEXT: [[T_2:%.*]] = icmp slt i8 [[START_4]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: ret void +; +entry: + %add.ptr.i = add nsw i8 %start, -3 + %c.1 = icmp slt i8 %add.ptr.i, %high + call void @llvm.assume(i1 %c.1) + %c.2 = icmp slt i8 %start, %high + call void @use(i1 %c.2) + %start.1 = add nsw i8 %start, 1 + %c.3 = icmp slt i8 %start.1, %high + call void @use(i1 %c.3) + %start.2 = add nsw i8 %start, -2 + %c.4 = icmp slt i8 %start.2, %high + call void @use(i1 %c.4) + %start.3 = add nsw i8 %start, -3 + %t.1 = icmp slt i8 %start.3, %high + call void @use(i1 %t.1) + %start.4 = add nsw i8 %start, -4 + %t.2 = icmp slt i8 %start.4, %high + call void @use(i1 %t.2) + ret void +} + +declare void @llvm.assume(i1) diff --git a/llvm/test/Transforms/ConstraintElimination/mixed-signed-unsigned-predicates.ll b/llvm/test/Transforms/ConstraintElimination/mixed-signed-unsigned-predicates.ll index cec97d5..2dc9efd 100644 --- a/llvm/test/Transforms/ConstraintElimination/mixed-signed-unsigned-predicates.ll +++ b/llvm/test/Transforms/ConstraintElimination/mixed-signed-unsigned-predicates.ll @@ -148,7 +148,7 @@ define i1 @test_add_nsw(i8 %start, i8 %low, i8 %high) { ; CHECK-NEXT: [[F_1:%.*]] = icmp uge i8 [[START_1]], [[HIGH]] ; CHECK-NEXT: [[RES_0:%.*]] = xor i1 [[F_0]], [[F_1]] ; CHECK-NEXT: [[SC_1:%.*]] = icmp sgt i8 [[START]], [[HIGH]] -; CHECK-NEXT: [[RES_1:%.*]] = xor i1 [[RES_0]], [[SC_1]] +; CHECK-NEXT: [[RES_1:%.*]] = xor i1 [[RES_0]], false ; CHECK-NEXT: [[SC_2:%.*]] = icmp sge i8 [[START_1]], [[HIGH]] ; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], [[SC_2]] ; CHECK-NEXT: [[START_2:%.*]] = add nuw i8 [[START]], 2 -- 2.7.4