Failure to turn a div by power of 2 into a single shift

Hello,

I have a simple loop like below

int I, j;

for (j = n; j > 1; j = i) {

i = j / 2;

}

The signed division can be safely turned into a single shift since j is known to be positive from the loop guard. LLVM currently cannot find out j is positive and compiles the above division into 3 instructions. Any thoughts on where to fix this?

Thank you in advance,

Haicheng

SCEV should be able to easily prove that j is positive here. I’m not sure where the right place to use that information would be in this case. Sanjoy, can you comment?

Philip

I’d missed the fact that j wasn’t just being decremented. This isn’t as easy as I said.

Philip

SCEV certainly should be able to prove that "j" is positive; but I'm
not sure if it is being queried about that via isKnownPredicate.

An interesting variant of the original example is

void foo(int n, volatile int* p) {
  int i, j;
  for (j = n; j > 1; j = i) {
    *p = (j > 0);
    i = j / 2;
  }
}

where the volatile store to *p does get optimized to "*p = true", but
that happens before loop rotation, when the loop is still in the form
of

define void @foo(i32 %n, i32* nocapture %p) #0 {
entry:
  br label %for.cond

for.cond: ; preds = %for.body, %entry
  %j.0 = phi i32 [ %n, %entry ], [ %div, %for.body ]
  %cmp = icmp sgt i32 %j.0, 1
  br i1 %cmp, label %for.body, label %for.end

for.body: ; preds = %for.cond
  %cmp1 = icmp sgt i32 %j.0, 0
  %conv = zext i1 %cmp1 to i32
  store volatile i32 %conv, i32* %p, align 4, !tbaa !2
  %div = sdiv i32 %j.0, 2
  br label %for.cond

for.end: ; preds = %for.cond
  ret void
}

and the dominating check on j > 1 is still "obvious".

-- Sanjoy

Thank you, both of you.

In Sanjoy's example, CorrelatedValuePropagation makes the change. I guess I can do the similar thing to turn the sdiv to udiv.

Best,

Haicheng

I created a patch in D17921 to address this.

Best,

Haicheng