Is this a bug with loop unrolling and TargetTransformInfo ?

Hi,

I ran into this issue recently and wanted to know if it was a bug or expected behavior.

In the R600 backend's TargetTransformInfo implementation, we were setting
UnrollingPreferences::Count = UINT_MAX. This was a mistake as we should have been
setting UnrollingPreferences::MaxCount instead. However, as a result of setting
Count to UINT_MAX, this loop would be unrolled 15 times:

if (b + 4 > a) {
  for (int i = 0; i < 4; i++, b++) {
    if (b + 1 <= a)
      *(dst + c + b) = 0;
     else
       break;
  }
}

Is this the expected behavior? Is the loop unroll pass supposed to use the
value of UnrollingPreferecnes::Count even if it is clearly wrong?

I have an LLVM IR test case for this issue attached to this patch:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150202/257276.html

-Tom

From: "Tom Stellard" <tom@stellard.net>
To: llvmdev@cs.uiuc.edu
Sent: Wednesday, February 4, 2015 1:45:26 PM
Subject: [LLVMdev] Is this a bug with loop unrolling and TargetTransformInfo ?

Hi,

I ran into this issue recently and wanted to know if it was a bug or
expected behavior.

In the R600 backend's TargetTransformInfo implementation, we were
setting
UnrollingPreferences::Count = UINT_MAX. This was a mistake as we
should have been
setting UnrollingPreferences::MaxCount instead. However, as a result
of setting
Count to UINT_MAX, this loop would be unrolled 15 times:

A bug regardless? Where did 15 come from?

-Hal

> From: "Tom Stellard" <tom@stellard.net>
> To: llvmdev@cs.uiuc.edu
> Sent: Wednesday, February 4, 2015 1:45:26 PM
> Subject: [LLVMdev] Is this a bug with loop unrolling and TargetTransformInfo ?
>
> Hi,
>
> I ran into this issue recently and wanted to know if it was a bug or
> expected behavior.
>
> In the R600 backend's TargetTransformInfo implementation, we were
> setting
> UnrollingPreferences::Count = UINT_MAX. This was a mistake as we
> should have been
> setting UnrollingPreferences::MaxCount instead. However, as a result
> of setting
> Count to UINT_MAX, this loop would be unrolled 15 times:

A bug regardless? Where did 15 come from?

It's the value computed by this loop on line 453 of the LoopUnrolPass.
Inputs are:

Count = 4294967295
PartialThreshold = 150
UnrolledSize = 34359738362

// Reduce unroll count to be the largest power-of-two factor of
// the original count which satisfies the threshold limit.
while (Count != 0 && UnrolledSize > PartialThreshold) {
  Count >>= 1;
  UnrolledSize = (LoopSize-2) * Count + 2;
}

I think the bug here may actually be in
LoopUnroll::selectUnrollCount(). It looks like it ends up returning UP.Count
in some cases when it is larger than TripCount.

-Tom

From: "Tom Stellard" <tom@stellard.net>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Wednesday, February 4, 2015 2:43:16 PM
Subject: Re: [LLVMdev] Is this a bug with loop unrolling and TargetTransformInfo ?

> > From: "Tom Stellard" <tom@stellard.net>
> > To: llvmdev@cs.uiuc.edu
> > Sent: Wednesday, February 4, 2015 1:45:26 PM
> > Subject: [LLVMdev] Is this a bug with loop unrolling and
> > TargetTransformInfo ?
> >
> > Hi,
> >
> > I ran into this issue recently and wanted to know if it was a bug
> > or
> > expected behavior.
> >
> > In the R600 backend's TargetTransformInfo implementation, we were
> > setting
> > UnrollingPreferences::Count = UINT_MAX. This was a mistake as we
> > should have been
> > setting UnrollingPreferences::MaxCount instead. However, as a
> > result
> > of setting
> > Count to UINT_MAX, this loop would be unrolled 15 times:
>
> A bug regardless? Where did 15 come from?
>

It's the value computed by this loop on line 453 of the
LoopUnrolPass.
Inputs are:

Count = 4294967295
PartialThreshold = 150
UnrolledSize = 34359738362

// Reduce unroll count to be the largest power-of-two factor of
// the original count which satisfies the threshold limit.
while (Count != 0 && UnrolledSize > PartialThreshold) {
  Count >>= 1;
  UnrolledSize = (LoopSize-2) * Count + 2;
}

I think the bug here may actually be in
LoopUnroll::selectUnrollCount(). It looks like it ends up returning
UP.Count
in some cases when it is larger than TripCount.

That does indeed seem like a bug, or something that should assert (if Count is too large).

-Hal