[LLVMdev] missing optimization for icmps in induction variables?

[Sanjoy Das]

Hi all,

I'm trying to get llvm to optimize away the %cmp to true in

define i32 @foo(i32* %array, i32* %length_ptr, i32 %init) {
 entry:
  %length = load i32* %length_ptr, !range !0
  %len.sub.1 = sub i32 %length, 1
  %upper = icmp slt i32 %init, %len.sub.1
  br i1 %upper, label %loop, label %exit

 loop:
  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
  %civ.inc = add i32 %civ, 1
  %cmp = icmp slt i32 %civ.inc, %length
  br i1 %cmp, label %latch, label %break

 latch:
  store i32 0, i32* %array
  %check = icmp slt i32 %civ.inc, %len.sub.1
  br i1 %check, label %loop, label %break

 break:
  ret i32 %civ.inc

 exit:
  ret i32 42
}

!0 = !{i32 0, i32 2147483647}


One way to prove "%cmp == true" in two steps

 1. notice that since both on the backedge and entry, %civ is known to
    be less than %len.sub.1, which not i32_signed_max.  This means
    %civ.inc is an "add nsw".

 2. on both the entry and backedge, we know "%civ `slt` %len.sub.1".
    This implies "(%civ nsw+ 1) `slt` (%len.sub.1 nsw+ 1)" ==>
    "%civ.inc `slt` %len".

Currently neither of these happen (i.e. even if I make transformation
(1) manually, (2) does not kick in).

Is the above reasoning correct?  If it is, what is the right place to
add this logic to?  I'm thinking ScalarEvolution (so that this gets
picked up by SimplifyIndVar), but maybe there is a more idiomatic
place?  The case above is a simplified form of my real workload, which
involves smin and smax expressions; so the implementation has to be
easily generalizable to such cases.


Thanks,
-- Sanjoy