HomePhabricator

[SCEV] Model `ashr exact x, C` as `(abs(x) EXACT/u (1<<C)) * signum(x)`

Authored by lebedev.ri on Oct 17 2020, 11:04 AM.

Description

[SCEV] Model ashr exact x, C as (abs(x) EXACT/u (1<<C)) * signum(x)

It's not pretty, but probably better than modelling it
as an opaque SCEVUnknown, i guess.

It is relevant e.g. for the loop that was brought up in
https://bugs.llvm.org/show_bug.cgi?id=46786#c26
as an example of what we'd be able to better analyze
once SCEV handles ptrtoint (D89456).

But as it is evident, even if we deal with ptrtoint there,
we also fail to model such an ashr.
Also, modeling of mul-of-exact-shr/div could use improvement.

As per alive2:
https://alive2.llvm.org/ce/z/tnfZKd

define i8 @src(i8 %0) {
  %2 = ashr exact i8 %0, 4
  ret i8 %2
}

declare i8 @llvm.abs(i8, i1)
declare i8 @llvm.smin(i8, i8)
declare i8 @llvm.smax(i8, i8)

define i8 @tgt(i8 %x) {
  %abs_x = call i8 @llvm.abs(i8 %x, i1 false)
  %div = udiv exact i8 %abs_x, 16
  %t0 = call i8 @llvm.smax(i8 %x, i8 -1)
  %t1 = call i8 @llvm.smin(i8 %t0, i8 1)
  %r = mul nsw i8 %div, %t1
  ret i8 %r
}

Transformation seems to be correct!

Details

Committed
lebedev.riOct 17 2020, 11:22 AM
Parents
rG130cc662b5d3: [NFC][SCEV] Refactor getAbsExpr() out of createSCEV()
Branches
Unknown
Tags
Unknown