Induction variable simplification does not simplify truncates

[sanjoy]

Bugzilla Link	24670
Version	trunk
OS	All
CC	@atrick,@hfinkel,@preames

Extended Description

Currently LLVM does not optimize %c0 to i1 true in the following example:

declare void @​use()

define void @​f(i32 %len) {
entry:
%e = icmp slt i32 0, %len
br i1 %e, label %loop, label %leave

loop:
%idx = phi i64 [ 0, %entry ], [ %idx.inc, %be ]
%idx.inc = add i64 %idx, 1
%idx.tr = trunc i64 %idx to i32
call void @​use()
%c0 = icmp slt i32 %idx.tr, %len
br i1 %c0, label %be, label %leave

be:
%idx.inc.tr = trunc i64 %idx.inc to i32
call void @​use()
%c1 = icmp slt i32 %idx.inc.tr, %len
br i1 %c1, label %loop, label %leave

leave:
ret void
}

The interesting bit is that SCEV already has all the smarts required to optimize this check away; and calling simplifyLoopIVs optimizes the check as expected. -indvars does not get this case because it does not look through truncates of induction variables, and thus does not try to eliminate %c0.

[atrick]

The funny thing is, IndVars doesn't even care about trunc. It's only looking for sext/zext.

It would seem fine to return a boolean from visitCast indicating whether it is safe to continue processing the uses of the cast. In the case of trunc it's certainly safe. It's probably ok in other cases too, but harder to prove to myself. My concern would be that sign/zero extend comes along later and expects the IV to still contain those instructions.

[sanjoy]

It would seem fine to return a boolean from visitCast indicating whether it
is safe to continue processing the uses of the cast. In the case of trunc
it's certainly safe. It's probably ok in other cases too, but harder to
prove to myself. My concern would be that sign/zero extend comes along later
and expects the IV to still contain those instructions.

I had tried a variant of that (visitCast returns false to continue the
search) earlier, but I ran into an issue: -indvars gets confused with
code of the form:

%idx = i64 {0,+,1}
%t = trunc %idx to i32
%e = sext %t to i64

It tries to sign extend %idx to i64 after discovering %e. This
fails because you cannot sext i64 to i64. Is this what you meant by
"sign/zero extend comes along later and expects the IV to still
contain those instructions."? I think the specific instance above can
be fixed, but I wonder if there are other invariants that
prevent -indvars from looking at narrow uses of wider induction
variables that it's simplifying.

A second option is to write a loop pass that just calls
simplifyLoopIVs on each loop. This pass can then be scheduled
independently of -indvars, and should be able to get the above case.