[llvm-dev] ScalarEvolution questions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] ScalarEvolution questions

Robin Eklind via llvm-dev

Hi,

 

I’m new to ScalarEvolution and wanted to explore its capabilities.

 

I have following few questions:

 

1) How to compare SCEV expressions.

I have a situation to compare two SCEV to find the min among them.

Found an existing function(getMinFromExprs) in LoopAccessAnalysis which compares two SCEVs.

getMinFromExprs function finds the diff between two SCEV’s and then checks for the negative value to find the minimum.

While checking the negative value it specifically look for SCEVConstant.

 

Do we have anything to find the min in case of NON-SCEVConstant (with some additional information), i.e.:

SCEV1: (sext i32 (-1 + %n.addr.0) to i64)

SCEV2: 0

Extra information “n.addr.0 > 1”

 

2) How to feed the relational information to SCEV, i.e. “a > b”.

This relational information may not be explicitly available in the program.

 

3) Is there any way in SCEV to force the compute(i.e. add) by ignore the cast(sext, zext, truc)

SCEV: (2 + (sext i32 (-1 + %n.addr.0) to i64))

After force addition expecting something like:  “(1 + %n.addr.0)”

 

Any help by answer or pointers will be really useful.

 

Thanks,

Ashutosh


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ScalarEvolution questions

Robin Eklind via llvm-dev
Hi Ashutosh,

On Wed, May 9, 2018 at 3:28 AM, Nema, Ashutosh via llvm-dev
<[hidden email]> wrote:

> I’m new to ScalarEvolution and wanted to explore its capabilities.
>
> I have following few questions:
>
> 1) How to compare SCEV expressions.
>
> I have a situation to compare two SCEV to find the min among them.
>
> Found an existing function(getMinFromExprs) in LoopAccessAnalysis which
> compares two SCEVs.
>
> getMinFromExprs function finds the diff between two SCEV’s and then checks
> for the negative value to find the minimum.
>
> While checking the negative value it specifically look for SCEVConstant.
>
> Do we have anything to find the min in case of NON-SCEVConstant (with some
> additional information), i.e.:
>
> SCEV1: (sext i32 (-1 + %n.addr.0) to i64)
>
> SCEV2: 0
>
> Extra information “n.addr.0 > 1”

There is ScalarEvolution::isImpliedCond -- using it you can ask the
question "n.addr.0 > 1" implies SCEV1 != SCEV2.  However this is
private to SCEV and I don't think we should expose it as part of
SCEV's public interface.

> 2) How to feed the relational information to SCEV, i.e. “a > b”.
>
> This relational information may not be explicitly available in the program.

Take a look at how SCEV uses assumes.  Given what you've said so far,
perhaps the best fix is to add the extra constraints you have as
assumes and see what SCEV does?

> 3) Is there any way in SCEV to force the compute(i.e. add) by ignore the
> cast(sext, zext, truc)
>
> SCEV: (2 + (sext i32 (-1 + %n.addr.0) to i64))
>
> After force addition expecting something like:  “(1 + %n.addr.0)”

You can't ask SCEV to do this directly, but you can rewrite SCEV
expressions to substitute subexpressions in any way you like.  E.g.
see SCEVInitRewriter.

-- Sanjoy
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ScalarEvolution questions

Robin Eklind via llvm-dev
Thanks Sanjoy, I'll look into this.

-----Original Message-----
From: Sanjoy Das [mailto:[hidden email]]
Sent: Thursday, May 10, 2018 8:07 AM
To: Nema, Ashutosh <[hidden email]>
Cc: [hidden email]
Subject: Re: [llvm-dev] ScalarEvolution questions

Hi Ashutosh,

On Wed, May 9, 2018 at 3:28 AM, Nema, Ashutosh via llvm-dev <[hidden email]> wrote:

> I’m new to ScalarEvolution and wanted to explore its capabilities.
>
> I have following few questions:
>
> 1) How to compare SCEV expressions.
>
> I have a situation to compare two SCEV to find the min among them.
>
> Found an existing function(getMinFromExprs) in LoopAccessAnalysis
> which compares two SCEVs.
>
> getMinFromExprs function finds the diff between two SCEV’s and then
> checks for the negative value to find the minimum.
>
> While checking the negative value it specifically look for SCEVConstant.
>
> Do we have anything to find the min in case of NON-SCEVConstant (with
> some additional information), i.e.:
>
> SCEV1: (sext i32 (-1 + %n.addr.0) to i64)
>
> SCEV2: 0
>
> Extra information “n.addr.0 > 1”

There is ScalarEvolution::isImpliedCond -- using it you can ask the question "n.addr.0 > 1" implies SCEV1 != SCEV2.  However this is private to SCEV and I don't think we should expose it as part of SCEV's public interface.

> 2) How to feed the relational information to SCEV, i.e. “a > b”.
>
> This relational information may not be explicitly available in the program.

Take a look at how SCEV uses assumes.  Given what you've said so far, perhaps the best fix is to add the extra constraints you have as assumes and see what SCEV does?

> 3) Is there any way in SCEV to force the compute(i.e. add) by ignore
> the cast(sext, zext, truc)
>
> SCEV: (2 + (sext i32 (-1 + %n.addr.0) to i64))
>
> After force addition expecting something like:  “(1 + %n.addr.0)”

You can't ask SCEV to do this directly, but you can rewrite SCEV expressions to substitute subexpressions in any way you like.  E.g.
see SCEVInitRewriter.

-- Sanjoy
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ScalarEvolution questions

Robin Eklind via llvm-dev
Hi Sanjoy,

Your inputs really helped.
       
Using “isImpliedCond”, able to relate and find the min for cases like:

SCEV1: (-1 + (sext i32 %n.addr.058 to i64))<nsw>
SCEV2: 0
Extra-Condition: (n.addr.058 > 7)
Result: ‘0’ (SCEV2)

I have another case where trying to find min between two SCEVs under an extra condition.
“isImpliedCond” is not helping for below case, may be I’m missing something:

SCEV1: (1 + (-1 * (sext i32 %n.addr.058 to i64)))<nsw>
SCEV2: 0
Extra-Condition: (n.addr.058 > 7)
In this case expecting result as SCEV1.

This is how using “isImpliedCond”:
Result = SE->isImpliedCond(ICmpInst::ICMP_SGT, B, A, ICmpInst::ICMP_SGT, Var, Const);
Inputs:
A: (1 + (-1 * (sext i32 %n.addr.058 to i64)))<nsw>
B: 0
Var: %n.addr.058
Const: 7

In this case "isImpliedCond" simply returns false.

Thanks,
Ashutosh

-----Original Message-----
From: Nema, Ashutosh
Sent: Thursday, May 10, 2018 10:10 AM
To: 'Sanjoy Das' <[hidden email]>
Cc: [hidden email]
Subject: RE: [llvm-dev] ScalarEvolution questions

Thanks Sanjoy, I'll look into this.

-----Original Message-----
From: Sanjoy Das [mailto:[hidden email]]
Sent: Thursday, May 10, 2018 8:07 AM
To: Nema, Ashutosh <[hidden email]>
Cc: [hidden email]
Subject: Re: [llvm-dev] ScalarEvolution questions

Hi Ashutosh,

On Wed, May 9, 2018 at 3:28 AM, Nema, Ashutosh via llvm-dev <[hidden email]> wrote:

> I’m new to ScalarEvolution and wanted to explore its capabilities.
>
> I have following few questions:
>
> 1) How to compare SCEV expressions.
>
> I have a situation to compare two SCEV to find the min among them.
>
> Found an existing function(getMinFromExprs) in LoopAccessAnalysis
> which compares two SCEVs.
>
> getMinFromExprs function finds the diff between two SCEV’s and then
> checks for the negative value to find the minimum.
>
> While checking the negative value it specifically look for SCEVConstant.
>
> Do we have anything to find the min in case of NON-SCEVConstant (with
> some additional information), i.e.:
>
> SCEV1: (sext i32 (-1 + %n.addr.0) to i64)
>
> SCEV2: 0
>
> Extra information “n.addr.0 > 1”

There is ScalarEvolution::isImpliedCond -- using it you can ask the question "n.addr.0 > 1" implies SCEV1 != SCEV2.  However this is private to SCEV and I don't think we should expose it as part of SCEV's public interface.

> 2) How to feed the relational information to SCEV, i.e. “a > b”.
>
> This relational information may not be explicitly available in the program.

Take a look at how SCEV uses assumes.  Given what you've said so far, perhaps the best fix is to add the extra constraints you have as assumes and see what SCEV does?

> 3) Is there any way in SCEV to force the compute(i.e. add) by ignore
> the cast(sext, zext, truc)
>
> SCEV: (2 + (sext i32 (-1 + %n.addr.0) to i64))
>
> After force addition expecting something like:  “(1 + %n.addr.0)”

You can't ask SCEV to do this directly, but you can rewrite SCEV expressions to substitute subexpressions in any way you like.  E.g.
see SCEVInitRewriter.

-- Sanjoy
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ScalarEvolution questions

Robin Eklind via llvm-dev
On Wed, May 16, 2018 at 1:24 AM, Nema, Ashutosh <[hidden email]> wrote:

> Hi Sanjoy,
>
> Your inputs really helped.
>
> Using “isImpliedCond”, able to relate and find the min for cases like:
>
> SCEV1: (-1 + (sext i32 %n.addr.058 to i64))<nsw>
> SCEV2: 0
> Extra-Condition: (n.addr.058 > 7)
> Result: ‘0’ (SCEV2)
>
> I have another case where trying to find min between two SCEVs under an extra condition.
> “isImpliedCond” is not helping for below case, may be I’m missing something:
>
> SCEV1: (1 + (-1 * (sext i32 %n.addr.058 to i64)))<nsw>
> SCEV2: 0
> Extra-Condition: (n.addr.058 > 7)
> In this case expecting result as SCEV1.
>
> This is how using “isImpliedCond”:
> Result = SE->isImpliedCond(ICmpInst::ICMP_SGT, B, A, ICmpInst::ICMP_SGT, Var, Const);
> Inputs:
> A: (1 + (-1 * (sext i32 %n.addr.058 to i64)))<nsw>
> B: 0
> Var: %n.addr.058
> Const: 7
>
> In this case "isImpliedCond" simply returns false.

In this case isImpliedCond is probably just being imprecise.  We could
make it more precise though, but can you give us some detail on what
you're actually trying to do?

-- Sanjoy

>
> Thanks,
> Ashutosh
>
> -----Original Message-----
> From: Nema, Ashutosh
> Sent: Thursday, May 10, 2018 10:10 AM
> To: 'Sanjoy Das' <[hidden email]>
> Cc: [hidden email]
> Subject: RE: [llvm-dev] ScalarEvolution questions
>
> Thanks Sanjoy, I'll look into this.
>
> -----Original Message-----
> From: Sanjoy Das [mailto:[hidden email]]
> Sent: Thursday, May 10, 2018 8:07 AM
> To: Nema, Ashutosh <[hidden email]>
> Cc: [hidden email]
> Subject: Re: [llvm-dev] ScalarEvolution questions
>
> Hi Ashutosh,
>
> On Wed, May 9, 2018 at 3:28 AM, Nema, Ashutosh via llvm-dev <[hidden email]> wrote:
>> I’m new to ScalarEvolution and wanted to explore its capabilities.
>>
>> I have following few questions:
>>
>> 1) How to compare SCEV expressions.
>>
>> I have a situation to compare two SCEV to find the min among them.
>>
>> Found an existing function(getMinFromExprs) in LoopAccessAnalysis
>> which compares two SCEVs.
>>
>> getMinFromExprs function finds the diff between two SCEV’s and then
>> checks for the negative value to find the minimum.
>>
>> While checking the negative value it specifically look for SCEVConstant.
>>
>> Do we have anything to find the min in case of NON-SCEVConstant (with
>> some additional information), i.e.:
>>
>> SCEV1: (sext i32 (-1 + %n.addr.0) to i64)
>>
>> SCEV2: 0
>>
>> Extra information “n.addr.0 > 1”
>
> There is ScalarEvolution::isImpliedCond -- using it you can ask the question "n.addr.0 > 1" implies SCEV1 != SCEV2.  However this is private to SCEV and I don't think we should expose it as part of SCEV's public interface.
>
>> 2) How to feed the relational information to SCEV, i.e. “a > b”.
>>
>> This relational information may not be explicitly available in the program.
>
> Take a look at how SCEV uses assumes.  Given what you've said so far, perhaps the best fix is to add the extra constraints you have as assumes and see what SCEV does?
>
>> 3) Is there any way in SCEV to force the compute(i.e. add) by ignore
>> the cast(sext, zext, truc)
>>
>> SCEV: (2 + (sext i32 (-1 + %n.addr.0) to i64))
>>
>> After force addition expecting something like:  “(1 + %n.addr.0)”
>
> You can't ask SCEV to do this directly, but you can rewrite SCEV expressions to substitute subexpressions in any way you like.  E.g.
> see SCEVInitRewriter.
>
> -- Sanjoy
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ScalarEvolution questions

Robin Eklind via llvm-dev
Hi Sanjoy,

I have a situation where a collection of SCEV's is required to be compared, to find the minimum & maximum. This comparison is with extra information/constraint which we have derived with some analysis. The extra constraint is in the form of "var1 > var2".

I'll look into 'isImpliedCond' and try to improve it for the case mentioned in previous mail.

Thanks,
Ashutosh

-----Original Message-----
From: Sanjoy Das [mailto:[hidden email]]
Sent: Wednesday, May 16, 2018 10:13 PM
To: Nema, Ashutosh <[hidden email]>
Cc: [hidden email]
Subject: Re: [llvm-dev] ScalarEvolution questions

On Wed, May 16, 2018 at 1:24 AM, Nema, Ashutosh <[hidden email]> wrote:

> Hi Sanjoy,
>
> Your inputs really helped.
>
> Using “isImpliedCond”, able to relate and find the min for cases like:
>
> SCEV1: (-1 + (sext i32 %n.addr.058 to i64))<nsw>
> SCEV2: 0
> Extra-Condition: (n.addr.058 > 7)
> Result: ‘0’ (SCEV2)
>
> I have another case where trying to find min between two SCEVs under an extra condition.
> “isImpliedCond” is not helping for below case, may be I’m missing something:
>
> SCEV1: (1 + (-1 * (sext i32 %n.addr.058 to i64)))<nsw>
> SCEV2: 0
> Extra-Condition: (n.addr.058 > 7)
> In this case expecting result as SCEV1.
>
> This is how using “isImpliedCond”:
> Result = SE->isImpliedCond(ICmpInst::ICMP_SGT, B, A,
> ICmpInst::ICMP_SGT, Var, Const);
> Inputs:
> A: (1 + (-1 * (sext i32 %n.addr.058 to i64)))<nsw>
> B: 0
> Var: %n.addr.058
> Const: 7
>
> In this case "isImpliedCond" simply returns false.

In this case isImpliedCond is probably just being imprecise.  We could make it more precise though, but can you give us some detail on what you're actually trying to do?

-- Sanjoy

>
> Thanks,
> Ashutosh
>
> -----Original Message-----
> From: Nema, Ashutosh
> Sent: Thursday, May 10, 2018 10:10 AM
> To: 'Sanjoy Das' <[hidden email]>
> Cc: [hidden email]
> Subject: RE: [llvm-dev] ScalarEvolution questions
>
> Thanks Sanjoy, I'll look into this.
>
> -----Original Message-----
> From: Sanjoy Das [mailto:[hidden email]]
> Sent: Thursday, May 10, 2018 8:07 AM
> To: Nema, Ashutosh <[hidden email]>
> Cc: [hidden email]
> Subject: Re: [llvm-dev] ScalarEvolution questions
>
> Hi Ashutosh,
>
> On Wed, May 9, 2018 at 3:28 AM, Nema, Ashutosh via llvm-dev <[hidden email]> wrote:
>> I’m new to ScalarEvolution and wanted to explore its capabilities.
>>
>> I have following few questions:
>>
>> 1) How to compare SCEV expressions.
>>
>> I have a situation to compare two SCEV to find the min among them.
>>
>> Found an existing function(getMinFromExprs) in LoopAccessAnalysis
>> which compares two SCEVs.
>>
>> getMinFromExprs function finds the diff between two SCEV’s and then
>> checks for the negative value to find the minimum.
>>
>> While checking the negative value it specifically look for SCEVConstant.
>>
>> Do we have anything to find the min in case of NON-SCEVConstant (with
>> some additional information), i.e.:
>>
>> SCEV1: (sext i32 (-1 + %n.addr.0) to i64)
>>
>> SCEV2: 0
>>
>> Extra information “n.addr.0 > 1”
>
> There is ScalarEvolution::isImpliedCond -- using it you can ask the question "n.addr.0 > 1" implies SCEV1 != SCEV2.  However this is private to SCEV and I don't think we should expose it as part of SCEV's public interface.
>
>> 2) How to feed the relational information to SCEV, i.e. “a > b”.
>>
>> This relational information may not be explicitly available in the program.
>
> Take a look at how SCEV uses assumes.  Given what you've said so far, perhaps the best fix is to add the extra constraints you have as assumes and see what SCEV does?
>
>> 3) Is there any way in SCEV to force the compute(i.e. add) by ignore
>> the cast(sext, zext, truc)
>>
>> SCEV: (2 + (sext i32 (-1 + %n.addr.0) to i64))
>>
>> After force addition expecting something like:  “(1 + %n.addr.0)”
>
> You can't ask SCEV to do this directly, but you can rewrite SCEV expressions to substitute subexpressions in any way you like.  E.g.
> see SCEVInitRewriter.
>
> -- Sanjoy
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev