%x = shl i64 %w, n

%y = add i64 %x, c

%z = ashr i64 %y, m

The above given instruction triplet is seen many times in the generated

LLVM IR, but SCEV model is not able to compute the SCEV value of AShr

instruction in this case.

This patch models the two cases of the above instruction pattern using

the following expression:

## > sext(add(mul(trunc(w), 2^(n-m)), c >> m))

- when n = m the expression reduces to sext(add(trunc(w), c >> n))

as n-m=0, and multiplying with 2^0 gives the same result.

- when n > m the expression works as given above.

It also adds several unittest to verify that SCEV is able to compute

the value.

$ opt sext-add-inreg.ll -passes="print<scalar-evolution>"

Comparing the snippets of the result of SCEV analysis:

- SCEV of ashr before change ----------------------------

%idxprom = ashr exact i64 %sext, 32

--> %idxprom U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: 8 LoopDispositions: { %for.body: Variant }

- SCEV of ashr after change ---------------------------

%idxprom = ashr exact i64 %sext, 32

--> {0,+,1}<nuw><nsw><%for.body> U: [0,9) S: [0,9) Exits: 8 LoopDispositions: { %for.body: Computable }

LoopDisposition of the given SCEV was LoopVariant before, after adding

the new way to model the instruction, the LoopDisposition becomes

LoopComputable as it is able to compute the SCEV of the instruction.