This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Improve impliesPoison
ClosedPublic

Authored by aqjune on Feb 17 2021, 8:11 PM.

Details

Summary

This patch improves ValueTracking's impliesPoison(V1, V2) to do this reasoning:

  %res = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
  %overflow = extractvalue { i64, i1 } %res, 1
  %mul      = extractvalue { i64, i1 } %res, 0

	; If %mul is poison, %overflow is also poison, and vice versa.

This improvement leads to supporting this optimization under -instcombine-unsafe-select-transform=0:

define i1 @test2_logical(i64 %a, i64 %b, i64* %ptr) {
; CHECK-LABEL: @test2_logical(
; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A]], 0
; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[B]], 0
; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = and i1 [[TMP1]], [[TMP2]]
; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[MUL]]
; CHECK-NEXT:    store i64 [[NEG]], i64* [[PTR:%.*]], align 8
; CHECK-NEXT:    ret i1 [[OVERFLOW_1]]
;

  %res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
  %overflow = extractvalue { i64, i1 } %res, 1
  %mul = extractvalue { i64, i1 } %res, 0
  %cmp = icmp ne i64 %mul, 0
  %overflow.1 = select i1 %overflow, i1 true, i1 %cmp
  %neg = sub i64 0, %mul
  store i64 %neg, i64* %ptr, align 8
  ret i1 %overflow.1
}

Previously, this didn't happen because the flag prevented select i1 %overflow, i1 true, i1 %cmp from being or i1 %overflow, %cmp.
Note that the select -> or conversion happens only when impliesPoison(%cmp, %overflow) returns true.
This improvement allows impliesPoison to do the reasoning.

Diff Detail

Event Timeline

aqjune created this revision.Feb 17 2021, 8:11 PM
aqjune requested review of this revision.Feb 17 2021, 8:11 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 17 2021, 8:11 PM
aqjune added inline comments.Feb 17 2021, 8:15 PM
llvm/include/llvm/Analysis/ValueTracking.h
587

I chose to not make propagatesPoison return true on extractvalue because otherwise we lose this nice property:
"If propagatesPoison(op x y) is true, and the result is non-poison, x and y are also non-poison"
If extractvalue is added, this doesn't hold any more; imagine

%aggr = { i64 poison, i64 0 }
%I = extractvalue %aggr, 1
; propagatesPoison(extractvalue %aggr, 1) now returns true, and the result is well-defined (constant 0), but %aggr isn't well-defined
spatel added inline comments.Feb 18 2021, 9:00 AM
llvm/lib/Analysis/ValueTracking.cpp
4865–4867

Are there other patterns that you are planning to add here?
If not, we could make the patch much smaller with a more direct match like we use in InstCombineSelect.cpp:

WithOverflowInst *II;
if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||
    !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
  return nullptr;
aqjune updated this revision to Diff 324838.Feb 18 2021, 6:49 PM

Use m_WithOverflowInst

aqjune marked an inline comment as done.Feb 18 2021, 6:51 PM
aqjune added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4865–4867

Yep, I think dealing with overflow instructions is enough.
I updated the code to use matches (with updates in PatternMatch.h)

Thanks - the pattern match with special-case -1 is a bit awkward, but I don't have a better suggestion.
I am not sure about subtleties of directlyImpliesPoison vs. impliesPoison. @nikic may want to have a look.

nikic accepted this revision.Feb 19 2021, 12:03 PM

LGTM

This revision is now accepted and ready to land.Feb 19 2021, 12:03 PM
This revision was landed with ongoing or failed builds.Feb 19 2021, 8:45 PM
This revision was automatically updated to reflect the committed changes.
aqjune marked an inline comment as done.