Thanks for taking a look!

> In https://reviews.llvm.org/D68103 the InstCombine learned that shift-by-sext

> is simply a shift-by-zext.

Just to make sure I'm following, the reasoning here is that the shift

amount must be positive or the shift would produce poison? And thus,

it's safe to assume that the sext == zext because we've (at worst)

removed UB in the original program?

Yes.

zext and sext are equivalent for non-negative inputs.

For negative inputs, sext will produce negative output.

And interpreted as unsigned number, such negative shift amount

is *always* bigger than largest legal shift amount:

* i1 can only be shifted by 0

* i2 can only be shifted by 1 (positive); 2,3 (negative) are not legal

shift amounts

* i3 can only be shifted by 1,2 (positive); 3 (positive) and 4-7

(negative) are not legal shift amounts

* i4 can only be shifted by 1,2,3 (positive); 4-7 (positive) and 8-15

(negative) are not legal shift amounts

* and so on.

Therefore we must not have negative shift amount (or we have UB), so

we can just use zext.

If so, two slightly off topic ideas.

1) This feels like a demanded bits problem. We know that any shift

value outside of a given range is UB, and thus only need to demand the

bits necessary to represent the defined range. Might be an interesting

extension.

Most specifically, we demand only low

bitwidth(shift)-ctlz(bitwidth(shift)-1) bits

of shift amount, yes. I did think of it as a demanded bits problem,

but didn't really succeed, let me see again..

2) Are we possibly missing opportunities by not exploiting knowledge of

the a known negative shift amount?

Anything specific you are thinking of?

> But the transform is limited to single-use sext.

> We can quite trivially get a case where there are two shifts by the same sext:

> https://godbolt.org/z/j6mO3t <- We should handle those cases.

>

> In https://reviews.llvm.org/D68103#1686130 Sanjay Patel notes that this

> sext is intrusive for analysis, that we will gain far better analysis with zext,

> so we should just ignore forego of the one-use check,

> and simply replace all shift-by-sext with shift-by-zext.

Doing the multi-use case is unfortunately complicated. Your limited use

scan might be a reasonable option in practice, but the need for cutoffs

creates undesirable dynamics.

To reiterate, the proposal is to just always transform that sext into zext,

with no care to the use count. So i'm not sure what cutoffs you mean.

A couple ideas on how to possibly approach the problem:

1) If we can prove that one shift dominates the other uses, then if we

can find UB which triggers based on overflow, we can do the replacement.

I'm not sure what all this means.

Here i only want to get rid of *all* of those sext's for good, so everything

else that may have to deal with looking past extension of shift amount

doesn't need to be modified.

2) Having a general multiple use demanded use routine would be very

powerful. Is it worth exploring the harder topic for generality?

There is some support for multi-use demandedbits in backend.

As for middle-end i'm not sure.

For sure, having that powerful mechanism may be useful, in general.

3) If we had an anyextend IR node, it might be reasonable to eagerly

produce the duplicate nodes, and rely on later CSE. I keep running

across cases where we have an extend where we know the high bits don't

matter, maybe it's time to represent that?

> I implemented this proposed suggestion here:

> https://reviews.llvm.org/D68150

>

> Does anyone see any problems with that trade-off?

>

Roman.