llvm dev - Jun 2009 - [LLVMdev] Handling SMax(N, N - constInt) in Scalar Evolution pass

Now that icmp and fcmp have supported returning vectors of i1 for a 
while, I think it's time to remove the vicmp and vfcmp instructions from 
LLVM. The good news is that we've never shipped a release that included 
them so we won't be providing auto-upgrade support.

There is some existing backend support for vicmp and vfcmp that looks 
different from what icmp and fcmp do. If this actually matters to you, 
please port the bits you need over to icmp/fcmp, or let me know if you 
think you still need vicmp/vfcmp and can't switch within (say) a week.

If I don't hear from anyone within a week then I'll go ahead and rip the
existing support out.

Thanks!
Nick

Hi all,

I'm working on a project which tries to prove an access to an array is
safe. For example,

int foo(int s) {
  int * p = malloc(s * sizeof int);
  ...
  int q = p[s - 2];
}

then the access of p[s - 2] always stays in bound.

I implemented a prototype using the Scalar Evolution pass. Here are the
pseudo-code of the implementation:

  const SCEV * offset = SE->getMinusSCEV(SE->getSCEV(GEP), GEPBase);
  const SCEV * bounds = SE->getSCEV(objSize);
 
  if (SE->getSMaxExpr(offset, bounds) == bounds) {
    ++safeGEPs;
  }

But it turns out that SCEVSMaxExpr does not handle the case of SMax(N,
N-2).

My question is, is there a plan to support something like this, or is it
possible to do some refactoring to enhance the capability of Scalar
Evolution? I notice that Scalar Evolution, Instruction Combining and
Memory Dependence Analysis require sort of evaluating symbolic
expression like this.

For this case SMax(A, B) is equivalent to SMax(A-B,0) + B, instruction
combining handles  sophisticated expressions like (A+B)-B pretty well.
It would be great if Scalar Evolution can support this.

Any comments are appreciated.

Cheers,

Haohui

Mai, Haohui wrote:
> Hi all,
> 
> I'm working on a project which tries to prove an access to an array is
> safe. For example,
> 
> int foo(int s) {
>   int * p = malloc(s * sizeof int);
>   ...
>   int q = p[s - 2];
> }
> 
> then the access of p[s - 2] always stays in bound.
> 
> I implemented a prototype using the Scalar Evolution pass. Here are the
> pseudo-code of the implementation:
> 
>   const SCEV * offset = SE->getMinusSCEV(SE->getSCEV(GEP), GEPBase);
>   const SCEV * bounds = SE->getSCEV(objSize);
>  
>   if (SE->getSMaxExpr(offset, bounds) == bounds) {
>     ++safeGEPs;
>   }
> 
> But it turns out that SCEVSMaxExpr does not handle the case of SMax(N,
> N-2).
Consider 8-bit integers and N = -127. N-1 equals INT_MIN and N-2 then is 
equal to INT_MAX, or 127. In that case, the SMax would equal N-2, not N.

In other cases (like N = 2) the SMax would equal N, not N-2.

Because of this, we cannot reduce this SMax any further. Your suggestion 
that "SMax(A, B) == SMax(A-B, 0) + B" is incorrect.

Nick
> My question is, is there a plan to support something like this, or is it
> possible to do some refactoring to enhance the capability of Scalar
> Evolution? I notice that Scalar Evolution, Instruction Combining and
> Memory Dependence Analysis require sort of evaluating symbolic
> expression like this.
> 
> For this case SMax(A, B) is equivalent to SMax(A-B,0) + B, instruction
> combining handles  sophisticated expressions like (A+B)-B pretty well.
> It would be great if Scalar Evolution can support this.
> 
> Any comments are appreciated.
> 
> Cheers,
> 
> Haohui
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Hi Nick,
> Now that icmp and fcmp have supported returning vectors of i1 for a 
> while,
the code generators don't know how to codegen vectors of i1, so does
this actually work?

Ciao,

Duncan.

On Jun 24, 2009, at 12:47 AM, Duncan Sands wrote:
> Hi Nick,
>
>> Now that icmp and fcmp have supported returning vectors of i1 for a
>> while,
>
> the code generators don't know how to codegen vectors of i1, so does
> this actually work?
No, but there are no clients of them yet.

-Chris