From c9826829d74e637163fdb0351870b8204e62d6e6 Mon Sep 17 00:00:00 2001 From: Bryan Chan Date: Sat, 29 Aug 2020 17:25:16 -0400 Subject: [PATCH] [EarlyCSE] Equivalent SELECTs should hash equally DenseMap assumes that, if its isEqual method returns true for two elements, then its getHashValue method must return the same value for them. This invariant is broken when one SELECT node is a min/max operation, and the other can be transformed into an equivalent min/max by inverting its predicate and swapping its operands. This patch fixes an assertion failure that would occur intermittently while compiling the following IR: define i32 @t(i32 %i) { %cmp = icmp sle i32 0, %i %twin1 = select i1 %cmp, i32 %i, i32 0 %cmpinv = icmp sgt i32 0, %i %twin2 = select i1 %cmpinv, i32 0, i32 %i %sink = add i32 %twin1, %twin2 ret i32 %sink } Differential Revision: https://reviews.llvm.org/D86843 --- llvm/lib/Transforms/Scalar/EarlyCSE.cpp | 13 +++++++++++++ llvm/test/Transforms/EarlyCSE/commute.ll | 19 +++++++++++++++++++ 2 files changed, 32 insertions(+) diff --git a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp index b655204..f0d3f90 100644 --- a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp +++ b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp @@ -191,6 +191,19 @@ static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A, Pred = ICmpInst::getSwappedPredicate(Pred); } + // Check for inverted variants of min/max by swapping operands. + switch (Pred) { + case CmpInst::ICMP_ULE: + case CmpInst::ICMP_UGE: + case CmpInst::ICMP_SLE: + case CmpInst::ICMP_SGE: + Pred = CmpInst::getInversePredicate(Pred); + std::swap(A, B); + break; + default: + break; + } + switch (Pred) { case CmpInst::ICMP_UGT: Flavor = SPF_UMAX; break; case CmpInst::ICMP_ULT: Flavor = SPF_UMIN; break; diff --git a/llvm/test/Transforms/EarlyCSE/commute.ll b/llvm/test/Transforms/EarlyCSE/commute.ll index 57c5a85..f5868a5 100644 --- a/llvm/test/Transforms/EarlyCSE/commute.ll +++ b/llvm/test/Transforms/EarlyCSE/commute.ll @@ -684,6 +684,25 @@ define i32 @select_not_invert_pred_cond_wrong_select_op(i8 %x, i8 %y, i32 %t, i3 ret i32 %r } +; This test is a reproducer for a bug involving inverted min/max selects +; hashing differently but comparing as equal. It exhibits such a pair of +; values, and we run this test with -earlycse-debug-hash which would catch +; the disagreement and fail if it regressed. +define i32 @inverted_max(i32 %i) { +; CHECK-LABEL: @inverted_max( +; CHECK-NEXT: [[CMP:%.*]] = icmp sle i32 0, [[I:%.*]] +; CHECK-NEXT: [[M1:%.*]] = select i1 [[CMP]], i32 [[I]], i32 0 +; CHECK-NEXT: [[CMPINV:%.*]] = icmp sgt i32 0, [[I:%.*]] +; CHECK-NEXT: [[M2:%.*]] = select i1 [[CMPINV]], i32 0, i32 [[I]] +; CHECK-NEXT: [[R:%.*]] = add i32 [[M1]], [[M2]] +; CHECK-NEXT: ret i32 [[R]] + %cmp = icmp sle i32 0, %i + %m1 = select i1 %cmp, i32 %i, i32 0 + %cmpinv = icmp sgt i32 0, %i + %m2 = select i1 %cmpinv, i32 0, i32 %i + %r = add i32 %m1, %m2 + ret i32 %r +} ; This test is a reproducer for a bug involving inverted min/max selects ; hashing differently but comparing as equal. It exhibits such a pair of -- 2.7.4