missing optimization for icmps in induction variables?

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

Sanjoy Das wrote:

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.

Before reading your two steps I was going to suggest jump threading. Jump threading is where we optimize redundant tests across blocks that feed into branches (block A tests property X and branches to block B which also tests property X). However jump threading is powered by lazy value info, which I don't think is suited for the sort of reasoning in your two steps.

One option is GVN. GVN does have x < y expressions but it doesn't try to deduce nuw/nsw bits. It might be possible to add that, but it isn't immediately obvious to me how. GVN also does path-sensitive expression commoning.

Nick

Hi Nick,

I checked in something towards (1) yesterday -- http://reviews.llvm.org/D6748

I was under the impression that (2) is exactly the kind of predicate
ScalarEvolution::isKnownPredicate is designed to solve (using
isImpliedCondXXX or something like that). Is there a reason to prefer
GVN over that?

Sanjoy Das wrote:

Hi Nick,

I checked in something towards (1) yesterday -- http://reviews.llvm.org/D6748

Ah, I missed that. Catching up on email.

I was under the impression that (2) is exactly the kind of predicate
ScalarEvolution::isKnownPredicate is designed to solve (using
isImpliedCondXXX or something like that). Is there a reason to prefer
GVN over that?

If you think of the problem as a loop problem then yes ScalarEvolution::isKnownPredicate makes sense. If you think of it as a redundancy elimination problem then GVN makes sense. Does this sort of problem occur outside of loops?

If you think of the problem as a loop problem then yes
ScalarEvolution::isKnownPredicate makes sense. If you think of it as a
redundancy elimination problem then GVN makes sense. Does this sort of
problem occur outside of loops?

I've only observed them happen inside loops, but that is only because
I've been looking at loops. :slight_smile: At least in theory if LLVM's GVN can
be made to in a path-sensitive manner, then there is no need to do
such tricks using SCEV.

I've only cursorily glanced into GVN.cpp, but given that we want LLVM
to conclude that '(x nsw+ 5) SLT L' implies 'x SLT (L nsw- 5)', will
the value numbering for cmp expressions have to become richer? The
operands to icmp themselves won't value number to the same value,
because they're not the same; but maybe there is some canonicalization
form we want to reduce the icmp expressions to before numbering them?

-- Sanjoy