llvm dev - Dec 2012 - [LLVMdev] [PATCH] Teaching ScalarEvolution to handle IV=add(zext(trunc(IV)), Step)

Ok, so I think I've mis-represented what's really happening.
Ignore my previous statements concerning %add :)

Again, given:
05:  for.body:                                         ; preds = %entry, 
%for.body
06:    %j.04 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
07:    %result.03 = phi i32 [ 0, %entry ], [ %add, %for.body ]
08:    %conv2 = and i32 %result.03, 255
09:    %add = add nsw i32 %conv2, 3
10:    %inc = add nsw i32 %j.04, 1
11:    %cmp = icmp slt i32 %inc, 8000
12:    br i1 %cmp, label %for.body, label %for.end

LLVM executes the following:

01:  createSCEV(%conv2 = and i32 %result.03, 255)
02:    calls getSCEV(%result.03)
03:       returns (3 + (zext i8 {-3,+,3}<%for.body> to i32))
04:    calls getTruncateExpr((3 + (zext i8 {-3,+,3}<%for.body> to i32)),
i8)
05:       calls getTruncateExpr(3)
06:          returns 3
07:       calls getTruncateExpt((zext i8 {-3,+,3}<%for.body> to i32))
08:          returns {-3,+,3}<%for.body>
09:       returns {0,+,3}<%for.body>
10:    calls getZeroExtendExpr({0,+,3}<%for.body>, i32);
11:       returns (zext i8 {0,+,3}<%for.body> to i32)
12:    returns (zext i8 {0,+,3}<%for.body> to i32)

This expression is (I believe) correct for %conv2.

The intent of the patch is to construct the correct (evaluatable)
expression for %result.03 being fed into the computation of %conv2.

Does that make more sense?

Matthew C.

On 12/18/2012 12:54 PM, Dan Gohman wrote:
> On Tue, Dec 18, 2012 at 9:56 AM, Matthew Curtis <mcurtis at
codeaurora.org> wrote:
>> Here's how I'm evaluating the expression (in my head):
>>
>> 00: Add(ZeroExtend(Truncate(Minus(AddRec(Start=0,Step=3)[n],3), i8),
i32),3)
>>                                                           |
>> 01: Add(ZeroExtend(Truncate(Minus(AddRec(Start=0,Step=3)[0],3), i8),
i32),3)
>>                                    |
>> 02: Add(ZeroExtend(Truncate(Minus(3,3), i8), i32),3)
> This step is wrong. The start value of the addrec is 0.
>
> Dan
>
>>                              |
>> 03: Add(ZeroExtend(Truncate(0, i8), i32),3)
>>                     |
>> 04: Add(ZeroExtend(0, i32),3)
>>          |
>> 05: Add(0,3)
>>      |
>> 06: 3
>>
>> Thanks again.
>> Matthew Curtis

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The
Linux Foundation

On Thu, Dec 20, 2012 at 8:36 AM, Matthew Curtis <mcurtis at
codeaurora.org> wrote:
> Ok, so I think I've mis-represented what's really happening.
> Ignore my previous statements concerning %add :)
>
> Again, given:
>
> 05:  for.body:                                         ; preds = %entry,
> %for.body
> 06:    %j.04 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
> 07:    %result.03 = phi i32 [ 0, %entry ], [ %add, %for.body ]
> 08:    %conv2 = and i32 %result.03, 255
> 09:    %add = add nsw i32 %conv2, 3
> 10:    %inc = add nsw i32 %j.04, 1
> 11:    %cmp = icmp slt i32 %inc, 8000
> 12:    br i1 %cmp, label %for.body, label %for.end
>
> LLVM executes the following:
>
> 01:  createSCEV(%conv2 = and i32 %result.03, 255)
> 02:    calls getSCEV(%result.03)
> 03:       returns (3 + (zext i8 {-3,+,3}<%for.body> to i32))
The problem is that this is not a correct expression for %result.03.
It isn't safe to use incorrect expressions in ScalarEvolution even if
it happens to work out in the case you're looking at.

Dan

On 12/21/2012 12:26 PM, Dan Gohman wrote:
> On Thu, Dec 20, 2012 at 8:36 AM, Matthew Curtis <mcurtis at
codeaurora.org> wrote:
>> Ok, so I think I've mis-represented what's really happening.
>> Ignore my previous statements concerning %add :)
>>
>> Again, given:
>>
>> 05:  for.body:                                         ; preds =
%entry,
>> %for.body
>> 06:    %j.04 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
>> 07:    %result.03 = phi i32 [ 0, %entry ], [ %add, %for.body ]
>> 08:    %conv2 = and i32 %result.03, 255
>> 09:    %add = add nsw i32 %conv2, 3
>> 10:    %inc = add nsw i32 %j.04, 1
>> 11:    %cmp = icmp slt i32 %inc, 8000
>> 12:    br i1 %cmp, label %for.body, label %for.end
>>
>> LLVM executes the following:
>>
>> 01:  createSCEV(%conv2 = and i32 %result.03, 255)
>> 02:    calls getSCEV(%result.03)
>> 03:       returns (3 + (zext i8 {-3,+,3}<%for.body> to i32))
> The problem is that this is not a correct expression for %result.03.
> It isn't safe to use incorrect expressions in ScalarEvolution even if
> it happens to work out in the case you're looking at.
>
> Dan
Any suggestions on how to construct a correct expression? Or otherwise 
teach ScalarEvolution to handle this case?

BTW, just so I understand, the expression for %result.03 is correct for 
n > 0, right?

Matthew C.

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The
Linux Foundation